【操作系統(tǒng)面試題匯總】鞏固你的計(jì)算機(jī)基礎(chǔ)

“

我并沒(méi)有系統(tǒng)的學(xué)習(xí)過(guò)計(jì)算機(jī)操作系統(tǒng)的課程，之前因?yàn)闇?zhǔn)備面試，發(fā)現(xiàn)大廠會(huì)比較喜歡考這一方面的問(wèn)題，所以根據(jù)一些朋友面經(jīng)的題目，再查找一些好的文章將其匯總了一下。其中像進(jìn)程與線程的區(qū)別，同步與異步，阻塞、非阻塞，死鎖了解這些概念我認(rèn)為對(duì)加深前端某些知識(shí)的理解還是很有幫助的。對(duì)于想沖擊大廠的同學(xué)來(lái)說(shuō)像磁盤(pán)尋道、進(jìn)程之間的通信方式這些問(wèn)題也是很有可能考的。

”

一、進(jìn)程和線程的區(qū)別是什么？

網(wǎng)上關(guān)于這個(gè)問(wèn)題有很多的解答，也有很多生動(dòng)的例子，但這里給出我自己比較認(rèn)可的一種回答，僅供參考。

本質(zhì)上來(lái)說(shuō)，進(jìn)程與線程都是CPU工作時(shí)間段的描述，也就是運(yùn)行中程序指令的描述。

背景知識(shí)：

為了解釋上面這句話，我們首先需要了解一些關(guān)于計(jì)算機(jī)的基礎(chǔ)知識(shí)。

1. 對(duì)于CPU來(lái)說(shuō)，其執(zhí)行任務(wù)的速度是非?？斓?。也就是說(shuō)即使有多個(gè)任務(wù)要執(zhí)行，但對(duì)于CPU來(lái)說(shuō)每個(gè)任務(wù)也是輪流執(zhí)行的，由于執(zhí)行的速度太快，以至于我們認(rèn)為其是同時(shí)在處理多個(gè)任務(wù)的。

2. CPU在執(zhí)行某段程序，或者任務(wù)之前需要將所有相關(guān)資源準(zhǔn)備好。這些任務(wù)都處于就緒隊(duì)列，然后等待操作系統(tǒng)的調(diào)度算法，選出某個(gè)任務(wù)去給CPU執(zhí)行，之后PC指針指向該代碼的開(kāi)始，由CPU取指令然后一個(gè)個(gè)執(zhí)行，在CPU執(zhí)行某個(gè)任務(wù)的時(shí)候?qū)?yīng)所需的資源會(huì)加載在RAM中。

3. 這里CPU執(zhí)行每一個(gè)任務(wù)的過(guò)程其實(shí)就可以理解為一個(gè)個(gè)進(jìn)程，而所需準(zhǔn)備的資源就可以理解為進(jìn)程執(zhí)行過(guò)程中的所需要的上下文環(huán)境，當(dāng)某個(gè)進(jìn)程執(zhí)行完畢，或者分配給他的CPU的時(shí)間段用完了，需要先保存當(dāng)前進(jìn)程的上下文環(huán)境，等待CPU的下次執(zhí)行。

那么多個(gè)進(jìn)程是怎么樣有序的執(zhí)行的？首先加載一個(gè)進(jìn)程的上下文環(huán)境，執(zhí)行完畢之后保存其上下文環(huán)境，之后加載下一個(gè)進(jìn)程的上下文環(huán)境，執(zhí)行完畢，保存上下文環(huán)境。。。如此重復(fù)。

說(shuō)了這些我想大家應(yīng)該對(duì)進(jìn)程的本質(zhì)有了自己的理解了，為了描述計(jì)算機(jī)在切換上下文之間CPU執(zhí)行程序的時(shí)間段我們有了進(jìn)程和線程這兩個(gè)名詞。

“

插入一點(diǎn)不相關(guān)的：名詞是對(duì)客觀事物的指代，形容詞是對(duì)客觀事物的描述。

”

之后的線程就很好理解了，線程是相比于進(jìn)程更小CPU執(zhí)行時(shí)間段，我們假設(shè)CPU要執(zhí)行一個(gè)程序A也就是處理一個(gè)進(jìn)程，而這個(gè)程序由a，b，c三部分組成。大家可以看下面這個(gè)例子來(lái)理解。

“

