Chap3进程调度与死锁

《Chap3进程调度与死锁》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、操作系统第三章进程调度与死锁计算机学院软件工程系舒新峰shuxf@xupt.edu.cn第三章进程调度与死锁在多道程序环境下，系统中有多个进程同时运行。多个的进程竞争处理机，就要求系统提供进程调度功能，将处理机动态地分配给系统中的各个进程，使之能够协调一致的运行。Part1：进程调度3.1进程调度概述3.2进程调度算法3.3CPU调度过程3·1进程调度概述要解决的问题WHAT：按什么原则分配CPU—进程调度算法WHEN：何时分配CPU—进程调度的时机HOW：如何分配CPU—CPU调度过程（进程的上下文切换）3·1进程调度概述1、进程调度的功能记录系统中所有进程的状态、优先数和资源的需

2、求情况。确定调度算法。决定将CPU分配给哪个进程及多长时间。分配处理机给进程。进行CPU现场的保护和移交，并实现CPU使用权的移交。处理机是计算机最重要的资源,如何提高处理机的利用率及改善系统性能,在很大程度上取决于进程调度（亦称处理机调度）性能的好坏,进程调度成为操作系统设计中心工作。3·1进程调度2、进程调度方式（1）非抢占方式(Nonpreemptivemode)：在非抢占方式下，调度程序一旦把CPU分配给某一进程后便让它一直运行下去，直到进程完成或发生某事件而不能运行时，才将CPU分给其它进程。这种调度方式通常用在批处理系统中。它的主要优点是简单、系统开销小。（2）抢占方式(Pr

3、eemptivemode)：当一个进程正在执行时，系统可以基于某种策略剥夺CPU给其它进程。剥夺的原则有：优先权原则、短进程优先原则和时间片原则。这种调度方式多用在分时系统和实时系统中，以便及时响应各进程的请求。3·1进程调度3、引进进程调度的时机进程调度的时机是与进程调度的方式有关的。通常当发现以下情况时，当前运行进程的CPU被收回，需要重新进行进程调度：正在执行的进程正确完成,或由于某种错误而终止运行(陷阱或中断)；执行中的进程提出I/O请求,等待I/O完成时;在分时系统中，分给进程的时间片用完时；按照优先级调度时,有更高优先级进程变为就绪时(抢占方式)；在进程通讯中,执行中的

4、进程执行了某种原语操作,如wait操作、阻塞原语和唤醒原语时,都可能引起进程调度。3·1进程调度4、进程调度算法的评价准则我们可从不同的角度来判断处理机调度算法的性能。实际的处理机调度算法选择是一个综合的判断结果。1）面向系统的调度性能准则吞吐量：单位时间内所完成的作业数，跟作业本身特性和调度算法都有关系——批处理系统。注意：平均周转时间不是吞吐量的倒数，因为并发执行的作业在时间上可以重叠。如在2小时内完成4个作业，每个周转时间是1小时，吞吐量是2个作业/小时。处理机利用率：——大中型主机各种设备的均衡利用：如CPU繁忙的作业和I/O繁忙（指次数多，每次时间短）的作业搭配——大中型主机

5、。3·1进程调度2）面向用户的调度性能准则周转时间：作业从提交到完成所经历的时间——批处理系统。（公式中T为实际运行时间）。si1n1nT平均周转T＝T平均带权周转W=ininTi=1i=1si响应时间：用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间—分时系统截止时间：开始截止时间和完成截止时间——实时系统，与周转时间有些相似。公平性：不因作业或进程本身的特性而使上述指标过分恶化。如长作业等待很长时间。优先级：可以使关键任务达到更好的指标。3·1进程调度3）调度算法本身的调度性能准则易于实现执行开销比要设计一个理想的调度算法是一件十分困难的事,在实际系统中

6、,调度算法往往折衷考虑。大多数操作系统都采用比较简单的调度算法。3·2进程调度算法1、先来先服务FCFS(先进先出调度算法，FIFO)【算法思想】：最简单的算法按照进程进入就绪队列的先后次序，分派CPU；当前进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。在进程唤醒后（如I/O完成），并不立即恢复执行，通常等到当前进程出让CPU。。【特点】：比较有利于长作业，而不利于短作业。有利于CPU繁忙的作业，而不利于I/O繁忙的作业。3·2进程调度算法2、短作业（进程）优先调度算法(SJF,SPF)【算法思想】：选择就绪队列中估计运行时间最短的进程投入运行。通常后来的短作业不抢

7、占正在执行的作业。【优点】：比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；提高系统的吞吐量；【缺点】：对长作业非常不利，可能长时间得不到执行；未能依据作业的紧迫程度来划分执行的优先级难以准确估计作业（进程）的执行时间，从而影响调度性能。3·2进程调度算法3、优先权调度算法(HPF—HighestPriorityFirst)【算法思想】：优先选择就绪队列中优先级最高的进程投入运行。