线程与锁
哲学家问题
问题描述：五位哲学家围绕一个圆桌就做，桌上在每两位哲学家之间摆着一支筷子。哲学家的状态可能是“思考”或者“饥饿”。如果饥饿，哲学家将拿起他两边的筷子就餐一段时间。进餐结束后，哲学家就会放回筷子。
代码实现：
public class Philosopher extends Thread {
private Chopstick left;
private Chopstick right;
private Random random;
public Philosopher(Chopstick left, Chopstick right) {
this.left = left;
this.right = right;
random = new Random();
}
@Override
public void run() {
try {
while (true) {
Thread.sleep(random.nextInt(1000)); // 思考一会儿
synchronized (left) { // 拿起左手的筷子
synchronized (right) { // 拿起右手的筷子
Thread.sleep(random.nextInt(1000)); // 进餐
}
}
}
} catch (InterruptedException e) {
// handle exception
}
}
}
规避方法：
一个线程使用多把锁时，就需要考虑死锁的可能。幸运的是，如果总是按照一个全局的固定的顺序获得多把锁，就可以避开死锁。
public class Philosopher2 extends Thread {
private Chopstick first;
private Chopstick second;
private Random random;
public Philosopher2(Chopstick left, Chopstick right) {
if (left.getId() < right.getId()) {
first = left;
second = right;
} else {
first = right;
second = left;
}
random = new Random();
}
@Override
public void run() {
try {
while (true) {
Thread.sleep(random.nextInt(1000)); // 思考一会儿
synchronized (first) { // 拿起左手的筷子
synchronized (second) { // 拿起右手的筷子
Thread.sleep(random.nextInt(1000)); // 进餐
}
}
}
} catch (InterruptedException e) {
// handle exception
}
}
}
外星方法
定义：调用这类方法时，调用者对方法的实现细节并不了解。
public class Downloader extends Thread {
private InputStream in;
private OutputStream out;
private ArrayList<ProgressListener> listeners;
public Downloader(URL url, String outputFilename) throws IOException {
in = url.openConnection().getInputStream();
out = new FileOutputStream(outputFilename);
listeners = new ArrayList<>();
}
public synchronized void addListener(ProgressListener listener) {
listeners.add(listener);
}
public synchronized void removeListener(ProgressListener listener) {
listeners.remove(listener);
}
private synchronized void updateProgress(int n) {
for (ProgressListener listener : listeners) {
listener.onProgress(n);
}
}
@Override
public void run() {
// ...
}
}
这里 updateProgress(n) 方法调用了一个外星方法，这个外星方法可能做任何事，比如持有另外一把锁。
可以这样来修改：
private void updateProgress(int n) {
ArrayList<ProgressListener> listenersCopy;
synchronized (this) {
listenersCopy = (ArrayList<ProgressListener>) listeners.clone();
}
for (ProgressListener listener : listenersCopy) {
listener.onProgress(n);
}
}
线程与锁模型带来的三个主要危害：
- 竞态条件
- 死锁
- 内存可见性
规避原则：
- 对共享变量的所有访问都需要同步化
- 读线程和写线程都需要同步化
- 按照约定的全局顺序来获取多把锁
- 当持有锁时避免调用外星方法
- 持有锁的时间应尽可能短
内置锁
内置锁限制：
- 无法中断 一个线程因为等待内置锁而进入阻塞之后，就无法中断该线程了；
- 无法超时 尝试获取内置锁时，无法设置超时；
-
不灵活 获得内置锁，必须使用
synchronized块。
synchronized( object ) {
<<使用共享资源>>
}
ReentrantLock
其提供了显式的lock和unlock， 可以突破以上内置锁的几个限制。
ReentrantLock lock = new ReentrantLock();
lock.lock();
try {
<<使用共享资源>>
} finally {
lock.unlock()
}
可中断
使用内置锁时，由于阻塞的线程无法被中断，程序不可能从死锁中恢复。
内置锁：制造一个死锁：
public class Uninterruptible {
public static void main(String[] args) throws InterruptedException {
final Object o1 = new Object();
final Object o2 = new Object();
Thread t1 = new Thread(){
@Override
public void run() {
try {
synchronized (o1) {
Thread.sleep(1000);
synchronized (o2) {}
}
} catch (InterruptedException e) {
System.out.println("Thread-1 interrupted");
}
}
};
Thread t2 = new Thread(){
@Override
public void run() {
try {
synchronized (o2) {
Thread.sleep(1000);
synchronized (o1) {}
}
} catch (InterruptedException e) {
System.out.println("Thread-2 interrupted");
}
}
};
t1.start();
t2.start();
Thread.sleep(2000);
t1.interrupt();
t2.interrupt();
t1.join();
t2.join();
}
}
ReentrantLock 替代内置锁：
public class Interruptible {
public static void main(String[] args) {
final ReentrantLock lock1 = new ReentrantLock();
final ReentrantLock lock2 = new ReentrantLock();
Thread t1 = new Thread(){
@Override
public void run() {
try {
lock1.lockInterruptibly();
Thread.sleep(1000);
lock2.lockInterruptibly();
} catch (InterruptedException e) {
System.out.println("Thread-1 interrupted");
}
}
};
// ...
}
}
可超时
利用 ReentrantLock 超时设置解决哲学家问题：
public class Philosopher3 extends Thread {
private ReentrantLock leftChopstick;
private ReentrantLock rightChopstick;
private Random random;
public Philosopher3(ReentrantLock leftChopstick, ReentrantLock rightChopstick) {
this.leftChopstick = leftChopstick;
this.rightChopstick = rightChopstick;
random = new Random();
}
@Override
public void run() {
try {
while (true) {
Thread.sleep(random.nextInt(1000)); // 思考一会儿
leftChopstick.lock();
try {
// 获取右手边的筷子
if (rightChopstick.tryLock(1000, TimeUnit.MILLISECONDS)) {
try {
Thread.sleep(random.nextInt(1000));
} finally {
rightChopstick.unlock();
}
} else {
// 没有获取到右手边的筷子，放弃并继续思考
}
} finally {
leftChopstick.unlock();
}
}
} catch (InterruptedException e) {
// ...
}
}
}
交替锁
场景：在链表中插入一个节点时，使用交替锁只锁住链表的一部分，而不是用锁保护整个链表。
线程安全链表：
public class ConcurrentSortedList { // 降序有序链表
private class Node {
int value;
Node pre;
Node next;
ReentrantLock lock = new ReentrantLock();
Node() {}
Node(int value, Node pre, Node next) {
this.value = value;
this.pre = pre;
this.next = next;
}
}
private final Node head;
private final Node tail;
public ConcurrentSortedList() {
this.head = new Node();
this.tail = new Node();
this.head.next = tail;
this.tail.pre = head;
}
public void insert(int value) {
Node current = this.head;
current.lock.lock();
Node next = current.next;
try {
while (true) {
next.lock.lock();
try {
if (next == tail || next.value < value) {
Node newNode = new Node(value, current, next);
next.pre = newNode;
current.next = newNode;
return;
}
} finally {
current.lock.unlock();
}
current = next;
next = current.next;
}
} finally {
next.lock.unlock();
}
}
public int size() {
Node current = tail; // 这里为什么要是从尾部开始遍历呢？ 因为插入是从头部开始遍历的
int count = 0;
while (current != head) {
ReentrantLock lock = current.lock;
lock.lock();
try {
++count;
current = current.pre;
} finally {
lock.unlock();
}
}
return count;
}
}
条件变量
并发编程经常要等待某个条件满足。比如从队列删除元素必须等待队列不为空、向缓存添加数据前需要等待缓存有足够的空间。
条件变量模式：
ReentrantLock lock = new ReentrantLock();
Condition condition = lock.newConditiion();
lock.lock();
try {
while(!<<条件为真>>) { // 条件不为真时
condition.await();
}
<<使用共享资源>>
} finnally {
lock.unlock();
}
一个条件变量需要与一把锁关联，线程在开始等待条件之前必须获得锁。获取锁后，线程检查等待的条件是否为真。
- 如果为真，线程将继续执行并解锁；
- 如果不为真，线程会调用
await()，它将原子的解锁并阻塞等待条件。
当另一个线程调用 signal() 或 signalAll()，意味着对应的条件可能变为真， await() 将原子的恢复运行并重新加锁。
条件变量解决哲学家就餐问题：
public class Philosopher4 extends Thread {
private boolean eating;
private Philosopher4 left;
private Philosopher4 right;
private ReentrantLock table;
private Condition condition;
private Random random;
public Philosopher4(ReentrantLock table) {
this.eating = false;
this.table = table;
this.condition = table.newCondition();
this.random = new Random();
}
public void setLeft(Philosopher4 left) {
this.left = left;
}
public void setRight(Philosopher4 right) {
this.right = right;
}
@Override
public void run() {
try {
while (true) {
think();
eat();
}
} catch (InterruptedException e) {
// ...
}
}
private void think() throws InterruptedException {
this.table.lock();
try {
this.eating = false;
this.left.condition.signal();
this.right.condition.signal();
} finally {
table.unlock();
}
Thread.sleep(1000);
}
private void eat() throws InterruptedException {
this.table.lock();
try {
while (left.eating || right.eating) {
this.condition.await();
}
this.eating = true;
} finally {
this.table.unlock();
}
Thread.sleep(1000);
}
}
原子变量
原子变量是无锁(lock-free) 非阻塞(non-blocking)算法的基础，这种算法可以不用锁和阻塞来达到同步的目的。
