開發(fā)崗位 | 小紅書是給的真多，我想沖了...

Redis 是由 C 語言實現(xiàn)的，在 Redis 6.0 版本之前采用的正是「單 Reactor 單進程」的方案，因為 Redis 業(yè)務(wù)處理主要是在內(nèi)存中完成，操作的速度是很快的，性能瓶頸不在 CPU 上，所以 Redis 對于命令的處理是單進程的方案。

到 Redis 6.0 之后，就將網(wǎng)絡(luò)IO的處理改成多線程的方式了，目的是為了這是因為隨著網(wǎng)絡(luò)硬件的性能提升，Redis 的性能瓶頸有時會出現(xiàn)在網(wǎng)絡(luò) I/O 的處理上。

所以為了提高網(wǎng)絡(luò) I/O 的并行度，Redis 6.0 對于網(wǎng)絡(luò) I/O 采用多線程來處理。但是對于命令的執(zhí)行，Redis 仍然使用單線程來處理，所以大家不要誤解 Redis 有多線程同時執(zhí)行命令。

Redis為什么快

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

之所以 Redis 采用單線程（網(wǎng)絡(luò) I/O 和執(zhí)行命令）那么快，有如下幾個原因：

• • Redis 的大部分操作

  都在內(nèi)存中完成

• • ，并且采用了高效的數(shù)據(jù)結(jié)構(gòu)，因此 Redis 瓶頸可能是機器的內(nèi)存或者網(wǎng)絡(luò)帶寬，而并非 CPU，既然 CPU 不是瓶頸，那么自然就采用單線程的解決方案了；Redis 采用單線程模型可以

  避免了多線程之間的競爭

• • ，省去了多線程切換帶來的時間和性能上的開銷，而且也不會導(dǎo)致死鎖問題。Redis 采用了

  I/O 多路復(fù)用機制

處理大量的客戶端 Socket 請求，IO 多路復(fù)用機制是指一個線程處理多個 IO 流，就是我們經(jīng)常聽到的 select/epoll 機制。簡單來說，在 Redis 只運行單線程的情況下，該機制允許內(nèi)核中，同時存在多個監(jiān)聽 Socket 和已連接 Socket。內(nèi)核會一直監(jiān)聽這些 Socket 上的連接請求或數(shù)據(jù)請求。一旦有請求到達，就會交給 Redis 線程處理，這就實現(xiàn)了一個 Redis 線程處理多個 IO 流的效果。

Redis哪些地方使用了多線程

edis 單線程指的是「接收客戶端請求->解析請求 ->進行數(shù)據(jù)讀寫等操作->發(fā)送數(shù)據(jù)給客戶端」這個過程是由一個線程（主線程）來完成的，這也是我們常說 Redis 是單線程的原因。
但是，Redis 程序并不是單線程的，Redis 在啟動的時候，是會啟動后臺線程（BIO）的：

Redis 在 2.6 版本，會啟動 2 個后臺線程，分別處理關(guān)閉文件、AOF 刷盤這兩個任務(wù)；

Redis 在 4.0 版本之后，新增了一個新的后臺線程，用來異步釋放 Redis 內(nèi)存，也就是 lazyfree 線程。例如執(zhí)行 unlink key / flushdb async / flushall async 等命令，會把這些刪除操作交給后臺線程來執(zhí)行，好處是不會導(dǎo)致 Redis 主線程卡頓。因此，當(dāng)我們要刪除一個大 key 的時候，不要使用 del 命令刪除，因為 del 是在主線程處理的，這樣會導(dǎo)致 Redis 主線程卡頓，因此我們應(yīng)該使用 unlink 命令來異步刪除大key。

之所以 Redis 為「關(guān)閉文件、AOF 刷盤、釋放內(nèi)存」這些任務(wù)創(chuàng)建單獨的線程來處理，是因為這些任務(wù)的操作都是很耗時的，如果把這些任務(wù)都放在主線程來處理，那么 Redis 主線程就很容易發(fā)生阻塞，這樣就無法處理后續(xù)的請求了。

后臺線程相當(dāng)于一個消費者，生產(chǎn)者把耗時任務(wù)丟到任務(wù)隊列中，消費者（BIO）不停輪詢這個隊列，拿出任務(wù)就去執(zhí)行對應(yīng)的方法即可。

雖然 Redis 的主要工作（網(wǎng)絡(luò) I/O 和執(zhí)行命令）一直是單線程模型，但是在 Redis 6.0 版本之后，也采用了多個 I/O 線程來處理網(wǎng)絡(luò)請求，這是因為隨著網(wǎng)絡(luò)硬件的性能提升，Redis 的性能瓶頸有時會出現(xiàn)在網(wǎng)絡(luò) I/O 的處理上。

所以為了提高網(wǎng)絡(luò) I/O 的并行度，Redis 6.0 對于網(wǎng)絡(luò) I/O 采用多線程來處理。但是對于命令的執(zhí)行，Redis 仍然使用單線程來處理，所以大家不要誤解 Redis 有多線程同時執(zhí)行命令。

Redis 官方表示，Redis 6.0 版本引入的多線程 I/O 特性對性能提升至少是一倍以上。

