第三章作业、处理机调度

第三章处理机管理教学内容:1、调度的类型和模型、调度算法2、多处理机调度3、线程与进程的区别4、进程的通信5、管程机制6、死锁

在多道程序系统中，一个作业从提交到执行通常要经历多级调度，系统的运行性能在很大程度上取决于调度。CPU调度使得多个进程有条不紊地共享一个CPU。CPU调度为每个用户都提供了一个虚拟处理机。一个好的调度策略对于加快作业总的周转时间、提高单位时间内的作业吞吐量、实现系统总的设计目标十分重要。一、作业的状态及其转换§3.1分级调度进程的三种状态?①提交状态：作业被提交给机房后或用户通过终端键盘想计算机键入其作业时的状态.②后备状态：作业的全部信息都已通过输入机输入，并由操作系统将其存在磁盘的某些分区（存放作业的输入井）中等待运行.③运行状态：作业一旦被作业调度程序选中而被送入主存中投入运行.④完成状态：作业完成其全部运行，释放出其所占用的全部资源。准备退出系统时的作业.二、作业与进程的关系

计算机要完成一个任务实体，必须要有一个以上的执行实体，一个作业总是由一个以上的多个进程组成。作业是用户向计算机提交任务的实体。

进程是计算机为完成用户任务实体而设置的执行实体三、调度的层次

在多道程序环境下，操作系统中面对众多进程，为了提高调度效率，也实行分级调度。高级调度（作业调度、宏观调度、长期调度、收容调度）按一定原则对外存输入井上的作业进行调度，从作业后备队列中选择作业进入主存并建立进程PCB。它决定允许哪些作业竞争系统资、决定哪些作业可以进入系统。低级调度（进程调度、短期调度）决定存在就绪进程时，哪一个就绪进程将分配到中央处理机，并且把中央处理机实际分配给这个进程（即低级调度是将处理机分配给进程）。

低级调度是由每秒可操作许多次的处理机调度程序执行，处理机调度程序应常驻存。仅有进程调度的调度队列模型具有高级和低级调度的调度队列模型中级调度（交换调度、中程调度）

负责进程在内存和辅存对换区间的对换。一些进程处于阻塞状态而暂时不能运行，中级调度将进程暂时移到辅存对换区，对换区的进程若其等待的事件已发生，则它们要由阻塞状态变为就绪，为了继续这些进程的继续进行，则由中级调度再度把它们调入内存。一个进程在其运行期间有可能多次调进调出决定允许哪些进程竞争处理机引入中级调度后，进程的就绪状态分为内存就绪(表示进程在内存中就绪)和外存就绪(进程在外存中就绪)。类似地，也可把阻塞状态进一步分成内存阻塞和外存阻塞两种状态。在调出操作的作用下，可使进程状态由内存就绪转为外存就绪，由内存阻塞转为外存阻塞；在中级调度的作用下，又可使外存就绪转为内存就绪。

具有三级调度时的调度队列模型

作业调度的功能：按某种算法从后备队列中挑选一个或一批作业调入内存，并创建PCB。一、后备作业队列与作业控制块

系统中有若干作业在输入井中，为了管理和调度作业，就必须记录已进入系统的各作业的情况，系统为每个作业设置了一个作业控制块（JCB）。

§3.2作业的调度

作业名

作业类型

资源要求

资源使用情况

优先级

当前状态

其它二、作业控制块JCB三、作业调度应完成的工作①按照某种调度算法从后备作业队列中选取作业。②为被选取的作业分配内存和外设资源（当系统为动态分配外设时，作业所申请的外设只作为调度的参考因素）。因此要用到内存分配程序和外设分配程序。

③为选中的作业建立相应的进程。

④为作业开始运行做好一切准备工作。如构造和读写作业运行时所需要的有关表格及建立负责其运行控制的作业运行控制程序。⑤在作业运行完毕或运行过程中因某种原因需要撤离时，作业调度程序还有完成作业的善后处理工作，如收回分配给他的全部资源，它们将从系统中抹去。四、作业调度目标与转换过程1、调度目标

a.对所有作业应该是公平合理

b.应使设备有高的利用率

c.每天执行尽可能多的作业

d.有快的响应时间

2、作业调度的转换过程

a.作业从后备状态到执行状态

b.作业从执行状态到完成状态

后备作业队列空按调度算法从作业中选出一作业调用存储、设备管理程序，审核资源要求资源要求能满足？放弃该作业否分配资源调用进程管理程序建立进程进程调度否是出口作业从后备状态到执行状态撤销该作业的所有进程及作业的JCB调用存储管理，设备管理回收分配给该作业的全部资源调用会计程序，计算该作业的执行费用调度下一个作业作业从执行状态到完成状态一、低级调度的主要功能如下：(1)保存处理机的现场信息。在进程调度进行调度时，首先需要保存当前进程的处理机的现场信息，如程序计数器、多个通用寄存器中的内容等，将它们送入该进程的进程控制块(PCB)中的相应单元。§3.3进程调度(2)按照某种算法选取进程。低级调度程序按某种算法如优先数算法、轮转法等，从就绪队列中选取一个进程，把它的状态改为运行状态，并准备把处理机分配给它。(3)把处理器分配给进程。由分派程序(Dispatcher)把处理器分配给进程。此时需为选中的进程恢复处理机现场，即把选中进程的进程控制块内,有关处理机现场的信息装入处理器相应的各个寄存器中，把处理器的控制权交给该进程，让它从取出的断点处开始继续运行。

二、进程调度中的三个基本机制

