操作系统-第三章处理器调度20160930

调度是系统将计算机资源分配给进程。在单道程序环境下，只有一个进程存在，计算机的所有资源由一个进程独占，没有资源竞争问题。在多道程序环境下，多个进程并发运行，各进程之间存在资源的相互竞争，特别是对处理器资源的竞争，从而影响到系统性能。处理器调度指在多道程序环境下将处理器分配给各进程。在处理器调度中，合理的调度算法能够提高处理器的处理能力和系统性能，满足用户需求。第3章处理机调度与死锁2/136第3章处理机调度与死锁3.1处理机调度的基本概念3.2调度算法3.3实时调度3.4多处理机系统中的调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测和解除3.1处理器调度的层次在内存中并发的进程之间构成的是一种竞争使用处理器的关系。低级调度将处理器分配给进程。低级调度受到内存中用户作业数的影响，处理器调度不只是低级调度问题，还与内存中能够接纳用户作业的个数有关，与作业调度有关，作业调度为高级调度。为了减轻内存的负担，外存作为内存的补充，进程可以在外存与内存之间对换。对换到外存的进程调入内存为中级调度，中级调度也会影响内存中进程的调度，处理器调度与中级调度有关。3.1处理器调度的层次处理器调度划分为3个层次：高级调度、中级调度和低级调度。进程调度是处理器调度的核心。用户作业从提交给系统开始，直到运行结束退出系统为止，将经历高级调度、中级调度和低级调度。3.1.1高级调度

1．作业及作业分类

作业由一组统一管理和操作的进程集合构成，是用户要求计算机系统完成的一项相对独立的工作。作业可以是完成了编译、链接之后的一个用户程序，也可以是用各种命令构成的一个脚本。根据需要处理工作的类型，作业分为计算型作业和I/O型作业。在操作系统中，将需要CPU处理为主的作业称为计算型作业；将以I/O过程为主的作业称为I/O型作业。一般情况下，操作系统管理会对这两种作业进行区别对待：I/O为主的作业，由于等待I/O过程需要更多的时间，执行更慢；计算型为主的作业等待I/O过程需要的时间更短，执行更快。3.1.1高级调度

作业也可以按照提交方式不同分为批处理作业和终端型作业。在多道程序环境下，用户的批处理作业被提交到系统的磁盘上，以批处理后备队列的形式进行组织，这样的作业为批处理作业。批处理作业需要作业调度将后备队列上的作业调度到内存才能执行。对终端型作业用户通过终端登录到系统，直接将作业置于内存中。终端型作业不需要作业调度便能执行。3.1.1高级调度（续）作业调度按照操作系统预先规定的作业调度策略，从磁盘的作业后备队列中选择作业调入内存，为作业分配所需要的资源并建立与作业相对应的进程。当作业运行的准备工作完成后，作业调度启动作业运行。在作业运行结束后，作业调度归还并释放作业占用的资源，结束作业。作业调度也称为高级调度或长程调度。作业调度模型如图3.1所示。图3.1作业调度模型提交作业后备队列用户作业进程就绪队列处理器进程阻塞队列高级调度终端交互用户3.1.1高级调度（续）作业与进程之间存在着紧密的关系：一个作业可能由一个进程组成，运行在一个进程下；也可能由多个进程组成，运行在多个进程下。作业是计算机处理任务的实体，进程是计算机处理任务的执行体。没有作业，进程无事可做；没有进程，作业不能完成。一个作业中创建多少个进程，有多少个进程运行由作业的拥有者根据需要决定。一个系统能够接纳作业的个数由系统的资源决定，特别是处理器和内存资源。一个系统能够接纳作业的个数称为系统的多道度，也称为系统的多道程序度。3.1.1高级调度（续）当内存中运行的作业太多时，会影响到系统的服务质量，影响到程序的正常执行。操作系统为了保证进入系统的用户作业能够顺利运行，会限制系统的多道度。当多道度达到限值时，只有完成一个作业后另一个作业才能进入。3.1.1高级调度（续）作业调度中操作系统需要完成的工作：确定作业的数据结构。操作系统为每个进入系统的作业分配一个与进程控制块（PCB）类似的作业控制块（JCB），作业控制块中包括：作业的名称、作业对资源的需求信息、作业的资源使用信息、作业的控制方式、作业类型、作业优先级和作业状态。作业控制块是作业的标志，存在于作业的整个过程中，只有作业完成或退出系统时，作业控制块才被撤销。操作系统根据作业控制块中的信息对作业进行调度和管理。作业名称由用户提供，系统将其写到作业控制块中。3.1.1高级调度（续）作业对资源的需求信息包括估计作业执行时间、作业最迟完成时间、作业要求的内存量、作业要求输入输出设备的类型和台数、作业要求的文件量和输出量，这些信息由用户提供。作业的资源使用信息包括作业进入系统时间、作业开始执行时间、作业已经执行时间、作业在内存中的地址、作业被分配的输入输出设备台号，这些信息由操作系统写入。作业的控制方式分为联机和脱机两种，表示该作业是联机操作还是脱机操作。作业类型分为CPU繁忙型作业和I/O繁忙型作业，或批处理输入作业和终端作业。3.1.1高级调度（续）作业优先级反映作业运行的紧急程度，可由用户指定，也可由系统根据作业类型、作业对资源的需求、作业要求的运行时间和系统当前状况动态指定。作业状态指作业当前所处的状态，可分为提交状态、后备状态、运行状态及完成状态。当作业运行结束时，首先释放作业所占用的全部资源，再由作业调度程序调用存储器管理程序收回该作业的作业控制块空间，从而撤销作业。确定作业的调度算法。操作系统调度程序在调度作业前需要确定作业的调度算法，然后再按照确定的作业调度算法从磁盘的作业后备队列中选择作业进入内存。3.1.1高级调度（续）为作业分配资源。作业运行需要各种资源，包括硬件资源和软件资源。硬件资源有内存、处理器和各种输入输出设备。软件资源有各种共享变量等。作业的资源分配策略主要考虑的是作业所包含的进程所需要的资源，在一般情况下，资源按照进程需求进行分配。资源分配中需要避免由进程之间的资源竞争而造成的死锁等现象。回收作业资源。作业完成后，作业调度程序除了要输出相关的作业信息之外，还要回收作业所占用的全部资源，撤销与作业相关的进程和作业控制块。3.1.1高级调度（续）在作业调度工作中，大多数工作由作业的调度程序完成。但是，内存和输入输出设备的分配和释放不是由作业调度程序完成，而是由存储器管理和设备管理程序完成的。作业调度程序只是将作业对内存的要求和对设备的要求转交给相应的内存管理程序和设备管理程序，由内存管理程序和设备管理程序完成内存和设备的分配与回收。3.1.1高级调度（续）3．作业的状态为了更好地描述作业，可以将作业分为不同的状态。作业的状态包括：提交状态、后备状态、执行状态和完成状态。提交状态:用户将作业提交给操作系统，等待输入程序和数据到磁盘。后备状态:系统接收输入的用户作业，并将其放入计算机磁盘。作业在磁盘上以后备队列形式进行组织，等待作业调度程序将作业调度到内存。执行状态:作业被调度到内存，为作业分配资源并为其创建与之对应的进程，进程获得CPU，开始运行。3.1.1高级调度（续）完成状态:从作业的第一个进程完成开始，直到作业所有的进程完成，释放作业所占用的资源，退出系统的整个进程。作业状态及其转换如图3.2所示。执行状态就绪运行阻塞后备状态提交状态完成状态图3.2作业状态及其转换3.1.1高级调度（续）作业状态的划分比进程状态的划分更粗，进程是作业全部状态中的一个阶段体现。作业调度将作业从后备状态转换到内存执行状态。作业执行状态包含作业所对应进程的就绪、运行和阻塞状态。在分时操作系统和实时操作系统中，终端用户的作业直接送入到内存，不需要作业调度。操作系统需要完成的功能是决定是否能够为作业创建进程。分时操作系统和实时操作系统也支持批处理作业，在批处理作业存在时，也能够完成作业调度。3.1.2中级调度

