|
|
楼主 |
发表于 2016-5-5 11:46:54
|
显示全部楼层
以下文字摘自《Windows 并发编程指南》，版权归原作者所有，仅供学习和研究参考。
对于任何良好的临界域实现方式来说，都存在一系列的需求。
1. 保持互斥性，无论在什么情况下，只能有一个线程可以进入临界域。
2. 保证进入临界域和退出临界域等操作的活跃性(Liveness)。系统可以不断地向前推进，这意味着这个算法既不能产生死锁，也不能产生活锁。具体来说，如果给定无限长的时间，那么每个到达临界域的线程都将进入临界域，没有任何线程会无限期地停留在临界域中。
3. 提供某种程度的公平性，例如根据线程到达临界域的时间来确定它相对于其他线程的优先级。虽然这并不意味着必须存在某种确定的公平性保证(例如先进先出)，但临界域经常会努力实现某种程度的公平性。
4. 另一个主观意义上的标准就是低开销。在进入临界域和离开临界域时保持较低的开销是非常重要的。在底层的系统软件中经常会大量地使用临界域，例如操作系统，因此在临界域的实现效率上存在着很大的压力。
可以采用多种方法来实现临界域。不过，目前所有的互斥机制都依赖于一组原子的比较和交换(Compare and Swap, CAS)硬件指令以及操作系统的支持。但在介绍这些指令之前，我们首先看看为什么需要硬件来提供支持。换句话说，通过我们熟悉的串行编程结构来实现EnterCriticalRegion和LeaveCriticalRegion难道不是很容易吗？
这种最简单，最初级的方法根本就不可行。我们可以设计一个标志变量，初始值为0，当有线程进入到临界域时将这个变量设置为1，而在离开临界域时设置为0,。每个试图进入临界域的线程都将首先检查这个标志，如果这个标志为0，这进入临界域并且将标志设置为1.
[cpp] view plain copy
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，此时就完成了对临界域中代码的执行。这种方式的实现形式可能像下面的代码这样：
[cpp] view plain copy
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。
下面的代码给出了完整的算法
[cpp] view plain copy
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; // 退出临界域
}
|
|
