计算机操作系统第三章处理机调度与死锁

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、型作业而言，通常需要经历作业调度作业调度(又称又称高级调度或长程调度高级调度或长程调度)和和进程调度进程调度(又称低级调度或又称低级调度或短程调度短程调度)两个过程后方能获得处理机；两个过程后方能获得处理机；对于终端型作业，则通常只需经过进程调度即可获对于终端型作业，则通常只需经过进程调度即可获得处理机。得处理机。3.1 处理机调度的基本概念处理机调度的基本概念 3.1.1 高级、中级和低级调度高级、中级和低级调度 1. 高级调度高级调度(High Scheduling) 高级调度高级调度(High Level Scheduling)又称为作业调又称为作业调度或长程调度度或长程调度(LongT

3、erm Scheduling)，其主要功能，其主要功能是根据某种算法，把是根据某种算法，把外存上处于后备队列中的那些作外存上处于后备队列中的那些作业调入内存业调入内存，也就是说，它的，也就是说，它的调度对象是作业调度对象是作业。在每在每次执行作业调度时，都须做出以下两个决定。次执行作业调度时，都须做出以下两个决定。 1) 接纳多少个作业接纳多少个作业 2) 接纳哪些作业接纳哪些作业 按照先来先服务、短作业优先、作按照先来先服务、短作业优先、作业优先级三种调度算法。业优先级三种调度算法。3.1.2 低级调度低级调度通常也把低级调度通常也把低级调度(Low Level Scheduling)称为进

4、称为进程调度或短程调度程调度或短程调度(ShortTerm Scheduling)，它所，它所调度的对象是进程调度的对象是进程(或内核级线程或内核级线程)。进程调度是最基本的一种调度，在多道批处理、分进程调度是最基本的一种调度，在多道批处理、分时和实时三种类型的时和实时三种类型的OS中，都必须配置这级调度。中，都必须配置这级调度。进程调度的基本概念进程调度的基本概念进程调度的实质进程调度的实质: 就是将处理器资源合理分配给就是将处理器资源合理分配给适当的，一方面确保任务的时间约束能被满足，适当的，一方面确保任务的时间约束能被满足，另一方面尽量提高处理器资源的利用率。另一方面尽量提高处理器资源的

5、利用率。进程调度就是从就绪状态的进程中，挑选一个进进程调度就是从就绪状态的进程中，挑选一个进程到处理器上运行。程到处理器上运行。操作系统中负责进程调度的程序称为进程调度器操作系统中负责进程调度的程序称为进程调度器（scheduler）或分派器）或分派器(dispatch）。）。调度要解决的问题调度要解决的问题WHAT：按什么原则分配：按什么原则分配CPU 调度算法调度算法WHEN：何时分配：何时分配CPU 调度的时机调度的时机HOW： 如何分配如何分配CPU 调度过程及进程的上下文切换调度过程及进程的上下文切换void OS_Sched (void) INT8U y; OS_ENTER_CRI

6、TICAL(); if (OSIntNesting = 0) & (OSLockNesting = 0) /* Sched. only if all ISRs done & not locked */ y = OSUnMapTblOSRdyGrp; /*Get pointer to HPT ready*/ OSPrioHighRdy = (INT8U)(y OSTCBPrio; self = TRUE; else if (prio = OSTCBCur-OSTCBPrio) /* See if suspending self */ self = TRUE; else self

7、= FALSE; /* No suspending another task */ ptcb = OSTCBPrioTblprio; if (ptcb = (OS_TCB *)0) /* Task to suspend must exist */ OS_EXIT_CRITICAL(); return (OS_TASK_SUSPEND_PRIO); if (OSRdyTblptcb-OSTCBY &= ptcb-OSTCBBitX) = 0 x00) /* Make task not ready */ OSRdyGrp &= ptcb-OSTCBBitY; ptcb-OSTCBS

8、tat |= OS_STAT_SUSPEND; /* Status of task is SUSPENDED */ OS_EXIT_CRITICAL(); if (self = TRUE) /* Context switch only if SELF */ OS_Sched(); return (OS_NO_ERR);1低级调度的功能低级调度的功能低级调度的主要功能如下：低级调度的主要功能如下：(1)按某种算法选取进程（调度）。按某种算法选取进程（调度）。(2)保存处理机的现场信息（上下文切换第一保存处理机的现场信息（上下文切换第一步骤）步骤）(3) 把处理器分配给进程（上下文切换第二步把处理

9、器分配给进程（上下文切换第二步骤）。骤）。2进程调度中的三个基本机制进程调度中的三个基本机制为了实现进程调度，应具有如下三个基本机制：为了实现进程调度，应具有如下三个基本机制：(1) 排队器排队器为了提高进程调度的效率，应事先将系统中所有的就绪为了提高进程调度的效率，应事先将系统中所有的就绪进程按照一定的方式排成一个或多个队列。进程按照一定的方式排成一个或多个队列。(2) 分派器分派器(调度程序调度程序)分派器把由进程调度程序所选定的进程，从就绪队列中分派器把由进程调度程序所选定的进程，从就绪队列中取出该进程取出该进程, 将处理机分配给它。将处理机分配给它。(3) 上下文切换机制上下文切换机制

10、当对处理机进行切换时，会发生两对上下文切换操作。当对处理机进行切换时，会发生两对上下文切换操作。 1) 非抢占方式非抢占方式(Non-preemptive Mode)在采用这种调度方式时，一旦把处理机分配给某进在采用这种调度方式时，一旦把处理机分配给某进程后，不管它要运行多长时间，都一直让它运行下程后，不管它要运行多长时间，都一直让它运行下去，去，决不会因为时钟中断等原因而抢占正在运行进决不会因为时钟中断等原因而抢占正在运行进程的处理机，也不允许其它进程抢占已经分配给它程的处理机，也不允许其它进程抢占已经分配给它的处理机。的处理机。直至该进程完成，自愿释放处理机，或发生某事件直至该进程完成，自

