《计算机操作系统》（孙雅如版）全套PPT电子课件教案- 第2章 处理机管理.ppt

第2章 处 理 机 管 理,2.1 进程概念 2.2 os内核及进程控制 2.3 进程通信 2.4 进程调度 2.5 线程 2.6 死锁 2.7 作业管理 2.8 操作系统的接口,2.1 进 程 概 念,2.1.1 进程的引入 在计算机系统中，为了充分地利用系统资源，cpu与外设必须并行工作。由于多道程序系统的出现，使得系统内部的活动变得复杂起来。例如，一个cpu可以在多道程序中快速切换，每道程序每次仅运行很短的时间，使得多道程序在一个小的时间段内都可以得到运行，给用户一种并行的错觉，称为并发执行。又如，当一道程序利用外设进行输入、输出时，cpu可以为另外一道程序工作，这是cpu与i/o设备的并行操作，也要求cpu在多道程序间快速切换。硬件的并行操作与程序的并发执行都需要cpu在多道程序中快速切换，原有的程序概念无法做到这一点，因此我们引入一个新概念进程。,1前趋图(procedence graph) 前趋图是一个有向无循环图dag(directed acyclic graph)。 在前趋图中，每个结点代表一个事件。在操作系统中，可以将结点看作语句、程序段或进程等。结点间的有向边表示两个结点间的前趋关系，记为“”。若有s1s2，则表示只有当s1完成之后，s2才可以执行，此时，称s1是s2的直接前趋，s2是s1的直接后继。 图2-1是一个例图。在图2-1(a)中，s1是没有前趋的结点，称为初始结点，s7是没有后继的结点，称为终止结点。而图2-1(b)是有两个初始结点的前趋图。至于图2-1(c)，因为s2与s3形成一个循环，所以它不是前趋图。,图2-1 例图,2程序的顺序执行 1) 程序的顺序执行 所谓程序的顺序执行，是指一个程序运行时独占整个系统资源, 处理机严格按照程序所规定的顺序进行操作。 在一个程序段中，只有前面的一个操作执行完，才能进行后面一个操作。在一个程序段的执行过程中，不能插入其它程序段中的操作。例如，对于下述程序段: s1: read（x，y）； s2: c = x+y； s3: print c；,其中s2必须在x、y被赋值后才能执行，同样，s3也必须在c被赋值后才能执行。因此，这个程序段的执行顺序如图2-2所示。,图2-2 一个程序段中语句的顺序执行,类似地，在一个系统中，若要执行几个程序段，只有当一个程序段执行完后才能执行另一个程序段中的操作。例如，一个程序段通常由输入(i)、计算(c)、输出(p)等操作组成，两个程序段的顺序执行则如图2-3所示。,图2-3 两个程序段的顺序执行,2) 程序顺序执行的特征 顺序性：处理机的操作严格按照程序所规定的操作顺序执行，时间上完全有序, 即只有前一个操作执行完以后，才能进行后继操作。 封闭性：程序执行时独占系统资源，系统内各种资源的状态（初始状态除外）只能被本程序所改变，因此其执行结果不受外界因素的干扰。 结果可再现性：只要程序执行的环境与初始状态不变, 当重复执行时, 所获得的结果相同, 与执行速度无关。,3程序的并发执行 并行操作是指多个操作在计算机系统的各个硬件部件上同时进行。例如，cpu与cpu的并行操作，cpu与i/o设备的并行操作，这是真正意义上的“同时”操作，称之为并行操作。 我们将要介绍的并发执行是指在一个时间段内，多个程序段在计算机系统中“一起”执行。例如，在一个时间段内，一个cpu在为多道程序工作，而在某一个瞬间，一个cpu只能运行一道程序，它只是在多道程序中快速切换，给人以cpu“同时”运行几道程序的感觉。每个程序内部仍是按顺序执行，但是多个程序的执行过程是可以交叉的，这是一种伪并行，称之为并发执行。,1) 并发执行 若干程序段在执行时间上有重叠, 即一个程序段的执行过程中插入了其它程序的操作，称为并发执行，如图2-4所示。程序p与程序q在t2t4之间是并发执行的，程序q与程序r在t3t5之间是并发执行的，而在t3t4之间，程序p、程序q与程序r是并发执行的。,图2-4 若干程序段的并发执行,2) 程序并发执行的特征 若干个程序段的并发执行，产生了一些与程序顺序执行时不同的特征： 顺序性：多个程序段并发执行时，每个程序段中语句的顺序执行仍然保持，但是多个程序段之间不再保持顺序执行的关系。 间断性：多个程序段并发执行时，由于共享资源或由于相互合作而形成执行时的相互制约关系，使得每个程序段执行时产生了间断性。例如，在单处理机系统中，多个程序段并发执行，当cpu执行一道程序时，必然导致其它程序暂时不能执行，这将使得程序具有“执行暂停执行”这种间断的活动规律。, 非封闭性：多个程序段并发执行时，每个程序段不再独占系统资源, 执行时受外界因素影响。例如，当一个用户的程序段执行中使用某个i/o设备时，其他用户的程序段申请使用该设备，就必须等待。 不可再现性：多个程序段并发执行时，产生了非封闭性，不再独占系统资源，此时，即使程序执行的环境与初始状态不变，重复执行时运算速度通常也不可再现，若运算结果与执行速度有关，则可能会被改变。,例如，两个并发执行的程序段共享一个变量，当两个程序段推进速度发生变化时，可能导致程序中引用共享变量的语句得到不同的结果，即程序运行结果不确定。我们通过下面一个例子来说明这种现象发生的过程。 设a与b是两个可以并发执行的程序段, n是共享变量。,因为程序段a与b是并发执行的程序段，每个程序段中的语句是顺序执行的，但是两个程序段的执行过程是可以交叉的。程序段a中的n=n+1语句可能在程序段b的print n语句之前执行，也可能在print n与n=0语句之间执行，还可能在n=0之后执行。不同的执行顺序会呈现不同的结果。例如当n的初始值为5时，会发生如下情况之一： 若程序段a中的n=n+1语句在程序段b的print n语句之前执行，则输出为6，n为0；, 若程序段a中的n=n+1语句在程序段b的print n与n=0语句之间执行，则输出为5，n为0； 若程序段a中的n=n+1语句在程序段b的n=0之后执行，则输出为5，n为1。 这样的结果用户是不能接受的。我们需要的是程序能并发执行，同时还要保证其具有可再现性。,4程序并发执行的条件,1) 读集 r(pi )=a1, a2, a3, .，am用以表示程序段pi执行时需要参考变量的集合，称为读集。其中a1, a2, a3, .，am是需要参考的变量。 例如，有语句： s1：c = a + b； 则 r c = a + b = a , b s2：x = x - 1； 则 r x = x - 1 = x ,2) 写集 w(pi)=b1, b2 , b3 , . , bn用以表示程序段pi执行中要改变的变量的集合，称为写集。其中b1, b2 , b3 , ., bn是需要改变的变量。 例如，有语句： s1：c = a + b； 则 w c = a + b = c s2：x = x - 1； 则 w x = x - 1 = x ,3) bernstein条件 1966年，bernstein提出了程序可以并发执行的条件，简称bernstein条件。 若两个程序段p1和p2能满足以下条件： r(p1)w(p2) = ； r(p2)w(p1) = ； w(p1)w(p2) = ； 则p1和p2可以并发执行，同时保证结果具有可再现性。,例如，有四条语句： s1: a = x + 1； s2: b = y + 1； s3: c = a + b； s4: d = c + 1； 显然，s1与s2可以并发执行，而s1与s3，s2与s3，s3与s4等均不可并发执行，用bernstein条件可以验证。通过图2-5，也很容易得到验证。,图2-5 具有四条语句的前趋图,5进程定义与特征 1) 进程定义 由于计算机众多硬件并行操作及多道程序的并发执行，使得“程序”的概念已经无法刻画程序执行中的活动与变化情况，因此引入了进程的概念。 1961年，进程的概念首先由美国麻省理工学院在multics系统中引入，得到人们的普遍重视并广为采用。随后，许多人都对进程下过定义，如： 进程是可以并发执行的程序在一个数据集合上的运行过程。,进程是程序的一次执行过程。 进程是可参与并发执行的程序。 进程是一个程序及其数据在处理机上执行时所发生的活动。 进程是在给定初始状态和内存区域的条件下，可以并发执行的程序的一次执行过程。 根据1978年在庐山召开的全国操作系统会议的讨论，认为“进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动”。,2) 进程的特征 进程是与程序完全不同的新概念，它具有以下特征： 并发性：在内存中的多个进程能在一段时间内同时运行。并发性使得进程的程序执行过程随时会被中断。多个进程的程序可以并发执行，这是进程最基本的特征之一，而程序是不能并发执行的。, 动态性：进程是程序的一次执行过程，“动态”是进程另一个最基本的特征。当要完成某项任务时为之创建进程，由处理机调度程序来选择要调度的进程并运行该进程的程序，当资源得不到满足时暂停执行，资源能够满足时，继续执行，直至任务完成后撤消该进程。因此，进程由创建到消亡是有一定生命期的，在生命期间进程是一个活动实体。而程序是可以永久存放于某种介质上的有序指令集合，是一个静态实体。, 独立性：进程是一个能够独立运行的基本单位，即只有进程才能被独立调度运行及独立获得资源。在系统中，除了系统提供的服务外，只有进程在活动，而程序是不能作为调度运行和获得资源的基本单位的。 异步性：这是指进程以各自独立的、不可预知的速度向前推进。这一特性基于进程的并发性，需要系统采取必要的措施，以保证各个进程的程序之间能协调运行。, 结构特征：进程实体中包含有程序段、数据段，还必须有一个存放进程生命期间管理信息的数据结构进程控制块pcb（process control block）。进程控制块pcb能够保证进程并发执行及在生命期间进程活动的顺利进行。不同的进程是以pcb来区别的，不同的pcb代表不同的进程。,2.1.2 进程的描述 1进程的组成 进程由三部分组成：进程控制块pcb、程序段和数据段，如图2-6所示。一个进程一经被创建，就有如下三部分内容： (1) pcb表：为便于管理，pcb表被放在不同的队列或状态中。新建进程的pcb表被放在就绪队列中，根据进程在活动过程中所处的状态，pcb表可被放在就绪队列或阻塞队列中，也可以处于执行状态中。 (2) 可执行的程序段：其首地址由pcb表中程序地址信息字段直接或间接指出。 (3) 可加工的数据段：其首地址由pcb表中数据地址信息字段直接或间接指出。有的进程可以没有数据段。,图2-6 进程的组成,进程控制块pcb是为描述进程动态变化过程以及对进程进行控制与管理而设的数据结构。进程与pcb表一一对应，操作系统根据pcb表了解进程的存在，它是进程是否存在的惟一标志。 pcb表常驻内存，属于系统空间，只有操作系统程序才能够访问，用户程序不得访问。 进程的程序段反映了进程的功能，数据段是程序加工的对象，均属于用户空间。运行时可以根据需要全部地或者部分地放在内存中。进程处于非执行状态时，如果内存有剩余空间，它的程序段和数据段放在内存，如果内存无剩余空间，则可以放在外存。进程处于执行状态时，程序段与数据段必须有一部分放在内存，以方便执行。程序段和数据段在内存与外存中的物理地址是由pcb表的地址信息字段指明的。,2pcb结构及其组织形式 pcb表记录了描述进程情况及控制进程运行所需要的全部信息，操作系统根据pcb提供的信息实施对进程的控制与管理。在一个系统中，pcb表的个数是有限的。当一个进程被创建时，为其分配一个空闲的pcb表，当进程被撤消时，回收其所占用的pcb表。pcb表被系统访问的频率很高，因此是常驻内存的。操作系统专门开辟一个pcb表区，每个pcb是一片连续的存储单元。根据pcb表所对应的进程的运行状态，所有的pcb表被组成若干个队列，如就绪队列、阻塞队列等，空闲的pcb表组成一个空闲队列，以备创建进程时进行申请使用和撤消进程时进行回收使用。,1) pcb的结构 pcb是一个线性表结构，通常包括以下内容： 进程标识符：分为外部标识符和内部标识符。外部标识符由创建进程者提供，通常由字母、数字等组成，在用户或其它进程访问该进程时使用。内部标识符是一个整数。在操作系统的pcb表区中，有多个pcb表，每个pcb表有一个序号，通常将这个序号做为内部标识符，以方便系统使用。 程序地址：进程的程序部分在内存及外存的地址，或描述程序地址信息的段表地址、页表地址、索引表地址等。, 数据地址：进程的数据部分在内存及外存的地址，或描述数据地址信息的段表地址、页表地址、索引表地址等。 状态：进程当前所处的状态，即就绪状态、执行状态及阻塞状态，已经被创建的进程的状态必为此三者之一。 cpu状态保护区：cpu状态信息主要由通用寄存器、程序计数器pc、程序状态字psw以及用户栈指针等组成，也称为中断点现场信息。cpu状态保护区用以保护进程被中断而暂停执行时cpu的状态信息，以便进程重新获得cpu时能够重布现场，从上次被中断处继续执行。, 进程优先级：进程优先级是用以描述进程使用处理机的优先级别的整数，是优先级调度算法中调度的依据。通常数值越小，优先级别越高。优先级可以处理成不变的，称为静态优先级，也可以处理成可变的，称为动态优先级。 通信信息：进程通信时需要使用的信息，包括标志位、信号或信号量、消息队列信息等。如消息缓冲通信机制中，在进程的pcb表中，需要有消息队列队首指针、消息个数及互斥使用消息队列的信号量等。 资源信息：进程对资源的需求及已经分配资源的清单。, 队列指针：除了执行状态的进程外，其余的进程pcb表都处于某一就绪队列或某一阻塞队列中。队列指针用于指向进程所在队列中下一个pcb表的首地址。 家族指针：进程在运行过程中可以创建新进程来协同完成同一任务。创建者称为父进程，被创建者称为子进程。父进程pcb表中有指向子进程的pcb表的指针，子进程的pcb表中有指向父进程的pcb表的指针，这就是家族指针，它可以将一个家族的进程联系起来，形成进程家族树。,2) pcb表的组织形式 在内存的系统空间中设有pcb表区，表区中的pcb表的个数根据系统的大小来设置。为了对进程实施有效的管理，通常将它们用某种方式组织起来，目前常用方式有如下几种： 链接方式：用pcb表中的队列指针项将具有相同状态的进程的pcb表链接起来，这样pcb表就形成就绪队列、空闲队列及阻塞队列等。其中，空闲队列是一个，而就绪队列与阻塞队列可以是多个。例如，可以将不同优先级的进程的pcb表排在不同的就绪队列中，也可以将阻塞原因不同的进程的pcb表排在不同的阻塞队列中。系统中的某些固定单元分别指向各队列队首地址及执行状态进程的pcb表的首地址。,以链接方式组织的pcb表如图2-7所示。其中，处于执行状态的是pcb1，处于就绪状态的是pcb3、pcb4、pcb2，处于阻塞状态的是pcb7、pcb6、pcb5，处于空闲状态的是pcb8、pcb9等。 索引方式：根据进程的状态，在内存中建立相应的索引表，系统中的某些固定单元保存各索引表的首地址。各索引表的表目中记录相应状态的pcb表的首地址。以索引方式组织的pcb表如图2-8所示。 对于图2-7中pcb的组织情况，可以用图2-9表示。,图2-7 链接方式组织pcb表示意图,图2-8 索引方式组织pcb表示意图,图2-9 进程pcb表组织的描述,3进程的状态及其变迁 1) 进程的基本状态及其变迁 进程有三个基本状态：就绪状态、执行状态与阻塞状态。进程的基本状态及其变迁如图2-10所示。进程在运行过程中必处于这三个基本状态之一。,图2-10 进程的基本状态及其变迁图,就绪状态：进程获得必要资源，例如内存等，已经具备了执行条件，只是没有空闲的cpu，处于等待cpu的状态。在系统中，将处于就绪状态的多个进程的pcb表排成一个队列，或按照某种规则排在不同的队列中，这些队列称为就绪队列。 执行状态：进程已经获得必要的资源及cpu，它的程序正在执行中，这时进程的状态称为执行状态。在多处理机系统中，可以有多个进程处于执行状态。在单处理机系统中，只能有一个进程处于执行状态，系统应尽量保证一个cpu上总有一个处于执行状态的进程，使cpu得到充分的利用。,阻塞状态：进程因某等待事件发生（例如i/o请求、某些原语操作等）而处于暂停执行的状态，此时即使将cpu分配给它，它的程序也无法执行。在系统中，将处于阻塞状态的进程的pcb表排成一个队列，或因阻塞原因不同而将进程的pcb表排在不同的队列中，这些队列称为阻塞队列。 进程的三个基本状态有下列四种可能的状态变迁： 就绪执行：进程调度程序按某种算法将处于就绪队列的某个进程选出，重布现场，把cpu分配给它，该进程便由就绪状态转变为执行状态。,执行就绪：处于执行状态的进程因时间片用完而被中断，将该进程的pcb表插入就绪队列，该进程便由执行状态转变为就绪状态。如果在采用抢占式调度策略的系统中，进入就绪队列的进程的优先级高于正处在执行状态的进程，可抢占cpu，将执行状态进程的pcb表插入就绪队列，由执行状态转变为就绪状态。,执行阻塞：进程在某等待事件发生（例如i/o请求、原语p操作等）而无法执行时，会由执行状态转变为阻塞状态，在等待该事件的完成过程中将放弃cpu的使用权，以免出现“忙等”。 阻塞就绪：进程在某等待事件完成，被阻塞的原因解除（例如i/o完成、原语v操作等）时，将阻塞状态进程的pcb表插入就绪队列，由阻塞状态转变为就绪状态，重新获得被调度的权力。 进程运行期间会不断地从一个状态转变为另一个状态，它可以多次处于上述三个基本状态中。当一个进程完成，或者在执行过程中出现意外情况而异常结束时，进程被撤消，生命期结束。,2) 进程的活动与静止状态 为了便于研究系统的工作状态是否正常、效率如何以及方便用户检查自己作业的执行情况或对进程进行修改等工作，需要使某些进程暂时处于静止状态，即让正在执行的进程停止执行，使处于就绪状态的进程不再接受调度，使处于阻塞状态的进程不再转变为就绪状态，我们把这种情况称为将进程挂起，使进程处于静止状态。当处于静止状态的进程被激活时，它将重新处于活动状态中。具有挂起功能的进程状态及其变迁如图2-11所示。,图2-11 具有静止状态和活动状态的进程状态变迁图,上述进程状态变迁图除了图2-10所示的四种可能的状态变迁外，又增加了下面六种情况： 活动就绪静止就绪：当进程处于未被挂起的就绪状态时，称为活动就绪状态，此时进程可以接受调度。当处于活动就绪状态的进程被挂起时，该进程便转变为静止就绪状态，此时进程不再接受调度。通常，新建进程进入活动就绪状态，以便尽快得到调度。,活动阻塞静止阻塞：当进程处于未被挂起的阻塞状态时，称为活动阻塞状态，此时进程可以因某等待事件的完成而转变为活动就绪状态。当处于活动阻塞状态的进程被挂起时，该进程便转变为静止阻塞状态。 静止阻塞静止就绪：处于静止阻塞状态的进程在所期待的事件出现后，将从静止阻塞状态转变为静止就绪状态，仍然处于静止状态。 静止就绪活动就绪：处于静止就绪状态的进程被激活后，该进程转变为活动就绪状态，进程可以重新接受调度。,静止阻塞活动阻塞：处于静止阻塞状态的进程被激活后，该进程转变为活动阻塞状态，当所期待的事件完成后，它将从活动阻塞状态转变为活动就绪状态。 执行静止就绪：处于执行状态的进程被挂起后处于静止就绪状态，暂停执行，不再接受调度。 以上是将就绪和阻塞状态分别分成静止及活动两个状态，可以看作对就绪状态与阻塞状态的细化。若我们将就绪状态分为高、中、低优先级队列，阻塞队列分为不同原因的阻塞队列，这是又一种对就绪、阻塞状态的细化方法。在unix系统中，不但对就绪状态、阻塞状态进行了细化，对执行状态也进行了细化，详见第6章的图6-3。,2.2 os内核及进程控制,2.2.1 os内核 1处理机的执行状态 处理机有核心态和用户态两种执行状态。 核心态：由设备中断、异常、自陷、信号（即软中断）等进入，这种状态具有较高的特权，允许使用全部机器资源与机器指令，是操作系统程序执行时的状态。 用户态：处理机在这种状态下只能使用指定的机器指令，不能使用如i/o、改变机器状态、修改存储保护等指令，并且只允许访问用户自己的存储区，是用户程序执行时的状态。,2操作系统内核 1) 内核定义 在第1章中，我们了解到没有配置任何软件的计算机称为裸机，操作系统是在裸机上添加多层软件形成的。通常将与硬件紧密相关的部分，如中断处理程序、设备驱动程序及进程从创建到撤消包括进程状态变迁中用到的公共操作等集中在一起，常驻内存，作为裸机上添加的第一层软件，叫做内核。,2) 内核功能 内核主要是为进程创造一个适宜的运行环境。内核完成中断处理、进程控制、进程通信、进程调度等操作及内存的分配与回收和设备的驱动等。这些功能通常用原语来实现。 3) 原语 原语是完成特定功能的程序段，如同扩充的机器指令广义指令一样，但是原语是不可分割的原子操作，即操作时要屏蔽中断。 系统中有各种不同的原语，如进程控制的原语、进程通信的原语等。,2.2.2 进程控制 1进程控制功能 进程控制是操作系统内核中的组成部分。在操作系统中有两类进程：系统进程和用户进程。由进程控制对系统中所有进程实施有效地管理。进程控制主要完成创建进程、撤消进程以及实现进程状态之间的转换等工作。,2进程控制方式 进程控制的方式有管理程序负责制和进程家族制两种。 1) 管理程序负责制 管理程序负责制如图2-12所示。 在管理程序负责制的系统中，当作业进入系统时，由管理程序为其创建进程、运行进程，直至完成任务予以撤消。管理程序负责制的特点是进程之间关系平等，由管理程序统一管理。,图2-12 管理程序负责制,2）进程家族制 图2-13表示进程家族制中的一棵进程树。根结点为祖先进程，创建进程者为父进程，被创建者为子进程。进程家族制的特点是层次清晰、进程控制灵活、资源分配严格。进程家族制中，子进程由父进程创建与撤消，它的活动完全由父进程控制，子进程只能使用父进程的资源。目前，这是一种常用的管理与控制进程的方式。,图2-13 进程家族树,2.2.3 进程控制原语 不同的操作系统中，使用的进程控制原语是不完全相同的，下面介绍几种常用的进程控制原语。 1创建原语 1) 功能 创建原语的功能是创建一个进程。,2) 引起创建的事件 在采用进程家族制的系统中，进程一般由父进程创建。引起创建的事件如下： 当终端用户登录时，由终端子进程创建用户进程； 批处理系统中，作业调度程序为选出的作业创建进程； 系统为合法用户建立服务进程； 进程运行时可以创建子进程来协同完成任务。,3) 创建原语的实现过程 创建原语需要一些参数，如进程外部标识符、cpu初始状态s0、初始内存区m0、所需资源r0、优先级k0等。,图2-14 创建原语实现过程,2撤消原语 1) 功能 撤消原语的功能是撤消一个或者多个进程。撤消策略有两种：一种是撤消一个具有指定标识符的进程，另一种是撤消一个进程及其所有子孙进程，以防止形成不可控制的孤儿进程。为了更好地保证系统的安全，通常使用后者。,2) 撤消进程的典型事件 进程完成任务，正常结束时被撤消； 进程运行出现故障及错误时，被迫终止运行而被撤消； 进程运行时因外界干预而撤消，如系统发生死锁时需要撤消一些进程、父进程撤消子进程等。 3) 撤消原语的实现过程 撤消原语的参数为撤消进程的标识符n。 撤消原语的实现过程如图2-15所示。,图2-15 撤消原语实现过程,3阻塞原语 1) 功能 阻塞原语完成进程从执行状态到阻塞状态的转变，这时处于执行状态的进程自身被阻塞。阻塞原语能够暂时剥夺执行进程使用cpu的权力，将其置为阻塞状态并插入阻塞队列，引起进程调度。,2) 引起阻塞的典型事件 进程请求i/o服务，无论获得i/o服务与否，通常都要暂时放弃cpu； 某些原语操作，如p操作等可能引起进程阻塞； 某些系统进程工作时占用cpu，无事可做时，则调用阻塞原语将自己阻塞。,3) 阻塞原语的实现过程,图2-16 阻塞原语实现过程,4唤醒原语 1) 功能 唤醒原语将进程从阻塞状态转变为就绪状态。它将唤醒进程的pcb表从阻塞队列移出，置为就绪状态，插入就绪队列，准备接受进程调度程序的下一次调度。 2) 唤醒进程的典型事件 进程请求的i/o操作完成； 某些原语操作，如v操作等可以解封阻塞进程； 某些系统进程有事可做时，用唤醒原语将其唤醒。,3) 唤醒原语的实现过程,图2-17 唤醒原语实现过程,5挂起原语 1) 功能 根据进程所处状态，挂起原语可以有三种处理： 完成进程从活动就绪状态到静止就绪状态的转变; 完成进程从活动阻塞状态到静止阻塞状态的转变; 若进程是执行状态，则转变为静止就绪状态。,2) 挂起对象与挂起方式 挂起对象： 进程请求挂起自身； 父进程挂起子进程。 挂起方式如下： 挂起一个具有指定标识符的进程； 挂起某个进程及其所有子孙进程。采用这种挂起方式可以避免进程被挂起而其子孙进程仍在活动而带来的问题。,3) 实现过程 下面对于挂起一个具有指定标识符的进程的挂起方式予以实现。 挂起原语的参数为进程标识符n。,图2-18 挂起原语实现过程,3) 激活原语实现过程 激活原语的参数为进程标识符n。,图2-19 激活原语实现过程,2.3 进 程 通 信,2.3.1 进程同步与互斥 1. 进程之间的关系 合作关系：一组进程协同完成一个任务，它们之间是合作关系。这种情况需要对于相互合作的多个进程的执行次序进行协调，这样就必须交换信息，以免出现时间上的差错。例如，一个计算进程和一个打印进程共同完成一个任务。若打印进程要打印时，而计算进程尚未计算出结果，打印进程就无法打印，但是这种要求会传达给计算进程。当计算进程计算出结果时，通知打印进程，则打印进程就可以工作了。这种“传达”与“通知”就是在交换信息。,竞争关系：多个进程因为使用共享资源而产生竞争关系，在抢占使用资源时可能导致使用失败，都达不到目的，因而要有信息交换以保证各得其所。例如，多个进程共同使用一台打印机，当一个进程打印时，其它进程不能使用，否则打印内容会混在一起。在这种情况下，就要求当前正在使用打印机的进程与其它要求打印的进程之间交换信息，才能协调对打印机的使用。,同步：多个进程在执行过程中，为了共享资源与相互合作而在执行次序上的协调，称为同步，即共享同一资源的进程和相互关联进程以通信手段来保障完成任务时保持一种固定的时间关系。 互斥：当某一进程访问某一资源时，不允许别的进程同时访问，这种限制称为互斥，即多个进程在访问某些资源（如临界资源）时，也要有一种执行次序上的协调，当一个进程访问完毕，另一个进程才能访问。所以就其本质来讲，互斥仍是一种同步。 在一个系统中，必须有相应的方法或机制来协调进程的执行次序。,2临界资源与临界区 1) 临界资源 一次仅允许一个进程访问的资源称为临界资源。 计算机的许多硬件资源都被处理成临界资源，如打印机、磁带机等。例如，若打印机允许若干用户同时打印，则打印结果会混在一起，不易分辨，给用户带来许多不便。 系统中还有许多软资源，如共享变量、表格、队列、栈等也被处理成临界资源，以避免多个进程对它们访问时出现问题。,例如，若有两个进程p1、p2，共享一个公用变量c，初值为8，p1、p2所做工作如下： p1 p2 l1：a = c； l4：b = c； l2：a = a+1； l5：b = b?1； l3：c = a； l6：c = b；,试看下述两种执行情况： (1) 若语句执行顺序为l1，l2，l3，l4，l5，l6，则c = 8； (2) 若语句执行顺序为l1，l2，l4，l5，l3，l6，则c = 7。 显然，上述结果是不能令人满意的。p1、p2是进程，每个进程中语句执行顺序是不变的，而两个进程的语句是可以交叉执行的，它们以哪种方式交叉执行是不可预知的。若p1、p2是一个自动售票系统中的退票与售票终端，就会产生许多麻烦。如果将c处理成临界资源，让p1、p2互斥访问c，一个进程对于c的一次访问完毕，另一个进程才能访问，就不会出现这种情况。,2) 临界区 进程访问临界资源的程序段称为临界区。 在一个系统中，可以用某些方法或某种机制保证进程对临界区的互斥访问，一个好的解决方案应该遵循以下条件： (1) 任何两个进程不能同时处于临界区内； (2) 进程在临界区外只作有限时间的等待； (3) 临界区外的进程不得阻塞其它进程进入临界区； (4) 等待临界区时, 释放cpu。,3对临界资源互斥访问的解决方法,1) 锁变量 设一个共享锁变量l，表示某个临界资源。其初值为0，表示锁开的状态。 当进程要求进入临界区时，测试锁变量，有两种情况： 若l为0，表示锁开着，则将l置为1，即可进入临界区。使用完毕，将l置为0，以便其它进程使用该临界资源； 若l为1，表示锁未开，则进程不断地进行测试，直到l为0时，方可进入临界区。 使用锁变量解决互斥问题，如图2-20所示。,图2-20 锁变量解决互斥,用锁变量解决互斥存在的问题如下： 进程持续测试锁变量l是否等于0的过程属于忙等待，对于cpu是一种浪费，违背进程互斥访问临界区的条件(4)：等待临界区时，释放cpu。 另外，可能有这种情况发生：一个进程读锁变量时发现其值为0，在将其置为1之前被中断，另一进程被调度运行，发现l为0，将其置为1，并进入临界区。当第一个进程再次运行时，又将锁置为1，也进入临界区。这样两个进程同时处于临界区中，违背了进程互斥访问临界区的条件(1)：任何两个进程不能同时处于临界区内。,2) 严格轮转法 设一个公用变量i，存放被允许进入临界区的进程的编号。 每个进程进入临界区时，对变量i进行测试，当进程号与变量i的值相等时，方可进入临界区，否则反复进行测试的工作。 进程出临界区时为公用变量i设置允许进入临界区的进程的编号，然后执行该进程非临界区的操作。 用严格轮转法解决互斥问题的过程，如图2-21所示。,图2-21 严格轮转法,用严格轮转法解决互斥存在的问题如下： 严格轮转法持续测试公用变量i直到它具有某特定值，这仍是忙等待，违背了进程互斥访问临界区的条件(4)：等待临界区时，释放cpu。 另外，若有pm、pn两进程，当pm进程执行完临界区时，将公用变量i置上允许进入临界区的进程pn的编号，假如pm非临界区操作很快做完，当pn进程尚未进入临界区时，pm再次要求进入临界区，因为公用变量i为pn的编号，虽然临界区空，而pm仍然不能进入，违反了进程对临界区互斥访问的条件(3) ：临界区外的进程不得阻塞其它进程进入临界区。,3) 屏蔽中断 屏蔽中断的作法是：每个进程进入临界区时，首先关中断再访问临界区，在离开临界区之前打开中断。中断关闭后，则时钟中断也被屏蔽，cpu将无法进行进程切换，就不必担心其它进程竞争该资源了。采用关中断方法实现进程之间的互斥，简单而有效，但是若用户进程忘了打开中断，系统将终止。如果有多个cpu，一个进程访问一个临界区时，使用关中断仅可以阻止本cpu上执行的进程进入该临界区，不能防止别的cpu上的进程访问该临界区。,4) ts指令（test and set） ts指令是一种利用硬件解决互斥的方法，通常将ts指令称为测试并上锁指令。 ts指令的定义： ts = lock； lock = true； 其中变量ts、lock为布尔量。 将lock作为某临界区的锁变量。当lock为false时，为未锁状态，即临界资源未被占用；当lock为true时，为上锁状态，即临界资源已被占用。 系统初启时，lock被赋值为false，即临界资源是空闲状态。,用ts指令解决互斥的方法是：当进程进入临界区前上锁，离开时开锁。用ts指令解决互斥问题的过程如图2-22所示。 用ts指令解决互斥的方法中，其检查过程是一种忙等待，违反了进程对临界区互斥访问的条件(4)：等待临界区时, 释放cpu。,图2-22 ts指令解决互斥,4信号量机制 1) p、v操作 荷兰学者e.w.dijkstra于1961年提出一种新的同步机制信号量机制。 在信号量机制中，用一个整型变量作为信号量。设置两种基本操作p和v，利用对信号量的改变达到互斥与同步的目的。信号量的初值表示同类临界资源的个数。当它被初始化后，只能为p、v操作所改变。 p、v是一对同步原语，是不可中断的原子操作。,p操作描述如下： 设s为信号量，代表某一种临界资源，q为申请资源s 的进程，q为申请该临界资源s未得到满足而形成的等待队列。具体工作过程如下： (1) s?1s； (2) 若s0，则进程q继续执行； (3) 若s0，则中断cpu，暂停执行，保留cpu现场，将q置为阻塞状态，q的pcb表放入s的等待队列q中，转进程调度程序入口（即阻塞原语）。 p操作的实现过程如图2-23所示。,图2-23 p操作实现过程,v操作描述如下： 设s为信号量，代表某一种临界资源，q为申请资源s 的进程，q 为申请资源 s 未得到满足而形成的等待队列。具体工作过程如下： (1) s + 1s； (2) 若s0，则进程q继续执行； (3) 若s0，则从s的等待队列q中唤醒一个进程，置为就绪状态，并将其pcb表插入就绪队列，q继续执行（即唤醒原语）。 v操作的实现过程如图2-24所示。,图2-24 v操作实现过程,在使用p、v操作的过程中需要注意的是： p操作为请求资源而设，v操作为增加、释放资源而设； p操作可能引起正在执行状态的进程阻塞，v操作可以解封进程，即唤醒进程； 在整个系统活动中，p、v必须成对出现。,2) 用p、v操作解决互斥问题 用p、v操作解决互斥的过程如下：设一个信号量s，表示某一个临界资源，初值为1，表示该资源未被占用。不同的临界资源用不同的信号量表示。进程访问临界资源时，将临界区置于p(s)与v(s)操作之间即可。 用p、v操作解决互斥如图2-25所示。 当临界资源已经被占用，其它进程要求进入临界区而执行p(s)操作时，使得s0，要求进程被阻塞。当有进程退出临界区而执行v(s)操作时，若s0 ，则可以解封被阻塞于s所代表的资源的阻塞队列中的进程。,图2-25 用p、v解决互斥,用p、v操作解决互斥时，信号量s值的意义如下： s=1，表示无进程进入临界区； s=0，表示有一进程进入临界区，而没有阻塞在临界区外的进程； s0，表示有一进程进入临界区，还有阻塞在临界区外的进程，s的绝对值表示等待进入临界区而被阻塞的进程个数。,设置信号量： 信号量m用以表示缓冲区有无可供打印的结果。m的初值为0。 信号量n用以表示缓冲区中计算结果是否被取走。n的初值为0。 计算进程与打印进程的工作过程如图2-26所示。,图2-26 计算进程与打印进程的工作过程,因为计算进程与打印进程的调度顺序是未知的，假定缓冲区大小仅能存放一个计算结果，且不考虑时钟中断，就绪队列中进程的排列次序为先a后b，则a、b的工作过程简述如下： 计算进程： (1) 将计算结果送缓冲区； (2) 执行v(m)。此时m=1（属m0），即缓冲区中有计算结果可供打印； (3) 执行p(n)。此时n=?1（属n0），即缓冲区中计算结果未被取走，不能再送计算结果，则计算进程被阻塞。等待打印进程取走计算结果时，将其唤醒，再依次做(1)、(2)、(3)，直至计算工作完成被撤消。,打印进程： (1) 执行p(m)。此时m=0（属m0），即缓冲区中有计算结果，可以取出打印； (2) 取出计算结果打印； (3) 执行v(n)。此时n=0（属n0），即计算进程因无缓冲区存放计算结果被阻塞，现在缓冲区已空，可供计算进程存放计算结果，因此唤醒计算进程。再依次做(1)、(2)、(3)，直至打印工作完成被撤消。 请考虑：若就绪队列中进程的排列次序为先b后a，进程a与b的工作过程如何进行，信号量m、n的值怎样变化。,4) 用p、v操作描述前趋关系 图2-27是一个有向无循环图，即一个前趋图。 若用p、v操作描述图中的前趋关系，则需在每个有向边上设一个信号量，初值为0。 首先，对所有到达si的有向边上的信号量做p操作，然后执行si，最后再对所有从si离去的有向边的信号量做v操作，则si并发执行时仍能保证其前趋关系。 如对于s6，则做p(e)，p(f)，s6，v(h)。即使s6排在就绪队列队首，也因执行p操作而被阻塞，需s3与s4执行v(e)与v(f)才能解封它, 从而保证了前趋关系s3s6与s4s6。,图2-27 一个前趋图,5信号量集机制 上述p、v操作一次只能对一个信号量做加一或减一操作，即只能使进程获得或释放一个单位的某种临界资源。假如进程一次需要共享多种临界资源，且每种资源个数不限于一个时，则p、v操作就显得效率不高，这种情况下我们可以用信号量集来解决。 在信号量集机制中，进程一次可以申请多个不同种类的临界资源，当可用资源个数低于系统规定的某一下限值时，不予分配。,现定义sp如下： sp(s1，t1，d1；.；sn，tn，dn) 若siti且sidi时，作si - disi，然后返回原程序继续执行；否则，若存在si ti或si di时, 则将申请资源的进程放入第一个不满足条件的si的等待队列，将程序计数器pc拨回到进程的程序开始执行sp 时的初始位置，转进程调度程序入口。其中： si：系统现有该类资源个数； ti：分配下限； di：需要分配的资源个数。,进程使用p操作申请资源时，不管申请到与否，再运行时都要从p操作所在程序位置的下一条指令开始执行。而进程用sp申请资源时申请的是不同种类的多个资源，假如某资源申请不到而进程被阻塞时，不释放其它资源，会使得系统资源更短缺，以致引起“死锁”的后果。因此，即使有一个资源申请不到，也将此次申请作废，程序计数器拨回到进程的程序执行sp时的初始位置。下次进程运行时再重新申请所有资源。 定义sv如下： sv(s1，d1；.；sn，dn),对于i1，n，做si+disi，同时将在si上等待的所有进程从阻塞队列移到就绪队列上，然后释放资源的进程继续执行。 特例： (1) sp(s，1，1)相当于p(s)； (2) sp(s，1，0)相当于一个可控开关，即当s1时，允许多个进程进入某特定区；当s1时，禁止任何进程进入某特定区。 (3) 将sp(s，1，0)作一引伸，如sp(s，n，0)，则表示当sn时，允许多个进程进入某特定区；当sn时，禁止任何进程进入某特定区。,6管程机制 1) 管程引入 进程可以使用p、v操作进行通信，但是访问临界资源的进程自行使用p、v操作解决通信问题时，会给系统带来许多问题。我们不能保证所有用户在编写程序时是完全无误的，比如可能出现这样的情况： p、v操作没有成对出现：只有p，而没有v，或者只有v，而没有p； p、v操作颠倒； 两个p操作颠倒等。,上述情况都会给系统带来不可预料的问题。对此，有人提出能否将对临界资源的控制与管理集中起来，用户只要提出使用要求，其它诸如互斥、同步等问题则不需要用户自己解决，而由系统统一解决。20世纪70年代，hoare 和b. hansen提出了一种同步原语，称为管程。当进程共享某临界资源时，只需调用相应的管程，而对资源的使用及其出现的诸如同步、互斥等问题，则完全由管程去解决。这样，资源的使用中用到的p、v操作仅出现在管程中，不会大量出现在进程的程序中，出错的几率也会少得多。,2) 概念 b.hansen 给管程下的定义是：一个管程指定义了一个数据结构和能为并发程序在该数据结构上执行的一组操作，这组操作能同步进程和改变管程中的数据。 管程的结构如图2-28所示，这里用数据结构对资源进行描述，一组过程体现对资源的使用方式。进程在管程外排队等候使用资源。,图2-28 管程的结构,由此可知，管程由以下几部分组成： (1) 管程标识符； (2) 局部于管程的共享变量说明； (3) 对该数据结构进行操作的一组过程； (4) 对局部于管程的数据的初始化过程。,管程基本特性是在任一时刻，管程中只能有一个活跃进程。当进程调用管程时，管程首先要检查的是管程中是否有其它活跃进程：若有，则将调用进程挂起，直到另一进程离开管程；若没有，则调用进程进入管程，这样就能够有效地保证进程访问临界资源时的互斥。而局部于管程的数据结构仅能被局部于管程的过程访问，局部于管程的过程仅能访问局部于管程的数据结构，这使得资源管理的模块变得清晰、简单，在系统资源发生变化时，资源管理模块的修改更容易实现。,管程实现进程同步时，需增加支持同步的设施： 设局部于管程的若干条件变量ci。 wait (ci)定义如下：进程申请管程服务时，管程调用wait (ci)。若请求服务未果，将进程挂在ci的等待队列上。 signal (ci)定义如下：signal (ci)可以重新启动一个在ci上阻塞的进程，若无阻塞进程，则该操作无效。,这里需要注意的是：wait 和signal与p、v操作是有区别的。 为避免管程中同时有两个进程活跃，signal (ci)操作后，让管程内进程继续活动，还是被唤醒进程进入管程呢？b.hansen建议执行signal (ci)的进程立即退出管程，而让被唤醒的进程进入管程，这样处理起来简单，容易实现。,2.3.2 经典同步问题 1生产者消费者问题（即有界缓冲区问题） 1) 问题 一群生产者向一个有界缓冲区存放产品，只要缓冲区未满，就可以存入；又有一群消费者从有界缓冲区取走产品，只要缓冲区未空，就可以取走。要求存与存之间、取与取之间和存与取之间不能同时进行，即一次只能有一个生产者或者一个消费者进入缓冲区，也就是所有的生产者与消费者必须互斥地访问缓冲区。当缓冲区满时，生产者停止放入产品，当缓冲区空时，消费者停止取走产品，即生产与消费同步。这里，生产的产品与消费的产品是等效的。,2) 解决方法 (1) 用p、v操作解决。 设置信号量： 互斥使用有界缓冲区的信号量s，初值为1； 同步信号量： 有界缓冲区的大小，即可以存放产品的最大数n，初值为k； 有界缓冲区中已经存放的产品个数m，初值为0。 生产者消费者问题的解决如图2-29所示。,图2-29 生产者-消费者问题,请思考以下问题： 若消费速度较生产速度快得多，图2-29可以简化吗？如何简化？ 若p(n)与p(s)颠倒，会产生什么问题？p(m)与p(s)呢？ 若v(s)与v(m)颠倒，会如何？v(s)与v(n)呢？,(2) 用管程解决。 该管程包括两个过程，enter过程与remove过程。生产者与消费者分别调用这两个过程，就可以完成对有界缓冲区的互斥访问和保持进程间的同步。 设：条件变量：full，empty； 有界缓冲区中产品计数值为count，初值为0，最大值为n。 enter过程如图2-30所示。 remove过程如图2-31所示。,图2-30 enter过程,图2-31 remove过程,2读者写者问题（courtois etal，1971） 1) 问题 一个