Process synchronization in distributed operating system
Return this lecture outline
Under stand-alone conditions, processes are running in the same processor and memory environment, and the process communication is very simple. Process can be used to share storage
"Perform direct communication. And under multi-aircock conditions, the process of cooperation with each other may run on different processes, communication between processes involves communication of the processor.
problem. In loose coupling systems, inter-process communication may also have to pass longer communication channels, or even networks. Therefore, under multi-machine conditions, widely used
The communication method, that is, the process is communicated by the message. In a distributed operating system, in order to achieve synchronization of the process, first occur in the system.
The event is sorted, and there is a good distributed synchronization algorithm.
First, see the event sorting problem. In a single processor system and a closely coupled multiprocessor system, since a total of a clock is shared, the memory is confirmed.
The order of the two events is relatively easy. In the distributed system, there is no shared clock, no shared memory, naturally it is difficult to determine two events.
Successful order. The sorting here includes both a prejudice to determine the two events, but also includes all events. Below we will introduce
A algorithm that Lamport proposed in 1978. This method is based on the following:
(1) The preferences between events;
(2) Set a logical clock for each process. The so-called logic clock refers to all activities that are launched locally, give a number of institutions, he
You can use a counter. In the system, each process has its own logical clock C. In a logical clock system of a system, conditions should be met:
For any activity A (INI) and B (Inj), if A-> B, the corresponding logic clock C (i, a)
The process of position. In order to meet the above conditions, the following rules must be followed:
First, according to the active occurrence, give each activity unique logical clock value.
Second, if the active A is a message M transmitted by the process 1, the message m should include a time postmark T (M) = C (i, a); when the acceptance process j is receiving
When the message is sent, if its logic clock C (J, B) Here we describe the second rule. Since each process has its own logical clock, the operation of these clock is not synchronous, so there may be This situation: The logic clock C (M) = 100 included in the message sent by the process 1, and the logic clock C receiving process j is receiving this message C (j) = 96, this obviously violates the requirements of the full order, because there is a relationship between A-> B between the send message event A and the receiving event B. Therefore, second regulations Then, synchronization of logic clock is used. According to this rule, the clock of the process J should be adjusted to make C (j)> = c (m), such as C (j) = c (m) 1 = 101. Second, see the synchronization algorithm. In all synchronization algorithms, all of the following four assumptions: (1) Each distributed system has n nodes, each node has a unique number, which can range from 1 to N. There is only one process in each node to visit Ask a request for shared resources. (2) Sequentially transfer information. That is, the sending process sends a message, and the receiving process is also received in the same order. (3) Each message can be transferred to the target process in a limited time. (4) Direct communication can be implemented between the processing unit, that is, each process can send the message directly to the specified process, and do not need to pass through the transfer processor. In the synchronous algorithm, the famous Lamport Algorithm, the Ricart and Agraword Algorithm, Mackawa (Square-Root) Algorithm, etc. Introduce several of them. 1, LAMPORT algorithm In this method, all events requiring access to critical resources are used in this method, and in accordance with the principle of first serving first, Treatment. The algorithm specifies that each process Pi, when sending a request message request, it should be put the time postmark (Ti, i) for it, where Ti is the log of the process PI. The clock value, and all the request queues are held in each process, and the queue contains a request message sorted by logical clock. Lamport algorithm with the following five Rules definition: (1) When the process PI requires access to a resource, the process will request a message in its own request queue and send a request (TI, I) message. Give all other processes. (2) When the process Pj receives the Request (TI, I) message, form a REPLY (TJ, J) message on the last postmark, put it in your own request team. Columns. It should be noted that if the process PJ receives the Request (TI, I) message, the access request for the same resource is proposed, then its time postmark should be T (Ti, i) is small. (3) If the following two conditions are met, the process Pi is allowed to access the resource: ● The message requested to access the resource is already the front of the request queue. ● PI has received response messages returned from all other processes, which are late in the postmark time than t (ti, i). (4) In order to release the resource, Pi eliminates the request message from its own request queue, and sends a Release message that hits the time postmark to all other processes. (5) After the process Pj receives the release message of the PI, remove the PI Request (Ti, I) message from its own queue. Thus, when each process is to access a shared resource, this algorithm requires the process to send 3 (n-1) messages, where (N-1) is a request message, (N-1) a reply message, (n-1) a Release message. 2, Ricart and AgrawLA algorithm Ricart et al. Proposed distributed synchronization algorithm, which is based on Lamport's event, but make some modifications, so that each access shared variable, only A 2 (N-1) message is required. Below is a description of the Ricart and AgrawLA algorithm. (1) When the process PI requires access to a resource, it sends a Request (TI, I) message to all other processes. (2) After the process Pj receives the Request (TI, I) message, the following operations are performed: ● If the process PJ is in the critical area, the postponation will issue a reply response to the process Pi; ● If the process PJ is currently not required to access critical resources, return a reply message with a timely postmark immediately; ● If the process PJ also requires access to critical resources, the postmark time in the message Request (Ti, i) is earlier than (tj, i), and then returns one sometimes REPLY message between postmarks; otherwise, PJ reserves the message sent by PI Request (Ti, I), and postpon a reply response. (3) When the process PI receives the response sent by all other processes, the resource can be accessed. (4) When the process releases the resource, only the REPLY message is sent to all processes that postpone the Reply message. This algorithm can achieve better performance: enable mutual exclusive access to shared resources; it can guarantee that there is no dead lock, because in the process - resource map In the middle, there will be a loop; there will be no hunger, because the access to the shared resource is sorted according to the postmark time, that is, according to the FCFS principle; each When accessing a shared resource, you only need to send 2 (n-1) messages. The following figure illustrates the status conversion of the process when accessing the shared resource: Of course, this algorithm also has a certain problem: First, each process that requires access to the shared resource must know the name of all processes, so once there is The new process enters the system, which will notify all processes in the system. Second, if there is a process in the system fail, it will inevitably make a request message. The process cannot receive a full response, so the system should also have such a function, that is, once a process is invalid, the system can notify the name of the process. process. 3, token delivery To implement the process mutual exclusion, token token is set in the system to indicate access to power. The token itself is a special format, usually only one The length of the byte is constantly looping in a logical ring that consists of a process. Every process in the ring is only the only preamble (PRODECESSOR) and the only postupor. When the token in the loop is looped to a certain process and is received, if the process wants to enter The critical area, it maintains the token and enters the critical area. Once it launches the critical area, transfer the token to the successor process. If the process of receiving the token is not Requires to enter the critical area, transfer the token directly to the subsequent process. Since there is only one token in the logical ring, the mutual exclusion of the process is achieved. use When the token, the following two points must be met: (1) The logic loop should have the ability to fail to fail or exit in a process in the loop, and communication link failure. Once the above situation is found, it should be immediately Undo the process or reconstruct the logical ring. (2) Must ensure that there is a token at any time at any time. Once the token is discovered, you should immediately select a process to generate a new token. Using the token delivery method to achieve mutual exclusion, the number of messages required is uncertain. Because, no matter whether there is a process request to enter its critical regions, the token is always Logic rings circulating, when all processes in the logical loop require access to the critical regions, the average per process is only a message to access the critical regions. But if you are on the token In a week, only one process requires access to the critical area, then equivalently requires N messages (n is the number of processes in the logical ring). Even if there is no process To enter the critical regions, there is still a constant transmission token. On the other hand, in the token delivery method, there is a natural priority relationship, that is, the upstream station has more High priority, it is prioritized to enter the critical regions. Just like the FCFS queue, the process in the loop can enter its critical regions in turn, so there will be no appearance. Hungry phenomenon.
