面試的過程中，為了考察面試者的基礎(chǔ)功力，除了算法以外，操作系統(tǒng)將會占比很大的權(quán)重，本文給大家分享我在面試過程中出現(xiàn)的非常高頻的面試題，我基本上會從兩個角度來闡述，一個是"官話"，一個是“大白話”。希望對即將面試的你有所幫助

1、為什么有了進程，還要有線程呢？

為了提高系統(tǒng)資源的利用率和系統(tǒng)的吞吐量，通常進程可讓多個程序并發(fā)的執(zhí)行，但是也會帶來一些問題

官話

• 進程如果在執(zhí)行的過程被阻塞，那這個進程將被掛起，這時候進程中有些等待的資源得不到執(zhí)行：

• 進程在同一時間只能做一件事兒

基于以上的缺點，操作系統(tǒng)引入了比進程粒度更小的線程，作為并發(fā)執(zhí)行的基本單位，從而減少程序在并發(fā)執(zhí)行時所付出的時間和空間開銷，提高并發(fā)性能。

舉個例子

小Q當年開發(fā)了一個聊天軟件，給女朋友說：咋們以后不用什么qq，微信了，我寫個聊天工具，咱兩正兒八經(jīng)的兩人世界可好。

說干就干，小Q很快就完成了開發(fā)，然后開始測試，打電話讓女朋友讓她發(fā)個信息，小Q就等著，等啊等啊，怎么還沒有發(fā)信息過來，沒顯示啊，一臉懵逼，單步調(diào)試吧，發(fā)現(xiàn)程序卡在了wati for user input不動了。牛逼，程序不輸入就沒辦法執(zhí)行后面的任務。咋搞？要不設(shè)置個1s，用戶1s不輸入直接跳過進行后面的接收階段和顯示階段，牛皮牛皮，果然好使，好使個錘錘，這樣用戶輸入信息不就很可能丟失，咋搞？

能不能將輸入和顯示這兩個動作給分開，一個負責輸入，發(fā)送消息，一個負責讀信息和顯示。不夸夸你自己嗎，直接開干呈現(xiàn)兩個窗口。

回來回來，這就是我們的多進程。不過多進程也還是有些問題需要注意，開多個窗口沒問題，無腦開窗口撩騷直接被榨干(內(nèi)存耗盡)，而且想要幾個窗口交換個數(shù)據(jù)也是賊麻煩，這是為啥呢

多進程的程序，每個進程都有自己的獨立內(nèi)存空間，都穿了衣服，不能相互亂看，要想通信就要接觸系統(tǒng)層面來通信，所以肯定就會造成較多的資源消耗和時間浪費。怎么整？

幾個進程為了方便，干脆商量一波，能不能開辟一塊內(nèi)存空間，共樂其中，這就是線程非常重要的意義，不過共享了不代表我們就是"裸"的，個人保密還是要做到，也不要吵架，可不可以通過鎖的方式保密呢，這就涉及到了線程的同步。這樣我猜測你應該了解進程和線程了吧。

2、簡單說下你對并發(fā)和并行的理解？

官話從概念出發(fā)：

• 并發(fā)

在一個時間段中多個程序都啟動運行在同一個處理機中

• 并行

假設(shè)目前A，B兩個進程，兩個進程分別由不同的 CPU ?管理執(zhí)行，兩個進程不搶占 CPU ?資源且可以同時運行，這叫做并行。

例子

并發(fā)是指多個任務在一段時間內(nèi)發(fā)生。比如今日成都某家老火鍋店做活動，全場5折(這還是比較狠)，但是只有200個位置，但是來的人太多了，來了250個人，此時多出的50個人只好等待著或者去另外家火鍋店。那么火鍋店老板對這250的安排不是同一時刻安排而是一段時間去處理，其實這就是并發(fā)。這個例子好像整的不算生動，我們再來一個

到了周末就是我們"開黑"的時光，奈何到了周一不遲到怎么對得起自己，但是遲到了被逮住就要被"BB"。好嘛，我們作為學生娃兒只好認慫，常規(guī)操作，兩腳一蹬，起床，刷牙，上廁所，拿包包沖。就是這樣類似復讀機的習慣操作是怎么回事？莫非我們就能同時干這么多事？其實不是的，我們大腦下達指令，起床，刷牙這些操作早形成了肌肉記憶，所以我們在這小段時間完成了這么多事兒，還可以多幾分鐘出來看看美女不香？

平時玩兒電腦的時候，邊寫代碼邊聽音樂，計算機同時處理了這么多任務。如果是單核 CPU ?，在我們看來這些事兒是同時發(fā)生的，其實那是因為底層 CPU ?切換的速度太快以致于我們完全感受不到它的切換，僅此為錯覺而已。但是如果是多核 ?CPU ? ?，各個 CPU ?負責不同的進程，各個進程不搶占 CPU ?，這樣同時進行，這就是真正意義上的并行。

說了這么多，那并行和并發(fā)到底啥區(qū)別？

兩者區(qū)別在于是否"同時"發(fā)生。是在一段時間同時發(fā)生還是多個事情在同一個時間點同時發(fā)生。

3、同步、異步、阻塞、非阻塞的概念

首先大家應該知道同步異步，阻塞非阻塞是兩個不同層面的問題，一個是operation層面，一個是kernal層面。同步異步最大的區(qū)別在于是否需要底層的響應再執(zhí)行。阻塞非阻塞最大的區(qū)別在于是否立即給出響應。

官話

同步：當一個同步調(diào)用發(fā)出后，調(diào)用者要一直等待返回結(jié)果。通知后，才能進行后續(xù)的執(zhí)行。

異步：當一個異步過程調(diào)用發(fā)出后，調(diào)用者不能立刻得到返回結(jié)果。實際處理這個調(diào)用的部件在完成后，通過狀態(tài)、通知和回調(diào)來通知調(diào)用者。

