Comments (10)
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 ofFAA
operation inlock()
determines FIFO order of entering critical section. - CLH/MCS locks satisfy
fairness
since success timing ofswap
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.
Related Issues (20)
- [Question] Unable to start the workspace on Coder HOT 1
- [Question] I get VALID?=timeout with full score log HOT 4
- [Lecture] Suggestion on teaching promising semantics HOT 1
- Optional Q&A session on June 5th (Wed)
- [Question] Understanding of access hazard & ABA hazard HOT 1
- Server rebooting scheduled (Jun 5, Wed, 10pm~) HOT 1
- [Question] zip is not installed on server HOT 2
- gg.kaist.ac.kr down for preparing for the final exam HOT 1
- [Question] find_harris_herlihy_shavit relaxed load for tag HOT 6
- [Question] Timeout on growable_array stress_concurrent with cargo_asan HOT 2
- [Question] How to get previous node of bucket sentinel? HOT 8
- [Question] Hazard Pointers: is it safe to protect a pointer to invalid memory? HOT 5
- [Question] Code lines for maintaining the invariants of stack/queue HOT 1
- [Question] About the problem of 2022 Fall HOT 2
- [Question] ordering in stack push for maintaining invariant HOT 1
- Final claim session on June 17th (Mon) HOT 4
- [Question] HW 7 reason for having atomicUsize type in hazard field HOT 2
- [Question] [HW7] Failed Basic Tests in hazard.rs HOT 3
- [Question] HW7 Dropping the Hazard Bag HOT 3
- [Question] Partial Points on HW7 HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from cs431.