5.25. The following pseudocode is a correct implementation of the producer/consumer prob- lem with a bounded buffer item [3] buffer; // initially empty semaphore empty: /1 initialized to +3 semaphore full: 1/ initialized to 0 binary_semaphore mutex; // initialized to 1 void producer () void consumer ) while (true while (true item produce ) wait (empty) wait (mutex) append (item) signal (mutex) signal (full) wait (fu11) wait (mutex) item take signal (mutex) signal (empty) consume (item) Scheduled Step of full's State and empty' s State Execution Buffer executes pl empty em em empty empty Pa executes pl Pa executeS Pb executes Pb executes Pc executes pl Cb executes-. Pc executes Cb executes Pa executes full Labels p1, p2, p3 and cl, c2, c3 refer to the lines of code shown above (p2 and c2 each cover three lines of code). Semaphores empty and full are linear semaphores that can take unbounded negative and positive values. There are multiple producer processes, referred to as Pa, Pb, Pc, etc., and multiple consumer processes, referred to as Ca, Cb, Cc, etc. Each semaphore maintains a FIFO (first-in-first-out) queue of blocked pro- cesses. In the scheduling chart below, each line represents the state of the buffer and semaphores after the scheduled execution has occurred. To simplify, we assume that scheduling is such that processes are never interrupted while executing a given portion of code pl, or p2,, or c3. mpty em em em emm ul full- mpty empty em empty empty empty Scheduled Step of full's State and empty' s State Pb executes pl-p3 full Execution Initialization Ca executes c1 Cb executes c1 | full--2 (Ca, Cb) | 000 and Queue em em em Buffer Pc executes Pa executes pl Pd executes p1 full=-1 (Ca) full Ca executes cl-c3 Pa executes pll2 (Ca, Pa executeS Pa executes p2 full2 (Ca, Cb X o0 Pa executes p3 | full=-1 (Cb) Ca | XOO Ca executes c2 Ca executes c3 Cc executes cl-c2 empty- Pa executes em full (Cb) full=-1 (Cb) Cc executes c3 em em Pd executes p2-p3 mpty 5.25. The following pseudocode is a correct implementation of the producer/consumer prob- lem with a bounded buffer item [3] buffer; // initially empty semaphore empty: /1 initialized to +3 semaphore full: 1/ initialized to 0 binary_semaphore mutex; // initialized to 1 void producer () void consumer ) while (true while (true item produce ) wait (empty) wait (mutex) append (item) signal (mutex) signal (full) wait (fu11) wait (mutex) item take signal (mutex) signal (empty) consume (item) Scheduled Step of full's State and empty' s State Execution Buffer executes pl empty em em empty empty Pa executes pl Pa executeS Pb executes Pb executes Pc executes pl Cb executes-. Pc executes Cb executes Pa executes full Labels p1, p2, p3 and cl, c2, c3 refer to the lines of code shown above (p2 and c2 each cover three lines of code). Semaphores empty and full are linear semaphores that can take unbounded negative and positive values. There are multiple producer processes, referred to as Pa, Pb, Pc, etc., and multiple consumer processes, referred to as Ca, Cb, Cc, etc. Each semaphore maintains a FIFO (first-in-first-out) queue of blocked pro- cesses. In the scheduling chart below, each line represents the state of the buffer and semaphores after the scheduled execution has occurred. To simplify, we assume that scheduling is such that processes are never interrupted while executing a given portion of code pl, or p2,, or c3. mpty em em em emm ul full- mpty empty em empty empty empty Scheduled Step of full's State and empty' s State Pb executes pl-p3 full Execution Initialization Ca executes c1 Cb executes c1 | full--2 (Ca, Cb) | 000 and Queue em em em Buffer Pc executes Pa executes pl Pd executes p1 full=-1 (Ca) full Ca executes cl-c3 Pa executes pll2 (Ca, Pa executeS Pa executes p2 full2 (Ca, Cb X o0 Pa executes p3 | full=-1 (Cb) Ca | XOO Ca executes c2 Ca executes c3 Cc executes cl-c2 empty- Pa executes em full (Cb) full=-1 (Cb) Cc executes c3 em em Pd executes p2-p3 mpty
