Silberschatz,Galvin,and Gagne?19996.1Applied Operating System Concepts
Module 6,CPU Scheduling
Basic Concepts （基本概念）
Scheduling Criteria （调度准则）
Scheduling Algorithms （调度算法）
Multiple-Processor Scheduling （多处理器调度）
Real-Time Scheduling （实时调度）
Algorithm Evaluation （算法评估）
Silberschatz,Galvin,and Gagne?19996.2Applied Operating System Concepts
Basic Concepts
Maximum CPU utilization obtained with multiprogramming
（通过多道程序设计得到 CPU的最高利用率）
CPU–I/O Burst Cycle – Process execution consists of a cycle of
CPU execution and I/O wait.
（ CPU-I/O脉冲周期 - 进程的执行包括进程在 CPU上执行和等待 I/O）
CPU burst distribution
（ CPU脉冲的分布）
Silberschatz,Galvin,and Gagne?19996.3Applied Operating System Concepts
Alternating Sequence of CPU And I/O Bursts
Silberschatz,Galvin,and Gagne?19996.4Applied Operating System Concepts
Histogram of CPU-burst Times
Silberschatz,Galvin,and Gagne?19996.5Applied Operating System Concepts
CPU Scheduler
Selects from among the processes in memory that are ready
to execute,and allocates the CPU to one of them.（选择内存中的就绪进程，并分配 CPU给其中之一）
CPU scheduling decisions may take place when a process
（ CPU调度可能发生在当一个进程）,
1,Switches from running to waiting state（从运行转到等待）,
2,Switches from running to ready state（从运行转到就绪）,
3,Switches from waiting to ready（从等待转到就绪）,
4,Terminates（终止运行）,
Scheduling under 1 and 4 is nonpreemptive （ 发生在 1,4两种情况下的调度称为非抢占式调度）,
All other scheduling is preemptive （ 其他情况下发生的调度称为抢占式调度）,
Silberschatz,Galvin,and Gagne?19996.6Applied Operating System Concepts
Dispatcher
Dispatcher module gives control of the CPU to the process
selected by the short-term scheduler; this involves（进程调度模块负责将对 CPU的控制权转交给由 CPU调度程序，包括）,
– switching context（切换上下文）
– switching to user mode（切换到用户态）
– jumping to the proper location in the user program to
restart that program（跳转到用户程序的适当位置并重新运行之）
Dispatch latency – time it takes for the dispatcher to stop
one process and start another running（调度时间 –调度程序终止一个进程的运行并启动另一个进程运行所花的时间）,
Silberschatz,Galvin,and Gagne?19996.7Applied Operating System Concepts
Scheduling Criteria
CPU utilization – keep the CPU as busy as possible
（ CPU利用率 – 使 CPU尽可能的忙碌）
Throughput – the number of processes that complete their
execution per time unit（吞吐量 – 单位时间内运行完的进程数
）
Turnaround time – the interval from submission to
completion （周转时间 – 进程从提交到运行结束的全部时间
）
Waiting time – amount of time a process has been waiting in
the ready queue（等待时间 –进程在就绪队列中等待调度的时间片总和 ）
Response time – amount of time it takes from when a
request was submitted until the first response is produced,
not output (for time-sharing environment)（响应时间 – 从进程提出请求到 首次被响应 [而不是输出结果 ]的时间段 [在分时系统环境下 ] ）
Silberschatz,Galvin,and Gagne?19996.8Applied Operating System Concepts
Optimization Criteria
Max CPU utilization
（最大的 CPU利用率）
Max throughput
（最大的吞吐量）
Min turnaround time
（最短的周转时间）
Min waiting time
（最短的等待时间）
Min response time
（最短的响应时间）
Silberschatz,Galvin,and Gagne?19996.9Applied Operating System Concepts
First-Come,First-Served (FCFS) Scheduling
Example,Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order（假定进程到达顺序如下）,P1,P2,P3
The Gantt Chart for the schedule is（该调度的 Gantt图为）,
Waiting time（等待时间） for P1 = 0; P2 = 24; P3 = 27
Average waiting time（平均等待时间）,(0 + 24 + 27)/3 = 17
P1 P2 P3
24 27 300
Silberschatz,Galvin,and Gagne?19996.10Applied Operating System Concepts
FCFS Scheduling (Cont.)
Suppose that the processes arrive in the order （假定进程到达顺序如下） P2,P3,P1,
The Gantt chart for the schedule is （该调度的 Gantt图为）,
Waiting time （等待时间） for P1 = 6; P2 = 0; P3 = 3
Average waiting time （平均等待时间）,(6 + 0 + 3)/3 = 3
Much better than previous case（比前例好得多）,
Convoy effect short process behind long process
（此种结果产生是由于长进程先于短进程到达）
P1P3P2
63 300
Silberschatz,Galvin,and Gagne?19996.11Applied Operating System Concepts
Shortest-Job-First (SJF) Scheduling
Associate with each process the length of its next CPU
burst,Use these lengths to schedule the process with the
shortest time.（关联到每个进程下次运行的 CPU脉冲长度，调度最短的进程）
Two schemes:
– nonpreemptive – once CPU given to the process it
cannot be preempted until completes its CPU burst（非抢占式调度 – 一旦进程拥有 CPU，它的使用权限只能在该
CPU 脉冲结束后让出 ).
– Preemptive – if a new process arrives with CPU burst
length less than remaining time of current 法 executing
process,preempt,This scheme is know as the
Shortest-Remaining-Time-First (SRTF).（抢占式调度 – 发生在有比当前进程剩余时间片更短的进程到达时，也称为最短剩余时间优先调度）
SJF is optimal – gives minimum average waiting time for a
given set of processes.（ SJF是最优的 – 对一组指定的进程而言，它给出了最短的平均等待时间）
Silberschatz,Galvin,and Gagne?19996.12Applied Operating System Concepts
Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
SJF (non-preemptive)
Average waiting time = (0 + 6 + 3 + 7)/4 - 4
Example of Non-Preemptive SJF
P1 P3 P2
73 160
P4
8 12
Silberschatz,Galvin,and Gagne?19996.13Applied Operating System Concepts
Example of Preemptive SJF
Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
SJF (preemptive)
Average waiting time = (9 + 1 + 0 +2)/4 - 3
P1 P3P2
42 110
P4
5 7
P2 P1
16
Silberschatz,Galvin,and Gagne?19996.14Applied Operating System Concepts
Determining Length of Next CPU Burst
Can only estimate the length（其长度只能估计）,
Can be done by using the length of previous CPU bursts,
using exponential averaging（可以通过先前的 CPU脉冲长度及计算指 数均值进行）,
:D e f i n e 4.
10,3.
b u r s t C P U n e x t t h e f o r v a l u e p r e d i c t e d 2.
b u r s t C P U of l e n g h t a c t u a l 1.
1n
th
n nt
,t nnn 11
Silberschatz,Galvin,and Gagne?19996.15Applied Operating System Concepts
Examples of Exponential Averaging
=0
–?n+1 =?n
– Recent history does not count.
=1
–?n+1 = tn
– Only the actual last CPU burst counts.
If we expand the formula,we get:
n+1 =? tn+(1 -?)? tn -1 + …
+(1 -? )j? tn -1 + …
+(1 -? )n=1 tn?0
Since both? and (1 -?) are less than or equal to 1,each
successive term has less weight than its predecessor.
Silberschatz,Galvin,and Gagne?19996.16Applied Operating System Concepts
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)（ CPU分配给最高优先级的进程 [假定最小的整数? 最高的优先级 ]）,
– Preemptive（抢占式）
– Nonpreemptive （非抢占式）
SJF is a priority scheduling where priority is the predicted
next CPU burst time（ SJF是以下一次 CPU脉冲长度为优先数的优先级调度）,
Problem? Starvation – low priority processes may never
execute （问题? 饥饿 – 低优先级的可能永远得不到运行）,
Solution? Aging – as time progresses increase the priority
of the process
（解决方法? 老化 – 视进程等待时间的延长提高其优先数）,
Silberschatz,Galvin,and Gagne?19996.17Applied Operating System Concepts
Round Robin (RR)
Each process gets a small unit of CPU time (time quantum),
usually 10-100 milliseconds,After this time has elapsed,the
process is preempted and added to the end of the ready
queue （每个进程将得到小单位的 CPU时间 [时间片 ]，通常为 10-
100毫 秒。时间片用完后，该进程将被抢占并插入就绪队列末尾
）,
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（假定就绪队列中有 n个进程、时间量为 q,则每个进程每次得到 1/n的、不超过 q单位的成块 CPU时间
，没有任何一个进程的等待时间会超过 (n-1) q单位）,
Performance（特性）
– q large? FIFO
– q small? q must be large with respect to context
switch,otherwise overhead is too high（ q相对于切换上下文的时间而言不许足够长，否则将导致系统开销过大）,
Silberschatz,Galvin,and Gagne?19996.18Applied Operating System Concepts
Example,RR with Time Quantum = 20
Process Burst Time
P1 53
P2 17
P3 68
P4 24
The Gantt chart is,
Typically,higher average turnaround than SJF,but better
response（典型的说,RR的平均周转时间比 SJF长，但响应时间要短一些）,
P1 P2 P3 P4 P1 P3 P4 P1 P3 P3
0 20 37 57 77 97 117 121 134 154 162
Silberschatz,Galvin,and Gagne?19996.19Applied Operating System Concepts
How a Smaller Time Quantum Increases Context Switches
Silberschatz,Galvin,and Gagne?19996.20Applied Operating System Concepts
Turnaround Time Varies With The Time Quantum
Silberschatz,Galvin,and Gagne?19996.21Applied Operating System Concepts
Multilevel Queue
Ready queue is partitioned into separate queues（就绪队列分为）,
foreground (interactive)（前台） [交互式 ]
background (batch) （后台） [批处理 ]
Each queue has its own scheduling algorithm
（每个队列有自己的调度算法）
foreground – RR
background – FCFS
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; e.g.,80% to foreground in
RR
20% to background in FCFS （给定时间片调度，即每个队列得到一定的 CPU时间，进程在给定时间内执行；如,80%的时间执行前台的 RR
调度,20%的时间执行后台的 FCFS调度）
Silberschatz,Galvin,and Gagne?19996.22Applied Operating System Concepts
Multilevel Queue Scheduling
Silberschatz,Galvin,and Gagne?19996.23Applied Operating System Concepts
Multilevel Feedback Queue
A process can move between the various queues; aging can
be implemented this way（进程能在不同的队列间移动；可实现老化）,
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（决定需要服务的进程将进入哪个队列的方法）
Silberschatz,Galvin,and Gagne?19996.24Applied Operating System Concepts
Multilevel Feedback Queues
Silberschatz,Galvin,and Gagne?19996.25Applied Operating System Concepts
Example of Multilevel Feedback Queue
Three queues,
– Q0 – time quantum 8 milliseconds
– Q1 – time quantum 16 milliseconds
– 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（新的作业进入 FCFS的 Q0队列，它得到 CPU时能使用 8毫秒，如果它不能在 8毫秒内完成，将移动到队列 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（作业在 Q1仍将作为 FCFS调度，能使用附加的 16毫秒，如果它还不能完成，
将被抢占，移至队列 Q2 ）,
Silberschatz,Galvin,and Gagne?19996.26Applied Operating System Concepts
Multiple-Processor Scheduling
CPU scheduling more complex when multiple CPUs are
available（多个 CPU可用时,CPU调度将更为复杂）,
Homogeneous processors within a multiprocessor
（多处理器内的同类处理器）,
Load sharing （负载共享）
Symmetric Multiprocessing (SMP) – each processor makes
its own scheduling decisions（对称多处理器 – 每个处理器决定自己的调度方案）,
Asymmetric multiprocessing – only one processor accesses
the system data structures,alleviating the need for data
sharing,（非对称多处理器 – 仅一个处理器能处理系统数据结构，这就减轻了对数据的共享需求）
Silberschatz,Galvin,and Gagne?19996.27Applied Operating System Concepts
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,
（软件实现的实时计算 –当要求临界进程得到比其他进程更高的优先级时）
Silberschatz,Galvin,and Gagne?19996.28Applied Operating System Concepts
Dispatch Latency
Silberschatz,Galvin,and Gagne?19996.29Applied Operating System Concepts
Thread Scheduling
Local Scheduling – How the threads library decides which
thread to put onto an available LWP,
（局部调度 –线程库怎样决定将哪个线程列入有效的轻量级线程
）
Global Scheduling – How the kernel decides which kernel
thread to run next,
（全局调度 –内核怎样决定下一个运行的内核线程）
Silberschatz,Galvin,and Gagne?19996.30Applied Operating System Concepts
Solaris 2 Scheduling
Silberschatz,Galvin,and Gagne?19996.31Applied Operating System Concepts
Java Thread Scheduling
JVM Uses a Preemptive,Priority-Based Scheduling Algorithm,
（ JVM使用的是抢占式的、基于优先级的调度算法）
FIFO Queue is Used if There Are Multiple Threads With the
Same Priority,
（对多个相同优先级的进程将使用 FIFO队列来调度）
Silberschatz,Galvin,and Gagne?19996.32Applied Operating System Concepts
Java Thread Scheduling (cont)
JVM Schedules a Thread to Run When（ JVM调度线程运行，当）,
1,The Currently Running Thread Exits the Runnable State（当前运行进程退出运行状态时）,
2,A Higher Priority Thread Enters the Runnable State（有更高优先级的进程进入可运行状态时）
* Note – the JVM Does Not Specify Whether Threads are Time-
Sliced or Not.（注意 – JVM并未指定线程是否是指定时间片的）
Silberschatz,Galvin,and Gagne?19996.33Applied Operating System Concepts
Time-Slicing
Since the JVM Doesn’t Ensure Time-Slicing,the yield()
Method May Be Used（鉴于 JVM不指定时间片，将使用 yield()
方法）,
while (true) {
// perform CPU-intensive task
.,,
Thread.yield();
}
This Yields Control to Another Thread of Equal Priority（这将把控制权转给另一个相同优先级的线程）,
Silberschatz,Galvin,and Gagne?19996.34Applied Operating System Concepts
Thread Priorities
Thread Priorities:
Priority Comment
Thread.MIN_PRIORITY Minimum Thread Priority
Thread.MAX_PRIORITY Maximum Thread Priority
Thread.NORM_PRIORITY Default Thread Priority
Priorities May Be Set Using setPriority() method:
setPriority(Thread.NORM_PRIORITY + 2);
Silberschatz,Galvin,and Gagne?19996.35Applied Operating System Concepts
Algorithm Evaluation
Deterministic modeling – takes a particular predetermined
workload and defines the performance of each algorithm for
that workload（确定模型法 – 精确预定作业量，并定义该作业量在每个算法上执行的情况）
Queueing models（等待队列模型）
Implementation（执行程序）
Silberschatz,Galvin,and Gagne?19996.36Applied Operating System Concepts
Evaluation of CPU Schedulers by Simulation
Module 6,CPU Scheduling
Basic Concepts （基本概念）
Scheduling Criteria （调度准则）
Scheduling Algorithms （调度算法）
Multiple-Processor Scheduling （多处理器调度）
Real-Time Scheduling （实时调度）
Algorithm Evaluation （算法评估）
Silberschatz,Galvin,and Gagne?19996.2Applied Operating System Concepts
Basic Concepts
Maximum CPU utilization obtained with multiprogramming
（通过多道程序设计得到 CPU的最高利用率）
CPU–I/O Burst Cycle – Process execution consists of a cycle of
CPU execution and I/O wait.
（ CPU-I/O脉冲周期 - 进程的执行包括进程在 CPU上执行和等待 I/O）
CPU burst distribution
（ CPU脉冲的分布）
Silberschatz,Galvin,and Gagne?19996.3Applied Operating System Concepts
Alternating Sequence of CPU And I/O Bursts
Silberschatz,Galvin,and Gagne?19996.4Applied Operating System Concepts
Histogram of CPU-burst Times
Silberschatz,Galvin,and Gagne?19996.5Applied Operating System Concepts
CPU Scheduler
Selects from among the processes in memory that are ready
to execute,and allocates the CPU to one of them.（选择内存中的就绪进程，并分配 CPU给其中之一）
CPU scheduling decisions may take place when a process
（ CPU调度可能发生在当一个进程）,
1,Switches from running to waiting state（从运行转到等待）,
2,Switches from running to ready state（从运行转到就绪）,
3,Switches from waiting to ready（从等待转到就绪）,
4,Terminates（终止运行）,
Scheduling under 1 and 4 is nonpreemptive （ 发生在 1,4两种情况下的调度称为非抢占式调度）,
All other scheduling is preemptive （ 其他情况下发生的调度称为抢占式调度）,
Silberschatz,Galvin,and Gagne?19996.6Applied Operating System Concepts
Dispatcher
Dispatcher module gives control of the CPU to the process
selected by the short-term scheduler; this involves（进程调度模块负责将对 CPU的控制权转交给由 CPU调度程序，包括）,
– switching context（切换上下文）
– switching to user mode（切换到用户态）
– jumping to the proper location in the user program to
restart that program（跳转到用户程序的适当位置并重新运行之）
Dispatch latency – time it takes for the dispatcher to stop
one process and start another running（调度时间 –调度程序终止一个进程的运行并启动另一个进程运行所花的时间）,
Silberschatz,Galvin,and Gagne?19996.7Applied Operating System Concepts
Scheduling Criteria
CPU utilization – keep the CPU as busy as possible
（ CPU利用率 – 使 CPU尽可能的忙碌）
Throughput – the number of processes that complete their
execution per time unit（吞吐量 – 单位时间内运行完的进程数
）
Turnaround time – the interval from submission to
completion （周转时间 – 进程从提交到运行结束的全部时间
）
Waiting time – amount of time a process has been waiting in
the ready queue（等待时间 –进程在就绪队列中等待调度的时间片总和 ）
Response time – amount of time it takes from when a
request was submitted until the first response is produced,
not output (for time-sharing environment)（响应时间 – 从进程提出请求到 首次被响应 [而不是输出结果 ]的时间段 [在分时系统环境下 ] ）
Silberschatz,Galvin,and Gagne?19996.8Applied Operating System Concepts
Optimization Criteria
Max CPU utilization
（最大的 CPU利用率）
Max throughput
（最大的吞吐量）
Min turnaround time
（最短的周转时间）
Min waiting time
（最短的等待时间）
Min response time
（最短的响应时间）
Silberschatz,Galvin,and Gagne?19996.9Applied Operating System Concepts
First-Come,First-Served (FCFS) Scheduling
Example,Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order（假定进程到达顺序如下）,P1,P2,P3
The Gantt Chart for the schedule is（该调度的 Gantt图为）,
Waiting time（等待时间） for P1 = 0; P2 = 24; P3 = 27
Average waiting time（平均等待时间）,(0 + 24 + 27)/3 = 17
P1 P2 P3
24 27 300
Silberschatz,Galvin,and Gagne?19996.10Applied Operating System Concepts
FCFS Scheduling (Cont.)
Suppose that the processes arrive in the order （假定进程到达顺序如下） P2,P3,P1,
The Gantt chart for the schedule is （该调度的 Gantt图为）,
Waiting time （等待时间） for P1 = 6; P2 = 0; P3 = 3
Average waiting time （平均等待时间）,(6 + 0 + 3)/3 = 3
Much better than previous case（比前例好得多）,
Convoy effect short process behind long process
（此种结果产生是由于长进程先于短进程到达）
P1P3P2
63 300
Silberschatz,Galvin,and Gagne?19996.11Applied Operating System Concepts
Shortest-Job-First (SJF) Scheduling
Associate with each process the length of its next CPU
burst,Use these lengths to schedule the process with the
shortest time.（关联到每个进程下次运行的 CPU脉冲长度，调度最短的进程）
Two schemes:
– nonpreemptive – once CPU given to the process it
cannot be preempted until completes its CPU burst（非抢占式调度 – 一旦进程拥有 CPU，它的使用权限只能在该
CPU 脉冲结束后让出 ).
– Preemptive – if a new process arrives with CPU burst
length less than remaining time of current 法 executing
process,preempt,This scheme is know as the
Shortest-Remaining-Time-First (SRTF).（抢占式调度 – 发生在有比当前进程剩余时间片更短的进程到达时，也称为最短剩余时间优先调度）
SJF is optimal – gives minimum average waiting time for a
given set of processes.（ SJF是最优的 – 对一组指定的进程而言，它给出了最短的平均等待时间）
Silberschatz,Galvin,and Gagne?19996.12Applied Operating System Concepts
Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
SJF (non-preemptive)
Average waiting time = (0 + 6 + 3 + 7)/4 - 4
Example of Non-Preemptive SJF
P1 P3 P2
73 160
P4
8 12
Silberschatz,Galvin,and Gagne?19996.13Applied Operating System Concepts
Example of Preemptive SJF
Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
SJF (preemptive)
Average waiting time = (9 + 1 + 0 +2)/4 - 3
P1 P3P2
42 110
P4
5 7
P2 P1
16
Silberschatz,Galvin,and Gagne?19996.14Applied Operating System Concepts
Determining Length of Next CPU Burst
Can only estimate the length（其长度只能估计）,
Can be done by using the length of previous CPU bursts,
using exponential averaging（可以通过先前的 CPU脉冲长度及计算指 数均值进行）,
:D e f i n e 4.
10,3.
b u r s t C P U n e x t t h e f o r v a l u e p r e d i c t e d 2.
b u r s t C P U of l e n g h t a c t u a l 1.
1n
th
n nt
,t nnn 11
Silberschatz,Galvin,and Gagne?19996.15Applied Operating System Concepts
Examples of Exponential Averaging
=0
–?n+1 =?n
– Recent history does not count.
=1
–?n+1 = tn
– Only the actual last CPU burst counts.
If we expand the formula,we get:
n+1 =? tn+(1 -?)? tn -1 + …
+(1 -? )j? tn -1 + …
+(1 -? )n=1 tn?0
Since both? and (1 -?) are less than or equal to 1,each
successive term has less weight than its predecessor.
Silberschatz,Galvin,and Gagne?19996.16Applied Operating System Concepts
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)（ CPU分配给最高优先级的进程 [假定最小的整数? 最高的优先级 ]）,
– Preemptive（抢占式）
– Nonpreemptive （非抢占式）
SJF is a priority scheduling where priority is the predicted
next CPU burst time（ SJF是以下一次 CPU脉冲长度为优先数的优先级调度）,
Problem? Starvation – low priority processes may never
execute （问题? 饥饿 – 低优先级的可能永远得不到运行）,
Solution? Aging – as time progresses increase the priority
of the process
（解决方法? 老化 – 视进程等待时间的延长提高其优先数）,
Silberschatz,Galvin,and Gagne?19996.17Applied Operating System Concepts
Round Robin (RR)
Each process gets a small unit of CPU time (time quantum),
usually 10-100 milliseconds,After this time has elapsed,the
process is preempted and added to the end of the ready
queue （每个进程将得到小单位的 CPU时间 [时间片 ]，通常为 10-
100毫 秒。时间片用完后，该进程将被抢占并插入就绪队列末尾
）,
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（假定就绪队列中有 n个进程、时间量为 q,则每个进程每次得到 1/n的、不超过 q单位的成块 CPU时间
，没有任何一个进程的等待时间会超过 (n-1) q单位）,
Performance（特性）
– q large? FIFO
– q small? q must be large with respect to context
switch,otherwise overhead is too high（ q相对于切换上下文的时间而言不许足够长，否则将导致系统开销过大）,
Silberschatz,Galvin,and Gagne?19996.18Applied Operating System Concepts
Example,RR with Time Quantum = 20
Process Burst Time
P1 53
P2 17
P3 68
P4 24
The Gantt chart is,
Typically,higher average turnaround than SJF,but better
response（典型的说,RR的平均周转时间比 SJF长，但响应时间要短一些）,
P1 P2 P3 P4 P1 P3 P4 P1 P3 P3
0 20 37 57 77 97 117 121 134 154 162
Silberschatz,Galvin,and Gagne?19996.19Applied Operating System Concepts
How a Smaller Time Quantum Increases Context Switches
Silberschatz,Galvin,and Gagne?19996.20Applied Operating System Concepts
Turnaround Time Varies With The Time Quantum
Silberschatz,Galvin,and Gagne?19996.21Applied Operating System Concepts
Multilevel Queue
Ready queue is partitioned into separate queues（就绪队列分为）,
foreground (interactive)（前台） [交互式 ]
background (batch) （后台） [批处理 ]
Each queue has its own scheduling algorithm
（每个队列有自己的调度算法）
foreground – RR
background – FCFS
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; e.g.,80% to foreground in
RR
20% to background in FCFS （给定时间片调度，即每个队列得到一定的 CPU时间，进程在给定时间内执行；如,80%的时间执行前台的 RR
调度,20%的时间执行后台的 FCFS调度）
Silberschatz,Galvin,and Gagne?19996.22Applied Operating System Concepts
Multilevel Queue Scheduling
Silberschatz,Galvin,and Gagne?19996.23Applied Operating System Concepts
Multilevel Feedback Queue
A process can move between the various queues; aging can
be implemented this way（进程能在不同的队列间移动；可实现老化）,
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（决定需要服务的进程将进入哪个队列的方法）
Silberschatz,Galvin,and Gagne?19996.24Applied Operating System Concepts
Multilevel Feedback Queues
Silberschatz,Galvin,and Gagne?19996.25Applied Operating System Concepts
Example of Multilevel Feedback Queue
Three queues,
– Q0 – time quantum 8 milliseconds
– Q1 – time quantum 16 milliseconds
– 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（新的作业进入 FCFS的 Q0队列，它得到 CPU时能使用 8毫秒，如果它不能在 8毫秒内完成，将移动到队列 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（作业在 Q1仍将作为 FCFS调度，能使用附加的 16毫秒，如果它还不能完成，
将被抢占，移至队列 Q2 ）,
Silberschatz,Galvin,and Gagne?19996.26Applied Operating System Concepts
Multiple-Processor Scheduling
CPU scheduling more complex when multiple CPUs are
available（多个 CPU可用时,CPU调度将更为复杂）,
Homogeneous processors within a multiprocessor
（多处理器内的同类处理器）,
Load sharing （负载共享）
Symmetric Multiprocessing (SMP) – each processor makes
its own scheduling decisions（对称多处理器 – 每个处理器决定自己的调度方案）,
Asymmetric multiprocessing – only one processor accesses
the system data structures,alleviating the need for data
sharing,（非对称多处理器 – 仅一个处理器能处理系统数据结构，这就减轻了对数据的共享需求）
Silberschatz,Galvin,and Gagne?19996.27Applied Operating System Concepts
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,
（软件实现的实时计算 –当要求临界进程得到比其他进程更高的优先级时）
Silberschatz,Galvin,and Gagne?19996.28Applied Operating System Concepts
Dispatch Latency
Silberschatz,Galvin,and Gagne?19996.29Applied Operating System Concepts
Thread Scheduling
Local Scheduling – How the threads library decides which
thread to put onto an available LWP,
（局部调度 –线程库怎样决定将哪个线程列入有效的轻量级线程
）
Global Scheduling – How the kernel decides which kernel
thread to run next,
（全局调度 –内核怎样决定下一个运行的内核线程）
Silberschatz,Galvin,and Gagne?19996.30Applied Operating System Concepts
Solaris 2 Scheduling
Silberschatz,Galvin,and Gagne?19996.31Applied Operating System Concepts
Java Thread Scheduling
JVM Uses a Preemptive,Priority-Based Scheduling Algorithm,
（ JVM使用的是抢占式的、基于优先级的调度算法）
FIFO Queue is Used if There Are Multiple Threads With the
Same Priority,
（对多个相同优先级的进程将使用 FIFO队列来调度）
Silberschatz,Galvin,and Gagne?19996.32Applied Operating System Concepts
Java Thread Scheduling (cont)
JVM Schedules a Thread to Run When（ JVM调度线程运行，当）,
1,The Currently Running Thread Exits the Runnable State（当前运行进程退出运行状态时）,
2,A Higher Priority Thread Enters the Runnable State（有更高优先级的进程进入可运行状态时）
* Note – the JVM Does Not Specify Whether Threads are Time-
Sliced or Not.（注意 – JVM并未指定线程是否是指定时间片的）
Silberschatz,Galvin,and Gagne?19996.33Applied Operating System Concepts
Time-Slicing
Since the JVM Doesn’t Ensure Time-Slicing,the yield()
Method May Be Used（鉴于 JVM不指定时间片，将使用 yield()
方法）,
while (true) {
// perform CPU-intensive task
.,,
Thread.yield();
}
This Yields Control to Another Thread of Equal Priority（这将把控制权转给另一个相同优先级的线程）,
Silberschatz,Galvin,and Gagne?19996.34Applied Operating System Concepts
Thread Priorities
Thread Priorities:
Priority Comment
Thread.MIN_PRIORITY Minimum Thread Priority
Thread.MAX_PRIORITY Maximum Thread Priority
Thread.NORM_PRIORITY Default Thread Priority
Priorities May Be Set Using setPriority() method:
setPriority(Thread.NORM_PRIORITY + 2);
Silberschatz,Galvin,and Gagne?19996.35Applied Operating System Concepts
Algorithm Evaluation
Deterministic modeling – takes a particular predetermined
workload and defines the performance of each algorithm for
that workload（确定模型法 – 精确预定作业量，并定义该作业量在每个算法上执行的情况）
Queueing models（等待队列模型）
Implementation（执行程序）
Silberschatz,Galvin,and Gagne?19996.36Applied Operating System Concepts
Evaluation of CPU Schedulers by Simulation
