Hi guys... 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...?
+1
A:
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?
Wayne Conrad
2010-01-01 00:11:12
I know a little about algorithm of semaphores (wait and signal algorithms).I don't know how to simulate the semaphore's queue with mailbox.when we say in wait procedure that :semaphore.count--;if (semaphore.count < 0) place this process in semaphore.queue and block this processand when we say in siganl procedure that :semaphore.count++;if (semaphore.count <= 0) remove process p from semaphore.queue and place in ready listNow How should I do these with mailbox?where processes must be placed?
Hero
2010-01-01 08:52:40
Hamed, I added to the answer.
Wayne Conrad
2010-01-01 19:42:04
Yes, a Semaphore with negative value (for mutual exclusion).Where the threads should be placed? (when we add a message to mailbox, where is a thread waked up from?)Should we consider a queue for threads, just like Semaphore?
Hero
2010-01-02 14:57:00
Mutex works fine in a semaphore that cannot be initialized with a negative value. Threads are normally put into a plain old FIFO (first in, first out) queue by P; V removes threads from the queue and wakes them up.Hamed, I think there is a language barrier between us. I've got the impression that you and I are using words that don't have the same meaning to the other person. Can you please define these terms?: "message queue," "mailbox," "queue."
Wayne Conrad
2010-01-02 15:39:22