(1)排队器。为了提高进程调度的效率，应事先将系统中所有的就绪进程按照一定的方式排成一个或多个队列，以便调度程序能最快地找到它。(2)分派器(分派程序)。分派器把由进程调度程序所选定的进程，从就绪队列中取出该进程，然后进行上下文切换，将处理机分配给它。

(3)上下文切换机制。当对处理机进行切换时，会发生两对上下文切换操作。在第一对上下文切换时，操作系统将保存当前进程的上下文，而装入分派程序的上下文，以便分派程序运行；在第二对上下文切换时，将移出分派程序，把新选进程的CPU现场信息装入到处理机的各个相应寄存器中。

上下文切换花去不少的处理机时间，每一次上下文切换大约需要花费几毫秒的时间，该时间大约可执行上千条指令。现在已有通过硬件(采用两组或多组寄存器)的方法来减少上下文切换的时间。一组寄存器供处理机在系统态时使用一组寄存器供应用程序使用。这种条件下的上下文切换只需改变指针，使其指向当前寄存器组即可。三、进程调度方式进程调度可采用下述两种调度方式。

1)非抢占方式(NonpreemptiveMode)一旦把处理机分配给某进程后，不管运行多长时间，都让它运行下去，决不会因为时钟中断等原因而抢占正在运行进程的处理机，也不允许其它进程抢占已经分配给它的处理机。直至该进程完成，自愿释放处理机，或发生某事件而被阻塞时，才再把处理机分配给其他进程。

在采用非抢占调度方式时，可能引起进程调度的因素可归结为如下几个：

(1)正在执行的进程执行完毕，或因发生某事件而不能再继续执行；

(2)执行中的进程因提出I/O请求而暂停执行；

(3)在进程通信或同步过程中执行了某种原语操作，如P操作(wait操作)、Block原语、Wakeup原语等。。非抢占调度方式实现简单，系统开销小，适用于大多数的批处理系统环境。但它难以满足紧急任务的要求——立即执行，因而可能造成难以预料的后果。显然，在要求比较严格的实时系统中，不宜采用这种调度方式。

2)抢占方式(PreemptiveMode)允许调度程序根据某种原则去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。优点:防止一个长进程长时间占用处理机，能为大多数进程提供更公平的服务，特别是能满足对响应时间有着较严格要求的实时任务的需求。但比非抢占方式调度所需付出的开销较大。抢占调度方式是基于一定原则的，主要有如下几条：(1)优先权原则。对一些重要的和紧急的作业赋予较高的优先权。当这种作业到达时，如果其优先权比正在执行进程的优先权高，便停止正在执行(当前)的进程，将处理机分配给优先权高的新到的进程，使之执行；或者说，允许优先权高的新到进程抢占当前进程的处理机。

(2)短作业(进程)优先原则。当新到达的作业(进程)比正在执行的作业(进程)明显的短时，将暂停当前长作业(进程)的执行，将处理机分配给新到的短作业(进程)，使之优先执行；或者说，短作业(进程)可以抢占当前较长作业(进程)的处理机。(3)时间片原则。各进程按时间片轮流运行，当一个时间片用完后，便停止该进程的执行而重新进行调度。这种原则适用于分时系统、大多数的实时系统，以及要求较高的批处理系统。§3.4调度算法一、周转时间：作业i从提交时刻Tsi到完成时刻Tei称为作业的周转时间。Ti=Tei(完成时刻)-Tsi(提交时刻)

一个作业的周转时间说明该作业在系统内停留的时间包含两部分：等待时间和执行时间

Ti=Twi+Tri

二、平均周转时间为（有n个作业，n>=1) n T=1/n∑Ti i=1三、带权周转时间Wi：

Wi=Ti(周转时间)/Tri(执行时间)平均带权周转时间为：

n W=1/n∑Wi i=1四、好的调度算法要求：CPU利用率高、吞吐量大、T和W小1、先来先服务（FCFS）调度算法将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列，并按照先来先服务的方式进行调度处理。优先考虑在系统中等待时间最长的作业，而不管要求运行时间的长短。作业进入时刻运行时间完成时刻周转时间带权周转时间1１０：003010：30 2１０：10603１０：2040 4１０：3020

作业1:

周转时间T1＝10:30－10:00＝30先来先服务算法分析结果301801.331102.75120611：3012：1012：30作业2:

周转时间T2＝11:30－10:10＝80带权周转时间W1＝30/30＝1

带权周转时间W2＝80/60＝1.33作业3:

周转时间T3＝12.10－10.20＝110

带权周转时间W3＝110/40＝2.75作业4:周转时间T4＝12.30－10.30＝120

带权周转时间W4＝120/20＝6平均周转时间:T＝(T1+T2+T3+T4)/4平均带权周转时间:W＝(W1+W2+W3+W4)/4T＝(30+80+110+120)/4=85(min)W＝(1+1.33+2.75+6)/4=2.77(min)作业号

1

2

3

4

到达时间8.008.509.009.50运行时间2.000.500.100.20调度顺序1

2

3

4作业号1

2

34到达时间8.008.509.009.50开始时间8.0010.0010.5010.60结束时间

10.0010.5010.6010.80周转时间2.002.001.601.30加权周转时间14

16

6.5例3-1：有下述作业序列：T1=10.00-8.00=2.00W1=2.00/2.00=1T2=10.50-8.50=2.00W2=2.00/0.50=4

T3=10.60-9.00=1.60W3=1.60/0.10=16T4=10.80-9.50=1.30W4=1.30/0.20=6.5

平均周转时间T=（T1+T2+T3+T4）/4=1.73加权平均周转时间W=(W1+W2+W3+W4)/4=6.88算法评价：这种算法按先来后到原则调度，比较公平，但是不利于短作业。此算法有利于CPU繁忙型作业，而不利于I/O繁忙型作业。

