6、進(jìn)程調(diào)度算法你了解多少？

1、 先來先服務(wù) first－come first－serverd（FCFS）  

非搶占式的調(diào)度算法，按照請(qǐng)求的順序進(jìn)行調(diào)度。

有利于長(zhǎng)作業(yè)，但不利于短作業(yè)，因?yàn)槎套鳂I(yè)必須一直等待前面的長(zhǎng)作業(yè)執(zhí)行完畢才能執(zhí)行，而長(zhǎng)作業(yè)又需要執(zhí)行很長(zhǎng)時(shí)間，造成了短作業(yè)等待時(shí)間過長(zhǎng)。

2、 短作業(yè)優(yōu)先 shortest job first（SJF）  

非搶占式的調(diào)度算法，按估計(jì)運(yùn)行時(shí)間最短的順序進(jìn)行調(diào)度。

長(zhǎng)作業(yè)有可能會(huì)餓死，處于一直等待短作業(yè)執(zhí)行完畢的狀態(tài)。因?yàn)槿绻�一直有短作業(yè)到來，那么長(zhǎng)作業(yè)永遠(yuǎn)得不到調(diào)度。

3、最短剩余時(shí)間優(yōu)先 shortest remaining time next（SRTN）  

最短作業(yè)優(yōu)先的搶占式版本，按剩余運(yùn)行時(shí)間的順序進(jìn)行調(diào)度。當(dāng)一個(gè)新的作業(yè)到達(dá)時(shí)，其整個(gè)運(yùn)行時(shí)間與當(dāng)前進(jìn)程的剩余時(shí)間作比較。

如果新的進(jìn)程需要的時(shí)間更少，則掛起當(dāng)前進(jìn)程，運(yùn)行新的進(jìn)程。否則新的進(jìn)程等待。

4、時(shí)間片輪轉(zhuǎn)  

將所有就緒進(jìn)程按 FCFS 的原則排成一個(gè)隊(duì)列，每次調(diào)度時(shí)，把 CPU 時(shí)間分配給隊(duì)首進(jìn)程，該進(jìn)程可以執(zhí)行一個(gè)時(shí)間片。

當(dāng)時(shí)間片用完時(shí)，由計(jì)時(shí)器發(fā)出時(shí)鐘中斷，調(diào)度程序便停止該進(jìn)程的執(zhí)行，并將它送往就緒隊(duì)列的末尾，同時(shí)繼續(xù)把 CPU 時(shí)間分配給隊(duì)首的進(jìn)程。

時(shí)間片輪轉(zhuǎn)算法的效率和時(shí)間片的大小有很大關(guān)系：

因?yàn)檫M(jìn)程切換都要保存進(jìn)程的信息并且載入新進(jìn)程的信息，如果時(shí)間片太小，會(huì)導(dǎo)致進(jìn)程切換得太頻繁，在進(jìn)程切換上就會(huì)花過多時(shí)間。

而如果時(shí)間片過長(zhǎng)，那么實(shí)時(shí)性就不能得到保證。

5、優(yōu)先級(jí)調(diào)度  

為每個(gè)進(jìn)程分配一個(gè)優(yōu)先級(jí)，按優(yōu)先級(jí)進(jìn)行調(diào)度。

為了防止低優(yōu)先級(jí)的進(jìn)程永遠(yuǎn)等不到調(diào)度，可以隨著時(shí)間的推移增加等待進(jìn)程的優(yōu)先級(jí)。

6、多級(jí)反饋隊(duì)列  

一個(gè)進(jìn)程需要執(zhí)行 100 個(gè)時(shí)間片，如果采用時(shí)間片輪轉(zhuǎn)調(diào)度算法，那么需要交換 100 次。

多級(jí)隊(duì)列是為這種需要連續(xù)執(zhí)行多個(gè)時(shí)間片的進(jìn)程考慮，它設(shè)置了多個(gè)隊(duì)列，每個(gè)隊(duì)列時(shí)間片大小都不同，例如 1，2，4，8，．．。進(jìn)程在第一個(gè)隊(duì)列沒執(zhí)行完，就會(huì)被移到下一個(gè)隊(duì)列。

