搜尋
首頁JavaJava面試題java多執行緒與並發面試題目(1~3題,附答案)

java多執行緒與並發面試題目(1~3題,附答案)

1、DeplayQueue延時無界阻塞佇列

在談到DelayQueue的使用和原理的時候,我們先介紹一下DelayQueue,DelayQueue是一個無界阻塞佇列,只有在延遲期滿時才能從中提取元素。此隊列的頭部是延遲期滿後保存時間最長的Delayed元素。 (推薦學習:java面試題目

DelayQueue阻塞佇列在我們系統開發中也常常會用到,例如:快取系統的設計,快取中的對象,超過了空閒時間,需要從快取中移出;任務調度系統,能夠準確的掌握任務的執行時間。我們可能需要透過線程處理很多時間上要求很嚴格的資料。

如果使用普通的線程,我們就需要遍歷所有的對象,一個一個的檢查看數據是否過期等,首先這樣在執行上的效率不會太高,其次就是這種設計的風格也大大的影響了數據的精度。一個需要12:00點執行的任務可能12:01才執行,這樣對資料要求很高的系統有更大的弊端。由此我們可以使用DelayQueue。

下面將會對DelayQueue做一個介紹,然後舉例。並且提供一個Delayed介面的實作和Sample程式碼。 DelayQueue是一個BlockingQueue,其特化的參數是Delayed。

(不了解BlockingQueue的同學,先去了解BlockingQueue再看本文)Delayed擴展了Comparable接口,比較的基準為延時的時間值,Delayed接口的實現類getDelay的返回值應為固定值(final)。 DelayQueue內部是使用PriorityQueue實現的。

DelayQueue=BlockingQueue+PriorityQueue+Delayed

DelayQueue的關鍵元素BlockingQueue、PriorityQueue、Delayed。可以這麼說,DelayQueue是一個使用優先隊列(PriorityQueue)實現的BlockingQueue,而優先隊列的比較基準值是時間。

他們的基本定義如下

public interface Comparable<T> {
    public int compareTo(T o);
}
public interface Delayed extends Comparable<Delayed> {
    long getDelay(TimeUnit unit);
}
public class DelayQueue<E extends Delayed> implements BlockingQueue<E> {
    private final PriorityQueue<E> q = new PriorityQueue<E>();
}

DelayQueue 內部的實作使用了一個優先隊列。當呼叫 DelayQueue 的 offer 方法時,把 Delayed 物件加入優先權佇列 q 中。如下:

public boolean offer(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        E first = q.peek();
        q.offer(e);
        if (first == null || e.compareTo(first) < 0)
            available.signalAll();
        return true;
    } finally {
        lock.unlock();
    }
}

DelayQueue 的 take 方法,把優先隊列 q 的 first 拿出來(peek),如果沒有達到延時閥值,則進行 await處理。如下:

public E take() throws InterruptedException {
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {
        for (; ; ) {
            E first = q.peek();
            if (first == null) {
                available.await();
            } else {
                long delay = first.getDelay(TimeUnit.NANOSECONDS);
                if (delay > 0) {
                    long tl = available.awaitNanos(delay);
                } else {
                    E x = q.poll();
                    assert x != null;
                    if (q.size() != 0)
                        available.signalAll(); //wake up other takers return x;
                }
            }
        }
    } finally {
        lock.unlock();
    }
}

DelayQueue 實例應用

Ps:為了具有呼叫行為,存放到 DelayDeque 的元素必須繼承 Delayed 介面。 Delayed 介面使物件成為延遲對象,它使存放在 DelayQueue 類別中的物件具有了啟動日期。此介面強制執行下列兩個方法。

以下將使用 Delay 做一個快取的實作。其中共包括三個類別Pair、DelayItem、Cache

Pair 類別:

public class Pair<K, V> {
    public K first;
    public V second;
    public Pair() {
    }
    public Pair(K first, V second) {
        this.first = first;
        this.second = second;
    }
}