11、愿释放处理机，或发生某事件而被阻塞时，才再把处理机分配给其他进程。而被阻塞时，才再把处理机分配给其他进程。3. 进程调度方式进程调度方式 在采用非抢占调度方式时，可能引起进程调度的因素可归在采用非抢占调度方式时，可能引起进程调度的因素可归结为这样几个：结为这样几个： 正在执行的进程执行完毕，正在执行的进程执行完毕， 或因发生某事件而不能再继续或因发生某事件而不能再继续执行；执行； 执行中的进程因提出执行中的进程因提出I/O请求而暂停执行；请求而暂停执行； 在进程通信或同步过程中执行了某种原语操作，如在进程通信或同步过程中执行了某种原语操作，如P操作操作(wait操作操作)、Block原语、原语

12、、suspend原语等。原语等。 这种调度方式的优点是这种调度方式的优点是实现简单、系统开销小实现简单、系统开销小，适用于大，适用于大多数的批处理系统环境。但它多数的批处理系统环境。但它难以满足紧急任务的要求难以满足紧急任务的要求立立即执行，因而可能造成难以预料的后果。显然，在要求比较即执行，因而可能造成难以预料的后果。显然，在要求比较严格的实时系统中，不宜采用这种调度方式。严格的实时系统中，不宜采用这种调度方式。 2) 抢占方式抢占方式(Preemptive Mode) 这种调度方式允许调度程序根据某种原则去暂停某这种调度方式允许调度程序根据某种原则去暂停某个正在执行的进程，将已分配给该进程

13、的处理机重个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。新分配给另一进程。抢占方式的优点：抢占方式的优点：可以防止一个长进程长时间占用可以防止一个长进程长时间占用处理机，能为大多数进程提供更公平的服务，特别处理机，能为大多数进程提供更公平的服务，特别是能满足对响应时间有着较严格要求的实时任务的是能满足对响应时间有着较严格要求的实时任务的需求。需求。但抢占方式比非抢占方式调度所需付出的开销较大。但抢占方式比非抢占方式调度所需付出的开销较大。抢占的原则有：抢占的原则有： 优先权原则优先权原则 通常是对一些重要的和紧急的作业赋通常是对一些重要的和紧急的作业赋予较高的优先权。予较高的优

14、先权。(2) 短作业短作业(进程进程)优先原则优先原则。 (3) 时间片原则。时间片原则。 3. 中级调度中级调度(Intermediate-Level Scheduling) 中级调度又称中程调度中级调度又称中程调度(Medium-Term Scheduling)。 引引入中级调度的主要目的，是为了提高内存利用率和系统吞吐入中级调度的主要目的，是为了提高内存利用率和系统吞吐量。量。 为此，为此，应使那些暂时不能运行的进程调至外存上去等待，应使那些暂时不能运行的进程调至外存上去等待，把此时的进程状态称为就绪驻外存状态或挂起状态把此时的进程状态称为就绪驻外存状态或挂起状态。当这些。当这些进程重又

15、具备运行条件、且内存又稍有空闲时，由中级调度进程重又具备运行条件、且内存又稍有空闲时，由中级调度来决定把外存上的哪些又具备运行条件的就绪进程，重新调来决定把外存上的哪些又具备运行条件的就绪进程，重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。程调度。 三种调度的小结三种调度的小结进程调度的运行频率最高，在分时系统中通常是进程调度的运行频率最高，在分时系统中通常是10100 ms 便进行一次进程调度，因此把它称为短程调度。为避免便进行一次进程调度，因此把它称为短程调度。为避免进程调度占用太多的进程调度占用太多的CPU时间，进程

16、调度算法不宜太复杂。时间，进程调度算法不宜太复杂。作业调度往往是发生在一个作业调度往往是发生在一个(批批)作业运行完毕，退出系统，作业运行完毕，退出系统，而需要重新调入一个而需要重新调入一个(批批)作业进入内存时，故作业调度的周作业进入内存时，故作业调度的周期较长，大约几分钟一次，因此把它称为长程调度。由于其期较长，大约几分钟一次，因此把它称为长程调度。由于其运行频率较低，故允许作业调度算法花费较多的时间。运行频率较低，故允许作业调度算法花费较多的时间。中级调度的运行频率基本上介于上述两种调度之间，因此把中级调度的运行频率基本上介于上述两种调度之间，因此把它称为中程调度。它称为中程调度。3.1

