并發(fā)：線程與鎖

線程與鎖

哲學家問題

問題描述：五位哲學家圍繞一個圓桌就做，桌上在每兩位哲學家之間擺著一支筷子。哲學家的狀態(tài)可能是“思考”或者“饑餓”。如果饑餓，哲學家將拿起他兩邊的筷子就餐一段時間。進餐結(jié)束后，哲學家就會放回筷子。

代碼實現(xiàn)：

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
        }
    }
}

規(guī)避方法：
一個線程使用多把鎖時，就需要考慮死鎖的可能。幸運的是，如果總是按照一個全局的固定的順序獲得多把鎖，就可以避開死鎖。

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
        }
    }
}

外星方法

定義：調(diào)用這類方法時，調(diào)用者對方法的實現(xiàn)細節(jié)并不了解。

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) 方法調(diào)用了一個外星方法，這個外星方法可能做任何事，比如持有另外一把鎖。

可以這樣來修改：

private  void updateProgress(int n) {
ArrayList<ProgressListener> listenersCopy;
    synchronized (this) {
        listenersCopy = (ArrayList<ProgressListener>) listeners.clone();
    }
        
    for (ProgressListener listener : listenersCopy) {
        listener.onProgress(n);
    }
}

線程與鎖模型帶來的三個主要危害：

  1. 競態(tài)條件
  2. 死鎖
  3. 內(nèi)存可見性

規(guī)避原則：

  • 對共享變量的所有訪問都需要同步化
  • 讀線程和寫線程都需要同步化
  • 按照約定的全局順序來獲取多把鎖
  • 當持有鎖時避免調(diào)用外星方法
  • 持有鎖的時間應(yīng)盡可能短

內(nèi)置鎖

內(nèi)置鎖限制：

  • 無法中斷 一個線程因為等待內(nèi)置鎖而進入阻塞之后，就無法中斷該線程了；
  • 無法超時 嘗試獲取內(nèi)置鎖時，無法設(shè)置超時；
  • 不靈活 獲得內(nèi)置鎖，必須使用 synchronized 塊。
synchronized( object ) {
    <<使用共享資源>>
}

ReentrantLock

其提供了顯式的lock和unlock， 可以突破以上內(nèi)置鎖的幾個限制。

ReentrantLock lock = new ReentrantLock();
lock.lock();
try {
    <<使用共享資源>>
} finally {
    lock.unlock()
}

可中斷

使用內(nèi)置鎖時，由于阻塞的線程無法被中斷，程序不可能從死鎖中恢復。

內(nèi)置鎖：制造一個死鎖：

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 替代內(nèi)置鎖：

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 超時設(shè)置解決哲學家問題：

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 {
                        // 沒有獲取到右手邊的筷子，放棄并繼續(xù)思考
                    }
                } finally {
                    leftChopstick.unlock();
                }
            }
        } catch (InterruptedException e) {
            // ...
        }
    }
}

交替鎖

場景：在鏈表中插入一個節(jié)點時，使用交替鎖只鎖住鏈表的一部分，而不是用鎖保護整個鏈表。

線程安全鏈表：

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;
    }
}

條件變量

并發(fā)編程經(jīng)常要等待某個條件滿足。比如從隊列刪除元素必須等待隊列不為空、向緩存添加數(shù)據(jù)前需要等待緩存有足夠的空間。

條件變量模式：

ReentrantLock lock = new ReentrantLock();
Condition condition = lock.newConditiion();

lock.lock();
try {
    while(!<<條件為真>>) {  // 條件不為真時
        condition.await();
    }
    <<使用共享資源>>
} finnally {
    lock.unlock();
}

一個條件變量需要與一把鎖關(guān)聯(lián)，線程在開始等待條件之前必須獲得鎖。獲取鎖后，線程檢查等待的條件是否為真。

  • 如果為真，線程將繼續(xù)執(zhí)行并解鎖；
  • 如果不為真，線程會調(diào)用 await()，它將原子的解鎖并阻塞等待條件。

當另一個線程調(diào)用 signal() 或 signalAll()，意味著對應(yīng)的條件可能變?yōu)檎妫?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)算法的基礎(chǔ)，這種算法可以不用鎖和阻塞來達到同步的目的。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容