大家好，我是小林。

網路崗位裡，可以說後端開發是最卷，投的人最多的，但是隔壁的客戶端開發投的就很少，有後端同學會被客戶端部門撈起來去面試，所以如果卷不過後端，又想進大廠的同學，可以嘗試投客戶端開發，面試相對沒那麼卷，薪資待遇跟後端也是一樣的。

今天分享一位快手客戶端一二三面的面經，同學的技術棧是C++後端，但是面試不會問後端內容了，主要就圍繞Cpp+作業系統+網路協定+演算法來問，相比後端所需要準備的內容就少了mysql 、redis、訊息佇列等後端元件，但是計算基礎的深度會問的比較深一點。

由其第三面，直接給兩個場景代碼題手寫出來，還是有點難度。。

快手一面

擁塞控制介紹一下

在網路出現擁塞時，如果繼續發送大量資料包，可能會導致資料包延遲、遺失等，這時TCP 就會重傳數據，但是一重傳就會導致網路的負擔更重，於是會導致更大的延遲以及更多的丟包，這個情況就會進入惡性循環被不斷地放大....

所以，TCP 不能忽略網路上發生的事，它被設計成一個無私的協議，當網路發送擁塞時，TCP 會自我犧牲，降低發送的資料量。

於是，就有了壅塞控制，控制的目的就是避免「發送方」的資料填滿整個網路。

為了在「傳送者」調節所要傳送資料的量，定義了一個叫做「壅塞視窗」的概念。

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

• 慢啟動
• 擁塞避免
• 擁塞發生
• 快速恢復

慢啟動

TCP 在剛建立連線完成後，首先是有個慢啟動的過程，這個慢啟動的意思就是一點一點的提高發送資料包的數量，如果一上來就發大量的數據，這不是給網路添堵嗎？

慢啟動的演算法記住一個規則就行：當發送方每收到一個ACK，擁塞視窗cwnd 的大小就會加1。

這裡假定擁塞視窗 cwnd 和發送視窗 swnd 相等，下面舉個栗子：

• 連線建立完成後，一開始初始化 cwnd = 1，表示可以傳送一個 MSS 大小的資料。
• 當收到一個ACK 確認應答後，cwnd 增加1，於是一次能夠發送2 個
• 當收到2 個的ACK 確認應答後， cwnd 增加2，於是就可以比之前多發2 個，所以這次能夠發送4 個
• 當這4 個的ACK 確認到來的時候，每個確認cwnd 增加1， 4 個確認cwnd 增加4，於是就可以比之前多發4 個，所以這次能夠發送8 個。

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

慢啟動演算法

可以看出慢啟動演算法，發包的數量是指數性的成長。

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

有一個叫慢啟動閘限 ssthresh （slow start threshold）狀態變數。

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

擁塞避免

當壅塞視窗 cwnd “超過”慢啟動閘限 ssthresh 就會進入壅塞避免演算法。

一般來說 ssthresh 的大小是 65535 位元組。

那麼進入擁塞避免演算法後，它的規則是：每當收到一個ACK 時，cwnd 增加1/cwnd。

接上前面的慢啟動的栗子，現假定 ssthresh 為 8：

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

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

擁塞避免

所以，我們可以發現，壅塞避免演算法就是將原本慢啟動演算法的指數成長變成了線性成長，還是成長階段，但是成長速度緩慢了一些。

就這麼一直成長著後，網路就會慢慢進入了擁塞的狀況了，於是就會出現丟包現象，這時就需要對遺失的資料包進行重傳。

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

擁塞發生

當網路出現壅塞，也就是會發生封包重傳，重傳機制主要有兩種：

• 超時重傳
• 快速重傳

當發生了「超時重傳」，則會使用擁塞發生演算法。

這時候，ssthresh 和cwnd 的值會改變：

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

擁塞發生演算法的變化如下圖：

擁塞發送—— 超時重傳

接著，就重新開始慢啟動，慢啟動是會突然減少資料流的。這真是一旦「超時重傳」，馬上回到解放前。但是這種方式太激進了，反應也很強烈，會造成網路卡頓。

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

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

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

快速恢復

快速重傳和快速恢復演算法一般同時使用，快速恢復演算法是認為，你還能收到3 個重複ACK 說明網路也不那麼糟糕，所以沒有必要像 RTO 逾時那麼強烈。

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

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

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