中级调度又称为中程调度，是为了提高内存利用率和平衡系统负载而采取的一种利用外存补充内存的措施。在多进程环境下，内存中的多个进程，其中有些进程可能需要挂起，这些进程暂时不参与对处理器的竞争。为了充分利用内存资源，系统会采用进程对换的方法将进程换出到外存，将这些进程占用的内存空间释放，让内存能够接纳新的进程或使得内存中的进程能够更快推进。当被换出到外存中的进程挂起时间到时，又需要将这些进程换入到内存。中级调度是在换出内存的进程中确定需要进入内存的进程。3.1.2中级调度

当进程需要换入内存，而内存资源不充足时，则系统需要选择内存中的进程换出外存，让出内存空间给进入内存的进程。中级调度根据内存中能够接纳的进程数来平衡系统负载，起到在一定时间内平滑和调整系统负载的作用。1．低级调度低级调度又称为进程调度、短程调度，是按照一定的调度算法从内存的就绪进程队列中选择进程，为进程分配处理器。进程调度发生在内存中的就绪进程，被调度的进程从内存就绪到处理器中执行的过程，该过程很短，被称为短程调度。中级调度位于高级调度与低级调度之间，被称为中程调度。中级调度主要用于内存管理，特别是虚拟存储器管理。3.1.3低级调度

作业调度发生进程位于外存与进入计算机内存之间，经过的过程最长，因此，作业调度被称为长程调度。进程调度与作业调度和中级调度比较，进程调度发生的频率最高，作业调度发生的频率最低。3.1.3低级调度

处理器调度的三级模型如图3.3所示。3.1.3低级调度图3.3处理器三级调度模型进程挂起就绪队列进程阻塞队列进程挂起阻塞队列进程就绪队列完成中级调度低级调度处理器高级调度作业后备队列交互式用户提交用户作业3.1.3低级调度（续）2．引起进程调度的主要原因

