Operating Systems Lecture Notes

2014 September 30 • Concurrency

---

Outline

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

What is Concurrency?

• Events occurring “at the same time.”
  • Many philosophical (and physical) questions, all ignored.
• There are degrees of concurrency.
  • Parallel, concurrent, or distributed computations.
  • Ignore these distinctions.
  • Or rather, focus on concurrent computations.

From Where Does It Come?

• From real life; life is concurrent.
• From independent hardware components combined.
  • Disks, keyboards, network interfaces...
• From increased utilization.
  • Virtual resources as multiplexed entities.

Why Concurrency?

• Any pretense at real life must handle concurrency.
• 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.

Sequential Example

Given	a single thread does
int find(a[], x) for i = 1 to |a| if a[i] ≡ x return i return -1	i = 0 if i > |a|, break if a[i] ≡ x, return i i = i + 1 if i > |a|, break if a[i] ≡ x, return i i = i + 1 if i > |a|, break if a[i] ≡ x, return i i = i + 1 if i > |a|, break
	\(\vdots\)

Concurrent Example

Given find(), two threads do
t1	t2
i = 0 if i > |a|, break if a[i] ≡ x, return i i = i + 1 if i > |a|, break if a[i] ≡ x, return i i = i + 1 if i > |a|, break if a[i] ≡ x, return i i = i + 1 if i > |a|, break if a[i] ≡ x, return i	i = 0 if i > |a|, break if a[i] ≡ x, return i i = i + 1 if i > |a|, break if a[i] ≡ x, return i i = i + 1 if i > |a|, break if a[i] ≡ x, return i
\(\vdots\)	\(\vdots\)

Fake Concurrency Example

Given find() and one execution engine, threads t1 and t2 do

i = 0 if i > |a|, break if a[i] ≡ x, return i i = 0 if i > |a|, break i = i + 1 if i > |a|, break if a[i] ≡ x, return i i = i + 1 if i > |a|, break if a[i] ≡ x, return i i = i + 1 if a[i] ≡ x, return i

\(\vdots\)

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.
  • The sleeping barber, Byzantine generals, readers-writers problem, ...

Shared-Account Withdrawals

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

  

Concurrent Withdrawals

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

  

• What account management can prevent this?

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 eats?
  • No philosopher should starve to death.
  • A philosopher can wait arbitrarily long to eat, but should eventually eat.

Santa Claus

• When not busy, Santa is sleeping.
• If all nine reindeer wake him, Santa delivers toys.
• If any three of ten elves wake 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.

Producers and Consumers

• Given the globals (a circular queue)

  widget q[N]
  q-size = 0
  head = tail = 0
  

  and the two functions

  p() loop w = f() while q-size ≡ N {} q[tail++] = w ++q-size

  c() loop while q-size ≡ 0 {} w = q[head++] --q-size g(w)

  run p() and c() in separate threads.

Producer-Consumer Architecture

Producer-Consumer Execution

p()	c()
w = f() q-size ≡ N q[tail++] = w ++q-size w = f() q-size ≡ N q[tail++] = w ++q-size w = f() q-size ≡ N q[tail++] = w ++q-size w = f() q-size ≡ N	q-size ≡ 0 w = q[head++] --q-size g(w) q-size ≡ 0 w = q[head++] --q-size g(w) q-size ≡ 0 w = q[head++] --q-size
\(\vdots\)	\(\vdots\)

Sharing and Conflict

• Unlike find(), concurrency causes problems for p() and c().
  • Concurrency and shared variables.
• Note head and tail are shared, but not really.
  • Only p() uses tail; only c() uses head.
• p() and c() use q, but not without conflicts.
  • Why?
• The problem comes from q-size.

A Closer Look

• How are prefix ++ and -- implemented?

  --q-size:	++q-size:
  get ri, @q-size sub ri, 1 put ri, @q-size	get ri, @q-size add ri, 1 put ri, @q-size

• Ignore the expression return value.
• Remember registers are per-thread state.

Concurrent Prefix Operations

p()	c()
get ri, @q-size add ri, 1 put ri, @q-size get ri, @q-size add ri, 1 put ri, @q-size get ri, @q-size add ri, 1 put ri, @q-size	get ri, @q-size sub ri, 1 put ri, @q-size get ri, @q-size sub ri, 1 put ri, @q-size get ri, @q-size sub ri, 1
\(\vdots\)	\(\vdots\)

The Sequential View

get ri, @q-size get ri, @q-size sub ri, 1 put ri, @q-size add ri, 1 put ri, @q-size get ri, @q-size sub ri, 1 get ri, @q-size add ri, 1 put ri, @q-size put ri, @q-size	p() and c() execute in multiplexed concurrency. p() and c() interfere with each other when setting q-size’s value. The problem is uncoordinated read and write access to shared state.
\(\vdots\)

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

• The Architecture of Concurrent Programs by Per Brinch Hansen from Prentice-Hall, 1977.
• Parallel Program Design by K. Mani Chandy and Jayadev Misra from Addison-Wesley, 1988.
• Concurrent Programming in ML by John Reppy from Cambridge University Press, 1999.

---

This page last modified on 2014 September 30.