操作系统第三章

第三章处理机调度与死锁第一节处理机调度的层次和调度算法的目标第二节作业与作业调度第三节进程调度第四节实时调度第五节死锁概述第六节预防死锁第七节避免死锁第八节死锁的检测与解除第一节处理机调度的层次和调度算法的目标在多道批处理系统中，存在着多个进程的数量已超过了处理机的数量。这就要求系统能够实现动态地将处理机分配给一个就绪进程。这个分配任务便是交由处理机调度程序完成的。这个调度程序的调度性能直接决定着系统的吞吐量高不高、资源利用率大不大，作业周转的时间以及系统响应的及时性等等，故处理机调度便成为OS中至关重要的部分。第一节处理机调度的层次和调度算法的目标处理机调度：根据处理机分配策略所规定的处理机分配算法，对处理机资源进行分配。由于在多道环境下，一个作业从提交到获得处理机执行，到作业运行完成，在这个过程中，可能需要经历多级处理机调度—处理机的层次：高级调度：称长程调度或作业调度调度对象：为作业。调度功能：实现将外存后备队列中的哪几个作业调入到内存中，为它们创建进程，分配系统资源，并插入就绪队列中。（应用于多道批处理系统）低级调度：称进程调度或短程调度调度对象：进程。调度功能：决定在内存中的就绪队列中，哪个进程应获得处理机，并由分派程序将处理机分配给被选中的进程。（应用于多道批处理系统、分时系统、实时系统）第一节处理机调度的层次和调度算法的目标中级调度：称内存调度调度对象：为进程。调度功能：实现提高内存利用率和系统吞吐量，将暂时不能运行的进程调至外存等待，进程状态转为就绪驻外存状态或挂起状态。当它具备运行条件且内存具有空间则重新调入内存，变为就绪状态。（应用于存储器管理）三种调度的比较与分析运行频率：进程调度中级调度作业调度运行时间：作业调度（几分钟）中级调度进程调度（10~100ms）调度队列模型具有高、低、中三级调度的调度队列模型就绪队列绪就、挂起队列CPU时间片完作业调度进程调度进程完成事件出现阻塞队列挂起等待事件中级调度事件发生后备队列塞阻、挂起队列挂起第一节处理机调度算法的目标不同类型的的操作系统具有不同的调度方式和算法，这些算法具有一些共同的目标，当然根据各自OS系统的特征，也形成了有差异的目标：处理机调度算法的共同目标批处理系统的目标分时系统的目标实时系统的目标第一节处理机调度算法的目标处理机调度算法的共同目标：（1）资源的利用率CPU的利用率=CPU有效工作时间/（CPU有效工作时间+CPU空闲等待时间）（2）公平性指应使诸进程都获得合理的CPU时间，不会发生进程饥饿现象，根据紧急性和重要程度来提供不同的服务。（3）平衡性由于系统中进程的类型多样，比如有计算进程，有I/O进程，为了使得处理机和各外部设备都处于忙碌状态，调度算法需要考虑保持资源使用的平衡性。（4）策略强制执行对所制定的策略只要需要，就必须准确执行，即使会造成某些工作的延迟也要执行。（例如：文件安全性检测）第一节处理机调度算法的目标批处理系统的目标：（1）平均周转时间短周转时间：指从作业被提交给系统开始到作业完成为止，这段时间间隔。包括：作业在外存后备队列上等待调度的时间、进程在就绪队列上等待调度的时间、进程在CPU上执行的时间、进程等待I/O操作完成的时间。为了使大多数用户都感到满意，系统应使作业的周转时间和平均周转时间尽量短，否则会引起特别是短作业用户的不满。那么作业平均周转时间表示为：第一节处理机调度算法的目标批处理系统的目标：（2）系统吞吐量高指在单位时间内系统所完成的作业数。单纯的满足吞吐量高只需要尽量多的选择短作业运行。（3）处理机利用率高使CPU一直忙碌，最好处理计算量大且复杂的长作业。分时系统的目标：（1）系统响应时间快指从用户通过键盘提交一个请求开始，到屏幕上显示处理结果为止的这一段时间间隔。（2）均衡性系统响应时间的快慢应与用户所请求服务的复杂性相适应。实时系统的目标：1.截止时间的保证：某任务必须开始执行或完成的最迟时间。2.可预测性：如对于视频连续播放，实现第i帧的播放和i+1帧的读取处理，这便提供了请求的可预测性。第二节作业与作业调度作业调度：将存放在外存后备队列中的作业调入内存中。1.批处理系统中的作业和作业步作业：不仅包含程序和数据还包含一份作业说明书，系统根据作业说明书来控制、运行程序。作业步：每个作业在运行期间，都要经历若干个加工步骤，我们把每个加工步骤称为一个作业步。例如：编译作业步、链接装配（目标程序）作业步、运行作业步。2.作业控制块（JCB）JCB：作为作业在系统中存在的标识，保存了系统对作业进行管理和调度的信息。包括：作业标识、用户名、资源使用情况等等。过程：一个作业进入系统，便为其建立JCB，然后根据其类型将它放入相应的后备队列中，若它被系统调度，则将其由外存放入内存。作业在运行过程中，系统会根据作业说明书对作业进行控制，完成运行后，系统将收回已分配给它的资源并撤销JCB。第二节作业与作业调度作业运行的三个阶段和三种状态（1）收容阶段作业进入系统后会存放在系统的外存（硬盘）中，创建JCB并插入到相应的后备队列来等待作业的调度，此时作业的状态称为后备状态。（2）运行阶段当作业被作业调度选中后，并为其创建进程，分配必要资源，插入到就绪队列中。作业从第一次进入到就绪状态到运行结束前期间，都称之为运行状态。（3）完成阶段当作业运行完成或发生异常情况而终止时，作业便进入完成状态。第二节作业与作业调度作业调度的主要任务（1）接纳多少个作业每次执行作业调度时，决定将多少个作业由外存调入到内存中，取决于多道程序度，即允许多少个作业同时在内存中运行。多道程序度的确定需要综合系统的规模、运行速度、作业大小、系统性能等情况。（2）接纳哪些作业由调度算法决定将哪些作业从外存调入内存。1.先来先服务调度算法2.短作业优先调度算法3.基于作业优先级的调度算法作业调度仅应用于批处理系统中，实时、分时系统没有。第二节调度算法先来先服务FCFS(firstcome,firstserved)短作业优先SJF(shortjobfirst)高响应比优先HRRN(HighestResponseRatioNext)先来先服务（FCFS）主要用于作业调度，也可用于进程调度。用于作业调度：每次从后备作业队列中选择最先进入的作业，将它们调入内存，为它们分配资源、创建进程，然后挂到就绪进程队列上。有利于长作业，而不利于短作业。用于进程调度：每次从就绪进程队列中选择最先进入的进程，为之分配处理机，使之投入运行。直到运行完成进程才会让出处理机--非抢占式。性能评价：周转时间=完成时间–到达时间带权周转时间=周转时间/服务（运行）时间进程编码到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C21101102100100D31001022021991.99单处理机系统，FCFS有利于CPU繁忙型的作业短作业优先调度算法短作业优先算法（SJF）是以作业所要求的运行时间长短来计算优先级的，作业越短，其优先级越高。SIF算法将从外存的后备队列中，选择若干个估计运行时间最短的作业，优先将它们调入内存运行。缺点：1.必须预知作业的运行时间，一般采用偏长估计。2.对长作业非常不利，其周转时间会明显增长，没有限制作业等待时间，可能会出现饥饿现象。3.无法实现人机交互。4.未考虑作业的紧迫程度。短作业/进程优先（SJ/PF）作调业度情算况法进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间47121418周转时间461011149带权周转时间1225.53.52.8FJS完成时间4918613周转时间4816398带权周转时间12.673.21.52.252.1优先级调度算法（PSA）是基于作业的紧迫程度，由外部赋予作业相应的优先级，根据优先级进行调度，该算法既能用于作业调度，也可用于进程调度。作业调度思想：从后备队列中选择若干个优先级最高的作业，装入内存或（进程）分配给处理机。对进程调度而言，有非抢占式和抢占式两种。非抢占式：主要用于批处理系统，也可用于某些对实时性要求不严的实时系统抢占式：每当出现新就绪进程，就将其优先权与正在执行的进程的优先权比较；用于严格的实时系统，对性能要求高的批处理和分时系统中。高响应比优先调度算法HRRNFCFS算法特点：只考虑作业从进入系统时，在后备队列中排队等待被系统调入内存中的等待时间，也就是先来先服务思想，而忽略了作业的运行时间。SJF算法特点：只考虑作业的运行时间，按照运行时间越短越优先的选择，而忽略了作业的等待时间，与FCFS算法正好相反。HRRN算法特点：既考虑了作业的等待时间又考虑了作业的运行时间。因此照顾了短作业，又不致使长作业的等待时间过长。高响应比中优先权动态优先权：系统为每一个作业创建一个动态优先级，令它随等待时间的延长而增加，即作业的等待时间越久，那么作业的优先级会变得越来越高，到一定时间后，必然获得调度。优先级的变化规律用公式描述为：等待时间+要求服务时间优先权=------------------------------------要求服务时间高响应比中响应比等待时间+要求服务时间优先权=------------------------------------要求服务时间Rp响应比：等待时间+要求服务时间响应时间Rp=------------------------------------=-------------------要求服务时间要求服务时间该调度算法大大改进了FCFS和SJF算法的缺点。如果作业的等待时间相同，则要求服务的时间越短，优先权越高，该算法有利于短作业当要求服务的时间相同时，等待时间越长，优先权越高，实现了FCFS对于长作业，当等待时间足够长，优先权可升到很高，也可以得到处理该算法照顾了短作业，考虑了作业到达的先后次序，不会使长作业长期得不到服务，它实现了一个较好的折中。课堂练习计算在单CPU环境下,采用FCFS调度算法、SJF优先调度算法和高响应比优先算法时的平均周转时间和平均带权周转时间,并指出它们的调度顺序作业号到达时刻服务时间(小时)19:00229:30139:400.5410:300.3答案FCFS：进程编码到达时间服务时间(小时)开始执行时间完成时间周转时间(小时)带权周转时间19:0029:0011:002129:30111:0012:002.52.539:400.512:0012:302.835.66410:300.312:3012:482.37.66答案SJF：进程编码到达时间服务时间(小时)开始执行时间完成时间周转时间(小时)带权周转时间19:0029:0011:002129:30111:4812:483.33.339:400.511:1811:482.134.26410:300.311:0011:180.82.66顺序：1-4-3-2答案_优先级计算HRRN：高响应比优先优先级计算方法：第一轮：优先级比较（编号3优先）2.优先级=（1.5+1）/1=2.53.优先级=（1.33+0.5）/0.5=3.664.优先级=（0.5+0.3）/0.3=2.66进程编码到达时间服务时间(小时)开始执行时间完成时间周转时间(小时)带权周转时间19:0029:0011:002139:400.511:0011:301.833.66第二轮：优先级比较（编号4优先）2.优先级=（2+1）/1=34.优先级=（1+0.3）/0.3=4.33顺序：1-3-4-2答案HRRN：高响应比优先进程编码到达时间服务时间(小时)开始执行时间完成时间周转时间(小时)带权周转时间19:0029:0011:002129:30111:4812:483.33.339:400.511:0011:301.833.66410:300.311:3011:481.34.3顺序：1-3-4-2进程调度无论是在多道批处理系统、分时系统还是实时系统中，都配置了进程调度。进程调度任务（