• 擁塞視窗 cwnd = ssthresh + 3 （ 3 的意思是確認有3 個資料包被收到了）；
• 重傳遺失的資料包；
• 如果再收到重複的ACK，那麼cwnd 增加1；
• 如果收到新數據的ACK 後，把cwnd 設定為第一步驟中的ssthresh 的值，原因是該ACK 確認了新的數據，說明從duplicated ACK 時的數據都已收到，該恢復過程已經結束，可以回到恢復之前的狀態了，也即再次進入擁塞避免狀態；

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

快速重傳和快速恢復

也就是沒有像「超時重傳」一夜回到解放前，而是還在比較高的數值，後續呈現線性成長。

http/https 的差別？

• HTTP 是超文本傳輸協議，資訊是明文傳輸，有安全風險的問題。HTTPS 則解決HTTP 不安全的缺陷，在TCP 和HTTP 網路層之間加入了SSL/TLS 安全協議，使得封包能夠加密傳輸。
• HTTP 連線建立相對簡單， TCP 三次握手之後便可進行HTTP 的訊息傳輸。而HTTPS 在TCP 三次握手之後，還需進行SSL/TLS 的握手過程，才可進入加密封包傳輸。
• 兩者的預設連接埠不一樣，HTTP 預設連接埠號碼是80，HTTPS 預設連接埠號碼是443。
• HTTPS 協定需要向CA（憑證權威）申請數位證書，以確保伺服器的身分是可信任的。

Https四次加密過程？

基於RSA 演算法的TLS 握手過程比較容易理解，所以這裡先用這個來展示TLS 握手過程，如下圖：

HTTPS 連線建立流程

TLS 協定建立的詳細流程：

1. ClientHello

首先，由客戶端向伺服器發起加密通訊請求，也就是 ClientHello 請求。

在這一步，客戶端主要向伺服器發送以下資訊：

（1）客戶端支援的TLS 協定版本，如TLS 1.2 版本。

（2）客戶端生產的隨機數（Client Random），後面用於產生「會話秘鑰」條件之一。

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

2. SeverHello

伺服器收到客戶端請求後，向客戶端發出回應，也就是 SeverHello。伺服器回應的內容有以下內容：

（1）確認TLS 協定版本，如果瀏覽器不支持，則關閉加密通訊。

（2）伺服器生產的隨機數（Server Random），也是後面用於生產「會話秘鑰」條件之一。

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

（4）伺服器的數位證書。

3.客戶端回應

在客戶端收到伺服器的回應之後，先透過瀏覽器或作業系統中的CA 公鑰，確認伺服器的數位憑證的真實性。

如果憑證沒有問題，用戶端會從數位憑證中取出伺服器的公鑰，然後使用它加密封包，向伺服器發送以下資訊：

（1）一個隨機數（pre-master key）。該隨機數會被伺服器公鑰加密。

（2）加密通訊演算法改變通知，表示隨後的資訊都將以「會話秘鑰」加密通訊。

（3）客戶端握手結束通知，表示客戶端的握手階段已經結束。這一項同時把之前所有內容的發生的資料做個摘要，用來供服務端校驗。

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

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

4. 伺服器的最後回應

伺服器收到客戶端的第三個隨機數（pre-master key）之後，透過協商的加密演算法，計算出本次通訊的「會話秘鑰」。

然後，向客戶端發送最後的訊息：

（1）加密通訊演算法改變通知，表示隨後的資訊都將以「會話秘鑰」加密通訊。

（2）伺服器握手結束通知，表示伺服器的握手階段已經結束。這一項同時把之前所有內容的發生的資料做個摘要，用來供客戶端校驗。

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

get和post的差別？

• 根據 RFC 規範，GET 的語意是從伺服器取得指定的資源，這個資源可以是靜態的文字、頁面、圖片影片等。GET 請求的參數位置一般是寫在URL 中，URL 規定只能支援ASCII，所以GET 請求的參數只允許ASCII 字符，而且瀏覽器會對URL 的長度有限制（HTTP協議本身對URL長度並沒有做任何規定）。
• 根據RFC 規範，POST 的語意是根據請求負荷（封包body）對指定的資源做出處理，具體的處理方式視資源類型而不同。POST 請求攜帶資料的位置一般是寫在報文body 中，body 中的資料可以是任意格式的數據，只要客戶端與服務端協商好即可，而且瀏覽器不會對body 大小做限制。

