大家好，我是小林。

今天來分析字節跳動校招后端開發面經，同學的技術棧是 Java 后端，問八股文比較多，一共經歷了一二三面，每一場面試的強度還是蠻高，每次都是 1 個小時+。

我把這幾場面試中比較有代表性的題目抽離出來給大家解析一波，給準備春招的同學做一個參考和學習，雖然是校招的面試，但是有些問題，其實社招也經常問的。

知識一學就忘原因，就是缺少溫故的過程，通過面試題的方式回顧系列的知識，也是一種高效的方式。

這次面經的考點，我簡單羅列一下：

• 操作系統：進程調度
• 網絡：HTTP、HTTPS
• Java：線程狀態、多線程、volatile、synchronized
• Redis：數據結構、跳表、性能、場景應用、緩存一致性
• MySQL：事務、隔離級別、日志、索引、間隙鎖、最左匹配原則
• 算法：每一輪 1 個算法

Redis

Redis 有哪些數據結構？

Redis 提供了豐富的數據類型，常見的有五種數據類型：String（字符串），Hash（哈希），List（列表），Set（集合）、Zset（有序集合）。

圖片

圖片

隨著 Redis 版本的更新，后面又支持了四種數據類型：BitMap（2.2 版新增）、HyperLogLog（2.8 版新增）、GEO（3.2 版新增）、Stream（5.0 版新增）。Redis 五種數據類型的應用場景：

• String 類型的應用場景：緩存對象、常規計數、分布式鎖、共享 session 信息等。
• List 類型的應用場景：消息隊列（但是有兩個問題：1. 生產者需要自行實現全局唯一 ID；2. 不能以消費組形式消費數據）等。
• Hash 類型：緩存對象、購物車等。
• Set 類型：聚合計算（并集、交集、差集）場景，比如點贊、共同關注、抽獎活動等。
• Zset 類型：排序場景，比如排行榜、電話和姓名排序等。

Redis 后續版本又支持四種數據類型，它們的應用場景如下：

• BitMap（2.2 版新增）：二值狀態統計的場景，比如簽到、判斷用戶登陸狀態、連續簽到用戶總數等；
• HyperLogLog（2.8 版新增）：海量數據基數統計的場景，比如百萬級網頁 UV 計數等；
• GEO（3.2 版新增）：存儲地理位置信息的場景，比如滴滴叫車；
• Stream（5.0 版新增）：消息隊列，相比于基于 List 類型實現的消息隊列，有這兩個特有的特性：自動生成全局唯一消息ID，支持以消費組形式消費數據。

Zset 使用了什么數據結構？

Zset 類型的底層數據結構是由壓縮列表或跳表實現的：

• 如果有序集合的元素個數小于 128 個，并且每個元素的值小于 64 字節時，Redis 會使用壓縮列表作為 Zset 類型的底層數據結構；
• 如果有序集合的元素不滿足上面的條件，Redis 會使用跳表作為 Zset 類型的底層數據結構；

在 Redis 7.0 中，壓縮列表數據結構已經廢棄了，交由 listpack 數據結構來實現了。

SkipList 了解嗎？

鏈表在查找元素的時候，因為需要逐一查找，所以查詢效率非常低，時間復雜度是O(N)，于是就出現了跳表。跳表是在鏈表基礎上改進過來的，實現了一種「多層」的有序鏈表，這樣的好處是能快讀定位數據。

那跳表長什么樣呢？我這里舉個例子，下圖展示了一個層級為 3 的跳表。

圖片

圖中頭節點有 L0~L2 三個頭指針，分別指向了不同層級的節點，然后每個層級的節點都通過指針連接起來：

• L0 層級共有 5 個節點，分別是節點1、2、3、4、5；
• L1 層級共有 3 個節點，分別是節點 2、3、5；
• L2 層級只有 1 個節點，也就是節點 3 。

如果我們要在鏈表中查找節點 4 這個元素，只能從頭開始遍歷鏈表，需要查找 4 次，而使用了跳表后，只需要查找 2 次就能定位到節點 4，因為可以在頭節點直接從 L2 層級跳到節點 3，然后再往前遍歷找到節點 4。

可以看到，這個查找過程就是在多個層級上跳來跳去，最后定位到元素。當數據量很大時，跳表的查找復雜度就是 O(logN)。

跳表的時間復雜度是多少？

跳表中查找一個元素的時間復雜度為O(logn)，空間復雜度是 O(n)。

