synchronization - Filter lock mutual exclusion property -

the following generalised version of peterson's 2-thread lock algorithm, allowing 'n' threads/processes compete critical section.

basically there 'n' levels , 'n' threads. threads inactive or executing in non critical section region @ level 0. level n-1 critical section. every thread/process must cross n-1 levels before entering critical section.

there 2 arrays, level[n] & victim[n]. first array indexed threadid of thread, , entry level[i] stores current level of thread threadid 'i'. second array indexed level number, , entry victim[i] stores threadid of recent thread enter level 'i'.

all elements of level[] initialized 0. no specific initialization victim[].

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

the code direct copy book "the art of multiprocessor programming" maurice herlihy , nir shavit.

the problem code doesn't seem satisfy mutual exclusion property !!

reasoning :- line 6 implies that, thread keep looping @ level until there thread @ same or higher level , thread recent 1 enter level in. also, 1 thread can stay @ level. if second thread comes same level 'victim[i] == me' expression become false first thread , hence pushed down next level.

now if there 1 thread @ each level , thread @ level 0 attempts advance level 1. push thread @ level 1 level 2, no more victim @ level 1. there ripple effect , each thread pushed down 1 level, causing thread @ level n-2 enter critical section !!

so code wrong or have interpreted wrong ?

n number of threads , n number of levels levels begin 0 , n-1 level critical section

and if levels filled thread there won't other threads enter level 0 first level. never happen.

for example if no of threads , number of levels 3. in beginning threads @ level 0 , 2 can advance next level , 1 must wait according condition while ((∃k != me) (level[k] >= && victim[i] == me)) ; , 1 2 threads advance level 2 critical section.

now each level filled 1 thread , possible scenario thread in critical section calls unlock() making it's level =0 other threads can proceed.

point number of threads equal number of levels