行程執行緒有什麼區別？

• 資源佔用：每個行程都有獨立的位址空間、檔案描述子和其他系統資源，進程之間的資源是相互獨立的，而執行緒共享所屬進程的位址空間和資源，包括檔案描述子、訊號處理等。
• 調度和切換：進程是系統進行調度和分配資源的基本單位，進程之間的切換開銷相對較大。而執行緒是在行程內部執行的，執行緒的切換開銷相對較小。
• 通訊與同步：進程之間通訊的方式包括管道、訊息佇列、共享記憶體等，進程間通訊相對複雜。執行緒之間共享進程的記憶體空間，直接讀寫共享資料即可實現通訊和同步。

執行緒有哪些資源，棧中保存什麼？

線程在作業系統中有一些特定的資源，包括：

• 執行緒控制區塊（Thread Control Block，TCB）：用於保存執行緒的狀態訊息，如程式計數器（Program Counter，PC）、暫存器值、執行緒ID、執行緒優先權等。
• 堆疊（Stack）：每個執行緒都有自己的堆疊空間，用於保存函數呼叫的局部變數、函數的回傳位址以及其他暫存資料。棧是執行緒私有的，不同執行緒之間的棧是相互獨立的。
• 暫存器（Registers）：執行緒在執行過程中會使用到暫存器，包括通用暫存器（如EAX、EBX等）、程式計數器（PC）等。暫存器保存了執行緒目前的執行狀態。
• 共享資源：執行緒可以共享所屬程序的資源，如開啟的檔案、訊號處理器等。這些資源可以在執行緒之間共享和存取。

棧中，主要保存了以下內容：

• 函數呼叫的局部變數：當一個函數被呼叫時，其局部變數會被保存在堆疊中。這些局部變數在函數執行結束後會被銷毀。
• 函數的回傳位址：當一個函數執行完畢後，就需要回到呼叫函數的位址。返回位址會被保存在堆疊中，以便函數執行完畢後能夠正確返回。
• 函數呼叫過程中的暫存數據：在函數執行過程中，可能會需要保存一些臨時數據，如函數的參數、中間計算結果等，這些數據會保存在堆疊中。

函數呼叫的時候，壓棧怎麼樣的

函數呼叫時，會進行以下壓棧操作：

• 儲存回傳位址：在函數呼叫前，呼叫指令會將下一指令的位址（即函數呼叫後需要繼續執行的位址）壓入堆疊中，以便函數執行完畢後能夠正確地回到呼叫點。
• 儲存呼叫者的堆疊幀指標：在函數呼叫前，呼叫指令會將目前堆疊幀指標（即呼叫者的堆疊指標）壓入堆疊中，以便函數執行完畢後能夠恢復到呼叫者的執行狀態。
• 傳遞參數：函數呼叫時，會將參數值依序壓入堆疊中，這些參數值在函數內部可以透過堆疊來存取。
• 分配局部變數空間：函數呼叫時，會為局部變數分配空間，這些局部變數會被保存在堆疊中。堆疊指標會相應地移動以適應新的局部變數空間。

靜態連結庫和動態連結庫有什麼不同？

• 連結方式：靜態連結函式庫在編譯連結時會被完整地複製到可執行檔中，成為執行檔的一部分；而動態連結函式庫在編譯連結時只會在執行檔中包含對函式庫的引用，實際的庫檔案在運行時由作業系統動態載入。
• 檔案大小：靜態連結庫會讓可執行檔的大小增加，因為函式庫的程式碼被完整地複製到執行檔中；而動態連結函式庫不會增加可執行檔的大小，因為函式庫的程式碼在執行時才會被載入。
• 記憶體佔用：靜態連結庫在運行時會被完整地加載到記憶體中，佔用固定的記憶體空間；而動態連結庫在運行時才會被加載，可以在多個進程之間共享，減少記憶體佔用。
• 可擴展性：動態連結庫的可擴展性更好，可以在不修改可執行文件的情況下替換或添加新的庫文件，而靜態連結庫需要重新編譯連結。

