共计 5448 个字符，预计需要花费 14 分钟才能阅读完成。
锁的意义
原子性 + 可见性
同一时间，只有一个线程执行锁中代码 + 锁内读在锁前代码执行完，写在锁开释前可见
原子
操作
自身内核的原子是通过原子指令实现的 https://code.woboq.org/linux/…
原子库实现的一下办法能够带内存屏障来增强可见性。
- store // 原子写
- load // 原子读
- exchange // 原子替换
-
compare_exchange_weak //compare and set 性能更高，然而两个值一样时可能会意外返回 false。a.compare_exchange_weak(&expect,val)。if a=expect，则 a.store(v), else expect=a, 返回 false
bool compare_exchange_weak (T& expected, T val, memory_order sync = memory_order_seq_cst) volatile noexcept; Compares the contents of the atomic object's contained value with expected: - if true, it replaces the contained value with val (like store). - if false, it replaces expected with the contained value . __asm__ __volatile__("": : :"memory"); inline void* Acquire_Load() const { void* result = rep_; MemoryBarrier(); return result; } inline void Release_Store(void* v) {MemoryBarrier(); rep_ = v; } -
compare_exchange_strong
2. 内存屏障
typedef enum memory_order { memory_order_relaxed, // 不对执行程序做保障 memory_order_acquire, // A load operation with this memory order performs the acquire operation on the affected memory location: no reads or writes in the current thread can be reordered before this load. All writes in other threads that release the same atomic variable are visible in the current thread (see Release-Acquire ordering below) memory_order_release, // A store operation with this memory order performs the release operation: no reads or writes in the current thread can be reordered after this store. All writes in the current thread are visible in other threads that acquire the same atomic variable (see Release-Acquire ordering below) and writes that carry a dependency into the atomic variable become visible in other threads that consume the same atomic (see Release-Consume ordering below). memory_order_acq_rel, // 同时蕴含 memory_order_acquire 和 memory_order_release memory_order_consume, // 本线程中, 所有后续的无关本原子类型的操作, 必须在本条原子操作实现之后执行 memory_order_seq_cst // 全副存取都按程序执行 } memory_order;无锁队列
template struct Node {T t; shared_ptr<Node> next;}; atomic<shared_ptr<Node>> head; public: slist() =default; ~slist() =default; class reference { shared_ptr p; public: reference(shared_ptr<Node> p_) : p{_p} {} T& operator*() { return p->t;} T* operator->() { return &p->t;} }; auto find(T t) const {auto p = head.load(); while (p && p->t != t) p = p->next; return reference{move(p)}; void push_front(T t) {auto p = make_shared<Node>(); p->t = t; p->next = head; while (head.compare_exchange_weak(p->next, p)) {}} void pop_front() {auto p = head.load(); while (p && !head.compare_exchange_weak(p, p->next)) {}} };
### mutex
- std 的 mutex =>pthread_mutex_lock
linux 的 glibc 的 pthread 包分好几种，一般的就调 futex。自适应的也会先 spin。
循环调用 CAS,wait 在 futex
cmpxchgl 查看 futex（也就是__lock 成员）是否为 0（示意锁未占用），如是，赋值 1（示意锁被占用） - pthread_cond_wait:
也是先开释 mutex。而后 futex 在 cond 上（lll_futex_wait (&cond->__data.__futex, futex_val, pshared);）而后再锁 mutex - 更多 pthread 的锁：https://casatwy.com/pthreadde…
利用
boost 和 std 都有。boost 的效率说是比 std 高一些
定义：mutex 对象 boost::shared_mutex, boost::mutex
lock_guard,shard_lock,unique_lock 都是模板类，用来治理 mutex
boost::shared_lock<T> 中的 T 只能是 shared_mutex 类
unique_lock<T> 中的 T 能够为 mutex 类中的任意一种，如果为 shared_mutex，那么 boost::unique_lock<boost::shared_mutex> 类的对象构造函数结构时，会主动调用 shared_mutex 的 shared_lock 办法，析构函数里，会主动调用 shared_mutex 的 shared_unlock 办法。如果是 boost:: unique_lock<boost::mutex>，则别离主动调用 lock 和 unlock 办法。
读写锁实现：
typedef boost::shared_lock<boost::shared_mutex> readLock;
typedef boost::unique_lock<boost::shared_mutex> writeLock;
boost::shared_mutex rwmutex;
用的时候：
readLock(rwmutex)
互斥锁：
typedef boost::unique_lock<boost::mutex> exclusiveLock;
boost::mutex m;
exclusiveLock(m)
tips
一写多读 多写多读 对于 coredump 这种线程平安都是因为地址拜访，比方要读的起始被删除了，数据的 reserve 啊，map 的树调整啊，rehash 啊，间接删除之类的。而独自的 ++ 这种是不须要的。
还有是可见性和原子性。多写不加锁（没有原子性，可见性的保障）会指令乱序笼罩，比方 ++ 的次数变少，读可能会读到旧数据，可能作为 if 判断不会立刻失效因为在寄存器和另一个 cpucache 中。
对于 volitale 作用就是禁止编译器优化，所以取值不会走寄存器。控制不了别的，所以前面的指令还是会乱序到他后面，cpu 还是有 cpucache，并且 cpucache 的 MSEI 没有指令加锁也不会原子性，依然会呈现读不到的状况。用内存屏障或者老老实实用原子，用锁，缩小锁抵触
内核原语（spinlocks，mutexes，memory barriers 等）确保了并发访问共享数据的平安，内核原语同时阻止了不须要的优化。如果能正确的应用这些同步原语，当然同时也就没有必要应用 volatile 类型。
https://lwn.net/Articles/233482/
barrier();
禁止编译器指令重排。不应用寄存器的值，从内存中 load
(https://zhuanlan.zhihu.com/p/…
spinlock
用户态和内核解决 spin 差别很大, 内核能管制特定 cpu, 所以逻辑会简单很多
用户态 spin 还会间接陷入内核阻塞, 内核可不会，那就是真的死循环, 必须思考性能
本人写 spinlock
pthread 有 spin
while (!condition) {if (count > xxx) break;
count++;
\_\_asm\_\_ volatile（"pause");
}
mutex();内核 spin
while (lock->locked);
lock->locked = 1; =》不原子 =》while (test_and_set(&lock->locked)); =》while (lock->locked || test_and_set(&lock->locked));
这种写法每次唤醒 lock 会呈现饿死状况
引入 owner 和排队
struct spinlock {
unsigned short owner;
unsigned short next;
};
void spin_lock(struct spinlock *lock)
{unsigned short next = xadd(&lock->next, 1);
while (lock->owner != next);
}
void spin_unlock(struct spinlock *lock)
{lock->owner++;}
在退出 spinlock 时，会 invalid spinlock 导致整个 cpu cache 平稳。=》每个 cpu 本人的构造，用链表链接起来
https://zhuanlan.zhihu.com/p/89058726信号量
信号量
可睡眠，可多个
原来 pthread_mutex 不反对过程，起初也有了，然而不是所有平台都反对。信号量是原来过程
加锁 down: 在自旋锁的爱护下，退出期待列表，解锁，调度进来，回来后获取锁，查看是否 up，up 返回否则循环
解锁 up: 在自旋锁的爱护下，去第一个期待列表，删除，设置 up, 回调
https://zhuanlan.zhihu.com/p/…
pfs 中用来进程同步
ABA
rocksdb 中无所队列 ABA 问题
如果地位 V 存储的是链表的头结点，那么产生 ABA 问题的链表中，原头结点是 node1，线程 2 操作头结点变动了两次，很可能是先批改头结点为 node2，再将 node1（在 C ++ 中，也可是重新分配的节点 node3，但恰好其指针等于曾经开释掉的 node1）插入表头成为新的头结点。
对于线程 1，头结点仍旧为 node1（或者说头结点的值，因为在 C ++ 中，尽管地址雷同，但其内容可能变为了 node3），CAS 操作胜利，但头结点之后的子链表的状态已不可预知。
建设一个全局数组 HP hp[N]，数组中的元素为指针，称为 Hazard pointer，数组的大小为线程的数目，即每个线程领有一个 HP。
约定每个线程只能批改本人的 HP，而不容许批改别的线程的 HP，但能够去读别的线程的 HP 值。
当线程尝试去拜访一个要害数据节点时，它得先把该节点的指针赋给本人的 HP，即通知他人不要开释这个节点。
每个线程保护一个公有链表 (free list)，当该线程筹备开释一个节点时，把该节点放入本人的链表中，当链表数目达到一个设定数目 R 后，遍历该链表把能开释的节点统统开释。
当一个线程要开释某个节点时，它须要查看全局的 HP 数组，确定如果没有任何一个线程的 HP 值与以后节点的指针雷同，则开释之，否则不开释，仍旧把该节点放回本人的链表中。
这个不是和文件持有时，其余不能 delete 是一样的。无锁链表在没有 delete 时候，next 比拟。问题是 CAS 间接取指针比拟啊。
https://www.drdobbs.com/lock-…
这个能够解决开释，相当于保护一个开释队列，先不开释 =。=
然而解决不了如果再申请还是这块内存，CAS 比拟里边值的问题，这个开释能够延时，然而赋值不行啊，还是要带 version 啊。
