Notes on the second part of Chapter 2 of Modern Operating Systems, on interprocess communication. These sections cover the basic ideas of mutual exclusion and coordination of concurrent processes. There wasn’t a ton in this section I hadn’t seen before, but it was a good refresher and a good chance to nail down some of the terminology.
2.3 Interprocess Communication
Three issues to consider in interprocess communication:
- Passing information between processes
- Preventing concurrent processes from interfering with each other
- Sequencing of dependency acquisition
2) and 3) also apply to threads. 1) less so because threads can share memory.
2.3.1 Race Conditions
- A race condition occurs when two processes are reading or writing shared data and the result depends on the order of execution.
- The shared data can be in memory, a file, a directory, whatever.
2.3.2 Critical Regions
- Need mutual exclusion to lock other processes out of shared data when it’s being used.
- The part of the program that uses the shared data, requiring mutual exclusion, is called the critical region.
- If you ensure that two processes are never executing the critical region at the same time, you can avoid race conditions.
Four conditions must hold for a good solution to this:
- No two processes are simultaneously in the critical region.
- No assumptions may be made about speed of processes or the number of CPUs.
- No process outside its critical region should be able to block other processes.
- No process should have to wait forever to enter its critical region.
2.3.3 Mutual Exclusion with Busy Waiting
In practice busy waiting is rarely useful, so I’m not going to write down any notes about it, but the book lists several bad solutions for mutual exclusion using busy waiting and goes over how they introduce race conditions and other badness.
A loop that runs doing nothing to implement busy waiting is called a spin lock.
The one useful thing the section covers is the TSL (test-and-set-lock) instruction, which is a CPU instruction that atomically sets and checks a lock variable. This instruction is useful in other, less terrible kinds of mutual exclusion.
2.3.4 Sleep and Wakeup
Want to get rid of busy waiting.
- We’ll use this problem as an example for the mutual exclusion techniques we’re about to discuss.
- Two processes share a fixed-size buffer
- One process produces things and puts them on the buffer.
- The other consumes things from the buffer and does something with them.
- Access to the shared buffer must be carefully managed.
- Conceptually, we want the producer to sleep when the buffer is full and wake up and add things to it when there is space. Conversely, we want the consumer to sleep when the buffer is empty and wake up and take things from it when it is not empty.
- One way to achieve sleep and wakeup is with semaphores.
- A semaphore is an integer variable that supports two operations:
downdecrements the semaphore. If the semaphore is zero, the process that called
downblocks until the semaphore is no longer zero.
upincrements the semaphore.
- Semaphores can represent “tickets” or “passes” to do a specific operation.
- You can use them like this to synchronize two processes, imposing a certain ordering on their actions.
- For example, in the producer-consumer problem, you can use
fullsemaphores to track how many spaces are empty and full in the buffer.
- Then you can force the consumer to do a
fullso that it blocks when there’s on the buffer to take, and force the producer to do a
emptyso that it blocks when there’s no space for it to add to the buffer.
- This assures that consumption only happens after production and production only proceeds to a certain point before some consumption happens.
- A mutex is another way of using a semaphore. It only has the values 0 and 1.
- If the value is 1, processes can enter the critical region. If 0, they block on trying to enter the critical region.
- If your processor has a TSL instruction, you can implement mutex locking and unlocking in user space.
- Importantly, this means you can implement mutexes so that when a thread blocks on a mutex, the thread can yield the CPU before blocking.
- Most modern OSes allow limited sharing of memory between processes, which allows mutex sharing.
- A collection of variables and functions that guarantee only a single thread at once can access them.
- Monitors are a programming language-specific feature. The compiler handles mutual exclusion, often using a mutex or semaphore under the hood.
- Monitors still need a way to block processes that can’t proceed anymore so that another process can start using the monitor. They do this with…
- Two operations:
- If a process can’t continue, it waits on a condition variable and blocks.
- Then another process can enter the monitor and wake up the sleeping process by doing a
signalon the condition variable.
- You can either immediately suspend the signaling process, resuming it later, and let the awakened process run; or you can require a signal to be the last thing in a function.
- Without the monitor’s guarantee of only one process running the code at once,
signalare subject to race conditions where signals cross and wakeup signals disappear into the void just as a process is about to go to sleep, causing them to never wake up.
Java objects can also be used as monitors with the
synchronized keyword and the
notifyAll methods. This combined with threads is the basis for all Java concurrency.
2.3.8 Message Passing
- Semaphores and monitors require shared memory, so they can’t be used in distributed systems.
- Message passing, on the other hand, is more general and works even across machines.
- Uses two operations:
receive. These are implemented as system calls.
sendgets a process ID and a message.
receivealso gets a process ID and in C implementations it gets passed an empty message to hydrate.
- A receiver can block until a message arrives, or return immediately with an error code.
Message passing raises several design challenges.
- Messages can be lost by the network. You can have receivers send back an acknowledgment signal, and have senders retry the message if they don’t get it after a certain timeout.
- Local message passing is slower than semaphores or monitors.
- You can implement message passing with a mailbox that buffers received messages, or you can have threads block and wait on each other. The latter is called a rendezvous.
- Block a group of processes all at the same point in the program to coordinate their start on the next phase.
2.4 Classical IPC Problems
These are all well-known and there’s a ton of information out there on them, so I didn’t take detailed notes about them.
2.4.1 Dining Philosophers
Models a situation where there is possible contention for a set of shared resources, which can lead to possible deadlocks or starvation.
2.4.2 Readers and Writers
A simplistic model of a database, where multiple concurrent processes can read but only one can write at a time.
2.4.3 Sleeping Barber
Models a situation where a bounded size queue of tasks is being serviced by a single process but filled by multiple processes.