The following pseudocode is a correct implementation of the producer/consumer problem with a bounded buffer:

Labels p1, p2, p3 and c1, 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 processes. 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 p1, or p2, …, or c3. Your task is to complete the following chart.

Transcribed Image Text:

item [3] buffer; // initially empty semaphore empty; // initialized to +3 semaphore full // initialized to o binary_semaphore mutex; // initialized to 1 void producer () void consumer () while (true) ( while (true ( item-producecl: wait (empty); wait (mutex); append (item); signal (mutex); signal (full) wait (full); wait (mutex) item = take ( ) ; signal (mutex); signal (empty) consume (item) pl: C2: p2: c3: empty's State and Queue empty+3 empty-+3 empty- +3 empty = +2 empty = +2 empty- +2 empty = +2 empty- +3 Scheduled Step of Execution full's State and Queue full 0 full =-1 (Ca) full-2 (Ca, Cb Buffer Initialization Ca executes cl Cb executes cl Pa executes pl Pa executes p2 Pa executes p3 Ca executes c2 Ca executes c3 Pb executes pl Pa executes pl Pa executes Pb executes Pb executes Pc executes pl Cb executes Pc executes Cb executes Pa executes full--2 (Ca, Cb) full =-2 (Ca, Cb) | full =-1 (Cb) Ca | OOo X OO X 00 full -1 (Cb) full1 (Cb) full = full- full = full = full- full- full- full = full- full = full = full- full full- full - full - full = full- full = full = empty empty- empty- empty = empty- empty- empty- empty- empty empty = empty = empty empty- empty empty empty empty empty empty - empty- Pb executes pl-p3 Pc executes Pa executes pl Pd executes pl Ca executes cl-c3 Pa executes Cc executes c1-c2 Pa executes Cc executes c3 Pd executes p2-p3