[OS] 进程互斥

对互斥的正确软件实现算法（面包店算法）是非常耗时的，现代的计算机系统都会提供简单的硬件指令，使用这些指令能够有效地解决临界区问题。

硬件提供一个TestAndSet指令，来实现原子指令的功能：

1 bool TestAndSet(bool *target)
2 {
3     bool rv = *target;
4     *target = true;
5     return rv;
6 }

在执行上述TestAndSet()函数时是不可以被打断的，因此可以使用以下方法来实现进程的同步：

 1 do
 2 {
 3     //剩余区
 4     
 5     waiting[i] = true;//表示进程Pi处于等待获取锁的状态
 6     key = true;
 7     while(waiting[i]&&key)
 8         key=TestAndSet(lock);//如果进程Pi抢到了锁，记录key=false
 9     waiting[i]=false;
10 
11     //临界区
12 
13     j=(i+1)%n;
14     while(j!=i && !waiting[j])//进程Pj处于等待获取锁的状态
15         j = (j+1)%n;
16     if(j==i)
17         lock = false;
18     else
19         waiting[j] = false;
20 
21     //剩余区
22 }
23 while(true);

临界区条件1：互斥
第一个进入的进程Pi要等执行了TestAndSet之后才能进入，这时Pi的key=false,其他进程key=true;后续进入的进程Pi，只有在其他进程将waiting[i]设为false之后，才可能进入。
临界区条件2：空闲让进
初始，key和所有的waiting[i]都为True，lock=false,因此首次执行TestAndSet的进程会进入临界区。当进入临界区的进程Pi执行完临界区操作之后，在退出区，通过While循环扫描当前处于等待状态的进程j (j!=i)，如果找到j，那么waiting[j]被设为false,Pj会随后进入临界区如果没有找到j，那么lock被置为false。总之，只要临界区资源空闲，想进入临界区的进程（其waiting[j]=true）都会被放进临界区。
临界区条件3：有限等待
每个进程退出临界区的时候，总会按顺序执行一个扫描，这个循环扫描的过程保证一个进程最多等待n-1次即可进入临界区操作。