CPU繁忙型作业：指CPU进行处理时，不需频繁的请求I/O，而每次I/O的操作时间又很短。I/O繁忙型作业：指该类作业无需大量的CPU时间进行计算，但要频繁地请求I/O。2、最短作业优先法（SJF）：该算法总是优先调度要求运行时间最短的作业。选中某个短作业后，就保证该作业尽可能快地完成运行并退出系统，运行中不允许被抢占。作业进入时刻运行时间完成时刻周转时间带权周转时间1１０：0030 2１０：10603１０：2040

4１０：302010:3012:3011:3010:5030207014011.752.331平均带权周转时间W＝1.55(T=1+2.33+1.75+1)/4=1.52(min)平均周转时间T=0.65(T=30+140+70+20)/4=65(min)

例3-2：有下述作业序列：作业号

1

2

3

4

到达时间8.008.509.009.50运行时间2.000.500.100.20调度顺序1

2

3

4作业号1

3

42到达时间8.009.009.508.50开始时间8.0010.0010.1010.30结束时间

10.0010.1010.3010.80周转时间2.001.100.802.30加权周转时间111

4

4.6周转时间：

加权周转时间：

T=结束时间-到达时间

T1=10.00-8.00=2.00

T2=10.80-8.50=2.30

T3=10.10-9.00=1.10

T4=10.30-9.50=0.80

W=周转时间+运行时间

W1=2.00/2.00=1

W2=2.30/0.50=4.6

W3=1.10/0.10=11

W4=0.80/0.20=4

平均周转时间：

T=(T1+T2+T3+T4)/4=1.55

加权平均周转时间：

W=(1+4.6+11+4)/4=5.15算法评价：优点:有利于短作业。给定的时限内可以完成更多的作业，增加系统的吞吐量，改善调度性能。缺点：（1）对长作业不利。

（2）完全没考虑作业的紧迫程度，不能保证紧迫作业会得到及时处理。

（3）由于作业的长短只根据用户提供的估计执行时间而定,而用户又有可能会有意无意的缩短其作业的估计执行时间，致使该算法不一定能真正做到短作业优先调度。五、高优先权优先调度算法1．优先权调度算法的类型常用于批处理系统中，作为作业调度算法，也作为进程调度算法，还用于实时系统中。当把该算法用于作业调度时，系统将从后备队列中选择若干个优先权最高的作业装入内存。当用于进程调度时，该算法是把处理机分配给就绪队列中优先权最高的进程，这时，又可进一步把该算法分成如下两种。

1)非抢占式优先权算法在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。

2)抢占式优先权调度算法系统把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。*:在采用这种调度算法时，是每当系统中出现一个新的就绪进程i时，就将其优先权Pi与正在执行的进程j的优先权Pj进行比较。如果Pi≤Pj，原进程Pj便继续执行；但如果是Pi>Pj，则立即停止Pj的执行，做进程切换，使i进程投入执行。显然，这种抢占式的优先权调度算法能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。2．优先权的类型

(1)静态优先权静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。一般地，优先权是利用某一范围内的一个整数来表示的，如，0～7或0～255中的某一整数，又把该整数称为优先数，只是具体用法各异：有的系统用“0”表示最高优先权，当数值愈大时，其优先权愈低；而有的系统恰恰相反。

确定进程优先权的依据：

1)进程类型。系统进程(如接收进程、对换进程、磁盘I/O进程)的优先权高于一般用户进程的优先权。

2)进程对资源的需求。如进程的估计执行时间及内存需要量的多少，对这些要求少的进程应赋予较高的优先权。

3)用户要求。是由用户进程的紧迫程度及用户所付费用的多少来确定优先权的。

静态优先权法简单易行，系统开销小，但不够精确，很可能出现优先权低的作业(进程)长期没有被调度的情况。因此，仅在要求不高的系统中才使用静态优先权。

(2)动态优先权动态优先权是指在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。例如，我们可以规定，在就绪队列中的进程，随其等待时间的增长，其优先权以速率a提高。若所有的进程都具有相同的优先权初值，则显然是最先进入就绪队列的进程将因其动态优先权变得最高而优先获得处理机，此即FCFS算法。若所有的就绪进程具有各不相同的优先权初值，那么，对于优先权初值低的进程，在等待了足够的时间后，其优先权便可能升为最高，从而可以获得处理机。采用抢占式优先权调度算法时，如果再规定当前进程的优先权以速率b下降，则可防止一个长作业长期地垄断处理机。在批处理系统中，短作业优先算法是一种比较好的算法，其主要的不足之处是长作业的运行得不到保证。如果我们能为每个作业引入前面所述的动态优先权，并使作业的优先级随着等待时间的增加而以速率a提高，则长作业在等待一定的时间后，必然有机会分配到处理机。该优先权的变化规律可描述为：3、最高相应比作业优先算法（HRN）R=（等待时间+要求服务时间）/要求服务时间

=响应时间/要求服务时间

R=（等待时间+要求服务时间）/要求服务时间=响应时间/要求服务时间

(1)如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。

(2)当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。

(3)对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。该算法既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务。因此，该算法实现了一种较好的折衷。当然，在利用该算法时，每要进行调度之前，都须先做响应比的计算，这会增加系统开销。例3-3：有下述作业序列：作业序列号

1

2

3

4到达时间8.008.509.009.50运行时间2.000.500.100.20在8.00这一时刻只有作业1到达所以先运行。因为此调度算法是非抢占式的，所以一直到作业1运行完，在时刻10.00才决定下一个作业，而此时作业2，3，4都已到达，则分别对它们进行响应比计算。

