Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, the first and second readers-writers problems are examples of a common computing problem in concurrency
Concurrency (computer science)
In computer science, concurrency is a property of systems in which several computations are executing simultaneously, and potentially interacting with each other...
. The two problems deal with situations in which many thread
Thread (computer science)
In computer science, a thread of execution is the smallest unit of processing that can be scheduled by an operating system. The implementation of threads and processes differs from one operating system to another, but in most cases, a thread is contained inside a process...
In computing, shared memory is memory that may be simultaneously accessed by multiple programs with an intent to provide communication among them or avoid redundant copies. Depending on context, programs may run on a single processor or on multiple separate processors...
at one time, some reading and some writing, with the natural constraint that no process may access the share for reading or writing while another process is in the act of writing to it. (In particular, it is allowed for two or more readers to access the share at the same time.) A readers-writer lock
Readers-writer lock
In computer science, a readers-writer or shared-exclusive lock In computer science, a readers-writer or shared-exclusive lock In computer science, a readers-writer or shared-exclusive lock (also known as the multiple readers / single-writer lock or the multi-reader lock,...
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
that solves one or more of the readers-writers problems.
The first readers-writers problem
Suppose we have a shared memory area with the constraints detailed above. It is possible to protect the shared data behind a mutual exclusion mutex, in which case no two threads can access the data at the same time. However, this solution is suboptimal, because it is possible that a reader R1 might have the lock, and then another reader R2 request access. It would be foolish for R2 to wait until R1 was done before starting its own read operation; instead, R2 should start right away. This is the motivation for the first readers-writers problem, in which the constraint is added that no reader shall be kept waiting if the share is currently opened for reading. This is also called readers-preference.
The second readers-writers problem
Suppose we have a shared memory area protected by a mutex, as above. This solution is suboptimal, because it is possible that a reader R1 might have the lock, a writer W be waiting for the lock, and then a reader R2 request access. It would be foolish for R2 to jump in immediately, ahead of W; if that happened often enough, W would starve
Resource starvation
In computer science, starvation is a multitasking-related problem, where a process is perpetually denied necessary resources. Without those resources, the program can never finish its task....
. Instead, W should start as soon as possible. This is the motivation for the second readers-writers problem, in which the constraint is added that no writer, once added to the queue, shall be kept waiting longer than absolutely necessary. This is also called writers-preference.
A solution to the writers-preference scenario is presented below:
int readcount, writecount; (initial value = 0)
semaphore mutex 1, mutex 2, mutex 3, w, r ; (initial value = 1)
P(mutex 1);
readcount := readcount - 1;
if readcount = 0 then V(w);
V(mutex 1);
WRITER
P(mutex 2);
writecount := writecount + 1;
if writecount = 1 then P(r);
V(mutex 2);
P(w);
writing is performed
V(w);
P(mutex 2);
writecount := writecount - 1;
if writecount = 0 then V(r);
V(mutex 2);
The third readers-writers problem
In fact, the solutions implied by both problem statements result in starvation — the first readers-writers problem may starve writers in the queue, and the second readers-writers problem may starve readers. Therefore, the third readers-writers problem is sometimes proposed, which adds the constraint that no thread shall be allowed to starve; that is, the operation of obtaining a lock on the shared data will always terminate in a bounded amount of time.
A solution with fairness for both readers and writers might be as follows:
semaphores: no_writers, no_readers, counter_mutex ( initial value is 1 )
shared variables: nreaders ( initial value is 0 )
local variables: prev, current
READER:
P( no_writers );
P( counter_mutex );
prev := nreaders;
nreaders := nreaders + 1;
V( counter_mutex );
if prev = 0 then P( no_readers );
V( no_writers );
... read ...
P( counter_mutex );
nreaders := nreaders - 1;
current := nreaders;
V( counter_mutex );
if current = 0 then V( no_readers );
Note that sections protected by counter_mutex could be replaced by a suitable fetch-and-add
Fetch-and-add
In computer science, the fetch-and-add CPU instruction is a special instruction that atomically modifies the contents of a memory location. It is used to implement mutual exclusion and concurrent algorithms in multiprocessor systems, a generalization of semaphores.In uniprocessor systems, it is...
atomic instruction, saving two potential context switches in reader's code.
Note also that this solution can only satisfy the condition that "no thread shall be allowed to starve" if and only if semaphores preserve first-in first-out ordering when blocking and releasing threads. Otherwise, a blocked writer, for example, may remain blocked indefinitely with a cycle of other writers decrementing the semaphore before it can.
In computer science, the dining philosophers problem is an example problem often used in concurrent algorithm design to illustrate synchronization issues and techniques for resolving them....
The cigarette smokers problem is a concurrency problem in computer science, originally described in 1971 by S. S. Patil.-Problem description:Assume a cigarette requires three ingredients to smoke:#Tobacco#Paper#A match...
In computer science, the sleeping barber problem is a classic inter-process communication and synchronization problem between multiple operating system processes...
