工学操作系统进程管理

工学操作系统进程管理第1页/共120页2第二章进程管理

（）学习目标：理解进程的概念以及与程序的异同掌握进程的实体、状态及状态的演变熟练掌握进程的控制与调度掌握进程之间的关系协调（同步与互斥）掌握进程的通信熟练掌握用信号量描述进程的同步第2页/共120页3第二章进程管理1进程的基本概念2进程控制3进程同步4经典进程的同步问题5管程机制6进程通信7线程第3页/共120页4第二章进程管理2.1进程的基本概念在传统的操作系统中，程序并不能独立运行，作为资源分配和独立运行的基本单位都是进程。在未配置OS的系统中，程序是顺序执行的在多道运行环境下，允许程序的并发执行

第4页/共120页52.1.1程序的顺序执行及其特征(图2-1)1程序的顺序执行：2特征：顺序性：程序段中的操作和指令按顺序执行封闭性：程序独占资源，结果不受外界因素影响。可再现性：只要程序的运行环境和初始条件相同，无论什么时间执行都能得到相同的结果。第5页/共120页62.1.2前趋图（图2-2） 前趋图（ProcedureGraph）是一个有向无循环图DAG（DirectedAcyclicGraph），用于描述进程之间执行的前后关系。图中的每一个结点可以用来表示一条语句、一个程序段或进程；结点间的有向边则表示在两结点之间存在的偏序或前趋关系第6页/共120页72.1.3程序的并发执行及其特征程序的并发执行：图2-3特征：间断性:并发性引起资源的共享或相互合作，因此形成了相互制约的关系，因而导致并发程序的“执行－暂停－执行”的间断过程。失去封闭性:并发性引起资源的共享，资源的状态由多个进程改变，这样进程的运行就失去了封闭性。

第7页/共120页8不可再现性：并发性使程序的运行失去了封闭性，程序的计算结果与程序的速度有关，从而失去了结果的可再现性。例如两个循环程序A和B,他们共享一个变量N，A执行一次N:=N+1，B执行一次都完成Print(N),然后执行N:=0.则会出现：N:=N+1;Print(N);N:=0;Print(N);N:=0;N:=N+1;Print(N);N:=N+1;N=0;第8页/共120页92.1.4进程的特征与状态为什么要引入进程？并发程序执行的不可再现性，使程序的并发执行失去了意义，为了程序能并发执行，且能够对并发执行的程序进行控制和描述。 。第9页/共120页10进程的定义：进程是进程实体（程序段、数据段、进程控制块）的运行过程，是系统进行资源分配和调度的独立单位第10页/共120页11结构特征：程序段，数据段，PCB（进程控制块）为了使程序能够独立运行而存放程序控制信息的数据结构。动态性：进程的实质是进程实体的一次执行过程，由创建而生，由调度而执行，由撤销而消亡。并发性：多个进程同驻内存，在一段时间内同时运行独立性：独立运行、资源分配、调度的单位异步性：独立的，不可预知的速度向前推进进程的特征：第11页/共120页12思考题程序与进程的联系与区别？第12页/共120页13进程基本状态及其转换：进程的动态性表明进程在其生存期内会经历一系列的离散状态，运行中的进程可以处于一下三种状态之一。

图2-5就绪态：万事具备，只欠CPU执行态：进程获得CPU,正在运行阻塞态：发生事件无法继续第13页/共120页14状态转换：就绪—进程调度分配CPU—执行执行—时间片用完—就绪执行—因某事件（I/O请求）—阻塞阻塞—资源满足（I/O完成）—就绪

例题第14页/共120页153.具有挂起功能的进程状态及其转换由于进程的不断创建，系统的资源特别是内存资源不能满足进程运行的需要，这时必须把某个进程对换到磁盘中，释放该进程占有的资源，暂时不参与进程调度，起到平滑系统操作负荷的目的。第15页/共120页16这种对换到磁盘，暂时不进行调度的进程状态叫做挂起状态（静止状态），分为静止就绪和静止阻塞。将进程换出的过程叫挂起将静止的进程换入的过程叫做释放静止就绪：进程具备运行条件，但处于辅存静止阻塞：进程正在等待某事件且在辅存中第16页/共120页17系统中的进程均处于阻塞状态，处理机空闲，此时需要腾出内存空间，将资源分配给某个等待进程，然后执行。竞争资源，导致资源不足，负荷过重，此时需要将一些进程挂起，释放资源。用户要求挂起的自己的进程，以便对中间结果进行核查，修改。父进程要求修改子进程时，需要将子进程挂起。

