Lecture Notes for Operating Systems Concepts

30 September 2002 - Concurrency

1. concurrent processing

   1. concurrency - several things happening "at the same time"

   2. multiprocessing - what's the big deal

   3. channel computers - coordination between the cpu and the channel cpus

   4. the coordinated execution of multiple processes

      1. easier design - large grain, narrow interfaces

      2. better performance - no waiting

      3. increased reliability - failure isn't final; easy replication

2. multiprocessors - true concurrency

   1. boss-worker

      1. coordination is simple but possibly inefficient

      2. reliability is fair to poor

      3. performance heavily dependent on task

   2. loosely-coupled

      1. coordination is somewhat complicated but more efficient

      2. reliability is good, but may be hard to achieve

      3. performance depends on task

   3. symmetric - smp

      1. coordination is similar to loosely-coupled systems; bandwidth is higher

      2. reliability is good, and is easier to achieve

      3. performance less dependent on task.

3. Process synchronization

   1. what's the problem

      1. consider the editor example

      2. unmediated access to shared information

   2. what's the solution

      1. control access to shared information

      2. mutual exclusion - at most one process accessing shared data at a time

      3. critical regions - an implementation of mutual exclusion

   3. simple minded boolean flags

   4. test and set

      1. a hardware solution - almost universally implemented

      2. inefficient due to spin waiting

   5. semaphores

      1. the stone in the bowl

   6. wait and signal

      1. signals aren't sticky - like phones without answering machines

4. patterns of process cooperation

   1. producer-consumer

      1. one-to-one, n-to-m

      2. one-way flow of information

   2. readers-writers

      1. a standard database problem

      2. readers read, writers write

      3. writers need exclusive access; readers can share

      4. no unnecessary delay, timely updates, no starvation

   3. barrier synchronization

      1. multi-phase tasks; each phase must be finished before the next starts

   4. pure synchronization - the sleeping barber

      1. essentially one-bit communication - stop-go

      2. no data are transfered, just state (which is data in some sense)

   5. general sharing - the dining philosophers

5. concurrency mechanisms programming languages

   1. abstracting operating systems features in a language, usually at a higher level

   2. ada

      1. tasks and rendezvous

   3. java

      1. threads and monitors (sorta)

This page last modified on 30 September 2002.