我們可以想象打開(kāi)Chrome瀏覽器相當(dāng)于打開(kāi)了一個(gè)進(jìn)程，而如果我們需要顯示一個(gè)頁(yè)面需要Chrome瀏覽器解析JS代碼的線程，發(fā)送請(qǐng)求數(shù)據(jù)的線程，生成位圖數(shù)據(jù)的線程等，他們以某種順序輪流工作最終生成了我們要顯示的頁(yè)面。

”

執(zhí)行過(guò)程就是首先會(huì)加載A的上下文環(huán)境，然后CPU執(zhí)行a部分，之后執(zhí)行b，之后執(zhí)行c，然后保存A的上下文環(huán)境。這里在切換線程的上下文環(huán)境時(shí)所消耗時(shí)間遠(yuǎn)遠(yuǎn)小于切換進(jìn)程上下文所需要的時(shí)間，所以CPU的利用率大大提高。

全局變量我們?cè)诔绦驇缀跞魏蔚胤蕉伎梢允褂茫喈?dāng)于所有的線程共享當(dāng)前進(jìn)程的上下文環(huán)境，也就是當(dāng)前進(jìn)程的地址空間。

“

注意這里描述的進(jìn)程線程概念和實(shí)際代碼中所說(shuō)的進(jìn)程線程是有區(qū)別的。編程語(yǔ)言中的定義方式僅僅是語(yǔ)言的實(shí)現(xiàn)方式，是對(duì)進(jìn)程線程概念的物化。

”

什么是單線程與多線程？

CPU的執(zhí)行時(shí)間段，從宏觀與微觀上可以分為進(jìn)程與線程，而線程又可以分為單線程與多線程。

• 單線程：這個(gè)很好理解，我們的的Javascript是單線程的，也就是說(shuō)瀏覽器在解析JS代碼時(shí)只有一個(gè)線程在工作的，如果發(fā)現(xiàn)某地方有錯(cuò)誤就會(huì)停止，后續(xù)無(wú)法執(zhí)行。這個(gè)有錯(cuò)誤后續(xù)無(wú)法執(zhí)行的過(guò)程也稱之為阻塞。
• 多線程：多個(gè)線程按照某種順序輪流執(zhí)行，多線程在上面的例子中，已經(jīng)可以很好的說(shuō)明了，但是我們要注意的是多線程的程序看起來(lái)像多個(gè)線程同時(shí)運(yùn)行，其實(shí)對(duì)于CPU來(lái)說(shuō)他們只是按照某種順序輪流執(zhí)行罷了。

簡(jiǎn)單來(lái)說(shuō)就是在一個(gè)進(jìn)程中，同一時(shí)間只能做一件事就是單線程，可以做多件事就是多線程。

什么是并發(fā)與并行？

• 并發(fā)：并發(fā)，在操作系統(tǒng)中，是指一個(gè)時(shí)間段中有幾個(gè)程序都處于已啟動(dòng)運(yùn)行到運(yùn)行完畢之間，且這幾個(gè)程序都是在同一個(gè)處理機(jī)上運(yùn)行，但任一個(gè)時(shí)刻點(diǎn)上只有一個(gè)程序在處理機(jī)上運(yùn)行。

“

我們想象有多個(gè)用戶訪問(wèn)服務(wù)器，如果將一個(gè)用戶的請(qǐng)求處理完才能處理下一個(gè)用戶的請(qǐng)求，那也太過(guò)于浪費(fèi)時(shí)間了，所以實(shí)際上我們好像是可以同時(shí)訪問(wèn)一個(gè)網(wǎng)站，但是對(duì)于被訪問(wèn)網(wǎng)站的服務(wù)器來(lái)說(shuō)其還是一個(gè)個(gè)處理不同客戶端的請(qǐng)求的，只不過(guò)其處理請(qǐng)求的速度太快讓我們誤以為多個(gè)用戶是同時(shí)訪問(wèn)網(wǎng)站的。

”

• 并行：同一時(shí)刻，多個(gè)指令，在不同的處理機(jī)上運(yùn)行。比如我們一邊聽(tīng)歌一邊寫(xiě)代碼，播放器進(jìn)程和VScode進(jìn)程就是并行的。

進(jìn)程與線程兩者區(qū)別是什么？

說(shuō)了上面這些再回答這個(gè)問(wèn)題，還是希望大家從理解的角度來(lái)記憶，從而在面試時(shí)給面試官一個(gè)滿意的答案。

