Synchronization problems in computers - Article 3

In this article, we will discuss a few synchronization problems in computers. In the next article,
I will introduce Mutex and Semaphore and explain how they can be helpful in solving
synchronization problems.

1. Dining philosophers problem

This is a classical synchronization problem formulated by Edsger Dijkstra.

Five silent philosophers sit at a round table with bowls of spaghetti. Forks are
placed between each pair of adjacent philosophers. (An alternative problem formulation uses rice and chopsticks instead of spaghetti and forks).

Each philosopher must alternately think and eat. However, a philosopher can only eat
spaghetti when he has both left and right forks. Each fork can be held by only one philosopher
and so a philosopher can use the fork only if it is not being used by another philosopher.
After he finishes eating, he needs to put down both forks so they become available to others.
A philosopher can take the fork on his right or the one on his left as they become available,
but cannot start eating before getting both of them.

Eating is not limited by the remaining amounts of spaghetti or stomach space; an infinite supply is assumed.

The problem is how to design a discipline of behavior (a concurrent algorithm) such that each philosopher will not starve; i.e., can forever continue to alternate between eating and thinking, assuming that any philosopher cannot know when others may want to eat or think.

Think about how to simulate and solve this in Computers.

2. A stack problem

There is a global stack of say 10 integers shared by 2 threads. Elements 1 to 10 (1,2,3,4,5,6,7,8,9 and 10) are pushed on to the stack.

Now, the problem is to synchronize the 2 threads in such a way that thread 1 pops 10, thread 2 pops 9, so on and so forth. Basically, we need to alternate between threads exactly once.

3. Rendezvous problem

In this problem, two threads need to proceed after uniting at a rendezvous.
Suppose T1 code is as below:

Statement T1.A

Statement T1.B

T2 code is as below:

Statement T2.A

Statement T2.B

Now, we need to ensure that T1 and T2 have both executed their first statements (i.e., T1.A and T2.A). Only then they can proceed.

4. Producer consumer problem

This is a general problem in computers where there are producers and consumers. Examples: In event driven UI systems, events like mouse click, object selection, window events will be produced by users and they will be handled by handlers.

Imagine network packets coming. Network packets are produced and they are consumed by upper layeres.

5. Readers writers problem

This is another classical problem. In this problem, say one thread is writing and modifying a data structure or a database and n threads are reading.

We have to ensure that when writer is writing, no other threads can enter. But, when reader is reading, other threads can also read. But, writer cannot enter. Basically, one class of threads mutually exclude other class of 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