digitalLockIn this special post, I’ll be tackling the concept of Mutexes and semaphores. However, this issue comes within the context of concurrent programming, thus, I will start by few key definitions which going to accompany us throughout the post.

Definitions

  1. Concurrency: simultaneously executing several processes which can interact with each other. They could also be sharing the same resource(i.e. memory).
  2. A race condition is a situation where two or more control threads are working with the same memory elements, and simultaneously decide to write different values in the same place. Without any priority scheme, lock or other control mechanism, the persisting value of the memory location will be the one that was written last.

Thus, the scheduling algorithm plays the major role in deciding what the final value would be.

Some properties of a process:

  • Safety: describe something which is always true
  • Liveness: something that eventually happens

Those properties should be valid every time the process is executed.

Example:

int J = 0; //global
while(I < 5) {
    Print 1;
}
J = 1;
while(J = 0) print 2

What can we say about the example above? Well, few facts:

  1. Only 1 or 2 would be printed – the safety property
  2. The program ends eventually – the liveness property

Milk problem – A Subtle Introduction to Mutual Exclusion(MutEx)

med_6672_Elegant_MorningAssume that two students live in the same dorm, thus having a common fridge.
whenever they run out of milk, someone should go and get some milk, however, there should be no more than one gallon of milk.

Problem: Let’s say that one morning one of them saw that there is no milk, then he went to buy some. Meanwhile, the other dude just woke-up and noticed that there is no milk as well(not knowing about his friend already committed to bring milk), then, like his other roommate, runs to buy milk.
Therefore, all the end of the day(eventually) we’ll end up with 2 milk gallons in the fridge, which is prohibited according to the rules.

To solve this, we can stick a note on the fridge door which tells that someone already sacrificing to bring milk. But, will this be enough? Of course Not!!
What can go wrong with that? Well, let’s say that while sticking the note on the fridge door, the other dude opened it and saw there’s no milk and went getting some regardless of the will of his friend to get milk too. Again, we ended up with 2 milks..

Condition: It’s obvious  that we need something strict to keep that from happening. The additional condition we need is to keep the other dude from approaching the fridge as long as his other roommate is either writing the note OR buying milk. That basically means, keeping him out of the critical section

Critical Section

diceFor the operating system, a critical section can be, for example, adding element to a linked list.

Challenge: Making it possible for multiple processes to atomically implement “complicated” set instructions while running in the CPU.

Let’s look again at what I just said:
atomically means that no other process interrupts the execution of those set of instruction. For example, look at this block of code:

 

Global Variables:

int a,b;
a = 12;
b = a + 12;
a++;

between any 2 instructions in Process1, another process could be interrupting by changing the value of the global variables, which accounts for a fake value of the results of Process1.

Therefore, a critical section, usually deals with shared resources, and outside of that section there are no shared resources. Because of that, in order for a process to enter the critical section, it must request that via an Entry Section, and exit the critical section through the Exit Section. Thus, the hierarchy goes as follows:

Before we carry on, please remember the following facts:
– Throughout the whole time there are interrupts, system calls, and preemptions.
– The goal behind the critical section, is preventing more than one thread to be working on this particular section of the code.

Now on, we’ll discuss ways of implementing the Exit  and  Entry Sections.

The methods I’ll present to you satisfy the following 2 conditions:

  1. Mutual Exclusion: Only one process is in the critical section at any given time.
  2. Progress: If there is no process in the critical section, in spite of the existence of some processes that need to enter the critical section, eventually, one of those processes will end up in the critical section. In other words, there is always a progress in executing the processes.

We can prevent starvation by introducing Bounded Waiting: if  process X requests to enter the critical section, there will be a limited number of times for other processes to enter the same critical section before X from the moment that X requested to enter the Critical Section until its exiting.

In the following attempts to resolve the problem we’ll basically be in the scenario where 2 processes; 0 and 1, trying to enter a Critical Section

Attempt 1

shared int turn = 0
do {
while (turn != i) {} //wait  This is our entry
	/* **************** */
	/*					*/
	/* critical section */
	/*					*/
	/* **************** */
	turn  = 1 – i;        //This is our exit
	/* **************** */
	/*					*/
	/* reminder section */
	/*					*/
	/* **************** */
} while(1);

Discussion:

The code above indeed provide Mutual Exclusion, means that process 0 and 1 cannot enter the Critical Section together at the same time.

However, say that process 0 doesn’t want to enter the Critical Section, this results in that process 1 cannot enter the Critical Section  as well, why? Since the value of the shared variable ‘turn’ couldn’t be updated. Also, remember that an external process cannot interfere with the one which is already in the Critical Section. A situation like that is called Strict Alternation.

Conclusion: This solution violates the progress property.

Attempt 2

Shared int busy = 0;
do {
	//Entry Section:
	while(busy) ; //wait
	busy = 1;
	/* **************** */
	/*					*/
	/* critical section */
	/*					*/
	/* **************** */
	//Exit Section:
	Busy = 0;
	/* **************** */
	/*					*/
	/* reminder section */
	/*					*/
	/* **************** */
} while(1);

Discussion:

Basically what we have here is something similar to Attempt1, since the other process keeps waiting as long as procces0 is busy, means in the Critical Section.

Attempt 3

Shared bool flag[2]  = {false};
do  {
	//Entry Section:
	flag[i] = true
	while(flag[1-i]);
	/* **************** */
	/*					*/
	/* critical section */
	/*					*/
	/* **************** */
	//Exit Section:
	flag[i] = false;
	/* **************** */
	/*					*/
	/* reminder section */
	/*					*/
	/* **************** */
} while(1);

Discussion:

The code above assures Mutual Exclusion, however, it guarantee no progress.

Let’s consider this scenario:

,  , (context switch) ,

What happens above is: The 2 processes(0 and 1) are stuck in the “while” loop at the Entry Section. A situation like that is called: “Deadlock”

Attempt 4 – modify Attempt 3

Shared bool flag[2]  = {false};
do {
	flag[i] = true;
	while(flag[1-i]) {
		flag[i] = false;
		/*wait*/
		flag[i]  = true;
	}
	/* **************** */
	/*					*/
	/* critical section */
	/*					*/
	/* **************** */
	flag[i] = false;
} while(1);

Discussion:

Let’s say that process0 (p0) requested to enter the Critical Section by setting ‘flag[0] = true’. The Entry Section in the code above checks first if process1 (p1) is in the Critical Section  already(by the loop: “while(flag[1-0])”), if yes, then p0 should wait for p1 to finish, how? Well, by setting “flag[0] = false”, after that, p0 waits for p1 to finish, and then request again by setting “flag[0] =true”(notice that all this is happening in the “while” loop in the Entry Section), if p1 is done, then p0 takes on the Critical Section.

This solution guarantee Mutual Exclusion but not progress, take a look at the following running procedure that portray a deadlock scenario.
That scenario can go over and over again without gaining progress.

Attempt 5 – Correct Way!

shared bool flag[2] = {false};
shared int turn = 0;
do {
	flag[i] = true; //current process needs to enter
	turn = 1 - i; //turn of the other process is prior
	//if the later process wants to enter-
        //and it's its turn, then wait:
	while(flag[1-i] && turn == (1 - i));
	/* **************** */
	/*					*/
	/* critical section */
	/*					*/
	/* **************** */
	flag[i] = false;

	/* **************** */
	/*					*/
	/* reminder section */
	/*					*/
	/* **************** */
} while(1);
Advertisements