33操作系统第三章.ppt
第三章 进程管理进程同步 定定义义：我我们们把把在在异异步步环环境境下下的的一一组组并并发发进进程程因因直直接接制制约约，互互相相发发送送消消息息，并并进进行行互互相相合合作作、互互相相等等待待，使使得得各各进进程程按按一一定定的的速速度度执执行行的的过过程称为进程间的同步。程称为进程间的同步。具具有有同同步步关关系系的的一一组组并并发发进进程程称称为为合合作作进进程程；合作进程间互相发送的信号称为消息或事件。合作进程间互相发送的信号称为消息或事件。同步的概念进程同步进程同步 例：计算进程和打印进程公用同一缓冲区例：计算进程和打印进程公用同一缓冲区BufBuf。P PC C(计算计算)P PP P（打印）打印）A:local A:local BufBuf B:local B:local P PririRepeat RepeatRepeat Repeat BufBuf BufBuf P Priri BufBufUntil Until BufBuf=空空 计算计算Until Until P Priri 空空得到计算结果得到计算结果打印打印BufBuf中数据中数据BufBuf 计算结果计算结果 清除清除BufBuf中数据中数据GotoGoto A A GotoGoto B B进程同步进程同步 问题：浪费CPU时间。采用消息的方法实现直接制约(同步)：设过程Wait(过程名)表示进程等待合作进程发来消息。过程signal(消息名)表示向合作进程发送消息。设 消 息 名 Bufempty表 示 Buf空，设 消 息 名Buffull表示Buf满（装满数据）。初始化：Bufempty=true，Buffull=false 进程同步进程同步Pc PpA:wait(Bufempty)B:wait(Buffull)计算 打印Buf中的数据 Buf 计算结果 清除Buf中的数据 Bufempty false Buffull false Signal(Buffull)signal(Bufempty)Goto A Goto B进程同步进程同步 私用（有）信号量私用（有）信号量 把把各各进进程程间间发发送送的的消消息息作作为为信信号号量量看看待待，这这种种信信号号量量只只与与制制约约进进程程和和被被制制约约进进程程有有关关，但但不不与与整整组组并并发发进进程程有有关关，这这种种信信号号量量称称为为私用信号量（私用信号量（Private SemaphorePrivate Semaphore）。）。与与私私用用信信号号量量相相对对应应，我我们们称称进进程程互互斥斥时时使用的信号量为公用信号量。使用的信号量为公用信号量。进程同步进程同步 用用P P、V V原语操作实现进程的直接制约原语操作实现进程的直接制约(同步同步)例例子子：设设进进程程和和通通过过缓缓冲冲区区队队列列传传送送数数据据（如如图图3.143.14）,P PA A为为发发送送进进程程，P PB B为为接接收收进进程程；P PA A发发送送数数据据时时调调用用发发送送过过程程deposit(data)deposit(data)，P PB B接接收收数数据据时时调调用用过过程程remove(data)remove(data)。且且数数据据的的发发送送与接收过程满足如下条件：与接收过程满足如下条件：1 1）在在P PA A至至少少送送一一块块数数据据入入一一个个缓缓冲冲区区之之前前，P PB B不不可可能能从从缓缓冲冲区区中中取取出出数数据据（假假定定数数据据块块长长等于缓冲区长度）。等于缓冲区长度）。进程同步进程同步 2）P PA A往往缓缓冲冲队队列列发发送送数数据据时时，至至少少有有一一个缓冲区是空的；个缓冲区是空的；3 3）由由P PA A发发送送的的数数据据块块在在缓缓冲冲队队列列中中按按先先进先出（进先出（FIFOFIFO）方式排列。方式排列。P PA A BuffBuff1 1 buffbuff2 2 buffbuff3 3 .BuffBuffn n P PB B进程同步进程同步 我们按如下三步描述过程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.进程同步进程同步 P PB B：remove(data)remove(data)Begin local x;Begin local x;P(BufP(Buf-full);-full);按按FIFOFIFO方方式式选选择择一一个个装装满满数数据据的缓冲区的缓冲区Buf(xBuf(x););data data Buf(xBuf(x););Buf(xBuf(x)置空标记；置空标记；V(BufV(Buf-empty);-empty);End.End.进程同步进程同步 这里，局部变量x用来指明缓冲区的区号；给Buf(x)置标志位是为了便于区别和搜索空缓冲区与非空缓冲区。比较互斥与同步的两个例子：互斥 同步设 置 信 号 量 S（公 用）设 置 信 号 量 S1，S2 （私用）信号量初值S=1 信号量初值S1=n.，S2=0。进程同步进程同步 算法描述：P1 P1 Begin begin P(S)P(S1)临界资源 送数 V（S）V（S2）End End进程同步进程同步 P2 P2P2 P2 Begin begin Begin begin P(S)P(S P(S)P(S2 2)临界资源临界资源 取数取数 V V（S S）V V（S S1 1）End EndEnd End进程同步进程同步 示图：P1、P2 P1 P2 P（S）P(S1)P(S2)临界区 送数 取数 V（S）V（S2）V（S1）经典进程的同步问题经典进程的同步问题 在多道程序环境下，进程同步问题十分重要，出现一系列经典的进程同步问题，其中有代表性有：生产者生产者消费者问题消费者问题哲学家进餐问题哲学家进餐问题读者读者写者问题写者问题 1 1、“生产者生产者消费者消费者”问题问题 生 产 者 消 费 者 问 题（Producer Consumer Problems）我们把系统中使用某一类资源的进程称为该资源的消费者，把释放同类资源的进程称为该资源的生产者。多个生产者 多个消费者P1 多个缓冲区 C1P2 1 2 .n C2 Pn Cn1 1、“生产者生产者消费者消费者”问题问题设设生生产产者者进进程程和和消消费费者者进进程程是是等等效效的的，其其 中中，各各 生生 产产 者者 进进 程程 使使 用用 的的 过过 程程deposit(data)deposit(data)和和各各消消费费者者使使用用的的过过程程removeremove(data)(data)可描述如下：可描述如下：首首先先，我我们们可可以以看看到到生生产产者者消消费费者者问问题题是是一一个个同同步步问问题题，即即生生产产者者和和消消费费者者之之间满足如下条件：间满足如下条件：1 1、“生产者生产者消费者消费者”问题问题（1）消费者想接收数据时，有界缓冲区中至少有一个单元是满的。（2）生产者想发送数据时，有界缓冲区中至少有一个单元是空的。另外，由于有界缓冲区是临界资源，因此，各生产者进程和各消费者进程之间必须互斥执行，即在一个时刻，只有一个进程使用缓冲区。1 1、“生产者生产者消费者消费者”问题问题下面是多个生产者、多个消费者、多个缓冲区的问题：设置信号量：mutex：公用信号量，表示生产者进程与消费者进程的互斥信号量；avail：生产者进程的私用信号量，其值表示有界缓冲区中的空单元数目（缓冲区空的个数）；1 1、“生产者生产者消费者消费者”问题问题 full：消费者进程的私用信号量，其值表示有界缓冲区中的非空单元数目（缓冲区满的个数）。给信号量赋初值：mutex初值为1；avail初值为n；full初值为0。1 1、“生产者生产者消费者消费者”问题问题过程描述：deposit(data)remove(data)begin beginP(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 2、“哲学家进餐哲学家进餐”问题问题n问题描述：问题描述：有五个哲学家，他们的生活方式是交替地进行思考和进餐。他们共用一张圆桌，分别坐在五张椅子上。在圆桌上有五个碗和五支筷子，平时一个哲学家进行思考，饥饿时便试图取用其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐。进餐毕，放下筷子又继续思考。n哲学家进餐问题可看作是并发进程并发执行时，处理共享资源的一个有代表性的问题。n semaphore stick5=1,1,1,1,1;/*分别表示分别表示5支筷子支筷子*/Main()cobegin philosopher(0);philosopher(1);philosopher(2);philosopher(3);philosopher(4);coend 哲学家进餐问题的解决哲学家进餐问题的解决 while(true)while(true)思考思考;p(sticki);p(sticki);P(stick(i+1)%5);P(stick(i+1)%5);进餐；进餐；V(sticki);V(sticki);V(stick(i+1)%5);V(stick(i+1)%5);第第i个哲学家的活动算法个哲学家的活动算法philosopher(int i)返回说明：说明：1、此算法可以保证不会有相保证不会有相邻的两位哲学家同时进餐邻的两位哲学家同时进餐。2、若五位哲学家同时饥饿而各自拿起了左边的筷子，这使五个信号量stick均为0，当他们试图去拿起右边的筷子时，都将因无筷子而无限期地等待下去，即可能会引起死锁可能会引起死锁。3 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()cobegin reader();writer();coend “读者读者写者写者”问题的解决问题的解决 while(true)while(true)p(p(rmutexrmutex););if(if(readcountreadcount=0)p(=0)p(wmutexwmutex););/*/*第一位读者阻止写者第一位读者阻止写者*/readcountreadcount+;+;V(V(rmutexrmutex););读数据集；读数据集；p(p(rmutexrmutex););readcountreadcount-;-;if(if(readcountreadcount=0)v(=0)v(wmutexwmutex););/*/*第第末位读者允许写者进末位读者允许写者进*/V(V(rmutexrmutex););reader()修改修改readcount修改修改readcount while(true)p(wmutex);/*阻止其它进程（读、写）进阻止其它进程（读、写）进/写数据集；写数据集；V(wmutex);/*允许其它进程（读、写）进允许其它进程（读、写）进/writer()
