|

楼主 |
发表于 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; // 退出临界域
}
|
|