计算机操作系统原理与windows2003实践教程 教学课件 作者 桑莉君 OS03调度与死锁.ppt

《计算机操作系统原理与windows2003实践教程 教学课件 作者 桑莉君 OS03调度与死锁.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章调度与死锁操作系统原理与Windows2003实践教程1第三章　调度与死锁3.1处理机调度3.2调度算法3.3死锁3.4死锁的预防3.5死锁的避免和银行家算法3.6死锁的检测与解除3.7Windows2003处理器3.8本章小结23.1处理器调度3.1.1调度的层次3.1.2进程调度3.1.3调度队列模型3调度的层次高级调度：也称作业调度中级调度：即交换调度低级调度：也称进程调度4处理机的三级调度5作业调度与进程调度6处理机调度与进程状态转换7进程调度进程调度的功能记录系统中所有进程的状态、优先数和资源需求确定调度算法分配处理器给进程8进程调度的时机：正在执行的进程执行完毕执行进

2、程调用阻塞原语将自己阻塞起来变为阻塞状态执行进程调用P操作，因资源不足而被阻塞；或调用V操作激活了等待资源的进程队列。执行进程提出I/O请求，被阻塞分时系统中时间片用完执行系统调用完毕，由系统程序返回用户进程时，可认为系统进程执行完毕，从而可调度选择一新的用户进程执行。9调度队列模型具有一级调度的调度队列模型10两级调度简化队列图11具有高、低两级调度的调度队列模型12具有三级调度的调度队列模型133.2调度算法3.2.1算法的衡量3.2.2先来先服务调度算法3.2.3短者优先调度算法3.2.4最短剩余时间优先调度算法3.2.5最高响应比优先调度算法3.2.6时间片轮转法3.2.7优先

3、级调度算法3.2.8多级反馈队列调度算法14确定调度策略时应考虑的主要因素：所用算法应保证实现系统的设计目标公平性原则均衡使用资源兼顾响应时间和资源利用率基于相对优先级，但避免无限延期系统开销不应大大15算法的衡量常用的评价准则包括：CPU利用率吞吐量周转时间就绪等待时间响应时间16CPU利用率：CPU利用率＝CPU有效工作时间／CPU总运行时间CPU总运行时间＝CPU有效工作时间＋CPU空闲时间17吞吐量：单位时间内CPU完成作业的数量18周转时间：Ti＝tci－tsi其中，tsi表示作业i的提交时间，即作业i到达系统的时间；tci表示作业i的完成时刻平均周转时间：19就绪等待时间：

4、作业在就绪队列中的等待时间20响应时间：从提交第一个请求到产生第一个响应所用的时间21先来先服务调度算法实现思想：“排队买票”，即按照作业到达系统或是进程进入就绪队列的先后次序作为选择依据就绪队列（后备队列）按照进入的先后次序为序，选择时选取队列的队首进程（作业）22【例3-1】假设一个系统有5个进程P1、P2、P3、P4、P5，已知它们的到达时间和运行时间，用FCFS算法进行调度。232425FCFS的优点：简单、容易实现有利于长进程（作业），不利于短进程（作业）有利于CPU型作业，不利于I/O型作业FCFS的缺点：属于不可抢占策略，表面上对于所有的作业和进程都是公平的，但系统吞吐量

5、不大，效率较低26短者优先调度算法实现思想：从就绪队列中挑选所需的运行时间（估计时间）最短的进程（作业）运行就绪队列（后备队列）按照进程（作业）的运行为序，选择时选取队列的队首进程（作业）即为最短者，新来的进程（作业）依据运行时间的长短插入到队列的合适位置。27【例3-2】设系统中有5个进程中A，B，C，D，E，它们到来的时间依次为0，1，2，3，4，运行时间依次为4，3，5，2，4，试用FCFC算法和短者优先调度算法调度。FCFS：进程的执行顺序依次为A→B→C→D→ESJF：进程的执行顺序依次为A→D→B→E→C。2829SJF（SPF）的优点：简单、容易实现有利于短进程（作业），

6、不利于长进程（作业）有利于保障系统吞吐量SJF（SPF）的缺点：对于长进程（作业）是不公平的30最短剩余时间优先调度算法实现思想：让运行到进程完成时所需运行时间最短的进程优先得到处理，其中包括新进入系统的进程。就绪队列（后备队列）按照进程（作业）的剩余运行时间的长短为序，选择时选取队列的队首进程（作业）即为最短者，新入队的进程（作业）依据剩余运行时间的长短插入到队列的合适位置。31优点：可以用于分时系统，保证及时响应用户要求属于可抢占策略，使短进程一进入系统就能立即得到服务，从而降低作业的平均等待时间缺点：系统开销增加需要保存进程的运行情况记录，以比较其剩余时间大小抢占本身消耗处理器时

7、间32最高响应比优先调度算法实现思想：综合FCFS和短者优先算法的特点就绪队列（后备队列）按照进程（作业）到来的先后次序为序，选择时计算队列全部进程的响应比，选择最高响应比的进程（作业）运行。33【例3-3】假设一个系统有4个进程P1、P2、P3、P4，已知它们的到达时间和运行时间，试用最高响应比优先算法进行调度。343536HRF的优点：短进程（作业）由于计算响应比的分母大而可以得到大的响应比，优先执行，长进程（作业）的响应比会随着等待时间的