双线程锁 | 王明的技术博客

link管理

链接快照平台

输入网页链接，自动生成快照
标签化管理网页链接

LockOne

class LockOne {
	private volatile boolean[] flags = new boolean[2];
	public void lock() {
		int i = ThreadID.get();
		int j = 1- i;
		flag[i] = true;
		while(flag[j]) {}		

	}

	public void unlock() {
		int i = ThreadID.get();
		flag[i] = false;
	}
}

假设线程A对应flag[0]标志,线程B对应flag[1]标志,那么我们得出下面这一个流程:


     write_A(flag[0] = true) -> read_A(flag[1] == false) -> CS_A

这段话的意思是线程A将


     flag[0]

的值置为true然后读取


     flag[1]

的值,这个过程称为


     CS_A

事件


     write_B(flag[1] = true) -> read_B(flag[0] == false) -> CS_B

这段话的意思是线程B将


     flag[1]

的值置为true然后读取


     flag[0]

的值,这个过程称为


     CS_B

事件

我们验证一下LockOne算法是否满足互斥

假设这个算法不是互斥的，也就是无法得到`CS_A -> CS_B`且`CS_B -> CS_A`.
假设CS_A事件先于CS_B事件,那么有：
write_A(flag[0] = true) -> read_A(flag[1] == false) -> write_B(flag[1] = true)
=>
read_A(flag[1] == false) -> write_B(flag[1] = true)
可以看到这俩个事件是互斥的(它们的临界区是没有重叠的).

LockOne算法满足了互斥,但是如果俩个线程并发执行的话，就会进入死锁,同样我们来证明一下

1
2
3

假设
write_A(flag[0] = true) -> write_B(flag[1] = true) -> read_A(flag[1] == false) -> read_B(flag[0] == false)
那么`flag[0]`和`flag[1]`就都成为true,也就是线程A和线程B进入了死锁.

至于说为什么要使用 volatile 关键字,这是为了保证 flags 变量的内存可见性,因为Java会将这段代码

while(flag[j]) {}
=>
if(flag[j]) {
	while(true) {

	}
}

编译后的代码进行了提升优化,加上 volatile 关键字,就是告诉编译器,不要提升优化我的代码.

LockTwo

class LockTwo {
	private int lock;
	public void lock() {
		int tid = ThreadID.get();
		lock = tid;
		while(lock == tid){}
	}

	public void unlock() {
		int tid = ThreadID.get();
		lock = tid;

	}
}

同样我们假设有俩个事件发生


     write_A(lock = 1) -> read_A(lock == 1) -> CS_A


     write_B(lock = 2) -> read_B(lock == 2) -> CS_B

很明显任何线程调用加锁操作都会造成死循环. 但是,如果锁调用交叉调用的话

1	write_A(lock = 1) -> write_B(lock = 2) -> read_A(lock == 2) -> read_B(lock == 2)

直到A线程释放锁,B线程就一直在阻塞着. 因此只要这俩个事件并发执行就能完成互斥要求.

Peterson

算法实现

class Peterson {
	private voliate boolean[] flag = new boolean[2];
	private int lock;

	public void lock() {
		int tid = ThreadID.get();
		int oid = 1 - tid;
		flag[oid] = true;
		lock = tid;

		while(flag[tid] && lock == tid) {}
	}

	public void unlock() {
		int tid = ThreadID.get();
		flag[tid] = false;
	}
}

同样的我们看看俩个线程依次调用锁过程(假设线程A对应flag[0]标志,线程B对应flag[1]标志)：

1
2

write_A(flag[1] = true) -> write_A(lock = 0) -> read_A(flag[0] == false) -> read_A(lock == 0) -> CS_A
write_B(flag[0] = true) -> write_B(lock = 1) -> read_B(flag[1] == true) -> read_B(lock == 1) -> CS_B

好，首先我们看一下


     CS_A

先于


     CS_B

事件执行的话,那么B线程会进入锁等待.

CS_A 和 CS_B 事件并发执行我们分俩种情况分析：

1	write_A(flag[1] = true) -> write_A(lock = 0) -> write_B(flag[0] = true) -> write_B(lock = 1) -> read_A(flag[1] == true) -> read_A(lock == 0) -> read_B(flag[1] == true) -> read_B(lock == 1)

同样的A线程事件先于B线程事件,我们看到A线程并没有进入锁等待,而是B线程进入了锁等待

1	write_A(flag[1] = true) -> write_A(lock = 0) -> write_B(flag[0] = true) -> write_B(lock = 1) -> read_B(flag[1] == true) -> read_B(lock == 1) -> read_A(flag[1] == true) -> read_A(lock == 0)

我们发现这个锁算法仍然是有问题的.