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

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.

Originally Posted by Cactus_Hugger

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..

Originally Posted by Cactus_Hugger

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..

Originally Posted by Codeplug

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

Originally Posted by Codeplug

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)

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..

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);
   }

you are right..
they were typos

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

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?