Redis 6.0 版本支持的 I/O 多線程特性，默認情況下 I/O 多線程只針對發(fā)送響應(yīng)數(shù)據(jù)（write client socket），并不會以多線程的方式處理讀請求（read client socket）。要想開啟多線程處理客戶端讀請求，就需要把 Redis.conf 配置文件中的 io-threads-do-reads 配置項設(shè)為 yes。

//讀請求也使用io多線程
io-threads-do-reads?yes

同時， Redis.conf 配置文件中提供了 IO 多線程個數(shù)的配置項。

//?io-threads?N，表示啟用?N-1?個?I/O?多線程（主線程也算一個?I/O?線程）
io-threads?4

關(guān)于線程數(shù)的設(shè)置，官方的建議是如果為 4 核的 CPU，建議線程數(shù)設(shè)置為 2 或 3，如果為 8 核 CPU 建議線程數(shù)設(shè)置為 6，線程數(shù)一定要小于機器核數(shù)，線程數(shù)并不是越大越好。
因此， Redis 6.0 版本之后，Redis 在啟動的時候，默認情況下會額外創(chuàng)建 6 個線程（_這里的線程數(shù)不包括主線程_）：

Redis-server ： Redis的主線程，主要負責(zé)執(zhí)行命令；bio_close_file、bio_aof_fsync、bio_lazy_free：三個后臺線程，分別異步處理關(guān)閉文件任務(wù)、AOF刷盤任務(wù)、釋放內(nèi)存任務(wù)；io_thd_1、io_thd_2、io_thd_3：三個 I/O 線程，io-threads 默認是 4 ，所以會啟動 3（4-1）個 I/O 多線程，用來分擔(dān) Redis 網(wǎng)絡(luò) I/O 的壓力。

講一下Redis底層的數(shù)據(jù)結(jié)構(gòu)

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

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

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

Redis 后續(xù)版本又支持四種數(shù)據(jù)類型，它們的應(yīng)用場景如下：

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

跳表和壓縮列表是怎么實現(xiàn)的？

跳表

Redis 只有 Zset 對象的底層實現(xiàn)用到了跳表，跳表的優(yōu)勢是能支持平均 O(logN) 復(fù)雜度的節(jié)點查找。

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

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

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

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

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

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

那跳表節(jié)點是怎么實現(xiàn)多層級的呢？這就需要看「跳表節(jié)點」的數(shù)據(jù)結(jié)構(gòu)了，如下：

typedef?struct?zskiplistNode?{
????//Zset?對象的元素值
????sds?ele;
????//元素權(quán)重值
????double?score;
????//后向指針
????struct?zskiplistNode?*backward;
??
????//節(jié)點的level數(shù)組，保存每層上的前向指針和跨度
????struct?zskiplistLevel?{
????????struct?zskiplistNode?*forward;
????????unsigned?long?span;
????}?level[];
}?zskiplistNode;

Zset 對象要同時保存「元素」和「元素的權(quán)重」，對應(yīng)到跳表節(jié)點結(jié)構(gòu)里就是 sds 類型的 ele 變量和 double 類型的 score 變量。每個跳表節(jié)點都有一個后向指針（struct zskiplistNode *backward），指向前一個節(jié)點，目的是為了方便從跳表的尾節(jié)點開始訪問節(jié)點，這樣倒序查找時很方便。

跳表是一個帶有層級關(guān)系的鏈表，而且每一層級可以包含多個節(jié)點，每一個節(jié)點通過指針連接起來，實現(xiàn)這一特性就是靠跳表節(jié)點結(jié)構(gòu)體中的zskiplistLevel 結(jié)構(gòu)體類型的 level 數(shù)組。

level 數(shù)組中的每一個元素代表跳表的一層，也就是由 zskiplistLevel 結(jié)構(gòu)體表示，比如 leve[0] 就表示第一層，leve[1] 就表示第二層。zskiplistLevel 結(jié)構(gòu)體里定義了「指向下一個跳表節(jié)點的指針」和「跨度」，跨度時用來記錄兩個節(jié)點之間的距離。

比如，下面這張圖，展示了各個節(jié)點的跨度。

第一眼看到跨度的時候，以為是遍歷操作有關(guān)，實際上并沒有任何關(guān)系，遍歷操作只需要用前向指針（struct zskiplistNode *forward）就可以完成了。

Redis 跳表在創(chuàng)建節(jié)點的時候，隨機生成每個節(jié)點的層數(shù)，并沒有嚴格維持相鄰兩層的節(jié)點數(shù)量比例為 2 : 1 的情況。

具體的做法是，跳表在創(chuàng)建節(jié)點時候，會生成范圍為[0-1]的一個隨機數(shù)，如果這個隨機數(shù)小于 0.25（相當(dāng)于概率 25%），那么層數(shù)就增加 1 層，然后繼續(xù)生成下一個隨機數(shù)，直到隨機數(shù)的結(jié)果大于 0.25 結(jié)束，最終確定該節(jié)點的層數(shù)。

這樣的做法，相當(dāng)于每增加一層的概率不超過 25%，層數(shù)越高，概率越低，層高最大限制是 64。

雖然我前面講解跳表的時候，圖中的跳表的「頭節(jié)點」都是 3 層高，但是其實如果層高最大限制是 64，那么在創(chuàng)建跳表「頭節(jié)點」的時候，就會直接創(chuàng)建 64 層高的頭節(jié)點。

壓縮列表

