26 The Critical-Section Problem

• Concurrent access to shared data may result in data inconsistency.
• Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes.

Problem

Finite buffer shared by producer and consumer

• Producer produces a stream of items and puts them into buffer,
• Consumer takes out stream of items.
  Have to deal with producers waiting for consumers when buffer is full, and consumers waiting for producers when buffer is empty.

Producer

while (true) {
	/* produce an item and put in nextProduced */
	while (count == BUFFER_SIZE); // wait if buffer full
	buffer [in] = nextProduced; // store new item
	in = (in + 1) % BUFFER_SIZE; // increment IN pointer.
	count++; // Increment counter
}

Consumer

while (true) {
	while (count == 0) ; // do nothing
	nextConsumed = buffer[out];
	out = (out + 1) % BUFFER_SIZE;
	count--;
	/* consume the item in nextConsumed */
}

Race Condition

There is something wrong with this code!

• count++ could be compiled as a sequence of CPU instructions :
  • register = count
  • register = register1+1
  • count = register1
• count-- could be compiled likewise:
  • register2 = count
  • register2 = register2-1
  • count = register2
• Consider that the producer and consumer execute the count++ and count-- around the same time, such that the CPU instructions are interleaved as follows (with count=5 initially) :

$$\begin{array}{rl}\text{Prod.}:& {\text{register}}_1=\text{count}\{{\text{register}}_1\to 5\}\\ \text{Prod.}:& {\text{register}}_1={\text{register}}_1+1\{{\text{register}}_1\to 6\}\\ \text{Cons.}:& {\text{register}}_2=\text{count}\{{\text{register}}_2\to 5\}\\ \text{Cons.}:& {\text{register}}_2={\text{register}}_2-1\{{\text{register}}_2\to 4\}\\ \text{Prod.}:& \text{count}={\text{register}}_1\{\text{count}\to 6\}\\ \text{Cons.}:& \text{count}={\text{register}}_2\{\text{count}\to 4\}\end{array}$$

• With an increment and a decrement, in whatever order, we would expect no change to the original value (5), but here we have ended up with 4 ?!?!

A race condition occurs when a system’s behaviour is dependent on the sequence or timing of other uncontrollable events, leading to unexpected or inconsistent results.