本文共 2863 字，大约阅读时间需要 9 分钟。

锁是并发实现的必要机制，计算机体系结构的指令集内有不同的硬件原语，可以实现锁机制。评价锁实现的效果有三个标准：

• 互斥实现：锁的基本任务就是实现临界区的互斥访问
• 公平性：保证每一个线程都能够有机会抢到锁
• 性能：锁的使用将会增加时间开销，要求其对性能的影响降到最低

锁的实现有以下几种方式：

1. 控制中断

控制中断是最早的互斥解决方案之一，即在临界区关闭中断，保持线程对临界区的持续访问，该方案是为单处理器系统开发的。

• 控制终端的方法较为简单，但是要求允许所有调用的线程执行特权级操作，然而程序往往是不被信任的，关闭中断对应用程序要求太多。
• 其次这种方案不适用于多处理器。
• 控制中断会导致中断丢失，可能会导致严重的系统问题。例如磁盘完成IO操作但是cpu却胡烈了这一请求。
• 在操作系统内部可以通过控制中断的方式实现临界区互斥访问，因为在操作系统内不存在信任问题。

2.简单标志位

• 用flag标志锁是否被使用，线程进入临界区时调用lock，检查标志位flag，检查标志是否为1，非1则置1，表明线程持有锁。结束临界区访问时，线程调用unlock，清除标志位。
• 当已有线程A占用临界区时，另一个线程B调用lock，在while中自旋，直到线程A结束占用unlock清空标志位，线程B退出while设置标志位为1，开始访问临界区代码。
• while循环空转被称为自旋锁（spin lock），自旋锁在单cpu中无法使用，自旋锁永远不会放弃cpu。自旋锁无法保证公平性，会导致线程饿死。自旋锁的性能开销很大。

typedef struct lock_t {
    int flag; } lock_t;void init(lock_t *mutex) {
   	// 0 -> lock is available, 1 -> held	mutex->flag = 0;}void lock(lock_t *mutex) {
   	while (mutex->flag == 1) // TEST the flag		; // spin-wait (do nothing)	mutex->flag = 1; // now SET it!}void unlock(lock_t *mutex) {
   	mutex->flag = 0;}

3. 测试并设置（test-and-set）

int TestAndSet(int *ptr, int new) {
   	int old = *ptr; // fetch old value at ptr	*ptr = new; // store ’new’ into ptr	return old; // return the old value}

typedef struct __lock_t {
   	int flag;} lock_t;void init(lock_t *lock) {
   	// 0 indicates that lock is available, 1 that it is held	lock->flag = 0;}void lock(lock_t *lock) {
   	while (TestAndSet(&lock->flag, 1) == 1)	; // spin-wait (do nothing)}void unlock(lock_t *lock) {
   	lock->flag = 0;}

4. 比较并交换（compare-and-swap）

• sparc和x86系统上提供了这一指令
• 实际上和test-and-set的思路一致

//比较并交换指令的一般形式int CompareAndSwap(int *ptr, int expected, int new) {
   	int actual = *ptr;	if (actual == expected)		*ptr = new;	return actual;}

只需要用下列code替代lock函数即可

void lock(lock_t *lock) {
   	while (CompareAndSwap(&lock->flag, 0, 1) == 1)		; // spin}

5.链接的加载和条件式存储（load-link and store-conditional）

• 在MIPS架构中，链接的加载和条件式存储可以配合使用

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; // success!} else {
   	return 0; // failed to update}}

void lock(lock_t *lock) {
   	while (1) {
   		while (LoadLinked(&lock->flag) == 1)			; // spin until it’s zero		if (StoreConditional(&lock->flag, 1) == 1)			return; // if set-it-to-1 was a success: all done				// otherwise: try it all over again	}}void unlock(lock_t *lock) {
   	lock->flag = 0;}

6.获取并增加（fetch-and-add）

• 不同与之前的方法，能保证所有线程都能抢到锁（标志位不断增加）

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);}

必须显示提供某种控制机制，决定释放锁，以及那个线程能够抢到锁

转载地址：http://fzksi.baihongyu.com/