壓縮列表是 Redis 為了節(jié)約內(nèi)存而開發(fā)的，它是由連續(xù)內(nèi)存塊組成的順序型數(shù)據(jù)結(jié)構(gòu)，有點類似于數(shù)組。

壓縮列表在表頭有三個字段：

zlbytes，記錄整個壓縮列表占用對內(nèi)存字節(jié)數(shù)；_

zltail，記錄壓縮列表「尾部」節(jié)點距離起始地址由多少字節(jié)，也就是列表尾的偏移量；_

zllen，記錄壓縮列表包含的節(jié)點數(shù)量；_

zlend，標記壓縮列表的結(jié)束點，固定值 0xFF（十進制255）。

在壓縮列表中，如果我們要查找定位第一個元素和最后一個元素，可以通過表頭三個字段（zllen）的長度直接定位，復(fù)雜度是 O(1)。而查找其他元素時，就沒有這么高效了，只能逐個查找，此時的復(fù)雜度就是 O(N) 了，因此壓縮列表不適合保存過多的元素。

另外，壓縮列表節(jié)點（entry）的構(gòu)成如下：

壓縮列表節(jié)點包含三部分內(nèi)容：

prevlen，記錄了「前一個節(jié)點」的長度，目的是為了實現(xiàn)從后向前遍歷；_

encoding，記錄了當(dāng)前節(jié)點實際數(shù)據(jù)的「類型和長度」，類型主要有兩種：字符串和整數(shù)。_

data，記錄了當(dāng)前節(jié)點的實際數(shù)據(jù)，類型和長度都由 encoding 決定；

當(dāng)我們往壓縮列表中插入數(shù)據(jù)時，壓縮列表就會根據(jù)數(shù)據(jù)類型是字符串還是整數(shù)，以及數(shù)據(jù)的大小，會使用不同空間大小的 prevlen 和 encoding 這兩個元素里保存的信息，這種根據(jù)數(shù)據(jù)大小和類型進行不同的空間大小分配的設(shè)計思想，正是 Redis 為了節(jié)省內(nèi)存而采用的。

壓縮列表的缺點是會發(fā)生連鎖更新的問題，因此連鎖更新一旦發(fā)生，就會導(dǎo)致壓縮列表占用的內(nèi)存空間要多次重新分配，這就會直接影響到壓縮列表的訪問性能。

所以說，雖然壓縮列表緊湊型的內(nèi)存布局能節(jié)省內(nèi)存開銷，但是如果保存的元素數(shù)量增加了，或是元素變大了，會導(dǎo)致內(nèi)存重新分配，最糟糕的是會有「連鎖更新」的問題。

因此，壓縮列表只會用于保存的節(jié)點數(shù)量不多的場景，只要節(jié)點數(shù)量足夠小，即使發(fā)生連鎖更新，也是能接受的。

雖說如此，Redis 針對壓縮列表在設(shè)計上的不足，在后來的版本中，新增設(shè)計了兩種數(shù)據(jù)結(jié)構(gòu)：quicklist（Redis 3.2 引入） 和 listpack（Redis 5.0 引入）。這兩種數(shù)據(jù)結(jié)構(gòu)的設(shè)計目標，就是盡可能地保持壓縮列表節(jié)省內(nèi)存的優(yōu)勢，同時解決壓縮列表的「連鎖更新」的問題。

如何保證緩存的一致性？

緩存是通過犧牲強一致性來提高性能的。這是由CAP理論決定的。緩存系統(tǒng)適用的場景就是非強一致性的場景，它屬于CAP中的AP。所以，如果需要數(shù)據(jù)庫和緩存數(shù)據(jù)保持強一致，就不適合使用緩存。

所以使用緩存提升性能，就是會有數(shù)據(jù)更新的延遲。這需要我們在設(shè)計時結(jié)合業(yè)務(wù)仔細思考是否適合用緩存。然后緩存一定要設(shè)置過期時間，這個時間太短、或者太長都不好：

太短的話請求可能會比較多的落到數(shù)據(jù)庫上，這也意味著失去了緩存的優(yōu)勢。太長的話緩存中的臟數(shù)據(jù)會使系統(tǒng)長時間處于一個延遲的狀態(tài)，而且系統(tǒng)中長時間沒有人訪問的數(shù)據(jù)一直存在內(nèi)存中不過期，浪費內(nèi)存。

但是，通過一些方案優(yōu)化處理，是可以最終一致性的。

針對刪除緩存異常的情況，可以使用 2 個方案避免：

刪除緩存重試策略（消息隊列）訂閱 binlog，再刪除緩存（Canal+消息隊列）

消息隊列方案

我們可以引入消息隊列，將第二個操作（刪除緩存）要操作的數(shù)據(jù)加入到消息隊列，由消費者來操作數(shù)據(jù)。

• • 如果應(yīng)用

  刪除緩存失敗

• • ，可以從消息隊列中重新讀取數(shù)據(jù)，然后再次刪除緩存，這個就是

  重試機制

• • 。當(dāng)然，如果重試超過的一定次數(shù)，還是沒有成功，我們就需要向業(yè)務(wù)層發(fā)送報錯信息了。如果

  刪除緩存成功

，就要把數(shù)據(jù)從消息隊列中移除，避免重復(fù)操作，否則就繼續(xù)重試。

舉個例子，來說明重試機制的過程。

重試刪除緩存機制還可以，就是會造成好多業(yè)務(wù)代碼入侵。

