Synchronization primitives: Mutex and Semaphore (Readers & Writers problem) - Article 8

Hi Friends,

In this article, we shall solve the Readers & Writers problem.

Readers & Writers problem:

There may be m writers & n readers related to a shared data structure or a record in the database (some shared data). Only one writer thread can be updating the data, but there can be many readers accessing the data.

The constraints are:

1. Any number of readers can be accessing the data in critical section.
2. Only one writer thread should be allowed to update the data in critical section.

Solution:

int readers = 0; // Shared variable to keep track of number of readers,
                 // yes this also needs to be protected
Semaphore readersProtect = 1;
Semaphore roomEmpty = 1;

Writers thread code:

roomEmpty.wait();
    // Update shared data, critical section for writers
roomEmpty.signal();

Readers thread code:

readersProtect.wait();
    readers = readers + 1;
    if(readers == 1)
        roomEmpty.wait(); // First reader locks and bars writers
readersProtect.signal();

 // Read shared data, critical section for readers

 readersProtect.wait();
    readers = readers - 1;
    if(readers == 0)
        roomEmpty.signal();
        // Last reader unlocks and grants access to writers
readersProtect.signal();

The solution is very easy than it appears. roomEmpty is used to control entry for readers & writers. readersProtect is used to control access for readers shared variable which is accessed only by readers. Hence, it appears in readers thread code.

The writers code is simple. It waits on roomEmpty and if its free, the thread enters and updates the code, else it is queued up.

In readers code, we are increasing readers if any reader thread enters and decrease readers if it leaves. The first thread locks roomEmpty if it's not locked. Subsequent reader threads can just enter and read the data. Finally, the last reader unlocks or signals roomEmpty (that room is empty).

Go through the code slowly and it's easy to understand.

Till here, we have solved many problems using Mutex and Semaphore, but only pseudo code has been presented. In the subsequent articles, I am going to introduce real code related to Pthreads or POSIX threads.

Comments

Post a Comment

Popular posts from this blog

Synchronization primitives: Mutex and Semaphore (Serialization & Mutex problems using Semaphore) - Article 6

Hi Friends, In the previous articles, we have gained knowledge about Mutex and Semaphore. In this article, we shall see how a Semaphore can be used to solve serialization problem and Mutual Exclusion (Mutex) problem. Serialization problem: Thread 1: Event A; // Could be any code Thread 2: Event B; // Could be any code The problem is, we have to ensure that Event B or a particular code or instructions should always be executed after Event A or some other particular code. Basically, we are serializing the instructions irrespective of how the threads are scheduled to run. Solution: There are no resources here, we need to just signal, initialize Semaphore to 0. Semaphore SignalThread2 = 0; Thread 1: Event A; SignalThread2.signal(); Thread 2: SignalThread2.wait(); Event B; The code for Thread 1 and Thread 2 is as above. Irrespective of which thread is scheduled, Event A always occurs before Event B. How? Let's say Thread 2 is scheduled first, it executes...
Read more

Synchronization: Discussion about Mutex and Semaphore - Article 1

This is the first article in the series about Mutex and Semaphore. In my blog, I shall follow below sequence: 1. First, I will try to explain the concept. 2. Next, we shall see what problems the concept may solve or what problems may occur if the concept is not applied. 3. Finally, we shall see how the concept will solve the problem. In this article, I will try to cover what Synchronization in Computers is all about and different problems that can occur if Synchronization is not used. First we will see the real world examples and see what Synchronization is all about. Dictionary meaning is as below: 1. To cause to occur or operate with exact coincidence in time or rate. 2. Synchronization is the coordination of events to operate a system in unison. Let's try to understand in depth. Consider below examples: 1. Imagine soldiers doing march past in a parade. - They operate at the same time and everybody march in order. - They appear synchronized. How do they do it? - Every...
Read more

Copy constructor in C++ (Part 2)

Now, the important question comes is regarding the signature of copy constructor. That is, why copy constructor takes a reference as parameter. Let's copy by value from previous example. CopyDemo(const CopyDemo obj) {     ptr = new int;     *ptr = *obj.ptr; } Now from main(), CopyDemo o2 = o1; Let me explain in detail. We have called copy constructor to copy o1 to o2. But, since we are passing by value, first o1 has to be copied to obj. So internally, statement will be, const CopyDemo obj = o1; Now, what happens is again copy constructor is invoked. Already, we can sense some problem, copy constructor is called again. Internally, the statement is repeated again. const CopyDemo obj = o1; This goes into a recursive loop and following statements get repeated till stack overflow happens and ultimately program crashes. const CopyDemo obj = o1; const CopyDemo obj = o1; const CopyDemo obj = o1; . . .
Read more