跪了,米哈游是真的細節(jié)...
大家好，我是小林。
今天分享米哈游的校招面經(jīng)，雖然問的問題不算很多，但是主要是考慮的計算機基礎(chǔ)的細節(jié)，游戲類的公司都會比較注重性能，所以對于計算機基礎(chǔ)方面的內(nèi)容會考察比較多。
米哈游面試輸入URL過程用到哪些協(xié)議？
主要會涉及HTTP/HTTPS協(xié)議、DNS協(xié)議、TCP協(xié)議、ARP協(xié)議、OPSF協(xié)議。
輸入URL過程如下：
- DNS 解析：當用戶輸入一個網(wǎng)址并按下回車鍵的時候，瀏覽器獲得一個域名，而在實際通信過程中，我們需要的是一個 IP 地址，因此我們需要先把域名轉(zhuǎn)換成相應(yīng) IP 地址。
- TCP 連接：瀏覽器通過 DNS 獲取到 Web 服務(wù)器真正的 IP 地址后，便向 Web 服務(wù)器發(fā)起 TCP 連接請求，通過 TCP 三次握手建立好連接。
- 建立TCP協(xié)議時，需要發(fā)送數(shù)據(jù)，發(fā)送數(shù)據(jù)在網(wǎng)絡(luò)層使用IP協(xié)議， 通過IP協(xié)議將IP地址封裝為IP數(shù)據(jù)報；然后此時會用到ARP協(xié)議，主機發(fā)送信息時將包含目標IP地址的ARP請求廣播到網(wǎng)絡(luò)上的所有主機，并接收返回消息，以此確定目標的物理地址，找到目的MAC地址；
- IP數(shù)據(jù)包在路由器之間，路由選擇使用OPSF協(xié)議， 采用Dijkstra算法來計算最短路徑樹，抵達服務(wù)端。
- 發(fā)送 HTTP 請求：建立 TCP 連接之后，瀏覽器向 Web 服務(wù)器發(fā)起一個 HTTP 請求（如果是HTTPS協(xié)議，發(fā)送HTTP 請求之前還需要完成TLS四次握手）；
- 處理請求并返回：服務(wù)器獲取到客戶端的 HTTP 請求后，會根據(jù) HTTP 請求中的內(nèi)容來決定如何獲取相應(yīng)的文件，并將文件發(fā)送給瀏覽器。
- 瀏覽器渲染：瀏覽器根據(jù)響應(yīng)開始顯示頁面，首先解析 HTML 文件構(gòu)建 DOM 樹，然后解析 CSS 文件構(gòu)建渲染樹，等到渲染樹構(gòu)建完成后，瀏覽器開始布局渲染樹并將其繪制到屏幕上。
TCP中斷了怎么辦？發(fā)送方幾個報文都沒回復怎么辦？
如果TCP意外斷開，并沒有正常關(guān)閉socket，雙方并未按照協(xié)議上的四次揮手去斷開連接。
那么這時候正在執(zhí)行Recv或Send操作的一方就會因為沒有任何連接中斷的通知而一直等待下去，也就是會被長時間卡住。
像這種如果一方已經(jīng)關(guān)閉或異常終止連接，而另一方卻不知道，我們將這樣的TCP連接稱為半打開的。
解決意外中斷辦法都是利用保活機制。而保活機制分又可以讓底層實現(xiàn)也可自己實現(xiàn)。
自己編寫心跳包程序
在自己的程序中加入一條線程，定時向?qū)Χ税l(fā)送數(shù)據(jù)包，查看是否有ACK，如果有則連接正常，沒有的話則連接斷開。
比如，web 服務(wù)軟件一般都會提供 keepalive_timeout 參數(shù)，用來指定 HTTP 長連接的超時時間。如果設(shè)置了 HTTP 長連接的超時時間是 60 秒，web 服務(wù)軟件就會啟動一個定時器，如果客戶端在完成一個 HTTP 請求后，在 60 秒內(nèi)都沒有再發(fā)起新的請求，定時器的時間一到，就會觸發(fā)回調(diào)函數(shù)來釋放該連接。
web 服務(wù)的 心跳機制
啟動 TCP 的keepAlive機制
以服務(wù)器端為例，如果當前server端檢測到超過一定時間沒有數(shù)據(jù)傳輸，那么會向client端發(fā)送一個心跳探測報文，如果連續(xù)幾個探測報文都沒有得到響應(yīng)，則認為當前的 TCP 連接已經(jīng)死亡，系統(tǒng)內(nèi)核將錯誤信息通知給上層應(yīng)用程序。
在 Linux 內(nèi)核可以有對應(yīng)的參數(shù)可以設(shè)置保活時間、保活探測的次數(shù)、保活探測的時間間隔，以下都為默認值：
net.ipv4.tcp_keepalive_time=7200
net.ipv4.tcp_keepalive_intvl=75
net.ipv4.tcp_keepalive_probes=9
- tcp_keepalive_time=7200：表示保活時間是 7200 秒（2小時），也就 2 小時內(nèi)如果沒有任何連接相關(guān)的活動，則會啟動保活機制
- tcp_keepalive_intvl=75：表示每次檢測間隔 75 秒；
- tcp_keepalive_probes=9：表示檢測 9 次無響應(yīng)，認為對方是不可達的，從而中斷本次的連接。
也就是說在 Linux 系統(tǒng)中，最少需要經(jīng)過 2 小時 11 分 15 秒才可以發(fā)現(xiàn)一個「死亡」連接。
img
注意，應(yīng)用程序若想使用 TCP 保活機制需要通過 socket 接口設(shè)置 SO_KEEPALIVE 選項才能夠生效，如果沒有設(shè)置，那么就無法使用 TCP 保活機制。
如果開啟了 TCP 保活，需要考慮以下幾種情況：
- 第一種，對端程序是正常工作的。當 TCP 保活的探測報文發(fā)送給對端, 對端會正常響應(yīng)，這樣 TCP 保活時間會被重置，等待下一個 TCP 保活時間的到來。
- 第二種，對端主機宕機并重啟。當 TCP 保活的探測報文發(fā)送給對端后，對端是可以響應(yīng)的，但由于沒有該連接的有效信息，會產(chǎn)生一個 RST 報文，這樣很快就會發(fā)現(xiàn) TCP 連接已經(jīng)被重置。
- 第三種，是對端主機宕機（注意不是進程崩潰，進程崩潰后操作系統(tǒng)在回收進程資源的時候，會發(fā)送 FIN 報文，而主機宕機則是無法感知的，所以需要 TCP 保活機制來探測對方是不是發(fā)生了主機宕機），或?qū)Χ擞捎谄渌驅(qū)е聢笪牟豢蛇_。當 TCP 保活的探測報文發(fā)送給對端后，石沉大海，沒有響應(yīng)，連續(xù)幾次，達到保活探測次數(shù)后，TCP 會報告該 TCP 連接已經(jīng)死亡。
鎖有哪些？
Linux 提供的鎖機制，主要有互斥鎖、信號量、自旋鎖、讀寫鎖。
- 互斥鎖（Mutex）：也稱為互斥量，用于保護共享資源，確保同一時間只有一個線程可以訪問該資源。當一個線程獲取到互斥鎖后，其他線程需要等待鎖釋放才能繼續(xù)訪問。
- 信號量（Semaphore）：用于控制對一組資源的訪問。信號量可以允許多個線程同時訪問資源，但是需要在訪問前進行P操作（申請資源）和在訪問結(jié)束后進行V操作（釋放資源），以確保資源的正確使用。
- 自旋鎖（Spinlock）：是一種忙等待鎖，在獲取鎖之前，線程會一直嘗試獲取鎖，而不會進入睡眠狀態(tài)。自旋鎖適用于保護臨界區(qū)較小、鎖占用時間短暫的情況。
- 讀寫鎖（ReadWrite Lock）：也稱為共享-獨占鎖，用于在讀操作和寫操作之間提供更好的并發(fā)性。讀寫鎖允許多個線程同時讀取共享資源，但是在寫操作時需要獨占訪問，保證數(shù)據(jù)的一致性。
鎖本身怎么保證線程安全？為什么一個線程拿到鎖以后，另一個線程就無法獲得鎖？
所謂的鎖，在計算機里本質(zhì)上就是一塊內(nèi)存空間。當這個空間被賦值為1的時候表示加鎖了，被賦值為0的時候表示解鎖了，僅此而已。多個線程搶一個鎖，就是搶著要把這塊內(nèi)存賦值為1。在一個多核環(huán)境里，內(nèi)存空間是共享的。
CPU 通常會有多個CPU核心，每個核上各跑一個線程，那如何保證一次只有一個線程成功搶到鎖呢？這必須要硬件的支持，譬如提供某種特殊指令。具體的實現(xiàn)如下。
硬件實現(xiàn)
CPU如果提供一些用來構(gòu)建鎖的原子性指令，比如x86的XCHG或CMPXCHG（加上LOCK prefix），能夠完成原子性的compare-and-swap （CAS）機制，用這樣的硬件指令就能實現(xiàn)自旋鎖。
畫外音：那么CAS是什么呢？
- CAS有3個操作數(shù)，內(nèi)存值V，舊的預期值A(chǔ)，要修改的新值B。當且僅當預期值A(chǔ)和內(nèi)存值V相同時，將內(nèi)存值V修改為B，否則什么都不做。反正就是我知道你flag為0，我來了，誒？你的flag怎么是1？那我走了，再見。
LOCK前綴的作用是鎖定系統(tǒng)總線（或者鎖定某一塊cache line）來實現(xiàn)原子性，簡單來說就是，如果指令前加了LOCK前綴，就是告訴其他核，一旦我開始執(zhí)行這個指令了，在我結(jié)束這個指令之前，誰也不許動，這樣便實現(xiàn)了一次只能有一個核對同一個內(nèi)存地址賦值。
操作系統(tǒng)實現(xiàn)
CPU提供了特殊硬件來保證內(nèi)存操作的原子性的時候，再通過一種簡單的邏輯，我們就可以構(gòu)建出一個簡單的自旋鎖來了。
下面就可以利用CAS來實現(xiàn)自旋鎖了：
// 1表示自旋鎖已分配給某個線程，0表示自旋鎖沒有分配個任何線程，即處于釋放狀態(tài)
int owner = 0;
void spin_lock(int * owner ) {
while(!compare_and_set(owner, 0, 1) {
}
}//需要說明的一點是系統(tǒng)對comare_and_set的內(nèi)核實現(xiàn)中包含對總線加鎖
這個邏輯很簡單，我們讓多個線程持續(xù)地搶著將某塊內(nèi)存地址的值賦為1（原始為0），誰先搶到了誰就可以進入臨界區(qū)，沒搶到的線程繼續(xù)在一個循環(huán)里面反復讀取這塊內(nèi)存地址的值，看看自己的機會是不是到了。當搶到鎖的線程在它的臨界區(qū)結(jié)束以后，就可以把該內(nèi)存地址的值賦為0，表示現(xiàn)在其他人可以搶鎖了，用這種方式構(gòu)建出來的鎖也被稱為自旋鎖，自旋的意思就是沒有拿到鎖的線程就在那兒自己轉(zhuǎn)兒。
接下來我們可以利用 CAS 原子操作實現(xiàn)互斥鎖，我們可以通過操作系統(tǒng)的介入，來實現(xiàn)一個線程向操作系統(tǒng)申請把自己掛起，還是把自己掛起，將CPU讓出來，這樣或許其他的線程能做點更有用的事情。通過這樣一種機制構(gòu)建出來的鎖，常常被稱為mutex（互斥鎖）。
lock:
movb $0, $al
xchgb $al, mutex
if(al 寄存器的內(nèi)存 > 0) {
return0;
} else
{
掛起等待;
}
goto lock;
unlock
movb $1, mutex
喚醒等待 mutex 的線程;
return 0;
lock：這一步先將0賦值到寄存器al，再將mutex與al中的值交換（xchgb指令，CAS原子操作），再進行判斷。當對某個線程進行l(wèi)ock操作時，即使在中間任意一步被切出去也沒有問題。這樣就保證了lock的操作也是原子的。
多線程一定好嗎？怎么選用？
不一定的，線程越多，系統(tǒng)的運行速度不一定越快。
多線程的優(yōu)點是提高程序的并發(fā)性，因為多線程可以同時執(zhí)行多個任務(wù)，分利用多核處理器的性能，提高程序的處理能力和響應(yīng)速度，所以如果任務(wù)可以進行有效的并行處理，并且對響應(yīng)時間有較高的要求，多線程可以提升性能和用戶體驗。
而多線程的缺點主要是：
- 多線程編程復雜：多線程編程需要考慮線程同步、共享資源訪問等問題，容易引發(fā)死鎖、競態(tài)條件等并發(fā)問題，增加了程序的復雜性和調(diào)試難度。
- 資源消耗：多線程需要占用額外的內(nèi)存和CPU資源，線程的創(chuàng)建、銷毀和切換都需要一定的開銷，如果線程數(shù)量過多，會導致系統(tǒng)資源的浪費和性能下降。
線程切換詳細過程是怎么樣的？上下文保存在哪里？
線程切換的詳細過程可以分為以下幾個步驟：
- 上下文保存：當操作系統(tǒng)決定切換到另一個線程時，它首先會保存當前線程的上下文信息。上下文信息包括寄存器狀態(tài)、程序計數(shù)器、堆棧指針等，用于保存線程的執(zhí)行狀態(tài)。
- 切換到調(diào)度器：操作系統(tǒng)將執(zhí)行權(quán)切換到調(diào)度器（Scheduler）。調(diào)度器負責選擇下一個要執(zhí)行的線程，并根據(jù)調(diào)度算法做出決策。
- 上下文恢復：調(diào)度器選擇了下一個要執(zhí)行的線程后，它會從該線程保存的上下文信息中恢復線程的執(zhí)行狀態(tài)。
- 切換到新線程：調(diào)度器將執(zhí)行權(quán)切換到新線程，使其開始執(zhí)行。
上下文信息的保存通常由操作系統(tǒng)負責管理，具體保存在哪里取決于操作系統(tǒng)的實現(xiàn)方式。一般情況下，上下文信息會保存在線程的控制塊（Thread Control Block，TCB）中。
TCB是操作系統(tǒng)用于管理線程的數(shù)據(jù)結(jié)構(gòu)，包含了線程的狀態(tài)、寄存器的值、堆棧信息等。當發(fā)生線程切換時，操作系統(tǒng)會通過切換TCB來保存和恢復線程的上下文信息。
如果要對一個很大的數(shù)據(jù)集，進行排序，而沒辦法一次性在內(nèi)存排序，這時候怎么辦？
可以使用外部排序來解決，基本思路分為兩個階段。
部分排序階段。
我們根據(jù)內(nèi)存大小，將待排序的文件拆成多個部分，使得每個部分都是足以存入內(nèi)存中的。然后選擇合適的內(nèi)排序算法，將多個文件部分排序，并輸出到容量可以更大的外存臨時文件中，每個臨時文件都是有序排列的，我們將其稱之為一個“順段”。
在第一個階段部分排序中，由于內(nèi)存可以裝下每個順段的所有元素，可以使用快速排序，時間復雜度是O(nlogn)。
歸并階段
我們對前面的多個“順段”進行合并，思想和歸并排序其實是一樣的。以 2 路歸并為例，每次都將兩個連續(xù)的順段合并成一個更大的順段。
因為內(nèi)存限制，每次可能只能讀入兩個順段的部分內(nèi)容，所以我們需要一部分一部分讀入，在內(nèi)存里將可以確定順序的部分排列，并輸出到外存里的文件中，不斷重復這個過程，直至兩個順段被完整遍歷。這樣經(jīng)過多層的歸并之后，最終會得到一個完整的順序文件。
歸并階段有個非常大的時間消耗就是 IO，也就是輸入輸出。最好就是讓歸并的層數(shù)越低越好，為了降低降低歸并層數(shù)，可以使用敗者樹。
敗者樹中的非終端結(jié)點中存儲的是勝利（左右孩子相比較，誰最小即為勝者）的一方；而敗者樹中的非終端結(jié)點存儲的是失敗的一方。而在比較過程中，都是拿勝者去比較。
現(xiàn)在有了敗者樹的加持，多路歸并排序就可以比較高效地解決外部排序的問題了。
大致思路就是：
- 先用內(nèi)排序算法（比如快速排序），盡可能多的加載源文件，將其變成 n 個有序順段。
- 在內(nèi)存有限的前提下每 k 個文件為一組，每次流式地從各個文件中讀取一個單詞，借助敗者樹選出字典序最低的一個，輸出到文件中，這樣就可以將 k 個順段合并到一個順段中了；反復執(zhí)行這樣的操作，直至所有順段被歸并到同一個順段。
算法
手撕LRU算法（思路：鏈表+哈希表）
#include <iostream>
#include <unordered_map>
#include <list>
using namespace std;
class LRUCache {
private:
int capacity;
unordered_map<int, pair<int, list<int>::iterator>> cache;
list<int> lru;
public:
LRUCache(int cap) {
capacity = cap;
}
int get(int key) {
if (cache.find(key) != cache.end()) {
// 將訪問的元素移到鏈表頭部
lru.erase(cache[key].second);
lru.push_front(key);
cache[key].second = lru.begin();
return cache[key].first;
}
return -1;
}
void put(int key, int value) {
if (cache.find(key) != cache.end()) {
// 更新已存在的元素的值，并將其移到鏈表頭部
lru.erase(cache[key].second);
}
else if (cache.size() >= capacity) {
// 刪除最久未使用的元素
cache.erase(lru.back());
lru.pop_back();
}
// 插入新元素到鏈表頭部
lru.push_front(key);
cache[key] = make_pair(value, lru.begin());
}
};
int main() {
LRUCache cache(2); // 創(chuàng)建容量為2的LRU緩存
cache.put(1, 1);
cache.put(2, 2);
cout << cache.get(1) << endl; // 輸出 1
cache.put(3, 3); // 因為緩存容量已滿，所以刪除最久未使用的元素2
cout << cache.get(2) << endl; // 輸出 -1，因為元素2已被刪除
cache.put(4, 4); // 因為緩存容量已滿，所以刪除最久未使用的元素1
cout << cache.get(1) << endl; // 輸出 -1，因為元素1已被刪除
cout << cache.get(3) << endl; // 輸出 3
cout << cache.get(4) << endl; // 輸出 4
return 0;
}
歷史好文：