1、主要内容：主要内容：n同步与同步机制n信号量及其操作n信号量的应用n哲学家进餐问题n生产者-消费者问题n读者-写者问题n理发师问题 著名的生产者-消费者问题是计算机操作系统中并发进程内在关系的一种抽象，是典型的进程同步问题。在操作系统中，生产者进程可以是计算进程、发送进程；而消费者进程可以是打印进程、接收进程等等。解决好生产者-消费者问题就解决好了一类并发进程的同步问题。 生产者-消费者问题表述：有n个生产者和m个消费者，连接在k个单位缓冲区的有界环形缓冲池上，故又叫有界缓冲问题。其中pi和cj都是并发进程，只要缓冲区未满，生产者进程pi所生产的产品就可以放入缓冲区；只要缓冲区非空，消费者进程
2、cj就可以从缓冲区取走并消耗产品。 .01k-1.k-2. intint k; k; typedef anyitem typedef anyitem item; /item item; /item类型类型 nextp, nextcnextp, nextc: item;: item; item bufferk item bufferk; int int in=0, out=0, counter=0; in=0, out=0, counter=0; process producer(voidprocess producer(void) while(TRUE while(TRUE) produce
3、an item in nextp produce an item in nextp; if(counter=k) sleep(producer if(counter=k) sleep(producer);); bufferin=nextp bufferin=nextp; ; in=(in+1) % k; in=(in+1) % k; counter+; counter+; if(counter=1) wakeup(consumer if(counter=1) wakeup(consumer);); process consumer(voidprocess consumer(void) whil
4、e(TRUE while(TRUE) if(counter=0) sleep(consumer if(counter=0) sleep(consumer);); nextc=bufferout nextc=bufferout; out=(out+1) % k; out=(out+1) % k; counter-; counter-; if(counter=k-1) wakeup(producer); if(counter=k-1) wakeup(producer); consume the item in nextc consume the item in nextc; 生产者和消费者单独运行
5、都是正确的，但是，如果并发执行（交替执行）就会产生错误：结果不唯一永远等待出现错误结果的原因在于各个进程访问缓冲区的速率不同，要得到正确结果，需要调整并发进程的速度，这需要通过在进程间交换信号或消息来调整相互速率，达到进程协调运行的目的。这种协调过程称为进程同步。进程同步。操作系统实现进程同步的机制称为同步机制，它通常由同步原语组成。常用的同步机制有：信号量与信号量与PVPV操作、管程和操作、管程和消息传递。消息传递。 1.1.前节种种方法解决临界区调度问题的缺点前节种种方法解决临界区调度问题的缺点 1)对不能进入临界区的进程，采用忙式等待测试法，浪费CPU时间。2)将测试能否进入临界区的责任
6、推给各个竞争的进程会削弱系统的可靠性，加重了用户编程负担。 3）这些方案只能解决进程竞争，不能解决进程协作问题。2.2.信号量同步机制的提出信号量同步机制的提出 1965年荷兰计算机科学家E.W.Dijkstra提出了新的同步工具-信号量和P、V操作。他将交通管制中多种颜色的信号灯管理交通的方法引入操作系统，让两个或多个进程通过特殊变量展开交互。一个进程在某一特殊点上被迫停止执行直到接收一个进程在某一特殊点上被迫停止执行直到接收到一个对应的特殊变量值，这种特殊变量就是信号量到一个对应的特殊变量值，这种特殊变量就是信号量(Semaphore)。进程可以使用P、V两个特殊操作来发送和接收信号，如果
7、协作进程的相应信号仍未送到，则进程被挂起直到信号送达为止。（注意：这里的“挂起”并不是第二章里的被对换到硬盘上，而是转入等待状态！）操作系统中，信号量是用来表示物理资源的实体，用一个结构性变量表示，有两个分量：一个是信号量的值，另一个是指向信号量的队列的指针。除赋初值外，信号量仅能由同步原语P和V对其进行操作，没有任何其他方法可以检查和操作信号量。原语是操作系统内核中执行时不可中断的过程，即原子操作。Dijkstra发明了两个信号量操作原语：P操作原语和V操作原语（荷兰语中“测试（Proberen）”和“增量（Verhogen）”的头字母）。常用的其他符号有：wait和signal；up和do
8、wn；sleep和wakeup等。利用信号量和P、V操作既可以解决并发进程的竞争问题，又可以解决并发进程的协作问题。 信号量的分类信号量的分类 信号量按其用途分为2种： 公用信号量：初值常常为1，用来实现进程间的互斥。相关进程均可对其执行P、V操作。 私有信号量：初值常常为可用资源数，多用来实现进程同步。拥有该信号量的一类进程可以对其执行P操作，而另一类进程可以对其执行V操作，多用于并发进程的同步。信号量按照取值可以分为两种：二元信号量： 仅允许取0和1，主要用于解决进程互斥；一般信号量（计数信号量）：允许取任意整数值，主要用于解决进程同步问题。一般信号量一般信号量 数据类型：s是结构性变量，
9、其中成员value为整型变量，系统初始化时为其赋初值；成员list为等待使用此类资源的进程队列的头指针。(1) P(s): 将s的成员value的值减一； 若结果小于0，则执行P操作的进程被阻塞，并且进入s的成员list指向的队列；否则，执行P操作的进程继续执行。 (2) V(s): 将s的成员value的值加一； 如果结果小于等于0，则执行V操作的进程从s的成员list指向的队列中唤醒一个进程（使其转变为就绪态），随后自己继续执行；如果结果大于0，则执行V操作的进程继续执行。结构型信号量和PV操作的实现：typdef struct semaphore int value; struct pc
10、b *list; void P(semaphore &s) s.value-; if(s.value0) w(s.list); void V(semaphore &s) s.value+; if(s.value=1) =1) Xi=Xi-1 ;Xi=Xi-1 ; AjAj=Xi; =Xi; V(sV(s); ); 输出一张票输出一张票； else else V(sV(s); ); 输出票已售完输出票已售完； coendcoend int intAmAm; semaphore smsemaphore sm; For(int j=0;jm;jFor(int j=0;j=1) =1) Xi=Xi-1
11、;Xi=Xi-1; Aj Aj=Xi; =Xi; V(sjV(sj); ); 输出一张票输出一张票 ； else else V(sjV(sj);); 输出票已售完输出票已售完 ； coendcoend 哲学家吃通心面问题问题 有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘于，每两人之间放一把叉子。每个哲学家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边去取叉子 哲学家吃通心面问题示意图问题示意图4001431232哲学家叉子哲学家吃通心面问问题题 semaphore fork5; semaphore fork5; for(in
12、t i;i for(int i;i5;i+) 5;i+) forki forki := 1; := 1;cobegincobeginprocess Philosopher_iprocess Philosopher_i() / i=0,1,2,3,4,() / i=0,1,2,3,4,while(truewhile(true)think()think()；P(forki)P(forki)； P(forki+1%5)P(forki+1%5)； eat()eat()；V(forki)V(forki)；V(fork(i+1)%5)V(fork(i+1)%5)； coendcoend 上述算法能够实现进
13、程的互斥（同步），但是，它可能发生死锁：如果每一个哲学家依次拿起右边（或者左边）的叉子，结果就会出现每一个人都拿到一把叉子，而都等待第二把叉子的现象。 解决死锁问题的方案：至多允许4位哲学家吃面；奇数号哲学家先拿左边的叉子，偶数号哲学家先拿右边的叉子；规定每一个哲学家都必须拿到两把叉子才能吃面，否则一把也不拿即当拿不到第二把叉子时，即放弃已拿到的第一把。注意：实现该方案需要修改信号量和PV操作的定义！ 生产者和消费者共享缓冲区 缓冲区中有空时，生产者可放入产品（不许放重），否则等待 缓冲区中有产品时，消费者可取出产品（不许取重），否则等待一个生产者、一个消费者共享一个缓冲区一个生产者、一个消费
14、者共享多个缓冲区多个生产者、多个消费者共享多个缓冲区多个生产者、多个消费者共享一个缓冲区多个生产者、一个消费者共享多个缓冲区一个生产者、多个消费者共享多个缓冲区 int B; semaphfore empty; /可以使用的空缓冲区数目 semaphore full; /缓冲区内可以使用的产品的数目 empty=1; /初始缓冲区内允许放入一件产品 full=0; /初始缓冲区内没有产品 cobegin process producer() while(true) produce(); P(empty); append() to B; V(full); coend process consum
15、er() while(true) P(full); take() from B; V(empty); 情况一： Producer: P(empty); empty=0; (进入临界区) Consumer: P(full); full=-1; (挂起) Producer: V(full); full=0; (唤醒consumer) Consumer: 临界区语句； (进入临界区)情况二： Consumer: P(full); full=-1; (挂起) Producer: P(empty); empty=0; 临界区; V(full); full=0;(唤醒消费者) Consumer: 临界区语
16、句； V(empty) ; empty= 1; Producer: . 前面的例子里生产者和消费者共享的是一个缓冲区，实际上，他们也可以共享多个缓冲区。为了实现协调，必须增加一个信号量。mutex信号量（初值1），使进程互斥地访问缓冲区 empty信号量（初值k），保证生产者不向满的缓冲区存full信号量（初值0），保证消费者不从空的缓冲区取 int Bk; semaphore empty; empty=k; semaphore full; full=0; semaphore mutex; mutex=1; int in=0; int out=0; cobegin process produc
17、er_i() while(true) produce(); P(empty); P(mutex); append() to Bin; in :=(in+1) % k; V(mutex); V(full); coend; process consumer_j () while(true) P(full); P(mutex); take() from Bout; out=(in+1) % k; V(mutex); V(empty); consume(); 情况一 (producer在临界区中， consumer加入) producer_i: P(empty);(empty=k-1) P(mutex
18、);(mutex=0) 临界区 consumer_i: P(full); (full=-1;) 挂起 producer_i: V(mutex);(mutex=1) V(full); (full=0;)(唤醒consomer_i) comsumer_i: P(mutex); (mutex=0;) 临界区； V(mutex);(mutex=1;) V(empty); (empty=k) 情况二： (consumer先启动) consumer_i: P(full); (full=-1;) 挂起 producer_i: P(empty);(empty=k-1;) P(mutex);(mutex=0)
19、临界区； V(mutex);(mutex=1) V(full);(full=0;) comsumer_i: P(mutex); (mutex=0;) 临界区； V(mutex);(mutex=1;) V(empty); (empty=k) 如果有多个P操作，必须注意它们之间的顺序一般来说，用于互斥的信号量上的P操作应该在后面。 V操作的次序无关紧要。讨论：如果在生产者进程中将P(mutex)和P(empty)交换则 若缓冲区已满 （empty=0;full=k;mutex=1;）,则 producer: P(mutex);(mutex=0) P(empty);(empty=-1;) 挂起 co
20、nsumer: P(full);(full=k-1); P(mutex);(mutex=-1); 挂起 有两组并发进程：读者和写者，共享一个文件F，要求： 允许多个读者同时执行读操作 任一写者在完成写操作之前不允许其它读者或写者工作 写者执行写操作前，应让已有的写者和读者全部退出 单纯使用信号量不能解决问题，需要引入计数器readcount对读进程计数，mutex代表对计数器操作的互斥信号量，writelock表示是否允许写的信号量。 int readcount=0; semaphore writeblock, mutex; writeblock=1; mutex=1; cobegin pro
21、cess reader_i() P(mutex); readcount+; if(readcount=1) P(writeblock); V(mutex); 读文件； P(mutex); readcount-; if(readcount=0) V(writeblock) ; V(mutex); process writer_j() P(writeblock); 写文件； V(writeblock); coend 本算法中，读者是优先的，当存在读者时，写者将被延迟，而且只要有一个读者活跃，随后的读者都被允许访问文件，从而导致写者长时间等待，并可能出现写者饥饿的现象。解决的方案：增加信号量修改程序
22、，可以得到写者具有优先权的方案，确保当一个写者进程想要访问文件时，不允许新的读者进程访问。读者写者锁：允许多名读者同时以只读方式存取有锁保护的对象；或者一位写者以写方式存取有锁保护的对象 。当一名或多名读者已经上锁后，此时形成读锁，写者将不能访问有读锁保护的对象；当锁被请求者用于写操作时，形成写锁，其他进程的读写操作必须等待。 写者优先的算法（增加一个信号量s，用于在写进程到来之后封锁后来的读进程）cobegin process reader_i() P(s); P(mutex); readcount+; if(readcount=1) P(writeblock); V(mutex); V(s
23、); 读文件； P(mutex); readcount-; if(readcount=0) V(writeblock) ; V(mutex); process writer_j() P(s); P(writeblock); 写文件； V(writeblock); V(s); coend 读者写者锁：允许多名读者同时以只读方式存取有锁保护的对象；或者一位写者以写方式存取有锁保护的对象 。当一名或多名读者已经上锁后，此时形成读锁，写者将不能访问有读锁保护的对象；当锁被请求者用于写操作时，形成写锁，其他进程的读写操作必须等待。 理发店有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子 如果没有顾
24、客，理发师便在理发椅上睡觉 当一个顾客到来时，它必须叫醒理发师 如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，他们就坐下来等待，否则就离开 int waiting0； /等候理发的顾客数 int CHAIRS=n; /为顾客准备的椅子数 semaphore customers, barbers，mutex; customers = 0; barbers= 0; mutex := 1;cobegin process barber() process barber() while(true while(true) P(cutomers P(cutomers); /); /若无顾客若无顾客,
25、 ,理发师睡眠理发师睡眠 P(mutexP(mutex); /); /进程互斥进程互斥 waiting-; /waiting-; /等候顾客数少一个等候顾客数少一个 V(barbersV(barbers); /); /理发师去为一个顾客理发理发师去为一个顾客理发 V(mutexV(mutex); /); /开放临界区开放临界区 cut-hair( ); /cut-hair( ); /正在理发正在理发 process customer_jprocess customer_j() () P(mutex P(mutex); /); /进程互斥进程互斥 if(waitingif(waitingCHAI
26、RS) /CHAIRS) /看看有没有空椅子看看有没有空椅子 waiting+; / waiting+; / 等候顾客数加等候顾客数加1 1 V(customers); / V(customers); /必要的话唤醒理发师必要的话唤醒理发师 V(mutexV(mutex); /); /退出临界区退出临界区 P(barbers); /P(barbers); /理发师忙理发师忙, , 顾客坐着等待顾客坐着等待 get_haircutget_haircut();(); else else V(mutex V(mutex); /); /人满了人满了, ,顾客离开顾客离开 coendcoend苹果桔子问
27、题 桌上有一只盘子，每次只能放入一只水果；爸爸专向盘子中放苹果(apple)，妈妈专向盘子中放桔子(orange)，一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子里的苹果 intint plate; plate;semaphore spsemaphore sp； / / 盘子里可以放几个水果盘子里可以放几个水果 semaphore sg1; / semaphore sg1; / 盘子里有桔子盘子里有桔子Semaphore sg2; / Semaphore sg2; / 盘子里有苹果盘子里有苹果sp= 1; / sp= 1; / 盘子里允许放入一个水果盘子里允许放入一个水果sg1= 0; / s
28、g1= 0; / 盘子里没有桔子盘子里没有桔子 sg2= 0; / sg2= 0; / 盘子里没有苹果盘子里没有苹果cobegincobeginprocess father() process father() while(truewhile(true) 削一个苹果削一个苹果 ； P(spP(sp);); 把苹果放入把苹果放入plateplate； V(sg2);V(sg2); process mother() process mother() while(truewhile(true) 剥一个桔子剥一个桔子 ； P(spP(sp);); 把桔子放入把桔子放入plateplate； V(sg1);V(sg1); coendcoendprocess son() process son() while(truewhile(true) ) P(sg1); P(sg1); 从从plateplate中取桔子中取桔子 ； V(spV(sp);); 吃桔子吃桔子 ； process daughter() process daughter() while(truewhile(true) ) P(sg2); P(sg2); 从从plateplate中取苹果中取苹果 ； V(spV(sp);); 吃苹果吃苹果 ；
