Shulou(Shulou.com)05/31 Report--

This article mainly explains how to understand the application scenarios of mutex, spin lock, read-write lock, pessimistic lock and optimistic lock. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn how to understand the application scenarios of mutex, spin lock, read-write lock, pessimistic lock and optimistic lock.

Text

When multithreading accesses shared resources, the problem of data confusion caused by resource competition can not be avoided, so we usually add locks before accessing shared resources in order to solve this problem.

The most commonly used is mutex locks, of course, there are many different locks, such as spin locks, read-write locks, optimistic locks and so on. Different kinds of locks are naturally suitable for different scenarios.

If you choose the wrong lock, then in some high concurrency scenarios, it may degrade the performance of the system, so the user experience will be very poor.

Therefore, in order to choose the appropriate lock, we not only need to know clearly the cost of locking, but also need to analyze the way of accessing the shared resources in the business scenario, and then consider the collision probability when accessing the shared resources concurrently.

Only by prescribing the right remedy to the case can we reduce the impact of locks on high concurrency performance.

Then, for different application scenarios, talk about the selection and use of "mutex lock, spin lock, read-write lock, optimistic lock, pessimistic lock".

Mutex or spin lock: who is more relaxed?

The bottom two are mutex and spin locks, there are many advanced locks are based on them, you can think of them as the foundation of various locks, so we must be aware of the difference and application between them.

The purpose of locking is to ensure that shared resources are accessed by only one thread at any time, so that the problem of shared data confusion caused by multi-threads can be avoided.

When one thread is already locked, other threads fail, and mutexes and spin locks are handled differently after locking failures:

When a mutex lock fails, the thread releases the CPU to other threads

When the spin lock fails, the thread waits until it gets the lock.

Mutex is a kind of "exclusive lock". For example, when thread A successfully locks, the mutex has been monopolized by thread A. as long as thread A does not release the lock, thread B will fail to lock, so it will release CPU to other threads. Since thread B has released CPU, the lock code of natural thread B will be blocked.

The phenomenon of blocking due to the failure of mutex locking is implemented by the operating system kernel. When locking fails, the kernel puts the thread to a "sleep" state, and when the lock is released, the kernel wakes up the thread at the appropriate time, and when the thread successfully acquires the lock, it can continue to execute. As shown below:

Therefore, when the mutex lock fails, it will fall into the kernel state from the user mode, and let the kernel help us switch threads. Although it simplifies the difficulty of using the lock, there is a certain performance cost.

What is the cost of this expense? There is the cost of two thread context switches:

When a thread fails to lock, the kernel sets the state of the thread from "run" to "sleep", and then switches the CPU to another thread to run.

Then, when the lock is released, the thread in the previous "sleep" state becomes "ready", and then the kernel switches the CPU to the thread to run at the appropriate time.

What is the context switch of the thread? When two threads belong to the same process, because the virtual memory is shared, these resources remain unchanged when switching, and only the private data, registers and other unshared data of the thread need to be switched.

The time it takes to switch up and down has been counted by the boss, probably between tens of nanoseconds to a few microseconds, if the execution time of the code you lock is relatively short, it may take longer to switch context than the code you lock.

Therefore, if you can be sure that the locked code has a short execution time, you should not use a mutex, but should choose a spin lock, otherwise you should use a mutex.

Spin lock is through the CAS function (Compare And Swap) provided by CPU to complete the locking and unlocking operation in "user mode" without active thread context switching, so it is faster and less expensive than mutex lock.

The general locking process consists of two steps:

The first step is to check the status of the lock, and if the lock is idle, perform the second step

Second, set the lock to be held by the current thread

The CAS function combines these two steps into a single hardware-level instruction to form an atomic instruction, which ensures that the two steps are inseparable and either execute two steps at once or neither.

When using a spin lock, when there is a multithreaded contention for the lock, the thread that failed to add the lock will "wait" until it gets the lock. The "busy wait" here can be implemented using the while loop wait, but it is best to use the PAUSE instruction provided by CPU to achieve the "busy wait", because you can reduce the power consumption when the loop waits.

