The new scheme is illustrated by the following:

The Critical-Section Problem

A solution to the critical-section problem must satisfy the following three requirements:
  1. Mutual Exclusion. If process Pi is executing in its critical section, then no other processes can be executing in their critical sections.
  2. Progress. If no process is executing in its critical section and there are some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely.
  3. Bounded Waiting. A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted.
Initial attempts to solve the problem.

Algorithm 1

Algorithm 2

Algorithm 3

Bakery Algorithm - Critical section for n processes

Bakery Algorithm

Synchronization Hardware

Semaphore - synchronization tool that does not require busy waiting.

Semaphore S

Example: critical section for n processes Implementation of the wait and signal operations so that they must execute atomically. Implementation of wait(S) operation with the TestandSet instruction: Race condition exists!

Better Code for wait(S)

  while (TestandSet(lock1)); 
  while (TestandSet(lock)); 
  S = S - 1;
  if (S < 0) {
      lock = false; 
  } else
      lock = false;
 lock1 = false; 
lock1 serialises the waits.

Semaphore can be used as general synchronization tool:

Two types of semaphores:

Classical Problems of Synchronization

Bounded-Buffer Problem

Readers-Writers Problem

A number of processes, some reading data, some writing. Any number of processes can read at the same time, but if a writer is writing then no other process must be able to access the data.

Dining-Philosophers Problem

A Problem posed by Dijkstra in 1965

Possible solution to the problem:

"take_fork" waits until the specified fork is available and then grabs it.

Unfortunately this solution will not work... what happens if all the philosophers grab their left fork at the same time.

Better solution.

High-level synchronization constructs


High-level synchronization construct that allows the safe sharing of an abstract data type among concurrent processes. (Hoare and Brinch Hansen 1974)
A collection of procedures, variables and data structures. Only one process can be active in a monitor at any instant. The producer consumer problem can be solved as follows using monitors: The dining philosophers problem can also be solved easily. There are very few languages that support constructs such as monitors... expect this to change. One language that does is Java. Here is a Java class that can be used to solve the producer consumer problem.

Monitor implementation using semaphores.

What happens when a monitor signals a condition variable?
A process waiting on the variable can't be active at the same time as the signaling process, therefore: 2 choices.
  1. Signaling process waits until the waiting process either leaves the monitor or waits for another condition.
  2. Waiting process waits until the signaling process either leaves the monitor or waits for another condition.

Atomic Transactions

Log-Based Recovery

Checkpoints - reduce recovery overhead

  1. Output all log records currently residing in volatile storage onto stable storage.
  2. Output all modified data residing in volatile storage to stable storage.
  3. Output log record <checkpoint> onto stable storage.

Concurrent Atomic Transactions