Race conditions and other IPC issues
CS 273 (OS), Fall 2019
Note: If you have already seen these concepts or examples in other courses, then
recall how you solved these problems in your prior class (e.g., Java
synchronized
, or MPI communication with a synchronization process, or semaphores in an operating system), thensee if you can come up with a solution to these problems in the context of this class (e.g., how can you program a solution in C/C++, or without MPI messages, etc.).
Dining Philosopher's Problem
E. Dijkstra, 1965
- Example: N processes sharing N resources in a circular arrangement. Each process has two states (computing, interacting with resources); each needs exclusive access to its two resources while interacting with them.
- Dijkstra's statement: N philosophers sit down together to eat spaghetti. Each philosopher spends his/her time alternately thinking then eating. In order to eat, a philosopher needs two forks; each fork is shared with exactly one other of the philosophers. What procedure will allow all the philosophers to continue to think and eat?
- Algorithm 1. Each philosopher does the following:
repeat forever think pick up left fork (as soon as it's available) pick up right fork (as soon as it's available) eat return left fork return right fork
Issue: Risk of Deadlock
- Algorithm 2. Each philosopher does the following:
repeat forever think repeat pick up left fork (as soon as it's available) if right fork is available pick up right fork else return left fork until both forks are possessed eat return left fork return right fork
Issue: Risk of Starvation
- Algorithm 3. The philosophers share a boolean array
myturn
of length N; ifmyturn[p]
is true then it is (hopefully) safe for philosopher p to eat. (We use an array rather than a single variable location to allow for concurrency.)We assume that there are functions
sleep()
for causing a philosopher to doze (blocked process) andwakeup(p)
for waking up a philosopher p.Each philosopher does the following:
if (p == 1) myturn[p] = true else myturn[p] = false next = (p+1) % N prev = (p+N-1) % N repeat forever think if (!myturn[p]) sleep() /* to be awakened by prev philosopher */ pick up left fork pick up right fork eat return left fork return right fork myturn[p] = false myturn[next] = true wakeup(next)
Issues: Less than maximal concurrency; race conditions
Producer/Consumer Problem
- One process produces things that another process uses.
Examples: print jobs, shell pipeline, values from a sensor.
Produced items are stored in an array of length
MAX
that is shared by the two processes. The number of items in that array is stored in a shared variablecount
. - Algorithm 1. Producer algorithm:
repeat forever produce an item if (count == MAX) sleep() /* to be awakened by consumer when space is available */ insert an item count = count + 1 if (count == 1) wakeup(consumer)
Consumer algorithm:
repeat forever if (count == 0) sleep() /* to be awakened by producer when an item is available */ remove an item count = count - 1 if (count == MAX-1) wakeup(producer) consume that item
Issues: Race conditions
Additional races if multiple producers and/or multiple consumers