.. _DiningPhil:

.. raw:: html

   <script>ODSA.SETTINGS.DISP_MOD_COMP = true;ODSA.SETTINGS.MODULE_NAME = "DiningPhil";ODSA.SETTINGS.MODULE_LONG_NAME = "Dining Philosophers Problem and Deadlock";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: 

Dining Philosophers Problem and Deadlock
========================================

The previous chapter introduced the concept of :term:`deadlock`. Deadlock is the
permanent blocking of two or more threads based on four necessary conditions.
The first three are general properties of synchronization primitives that are
typically unavoidable. The last is a system state that arises through a sequence
of events.

   * :term:`Mutual exclusion`: Once a resource has been acquired up to its
     allowable capacity, no other thread is granted access.
   * :term:`No preemption`: Once a thread has acquired a resource, the
     resource cannot be forcibly taken away. For instance, only the owner of a mutex
     can unlock it.
   * :term:`Hold and wait`: It is possible that a thread can acquire one
     resource and retain ownership of that resource while waiting on another.
   * :term:`Circular wait`: One thread needs a resource held by another, while
     this second thread needs a different resource held by the first.

.. _DiningPhil:

.. figure:: Images/CSF-Images.8.3.png
   :align: right
   :width: 90%
   :figwidth: 30%
   :alt: Providing the same number of plates and forks creates a problem for a set
         of dining philosophers

   Providing the same number of plates and forks creates a problem for a set of
   dining philosophers

The :term:`dining philosophers problem` is a metaphor that illustrates the
problem of deadlock. The scenario consists of a group of philosophers sharing a
meal at a round table. As philosophers, they like to take some time to think;
but they are at a meal, so they also need to eat. As illustrated in
:num:`Figure #DiningPhil`, there is a large serving dish in the middle of the table.
Every philosopher has a plate and two serving forks, one to their right and one
to their left. When a philosopher decides that they are hungry enough, they stop
thinking and grab the forks to serve themselves from the serving dish in the middle.

The problem arises when all of the philosophers decide to eat at the same time.
Consider the case where all of the philosophers independently decide that they
will try to grab the fork to their left first. When this happens, assuming all
of the places at the table are occupied, then all of the forks have been taken.
That is, each of the five forks shown are to the left of exactly one of the five
philosophers. At this point, every philosopher has exactly one fork, but there
are none available for anyone to get their second fork. Unless one of the
philosophers decides to give up on eating and put a fork down, all of the
philosophers will starve.

`Code Listing 8.24 <#cl8-24>`_ illustrates how this scenario translates into
code with semaphores. Multiple *philosopher* threads share an array of N *fork*
semaphores (numbered 0 through N-1) and each thread tries to acquire two of
them. Thread 0 waits on semaphores 0 and 1, thread 1 waits on semaphores 1 and
2, and so on, until thread N-1 waits on semaphores N-1 and 0 (since the modulus
operator is applied).

.. _cl8-24:

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

Assuming they are initialized to 1 and the standard ``sem_wait()`` is used,
semaphores exhibit the three required system features of deadlock. They enforce
mutual exclusion because the second thread to attempt to down the semaphore will
become blocked since the internal value would be negative. Since the threads can
acquire one and get blocked trying to acquire the second semaphore, they satisfy
the hold-and-wait criterion. And since no thread can break another thread's
claim to a semaphore, the no preemption criterion is met. The fourth criterion
for deadlock, circular wait, arises from the sequence in which the threads wait
on the respective semaphores. Every philosopher is waiting on the fork to their
right, which has been grabbed by someone else as their left fork. 

.. topic:: Example

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

   `Table 8.1 <#tbl8-1>`_ illustrates how the circular wait arises. Every thread
   successfully waits on one semaphore and gets blocked by the second.

   .. _tbl8-1:

   .. raw:: html

      <center>
      <table class="table table-bordered">
        <thead class="thead-light">
          <tr>
            <th class="py-0 center">Thread 0</th>
            <th class="py-0 center">Thread 1</th>
            <th class="py-0 center">Thread 2</th>
            <th class="py-0 center">Thread 3</th>
            <th class="py-0 center">Thread 4</th>
          </tr>
        </thead>
        <tbody>
          <tr>
            <td class="py-0">sem_wait(0);<br />&nbsp;&nbsp;
              SUCCESS<br />sem_wait(1);<br />&nbsp;&nbsp; BLOCKED</td>
            <td class="py-0">sem_wait(1);<br />&nbsp;&nbsp;
              SUCCESS<br />sem_wait(2);<br />&nbsp;&nbsp; BLOCKED</td>
            <td class="py-0">sem_wait(2);<br />&nbsp;&nbsp;
              SUCCESS<br />sem_wait(3);<br />&nbsp;&nbsp; BLOCKED</td>
            <td class="py-0">sem_wait(3);<br />&nbsp;&nbsp;
              SUCCESS<br />sem_wait(4);<br />&nbsp;&nbsp; BLOCKED</td>
            <td class="py-0">sem_wait(4);<br />&nbsp;&nbsp;
              SUCCESS<br />sem_wait(0);<br />&nbsp;&nbsp; BLOCKED</td>
          </tr>
        </tbody>
      </table>
      <p>
      Table 8.1: If all threads get through the first semaphore, no one gets by the second
      </p>
      </center>