阻塞：是指調(diào)用結(jié)果返回前，當前線程會被掛起，即阻塞。

非阻塞：是指即使調(diào)用結(jié)果沒返回，也不會阻塞當前線程。

形象比喻：

• 小Q去釣魚，拋完線后就傻傻的看著有沒有動靜，有則拉桿(同步阻塞)

• 小Q去釣魚，拿魚網(wǎng)撈一下，有沒有魚立即知道，不用等，直接就撈(同步非阻塞)

• 小Q去釣魚，這個魚缸比較牛皮，扔了后自己就打王者榮耀去了，因為魚上鉤了這個魚缸帶的報警器會通知我。這樣實現(xiàn)異步(異步非阻塞）

4、進程和線程的相關(guān)題

官話：

• 進程：進程是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位，是系統(tǒng)中的并發(fā)執(zhí)行的單位。

• 線程：線程是進程的一個實體，也是 ?CPU ? 調(diào)度和分派的基本單位，它是比進程更小的能獨立運行的基本單位，有時又被稱為輕量級進程。

• 進程是資源分配的最小單位，而線程是 ** CPU ? 調(diào)度**的最小單位；

• 創(chuàng)建進程或撤銷進程，系統(tǒng)都要為之分配或回收資源，操作系統(tǒng)開銷遠大于創(chuàng)建或撤銷線程時的開銷；

• 不同進程地址空間相互獨立，同一進程內(nèi)的線程共享同一地址空間。一個進程的線程在另一個進程內(nèi)是不可見的；

• 進程間不會相互影響，而一個線程掛掉將可能導致整個進程掛掉；

別背了，我知道你們都會背，舉個例子

計算機中的核心是 CPU ?，說它是我們的大腦一點不為過。在此用一個連鎖火鍋店舉例，因為疫情的影響，今天到目前營業(yè)額一般，只好開一家店，其他疫情較為嚴重的店只好先關(guān)閉，這里涉及的含義：單個 CPU ?一次只運行一個任務。進程就類似這家火鍋店，它代表 CPU ?所能處理的單個任務，其他地方火鍋店只能處于非運行狀態(tài)。

一個火鍋店有很多服務員，一起協(xié)同工作，將火鍋店做的紅紅火火，那么線程就好比這些服務員，一個進程可有多個線程。、

火鍋店各個工作房間是共享的，所有服務員都可以進出，這意味著進程的內(nèi)存空間共享，每個線程都可以使用這些共享內(nèi)存。但是不是每個房間都可以容納相同的人數(shù)，比如衛(wèi)生間就只有一個人，其他人不能同時進去。這意味著一個線程在使用共享內(nèi)存的時候，其他線程需要等待結(jié)束才能使用這塊內(nèi)存。那怎么防止別人進入呢？很直接的辦法就是進去之后記得關(guān)門(上鎖)，上了鎖，其他人想進來發(fā)現(xiàn)是上鎖了，那就等鎖打開后再進去，這就叫做互斥鎖，防止多個線程同時讀寫某一塊內(nèi)存區(qū)域。

ok到這里，我們總結(jié)一波

• 如果以多進程的方式運行，那么允許多個任務同時運行

• 如果以多線程的方式運行，那么允許將單個任務分成不同的部分運行

• 為了防止進程/線程之間產(chǎn)生沖突和允許進程之間的共享資源，需要提供一種協(xié)調(diào)機制。

多線程與多進程的基本概念

不知道大家經(jīng)歷過食堂打菜的場景沒有，如果學校食堂就開設(shè)一個窗口，打菜的阿姨也沒辦法，只好一個個給大家依次打菜，這就好比"單線程",效率非常低(此處可以考慮為什么redis使用單線程卻這么牛逼)

為了提高效率，在食堂多加了幾個窗口，這就類似"多線程"形式。

那么又想起一個問題，“多線程一定就比單線程效率高麥？”（ps Memcache是多線程模型而Redis是單線程模型)

貌似我們一提到高并發(fā)，分布式，就不得不想起多線程，那么多線程一定比單線程效率高？

上面說了采用多線程多核效果更好，但是多線程對 CPU ?，內(nèi)存等都要求比較高，如果存在的上下文切換過于耗時，互斥時間太久，效率反而會低。

不一定。我不從專業(yè)術(shù)語來將，舉個例子，假設(shè)目前接水房有四個水管可以接水，我如果用4個桶分別對應4個水管，那么就比較完美，如果少一個則閑置一個，多一個則會出現(xiàn)搶占。如果此時我的水桶個數(shù)大于水管數(shù)，為了每個桶都有水，我們就需要切換水桶，這個過程實際上就是線程的上下文切換，代價一樣不小。

多線程與多進程的應用場景

多線程的優(yōu)點

• 更加高效的內(nèi)存共享。多進程下內(nèi)存共享不便

• 較輕的上下文切換。因為不用切換地址空間，CR3寄存器和清空TLB

多進程的優(yōu)點：

• 各個進程有自己內(nèi)存空間，所以具有更強的容錯性，不至于一個集成crash導致系統(tǒng)崩潰

• 具有更好的多核可伸縮性，因為進程將地址空間，頁表等進行了隔離，在多核的系統(tǒng)上可伸縮性更強

如何提升多線程的效率

• 盡量使用池化技術(shù)，也就是線程池，從而不用頻繁的創(chuàng)建，銷毀線程

• 減少線程之間的同步和通信

• 通過Huge Page的方式避免產(chǎn)生大量的缺頁異常

• 避免需要頻繁共享寫的數(shù)據(jù)

5、進程的狀態(tài)轉(zhuǎn)換

在Linux中，進程的狀態(tài)有七種

• 可運行狀態(tài)

