大家好，我是小林。

騰訊面試風格是比較注重計算機基礎(chǔ)的，操作系統(tǒng)和網(wǎng)絡都會問的比較多，所以大家針對不同公司面試的時候，要有一個準備的側(cè)重點。

今天分析一位同學騰訊校招后端開發(fā)面經(jīng)，足足面了 2 個小時，1 小時手撕算法，1 小時基礎(chǔ)拷打，最累一場面試，雖然面的很累，但是同學反饋面試官人很好，會一直引導。

這次面經(jīng)的考點，我簡單羅列一下：

• Java：HashMap、垃圾回收算法、線程模型
• 操作系統(tǒng)：用戶態(tài)與內(nèi)核態(tài)、進程調(diào)度、進程間通信、虛擬內(nèi)存、進程&線程&協(xié)程
• 網(wǎng)絡：TCP三次握手、擁塞控制、https
• Redis：5 種數(shù)據(jù)結(jié)構(gòu)
• MySQL：b+樹
• 算法：4 個算法題

Java

Java里面的線程和操作系統(tǒng)的線程一樣嗎？

Java 底層會調(diào)用 pthread_create 來創(chuàng)建線程，所以本質(zhì)上 java 程序創(chuàng)建的線程，就是和操作系統(tǒng)線程是一樣的，是 1 對 1 的線程模型。

圖片

HashMap的底層原理？

圖片

存儲對象時，我們將K/V傳給put方法時，它調(diào)用hashCode計算hash從而得到bucket位置，進一步存儲，HashMap會根據(jù)當前bucket的占用情況自動調(diào)整容量(超過Load Facotr則resize為原來的2倍)。

獲取對象時，我們將K傳給get，它調(diào)用hashCode計算hash從而得到bucket位置，并進一步調(diào)用equals()方法確定鍵值對。如果發(fā)生碰撞的時候，Hashmap通過鏈表將產(chǎn)生碰撞沖突的元素組織起來，在Java 8中，如果一個bucket中碰撞沖突的元素超過某個限制(默認是8)，則使用紅黑樹來替換鏈表，從而提高速度。

如何判斷一個對象是無用對象？

判斷一個對象是否為無用對象（即不再被引用，并且可以被垃圾回收器回收）通常依賴于垃圾回收器的工作。Java的垃圾回收器使用了可達性分析算法來確定對象是否可達，如果一個對象不可達，則可以被判定為無用對象。

具體判斷一個對象是否為無用對象的方式如下：

1. 引用計數(shù)法（Reference Counting）：該方法通過在對象中維護一個引用計數(shù)器，每當有一個引用指向該對象時，計數(shù)器加1，當引用指向該對象的引用被釋放時，計數(shù)器減1。當計數(shù)器為0時，可以判定該對象為無用對象。然而，Java的垃圾回收器并不使用引用計數(shù)法，因為它無法解決循環(huán)引用的問題。
2. 可達性分析法（Reachability Analysis）：Java的垃圾回收器主要使用可達性分析法來判斷對象的可達性。該方法從一組稱為"GC Roots"的根對象開始，通過遍歷對象圖，標記所有從根對象可達的對象。那些未被標記的對象則被判定為無用對象。

假設HashMap里面存放100萬個對象，那么gc可能會有什么問題？

對象太多，使用可達性分析法去掃描這些無用對象的時候花費的時間比較長，gc花費的時間就會變長。

操作系統(tǒng)

用戶態(tài)和內(nèi)核態(tài)有什么區(qū)別？

用戶態(tài)（User Mode）和內(nèi)核態(tài)（Kernel Mode）是操作系統(tǒng)中的兩種特權(quán)級別，它們有以下幾個區(qū)別：

1. 訪問權(quán)限：在用戶態(tài)下，應用程序只能訪問受限的資源和執(zhí)行受限的操作，例如用戶空間的內(nèi)存、文件和設備。而在內(nèi)核態(tài)下，操作系統(tǒng)具有完全的訪問權(quán)限，可以訪問系統(tǒng)的所有資源和執(zhí)行所有操作。
2. CPU指令集：在用戶態(tài)下，CPU只能執(zhí)行非特權(quán)指令，例如算術(shù)運算、邏輯運算等。而在內(nèi)核態(tài)下，CPU可以執(zhí)行特權(quán)指令，例如訪問設備、修改系統(tǒng)狀態(tài)等。
3. 中斷和異常處理：在用戶態(tài)下，當發(fā)生中斷或異常時，操作系統(tǒng)會進行中斷處理，將控制權(quán)轉(zhuǎn)移到內(nèi)核態(tài)下的中斷處理程序中。而在內(nèi)核態(tài)下，操作系統(tǒng)可以直接處理中斷和異常，并進行相應的處理操作。
4. 內(nèi)存保護：在用戶態(tài)下，應用程序只能訪問自己的內(nèi)存空間，無法訪問其他應用程序的內(nèi)存空間和操作系統(tǒng)的內(nèi)存空間。而在內(nèi)核態(tài)下，操作系統(tǒng)可以訪問所有的內(nèi)存空間，包括應用程序的內(nèi)存空間。
5. 安全性：由于用戶態(tài)的應用程序受到限制，操作系統(tǒng)可以對其進行隔離和保護，防止惡意代碼對系統(tǒng)造成損害。而內(nèi)核態(tài)下的操作系統(tǒng)具有更高的權(quán)限，需要對其進行嚴格的安全管理，以防止非法訪問和惡意操作。

