how to Simulate semaphores with message passing...?

Question

I want to simulate the semaphores (wait and signal procedure) with the message passing just in form of algorithm (and not code).

can anyone help me...?

Answer 1

Do you need to know the algorithms with which critical-sections and semaphores primitives are implemented? See Process Synchronization (pdf). Note that sometimes you may see a semaphore implemented using critical-sections to ensure atomicity of the test-modify operations.

Message queuing is built on top of synchronization primitives. The message queue you seek is in Chapter 4 of the excellent Little Book of Semaphores (pdf).

Edited to add:

I have to guess what you mean by "mailbox," so if this answer is no good, it'd be helpful for you to define what a mailbox is. Do I understand that the exercise is to implement P and V by using a high-level synchronization mechanism such as a message queue? Since a message queue is by necessity protected against concurrency issues, that's a simple exercise.

Given a class Mailbox which is guaranteed to be thread-safe and which has these methods:

• enqueue(message) - Add a message to the mailbox. If there any threads blocked in dequeue, wake one.
• dequeue - Remove a message from the mailbox, blocking if the mailbox is empty.

Then a semaphore class would have these methods:

initialize(count):
  mailbox = Mailbox.new
  count.times do
    v

v:
  mailbox.enqueue(any_message)

p:
  mailbox.dequeue

any_message is any message at all. It doesn't matter what it is, since we're only using the message queue to wake up blocked threads.

This algorithm emulates a semaphore which cannot have a negative value. A semaphore which can be created with a negative value will need to do more work. Which do you need?