1.5 Synchronization, cpu scheduling  (Page 4/10)

Both of the shortcomings can be overcome by not restricting ourselves to a binary variable, but instead define a generalized or counting semaphore.

• A counting semaphore S takes on non-negative integer values
• Two operations are supported
• P(S) is
• while (S=0) {}
• S--

where finding S>0 and decrementing S is atomic

• That is, wait until the gate is open (positive), then run through and atomically close the gate one unit
• Another way to describe this atomicity is to say that it is not possible for the decrement to occur when S=0 and it is also not possible for twoprocesses executing P(S) simultaneously to both see the same necessarily (positive) value of S unless a V(S) is also simultaneous.
• V(S) is simply S++

These counting semaphores can solve what I call the semi-critical-section problem, where you premit up to k processes in thesection. When k=1 we have the original critical-section problem.

initially S=k

loop forever

P(S)

SCS<== semi-critical-section

V(S)

NCS

Producer-consumer problem

• Two classes of processes
  • Producers, which produce times and insert them into a buffer.
  • Consumers, which remove items and consume them.
• What if the producer encounters a full buffer?Answer: It waits for the buffer to become non-full.
• What if the consumer encounters an empty buffer?Answer: It waits for the buffer to become non-empty.
• Also called the bounded buffer problem.
  • Another example of active entities being replaced by a data structure when viewed at a lower level (Finkel's levelprinciple).

Initially e=k, f=0 (counting semaphore); b=open (binary semaphore)

Producer Consumer

loop forever loop forever

produce-item P(f)

P(e) P(b); take item from buf; V(b)

P(b); add item to buf; V(b) V(e)

V(f) consume-item

• k is the size of the buffer
• e represents the number of empty buffer slots
• f represents the number of full buffer slots
• We assume the buffer itself is only serially accessible. That is, only one operation at a time.
  • This explains the P(b) V(b) around buffer operations
  • I use; and put three statements on one line to suggest that a buffer insertion or removal isviewed as one atomic operation.
  • Of course this writing style is only a convention, the enforcement of atomicity is done by the P/V.
• The P(e), V(f) motif is used to force “bounded alternation”. If k=1 it gives strict alternation.

Semaphore implementation

Unfortunately, it is rare to find hardware that implements P&V directly (or messages, or monitors). They all involve some sort of scheduling and it is not clear that scheduling stuff belongs in hardware(layering). Thus semaphores must be built up in software using some lower-level synchronization primitive provided by hardware.

Need a simple way of doing mutual exclusion in order to implement P's and V's. We could use atomic reads and writes, as in "too muchmilk" problem, but these are very clumsy.

Uniprocessor solution: Disable interrupts.