What is the big issue in managing multiple processes?
Concurrency — managing the interaction of all of these processes (multiprogramming, multiprocessing, distributed processing).
Three contexts in which concurrency arises.
Multiple applications (sharing time); structured applications (extension of modular design); operating system structure (OS as a set of processes or threads).
Why are concurrency errors difficult to locate?
Because results are not deterministic and reproducible.
Define an atomic operation.
A sequence of one or more instructions that appears to be indivisible: no other process can see an intermediate state or interrupt it; it executes as a group, or not at all.
Deadlock vs livelock.
Deadlock: processes cannot proceed because each waits for another. Livelock: processes continuously change state in response to each other without doing any useful work.
Define mutual exclusion.
When one process is in a critical section that accesses shared resources, no other process may be in a critical section that accesses any of those shared resources.
Define starvation (concurrency key terms).
A runnable process is overlooked indefinitely by the scheduler; although it is able to proceed, it is never chosen.
On what does the output depend in a race condition?
On the order of execution — on who finishes the race last.
Three control problems of competition among processes.
1. Need for mutual exclusion (critical sections); 2. deadlock; 3. starvation.
Which relationship do processes that are unaware of each other have (Table 5.2)?
Competition.
Which interaction adds the "data coherence" control problem?
Processes indirectly aware of each other (e.g., shared object) — cooperation by sharing.
List the six requirements for mutual exclusion.
One process at a time in the critical section; halting in a noncritical section without interfering; no deadlock or starvation; no delay when the critical section is free; no assumptions about speeds or number of processes; finite time inside the critical section.
Why does disabling interrupts not work on multiprocessors?
Disabling interrupts guarantees mutual exclusion only because uniprocessors only allow interleaving; it will not work in a multiprocessor architecture.
What is another name for the compare&swap instruction?
The compare and exchange instruction.
Three disadvantages of hardware mutual exclusion (special instructions).
Busy-waiting consumes processor time; starvation is possible; deadlock is possible.
What are the three atomic operations on a semaphore?
Initialize, decrement (semWait), increment (semSignal).
What does semWait(s) do?
s.count--; if s.count < 0, place the process in s.queue and block it.
What does semSignal(s) do?
s.count++; if s.count <= 0, remove a process P from s.queue and place it on the ready list.
Strong vs weak semaphore.
Strong semaphores remove waiting processes in FIFO order; weak semaphores don't specify the order of removal from the queue.
State the producer/consumer problem.
Ensure that the producer can't add data into a full buffer and the consumer can't remove data from an empty buffer (only one may access the buffer at a time).
Bounded buffer: when does the producer wait and when does the consumer wait?
Producer: while ((in + 1) % n == out) — buffer full. Consumer: while (in == out) — buffer empty.
What is a monitor?
A programming-language construct that provides equivalent functionality to that of semaphores and that is easier to control.
Three chief characteristics of a monitor.
Local data variables accessible only by the monitor; a process enters by invoking one of its procedures; only one process may be executing in the monitor at a time.
cwait(c) vs csignal(c).
cwait(c): suspend execution of the calling process on condition c. csignal(c): resume execution of some process blocked after a cwait on the same condition.