訂閱 MySQL binlog，再操作緩存

「先更新數(shù)據(jù)庫，再刪緩存」的策略的第一步是更新數(shù)據(jù)庫，那么更新數(shù)據(jù)庫成功，就會產(chǎn)生一條變更日志，記錄在 binlog 里。

于是我們就可以通過訂閱 binlog 日志，拿到具體要操作的數(shù)據(jù)，然后再執(zhí)行緩存刪除，阿里巴巴開源的 Canal 中間件就是基于這個實現(xiàn)的。

Canal 模擬 MySQL 主從復(fù)制的交互協(xié)議，把自己偽裝成一個 MySQL 的從節(jié)點，向 MySQL 主節(jié)點發(fā)送 dump 請求，MySQL 收到請求后，就會開始推送 Binlog 給 Canal，Canal 解析 Binlog 字節(jié)流之后，轉(zhuǎn)換為便于讀取的結(jié)構(gòu)化數(shù)據(jù)，供下游程序訂閱使用。

下圖是 Canal 的工作原理：

將binlog日志采集發(fā)送到MQ隊列里面，然后編寫一個簡單的緩存刪除消息者訂閱binlog日志，根據(jù)更新log刪除緩存，并且通過ACK機制確認處理這條更新log，保證數(shù)據(jù)緩存一致性

Java

ConcurrentHashMap為什么是線程安全的？

JDK 1.7 ConcurrentHashMap

在 JDK 1.7 中它使用的是數(shù)組加鏈表的形式實現(xiàn)的，而數(shù)組又分為：大數(shù)組 Segment 和小數(shù)組 HashEntry。

Segment 是一種可重入鎖（ReentrantLock），在 ConcurrentHashMap 里扮演鎖的角色；HashEntry 則用于存儲鍵值對數(shù)據(jù)。一個 ConcurrentHashMap 里包含一個 Segment 數(shù)組，一個 Segment 里包含一個 HashEntry 數(shù)組，每個 HashEntry 是一個鏈表結(jié)構(gòu)的元素。

JDK 1.7 ConcurrentHashMap 分段鎖技術(shù)將數(shù)據(jù)分成一段一段的存儲，然后給每一段數(shù)據(jù)配一把鎖，當(dāng)一個線程占用鎖訪問其中一個段數(shù)據(jù)的時候，其他段的數(shù)據(jù)也能被其他線程訪問，能夠?qū)崿F(xiàn)真正的并發(fā)訪問。

JDK 1.8 ConcurrentHashMap

在 JDK 1.7 中，ConcurrentHashMap 雖然是線程安全的，但因為它的底層實現(xiàn)是數(shù)組 + 鏈表的形式，所以在數(shù)據(jù)比較多的情況下訪問是很慢的，因為要遍歷整個鏈表，而 JDK 1.8 則使用了數(shù)組 + 鏈表/紅黑樹的方式優(yōu)化了 ConcurrentHashMap 的實現(xiàn)，具體實現(xiàn)結(jié)構(gòu)如下：

JDK 1.8 ConcurrentHashMap JDK 1.8 ConcurrentHashMap 主要通過 volatile + CAS 或者 synchronized 來實現(xiàn)的線程安全的。添加元素時首先會判斷容器是否為空：

如果為空則使用 ?volatile ?加 ?CAS ?來初始化如果容器不為空，則根據(jù)存儲的元素計算該位置是否為空。
• 如果根據(jù)存儲的元素計算結(jié)果為空，則利用 ?CAS ?設(shè)置該節(jié)點；如果根據(jù)存儲的元素計算結(jié)果不為空，則使用 synchronized ?，然后，遍歷桶中的數(shù)據(jù)，并替換或新增節(jié)點到桶中，最后再判斷是否需要轉(zhuǎn)為紅黑樹，這樣就能保證并發(fā)訪問時的線程安全了。

如果把上面的執(zhí)行用一句話歸納的話，就相當(dāng)于是ConcurrentHashMap通過對頭結(jié)點加鎖來保證線程安全的，鎖的粒度相比 Segment 來說更小了，發(fā)生沖突和加鎖的頻率降低了，并發(fā)操作的性能就提高了。而且 JDK 1.8 使用的是紅黑樹優(yōu)化了之前的固定鏈表，那么當(dāng)數(shù)據(jù)量比較大的時候，查詢性能也得到了很大的提升，從之前的 O(n) 優(yōu)化到了 O(logn) 的時間復(fù)雜度。

OS

講一下銀行家算法

系統(tǒng)發(fā)生死鎖是很正常的，我們需要主動去預(yù)防死鎖，即進行有序的資源分配，使用銀行家算法。銀行家算法是最有代表性的避免死鎖的算法。
為什么叫銀行家算法呢？就是這個算法的邏輯很像銀行放貸的邏輯，也就是盡可能避免壞賬的出現(xiàn)。
銀行家算法的業(yè)務(wù)邏輯如下。

不負荷執(zhí)行：一個進程的最大需求量不超過系統(tǒng)擁有的總資源數(shù)，才會被接納執(zhí)行。

可分期：一個進程可以分期請求資源，但總請求書不可超過最大需求量。

推遲分配：當(dāng)系統(tǒng)現(xiàn)有資源數(shù)小于進程需求時，對進程的需求可以延遲分配，但總讓進程在有限時間內(nèi)獲取資源。