1. 首先進(jìn)程與線程本質(zhì)都是CPU工作的時(shí)間段的描述，這句話可以得50分
2. 進(jìn)程是資源分配的基本單位，線程是程序執(zhí)行的基本單位
3. 進(jìn)程擁有獨(dú)立的地址空間，多進(jìn)程程序一個(gè)進(jìn)程崩潰了不影響其他進(jìn)程。多線程程序共享當(dāng)前進(jìn)程的地址空間，一個(gè)線程崩潰了可能導(dǎo)致整個(gè)進(jìn)程崩潰
4. 線程之間通信很容易，本身就共享同一塊內(nèi)存，只要指針指向就可以了，而進(jìn)程之間通信就比較麻煩，這里面試官可能會(huì)問(wèn)進(jìn)程之間如何通信等，文章后面有回答

其實(shí)多線程程序從宏觀上來(lái)看，是讓一個(gè)程序在運(yùn)行時(shí)有多個(gè)功能可以同時(shí)執(zhí)行，但本質(zhì)上對(duì)于CPU來(lái)說(shuō)還是離不開(kāi)切換當(dāng)前線程的上下文（當(dāng)然切換線程的上下文比較容易），按某種順序執(zhí)行不同的線程等。

二、什么是同步與異步？

同步和異步本質(zhì)上關(guān)心的是消息的通信機(jī)制 (synchronous communication/ asynchronous communication)。

同步：如果你發(fā)起一個(gè)調(diào)用，在沒(méi)有得到結(jié)果之前這個(gè)調(diào)用是沒(méi)有返回值的，如果一旦有了結(jié)果，該調(diào)用就有了返回值。也就是說(shuō)我們需要主動(dòng)的等待調(diào)用的結(jié)果。

異步：異步正好相反，如果我們發(fā)起了一個(gè)調(diào)用，這個(gè)調(diào)用就立刻返回了，所以沒(méi)有返回結(jié)果。也就是說(shuō)當(dāng)一個(gè)調(diào)用被發(fā)起后，我們是不會(huì)立刻得到結(jié)果的，而是等待被調(diào)用者通過(guò)狀態(tài)、通知來(lái)通知調(diào)用者，或者通過(guò)回調(diào)函數(shù)來(lái)處理這個(gè)調(diào)用（很像Promsie）。

舉個(gè)例子：你打電話問(wèn)書(shū)店老板有沒(méi)有《分布式系統(tǒng)》這本書(shū)，如果是同步通信機(jī)制，書(shū)店老板會(huì)說(shuō)，你稍等，”我查一下"，然后開(kāi)始查啊查，等查好了（可能是5秒，也可能是一天）告訴你結(jié)果（返回結(jié)果）。
而異步通信機(jī)制，書(shū)店老板直接告訴你我查一下啊，查好了打電話給你，然后直接掛電話了（不返回結(jié)果）。然后查好了，他會(huì)主動(dòng)打電話給你。在這里老板通過(guò)“回電”這種方式來(lái)回調(diào)。

三、什么是阻塞與非阻塞？

阻塞和非阻塞關(guān)注的是程序在等待調(diào)用結(jié)果（消息返回值）時(shí)的狀態(tài)。

阻塞調(diào)用是指當(dāng)前調(diào)用在沒(méi)有得到返回結(jié)果之前，線程會(huì)被掛起。無(wú)法執(zhí)行其他調(diào)用，只有返回結(jié)果之后才可以。

非阻塞調(diào)用指在沒(méi)有返回結(jié)果之前，該線程還可以滿足其他調(diào)用，不會(huì)被阻塞。

舉個(gè)例子：你打電話問(wèn)書(shū)店老板有沒(méi)有《分布式系統(tǒng)》這本書(shū)，你如果是阻塞式調(diào)用，你會(huì)一直把自己“掛起”，直到得到這本書(shū)有沒(méi)有的結(jié)果，如果是非阻塞式調(diào)用，你不管老板有沒(méi)有告訴你，你自己先一邊去玩了， 當(dāng)然你也要偶爾過(guò)幾分鐘check一下老板有沒(méi)有返回結(jié)果。

在這里阻塞與非阻塞與是否同步異步無(wú)關(guān)。跟老板通過(guò)什么方式回答你結(jié)果無(wú)關(guān)。

總結(jié)一下就是，同步與異步主要關(guān)注消息的通信機(jī)制，而阻塞與非阻塞主要關(guān)注的是等待程序調(diào)用結(jié)果時(shí)的狀態(tài)。