為什么 MysSQL 不用 SkipList？

B+樹的高度在3層時存儲的數據可能已達千萬級別，但對于跳表而言同樣去維護千萬的數據量那么所造成的跳表層數過高而導致的磁盤io次數增多，也就是使用B+樹在存儲同樣的數據下磁盤io次數更少。

Redis 使用場景?

Redis 是一種基于內存的數據庫，對數據的讀寫操作都是在內存中完成，因此讀寫速度非常快，常用于緩存，消息隊列、分布式鎖等場景。

圖片

Redis用途

Redis 提供了多種數據類型來支持不同的業務場景，比如 String(字符串)、Hash(哈希)、 List (列表)、Set(集合)、Zset(有序集合)、Bitmaps（位圖）、HyperLogLog（基數統計）、GEO（地理信息）、Stream（流），并且對數據類型的操作都是原子性的，因為執行命令由單線程負責的，不存在并發競爭的問題。

除此之外，Redis 還支持事務 、持久化、Lua 腳本、多種集群方案（主從復制模式、哨兵模式、切片機群模式）、發布/訂閱模式，內存淘汰機制、過期刪除機制等等。

Redis 性能好的原因是什么？

官方使用基準測試的結果是，單線程的 Redis 吞吐量可以達到 10W/每秒，如下圖所示：

圖片

之所以 Redis 采用單線程（網絡 I/O 和執行命令）那么快，有如下幾個原因：

• Redis 的大部分操作都在內存中完成，并且采用了高效的數據結構，因此 Redis 瓶頸可能是機器的內存或者網絡帶寬，而并非 CPU，既然 CPU 不是瓶頸，那么自然就采用單線程的解決方案了；
• Redis 采用單線程模型可以避免了多線程之間的競爭，省去了多線程切換帶來的時間和性能上的開銷，而且也不會導致死鎖問題。
• Redis 采用了 I/O 多路復用機制處理大量的客戶端 Socket 請求，IO 多路復用機制是指一個線程處理多個 IO 流，就是我們經常聽到的 select/epoll 機制。簡單來說，在 Redis 只運行單線程的情況下，該機制允許內核中，同時存在多個監聽 Socket 和已連接 Socket。內核會一直監聽這些 Socket 上的連接請求或數據請求。一旦有請求到達，就會交給 Redis 線程處理，這就實現了一個 Redis 線程處理多個 IO 流的效果。

Redis 和 MySQL 如何保證一致性

可以采用「先更新數據庫，再刪除緩存」的更新策略+過期時間來兜底。

我們用「讀 + 寫」請求的并發的場景來分析。

假如某個用戶數據在緩存中不存在，請求 A 讀取數據時從數據庫中查詢到年齡為 20，在未寫入緩存中時另一個請求 B 更新數據。它更新數據庫中的年齡為 21，并且清空緩存。這時請求 A 把從數據庫中讀到的年齡為 20 的數據寫入到緩存中。

圖片

最終，該用戶年齡在緩存中是 20（舊值），在數據庫中是 21（新值），緩存和數據庫數據不一致。

從上面的理論上分析，先更新數據庫，再刪除緩存也是會出現數據不一致性的問題，但是在實際中，這個問題出現的概率并不高。

因為緩存的寫入通常要遠遠快于數據庫的寫入，所以在實際中很難出現請求 B 已經更新了數據庫并且刪除了緩存，請求 A 才更新完緩存的情況。

而一旦請求 A 早于請求 B 刪除緩存之前更新了緩存，那么接下來的請求就會因為緩存不命中而從數據庫中重新讀取數據，所以不會出現這種不一致的情況。

所以，「先更新數據庫 + 再刪除緩存」的方案，是可以保證數據一致性的。

而且為了確保萬無一失，還給緩存數據加上了「過期時間」，就算在這期間存在緩存數據不一致，有過期時間來兜底，這樣也能達到最終一致。

MySQL

事務有哪些特性?

事務 4 個特性，分別如下：

