Lock

A mutex is a programming flag used to grab and release an object.

A mutex is a programming flag used to grab and release an object. When data are acquired that cannot be shared or processing is started that cannot be performed simultaneously elsewhere in the system, the mutex is set to lock (typically zero), which blocks other attempts to use it. The mutex is set to unlock when the data are no longer needed or the routine is finished.

Example

The first solution is the obvious one–put a lock on the door of the bathroom. When someone enters the bathroom, they lock the door. While this may work for people, it does not work for computers; in fact, it does not work for people if they behave like computers. Here is a scenario where it fails. Two people walk up to the door, open the door together, enter together and lock the door together. This scenario does not happen normally because people use their sense of sight, hearing and touch to notice there is someone with them. However, computers have none of these senses, and therefore, they cannot use solutions that rely on them.

Spin Lock vs. Blocking Lock

Spinning locks busy wait until an event occurs $\Rightarrow$ task oscillates between ready and running states due to time slicing.

Blocking locks do not busy wait, but block until an event occurs $\Rightarrow$ some other mechanism must unblock waiting task when the event happens.

Spin Locks

• Non-yielding spin lock: uSpinLock
• Yielding spin lock: uLock They are either closed (0) or opened (1), and waiting task compete to acquire the lock after it is released.

• acquire() acquires the lock if it is open, otherwise the calling task spins waiting until it can acquire the lock
• tryacquire() makes one attempt to acquire the lock
  • i.e., it does not wait. tryacquire returns true if the the lock is acquired and false otherwise.
• release() releases the lock, which allows any waiting tasks to compete to acquire the lock. release only (re)sets the lock to open(1)

• a) two tasks are created in uMain::main and each is passed a reference to an instance of uLock. As in previous synchronization examples, the lock starts closed instead of open so if task t2 reaches S2 first, it waits until the lock is released by task t1. As well, the synchronization protocol is separated between the tasks instead of surrounding a critical section.
• b) two tasks are created in uMain::main and each is passed a reference to an instance of uLock. Each task uses the lock to provide mutual exclusion for two critical sections in their main routine by acquiring and releasing the lock before and after the critical section code. When one task’s thread is in a critical section, the other task’s thread can execute outside the critical sections but must wait to gain entry to the critical section.

for spinning locks, an arriving task could miss seeing the exiting task reset the lock, but eventually rechecks the lock and finds it open.

Blocking Locks

Every task to a bit of extra work so that all tasks perform better.

For blocking locks, an arriving task only gets one check to test if the lock is open, and then blocks. Once blocked, the task is completely dependent on the exiting task to unblock it, otherwise it waits forever

Mutex Lock

Mutex Lock

Only used for mutual exclusion, and tasks waiting on these locks block rather than spin when the critical section is occupied.

Two kinds:

• single acquisition
  • non-reentrant: meaning the task that acquires the lock (lock owner) cannot acquire it again
  • single acquisition cannot handle looping or recursion involving the same lock, e,g,: recursive call fails after 1st recursion because the lock is already acquired, which prevents further entry into the critical section by the lock owner! $\to$ Deadlock
• multiple acquisition
  • reentrant: meaning the lock owner can acquire it multiple times, called an owner lock
  • solves the problem for instance if you forgot to bring soap into the bathroom and need to momentarily step out. the person using the bathroom does not want to release the bathroom lock because someone could enter.
  • To allow multiple acquisition, the lock remembers the task that has acquired the lock (owner), and that task is allowed to acquire the lock again without blocking.

Figure 7.2a:

• Implementation of a mutex (owner) lock.
• A task blocks by linking itself onto a list, marking itself blocked, and yielding its time-slice, without putting itself on the ready queue
• Since this task is not on the ready queue, it is ineligible for execution until the task releasing the lock transfers it from the blocked list to the ready queue.
• The only mechanism available to provide the locking is the nonblocking spin-lock or a wait-free mechanism, which is used to provide the necessary mutual exclusion.
• the lock has auxiliary variables inUse flag and an optional owner indicator, if it is a multiple-acquisition lock.
  • The inUse flag indicates if the lock is acquired, and it is set and reset by the task that currently owns the lock. The flag is tested by an acquiring task, and if set, the task blocks on the lock’s blocking list, unless it is the lock owner.
  • Adding the owner-lock feature requires remembering which task currently has the lock acquired, and checking during a lock acquire so the lock owner does not block.