同步與異步主要關(guān)心的是消息通知時(shí)的方式，如果調(diào)用立刻就有返回值那就是同步，如果調(diào)用時(shí)不是立刻有返回值而是有返回值時(shí)通過(guò)某種方式通知我們那就是異步。

阻塞與非阻塞主要關(guān)心的是等待通知時(shí)的狀態(tài)，如果等待通知時(shí)不能做其他的事就是阻塞，而等待通知與做其他事無(wú)影響那就是非阻塞。

四、進(jìn)程之間的通信方式有哪些，他們的優(yōu)缺點(diǎn)有哪些呢？

上面已經(jīng)說(shuō)過(guò)，每一個(gè)進(jìn)程都有自己的用戶地址空間，進(jìn)程中是無(wú)法獲取到其他進(jìn)程的全局變量或數(shù)據(jù)的，所以如果進(jìn)程之間要進(jìn)行通信必須通過(guò)“第三者”也就是內(nèi)核，在內(nèi)核中開(kāi)辟一塊內(nèi)存緩沖區(qū)，進(jìn)程A將數(shù)據(jù)拷貝到內(nèi)核緩沖區(qū)之中，進(jìn)程B要使用的話就必須去內(nèi)核緩沖區(qū)中讀取，這樣就完成了進(jìn)程之間的相互通信，內(nèi)核提供的這種機(jī)制就稱之為進(jìn)程間通信（IPC，InterProcess Communication）。

管道：

管道分為兩種，一種是匿名管道，一種是具名管道。在Linux中使用“|”來(lái)表示管道，有興趣的同學(xué)可以去看看它的用法。

管道的實(shí)質(zhì)是一個(gè)內(nèi)核緩沖區(qū)，進(jìn)程以先進(jìn)先出的方式從緩沖區(qū)存取數(shù)據(jù)，管道一端的進(jìn)程順序的將數(shù)據(jù)寫(xiě)入緩沖區(qū)，另一端的進(jìn)程則順序的讀出數(shù)據(jù)，我們可以將其想象成一個(gè)隊(duì)列。


匿名管道：

• 其是半全雙工的，數(shù)據(jù)只能單向流動(dòng)，如果雙方都需要通信就需要建立兩個(gè)管道
• 其只能用在親戚進(jìn)程之間，父子進(jìn)程，兄弟進(jìn)程
• 數(shù)據(jù)的讀出和寫(xiě)入：一個(gè)進(jìn)程向管道中寫(xiě)的內(nèi)容被管道另一端的進(jìn)程讀出。寫(xiě)入的內(nèi)容每次都添加在管道緩沖區(qū)的末尾，并且每次都是從緩沖區(qū)的頭部讀出數(shù)據(jù)。
• 注意通信時(shí)的數(shù)據(jù)還是在內(nèi)存中的

具名管道：

• 解決了匿名管道只能在親戚進(jìn)程之間通信的問(wèn)題
• 管道的名字存放在系統(tǒng)磁盤(pán)，內(nèi)容存放在內(nèi)核中

管道的優(yōu)缺點(diǎn)：

優(yōu)點(diǎn)很明確，在Linux系統(tǒng)中使用很簡(jiǎn)單，存在阻塞機(jī)制，如果可以確保數(shù)據(jù)被取走。

缺點(diǎn)是內(nèi)核的緩沖區(qū)是有限的，并且也正是由于存在阻塞機(jī)制a進(jìn)程給b進(jìn)程傳遞數(shù)據(jù)，b進(jìn)程讀取數(shù)據(jù)后a進(jìn)程才可以返回。所以不適合頻繁通信的情況。

信號(hào)：

“

信號(hào)是軟件層次上對(duì)中斷機(jī)制的一種模擬，是一種異步通信方式，信號(hào)可以在用戶空間進(jìn)程和內(nèi)核之間直接交互，內(nèi)核可以利用信號(hào)來(lái)通知用戶空間的進(jìn)程發(fā)生了哪些系統(tǒng)事件。

”