• 原子性（Atomicity）：一個事務中的所有操作，要么全部完成，要么全部不完成，不會結束在中間某個環節，而且事務在執行過程中發生錯誤，會被回滾到事務開始前的狀態，就像這個事務從來沒有執行過一樣，就好比買一件商品，購買成功時，則給商家付了錢，商品到手；購買失敗時，則商品在商家手中，消費者的錢也沒花出去。
• 一致性（Consistency）：是指事務操作前和操作后，數據滿足完整性約束，數據庫保持一致性狀態。比如，用戶 A 和用戶 B 在銀行分別有 800 元和 600 元，總共 1400 元，用戶 A 給用戶 B 轉賬 200 元，分為兩個步驟，從 A 的賬戶扣除 200 元和對 B 的賬戶增加 200 元。一致性就是要求上述步驟操作后，最后的結果是用戶 A 還有 600 元，用戶 B 有 800 元，總共 1400 元，而不會出現用戶 A 扣除了 200 元，但用戶 B 未增加的情況（該情況，用戶 A 和 B 均為 600 元，總共 1200 元）。
• 隔離性（Isolation）：數據庫允許多個并發事務同時對其數據進行讀寫和修改的能力，隔離性可以防止多個事務并發執行時由于交叉執行而導致數據的不一致，因為多個事務同時使用相同的數據時，不會相互干擾，每個事務都有一個完整的數據空間，對其他并發事務是隔離的。也就是說，消費者購買商品這個事務，是不影響其他消費者購買的。
• 持久性（Durability）：事務處理結束后，對數據的修改就是永久的，即便系統故障也不會丟失。

隔離性有哪些隔離級別?

四個隔離級別如下：

• 讀未提交（*read uncommitted*），指一個事務還沒提交時，它做的變更就能被其他事務看到；
• 讀提交（*read committed*），指一個事務提交之后，它做的變更才能被其他事務看到；
• 可重復讀（*repeatable read*），指一個事務執行過程中看到的數據，一直跟這個事務啟動時看到的數據是一致的，MySQL InnoDB 引擎的默認隔離級別；
• 串行化（*serializable* ）；會對記錄加上讀寫鎖，在多個事務對這條記錄進行讀寫操作時，如果發生了讀寫沖突的時候，后訪問的事務必須等前一個事務執行完成，才能繼續執行；

按隔離水平高低排序如下：

圖片

針對不同的隔離級別，并發事務時可能發生的現象也會不同。

圖片

也就是說：

• 在「讀未提交」隔離級別下，可能發生臟讀、不可重復讀和幻讀現象；
• 在「讀提交」隔離級別下，可能發生不可重復讀和幻讀現象，但是不可能發生臟讀現象；
• 在「可重復讀」隔離級別下，可能發生幻讀現象，但是不可能臟讀和不可重復讀現象；
• 在「串行化」隔離級別下，臟讀、不可重復讀和幻讀現象都不可能會發生。

MySQL 默認用的哪個級別?

MySQL 默認隔離級別是「可重復讀」，可以很大程度上避免幻讀現象的發生（注意是很大程度避免，并不是徹底避免），所以 MySQL 并不會使用「串行化」隔離級別來避免幻讀現象的發生，因為使用「串行化」隔離級別會影響性能。

間隙鎖的原理

Gap Lock 稱為間隙鎖，只存在于可重復讀隔離級別，目的是為了解決可重復讀隔離級別下幻讀的現象。

假設，表中有一個范圍 id 為（3，5）間隙鎖，那么其他事務就無法插入 id = 4 這條記錄了，這樣就有效的防止幻讀現象的發生。

img

間隙鎖雖然存在 X 型間隙鎖和 S 型間隙鎖，但是并沒有什么區別，間隙鎖之間是兼容的，即兩個事務可以同時持有包含共同間隙范圍的間隙鎖，并不存在互斥關系，因為間隙鎖的目的是防止插入幻影記錄而提出的。

什么時候會加間隙鎖?

當我們用唯一索引進行等值查詢的時候，查詢的記錄不存在的時候，在索引樹找到第一條大于該查詢記錄的記錄后，將該記錄的索引中的 next-key lock 會退化成「間隙鎖」。

假設事務 A 執行了這條等值查詢語句，查詢的記錄是「不存在」于表中的。

mysql> begin;
Query OK, 0 rows affected (0.00 sec)

mysql> select * from user where id = 2 for update;
Empty set (0.03 sec)

接下來，通過 select * from performance_schema.data_locks\G; 這條語句，查看事務執行 SQL 過程中加了什么鎖。

圖片

從上圖可以看到，共加了兩個鎖，分別是：

• 表鎖：X 類型的意向鎖；
• 行鎖：X 類型的間隙鎖；