17、.2 调度队列模型调度队列模型 1. 仅有进程调度的调度队列模型仅有进程调度的调度队列模型 图 3 - 1 仅具有进程调度的调度队列模型 就 绪队 列阻 塞队列进程调度CPU进程完成等待事件交互用户事件出现时间片完3.2 调度队列模型和调度准则调度队列模型和调度准则1. 仅有进程调度的调度队列模型仅有进程调度的调度队列模型 每个进程在执行时都可能出现以下三种情况：每个进程在执行时都可能出现以下三种情况：(1) 任务在给定的时间片内已经完成，该进程便在任务在给定的时间片内已经完成，该进程便在释放处理机后进入释放处理机后进入完成状态完成状态；(2) 任务在本次分得的时间片内尚未完成，任务在本次分得

18、的时间片内尚未完成，OS便将便将该任务再放入该任务再放入就绪队列的末尾就绪队列的末尾；(3) 在执行期间，进程因为某事件而被阻塞后，被在执行期间，进程因为某事件而被阻塞后，被OS放入放入阻塞队列阻塞队列。2. 具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型 图 3-2 具有高、低两级调度的调度队列模型 就 绪队列进程调度CPU进程完成等待事件1作业调度事件1出现时间片完等待事件2事件2出现等待事件n事件n出现后备 队列作业调度按一定的作业调度算法，从外存的后备队列中选择一作业调度按一定的作业调度算法，从外存的后备队列中选择一批作业调入内存，并为它们建立进程，送入就绪队列，然后

19、才批作业调入内存，并为它们建立进程，送入就绪队列，然后才由进程调度按照一定的进程调度算法选择一个进程，把处理机由进程调度按照一定的进程调度算法选择一个进程，把处理机分配给该进程。分配给该进程。当在当在OS 中引入中级调度后，人们可把进程的就绪中引入中级调度后，人们可把进程的就绪状态分为内存就绪状态分为内存就绪(表示进程在内存中就绪表示进程在内存中就绪)和外存和外存就绪就绪(进程在外存中就绪进程在外存中就绪)。把阻塞状态进一步分成内存阻塞和外存阻塞两种状把阻塞状态进一步分成内存阻塞和外存阻塞两种状态。态。在调出操作的作用下，可使进程状态由内存就绪转在调出操作的作用下，可使进程状态由内存就绪转为外

20、存就绪，由内存阻塞转为外存阻塞；为外存就绪，由内存阻塞转为外存阻塞；在中级调度的作用下，又可使外存就绪转为内存就在中级调度的作用下，又可使外存就绪转为内存就绪。绪。3. 同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型 3. 同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型 图 3-3 具有三级调度时的调度队列模型 就绪队列进程调度CPU就绪，挂起队列中级调度阻塞，挂起队列阻塞队列等待事件进程完成时间片完作业调度交互型作业后备队列批量作业挂起事件出现事件出现3.1.3 处理机调度算法的目标处理机调度算法的目标1。调度算法的共同目标：。调度算法的共同目标：1、提高资源利用

21、率提高资源利用率CPUCPU利用率利用率= CPU= CPU有效工作时间有效工作时间/(CPU/(CPU有效工作时间有效工作时间+CPU+CPU空闲等待时间空闲等待时间) )2 2、公平性、公平性3 3、系统资源使用的平衡性、系统资源使用的平衡性4 4、策略强制执行、策略强制执行调度的原则：满足用户的需要和系统的需要。调度的原则：满足用户的需要和系统的需要。（1）周转时间短）周转时间短。，是指从作业被提交给系统，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔（称开始，到作业完成为止的这段时间间隔（称为作业周转时间）。为作业周转时间）。作业在外存后备队列上等待调度的时间作业在外存后备队

22、列上等待调度的时间进程在就绪队列上等待进程调度的时间进程在就绪队列上等待进程调度的时间进程在进程在CPU上执行的时间上执行的时间进程等待进程等待IO操作完成的时间。操作完成的时间。 作业的周转时间作业的周转时间T与系统为它提供服务的时间与系统为它提供服务的时间Ts之之比，即比，即W=T/Ts，称为带权周转时间，平均带权周，称为带权周转时间，平均带权周转时间则可表示为转时间则可表示为: （2）系统吞吐量高）系统吞吐量高单位时间内系统所完成的作业数。尽量多选择短作业运行。（3）处理机利用率高）处理机利用率高选择合适的调度方法和调度算法提高CPU利用率。选择大作业运行。3、分时系统的目标、分时系统的

23、目标（1）响应时间快）响应时间快（2） 均衡性均衡性系统响应时间的快慢与用户所请求的服务的复杂系统响应时间的快慢与用户所请求的服务的复杂性相适应。性相适应。分时系统中，所谓响应时间，是从用户通过分时系统中，所谓响应时间，是从用户通过键盘（或者鼠标）提交一个请求开始，直至键盘（或者鼠标）提交一个请求开始，直至系统首次产生响应为止的时间。系统首次产生响应为止的时间。响应时间包括三部分时间：响应时间包括三部分时间：从键盘输入的请求信息传送到处理机的时间。从键盘输入的请求信息传送到处理机的时间。处理机对请求信息进行处理的时间。处理机对请求信息进行处理的时间。将所形成的响应信息回送到终端显示器的时间。将

