{"history":[],"article":{"id":"a0e1a98c-27bb-48e6-bce5-b741468fb42e","title":"Monitor (synchronization)","slug":"monitor-synchronization","content":":::summary\n:::\n\n# \nIn [concurrent programming](https://bliptext.com/articles/concurrent-computing), a **monitor** is a synchronization construct that prevents threads from concurrently accessing a shared object's state and allows them to wait for the state to change.\nThey provide a mechanism for threads to temporarily give up exclusive access in order to wait for some condition to be met, before regaining exclusive access and resuming their task.\nA monitor consists of a [mutex (lock)](https://bliptext.com/articles/lock-computer-science) and at least one **condition variable**.\nA ****condition variable**** is explicitly 'signalled' when the object's state is modified, temporarily passing the mutex to another thread 'waiting' on the ****condition variable****.\nAnother definition of **monitor** is a **[thread](https://bliptext.com/articles/thread-computer-science)-safe** [class](https://bliptext.com/articles/class-computer-science), [object](https://bliptext.com/articles/object-computer-science), or [module](https://bliptext.com/articles/module-programming) that wraps around a [mutex](https://bliptext.com/articles/mutual-exclusion) in order to safely allow access to a method or variable by more than one [thread](https://bliptext.com/articles/thread-computer-science).\nThe defining characteristic of a monitor is that its [methods](https://bliptext.com/articles/method-computer-science) are executed with [mutual exclusion](https://bliptext.com/articles/mutual-exclusion): At each point in time, at most one thread may be executing any of its [methods](https://bliptext.com/articles/method-computer-science).\nBy using one or more condition variables it can also provide the ability for threads to wait on a certain condition (thus using the above definition of a \"monitor\").\nFor the rest of this article, this sense of \"monitor\" will be referred to as a \"thread-safe object/class/module\".\nMonitors were invented by [Per Brinch Hansen](https://bliptext.com/articles/per-brinch-hansen) and [C. A. R. Hoare](https://bliptext.com/articles/c-a-r-hoare), and were first implemented in [Brinch Hansen's](https://bliptext.com/articles/per-brinch-hansen) [Concurrent Pascal](https://bliptext.com/articles/concurrent-pascal) language.\n\n# Mutual exclusion\nWhile a thread is executing a method of a thread-safe object, it is said to occupy the object, by holding its [mutex (lock)](https://bliptext.com/articles/lock-computer-science).\nThread-safe objects are implemented to enforce that at each point in time, at most one thread may occupy the object.\nThe lock, which is initially unlocked, is locked at the start of each public method, and is unlocked at each return from each public method.\nUpon calling one of the methods, a thread must wait until no other thread is executing any of the thread-safe object's methods before starting execution of its method.\nNote that without this mutual exclusion, two threads could cause money to be lost or gained for no reason.\nFor example, two threads withdrawing 1000 from the account could both return true, while causing the balance to drop by only 1000, as follows: first, both threads fetch the current balance, find it greater than 1000, and subtract 1000 from it; then, both threads store the balance and return.\n\n# Condition variables\n\n## Problem statement\nFor many applications, mutual exclusion is not enough.\nThreads attempting an operation may need to wait until some condition P holds true.\nA [busy waiting](https://bliptext.com/articles/busy-waiting) loop\n**while** **not** ( P ) **do** **skip**\nwill not work, as mutual exclusion will prevent any other thread from entering the monitor to make the condition true.\nOther \"solutions\" exist such as having a loop that unlocks the monitor, waits a certain amount of time, locks the monitor and checks for the condition P. Theoretically, it works and will not deadlock, but issues arise.\nIt is hard to decide an appropriate amount of waiting time: too small and the thread will hog the CPU, too big and it will be apparently unresponsive.\nWhat is needed is a way to signal the thread when the condition P is true (or could be true).\n\n## Case study: classic bounded producer/consumer problem\nA classic concurrency problem is that of the **bounded producer/consumer**, in which there is a [queue](https://bliptext.com/articles/queue-data-structure) or [ring buffer](https://bliptext.com/articles/circular-buffer) of tasks with a maximum size, with one or more threads being \"producer\" threads that add tasks to the [queue](https://bliptext.com/articles/queue-data-structure), and one or more other threads being \"consumer\" threads that take tasks out of the [queue](https://bliptext.com/articles/queue-data-structure).\nThe queue is assumed to be non–thread-safe itself, and it can be empty, full, or between empty and full.\nWhenever the queue is full of tasks, then we need the producer threads to block until there is room from consumer threads dequeueing tasks.\nOn the other hand, whenever the queue is empty, then we need the consumer threads to block until more tasks are available due to producer threads adding them.\nAs the queue is a concurrent object shared between threads, accesses to it must be made [atomic](https://bliptext.com/articles/atomicity-database-systems), because the queue can be put into an **inconsistent state** during the course of the queue access that should never be exposed between threads.\nThus, any code that accesses the queue constitutes a **[critical section](https://bliptext.com/articles/critical-section)** that must be synchronized by mutual exclusion.\nIf code and processor instructions in critical sections of code that access the queue could be **interleaved** by arbitrary **context switches** between threads on the same processor or by simultaneously-running threads on multiple processors, then there is a risk of exposing inconsistent state and causing [race conditions](https://bliptext.com/articles/race-condition).\n\n### Incorrect without synchronization\nA naïve approach is to design the code with **busy-waiting** and no synchronization, making the code subject to race conditions:\nThis code has a serious problem in that accesses to the queue can be interrupted and interleaved with other threads' accesses to the queue.\nThe queue.enqueue and queue.dequeue methods likely have instructions to update the queue's member variables such as its size, beginning and ending positions, assignment and allocation of queue elements, etc.\nIn addition, the queue.isEmpty and queue.isFull methods read this shared state as well.\nIf producer/consumer threads are allowed to be interleaved during the calls to enqueue/dequeue, then inconsistent state of the queue can be exposed leading to race conditions.\nIn addition, if one consumer makes the queue empty in-between another consumer's exiting the busy-wait and calling \"dequeue\", then the second consumer will attempt to dequeue from an empty queue leading to an error.\nLikewise, if a producer makes the queue full in-between another producer's exiting the busy-wait and calling \"enqueue\", then the second producer will attempt to add to a full queue leading to an error.\n\n### Spin-waiting\nOne naive approach to achieve synchronization, as alluded to above, is to use \"**spin-waiting**\", in which a mutex is used to protect the critical sections of code and busy-waiting is still used, with the lock being acquired and released in between each busy-wait check.\nThis method assures that an inconsistent state does not occur, but wastes CPU resources due to the unnecessary busy-waiting.\nEven if the queue is empty and producer threads have nothing to add for a long time, consumer threads are always busy-waiting unnecessarily.\nLikewise, even if consumers are blocked for a long time on processing their current tasks and the queue is full, producers are always busy-waiting.\nThis is a wasteful mechanism.\nWhat is needed is a way to make producer threads block until the queue is non-full, and a way to make consumer threads block until the queue is non-empty.\n(N.B.: Mutexes themselves can also be **spin-locks** which involve busy-waiting in order to get the lock, but in order to solve this problem of wasted CPU resources, we assume that queueLock is not a spin-lock and properly uses a blocking lock queue itself.)\n\n## Condition variables\nThe solution is to use **condition variables**.\nConceptually, a condition variable is a queue of threads, associated with a mutex, on which a thread may wait for some condition to become true.\nThus each condition variable c is associated with an [assertion](https://bliptext.com/articles/assertion-computing) Pc.\nWhile a thread is waiting on a condition variable, that thread is not considered to occupy the monitor, and so other threads may enter the monitor to change the monitor's state.\nIn most types of monitors, these other threads may signal the condition variable c to indicate that assertion Pc is true in the current state.\nThus there are three main operations on condition variables:\n2. move this thread from the \"running\" to 's \"wait-queue\" (a.k.a. \"sleep-queue\") of threads, and\n3. sleep this thread.\n(Context is synchronously yielded to another thread.)\nAs a design rule, multiple condition variables can be associated with the same mutex, but not vice versa.\n(This is a [one-to-many](https://bliptext.com/articles/multivalued-function) correspondence.) This is because the predicate Pc is the same for all threads using the monitor and must be protected with mutual exclusion from all other threads that might cause the condition to be changed or that might read it while the thread in question causes it to be changed, but there may be different threads that want to wait for a different condition on the same variable requiring the same mutex to be used.\nIn the producer-consumer example [described above](https://bliptext.com/articles/), the queue must be protected by a unique mutex object,.\nThe \"producer\" threads will want to wait on a monitor using lock and a condition variable c_{full} which blocks until the queue is non-full.\nThe \"consumer\" threads will want to wait on a different monitor using the same mutex but a different condition variable c_{empty} which blocks until the queue is non-empty.\nIt would (usually) never make sense to have different mutexes for the same condition variable, but this classic example shows why it often certainly makes sense to have multiple condition variables using the same mutex.\nA mutex used by one or more condition variables (one or more monitors) may also be shared with code that does not use condition variables (and which simply acquires/releases it without any wait/signal operations), if those [critical sections](https://bliptext.com/articles/critical-section) do not happen to require waiting for a certain condition on the concurrent data.\n\n## Monitor usage\nThe proper basic usage of a monitor is:\nThe following is the same pseudocode but with more verbose comments to better explain what is going on:\n\n### Solving the bounded producer/consumer problem\nHaving introduced the usage of condition variables, let us use it to revisit and solve the classic bounded producer/consumer problem.\nThe classic solution is to use two monitors, comprising two condition variables sharing one lock on the queue:\nThis ensures concurrency between the producer and consumer threads sharing the task queue, and blocks the threads that have nothing to do rather than busy-waiting as shown in the aforementioned approach using spin-locks.\nA variant of this solution could use a single condition variable for both producers and consumers, perhaps named \"queueFullOrEmptyCV\" or \"queueSizeChangedCV\".\nIn this case, more than one condition is associated with the condition variable, such that the condition variable represents a weaker condition than the conditions being checked by individual threads.\nThe condition variable represents threads that are waiting for the queue to be non-full and ones waiting for it to be non-empty.\nHowever, doing this would require using broadcast in all the threads using the condition variable and cannot use a regular signal.\nThis is because the regular signal might wake up a thread of the wrong type whose condition has not yet been met, and that thread would go back to sleep without a thread of the correct type getting signaled.\nFor example, a producer might make the queue full and wake up another producer instead of a consumer, and the woken producer would go back to sleep.\nIn the complementary case, a consumer might make the queue empty and wake up another consumer instead of a producer, and the consumer would go back to sleep.\nUsing broadcast ensures that some thread of the right type will proceed as expected by the problem statement.\nHere is the variant using only one condition variable and broadcast:\n\n## Synchronization primitives\nMonitors are implemented using an [atomic](https://bliptext.com/articles/linearizability) read-modify-write primitive and a waiting primitive.\nThe read-modify-write primitive (usually test-and-set or compare-and-swap) is usually in the form of a memory-locking instruction provided by the [ISA](https://bliptext.com/articles/instruction-set-architecture), but can also be composed of non-locking instructions on single-processor devices when interrupts are disabled.\nThe waiting primitive can be a [busy-wait](https://bliptext.com/articles/busy-wait) loop or an OS-provided primitive that prevents the thread from being [scheduled](https://bliptext.com/articles/scheduling-computing) until it is ready to proceed.\nHere is an example pseudocode implementation of parts of a threading system and mutexes and Mesa-style condition variables, using **test-and-set** and a first-come, first-served policy:\n\n### Sample Mesa-monitor implementation with Test-and-Set\n\n## Blocking condition variables\nThe original proposals by [C. A. R. Hoare](https://bliptext.com/articles/c-a-r-hoare) and [Per Brinch Hansen](https://bliptext.com/articles/per-brinch-hansen) were for blocking condition variables.\nWith 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.\nMonitors using blocking condition variables are often called Hoare-style monitors or signal-and-urgent-wait monitors.\nWe assume there are two queues of threads associated with each monitor object\nIn addition we assume that for each condition variable c, there is a queue\nAll queues are typically guaranteed to be [fair](https://bliptext.com/articles/unbounded-nondeterminism) and, in some implementations, may be guaranteed to be [first in first out](https://bliptext.com/articles/fifo-computing-and-electronics).\nThe implementation of each operation is as follows.\n(We assume that each operation runs in mutual exclusion to the others; thus restarted threads do not begin executing until the operation is complete.)\nenter the monitor:\nenter the method\n**if** the monitor is locked\nadd this thread to e block this thread\n**else**\nlock the monitor\nleave the monitor:\nschedule\n**return** from the method\n**wait** c: add this thread to c.q schedule\nblock this thread\n**signal** c: **if** there is a thread waiting on c.q select and remove one such thread t from c.q (t is called \"the **signal**ed thread\")\nadd this thread to s restart t (so t will occupy the monitor next)\nblock this thread\nschedule:\n**if** there is a thread on s select and remove one thread from s and restart it (this thread will occupy the monitor next)\n**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)\n**else**\nunlock the monitor\n(the monitor will become unoccupied)\nThe routine selects the next thread to occupy the monitor\nor, in the absence of any candidate threads, unlocks the monitor.\nThe 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.\nAn alternative is \"signal and wait,\" in which there is no queue and signaler waits on the queue instead.\nSome implementations provide a **signal and return** operation that combines signaling with returning from a procedure.\n**signal** c **and return**:\n**if** there is a thread waiting on c.q select and remove one such thread t from c.q (t is called \"the signaled thread\")\nrestart t (so t will occupy the monitor next)\n**else**\nschedule\n**return** from the method\nIn 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.\nIf Pc is true at the start of each **signal** c operation, it will be true at the end of each **wait** c operation.\nThis is summarized by the following [contracts](https://bliptext.com/articles/design-by-contract).\nIn these contracts, I is the monitor's [invariant](https://bliptext.com/articles/invariant-computer-science).\nenter the monitor:\n**postcondition** I leave the monitor:\n****precondition**** I **wait** c: ****precondition**** I **modifies** the state of the monitor\n**postcondition** Pc ****and**** I **signal** c: **precondition** Pc ****and**** I **modifies** the state of the monitor\n**postcondition** I **signal** c **and return**:\n**precondition** Pc **and** I\nIn these contracts, it is assumed that I and Pc do not depend on the\ncontents or lengths of any queues.\n(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:\n**wait** c: **precondition** I **modifies** the state of the monitor\n**postcondition** Pc **signal** c **precondition** (**not** empty(c) ****and**** Pc) **or** (empty(c) ****and**** I) **modifies** the state of the monit**or**\n**postcondition** I\n(See Howard and Buhr et al. for more.)\nIt is important to note here that the assertion Pc is entirely up to the programmer; he or she simply needs to be consistent about what it is.\nWe conclude this section with an example of a [thread-safe](https://bliptext.com/articles/thread-safety) class using a blocking monitor that implements a bounded, [thread-safe](https://bliptext.com/articles/thread-safety) [stack](https://bliptext.com/articles/stack-data-structure).\n**monitor class** SharedStack {\n**private const** capacity := 10\n****private**** int[capacity] A ****private**** int size := 0\n**invariant** 0 <= size **and** size <= capacity\n**private** BlockingCondition theStackIsNotEmpty /* **associated with** 0 < size **and** size <= capacity */\n**private** BlockingCondition theStackIsNotFull /* **associated with** 0 <= size **and** size < capacity */\n**public method** push(int value)\n{ **if** size = capacity **then** **wait** theStackIsNotFull\n**assert** 0 <= size **and** size < capacity\nA[size] := value ; size := size + 1\n**assert** 0 < size **and** size <= capacity\n**signal** theStackIsNotEmpty **and return**\n} **public method** int pop\n{ **if** size = 0 **then** **wait** theStackIsNotEmpty\n**assert** 0 < size **and** size <= capacity\nsize := size - 1 ;\n**assert** 0 <= size **and** size < capacity\n**signal** theStackIsNotFull **and return** A[size]\n} }\nNote 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.\nThe 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.\nIn 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\".\nAside 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.\n# [A Hoare style monitor with two condition variables and . After Buhr et al. | upload.wikimedia.org/wikipedia/commons/d/db/Monitor///%28synchronization%29-SU.png]\n\n## Nonblocking condition variables\nWith nonblocking condition variables (also called \"Mesa style\" condition variables or \"signal and continue\" condition variables), signaling does not cause the signaling thread to lose occupancy of the monitor.\nInstead the signaled threads are moved to the queue.\nThere is no need for the queue.\nWith nonblocking condition variables, the **signal** operation is often called **notify** — a terminology we will follow here.\nIt is also common to provide a **notify all** operation that moves all threads waiting on a condition variable to the queue.\nThe meaning of various operations are given here.\n(We assume that each operation runs in mutual exclusion to the others; thus restarted threads do not begin executing until the operation is complete.)\nenter the monitor:\nenter the method\n**if** the monitor is locked\nadd this thread to e block this thread\n**else**\nlock the monitor\nleave the monitor:\nschedule\n**return** from the method\n**wait** c: add this thread to c.q schedule\nblock this thread\n**notify** c: if there is a thread waiting on c.q select and remove one thread t from c.q (t is called \"the notified thread\")\nmove t to e **notify all** c: move all threads waiting on c.q to e schedule :\n**if** there is a thread on e select and remove one thread from e and restart it **else**\nunlock the monitor\nAs a variation on this scheme, the notified thread may be moved to a queue called, which has priority over.\nSee Howard and Buhr et al. for further discussion.\nIt is possible to associate an assertion Pc with each condition variable c such that Pc is sure to be true upon return from.\nHowever, one must\nensure that Pc is preserved from the time the **notify**ing thread gives up occupancy until the notified thread is selected to re-enter the monitor.\nBetween these times there could be activity by other occupants.\nThus it is common for Pc to simply be true.\nFor this reason, it is usually necessary to enclose each **wait** operation in a loop like this\n**while** **not** ( P ) **do**\n**wait** c\nwhere P is some condition stronger than Pc.\nThe operations and are treated as \"hints\" that P may be true for some waiting thread.\nEvery iteration of such a loop past the first represents a lost notification; thus with nonblocking monitors, one must be careful to ensure that too many notifications cannot be lost.\nAs an example of \"hinting,\" consider a bank account in which a withdrawing thread will wait until the account has sufficient funds before proceeding\n**monitor class** Account {\n**private** int balance := 0\n**invariant** balance >= 0\n**private** NonblockingCondition balanceMayBeBigEnough\n**public method** withdraw(int amount)\n**precondition** amount >= 0\n{ **while** balance < amount **do** **wait** balanceMayBeBigEnough\n**assert** balance >= amount\nbalance := balance - amount\n} **public method** deposit(int amount)\n**precondition** amount >= 0\n{ balance := balance + amount\n**notify all** balanceMayBeBigEnough\n} }\nIn this example, the condition being waited for is a function of the amount to be withdrawn, so it is impossible for a depositing thread to know that it made such a condition true.\nIt makes sense in this case to allow each waiting thread into the monitor (one at a time) to check if its assertion is true.\n# [A Mesa style monitor with two condition variables and | upload.wikimedia.org/wikipedia/commons/1/15/Monitor///%28synchronization%29-Mesa.png]\n\n## Implicit condition variable monitors\nIn the [Java](https://bliptext.com/articles/java-programming-language) language, each object may be used as a monitor.\nMethods requiring mutual exclusion must be explicitly marked with the **[synchronized](https://bliptext.com/articles/java-keyword)** keyword.\nBlocks of code may also be marked by **[synchronized](https://bliptext.com/articles/java-keyword)**.\nRather than having explicit condition variables, each monitor (i.e., object) is equipped with a single wait queue in addition to its entrance queue.\nAll waiting is done on this single wait queue and all **notify** and **notify**All operations apply to this queue.\nThis approach has been adopted in other languages, for example [C#](https://bliptext.com/articles/c-sharp-programming-language).\n# [A Java style monitor | upload.wikimedia.org/wikipedia/commons/f/f5/Monitor///%28synchronization%29-Java.png]\n\n## Implicit signaling\nAnother approach to **signal**ing is to omit the **signal** operation.\nWhenever a thread leaves the monitor (by returning or waiting), the assertions of all waiting threads are evaluated until one is found to be true.\nIn such a system, condition variables are not needed, but the assertions must be explicitly coded.\nThe contract for wait is\n**wait** P: **precondition** I **modifies** the state of the monitor\n**postcondition** P **and** I\n\n# History\nBrinch Hansen and Hoare developed the monitor concept in the early 1970s, based on earlier ideas of their own and of [Edsger Dijkstra](https://bliptext.com/articles/e-w-dijkstra).\nBrinch Hansen published the first monitor notation, adopting the [class](https://bliptext.com/articles/class-computer-programming) concept of [Simula 67](https://bliptext.com/articles/simula), and invented a queueing mechanism.\nHoare refined the rules of process resumption.\nBrinch Hansen created the first implementation of monitors, in [Concurrent Pascal](https://bliptext.com/articles/concurrent-pascal).\nHoare demonstrated their equivalence to [semaphores](https://bliptext.com/articles/semaphore-programming).\nMonitors (and Concurrent Pascal) were soon used to structure process synchronization in the [Solo operating system](https://bliptext.com/articles/solo-operating-system).\nProgramming languages that have supported monitors include:\nA number of libraries have been written that allow monitors to be constructed in languages that do not support them natively.\nWhen library calls are used, it is up to the programmer to explicitly mark the start and end of code executed with mutual exclusion.\n[Pthreads](https://bliptext.com/articles/posix-threads) is one such library.","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-25T21:19:28.216Z","updated_at":"2025-01-25T21:19:28.216Z","search_vector":"'monitor':1 'synchron':2","search_content":" \n \n\n# \nIn [concurrent programming](https://bliptext.com/articles/concurrent-computing), a **monitor** is a synchronization construct that prevents threads from concurrently accessing a shared object's state and allows them to wait for the state to change.\nThey provide a mechanism for threads to temporarily give up exclusive access in order to wait for some condition to be met, before regaining exclusive access and resuming their task.\nA monitor consists of a [mutex (lock)](https://bliptext.com/articles/lock-computer-science) and at least one **condition variable**.\nA ****condition variable**** is explicitly 'signalled' when the object's state is modified, temporarily passing the mutex to another thread 'waiting' on the ****condition variable****.\nAnother definition of **monitor** is a **[thread](https://bliptext.com/articles/thread-computer-science)-safe** [class](https://bliptext.com/articles/class-computer-science), [object](https://bliptext.com/articles/object-computer-science), or [module](https://bliptext.com/articles/module-programming) that wraps around a [mutex](https://bliptext.com/articles/mutual-exclusion) in order to safely allow access to a method or variable by more than one [thread](https://bliptext.com/articles/thread-computer-science).\nThe defining characteristic of a monitor is that its [methods](https://bliptext.com/articles/method-computer-science) are executed with [mutual exclusion](https://bliptext.com/articles/mutual-exclusion): At each point in time, at most one thread may be executing any of its [methods](https://bliptext.com/articles/method-computer-science).\nBy using one or more condition variables it can also provide the ability for threads to wait on a certain condition (thus using the above definition of a \"monitor\").\nFor the rest of this article, this sense of \"monitor\" will be referred to as a \"thread-safe object/class/module\".\nMonitors were invented by [Per Brinch Hansen](https://bliptext.com/articles/per-brinch-hansen) and [C. A. R. Hoare](https://bliptext.com/articles/c-a-r-hoare), and were first implemented in [Brinch Hansen's](https://bliptext.com/articles/per-brinch-hansen) [Concurrent Pascal](https://bliptext.com/articles/concurrent-pascal) language.\n\n# Mutual exclusion\nWhile a thread is executing a method of a thread-safe object, it is said to occupy the object, by holding its [mutex (lock)](https://bliptext.com/articles/lock-computer-science).\nThread-safe objects are implemented to enforce that at each point in time, at most one thread may occupy the object.\nThe lock, which is initially unlocked, is locked at the start of each public method, and is unlocked at each return from each public method.\nUpon calling one of the methods, a thread must wait until no other thread is executing any of the thread-safe object's methods before starting execution of its method.\nNote that without this mutual exclusion, two threads could cause money to be lost or gained for no reason.\nFor example, two threads withdrawing 1000 from the account could both return true, while causing the balance to drop by only 1000, as follows: first, both threads fetch the current balance, find it greater than 1000, and subtract 1000 from it; then, both threads store the balance and return.\n\n# Condition variables\n\n## Problem statement\nFor many applications, mutual exclusion is not enough.\nThreads attempting an operation may need to wait until some condition P holds true.\nA [busy waiting](https://bliptext.com/articles/busy-waiting) loop\n**while** **not** ( P ) **do** **skip**\nwill not work, as mutual exclusion will prevent any other thread from entering the monitor to make the condition true.\nOther \"solutions\" exist such as having a loop that unlocks the monitor, waits a certain amount of time, locks the monitor and checks for the condition P. Theoretically, it works and will not deadlock, but issues arise.\nIt is hard to decide an appropriate amount of waiting time: too small and the thread will hog the CPU, too big and it will be apparently unresponsive.\nWhat is needed is a way to signal the thread when the condition P is true (or could be true).\n\n## Case study: classic bounded producer/consumer problem\nA classic concurrency problem is that of the **bounded producer/consumer**, in which there is a [queue](https://bliptext.com/articles/queue-data-structure) or [ring buffer](https://bliptext.com/articles/circular-buffer) of tasks with a maximum size, with one or more threads being \"producer\" threads that add tasks to the [queue](https://bliptext.com/articles/queue-data-structure), and one or more other threads being \"consumer\" threads that take tasks out of the [queue](https://bliptext.com/articles/queue-data-structure).\nThe queue is assumed to be non–thread-safe itself, and it can be empty, full, or between empty and full.\nWhenever the queue is full of tasks, then we need the producer threads to block until there is room from consumer threads dequeueing tasks.\nOn the other hand, whenever the queue is empty, then we need the consumer threads to block until more tasks are available due to producer threads adding them.\nAs the queue is a concurrent object shared between threads, accesses to it must be made [atomic](https://bliptext.com/articles/atomicity-database-systems), because the queue can be put into an **inconsistent state** during the course of the queue access that should never be exposed between threads.\nThus, any code that accesses the queue constitutes a **[critical section](https://bliptext.com/articles/critical-section)** that must be synchronized by mutual exclusion.\nIf code and processor instructions in critical sections of code that access the queue could be **interleaved** by arbitrary **context switches** between threads on the same processor or by simultaneously-running threads on multiple processors, then there is a risk of exposing inconsistent state and causing [race conditions](https://bliptext.com/articles/race-condition).\n\n### Incorrect without synchronization\nA naïve approach is to design the code with **busy-waiting** and no synchronization, making the code subject to race conditions:\nThis code has a serious problem in that accesses to the queue can be interrupted and interleaved with other threads' accesses to the queue.\nThe queue.enqueue and queue.dequeue methods likely have instructions to update the queue's member variables such as its size, beginning and ending positions, assignment and allocation of queue elements, etc.\nIn addition, the queue.isEmpty and queue.isFull methods read this shared state as well.\nIf producer/consumer threads are allowed to be interleaved during the calls to enqueue/dequeue, then inconsistent state of the queue can be exposed leading to race conditions.\nIn addition, if one consumer makes the queue empty in-between another consumer's exiting the busy-wait and calling \"dequeue\", then the second consumer will attempt to dequeue from an empty queue leading to an error.\nLikewise, if a producer makes the queue full in-between another producer's exiting the busy-wait and calling \"enqueue\", then the second producer will attempt to add to a full queue leading to an error.\n\n### Spin-waiting\nOne naive approach to achieve synchronization, as alluded to above, is to use \"**spin-waiting**\", in which a mutex is used to protect the critical sections of code and busy-waiting is still used, with the lock being acquired and released in between each busy-wait check.\nThis method assures that an inconsistent state does not occur, but wastes CPU resources due to the unnecessary busy-waiting.\nEven if the queue is empty and producer threads have nothing to add for a long time, consumer threads are always busy-waiting unnecessarily.\nLikewise, even if consumers are blocked for a long time on processing their current tasks and the queue is full, producers are always busy-waiting.\nThis is a wasteful mechanism.\nWhat is needed is a way to make producer threads block until the queue is non-full, and a way to make consumer threads block until the queue is non-empty.\n(N.B.: Mutexes themselves can also be **spin-locks** which involve busy-waiting in order to get the lock, but in order to solve this problem of wasted CPU resources, we assume that queueLock is not a spin-lock and properly uses a blocking lock queue itself.)\n\n## Condition variables\nThe solution is to use **condition variables**.\nConceptually, a condition variable is a queue of threads, associated with a mutex, on which a thread may wait for some condition to become true.\nThus each condition variable c is associated with an [assertion](https://bliptext.com/articles/assertion-computing) Pc.\nWhile a thread is waiting on a condition variable, that thread is not considered to occupy the monitor, and so other threads may enter the monitor to change the monitor's state.\nIn most types of monitors, these other threads may signal the condition variable c to indicate that assertion Pc is true in the current state.\nThus there are three main operations on condition variables:\n2. move this thread from the \"running\" to 's \"wait-queue\" (a.k.a. \"sleep-queue\") of threads, and\n3. sleep this thread.\n(Context is synchronously yielded to another thread.)\nAs a design rule, multiple condition variables can be associated with the same mutex, but not vice versa.\n(This is a [one-to-many](https://bliptext.com/articles/multivalued-function) correspondence.) This is because the predicate Pc is the same for all threads using the monitor and must be protected with mutual exclusion from all other threads that might cause the condition to be changed or that might read it while the thread in question causes it to be changed, but there may be different threads that want to wait for a different condition on the same variable requiring the same mutex to be used.\nIn the producer-consumer example [described above](https://bliptext.com/articles/), the queue must be protected by a unique mutex object,.\nThe \"producer\" threads will want to wait on a monitor using lock and a condition variable c_{full} which blocks until the queue is non-full.\nThe \"consumer\" threads will want to wait on a different monitor using the same mutex but a different condition variable c_{empty} which blocks until the queue is non-empty.\nIt would (usually) never make sense to have different mutexes for the same condition variable, but this classic example shows why it often certainly makes sense to have multiple condition variables using the same mutex.\nA mutex used by one or more condition variables (one or more monitors) may also be shared with code that does not use condition variables (and which simply acquires/releases it without any wait/signal operations), if those [critical sections](https://bliptext.com/articles/critical-section) do not happen to require waiting for a certain condition on the concurrent data.\n\n## Monitor usage\nThe proper basic usage of a monitor is:\nThe following is the same pseudocode but with more verbose comments to better explain what is going on:\n\n### Solving the bounded producer/consumer problem\nHaving introduced the usage of condition variables, let us use it to revisit and solve the classic bounded producer/consumer problem.\nThe classic solution is to use two monitors, comprising two condition variables sharing one lock on the queue:\nThis ensures concurrency between the producer and consumer threads sharing the task queue, and blocks the threads that have nothing to do rather than busy-waiting as shown in the aforementioned approach using spin-locks.\nA variant of this solution could use a single condition variable for both producers and consumers, perhaps named \"queueFullOrEmptyCV\" or \"queueSizeChangedCV\".\nIn this case, more than one condition is associated with the condition variable, such that the condition variable represents a weaker condition than the conditions being checked by individual threads.\nThe condition variable represents threads that are waiting for the queue to be non-full and ones waiting for it to be non-empty.\nHowever, doing this would require using broadcast in all the threads using the condition variable and cannot use a regular signal.\nThis is because the regular signal might wake up a thread of the wrong type whose condition has not yet been met, and that thread would go back to sleep without a thread of the correct type getting signaled.\nFor example, a producer might make the queue full and wake up another producer instead of a consumer, and the woken producer would go back to sleep.\nIn the complementary case, a consumer might make the queue empty and wake up another consumer instead of a producer, and the consumer would go back to sleep.\nUsing broadcast ensures that some thread of the right type will proceed as expected by the problem statement.\nHere is the variant using only one condition variable and broadcast:\n\n## Synchronization primitives\nMonitors are implemented using an [atomic](https://bliptext.com/articles/linearizability) read-modify-write primitive and a waiting primitive.\nThe read-modify-write primitive (usually test-and-set or compare-and-swap) is usually in the form of a memory-locking instruction provided by the [ISA](https://bliptext.com/articles/instruction-set-architecture), but can also be composed of non-locking instructions on single-processor devices when interrupts are disabled.\nThe waiting primitive can be a [busy-wait](https://bliptext.com/articles/busy-wait) loop or an OS-provided primitive that prevents the thread from being [scheduled](https://bliptext.com/articles/scheduling-computing) until it is ready to proceed.\nHere is an example pseudocode implementation of parts of a threading system and mutexes and Mesa-style condition variables, using **test-and-set** and a first-come, first-served policy:\n\n### Sample Mesa-monitor implementation with Test-and-Set\n\n## Blocking condition variables\nThe original proposals by [C. A. R. Hoare](https://bliptext.com/articles/c-a-r-hoare) and [Per Brinch Hansen](https://bliptext.com/articles/per-brinch-hansen) were for blocking condition variables.\nWith 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.\nMonitors using blocking condition variables are often called Hoare-style monitors or signal-and-urgent-wait monitors.\nWe assume there are two queues of threads associated with each monitor object\nIn addition we assume that for each condition variable c, there is a queue\nAll queues are typically guaranteed to be [fair](https://bliptext.com/articles/unbounded-nondeterminism) and, in some implementations, may be guaranteed to be [first in first out](https://bliptext.com/articles/fifo-computing-and-electronics).\nThe implementation of each operation is as follows.\n(We assume that each operation runs in mutual exclusion to the others; thus restarted threads do not begin executing until the operation is complete.)\nenter the monitor:\nenter the method\n**if** the monitor is locked\nadd this thread to e block this thread\n**else**\nlock the monitor\nleave the monitor:\nschedule\n**return** from the method\n**wait** c: add this thread to c.q schedule\nblock this thread\n**signal** c: **if** there is a thread waiting on c.q select and remove one such thread t from c.q (t is called \"the **signal**ed thread\")\nadd this thread to s restart t (so t will occupy the monitor next)\nblock this thread\nschedule:\n**if** there is a thread on s select and remove one thread from s and restart it (this thread will occupy the monitor next)\n**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)\n**else**\nunlock the monitor\n(the monitor will become unoccupied)\nThe routine selects the next thread to occupy the monitor\nor, in the absence of any candidate threads, unlocks the monitor.\nThe 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.\nAn alternative is \"signal and wait,\" in which there is no queue and signaler waits on the queue instead.\nSome implementations provide a **signal and return** operation that combines signaling with returning from a procedure.\n**signal** c **and return**:\n**if** there is a thread waiting on c.q select and remove one such thread t from c.q (t is called \"the signaled thread\")\nrestart t (so t will occupy the monitor next)\n**else**\nschedule\n**return** from the method\nIn 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.\nIf Pc is true at the start of each **signal** c operation, it will be true at the end of each **wait** c operation.\nThis is summarized by the following [contracts](https://bliptext.com/articles/design-by-contract).\nIn these contracts, I is the monitor's [invariant](https://bliptext.com/articles/invariant-computer-science).\nenter the monitor:\n**postcondition** I leave the monitor:\n****precondition**** I **wait** c: ****precondition**** I **modifies** the state of the monitor\n**postcondition** Pc ****and**** I **signal** c: **precondition** Pc ****and**** I **modifies** the state of the monitor\n**postcondition** I **signal** c **and return**:\n**precondition** Pc **and** I\nIn these contracts, it is assumed that I and Pc do not depend on the\ncontents or lengths of any queues.\n(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:\n**wait** c: **precondition** I **modifies** the state of the monitor\n**postcondition** Pc **signal** c **precondition** (**not** empty(c) ****and**** Pc) **or** (empty(c) ****and**** I) **modifies** the state of the monit**or**\n**postcondition** I\n(See Howard and Buhr et al. for more.)\nIt is important to note here that the assertion Pc is entirely up to the programmer; he or she simply needs to be consistent about what it is.\nWe conclude this section with an example of a [thread-safe](https://bliptext.com/articles/thread-safety) class using a blocking monitor that implements a bounded, [thread-safe](https://bliptext.com/articles/thread-safety) [stack](https://bliptext.com/articles/stack-data-structure).\n**monitor class** SharedStack {\n**private const** capacity := 10\n****private**** int[capacity] A ****private**** int size := 0\n**invariant** 0 = 0\n**private** NonblockingCondition balanceMayBeBigEnough\n**public method** withdraw(int amount)\n**precondition** amount >= 0\n{ **while** balance = amount\nbalance := balance - amount\n} **public method** deposit(int amount)\n**precondition** amount >= 0\n{ balance := balance + amount\n**notify all** balanceMayBeBigEnough\n} }\nIn this example, the condition being waited for is a function of the amount to be withdrawn, so it is impossible for a depositing thread to know that it made such a condition true.\nIt makes sense in this case to allow each waiting thread into the monitor (one at a time) to check if its assertion is true.\n# [A Mesa style monitor with two condition variables and | upload.wikimedia.org/wikipedia/commons/1/15/Monitor///%28synchronization%29-Mesa.png]\n\n## Implicit condition variable monitors\nIn the [Java](https://bliptext.com/articles/java-programming-language) language, each object may be used as a monitor.\nMethods requiring mutual exclusion must be explicitly marked with the **[synchronized](https://bliptext.com/articles/java-keyword)** keyword.\nBlocks of code may also be marked by **[synchronized](https://bliptext.com/articles/java-keyword)**.\nRather than having explicit condition variables, each monitor (i.e., object) is equipped with a single wait queue in addition to its entrance queue.\nAll waiting is done on this single wait queue and all **notify** and **notify**All operations apply to this queue.\nThis approach has been adopted in other languages, for example [C#](https://bliptext.com/articles/c-sharp-programming-language).\n# [A Java style monitor | upload.wikimedia.org/wikipedia/commons/f/f5/Monitor///%28synchronization%29-Java.png]\n\n## Implicit signaling\nAnother approach to **signal**ing is to omit the **signal** operation.\nWhenever a thread leaves the monitor (by returning or waiting), the assertions of all waiting threads are evaluated until one is found to be true.\nIn such a system, condition variables are not needed, but the assertions must be explicitly coded.\nThe contract for wait is\n**wait** P: **precondition** I **modifies** the state of the monitor\n**postcondition** P **and** I\n\n# History\nBrinch Hansen and Hoare developed the monitor concept in the early 1970s, based on earlier ideas of their own and of [Edsger Dijkstra](https://bliptext.com/articles/e-w-dijkstra).\nBrinch Hansen published the first monitor notation, adopting the [class](https://bliptext.com/articles/class-computer-programming) concept of [Simula 67](https://bliptext.com/articles/simula), and invented a queueing mechanism.\nHoare refined the rules of process resumption.\nBrinch Hansen created the first implementation of monitors, in [Concurrent Pascal](https://bliptext.com/articles/concurrent-pascal).\nHoare demonstrated their equivalence to [semaphores](https://bliptext.com/articles/semaphore-programming).\nMonitors (and Concurrent Pascal) were soon used to structure process synchronization in the [Solo operating system](https://bliptext.com/articles/solo-operating-system).\nProgramming languages that have supported monitors include:\nA number of libraries have been written that allow monitors to be constructed in languages that do not support them natively.\nWhen library calls are used, it is up to the programmer to explicitly mark the start and end of code executed with mutual exclusion.\n[Pthreads](https://bliptext.com/articles/posix-threads) is one such library.","revisionCount":0},"hasMore":false,"nextCursor":null}