• 信號(hào)是Linux系統(tǒng)中常用的一種進(jìn)程間的通信方式，可以在任何時(shí)刻向進(jìn)程進(jìn)行通信，而不需要知道進(jìn)程的狀態(tài)
• 如果當(dāng)前進(jìn)程并未處于執(zhí)行狀態(tài)，那么該信號(hào)會(huì)保存在內(nèi)核中，當(dāng)進(jìn)程進(jìn)行執(zhí)行時(shí)傳遞給進(jìn)程
• 如果該進(jìn)程將信號(hào)設(shè)置為阻塞，那么該信號(hào)將會(huì)被延時(shí)傳遞，直到阻塞取消

也就是說(shuō)信號(hào)主要是在進(jìn)程與內(nèi)核直接進(jìn)行傳遞，可以用于控制進(jìn)程終止退出等，信號(hào)事件主要有兩個(gè)來(lái)源

• 硬件來(lái)源：用戶按鍵輸入Ctrl+C退出、硬件異常如無(wú)效的存儲(chǔ)訪問(wèn)等。
• 軟件終止：終止進(jìn)程信號(hào)、其他進(jìn)程調(diào)用kill函數(shù)、軟件異常產(chǎn)生信號(hào)。

Linux中的信號(hào)有：

（1）SIGHUP：用戶從終端注銷(xiāo)，所有已啟動(dòng)進(jìn)程都將收到該進(jìn)程。系統(tǒng)缺省狀態(tài)下對(duì)該信號(hào)的處理是終止進(jìn)程。（2）SIGINT：程序終止信號(hào)。程序運(yùn)行過(guò)程中，按Ctrl+C鍵將產(chǎn)生該信號(hào)。（3）SIGQUIT：程序退出信號(hào)。程序運(yùn)行過(guò)程中，按Ctrl+\\鍵將產(chǎn)生該信號(hào)。（4）SIGBUS和SIGSEGV：進(jìn)程訪問(wèn)非法地址。（5）SIGFPE：運(yùn)算中出現(xiàn)致命錯(cuò)誤，如除零操作、數(shù)據(jù)溢出等。（6）SIGKILL：用戶終止進(jìn)程執(zhí)行信號(hào)。shell下執(zhí)行kill -9發(fā)送該信號(hào)。（7）SIGTERM：結(jié)束進(jìn)程信號(hào)。shell下執(zhí)行kill 進(jìn)程pid發(fā)送該信號(hào)。（8）SIGALRM：定時(shí)器信號(hào)。（9）SIGCLD：子進(jìn)程退出信號(hào)。如果其父進(jìn)程沒(méi)有忽略該信號(hào)也沒(méi)有處理該信號(hào)，則子進(jìn)程退出后將形成僵尸進(jìn)程。

消息隊(duì)列：

我們知道對(duì)于管道是存在阻塞機(jī)制的，如果一端要傳遞數(shù)據(jù)那么直到另一端接收數(shù)據(jù)后進(jìn)程才可以返回，那么可不可以讓進(jìn)程將數(shù)據(jù)放在某個(gè)內(nèi)存之后就立刻返回呢？

答案就是消息隊(duì)列的通信模式，A進(jìn)程將數(shù)據(jù)放在消息隊(duì)列后就返回了，如果之后B進(jìn)程需要就去消息隊(duì)列中取。這個(gè)有點(diǎn)類似緩存。

當(dāng)然這個(gè)方式解決了管道只能單向傳輸，存在阻塞機(jī)制的問(wèn)題，但是如果通信的數(shù)據(jù)過(guò)大，在反復(fù)通信的情況下，系統(tǒng)消耗還是比較嚴(yán)重。

注意：匿名管道是存在于內(nèi)存文件，中具名管道存在于系統(tǒng)磁盤(pán)中，而消息隊(duì)列是存在于內(nèi)核中的。

共享內(nèi)存：

既然消息隊(duì)列還是存在拷貝大量數(shù)據(jù)時(shí)效率不高的問(wèn)題，那么如果兩個(gè)進(jìn)程可以共享一塊內(nèi)存那這個(gè)問(wèn)題不就解決了？

其實(shí)系統(tǒng)分配給進(jìn)程的不是真實(shí)的物理內(nèi)存，而是地址空間，我們讓多個(gè)進(jìn)程共享一塊地址空間就可以讓進(jìn)程間通信達(dá)到最快的速度，但每個(gè)進(jìn)程依然擁有自己獨(dú)立的地址空間，只有一部分是共享的。

信號(hào)量：

我們知道JS設(shè)計(jì)成單線程本質(zhì)上是為了如果存在多個(gè)線程同時(shí)修改DOM，那么頁(yè)面中的DOM究竟是處于什么狀態(tài)？