這種方式下，之前的進(jìn)程只需要交換 7 次。每個(gè)隊(duì)列優(yōu)先權(quán)也不同，最上面的優(yōu)先權(quán)最高。因此只有上一個(gè)隊(duì)列沒有進(jìn)程在排隊(duì)，才能調(diào)度當(dāng)前隊(duì)列上的進(jìn)程。

可以將這種調(diào)度算法看成是時(shí)間片輪轉(zhuǎn)調(diào)度算法和優(yōu)先級(jí)調(diào)度算法的結(jié)合。

7、Linux下進(jìn)程間通信方式？

管道：

無名管道（內(nèi)存文件）：管道是一種半雙工的通信方式，數(shù)據(jù)只能單向流動(dòng)，而且只能在具有親緣關(guān)系的進(jìn)程之間使用。進(jìn)程的親緣關(guān)系通常是指父子進(jìn)程關(guān)系。

有名管道（FIFO文件，借助文件系統(tǒng)）：有名管道也是半雙工的通信方式，但是允許在沒有親緣關(guān)系的進(jìn)程之間使用，管道是先進(jìn)先出的通信方式。

共享內(nèi)存：共享內(nèi)存就是映射一段能被其他進(jìn)程所訪問的內(nèi)存，這段共享內(nèi)存由一個(gè)進(jìn)程創(chuàng)建，但多個(gè)進(jìn)程都可以訪問。共享內(nèi)存是最快的IPC方式，它是針對(duì)其他進(jìn)程間通信方式運(yùn)行效率低而專門設(shè)計(jì)的。它往往與信號(hào)量，配合使用來實(shí)現(xiàn)進(jìn)程間的同步和通信。

消息隊(duì)列：消息隊(duì)列是有消息的鏈表，存放在內(nèi)核中并由消息隊(duì)列標(biāo)識(shí)符標(biāo)識(shí)。消息隊(duì)列克服了信號(hào)傳遞信息少、管道只能承載無格式字節(jié)流以及緩沖區(qū)大小受限等缺點(diǎn)。

套接字：適用于不同機(jī)器間進(jìn)程通信，在本地也可作為兩個(gè)進(jìn)程通信的方式。

信號(hào)：用于通知接收進(jìn)程某個(gè)事件已經(jīng)發(fā)生，比如按下ctrl ＋ C就是信號(hào)。

信號(hào)量：信號(hào)量是一個(gè)計(jì)數(shù)器，可以用來控制多個(gè)進(jìn)程對(duì)共享資源的訪問。它常作為一種鎖機(jī)制，實(shí)現(xiàn)進(jìn)程、線程的對(duì)臨界區(qū)的同步及互斥訪問。

8、Linux下同步機(jī)制？

POSIX信號(hào)量：可用于進(jìn)程同步，也可用于線程同步。

POSIX互斥鎖 ＋ 條件變量：只能用于線程同步。

線程和進(jìn)程的區(qū)別？

調(diào)度：線程是調(diào)度的基本單位（PC，狀態(tài)碼，通用寄存器，線程棧及棧指針）；進(jìn)程是擁有資源的基本單位（打開文件，堆，靜態(tài)區(qū)，代碼段等）。

并發(fā)性：一個(gè)進(jìn)程內(nèi)多個(gè)線程可以并發(fā)（最好和CPU核數(shù)相等）；多個(gè)進(jìn)程可以并發(fā)。

擁有資源：線程不擁有系統(tǒng)資源，但一個(gè)進(jìn)程的多個(gè)線程可以共享隸屬進(jìn)程的資源；進(jìn)程是擁有資源的獨(dú)立單位。

系統(tǒng)開銷：線程創(chuàng)建銷毀只需要處理PC值，狀態(tài)碼，通用寄存器值，線程棧及棧指針即可；進(jìn)程創(chuàng)建和銷毀需要重新分配及銷毀task＿struct結(jié)構(gòu)。

9、如果系統(tǒng)中具有快表后，那么地址的轉(zhuǎn)換過程變成什么樣了？

