《第三章 进程管理B课件》由会员分享，可在线阅读，更多相关《第三章 进程管理B课件（56页珍藏版）》请在金锄头文库上搜索。
1、第三章 进程管理,进程的引入和定义 进程状态及转换 进程的产生和终止 进程的描述 进程控制 进程互斥与同步 进程间通信 管道（pipe） 线程（Thread）,3.6 进程互斥与同步,1 进程互斥 为提高资源利用率采取了程序并发执行的办法。由于多个并发进程间对有限资源的争夺和共享而可能导致程序执行结果失去封闭性。 1. 临界资源和临界区（critical section） 临界资源（critical resource） 一次只允许一个进程使用 临界区（critical section） 进程中访问临界资源的那段代码 。若在一组并发进程的各自临界区中都使用了相同的共享变量，则称这组临界区为相关临
2、界区。,例如：一个联网的航空售票系统,航空售票系统有n个终端分布在各地，通过网络连接到中心服务器。顾客通过在各地的终端购买飞机票。每个终端登录到服务器，服务器为每个终端建立一个售票进程，售票进程在卖票之前先检查总的飞机票数t是否大于或等于顾客所需飞机票数m，如果tm说明没有足量的飞机票可以卖给顾客；否则有票可以出售给顾客，每次卖飞机票给顾客后就把总的飞机票数t减去m。 /售票进程用伪码可以描述如下： sell(m) begin read（t）； if (tm) then begin 售出m张飞机票给顾客； t：=t-m； end； else write（飞机票不足）； end,考虑这种情形,并
3、发进程互斥执行的准则,并发的多个进程间在竞争资源时，如果能够避免对临界资源使用的冲突，就能保证并发进程执行结果的一致性和封闭性。即为保证执行结果的封闭性，多个并发进程共享临界区内的公有资源，但不允许并发进程同时进入临界区。 间接制约：这种由共享公有资源而造成的对并发进程执行速度的相互制约。 进程互斥：由进程间间接制约的关系导致的多个并发进程不能同时访问同一临界区 。,进程互斥执行必须满足的四个准则,（1）每次至多允许一个进程处于临界区内； （2）进程在有限时间内能够进入其临界区； （3）在其临界区之外停止的进程不应当阻塞别的进程； （4）对于有关的进程速度或者CPU数不作任何假定。 实现进程互
4、斥的方法有硬件方法，如禁止中断，特殊的机器指令等；更多的是软件方法，如P、V原语，监控程序等。,2 互斥与同步机制,1. 禁止中断（Disabling Interrupts） 是最简单的方法，让每个进程在即将进入临界区之前关中断，在执行完对共享资源的操作的那一段程序之后又开中断。 两个弊端 赋予用户进程禁止中断的权力是很危险的事，因为如果用户关闭中断后就不再打开会导致系统停止。 执行效率也会明显降低，因为操作系统不能随时切换进程。 利用禁止中断实现进程互斥 ： repeat /禁止中断 /临界区 /开中断 until false,2. TS硬件指令（Test and Set） 专门的硬件指令，
5、允许我们在一个存贮周期去测试和修改一个字的内容，或者交换两个字的内容。 function TS (var lock:Boolean)：boolean； begin TS：=lock ； lock：=true ； end 利用TS指令实现进程互斥 ： repeat while TS (lock) do skip; critical section; lock:= false; until false,使用TS指令实现互斥有几个优点： （1）可用于任意数量进程的单处理机系统或共享主存的多处理机系统； （2）实现简单，易于验证； （3）支持多个临界区，每个临界区用自己的布尔变量lock标志。 TS指
6、令的方法也存在严重缺陷： （1）由于采用的是忙等待策略，要不停地循环检测Lock值，浪费处理器资源，效率很低； （2）有可能有多个进程同时等待进入临界区，而选择哪一个进程进入临界区是随意的，这样就有可能导致某些进程长时间得不到临界区的访问权； （3）在单机系统中， 可能出现死锁。,信号量,3. 信号量和P、V原语 信号量：一个仅能由同步原语进行操作的整型变量，用来实现进程之间的互斥和同步。1965年由荷兰著名计算机科学家E.W.Dijkstra提出 。 分为 二元信号量：它仅允许取值0和1，主要用作互斥变量； 一般信号量：它允许取任意整数值，主要用于进程之间的同步。 信号量值为0时，说明没有资
7、源可用，为正整数n表示有n个同类资源可用，为负整数m则表示有|m|个进程被堵塞在该临界资源外。 操作系统利用信号量对进程和资源进行控制和管理，信号量的值仅能由P、V操作来改变。,P、V原语,P、V原语是不可中断的过程，它们在屏蔽中断的情况下连续执行。可来实现并发进程对临界区的互斥访问。 假设信号量sem的值只能由P、V操作来改变，操作系统利用它的状态对进程和资源进行管理。 P、V操作分别定义为P(sem)和V(sem) 。,P(sem)执行的动作步骤： （1）semsem1； （2）if sem0 then block ( sem ) ； /若sem0，则阻塞当前进程，将其插入等待 sem的队
8、列，调度另一进程运行。 （3）否则，返回当前进程继续执行,V(sem)执行的动作步骤： （1）semsem1； （2）if sem 0 then active (sem) / 从该信号量的等待队列中唤醒一等待进程，使之从阻塞态变成就绪态，插入就绪队列，然后再 返回当前进程继续执行或转进程调度。 （3）否则，返回当前进程继续执行,P、V操作实现两个并发进程PA、PB的互斥的例子： cobegin process PA begin P (sem)； 临界区代码SA； V (sem)； end,process PB begin P (sem)； 临界区代码 SB； V (sem)； end coen
9、d,进程同步,3 进程同步 同步一般是指两个事件的发生有着某种时序上的关系，进程同步是指系统中的几个进程为共同完成一个任务而产生的相互合作、协同运行关系。例如：,并发进程间的直接制约一组在异步环境下的并发进程，各自的执行结果互为对方的执行条件，从而限制各进程的执行速度的过程。 进程间的同步把一组并发进程因直接制约而互相发送消息、互相合作、互相等待，使得各进程按一定的速度执行的过程。,同步例子,例如，假设有5个进程P1、P2、P3、P4、P5，它们的关系为：P1执行完成后，P2、P4才能执行，P2执行完成后，P3才能执行，P3和P4都完成后，P5才能执行。如右图所示。 使用P、V操作实现这样的流
10、程！,三个经典的同步/互斥问题,1生产者-消费者问题（producer-consumer problems） 有一个可放n件产品的缓冲区，m个生产者（producer）P1，P2，Pm和k个消费者C1，C2，Ck。每个生产者每次生产一件产品放入缓冲区，每个消费者每次从缓冲区取一件产品去消费。 其中缓冲区是生产者和消费者的共享资源，生产者和消费者对缓冲区的访问必须满足：生产者要往缓冲区中放产品时，缓冲区至少还有一个空单元可放产品；消费者要从缓冲区中取产品了消费时，缓冲区中至少还有一个产品可供消费。可以看出这是一个典型的同步问题。,生产者消费者进程描述,求解 环形缓冲区,生产者与消费者关系的形式描
11、述，设： 公用信号量 mutex ：初值为1，用于实现临界区的互斥； 生产者私用信号量empty：初值为n，指示空缓冲块数目； 消费者私用信号量full：初值为0，指示满缓冲块数目； 整型量in和out：初值均为0，in 指示空缓冲块序号头指针，out指示满缓冲块序号头指针。,process consumer j ( j=1,2, , n ) begin repeat P ( full ); P ( mutex ); P：= buffer out； Out：= (out+1) mod n ； V ( mutex )； V (empty )； until false end,process pr
12、oducer i ( i=1,2, , m ) begin repeat produce a product ； P (empty) ； P (mutex) ； Buffer in：=product ； in：= (in+1) mod n ； V (mutex) ； V (full) ； until false end；,begin mutex, empty, full：semaphore； buffer：array 0n-1 of integer； in,out：intege； in：=out：=0 ； mutex：=1； empty：=n； full：=0； begin cobegin p
13、rocess producer i ( i=1,2, , m ) process consumer j ( j=1,2, , n ) coend ； end； end,2读者-写者（reader-writer）问题 进程共享一个数据区，数据区可以是一个文件、一块内存空间、或一组寄存器。其中有些进程只能读数据区中的数据，而另外一些进程只能写数据区。把只能读数据区的进程叫做“读者（reader）”，只能写数据区的进程叫做“写者（writer）”。而且reader和writer要满足：多个reader可同时读数据区；任一时刻只能有一个writer可以写数据区；reader和writer不能同时对数据
14、区进行操作。 读者和读者之间是可以同时访问数据区的，不存在制约关系。一次只能有一个写者在写数据区，写者与写者之间是互斥的制约关系。读者和写者之间也是存在互斥的制约关系。,一个写者在写数据区时，只有它一个进程能访问数据区，可以用一个信号量来阻塞其它想访问数据区的进程。为了使得读者能够同时读数据区，引入一个计数变量readcount来记录同时读数据区的进程数。readcount是读者之间的共享变量，所以对它的存取也要互斥进程。 设：变量readcount 记录当前正在访问该对象的读者个数； 互斥信号量mut 用来互斥对readcounnt的修改； 互斥信号量wmut 用于互斥写者，它也可由当前第一
15、个要求访问该对象的读者和最后一个退出访问的读者使用，但它不被中间的那些读者使用。,var mut, wmut：semaphore； mut,：=1；wmut：=1； readcount：integer； readcount：=0； begin cobegin process reader i (i=1,2, m) process writer j (j=1,2, n) coend； end,process reader i (i=1,2, m) begin repeat P (mut )； if readcount=0 then P ( wmut )； readcount：=readcount
16、+1； V ( mut )； Perform read operation； /实行读操作/ P ( mut )； Readcount：=readcount-1； if readcount=0 then V (wmut)； V ( mut )； until false； end；,process writer j (j=1,2, n) begin repeat P (wmut)； Perform write operation； /实行写操作/ V (wmu)； until false; end；,哲学家就餐问题,3哲学家就餐问题（The Dining Philosophers Problem） 五个哲学家
