锁的基本思想
lock_t mutex; ... lock(&mutex); balance = balance + 1; unlock(&mutex);
锁的基本使用如上，首先声明一个锁变量，lock()尝试获取锁，如果没有其它线程持有该锁，该线程会获取锁，进入临界区，其它线程无法进入临界区。锁的持有者一旦调用unlock()，锁就可以了，此时等待的线程察觉到锁可以用，会获取该锁，进入临界区。
实现一个锁
上面我们从使用的角度对锁有了基本认识，那么该如何实现一个锁呢，我们需要什么样的硬件支持，操作系统应该提供怎样的支持呢？下面我们尝试去解答这些问题。
1.目标
在实现锁之前我们应该明确目标，设立一些标准来评价锁的效果。第一是锁的基本任务，提供互斥，能否有效阻止多线程进入临界区；第二是公平性，就是每个线程能否公平抢到锁，会不会有可能锁会被饿死；第三是性能，具体来说就是时间开销，有几个场景要考虑，一个是无竞争情况下的抢锁和放锁的开销，一个是单CPU多线程竞争，最后一个是多CPU多线程的情况。
2.控制中断
void lock() { DisableInterrupts(); } void unlock() { EnableInterrupts(); }
最早的方案之一，就是在临界区关闭中断，这个主要是针对单处理器，伪代码如上。
这个方法主要优点就是简单，但是缺点很明显，首先就是允许用户拥有特权，我们很难保证某些贪婪的用户不会滥用特权，比如一开始就调用lock()后，这样会一直占用处理器；第二就是不支持多处理器，多线程运行在多处理器的情况下，即使关闭中断也没用；第三就是关闭中断会导致中断丢失，这个可能会导致严重的系统问题，比如磁盘设备完成了读取请求，但是CPU错过了，那么操作系统该如何唤醒等待的进程呢？最后一个不太重要的原因就是效率低，关闭和开启中断比较慢。
基于以上原因，只有有限的场景下才会使用关闭中断来实现互斥。
3.原子交换
因为关闭中断无法工作在多处理器上，我们是不是该寻求硬件的帮忙呢？答案是肯定的，最简单的硬件支持是test-and-set指令，也叫原子交换。下面我们来试着理解test-and-set如何工作，先实现一个简单的锁。
void init(lock_t *mutex) { mutex->flag = 0; } void lock(lock_t *mutex) { while (mutex->flag == 1) ; // spin-wait (do nothing) mutex->flag = 1; } void unlock(lock_t *mutex) { mutex->flag = 0; }
思想很简单就是通过一个变量来标志锁是否被占用，如果锁被占用，线程就会一直等待，这里有两个问题：正确性和性能。这个正确性问题在并发中很常见，假设代码按照下表执行
| Thread1 | Thread2 |
|
call loack() while(flag == 1) interrupt:switch to thread2 |
|
|
call lock() while(flag == 1) flag=1; interrupt:switch to thread1 |
|
| flag=1;//set flag to 1 (too!) |
可以看出，中断可能会导致两个线程都进入临界区，显然这个没有达到基本的要求：互斥。
性能问题主要是线程在等待已经被持有的锁是，采用了自选等待的技术，会浪费时间。
4.实现可用的自旋锁
上面的想法是好的，但是没有硬件的支撑，显然是无法实现的。幸运的是系统提供了这一指令，在SPARC上叫ldstub(load/store unsigned byte)，在x86上叫xchg(atomic change)。这个指令虽然不同，但做的事差不多，我们用如下的伪代码表示：
int TestAndSet(int *old_ptr, int new) { int old = *old_ptr; *old_ptr = new; return old; }
这个代码实现了两件事，一个是替换旧值，另外一个是返回旧值。即可以跟新标志位，又可以检查。关键这些是原子执行的。下面我们再看看原先的代码：
void init(lock_t *mutex) { mutex->flag = 0; } void lock(lock_t *mutex) { while (TestAndSet(mutex->flag, 1) == 1) ; // spin-wait (do nothing) } void unlock(lock_t *mutex) { mutex->flag = 0; }
假如flag为0，刚好替换为1，且返回0，进入临界区；假如flag为1；即使替换，还是保持值不变，返回1，while循环等待。
到这里可能也理解了为什么这种锁是自旋锁，这是最简单的一种锁，利用CPU周期，直到锁可用。在单处理器上，需要抢占式的处理器，否则自旋锁在单CPU上无法使用。
5.评价自旋锁
我们从上面提的三个标准来看自旋锁，首先正确性是满足的，这是一个合格的锁，其次看公平性，自旋锁能保证等待线程进入临界区吗？答案是否定的，实际上自旋的线程在竞争条件下可能会永远自旋。所以自旋锁没有公平性，可能会导致饿死。
最后我们看一下性能，这个我们分两种情况讨论：在单CPU上，性能开销很大，线程进入临界区后，其它线程（假设有N-1一个线程）会自旋一个时间片，浪费CPU时间，临界区线程效率也会低。但是在多CPU上，自旋锁性能不错，线程1进入临界区后，线程2竞争锁会在另一个CPU上自旋，临界区一般时间很短，因此很快锁就可用了，线程2就可用了，你看多CPU处理器上，性能是不是还可以。
6.自旋过多：让出来
自旋过多浪费了大量的时间片，我们有没有办法解决呢？有一种简单的方法就是自旋的时候放弃CPU
void init(lock_t *mutex) { mutex->flag = 0; } void lock(lock_t *mutex) { while (TestAndSet(mutex->flag, 1) == 1) yield() ; // give up the CPU } void unlock(lock_t *mutex) { mutex->flag = 0; }
我们假定操作系统提供了原语yield()，线程可以调用它主动放弃CPU，让其它线程运行。线程可以处于3态之一（运行，就绪和阻塞）。yield()系统调用可以让运行态变为就绪态，从而允许其他线程运行。
下面我们分析一下效果，在单CPU运行两个线程，基于yield()的方法很有效，一个线程lock()住，让出CPU，另外一个线程运行，完成临界区，效果比较好。我们再来考虑多线程反复竞争（假设100个）另一把锁的情况，在这种情况下，一个线程持有锁，在释放锁之前被抢占，其它99个线程会一直处于让出的模式，成本比较高，而且，一个线程一直让出，可能会饿死。我们需要另一种方法来解决这个问题。
7.使用队列
为了防止饿死，我们需要显式的加以控制，锁释放是，谁能获取到锁。为了做到这一点，需要操作系统的支持，并需要一个队列来保存等待锁的线程。
简单起见，我们利用Solaris提供的支持，它提供了两个调用：park()让线程休眠，unpark(id)唤醒线程。
typedef struct lock_t { int flag; int guard; queue_t *q; } void init(lock_t *mutex) { mutex->flag = 0; mutex->guard = 0; queue_init(mutex->q); } void lock(lock_t *mutex) { while (TestAndSet(mutex->guard, 1) == 1) ; // spinning if(m->flag == 0) { mutex->flag = 1; mutex->guard = 0; } else { queue_add(mutex->q, gettid()); mutex->guard = 0; park(); } } void unlock(lock_t *mutex) { while (TestAndSet(mutex->guard, 1) == 1) ; // spinning if(queue_empty(mutex->q)) mutex->flag = 0; else unpark(queue_remove(mutex->q)); mutex->guard = 0; }
在这个例子中，我们做了两件事，通过test-and-set和park()结合，实现了一个高性能的锁，其次通过队列，保证了公平性，避免饿死。
上面我们可以看出guard其实是自旋锁，但是这个时间很短，只是用来保证队列和flag操作，现在看来是可以容忍的。
这里其实还有一个问题就是，在park()之前，刚好切换到另一个持有锁的线程，且这个线程释放了锁，这个时候再切换回来，会有麻烦，会一直park()下去，为了解决这个问题，Solaris通过调用setpark()来解决，表明自己将要park。
queue_add(mutex->q, gettid()); setpark(); mutex->guard = 0; park(); }
参考：
- 操作系统导论