Principle of Mutual Exclusion

28 Mar 2011 by

Mutual Exclusion is a process that prevents multiple threads or processes from accessing shared resources at the same time. The problem is coming from the fact that in both distributed systems and single system, several threads or processes share a resource but cannot use it concurrently. Mutual Exclusion, Synchronization and Data Coordination are commonly use interchangeably; or just MUTEX for short.

Rationale

This will guide you to the root of the problem and give you solution.

Let see the two blocks of code that runs in parallel called foo() and bar().

The initial state: x=6 and y=0.

FooThread

void foo()
{
   x++;
   y = x;
}

BarThread

void bar()
{
   y++;
   x += 3;
}

After running these 2 threads in parallel, we cannot predict the final value of x and y. There are many possibilities of x and y.

  • x=10 and y=8 if foo() runs first and is completed before bar() is actually started
  • x=10 and y=10 if bar() runs first and is completed before foo() is actually started
  • x=10 and y=7 if the flow of execution is x++; y++; y=x; and x+=3;
  • etc.

Problem

This problem is caused by many threads or processes race each other to win to access a resource. It is called Race Condition.

The block of codes of shared resources is called Critical Section.

“A critical section is a piece of code in which processes or threads access a common resource”, — wikipedia

Solution

To achieve mutual exclusion, there are techniques separately in single system and distributed system.

In single system, mutual exclusion can be achieved by using:

In distributed systems, mutual exclusion can be achieved by using some algorithms:

We will discuss more about individual system in a later post. Stay tune.

 

2 responses so far

Leave a Reply