The spin lock is the simplest type of lock that spins all the time, using the CPU cycle until the lock is available. It should be noted that on a single-core CPU, you need a preemptive scheduler (that is, constantly interrupting one thread through the clock and running other threads). Otherwise, spin locks cannot be used on a single CPU, because a spinning thread will never give up CPU.

Spin lock has less overhead, and generally does not actively generate thread switching in multi-core systems, so it is suitable for programming methods such as asynchronous and cooperative programs to switch requests in user mode, but if the locked code takes too long to execute, the spin thread takes up CPU resources for a long time, so the spin time and the locked code execution time are proportional to each other. We need to know this clearly.

The use level of spin lock is similar to that of mutex lock, but the implementation level is completely different: when locking fails, mutex lock is dealt with by "thread switching" and spin lock by "busy waiting".

Both of them are the most basic way of handling locks, and more advanced locks will choose one of them to implement. For example, read-write locks can be implemented either by mutual exclusion or based on spin locks.

Read-write lock: is there a priority distinction between reading and writing?

We can also know from the literal meaning of read-write lock that it consists of "read lock" and "write lock". If you only read shared resources, use "read lock" to add locks, and if you want to modify shared resources, use "write locks" to add locks.

Therefore, read-write locks are suitable for scenarios where read and write operations can be clearly distinguished.

Read-write locks work as follows:

When the "write lock" is not held by the thread, multiple threads can hold the read lock concurrently, which greatly improves the access efficiency of the shared resource, because the "read lock" is used to read the shared resource. so multiple threads holding read locks at the same time will not destroy the data of shared resources.

However, once the "write lock" is held by the thread, the acquisition of the read lock by the reader thread will be blocked, and the acquisition of the write lock by other writing threads will also be blocked.

Therefore, a write lock is an exclusive lock because only one thread can hold a write lock at any one time, similar to mutex and spin locks, while a read lock is a shared lock because a read lock can be held by multiple threads at the same time.

Knowing how read-write locks work, we can find that read-write locks can give full play to their advantages in the scenario of reading more and writing less.

In addition, according to the implementation, read-write locks can be divided into "read-first locks" and "write-first locks".

The read priority lock expects that the read lock can be held by more threads in order to improve the concurrency of the reader thread. The way it works is: when the reader thread A holds the read lock first, the writer thread B will be blocked when it acquires the write lock. And in the blocking process, the subsequent reader thread C can still successfully acquire the read lock. Finally, the writer thread B can not successfully acquire the read lock until the reader thread An and C release the read lock. As shown below:

The write priority lock is the priority service writer thread, which works as follows: when the reader thread A holds the read lock first, the writer thread B will be blocked when it acquires the write lock, and in the blocking process, the subsequent reading thread C will fail to acquire the read lock, so the reading thread C will be blocked in the operation of acquiring the read lock, so that as long as the reader thread A releases the read lock, thread B can successfully acquire the read lock. As shown below:

Read first locks are better for reader thread concurrency, but not without problems. Let's imagine that if the reader thread acquires the read lock all the time, the writer thread will never acquire the write lock, which leads to the "hunger" of the writer thread.

The write priority lock ensures that the writer thread will not starve to death, but if the writer thread acquires the write lock all the time, the reader thread will also starve to death.

Since the other party may starve to death regardless of the priority read lock or write lock, then we will not take sides and have a "fair read-write lock".

A relatively simple way to make a fair read-write lock is to queue up the threads that acquire the lock, both the writer thread and the reader thread can be locked according to the first-in-first-out principle, so that the reading thread can still be concurrent and there will be no hunger.

Mutex and spin locks are the most basic locks, and read-write locks can be implemented by selecting one of these two locks according to the scenario.

Optimistic lock and pessimistic lock: what is the difference between the attitude of doing things?

The mutexes, spin locks and read-write locks mentioned earlier are all pessimistic locks.

Pessimistic lock is more pessimistic because it thinks that multi-threads have a high probability of modifying shared resources at the same time, so conflicts are easy to occur, so lock them before accessing shared resources.

On the contrary, if multiple threads have a low probability of modifying shared resources at the same time, optimistic locks can be used.

