以下文字摘自《Windows 并发编程指南》，版权归原作者所有，仅供学习和研究参考。
对于任何良好的临界域实现方式来说，都存在一系列的需求。
1. 保持互斥性，无论在什么情况下，只能有一个线程可以进入临界域。
2. 保证进入临界域和退出临界域等操作的活跃性(Liveness)。系统可以不断地向前推进，这意味着这个算法既不能产生死锁，也不能产生活锁。具体来说，如果给定无限长的时间，那么每个到达临界域的线程都将进入临界域，没有任何线程会无限期地停留在临界域中。
3. 提供某种程度的公平性，例如根据线程到达临界域的时间来确定它相对于其他线程的优先级。虽然这并不意味着必须存在某种确定的公平性保证(例如先进先出)，但临界域经常会努力实现某种程度的公平性。
4. 另一个主观意义上的标准就是低开销。在进入临界域和离开临界域时保持较低的开销是非常重要的。在底层的系统软件中经常会大量地使用临界域，例如操作系统，因此在临界域的实现效率上存在着很大的压力。
可以采用多种方法来实现临界域。不过，目前所有的互斥机制都依赖于一组原子的比较和交换(Compare and Swap, CAS)硬件指令以及操作系统的支持。但在介绍这些指令之前，我们首先看看为什么需要硬件来提供支持。换句话说，通过我们熟悉的串行编程结构来实现EnterCriticalRegion和LeaveCriticalRegion难道不是很容易吗？
这种最简单，最初级的方法根本就不可行。我们可以设计一个标志变量，初始值为0，当有线程进入到临界域时将这个变量设置为1，而在离开临界域时设置为0,。每个试图进入临界域的线程都将首先检查这个标志，如果这个标志为0，这进入临界域并且将标志设置为1.
int taken = 0;
void EnterCriticalRegion()
{
while(taken != 0) // 忙等待
taken = 1; //表示临界域已经被获取了
}
void LeaveCriticalRegion()
{
taken = 0; //表示临界域已经被释放了
}
这种实现方式非常糟糕。原因在于，在算法中使用的一系列读操作和写操作都不是原子的。假设有两个线程在读取taken时都获得了0，并且根据这个信息都决定将1写入taken。这两个线程都会认为自己获得了这个临界域，但它们却在同时运行临界域中的代码。这正是我们最初使用临界域所要避免发生的事情。
在分析现有的技术之前，即在现代临界域中使用的技术，我们将首先回顾过去40多年中在互斥的实现方式上经历的曲折发展道路
严格交替
我们首先可能会尝试通过严格交替(Strict Alteration) 来实现互斥行为，首先将所有权交给线程0，然后线程0在执行完时再把所有权交个线程1，而线程1在执行完成时又接着把所有权交给线程2，以此类推，直到N个线程，最后由线程N-1将所有权交回给线程0，此时就完成了对临界域中代码的执行。这种方式的实现形式可能像下面的代码这样：
const int N= ....; //系统中线程的编号
int turn = 0； //线程0首先执行
void EnterCriticalRegion(int i)
{
while(turn != i) // 忙等待
// 其他某个线程将所有权交给了我们，现在我们拥有临界域
}
void LeaveCriticalRegion(int i)
{
//将所有权交回给下一个线程(可能交回到线程0)
turn = （i+1) % N;
}
这个算法能够实现N个并发线程在使用临界域时的互斥性。在这种模式中，每个线程都有一个唯一的标识，取值范围为【0....N】,这个标识将被作为参数i的值传递给EnterCriticalRegion。变量turn表示当前哪个线程被允许在临界域中执行，并且当线程试图进入临界域时，它必须等待另一个线程将所有权交给它，在上面的示例中使用的是忙等待。在这个算法中，我们必须指定哪个线程最先执行，在示例中选择线程0首先执行并且在外部将turn初始化为0.在离开临界域时，每个线程都要通知下一个线程开始执行：设置相应的turn，如果达到了线程的最大数量，则将turn回卷为0，否则将turn递增1。
在严格交替中存在一个问题：在决定将临界域的所有权交给某个线程时，并没有考虑线程到达临界域的时间。相反的是，在算法中存在一种预定义的顺序：首先是0，然后是1，---，N-1，然后又回到0，等等。这种顺序是固定的，不可修改。这种顺序不可能是公平的，它经常导致一个不在临界域中的线程阻碍另一个线程进入临界域。这可能会降低系统的活跃性，但却会降低程序的性能和可伸缩性。只有当线程有规律地进入临界域和退出临界域时，这个算法才能发挥作用。另一个问题是，在临界域中不能容纳可变数量的线程。我们很难知道有多少个线程将进入某个临界域，并且更难知道线程的数量在进程的生命周期中是否保持不变。
Dekker和Dijkstra提出的算法(1965)
在第一个被广泛接受的互斥问题解决方案中并没有使用严格交替，它是由一位读者在回应E.W.Dijkstra于1965年发表的一篇文章时提出的，Dijkstra在这篇文章中提出了互斥问题，并且寻求对这个问题的解决方案。一个叫做T.Dekker的读者提交了一个解决方案能够满足Dijkstra的标准，但只能适用于两个并发的线程。这种算法称为“Dekker算法”，Dijkstra随后在同年发布的另一篇文章中扩展了这种算法使其可以适用于N个线程。
Dekker提出的解决方案与严格交替是类似的，都需要分配次序，但在这个解决方案中，每个线程可以表示是否希望进入临界域。当一个线程想要进入临界域但却还没有轮到它的次序时，它可以“窃取”其他不打算进入临界域(即不在临界域中)的线程的次序。
在下面的示例中定义了一个共享的布尔数组flags，这个数组包含两个元素并且都被初始化为false。当线程希望进入临界域时，它将true保存到相应位置的元素中（线程0使用下标为0的元素，线程1使用下标为1的元素），并且在退出时将false写入这个元素。当且仅当线程希望进入临界域时才执行这些操作。这种方式是可行的，因为线程首先写入到一个共享的数组flags，然后判断另一个线程是否也已经写入到数组flags。我们可以确保，如果将true写入flags，然后从另一个线程对应的元素中读取false，那么另一个线程将看到这个true值。（注意，在现代处理器中是以乱序方式来执行读操作和写操作，这种执行方式将破坏这种假设。）
在算法中必须处理这两个线程同时进入临界域的情况。算法通过共享变量turn来做出决策，正如在前面已经看到的情形。就像在严格交替中，当两个线程都希望进入临界域时，只有当其中一个线程看到turn等于它自己的索引时，才会进入到临界域，而其他的线程将不再希望进入（也就是，它在flags中元素的值为false）。如果某个线程发现两个线程都希望进入但却还没有轮到它的次序，那么这个线程将“后退”并且将它的flags元素设置为false，然后等待turn 发生变化。这就使另一个线程进入临界域。当线程离开临界域时，它只是将对应的flags元素重置为false，并且修改turn。
下面的代码给出了完整的算法
static bool[] flags = new bool[2];
static int turn = 0;
void EnterCriticalRegion(int i) // i只能是0或者1
{
int j = 1-i; //另一个线程在flags中的索引
flags[i] = true; // 表示希望进入临界域
while(flags[j]) //等待直到另一个线程不希望进入临界域
{
if(turn == j) //还没有轮到我们，因此必须后退并且等待
{
flags[i] = false;
while(turn == j) // 忙等待
flags[i] = true;
}
}
}
void LeaveCriticalRegion(int i)
{
turn = 1-i; // 让出次序
flags[i] = false; // 退出临界域
}
Dijkstra对这个算法进行了修改以支持N个线程。虽然这个算法仍然要求N是一个确定值，但它能够适用于线程数量小于N的系统，从而使得算法更为适用。
这个算法与Deckker的算法略微不同。首先定义一个大小为N的数组flags，但数组中的元素不是布尔类型而是一种三值（Tri-Value)类型。每个元素的值都可以是以下三个值之一： passive，表示这个线程此时不打算进入临界域；requesting,表示这个线程正在尝试进入临界域；active，表示这个线程当时正在临界域中执行。
线程在到达临界域时，它将把数组flags中的对应元素设置为requesting以表示希望进入临界域。然后，它将尝试“窃取”当前的次序：如果当前的次序被分配给一个并不打算进入临界域的线程，那么这个已达到的线程将把turn设置为它自己的索引。一旦这个线程获得了turn，那么它将把状态设置为active。然而，在线程继续执行之前，它必须验证没有其他的线程在同时也窃取了次序并且可能已经进入到了临界域，否则将破坏互斥行为。具体的验证方式就是确保没有其他线程的标志是active。如果发现了另一个活跃的线程，那么这个已到达的线程将后退并且回到requesting状态，并且直到它能进入临界域才继续执行。当线程离开临界域时，它会将相应的标志设置为passive。
下面是一个用C#编写的示例实现。
const int N = ...; // 可以进入临界域的线程编号
enum F ： int
{
Passive,
Requesting,
Active
}
F[] flags = new new F[N]; // 所有元素被初始化为passive
int turn = 0;
void EnterCriticalRegion(int i)
{
int j;
do
{
flags [ i] = F.Requesting; // 表示希望进入临界域
while(turn != i) // 保持自旋，直到轮到自己的次序
if（flags[turn] == F.Passive)
turn = i; // 窃取次序
flags[i] = F.Active; // 宣告正在进入临界域
//确保没有其他的线程已经进入到临界域
for(j = 0; j<N &&(j == i || flags[j] != F.Active); j++);
}
while (j<N);
}
void LeaveCriticalRegion(int i)
{
flags[i] = F.Passive // 表示离开临界域
}
Peterson提出的算法(1981)
在Dekker算法发布了大约16年之后，G.L。Peterson提出了一种简化算法，并且在它的文章”Myths about Mutual Exclusion“ 中给出了详细的描述。这种算法简称为Peterson算法。在不到两页的篇幅中，他给出了一个适用于两个线程的算法，以及一个适用于N线程的算法，这两个算法都比Dekker和Dijkstra最初提出的算法要简单。
为了简单起见，我们这里只介绍适用于两个线程的算法。共享变量都是相同的，包括一个flags数组和一个turn变量，这与Dekker算法是一样的。然而，与Dekker算法不同的是，当线程希望进入临界域时，它将首先把flags中对应的元素设置为true，然后立即把turn让给其他的线程。接下来，这个线程将等待另一个线程不在临界域中或者知道turn值重新回到这个线程。
bool[] flags = new bool[2];
int turn = 0;
void EnterCriticalRegion(int i)
{
flags[i] = true; // 表示希望进入临界域
turn = 1-i;
//等待直到临界域可用或者轮到了我们的次序
whle(flags[1-i] && turn != i) // 忙等待
}
void LeaveCriticalRegion(int i)
{
flags[i] = false; // 退出临界域
}
与Dekker算法一样，Peterson算法同样盲足所有基本的互斥性、公平性以及活跃性。但这个算法更为简单，因此在讲解互斥时比Dekker算法用得更多。
Lamport提出的Bakery算法(1974)
L.Lamport同样提出了一种算法，称为Bekery算法。这种算法能够很好地适用于不同数量线程的情况，此外这个算法的好处在于，如果某个线程在进入临界域或者退出临界域发生失败，那么并不会破坏系统的活跃性，而在之前介绍的其他算法中都存在这个问题。所要求的就是，这个线程必须将它的票号(Ticket Number)重新设置为0并且移动到非临界域。Lamport希望将它的算法应用与分布式系统中，因为在任何一个分布式系统算法中，容错(Fault Tolerance)都是一个非常关键的属性。
这个算法称为Bakery(面包店)算法，主要是因为它的工作原理有点类似于面包店的运作方式。当一个线程到达时，它将获得一个票号，只有当这个线程的票号被叫到时（或者更准确地说，只有当那些票号更小的线程都已经执行完毕后），这个线程才被允许进入临界域。这个算法能够正确地处理边界情况：多个线程通过线程之间的某种排序方式被分配到了同一个票号-------例如，唯一的线程标识、名字或者其他可进行比较的属性-------这种情况将破坏平衡。以下是这个算法的示例实现。
const int N= ....; //可以进入临界域的编程编号
int[] choosing = new int[N];
int[] number = new int[N];
void EnterCriticalRegion(int i)
{
// 让其他线程知道正在选择一个票号
// 然后找到当前最大的票号并且加1
choosing[i] = 1;
int m = 0;
for(int j = 0; j<N; j++)
{
int jn = number[j];
m = jn > m? jn : m;
}
number[i] = 1+ m;
choosing[i] = 0;
for(int j=0; j<N; j++)
{
//等待线程完成选择
while(choosing[j] != 0) //忙等待
//等待拥有更低票号的线程执行完成。如果获得了与另一个线程相同的票号，
// 那么ID值最小的线程将首先进入
int jn;
while((jn = number[j]) != 0 && (jn == number[i] && j<i)))
//忙等待
}
//叫到我们的票号，进入临界域....
}
void LeaveCriticalRegion( int i)
{
number[i] = 0;
}