太原理工大学操作系统-第三章处理机调度与死锁概要.ppt

哲学家问题中的应用 哲学家问题分析 四、进程调度算法 采用最高优先级优先调度算法时，系统对每个进程确定一个优先数，进程的优先数用于表示进程的重要性及运行的优先性。调度时，系统把处理机分配给优先级最高的就绪进程。如果就绪进程具有相同的优先数，则再按先来先服务的次序分配处理机。 先来先服务调度算法是按照进程进入就绪队列的先后次序来选择进程分配处理机。 （一）最高优先级优先调度算法 系统确定优先数的方法： 1.静态优先数法：静态优先数是在创建进程时系统为其确定的，并且在进程的生命期内不再改变。 确定静态优先数的原则： 1）按进程类型。系统进程的优先级高于用户进程的优先级。 2）按进程使用的资源。进程所使用的资源越多，进程的优先级越低；反之，则进程的优先级越高。 3）按进程的估计运行时间。进程的估计运行时间越长，进程的优先级越低；反之，则进程的优先级越高。 4）由用户指定。有些系统可以按收费标准不同，设置不同的优先级别，可以由用户指定。 静态优先级法实现起来比较简单，但不能反映系统以及进程在运行过程中的动态变化情况，系统管理效果显然不佳。 2. 动态优先数法。动态优先数是指在系统创建进程时，根据系统资源的使用情况和进程的当前特点确定一个优先数，然后，在进程运行过程中再根据情况的变化动态调整进程的优先数。 调整进程优先数的原则： 1）进程占有处理机的时间越长，则进程的优先级越低；进程的等待时间越长，则进程的优先级越高。 2）根据进程所执行的程序的轻重缓急程度，调整进程的优先数。 优先权的变化规律： (1) 如果进程（作业）的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短进程（作业）。 (2) 当要求服务的时间相同时，进程（作业）的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。 (3) 对于长进程（作业），进程（作业）的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高， 从而也可获得处理机（进入主存）。 （二）时间片轮转调度算法 在分时系统中，为了满足系统对响应时间的要求，通常采用时间片轮转调度算法。 1. 简单轮转法(固定时间片轮转法） 在这种调度算法中，系统把所有就绪进程按到达的先后顺序形成一个就绪队列，就绪队列中的所有进程按时间片依次轮流获得处理机。 时间片的大小应根据进程要求系统给出应答的时间和进入系统的进程数来决定。可以表示为： 其中，q是时间片的大小，T是系统的响应时间，N是进入系统的进程数。 简单轮转法的优点是简单、方便，但由于采用固定时间片的方式，调度欠灵活，服务质量不够理想。可以通过以下两个方面加以改进： 1）将固定时间片方式改为可变时间片方式； 2）将单就绪队列改为多就绪队列。 2. 可变时间片轮转法 时间片可变会给系统带来好处。如果要求系统快速应答，则时间片小一些，这样可使轮转一遍的总时间减少而可对进程尽快应答。如果进程数少，则时间片可以大一些，这样可减少进程调度的次数，提高系统效率。 可变时间片轮转法中，可采取如下措施调整时间片： 1) 固定周期轮转法。 在这种方法中，每一轮调度中所得的时间片q＇值的大小仅在这一轮调度中有效。系统的响应时间T固定，在每一轮调度中，根据当前就绪队列中的进程数n计算这一轮调度的时间片：q＇＝T/ n ， 然后进行轮转，每个进程可获得这一轮的一个时间片q＇。在此期间所到达的进程暂不进入就绪队列，等此次轮转完毕再一并进入。系统根据此时就绪队列的进程数重新计算时间片q＇，然后开始下一轮循环。 2) 时间片的大小取决于优先级的高低，优先级高的进程分得的时间片较大，优先级低的进程分得的时间片较小。 3) 短作业的时间片较小，长作业的时间片较大。 3.多级反馈轮转法（多重时间片轮转调度算法） 调度算法的实施过程如下： 1. 设置多个就绪队列，并为各个就绪队列赋予不同的优先级。第一个就绪队列的优先级最高，第二个就绪队列的优先级次之，其余各个就绪队列的优先级逐个降低。 2.赋予各个就绪队列中进程的时间片也各不相同，优先级越高的就绪队列中的进程的时间片越小，反之，优先级越低的就绪队列中的进程的时间片越大。 3.当一个新被创建的进程进入就绪队列后，首先将它加入第一个就绪队列的队尾，按先来先服务的原则排队等待调度。 当轮到该进程执行时，如能在该时间片内完成，则该进程将被撤消；如果在一个时间片结束时该进程尚未完成，调度程序则将该进程转入第二个就绪队列的队尾，按先来先服务的原则排队等待调度；如果它在第二个就绪队列中运行一个时间片后仍未完成，再以同样的方法将它转入第