進程調(diào)度算法說一下

01 先來先服務調(diào)度算法

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

FCFS 調(diào)度算法

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

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

FCFS 對長作業(yè)有利，適用于 CPU 繁忙型作業(yè)的系統(tǒng)，而不適用于 I/O 繁忙型作業(yè)的系統(tǒng)。

02 最短作業(yè)優(yōu)先調(diào)度算法

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

SJF 調(diào)度算法

這顯然對長作業(yè)不利，很容易造成一種極端現(xiàn)象。

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

03 高響應比優(yōu)先調(diào)度算法

前面的「先來先服務調(diào)度算法」和「最短作業(yè)優(yōu)先調(diào)度算法」都沒有很好的權(quán)衡短作業(yè)和長作業(yè)。

那么，高響應比優(yōu)先 （*Highest Response Ratio Next, HRRN*）調(diào)度算法主要是權(quán)衡了短作業(yè)和長作業(yè)。

每次進行進程調(diào)度時，先計算「響應比優(yōu)先級」，然后把「響應比優(yōu)先級」最高的進程投入運行，「響應比優(yōu)先級」的計算公式：

圖片

從上面的公式，可以發(fā)現(xiàn)：

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

04 時間片輪轉(zhuǎn)調(diào)度算法

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

RR 調(diào)度算法

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

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

另外，時間片的長度就是一個很關(guān)鍵的點：

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

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

05 最高優(yōu)先級調(diào)度算法

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

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

進程的優(yōu)先級可以分為，靜態(tài)優(yōu)先級和動態(tài)優(yōu)先級：

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

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

• 非搶占式：當就緒隊列中出現(xiàn)優(yōu)先級高的進程，運行完當前進程，再選擇優(yōu)先級高的進程。
• 搶占式：當就緒隊列中出現(xiàn)優(yōu)先級高的進程，當前進程掛起，調(diào)度優(yōu)先級高的進程運行。

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

06 多級反饋隊列調(diào)度算法

多級反饋隊列（*Multilevel Feedback Queue*）調(diào)度算法是「時間片輪轉(zhuǎn)算法」和「最高優(yōu)先級算法」的綜合和發(fā)展。

顧名思義：

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

多級反饋隊列

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

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

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

進程間的通信機制？

圖片

由于每個進程的用戶空間都是獨立的，不能相互訪問，這時就需要借助內(nèi)核空間來實現(xiàn)進程間通信，原因很簡單，每個進程都是共享一個內(nèi)核空間。

Linux 內(nèi)核提供了不少進程間通信的方式，其中最簡單的方式就是管道，管道分為「匿名管道」和「命名管道」。

匿名管道顧名思義，它沒有名字標識，匿名管道是特殊文件只存在于內(nèi)存，沒有存在于文件系統(tǒng)中，shell 命令中的「|」豎線就是匿名管道，通信的數(shù)據(jù)是無格式的流并且大小受限，通信的方式是單向的，數(shù)據(jù)只能在一個方向上流動，如果要雙向通信，需要創(chuàng)建兩個管道，再來匿名管道是只能用于存在父子關(guān)系的進程間通信，匿名管道的生命周期隨著進程創(chuàng)建而建立，隨著進程終止而消失。

命名管道突破了匿名管道只能在親緣關(guān)系進程間的通信限制，因為使用命名管道的前提，需要在文件系統(tǒng)創(chuàng)建一個類型為 p 的設備文件，那么毫無關(guān)系的進程就可以通過這個設備文件進行通信。另外，不管是匿名管道還是命名管道，進程寫入的數(shù)據(jù)都是緩存在內(nèi)核中，另一個進程讀取數(shù)據(jù)時候自然也是從內(nèi)核中獲取，同時通信數(shù)據(jù)都遵循先進先出原則，不支持 lseek 之類的文件定位操作。