24、所形成的响应信息回送到终端显示器的时间。4、实时系统的目标、实时系统的目标（1）截至时间的保证）截至时间的保证所谓截止时间，是指某任务所谓截止时间，是指某任务必须开始执行的最迟必须开始执行的最迟时间时间，或，或必须完成的最迟时间必须完成的最迟时间。（也叫做时限，。（也叫做时限，即即deadlinedeadline）（2）可预测性）可预测性保证任务执行的连续性，执行流程能够事先确定保证任务执行的连续性，执行流程能够事先确定。：正在执行的进程执行完毕，或因发生某事件而正在执行的进程执行完毕，或因发生某事件而不能再继续执行（包括：当前执行进程被中断、时不能再继续执行（包括：当前执行进程被中断、时间片

25、用完了、挂起自己、退出等）；间片用完了、挂起自己、退出等）；执行中的进程因提出执行中的进程因提出IO请求而暂停执行；请求而暂停执行；在进程通信或同步过程中执行了某种原语操作，如在进程通信或同步过程中执行了某种原语操作，如P、V操作原语，操作原语，Block原语，原语， Wakeup原语等。原语等。就绪队列中新进入了进程。（如创建了新的进程，就绪队列中新进入了进程。（如创建了新的进程，或者某个进程被唤醒、某个进程被激活）或者某个进程被唤醒、某个进程被激活）调度算法是指：根据系统的资源分配策略调度算法是指：根据系统的资源分配策略所规定的资源分配算法。对于不同的系统所规定的资源分配算法。对于不同的系

26、统目标，通常采用不同的调度算法。目标，通常采用不同的调度算法。1.先来先服务先来先服务2.短进程优先短进程优先3.时间片轮转时间片轮转4.高优先权优先调度算法高优先权优先调度算法实时调度算法实时调度算法最早截至时间优先最早截至时间优先EDF算法算法1. 先来先服务调度算法先来先服务调度算法(FCFS)缺陷：对待短作业（进程）不公平，如果他们排在队缺陷：对待短作业（进程）不公平，如果他们排在队列后面，则其等待时间远大于其执行时间。列后面，则其等待时间远大于其执行时间。短作业短作业(进程进程)优先调度算法优先调度算法SJ(P)F，是指对短作业或短进程是指对短作业或短进程优先调度的算法。它们可以分别

27、用于作业调度和进程调度优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先短作业优先(SJF)的调度算法的调度算法，是从后备队列中选择一个或，是从后备队列中选择一个或若干个若干个估计运行时间最短的作业估计运行时间最短的作业，将它们调入内存运行。，将它们调入内存运行。短进程优先短进程优先(SPF)调度算法调度算法，则是从就绪队列中选出一，则是从就绪队列中选出一估计估计运行时间最短的进程运行时间最短的进程，将处理机分配给它，使它立即执行并，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。重新

28、调度。 (1) 该算法对长作业不利，如作业该算法对长作业不利，如作业C的周转的周转时间由时间由10增至增至16，其带权周转时间由，其带权周转时间由2增至增至3.1。更严重的是，如果有一长作业。更严重的是，如果有一长作业(进程进程)进进入系统的后备队列入系统的后备队列(就绪队列就绪队列)，由于调度程，由于调度程序总是优先调度那些短作业序总是优先调度那些短作业(进程进程)，将导致将导致长作业长作业(进程进程)长期不被调度长期不被调度。 (2) 不能保证紧迫性作业不能保证紧迫性作业(进程进程)会被及时处理。会被及时处理。 (3) 由于作业由于作业(进程进程)的长短只是根据用户所提的长短只是根据用户所

29、提供的估计执行时间而定的，而用户不一定对供的估计执行时间而定的，而用户不一定对执行时间估计那么准确，致使该算法不一定执行时间估计那么准确，致使该算法不一定能真正做到短作业优先调度。能真正做到短作业优先调度。在时间片轮转法中，系统将所有的就绪进程按先来在时间片轮转法中，系统将所有的就绪进程按先来先服务的原则，排成一个队列，每次调度时，把先服务的原则，排成一个队列，每次调度时，把CPUCPU分配给队首进程。并令其执行一个时间片。分配给队首进程。并令其执行一个时间片。时间片处理过程：时间片处理过程：当执行的时间片用完时，由一个当执行的时间片用完时，由一个计时器发出时钟中断请求，操作系统便根据此信号计

30、时器发出时钟中断请求，操作系统便根据此信号来停止该进程的执行，并将它送往就绪队列的末尾；来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。同时也让它执行一个时间片。以此保证就绪队列中的所有进程，在一给以此保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片的处理机定的时间内，均能获得一时间片的处理机执行时间，换言之，系统能在给定的时间执行时间，换言之，系统能在给定的时间内，响应所有用户的请求。内，响应所有用户的请求。内核在满足下列条件时，将把内核在满足下列条件时，将把CPU

31、CPU交给下交给下一个就绪态的进程：一个就绪态的进程：当前进程因为某种原因暂停执行，如被阻塞；当前进程因为某种原因暂停执行，如被阻塞；当前进程在时间片还没有结束时已经完成了；当前进程在时间片还没有结束时已经完成了；时间片结束。时间片结束。有四个进程按时间片进行轮转调度有四个进程按时间片进行轮转调度(按按1个个时间片和时间片和4个时间片进行调度个时间片进行调度).1.1.时间片的大小对计算机性能的影响。时间片时间片的大小对计算机性能的影响。时间片太大、太小都不好。太大、太小都不好。2.2.存在的问题：未有效利用系统资源。对于短存在的问题：未有效利用系统资源。对于短的、计算型进程比较有利，因为该进

