.. _ReadWrite:

.. raw:: html

   <script>ODSA.SETTINGS.DISP_MOD_COMP = true;ODSA.SETTINGS.MODULE_NAME = "ReadWrite";ODSA.SETTINGS.MODULE_LONG_NAME = "Readers-Writers Problem";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: 

Readers-Writers Problem
=======================

The :term:`readers-writers problem` illustrates a second common pattern in
concurrent software. In this problem, multiple readers are sharing concurrent
access to a resource. Unlike the consumers in the producer-consumer problem, the
readers *do not change* the shared resource in any way; the reader retrieves a
copy of the data, but the original shared copy remains intact. In addition to
the readers, one or more writers are responsible for modifying the data.

To illustrate the readers-writers problem, consider a web-based e-commerce
application. This application is built on a multithreaded server that assigns
requests to distinct threads. Some threads are queries that are requesting
information about the company's available products, their prices, and so on. As
these requests do not modify the inventory or create purchase orders, these
threads are acting as readers. On the other hand, some threads are processing
requests to insert a new order; other threads are initiated from the delivery
team to update the inventory and to indicate that an order has been shipped.
These threads are writers.


A Solution Using Lightswitches
------------------------------

One common solution for the readers-writers problem aligns with the asymmetric
lightswitch described previously. As the readers allow concurrent access, the
reader thread would use the ``enter()`` and ``leave()`` routines to access the
shared resource. The writers, however, require mutual exclusion, both with other
writers and with all of the readers. Consequently, the writers do not need to
employ the lightswitch, simply accessing the semaphore directly.
`Code Listing 8.19 <#cl8-19>`_ shows the framework for this solution.

.. _cl8-19:

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

Fairness to Writers
-------------------

.. _Unfair:

.. figure:: Images/CSF-Images.8.2.png
   :align: right
   :width: 95%
   :figwidth: 45%
   :alt: An unfair timing for the writer

   An unfair timing for the writer

The solution to the readers-writers problem as shown in `Code Listing 8.19
<#cl8-19>`_ has an important flaw to highlight. This approach fails to achieve
:term:`fairness`, particularly in relation to the writers. Specifically,
consider the timing of events shown in :num:`Figure #Unfair`. In this
scenario, Reader A arrives first and decrements the semaphore. When the writer
arrives and tries to do the same, it gets blocked. The writer must then wait
until *all readers* have left. Once Reader B arrives, the two readers take turns
leaving and re-entering. Since at least one reader is always in the system, the
writer is blocked indefinitely, a situation known as :term:`starvation`.

The writer's starvation in this scenario can be fixed by placing a turnstile
before the readers can enter as shown in `Code Listing 8.20 <#cl8-20>`_. As long
as there is no writer attempting to enter the critical section, the readers can
each pass through the turnstile and invoke ``enter()`` on the lightswitch.
However, once a writer arrives, it will call ``sem_wait()`` on the turnstile
semaphore, blocking new readers from passing through the turnstile. The writer
will then call ``sem_wait()`` on the lightswitch semaphore and block. When the
last of the readers that are already in the critical section call ``leave()``,
that thread will ``sem_post()`` to the lightswitch semaphore, allowing the
writer to enter. The writer can then ``sem_post()`` to the turnstile, allowing
readers to pass through again. The first reader through calls ``enter()`` on the
lightswitch and gets blocked until the writer leaves.

.. _cl8-20:

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

Depending on the particular context, it may be acceptable or desirable to use
the solution that potentially allows writer starvation. For instance, if read
accesses to the critical section are extremely fast and concurrent reads are
rare, starvation would not occur; the turnstile would then impose unnecessary
system calls and potential context switches that may accumulate. However, this
cost may be acceptable to mitigate potential delays to the writers.

Search-Insert-Delete Problem
----------------------------

The :term:`search-insert-delete problem` is a variant on the readers-writers
problem. In this variant, multiple threads can search through a data structure
concurrently; the searchers are essentially identical to the readers from
before. However, the writers are broken into two distinct types of threads:
inserters are adding new data while deleters are removing elements. As with the
original writers, deletions must be mutually exclusive with all other accesses
to the shared data structure. However, insertions have a more relaxed
requirement: they must be mutually exclusive with themselves and with deletions,
but concurrent searches are still allowed. That is, the inserters and searchers
cannot lock each other out, but only one inserter is allowed access at a time;
deleters, on the other hand, require mutual exclusion.

This problem can be solved with slight modifications of the original solution
for the readers-writers. The searcher thread is identical to the reader, as
shown in `Code Listing 8.21 <#cl8-21>`_.

.. _cl8-21:

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

Inserters are also very similar to readers. The main difference is that
inserters also require mutual exclusion among themselves, requiring a lock as
shown in `Code Listing 8.22 <#cl8-22>`_.

.. _cl8-22:

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

To complete the solution, the deleter threads behave identically to the writers.
The only difference is that the deleter must rely on both lightswitches for the
other two types of threads as shown in `Code Listing 8.23 <#cl8-23>`_. If the
deleter successfully passes the semaphore for the ``search_switch``, then there
are no searchers in the critical section and new searchers will be blocked by
the lightswitch. Once the last inserter leaves the critical section, the deleter
would be able to pass the ``insert_switch`` semaphore and enter the critical
section. Additional inserters would also be locked out at this point. Once the
deleter exits the critical section, inserters and searchers would be allowed back in.

.. codeinclude:: SynchProblems/CodeListing-8-23.c

This solution, which is a variant on the original readers-writers solution, has
the same weakness previously discussed. The deleter threads can potentially face
starvation, as long as there is at least one searcher or inserter in their
critical sections. Interestingly, though, the searcher threads can also face
starvation. Specifically, consider the case where all the searchers leave the
critical section and a deleter has arrived. As long as there are inserters in
the critical section, the deleter cannot enter. However, the deleter has already
successfully locked out future searchers. Consequently, the future searchers
would be effectively locked out by the inserters. Adapting the turnstile
approach used for readers-writers would successfully prevent starvation in this case, too.

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