Filter lock mutual exclusion property

Question

The following is a generalised version of Peterson's 2-thread lock algorithm, allowing 'n' threads/processes to compete for critical section.

Basically there are 'n' levels and 'n' threads. Threads which are inactive or are executing in non critical section region are at level 0. Level n-1 is the critical section. Every thread/process must cross n-1 levels before entering the critical section.

There are 2 arrays, level[n] & victim[n]. The first array is indexed by threadId of a thread, and an entry level[i] stores the current level of a thread with threadId 'i'. The second array is indexed by level number, and an entry victim[i] stores the threadId of the most recent thread to enter level 'i'.

All elements of level[] are initialized to 0. No specific initialization for 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   }

The code is a direct copy from the book "The Art of Multiprocessor Programming" by Maurice Herlihy and Nir Shavit.

The problem is that the code doesn't seem to satisfy the mutual exclusion property !!

Reasoning :- Line 6 implies that, a thread would keep looping at a level until there is some thread at same or higher level and the thread itself is the most recent one to enter the level it is currently in. Also, only one thread can stay at a level. If a second thread comes to the same level then the 'victim[i] == me' expression would become false for the first thread and hence would be pushed down to the next level.

Now if there is one thread at each level and the thread at level 0 attempts to advance to level 1. This would push the thread at level 1 to level 2, as it would no more be the victim at level 1. Thus there will be ripple effect and each thread would be pushed down by one level, causing the thread at level n-2 to enter its critical section too !!

So is the code actually wrong or have I interpreted anything wrong ?

Answer 1

n is the number of threads and n is the number of levels levels begin with 0 and the n-1 level is the critical section

and if all the levels filled with a thread there won't be any other threads to enter level 0 which is the first level. so it will never happen.

for example if no of threads and number of levels are 3. in the beginning all the threads are at level 0 and two can advance to next level and one must wait according to the condition while ((∃k != me) (level[k] >= i && victim[i] == me)) ; and one from that two threads advance to level 2 which is the critical section.

now each level is filled with one thread and only possible scenario is thread in the critical section calls unlock() by making it's level =0 then only other threads can proceed.

point is number of threads equal to number of levels