Hardware Solution to Mutual Exclusion

By | October 10, 2021

Hardware Solution to Mutual Exclusion or Synchronization Hardware

The various hardware based methods that can be used to solve the critical section problem.

Interrupt Disabling

  • On a single CPU system, processes do not actually execute in parallel. Concurrency is achieved by interleaving the execution of the ready processes.
  • Once a process has gained control of the CPU, it can only loose that control when it invokes an operating system service or when it is interrupted.
  • Thus simplest solution for mutual exclusion is to have each process disable all interrupts just after entering its critical section.
  • The process can reenable these interrupts just before leaving the critical section.
  • Thus once a process has disable interrupts, it can use the shared memory without the fear that any other process will interfere.
  • This solution is appropriate for uniprocessor machine. During the calculation of critical section, multiprogramming is not utilized by this solution.
Disabling interrupts

Disadvantages of Disabling Interrupts

There are several disadvantages of this solution:

  1. It works only in a single processor environment.
  2. Performance of the system is degraded, as multiprogramming is not utilized during the execution of critical section.
  3. A process waiting to enter its critical section could suffer from starvation.
  4. This approach will not work in multiprocessor architecture. When the computer system includes more than one processor, it is possible for more than one process to be executing at a time. To disable interrupts, all processors will have to inter-communicate with each other and this will be a time consuming effort. Thus it does not guarantee mutual exclusion.

Hardware Instructions

Many machines provide special instructions that can read, modify and store a memory word atomically. The most commonly used instructions are :

  1. Test-and-Set instruction (used in Motorolla 68 K)
  2. Compare-and-Swap instruction (in IBM 370 and Motorola 68K)
  3. Exchange instruction (used in X86)

1. Test and Set

  • This instruction provides the action of testing a variable and consequently setting it to a stipulated value.
  • Test-and-set instruction executes atomically.
  • Test-and-set instruction operates on a single Boolean variable (used as a switch indicator). In our example the shared variable is locked.
boolean Test and Set (boolean locked)
{
if(locked)
  return true:
else
{
  locked = true;
  return false;
  }
}
Solution using test-and-set instruction
  • If the variable has a value of O, it replaces it with 1 and return false, otherwise it returns true.
  • Mutual exclusion is met because if first process is in critical section, it sets the value of lock to true (by executing test-and-set function).
  • Thus second process will have a true value for test-and-set instruction and therefore, it will not come out of the while loop till the lock is set to false by the first process executing its critical section.
  • Thus, test-and-set instruction guarantees mutual exclusion and prevents starvation.

2. Compare-and-Swap

  • This instruction operates on the contents of two words and is executed atomically.
  • The definition of swap instruction is given in figure.
boolean void swap (boolean a, boolean b)
{
  boolean temp;
  temp = b;
  b= a; 
  a = temp;
}
Solution using swap instruction
  • Mutual exclusion is achieved as follows : A global variable lock is declared and initialized to false. In addition, each process also has a local boolean variable key which can be set to either true or false.

3. Exchange

  • This instruction exchanges the contents of a register with that of a memory location.
  • During the execution of this instruction, access to the memory location is blocked f any other instruction referencing that location.
  • The exchange instruction is defined in figure.
  • In this procedure, a shared variable is used that is initialized to 0.
  • The process that may enter its critical section is one that finds this shared variable equal to 0.
  • It then excludes all other processes from the critical section by setting this variable to 1.
  • When a process leaves its critical section it resets this shared variable to 0, allowing another process to gain access to its critical section.
Void exchange(int register, int memory)
{
  int temp;
  temp = memory;
  memory = register;
  register = temp;
}

Advantages of using hardware instruction approach

  1. The various advantages of using machine instruction to enforce mutual exclusion are:
  2. It is applicable to any number of processes on either a single processor of processor sharing main memory.
  3. It is simple and therefore easy to verify.
  4. It can be used to support multiple critical sections ; each critical section can be defined by its own variable.
Hardware Solution to Mutual Exclusion

Disadvantages of using hardware instruction approach

1. Starvation is possible: When a process leaves a critical section and more than one process is waiting, the of is Thus, some process process is waiting, the of is Thus, some process could indefinitely be denied access.

2. Busy-waiting is employed: While a process is waiting for access to a critical section, it continues to consume processor time.

Busy-waiting means that while a process is in its critical section, any other process that tries to enter in its critical section must loop continuously till it can enter the critical section. This leads to the wastage of CPU cycles, which could have been used by some other process to do some very important task as compared to continuous waiting. Figure explains this concept more clearly.

Busy-waiting leads to wastage of CPU cycles

3. Deadlock is possible: Consider the following scenario on a single processor system :

  1. Process P1 executes the special instruction (for example, exchange) and enters its critical section.
  2. After some time P1 is interrupted to give the processor to P2, which has higher priority.
  3. If P2 now attempts to use the same resource as P1, it will be denied access because of mutual exclusion mechanism. Thus, it will go into a bust-waiting loop.
  4. However, PI will never be dispatched because of its lows priority than another ready process P2. This will result in deadlock.

Leave a Reply

Your email address will not be published. Required fields are marked *