It is important to note that this problem applies to other synchronization
primitives, not just semaphores. That is, locks and condition variables also
meet the system requirements for deadlock. To illustrate how this problem could
arise in practice with locks, consider the software that links incoming and
outgoing connections in a network switch. In this scenario, assume that each
thread responsible for forwarding data packets acquires locks on dedicated
physical ports. As such, the software maintains an array of locks ``nic_locks``.
There is no assumption that the ports need to be adjacent; instead, the switch
code just grabs any two that are available. `Code Listing 8.25 <#cl8-25>`_ shows
a simplistic approach that fits the dining philosophers structure. The first
loop iterates through the locks until one is assigned to be this thread's
incoming port; the second loop acquires the outgoing port. To make matters
worse, these two loops may be in different portions of the code base, so someone
reviewing the code **may not think they are actually connected in this way**!

.. _cl8-25:

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

Solution of Limiting Accesses
-----------------------------

One approach to solving the dining philosophers problem is to employ a
multiplexing semaphore to limit the number of concurrent accesses. To return to
the original metaphor, this solution would require that one of the seats at the
table must always remain unoccupied. Assuming all of the philosophers try to
grab their left fork first, the fork to the left of the empty seat would not be
claimed. Consequently, the philosopher to the left of that seat could grab the
fork as their second, as it is the fork to their left. After this philosopher
eats, they can put both forks down, making their left fork available as the
right fork for the next philosopher.

`Code Listing 8.26 <#cl8-26>`_ shows how to incorporate this approach into the
structure of `Code Listing 8.24 <#cl8-24>`_. A single additional semaphore
(``can_sit``) is created and initialized to N-1 for N semaphores. This semaphore
prevents all N semaphores from being decremented by the first call to
``sem_wait()``. As such, there must be at least one semaphore that can be
decremented by the second call, guaranteeing one thread enters the critical
section. Once that thread leaves, it increments its *fork* semaphores and the
new semaphore, allowing a new thread to enter.

.. _cl8-26:

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

.. topic:: Example

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

   At first glance, it may appear that placing the call to ``sem_post()`` before
   the critical section could still allow the same problem as before.
   Specifically, this structure allows N calls to ``sem_wait()``, just as the
   original version did. However, the order of the outcomes is different, as
   highlighted in `Table 8.2 <#tbl8-2>`_. If thread 1 was initially blocked by the
   multiplexing semaphore, thread 0 is able to call ``sem_wait(1)`` successfully
   first. This order of events breaks the circular wait.

   .. _tbl8-2:

   .. raw:: html

      <center>
      <table class="table table-bordered">
        <thead class="thead-light">
          <tr>
            <th class="py-0 center">Thread 0</th>
            <th class="py-0 center">Thread 1</th>
            <th class="py-0 center">Thread 2</th>
            <th class="py-0 center">Thread 3</th>
            <th class="py-0 center">Thread 4</th>
          </tr>
        </thead>
        <tbody>
          <tr>
            <td class="py-0">sem_wait(0);<br />&nbsp;&nbsp;
              SUCCESS<br />sem_wait(1);<br />&nbsp;&nbsp; <b><i>SUCCESS</i></b></td>
            <td class="py-0">sem_wait(1);<br />&nbsp;&nbsp; <b><i>BLOCKED</i></b></td>
            <td class="py-0">sem_wait(2);<br />&nbsp;&nbsp;
              SUCCESS<br />sem_wait(3);<br />&nbsp;&nbsp; BLOCKED</td>
            <td class="py-0">sem_wait(3);<br />&nbsp;&nbsp;
              SUCCESS<br />sem_wait(4);<br />&nbsp;&nbsp; BLOCKED</td>
            <td class="py-0">sem_wait(4);<br />&nbsp;&nbsp;
              SUCCESS<br />sem_wait(3);<br />&nbsp;&nbsp; BLOCKED</td>
          </tr>
        </tbody>
      </table>
      <p>
      Table 8.2: The multiplexing semaphore changes where threads get blocked
      </p>
      </center>


Solution by Breaking Hold-and-wait
----------------------------------