（1）处理器执行的进程完成任务，处理器空闲；（2）处理器执行的进程转入阻塞状态，此时处理器空闲；（3）处理器执行的进程被其它进程抢占；（4）处理器执行的进程被挂起。3.1.3低级调度（续）3．进程调度中的基本机制（1）排队器。为使进程调度时能够快速有效地找到就绪队列中的每个进程，首先应该按照一定的方式将进程就绪队列排成一个或多个队列。（2）分派程序。分派程序将根据进程调度策略将所选中的进程从就绪队列中移出，然后进行进程上下文的切换，并将处理器分配给进程。（3）上下文切换机制。上下文切换机制是指在操作系统分派程序的执行下完成处理器的切换过程，实现进程上下文切换3.1.3低级调度（续）4．进程切换的实现进程切换需要完成进程上下文切换，进程状态、进程等待时间等信息的改变。新、老进程切换如图3.4所示。老进程新进程CPU图3.4进程调度中的进程切换进程切换过程描述？3.1.3低级调度（续）进程切换需要完成以下工作：保存并恢复处理器信息。处理器中的寄存器保存了当前正在执行进程的相关数据和状态，在进程被切换时，必须将进程的这些信息保存到进程控制块中，以便进程被处理器再次执行时，能够将进程的断点信息从进程控制块拷贝回处理器寄存器中，保证处理器能够从进程的上次断点开始继续向前推进。处理器中寄存器信息写到老进程的进程控制块中，新进程的进程控制块信息被拷贝到处理器的寄存器中。3.1.3低级调度（续）更新进程控制块中的进程状态、进程达到时间、进程等待时间、进程优先级变化等信息，并将进程控制块移到相应的进程队列。被切换的进程状态从执行改为就绪或阻塞，其进程控制块也被插入就绪队列或阻塞队列。同样，被分配处理器的进程，其状态从就绪改为执行，进程控制块从就绪队列中移出。更新存储器管理数据结构，维护进程的代码段和数据段。3.1.3低级调度（续）5．进程调度中的非抢占（nonpreemptive）调度和抢占（preemptive）调度

非抢占式调度是一种通常的调度方式，在非抢占调度中，处理器分配给进程后，一直到进程结束或进程阻塞，进程才自动放弃处理器。非抢占调度存在什么问题？若执行进程正好在执行一个没有资源的无限循环，则执行进程不会放弃处理器，所有的就绪进程会永久等待，系统进入了一种僵持的状态。解决方法?如果此时系统能够自身定期强制执行进程中断，则可以避免这种僵持状态。3.1.3低级调度（续）强制执行进程中断的调度方式为抢占调度方式，又称为剥夺调度方式，是指一个进程正在处理器中运行时，操作系统可以根据规定的抢占原则，将已经分配给进程的处理器从进程剥夺，并分配给其他的进程。在系统允许抢占调度，并满足抢占条件的情况下，系统才可以采用抢占调度方式。满足抢占条件的进程能够抢占当前正在执行进程的处理器。被抢占的进程状态从执行状态变为就绪状态，其进程控制块进入到进程就绪队列。3.1.3低级调度（续）具有抢占的进程状态如图3.5所示。图3.5进程的抢占与非抢占调度阻塞态就绪态运行态终止态抢占非抢占进程调度非抢占3.1.3低级调度（续）抢占条件也称为抢占原则，可归纳为如下：时间片在分时系统中，当进程运行的时间片到时，进程会被抢占，处理器被分配给其他的就绪进程。分时操作系统采用了基于时间片的抢占调度方法，如UNIX操作系统和Linux操作系统。优先级当就绪队列上有优先级比当前正在处理器运行的进程的优先级高的进程时，系统将处理器从当前进程剥夺，优先级高的进程得到处理器。基于优先级的进程抢占调度被很多操作系统所采用，特别是实时操作系统。在UNIX操作系统中，当用户态进程完成系统调用后从核心态返回用户态继续运行时，处理器可能被处于核心态执行的其他进程抢占。3.1.3低级调度（续）短进程当就绪队列中有进程的执行时间比当前正在处理器运行的进程需要的执行时间更短时，当前进程被抢占，系统将处理器分配给更短的进程。抢占是一种灵活和有效的处理进程调度方法，避免了进程永远不放弃处理器的现象，也为紧急情况下的进程运行创造了机会。3.1.3低级调度（续）抢占带来的问题：增加系统开销进程间共享数据不一致问题在进程之间存在数据共享时，如果一个进程的数据更新尚未结束而被抢占，得到处理器的进程恰好又要读取这部分共享数据，此时读取的数据可能存在不一致的问题。这样，操作系统必须采取一定的措施保证数据的一致性。影响操作系统内核程序设计问题如果抢占发生在操作系统内核程序执行期间，如系统调用期间，核心程序可能正在改变核心中的重要数据时被抢占，从而造成操作系统核心出现问题，影响系统的稳定性。3.1.3低级调度（续）在操作系统设计时应考虑避免核心调用时被抢占的情况。如UNIX操作系统在设计时规定系统调用期间不能抢占。内核程序执行时不能被抢占又影响系统实时性，特别是在此期间系统不能接收中断，造成输入信息丢失，输出信息被重写。UNIX、Linux、微软公司的Windows操作系统、苹果公司的MacOS都采用了抢占调度方式。3.2评价调度算法的准则