消息隊列克服了管道通信的數(shù)據(jù)是無格式的字節(jié)流的問題，消息隊列實際上是保存在內(nèi)核的「消息鏈表」，消息隊列的消息體是可以用戶自定義的數(shù)據(jù)類型，發(fā)送數(shù)據(jù)時，會被分成一個一個獨立的消息體，當然接收數(shù)據(jù)時，也要與發(fā)送方發(fā)送的消息體的數(shù)據(jù)類型保持一致，這樣才能保證讀取的數(shù)據(jù)是正確的。消息隊列通信的速度不是最及時的，畢竟每次數(shù)據(jù)的寫入和讀取都需要經(jīng)過用戶態(tài)與內(nèi)核態(tài)之間的拷貝過程。

共享內(nèi)存可以解決消息隊列通信中用戶態(tài)與內(nèi)核態(tài)之間數(shù)據(jù)拷貝過程帶來的開銷，它直接分配一個共享空間，每個進程都可以直接訪問，就像訪問進程自己的空間一樣快捷方便，不需要陷入內(nèi)核態(tài)或者系統(tǒng)調(diào)用，大大提高了通信的速度，享有最快的進程間通信方式之名。但是便捷高效的共享內(nèi)存通信，帶來新的問題，多進程競爭同個共享資源會造成數(shù)據(jù)的錯亂。

那么，就需要信號量來保護共享資源，以確保任何時刻只能有一個進程訪問共享資源，這種方式就是互斥訪問。信號量不僅可以實現(xiàn)訪問的互斥性，還可以實現(xiàn)進程間的同步，信號量其實是一個計數(shù)器，表示的是資源個數(shù)，其值可以通過兩個原子操作來控制，分別是 P 操作和 V 操作。

與信號量名字很相似的叫信號，它倆名字雖然相似，但功能一點兒都不一樣。信號是異步通信機制，信號可以在應用進程和內(nèi)核之間直接交互，內(nèi)核也可以利用信號來通知用戶空間的進程發(fā)生了哪些系統(tǒng)事件，信號事件的來源主要有硬件來源（如鍵盤 Cltr+C ）和軟件來源（如 kill 命令），一旦有信號發(fā)生，進程有三種方式響應信號 1. 執(zhí)行默認操作、2. 捕捉信號、3. 忽略信號。有兩個信號是應用進程無法捕捉和忽略的，即 SIGKILL 和 SIGSTOP，這是為了方便我們能在任何時候結(jié)束或停止某個進程。

前面說到的通信機制，都是工作于同一臺主機，如果要與不同主機的進程間通信，那么就需要 Socket 通信了。Socket 實際上不僅用于不同的主機進程間通信，還可以用于本地主機進程間通信，可根據(jù)創(chuàng)建 Socket 的類型不同，分為三種常見的通信方式，一個是基于 TCP 協(xié)議的通信方式，一個是基于 UDP 協(xié)議的通信方式，一個是本地進程間通信方式。

IO多路復用，select、poll、epoll 的區(qū)別？

select 實現(xiàn)多路復用的方式是，將已連接的 Socket 都放到一個文件描述符集合，然后調(diào)用 select 函數(shù)將文件描述符集合拷貝到內(nèi)核里，讓內(nèi)核來檢查是否有網(wǎng)絡事件產(chǎn)生，檢查的方式很粗暴，就是通過遍歷文件描述符集合的方式，當檢查到有事件產(chǎn)生后，將此 Socket 標記為可讀或可寫， 接著再把整個文件描述符集合拷貝回用戶態(tài)里，然后用戶態(tài)還需要再通過遍歷的方法找到可讀或可寫的 Socket，然后再對其處理。

所以，對于 select 這種方式，需要進行 2 次「遍歷」文件描述符集合，一次是在內(nèi)核態(tài)里，一個次是在用戶態(tài)里 ，而且還會發(fā)生 2 次「拷貝」文件描述符集合，先從用戶空間傳入內(nèi)核空間，由內(nèi)核修改后，再傳出到用戶空間中。

select 使用固定長度的 BitsMap，表示文件描述符集合，而且所支持的文件描述符的個數(shù)是有限制的，在 Linux 系統(tǒng)中，由內(nèi)核中的 FD_SETSIZE 限制， 默認最大值為 1024，只能監(jiān)聽 0~1023 的文件描述符。

poll 不再用 BitsMap 來存儲所關(guān)注的文件描述符，取而代之用動態(tài)數(shù)組，以鏈表形式來組織，突破了 select 的文件描述符個數(shù)限制，當然還會受到系統(tǒng)文件描述符限制。

但是 poll 和 select 并沒有太大的本質(zhì)區(qū)別，都是使用「線性結(jié)構(gòu)」存儲進程關(guān)注的 Socket 集合，因此都需要遍歷文件描述符集合來找到可讀或可寫的 Socket，時間復雜度為 O(n)，而且也需要在用戶態(tài)與內(nèi)核態(tài)之間拷貝文件描述符集合，這種方式隨著并發(fā)數(shù)上來，性能的損耗會呈指數(shù)級增長。

