.. _Barriers:

.. raw:: html

   <script>ODSA.SETTINGS.DISP_MOD_COMP = true;ODSA.SETTINGS.MODULE_NAME = "Barriers";ODSA.SETTINGS.MODULE_LONG_NAME = "Barriers";ODSA.SETTINGS.MODULE_CHAPTER = "Synchronization Primitives"; 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: 

Barriers
========

Semaphores provide a general mechanism that allows one thread to indicate that a
particular event has happened. One type of event that arises quite commonly in
concurrent applications is the need to make sure all threads reach some common
point before any of them continues on. That is, multiple threads may perform
some initial computation then pause; at that point some manager thread checks
these initial results and allows the threads to continue once their results have been approved.

As an example, consider the case of an autonomous car or flying drone. These
types of systems require accurate measurements of real-world phenomena like
speed, position, and acceleration. However, these measurements involve
floating-point calculations that may encounter rounding errors. To improve the
accuracy of the vehicle's autonomous controls, multiple threads may be
simultaneously and independently performing these calculations. The manager
control thread will occasionally require these threads to reach a common point
in time where each thread reports on its best guess of the measurements. The
manager may then correct errors in some threads, then allow them to continue.

Achieving this kind of synchronization with semaphores is complex and
error-prone. One approach would be to use two semaphores: the manager thread
would repeatedly wait on one of them as the threads were finishing their
calculations; the manager would then signal on a different semaphore that each
thread was waiting on. However, if all threads agree but one crashes, then the
entire system would fail; the manager thread would continue to wait on that last
thread to finish (which will never happen).

As an alternative, :term:`synchronization barriers <barrier>`
allow programs to specify a *minimum* number of threads that must reach a common
point before any can continue. For instance, if the autonomous vehicle manager
thread receives reports from 7 out of 10 threads about the current position,
then the system may be designed to consider this measurement *good enough* and
let the threads continue rather than requiring the last three threads to
finish.

The base functionality of barriers is specified with thread functions. The
barrier is initialized with ``pthread_barrier_init()``, with the last parameter
indicating the *minimum* number of threads that must reach the barrier before
any can be allowed to continue. Threads use the ``pthread_barrier_wait()``
function to indicate that they have reached the common point. If the minimum
number of threads have not yet reached the barrier, then the current thread will
become blocked. Once the minimum number has been reached, all threads waiting at
the barrier become unblocked; any future thread that calls
``pthread_barrier_wait()`` will pass right through the barrier without any
delay. Finally, ``pthread_barrier_destroy()`` is used to clean up any resources
associated with the barrier.

.. topic:: C library functions – <pthread.h>

   .. figure:: Images/CSF-Images-Library.png
      :align: left
      :width: 100%
      :alt: Decorative C library image

   ``int pthread_barrier_init (pthread_barrier_t *barrier, const pthread_barrierattr_t *attr, unsigned count);``
     Initialize a synchronization barrier with the specified attributes.

   ``int pthread_barrier_destroy (pthread_barrier_t *barrier);``
     Delete a synchronization barrier.

   ``int pthread_barrier_wait (pthread_barrier_t *barrier);``
     Make a thread wait until enough have reached the barrier.

Concurrent Calculations with Barriers
-------------------------------------

To show how barriers work, consider using two threads to determine which
function grows faster: the Fibonnacci sequence or the exponential function. That
is, is the 100th Fibonacci number greater than $c^{100}$ for some constant $c$? [#f43]_
It can be shown that each Fibonacci number is slightly less than double
the previous value, so the answer would be no for any constant integer greater
than 1. But what if the constant is 1.6? [#f44]_ Then the answer is not obvious,
but it is easy enough to calculate.

`Code Listing 7.13 <#cl7-13>`_ shows how barriers can address this problem. The
``fibonacci()`` and ``exponential()`` threads take a struct that contains a
shared ``pthread_barrier_t``, a digit that specifies how far into the sequence
and what exponent to calculate, and a base value that specifies the base of the
exponent. That is, if digit is specified as 30 and base is 1.6, ``fibonacci()``
will calculate the 30th Fibonacci number, while ``exponent()`` will calculate
(approximately) $1.6^{30}$.

.. _cl7-13:

.. codeinclude:: Synch/CodeListing-7-13.c
   :linenos: true

.. topic:: Bug Warning

   .. figure:: Images/CSF-Images-BugWarning.png
      :align: left
      :width: 90%
      :alt: Decorative bug warning

   As indicated in the code, you should not try to calculate the exponential value
   as shown in this code. For one thing, this code is (intentionally) inefficient
   and could be easily optimized. More importantly, though, the result is
   guaranteed to be inaccurate. Floating-point arithmetic is susceptible to
   rounding errors, particularly with repeated calculations and large values.
   Consequently, this example should primarily be considered for its use of
   barriers rather than its accuracy regarding the comparison of Fibonacci and
   exponential growth.

The key lines to note regarding these threads are the calls to
``pthread_barrier_wait()`` and the references to the fields ``fib`` and ``exp``,
which store the results of each calculation. Specifically, note that there is no
race condition regarding these fields because the threads only *read* the values
after the barrier. That is, nothing changes after the barrier, so there is no
concern that the values checked are inaccurate. This guarantee arises from the
fact that both threads must reach the barrier (i.e., the
``pthread_barrier_wait()`` call) before either can proceed.

One question that cannot be answered with this code is which thread runs faster.
With barriers, all we can say for sure is that both threads reach the barrier
before either proceeds. We have no information about which one arrived first.
From the perspective of the barrier, such a question is irrelevant. The only
thing that matters is that both finish before they each check the results.

`Code Listing 7.14 <#cl7-14>`_ shows the initialization required. The main
thread initializes the barrier so that 2 threads are required, then creates the
threads. Notice that both threads receive pointers to the same ``struct``
instance, so they share the same ``barrier``, ``fib``, and ``exp`` fields. The
main thread joins both of the helper threads, but the join must occur after the
threads have called ``pthread_exit()``. Since both threads call
``pthread_barrier_wait()`` before that, the main thread is guaranteed to clean
up the barrier only *after* it is no longer needed.

.. _cl7-14:

.. codeinclude:: Synch/CodeListing-7-14.c
   :linenos: true

.. [#f43] To be clear, the ``exponential()`` function is truly the exponential
   $c^n$ rather than the polynomial $n^c$. In both ``exponential()`` and
   ``fibonacci(),`` we are using $n = 100$.

.. [#f44] The selection of 1.6 as the value was not an arbitrary choice. There
   is a closed-form solution known as Binet's formula, and calculations based on
   this formula can be done to show that each Fibonacci number is approximately
   1.6 times the value of the previous number.

.. avembed:: Exercises/Synch/SynchBarrierSumm.html ka
   :module: Barriers
   :long_name: Barrier questions
   :threshold: 2