Semaphore vs Monitor

Trying to decide what kind of counting syncronisation object I should use for my buffer polling expansion to the CNI (see two posts down).In my travels I found a lively and mostly misguided debate of monitors vs semaphores so decided to investigate further.

When people talk of a monitor, what they are referring to is a design pattern that works best using a simple condition variable. The monitor pattern is an example of object wide course locking. The monitor pattern provides strict access control to an objects members and methods.

A monitor is not a new technology but is a transition in a way of programming syncronisation. Think of a syncronisation Aspect and you are mentally on your way there.  A monitor is semantic leap of the scale of C struct to C++  class  or from heap based memory management to garbage collection.

Some languages have made monitor a compiler primitive such the that compiler can enforce the pattern implementation.

It is easily proven that semaphores and monitors are equally powerful:  each can be used to implement the other.

You use monitors in applications, not in operating systems.

 Semaphores

  • a semaphore is a special counter
    • with an initial value C
    • two operations, P and V, for changing that value
    • P waits until #P – #V <= C
    • V signals the counter, and a waiting process, if any
  • Effective for tracking multiple interchangeable resources
  • generally assumed fair:
    • processes complete P operations in the same order they start them
  • low-level:
    • easy to forget a P or a V
  • scattered:
    • if you want to change how processes synchronize access to a data structure, you have to find all the places in the code where they touch that structure, which is difficult and error-prone (aliasing!).

Monitors

  • monitors were an attempt to address the weaknesses of semaphores  (low-level and scattered)
  • several parallel programming languages have incorporated monitors as their fundamental synchronization mechanism
  • a monitor is a shared object (abstraction) with operations, internal state, and a number of condition queues.
    • only one operation of a given monitor may be active at a time, i.e. no need to remember to release things – occurs on procedure exit
    • a process that calls a busy monitor is delayed until the monitor is free
    • like objects, but with strict scoping
      • monitor variables always private (not visible outside monitor procedures)
      • monitor procedures may only access monitor variables and parameters
    • condition variables within monitor
      • var x : condition
      • x.wait operation ALWAYS waits until another process performs x.signal
      • x.signal wakes up a process (usually first to wait) IFF some process is waiting — otherwise has NO EFFECT whatsoever, i.e. signal <> V.
  • on behalf of its calling process, any operation may suspend itself by waiting on a condition (and thereby releasing control of the monitor).

Example of Semaphores vs. Monitors

Consider the bounded buffer with semaphores:  Here’s the same thing with monitors:
shared buf : array [1..N] of data
 

    shared front, rear : integer := 1

    shared empty, full : sem := N, 0

    procedure deposit (m : data)
        P (empty)

        buf[rear] := m
        rear := rear mod N + 1

        V (full)
 

    procedure fetch : data
        P (full)

        m : data := buf[front]
        front := front mod N + 1
        V (empty)
        return m

monitor BB
     export deposit, fetch
     buf : array [1..N] of data
     front, rear : integer := 1
     slots : integer := 0
     emptied, filled : condition

     procedure deposit (m : data)
         if slots = N
             wait (emptied)
         buf[rear] := m
         rear := rear mod N + 1
         slots := slots + 1
         signal (filled)

     procedure fetch : data
         if slots = 0
             wait (filled)
         m : data := buf[front]
         front := front mod N + 1
         slots := slots - 1
         signal (emptied)
         return m

 

 

Semaphores Condition Variables
Can be used anywhere in a program, but should not be used in a monitor Can be used in monitors. Can be used anywhere but almost always requires combination with mutex or another syncronisation primitive, so they are difficult to use and don't make as much sense outside of the monitor pattern. If you disagree with me and have a counter case, first as the question 'is my counter case an example of the monitor pattern' - I suspect you will find the answer is yes.
Wait() does not always block the caller (i.e., when the semaphore counter is greater than zero). Wait() always blocks the caller.
Signal() either releases a blocked thread, if there is one, or increases the semaphore counter. Signal() either releases a blocked thread, if there is one, or the signal is lost as if it never happens.
If Signal() releases a blocked thread, the caller and the released thread both continue. If Signal() releases a blocked thread, the caller yields the monitor (Hoare type) or continues (Mesa Type). Only one of the caller or the released thread can continue, but not both.

 

About these ads

About metawrap

CTO Massive Interactive. Ex Computer Whiz Kid - Now Grumpy Old Guru.
This entry was posted in C#, Rants. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s