Module 6: CPU Scheduling Basic Concepts(基本概念) ° Scheduling criteria(调度准则) ° Scheduling Algorithms(调度算法) Multiple- Processor Scheduling(多处理器调度) ° Real-Time Scheduling(实时调度) ° Algorithm Evaluation(算法评估) Applied Operating System Concepts Silberschatz, Galvin, and Gagne @1999
6.1 Silberschatz, Galvin, and Gagne ©1999 Applied Operating System Concepts Module 6: CPU Scheduling • Basic Concepts （基本概念） • Scheduling Criteria （调度准则） • Scheduling Algorithms （调度算法） • Multiple-Processor Scheduling （多处理器调度） • Real-Time Scheduling （实时调度） • Algorithm Evaluation （算法评估）
Basic Concepts Maximum CPU utilization obtained with multiprogramming (通过多道程序设计得到cPU的最高利用率) CPU-1l0 Burst Cycle- Process execution consists of a cycle of CPU execution and l/o wait (cPU-/O脉冲周期-进程的执行包括进程在cPU上执行和等待Ⅳo) CPU burst distribution (cPU脉冲的分布) Applied Operating System Concepts 62 Silberschatz, Galvin, and Gagne @1999
6.2 Silberschatz, Galvin, and Gagne ©1999 Applied 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脉冲的分布）
Alternating Sequence of CPU And l/o Bursts load store add store d from file CPU burst wait for I/O 1/O burst store increment index CPU burst write to file air for 1/ load store add store read from file CPU burst wait for 1/O v/o burst Applied Operating System Concepts 6.3 Silberschatz, Galvin, and Gagne @1999
6.3 Silberschatz, Galvin, and Gagne ©1999 Applied Operating System Concepts Alternating Sequence of CPU And I/O Bursts
Histogram of CPU-burst Times 160 140 120 8100 000 burst duration(milliseconds) Applied Operating System Concepts 6.4 Silberschatz, Galvin, and Gagne @1999
6.4 Silberschatz, Galvin, and Gagne ©1999 Applied Operating System Concepts Histogram of CPU-burst Times
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 under1and4 is nonpreemptive(发生在1、4两 种情况下的调度称为非抢占式调度) All other scheduling is preemptive(其他情况下发生的调度称 为抢占式调度) Applied Operating System Concepts 6.5 Silberschatz, Galvin, and Gagne @1999
6.5 Silberschatz, Galvin, and Gagne ©1999 Applied 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 （其他情况下发生的调度称 为抢占式调度）
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(调度时间一调度程序 终止一个进程的运行并启动另一个进程运行所花的时间) Applied Operating System Concepts 6 Silberschatz, Galvin, and Gagne @1999
6.6 Silberschatz, Galvin, and Gagne ©1999 Applied 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（调度时间 – 调度程序 终止一个进程的运行并启动另一个进程运行所花的时间）
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)(响应时间一从进 程提出请求到首次被响应[面而不是输出结果]的时间段[在分时系统 环境下]) Applied Operating System Concepts 67 Silberschatz, Galvin, and Gagne @1999
6.7 Silberschatz, Galvin, and Gagne ©1999 Applied 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)（响应时间 – 从进 程提出请求到 首次被响应[而不是输出结果]的时间段[在分时系统 环境下] ）
Optimization Criteria ● Max cpu util| ization (最大的cPU利用率) ° Max throughput (最大的吞吐量) o Min turnaround time (最短的周转时间) ° Min waiting time (最短的等待时间) e Min response time (最短的响应时间) Applied Operating System Concepts 6.8 Silberschatz, Galvin, and Gagne @1999
6.8 Silberschatz, Galvin, and Gagne ©1999 Applied Operating System Concepts Optimization Criteria • Max CPU utilization （最大的CPU利用率） • Max throughput （最大的吞吐量） • Min turnaround time （最短的周转时间） • Min waiting time （最短的等待时间） • Min response time （最短的响应时间）
First-Come, First-served (FCFS)Scheduling ° EXample Process Burst time 24 3 3 Suppose that the processes arrive in the order(假定进程到达顺一 序如下):P1,P2,P3 The Gantt Chart for the schedule is(该调度的 Gantt图为): 24 27 30 ° Waiting time(等待时间)forP1=0;P2=24;P3=27 · Average waiting time(平均等待时间):(0+24+27)/3=17 Applied Operating System Concepts 6.9 Silberschatz, Galvin, and Gagne @1999
6.9 Silberschatz, Galvin, and Gagne ©1999 Applied 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 0 24 27 30
FCFS Scheduling(Cont Suppose that the processes arrive in the order(假定进程到达顺序 如下)P2,P3,P1 The gantt chart for the schedule is(该调度的Gant图为) 0 3 6 30 ° Waiting time(等待时间)forP1=6;P2=0.P3= ° Average waiting time(平均等待时间):(6+0+3)/3=3 Much better than previous case(比前例好得多) Convoy effect short process behind long process (此种结果产生是由于长进程先于短进程到达) Applied Operating System Concepts 6.10 Silberschatz, Galvin, and Gagne @1999
6.10 Silberschatz, Galvin, and Gagne ©1999 Applied 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 （此种结果产生是由于长进程先于短进程到达） P2 P3 P1 0 3 6 30