Editing Monitor (synchronization) (section)

===Blocking condition variables===
The original proposals by [[C. A. R. Hoare]] and [[Per Brinch Hansen]] were for ''blocking condition variables''. With a blocking condition variable, the signaling thread must wait outside the monitor (at least) until the signaled thread relinquishes occupancy of the monitor by either returning or by again waiting on a condition variable. Monitors using blocking condition variables are often called ''Hoare-style'' monitors or ''signal-and-urgent-wait'' monitors.

[[File:Monitor (synchronization)-SU.png|thumb|200px|right|A Hoare style monitor with two condition variables <code>a</code> and <code>b</code>. After Buhr ''et al.'']]

We assume there are two queues of threads associated with each monitor object
* <code>e</code> is the entrance queue
* <code>s</code> is a queue of threads that have signaled.
In addition we assume that for each condition variable {{mvar|c}}, there is a queue
* <code>{{mvar|c}}.q</code>, which is a queue for threads waiting on condition variable {{mvar|c}}
All queues are typically guaranteed to be [[Unbounded nondeterminism#Fairness|fair]] and, in some implementations, may be guaranteed to be [[fIFO (computing and electronics)|first in first out]].

The implementation of each operation is as follows. (We assume that each operation runs in mutual exclusion to the others; thus restarted threads do not begin executing until the operation is complete.)

 enter the monitor:
     enter the method
     '''if''' the monitor is locked
         add this thread to e
         block this thread
     '''else'''
         lock the monitor
 
 leave the monitor:
     schedule
     '''return''' from the method
 
 '''wait''' {{mvar|c}}:
     add this thread to {{mvar|c}}.q
     schedule
     block this thread
 
 '''signal''' {{mvar|c}}:
     '''if''' there is a thread waiting on {{mvar|c}}.q
         select and remove one such thread t from {{mvar|c}}.q
         (t is called "the signaled thread")
         add this thread to s
         restart t
         (so t will occupy the monitor next)
         block this thread
 
 schedule:
     '''if''' there is a thread on s
         select and remove one thread from s and restart it
         (this thread will occupy the monitor next)
     '''else if''' there is a thread on e
         select and remove one thread from e and restart it
         (this thread will occupy the monitor next)
     '''else'''
         unlock the monitor
         (the monitor will become unoccupied)

The <code>schedule</code> routine selects the next thread to occupy the monitor
or, in the absence of any candidate threads, unlocks the monitor.

The resulting signaling discipline is known as ''"signal and urgent wait,"'' as the signaler must wait, but is given priority over threads on the entrance queue. An alternative is ''"signal and wait,"'' in which there is no <code>s</code> queue and signaler waits on the <code>e</code> queue instead.

Some implementations provide a '''signal and return''' operation that combines signaling with returning from a procedure.

 '''signal''' {{mvar|c}} '''and return''':
     '''if''' there is a thread waiting on {{mvar|c}}.q
         select and remove one such thread t from {{mvar|c}}.q
         (t is called "the signaled thread")
         restart t
         (so t will occupy the monitor next)
     '''else'''
         schedule
     '''return''' from the method

In either case ("signal and urgent wait" or "signal and wait"), when a condition variable is signaled and there is at least one thread waiting on the condition variable, the signaling thread hands occupancy over to the signaled thread seamlessly, so that no other thread can gain occupancy in between. If {{mvar|P<sub>c</sub>}} is true at the start of each '''signal''' {{mvar|c}} operation, it will be true at the end of each '''wait''' {{mvar|c}} operation. This is summarized by the following [[design by contract|contracts]]. In these contracts, {{mvar|I}} is the monitor's [[invariant (computer science)|invariant]].

 enter the monitor:
     '''postcondition''' {{mvar|I}}
 
 leave the monitor:
     '''precondition''' {{mvar|I}}
 
 '''wait''' {{mvar|c}}:
     '''precondition''' {{mvar|I}}
     '''modifies''' the state of the monitor
     '''postcondition''' {{mvar|P<sub>c</sub>}} '''and''' {{mvar|I}}
 
 '''signal''' {{mvar|c}}:
     '''precondition''' {{mvar|P<sub>c</sub>}} '''and''' {{mvar|I}}
     '''modifies''' the state of the monitor
     '''postcondition''' {{mvar|I}}
 
 '''signal''' {{mvar|c}} '''and return''':
     '''precondition''' {{mvar|P<sub>c</sub>}} '''and''' {{mvar|I}}

In these contracts, it is assumed that {{mvar|I}} and {{mvar|P<sub>c</sub>}} do not depend on the
contents or lengths of any queues.

(When the condition variable can be queried as to the number of threads waiting on its queue, more sophisticated contracts can be given. For example, a useful pair of contracts, allowing occupancy to be passed without establishing the invariant, is:

 '''wait''' {{mvar|c}}:
     '''precondition''' {{mvar|I}}
     '''modifies''' the state of the monitor
     '''postcondition''' {{mvar|P<sub>c</sub>}}
 
 '''signal''' {{mvar|c}}
     '''precondition''' ('''not''' empty({{mvar|c}}) '''and''' {{mvar|P<sub>c</sub>}}) '''or''' (empty({{mvar|c}}) '''and''' {{mvar|I}})
     '''modifies''' the state of the monitor
     '''postcondition''' {{mvar|I}}

(See Howard<ref name="1976_Howard">{{cite conference
|last1=Howard |first1=John H.
|title=Signaling in monitors
|book-title=ICSE '76 Proceedings of the 2nd international conference on Software engineering
|conference=International Conference on Software Engineering
|publisher=IEEE Computer Society Press |location=Los Alamitos, CA, USA
|year=1976
|pages=47–52
|url=http://dl.acm.org/citation.cfm?id=807647
}}</ref> and Buhr ''et al.''<ref name="1995_Buhr-Fortier-Coffin">{{cite journal
|last1=Buhr |first1=Peter A.
|last2=Fortier |first2=Michel
|last3=Coffin |first3=Michael H.
|title=Monitor classification
|journal=[[ACM Computing Surveys]]
|volume=27
|issue=1
|date=March 1995
|pages=63–107
|doi=10.1145/214037.214100
|s2cid=207193134
|doi-access=free
}}</ref> for more.)

It is important to note here that the assertion {{mvar|P<sub>c</sub>}} is entirely up to the programmer; he or she simply needs to be consistent about what it is.

We conclude this section with an example of a thread-safe class using a blocking monitor that implements a bounded, [[thread safety|thread-safe]] [[stack (data structure)|stack]].

 '''monitor class''' ''SharedStack'' {
     '''private const''' capacity := 10
     '''private''' ''int''[capacity] A
     '''private''' ''int'' size := 0
     '''invariant''' 0 <= size '''and''' size <= capacity
     '''private''' ''BlockingCondition'' theStackIsNotEmpty <u>/* '''associated with''' 0 < size '''and''' size <= capacity */</u>
     '''private''' ''BlockingCondition'' theStackIsNotFull <u>/* '''associated with''' 0 <= size '''and''' size < capacity */</u>
 
     '''public method''' push(''int'' value)
     {
         '''if''' size = capacity '''then''' '''wait''' theStackIsNotFull
         '''assert''' 0 <= size '''and''' size < capacity
         A[size] := value ; size := size + 1
         '''assert''' 0 < size '''and''' size <= capacity
         '''signal''' theStackIsNotEmpty '''and return'''
     }
 
     '''public method''' ''int'' pop()
     {
         '''if''' size = 0 '''then''' '''wait''' theStackIsNotEmpty
         '''assert''' 0 < size '''and''' size <= capacity
         size := size - 1 ;
         '''assert''' 0 <= size '''and''' size < capacity
         '''signal''' theStackIsNotFull '''and return''' A[size]
     }
 }

Note that, in this example, the thread-safe stack is internally providing a mutex, which, as in the earlier producer/consumer example, is shared by both condition variables, which are checking different conditions on the same concurrent data.  The only difference is that the producer/consumer example assumed a regular non-thread-safe queue and was using a standalone mutex and condition variables, without these details of the monitor abstracted away as is the case here.  In this example, when the "wait" operation is called, it must somehow be supplied with the thread-safe stack's mutex, such as if the "wait" operation is an integrated part of the "monitor class".  Aside from this kind of abstracted functionality, when a "raw" monitor is used, it will ''always'' have to include a mutex and a condition variable, with a unique mutex for each condition variable.