6月安卓手機性能榜：vivo/iQOO霸占旗艦排行榜前三
2023年上半年已經(jīng)正式過去了，我們也迎來了安兔兔V10版本，在新的驍龍8Gen3和天璣9300發(fā)布之前，性能榜的榜單大體會以驍龍8Gen2和天璣9200+為主，至于那顆3.36GHz的驍龍8Gen2領(lǐng)先
本文繼續(xù)討論 Netty 相關(guān)的面試題，今天咱們來看一道 Netty 中的高頻面試題：說說 Netty 延遲任務(wù)的時間輪調(diào)度算法？
Netty 框架是以性能著稱的框架，因此在它的框架中使用了大量提升性能的機制，例如 Netty 用于實現(xiàn)延遲隊列的時間輪調(diào)度算法就是一個典型的例子。使用時間輪算法可以實現(xiàn)海量任務(wù)新增和取消任務(wù)的時間度為 O(1)，那么什么是時間輪調(diào)度算法呢？接下來我們一起來看。
在 Netty 中，我們需要使用 HashedWheelTimer 類來實現(xiàn)延遲任務(wù)，例如以下代碼：
public class DelayTaskExample { public static void main(String[] args) { System.out.println("程序啟動時間：" + LocalDateTime.now()); NettyTask(); } private static void NettyTask() { // 創(chuàng)建延遲任務(wù)實例 HashedWheelTimer timer = new HashedWheelTimer(3, // 間隔時間 TimeUnit.SECONDS, // 間隔時間單位 100); // 時間輪中的槽數(shù) // 創(chuàng)建任務(wù) TimerTask task = new TimerTask() { @Override public void run(Timeout timeout) throws Exception { System.out.println("執(zhí)行任務(wù)時間：" + LocalDateTime.now()); } }; // 將任務(wù)添加到延遲隊列中 timer.newTimeout(task, 0, TimeUnit.SECONDS); }}以上程序的執(zhí)行結(jié)果如下：
程序啟動時間：2024-06-04T10:16:23.033
執(zhí)行任務(wù)時間：2024-06-04T10:16:26.118
從上述執(zhí)行結(jié)果可以看出，我們使用 HashedWheelTimer 實現(xiàn)了延遲任務(wù)的執(zhí)行。
那么問題來了，HashedWheelTimer 是如何實現(xiàn)延遲任務(wù)的？什么是時間輪調(diào)度算法？
查看 HashedWheelTimer 類的源碼會發(fā)現(xiàn)，其實它是底層是通過時間輪調(diào)度算法來實現(xiàn)的，以下是 HashedWheelTimer 核心實現(xiàn)源碼（HashedWheelTimer 的創(chuàng)建源碼）如下：
private static HashedWheelBucket[] createWheel(int ticksPerWheel) { // 省略其他代碼 ticksPerWheel = normalizeTicksPerWheel(ticksPerWheel); HashedWheelBucket[] wheel = new HashedWheelBucket[ticksPerWheel]; for (int i = 0; i < wheel.length; i ++) { wheel[i] = new HashedWheelBucket(); } return wheel;}private static int normalizeTicksPerWheel(int ticksPerWheel) { int normalizedTicksPerWheel = 1; while (normalizedTicksPerWheel < ticksPerWheel) { normalizedTicksPerWheel <<= 1; } return normalizedTicksPerWheel;}private static final class HashedWheelBucket { private HashedWheelTimeout head; private HashedWheelTimeout tail; // 省略其他代碼}在 HashedWheelTimer 中，使用了 HashedWheelBucket 數(shù)組實現(xiàn)時間輪的概念，每個 HashedWheelBucket 表示時間輪中一個 slot（時間槽），HashedWheelBucket 內(nèi)部是一個雙向鏈表結(jié)構(gòu)，雙向鏈表的每個節(jié)點持有一個 HashedWheelTimeout 對象，HashedWheelTimeout 代表一個定時任務(wù)，每個 HashedWheelBucket 都包含雙向鏈表 head 和 tail 兩個 HashedWheelTimeout 節(jié)點，這樣就可以實現(xiàn)不同方向進行鏈表遍歷，如下圖所示：
時間輪算法的設(shè)計思想就來源于鐘表，如上圖所示，時間輪可以理解為一種環(huán)形結(jié)構(gòu)，像鐘表一樣被分為多個 slot 槽位。每個 slot 代表一個時間段，每個 slot 中可以存放多個任務(wù)，使用的是鏈表結(jié)構(gòu)保存該時間段到期的所有任務(wù)。時間輪通過一個時針隨著時間一個個 slot 轉(zhuǎn)動，并執(zhí)行 slot 中的所有到期任務(wù)。
任務(wù)的添加是根據(jù)任務(wù)的到期時間進行取模，然后將任務(wù)分布到不同的 slot 中。如上圖所示，時間輪被劃分為 8 個 slot，每個 slot 代表 1s，當(dāng)前時針指向 2 時，假如現(xiàn)在需要調(diào)度一個 3s 后執(zhí)行的任務(wù)，應(yīng)該加入 2+3=5 的 slot 中；如果需要調(diào)度一個 12s 以后的任務(wù)，需要等待時針完整走完一圈 round 零 4 個 slot，需要放入第 (2+12)%8=6 個 slot。
那么當(dāng)時針走到第 6 個 slot 時，怎么區(qū)分每個任務(wù)是否需要立即執(zhí)行，還是需要等待下一圈 round，甚至更久時間之后執(zhí)行呢？所以我們需要把 round 信息保存在任務(wù)中。例如圖中第 6 個 slot 的鏈表中包含 3 個任務(wù)，第一個任務(wù) round=0，需要立即執(zhí)行；第二個任務(wù) round=1，需要等待 1*8=8s 后執(zhí)行；第三個任務(wù) round=2，需要等待 2×8=8s 后執(zhí)行。所以當(dāng)時針轉(zhuǎn)動到對應(yīng) slot 時，只執(zhí)行 round=0 的任務(wù)，slot 中其余任務(wù)的 round 應(yīng)當(dāng)減 1，等待下一個 round 之后執(zhí)行。
可以看出時間輪有點類似 HashMap，如果多個任務(wù)如果對應(yīng)同一個 slot，處理沖突的方法采用的是拉鏈法。在任務(wù)數(shù)量比較多的場景下，適當(dāng)增加時間輪的 slot 數(shù)量，可以減少時針轉(zhuǎn)動時遍歷的任務(wù)個數(shù)。
時間輪定時器最大的優(yōu)勢就是，任務(wù)的新增和取消都是 O(1) 時間復(fù)雜度，而且只需要一個線程就可以驅(qū)動時間輪進行工作。
本文鏈接：http://www.tebozhan.com/showinfo-26-92120-0.html面試官：說說延遲任務(wù)的時間輪調(diào)度算法？
聲明：本網(wǎng)頁內(nèi)容旨在傳播知識，若有侵權(quán)等問題請及時與本網(wǎng)聯(lián)系，我們將在第一時間刪除處理。郵件：2376512515@qq.com
Copyright ? 2016-2023 天津谷騏科技有限公司 版權(quán)所有 sitemap.xml
違法及侵權(quán)請聯(lián)系：2376512515@qq.com 津ICP備18001702號
津公網(wǎng)安備 12010102000574號