Chapter 11: Low-level synchronization: algorithms

11.2 An example of semaphores in system design: the THE system

(THE = Technische Hogeschool Eindhoven, Dijkstra leverde hier baanbrekend werk met concept van semafoor)
The lowest level (0), creates virtual processors. Above this, processes exist and may communicate using a semaphore mechanism. The rest of the system may be written using these concurrency constructs. All interrupts enter at this level, and all but the clock interrupt are handled at higher levels. At level 1, one process provides a one-level virtual store. It synchronizes with drum interrupts and with requests for store from higher-level processes. At level 2, one process provides virtual consoles for higher-level processes and syncs with their requests. It also syncs with console interrupts and the memory manager process. At level 3, a separate process manages each physical device. Each process syncs with its device’s interrupts, with the memory and console manager processes, and with higher-level processes over I/O requests. At level 4, the highest, reside 5 user processes. In all cases where data is passed, producer-consumer style message buffering must be used, controlled by semaphores.

11.3 The producer-consumer, bounded buffer problem

11.3.2 Definition of a cyclic or bounded buffer
circular array
* the index values ranging from 0 to N-1
* some slots are occupied by data items (indicated by ‘data’); others are empty (indicated by shading)
* two cursors (variables holding a valid index value) named ‘in’ and ‘out’, the purposes of which are, respectively, to indicate the first available empty slot and the next data item that can be taken from the buffer.

11.3.3 Algorithm for a single producer and single consumer
figure gives high-level view of a solution to the single producer, single consumer problem. The problem would be programmed in practice in a modular style by defining a buffer class. (hoe lossen we bounded buffer probleem op met semaforen?)

two semaphores, items and spaces
note that for a single producer and a single consumer the buffer is not accessed under mutual exclusion since they are accessing different parts of the buffer (using different cursors). Sync of the processes ensures that they block before attempting to access the same slot in the buffer.(2 semaforen die gedeeltelijk elkaars spiegelbeeld zijn => counting semaphore; maar er wordt wel voor synchronisatie links en rechts gezorgd. Geen kritische regio (want 1 producer, 1 consumer) dus geen binaire semafoor nodig voor wederzijdse uitsluiting => verandert bij overgang naar meerdere producers, meerdere consumers)

11.3.4 Algorithm for more than one producer or consumer
the many producers must access the buffer under mutual exclusion as they are using the same cursor to insert items.
enforce exclusive access to the buffer between consumers
one producer and one consumer could access the buffer concurrently, provided producers and consumers use different guard semaphores.

11.4 Safety and liveness properties

11.5 The multiple readers, single writer problem

figure 1: basic structure of code which must be executed by reader processes and writer processes. To acquire or release the resource, shared counts must be accessed under mutual exclusion. The fact that writers must write under mutual exclusion is indicated.
figure 2: gives the algorithm in detail. Priority is given to waiting writers over waiting readers, since active readers only go on to become reading readers if there are no active writers. The various counts are accessed under mutual exclusion, protected by the semaphore CGUARD. Processes wait to read or write on semaphores R or W respectively. R and W are given ‘wake-up-waiting’ signals in the acquire procedures if there are no active writers (for R) or no running readers (for W). releasing the resource may involve sending sync signals to waiting readers and writers; the last reading reader wakes up any waiting writers, the last active writer wakes up waiting readers.
(readers-writers probleem: meerdere lezers kunnen gegevens terzelfder tijd lezen, hinderen elkaar niet; schrijver zorgt voor probleem: er mag niemand lezen tijdens het schrijven + write moet exclusief zijn (geen andere schrijvers), assumptie: schrijvers krijgen voorrang)

11.6 Limitations of semaphores

operations do not allow a test for busy without a commitment to blocking

11.7 Eventcounts and sequencers

11.7.1 Use of eventcounts for sync
a process specifies which occurrence of an event it is waiting for, rather than just the next event of that type. We therefore introduce a local count I within the process for this purpose.


11.7.2 Use of a sequencer to enforce mutual exclusion
process competing with others to use a resource protected by the eventcount GUARD. The process first acquires a ticket, stored in its local variable myturn. It then attempts to enter its critical region by executing GUARD.await(myturn).
the order of execution of critical regions is determined by the values returned by turns.ticket() (low => high)
(minstens even complex als semaforen en lost eiglk niets op; await(value): niet meer wachten tot iets vrijkomt, maar op bepaalde waarde; advance : doet value +1
zodat volgend process verder kan)

11.7.3 Producer-consumer, bounded buffer with eventcounts and sequencers
producer and consumer may access the buffer at the same time since the solution to the sync problem ensures that the consumer does not read the ith item until the producer has written it and the producer does not write into the ith slot until the consumer has read the i-Nth item from it.
figure1: eventcounts ‘in’ and ‘out’ count the items put in by the producer and taken out by the consumer. When there are multiple producers and consumers, a sequencer ‘tp’ must be used to order the accesses to the buffer of producers and one ‘tc’ for that of consumers. Figure 2 outlines the solution.

11.8 POSIX threads

11.8.2 Synchronization
Mutexes
a mutex (mutual exclusion) is an object that multiple threads use to ensure the integrity of a shared resource that they access by allowing only one thread to access it at a time. Mutex has two states: locked and unlocked. For each piece of shared data, all threads accessing that data must use the same mutex: each thread locks the mutex before it accesses the shared data and unlocks the mutex when it has finished accessing that data. Each mutext must be created by pthread_mutex_init
* fast mutex: locked exactly once by a thread. If a thread attempts to lock the mutex again without first unlocking it, the thread will wait for itself to release the lock and will deadlock.
* recursive mutex: can be locked more than once by a given thread without causing a deadlock. Useful if a thread needs exclusive access to a piece of data, and it needs to call another routine that needs exclusive access to the data.
* non-recursive mutex: locked exactly once by a thread. Error if any thread tries to lock already locked mutex. Useful during development and debugging.

mutex sync operations:
* pthread_mutex_lock: if mutex is locked, the thread waits for the mutex to become available
* pthread_mutex_trylock: this returns immediately with a boolean value indicating whether or not it was able to lock the mutex
*pthread_mutex_unlock: when a thread has finished accessing a piece of shared data, it unlocks the associated mutex by calling pthread_mutex_unlock

Condition variables
a condition variable allows a thread to block its own execution until some shared data reaches a particular state. A condition variable is a sync object used in conjunction with a mutex. A condition variable allows threads to wait for that data to enter a defined state.
a condition variable is used for tasks with coarse granularity; a thread can wait on a condition variable for long periods. A mutex is used for sync with fine granularity and should be held only for short periods of time.
Waiting on the condition variable automatically unlocks the mutex.