28. Locks Flashcards
What is purpose of the lock?
To allow only a single thread to execute in critical section at a time.
What happens if thread tries to acquire a lock held by other thread?
It will not return until the lock is released and acquired by this thread
What is mutex?
It’s a name for the lock in POSIX, which stands for mutual exclusion.
How is working lock evaluated?
- Prevents multiple thread from entering critical section
- Fair in terms that each tried gets a fair shot at acquiring a lock once it’s free (avoiding starvation for threads)
- Performance
What was the first approach to locks?
Disabling hardware interrupts. While not used in programs, it might be still used in some OS parts
How did approach with flag variable work and why it was a failure?
It didn’t provide mutual exclusion during lock acquшsition. It also had bad performance because waiting thread would spin-wait and waste CPU cycles.
How a working spin lock was achieved? How does it do in terms of fairness and performance?
With support of hardware operation test-and-set (or atomic exchange). It’s not quite fair as a waiting thread may spin forever. It’s also not performant on single-core CPU due to the fact waiting threads will simply waste CPU cycles waiting for the lock while it’s still held by other, prempted, thread.
How does test-and-set instruction works?
It accepts a pointer to old value and new value (0 or 1, i.e whether the lock is to be held or released). Then it atomically returns the current value of lock (0 or 1), while setting it to a new value(0 or 1).
What was the other primitive hardware instruction to support locks?
Compare-and-Swap. It accepted now the lock, expected and new values. If the expected value matched the value of lock, the “new” value would get written to lock. The current value of lock always returns.
How does load-linked and store-conditional pair of hardware instructions work?
Load-linked simply loads a value at given address. Store conditional updates the values at that same address if not intervening store to that address took place. In case of success it returns 1 and updates the value, if it fails it returns 0 and value is not updated.
What is the other instruction beside load-linked/store-conditional, compare-and-swap and test-and-set? How does it work?
Fetch-and-Add. It increments a value at address while returning an old value. Instead of usual spin lock, it was used for ticket lock, which is still a spin lock, but more fair. This solution uses ticket and turn variable, a thread gets it ticket with fetch-and-add and then spins until lock’s turn value is not equal to thread’s turn. The global lock’s turn will increment when other thread releases it and match the waiting thread’s ticket.
What is the simplest approach to the wastefulness of spin locks?
To yield CPU when lock is held instead if just spinning.
What is more effective approach to ineffectiveness of spin lock? What part of system helps with it (software, hardware)?
OS helps with the introduction of queues. In such lock implementation, a ‘guard’ is used as a spin-lock around the flag (lock) and queue manipulations. Once guard lock is applied, a thread further can acquire the lock or put itself in a queue if lock is held and get parked. When unlocking, the guard lock is also acquired and the next thread is simply picked from queue and unparked (without letting go of a lock, basically passing it to a next thread).
What is wakeup/waiting race? How does Solaris solve it?
It’s a situation where the thread gets interrupted right before the park() call in the lock() call. If the other thread runs and queue is empty, it will release the lock instead of unparking another waiting thread, making the interrupted thread sleep forever. Solaris solves this problem by adding a call that thread can use to indicate it’s about to park - setpark()
