0

以下是 Peterson 的 2 线程锁定算法的通用版本，允许“n”个线程/进程竞争临界区。

基本上有“n”个级别和“n”个线程。处于非活动状态或在非临界区区域中执行的线程处于级别 0。级别 n-1 是临界区。每个线程/进程在进入临界区之前必须跨越 n-1 级。

有 2 个数组，级别 [n] 和受害者 [n]。第一个数组由线程的threadId索引，entry level[i]存储threadId为'i'的线程的当前级别。第二个数组由级别编号索引，条目victim[i] 存储最近进入级别“i”的线程的threadId。

level[] 的所有元素都初始化为 0。victim[] 没有特定的初始化。

1    void lock()
2    {  int me = ThreadID.get();
3       for (int i = 1; i < n; i++)
4       { level[me] = i;
5         victim[i] = me;
6         while ((∃k != me) (level[k] >= i && victim[i] == me)) ;
7       }
8    }
9   
10   void unlock()
11   {  int me = ThreadID.get();
12      level[me] = 0;
13   }

该代码直接摘自 Maurice Herlihy 和 Nir ​​Shavit 所著的《多处理器编程的艺术》一书。

问题是代码似乎不满足互斥属性！

推理：- 第 6 行暗示，一个线程将保持在一个级别循环，直到有一些线程处于相同或更高级别，并且线程本身是最近进入它当前所在级别的线程。此外，只有一个线程可以保持在一个水平。如果第二个线程到达同一级别，那么第一个线程的“victim[i] == me”表达式将变为假，因此将被推到下一个级别。

现在，如果每个级别都有一个线程，并且级别 0 的线程尝试前进到级别 1。这会将级别 1 的线程推到级别 2，因为它不再是级别 1 的受害者。因此会有涟漪效应，每个线程将被下推一级，导致第 n-2 级的线程也进入其临界区！！

那么代码实际上是错误的还是我解释了什么错误？

4

1 回答 1

0

n 是线程数，n 是级别数，级别以 0 开头，n-1 级别是临界区

如果所有级别都填充了一个线程，则不会有任何其他线程进入级别 0，即第一级。所以它永远不会发生。

例如，如果线程数和级别数为 3。开始时所有线程都处于级别 0，并且两个线程可以前进到下一个级别，并且必须根据条件等待 while ((∃k != me) (level[ k] >= i && 受害者[i] == me)) ; 并且从这两个线程中的一个进入关键部分的级别 2。

现在每个级别都填充了一个线程，唯一可能的情况是临界区中的线程调用 unlock() 通过使其级别 = 0 然后只有其他线程可以继续。

点是线程数等于级别数

于 2014-01-03T05:49:37.237 回答