英文名詞為TASK_RUNNING，其實這個狀態(tài)雖然是RUNING，實際上并不一定會占有 CPU ?，可能修改TASK_RUNABLE會更妥當。TASK_RUNGING根據(jù)是否在在 CPU ?上運行分為RUNGING和READY兩種狀態(tài)。處于READY狀態(tài)的進程隨時可以運行，只不過因為此時 CPU ?資源受限，調(diào)度器沒選中運行

• 可中斷睡眠狀態(tài)與不可中斷睡眠狀態(tài)

我們知道進程不可能一直處于可運行的狀態(tài)。假設(shè)A進程需要讀取磁盤中的文件，這樣的系統(tǒng)調(diào)用消耗時間較長，進程需要等待較長的時間才能執(zhí)行后面的命令，而且等待的時間還是不可估算的，這樣的話進程還占用 CPU ?就不友好了，因此內(nèi)核就會將其更改為其他的狀態(tài)并從 CPU ?可運行的隊列移除。

Linux中存在兩種睡眠狀態(tài)，分別為：可中斷的睡眠狀態(tài)和不可中斷的狀態(tài)。兩者最大的區(qū)別為是否響應收到的信號，那么從可中斷的睡眠的進程是如何返回到可運行的狀態(tài)呢

• 等待的事情發(fā)生且繼續(xù)運行的條件滿足

• 收到了沒有被屏蔽的信號

處于此狀態(tài)的進程，收到信號會返回EINTR給用戶空間。開發(fā)者通過檢測返回值的方式進行后續(xù)邏輯處理

但是對于不可中斷的睡眠狀態(tài)，就只有一種方式返回到可運行狀態(tài)，即等待事情發(fā)生了繼續(xù)運行

上圖中為什么出現(xiàn)個 TASK_UNINTERRUPTIBLE 狀態(tài)，主要是因為內(nèi)核中的進程不是什么進程都可以被打斷，假設(shè)響應的是異步信號，程序在執(zhí)行的過程中插入一段用于處理異步信號的而流程，原來的流程就會被中斷。所以當進程在和硬件打交道的時候，需要使用 TASK_UNINTERRUPTIBLE 狀態(tài)將進程保護起來，從而避免進程和設(shè)備打交道的過程中被打斷導致設(shè)備處于不可控的狀態(tài)。

那么TASK_UNINTERRUPTIBLE狀態(tài)會出現(xiàn)多久呢？

其實 TASK_UNINTERRUPTIBLE 狀態(tài)是很危險的狀態(tài)，因為它刀槍不入，你無法通過信號殺死這樣一個不可中斷的休眠狀態(tài)，正常情況，TASK_UNINTERRUPTIBLE狀態(tài)存在時間很短，但是不排除存在此狀態(tài)進程比較持久的情況，真的刀槍不入了？可不可以進行提前的預防？

可以的，早就考慮了。內(nèi)核提供了hung task機制，它會啟動一個khungtaskd內(nèi)核線程對TASK_UNINTERRUPTIBLE狀態(tài)進行檢測，不能讓他失控了。khungtaskd會定期的喚醒，如果超過120s都還沒有調(diào)度，內(nèi)核就會通過打印警告和堆棧信息。當然，不一定就是120s，可以通過下面選項進行定制

sysctl?kernel.hung_task_timeout_secs

說了這么多，我們怎么知道到底有沒有出現(xiàn)這個狀態(tài)，哪里看？可以通過/proc和ps進行查看

• 睡眠進程和等待隊列

不管是上面提到的可中斷的睡眠進程還是不可中斷的睡眠進程，都離不開一種數(shù)據(jù)結(jié)構(gòu)---隊列。哦？假設(shè)進程A因為某某原因需要休眠，為啥要休眠，等待的資源遲遲拿不到或者等待的事件總是不來，沒法進行下一步操作，這個時候內(nèi)核來了，"行吧，我不會拋棄你，我一定會想辦法讓你和等待的資源(事件)扯上關(guān)系"，只要等待的時機到來我就喚醒你，這采用的方法即"等待隊列"。如果進一步深究，想了解它的底層實現(xiàn)(采用了雙向鏈表)，文末我會給大家推薦基本書籍。

• TASK_STOPPED狀態(tài)于TASK_TRACED狀態(tài)

TASK_STOPPED狀態(tài)屬于比較特殊的狀態(tài)，可以通過SIGCONT信號回復進程的執(zhí)行

TASK_TRACED是被跟蹤的狀態(tài)，進程會停下來等待跟蹤它的進程對它進行進一步的操作

• EXIT_ZOMBIE狀態(tài)與EXIT_DEAD狀態(tài)

當進程儲于這兩種的任意一種，就可以宣布"死亡" 。

就緒 —> 執(zhí)行：準備就緒，調(diào)度器滿足了的需求，給我一種策略，我就可從就緒變?yōu)閳?zhí)行的狀態(tài)；

執(zhí)行 —> 阻塞：不是每個進程都是那么一帆風順，就像我們每次考試，不管是中考，高考還是考研，難免都會出現(xiàn)磕磕盼盼，遇到了可能暫時會阻擋我們前行的小事兒，可是要相信不會一直的阻擋我們，只要我們有恒心堅持，時機到來，你也準備好了，那就美哉。回到這里，對于進程而言，當需要等到某個事情發(fā)生而無法執(zhí)行的時候，進程就變?yōu)?strong style="font-size: inherit;line-height: inherit;color: rgb(255, 69, 0);">阻塞的狀態(tài)。比如當前進程提出輸入請求，如進程提出輸入/輸出請求，進程所申請資源（主存空間或外部設(shè)備）得不到滿足時變成等待資源狀態(tài)，進程運行中出現(xiàn)了故障（程序出錯或主存儲器讀寫錯等）變成等待干預狀態(tài)等等；

