Operating System – The most detailed explanation of the classic synchronization problem (Series 1 – Consumer Producer Problem)

Directory:

1. Producer and consumer issues

(1) Single producer, consumer

(2) Multiple producers and consumers

(3) Practice questions

Producer and consumer issues are often the focus of exams, so mastering this issue is critical. This article will focus on typical producer and consumer problems from simple to difficult, from easy to deep. Finally, we provide several postgraduate entrance examination real questions to practice in order to fully master this type of questions.

(1) Single producer, consumer

Problem description:

There is a set of producer processes and a set of consumer processes. The producer process produces one product and puts it into the buffer each time; the consumer process takes out one product from the bounded buffer and uses it each time. The producer and consumer share an initially empty buffer of size n.

Problem analysis:

This problem requires two processes, namely the producer and consumer processes, and a mutually exclusive semaphore mutex (buffer), whose mute=1 means only A process enters the buffer; Two resource semaphores: Before production starts, empty=n, full=0, that is, a total of n products can be stored, but currently there are only 0.

pseudocode:

semaphore mutex=1,empty=n,ful1=0; //Initialize the semaphore
//Producer process
        void producer(){
              do {
                 Producers produce products;
                 P(empty) //Determine whether the buffer is empty
                 P(mutex); //Determine whether the buffer can be entered, if empty, enter
                  Place product in designated area;
                 V(mutex); //Exit the critical section and allow other processes to enter
                 V(full); //The number of non-empty buffers in the buffer pool is increased by 1, and the waiting consumer process is awakened at the same time
                  }while(true);
                        }
//Consumer process
           void consumer(){
              do{
                P(full); //Determine whether the buffer is not empty (whether there is a product)
                P(mutex); //Determine whether the buffer can be entered (if it is not empty, enter)
                 take away product;
                V(mutex); //Exit the critical section and allow other processes to enter
                V(empty); //The number of empty buffers in the buffer pool is increased by 1 to wake up the waiting producer process
                         }
                  Use of the product;
                           }

Through the above pseudocode, it can be found that the P (mutex) and V (mutex) operations used to achieve mutual exclusion in each process must appear in pairs and in the same process; note: each program The order of multiple P and V operations in the process cannot be reversed. For example, in the producer process, you should first check whether the resource semaphore is empty and perform the P operation –P (empty); then perform the P operation into the buffer –P (mutex), otherwise a deadlock may occur due to mutual exclusion, that is, entering the buffer pool but there is no free buffer (empty\\
eq0), the producer process will be blocked, and other processes cannot enter the critical section, resulting in a process deadlock.

(2) Multiple producers-consumer issues
Problem description
There is a plate on the table, and only one piece of fruit can be put into it at a time. The father only puts apples on the plate, and the mother only puts oranges on the plate. The son is waiting to eat the oranges on the plate, and the daughter is waiting to eat the apples on the plate. Only when the plate is empty, parents can put a piece of fruit on the plate. Only when there is the fruit they need, the son or daughter can take out the fruit from the plate.
Problem Analysis

The plate is a buffer and only one process is allowed to enter, so a mutex is needed. When the plate is empty, the father can enter the buffer zone and put apples on the plate, or the mother can enter the buffer zone and put oranges on it; if there is something in the plate, and the son finds that it is not empty and the plate is filled with oranges, he will enter the buffer zone. The district takes the orange and eats it. If it is an apple, the daughter picks it up and eats it. There are four processes in total. At this time, three resource semaphores apple, orange and plate are needed to indicate whether there is something on the plate, what it is if there is something, and then determine whether The buffer can be accessed.

Pseudocode:

//Define semaphore
semaphore mutex = 1; //Achieve mutually exclusive access to the plate (buffer)
semaphore apple = 0; //How many apples are there on the plate?
semaphore orange = 0; //How many oranges are there on the plate?
semaphore plate = 1; //How many more fruits can be placed on the plate?
  //Process 1: Father
           dad(){
                while(1){
                     Prepare an apple;
                    P(plate); //Check whether fruit can be placed on the plate
                    P(mutex); //Enter the critical section
                       Place apples on plate;
                    V(mutex); //Exit the critical section and wake up the daughter to get the apple
                    V(apple); //number of apples + 1
                        }
                  }
  //Process 2: Mother
            mom(){
                while(1){
                     Prepare an orange;
                  P(plate); //Check whether fruit can be placed on the plate
                  P(mutex); //Enter the critical section
                     Place oranges on plate;
                  V(mutex); //Exit the critical section and wake up the son to get oranges
                  V(orange); //Number of oranges + 1
                          }
                 }
 //Process 3: Daughter
           daughter(){
               while(1){
  
                  P(apple); //Determine whether there is an apple to take
                  P(mutex); //Enter critical section, mutually exclusive access
                   Remove apples from plate;
                   V(mutex); //Exit the critical section
                   V(plate); //The number of fruits on the plate-1
                     eat apples;
                         }
                       }
  //Process 4: Son

              son(){
                  while(1){
  
                    P(orange); //Determine whether there are oranges available
                    P(mutex); //Enter critical section, mutually exclusive access
                       Remove oranges from plate;
                    V(mutex); //Exit the critical section
                    V(plate); //The number of fruits on the plate-1
                       eat oranges;
                           }
                       }

(3) Practice with real questions

Problem description

Two products, A and B, can be stored in a warehouse. The requirements are:
①Only one product can be deposited at a time.
②The quantity of product A-the quantity of product B Among them, M and N are positive integers. Use P operation and V operation to describe the warehousing process of product A and product B.

