自旋锁
- 用
ATOMIC_FLAG_INIT进行了flag的初始化- 它确保了
flag的初始状态是清除（或说“未设置”）状态
- 它确保了
lock调用了test_and_set方法来试图获取锁test_and_set会检查flag的当前值：如果flag是清除状态，则设置它并返回false；如果flag是已设置状态，则返回true- 当某线程首次尝试获取锁时，
flag会被设置，而其它的线程将进入自旋状态，直到锁被释放
unlock用于释放锁flag.clear(std::memory_order_release);- 调用clear方法来清除（或说“重置”）flag，从而释放锁
test_and_set包含了读修改写的过程，所以使用了std::memory_order_acquire- 这个内存序，确保
test_and_set之前的读写操作不会被重新排到test_and_set的后面 - 换句话说，确保
flag被成功修改后，其他线程看到的flag的值以及flag之前的值，都是修改完成的
- 这个内存序，确保
clear这里用了memory_order_release，是因为这是一个写操作- 它保证了这个操作之前的所有当前线程中的写操作对其他线程都是可见，确保其他的这些操作不会被重新排在这个操作的后面
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class spinlock_mutex { std::atomic_flag flag; public: spinlock_mutex() : flag(ATOMIC_FLAG_INIT) { } void lock() { while(flag.test_and_set(std::memory_order_acquire)); } void unlock() { flag.clear(std::memory_order_release); } }; |
无锁线程安全栈
push操作介绍compare_exchange_weak是一个原子操作，它的工作方式是：比较head的当前值是否等于new_node->next（也就是我们之前读取的旧的栈顶）- 如果它们相等，那么
head将被更新为new_node，也就是我们新创建的节点 - 如果不等，那么
new_node->next将被更新为当前的head值，并再次尝试该操作 - 这里使用循环，因为
compare_exchange_weak可能会失败，即使head没有发生变化。因此，需要反复尝试，直到成功为止
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
template<typename T> class lock_free_stack { private: struct node; struct counted_node_ptr { int external_count; node* ptr; }; struct node { std::shared_ptr<T> data; std::atomic<int> internal_count; counted_node_ptr next; node(T const& data_) : data(std::make_shared<T>(data_)), internal_count(0) { } }; std::atomic<counted_node_ptr> head; void increase_head_count(counted_node_ptr& old_counter) { counted_node_ptr new_counter; do { new_counter = old_counter; ++new_counter.external_count; } while (!head.compare_exchange_strong(old_counter, new_counter, std::memory_order_acquire, std::memory_order_relaxed)); old_counter.external_count = new_counter.external_count; } public: ~lock_free_stack() { while(pop()); } void push(T const& data) { counter_node_ptr new_node; new_node.ptr = new node(data); new_node.external_count = 1; new_node.ptr->next = head.load(std::memory_order_relaxed); while(!head.compare_exchange_weak(new_node.ptr->next, new_node, std::memory_order_release, std::memory_order_relaxed)); } std::shared_ptr<T> pop() { counted_node_ptr old_head = head.load(std::memory_order_relaxed); for (;;) { increase_head_count(old_head); node* const ptr = old_head.ptr; if (!ptr) { return std::shared_ptr<T>(); } if (head.compare_exchange_strong(old_head, ptr->next, std::memory_order_relaxed)) { std::shared_ptr<T> res; res.swap(ptr->data); int const count_increase = old_head.external_count - 2; if (ptr->internal_count.fetch_add(count_increase, std::memory_order_release) == count_increase) { delete ptr; } return res; } else if (ptr->internal_count.fetch_add(-1, std::memory_order_relaxed) == -1) { ptr->internal_count.load(std::memory_order_acquire); delete ptr; } } } }; |
无锁线程安全队列
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 |
template<typename T> class lock_free_queue { private: struct node; struct counted_node_ptr { int external_count; node* ptr; }; std::atomic<counted_node_ptr> head; std::atomic<counted_node_ptr> tail; struct node_counter { unsigned internal_count:30; unsigned external_counters:2; }; private: struct node { std::atomic<T*> data; std::atomic<node_counter> count; std::atomic<counted_node_ptr> next; node() { node_counter new_counter; new_counter.interal_count = 0; new_counter.external_counters=2; count.store(new_count); next.ptr = nullptr; next.external_count = 0; } void release_ref() { node_counter old_counter = count.load(std::memory_order_relaxed); node_counter new_counter; do { new_counter = old_counter; --new_counter.internal_count; } while(!count.compare_exchange_strong(old_counter, new_counter, std::memory_order_acquire, std::memory_order_relaxed)); if (!new_counter.internal_count && !new_counter.external_counters) { delete this; } } }; private: static void increase_external_count(std::atomic<counted_node_ptr>& counter, counted_node_ptr& old_counter) { counted_node_ptr new_counter; do { new_counter = old_counter; ++new_counter.external_count; } while(!conter.compare_exchange_strong(old_counter, new_counter, std::memory_order_acquire, std::memory_order_relaxed)); old_counter.external_count = new_counter.external_count; } static void free_external_counter(counted_node_ptr &old_node_ptr) { node* const ptr = old_node_ptr.ptr; int const count_increase = old_node_ptr.external_count - 2; node_counter old_counter = ptr->count.load(std::memory_order_relaxed); node_counter new_counter; do { new_counter = old_counter; --new_counter.external_counters; new_counter.internal_count += count_increase; } while(!ptr->count.compare_exchange_strong(old_counter, new_counter, std::memory_order_acquire, std::memory_order_relaxed)); if (!new_counter.internal_count && !new_counter.external_counters) { delete ptr; } } public: std::unique_ptr<T> pop() { counted_node_ptr old_head = head.load(std::memory_order_relaxed); for (;;) { increase_external_count(head, old_head); node* const ptr = old_head.ptr; if (ptr == tail.load().ptr) { return std::unique_ptr<T>(); } counted_node_ptr next = ptr->next.load(); if (head.compare_exchange_strong(old_head, next)) { T* const res = ptr->data.exchange(nullptr); free_external_counter(old_head); return std::unique_ptr<T>(res); } ptr->release_ref(); } } void push(T new_value) { std::unique_ptr<T> new_data(new T(new_value)); counted_node_ptr new_next; new_next.ptr = new node; new_next.external_count = 1; counted_node_ptr old_tail = tail.load(); for (;;) { increase_external_count(tail.old_tail); T* old_data = nullptr; if(old_tail.ptr->data.compare_exchange_strong(old_data, new_data.get())) { counted_node_ptr old_next = {0}; if (!old_tail.ptr->next.compare_exchange_strong(old_next, new_next)) { delete new_next.ptr; new_next = old_next; } set_new_tail(old_tail, new_next); new_data.release(); break; } else { counted_node_ptr old_next = {0}; if (old_tail.ptr->next.compare_exchange_strong(old_next, new_text)) { old_next = new_next; new_next.ptr = new node; } set_new_tail(old_tail, old_next); } } } }; |
声明：本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！
你可能也喜欢
- ♥ STL_queue06/07
- ♥ WTL 概述03/10
- ♥ macOs 解析mach-o05/11
- ♥ C++11_第四篇12/08
- ♥ C++并发编程_同步并发(Condition_variable)05/21
- ♥ 深度探索C++对象模型一02/09