阻塞 —> 就緒：處于阻塞狀態(tài)的進程，在其等待的事件已經(jīng)發(fā)生，如輸入/輸出完成，資源得到滿足或錯誤處理完畢時，處于等待狀態(tài)的進程并不馬上轉(zhuǎn)入執(zhí)行狀態(tài)，而是先轉(zhuǎn)入就緒狀態(tài)，然后再由系統(tǒng)進程調(diào)度程序在適當?shù)臅r候?qū)⒃撨M程轉(zhuǎn)為執(zhí)行狀態(tài)；

執(zhí)行 —> 就緒：正在執(zhí)行的進程，因時間片用完而被暫停執(zhí)行，或在采用搶先式優(yōu)先級調(diào)度算法的系統(tǒng)中,當有更高優(yōu)先級的進程要運行而被迫讓出處理機時，該進程便由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)榫途w狀態(tài)。

6、進程間的通信方式有哪些？

管道

學習軟件工程規(guī)范的時候，我們知道瀑布模型，在整個項目開發(fā)過程分為多個階段，上一階段的輸出作為下一階段的輸入。各個階段的具體內(nèi)容如下圖所示

最初我們在學習Linux基本命令使用的時候，我們經(jīng)常通過多個命令的組合來完成我們的需求。比如說我們想知道如何查看進程或者端口是否在使用，會使用下面的這條命令

netstat -nlp | grep XXX

這里的"|"實際上就是管道的意思。"|"前面部分作為"|"后面的輸入，很明顯是單向的傳輸，這樣的管道我們叫做"匿名管道"，自行創(chuàng)建和銷毀。既然有匿名管道，應該就有帶名字的管道"命名管道"。如果你想雙向傳輸，可以考慮使用兩個管道拼接即可。

創(chuàng)建命名管道的方式

mkfifo test

test即為管道的名稱，在Linux中一切皆文件，管道也是以文件的方式存在，咋們可以使用ls -l 查看下文件的屬性，它會"p"標識。

下面我們向管道寫入內(nèi)容

echo "666" > test

此時按道理來說咋們已經(jīng)將內(nèi)容寫入了test，沒有直接輸出是因為我們需要開啟另一個終端進行輸出(可以理解為暫存管道)

cat < test

ok，我們發(fā)現(xiàn)管道內(nèi)容被讀出來，同時echo退出。那么管道這種通信方式有什么缺點？我們知道瀑布模型的軟件開發(fā)模式是非常低下的，同理采用管道進行通信的效率也很低，因為假設(shè)現(xiàn)在有AB兩個進程，A進程將數(shù)據(jù)寫入管道，B進程需要等待A進程將信息寫完以后才能讀出來，所以這種方案不適合頻繁的通信。那優(yōu)點是什么？

最明顯的優(yōu)點就是簡單，我們平時經(jīng)常使用以致于都不知道這是管道。鑒于上面的缺點，我們怎么去彌補呢？接著往下看

消息隊列

管道通信屬于一股腦的輸入，能不能稍微溫柔點有規(guī)矩點的發(fā)送消息？

答：可以的。消息隊列在發(fā)送數(shù)據(jù)的時候，按照一個個獨立單元(消息體)進行發(fā)送，其中每個消息體規(guī)定大小塊，同時發(fā)送方和接收方約定好消息類型或者正文的格式。

在管道中，其大小受限且只能承載無格式字節(jié)流的方式，而消息隊列允許不同進程以消息隊列的形式發(fā)送給任意的進程。

但是當發(fā)送到消息隊列的數(shù)據(jù)太大，需要拷貝的時間也就越多，所以還有其他的方式？繼續(xù)看

共享內(nèi)存

使用消息隊列可以達到不錯的效果，但是如果我們兩個部門需要交換比較大的數(shù)據(jù)的時候，一發(fā)一收還是不能及時的感知數(shù)據(jù)。能不能更好的辦法，雙方能很快的分享內(nèi)容數(shù)據(jù)，答：有的，共享內(nèi)存

我們知道每個進程都有自己的虛擬內(nèi)存空間，不同的進程映射到不同的物理內(nèi)存空間。那么我們可不可以申請一塊虛擬地址空間，不同進程通過這塊虛擬地址空間映射到相同的屋里地址空間呢？這樣不同進程就可以及時的感知進程都干了啥，就不需要再拷貝來拷貝去。

我們可以通過shmget創(chuàng)建一份共享內(nèi)存，并可以通過ipcs命令查看我們創(chuàng)建的共享內(nèi)存。此時如果一個進程需要訪問這段內(nèi)存，需要將這個內(nèi)存加載到自己虛擬地址空間的一個位置，讓內(nèi)核給它一個合法地址。使用完畢接觸板頂并刪除內(nèi)存對象。

那么問題來了，這么多進程都共享這塊內(nèi)存，如果同時都往里面寫內(nèi)容，難免會出現(xiàn)沖突的現(xiàn)象，比如A進程寫了數(shù)字5，B進程同樣的地址寫了6就直接給覆蓋了，這樣就不友好了，怎么辦？繼續(xù)往下看

信號量

為了防止沖突，我們得有個約束或者說一種保護機制。使得同一份共享的資源只能一個進程使用，這里就出現(xiàn)了信號量機制。

信號量實際上是一個計數(shù)器，這里需要注意下，信號量主要實現(xiàn)進程之間的同步和互斥，而不是存儲通信內(nèi)容。

信號量定義了兩種操作，p操作和v操作，p操作為申請資源，會將數(shù)值減去M，表示這部分被他使用了，其他進程暫時不能用。v操作是歸還資源操作，告知歸還了資源可以用這部分。

信號

從管道----消息隊列-共享內(nèi)存/信號量，有需要等待的管道機制，共享內(nèi)存空間的進程通信方式，還有一種特殊的方式--信號

我們或許聽說過運維或者部分開發(fā)需要7 * 24小時值守(項目需要上線的時候)，當然也有各種監(jiān)管，告警系統(tǒng)，一旦出現(xiàn)系統(tǒng)資源緊張等問題就會告知開發(fā)或運維人員，對應到操作系統(tǒng)中，這就是信號。

