VxWorks Beginner - Semaphore question. - VxWorks

This is a discussion on VxWorks Beginner - Semaphore question. - VxWorks ; Hello all! I'm a fairly new VxWorks programmer.. for that matter, I'm fairly new to any programming outside of the PC DOS/Windows arena. I ran into a problem recently while trying to code up some simple linked list stuff. I'm ...

+ Reply to Thread
Results 1 to 8 of 8

Thread: VxWorks Beginner - Semaphore question.

  1. VxWorks Beginner - Semaphore question.

    Hello all!

    I'm a fairly new VxWorks programmer.. for that matter, I'm fairly new
    to any programming outside of the PC DOS/Windows arena.

    I ran into a problem recently while trying to code up some simple
    linked list stuff. I'm not 100% sure I have a firm grasp of what
    "exactly" a semaphore is... but...

    Suppose I have a couple of functions:

    MY_TYPE* linked_list;

    void insert_node(MY_TYPE* new_node);
    MY_TYPE* get_first_node();

    Obviously, one function inserts a new link into the linked list, while
    another simply returns the first node (or any node, for that matter).
    Now, suppose these functions are called in various places across the
    application in various threads. Scheduling is turned on (default to
    round-robin, I believe?) - thus this leads me to think that I need to
    use a few semaphores to protect the reading and writing of this
    resource.

    The implementation I'm looking for should be fairly common. I would
    like to lock the resource during any WRITES to the resource, namely in
    the insert_node() function. During a write, I would like to block all
    reads and all other writes such that the function has exclusive access
    to the global variable.

    During reads, I would like to block any sort of writing to the
    resource...but should allow any other read operations to occur
    concurrently.

    So, I worked at it a little, and this is what I came up with (the
    semaphores are all binary, and created elsewhere. Both semaphores are
    initialized to FULL):

    void READ()
    {
    static int readcount = 0;

    readcount++;
    if (readcount == 1)
    {
    semTake(R, WAITFOREVER);
    semTake(W, WAITFOREVER);
    }
    else
    {
    semTake(R, WAITFOREVER);
    }
    semGive(R);
    //
    // perform read
    //
    readcount--;
    if (readCount == 0)
    {
    semGive(W);
    }
    }

    void WRITE()
    {
    semTake(W, WAITFOREVER);
    taskLock();
    //
    // perform write
    //
    taskUnLock();
    semGive(W);
    }

    This seems overly complicated for what I'm trying to do. But my
    reasoning is:

    During a write, the write operation takes the W semaphore. This
    signals all other operations a write is going on, and that he has
    exclusive access to the shared resource.

    During a read, the FIRST read will grab the R semaphore. This signals
    all other incoming reads that it is trying to "make it safe" to read.
    After obtaining the R semaphore, it attempts to grab the W semaphore,
    which would disable all incoming writes.

    After ensuring writes are disabled, each read operation is responsible
    for giving up a R semaphore so that the next read can occur. Finally,
    as each read completes, it decrements its counter. If a particular
    read operation finds that it is the last read operation in the list, it
    gives up the W semaphore, letting all writes know that it is okay to
    write again.

    *phew* that was confusing.

    But, as I looked at it in more depth, I saw many problems.
    1) A problem may exist if a SECOND read can grab the R semaphore (in
    the else) before the FIRST read grabs it (in the if). I'm not sure if
    this is possible due to different tasks having different priorities and
    the VxWorks task scheduling.

    2) A problem definitely exists in terms of priority inversion.
    Basically, once a read chain has been kicked off, any incoming reads
    will automatically have higher priority than a write, even if the read
    occurred later in time.

    I surely hope that there is a much cleaner and more elegant solution to
    this than the mess I've made up. It seems to me that managing a
    resource to read/write routines is a fairly common task, and I can't
    imagine always requiring exclusive access to a read routine. I
    expected a cookie-cutter solution to the problem when I first looked
    around the Internet, but I have yet to find anything.

    Does anyone have an idea of how this should be implemented?

    Thanks...


  2. Re: VxWorks Beginner - Semaphore question.

    semTake()


  3. Re: VxWorks Beginner - Semaphore question.

    Hi alydis,
    Ok I could figure out a solution.If someone can think
    of a better one please put a cc to my mail id:kaushal.r@gmail.com.The
    sol goes like this:

    writer1---------->
    writer2----------> OW { Resource =Linked
    List }
    writer3----------> ^
    writer4---------> ^
    : ^

    <--------reader1
    : MAIN Reader [ Req]---[ message ]----[
    Queue ]----[ ]-- <---------reader2


    <---------reader3


    <-------reader4

    Explanation:There would be many writerer tasks to the LL .All of them
    would use the L L only
    if they can get the Mutex semaphore OW .Any reader task would call a
    function which would
    write the request to a "request message queue" which is read by the
    MAIN reader task.This
    reader task would first take the OW if successful ,then alone access
    the LL and send the reply back to the reader task via another MsgQ
    which is specific to that reader(Standard Single server multiple
    clients approach;refer vxWorks programmers guide on msgQs).

    If multiple readers request it is as good as multiple reads from the
    msgQ and recursive take by the MAIN reader task.This is valid as
    recursive take for a Mutex semaphore is valid.If you specify the
    options as SEM_Q_PRIORITY orred with inversion safe, the tasks would be
    safe
    from priority inversion problem.

    Create the OW using semMCreate which is initally available.Immediately
    take it.The moment first node is created in the linked list make the
    semaphore available.First node of the LL will always peculiar.
    Hope that was useful.
    -kaushal.


  4. Re: VxWorks Beginner - Semaphore question.


    alydis wrote:
    > Hello all!
    >
    > I'm a fairly new VxWorks programmer.. for that matter, I'm fairly new
    > to any programming outside of the PC DOS/Windows arena.
    >
    > I ran into a problem recently while trying to code up some simple
    > linked list stuff. I'm not 100% sure I have a firm grasp of what
    > "exactly" a semaphore is... but...
    >
    > Suppose I have a couple of functions:
    >
    > MY_TYPE* linked_list;
    >
    > void insert_node(MY_TYPE* new_node);
    > MY_TYPE* get_first_node();
    >
    > Obviously, one function inserts a new link into the linked list, while
    > another simply returns the first node (or any node, for that matter).
    > Now, suppose these functions are called in various places across the
    > application in various threads. Scheduling is turned on (default to
    > round-robin, I believe?) - thus this leads me to think that I need to
    > use a few semaphores to protect the reading and writing of this
    > resource.
    >
    > The implementation I'm looking for should be fairly common. I would
    > like to lock the resource during any WRITES to the resource, namely in
    > the insert_node() function. During a write, I would like to block all
    > reads and all other writes such that the function has exclusive access
    > to the global variable.
    >
    > During reads, I would like to block any sort of writing to the
    > resource...but should allow any other read operations to occur
    > concurrently.
    >
    > So, I worked at it a little, and this is what I came up with (the
    > semaphores are all binary, and created elsewhere. Both semaphores are
    > initialized to FULL):
    >
    > void READ()
    > {
    > static int readcount = 0;
    >
    > readcount++;
    > if (readcount == 1)
    > {
    > semTake(R, WAITFOREVER);
    > semTake(W, WAITFOREVER);
    > }
    > else
    > {
    > semTake(R, WAITFOREVER);
    > }
    > semGive(R);
    > //
    > // perform read
    > //
    > readcount--;
    > if (readCount == 0)
    > {
    > semGive(W);
    > }
    > }
    >
    > void WRITE()
    > {
    > semTake(W, WAITFOREVER);
    > taskLock();
    > //
    > // perform write
    > //
    > taskUnLock();
    > semGive(W);
    > }
    >
    > This seems overly complicated for what I'm trying to do. But my
    > reasoning is:
    >
    > During a write, the write operation takes the W semaphore. This
    > signals all other operations a write is going on, and that he has
    > exclusive access to the shared resource.
    >
    > During a read, the FIRST read will grab the R semaphore. This signals
    > all other incoming reads that it is trying to "make it safe" to read.
    > After obtaining the R semaphore, it attempts to grab the W semaphore,
    > which would disable all incoming writes.
    >
    > After ensuring writes are disabled, each read operation is responsible
    > for giving up a R semaphore so that the next read can occur. Finally,
    > as each read completes, it decrements its counter. If a particular
    > read operation finds that it is the last read operation in the list, it
    > gives up the W semaphore, letting all writes know that it is okay to
    > write again.
    >
    > *phew* that was confusing.
    >
    > But, as I looked at it in more depth, I saw many problems.
    > 1) A problem may exist if a SECOND read can grab the R semaphore (in
    > the else) before the FIRST read grabs it (in the if). I'm not sure if
    > this is possible due to different tasks having different priorities and
    > the VxWorks task scheduling.
    >
    > 2) A problem definitely exists in terms of priority inversion.
    > Basically, once a read chain has been kicked off, any incoming reads
    > will automatically have higher priority than a write, even if the read
    > occurred later in time.
    >
    > I surely hope that there is a much cleaner and more elegant solution to
    > this than the mess I've made up. It seems to me that managing a
    > resource to read/write routines is a fairly common task, and I can't
    > imagine always requiring exclusive access to a read routine. I
    > expected a cookie-cutter solution to the problem when I first looked
    > around the Internet, but I have yet to find anything.
    >
    > Does anyone have an idea of how this should be implemented?
    >
    > Thanks...


    Alydis,
    I forsee some problems in your implementation.I would like to know
    whats the purpose of releasing the semaphore before you perform the
    read operation?I am exactly pertaining to this place in your
    problem(See my comments followed by arrow mark in your code):


    void READ()
    > {
    > static int readcount = 0;
    >
    > readcount++;
    > if (readcount == 1)
    > {
    > semTake(R, WAITFOREVER);
    > semTake(W, WAITFOREVER);
    > }
    > else
    > {
    > semTake(R, WAITFOREVER);
    > }
    > semGive(R);----------->you are releasing the semaphore,before you

    are performing the read operation.If you do

    this,the very purpose of R semaphore is
    defeated.I believe you are not using this
    semaphore at all because you are taking it and releasing it,simply with
    out using it.In which case its equivalent to not having a semaphore
    itself!
    > //
    > // perform read
    > //
    > readcount--;
    > if (readCount == 0)
    > {
    > semGive(W);
    > }
    > }
    >
    > void WRITE()
    > {
    > semTake(W, WAITFOREVER);
    > taskLock();
    > //
    > // perform write
    > //
    > taskUnLock();
    > semGive(W);
    > }



    The next thing is since you need exclusive access to the Write
    operation,Go for a Mutex instead of a Binary.Provide inversion safety
    while creating MUTEX.

    The other thing which I would like to say is generally you would create
    Binary semaphore with EMPTY flag,where as MUTEX with FULL flag.I
    believe if you could get what I conveyed,You should be able to solve
    your problem.

    Regards,
    s.subbarayan


  5. Re: VxWorks Beginner - Semaphore question.

    ssubbarayan,

    I think you've misunderstood my intent here. What I'm trying to
    implement is a semaphore system in which:

    For writes, I wish to block reads and writes both.
    For reads, I wish to block only writes.

    So, in my write function:
    1) I take W semaphore. This blocks other tasks that attempt to call
    the write routine.

    In my read function:
    1) I have to make sure that the write routine gets blocked. But, I
    only want to do this on the FIRST read. So, the FIRST read grabs the W
    semaphore.
    2) I also have to make sure the write routine gets unblocked when I am
    done with all my reads. This is why I release the W semaphore when I
    detect that I have no other reads.
    3) For all the reads in the middle, I have to make sure that the first
    read has successfully blocked the writes. The way I implemented this
    is through the R semaphore. Once the first read operation successfully
    takes the W semaphore, it gives a R semaphore. This indicates that the
    read resource is now available. Now that the R semaphore has become
    available, the 2nd read unblocks and continues its reading of the
    resource. But, if I want a 3rd read to unpend, I must give the R
    semaphore again. Thus, my 2nd read must also give a R semaphore...and
    so on....

    Now, I see 2 problems with my implementation:
    1) The write operation will NEVER run, as long as read operations keep
    getting called. This is like a priority inversion, but I don't know
    that it quite qualifies as a traditional priority inversion example
    (meaning, I doubt mutex semaphores will solve this problem).
    2) I'm not sure if this scenario is even possible. If 2 read
    operations start execution at nearly the same time. Say the 2nd read
    (the one in which readcount == 2) grabbed the R semaphore BEFORE the
    first read was able to (the one in which readcount==1). This may or
    may not be possible. The 1st read semaphore would have had to reach
    the readcount++ line BEFORE the 2nd read; yet the 2nd read reached the
    semTake(R,WAITFOREVER) BEFORE the 1st read. This could only happen if
    the task scheduler somehow scheduled a larger timeslice for the 2nd
    read, than it did for the 1st read.

    The 2nd problem I may be able to solve with some sort of a taskLock()
    call inside the read function. The first problem, however, I have no
    clue as to how to deal with it.

    Of course, if there is another simpler or more robust solution to this,
    I welcome to hear it! I threw this together, but I have very little
    experience with VxWorks... I would like to know how others have
    approached this problem.


  6. Re: VxWorks Beginner - Semaphore question.

    Is there a particular reason why you wouldn't use a regular mutex
    semaphore togovern all accesses (reads and writes) to the resource?
    Like so:

    SEM_ID mutex = semMCreate(SEM_Q_PRIORITY | SEM_Q_INVERSION_SAFE);
    /* If you'd prefer FIFO execution, then it would be
    * SEM_ID mutex = semMCreate(SEM_Q_FIFO);
    */

    void READ()
    {
    semTake(mutex, WAIT_FOREVER);

    //
    // perform read
    //

    semGive(mutex);
    }

    void WRITE()
    {
    semTake(mutex, WAIT_FOREVER);

    //
    // perform write
    //

    semGive(mutex);
    }

    So with the above, if the semaphore is in use by task 'A' and another
    task 'B' calls either READ() or WRITE(), task 'B' will change state to
    PENDING at the semTake() call, until task 'A' calls semGive(). This
    puts task 'B' back into READY state and it will then "have" the
    semaphore, blocking others from accessing the resource.

    If you have multiple tasks involved, they will get lined up in a PEND
    Queue while they each wait on the semTake() call to return. The order
    of the tasks in that PEND Queue is dependent on the flags passed to
    semMCreate(). I've coded it above to be ordered by task priority (with
    an added flag to help avoid priority inversion problems). Or I've
    included in the comment the way to make a general "first come, first
    served" mutex.

    This is a rather basic concept for a multi-threaded/-tasked embedded
    OS. You may want to brush up on real-time programming concepts
    before diving much deeper. Google is your friend.

    HTH,
    -JPL


  7. Re: VxWorks Beginner - Semaphore question.

    Alydis,

    You're trying to implement a classic Reader/Writer lock, and you've
    discovered that it's not an easy thing to do - there are several
    implementations available online (google is your friend) but you'd have
    to translate them into vxWorks terms yourself. In addition, the
    performance hit of having to take multiple mutexes can be worse than
    the problem you're trying to solve by allowing parallel readers.

    I agree with jpl's suggestion and would recommend that you just use a
    regular mutex to protect the linked list. If that's no good because it
    would need to be held for too long a period, then maybe consider using
    a mutex for the list and a reference counter in each list item; you
    have to own the mutex to traverse or modify the list, but while you're
    looking at (reading) an individual item on the list you take a
    reference to it and release the mutex. You would need extra mutexes to
    protect individual list items if they're modifyable in situ, but you
    might also consider using read/copy/update instead - this is a very
    powerful technique that the Linux kernel uses to resolve this kind of
    problem and well worth looking up.

    HTH,

    - Andrew


  8. Re: VxWorks Beginner - Semaphore question.

    I understand how mutex semaphores work JPL, but I'm not sure if you
    understand what I was trying to do.

    I realize that I can use a simple mutex and lock out reads and writes
    such that there can be only 1 task accessing the list at a time.
    Regardless of its operation.

    What I was trying to implement, was a system in which reads and writes
    were differentiated, such that writes take exclusive control of the
    resource. But reads are capable of sharing the resource with other
    reads.

    Now, Andrew brings up a good point, in that... since it seems like a
    "Reader/Writer lock" is something that may be a bit tricky to
    implement. If the implementation costs a great deal over overhead,
    then it may not be worth it at all to schedule multiple parallel tasks,
    and work with a system that simply blocks reads.


+ Reply to Thread