双线程锁

算法 评论
  1. LockOne
  2. LockTwo
  3. Peterson

所谓的双线程锁指的是这种锁适用于俩个线程运行的前提下. 下面我们依次给出了三种双线程锁解决方案：

双线程算法遵循以下俩点约定:

  1. 线程标志为0或者1. 若当前线程调用者的标志为i,则另一方的调用者为1 - i
  2. 通过ThreadId.get()获取自己的标志
  • 互斥: 俩个线程的临界区是没有重叠的,那么我们撑这俩个临界区是互斥的.
  • 无死锁: 如果一个线程尝试获得一个锁,那么总会成功获得这个锁.
  • 无饥饿：每一个尝试获得锁的线程都能成功. 当线程调用一个锁方法的时候,这个方法立即返回,我们便称这个锁是无饥饿的.

LockOne

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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]标志,那么我们得出下面这一个流程:

  1. write_A(flag[0] = true) -> read_A(flag[1] == false) -> CS_A这段话的意思是线程A将flag[0]的值置为true然后读取flag[1]的值,这个过程称为CS_A事件
  2. write_B(flag[1] = true) -> read_B(flag[0] == false) -> CS_B这段话的意思是线程B将flag[1]的值置为true然后读取flag[0]的值,这个过程称为CS_B事件

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

1
2
3
4
5
6
假设这个算法不是互斥的，也就是无法得到`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会将这段代码

1
2
3
4
5
6
7
while(flag[j]) {}
=>
if(flag[j]) {
	while(true) {

	}
}

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

LockTwo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;

	}
}

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

  1. write_A(lock = 1) -> read_A(lock == 1) -> CS_A
  2. 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

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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)

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

王明Coder

一个纯粹的技术开发者。