Synchronization Using Monitors

  1. What are monitors?

  • A high-level synchronization mechanism, with three slight variants:

    • Brinch Hansen
    • Hoare
    • Mesa

  • The original definition was supported by the programming language

    • Either a theoretical language or a real one like Mesa Programming Language (1977)
    • Supported by ( and enforced by) the language and the compiler

  • Now more typically provided by a library, unknown to the compiler

    • Example: POSIX Pthreads library
    • Must use the library in a "stylized" fashion, conformance checked at runtime.
  1. Basic Structure of a Monitor
    • Entry procedures can be called only from outside of the monitor
      • only way to enter the monitor
      • automatically acquires (waits for) the mutual exclusion of the monitor
      • automatically releases on return
      • Only one process can be active inside the monitor at a time
    • Internal procedures can be called only when already inside the monitor
  2. Condition Variable
    • A Special type of shared variables (inside of a monitor)
      • condition x, y, z;
    • Since a shared variable, a condition variable can be used only inside the monitor
      • A condition variable has no value
    • Only two operations allowed on a condition variable
      • x.wait - the current process is blocked until
      • x.signal - unblock one process waiting on x.wait, if any - has no effect if no process is waiting, still cost runtime
  3. A Problem with Condition Variables
    • The process calling x.signal must have been active then inside the monitor
      • x is a shared variable and is only accessible from inside the monitor
    • The process woken up is woken inside the monitor too
      • This woken process must have been active inside the monitor to do x.wait
    • Problem: so we would have 2 processes active at the same time inside the monitor?
    • Solution: we need to define our way out of this problem --> 3 different solutions: Hansen, Hoare, Mesa
  4. Hoare vs. Mesa vs. Brinch Hansen Monitors
  • The three solve this problem differently:
    • The code looks the same though
    • Only behaviors are different
    • No one can tell just by looking at the code what type is supposed to be
    • Must state the chosen monitor type
  • Hoare Monitor wait/signal Behavior
    • First, process Q does an x.wait, then later process P does an x.signal
    • P is immediately blocked when it does x.signal
    • Control transfers directly to Q and it wakes up from its x.wait
    • An atomic switch from P to Q
    • P runs again only sometime later at least after Q returns from the monitor or itself waits on some condition variable.
    • Every variable still has the same value when Q resumes as when P signaled.
    • The textbook named it "signal and wait"
  • Mesa Monitor wait/signal Behavior
    • First, process Q does an x.wait, then later process P does an x.signal
    • P continues to run normally after doing x.signal
    • Q is no longer blocked on the conditional variable
    • However, it is still blocked because of mutual exclusion
    • Q runs only sometimes later at least after process P exits the monitor or itself waits on some condition variable
    • Be Careful: essentially anything could have happened to monitor variables after P's x.signal and before Q resumes execution after its x.wait
    • The textbook calls this "signal and continue"
  • Brinch Hansen Monitor wait/signal Behavior
    • First, process Q does an x.wait, then later process P does an x.signal
    • A signal must be the last thing you do before you return from the monitor
    • Q runs only sometimes later (not necessarily immediately)
    • The simplest possible rule for avoiding the problem of both P and Q active inside the monitor at the same time
    • Sort of like an intersection between Hoare and Mesa
  1. Why Three Different wait/signal Behaviors?
  2. Some (Unavoidably Necessary) Assumptions
  3. Starvation vs. Deadlock
  4. Restrictions on Use of Monitor Extensions