Readers-Writers & Dinning philosophers Problem

The Readers-Writers Problem

Suppose that a database is to be shared among several concurrently running processes. Some of these processes may want to only read the database, whereas others may want to update (that is, to read and write) the database. We distinguish between these two types of processes by referring to the former as readers and to the latter as writers. Obviously, if two readers access the shared data simultaneously no adverse effects on the result. If a writer and some other process (either a reader or a writer) access the database simultaneously, chaos may ensue.  To ensure that these difficulties do not arise and we require that the writers have exclusive access to the shared database while writing to the database. This synchronization problem is referred to as the readers-writers problem. It was originally stated, it has been used to test every new synchronization primitive. The readers-writers problem has a several variations, all involving the priorities.

The simple one is referred to as the first readers-writers problem, requires that no reader be kept waiting unless a writer has already obtained permission to use the shared objects. In another words, no reader should wait for other readers to finish simply because a writer is waiting. The second reader’s writer’s problem requires that, once a writer is ready to that writer performs its write as soon as possible. In other words if a writer is waiting to access the object, no new readers may start reading. A solution to either problem may result in starvation. In the first case the writers may starve in the second case the readers may starve. For this reason, other variants of the problem have been proposed. Next, we present a solution to the first readers-writers problem. Refer to the bibliographical notes at the end of the chapter for references describing starvation-free solutions to the second readers-writers problem.  In the solution to the first readers-writers problem, the reader processes share the following data structures:

Semaphore mutex, w.r.t into read count the semaphores mutex and w.r.t are initialized to 1 read count is initialized to 0. The semaphore w.r.t is common to both reader and writer processes. The mutex semaphore is used to ensure the mutual exclusion when the variable read count is updated. The read count variable keeps track of how many processes are currently reading the object. The semaphore w.r.t functions as a mutual-exclusion semaphore for the writers and it is also used by the first or last reader that enters or exits the critical section. It is not a used by the readers who enter or exit while other readers are in their critical sections. The code for a writer process is shown in Figure1.1 the code for a reader process is shown in Figure. Note that, if a writer is in the critical section and n readers are waiting and then one reader is queued on w.r.t, and n- 1 readers are queued on the mutex. Also observe that, when a writer executes signal (w.r.t), we may resume the execution of either the waiting readers or a single waiting writer then the selection is made by the scheduler. The readers-writers problem and its solutions have been generalized to provide locks on some systems. Acquiring a reader-writer lock

structure of writer process

Figure1.1:-the structure of a writer process

Requires specifying the mode of the lock either read or write access. When a process wishes only to read shared data if it is requests the reader-writer lock in read mode; a process wishing to modify the shared data must request the lock in write mode and Multiple processes are permitted to concurrently acquire a reader-writer lock in read mode, but only one process may acquire the lock for writing, as exclusive access is required for writers.  Reader-writer locks are most useful in the following situations: In applications where it is easy to identify which processes only read shared data and which processes only write shared data.  In applications that have more readers than writers. This is because reader writer locks generally require more overhead to establish than semaphores or mutual-exclusion locks. The increased concurrency of allowing multiple readers compensates for the overhead involved in setting up the reader writer lock.

The dining- philosophers problem

Consider five philosophers who spend their lives in the thinking and eating and philosophers share a circular table surrounded by their five chairs, each belonging


 structure of readers process

Fig: -1.2 the structure of readers process

situation of dining- philosophers

Fig:-1.3 the situation of dining- philosophers


To one philosophers. In the center of the table is a bowl of rice and the table is laid with a five single chopsticks (Figure 1.2). When a philosopher thinks, she does not interact with her colleagues or friends then  A philosopher gets hungry and tries to pick up the two chopsticks that are closest to her (the chopsticks that are between her and her left and right neighbors). A philosopher may pick up only one chopstick at a time. Obviously, she cam1ot pick up a chopstick that is already in the hand of a neighbor. When a dining philosopher has both her chopsticks at the same time, she eats without releasing her both side chopsticks. When she is finished eating then she puts down both of her chopsticks and starts thinking again.

The dining-philosophers problem is considered a classic synchronization problem neither because of its practical importance nor because computer scientists dislike philosophers but because it is an example of a large class of concurrency control problems. It is a simple representation of the need to a distribute or allocate several resources among several processes in a deadlock-free and starvation-free mam1er. One simple solution is to represent each chopstick with a semaphore. A philosopher tries to grab the chopstick by executing wait () operation on that semaphore; she releases her chopsticks by executing the signal operation on the appropriate semaphores. The shared data are semaphore chopstick where all the elements of chopstick are initialized to 1. The structure of philosopher is shown in Figure 1.4. Although this solution guarantees that no two neighbors are eating at the same time and it nevertheless must be rejected because it could create deadlock. Suppose that all five philosophers become hungry simultaneously and each grabs her left side chopstick and all the elements of chopstick will now be equal to zero and when each philosopher tries to grab her right chopstick, she will be delayed forever. Several possible remedies to the deadlock problem are listed next.  Allow at most four philosophers to be sitting simultaneously at the table.

structure of philosophers I

Fig:-1.4 the structure of philosophers I


Allow a philosopher to pick up her chopsticks only if both chopsticks are available (to do this, she must pick them up in a critical section).Use an asymmetric solution that is, an odd philosopher taken first her left side chopstick and then her right side chopstick, whereas an even philosopher taken her right side chopstick and then her left side chopstick

Sourabh Bhunje

Sourabh Bhunje, B.E. IT from Pune University. Currently Working at Techliebe. Professional Skills: Programming - Software & Mobile, Web & Graphic Design, Localization, Content Writing, Sub-Titling etc.

Leave a Reply