epoll 通過兩個方面，很好解決了 select/poll 的問題。

• 第一點，epoll 在內(nèi)核里使用紅黑樹來跟蹤進程所有待檢測的文件描述字，把需要監(jiān)控的 socket 通過 epoll_ctl() 函數(shù)加入內(nèi)核中的紅黑樹里，紅黑樹是個高效的數(shù)據(jù)結(jié)構(gòu)，增刪改一般時間復雜度是 O(logn)。而 select/poll 內(nèi)核里沒有類似 epoll 紅黑樹這種保存所有待檢測的 socket 的數(shù)據(jù)結(jié)構(gòu)，所以 select/poll 每次操作時都傳入整個 socket 集合給內(nèi)核，而 epoll 因為在內(nèi)核維護了紅黑樹，可以保存所有待檢測的 socket ，所以只需要傳入一個待檢測的 socket，減少了內(nèi)核和用戶空間大量的數(shù)據(jù)拷貝和內(nèi)存分配。
• 第二點， epoll 使用事件驅(qū)動的機制，內(nèi)核里維護了一個鏈表來記錄就緒事件，當某個 socket 有事件發(fā)生時，通過回調(diào)函數(shù)內(nèi)核會將其加入到這個就緒事件列表中，當用戶調(diào)用 epoll_wait() 函數(shù)時，只會返回有事件發(fā)生的文件描述符的個數(shù)，不需要像 select/poll 那樣輪詢掃描整個 socket 集合，大大提高了檢測的效率。

從下圖你可以看到 epoll 相關(guān)的接口作用：

圖片

epoll 的方式即使監(jiān)聽的 Socket 數(shù)量越多的時候，效率不會大幅度降低，能夠同時監(jiān)聽的 Socket 的數(shù)目也非常的多了，上限就為系統(tǒng)定義的進程打開的最大文件描述符個數(shù)。因而，epoll 被稱為解決 C10K 問題的利器。

為什么操作系統(tǒng)要設計虛擬內(nèi)存？

如果沒有虛擬內(nèi)存，程序直接操作物理內(nèi)存的話。

圖片

在這種情況下，要想在內(nèi)存中同時運行兩個程序是不可能的。如果第一個程序在 2000 的位置寫入一個新的值，將會擦掉第二個程序存放在相同位置上的所有內(nèi)容，所以同時運行兩個程序是根本行不通的，這兩個程序會立刻崩潰。

這里關(guān)鍵的問題是這兩個程序都引用了絕對物理地址，而這正是我們最需要避免的。

進程的中間層

我們可以把進程所使用的地址「隔離」開來，即讓操作系統(tǒng)為每個進程分配獨立的一套「虛擬地址」，人人都有，大家自己玩自己的地址就行，互不干涉。但是有個前提每個進程都不能訪問物理地址，至于虛擬地址最終怎么落到物理內(nèi)存里，對進程來說是透明的，操作系統(tǒng)已經(jīng)把這些都安排的明明白白了。

操作系統(tǒng)會提供一種機制，將不同進程的虛擬地址和不同內(nèi)存的物理地址映射起來。如果程序要訪問虛擬地址的時候，由操作系統(tǒng)轉(zhuǎn)換成不同的物理地址，這樣不同的進程運行的時候，寫入的是不同的物理地址，這樣就不會沖突了。

進程和線程的區(qū)別？

• 資源分配：進程是操作系統(tǒng)中的一個執(zhí)行實體，擁有獨立的地址空間、文件描述符、打開的文件等資源。每個進程都被分配了獨立的系統(tǒng)資源。而線程是進程中的一個執(zhí)行單元，多個線程共享同一個進程的地址空間和其他資源，包括文件描述符、打開的文件等。
• 調(diào)度和切換：進程的調(diào)度是由操作系統(tǒng)內(nèi)核進行的，切換進程需要進行上下文切換，涉及用戶態(tài)和內(nèi)核態(tài)之間的切換，開銷相對較大。而線程的調(diào)度是在用戶程序中完成，切換線程可以在用戶態(tài)下快速切換，減少了系統(tǒng)調(diào)用的開銷。
• 并發(fā)性：進程是獨立的執(zhí)行實體，不同進程之間通過進程間通信（IPC）來進行數(shù)據(jù)交換和共享。進程間通信的方式包括管道、信號量、共享內(nèi)存等。而線程是在同一個進程中執(zhí)行的，多個線程之間共享同一進程的資源，可以通過共享內(nèi)存的方式進行數(shù)據(jù)交換和共享。

進程的地址空間里面有什么？

虛擬內(nèi)存空間劃分

通過這張圖你可以看到，用戶空間內(nèi)存，從低到高分別是 6 種不同的內(nèi)存段：

