Race Conditions and Process Synchronization

Two SR processes doing sum:=fn(sum,i) at about the same time is also a race condition: sum takes the place of N, i takes the place of 1, and the function fn takes the place of +.
SR Program: A Race Condition.

There is a fixed $10 million in this bank (10,000 accounts that each start out with $1000) but the auditor sometimes sees more, sometimes less. Can you figure out what is going wrong here?
SR Program: A Different Kind of Race Condition.

An another example of what can go wrong, this time using a linked list.

Suppose we have a computer, single CPU with round-robin context switching or multiple CPUs, shared memory.

      memory:
  ----------------------------------------
  | process A . shared queue . process B |
  ----------------------------------------

      shared queue:
  head -> 1 -> 2 -> 3 -> 4 ->null
                         ^
  tail ------------------|

  to add a new node x to the queue

  old_tail is a local variable
    link(node x) := null         /* null out x's next pointer */
    old_tail := tail             /* follow tail to node 4 */
    tail := address x            /* change tail from 4 to x */
    link(old_tail) := address x  /* change 4 from ->null to ->x */

Suppose processes A and B that share the queue both try to add new nodes 5 and 6 respectively to the queue at about the same time.

A Race Condition Adding to a Queue.

PostScript version of above.
If you cannot spawn an external PostScript viewer or see GIFs, try this.

We need a way to keep the instructions from A and B that add an element to the queue from getting interleaved.

    process A                                process B
    ---------                                ---------
      ...                                       ...
      add_to_queue(queue, node 5)               add_to_queue(queue, 6)
      ...                                       ...

We will call the instructions in each process that add to the queue a critical section of code.

Earlier queue example is an example of a race condition:

• two or more processes share data
• they are reading and writing the shared data concurrently
• final result depends on who does what when

Another very simple example: suppose processes A and B execute N:=N+1 at about the same time.

  Process A                          Process B
  ---------                          ---------

  shared variable N initially 0      shared variable N
  ...                                ...
  N := N + 1                         N := N + 1
  ...                                ...

On load/store register architectures, N:=N+1 compiles to something like
load N into accumulator
accumulator := accumulator + 1
store accumulator into N

On a shared-memory multiprocessor or a uniprocessor with context switching, the machine language instructions could get interleaved thusly

    process A: load N to acc        (context switch)
            B: load N to acc        (context switch)
            A: acc := acc + 1       (context switch)
            B: acc := acc + 1       (context switch)
            A: store acc to N       (context switch)
            B: store acc to N       (context switch)

Final value of N is 1 and is incorrect. Any interleaving (other than all A followed by all B or vice versa) will give incorrect results.

These examples show that concurrently executing processes that share data need to

• synchronize their operations and processing in order to
• avoid race conditions on shared data

Critical Sections and Mutual Exclusion

Critical section

a section of code in a process that accesses one or more shared variables in a read-update-write fashion

Mutual exclusion

only one process at a time can access (read-update-write) a shared variable at a time

Mutual exclusion problem

how to keep two or more processes from being in their critical sections at the same time

• no assumptions about the number of CPUs or their relative speeds
• no process outside its critical section may block other processes outside their critical sections from entering
  • no deadlock
  • also called a ``safety'' property (absence of unnecessary delay)
• no process should have to wait forever (be blocked from) to enter its critical section
  • no starvation
  • also called a ``liveness'' property (eventual entry)

the above two can be recast as the following three

1. no deadlock: this would occur if two processes tried to enter their critical sections at about the same time, and neither succeeded even though no other processes were in their critical sections
2. no starvation in the absence of contention: this would occur if a process tried to enter its critical section and no other processes were in their critical sections, but it could not enter
3. no starvation in the presence of contention: this would occur if two or more processes were trying to enter their critical sections, but one never gets to while the other(s) gets to over and over again

Atomic instruction or atomic action

in a computer architecture, some machine language instruction that is executed completely without interruption or executed not at all

without interruption means no interleaving of other instructions from another process, no context switching, no hardware interrupts

for example, load register from memory and store register to memory

some architectures have an instruction to increment a memory location atomically

some architectures let a processor lock the bus for a sequence of instructions so they are done atomically

in general or abstractly speaking, an atomic action ``makes an indivisible state transition''

``any intermediate state that might exist in the implementation of the action must not be visible to other processes'' (p. 60 Andrews Concurrent Programming book)

this means nothing from another process can be interleaved in the implementation of the action for it to be atomic

Critical sections need to be done as if they were one atomic action to avoid race conditions.

The mutual exclusion problem is

