Home » Operating Systems

Classical Synchronization problem in Operating System

In this article, we will learn about the classical synchronization problem and try to understand the solutions for this process in operating system.
Submitted by Prerana Jain, on August 22, 2018

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.

Producer Consumer
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:

P C
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();
    }
}





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.
Learn PCB Designing: PCB DESIGNING TUTORIAL







Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.