《第三章处理机调度与死锁2》由会员分享，可在线阅读，更多相关《第三章处理机调度与死锁2（64页珍藏版）》请在金锄头文库上搜索。
1、第三章 处理机调度与死锁,内容提要,处理机调度及调度算法 产生死锁的原因和必要条件 预防死锁的方法，死锁的检测与解除 银行家算法,第三章 处理机调度与死锁,处理机调度：按一定方法动态地把处理机分配给就绪队列中的一个进程,WHAT：按什么原则分配CPU进程调度算法 WHEN：何时分配CPU 进程调度的时机HOW：如何分配CPU CPU调度过程（进程的上下文切换）,第三章 处理机调度与死锁,3.1 处理机调度的基本概念1)调度类型高级调度：即作业调度，选择后备作业进入内存，为其建立进程,分配资源并排在就绪队列。中级调度：即对换调度，将暂不运行的进程调到外存等待，从而提高内存利用率和系统吞吐量低级调
2、度：即进程调度，决定哪个进程可以占用CPU，进入运行状态。,输入程序,就绪,阻塞,就绪,运行,完成,阻塞,后备,外存,中级调度,对换,低级调度,作业调度,2)进程调度方式调度方式是指但某一个进程正在处理机上执行时如果有 个更重要更紧迫的进程需要处理此时应该如何分配处理机。 非抢占方式进程一旦被调度执行，除非进程完成或发生某事件被阻塞，否则不允许其他进程抢夺其执行权。 抢占方式允许按某种策略（原则）剥夺正在执行的进程的执行权-优先权原则 -短作业(进程)优先原则 -时间片原则,3)调度类型与O.S类型的关系 多道批处理系统：存在作业调度、进程调度 分时/实时系统：只有进程调度共同点：均存在进程调
3、度（分配CPU） 4) 调度队列模型(三种),仅有进程调度的调度队列模型具有高级和低级的调度队列模型具有三级调度的调度队列模型,调度队列模型,仅有进程调度的调度队列模型,进程调度,进程完成,等待事件,交互用户,时间片完,进程调度,进程完成,时间片完,与上一模型的主要区别：就绪队列的形式；设置多个阻塞队列,具有高级和低级的调度队列模型,同时具有三级调度的调度队列模型,进程调度,中级调度,等待事件,进程完成,时间片完,作业调度,交互型作业,批量作业,挂起,事件出现,事件出现,5) 调度性能评价作业调度算法的评价因素CPU利用率：越高越好吞吐量：单位时间内CPU完成作业的数量周转时间：通常与带权周转
4、时间一起作为评价批处理系统的性能指标，定义如下：,其中：作业Ji的提交时间为tsi，执行时间为tri，完成时间为toi,n个作业的平均周转时间T和平均周转系数W分别为,对于每个用户来说，总是希望作业提交后立即执行，这样周转时间等于执行时间；而对于一个计算机系统来说，不可能满足每个用户的这种要求，只能使系统的平均周转时间最短。,对于分时系统常把响应时间的长短作为评价标准；对于实时系统常把截止时间作为评价标准。,3.2 调度算法,先来先服务调度算法短作业（进程）优先调度算法高优先权者优先调度算法时间片轮转调度算法多队列反馈轮转调度算法实时调度算法,相关术语,调度算法：根据系统的资源分配策略所规定的
5、资源分配算法 几个术语到达时间、服务时间、开始时间完成时间、等待时间周转时间：完成时间-到达时间带权周转时间：周转时间/服务时间,1）先来先服务调度算法 策略：先进入后备队列（就绪队列）的作业（进程）先被调度 优点：算法简单易实现 缺点：不分轻重缓急，对短作业（进程）不利 2）短作业（进程）优先调度算法 策略：启动要求运行时间最短的作业。 优点：有效降低作业平均等待时间提高系统的吞吐量 缺点：长作业（进程）可能长期得不到服务,0,4,4,4,7,6,例：先来先服务算法（FCFS）,7,12,10,12,14,11,14,18,14,0,4,4,1,例：短作业/短进程优先（SJF/SPF）,4,
6、6,3,3/2,6,9,8,8/3,9,13,9,9/4,13,18,16,16/5,40/5,2.1,3）高优先权者优先调度算法优先权：反映作业（进程）重要性和调度级别的权值，又称优先数。通常分为： 静态优先数：进程创建时确定运行过程中保持不变。一般根据进程的类型，资源需求情况，估计的运行时间等因素确定。一般用一整数进行表示（如0至32） 动态优先数：创建进程时确定一个优先级，进程运行过程中可以根据情况的变化调整优先级，调整一般是根据进程占用的CPU的时间长短、进程等待CPU时间长短来进行（如高响应比优先）。,调度类型 非抢占式优先权调度：处理机一旦分配给就绪队列中优先权最高的进程后，该进程
7、就一直运行下去直到自动放弃或完成，这时才可把处理机分配给另一优先级最高的进程。 抢占式优先权调度：进程在运行时一旦出现了另一个优先级更高的进程，调度程序就停止该进程而把处理机分配给新出现的高优先权进程。,例：静态优先权，非抢占式（1为高优先权）,0,4,4,1,4,8,4,1,8,11,10,10/3,11,16,14,14/5,16,18,15,15/2,9.4,2.93,考虑一下抢占式，情况如何？,高响应比优先调度算法（HRP）：优先调度响应比高的作业,对短作业有利,是先来先服务,对长作业有利,缺点：要进行响应比计算，增加了系统开销,小结： 等待时间相同的作业，则要求服务的时间愈短，其优先
8、权愈高 要求服务的时间相同的作业，则等待时间愈长，其优先权愈高 长作业，优先权随等待时间的增加而提高，其等待时间足够长时，其优先权便可升到很高， 从而也可获得处理机,4）时间片轮转调度算法（适合于分时系统）策略系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便停止该进程的执行，并将其放就绪队列尾；然后，再把处理机分配给就绪队列中新的队首优、缺点：简单易实现，但不分轻重缓急关键：时间片大小的选择,例：基于时间片的轮转调度算法,A,B,C,D,E,A,B,C,D,E,A,B,C,
9、E,A,C,E,C,0,1,2,3,4,9,12,15,17,18,15,15/4,11,11/3,16,16/5,6,6/2,13,13/4,12.2,2.12,若到达时间为0、1、2、3、4，又如何？,5）多级队列反馈轮转调度算法策略：将时间片与优先级调度相结合。-设置多个就绪队列，分别赋予不同的优先级。优先级越低则时间片越长-新进程进入内存后，先投入第一队列的末尾，按FCFS算法调度；若按第一队列一个时间片未能执行完，则降低投入到第二队列的末尾，同样按FCFS算法调度；如此下去，降低到最后的队列，则按“时间片轮转”算法调度直到完成-仅当较高优先级的队列为空，才调度较低优先级的队列中的进程
10、执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾,就绪队列1,就绪队列2,就绪队列3,就绪队列n,按FIFO原则排队等待调度,尚未完成转入第二队列的末尾，按FIFO原则等待调度,采取按时间片轮转的方式运行,因等待而放弃CPU后，进入阻塞队列，一旦等待的事件发生，则回到原来的就绪队列,调度算法性能分析,设有四个作业，其提交时刻、执行时间如下表所示，分别采用 FCFS、SJF、FPF调度方法，计算平均周转时间T和平均周转系 数W。,先来先服务调度算法：顺序为1 2 3 4，平均周转时间和平均周转系数的计算结果如下表所示：,8.00,10.00,2
11、.00,1.00,10.00,10.50,2.00,4.00,10.50,10.60,1.60,16.00,10.60,10.80,1.30,6.50,6.90,27.50,平均周转时间T1.725小时，平均周转系数W6.875, 最短作业优先调度算法： 由于在8.00开始执行作业，当时仅有1，而作业2，3，4尚未到达，故作业1是最短作业。作业1执行完成后是10.00，此时作业2，3，4均已经到达，故选最短作业3，然后是4，2。所以顺序为1,3,4,2。平均周转时间和平均周转系数的计算结果如下表所示：,8.00,10.00,2.00,1.00,10.00,10.10,1.10,11.00,10
12、.10,10.30,0.80,4.00,10.30,10.80,2.30,4.60,6.20,20.60,平均周转时间T1.55小时，平均周转系数W5.15,响应比高者优先算法： 在作业1执行完成，计算作业2，3，4的响应比分别为：4， 11，3.5，因此作业1执行完成后选中作业3完成。执行顺序 为1，3，2，4。按此算法求得的平均周转时间和平均周转系 数如下表所示：,8.00,10.00,2.00,1.00,10.00,10.10,1.10,11.00,10.10,10.60,2.10,4.20,10.60,10.80,1.30,6.50,6.50,22.70,平均周转时间T1.625小时，
13、平均周转系数W5.675,总结：就其平均周转时间和平均周转系数来说，最短作业优先算法最小，先来先服务算法最大，响应比高者优先算法居中。,6）两种常见的实时调度算法 最早截止时间优先算法(EDF) 选择就绪队列中开始截止时间最早的实时任务对应的进程先执行（一般非抢占方式） 最低松弛度优先算法(LLF) 松弛度=规定完成时间-所需执行时间-当前时间选择松弛度最小的实时任务对应的就绪进程先执行，一般采用抢占方式，当某进程松弛度为零时，必须立即抢占执行。,EDF例：,t=0 只有P1进程，P1执行4个单位时间 t=4 P2、P3均到达，P3截止时间早于P2截止时间 P3执行两个单位时间 t=6 P2和
14、P4就绪，P4截止时间早于P2，P4执行 t=9 只剩P2，P2执行,LLF例：两个周期性实时任务A和B，A：每20ms执行一次，每次执行时间为10msB：每50ms执行一次，每次执行时间为25ms,3.3 死锁死锁：多个进程竞争系统资源，造成一种僵局，使得这些进程在无外力的作用下，均无法继续向前推进。讨论问题 死锁的产生原因 产生死锁的必要条件 死锁的预防 死锁的避免 死锁的检测和解除,1）产生死锁的原因 死锁主要是由两个或多个进程对资源需求的冲突引起的,进程A,请求资源R2,进程B,请求资源R1,请求资源R1,请求资源R2,R1,R2,（阻塞）,（阻塞）,死锁产生的原因：资源竞争进程推进顺
15、序不当 资源竞争引起死锁情况 独占资源分为可剥夺式和不可剥夺式，死锁与不可剥夺式有关。,进程的推进顺序不当导致死锁,进程的推进顺序非法将导致死锁（续）,进程推进顺序合法,进程的推进顺序非法将导致死锁（续）,进程推进顺序合法,进程的推进顺序非法将导致死锁（续）,进程推进顺序合法,进程的推进顺序非法将导致死锁（续）,进程推进顺序不合法,D:不安全区,2）死锁产生的四个必要条件,互斥条件请求和保持条件不剥夺条件环路等待条件 上述条件是产生死锁的必有条件，并非充分条件。如 果破坏上述4个条件之一，就可以预防死锁的产生。,3.4 死锁的处理,用于处理死锁的主要方法： 预防死锁：通过设置限制条件破坏死锁的
16、四个必要条件中的一个或几个来防止死锁发生 避免死锁：资源分配过程中用某种方法防止系统进入不安全状态来防止死锁发生 检测死锁：通过系统的检测机构来检测死锁发生 解除死锁：通过撤销或挂起一些进程恢复系统正常运行,1）预防死锁,策略：从破坏死锁的必要条件入手,破坏（摒弃）四个必要条件之一摒弃“互斥条件”由设备的固有属性决定，只能通过某种技术加以利用，但一般来说这种方法不是很有效。摒弃“请求和保持条件” 进程创建时，一次性将全部所需资源均分配给进程，其在运行过程中不会产生新的请求。,摒弃“不剥夺条件” 进程因请求新资源而得不到满足，造成阻塞时，暂时释放已占有的所有资源（剥夺）。摒弃“环路等待条件” 按序分配资源。系统依据一定的策略给资源由低到高编号，进程必须按从小到大顺序申请资源，并规定进程占有的资源号小于申请的资源号才能得到申请资源。使之资源分配图不会形成环路。,