处理器调度算法也称为调度策略，用于控制对处理器的分配，是处理器调度中非常重要的环节。不同的调度策略，对系统性能的影响不同。适合操作系统的调度算法，能够提高系统的性能。评价调度算法从系统性能、用户满意两方面进行考虑，充分体现对用户的公平性和系统的高效性，既保证每个用户有合理的处理器时间，又保证系统的处理器利用率高。3.2评价调度算法的准则（续）评价调度算法的准则如下：处理器利用率（CPUutilization）处理器利用率为CPU有效工作时间与CPU总的运行时间之比，即：CPU利用率

=

CPU有效工作时间/CPU总的运行时间

CPU总的运行时间

=

CPU的有效工作时间

+

CPU的空闲时间思考：理想情况下CPU的利用率是多少？100%实际应用中，总会存在进程切换等工作，而进程切换需要时间。对于轻负载系统，CPU的利用率大约为40%；对于重负载系统，CPU的利用率最高可达90%。3.2评价调度算法的准则（续）响应时间（responsetime）响应时间是交互环境下用户从键盘提交第1个请求开始，到系统首次产生响应为止的时间，或者是屏幕上显示出结果为止的时间。响应时间

=

从终端键盘输入的请求信息传送到处理机的时间

+

处理机对请求信息的处理时间

+

生成的响应信息回送到终端显示器的时间对于用户来讲，希望响应时间越短越好。3.2评价调度算法的准则（续）周转时间（turnaroundtime）周转时间指用户作业提交给操作系统开始到作业完成为止的时间。周转时间Ti

=

作业在后备队列中的等待调度时间+进程在就绪队列上等待调度的时间+进程在CPU上的运行时间

+

进程等待I/O或其他事件发生的时间带权周转时间带权周转时间Tf

=

作业的周转时间Ti/系统为作业提供的服务时间Tsi

每个用户都希望自己作业的周转时间越短越好，计算机系统管理希望所有作业的平均周转时间越短越好，带权周转时间越短越好。3.2评价调度算法的准则（续）系统吞吐量（throughput）单位时间内处理的进程数目为CPU的工作成效。单位时间内完成的进程数目为系统的吞吐量。在处理大而长的进程时，吞吐量可能每小时只有一个；在处理小而短的进程时，吞吐量达到每秒几十甚至上百个。在选择处理器的调度算法时，用户希望CPU利用率和系统吞吐量越大越好，响应时间和周转时间越小越好。对于实时系统，作业调度的关键在于能否满足作业的实时要求，对周转时间等指标并不特别着重。40/1363.3调度算法学习目标：熟练掌握常见的调度算法，明确各调度算法的优缺点。学习难点：理解各调度算法的思想，将算法在实践中灵活应用。41/136先来先服务算法(FirstComeFirstServed)最短作业优先算法(ShortestJobFirst)最高响应比优先算法(HighestResponseRatioFirst)基于时间片的调度算法

时间片轮转(Round-Robin)

多队列反馈调度算法(MultilevelFeedback)

3.3.1主要的调度算法42/136算法基本思想：按照作业进入系统的先后次序来挑选作业，先进入系统的作业优先被挑选。3.3.2先来先服务算法（FirstComeFirstServed）12345cpu43/136算法基本思想：按照作业进入系统的先后次序来挑选作业，先进入系统的作业优先被挑选。3.2.2先来先服务算法（FirstComeFirstServed）12345cpu44/136算法举例：（单位:小时，以十进制计）作业提交时间运行时间开始时间完成时间周转时间带权周转时间A06B13C25D32平均周转时间t=平均带权周转时间w=06616982.67914122.41416136.59.753.14=完成时间-提交时间=周转时间/运行时间45/136算法优缺点：算法容易实现；适用于作业调度和进程调度；效率不高，只顾及作业等候时间，没考虑作业要求服务时间的长短；不利于短作业。46/136算法思想应用：日常生活中先来先服务思想的应用47/136思考：一批作业几乎同时提交，(有先后顺序，但相差时间可忽略)如果作业提交的次序发生改变，结果会发生变化吗？(一个进程所需的CPU时间分别为28、9、3)48/136A(28)B(9)C(3)283740A(28)B(9)C(3)91240A(28)B(9)C(3)312403520.318.349/136算法基本思想：

SJF算法以进入系统的作业所要求的CPU时间为标准，总选取估计计算时间最短的作业投入运行。3.3.3最短作业优先算法（ShortestJobFirst）12345cpu50/136算法基本思想：

