《处理机调度与死锁(3)》由会员分享，可在线阅读，更多相关《处理机调度与死锁(3)（48页珍藏版）》请在金锄头文库上搜索。
1、第三章第三章 处理机调度与死锁处理机调度与死锁 3.1 3.1 处理机调度的根本概念处理机调度的根本概念 3.2 3.2 调度算法调度算法 3.3 3.3 实时调度实时调度 3.4 3.4 多处理机系统中的调度多处理机系统中的调度 3.5 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件 3.6 3.6 预防死锁的方法预防死锁的方法 3.7 3.7 死锁的检测与解除死锁的检测与解除 .作业的状态及其转换作业的状态及其转换批处理系统才有作业的概念，分时系统没有作业的概念；批处理系统才有作业的概念，分时系统没有作业的概念；作业的状态分为：提交、后备、运行和完成；作业的状态分为：提交、后备、
2、运行和完成；提交状态：作业再输入设备上并准备进入外存输入井前的状态。用户提交状态：作业再输入设备上并准备进入外存输入井前的状态。用户作业通常包括：程序、数据和作业说明书作业通常包括：程序、数据和作业说明书后备状态：由后备状态：由SPOOLingSPOOLing输入程序输入到外存输入井中，为其建立作输入程序输入到外存输入井中，为其建立作业控制块业控制块JCBJCB，并将，并将JCBJCB插入到后备作业队列中的状态插入到后备作业队列中的状态运行状态：作业被作业调度程序选中，由外存输入井调入到内存，为运行状态：作业被作业调度程序选中，由外存输入井调入到内存，为其分配了所需的资源并建立了进程，此时作业
3、就进入到运行状态。其分配了所需的资源并建立了进程，此时作业就进入到运行状态。完成状态：当作业正常结束或异常终止时，就进入完成状态。由作业完成状态：当作业正常结束或异常终止时，就进入完成状态。由作业调度程序做收尾工作：撤销调度程序做收尾工作：撤销JCBJCB、回收分给该作业的系统资源等。、回收分给该作业的系统资源等。3.1 3.1 处理机调度的根本概念处理机调度的根本概念.作业的状态及其转换作业的状态及其转换提交后备运行就绪阻塞就绪阻塞完成SPOOLing程序作业调度程序进程调度程序中级调度外存外存输入井输入设备内存.在多道批处理系统中，一个作业从提交到后备作业队列，再调入内从在多道批处理系统中
4、，一个作业从提交到后备作业队列，再调入内从经运行到完成，可能需要经历三级调度：经运行到完成，可能需要经历三级调度：1.1.高级调度高级调度High Scheduling)High Scheduling)高级调度又称为作业调度或宏观调度或长程调度，其主要功能高级调度又称为作业调度或宏观调度或长程调度，其主要功能是根据一定的算法，从后备作业队列一批作业中选出假设干是根据一定的算法，从后备作业队列一批作业中选出假设干个作业调入内存，并为它们创立进程和分配必要的资源，然后将个作业调入内存，并为它们创立进程和分配必要的资源，然后将创立的新进程放入进程就绪队列中，使其处于就绪状态。当作业创立的新进程放入进
5、程就绪队列中，使其处于就绪状态。当作业运行结束时，还要做一些善后工作资源回收运行结束时，还要做一些善后工作资源回收3.1.1 3.1.1 处理机调度的层次处理机调度的层次.高级调度特点：高级调度特点：1 1多道批处理系统需要作业调度；分时系统和实时系统多道批处理系统需要作业调度；分时系统和实时系统一般不需要高级调度。一般不需要高级调度。2 2每次调度多少作业程序？需由系统规定的多道程每次调度多少作业程序？需由系统规定的多道程序度而定；序度而定；3 3调度那些作业？由调度算法策略而定，如先来先调度那些作业？由调度算法策略而定，如先来先效劳，短作业优先调度，优先权调度算法等。效劳，短作业优先调度，
6、优先权调度算法等。.2.2.中级调度中级调度(Intermediate-Level Scheduling)(Intermediate-Level Scheduling)中级调度又称之为中程调度中级调度又称之为中程调度(Medium-Term Scheduling)(Medium-Term Scheduling)，中级调度主要任务是实施进程在内、外存间的交换；，中级调度主要任务是实施进程在内、外存间的交换；中级调度的主要功能是在内存使用紧张时，将一些暂时不中级调度的主要功能是在内存使用紧张时，将一些暂时不能运行的进程从内存对换到外存上等待此时的进程状能运行的进程从内存对换到外存上等待此时的进程状
7、态称为挂起状态或驻留外存状态。以后，当外存有足态称为挂起状态或驻留外存状态。以后，当外存有足够的空闲空间时，再将适宜的进程重新换入内存，等待够的空闲空间时，再将适宜的进程重新换入内存，等待进程调度。进程调度。引入中级调度的主要目的是为了提高内存的利用率和系统引入中级调度的主要目的是为了提高内存的利用率和系统吞吐量。吞吐量。.3.3.低级调度低级调度(Low Level Scheduling)(Low Level Scheduling)低级调度又称进程调度或微观调度或短程调度，其主要功低级调度又称进程调度或微观调度或短程调度，其主要功能是根据一定的算法，将能是根据一定的算法，将CPUCPU分派给
8、就绪进程队列中的分派给就绪进程队列中的某一进程。某一进程。执行低级调度功能的程序称为进程调度程序，由它实现执行低级调度功能的程序称为进程调度程序，由它实现CPUCPU在进程间的切换。在进程间的切换。进程调度是操作系统中最根本的一种调度，在一般操作系进程调度是操作系统中最根本的一种调度，在一般操作系统包括：多道批处理系统、分时系统和实时系统中统包括：多道批处理系统、分时系统和实时系统中都必须有进程调度，而且它的策略的优劣直接影响整个都必须有进程调度，而且它的策略的优劣直接影响整个系统的性能。系统的性能。.4 4、进程调度方式、进程调度方式 n非抢占方式非抢占方式NonpreemptiveNonp
9、reemptive：在这种调度方式下，一旦一个：在这种调度方式下，一旦一个进程被选中运行，它就一直运行下去，直到它运行结束并自愿放进程被选中运行，它就一直运行下去，直到它运行结束并自愿放弃弃CPUCPU，或者因等待某一事件而被阻塞或终止时为止，才把，或者因等待某一事件而被阻塞或终止时为止，才把CPUCPU出让给其他进程，即得到出让给其他进程，即得到CPUCPU的进程不管运行多长时间，都一直的进程不管运行多长时间，都一直运行下去，不会因为当前进程以外的原因而被迫让出运行下去，不会因为当前进程以外的原因而被迫让出CPUCPU。n引起调度的原因：引起调度的原因：1 1当前进程运行结束或发生某事件而终
10、止；当前进程运行结束或发生某事件而终止；2 2当前进程因提出当前进程因提出I/OI/O请求而阻塞；请求而阻塞；3 3进程之间通信或同步而由进程之间通信或同步而由于执行原语而等待。于执行原语而等待。.n抢占方式抢占方式PreemptivePreemptive：抢占方式允许调度程序根据某种策略：抢占方式允许调度程序根据某种策略中止当前进程的执行，将其移入就绪队列，并将处理机分派给另中止当前进程的执行，将其移入就绪队列，并将处理机分派给另一个进程使之投入运行。一个进程使之投入运行。n抢占原那么：抢占原那么：1 1优先权原那么：允许高优先权进程抢占低优先权优先权原那么：允许高优先权进程抢占低优先权的的
11、CPUCPU；2 2短作业原那么：允许短进程抢占长进程的处理机；短作业原那么：允许短进程抢占长进程的处理机；3 3时间片原那么：分时系统中的当前进程，假设时间片规定的时时间片原那么：分时系统中的当前进程，假设时间片规定的时间用完，不管是否运行结束，都要立即中止放到就绪队列中，再间用完，不管是否运行结束，都要立即中止放到就绪队列中，再将将CPUCPU分派给其它进程。分派给其它进程。.3.1.2 3.1.2 调度队列模型调度队列模型 不同不同OSOS对高级、中级和低级调度的选取形成了不同的调度队列模对高级、中级和低级调度的选取形成了不同的调度队列模型，共有型，共有3 3种类型。种类型。1 1、仅有
12、进程调度的调度队列模型、仅有进程调度的调度队列模型 常在分时系统中设置仅有进程调度的调度队列模型。终端用户的常在分时系统中设置仅有进程调度的调度队列模型。终端用户的登录注册以及交互命令的输入执行，系统都将为其建立进程，并登录注册以及交互命令的输入执行，系统都将为其建立进程，并放在放在FIFOFIFO就绪队列中，按照时间片轮转调度执行。进程的调度和就绪队列中，按照时间片轮转调度执行。进程的调度和变化过程如以下图所示。变化过程如以下图所示。.图图3-1 3-1 仅具有进程调度的调度队列模型仅具有进程调度的调度队列模型 P1P2P4.2.2.具有高级和低级调度的调度队列模型具有高级和低级调度的调度队
13、列模型在批处理系统中，不仅需要进程调度，而且还需要作业调度。假设在批处理系统中，不仅需要进程调度，而且还需要作业调度。假设OSOS中仅包含高级调度和低级调度就形成了具有高级和低级调度的队中仅包含高级调度和低级调度就形成了具有高级和低级调度的队列模型。列模型。进程调度进程调度常以最高常以最高优先权优优先权优先调度算先调度算法，就绪法，就绪队列形式队列形式为优先权为优先权队列。队列。阻塞队列按照不同事件排队阻塞队列按照不同事件排队就绪队列进程调度进程调度CPU进程完成等待事件 1作业作业调度调度事件1出现时间片完等待事件 2事件2出现等待事件 n事件n出现后备队列.3.3.同时具有三级调度的调度队
14、列模型同时具有三级调度的调度队列模型 作业作业CPU就绪挂起队列就绪挂起队列阻塞挂起队列阻塞挂起队列阻塞队列阻塞队列就绪队列就绪队列时间片到时间片到进程调度进程调度作业调度作业调度调入调入中级调度中级调度事件出现事件出现交互式用户交互式用户等待事件等待事件进程完成进程完成挂起调出挂起调出挂起调出挂起调出事件出现事件出现 具有三级调度时的调度队列模型具有三级调度时的调度队列模型 .3.1.3 3.1.3 选择调度方式和调度算法的假设干准那么选择调度方式和调度算法的假设干准那么 1.1.面向用户的准那么面向用户的准那么 周转时间短：周转时间短：周转周期是指作业从提交给系统开始，到作业完周转周期是指
15、作业从提交给系统开始，到作业完成为止所消耗的时间。常用于衡量系统性能、作业调度算法的成为止所消耗的时间。常用于衡量系统性能、作业调度算法的优劣的重要指标。优劣的重要指标。可把平均周转时间描述为：可把平均周转时间描述为：作作业业的的周周转转时时间间T与与系系统统为为它它提提供供效效劳劳的的时时间间TS之之比比，即即W=T/TS，称为带权周转时间，而平均带权周转时间那么可表示为称为带权周转时间，而平均带权周转时间那么可表示为:.响应时间快：分时系统性能的主要评价指标。响应时间指用户响应时间快：分时系统性能的主要评价指标。响应时间指用户从键盘键入一个命令开始，到系统首次给出响应信息为止这段从键盘键入
16、一个命令开始，到系统首次给出响应信息为止这段时间。时间。截止时间的保证：评价实时系统性能的重要指标。截止时间是截止时间的保证：评价实时系统性能的重要指标。截止时间是指系统为处理某事件指系统为处理某事件/任务必须开始执行的最迟时间，或必须任务必须开始执行的最迟时间，或必须完成的最迟时间。完成的最迟时间。优先权准那么：批处理、分时和实时系统中的调度算法都应该优先权准那么：批处理、分时和实时系统中的调度算法都应该遵循的原那么。这种调度思想就是遵循的原那么。这种调度思想就是“急事急办，优先权高者急事急办，优先权高者为急。为急。.2.2.面向系统的准那么面向系统的准那么 系统吞吐量高：评价批处理系统整体性能的重要指标。吞吐系统吞吐量高：评价批处理系统整体性能的重要指标。吞吐量是指单位时间内系统所完成的作业数。作业调度算法对系量是指单位时间内系统所完成的作业数。作业调度算法对系统吞吐量有直接影响，选择确定时应考虑这一准那么。统吞吐量有直接影响，选择确定时应考虑这一准那么。处理机利用率好：处理机利用率好：CPUCPU的利用率是衡量大中型系统性能的重的利用率是衡量大中型系统性能的重要指标。要指标。各类