• 代碼段，包括二進制可執(zhí)行代碼；
• 數(shù)據(jù)段，包括已初始化的靜態(tài)常量和全局變量；
• BSS 段，包括未初始化的靜態(tài)變量和全局變量；
• 堆段，包括動態(tài)分配的內(nèi)存，從低地址開始向上增長；
• 文件映射段，包括動態(tài)庫、共享內(nèi)存等；
• 棧段，包括局部變量和函數(shù)調(diào)用的上下文等。棧的大小是固定的，一般是 8 MB。當然系統(tǒng)也提供了參數(shù)，以便我們自定義大小；

上圖中的內(nèi)存布局可以看到，代碼段下面還有一段內(nèi)存空間的（灰色部分），這一塊區(qū)域是「保留區(qū)」，之所以要有保留區(qū)這是因為在大多數(shù)的系統(tǒng)里，我們認為比較小數(shù)值的地址不是一個合法地址，例如，我們通常在 C 的代碼里會將無效的指針賦值為 NULL。因此，這里會出現(xiàn)一段不可訪問的內(nèi)存保留區(qū)，防止程序因為出現(xiàn) bug，導致讀或?qū)懥艘恍┬?nèi)存地址的數(shù)據(jù)，而使得程序跑飛。

在這 7 個內(nèi)存段中，堆和文件映射段的內(nèi)存是動態(tài)分配的。比如說，使用 C 標準庫的 malloc() 或者 mmap() ，就可以分別在堆和文件映射段動態(tài)分配內(nèi)存。

線程切換要保存哪些上下文？

• 寄存器上下文：線程切換時需要保存和恢復線程所使用的寄存器的值，以便切換后能夠繼續(xù)執(zhí)行。常見的寄存器包括通用寄存器（如EAX、EBX、ECX等）、指令指針寄存器（如EIP）、堆棧指針寄存器（如ESP）等。
• 棧：線程的棧用于保存局部變量、函數(shù)調(diào)用信息等。在線程切換時，需要保存和恢復當前線程的棧指針，以及相應的棧幀信息。
• 線程上下文信息：線程切換時，需要保存和恢復與線程相關(guān)的其他上下文信息，如線程狀態(tài)、調(diào)度優(yōu)先級等。

協(xié)程和線程什么區(qū)別？

• 調(diào)度方式：線程的調(diào)度是由操作系統(tǒng)內(nèi)核進行的，而協(xié)程的調(diào)度是由程序員或者特定的協(xié)程調(diào)度器進行的。線程的調(diào)度是由操作系統(tǒng)內(nèi)核控制，切換線程需要進行系統(tǒng)調(diào)用，涉及用戶態(tài)和內(nèi)核態(tài)之間的切換，相對較為耗時。而協(xié)程的調(diào)度是在用戶程序中完成，切換協(xié)程可以在用戶態(tài)下快速切換，減少了系統(tǒng)調(diào)用的開銷。
• 并發(fā)性：線程是操作系統(tǒng)提供的輕量級進程，多個線程之間可以并發(fā)執(zhí)行，但在多核處理器上，線程的并發(fā)性是通過操作系統(tǒng)的線程調(diào)度實現(xiàn)的。而協(xié)程是在單個線程中執(zhí)行的，多個協(xié)程之間通過協(xié)程調(diào)度器進行切換，實現(xiàn)了更細粒度的并發(fā)性。
• 內(nèi)存消耗：線程的創(chuàng)建和銷毀需要操作系統(tǒng)進行一系列的資源分配和回收，包括線程的?？臻g和線程控制塊等。而協(xié)程在單個線程中執(zhí)行，不需要額外的系統(tǒng)資源分配，只需要協(xié)程調(diào)度器保存和恢復協(xié)程的上下文。
• 同步方式：線程之間的通信和同步需要使用鎖、條件變量等機制來進行，這些機制需要進行加鎖和解鎖的操作，容易引發(fā)死鎖和競態(tài)條件等問題。而協(xié)程可以使用更輕量級的方式進行通信和同步，如使用通道（Channel）來實現(xiàn)協(xié)程之間的消息傳遞。

網(wǎng)絡

講一下TCP三次握手的過程

• TCP 是面向連接的協(xié)議，所以使用 TCP 前必須先建立連接，而建立連接是通過三次握手來進行的。三次握手的過程如下圖：

圖片

• TCP 三次握手

圖片

• 第一個報文 —— SYN 報文

圖片

• 第二個報文 —— SYN + ACK 報文

圖片

• 第三個報文 —— ACK 報文一旦完成三次握手，雙方都處于 ESTABLISHED 狀態(tài)，此時連接就已建立完成，客戶端和服務端就可以相互發(fā)送數(shù)據(jù)了。

