Samuel Tardieu @ rfc1149.net

The third readers-writers problem

,

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:

  1. 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.
  2. Give writers priority: here, readers may starve.
  3. 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.

semaphore accessMutex;     // Initialized to 1
semaphore readersMutex;    // Initialized to 1
semaphore orderMutex;      // Initialized to 1

unsigned int readers = 0;  // Number of readers accessing the resource

void reader()
{
  P(orderMutex);           // Remember our order of arrival

  P(readersMutex);         // We will manipulate the readers counter
  if (readers == 0)        // If there are currently no readers (we came first)...
    P(accessMutex);        // ...requests exclusive access to the resource for readers
  readers++;               // Note that there is now one more reader
  V(orderMutex);           // Release order of arrival semaphore (we have been served)
  V(readersMutex);         // We are done accessing the number of readers for now

  ReadResource();          // Here the reader can read the resource at will

  P(readersMutex);         // We will manipulate the readers counter
  readers--;               // We are leaving, there is one less reader
  if (readers == 0)        // If there are no more readers currently reading...
    V(accessMutex);        // ...release exclusive access to the resource
  V(readersMutex);         // We are done accessing the number of readers for now
}

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
}

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.

  • orderMutex cannot 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 reader() or writer() once, but it works in the general case).

  • readers is 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 readersMutex so the readers integrity is guaranteed.

  • accessMutex is taken at line 13 just before readers goes from 0 to 1. It is released at line 23 just after readers goes back to 0. Detection of those raising or falling edges is guaranteed by the use of the readersMutex lock. As seen above, it means that no reader will be executing lines 14 to 22 (inclusive) without accessMutex being taken by a reader (possibly gone now), especially line 18 which represents resource access.

  • accessMutex can be requested when readersMutex is held (on line 13), and readersMutex can be requested when accessMutex is held (on line 20). However, the first situation (line 13) only happens when readers is 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 accessMutex being taken in an unconditional and exclusive way. Since we have seen above that accessMutex is always collectively taken by readers before they access the resource, the resource is properly protected.

  • Fair access is guaranteed through the orderMutex which is taken upon arrival and released only when access to the resource has been granted.

blog comments powered by Disqus