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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 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 calls
writer()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 by
readersintegrity is guaranteed.
accessMutexis taken at line 13 just before
readersgoes from 0 to 1. It is released at line 23 just after
readersgoes back to 0. Detection of those raising or falling edges is guaranteed by the use of the
readersMutexlock. As seen above, it means that no reader will be executing lines 14 to 22 (inclusive) without
accessMutexbeing taken by a reader (possibly gone now), especially line 18 which represents resource access.
accessMutexcan be requested when
readersMutexis held (on line 13), and
readersMutexcan be requested when
accessMutexis held (on line 20). However, the first situation (line 13) only happens when
readersis 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 that
accessMutexis 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.