以下是對Delay 介面的實作:

import java.util.concurrent.Delayed;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicLong;
public class DelayItem<T> implements Delayed {
    /**
     * Base of nanosecond timings, to avoid wrapping
     */
    private static final long NANO_ORIGIN = System.nanoTime();
    /**
     * Returns nanosecond time offset by origin
     */
    final static long now() {
        return System.nanoTime() - NANO_ORIGIN;
    }
    /**
     * Sequence number to break scheduling ties, and in turn to guarantee FIFO order among tied
     * entries.
     */
    private static final AtomicLong sequencer = new AtomicLong(0);
    /**
     * Sequence number to break ties FIFO
     */
    private final long sequenceNumber;
    /**
     * The time the task is enabled to execute in nanoTime units
     */
    private final long time;
    private final T item;
    public DelayItem(T submit, long timeout) {
        this.time = now() + timeout;
        this.item = submit;
        this.sequenceNumber = sequencer.getAndIncrement();
    }
    public T getItem() {
        return this.item;
    }
    public long getDelay(TimeUnit unit) {
        long d = unit.convert(time - now(), TimeUnit.NANOSECONDS); return d;
    }
    public int compareTo(Delayed other) {
        if (other == this) // compare zero ONLY if same object return 0;
            if (other instanceof DelayItem) {
                DelayItem x = (DelayItem) other;
                long diff = time - x.time;
                if (diff < 0) return -1;
                else if (diff > 0) return 1;
                else if (sequenceNumber < x.sequenceNumber) return -1;
                else
                    return 1;
            }
        long d = (getDelay(TimeUnit.NANOSECONDS) - other.getDelay(TimeUnit.NANOSECONDS));
        return (d == 0) ?0 :((d < 0) ?-1 :1);
    }
}

以下是Cache 的實現,包括了put 和get 方法

import javafx.util.Pair;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.DelayQueue;
import java.util.concurrent.TimeUnit;
import java.util.logging.Level;
import java.util.logging.Logger;
public class Cache<K, V> {
    private static final Logger LOG = Logger.getLogger(Cache.class.getName());
    private ConcurrentMap<K, V> cacheObjMap = new ConcurrentHashMap<K, V>();
    private DelayQueue<DelayItem<Pair<K, V>>> q = new DelayQueue<DelayItem<Pair<K, V>>>();
    private Thread daemonThread;
    public Cache() {
        Runnable daemonTask = new Runnable() {
            public void run() {
                daemonCheck();
            }
        };
        daemonThread = new Thread(daemonTask);
        daemonThread.setDaemon(true);
        daemonThread.setName("Cache Daemon");
        daemonThread.start();
    }
    private void daemonCheck() {
        if (LOG.isLoggable(Level.INFO)) LOG.info("cache service started.");
        for (; ; ) {
            try {
                DelayItem<Pair<K, V>> delayItem = q.take();
                if (delayItem != null) {
                    // 超时对象处理
                    Pair<K, V> pair = delayItem.getItem();
                    cacheObjMap.remove(pair.first, pair.second); // compare and remove
                }
            } catch (InterruptedException e) {
                if (LOG.isLoggable(Level.SEVERE)) LOG.log(Level.SEVERE, e.getMessage(), e);
                break;
            }
        }
        if (LOG.isLoggable(Level.INFO)) LOG.info("cache service stopped.");
    }
    // 添加缓存对象
    public void put(K key, V value, long time, TimeUnit unit) {
        V oldValue = cacheObjMap.put(key, value);
        if (oldValue != null) q.remove(key);
        long nanoTime = TimeUnit.NANOSECONDS.convert(time, unit);
        q.put(new DelayItem<Pair<K, V>>(new Pair<K, V>(key, value), nanoTime));
    }
    public V get(K key) {
        return cacheObjMap.get(key);
    }
}

測試main 方法:##

