Module 4

COSC 4337 Operating System Notes

Cooperating Threads

Cooperating threads are allowed because:

• People cooperate, and computers enhance people's lives, thus computers must cooperate.

• Sharing resources:

  • One computer, many users.

  • One bank balance, many ATMs.

  • Embedded systems (robot control coordinating arm & hand).

• Speedup through overlapping I/O and computation.

  • Many file systems do read-ahead.

  • Multiprocessors can chop up a program into parallel pieces.

• Modularity by breaking large problems into simpler pieces.

  • Example: Compilation using gcc calls cpp | cc1 | cc2 | as | ld.

  • Makes the system easier to extend.

Goals for Synchronization

• Concurrency examples.

• The need for synchronization.

• Examples of valid synchronization.

• Hardware support for synchronization.

• Higher-level synchronization abstractions, such as semaphores, monitors, and condition variables.

• Classical problems of synchronization.

• Java synchronization.

Threaded Web Server

Multithreaded version:

serverLoop() {
    connection = AcceptCon();
    ThreadFork(ServiceWebPage(), connection);
}

Advantages of the threaded version:

• Can share file caches kept in memory, results of CGI scripts, and other resources.

• Threads are cheaper to create than processes, resulting in lower per-request overhead.

ATM Bank Server

ATM server problem: service a set of requests without corrupting the database or handing out too much money.

Threads for Easier Concurrency

Threads yield overlapped I/O and computation without "deconstructing" code into non-blocking fragments.

One thread per request allows requests to proceed to completion, blocking as required:

Deposit(acctId, amount) {
    acct = GetAccount(actId);  /* use I/O */
    acct->balance += amount;
    StoreAccount(acct);  /* disk I/O */
}

Withdraw(acctId, amount) {
    acct = GetAccount(actId);  /* use I/O */
    acct->balance -= amount;
    StoreAccount(acct);  /* disk I/O */
}

Shared State Corruption

Shared state can get corrupted due to concurrent access:

Thread 1           Thread 2
load r1, acct->balance   load r1, acct->balance
sub r1, amount2       add r1, amount1
store r1, acct->balance  store r1, acct->balance

Concurrent access to shared data may result in data inconsistency.

Lowest Level Problems

Most of the time, threads work on separate data, so scheduling doesn’t matter:

Thread A           Thread B
x = 1;             y = 2;

However, consider the following (initially, y = 12):

Thread A           Thread B
x = 1;             y = 2;
x = y+1;           y = y*2;

What are the possible values of x? 13, 3, or 5.

Atomic Operations

To understand a concurrent program, we need to know the underlying indivisible operations.

• Atomic Operation: an operation that always runs to completion or not at all.

  • It is indivisible: it cannot be stopped in the middle, and its state cannot be modified by someone else in the middle.

  • Fundamental building block – if there are no atomic operations, then threads have no way to work together.

$OP1 OP2 … OPn$

Atomic Operations (Cont.)

• On most machines, memory references and assignments (i.e., loads and stores) 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.

• Threaded programs must work for all interleavings of thread instruction sequences.

• Cooperating threads are inherently non-deterministic and non-reproducible.

• Really hard to debug unless carefully designed!

Race Condition

• Race condition: The situation where several processes access and manipulate shared data concurrently. The final value of the shared data depends upon which process finishes last.

• To prevent race conditions, concurrent processes must be synchronized.

Example: Therac-25

• Machine for radiation therapy.

• Software control of electron accelerator and electron beam/X-ray production.

• Software control of dosage.

• Software errors caused the death of several patients due to a series of race conditions on shared variables and poor software design.

• "They determined that data entry speed during editing was the key factor in producing the error condition: If the prescription data was edited at a fast pace, the overdose occurred."

Example: Space Shuttle

• Original Space Shuttle launch aborted 20 minutes before scheduled launch.

• Shuttle has five computers:

  • Four run the “Primary Avionics Software System” (PASS).

    • Asynchronous and real-time.

    • Runs all of the control systems.

    • Results synchronized and compared every 3 to 4 ms.

  • The Fifth computer is the “Backup Flight System” (BFS).

    • Stays synchronized in case it is needed.

    • Written by a completely different team than PASS.

