Using semaphores in a parallel programming or multi user environment

[Eus]

Hi Ho!

I read on http://en.wikipedia.org/wiki/Semaphore_(programming) that

P(Semaphore s, integer howmany)
{
wait until s >= 0;
s := s - howmany; /* must be atomic operation */
wait until s >= 0;
}

Must the whole function of P be atomic or just the "s := s - howmany;" part?
A pointer to a more detailed resource would help also.

Thank you very much.


Eus

 

[Coin]

As I interpret what they've written there, they just mean that the decrement must be atomic. For one thing, atomic increment/decrement is a widely available synchronization primitive. For another thing, I don't see how it would make sense to say that a "wait" should be "atomic" with respect to some other operation in the first place.

 

[Eus]

Okay, I got it. Thanks.

Besides that, it is also written there that "the need of checking and waiting twice for the s >= 0 condition in P is needed to guarantee that as multiple processes are added to the semaphore's waiting list they do not disturb each other's request: a process does not change the semaphore's count until it is next in the queue."

I still don't get why a process will disturb the other if it changes the semaphore's count in its legitimate turn. Could you please give additional information? Or, maybe a pointer to a more detailed explanation?

Thank you very much.


Eus

 

[jim mcnamara]

It is a process context-switching issue. There is no guarantee about when a process or a thread will get/lose it's turn with the CPU. Atomic means the process will complete a subtraction, guaranteed, once it starts a subtraction. It cannot lose its turn with the CPU in the middle of making the subtraction.

Semaphores and mutexes are traffic cops, making threads or processes take turns one at a time when accessing an object or a critical section. So any change to a mutex has to complete, it cannot be left in an indeterminate state - its value has to be absolutely the same for any process that tests it, not 0 for me and 1 for you.

 

[Eus]

It is a process context-switching issue...

Semaphores and mutexes are traffic cops, ...

Yes, to avoid race condition and to enforce a certain order of execution (to perform synchronization).

But, it still does not explain why:

the need of checking and waiting twice for the s >= 0 condition in P is needed to guarantee that as multiple processes are added to the sempahore's waiting list they do not disturb each other's request: a process does not change the sempahore's count until it is next in the queue.

With other words, why doesn't P defined as:

P(Semaphore s, integer howmany)
{
    s := s - howmany; /* must be atomic operation */
    wait until x >= 0;
}

instead?

It is written there that:

In real implementations it is done without actually activating up the waiting process for the intermediate step.

Do you agree that it says about the new definition of P that I write above?

If you agree, then why even bother putting two waiting codes in the old definition of P and start making a long explanation, which I paste below, about it?

It should be noted that the semaphore count is not necessary equal to the buffers available in the pool. The need of checking and waiting twice for the s >= 0 condition in P is needed to guarantee that as multiple processes are added to the semaphore's waiting list they do not disturb each other's request: a process does not change the semaphore's count until it is next in the queue. In real implementations it is done without actually activating up the waiting process for the intermediate step.

The main thing is in the following sentence that is still greek to me:

... they do not disturb each other's request: a process does not change the semaphore's count until it is next in the queue.

Why "until it is next in the queue"? The scheduler picks a process at random, doesn't it?
In what way a process can change the semaphore's count before it is next in the queue if function P is the only way to change the semaphore's count?
In what way a process disturbs each other's request if the process does change the semaphore's count before it is next in the queue?

Could someone please help?

Thank you.


Eus

 

[Hurkyl]

With other words, why doesn't P defined as:

P(Semaphore s, integer howmany)
{
    s := s - howmany; /* must be atomic operation */
    wait until x >= 0;
}

instead?

This is definitely bad -- it leads to deadlock. Consider the following: (the letters denote threads of execution)

The semaphorse is created with 3 permits.

A acquires 2 permits. The counter is now 1
B attempts to acquire 2 permits. The counter is now -1, and B sleeps.
C attempts to acquire 2 permits. The counter is now -3, and C sleeps.
A returns 2 permuts. The counter is -1.

Note that B and C can now never proceed; the counter is firmly locked at a negative value.


The example you originally gave in this post can demonstrate the same bad behavior -- e.g. if B and C both wake up from the first wait at the same time, and both do the decrement before the second check.


I think the Wikipedia article is implicitly making use of some additional synchronization method in their exposition. I'm going to complain on the discussion page.

 

[Eus]

This is definitely bad -- it leads to deadlock.

If suppose the whole function of P is atomic, can a deadlock occur?
Atomic means that once a thread is actively executing P, no other thread can execute P.
But, once a thread is sleeping waiting for its turn or it has reached the end of P, another thread can execute P.
Any objection to this atomic definition of P?

Anyway, even if P is atomic, a deadlock can still occur as follows :

Consider the original code below:

P(Semaphore s, integer howmany) /*ATOMIC*/
{
    wait until s >= 0; /*first wait*/
    s := s - howmany;
    wait until s >= 0;/*second wait*/
}

Using your example, there will be a deadlock as follows:
The semaphore is created with 3 permits.

A acquires 2 permits. The counter is now 1
B attempts to acquire 2 permits. The counter is now -1, and B sleeps at 2nd wait.
C attempts to acquire 2 permits. C sleeps at 1st wait because the counter is -1.
A returns 2 permits. The counter is 1.
C wakes up to acquire 2 permits. The counter is now -1, and C sleeps at 2nd wait.
DEADLOCK!

I think the Wikipedia article is implicitly making use of some additional synchronization method in their exposition.

I think the article even does not say anything about that.
I cannot find a sentence that makes an allusion to it.

I'm going to complain on the discussion page.

Thank you for your help.


Eus