临界区算法：Peterson与面包店算法
读写信号量的代码一定是临界区，只能有一个线程进入执行。
临界区算法需要满足：
- 互斥进入：只有一个线程能进入临界区执行代码。
- 有空让进：没有线程在临界区执行时，对于新线程需要进入临界区则肯定能进入。
- 有限等待：线程不能无限等待进入临界区。即不能某个线程一直霸占临界区一直执行。
以下其两种算法都以并行方式考虑。对于并发，当它无法进入临界区时会等待（下述算法以while空循环实现），到时间片用完时会进行调度，所以效果其实类似并行，对于并行、并发对于算法没有太大影响，所以下述两种算法都考虑并行。
Peterson算法
针对两个进程，结合了标记和轮转两种思想。
标记flag是为了告知另一个进程我将要进入临界区，另一个进程发现了我的flag则可能需要把自己阻塞（不是线程意义上的阻塞，而是while空循环）而让另一个执行，执行完后再把flag设置回去。
这里说的可能是因为，当两个同时进入需要进入临界区时，flag都被设置，则两个都会把自己阻塞，那么都无法进入临界区，就不满足有空让进。
所以，需要一个turn来分主次。轮到对应的turn时，才会阻塞自己。同时，每次执行都会修改turn，那么他就不会一直循环执行，从而实现有限等待。
算法示例：
// 进程P0
flag[0] = true;
turn = 1;
while(flag[1] && turn == 1) ;
// 临界区
flag[0] = false;
// 剩余区
// 进程P1
flag[1] = true;
turn = 0;
while(flag[0] && turn == 0) ;
// 临界区
flag[1] = false;
// 剩余区
Peterson算法满足：
-
互斥进入：两进程并行时，flag[0]、flag[1]都为true（某个为false则表明该进程并未执行），两线程都会设置turn，只是先后的问题，那么两个进程的while循环条件只会有一个满足而执行空循环，只会有一个进入临界区执行，执行完后把flag设置为false则让另一个跳出while循环而进入临界区。
那么当某个线程已经在临界区执行时，另一个能否进入临界区呢？假设当P0进入临界区执行，则P1是无法进入临界区的。因为P0在临界区执行的时候，flag[0]肯定为true，满足P1循环的第一个条件。同时turn也被修改为0，满足第二个条件，则会进行while循环，无法进入临界区。
-
有空让进：若只有一个线程执行，比如P0，那么flag[1]肯定是false，能进入临界区。若两个线程都执行，turn只取得一个值，使得肯定有一个线程不满足while循环从而可以进入临界区。
-
有限等待：两进程并行，若P0在等待，这里就是进入while循环，P1执行完一次后，他在下次执行临界区前P0必定会执行了临界区。因为P1下次执行要求while条件不满足，而P0在等待时标记了flag告诉P1我要执行，而且P1执行时，轮次turn也修改为了P0，只有P0执行完临界区后，修改了他自己得flag，P1才可以执行下一次。
面包店算法
同样是结合了标记和轮转两种思想，不过是针对于多个进程。
对于标记，只要不为0则表示我需要进入临界区。
对于轮转，每个进程都会取一个号码，为当前所有号码最大值加一。相当于排队取号。
只有标记了自己并且是最小号才能进入临界区。
这里需要注意一个问题，（这里是我自己推测的），当一个新进程在取号的时候，原本存储号的空间原本就有值，而取号时是一连串的指令，中途可能会调度，所以其他进程进行比较时可能比较的是旧值，这里就要要求比较前，对应进程需要完成取号。
算法示例：
// 进程Pi
choosing[i] = true;
num[i] = max(num[0], ..., num[n - 1]) + 1;
choosing[i] = false;
for (j = 0; j < n; j++)
{
while(choosing[j]) ;
while( (num[j] != 0) && (num[j], j) < (num[i], i) ) ;
}
// 临界区
num[i] = 0;
// 剩余区
面包店算法满足：
- 互斥进入：Pi在临界区时，对于另一个进程Pk，肯定满足(num[i], i) < (num[k], k)，则会执行while循环。
- 有空让进：没有进程在临界期时，最小号的进程肯定能进入。
- 有限等待：一个进程执行完后，下次取号肯定是最大的，只有相较小号的线程执行完才能继续执行。
其他方法
上述两种方法都是软件实现的。但其实可以通过硬件实现。
关中断
此方法只适用于单处理器/单核，在进入临界区执行时关中断（关闭INTR），执行完后开中断，则不会进行调度，只会有一个进程在临界区执行。
硬件原子指令法
在执行临界区时，先对某个变量上锁，执行完后再对该变量开锁。而上锁开锁，就是通过硬件来实现”一步指令“，即中途无法被调度。如以下示例中，testAndSet中代码一次执行完，无法被调度：
boolean testAndSet(boolean& x)
{
boolean rv = x;
x = true;
return rv;
}
while(testAndSet(lock)) ;
// 临界区
lock = false;
// 剩余区