chp03处理机调度单击此处编辑母版标题.pptxVIP

第3章 处理机调度与死锁;;3.1 处理机调度的层次和调度算法的目标;3.1 处理机调度的层次和调度算法的目标;;利用多道程序最大化CPU使用率。 CPU – I/O脉冲周期 － 进程执行由CPU执行和I/O等待周期组成。 CPU burst I/O wait CPU burst I/O wait ….;CPU脉冲时间直方图;CPU调度程序;CPU调度程序;分派程序 ;CPU utilization (使用率)：使CPU尽可能忙 CPU throughput (吞吐量)：单位时间完成进程的数量 Process turnaround time (周转时间)：从进程提交到进程完成的时间间隔称为周转时间 Process waiting time (等待时间)：在就绪队列中??待所花时间之和 Process response time (响应时间)：从提交请求到产生第一响应的时间;优化准则： 最大化CPU使用率 最大化吞吐量 最小化周转时间 最小化等待时间 最小化响应时间;First come first served (FCFS) （先来先服务调度） Shortest job first (SJF) （短作业优先调度） Priority scheduling （优先级调度） Round robin (RR) （时间片轮转调度） Multilevel queue algorithm （多级队列调度） Multilevel feedback queue algorithm （多级反馈队列调度）;Scheduling algorithms: FCFS（先来先服务）;假设进程到达顺序为： P2 , P3 , P1 . 对应的调度甘特图为：;Convoy effect (护航效果) ： CPU脉冲时间短的进程在CPU脉冲时间长的进程之后执行。 FCFS 调度算法是非抢占的。 FCFS调度算法尤其不适合分时系统。 在分时系统中一个进程长时间占用处理机是不允许的。 由于所有其他进程都等待一个大进程释放CPU，就会产生护航效果。与可能允许较短进程先行相比，这种效果会导致CPU和设备的使用率变得更低;将每个进程与其下一个CPU脉冲相关联。当CPU为可用时，它会赋给具有最短后续CPU脉冲的进程。如果两个进程具有同样长度的CPU脉冲，那么可以使用FCFS调度来处理。 两种方式 非抢占式：一旦进程获得CPU就一直占据CPU，直到其CPU脉冲完成为止 抢占式：如果一个新来的进程其CPU脉冲时间小于当前进程的CPU脉冲时间，则抢占之。这种调度方式称为最短剩余时间作业优先（Shortest Remaining Time First：SRTF） SJF是最佳的：对于给定的一组进程，SJF算法的平均等待时间最小。;Scheduling algorithms: SJF（短作业优先）; Process Arrival time Burst Time P1 0 8 P2 1 4 P3 2 9 P4 3 5 SJF （抢占式）调度甘特图： ;确定下一CPU脉冲的长度;下一个CPU区间长度的预测;SJF可证明为最佳调度算法 SJF调度算法支持抢占和非抢占调度算法 适合于长程调度，不太适合短程调度 难以估计CPU脉冲时间;每个进程被赋予一个优先级数字（优先权） CPU分配给优先权高的进程（优先级数字越小，则优先权越大） 抢占式 非抢占式 SJF是一种特定的优先权调度方法，其优先权为下一个CPU脉冲的倒数;Scheduling algorithms: Priority scheduling（优先级调度）;该算法存在的问题：饥饿 低优先权的进程可能永远无法执行 解决办法：老化 随着时间的推进，进程的优先权逐渐提高 ;Scheduling algorithms: RR （时间片轮转）;Scheduling algorithms: RR (q=20ms);时间片与上下文切换开销;Scheduling algorithms: RR （时间片轮转）;周转时间随时间片大小而改变;Scheduling algorithms: Multilevel queue（多级队列）;Scheduling algorithms: Multilevel queue（多级队列）;多级队列调度示意图;Multilevel feedback queue（多级反馈队列）;三个队列 Q0：时间片为8毫秒 Q1：时间片为16毫秒 Q2：FCFS;调度 进入就绪队列的进程被放在队列0内。队列0的每个进程都有8ms的时间片。如果一个进程不能在这一时