Operating System CPU Scheduing - 2 Monday, August 11, 2008

Roadmap Basic Concepts Scheduling Criteria Scheduling Algorithms Real-Time Scheduling Multiple-Processor Scheduling Operating System Examples Algorithm Evaluation 多道程序设计的目标是在任何时候都有一个进程在运行，以使CPU使用率最大化。 调度是操作系统的基本功能。几乎所有计算机资源在使用前都要被调度。当然，CPU是最为重要的计算机资源之一。因此，CPU调度对操作系统设计来说非常重要。 8/11/2008 6:14 PM bettynj@gmail.com

Priority Scheduling A priority number (integer) is associated with each process, The CPU is allocated to the process with the highest priority (smallest integer  highest priority). Preemptive nonpreemptive SJF is a priority scheduling whose priority is the predicted next CPU burst time. 优先权调度算法：每个进程都有一个优先权与其关联，具有最高优先权的进程会被分配到CPU。具有相同优先权的进程按FCFS顺序调度。 SJF算法作为优先权算法，其优先权为下一个CPU区间的倒数。CPU区间越大，则优先权越小；反之亦然。 优先权调度可以使可抢占的或者非抢占的。当一个进程到达就绪队列时，其优先权与当前运行进程的优先权相比较。如果新到达进程的优先权高于当前运行进程的优先权，那么抢占优先权调度算法会抢占CPU。非抢占优先权调度算法只是将新进程加到就绪队列的头部。 8/11/2008 6:14 PM bettynj@gmail.com

Example of Priority Scheduling Process Burst Time Priority P1 10 3 P2 1 1 P3 2 4 P4 1 5 P5 5 2 The processes have arrived at time 0, in the order P1, P2, P3, P4, P5. The Gantt chart: Average waiting time = (6 + 0 + 16 +18 + 1)/5 = 8.2 P2 P5 1 18 P3 6 P1 P4 19 16 8/11/2008 6:14 PM bettynj@gmail.com

Priority Scheduling (cont.) Problem : Starvation, i.e. low priority processes may never execute. Solution : Aging, i.e. as time progresses increase the priority of the process. 优先权可通过内部或外部方式来定义。 内部优先权使用一些可测量数据以计算进程优先权，如时间极限、内存要求、打开文件的数量和平均I/O时间区间和平均CPU时间区间之比等。 外部优先权是通过操作系统之外的准则来设置的，如进程重要性、用于支付使用计算机的费用类型和数量、赞助工作的单位等。 优先权调度算法的一个主要问题是无穷阻塞（或饥饿），使某个低优先权进程无穷等待CPU在一个重负载计算机系统中，平稳的高优先权进程可以阻止低优先权进程获得CPU。 解决方案：老化，即以逐渐增加在系统中等待很长时间的进程的优先权的技术。 8/11/2008 6:14 PM bettynj@gmail.com

Round Robin (RR) Each process gets a small unit of CPU time (time quantum), usually 10-100 milliseconds. Keep the ready queue as a FIFO queue of processes, and new processes are added to the tail of the ready queue. The CPU scheduler picks the first process from the ready queue, sets a timer to interrupt after 1 time quantum, and dispatches the process. 轮转法调度算法是专门为分时系统而设计的。它类似于FCFS调度，但是增加了抢占以在进程间切换。定义一个较小时间单元，称为时间量或时间片，通常为10ms到100ms。就绪队列作为循环队列处理。CPU调度程序循环就绪队列，为每个进程分配不超过一个时间片间隔的CPU。 8/11/2008 6:14 PM bettynj@gmail.com

Round Robin (cont.) If the process has a CPU burst: less than 1 time quantum The process itself will release the CPU voluntarily. The scheduler will then proceed to the next process in the ready queue. longer than 1 time quantum The timer will go off and will cause an interrupt to the OS. Execute a context switch, and the process will be put at the tail of the ready queue. The CPU scheduler will then select the next process in the ready queue. 此后，可能存在两种情况： 进程可能只需要小于一个时间片的CPU区间。此时，进程本身会自动释放CPU。调度程序接着会处理就绪队列的下一个进程。 当前运行进程的CPU区间比一个时间片要长，定时器会中断并产生操作系统中断。进行上下文切换，该进程会被加入到就绪队列的尾部。 接着，CPU调度程序会选择就绪队列中的下一个进程 8/11/2008 6:14 PM bettynj@gmail.com

