.. _CigSmokers:

.. raw:: html

   <script>ODSA.SETTINGS.DISP_MOD_COMP = true;ODSA.SETTINGS.MODULE_NAME = "CigSmokers";ODSA.SETTINGS.MODULE_LONG_NAME = "Cigarette Smokers Problem and the Limits of Semaphores and Locks";ODSA.SETTINGS.MODULE_CHAPTER = "Synchronization Patterns and Problems"; ODSA.SETTINGS.BUILD_DATE = "2021-06-01 12:51:47"; ODSA.SETTINGS.BUILD_CMAP = false;JSAV_OPTIONS['lang']='en';JSAV_EXERCISE_OPTIONS['code']='java';</script>


.. |--| unicode:: U+2013   .. en dash
.. |---| unicode:: U+2014  .. em dash, trimming surrounding whitespace
   :trim:


.. This file is part of the OpenCSF eTextbook project. It was
.. auto-generated by scripts from the OpenDSA eTextbook project.
.. See https://OpenCSF.org for more details. OpenCSF is distributed
.. under a Creative Commons Attribution-NonCommercial 4.0 International
.. License (see http://creativecommons.org/licenses/by-nc/4.0/),
.. Copyright (c) 2019-2021 by Michael S. Kirkpatrick. OpenDSA is
.. distributed under an MIT open source license, Copyright (c) 2012-2021
.. by the OpenDSA Project Contributors.

.. avmetadata::
   :author: Michael S. Kirkpatrick
   :requires:
   :satisfies: 
   :topic: 

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
:term:`cigarette smokers problem`  [#f46]_ 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 <#cl8-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.

.. _cl8-29:

.. codeinclude:: SynchProblems/CodeListing-8-29.c
   :linenos: true

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 <#cl8-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.

.. _cl8-30:

.. codeinclude:: SynchProblems/CodeListing-8-30.c
   :linenos: true

To understand the implications of the cigarette smokers problem, it is important
to emphasize that `Code Listings 8.29 <#cl8-29>`_ and `8.30 <#cl8-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.

.. topic:: Example

   .. figure:: Images/CSF-Images-Example.png
      :align: left
      :width: 100%
      :alt: Decorative example icon

   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 <#tbl8-4>`_ if the agent produces
   a match and tobacco. If these items are grabbed by two threads, no smoker can progress.

   .. _tbl8-4:

   .. raw:: html

      <center>
      <table class="table table-bordered">
        <thead class="thead-light">
          <tr>
            <th class="py-0 center">Smoker with Tobacco</th>
            <th class="py-0 center">Smoker with Paper</th>
            <th class="py-0 center">Smoker with Match</th>
          </tr>
        </thead>
        <tbody>
          <tr>
            <td class="py-0">sem_wait(match_sem);<br />&nbsp;&nbsp;
              SUCCESS<br />sem_wait(paper_sem);<br />&nbsp;&nbsp; BLOCKED</td>
            <td class="py-0">sem_wait(tobacco_sem);<br />&nbsp;&nbsp;
              SUCCESS<br />sem_wait(match_sem);<br />&nbsp;&nbsp; BLOCKED</td>
            <td class="py-0">sem_wait(paper_sem);<br />&nbsp;&nbsp;
              BLOCKED<br />sem_wait(tobacco_sem);<br />&nbsp;&nbsp; BLOCKED</td>
          </tr>
        </tbody>
      </table>
      <p>
      Table 8.4: Possible scenario when agent places match and tobacco on the table
      </p>
      </center>

   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 <#tbl8-5>`_.

   .. _tbl8-5:

   .. raw:: html

      <center>
      <table class="table table-bordered">
        <thead class="thead-light">
          <tr>
            <th class="py-0 center">Smoker with Tobacco</th>
            <th class="py-0 center">Smoker with Paper</th>
            <th class="py-0 center">Smoker with Match</th>
          </tr>
        </thead>
        <tbody>
          <tr>
            <td class="py-0">sem_wait(paper_sem);<br />&nbsp;&nbsp;
              SUCCESS<br />sem_wait(match_sem);<br />&nbsp;&nbsp; BLOCKED</td>
            <td class="py-0">sem_wait(tobacco_sem);<br />&nbsp;&nbsp;
              SUCCESS<br />sem_wait(match_sem);<br />&nbsp;&nbsp; BLOCKED</td>
            <td class="py-0">sem_wait(paper_sem);<br />&nbsp;&nbsp;
              BLOCKED<br />sem_wait(tobacco_sem);<br />&nbsp;&nbsp; BLOCKED</td>
          </tr>
        </tbody>
      </table>
      <p>
      Table 8.5: Imposing a linear ordering does not fix the deadlock
      </p>
      </center>

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 <#cl8-31>`_
illustrates how these forms could be used in a successful solution to the
cigarette smokers problem.

.. _cl8-31:

.. codeinclude:: SynchProblems/CodeListing-8-31.c
   :linenos: true

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 <#tbl8-5>`_, we can observe that this approach does
not always succeed in avoiding deadlock. Specifically, `Table 8.5 <#tbl8-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.

.. [#f46] 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.

.. avembed:: Exercises/SynchProblems/SynchProbCigSumm.html ka
   :module: CigSmokers
   :points: 1.0
   :required: True
   :exer_opts: JXOP-debug=true&amp;JOP-lang=en&amp;JXOP-code=java
   :long_name: Cigarette Smokers Summary Questions
   :threshold: 3