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

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

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

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

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

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

長作業(yè)有可能會餓死，處于一直等待短作業(yè)執(zhí)行完畢的狀態(tài)。因為如果一直有短作業(yè)到來，那么長作業(yè)永遠得不到調(diào)度。

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

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

如果新的進程需要的時間更少，則掛起當前進程，運行新的進程。否則新的進程等待。

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

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

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

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

因為進程切換都要保存進程的信息并且載入新進程的信息，如果時間片太小，會導(dǎo)致進程切換得太頻繁，在進程切換上就會花過多時間。

而如果時間片過長，那么實時性就不能得到保證。

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

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

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

6、多級反饋隊列  

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

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

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

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

7、Linux下進程間通信方式？

管道：

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

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

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

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

套接字：適用于不同機器間進程通信，在本地也可作為兩個進程通信的方式。

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

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

8、Linux下同步機制？

POSIX信號量：可用于進程同步，也可用于線程同步。

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

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

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

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

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

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

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

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

由于查詢快表的速度比查詢頁表的速度快很多，因此只要快表命中，就可以節(jié)省很多時間。
因為局部性原理，–般來說快表的命中率可以達到90％以上。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5、總結(jié)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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