搜索
操作系统原理PrinciplesofOperatingSystem2第2章进程管理2.1进程与任务处理机管理主要研究进程控制、进程和线程管理、提供进程同步机制和进程通信机制，进程调度和死锁等。我们可以把进程理解为操作系统的工作单元，进程是正在执行的程序，进程的执行需要一定的资源。操作系统主要研究进程与资源的关系。32.1.1前趋图为了描述一个程序的各部分(程序段或语句)间的依赖关系如图所示的前趋图中，P1为初始点，P7为终止点。前趋图存在下面的前趋关系：P1→P2，P1→P3，P1→P4，P2→P5，P3→P5，P3→P6，P4→P6，P5→P7，P6→P7。4前趋图中有两种元素：①节点。用圆圈○表示，其内涵可以是一条语句、一个程序段或进程。②有向边。用箭头→表示，表示两个节点之间存在的偏序(Partial_Order)或前趋关系(Precedence_Relation)。Pi→Pj表示在Pj开始前Pi必须完成，即Pi是Pj的直接前趋，Pj是Pi的直接后继，前趋图中不存在循环。52.1.2程序的顺序执行程序是指一个按严格次序执行的操作序列，执行的次序有顺序、分支和循环；操作是数据处理的一种规则，一经启动就需要在有限时间内完成。一个程序中包括三部分。I:输入操作，C:计算操作，P:打印操作。这样多个程序的顺序执行次序如图所示。6⒊顺序程序的特征如下:①顺序性：程序的执行是按照程序结构所指定的次序进行的。②封闭性：程序在封闭的环境下执行，即程序执行时独占全部系统资源。程序一旦开始执行，其计算结果不受外界因素影响，计算机的状态完全由该程序的控制逻辑所决定。③可再现性：只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它是从头到尾不停顿地执行，还是“停停走走”地执行，都将获得相同的结果。程序的结果与它的执行速度无关，只要给定相同的输入，一定会得到相同的结果。72.1.3程序的并发执行为提高系统资源的利用率和增强系统处理能力，在现代计算机中广泛采用并行操作技术和并发程序设计技巧。程序的并发执行是指两个或两个以上程序段在执行时间上的重叠。每个程序的输入操作、计算操作和打印操作必须顺序执行。对一批程序进行同时处理时，不同程序的各项操作可以并发执行。8如图2-3所示，存在以下的前趋关系：Ii→Ci，Ci→Pi，Ii→Ii+1，Ci→Ci+1，Pi→Pi+1。故Pi-1和Ci以及Ii+1之间可以并发执行。9⒉程序的并发执行的特征：①间断性：程序并发执行时，处理机交替执行多个程序，每个程序都是以“停停走走”的方式执行，可能走到中途停下来，而且程序无法预知每次执行和暂停的时间长度，失去原有的时序关系。②失去封闭性：由于程序的并发执行，打破了由一程序独占系统资源的封闭性。多个程序共享一个计算机系统的多种资源，每个程序的执行都会受其他程序的影响。③失去可再现性。程序并发执行时，由于失去了封闭性。由于程序每次执行的环境不同，程序执行的速度具有不可再现性。如果不采取制约措施，在不同执行环境下的程序的执行结果也将失去可再现特征。10程序执行是为了对输入信息进行处理，并得到相应的处理结果。为此，程序在并发执行时，必须保证程序执行结果可再现性。由于程序并发执行产生了一系列新特征，为了准确地描述并发程序的执行，必须引入进程的概念。112.1.4进程进程是指程序在并发环境下的一次运行过程。可并发执行的程序在一个数据集合上的运行过程传统进程的两个属性：进程是操作系统进行资源分配和处理机调度的基本单位。现代操作系统引进线程之后，进程的两个属性发生分离，进程仅是操作系统进行资源分配基本单位，而线程是操作系统处理机调度的基本单位。12引入进程对操作系统的影响进程是计算机系统资源的使用主体，进程与处理机、存储器和外设等资源的分配和回收相对应。操作系统引入进程，可以实现多个进程的并发执行，提高了系统资源的利用率，提高了系统的吞吐量。但由于每个进程配备PCB，增加了内存的空间开销。进程之间的切换、同步等需付出时间开销，引入进程会带来额外的时空开销，增加了操作系统的复杂性。13⒉进程的特征①动态性②并发性③独立性④异步性⑤结构特征。14进程的程序段描述了进程所要完成的功能。如果一个程序能够被多个进程同时共享执行，那么，这个程序段就是纯代码(purecode)，即可重入代码(reentrycode)形式编写的，它是指进程执行时不可修改的部分。数据段是指进程执行时用到的数据。用户程序在此数据集合上进行操作，得到相应的结果。进程控制块包含进程的描述信息和控制信息，不同的操作系统其进程控制块的内容及信息量也不相同。15⒊进程和程序的比较①程序是有序代码的集合，是一个静态的概念。进程是程序的一次执行过程，是一个动态概念。进程不可以在计算机之间迁移，而程序通常对应着文件，可以复制。②进程是一个状态变化的过程，是有生命期的。而程序是永久的，可以长久保存。③进程与程序的组成不同。进程由程序段、数据段和进程控制块组成，而程序仅是代码的有序集合。④进程与程序是密切相关的。通过多次执行，一个程序可对应多个进程。但进程与它本身所运行的程序只能是一对一的关系。⑤进程更能真实地描述并发，而程序不能。⑥进程可创建其他进程，而程序并不能形成新的程序。162.1.5任务与多任务对于有多个CPU的计算机，同时在每一个CPU上执行进程称为多重处理。多重处理是针对多机系统定义的，这一点请读者注意理解。我们可以认为多重处理是多任务处理在多机系统中的一个特例，多重处理是多任务处理的子集。多任务是指在同一时间间隔内系统执行多个进程,这里包含多重处理和多进程并发执行。任务是一个具有开始时间和完成时间的操作,任务是系统的基本工作单元，任务调度与进程调度的过程基本类似。在操作系统中，站在用户的角度上，任务可以理解为逻辑上的进程。不同的操作系统进程与任务的含义不同，在Linux系统中，进程与任务的含义是相同的。172.2进程的状态与进程控制块2.2.1进程的基本状态18进程在运行过程中主要是在就绪、执行和阻塞三种基本状态间进行转换①创建(new)状态。进程正在创建过程中，但还未将它送入就绪队列时的状态。②就绪状态（Ready）。进程已得到必要的资源，唯缺处理机，等待处理机调度，一旦获得处理机便可立即执行。将处于就绪状态的那些进程排成队列就叫就绪状态队列。③执行状态（Running）。进程占用CPU资源并正在CPU上执行，处于此状态的进程数目小于等于CPU的数目。在没有其他进程可以执行时(如所有进程都在阻塞状态)，通常会自动执行系统的空闲进程。在多机系统中，可以有多个进程处于执行状态。而在单机系统中，仅有一个进程处于执行状态。19④等待状态（Waiting）。也称为阻塞（Blocked)状态，在执行过程中，因等待某一事件而暂时无法执行。将等待同一事件的阻塞进程排一个队列就叫该事件的等待队列。⑤退出（exit)状态。当一个进程已经正常结束或异常结束，系统回收资源。操作系统已将它从就绪队列中移出，正在将它撤消。202.2.2进程的状态变迁机制①提交(Admit)：完成一个新进程的创建过程，新进程进入就绪状态。由于性能、内存、进程总数等原因，系统会限制并发进程总数。②调度(Dispatch)：按调度算法从就绪进程队列中选择进程，进入执行状态。③释放(Release)：由于进程完成或异常终止进程运行，进入退出状态。状态变迁图中只画出了执行状态到退出状态间的释放转换。但实际上，还存在从就绪状态或阻塞状态到退出状态的释放转换。执行到退出的转换可分为正常退出(exit)和异常退出(abort)。21④超时(Timeout)：由于用完时间片或高优先级进程就绪等原因导致进程暂停执行。分配的时间片用完而发生时钟中断，或一个刚进入就绪队列的进程，其优先级高于处于执行状态的进程的优先级而抢占处理机，于是进程从执行状态到就绪状态的转变。⑤等待事件(EventWait)：进程要求的事件未出现而进入阻塞。可能的原因包括：申请系统服务或资源、通信、I/O操作等。⑥事件发生(EventOccurs)：进程等待的事件发生。例如，操作完成、申请成功等。进程从等待状态转变为就绪状态，重新等待处理机调度。操作系统中多个进程的并发执行是通过两套循环完成。一是通过调度与超时二种状态变迁原因的循环。二是通过调度、等待事件和事件发生三种状态变迁原因的循环。222.2.4进程控制块所谓进程控制块（ProcessControlBlock，PCB）是由操作系统维护，用来记录进程相关信息的数据结构。每个进程在操作系统中都有对应的进程控制块。操作系统依据进程控制块对进程进行控制和管理，进程控制块中的内容会随进程的推进而动态改变。进程控制块通常不能由应用程序自身的代码来直接访问，而要通过系统调用进行访问。232.2.5进程之间的上下文切换在多进程并发执行中，将CPU切换到另一个进程需要保存原来进程的关联状态并装入新进程的关联状态。这一任务称为上下文切换当发生上下文切换时，内核会将旧进程的关联状态保存在其PCB中，然后装入经调度要执行的新进程的已保存的关联状态。上下文切换时间是系统额外开销，因为切换时系统并不能做什么有用的工作。操作系统越复杂，上下文切换所要做的工作就越多。上下文切换问题可能会成为操作系统性能的瓶颈，我们可以采用线程减少或避免上下文切换时间，降低操作系统开销。242.3进程控制⒈链接方式25⒉索引方式262.3.3进程控制原语创建进程的典型事件①批处理系统中的作业调度。②用户登录。③用户启动应用程序。④由操作系统创建的系统服务。⑤创建新的进程。27⒉撤消原语撤消进程的典型事件：①正常结束：进程完成了程序的执行任务。②异常结束：出错或故障结束，有算术运算出错、I/O故障等。③被干预结束：包括操作员或操作系统干预结束、被父进程请求结束、父进程本身要结束而其子孙进程跟随结束。28⒊阻塞原语阻塞原语具体的操作过程是：查找到该被阻塞进程的PCB，剥夺其处理机，将其状态改为阻塞状态，转进程调度。根据阻塞事件的类型将该阻塞进程插入到相应阻塞队列中。阻塞原语的算法描述:voidblock(WQ[r]){i=*EP;/*取得调用者进程的PCB*/stop(i);/*剥夺CPU*/i.status=”blocked”/*将进程i的状态置为阻塞状态*/i.state=WQ[r];/*填入所在队列的首指针*/insert(WQ[r]);/*插入相应阻塞队列*/scheduler;/*进程调度*/}29⒋唤醒原语因事件发生，进程从阻塞状态转换到就绪状态，用唤醒原语完成。唤醒原语对PCB进行修改来实现其功能，在被唤醒的阻塞队列中，找到队首进程。并将该进程从阻塞队列移出，插入到就绪队列中，再将该进程状态改为就绪状态。对于可抢占式进程调度，还可引起进程调度，以便让高优先权进程迅速进入执行状态。唤醒原语算法描述为：voidwakeup(WQ[r]){i=remove(WQ[r]);/*查找并得到PCB(n)，从阻塞队列wQ[r]中移出n*/i.status=”ready”;/*置进程i的状态为就绪状态*/i.state=RQ;/*填入所在队列的首指针*/insert(RQ，i);/*插入就绪队列RQ*/scheduler;/*进程调度*/}