Reader Writer Concurrency Problem (synchronization between threads)?

Question

I'm on the last part of a synchronization project for my OS class that involves the reader writer cs problem using semaphore and mutex variables.

I'm trying to wrap my head around the idea of true concurrency. Say we take the reader preference route. In order to signal the writer when the reader que is empty, we would need to track how many readers are in que.

To allow true concurrency we would not want to block access to the shared memory by any reader unless a que maximum was reached or the writer was active. In this case, when checking the amount of readers in que, we could see zero in one reader thread and signal the writer, but possibly have another reader access the memory before the writer gets time on the processor, thereby allowing a reader to access the memory at the same time the writer is writing to it.

In the example implementations I've seen, most people seem to surround the reader critical areas with a mutex. While this does provide a solution to the reader writer simultaneous access issue, it also seems to me eliminate true concurrency. When the implementations mentioned above run, really only one thread can read at a time.

So my question is, what can I do that will preserve true concurrency, but still allow me to block all reader threads when a writer is active?

I actually may have thought of something, but I'm going to post this to get your thoughts in case I'm wrong or just to see if there's a better way. My plan is a simple global variable, set it to 1 when the writer is active, reader when entering critical section reads if var is 0, skips if 1(writer active).


My set up:

WRITER:
sem_wait(&mutex);
critical section;
sem_signal(&readers);

READER:
sem_wait(&spaces);
sem_signal(&readers);

readCounter++;
critical;
readcounter--;
if (readCounter == 0) sem_signal(&mutex);

sem_wait(&readers);
sem_signal(&spaces);



mutex is initialized to 0 and blocks WRITER until a signal arrives from READER indicating the reader que is empty.

readers is initialized to 0 and incremented when READER begins, decremented when it ends.

spaces is used to control the maximum concurrent readers allowed, initialized to user preference, I arbitrarily chose 7. When READER starts spaces is decremented, when it ends it gets incremented.



This implementation seems to do a good job of preserving the integrity of concurrency among readers, but the issue I presented arises when the counter is being checked in one thread where the value will show 0, while at the same time another thread is entering the critical area, meaning it will have already signaled the readers semaphore. When the first thread sees 0 as the counter value it signals the writer, after which it should call the wait function on the readers semaphore, which if the que were truly empty the semaphore would block at this call. Since another thread can and likely is running in the critical section, the semaphore has already been signaled, preventing the block that should occur.

Basically the readers never really stop, or could in some cases, not in others, but unpredictable. This is the dilemma, true concurrency is unpredictable. Hmm...hopefully someone out there can help me through this, no pun intended, "writers block."

Answer 1

Have you tried posting this one on stackoverflow.com? You might get an answer there.



This question is legit, but way too advanced for YA!. Someone on SO might take the time to answer this.

Answer 2

ALL 3 ive been a reader considering 1st grade (i will examine 4 hundred wpm) author ever considering 4 th grade (gotten particularly some awards) Listener: i became born (i had to take heed to my dad and mom and couldnt say something :)

Answer 3

I think that what you are attempting to implement is a reader/writer lock which can be held by multiple readers or a single writer at any given time..



Yes, you need a counter of the number of readers and yes, you need to protect the access to the counter.



I am not quite sure what semaphore primitives you have available to you or if you are allowed (or required) to define them for yourself, but this is easy if you have a counting semaphore.



Let MAX_READERS be the maximum number of concurrent readers allowed and suppose that we have semaphore operations:



sem_init()

sem_acquire()

sem_release()



with the (I hope) obvious semantics:



Initialize the value of the semaphore to MAX_READERS.



semaphore sem;

sem_init(&sem, MAX_READERS);



reader:

sem_acquire(&sem, 1);

... critical section ...

sem_release(&sem, 1);



writer:

sem_acquire(&sem, MAX_READERS);

... critical section ...

sem_release(&sem, MAX_READERS);





This forces the writer to block until there are no readers and blocks readers until there is no writer.



Edited to add the following clarification:



You seem to misunderstand how the counting semaphore works.



Think of it as a something that allocates a finite number or resources - in this case MAX_READERS worth of tickets to allow you to enter the critical region.



Initially there are MAX_READERS tickets available.



When a reader wants to enter the critical zone it requests 1 ticket - if it gets the ticket then it enters the critical region and when it leaves the critical region it gives the ticket back - while the reader is in the critical region there are *less* than MAX_READERS tickets available.



Up to MAX_READERS readers can be in the critical region at the same time - each holding *one* ticket.



When a writer wants to enter the critical region it requests *all* of the tickets - MAX_READERS worth - it can only get *all* of the tickets when there are *no* readers in the critical region (because if there was even one reader in the critical region there would be less than MAX_READERS tickets available) - if it can get all of the tickets then the writer enters the critical region and when it leaves the critical region it gives *all* of the tickets back - otherwise it blocks.



In summary - if there is even a single reader in the critical region a writer will be blocked because it cannot acquire *all* of the tickets - when it *does* get all of the tickets it knows that there can be no readers in the critical region. Also for as long as the writer is in the critical region holding all of the tickets no reader (or another writer for that matter) can enter because the writer holds *all* of the tickets and nobody else can get one.



Sorry, I don't know how to explain it any clearer than that ...