使用3个PetersonLocks的数组来同步4个进程

Question

假设我们有如下的PetersonLock类：

class PetersonLock {
     AtomicBoolean flag[] = new AtomicBoolean[2];
     volatile int victim;

     public void Acquire(int id) {

         flag[id].set(true);
         victim = id;
         while (flag[1-id].get() && victim == id);
    }

    public void Release(int id) {
         flag[id].set(false);
    }
}

其中id为1或0。我现在有下面的类来分层地使用3个PetersonLocks来处理4个进程。

class Lock4Pete{

    PetersonLock[] lock = new PetersonLock[3];

    public void Acquire(int id) {

         lock[0].Acquire(id/2);
         lock[1+id/2].Aquire(id%2);
    }

    public void Release(int id) {

         lock[1+id/2].Release(id%2);
         lock[0].Release(id/2);
    }
  }

其中id是0、1、2或3。

我不明白这背后的想法，我也不知道如何修复这段代码。我不知道他们想在这里做什么。为什么4个进程需要3个锁?为什么每个进程都可以使用锁

如果能得到一些帮助，我们将不胜感激。这不是家庭作业，而是一个我不太理解的练习。

Answer 1

这4个线程被分成2个箱，每个箱包含2个线程。id/2指定线程所属的bin，id%2指定线程在bin中的索引。

让我们重写代码，将id/2和id%2作为单独的变量进行处理。

class Lock4Pete {

    // This lock determines the active bin.
    PetersonLock masterLock = new PetersonLock;

    // Each of these locks guards the corresponding bin.
    PetersonLock[] binLocks = new PetersonLock[2];

    public void Acquire(int bin, int index) {
        // After this line is executed in one of the threads, 
        // any thread from a *different* bin will have to wait 
        // until this thread calls masterLock.Release(bin);  
        // before it can execute masterLock.Acquire(another_bin);
        masterLock.Acquire(bin);

        // It is possible that more than one thread reaches this point 
        // simultaneously, but they are guaranteed to be from the same bin.
        // Now we only need to make sure that threads from that bin can 
        // neither acquire the lock simultaneously nor come to a deadlock.

        // After this line is executed, 
        // any thread from the *same* bin will have to wait until 
        // this thread calls binLocks[bin].Release(index); 
        // before it can execute binLocks[bin].Aquire(another_index);
        binLocks[bin].Aquire(index);

        // Thus, only one thread at a time can reach the end of this
        // method and acquire the lock.
    }

    public void Release(int bin, int index) {
         binLocks[bin].Release(index);
         masterLock.Release(bin);
    }
}