SJF算法以进入系统的作业所要求的CPU时间为标准，总选取估计计算时间最短的作业投入运行。3.3.3最短作业优先算法（ShortestJobFirst）12345cpu51/136算法举例：（单位:小时，以十进制计）作业提交时间运行时间开始时间完成时间周转时间带权周转时间A06B13C25D32平均周转时间t=平均带权周转时间w=0661811103.31116142.86852.58.752.4FCFSt=9.75w=3.14结论：SJF的平均作业周转时间比FCFS要小，故它的调度性能比FCFS好=完成时间-提交时间=周转时间/运行时间52/136算法优缺点：算法容易实现；适用于作业调度；能有效降低作业的平均等待时间；忽视了作业等待时间，对长作业不利，有可能导致长作业（进程）长期不被调度（出现饥饿现象）；要精确知道一个作业的运行时间比较困难的。53/136算法思想应用：厨师做菜次序的安排54/136课后思考：如采用最短剩余时间优先算法SRTF（ShortestRemainingTimeFirst），情况将如何变化。作业提交时间运行时间A06B13C25D3255/136作业提交时间运行时间首次开始首次完成再次开始再次完成周转时间带权周转A06B13C25D32平均周转时间t=平均带权周转时间w=01144661111161131431.8312.81.57.751.5356/1363.3.4最高响应比优先（HighestResponseRatioFirst）优先权的类型：静态优先权—在创建进程时确定的，且在进程的整个运行期间保持不变。动态优先权—在创建进程时赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变。57/136最高响应比优先（HighestResponseRatioFirst）响应比概念：公式理解：等待时间相近，服务时间越短，优先权越高SJF服务时间相近，等待时间越长，优先权越高FCFS算法基本思想：

HRRF算法在当前作业执行完时,计算剩余作业的响应比，选取响应比最高的作业投入运行。58/136举例：以下四个作业先后到达系统进入调度：

开始只有作业1，被选中执行时间20ms；作业1执行完毕，响应比依次为1+15/15、1+10/5、1+5/10，作业3被选中，执行时间5ms；作业3执行完毕，响应比依次为1+20/15、1+10/10，作业2被选中，执行时间15ms；作业2执行完毕，作业4被选中，执行时间10ms；平均作业周转时间T=(20+15+35+35)/4=26.25平均带权作业周转时间W=(20/20+15/5+35/15+35/10)/4=2.4659/136算法优缺点：

算法适用于作业调度；既考虑作业等待时间，又考虑作业的运行时间；既照顾短作业又不使长作业的等待时间过长;

计算响应比需要耗费时间。60/136算法思想应用：义诊就医次序安排61/136算法基本思想：

系统按照固定的时间片依次轮流执行就绪队列中的各个进程。3.3.5时间片轮转法（Round-Robin)ABCD62/136算法举例：有三个进程P1、P2、P3先后到达，它们分别需要20、4和2个单位时间运行完毕。假如它们按P1、P2、P3的顺序执行，且不可剥夺，则三进程各自的周转时间、平均周转时间是多少个时间单位。假如它们按P1、P2、P3的顺序执行，且不可剥夺，则三进程各自的周转时间分别为20、24、26个单位时间，平均周转时间是23.33个时间单位。63/136算法举例：有三个进程P1、P2、P3先后到达，分别需要20、4和2个单位时间运行完毕，假如用时间片轮转原则的剥夺调度方式，时间片为2个时间单位。则各进程的周转时间和平均周转时间。02468101214161820222426p1p2p3p1p2p1p1p1p1p1p1p1p1P1、P2、P3的周转时间分别为26、10、6平均周转时间为（26+10+6）/3=1464/136算法优缺点：

算法主要针对分时系统，适用于进程调度；对用户的响应及时、快速；时间片的长度确定比较困难；进程切换开销比较大。65/136算法思想应用：驾校培训安排66/136回顾与总结

算法FCFSSJFHRRFRR

项目适用范围抢占性优点缺点作业、进程作业作业进程非抢占两者均可非抢占抢占简单利于短作业均衡调度响应及时无视特殊要求易导致饥饿计算耗时切换开销大67/136算法基本思想：将就绪队列分为N级，每个就绪队列分配给不同的时间片，队列优先权越高,为每个进程所规定的执行时间片就越小；系统从第一级调度，当第一级为空时，系统转向第二个队列，.....当运行进程用完一个时间片，放弃CPU时，进入下一级队列；等待进程被唤醒时，进入原来的就绪队列；当进程第一次就绪时，进入第一级队列。3.2.5.2多队列反馈调度算法68/136首先系统中设置多个就绪队列；每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大；各个队列按照先进先出调度算法；一个新进程就绪后进入第一级队列；进程由于等待而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列；当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到原来一级就绪队列末尾；当第一级队列空时，就去调度第二级队列，如此类推；当时间片到后，进程放弃CPU，回到下一级队列。算法步骤：69/136多队列反馈调度算法模型70/1363.2.6引起进程调度的原因正在执行的进程执行完毕或因发生某事件而不能再继续执行；执行中的进程因提出I/O请求而暂停执行；在进程通信或同步过程中执行了某种原语操作如P操作、阻塞、挂起原语等；在可剥夺式调度中，有比当前进程优先权更高的进程进入就绪队列；在时间片轮转法中，时间片完。71/1363.2.7进程调度算法其中，RQ为就绪队列指针，EP为运行队列指针。72/136第3章处理机调度与死锁3.1处理机调度的基本概念3.2调度算法3.3实时调度3.4多处理机系统中的调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测和解除73/1363.3实时调度

3.3.1实现实时调度的基本条件

提供必要的信息(就绪时间、截止时间、处理时间、资源优先级)；系统处理能力强；采用抢占式调度机制；具有快速切换机制。74/1363.3.2实时调度算法的分类非抢占式调度算法非抢占式轮转调度算法非抢占式优先调度算法抢占式调度算法基于时钟中断的抢占优先调度算法立即抢占优先权调度算法75/136图3-5实时进程调度76/1363.3.3.1最早截止时间优先即EDF(EarliestDeadlineFirst)算法