32、程充分的、计算型进程比较有利，因为该进程充分利用时间片，而利用时间片，而I/OI/O型进程却不利，因为在两型进程却不利，因为在两次次I/OI/O之间仅需很少的之间仅需很少的CPUCPU时间，却需要等待时间，却需要等待一个时间片。一个时间片。3.3.常用于分时系统及事务处理系统。常用于分时系统及事务处理系统。该算法是把该算法是把处理机分配给处理机分配给就绪队列就绪队列中优先中优先级最高的进程级最高的进程。该算法分两种类型：非抢占式优先权算法该算法分两种类型：非抢占式优先权算法和抢占式优先权调度算法和抢占式优先权调度算法 在这种方式下，系统一旦把处理机分配给就在这种方式下，系统一旦把处理机分配给就

33、绪队列中绪队列中优先权最高优先权最高的进程后，该进程便一的进程后，该进程便一直执行下去，直至完成；直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最统方可再将处理机重新分配给另一优先权最高的进程。高的进程。在这种方式下，系统同样是把处理机分配给在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止先权更高的进程，进程调度程序就立即停止当前进程的执行，重新将处

34、理机分配给新到当前进程的执行，重新将处理机分配给新到的优先权最高的进程。的优先权最高的进程。在采用这种调度算法时，是在采用这种调度算法时，是每当系统中出每当系统中出现一个新的就绪进程现一个新的就绪进程i时，就将其优先权时，就将其优先权Pi与正在执行的进程与正在执行的进程j的优先权的优先权Pj进行比较进行比较。如果如果PiPj，原进程，原进程Pj便继续执行；便继续执行；如果是如果是PiPj, 则立即停止则立即停止Pj的执行，做进的执行，做进程切换，使程切换，使i进程投入执行。进程投入执行。 特点：特点：能更好地满足紧迫作业的要求，故能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中，

35、以而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。及对性能要求较高的批处理和分时系统中。 缺点：缺点：系统开销较大。系统开销较大。 静态优先权静态优先权 静态优先权是在创建进程时确定的，且在进程静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。的整个运行期间保持不变。动态优先权动态优先权 动态优先权是指，在创建进程时所赋予的优先动态优先权是指，在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能加而改变的，以便获得更好的调度性能。 （1 1）进程类型。进程类型。系统进程

36、的优先权高于一系统进程的优先权高于一般用户进程的优先权。般用户进程的优先权。 （2 2）进程对资源的需求。进程对资源的需求。对要求少的进程对要求少的进程应赋予较高的优先权。应赋予较高的优先权。 （3 3）用户要求。用户要求。按照各进程的执行流程和按照各进程的执行流程和进程的紧迫程度来指定进程的优先权。进程的紧迫程度来指定进程的优先权。问题在批处理系统中，短作业优先算法是一种比较好的算法在批处理系统中，短作业优先算法是一种比较好的算法，其主要的不足之处是长作业的运行得不到保证。，其主要的不足之处是长作业的运行得不到保证。有没有什么办法既考虑到短作业，又能够估计长作业呢？有没有什么办法既考虑到短作

37、业，又能够估计长作业呢？如果我们能为每个作业引入前面所述的动态优先权，并如果我们能为每个作业引入前面所述的动态优先权，并使作业的优先级随着等待时间的增加而以速率使作业的优先级随着等待时间的增加而以速率a 提高，提高，则长作业在等待一定的时间后，必然有机会分配到处理则长作业在等待一定的时间后，必然有机会分配到处理机。机。优先权的变化规律可描述为：优先权的变化规律可描述为： 要要求求服服务务时时间间要要求求服服务务时时间间等等待待时时间间优优先先权权由于等待时间与服务时间之和，就是系统对该作业由于等待时间与服务时间之和，就是系统对该作业的的响应时间响应时间，故该优先权又相当于，故该优先权又相当于响

38、应比响应比RP。要求服务时间要求服务时间响应时间响应时间要求服务时间要求服务时间要求服务时间要求服务时间等待时间等待时间优先权优先权(1) 如果作业的等待时间相同，则要求服务的时间如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。愈短，其优先权愈高，因而该算法有利于短作业。 (2) 当要求服务的时间相同时，作业的优先权决当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。因而它实现的是先来先服务。 (3) 对于长作业，作业的优先级可以随等待时间对于长作业，作业的

39、优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先的增加而提高，当其等待时间足够长时，其优先级便可升到很高，级便可升到很高， 从而也可获得处理机。从而也可获得处理机。 该算法既照顾了短作业，又考虑了作业该算法既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得到达的先后次序，不会使长作业长期得不到服务。不到服务。利用该算法时，每次调度之前，都须先利用该算法时，每次调度之前，都须先做响应比的计算，做响应比的计算，会增加系统开销会增加系统开销。由于在实时系统中都存在着若干个实时进程由于在实时系统中都存在着若干个实时进程或任务，或任务， 实时进程通常带有某种程度的实时进程通常带

