Shulou(Shulou.com)06/02 Report--

This article introduces the knowledge of "how to understand the conditional synchronization mode in multi-core programming". Many people will encounter such a dilemma in the operation of actual cases. next, let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

In multithreaded programming, when operating on shared resources, synchronization (usually locks or atomic operations) is needed to protect against data contention. Unfortunately, synchronization operations are very expensive, such as adding an integer variable, then the cost of synchronization operation is more than 100 times that of addition operation.

Is there any way to reduce the cost of this synchronization operation? If faster locks or faster atomic operations can be designed, this overhead will naturally be reduced. According to the current technology, the fastest atomic operation is also hundreds of times more time-consuming than the ordinary addition operation, so it is very difficult to start from this aspect.

So is it possible to reduce the overhead of synchronization operations from the perspective of software algorithms? The answer is yes, the basic idea is to reduce the number of times to use synchronization, for example, the original need to use synchronization 1000 times, now it is changed to use synchronization under certain conditions, only 10 times, then the cost of synchronization is reduced by 100 times, and the efficiency is greatly improved. Let's start with an example of a shared queue.

A common shared queue is usually implemented using locks, of course, it is also implemented with CAS atomic operations. Here we only discuss shared queues implemented with locks.

In shared queues with lock protection, locks are usually used for queue inbound and dequeuing operations. A typical dequeue operation pseudo code using lock protection is as follows:

Template class Locked_DeQueue (T & data) {Lock (); DeQueue (data); / / call the serial dequeue operation Unlock ();}

When using the Locked_DeQueue () function above, a lock operation occurs each time it is called. In fact, the locking operation is not always required, such as when the queue is listed as empty, there is actually no need for out-of-queue operation, there are certain methods that can be taken to avoid locking operation, but using the above Locked_DeQueue () function can not avoid locking operation, which needs to be improved on the above function.

One of the easiest aspects to think of is to determine whether the queue is empty or not, and then use lock protection to dequeue if not. The code is as follows:

Template class Locked_DeQueue_a (T & data) {If (! IsEmpty ()) {Lock (); DeQueue (data); / / call the serial dequeue operation Unlock ();}}

A key point of the Locked_DeQueue_a () function above is that the IsEmpty () function must not use locking operations, otherwise instead of reducing the synchronization overhead, it nearly doubles the synchronization overhead.

How to make the IsEmtpy () function without lock operation? take the ring queue implemented by the array as an example, when judging whether the queue is empty, the basic method is to judge whether the first pointer of the queue is equal to the pointer at the end of the queue. The pseudo code is as follows:

INT IsEmpty () {Lock () if (first pointer = = end pointer) {Unlock (); return 1; / / Null} else {Unlock (); return 0; / / non-null}}

Since the head and tail pointers of the queue will change when entering or leaving the team, so lock protection is needed in the above IsEmpty () function, so how to remove this layer of lock protection?

The basic method is to set a flag variable EmptyFlag. When the queue is empty, the value of the flag variable is set to 1 when the queue is empty, and 0 when the queue is not empty. In this way, we can determine whether the queue is empty or not by EmptyFlag a single variable, and the read and write of a single variable can be realized by atomic operations, so that there is no synchronous operation like normal operations.

The following is the dequeue operation implemented using the EmptyFlag variable.

Template class

Locked_DeQueue_b (T & data)

{

If (EmptyFlag)

{

Return

}

Lock ()

Before if (! EmptyFlag) / / Lock (), other threads may have modified the flag

{

DeQueue (data); / / call serial dequeue operation

If (line head pointer = = line tail pointer)

{

/ / after leaving the queue, the queue becomes empty and atomic operation is used to set EmptyFlag to 1.

AtomicIncrement & EmptyFlag)

}

}

Unlock ()

}

The empty function of the queue can be used in the following implementation that does not require synchronization at all.

INT IsEmpty () {return EmptyFlag;}

From the implementation of the Locked_DeQueue_b () function, we can see that if the queue is originally empty, it only judges one EmptyFlag and returns, does not call the lock operation, reduces the number of synchronization, and in the IsEmpty () function, there is no need to use synchronization at all, which is very effective for those scenarios that need to frequently judge whether the queue is empty.

For example, for dynamic task scheduling, assume that a common shared queue with locks is used. When a thread private queue is empty, you need to steal the tasks in the shared queue of other threads. If the stolen queue is empty, a lock operation occurs, and then you need to steal another queue of tasks. If the queue is still empty, you need another lock operation, and multiple locking and unlocking may occur in the task acquisition operation. Through the conditional synchronization method mentioned above, when stealing a task, it can be achieved with a lock operation.

The conditional synchronization mode mentioned above is very suitable for situations with state machine nature, using synchronization only when state switching occurs (such as switching between empty or non-empty states in the queue), and reducing the use of synchronization by operating on state variables (such as EmptyFlag) instead of other non-state variables (such as queue head pointer and queue end pointer).

This is the end of the content of "how to understand conditional synchronization mode in multicore programming". Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.