因此，此時事務 A 在 id = 5 記錄的主鍵索引上加的是間隙鎖，鎖住的范圍是 (1, 5)。

圖片

接下來，如果有其他事務插入 id 值為 2、3、4 這一些記錄的話，這些插入語句都會發生阻塞。

注意，如果其他事務插入的 id = 1 或者 id = 5 的記錄話，并不會發生阻塞，而是報主鍵沖突的錯誤，因為表中已經存在 id = 1 和 id = 5 的記錄了。

比如，下面這個例子：

img

因為事務 A 在 id = 5 記錄的主鍵索引上加了范圍為 (1, 5) 的 X 型間隙鎖，所以事務 B 在插入一條 id 為 3 的記錄時會被阻塞住，即無法插入 id = 3 的記錄。

MySQL 如何保證原子性?

通過 undo log 來保證原子性的。

undo log 是一種用于撤銷回退的日志。在事務沒提交之前，MySQL 會先記錄更新前的數據到 undo log 日志文件里面，當事務回滾時，可以利用 undo log 來進行回滾。如下圖：

回滾事務

undo log 撤銷過程具體是怎么撤銷的?

每當 InnoDB 引擎對一條記錄進行操作（修改、刪除、新增）時，要把回滾時需要的信息都記錄到 undo log 里，比如：

• 在插入一條記錄時，要把這條記錄的主鍵值記下來，這樣之后回滾時只需要把這個主鍵值對應的記錄刪掉就好了；
• 在刪除一條記錄時，要把這條記錄中的內容都記下來，這樣之后回滾時再把由這些內容組成的記錄插入到表中就好了；
• 在更新一條記錄時，要把被更新的列的舊值記下來，這樣之后回滾時再把這些列更新為舊值就好了。

在發生回滾時，就讀取 undo log 里的數據，然后做原先相反操作。比如當 delete 一條記錄時，undo log 中會把記錄中的內容都記下來，然后執行回滾操作的時候，就讀取 undo log 里的數據，然后進行 insert 操作。

怎么決定建立哪些索引?

什么時候適用索引？

• 字段有唯一性限制的，比如商品編碼；
• 經常用于 WHERE 查詢條件的字段，這樣能夠提高整個表的查詢速度，如果查詢條件不是一個字段，可以建立聯合索引。
• 經常用于 GROUP BY 和 ORDER BY 的字段，這樣在查詢的時候就不需要再去做一次排序了，因為我們都已經知道了建立索引之后在 B+Tree 中的記錄都是排序好的。

什么時候不需要創建索引？

• WHERE 條件，GROUP BY，ORDER BY 里用不到的字段，索引的價值是快速定位，如果起不到定位的字段通常是不需要創建索引的，因為索引是會占用物理空間的。
• 字段中存在大量重復數據，不需要創建索引，比如性別字段，只有男女，如果數據庫表中，男女的記錄分布均勻，那么無論搜索哪個值都可能得到一半的數據。在這些情況下，還不如不要索引，因為 MySQL 還有一個查詢優化器，查詢優化器發現某個值出現在表的數據行中的百分比很高的時候，它一般會忽略索引，進行全表掃描。
• 表數據太少的時候，不需要創建索引；
• 經常更新的字段不用創建索引，比如不要對電商項目的用戶余額建立索引，因為索引字段頻繁修改，由

最左匹配是什么，舉個例子？

使用聯合索引時，存在最左匹配原則，也就是按照最左優先的方式進行索引的匹配。在使用聯合索引進行查詢的時候，如果不遵循「最左匹配原則」，聯合索引會失效，這樣就無法利用到索引快速查詢的特性了。

比如，如果創建了一個 (a, b, c) 聯合索引，如果查詢條件是以下這幾種，就可以匹配上聯合索引：

• where a=1；
• where a=1 and b=2 and c=3；
• where a=1 and b=2；

需要注意的是，因為有查詢優化器，所以 a 字段在 where 子句的順序并不重要。

但是，如果查詢條件是以下這幾種，因為不符合最左匹配原則，所以就無法匹配上聯合索引，聯合索引就會失效:

• where b=2；
• where c=3；
• where b=2 and c=3；

上面這些查詢條件之所以會失效，是因為(a, b, c) 聯合索引，是先按 a 排序，在 a 相同的情況再按 b 排序，在 b 相同的情況再按 c 排序。所以，b 和 c 是全局無序，局部相對有序的，這樣在沒有遵循最左匹配原則的情況下，是無法利用到索引的。