第17页/共120页18状态转换：如图2-6活动阻塞－静止阻塞：活动阻塞进程由其自身调用或其他进程调用挂起原语（suspend)。在其挂起期间并不影响其等待事件的发生。活动就绪－静止就绪：活动就绪进程由其自身或其他进程调用挂起原语而进入的一种状态。在其挂起期间没有资格竞争cpu第18页/共120页19创建状态和终止状态创建一个进程需要：创建PCB,并填写必要的管理信息；分配内存资源，转入就绪状态。终止一个进程需要：首先等待OS进行善后处理；然后将PCB清零，将PCB空间返还系统。第19页/共120页20创建就绪执行阻塞终止许可时间片完进程调度I/O完成I/O请求释放图2-7进程的五种基本状态及转换第20页/共120页211.5进程控制块（图示）：记录了操作系统所需要的,用于描述进程的当前状态、本身特性、对资源的占有以及控制进程运行的全部信息。记录了这些信息的数据结构就是进程控制块（PCB) ,是进程存在的唯一标志，常驻内存。第21页/共120页222进程控制块中信息：

进程标识符：外部标识符-名字、用户使用;内部标识符-数字、系统使用。

处理机状态：由处理机各种寄存器中的内容组成。处理机运行时状态信息放在寄存器中，处理机中断时放在PCB中。通用寄存器、指令计数器、程序状态字(PSW)、用户栈指针第22页/共120页23

进程调度信息（进程状态、进程优先级、进程调度需要的其它信息、事件）

进程控制信息（程序和数据地址、进程同步和通信机制、资源清单和链接指针）。第23页/共120页243PCB的组织方式系统中通常会由多个PCB，这些PCB通常会用某种方式组织起来，才能有效的管理。链接方式（图2-7）索引方式（图2-8）第24页/共120页252.2进程控制进程控制是进程管理的最基本的功能，用于创建新进程，终止进程，进程的状态转换。进程控制由OS内核中的原语实现。原语：由若干指令组成的，用于完成一定功能的过程，这些过程是原子操作。原子操作：是一个不可分的基本单位，操作中的动作或者全做或者全不做。

第25页/共120页26在操作系统中，通常把进程控制用程序段做成原语。用于进程控制的原语有：创建原语(creat)、撤销原语(destory)、阻塞原语(block)、唤醒原语(wakeup)等。第26页/共120页272.2.1进程创建进程在执行过程中可以通过系统调用创建多个子进程，将正在执行的进程叫做父进程，新创建的进程叫做子进程。1进程图：描述进程的家族关系的有向树（图2-9）父进程、子进程、祖先进程。进程图由结点和有向边构成。第27页/共120页28子进程可以继承父进程拥有的资源子进程撤销时要归还父进程的资源父进程撤销时必须同时撤销所有的子进程。在PCB设置了家族关系表项，标明进程的父进程和所有子进程。第28页/共120页29请同学们想一下：使用进程图是为了描述什么？进程图与前趋图的比较，有什么异同？第29页/共120页302引起进程创建的事件：用户登录作业调度提供服务应用请求

系统创建进程父进程创建进程第30页/共120页313进程的创建调用creat()原语。申请空白PCB和唯一的数字标识符为新进程分配资源（内存空间）初始化PCB—标识信息，处理机状态信息，处理机控制信息将进程插入就绪队列。建立PCB，分配内存，加载程序，入就绪链第31页/共120页32入口查PCB链表有空PCB？PCB（I）入进程家族或进程链PCB(1)入就绪队列将有关参数填入PCB（1）相应项取空表PCB(1)返回创建失败无创建原语流程图有第32页/共120页33

