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.

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

 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 */
    }
}