信號(hào)量的目的本質(zhì)上也是為了解決如果多個(gè)線程共享內(nèi)存，一個(gè)線程在使用內(nèi)存的時(shí)候讓其他線程不再使用，防止同時(shí)修改出現(xiàn)問(wèn)題。

信號(hào)量本質(zhì)上就是計(jì)數(shù)器，原理就是假設(shè)初始信號(hào)量為1，如果A進(jìn)程訪問(wèn)內(nèi)存的時(shí)候?qū)⑿盘?hào)量置為0，其他內(nèi)存要訪問(wèn)的時(shí)候看見(jiàn)信號(hào)量為0就不再訪問(wèn)了。

Socket：

如果上面說(shuō)的進(jìn)程之間的通信是在同一個(gè)計(jì)算機(jī)之中的話，那么Socket套接字便是為處于不同計(jì)算機(jī)之間進(jìn)程通信提供了一種方式。


                         


我們可以看見(jiàn)其處于應(yīng)用層與傳輸層之間，是應(yīng)用層與傳輸層之間的橋梁。


差不多就是這些了，雖然也就只有幾個(gè)但是我還是查看了許多的文章，希望可以簡(jiǎn)單好理解的總結(jié)出來(lái)，很多太復(fù)雜的我也不愿去記了，畢竟這部分日常使用的也比較少。

五、請(qǐng)說(shuō)說(shuō)磁盤(pán)調(diào)度（尋道）算法？

先來(lái)看看磁盤(pán)結(jié)構(gòu)：



常見(jiàn)的機(jī)械磁盤(pán)是上圖左邊的樣子，中間圓的部分是磁盤(pán)的盤(pán)片，一般會(huì)有多個(gè)盤(pán)片，每個(gè)盤(pán)面都有自己的磁頭。右邊的圖就是一個(gè)盤(pán)片的結(jié)構(gòu)，盤(pán)片中的每一層分為多個(gè)磁道，每個(gè)磁道分多個(gè)扇區(qū)，每個(gè)扇區(qū)是 512 字節(jié)。那么，多個(gè)具有相同編號(hào)的磁道形成一個(gè)圓柱，稱之為磁盤(pán)的柱面，如上圖里中間的樣子。

磁盤(pán)調(diào)度算法的目的很簡(jiǎn)單，就是為了提高磁盤(pán)的訪問(wèn)性能，一般是通過(guò)優(yōu)化磁盤(pán)的訪問(wèn)請(qǐng)求順序來(lái)做到的。

尋道的時(shí)間是磁盤(pán)訪問(wèn)最耗時(shí)的部分，如果請(qǐng)求順序優(yōu)化的得當(dāng)，必然可以節(jié)省一些不必要的尋道時(shí)間，從而提高磁盤(pán)的訪問(wèn)性能。

接下來(lái)主要介紹一下幾種尋道算法：

• 先來(lái)先服務(wù)算法
• 最短尋道時(shí)間優(yōu)先算法
• 掃描算法算法
• 循環(huán)掃描算法
• LOOK 與 C-LOOK 算法

先來(lái)先服務(wù)算法 FCFS：

根據(jù)進(jìn)程訪問(wèn)磁盤(pán)的先后順序來(lái)進(jìn)行調(diào)度。

優(yōu)點(diǎn)：簡(jiǎn)單，公平每一個(gè)進(jìn)程的請(qǐng)求都能依次得到處理，不會(huì)出現(xiàn)某一進(jìn)程的請(qǐng)求長(zhǎng)期得不到滿足的情況。

缺點(diǎn)：由于此算法未對(duì)尋道進(jìn)行優(yōu)化，導(dǎo)致平均尋道時(shí)間較長(zhǎng)。

最短時(shí)間優(yōu)先算法 SSTF：

優(yōu)先處理距當(dāng)前磁頭距離最近的磁道上的進(jìn)程請(qǐng)求。

優(yōu)點(diǎn)：在性能上要優(yōu)于先來(lái)先服務(wù)算法，可以使每次尋道時(shí)間最短。

缺點(diǎn)：如果在動(dòng)態(tài)的請(qǐng)求情況下，可能會(huì)出現(xiàn)饑餓問(wèn)題，導(dǎo)致磁頭一直在一個(gè)小范圍移動(dòng)，有些進(jìn)程的請(qǐng)求永遠(yuǎn)無(wú)法得到處理。