Creat(s0,m0,pi){p=Get-New-PCB();分配新的PCBpid=Get-New-PID();分配进程IDp->ID=pid;设置进程IDp->CPU-State=so;CPU的状态p->Memory=m0;p->Priority=pi;p->Status.Type=‘ready’;p->Status.List=RL;Insert(RL,p);Scheduler();调度程序}第33页/共120页342.2.2进程终止引起进程终止的事件：1正常结束：计算机系统中，都有一个表示进程已经运行完成的指示。如：批处理(Holt)，分时系统中(LogsOff）。2异常结束越界错误、保护错、特权指令错、非法指令错、运行超时、等待超时、算术运算错、I/O故障3外界干预操作员或操作系统干预父进程请求父进程终止第34页/共120页35入口返回查进程链表或进程家族有此PCB吗？该PCB有子进程吗？释放该进程所占有的资源释放该PCB结构本身出错处理有无有第35页/共120页362终止过程:调用进程终止原语根据进程标识符，从PCB集合中检索出该进程的PCB，读出该进程的状态；若正处于执行态，立即停止该进程的执行，并设置调度标志为真，把处理机分配给新进程；

终止所有子进程；

全部资源归还给其父进程或系统；将被终止进程的PCB从所在队列（或链表）中移出归还资源，撤销PCB，通知父进程第36页/共120页37Destroy(pid){p=Get-PCB(pid);Kill-Tree(p);Scheduler();}Kill-Tree(p){For(eachqinp->creation.tree.child)Kill-tree(q);If(p->status.type=‘runing’{p1=p->processor-ID;Interrupt(p1);}Remove(p->status.list,p);release-all(p->memory);Releas-all(p->other-resources);Close-all(p->open-files);Delete-PCB(P);}第37页/共120页382.2.3进程的阻塞和唤醒1进程阻塞

一个进程经常要和其他进程通信。这在运行的进程因为提出服务请求（I/O)操作，未得到操作系统的立即满足，或者所需数据尚未到达等原因，将转变为阻塞状态。第38页/共120页392阻塞过程： 调用阻塞原语block()，是主动行为。停止进程的执行将PCB中的执行态改为阻塞态将PCB插入阻塞队列将处理机分配给另一个就绪进程。

第39页/共120页40入口保存当前进程的CPU现场置该进程的状态被阻塞进程入等待队列转进程调度阻塞原语第40页/共120页41Block(){p=Get-PCB();s=p->Status.Type;Cpu=p->processor-ID;P->CPU-State=interrupt(cpu);p->status.type=‘blocked’;Insert(BL,p);Scheduler();}第41页/共120页423唤醒过程唤醒原语wakeup()，将等待该事件的进程唤醒。把阻塞的进程从阻塞队列中移出将PCB的状态由阻塞改为就绪将PCB插入就绪队列第42页/共120页43入口从等待队列中摘下被唤醒进程将被唤醒进程置为就绪状态将被唤醒进程送入就绪队列进程调度返回唤醒原语第43页/共120页44Wakeup(pid){P=Get-PCB(pid);Remove(p->status.list,p);P->status.type=‘ready’;Insert(RL,p);Scheduler();}第44页/共120页452.2.4进程的挂起和激活当出现了引起进程挂起的事件时，用户请求将自己挂起，或者父进程请求挂起自己的子进程，应该利用挂起原语suspend()挂起原语的执行过程：检查被挂起进程的状态；如果处于活动就绪状态，就将它改为静止就绪；如果处于活动阻塞，则改为静止阻塞。进程的激活过程：当发生激活事件后，系统利用激活原语Active()将指定进程激活。激活原语先将进程从外存调入内存，然后检查进程的状态。第45页/共120页46填空题为使进程由活动就绪转变为静止就绪，应利用__⑴__原语；为使进程由执行状态变为阻塞状态，应利用__⑵__原语；为使进程由静止就绪变为活动就绪，应利用__⑶__原语；从阻塞状态变为就绪状态应利用__⑷__原语。⑴-⑷：suspend()block()active()wakeup()第46页/共120页47知识回顾什么是进程?进程的三种基本状态及转换条件及其关系？什么是进程控制块PCB?第47页/共120页482.3进程同步在多道程序运行环境下，并发执行的进程共享计算机资源，从而导致进程之间存在着一定的制约关系。为了保证执行结果的正确性和资源的充分利用，系统必须提供相应的并发控制机制（进程同步机制）并发进程之间为了完成某个任务而相互等待的关系就是进程同步关系。第48页/共120页49进程同步的任务：对多个相关进程在执行次序上进行协调，使并发进程之间有效的共享资源和相互合作，使执行结果可再现。2.3.1进程同步的基本概念1两种形式的制约关系：直接相互制约（源于相互合作）间接相互制约(源于资源共享）第49页/共120页501).直接相互制约：发生在相关进程之间sendreceiveP1:P2:2).间接相互制约：发生在任何进程之间RP2P1holdwait第50页/共120页512临界资源临界资源：一段时间内只允许一个进程访问的资源要求：各进程必须互斥访问临界资源。原因：例如生产者－消费者进程生产者进程（producer)消费者进程（consumer){…

{…

放产品取产品

counter:=counter+1;counter:=counter-1;

…

…}}第51页/共120页52机器语言形式为：生产者进程

