处理机调度与死锁课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,淮海工学院计算机科学系,*,第三章 处理机调度与死锁,3.1 处理机调度的基本概念,3.2 调度算法,3.3 实时调度,3.4 多处理机系统中的调度,3.5 产生死锁的原因和必要条件,3.6 预防死锁的方法,3.7 死锁的检测与解除,淮海工学院计算机科学系,第三章 处理机调度与死锁 3.1 处理机调度的基本概念 淮,1,作业的状态及其转换,批处理系统才有作业的概念，分时系统没有作业的概念；,作业的状态分为：,提交、后备、运行和完成；,提交状态：,作业再输入设备上并准备进入外存输入井前的状态。用户作业通常包括：程序、数据和作业说明书,后备状态：,由SPOOLing输入程序输入到外存输入井中，为其建立作业控制块（JCB），并将JCB插入到后备作业队列中的状态,运行状态：,作业被作业调度程序选中，由外存输入井调入到内存，为其分配了所需的资源并建立了进程，此时作业就进入到运行状态。,完成状态：,当作业正常结束或异常终止时，就进入完成状态。由作业调度程序做收尾工作：撤销JCB、回收分给该作业的系统资源等。,3.1 处理机调度的基本概念,淮海工学院计算机科学系,作业的状态及其转换批处理系统才有作业的概念，分时系统没有作业,2,作业的状态及其转换,提交,后备,运行,就绪,阻塞,就绪,阻塞,完成,SPOOLing,程序,作业调度程序,进程调度,程序,中级调度,外存,外存输,入井,输入设,备,内存,淮海工学院计算机科学系,作业的状态及其转换提交后备运行就绪阻塞就绪阻塞完成SPOOL,3,在多道批处理系统中，一个作业从提交到后备作业队列，再调入内从经运行到完成，可能需要经历三级调度：,1.高级调度（High Scheduling),高级调度又称为作业调度或宏观调度或长程调度，其主要功能是根据一定的算法，从后备作业队列（一批作业）中选出若干个作业调入内存，并为它们创建进程和分配必要的资源，然后将创建的新进程放入进程就绪队列中，使其处于就绪状态。当作业运行结束时，还要做一些善后工作（资源回收）,3.1.1 处理机调度的层次,淮海工学院计算机科学系,在多道批处理系统中，一个作业从提交到后备作业队列，再调入内从,4,高级调度特点：,1）多道批处理系统需要作业调度；分时系统和实时系统一般不需要高级调度。,2）每次调度多少作业（程序）？需由系统规定的多道程序度而定；,3）调度那些作业？由调度算法（策略）而定，如先来先服务，短作业优先调度，优先权调度算法等。,淮海工学院计算机科学系,高级调度特点：淮海工学院计算机科学系,5,2.中级调度(Intermediate-Level Scheduling),中级调度又称之为中程调度(Medium-Term Scheduling),，中级调度主要任务是实施进程在内、外存间的交换；,中级调度的主要功能是在内存使用紧张时，将一些暂时不能运行的进程从内存对换到外存上等待（此时的进程状态称为挂起状态或驻留外存状态）。以后，当外存有足够的空闲空间时，再将合适的进程重新换入内存，等待进程调度。,引入中级调度的主要目的是为了提高内存的利用率和系统吞吐量。,淮海工学院计算机科学系,2.中级调度(Intermediate-Level Sch,6,3.低级调度(Low Level Scheduling),低级调度又称进程调度或微观调度或短程调度，其主要功能是根据一定的算法，将CPU分派给就绪进程队列中的某一进程。,执行低级调度功能的程序称为进程调度程序，由它实现CPU在进程间的切换。,进程调度是操作系统中最基本的一种调度，在一般操作系统（包括：多道批处理系统、分时系统和实时系统）中都必须有进程调度，而且它的策略的优劣直接影响整个系统的性能。,淮海工学院计算机科学系,3.低级调度(Low Level Scheduling)淮,7,4、进程调度方式,非抢占方式（Nonpreemptive）：,在这种调度方式下，一旦一个进程被选中运行，它就一直运行下去，直到它运行结束并自愿放弃CPU，或者因等待某一事件而被阻塞或终止时为止，才把CPU出让给其他进程，即得到CPU的进程不管运行多长时间，都一直运行下去，不会因为当前进程以外的原因而被迫让出CPU。,引起调度的原因：1）,当前进程运行结束或发生某事件而终止；,2）,当前进程因提出I/O请求而阻塞；,3）,进程之间通信或同步而由于执行原语而等待。,淮海工学院计算机科学系,4、进程调度方式 非抢占方式（Nonpreemptive）：,8,抢占方式（Preemptive）：,抢占方式允许调度程序根据某种策略中止当前进程的执行，将其移入就绪队列，并将处理机分派给另一个进程使之投入运行。,抢占原则：,1）优先权原则：,允许高优先权进程抢占低优先权的CPU；,2）短作业原则：,允许短进程抢占长进程的处理机；,3）时间片原则：,分时系统中的当前进程，若时间片规定的时间用完，不管是否运行结束，都要立即中止放到就绪队列中，再将CPU分派给其它进程。,淮海工学院计算机科学系,抢占方式（Preemptive）：抢占方式允许调度程序根据某,9,3.1.2 调度队列模型,不同OS对高级、中级和低级调度的选取形成了不同的调度队列模型，共有3种类型。,1、仅有进程调度的调度队列模型,常在分时系统中设置仅有进程调度的调度队列模型。终端用户的登录注册以及交互命令的输入执行，系统都将为其建立进程，并放在FIFO就绪队列中，按照时间片轮转调度执行。进程的调度和变化过程如下图所示。,淮海工学院计算机科学系,3.1.2 调度队列模型 不同OS对高级、中级和低级调度的,10,图3-1 仅具有进程调度的调度队列模型,P1,P2,P4,淮海工学院计算机科学系,图3-1 仅具有进程调度的调度队列模型 P1P2P4淮海工学,11,2.具有高级和低级调度的调度队列模型,在批处理系统中，不仅需要进程调度，而且还需要作业调度。若OS中仅包含高级调度和低级调度就形成了具有高级和低级调度的队列模型。,进程调度常以最高优先权优先调度算法，就绪队列形式为优先权队列。,阻塞队列按照不同事件排队,就,绪,队,列,进程调度,CPU,进程完成,等待事件,1,作业,调度,事件,1,出现,时间片完,等待事件,2,事件,2,出现,等待事件,n,事件,n,出现,后,备,队,列,淮海工学院计算机科学系,2.具有高级和低级调度的调度队列模型进程调度常以最高优先权,12,3.同时具有三级调度的调度队列模型,作业,CPU,就绪挂起队列,阻塞挂起队列,阻塞队列,就绪队列,时间片到,进程调度,作业调度,调入,中级调度,事件出现,交互式用户,等待事件,进程完成,挂起调出,挂起调出,事件出现,具有三级调度时的调度队列模型,淮海工学院计算机科学系,3.同时具有三级调度的调度队列模型 作业CPU就绪挂起队列,13,3.1.3 选择调度方式和调度算法的若干准则,1.面向用户的准则,周转时间短：,周转周期是指作业从提交给系统开始，到作业完成为止所消耗的时间。常用于衡量系统性能、作业调度算法的优劣的重要指标。,可把平均周转时间描述为：,作业的周转时间,T,与系统为它提供服务的时间,T,S,之比，即,W,=,T/T,S,，称为带权周转时间，而平均带权周转时间则可表示为:,淮海工学院计算机科学系,3.1.3 选择调度方式和调度算法的若干准则 1.面向用户,14,响应时间快：,分时系统性能的主要评价指标。响应时间指用户从键盘键入一个命令开始，到系统首次给出响应信息为止这段时间。,截止时间的保证：,评价实时系统性能的重要指标。截止时间是指系统为处理某事件/任务必须开始执行的最迟时间，或必须完成的最迟时间。,优先权准则：,批处理、分时和实时系统中的调度算法都应该遵循的原则。这种调度思想就是“急事急办”，优先权高者为急。,淮海工学院计算机科学系,响应时间快：分时系统性能的主要评价指标。响应时间指用户从键盘,15,2.面向系统的准则,系统吞吐量高：,评价批处理系统整体性能的重要指标。吞吐量是指单位时间内系统所完成的作业数。作业调度算法对系统吞吐量有直接影响，选择确定时应考虑这一准则。,处理机利用率好：,CPU的利用率是衡量大中型系统性能的重要指标。,各类资源的平衡利用：,选择适当调度算法，保证各种资源的利用都处于忙碌状态。,淮海工学院计算机科学系,2.面向系统的准则 系统吞吐量高：评价批处理系统整体性能,16,3.2 调度算法,1、先来先服务（FCFS）调度算法,适应范围：,适应作业调度和进程调度；,调度过程：,FCFS用于作业（进程）调度时，从后备（就绪）队列中选择若干或一个先到来的作业（进程）投入运行。进程在分派到CPU进入运行过程中，只有当进程运行结束或因某事件发生而被阻塞才放弃CPU。,算法特点：,算法容易实现，但效率不高；只顾及作业等候时间，没考虑作业要求服务时间的长短，不利于短作业而优待了长作业；作业调度不分轻重缓急，人人平等；FCFS为非抢占式调度。,淮海工学院计算机科学系,3.2 调度算法 1、先来先服务（FCFS）调度算法淮海工,17,先来先服务（FCFS）调度算法效率举例,表注：周转时间=完成时间-到达时间；带权周转时间=周转时间/服务时间,淮海工学院计算机科学系,先来先服务（FCFS）调度算法效率举例表注：周转时间=完成时,18,2、短作业/进程（SJF/SPF）优先调度算法,适应范围：,适应作业调度和进程调度。SJF/SPF算法以进入系统的作业/进程所要求的CPU时间为标准，总选取估计计算时间最短的作业/进程投入运行。,算法特点：,算法易于实现，效率不高；忽视长作业等待时间，会出现饥饿现象；不考虑紧迫作业/进程的需求；长短时间人为估计，不可靠，会出现以长乱短。,SPF算法类型：,抢占或非抢占式。抢占式SPF调度算法在新进程进入就绪队列时，将其运行时间与当前进程的剩余运行时间相比，若更短时，可抢占CPU；非抢占式SPF算法允许当前运行进程先执行直到释放CPU为止。,可抢占SPF调度有时称为最短剩余时间优先（shortest-remaining-time-first）调度。,淮海工学院计算机科学系,2、短作业/进程（SJF/SPF）优先调度算法 适应范围：适,19,FCFS和SJF调度算法的性能分析,淮海工学院计算机科学系,FCFS和SJF调度算法的性能分析 淮海工学院计算机科学系,20,例题：,假如5个就绪进程其到达系统和所需CPU时间如下表所示（单位：毫秒），如果忽略I/O以及其他开销，分别计算采用FCFS、非抢占式SPF和抢占式SPF调度算法进行CPU调度的平均周转时间和平均带权周转时间。,进程到达和运行时间,进程,到达时间,运行时间,A,0,3,B,2,6,C,4,4,D,6,5,E,8,2,淮海工学院计算机科学系,例题：假如5个就绪进程其到达系统和所需CPU时间如下表所,21,解答如下：,（1）采用FCFS的调度顺序为：,A,B,C,D,E,0,3,9,13,18,20,平均周转时间为：,T=(3-0)+(9-2)+(13-4)+(18-6)+(20-8)/5=8.6,带权平均周转时间为：W=2.56,淮海工学院计算机科学系,解答如下：ABCDE039131820平均周转时间为：淮,22,（2）采用非抢占SJF的调度顺序为：,A,B,E,C,D,0,3,9,11,15,20,平均周转时间为：T=7.6,带权平均周转时间为：W=1.84,淮海工学院计算机科学系,（2）采用非抢占SJF的调度顺序为：ABECD03911,23,（3）采用抢占SJF的调度顺序为：,平均周转时间为：T=7.2,带权平均周转时间为：W=1.59,A,B1,E,C,B2,0,3,8,10,15,20,D,4,淮海工学院计算机科学系,（3）采用抢占SJF的调度顺序为：平均周转时间为：T=7,24,3、高优先权优先调度算法,（priority-scheduling algorithm）,1）优先权调度算法的类型,非抢占式优