图3-6EDF算法用于非抢占调度方式3.3.3常用的几种实时调度算法

77/1363.3.3.2最低松弛度优先(LLF)算法

该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级。该算法主要用于可抢占调度方式中。假如在一个实时系统中，有两个周期性实时任务A和B，任务A要求每20ms执行一次，执行时间为10ms；任务B只要求每50ms执行一次，执行时间为25ms。

图3-7A和B任务每次必须完成的时间78/136

在刚开始时(t1=0)，A1必须在20ms时完成，而它本身运行又需10ms，可算出A1的松弛度为10ms；B1必须在50ms时完成，而它本身运行就需25ms，可算出B1的松弛度为25ms，故调度程序应先调度A1执行。在t2=10ms时，A2的松弛度可按下式算出：A2的松弛度=必须完成时间-其本身的运行时间-当前时间

=40ms-10ms-10ms=20ms

类似地，可算出B1的松弛度为15ms，调度程序应选择B2运行。t3=30ms时，A2的松弛度已减为0，B1的松弛度为15ms，于是调度程序应抢占B1的处理机而调度A2运行…….79/136图3-8利用ELLF算法进行调度的情况t1=0时：A1的松弛度=必须完成时间-其本身的运行时间-当前时间

=20ms-10ms-0ms=10msB1的松弛度=必须完成时间-其本身的运行时间-当前时间

=50ms-25ms-0ms=25ms01020304050607080A1t2=10时：A2的松弛度=必须完成时间-其本身的运行时间-当前时间

=40ms-10ms-10ms=20msB1的松弛度=必须完成时间-其本身的运行时间-当前时间

=50ms-25ms-10ms=15msB1(20)t3=30时：A2的松弛度=必须完成时间-其本身的运行时间-当前时间

=40ms-30ms-10ms=0msB1的松弛度=必须完成时间-其本身的运行时间-当前时间

=50ms-5ms-30ms=15msA2t4=40时：A3的松弛度=必须完成时间-其本身的运行时间-当前时间

=60ms-10ms-40ms=10msB1的松弛度=必须完成时间-其本身的运行时间-当前时间

=50ms-5ms-40ms=5msB1(5)A3B2(15)A4B2(10)9080/136图3-8利用ELLF算法进行调度的情况81/136第3章处理机调度与死锁3.1处理机调度的基本概念3.2调度算法3.3实时调度3.4多处理机系统中的调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测和解除82/1363.4多处理机系统中的调度

MPS——MultiProcessorSystem

3.4.1紧密耦合MPS和松弛耦合MPS

1.紧密耦合MPS

通过高速总线或高速交叉开关连接多个处理器，多个CPU共享主存储器和I/O设备，系统中的所有资源和进程由操作系统统一控制和管理

2.松弛耦合MPS

通过通道或通信线路连接多个计算机，每个计算机都有自己的存储器和I/O设备，都有自己的操作系统控制和管理本地资源和进程的运行(——计算机网络)83/1363.4.2对称MPS和非对称MPS

根据处理器是否相同来划分。

1.对称MPS——SMPS

系统中的处理器在结构和功能上都相同。

2.非对称MPS

系统中有多种类型的处理器，它们的结构和功能各不相同。其中一个是主处理器，其余都是从处理器。84/136

一）对称多处理器系统中的进程分配方式

1.静态分配方式进程从开始执行到执行结束，都被固定地分配到一个处理器。每个此类系统一般采用主从式操作系统，即OS的核心驻留于主处理器中，而用户程序则在从处理器上，进程调度由主处理器执行。每当从处理器空闲时，就向主处理器发送一个索求进程的信号，主处理器从公用就绪队列中进行进程调度处理器有一个专用的就绪队列，被阻塞的进程再次就绪时，仍回到该队列的末尾。

2.动态分配方式系统中可以只设置一个公共的就绪队列，其中的进程可以分配到系统中的任何一个处理器。3.4.3进程分配方式85/136

二）非对称MPS中的进程分配方式此类系统一般采用主从式操作系统，即OS的核心驻留于主处理器中，而用户程序则在从处理器上，进程调度由主处理器执行。每当从处理器空闲时，就向主处理器发送一个索求进程的信号，主处理器从公用就绪队列中进行进程调度。86/136一）自调度方式

1.自调度机制在系统中设置一个公共的进程(线程)就绪队列，所有的处理器空闲时，都可以自己到该队列中取得一个进程(线程)投入运行

(1)FCFS算法

(2)最小优先数优先算法

(3)抢占式最小优先数优先算法3.4.4进程(线程)调度方式87/1362.自调度方式的特点有任务的情况下处理机不会空闲分布式调度可以沿用单处理机环境下的就绪队列组方式织和进程调度方法多处理机互斥共享单就绪队列引起的瓶颈重新调度时线程迁移引起的低效性线程切换频繁88/136二）成组调度

1.基本原理把一个进程中的一组线程分配到一组处理机上执行。其优点是：

