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 ;

}

 

                 

 

0Comment