cmsc412 note 8

CMSC 412

NOTE 8

March 16, 1999

Low-level Atomic Read-Modify-Write Constructs

1. Overview

As we have seen earlier, solving process synchronization problems with read-write atomicity only is very difficult. At the same time, we cannot always resort to disabling interrupts, because it is not flexible, cannot be provided to users, and does not work for multi-cpu systems. Hence most systems provide atomic execution of some type of read-modify-write instructions. Examples include:

Test-and-Set instruction:

  boolean test_and_set( memoryBit target ) {
     returns old value of target and sets target to true
  }

Swap instruction:

  boolean swap( memoryBit a, b ) {
     swaps the values of a and b
  }

2. Using Test-and-Set and Swap

Read-Modify-Write atomicity allows us to easily solve the N-process Mutual Exclusion problem.

Algorithm using test-and-set

  // variables shared by processes 0, 1, ..., N-1
  boolean lock initially FALSE
 
  entry(i) {
    while test_and_set( lock ) do skip ;
    // at most one process comes here
  }

  exit(i) {
    lock := FALSE ;
  }

The above program satisfies the safety property but not the progress property (because we still cannot assume anything about process speeds other than that it is non-zero).

Algorithm using swap

Here is a program using Swap instructions that satisfies safety but not progress:

  // variables shared by processes 0, 1, ..., N-1
  boolean lock initially FALSE
 
  entry(i) {
    boolean key := TRUE ;
    repeat swap( key, lock ) until key=FALSE ;
  }

  exit(i) {
    lock := FALSE ;
  }

Another algorithm using test-and-set

Here is a program using Test_and_Set instructions that satisfies safety and progress. As in the above solutions, there is a lock. However, when a process leaves the CS, it frees the lock only if there is no waiting process, otherwise it "passes" the lock to the "next" waiting process instead of allowing all process to contend for the lock. "Next" can be defined using any circular ordering of the processes; here, the next process after process i is process (i+1) mod N.

  // variables shared by processes 0, 1, ..., N-1
  boolean lock initially FALSE ;            // read/writeable by all processes
  boolean waiting[0..N-1] initially FALSE ; // read/writeable by all processes

  entry(i) {
    boolean key := TRUE ;
    waiting[i] := TRUE ;
    while ( waiting[i] and key ) do {
          key := test_and_set( lock ) ;
    };
    waiting[i] := FALSE ;
  }

  exit(i) {
    int p ;
    // search for next waiting process
    p := (i+1) mod N ;
    while ( p != i and not waiting[p] ) do {
      p := (p+1) mod N ;
    };

    if p=i
      then { lock := FALSE }        // no waiting proceses
      else { waiting[p] := FALSE }  // p is next waiting process. Free it
  }

In entry(i), the while-loop test succeeds (and hence process i busy waits) if and only if the lock is already false (i.e., grabbed by another process) and this process is waiting. So a process j that has grabbed the lock can give it to process i by setting waiting[i] to false.