Hardware Solutions

Test and Set (or Test and Set lock) instruction

This test and set instruction is used to write 1 (set) to a memory location and return its old atomic value. If the returned value is 1 (set) that means lock acquired is not available otherwise lock is free and it will set to 1. This is based on any number of processes and support multiple critical section

                   

Function Lock(boolean *lock)  {

   while(test_and_set(lock) = = 1) ;

}

 

Implementation:

                        

extern bool lock (false)

do

{

while (test_and_set (lock)) ;   /* wait for lock */

critical _section () ;

lock = false ;        /* Release the lock */

remainder_section () ;

}

while (true) ;

 

It satisfies mutual exclusion and progress but not bounded waiting (starvation). Busy waiting, starvation and deadlock may be possible in test and set instruction.

 

Swap Instruction

Another variation of test and set of two boolean variables is swap instruction which swaps two variables.

                       

Swap (x, y)

{

Int temp = x

x = y ;

y = temp ;

}

 

Implementation:

                        

boolean lock = false ;

do

{

 

temp = true ;

swap (lock, temp) ;

 

//Critical_section () ;

 

lock = false;

//Remainder section () ;

 

}

while (true) ;

                

When we compare the value before swapping; this is known as compare and swap instruction. It compares the value or content of a memory location to given value and, if they match then modifies the value or contents of that value into that memory location. This is atomic operation.

               

int compare_and_swap( int a, int oldval, int newval )

{

int temp = *a ;   /* present content of memory */

if ( temp = = oldval )

*x = newval ;

return temp ;

}

Implementation

                    

While (compare_and_swap(lock, 1) ! = 0) ; /* spin until lock = = 0 */

 

//Critical_section () ;

 

Lock = 0 ; /* release lock */

//Remainder section ;

            

Disabling interrupts

Disabling interrupts on one processor may not satisfies mutual exclusion condition of multiprocessor system, so disabling interrupts is insufficient on a multiprocessor system. Disabling interrupts blocks notification of external events that could trigger a context switch (e.g., timer). It works on kernel mode. Disabling interrupts is simplest way to enforce mutual exclusion on single processor system. A process waiting to enter its critical section could suffer from starvation.

Disabling/Enabling interrupts is same as acquire/release locks:

 

void lock() {

disable interrupts ;

}

void unlock() {

enable interrupts ;

}

 

Fetch and Increment Instruction

Fetch and increment (or Fetch and add) instruction return the value of a memory location and increment that memory location

                 

int fetch_and_add (address location)

{

int value = *location ;

*location = *location + 1;

return value ;

}

 

                 

 

Contributor's Info

Created:
0Comment
Software Solutions

Strict alternation or Turn variable or Dekker's algorithm

This is very simple approach included only two processes that are trying to synchronize. The algorithm allows only one process into critical section at a time means one process already in the critical section, then other process will have to wait. Strict alternation satisfies mutual exclusion and bounded waiting(no starvation) but it does not satisfies progress. It also avoid deadlock.

 

Algorithm 1: Use of turn variable

                              

turn=first;
do
{
while ( turn != first); /* if not ‘first’'s turn , wait indefinitely */
 

// Critical_section ();
 

turn = second; /* after ‘first’ leaves critical section, lets ‘second’ in */
//remainder section
}

while (true);  /* loop again */

 

Algorithm 2: Use of flag variable

                  

do
{
flag[first] = true; /* ready to enter CS */
while (flag[second]);  /* if ‘second’ also want the critical section then ‘first’ should wait */
 

// Critical_section ();

flag[first]= false; /*after ‘first’ leaves critical section, lets ‘second’ in
//remainder section

}

while (true);  /* loop again */

 

You can take first = P0 = i and second = P1 = j.

 

Peterson’s algorithm

This algorithm (combination of algorithm 1 and algorithm 2) is based on two processes, that require two shared data item; turn and two boolean flags.  If process i wants to enter into critical section, it sets flag[i] to true and if turn = = i then process is allowed into their critical section.

                                   

do
{
flag[first] = true;      /* ‘first’ is ready to enter into CS */
turn = second;       /* lets ‘second’ into CS, if both processes do this, turn will get the later value */
while (flag[second] && turn == second);

 

// critical section
 

flag[first]= false;    /* after ‘first’ leaves critical section, lets ‘second’ in */
//remainder section
}

while (true); /* loop again */

 

 

You can assume first = i = P0 and second = j = P1.

Shared variables flag[first] and flag[second] are initialized to False initially and turn is set randomly(either first or second).

When a process wants to enter into critical section, it raises its own flag (i.e., flag[first] = true) and sets turn to second. Condition of while loop checks flags and turn shared variables. If flag of second process is set and turn is second; this condition satisfied mutual exclusion. We can start with any of two process, initially no process is waiting for other process that to be executed, so it also satisfied progress. There is bound of time to enter into critical section for any process, so it's also satisfied bounded waiting(no starvation) condition. Peterson’s algorithm avoids deadlock.

 

Multiple process solution

For more than one processes filter algorithm generalizes Peterson’s algorithm. This requires (n -1) variable and a atomic register in per process.  

 

Barkery’s algorithm ( Multiple process solution )

This algorithm is based on multiple process

bool choosing[n]=0;  /* Shared Boolean array */
int number [n]=0;     /* Shared integer array to hold turn number */

do

{
choosing[first] = true;  

number[first] = max(number[0], number[1], ...., number[n-1])+1;

choosing[first]=false;

for( second = 0; second < n; next process )    

{
while (choosing[second]);    

while ((number[second] ! = 0 ) && (( number[second], second ) < ( number[first], first )));                                                      
}

//Critical Section ();.

number[first] = 0;      
//remainder section

}

while(true);

You can assume that first = i = P0 and second = j = P1 and so on.

Bakery algorithm satisfies mutual exclusion, progress, and bounded waiting(no starvation). It also avoids deadlock.

 

Contributor's Info

Created:
0Comment