java 之多线程 LOCK实现(一)
一,前言
?? 众所周知,一个可靠的多线程程序必须要能够坐到无死锁,无饥饿。
?? 什么叫做无饥饿:如果一个线程需要获得一个Lock,那么这个操作在一个有限时间内最终会获得成功(不论时间长短)。
那么我们现在就来实现只有两个线程的Lock。
?
二,Lock接口?
?
public interface Lock{ public void lock(); public void unlock();}
三,只有两个线程的Lock实现
?
public class TwoThreadLockImpl implements Lock { private boolean[] flag = new boolean[2]; public void lock() { /**获得当前线程Id(0或者1) **/ int threadId = ThreadUtil.getCurrentThread(); step 1 flag[threadId ] = true; step 2 /**循环等待另一个线程将标志位设置为false; **/ while(!flag[1- threadId] ) { step 3 } /** 这个地方标志着一个线程已经获得这个Lock **/ } public void unlock() { int threadId = ThreadUtil.getCurrentThread(); 将标志位设置为false,让另外一个线程可以获得这个锁。 boolean[threadId ] = false; }}
?
?
但是这个Lock实现有个缺陷,如果执行方式如下:
?
????????????????????? 线程A??????????? 线程B
??1???????????????? step 1??????????????
??2???????????????????????????????????? step1
? 3???????????????? step 2
? 4??????????????????????????????????????step 2
? 5???????????????? step 3
??6??????????????????????????????????????step 3
?
在执行第5,6两步的时候 会发生死锁。即两个线程谁也永远不能得到这个锁。
?
?
四,这个实现是个正确的实现吗?即这个实现满足互斥特性吗?
???? 定义如下,如果一个线程在一获得锁与释放锁之间的执行时间为Ca,定义两个线程在时间上的 偏序为Ca > Cb表示 Ca在Cb之前先发生。一个正确的锁必须满足互斥,要么Ca>Cb要么Cb > Ca。
???? 这个a,b表示线程ID
???? 证明如下:
??????????假设这个Lock实现不满足互斥特性:即Ca Cb没有时间上的偏序关系。
????????? 即Ca Cb之间有交集
?
??????????????????????????????????????????? |-----------Ca--------------------------|
?
-----------------------------------|----------------------|------------------|-------------------------|-----
?
???????????????????????????????????????????????????????????????????????? |----------------------Cb------------------|
?
???????? 红色的部分为时间交集。
?
????????? 通过阅读代码可以得到:
???线程a:???? write(a)(flag(a) = true) > read(a)(flag(b) == false) > Ca????????? -----------1
??线程b:????? write(b)(flag(b) = true) > read(b)(flag(a) == false) > Cb????????? -----------2
? 我们又注意到,在标志位被设置为true 到 释放锁之前不会被重置。即:
? 如果a想获得lock必须得等到b执行flag(b) = false之后,才会读取到read(a)(flag(b) == false)-------->即a想获得锁必须得等到b执行完unlock之后,反过来b想获得锁也得等到a执行完unlock之后,即要么Ca > Cb要么Cb > Ca.与证明假设矛盾。即此lock实现满足互斥特性。
?
?
???
?
?
??
?
?
1 楼 zhaoxjmail 2012-09-07 楼主,有些看不明白,boolean[threadId ] = false;是不是应该是flag[threadId]=false;