Multiple threads are fighting for the same resource. How can they be peaceful?

However, this did not affect Xiaoming. Unexpectedly, a huge thunder flashed by and the office building was cut off. Then the whole building echoed with Xiao Ming’s heartbreaking “sleeping trough”. < p > < p > when he got to the toilet, he rushed into the toilet because he was in a hurry. He felt for the first door with his hands, and then he grabbed the door. < / P > < p > in the dark, although Xiao Hong can’t see, relying on the sound, she finds that there is something wrong with the door in front of her, so she rivets her strength and kicks it with her high-heeled shoes. < / P > < p > when the story is finished, we have talked so much about it. In fact, it is to show that for shared resources, if there is no lock, in a multi-threaded environment, there may be a rollover scene. < / P > < p > in a single core CPU system, in order to realize the illusion of multiple programs running at the same time, the operating system usually schedules each process to execute one time slice at a time. When the time slice is used up, the next process will be switched to run. Because the time slice is very short, the phenomenon of “concurrency” is caused. < / P > < p > in addition, the operating system also creates the illusion of huge and private virtual memory for each process. This abstraction of address space makes each program seem to have its own memory. In fact, the operating system secretly makes multiple address spaces “reuse” physical memory or disk. < / P > < p > If a program has only one execution process, it also means that it is single threaded. Of course, a program can have multiple execution processes, which is the so-called multithreaded program. Thread is the basic unit of scheduling, and the process is the basic unit of resource allocation. < / P > < p > therefore, threads can share process resources, such as code segments, heap space, data segments, open files and other resources, but each thread has its own independent stack space. < / P > < p > each run will not only produce errors, but also get different results. It can’t be tolerated in computers. Although it’s a small probability error, it must happen in a small probability event. “Murphy’s law” is understood by everyone. < / P > < p > imagine that our thread 1 enters this code area. It loads the value of I from memory into its register, and then it adds 1 to the register. At this time, the I value in the register is 51. < / P > < p > now, an unfortunate thing happens: a clock interrupt occurs. Therefore, the operating system saves the state of the currently running thread to the thread control block TCP of the thread. < / P > < p > now something worse happens, thread 2 is scheduled to run and enter the same piece of code. It also executes the first instruction, fetches the I value from memory and puts it into a register. At this time, the value of I in memory is still 50, so the I value in thread 2 register is also 50. Suppose thread 2 executes the next two instructions, I value in register + 1, then I value in register is saved in memory, so global variable I value is 51. < / P > < p > finally, another context switch occurs and thread 1 resumes execution. Remember that it has executed two assembly instructions and is now ready to execute the last instruction. Recall that the I value in thread 1 register is 51, so after the last instruction is executed, the value is saved to memory and the value of global variable I is set to 51 again. < / P > < p > in short, the code that increases I is run twice. Logically, the last I value should be 52, but due to uncontrollable scheduling, the final I value is 51. < / P > < p > the situation shown above is called contention condition. When multiple threads compete with each other to operate shared variables, due to bad luck, that is, context switching occurs during the execution process, we get wrong results. In fact, each run may get different results, so the output results are uncertain. < / P > < p > because the code of sharing variables by multithreading may lead to competition, we call this code critical section. It is a code fragment that accesses shared resources and must not be executed by multiple threads at the same time. < / P > < p > we hope that this code is mutually exclusive, that is to say, when a thread is executing in the critical section, other threads should be prevented from entering the critical area. In other words, only one thread can appear during the execution of this code. In addition, mutual exclusion is not only for multithreading. When multi processes compete to share resources, they can also use mutual exclusion to avoid resource confusion caused by resource competition. < / P > < p > mutex solves the problem of using critical area by concurrent processes / threads. This interaction based on critical area control is relatively simple. As long as a process / thread enters the critical area, other processes / threads that try to enter the critical area will be blocked until the first process / thread leaves the critical area. < / P > < p > we all know that in multithreading, each thread does not necessarily execute in sequence, and they basically advance at an independent and unpredictable speed. However, sometimes we hope that multiple threads can cooperate closely to achieve a common task. < / P > < p > for example, thread 1 is responsible for reading data, while thread 2 is responsible for processing data. These two threads are cooperative and interdependent. When thread 2 does not receive the wake-up notice from thread 1, it will always block and wait. When thread 1 reads the data and needs to pass the data to thread 2, thread 1 will wake up thread 2 and hand over the data to thread 2 for processing. < p > < p > the so-called synchronization means that concurrent processes / threads may need to wait for and exchange messages with each other at some key points, which is called process / thread synchronization. < / P > < p > for example, if you want to eat when you are hungry, you ask your mother to cook early. When your mother hears about it, she starts cooking. However, before your mother finishes the meal, you have to stop and wait. After that, you will be informed. Then you can have your meal. < / P > < p > synchronization is like “operation a should be executed before operation B”, “operation C must be executed after operation a and operation B are completed”, etc.; mutual exclusion is like “operation a and operation B” In order to achieve the correct cooperation between processes / threads, the operating system must provide measures and methods to achieve process collaboration. There are two main methods: < / P > < p > locking: locking and unlocking operations; signal: P, V Both of them can easily realize process / thread mutual exclusion, and semaphore is more powerful than lock, and it can also realize process / thread synchronization conveniently. < / P > < p > any thread that wants to enter the critical region must execute the lock operation first. If the lock operation passes smoothly, the thread can enter the critical area; after the access to the critical resource is completed, the unlock operation is performed to release the critical resource. < / P > < p > before explaining the implementation of “busy wait lock”, this paper first introduces the special atomic operation instructions provided by modern CPU architecture — Test and set instructions. < / P > < p > old_ When PTR is updated to new, old is returned_ The old value of PTR; of course, the key is that the code is atomic execution. Because you can test old values and set new values, we call this instruction “test and set.”. < / P > < p > the first scenario is to assume that a thread is running and calls lock. No other thread holds the lock, so the flag is 0. When the testandset method is called and returns 0, the thread will jump out of the while loop and obtain the lock. At the same time, the flag of the atom is set to 1, indicating that the lock has been held. When the thread leaves the critical area, it calls unlock to clean the flag to 0. The second scenario is when a thread already holds a lock. This thread calls lock and then calls TestAndSet, which returns 1 at this time. As long as another thread holds the lock all the time, testandset will repeatedly return 1, and the thread will be busy all the time. When the flag is finally changed to 0, the thread will call testandset, return 0 and set it atomically to 1 to obtain the lock and enter the critical area. Obviously, when the lock cannot be obtained, the thread will loop all the time and do nothing, so it is called “busy waiting lock”, also known as spin lock. < / P > < p > this is the simplest type of lock, spinning all the time, using CPU cycles until the lock is available. On a single processor, a preemptive scheduler is required. Otherwise, spinlocks cannot be used on a single CPU, because a spinning thread never abandons the CPU. < / P > < p > since you don’t want to spin, when the lock is not obtained, put the current thread into the waiting queue of the lock, and then execute the scheduler to let the CPU run by other threads. < / P > < p > this time, only two simple lock implementations are proposed. Of course, in the specific implementation of the operating system, it will be more complex, but also inseparable from the two basic elements of this example. < / P > < p > if you want to have a better understanding of locks, it is recommended that you can read the contents of chapter 28 locks. This book can be read for free in “wechat reading”. < / P > < p > P operation: after subtracting SEM by 1, if SEM & lt; 0 is reduced, the process / thread will enter the blocking wait; otherwise, it will continue, indicating that the P operation may be blocked; V operation: add 1 to SEM, and then add if SEM & lt; 0; =0, wake up a waiting process / thread, indicating that the V operation will not be blocked; P operation is used before entering the critical area, and V operation is used after leaving the critical area, and these two operations must appear in pairs. The functions of PV operation are managed and implemented by the operating system, so the operating system has made the execution of PV functions atomic. < / P > < p > at this time, any thread that wants to enter the critical region must first perform P operation on the mutex semaphore, and then execute V operation after completing the access to critical resources. Since the initial value of the mutex semaphore is 1, the s value changes to 0 after the first thread performs the P operation, indicating that the critical resource is idle and can be allocated to the thread to enter the critical area. < / P > < p > if there is a second thread that wants to enter the critical area, it should also perform the P operation first. As a result, s becomes negative, which means that the critical resource has been occupied. Therefore, the second thread is blocked. After the first thread executes the V operation to release the critical resource and recover the s value to 0, the second thread is awakened to enter the critical area. After the access of the critical resource is completed, V operation is executed again to restore s to the initial value of 1. < / P > < p > if the mutex semaphore is 1, it means that no thread has entered the critical area; if the mutex semaphore is 0, it means that a thread has entered the critical area; if the mutex semaphore is – 1, it means that one thread has entered the critical area, and the other thread is waiting to enter. Through the way of mutual exclusion semaphore, we can ensure that only one thread is executing in the critical area at any time. < / P > < p > the semaphore changes from – 1 to 0, indicating that the son needs to eat at this time, so he wakes up in the blocking