Lock and Condition Variables

Naive Use of Interrupt Enable/Disable

On a unified-processor, can avoid context switching by:

• avoiding internal events
• preventing external events by disabling interrupts

Consequently, naive implementation of locks:

• LockAcquire(){disable interrupts;}
• LockRelease(){enable interrupts;}

Do not use this.

Better Implementation of Locks

Key idea: maintain a lock variable and impose mutual exclusion only during operations on that variable.

Atomic Read-Modify-Write Instructions

Can we extend the lock implementation to multi-processor>

• not good idea, as disabling interrupts on all processors requires messages and would be very time consuming

Def. Atomic Instruction Sequences.

• these instructions read a value and write a new value atomically
• hardware is responsible for implementing this correctly
  • on both unified-processors (not too hard)
  • and multiprocessors (requires help from cache coherence protocol)
• unlike disabling interrupts, can be used on both unified-processors and multi-processors

Spinlock

Def. Spinlock: another flawed, but simple solution:

int value = 0; // Free
Acquire() {
  while (test&set(value)); // while busy
}
Release() {
  value = 0;
}

Simple explanation:

• if lock is free, test&set reads 0 and sets value=1, so lock is now busy
  • it returns 0 so while exits
• if lock is busy, test&set reads 1 and sets value=1 (no change)
  • it returns 1, so while loop continues
• when we set value = 0, someone else can get lock
• busy waiting: thread consumes cycles while waiting

当拿着的锁的线程使用锁的时间很短时，应用自旋锁

Positive for this solution:

• machine can receive interrupts
• user code can use this lock
• works on a multiprocessor

Negatives:

• this is very inefficient as thread will consume cycles waiting
• waiting thread may take cycles away from thread holding lock (no one wins!)
• priority inversion: Iif busy-waiting thread has higher priority than thread holding lock \(\Rightarrow\) no progress

Better Locks Using test&set

Condition Variable

Mesa Monitors

• signaler keeps lock and processor
• waiter placed on ready queue with no special priority
• practically, need to check condition again after wait

Hoare Monitors

• signaler gives up lock, CPU to waiter; waiter runs immediately
• waiter gives up lock, processor back to signaler when it exits critical section or if it waits again

Quick Questions

• Do lock.Acquire() and lock.Release() always trap into kernel?
  • No
• Interrupt handlers must use spin locks instead of queueing locks. Why?
  • interrupt handlers are not supposed to sleep