Synchronization

Sharing data between processes requires synchronization to avoid e.g. race conditions. Standard example is the producer-consumer program with shared memory (see Process communication).

A race condition occurs when more than one process reads/writes shared data in a way such that the correctness of the computation depends on the order of execution.

The producer-consumer problem is an instance of the critical-section problem:

• n processes share data
• each process has a critical section where the shared data is updated
• problem: make sure that only one process at a time is in the critical section

Process structure:

repeat
  [entry section]      - ask for permission to enter CS
    [Critical Section]
  [exit section]       - clean up, let others know this proc. exited CS
  [remainder section]  - non-critical code

Requirements on a solution of the CS problem:

1. Mutual exclusion: if process Pi is in its CS, no other processes can be in their CS
2. Progress: if no process is in its CS, and some processes want to enter their CS, only those processes which are not in their remainder section can influence the decision on which process will enter its CS next. This decision can not be postponed indefinitely
3. Bounded waiting: when one process has requested to enter its CS, there is a limit on the number of times other processes can enter their CS before the request is granted.

1 is the foundation. 2 makes sure, e.g., that a solution is not to simply alternate/take turns. 3 makes sure, e.g., that a solution is not to allow only one process.

Assumptions for solutions:

1. No process is stopped
2. No assumptions on the relative speed of processes

1. Peterson's Solution

Relatively simple solutions exist for the case of exactly 2 processes. Classic algorithm: Peterson's Solution, which requires load/store/test instructions to be atomic.

Notation: j = 1-i (i.e. Pi and Pj "the process" and "the other process")

shared bool flag[2], int turn;

repeat
  flag[i] = TRUE;          - process i wants to enter CS
  turn = j;                - allow the other to run
  while (flag[j] == TRUE and turn == j)
      do nothing;          - wait for the other process to finish
  [Critical Section]
  flag[i] = FALSE;         - we're not interested anymore
  [remainder section]

• With only turn, the processes will take turns, breaking Progress requirement.
• With only flag, the algorithm may lock up (if flag[i] == flag[j] == TRUE.
• The combination breaks the lock and the strict alternation

Exercise: understand the proof in the book.

2. Hardware-supported solutions

Easiest way: use a "sledgehammer" - disable interrupts, preventing preemption.

Works in single-CPU systems with non-preemptive kernel: while in kernel/supervisor mode (executing system calls), no preemption is done. However, preemptive kernels are better for real-time programming, and may be more responsive.

Disabling interrupts on multiprocessors is time consuming (all processors must effectively synchronise!). In general also "overkill" and only useful for very short pieces of code.

Standard solution: provide special atomic instructions for supporting CS problem solution, which cannot be interrupted.

1. Test-and-Set(x) sets x to TRUE and returns the previous value, atomically
2. Swap(x,y) swaps the contents of x and y, atomically

Example use:

shared lock = FALSE;

repeat
  while (Test-and-Set(lock))   - lock it
      do nothing;              - already locked
  [Critical Section]
  lock = FALSE;                - unlock
  [remainder section]

Doesn't satisfy Bounded Waiting - slightly more complex version does (fig 6.8).

Above solutions use busy waiting (tight loops testing the lock/flags etc), which is wasteful since it keeps the process in the RQ although it "should" be waiting.

3. Semaphores

Semaphores (invented by Edsger W. Dijkstra) provide a general and easy-to-use solution. Typically implemented by the operating system, avoiding busy waiting.

Structure:

• integer variable S (protected)
• initialisation operation (setting S)
• two operations
  1. wait (or P, proberen (test in Dutch))
  2. signal (or V, verhogen (increment in Dutch))

Value of S is "the number of wait operations that can be done without blocking".

Simple example implementation of operations:

wait(semaphore S)
{
  while (S <= 0) do nothing;  - test is ATOMIC
  S--;                        - ATOMIC
}
signal(semaphore S)
{
  S++;                        - ATOMIC
}

"Real" implementations later.

repeat
  wait(mutex);
  [Critical Section]
  signal(mutex);
  [remainder section]

P1: S1;
    signal(synch);

P2: wait(synch);
    S2;

int in = 0;
while (<more data produced>)
  wait(empty);                   - wait for an empty slot  
  wait(mutex);			 - lock the buffer
  buf[in] = next data;
  in = (in + 1) mod N;
  signal(mutex);		 - unlock buffer
  signal(full);			 - one more occupied

int out = 0;
do
  wait(full);                    - wait for an occupied slot
  wait(mutex);			 - lock buffer
  next data = buf[out]
  out = (out + 1) mod N;
  signal(mutex);		 - unlock buffer
  signal(empty);		 - one more free
  <consume data>

wait(semaphore S)       - ATOMIC
{
  S--;
  if (S < 0) {
    add process to S->list;   - end of atomic
    block(process);  - move process to semaphore waiting list
  }
}
signal(semaphore S)     - ATOMIC
{
  S++;
  if (S <= 0) {
    pick a process from S->list;  - end of atomic
    wakeup(process);  - move it to ready list
  }
}

P1:                P2:
  wait(S)            wait(Q)
  wait(Q)            wait(S)
  ...                ....
  signal(Q)          signal(Q)
  signal(S)          signal(S)

4. Monitors

Abstract data type/class which ensures only one process at a time is executing a method, and in addition different but similar wait/signal operations.