Locking Flashcards
What is the objective of a lock?
To provide mutual exclusion
What are the two statuses a lock can have?
Available & acquired
Give the function call: Tries to acquire the lock
lock()
Give the function call: Releases the lock thathas been acquired by caller
unlock()
What are the three attributes that a good lock has?
Mutual exclusion, fairness and performance
What attribute of a good lock has the following description: progress & ensures no starvation
Fairness
What attribute of a good lock has the following description: overhead to grad & release lock
Performance
What do we call the software based solution to the critical section problem?
Peterson’s Solution
Give the definition of the instruction:
Tests and modifies the content of a memory word atomically
TestAndSet (TAS)
Give the definition of the instruction:
Tests whether the value at the address specified by ptr is equal to expected, if so, updates the memory location pointed to by ptr with the new value
Compare-And-Swap
Give the definition:
A lock that spins, using CPU cycles, until the lock becomes available
Spinlock
Give the definition:
When a thread needs to endlessly check the lock value to check if the lock is held by others
Spin-waiting
What is the advantage of using a simple spinlock?
Mutual exclusion
What are the two disadvantages with using a simple spinlock?
No fairness & no performance
What lock type does the following:
Locks
1. Uses Fetch-And-Add on the ticket value
2. Return value is the threads “turn” value
Unlocks
1. Increments the turn
Ticket lock
What does a ticket lock guarantee?
Fairness
Give the definition of the hardware primitive: Atomically increments a value while returning the old value at a particular address
Fetch-And-Add
Spinlocks can be fast when there are:
- Many CPUs
- Locks are held a short time
What is the advantage that makes a spinlock fast in this case?
No context switch
Spinlocks can be slow when there is:
- One CPU
- Locks are held a long time
What is the disadvantage that makes a spinlock slow in this case?
Spinning is wasteful
Give the definition of the function call:
Instead of spinning, the CPU is given up to another process/thread. The yielding thread deschedules itself.
yield()
Give the definition of the spinlock type:
Sleep and put thread on a queue instead of spinning
Locks with queue
What do locks with queue guarantee won’t happen as long as all threads relinquish locks
Starvation
Give the definition of the spinlock type:
Hybrid approach that combines both spin-wait & sleep/block
Two phase lock
Is the lock released quickly or slowly with spin-wait?
Quickly
Is the lock released quickly or slowly with sleep/block?
Slowly
Is this the first or second phase of a two phase lock?
The lock spins for a while
First
Is this the first or second phase of a two phase lock?
If the lock is acquired in the first phase, put the calling thread to sleep
Second
Give the definition of the spinlock type:
If a thread has a locked adaptive mutex and the process/thread holding the adaptive mutex is running, the adaptive mutex executes busy waiting. Otherwise, it blocks the thread.
Adaptive mutex
