Official account: Java Xiaokaxiu, website: Javaxks.com

Author: Hopefully Sky, link: blog.csdn.net/fuzhongmin0…

Producer-consumer problem

Producer-consumer questions are very common in all kinds of exams (graduate school entrance exam, programmer certificate, programmer interview written exam, final exam). One reason is that producer-consumer questions are very common in practical concurrent program (multi-process, multi-thread) design. The second is that this kind of question is more comprehensive, involving process cooperation, mutual exclusion, sometimes also related to the avoidance of deadlock. Producer-consumer questions are a comprehensive test of your understanding and design of concurrent programs.

The most basic producer-consumer problem is the producer consumer problem with bounded buffer and the producer consumer problem with unbounded buffer. We should grasp the solutions of these two problems.

For the producer-consumer problem of bounded buffers, two processes share a common fixed-size buffer. One is a producer, putting information into a buffer; The other is the consumer, taking information out of the buffer (we can generalize the problem to m producers and N consumers, but we’ll only talk about one producer and one consumer to simplify the solution).

The problem is that when the buffer is full and the producer wants to put a new item into it, the solution is to let the producer sleep and wake it up when the consumer removes one or more items from the buffer. Similarly, when a consumer tries to fetch data from a buffer and finds that the buffer is empty, the consumer sleeps until the producer puts some data into it and wakes it up.

As simple as this method sounds, to keep track of the number of data items in the buffer, we need a variable count. If the buffer contains a maximum of N items, the producer code checks first to see if count reaches N. If so, the producer is asleep. If not, the producer checks first to see if count reaches N. Otherwise the producer puts a data item into the buffer and increments the value of count.

The consumer code is similar: first tests if count is 0, if so, sleep; Otherwise, take an item from it and decrement count. Each process also detects whether another process should be woken up, and if so, wakes it up. The code for the producer consumer is as follows:

#define N 100 int count = 0; void producer(void) { int item; while(TRUE) { item = produce_item(); If (count == N) // Sleep (); insert_item(item); count = count + 1; If (count == 1) wakeup(consumer); } } void consumer(void) { int item; While (TRUE) {if(count == 0) // Sleep (); item = remove_item(); count = count - 1; If (count == n-1) wakeup(producer); consume_item(item); }}Copy the code

Race conditions are possible because access to count is not restricted. It is possible that the buffer is empty, the consumer has just read the value of count and found that it is 0, at which point the scheduler decides to suspend the consumer and start running the producer (process switch). The producer adds an item to the buffer, count plus 1. The producer now calls wakeup to wakeup the consumer, assuming that count was 0 and that the consumer must be asleep.

But the consumer is not logically asleep, so the wakeup signal is lost, and the next time the consumer runs, it tests the previously read count value and finds that it is 0. So sleep, sooner or later the producer will fill the buffer, and then sleep, and both processes will sleep forever.

Introduction and operation of semaphore

A semaphore is a method proposed by Dijkstra in 1965 that uses an integer variable to accumulate the number of awakenments for later use. In his proposal, he introduced a new variable type called a semaphore. A semaphore can have a value of 0 (indicating that no wake up operations have been saved) or a positive value (indicating that one or more wake up operations have been performed).

Dijkstra suggests setting up two operations: down and up (generalized sleep and wakeup, respectively). To perform down on a semaphore, check whether its value is greater than 0. If the value is greater than 0, subtract it by 1 (that is, discard a saved wake signal) and continue; If this value is 0, the process will sleep and the down operation has not finished. Checking values, changing variable values, and possible sleep operations are all performed as a single, indivisible atomic operation. Ensure that once a semaphore operation is started, no other process is allowed to access the semaphore until the operation is complete or blocked. This atomicity is absolutely necessary to solve synchronization problems and avoid race conditions. An atomic operation is a set of related operations that are either performed continuously or not at all.

The up operation increments the semaphore value by 1. If one or more processes are asleep on the semaphore and unable to complete a previous DOWN operation, the system selects one of them (e.g. randomly) and allows the process to complete its down operation. Thus, after an up operation is performed on a semaphore on which a process is sleeping, the value of the semaphore is still 0, but there is one less process sleeping on it. Increasing the semaphore value by 1 and waking up a process are also inseparable, and no process will block for up execution, just as no process will block for wakeup execution in the previous model.

In Dijkstra’s original paper, he used the names P and V instead of down and up, respectively. In Dutch, Proberen means to try, and Verhogen means to increase or raise.

Explain the meaning of P and V operation of semaphore physically. P(S) indicates that a resource is applied for. S.value>0 indicates that a resource is available and the value is the number of resources. S.value=0 indicates that no resource is available. S.v alue < 0, | S.v alue | said S process in the wait queue number. V(S) represents the release of a resource, and the initial semaphore value should be greater than or equal to 0. The P operation is equivalent to “waiting for a signal”, while the V operation is equivalent to “sending a signal”. In the implementation of synchronization, the V operation is equivalent to sending a signal saying that the collaborator has completed a task, and in the implementation of mutual exclusion, the V operation is equivalent to sending a signal saying that the critical resource is available. In fact, when mutual exclusion is implemented, P and V operations are equivalent to applying for resources and releasing resources.

The solution uses three semaphores: one called full, which records the number of full buffer slots, and one called Empty, which records the total number of empty buffer slots. One, called mutex, is used to ensure that producers and consumers do not access the buffer at the same time. The initial value of full is 0, the initial value of empty is the number of slots in the buffer, and the initial value of mutex is 1. A semaphore used by two or more processes, with an initial value of 1 to ensure that only one process can enter the critical region at a time, is called a binary semaphore. Mutual exclusion can be achieved if each process performs a down operation before entering a critical section and an up operation just after exiting.