Example of RR with Time Quantum = 4 Process Burst Time P1 24 P2 3 P3 3 The Gantt chart is: Average waiting time is (6 + 4 + 7)/3=5.66 Typically, higher average turnaround than SJF, but better response. P1 P2 P3 4 7 10 14 18 22 26 30 RR调度算法中，队列中没有进程被分配超过一个时间片的CPU时间。如果进程的CPU区间超过了一个时间片，那么该进程被抢占，而被放回到就绪队列。RR算法是可抢占的。 8/11/2008 6:14 PM bettynj@gmail.com

Round Robin (cont.) If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once. No process waits more than (n-1)q time units. Performance q large  q small  如果就绪队列中有n个进程且时间片为q，那么每个进程会得到1/n的CPU时间，每个长度不超过q时间单元。每个进程必须等待CPU的时间不会超过(n-1)q各时间单元，直到它的下一个时间片为止。 RR算法的性能很大程度上依赖于时间片的大小。在极端情况下，如果时间片非常大（无限），那么RR策略与FCFS策略一样。如果时间片很小，那么RR方法称为处理机共享，（从理论上来说）n各进程对于用户来说都有它自己的处理器，速度各为真正处理器速度的1/n。 FCFS q must be large with respect to context switch, otherwise overhead is too high. 8/11/2008 6:14 PM bettynj@gmail.com

Time Quantum and Context Switch Time 上下文切换对RR的影响：假设只有一个具有10个时间单元的进程。如果时间片为12个时间单元，那么进程在不到一个时间片内就能完成，且没有额外开销。而如果时间片为6个时间单元，那么进程需要两个时间片，并产生了一次上下文切换。如果时间片为1个单元，那么就有9个上下文切换，相应地使进程执行减慢。 因此，希望时间片要比上下文切换时间长。如果上下文切换时间约为时间片的10%，那么约10%的CPU时间会浪费在上下文切换上。 8/11/2008 6:14 PM bettynj@gmail.com

Turnaround Time Varies With The Time Quantum 周转时间也依赖于时间片的大小。 8/11/2008 6:14 PM bettynj@gmail.com

Multilevel Queue Ready queue is partitioned into separate queues, for example: foreground (interactive) background (batch) Each queue has its own scheduling algorithm, for example: foreground – RR background – FCFS 多级队列调度将就绪队列分成多个独立队列。根据进程的某些属性，如内存大小、进程优先权或进程类型，进程会被永久地分配到一个队列。每个队列有自己的调度算法。 8/11/2008 6:14 PM bettynj@gmail.com

Multilevel Queue Scheduling 8/11/2008 6:14 PM bettynj@gmail.com

Multilevel Queue (cont.) Scheduling must be done between the queues. Fixed priority scheduling; (i.e., serve all from foreground then from background). Possibility of starvation. Time slice – each queue gets a certain amount of CPU time which it can schedule amongst its processes; i.e.: 80% to foreground in RR 20% to background in FCFS 队列之间必须有调度，通常采用固定优先权可抢占调度来实现。 每个队列与更低优先权队列相比有绝对的优先权。 另一种可能是在队列之间划分时间片。每个队列都有一定的CPU时间，这可用于调度队列内的不同进程。 8/11/2008 6:14 PM bettynj@gmail.com

Multilevel Feedback Queue Multilevel feedback queue scheduling allows a process to move between queues. The idea is to separate processes with different CPU-burst characteristics. If a process uses too much CPU time, it will be moved to a lower-priority queue. A process that waits too long in a lower-priority queue may be moved to a higher-priority queue. 多级队列调度算法中进程并不在队列之间移动，优点是低调度开销，缺点是不够灵活。 多级反馈队列调度允许进程在队列之间移动。其主要思想是根据不同CPU区间特点以区分进程。如果进程使用过多CPU时间，那么它会被移到更低优先权队列。这种方案会将I/O约束和交互式进程留在较高优先权队列。类似地，在较低优先权队列中等待过长的进程会被转移到较高优先权队列。这种形式的老化能阻止饥饿的发生。 8/11/2008 6:14 PM bettynj@gmail.com

Example of Multilevel Feedback Queue Three queues: Q0 – time quantum 8 ms Q1 – time quantum 16 ms Q2 – FCFS Scheduling A new job enters queue Q0 which is served FCFS. When it gains CPU, job receives 8 milliseconds. If it does not finish in 8 milliseconds, job is moved to queue Q1. At Q1 job is again served FCFS and receives 16 additional milliseconds. If it still does not complete, it is preempted and moved to queue Q2. 进入就绪队列的进程被放在队列0内。队列0的每个进程都有8ms的时间片。如果一个进程必能在这一时间内完成，那么它就被移到队列1的尾部。如果队列0为空，队列1头部进程会得到一个16ms的时间片。如果它不能完成，那么它将被抢占，并被放到队列2中。只有当队列0和1为空时，队列2内的进程才可根据FCFS来运行。 8/11/2008 6:14 PM bettynj@gmail.com

