有关“活锁“的疑问

tomkedy

1）以下是我看到的一个有关“活锁“的例子，
------------------------------------------------------------

void process_A(void)
{
A1:        enter_region(&resource_1);
A2:        enter_region(&resource_2);
A3:        use_both_resources();
A4:        leave_region(&resource_2);
A5:        leave_region(&resource_1);
}

void process_B(void)
{
B1:        enter_region(&resource_2);
B2:        enter_region(&resource_1);
B3:        use_both_resources();
B4:        leave_region(&resource_1);
B5:        leave_region(&resource_2);
}

该书中对以上代码例子的介绍如下：
.......
假设有一对进程使用2种资源，如上代码，每个进程都需要2种资源，它们利用轮询原语尝试取得必要的锁，如果尝试失败，则该进程继续尝试。如果进程A先运行并得到资源1，然后进程2运行并得到资源2，以后不管哪一个进程运行，都不会有任何进展，但是哪一个进程也没有阻塞。结果2个进程总是一再消耗完分配该它们的CPU配额，但是没有进展也没有阻塞（没发生死锁）。但从现象上看像是发生了死锁，因此叫活锁（livelock）
.......

------------------------------------------------------------


2）以下是我对上面这段话的模拟：

由于进程A先运行，因此在A1时间点，进程A获得了resource_1的锁。但进程A还没有进入时间点A2就被剥夺了CPU，系统切换到进程B，这时在时间B1，进程B获得了resource_2的锁。

接下来，假设进程B也马上被剥夺了CPU（还未到B2时间点），则系统切换到进程A。这时，进程A处于时间点A2，但它不能获得resource_2的锁，因为该锁已被进程B获得，因此进程A只能“忙等待“（阻塞）。不久后，进程A被剥夺CPU并且系统切换到进程B，进程B进入时间点B2，但它同样不能获得resource_1的锁，因为该锁为进程A所有，所以它也只能像进程A一样等待。那这个应该是一个“死锁“的例子吧，为何会是“活锁“？

tomkedy

回复 1# tomkedy


   顶

tempname2

跟死锁基本类似。区别大概是死锁block forever，活锁run forever。

tomkedy

跟死锁基本类似。区别大概是死锁block forever，活锁run forever。
tempname2 发表于 2011-06-13 21:42

我从例子中的文字理解，与你的基本一致；但是结合代码例子，似乎得出的是“死锁“，为何？是不是我分析错了？

tempname2

回复 4# tomkedy

每个进程都需要2种资源，它们利用轮询原语尝试取得必要的锁，如果尝试失败，则该进程继续尝试

类似自旋锁的东西。

这种情况应该是极端严重的starvation。

vupiggy

你说的没错，那那段代码是死锁，给该书作者写信吧。活锁发生以后运气好的时候仍然是可以走出来的，死锁则永远等待，没有任何机会。

活锁大多有一个解锁过程寄希望于另一方可以先走，大概是这样的：

1. 
   
2. /* 线程1，2都必须获得两把锁之后再继续工作 */
   
3. lock_t lock1, lock2;
   
4. 
   
5. /* 线程1 */
   
6. thread1_work(void)
   
7. {
   
8.         while(1) {
   
9.                 lock1.lock();
   
10.                 while (lock2.locked())
    
11.                 {
    
12.                         /* 无法获得锁2，于是释放锁1，试图让拥有锁2的线程可以获得锁1 */
    
13.                         lock1.unlock();
    
14.                
    
15.                         schedule(); /* or schedule_timeout() */
    
16.                
    
17.                         lock1.lock(); /* 再次试图获得两把锁 */
    
18.                 }
    
19.                 lock2.lock();
    
20. 
    
21.                 /* 运气好的时候能到达此处 */
    
22.                 work_on_resources();
    
23. 
    
24.                 lock1.unlock();
    
25.                 lock2.unlock();
    
26.         }
    
27. }
    
28. 
    
29. /* 线程2 */
    
30. thread2_work(void)
    
31. {
    
32.         while(1) {
    
33.                 lock2.lock();
    
34.                 while (lock1.locked())
    
35.                 {
    
36.                         lock2.unlock();
    
37.                
    
38.                         schedule();
    
39.                
    
40.                         lock2.lock();
    
41.                 }
    
42.                 lock1.lock();
    
43. 
    
44.                 work_on_resources();
    
45.                 lock1.unlock();
    
46.                 lock2.unlock();
    
47.         }
    
48. }
    

复制代码

vupiggy

活锁实际上你在生活中经常碰到，就是你走在狭窄的人行道上和对面来客互相谦让，结果让个两三次以后，终于有人烦了不再谦让或者是彼此让路的时序有了一点差别，就把这个活锁给解了。如果是死锁，像你的例子代码里以相反的顺序获得两把锁，并且获得一把锁以后就死等另外一把锁，那就死没解了。

tempname2

你说的没错，那那段代码是死锁，给该书作者写信吧。
vupiggy 发表于 2011-06-13 21:54

看来这个活锁的定义不是很清楚。entry_region里行为是不停的获得锁，类似：

1. while ( !acquire_lock_no_block(lock) )
   
2.                ;
   

复制代码

一般的livelock定义里，只说两者都不能make progress，似乎没有说能不能最终突破窘境。

另外，LZ引用的程序与文字，和我手上影印版《Modern Operating Sytems》关于活锁的一节几乎一模一样。要么LZ看的是《Modern Operating Systems》的中文版，要么LZ看的是某山寨版国产操作系统教材，但是这个例子应该没有问题。

tomkedy

看来这个活锁的定义不是很清楚。entry_region里行为是不停的获得锁，类似：一般的livelock定义里，只说 ...
tempname2 发表于 2011-06-13 22:37

楼上，没错，我看的是《Modern Operating Systems》的中文版。但一来怕是自己理解错，二来Tam可是这方面的大师，因此之前并没有将书名及作者写出来........

另，你为何认为例子没问题？可否说说你的分析（我是指代码中的执行过程，因为我的分析得出的是“死锁"......）

tempname2

回复 9# tomkedy

这个完全看livelock是怎样定义的。你引用的那段话里“但从现象上看像是发生了死锁，因此叫活锁（livelock）”，原文是"but we have something functionally equivalent to deadlock:livelock"。如果说译文“现象上看”还不够强烈的话，functionally equivalent to 应该足够表明作者认为两种锁最终的效果是无异的。这里或许是强调死锁会block这一特征，不然两者不需要区别。这或许是一些不严格的定义带来的纠结。书上这一节最后一段还说，有些人不区别starvation与deadlock。这里说starvation应该是永远得到资源的情况，但是一般环境下对starvation的理解似乎是很长一时间内得不到资源。所以，{:3_196:}