Problem Analysis

Use the semaphore mutex to control the mutual exclusive access of two processes to critical resources (warehouses), and use the synchronization semaphores Sa and Sb (respectively representing the difference between the quantities that can be accommodated between products A and B, and the quantities that can be accommodated between products B and A. Poor) satisfies condition 2 and condition 3.

For ②, let the quantity of product B = 0, and the quantity of product is a positive integer, then the quantity of product A = M-1; similarly, let the quantity of product A = 0, then the quantity of product B = N-1.

There are two processes in total, Sa stores the process (process_A) and Sb stores the process (process_B); Three semaphoresSa, Sb and mutex .

The code is as follows:

//Define semaphore
Semaphore Sa=M-1,Sb=N-1;
Semaphore mutex=l; //Access the mutually exclusive semaphore of the warehouse
//process one
     process_A(){
            while(l){
                  P(Sa); //See if Sa can still be deposited
                  P(mutex); //The number of Sa is less than M-1, then enter the mutually exclusive buffer
                    Product A is put into storage;
                  V(mutex); //Exit the buffer
                 V(Sb); //Wake up process b
                    }
                }
    
//process two
      process_B(){
            while(1){
                 P(Sb); //See if Sb can still be deposited
                 P(mutex); //The number of Sb is less than N-1, then enter the mutually exclusive buffer
                   Product B is put into storage;
                 V(mutex); //Exit the buffer
                 V(Sa); //Wake up process a
                      }
                 }

(4) Practice with real questions

Problem description

The baker has a lot of bread, which is sold by n salespeople. Each customer takes a number after entering the store and waits for the number to be called.
When a salesperson becomes available, the next number is called. Try to design an algorithm that synchronizes salespeople and customers.

Problem Analysis

There are two processes in total, the customer’s number-taking process (Consumer) and the salesperson’s number-calling process (Seller). Four semaphores, i, j, mutex_i, mutex_j;Why choose two mutually exclusive semaphores instead of one? It’s because the customer takes the number and the salesperson calls The number requires two values i and j. The increase of the two values cannot be in the same buffer. They are independent of each other and do not affect each other. Otherwise, the corresponding value cannot be increased correctly. I understand it this way: taking a number and calling a number are two different procedures. For example, taking a number uses a machine to take a number, while calling a number requires a waiter to call the number through another machine or manually, using different machines or processes. Therefore, different mutually exclusive semaphores need to be distinguished.

The code is as follows:

//Define semaphore
int i=0,j=0; //i represents the customer's number value, j represents the seller's number value, both are initialized to 0
semaphore mutex_i=1,mutex_j=1;
//customer process
      Consumer(){
             First the customer enters the bakery;
             P(mutex_i); //Enter the critical resource area for number retrieval, mutually exclusive access to i
             Take the number i;
             i + + ; //Increase number by 1
            V(mutex_i); //After taking the number, leave the number retrieval resource area
           Wait for the number to be called and buy bread;
                }
//salesperson process
      Seller(){
           (while(1){
           P(mutex_j); //The seller goes in and hand over the resource area, mutually exclusive access
            if(j<i)
               {
                call j;
               j + + ; //After the number is called, the number of j is increased by 1
           V(mutex_j); //Leave the number calling resource area
           selling bread;
                }
           else{
               V(mutex_j); //There are no customers at the moment, leave the calling area
              have a break;
                        }
               }
               

(5) Practice questions

Problem description

There are multiple producer processes and multiple consumer processes in the system, sharing a ring buffer (initially empty) that can store 100 products. When the buffer is not full, the producer process can put a product it produces, otherwise wait; when the buffer is not empty, the consumer process can take a product from the buffer, otherwise wait. A consumer process is required to take out 10 products from the buffer before other consumer processes can take the products. Please use semaphore P, V (wait(), signal()) operations to achieve mutual exclusion and synchronization between processes. It is required to write out the complete process and explain the meaning and initial value of the semaphore used.

Problem Analysis

Two processes, producer (Producer) and consumer (Costumer); Two resource semaphores empty=100, representing a total of 100 product vacancies, full=0 , Indicates whether there are products in the buffer, if so, consumption can be taken away; Two mutually exclusive semaphores mutex_1=1 (indicates that only one process can access the buffer area), mutex_2=1 (indicates that consumers can obtain 10 products continuously when entering the buffer area, and there must be no interference from other processes during the continuous acquisition process),

The code is as follows:

//Define semaphore
   Semapher mutex=1, mutex_2=1;
   Semapher empty=100,full=0;
//Producer process:
Producer()
{
  While(1)
  {
     P(empty);//Determine whether the buffer is empty, if so, produce the product
     P(mutex_1);//Enter critical area production
     product;
     V(mutex_1);//Leave the critical section
     V(full);//Non-empty quantity + 1
  }
}
//Consumer process
Costumer()
{
  While(1)
  {
     P(mutex_2);//Prevent other consumers from entering
     for(i=0,i<10,i + + )
    {
       P(full);//Determine whether there is a product available
       P(mutex_1);//Enter the critical section
        take product;
       V(mutex_1); //Leave the critical resource
       V(empty);//empty number + 1
    }
       V(mutex_2);

   }
}

This producer-consumer issue has been written so much for now, everyone must master it! If you have any questions, you can comment or message me privately.

For the other two classic synchronization process problems, you can read my other articles, and there is also a separate exercise on the real questions. You can take a look, and the editor will also give a detailed analysis.

Welcome everyone to correct me~~

syntaxbug.com © 2021 All Rights Reserved.