Operating Systems Lecture Notes

30 January 2012 • Concurrency

---

Outline

• What is concurrency?
• Concurrency in action.
• OS concurrency.

What is Concurrency?

• Actions occurring “at the same time.”
  • Many philosophical (and physical) questions, all ignored.
• There are degrees of concurrency.
  • Concurrent, distributed, or parallel computations.
  • We’re going to ignore these distinctions.

From Where Does It Come?

• From real life; life is concurrent.
• From independent hardware components combined.
  • Disks, keyboards, network interfaces...

Why Concurrency?

• Any pretence at real life must handle concurrency somehow.
• Performance
  • If Joe mows the lawn in an hour, Joe and Fred together should mow the lawn in half an hour.
• Conceptual clarity.
  • Large-grained concurrency used judiciously can greatly simplify design.
  • Pipe-and-filter architectures.

Sequential Execution

• The alternative to concurrency is sequential execution.
  • “Sequential”: one thing at a time.
• Sequential execution is inefficient and annoying.
  • Inefficient: 1 activity source working, n - 1 activity sources idle.
  • Annoying: stop typing so the system can handle a tcp packet.
• It is, however, relatively simple.

Why Not Concurrency?

• Concurrency is hard to get right.
• The cost of getting it right can severely cut into the benefits.
  • The coordination overhead.
• Concurrency is a tough beast to tame and manage.
  • Concurrent code is obscure, fragile, and immiscible.

Concurrency Examples

• Three classic examples: shared-account withdrawals, dining philosophers, and santa claus.
• Although fanciful, these problems represent some fundamental concurrency problems.
  • There are many others too.
  • The sleeping barber, The byzantine generals, ...

Shared-Account Withdrawals

• A and B have a joint account and their own ATM cards.
• A withdraws $100.

  

Concurrent Withdrawals

• A and B both withdraw $100 “at the same time.”

  

Dining Philosophers

• N philosophers sit around a table; each philosopher has a plate and a fork to their left.
• A philosopher either eats or thinks, always alternating between the two independently of other philosophers.
• A philosopher eats infinite spaghetti, which requires two forks.

The Dining Philosophers’ Problem

• There are only enough forks for n/2 philosophers to eat at any time.
• What can the philosophers do to make sure that every philosopher eventually eat?
  • No philosopher should starve to death.
  • A philosopher can be delayed arbitrarily long waiting to eat.

Santa Claus

• When not busy, santa spends his time sleeping.
• If all nine reindeer awaken him, santa delivers toys.
• If any three of ten elves awaken him, santa consults on toy R&D.
• Santa always eventually goes back to sleep.

The Santa Claus Problem

• How can the elves and reindeer work so that
  • They can get to santa as quickly as possible.
  • Reindeer have priority over elves.
• Subject to the usual non-functional constraints: simplicity, efficiency, ...

The Problems Abstracted

• The two main forms of concurrency problems are
  1. Coordination: successfully sharing resources.
  2. Synchronization: making sure activities are arranged properly.
• Synchronization is the more basic problem.
  • Synchronization solutions can be used to provide coordination solutions.

Operating Systems Concurrency

• Operating (and hardware) systems are swimming in concurrency.
  • Various components (CPU, disk, network) represent independent activities.
  • The whole system is embedded in the world (keyboards, other systems, sensors).

Multiple CPUs

• Multiple CPUs is an obvious source of concurrency.
• Single CPU systems can get in on the game too.
  • This is where the operation system comes in.
• Concurrency becomes a resource provided by the OS.
  • The operating system first manufactures concurrency,
  • and then provides the tools to manage it.

The OS Task

• An OS has three main tasks with respect to concurrency:
  • Provide it to processes as a resource (or a service).
  • Provide mechanisms so processes can control concurrency.
  • Exploit concurrency within the OS to provide better performance.

Process Concurrency

• The process itself is the main aspect of process-visible concurrency
  • The process views itself as executing independently of all other processes.
• However, process concurrency is non-atomic.
  • The atomic part of concurrency is known as threads.

Concurrency Control

• The two main aspects of concurrency are coordination and synchronization.
• Coordination requires resources explicitly shared among processes.
  • Resources like files, shared memory, clip boards, and so on.
• Synchronization requires OS mechanisms to control process execution.
  • Routines to manipulate process priority, readiness to run.

OS Concurrency

• There can be orders of magnitude speed difference between hardware components
  • Disks delivering 10-200 mbytes/sec to a 2 gHz CPU.
• Concurrency is mandatory to avoid running the system at its slowest rate.
• An OS shares resources with itself, requiring self-synchronization.
  Asynchronous events can cause the OS to switch tasks at unpredictable times.

Summary

• Concurrency is a property of the real world, and makes it practical.
• Operating systems provides concurrency as a resource.
  • And exploit it in implementation.

References

• Concurrency, Chapter 8, in An Operating Systems Vade Mecum by Raphael Finkel, Prentice Hall, 1988.

---

This page last modified on 2012 January 30.