聽起來有點繞，我們還是舉個例子來說明。

假如系統(tǒng)中有三類互斥資源 R1、R2、R3，可用資源數(shù)分別是 9、8、5，在指定時刻有 P1、P2、P3、P4 和 P5 這五個進程，這些進程的對三類互斥資源的最大需求量和已分配資源數(shù)如下表所示，那么系統(tǒng)如何先后運行這五個進程，不會發(fā)生死鎖問題？

第一步：分析

首先分析首次需求的資源，系統(tǒng)剩余可用資源數(shù)分別是 2、1、0，各進程需要的資源數(shù)如下表所示。

資源 R1 的剩余可用資源數(shù) = 9 - 1 - 2 - 2 - 1 - 1 = 2。
資源 R2 的剩余可用資源數(shù) = 8 - 2 - 1 - 1 - 2 - 1 = 1。
資源 R3 的剩余可用資源數(shù) = 5 - 1 - 1 - 0 - 0 - 3 = 0。

根據(jù)銀行家算法不負荷原則【一個進程的最大需求量不超過系統(tǒng)擁有的總資源數(shù)，才會被接納執(zhí)行】，優(yōu)先給進程 P2 執(zhí)行，因為剩余的 0 1 0 資源夠讓 P2 執(zhí)行。

第二步：執(zhí)行 P2

P2 執(zhí)行之后，釋放了剛剛放入的 2 1 0 資源，而且可以釋放已分配的 2 1 1 資源，所以此時的資源剩余量。

資源 R1 的剩余可用資源數(shù) = 原資源數(shù) - 執(zhí)行 P2 消耗數(shù) + P2 執(zhí)行完釋放的資源數(shù) = 2 - 0 +（2 + 0） = 4。
資源 R2 的剩余可用資源數(shù) = 原資源數(shù) - 執(zhí)行 P2 消耗數(shù) + P2 執(zhí)行完釋放的資源數(shù) = 1 - 1 + （1 + 1） = 2。
資源 R3 的剩余可用資源數(shù) = 原資源數(shù) - 執(zhí)行 P2 消耗數(shù) + P2 執(zhí)行完釋放的資源數(shù) = 0 - 0 +（0 + 1） = 1。

執(zhí)行完成 P2 后，操作系統(tǒng)剩余可用資源數(shù)為 4 2 1。

第三步：執(zhí)行 P4

此時操作系統(tǒng)剩余可用資源數(shù)為 4 2 1，只能執(zhí)行進程 P4，因為其他進程資源不夠。

P4 執(zhí)行之后，釋放了剛剛放入的 0 0 1 資源，而且可以釋放已分配的 1 2 1 資源，所以此時的資源剩余量。

資源 R1 的剩余可用資源數(shù) = 原資源數(shù) - 執(zhí)行 P4 消耗數(shù) + P4 執(zhí)行完釋放的資源數(shù) = 4 - 0 +（1 + 0） = 5。
資源 R2 的剩余可用資源數(shù) = 原資源數(shù) - 執(zhí)行 P4 消耗數(shù) + P4 執(zhí)行完釋放的資源數(shù) = 2 - 0 + （2 + 0） = 4。
資源 R3 的剩余可用資源數(shù) = 原資源數(shù) - 執(zhí)行 P4 消耗數(shù) + P4 執(zhí)行完釋放的資源數(shù) = 1 - 1 +（1 + 1） = 2。

執(zhí)行完成 P4 后，操作系統(tǒng)剩余可用資源數(shù)為 5 4 2。

第四步：執(zhí)行 P5

此時操作系統(tǒng)剩余可用資源數(shù)為 5 4 2，只能執(zhí)行進程 P5，因為其他進程資源不夠。

P5 執(zhí)行之后，釋放了剛剛放入的 2 3 1 資源，而且可以釋放已分配的 1 1 3 資源，所以此時的資源剩余量。

資源 R1 的剩余可用資源數(shù) = 原資源數(shù) - 執(zhí)行 P5 消耗數(shù) + P5 執(zhí)行完釋放的資源數(shù) = 5 - 2 +（1 + 2） = 6。
資源 R2 的剩余可用資源數(shù) = 原資源數(shù) - 執(zhí)行 P5 消耗數(shù) + P5 執(zhí)行完釋放的資源數(shù) = 4 - 3 + （1 + 3） = 5。
資源 R3 的剩余可用資源數(shù) = 原資源數(shù) - 執(zhí)行 P5 消耗數(shù) + P5 執(zhí)行完釋放的資源數(shù) = 2 - 1 +（3 + 1） = 5。

執(zhí)行完成 P5 后，操作系統(tǒng)剩余可用資源數(shù)為 6 5 5。

第五步：執(zhí)行 P1 或者 P3

此時操作系統(tǒng)剩余可用資源數(shù)為 6 5 5，可以執(zhí)行 P1 或 P3。

所以安全執(zhí)行順序為 p2 => p4 => p5 => p1 => p3 或 p2 => p4 => p5 => p3 => p1。

在這里插入圖片描述或在這里插入圖片描述

銀行家算法總結(jié)