在操作系統(tǒng)中，不同信號用不同的值表示，每個信號設(shè)置相應的函數(shù)，一旦進程發(fā)送某一個信號給另一個進程，另一進程將執(zhí)行相應的函數(shù)進行處理。也就是說把可能出現(xiàn)的異常等問題準備好，一旦信號產(chǎn)生就執(zhí)行相應的邏輯即可。

套接字

上面的幾種方式都是單機情況下多個進程的通信方式，如果我想和相隔幾千里的小姐姐通信怎么辦？

這就需要套接字socket了。其實這玩意隨處可見，我們平時的聊天，我們天天請求瀏覽器給予的響應等，都是這老鐵。

小結(jié)

分享了一下幾種進程間通信方式，希望大家能知其然并知其所以然，機械式的記憶容易忘記哦。

• 管道

• 消息隊列

• 共享內(nèi)存

• 信號量

• 信號

• 套接字

7、進程的調(diào)度算法有哪些？

調(diào)度算法是指：調(diào)度程序是內(nèi)核的重要組成部分，決定這下一個要運行的進程。那么根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法。常用的調(diào)度算法有：先來先服務調(diào)度算法、時間片輪轉(zhuǎn)調(diào)度法、短作業(yè)優(yōu)先調(diào)度算法、最短剩余時間優(yōu)先、高響應比優(yōu)先調(diào)度算法、優(yōu)先級調(diào)度算法等等。

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

先來先服務讓我們想起了隊列的先進先出特性，每一次的調(diào)度都從隊列中選擇最先進入隊列的投入運行。

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

先來理解輪轉(zhuǎn)，假設(shè)當前進程A、B、C、D，按照進程到達的時間排序，而且每個進行都有著同樣大小的時間片。如果這個進程在當前的時間片運行結(jié)束，啥事兒沒有，直接將進程從隊列移除完事兒。如果進程在這個時間片跑完都沒有結(jié)束，進程變?yōu)榈却隣顟B(tài)，放在進程尾部直到所有進程執(zhí)行完畢。

為什么進程要切換，切換無外乎是時間片夠用或者不夠用。如果時間片夠用，那么進程可以運行到結(jié)束，結(jié)束后刪除啟動新的時間片。如果時間片不夠用，對不起，暫時只能完成一部分任務(變?yōu)榈却隣顟B(tài))，過后再等待 CPU ?的調(diào)度。網(wǎng)上開源的代碼太多，怎么實現(xiàn)，大家可以參照加深影響。

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

短作業(yè)優(yōu)先調(diào)度算法，從名稱可以清晰的知道「短作業(yè)」意味著執(zhí)行時間比較短，「優(yōu)先」代表執(zhí)行順序。結(jié)合就是"短者吃香"。那么多短吃香？進程不可能都短，也有需要執(zhí)行時間比較長的進程怎么辦？一直等待，直到餓死麥？而且有些進程比較緊急，能夠得到先執(zhí)行？這些都是此算法所出現(xiàn)的問題，然后出現(xiàn)下面的一些算法

• 最短剩余時間優(yōu)先調(diào)度算法

最短剩余時間是針對最短進程優(yōu)先增加了搶占機制的版本。在這種情況下，進程調(diào)度總是選擇預期剩余時間最短的進程。當一個進程加入到就緒隊列時，他可能比當前運行的進程具有更短的剩余時間，因此只要新進程就緒，調(diào)度程序就能可能搶占當前正在運行的進程。像最短進程優(yōu)先一樣，調(diào)度程序正在執(zhí)行選擇函數(shù)是必須有關(guān)于處理時間的估計，并且存在長進程饑餓的危險。

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

什么是高響應比，有響應之前應該會有請求，相當于是請求+響應+優(yōu)先，算是一種綜合的調(diào)度算法。也就是它結(jié)合了短作業(yè)優(yōu)先，先來先服務以及長作業(yè)的一些特性。ok，那么這三種是如何體現(xiàn)出來的

首先來說短作業(yè)優(yōu)先。等待時間我們假設(shè)相等，服務時間很短，這樣的話短作業(yè)就會有更高的優(yōu)先權(quán)。

再來看先來先服務。假設(shè)服務時間相同，先來的自然等待時間較長，優(yōu)先級越高。

上面說長作業(yè)很可能因為等待時間過長，容易餓死。在這里不會，仿佛像醫(yī)生的這個職業(yè)，工作越久資歷越老，優(yōu)先級越來越高，越來越吃香

• 優(yōu)先級調(diào)度算法

優(yōu)先級調(diào)度算法每次從后備作業(yè)隊列中選擇優(yōu)先級最髙的一個或幾個作業(yè)，將它們調(diào)入內(nèi)存，分配必要的資源，創(chuàng)建進程并放入就緒隊列。在進程調(diào)度中，優(yōu)先級調(diào)度算法每次從就緒隊列中選擇優(yōu)先級最高的進程，將處理機分配給它，使之投入運行。

8、什么是死鎖？

死鎖，顧名思義就是導致線程卡死的鎖沖突，例如下面的這種情況

線程 1 已經(jīng)成功拿到了互斥量 1 ，正在申請互斥量 2 ，而同時在另一個 ?CPU ? 上，線程 2 已經(jīng)拿到了互
斥量 2 ，正在申請互斥量 1 。彼此占有對方正在申請的互斥量，結(jié)局就是誰也沒辦法拿到想要的互斥
量，于是死鎖就發(fā)生了。

稍微復雜一點的情況

存在多個互斥量的情況下，避免死鎖最簡單的方法就是總是按照一定的先后順序申請這些互斥
量。還是以剛才的例子為例，如果每個線程都按照先申請互斥量 1 ，再申請互斥量 2 的順序執(zhí)行，死鎖
就不會發(fā)生。有些互斥量有明顯的層級關(guān)系，但是也有一些互斥量原本就沒有特定的層級關(guān)系，不過
沒有關(guān)系，可以人為干預，讓所有的線程必須遵循同樣的順序來申請互斥量