我這里舉聯合索引（a，b）的例子，該聯合索引的 B+ Tree 如下（圖中葉子節點之間我畫了單向鏈表，但是實際上是雙向鏈表，原圖我找不到了，修改不了，偷個懶我不重畫了，大家腦補成雙向鏈表就行）。

可以看到，a 是全局有序的（1, 2, 2, 3, 4, 5, 6, 7 ,8），而 b 是全局是無序的（12，7，8，2，3，8，10，5，2）。因此，直接執行where b = 2這種查詢條件沒有辦法利用聯合索引的，利用索引的前提是索引里的 key 是有序的。

只有在 a 相同的情況才，b 才是有序的，比如 a 等于 2 的時候，b 的值為（7，8），這時就是有序的，這個有序狀態是局部的，因此，執行where a = 2 and b = 7是 a 和 b 字段能用到聯合索引的，也就是聯合索引生效了。

Java

Java 里面線程有哪些狀態?

源自《Java并發編程藝術》

java.lang.Thread.State枚舉類中定義了六種線程的狀態，可以調用線程Thread中的getState()方法獲取當前線程的狀態。

wait 狀態下的線程如何進行恢復到 running 狀態?

• 等待的線程被其他線程對象喚醒，notify()和notifyAll()。
• 如果線程沒有獲取到鎖則會直接進入 Waiting 狀態，其實這種本質上它就是執行了 LockSupport.park() 方法進入了Waiting 狀態，那么解鎖的時候會執行LockSupport.unpark(Thread)，與上面park方法對應，給出許可證，解除等待狀態。

notify 和 notifyAll 的區別?

同樣是喚醒等待的線程，同樣最多只有一個線程能獲得鎖，同樣不能控制哪個線程獲得鎖。

區別在于：

• notify：喚醒一個線程，其他線程依然處于wait的等待喚醒狀態，如果被喚醒的線程結束時沒調用notify，其他線程就永遠沒人去喚醒，只能等待超時，或者被中斷
• notifyAll：所有線程退出wait的狀態，開始競爭鎖，但只有一個線程能搶到，這個線程執行完后，其他線程又會有一個幸運兒脫穎而出得到鎖

notify 選擇哪個線程?

notify在源碼的注釋中說到notify選擇喚醒的線程是任意的，但是依賴于具體實現的jvm。

圖片

notify源碼

JVM有很多實現，比較流行的就是hotspot，hotspot對notofy()的實現并不是我們以為的隨機喚醒,，而是“先進先出”的順序喚醒。

如何停止一個線程的運行?

主要有這些方法：

• 異常法停止：線程調用interrupt()方法后，在線程的run方法中判斷當前對象的interrupted()狀態，如果是中斷狀態則拋出異常，達到中斷線程的效果。
• 在沉睡中停止：先將線程sleep，然后調用interrupt標記中斷狀態，interrupt會將阻塞狀態的線程中斷。會拋出中斷異常，達到停止線程的效果
• stop()暴力停止：線程調用stop()方法會被暴力停止，方法已棄用，該方法會有不好的后果：強制讓線程停止有可能使一些請理性的工作得不到完成。
• 使用return停止線程：調用interrupt標記為中斷狀態后，在run方法中判斷當前線程狀態，如果為中斷狀態則return，能達到停止線程的效果。

調用 interrupt 是如何讓線程拋出異常的?

每個線程都一個與之關聯的布爾屬性來表示其中斷狀態，中斷狀態的初始值為false，當一個線程被其它線程調用Thread.interrupt()方法中斷時，會根據實際情況做出響應。

• 如果該線程正在執行低級別的可中斷方法（如Thread.sleep()、Thread.join()或Object.wait()），則會解除阻塞并拋出InterruptedException異常。
• 否則Thread.interrupt()僅設置線程的中斷狀態，在該被中斷的線程中稍后可通過輪詢中斷狀態來決定是否要停止當前正在執行的任務。

如果是靠變量來停止線程，缺點是什么?

缺點是中斷可能不夠及時，循環判斷時會到下一個循環才能判斷出來。

class InterruptFlag {
  // 自定義的中斷標識符
  private static volatile boolean isInterrupt = false;

