Concurrent Programming Class Notes

Lecture Notes for Concurrent Programming

24 June 2003 - Using Semaphores

Outline

Mutual exclusion and mutex semaphores.
Conditional synchronization and signaling semaphores
Split-Binary Semaphores
- Multi-buffer producer-consumer synchronization.
The Dining Philosophers
The Readers-Writers Problem
- Passing the baton.
Resource scheduling.

Mutual Exclusion

There's a direct correspondence between critical sections and binary semaphores.
critical_section cs cs.enter(0) // whatever cs.exit(0)

semaphore s(1) s.get() // Whatever s.put()
- But semaphores don't use thread identifiers.

A Critical section has a simple binary-semaphore implementation.

int x = ... critical_section cs co cs.enter(0) x = ... x ... cs.exit(0) || cs.enter(1) x = ... x ... cs.exit(1) oc

int x = ... semaphore mutex(1) co mutex.lock() x = ... x ... mutex.unlock() || mutex.lock() x = ... x ... mutex.unlock() oc

Mutex Semaphores

A binary semaphore used for mutual exclusion is called a mutex.
- The operations on a mutex are lock() (get()) and unlock() (put()).
Make sure you get the mutex initialization right.
- It's usually unlocked, but may occasionally be locked.
The mutex global invariant is
```
(#mutex.put() - #mutex.get()) + #in_cr = 1
```
- The stone's either in the bowl or in the critical section.

Conditional Synchronization

Remember producer-consumer synchronization?

data buffer bool empty = true

producer while true while !empty skip buffer = p() empty = false

consumer while true while empty skip c(buffer) empty = true

How does it generalize to m producers and n consumers.
- There's lots of interference over empty and full.

Boolean semaphores manipulate booleans atomically.

data buffer semaphore empty(1) semaphore full(0) ## empty.available() + full.available() = 1

producer [i = 1 to m] while true empty.wait() buffer = p() full.signal()

consumer [i = 1 to n] while true full.wait() c(buffer) empty.signal()

Signaling Semaphores

A binary semaphore implementing conditional synchronization is known as a signaling semaphore.
- The operations on a signaling semaphore are wait() (get()) and signal() (put()).
- This is what railroad semaphores originally did.
A signaling semaphore is like a signal or an interrupt, except it remembers.
- However the notification is one-shot; the first waiter gets it.
- Conditional semaphores are not a substitute for boolean variables.

Split-Binary Semaphores

What is the global invariant for m-producer n-consumer synchronization?
```
empty.available() + #in_cr + full.available() = 1
```
- There is effectively only one stone between empty and full.
A split-binary semaphore is a set of n binary semaphores obeying the invariant
```
0 <= (Sum i : 0 <= i < n : s[i].available()) <= 1
```
Each semaphore in a split-binary semaphore may represent a different state of the shared resource.
- Computations queue up at the semaphore representing the resource state of interest.

Multi-Buffer Producer-Consumer

Producer-consumer synchronization isn't too concurrent.
- The producer and consumer wait around for the buffer.

Increasing the number of buffers improves concurrency.

Manage an array of buffers as a circular list.

const int k = ... data buffer[0 : k - 1] int front = 0, back = 0 semaphore empty(k) semaphore full(0) ## empty.available() + full.available() = k

producer while true empty.get() buffer[back] = p() back = (back + 1) % k full.put()

consumer while true full.get() c(buffer[front]) front = (front + 1) % k empty.put()

This solution uses counting semaphores to keep track of empty and full buffers.
- The semaphore's count keeps track of the number of resource units available.

Multi-Buffers, Mult-Producer-Consumers

Multiple consumers interfere over front; multiple producers interfere over back.

A little atomicity turns the trick.

const int k = ... data buffer[0 : k - 1] int front = 0, back = 0 semaphore empty(k), full(0) semaphore back_mtx(1), front_mtx(1) ## empty.available() + full.available() = k

producer [i = 1 to m] while true empty.wait() back_mtx.lock() buffer[back] = p() back = (back + 1) % k back_mtx.unlock() full.signal()

consumer [i = 1 to n] while true full.wait() front_mtx.lock() c(buffer[front]) front = (front + 1) % k front_mtx.unlock() empty.signal()

The Dining Philosophers

Five philosophers live around a table.
- There's a fork between adjacent philosophers.
- Philosophers alternately eat and think.
- Eating requires both adjacent forks.
- Philosophers may starve to death. (But do they really?)
How to manage the forks so that every philosopher lives?
- Safety: no philosopher starves to death.
- Liveness: every hungry philosopher eventually eats.
- These are two ways to say the same thing.
Symmetric solutions lead to deadlock.
- Every philosopher does the same thing.
  - Grab the left fork, then the right fork.

Asymmetric Solutions

Have different philosophers do different things.
- Odd philosophers pick up their right fork first.
- Even philosophers pick up their left fork first.