RP2=4，RP3=11，RP4=3.5

作业3作业2作业4调度顺序

1

2

3

4作业号

1

3

2

4到达时间8.009.008.509.50开始时间8.0010.0010.1010.60结束时间10.0010.1010.6010.80周转时间2.000加权周转时间

1114.26.5平均周转时间T=(T1+T2+T3+T4)/4=1.625加权平均周转时间W=(W1+W2+W3+W4)/4=5.64、时间片轮转调度算法（RR）（1）基于时间片的轮转调度算法时间片轮转法主要用于进程调度。q=1和q=4时的进程运行情况

q=1和q=4时进程的周转时间

例：

进

程

P1

P2

P3

下一个CPU周期

24

3

3

解：若取时间片=4，则轮转法执行情况如下：

T2=7，T3=10完成，T1=30。平均周转时间：T=(T1+T2+T3）/3=（7+10+30）/3=16

：

P1P1P1P1P1P1P2P3047101418222630①当时间片很大时，每个进程得到比完成该进程多的处理机时间，此时轮转调度模式退化为先进先出模式。②当时间片非常小时，上下文转换开销就成了决定因素，系统性能降低，大多数时间都消耗在处理机的转换上，只有少许用在用户的计算上。

这个最佳的时间片值是多少呢？显然，它将随系统而异。随负载而异，同时也随进程异。时间片的选取是实现各种调度算法的关键之处，而时间片的额定通常应考虑终端数目，处理机能力、各终端任务的急迫程度、外存传输速度等方面的因素。时间片轮转法亦可应用于批处理系统的处理机调度。时间片的更新：

每当一轮调度开始时，系统便根据就绪队列中已有进程数目计算一次值。作为新一轮调度的时间片。这种方法得到的时间片是随就绪队列中的进程数变化的。（2）多级反馈队列调度算法

1)应设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，……，第i+1个队列的时间片要比第i个队列的时间片长一倍。

多级反馈队列调度算法

2)当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，如此下去，当一个长作业(进程)从第一队列依次降到第n队列后，在第n队列中便采取按时间片轮转的方式运行。

3)仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1～(i-1)队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1～(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程。(3)多级反馈队列调度算法的性能多级反馈队列调度算法具有较好的性能，能很好地满足各种类型用户的需要。

1)终端型作业用户。由于终端型作业用户所提交的作业大多属于交互型作业，作业通常较小，系统只要能使这些作业(进程)在第一队列所规定的时间片内完成，便可使终端型作业用户都感到满意。

2)短批处理作业用户。对于很短的批处理型作业，开始时像终端型作业一样，如果仅在第一队列中执行一个时间片即可完成，便可获得与终端型作业一样的响应时间。对于稍长的作业，通常只需在第二队列和第三队列各执行一个时间片即可完成，其周转时间仍然较短。

3)长批处理作业用户。对于长作业，它将依次在第1，2，…，n个队列中运行，然后再按轮转方式运行，用户不必担心其作业长期得不到处理。5、四种调度算法的优、缺点：

例：

进程

下一个CPU周期

P1

9

P2

3

P3

6

1）FCFS调度算法：

T1=9

T2=12

T3=18平均周转时间T=(T1+T2+T3)/3=13

W1=1

W2=4

W3=3加权周转时间W=(W1+W2+W3)/3=2.7

P1P2P30912182）SJF调度算法：0P2P3P13918T1=18T2=3T3=9

平均周转时间T=（T1+T2+T3）/3=10

W1=2

W2=1W3=1.5

加权周转时间W=(W1+W2+W3)/3=1.5当时间片=4：

T1=18T2=7

T3=17

平均周转时间T=（T1+T2+T3）/3=14

W1=2

W2=2.3W3=2.9加权周转时间W=(W1+W2+W3)/3=2.4

P2P3P1011154P1717P3183）时间片调度算法（RR算法）：当时间片=3：

T1=18T2=6

T3=15

平均周转时间T=（T1+T2+T3）/3=13

W1=2

W2=2

W3=2.5加权周转时间W=(W1+W2+W3)/3=2.2

P2P3P109123P161518P3P13）时间片调度算法（RR算法）：

T1=9

T2=12

T3=18平均周转时间T=(t1+T2+T3)/3=13

W1=1W2=4

W3=3

加权周转时间W=(W1+W2+W3)/3=2.7P1P2P30912184）HRN调度算法：

算

法

T

W

FIFO

13

2.7

SJF

10

1.5

时间片(4)

14

2.4

HRN

13

2.7

什么是多处理机系统多处理机操作系统的分类多处理机系统调度策略§3.5多处理机调度一、多处理机系统：是一个具有两个或多个处理机能相互进行通信以协同一个大的给定问题求解的计算机系统。使用多处理机系统的主要原因：

1、提高系统吞吐量。多处理机操作系统提高资原分配和管理，进程和处理机管理，内存和数据集保护以及文件系统等功能。

2、提高系统的可靠性在发生故障时能使用；还能提供系统结构重组的能力，以支持系统的降级使用。因此，多处理机的调度策略也必须考虑到降级使用和结构重组问题。特点：1）有两个或多个处理机2）共享主存或高速通信网络3）共享输入输出子系统4）有单一完整的操作系统5）各级硬件和软件相互作用

广义的计算机系统的一个共同的特点是有n个处理器(n>1),能做到真正的并行处理,也就是能同时执行n条指令主要功能：●进程分配●更好的利用多机硬件●资源在处理机之间的分配●改善程序的响应时间●处理机的负载平衡●处理机间的协调和同步●因处理机故障引起的系统重组

