Classical Problems of Synchronization

In this blog, we will discuss the various classical problems of synchronization.

Semaphore can be used in other synchronization problems besides Mutual Exclusion.

Below are some of the classical problems depicting flaws of process synchronization in systems where cooperating processes are present.

We will discuss the following three problems:

1. Bounded Buffer (Producer-Consumer) Problem
2. Printer Spooler problem
3. Dining Philosophers Problem
4. The Readers Writers Problem

Bounded Buffer Problem

The bounded buffer problem, which is also called the producer-consumer problem, is one of the classic problems of synchronization. Let’s start by understanding the problem here, before moving on to the solution and program code.

What is the Problem Statement?

There is a buffer of n slots and each slot is capable of storing one unit of data. There are two processes running, namely, producer and consumer, which are operating on the buffer.

Bounded Buffer Problem

A producer tries to insert data into an empty slot of the buffer. A consumer tries to remove data from a filled slot in the buffer. As you might have guessed by now, those two processes won’t produce the expected output if they are being executed concurrently.

There needs to be a way to make the producer and consumer work in an independent manner.

Here’s a Solution

One solution to this problem is to use semaphores. The semaphores which will be used here are:

• m, a binary semaphore that is used to acquire and release the lock.
• empty, a counting semaphore whose initial value is the number of slots in the buffer, since, initially all slots are empty.
• full, a counting semaphore whose initial value is 0.

At any instant, the current value of empty represents the number of empty slots in the buffer and fully represents the number of occupied slots in the buffer.

The Producer Operation

The pseudocode of the producer function looks like this:

• Looking at the above code for a producer, we can see that a producer first waits until there is at least one empty slot.
• Then it decrements the empty semaphore because there will now be one less empty slot since the producer is going to insert data in one of those slots.
• Then, it acquires a lock on the buffer, so that the consumer cannot access the buffer until the producer completes its operation.
• After performing the insert operation, the lock is released and the value of full is incremented because the producer has just filled a slot in the buffer.

The Consumer Operation

The pseudocode for the consumer function looks like this:

• The consumer waits until there is at least one full slot in the buffer.
• Then it decrements the full semaphore because the number of occupied slots will be decreased by one after the consumer completes its operation.
• After that, the consumer acquires a lock on the buffer.
• Following that, the consumer completes the removal operation so that the data from one of the full slots are removed.
• Then, the consumer releases the lock.
• Finally, the empty semaphore is incremented by 1, because the consumer has just removed data from an occupied slot, thus making it empty.

Printer Spooler Problem

• As we know the printer is a peripheral device, so it is slower in comparison to CPU and memory.
• So, if multiple users send some file to the printer to print then the spooler comes into play.
• The spooler is a program in a printer that stores all the files coming to print and when the printer is free it gives it to the printer in a sequential manner.

This four-line code is executed by each process in order to store its file in the spooler directory to print.

in: Shared variable m: Memory location Ri: Register F-N: File name SD: Spooler directory

1. Line 1: Inline one we are loading free memory location m[in], in register Ri
2. Line 2: Inline two we are storing file name (F-N) in the spooler directory (SD) at position Ri, which is for instance 0
3. Line 3: In line three we are incrementing the count of Ri from 0 to 1, so the next file can be stored in at index 1
4. Line 4: In line four the new file will be stored at incremented memory location m[in]

The problem Statment

Say there are two processes P1 and P2 with file names F1.txt and F2.txt that arrive at a concurrent time, let’s say that the first three instructions of process P1 with file name F1 get executed, and then preemption occurs. Due to this m[in] does not gets incremented and still points to the location of f4.txt in the spooler directory.

now the next process P2 starts with filename F5 and the first instructions load the m[in] (which points to the f1.txt) to the register and then writes the file f2.txt on it.

Due to this F1 is overwritten by F2 and data is lost. After P2 is completed, the last instruction of P1 gets executed (store m[in], Ri ) which then points to the next location in the spooler directory.

This leads to loss of data and needs to be solved using process synchronization.

Solution

