大家好,我是小林。ZL428資訊網——每日最新資訊28at.com
今天來分析字節(jié)跳動校招后端開發(fā)面經,同學的技術棧是 Java 后端,問八股文比較多,一共經歷了一二三面,每一場面試的強度還是蠻高,每次都是 1 個小時+。ZL428資訊網——每日最新資訊28at.com
我把這幾場面試中比較有代表性的題目抽離出來給大家解析一波,給準備春招的同學做一個參考和學習,雖然是校招的面試,但是有些問題,其實社招也經常問的。ZL428資訊網——每日最新資訊28at.com
知識一學就忘原因,就是缺少溫故的過程,通過面試題的方式回顧系列的知識,也是一種高效的方式。ZL428資訊網——每日最新資訊28at.com
這次面經的考點,我簡單羅列一下:ZL428資訊網——每日最新資訊28at.com
- 操作系統(tǒng):進程調度
- 網絡:HTTP、HTTPS
- Java:線程狀態(tài)、多線程、volatile、synchronized
- Redis:數據結構、跳表、性能、場景應用、緩存一致性
- MySQL:事務、隔離級別、日志、索引、間隙鎖、最左匹配原則
- 算法:每一輪 1 個算法
Redis
Redis 有哪些數據結構?
Redis 提供了豐富的數據類型,常見的有五種數據類型:String(字符串),Hash(哈希),List(列表),Set(集合)、Zset(有序集合)。ZL428資訊網——每日最新資訊28at.com
圖片ZL428資訊網——每日最新資訊28at.com
圖片ZL428資訊網——每日最新資訊28at.com
隨著 Redis 版本的更新,后面又支持了四種數據類型:BitMap(2.2 版新增)、HyperLogLog(2.8 版新增)、GEO(3.2 版新增)、Stream(5.0 版新增)。Redis 五種數據類型的應用場景:ZL428資訊網——每日最新資訊28at.com
- String 類型的應用場景:緩存對象、常規(guī)計數、分布式鎖、共享 session 信息等。
- List 類型的應用場景:消息隊列(但是有兩個問題:1. 生產者需要自行實現(xiàn)全局唯一 ID;2. 不能以消費組形式消費數據)等。
- Hash 類型:緩存對象、購物車等。
- Set 類型:聚合計算(并集、交集、差集)場景,比如點贊、共同關注、抽獎活動等。
- Zset 類型:排序場景,比如排行榜、電話和姓名排序等。
Redis 后續(xù)版本又支持四種數據類型,它們的應用場景如下:ZL428資訊網——每日最新資訊28at.com
- BitMap(2.2 版新增):二值狀態(tài)統(tǒng)計的場景,比如簽到、判斷用戶登陸狀態(tài)、連續(xù)簽到用戶總數等;
- HyperLogLog(2.8 版新增):海量數據基數統(tǒng)計的場景,比如百萬級網頁 UV 計數等;
- GEO(3.2 版新增):存儲地理位置信息的場景,比如滴滴叫車;
- Stream(5.0 版新增):消息隊列,相比于基于 List 類型實現(xiàn)的消息隊列,有這兩個特有的特性:自動生成全局唯一消息ID,支持以消費組形式消費數據。
Zset 使用了什么數據結構?
Zset 類型的底層數據結構是由壓縮列表或跳表實現(xiàn)的:ZL428資訊網——每日最新資訊28at.com
- 如果有序集合的元素個數小于 128 個,并且每個元素的值小于 64 字節(jié)時,Redis 會使用壓縮列表作為 Zset 類型的底層數據結構;
- 如果有序集合的元素不滿足上面的條件,Redis 會使用跳表作為 Zset 類型的底層數據結構;
在 Redis 7.0 中,壓縮列表數據結構已經廢棄了,交由 listpack 數據結構來實現(xiàn)了。ZL428資訊網——每日最新資訊28at.com
SkipList 了解嗎?
鏈表在查找元素的時候,因為需要逐一查找,所以查詢效率非常低,時間復雜度是O(N),于是就出現(xiàn)了跳表。跳表是在鏈表基礎上改進過來的,實現(xiàn)了一種「多層」的有序鏈表,這樣的好處是能快讀定位數據。ZL428資訊網——每日最新資訊28at.com
那跳表長什么樣呢?我這里舉個例子,下圖展示了一個層級為 3 的跳表。ZL428資訊網——每日最新資訊28at.com
圖片ZL428資訊網——每日最新資訊28at.com
圖中頭節(jié)點有 L0~L2 三個頭指針,分別指向了不同層級的節(jié)點,然后每個層級的節(jié)點都通過指針連接起來:ZL428資訊網——每日最新資訊28at.com
- 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。ZL428資訊網——每日最新資訊28at.com
可以看到,這個查找過程就是在多個層級上跳來跳去,最后定位到元素。當數據量很大時,跳表的查找復雜度就是 O(logN)。ZL428資訊網——每日最新資訊28at.com
跳表的時間復雜度是多少?
跳表中查找一個元素的時間復雜度為O(logn),空間復雜度是 O(n)。ZL428資訊網——每日最新資訊28at.com
為什么 MysSQL 不用 SkipList?
B+樹的高度在3層時存儲的數據可能已達千萬級別,但對于跳表而言同樣去維護千萬的數據量那么所造成的跳表層數過高而導致的磁盤io次數增多,也就是使用B+樹在存儲同樣的數據下磁盤io次數更少。ZL428資訊網——每日最新資訊28at.com
Redis 使用場景?
Redis 是一種基于內存的數據庫,對數據的讀寫操作都是在內存中完成,因此讀寫速度非常快,常用于緩存,消息隊列、分布式鎖等場景。ZL428資訊網——每日最新資訊28at.com
圖片ZL428資訊網——每日最新資訊28at.com
Redis用途ZL428資訊網——每日最新資訊28at.com
Redis 提供了多種數據類型來支持不同的業(yè)務場景,比如 String(字符串)、Hash(哈希)、 List (列表)、Set(集合)、Zset(有序集合)、Bitmaps(位圖)、HyperLogLog(基數統(tǒng)計)、GEO(地理信息)、Stream(流),并且對數據類型的操作都是原子性的,因為執(zhí)行命令由單線程負責的,不存在并發(fā)競爭的問題。ZL428資訊網——每日最新資訊28at.com
除此之外,Redis 還支持事務 、持久化、Lua 腳本、多種集群方案(主從復制模式、哨兵模式、切片機群模式)、發(fā)布/訂閱模式,內存淘汰機制、過期刪除機制等等。ZL428資訊網——每日最新資訊28at.com
Redis 性能好的原因是什么?
官方使用基準測試的結果是,單線程的 Redis 吞吐量可以達到 10W/每秒,如下圖所示:ZL428資訊網——每日最新資訊28at.com
圖片ZL428資訊網——每日最新資訊28at.com
之所以 Redis 采用單線程(網絡 I/O 和執(zhí)行命令)那么快,有如下幾個原因:ZL428資訊網——每日最新資訊28at.com
- Redis 的大部分操作都在內存中完成,并且采用了高效的數據結構,因此 Redis 瓶頸可能是機器的內存或者網絡帶寬,而并非 CPU,既然 CPU 不是瓶頸,那么自然就采用單線程的解決方案了;
- Redis 采用單線程模型可以避免了多線程之間的競爭,省去了多線程切換帶來的時間和性能上的開銷,而且也不會導致死鎖問題。
- Redis 采用了 I/O 多路復用機制處理大量的客戶端 Socket 請求,IO 多路復用機制是指一個線程處理多個 IO 流,就是我們經常聽到的 select/epoll 機制。簡單來說,在 Redis 只運行單線程的情況下,該機制允許內核中,同時存在多個監(jiān)聽 Socket 和已連接 Socket。內核會一直監(jiān)聽這些 Socket 上的連接請求或數據請求。一旦有請求到達,就會交給 Redis 線程處理,這就實現(xiàn)了一個 Redis 線程處理多個 IO 流的效果。
Redis 和 MySQL 如何保證一致性
可以采用「先更新數據庫,再刪除緩存」的更新策略+過期時間來兜底。ZL428資訊網——每日最新資訊28at.com
我們用「讀 + 寫」請求的并發(fā)的場景來分析。ZL428資訊網——每日最新資訊28at.com
假如某個用戶數據在緩存中不存在,請求 A 讀取數據時從數據庫中查詢到年齡為 20,在未寫入緩存中時另一個請求 B 更新數據。它更新數據庫中的年齡為 21,并且清空緩存。這時請求 A 把從數據庫中讀到的年齡為 20 的數據寫入到緩存中。ZL428資訊網——每日最新資訊28at.com
圖片ZL428資訊網——每日最新資訊28at.com
最終,該用戶年齡在緩存中是 20(舊值),在數據庫中是 21(新值),緩存和數據庫數據不一致。ZL428資訊網——每日最新資訊28at.com
從上面的理論上分析,先更新數據庫,再刪除緩存也是會出現(xiàn)數據不一致性的問題,但是在實際中,這個問題出現(xiàn)的概率并不高。ZL428資訊網——每日最新資訊28at.com
因為緩存的寫入通常要遠遠快于數據庫的寫入,所以在實際中很難出現(xiàn)請求 B 已經更新了數據庫并且刪除了緩存,請求 A 才更新完緩存的情況。ZL428資訊網——每日最新資訊28at.com
而一旦請求 A 早于請求 B 刪除緩存之前更新了緩存,那么接下來的請求就會因為緩存不命中而從數據庫中重新讀取數據,所以不會出現(xiàn)這種不一致的情況。ZL428資訊網——每日最新資訊28at.com
所以,「先更新數據庫 + 再刪除緩存」的方案,是可以保證數據一致性的。ZL428資訊網——每日最新資訊28at.com
而且為了確保萬無一失,還給緩存數據加上了「過期時間」,就算在這期間存在緩存數據不一致,有過期時間來兜底,這樣也能達到最終一致。ZL428資訊網——每日最新資訊28at.com
MySQL
事務有哪些特性?
事務 4 個特性,分別如下:ZL428資訊網——每日最新資訊28at.com
- 原子性(Atomicity):一個事務中的所有操作,要么全部完成,要么全部不完成,不會結束在中間某個環(huán)節(jié),而且事務在執(zhí)行過程中發(fā)生錯誤,會被回滾到事務開始前的狀態(tài),就像這個事務從來沒有執(zhí)行過一樣,就好比買一件商品,購買成功時,則給商家付了錢,商品到手;購買失敗時,則商品在商家手中,消費者的錢也沒花出去。
- 一致性(Consistency):是指事務操作前和操作后,數據滿足完整性約束,數據庫保持一致性狀態(tài)。比如,用戶 A 和用戶 B 在銀行分別有 800 元和 600 元,總共 1400 元,用戶 A 給用戶 B 轉賬 200 元,分為兩個步驟,從 A 的賬戶扣除 200 元和對 B 的賬戶增加 200 元。一致性就是要求上述步驟操作后,最后的結果是用戶 A 還有 600 元,用戶 B 有 800 元,總共 1400 元,而不會出現(xiàn)用戶 A 扣除了 200 元,但用戶 B 未增加的情況(該情況,用戶 A 和 B 均為 600 元,總共 1200 元)。
- 隔離性(Isolation):數據庫允許多個并發(fā)事務同時對其數據進行讀寫和修改的能力,隔離性可以防止多個事務并發(fā)執(zhí)行時由于交叉執(zhí)行而導致數據的不一致,因為多個事務同時使用相同的數據時,不會相互干擾,每個事務都有一個完整的數據空間,對其他并發(fā)事務是隔離的。也就是說,消費者購買商品這個事務,是不影響其他消費者購買的。
- 持久性(Durability):事務處理結束后,對數據的修改就是永久的,即便系統(tǒng)故障也不會丟失。
隔離性有哪些隔離級別?
四個隔離級別如下:ZL428資訊網——每日最新資訊28at.com
- 讀未提交(*read uncommitted*),指一個事務還沒提交時,它做的變更就能被其他事務看到;
- 讀提交(*read committed*),指一個事務提交之后,它做的變更才能被其他事務看到;
- 可重復讀(*repeatable read*),指一個事務執(zhí)行過程中看到的數據,一直跟這個事務啟動時看到的數據是一致的,MySQL InnoDB 引擎的默認隔離級別;
- 串行化(*serializable* );會對記錄加上讀寫鎖,在多個事務對這條記錄進行讀寫操作時,如果發(fā)生了讀寫沖突的時候,后訪問的事務必須等前一個事務執(zhí)行完成,才能繼續(xù)執(zhí)行;
按隔離水平高低排序如下:ZL428資訊網——每日最新資訊28at.com
圖片ZL428資訊網——每日最新資訊28at.com
針對不同的隔離級別,并發(fā)事務時可能發(fā)生的現(xiàn)象也會不同。ZL428資訊網——每日最新資訊28at.com
圖片ZL428資訊網——每日最新資訊28at.com
也就是說:ZL428資訊網——每日最新資訊28at.com
- 在「讀未提交」隔離級別下,可能發(fā)生臟讀、不可重復讀和幻讀現(xiàn)象;
- 在「讀提交」隔離級別下,可能發(fā)生不可重復讀和幻讀現(xiàn)象,但是不可能發(fā)生臟讀現(xiàn)象;
- 在「可重復讀」隔離級別下,可能發(fā)生幻讀現(xiàn)象,但是不可能臟讀和不可重復讀現(xiàn)象;
- 在「串行化」隔離級別下,臟讀、不可重復讀和幻讀現(xiàn)象都不可能會發(fā)生。
MySQL 默認用的哪個級別?
MySQL 默認隔離級別是「可重復讀」,可以很大程度上避免幻讀現(xiàn)象的發(fā)生(注意是很大程度避免,并不是徹底避免),所以 MySQL 并不會使用「串行化」隔離級別來避免幻讀現(xiàn)象的發(fā)生,因為使用「串行化」隔離級別會影響性能。ZL428資訊網——每日最新資訊28at.com
間隙鎖的原理
Gap Lock 稱為間隙鎖,只存在于可重復讀隔離級別,目的是為了解決可重復讀隔離級別下幻讀的現(xiàn)象。ZL428資訊網——每日最新資訊28at.com
假設,表中有一個范圍 id 為(3,5)間隙鎖,那么其他事務就無法插入 id = 4 這條記錄了,這樣就有效的防止幻讀現(xiàn)象的發(fā)生。ZL428資訊網——每日最新資訊28at.com
imgZL428資訊網——每日最新資訊28at.com
間隙鎖雖然存在 X 型間隙鎖和 S 型間隙鎖,但是并沒有什么區(qū)別,間隙鎖之間是兼容的,即兩個事務可以同時持有包含共同間隙范圍的間隙鎖,并不存在互斥關系,因為間隙鎖的目的是防止插入幻影記錄而提出的。ZL428資訊網——每日最新資訊28at.com
什么時候會加間隙鎖?
當我們用唯一索引進行等值查詢的時候,查詢的記錄不存在的時候,在索引樹找到第一條大于該查詢記錄的記錄后,將該記錄的索引中的 next-key lock 會退化成「間隙鎖」。ZL428資訊網——每日最新資訊28at.com
假設事務 A 執(zhí)行了這條等值查詢語句,查詢的記錄是「不存在」于表中的。ZL428資訊網——每日最新資訊28at.com
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; 這條語句,查看事務執(zhí)行 SQL 過程中加了什么鎖。ZL428資訊網——每日最新資訊28at.com
圖片ZL428資訊網——每日最新資訊28at.com
從上圖可以看到,共加了兩個鎖,分別是:ZL428資訊網——每日最新資訊28at.com
因此,此時事務 A 在 id = 5 記錄的主鍵索引上加的是間隙鎖,鎖住的范圍是 (1, 5)。ZL428資訊網——每日最新資訊28at.com
圖片ZL428資訊網——每日最新資訊28at.com
接下來,如果有其他事務插入 id 值為 2、3、4 這一些記錄的話,這些插入語句都會發(fā)生阻塞。ZL428資訊網——每日最新資訊28at.com
注意,如果其他事務插入的 id = 1 或者 id = 5 的記錄話,并不會發(fā)生阻塞,而是報主鍵沖突的錯誤,因為表中已經存在 id = 1 和 id = 5 的記錄了。ZL428資訊網——每日最新資訊28at.com
比如,下面這個例子:ZL428資訊網——每日最新資訊28at.com
imgZL428資訊網——每日最新資訊28at.com
因為事務 A 在 id = 5 記錄的主鍵索引上加了范圍為 (1, 5) 的 X 型間隙鎖,所以事務 B 在插入一條 id 為 3 的記錄時會被阻塞住,即無法插入 id = 3 的記錄。ZL428資訊網——每日最新資訊28at.com
MySQL 如何保證原子性?
通過 undo log 來保證原子性的。ZL428資訊網——每日最新資訊28at.com
undo log 是一種用于撤銷回退的日志。在事務沒提交之前,MySQL 會先記錄更新前的數據到 undo log 日志文件里面,當事務回滾時,可以利用 undo log 來進行回滾。如下圖:ZL428資訊網——每日最新資訊28at.com
回滾事務ZL428資訊網——每日最新資訊28at.com
undo log 撤銷過程具體是怎么撤銷的?
每當 InnoDB 引擎對一條記錄進行操作(修改、刪除、新增)時,要把回滾時需要的信息都記錄到 undo log 里,比如:ZL428資訊網——每日最新資訊28at.com
- 在插入一條記錄時,要把這條記錄的主鍵值記下來,這樣之后回滾時只需要把這個主鍵值對應的記錄刪掉就好了;
- 在刪除一條記錄時,要把這條記錄中的內容都記下來,這樣之后回滾時再把由這些內容組成的記錄插入到表中就好了;
- 在更新一條記錄時,要把被更新的列的舊值記下來,這樣之后回滾時再把這些列更新為舊值就好了。
在發(fā)生回滾時,就讀取 undo log 里的數據,然后做原先相反操作。比如當 delete 一條記錄時,undo log 中會把記錄中的內容都記下來,然后執(zhí)行回滾操作的時候,就讀取 undo log 里的數據,然后進行 insert 操作。ZL428資訊網——每日最新資訊28at.com
怎么決定建立哪些索引?
什么時候適用索引?ZL428資訊網——每日最新資訊28at.com
- 字段有唯一性限制的,比如商品編碼;
- 經常用于 WHERE 查詢條件的字段,這樣能夠提高整個表的查詢速度,如果查詢條件不是一個字段,可以建立聯(lián)合索引。
- 經常用于 GROUP BY 和 ORDER BY 的字段,這樣在查詢的時候就不需要再去做一次排序了,因為我們都已經知道了建立索引之后在 B+Tree 中的記錄都是排序好的。
什么時候不需要創(chuàng)建索引?ZL428資訊網——每日最新資訊28at.com
- WHERE 條件,GROUP BY,ORDER BY 里用不到的字段,索引的價值是快速定位,如果起不到定位的字段通常是不需要創(chuàng)建索引的,因為索引是會占用物理空間的。
- 字段中存在大量重復數據,不需要創(chuàng)建索引,比如性別字段,只有男女,如果數據庫表中,男女的記錄分布均勻,那么無論搜索哪個值都可能得到一半的數據。在這些情況下,還不如不要索引,因為 MySQL 還有一個查詢優(yōu)化器,查詢優(yōu)化器發(fā)現(xiàn)某個值出現(xiàn)在表的數據行中的百分比很高的時候,它一般會忽略索引,進行全表掃描。
- 表數據太少的時候,不需要創(chuàng)建索引;
- 經常更新的字段不用創(chuàng)建索引,比如不要對電商項目的用戶余額建立索引,因為索引字段頻繁修改,由
最左匹配是什么,舉個例子?
使用聯(lián)合索引時,存在最左匹配原則,也就是按照最左優(yōu)先的方式進行索引的匹配。在使用聯(lián)合索引進行查詢的時候,如果不遵循「最左匹配原則」,聯(lián)合索引會失效,這樣就無法利用到索引快速查詢的特性了。ZL428資訊網——每日最新資訊28at.com
比如,如果創(chuàng)建了一個 (a, b, c) 聯(lián)合索引,如果查詢條件是以下這幾種,就可以匹配上聯(lián)合索引:ZL428資訊網——每日最新資訊28at.com
- where a=1;
- where a=1 and b=2 and c=3;
- where a=1 and b=2;
需要注意的是,因為有查詢優(yōu)化器,所以 a 字段在 where 子句的順序并不重要。ZL428資訊網——每日最新資訊28at.com
但是,如果查詢條件是以下這幾種,因為不符合最左匹配原則,所以就無法匹配上聯(lián)合索引,聯(lián)合索引就會失效:ZL428資訊網——每日最新資訊28at.com
- where b=2;
- where c=3;
- where b=2 and c=3;
上面這些查詢條件之所以會失效,是因為(a, b, c) 聯(lián)合索引,是先按 a 排序,在 a 相同的情況再按 b 排序,在 b 相同的情況再按 c 排序。所以,b 和 c 是全局無序,局部相對有序的,這樣在沒有遵循最左匹配原則的情況下,是無法利用到索引的。ZL428資訊網——每日最新資訊28at.com
我這里舉聯(lián)合索引(a,b)的例子,該聯(lián)合索引的 B+ Tree 如下(圖中葉子節(jié)點之間我畫了單向鏈表,但是實際上是雙向鏈表,原圖我找不到了,修改不了,偷個懶我不重畫了,大家腦補成雙向鏈表就行)。ZL428資訊網——每日最新資訊28at.com
ZL428資訊網——每日最新資訊28at.com
可以看到,a 是全局有序的(1, 2, 2, 3, 4, 5, 6, 7 ,8),而 b 是全局是無序的(12,7,8,2,3,8,10,5,2)。因此,直接執(zhí)行where b = 2這種查詢條件沒有辦法利用聯(lián)合索引的,利用索引的前提是索引里的 key 是有序的。ZL428資訊網——每日最新資訊28at.com
只有在 a 相同的情況才,b 才是有序的,比如 a 等于 2 的時候,b 的值為(7,8),這時就是有序的,這個有序狀態(tài)是局部的,因此,執(zhí)行where a = 2 and b = 7是 a 和 b 字段能用到聯(lián)合索引的,也就是聯(lián)合索引生效了。ZL428資訊網——每日最新資訊28at.com
Java
Java 里面線程有哪些狀態(tài)?
源自《Java并發(fā)編程藝術》ZL428資訊網——每日最新資訊28at.com
java.lang.Thread.State枚舉類中定義了六種線程的狀態(tài),可以調用線程Thread中的getState()方法獲取當前線程的狀態(tài)。ZL428資訊網——每日最新資訊28at.com
線程狀態(tài) ZL428資訊網——每日最新資訊28at.com | 解釋 ZL428資訊網——每日最新資訊28at.com |
NEW ZL428資訊網——每日最新資訊28at.com | 尚未啟動的線程狀態(tài),即線程創(chuàng)建,還未調用start方法ZL428資訊網——每日最新資訊28at.com |
RUNNABLE ZL428資訊網——每日最新資訊28at.com | 就緒狀態(tài)(調用start,等待調度)+正在運行ZL428資訊網——每日最新資訊28at.com |
BLOCKED ZL428資訊網——每日最新資訊28at.com | 等待監(jiān)視器鎖時,陷入阻塞狀態(tài)ZL428資訊網——每日最新資訊28at.com |
WAITING ZL428資訊網——每日最新資訊28at.com | 等待狀態(tài)的線程正在等待另一線程執(zhí)行特定的操作(如notify)ZL428資訊網——每日最新資訊28at.com |
TIMED_WAITING ZL428資訊網——每日最新資訊28at.com | 具有指定等待時間的等待狀態(tài)ZL428資訊網——每日最新資訊28at.com |
TERMINATED ZL428資訊網——每日最新資訊28at.com | 線程完成執(zhí)行,終止狀態(tài)ZL428資訊網——每日最新資訊28at.com |
wait 狀態(tài)下的線程如何進行恢復到 running 狀態(tài)?
- 等待的線程被其他線程對象喚醒,notify()和notifyAll()。
- 如果線程沒有獲取到鎖則會直接進入 Waiting 狀態(tài),其實這種本質上它就是執(zhí)行了 LockSupport.park() 方法進入了Waiting 狀態(tài),那么解鎖的時候會執(zhí)行LockSupport.unpark(Thread),與上面park方法對應,給出許可證,解除等待狀態(tài)。
notify 和 notifyAll 的區(qū)別?
同樣是喚醒等待的線程,同樣最多只有一個線程能獲得鎖,同樣不能控制哪個線程獲得鎖。ZL428資訊網——每日最新資訊28at.com
區(qū)別在于:ZL428資訊網——每日最新資訊28at.com
- notify:喚醒一個線程,其他線程依然處于wait的等待喚醒狀態(tài),如果被喚醒的線程結束時沒調用notify,其他線程就永遠沒人去喚醒,只能等待超時,或者被中斷
- notifyAll:所有線程退出wait的狀態(tài),開始競爭鎖,但只有一個線程能搶到,這個線程執(zhí)行完后,其他線程又會有一個幸運兒脫穎而出得到鎖
notify 選擇哪個線程?
notify在源碼的注釋中說到notify選擇喚醒的線程是任意的,但是依賴于具體實現(xiàn)的jvm。ZL428資訊網——每日最新資訊28at.com
圖片ZL428資訊網——每日最新資訊28at.com
notify源碼ZL428資訊網——每日最新資訊28at.com
JVM有很多實現(xiàn),比較流行的就是hotspot,hotspot對notofy()的實現(xiàn)并不是我們以為的隨機喚醒,,而是“先進先出”的順序喚醒。ZL428資訊網——每日最新資訊28at.com
如何停止一個線程的運行?
主要有這些方法:ZL428資訊網——每日最新資訊28at.com
- 異常法停止:線程調用interrupt()方法后,在線程的run方法中判斷當前對象的interrupted()狀態(tài),如果是中斷狀態(tài)則拋出異常,達到中斷線程的效果。
- 在沉睡中停止:先將線程sleep,然后調用interrupt標記中斷狀態(tài),interrupt會將阻塞狀態(tài)的線程中斷。會拋出中斷異常,達到停止線程的效果
- stop()暴力停止:線程調用stop()方法會被暴力停止,方法已棄用,該方法會有不好的后果:強制讓線程停止有可能使一些請理性的工作得不到完成。
- 使用return停止線程:調用interrupt標記為中斷狀態(tài)后,在run方法中判斷當前線程狀態(tài),如果為中斷狀態(tài)則return,能達到停止線程的效果。
調用 interrupt 是如何讓線程拋出異常的?
每個線程都一個與之關聯(lián)的布爾屬性來表示其中斷狀態(tài),中斷狀態(tài)的初始值為false,當一個線程被其它線程調用Thread.interrupt()方法中斷時,會根據實際情況做出響應。ZL428資訊網——每日最新資訊28at.com
- 如果該線程正在執(zhí)行低級別的可中斷方法(如Thread.sleep()、Thread.join()或Object.wait()),則會解除阻塞并拋出InterruptedException異常。
- 否則Thread.interrupt()僅設置線程的中斷狀態(tài),在該被中斷的線程中稍后可通過輪詢中斷狀態(tài)來決定是否要停止當前正在執(zhí)行的任務。
如果是靠變量來停止線程,缺點是什么?
缺點是中斷可能不夠及時,循環(huán)判斷時會到下一個循環(huán)才能判斷出來。ZL428資訊網——每日最新資訊28at.com
class InterruptFlag { // 自定義的中斷標識符 private static volatile boolean isInterrupt = false; public static void main(String[] args) throws InterruptedException { // 創(chuàng)建可中斷的線程實例 Thread thread = new Thread(() -> { while (!isInterrupt) { // 如果 isInterrupt=true 則停止線程 System.out.println("thread 執(zhí)行步驟1:線程即將進入休眠狀態(tài)"); try { // 休眠 1s Thread.sleep(1000); } catch (InterruptedException e) { e.printStackTrace(); } System.out.println("thread 執(zhí)行步驟2:線程執(zhí)行了任務"); } }); thread.start(); // 啟動線程 // 休眠 100ms,等待 thread 線程運行起來 Thread.sleep(100); System.out.println("主線程:試圖終止線程 thread"); // 修改中斷標識符,中斷線程 isInterrupt = true; }}
當終止線程后,執(zhí)行步驟2依然會被執(zhí)行,這就是缺點。ZL428資訊網——每日最新資訊28at.com
volatile 保證原子性嗎?
volatile關鍵字并沒有保證我們的變量的原子性,volatile是Java虛擬機提供的一種輕量級的同步機制,主要有這三個特性:ZL428資訊網——每日最新資訊28at.com
那我們要如何保證原子性?
可以通過synchronized來保證原子性。ZL428資訊網——每日最新資訊28at.com
synchronized 支持重入嗎?如何實現(xiàn)的?
synchronized是基于原子性的內部鎖機制,是可重入的,因此在一個線程調用synchronized方法的同時在其方法體內部調用該對象另一個synchronized方法,也就是說一個線程得到一個對象鎖后再次請求該對象鎖,是允許的,這就是synchronized的可重入性。ZL428資訊網——每日最新資訊28at.com
synchronized底層是利用計算機系統(tǒng)mutex Lock實現(xiàn)的。每一個可重入鎖都會關聯(lián)一個線程ID和一個鎖狀態(tài)status。ZL428資訊網——每日最新資訊28at.com
當一個線程請求方法時,會去檢查鎖狀態(tài)。ZL428資訊網——每日最新資訊28at.com
- 如果鎖狀態(tài)是0,代表該鎖沒有被占用,使用CAS操作獲取鎖,將線程ID替換成自己的線程ID。
- 如果鎖狀態(tài)不是0,代表有線程在訪問該方法。此時,如果線程ID是自己的線程ID,如果是可重入鎖,會將status自增1,然后獲取到該鎖,進而執(zhí)行相應的方法;如果是非重入鎖,就會進入阻塞隊列等待。
在釋放鎖時,ZL428資訊網——每日最新資訊28at.com
- 如果是可重入鎖的,每一次退出方法,就會將status減1,直至status的值為0,最后釋放該鎖。
- 如果非可重入鎖的,線程退出方法,直接就會釋放該鎖。
網絡
HTTP 與 HTTPS 協(xié)議的區(qū)別?
HTTP 與 HTTPS 網絡層ZL428資訊網——每日最新資訊28at.com
- HTTP 是超文本傳輸協(xié)議,信息是明文傳輸,存在安全風險的問題。HTTPS 則解決 HTTP 不安全的缺陷,在 TCP 和 HTTP 網絡層之間加入了 SSL/TLS 安全協(xié)議,使得報文能夠加密傳輸。
- HTTP 連接建立相對簡單, TCP 三次握手之后便可進行 HTTP 的報文傳輸。而 HTTPS 在 TCP 三次握手之后,還需進行 SSL/TLS 的握手過程,才可進入加密報文傳輸。
- 兩者的默認端口不一樣,HTTP 默認端口號是 80,HTTPS 默認端口號是 443。
- HTTPS 協(xié)議需要向 CA(證書權威機構)申請數字證書,來保證服務器的身份是可信的。
操作系統(tǒng)
有哪些進程調度算法 ?
01 先來先服務調度算法ZL428資訊網——每日最新資訊28at.com
最簡單的一個調度算法,就是非搶占式的先來先服務(*First Come First Serve, FCFS*)算法了。ZL428資訊網——每日最新資訊28at.com
FCFS 調度算法ZL428資訊網——每日最新資訊28at.com
顧名思義,先來后到,每次從就緒隊列選擇最先進入隊列的進程,然后一直運行,直到進程退出或被阻塞,才會繼續(xù)從隊列中選擇第一個進程接著運行。ZL428資訊網——每日最新資訊28at.com
這似乎很公平,但是當一個長作業(yè)先運行了,那么后面的短作業(yè)等待的時間就會很長,不利于短作業(yè)。ZL428資訊網——每日最新資訊28at.com
FCFS 對長作業(yè)有利,適用于 CPU 繁忙型作業(yè)的系統(tǒng),而不適用于 I/O 繁忙型作業(yè)的系統(tǒng)。ZL428資訊網——每日最新資訊28at.com
02 最短作業(yè)優(yōu)先調度算法ZL428資訊網——每日最新資訊28at.com
最短作業(yè)優(yōu)先(*Shortest Job First, SJF*)調度算法同樣也是顧名思義,它會優(yōu)先選擇運行時間最短的進程來運行,這有助于提高系統(tǒng)的吞吐量。ZL428資訊網——每日最新資訊28at.com
SJF 調度算法ZL428資訊網——每日最新資訊28at.com
這顯然對長作業(yè)不利,很容易造成一種極端現(xiàn)象。ZL428資訊網——每日最新資訊28at.com
比如,一個長作業(yè)在就緒隊列等待運行,而這個就緒隊列有非常多的短作業(yè),那么就會使得長作業(yè)不斷的往后推,周轉時間變長,致使長作業(yè)長期不會被運行。ZL428資訊網——每日最新資訊28at.com
03 高響應比優(yōu)先調度算法ZL428資訊網——每日最新資訊28at.com
前面的「先來先服務調度算法」和「最短作業(yè)優(yōu)先調度算法」都沒有很好的權衡短作業(yè)和長作業(yè)。ZL428資訊網——每日最新資訊28at.com
那么,高響應比優(yōu)先 (*Highest Response Ratio Next, HRRN*)調度算法主要是權衡了短作業(yè)和長作業(yè)。ZL428資訊網——每日最新資訊28at.com
每次進行進程調度時,先計算「響應比優(yōu)先級」,然后把「響應比優(yōu)先級」最高的進程投入運行,「響應比優(yōu)先級」的計算公式:ZL428資訊網——每日最新資訊28at.com
圖片ZL428資訊網——每日最新資訊28at.com
從上面的公式,可以發(fā)現(xiàn):ZL428資訊網——每日最新資訊28at.com
- 如果兩個進程的「等待時間」相同時,「要求的服務時間」越短,「響應比」就越高,這樣短作業(yè)的進程容易被選中運行;
- 如果兩個進程「要求的服務時間」相同時,「等待時間」越長,「響應比」就越高,這就兼顧到了長作業(yè)進程,因為進程的響應比可以隨時間等待的增加而提高,當其等待時間足夠長時,其響應比便可以升到很高,從而獲得運行的機會;
04 時間片輪轉調度算法ZL428資訊網——每日最新資訊28at.com
最古老、最簡單、最公平且使用最廣的算法就是時間片輪轉(*Round Robin, RR*)調度算法。ZL428資訊網——每日最新資訊28at.com
RR 調度算法ZL428資訊網——每日最新資訊28at.com
每個進程被分配一個時間段,稱為時間片(*Quantum*),即允許該進程在該時間段中運行。ZL428資訊網——每日最新資訊28at.com
- 如果時間片用完,進程還在運行,那么將會把此進程從 CPU 釋放出來,并把 CPU 分配給另外一個進程;
- 如果該進程在時間片結束前阻塞或結束,則 CPU 立即進行切換;
另外,時間片的長度就是一個很關鍵的點:ZL428資訊網——每日最新資訊28at.com
- 如果時間片設得太短會導致過多的進程上下文切換,降低了 CPU 效率;
- 如果設得太長又可能引起對短作業(yè)進程的響應時間變長。將
一般來說,時間片設為 20ms~50ms 通常是一個比較合理的折中值。ZL428資訊網——每日最新資訊28at.com
05 最高優(yōu)先級調度算法ZL428資訊網——每日最新資訊28at.com
前面的「時間片輪轉算法」做了個假設,即讓所有的進程同等重要,也不偏袒誰,大家的運行時間都一樣。ZL428資訊網——每日最新資訊28at.com
但是,對于多用戶計算機系統(tǒng)就有不同的看法了,它們希望調度是有優(yōu)先級的,即希望調度程序能從就緒隊列中選擇最高優(yōu)先級的進程進行運行,這稱為最高優(yōu)先級(*Highest Priority First,HPF*)調度算法。ZL428資訊網——每日最新資訊28at.com
進程的優(yōu)先級可以分為,靜態(tài)優(yōu)先級和動態(tài)優(yōu)先級:ZL428資訊網——每日最新資訊28at.com
- 靜態(tài)優(yōu)先級:創(chuàng)建進程時候,就已經確定了優(yōu)先級了,然后整個運行時間優(yōu)先級都不會變化;
- 動態(tài)優(yōu)先級:根據進程的動態(tài)變化調整優(yōu)先級,比如如果進程運行時間增加,則降低其優(yōu)先級,如果進程等待時間(就緒隊列的等待時間)增加,則升高其優(yōu)先級,也就是隨著時間的推移增加等待進程的優(yōu)先級。
該算法也有兩種處理優(yōu)先級高的方法,非搶占式和搶占式:ZL428資訊網——每日最新資訊28at.com
- 非搶占式:當就緒隊列中出現(xiàn)優(yōu)先級高的進程,運行完當前進程,再選擇優(yōu)先級高的進程。
- 搶占式:當就緒隊列中出現(xiàn)優(yōu)先級高的進程,當前進程掛起,調度優(yōu)先級高的進程運行。
但是依然有缺點,可能會導致低優(yōu)先級的進程永遠不會運行。ZL428資訊網——每日最新資訊28at.com
06 多級反饋隊列調度算法ZL428資訊網——每日最新資訊28at.com
多級反饋隊列(*Multilevel Feedback Queue*)調度算法是「時間片輪轉算法」和「最高優(yōu)先級算法」的綜合和發(fā)展。ZL428資訊網——每日最新資訊28at.com
顧名思義:ZL428資訊網——每日最新資訊28at.com
- 「多級」表示有多個隊列,每個隊列優(yōu)先級從高到低,同時優(yōu)先級越高時間片越短。
- 「反饋」表示如果有新的進程加入優(yōu)先級高的隊列時,立刻停止當前正在運行的進程,轉而去運行優(yōu)先級高的隊列;
多級反饋隊列ZL428資訊網——每日最新資訊28at.com
來看看,它是如何工作的:ZL428資訊網——每日最新資訊28at.com
- 設置了多個隊列,賦予每個隊列不同的優(yōu)先級,每個隊列優(yōu)先級從高到低,同時優(yōu)先級越高時間片越短;
- 新的進程會被放入到第一級隊列的末尾,按先來先服務的原則排隊等待被調度,如果在第一級隊列規(guī)定的時間片沒運行完成,則將其轉入到第二級隊列的末尾,以此類推,直至完成;
- 當較高優(yōu)先級的隊列為空,才調度較低優(yōu)先級的隊列中的進程運行。如果進程運行時,有新進程進入較高優(yōu)先級的隊列,則停止當前運行的進程并將其移入到原隊列末尾,接著讓較高優(yōu)先級的進程運行;
可以發(fā)現(xiàn),對于短作業(yè)可能可以在第一級隊列很快被處理完。對于長作業(yè),如果在第一級隊列處理不完,可以移入下次隊列等待被執(zhí)行,雖然等待的時間變長了,但是運行時間也變更長了,所以該算法很好的兼顧了長短作業(yè),同時有較好的響應時間。ZL428資訊網——每日最新資訊28at.com
算法
- 給定鏈表 1 -> 2 -> ... -> n-1 -> n,使用 O(1) 空間復雜度使其變?yōu)?1 -> n -> 2 -> n-1 -> ...
- 只記得有關滑動窗口,應該是力扣 TOP 100 的
本文鏈接:http://www.www897cc.com/showinfo-26-60957-0.html終究還是拿下字節(jié)!強度拉滿!
聲明:本網頁內容旨在傳播知識,若有侵權等問題請及時與本網聯(lián)系,我們將在第一時間刪除處理。郵件:2376512515@qq.com
上一篇: 基于Doris ,打造快速、安全、高可靠的實時數據倉庫
下一篇: 接手了個項目,被if..else搞懵逼了