• 客戶端收到服務端報文后，還要向服務端回應最后一個應答報文，首先該應答報文 TCP 首部 ACK 標志位置為 1 ，其次「確認應答號」字段填入 server_isn + 1 ，最后把報文發(fā)送給服務端，這次報文可以攜帶客戶到服務端的數(shù)據(jù)，之后客戶端處于 ESTABLISHED 狀態(tài)。
• 服務端收到客戶端的應答報文后，也進入 ESTABLISHED 狀態(tài)。
• 服務端收到客戶端的 SYN 報文后，首先服務端也隨機初始化自己的序號（server_isn），將此序號填入 TCP 首部的「序號」字段中，其次把 TCP 首部的「確認應答號」字段填入 client_isn + 1, 接著把 SYN 和 ACK 標志位置為 1。最后把該報文發(fā)給客戶端，該報文也不包含應用層數(shù)據(jù)，之后服務端處于 SYN-RCVD 狀態(tài)。
• 客戶端會隨機初始化序號（client_isn），將此序號置于 TCP 首部的「序號」字段中，同時把 SYN 標志位置為 1，表示 SYN 報文。接著把第一個 SYN 報文發(fā)送給服務端，表示向服務端發(fā)起連接，該報文不包含應用層數(shù)據(jù)，之后客戶端處于 SYN-SENT 狀態(tài)。
• 一開始，客戶端和服務端都處于 CLOSE 狀態(tài)。先是服務端主動監(jiān)聽某個端口，處于 LISTEN 狀態(tài)

TCP擁塞控制具體過程？

擁塞控制主要是四個算法：

• 慢啟動
• 擁塞避免
• 擁塞發(fā)生
• 快速恢復

一、慢啟動

慢啟動的算法記住一個規(guī)則就行：當發(fā)送方每收到一個 ACK，擁塞窗口 cwnd 的大小就會加 1。

這里假定擁塞窗口 cwnd 和發(fā)送窗口 swnd 相等，下面舉個栗子：

• 連接建立完成后，一開始初始化 cwnd = 1，表示可以傳一個 MSS 大小的數(shù)據(jù)。
• 當收到一個 ACK 確認應答后，cwnd 增加 1，于是一次能夠發(fā)送 2 個
• 當收到 2 個的 ACK 確認應答后， cwnd 增加 2，于是就可以比之前多發(fā)2 個，所以這一次能夠發(fā)送 4 個
• 當這 4 個的 ACK 確認到來的時候，每個確認 cwnd 增加 1， 4 個確認 cwnd 增加 4，于是就可以比之前多發(fā) 4 個，所以這一次能夠發(fā)送 8 個。

慢啟動算法的變化過程如下圖：

慢啟動算法

可以看出慢啟動算法，發(fā)包的個數(shù)是指數(shù)性的增長。

那慢啟動漲到什么時候是個頭呢？

有一個叫慢啟動門限 ssthresh （slow start threshold）狀態(tài)變量。

• 當 cwnd < ssthresh 時，使用慢啟動算法。
• 當 cwnd >= ssthresh 時，就會使用「擁塞避免算法」。

二、擁塞避免算法

前面說道，當擁塞窗口 cwnd 「超過」慢啟動門限 ssthresh 就會進入擁塞避免算法。

一般來說 ssthresh 的大小是 65535 字節(jié)。那么進入擁塞避免算法后，它的規(guī)則是：**每當收到一個 ACK 時，cwnd 增加 1/cwnd。*接上前面的慢啟動的栗子，現(xiàn)假定 ssthresh 為 8：

• 當 8 個 ACK 應答確認到來時，每個確認增加 1/8，8 個 ACK 確認 cwnd 一共增加 1，于是這一次能夠發(fā)送 9 個 MSS 大小的數(shù)據(jù)，變成了線性增長。

擁塞避免算法的變化過程如下圖：

擁塞避免

所以，我們可以發(fā)現(xiàn)，擁塞避免算法就是將原本慢啟動算法的指數(shù)增長變成了線性增長，還是增長階段，但是增長速度緩慢了一些。

就這么一直增長著后，網(wǎng)絡就會慢慢進入了擁塞的狀況了，于是就會出現(xiàn)丟包現(xiàn)象，這時就需要對丟失的數(shù)據(jù)包進行重傳。

當觸發(fā)了重傳機制，也就進入了「擁塞發(fā)生算法」。

三、擁塞發(fā)生

當網(wǎng)絡出現(xiàn)擁塞，也就是會發(fā)生數(shù)據(jù)包重傳，重傳機制主要有兩種：

• 超時重傳
• 快速重傳

這兩種使用的擁塞發(fā)送算法是不同的，接下來分別來說說。

3.1 當發(fā)生了「超時重傳」，則就會使用擁塞發(fā)生算法。

這個時候，ssthresh 和 cwnd 的值會發(fā)生變化：

