Limited Expected Mutual Exception with Test and Set

Question

I read the famous book "Operating System Concepts" (Avi Silbershatz, Peter Bar Galvin, Greg Gan), version 9: http://codex.cs.yale.edu/avi/os-book/OS9/

In the chapter "Process synchronization" there is an algorithm "Mutual exception with restrictions" using test_and_set "as follows:

do { waiting[i] = true; key = true; // <-- Boolean variable that I do not see its utility while (waiting[i] && key) // <-- the value of the key variable here is always true key = test_and_set(&lock); // <-- it might become false here, but what is the point? waiting[i] = false; /* critical section */ j = (i + 1) % n; while ((j != i) && !waiting[j]) j = (j + 1) % n; if (j == i) lock = false; else waiting[j] = false; /* remainder section */ } while (true); 

I don’t see the role of the logical variable key (used in the 3rd, 4th and 5th lines of the code above), I see that we can remove it without any specific effect on the algorithm, am I right or am I missed?

Answer 1

You can simplify the algorithm:

 do { waiting[i] = true; while (waiting[i] && test_and_set(&lock)) ; waiting[i] = false; /* critical section */ j = (i + 1) % n; while ((j != i) && !waiting[j]) j = (j + 1) % n; if (j == i) lock = false; else waiting[j] = false; /* remainder section */ } while (true); 

and that would be exactly the same. I think the authors used key because they thought this would make the code easier to read.

As stated in the comments:

Typically, when using test_and_set you simply do while(test_and_set(&lock)) ; . However, in this case, you want to make sure that the thread only waits a limited amount of time to block. This is done using the waiting array. At the end of the critical section, when we unlock, we do not just set the lock to false, as you usually unlock it. Instead, we try to find the next thread that is waiting for blocking. To the next, I mean the increment of the stream identifier, and then the cycle when we press n (part j = (j + 1) % n; ). If such a stream j found, we set waiting[j] to false instead of lock .

This prevents scenarios in which 2 or more threads are constantly locking up while another thread or thread group is always waiting. For example, let's say that 3 threads expect the same lock (threads 0, 1, and 2). Say thread 0 releases the lock, and then thread 1 captures it. While thread 1 has lock thread 0, then tries to lock again, and when thread 1 releases lock thread 0, it locks it instead of thread 2. This can be repeated endlessly and thread 2 never gets a lock.

In this limited wait algorithm using the waiting array, this behavior cannot occur. If three threads constantly capture a lock, the next thread in terms of a thread identifier will go further, for example. thread 0 will capture and release the lock, followed by thread 1, and then thread 2. This is because each thread expects either a lock or its entry in the waiting array becomes false . If another thread is waiting for a lock when the thread is about to release the lock, it sets the waiting entry instead of lock , freeing only that thread from waiting for rotation. This prevents the pathological event of one or more threads waiting indefinitely to block.

Answer 2

How would you substantiate, if there are only two processes, why the limited expectation is also not satisfied ??