计算机操作系统原理培训及实操第2章.pdf
第2章 处 理 机 管 理第2章 处 理 机 管 理2.1 进程概念进程概念2.2 OS内核及进程控制内核及进程控制2.3 进程通信进程通信2.4 进程调度进程调度2.5 线程线程2.6 死锁死锁2.7 作业管理作业管理2.8 操作系统的接口操作系统的接口第2章 处 理 机 管 理2.1 2.1 进进 程程 概概 念念2.1.1 2.1.1 进程的引入进程的引入 在计算机系统中，为了充分地利用系统资源，CPU与外设必须并行工作。由于多道程序系统的出现，使得系统内部的活动变得复杂起来。例如，一个CPU可以在多道程序中快速切换，每道程序每次仅运行很短的时间，使得多道程序在一个小的时间段内都可以得到运行，给用户一种并行的错觉，称为并发执行。又如，当一道程序利用外设进行输入、输出时，CPU可以为另外一道程序工作，这是CPU与I/O设备的并行操作，也要求CPU在多道程序间快速切换。硬件的并行操作与程序的并发执行都需要CPU在多道程序中快速切换，原有的程序概念无法做到这一点，因此我们引入一个新概念进程。第2章 处 理 机 管 理 1 1前趋图前趋图(ProcedenceProcedence Graph)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章 处 理 机 管 理图2-1 例图(a)(b)(c)S2S3S4S1S5S6S7S1S2S3S4S1S2S3第2章 处 理 机 管 理 2 2程序的顺序执行程序的顺序执行 1)程序的顺序执行 所谓程序的顺序执行，是指一个程序运行时独占整个系统资源,处理机严格按照程序所规定的顺序进行操作。在一个程序段中，只有前面的一个操作执行完，才能进行后面一个操作。在一个程序段的执行过程中，不能插入其它程序段中的操作。例如，对于下述程序段:S1:READ（X，Y）；S2:C=X+Y；S3:PRINT C；第2章 处 理 机 管 理 其中S2必须在X、Y被赋值后才能执行，同样，S3也必须在C被赋值后才能执行。因此，这个程序段的执行顺序如图2-2所示。图2-2 一个程序段中语句的顺序执行S1S2S3第2章 处 理 机 管 理 类似地，在一个系统中，若要执行几个程序段，只有当一个程序段执行完后才能执行另一个程序段中的操作。例如，一个程序段通常由输入(I)、计算(C)、输出(P)等操作组成，两个程序段的顺序执行则如图2-3所示。图2-3 两个程序段的顺序执行I1C1P1I2C2P2第2章 处 理 机 管 理 2)程序顺序执行的特征 顺序性：处理机的操作严格按照程序所规定的操作顺序执行，时间上完全有序,即只有前一个操作执行完以后，才能进行后继操作。封闭性：程序执行时独占系统资源，系统内各种资源的状态（初始状态除外）只能被本程序所改变，因此其执行结果不受外界因素的干扰。结果可再现性：只要程序执行的环境与初始状态不变,当重复执行时,所获得的结果相同,与执行速度无关。第2章 处 理 机 管 理 3 3程序的并发执行程序的并发执行 并行操作是指多个操作在计算机系统的各个硬件部件上同时进行。例如，CPU与CPU的并行操作，CPU与I/O设备的并行操作，这是真正意义上的“同时”操作，称之为并行操作。我们将要介绍的并发执行是指在一个时间段内，多个程序段在计算机系统中“一起”执行。例如，在一个时间段内，一个CPU在为多道程序工作，而在某一个瞬间，一个CPU只能运行一道程序，它只是在多道程序中快速切换，给人以CPU“同时”运行几道程序的感觉。每个程序内部仍是按顺序执行，但是多个程序的执行过程是可以交叉的，这是一种伪并行，称之为并发执行。第2章 处 理 机 管 理 1)并发执行 若干程序段在执行时间上有重叠,即一个程序段的执行过程中插入了其它程序的操作，称为并发执行，如图2-4所示。程序P与程序Q在t2t4之间是并发执行的，程序Q与程序R在t3t5之间是并发执行的，而在t3t4之间，程序P、程序Q与程序R是并发执行的。图2-4 若干程序段的并发执行t1Pt2t3t4Qt5t6RT第2章 处 理 机 管 理 2)程序并发执行的特征 若干个程序段的并发执行，产生了一些与程序顺序执行时不同的特征：顺序性：多个程序段并发执行时，每个程序段中语句的顺序执行仍然保持，但是多个程序段之间不再保持顺序执行的关系。间断性：多个程序段并发执行时，由于共享资源或由于相互合作而形成执行时的相互制约关系，使得每个程序段执行时产生了间断性。例如，在单处理机系统中，多个程序段并发执行，当CPU执行一道程序时，必然导致其它程序暂时不能执行，这将使得程序具有“执行暂停执行”这种间断的活动规律。第2章 处 理 机 管 理 非封闭性：多个程序段并发执行时，每个程序段不再独占系统资源,执行时受外界因素影响。例如，当一个用户的程序段执行中使用某个I/O设备时，其他用户的程序段申请使用该设备，就必须等待。不可再现性：多个程序段并发执行时，产生了非封闭性，不再独占系统资源，此时，即使程序执行的环境与初始状态不变，重复执行时运算速度通常也不可再现，若运算结果与执行速度有关，则可能会被改变。第2章 处 理 机 管 理 例如，两个并发执行的程序段共享一个变量，当两个程序段推进速度发生变化时，可能导致程序中引用共享变量的语句得到不同的结果，即程序运行结果不确定。我们通过下面一个例子来说明这种现象发生的过程。设A与B是两个可以并发执行的程序段,N是共享变量。A:B:N=N+1；PRINT N；N=0；第2章 处 理 机 管 理 因为程序段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；第2章 处 理 机 管 理 若程序段A中的N=N+1语句在程序段B的PRINT N与N=0语句之间执行，则输出为5，N为0；若程序段A中的N=N+1语句在程序段B的N=0之后执行，则输出为5，N为1。这样的结果用户是不能接受的。我们需要的是程序能并发执行，同时还要保证其具有可再现性。第2章 处 理 机 管 理4 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章 处 理 机 管 理 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 第2章 处 理 机 管 理 3)Bernstein条件 1966年，Bernstein提出了程序可以并发执行的条件，简称Bernstein条件。若两个程序段P1和P2能满足以下条件：R(P1)W(P2)=；R(P2)W(P1)=；W(P1)W(P2)=；则P1和P2可以并发执行，同时保证结果具有可再现性。第2章 处 理 机 管 理 例如，有四条语句：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章 处 理 机 管 理图2-5 具有四条语句的前趋图S1S2S3S4第2章 处 理 机 管 理 5 5进程定义与特征进程定义与特征 1)进程定义 由于计算机众多硬件并行操作及多道程序的并发执行，使得“程序”的概念已经无法刻画程序执行中的活动与变化情况，因此引入了进程的概念。1961年，进程的概念首先由美国麻省理工学院在MULTICS系统中引入，得到人们的普遍重视并广为采用。随后，许多人都对进程下过定义，如：进程是可以并发执行的程序在一个数据集合上的运行过程。第2章 处 理 机 管 理 进程是程序的一次执行过程。进程是可参与并发执行的程序。进程是一个程序及其数据在处理机上执行时所发生的活动。进程是在给定初始状态和内存区域的条件下，可以并发执行的程序的一次执行过程。根据1978年在庐山召开的全国操作系统会议的讨论，认为“进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动”。第2章 处 理 机 管 理 2)进程的特征 进程是与程序完全不同的新概念，它具有以下特征：并发性：在内存中的多个进程能在一段时间内同时运行。并发性使得进程的程序执行过程随时会被中断。多个进程的程序可以并发执行，这是进程最基本的特征之一，而程序是不能并发执行的。第2章 处 理 机 管 理 动态性：进程是程序的一次执行过程，“动态”是进程另一个最基本的特征。当要完成某项任务时为之创建进程，由处理机调度程序来选择要调度的进程并运行该进程的程序，当资源得不到满足时暂停执行，资源能够满足时，继续执行，直至任务完成后撤消该进程。因此，进程由创建到消亡是有一定生命期的，在生命期间进程是一个活动实体。而程序是可以永久存放于某种介质上的有序指令集合，是一个静态实体。第2章 处 理 机 管 理 独立性：进程是一个能够独立运行的基本单位，即只有进程才能被独立调度运行及独立获得资源。在系统中，除了系统提供的服务外，只有进程在活动，而程序是不能作为调度运行和获得资源的基本单位的。异步性：这是指进程以各自独立的、不可预知的速度向前推进。这一特性基于进程的并发性，需要系统采取必要的措施，以保证各个进程的程序之间能协调运行。第2章 处 理 机 管 理 结构特征：进程实体中包含有程序段、数据段，还必须有一个存放进程生命期间管理信息的数据结构进程控制块PCB（Process Control Block）。进程控制块PCB能够保证进程并发执行及在生命期间进程活动的顺利进行。不同的进程是以PCB来区别的，不同的PCB代表不同的进程。第2章 处 理 机 管 理2.1.2 2.1.2 进程的描述进程的描述 1 1进程的组成进程的组成 进程由三部分组成：进程控制块PCB、程序段和数据段，如图2-6所示。一个进程一经被创建，就有如下三部分内容：(1)PCB表：为便于管理，PCB表被放在不同的队列或状态中。新建进程的PCB表被放在就绪队列中，根据进程在活动过程中所处的状态，PCB表可被放在就绪队列或阻塞队列中，也可以处于执行状态中。(2)可执行的程序段：其首地址由PCB表中程序地址信息字段直接或间接指出。(3)可加工的数据段：其首地址由PCB表中数据地址信息字段直接或间接指出。有的进程可以没有数据段。第2章 处 理 机 管 理图2-6 进程的组成PCB程序段数据段第2章 处 理 机 管 理 进程控制块PCB是为描述进程动态变化过程以及对进程进行控制与管理而设的数据结构。进程与PCB表一一对应，操作系统根据PCB表了解进程的存在，它是进程是否存在的惟一标志。PCB表常驻内存，属于系统空间，只有操作系统程序才能够访问，用户程序不得访问。进程的程序段反映了进程的功能，数据段是程序加工的对象，均属于用户空间。运行时可以根据需要全部地或者部分地放在内存中。进程处于非执行状态时，如果内存有剩余空间，它的程序段和数据段放在内存，如果内存无剩余空间，则可以放在外存。进程处于执行状态时，程序段与数据段必须有一部分放在内存，以方便执行。程序段和数据段在内存与外存中的物理地址是由PCB表的地址信息字段指明的。第2章 处 理 机 管 理 2 2PCBPCB结构及其组织形式结构及其组织形式 PCB表记录了描述进程情况及控制进程运行所需要的全部信息，操作系统根据PCB提供的信息实施对进程的控制与管理。在一个系统中，PCB表的个数是有限的。当一个进程被创建时，为其分配一个空闲的PCB表，当进程被撤消时，回收其所占用的PCB表。PCB表被系统访问的频率很高，因此是常驻内存的。操作系统专门开辟一个PCB表区，每个PCB是一片连续的存储单元。根据PCB表所对应的进程的运行状态，所有的PCB表被组成若干个队列，如就绪队列、阻塞队列等，空闲的PCB表组成一个空闲队列，以备创建进程时进行申请使用和撤消进程时进行回收使用。第2章 处 理 机 管 理 1)PCB的结构 PCB是一个线性表结构，通常包括以下内容：进程标识符：分为外部标识符和内部标识符。外部标识符由创建进程者提供，通常由字母、数字等组成，在用户或其它进程访问该进程时使用。内部标识符是一个整数。在操作系统的PCB表区中，有多个PCB表，每个PCB表有一个序号，通常将这个序号做为内部标识符，以方便系统使用。程序地址：进程的程序部分在内存及外存的地址，或描述程序地址信息的段表地址、页表地址、索引表地址等。第2章 处 理 机 管 理 数据地址：进程的数据部分在内存及外存的地址，或描述数据地址信息的段表地址、页表地址、索引表地址等。状态：进程当前所处的状态，即就绪状态、执行状态及阻塞状态，已经被创建的进程的状态必为此三者之一。CPU状态保护区：CPU状态信息主要由通用寄存器、程序计数器PC、程序状态字PSW以及用户栈指针等组成，也称为中断点现场信息。CPU状态保护区用以保护进程被中断而暂停执行时CPU的状态信息，以便进程重新获得CPU时能够重布现场，从上次被中断处继续执行。第2章 处 理 机 管 理 进程优先级：进程优先级是用以描述进程使用处理机的优先级别的整数，是优先级调度算法中调度的依据。通常数值越小，优先级别越高。优先级可以处理成不变的，称为静态优先级，也可以处理成可变的，称为动态优先级。通信信息：进程通信时需要使用的信息，包括标志位、信号或信号量、消息队列信息等。如消息缓冲通信机制中，在进程的PCB表中，需要有消息队列队首指针、消息个数及互斥使用消息队列的信号量等。资源信息：进程对资源的需求及已经分配资源的清单。第2章 处 理 机 管 理 队列指针：除了执行状态的进程外，其余的进程PCB表都处于某一就绪队列或某一阻塞队列中。队列指针用于指向进程所在队列中下一个PCB表的首地址。家族指针：进程在运行过程中可以创建新进程来协同完成同一任务。创建者称为父进程，被创建者称为子进程。父进程PCB表中有指向子进程的PCB表的指针，子进程的PCB表中有指向父进程的PCB表的指针，这就是家族指针，它可以将一个家族的进程联系起来，形成进程家族树。第2章 处 理 机 管 理 2)PCB表的组织形式 在内存的系统空间中设有PCB表区，表区中的PCB表的个数根据系统的大小来设置。为了对进程实施有效的管理，通常将它们用某种方式组织起来，目前常用方式有如下几种：链接方式：用PCB表中的队列指针项将具有相同状态的进程的PCB表链接起来，这样PCB表就形成就绪队列、空闲队列及阻塞队列等。其中，空闲队列是一个，而就绪队列与阻塞队列可以是多个。例如，可以将不同优先级的进程的PCB表排在不同的就绪队列中，也可以将阻塞原因不同的进程的PCB表排在不同的阻塞队列中。系统中的某些固定单元分别指向各队列队首地址及执行状态进程的PCB表的首地址。第2章 处 理 机 管 理 以链接方式组织的PCB表如图2-7所示。其中，处于执行状态的是PCB1，处于就绪状态的是PCB3、PCB4、PCB2，处于阻塞状态的是PCB7、PCB6、PCB5，处于空闲状态的是PCB8、PCB9等。索引方式：根据进程的状态，在内存中建立相应的索引表，系统中的某些固定单元保存各索引表的首地址。各索引表的表目中记录相应状态的PCB表的首地址。以索引方式组织的PCB表如图2-8所示。对于图2-7中PCB的组织情况，可以用图2-9表示。第2章 处 理 机 管 理图2-7 链接方式组织PCB表示意图PCB1PCB2PCB3 4PCB4PCB5PCB6PCB7PCB8PCB92569空闲队列指针阻塞队列指针就绪队列指针执行指针第2章 处 理 机 管 理图2-8 索引方式组织PCB表示意图PCB1PCB2PCB3PCB4PCB5PCB6PCB7342就绪索引表765阻塞索引表执行指针就绪表指针阻塞表指针第2章 处 理 机 管 理图2-9 进程PCB表组织的描述执行就绪阻塞PCB1PCB3PCB4PCB2PCB7PCB6PCB5第2章 处 理 机 管 理 3 3进程的状态及其变迁进程的状态及其变迁 1)进程的基本状态及其变迁 进程有三个基本状态：就绪状态、执行状态与阻塞状态。进程的基本状态及其变迁如图2-10所示。进程在运行过程中必处于这三个基本状态之一。图2-10 进程的基本状态及其变迁图执行被抢占时钟中断就绪阻塞某等待事件完成进程调度某等待事件发生(如I/O请求、P操作等）(如I/O完成、V操作等）第2章 处 理 机 管 理 就绪状态：进程获得必要资源，例如内存等，已经具备了执行条件，只是没有空闲的CPU，处于等待CPU的状态。在系统中，将处于就绪状态的多个进程的PCB表排成一个队列，或按照某种规则排在不同的队列中，这些队列称为就绪队列。执行状态：进程已经获得必要的资源及CPU，它的程序正在执行中，这时进程的状态称为执行状态。在多处理机系统中，可以有多个进程处于执行状态。在单处理机系统中，只能有一个进程处于执行状态，系统应尽量保证一个CPU上总有一个处于执行状态的进程，使CPU得到充分的利用。第2章 处 理 机 管 理 阻塞状态：进程因某等待事件发生（例如I/O请求、某些原语操作等）而处于暂停执行的状态，此时即使将CPU分配给它，它的程序也无法执行。在系统中，将处于阻塞状态的进程的PCB表排成一个队列，或因阻塞原因不同而将进程的PCB表排在不同的队列中，这些队列称为阻塞队列。进程的三个基本状态有下列四种可能的状态变迁：就绪执行：进程调度程序按某种算法将处于就绪队列的某个进程选出，重布现场，把CPU分配给它，该进程便由就绪状态转变为执行状态。第2章 处 理 机 管 理 执行就绪：处于执行状态的进程因时间片用完而被中断，将该进程的PCB表插入就绪队列，该进程便由执行状态转变为就绪状态。如果在采用抢占式调度策略的系统中，进入就绪队列的进程的优先级高于正处在执行状态的进程，可抢占CPU，将执行状态进程的PCB表插入就绪队列，由执行状态转变为就绪状态。第2章 处 理 机 管 理 执行阻塞：进程在某等待事件发生（例如I/O请求、原语P操作等）而无法执行时，会由执行状态转变为阻塞状态，在等待该事件的完成过程中将放弃CPU的使用权，以免出现“忙等”。阻塞就绪：进程在某等待事件完成，被阻塞的原因解除（例如I/O完成、原语V操作等）时，将阻塞状态进程的PCB表插入就绪队列，由阻塞状态转变为就绪状态，重新获得被调度的权力。进程运行期间会不断地从一个状态转变为另一个状态，它可以多次处于上述三个基本状态中。当一个进程完成，或者在执行过程中出现意外情况而异常结束时，进程被撤消，生命期结束。第2章 处 理 机 管 理 2)进程的活动与静止状态 为了便于研究系统的工作状态是否正常、效率如何以及方便用户检查自己作业的执行情况或对进程进行修改等工作，需要使某些进程暂时处于静止状态，即让正在执行的进程停止执行，使处于就绪状态的进程不再接受调度，使处于阻塞状态的进程不再转变为就绪状态，我们把这种情况称为将进程挂起，使进程处于静止状态。当处于静止状态的进程被激活时，它将重新处于活动状态中。具有挂起功能的进程状态及其变迁如图2-11所示。第2章 处 理 机 管 理图2-11 具有静止状态和活动状态的进程状态变迁图活动就绪激活静止就绪挂起解 封活动阻塞激活静止阻塞挂起解 封执行被抢占时钟中断某等待事件发生进程调度挂起第2章 处 理 机 管 理 上述进程状态变迁图除了图2-10所示的四种可能的状态变迁外，又增加了下面六种情况：活动就绪静止就绪：当进程处于未被挂起的就绪状态时，称为活动就绪状态，此时进程可以接受调度。当处于活动就绪状态的进程被挂起时，该进程便转变为静止就绪状态，此时进程不再接受调度。通常，新建进程进入活动就绪状态，以便尽快得到调度。第2章 处 理 机 管 理 活动阻塞静止阻塞：当进程处于未被挂起的阻塞状态时，称为活动阻塞状态，此时进程可以因某等待事件的完成而转变为活动就绪状态。当处于活动阻塞状态的进程被挂起时，该进程便转变为静止阻塞状态。静止阻塞静止就绪：处于静止阻塞状态的进程在所期待的事件出现后，将从静止阻塞状态转变为静止就绪状态，仍然处于静止状态。静止就绪活动就绪：处于静止就绪状态的进程被激活后，该进程转变为活动就绪状态，进程可以重新接受调度。第2章 处 理 机 管 理 静止阻塞活动阻塞：处于静止阻塞状态的进程被激活后，该进程转变为活动阻塞状态，当所期待的事件完成后，它将从活动阻塞状态转变为活动就绪状态。执行静止就绪：处于执行状态的进程被挂起后处于静止就绪状态，暂停执行，不再接受调度。以上是将就绪和阻塞状态分别分成静止及活动两个状态，可以看作对就绪状态与阻塞状态的细化。若我们将就绪状态分为高、中、低优先级队列，阻塞队列分为不同原因的阻塞队列，这是又一种对就绪、阻塞状态的细化方法。在UNIX系统中，不但对就绪状态、阻塞状态进行了细化，对执行状态也进行了细化，详见第6章的图6-3。第2章 处 理 机 管 理2.2 2.2 OSOS内核及进程控制内核及进程控制2.2.1 2.2.1 OSOS内核内核 1 1处理机的执行状态处理机的执行状态 处理机有核心态和用户态两种执行状态。核心态：由设备中断、异常、自陷、信号（即软中断）等进入，这种状态具有较高的特权，允许使用全部机器资源与机器指令，是操作系统程序执行时的状态。用户态：处理机在这种状态下只能使用指定的机器指令，不能使用如I/O、改变机器状态、修改存储保护等指令，并且只允许访问用户自己的存储区，是用户程序执行时的状态。第2章 处 理 机 管 理 2 2操作系统内核操作系统内核 1)内核定义 在第1章中，我们了解到没有配置任何软件的计算机称为裸机，操作系统是在裸机上添加多层软件形成的。通常将与硬件紧密相关的部分，如中断处理程序、设备驱动程序及进程从创建到撤消包括进程状态变迁中用到的公共操作等集中在一起，常驻内存，作为裸机上添加的第一层软件，叫做内核。第2章 处 理 机 管 理 2)内核功能 内核主要是为进程创造一个适宜的运行环境。内核完成中断处理、进程控制、进程通信、进程调度等操作及内存的分配与回收和设备的驱动等。这些功能通常用原语来实现。3)原语 原语是完成特定功能的程序段，如同扩充的机器指令广义指令一样，但是原语是不可分割的原子操作，即操作时要屏蔽中断。系统中有各种不同的原语，如进程控制的原语、进程通信的原语等。第2章 处 理 机 管 理2.2.2 2.2.2 进程控制进程控制 1 1进程控制功能进程控制功能 进程控制是操作系统内核中的组成部分。在操作系统中有两类进程：系统进程和用户进程。由进程控制对系统中所有进程实施有效地管理。进程控制主要完成创建进程、撤消进程以及实现进程状态之间的转换等工作。第2章 处 理 机 管 理 2 2进程控制方式进程控制方式 进程控制的方式有管理程序负责制和进程家族制两种。1)管理程序负责制 管理程序负责制如图2-12所示。在管理程序负责制的系统中，当作业进入系统时，由管理程序为其创建进程、运行进程，直至完成任务予以撤消。管理程序负责制的特点是进程之间关系平等，由管理程序统一管理。第2章 处 理 机 管 理图2-12 管理程序负责制管理程序第2章 处 理 机 管 理 2）进程家族制 图2-13表示进程家族制中的一棵进程树。根结点为祖先进程，创建进程者为父进程，被创建者为子进程。进程家族制的特点是层次清晰、进程控制灵活、资源分配严格。进程家族制中，子进程由父进程创建与撤消，它的活动完全由父进程控制，子进程只能使用父进程的资源。目前，这是一种常用的管理与控制进程的方式。第2章 处 理 机 管 理图2-13 进程家族树HIDJKEFGBCAL第2章 处 理 机 管 理2.2.3 2.2.3 进程控制原语进程控制原语 不同的操作系统中，使用的进程控制原语是不完全相同的，下面介绍几种常用的进程控制原语。1 1创建原语创建原语 1)功能 创建原语的功能是创建一个进程。第2章 处 理 机 管 理 2)引起创建的事件 在采用进程家族制的系统中，进程一般由父进程创建。引起创建的事件如下：当终端用户登录时，由终端子进程创建用户进程；批处理系统中，作业调度程序为选出的作业创建进程；系统为合法用户建立服务进程；进程运行时可以创建子进程来协同完成任务。第2章 处 理 机 管 理 3)创建原语的实现过程 创建原语需要一些参数，如进程外部标识符、CPU初始状态S0、初始内存区M0、所需资源R0、优先级K0等。图2-14 创建原语实现过程在PCB表区索取一张空表申请内存；调入程序和数据；分配其它必要资源初始化PCB表将PCB表插入就绪队列返回第2章 处 理 机 管 理 2 2撤消原语撤消原语 1)功能 撤消原语的功能是撤消一个或者多个进程。撤消策略有两种：一种是撤消一个具有指定标识符的进程，另一种是撤消一个进程及其所有子孙进程，以防止形成不可控制的孤儿进程。为了更好地保证系统的安全，通常使用后者。第2章 处 理 机 管 理 2)撤消进程的典型事件 进程完成任务，正常结束时被撤消；进程运行出现故障及错误时，被迫终止运行而被撤消；进程运行时因外界干预而撤消，如系统发生死锁时需要撤消一些进程、父进程撤消子进程等。3)撤消原语的实现过程 撤消原语的参数为撤消进程的标识符n。撤消原语的实现过程如图2-15所示。第2章 处 理 机 管 理图2-15 撤消原语实现过程找出撤消进程n的PCB表n是执行状态？中断CPU,停止执行置重新调度标志为真撤消n的子孙进程归还资源(系统、父进程）将PCB表移出所在队列归还给系统调度标志为真?n为就绪？n为阻塞？NYNY出错处理YNNY进程调度程序入口返回第2章 处 理 机 管 理 3 3阻塞原语阻塞原语 1)功能 阻塞原语完成进程从执行状态到阻塞状态的转变，这时处于执行状态的进程自身被阻塞。阻塞原语能够暂时剥夺执行进程使用CPU的权力，将其置为阻塞状态并插入阻塞队列，引起进程调度。第2章 处 理 机 管 理 2)引起阻塞的典型事件 进程请求I/O服务，无论获得I/O服务与否，通常都要暂时放弃CPU；某些原语操作，如P操作等可能引起进程阻塞；某些系统进程工作时占用CPU，无事可做时，则调用阻塞原语将自己阻塞。第2章 处 理 机 管 理3)阻塞原语的实现过程图2-16 阻塞原语实现过程找出执行进程的PCB表中断CPU，暂停执行,保存CPU现场将执行进程置为阻塞状态将PCB插入该事件阻塞队列进程调度程序人口第2章 处 理 机 管 理 4 4唤醒原语唤醒原语 1)功能 唤醒原语将进程从阻塞状态转变为就绪状态。它将唤醒进程的PCB表从阻塞队列移出，置为就绪状态，插入就绪队列，准备接受进程调度程序的下一次调度。2)唤醒进程的典型事件 进程请求的I/O操作完成；某些原语操作，如V操作等可以解封阻塞进程；某些系统进程有事可做时，用唤醒原语将其唤醒。第2章 处 理 机 管 理3)唤醒原语的实现过程图2-17 唤醒原语实现过程找出唤醒进程的PCB表将PCB表从阻塞队列移出将进程PCB表中状态置为就绪将PCB表插入就绪队列返回第2章 处 理 机 管 理5 5挂起原语挂起原语1)功能根据进程所处状态，挂起原语可以有三种处理：完成进程从活动就绪状态到静止就绪状态的转变;完成进程从活动阻塞状态到静止阻塞状态的转变;若进程是执行状态，则转变为静止就绪状态。第2章 处 理 机 管 理 2)挂起对象与挂起方式 挂起对象：进程请求挂起自身；父进程挂起子进程。挂起方式如下：挂起一个具有指定标识符的进程；挂起某个进程及其所有子孙进程。采用这种挂起方式可以避免进程被挂起而其子孙进程仍在活动而带来的问题。第2章 处 理 机 管 理 3)实现过程 下面对于挂起一个具有指定标识符的进程的挂起方式予以实现。挂起原语的参数为进程标识符n。图2-18 挂起原语实现过程找出挂起进程n的PCB表取PCB表中的进程状态n是执行状态？Y中断CPU，暂停执行并保留CPU现场执行状态静止就绪活动就绪静止就绪n为活动就绪？n为活动阻塞？活动阻塞静止阻塞NYNY出错处理N进程调度程序入口返回第2章 处 理 机 管 理3)激活原语实现过程激活原语的参数为进程标识符n。图2-19 激活原语实现过程找出激活进程n的PCB表激活对象在外存?由外存调入内存n为静止就绪?静止就绪活动就绪激活进程优先级较运行进程高?中断CPU，暂停执行并保留CPU现场进程调度程序入口NYYn为静止阻塞？静止阻塞活动阻塞YN出错处理Y返回NN第2章 处 理 机 管 理2.3 2.3 进进 程程 通通 信信2.3.1 2.3.1 进程同步与互斥进程同步与互斥 1.1.进程之间的关系进程之间的关系 合作关系：一组进程协同完成一个任务，它们之间是合作关系。这种情况需要对于相互合作的多个进程的执行次序进行协调，这样就必须交换信息，以免出现时间上的差错。例如，一个计算进程和一个打印进程共同完成一个任务。若打印进程要打印时，而计算进程尚未计算出结果，打印进程就无法打印，但是这种要求会传达给计算进程。当计算进程计算出结果时，通知打印进程，则打印进程就可以工作了。这种“传达”与“通知”就是在交换信息。第2章 处 理 机 管 理 竞争关系：多个进程因为使用共享资源而产生竞争关系，在抢占使用资源时可能导致使用失败，都达不到目的，因而要有信息交换以保证各得其所。例如，多个进程共同使用一台打印机，当一个进程打印时，其它进程不能使用，否则打印内容会混在一起。在这种情况下，就要求当前正在使用打印机的进程与其它要求打印的进程之间交换信息，才能协调对打印机的使用。第2章 处 理 机 管 理 同步：多个进程在执行过程中，为了共享资源与相互合作而在执行次序上的协调，称为同步，即共享同一资源的进程和相互关联进程以通信手段来保障完成任务时保持一种固定的时间关系。互斥：当某一进程访问某一资源时，不允许别的进程同时访问，这种限制称为互斥，即多个进程在访问某些资源（如临界资源）时，也要有一种执行次序上的协调，当一个进程访问完毕，另一个进程才能访问。所以就其本质来讲，互斥仍是一种同步。在一个系统中，必须有相应的方法或机制来协调进程的执行次序。第2章 处 理 机 管 理 2 2临界资源与临界区临界资源与临界区 1)临界资源 一次仅允许一个进程访问的资源称为临界资源。计算机的许多硬件资源都被处理成临界资源，如打印机、磁带机等。例如，若打印机允许若干用户同时打印，则打印结果会混在一起，不易分辨，给用户带来许多不便。系统中还有许多软资源，如共享变量、表格、队列、栈等也被处理成临界资源，以避免多个进程对它们访问时出现问题。第2章 处 理 机 管 理 例如，若有两个进程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；第2章 处 理 机 管 理 试看下述两种执行情况：(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章 处 理 机 管 理 2)临界区 进程访问临界资源的程序段称为临界区。在一个系统中，可以用某些方法或某种机制保证进程对临界区的互斥访问，一个好的解决方案应该遵循以下条件：(1)任何两个进程不能同时处于临界区内；(2)进程在临界区外只作有限时间的等待；(3)临界区外的进程不得阻塞其它进程进入临界区；(4)等待临界区时,释放CPU。第2章 处 理 机 管 理3 3对临界资源互斥访问的解决方法对临界资源互斥访问的解决方法 1)锁变量 设一个共享锁变量L，表示某个临界资源。其初值为0，表示锁开的状态。当进程要求进入临界区时，测试锁变量，有两种情况：若L为0，表示锁开着，则将L置为1，即可进入临界区。使用完毕，将L置为0，以便其它进程使用该临界资源；若L为1，表示锁未开，则进程不断地进行测试，直到L为0时，方可进入临界区。使用锁变量解决互斥问题，如图2-20所示。第2章 处 理 机 管 理图2-20 锁变量解决互斥L0?L1NY临界区L0返回第2章 处 理 机 管 理 用锁变量解决互斥存在的问题如下：进程持续测试锁变量L是否等于0的过程属于忙等待，对于CPU是一种浪费，违背进程互斥访问临界区的条件(4)：等待临界区时，释放CPU。另外，可能有这种情况发生：一个进程读锁变量时发现其值为0，在将其置为1之前被中断，另一进程被调度运行，发现L为0，将其置为1，并进入临界区。当第一个进程再次运行时，又将锁置为1，也进入临界区。这样两个进程同时处于临界区中，违背了进程互斥访问临界区的条件(1)：任何两个进程不能同时处于临界区内。第2章 处 理 机 管 理 2)严格轮转法 设一个公用变量i，存放被允许进入临界区的进程的编号。每个进程进入临界区时，对变量i进行测试，当进程号与变量i的值相等时，方可进入临界区，否则反复进行测试的工作。进程出临界区时为公用变量i设置允许进入临界区的进程的编号，然后执行该进程非临界区的操作。用严格轮转法解决互斥问题的过程，如图2-21所示。第2章 处 理 机 管 理图2-21 严格轮转法in?临界区NYim返回第2章 处 理 机 管 理 用严格轮转法解决互斥存在的问题如下：严格轮转法持续测试公用变量i直到它具有某特定值，这仍是忙等待，违背了进程互斥访问临界区的条件(4)：等待临界区时，释放CPU。另外，若有Pm、Pn两进程，当Pm进程执行完临界区时，将公用变量i置上允许进入临界区的进程Pn的编号，假如Pm非临界区操作很快做完，当Pn进程尚未进入临界区时，Pm再次要求进入临界区，因为公用变量i为Pn的编号，虽然临界区空，而Pm仍然不能进入，违反了进程对临界区互斥访问的条件(3)：临界区外的进程不得阻塞其它进程进入临界区。第2章 处 理 机 管 理 3)屏蔽中断 屏蔽中断的作法是：每个进程进入临界区时，首先关中断再访问临界区，在离开临界区之前打开中断。中断关闭后，则时钟中断也被屏蔽，CPU将无法进行进程切换，就不必担心其它进程竞争该资源了。采用关中断方法实现进程之间的互斥，简单而有效，但是若用户进程忘了打开中断，系统将终止。如果有多个CPU，一个进程访问一个临界区时，使用关中断仅可以阻止本CPU上执行的进程进入该临界区，不能防止别的CPU上的进程访问该临界区。第2章 处 理 机 管 理 4)TS指令（Test and Set）TS指令是一种利用硬件解决互斥的方法，通常将TS指令称为测试并上锁指令。TS指令的定义：ts=lock；lock=tr
