[Operating system] Synchronous mutual exclusion mechanism (II) : Communication mechanism between pipe and process (IPC)

A Monitor is a set of procedures that operate on a data structure about a shared resource. A process can only indirectly access data structures in a pipe by calling procedures in the pipe.

The pipe is mutually exclusive, so when one process calls the pipe, no other process can call the pipe. This is mainly designed to ensure data integrity. The mutual exclusion of pipe procedures is guaranteed by the compiler.

We already know that a process can wake up other processes waiting on a condition variable. If P enters the pipe and wakes up Q, if P and Q operate on data in the pipe at the same time, the data integrity in the pipe will be broken. How can we avoid this problem? There are three solutions:

1. P process waiting Q (Hoare process)
2. Q process waits for P process to continue (MESA process)
3. The specified wake up operation is the last executable operation in the pipe. This means that when any process wakes up another process in the pipe, that process must exit the pipe.

The Hoare tube can be illustrated with the following diagram:



As shown in the figure above, when a process P fromEntry waiting queueIt enters Hoare pipe procedure and performs various operations on resources (at this time, all other pipe procedures can only wait outside the pipe procedure). When a certain process n is executed, condition CN is found insufficient and cannot be continuedProcess P waits on the condition variable cn via the wait operation, process P gives up the mutex and opens the door for other processes to enter. Suppose Q enters, and after a number of operations, the condition variable cn is satisfied. At this point, Q wakes up PROCESS P through the signal operation, which, according to the semantics of the Hoare procedure, should be executed by P while Q waits. The Hoare procedure creates a special section within the procedure for all such processes to enter the wait state by waking up other processesEmergency waiting queue.

The above is a detailed introduction to the working process of pipe process, followed by two supplementary instructions for pipe process:

1. A pipe is mutually exclusive, so when a process attempts to enter an already occupied pipe, it should wait at the pipe’s entrance. For this purpose, an entrance waiting queue is set up at the entrance of the pipeline.
2. If process P wakes up process Q, process P waits for process Q to execute. If process Q wakes up process R, process Q waits for process R to execute. Processes P and Q enter the emergency waiting queue, and so on. Therefore, there may be multiple waiting processes inside the pipe, but at most one process can operate on the pipe at any time.

An emergency wait queue is a process wait queue created inside a pipe and has a higher priority than an entry wait queue.

This section focuses on using pipe procedures to solve producer/consumer problems. The logic is the same as PV operations using semaphores, as shown in the pseudocode in Listing 2-1. Listing 2-1 Hoare procedures for solving producer-consumer problems