counter:=counter+1;1register1:=counter;2register1:=register1+1;3counter:=register1消费者进程counter:=counter-1;4register2:=counter;5register2:=register2-1;6counter:=register2由于生产者和消费者并发运行，且共享变量counter，造成：可能性ABCD其他CPU执行顺序123456456123124536451263…Counter初值55546…正确正确不正确不正确不正确第52页/共120页533临界区临界区：每个进程中访问临界资源的代码称为临界区。进入区：检查临界资源是否正在被使用。退出区：将临界资源使用标志恢复，释放临界资源。剩余区：保证进程互斥的进入临界区，从而保证互斥访问临界资源第53页/共120页54临界区(CS)：每个进程中访问临界资源的那段代码生产者进程（producer)消费者进程（consumer){…

{…

放产品取产品counter:=counter+1;－(CS)counter:=counter-1;-(CS)

…

…}}为了实现对临界资源的互斥访问，应保证各进程互斥的进入临界区。第54页/共120页55 4同步机制应遵循的规则：

空闲让进，忙则等待，有限等待，让权等待。第55页/共120页56P操作相当于申请资源，而V操作相当于释放资源。所以要记住以下几个关键字：P操作----申请资源V操作----释放资源2.3.2信号量机制第56页/共120页57PV操作的含义：PV操作是由P操作原语和V操作原语组成（原语是不可中断的过程），对信号量进行操作，具体定义如下：P（S）：①将信号量S的值减1，即S=S1；②如果S0，则该进程继续执行；否则该进程置为等待状态，排入等待队列。V（S）：①将信号量S的值加1，即S=S+1；②如果S>0，则该进程继续执行；否则释放队列中第一个等待信号量的进程。第57页/共120页58一个生产者，一个消费者，公用一个缓冲区好又多一分店伊利牛奶生产厂家件生产一个产品取出一个产品第58页/共120页59empty——表示缓冲区是否为空，初值为1。full——表示缓冲区中是否为满，初值为0。生产者进程while(TRUE){生产一个产品;P(empty);

产品送往Buffer;V(full);}消费者进程while(TRUE){P(full);

从Buffer取出一个产品;V(empty);

消费该产品;}第59页/共120页60信号量机制是一种卓有成效的进程同步工具，被广泛应用于单处理机和多处理机系统，以及计算机网络中。信号量机制第60页/共120页61（１）信号量的含义。信号量是一个用来实现进程同步的整型或记录型变量，除了初始化外，对它只能执行wait和signal这两种原子操作。在学习时，应了解对信号量的wait和signal操作分别是如何实现的，整型信号量存在着什么不足之处，记录型信号量是如何解决整型信号量的不足的。

