计算机操作系统 第三版 第二章进程管理

第二章进程管理2.1进程的基本概念2.2进程控制2.3进程同步2.4经典进程的同步问题2.5进程通信2.6线程2.1进程的基本概念一、前趋图二、程序顺序执行三、程序并发执行进程的描述一、进程的定义、特征二、进程的状态（状态、状态转换）三、进程控制块PCB前趋图的定义前趋图：有向无循环图（DAG）。描述一个程序的各部分（程序段或语句）间的依赖关系，或者是一个大的计算的各个子任务间的因果（前后）关系。前趋图中的每个结点可以表示一条语句、一个程序段或一个进程，结点间的有向边表示两个结点之间存在的偏序关系或前趋关系“→”。→＝{(Pi,Pj)|在Pj开始前Pi必须完成}。如果(Pi,Pj)∈→，可写成Pi→Pj，Pi是Pj的直接前趋，Pj是Pi的直接后继。没有前趋的结点称为初始结点，没有后继的结点称为终止结点。此外，每个结点还具有一个权值，用于表示该结点所含有的程序量或结点的执行时间。Eg1：以下三条语句的前趋图为：S1:a:=x+yS2:b:=a-5S3:c:=b+1Eg2:S1：a:=x+2S2:b:=y+4S3:c:=a+bS4:d:=c+6s1s2s3s1s2s3s4前趋图的定义（续）程序顺序执行程序顺序执行：必须按照某种先后次序逐个执行。如：数据输入程序I计算程序C数据输出程序P程序顺序执行时有如下特征：顺序性：一个程序各个部分的执行，严格地按照某种先后次序执行。封闭性：程序在封闭的环境下运行，即程序运行时独占全部系统资源。可再现性：只要程序执行时的环境和初始条件相同，当程序重复执行时，都将获得相同的结果。程序顺序执行的特性为程序员检测和校正程序的错误带来很大方便。程序并发执行程序可实现并发执行。(输入I、计算C、打印P)前趋关系：Ii→Ci,Ii→Ii+1,Ci→Pi,Ci→Ci+1,Pi→Pi+1因此，Ii+1,Ci,Pi-1是可以重叠执行的。I1I2I3I4C1C2C3C4P1P2P3P4程序并发执行（续）程序的并发执行:指一组在逻辑上互相独立的程序或程序段在执行时间上客观上互相重叠，即一个程序或程序段的执行尚未结束，另一个程序（段）的执行已经开始的方式。程序并发执行时的特征间断性（异步性）失去封闭性：共享资源不可再现性：失去封闭性失去可再现性程序并发执行（续）程序在并发执行时，由于失去了封闭性，也将导致其再失去可再现性。例如，有两个循环程序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。A：B：beginbeginrepeatrepeatN=N+1；PrintN；N=0；untiluntilendend程序并发执行（续）上述情况说明，程序在并发执行时，由于失去了封闭性，其计算结果已与并发程序的执行速度有关，从而使程序的执行失去了可再现性，亦即，程序经过多次执行后，虽然它们执行时的环境和初始条件相同，但得到的结果却各不相同。程序并发执行时的不可再现性是绝对不允许的；因此应采取措施使并发程序保持其可再现性。引入进程，对并发执行的程序加以描述和控制。进程的定义、特征1、进程(Process)的定义1）进程是程序的一次执行过程。2）进程是一个程序及其数据在处理机上顺序执行时所发生的活动。3）进程是程序在一个数据集合上的运行过程，它是系统进行资源分配和调度的一个独立单位。4）进程是进程实体的运行过程2、进程的基本特征（1）结构特征由程序段、相关数据段及进程控制块（PCB）组成，总称“进程映像”。进程的定义、特征程序代码—功能实现程序段操作的数据集—工作区进程控制块(PCB)：系统感知进程的唯一标识不同的PCB代表不同的进程三部分组成PCB信息：进程标识号（唯一）、进程状态信息、进程控制信息2、进程的基本特征（2）动态性由“创建”而产生，由“调度”而执行；由得不到资源而阻塞；由撤消而消亡。（而程序是静态的）。（3）并发性多个进程实体同时存在于内存中，能在一段时间内同时运行。（4）独立性能独立运行的基本单位，也是系统进行资源分配和调度的独立单位。（5）异步性指进程以各自独立的、不可预知的速度向前推进。进程的定义、特征程序进程概念静态动态所在存储器外存内存存在时间永久有生命期组成有序指令程序段,数据段,PCB对应关系一个程序可对应多个进程一个进程可对应多个程序（调用）进程与程序的主要区别进程状态1、进程的5种状态（三种基本状态）New新建/创建：进程正在创建中的状态。Ready就绪：进程已获得了除处理机以外的所有资源，等待分配处理机执行的等待状态。Running运行/执行：当一个进程获得必要的资源并正在处理机上执行的状态。Waiting等待/阻塞：正在执行的进程由于发生某事件而暂时无法执行下去，此时进程所处的状态。Terminated终止/撤消/退出：进程执行完毕，释放所占资源的状态。进程在运行期间并非固定处于某个状态，而是不断从一个状态转换到另一个状态。进程状态（续）2、进程状态转换就就就就就就就就就就就就就就I/O就就I/O就就多个阻塞队列4.七状态模型挂起进程提出的背景：处理器的速度要比I/O的速度快的多。当内存中所有的进程被阻塞时，怎么办？解决的办法：挂起：把主存中某个进程的一部分或者全部内容转移到磁盘(外存)中,扩大内存。被交换出去的进程称之为挂起状态suspendstate一个挂起态将一个进程挂起后，选择什么样的进程进入内存？接纳一个新进程。调入一个以前被挂起的进程。(更倾向于此)问题是：若所有被挂起的进程都需等待事件的发生所以对于挂起状态还要区分是否在等待事件的发生。程控制块ProcessControlBlockPCB系统为了管理进程设置的一个专门的数据结构；由操作系统创建，创建进程，首先要创建PCB；PCB中记录了OS所需的、用于描述进程的当前状态以及控制进程的全部信息；进程与PCB是一一对应的；PCB是系统感知进程存在的唯一标志；系统利用PCB来控制、管理进程；PCB的功能——支持多进程进程控制块记录了进程的所有信息。当进程中断时，操作系统会把程序计数器和处理器寄存器（上下文数据）保存在PCB的相应位置，设置状态为阻塞或就绪。操作系统将其他进程设为运行态，把其他进程PCB中的程序计数器和进程上下文数据加载到处理器寄存器中，运行其他进程。有了PCB，就可以中断一个进程，并且在后来恢复执行时好像进程未被中断过一样。PCB是支持多进程和提供多进程处理的关键工具。ProcessElements进程元素标识符，用以与其他进程区别状态优先权程序计数器内存指针上下文数据I/O状态信息审计信息（所需处理器时间总和，已执行多长时间、时间限制等）PCB表由于PCB被系统频繁访问，是常驻内存的，属于系统空间，只有操作系统程序才能够访问，用户程序不得访问。系统把所有的PCB组织起来，存放在内存的固定区域——PCB表、PCB池。PCB表的容量有限决定着系统中最多可同时存在的进程个数系统的并发度xPCB90PCB89PCB77PCB6PCB58PCB40PCB33PCB24PCB1执行指针就绪队列指针阻塞队列指针空闲队列指针下一个PCB的地址按链接方式组织PCBPCB9PCB8PCB7PCB6PCB5PCB4PCB3PCB2PCB1执行指针就绪表指针阻塞表指针就绪索引表阻塞索引表按索引方式组织PCB进程控制进程控制是进程管理中最基本的功能，即对系统中所有的进程实施有效的管理，其功能包括进程的创建、撤消、阻塞与唤醒等，这些功能一般是由操作系统的内核通过原语来完成。OS内核：在现代OS中，常把一些功能模块（与硬件紧密相关的及运行频率较高的）放在紧靠硬件的软件层次中，加以特殊保护，使它们常驻内存，以提高OS的运行效率，这部分功能模块就称OS的内核。内核是基于硬件的第一层软件扩充，它为系统控制和管理进程提供了良好的环境。CPU的执行状态CPU有两种执行状态：用户态：也叫目态。具有较低特权，只能执行规定的指令，访问规定的寄存器和存储器。通常，用户程序都运行在用户态。系统态：也叫管态或核心态。具有较高的特权，能执行一切指令，访问所有寄存器和存储区。通常，OS内核运行在系统态下。使用两种模式的原因保护操作系统以及操作系统使用的数据结构不受用户程序的干涉。原语进程控制是OS内核通过原语来完成的。原语是指系统态下执行的某些具有特定功能的程序段。指一个操作中的所有动作要么全做，要么全不做。换言之，它是一个不可分割的基本单位，因此，在执行过程中不允许被中断。原语在核心态下执行，常驻内存。进程的创建引起进程创建的事件分时OS的用户登录：为该终端用户创建一个进程批处理系统的作业调度：为被调度的作业创建进程提供服务：如要打印时建立打印进程应用请求：由应用程序建立多个进程（并发）创建进程由创建原语完成。被创建进程称作子进程，创建进程的进程称作父进程；子进程又可创建自己的子进程，形成一棵有向的进程树——进程图。内核创建进程创建一个进程可以创建若干个新进程，新创建的进程又可以创建子进程，为了描述进程之间的创建关系，引入进程图。进程图：又称为进程树或进程家族树，是描述进程家族关系的一棵有向树。ABDECF父进程祖先进程子进程进程的家族关系了解进程家族关系的必要性子进程可继承父进程的所有资源。子进程撤销时要把资源归还给父进程。父进程撤销时也必须撤销所有子进程。在每个进程的PCB中都设置家族关系的表项，以表明自己的父进程和所有的子进程。进程的创建操作系统一旦发现了要求创建进程的事件后，便调用进程创建原语Create按以下过程创建一新进程：申请一个空闲的PCB为新进程分配资源（静态、动态）对PCB初始化将PCB插入就绪队列返回一个进程标识号系统的PCB是有限的申请不到出错初始化标识信息：将系统分配的标识符和父进程标识符填入新PCB。初始化处理机状态信息：程序计数器指向程序的入口地址，栈指针指向栈顶。初始化处理机控制信息：设置进程的状态，设置优先级。ExampleofCreateProcessCreate(){structpcb*p;p=alloc_pcb();//allocaemptyprocesscontrolblock……//initialpp-state=not-running;p-parent=current;current-child=p;enqueue(NoRunningQUEUE,p);//putpintoreadyqueue……}进程的撤消当进程完成任务或遇到异常情况和外界干预需要结束时，使用终止原语来终止进程,以便及时释放其占有的各类资源。终止进程的实质：收回PCB。具体操作：找到要终止的进程的PCB。若正在执行，则终止执行，并置重新调度标志。终止该进程的所有子孙进程。释放终止进程的拥有的全部资源将终止进程移出所在队列，并收回PCB。进程撤消的过程在运行？NYNY由标识符在PCB集中找到PCB并其读状态归还占有资源从所在队列(索引表)撤消PCB中止运行重置调度标志终止所有子孙进程有子孙进程？归还给父进程或系统进程的阻塞与唤醒阻塞当正在执行的进程需要等待某种事件的到来或本身无新工作可做时，应调用阻塞原语block()将自己阻塞。阻塞是进程自身的一种主动行为。具体操作：停止进程的执行。修改其状态为阻塞。将其PCB插入相应的阻塞队列。转调度程序重新调度。唤醒阻塞进程等