.. _Semaphores:
.. 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:
Semaphores
==========
:term:`Semaphores ` are a flexible synchronization primitive that can
be used for many purposes. They can be used as a form of message-passing IPC to
allow processes to synchronize access to shared memory or memory-mapped files.
But in contrast to other forms of IPC, semaphores can be used for thread
synchronization, as well.
As described previously, a semaphore is a non-negative integer with atomic
operations for incrementing and decrementing its value. The POSIX function for
decrementing the semaphore is ``sem_wait()``, while the ``sem_post()`` function
increments the value. If the semaphore's value is 0 prior to decrementing, then
the ``sem_wait()`` operation will block the current thread. If a thread calls
``sem_post()`` and there is at least one thread waiting on the semaphore, then
one of the threads becomes unblocked. The choice of which thread gets unblocked
is implementation dependent.
.. topic:: C library functions –
.. figure:: Images/CSF-Images-Library.png
:align: left
:width: 100%
:alt: Decorative C library image
``int sem_wait (sem_t *sem);``
Decrement the semaphore's value; block if the value is currently 0.
``int sem_post (sem_t *sem);``
Increment the semaphore's value; resume another process if the value is 0.
In this section, we'll describe three basic techniques of using semaphores:
signaling, mutual exclusion, and multiplexing. In essence, all of these
techniques look identical, but with one exception: the initial value. For
signaling, the semaphore is initialized to 0; for mutual exclusion, the initial
value is 1; for multiplexing, the initial value is a positive number greater
than 1. To summarize, the general practice is that **the initial value of the
semaphore is the desired number of initial allowed concurrent accesses**.
Semaphores as Signaling
-----------------------
Semaphores can be used to send general signals to other threads that some
application-specific event has occurred. Note that this use of semaphores is
different from the pre-defined :term:`signals ` such as ``SIGKILL``.
Events with semaphores have no pre-defined meaning and are simply indications
that *something* has occurred.
To illustrate signaling, consider the two threads shown in `Code Listing 7.7
<#cl7-7>`_. One thread (``keyboard_listener()``) reads a line of input from
``STDIN`` into a shared buffer. Once the input has been received, the thread
posts to the semaphore to alert the second thread that the event (receiving
input) has occurred. The second thread (``keyboard_echo()``) starts by waiting
on the semaphore before trying to read the input from the buffer. The semaphore
ensures that the echo thread cannot try to read from the buffer until the
listener has finished writing to the buffer.
.. _cl7-7:
.. codeinclude:: Synch/CodeListing-7-7.c
:linenos: true
The key with signaling is that the semaphore must be created and initialized
with an initial value of 0 as shown in `Code Listing 7.8 <#cl7-8>`_. By using
this initial value, the semaphore eliminates the issue of nondeterministic
thread scheduling. Specifically, if the ``keyboard_echo()`` thread runs first,
it must wait until the ``keyboard_listener()`` reads the input and ups the
semaphore. However, if ``keyboard_listener()`` runs first and ups the semaphore
before ``keyboard_echo()`` gets scheduled, then the semaphore will have a value
of 1 and the thread will not be blocked.
.. _cl7-8:
.. codeinclude:: Synch/CodeListing-7-8.c
:linenos: true
.. topic:: Bug Warning
.. figure:: Images/CSF-Images-BugWarning.png
:align: left
:width: 90%
:alt: Decorative bug warning
In this basic signaling pattern, it is possible to have the two threads
repeatedly post to or wait on a single semaphore. This approach is a common
technique for handling repeated events. However, it is fraught with peril. In
this example, there is only one buffer. So if the ``keyboard_listener()``
repeatedly reads input (posting each time), the buffer would be repeatedly
overwritten, and there is no guarantee that the ``keyboard_echo()`` thread
would read any of the input.
Another complication arises if there are multiple threads repeatedly waiting on
the same semaphore. In the default implementation of POSIX semaphores, the
order in which threads are unblocked with ``sem_post()`` is unspecified. As
such, it is possible that one thread might be repeatedly unblocked while the
other waiting thread is never unblocked.
Mutual Exclusion with Semaphores
--------------------------------
Semaphores can also be used to ensure mutually exclusive access to a shared
variable or resource. Consider the two threads, shown in `Code Listing 7.9
<#cl7-9>`_, that atomically increment or decrement an int counter variable. Each
change to the shared variable is preceded by a call to ``sem_wait()`` and
followed by a call to ``sem_post()``. This wrapping is analogous to the mutual
exclusion style used with locks.
.. _cl7-9:
.. codeinclude:: Synch/CodeListing-7-9.c
:linenos: true
As shown in `Code Listing 7.10 <#cl7-10>`_, the difference between signaling and
mutual exclusion is the initial value of the semaphore. For mutual exclusion,
the semaphore is initialized to 1.
.. _cl7-10:
.. codeinclude:: Synch/CodeListing-7-10.c
:linenos: true
As illustrated in `Code Listing 7.9 <#cl7-9>`_, semaphores can be used
identically to mutex locks as shown previously. In fact, `Code Listing 7.11
<#cl7-11>`_ shows that we can use semaphores as a foundation to create locks.
Acquiring the lock involves waiting on the semaphore and setting oneself as the
lock owner. Releasing the lock clears the ownership field and posts to the
semaphore. If multiple threads try to acquire the lock, they all end up trying
to down the semaphore, and only one is successful. Once that thread releases the
lock, the semaphore is upped and a single thread is unblocked; that thread then
sets itself as the owner.
.. _cl7-11:
.. codeinclude:: Synch/CodeListing-7-11.c
:linenos: true
The key difference between locks and semaphores is that a semaphore must be
explicitly initialized to the integer value 1, whereas the initialization for a
lock is opaque. Or, put a different way, **mutex locks are preferred because
they adhere to the principles of encapsulation and information hiding**. The
notion of *acquiring a lock* is more concrete than *waiting on a semaphore,* and
is a more appropriate abstraction for mutual exclusion.
Multiplexing with Semaphores
----------------------------
Both locks and semaphores can be used for mutual exclusion, though locks are
typically the preferred abstraction. However, the mutual exclusion style of
semaphores can be extended to allow for multiple but limited shared accesses.
This concept is known as :term:`multiplexing `. That is, while a lock can only be
used to grant access to a single thread at a time, a semaphore can be set to
allow 5, 10, or any other number of concurrent accesses. Once this limited
number has been reached, any additional threads would become blocked, just as
they would if trying to acquire a locked mutex.
As a real-world example of multiplexing, consider a popular restaurant or club.
Building safety codes specify that there is a maximum occupancy, say 100 people.
As patrons start arriving when the place opens, they are allowed in one at a
time. However, once the 100th person has been allowed in, the management must
make sure that no one else enters (or risk legal trouble and fines). At that
point, a line forms out front. Once a single person leaves, the next patron is
allowed in. In this case, **the employee enforcing this restriction at the
entrance is acting like a multiplexing semaphore with an initial value of 100**.
Within the context of computing, multiplexing has many uses. One example is to
limit the number of concurrent accesses to a pool of resources where more than
one is required for each operation. For example, consider a networking hub that
has 10 incoming ports and 10 outgoing ports that can be locked independently.
Consider the scenario where 9 threads have already locked both an incoming and
an outgoing port. Two new threads arrive; one of them acquires an incoming port
and the second acquires an outgoing port. At this point, no ports of either kind
are available. If these last two threads then try to acquire the missing port,
they cannot. As a result, there are two ports (one incoming and one outgoing)
that are both locked but not in use. This waste of resources could be prevented
with the structure in `Code Listing 7.12 <#cl7-12>`_.
.. _cl7-12:
.. codeinclude:: Synch/CodeListing-7-12.c
:linenos: true
Assuming the ``pool_semaphore`` was initialized to 10, every thread granted
access to the pool of resources (ports in this example) will have access to one
of each type. Moreover, this structure makes it possible for the incoming and
outgoing ports to be acquired in any order; this flexibility is commonly
associated with the problem of :term:`deadlock`, but multiplexing in this manner
avoids that issue.
.. avembed:: Exercises/Synch/SynchSemsSumm.html ka
:module: Semaphores
:points: 1.0
:required: True
:exer_opts: JXOP-debug=true&JOP-lang=en&JXOP-code=java
:long_name: Semaphore questions
:threshold: 3