About starvation freedom, Exercise 15 in Chapter 2, and the answer from Professor Amir Pnueli's class

[Ziyao Wei]

Dear all,

First, I'd thank Prof. Herlihy and Prof. Shavit for such a brilliant book. It's really an eye-opener! It's used here in New York University's Courant Institute of Mathematical Sciences' CS department as the text / recommended book for quite several years, although I am not in that class.

However, I am a bit confused about starvation freedom and Exercise 15. I think starvation freedom (I did not find a precise definition) means that "for any thread that wants to enter the CS, there exist(s) time period(s) that it could do this", but if it is unlucky and the algorithm does not have bounded waiting property, then it could possibly stay outside of the CS from an arbitrary length of time.

Exercise 15 was chosen by the Prof. Amir Pnueli as one of the exercises in the 2009 Spring version of the Distributed Computing course, and here's the answer provided in that course: http://www.cs.nyu.edu/courses/spring09/G22.2631-001/sol1.pdf

Problem 4 is that exercise.

However, I don't really understand the given answer that this algorithm does not have the starvation freedom property; I think that since when a thread got stuck on line 8, once another thread unlocks, y will be -1 and that stuck thread then may get out of the loop. Does that means that like filter lock, this algorithm does not have bounded waiting but is starvation free?

Of course, I think another definition of starvation freedom will both satisfy the answer and my logic: "Suppose some thread is currently stuck somewhere. If the system keeps making progress as a whole, then from some certain time on, the stuck thread will always be able to make progress unless it has made progress since it's been stuck." I don't know if this is clear enough or not, but that's the best I could think of now.

Now I am stuck in the loop of my mis/understanding and the late Prof. Pnueli's solution. What have I went wrong on this exercise, or maybe my second take here is right?

Thanks!

Best,

Ziyao

[Eric Mercer]

On Jan 25, 2012, at 23:41 , Ziyao Wei wrote:

> Dear all,
>
> First, I'd thank Prof. Herlihy and Prof. Shavit for such a brilliant book. It's really an eye-opener! It's used here in New York University's Courant Institute of Mathematical Sciences' CS department as the text / recommended book for quite several years, although I am not in that class.
>
> However, I am a bit confused about starvation freedom and Exercise 15. I think starvation freedom (I did not find a precise definition) means that "for any thread that wants to enter the CS, there exist(s) time period(s) that it could do this", but if it is unlucky and the algorithm does not have bounded waiting property, then it could possibly stay outside of the CS from an arbitrary length of time.
>
> Exercise 15 was chosen by the Prof. Amir Pnueli as one of the exercises in the 2009 Spring version of the Distributed Computing course, and here's the answer provided in that course: http://www.cs.nyu.edu/courses/spring09/G22.2631-001/sol1.pdf
> Problem 4 is that exercise.
>
> However, I don't really understand the given answer that this algorithm does not have the starvation freedom property; I think that since when a thread got stuck on line 8, once another thread unlocks, y will be -1 and that stuck thread then may get out of the loop. Does that means that like filter lock, this algorithm does not have bounded waiting but is starvation free?

The key difference between the filter lock and the example in this problem is that in the filter lock, at some point, a thread is no longer a victim at any given level (assuming constant contention for the lock), and as such, it can make progress when it gets on the processor. That is to say that the lock algorithm itself does not prevent a thread from making progress, and as such, it is starvation free but not necessarily fair since other threads may overtake a thread that simply does not get fair time on the scheduler.

In contrast, the lock in this problem makes no similar guarantee. Specifically, if unlock() is called to reset y to -1, then there is an equally likely chance that another thread will set y to its thread ID as it is for the waiting thread to set y to its ID. As such, the algorithm itself will repeatedly block a thread from making progress so when the blocked thread does get on the processor, it may find itself yet blocked again. In other words, the filter algorithm guarantees a thread can make progress when it gets on the processor (regardless of when that happens) whereas this algorithm does not and therefore is not starvation free.

Does that makes sense?

Regards.

egm

--
++++++++++++++++++++++++++++
Eric G Mercer
Computer Science Department
Brigham Young University