进程管理.ppt

第三章 进程管理进程同步定义：我们把在异步环境下的一组并发进 程因直接制约，互相发送消息，并进行互相 合作、互相等待，使得各进程按一定的速度 执行的过程称为进程间的同步 具有同步关系的一组并发进程称为合作进程 ；合作进程间互相发送的信号称为消息或事 件 同步的概念进程同步例：计算进程和打印进程公用同一缓冲区Buf PC(计算) PP（打印）A:local Bufˊ B:local Pri Repeat RepeatBufˊ Buf Pri Buf Until Bufˊ=空 计算Until Pri ≠ 空 得到计算结果打印Buf中数据 Buf 计算结果 清除Buf中数据 Goto A Goto B进程同步问题：浪费CPU时间采用消息的方法实现直接制约(同步)：①设过程Wait(过程名)表示进程等待合作进程发 来消息过程signal(消息名)表示向合作进程发送消息②设消息名Bufempty表示Buf空，设消息名 Buffull表示Buf满（装满数据）。

③初始化：Bufempty=true，Buffull=false 进程同步Pc Pp A:wait(Bufempty) B:wait(Buffull)计算 打印Buf中的数据Buf 计算结果 清除Buf中的数据Bufempty false Buffull falseSignal(Buffull) signal(Bufempty)Goto A Goto B进程同步私用（有）信号量把各进程间发送的消息作为信号量看待 ，这种信号量只与制约进程和被制约进程有 关，但不与整组并发进程有关，这种信号量 称为私用信号量（Private Semaphore）与私用信号量相对应，我们称进程互斥 时使用的信号量为公用信号量进程同步用P、V原语操作实现进程的直接制约(同步)例子：设进程和通过缓冲区队列传送数据（ 如图3.14）, PA为发送进程，PB为接收进程； PA发送数据时调用发送过程deposit(data)， PB接收数据时调用过程remove(data)。

且数据 的发送与接收过程满足如下条件：1）在PA至少送一块数据入一个缓冲区之前 ，PB不可能从缓冲区中取出数据（假定数据块 长等于缓冲区长度）进程同步2）PA往缓冲队列发送数据时，至少有 一个缓冲区是空的；3）由PA发送的数据块在缓冲队列中按先 进先出（FIFO）方式排列PA Buff1 buff2 buff3 …. Buffn PB进程同步我们按如下三步描述过程deposit(data)和 remove (data)1）设Buf-empty为进程PA的私用信号量，表 示缓冲区是否有空；Buf-full为进程PB的私 用信号量，表示缓冲区是否有数可取；2）Buf-empty的初始值为n (n为缓冲队列 的缓冲区个数)，Buf-full的初始值为0;进程同步3) 算法描述如下：PA： deposit(data)Begin local x;P(Buf-empty);按FIFO方式选择一个空缓冲区 Buf(x);Buf(x) data；Buf(x)置满标记；V(Buf-full); End.进程同步PB： remove(data)Begin local x;P(Buf-full);按FIFO方式选择一个装满数 据的缓冲区Buf(x);data Buf(x);Buf(x)置空标记；V(Buf-empty); End.进程同步这里，局部变量x用来指明缓冲区的区号 ；给Buf(x)置标志位是为了便于区别和搜 索空缓冲区与非空缓冲区。

比较互斥与同步的两个例子： 互斥 同步 ①设置信号量S（公用） 设置信号量S1， S2 （私用） ②信号量初值S=1 信号量初值 S1=n.，S2=0 进程同步③算法描述：P1 P1Begin beginP(S) P(S1)临界资源 送数V（S） V（S2 ）End End进程同步P2 P2Begin beginP(S) P(S2)临界资源 取数V（S） V（S1 ）End End进程同步示图： P1、P2 P1 P2P（S） P(S1) P(S2)临界区 送数 取数V（S） V（S2） V（S1）经典进程的同步问题在多道程序环境下，进程同步问题十分重要，出现一系列经典的进程同步问题，其中有代表性有：§ 生产者—消费者问题§ 哲学家进餐问题§ 读者—写者问题1、“生产者—消费者”问题生产者–消费者问题（Producer– Consumer Problems）我们把系统中使用某一类资源的进程称 为该资源的消费者，把释放同类资源的进 程称为该资源的生产者。

