互斥是当一个进程在临界区访问共享资源时，其他进程不能进入该临界区访问任何共享资源。
互斥的实现有两个方面：
- 硬件支持
- 软件设计
硬件支持
- 禁用中断，指的是在线程执行临界区代码过程中不可中断，即不会把CPU的时间片交出去，直到执行完成。这种方式在多处理器的系统中不能保证互斥，且即使在单核系统中能实现互斥，代价也是很大的。
- 专用的机器指令
包括比较和交换指令（CompareAndSwap，CAS）和交换指令（exchange）；
在硬件级别上，对存储单元的访问排斥对相同单元的其他访问。基于这一点，处理器的设计者提出了一些机器指令，用于保证两个动作的原子性，如在一个取指令周期中对一个存储器单元的读和写或者读和测试。在该指令执行的过程中，其他指令访问内存将被阻止。而且这些动作在一个指令周期中完成。
比较和交换：
// 用一个测试值检查一个内存单元（*word），如果该内存单元的当前值是testval，就更新为新值，否则不变。
int compare_and_swap(int *word,int testval,int newval){
int oldval;
oldval = *word;
if (oldval == testval)
{
*word = newval;
}
return oldval;
}
处理器保证以上操作是原子操作，不可中断。
交换指令：
// 交换一个寄存器的内容和一个内存单元的内容
void exchange(int register,int memory){
int temp;
temp = memory;
memory = register;
register = temp;
}
对互斥的支持实现：
CAS:
const int n = /*进程数*/
int bolt;
void p(int i){
// bolt==0时，bolt会被更新为1，并且CAS返回0，可以跳出轮询进入临界区代码
// 换个解释就是如果bolt==1,就一直等待，直到bolt==0
while(compare_and_swap(bolt,0,1)==1){
/*不做任何事*/
}
/*临界区代码*/
bolt = 0;
}
}
void main(){
bolt =0;
pargin(p(1),p(2),...p(n));
}
exchange:
const int n = /*进程数*/
int bolt;
void p(int i){
int keyi = 1;
while(true){
// 轮询直到bolt==0,会和keyi交换，使得keyi=0,bolt=1，从而跳出循环
// 也即直到bolt==0，才能进入临界区代码
do exchange(keyi,bolt)
while(keyi != 0);
/*临界区代码*/
bolt = 0;
}
}
void main(){
bolt =0;
pargin(p(1),p(2),...p(n));
}
机器指令方法的特点：
（1）优点
- 适用于单处理器或共享内存的多处理器
- 简单且易于证明
- 可用于支持多个临界区，每个临界区可以使用其自己的变量定义
（2）缺点 - 使用了忙等待
- 可能饥饿
- 可能死锁
程序设计语言机制
- 互斥量（基于二元信号量）
- 管程（monitor）（基于互斥量的结构）
java synchroized的实现基础就是monitor
信号量
信号量是多线程协作的一个共享变量，是进程（线程）间传递信号的一个整数值。它有三种原子操作：初始化、递减（P）和递增（V）。
递减操作可以用来阻塞一个线程，递增操作可以用来唤醒一个线程。
信号中包括一个整形变量，和两个原子操作P和V，其原子性由操作系统保证，这个整形变量只能通过P操作和V操作改变。
P意味着信号量值减1，减完之后如果信号量值小于0，则说明资源不够用的，把进程加入等待队列。
V意味着信号量值加1，加完之后如果信号量值小于等于0，则说明等待队列里有进程，那么唤醒一个等待进程。
通常，信号量是用来控制执行临界区代码的并发线程数。
当线程进入由信号量保护的代码时，先将信号量的值减一，如果减一后值为负数，则此线程阻塞，否则可以继续执行；
当线程离开信号量保护的代码时，信号量加一，如果值小于或等于0，说明有线程由于递减操作后阻塞，就将阻塞队列的其中一个线程解除阻塞。
也就是这种情况下，PV是要成对出现在临界区前后的。
信号量的等待进程被放在等待队列中，按先进先出的次序执行。
自旋锁不能保证进程按先进先出的次序执行，因为自旋锁的所有等待进程都在循环中忙等待，在临界区释放的那一刻，先检查到临界区为空的进程先进入临界区，没有先来后到之分
所以信号量的初始值是可以正常执行临界区代码而不会被挂起的线程数，如果信号量初始化是初始值为1，则同一时刻只能有一个线程执行临界区代码，也就可以构成互斥的条件。这个情况下的信号量，叫做二元信号量。
根据S初始值的不同，semaphore就有不同的作用。如果S初始值为1，那么这个semaphore就是一个mutex semaphore，效果就是临界区的互斥访问。如果S初始值为0，那么就是用来做条件同步，效果就是必须等待某些条件发生。如果S初始值为N（N一般大于1），那么就是用来限制并发数目，也被称之为counting semaphone。
信号量在现实生活中很容易找到对比的例子，比如银行的窗口数量就是S，在窗口办理业务就是P操作，业务办理结束就是V操作。
- 使用信号量的缺陷
读/开发代码比较困难，而且PV在不同的线程里配对，容易写错。而且必须先检查资源信号量的值，再进入临界区（即先写emptyBuffers->P(),再写mutex->P())，否则所有线程都不能进入临界区
管程
管程是编程语言提供的一种抽象数据结构，用于多线程互斥访问共享资源。首先，是互斥访问，即任一时刻只有一个线程在执行管程代码；第二，正在管程内的线程可以放弃对管程的控制权，等待某些条件发生再继续执行。
管程是为了解决信号量在临界区的PV操作上的配对的麻烦，把配对的PV操作集中在一起，生成的一种并发编程方法。其中使用了条件变量这种同步机制。
管程与临界区不同的是，在管程中的线程可以临时放弃管程的互斥访问，让其他线程进入到管程中来。而临界区中的线程只能在线程退出临界区时，才可以放弃对临界区的访问。
信号量 VS 管程
信号量与管程都能够解决我们编程中遇到的同步互斥问题，二者本质上时互通的，hoare在论文中也证明了可以用信号量实现管程、也可以用管程实现信号量。
简单归纳一下二者的区别：
- 信号量本质是可共享的资源的数量； 而管程是一种抽象数据结构用来限制同一时刻只有一个线程进入临界区
- 信号量是可以并发的，并发量取决于S初始值；而管程内部同一时刻最多只能有一个线程执行
- 信号量与管理的资源紧耦合（即信号量S的初始值等同于资源的数目，且通过PV操作修改剩余可用的资源数量）；而在管程中需自行判断是否还有可共享的资源。这一点可以参见下面生产者消费者的实现代码
- 信号量的P操作可能阻塞，也可能不阻塞；而管程的wait操作一定会阻塞
- 信号量的V操作如果唤醒了其他线程，当前线程与被唤醒线程并发执行；对于管程的signal操作，要么当前线程继续执行（Hansen），要么被唤醒线程继续执行（Hoare），二者不能并发。
参考资料
[1] 操作系统原理与设计精髓