In the example below, we actually use the semaphore in two different ways, and it is important to distinguish between the two. The semaphore mutex is used for mutex, which is used to ensure that only one process reads or writes the buffer and associated variables at any one time. Mutex is a necessary operation to avoid chaos.

#define N 100 typedef int semaphore; semaphore mutex = 1; semaphore empty = N; semaphore full = 0; void producer(void) { int item; while(TRUE) { item = produce_item(); down(&empty); // The number of empty slots is reduced by 1, equivalent to P(empty) down(&mutex); P(mutex) insert_item(item); // Put the new data into the buffer up(&mutex); V(mutex) up(&full); V(full)}} void consumer(void) {int item; while(TRUE) { down(&full); P(full) down(&mutex); P(mutex) item = remove_item(); // Fetch data from buffer up(&mutex); // Leave the critical section, equivalent to V(mutex) up(&empty); // Add 1 to the number of empty slots, equivalent to V(empty) consume_item(item); // Process the data item}}Copy the code

Another use of semaphores is for synchronization, where full and Empty are used to ensure that certain events occur or do not occur in sequence. In this case, they ensure that the producer stops when the buffer is full and the consumer stops when the buffer is empty.

For the producer-consumer problem of unbounded buffers, two processes share a common buffer of unlimited size. Because it is an unbounded buffer (the warehouse is unbounded), that is, producers don’t care whether the warehouse is full, they just produce things into it, but consumers still care whether the warehouse is empty. So producers don’t block if they can’t get a buffer, don’t need to manage empty buffers, and can remove the semaphores and PV operations used to manage empty buffers in bounded buffers.

Semaphore mutex = 1; Semaphore full = 0; Int in = 0, out = 0; void producer(void) { while(TRUE) { item = produce_item(); P(mutex); Buffer(in) = item; // Put the newly produced data item into the buffer in = in + 1; // Input pointer is out of bounds V(mutex); // Leave the critical section V(full); // Increase the number of used buffers}} void consumer(void) {int item; while(TRUE) { P(full); // Wait for the number of used buffers to be non-0 P(mutex); Item = Buffer(out); Out = out + 1; // The output pointer is out of bounds V(mutex); Consume_item (item); // Process the data item}}Copy the code

In computing, synchronization is when a process executes a request and if it takes some time to return information, the process will wait. Execution does not continue until a return message is received. Asynchronism means that the process does not need to wait for a long time, but continues to perform the following operations. When a message is returned, the system notifies the process to process it, which improves efficiency.

Process synchronization and mutual exclusion

In an operating system, a process is the smallest unit of resource ownership (a thread can access all the resources in its process, but the thread does not own the resources itself or only a few necessary resources). For some resources, however, only one process can occupy them at a time. These resources, which can only be occupied by one process at a time, are called critical resources. Critical resources such as physical printers, or variables and data that exist in hard disk or memory and are shared by multiple processes (if such resources are not protected as critical resources, they may cause data loss problems).

Access to critical resources must be mutually exclusive. That is, when a critical resource is occupied, another process applying for the critical resource will be blocked until the critical resource is released. Code that accesses critical resources in a process is called a critical section.

Process synchronization is also the direct restriction relationship between processes, which is the restriction relationship between two or more processes established to complete a certain task, and these processes need to coordinate their work order in some locations while waiting and transmitting information. The direct constraining relationship between processes comes from their cooperation. For example, process A needs to read information from the buffer generated by process B. When the buffer is empty, process B blocks because it cannot read information. When process A generates information and puts it into the buffer, process B is woken up.

Process exclusion is an indirect constraint relationship between processes. When one process enters a critical section to use a critical resource, another process must wait. Only when a process using a critical resource exits a critical section will the process be unblocked. ** For example, if process B needs to access the printer and process A occupies the printer, process B will be blocked until process A releases the printer resources and process B can continue to execute, as shown in the following figure.

Synchronization and mutual exclusion of processes refer to the mutual restriction of processes in advance. Process synchronization originates from process cooperation, which is a direct interaction between processes to complete a task together. Process exclusion is an indirect restriction relationship between processes due to the competition for critical resources.

The basic methods to realize the critical region mutually exclusive access are hardware implementation method and semaphore method.

The easiest way to implement critical sections in hardware is to turn off CPU interrupts. From the computer principle we know that CPU process switch is to be interrupted to carry out. If the interrupt is shielded, the current process can be guaranteed to successfully complete the critical section of the code, thus realizing the mutual exclusion. The steps of this approach are: mask interrupts – perform critical section operations – open interrupts. But this is not good, and it greatly limits the processor’s ability to alternate tasks. And the permission to turn off the interrupt to the user code, so if the user code after shielding the interrupt is no longer open, the system is not kneeling?

Semaphore implementation, which we are more familiar with P/V operations. By setting a semaphore S representing the number of resources, by P and V operations on the semaphore S to achieve mutually exclusive process. P/V operations are operating system primitives meant to be atomic. The P operation first reduces the semaphore S**, indicating that a process will occupy or wait for resources **, and then detects whether S is less than 0** *. If S is less than ** 0, it will block. If S is greater than 0, it will occupy resources for execution. V operation is the opposite operation to P operation. It first increases the semaphore S**, indicating that the number of processes occupying or waiting for resources decreases by ** 1. Then it detects whether S is less than 0, and wakes up other processes waiting to use S resources if it is greater than 0. The previous producer-consumer problem is a typical process synchronization problem solved using semaphores.