广义上说，使用多处理机协调工作，来完成用户所要求任务的计算机系统。这包扩了并行处理系统（parallelprocessingsystem），例如数据流机(dataflowmachine)和细胞阵列处理机(Celluararrayprocessors)等，也包扩了在物理上分散且通过不同的物理传输媒体传输数据的机算机网络系统和计算机网络为基础的，对用户透明的分布式系统，以及在同一的计算机系统里共享内存的多处理机系统。

二、多处理机操作系统：

指哪些用来并行执行用户的几个程序，以提高系统的吞吐率、提高系统可靠性的多处理机操作系统。这种系统由共享公共内存和外设的n(n>1)个CPU组成。

从概念上说，在多处理机系统中的各进程的行为与在单机系统下的行为相同。多处理环境下，进程可在各处理机间进行透明迁移，从而由进程上下文切换等带来的系统开销将使多处理机操作系统的复杂度大大增加。另外，由于多处理机系统并行地执行用户的几个程序（进程），这又带来了多处理机条件下的并发执行问题。三、多处理机操作系统

主从式（master-slaveconfiguration）独立监控系统(Separatesupervisor)

移动式监控系统(floatingsupervisor)(1)主从式指定一台特定的处理机为主处理机，由它负责对全系统的执行进行控制。主处理器上执行操作系统程序，以控制其它从处理机的状态，并为从处理机分配任务。DECsystem10，Cyber170以及多处理机UNIX系统MPX都是主从式结构。

在主从式操作系统中，如果从处理机需要主处理机提供服务时,它们采用硬件中断方式中断处理机上执行的进程以要求主处理机提供服务。这种结构的操作系统一般重组功能较差，因为只有主处理机上执行操作系统程序。如果主处理机失败或发生不可恢复的错误时，整系统将会瘫痪。(2)独立监控系统独立监控系统的监控程序在每个处理机上执行,每个处理机为自己的需要提供服务又互相通报执行情况.一般来说,每个监控程序能重新装入或在不同的处理机上复制独立的副本.

独立监控系统不像主从结构那样易于崩溃,但其监控程序在各处理机中的副本会占去大量的内存.(3)移动式监控系统移动式监控系统把监控程序根据需要从一个处理机移到另一个处理机上.使所有资原有比较均衡的负载.

移动式监控系统的处理机调度以及服务请求冲突等大都采用优先级的方式来解决。所以移动式监控系统是一种效率最高,实现也最难的多处理操作系统。四、多处理机系统调度策略调度目标是：以最高的可靠性，使用最少的处理机在最短的时间内完成最多的可以并行完成的进程。调度评价：调度程序的目的：是根据给定的执行时间和相互关系，确定出一个最佳的执行顺序。多处理机的调度有两种评价模型：（1）确定性模型、（2）随机性模性确定性模型只用来确定给定进程的执行顺序，而随机性模性则常被用来研究动态调度技术。确定性模型：进程调度执行之前，估计出这些被调度进程所需的执行时间，以及这些进程之间的相互关系。动态调度：在一个特定的时刻，将进程分配到一个特定的处理机上执行。随机模型中的进程执行时间是一个具有平均值和标准偏移值的随机变量。

五、多处理机系统与单机调度的区别

1、多处理机调度与单机调度的主要区别涉及两个资源分配问题：（1）存放程序或数据的存储器分配及如何访问他们的问题。

在多机系统中，由于各进程在物理上也同时执行而不是单机系统那样的交叉执行，这些在物理上同时执行的进程可能同时访问物理存储器的同一地址。处理机对同一存储块的访问必须是顺序的。各进程同时访问物理存储器上的同一地址是不允许的。

2、将等待执行的就绪进程分配到哪一个处理机上执行的问题。

在单机系统中，由于只有一个处理机，在调度程序中选取了某个就绪状态的进程之后，不须再选择处理机。而在多机系统中，为了尽量做到让各处理机负荷平衡，可能会会将处理机在进程之间进行多次切换。如果被切换进程正在执行其临界区部分或系统中进程数目相当多，这种频繁的上下文转换将会使系统效率大大下降。为了解决进程对处理机的分配问题，在有的多出理机系统中采用了局部就绪对列的方法限制进程的转移。

局部就绪对列：就是把处于就绪状态的进程分成不同的组，并使每一组进程和一个处理机对应起来。优点：每个处理机只执行其对应就绪对列中的进程。各个就绪对列中的进程不断发生横向转移。减少了调度程序的开销。缺点：处理机的使用率却因此下降。例如：系统中某个局部就绪对列中因等待进程较多而使得对应的处理机十分繁忙，而另外的处理机则因就绪对列为空而处于空闲状态。进程的定义进程的参考定义有如下几种：1、进程是程序的一次执行；2、进程=PCB+程序+数据；3、进程是一个可拥有资源的独立实体，同时又是一个可以独立调度的基本单位。§3.6进程控制PCB程序段私有数据块进程结构三要素:

进程名

当前状态

优先数

现场保留区

指示处于同一状态进程的链指针

资源清单

进程起始地址

家族关系

其他进程控制块一、进程控制祖先进程用户进程系统进程用户进程用户进程进程家族树任务:对系统中的全部进程实施有效管理表现:进程的创建、撤消、状态转换二、原语：

操作系统的核心，由若干条指令组成，用以实现某个特定操作。不可中断的系统程序。在管态下运行、常驻内存目的:实现进程的通信和控制三、原语和系统调用的区别：（1）相同点：被进程调用（2）不同点：原语是通过在其执行过程中关闭中断实现，一般由系统进程调用；系统调用是在目态下执行的进程调用，并借助中断进入管态程序，最后转交给相应的系统进程实现功能；原语有不可中断性进程控制原语及进程的状态转换运行就绪阻塞进程调度I/O完成时间片用完等待I/O完成创建进程撤销进程唤醒进程阻塞进程结束开始进程控制原语创建原语撤销原语阻塞原语唤醒原语

