《操作系统-汤小丹-第四版》第2章.ppt

第二章进 程 管 理,2.1进程的基本概念 2.2进程控制 2.3进程同步 2.4经典进程的同步问题 2.5 进程通信 2.6线程,2.1进程的基本概念,2.1.1程序的顺序执行及其特征1.程序的顺序执行通常可以把一个应用程序分成若干个程序段，在各程序段之间，必须按照某种先后次序顺序执行，仅当前一操作(程序段)执行完后，才能执行后继操作。例如，在进行计算时，总须先输入用户的程序和数据，然后进行计算，最后才能打印计算结果。这里，我们用结点(Node)代表各程序段的操作(在图2-1中用圆圈表示)，其中，I代表输入操作，C代表计算操作，P为打印操作；另外，用箭头指示操作的先后次序。这样，上述的三个程序段的执行顺序可示于图2-1(a)中。对一个程序段中的多条语句来说，也有一个执行顺序问题，例如对于下述三条语句的程序段:,S1:a:=x+y；S2:b:=a-5；S3:c:=b+1；,其中，语句S2必须在语句S1之后(即a被赋值)才能执行；同样，语句S3也只能在b被赋值后才能执行。因此，这三条语句应按图2-1(b)所示的顺序执行。,图 2-1程序的顺序执行,2.程序顺序执行时的特征(1)顺序性：处理机的操作严格按照程序所规定的顺序执行，即每一操作必须在上一个操作结束之后开始。(2)封闭性：程序是在封闭的环境下执行的，即程序运行时独占全机资源，资源的状态(除初始状态外)只有本程序才能改变它。程序一旦开始执行，其执行结果不受外界因素影响。(3)可再现性：只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它是从头到尾不停顿地执行，还是“停停走走”地执行，都将获得相同的结果。程序顺序执行时的特性，为程序员检测和校正程序的错误带来了很大的方便。,2.1.2前趋图前趋图(Precedence Graph)是一个有向无循环图，记为DAG(Directed Acyclic Graph)，用于描述进程之间执行的前后关系。图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序(Partial Order，亦称偏序关系)或前趋关系(Precedence Relation)“”。,=(Pi，Pj)|Pi must complete before Pj may start，如果(Pi，Pj)，可写成PiPj，称Pi是Pj的直接前趋，而称Pj是Pi的直接后继。在前趋图中，把没有前趋的结点称为初始结点(Initial Node)，把没有后继的结点称为终止结点(Final Node)。此外，每个结点还具有一个重量(Weight)，用于表示该结点所含有的程序量或结点的执行时间。在图2-1(a)和2-1(b)中分别存在着这样的前趋关系：,IiCiPi,S1S2S3,和,对于图2-2(a)所示的前趋图，存在下述前趋关系：,P1P2，P1P3，P1P4，P2P5，P3P5，P4P6，P4P7，P5P8，P6P8，P7P9，P8P9或表示为：P=P1，P2，P3，P4，P5，P6，P7，P8，P9=(P1，P2)，(P1，P3)，(P1，P4)，(P2，P5)，(P3，P5)，(P4，P6)，(P4，P7)，(P5，P8)，(P6，P8)，(P7，P9)，(P8，P9),应当注意，前趋图中必须不存在循环，但在图2-2(b)中却有着下述的前趋关系：,S2S3，S3S2,图 2-2前趋图,2.1.3程序的并发执行及其特征1程序的并发执行在图2-1中的输入程序、计算程序和打印程序三者之间，存在着IiCiPi这样的前趋关系，以至对一个作业的输入、计算和打印三个操作，必须顺序执行，但并不存在PiIi+1的关系，因而在对一批程序进行处理时，可使它们并发执行。例如，输入程序在输入第一个程序后，在计算程序对该程序进行计算的同时，可由输入程序再输入第二个程序，从而使第一个程序的计算操作可与第二个程序的输入操作并发执行。一般来说，输入程序在输入第i+1个程序时，计算程序可能正在对第i个程序进行计算，而打印程序正在打印第i-1个程序的计算结果。图2-3示出了输入、计算和打印这三个程序对一批作业进行处理的情况。,图2-3 并发执行时的前趋图,在该例中存在下述前趋关系：,IiCi，IiIi+1，CiPi，CiCi+1，PiPi+1,而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之间，可以并发执行。对于具有下述四条语句的程序段：S1:a:=x+2S2:b:=y+4S3:c:=a+bS4:d:=c+b,图 2-4四条语句的前趋关系,2程序并发执行时的特征1)间断性程序在并发执行时，由于它们共享系统资源，以及为完成同一项任务而相互合作，致使在这些并发执行的程序之间，形成了相互制约的关系。例如，图2-3 中的I、C和P是三个相互合作的程序，当计算程序完成Ci1的计算后，如果输入程序I尚未完成Ii的处理，则计算程序就无法进行Ci的处理，致使计算程序必须暂停运行。又如，当打印程序完成Pi的打印后，若计算程序尚未完成Ci1的计算，则打印程序就无法对Ci1的计算结果进行打印。一旦使程序暂停的因素消失后(如Ii已处理完成)，计算程序便可恢复执行对Ci的处理。简而言之，相互制约将导致并发程序具有“执行暂停执行”这种间断性的活动规律。,2)失去封闭性程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性。这样，某程序在执行时，必然会受到其它程序的影响。例如，当处理机这一资源已被某个程序占有时，另一程序必须等待。,3)不可再现性程序在并发执行时，由于失去了封闭性，也将导致其再失去可再现性。例如，有两个循环程序A和B，它们共享一个变量N。程序A每执行一次时，都要做N:=N+1操作；程序B每执行一次时，都要执行Print(N)操作，然后再将N置成“0”。程序A和B以不同的速度运行。这样，可能出现下述三种情况(假定某时刻变量N的值为n)。,(1)N:=N+1在Print(N)和N:=0之前，此时得到的N值分别为n+1，n+1，0。(2)N:=N+1在Print(N)和N:=0之后，此时得到的N值分别为n，0，1。(3)N:=N+1在Print(N)和N:=0之间，此时得到的N值分别为n，n+1，0。上述情况说明，程序在并发执行时，由于失去了封闭性，其计算结果已与并发程序的执行速度有关，从而使程序的执行失去了可再现性，亦即，程序经过多次执行后，虽然它们执行时的环境和初始条件相同，但得到的结果却各不相同。,2.1.4进程的特征与状态1.进程的特征和定义在多道程序环境下，程序的执行属于并发执行，此时它们将失去其封闭性，并具有间断性及不可再现性的特征。这决定了通常的程序是不能参与并发执行的，因为程序执行的结果是不可再现的。这样，程序的运行也就失去了意义。为使程序能并发执行，且为了对并发执行的程序加以描述和控制，人们引入了“进程”的概念。为了能较深刻地了解什么是进程，我们将先对进程的特征加以描述。,1)结构特征通常的程序是不能并发执行的。为使程序(含数据)能独立运行，应为之配置一进程控制块，即PCB(Process Control Block)；而由程序段、相关的数据段和PCB三部分便构成了进程实体。在早期的UNIX版本中，把这三部分总称为“进程映像”。值得指出的是，在许多情况下所说的进程，实际上是指进程实体，例如，所谓创建进程，实质上是创建进程实体中的PCB；而撤消进程，实质上是撤消进程的PCB，本教材中也是如此。,2)动态性进程的实质是进程实体的一次执行过程，因此，动态性是进程的最基本的特征。动态性还表现在：“它由创建而产生，由调度而执行，由撤消而消亡”。可见，进程实体有一定的生命期，而程序则只是一组有序指令的集合，并存放于某种介质上，其本身并不具有运动的含义，因而是静态的。,3)并发性这是指多个进程实体同存于内存中，且能在一段时间内同时运行。并发性是进程的重要特征，同时也成为OS的重要特征。引入进程的目的也正是为了使其进程实体能和其它进程实体并发执行；而程序(没有建立PCB)是不能并发执行的。4)独立性在传统的OS中，独立性是指进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位。凡未建立PCB的程序都不能作为一个独立的单位参与运行。,5)异步性这是指进程按各自独立的、不可预知的速度向前推进，或说进程实体按异步方式运行。现在我们再来讨论进程的定义。曾有许多人从不同的角度对进程下过定义，其中较典型的进程定义有：(1)进程是程序的一次执行。(2)进程是一个程序及其数据在处理机上顺序执行时所发生的活动。(3)进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。,2.进程的三种基本状态进程执行时的间断性决定了进程可能具有多种状态。事实上，运行中的进程可能具有以下三种基本状态。1)就绪(Ready)状态当进程已分配到除CPU以外的所有必要资源后，只要再获得CPU，便可立即执行，进程这时的状态称为就绪状态。在一个系统中处于就绪状态的进程可能有多个，通常将它们排成一个队列，称为就绪队列。,2)执行状态进程已获得CPU，其程序正在执行。在单处理机系统中，只有一个进程处于执行状态；在多处理机系统中，则有多个进程处于执行状态。3)阻塞状态正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃处理机而处于暂停状态，亦即进程的执行受到阻塞，把这种暂停状态称为阻塞状态，有时也称为等待状态或封锁状态。致使进程阻塞的典型事件有：请求I/O，申请缓冲空间等。通常将这种处于阻塞状态的进程也排成一个队列。有的系统则根据阻塞原因的不同而把处于阻塞状态的进程排成多个队列。,图2-5 进程的三种基本状态及其转换,3.挂起状态1)引入挂起状态的原因在不少系统中进程只有上述三种状态，但在另一些系统中，又增加了一些新状态，最重要的是挂起状态。引入挂起状态的原因有：(1)终端用户的请求。当终端用户在自己的程序运行期间发现有可疑问题时，希望暂时使自己的程序静止下来。亦即，使正在执行的进程暂停执行；若此时用户进程正处于就绪状态而未执行，则该进程暂不接受调度，以便用户研究其执行情况或对程序进行修改。我们把这种静止状态称为挂起状态。,(2)父进程请求。有时父进程希望挂起自己的某个子进程，以便考查和修改该子进程，或者协调各子进程间的活动。(3)负荷调节的需要。当实时系统中的工作负荷较重，已可能影响到对实时任务的控制时，可由系统把一些不重要的进程挂起，以保证系统能正常运行。(4)操作系统的需要。操作系统有时希望挂起某些进程，以便检查运行中的资源使用情况或进行记账。,2)进程状态的转换在引入挂起状态后，又将增加从挂起状态(又称为静止状态)到非挂起状态(又称为活动状态)的转换；或者相反。可有以下几种情况：(1)活动就绪静止就绪。当进程处于未被挂起的就绪状态时，称此为活动就绪状态，表示为Readya。当用挂起原语Suspend将该进程挂起后，该进程便转变为静止就绪状态，表示为Readys，处于Readys状态的进程不再被调度执行。,图 2-6具有挂起状态的进程状态图,(2)活动阻塞静止阻塞。当进程处于未被挂起的阻塞状态时，称它是处于活动阻塞状态，表示为Blockeda。当用Suspend原语将它挂起后，进程便转变为静止阻塞状态，表示为Blockeds。处于该状态的进程在其所期待的事件出现后，将从静止阻塞变为静止就绪。(3)静止就绪活动就绪。处于Readys状态的进程，若用激活原语Active激活后，该进程将转变为Readya状态。(4)静止阻塞活动阻塞。处于Blockeds状态的进程，若用激活原语Active激活后，该进程将转变为Blockeda状态。图2-6示出了具有挂起状态的进程状态图。,4创建状态和终止状态1)创建状态创建一个进程一般要通过两个步骤：首先，为一个新进程创建PCB，并填写必要的管理信息；其次，把该进程转入就绪状态并插入就绪队列之中。当一个新进程被创建时，系统已为其分配了PCB，填写了进程标识等信息，但由于该进程所必需的资源或其它信息，如主存资源尚未分配等，一般而言，此时的进程已拥有了自己的PCB，但进程自身还未进入主存，即创建工作尚未完成，进程还不能被调度运行，其所处的状态就是创建状态。,引入创建状态，是为了保证进程的调度必须在创建工作完成后进行，以确保对进程控制块操作的完整性。同时，创建状态的引入，也增加了管理的灵活性，操作系统可以根据系统性能或主存容量的限制，推迟创建状态进程的提交。对于处于创建状态的进程，获得了其所必需的资源，以及对其PCB初始化工作完成后，进程状态便可由创建状态转入就绪状态。,2)终止状态进程的终止也要通过两个步骤：首先等待操作系统进行善后处理，然后将其PCB清零，并将PCB空间返还系统。当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是被其他有终止权的进程所终结，它将进入终止状态。进入终止态的进程以后不能再执行，但在操作系统中依然保留一个记录，其中保存状态码和一些计时统计数据，供其它进程收集。一旦其它进程完成了对终止状态进程的信息提取之后，操作系统将删除该进程。图2-7示出了增加了创建状态和终止状态后，进程的三种基本状态及转换图衍变为五种状态及转换关系图。,图2-7 进程的五种基本状态及转换,图2-8 具有创建、终止和挂起状态的进程状态图,如图2-8所示，引进创建和终止状态后，在进程状态转换时，相比较图2-7所示的进程五状态转换而言，需要增加考虑下面的几种情况。(1)NULL创建：一个新进程产生时，该进程处于创建状态。(2)创建活动就绪：在当前系统的性能和内存的容量均允许的情况下，完成对进程创建的必要操作后，相应的系统进程将进程的状态转换为活动就绪状态。,(3)创建静止就绪：考虑到系统当前资源状况和性能要求，并不分配给新建进程所需资源，主要是主存资源，相应的系统进程将进程状态转为静止就绪状态，对换到外存，不再参与调度，此时进程创建工作尚未完成。(4)执行终止：当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是被其他有终止权的进程所终结，进程即进终止状态。,2.1.5进程控制块1进程控制块的作用为了描述和控制进程的运行，系统为每个进程定义了一个数据结构进程控制块PCB(Process Control Block)，它是进程实体的一部分，是操作系统中最重要的记录型数据结构。PCB中记录了操作系统所需的、用于描述进程的当前情况以及控制进程运行的全部信息。进程控制块的作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。,或者说，OS是根据PCB来对并发执行的进程进行控制和管理的。例如，当OS要调度某进程执行时，要从该进程的PCB中查出其现行状态及优先级；在调度到某进程后，要根据其PCB中所保存的处理机状态信息，设置该进程恢复运行的现场，并根据其PCB中的程序和数据的内存始址，找到其程序和数据；进程在执行过程中，当需要和与之合作的进程实现同步、通信或访问文件时，也都需要访问PCB；当进程由于某种原因而暂停执行时，又须将其断点的处理机环境保存在PCB中。可见，在进程的整个生命期中，系统总是通过PCB对进程进行控制的，亦即，系统是根据进程的PCB而不是任何别的什么而感知到该进程的存在的。所以说，PCB是进程存在的惟一标志。,当系统创建一个新进程时，就为它建立了一个PCB；进程结束时又回收其PCB，进程于是也随之消亡。PCB可以被操作系统中的多个模块读或修改，如被调度程序、资源分配程序、中断处理程序以及监督和分析程序等读或修改。因为PCB经常被系统访问，尤其是被运行频率很高的进程及分派程序访问，故PCB应常驻内存。系统将所有的PCB组织成若干个链表(或队列)，存放在操作系统中专门开辟的PCB区内。例如在Linux系统中用task_struct数据结构来描述每个进程的进程控制块，在Windows操作系统中则使用一个执行体进程块(EPROCESS)来表示进程对象的基本属性。,2进程控制块中的信息1)进程标识符进程标识符用于惟一地标识一个进程。一个进程通常有两种标识符：(1)内部标识符。在所有的操作系统中，都为每一个进程赋予了一个惟一的数字标识符，它通常是一个进程的序号。设置内部标识符主要是为了方便系统使用。(2)外部标识符。它由创建者提供，通常是由字母、数字组成，往往是由用户(进程)在访问该进程时使用。为了描述进程的家族关系，还应设置父进程标识及子进程标识。此外，还可设置用户标识，以指示拥有该进程的用户。,2)处理机状态处理机状态信息主要是由处理机的各种寄存器中的内容组成的。处理机在运行时，许多信息都放在寄存器中。当处理机被中断时，所有这些信息都必须保存在PCB中，以便在该进程重新执行时，能从断点继续执行。这些寄存器包括：通用寄存器，又称为用户可视寄存器，它们是用户程序可以访问的，用于暂存信息，在大多数处理机中，有 832个通用寄存器，在RISC结构的计算机中可超过100个；指令计数器，其中存放了要访问的下一条指令的地址；程序状态字PSW，其中含有状态信息，如条件码、执行方式、中断屏蔽标志等；用户栈指针，指每个用户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址，栈指针指向该栈的栈顶。,3)进程调度信息在PCB中还存放一些与进程调度和进程对换有关的信息，包括：进程状态，指明进程的当前状态，作为进程调度和对换时的依据；进程优先级，用于描述进程使用处理机的优先级别的一个整数，优先级高的进程应优先获得处理机；进程调度所需的其它信息，它们与所采用的进程调度算法有关，比如，进程已等待CPU的时间总和、进程已执行的时间总和等；事件，指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。,4)进程控制信息进程控制信息包括：程序和数据的地址，指进程的程序和数据所在的内存或外存地(首)址，以便再调度到该进程执行时，能从PCB中找到其程序和数据；进程同步和通信机制，指实现进程同步和进程通信时必需的机制，如消息队列指针、信号量等，它们可能全部或部分地放在PCB中；资源清单，即一张列出了除CPU以外的、进程所需的全部资源及已经分配到该进程的资源的清单；链接指针，它给出了本进程(PCB)所在队列中的下一个进程的PCB的首地址。,3.进程控制块的组织方式1)链接方式这是把具有同一状态的PCB，用其中的链接字链接成一个队列。这样，可以形成就绪队列、若干个阻塞队列和空白队列等。对其中的就绪队列常按进程优先级的高低排列，把优先级高的进程的PCB排在队列前面。此外，也可根据阻塞原因的不同而把处于阻塞状态的进程的PCB排成等待I/O操作完成的队列和等待分配内存的队列等。图2-9示出了一种链接队列的组织方式。,图 2-9PCB链接队列示意图,2)索引方式系统根据所有进程的状态建立几张索引表。例如，就绪索引表、阻塞索引表等，并把各索引表在内存的首地址记录在内存的一些专用单元中。在每个索引表的表目中，记录具有相应状态的某个PCB在PCB表中的地址。图2-10示出了索引方式的PCB组织。,图 2-10按索引方式组织PCB,2.2进 程 控 制,进程控制是进程管理中最基本的功能。它用于创建一个新进程，终止一个已完成的进程，或终止一个因出现某事件而使其无法运行下去的进程，还可负责进程运行中的状态转换。如当一个正在执行的进程因等待某事件而暂时不能继续执行时，将其转换为阻塞状态，而当该进程所期待的事件出现时，又将该进程转换为就绪状态等等。进程控制一般是由OS的内核中的原语来实现的。,原语(Primitive)是由若干条指令组成的，用于完成一定功能的一个过程。它与一般过程的区别在于：它们是“原子操作(Action Operation)”。所谓原子操作，是指一个操作中的所有动作要么全做，要么全不做。换言之，它是一个不可分割的基本单位，因此，在执行过程中不允许被中断。原子操作在管态下执行，常驻内存。,图2-11 进程树,2.2.1进程的创建1进程图(Process Graph)进程图是用于描述一个进程的家族关系的有向树，如图2-11所示。图中的结点(圆圈)代表进程。在进程D创建了进程I之后，称D是I的父进程(Parent Process)，I是D的子进程(Progeny Process)。,2引起创建进程的事件在多道程序环境中，只有(作为)进程(时)才能在系统中运行。因此，为使程序能运行，就必须为它创建进程。导致一个进程去创建另一个进程的典型事件，可有以下四类：(1)用户登录。在分时系统中，用户在终端键入登录命令后，如果是合法用户，系统将为该终端建立一个进程，并把它插入就绪队列中。(2)作业调度。在批处理系统中，当作业调度程序按一定的算法调度到某作业时，便将该作业装入内存，为它分配必要的资源，并立即为它创建进程，再插入就绪队列中。,(3)提供服务。当运行中的用户程序提出某种请求后，系统将专门创建一个进程来提供用户所需要的服务，例如，用户程序要求进行文件打印，操作系统将为它创建一个打印进程，这样，不仅可使打印进程与该用户进程并发执行，而且还便于计算出为完成打印任务所花费的时间。,(4)应用请求。在上述三种情况下，都是由系统内核为它创建一个新进程；而第4类事件则是基于应用进程的需求，由它自己创建一个新进程，以便使新进程以并发运行方式完成特定任务。例如，某应用程序需要不断地从键盘终端输入数据，继而又要对输入数据进行相应的处理，然后，再将处理结果以表格形式在屏幕上显示。该应用进程为使这几个操作能并发执行，以加速任务的完成，可以分别建立键盘输入进程、表格输出进程。,3进程的创建(Creation of Process)一旦操作系统发现了要求创建新进程的事件后，便调用进程创建原语Creat()按下述步骤创建一个新进程。(1)申请空白PCB。为新进程申请获得惟一的数字标识符，并从PCB集合中索取一个空白PCB。,(2)为新进程分配资源。为新进程的程序和数据以及用户栈分配必要的内存空间。显然，此时操作系统必须知道新进程所需内存的大小。对于批处理作业，其大小可在用户提出创建进程要求时提供。若是为应用进程创建子进程，也应是在该进程提出创建进程的请求中给出所需内存的大小。对于交互型作业，用户可以不给出内存要求而由系统分配一定的空间。如果新进程要共享某个已在内存的地址空间(即已装入内存的共享段)，则必须建立相应的链接。,(3)初始化进程控制块。PCB的初始化包括：初始化标识信息，将系统分配的标识符和父进程标识符填入新PCB中；初始化处理机状态信息，使程序计数器指向程序的入口地址，使栈指针指向栈顶；初始化处理机控制信息，将进程的状态设置为就绪状态或静止就绪状态，对于优先级，通常是将它设置为最低优先级，除非用户以显式方式提出高优先级要求。(4)将新进程插入就绪队列，如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列。,2.2.2进程的终止1引起进程终止的事件1)正常结束在任何计算机系统中，都应有一个用于表示进程已经运行完成的指示。例如，在批处理系统中，通常在程序的最后安排一条Holt指令或终止的系统调用。当程序运行到Holt指令时，将产生一个中断，去通知OS本进程已经完成。在分时系统中，用户可利用Logs off去表示进程运行完毕，此时同样可产生一个中断，去通知OS进程已运行完毕。,2)异常结束在进程运行期间，由于出现某些错误和故障而迫使进程终止(Termination of Process)。这类异常事件很多，常见的有下述几种：(1)越界错误。这是指程序所访问的存储区已越出该进程的区域。(2)保护错。这是指进程试图去访问一个不允许访问的资源或文件，或者以不适当的方式进行访问，例如，进程试图去写一个只读文件。(3)非法指令。这是指程序试图去执行一条不存在的指令。出现该错误的原因，可能是程序错误地转移到数据区，把数据当成了指令。,(4)特权指令错。这是指用户进程试图去执行一条只允许OS执行的指令。(5)运行超时。这是指进程的执行时间超过了指定的最大值。(6)等待超时。这是指进程等待某事件的时间超过了规定的最大值。(7)算术运算错。这是指进程试图去执行一个被禁止的运算，例如被0除。(8)I/O故障。这是指在I/O过程中发生了错误等。,3)外界干预外界干预并非指在本进程运行中出现了异常事件，而是指进程应外界的请求而终止运行。这些干预有：(1)操作员或操作系统干预。由于某种原因，例如，发生了死锁，由操作员或操作系统终止该进程。(2)父进程请求。由于父进程具有终止自己的任何子孙进程的权力，因而当父进程提出请求时，系统将终止该进程。(3)父进程终止。当父进程终止时，OS也将它的所有子孙进程终止。,2进程的终止过程如果系统中发生了上述要求终止进程的某事件，OS便调用进程终止原语，按下述过程去终止指定的进程。(1)根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态。(2)若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。,(3)若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防它们成为不可控的进程。(4)将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。(5)将被终止进程(PCB)从所在队列(或链表)中移出，等待其他程序来搜集信息。,2.2.3进程的阻塞与唤醒1.引起进程阻塞和唤醒的事件有下述几类事件会引起进程阻塞或被唤醒。1)请求系统服务当正在执行的进程请求操作系统提供服务时，由于某种原因，操作系统并不立即满足该进程的要求时，该进程只能转变为阻塞状态来等待。例如，一进程请求使用某资源，如打印机，由于系统已将打印机分配给其他进程而不能分配给请求进程，这时请求者进程只能被阻塞，仅在其他进程在释放出打印机的同时，才将请求进程唤醒。,2)启动某种操作当进程启动某种操作后，如果该进程必须在该操作完成之后才能继续执行，则必须先使该进程阻塞，以等待该操作完成。例如，进程启动了某I/O设备，如果只有在I/O设备完成了指定的I/O操作任务后进程才能继续执行，则该进程在启动了I/O操作后，便自动进入阻塞状态去等待。在I/O操作完成后，再由中断处理程序或中断进程将该进程唤醒。,3)新数据尚未到达对于相互合作的进程，如果其中一个进程需要先获得另一(合作)进程提供的数据后才能对数据进行处理，则只要其所需数据尚未到达，该进程只有(等待)阻塞。例如，有两个进程，进程A用于输入数据，进程B对输入数据进行加工。假如A尚未将数据输入完毕，则进程B将因没有所需的处理数据而阻塞；一旦进程A把数据输入完毕，便可去唤醒进程B。,4)无新工作可做系统往往设置一些具有某特定功能的系统进程，每当这种进程完成任务后，便把自己阻塞起来以等待新任务到来。例如，系统中的发送进程，其主要工作是发送数据，若已有的数据已全部发送完成而又无新的发送请求，这时(发送)进程将使自己进入阻塞状态；仅当又有进程提出新的发送请求时，才将发送进程唤醒。,2进程阻塞过程正在执行的进程，当发现上述某事件时，由于无法继续执行，于是进程便通过调用阻塞原语block把自己阻塞。可见，进程的阻塞是进程自身的一种主动行为。进入block过程后，由于此时该进程还处于执行状态，所以应先立即停止执行，把进程控制块中的现行状态由“执行”改为“阻塞”，并将PCB插入阻塞队列。如果系统中设置了因不同事件而阻塞的多个阻塞队列，则应将本进程插入到具有相同事件的阻塞(等待)队列。最后，转调度程序进行重新调度，将处理机分配给另一就绪进程并进行切换，亦即，保留被阻塞进程的处理机状态(在PCB中)，再按新进程的PCB中的处理机状态设置CPU的环境。,3进程唤醒过程当被阻塞进程所期待的事件出现时，如I/O完成或其所期待的数据已经到达，则由有关进程(比如用完并释放了该I/O设备的进程)调用唤醒原语wakeup()，将等待该事件的进程唤醒。唤醒原语执行的过程是：首先把被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态由阻塞改为就绪，然后再将该PCB插入到就绪队列中。应当指出，block原语和wakeup原语是一对作用刚好相反的原语。因此，如果在某进程中调用了阻塞原语，则必须在与之相合作的另一进程中或其他相关的进程中安排唤醒原语，以能唤醒阻塞进程；否则，被阻塞进程将会因不能被唤醒而长久地处于阻塞状态，从而再无机会继续运行。,2.2.4进程的挂起与激活1进程的挂起当出现了引起进程挂起的事件时，比如，用户进程请求将自己挂起，或父进程请求将自己的某个子进程挂起，系统将利用挂起原语suspend()将指定进程或处于阻塞状态的进程挂起。挂起原语的执行过程是：首先检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；对于活动阻塞状态的进程，则将之改为静止阻塞。为了方便用户或父进程考查该进程的运行情况而把该进程的PCB复制到某指定的内存区域。最后，若被挂起的进程正在执行，则转向调度程序重新调度。,2进程的激活过程当发生激活进程的事件时，例如，父进程或用户进程请求激活指定进程，若该进程驻留在外存而内存中已有足够的空间时，则可将在外存上处于静止就绪状态的该进程换入内存。这时，系统将利用激活原语active()将指定进程激活。激活原语先将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，便将之改为活动就绪；若为静止阻塞，便将之改为活动阻塞。假如采用的是抢占调度策略，则每当有新进程进入就绪队列时，应检查是否要进行重新调度，即由调度程序将被激活进程与当前进程进行优先级的比较，如果被激活进程的优先级更低，就不必重新调度；否则，立即剥夺当前进程的运行，把处理机分配给刚被激活的进程。,2.3进 程 同 步,2.3.1进程同步的基本概念1两种形式的制约关系在多道程序环境下，当程序并发执行时，由于资源共享和进程合作，使同处于一个系统中的诸进程之间可能存在着以下两种形式的制约关系。(1)间接相互制约关系。同处于一个系统中的进程，通常都共享着某种系统资源，如共享CPU、共享I/O设备等。所谓间接相互制约即源于这种资源共享，例如，有两个进程A和B，如果在A进程提出打印请求时，系统已将惟一的一台打印机分配给了进程B，则此时进程A只能阻塞；一旦进程B将打印机释放，则A进程才能由阻塞改为就绪状态。,(2)直接相互制约关系。这种制约主要源于进程间的合作。例如，有一输入进程A通过单缓冲向进程B提供数据。当该缓冲空时，计算进程因不能获得所需数据而阻塞，而当进程A把数据输入缓冲区后，便将进程B唤醒；反之，当缓冲区已满时，进程A因不能再向缓冲区投放数据而阻塞，当进程B将缓冲区数据取走后便可唤醒A。,2.临界资源在第一章中我们曾经介绍过，许多硬件资源如打印机、磁带机等，都属于临界资源(Critical Resouce)，诸进程间应采取互斥方式，实现对这种资源的共享。下面我们将通过一个简单的例子来说明这一过程。,生产者-消费者(producer-consumer)问题是一个著名的进程同步问题。它描述的是：有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池，生产者进程将它所生产的产品放入一个缓冲区中；消费者进程可从一个缓冲区中取走产品去消费。尽管所有的生产者进程和消费者进程都是以异步方式运行的，但它们之间必须保持同步，即不允许消费者进程到一个空缓冲区去取产品，也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。,我们可利用一个数组来表示上述的具有n个(0，1，n-1)缓冲区的缓冲池。用输入指针in来指示下一个可投放产品的缓冲区，每当生产者进程生产并投放一个产品后，输入指针加1；用一个输出指针out来指示下一个可从中获取产品的缓冲区，每当消费者进程取走一个产品后，输出指针加1。由于这里的缓冲池是组织成循环缓冲的，故应把输入指针加1表示成 in:=(in+1)mod n；输出指针加1表示成out:=(out+1)mod n。当(in+1)mod n=out时表示缓冲池满；而in=out则表示缓冲池空。此外，还引入了一个整型变量counter，其初始值为0。每当生产者进程向缓冲池中投放一个产品后，使counter加1；反之，每当消费者进程从中取走一个产品时，使counter减1。生产者和消费者两进程共享下面的变量：,Var n，integer；type item=；var buffer:array0，1，n-1 of item；in，out:0，1，n-1；counter:0，1，n；,指针in和out初始化为1。在生产者和消费者进程的描述中，noop是一条空操作指令，while condition do no-op语句表示重复的测试条件(condication)，重复测试应进行到该条件变为false(假)，即到该条件不成立时为止。在生产者进程中使用一局部变量nextp，用于暂时存放每次刚生产出来的产品；而在消费者进程中，则使用一个局部变量nextc，用于存放每次要消费的产品。,consumer:repeat while counter=0 do no-op；nextc:=bufferout；out:=(out+1)mod n；counter:=counter-1；consumer the item in nextc；until false；,虽然上面的生产者程序和消费者程序在分别看时都是正确的，而且两者在顺序执行时其结果也会是正确的，但若并发执行时就会出现差错，问题就在于这两个进程共享变量counter。生产者对它做加1操作，消费者对它做减1操作，这两个操作在用机器语言实现时，常可用下面的形式描述：,register1:=counter；register2:=counter；register1:=register1+1；register2:=register2-1；counter:=register1；counter:=register2；,假设counter的当前值是5。如果生产者进程先执行左列的三条机器语言语句，然后消费者进程再执行右列的三条语句，则最后共享变量counter的值仍为5；反之，如果让消费者进程先执行右列的三条语句，然后再让生产者进程执行左列的三条语句，则counter值也还是5，但是，如果按下述顺序执行：,register1:=counter；(register1=5)register1:=register1+1；(register1=6)register2:=counter；(register2=5)register2:=register2-1；(register2=4)counter:=register1；(counter=6)counter:=register2；(counter=4),正确的counter值应当是5，但现在是4。读者可以自己试试，倘若再将两段程序中各语句交叉执行的顺序改变，将可看到又可能得到counter=6的答案，这表明程序的执行已经失去了再现性。为了预防产生这种错误，解决此问题的关键是应把变量counter作为临界资源处理，亦即，令生产者进程和消费者进程互斥地访问变量counter。,3临界区由前所述可知，不论是硬件临界资源，还是软件临界资源，多个进程必须互斥地对它进行访问。人们把在每个进程中访问临界资源的那段代码称为临界区(critical section)。显然，若能保证诸进程互斥地进入自己的临界区，便可实现诸进程对临界资源的互斥访问。为此，每个进程在进入临界区之前，应先对欲访问的临界资源进行检查，看它是否正被访问。如果此刻该临界资源未被访问，进程便可进入临界区对该资源进行访问，并设置它正被访问的标志；如果此刻该临界资源正被某进程访问，则本进程不能进入临界区。因此，必须在临界区前面增加一段用于进行上述检查的代码，把这段代码称为进入区(entry section)。相应地，在临界区后面也要加上一段称为退出区(exit sectio