40、有某种程度的紧迫性；紧迫性； 需要引入一种新的调度解决实时进程的调度，需要引入一种新的调度解决实时进程的调度，即实时调度。即实时调度。 3.4 实时调度实时调度实时系统：实时系统：计算机计算机及时及时响应外部事件的请求，响应外部事件的请求，在在规定的时间内规定的时间内完成对该事件的处理，并控完成对该事件的处理，并控制所有实时设备和实时任务协调一致的运行。制所有实时设备和实时任务协调一致的运行。提供必要的信息提供必要的信息 （1）就绪时间。）就绪时间。（2）开始截止时间和完成截止时间。）开始截止时间和完成截止时间。（3）处理时间。）处理时间。（4）资源要求。）资源要求。（5）优先级。）优先级。在

41、实时系统中，通常都有着多个实时任务。若处理在实时系统中，通常都有着多个实时任务。若处理机的处理能力不够强，则有可能因处理机忙不过来机的处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不能得到及时处理，从而导致发而使某些实时任务不能得到及时处理，从而导致发生难以预料的后果。生难以预料的后果。假定系统中有假定系统中有m 个周期性的硬实时任务，它们的处个周期性的硬实时任务，它们的处理时间可表示为理时间可表示为Ci，周期时间表示为，周期时间表示为Pi，则在单处，则在单处理机情况下，必须满足下面的限制条件：理机情况下，必须满足下面的限制条件：假如系统中有假如系统中有6个硬实时任务，它们的周期时个

42、硬实时任务，它们的周期时间都是间都是 50 ms，而每次的处理时间为，而每次的处理时间为 10 ms，则不难算出，此时是不能满足上式的，因，则不难算出，此时是不能满足上式的，因而系统是不可调度的。而系统是不可调度的。解决的方法是提高系统的处理能力，其途径解决的方法是提高系统的处理能力，其途径有二：有二：其一仍是采用单处理机系统，但须增强其处理能其一仍是采用单处理机系统，但须增强其处理能力，以显著地力，以显著地减少对每一个任务的处理时间减少对每一个任务的处理时间；其二是采用多处理机系统。其二是采用多处理机系统。在含有硬实时任务的实时系统中，广泛采用在含有硬实时任务的实时系统中，广泛采用抢占机制抢

43、占机制。当一个优先权更高的任务到达时，。当一个优先权更高的任务到达时，允许暂停当前任务，而令高优先权任务立即允许暂停当前任务，而令高优先权任务立即投入运行，这样便可满足该硬实时任务对截投入运行，这样便可满足该硬实时任务对截止时间的要求。止时间的要求。 该机制应具有如下两方面的能力：该机制应具有如下两方面的能力： (1) 对外部中断的快速响应能力。对外部中断的快速响应能力。为使在紧迫的外部事件请求为使在紧迫的外部事件请求中断时系统能及时响应，要求系统具有快速硬件中断机构，还中断时系统能及时响应，要求系统具有快速硬件中断机构，还应使禁止中断的时间间隔尽量短，应使禁止中断的时间间隔尽量短， 以免耽误

44、时机以免耽误时机(其它紧迫任其它紧迫任务务)。 (2) 快速的任务分派能力。快速的任务分派能力。在完成任务调度后，便应进行任务在完成任务调度后，便应进行任务切换。为了提高任务切换的速度，切换。为了提高任务切换的速度， 应使系统中的每个运行功应使系统中的每个运行功能单位适当的小，以减少任务切换的时间开销。能单位适当的小，以减少任务切换的时间开销。 该算法是根据任务的该算法是根据任务的开始截止时间（或者结束截至开始截止时间（或者结束截至时间）时间）来确定任务的优先级。截止时间愈早，其优先来确定任务的优先级。截止时间愈早，其优先级愈高。级愈高。要求在系统中保持一个实时任务就绪队列，该队列要求在系统中

45、保持一个实时任务就绪队列，该队列按各任务截止时间的早晚排序；按各任务截止时间的早晚排序；具有最早截止时间的任务排在队列的最前面具有最早截止时间的任务排在队列的最前面。调度。调度程序总是选择就绪队列中的第一个任务，为之分配处程序总是选择就绪队列中的第一个任务，为之分配处理机，使之投入运行。理机，使之投入运行。 任务调度EDF调度当一个进程执行完（或不能继续执行），则换另一当一个进程执行完（或不能继续执行），则换另一个进程占处理机执行，称为进程切换。个进程占处理机执行，称为进程切换。在进程切换时，要保护执行现场。在进程切换时，要保护执行现场。执行现场称为进程的上下文。包括执行现场称为进程的上下文。

46、包括CPU主要寄存器，主要寄存器，如如SP，PC，通用寄存器。，通用寄存器。进程进程1 1进程进程2 2内核调度程序内核调度程序保存进程保存进程1 1的上下文到的上下文到PCB1PCB1从从PCB2PCB2恢复进程恢复进程2 2的上下文的上下文保存进程保存进程2 2的上下文到的上下文到PCB2PCB2从从PCB1PCB1恢复进程恢复进程1 1的上下文的上下文时间时间1 保存进程上下文环境保存进程上下文环境2 更新当前运行进程的控制块内容，将其状态改更新当前运行进程的控制块内容，将其状态改为就绪或阻塞状态为就绪或阻塞状态3 将进程控制块移到相应队列（就绪队列或阻塞将进程控制块移到相应队列（就绪队

