无等待缓冲区填充算法
我有一个恒定宽度 N 的缓冲区，它由两端的多个进程填充 - 每个进程可以同时将 L 元素推送到最左边的空位置，或将 R 元素推送到最右边的空位置。 我使用 CAS 指令同步两个变量（左堆栈顶部和右堆栈顶部）的进程。
保证缓冲区不会溢出，实际上栈顶之间会留出一个元素的空间。我需要的是这些进程中只有一个会报告这个空白空间的位置。
最初我最终必须同时向左侧和右侧推送，因此在向左推送然后向右推送之后，进程可以查看左侧堆栈顶部，将其 + 1 与其最后一次向右推送的位置进行比较，如果这两个相等，则该进程是最后一个进程（缓冲区填满时向右推的最后一个进程获胜）。然而，现在我意识到我不能保证最终双方都推动，所以这个协议不能应用。
您能想到任何足以满足要求的免等待协议吗？我可以通过 CAS 指令使用更多变量，但我无法同时原子地修改或读取多个变量。当然，变量越少越好。
I have a buffer of constant width N which is filled by several processes from both ends - each process can at one moment push L elements to the leftmost empty positions or R elements to the rightmost empty positions.
I synchronize the processes on two variables (left stack top and right stack top) using the CAS instruction.
It is guaranteed that the buffer will not overflow, in fact space for one element between the stacks tops will be left. What I need is that one and only one of these processes will report the position of this empty space.
Originally I had to push both on the left and right side in the end, so after pushing to the left and then to the right the process could look on the left stack top, compare it + 1 to the position of its last right push and if these two were equal, the process was the last one (the last process pushing to the right when the buffer is filled wins). However, now I've realized I cannot guarantee pushing on both sides in the end so this protocol cannot be applied.
Can you think of any wait-free protocol that would suffice? I can use more variables with the CAS instruction, but I cannot atomically modify or read more than one at one moment. Of course, the less variables the better.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论