Home » Operating System

Classical Synchronization Problem in Operating System

In this tutorial, we will learn about the classical synchronization problem in Operating System with its solution. By Prerana Jain Last updated : May 07, 2023

Classical Synchronization Problem

In this section, we present a number of different philosopher synchronization problems that are important mainly because they are examples for a large class of concurrency- control problems. These problems are used for testing nearly every new proposed synchronization scheme.

Bounded buffer problem/ producer- consumer problem

Bounded buffer problem or producer-consumer problem is a classical synchronization problem where we have a buffer with n cells or n slots and there are 2 process producers and consumers can produce and consume one article at a time.

Write a solution using a semaphore to ensure overflow condition for producers underflow for consume and a critical section for the buffer.

Here we have pool of n buffers.

Mutex - Semaphore for mutual exclusion to access buffer pool, initialized to 1.

Empty - Semaphore to count empty buffer N.

Full - Semaphore to count fill buffer 0.

Wait (empty)
Wait (mutex)
Critical section
Signal (mutex)
Signal (full)

Wait (empty)
Wait (mutex)
Critical section
Signal (mutex)
Signal (empty)

We have used 3 semaphore e- empty cells, as well as underflow f- fixed cells as well as overflow mutex, is used for the critical section.

Example:

while(1)
{
    produce();
    wait(e)
    wait(mutex)
    append()
    signal(mutex)
    signal(f)
}

while(1)
{
    wait(p)
    wait(mutex)
    pick();
    signal(mutex)
    signal(e)
    consume();
}

1. Reader/writer Problem

• There is a shared piece of text and 2 types of process in accessing this text reader and writer.
• There is no clash between reader and reader therefore when a reader is inside critical section then other readers may get an only entry but when a write is inside critical section then neither the reader nor the writer gets an entry.
• Hence in the solution, we have used 3 resources a semaphore mutex for synchronization between writer and reader-writer.
• While read count (RC) is a simple integer variable which is given security by reading semaphore which works for synchronization between reader- reader.

Writer

while(1)
{  
	wait(mutex)
	write
	signal(mutex)
}

Reader

while(1)
{  
	wait(Read)
	Rc = Rc + 1;
	
	if(Rc = = 1)
	{  
		wait (mutex)
	} 
	
	wait(Read)
	Rc = Rc-1
	
	if(Rc ==0)
	{ 
		signal(mutex)
	}
	
	signal(Read)
}

2. Dining Philosopher Problem

In this problem, there is a circular table and number of philosopher a sitting on the table. There is a chop-stick placed between every philosopher. Philosopher prior only 2 processes either they think or eat (using 2 chop-stick).

Pi()
while(1)
{ 
	think
	P(s)
	Wait (chop-stick[i])
	Wait (chop-stick(i+1 % 5)
	V(s)
	Eat
	Signal( chop-stick[i]
	Signal (chop-stick(i+1 % 5)
	Think
}

Solution using semaphore for philosopher synchronization

Solution suffers from dead-lock and the following modification can be done:

1. Allow n-1 philosopher to sit on the table.
2. Allow n+1 chop-stick to be put on the table.
3. n-1 philosopher picks the left chop-stick first(the right and then the last philosopher pick the right first and left or vice-versa.
4. Division can be done between add an even number philosopher.
5. Take one more semaphore and consider 2 wait operation as a critical section.

Improved implementation

Here, there will be 2 improvements:

• The implementation will become effective as there is no wastage of CPU clock cycles.
• The bounded wait will also be ensured as it uses strictly follow First come first serve.

P(s)
{
    s = s-1
    if (s<0)
    {
        block();
        Add it to the queue();
    }
}

V(s)
{
    s = s+1
    if (s<1)
    {
        dequeue();
        resume();
    }
}