《著名的生产者消费者互斥问题》由会员分享，可在线阅读，更多相关《著名的生产者消费者互斥问题（25页珍藏版）》请在金锄头文库上搜索。
1、Producer/Consumer Problem A producer is generating data and placing them into a buffer A consumer is taking items out of the buffer one at time The producer and the consumer work simultaneously Only one producer or consumer may access the buffer at any moment A generic model for many practical probl
2、emsA Solution to Infinite P/C Problem/* program producer-consumer */ semaphore n = 0; /* to count goods */ semaphore s = 1; void producer() while (true)produce();wait(s);append();signal(s);signal(n); void consumer() while (true)wait(n);wait(s);take();signal(s);consume(); void main() parbegin (produc
3、er, consumer); If the order is changed to wait(s); wait(n); What might happen?P/C Problem with A Finite Bufferconsumer: while (true) while (in = out) /* empty: out-in*/* do nothing */;w = bout;out = (out + 1) % n;/* consume item w */ producer: while (true) /* produce item v */while (in + 1) % n = ou
4、t) /* full: in-out*/* do nothing */;bin = v;in = (in + 1) % n Typical Solution const int sizeofbuffer = /* buffer size */; semaphore s = 1; /* for ME */ semaphore n= 0; /* number of goods available */ semaphore e= sizeofbuffer; /* number of available places */ void producer() while (true) produce();
5、wait(e);wait(s);append();signal(s);signal(n); Block on: Unblock on: Producer: insert in full buffer Consumer: remove item Consumer: remover from empty buffer Producer: insert itemvoid consumer() while (true) wait(n);wait(s);take();signal(s);signal(e);consume(); void main() parbegin (producer, consum
6、er); Comments on Semaphores Interpretation: S0, there are still |S| processes that can execute without suspension S0, |S| processes are blocked on S The value of a semaphore can not be checked, but can only be used by Wait and Signal operations, and queuing mechanismExample - 1 ProblemGiven eight pr
7、ocesses p1, p2, , p8 with left execution constrains, design a synchronized scheduling algorithm KeyIf process B follows A in execution, then use wait(s) in B while signal(s) in A, where semaphore s is initialized with 0P1P2P3 P4P5P6P7P8SolutionSemaphore s13=0, s14=0, s15=0, s23=0, s24=0, s25=0, s36=
8、0, s48=0, s57=0, s68=0, s78=0;Void P1() while (true) /* do all work; */ signal(s13); signal(s14); signal(s15); Void P4() while (true) wait(s14); wait(s24) /* do all work; */ signal(s48); Void P5() while (true) wait(s15); wait(s25) /* do all work; */ signal(s57); Void P7() while (true) wait(s57); /*
9、do all work; */ signal(s78); Void P6() while (true) wait(s36); /* do all work; */ signal(s68); Void P8() while (true) wait(s68); wait(s48); wait(s78); /* do all work; */ Void P3() while (true) wait(s13); wait(s23) /* do all work; */ signal(s36); Void P2() while (true) /* do all work; */ signal(s23);
10、 signal(s24); signal(s25); Parbegin(P1,P2,P3, , P8); Example - 2 ProblemA lair with infinite space, can be used to shield cows and bulls. Design a lairage process meets following constrains: Put one cow or bull into the lair once - N Number of Cow Number of Bull M Key Set up a semaphore mutex for th
11、e purpose of ME Split the inequality into two pieces Formulate the problem as a producer/consumer problem with special initial valuesSolutionSemaphore mutex=1, scow=m-1, sbull=n-1; void pcow() while (true) /* get a cattle */if (cattle = cow) wait(scow);wait(mutex);/* lairage the cow */signal(sbull);
12、signal(mutex); void pbull() while (true) /* get a cattle */if (cattle = bull) wait(sbull);wait(mutex);/* lairage the bull */signal(scow);signal(mutex); parbegin(pcow, pbull);Beginning with a coherent statusMaintain the coherence in the rest procedureQuiz (in 15 mins) An enterprise uses the following
13、 working procedure All paper documents can only be issued by the CEO office A paper document becomes valid only signed by two key officers, say CIO, and CTO The order of signing does make no sense The CEO office can issue a new document once all previous document have been signed Try to simulate the
14、 procedure by using semaphoreKey to the Quiz Try to formulate the problem into a classical one, e.g. the P/C problem Try to sketch the relationship among office, CIO and CTO The phrase paper document implies that the document should be read in the manner of ME Programming, straight forward OfficeCIO
15、CTOA Referential SolutionSemaphore Mutex=1; Semaphore S=2; Semaphore S1=0, S2=0; main () parbegin(office, CIO, CTO); office() while (TRUE) wait(S);wait(S);wait(Mutex);/* print document */signal(Mutex) ;signal(S1) ;signal(S2) ; CIO() while (TRUE) wait(S1);wait(Mutex);/* sign the document */signal(Mutex) ;signal(S) ; CTO() while (TRUE) wait(S2);wait(Mutex);/* sign the document */signal(Mutex) ;signal(S) ; Review the Solution to Infinite P/C Problem/* program producer-consumer */ semaphore n = 0; /* to count goods */ semaphore s = 1; void producer() while (true)produce();wa