掃描算法（電梯算法） SCAN：

因?yàn)樽疃虝r(shí)間優(yōu)先算法會(huì)造成饑餓問(wèn)題，也就是有些磁路可能訪問(wèn)不到，導(dǎo)致磁頭總在一個(gè)小范圍移動(dòng)，所以我們讓磁頭一直沿一個(gè)方向移動(dòng)直到到達(dá)這個(gè)方向上最后一個(gè)磁道再更換方向，因?yàn)檫@樣尋道的過(guò)程十分類似于電梯，所以又稱為電梯算法。

優(yōu)點(diǎn)：這種尋道算法的性能比較好，且不會(huì)出現(xiàn)饑餓問(wèn)題。

缺點(diǎn)：中間的磁道會(huì)比較占便宜，中間部分磁道的響應(yīng)頻率會(huì)比較高，也就是每個(gè)磁道響應(yīng)的頻率并不均勻。

循環(huán)掃描算法 CSCAN：

因?yàn)閽呙杷惴〞?huì)造成每個(gè)磁道響應(yīng)的處理頻率并不均勻，所以我們有了循環(huán)掃描算法，讓磁頭一直向一個(gè)方向移動(dòng)，直到這個(gè)方向上的所有磁道響應(yīng)處理完到達(dá)這個(gè)方向上最后一個(gè)磁道，我們快速再讓磁頭移動(dòng)到另一方的邊緣，移動(dòng)的過(guò)程中不會(huì)處理其他的請(qǐng)求，之后再次向同一方向移動(dòng)。也就是說(shuō)其只在解決某一方向上的請(qǐng)求。

循環(huán)掃描算法解決了解決了掃描算法對(duì)每個(gè)磁道上的響應(yīng)處理不均勻的問(wèn)題，是比較完美的一種算法。

LOOK與C-LOOK：

Look:


LOOK與C-LOOK是針對(duì)掃描算法與循環(huán)掃描每次需要到達(dá)某一方向上最后一個(gè)磁道才返回的問(wèn)題，優(yōu)化后只要處理完某一方向上最后一個(gè)請(qǐng)求就更改方向，而不需要到達(dá)最后一個(gè)磁道了。


C-LOOK：

六、談?wù)勀銓?duì)死鎖的理解

死鎖的定義：

在一個(gè)集合中，每一個(gè)進(jìn)程都在等待，這個(gè)集合中其他進(jìn)程才能引發(fā)的事件（資源），那么這組進(jìn)程就是死鎖的。

簡(jiǎn)單理解就是假如A進(jìn)程運(yùn)行中需要獲取a資源，但是a資源被B進(jìn)程所占用了，那么A進(jìn)程就無(wú)法繼續(xù)執(zhí)行下去且A進(jìn)程已經(jīng)獲取的資源b無(wú)法釋放，就一直卡在那里，過(guò)了一會(huì)B進(jìn)程也需要獲取b資源了由于A進(jìn)程卡在那里兩者都無(wú)法繼續(xù)運(yùn)行下去，這就發(fā)生了死鎖。

所以死鎖的本質(zhì)就是進(jìn)程之間由于資源的競(jìng)爭(zhēng)（也可以理解為資源獲取順序的不當(dāng)）而造成彼此之間都無(wú)法繼續(xù)運(yùn)行的情況。

注意：上面所說(shuō)的資源可以是很多東西如：鎖，網(wǎng)絡(luò)連接，通知事件，磁盤(pán)等。

死鎖發(fā)生的必要條件：

• 互斥條件：同一時(shí)間，同一資源只可以被一個(gè)進(jìn)程所占用，當(dāng)該資源被占用時(shí)其他進(jìn)程便不可以使用
• 請(qǐng)求和保持條件：當(dāng)一個(gè)進(jìn)程運(yùn)行時(shí)需要獲取的資源，被另一進(jìn)程所占用時(shí)，這個(gè)進(jìn)程將一直處于請(qǐng)求狀態(tài)，當(dāng)前所占用的資源也無(wú)法被釋放
• 不可剝奪條件：當(dāng)一進(jìn)程使用某一資源時(shí)，該資源便不可以被其他進(jìn)程所使用，直到該資源被釋放
• 環(huán)路等待條件：在發(fā)生死鎖的進(jìn)程組內(nèi)，一個(gè)進(jìn)程將會(huì)占有另一進(jìn)程所需要的資源從而形成一個(gè)等待閉環(huán)

