Skip to main content

Classical Problem Of Synchronization


There are many classical problem in synchronization method as examples of a large class of concurrency - control problems. these problems are used for testing nearly every newly proposed method or scheme of synchronization. Let us take some problems one by one :-


The Bounded-Buffer Problem :-
 The bounded-buffer problem was commonly used to illustrate the power of synchronization premitives.
   Bounded-buffer problrm is also known as producer consumer problem. This problem is genetalized in terms of the producer-consumer problem. The solution to this problem is, create two counting semaphore "full" and "empty" to keep track of the current number of full anbd empty buffers respectively. Producers produce a product and consumers consume the product, but use of one of the containers each time. 
  The code of producer and consumer are as follows :- 
 int count = 0;
 void producer (void)
 {
    int item p;
   
    while (true)
    {
       producer_item (itemp);
       while( count == n);
       Buffer [in] = itemp;
       in= (in +1)mod n;
       count = count +1;
    }
 }     

 void cousumer (void);
 {
    int item c;
   
    while (true)
    {
       while( count == 0);
      item c = Buffer (out); 
      out =  (out +1)mod n;
     count = count -1;
     process_item (item c);    
   }
}     


The Reader-Writer Problem :-
This is the major type of problem in process synchronization. Suppose that a database is to be shared among several concurrent processes. Some of these process may want to read the database only, whereas other may want to write, means update the database. We use two types of processes namely readers and writers. Obviously, if two readers access the shated data simultaneously, no problem occur. But if two writer or one writer , one reader simultaneously access the shared data then problem occurs. Preciousely in O/S this problem is called reader-writer problem. The Parameters are as follows :-
  • One  set of data is shared among a number of processes.
  • Once a writer is ready, it perform its write. Only one writer may write at a time.
  • If a process is  writing, no other process can read database at that instance of time.
  • If atleast one reader is reading, no other process can write.
  • Readers may not wriote and only able to read.
Let as see the code of reader and writer as follows :-

 int rc =0;
 semaphore mutex = 1;
 semaphore db = 1;
 void reader (void)
 {
  while (true)
  {
    down (mutex);
    rc = rc +1;
    if (rc == 1) then down (db);
    up (mutex)
DB
   down (mutex)
   rc = rc -1;
   if (rc == 0) then up (db);
   up (mutex)
   process_data
  }
}

  void writer(void)
   {
     while (true)
     {
      down (db);
DB
      up (db);
      }
   }


The Dining-philosphers problem :-
The dining -philosopher problem is considered as a classic synchronization problem because of concurrency-control problems. Consider five philosophers who spend their lives thinking and eating. The philosophers share a circular table. At the centre of table there is a bowl of rice, and the table is laid with 5 single chopsticks. As shown in figure :-

When a philosopher thinks, he/she does not interact with his/her collegues. When philos0pher gets hungry and tried to pick up the two chopsticks that are closest to him/her. A philosopher may pick up only one chopstick at a time. Obviously, he/she can not pick up a chopstick that is already in the hand of a neighbour collegue. When a philosopher has both chopsticks at a time, he/she eats without releasing the chopsticks. When earting completes he/she puts down both chopsticks and start thinking again. It is a simple representation of the need to allocate several resources among several porcesses in deadlock-free and starvation-free manner.
  
Here is the code for this problem :-

 void philosopher (void)
 {
    while (true)
    {
      thinking();
      take_chopstick (i);
      take_chopstick ((i +1)%N);
     
      EAT();
      put_choipstick(i);
      put_chopstick ((i +1)%N);
    }
 }

One simple solution of the problem is to represent each chopstick withqa semaphore. A philisophore tries to grab a chopstick by executing wait()/down() operation on that semaphore. He/she releases thgeir chopsticks by executing the signal()/up operation. Although this solution guarantees that no two neighbour are eating simultaneously.

Share, Follow and please comment if you find anything incorrect or to share more information about the topic discussed above.


Comments

Popular posts from this blog

Process & Its state And process control block :-

                ⇰  PROCESS :- A process can be thought of as a program in execution. Means when any program is executed it becomes process. A processwill need certain resources such as CPU time , memory, files and I/O devices to complete its task. These resources are allocated to the process either when it is created or at the time of execution.             A process is the unit of work in most systems. A system consistes of a collection of processes. All these processes may execute concurrently. Traditionally a process contained only a single thread. Most modern operating ststems now supports processes that have multiple threads.         The operating system is responsible for several important works of process management as - the creation and deletion of process, the schrduling of process, communication and deadlock handling of process. Process is broudly divided into two ...

Process Scheduling And Types of Process Schedular :-

        ⇰ PROCESS SCHEDULING Process Scheduling  is a task  of Operating System that schedules processes of different states like new, ready, waiting, terminated  and running.This scheduling helps in allocation of CPU time for each process, and Operating System allocates the CPU time for each procss. And the process scheduling plays important role to keep the CPU busy all the time.  ⏩   Followings are some objectives of Process Scheduling :-  i > To increase the amount of users within acceptable response times.  ii > To maintain the balance between response and utilization of system. iii > To decrease the enforce priorities and  give reference to the processes holding the key resources.      ⇰  PROCESS SCHEDULAR A scheduler carries out the pro cess scheduling work. Schedulers are often implemented so they keep all computer resources busy and  allows multiple users to shar...

Definition of Stack and its algorithm with working process(data structure)

                  Stack                           A Stack is  an ordered collection of items where the addition of items and the removal of existing items always takes place at the same end. This end is commonly referred to as the “top". * working method of stack :- i> Initially top=-1 ii> By increasing top pointer we can insert element    in the stack. iii> when top=size of stack-1  then stack is full. iv> By decreasing the top pointer we can remove   the   element from stack. v> when top=-1 then the stack is empty. figure shows run time stack * The fundamental operations which are possible on a stack are:-         1. push operation (insertion).    2. pop operation (deletion).    3. peep opetation(extract informat...