Chen Zhiwu chain chzg99@21cn.com
The meaning of PV primitive
P operations and V operations are uninterrupted blocks called primitives. The concept of PV primitives and semaphors is proposed by the Dutch Scientist E.W.DIJKSTRA. The semaphore SEM is an integer, and the SEM is greater than or equal to the number of resource entities that can be used for the process, but the SEM is less than zero indicating that the number of processes waiting to use the critical region. The action of the P primitive operation is: (1) SEM minus 1; (2) If the SEM is reduced, it is still greater than or equal to zero, then the process continues; (3) If the SEM is reduced, if the SEM is reduced, then the process is blocked. Enter the queue corresponding to this signal, then turn the process schedule. The action of the V primary language is: (1) SEM plus 1; (2) If the result is greater than zero, the process continues; (3) If the result is less than or equal to zero, wake up from the waiting queue of the signal. Wait for the process, then return to the original process to continue execution or transfer process schedule. PV operations can only be performed once for each process, and must be used. An interrupt occurs during the execution of PV primitives.
Using PV primitives to realize the mutual exclusion
Since the Semic Sem SEM for mutex is related to all concurrent processes, it is called a public signal amount. The value of the public signal reflects the number of public resources. Just place the critical zone between P (SEM) and V (SEM), the mutual exclusion between processes can be realized. Just as one bathroom in the train, all the passengers of the car share this public resource: toilet, so the passengers must be mutually exclusive into the bathroom, as long as the bathroom is placed between P (SEM) and V (SEM), The effect of mutual exclusion can be reached. The following example shows the mutual exclusion implementation of the process. Example 1 Workers producing Go accidentally put the equal number of black sons and white pieces into a box, now use the automatic sorting system to separate the black and white seeds, the system consists of two concurrent execution processes, the functions are as follows: (1 Process A specializes in picking a black child, the process B specializes in white; (2) Each process picks up one child, when a process does not allow another process to pick up; analysis: First step: Determine process The relationship is related. The function (2) can be known between the process is a mutual exclusion. Step 2: Determine the amount of semaphore and its value. Since the process A and the process B want to enter the box to pick the box, the box is a public resource of two processes, so set a semaphore S, depending on the number of public resources, because the box is only one, the initial value of S Set to 1. Implementation: Begin S: Semaphore; S: = 1; Cobegin Process A Begin L1: P (s); picking black; v (s); goto l1; end; process b begin L2: P (s); picking white son; v (s); goto L2; End; COEND; END; Determine whether there is mutual exclusion between processes, the key is whether there is a public resource in the process, and a public resource corresponds to a semaphore. Determine the value of the semaphore is a key point, which represents the number of available resource entities. As of the following example: Example 2 a station ticket office, at any time, you can accommodate 20 ticket purchases. When less than 20 ticket purchases in the ticket office, the ticket purchases outside the hall can enter, otherwise it is necessary to wait outside. . Each ticket purchase can see a process. Analysis: The first step: determine the relationship between processes. The ticket office is a public resource shared by all processes. When more than 20 ticket purchases in the ticket office, the tickets outside the hall need to wait outside. Therefore, the process is a mutually exclusive relationship. Step 2: Determine the amount of semaphore and its value. There is only one public resource: the ticket office, so set a semaphore S. The ticket office is up to 20 processes, ie the number of resource entities is 20, and the initial value of S is set to 20. Implementation: Begin S: Semaphore; S: = 20; Cobegin Process Pi (i = 1, 2, ...) Begin P (s); enter the ticketing hall; purchase; v (s); end; coend If the ticket is enters the ticket office to perform P (s) operation, if the S is greater than or equal to zero, the number of people in the ticket office has not been fully entered.
If the S is less than zero, the number of people in the ticket office cannot be entered. This implementation is also allowed to allow 20 processes to enter the ticket purchase ticket purchase, and the rest can only wait. Realize the synchronization of the process with PV primitives
Unlike the process, the signal amount when the process is synchronized is only related to the restriction process and the restructure process rather than related to the entire set of concurrent processes, so this signal is called private semaphore. The method of implementing process synchronization using PV primitives is: First, the relationship between the judgment processes is synchronized, and the amount of private seminated signal is set for each concurrent process, and then the first value of the private sector, and finally utilize the PV primitive and private semaphore regulations. The order of execution of each process. Here we add an example 1 to add a condition to make it synchronized between processes. Example 3 Add a function on the basis of Example 1: (3) After a process picks up a piece of chess (black and white), let another process pick a piece (black and white or white). Analysis: The first step: determine the relationship between processes. It can be seen from the function (1) (2) (3), and the relationship between processes is synchronous. Step 2: Determine the amount of semaphore and its value. Process A and B share this public resource, but specify that two processes must take turns to take different colored chess pieces, and thus interworking each other. A private signal amount S1 can be provided for the process a, which is used to determine whether the process A can pick a black child, the initial value is 1. A private signal amount S2 is also provided for the process B, which is used to determine if the process B can pick the white stroke, the initial value of 0. Of course, you can also set the size of the S1 0, and the start value of S2 is 1. Implementation: Begin S1, S2: Semaphore; S1: = 1; S2: = 0; Cobegin Process A Begin L1: P (S1); Picking Black; V (S2); Goto L1; End; Process B Begin L2: P ( S2); picking white children; v (s1); goto l2; end; coEnd; end; another question is that is the P primitive? Is there a front of the V primary language? The answer is negative. Let's take a look at an example. Example 4 is located on the bus, the activities of the driver and the ticket sellers are: drivers: launching vehicles, driving, and parking. Passerves: Passengers, shutters, ticketing, driving doors, and get off the passengers. Use a PV operation to control it. Analysis: The first step: determine the relationship between processes. After the driver is stopped, the ticket operator can work. Similarly, after the ticket seller off the door, the driver will work. Therefore, it is a synchronization relationship between the driver and the ticket. Step 2: Determine the amount of semaphore and its value. Due to the interworking message between the driver and the ticket provider, the driver process sets a private semaphore RUN to determine whether the driver can work, the initial value is 0. The ticket seller process sets a private semaphore STOP to determine if parking is stopped, and if the ticket seller can drive the door, the initial value is 0.
Implementation: Begin Stop, Run: Semaphore Stop: = 0; Run: = 0; Cobegin Driver: Begin L1: P (Run); Start the vehicle; normal driving; to the station parking; v (STOP); goto l1; end; conductor : Begin L2: Passengers; shutters; v (run); ticket sales; P (STOP); driving door; underwater; goto l2; end; coEnd; end; use PV operations can also achieve process synchronization and mutual exclusion Problem, typical: Multiple producers and multiple consumer shared cache are N. This example has been introduced in many books, and it will not be said here.
