10: Lock and Condition Variables Design

OS Conceptual Framework

OS Conceptual Framework

Figure 1: OS Conceptual Framework

• physical addresses shared
  • processes and address translation
• CPU must be shared
  • threads
• processes aren’t trusted
  • kernel/user split
• threads might not cooperate
  • user timer interrupts to context switch

Correctness for Systems with Concurrency

A dispatcher can schedule thread in any way, programs must work under all circumstances.

• independent threads
  • no state shared with other threads
  • deterministic \(\Rightarrow\) input state determines results
  • reproducible \(\Rightarrow\) can recreate starting conditions, I/O
  • scheduling order doesn’t matter
• cooperating threads
  • shared state between multiple threads
  • non-deterministic
  • non-reproducible

Atomic Operations

Def. Atomic Operations: an operation that always runs to completion or not at all.

• it is indivisible: it cannot be stopped in the middle and state cannot be modified by someone else in the middle
• fundamental building block - if no atomic operations, then have no way for threads to work together

On most machines, memory references and assignments of words are atomic.

Many instructions are not atomic

• double-precision floating point store often not atomic
• VAX and IBM 360 had an instruction to copy a whole array

Some Definition

• Def. Synchronization: using atomic operations to ensure cooperation between threads
  • for now, only loads and stores are atomic
• Def. Mutual Exclusion: ensuring that only one thread does a particular thing at a time
  • one thread exclude the other while doing its task
• Def. Critical Section: piece of code that only one thread can execute at once
  • critical section is the result of mutual exclusion
  • critical section and mutual exclusion are two ways of describing the same thing
• Def. Lock: prevent someone from doing something
  • lock before entering critical section and before accessing shard data
  • unlock when leaving, after accessing shared data
  • wait if locked

Lock

Suppose we have some sort of implementation of a lock

• lock.Acquire() - wait until lock is free, then grab
• lock.Release() - unlock, waking up anyone waiting
• these must be atomic operations - if two threads are waiting for the lock and both see it’s free, only one succeeds to grab the lock

Three formal properties

• mutual exclusion: at most one thread holds the lock
• progress: if no thread holds the lock and any thread attempts to acquire the lock, then eventually some thread succeeds in acquiring the lock
• bounded waiting: if thread \(T\) attempts to acquire a lock, then there exists a bound on the number of times other threads can successfully acquire the lock before \(T\) does.
  • yet, it does not promise that waiting threads acquire the lock in FIFO order

Conditional Variable

Def. Conditional Variable: a queue of threads waiting for something inside a critical section.

• key idea: allow sleeping inside critical section by atomically releasing lock at time we go to sleep

Operations:

• wait(&lock): atomically release lock and go to sleep. Reacquire lock later, before returning
• signal(); wake up one waiter, if any
• broadcast(): wake up all waiters

Semaphores

Def. Semaphores are a kind of generalized lock.A semaphore has a non-negative integer value and supports the following two operations:

• P(): an atomic operation that waits for semaphore to become positive, then decrements it by 1
  • think of this as the wait() operation
• V(): an atomic operation that increments the semaphore by 1, waking up a waiting P, if any
  • think of this as the signal() operation

The Uses of Semaphores

1. mutual exclusion (initial value 1)
2. schedule constraints (initial value 0)
   • allow thread 1 to wait for a signal from thread 2, i.e., thread 2 schedules thread 1 when a given event occurs
   • example: suppose you had to implement threadjoin() which must wait for thread to terminate