置状态为“阻塞”插入等待队列停止程序运行释放PCB释放内存释放所有资源申请空白PCB填PCB置状态为“就绪”插入就绪队列置状态为“就绪”插入就绪队列进程的属性：1、可拥有资源的独立单位；2、可以独立调度和分配的基本单位。并发执行的先提条件：1、创建进程2、撤消进程3、进程切换四、线程引入线程的目的：为了减少程序并发执行时所付出的时空开销，使操作系统具有更好的并发性。………………………………进程线程1线程2线程3进程1

分配处理机资源分配线程：是进程中的一个实体，是被系统独立调度的基本单位。线程有进程的三个基本状态。进程和线程的区别：1、调度同一进程中线程的切换不会引起进程切换2、并发性进程之间或进程内的多个线程间都可并发执行3、拥有资源进程拥有资源而线程可以访问其隶属进程的资源（代码段、数据段等）4、系统开销进程切换开销大于线程切换的开销§3.7进程通信临界资源和临界区同步与互斥两个经典的同步/互斥问题其他同步例子管程消息缓冲一、进程通信概述:进程通信：指进程间的信息交换过程按进程间通信的规模和方式的不同，分为低级通信和高级通信。低级通信：进程间只传递状态和整数值（控制信息），包括进程互斥和同步所采用的信号量及管程机制。缺点：传送信息量小，效率低；编程复杂，易出错高级通信：进程间通信时能够传送任意数量的数据。主要包括共享存储区、共享文件、消息传递（分为消息缓冲和信箱方式）。独立进程：在并发（多任务）环境下，一个进程不受到其他进程的影响。协作进程：在并发（多任务）环境下，一个进程受到其他进程的影响，该进程和影响他的进程都称为协作进程。影响的关系有互斥、同步、通信。二、临界资源和临界区临界资源:criticalresource（某段时间内只允许一个进程使用的资源）临界区:criticalsection（必须互斥执行的程序段是相对于临界资源的临界区）程序1Y=Y+1output程序2Y=Y+2output内存共享区Ypcb1pcb2使用临界区应遵循以下准则：（1）空闲则入：其他进程均不处于临界区；（2）忙则等待：已有进程处于临界区；（3）有限等待：等待进入临界区的进程不能“死等”（4）让权等待：不能进入临界区的进程应释放CPU（如转换到阻塞状态）三、同步与互斥基本概念同步工具硬件指令信号量与P、V操作并发程序共享资源问题的解决基本概念同步进程之间的一种通信方式，有时序上的制约关系，或者说是进程之间为了协同工作而存在的一种等待关系。互斥进程之间对临界资源的一种竞争关系，排他性地对资源的访问方式。进程同步：进程间共同完成一项任务时直接发生相互作用的关系，是进程之间的直接制约关系。在多道环境下，这种进程间在执行次序上的协调必不可少。进程互斥：保证每次只有一个进程使用临界资源。主要用于资源共享，是进程之间的间接制约关系。软件的忙等互斥方案

PiRepeatwhileturn<>idoskipcriticalsection(临界区)turn=jremainsection(其余代码)Untilfalse

PjRepeatwhileturn<>jdoskipcriticalsection(临界区)turn=i//强制轮流

remainsection(其余代码)Untilfalse（1）算法1Turn=i时Pi进入临界区，Turn=j时Pj进入临界区缺点：强制两个进程轮流进入临界区，造成资源利用不充分（2）算法2Pi:Repeat1Whileflag[j]doskip;3flag[i]:=ture;5criticalsection(临界区)flag[i]:=flase;Untilfalse

Pj:Repeat2

Whileflag[i]doskip;4flag[j]:=ture;6

criticalsection(临界区)flag[j]:=flase;Untilfalse

缺点：两个进程同时进入临界区（3）算法3：Pi:Repeat1flag[i]:=ture；3Whileflag[j]doskip;criticalsection(临界区)flag[i]:=flase;Untilfalse

Pj:Repeat2

flag[j]:=ture;

4

Whileflag[i]doskip;criticalsection(临界区)flag[j]:=flase;Untilfalse

缺点：两个进程无限期等待（4）算法4(petersun算法)，只针对双进程：Pi:Repeatflag[i]:=ture；turn:=j;While(flag[j]andturn=j)doskip;criticalsection(临界区)flag[i]:=flase;Untilfalse

LOCK和UNLOCK(低级通信原语)设公共变量x代表某个临界资源的状态

0资源可用

x=1资源正在使用四、同步工具进程进入临界资源的操作:1:检查X的值.X=1,表示资源正在使用,返回继续进行检查;X=0,表示资源可以使用,X:=1(关锁);2:进入临界区,访问临界资源;3:释放临界资源,X:=0(开锁).测试X:=1进入临界区退出临界区X:=0返回X:=0X:=1继续测试同步机制：用于控制进程之间的同步与互斥。硬件指令：test-and-set（lock）功能表示如下：关锁源语Lock(X)L:IfX=1thengotoLelseX:=1;开锁源语UnLock(X)X:=0程序1初始化lock=0程序的其它部分代码开锁lock=0test-and-set（lock）访问临界资源代码程序的其它部分lock=1lock=0程序2初始化lock=0程序的其它部分代码开锁lock=0test-and-set（lock）访问临界资源代码程序的其它部分lock=1lock=0应用举例五、P/V操作、信号量P/V操作由P操作原语和V操作原语组成，意义是：在一个整型变量S上定义了两个操作。信号量：整型变量S称为信号量，仅能由P、V操作修改的整型变量。整型值S队列指针NextP操作P操作：申请资源操作(1)

