Readers, Writers and Deadlock

Readers/Writers Problem

Motivation: Consider a shared database.

• Two classes of users:
  • Readers - never modify database.
  • Writers - read and modify database.

Is using a single lock on the whole database sufficient?

• Like to have many readers at the same time.
• Only one writer at a time.

Basic Readers/Writers Solution

• Correctness Constraints:
  • Readers can access database when no writers.
  • Writers can access database when no readers or writers.
  • Only one thread manipulates state variables at a time.
• Basic structure of a solution:
  • Reader()
    • Wait until no writers
    • Access database
    • Check out - wake up a waiting writer
  • Writer()
    • Wait until no active readers or writers
    • Access database
    • Check out - wake up waiting readers or writers
  • State variables (protected by a lock called “lock”)
    • int AR: Number of active readers; initially = 0
    • int WR: Number of waiting readers; initially = 0
    • int AW: Number of active writers; initially = 0
    • int WW: Number of waiting readers; initially = 0
    • Condition okToRead = NIL
    • Condition okToWrite = NIL

For reader

Reader() {
    lock.Acquire();
    while ((AW + WW) > 0) {
        WR++;
        okToRead.wait(&lock)
        WR--;
    }
    AR++;
    lock.Release();

    AccessDatabase();

    lock.Acquire();
    AR--;
    if (AR == 0 && WW > 0) okToWriter.signal();
    lock.Release();
}

For writer

Writer() {
    lock.Acquire();
    while ((AR + AW) > 0) {
        WW++;
        okToWrite.wait(&lock)
        WW--
    }
    AW++;
    lock.Release();

    AccessDatabase();

    lock.Acquire();
    AW--;
    if (WW > 0) {
        okToWrite.signal();
    } else {
        okToRead.broadcast();
    }

    lock.Release();
}

Now we wrad the code into a RWlock class.

class RWLock {
    Lock lock;
    CV canRead; // okToRead
    CV canWrite; // okToWrite
}

void RWLock::startRead() {
    lock.Acquire()
    WR++;
    while ((AW + WW) > 0) {
        canRead.wait(&lock);
    }
    WR--;
    AR++;
    lock.Release();
}

void RWLock::doneRead() {
    lock.Acquire()
    AR--;
    if (AR == 0 && WW > 0) canWrite.signal();
    lock.Release();
}

void RWLock::startWrite() {
    lock.Acquire();
    WW++;
    while ((AW + AR) > 0) {
        canWrite.wait(&lock);
    }
    WW--;
    AW++;
    lock.Release();
}

void RWLock::doneWrite() {
    lock.Acquire();
    AW--;
    assert(AW == 0);
    if (WW > 0) canWrite.signal();
    else canRead.broadcast();
    lock.Release();
}

Deadlock

Def. Deadlock A cycle of waiting among a set of threads, where each thread waits for some other thread in the cycle to take some action.

If a deadlock occurs, it can be resolved if one thread backs up preempt resources and rollback.

Deadlocks occur with multiple resources. Means you cannot decompose the problem. Cannot solve deadlock for each resource independently.

Four Requirements for Deadlock

1. Mutual exclusion
   • Only one thread at a time can use a resource.
2. Hold and wait
   • Thread holding at least one resource is waiting to acquire additional resources held by other thread.
3. No preemption
   • Resources are released only voluntarily by the thread holding the resource, after thread is finished with it.
4. Circular wait
   • There exists a set \(\{T_1, T_2, \cdots, T_n\}\) of waiting threads.
   • \(T_i\) is waiting for a resource that is held by \(T_{i + 1}\).

Methods for Handling Deadlocks

1. Allow system to enter deadlock and then recover
   • Requires deadlock detection algorithm.
   • Som technique for forcibly preempting resources and/or terminating tasks.
2. Ensure that system will never enter a deadlock.
   • Need to monitor all lock acquisitions.
   • Selectively deny those that might lead to deadlock.
3. Ignore the problem and pretend that deadlocks never occur in the system.
   • Used by most operating systems, including UNIX.

Preventing Deadlocks

Removing circular wait

Just make sure all locks acquired in the same order.

• Total ordering.
• Partial ordering.

e.g. We can enforce lock ordering by lock address.

Preventing Hold and Wait

Just use another lock to lock the locks.

Lock globalLock; // 额外的全局锁

void thread_func() {
    globalLock.acquire();      // 先获得全局锁
    L1.acquire();              // 再获得所有需要的资源锁
    L2.acquire();
    globalLock.release();      // 释放全局锁

    // 临界区操作
    // ...

    L2.release();
    L1.release();
}

Cons: must know which locks will be used beforehand; concurrency decreased.

Preventing Mutual Exclusion

Design lock-free (or wait-free) data structures and algorithms using powerful hardware instructions.

int CompareAndSwap(int *address, int expected, int new) {
    if (*address == expected) {
        *address = new;
        return 1; // success
    }
    return 0; // failure
}

Using CompareAndSwap to implement “increment a value by \(n\)”.

void AtomicIncrement(int *value, int n) {
    do {
        int old = *value;
    } while (CompareAndSwap (value, old, old + n) == 0);
}

Using CompareAndSwap to implement “insert an element to a list head”.

// without deadlock prevention
void insert(int value) {
    node_t *n = malloc(sizeof(node_t));
    assert(n != NULL);
    n -> value = value;
    n -> next = head;
    head = n;
}

