«  8.5. Dining Philosophers Problem and Deadlock   ::   Contents   ::   8.7. Extended Example: Parallel Modular Exponentiation  »

8.6. Cigarette Smokers Problem and the Limits of Semaphores and Locks

One key feature of the dining philosopher problem is that all of the resources can be treated interchangeably. One person’s left fork can serve as someone else’s right fork, and vice versa. In the array of semaphores, the threads could theoretically wait on the semaphores in a random order and still achieve the circular wait if circumstances align properly. Consequently, it is tempting to think that circular wait cannot happen if different types of resources are used. For instance, is it possible to have deadlock if the resources consist of a single semaphore, a single lock, and a single condition variable?

The answer to this question is yes; using different types of synchronization primitives that satisfy the three system properties (mutual exclusion, hold and wait, no preemption) does not provide safety against deadlock. The cigarette smokers problem [1] helps to illustrate this point, but it actually proves a stronger point as well. While the dining philosophers problem could be solved by using an additional semaphore, the cigarette smokers problem highlights a scenario that is provably impossible to solve with semaphores alone.

The scenario for the cigarette smokers problem consists of four threads: three smokers and one agent. In order to smoke, the smoker needs to acquire three items: tobacco, paper, and a match. Once the smoker has all three, they combine the paper and tobacco to roll a cigarette and use the match to light it. Each of the three smokers has an infinite supply of exactly one item and needs the other two. Code Listing 8.29 shows a sample outline for the smoker threads. The smoker shown there is assumed to have an infinite supply of tobacco but needs the match and paper. The smoker sends a signal to request more paper and matches when they are finished smoking. The other two threads are similar, but one would wait on semaphores for a match and tobacco and the third would wait on tobacco and paper.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
/* Code Listing 8.29:
   Sample structure for a smoker thread
 */

void *
smoker_with_tobacco (void)
{
  while (true)
    {
      sem_wait (match_sem); /* grab match from table */
      sem_wait (paper_sem); /* grab paper from table */
      /* roll cigarette and smoke */
      sem_post (more_needed); /* signal to agent */
    }
}

The fourth thread is an agent that creates two of the three items at a time, placing the items on the table. Once the items are taken away, the agent waits on a signal to produce more. Code Listing 8.30 shows an outline of an agent thread. The agent picks randomly between three cases, producing some combination of two out of the three items. The agent places the items on the table, then waits for a request for more items.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/* Code Listing 8.30:
   Sample structure for the agent thread
 */

void *
agent (void)
{
  while (true)
    {
      int number = rand() % 3;
      switch (number)
        {
           case 0: sem_post (match_sem); /* match and paper */
                   sem_post (paper_sem);
                   break;
           case 1: sem_post (match_sem); /* match and tobacco */
                   sem_post (tobacco_sem);
                   break;
           case 2: sem_post (paper_sem); /* tobacco and paper */
                   sem_post (tobacco_sem);
                   break;
        }
      sem_wait (more_needed); /* wait for request for more */
    }
}

To understand the implications of the cigarette smokers problem, it is important to emphasize that Code Listings 8.29 and 8.30 are just sample implementations. The smoker_with_tobacco() could be changed to wait on the paper_sem before the match_sem; the order does not matter. Similarly, the agent() could be written so that case 0 would post to paper_sem before match_sem. The result does not rely on any particular ordering of these lines of code.

In addition to the description above, there is one constraint placed on the agent thread. Once it is written, it cannot change. The problem is a metaphor for working with an OS. The agent is the OS, providing a service of some sort; it is not aware of the design of applications that will be running on the system. This restriction, then, makes sense. You would not expect your OS to behave differently whenever you install or update the applications running on it.

Decorative example icon

Example 8.6.1


Based on this restriction of the agent thread, the cigarette smokers problem states that it is impossible to create the smoker threads that would avoid deadlock. That is, regardless of how you order the calls to sem_wait() in the smoker threads, the possibility of deadlock cannot be avoided. For instance, consider the outcomes in Table 8.4 if the agent produces a match and tobacco. If these items are grabbed by two threads, no smoker can progress.

Smoker with Tobacco Smoker with Paper Smoker with Match
sem_wait(match_sem);
   SUCCESS
sem_wait(paper_sem);
   BLOCKED
sem_wait(tobacco_sem);
   SUCCESS