47、列或阻塞队列）队列）4 改变需投入运行进程的控制块内容，将其状态改变需投入运行进程的控制块内容，将其状态变为运行状态变为运行状态5 恢复需投入运行进程的上下文环境恢复需投入运行进程的上下文环境Linux进程切换（进程切换（context_switch() ）本质上）本质上两步：两步：1) 进程页表进程页表PGD切换；切换；2) 内核态堆栈和硬件上下文切换（包括内核态堆栈和硬件上下文切换（包括CPU寄存器）；寄存器）； context_switch()通过调用通过调用switch_mm()切切换进程空间，调用换进程空间，调用switch_to切换内核上下切换内核上下文环境。文环境。作业1：分析分

48、析Linux3.0源代码中的源代码中的switch_to函数。搞函数。搞清楚进程上下文切换的过程。清楚进程上下文切换的过程。所谓死锁（所谓死锁（Deadlock），是指），是指多个进程在运多个进程在运行过程中因争夺资源而造成的一种僵局行过程中因争夺资源而造成的一种僵局（Deadly- Embrace），当进程处于这种僵），当进程处于这种僵持状态时，若无外力作用，它们都将无法再持状态时，若无外力作用，它们都将无法再向前推进。向前推进。3.5.1、产生死锁的原因、产生死锁的原因产生死锁的原因可归结为如下两点：产生死锁的原因可归结为如下两点： （1）竞争资源。）竞争资源。 （2）进程间推进顺序非法。

49、）进程间推进顺序非法。1）可剥夺和非剥夺性资源）可剥夺和非剥夺性资源可抢占性资源可抢占性资源: 是指某进程在获得这类资源后，是指某进程在获得这类资源后，该资源可以再被其他进程或系统剥夺。如该资源可以再被其他进程或系统剥夺。如CPU ，对于这类资源是对于这类资源是不会引起死锁不会引起死锁的。的。不可抢占性资源不可抢占性资源: 当系统把这类资源分配给某进当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自行程后，再不能强行收回，只能在进程用完后自行释放。释放。 如打印机等，对于这类资源如打印机等，对于这类资源会引起死锁会引起死锁。 2）竞争不可抢占性资源）竞争不可抢占性资源在系统中所

50、配置的非剥夺性资源，由于它们的在系统中所配置的非剥夺性资源，由于它们的数量不能满足诸进程运行的需要，会使进程在数量不能满足诸进程运行的需要，会使进程在运行过程中，因争夺这些资源而陷入僵局。运行过程中，因争夺这些资源而陷入僵局。例如，系统中只有一台打印机例如，系统中只有一台打印机R1和一台磁带机和一台磁带机R2，可供进程，可供进程P1和和P2共享。处理不好，在共享。处理不好，在P1与与P2之间会形成僵局，引起死锁。之间会形成僵局，引起死锁。 图 I/O设备共享时的死锁情况 此箭头表示P1已经获得R1资源此箭头表示P1申请R2资源 3）竞争临时性（可消耗性）竞争临时性（可消耗性 ）资源）资源 临时

51、性资源，临时性资源，也称之为消耗性资源，也称之为消耗性资源，它也可能引起死锁。它也可能引起死锁。例如：例如：S1、S2和和S3是临时性资源，是由进是临时性资源，是由进程程P1、P2和和P3产生的消息。如果消息通信产生的消息。如果消息通信处理顺序不当也会发生死锁。处理顺序不当也会发生死锁。图 3-13 进程之间通信时的死锁 S2P1S3P3S1P2产生接收2.进程推进顺序不当引起死锁进程推进顺序不当引起死锁1）进程推进顺序合法）进程推进顺序合法进程推进顺序合法不会引起进程死锁的。进程推进顺序合法不会引起进程死锁的。 2）进程推进顺序非法）进程推进顺序非法 若并发进程若并发进程P1和和P2推进顺序

52、不合法，进入推进顺序不合法，进入不安全状态，于是发生了进程死锁。不安全状态，于是发生了进程死锁。 2. 进程推进顺序不当引起死锁进程推进顺序不当引起死锁 1) 进程推进顺序合法进程推进顺序合法 P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)D不安全区域D除了曲线4外，都是安全的 D 2) 进程推进顺序非法进程推进顺序非法 若并发进程若并发进程P1和和P2按曲线所示的顺序推进，按曲线所示的顺序推进，它们将进入不安全区它们将进入不安全区D内。内。 此时此时P1保持了资源保持了资源R1, P2保持了资源

53、保持了资源R2, 系统处于系统处于不安全状态。因为，这时两进程再向前推进，便可不安全状态。因为，这时两进程再向前推进，便可能发生死锁。能发生死锁。例如，当例如，当P1运行到运行到P1:Request(R2)时，将因时，将因R2已被已被P2占用而阻塞；当占用而阻塞；当P2运行到运行到P2: Request(R1)时，也将时，也将因因R1已被已被P1占用而阻塞，于是发生了进程死锁。占用而阻塞，于是发生了进程死锁。 （1）互斥条件：互斥条件：指进程对所分配到的资源进行排它指进程对所分配到的资源进行排它性使用性使用 。（2）请求和保持条件：）请求和保持条件：指进程已经保持了至少一个指进程已经保持了至少