如何預(yù)防以及避免死鎖：

1.合理的規(guī)劃資源使用順序

既然死鎖的發(fā)生多數(shù)是因?yàn)橘Y源分配時(shí)間不合理而造成的那么我們就制定更加合理的資源使用順序從而盡可能的避免死鎖的發(fā)生。

比如原先進(jìn)程A需要先使用資源a然后再使用資源b，而B(niǎo)進(jìn)程需要先使用資源c再使用資源b，那么極有可能發(fā)生死鎖的情況，我們可以讓進(jìn)程B進(jìn)程先使用資源b使用完釋放后再去使用資源c，這樣來(lái)盡可能的避免死鎖的發(fā)生。

上面只是舉例說(shuō)明一下可以通過(guò)合理的資源分配來(lái)盡可能的避免死鎖的發(fā)生。


2.設(shè)置最大資源占用時(shí)間

當(dāng)某一進(jìn)程需要請(qǐng)求使用某一資源而該資源被其他進(jìn)程所占用時(shí)，其會(huì)一直保持當(dāng)前已經(jīng)獲取資源的占用而處于等待狀態(tài)，從而可能造成其他進(jìn)程也無(wú)法對(duì)資源的使用，從而造成死鎖現(xiàn)象。

既然死鎖可能由于資源被某一進(jìn)程長(zhǎng)時(shí)間占用所導(dǎo)致那么我們就設(shè)置該資源的最大占用時(shí)間，一但超過(guò)時(shí)間便主動(dòng)釋放。


3.預(yù)先分配所需資源

當(dāng)某一進(jìn)程運(yùn)行時(shí)再去獲取其需要的資源，如果該資源正處于被其他進(jìn)程所占用狀態(tài)那么很有可能造成死鎖情況，所以當(dāng)進(jìn)程運(yùn)行前我們可以提前分配給該進(jìn)程運(yùn)行時(shí)所有所需要的資源，這樣也可以盡可能避免死鎖。

但是這樣會(huì)導(dǎo)致該資源的利用率降低，某些資源并不是在進(jìn)程運(yùn)行時(shí)一直被需要。

4.銀行家算法

銀行家善于計(jì)算??，所以銀行家算法就是對(duì)當(dāng)前所有進(jìn)程正在使用的資源，以及將要使用的資源，以及剩余可利用的資源進(jìn)行計(jì)算從而分析出當(dāng)前狀態(tài)是否安全，確保資源充足不會(huì)發(fā)生死鎖。

檢測(cè)死鎖：

我們可以使用一些算法來(lái)定時(shí)檢測(cè)在系統(tǒng)中是否有死鎖發(fā)生，如檢測(cè)當(dāng)前內(nèi)存資源的利用率等。

解除死鎖：

當(dāng)檢測(cè)到死鎖發(fā)生后我們便需要解決死鎖，最直接的方式就是重啟電腦，但是作為一名程序員我們應(yīng)該更專業(yè)一些。

• 終止相關(guān)進(jìn)程：檢測(cè)到發(fā)生死鎖的進(jìn)程撤銷(xiāo)或者掛起它，強(qiáng)制其釋放內(nèi)存
• 剝奪資源：強(qiáng)行將進(jìn)程所占用的資源剝奪出來(lái)，解除死鎖
• 進(jìn)程回退：將死鎖進(jìn)程回退到未出問(wèn)題之前，不過(guò)比較難以實(shí)現(xiàn)

七、參考：

知乎 小林coding 大廠面試愛(ài)問(wèn)的「調(diào)度算法」，20 張圖一舉拿下^[1]

參考

小獅子有話說(shuō)

你好，我是 Chocolate，一個(gè)獅子座的前端攻城獅，希望成為優(yōu)秀的前端博主，每周都會(huì)更新文章，與你一起變優(yōu)秀~

1. 關(guān)注小獅子前端，回復(fù)【小獅子】獲取為大家整理好的文章、資源合集
2. 我的博客地址：yangchaoyi.vip 歡迎收藏，可在博客留言板留下你的足跡，一起交流~
3. 覺(jué)得文章不錯(cuò)，【點(diǎn)贊】【在看】支持一波 ??ヽ(°▽°)ノ?

叮咚~ 可以給小獅子加星標(biāo)，便于查找。感謝加入小獅子前端，最好的我們最美的遇見(jiàn)，我們下期再見(jiàn)~