Mutex Implementation Flashcards
If a thread can’t be made Thread local or Immutable we need to implement mutual exclusion. What is mutual exclusion?
Ensuring that no bad interleavings or data races occur, this is done by defining a critical section.
Define Deadlock-free.
At least one thread is guaranteed to proceed into the critical section at some point.
Define Starvation-free.
All threads are guaranteed to proceed into the critical section at some point.
Define Lock-free.
At least one thread always makes progress.
Define Wait-free.
All threads make progress within a finite amount of time.
When is a critical section mutually exclusive?
It is mutually exclusive if there is no state in which more than one thread is in the critical section.
Give an implementation of the Peterson Lock.
Does the Peterson Lock satisfy the requirements for a critical section. What are the steps in the picture?
- Set our flag, thereby indicating that we’re interested in entering the critical section.
- Indicate that the other thread is allowed to go first. The thread that arrives at this statement firrst will enter the critical section firrst.
- Wait until the other thread is either no longer interested in entering the critical section or until
we’re allowed to go first. - Indicate that we’re no longer interested.
Peterson Lock satisfies the requirements for correct implementation of critical section. It even starvation-free.
Is the filter lock fair?
Is not fair according to the first-come-first-served principle.
Definition of fairness
Definition: A lock is first-come-first-served if, whenever, thread A finishes its doorway before thread B starts its doorway, then A cannot be overtaken by B.
How do we split the lock() into two section to define fairness.
1) A doorway section, whose execution interval consists of a bounded number of steps.
2) A waiting section, whose execution interval may take an unbounded number of steps.
What is spinning or busy waiting?
When a thread can’t immediately acquire the lock so it keeps retrying.
Which of the Mutex implementations are spinlocks?
FilterLock and BakeryLock
What is blocking? Is it a good choice?
Instead of busy waiting we can ask the operating systems schedular to schedule another thread on your processor until the lock becomes available again.
Switching threads is expensive so its only worth it if the wait for the lock to be available is not long.
What is exponential backoff?
Every time we don’t manage to acquire the lock, we wait for a random amount of time m
where m is [0,t^x] where x is the number of times we have failed to acquire the lock and t is the initial wait time.
Explain the bakery lock pseudocode in the picture.
Remember bakery algorithm is for n processes and is fair because thread 1 will always enter before thread 2
we have a label and a flag array of size n-1 –> for n threads
flag[me] = true means the thread me wants to acquire the lock and enter the critical section
in the lock(me) section the thread sets flag to true saying he wants to acquire the lock.
than he gets a label. this is done by finding the max label that already exists and adding 1 to it, so that the thread has the highest labe.
than the thread waits while there exists another thread who also wants to enter the CS and there label is smaller than ours (label[k] < label[me]) and their thread id is smaller than ours (k < i me)
we have to also involve the thread id because if we didnt and only used the label number there could be a deadlock, because doing max label could happen at them same time for two threads and they might have the same label number. so wee need to also check the thread id
Lock implemented with Read-Modify-Write operation also known as atomic operation in this case TAS. Give pseudocode
1) Initialize the lock to 0
2) while we dont get true back from TAS this is equivalent to being able to acquire the lock. while did is not possible we wait and retry. Remember TAS will check if lock = 0 and in that case change to 1 and return true. We wait until that happens
3) release lock by setting it back to 0
Important when we use while we always have to negate the outcome we want so that we retry until success as seen here with !TAS(lock)
Lock implemented with Read-Modify-Write operation also known as atomic operation in this case CAS. Give pseudocode
We wait until the result of CAS is something other than 0.
Remember CAS takes these arguments (memref a, int old, int new).
than check if (old == oldval) where oldval == mem[a].
So we expect oldval to be 0 if this is true we change it to 1 thereby acquiring the lock. Than we return the value which is now 1 not 0. This lets us move out of the while loop
To unlock you could alos just do lock = 0;
