Semaphores are used to solve process synchronization and mutual exclusion

First of all we know about the critical resources and critical area concept: critical resource is a only allows a process to access resources, a process in the use of critical resources, it is impossible to access another process, the operating system can’t midway strip is the user’s right to use, is the so-called “pour out married the daughter of water” is also. That is, critical resources are inalienable resources. What about the critical region? The so-called critical area is the process of the model critical resources of that section of the program code, note, is the program code, not memory resources, this is the difference between critical resources and critical areas. We stipulate the use principle of critical region (that is, the principle that synchronization mechanism should follow) 16 words formula: “idle to advance, busy to wait, limited to wait, let the right to wait” – Strling. Let’s break it down:

(1) Idle let in: when critical resources are idle, the process must be allowed to enter without “mutual exclusion and comity”. (2) Busy waiting: outside processes wait while critical resources are in use. (3) Limited wait: the process waits to enter the critical area for a limited time, and will not starve to death. (4) Let power wait: the process waiting to enter the critical area should give up the use of CPU.

All right, let’s move on to the next part.

There are two kinds of restriction relations between processes: direct restriction relation and indirect restriction relation, which is commonly called synchronization and mutual exclusion of processes. As the name implies, one is a cooperative relationship and the other is mutually exclusive. To put it bluntly, process mutual exclusion means that “when you use it, others can’t use it, and when others use it, you can’t use it either”, which is an indirect restriction relationship derived from resource sharing. Process synchronization refers to “we all use some common resource area, we all work together to accomplish something, but I do some small things, and you do other small things”, which is a direct constraint relationship derived from mutual cooperation. The difference between the two is that there is no necessary connection between mutually exclusive processes. It is a competitive relationship. Whoever competes for a resource uses it and does not return it until it is used up. For example, the resource of washing machine in the laundry room, there is no need for the students to be in contact with each other. You can not know each other, but whoever competes for the right to use the washing machine can use it until the washing machine is finished and gone. However, there is an inevitable connection between synchronized processes, even if the competition for the right to use, if the partner does not send out the necessary information, the process still cannot be executed. For example, queuing to fetch water, even if you are discharged, if the water tank runs out of water, you can not fetch water, indicating that you and the water tank are bound, you have to take water from it, you are synchronous relationship, you cooperate to complete the process of “fetching water”.

So let’s first discuss how to achieve mutually exclusive control of processes. There are several methods: strict rotation (each process is executed from beginning to end each time, efficiency is not high, may wait for a long time), interrupt shielding (just enter the critical zone interrupt shielding, just out of the critical zone interrupt open), special machine instructions test_AND_SET, test_AND_clear, locking, software methods, semaphore mechanism. Set a lock flag K to indicate the state of the critical resource, K=1 to indicate that the critical resource is in use, K=0 to indicate that no process is accessing the critical resource. If a process needs to access a critical resource, check the lock flag K first:

If K == 1, loop until K = 0 else if K == 0, set lock flag to 1, enter the critical regionCopy the code

When leaving the critical zone, set the lock flag K to 0. The software approach is similar, such as the Eskimo hut protocol, the Eskimo hut is small, only one person can enter at a time, and there is a blackboard inside the hut, which marks the progress of entering the critical zone. If the process applies to enter the critical area, it will first enter the cabin to check the blackboard sign. If it is oneself, then leave the cabin and enter the critical area. After the execution, enter the cabin to modify the blackboard sign to other processes and leave the cabin. If the chalkboard sign is not you, enter the chalkboard sign repeatedly to see if it is you. Both methods implement mutually exclusive access, but both violate one of the four principles: let wait, both require a constant loop to check for flags, hog CPU resources, and are not very good methods.

Later, Dutch computer scientist Dijkstra in 1965 proposed a semaphore mechanism to solve the process synchronization and mutual exclusion problem, received very good results, has been used until now, widely used in single-processor and multi-processor systems and computer networks. The semaphore mechanism means that two or more processes execute simultaneously without conflict through one or more signals that they can all use. If the critical resource is insufficient, a signal will be given, and if the process wants to access it, it will block in a queue waiting for scheduling. When the critical resource is used up, a process changes the signal and wakes up the blocked process in time, which realizes the synchronization and mutual exclusion between processes.

