Chapter 5 Flashcards
Does Wait-Free Imply Mutual exclusion
No
What is the problem with mutual exclusion?
If something happens to a register that has a lock the rest of the registers have to wait until lock is released
What does the principle of consensus determine?
The power of sync primitives
What is the basic idea of Consensus
Each class in hierarchy has an associated consensus number
What is a Consensus number?
Max no of threads for which objects can solve consensus
What method does a consensus object have?
decide()
what does decide() return in consensus object?
a value that is consistent and valid (all threads decide the same value, the common decision value is some thread’s input)
Can 2 threads reach consensus on 2 values using atomic registers?
No
What consensus number does an atomic number have?
1
What does a sequential number of 1 mean?
only 1 thread can solve it so its sequential
Can a FIFO Queue Implement Consensus?
Yes, but only for 2 threads (consensus number 2)
What does RMW stand for?
Read-Modify-Write
What are the RMW Methods? and which one takes 2 values?
getAndSet(x)
getAndIncrement()
getAndAdd(k)
get()
compareAndSet() <= takes 2 values
what is the consensus number of non-trivial RMW objects?
2
What methods do subclasses of consensus have?
propose(x)
decide(object value)