動態連結庫怎麼裝載到記憶體的？

透過用mmap把該庫直接映射到各個進程的位址空間中，儘管每個進程都認為自己地址空間中加載了該庫，但實際上該庫在內存中只有一份，mmap就這樣很神奇和動態連結庫聯動起來了。

圖片

虛擬記憶體介紹一下

• 第一，虛擬記憶體可以使得進程對運行記憶體超過物理記憶體大小，因為程式運行符合局部性原理，CPU 存取記憶體會有很明顯的重複存取的傾向性，對於那些沒有被經常使用到的內存，我們可以把它換出到實體記憶體之外，例如硬碟上的swap 區域。
• 第二，由於每個行程都有自己的頁表，所以每個行程的虛擬記憶體空間就是互相獨立的。進程也沒有辦法存取其他進程的頁表，所以這些頁表是私有的，這就解決了多進程之間位址衝突的問題。
• 第三，頁表裡的頁表項中除了實體位址之外，還有一些標記屬性的比特，例如控制一個頁的讀寫權限，標記該頁是否存在等。在記憶體存取方面，作業系統提供了更好的安全性。

中斷是什麼

在作業系統中，中斷是指由硬體或軟體觸發的事件，它會暫時中止目前正在執行的程序，並轉而執行與中斷相關的處理程序。中斷可以是內部的，如除法錯誤或越界訪問，也可以是外部的，如硬體設備的輸入/輸出請求或時脈中斷。

中斷的作用是提供一種機制來處理和回應各種事件，例如處理硬體設備的輸入/輸出請求、處理異常情況、進行時脈調度等。當發生中斷時，作業系統會根據中斷類型決定要執行的中斷處理程序，並在處理中斷後恢復原來的程式執行。

中斷處理程序可以執行一系列操作，如保存目前程序的上下文、處理中斷事件、與設備通訊、調度其他程序等。透過使用中斷，作業系統可以實現多任務處理、即時回應外部事件、提高系統的可靠性和穩定性。

作業系統的鎖，自己實作一個讀寫鎖

讀者只會讀取數據，不會修改數據，寫者即可以讀取也可以修改數據。

讀者-寫者的問題描述：

• 「讀-讀」允許：同一時刻，允許多個讀者同時閱讀
• 「讀-寫」互斥：沒有寫者時讀者才能讀，沒有讀者時寫者才能寫
• 「寫-寫」互斥：沒有其他寫者時，寫者才能寫

接下來，提出幾個解決方案來分析分析。

方案一

使用信號量的方式來嘗試解決：

• 信號量 wMutex：控制寫入操作的互斥訊號量，初始值為1 ；
• 讀者數 rCount：正在進行讀取操作的讀者數，初始化為0；
• 信號量 rCountMutex：控制rCount 讀者計數器的互斥修改，初始值為1；

接下來看看程式碼的實作：

圖片

上面的這種實現，是讀者優先的策略，因為只要有讀者正在讀的狀態，後來的讀者都可以直接進入，如果讀者持續不斷進入，則寫者會處於飢餓狀態。

方案二

那既然有讀者優先策略，自然也有寫者優先策略：

• 只要有寫者準備要寫入，寫者應盡快執行寫入操作，後來的讀者就必須阻塞；
• 如果有寫者持續不斷寫入，則讀者就處於飢餓；

在方案一的基礎上新增下列變數：

• 信號量 rMutex：控制讀者進入的互斥信號量，初始值為1；
• 信號量 wDataMutex：控制寫者寫入操作的互斥信號量，初始值為1；
• 寫者計數 wCount：記錄寫者數量，初始值為0；
• 信號量 wCountMutex：控制wCount 互斥修改，初始值為1；

具體實作如下程式碼：

注意，這裡rMutex 的作用，開始有多個讀者讀數據，它們全部進入讀者隊列，此時來了一個寫者，執行了P(rMutex) 之後，後續的讀者由於阻塞在rMutex 上，都不能再進入讀者隊列，而寫者到來，則可以全部進入寫者隊列，因此保證了寫者優先。

同時，第一個寫者執行了 P(rMutex) 之後，也不能馬上開始寫，必須等到所有進入讀者佇列的讀者都執行完讀操作，透過 V(wDataMutex) 喚醒寫者的寫入操作。

方案三

