《操作系统概念ch5》由会员分享，可在线阅读，更多相关《操作系统概念ch5（100页珍藏版）》请在金锄头文库上搜索。
1、Chapter 5: CPU SchedulingChapter 5: CPU Scheduling5.2Operating System Concepts 7th EditionChapter 5: CPU SchedulingChapter 5: CPU SchedulingnBasic ConceptsnScheduling Criteria nScheduling AlgorithmsnMultiple-Processor SchedulingnReal-Time SchedulingnThread SchedulingnOperating Systems ExamplesnJava
2、Thread SchedulingnAlgorithm Evaluation5.3Operating System Concepts 7th EditionBasic ConceptsBasic ConceptsnMaximum CPU utilization obtained with multiprogramming通过多道 程序最大化CPU使用率nCPUI/O Burst Cycle Process execution consists of a cycle of CPU execution and I/O wait CPU-I/O区间周期：进程执行由CPU执 行和I/O等待周期组成nC
3、PU burst distribution CPU区间分布5.4Operating System Concepts 7th EditionAlternating Sequence of CPU And I/O BurstsAlternating Sequence of CPU And I/O Bursts CPUCPU和和I/OI/O区间的交替序列区间的交替序列5.5Operating System Concepts 7th EditionHistogram of CPU-burst TimesHistogram of CPU-burst Times CPUCPU区间时间图区间时间图5.6Op
4、erating System Concepts 7th EditionCPU SchedulerCPU SchedulernSelects from among the processes in memory that are ready to execute, and allocates the CPU to one of them从就绪队列中选择一个进程执行，把 CPU分给它 nCPU scheduling decisions may take place when a process:发生位置1. Switches from running to waiting state一个进程从运行
5、态切换到等待态2. Switches from running to ready state一个进程从运行态到就绪态3. Switches from waiting to ready 一个进程从等待态到就绪态4. Terminates 一个进程终止nScheduling under 1 and 4 is nonpreemptive 1和4是非抢占调度nAll other scheduling is preemptive 其他的是抢占调度5.7Operating System Concepts 7th EditionDispatcherDispatcher分派程序分派程序nDispatcher
6、module gives control of the CPU to the process selected by the short-term scheduler; this involves:将CPU控制交给 由短期调度程序选择的进程，包括：lswitching context 上下文切换lswitching to user mode 切换到用户模式ljumping to the proper location in the user program to restart that program 跳转到用户程序的合适位置，以重新执行程序nDispatch latency time it
7、 takes for the dispatcher to stop one process and start another running 分派延时：分派进程停止一个而 启动另一个所花的时间5.8Operating System Concepts 7th EditionScheduling CriteriaScheduling Criteria调度准则调度准则nCPU utilization keep the CPU as busy as possible CPU利用率nThroughput # of processes that complete their execution per
8、time unit 吞吐量：一个时间单元内完成进程的数量nTurnaround time amount of time to execute a particular process 周 转时间：从进程提交到进程完成的时间nWaiting time amount of time a process has been waiting in the ready queue 等待时间：进程在就绪队列中等待所花时间之和nResponse time amount of time it takes from when a request was submitted until the first resp
9、onse is produced, not output (for time- sharing environment)对于分时系统，从提交请求到第一次响应的时间5.9Operating System Concepts 7th Editionl带权周转时间: 周转时间包含了两个部分，即等 待时间和执行时间。为了更进一步反映调度性能 ，使用带权周转时间的概念。带权周转时间是周 转时间与执行时间的比：Wi=Ti/Tri对于几个作业来说，其平均带权周转时间为：5.10Operating System Concepts 7th EditionOptimization CriteriaOptimizat
10、ion CriterianMax CPU utilization 高CPU利用率nMax throughput 高吞吐量nMin turnaround time 低周转时间nMin waiting time 低等待时间nMin response time 低响应时间5.11Operating System Concepts 7th EditionFirst-Come, First-Served (FCFS) First-Come, First-Served (FCFS) SchedulingSchedulingn进程到达就绪队列时按先后顺序排队。选择 进程去执行时，始终选队首进程。进程获得CP
11、U 后，直至执行完或发生某等待事件，才释放CPU 。5.12Operating System Concepts 7th Editionn实现方法l用一个FIFO队列来维护就绪进程l调度算法每次从FIFO队列取排在队头的进程转入运行态l新进入就绪态的进程放入队尾5.13Operating System Concepts 7th Editionn算法评价: l在没有特殊理由要优先调度某进程时，从处理的 角度来看，FCFS方式是一种最合适的方法，无论 是追加还是取出一个队列元素在操作上都是最简 单的。l该算法在一般意义下是公平的。即每个进程都按 照它们在队列中等待时间长短来决定它们是否优 先享受服务
12、。5.14Operating System Concepts 7th EditionFirst-Come, First-Served (FCFS) SchedulingFirst-Come, First-Served (FCFS) SchedulingProcessBurst Time P124P2 3P33 nSuppose that the processes arrive in the order: P1 , P2 , P3 The Gantt Chart for the schedule is:nWaiting time for P1 = 0; P2 = 24; P3 = 27nAve
13、rage waiting time: (0 + 24 + 27)/3 = 17P1P2P324273005.15Operating System Concepts 7th EditionFCFS Scheduling (Cont.)FCFS Scheduling (Cont.)Suppose that the processes arrive in the orderP2 , P3 , P1 nThe Gantt chart for the schedule is:nWaiting time for P1 = 6; P2 = 0; P3 = 3nAverage waiting time: (6
14、 + 0 + 3)/3 = 3nMuch better than previous casen（此种结果产生是由于长进程晚于短进程到达）nConvoy effect short process behind long process护航效果P1P3P2633005.16Operating System Concepts 7th EditionFCFSFCFSn平均周转时间n27n135.17Operating System Concepts 7th EditionFCFSFCFS在实际操作系统中，尽管很少单独使用FCFS算法，但和其 他一些算法配合起来，FCFS算法还是使用得相当多的。缺点:
15、1.周转时间与响应时间无法保证 2.对短作业不利对于那些执行时间较短的作业或进程来说，如果它 们在某些执行时间很长的作业或进程之后到达，则它 们将等待很长时间。5.18Operating System Concepts 7th EditionShortest-Job-First (SJF) SchedulingShortest-Job-First (SJF) Scheduling 最短作业优先最短作业优先nAssociate with each process the length of its next CPU burst. Use these lengths to schedule the
16、 process with the shortest time。将每 个进程与下一个CPU区间段关联，分配CPU给具有最短区间段的进 程nTwo schemes: lnonpreemptive once CPU given to the process it cannot be preempted until completes its CPU burst。非抢占lpreemptive 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)抢占：剩余时间最短者 优先nSJF is optimal gives minim