多个生产者 多个消费 者 P1 多个缓冲区 C1 P2 1 2 …. n C2 … … Pn Cn1、“生产者—消费者”问题设生产者进程和消费者进程是等效的， 其中，各生产者进程使用的过程 deposit(data)和各消费者使用的过程 remove( data)可描述如下： 首先，我们可以看到生产者–消费者问 题是一个同步问题，即生产者和消费者之 间满足如下条件：1、“生产者—消费者”问题（1）消费者想接收数据时，有界缓冲区中 至少有一个单元是满的 （2）生产者想发送数据时，有界缓冲区中 至少有一个单元是空的 另外，由于有界缓冲区是临界资源，因 此，各生产者进程和各消费者进程之间 必须互斥执行，即在一个时刻，只有一 个进程使用缓冲区1、“生产者—消费者”问题下面是多个生产者、多个消费者、多个缓 冲区的问题：①设置信号量：mutex：公用信号量，表示生产者进程与 消费者进程的互斥信号量；avail：生产者进程的私用信号量，其值 表示有界缓冲区中的空单元数目（缓冲 区空的个数）；1、“生产者—消费者”问题full：消费者进程的私用信号量，其值表 示有界缓冲区中的非空单元数目（缓冲 区满的个数）。

②给信号量赋初值：mutex初值为1； avail初值为n；full初值为0 1、“生产者—消费者”问题③过程描述： deposit(data) remove(data) begin begin P(avail) P(full) P(mutex) P(mutex) 送数到缓冲区某单元 取缓冲区某单元数 据 V（full） V（avail） V（mutex） V（mutex） End End“生产者-消费者”问题中应注意1. 互斥信号量的P,V操作在每一程序中必须成对出现. 2. 资源信号量(full,empty)也必须成对出现,但可分别处于不同的 程序中. 3. 多个P操作顺序不能颠倒. 4. 先执行资源信号量的P操作,再执行互斥信号量的P操作,否则可 能引起进程死锁. 5. 它是一个同步问题：（1）消费者想要取产品，有界缓冲区中至少有一个单元是满的 2）生产者想要放产品，有界缓冲区中至少有一个是空的。

6. 它是一互斥问题有界缓冲区是临界资源，因此，各生产者进程和各消费者进 程必须互斥执行返回2、“哲学家进餐”问题n问题描述：有五个哲学家，他们的生活方式是交替地进行思考和进餐他们共用一张圆桌，分别坐在五张椅子上在圆桌上有五个碗和五支筷子，平时一个哲学家进行思考，饥饿时便试图取用其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐进餐毕，放下筷子又继续思考n哲学家进餐问题可看作是并发进程并发执行时，处理共享资源的一个有代表性的问题n semaphore stick[5]={1,1,1,1,1}; /*分别表示5支筷子*/Main(){cobeginphilosopher(0);philosopher(1);philosopher(2);philosopher(3);philosopher(4);coend}哲学家进餐问题的解决{while(true){思考; p(stick[i]); P(stick[(i+1)%5]); 进餐； V(stick[i]);V(stick[(i+1)%5]); } }第i个哲学家的活动算法philosopher(int i)返回说明：1、此算法可以保证不会有相邻的两位哲学家同时进餐。

2、若五位哲学家同时饥饿而各自拿起了左边的筷子，这使五个信号量stick均为0，当他们试图去拿起右边的筷子时，都将因无筷子而无限期地等待下去，即可能会引起死锁3、“读者—写者”问题n问题描述：一个数据对象（数据文件或记录）可被多个进程共享其中，reader进程要求读，writer 进程要求写或修改允许多个reader进程同时读共享数据，但绝不允许一个writer进程与其它的reader进程或writer进程同时访问，即writer进程必须与其它进程互斥访问共享对象n“读者—写者”问题的同步算法描述设置一个共享变量和两个信号量：共享变量Readcount：记录当前正在读数据集的读进程数目，初值为0读互斥信号量Rmutex ：表示读进程互斥地访问共享变量readcount，初值为1.写互斥信号量wmutex：表示写进程与其它进程（读、写）互斥地访问数据集，初值为1.“读者—写者”问题的解决n“读者—写者”问题的同步算法描述semaphore rmutex=1; semaphore wmutex=1; int readcount=0; Main() {cobeginreader();writer();coend}“读者—写者”问题的解决{while(true){p(rmutex); if(readcount= =0) p(wmutex);/*第一位读者阻止写者*/readcount++;V(rmutex);读数据集； p(rmutex); readcount--; if(readcount= =0) v(wmutex);/*第末位读者允许写者进*/V(rmutex); } }reader()修改 readcount修改 readcount{while(true){p(wmutex); /**阻止其它进程（读、写）进/写数据集； V(wmutex)。