面試的頻操過程中,為了考察面試者的作系基礎功力,除了算法以外,統面操作系統將會占比很大的小故權重,本文給大家分享我在面試過程中出現的事揭試題非常高頻的面試題,我基本上會從兩個角度來闡述,秘高一個是"官話",一個是“大白話”。希望對即將面試的你有所幫助
1、為什么有了進程,還要有線程呢?
為了提高系統資源的利用率和系統的吞吐量,通常進程可讓多個程序并發的執行,但是也會帶來一些問題
官話
進程如果在執行的過程被阻塞,那這個進程將被掛起,這時候進程中有些等待的資源得不到執行:
進程在同一時間只能做一件事兒
基于以上的缺點,操作系統引入了比進程粒度更小的線程,作為并發執行的基本單位,從而減少程序在并發執行時所付出的時間和空間開銷,提高并發性能。
舉個例子
小Q當年開發了一個聊天軟件,給女朋友說:咋們以后不用什么qq,微信了,我寫個聊天工具,咱兩正兒八經的兩人世界可好。
說干就干,小Q很快就完成了開發,然后開始測試,打電話讓女朋友讓她發個信息,小Q就等著,等啊等啊,怎么還沒有發信息過來,沒顯示啊,一臉懵逼,單步調試吧,發現程序卡在了wati for user input不動了。牛逼,程序不輸入就沒辦法執行后面的任務。咋搞?要不設置個1s,用戶1s不輸入直接跳過進行后面的接收階段和顯示階段,牛皮牛皮,果然好使,好使個錘錘,這樣用戶輸入信息不就很可能丟失,咋搞?
能不能將輸入和顯示這兩個動作給分開,一個負責輸入,發送消息,一個負責讀信息和顯示。不夸夸你自己嗎,直接開干呈現兩個窗口。
回來回來,這就是我們的多進程。不過多進程也還是有些問題需要注意,開多個窗口沒問題,無腦開窗口撩騷直接被榨干(內存耗盡),而且想要幾個窗口交換個數據也是賊麻煩,這是為啥呢
多進程的程序,每個進程都有自己的獨立內存空間,都穿了衣服,不能相互亂看,要想通信就要接觸系統層面來通信,所以肯定就會造成較多的資源消耗和時間浪費。怎么整?
幾個進程為了方便,干脆商量一波,能不能開辟一塊內存空間,共樂其中,這就是線程非常重要的意義,不過共享了不代表我們就是"裸"的,個人保密還是要做到,也不要吵架,可不可以通過鎖的方式保密呢,這就涉及到了線程的同步。這樣我猜測你應該了解進程和線程了吧。
2、簡單說下你對并發和并行的理解?
官話從概念出發:
并發
在一個時間段中多個程序都啟動運行在同一個處理機中
并行
假設目前A,B兩個進程,兩個進程分別由不同的 CPU ?管理執行,兩個進程不搶占 CPU ?資源且可以同時運行,這叫做并行。
例子
并發是指多個任務在一段時間內發生。比如今日成都某家老火鍋店做活動,全場5折(這還是比較狠),但是只有200個位置,但是來的人太多了,來了250個人,此時多出的50個人只好等待著或者去另外家火鍋店。那么火鍋店老板對這250的安排不是同一時刻安排而是一段時間去處理,其實這就是并發。這個例子好像整的不算生動,我們再來一個
到了周末就是我們"開黑"的時光,奈何到了周一不遲到怎么對得起自己,但是遲到了被逮住就要被"BB"。好嘛,我們作為學生娃兒只好認慫,常規操作,兩腳一蹬,起床,刷牙,上廁所,拿包包沖。就是這樣類似復讀機的習慣操作是怎么回事?莫非我們就能同時干這么多事?其實不是的,我們大腦下達指令,起床,刷牙這些操作早形成了肌肉記憶,所以我們在這小段時間完成了這么多事兒,還可以多幾分鐘出來看看美女不香?
平時玩兒電腦的時候,邊寫代碼邊聽音樂,計算機同時處理了這么多任務。如果是單核 CPU ?,在我們看來這些事兒是同時發生的,其實那是因為底層 CPU ?切換的速度太快以致于我們完全感受不到它的切換,僅此為錯覺而已。但是如果是多核 ?CPU ? ?,各個 CPU ?負責不同的進程,各個進程不搶占 CPU ?,這樣同時進行,這就是真正意義上的并行。
說了這么多,那并行和并發到底啥區別?
兩者區別在于是否"同時"發生。是在一段時間同時發生還是多個事情在同一個時間點同時發生。
3、同步、異步、阻塞、非阻塞的概念
首先大家應該知道同步異步,阻塞非阻塞是兩個不同層面的問題,一個是operation層面,一個是kernal層面。同步異步最大的區別在于是否需要底層的響應再執行。阻塞非阻塞最大的區別在于是否立即給出響應。
官話
同步:當一個同步調用發出后,調用者要一直等待返回結果。通知后,才能進行后續的執行。
異步:當一個異步過程調用發出后,調用者不能立刻得到返回結果。實際處理這個調用的部件在完成后,通過狀態、通知和回調來通知調用者。
阻塞:是指調用結果返回前,當前線程會被掛起,即阻塞。
非阻塞:是指即使調用結果沒返回,也不會阻塞當前線程。
形象比喻:
小Q去釣魚,拋完線后就傻傻的看著有沒有動靜,有則拉桿(同步阻塞)
小Q去釣魚,拿魚網撈一下,有沒有魚立即知道,不用等,直接就撈(同步非阻塞)
小Q去釣魚,這個魚缸比較牛皮,扔了后自己就打王者榮耀去了,因為魚上鉤了這個魚缸帶的報警器會通知我。這樣實現異步(異步非阻塞)
4、進程和線程的相關題
官話:
進程:進程是系統進行資源分配和調度的一個獨立單位,是系統中的并發執行的單位。
線程:線程是進程的一個實體,也是 ?CPU ? 調度和分派的基本單位,它是比進程更小的能獨立運行的基本單位,有時又被稱為輕量級進程。
進程是資源分配的最小單位,而線程是 ** CPU ? 調度**的最小單位;
創建進程或撤銷進程,系統都要為之分配或回收資源,操作系統開銷遠大于創建或撤銷線程時的開銷;
不同進程地址空間相互獨立,同一進程內的線程共享同一地址空間。一個進程的線程在另一個進程內是不可見的;
進程間不會相互影響,而一個線程掛掉將可能導致整個進程掛掉;
別背了,我知道你們都會背,舉個例子
計算機中的核心是 CPU ?,說它是我們的大腦一點不為過。在此用一個連鎖火鍋店舉例,因為疫情的影響,今天到目前營業額一般,只好開一家店,其他疫情較為嚴重的店只好先關閉,這里涉及的含義:單個 CPU ?一次只運行一個任務。進程就類似這家火鍋店,它代表 CPU ?所能處理的單個任務,其他地方火鍋店只能處于非運行狀態。
一個火鍋店有很多服務員,一起協同工作,將火鍋店做的紅紅火火,那么線程就好比這些服務員,一個進程可有多個線程。、
火鍋店各個工作房間是共享的,所有服務員都可以進出,這意味著進程的內存空間共享,每個線程都可以使用這些共享內存。但是不是每個房間都可以容納相同的人數,比如衛生間就只有一個人,其他人不能同時進去。這意味著一個線程在使用共享內存的時候,其他線程需要等待結束才能使用這塊內存。那怎么防止別人進入呢?很直接的辦法就是進去之后記得關門(上鎖),上了鎖,其他人想進來發現是上鎖了,那就等鎖打開后再進去,這就叫做互斥鎖,防止多個線程同時讀寫某一塊內存區域。
ok到這里,我們總結一波
如果以多進程的方式運行,那么允許多個任務同時運行
如果以多線程的方式運行,那么允許將單個任務分成不同的部分運行
為了防止進程/線程之間產生沖突和允許進程之間的共享資源,需要提供一種協調機制。
多線程與多進程的基本概念
不知道大家經歷過食堂打菜的場景沒有,如果學校食堂就開設一個窗口,打菜的阿姨也沒辦法,只好一個個給大家依次打菜,這就好比"單線程",效率非常低(此處可以考慮為什么redis使用單線程卻這么牛逼)
為了提高效率,在食堂多加了幾個窗口,這就類似"多線程"形式。
那么又想起一個問題,“多線程一定就比單線程效率高麥?”(ps Memcache是多線程模型而Redis是單線程模型)
貌似我們一提到高并發,分布式,就不得不想起多線程,那么多線程一定比單線程效率高?
上面說了采用多線程多核效果更好,但是多線程對 CPU ?,內存等都要求比較高,如果存在的上下文切換過于耗時,互斥時間太久,效率反而會低。
不一定。我不從專業術語來將,舉個例子,假設目前接水房有四個水管可以接水,我如果用4個桶分別對應4個水管,那么就比較完美,如果少一個則閑置一個,多一個則會出現搶占。如果此時我的水桶個數大于水管數,為了每個桶都有水,我們就需要切換水桶,這個過程實際上就是線程的上下文切換,代價一樣不小。
多線程與多進程的應用場景
多線程的優點
更加高效的內存共享。多進程下內存共享不便
較輕的上下文切換。因為不用切換地址空間,CR3寄存器和清空TLB
多進程的優點:
各個進程有自己內存空間,所以具有更強的容錯性,不至于一個集成crash導致系統崩潰
具有更好的多核可伸縮性,因為進程將地址空間,頁表等進行了隔離,在多核的系統上可伸縮性更強
如何提升多線程的效率
盡量使用池化技術,也就是線程池,從而不用頻繁的創建,銷毀線程
減少線程之間的同步和通信
通過Huge Page的方式避免產生大量的缺頁異常
避免需要頻繁共享寫的數據
5、進程的狀態轉換
在Linux中,進程的狀態有七種
可運行狀態
英文名詞為TASK_RUNNING,其實這個狀態雖然是RUNING,實際上并不一定會占有 CPU ?,可能修改TASK_RUNABLE會更妥當。TASK_RUNGING根據是否在在 CPU ?上運行分為RUNGING和READY兩種狀態。處于READY狀態的進程隨時可以運行,只不過因為此時 CPU ?資源受限,調度器沒選中運行
可中斷睡眠狀態與不可中斷睡眠狀態
我們知道進程不可能一直處于可運行的狀態。假設A進程需要讀取磁盤中的文件,這樣的系統調用消耗時間較長,進程需要等待較長的時間才能執行后面的命令,而且等待的時間還是不可估算的,這樣的話進程還占用 CPU ?就不友好了,因此內核就會將其更改為其他的狀態并從 CPU ?可運行的隊列移除。
Linux中存在兩種睡眠狀態,分別為:可中斷的睡眠狀態和不可中斷的狀態。兩者最大的區別為是否響應收到的信號,那么從可中斷的睡眠的進程是如何返回到可運行的狀態呢
等待的事情發生且繼續運行的條件滿足
收到了沒有被屏蔽的信號
處于此狀態的進程,收到信號會返回EINTR給用戶空間。開發者通過檢測返回值的方式進行后續邏輯處理
但是對于不可中斷的睡眠狀態,就只有一種方式返回到可運行狀態,即等待事情發生了繼續運行
上圖中為什么出現個 TASK_UNINTERRUPTIBLE 狀態,主要是因為內核中的進程不是什么進程都可以被打斷,假設響應的是異步信號,程序在執行的過程中插入一段用于處理異步信號的而流程,原來的流程就會被中斷。所以當進程在和硬件打交道的時候,需要使用 TASK_UNINTERRUPTIBLE 狀態將進程保護起來,從而避免進程和設備打交道的過程中被打斷導致設備處于不可控的狀態。
那么TASK_UNINTERRUPTIBLE狀態會出現多久呢?
其實 TASK_UNINTERRUPTIBLE 狀態是很危險的狀態,因為它刀槍不入,你無法通過信號殺死這樣一個不可中斷的休眠狀態,正常情況,TASK_UNINTERRUPTIBLE狀態存在時間很短,但是不排除存在此狀態進程比較持久的情況,真的刀槍不入了?可不可以進行提前的預防?
可以的,早就考慮了。內核提供了hung task機制,它會啟動一個khungtaskd內核線程對TASK_UNINTERRUPTIBLE狀態進行檢測,不能讓他失控了。khungtaskd會定期的喚醒,如果超過120s都還沒有調度,內核就會通過打印警告和堆棧信息。當然,不一定就是120s,可以通過下面選項進行定制
sysctl?kernel.hung_task_timeout_secs
說了這么多,我們怎么知道到底有沒有出現這個狀態,哪里看?可以通過/proc和ps進行查看
睡眠進程和等待隊列
不管是上面提到的可中斷的睡眠進程還是不可中斷的睡眠進程,都離不開一種數據結構---隊列。哦?假設進程A因為某某原因需要休眠,為啥要休眠,等待的資源遲遲拿不到或者等待的事件總是不來,沒法進行下一步操作,這個時候內核來了,"行吧,我不會拋棄你,我一定會想辦法讓你和等待的資源(事件)扯上關系",只要等待的時機到來我就喚醒你,這采用的方法即"等待隊列"。如果進一步深究,想了解它的底層實現(采用了雙向鏈表),文末我會給大家推薦基本書籍。
TASK_STOPPED狀態于TASK_TRACED狀態
TASK_STOPPED狀態屬于比較特殊的狀態,可以通過SIGCONT信號回復進程的執行
TASK_TRACED是被跟蹤的狀態,進程會停下來等待跟蹤它的進程對它進行進一步的操作
EXIT_ZOMBIE狀態與EXIT_DEAD狀態
當進程儲于這兩種的任意一種,就可以宣布"死亡" 。
就緒 —>執行:準備就緒,調度器滿足了的需求,給我一種策略,我就可從就緒變為執行的狀態;
執行 —>阻塞:不是每個進程都是那么一帆風順,就像我們每次考試,不管是中考,高考還是考研,難免都會出現磕磕盼盼,遇到了可能暫時會阻擋我們前行的小事兒,可是要相信不會一直的阻擋我們,只要我們有恒心堅持,時機到來,你也準備好了,那就美哉。回到這里,對于進程而言,當需要等到某個事情發生而無法執行的時候,進程就變為阻塞的狀態。比如當前進程提出輸入請求,如進程提出輸入/輸出請求,進程所申請資源(主存空間或外部設備)得不到滿足時變成等待資源狀態,進程運行中出現了故障(程序出錯或主存儲器讀寫錯等)變成等待干預狀態等等;
阻塞 —>就緒:處于阻塞狀態的進程,在其等待的事件已經發生,如輸入/輸出完成,資源得到滿足或錯誤處理完畢時,處于等待狀態的進程并不馬上轉入執行狀態,而是先轉入就緒狀態,然后再由系統進程調度程序在適當的時候將該進程轉為執行狀態;
執行 —>就緒:正在執行的進程,因時間片用完而被暫停執行,或在采用搶先式優先級調度算法的系統中,當有更高優先級的進程要運行而被迫讓出處理機時,該進程便由執行狀態轉變為就緒狀態。
6、進程間的通信方式有哪些?
管道
學習軟件工程規范的時候,我們知道瀑布模型,在整個項目開發過程分為多個階段,上一階段的輸出作為下一階段的輸入。各個階段的具體內容如下圖所示
最初我們在學習Linux基本命令使用的時候,我們經常通過多個命令的組合來完成我們的需求。比如說我們想知道如何查看進程或者端口是否在使用,會使用下面的這條命令
netstat -nlp | grep XXX
這里的"|"實際上就是管道的意思。"|"前面部分作為"|"后面的輸入,很明顯是單向的傳輸,這樣的管道我們叫做"匿名管道",自行創建和銷毀。既然有匿名管道,應該就有帶名字的管道"命名管道"。如果你想雙向傳輸,可以考慮使用兩個管道拼接即可。
創建命名管道的方式
mkfifo test
test即為管道的名稱,在Linux中一切皆文件,管道也是以文件的方式存在,咋們可以使用ls -l 查看下文件的屬性,它會"p"標識。
下面我們向管道寫入內容
echo "666" >test
此時按道理來說咋們已經將內容寫入了test,沒有直接輸出是因為我們需要開啟另一個終端進行輸出(可以理解為暫存管道)
cat < test
ok,我們發現管道內容被讀出來,同時echo退出。那么管道這種通信方式有什么缺點?我們知道瀑布模型的軟件開發模式是非常低下的,同理采用管道進行通信的效率也很低,因為假設現在有AB兩個進程,A進程將數據寫入管道,B進程需要等待A進程將信息寫完以后才能讀出來,所以這種方案不適合頻繁的通信。那優點是什么?
最明顯的優點就是簡單,我們平時經常使用以致于都不知道這是管道。鑒于上面的缺點,我們怎么去彌補呢?接著往下看
消息隊列
管道通信屬于一股腦的輸入,能不能稍微溫柔點有規矩點的發送消息?
答:可以的。消息隊列在發送數據的時候,按照一個個獨立單元(消息體)進行發送,其中每個消息體規定大小塊,同時發送方和接收方約定好消息類型或者正文的格式。
在管道中,其大小受限且只能承載無格式字節流的方式,而消息隊列允許不同進程以消息隊列的形式發送給任意的進程。
但是當發送到消息隊列的數據太大,需要拷貝的時間也就越多,所以還有其他的方式?繼續看
共享內存
使用消息隊列可以達到不錯的效果,但是如果我們兩個部門需要交換比較大的數據的時候,一發一收還是不能及時的感知數據。能不能更好的辦法,雙方能很快的分享內容數據,答:有的,共享內存
我們知道每個進程都有自己的虛擬內存空間,不同的進程映射到不同的物理內存空間。那么我們可不可以申請一塊虛擬地址空間,不同進程通過這塊虛擬地址空間映射到相同的屋里地址空間呢?這樣不同進程就可以及時的感知進程都干了啥,就不需要再拷貝來拷貝去。
我們可以通過shmget創建一份共享內存,并可以通過ipcs命令查看我們創建的共享內存。此時如果一個進程需要訪問這段內存,需要將這個內存加載到自己虛擬地址空間的一個位置,讓內核給它一個合法地址。使用完畢接觸板頂并刪除內存對象。
那么問題來了,這么多進程都共享這塊內存,如果同時都往里面寫內容,難免會出現沖突的現象,比如A進程寫了數字5,B進程同樣的地址寫了6就直接給覆蓋了,這樣就不友好了,怎么辦?繼續往下看
信號量
為了防止沖突,我們得有個約束或者說一種保護機制。使得同一份共享的資源只能一個進程使用,這里就出現了信號量機制。
信號量實際上是一個計數器,這里需要注意下,信號量主要實現進程之間的同步和互斥,而不是存儲通信內容。
信號量定義了兩種操作,p操作和v操作,p操作為申請資源,會將數值減去M,表示這部分被他使用了,其他進程暫時不能用。v操作是歸還資源操作,告知歸還了資源可以用這部分。
信號
從管道----消息隊列-共享內存/信號量,有需要等待的管道機制,共享內存空間的進程通信方式,還有一種特殊的方式--信號
我們或許聽說過運維或者部分開發需要7 * 24小時值守(項目需要上線的時候),當然也有各種監管,告警系統,一旦出現系統資源緊張等問題就會告知開發或運維人員,對應到操作系統中,這就是信號。
在操作系統中,不同信號用不同的值表示,每個信號設置相應的函數,一旦進程發送某一個信號給另一個進程,另一進程將執行相應的函數進行處理。也就是說把可能出現的異常等問題準備好,一旦信號產生就執行相應的邏輯即可。
套接字
上面的幾種方式都是單機情況下多個進程的通信方式,如果我想和相隔幾千里的小姐姐通信怎么辦?
這就需要套接字socket了。其實這玩意隨處可見,我們平時的聊天,我們天天請求瀏覽器給予的響應等,都是這老鐵。
小結
分享了一下幾種進程間通信方式,希望大家能知其然并知其所以然,機械式的記憶容易忘記哦。
管道
消息隊列
共享內存
信號量
信號
套接字
7、進程的調度算法有哪些?
調度算法是指:調度程序是內核的重要組成部分,決定這下一個要運行的進程。那么根據系統的資源分配策略所規定的資源分配算法。常用的調度算法有:先來先服務調度算法、時間片輪轉調度法、短作業優先調度算法、最短剩余時間優先、高響應比優先調度算法、優先級調度算法等等。
先來先服務調度算法
先來先服務讓我們想起了隊列的先進先出特性,每一次的調度都從隊列中選擇最先進入隊列的投入運行。
時間片輪轉調度算法
先來理解輪轉,假設當前進程A、B、C、D,按照進程到達的時間排序,而且每個進行都有著同樣大小的時間片。如果這個進程在當前的時間片運行結束,啥事兒沒有,直接將進程從隊列移除完事兒。如果進程在這個時間片跑完都沒有結束,進程變為等待狀態,放在進程尾部直到所有進程執行完畢。
為什么進程要切換,切換無外乎是時間片夠用或者不夠用。如果時間片夠用,那么進程可以運行到結束,結束后刪除啟動新的時間片。如果時間片不夠用,對不起,暫時只能完成一部分任務(變為等待狀態),過后再等待 CPU ?的調度。網上開源的代碼太多,怎么實現,大家可以參照加深影響。
短作業優先調度算法
短作業優先調度算法,從名稱可以清晰的知道「短作業」意味著執行時間比較短,「優先」代表執行順序。結合就是"短者吃香"。那么多短吃香?進程不可能都短,也有需要執行時間比較長的進程怎么辦?一直等待,直到餓死麥?而且有些進程比較緊急,能夠得到先執行?這些都是此算法所出現的問題,然后出現下面的一些算法
最短剩余時間優先調度算法
最短剩余時間是針對最短進程優先增加了搶占機制的版本。在這種情況下,進程調度總是選擇預期剩余時間最短的進程。當一個進程加入到就緒隊列時,他可能比當前運行的進程具有更短的剩余時間,因此只要新進程就緒,調度程序就能可能搶占當前正在運行的進程。像最短進程優先一樣,調度程序正在執行選擇函數是必須有關于處理時間的估計,并且存在長進程饑餓的危險。
高響應比優先調度算法
什么是高響應比,有響應之前應該會有請求,相當于是請求+響應+優先,算是一種綜合的調度算法。也就是它結合了短作業優先,先來先服務以及長作業的一些特性。ok,那么這三種是如何體現出來的
首先來說短作業優先。等待時間我們假設相等,服務時間很短,這樣的話短作業就會有更高的優先權。
再來看先來先服務。假設服務時間相同,先來的自然等待時間較長,優先級越高。
上面說長作業很可能因為等待時間過長,容易餓死。在這里不會,仿佛像醫生的這個職業,工作越久資歷越老,優先級越來越高,越來越吃香
優先級調度算法
優先級調度算法每次從后備作業隊列中選擇優先級最髙的一個或幾個作業,將它們調入內存,分配必要的資源,創建進程并放入就緒隊列。在進程調度中,優先級調度算法每次從就緒隊列中選擇優先級最高的進程,將處理機分配給它,使之投入運行。
8、什么是死鎖?
死鎖,顧名思義就是導致線程卡死的鎖沖突,例如下面的這種情況
線程 1 已經成功拿到了互斥量 1,正在申請互斥量 2,而同時在另一個 ?CPU ? 上,線程 2 已經拿到了互
斥量 2,正在申請互斥量 1。彼此占有對方正在申請的互斥量,結局就是誰也沒辦法拿到想要的互斥
量,于是死鎖就發生了。
稍微復雜一點的情況
存在多個互斥量的情況下,避免死鎖最簡單的方法就是總是按照一定的先后順序申請這些互斥
量。還是以剛才的例子為例,如果每個線程都按照先申請互斥量 1 ,再申請互斥量 2 的順序執行,死鎖
就不會發生。有些互斥量有明顯的層級關系,但是也有一些互斥量原本就沒有特定的層級關系,不過
沒有關系,可以人為干預,讓所有的線程必須遵循同樣的順序來申請互斥量
9、產生死鎖的原因?
由于系統中存在一些不可剝奪資源,而當兩個或兩個以上進程占有自身資源,并請求對方資源時,會導致每個進程都無法向前推進,這就是死鎖。
競爭資源
例如:系統中只有一臺打印機,可供進程 A 使用,假定 A 已占用了打印機,若 B 繼續要求打印機打印將被阻塞。
系統中的資源可以分為兩類:
可剝奪資源:是指某進程在獲得這類資源后,該資源可以再被其他進程或系統剝奪, CPU ? 和主存均屬于可剝奪性資源;
不可剝奪資源,當系統把這類資源分配給某進程后,再不能強行收回,只能在進程用完后自行釋放,如磁帶機、打印機等。
進程推進順序不當
例如:進程 A 和 進程 B 互相等待對方的數據。
10、死鎖產生的必要條件?
互斥
要求各個資源互斥,如果這些資源都是可以共享的,那么多個進程直接共享即可,不會存在等待的尷尬場景
非搶占
要求進程所占有的資源使用完后主動釋放即可,其他的進程休想搶占這些資源。原因很簡單,如果可以搶占,直接拿就好了,不會進入尷尬的等待場景
要求進程是在占有(holding)至少一個資源的前提下,請求(waiting)新的資源的。由于新的資源被其它進程占有,此時,發出請求的進程就會帶著自己占有的資源進入阻塞狀態。假設 P1,P2 分別都需要 R1,R2 資源,如果是下面這種方式:
?P1:??????????P2:
request(R1)??request(R2)
request(R2)??request(R1)?如果 P1 請求到了 R1 資源之后,P2 請求到了 R2 資源,那么此后不管是哪個進程再次請求資源,都是在占有資源的前提下請求的,此時就會帶著這個資源陷入阻塞狀態。P1 和 P2 需要互相等待,發生了死鎖。
換一種情況:
?P1:??????????P2:
request(R1)??request(R1)
request(R2)??request(R2)?如果 P1 請求到了 R1 資源,那么 P2 在請求 R1 的時候雖然也會阻塞,但是是在不占有資源的情況下阻塞的,不像之前那樣占有 R2。所以,此時 P1 可以正常完成任務并釋放 R1,P2 拿到 R1 之后再去執行任務。這種情況就不會發生死鎖。
循環等待
要求存在一條進程資源的循環等待鏈,鏈中的每一個進程占有的資源同時被另一個進程所請求。
發生死鎖時一定有循環等待(因為是死鎖的必要條件),但是發生循環等待的時候不一定會發生死鎖。這是因為,如果循環等待鏈中的 P1 和 鏈外的 P6 都占有某個進程 P2 請求的資源,那么 P2 完全可以選擇不等待 P1 釋放該資源,而是等待 P6 釋放資源。這樣就不會發生死鎖了。
11、解決死鎖的基本方法?
如果我們已經知道死鎖形成的必要條件,逐一攻破即可。
破壞互斥
通過與鎖完全不同的同步方式CAS,CAS提供原子性支持,實現各種無鎖的數據結構,不僅可以避免互斥鎖帶來的開銷也可避免死鎖問題。
破壞不搶占
如果一個線程已經獲取到了一些鎖,那么在這個線程釋放鎖之前這些鎖是不會被強制搶占的。但是為了防止死鎖的發生,我們可以選擇讓線程在獲取后續的鎖失敗時主動放棄自己已經持有的鎖并在之后重試整個任務,這樣其他等待這些鎖的線程就可以繼續執行了。這樣就完美了嗎?當然不
這種方式雖然可以在一定程度上避免死鎖,但是如果多個相互存在競爭的線程不斷的放棄重啟放棄循環,就會出現活鎖的問題,此時線程雖然沒有因為鎖沖突被卡死,但是仍然會因為阻塞時間太長處于重試當中。怎么辦?
方案1:給任務重試部分增加隨機延遲時間,降低任務沖突的概率
破壞環路等待
在實踐的過程中,采用破壞環路等待的方式非常常見,這種技術叫做"鎖排序"。很好理解,我們假設現在有個數組A,采用單向訪問的方式(從前往后),依次訪問并加鎖,這樣一來,線程只會向前單向等待鎖釋放,自然也就無法形成一個環路了。
說到這里,我想說死鎖不僅僅出現在多線程編程領域,在數據庫的訪問也是非常的常見,比如我們需要更新數據庫的幾行數據,就得先獲取這些數據的鎖,然后通過排序的方式阻止數據層發生死鎖。
這樣就完美了?當然沒有,那會出現什么問題?
這種方案也存在它的缺點,比如在大型系統當中,不同模塊直接解耦和隔離得非常徹底,不同模塊開發人員不清楚其細節,在這樣的情況下就很難做到整個系統層面的全局鎖排序了。在這種情況下,我們可以對方案進行擴充,例如Linux在內存映射代碼就使用了一種鎖分組排序的方式來解決這個問題。鎖分組排序首先按模塊將鎖分為了不同的組,每個組之間定義了嚴格的加鎖順序,然后再在組內對具體的鎖按規則進行排序,這樣就保證了全局的加鎖順序一致。在Linux的對應的源碼頂部,我們可以看到有非常詳盡的注釋定義了明確的鎖排序規則。
這種解決方案如果規模過大的話即使可以實現也會非常的脆弱,只要有一個加鎖操作沒有遵守鎖排序規則就有可能會引發死鎖。不過在像微服務之類解耦比較充分的場景下,只要架構拆分合理,任務模塊盡可能小且不會將加鎖范圍擴大到模塊之外,那么鎖排序將是一種非常實用和便捷的死鎖阻止技術
12、怎么預防死鎖?
破壞請求條件:一次性分配所有資源,這樣就不會再有請求了;
破壞請保持條件:只要有一個資源得不到分配,也不給這個進程分配其他的資源:
破壞不可剝奪條件:當某進程獲得了部分資源,但得不到其它資源,則釋放已占有的資源;
破壞環路等待條件:系統給每類資源賦予一個編號,每一個進程按編號遞增的順序請求資源,釋放則相反。
13、怎么避免死鎖?
銀行家算法
當進程首次申請資源時,要測試該進程對資源的最大需求量,如果系統現存的資源可以滿足它的最大需求量則按當前的申請量分配資源,否則就推遲分配。
當進程在執行中繼續申請資源時,先測試該進程已占用的資源數與本次申請資源數之和是否超過了該進程對資源的最大需求量。若超過則拒絕分配資源。若沒超過則再測試系統現存的資源能否滿足該進程尚需的最大資源量,若滿足則按當前的申請量分配資源,否則也要推遲分配。
安全序列
是指系統能按某種進程推進順序(P1, P2, P3, …, Pn),為每個進程 Pi 分配其所需要的資源,直至滿足每個進程對資源的最大需求,使每個進程都可以順序地完成。這種推進順序就叫安全序列【銀行家算法的核心就是找到一個安全序列】。
系統安全狀態
如果系統能找到一個安全序列,就稱系統處于安全狀態,否則,就稱系統處于不安全狀態。
14、怎么解除死鎖?
資源剝奪:掛起某些死鎖進程,并搶占它的資源,將這些資源分配給其他死鎖進程(但應該防止被掛起的進程長時間得不到資源);
撤銷進程:強制撤銷部分、甚至全部死鎖進程并剝奪這些進程的資源(撤銷的原則可以按進程優先級和撤銷進程代價的高低進行);
進程回退:讓一個或多個進程回退到足以避免死鎖的地步。進程回退時自愿釋放資源而不是被剝奪。要求系統保持進程的歷史信息,設置還原點。
15、什么是緩沖區溢出?有什么危害?
官話
緩沖區溢出是指當計算機向緩沖區內填充數據時超過了緩沖區本身的容量,溢出的數據覆蓋在合法數據上
舉個例子
一個兩升的杯子,你如果想導入三升,怎么做?其他一生只好流出去,不是打濕了電腦就是那啥。
16、物理地址、邏輯地址、線性地址
物理地址:它是地址轉換的最終地址,是內存單元真正的地址。如果采用了分頁機制,那么線性地址會通過頁目錄和頁表得方式轉換為物理地址。如果沒有啟用則線性地址即為物理地址
邏輯地址:在編寫c語言的時候,通過&操作符可以讀取指針變量本省得值,這個值就是邏輯地址。實際上是當前進程得數據段得地址,和真實的物理地址沒有關系。只有當在Intel實模式下,邏輯地址==物理地址。我們平時的應用程序都是通過和邏輯地址打交道,至于分頁,分段機制對他們而言是透明得。邏輯地址也稱作虛擬地址
線性地址:線性地址是邏輯地址到物理地址的中間層。我們編寫的代碼會存在一個邏輯地址或者是段中得偏移地址,通過相應的計算(加上基地址)生成線性地址。此時如果采用了分頁機制,那么吸納行地址再經過變換即產生物理地址。在Intelk 80386中地址空間容量為4G,各個進程地址空間隔離,意味著每個進程獨享4G線性空間。多個進程難免出現進程之間的切換,線性空間隨之切換。基于分頁機制,對于4GB的線性地址一部分會被映射到物理內存,一部分映射到磁盤作為交換文件,一部分沒有映射,通過下面加深一下印象
17、分頁與分段的區別?
我們知道計算機的五大組成部分分別為運算器,存儲器,存儲器 ,輸入和輸出設備。我們的數據或者指定都需要存放內存然后給 CPU ?大哥拿去執行。我們平時寫的代碼不是直接操作的物理地址,我們所看到的地址實際上叫做虛擬地址,通過相應的轉換規則將虛擬地址轉換為物理地址。
那么虛擬地址是怎么轉換為物理地址的呢?
第一種方式,采用一個映射表代表虛擬地址到物理地址的映射,在計算機中我們叫做頁表。頁表將內存地址分為頁號和偏移量,舉個例子
我們將高位部分稱為內存地址的頁號,后面的低位叫做內存地址的偏移量。我們只需要保存虛擬地址內存的頁號和物理內存頁號之間的映射關系即可。
這樣說了,也就是三部曲
虛擬地址----->頁號+偏移量
通過頁表查詢出虛擬頁號,對應的物理頁號
物理頁號+偏移量----->物理內存地址
這樣的方法,在32位的內存地址,頁表需要多大的空間?
在一個32位的內存地址空間,頁表需要記錄2^20個物理頁面的映射關系,可以想象為要給數組。那么一個頁號是完整的4字節。這樣一個頁表就是4MB。
再來,我們知道進程有各自的虛擬內存空間,也就是說每個進程都需要一個這樣的頁表,不管此進程是只有幾KB的程序還是需要GB的內存空間都需要這樣的頁表,用這樣的結構保存頁面,內存的占用將非常的大,那其他方式是怎么樣的呢
多級頁表
同樣的虛擬內存地址,偏移量部分和上面方式一樣,但是我們將頁號部分拆分為四段,從高到低分成4級到1級的4個頁表索引
這樣一來,每個進程將有4級頁表。通過4級頁表的索引找到對應的條目。通過這個條目找到3級頁表所在位置,4級的每一個條目可能有多個3級的條目,找到了3級的條目后找到對應3級索引的條目,就這樣到達1級頁表。1級對應的則為物理頁號。最終通過物理頁號+偏移量的方式獲取物理內存地址。
18 為什么使用多級頁表
使用多級頁表可以讓頁表在內存中離散存儲。多級頁表通過索引就可以定位到具體的項。舉個例子,假設當前虛擬地址空間為4G,每個頁的大小為4k,如果是一級頁表的話,共有2……20個頁表項,假設每個頁表項需要4B,那么存放所有的頁表項需要4M,那么為了隨機訪問,我們就需要連續的4M內存空間存放所有的頁表項。這樣一來,隨著虛擬地址空間的增大,需要存放頁表所需的連續空間也就越來多大。如果使用多級頁表,我們只需要一頁存放目錄項,頁表存放在內存其他位置即可,下面有例子進一步講解
使用多級頁表更加節省頁表內存。理論上,使用一級頁表,需要連續存儲空間存放所有項。使用多級頁表只需要給實際使用的的那些虛擬地址內存的請求分配內存
舉個例子
假設虛擬地址空間為4G,A進程只是用 4M 的內存空間。對于一級頁表,我們需要 4M 空間存放這4GB 虛擬地址對應的頁表,然后找到進程真正的 4M 內存空間。這樣的話,A進程本來只使用 4MB 內存空間,但是為了訪問它,我們需要為所有的虛擬地址空間建立頁表,豈不是很浪費。對于二級頁表而言,使用一個頁目錄就可定位 4M 的內存,存放一個頁目錄項需要 4k,還需要一頁存放進程使用的 4M,4M=1024*4k,也就相當于 1024個頁表項就可以映射4M的內存空間,那么總共就只需要4k(頁表)+4k(頁目錄)=8k來存放進程需要的 4M 內存空間對應頁表和頁目錄項。這樣看來確實剩下不少的內存。
那使用多級頁表有啥缺點?
還是有的,咋們使用一級頁表的時候,只需要訪問兩次內存,一次是訪問頁表項,一次是訪問需要讀取的一頁數據。如果是二級頁表,就需要訪問三次,第一次訪問頁目錄,第二次訪問頁表項,第三次訪問讀取的數據。訪問次數的增加以為訪問數據所花費的總時間也增加
19、頁面置換算法有哪些?
請求調頁,也稱按需調頁,即對不在內存中的“頁”,當進程執行時要用時才調入,否則有可能到程序結束時也不會調入。而內存中給頁面留的位置是有限的,在內存中以幀為單位放置頁面。為了防止請求調頁的過程出現過多的內存頁面錯誤(即需要的頁面當前不在內存中,需要從硬盤中讀數據,也即需要做頁面的替換)而使得程序執行效率下降,我們需要設計一些頁面置換算法,頁面按照這些算法進行相互替換時,可以盡量達到較低的錯誤率。常用的頁面置換算法如下:
先進先出置換算法(FIFO)
先進先出,即淘汰最早調入的頁面。
最佳置換算法(OPT)
選未來最遠將使用的頁淘汰,是一種最優的方案,可以證明缺頁數最小。
最近最久未使用(LRU)算法
即選擇最近最久未使用的頁面予以淘汰
時鐘(Clock)置換算法
時鐘置換算法也叫最近未用算法 NRU(Not RecentlyUsed)。該算法為每個頁面設置一位訪問位,將內存中的所有頁面都通過鏈接指針鏈成一個循環隊列。。
20 書籍/視頻學習推薦
書籍
Linux內核設計與實現
操作系統導論
現代操作系統
深入理解操作系統
視頻
B站 ----哈工大李志軍老師講解
https://www.bilibili.com/video/av17036347/
往期推薦
免責聲明:本文內容由21ic獲得授權后發布,版權歸原作者所有,本平臺僅提供信息存儲服務。文章僅代表作者個人觀點,不代表本平臺立場,如有問題,請聯系我們,謝謝!