Unit 3: Synchronization and deadlocks

Inter-process communication (IPC) lets processes exchange data. The two models are shared memory (fast, needs synchronisation) and message passing (send/receive; easier across computers). A race condition occurs when two processes access shared data at the same time and the result depends on the order in which they run.

A critical section is the part of a program that accesses shared data. A solution must satisfy three requirements:

• Mutual exclusion: only one process in its critical section at a time.
• Progress: if no process is in the critical section, one that wants to enter must be allowed to without indefinite delay.
• Bounded waiting: a limit on how many times others can enter before a waiting process gets its turn.

A semaphore S is an integer variable accessed only through two atomic operations:

• wait(S) (P): while S ≤ 0 wait; then S = S − 1.
• signal(S) (V): S = S + 1.

A binary semaphore (0 or 1, also called a mutex) gives mutual exclusion; a counting semaphore controls access to a resource with several instances.

wait(mutex);
    /* critical section */
signal(mutex);
    /* remainder section */

A monitor is a high-level construct in which shared data and the procedures that use it are grouped together, and only one process can be active inside the monitor at a time. Condition variables (wait and signal) handle waiting inside it.

A deadlock is a situation in which a set of processes are blocked forever, each waiting for a resource held by another.

A resource allocation graph shows processes and resources; a cycle indicates a possible deadlock (a certain deadlock if each resource has one instance).

• Prevention: make sure at least one of the four conditions can never hold (for example, request all resources at once, or number resources and request them in order).
• Avoidance: check each request and grant it only if the system stays in a safe state. The Banker's algorithm does this.
• Detection and recovery: allow deadlock, detect it periodically, then recover by terminating processes or preempting resources.