第61页/共120页62（２）信号量的物理意义。一个信号量S通常对应于一类临界资源。在学习时，必须理解S.value的值在物理上有什么特殊的含义，而每次wait和signal操作又分别意味着什么，故必须分别对S.value进行什么操作。第62页/共120页63（３）用信号量实现互斥。为了实现进程对临界资源的互斥访问，需为每类临界资源设置一初值为1的互斥信号量mutex。在学习时，应清楚在进入临界区前或退出临界区后应对mutex分别执行什么操作，为什么对mutex的wait和signal操作必须成对出现，如少了其中的wait操作或signal操作，会对互斥算法产生什么样的影响。第63页/共120页64（４）用信号量实现前趋关系。为实现前趋关系Pi→Pj，可为它们设置一个初值为0的信号量S。在学习时，应清楚对S的wait操作和signal操作应分别安排在什么位置，同时必须注意wait(S)操作和signal(S)操作也必须成对出现。

第64页/共120页65信号量的分类：

整型信号量（integersemaphore)：信号量是整数。记录型信号量（recordsemaphore)：每个信号量s除一个整数值s.value（计数）外，还有一个进程等待队列s.L，其中是阻塞在该信号量的各个进程的标识

第65页/共120页661、整型信号量

最初由Dijkstra把整型信号量定义为一个整型量，除初始化外，仅能通过两个标准的原子操作wait(s)和signal(s)来访问，分别称为P和V操作。wait(s):whiles<=0dono_op;

s:=s-1;

signal(s):s:=s+1

ifs<=0thenwakeup(P1);

第66页/共120页672、记录型信号量

在整型信号量中的wait(s)，只要s<=0则会不停地测试，该机制不遵循“让权等待”的准则，记录型的信号量描述如下：

typesemaphore=record

Value:integer;

L:

listofprocess;

end第67页/共120页68相应的wait(s)和signal(s)操作描述如下：procedurewait(s)

vars:semaphore;

begin

s.Value:=s.Value-1;

ifs.Value<0thenblock(s,L);

end;proceduresignal(s)

vars:semaphore;

begin

s.Value:=s.Value+1;

ifs.Value<=0thenwakeup(s.L);

end;

当s.Value初值为1时表示互斥信号量。第68页/共120页693、AND型信号量

上述的进程互斥问题是针对进程之间要共享一个临界资源，在某些场合下，一个进程要先获得两类或更多的共享资源方能执行任务。例：有A、B进程，它们共享D和E两个临界资源，对这两个数据分别用信号量S1和S2，且S1=S2=1，则在这两个进程中必然会有：processA

processB

wait(S1);

wait(S2);

wait(S2);

wait(S1)；

第69页/共120页70如按如下调度方式，则A、B进程进入了死锁。

时刻ABS1S2(1)Wait(s1)S1=0(2)Wait(s2)S2=0(3)Wait(s2)S2=-1(4)等待(5)Wait(s1)S1=-1(6)等待第70页/共120页71AND同步机制的基本思想：将进程在整个运行过程中所需要的所有临界资源一次性分配给进程，使用完后一起释放，只要一个资源没有分配到则其它可能分配到的资源也不分配，已经分配的全部释放，AND原语对资源的分配是原子的，其操作定义如下：第71页/共120页72swait(s1,s2,...sn)

ifs1>=1ands2>=1and...sn>=1then

fori=1tondo

si:=si-1;

endfor

else

将调用swait的进程置入所有的对应于si的等待该信号的进程队列中。

endif;

ssignal(s1,s2,...sn)

fori=1tondo

si:=si+1;

将与si有关的进程插入到就绪队列中。

endfor第72页/共120页734、信号量集在记录型信号量中，P和V仅执行减1和增1操作，当一次需要N个某类资源时则要进行N次P操作，其效率低下，此外在某些情况下当资源数低于某一下限值便不分配，在每次分配之前，必须测试该资源总数是否大于下限值，下面是对AND信号量机制的改写：第73页/共120页74si：资源总数，

ti:下限值，di:所需的资源数

swait(s1,t1,d1;...sn,tn,dn)

ifs1>=t1and...sn>=tnthen

fori=1tondo

si=si-di;

endfor;

else

将调用swait的进程插入到相应的si的等待队列中;

第74页/共120页75ssignal(s1,d1;...sn,dn)

fori=1tondo

si=si+di;

将对应于si的所有进程唤醒到就绪队列中;

endfor;

