并发算法和理论-02-Mutual Exclusion

Using Locks

public class Counter {
	private long value;
	private Lock lock;

	public long getAndIncrement() {
		lock.lock(); // acquire lock
		try { // critical section
			int temp = value;
			value = value + 1;
		} finally {
			lock.unlock(); // release lock, no matter what
		}
		return temp;
	}
}

两个 Liveness

避免死锁 Deadlock-Free：如果某个线程调用 lock()，并且从不返回，那么其他线程必须无限次地完成 lock() 和 unlock() 调用。整个系统都会取得进展，即使某个线程饿死。

避免饿死 Starvation-Free：如果某个线程调用 lock()，它最终会返回，各个线程取得进展。

双线程并发

LockOne 算法

class LockOne implements Lock {
	private boolean[] flag = new boolean[2]; // Each thread has flag

	public void lock() {
		flag[i] = true; // set my flag
		while (flag[j]) { // Wait for the other flag to become false
		}
	}

	public void unlock() {
		flag[i] = false; // Reset my flag
	}
}

该算法不能避免死锁，并发执行时 flag[i] = true 和 flag[j] = true 可能同时出现，此时系统陷入死锁。串行执行时没有死锁。

LockTwo 算法

public class LockTwo implements Lock {
	private int victim;

	public void lock() {
		victim = i; // let the other go first
		while (victim == i) { // Wait for permission
		}
	}

	public void unlock() { 
		// Nothing to do
	}
}

该算法不能避免死锁，串行执行时会陷入死循环，并发执行时没有死锁。

Peterson's Algorithm

public void lock() {
	flag[i] = true; // Announce I’m interested
	victim = i; // Defer to the other
	while (flag[j] && victim == i) { // Wait while other interested & I’m the victim
	}
}

public void unlock() {
	flag[i] = false; // No longer interested
}

可以证明，该算法能够避免死锁，避免饿死。

多线程并发 Filter Algorithm

过滤锁

有 n-1 个“等候室”，称为层级 level。在每个层级，至少有一个进入层级。

如果许多线程尝试，则至少有一个被阻止。只有一个线程通过。

class Filter implements Lock {
	int[] level;  // level[i] for thread i, the level that i is trying to enter
	int[] victim; // victim[L] for level L, the thread that is excluded from level L

	public Filter(int n) {
		level = new int[n];
		victim = new int[n];
		for (int i = 1; i < n; i++) {
			level[i] = 0;
		}
	}

	public void lock() {
		for (int L = 1; L < n; L++) {
			level[i] = L; // Announce intention to enter level L
			victim[L] = i; // Give priority to anyone but me
			while ((exists k != i level[k] >= L) &&victim[L] == i ){
				// Wait as long as someone else is at same or higher level, and I’m designated victim
			}
		}
	}

	public void unlock() {
		level[i] = 0;
	}
}

EagleBear2002 的博客