Use magic to atomically yield without scheduling and release the spin lock. This ensures a releasing task cannot start the release routine until the blocking task is on the lock’s blocking list and not executing on a CPU.

yieldNoSchedule(lock); // yield CPU but do not reschedule onto
					   // the ready queue

• the spin lock is passed to the runtime system, which does the yield without schedule and then, on behalf of the user, unlocks the lock.
• A releasing task checks for blocked tasks and schedules one if available, and then resets the inUse flag and owner.
• barging

Figure 7.2b:

• Removes barging and hence starvation, by conditionally resetting inUse only when there are no blocked tasks.
• All acquiring tasks see the lock as acquired and block.
• When the unblocked task restarts, it progresses without further checking because it is granted acquisition directly from the releasing task.
• The unblocking task still reacquires the spin lock because it updates variables before leaving the entry protocol.

Safer and more efficient solution without any simultaneous variable access and the unnecessary release/acquire of the spin lock to transfer the mutual exclusion:

Figure 7.3a:

• After the releasing task acquires the spin lock and decides to unblock a task, it does not release the spin lock (baton passing, see Sect. 7.6.1, p. 356), which is accomplished by moving the spin-lock release into the else clause in member release.
• When the blocked task restarts in member acquire, the spin- lock acquire after the yield is removed because the spin lock has not been released, so the unblocked task can safely perform any additional operations needing mutual exclusion.
• the mutual exclusion provided by the spin lock is transferred directly from the releasing task to the unblocking task
• Here: the critical section is not bracketed by the spin lock; instead, the acquire and release are performed in separate blocks of code, similar to lock usage for synchronization.

Figure 7.3b:

• Further simplification: remove variables inUse and owner.
• This approach leaves the lock owner at the front of the blocked list while in the critical section to act as the flag and owner variables!
• In release(), the lock owner removes its own node from the blocked list rather removing the next owner.
• So, while the critical section is being used, the blocked list always has a node on it, which can be checked for in-use and owner.
• Any acquiring task now sees the blocked list is not empty and waits.

Note

The unblocking task in the acquire routine does not need to reacquire the spin lock because no lock variables are accessed before entering the critical section.

Have we eliminated busy waiting using blocking lock?

No still exists because the spin lock is necessary and the spin lock has busy waiting.

However, instead of busy waiting for the large user critical-section, the busy wait is only for the short time to conditionally set state variables and possibly block.

Smaller chance of starvation. Trick is to keep making the probability smaller.

From the notes: Implementation of multiple acquisition lock manages owner state (blue):

Lock-Release Pattern

_Finally clause on the try statement is always executed regardless of how the try block terminates. Putting the lock release into the _Finally clause ensures any form of block exit (normal, break, return, exception), always releases the lock.

• The C++ constructor/destructor mechanism can be used to capture the entire mutex-lock pattern, i.e., both acquire and release.
• The idiom is called RAII, and it ties resource usage, e.g., the lock to object lifetime.
  • The RAII class has a reference to a mutex lock and its constructor acquires the lock and its destructor releases the lock.

Stream Lock

A coarse-grained solution is to perform all stream operations (e.g., I/O) via a single task, providing the necessary mutual exclusion for the stream. A fine-grained solution is to have a lock for each stream, which is acquired and released around stream operations by each task.

$\mu$C++ provides a fine-grained solution:

• owner lock is acquired and released indirectly by instantiating a type that is specific to the kind stream:
  • type isacquire for input streams and
  • type osacquire for output streams

constraining the output to two different lines in any order:

The anonymous locking object is only deallocated after the entire cascaded I/O expression is completed, and it then implicitly releases the stream’s owner lock in its destructor.

Because of the properties of an Owner Lock , a task can allocate multiple locking objects for a specified stream, and the stream’s owner lock is only released when the topmost locking object is deallocated.

Multiple I/O statements can be protected atomically using normal block structure, e.g.:

• Which locking-release pattern is used by stream locks?

Synchronization Lock

Related

• Owner Lock