S:=S-1；(2)

如果S≥0，则表示有资源，该进程继续执行；如果S<0，则表示已无资源，执行原语的进程被置成阻塞状态，并使其在S信号量的队列中等待，直至其他进程在S上执行V操作释放它为止。

V操作：释放资源操作(1)

S:=S+1；(2)

如果S>0，则该进程继续执行；如果S≤0，则释放S信号量队列的排头等待者并清除其阻塞状态，即从阻塞状态转变到就绪状态，执行V(S)者继续执行。

V操作注意:一、一个正在执行P/V操作的进程，不允许任何其它进程中断它的操作，既保证同时只有一个进程对信号量S实施P或V操作。二、S>0:表示某类资源的可用数量；

S<0:表示无资源分配给请求的进程，S的绝对值等于等待队列的进程数目。进程A………P(S)将一项移入对列V(S)………..进程B………P(S)从对列移出一项V(S)………..例(互斥)：对列的移出与加入(S=1)例(同步):进程A:将信息输入到缓冲区B1进程B:从缓冲区B1中输出信息S1:缓冲区B1中是否有可供处理的信息处理S1=0S2:缓冲区B1中的信息是被进程B取走S2=0进程A………读消息到B1V(S1)P(S2)………..进程B………P(S1)将B1内容输出到B2V(S2)………..S1=1唤醒BS2<0:阻塞A(B1满)S1<0:阻塞BS1=0:输出信息唤醒A两个经典的同步/互斥问题生产者/消费者问题1、需输出打印文件的用户进程和打印机管理进程相对于打印机的管理进程用户进程（生产着）、打印机管理进程（消费者）2、需读入一磁盘文件的用户进程和磁盘管理进程相对于磁盘管理进程：用户进程（消费者）、磁盘管理进程（生产着）生产者/消费者问题模型的抽象化与进程分析生产者进程临界资源消费者进程信号量的设置Mutex=1 临界资源Empty=n 空缓冲区的数目Full=0 满缓冲区的数目满空ij

环形缓冲区生产者/消费者算法描述：varmutex，empty，full：psemaphore；i,j，goods：integer；buffer：array[0…n-1]ofitem；procedureproducer；生产者进程

beginwhiletruedobeginproducenextproduct；

P(empty)；P(mutex)；

buffer(i):=product；i:=(i+1)mod(n)；

V(mutex)；V(full)；

endend；procedureconsumer；消费者进程

beginwhiletruedobegin

P(full)；

P(mutex)；

goods：=buffer(j)；

j:=(j+1)mod(n)；

V(mutex)；

V(empty)；

consumeproduct；

endend；beginseminitial(mutex.v，1；empty.v，n；full.v，0)；i：=j：=0；

cobeginproducer；

consumer；

coendend并发进程文件写者进程读者进程读者进程...信号量的设置mutex=1临界资源1wrt=1临界资源2读者计数器readcount写者进程互斥信号量互斥写者互斥readcount读者与写者问题注意：对所有读者，readcount是共享变量，要互斥访问读者与写者问题算法描述

（无写进程时读者可访问、不考虑同时进入、优先考虑写入）:Varmutex，wrt,psemaphore；readcount：integer；beginseminit(mutex.v，1；wrt.v，1)；Readcount：=0；cobeginprocedurereader；begin

P(mutex);readcount:=readcount+1；

ifreadcount=1thenP(wrt)；

V(mutex)；

readingisperforming；

P(mutex);readcount:=readcount-1；

ifreadcount=0thenV(wrt)；

V(mutex)；endprocedurewriter；

begin

P(wrt)；

writingisperforming；

V(wrt)；

end

coendend；开（关）锁、P/V操作缺点：（1）临界段操作的代码以及进入和退出临界段的开（关）锁操作代码都要用户编写；（2）所有同步原语操作都分散在用户编写的各程序代码中，由进程来执行，系统无法有效控制和管理这些同步原语操作（无法检错、纠错）；（3）用户在编程时发生的不正确使用同步原语的操作会带来死锁的后果。P（Mutex）临界段P（Mutex）V（Mutex）临界段P（Mutex）六、管程把分散的各同类临界区集中起来。并为每个可共享资源设立一个专门的机构来统一管理各进程对该资源的访问，这个专门机构称为管程。优点：1、便于系统管理共享资源；2、保证互斥访问。Hansen在并发PASCAL语言中首先引入管程，将它作为语言中的一个并发数据结构类型。管程主要由两部分组成l

局部于该管程的共享数据，这些数据表示了相应资源的状态l

局部于该管程的若干过程，每个过程完成关于上述数据的某种规定操作。局部于管程内的数据结构只能被该管程内的过程所访问。局部于管程内的过程只能访问该管程内的数据结构管程的组成:对临界资源的互斥实现方法（编译）：管程每次只允许一个进程访问该管程内的某个过程。避免死锁：进程访问管程内的某个过程被阻塞时，应立即退出。条件变量：每个独立的条件变量是和进程需要等待的某种原因(或说条件)相联系的，当定义一个条件变量时，系统就建立一个相应的等待队列。关于条件变量有两种操作：wait(x)和signal(x).其中x为条件变量。Wait（）：把调用者进程挂在与x相应的等待队列上Signal（）：唤醒相应等待队列上的一个进程生产者/消费者管程描述producer:beginrepeat produceanitem; ringbuffer.put(item);untilfalse;endconsumer:begin repeat ringbuffer.get(item); consumetheitem; untilfalseendmonitorringbuffer；varrbuffer：array[0..n-1]ofitem；