既然讀者優先策略和寫者優先策略都會造成飢餓的現象，那麼我們就來實現公平策略。

公平策略：

• 優先順序相同；
• 寫者、讀者互斥訪問；
• 只能一個寫者訪問臨界區；
• 可以有多個讀者同時存取臨界資源；

具體程式碼實作：

圖片

看完程式碼不知你是否有這樣的疑問，為什麼加了一個信號量 flag，就實現了公平競爭？

對比方案一的讀者優先策略，可以發現，讀者優先中只要後續有讀者到達，讀者就可以進入讀者隊列， 而寫者必須等待，直到沒有讀者到達。

沒有讀者到達會導致讀者隊列為空，即 rCount==0，此時寫者才可以進入臨界區執行寫入操作。

而這裡 flag 的作用就是阻止讀者的這種特殊權限（特殊權限是只要讀者到達，就可以進入讀者隊列）。

例如：開始來了一些讀者讀數據，它們全部進入讀者隊列，此時來了一個寫者，執行P(falg) 操作，使得後續到來的讀者都阻塞在flag 上，不能進入讀者隊列，這會使得讀者隊列逐漸為空，即rCount 減為0。

這個寫者也不能立刻開始寫（因為此時讀者佇列不為空），會阻塞在信號量wDataMutex 上，讀者佇列中的讀者全部讀取結束後，最後一個讀者程序執行V(wDataMutex)，喚醒剛才的寫者，寫者則繼續開始進行寫入操作。

演算法題

• 二元樹層序遍歷建構一個二元樹測試

快手二面

指標和引用值傳遞的概念

• 值傳遞是指將參數的值複製一份，並傳遞給函數或方法進行操作。在值傳遞中，函數或方法對參數進行修改不會影響到原始的變數值。
• 指標引用是指將參數的記憶體位址傳遞給函數或方法，使得函數或方法可以直接存取和修改原始變數的值。在指標參考中，函數或方法對參數的修改會直接反映在原始變數上。

int double string強制轉換為什麼會精確度遺失?

• 整數到浮點數：整數型別是精確表示的，而浮點數型則是近似表示的，具有固定的有效位數。當整數轉換為浮點數時，可能會導致精確度遺失，因為浮點數無法精確地表示整數的所有位數。
• 浮點數到整數：浮點數型別具有小數部分和指數部分，而整數型別只能表示整數值。當浮點數轉換為整數時，小數部分將被丟棄，可能導致精確度損失。
• 字串到數值類型：字串表示的是文字形式的數據，而數值類型表示的是數值形式的數據。當字串轉換為數值類型時，如果字串無法解析為有效的數值，或者字串表示的數值超出了目標類型的範圍，就會導致精度遺失或產生錯誤的結果。

void*是什麼?

void*是一種通用的指標類型，稱為"無型別指標"。它可以用來表示指向任何類型的指針，因為void*指針沒有指定特定的資料類型。

由於void*是無型別的，它不能直接進行解引用操作，也不能進行指標運算。在使用void*指標時，需要將其轉換為特定的指標類型才能進行操作。

void*指標常用於需要在不同類型之間進行通用操作的情況，例如在函數中傳遞任意類型的指標參數或在動態記憶體分配中使用。

malloc的參數列表void*怎麼轉化為int*的？

可以使用型別轉換將void*指標轉換為int*指標。以下是將void*指標轉換為int*指標的範例程式碼：

void* voidPtr = malloc(sizeof(int));  // 分配内存并返回void*指针
int* intPtr = (int*)voidPtr;           // 将void*指针转化为int*指针

// 现在可以通过intPtr指针访问int类型的数据
*intPtr = 42;
1.
2.
3.
4.
5.

在上述範例中，使用malloc函數分配了儲存一個int類型資料所需的內存，並傳回了一個void*指標。然後，透過將void*指針轉換為int*指針，將其賦值給intPtr變數。現在，可以透過intPtr指標存取和操作int類型的資料。

演算法題

• 從一個陣列中找出滿足比左側都要大比右側都要小的數

快手三面

• n個執行緒依照順序列印編號
• 設計一個貪吃蛇小遊戲，蛇的資料結構和蛇體更新和碰撞偵測

三面一個八股沒問，直接來兩個場景代碼題，比較注重實操，太難啦。