锁的实现
操作系统会给用户程序提供开锁，闭锁的原语操作，那么锁在操作系统中是怎么实现的呢？
1.使用中断启用与禁止来实现锁
中断禁止:就是禁止打断，可以将一系列操作变为原子操作
中断启用：就是从这里开始，可以被打断，允许操作系统进行调度
上锁操作
lock() {
/**中断禁止*/
while(value != FREE) {
/**中断启用*/
//之所以在这里允许被调度，是因为在单核机器上运行时，
//如果调用lock()的线程因为中断禁止而一直获得CPU时间的话，
//那么获得锁的线程根本没有机会运行并释放锁，所以必须给其他线程插入的机会
/**中断禁止*/
}
value = BUSY;
/**中断启用*/
}
解锁操作
unlock() {
/**中断禁止*/
value = FREE;//因为这并不是原子操作，所以需要中断禁止的保护
/**中断启用*/
}
缺点：繁忙等待，不可重入（指该实现）
2.使用测试与设置指令来实现锁
测试与设置（test & set）指令：以不可分割的方式执行如下两个步骤：
1）设置操作：将1写入指定内存单元。
2）读取操作：返回指定内存单元里原来的值（写入1之前的值）。
指令若以程序来实现，则是这样的：
test_and_set(value) {
tmp = value;
value = 1;
return(tmp);
}
上锁操作
lock() {
while(test_and_set(value) ！= 0) {}
}
如果返回值不为0（即不能将锁从0变为1），则会一直循环，繁忙等待锁的释放（0）再获取锁（1）。当能够将value从0设置为1时，跳出循环，调用lock()的线程进入临界区。
如果同一个线程调用两次lock()，因为value已经为1，所以返回值会一直返回1，会无法退出循环，导致死锁。
解锁操作
unlock() {
value = 0;
}
缺点：繁忙等待，不可重入（指该实现）
3.以非繁忙等待、中断启用与禁止来实现锁
锁的实现思路如下：
1）使用中断禁止，但不进行繁忙等待。
2）如果拿不到锁，进程放弃CPU并进入睡眠状态，以便持有锁的进程可以更好地运行。
3）当锁释放的时候将睡觉进程叫醒。
错误示例 上锁操作
lock() {
/**中断禁止*/
if(value == FREE) {
value = BUSY;
} else {
/**将该线程放进等待队列，准备进入睡眠*/
/**调用yield放弃CPU切换到其他线程*/
}
/**中断启用*/
}
错误示例 解锁操作
unlock() {
/**中断禁止*/
value = FREE;
if(等待队列不为空) {
/**将等待队列的其中一个线程移至就绪队列*/
value = BUSY;
}
/**中断启用*/
}
上述锁的实现程序乍一看似乎很有道理，可仔细一想却发现有问题。
问题是，在上锁操作中，我们调用yield切换到别的线程的语句在启用中断指令前执行，由于切换到另一个线程后，该线程就无法再执行，那么后面的中断启用指令自然就不能执行了。
而因为我们是在中断处于禁止状态下切换到别的线程的，如果别的线程没有执行中断启用或者自动放弃CPU给另一个线程，那么该线程将一直占用CPU，其他的线程（包括调用lock()的线程）将无法得到执行。
解决方法：
分析后可以发现，“将自己放在等待队列”和“切换到别的线程”这两个操作应该是一组原子操作，不能在中间中断。
这也就是说，启用中断操作只能在执行这两个操作之后，而不能在中间。
那么剩下的唯一可能就是闭锁操作不启用中断，而是留给别的线程去启用中断。
也就是说，我们要求所有线程遵守下列约定：
•所有线程承诺在调用线程切换时将中断留在禁止状态。
•所有线程承诺在从切换返回时（回到自己线程时）将中断重新启用。
实现过程
因此整个过程如下：
| 线程A（没有锁，调用lock()） | 线程B（初始获得锁） |
|---|---|
| CPU时间片结束 | |
| 禁止中断 | |
| 切换到A | |
| 启用中断 | |
| （用户代码） | |
| 请求资源，调用lock() | |
| 禁止中断 | |
| 检查锁的情况（锁被B持有） | |
| 进入等待队列 | |
| 切换至线程B | |
| 启用中断 | |
| （用户代码） | |
| 释放资源，调用unlock() | |
| 从等待队列中拿出A | |
| 将A移到就绪队列 | |
| CPU时间片结束 | |
| 禁止中断 | |
| 切换到A | |
| 启用中断 | |
| lock()方法返回 | |
| A获得锁 | |
| 进入临界区 |
缺点：依赖操作系统。
4.以最少繁忙等待、测试与设置来实现锁
思路：只用繁忙等待来执行闭锁的操作。如果不能获得就放弃CPU。
上锁操作
lock() {
while(test_and_set(guard) == 1) {}
if(value == FREE) {
value = BUSY；
guard = 0;
} else {
guard = 0;
/**将自己加入该锁的等待队列，准备进入睡眠*/
/**切换到其他线程*/
}
解锁操作
unlock() {
while(test_and_set(guard) == 1){}
value = FREE;
if(锁的等待队列不为空) {
/**将等待队列中一个线程移至就绪队列*/
value = BUSY；
}
guard = 0;
}
为什么繁忙等待时间缩短了？
这是因为我们将等待对象从value改成了guard。
guard要防止的只是多个线程同时拿锁而已，一旦拿锁的动作完成（不管是否拿到锁），guard都将被设置为0。
而这个范围很小。在拿到锁的情况下, guard保护的只有if(value == FREE)的条件判断和value=BUSY的赋值语句。在没有拿到锁的情况下，guard保护的语句只有将自己这个线程加到等待队列和切换线程的一段代码。
该实现中存在一个问题。假如在将自己放在等待队列后，执行切换操作前突然发生线程切换，那么本线程将同时处于等待和就绪两个队列。这个问题是怎么解决的呢？
解决办法也很简单，就是将执行lock这个系统调用的进程的优先权提高，以使这种情况发生的概率降低。当然，完全避免是不可能的。
参考资料：
《操作系统之哲学原理》 邹恒明著
网友评论