There are times where the previous approach would not be optimal, particularly
if there is a large gap between the two calls to ``sem_wait()`` in the initial
approach. For instance, if we consider the scenario described in `Code Listing
8.25 <#cl8-25>`_, the threads might retrieve a large amount of data from their
incoming port before locking an outgoing port. The multiplexing approach would
reduce the number of threads that can perform this initial work until at least
one gets past the second semaphore. Depending on the needs of the specific
application, this delay may be undesirable.

`Code Listing 8.27 <#cl8-27>`_ outlines a different approach focused on breaking
the hold-and-wait criterion. Rather than using ``sem_wait()`` on the second
semaphore, ``sem_try_wait()`` provides a mechanism to detect the failure without
blocking. If the semaphore is successfully decremented, the thread continues as
normal. However, if the decrement would cause the thread to block, it posts to
the first semaphore and starts over from scratch. In the terms of the dining
philosopher scenario, if someone fails to grab their right fork they would put
their left fork back down and try again. In the meantime, the philosopher to
their left could grab the fork before it is picked back up.

.. _cl8-27:

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

This approach depends on the work that is done between waiting on the two
semaphores. If the initial work cannot be undone, it is not clear what should be
done if the ``sem_try_wait()`` fails. One possibility would be simply to discard
the partial results, which may be acceptable in some cases. As an example of
where this is true, consider a streaming media player. Partial results can
happen when some but not all of the data packets have arrived; the result may be
that the player switches to a low-resolution form (creating pixelated images) or
switches to audio only.

On the other hand, consider a financial database where the initial work is to
withdraw money from one account. After waiting on the second semaphore (if
successful), the money would be deposited in a second account. However, if the
``sem_try_wait()`` fails and the withdraw cannot be undone, the money would be
lost. This is clearly not an acceptable result. As such, this approach should be
used only in cases where it is clear that the initial work can be undone or
discarded safely.

Solution by Imposing Order
--------------------------

A third possibility for solving the dining philosophers problem is to impose a linear ordering on the semaphores. This order could be imposed by requiring ``i < j`` anytime ``sems[i]`` is accessed before ``sems[j]``. As before, thread 0 would wait on semaphores 0 and 1 (in that order), thread 1 would wait on semaphores 1 and 2, and so on. However, the last thread would have a different ordering. If there are N semaphores (numbered 0 through N-1), the last thread would have to wait on semaphore 0 before semaphore N-1 to adhere to the linear ordering. `Code Listing 8.28 <#cl8-28>`_ shows how this order can be imposed by adding a single ``if`` statement.

.. _cl8-28:

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

.. topic:: Example

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

   To visualize how this change affects the outcomes to prevent deadlock, consider
   the highlights in `Table 8.3 <#tbl8-3>`_. Since thread 4 must adhere to the
   linear order, it must try to wait on semaphore 0 before it can wait on
   semaphore 4. Assuming thread 0 arrived earlier and decremented semaphore 0
   successfully as shown, thread 4 becomes blocked from the start. Consequently,
   thread 3 is successful in decrementing semaphore 4. The linear ordering
   prevents the circular wait that would cause deadlock.

   .. _tbl8-3:

   .. raw:: html

      <center>
      <table class="table table-bordered">
        <thead class="thead-light">
          <tr>
            <th class="py-0 center">Thread 0</th>
            <th class="py-0 center">Thread 1</th>
            <th class="py-0 center">Thread 2</th>
            <th class="py-0 center">Thread 3</th>
            <th class="py-0 center">Thread 4</th>
          </tr>
        </thead>
        <tbody>
          <tr>
            <td class="py-0">sem_wait(0);<br />&nbsp;&nbsp;
              SUCCESS<br />sem_wait(1);<br />&nbsp;&nbsp; BLOCKED</td>
            <td class="py-0">sem_wait(1);<br />&nbsp;&nbsp;
              SUCCESS<br />sem_wait(2);<br />&nbsp;&nbsp; BLOCKED</td>
            <td class="py-0">sem_wait(2);<br />&nbsp;&nbsp;
              SUCCESS<br />sem_wait(3);<br />&nbsp;&nbsp; BLOCKED</td>
            <td class="py-0">sem_wait(3);<br />&nbsp;&nbsp;
              SUCCESS<br />sem_wait(4);<br />&nbsp;&nbsp; <b><i>SUCCESS</i></b></td>
            <td class="py-0">sem_wait(0);<br />&nbsp;&nbsp;
              <b><i>BLOCKED</i></b><br />sem_wait(4);</td>
          </tr>
        </tbody>
      </table>
      <p>
      Table 8.3: Thread 4 gets blocked by semaphore 0, allowing thread 3 to proceed
      </p>
      </center>

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