第三章 处理机调度与死锁.ppt

《第三章 处理机调度与死锁.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、操作系统原理用户用户用户作业1作业2作业3作业4外存后备队列作业调度程序内存CPU进程调度第三章处理机调度与死锁3.1处理机调度的层次和调度算法的目标3.1.1处理机调度的层次1高级调度长程调度、作业调度，调度对象为作业。低级调度进程调度、短程调度，调度对象为进程。3中级调度内存调度，为提高内存利用率和系统吞吐量。第三章处理机调度与死锁CPU就绪队列阻塞队列后备作业队列高级调度低级调度时间片用完进程完成等待事件事件解除第三章处理机调度与死锁3.1处理机调度的层次和调度算法的目标3.1.2处理机算法的目

2、标1处理机算法的共同目标（1）资源利用率（2）公平性（3）平衡性（4）策略强制执行性第三章处理机调度与死锁3.1处理机调度的层次和调度算法的目标3.1.2处理机算法的目标2批处理系统的目标（1）平均周转时间短作业提交开始到作业完成为止的时间间隔系统：作业的平均周转时间尽可能少用户：自己作业周转时间尽量少指标：平均周转时间指标：带权周转时间第三章处理机调度与死锁①作业平均周转时间（T）②带权平均周转时间（W）T＝（）×å=niTi1n为作业数目，第i个作业的周转时间Ti＝Ei–SiEi：作业完成时间Si

3、：作业提交时间W＝（）×ri为某作业i的实际执行时间3.1处理机调度的层次和调度算法的目标3.1.2处理机算法的目标第三章处理机调度与死锁3.1处理机调度的层次和调度算法的目标3.1.2处理机算法的目标2批处理系统的目标（2）系统吞吐量（3）处理机利用率高3分时系统的目标（1）响应时间快（2）均衡性4实时系统的目标（1）截止时间的保证（2）可预测性第三章处理机调度与死锁3.2作业与作业调度3.2.1批处理系统中的作业1作业和作业步（1）作业（Job）：程序+数据+作业说明符（2）作业步：作业执行过程中

4、的加工步骤2作业控制块（JCB）(1)作业存在的标识(2)保存系统对作业进行管理和调度的所有信息第三章处理机调度与死锁3.2作业与作业调度3.2.1批处理系统中的作业3作业运行的三个阶段和三种状态后备状态→运行状态→完成状态（1）三个阶段收容阶段→运行阶段→完成阶段（2）三种状态第三章处理机调度与死锁3.2作业与作业调度3.2.2作业调度的主要任务1决定接纳多少个作业多道程序度2接纳哪些作业调度算法第三章处理机调度与死锁3.2作业与作业调度3.2.3先来先服务和短作业优先算法1先来先服务算法（1）FC

5、FS：FirstComeFirstServe（2）适用于作业、进程调度（3）选择最先进入的作业/进程（4）例子：第三章处理机调度与死锁作业到达t服务t开始t结束tTWA01B1100C21D31000111011011021022021110011001001991.99平均周转时间：t=100带权平均周转时间w=25.9975优点：实现简单（优待大作业）缺点：对短作业不利3.2作业与作业调度3.2.3先来先服务和短作业优先算法第三章处理机调度与死锁2短作业优先算法（1）SJ（P）F：Shortest

6、Job（Process）First（2）适用于作业、进程调度（3）选择短的作业/进程（4）例子：3.2作业与作业调度3.2.3先来先服务和短作业优先算法第三章处理机调度与死锁进程ABCDE平均到达t01234服务t43524先来先服务算法开始t完成tTW短作业优先算法开始t完成tTW作业情况算法0447712121414184162102115.5143.592.804691318469134182.67163.231.592.2582.143.2作业与作业调度3.2.3先来先服务和短作业优先算法第三

7、章处理机调度与死锁1优先级调度算法（PSA）3.2作业与作业调度3.2.4优先级调度算法和高响应比优先调度算法先来先服务算法→等待时间为优先级短作业优先算法→作业长短为优先级优先级调度算法→作业的紧迫程度第三章处理机调度与死锁2高响应比优先权调度算法（HRRN）（1）HRRN是介于FCFS和SJP（F）之间的一种折中算法（2）优先权3.2作业与作业调度3.2.4优先级调度算法和高响应比优先调度算法优先权=（等待时间+要求服务时间）/要求服务时间动态优先权：随等待时间延长而增加响应比R=（等待时间+要求

8、服务时间）/要求服务时间=响应时间/要求服务时间第三章处理机调度与死锁2高响应比优先权调度算法（HRRN）（3）优点＊等待时间相同，则处理时间短，优先级R高。＊作业处理时间相同，则等待时间决定优先级R。＊对于长作业，等待足够时间，R增加，可获得处理机。——SJF——FCFS（4）缺点＊增加系统开销3.2作业与作业调度3.2.4优先级调度算法和高响应比优先调度算法第三章处理机调度与死锁2高响应比优先权调度算法（HRRN）（5）例子到达t服务t开始t完成tT