操作系统总汇.docx

第三章 §3.1 调度的基本概念 (一） 一、调度的类型和模型 一个批处理型作业从进入系统并驻留在外存的后备队列上开始，直至作业运行完毕，可能要经历三级调度过程：1、高级调度 又称为作业调度，作用：把外存上处于后备队列中的作业调入内存，并为他们创建进程、分配资源、排在就绪队列上，准备执行，因此，有时把它称为接纳调度。分时系统、实时系统中通常不具备作业调度。2、低级调度 又称为进程调度，它决定就绪队列中哪个进程将获得处理机，然后由分派程序执行把处理机分配给进程的操作。在OS中都必须配置。3、中级调度 目的：提高内存利用率和系统吞吐量。作用：使暂时不能运行的进程从内存调至外存，进入就绪驻外存状态或挂起状态。把外存上又具备运行条件的就绪进程，重新调入内存，并修改为就绪状态，挂在就绪队列上。又称对换。 一.、先来先服务（FCFS）算法 FCFS（First Come First Server ）法，又称为先进先出（FIFO）算法，就绪进程按照进入的先后次序排列，调度程序总是选择队首的进程执行。 这是一种非剥夺式的调度算法，简单、易实现。 对短进程易出现等待时间长，服务质量差。 该算法有利于CPU繁忙型的进程，不利于I/O繁忙型的进 程。 该算法只能用于辅助算法。二、短作业（进程）优先（SJ(P)F）算法 短作业优先（SJF）调度算法:是从后备队列中选择一个或若干个估计运行时间最短作业，将它们调入内存运行。而短进程则是从就绪队列中选择估计时间最短的进程，把处理机分配给它。 SJ(P)F调度算法也存在不容忽视的缺点：（1）对长作业不利。如果有一长作业进入系统的后备队列，由于总是优先调度那些短作业（进程），将导致长作业长期不被调度。（2）完全未考虑作业的紧迫程度，不能保证紧迫性作业（进程）会被及时处理。（3）作业（进程）的长短根据用户所提供的估计执行时间而定的不一定能真正做到短作业优先调度。 三、 最高优先权（HPF）优先调度算法优先权调度算法的类型非抢占式优先权算法把处理机分配给就绪队列中优先权最高的进程后便一直执行下去直至完成；或发生某事件使该进程放弃处理机时，可再将处理机重新分配给另一优先权最高的进程。用于批处理系统和某些对实时性要求不严的实时系统中。抢占式优先权调度算法把处理机分配给优先权最高的进程，使之执行。在执行期间，只要又出现优先权更高的进程，就重新将处理机分配给新到的优先权最高的进程。能更好地满足紧迫作业的要求，常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。优先权的类型1）静态优先权 ：在创建进程时确定在进程的整个运行期间保持不变。一般地，用某一范围内的一个整数来表示的，例如，0~7或0~255中的某一整数，又把该整数称为优先数。 静态优先权法优缺点：简单，系统开销小不精确，仅在要求不高的系统中使用动态优先权高响应比优先调度算法 优先权随进程推进或随其等待时间的增加而改变的，以便获得更好的调度性能。 引入动态优先权，并使作业优先级随着等待时间的增加而以速率a提高。该优先权的变化规律为：优先权 =（等待时间+要求服务时间） /要求服务时间优先权 = RP =响应时间/要求服务时间RP ：响应比 四、高响应比优先调度算法（HRN） HRN（Highest Response ratio Next）算法将短进程优先与动态优先级相结合。所谓高响应是指进程获得调度的响应，即优先数R。 R =（W+T）/T = 1+W/T T — 估计进程执行的时间。 W — 进程等待的时间。 由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为： ① 随着进程等待时间的增加，优先权动态增加。 ② 对等待相同时间的短进程比长进程优先权增加得多。 ③ 长进程随着等待时间增加也会被调度。 例：有4个作业A、B、C、D，它们的到达时间分别为8.00，8.50，9.00，9.50，各自要求服务时间为2.00，0.50，0.10，0.20，求它们平均周转时间和平均带权周转时间? (1) 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。 (2) 当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。 (3) 对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时