(1)若一组线(进)程可以并行执行，就可以减少阻塞情况的发生，减少了切换频率，提高了性能

(2)一次调度为一组线程分配处理机，减少了调度频率，减少了系统开销2.为应用程序分配处理机时间的方法

1)为所有的应用程序平均分配处理机时间

2)为所有的线程平均分配处理机时间89/136

1.基本原理为一个应用程序的每个线程分配一个处理器，直到该应用程序执行完毕，才释放为该应用程序所分配的所有处理器。3.4.5专用处理器分配2.采用专用处理器分配方法的理由

1)专用处理器分配方式的缺点部分处理器的利用率可能不高

2)仍然采用专用处理器分配方式的原因

(1)在大规模(甚至几百个处理器)高度并行的系统中，单个处理器的利用率不那么重要；

(2)避免了线程切换，加速了程序运行。90/136讨论与练习91/136第3章处理机调度与死锁3.1处理机调度的基本概念3.2调度算法3.3实时调度3.4多处理机系统中的调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测和解除92/1363.5.1死锁的概念1.死锁例子:(deadlock)一个由于申请不同类型资源而产生死锁的例子设系统有一台打印机(R1)一台扫描仪(R2)，两进程共享这两台设备。用信号量S1表示R1是否可用，用信号量S2表示R2是否可用，S1、S2初值为1。

93/1363.5.1.1死锁概念指多个进程因竞争共享资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。即：一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。94/136参与死锁的进程最少是两个；参与死锁的进程至少有两个已经占有资源；参与死锁的所有进程都在等待资源；参与死锁的进程是当前系统中所有进程的子集。注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。3.5.1.2关于死锁的一些结论95/136永久性资源：可以被多个进程多次使用（可再用资源）可抢占资源(处理机,主存)不可抢占资源(打印机,磁带机)临时性资源：只可使用一次的资源；如信号量,中断信号，同步信号等（可消耗性资源）“申请--分配--使用--释放”模式3.5.1.3永久性资源和临时性资源96/1363.5.2产生死锁的原因1.竞争系统资源当系统中供多个进程共享的资源数目不足以满足诸进程的需要时,会引起进程对资源的竞争而产生死锁。2.进程的推进顺序不当进程在运行过程中,请求和释放资源的顺序不当,也可能造成进程死锁。97/1361.竞争系统资源

若系统中只有一台打印机R1和一台读卡机R2，可供进程P1和P2共享。若形成环路，这样会产生死锁。98/136有环有死锁99/136有环无死锁100/1362.进程的推进顺序不当在进程P1和P2并发执行时，按照左图曲线①②③所示顺序推进时，两进程会顺利完成，我们称这种推进顺序是合法的。若按曲线④的顺序推进时，进入不安全区D内，两进程再推进会产生死锁。P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)③④③③③②②①①进程P1、P2并发执行。资源R1、R2曲线4将进入不安全区域（进程推进顺序非法）102/136互斥使用：在一段时间内，一个资源只能由一个进程独占使用，若别的进程也要求该资源，则须等待直至其占用者释放；保持和等待：允许进程在不释放其已分得资源的情况下请求并等待分配新的资源；非剥夺性：进程所获得的资源在未使用完之前，不能被其它进程强行夺走，而只能由其自身释放；循环等待：存在一个等待进程集合，P0正在等待一个P1占用的资源，P1正在等待一个P2占用的资源，…，Pn正在等待一个由P0占用的资源。3.5.3产生死锁的必要条件103/136预防死锁：通过设置某些限制条件，破坏产生死锁的四个必要条件中的一个或者几个，预防死锁。避免死锁：在资源的动态分配过程中，用某种方法防止系统进入不安全状态，避免死锁。检测死锁：检测死锁的发生，确定与死锁有关的进程与资源，采取措施，从系统中将已发生的死锁清除。解除死锁：通过撤消和挂起一些进程，回收一些资源，分配给处于阻塞状态的进程，使之转为就绪状态。3.5.4解决死锁的基本办法104/136第3章处理机调度与死锁3.1处理机调度的基本概念3.2调度算法3.3实时调度3.4多处理机系统中的调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测和解除105/1363.6预防死锁的方法和避免死锁

在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一。资源一次性分配；(破坏请求和保持条件)可剥夺资源；即当某进程新的资源未满足时，释放已占有的资源(破坏不可剥夺条件)资源有序分配法；系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反(破坏环路等待条件)

3.6.1预防死锁的方法106/136死锁避免定义:在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。预防死锁的几种策略，会严重地损害了系统性能。因此要施加较弱的限制，从而获得较满意的系统性能来避免死锁。由于在避免死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，进程等待。其中最具有代表性的避免死锁算法是银行家算法。

3.6.2避免死锁107/136

安全状态指系统能按某种进程顺序来为每个进程分配其所需资源，直至最大需求，使每个进程都可顺序完成。若系统不存在这样一个序列，则称系统处于不安全状态。

3.6.3安全状态与不安全状态108/1361)安全序列概念

一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj(j<i)当前占有资源量之和，系统处于安全状态。

(安全状态一定是没有死锁发生的)109/136

