The readers-writers problem is a classical one in computer science: we have a resource (e.g., a database) that can be accessed by readers, who do not modify the resource, and writers, who can modify the resource. When a writer is modifying the resource, no-one else (reader or writer) can access it at the same time: another writer could corrupt the resource, and another reader could read a partially modified (thus possibly inconsistent) value.
This problem has been extensively studied since the 60's, and is often categorized into three variants:
- Give readers priority: when there is at least one reader currently accessing the resource, allow new readers to access it as well. This can cause starvation if there are writers waiting to modify the resource and new readers arrive all the time, as the writers will never be granted access as long as there is at least one active reader.
- Give writers priority: here, readers may starve.
- Give neither priority: all readers and writers will be granted access to the resource in their order of arrival. If a writer arrives while readers are accessing the resource, it will wait until those readers free the resource, and then modify it. New readers arriving in the meantime will have to wait.
Unfortunately, only the solutions for the first two problems are easily found on the Internet. As of today, even the wikipedia page on the subject does not have any algorithm for what is called "the third readers-writers problem". However, this algorithm is very simple once you decompose the problem in smaller steps and properties.
The third readers-writers problem
We will build the solution using C code. We will use semaphores for mutual exclusion (mutex). Those semaphores, being used as locks, are all initialized in the released state (1 available place); those initializations will not appear in code snippets below but will be shown in comments.
First of all, we said earlier that we want fair-queuing between readers and writers in order to prevent starvation. To achieve that, we will use a semaphore named orderMutex that will materialize the order of arrival. This semaphore will be taken by any entity that requests access to the resource, and released as soon as this entity gains access to the resource:
semaphore orderMutex; // Initialized to 1
void reader()
{
P(orderMutex); // Remember our order of arrival
...
V(orderMutex); // Released when the reader can access the resource
...
}
void writer()
{
P(orderMutex); // Remember our order of arrival
...
V(orderMutex); // Released when the writer can access the resource
}
Now, we can write the writer code as it is the most straightforward of both. The writer wants an exclusive access to the resource. We will create a new semaphore named accessMutex that the writer will request before modifying the resource:
semaphore accessMutex; // Initialized to 1
semaphore orderMutex; // Initialized to 1
void reader()
{
P(orderMutex); // Remember our order of arrival
...
V(orderMutex); // Released when the reader can access the resource
...
}
void writer()
{
P(orderMutex); // Remember our order of arrival
P(accessMutex); // Request exclusive access to the resource
V(orderMutex); // Release order of arrival semaphore (we have been served)
WriteResource(); // Here the writer can modify the resource at will
V(accessMutex); // Release exclusive access to the resource
}
The reader code is a bit more complicated as multiple readers can simultaneously access the resource. We want the first reader to get access to the resource to lock it so that no writer can access it at the same time. Similarly, when a reader is done with the resource, it needs to release the lock on the resource if there are no more readers currently accessing it.
This is similar to a light switch in a dark room: the first person entering the room will turn the lights on, while the last person leaving the room will turn the lights off. However, it is much more simple if the room has only one door and only one person can enter or leave the room at the same time, to prevent someone from switching the lights off when someone enters at the same time using another door. This is why we will use a counter named readers representing the number of readers currently accessing the resource, as well as a semaphore named readersMutex to protect the counter against conflicting accesses.
1 semaphore accessMutex; // Initialized to 1
2 semaphore readersMutex; // Initialized to 1
3 semaphore orderMutex; // Initialized to 1
4
5 unsigned int readers = 0; // Number of readers accessing the resource
6
7 void reader()
8 {
9 P(orderMutex); // Remember our order of arrival
10
11 P(readersMutex); // We will manipulate the readers counter
12 if (readers == 0) // If there are currently no readers (we came first)...
13 P(accessMutex); // ...requests exclusive access to the resource for readers
14 readers++; // Note that there is now one more reader
15 V(orderMutex); // Release order of arrival semaphore (we have been served)
16 V(readersMutex); // We are done accessing the number of readers for now
17
18 ReadResource(); // Here the reader can read the resource at will
19
20 P(readersMutex); // We will manipulate the readers counter
21 readers--; // We are leaving, there is one less reader
22 if (readers == 0) // If there are no more readers currently reading...
23 V(accessMutex); // ...release exclusive access to the resource
24 V(readersMutex); // We are done accessing the number of readers for now
25 }
26
27 void writer()
28 {
29 P(orderMutex); // Remember our order of arrival
30 P(accessMutex); // Request exclusive access to the resource
31 V(orderMutex); // Release order of arrival semaphore (we have been served)
32
33 WriteResource(); // Here the writer can modify the resource at will
34
35 V(accessMutex); // Release exclusive access to the resource
36 }
Checking the solution for the required properties
We can look back the this solution and check if it looks like it fits our requirements. It can be formally proved correct using for example Petri nets.
orderMutexcannot be part of a deadlock since at the time it is requested no other semaphore is ever held by the calling process, so we can forget about it in our deadlock analysis (this property holds if every process only callsreader()orwriter()once, but it works in the general case).readersis always strictly greater than 0 if any reader is currently executing lines 15 to 20 (inclusive): the variable is unconditionally incremented at line 14 and unconditionally decremented at line 21 without any other modification, and no modification ever occurs without an exclusive lock granted byreadersMutexso thereadersintegrity is guaranteed.accessMutexis taken at line 13 just beforereadersgoes from 0 to 1. It is released at line 23 just afterreadersgoes back to 0. Detection of those raising or falling edges is guaranteed by the use of thereadersMutexlock. As seen above, it means that no reader will be executing lines 14 to 22 (inclusive) withoutaccessMutexbeing taken by a reader (possibly gone now), especially line 18 which represents resource access.accessMutexcan be requested whenreadersMutexis held (on line 13), andreadersMutexcan be requested whenaccessMutexis held (on line 20). However, the first situation (line 13) only happens whenreadersis equal to 0 (first reader to get access to the resource), which can never be the case if another reader is currently trying to execute line 20 as seen above, so those two potentially deadlocking reservations can never occur at the same time. Thus those two semaphores cannot interact and cause a deadlock.The resource is never accessed by a writer without
accessMutexbeing taken in an unconditional and exclusive way. Since we have seen above thataccessMutexis always collectively taken by readers before they access the resource, the resource is properly protected.Fair access is guaranteed through the
orderMutexwhich is taken upon arrival and released only when access to the resource has been granted.