Locks provide mutual exclusion.

The basic idea

The lock is a variable, so it needs to be declared (e.g. mutex).

It’s either acquired/locked/held （被占用）, or available/unlocked/free （可用）. If a lock is acquired, a thread is in a critical section related to that.

If a thread calls lock(), it waits until the lock is available, and then acquire it. If unlock() is called, then it’s available again.

Pthread locks

The POSIX library calls a lock mutex.

// initialization
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
// lock
pthread_mutex_lock(&lock);
// do something
// unlock
pthread_mutex_unlock(&lock);

We don’t need to use the same mutex for all critical sections, we just need to declare one for each. It supports a fine-grained way.

Evaluating locks

Criteria:

• Correctness
  • mutual exclusion
  • deadlock-free
  • starvation-free
• Fairness
• Performance

Controlling interrupts

For single-processor machines, we can disable interrupts in the critical sections. However, disabling interrupts is an important privilege. During that, interrupts are lost, so that the CPU doesn’t know when IO is complete.

Test and set (atomic exchange, 原子交换）

Test-and-set instruction (测试并设置指令，a.k.a. atomic exchange) is the simplest way of hardware support.

The first attempt is to set a variable to imply if it’s occupied by a thread. If yes, the thread must spin-wait (自旋等待, do nothing to wait for release).

Problems: performance and correctness.