TODO Merge this into the correct chapters.

Semaphore Implementation with no Busy Waiting

TODO

Typedef struct {
    int value;
    struct process *list;
    } semaphore;

wait(semaphore *S) {
    S -> value--;
    if (S -> value < 0) {
        // add this process to S -> list
        sleep();
    }
}

signal(semaphore *S) {
    if (S -> value <= 0) {
        // remove process from S -> list
        wakeup(P);
    }
}

Basic system calls used:

• sleep(): suspend process that invokes it.
• wakeup(); resume execution of suspended process.

Issues with Semaphores

Incorrect use of sempahore operations can cause deadlock and starvation.

Example: Misusing Semaphores

Interchanging Order

TODO

Replaces signal with wait

TODO

omits signal, wait, or both

TODO

Monitors

High-level ADT that encapsulates data along with functions though which the data may be accessed and manipulated

• High-level synchronization primitive implemented using P and V operations.
• Not powerful enough to model some synchronization schemes.

Purpose: Guarantee mutual exclusion.

• Avoids lockout, deadlock, and starvation.

monitor monitor_name
{
    // shared vars
    procedure P1 (...) {...}
    ...
    procedure Pn (...) {...}
        initialization code (...) {...}
}

Deadlock & Starvation

Deadlock: Two or more processes wait indefinitely for an event that can only be caused by only one of the waiting processes.

Starvation: Indefinite blocking

• A process may never be removed from the semaphore queue in which it is suspended.

Priority Inversion: Scheduling problem when lower-priority process holds a lock needed by a higher-priority process.

• Solved by priority-inheritance protocol

Indivisibility: When we say a critical section must be indivisibly/atomically, we are talking about the code which holds and releases the lock.

• The critical section itself can be big and doesn’t need to be done in a single cycle, it can be preempted safely (though, this can lead to starvation).

Priority Inversion Protocol: We temporarily assign the highest priority to the process currently executing in its critical section to prevent it getting starved.

Classical Problems of Synchronization

Bounded Buffer Problem

Suppose you have n buffers, each can hold one item.

• Semaphore mutex initialized to the value 1 (no process in critical section).
• Semaphore full initialized to 1.
• Semaphore empty initialized to n.

TODO Code

do {
    ...
    // produce iteme
    ...

}

Producer:

• wait(empty): empty will inform us if there is space
• wait(mutex): Will inform us if we can write.
• signal(mutex): Release lock.
• signal(full): Increments full.

Consumer:

• wait(full): Informs us if there is space.
• wait(mutex): Can we write?

TODO Increment and decrement rules?

Idea? — To prevent deadlock, we have each process manage a dedicated boolean? notfull and notempty? How does that owrk?

Readers and Writers

In this problem, a dataset if shared among a number of concurrent processes.

• Readers: Only read the dataset (they don’t update it).
• Writers: Can read and write.

Problem: How do you let multiple readers read at the same time?

• Only one writer can access the shared data at the same time.

Variations:

• First: No reader kept waiting unless writer has permission to use shared object.
  • In other words, no reader needs to wait for other readers to finish simply because a writer is waiting.
  • Favor readers (starves writer)
• Second: Once writer is ready, it does the write ASAP.
  • In other words, if a writer is waiting to access the object, no new readers may begin reading.
  • Favor writers (starves readers)

Note — Both may have starvation, leading to even more variations.

• On some systems, the kernel provides reader/writer locks to resolve this.

Solution to First Variation

Shared Data:

• Semaphore: rw_mutex
  • Checked by the writer, first reader, and last reader.
• Semaphore: mutex
  • Checked by all readers. For mutual exclusion when updating read_count.
• Integer: read_count
  • Lets a reader know if it’s the first or last reader.

The idea basically, is the first reader will check if it’s safe to get into the CS (wait(rw_mutex)). After this, all the readers won’t have to wait for the rw_mutex, they’ll only ever wait to update the read_count. The last reader will release the lock and allow the writer to do its thing again.

• This blurb is useless. Will rethink and repurpose into code example.

TODO Code

Solution via Monitor

Suppose you have a monitor:

TODO Define reader-writer Monitor

Dining Philosophers

Problem

Philosophers spend their lives alternating between thinking and eating.

• They don’t interact with their neighbors and occasionally try to pick up two chopsticks (only from their left or right side) to eat.
  • They need two chopsticks to eat.

In the case of 5 philosophers sitting in a circle (with a single chopstick in-between each):

• Shared data: Bowl of rice (data set), semaphore (chopstick[5]) initialized to 1

Issue: If every philosopher picks up a chopstick, they will get into deadlock.

Naive “Solution”

One naive “solution” is to represent each chopstick with a semaphore.

• Philosophers call wait on the chopsticks on their right and left side.

    semaphore chopstick[5];
    loop {
        // Wait
        wait(chopstick[i]); // (left)
        wait(chopStick[(i \text{$+$} 1) % 5]); // (right)
            // eat...

        // Release
        signal(chopstick[i]);
        signal(chopStick[(i \text{$+$} 1) % 5]);
            // think...
    }

Problem: If every single philosopher grabs their left chopstick at once (this is valid), this’ll result in deadlock.

/s — Unrelated, but one optimization is to put “think” at the start of the loop so that the philosophers think before they wait. But personally I don’t want them to think on an empty stomache.

Some Solutions

1. Allow at most four philosophers to be sitting simultaneously at the table.