// with deadlock prevention
void insert(int value) {
    node_t *n = malloc(sizeof(node_t));
    assert(n != NULL);
    n -> value = value;
    do {
        n -> next = head;
    } while (CompareAndSwap(&head, n -> next, n) == 0);
}

Cons: too complicated; hardware support needed (possibly performance degradation).

Smart Scheduling

Def. Resource-Allocation Graph

• System Model
  • A set of Threads \(\{T_1, T_2, \cdots, T_n\}\).
  • Resource types \(\{R_1, R_2, \cdots, R_m\}\)
    • CPU cycles, memory space, I/O devices.
  • Each resource type \(R_i\) has \(W_i\) instances.
  • Each thread utilizes a resource as follows:
    • Request() / Use() / Release().
• Resource-Allocation Graph:
  • V is partitioned into two types:
    • \(T = \{T_1, T_2, \cdots, T_n\}\), the set threads in the system.
    • \(R = \{R_1, R_2, \cdots, R_m\}\), the set of resource types in system.
  • Request edge - directed edge \(T_i \to R_j\).
  • Assignment edge - directed edge \(R_{j} \to T_{i}\).

Resource Allocation Graph Examples

Figure 1: Resource Allocation Graph Examples

Algorithm - Deadlock Detection.

• Only one of each type of resource \(\Rightarrow\) look for loops.
• More General Deadlock Detection Algorithm

  • Let [X] represent an m-ary vector of non-negative integers (quantities of resources of each type):

  • See if tasks can eventually terminate on their own

    [Avail] = [FreeResources]
    Add all nodes to UNFINISHED
    do {
        done = true
        Foreach node in UNFINISHED {
            if ([Request_{node}] <= [Avail]) {
                remove node from UNFINISHED
                [Avail] = [Avail] + [Alloc_{node}]
                done = false
            }
        }
    } until (done)

  • Nodes left in UNFINISHED \(\Rightarrow\) deadlocked.

What to do when detect deadlock?

• Terminate thread, force it to give up resources.

  • But, not always possible - killing a thread holding a mutex leaves world inconsistent.

• Preempt resources without killing off thread

  • Take away resources from thread temporarily.
  • Doesn’t always fit with semantics of computation.

• Roll back actions of deadlock threads

• Many operating systems use other options.

Bankers Algorithm

• What if you don’t know the order/amount of requests ahead of time?

• Must assume some worst-case “max” resource needed by each process.

• Toward right idea.

  • State maximum resource needs in advance.
  • Allow particular thread to proceed if: (available resources - #requested) \(\geq\) max remaining that might be needed by any thread.
  • Invariant: At all times, every request would succeed.

Algorithm - Bankers Algorithm.

• Invariant: At all times, there exists some order of requests that would succeed.

• Key ideas:

  • A thread states its maximum resource requirements, but acquires and releases resources incrementally as the thread executes.
  • The runtime system delays granting some requests to ensure that the system never deadlock.

• Safe state: For any possible sequence of resource requests, there is at least one safe sequence of processing the requests that eventually succeeds in granting all pending and future requests.
  • A system in a safe state controls its own destiny: for any workload, it can avoid deadlock by delaying the processing of some requests.
• Unsafe state: There is at least one sequence of future resource requests that leads to deadlock no matter what processing order is tried.
  • An unsafe state does not always lead to deadlock.
  • However, as long as the system remains in an unsafe state, a bad workload or unlucky scheduling of requests can force it to deadlock.
• Deadlocked state: The system has at least one deadlock.

The banker’s algorithm delays any request that takes it from a safe to an unsafe state.

How to implement this ?

• Allocate resources dynamically.
  • Evaluate each request and grant if some ordering threads is still deadlock free afterward.
  • Use deadlock detection algorithm presented ealier.
    • But assume each process needs “max” resources to finish.

    [Avail] = [FreeResources]
    Add all nodes to UNFINISHED
    do {
        done = true
        Foreach node in UNFINISHED {
            if ([MAX_{node}] - [Alloc_{node}] <= [Avail]) {
                remove node from UNFINISHED
                [Avail] = [Avail] + [Alloc_{node}]
                done = false
            }
        }
    } until (done)

• Keep system in a safe state, i.e. there exists a sequence \(\{T_1, T_2, \cdots, T_n\}\) with \(T_{1}\) requesting all remaining resources, finishing, then \(T_2\) requesting all remaining resources, etc….

• vs. “Require all before starting”, the Banker’s algorithm allows the sum of maximum resource needs of all current threads to be greater than total resources.

Example. Page Allocation with the Banker’s Algorithm Suppose we have a system with \(8\) pages of memory and three processors: A, B, and C, which need \(4\), \(5\) and \(5\) pages to complete, respectively.

Process	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
A	0	1	1	1	2	2	2	3	3	3	4	0	0	0	0	0	0	0	0
B	0	0	1	1	1	2	2	2	wait	wait	wait	wait	3	4	4	5	0	0	0
C	0	0	0	1	1	1	2	2	2	wait	wait	wait	3	3	wait	wait	4	5	0
Total	0	1	2	3	4	5	6	7	7	7	8	4	6	7	7	8	4	5	0

Table 1: Banker’s Algorithm Process