锁

并发编程的一个最基本问题就是原子性地执行一系列指令。锁有助于直接解决这一问题。

锁的基本思想

锁就是一个变量。这个变量保存了锁在某一时刻的状态。它要么是可用的，表示没有线程持有锁，要么是被占用的，表示有线程持有锁，正处于临界区（访问共享资源的那部分代码）。

Pthread锁

POSIX库将锁称为互斥量（mutex），因为它被用来提供线程之间的互斥。当一个线程在临界区，它能阻止其它线程进入到本地线程直到本线程离开临界区。

设计锁

一个锁应当能保证不会有第二个线程进入临界区。另外，还应当保证公平性，所有的线程都有机会公平抢到锁。在设计锁时还应该考虑到抢锁和释放锁的开销。

为了实现上面两点，我们需要使用硬件和操作系统的支持。

控制中断

在临界区关闭中断。这个方案是为单处理系统开发的。

原子交换（测试并设置）

控制中断无在多处理器上工作，系统设计者开始让硬件支持锁。最简单的硬件支持就是测试并设置指令（test-and-set instruction），也叫做原子交换。

typedef struct lock_t { int flag; } lock_t;void init(lock_t* mutex)
{mutex->flag = 0;
}void lock(lock_t* mutex)
{while (mutex->flag == 1) //测试; //锁被其它线程占用，该线程陷入自旋mutex->flag = 1; //设置
}void unlock(lock_t* mutex)
{mutex->flag = 0;
}

这种设置也是有问题的，首先它不能完成让线程互斥的基本任务。考虑这种情况，当线程1在测试锁时（只是通过了测试并未设置），发生了中断切换的线程2，随后线程2执行了完整的测试和设置，此时再次发生中断切换到线程1。由于先前线程1已经通过了测试语句，接下来会执行设置代码。这样一来，就有两个线程同时持有锁了。

在性能上，如果一个线程在等待已经被持有的锁时，会一直自旋，不停地检查锁。这会浪费许多CPU时间。

实现这种锁，需要一条硬件指令支持。在x86上是xchg指令（原子交换）。下面的代码片段说明了该指令的工作方式：

int TestAndSet(int* old_ptr, int new)
{int old = *old_ptr;*old_ptr = new;return old;
}

这些代码都是原子地执行。利用这类原子交换指令可以实现自旋锁。

typedef struct lock_t
{int flag;
} lock_t;void init(lock_t* lock)
{lock->flag = 0;
}void lock(lock_t* lock)
{while (TestAndSet(lock, 1) == 1);//自旋
}void unlock(lock_t* lock)
{lock->flag = 0;
}

比较并交换

另一个硬件支持是比较并交换指令。

int CompareAndSwap(int *ptr, int expected, int new)
{int actual = *ptr;if (actual == expected)*ptr = new;return actual;
}

链接的加载和条件式存储指令

int LoadLinked(int* ptr)
{return *ptr;
}int StoreConditional(int* ptr, int value)
{if (no one has updated *ptr since the LoadLinked to this address){*ptr = value;return 1;}else{return 0;}
}

获取并增加

int FetchAndAdd(int *ptr)
{int old = *ptr;*ptr = old + 1;return old;
}typedef struct lock_t
{int ticket;int turn;
} lock_t;void lock_init(lock_t *lock)
{lock->ticket = 0;lock->turn = 0;
}void lock(lock_t* lock)
{int myturn = FetchAndAdd(&lock->ticket);while (lock->turn != myturn); //spin
}void unlock(lock_t* lock)
{FetchAndAdd(&lock->turn);
}

解决自旋时的浪费

在自旋的时候，线程应该放弃CPU，从运行状态变为就绪状态。而且我们应该控制释放锁时谁可以抢到锁，这是为了避免性能上的浪费以及饿死的问题。

为此，我们需要操作系统维护一个队列保存正在等待锁的线程队列。这样我们就可以在锁被占用时休眠线程，在锁可用时从队头中唤醒一个线程。