ONLY ONE OF THE SOLUTIONS IN THIS FILE APPEARS TO BE CORRECT. WHICH ONE? /*************************************************************************/ #include "prototypes.h" typedef int semaphore; semaphore mutex = 1; semaphore mutexR = 1; semaphore wrt = 0; semaphore rdr = 0; readcount=0; wait_to_read = FALSE; wait_to_write = FALSE; busy = FALSE; void writer(void) { /* ENTERCS_WR: */ P(mutex); if ((readcount != 0) || (busy == TRUE)) { wait_to_write = TURE; P(wrt); } busy = TURE; V(mutex); /* Go into database */ /* EXITCS_WR */ busy = FALSE; if (wait_to_read == TURE) { V(rdr); } else { if(wait_to_write == TURE) V(wrt); wait_to_write = FALSE; } } void reader() { /* ENTERCS_RD: */ P(mutex); if ((busy == TRUE) ||( wait_to_write == TRUE)) { wait_to_read = TRUE; P(rdr); } readcount++; V(mutex); /* Go into database */ /* EXITCS_RD: */ P(mutexR); readcount--; if (readcount ==0) && (wait_to_write== TRUE)) { V(wrt); wait_to_write = FALSE; } V(mutexR); } *Note: Here we suppose there is first-come-first-enter-in-database rule. /********************************************************************/ It's actually a limited waiting time solution. However, if NUM is properly chosen for a practical problem, then no starvation will happen although a writer may be hungry for a while ( when many readers and NUM too big) /***********************************************************************************/ #define NUM 10 /* # of maximum readers allowed before a writer */ typedef int semaphore; semaphore mutex=1; /* controls access to 'rc' */ semaphore db=1; /* controls access to the data base */ int rc=0; /* # of processes reading or wanting to */ int rwc=0; /* # of readers since last writing */ void reader(void) { while(TRUE){ P(&mutex); /* get exclusive access to 'rc' */ rc++; /* one reader more now */ rwc++; /* one more readers since last writing */ if(rc==1 or rwc==1) P(&db); /* if first reader (or since last writing)*/ V(&mutex); /* release exclusive access to 'rc' */ read_database(); /* access the data */ P(&mutex); /* get exclusive access to 'rc' */ rc--; /* one reader fewer now */ if(rc==0 or rwc==NUM){ /* if last reader of NUM readers have done */ rwc=0; V(&db); } V(&mutex); /* release exclusive access to 'rc' */ use_data(); } } void writer(void) { while(TRUE){ think_data(); /* noncritical section */ P(&db); /* get exclusive access */ write_database(); /* update the data */ V(&db); /* release exclusive access */ } } /*****************************************************************************/ This solution comes from the following points: (1) If there is a writer waiting, then no new reader will be allowed to start. But old readers will be allowed to finish their work. ( thus writer can get in after a while) (2) All readers waiting at the end of a writer should have priority over the next coming writer, otherwise reader will suffer starvation. /***********************************************************************************/ typedef int semaphore; semaphore mutexW=1; /* controls access to 'busy' etc. */ semaphore mutexR=1; /* controls access to 'readcount' */ semaphore wrt=1; /* controls writing access to the data base */ semaphore rdr=1; /* controls reading access to the data base */ int readcount=0; /* # of processes reading or wanting to */ logic busy=FALSE; logic wait_to_read=FALSE; logic wait_to_write=FALSE; void reader(void) { while(TRUE){ P(&mutexR); /* get exclusive access to 'readcount' */ if(readcount==0)P(&rdr); /* first reader ... */ if(busy==TRUE OR wait_to_write==TRUE){ /* if writing or waiting to write */ wait_to_read=TRUE; V(&mutexR); /* release access to 'readcount' for previous readers*/ P(&rdr); /* P(&rdr) actually blocks new reader if sb. is */ readcount++; /* counting readers waken by V(rdr) */ } /* writing or wanting to write */ else{ readcount++; /* counting reader */ V(&mutexR); /* release exclusive access to 'readcount' */ } read_database(); /* access the data */ P(&mutexR); /* get exclusive access to 'readcount' */ readcount--; /* one reader fewer now */ if(readcount==0){ V(&wrt); wait_to_write=FALSE; } V(&mutexR); /* release exclusive access to 'readcount'*/ use_data(); /* noncritical section */ } } void writer(void) { while(TRUE){ think_data(); /* noncritical section */ P(&mutexW) /* get exclusive access to 'busy' etc. */ if(readcount != 0)wait_to_write=TRUE; P(&wrt); busy=TRUE; write_database(); /* update the data */ busy=FALSE; if(wait_to_read==TRUE){ while( rdr != 0)V(&rdr); /* can we do this ? */ wait_to_read=FALSE; } else{ V(wrt); wait_to_write=FALSE; } V(&mutexW); /* release exclusive access */ } } Here is the solution I have come up with to the readers/writers problem, using semaphores. The only extension I've made to the semaphore type is the addition of a routine semval(S), which returns S.value. Note that, though I've used C syntax throughout, this is meant only as pseudo-code. (The semaphore initialization code is not correct, for instance.) I've tried to comment my solution liberally, but if anything remains unclear, please let me know, and I'll try to explain what I meant. I have given this solution a great deal of thought, and I do believe it will work. I have based my solution on the monitor algorithm you handed out in class. I renamed some of the variables to give them more natural names, and I used the following rules for converting to semaphores: o Create a binary semaphore, called mutex, to prevent race conditions between the processes calling these functions. o When entering any routine, call P(mutex). o When leaving a routine normally (no signal), call V(mutex). o Create a synchronization semaphore for each condition variable. The initial value should be 0, and the absolute value of the semaphore represents the number of processes waiting. o When leaving a routine with a signal, call V(sem). Only do this if one or more processes is actually waiting for sem. Do not release mutex, as it is being "granted" to the waiting process. o When it is necessary to wait for a semaphore, call V(mutex) first (to allow other processes to access these functions), then P(sem). When P(sem) returns, mutual exclusion will again be guaranteed for the current process. Cheers, /////////////////////////////////////////////////////////////////////// // // Filename: ReadersWriters.c // // Description: A solution to the readers/writers problem that uses // semaphores instead of a monitor. // // Notes: Some of this is just pseudo-code; it will not compile. // The basic algorithm is taken from Tanenbaum, Fig. 2-16 // // Date Name Comments // ------------ --------------- --------------------------------------- // 24 Sep 1996 Michael Barr Extra-credit for ENEE 648I. // // // Copyright (c) 1996 by E.E. Man Consulting. All rights reserved. /////////////////////////////////////////////////////////////////////// #include "sem.h" // Semaphore interface details. int nReaders = 0; // There are no readers on startup. boolean bWriting = FALSE; // There is no writer on startup. sem sRead = 0; // Synchronization semaphore for reads. sem sWrite = 0; // Synchronization semaphore for writes. sem mutex = 1; // Binary semaphore to prevent races. /////////////////////////////////////////////////////////////////////// // // Function: enterReader() // // Description: Called by reader before reading database. // // Comments: Allows reader access only if no process is, or would // like to be, writing. // /////////////////////////////////////////////////////////////////////// enterReader() { P(mutex); // Obtain exclusive access to globals. // Block if a write is in progress or a writer is waiting. // if ((bWriting == TRUE) || (semval(sWrite) < 0)) { V(mutex); // Release exclusive access to globals. P(sRead); // Wait for reader right-of-way. // When we wake, we have exclusive access to globals. } // This process now has read permission. // nReaders++; // Increment the number of readers. // If another reader is waiting, wake him up. Otherwise, // release the mutex, to allow new processes to enter. // if (semval(sRead) < 0) { V(sRead); // Wake next reader. } else V(mutex); // Release exclusive access to globals. } // enterReader() /////////////////////////////////////////////////////////////////////// // // Function: exitReader() // // Description: Called by reader after reading database. // // Comments: Decrement reader count. If we're the last reader, // wake the waiting writer (if any). // /////////////////////////////////////////////////////////////////////// exitReader() { P(mutex); // Obtain exclusive access to globals. nReaders--; // Decrement the number of readers. // If no more readers and a writer is waiting: wake writer. // if ((nReaders == 0) && (semval(sWrite) < 0)) { V(sWrite); // Wake next writer. } else V(mutex); // Release exclusive access to globals. } // exitReader() /////////////////////////////////////////////////////////////////////// // // Function: enterWriter() // // Description: Called by writer before writing database. // // Comments: Allows the first process to write, once all readers // currently reading have exited. While waiting, new // readers are kept out. // /////////////////////////////////////////////////////////////////////// enterWriter() { P(mutex); // Obtain exclusive access to globals. // Block if readers are active or another writer is active. // if ((nReaders > 0) || (bWriting == TRUE)) { V(mutex); // Release exclusive access to globals. P(sWrite); // Wait for writer right-of-way. // When we wake, we have exlusive access to globals. } // This process now has write permission. // bWriting = TRUE; // Indicate write in progress. V(mutex); // Release exclusive access to globals. } // enterWriter() /////////////////////////////////////////////////////////////////////// // // Function: exitWriter() // // Description: Called by writer after writing database. // // Comments: If readers are waiting, wake the first. If not, but // another writer is waiting, wake it. // /////////////////////////////////////////////////////////////////////// exitWriter() { P(mutex); // Obtain exclusive access to globals. bWriting = FALSE; // Write no longer in progress. // Grant right-of-way to readers (if any) or next writer. If // no one is waiting, release mutex. // if (semval(sRead) < 0) { V(sRead); // Wake next reader. } else if (semval(sWrite) < 0) { V(sWrite); // Wake next writer. } else V(mutex); // Release exclusive access to globals. } // exitWriter() The following sequence of events would lead to an undesired event in the algorithm you gave in class : 1. Writer1 comes first. So, Busy = true. 2. Reader1 comes next. So, wait_to_read = true and blocked at rdr. 3. Reader2 comes next. Blocked at mutexr1. 4. Writer2 comes. wait_to_write = true and blocked at wrt. 5. Writer1 leaves. rdr released. So, Reader1 executes and releases mutexr1. When Reader2 executes, it is blocked at rdr because wait_to_write is true. Thus, after reader1, writer2 goes in and not Reader2. What we had wanted was that when a writer is done and readers are waiting, all readers get in. But in the above algorithm, only one reader gets in and the rest are blocked, i.e., waiting for a writer which came after them to finish. This can be taken care of by storing the number of readers waiting when a writer comes in, in a global variable and using it to check in EnterCS_RD. int no_reader_waiting=1; EnterCS_WR: P(mutexw); if (readcount != 0 or busy == true) then wait_to_write=true; no_reader_waiting=mutexr1.val; P(wrt); busy=true; V(mutexw); EnterCS_RD: P(mutexr1); if (busy == true or (wait_to_write == true && mutexr1.val < no_reader_waiting )) then wait_to_read=true; P(rdr); readcount++; V(mutexr1); The exit routines remain same. I wrote a solution that I think works. It involves readers/ writers and a schedualer. The schedualer works with a bounded buffer with two processes accessing the buffer:- register and wakeup. Here goes: mutex =1 Read =1 Write =1 Reader[n] enter CS: P(mutex) register (R, n); // enter queue wakeup; // this insures that it wakes // if first one in the queue V(mutex) Read_OK[n].wait // wait for schedualer P(Read) ++Read_count; wakeup; // wakeup waiting readers V(Read) Reader[n] leaves CS: P(Read) --Read_count; wakeup; //wakeup readers or writer V(Read) Writer[n] enter CS: P(mutex) register (W, n); wakeup; // wake up self V(mutex) Write_OK[n].wait P(Write) ++Write_count; V(Write) Write[n] leaves CS: P(Write) --Write_count; wakeup; //wake up readers or writer V(Write) For the wake up and register, they will use the solution for the bounded buffer. Therefore, only the functions they perform will be described. wakeup CS: if (Read_count >=0 && Write_count=0 && start*=R) Read_OK[n].signal ++start; if (Read_count =0 && Write_count=0 && start*=W) Write_OK[n].signal ++start; signal (type, n) CS: // type is either R or W append_table (type, n); ++end; ______________________________ type | number ------------------------------ start >> R | 1 R | 2 W | 3 end >> EnterCS_RD: P(mutexr1); if (busy==TRUE OR wait_to_write=TRUE) then wait_to_read=true; P(rdr) readcount++; V(mutexr1); ExitCS_RD: P(mutexr2); readcount--; if(readcount==0) V(wrt); V(mutexr2); There is one obvious race condition in the reader code: Something can try to readcount++ and readcount-- at the "same time". Since it takes only one error to keep the algorithm from working, it is not necessary to find more errors, and attempt to band-aid this solution. Instead, I will implement the monitor solution using semaphores, such that it could be run on any system w/semaphores and a C compiler. semaphore MonMutex=1; /* semaphore to enforce a maximum of one process in the following four procedures at any time */ semaphore OK_to_read=0; /* block when not OK to read */ semaphore OK_to_write=0; /* Block when not OK to write */ /* All of the following variables are protected by MonMutex to avoid races */ int busy=false; int read_count=0; int waiting_to_read=0,waiting_to_write=0; /* Number of processes waiting */ start_read() { P(MonMutex); if(busy || waiting_to_write) { waiting_to_read++; V(MonMutex); /* Release the mutex so others can start */ P(OK_to_read); /* Block until OK to read */ waiting_to_read--; /* When we return from P, we will have the MonMutex back */ } read_count++; if(waiting_to_read) V(OK_to_read); /* Signal the next reader, hold mutex */ else V(MonMutex); /* Normal exit */ } /* Note: a straightforward inplemenation of the monitor would not have the if(waiting_to_read)... This would cause the system to lose the MonMutex unless there is a process to signal on OK_to_read This book probably uses a slightly different implemenation of monitors than Tanenbaum. From observeration, 'signal' will only signal something if it exists; else it will do a normal exit. */ end_read() { P(MonMutex); read_cnt--; if(read_cnt==0 && waiting_to_write) V(OK_to_write); /* signal writers */ else V(MonMutex); /* Else leave normally */ } start_write() { P(MonMutex); if(read_cnt!=0 || busy) { waiting_to_write++; V(MonMutex); /* Release mutex */ P(OK_to_write); /* block until OK to write */ waiting_to_write--; } busy=true; V(MonMutex); } end_write() { P(MonMutex); busy=false; if(waiting_to_read) V(OK_to_read); /* signal readers */ else if(waiting_to_write) V(OK_to_write); /* signal writers */ else V(MonMutex); /* normal exit */ } Statement of the problem : - Any number of readers can read the buffer as long as there is no writer waiting. - The first writer in the writers' queue is allowed to write after all readers currently reading the buffer have finished reading the buffer. - During the time the writer is writing into the buffer, new readers and writers are put into readers' and writers' queues respectively. - After the present writer has finished writing into the buffer, the next writer is allowed to write only if there is no reader in the readers' queue. - After a writer has finished, if there are both readers in the readers queue and writers in the writers queue, then 'all waiting readers' enter next (even if they arrived after the waiting writer), but new readers (who arrive after the readers already waiting all entered the CS) must wait. - This alternation between one writer and one or more readers repeats. *************************************************************************** Solution : ----------- /* declarations and initialization */ semaphores readers_queue = writers_queue = 0; semaphore mutex = 1; /* mutual exclusion */ integer reader_q_count = 0, /* no. of readers waiting to read */ writer_q_count = 0, /* no. of writers waiting to write */ current_readers = 0; /* no. of readers currently reading buffer */ boolean busy_write = FALSE; /* to begin with, preference to readers */ /* procedure for the readers */ Reader() { P(mutex) /* block other readers changing 'reader_q_count' */ reader_q_count++ /* place new reader in reader queue */ /* check if a writer is using the buffer or if other writers are waiting */ if ((busy_write == TRUE) or (writer_q_count != 0)) { V(mutex) /* allow other readers to enter the readers_queue */ P(readers_queue) /* put reader into readers_queue */ P(mutex) /*mutual exclusion when reader is removed from queue */ } reader_q_count-- /* reader will now read buffer, exit from queue */ current_readers++ /* count readers that enter CS before the next writer arrives */ V(mutex) /* release semaphore */ read_buffer() P(mutex) /* block other readers changing 'current_readers' */ current_readers-- /* if there are no more readers currently in the critical section, allow the first waiting writer (if any)to write into the buffer */ if(current_readers == 0){ V(writers_queue) /* wake-up the first blocked writer */ V(mutex) /* release semaphore */ } else V(mutex) /* release semaphore */ } /* procedure for the writers */ Writer() { P(mutex) /* block other writers changing 'writer_q_count' */ writer_q_count++ /* place new writer in writer queue */ /* check if a writer is using the buffer or if there are readers currently reading the buffer */ if ((busy_write == TRUE) or (current_readers != 0)) { V(mutex) /* allow other writers to enter the writers_queue */ P(writers_queue) /* put writer into writers_queue */ P(mutex) /*mutual exclusion when writer is removed from queue */ } writer_q_count-- /* writer will now write into buffer, exit queue */ busy_write == TRUE /* prevent other readers and writers from accessing the buffer*/ V(mutex) /* release semaphore */ write_buffer() P(mutex) /* block other writers from changing 'busy_write' */ busy_write == FALSE /* allow other readers or writers to use buffer */ /* check if there are any readers waiting in the readers_queue. Allow 'all waiting readers' to enter next (even if they arrived after any waiting writer) */ if ( reader_q_count != 0){ for (i=1; reader_q_count; i++) { V(readers_queue)} /* wake up all waiting readers irrespective of the number of waiting writers */ reader_q_count = 0 /* new readers (who arrive after the readers already waiting all entered the CS) must wait */ } V(mutex) /* release semaphore */ } Firstly, I think the initial values of the semophores wrt and rdr should be 0 so that readers and writers will be blocked when the critical region is not available. Secondly, I think there are several problems with the algorithm: 1) There should be statements to set wait_to_write and wait_to_read to FALSE, otherwise they will always be TRUE. 2) When one writer exits the C.S., and if there are no readers waiting, it will increment the value of wrt no matter whether there are writers waiting or not. If there are not, after V(wrt), wrt = 1. Suppose now there is a reader coming, it will enter the C.S. since there is no writer waiting and no writer writing. But if before this reader leaves the C.S., there is a writer coming, it will go to { wait_to_write=TRUE; P(wrt); } but will not block because wrt = 0 after P(wrt). So it will also enter the C.S. Therefore, this algorithm fails to satisfy the mutual exclusive requirement. 3)Suppose one writer just leaves the C.S. and there is a reader waiting and no writer waiting. So wait_to_read=true. If context switch occurs between " busy = FALSE " and " if wait_to_read then V(rdr) ", and if a writer comes and gets CPU, it will enter the C.S. because readcount = 0 and busy = false. If before this writer leaves the C.S., the former writer gets the CPU back , goes to "if wait_to_read then V(rdr)", and wakes the waiting reader, this reader will also enter the C.S.. So now, the mutual exclusive requirement is not satisfied. Thirdly, the following is my solution to these problems: Init: readcount=0; busy=FALSE, wait_to_read=FALSE, wait_to_write=FALSE; wrt=0, rdr=0 EnterCS_WR: P(mutexw) if (readcount != 0 OR busy==TRUE) then wait_to_write=TRUE; P(wrt); wait_to_write=FALSE // for problem 1 busy = TRUE V(mutexw) ExitCS_WR disable interrupts// for problem 3 busy = FALSE if wait_to_read then V(rdr) else if wait_to_write then V(wrt)// for problem 2 enable interrupts// for problem 3 EnterCS_RD: P(mutexr1) if (busy==TRUE OR wait_to_write=TRUE) then wait_to_read=true; P(rdr) wait_to_read=FALSE// for problem 1 readcount++; V(mutexr1); ExitCS_RD: P(mutexr2) readcount--; if (readcount==0) V(wrt); V(mutexr2) now I would like to present my semaphore solution to the reader/writer problem, which uses a special function called semval(s) to check the value of a semaphore s; also I used an important "gate" semaphore that guards any reading of the global variables: Initial values: readcount=0, busy=false, gate.val=1, W.val=0, R.val=0 Enter_W: P(gate) /* gate guards checking & updating globals */ if(readcount!=0 or busy==true) V(gate); P(W); /* release gate before getting blocked, the blocked process always wakes up by an exiting writer or reader who's already using a gate so the same condition on gate semaphore is maintained when a writer returns from a block*/ busy=true; V(gate) Exit_W: P(gate) busy=false if (semval(R)<0) /* reader has priority after each writer exits*/ while (semval(R)<0) V(R) /*all readers waiting in the R blocked queue should be able to get in after a writer exits */ else if (semval(W)<0) /* if no reader in queue, wake the next ... */ V(W) /* ...writer only if there is one */ else V(gate) Enter_R: P(gate) if (busy==true or semval(W)<0) V(gate); P(R); /* again, release gate if blocked */ ++readcount; V(gate) Exit_R: P(gate) --readcount if (readcount==0) if(semval(W)<0) V(W) /* check that the W blocked queue is not..*/ else /* ...empty before doing V on it */ V(gate) I hope this is a valid solution using semaphores: EnterCS_WR: P(nomorereads) P(nowrites) ExitCS_WR: V(nomorereads) if (blockedreads.value<0) then while (blockedreads.value<0) V(blockedreads) else V(nowrites) EnterCS_RD: flag = 1 nowrites.value-- if (nomorereads.value = 0) then P(blockedreads) P(mutex) readcount++ flag = 0 V(mutex) ExitCS_WR: P(mutex) readcount-- if ((readcount = 0) AND (flag=0)) then V(nowrites) V(mutex) NOTE: V() is modified to set the semaphore value to zero when there are no actually blocked processes. This is needed because EnterCS_RD uses the command nowrites.value--. This is in effect a non-blocking P().