銀行家算法的核心思想，就是在分配給進程資源前，首先判斷這個進程的安全性，也就是預(yù)執(zhí)行，判斷分配后是否產(chǎn)生死鎖現(xiàn)象。如果系統(tǒng)當(dāng)前資源能滿足其執(zhí)行，則嘗試分配，如果不滿足則讓該進程等待。通過不斷檢查剩余可用資源是否滿足某個進程的最大需求，如果可以則加入安全序列，并把該進程當(dāng)前持有的資源回收；不斷重復(fù)這個過程，看最后能否實現(xiàn)讓所有進程都加入安全序列。安全序列一定不會發(fā)生死鎖，但沒有死鎖不一定是安全序列。

講一下頁表

分頁是把整個虛擬和物理內(nèi)存空間切成一段段固定尺寸的大小。這樣一個連續(xù)并且尺寸固定的內(nèi)存空間，我們叫頁（_Page_）。在 Linux 下，每一頁的大小為 4KB。
虛擬地址與物理地址之間通過頁表來映射，如下圖：

頁表是存儲在內(nèi)存里的，內(nèi)存管理單元 （_MMU_）就做將虛擬內(nèi)存地址轉(zhuǎn)換成物理地址的工作。

而當(dāng)進程訪問的虛擬地址在頁表中查不到時，系統(tǒng)會產(chǎn)生一個缺頁異常，進入系統(tǒng)內(nèi)核空間分配物理內(nèi)存、更新進程頁表，最后再返回用戶空間，恢復(fù)進程的運行。

內(nèi)存分頁由于內(nèi)存空間都是預(yù)先劃分好的，也就不會像內(nèi)存分段一樣，在段與段之間會產(chǎn)生間隙非常小的內(nèi)存，這正是分段會產(chǎn)生外部內(nèi)存碎片的原因。而采用了分頁，頁與頁之間是緊密排列的，所以不會有外部碎片。

但是，因為內(nèi)存分頁機制分配內(nèi)存的最小單位是一頁，即使程序不足一頁大小，我們最少只能分配一個頁，所以頁內(nèi)會出現(xiàn)內(nèi)存浪費，所以針對內(nèi)存分頁機制會有內(nèi)部內(nèi)存碎片的現(xiàn)象。

在分頁機制下，虛擬地址分為兩部分，頁號和頁內(nèi)偏移。頁號作為頁表的索引，頁表包含物理頁每頁所在物理內(nèi)存的基地址，這個基地址與頁內(nèi)偏移的組合就形成了物理內(nèi)存地址，見下圖。

總結(jié)一下，對于一個內(nèi)存地址轉(zhuǎn)換，其實就是這樣三個步驟：

把虛擬內(nèi)存地址，切分成頁號和偏移量；根據(jù)頁號，從頁表里面，查詢對應(yīng)的物理頁號；直接拿物理頁號，加上前面的偏移量，就得到了物理內(nèi)存地址。

下面舉個例子，虛擬內(nèi)存中的頁通過頁表映射為了物理內(nèi)存中的頁，如下圖：

講下為什么進程之下還要設(shè)計線程，線程之間怎么通信的

為什么要設(shè)計線程

我們舉個例子，假設(shè)你要編寫一個視頻播放器軟件，那么該軟件功能的核心模塊有三個：

從視頻文件當(dāng)中讀取數(shù)據(jù)；對讀取的數(shù)據(jù)進行解壓縮；把解壓縮后的視頻數(shù)據(jù)播放出來；

對于單進程的實現(xiàn)方式，我想大家都會是以下這個方式：對于單進程的這種方式，存在以下問題：

播放出來的畫面和聲音會不連貫，因為當(dāng) CPU 能力不夠強的時候，Read 的時候可能進程就等在這了，這樣就會導(dǎo)致等半天才進行數(shù)據(jù)解壓和播放；各個函數(shù)之間不是并發(fā)執(zhí)行，影響資源的使用效率；

那改進成多進程的方式：

對于多進程的這種方式，依然會存在問題：

進程之間如何通信，共享數(shù)據(jù)？維護進程的系統(tǒng)開銷較大，如創(chuàng)建進程時，分配資源、建立 PCB；終止進程時，回收資源、撤銷 PCB；進程切換時，保存當(dāng)前進程的狀態(tài)信息；

那到底如何解決呢？需要有一種新的實體，滿足以下特性：

實體之間可以并發(fā)運行；實體之間共享相同的地址空間；

這個新的實體，就是**線程( Thread )**，線程之間可以并發(fā)運行且共享相同的地址空間。

線程間的通信方式

Linux系統(tǒng)提供了五種用于線程通信的方式：互斥鎖、讀寫鎖、條件變量、自旋鎖和信號量。

互斥鎖（Mutex）：互斥量(mutex)從本質(zhì)上說是一把鎖，在訪問共享資源前對互斥量進行加鎖，在訪問完成后釋放互斥量上的鎖。對互斥量進行加鎖以后，任何其他試圖再次對互斥鎖加鎖的線程將會阻塞直到當(dāng)前線程釋放該互斥鎖。如果釋放互斥鎖時有多個線程阻塞，所有在該互斥鎖上的阻塞線程都會變成可運行狀態(tài)，第一個變?yōu)檫\行狀態(tài)的線程可以對互斥鎖加鎖，其他線程將會看到互斥鎖依然被鎖住，只能回去再次等待它重新變?yōu)榭捎谩?/p>

