Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Using semaphores in a parallel programming or multi user environment

  1. Dec 28, 2007 #1

    Eus

    User Avatar

    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.

    Best regards,
    Eus
     
  2. jcsd
  3. Dec 28, 2007 #2
    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.
     
  4. Dec 29, 2007 #3

    Eus

    User Avatar

    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.

    Best regards,
    Eus
     
  5. Dec 29, 2007 #4

    jim mcnamara

    User Avatar
    Science Advisor
    Gold Member

    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.
     
  6. Jan 1, 2008 #5

    Eus

    User Avatar

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

    But, it still does not explain why:
    With other words, why doesn't P defined as:
    Code (Text):

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

    It is written there that:
    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?
    The main thing is in the following sentence that is still greek to me:
    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.

    Best regards,
    Eus
     
  7. Jan 1, 2008 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  8. Jan 2, 2008 #7

    Eus

    User Avatar

    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 :wink::

    Consider the original code below:
    Code (Text):

    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 article even does not say anything about that.
    I cannot find a sentence that makes an allusion to it.

    Thank you for your help.

    Best regards,
    Eus
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Using semaphores in a parallel programming or multi user environment
  1. Semaphores program (Replies: 0)

Loading...