Race conditions and other IPC issues (CS 273 (OS), Fall 2019)

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), then
see 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; if myturn[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) and wakeup(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 variable count.

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