9、產(chǎn)生死鎖的原因？

由于系統(tǒng)中存在一些不可剝奪資源，而當兩個或兩個以上進程占有自身資源，并請求對方資源時，會導致每個進程都無法向前推進，這就是死鎖。

• 競爭資源

例如：系統(tǒng)中只有一臺打印機，可供進程 A 使用，假定 A 已占用了打印機，若 B 繼續(xù)要求打印機打印將被阻塞。

系統(tǒng)中的資源可以分為兩類：

1. 可剝奪資源：是指某進程在獲得這類資源后，該資源可以再被其他進程或系統(tǒng)剝奪， CPU ? 和主存均屬于可剝奪性資源；

2. 不可剝奪資源，當系統(tǒng)把這類資源分配給某進程后，再不能強行收回，只能在進程用完后自行釋放，如磁帶機、打印機等。

• 進程推進順序不當

例如：進程 A 和 進程 B 互相等待對方的數(shù)據(jù)。

10、死鎖產(chǎn)生的必要條件？

互斥

要求各個資源互斥，如果這些資源都是可以共享的，那么多個進程直接共享即可，不會存在等待的尷尬場景

非搶占

要求進程所占有的資源使用完后主動釋放即可，其他的進程休想搶占這些資源。原因很簡單，如果可以搶占，直接拿就好了，不會進入尷尬的等待場景

要求進程是在占有（holding）至少一個資源的前提下，請求（waiting）新的資源的。由于新的資源被其它進程占有，此時，發(fā)出請求的進程就會帶著自己占有的資源進入阻塞狀態(tài)。假設(shè) P1，P2 分別都需要 R1，R2 資源，如果是下面這種方式：

P1:??????????P2:
request(R1)??request(R2)
request(R2)??request(R1)?

?

如果 P1 請求到了 R1 資源之后，P2 請求到了 R2 資源，那么此后不管是哪個進程再次請求資源，都是在占有資源的前提下請求的，此時就會帶著這個資源陷入阻塞狀態(tài)。P1 和 P2 需要互相等待，發(fā)生了死鎖。

換一種情況：

P1:??????????P2:
request(R1)??request(R1)
request(R2)??request(R2)?

?

如果 P1 請求到了 R1 資源，那么 P2 在請求 R1 的時候雖然也會阻塞，但是是在不占有資源的情況下阻塞的，不像之前那樣占有 R2。所以，此時 P1 可以正常完成任務并釋放 R1，P2 拿到 R1 之后再去執(zhí)行任務。這種情況就不會發(fā)生死鎖。

• 循環(huán)等待

要求存在一條進程資源的循環(huán)等待鏈，鏈中的每一個進程占有的資源同時被另一個進程所請求。

發(fā)生死鎖時一定有循環(huán)等待（因為是死鎖的必要條件），但是發(fā)生循環(huán)等待的時候不一定會發(fā)生死鎖。這是因為，如果循環(huán)等待鏈中的 P1 和 鏈外的 P6 都占有某個進程 P2 請求的資源，那么 P2 完全可以選擇不等待 P1 釋放該資源，而是等待 P6 釋放資源。這樣就不會發(fā)生死鎖了。

11、解決死鎖的基本方法？

如果我們已經(jīng)知道死鎖形成的必要條件，逐一攻破即可。

• 破壞互斥

通過與鎖完全不同的同步方式CAS，CAS提供原子性支持，實現(xiàn)各種無鎖的數(shù)據(jù)結(jié)構(gòu)，不僅可以避免互斥鎖帶來的開銷也可避免死鎖問題。

• 破壞不搶占

如果一個線程已經(jīng)獲取到了一些鎖，那么在這個線程釋放鎖之前這些鎖是不會被強制搶占的。但是為了防止死鎖的發(fā)生，我們可以選擇讓線程在獲取后續(xù)的鎖失敗時主動放棄自己已經(jīng)持有的鎖并在之后重試整個任務，這樣其他等待這些鎖的線程就可以繼續(xù)執(zhí)行了。這樣就完美了嗎？當然不

這種方式雖然可以在一定程度上避免死鎖，但是如果多個相互存在競爭的線程不斷的放棄重啟放棄循環(huán)，就會出現(xiàn)活鎖的問題，此時線程雖然沒有因為鎖沖突被卡死，但是仍然會因為阻塞時間太長處于重試當中。怎么辦？

方案1：給任務重試部分增加隨機延遲時間，降低任務沖突的概率

• 破壞環(huán)路等待

在實踐的過程中，采用破壞環(huán)路等待的方式非常常見，這種技術(shù)叫做"鎖排序"。很好理解，我們假設(shè)現(xiàn)在有個數(shù)組A，采用單向訪問的方式(從前往后)，依次訪問并加鎖，這樣一來，線程只會向前單向等待鎖釋放，自然也就無法形成一個環(huán)路了。

說到這里，我想說死鎖不僅僅出現(xiàn)在多線程編程領(lǐng)域，在數(shù)據(jù)庫的訪問也是非常的常見，比如我們需要更新數(shù)據(jù)庫的幾行數(shù)據(jù)，就得先獲取這些數(shù)據(jù)的鎖，然后通過排序的方式阻止數(shù)據(jù)層發(fā)生死鎖。

這樣就完美了？當然沒有，那會出現(xiàn)什么問題？

這種方案也存在它的缺點，比如在大型系統(tǒng)當中，不同模塊直接解耦和隔離得非常徹底，不同模塊開發(fā)人員不清楚其細節(jié)，在這樣的情況下就很難做到整個系統(tǒng)層面的全局鎖排序了。在這種情況下，我們可以對方案進行擴充，例如Linux在內(nèi)存映射代碼就使用了一種鎖分組排序的方式來解決這個問題。鎖分組排序首先按模塊將鎖分為了不同的組，每個組之間定義了嚴格的加鎖順序，然后再在組內(nèi)對具體的鎖按規(guī)則進行排序，這樣就保證了全局的加鎖順序一致。在Linux的對應的源碼頂部，我們可以看到有非常詳盡的注釋定義了明確的鎖排序規(guī)則。