54、一个资源，但又提出了新的资源请求资源，但又提出了新的资源请求 。 （3）不可抢占条件：）不可抢占条件：指进程已获得的资源，在未使指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自用完之前，不能被剥夺，只能在使用完时由自己释放。己释放。 （4）环路等待条件：）环路等待条件：指在发生死锁时，必然存在一指在发生死锁时，必然存在一个个进程进程资源的环形链资源的环形链 。（1）预防死锁）预防死锁：是通过设置某些限制条件，：是通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一去破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁。个或几个条件，来预防发生死锁。（2）避免死锁：

55、）避免死锁：是在资源的动态分配过程中，是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，用某种方法去防止系统进入不安全状态，从而避免发生死锁。从而避免发生死锁。 （3）检测死锁：）检测死锁：通过系统所设置的检测机构，通过系统所设置的检测机构，及时地检测出死锁的发生，并精确地确定与及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源；死锁有关的进程和资源；（4）解除死锁：）解除死锁：当检测到系统中已发生死锁当检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。常用时，须将进程从死锁状态中解脱出来。常用的实施方法是的实施方法是撤消或挂起一些进程撤消或挂起一些进程。预防死锁的方

56、法是使四个必要条件中的第预防死锁的方法是使四个必要条件中的第2、3、4条件之一不能成立，来避免发生条件之一不能成立，来避免发生死锁。至于必要条件死锁。至于必要条件1，因为它是由设备，因为它是由设备的固有属性所决定的，不仅不能改变，还的固有属性所决定的，不仅不能改变，还应加以保证。应加以保证。系统规定所有进程在开始运行之前，都必须系统规定所有进程在开始运行之前，都必须一次性地申请其在整个运行过程所需的全部一次性地申请其在整个运行过程所需的全部资源资源。从而进程在整个运行期间，便不会再提出资从而进程在整个运行期间，便不会再提出资源要求，从而摒弃了请求和保持条件，由此源要求，从而摒弃了请求和保持条件

57、，由此可以避免发生死锁。可以避免发生死锁。优点：优点：简单、易于实现且很安全。简单、易于实现且很安全。缺点：缺点：资源被严重浪费，使进程延迟运行。资源被严重浪费，使进程延迟运行。 v 1）摒弃）摒弃“请求和保持请求和保持”条件条件当一个已经保持了某些资源的进程，再提出新的资当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足时，源请求而不能立即得到满足时，必须释放它已经保必须释放它已经保持了的所有资源。待以后需要时再重新申请持了的所有资源。待以后需要时再重新申请。从而。从而破坏破坏了了“不剥夺不剥夺”条件条件。缺点：这种预防死锁的方法，实现起来比较复杂且缺点：这种预防死锁的方法

58、，实现起来比较复杂且要付出很大代价。因为一个资源在使用一段时间后，要付出很大代价。因为一个资源在使用一段时间后，它的被迫释放可能会造成前段工作的失效。还会使它的被迫释放可能会造成前段工作的失效。还会使进程前后两次运行的信息不连续。进程前后两次运行的信息不连续。 这种方法中规定，系统将所有资源按类型这种方法中规定，系统将所有资源按类型进行线性排队，并赋予不同的序号。进行线性排队，并赋予不同的序号。 所有所有进程对资源的请求必须严格按照资源序号进程对资源的请求必须严格按照资源序号递增的次序提出。递增的次序提出。当进程以及获取资源当进程以及获取资源Ri，当且仅当，当且仅当F（Rj）F(Ri)时，才允

59、许其申请资源时，才允许其申请资源Rj。这样，在所形成的资源分配图中，不可能这样，在所形成的资源分配图中，不可能再出现环路，因而再出现环路，因而摒弃了摒弃了“环路等待环路等待”条条件件。 避免死锁与预防死锁的方法不同，不是实现避免死锁与预防死锁的方法不同，不是实现采取某种限制措施，破坏产生死锁的必要条采取某种限制措施，破坏产生死锁的必要条件，而是在资源动态分配过程中，防止系统件，而是在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁。进入不安全状态，以避免发生死锁。1安全状态安全状态所谓安全状态，是指系统能按某种进程顺序，如所谓安全状态，是指系统能按某种进程顺序，如，依次为，依次为n个

60、进程分配其所需资个进程分配其所需资源，直至其最大需求，使每个进程都可顺利地完成，源，直至其最大需求，使每个进程都可顺利地完成，称系统处于安全状态。称系统处于安全状态。称称P1，P2，Pn序列为安全序列。否则，序列为安全序列。否则，如如果系统无法找到这样一个安全序列，则称系统处于果系统无法找到这样一个安全序列，则称系统处于不安全状态不安全状态。 进程进程最大需最大需求求已分配已分配还需要还需要可可用用P11055 3P2422P3927 所以所以时刻，不能满足时刻，不能满足P3的请求。的请求。避免死锁的关键在于避免死锁的关键在于如何准确的预测是否如何准确的预测是否会出现死锁，从而避免死锁。会出现死锁，从而避免死锁。最有代表性