java - 房间同步 : How to ensure multiple threads are using same node?

Question

(问题链接到维基:http://en.wikipedia.org/wiki/Room_synchronization)

假设有N个NODE类型的资源，用数组表示

 NODE  nodearray[N];

假设有 M 个线程在执行操作(读/写)。当第一个线程到达时，它可以自由选择 N 个资源中的任何一个，但只要第一个线程持有资源编号 x(x 是 0 到 n-1)，第二个线程必须使用相同的 x。

假设我们要实现两个功能

int get();// gets the resource number for the thread and 
void ret();// returns the resource from the thread

知道如何实现吗？

Answer 1

对于您所陈述的问题，我认为您只需要保留一个计数器，指示当前正在使用哪个(单个)资源，以及一个互斥体来使您的所有函数调用原子。

(编辑:我最初在这里有代码，但它几乎与@Ajeet 在我发布此问题前几个小时在他对自己问题的回答中发布的代码相同。所以看看@Ajeet 的回答如果你想要 C 中的代码。)

您提出的房间同步形式不是原作者的想法(link to pdf) .他们需要一个操作，让调用者指定他们想要进入的房间。如果其他人在不同的房间，调用者需要等待。所以在那种情况下我们有:

void enter(int roomnum);  // wait until everyone is out of all rooms other than roomnum
void exit(int roomnum);   // exit roomnum

而且实现更有趣。 (提示:除了上面的三个变量之外，您还需要一个条件变量。)

如果您想知道为什么其中的任何一点有用(我想知道):在我链接到的论文中，他们正在尝试实现相对复杂的可扩展并发算法。他们提出了一种使用票自旋锁解决房间同步问题的方法(第 7 页)。并展示如何使用房间同步问题来实现可扩展的并发堆栈(第 4 页)。 (对并发堆栈的理解是:任意数量的线程使用获取和递增同时推送是可以的，并且任意数量的线程使用获取和递减同时弹出也是可以的，但是你需要确保没有 push 和 pops 同时发生。)