to devise a pre-protocol and a post-protocol based on either hardware or software

that prevent two processes from being in their critical sections at the same time

that have the desirable no deadlock and no starvation properties

that allow critical sections to be executed atomically

given that

• load/store register architecture
• multiple concurrently executing processes are sharing data
• single or multiple CPUs where we cannot make relative speed assumptions
• accesses to shared variables can be interleaved if two processes are in their critical sections at the same time
• processes may not halt in their pre- or post-protocols
• processes may not halt in their critical sections
• processes may halt outside their critical sections

process Pi, i = 1, 2, 3, ...

    while (true) {
      ...
      non critical section code;
      ...
      mutex_begin(i);   /* pre-protocol */
      ...
      critical section code;
      ...
      mutex_end(i);     /* post-protocol */
    }

The mutual exclusion problem becomes, how do we implement mutex_begin() and mutex_end()?

Several approaches:

busy waiting vs. blocking (with a call to the OS)

pure user-level software vs. hardware vs. OS assistance

Hardware solution

  mutex_begin() {                             mutex_end() {
    disable interrupts;                         enable interrupts;
  }                                           }

  mutex_begin() {                             mutex_end() {
    lock bus;                                   unlock bus;
  }                                           }

this works but

• bad to let regular users do this (nobody else can do anything at all until they re-enable interrupts or unlock bus)
• okay for kernel to do this for short periods of time (disable interrupts and lock bus are privileged instructions probably)
• disable interrupts doesn't work for multiple CPUs

Software with busy waiting possible solution

process Pi brackets its critical section code with mutex_begin(i) and mutex_end(i), passing its id i as a parameter

                    shared boolean lock_flag = false;
  mutex_begin() {                             mutex_end() {
    while (lock_flag) {                         lock_flag = false;
      /* skip */ ;                            }
    }
    lock_flag = true;
  }

does not work

still have race condition: both processes retrieve false lock flag at the same time, so mutual exclusion not enforced

Another software with busy waiting possible solution

                    shared int turn = 1;
  mutex_begin(i) {                               mutex_end(i) {
    while (turn != i) /* skip */;                  turn = (i % 2) + 1;
  }                                              }

this sorta works but

• called strict alternation
• violates the ``no starvation in absence of contention'' desirable property

Another software with busy waiting possible solution

    shared boolean flag[2]; /* flag[i] is intention of Pi to enter CS */
    j = (i%2)+1; /* i=me, j=other */

  mutex_begin(i) {                               mutex_end(i) {
    flag[i] = true;                                flag[i] = false;
    while (flag[j]) /* skip */;                  }
  }

mutual exclusion ok

but deadlock possible if both set their flags and enter while loops at same time

Another software with busy waiting possible solution

  mutex_begin(i) {                               mutex_end(i) {
    while (flag[j]) /* skip */;                    flag[i] = false;
    flag[i] = true;                              }
  }

mutual exclusion not ok

Software with busy waiting solution

Peterson's algorithm

satisfies all desirable properties

                      shared int turn = 1;
                      shared boolean flag[2];
  mutex_begin(i) {                               mutex_end(i) {
    flag[i] = true;                                flag[i] = false;
    turn = j;                                    }
    while (flag[j] and turn=j) /* skip */;
  }

Hardware solution with busy waiting

test_and_set instruction, atomic and uninterruptible

test_and_set(register, memory_location, value) {

retrieve contents of memory_location to register;

store value in memory_location;

}

                    shared boolean lock_flag = false;
  mutex_begin() {                             mutex_end() {
    do {                                        lock_flag = false;
      test_and_set(R, lock_flag, true);       }
    } while (R = true);
  }

Busy waiting, either hardware or software, wastes CPU cycles.

Also, if a low priority process is in its critical section and a high priority process starts busy waiting, the latter will starve (never enter its critical section).

An attempt at a blocking solution (using OS help)

sleep();
wakeup();

bounded buffer problem, room for at most N items in buffer

                shared int N, count
producer                                consumer
--------                                --------
  while (true) {                          while (true) {
    produce_item(...);                      if (count == 0) sleep();
    if (count == N) sleep();                remove_item(...);
    enter_item(...);                        count--;
    count++;                                if (count == N-1) wakeup(producer);
    if (count == 1) wakeup(consumer);       consume_item(...);
  }                                       }

wakeup is lost if process is not sleeping

consumer: if (count == 0) sleep(); compiles into

    load count into accumulator
                              <--- context switch, producer sends wakeup
    if (accumulator == 0) ...

now producer fills up buffer and sleeps forever

Need to be able to store wakeup signals