Coupon Accepted Successfully!


Concurrency, Synchronization & Deadlock

Principles and Problems in Concurrency

Concurrency is the interleaving of processes in time to give the appearance of simultaneous execution.

A Simple Example

The fundamental problem in concurrency is processes interfering with each other while accessing a shared global resource. This can be illustrated with a surprisingly simple example:

chin = getchar();

chout = chin;


Imagine two processes P1 and P2 both executing this code at the “same” time,

with the following interleaving due to multi-programming.

  1. P1 enters this code, but is interrupted after reading the character x into chin.
  2. P2 enters this code, and runs it to completion, reading and displaying the character y.
  3. P1 is resumed, but chin now contains the character y, so P1 displays the wrong character.

The essence of the problem is the shared global variable chin. P1 sets chin, but this write is subsequently lost during the execution of P2. The general 2 solution is to allow only one process at a time to enter the code that accesses chin: such code is often called a critical section. When one process is inside a critical section of code, other processes must be prevented from entering that section. This requirement is known as mutual exclusion.

Mutual Exclusion

Mutual exclusion is in many ways the fundamental issue in concurrency. It is the requirement that when a process P is accessing a shared resource R, no other process should be able to access R until P has finished with R.

There are essentially three approaches to implementing mutual exclusion.

  • Leave the responsibility with the processes themselves: this is the basis of most software approaches.
  • Allow access to shared resources only through special-purpose machine instructions:
  • Provide support through the operating system, or through the programming language.


The fundamental idea of semaphores is that processes “communicate” via global counters that are initialised to a positive integer and that can be accessed only through two atomic operations:

semSignal(x) increments the value of the semaphore x.

semWait(x) tests the value of the semaphore x: if x > 0, the process decrements x and continues; if x = 0, the process is blocked until some other process performs a semSignal.


Deadlock is defined as the permanent blocking of a set of processes that either compete for global resources or communicate with each other. It occurs when each process in the set is blocked awaiting an event that can be triggered only by another blocked process in the set.

Consider Figure , in which both processes P and Q need both resources A and B simultaneously to be able to proceed.

Thus P has the form get A, ... get B, ..., release A, ..., release B, and Q has the form get B, ... get A, ..., release B, ..., release A.


The six paths depicted in above correspond to the following.

  1. Q acquires both resources, then releases them. P can operate freely later.
  2. Q acquires both resources, then P requests A. P is blocked until the resources are released, but can then operate freely.
  3. Q acquires B, then P acquires A, then each requests the other resource. Deadlock is now inevitable.
  4. P acquires A, then Q acquires B, then each requests the other resource. Deadlock is now inevitable.
  5. P acquires both resources, then Q requests B. Q is blocked until the resources are released, but can then operate freely.
  6. P acquires both resources, then releases them. Q can operate freely later.

Contrast the above example with the situation where P does not need the resources simultaneously: P has the form get A, ... release A, ..., get B, ..., release B, and Q is defined as before.


Example of No Deadlock

Again the six paths show the possible execution sequences.

Conditions for Deadlock

Three policy conditions are necessary for deadlock to be possible.

  1. Mutual exclusion : Only one process may use a resource at one time.
  2. Hold and wait: A process may hold some resources while waiting for others.
  3. No preemption: No process can be forced to release a resource.
  4. Circular wait: A closed chain of processes exists, such that each process is blocked waiting for a resource held by another process in the set.

Three approaches exist for dealing with deadlock:

  1. Prevention involves adopting a static policy that disallows one of the four conditions above.
  2. Avoidance involves making dynamic choices that guarantee prevention.
  3. Detection and recovery involves recognising when deadlock has occurred, and trying to recover.

Deadlock Prevention

We can prevent deadlock from occurring by adopting either an indirect policy that disallows one of the three necessary conditions, or a direct policy that disallows sets of processes that can exhibit a circular wait.

Deadlock Avoidance

Deadlock avoidance Simplest algorithm - each process tells max number of resources it will ever need. As process runs, it requests resources but never exceeds max number of resources. System schedules processes and allocates resoures in a way that ensures that no deadlock results.

Test Your Skills Now!
Take a Quiz now
Reviewer Name