Operating Systems
In this chapter we examine the classical problems that appear in nearly every operating systems textbook. They are usually presented in terms of real-world problems, so that the statement of the problem is clear and so that students can bring their intuition to bear.
For the most part, though, these problems do not happen in the real world, or if they do, the real-world solutions are not much like the kind of synchronization code we are working with.
The reason we are interested in these problems is that they are analogous to common problems that operating systems (and some applications) need to solve. For each classical problem I will present the classical formulation, and also explain the analogy to the corresponding OS problem.
In multithreaded programs there is often a division of labor between threads. In one common pattern, some threads are producers and some are consumers. Producers create items of some kind and add them to a data structure; consumers remove the items and process them.
Event-driven programs are a good example. An “event” is something that happens that requires the program to respond: the user presses a key or moves the mouse, a block of data arrives from the disk, a packet arrives from the network, a pending operation completes.
Whenever an event occurs, a producer thread creates an event object and adds it to the event buffer. Concurrently, consumer threads take events out of the buffer and process them. In this case, the consumers are called “event handlers.”
There are several synchronization constraints that we need to enforce to make this system work correctly:
While an item is being added to or removed from the buffer, the buffer is in an inconsistent state. Therefore, threads must have exclusive access to the buffer.
If a consumer thread arrives while the buffer is empty, it blocks until a producer adds a new item.
Assume that producers perform the following operations over and over:
event = waitForEvent()
buffer.add(event)
Also, assume that consumers perform the following operations:
event = buffer.get()
event.process()
As specified above, access to the buffer has to be exclusive, but waitForEvent and event.process can run concurrently.
Add synchronization statements to the producer and consumer code to enforce the synchronization constraints.
The next classical problem, called the Reader-Writer Problem, pertains to any situation where a data structure, database, or file system is read and modified by concurrent threads. While the data structure is being written or modified it is often necessary to bar other threads from reading, in order to prevent a reader from interrupting a modification in progress and reading inconsistent or invalid data.
As in the producer-consumer problem, the solution is asymmetric. Readers and writers execute different code before entering the critical section. The synchronization constraints are:
Any number of readers can be in the critical section simultaneously.
Writers must have exclusive access to the critical section.
In other words, a writer cannot enter the critical section while any other thread (reader or writer) is there, and while the writer is there, no other thread may enter.
The exclusion pattern here might be called categorical mutual exclusion. A thread in the critical section does not necessarily exclude other threads, but the presence of one category in the critical section excludes other categories.
Use semaphores to enforce these constraints, while allowing readers and writers to access the data structure, and avoiding the possibility of deadlock.
In the previous solution, is there any danger of deadlock? In order for a deadlock to occur, it must be possible for a thread to wait on a semaphore while holding another, and thereby prevent itself from being signaled.
In this example, deadlock is not possible, but there is a related problem that is almost as bad: it is possible for a writer to starve.
If a writer arrives while there are readers in the critical section, it might wait in queue forever while readers come and go. As long as a new reader arrives before the last of the current readers departs, there will always be at least one reader in the room.
This situation is not a deadlock, because some threads are making progress, but it is not exactly desirable. A program like this might work as long as the load on the system is low, because then there are plenty of opportunities for the writers. But as the load increases the behavior of the system would deteriorate quickly (at least from the point of view of writers).
Extend this solution so that when a writer arrives, the existing readers can finish, but no additional readers may enter.
In the previous section, we addressed what I’ll call categorical starvation, in which one category of threads (readers) allows another category (writers) to starve. At a more basic level, we have to address the issue of thread starvation, which is the possibility that one thread might wait indefinitely while others proceed.
For most concurrent applications, starvation is unacceptable, so we enforce the requirement of bounded waiting, which means that the time a thread waits on a semaphore (or anywhere else, for that matter) has to be provably finite.
In part, starvation is the responsibility of the scheduler. Whenever multiple threads are ready to run, the scheduler decides which one or, on a parallel processor, which set of threads gets to run. If a thread is never scheduled, then it will starve, no matter what we do with semaphores.
So in order to say anything about starvation, we have to start with some assumptions about the scheduler. If we are willing to make a strong assumption, we can assume that the scheduler uses one of the many algorithms that can be proven to enforce bounded waiting. If we don’t know what algorithm the scheduler uses, then we can get by with a weaker assumption:
Property 1: if there is only one thread that is ready to run, the scheduler has to let it run.
If we can assume Property 1, then we can build a system that is provably free of starvation. For example, if there are a finite number of threads, then any program that contains a barrier cannot starve, since eventually all threads but one will be waiting at the barrier, at which point the last thread has to run.
In general, though, it is non-trivial to write programs that are free from starvation unless we make the stronger assumption:
Property 2: if a thread is ready to run, then the time it waits until it runs is bounded.
In our discussion so far, we have been assuming Property 2 implicitly, and we will continue to. On the other hand, you should know that many existing systems use schedulers that do not guarantee this property strictly.
Even with Property 2, starvation rears its ugly head again when we introduce semaphores. In the definition of a semaphore, we said that when one thread executes signal, one of the waiting threads gets woken up. But we never said which one. In order to say anything about starvation, we have to make assumptions about the behavior of semaphores.
The weakest assumption that makes it possible to avoid starvation is:
Property 3: if there are threads waiting on a semaphore when a thread executes signal, then one of the waiting threads has to be woken.
This requirement may seem obvious, but it is not trivial. It has the effect of barring one form of problematic behavior, which is a thread that signals a semaphore while other threads are waiting, and then keeps running, waits on the same semaphore, and gets its own signal! If that were possible, there would be nothing we could do to prevent starvation.
With Property 3, it becomes possible to avoid starvation, but even for something as simple as a mutex, it is not easy. For example, imagine three threads running the following code:
while True:
mutex.wait()
# critical section
mutex.signal()
The while statement is an infinite loop; in other words, as soon as a thread leaves the critical section, it loops to the top and tries to get the mutex again.
Imagine that Thread A gets the mutex and Thread B and C wait. When A leaves, B enters, but before B leaves, A loops around and joins C in the queue. When B leaves, there is no guarantee that C goes next. In fact, if A goes next, and B joins the queue, then we are back to the starting position, and we can repeat the cycle forever. C starves.
The existence of this pattern proves that the mutex is vulnerable to starvation. One solution to this problem is to change the implementation of the semaphore so that it guarantees a stronger property:
Property 4: if a thread is waiting at a semaphore, then the number of threads that will be woken before it is bounded.
For example, if the semaphore maintains a first-in-first-out queue, then Property 4 holds because when a thread joins the queue, the number of threads ahead of it is finite, and no threads that arrive later can go ahead of it.
A semaphore that has Property 4 is sometimes called a strong semaphore; one that has only Property 3 is called a weak semaphore. We have shown that with weak semaphores, the simple mutex solution is vulnerable to starvation. In fact, Dijkstra conjectured that it is not possible to solve the mutex problem without starvation using only weak semaphores.
In 1979, J.M. Morris refuted the conjecture by solving the problem, assuming that the number of threads is finite . If you are interested in this problem, the next section presents his solution. If this is not your idea of fun, you can just assume that semaphores have Property 4 and go on to Section [dining].
write a solution to the mutual exclusion problem using weak semaphores. Your solution should provide the following guarantee: once a thread arrives and attempts to enter the mutex, there is a bound on the number of threads that can proceed ahead of it. You can assume that the total number of threads is finite.
The Dining Philosophers Problem was proposed by Dijkstra in 1965, when dinosaurs ruled the earth . It appears in a number of variations, but the standard features are a table with five plates, five forks (or chopsticks) and a big bowl of spaghetti. Five philosophers, who represent interacting threads, come to the table and execute the following loop:
while True:
think()
get_forks()
eat()
put_forks()
The forks represent resources that the threads have to hold exclusively in order to make progress. The thing that makes the problem interesting, unrealistic, and unsanitary, is that the philosophers need two forks to eat, so a hungry philosopher might have to wait for a neighbor to put down a fork.
Assume that the philosophers have a local variable i that identifies each philosopher with a value in (0. . 4). Similarly, the forks are numbered from 0 to 4, so that Philosopher i has fork i on the right and fork i + 1 on the left. Here is a diagram of the situation:
Image source: Wikipedia
Assuming that the philosophers know how to think and eat, our job is to write a version of get_forks and put_forks that satisfies the following constraints:
Only one philosopher can hold a fork at a time.
It must be impossible for a deadlock to occur.
It must be impossible for a philosopher to starve waiting for a fork.
It must be possible for more than one philosopher to eat at the same time.
The last requirement is one way of saying that the solution should be efficient; that is, it should allow the maximum amount of concurrency.
We make no assumption about how long eat and think take, except that eat has to terminate eventually. Otherwise, the third constraint is impossible—if a philosopher keeps one of the forks forever, nothing can prevent the neighbors from starving.
To make it easy for philosophers to refer to their forks, we can use the functions left and right:
def left(i): return i
def right(i): return (i + 1) % 5
The % operator wraps around when it gets to 5, so (4 + 1) % 5 = 0.
Since we have to enforce exclusive access to the forks, it is natural to use a list of Semaphores, one for each fork. Initially, all the forks are available.
forks = [Semaphore(1) for i in range(5)]
This notation for initializing a list might be unfamiliar to readers who don’t use Python. The range function returns a list with 5 elements; for each element of this list, Python creates a Semaphore with initial value 1 and assembles the result in a list named forks.
Here is an initial attempt at get_fork and put_fork:
def get_forks(i):
fork[right(i)].wait()
fork[left(i)].wait()
def put_forks(i):
fork[right(i)].signal()
fork[left(i)].signal()
It’s clear that this solution satisfies the first constraint, but we can be pretty sure it doesn’t satisfy the other two, because if it did, this wouldn’t be an interesting problem and you would be reading Chapter [next].
what’s wrong?
The problem is that the table is round. As a result, each philosopher can pick up a fork and then wait forever for the other fork. Deadlock!
write a solution to this problem that prevents deadlock.
Hint: one way to avoid deadlock is to think about the conditions that make deadlock possible and then change one of those conditions. In this case, the deadlock is fairly fragile—a very small change breaks it.
The cigarette smokers problem problem was originally presented by Suhas Patil , who claimed that it cannot be solved with semaphores. That claim comes with some qualifications, but in any case the problem is interesting and challenging.
Four threads are involved: an agent and three smokers. The smokers loop forever, first waiting for ingredients, then making and smoking cigarettes. The ingredients are tobacco, paper, and matches.
We assume that the agent has an infinite supply of all three ingredients, and each smoker has an infinite supply of one of the ingredients; that is, one smoker has matches, another has paper, and the third has tobacco.
The agent repeatedly chooses two different ingredients at random and makes them available to the smokers. Depending on which ingredients are chosen, the smoker with the complementary ingredient should pick up both resources and proceed.
For example, if the agent puts out tobacco and paper, the smoker with the matches should pick up both ingredients, make a cigarette, and then signal the agent.
To explain the premise, the agent represents an operating system that allocates resources, and the smokers represent applications that need resources. The problem is to make sure that if resources are available that would allow one more applications to proceed, those applications should be woken up. Conversely, we want to avoid waking an application if it cannot proceed.
Based on this premise, there are three versions of this problem that often appear in textbooks:
Patil’s version imposes restrictions on the solution. First, you are not allowed to modify the agent code. If the agent represents an operating system, it makes sense to assume that you don’t want to modify it every time a new application comes along. The second restriction is that you can’t use conditional statements or an array of semaphores. With these constraints, the problem cannot be solved, but as Parnas points out, the second restriction is pretty artificial . With constraints like these, a lot of problems become unsolvable.
This version keeps the first restriction—you can’t change the agent code—but it drops the others.
In some textbooks, the problem specifies that the agent should signal the smoker that should go next, according to the ingredients that are available. This version of the problem is uninteresting because it makes the whole premise, the ingredients and the cigarettes, irrelevant. Also, as a practical matter, it is probably not a good idea to require the agent to know about the other threads and what they are waiting for. Finally, this version of the problem is just too easy.
Naturally, we will focus on the interesting version. To complete the statement of the problem, we need to specify the agent code. The agent uses the following semaphores:
agentSem = Semaphore(1)
tobacco = Semaphore(0)
paper = Semaphore(0)
match = Semaphore(0)
The agent is actually made up of three concurrent threads, Agent A, Agent B and Agent C. Each waits on agentSem; each time agentSem is signaled, one of the Agents wakes up and provides ingredients by signaling two semaphores.
agentSem.wait()
tobacco.signal()
paper.signal()
agentSem.wait()
paper.signal()
match.signal()
agentSem.wait()
tobacco.signal()
match.signal()
This problem is hard because the natural solution does not work. It is tempting to write something like:
tobacco.wait()
paper.wait()
agentSem.signal()
paper.wait()
match.wait()
agentSem.signal()
tobacco.wait()
match.wait()
agentSem.signal()
What’s wrong with this solution?
The problem with the previous solution is the possibility of deadlock. Imagine that the agent puts out tobacco and paper. Since the smoker with matches is waiting on tobacco, it might be unblocked. But the smoker with tobacco is waiting on paper, so it is possible (even likely) that it will also be unblocked. Then the first thread will block on paper and the second will block on match. Deadlock!
This website is provided under a CC BY-SA license by the
The Berea CS Department.
Fall 2013 offering of taught by Matt Jadud