Concurrent Programming Class Notes

Lecture Notes for Concurrent Programming

24 June 2003 - Semaphores

Outline

Motivation
Description
Implementation
Reasoning
Semaphore Variations
- Counting Semaphores

Motivation

A critical section is a unit of coarse-grained synchronization.
- It implements a multi-statement atomic action.
A critical section is good at mutual exclusion, less good at conditional synchronization.
- Synchronization requires hopping in and out of the critical section.
Implementing critical sections for mutual exclusion is expensive.
- At user level, spin locks are inefficient.
- At system level, a general promise of mutual exclusion is usually too much.
Devise something to replace critical sections.
- Implement mutual exclusion or conditional synchronization.
- Be efficient to implement and use.

Description

Consider a stone in a bowl.
- A computation must take the stone to proceed past the bowl.
- A computation must wait for the stone if the bowl's empty.
- A computation must return to the bowl from which it came.

A binary semaphore is a stone in a bowl.

class semaphore 

  public:

    semaphore(bool init)

    void get()

    void put()

  private:

    bool available

Implementation

Take the stone, delaying until possible.

void semaphore::get()
  < await available ; available = false >

Put the stone back

void semaphore::put()
  available = true

Create a bowl with (possibly) a stone.
```
semaphore(bool a) 
  available = a
```
get() atomicity can be implemented with a critical section, or (more likely) by the host environment (language or operating system).
- put() may have to be atomic too.
It is useful to imagine a queue or set of waiting computations.

Reasoning

Axioms for put and get aren't helpful, because they involve private state.
- And they don't say much either.
It is more helpful to count the number of put()s and get()s.
- #s.get() is the number of completed get() calls made on semaphore s.
- Similarly for #s.put().
The global (or class) invariant for a binary semaphore is
```
0 <= #s.put() - #s.get() <= 1
```
- Mutual exclusion from binary semaphores follows immediately.
```
Computations in cr = #s.put() - #s.get()
```

Semaphore Variations

Semaphore features vary widely.
Semaphore operations.
- Conditional get()s.
```
bool try_get()
  < if available
    then available = false
         return true
    else return false >
```
- Return the number of waiting computations.
- Return the number of available stones.
Release behavior.
- Release a random waiter; release the oldest waiter; release the newest waiter; release the highest-priority waiter; release all waiters.
Gang-semaphore operations.
- Lock or release a set of semaphores atomically.
- Lock one-of-n semaphores.
- A condition variable is a specialization for two semaphores.

Counting Semaphores

A bowl can hold more than one stone.

A counting semaphore is a generalization of binary semaphores.

class counting_semaphore 

  public:

    semaphore(unsigned init = 0)
      cnt = init;

    void get()
      < await cnt > 0 ; cnt-- >

    void put()
      < cnt = cnt + 1 >

  private:

    // 0 <= #put() - #get() <= init

    unsigned cnt;

Counting semaphores do not provide mutual exclusion
- Unless init = 1;

Points to Remember

Semaphores provide greater generality than do critical regions.
- Equivalent mutual exclusion, simpler conditional synchronization.
Semaphores follow the metaphor of a stone in a bowl.
- But it's only a metaphor.
Semaphore implementations are efficient.
- Usually implemented in the host language or operating system.
Semaphore reasoning is based on operation count.
Make sure you understand the properties of the semaphores you use.

This page last modified on 1 July 2003.