// 测试入口函数
public static void main(String[] args) throws Exception {
    Cache<Integer, String> cache = new Cache<Integer, String>();
    cache.put(1, "aaaa", 3, TimeUnit.SECONDS);
    Thread.sleep(1000 * 2);
    {
        String str = cache.get(1);
        System.out.println(str);
    }
    Thread.sleep(1000 * 2);
    {
        String str = cache.get(1);
        System.out.println(str);
    }
}

輸出結果為:

aaaa
null

我們看到上面的結果,如果超過延時的時間,那麼快取中資料就會自動遺失,取得就為null。

2、並發(Collection)佇列-非阻塞佇列

#非阻塞佇列##首先我們要簡單的理解下什麼是非阻塞隊列:

與阻塞隊列相反,非阻塞隊列的執行並不會被阻塞,無論是消費者的出隊,或是生產者的入隊。在底層,非阻塞佇列使用的是 CAS(compare and swap)來實作執行緒執行的非阻塞。

非阻塞佇列簡單操作

與阻塞佇列相同,非阻塞佇列中的常用方法,也是出隊和入隊。

offer():Queue 介面繼承下來的方法,實作佇列的入隊操作,不會阻礙執行緒的執行,插入成功回傳true;出隊方法:

poll():移動頭結點指針,返回頭結點元素,並將頭結點元素出隊;隊列為空,則返回null;

peek():移動頭結點指針,返回頭結點元素,不會將頭結點元素出隊;佇列為空,則傳回null;

3、非阻塞演算法CAS

首先我們需要了解悲觀鎖和樂觀鎖

悲觀鎖:假定並發環境是悲觀的,如果發生並發衝突,就會破壞一致性,所以要透過獨佔鎖徹底禁止衝突發生。有一個經典比喻,“如果你不鎖門,那麼搗蛋鬼就回闖入並搞得一團糟”,所以“你只能一次打開門放進一個人,才能時刻盯緊他”。

樂觀鎖:假定並發環境是樂觀的,即雖然會有並發衝突,但衝突可發現且不會造成損害,所以,可以不加任何保護,等發現並發衝突後再決定放棄操作還是重試。可類比的比喻為,“如果你不鎖門,那麼雖然搗蛋鬼會闖入,但他們一旦打算破壞你就能知道”,所以“你大可以放進所有人,等發現他們想破壞的時候再做決定」。

通常認為樂觀鎖的效能比悲觀所更高,特別是在某些複雜的場景。這主要由於悲觀鎖在加鎖的同時,也會把某些不會造成破壞的操作保護起來;而樂觀鎖的競爭則只發生在最小的並發衝突處,如果用悲觀鎖來理解,就是「鎖的粒度最小」。但樂觀鎖的設計往往比較複雜,因此,複雜場景下還是多用悲觀鎖。首先確保正確性,有必要的話,再去追求性能。

樂觀鎖的實現往往需要硬體的支持,多數處理器都實現了一個CAS指令,實現“Compare And Swap”的語義(這裡的swap是“換入”,也就是set),構成了基本的樂觀鎖。 CAS包含3個運算元:

需要讀寫的記憶體位置V

比較的值A

#所寫入的新值B

當且僅當位置V的值等於A時,CAS才會以原子方式以新值B來更新位置V的值;否則不會執行任何操作。無論位置V的值是否等於A,都會傳回V原有的值。一個有趣的事實是,「使用CAS控制並發」與「使用樂觀鎖」並不等價。 CAS只是一種手段,既可以實現樂觀鎖,也可以實現悲觀鎖。樂觀、悲觀只是一種並發控制的策略。

以上是java多執行緒與並發面試題目(1~3題,附答案)的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

WebStorm Mac版

WebStorm Mac版

好用的JavaScript開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

PhpStorm Mac 版本

PhpStorm Mac 版本

最新(2018.2.1 )專業的PHP整合開發工具

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

將Eclipse與SAP NetWeaver應用伺服器整合。