CPU调度

Posted on Edited on
1.评价准则
  • CPU使用率：<40% 轻负荷，>90% 重负荷
  • 吞吐量：一个时间单元内处理进程的数量
  • 周转时间：进程提交到完成的时间，包含了等待和处理时间。
  • 等待时间
  • 响应时间：从提交到第一次响应之间的时间间隔
2.算法
1）先到先服务（FCFS）
     最普通的一种调度方法。它是非抢占的，而且往往不是最优算法。因为它的等待时间依赖于处理任务的顺序。

2）最短作业优先（SJF）
     SJF算法被证明为是最佳算法，因为其等待时间最短。但其实现难度是无法预料下一个任务的处理时间。现在比较常用的做法是，采用估计算法来预测下一个处理时间。所以往往时间越久，预测越准确，所以SJF调度经常用于长期调度。
     可抢占式的SJF算法，被称作最短剩余时间优先调度。

3）优先权调度
     SJF是一种特殊的优先权调度算法。这个算法有个问题，即无穷阻塞，又叫饥饿。因为如果一直有高优先级任务来抢占资源，则有可能有一些低优先级任务永远得不到操作。饥饿的解决方案是老化，即随着时间的推移，增大一些低优先级任务的优先级。

4）轮转法（RR，round-robin）
     这是将CPU处理时间分成许多小的时间片，每个任务轮流获得CPU时间。这是专门为分时系统设计的，每个任务都会得到处理时间。但每次切换任务都会又一次上下文切换，这个会消耗一定的资源。

5）多级队列调度
     这是指将所有任务分成若干个处理队列，每个队列可采用不同的调度算法，然后队列之间可采用固定优先权可抢占调度，或者采用round-robin调度，即所有队列分享时间片。

6）多级反馈队列调度
     这是当下最通用的CPU调度算法。这是加强版的多级队列调度。任务可以在队列之间移动。需要长时间操作的任务，会被转移到低优先级队列；等待时间过长的任务，会被转移到高优先级队列。
     这种调度算法可由下列参数定义：
  • 队列数量
  • 每个队列的调度算法
  • 任务升级到高优先级队列的条件
  • 任务降级到低优先级队列的条件
  • 某个任务初始时该进入哪个队列     
3.Linux调度算法  
     Linux assigns higher-priority tasks longer time quanta and lower-priority tasks shorter time quanta.   The relationship between priorities and time-slice length is shown in Figure 5.15.
     Each runqueue contains two priority arrays: active and expired.The active array contains all tasks with time remaining in their time slices, and the expired array contains all expired tasks. 

     Each of these priority arrays contains a list of tasks indexed according to priority (Figure 5.16). The scheduler chooses the task with the highest priority from the active array for execution on the CPU.
     When all tasks have exhausted their time slices (that is, the active array is empty), the two priority arrays are exchanged: the expired array becomes the active array, and vice versa.
     Real-time tasks are assigned static priorities. All other tasks have dynamic priorities that are based on their nice values plus or minus the value 5. 这个要看任务的等待时间，等太久了就要减5以提高优先级，否则要加5降低优先级。
     A task’s dynamic priority is recalculated when the task has exhausted its time quantum and is to be moved to the expired array. Thus, when the two arrays are exchanged, all tasks in the new active array have been assigned new priorities and corresponding time slices.