We can initialize a semaphore with value 1 for the first time the spooler directory gets accessed. Then in the entry section of the code, we check if the semaphore is 1 or 0. The process gets executed if and only if the semaphore is 1.And then we assign the semaphore with value 0 while the process is being executed and then again assign it to 1 in the end block after the process gets completely executed. This way if any process gets preempted at any instruction and a new process comes, the semaphore is going to remain 0 since P1 has not been completed which forces the other process to wait till the P1 gets executed and the semaphore becomes 1 again.

Pseudocode

Dining Philosophers Problem

The dining philosophers problem is another classic synchronization problem that is used to evaluate situations where there is a need of allocating multiple resources to multiple processes.

What is the Problem Statement?

Consider there are five philosophers sitting around a circular dining table. The dining table has five chopsticks and a bowl of rice in the middle as shown in the below figure.

Dining Philosophers Problem

At any instant, a philosopher is either eating or thinking. When a philosopher wants to eat, he uses two chopsticks — one from their left and one from their right. When a philosopher wants to think, he keeps down both chopsticks at their original place.

Here’s the Solution

From the problem statement, it is clear that a philosopher can think for an indefinite amount of time. But when a philosopher starts eating, he has to stop at some point in time. The philosopher is in an endless cycle of thinking and eating.

An array of five semaphores, stick[5]for each of the five chopsticks.

The code for each philosopher looks like this:

When a philosopher wants to eat the rice, he will wait for the chopstick at his left and picks up that chopstick. Then he waits for the right chopstick to be available, and then picks it too. After eating, he puts both the chopsticks down.

But if all five philosophers are hungry simultaneously, and each of them picks up one chopstick, then a deadlock situation occurs because they will be waiting for another chopstick forever. The possible solutions for this are:

• There should be at most four philosophers on the table.
• An even philosopher should pick the right chopstick and then the left chopstick while an odd philosopher should pick the left chopstick and then the right chopstick.
• A philosopher should only be allowed to pick their chopstick if both are available at the same time.

Readers Writer Problem

Readers writer problem is another example of a classic synchronization problem. There are many variants of this problem, one of which is examined below.

The Problem Statement

There is a shared resource that should be accessed by multiple processes. There are two types of processes in this context. They are reader and writer. Any number of reader can read from the shared resource simultaneously, but only one writer can write to the shared resource. When a writer is writing data to the resource, no other process can access the resource. A writer cannot write to the resource if there are non-zero readers accessing the resource at that time.

The Solution

From the above problem statement, it is evident that readers have higher priority than writer. If a writer wants to write to the resource, it must wait until there are no readers currently accessing that resource.

Here, we use one mutex m and a semaphore w. An integer variable read_count is used to maintain the number of readers currently accessing the resource. The variable read_count is initialized to 0. A value of 1 is given initially to m and w.

Instead of having the process to acquire a lock on the shared resource, we use the mutex m to make the process to acquire and release lock whenever it is updating the read_count variable.

The code for the writer process looks like this:

And, the code for the reader process looks like this:

Here is the Code uncoded(explained)

• As seen above in the code for the writer, the writer just waits on the w semaphore until it gets a chance to write to the resource.
• After performing the write operation, it increments w so that the next writer can access the resource.
• On the other hand, in the code for the reader, the lock is acquired whenever the read_count is updated by a process.
• When a reader wants to access the resource, first it increments the read_count value, then accesses the resource, and then decrements the read_count value.
• The semaphore w is used by the first reader which enters the critical section and the last reader who exits the critical section.
• The reason for this is, when the first readers enter the critical section, the writer is blocked from the resource. Only new readers can access the resource now.
• Similarly, when the last reader exits the critical section, it signals the writer using the w semaphore because there are zero readers now and a writer can have the chance to access the resource.

Possibilities-

Thank you for staying with us so far. Hope you liked the article. Like and Comment down your feedback!!

Authors:

• Aaditi Badgujar
• Sahil Adhav
• Anmol Warikoo
• Antima Modak
• Aryan Aher