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 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...

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 ...

Tokens and its types in 'C'

   Tokens are the smallest individual unit of a program or in simple words it is a main part of C program.Tokens are the building blocks of any program. The smallest individual and basic unit of a C programming is called c tokens.      *    Normally there are six types of tokens in C:- i> Keywords:-          Keywords are special words that are used to give a special meaning to the program and can't be used as variable and constant.They are basically a sequence of characters that have fixed to mean. For example:-                 auto     double      long     break                 float    short        char     if                while    continue   int       void etc. All...