①CPU給出邏輯地址，由某個(gè)硬件算得頁(yè)號(hào)、頁(yè)內(nèi)偏移量，將頁(yè)號(hào)與快表中的所有頁(yè)號(hào)進(jìn)行比較。②如果找到匹配的頁(yè)號(hào)，說明要訪問的頁(yè)表項(xiàng)在快表中有副本，則直接從中取出該頁(yè)對(duì)應(yīng)的內(nèi)存塊號(hào)，再將內(nèi)存塊號(hào)與頁(yè)內(nèi)偏移量拼接形成物理地址，最后，訪問該物理地址對(duì)應(yīng)的內(nèi)存單元。因此，若快表命中，則訪問某個(gè)邏輯地址僅需一次訪存即可。
③如果沒有找到匹配的頁(yè)號(hào)，則需要訪問內(nèi)存中的頁(yè)表，找到對(duì)應(yīng)頁(yè)表項(xiàng)，得到頁(yè)面存放的內(nèi)存塊號(hào)，再將內(nèi)存塊號(hào)與頁(yè)內(nèi)偏移量拼接形成物理地址，最后，訪問該物理地址對(duì)應(yīng)的內(nèi)存單元。因此，若快表未命中，則訪問某個(gè)邏輯地址需要兩次訪存（注意：在找到頁(yè)表項(xiàng)后，應(yīng)同時(shí)將其存入快表，以便后面可能的再次訪問。但若快表已滿，則必須按照－定的算法對(duì)舊的頁(yè)表項(xiàng)進(jìn)行替換）

由于查詢快表的速度比查詢頁(yè)表的速度快很多，因此只要快表命中，就可以節(jié)省很多時(shí)間。
因?yàn)榫植啃栽�理，–般來說快表的命中率可以達(dá)到90％以上。

例：某系統(tǒng)使用基本分頁(yè)存儲(chǔ)管理，并采用了具有快表的地址變換機(jī)構(gòu)。訪問－ －次快表耗時(shí)1us， 訪問一次內(nèi)存耗時(shí)100us。若快表的命中率為90％，那么訪問一個(gè)邏輯地址的平均耗時(shí)是多少？
（1＋100） ＊ 0．9 ＋ （1＋100＋100） ＊ 0．1 ＝ 111 us
有的系統(tǒng)支持快表和慢表同時(shí)查找，如果是這樣，平均耗時(shí)應(yīng)該是（1＋100） ＊ 0．9＋ （100＋100） ＊0．1＝110．9 us
若未采用快表機(jī)制，則訪問一個(gè)邏輯地址需要100＋100 ＝ 200us
顯然，引入快表機(jī)制后，訪問一個(gè)邏輯地址的速度快多了。

10、內(nèi)存交換和覆蓋有什么區(qū)別？

交換技術(shù)主要是在不同進(jìn)程（或作業(yè)）之間進(jìn)行，而覆蓋則用于同一程序或進(jìn)程中。

11、動(dòng)態(tài)分區(qū)分配算法有哪幾種？可以分別說說嗎？

1、首次適應(yīng)算法

算法思想：每次都從低地址開始查找，找到第–個(gè)能滿足大小的空閑分區(qū)。

如何實(shí)現(xiàn)：空閑分區(qū)以地址遞增的次序排列。每次分配內(nèi)存時(shí)順序查找空閑分區(qū)鏈（ 或空閑分［表），找到大小能滿足要求的第－一個(gè)空閑分區(qū)。

2、最佳適應(yīng)算法

算法思想：由于動(dòng)態(tài)分區(qū)分配是一種連續(xù)分配方式，為各進(jìn)程分配的空間必須是連續(xù)的一整片區(qū)域。因此為了保證當(dāng)“大進(jìn)程”到來時(shí)能有連續(xù)的大片空間，可以盡可能多地留下大片的空閑區(qū)，即，優(yōu)先使用更小的空閑區(qū)。

如何實(shí)現(xiàn)：空閑分區(qū)按容量遞增次序鏈接。每次分配內(nèi)存時(shí)順序查找空閑分區(qū)鏈（或空閑分區(qū)表），找到大小能滿足要求的第－一個(gè)空閑分區(qū)。

3、最壞適應(yīng)算法

又稱最大適應(yīng)算法（Largest Fit）

算法思想：為了解決最佳適應(yīng)算法的問題—即留下太多難以利用的小碎片，可以在每次分配時(shí)優(yōu)先使用最大的連續(xù)空閑區(qū)，這樣分配后剩余的空閑區(qū)就不會(huì)太小，更方便使用。

