ch.7 Mutual Exclusion

Question 1

what are the 3 mutual exclusion solutions?

Answer 1

strict alternation, Dekkers Algorithm, the bakery algorithm

Question 2

what four things must be ensured for Mutual Exclusion?

Answer 2

1. only one thread in CS
2. any number of threads
3. threads outside of CS cannot block another thread
4. no thread can wait forever

Question 3

what is the strict Alternation algorithm

Answer 3

uses a shared variable to determine who goes first
ex: int next = 0 blocks and int = 1 continues

Question 4

which mutual exclusion properties does the strict algorithm work for?

Answer 4

only one thread in CS and can be extended to more than one thread

Question 5

which mutual exclusion property does the strict algorithm not work for?

Answer 5

a thread can be blocked outside of the critical section
a thread can wait forever

Question 6

What is Dekkers Algorithm?

Answer 6

unselfish algorithm -> each thread waits until the thread has completed their process (achieves all four mutual exclusion properties but it has issues)

Question 7

what are some issues with Dekkers Algorithm?

Answer 7

1. inefficient while loops (uses a lot of resources)
2. potential to deadlock if both are waiting for the other to take their turn
3. live lock can occur if each thread keep yielding to the other thread
4. hard to scale

Question 8

what is the bakery Algorithm?

Answer 8

an analogy : a bakery’s ticket counter
a. thread “enters” the “bakery”
b. thread “gets” the next ticket
c. thread waits for its turn

provides mutual exclusion

Question 9

what is the best property of the bakery algorithm?

Answer 9

the algorithm does not depend on the output of a thread

ex: if there are concurrent read and write operations the algorithm does not depend upon a correct read, the read can return any arbitrary value!