[CS 704D] Mutual Exclusion and Trial Algorithms

The semaphore idea offered by Dijikstra was a brilliant idea, it created a simple mechanism for setting up mutual exclusion. Until that happened, several algorithms were tried to solve the problem of safeguarding a critical section through mutual exclusion. The purpose of this post is to discuss these algorithms and look at what they had to offer. In today's post we discuss the first algorithm. The reference source is,

Operating Systems Concepts and Design - Milan Milenkovic, TMH

A typical coding for a mutex process, named mutex-1 here could be as follows.Comments are included in [ ] brackets.

program/module mutex-1;
.
.
.
type
       who= (proc1), (proc2) ; [an enumerated, user defined type define to processes in existence]
  var
        turn : who;                     [a variable turn is defined to contain the id of the process that is to be handled]

process p1;                          [pseudo code for the process 1]
   begin 
           while true do             [once a process is initiated]
           begin  
                    while turn= proc2 do (keeptesting);  [ this is the busy-wait part of controlling the critical section]
                    CRITICAL SECTION;
                    turn = proc2;       [release the  semaphore, in this case explicitly assign to the other process]
                    .
                    .                        [ code for other actions in process p1]
            end (while);
  end (p1)

process p2;                          [pseudo code for the process 2]

   begin 

           while true do             [once a process is initiated]

           begin  

                    while turn= proc1 do (keeptesting);  [ this is the busy-wait part of controlling the critical section]

                    CRITICAL SECTION;

                    turn = proc1;       [release the  semaphore, in this case explicitly assign to the other process]

                    .

                    .                        [ code for other actions in process p2]

            end (while);

  end (p1);

[parent process]

begin (mutex1)

       turn =  .....;         [ turn can be initiated to proc1 or proc2; this decides who starts first]

       initiate p1,p2;

end [mutex1]            

The control mechanism forces a strict turn on the two processes. In a computer system the processes will be running at unpredictable speeds compared to each other. Thus, the slower process will force an overall average speed of the slower process on all the processes. Besides, there is a more serious problem. If one process crashes it will stop the other process permanently. Further, if it crashes after acquiring the lock and then crashes, the other process will not get access to the resource, even if it is not being used. One way around is to let the OS handle the procedures to be used in the critical section. the OS would be able to use time outs to detect if a crash and stoppage has occurred.

Either process will have to be aware of the other. In general that is bad policy. One process can, maliciously, affect the operation of the other.