monitor ProducerConsumer{
    /* Define two condition variables, full means the producer stops producing when the buffer is full and empty means the consumer stops consuming when the buffer is empty
    condition full,empty;
    /* Number of non-empty buffers */
    integer count;

    procedure insert(item :integer);
        begin
            /* When the buffer is full, the producer process aborts execution and enters the condition variable full */
            if(count==N) then wait(full); insert_item(item); count++;/* Wake up the consumer process waiting on the condition variable empty */ when the buffer data amount is 1
            it(count==1) then signal(empty);
        end;


    function remove:integer;
        begin
            /* When the buffer is empty, the consumer process aborts execution and enters the condition variable empty */
            if(count==0) then wait(empty); remove=remove_item; count--;/* Wake up the producer process waiting on the condition variable full when the buffer data amount is n-1
            if(count==N- 1) then signal(full);
        end;

    end monitor;
}

// The producer process
procedure producer;
    begin
        while(TRUE){
            item=produce_item;
            ProducerConsumer.insert(item);
        }
    end;

// Consumer process
procedure consumer;
    begin 
        while(TRUE){
            item=ProducerConsumer.remove;
            consume_item(item);
        }
    end;
Copy the code

The idea of using semaphores to solve producer-consumer problems can be found in the blog: [Operating systems] Synchronous mutex (I) : An introduction to synchronous mutex and an in-depth understanding of semaphores

Hoare procedures are based on wait/ Signal, which wakes up a process and immediately relinquish the CPU, while MESA procedures are based on Wait/Notify. Notify means that when a process in the pipeline executes notify©, it causes the C conditional queue to be notified and the signaling process to continue execution. Three things to note about Notify:

1. The result of notify is that processes at the head of the conditional queue resume execution when CPU is available in the future (unlike Hoare procedures, which do not immediately fetch CPU execution).
2. However, since there is no guarantee that no other process has entered the pipe and modified the data resources before the process, the process rechecks the condition each time before acquiring the CPU for execution. So MESA procedures replace the if statement in Hoare procedures with a while loop.
3. The effect of using the while loop to judge is that it results in at least one additional check for the condition variable. However, there are no additional process switches, and there are no restrictions on when waiting processes run after Notify.
4. Improvements: Since the process is scheduled every time the condition check is performed by the while statement, it can be implementedA monitor timer is associated with each condition primitive, and processes that exceed a certain wait time are directly set to ready state, whether notified or not(No error is reported even if the condition variable is not met, because the while statement ensures that the program receiving the signal checks the relevant variable and continues to wait if the desired condition is not met.)
   
   Listing 3-1 MESA procedures for solving producer-consumer problems

monitor ProducerConsumer{
    /* Define two condition variables, full means the producer stops producing when the buffer is full and empty means the consumer stops consuming when the buffer is empty
    condition full,empty;
    /* Number of non-empty buffers */
    integer count;

    procedure insert(item :integer);
        begin
            /* When the buffer is full, the producer process aborts execution and enters the condition variable full */
            while(count==N) then wait(full); insert_item(item); count++;/* Wake up the consumer process waiting on the condition variable empty */ when the buffer data amount is 1
            cnotify(empty);
        end;


    function remove:integer;
        begin
            /* When the buffer is empty, the consumer process aborts execution and enters the condition variable empty */
            while(count==0) then wait(empty); remove=remove_item; count--;/* Wake up the producer process waiting on the condition variable full when the buffer data amount is n-1
           cnotify(full);
        end;

    end monitor;
}
Copy the code

The mechanism of semaphores and tubes has been introduced respectively in the previous and previous sections of this paper. However, these two communication modes can only transmit simple information and do not support the transmission of large amounts of information. In addition, tubes are not suitable for users with multiple processors, so a new communication mechanism needs to be introduced.

The core idea of messaging is shown below:



Listing 4-1 implements the SEND primitive with the PV operation

/* Define the following four semaphores */
EmptyBuff: Empty message buffer, initial value N
// fullBuff: full message buffer with initial value 0
// mutex1: the initial value is 1
// mutex2: initial value is 1
send(destination,msg){
    // Find the receiving process according to destination; If not, report an error and returnApply for empty buffer P(emptyBuff); P(mutex1); Empty buffer; V(mutex1); Copy the message from MSG to an empty buffer; P(mutex2); Attach the message buffer to the receiving process's message queue V(mutex2); V(fullBuff); }Copy the code

Using aBuffered transport medium – memory or filesConnects two processes that communicate with each other. The schematic diagram is as follows:



The following three points should be paid attention to in pipeline communication mode:

1. Write as a stream of characters
2. First in, first out order is guaranteed
3. Coordination capabilities that the pipeline communication mechanism must provide: *Mutual exclusion, synchronization, check whether the other process exists

In addition to these three communication methods, there are sockets, remote procedure calls, etc.

It is indivisible and will not be interrupted by other tasks or events until it is completed; Often used to implement reference counting of resources

In this paper, we introduce the concept of pipeline and the synchronous mutual exclusion mechanism, focusing on Hoare pipeline and MESA pipeline. This paper introduces the interprocess communication mechanisms — message passing, shared memory and pipes, and introduces two IPC mechanisms in Linux system.