  public static void main(String[] args) throws InterruptedException {
    // 創建可中斷的線程實例
    Thread thread = new Thread(() -> {
      while (!isInterrupt) { // 如果 isInterrupt=true 則停止線程
        System.out.println("thread 執行步驟1：線程即將進入休眠狀態");
        try {
          // 休眠 1s
          Thread.sleep(1000);
        } catch (InterruptedException e) {
          e.printStackTrace();
        }
        System.out.println("thread 執行步驟2：線程執行了任務");
      }
    });
    
    thread.start(); // 啟動線程
    // 休眠 100ms，等待 thread 線程運行起來
    Thread.sleep(100);
    System.out.println("主線程：試圖終止線程 thread");
    // 修改中斷標識符，中斷線程
    isInterrupt = true;
  }
}

當終止線程后，執行步驟2依然會被執行，這就是缺點。

volatile 保證原子性嗎？

volatile關鍵字并沒有保證我們的變量的原子性，volatile是Java虛擬機提供的一種輕量級的同步機制，主要有這三個特性：

• 保證可見性
• 不保證原子性
• 禁止指令重排

那我們要如何保證原子性?

可以通過synchronized來保證原子性。

synchronized 支持重入嗎？如何實現的?

synchronized是基于原子性的內部鎖機制，是可重入的，因此在一個線程調用synchronized方法的同時在其方法體內部調用該對象另一個synchronized方法，也就是說一個線程得到一個對象鎖后再次請求該對象鎖，是允許的，這就是synchronized的可重入性。

synchronized底層是利用計算機系統mutex Lock實現的。每一個可重入鎖都會關聯一個線程ID和一個鎖狀態status。

當一個線程請求方法時，會去檢查鎖狀態。

1. 如果鎖狀態是0，代表該鎖沒有被占用，使用CAS操作獲取鎖，將線程ID替換成自己的線程ID。
2. 如果鎖狀態不是0，代表有線程在訪問該方法。此時，如果線程ID是自己的線程ID，如果是可重入鎖，會將status自增1，然后獲取到該鎖，進而執行相應的方法；如果是非重入鎖，就會進入阻塞隊列等待。

在釋放鎖時，

1. 如果是可重入鎖的，每一次退出方法，就會將status減1，直至status的值為0，最后釋放該鎖。
2. 如果非可重入鎖的，線程退出方法，直接就會釋放該鎖。

網絡

HTTP 與 HTTPS 協議的區別？

HTTP 與 HTTPS 網絡層

• HTTP 是超文本傳輸協議，信息是明文傳輸，存在安全風險的問題。HTTPS 則解決 HTTP 不安全的缺陷，在 TCP 和 HTTP 網絡層之間加入了 SSL/TLS 安全協議，使得報文能夠加密傳輸。
• HTTP 連接建立相對簡單， TCP 三次握手之后便可進行 HTTP 的報文傳輸。而 HTTPS 在 TCP 三次握手之后，還需進行 SSL/TLS 的握手過程，才可進入加密報文傳輸。
• 兩者的默認端口不一樣，HTTP 默認端口號是 80，HTTPS 默認端口號是 443。
• HTTPS 協議需要向 CA（證書權威機構）申請數字證書，來保證服務器的身份是可信的。

操作系統

有哪些進程調度算法 ?

01 先來先服務調度算法

最簡單的一個調度算法，就是非搶占式的先來先服務（*First Come First Serve, FCFS*）算法了。

FCFS 調度算法

顧名思義，先來后到，每次從就緒隊列選擇最先進入隊列的進程，然后一直運行，直到進程退出或被阻塞，才會繼續從隊列中選擇第一個進程接著運行。

這似乎很公平，但是當一個長作業先運行了，那么后面的短作業等待的時間就會很長，不利于短作業。

FCFS 對長作業有利，適用于 CPU 繁忙型作業的系統，而不適用于 I/O 繁忙型作業的系統。

02 最短作業優先調度算法

最短作業優先（*Shortest Job First, SJF*）調度算法同樣也是顧名思義，它會優先選擇運行時間最短的進程來運行，這有助于提高系統的吞吐量。

SJF 調度算法

這顯然對長作業不利，很容易造成一種極端現象。

比如，一個長作業在就緒隊列等待運行，而這個就緒隊列有非常多的短作業，那么就會使得長作業不斷的往后推，周轉時間變長，致使長作業長期不會被運行。

03 高響應比優先調度算法

前面的「先來先服務調度算法」和「最短作業優先調度算法」都沒有很好的權衡短作業和長作業。

那么，高響應比優先 （*Highest Response Ratio Next, HRRN*）調度算法主要是權衡了短作業和長作業。

