怎样协调无锁异步队列的多个写入者
代码来了，为了方便显示逻辑，用c语言方式书写：// 将两次位置操作：查找和完成，放在一个原子类型中，保证更新不会冲突typedef struct { unsigned int index : 16; unsigned int ready : 16;} write_seed_t;union { write_seed_t write_seed; atomic_uint32_t atomic_write_seed;};// 环形缓冲区中保存的是指针，可以以原子方式更新，写就是置值，读就是置空// 缓冲区的长度不应超过上述定义的index字长的一半，即16位的一半void *buf;void put(void *ptr) // 假定指针值最后一位为0，即偶数{ union { write_seed_t seed; atomic_uint32_t atomic_seed; }; atomic_uint32_t atomic_expected; ptr \u0026amp;= 1; // 指针添加标记，值加1变成奇数 // 保存标记后指针到缓冲区内第一个空的位置上 do { atomic_expected = atomic_seed = atomic_load(\u0026amp;atomic_write_seed); if (seed.index - read_seed.index == BUF_LEN) { ; // TODO: 缓冲区已满 }stage_1: // 找出用于保存的第一个空位置，可以抢占 if (atomic_load(\u0026amp;buf) != NULL) { seed.index ++; if (!atomic_cas(\u0026amp;atomic_write_seed, atomic_expected, atomic_seed)) continue; } } while (atomic_cas(\u0026amp;buf, NULL, ptr));stage_2: // seed的ready部分更新，如果失败，表明有后续的put操作已经跟进，会帮助推进，故无需理会 // 此次操作是必要的，但需要回避此刻put操作挂起时，延迟执行后的ABA风险 seed.ready = seed.index; atomic_cas(\u0026amp;atomic_write_seed, atomic_expected, atomic_seed);stage_3: // 去除缓冲区内指针标记，此处可以与某次get操作竞争，get操作会把指针置为NULL同时不改变标记位，即如果此处挂起的话，留下的会是NULL + 1 do { ptr = atomic_load(\u0026amp;buf); assert(ptr \u0026amp; 1 != 0); } while (!atomic_cas(\u0026amp;buf, ptr, ptr - 1));}这里的预置条件是缓冲区长度受限，然后指针的值的最后一位为0，即地址双位对齐。因为所有操作不能在一次原子操作中完成，所以分成三个阶段，stage_1，stage_2，stage_3，其中前后两个阶段都是典型的无锁cas循环方式。问题的核心在于stage_2中断的话，put操作延迟任意长时间后，再执行可能存在ABA问题，这里通过将指针加上标记后，使得只有经过stage_3，put操作完全结束后，该缓冲区位置才可能变成NULL，也就是stage_1中的index不会重复到一个相同的值上，来避免这个问题。带来的副作用就是如果put线程真的挂起的话，缓冲区中会遗留下一些NULL+1的空洞，但不会阻断其他线程的执行。get操作这里就略过了，应该不难实现。注：（1）以环形缓冲区方式实现无锁队列并不是一个好的办法，因为缓冲区大小不可变，存在读空写满的可能，而后者可以在动态队列实现避免。动态无锁队列实现并不难，但为了避免ABA问题，遗留下了内存回收的难题，这里其实也有内存回收的问题，但不难解决。（2）其实在这种限制下，最简单的做法是直接循环整个缓冲区，put操作看到空的就放进去，get操作看到非空就取出来，这几乎是wait-free的，但时间复杂度是O(n)（n为缓冲区长度）的。所以有的时候高级未必就一定是好，还是要根据问题和要求分析。（3）XiYang的实现中的想法很好，提高了操作的并发性，我也曾试图在算法中容纳这种想法，但会变得非常复杂，而且原子操作的字长变得捉襟见肘，有兴趣的可以自行考虑。（4）如果采取类似（2）的做法，协调好读进程的话，上述算法中ABA风险也几乎可以忽略，即无需使用指针标记位和第二阶段的操作。（5）在stage_1也存有ABA问题，和（4）一样没什么风险，这里忽略了，但也可以修复，只是更加麻烦一些，留待有兴趣的自行改进。（6）代码细节仍有优化空间，但跟无锁关系不大，XiYang提到不想分配内存，这几乎是可以避免的（参考注1），留待各位自行思考。
推荐阅读
- 聪明人养花，这3种“花”怎样也要养一盆，每年能省不少医药费
- 互联网怎样解决“家政服务上门速度慢”的问题
- 怎样看待从1月8号起，QQ钱包开始提现收费
- 银行it人怎样转型
- 汽车|冬天怎样让车内温度快速升高？座椅加热的最佳使用方式二，外循环的作用总结
- 怎样进入通信行业
- 怎样评价扶他柠檬茶的小说《云养汉》的结尾
- 怎样成为一名合格的Python程序员?
- 怎样评价华为、诺基亚、中兴中标中国移动高端路由交换设备扩容集采
- 怎样评价类似前橙会、百老汇、南极圈这样类型的离职帮抱团，对企业的积极意义和消极意义