如何實(shí)現(xiàn)：空閑分區(qū)按容量遞減次序鏈接。每次分配內(nèi)存時(shí)順序查找空閑分區(qū)鏈（或空閑分區(qū)表），找到大小能滿足要求的第－一個(gè)空閑分區(qū)。

4、鄰近適應(yīng)算法

算法思想：首次適應(yīng)算法每次都從鏈頭開始查找的。這可能會(huì)導(dǎo)致低地址部分出現(xiàn)很多小的空閑分區(qū)，而每次分配查找時(shí)，都要經(jīng)過這些分區(qū)，因此也增加了查找的開銷。如果每次都從上次查找結(jié)束的位置開始檢索，就能解決上述問題。

如何實(shí)現(xiàn)：空閑分區(qū)以地址遞增的順序排列（可排成－一個(gè)循環(huán)鏈表）。每次分配內(nèi)存時(shí)從上次查找結(jié)束的位置開始查找空閑分區(qū)鏈（或空閑分區(qū)表），找到大小能滿足要求的第一個(gè)空閑分區(qū)。

5、總結(jié)

首次適應(yīng)不僅最簡(jiǎn)單，通常也是最好最快，不過首次適應(yīng)算法會(huì)使得內(nèi)存低地址部分出現(xiàn)很多小的空閑分區(qū)，而每次查找都要經(jīng)過這些分區(qū)，因此也增加了查找的開銷。鄰近算法試圖解決這個(gè)問題，但實(shí)際上，它常常會(huì)導(dǎo)致在內(nèi)存的末尾分配空間分裂成小的碎片，它通常比首次適應(yīng)算法結(jié)果要差。

最佳導(dǎo)致大量碎片，最壞導(dǎo)致沒有大的空間。

進(jìn)過實(shí)驗(yàn)，首次適應(yīng)比最佳適應(yīng)要好，他們都比最壞好。

12、虛擬技術(shù)你了解嗎？

虛擬技術(shù)把一個(gè)物理實(shí)體轉(zhuǎn)換為多個(gè)邏輯實(shí)體。

主要有兩種虛擬技術(shù)：時(shí)（時(shí)間）分復(fù)用技術(shù)和空（空間）分復(fù)用技術(shù)。

多進(jìn)程與多線程：多個(gè)進(jìn)程能在同一個(gè)處理器上并發(fā)執(zhí)行使用了時(shí)分復(fù)用技術(shù)，讓每個(gè)進(jìn)程輪流占用處理器，每次只執(zhí)行一小個(gè)時(shí)間片并快速切換。

虛擬內(nèi)存使用了空分復(fù)用技術(shù)，它將物理內(nèi)存抽象為地址空間，每個(gè)進(jìn)程都有各自的地址空間。地址空間的頁(yè)被映射到物理內(nèi)存，地址空間的頁(yè)并不需要全部在物理內(nèi)存中，當(dāng)使用到一個(gè)沒有在物理內(nèi)存的頁(yè)時(shí)，執(zhí)行頁(yè)面置換算法，將該頁(yè)置換到內(nèi)存中。

13、進(jìn)程狀態(tài)的切換你知道多少？

就緒狀態(tài)（ready）：等待被調(diào)度

運(yùn)行狀態(tài)（running）

阻塞狀態(tài)（waiting）：等待資源

應(yīng)該注意以下內(nèi)容：

只有就緒態(tài)和運(yùn)行態(tài)可以相互轉(zhuǎn)換，其它的都是單向轉(zhuǎn)換。就緒狀態(tài)的進(jìn)程通過調(diào)度算法從而獲得 CPU 時(shí)間，轉(zhuǎn)為運(yùn)行狀態(tài)；而運(yùn)行狀態(tài)的進(jìn)程，在分配給它的 CPU 時(shí)間片用完之后就會(huì)轉(zhuǎn)為就緒狀態(tài)，等待下一次調(diào)度。

阻塞狀態(tài)是缺少需要的資源從而由運(yùn)行狀態(tài)轉(zhuǎn)換而來，但是該資源不包括 CPU 時(shí)間，缺少 CPU 時(shí)間會(huì)從運(yùn)行態(tài)轉(zhuǎn)換為就緒態(tài)。