概述
Postgresql中的大锁很多，其中ProcArrayLock和XactSLRULock使用了无锁队列优化（PG中XID的分发也可以用这种机制优化，高压场景下效果不错）。
- ProcArrayLock
- 优化前：事务提交清理proc的xid，所有进程争抢ProcArrayLock（PG的锁机制会用sem排队）。
- 优化后：第一个向队列加入元素的proc为leader，后续的proc使用cas将要做的加入队列，由leader统一做。
- XactSLRULock
- 优化前：写CLOG时，不同进程争抢XactSLRULock（PG的锁机制会用sem排队），拿到锁才有资格写SLRU页面。
- 优化后：第一个向队列加入元素的proc为leader，后续的proc使用cas将要做的加入队列，由leader统一做。
关于XactSLRULock请参考《Postgresql源码（101）深入分析clog组提交（clog group updates）》
本篇只精简CAS部分的实现，具体请参考上面文章。
Postgresql中的CAS无锁队列逻辑总结
PG中CAS无锁队列最简代码（所有变量为int）
ProcArrayGroupClearXid......nextidx = pg_atomic_read_u32(&procglobal->procArrayGroupFirst);while (true){pg_atomic_write_u32(&proc->procArrayGroupNext, nextidx);if (pg_atomic_compare_exchange_u32(&procglobal->procArrayGroupFirst,&nextidx,(uint32) proc->pgprocno))break;}
pg_atomic_compare_exchange_u32为PG的CAS实现，在X86下使用汇编lock锁总线cmpxchgl实现：
static inline bool
pg_atomic_compare_exchange_u32_impl(volatile pg_atomic_uint32 *ptr,uint32 *expected, uint32 newval)
{char ret;/** Perform cmpxchg and use the zero flag which it implicitly sets when* equal to measure the success.*/__asm__ __volatile__(" lock \n"" cmpxchgl %4,%5 \n"" setz %2 \n"
: "=a" (*expected), "=m"(ptr->value), "=q" (ret)
: "a" (*expected), "r" (newval), "m"(ptr->value)
: "memory", "cc");return (bool) ret;
}
pg_atomic_compare_exchange_u32的逻辑比较简单：
- 1参一定赋值给2参nextidx：nextidx = procArrayGroupFirst
- 3参可能赋值给1参procArrayGroupFirst：procArrayGroupFirst = pgprocno（如果1参等于2参）
实例
考虑ProcArrayGroupClearXid三并发进入ProcArrayGroupClearXid函数的场景：
进程一：进入前
procArrayGroupFirst -----> invalid <----- nextidx
第一次进入CAS nextidx和procArrayGroupFirst都等于invalid，所以CAS返回true，并且参1procArrayGroupFirst更新为procno1。（nextidx记录procArrayGroupFirst的旧值，也就是队列原来的头部）
invalid <----- nextidx^| procArrayGroupNext |
procArrayGroupFirst -----> procno1
进程二：CAS后
invalid^| procArrayGroupNext | procno1 <----- nextidx^| procArrayGroupNext |
procArrayGroupFirst -----> procno2
进程三：CAS
invalid^| procArrayGroupNext | procno1^| procArrayGroupNext | procno2 <----- nextidx^| procArrayGroupNext |
procArrayGroupFirst -----> procno2
这样就通过CAS形成了一个无锁队列，其中队列头指针procArrayGroupFirst，队列关系由procArrayGroupNext串联，nextidx指向队列前一个元素。
因为CAS保证了compare 和 swap的原子性，所以pg_atomic_compare_exchange_u32不会出现以下场景：
- 比较完了相同，但swap时被别的进程改为不同了。
- 比较完了不同，但swap时被别的进程改为相同了。
综上，就是Postgresql中使用CAS实现无锁队列的方法。