• ssthresh 設為 cwnd/2，
• cwnd 重置為 1 （是恢復為 cwnd 初始化值，我這里假定 cwnd 初始化值 1）

擁塞發(fā)生算法的變化如下圖：

擁塞發(fā)送 —— 超時重傳

接著，就重新開始慢啟動，慢啟動是會突然減少數(shù)據(jù)流的。這真是一旦「超時重傳」，馬上回到解放前。但是這種方式太激進了，反應也很強烈，會造成網(wǎng)絡卡頓。就好像本來在秋名山高速漂移著，突然來個緊急剎車，輪胎受得了嗎。。。

3.2發(fā)生快速重傳的擁塞發(fā)生算法

還有更好的方式，前面我們講過「快速重傳算法」。當接收方發(fā)現(xiàn)丟了一個中間包的時候，發(fā)送三次前一個包的 ACK，于是發(fā)送端就會快速地重傳，不必等待超時再重傳。

TCP 認為這種情況不嚴重，因為大部分沒丟，只丟了一小部分，則 ssthresh 和 cwnd 變化如下：

• cwnd = cwnd/2 ，也就是設置為原來的一半;
• ssthresh = cwnd;
• 進入快速恢復算法

四、快速恢復

快速重傳和快速恢復算法一般同時使用，快速恢復算法是認為，你還能收到 3 個重復 ACK 說明網(wǎng)絡也不那么糟糕，所以沒有必要像 RTO 超時那么強烈。

正如前面所說，進入快速恢復之前，cwnd 和 ssthresh 已被更新了：

• cwnd = cwnd/2 ，也就是設置為原來的一半;
• ssthresh = cwnd;

然后，進入快速恢復算法如下：

• 擁塞窗口 cwnd = ssthresh + 3 （ 3 的意思是確認有 3 個數(shù)據(jù)包被收到了）；
• 重傳丟失的數(shù)據(jù)包；
• 如果再收到重復的 ACK，那么 cwnd 增加 1；
• 如果收到新數(shù)據(jù)的 ACK 后，把 cwnd 設置為第一步中的 ssthresh 的值，原因是該 ACK 確認了新的數(shù)據(jù)，說明從 duplicated ACK 時的數(shù)據(jù)都已收到，該恢復過程已經(jīng)結(jié)束，可以回到恢復之前的狀態(tài)了，也即再次進入擁塞避免狀態(tài)；

快速恢復算法的變化過程如下圖：

快速重傳和快速恢復

也就是沒有像「超時重傳」一夜回到解放前，而是還在比較高的值，后續(xù)呈線性增長。

http與https的區(qū)別？

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

https加密的過程？

SSL/TLS 協(xié)議基本流程：

• 客戶端向服務器索要并驗證服務器的公鑰。
• 雙方協(xié)商生產(chǎn)「會話秘鑰」。
• 雙方采用「會話秘鑰」進行加密通信。

前兩步也就是 SSL/TLS 的建立過程，也就是 TLS 握手階段。

基于 RSA 算法的 TLS 握手過程比較容易理解，所以這里先用這個給大家展示 TLS 握手過程，如下圖：

HTTPS 連接建立過程

TLS 協(xié)議建立的詳細流程：

1.ClientHello

首先，由客戶端向服務器發(fā)起加密通信請求，也就是 ClientHello 請求。

在這一步，客戶端主要向服務器發(fā)送以下信息：

（1）客戶端支持的 TLS 協(xié)議版本，如 TLS 1.2 版本。

（2）客戶端生產(chǎn)的隨機數(shù)（Client Random），后面用于生成「會話秘鑰」條件之一。

（3）客戶端支持的密碼套件列表，如 RSA 加密算法。

2.SeverHello

服務器收到客戶端請求后，向客戶端發(fā)出響應，也就是 SeverHello。服務器回應的內(nèi)容有如下內(nèi)容：

（1）確認 TLS 協(xié)議版本，如果瀏覽器不支持，則關(guān)閉加密通信。

（2）服務器生產(chǎn)的隨機數(shù)（Server Random），也是后面用于生產(chǎn)「會話秘鑰」條件之一。

（3）確認的密碼套件列表，如 RSA 加密算法。

（4）服務器的數(shù)字證書。

3.客戶端回應

客戶端收到服務器的回應之后，首先通過瀏覽器或者操作系統(tǒng)中的 CA 公鑰，確認服務器的數(shù)字證書的真實性。

如果證書沒有問題，客戶端會從數(shù)字證書中取出服務器的公鑰，然后使用它加密報文，向服務器發(fā)送如下信息：

（1）一個隨機數(shù)（pre-master key）。該隨機數(shù)會被服務器公鑰加密。

（2）加密通信算法改變通知，表示隨后的信息都將用「會話秘鑰」加密通信。

