reader/writer locks on shared mem using semaphores

This is a discussion on reader/writer locks on shared mem using semaphores within the C Programming forums, part of the General Programming Boards category; I think posting the actual problem will help Suppose we have a shared memory segment shared between 3 processes. Each ...

  1. #1
    Devil™
    Join Date
    Oct 2007
    Location
    IIT-Kharagpur, India
    Posts
    104

    reader/writer locks on shared mem using semaphores

    I think posting the actual problem will help
    Suppose we have a shared memory segment shared between 3 processes.
    Each of these processes keeps trying to write to the memory or read from it
    randomly. We are to allow only one writer at a time to prevent an inconsistent
    value from being written. Implement this using semaphore. Keep in mind that
    multiple readers can be allowed at once. Also, make sure that no process is
    starved in getting access to the shared memory i.e. there is no possibility of an
    infinite waiting time.
    I am trying to implement a reader/writer lock on shared memory accessed by multiple process..

    its like this:
    every process can access the shared memory and read/write at random..
    only one writer should be writing at any given point of time..
    where as any number of readers can read at the same time..
    there should not be starvation too..

    I know to use semaphores & shared memory.. I am asking if this is the right way to do it..
    here is the pseudo-code for a process

    (my coding style will be little weird, as I put P()= increase & V() = decrease.. anyway this is not a problem as long as we a make sure that end is always 0, you can suggest your method with conventional P(), V())
    Code:
    /*******************************************************
     *    assume that following are semaphores and 
     *    are initialized in the parent process as follows
     *    initialize_semaphore anyone_inside = 0
     *    initialize_semaphore writers_waiting = 0
     *    initialize_semaphore write_mode = 0
     *    Blue colored statements are executed in one semop
     ********************************************************/
    int main()
    {
         /* all stupid stuff here */
    
        /* process trying to access critical section */
        if( want_to_read )
        {
            if(sem_wait(writers_waiting)) // wait till writers_waiting = 0
            {
                if( sem_wait(write_mode)) // wait till write_mode = 0
                {
                    P(anyone_inside); // increment => anyone_inside++;
    
                    read();
    
                    V(anyone_inside); // decrement => anyone_inside--;
                }
            }
        }
        else // trying to write
        {
            P(writers_waiting); // increment => writers_waiting++
    
            if(sem_wait(anyone_inside)) // wait till anyone_inside = 0
            {
                P(anyone_inside);// increment => anyone_inside++;
                P(write_mode); // increment => write_mode = 1;
                
                V(writers_waiting); // decrement => writers_waiting--;
    
                write();
                
                V(write_mode); // decrement => write_mode--
                V(anyone_inside); // decrement => anyone_inside--
            }
        }
    }
    is this how it is done?
    will this work?
    or any betterway?

    P.S: the trivial single semaphore solution like one process at a time access is not needed
    Last edited by gibsosmat; 11-16-2007 at 09:38 AM.
    C's Motto: who cares what it means? I just compile it!!

  2. #2
    int x = *((int *) NULL); Cactus_Hugger's Avatar
    Join Date
    Jul 2003
    Location
    Banks of the River Styx
    Posts
    902
    Thread stuff is mostly OS specific, although POSIX threads are available for numerous OSs. What are you using? (The above won't work, by itself...)

    Also, though this seems to be pseudo-code, watch the assignments in the if() statements -- you likely mean for an equality test there.
    long time; /* know C? */
    Unprecedented performance: Nothing ever ran this slow before.
    Any sufficiently advanced bug is indistinguishable from a feature.
    Real Programmers confuse Halloween and Christmas, because dec 25 == oct 31.
    The best way to accelerate an IBM is at 9.8 m/s/s.
    recursion (re - cur' - zhun) n. 1. (see recursion)

  3. #3
    Devil™
    Join Date
    Oct 2007
    Location
    IIT-Kharagpur, India
    Posts
    104
    Quote Originally Posted by Cactus_Hugger View Post
    Thread stuff is mostly OS specific, although POSIX threads are available for numerous OSs. What are you using? (The above won't work, by itself...)
    I am using System V semaphores (heavy semaphores sys/sem.h), On linux..

    Quote Originally Posted by Cactus_Hugger View Post
    Also, though this seems to be pseudo-code, watch the assignments in the if() statements -- you likely mean for an equality test there.
    I am using semop( ) for checking of some_semaphore = 0 and then proceed afterwards..
    Last edited by gibsosmat; 11-15-2007 at 11:28 PM.
    C's Motto: who cares what it means? I just compile it!!

  4. #4
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,662
    >> there should not be starvation too..
    Are you saying that the implementation should be "fair"? Or is it ok to be unfair by favoring reader or writer access?

    gg

  5. #5
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,662
    I'm a little confused by the pseudo-code.....
    Where you have statements like "if(writers_waiting = 0)" - is that a "sem_getvalue()" operation? Or does that really mean "writers_waiting.P()" on entry of the block and "writers_waiting.V()" on exit of the block?

    gg

  6. #6
    Devil™
    Join Date
    Oct 2007
    Location
    IIT-Kharagpur, India
    Posts
    104
    Quote Originally Posted by Codeplug View Post
    >> there should not be starvation too..
    Are you saying that the implementation should be "fair"? Or is it ok to be unfair by favoring reader or writer access?

    gg
    it can be fair/unfair..
    like readers can be given priority..
    but the priority should not make the writer process starve

    starvation in the sense.. no process should be left waiting for infinite time even if the random requests are intelligently placed..
    i.e every process will get access to the shared memory in finite time, no matter what the sequences of the semaphore requests are

    Quote Originally Posted by Codeplug View Post
    I'm a little confused by the pseudo-code.....
    Where you have statements like "if(writers_waiting = 0)" - is that a "sem_getvalue()" operation? Or does that really mean "writers_waiting.P()" on entry of the block and "writers_waiting.V()" on exit of the block?

    gg
    I think you are talking about POSIX semaphores that you get from '#include <semaphore.h>'.. like sem_open( ), sem_getvalue( )
    I am using UNIX System V semaphores, they come from '#include <sys/sem.h>'.. like semget( ), semcntl( ),semop( )
    (these are called so coz they were introduced in UNIX System V IPC)
    they are also same like these (POSIX) semaphores..
    but I get to access a set of semaphores with sem_open.. and I can do a set of operations on those semaphore set using semop( )

    I didnt mean that sem_getvalue( ) from the code
    Code:
    if(writers_waiting = 0) // this is not like sem_getvalue()
    
    //   it is like
    
    if(sem_wait(writers_waiting))
    
    /******************************************
     *    I didnt write it this way because 
     *    I will be executing all the logic in  
     *    one semop( ) instructions array
     ******************************************/
    well assume that
    something_sema++ = P(something_sema)
    something_sema-- = V(something_sema)
    C's Motto: who cares what it means? I just compile it!!

  7. #7
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,662
    Ok - I think I follow now. Here's your pseudo-code simplified by removing the "if" semantics on sem_wait()'s, and by putting all atomic operations on a single line. I also removed P() and V() semantics since it's a bit misleading. In your example, the P and V operations never block since the semaphore is just being used as a counter.
    Code:
        if (want_to_read)
        {
    A       sem_wait(writers_waiting);
    B       sem_wait(write_mode);
    C       ++anyone_inside;
    D       read();
    E       --anyone_inside;
        }
        else // trying to write
        {
    F       ++writers_waiting;
    G       sem_wait(anyone_inside);
    H       ++anyone_inside; ++write_mode;
    I       --writers_waiting;
    J       write();
    K       --write_mode; --anyone_inside;
        }
    Now imagine that you have a reader thread and writer thread.
    - Reader advances to (C) then context switch before executing (C)
    - Writer advances to (J) then context switch
    - You now have a reader and a writer playing in the same sandbox!

    The easy solution is to execute (A), (B), and (C) atomically via semop(). Then (D) can only be executed once there are no writers and no writers are waiting. And once any reader thread reaches (D), any writer thread will block at (G).

    >> i.e every process will get access to the shared memory in finite time, no matter what the sequences of the semaphore requests are
    As it is now, your implementation is very "writer favorable". As soon as any writer reaches (G), all subsequent readers will block until there are no writers and no writers waiting. This could starve readers under a heavy writer load.

    Based on your assignment quote, starving your readers probably isn't acceptable Start thinking about ways to prevent "infinite starvation" - it doesn't have to be fair.

    gg

  8. #8
    Devil™
    Join Date
    Oct 2007
    Location
    IIT-Kharagpur, India
    Posts
    104
    thanks for your help..
    I am trying to solve that starvation..
    But most of the articles on net are using locks for read/write access..
    I will figure it out..
    any help from you is appreciated..
    C's Motto: who cares what it means? I just compile it!!

  9. #9
    Devil™
    Join Date
    Oct 2007
    Location
    IIT-Kharagpur, India
    Posts
    104
    This is called third readers-writers problem.. and its standard..
    I didnt know that..
    I got it done
    here it is..
    Code:
      /* to keep track of process entering and leaving shared mem */
      int writers=0, readers=0;
    
      /* control the readers, writers access by process */
      semaphore mutex=1;
    
      /* control the actual access to the shared memory for process */
      semaphore resource=1;
    
     ...
    
     if(want_to_write)
       {
         /* want to write to shared memory */
         sem_wait(mutex);
    
         writers++;
         sem_post(mutex);
         
         sem_wait(resource);
         
         /* writing to the resource */
         memory = myvalue; 
         writers--;
    
         sem_post(mutex);
         sem_post(resource);
       }
     else
       {
         /* want to read */
         sem_wait(mutex);
         if(writers > 0 || readers == 0)
           {
             sem_post(mutex);
             sem_wait(resource);
             wait(mutex);
           }
    
         readers++;
    
         sem_post(mutex);
    
         printf("Shared Memory: %d\n",memory);
    
         sem_wait(mutex);
    
         readers++;
    
         if(readers == 0)
           sem_post(resource);
         sem_post(mutex);
       }
    C's Motto: who cares what it means? I just compile it!!

  10. #10
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,662
    There are a couple of "typo's". Let me know if my corrections are what you intended.
    Code:
    /* to keep track of process entering and leaving shared mem */
    int writers=0, readers=0;
    
    /* control the readers, writers access by process */
    semaphore mutex=1;
    
    /* control the actual access to the shared memory for process */
    semaphore resource=1;
    
    if (want_to_write)
    {
        sem_wait(mutex);
        writers++;
        sem_post(mutex);
         
        sem_wait(resource);
        memory = myvalue; 
        
        sem_wait(mutex);
        writers--; 
        sem_post(mutex);
        sem_post(resource);
    }
    else /* want to read */
    {
        sem_wait(mutex);
        if (writers > 0 || readers == 0)
        {
            sem_post(mutex);
            sem_wait(resource);
            sem_wait(mutex);
        }
    
        readers++;
        sem_post(mutex);
        
        printf("Shared Memory: %d\n", memory);
        
        sem_wait(mutex);
        readers--;
        if (readers == 0)
            sem_post(resource);
        sem_post(mutex);
    }
    gg

  11. #11
    Devil™
    Join Date
    Oct 2007
    Location
    IIT-Kharagpur, India
    Posts
    104
    you are right..
    they were typos
    C's Motto: who cares what it means? I just compile it!!

  12. #12
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,662
    This version does look correct. However, whether or not starvation can occur really depends on the "semaphore resource" implementation. In other words, you need to know "who will unblock next" whenever a "sem_post(resource)" call is made. If it's done in a FIFO fashion for example, then you're ok.

    gg

  13. #13
    Devil™
    Join Date
    Oct 2007
    Location
    IIT-Kharagpur, India
    Posts
    104
    this code is same for all the process accessing the memory..
    so the one who calls resource first will do it..
    though documentation didnt specify if the sem_wait requests are processed in FIFO fashion..
    as this works fine I didnt give much thought to that..

    even if some process holds on the sema 'resource' and just releases using sem_post(resource)
    I didnt understand why should I be bothered if this is going to be FIFO or not..

    for instance lets say the sema requests are serviced at random.
    In that case there is probability for the process to get the resource and is certainly not 0 (zero)
    non zero because there is no priority specified or the pid..
    so any given process might take infinitely long time (probability is too less for that unlucky process)
    but NOT infinite time(as probability is not 0) even if the processes requests are manipulated
    C's Motto: who cares what it means? I just compile it!!

  14. #14
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,662
    I understand what you're saying - but some folks just *have* to have gaurentees

    As a counter example - assume the semaphore was priority based, and all writers had higher priority (for whatever reason) - then you could have reader starvation under a heavy writer load.

    But assuming the <sys/sem.h> implementation is somewhat fair - you should be ok.

    gg

  15. #15
    Devil™
    Join Date
    Oct 2007
    Location
    IIT-Kharagpur, India
    Posts
    104
    hmm..
    may be it can be.. but this is just an assignment.. so I didnt dig in too much

    Also I didnt use those System V semaphores for this.. i.e <sys/sem.h>
    though they are flexible & powerful they are painful to debug..
    like one semop() executes many operations (ex: sem_wait, sem_post, sem_trywait etc..) atomically and returns fail if any one of them fails..
    It becomes little difficult to figure out/debug where things have gone wrong..

    so I choose UNIX Philosophy..
    Do one thing, Do it well

    I used POSIX semaphores (<semaphore.h>) for now..

    keeping this aside.. many times I wounder why are we taught few things that are practically not used..
    how ppl get to know how the things should be done in the software industry.. will there be someone like a guide who tells this is how you should do and stuff?
    C's Motto: who cares what it means? I just compile it!!

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. reader/writer problem using semaphores
    By jalex39 in forum C Programming
    Replies: 3
    Last Post: 03-06-2009, 08:54 PM
  2. Replies: 7
    Last Post: 02-06-2009, 11:27 AM
  3. Shared Memory semaphores?
    By Ironic in forum C Programming
    Replies: 0
    Last Post: 10-31-2008, 07:13 PM
  4. Managing shared memory lookups
    By clancyPC in forum Linux Programming
    Replies: 0
    Last Post: 10-08-2003, 04:44 AM
  5. Shared memory in Linux: B-TREE of structures
    By zahid in forum Linux Programming
    Replies: 3
    Last Post: 01-26-2002, 10:15 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21