這種解決方案如果規(guī)模過大的話即使可以實現(xiàn)也會非常的脆弱，只要有一個加鎖操作沒有遵守鎖排序規(guī)則就有可能會引發(fā)死鎖。不過在像微服務之類解耦比較充分的場景下，只要架構(gòu)拆分合理，任務模塊盡可能小且不會將加鎖范圍擴大到模塊之外，那么鎖排序?qū)⑹且环N非常實用和便捷的死鎖阻止技術(shù)

12、怎么預防死鎖？

破壞請求條件：一次性分配所有資源，這樣就不會再有請求了；

破壞請保持條件：只要有一個資源得不到分配，也不給這個進程分配其他的資源：

破壞不可剝奪條件：當某進程獲得了部分資源，但得不到其它資源，則釋放已占有的資源；

破壞環(huán)路等待條件：系統(tǒng)給每類資源賦予一個編號，每一個進程按編號遞增的順序請求資源，釋放則相反。

13、怎么避免死鎖？

• 銀行家算法

當進程首次申請資源時，要測試該進程對資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當前的申請量分配資源，否則就推遲分配。

當進程在執(zhí)行中繼續(xù)申請資源時，先測試該進程已占用的資源數(shù)與本次申請資源數(shù)之和是否超過了該進程對資源的最大需求量。若超過則拒絕分配資源。若沒超過則再測試系統(tǒng)現(xiàn)存的資源能否滿足該進程尚需的最大資源量，若滿足則按當前的申請量分配資源，否則也要推遲分配。

• 安全序列

是指系統(tǒng)能按某種進程推進順序（P1, P2, P3, …, Pn），為每個進程 Pi 分配其所需要的資源，直至滿足每個進程對資源的最大需求，使每個進程都可以順序地完成。這種推進順序就叫安全序列【銀行家算法的核心就是找到一個安全序列】。

• 系統(tǒng)安全狀態(tài)

如果系統(tǒng)能找到一個安全序列，就稱系統(tǒng)處于安全狀態(tài)，否則，就稱系統(tǒng)處于不安全狀態(tài)。

14、怎么解除死鎖？

• 資源剝奪：掛起某些死鎖進程，并搶占它的資源，將這些資源分配給其他死鎖進程（但應該防止被掛起的進程長時間得不到資源）；

• 撤銷進程：強制撤銷部分、甚至全部死鎖進程并剝奪這些進程的資源（撤銷的原則可以按進程優(yōu)先級和撤銷進程代價的高低進行）；

• 進程回退：讓一個或多個進程回退到足以避免死鎖的地步。進程回退時自愿釋放資源而不是被剝奪。要求系統(tǒng)保持進程的歷史信息，設(shè)置還原點。

15、什么是緩沖區(qū)溢出？有什么危害？

官話

緩沖區(qū)溢出是指當計算機向緩沖區(qū)內(nèi)填充數(shù)據(jù)時超過了緩沖區(qū)本身的容量，溢出的數(shù)據(jù)覆蓋在合法數(shù)據(jù)上

舉個例子

一個兩升的杯子，你如果想導入三升，怎么做？其他一生只好流出去，不是打濕了電腦就是那啥。

16、物理地址、邏輯地址、線性地址

• 物理地址：它是地址轉(zhuǎn)換的最終地址，是內(nèi)存單元真正的地址。如果采用了分頁機制，那么線性地址會通過頁目錄和頁表得方式轉(zhuǎn)換為物理地址。如果沒有啟用則線性地址即為物理地址

• 邏輯地址：在編寫c語言的時候，通過&操作符可以讀取指針變量本省得值，這個值就是邏輯地址。實際上是當前進程得數(shù)據(jù)段得地址，和真實的物理地址沒有關(guān)系。只有當在Intel實模式下，邏輯地址==物理地址。我們平時的應用程序都是通過和邏輯地址打交道，至于分頁，分段機制對他們而言是透明得。邏輯地址也稱作虛擬地址

• 線性地址：線性地址是邏輯地址到物理地址的中間層。我們編寫的代碼會存在一個邏輯地址或者是段中得偏移地址，通過相應的計算(加上基地址)生成線性地址。此時如果采用了分頁機制，那么吸納行地址再經(jīng)過變換即產(chǎn)生物理地址。在Intelk 80386中地址空間容量為4G，各個進程地址空間隔離，意味著每個進程獨享4G線性空間。多個進程難免出現(xiàn)進程之間的切換，線性空間隨之切換?；诜猪摍C制，對于4GB的線性地址一部分會被映射到物理內(nèi)存，一部分映射到磁盤作為交換文件，一部分沒有映射，通過下面加深一下印象

17、分頁與分段的區(qū)別？

我們知道計算機的五大組成部分分別為運算器，存儲器，存儲器 ，輸入和輸出設(shè)備。我們的數(shù)據(jù)或者指定都需要存放內(nèi)存然后給 CPU ?大哥拿去執(zhí)行。我們平時寫的代碼不是直接操作的物理地址，我們所看到的地址實際上叫做虛擬地址，通過相應的轉(zhuǎn)換規(guī)則將虛擬地址轉(zhuǎn)換為物理地址。

那么虛擬地址是怎么轉(zhuǎn)換為物理地址的呢？

第一種方式，采用一個映射表代表虛擬地址到物理地址的映射，在計算機中我們叫做頁表。頁表將內(nèi)存地址分為頁號和偏移量，舉個例子