我们通过一个例子来说明安全性。假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示：进程最大需求已分配可用P1P2P3104952232)安全序列举例安全序列（P2,P1,P3)110/136

如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。例如，在T0时刻以后，P3又请求1台磁带机，若此时系统把剩余3台中的1台分配给P3，则系统便进入不安全状态。

因为，此时也无法再找到一个安全序列，例如，把其余的2台分配给P2，这样，在P2完成后只能释放出4台，既不能满足P1尚需5台的要求，也不能满足P3尚需6台的要求，致使它们都无法推进到完成，彼此都在等待对方释放资源，即陷入僵局，结果导致死锁。进程最大需求已分配可用P1P2P3104952233)由安全状态向不安全状态的转换111/136讨论与练习112/136安全状态与不安全状态不安全状态:不存在一个安全序列，不安全状态一定导致死锁113/1363.6.4利用银行家算法避免死锁

1)银行家算法中的数据结构

(1)可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available［j］=K，则表示系统中现有Rj类资源K个。[ə'veiləbəl]

114/136

(2)最大需求矩阵Max。这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max［i,j］=K，则表示进程i需要Rj类资源的最大数目为K。(3)分配矩阵Allocation。这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation［i,j］=K，则表示进程i当前已分得Rj类资源的数目为K。115/136(4)需求矩阵Need。这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need［i,j］=K，则表示进程i还需要Rj类资源K个，方能完成其任务。Need［i,j］=Max［i,j］-Allocation［i,j］

116/136

设Requesti是进程Pi的请求向量，如果Requesti［j］=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查:(1)如果Requesti［j］≤Need［i,j］，便转向步骤2；否则认为出错，因为它所请求的资源数已超过它所宣布的最大值;

(2)如果Requesti［j］≤Available［j］，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。2)银行家算法117/136(3)系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值:

Available［j］∶=Available［j］-Requesti［j］;Allocation［i,j］∶=Allocation［i,j］+Requesti［j］;Need［i,j］∶=Need［i,j］-Requesti［j］;(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。118/1363)安全性算法

(1)设置两个向量：①工作向量Work:它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work∶=Available;②Finish:它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish［i］∶=false;当有足够资源分配给进程时，再令Finish［i］∶=true。119/136(2)从进程集合中找到一个能满足下述条件的进程：①Finish［i］=false;②Need［i,j］≤Work［j］；若找到，执行步骤(3)，否则，执行步骤(4)。(4)如果所有进程的Finish［i］=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。(3)当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

Work［j］∶=Work［j］+Allocation［i,j］;Finish［i］∶=true;gotostep2;120/1364)银行家算法之例

假定系统中有五个进程｛P0,P1,P2,P3,P4｝和三类资源｛A,B,C｝，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图3-15所示。图3-8T0时刻的资源分配表

资源进程MaxAllocationNeedAvailableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P4433002431

资源进程MaxAllocationNeedAvailableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P4433002431

(1)T0时刻的安全性

资源进程WorkNeedAllocationWork+AllocationFinishABCABCABCABCp1332122200532truep3532011211743truep4743431002745truep0745743010755truep27556003021057true122/136(2)P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查：①Request1(1,0,2)≤Need1(1,2,2)②Request1(1,0,2)≤Available1(3,3,2)③系统先假定可为P1分配资源，并修改Available,Allocation1和Need1向量，由此形成的资源变化情况如图3-15中的圆括号所示。④再利用安全性算法检查此时系统是否安全。

资源进程MaxAllocationNeedAvailableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P4433002431Request1(1，0，2)

资源进程MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431

资源进程MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431

资源进程WorkNeedAllocationWork+AllocationFinishABCABCABCABCp1230020302532truep3532011211743truep4743431002745truep0745743010755truep27556003021057true125/136

(3)P4请求资源：P4发出请求向量Request4(3，3，0)

资源进程MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431系统按银行家算法进行检查：①Request4(3,3,0)≤Need

(4,3,1);②Request4(3,3,0)>Available(2,3,0)，让P4等待。126/136(4)P0请求资源：P0发出请求向量Requst0(0，2，0)

资源进程MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431系统按银行家算法检查：①Request0(0,2,0)≤Need

(7,4,3);②Request0(0,2,0)≤Available(2,3,0);③系统暂时先假定可为P0分配资源，并修改有关数据，如下图所示。

Request0(0，2，0)

资源进程MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431

资源进程MaxAllocationNeedAvailableABCABCABCABCP0753030723210P1322302020P2902302600P3222211011P4433002431128/136(5)进行安全性检查:可用资源Available(2,1,0)已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源．如果把P0发出请求向量改为Request0(0,１,0)，系统是否可以将资源分配给它？？？

资源进程MaxAllocationNeedAvailableABCABCABCABCP0753030723210P1322302020P2902302600P3222211011P4433002431Request0(0，1，0)

资源进程MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431

资源进程MaxAllocationNeedAvailableABCABCABCABCP0753020733220P1322302020P2902302600P3222211011P4433002431

资源进程WorkNeedAllocationWork+AllocationFinishABCABCABCABCP0220733020240trueP1240020302542trueP3542011211753trueP4753431002755trueP27