Multilevel Feedback Queue (cont.) Multilevel-feedback-queue scheduler defined by the following parameters: number of queues scheduling algorithms for each queue method used to determine when to upgrade a process method used to determine when to demote a process method used to determine which queue a process will enter when that process needs service 多级反馈队列调度程序可由下列参数来定义： 队列数量 每个队列的调度算法 用以确定进程何时升级到较高优先权队列的方法 用以确定进程何是降级到较低优先权队列的方法 用以确定进程在需要服务时应进入哪个队列的方法 多级反馈队列是最通用的方案，但是它也是最复杂的。 8/11/2008 6:14 PM bettynj@gmail.com

Roadmap Basic Concepts Scheduling Criteria Scheduling Algorithms Real-Time Scheduling Multiple-Processor Scheduling Operating System Examples Algorithm Evaluation 8/11/2008 6:14 PM bettynj@gmail.com

Real-Time Scheduling Hard real-time systems – required to complete a critical task within a guaranteed amount of time. Soft real-time computing – requires that critical processes receive priority over less fortunate ones. Priority schedule Less dispatch delay 实时计算可分成两种类型： 硬实时系统：需要在保证的时间内完成关键任务。 软实时系统：计算的限制较少。它要求关键进程要比其他较弱进程拥有更高的优先权。 8/11/2008 6:14 PM bettynj@gmail.com

Roadmap Basic Concepts Scheduling Criteria Scheduling Algorithms Real-Time Scheduling Multiple-Processor Scheduling Operating System Examples Algorithm Evaluation 8/11/2008 6:14 PM bettynj@gmail.com

Multiple-Processor Scheduling CPU scheduling more complex when multiple CPUs are available. Homogeneous processors within a multiprocessor. Load sharing Asymmetric multiprocessing – only one processor accesses the system data structures, alleviating the need for data sharing. 如果有多个CPU，那么调度问题就相应地更为复杂。本节主要讨论处理器功能相同（或异构）的系统，任何可用处理器可用于运行队列内的任何进程。而且还假定通用内存访问UMA。 即使对同构多处理器，也有一些调度限制。 如果有多个相同处理器可用，那么可进行负载分配。有可能为每个处理器提供独立的队列。而在此情况下，一个具有空队列的处理器会空闲，而另一个处理器会很忙。为了阻止这种情况，可使用一个共同就绪队列。所有进程都进入这一队列，并被调度到任何可用空闲处理器上。 对于这种情况，有两种调度方法可用： 一种方法是每个处理器是自我调度的。每个处理器必须被仔细编程，必须确保两个处理器不能选择同一个进程，且进程不会从队列中丢失。 另一个方法可以避免这个问题，即选择一个处理器来为其他处理器进行调度，因此创建了主-从结构。 8/11/2008 6:14 PM bettynj@gmail.com

Roadmap Basic Concepts Scheduling Criteria Scheduling Algorithms Real-Time Scheduling Multiple-Processor Scheduling Operating System Examples Algorithm Evaluation 8/11/2008 6:14 PM bettynj@gmail.com

Windows 2000 Priorities 8/11/2008 6:14 PM bettynj@gmail.com

Keystone Algorithms of CPU scheduling: FCFS SJF Priority scheduling Round robin Computation of different scheduling criteria, such as average waiting time. 8/11/2008 6:14 PM bettynj@gmail.com

Homework Consider the following set of processes, with the length of the CPU-burst time given in milliseconds: process burst time priority arrive P1 10 3 0 P2 1 1 1 P3 2 3 2 P4 1 4 3 P5 5 2 4 The processes are assumed to have arrived in the order P1, P2, P3, P4, P5, all at time 0. a. Draw four Gantt charts illustrating the execution of these processes using FCFS, preemptive SJF, a preemptive priority (smaller priority implies higher priority), and RR (quantum=2) scheduling b. What is the turnaround time of each process for each of the scheduling algorithms in part a c. What is the waiting time of each process for each of the scheduling algorithms in part a d. Which of the schedules in part a results in the minimal average waiting time (over all processes) 8/11/2008 6:14 PM bettynj@gmail.com

Homework Consider a variant of the RR scheduling algorithm where the entries in the ready queue are pointers to the PCBs. a. What would be the effect of putting two pointers to the same process in the ready queue b. What would be the major advantages and disadvantages of this scheme c. How would you modify the basic RR algorithm to achieve the same effect without the duplicate pointers 8/11/2008 6:14 PM bettynj@gmail.com

Scheduling Algorithms Operating System Scheduling Algorithms Monday, August 11, 2008