互斥锁

互斥锁 (mutex lock) 确保关键区同一时刻最多只能有一个线程进入。

评估指标

互斥 (mutual exclusion)：最基本的要求。它能够实现关键区的互斥访问吗？ 公平 (fairness)：饥饿线程？ 效率 (performance)：锁的开销 (overhead) 几何？

禁用中断

当线程 A 进入关键区后，禁用中断以保证不会切换到其他线程。

  • 禁用中断是一个受限操作，将该权限转让给用户程序会产生诸多安全问题
  • 多核/多处理器？
  • 中断本身十分重要！

OS 代码有时会采取禁用中断实现互斥锁。

原子指令与自旋锁

依赖硬件支持的两种原子指令 (atomic instructions) 来实现互斥锁。

Test-and-Set
c
int TestAndSet(int *ptr, 
               int new) {
    int old = *ptr;
    *ptr = new;
    return old;
}
Compare-and-Swap
c
void CompareAndSwap(int *ptr, 
                    int expected, 
                    int new) {
    int temp = *ptr;
    if (temp == expected)
        *ptr = new;
    return temp;
}

使用这两种原子指令实现一个简单的自旋锁 (spin lock)，未能获取 (acquire) 锁的线程在 while 循环中自旋等待 (spin waiting)。

c
int flag = 0;
while (TestAndSet(&flag, 1) == 1);
// or while (CompareAndSwap(&flag, 0, 1));
critical_section();
flag = 0;

评估：

  • 能够保证互斥访问
  • 不保证公平：可能会有长期饥饿的线程
  • 单核效率极低，多核（尤其是核数大致与线程数一致）效率较好

让步

很自然的想法。与其自旋等待占用 CPU 资源，不如主动让出 (yield) 自己的时间片，结束本轮的调度。

c
int flag = 0;
while (TestAndSet(&flag, 1) == 1)   // or while (CompareAndSwap(&flag, 0, 1))
    yield();
critical_section();
flag = 0;
  • 单核线程较多时，开销还是很大
  • 仍未保证公平

队列，睡眠与唤醒

Solaris 添加了三个新的系统调用：

  • park()：使当前线程睡眠，不再参与调度（而不仅仅只是让出本轮的时间片）
  • unpark(threadID)：唤醒指定的线程
  • setpark()：标记当前线程即将进入睡眠，使得若在真正执行 park() 之前收到了 unpark()， park() 会立即返回而不会阻塞。
c
typedef struct __lock_t {
    int flag;
    int guard;
    queue_t *q;
} lock_t;

void lock_init(lock_t *m) {
    m->flag = 0;
    m->guard = 0;
    queue_init(m->q);
}

void lock(lock_t *m) {
    while (TestAndSet(&m->guard, 1) == 1)
        ; // acquire guard lock by spinning

    if (m->flag == 0) {
        m->flag = 1;  // lock is acquired
        m->guard = 0;
    } else {
        queue_add(m->q, gettid());
        setpark();
        m->guard = 0;
        park();
    }
}

void unlock(lock_t *m) {
    while (TestAndSet(&m->guard, 1) == 1)
        ; // acquire guard lock by spinning

    if (queue_empty(m->q))
        m->flag = 0; // let go of lock; no one wants it
    else
        unpark(queue_remove(m->q)); // hold lock for next thread

    m->guard = 0;
}
  • 引入的队列保证了公平，线程按照 FIFO 顺序被唤醒
  • guard 自旋锁控制队列的入口，但其保护的代码是简单的队列逻辑 (L. 17-25 与 L. 32-37) 而非用户指定的关键区，所以自旋开销很小
  • 非自旋锁 flag 控制关键区的入口

为什么需要 setpark()？

  • 如果在释放 guard 锁与 park() 间恰好发生了中断，其他线程可能会在当前线程沉睡之前就尝试 unpark() 唤醒它，从而导致当前进程永久睡眠。

阅读

Chapter 28 – Locks (except sections 28.10, 28.11, 28.15, 28.16), OSTEP, http://pages.cs.wisc.edu/~remzi/OSTEP/threads-locks.pdf