[Question] Should we consider, for fairness evaluation, that a thread might not `unlock()`? about cs431 HOT 10 CLOSED

I guess your questions can be clarified by the section 2.5 of The Art of Multiprocessor Programming (we call it "art" book), listed as one of our supplementary resources (https://github.com/kaist-cp/cs431?tab=readme-ov-file#textbook).

Starvation-freedom

As long as I understand, you understand the notion of fairness as all threads eventually succeed in their operation, which eliminates an unfair situation where one thread keeps failing due to contention. However, it is more like starvation-freedom based on the definition of the art book.

Freedom from starvation: Every thread that attempts to acquire the lock eventually succeeds. Every call to lock() eventually returns. This property is sometimes called lockout freedom. (p. 24)

Note that the definition is given under the assumption that a resource (e.g. lock) is always available (e.g. lock is always released). So, even though one thread might not release a lock forever, we can still discuss that ticket lock (or other locks including the Peterson lock in §2.3.3) has starvation-freedom.

Fairness

Fairness is more like fair ordering of the operation. §2.5 of the art book introduces a formal definition of fairness of lock. Informally speaking, an implementation of lock satisfies fairness if each thread enters its critical section in FIFO order of request.

• Ticket lock satisfies fairness since success timing of FAA operation in lock() determines FIFO order of entering critical section.
• CLH/MCS locks satisfy fairness since success timing of swap operation determines FIFO order of entering critical section.

from cs431.

Yes, you should consider such cases.

from cs431.

But how can we ever have a fair lock then? In my view releasing the lock is the responsibility of the thread and therefore we should not include such cases in the analysis of the lock's fairness.

from cs431.

But how can we ever have a fair lock then? In my view releasing the lock is the responsibility of the thread and therefore we should not include such cases in the analysis of the lock's fairness.

I share the same view with you. If we ever include cases that some threads do not release a lock, we can never say a lock is fair.

from cs431.

Thank you for kind explanation. But I have a followup question that, as the definition of Starvation Freedom is given under that a resource is always available, it seems that we shouldn't consider cases where a lock is never released (to say Ticket Lock is Starvation-Free). But I think it does not align with @Lee-Janggun's comment, as he says we can't assume that a resource is available. Could you clarify?

from cs431.

Your original question was asking whether the definition of fairness considers the case that a thread never calls unlock(). When considering fairness, you should consider such situation since its definition does not assume availability of a resource (if you read §2.5 of the art book, then you can see that it explicitly considers a waiting section where a thread waits its turn possibly indefinitely before entering a critical section). So, even though the ticket lock satisfies fairness, lock() function might wait indefinitely.

However, if you consider starvation freedom, then you should reason about progress guarantee of all threads calling lock() given that a resource is available.

from cs431.

The point of my comment was that: during that specific exam, you had to consider such cases. I was simply repeating the grading criteria; I should have made that clearer.

Now there really doesn't exist a universal silver bullet definition of fairness, and one must consider the context carefully. The context of the exam was that you had to consider the case a thread does not release.

from cs431.

So in conclusion, the statement
[7] In (A), a thread waiting to acquire the lock might potentially wait indefinitely until its turn comes.

Is true because a thread might not release the lock?

from cs431.

Yes you're correct.

from cs431.

Thank you. I learned a lot from your help. :)

from cs431.