我們將高位部分稱為內(nèi)存地址的頁號，后面的低位叫做內(nèi)存地址的偏移量。我們只需要保存虛擬地址內(nèi)存的頁號和物理內(nèi)存頁號之間的映射關(guān)系即可。

這樣說了，也就是三部曲

• 虛擬地址-----> 頁號+偏移量

• 通過頁表查詢出虛擬頁號，對應的物理頁號

• 物理頁號+偏移量-----> 物理內(nèi)存地址

這樣的方法，在32位的內(nèi)存地址，頁表需要多大的空間？

在一個32位的內(nèi)存地址空間，頁表需要記錄2^20個物理頁面的映射關(guān)系，可以想象為要給數(shù)組。那么一個頁號是完整的4字節(jié)。這樣一個頁表就是4MB。

再來，我們知道進程有各自的虛擬內(nèi)存空間，也就是說每個進程都需要一個這樣的頁表，不管此進程是只有幾KB的程序還是需要GB的內(nèi)存空間都需要這樣的頁表，用這樣的結(jié)構(gòu)保存頁面，內(nèi)存的占用將非常的大，那其他方式是怎么樣的呢

多級頁表

同樣的虛擬內(nèi)存地址，偏移量部分和上面方式一樣，但是我們將頁號部分拆分為四段，從高到低分成4級到1級的4個頁表索引

這樣一來，每個進程將有4級頁表。通過4級頁表的索引找到對應的條目。通過這個條目找到3級頁表所在位置，4級的每一個條目可能有多個3級的條目，找到了3級的條目后找到對應3級索引的條目，就這樣到達1級頁表。1級對應的則為物理頁號。最終通過物理頁號+偏移量的方式獲取物理內(nèi)存地址。

18 為什么使用多級頁表

• 使用多級頁表可以讓頁表在內(nèi)存中離散存儲。多級頁表通過索引就可以定位到具體的項。舉個例子，假設(shè)當前虛擬地址空間為4G，每個頁的大小為4k，如果是一級頁表的話，共有2……20個頁表項，假設(shè)每個頁表項需要4B，那么存放所有的頁表項需要4M，那么為了隨機訪問，我們就需要連續(xù)的4M內(nèi)存空間存放所有的頁表項。這樣一來，隨著虛擬地址空間的增大，需要存放頁表所需的連續(xù)空間也就越來多大。如果使用多級頁表，我們只需要一頁存放目錄項，頁表存放在內(nèi)存其他位置即可，下面有例子進一步講解

• 使用多級頁表更加節(jié)省頁表內(nèi)存。理論上，使用一級頁表，需要連續(xù)存儲空間存放所有項。使用多級頁表只需要給實際使用的的那些虛擬地址內(nèi)存的請求分配內(nèi)存

舉個例子

假設(shè)虛擬地址空間為4G，A進程只是用 4M 的內(nèi)存空間。對于一級頁表，我們需要 4M 空間存放這4GB 虛擬地址對應的頁表，然后找到進程真正的 4M 內(nèi)存空間。這樣的話，A進程本來只使用 4MB 內(nèi)存空間，但是為了訪問它，我們需要為所有的虛擬地址空間建立頁表，豈不是很浪費。對于二級頁表而言，使用一個頁目錄就可定位 4M 的內(nèi)存，存放一個頁目錄項需要 4k，還需要一頁存放進程使用的 4M，4M=1024*4k，也就相當于 1024 個頁表項就可以映射4M的內(nèi)存空間，那么總共就只需要4k(頁表)+4k(頁目錄)=8k來存放進程需要的 4M 內(nèi)存空間對應頁表和頁目錄項。這樣看來確實剩下不少的內(nèi)存。

那使用多級頁表有啥缺點？

還是有的，咋們使用一級頁表的時候，只需要訪問兩次內(nèi)存，一次是訪問頁表項，一次是訪問需要讀取的一頁數(shù)據(jù)。如果是二級頁表，就需要訪問三次，第一次訪問頁目錄，第二次訪問頁表項，第三次訪問讀取的數(shù)據(jù)。訪問次數(shù)的增加以為訪問數(shù)據(jù)所花費的總時間也增加

19、頁面置換算法有哪些？

請求調(diào)頁，也稱按需調(diào)頁，即對不在內(nèi)存中的“頁”，當進程執(zhí)行時要用時才調(diào)入，否則有可能到程序結(jié)束時也不會調(diào)入。而內(nèi)存中給頁面留的位置是有限的，在內(nèi)存中以幀為單位放置頁面。為了防止請求調(diào)頁的過程出現(xiàn)過多的內(nèi)存頁面錯誤（即需要的頁面當前不在內(nèi)存中，需要從硬盤中讀數(shù)據(jù)，也即需要做頁面的替換）而使得程序執(zhí)行效率下降，我們需要設(shè)計一些頁面置換算法，頁面按照這些算法進行相互替換時，可以盡量達到較低的錯誤率。常用的頁面置換算法如下：

• 先進先出置換算法（FIFO）

先進先出，即淘汰最早調(diào)入的頁面。

• 最佳置換算法（OPT）

選未來最遠將使用的頁淘汰，是一種最優(yōu)的方案，可以證明缺頁數(shù)最小。

• 最近最久未使用（LRU）算法

即選擇最近最久未使用的頁面予以淘汰

• 時鐘（Clock）置換算法

時鐘置換算法也叫最近未用算法 NRU（Not RecentlyUsed）。該算法為每個頁面設(shè)置一位訪問位，將內(nèi)存中的所有頁面都通過鏈接指針鏈成一個循環(huán)隊列。。

20 書籍/視頻學習推薦

書籍

• Linux內(nèi)核設(shè)計與實現(xiàn)

• 操作系統(tǒng)導論

• 現(xiàn)代操作系統(tǒng)

• 深入理解操作系統(tǒng)

視頻

• B站 ----哈工大李志軍老師講解

https://www.bilibili.com/video/av17036347/