2. Make the act of picking up both chopsticks a critical section (e.g., wrap in mutex).

  semaphore chopstick[5];
  loop {
      // Wait
      P(mutex);
      wait(chopstick[i]); // (left)
      wait(chopStick[(i \text{$+$} 1) % 5]); // (right)
      V(mutex);
          // eat...

      // Release
      signal(chopstick[i]);
      signal(chopStick[(i \text{$+$} 1) % 5]);
          // think...
  }

  semaphore chopstick[5];
  loop {
      // Wait
      P(wait(chopstick[min(i, (i \text{$+$} 1) % 5]);
      P(wait(chopstick[max(i, (i \text{$+$} 1) % 5]);
          // eat...

      // Release
      signal(chopstick[i]);
      signal(chopStick[(i \text{$+$} 1) % 5]);
          // think...
  }

3. Asymmetric; odd-numbered philosophers pick up left-then-right chopstick, evens vice-versa.

4.

Deadlock

When a process is waiting for something that’ll never happens.

Deadlock arises if four conditions hold simultaneously:

1. Mutual Exclusion: Only one process at a time can use a resource.
2. Hold and Wait: A process holds one process, and waits for another resource(s) to be available.
3. No Preemption: A resource can only by release voluntarily by the process holding it.
4. Circular Wait: There exists at set { P_0,P_1,...,P_n } of waiting processes such that P_0 is waiting for a resource held by P_1, P_1 is waiting for a resource held by P_2, etc.

Example — Dining Philosophers demonstrates all four properties.

Resource Allocation Graph

Set of vertieces V and edges E.

• Two types of verticies:
  • P:
  • R:

Example TODO

Deadlock Detection

If a resource allocation graph has a cycle, it may have a deadlock, specifically:

• Only one instance per resource type: Deadlock
• Several instances per instance type: Possible Deadlock

TODO Graphs

Handling Deadlock

1. Ensure system doesn’t get deadlocked
   • Deadlock prevention
   • Deadlock avoidance.
2. Allow system to enter deadlock, detect it, and recover from it.
3. Ignore problem and pretend deadlocks never occur.
   • Leave it to the programmer to handle deadlocks.

Real-World: #3 is used by most systems (UNIX, Windows, and Linux).

If we can break any of the four conditions, we can prevent deadlocks.

• We do this by restraining the way requests can be made.

1. Breaking Mutual Exclusion: Make this not-required for shareable resources (e.g., read-only files).
   • In general, we can’t actually break deadlocks this way, as stuff like mutex locks cannot be shared.
2. Breaking Hold and Wait: Guarantee that when a process requests a resource, it doesn’t hold any other resources.
   1. Method 1: Process must request and be allocated all its resources before it begins execution, or
   2. Method 2: Process can only request resources when it has none allocated to it (e.g., it must deallocate before it can request more)
3. Breaking No Preemption: If a process is holding some resources and request another resource that cannot be immediately allocated, all its resources are released.
   • Process will only restart once it can regain its old resources and the new ones it’s requesting.
4. Breaking Circular Wait: Impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration.
   • Proof by contradiction shows this guarantee no deadlock, and it’s also a practical solution.
   • There are many algorithms that work by trying to break circular waits.

More on Issues:

• Hold and Wait: Low resource utilization, starvation.
• Preemption: This is applied to resources whose states can be easily saved and restored, like CPU registers and memory. But, it can’t be applied to resources like mutex locks and semaphores.

Deadlock Avoidance

Requests that the system has some additional a priori information available.

Simplest and most-useful model: Each process must declare the maximum number of resources of each type that it may need.

• The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure there is never a circular wait.
• Resource-allocation state is defined by:
  1. Number of available resources,
  2. Number of allocated resources, and
  3. Maximum demands of the processes.

Basically, we must be careful when allocating resources, to prevent circular waits.

On Safe State:

• Safe State: When the system can allocate resource to each process (up to its maximum) in some order and avoid deadlock.

Avoidance Algorithms

Resource Allocation Graph

Use: Single-instances of resources.

TODO Drawing of Resource Allocation Graph with Claim Edge.

We introduce the claim edge, which says a process will use a process in the future.

• This means that resoures must be claimed a priori in the system.

On Behavior:

• A process request to use its claim at any time, which converts the claim edge into a request edge.
• When a request is served, it is converted to an assignment edge.
• Likewise, when a resource is released, the assignment edge reconverts to a claim.

Central Idea — Requests to convert request edges to assignment edges are only served if they don’t result in the formation of a cycle.

Bankers Algorithm

Use: Multiple-instances of resources.

When a process gets all its resources, it must return them in a finite amount of time.

• Like before, processes must claim maximum use a priori, and may have to wait for a request to be served.

Data Structure: We use an array and three n \times m matrices to do banker’s algorithm.

• Available: Vector of length m. If available[j]=k, there are k instances of resource type R_j available.
• Max: If Max[i,j] = k, then process P_i can request at most k instances of resource type R_j.
• Allocation: TODO
• Need: TODO
  • This is merely Max - Allocation (TODO

TODO Algorithm, described using data structure.

Baically, every time a request is made, we run a huge calculation to see if this would leave us in a safe state.

• If we have the resources to fulfill a request that’d result in a process getting its Max, we assume that process finishes and deallocates all of its held resources. TODO
• All we are checking for, “can we finish all these processes”

TODO

TODO Wait-for graph? Detecting Deadlock??

Recovering from Deadlock

Abort Deadlocked Processes

Danger — Aborting a process, especially in its critical section, is dangerous (e.g., corrupting a file mid-write)

Abort All

Abort all deadlocked processes. This guarantees the end of deadlock.

Abort One at a Time

You can abort one deadlocked process at a time, checking if the deadlock cycle is eliminated.

Recovery from Deadlock

Resource Preemption

Alternatively, you can do resource preemption to break one of the four criteria of deadlock.

Costs — It’s costly to repeatedly:

1. Select a victim,
2. Rollback to a safe state, and
3. Ensure you aren’t starving (repeatedly targeting the same process).