Concurrent Programming Class Notes

Lecture Notes for Concurrent Programming

17 June 2003 - Implementing Critical Sections

Outline

A Simple Implementation
- Removing Interference
- Removing Atomicity
- Software Atomicity
Look Before Leaping (Peterson's Algorithm)
Ordering waiters (The Ticket Algorithm)
Self-ordering waiters (The Bakery Algorithm)
Implementation details
- Interfaces
- Classes

A Simple Implementation

If the critical section is empty, walk right in; otherwise wait.

bool cs_occupied = false

// entry protocol

   { true }
   while (cs_occupied) skip
   { !cs_occupied }
   cs_occupied = true
   { cs_occupied }

// critical section

// exit protocol

   { cs_occupied }
   cs_occupied = false
   { !cs_occupied }

This is called a spin-lock solution.

It does not provide mutual exclusion.
- The statement cs_occupied = true in computation j interferes with the entry-protocol predicate { !cs_occupied } in computation i.

Removing Interference

The predicate { !cs_occupied } can't get any weaker.
Read-write segregation isn't possible because cs_occupied must be read and written at the same time.
There's no local part for the global invariant, and all computations must write cs_occupied.

That leaves atomicty.

// entry protocol

   { true }
   < while (cs_occupied) skip
     { cs_occupied }
     cs_occupied = true 
   >
   { cs_occupied }

The exit protocol is already atomic by assumption.

Removing Atomicity

We still need to deal with the atomic sequence
```
< while (cs_occupied) skip ; cs_occupied = true >
```
- It's been squeezed into a simple, generic form.

We can implement this atomic sequence using hardware.

The test-and-set operation

bool test_and_set(bool & b)
  < bool t = b;
    b = true;
    return t;
  >

With test-and-set, the entry protocol is

{ true }
while test_and_set(cs_occupied) skip
{ cs_occupied }

Software Atomicity

The test-and-set solution has some problems:
- It requires a strongly fair scheduler to provide eventual entry.
- It's hardware dependent.
O.k. - atomicity's out. What else we got?
- Weakening is still not helpful.
- A global invariant still needs local var
Let's try read-write variables.

Wait until the other computation's clear.

bool in1 = false, in2 = false

// entry protocol

   while in2 skip		while in1 skip
   { not in1 and not in2 }	{ not in1 and not in2 }
   in1 = true			in2 = true
   { in1 and not in2 }		{ not in1 and in2 }

// exit protocol
   
   in1 = false			in2 = false

This solution doesn't implement mutual exclusion.

Take Turns

Raise the flag, then go.

bool in1 = false, in2 = false

// entry protocol

in1 = true              in2 = true	   
while in2 skip		while in1 skip	   
{ in1 and not in2 }	{ not in1 and in2 }

This solution deadlocks when both set in to true "at the same time".

There's a symmetry between the computations' execution.

Break the symmetry by picking the winner.

bool in1 = false, in2 = false
int winner;

// entry protocol

in1 = true		     in2 = true
winner = 2		     winner = 1
while in2 and winner == 2    while in1 and winner == 1

// exit protocol

in1 = false		      in2 = false

Turn-Taking Analysis

winner ensures mutual exclusion.
- It can only be 1 or 2 when in1 and in2 is true.
Competitive entry produces a winner.
- winner can only be 1 or 2.
Non-competitive entry is immediate.
- in[j] fails immediately for computation i.
Entry is fair.
- The monotonic while guard requires only weakly-fair scheduling.
n-computation turn-taking is a bit tricky.
- Each computation reaches the critical section after taking n steps.
- A computation advances one step if
  - there are no computations ahead of it, or
  - it gets pushed from behind by a new computation.

Ordering Waiters

n-computation turn-taking requires O(n²) work.
- Each computation advances at its own pace.
- Every computation checks every other computation before advancing.

Assign each computation a number to determine the waiting order.

Use tickets, like they do in stores.

## in_cs(i) imp tickets[i] = current
## forall i, j : 0 < i < j <= n 
##             : tickets[i] != tickets[j]

int ticket = 1
int current = ticket
int tickets[1:n] = (-1, -2, ..., -n)

// entry protocol

   < tickets[i] = ticket ; ticket = ticket + 1 >
   < await tickets[i] == current >
   
// exit protocol

   < current = current + 1 >

Ticketing Global Invariant

A computation in the critical section holds the current ticket.
- in_cs(i) imp tickets[i] = current
Every computation's ticket is unique among all computations' tickets.
- forall i,j : 0 < i < j <= n : tickets[i] != tickets[j]
The invariant is initially true.
< tickets[i] = ticket ; ticket++ > preserves uniqueness.
< await tickets[i] == current > preserves ticket entry.

Ticketing Properties

Ticketing provides mutual exclusion.
- Only the current-ticket holder can enter the critical section.
Ticket uniqueness provides competitive success.
- The computations are totally ordered by ticket.
Ticketing provides non-competitive success.
- The solitary computation holds the current ticket.
Ticket numbering provides fairness.
- The computations are stably ordered.
- A weakly fair scheduler is enough.

Implementing Ticket Ordering

< await tickets[i] == current > obeys the At-Most-Once property and is effectively atomic.
- The await statement can be replaced by the spin lock
```
while (tickets[i] != current) skip)
```
< current = current + 1 > doesn't obey the At-Most-Once property, but is effectively atomic anyway.
- By the global invariant.
< tickets[i] = ticket ; ticket++ > is a problem.
- Hardware may help with an atomic fetch-add-return instruction.
- Otherwise, use another critical-section implementation.
  - A spin-lock or turn-taking protocol.

Alternatives to Tickets

The ticket algorithm requires special hardware or another critical-section implementation.
- The problem is contention at the ticket machine.
- Can we eliminate the machine?
Derive a new ticket from existing tickets.
- This is similar to putting yourself at the end of the line.
The new ticket should be larger than all existing tickets.
- Assume n computations, each having a ticket in int tickets[1:n].
- Unused tickets are set to 0.
- Computation i computes its ticket value as
```
tickets[i] = (max i : 1 <= i <= n : tickets[i]) + 1
```
A computation enters the critical section when it's first in line.
- When its ticket is smallest among the in-use tickets.
When a computation leaves the critical section, make the ticket unused.

The Bakery Algorithm

The resulting algorithm is known as the Bakery Algorithm.

## in_cs(i)  imp  
##   tickets[i] > 0 and
##   forall j : 1 <= j <= n and i != j 
##            : (tickets[j] = 0)  or 
## 	        (tickets[i] < tickets[j])

int tickets[1:n] = ([n] 0)

// entry protocol

< tickets[i] = 
    (max i : 1 <= i <= n : tickets[i]) + 1 
>
for [j = 1 to n st j != i]
  < await (tickets[j] == 0) or 
	  (tickets[i] < tickets[j]) 
  >

// exit protocol

tickets[i] = 0

A computation in a critical section holds a valid ticket smaller than all other valid tickets.

Bakery Algorithm Properties

The Bakery algorithm provides
1. Mutual exclusion via the unique smallest ticket.
2. Competitive success via the smallest ticket.
3. Non-competitive success because unused tickets are zero.
4. Fairness via an ordering over unique values.
The global invariant holds because
- New ticket values are computed atomically, ensuring uniqueness.
- The smallest in-use ticket gets the critical region.

Implementing The Bakery Algorithm

The implementation seems hard.
- Computing
```
< tickets[i] = 
    (max i : 1 <= i <= n : tickets[i]) + 1 
>
```
  is too complicated for hardware atomicty, and too slow for software atomicty.
- The await statement guard
```
(tickets[j] == 0) or (tickets[i] < tickets[j]) 
```
  doesn't obey the At-Most-Once property.
What happens if the new ticket computation isn't atomic?
- New ticket values may not be unique.

Tie-Breaking Again

Two computations with the same ticket. Who wins?

A standard trick: use the computation id to break the tie.

for [ j = 1 to n st j != i ]
  < await turn[j] == 0 or
 	  (turn[i] < turn[j]) or
	  (turn[i] == turn[j]  and  i < j)
  >

What about atomic execution?
- Does
```
tickets[j] = 
  (max k : 1 <= k <= n : tickets[k]) + 1
```
  interfere with the await guard?
- Does tickets[j] = 0 interfere with the await guard?
- With no interference, replace the await with a while.

Critical Section Interfaces

Implement an abstract virtual class (or interface).

// C++

class critical_section
  virtual void enter(unsigned tid) = 0
  virtual void exit(unsigned tid) = 0

// Java

interface CriticalSection
  void enter(int tid)
  void exit(int tid)

An interface abstracts away implementation details, leaving only behavior.

// C++ 

void f(critical_section & cs)
  cs.enter(tid)
    // whatever
  cs.exit(tid)

// Java

void f(CriticalSection cs)
  cs.enter(tid)
    // whatever
  cs.exit(tid)

Notice the & for C++; it's important.

Critical Section Implementations

class two_way_tie_breaker
  : critical_section

  two_way_tie_breaker()
    in[0] = in[1] = false;

  void entry(unsigned me)
    assert (me == 0) or (me == 1)
    assert !in[me]
    const unsigned other = (me + 1) % 2
    in[me] = true ; winner = other
    while (in[other] and winner == other) ;
    
  void exit(unsigned me)
    assert (me == 0) or (me == 1)
    assert in[me]
    in[me] = false

  bool in[2]
  int winner

Each instance is a separate critical section.
Global scoped has been pushed down into class scope.
Check everything; this code is crucial.

Points to Remember

Gradually work towards an implementable design.
- Push atomic execution to smaller code segments.
- Rely on effectively atomic statements.
Break ties caused by non-atomic execution.
- Peterson's Algorithm picks winners.
- The Bakery Algorithm uses non-unique tickets.
Impose order for better performance.
- The Ticketing Algorithm
Abstract implementations with a critical-section interface.
Push global state into critical-section classes.

This page last modified on 25 June 2003.