Optimistic lock works optimistically. It assumes that the probability of conflict is very low. It works by first modifying the shared resource, and then verifying whether there is any conflict during this period of time. If no other thread is modifying the resource, then the operation is completed. If another thread is found to have modified the resource, abandon the operation.

How to retry after giving up is closely related to the business scenario. Although the cost of retry is high, it is acceptable if the probability of conflict is low enough.

It can be seen that the optimistic attitude is to change the resources first, regardless of the three, seven and twenty-one. In addition, you will find that the optimistic lock is not locked all the way, so it is also called lock-free programming.

Here is an example of a scenario: online documentation.

We all know that online documents can be edited by multiple people at the same time, and if pessimistic locks are used, as long as one user is editing the document, other users will not be able to open the same document, which is certainly a bad user experience.

That enables multiple people to edit at the same time, which actually uses an optimistic lock, which allows multiple users to open the same document for editing, and then verify whether the modified content conflicts after editing and submitting.

What is a conflict? Here is an example, for example, user A first edits the document in the browser, and then user B opens the same document in the browser for editing, but user B submits changes more than user A, and user A does not know the process. When A submits the modified content, then there will be a conflict between An and B where the parallel changes will occur.

How does the server verify that there is a conflict? The general plan is as follows:

Because the probability of conflict is relatively low, let the user edit the document first, but the browser will record the document version number returned by the server when downloading the document.

When the user submits the modification, the request sent to the server will be accompanied by the original document version number. After receiving it, the server compares it with the current version number. If the version number is the same, the modification is successful, otherwise the submission fails.

In fact, our common SVN and Git also use the idea of optimistic lock, first let the user edit the code, and then when submitting, use the version number to determine whether there is a conflict, where there is a conflict, we need to modify it ourselves and then resubmit it.

Optimistic locking removes the operation of locking and unlocking, but in the event of a conflict, the cost of retry is very high, so optimistic locking is considered only in scenarios where the probability of conflict is very low and the cost of locking is very high.

Summary

In the development process, the most common is the mutex lock. When the mutex lock fails, it will be dealt with by "thread switching". When the failed thread locks again, there will be two thread context switching costs. The performance loss is relatively large.

If we clearly know that the execution time of the locked code is very short, then we should choose the spin lock with less overhead, because when the spin lock fails, it will not actively generate thread switching, but will wait until the lock is acquired. then if the execution time of the locked code is very short, the busy waiting time is correspondingly short.

If you can distinguish between read and write scenarios, then the read-write lock is more appropriate, which allows multiple reading threads to hold the read lock at the same time, improving read concurrency. According to whether the reader is partial to the reader or the writer, it can be divided into read priority lock and write priority lock. The read priority lock has strong concurrency, but the writer thread will starve to death, while the write priority lock will serve the writer thread first, and the reader thread may starve to death. In order to avoid the problem of hunger, there is a fair read-write lock, which queues the thread requesting the lock and ensures that the thread is locked on the principle of first-in, first-out. This ensures that some thread will not starve to death and is more versatile.

Mutex and spin locks are the most basic locks, and read-write locks can be implemented by selecting one of these two locks according to the scenario.

In addition, mutex, spin lock, read-write lock all belong to pessimistic lock. Pessimistic lock thinks that when concurrent access to shared resources, the collision probability may be very high, so you need to add locks before accessing shared resources.

On the contrary, if the collision probability of concurrent access to shared resources is very low, optimistic locks can be used. It works by not locking the shared resources first, and then verifying whether there is any conflict during this period of time after modifying the shared resources. If no other thread is modifying the resource, then the operation is completed. If other threads are found to have modified the resource, give up the operation.

However, once the probability of conflict increases, it is not suitable to use an optimistic lock because it is very expensive to retry to resolve the conflict.

No matter what kind of lock is used, the scope of our locking code should be as small as possible, that is, the locking granularity should be small, so that the execution speed will be faster. Then, if you use the right lock, it will speed up quickly.

At this point, I believe you have a better understanding of "how to understand the application scenarios of mutex, spin lock, read-write lock, pessimistic lock and optimistic lock". Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.