semaphore forks[0:4] = ([5] 1)

process philosopher [ i = 0 to 4 ]
  while true
      think
    forks[(i + ((i + 1) % 2)) % 5].lock()
    forks[i + (i % 2)].lock()
      eat
    forks[(i + ((i + 1) % 2)) % 5].unlock()
    forks[i + (i % 2)].unlock()

No circular wait chains; no deadlock possible.
Every philosopher eats eventually.

The Readers-Writers Problem

Reading and writing processes share a database.
- A writing process requires exclusive access to the database.
- A reading process can share database access with other readers.
Design an database access mechanism for the processes.
- Allow maximum concurrency (high throughput).
- Preserve database and operational integrity.
- Be fair (every process eventually gets in).
- Be timely (processes should not be unnecessarily delayed).
- Be predictable (a read following a write should be able to see the write's effects).

A Simple Readers-Writers Solution

Forget everything but mutual exclusion for the moment.

database db
semaphore mutex(1)

## mutex.available() + # in cr = 1

process reader [ i = 1 to m ]
  mutex.lock()
    read the data base
  mutex.unlock()

process writer [ i = 1 to n ]
  mutex.lock()
    write the data base
  mutex.unlock()

This protects the database but little else.
- It's not fair and it's not concurrent.

A Concurrent Readers-Writers Solution

The first reader leads the way for the rest.

database db
semaphore mutex(1)
int readers = 0

process reader [ i = 1 to m ]
  < if ++nr == 1 then mutex.lock() >
    read the data base
  < if --nr == 0 then mutex.unlock() >

process writer [ i = 1 to n ]
  mutex.lock()
    write the data base
  mutex.unlock()

This solution could starve writers.
- A never-ending stream of readers.

Safety and Liveness

A new mutex can provide reader atomicity.

process reader [ i - 1 to m ]

  r_mutex.lock()
    if ++nr == 1 then mutex.lock()
  r_mutex.unlock()

    read the data base

  r_mutex.lock()
    if --nr == 0 then mutex.unlock()
  r_mutex.unlock()

What's wrong with this code?
- It blocks in a critical section.

The critical-section exit liveness property is crucial here.
The eventual entry liveness property still doesn't hold.
- Readers can starve writers.

Adding Fairness

Using one semaphore for both readers and writers is complex.
- A waiter looks like any other waiter.
- Distinguish between the two with separate semaphores.
What is fair?
- Incoming readers wait if there are waiting writers.
- An exiting writer releases all waiting readers.
  - Or a waiting writer of there's no waiting readers.
- The last exiting reader releases a waiting writer.

An Incorrec

This code doesn't provide exclusive writer access. Why?

semaphore mtx(0) semaphore r_go(0), w_go(0) int dw = 0, dr = 0, nr = 0, nw = 0

// writer entry protocol mtx.lock() if nw + nr > 0 dw++ mtx.unlock() w_go.wait() mtx.lock() dw-- else nw++ mtx.unlock

// reader entry protocol mtx.lock() if nw + dw > 0 dr++ mtx.unlock() r_go.wait() mtx.lock() if --dr > 0 r_go.signal() nr++ mtx.unlock

// writer exit protocol mtx.lock() nw-- if dr > 0 r_go.signal() else if dw > 0 nw++ w_go.signal() mtx.unlock()

// reader exit protocol mtx.lock() if --nr == 0 and dw > 0 nw++ w_go.signal() mtx.unlock()

The Blown Invariant

Consider the invariant
There are nr readers in the database.
- Initially it's true.
- Unfortunately, it's not maintained by writers exiting the critical section.
The blown invariant, and the loss of atomicity implied
```
mtx.unlock()
r_go.wait()
mtx.lock()
```
prevents the code from providing writer-exclusive access.
- This code loses atomicity, exposing internal predicates to interference.
- This is a big problem when writing Java code.
An exiting writer fails to maintain the reader invariant.

An Unfair Solution

mtx.lock()        // reader entry
if nw + dw > 0 
  dr++
  mtx.unlock()
  r_go.wait()     { there are nr cs readers }
  mtx.lock()
  if --dr > 0     { there are nr cs readers }
    nr++
    r_go.signal() { there are nr cs readers }
else
  nr++
mtx.unlock


mtx.lock()        // writer exit
nw--
if dr > 0         { there are nr cs readers }
  nr++
  r_go.signal()   { there are nr cs readers }

else if dw > 0    { there are nw cs readers }
  nw++
  w_go.signal()   { there are nw cs readers }
mtx.unlock()

This code is still wrong. Why? Hint: writers still can starve. (Don't peek).

The Thief in the Night

Here's what we want.

Here's what we get.

Hopping in and out of mutual exclusion makes the readers-writers code complex and error-prone.
- It also makes the code expensive to execute.
Can we reduce the number of mutual-excluding hops made?

Passing the Baton

Can we reduce the number of hops into and out of mutual exclusion?
Consider an exiting reader enabling a writer.
- The writer obtains the stone directly from the reader.
  - No bowl means no competition.
- No semaphores are involved; mutual exclusion is maintained.
  - And you better make sure of that.
Passing the baton maintains mutual exclusion while changing the threads enjoying mutual exclusion.

The Baton Passing Mechansim

Without baton passing.

// entry protocol mtx.lock() if delay mtx.unlock() delay.wait() mtx.lock() // whatever mtx.unlock

// exit protocol mtx.lock() // whatever if delayed delay.signal() mtx.unlock()

With baton passing.

// entry protocol mtx.lock() if delay mtx.unlock() delay.wait() ~~mtx.lock()~~ // whatever mtx.unlock

// exit protocol mtx.lock() // whatever if delayed delay.signal() else mtx.unlock()

A Correct, Fair Readers-Writers Solution

// writer entry protocol mtx.lock() if nw + nr > 0 dw++ mtx.unlock() w_go.wait() ~~mtx.lock()~~ dw-- ~~else~~ nw++ mtx.unlock

// reader entry protocol mtx.lock() if nw + dw > 0 dr++ mtx.unlock() r_go.wait() ~~mtx.lock()~~ --dr nr++ if dr > 0 r_go.signal() else mtx.unlock

// writer exit protocol mtx.lock() nw-- if dr > 0 ~~nr++~~ r_go.signal() else if dw > 0 ~~nw++~~ w_go.signal() else mtx.unlock()

// reader exit protocol mtx.lock() if --nr == 0 and dw > 0 ~~nw++~~ w_go.signal() else mtx.unlock()

Baton Passing and Mutual Exclusion

Baton passing implements mutual exclusion by destroying it.
- The signaling and signaled computation are in the critical section at the same time.
This works as long as the exiting computation behaves.
- "Behaves" means "doesn't do anything but exit."
- This can be tricky to arrange.
```
// reader entry

mtx.lock()
if nw + dw > 0 
  dr++
  mtx.unlock()
  r_go.wait()
  --dr
if dr > 0
  r_go.signal()
nr++
mtx.unlock()
```
- Readers can interfere over nr++.

Resource Scheduling

You have r resources and u users requesting them, r < u.
- Disk drives, CPUs, messages, buffers, . . .
Denied requesters are delayed until satisfied.
- Assume each requester can be satisfied.

The general resource allocation solution is

allocation
request(parameters)
  < await request satisfied ; allocate >

void
release(parameters, allocation)
  < return allocation >

This solution selects an arbitrary waiting allocator.
- Which may or may not be acceptable.

General Resource Scheduling

The general implementation shape is

semaphore mutex(1)
semaphore change(0)
int waiters = 0

request()
  mutex.lock()

    while !satisfied
      waiters++
      mutex.unlock()
      change.signal()
      mutex.lock()
      waiters--

    // allocate

    if waiters > 0
      change.signal()

  mutex.unlock()

release()
  mutex.lock()

    // deallocate

    if waiters > 0
      change.signal()

  mutex.unlock()

Resource management is non-atomic and has interference.

Passing the Baton

Baton passing increases control over allocation and reduces the cost of mutual exclusion.

The general implementation shape is

semaphore mutex(1)
semaphore change(0)
int waiters = 0

request()
  mutex.lock()
    while !satisfied
      waiters++
      mutex.unlock()
      change.wait()
      waiters--

    // allocate

  if satisfied
    change.signal()
  else
    mutex.unlock()

release()
  mutex.lock()
    // deallocate
    if satisfied
      change.signal()
    else
      mutex.unlock()

Shortest-Job-Next Scheduling

Each allocation request includes an estimated use time.

Grant allocations in increasing order by use time.

Hang the waiters in a priority queue

struct qe { params ; semaphore wait(0) } queue<qe> wq semaphore mutex(1)

request(params, time) mutex.lock() if not satisfied(params) wq.push(time, qe(papams)) qe & me wq.top() mutex.unlock() me.wait.wait() wq.pop() // allocate if satisfied() wq.top().waiter.signal() else mutex.unlock()

release() mutex.lock() // deallocate if satisfied() change.signal() else mutex.unlock()

static satisfied() return not wq.empty() and satisfied(wq.front().params)

Points to Remember

Use mutex semaphores to implement mutual exclusion.
Use signaling semaphores to implement conditional synchronization.
Split-binary semaphores let you distinguish resource states.
- An empty or full producer-consumer buffer.
Use counting semaphores to keep track of resources.
- Multi-buffer producer-consumer synchronization.
Build on a correct solution to a simple problem.
- Several steps to a readers-writers solution.
Use baton passing to reduce the overhead of maintaining mutual exclusion.
- Make sure you actually maintain mutual exclusion, though.

This page last modified on 27 June 2003.