條件變量（Condition Variables）：條件變量(cond)是在多線程程序中用來實現(xiàn)"等待--》喚醒"邏輯常用的方法。條件變量利用線程間共享的全局變量進行同步的一種機制，主要包括兩個動作：一個線程等待"條件變量的條件成立"而掛起；另一個線程使“條件成立”。為了防止競爭，條件變量的使用總是和一個互斥鎖結(jié)合在一起。線程在改變條件狀態(tài)前必須首先鎖住互斥量，函數(shù)pthread_cond_wait把自己放到等待條件的線程列表上，然后對互斥鎖解鎖(這兩個操作是原子操作)。在函數(shù)返回時，互斥量再次被鎖住。

自旋鎖（Spinlock）：自旋鎖通過 CPU 提供的 CAS 函數(shù)（_Compare And Swap_），在「用戶態(tài)」完成加鎖和解鎖操作，不會主動產(chǎn)生線程上下文切換，所以相比互斥鎖來說，會快一些，開銷也小一些。一般加鎖的過程，包含兩個步驟：第一步，查看鎖的狀態(tài)，如果鎖是空閑的，則執(zhí)行第二步；第二步，將鎖設(shè)置為當(dāng)前線程持有；使用自旋鎖的時候，當(dāng)發(fā)生多線程競爭鎖的情況，加鎖失敗的線程會「忙等待」，直到它拿到鎖。CAS 函數(shù)就把這兩個步驟合并成一條硬件級指令，形成

原子指令，這樣就保證了這兩個步驟是不可分割的，要么一次性執(zhí)行完兩個步驟，要么兩個步驟都不執(zhí)行。這里的「忙等待」可以用 while 循環(huán)等待實現(xiàn)，不過最好是使用 CPU 提供的 PAUSE 指令來實現(xiàn)「忙等待」，因為可以減少循環(huán)等待時的耗電量。

信號量（Semaphores）：信號量可以是命名的（有名信號量）或無名的（僅限于當(dāng)前進程內(nèi)的線程），用于控制對資源的訪問次數(shù)。通常

信號量表示資源的數(shù)量，對應(yīng)的變量是一個整型（sem）變量。另外，還有兩個原子操作的系統(tǒng)調(diào)用函數(shù)來控制信號量的

• ，分別是：_P 操作_：將 sem 減 1，相減后，如果 sem < 0，則進程/線程進入阻塞等待，否則繼續(xù)，表明 P 操作可能會阻塞；_V 操作_：將 sem 加 1，相加后，如果 sem <= 0，喚醒一個等待中的進程/線程，表明 V 操作不會阻塞；

讀寫鎖（Read-Write Locks）：讀寫鎖從字面意思我們也可以知道，它由「讀鎖」和「寫鎖」兩部分構(gòu)成，如果只讀取共享資源用「讀鎖」加鎖，如果要修改共享資源則用「寫鎖」加鎖。所以，讀寫鎖適用于能明確區(qū)分讀操作和寫操作的場景。

• • 讀寫鎖的工作原理是：當(dāng)「寫鎖」沒有被線程持有時，多個線程能夠并發(fā)地持有讀鎖，這大大提高了共享資源的訪問效率，因為「讀鎖」是用于讀取共享資源的場景，所以多個線程同時持有讀鎖也不會破壞共享資源的數(shù)據(jù)。但是，一旦「寫鎖」被線程持有后，讀線程的獲取讀鎖的操作會被阻塞，而且其他寫線程的獲取寫鎖的操作也會被阻塞。所以說，寫鎖是獨占鎖，因為任何時刻只能有一個線程持有寫鎖，類似互斥鎖和自旋鎖，而讀鎖是共享鎖，因為讀鎖可以被多個線程同時持有。知道了讀寫鎖的工作原理后，我們可以發(fā)現(xiàn)，

  讀寫鎖在讀多寫少的場景，能發(fā)揮出優(yōu)勢。

MySQL

講一講mysql的引擎吧，你有什么了解？

MySQL中常用的存儲引擎分別是：MyISAM存儲引擎、innoDB存儲引擎，他們的區(qū)別在于：

事務(wù)：InnoDB 支持事務(wù)，MyISAM 不支持事務(wù)，這是 MySQL 將默認存儲引擎從 MyISAM 變成 InnoDB 的重要原因之一。索引結(jié)構(gòu)：InnoDB 是聚簇索引，MyISAM 是非聚簇索引。聚簇索引的文件存放在主鍵索引的葉子節(jié)點上，因此 InnoDB 必須要有主鍵，通過主鍵索引效率很高。但是輔助索引需要兩次查詢，先查詢到主鍵，然后再通過主鍵查詢到數(shù)據(jù)。因此，主鍵不應(yīng)該過大，因為主鍵太大，其他索引也都會很大。而 MyISAM 是非聚簇索引，數(shù)據(jù)文件是分離的，索引保存的是數(shù)據(jù)文件的指針。主鍵索引和輔助索引是獨立的。鎖粒度：InnoDB 最小的鎖粒度是行鎖，MyISAM 最小的鎖粒度是表鎖。一個更新語句會鎖住整張表，導(dǎo)致其他查詢和更新都會被阻塞，因此并發(fā)訪問受限。count 的效率：InnoDB 不保存表的具體行數(shù)，執(zhí)行 select count(*) from table 時需要全表掃描。而MyISAM 用一個變量保存了整個表的行數(shù)，執(zhí)行上述語句時只需要讀出該變量即可，速度很快。

講一下mysql里的鎖？