k，nextempty，nextfull：integer；

empty，full：condition；procedureentryput(varproduct：item)；

beginifk=nthenwait(empty)；

rbuffer[nextempty]:=product；

k:=k+1；

nextempty:=（nextempty+1)mod（n）；

signal(full)；

end；procedureentryget(vargoods：item)；

begin

ifk=0thenwait(full)；

goods：=rbuffer[nextfull]；

k:=k-1；

nextfull:=(nextfull+1)mod（n）；

signal(empty)；

end；begink:=0；

nextempty：=0；nextfull：=0；end；满空消息：进程之间以不连续的成组方式发送的信息。消息缓冲区：包含有指向发送进程的指针、指向消息接受进程的指针、指向下一个消息缓冲区的指针、消息长度、消息内容等信息的一个缓冲区。是进程通信的基本单位。七、消息缓冲PCB(B):mq消息队列mutex互斥指针sm同步指针Sender:ASize:5Text:HelloNptr:receive(b):发送者：A

长度：5

正文：Hellob

0:send(B,a):发送者：A

长度：5

正文：Helloa发送接收发送与接收消息过程进程A进程BReceive和sendProceduresend(receiver,a)Begin getbuf(a,size,i); i.sender:=a.sender; i.size:=a.size; i.text:=a.text; i.next:=0; getid(PCB,receiver,j);

P(j.mutext); insert(j.mq,i);

V(j.mutext);

V(j.sm);EndProcedurereceive(b)Begin

P(j.sm);

P(j.mutext); remove(j.mq,i);

V(j.mutext); b.sender:=i.sender; b.size:=i.size; b.text:=i.text; putbuf(i);End死锁的原因和必要条件预防死锁资源独占(静态分配）资源顺序分配资源受控动态分配（避免死锁）发现死锁（死锁检测）解除死锁八、死锁

进程P1

进程P2

： ： 申请文件F 申请磁带机Tr1

：申请磁带机T … … r2:申请文件F

释放磁带机T …

释放文件F 释放文件F … 释放磁带机T

…死锁例子简单的死锁例子FTP2P1请求已分配请求配分已进程资源图产生死锁的原因和必要条件：原因：系统资源不足、进程推进顺序不合适；必要条件互斥条件不剥夺条件请求和保持条件环路等待条件预防死锁1、资源独占静止分配方法，预先分配所有资源给请求进程，而且在请求的进程在获取资源运行后一直处于独占资源的状态。（破坏互斥）缺点：资源利用率低、使用不方便。2、资源顺序分配法对系统提供的资源按编号顺序申请或释放（破坏环路等待）缺点：资源利用率低、使用不方便。……….L2L1LjLmax申请释放3、资源受控动态分配分配给要运行的进程所需要资源的最大申请量，动态分配。缺点：事先获取资源的最大需求量。

资源

R1R2…Rj…RmP1a11a12…a1j…a1mP2a21a22…a2j…a2m…………………Piai1ai2…aij…aim…………………Pnan1an2

…anj…anm进程死锁检测（发现）：资源分配表

进程资源P1P

2…P

j…P

nR1

b11b21…b1j…bn1R2b12b22…b2j…bm2…………………Rjb1jb2j…bij…bnj…………………Rm

bm1bm2

…bmj…bmn进程等待表:等待资源计数器C:引起相应进程被阻塞的资源数目。C1，C2，…….Cn未阻塞队列L：未阻塞的进程。检测算法如下:(1)把未阻塞(Ci=0)的进程Pi记录在L表中(其全部资源请求已得到满足的进程)；(2)从L表中选择一进程，根据资源分配表S释放分配给该进程的所有资源；(3)由进程等待表W依次检查和修改需要该进程释放资源的每一个进程的等待计数器Cj；(4)若Cj=0，则表示该进程所请求的资源已得到满足，不再阻塞，将Pj记入L表中；(5)再从L表中选取另一进程，重复上述操作；(6)若所有的进程都记入L表中，则系统初始状态为非死锁状态，否则为死锁状态。避免死锁：始终处于安全状态。在避免死锁方法中，允许进程动态申请资源，系统在分配资源前，先计算资源分配的安全性。若安全则将资源分配给进程，否则进程等待。安全状态：系统能按照某种顺序（p2、p2、p3…）为进程分配所需的资源，直至最大需求，使每个进程都可以顺利完成。此时系统处于安全状态，（p2、p2、p3…）为安全序列。不安全状态：若某一时刻中，系统不存在一个安全序列，则称此时系统为不安全状态。

进入不安全状态后，便可能进入死锁状态。避免死锁的本质：系统不进入不安全状态。避免死锁----安全状态例

T0时刻系统资源状态如下进程最大需求已分配需求可用P1

553P2422…P392710避免死锁进程最大需求已分配需求可用P1

555P2422…P392710避免死锁进程最大需求已分配需求可用P1

5510P2422…P392710避免死锁进程最大需求已分配需求可用P1

5510P2422…P392710安全序列<p2、p2、p3>避免死锁

---由安全状态向不安全状态转移

若在T0之后，又将一个资源分给了P3进程最大需求已分配需求可用P1

552P2422…P393610利用银行家算法避免死锁

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

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

(2)最大需求矩阵Max。这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。

(3)分配矩阵Allocation。这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的数目为K。

(4)需求矩阵Need。这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。上述三个矩阵间存在下述关系：Need[i,j]=Max[i,j]-Allocation[i,j]银行家算法设Requesti是进程Pi的请求向量，如果Requesti[j]=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：

(1)如果Requesti[j]≤Need[i,j]，便转向步骤(2)；否则认为出错，因为它所需要