.. _SynchProblemsOverview:

.. raw:: html

   <script>ODSA.SETTINGS.DISP_MOD_COMP = true;ODSA.SETTINGS.MODULE_NAME = "SynchProblemsOverview";ODSA.SETTINGS.MODULE_LONG_NAME = "Synchronization Patterns and Problems";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: Synchronization Problems Introduction
   :topic: Synchronization Problems

Synchronization Patterns and Problems
=====================================

.. figure:: Images/CSF-Timeline.8.png
   :align: center
   :width: 90%
   :figwidth: 100%
   :alt: Timeline of major CSF topics with Multicore and Threads highlighted

.. raw:: html

    <blockquote class="blockquote text-center">
        <p>“If you’re not failing 90% of the time, then you’re probably not
        working on sufficiently challenging problems.”
        <footer class="blockquote-footer">Alan Kay</footer>
    </blockquote>

From the earliest work on synchronization, it became clear that there were common software patterns
that could solve key timing issues and race conditions that frequently occurred. Edsger Dijkstra
characterized one such pattern as the Dining Philosophers problem in 1965. Tony Hoare—while working
on his Communicating Sequential Processes (CSP) language to support formal analysis of
concurrency—revisited this problem in 1985 and defined the standard version of it. Solutions for
these types of synchronization problems are powerful and reusable techniques for creating robust and
safe implementations of concurrent software.

.. topic:: Chapter Objectives

   .. figure:: Images/CSF-Images-Objectives.png
      :align: left
      :figwidth: 5%
      :width: 100%
      :alt: Decorative chapter objectives image

   In this chapter, we will address the following instructional objectives:

   * We will illustrate several design patterns that can be used for simple
     synchronization tasks.
   * We will examine classical synchronization problems that have been studied
     extensively, with well-known solutions.
   * We will highlight classical synchronization problems that demonstrate the
     limitations of basic synchronization primitives.
   * We will consider additional synchronization problems with more complex
     requirements that can be mapped to simpler design patterns.

:term:`Race condition` bugs can be extremely difficult to diagnose and fix.
Observing these bugs depends on the programmer's ability to reconstruct the
timing that makes the bug manifest. This task becomes even more difficult when
the bug is caused by the interaction of multiple system components that may or
may not be under that programmer's control. Fortunately, many common tasks in
concurrent software are simple in nature and can be achieved by applying basic
synchronization design patterns with semaphores, locks, or other
:term:`synchronization primitives <synchronization primitive>`. Other tasks are
variations on well-known :term:`synchronization problems <synchronization problem>`.
These problems tend to have an underlying structure that has a known solution
that provides safe and efficient execution.

This chapter will focus on known solutions to common tasks that arise in
concurrent software. We will describe the scenarios in which these design
patterns and solutions apply and provide informal explanations of why they work.
For the more complex problems, we will consider how the requirements can be
decomposed into pieces that map to the more basic design patterns.


