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

This article mainly introduces the relevant knowledge of how to achieve STL container, the content is detailed and easy to understand, the operation is simple and fast, and has a certain reference value. I believe you will gain something after reading this article on how to achieve STL container. Let's take a look at it.

The formal definition of an unlocked object (lock-free object) is as follows [Her91]: to determine whether a shared object is of lock-free type (non-blocking object) by ensuring that some threads complete an operation in a limited number of system steps, regardless of the results of other threads (even if other thread operations are not successful). A more stringent non-waiting object (wait-free object) is defined as determining whether an object is non-waiting, depending on whether each thread completes the operation on the object in a limited number of steps. The condition of no lock is that at least one thread is guaranteed to complete the task, while the more stringent non-waiting condition is to ensure that all threads can complete the task successfully. Linearization (linearizability) also has a theoretical definition of competitive data structure [Her90]. As a standard, it plays an important role in verifying the correctness of lock-free algorithms. In short, whether the algorithm is linearized depends on whether the result of the operation after the completion of the algorithm is obvious, which is self-evident. For example, as long as the insert function is complete, the result of the list insert operation is obvious. It sounds stupid, but no one can think of an algorithm that does a list insertion, but it's not linearized. For example, various types of caches may violate this feature: we first place a new element in the cache instead of inserting it directly, and then command other threads to "insert this element in the cache into the list" until it is inserted. Or we do an insert only when there are a considerable number of elements in the cache. So after the insert function is executed, we still can't guarantee that this element is in the list. What is certain is that this element will be inserted into the list sooner or later.

Here is a very simple code implementation:

Struct Node {

Node * m_pNext

}

Class queue {

Node * m_pHead

Node * m_pTail

Public:

Queue (): m_pHead (NULL), m_pTail (NULL) {}

Void enqueue (Node * p)

{

P-> m_pNext = m_pTail

M_pTail = p

If (! m_pHead)

M_pHead = p

}

Node * dequeue ()

{

If (! m_pHead) return NULL

Node * p = m_pHead

M_pHead = p-> m_pNext

If (! m_pHead)

M_pTail = NULL

Return p

}

}

It can be written even more briefly, which is the implementation of the classic lock-free Michael&Scott queue algorithm. It looks like joining the team and getting out of the right way (the same as pushing the stack and popping up). (the code is a simplified version of the libcds library class cds::intrusive::MSQueue)

Bool enqueue (value_type& val)

{

Node_type * pNew = node_traits::to_node_ptr (val)

Typename gc::Guard guard

Back_off bkoff

Node_type * t

While (true) {

T = guard.protect (m_pTail, node_to_value ())

Node_type * pNext = t-> m_pNext.load (memory_model::memory_order_acquire)

If (pNext! = null_ptr ()) {

/ / Tail is misplaced, advance it

M_pTail.compare_exchange_weak (t, pNext, memory_model::memory_order_release)

CDS_ATOMIC::memory_order_relaxed)

Continue

}

Node_type * tmp = null_ptr ()

If (t-> m_pNext.compare_exchange_strong (tmp, pNew, memory_model::memory_order_release)

CDS_ATOMIC::memory_order_relaxed))

{

Break

}

Bkoff ()

}

+ + m_ItemCounter

M_pTail.compare_exchange_strong (t, pNew, memory_model::memory_order_acq_rel)

CDS_ATOMIC::memory_order_relaxed)

Return true

}

Value_type * dequeue ()

{

Node_type * pNext

Back_off bkoff

Typename gc::template GuardArray guards

Node_type * h

While (true) {

H = guards.protect (0, m_pHead, node_to_value ())

PNext = guards.protect (1, h-> m_pNext, node_to_value ())

If (m_pHead.load (memory_model::memory_order_relaxed) = h)

Continue

If (pNext = = null_ptr ())

Return NULL; / / empty queue

Node_type * t = m_pTail.load (memory_model::memory_order_acquire)

If (h = = t) {

/ / It is needed to help enqueue

M_pTail.compare_exchange_strong (t, pNext, memory_model::memory_order_release)

CDS_ATOMIC::memory_order_relaxed)

Continue

}

If (m_pHead.compare_exchange_strong (h, pNext)

Memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed))

{

Break

}

Bkoff ()

}

-- m_ItemCounter

Dispose_node (h)

Return pNext

}

This is a very complex algorithm, the same one-way linked list. But even if you make a general comparison, you can see some of the characteristics of unlocked queues. In the unlocked queue, we can find the following description:

Infinite loop: we will try to do this later, which is a typical pattern that implements the atomic operation compare_exchange

The security of local variables (guards) needs to rely on the secure memory recovery method in the lock-free algorithm. In this case, the risk pointer (Hazard Pointers) method

Atomic primitives using the Clear11 standard: load, compare_exchange, and memory fences memory_order_xxx

Helping: a method that is widely used in lock-free algorithms, especially in scenarios where one thread helps other threads execute tasks

Compensation strategy (functor bkoff): this is not necessary, but it can relieve the pressure on the processor when there are many connections, especially if multiple threads call queues one by one.

This is the end of the article on "how to implement the STL container". Thank you for reading! I believe you all have a certain understanding of "how to implement STL container". If you want to learn more, you are welcome to follow the industry information channel.

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.