.. _sync_solutions:

.. sidebar:: Wait Queues

    To implement synchronization, processes sometimes need to wait
    until a resource or lock becomes available.  For performance reason, we
    can not allow the process to just execute an empty loop (**Busy wait**).
    Thus, an additional responability that the OS must take on is to manage
    waiting queues, so that processes or threads can wait without using the
    CPU and be retrieved from the wait queue as soon as the resource that
    they are waiting for becomes available.  This functionality is
    provided by the resource manager.  See :ref:`resource_alloc`.

    In the algorithms discussed below, when **WAIT()** is executed, we mean
    that the process or thread is put in a queue and later retrieved when
    the tread issues a **SIGNAL()**.

Possible Synchronization Solutions
----------------------------------------------

.. important::

    * Software solution

    * Disable interrupts

    * . . . Something new, with hardware support . . .

Software Solution
^^^^^^^^^^^^^^^^^^

As we observed (:ref:`sync_requirements`), simple user code lock
implementations do not work.  However, as is noted in many texts, there are
some software algorithms (Dekker's, Peterson's and Bakery) that in some
situation may be useful to provide synchronization solutions.  These algorithms
could be useful in virtual threading environments such as Java, Python, Perl,
or Pthreads where the programming environment has some control over the
scheduling of threads.  However, there are restrictions on the usability of
these algorithms as a general purpose synchronization framework.

#.  Dekker's and Peterson's algorithms only work for two threads.

#.  The bakery algorithm requires that we know the number of threads before
    execution.

#.  They contain ``DoNothing()`` instructions as a waiting mechanism.  It might
    be difficult to implement this to behave like the wait queues that the
    operating system provides.

Disable Interrupts
^^^^^^^^^^^^^^^^^^^

To execute the critical section::

    disableInterrupts();
    /* --------------- */
      Critical Section
    /* --------------- */
    enableInterrupts();

* This block interrupts for the whole computer
* Interrupts could be disabled arbitrarily long
* Do you trust **ALL** programmers this much?

How about operating system provided software locks using disabled interrupts?::

    void get_lock(locked) {
        disableInterrupts();
        while( locked ) {
            enableInterrupts();
            WAIT();
            disableInterrupts();
        }
        locked = True
        enableInterrupts();
    }

    void release_lock(locked) {
        disableInterrupts();
        locked = False
        enableInterrupts();
        SIGNAL()
    }

-----------------

.. centered:: Is This Good Enough?

* Interrupts not disabled during whole critical section.
* Mostly easy for programmers::

    shared boolean lock;

    ...

    acquire_lock(lock);
    /* --------------- */
      Critical Section
    /* --------------- */
    release_lock(lock);

* What if programmers release a lock they don't own?  This could be solved with
  careful programming, but adds complexity.

* Remember: **This blocks interrupts for processes using the CPU**.

* For shared memory, multiprocessor system -- interrupts for other CPU's are
  not blocked.

* There might be a better solution.
    

.. _semaphores:
.. _semaphore:

Dijkstra's Semaphore
^^^^^^^^^^^^^^^^^^^^^^

* Proposed in 1965 by Edseger Dijkstra

* Conceptual OS mechanism, with no specific implementation defined 
  (could be ``enter()``/``exit()``)

* Basis of all contemporary OS synchronization mechanisms

* A simple hardware based solution

* A :term:`semaphore`, s, is a nonnegative integer variable that can only be 
  changed or tested by these two indivisible functions:

    .. centered:: V(s): [s = s + 1]

    .. centered:: P(s): [while(s == 0) {WAIT()}; s = s - 1]

* V and P are the first letters of Dutch words. P (*probern* -- to
  test) is used for acquiring the lock.  V (*verhogen* -- to increment) is
  used for releasing the lock.

* The square brackets [ ] here mean that the actions between the brackets
  is to be autonomous (not interruptible).

* The initial value of s determines how many simultaneous threads may hold the
  semaphore lock. Set s to 1 for a simple lock, called a *binary lock* or
  *binary semaphore*.  Some problems allow for s to be larger than 1.