第75页/共120页76swait(s,d,d)：此时信号量集中仅有一个信号量，允许每次申请d个资源，当少于d时不分配。swait(s,1,1)：为一般的记录型信号量或互斥信号量(s=1)swait(s,1,0)：当s>=1时允许多个进程进入，当s=0时阻止任何进程进入。第76页/共120页772.3.3信号量的应用1)利用信号量实现进程互斥设有2个并发进程P0和P1互斥共享counter变量。第77页/共120页78begin

count:integer:=0;

s:semaphore:=1;

processPin

processPout

r1:integer

r2:integer;

begin

begin

p(s);

p(s);

r1:=count;

r2:=count;

r1:=r1+1;

r2:=r2-1;

count:=r1;

count:=r2;

v(s);

v(s)

end;

end;

coend;

end;第78页/共120页792）PV操作实现前趋图第79页/共120页80定义：

vara,b,c,d,e,f,g:signal:=0,0,0,0,0,0,0processs1

processs2

processs3

s1;

P(a);

P(b);

V(a);

s2;

s3;

V(b);

V(c);

V(e);

end;

V(d);

end;

end;

processs4

processs5

processs6

P(c);

P(d);

P(e);

s4;

s5;

P(f);

V(f);

V(g);

P(g);

end;

end;

s6

end

第80页/共120页81【例1】桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用，请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。第81页/共120页82解：在本题中，应设置三个信号量S、So、Sa，信号量S表示盘子是否为空，其初值为l；信号量So表示盘中是否有桔子，其初值为0；信号量Sa表示盘中是否有苹果，其初值为0。同步描述如下：

第82页/共120页83intS＝1;intSa＝0;intSo＝0;main(){cobeginfather();/*父亲进程*/son();/*儿子进程*/daughter();/*女儿进程*/coend

｝第83页/共120页84father(){while(1){P(S);

将水果放入盘中;if（放入的是桔子）V(So);elseV(Sa);}}第84页/共120页85

son(){while(1){P(So);

从盘中取出桔子;V(S);

吃桔子;

｝

}第85页/共120页86

daughter(){while(1){P(Sa);

从盘中取出苹果;V(S);

吃苹果;

｝｝第86页/共120页87三个进程P1、P2、P3互斥使用一个包含N（N>0)个单元的缓冲区。P1每次使用produce()生成一个正整数，并用put()送入缓冲区的某一个单元中；P2每次用getodd()从该缓冲区中取走一个奇数，并用countodd()统计奇数的个数；P3每次用geteven()从该缓冲区中取走一个偶数，并用counteven()统计偶数的个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义，要求用伪代码描述。思考题1第87页/共120页88第88页/共120页89思考题2四个进程A、B、C、D都要读一个共享文件F，系统允许多个进程同时读文件F。但限制是进程A和进程C不能同时读文件F，进程B和进程D也不能同时读文件F。为了使这四个进程并发执行时能按系统要求使用文件，现用PV操作进行管理，请回答下面的问题：第89页/共120页901）应定义的信号量及初值：

。2）在下列的程序中填上适当的P、V操作，以保证它们能正确并发工作：

A()B()C()D(){{{{[1];[3];[5];[7];readF;readF;readF;readF;[2];[4];[6];[8];}}}}第90页/共120页91思考题解答：

（1）定义二个信号量S1、S2，初值均为1，即：S1=1，S2=1。其中进程A和C使用信号量S1，进程B和D使用信号量S2。（2）从[1]到[8]分别为：P(S1)V(S1)P(S2)V(S2)P(S1)V(S1)P(S2)V(S2)第91页/共120页92内容回顾什么是进程同步？什么是临界资源和临界区？进程同步遵循的规则？几种常见的信号量机制？第92页/共120页932.3.4管程管理对于信号量机制，每个访问临界资源的进程自备PV操作，给系统管理带来了麻烦，而且容易出现死锁。共享变量分部到各程序中，使程序易读性差。正确性难以保证。第93页/共120页941管程的基本概念为了更易于编写正确的程序，Hoare和BrinchHansan提出了一种高级的同步原语，称为管程(monitor)。

第94页/共120页95基本思想：将共享资源用共享数据结构表示，用对数据结构操作的一组过程表示资源管理程序，将共享数据结构和对它们