• Countdown aborted because BFS disagreed with PASS.

  • A 1/67 chance that PASS was out of sync one cycle.

  • Bug due to modifications in initialization code of PASS.

  • A delayed init request placed into the timer queue.

  • As a result, the timer queue was not empty at the expected time to force the use of the hardware clock.

  • Bug not found during extensive simulation.

Another Concurrent Program Example

Two threads, A and B, compete with each other.

• One tries to increment a shared counter.

• The other tries to decrement the counter.

Thread A           Thread B
i = 0;             i = 0;
while (i < 10)     while (i > -10)
    i = i + 1;       i = i – 1;
printf(“A wins!”);   printf(“B wins!”);

Assume that memory loads and stores are atomic, but incrementing and decrementing are not atomic.

• Who wins? Could be either.

• Is it guaranteed that someone wins? Why or why not?

• What if both threads have their own CPU running at the same speed? Is it guaranteed that it goes on forever?

Process Synchronization (Chapter 6)

• The Critical-Section Problem

• Synchronization Hardware

• Semaphores

• Classical Problems of Synchronization

• Monitors

Motivation: “Too much milk”

• Great thing about OS’s – analogy between problems in OS and problems in real life.

  • Help you understand real life problems better.

  • But, computers are much stupider than people.

• Example: People need to coordinate:

Definitions

• Synchronization: using atomic operations to ensure cooperation between threads.

  • For now, only loads and stores are atomic.

  • We are going to show that it's hard to build anything useful with only reads and writes.

• Mutual Exclusion: ensuring that only one thread does a particular thing at a time.

  • One thread excludes the other while doing its task.

The Critical-Section Problem

• Critical Section: piece of code that only one thread can execute at once. Only one thread at a time will get into this section of code.

• Critical section is the result of mutual exclusion.

• Critical section and mutual exclusion are two ways of describing the same thing.

Solution to Critical-Section Problem

1. Mutual Exclusion. If a thread is executing in its critical section, then no other threads can be executing in their critical sections.

2. Progress. If no thread is executing in its critical section and there exist some threads that wish to enter their critical section, then the selection of the threads that will enter the critical section next cannot be postponed indefinitely.

3. Bounded Waiting. A bound must exist on the number of times that other threads are allowed to enter their critical sections after a thread has made a request to enter its critical section and before that request is granted.

   • Assume that each thread executes at a nonzero speed.

   • No assumption concerning the relative speed of the n threads.

More Definitions

• Lock: prevents someone from doing something.

  • Lock before entering the critical section and before accessing shared data.

  • Unlock when leaving, after accessing shared data.

  • Wait if locked.

• Important idea: all synchronization involves waiting.

• For example: fix the milk problem by putting a key on the refrigerator.

  • Lock it and take key if you are going to go buy milk.

  • Fixes too much: husband’s angry if only wants orange juice.

Too Much Milk: Correctness Properties

• Need to be careful about the correctness of concurrent programs since they are non-deterministic.

• Always write down behavior first.

  • Think first, then code.

• What are the correctness properties for the “Too much milk” problem???

  • Never more than one person buys.

  • Someone buys if needed.

• Restrict ourselves to using only atomic load and store operations as building blocks.

Too Much Milk: Solution #1

• Use a note to avoid buying too much milk:

  • Leave a note before buying (kind of "lock").

  • Remove the note after buying (kind of "unlock").

  • Don't buy if there's a note already (wait).

• Suppose a computer tries this (remember, only memory read/write are atomic):

if (noMilk) {
    if (noNote) {
        leave Note;
        buy milk;
        remove note;
    }
}

• Result? Still too much milk but only occasionally!

• The thread can get context-switched after checking the milk and note but before buying milk!

• The solution makes the problem worse since it fails intermittently.

• Makes it really hard to debug… Must work despite what the dispatcher does!

Too Much Milk: Solution #1½

• Clearly, the Note is not quite blocking enough. Let’s try to fix this by placing the note first.

• Another try at the previous solution:

leave Note;
if (noMilk) {
    if (noNote) {
        leave Note;
        buy milk;
    }
}
remove note;

• What happens here? With a human, probably nothing bad. But with a computer: no one ever buys milk.

Too Much Milk Solution #2

• How about labeled notes?

• Now we can leave a note before checking.

• Algorithm looks like this:

Thread A           Thread B
leave note A;       leave note B;
if (noNote B) {     if (noNoteA) {
    if (noMilk) {       if (noMilk) {
        buy Milk;           buy Milk;
    }
}                   }
remove note A;      remove note B;

• Does this work?

Too Much Milk Solution #2

• It's possible for neither thread to buy milk.

• Context switches at exactly the wrong times can lead each to think that the other is going to buy.

• This kind of lockup is called "starvation!"

  • Really insidious: extremely unlikely that this would happen but will at the worst possible time.

Too Much Milk Solution #3

Here is a possible two-note solution:

Thread A             Thread B
leave note A;        leave note B;
while (note B) {  //X
    if (noNote A) { //Y
        do nothing;       if (noMilk) {
                          buy milk;
        }
    }
                         if (noMilk) {
                         buy milk;
                         }
}
remove note B;       remove note A;

• Does this work? Yes. Both can guarantee that:

  • It is safe to buy, or

  • The other will buy, so it's ok to quit

• At X:

  • If no note B, safe for A to buy

  • Otherwise, wait to find out what will happen

• At Y:

  • If no note A, safe for B to buy

  • Otherwise, A is either buying or waiting for B to quit.

Solution #3 discussion

• Our solution protects a single “Critical-Section” piece of code for each thread:

if (noMilk)
    buy milk;

• Solution #3 works, but it’s really unsatisfactory.

  • Really complex – even for this simple an example.

  • Hard to convince yourself that this really works.

  • A’s code is different from B’s – what if lots of threads?

    • The code would have to be slightly different for each thread.

  • While A is waiting, it is consuming CPU time.

    • This is called “busy-waiting”.

• There’s a better way:

  • Have hardware provide better (higher-level) primitives than atomic load and store.

  • Build even higher-level programming abstractions on this new hardware support.

Too Much Milk: Solution #4

Suppose we have some sort of implementation of a lock (more in a moment).

• 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 in grabbing the lock.

• Then, our milk problem is easy:

milklock.Acquire();
if (nomilk)
    buy milk;
milklock.Release();

• Once again, the section of code between Acquire() and Release() is called a “Critical Section”.

• Of course, you can make this even simpler: suppose you are out of ice cream instead of milk. Skip the test since you always need more ice cream.

Synchronization: Where are we going?

We are going to implement various higher-level synchronization primitives using atomic operations.

• Everything is pretty painful if only atomic primitives are load and store.

• Need to provide primitives useful at user-level

Lock Implementation in Hardware

• Lock: prevents someone from doing something.

  • Lock before entering the critical section and before accessing shared data.

  • Unlock when leaving, after accessing shared data.

  • Wait if locked.

• Important idea: all synchronization involves waiting.

• Hardware Lock instruction.

  • Done in the Intel 432.

  • Each feature makes hardware more complex and slow.

• What about putting a task to sleep?

• How do you handle the interface between the hardware and scheduler?

Multi-Instruction Atomic Operations

How can we build multi-instruction atomic operations?

• Recall: the dispatcher gets control in two ways.

  • Internal: Thread does something to relinquish the CPU.

  • External: Interrupts cause dispatcher to take CPU.

• On a uniprocessor, can avoid context-switching by:

  • Avoiding internal events (although virtual memory is tricky).

  • Preventing external events by disabling interrupts.

• Consequently, a naive Implementation of locks:

LockAcquire { disable Ints; }
LockRelease { enable Ints; }

Problems with Interrupt Enable/Disable

• Can’t let the user do this! Consider the following:

LockAcquire();
while(TRUE) {;}

• Real-Time system—no guarantees on timing!

  • The critical section might be arbitrarily long.

• What happens with I/O or other important events?

  • “Reactor about to meltdown. Help?”

• Alternative: atomic instruction sequences.

  • These instructions read a value from memory and write a new value atomically.

Data Structure for Hardware Solutions

public class HardwareData {
    private boolean value = false;

    public HardwareData(boolean value) {
        this.value = value;
    }

    public boolean get() {
        return value;
    }

    public void set(boolean newValue) {
        this.value = newValue;
    }

    // Continued on Next Slide
}

public boolean getAndSet(boolean newValue) {
    boolean oldValue = this.get();
    this.set(newValue);
    return oldValue;
}

public void swap(HardwareData other) {
    boolean temp = this.get();
    this.set(other.get());
    other.set(temp);
}

Get-and-Set instruction

The important characteristic is that this instruction is executed atomically.

• If two Get-and-set instructions are executed simultaneously (each on a different CPU), they will be executed sequentially in some arbitrary order.

• We can implement mutual exclusion by declaring lock to be an object of class HardwareData and initializing it to be false.

Thread Using get-and-set Lock

// lock is shared by all threads
HardwareData lock = new HardwareData(false);

while (true) {
    while (lock.getAndSet(true))
        Thread.yield(); //busy waiting

    criticalSection();
    lock.set(false);
    nonCriticalSection();
}

Swap instruction

• Busy-Waiting: thread consumes cycles while waiting.

• The swap instruction operates on the contents of two words, being executed atomically.

• If the machine supports the swap instruction, then mutual exclusion can be provided as follows:

Thread Using swap Instruction

// lock is shared by all threads
HardwareData lock = new HardwareData(false);
// each thread has a local copy of key
HardwareData key = new HardwareData(true);

while (true) {
    key.set(true);
    do {
        lock.swap(key);
    } while (key.get() == true); //busy waiting

    criticalSection();
    lock.set(false);
    nonCriticalSection();
}

Problem: Busy-Waiting for Lock

Positives for this solution:

• The machine can receive interrupts.

• User code can use this lock.

• Works on a multiprocessor.

Negatives:

• This is very inefficient because the busy-waiting thread will consume cycles waiting.

• Waiting thread may take cycles away from the thread holding the lock (no one wins!).

• Priority Inversion: If the busy-waiting thread has a higher priority than the thread holding the lock  no progress!

Semaphores

A semaphore is a synchronization tool that does not require busy waiting.

• Semaphores are a kind of generalized lock.

• First defined by Dijkstra in the late 60s.

• The main synchronization primitive used in original UNIX.

• Definition: a Semaphore has a non-negative integer value (s) and supports the following two operations:

  • acquire() or P(): an atomic operation that waits for the semaphore to become positive, then decrements it by 1.
    Think of this as the wait() operation.

  • release() or V(): an atomic operation that increments the semaphore by 1, waking up a waiting P, if any.
    Think of this as the signal() operation.

  • Note that P() stands for “proberen” (to test) and V() stands for “verhogen” (to increment) in Dutch.

• Semaphores are like integers, except:

  • No negative values.

  • Only operations allowed are P and V – can’t read or write value, except to set it initially.

  • Operations must be atomic.

    • Two P’s together can’t decrement value below zero.

    • Similarly, a thread going to sleep in P won’t miss wakeup from V – even if they both happen at the same time.

Semaphore

Can only be accessed via two indivisible (atomic) operations

acquire(S) {
    while (S <= 0)  // no-op
        ;
    S--;
}

release(S) {
    S++;
}

Semaphore S; // initialized to 1

acquire(S);
criticalSection();
release(S);

Semaphores Like Integers Except

Semaphore from a railway analogy. Here is a semaphore initialized to 2 for resource control:

Two Uses of Semaphores

• Mutual Exclusion (initial value = 1)

  • Also called “Binary Semaphore”.

  • Can be used for mutual exclusion:

semaphore.P();
// Critical section goes here
semaphore.V();

• Scheduling Constraints (initial value = 0)

  • Locks are fine for mutual exclusion, but what if you want a thread to wait for something?

  • Example: Suppose you had to implement ThreadJoin which must wait for the thread to terminate

initial value of semaphore = 0

ThreadJoin {
    semaphore.P();
}

ThreadFinish {
    semaphore.V();
}

Semaphore as General Synchronization Tool

• Counting semaphore – integer value can range over an unrestricted domain.

• Binary semaphore – integer value can range only between 0 and 1; can be simpler to implement.

  • Also known as mutex locks.

  • Can implement a counting semaphore S as a binary semaphore.

Usage of Counting Semaphores

Counting semaphores can be used to control access to a given resource consisting of a finite number of instances.

• The semaphore is initialized to the number of resources available.

• Each thread that wishes to use a resource performs an acquire() operation on the semaphore

• When a thread releases a resource, it performs a release() operation.

• When the count for the semaphore goes to 0, all resources are being used.

Semaphore Implementation

The main disadvantage of the mutual-exclusion solutions and the previous semaphore just described is that they all require busy waiting.

• Loop continuously in the entry code – spinlock.

• Rather than busy waiting, the process block itself.

• The block operation places a process into a waiting queue associated with the semaphore, and the state of the process is switched to the waiting state.

Semaphore Implementation

acquire(S) {
    value--;
    if (value < 0) {
        add this process to list;
        block; // suspends the process
    }
}

release(S) {
    value++;
    if (value <= 0) {
        remove a process P from list;
        wakeup(P); // resume the execution
    }
}

Block and wakeup(P) are provided by the OS as basic system calls.

Deadlock

Deadlock – two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes.

Let S and Q be two semaphores initialized to 1.

P0                  P1
acquire(S);         acquire(Q);
acquire(Q);         acquire(S);
...
release(S);         release(Q);
release(Q)          release(S);

Starvation

Starvation – indefinite blocking. A process may never be removed from the semaphore queue in which it is suspended.

Indefinite blocking may occur if we add and remove processes from the list associated with a semaphore in LIFO order.

Summary

Concurrent threads are a very useful abstraction

• Allow transparent overlapping of computation and I/O.

• Allow the use of parallel processing when available.

Concurrent threads introduce problems when accessing shared data

• Programs must be insensitive to arbitrary interleavings.

• Without careful design, shared variables can become completely inconsistent.

Important concept: Atomic Operations

• An operation that runs to completion or not at all.

• These are the primitives on which to construct various synchronization primitives.

Summary

Showed how to protect a critical section with only atomic load and store  pretty complex!

• Talked about hardware atomicity primitives:

  • Disabling of interrupts, test&set, swap, comp&swap, load-linked/store conditional.

• Showed several constructions of Locks.

  • Must be very careful not to waste/tie up machine resources.

    • Shouldn’t disable interrupts for long.

    • Shouldn’t spin wait for long.

  • Key idea: Separate lock variable, use hardware mechanisms to protect modifications of that variable.

Classical Problems of Synchronization

• Bounded-Buffer Problem

• Readers and Writers Problem

• Dining-Philosophers Problem

Bounded-Buffer Problem

public class BoundedBuffer implements Buffer {
    private static final int BUFFER_SIZE = 5;
    private Object[] buffer;
    private int in, out;
    private Semaphore mutex;
    private Semaphore empty;
    private Semaphore full;

    // Continued on next Slide
}

Bounded Buffer Constructor

public BoundedBuffer() {
    // buffer is initially empty
    in = 0;
    out = 0;
    buffer = new Object[BUFFER_SIZE];
    mutex = new Semaphore(1);
    empty = new Semaphore(BUFFER_SIZE);
    full = new Semaphore(0);
}

public void insert(Object item) { /* next slides */ }

public Object remove() { /* next slides */ }

Bounded Buffer Problem: insert() Method

public void insert(Object item) {
    empty.acquire();
    mutex.acquire();
    // add an item to the buffer
    buffer[in] = item;
    in = (in + 1) % BUFFER_SIZE;
    mutex.release();
    full.release();
}

Bounded Buffer Problem: remove() Method

public Object remove() {
    full.acquire();
    mutex.acquire();
    // remove an item from the buffer
    Object item = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
    mutex.release();
    empty.release();
    return item;
}

Bounded Buffer Problem: Producer

import java.util.Date;

public class Producer implements Runnable {
    private Buffer buffer;

    public Producer(Buffer buffer) {
        this.buffer = buffer;
    }

    public void run() {
        Date message;
        while (true) {
            // nap for awhile
            SleepUtilities.nap();
            // produce an item & enter it into the buffer
            message = new Date();
            buffer.insert(message);
        }
    }
}

Bounded Buffer Problem: Consumer

import java.util.Date;

public class Consumer implements Runnable {
    private Buffer buffer;

    public Consumer(Buffer buffer) {
        this.buffer = buffer;
    }

    public void run() {
        Date message;
        while (true) {
            // nap for awhile
            SleepUtilities.nap();
            // consume an item from the buffer
            message = (Date) buffer.remove();
        }
    }
}

Bounded Buffer Problem: Factory

public class Factory {
    public static void main(String args[]) {
        Buffer buffer = new BoundedBuffer();
        // now create the producer and consumer threads
        Thread producer = new Thread(new Producer(buffer));
        Thread consumer = new Thread(new Consumer(buffer));
        producer.start();
        consumer.start();
    }
}

Readers-Writers Problem

A data object (such as a file, a database) is to be shared among several concurrent processes.

• Some processes (readers) may want only to read the content of the shared object, whereas others (writers) may want to update (read and write) the shared object.

• If two readers access the shared data object simultaneously, no adverse effects will result. However, if a writer and some other process (either a reader or writer) access the shared object simultaneously, chaos may ensue.

Readers-Writers Problem

Shared data

semaphore mutex, db;

Initially mutex = 1, db = 1, readercount = 0.

Readers-Writers Problem

• The first readers-writers problem requires that no reader will be kept waiting unless a writer has already obtained permission to use the shared database.

• The second readers-writers problem requires that once a writer is ready, that writer performs its write as soon as possible.

• A solution to either problem may result in starvation.

• Next is a solution to the first problem

The First Readers-Writers Problem: Reader

public class Reader implements Runnable {
    private RWLock db;

    public Reader(RWLock db) {
        this.db = db;
    }

    public void run() {
        while (true) {
            SleepUtilities.nap(); //nap for awhile
            db.acquireReadLock();
            // you now have access to read from the database
            SleepUtilities.nap();
            db.releaseReadLock();
        }
    }
}

Readers-Writers Problem: Writer

public class Writer implements Runnable {
    private RWLock db;

    public Writer(RWLock db) {
        this.db = db;
    }

    public void run() {
        while (true) {
            SleepUtilities.nap(); //nap for awhile
            db.acquireWriteLock();
            // you have access to write to the database
            SleepUtilities.nap();
            db.releaseWriteLock();
        }
    }
}

Readers-Writers Problem: Interface

public interface RWLock {
    public abstract void acquireReadLock();

    public abstract void acquireWriteLock();

    public abstract void releaseReadLock();

    public abstract void releaseWriteLock();
}

Readers-Writers Problem: Database

public class Database implements RWLock {
    private int readerCount;
    private Semaphore mutex;
    private Semaphore db;

    public Database() {
        readerCount = 0;
        mutex = new Semaphore(1);
        db = new Semaphore(1);
    }

    public int acquireReadLock() { /* next slides */ }

    public int releaseReadLock() { /* next slides */ }

    public void acquireWriteLock() { /* next slides */ }

    public void releaseWriteLock() { /* next slides */ }
}

Readers-Writers Problem: Methods Called by Readers

public void acquireReadLock() {
    mutex.acquire();
    ++readerCount;
    // if I am the first reader tell all others
    // that the database is being read
    if (readerCount == 1)
        db.acquire();
    mutex.release();
}

public void releaseReadLock() {
    mutex.acquire();
    --readerCount;
    // if I am the last reader tell all others
    // that the database is no longer being read
    if (readerCount == 0)
        db.release();
    mutex.release();
}

Readers-Writers Problem: Methods called by writers

public void acquireWriteLock() {
    db.acquire();
}

public void releaseWriteLock() {
    db.release();
}

Readers-Writers Problem

Read-write locks are most useful in the following situations:

*