上一篇中提到的Peterson算法是一种基于软件的解答，但是并不保证在现在多核计算机的体系结构中正确工作。下面我们来探讨临界区问题的多个解答。
硬件同步
对于单处理器环境，临界区问题可简单的加以解决：在修改共享变量的时候只要禁止中断。这样就能保证当前指令正确的执行，且不会被抢占。
然而，在多处理器环境，多处理器的中断禁止会很耗时，因为消息要传递到所有的处理器。消息传递会延迟进入临界区，并且降低多核的效率。另外，如果系统时钟是终端来更新的，那么问题就更复杂了。
因此，许多的现在系统提供特殊的硬件指令，用于检测和修改字的内容，或者用于原子的交换两个字（作为不可终端的指令）。它们通过这些特殊的指令，相对简单的解决临界区问题。
这里仅以test_and_set()指令为例来说明：
test_and_set.png
test_and_set()的指令是原子的。因此，不论CPU如何并发的执行，在指令上，test_and_set是不能被打断的。因此可以把临界区问题这样实现
test_and_set1.png
互斥锁
上面的方法是基于硬件实现的，在临界区问题上，应用程序设计人员能用到最简单的工具就是互斥锁（mutex lock)。
利用互斥锁的临界区问题的结构为：
mutex_lock.png
这里可以看到，一个进入临界区时应该得到锁；在退出时释放锁。
在这个结构中，我们给出acquire() 和release()的定义：
// available 表示锁是否可用
acquire() {
// 如果临界区不可用，进行忙等待。
while (!available) ;
available = false;
}
release() {
available = true;
}
这里实现的一个缺点是：他需要忙等待。一般在实现时，互斥锁都是采用硬件来实现的。
这里介绍的这个方法处于忙等待。 一般把 在访问临界区时，不断地要通过忙等待判断锁是否可用的互斥锁称为 自旋锁（spin lock）
自旋锁与互斥锁有点类似，但是自旋锁不会引起调用者阻塞，如果自旋锁已经被别的执行单元保持，调用者会一直循环检查该自旋锁的保持者是否已经释放了锁，所以才叫自旋。自旋锁是忙等待，互斥锁是挂起阻塞。
自旋锁的有点：自旋锁一般持有的代码段耗时比较短，当进程获取到自旋锁后，不用进行上下文的切换。
自旋锁一般用于多核系统中，自旋锁在一个处理器上"旋转"，其他线程在其他核上执行命令。
信号量
信号量是线程同步中另一种方法。
通常信号量是一个整数变量。信号量一般由两个操作wait() 和signal()，wait()操作称为P操作(荷兰语：proberen，测试) ，signal()称为V操作(荷兰语: verhogen,增加)。
信号量一般根据使用情况分为计数信号量和二进制信号量。
二进制信号量可以当做互斥锁来用。
计数信号量可以用于控制访问具有多个实例的某种资源。
P操作：当一个线程程执行操作wait()并且发现信号量值不为正的时候，他必须等待，这里的等待不是忙等待，而是阻塞自己，把自己放入到和信号量有关的队列中。
V操作：当阻塞的线程等到其他线程执行了signal()操作后，线程会被wakeup(),将它从I/O队列加入到就绪对列中。
忙等待的信号量的实现是：
wait(S) {
while (s <= 0)
; // busy wait
S--;
}
signal(S) {
S++;
}
阻塞的信号量的实现为：
typedef struct {
int value;
struct process * list; // 进程的队列
} semaphore;
wait (semaphore& s) {
s.value -- ;
// 如果value 的值小于它们的使用量，把进程加入到队列中进行挂起
if (s.value < 0) {
/* add this process to s.list */
block();
}
}
signal(semaphore & s) {
s.value++；
// 如果s->value的绝对值 表示挂起的队列的长度，如果挂起队列有值，就唤醒一个进程
if (s->value <= 0) {
remove a process from s.list;
wakeup();
}
}
死锁和饥饿
虽然上面的的进程队列，可以避免忙等待的情况，但是具有等待队列的信号量实现可能导致： 两个进程或者多个进程，无限等待一个事件，而该事件只有由等待的进程之一来产生，就会出现死锁。
看下死锁的情况：
假设有一个系统，它有两个进程，P0和P1，每个访问共享信号的S和Q，这两个的初始值都为1。
deallock.png
这里就会看到，P0进程在等待P1进程的S,Q, P1进程在等待进程的P0的Q,S； 由于执行顺序的不确定，就会导致死锁。
除此之外，如果进程无限等待信号量而得不到执行，那么我们称这类问题为 饥饿。即信号量有关的信号有关的队列按照后进先出的顺序来增加和删除，第一个信号量将一直得不到响应。
优先级反转
假设有三个进程，L，M和H，他们的优先级顺序为L< M < H。假定进程H需要资源R，而R被进程L访问。通常进程H将等待L用完资源R，但是在假设M在这个过程中进入了可运行状态，从而抢占了L，从而导致了进程优先级低的M影响了H的执行，这种问题就是优先级翻转。
在解决这类问题的时候，采用了优先级继承协议。
比如：上面的例子中，优先级继承协议将允许有关进程L临时继承进程的H的优先级，从而防止M抢占执行。当进程L用完资源R后，它将放弃继承的进程H的优先级，从而采用原来的优先级。
管程
利用信号量可以同一种方便有效的进程同步机制，但是他们产生的错误也是难以检测到的，具体例子请参考下一节要讲的《线程同步经典问题系列》。
为了解决这类问题，操作系统义工了管程的概念。
管程其实是一种语法定义的数据和函数的集合。就类似于一个函数，但是它可以保证在管程的这段结构代码里，每次只有一个进程在管程内处于活动状态。
monitor管程.png
而且管程在进行同步时，是下面的结构，一次只有一个管程在代码段中执行，其他都在入口队列中排队。
管程的执行模式.png
进入管程时的互斥是由编译器负责，但通常是用一个互斥量的方式来进行的。虽然管程提供了一种实现互斥的方法，但是，当进程无法继续运行的是被阻塞。比如：在生产者-消费者中，我们怎么让生产者在缓冲区满的时候阻塞呢？
解决的办法就是，一个新的同步机制条件变量；
条件变量一般只有两个操作：wait()和signal();
当一个管程无法继续运行时，它会在某个条件变量上执行wait();该操作使得调用线程自身阻塞直到其他管程执行signal()，并且还将另外一个以前在等待管程之外的线程调入管程。
条件变量
一般条件变量和互斥量是一起使用的。
这种模式用于让一个线程锁住一个互斥量，然后当它不能获得某个结果的时候，挂起并等待一个条件变量。
比如生产者消费者中，假设生产者缓冲区满了，需要阻塞，那么,
可以使用条件变量将其阻塞。
pthread_mutex_lock(&mutex);
while( bufffer != 0) pthread_cond_wait(cond, mutex);
// buffer[n] = A;
pthread_cond_signal(cond);
pthread_mutex_unlock();
条件变量的wait操作一般干了三件事：
1、给互斥锁解锁
2、把调用线程投入睡眠，直到另外某个线程就本条件调用signal。
3、然后，在返回前重新给互斥锁上锁（没有获得锁时一直阻塞在这里）
（具体的调用放在后面的对线程同步的API讲解）。
死锁
前面提到了死锁。这里对死锁进行几个概念性的总结。
如果在一个系统中一下四个同时满足，那么就有可能引起死锁：
- 互斥。 必须至少有一个资源只能允许一个线程使用。
- 占用并等待。一个线程应该占有一个资源并且的等待其他资源。
- 非抢占。 资源不能被抢占。
- 循环等待。 有一组等待进程(P0,P1,....Pn), P0等待的资源P1占用，P1的资源P2占用...., Pn等待的资源P0占用，形成一个死循环。
网友评论