sem_wait(match_sem);
   BLOCKED
sem_wait(paper_sem);
   BLOCKED
sem_wait(tobacco_sem);
   BLOCKED

Table 8.4: Possible scenario when agent places match and tobacco on the table

It is tempting to claim that there is a simple fix: rewrite the smoker_with_tobacco() so that it must wait on the paper_sem before the match_sem. Switching this order would require both smoker_with_tobacco() and smoker_with_match() to wait on paper_sem first. Since the agent had only incremented the tobacco_sem and match_sem, the smoker_with_paper() could proceed without being blocked. While that would be the case in this situation, consider the next round where the agent places a different combination on the table. If that combination included paper and tobacco, the smoker_with_tobacco() could, once again, push the system into deadlock as in Table 8.5.

Smoker with Tobacco Smoker with Paper Smoker with Match
sem_wait(paper_sem);
   SUCCESS
sem_wait(match_sem);
   BLOCKED
sem_wait(tobacco_sem);
   SUCCESS
sem_wait(match_sem);
   BLOCKED
sem_wait(paper_sem);
   BLOCKED
sem_wait(tobacco_sem);
   BLOCKED

Table 8.5: Imposing a linear ordering does not fix the deadlock

8.6.1. Implications of the Cigarette Smokers Problem

The key claim of the cigarette smokers problem is that this scenario has no solution for traditional semaphores, as they existed at the time. When this problem was initially proposed, semaphores only provided operations for incrementing or decrementing their internal value by one. The problem proves that, if we are limited to those operations only, there are situations in which avoiding deadlock is provably impossible. Regardless of how the agent and the smoker threads are constructed, once the agent’s structure is fixed, any construction of the smokers will create a possible deadlock situation.

As a result, the cigarette smokers problem proves that some form of introspection is needed for synchronization primitives. This introspection is provided by POSIX operations such as sem_try_wait() or pthread_mutex_trylock(). These operations provide information about whether or not the synchronization attempt will succeed. Code Listing 8.31 illustrates how these forms could be used in a successful solution to the cigarette smokers problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
/* Code Listing 8.31:
   Sample structure for a smoker thread
 */

void *
smoker_with_tobacco (void)
{
  while (true)
    {
      sem_wait (match_sem); /* grab match from table */
      if (sem_try_wait (paper_sem) == 0) /* grab paper */
        {
          /* roll cigarette and smoke */
          sem_post (more_needed); /* signal to agent */
        }
      else sem_post (match_sem); /* drop the match */
    }
}

8.6.2. On Cigarette Smokers and Dining Philosophers

The last solution proposed to the dining philosophers problem worked by imposing a linear ordering on the semaphores. Examining the order of calls to sem_wait() in Table 8.5, we can observe that this approach does not always succeed in avoiding deadlock. Specifically, Table 8.5 is built on a solution that imposes an order of paper_sem before tobacco_sem and tobacco_sem before match_sem. By transitivity, this requires the paper_sem before match_sem, as implemented in the smoker_with_tobacco().

It is fair to ask, then, why the linear ordering works for dining philosophers but fails for cigarette smokers. The key difference has to do with the sum of the semaphores’ internal values. In the dining philosophers problem, all semaphores are initialized to one; consequently, if there are N semaphores, their sum is also N. In contrast, the cigarette smokers problem initializes all semaphores to zero. The agent then posts to two out of the three semaphores. The semaphores are then both decremented and the cycle repeats. As a result, the sum of the semaphores never reaches three.

Based on these comparisons, we could generalize the cigarette smokers problem to more than three threads. In this generalized form, there would be N smokers and the agent would place only N-1 items on the table. If every thread requires two resources (decrementing two semaphores, acquiring two locks, etc.), then a linear ordering will not prevent deadlock. The total number of available resources must be at least the total number of possible requests that can be made. If there are N threads that can all issue concurrent requests, there must be N instances available for the linear ordering to prevent deadlock.

[1]The name of this problem illustrates how cultural norms can change over time. The cigarette smokers problem was first described in a paper in 1971, when smoking was considered much more socially acceptable than now and rolling one’s own cigarettes was a commonly known practice.
«  8.5. Dining Philosophers Problem and Deadlock   ::   Contents   ::   8.7. Extended Example: Parallel Modular Exponentiation  »

About Contact Us Privacy License