8.4. Readers-Writers Problem¶

8.4.1. A Solution Using Lightswitches¶

One common solution for the readers-writers problem aligns with the asymmetric lightswitch described previously. As the readers allow concurrent access, the reader thread would use the enter() and leave() routines to access the shared resource. The writers, however, require mutual exclusion, both with other writers and with all of the readers. Consequently, the writers do not need to employ the lightswitch, simply accessing the semaphore directly. Code Listing 8.19 shows the framework for this solution.

 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

/* Code Listing 8.19:
   Asymmetric lightswitch solution to readers-writers
 */

void *
reader (void * _args)
{
  /* Cast the args struct as a lightswitch */
  ls_t *lightswitch = (ls_t  *) _args;
  enter (lightswitch);
  /* Read the shared data */
  leave (lightswitch);
  /* Do other work and exit thread */
}

void *
writer (void * _args)
{
  /* Cast the args struct as a lightswitch */
  ls_t *lightswitch = (ls_t  *) _args;
  sem_wait (lightswitch->semaphore);
  /* Write to the shared data structure */
  sem_post (lightswitch->semaphore);
  /* Do other work and exit thread */
}

8.4.2. Fairness to Writers¶

Figure 8.4.1: An unfair timing for the writer

The solution to the readers-writers problem as shown in Code Listing 8.19 has an important flaw to highlight. This approach fails to achieve fairness, particularly in relation to the writers. Specifically, consider the timing of events shown in Figure 8.4.1. In this scenario, Reader A arrives first and decrements the semaphore. When the writer arrives and tries to do the same, it gets blocked. The writer must then wait until all readers have left. Once Reader B arrives, the two readers take turns leaving and re-entering. Since at least one reader is always in the system, the writer is blocked indefinitely, a situation known as starvation.

The writer’s starvation in this scenario can be fixed by placing a turnstile before the readers can enter as shown in Code Listing 8.20. As long as there is no writer attempting to enter the critical section, the readers can each pass through the turnstile and invoke enter() on the lightswitch. However, once a writer arrives, it will call sem_wait() on the turnstile semaphore, blocking new readers from passing through the turnstile. The writer will then call sem_wait() on the lightswitch semaphore and block. When the last of the readers that are already in the critical section call leave(), that thread will sem_post() to the lightswitch semaphore, allowing the writer to enter. The writer can then sem_post() to the turnstile, allowing readers to pass through again. The first reader through calls enter() on the lightswitch and gets blocked until the writer leaves.

 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

/* Code Listing 8.20:
   A starvation-free readers-writers solution
 */

struct args {
  ls_t *lightswitch;
  sem_t *turnstile;
};

void *
reader (void * _args)
{
  /* Cast the args as struct with lightswitch and turnstile */
  struct args *args = (struct args *) _args;
  sem_wait (args->turnstile);
  sem_post (args->turnstile);
  enter (args->lightswitch);
  /* Read the shared data */
  leave (args->lightswitch);
  /* Do other work and exit thread */
}

void *
writer (void * _args)
{
  /* Cast the args as struct with lightswitch and turnstile */
  struct args *args = (struct args *) _args;
  sem_wait (args->turnstile);
  sem_wait (lightswitch->semaphore);
  sem_post (args->turnstile);
  /* Write to the shared data structure */
  sem_post (lightswitch->semaphore);
  /* Do other work and exit thread */
}

Depending on the particular context, it may be acceptable or desirable to use the solution that potentially allows writer starvation. For instance, if read accesses to the critical section are extremely fast and concurrent reads are rare, starvation would not occur; the turnstile would then impose unnecessary system calls and potential context switches that may accumulate. However, this cost may be acceptable to mitigate potential delays to the writers.

8.4.3. Search-Insert-Delete Problem¶

The search-insert-delete problem is a variant on the readers-writers problem. In this variant, multiple threads can search through a data structure concurrently; the searchers are essentially identical to the readers from before. However, the writers are broken into two distinct types of threads: inserters are adding new data while deleters are removing elements. As with the original writers, deletions must be mutually exclusive with all other accesses to the shared data structure. However, insertions have a more relaxed requirement: they must be mutually exclusive with themselves and with deletions, but concurrent searches are still allowed. That is, the inserters and searchers cannot lock each other out, but only one inserter is allowed access at a time; deleters, on the other hand, require mutual exclusion.

This problem can be solved with slight modifications of the original solution for the readers-writers. The searcher thread is identical to the reader, as shown in Code Listing 8.21.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

/* Code Listing 8.21:
   Searchers are identical to readers
 */

void * 
searcher (void * _args)
{
  /* Cast the args struct as a lightswitch */
  ls_t *search_switch = (struct args *) _args;
  enter (search_switch);
  /* critical section */
  leave (search_switch);
  /* Do other work and exit thread */
}

Inserters are also very similar to readers. The main difference is that inserters also require mutual exclusion among themselves, requiring a lock as shown in Code Listing 8.22.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

/* Code Listing 8.22:
   Inserters also require a lock for mutual exclusion to the data structure
 */

struct ins_args {
  ls_t *insert_switch;
  pthread_mutex_t *insert_lock;
};

void *
inserter (void * _args)
{
  /* Cast the args struct as a lightswitch */
  struct ins_args *args = (struct ins_args *) _args;
  enter (args->insert_switch);
  pthread_mutex_lock (args->insert_lock);
  /* critical section */
  pthread_mutex_lock (args->insert_lock);
  leave (args->insert_switch);
  /* Do other work and exit thread */
}

To complete the solution, the deleter threads behave identically to the writers. The only difference is that the deleter must rely on both lightswitches for the other two types of threads as shown in Code Listing 8.23. If the deleter successfully passes the semaphore for the search_switch, then there are no searchers in the critical section and new searchers will be blocked by the lightswitch. Once the last inserter leaves the critical section, the deleter would be able to pass the insert_switch semaphore and enter the critical section. Additional inserters would also be locked out at this point. Once the deleter exits the critical section, inserters and searchers would be allowed back in.

/* Code Listing 8.23:
   Deleters must work with lightswitches for both searchers and inserters
 */

void *
deleter ()
{
  sem_wait (search_switch->semaphore);
  sem_wait (insert_switch->semaphore);
  /* critical section */
  sem_post (insert_switch->semaphore);
  sem_post (search_switch->semaphore);
}

This solution, which is a variant on the original readers-writers solution, has the same weakness previously discussed. The deleter threads can potentially face starvation, as long as there is at least one searcher or inserter in their critical sections. Interestingly, though, the searcher threads can also face starvation. Specifically, consider the case where all the searchers leave the critical section and a deleter has arrived. As long as there are inserters in the critical section, the deleter cannot enter. However, the deleter has already successfully locked out future searchers. Consequently, the future searchers would be effectively locked out by the inserters. Adapting the turnstile approach used for readers-writers would successfully prevent starvation in this case, too.