Interprocess Communication
Race Conditions
Situations like this, where two or more processes are reading or writing some shared data and the final result depends on who runs precisely when, are called race conditions.
Cirtical Regions
Sometimes a process has to access shared memory or files, or do other critical things that can lead to races. That part of the program where the shared memory is accessed is called the critical region or critical section.
We should make sure that if one process is using a shared variable or file, the other processes will be excluded from doing the same thing, which is called mutual exclusion.
We need four conditions to have processes coopreate correctly:
- No two processes may be simultaneously inside their critical regions.
- No assumptions may be made about speeds or the number of CPUs.
- No process running outside its critical region may block any process.
- No process should have to wait forever to enter its critical region.
Mutual Exclusion with Busy Waiting
Disabling Interrupts
On a single-processor system, the simplest solution is to have each process disable all interrupts just after entering its critical region and re-enable them just before leaving it.
Problems:
- it is unwise to give user processes the power to turn off interrupts.
- if the system is a multiprocessor (with two or more CPUs) disabling interrupts affects only the CPU that executed the disable instruction.
Lock Variables
Consider having a single, shared (lock) variable, initially 0. When a process wants to enter its critical region, it first tests the lock.
- If the lock is 0, the process sets it to 1 and enters the critical region.
- If the lock is already 1, the process just waits until it becomes 0.
Strict Alternation
Continuously testing a variable until some value appears is called busy waiting. A lock that uses busy waiting is called a spin lock.
Peterson’s Solution
Before using the shared variables (i.e., before entering its critical region), each process calls enter region with its own process number, 0 or 1, as parameter. This call will cause it to wait, if need be, until it is safe to enter. After it has finished with the shared variables, the process calls leave region to indicate that it is done and to allow the other process to enter, if it so desires.
The TSL Instruction
TSL RX,LOCK
(Test and Set Lock) that works as follows. It reads the contents of the memory word lock into register RX and then stores a nonzero value at the memory address lock. The operations of reading the word and storing into it are guaranteed to be indivisible—no other processor can access the memory word until the instruction is finished. The CPU executing the TSL instruction locks the memory bus to prohibit other CPUs from accessing memory until it is done.
To use the TSL instruction, we will use a shared variable, lock, to coordinate access to shared memory. When lock is 0, any process may set it to 1 using the TSL instruction and then read or write the shared memory. When it is done, the process sets lock back to 0 using an ordinary move instruction.
An alternative instruction to TSL is XCHG, which exchanges the contents of two locations atomically
Priority Inversion Problem
Consider a computer with two processes, H, with high priority, and L, with low priority. The scheduling rules are such that H is run whenever it is in ready state. At a certain moment, with L in its critical region, H becomes ready to run (e.g., an I/O operation completes). H now begins busy waiting, but since L is never scheduled while H is running, L never gets the chance to leave its critical region, so H loops forever.
The Producer-Consumer Problem
Two processes share a common, fixed-size buffer. One of them, the producer, puts information into the buffer, and the other one, the consumer, takes it out.
Sleep and Wakeup
Fatal race condition
The buffer is empty and the consumer has just read count to see if it is 0. At that instant, the scheduler decides to stop running the consumer temporarily and start running the producer. The producer inserts an item in the buffer, increments count, and notices that it is now 1. Reasoning that count was just 0, and thus the consumer must be sleeping, the producer calls wakeup to wake the consumer up.
Unfortunately, the consumer is not yet logically asleep, so the wakeup signal is lost. When the consumer next runs, it will test the value of count it previously read, find it to be 0, and go to sleep. Sooner or later the producer will fill up the buffer and also go to sleep. Both will sleep forever.
Semaphores
Mutex
A mutex is a shared variable that can be in one of two states: unlocked or locked, with 0 meaning unlocked and all other values meaning locked.
The major calls relating to mutexes in Pthreads are as below:
In addition to mutexes, Pthreads offers a second synchronization mechanism: condition variables, which allow threads to block due to some condition not being met.
Monitor
A monitor is a collection of procedures, variables, and data structures that are all grouped together in a special kind of module or package.