（3）客戶端握手結(jié)束通知，表示客戶端的握手階段已經(jīng)結(jié)束。這一項同時把之前所有內(nèi)容的發(fā)生的數(shù)據(jù)做個摘要，用來供服務端校驗。

上面第一項的隨機數(shù)是整個握手階段的第三個隨機數(shù)，會發(fā)給服務端，所以這個隨機數(shù)客戶端和服務端都是一樣的。

服務器和客戶端有了這三個隨機數(shù)（Client Random、Server Random、pre-master key），接著就用雙方協(xié)商的加密算法，各自生成本次通信的「會話秘鑰」。

4.服務器的最后回應

服務器收到客戶端的第三個隨機數(shù)（pre-master key）之后，通過協(xié)商的加密算法，計算出本次通信的「會話秘鑰」。

然后，向客戶端發(fā)送最后的信息：

（1）加密通信算法改變通知，表示隨后的信息都將用「會話秘鑰」加密通信。

（2）服務器握手結(jié)束通知，表示服務器的握手階段已經(jīng)結(jié)束。這一項同時把之前所有內(nèi)容的發(fā)生的數(shù)據(jù)做個摘要，用來供客戶端校驗。

至此，整個 TLS 的握手階段全部結(jié)束。接下來，客戶端與服務器進入加密通信，就完全是使用普通的 HTTP 協(xié)議，只不過用「會話秘鑰」加密內(nèi)容。

Redis

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ù)類型的應用場景：

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

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

• 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ù)。

Zset底層數(shù)據(jù)結(jié)構(gòu)？

Zset 類型的底層數(shù)據(jù)結(jié)構(gòu)是由壓縮列表或跳表實現(xiàn)的：

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

在 Redis 7.0 中，壓縮列表數(shù)據(jù)結(jié)構(gòu)已經(jīng)廢棄了，交由 listpack 數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)了。

MySQL

B+樹有什么特點？

B+ 樹就是對 B 樹做了一個升級，MySQL 中索引的數(shù)據(jù)結(jié)構(gòu)就是采用了 B+ 樹，B+ 樹結(jié)構(gòu)如下圖：

圖片

B+ 樹與 B 樹差異的點，主要是以下這幾點：

• 葉子節(jié)點（最底部的節(jié)點）才會存放實際數(shù)據(jù)（索引+記錄），非葉子節(jié)點只會存放索引；
• 所有索引都會在葉子節(jié)點出現(xiàn)，葉子節(jié)點之間構(gòu)成一個有序鏈表；
• 非葉子節(jié)點的索引也會同時存在在子節(jié)點中，并且是在子節(jié)點中所有索引的最大（或最?。?/li>
• 非葉子節(jié)點中有多少個子節(jié)點，就有多少個索引；

MySQL 默認的存儲引擎 InnoDB 采用的是 B+ 作為索引的數(shù)據(jù)結(jié)構(gòu)，原因有：

• B+ 樹的非葉子節(jié)點不存放實際的記錄數(shù)據(jù)，僅存放索引，因此數(shù)據(jù)量相同的情況下，相比存儲即存索引又存記錄的 B 樹，B+樹的非葉子節(jié)點可以存放更多的索引，因此 B+ 樹可以比 B 樹更「矮胖」，查詢底層節(jié)點的磁盤 I/O次數(shù)會更少。
• B+ 樹有大量的冗余節(jié)點（所有非葉子節(jié)點都是冗余索引），這些冗余索引讓 B+ 樹在插入、刪除的效率都更高，比如刪除根節(jié)點的時候，不會像 B 樹那樣會發(fā)生復雜的樹的變化；
• B+ 樹葉子節(jié)點之間用鏈表連接了起來，有利于范圍查詢，而 B 樹要實現(xiàn)范圍查詢，因此只能通過樹的遍歷來完成范圍查詢，這會涉及多個節(jié)點的磁盤 I/O 操作，范圍查詢效率不如 B+ 樹。

怎么做能使得查詢不需要3次io？

把節(jié)點緩存在內(nèi)存中，這樣下次查詢數(shù)據(jù)的時候，直接在內(nèi)存進行索引查找就可以了。

智力題

• 1000瓶毒藥里面只有1瓶是有毒的，問需要多少只老鼠才能在24小時后試出那瓶有毒。

參考：這是一個經(jīng)典的二分法或者說是二進制的問題。對于1000瓶藥，可以用二進制表示為從0000000000（0）到1111101000（1000）的范圍，總共需要10位。因此，需要10只老鼠來試出哪一瓶是有毒的。具體的實施方案就是，將每一瓶藥對應到一個二進制的數(shù)字，然后讓對應到1的位置的老鼠去試那一瓶藥。這樣，24小時后，只需要看哪些老鼠死了，就能確定哪一瓶藥是有毒的。

算法

• 二分查找（2 題）
• 洗牌算法
• 最大子數(shù)組和