Semaphores are divided into integer semaphores, recording semaphores, AND semaphores, AND semaphore sets. The original semaphore is an integer semaphore, defined as an integer variable that can only be accessed by two atomic operations, P and V. Atomic operations are a set of connected operations that are either performed continuously or not at all. These two operations are also called wait and signal or Down and Up. The P,V operation is called because Dijkstra is Dutch, and the P stands for “proberen” in Dutch, meaning “to test”, while the V stands for “verhogen” in Dutch, meaning “to increase”. Originally P,V operations were described as:

P(S):   while (S≤0)  {do nothing};
            S=S-1;
            
            V(S):   S=S+1;
    Copy the code

But it obviously violates the right to make “for the principle of”, developed for recording semaphore, recording of data structure is a type of semaphore two tuples, contains the value of the semaphore value and blocked on the semaphore queue Q value with nonnegative initial value, generally reflect the amount of resources, only by P, V operation to change its value. (There is another definition, where the semaphore consists of value and P, where value is the value of the semaphore and P is a pointer to the PCB queue).

The P,V operation primitives of the recording semaphore are:

P(S):   S.value = S.value-1;
            if(S.value < 0)
               block(S,Q);
               V(S):   S.value = S.value + 1;
            if(S.value <= 0)
                wakeup(S,Q);
                Copy the code

Let’s explain what these two operations mean in detail:

If s.value <0, then it means that the original S.value< =”0, that is, there are no resources available, so the process is blocked in the blocking queue related to the semaphore S. If S.v alue < 0, then | S.v alue | actually means blocking queue length, namely the number of processes waiting to use resources. Then, the V operation: first, s.value is incremented by 1 to release a resource. If s.value “0 is blocked by a process in the queue, a process in the queue is awakened. So, why doesn’t the process wake up when s.value=””> 0? Very simple, because there are no more processes in the blocking queue.

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 implementing mutual exclusion, P,V operations are equivalent to requesting resources and releasing resources.

When we set the initial semaphore value to 1, we can usually implement a mutex because the semaphore represents the number of resources available, and the mutex guarantees that only one process can access the critical resource, which means that only one access is available. A value of 0 or N can be used for synchronization. We will see this later in the producer-consumer problem. The realization of mutual exclusion with P,V operation is similar to the realization of locking, adding P operation before the critical area, adding V operation after the critical area, the mutual exclusion control process can enter the critical area, access to critical resources. Because of the blocking mechanism introduced in the recording semaphore, the situation of not letting the weight wait is eliminated and the implementation efficiency is improved.

The classic synchronous mutex problem is also known as the bounded buffer problem. Specific performance is as follows:

1. Two processes operate on the same memory resource. One is a producer and the other is a consumer. 2. The producer fills the shared memory resource with data. If the area is full, the producer waits for consumers to consume data. 3. The consumer fetches data from the shared memory resource. If the region is empty, the consumer waits for the producer to fill the data. 4. The filling of data by producers and the consumption of data by consumers cannot occur at the same time.

When the buffer is empty, the consumer needs to wait for the producer to fill in the data; when the buffer is full, the producer needs to wait for the consumer to consume. The two work together to transfer or transmit data. The mutual exclusion between producer and consumer is that when the producer fills the buffer with data, the consumer cannot consume and needs to wait for the producer to complete the work, and vice versa.

Now that we know about mutex and synchronization, let’s set the semaphore:

Since there is a mutex relationship, we should set a mutex so that both cannot operate on the buffer at the same time. In addition, to control the synchronization relationship, we set two semaphores, empty and full, to represent the number of empty slots and the number of full slots in the buffer, that is, the number of buffer cells with data. The initial value of mutex is 1, and the initial value of empty is n, which is the buffer capacity. It means that there is no data at the beginning and there are n empty cells. Similarly, the initial value of full is 0.

The following is the producer-consumer behavior design:

Void Productor() {while(1) {// create data P(&empty); P(&mutex); // populate data V(&mutex); V(&full); } } void Consumer() { while(1) { P(&full); P(&mutex); // Consume data V(&mutex); V(&empty); }}Copy the code

So we analysis is completed, www.cnblogs.com/whatbeg/p/4… In this article I have implemented the Producer-consumer problem with semaphores using the Windows API.

Now, the question is, we have two P’s and two V’s in both producers and consumers. Can the two P’s be switched? What about V operations? Think about it.

The answer is P is not commutative, V is. Why is that? Imagine a situation where the producer performs P(mutex) to lock the mutex, and then P(empty), at which point empty < 0, is locked, unable to produce, and waits for the consumer to consume, but the mutex is locked, so the two people wait and wait for Godot. But the V operation can be swapped at will, because the V operation unlocks and wakes up, not because it locks anything.

The philosopher’s dining problem is described as follows:

There are five philosophers, their way of life is alternately thinking and eating, philosophers Shared a round table, sitting on the five chairs around respectively, on the table there are five bowls and chopsticks five, philosophers to think at ordinary times, hunger when he was trying to take the left, right closest to his chopsticks, only when he got the two chopsticks to eat, after dinner, Put down your chopsticks and go on thinking.

Constraints (1) A philosopher can eat only when he has two chopsticks. (2) If the chopsticks have been taken away by others, they must wait for others to finish eating before they can get them. (3) No philosopher will put down his chopsticks until he has two chopsticks to eat with. (4) Return the chopsticks to their original place after use

Analysis: Chopsticks are a critical resource, only one philosopher at a time, which is mutually exclusive. If the chopstick is taken away, it needs to wait. This is a synchronous relationship.

It is easy to think of a wrong solution, so set a semaphore to represent a chopstick, there are five chopsticks, so set five semaphore. Every time a philosopher is hungry, he first tries to take the chopsticks on the left, then tries to take the chopsticks on the right. If he can’t get the chopsticks, he will wait. This situation may lead to a deadlock, because we don’t know when the process switch (the root cause of this problem is also a lot of IPC), if five philosophers hunger at the same time, at the same time try to picked up the chopsticks on the left, is also very lucky to have won, so when they picked up the chopsticks on the right will take less than, and according to the third constraint conditions, will not let go of chopsticks, This creates a deadlock. Recorded in modern operating systems around a solution is only as a philosopher of chopsticks are all available, just pick up the chopsticks, “trying to get two chopsticks” as a critical resource, using a mutex mutex exclusive control of its, and then record the state of the philosopher with n variables (hunger, eating, thinking < dispensable, >), and then use an array of synchronized semaphores, each corresponding to a philosopher, to ensure that the philosopher can not get the chopsticks he needs to block. The algorithm is as follows:

Another solution is to make the even-numbered and odd-numbered philosophers hold the chopsticks in different order to destroy the loop waiting condition. It is also possible to allow only 4 philosophers to eat at the same time (if 4 people all take one chopstick, the 5th person can’t take another chopstick, thus leaving one chopstick free)

There is an empty plate on the table, and no more than one fruit is allowed. Dad can put an apple on the plate, mom can put an orange on the plate. The son waited for the orange on his plate, the daughter for the apple. Try P and V operation to realize the synchronization of father, mother, son and daughter.

Analysis: Critical resources are dishes, which can not be taken, taken and taken again. Synchronous relationship: father, mother and plate are empty, son and plate have orange, daughter and plate have apple.

So set up a mutex semaphore to control access to the plate, using empty, orange, and apple to represent the synchronization relationship. The procedure is as follows:

Semaphore mutex = 1; Semaphore empty = 1, orange = apple = 0; mother: while(1) { P(empty); P(mutex); // Add orange V(mutex) V(orange); } father: while(1) { P(empty); P(mutex); // Add apple V(mutex) V(apple); } son: while(1) {P(orange) P(mutex) // take orange V(mutex); V(empty); } daughter: while(1) {P(apple) P(mutex) // take apple V(mutex); V(empty); }Copy the code

There was a reading room in which the reader had to enter on a registration form which gave a table for each seat, including the seat number and the reader’s name. Readers have to cancel the sign-in when they leave. There are 100 seats in the reading room. The process is controlled by PV operation.

Analysis:

Since every reader does the same thing: register -> enter -> read -> unregister -> leave, create a reader model. The critical resources are: seats, and the register table readers have a mutually exclusive relationship between seats and the register table. Therefore, set the semaphore empty to represent the number of empty seats, initially 100, and mutex to represent mutually exclusive access to the register table, initially 1.

P,V operations are as follows:

Semaphore mutex = 1, empty = 100; Reader () : While(true) {P(empty) {P(true) {P(empty) // register V(mutex) // register V(mutex) // V(empty) // Free seat}Copy the code

Analysis: The critical resource is a small section with half of the blocked area, so Go_mutex and Come_mutex are needed to control the passage of vehicles in each direction and realize the synchronization relationship between the two directions. The synchronization relationship is: when there are vehicles in one direction, the vehicles in the other direction must wait, and vice versa. Similar to the reader-writer problem, vehicles passing from both sides are equivalent to two readers. We set up two counters, A and B, respectively representing the number of cars in two directions, and two semaphore A_mutex and B_mutex, to achieve mutually exclusive access to the counter, because only one car is allowed to pass the landslide. Therefore, we also need to set a mutex to ensure that vehicles in the same direction pass through the mutex.

The procedure is as follows (PV operation included) :

#include <Windows.h> #include <stdio.h> #define N 100 #define TRUE 1 typedef int Semaphore; Semaphore A = 0, B = 0; HANDLE Go_mutex,Come_mutex; HANDLE A_mutex,B_mutex; HANDLE mutex; void down(HANDLE handle) { WaitForSingleObject(handle, INFINITE); } void up(HANDLE handle) { ReleaseSemaphore(handle, 1, NULL); } DWORD WINAPI Come(LPVOID v) { while(TRUE) { down(Come_mutex); down(A_mutex); A = A+1; if(A == 1) { down(Go_mutex); Printf (" <<<===== starts from east to west \n"); } up(A_mutex); up(Come_mutex); down(mutex); / / from east to west through the roadway printf (" < < < = = = = = car first % s \ n ", v) (char *); Printf (" END <<<===== th %s car \n",(char *)v); up(mutex); down(A_mutex); A = A-1; if(A == 0) { up(Go_mutex); Printf (" All traffic from east to west completed \n"); } up(A_mutex); Sleep(2000); } return 1; } DWORD WINAPI Go(LPVOID v) { while(TRUE) { down(Go_mutex); down(B_mutex); B = B+1; if(B == 1) { down(Come_mutex); Printf (" start from west to East ====>\n"); } up(B_mutex); up(Go_mutex); down(mutex); Printf (" nO %s 车=====>>>\n",(char *)v); Printf (" %s 车=====>>> END\n",(char *)v); up(mutex); down(B_mutex); B = B-1; if(B == 0) { up(Come_mutex); Printf (" All traffic from west to east finished \n"); } up(B_mutex); Sleep(2000); } return 1; } int main() { DWORD Tid; char AThread[12][10]; char BThread[12][10]; mutex = CreateSemaphore(NULL, 1, 1, NULL); A_mutex = CreateSemaphore(NULL, 1, 1, NULL); B_mutex = CreateSemaphore(NULL, 1, 1, NULL); Go_mutex = CreateSemaphore(NULL, 1, 1, NULL); Come_mutex = CreateSemaphore(NULL, 1, 1, NULL); for(int i=0; i<4; i++) { AThread[i][0] = i+1+'0'; AThread[i][1] = '\0'; CreateThread(NULL,0,Come,AThread[i],0,&Tid); } for(int i=4; i<8; i++) { BThread[i][0] = i+1+'0'; BThread[i][1] = '\0'; CreateThread(NULL,0,Go,BThread[i],0,&Tid); } Sleep(20000); return 0; }Copy the code

Running results:

From which it can be seen that the normal alternating sequence of vehicles through the section. The number repeats because threads are scheduled to execute repeatedly.

Modern Operating System — Andrew S. Tanenbaum 2. Operating System Design and Implementation — Andrew S. Tanenbaum 3. Essence and Design Principle of Operating System — Strling 4