每次進行進程調度時，先計算「響應比優先級」，然后把「響應比優先級」最高的進程投入運行，「響應比優先級」的計算公式：

圖片

從上面的公式，可以發現：

• 如果兩個進程的「等待時間」相同時，「要求的服務時間」越短，「響應比」就越高，這樣短作業的進程容易被選中運行；
• 如果兩個進程「要求的服務時間」相同時，「等待時間」越長，「響應比」就越高，這就兼顧到了長作業進程，因為進程的響應比可以隨時間等待的增加而提高，當其等待時間足夠長時，其響應比便可以升到很高，從而獲得運行的機會；

04 時間片輪轉調度算法

最古老、最簡單、最公平且使用最廣的算法就是時間片輪轉（*Round Robin, RR*）調度算法。

RR 調度算法

每個進程被分配一個時間段，稱為時間片（*Quantum*），即允許該進程在該時間段中運行。

• 如果時間片用完，進程還在運行，那么將會把此進程從 CPU 釋放出來，并把 CPU 分配給另外一個進程；
• 如果該進程在時間片結束前阻塞或結束，則 CPU 立即進行切換；

另外，時間片的長度就是一個很關鍵的點：

• 如果時間片設得太短會導致過多的進程上下文切換，降低了 CPU 效率；
• 如果設得太長又可能引起對短作業進程的響應時間變長。將

一般來說，時間片設為 20ms~50ms 通常是一個比較合理的折中值。

05 最高優先級調度算法

前面的「時間片輪轉算法」做了個假設，即讓所有的進程同等重要，也不偏袒誰，大家的運行時間都一樣。

但是，對于多用戶計算機系統就有不同的看法了，它們希望調度是有優先級的，即希望調度程序能從就緒隊列中選擇最高優先級的進程進行運行，這稱為最高優先級（*Highest Priority First，HPF*）調度算法。

進程的優先級可以分為，靜態優先級和動態優先級：

• 靜態優先級：創建進程時候，就已經確定了優先級了，然后整個運行時間優先級都不會變化；
• 動態優先級：根據進程的動態變化調整優先級，比如如果進程運行時間增加，則降低其優先級，如果進程等待時間（就緒隊列的等待時間）增加，則升高其優先級，也就是隨著時間的推移增加等待進程的優先級。

該算法也有兩種處理優先級高的方法，非搶占式和搶占式：

• 非搶占式：當就緒隊列中出現優先級高的進程，運行完當前進程，再選擇優先級高的進程。
• 搶占式：當就緒隊列中出現優先級高的進程，當前進程掛起，調度優先級高的進程運行。

但是依然有缺點，可能會導致低優先級的進程永遠不會運行。

06 多級反饋隊列調度算法

多級反饋隊列（*Multilevel Feedback Queue*）調度算法是「時間片輪轉算法」和「最高優先級算法」的綜合和發展。

顧名思義：

• 「多級」表示有多個隊列，每個隊列優先級從高到低，同時優先級越高時間片越短。
• 「反饋」表示如果有新的進程加入優先級高的隊列時，立刻停止當前正在運行的進程，轉而去運行優先級高的隊列；

多級反饋隊列

來看看，它是如何工作的：

• 設置了多個隊列，賦予每個隊列不同的優先級，每個隊列優先級從高到低，同時優先級越高時間片越短；
• 新的進程會被放入到第一級隊列的末尾，按先來先服務的原則排隊等待被調度，如果在第一級隊列規定的時間片沒運行完成，則將其轉入到第二級隊列的末尾，以此類推，直至完成；
• 當較高優先級的隊列為空，才調度較低優先級的隊列中的進程運行。如果進程運行時，有新進程進入較高優先級的隊列，則停止當前運行的進程并將其移入到原隊列末尾，接著讓較高優先級的進程運行；

可以發現，對于短作業可能可以在第一級隊列很快被處理完。對于長作業，如果在第一級隊列處理不完，可以移入下次隊列等待被執行，雖然等待的時間變長了，但是運行時間也變更長了，所以該算法很好的兼顧了長短作業，同時有較好的響應時間。

算法

• 給定鏈表 1 -> 2 -> ... -> n-1 -> n，使用 O(1) 空間復雜度使其變為 1 -> n -> 2 -> n-1 -> ...
• 只記得有關滑動窗口，應該是力扣 TOP 100 的