Hoare Monitor implementation using semaphores?

Question

it is my exam in 4 days and I just spoke to my lectuer and he has been extremely unclear about this part of the lecture and I really struggled along with many students how to understand this.

Basiclly, if you wanna implement Hoare monitor using semaphore, what is the sequences of steps involved?

Below is the pseudocode

]3

Update:

I am starting to get it now

so the 1st slide is for the process accessing the monitor

if you are the only one, then you call wait(mutex)

get into the monitor do your stuff and leave

if there is something waiting to get into the monitor then you up the next semaphore, that is the quene of waiting process to get into the semaphore. else if you are the only one in the monitor then you exit and up mutex so someone else can get into the mutex

for the 2nd slide with the wait(condition) and signal(condition)

when u wait(c): c_count++ //number of process waiting for this condition, increment by one if(next_count>0) up(next) //if number of waiting process that want t get into the monitor is more than zero, up(next), unblock one of the waiting process

else up(mutex) //if you are the only one then up mutex so someone else get in down(c_sem) // block yourself to sleep c_count-- //you wake up so number of process waiting for this condition decrement

for the signal(c) part:

if(c_count>0) // if number of process waiting for this condition is bigger than 0

next_counter++ //number of process wanting to get into the monitor increment by one up(c_sem); // unblock one of the process waiting for this condition down(next) //if a spot is available, down this otherwise get block and join list of waiting processes next_count--; //you wake up and try to get into the monitor

Answer 1

Man, I can see why you are confused. The problem here is that this example merges two concepts.

A semaphore is a form of mutex. In the abstract, a mutex is just a variable that can be atomically incremented or decremented. Your up function increments. Your down function decrements event if multiple process are up'ing or down'ing at the same time. If you just make up equivalent to count = count + 1 you would get random results if multiple processes tried to increment at the same time.

In the real world (outside academia) a semaphore does more than just increment. You can wait on a semaphore as well.

So, if I do

 real_world_down (semaphore)

My process decrements the semaphore. If no process (or thread) has locked the semaphore (usually = 0, with 1 being the starting point), my process continues. If another process has already locked the semaphore (value after down < 0), my process waits.

When the process that has locked the semaphore finishes and does

 real_world_up (semaphore)

The operating system picks one of the waiting processes to run automatically.

Thus your Hoare monitor looks like

  var 
     semaphore ; 
  Procedure Monitor

       real_world_down (semaphore) ;

       /* do whatever you want */

       real_world_up (semaphore) ;

 End ;

Or we could write it as:

  var 
     semaphore ; 
  Procedure Monitor

       lock (semaphore) ;

       /* do whatever you want */

       unlock (semaphore) ;

 End ;

That's the monitor part. The part about your example that is confusing is that it is a poorly written lock/unlock using academic semaphores that just increment and decrement atomically and have no knowledge of who is waiting on them.

It's wait is equivalent to my lock. It's equivalent to my unlock is totally FUed.

At this point I would leave as an exercise for you to create a lock function that will only allow one process/thread to acquire the lock using a pair of semaphores but will allow multiple processes to wait and, when unlocked, will allow one waiting process/thread to continue.

It needs an unlock function that will unlock the mutex pair to allow one process/thread to continue.

Answer 2

First of all - 2 hours is not really much time to calm you down, I guess - so I don't even try.

On the other hand: it's an exam, not a hackathon. Having said this, ... why don't you stick to the academic level that the slides of your professor have.

If you want a different version of explaining the fundamental work of the genius C.A.R. Hoare than have a look at this PowerPoint - you can read it all but the most important page for you should be page 15: MonitorPPT

And: in case you want to read the original paper after the exam - to prepare for fighting for points that you didn't get or just for fun - here it is: C.A.R. Hoare - Monitors: An Operating System Structuring Concept

All the best for your exam, Tom!