.. _SynchDesign:
.. raw:: html
.. |--| 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:
Basic Synchronization Design Patterns
=====================================
:term:`Locks ` are very simple synchronization primitives, as they have
only one intended purpose: ensuring mutually exclusive access to a critical
section. Other primitives, such as :term:`semaphores `, can also
provide mutual exclusion. However, semaphores are flexible and can be used for a
variety of synchronization goals. This section describes four common techniques.
Signaling
---------
The simplest synchronization design pattern uses semaphores for :term:`signaling `.
Signaling arises when one thread needs to wait until some particular event has
occurred. This timing is accomplished by waiting on shared semaphore that is
incremented immediately after the event.
* Initialize the semaphore to 0.
* One thread calls ``sem_wait()`` to block until some critical event has occurred.
* A second thread detects that the event has occurred, then calls ``sem_post()`` to
unblock the waiting thread.
The key observation with signaling is that the scheduling of the threads does
not affect the correctness of the results. That is, there are only two possible
scenarios to consider. In one scenario, the thread that calls ``sem_wait()``
runs first. Since the semaphore is initialized to 0, the thread must block until
the other thread runs and calls ``sem_post()``. Alternatively, the second thread
runs first and calls ``sem_post()``, incrementing the semaphore's value to 1.
Then, when the other thread calls ``sem_wait()``, it can proceed without
blocking because the event has already occurred.
`Code Listing 8.1 <#cl8-1>`_ uses a separate thread to perform some sort of
initialization work. For instance, this initialization might involve reading in
a large amount of data from configuration files, allocating request queues,
overwriting the default signal handlers, or other such tasks. This
initialization may be done concurrently with other work that the main thread is
trying to accomplish. But at a certain point, the main thread needs to pause
until it can be guaranteed that all of the initialization is done. The semaphore
guarantees the timing of this pause.
.. _cl8-1:
.. codeinclude:: SynchProblems/CodeListing-8-1.c
:linenos: true
The use of the semaphore here may seem unnecessary, and that would be a fair
objection to this particular scenario. That is, the same timing could be
achieved by having the main thread call ``pthread_join()`` when it needs to wait
for the initialization thread to complete. However, using the semaphore allows
the initialization thread to signal that the critical work has been done
*before* the thread finishes. This early notification may be beneficial if the
thread needs to perform additional work, such as freeing up allocated memory or
cleaning up files. Furthermore, there may be other threads that are also waiting
on the initialization; since they are not the thread's parent, they cannot join
it and must be signaled using a mechanism such as a semaphore.
Turnstiles
----------
A :term:`turnstile` is a variant on signaling that can cause a chain-reaction
that unblocks several threads one at a time. The key structure of a turnstile is
to follow ``sem_wait()`` immediately with a call to ``sem_post()``. As with
signaling, the semaphore must be initialized to 0, which ensures that every
thread executing the turnstile gets blocked. That is, the turnstile acts like a
locked door and the threads form a queue waiting to get in.
Once it becomes acceptable for the threads to enter, one thread makes a single
call to ``sem_post()``. This call unblocks exactly one thread that is waiting at
the turnstile; that thread returns from the ``sem_wait()`` that had blocked it
and immediately calls ``sem_post()``, unblocking the next thread. This pattern
then continues, with each thread unblocking the next thread in line, one at a
time. `Code Listing 8.2 <#cl8-2>`_ illustrates this pattern, with the ``user()``
waiting at the turnstile.
.. _cl8-2:
.. codeinclude:: SynchProblems/CodeListing-8-2.c
:linenos: true
Turnstiles allow POSIX semaphores to behave similar to the broadcast feature of
:term:`condition variables ` or using the System V
``semop()`` function to increase a semaphore by more than 1. There is a key
difference that distinguishes the intended use of turnstiles, though. Turnstiles
cause the unblocking to propagate to all threads that are waiting at the
turnstile, but also those that have not arrived yet. Broadcasting only notifies
threads that are already waiting, and ``semop()`` unblocks a maximum of the
number of threads specified by the ``sem_op`` argument. In other words,
turnstiles permanently unblock all current and future threads based on a key event.
Rendezvous
----------
A :term:`rendezvous` is a mutual signaling between two threads. The goal of a rendezvous is to ensure that two threads meet at a pre-defined common point. To create a rendezvous, two semaphores are initialized to 0. The two threads then call ``sem_post()`` on one semaphore just prior to calling ``sem_wait()`` on the other. At run-time, one thread will arrive at the rendezvous first and get blocked by the call to ``sem_wait()``. Then, when the other thread arrives, it unblocks the first by calling ``sem_post()``; however, this thread is not blocked by the call to ``sem_wait()``, as the semaphore's value has already been incremented to 1.
To illustrate the use of a rendezvous, assume that a program wants to detect corrupted files on a web server. To do this, the program uses one thread to retrieve the file from the web site; a second thread reads the same file from a location that is known to be secure and correct. The two threads need to complete reading the two copies before comparing their contents (a mismatch would indicate corruption). `Code Listing 8.3 <#cl8-3>`_ shows the structure for these two threads.
.. _cl8-3:
.. codeinclude:: SynchProblems/CodeListing-8-3.c
:linenos: true
Multiplexing
------------
In many cases, mutual exclusion is too strong of a system requirement, but it is reasonable to place a limit on the number of concurrent accesses. For example, network servers (e.g., web or e-mail servers) allow hundreds or thousands of concurrent network connections to serve content to remote users. Allowing an unlimited number of connections would exhaust the system resources, such as consuming all of the system's available memory or trying to read too many files on a single hard drive.
The solution in this case is :term:`multiplexing `. Multiplexing allows multiple concurrent accesses up to a given limit; additional requests beyond that limit are blocked until more resources become available. The key defining feature of multiplexing is to initialize the semaphore's value to a positive integer greater than 1. This initial value is the *maximum* number of concurrent accesses allowed. Once the thread semaphore has been decremented to 0, the limit has been reached and future accesses are blocked. Mutual exclusion is a special case of multiplexing, where the initial value is 1.
`Code Listing 8.4 <#cl8-4>`_ illustrates the code framework for a server that launches a new thread each time a request has been received. Whenever a request is received, the main thread first decrements the semaphore to determine if the limit has been reached. If the limit has not been reached, a new thread handles the request. However, if the maximum number of threads has already been reached, the main thread gets blocked. Eventually, one of the threads serving content finishes. Just before exiting, that thread increments the semaphore, which unblocks the main thread; at that point, the main thread creates a new thread to handle the pending request it had received.
.. _cl8-4:
.. codeinclude:: SynchProblems/CodeListing-8-4.c
:linenos: true
Lightswitches
-------------
When providing concurrent access to a resource, it is sometimes necessary to
distinguish between the type of threads that are allowed access. For instance,
consider a web-based application that allows multiple people to edit a document
collaboratively. Each user is assigned a separate thread for modifying the
contents of the document. In addition, a separate thread is responsible for
storing a backup copy automatically. Other threads might be running to check the
spelling or grammar. When there are different types of threads, it may be
necessary for one type of thread to lock out other types while still allowing
concurrent access for the same type.
The :term:`lightswitch` pattern makes it possible to enforce this type of
constraint. In addition, the lightswitch allows the first thread of a particular
type to perform some initialization as needed. The name derives from the idea of
a group of people entering a room; the first person to enter turns on the lights
by flipping the lightswitch and the last person to leave turns the lights off.
`Code Listing 8.5 <#cl8-5>`_ shows one variant on a lightswitch. Note that the
``if`` statement in both cases can be extended to perform additional
initialization and clean-up work if needed.
.. _cl8-5:
.. codeinclude:: SynchProblems/CodeListing-8-5.c
:linenos: true
The implementation in `Code Listing 8.5 <#cl8-5>`_ works for an *asymmetric*
approach in which one type of thread allows concurrent access while another does
not. The ``enter()`` and ``leave()`` functions would be used by the thread type
that allows concurrency. The thread type that requires mutual exclusion would
work directly with the ``can_enter`` semaphore without using the lock. That is, the
lightswitch could be used as shown in `Code Listing 8.6 <#cl8-6>`_.
.. _cl8-6:
.. codeinclude:: SynchProblems/CodeListing-8-6.c
:linenos: true
.. topic:: Bug Warning
.. figure:: Images/CSF-Images-BugWarning.png
:align: left
:width: 90%
:alt: Decorative bug warning
The lightswitch in `Code Listing 8.6 <#cl8-6>`_ is not safe if all types of
threads allow for concurrent access to their respective critical sections.
Consider the case where a thread of type A has previously entered. After that
point, a thread of type B tries to enter, but is blocked by the semaphore
within the ``if`` statement. Note, though, that this thread still retains the
lock as it gets blocked. When any type A thread tries to leave, they will get
blocked trying to acquire the lock. Consequently, none of the type A threads
can post to the semaphore according to the ``leave()`` function. The system
would then enter a state of :term:`deadlock`, as the type A threads are waiting
on the type B thread that has the lock while the type B thread is waiting on a
type A thread to post to the semaphore.
If the concurrency is not asymmetric—that is, multiple types of threads allow
concurrent access—then the ``if`` statement would need to be modified. Using the
structure in `Code Listing 8.5 <#cl8-5>`_, the ``enter()`` function could be
modified to release the lock prior to calling ``sem_wait(can_enter)``, then
re-acquiring it as shown in `Code Listing 8.7 <#cl8-7>`_. Note that the
``leave()`` function remains unchanged, as ``sem_post(can_enter)`` would
never block.
.. _cl8-7:
.. codeinclude:: SynchProblems/CodeListing-8-7.c
:linenos: true
As an alternative, the lightswitch could be modified to use condition variables
as shown in `Code Listing 8.8 <#cl8-8>`_. In this case, a bool variable is added
to indicate whether or not a new type of thread can enter its respective
critical section. When the first thread of a new type enters the critical
section, it would set ``can_enter`` to false, blocking out other threads that
would try to enter until the last leaving thread sets ``can_enter`` back to true.
.. _cl8-8:
.. codeinclude:: SynchProblems/CodeListing-8-8.c
:linenos: true
Given that the lightswitch pattern is more complex than the other patterns, it
is a good design choice to encapsulate the variables into a single ``struct``
that can then be passed around. Any thread needing access to the same
lightswitch could be passed a pointer to the ``struct`` instance in the thread
arguments as shown in `Code Listing 8.9 <#cl8-9>`_. Note that this assumes the
interface for ``enter()`` and ``leave()`` have been adapted to receive the
struct parameter instead of the individual fields.
.. _cl8-9:
.. codeinclude:: SynchProblems/CodeListing-8-9.c
:linenos: true
.. avembed:: Exercises/SynchProblems/SynchProbDesignSumm.html ka
:module: SynchDesign
:points: 1.0
:required: True
:exer_opts: JXOP-debug=true&JOP-lang=en&JXOP-code=java
:long_name: Synchronization Problem Design Patterns Summary Questions
:threshold: 5
.. .. inlineav:: LinearRecurrencesCON ss
.. :long_name: Linear Recurrences Slideshow
.. :links: AV/Background/LinearRecurrencesCON.css
.. :scripts: AV/Background/LinearRecurrencesCON.js
.. :output: show