在 MySQL 里，根據(jù)加鎖的范圍，可以分為全局鎖、表級鎖和行鎖三類。

全局鎖：通過flush tables with read lock 語句會將整個數(shù)據(jù)庫就處于只讀狀態(tài)了，這時其他線程執(zhí)行以下操作，增刪改或者表結(jié)構(gòu)修改都會阻塞。全局鎖主要應(yīng)用于做

全庫邏輯備份，這樣在備份數(shù)據(jù)庫期間，不會因為數(shù)據(jù)或表結(jié)構(gòu)的更新，而出現(xiàn)備份文件的數(shù)據(jù)與預(yù)期的不一樣。

表級鎖：MySQL 里面表級別的鎖有這幾種：

• • 表鎖：通過lock tables 語句可以對表加表鎖，表鎖除了會限制別的線程的讀寫外，也會限制本線程接下來的讀寫操作。元數(shù)據(jù)鎖：當(dāng)我們對數(shù)據(jù)庫表進行操作時，會自動給這個表加上 MDL，對一張表進行 CRUD 操作時，加的是

MDL 讀鎖；對一張表做結(jié)構(gòu)變更操作的時候，加的是MDL 寫鎖

• • ；MDL 是為了保證當(dāng)用戶對表執(zhí)行 CRUD 操作時，防止其他線程對這個表結(jié)構(gòu)做了變更。意向鎖：當(dāng)執(zhí)行插入、更新、刪除操作，需要先對表加上「意向獨占鎖」，然后對該記錄加獨占鎖。

意向鎖的目的是為了快速判斷表里是否有記錄被加鎖。

行級鎖：InnoDB 引擎是支持行級鎖的，而 MyISAM 引擎并不支持行級鎖。

• 記錄鎖，鎖住的是一條記錄。而且記錄鎖是有 S 鎖和 X 鎖之分的，滿足讀寫互斥，寫寫互斥間隙鎖，只存在于可重復(fù)讀隔離級別，目的是為了解決可重復(fù)讀隔離級別下幻讀的現(xiàn)象。Next-Key Lock 稱為臨鍵鎖，是 Record Lock + Gap Lock 的組合，鎖定一個范圍，并且鎖定記錄本身。

MySQL主從復(fù)制了解嗎

MySQL 的主從復(fù)制依賴于 binlog ，也就是記錄 MySQL 上的所有變化并以二進制形式保存在磁盤上。復(fù)制的過程就是將 binlog 中的數(shù)據(jù)從主庫傳輸?shù)綇膸焐稀?br /> 這個過程一般是異步的，也就是主庫上執(zhí)行事務(wù)操作的線程不會等待復(fù)制 binlog 的線程同步完成。

MySQL 集群的主從復(fù)制過程梳理成 3 個階段：

寫入 Binlog：主庫寫 binlog 日志，提交事務(wù)，并更新本地存儲數(shù)據(jù)。

同步 Binlog：把 binlog 復(fù)制到所有從庫上，每個從庫把 binlog 寫到暫存日志中。

回放 Binlog：回放 binlog，并更新存儲引擎中的數(shù)據(jù)。

具體詳細過程如下：

MySQL 主庫在收到客戶端提交事務(wù)的請求之后，會先寫入 binlog，再提交事務(wù)，更新存儲引擎中的數(shù)據(jù)，事務(wù)提交完成后，返回給客戶端“操作成功”的響應(yīng)。從庫會創(chuàng)建一個專門的 I/O 線程，連接主庫的 log dump 線程，來接收主庫的 binlog 日志，再把 binlog 信息寫入 relay log 的中繼日志里，再返回給主庫“復(fù)制成功”的響應(yīng)。從庫會創(chuàng)建一個用于回放 binlog 的線程，去讀 relay log 中繼日志，然后回放 binlog 更新存儲引擎中的數(shù)據(jù)，最終實現(xiàn)主從的數(shù)據(jù)一致性。

在完成主從復(fù)制之后，你就可以在寫數(shù)據(jù)時只寫主庫，在讀數(shù)據(jù)時只讀從庫，這樣即使寫請求會鎖表或者鎖記錄，也不會影響讀請求的執(zhí)行。

主從延遲都有什么處理方法？

強制走主庫方案：對于大事務(wù)或資源密集型操作，直接在主庫上執(zhí)行，避免從庫的額外延遲。

B+樹的特點是什么？

B+樹是一種自平衡的多路查找樹，所有葉節(jié)點都位于同一層，保證了樹的平衡，使得搜索、插入和刪除操作的時間復(fù)雜度為對數(shù)級別的。非葉節(jié)點僅包含索引信息，不存儲具體的數(shù)據(jù)記錄，它們只用來引導(dǎo)搜索到正確的葉節(jié)點。非葉節(jié)點的子樹指針與關(guān)鍵字數(shù)量相同，每個子樹指針指向一個子樹，子樹中的所有鍵值都在某個區(qū)間內(nèi)。所有數(shù)據(jù)記錄都存儲在葉節(jié)點中，且葉節(jié)點中的數(shù)據(jù)是按關(guān)鍵字排序的。葉節(jié)點包含實際的數(shù)據(jù)和關(guān)鍵字，它們是數(shù)據(jù)存儲和檢索的實體單元。葉節(jié)點之間通過指針相互鏈接，形成一個鏈表，便于范圍查詢和順序遍歷。