最新IPC经典问题.doc

《最新IPC经典问题.doc》由会员分享，可在线阅读，更多相关《最新IPC经典问题.doc（15页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、精品资料IPC经典问题.IPC经典问题读者写者问题读者优先：semaphore mutex=1;/控制对rc的访问semaphore db=1;/控制对数据库的访问int rc=1;/正在读或想要读的进程数void reader(void) while(1) down(&mutex); rc+; if(rc=1) down(&db); up(&mutex); read_database(); down(&mutex); rc-; if(rc=0) up(&db); up(&mutex); use_data_read(); void writer(void) while(1) think_up_

2、data(); down(&db); write_database(); up(&db); 写者优先，条件为：（1）多个读者可以同时进行读；（2）写者必须互斥（只允许一个写者写，同时也不能读者、写者同时进行）；（3）写者优先于读者（一旦有写者来，则后续读者必须等待，唤醒时优先考虑写者）。注意唤醒时优先考虑写者这个条件semaphore read=1;/用于阻塞读者semaphore rmutex=1,wmutex=1;/用于控制对rcount和wcount的访问semaphore db=1;/控制对数据库的访问int rcount=wcount=0;void reader(void) p(re

3、ad); /只要有写者等待，读者就会阻塞 p(rmutex); rcount+; if(rcount=1) p(db); v(rmutex); v(read);/及时释放，多个读者可以同时读 read_database(); p(rmutex); rcount-; if(rcount=0) v(db); v(rmutex);void writer(void) p(wmutex); wcount+; if(wcount=1) p(read); v(wmutex); p(db); write_database(); v(db); p(wmutex); wcount-; if(wcount=0) v

4、(read); v(wmutex);如果唤醒时读写队列平等的话semaphore write=1;/用于阻塞写者semaphore mutex=1;/用于控制对rc的访问semaphore db=1;/控制对数据库的访问int rc=0;void reader(void) p(db); p(mutex); rc+; if(rc=1) p(write); /有读者进入，互斥写操作 v(mutex); v(db); / 及时释放读写互斥信号量，允许其它读、写进程申请资源 read_database(); p(mutex); rc-; if(rc=0) v(write); /所有读者退出，允许写操作

5、 v(mutex);void writer(void) p(db);/ 互斥后续其它读者、写者 p(write);/如有读者正在读，等待所有读者读完 write_database(); v(write);/允许后续新的第一个读者进入后互斥写操作 v(db);/允许后续新读者及其它写者 哲学家就餐问题思路：如果一个哲学家旁边两个都不在进餐时拿起叉子是安全的。注意状态的变化应该处于临界区，如果一个哲学家不能拿起叉子时应阻塞，同时加入一个状态表明他饥饿，旁边的哲学家就餐完毕会通知他#define N 5#define LEFT (i-1)%N#define RIGHT (i+1)%N#define

6、THINKING 0#define HUNGRY 1#define EATING 2int stateN;/记录每个人状态的数组semaphore mutex=1;/临界区互斥semaphore sN=0;/每个哲学家一个信号量,表示能否得到两只叉子void philosopher(int i) while(1) think(); take_forks(i); eat(); put_forks(i); void take_forks(int i) donw(&mutex); statei=HUNGRY; test(i);/试图得到两只叉子 up(&mutex); down(&si);/如果得不

7、到叉子就阻塞void put_forks(int i) down(&mutex); statai=THINKING; test(LEFT);/看下左邻居现在是否能进餐 test(RIGHT);/看下右邻居现在是否能进餐 up(&mutex);void test(int i) if(statei=HUNGRY & stateLEFT!=EATING & stateRIGHT!=EATING) statei=EATING; up(&si); 红黑客过河有红客和黑客两组人员需要过河。河上有船，但是每次只能乘坐4人，且每次乘客满员时才能开船，到河对岸后空船返回。但船上乘客不能同时有3个红客 、1个黑客

8、 或者 1个红客 、 3个黑客的组合。（其他组合安全）。请编写程序，用PV操作解决红客、黑客过河的问题。对同步与互斥的分析：同步关系：1. 满员才能开船；2. 红黑客满足一定的组合规则,才能有四人上船互斥关系：红黑客对请求上船的控制显然，此题难点在对同步关系的解决。下面给出所写程序的算法思想： Red():每个红客到来请求上船时执行该程序： 1.请求进入临界区； 2.首先检查本人的到来是否满足上船的组合(即4个红客或2个红客与2个黑客); 3.如果满足2个红客和2和黑客的组合，则看是否有船可上，有的话该红客上船并通知另外1个红客和2个黑客上船，然后通知船满员，并退出临界区； 4.如果满足4个红

9、客的组合，则看是否有船可上，有的话该红客上船并通知另外3个红客上船，然后通知船满员，并退出临界区； 5.不符合上船的组合，则先退出临界区，然后在信号量S_red上等待，直到当条件满足时，有人通知其上船。 6.完毕。 Black():每个黑客到来请求上船时执行该程序,其算法与Red()完全一致； Boat():河上的船执行该程序：1.等待满员后开船过河； 2.空船返回，通知可以上船了，转而执行1。 / semapore boats=1; /河上船只的数量 semapore full=0; /船的满员状态 semapore S_red=0; /控制红客上船 semapore S_black=0;

10、/控制黑客上船 semapore mutex=1; /由于互斥 int reds=0; /等待上船的红客数 int blacks=0; /等待上船的黑客数 Red() P(mutex);/进入临界区 reds+; /等待上船的红客数加1 if(reds =2 & blacks =2) /2个红客和黑客的组合 P(boats); /准备上船，无船则等待 take_boat();/该红客上船 reds=reds-2;/等待上船的红客数减2 V(S_red); /通知另一个红客上船 blacks=blacks-2;/等待上船的黑客数减2 /通知其他两黑客上船 V(S_black); V(S_blac

11、k); V(full);/通知船满员 V(mutex);/退出临界区 else if(reds=4) /4个红客的组合 P(boats); /准备上船，无船则等待 take_boat(); /该红客上船 /递减等待上船的红客数，通知其他3个红客上船 while(-reds) V(S_red); V(full);/通知船满员 V(mutex);/退出临界区 else V(mutex)；/退出临界区，此步必在P(S_red)之前，不然会产生死锁 /该红客等待直至条件满足时上船 P(S_red); take_boat(); Black() P(mutex); blacks+; if(blacks =

12、2 & reds =2) P(boats); take_boat()； blacks=blacks-2; V(S_black); reds=reds-2; V(S_red); V(S_red); V(full); V(mutex); else if(blacks=4) P(boats); take_boat()； while(-blacks) V(S_black); V(full); V(mutex); else V(mutex); P(S_black); take_boat(); Boat() while(TRUE) P(full); /等待满员 shove_off(); /开船过河 boat_return();/空船返回 V(boats); /通知可以上船了 该算法存在一个问题是如果2红1黑时接下来来的都是红客时，会造成饥饿现象。改进：利用5人中必有4人满足开船条件，每5个人检查一下让其中4个人过河，红黑客算法也不用分开写了。转载于：