Unsorted

TODO What came before?

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?