第2章进程管理

第二章进程管理第一节进程的基本概念一、前趋图(一)前趋图1、作用：为了描述进程之间执行的前后关系，我们常常采用前趋图方式。2、定义：前趋图是一个有向无循环图DAG(DirectedAcyclicGraph)。图中每个节点表示一条语句、一个程序段或进程。有向边表示在两节点之间存在的偏序或前趋关系，表示为“→”，描述为：→＝{(Pi,Pj)|在Pj开始前Pi必须完成}如果（Pi，Pj）∈→，也就是Pi和Pj存在偏序或前趋关系，那么可写成Pi→Pj，其中我们说Pi是Pj的直接前趋，Pj是Pi的直接后继。每个节点有一个重量，也就是权值，表示节点所含的程序量或者节点的执行时间。在该前趋图中：存在下面的前趋关系：P1→P2，P1→P3，P1→P4，P2→P5，P3→P5，P4→P6，P4→P7，P5→P8，P6→P8，P7→P9，P8→P9；或表示为：Ｐ={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)}（二）程序的顺序执行程序在执行时，把一个程序分成若干个程序段，它们必须按照某种先后次序顺序执行，也就是前一个操作完成，后面的操作才能执行。前趋图如下顺序执行前趋图语句的顺序执行：语句顺序执行程序顺序执行的特征：顺序性：前一操作完成，后一操作才能进行。封闭性：程序在封闭的环境下运行，即程序运行时独占全部系统资源。可再现性：只要程序执行时的环境相同，程序每次运行结果相同。（三）程序并发执行概念：程序的并发执行：一组在逻辑上互相独立的程序或程序段在执行过程中，其执行时间在客观上相互重叠。现在来理解这个概念：从两点来理解。首先，程序段在逻辑上是没有关联的。例如一个是A程序的打印程序段，一个是B程序的计算程序段。其次，这几个不关联的程序段在执行时间上是重叠的。也就是一个程序段的执行尚未结束，另一个程序段的执行已经开始的执行方式。例如A程序的打印程序段尚未执行完，B程序的计算程序段已经开始执行。并发执行的特征：1、间断性：是指程序在执行中一般是“执行—暂停执行—执行”，间断执行的。间断性产生的原因是，程序执行时的相互制约，这种制约是由于程序并发执行而产生的，因为程序在并发执行中可能会对共享资源或为同一项任务的执行而产生制约。是有点太抽象了那么看课本的例子。就明白了，程序A将使用打印机，可是它却被程序B占用。那么程序A就必须等待这个就是典型的因为共享资源而造成的间断。2、失去封闭性：封闭性是指程序运行时独占资源，只有本程序能改变它。但是在并发执行时，各程序都可共享资源，因此失去封闭性。3、不可再现性：程序并发执行时，失去可再现性。例如当两个程序共享一个变量时，可能造成不可再现性。程序的并发执行破坏了程序的可再现性。见课本例子。4、通信性：对于相互合作的程序，为了更有效地协调运行，相互之间需要进行通信。5、独立性：并发程序在运行过程中，既然是作为一个独立的运行实体，它也必然具有作为一个单位去获得资源的独立性。程序并发执行条件（Bernstein条件）程序并发执行时的不可再现性是不允许的，因此必须采取措施保证其再现性。读集：R(Pi)={a1,a2,...,am}，为程序Pi在执行期间所需参考的所有变量的集合写集：W(Pi)={b1,b2,...,bn}，为程序Pi在执行期间所要改变的所有变量的集合两个程序是否能并发执行，可根据Bernstein条件来判断，该条件是：R(P1)∩W(P2)∪R(P2)∩W(P1)∪W(P1)∩W(P2)={}满足伯恩斯坦条件则能并发执行。例如：四条语句：S1：a:=x+yS2：b:=z+1S3：c:=a-bS4：w:=c+1读集和写集是：R(S1)={x,y}R(S2)={z}R(S3)={a,b}R(S4)={c}W(S1)={a}W(S2)={b}W(S3)={c}W(S4)={w}可见，S1和S2可并发执行，因为满足Bernstein条件；S1和S3不可并发执行，因为R(S3)∩W(S1)={a}；S2和S3不可并发执行，因为R(S3)∩W(S2)={b}；S3和S4不可并发执行，因为R(S4)∩W(S3)={c}。二、进程的描述(一)概念的引入并发执行的出现后，我们要怎样描述多个作业、多个任务这样的并发活动在计算机系统内部的表现和情况呢？这样就引入的进程。(二)进程的定义和特征1、进程的定义进程定义：可并发执行的程序在一个数据集合上的运行过程。怎么理解这个概念？首先进程是一个运行过程，这样看来它是一个动态的。其次它必须具备是的物质条件是一个程序段，一个数据集合，还有后面要讲到的进程控制块。现在我们知道，进程的物质实体由三部分构成：程序段，数据段，进程控制块。再合起来理解进程的定义，简单说，进程就是程序实体的运行过程。它是系统进行资源分配和调度的一个独立单位。2、进程特征进程有5个基本特征1)动态性：进程的实质是程序的一次执行过程，因此，动态特征是进程最基本的特征。进程有一定的生命期，由创建而产生，由调度而执行，因得不到资源而暂停执行，由撤销而消亡。2)并发性：从上面可知，引入进程的目的就是为了描述程序的并发执行，其实是程序的进程的并发执行。那么我们可知，没有为之建立进程的程序是不能并发执行的，仅当为之建立一个进程后才能参加并发执行。3)独立性：进程是一个能独立运行的基本单位，同时也是系统分配资源和调度的独立单位。4)异步性：由于进程间的相互制约，使进程具有执行的间断性，即进程按各自独立的、不可预知的速度向前推进。5)结构特征：为了控制和管理进程，为每个进程设立一个进程控制块PCB。从结构上看，进程实体由程序段，数据段和进程控制块三部分组成，也叫“进程映象”。(三)进程的状态及转换1、最基本的三个状态是：就绪，执行，阻塞状态。就绪状态：当进程已分配到除CPU以外的所有必要资源后，只要再能获得处理机，便可执行。此时进程是就绪状态。执行状态：进程已获得处理机，正在执行。阻塞状态：进程因发生某事件（如请求I/O,申请缓冲空间等）而暂停执行时的状态，也就是进程的执行受到阻塞。此时为阻塞状态，也叫做等待状态。进程的三种基本状态演变图如下：这个图还行，三个基本状态转换图转换图说明：进程已分配到除CPU以外的所有必要资源时，它便处于就绪状态，一旦获得CPU，便立即执行。已获得CPU的进程进入执行状态。正在执行的进程，由于发生某个事件而暂时无法执行时，便放弃处理机而进入阻塞状态。由于执行的进程变为阻塞状态后，调度程序立即把处理机分配给另一个就绪进程；因此，阻塞进程的事件消失后，进程不会立即恢复到执行状态，而转变为就绪状态，重新等待处理机。2、挂起状态1)什么是挂起状态：使正在执行的进程暂停执行；使处于就绪态的进程暂不接受调度的这种静止状态成为挂起状态。2)引入挂起状态的原因：四个原因，同学们看一下课本。3)引入挂起态后的进程状态转换：了解一下。来看下面的图，静止就是挂起具有挂起操作的进程状态演变图。知道就行(四)进程控制块PCBprocesscontrolblock1、为什么引入进程控制块？为了描述进程，即系统中需要有描述进程存在和能够反映其变化的物理实体，也就是进程的静态描述。进程的静态描述有3部分组成：PCB，程序段，与程序段相关的数据段。为了描述进程而引入PCB.2、什么是进程控制块？是进程实体的一部分，是描述和控制、管理进程的记录型数据结构，是进程存在的唯一标志。通过这个定义，我们理解PCB就是一个数据结构，作用是描述，控制和管理进程。3、PCB是感知进程存在的唯一标志在创建一个进程时，应首先创建其PCB，然后才能根据PCB中信息对进程实施有效的管理和控制。当一个进程完成其功能时之后,系统则释放PCB，进程也随之消亡。3、进程控制块的组成一般来说，根据操作系统的要求不同，进程的PCB所含的内容也会不同。但一下基本内容是必需的：1)进程描述信息：进程名或进程标识符：每个进程都有唯一的进程名或进程标识号。在识别一个进程时，进程名或进程标识号代表该进程。进程与PCB是一一对应的用户名或用户标识号：每个进程都隶属于某个用户，用户名或用户标识号有利于资源共享与保护。2)进程调度信息：进程当前状态：说明进程当前处于何种状态。进程在活动期间可分为就绪态、执行态和等待状态。进程优先级（priority）：进程优先级是选取进程占有处理机的重要依据。与进程优先级有关的PCB表项还有：占有CPU时间，进程优先级偏移，占据内存时间等。3)进程控制信息：程序与数据地址：该进程的程序和数据所在位置信息。进程通信机制：用于实现进程间的通信所需的数据结构。资源清单：列出进程拥有的资源的记录。连接字：给出本进程所在队列中的下一个进程的PCB首址。4)处理机状态（CPU现场保护结构）：主要是处理机各种寄存器值（通用、程序计数器PC、状态字PSW，地址包括栈指针）。作用：处理机运行时，信息放在寄存器中，当处理机被中断时，所有这些信息都必须保存在被中断进程的PCB中，以便将来该进程重新执行时，能从断点处继续执行。4、进程控制块的组织方式在系统中，由于进程的状态各种各样，有的进程在执行态，有的在阻塞，有的在就绪态。进程与PCB是一一对应，因此系统中，通常有几十甚至上百个PCB。为了对这些PCB进行有效管理，需要将它们组织起来。常用的组织方式有2种：1)链接方式链接方式组织PCB图说明：链接组织方式是把处于同一状态的进程组织在一起，形成就绪队列、阻塞队列、空闲队列等。在这些不同状态的队列中，再按一定的规则进行排列。如就绪队列中按进程优先级的大小排列，2)索引方式索引方式组织PCB图说明：同一状态的进程归入一个index表（由index指向PCB），多个状态对应多个不同的index表，各状态的进程形成不同的索引表：就绪索引表、阻塞索引表第二节进程控制处理机的执行状态为防止OS及其关键数据（如PCB等)不被用户有意或无意破坏,通常将处理机的执行状态分为两种处理机状态特权(执行指令,访问）程序系统态(核心态)较高(一切指令,所有R及存储区)OS内核用户态较低(规定指令,指定R及存储区)用户程序cobegin和coend括起来表示这n个语句是可以并发执行的。co是concurrent的头两个字符。其他的语法就是PASCAL语法。进程管理的一个重要任务就是进程控制。一、什么是进程控制？就是系统使用一些具有特定功能的程序段来创建、撤销进程以及完成各状态间的转换，从而达到多进程高效率并发执行和协调、实现资源共享的目的。这些具有特定功能的程序段，就是操作系统内核。进程控制一般是由操作系统的内核来实现，内核在执行操作时，往往是通过执行各种原语操作来实现的。操作系统内核：是加在硬件上的第一层软件，通过执行各种原语操作来实现各种控制和管理功能，具有创建进程、撤消进程、进程通信、资源管理的功能。同时把它们常驻内存，以提高OS的运行效率，这部分功能模块就称OS的内核。内核是基于硬件的第一层软件扩充。二、进程的创建一）一些概念1、进程图（ProcessGraph）进程图是用于描述进程家族关系的有向树。进程图说明：结点代表进程，一棵树表示一个家族，根结点为该家族的祖先。子进程可以继承父进程拥有的资源，子进程撤销时，还给父进程这些资源。父进程撤销时，同时要撤销其所有的子进程。注意：进程图和前趋图之间的区别前趋图描述的是任务（或进程）之间的前趋关系；只有在前趋进程完成后，其后继进程才能运行；进程图中，描述的进程的进程关系。创建者和被创建者可以并发执行，也可以是父进程等待其所有的子进程结束后再执行，这完全取决于创建原语和创建者的需要。2、原语：是由若干多机器指令构成的完成某种特定功能的一段程序，具有不可分割性。即原语的执行必须是连续的，在执行过程中不允许被中断，在操作系统中，它是不可分割的基本单位。原来就是程序段，别被新名字吓倒了。二）进程创建1、进程创建原语：进程创建是调用创建原语来实现。创