動態分區分配算法有哪幾種？
6、進程調度算法你了解多少？
1、 先來先服務 first－come first－serverd（FCFS）
非搶占式的調度算法，按照請求的順序進行調度。
有利于長作業，但不利于短作業，因為短作業必須一直等待前面的長作業執行完畢才能執行，而長作業又需要執行很長時間，造成了短作業等待時間過長。
2、 短作業優先 shortest job first（SJF）
非搶占式的調度算法，按估計運行時間最短的順序進行調度。
長作業有可能會餓死，處于一直等待短作業執行完畢的狀態。因為如果一直有短作業到來，那么長作業永遠得不到調度。
3、最短剩余時間優先 shortest remaining time next（SRTN）
最短作業優先的搶占式版本，按剩余運行時間的順序進行調度。當一個新的作業到達時，其整個運行時間與當前進程的剩余時間作比較。
如果新的進程需要的時間更少，則掛起當前進程，運行新的進程。否則新的進程等待。
4、時間片輪轉
將所有就緒進程按 FCFS 的原則排成一個隊列，每次調度時，把 CPU 時間分配給隊首進程，該進程可以執行一個時間片。
當時間片用完時，由計時器發出時鐘中斷，調度程序便停止該進程的執行，并將它送往就緒隊列的末尾，同時繼續把 CPU 時間分配給隊首的進程。
時間片輪轉算法的效率和時間片的大小有很大關系：
因為進程切換都要保存進程的信息并且載入新進程的信息，如果時間片太小，會導致進程切換得太頻繁，在進程切換上就會花過多時間。
而如果時間片過長，那么實時性就不能得到保證。
5、優先級調度
為每個進程分配一個優先級，按優先級進行調度。
為了防止低優先級的進程永遠等不到調度，可以隨著時間的推移增加等待進程的優先級。
6、多級反饋隊列
一個進程需要執行 100 個時間片，如果采用時間片輪轉調度算法，那么需要交換 100 次。
多級隊列是為這種需要連續執行多個時間片的進程考慮，它設置了多個隊列，每個隊列時間片大小都不同，例如 1，2，4，8，．．。進程在第一個隊列沒執行完，就會被移到下一個隊列。
這種方式下，之前的進程只需要交換 7 次。每個隊列優先權也不同，最上面的優先權最高。因此只有上一個隊列沒有進程在排隊，才能調度當前隊列上的進程。
可以將這種調度算法看成是時間片輪轉調度算法和優先級調度算法的結合。
7、Linux下進程間通信方式？
管道：
無名管道（內存文件）：管道是一種半雙工的通信方式，數據只能單向流動，而且只能在具有親緣關系的進程之間使用。進程的親緣關系通常是指父子進程關系。
有名管道（FIFO文件，借助文件系統）：有名管道也是半雙工的通信方式，但是允許在沒有親緣關系的進程之間使用，管道是先進先出的通信方式。
共享內存：共享內存就是映射一段能被其他進程所訪問的內存，這段共享內存由一個進程創建，但多個進程都可以訪問。共享內存是最快的IPC方式，它是針對其他進程間通信方式運行效率低而專門設計的。它往往與信號量，配合使用來實現進程間的同步和通信。
消息隊列：消息隊列是有消息的鏈表，存放在內核中并由消息隊列標識符標識。消息隊列克服了信號傳遞信息少、管道只能承載無格式字節流以及緩沖區大小受限等缺點。
套接字：適用于不同機器間進程通信，在本地也可作為兩個進程通信的方式。
信號：用于通知接收進程某個事件已經發生，比如按下ctrl ＋ C就是信號。
信號量：信號量是一個計數器，可以用來控制多個進程對共享資源的訪問。它常作為一種鎖機制，實現進程、線程的對臨界區的同步及互斥訪問。
8、Linux下同步機制？
POSIX信號量：可用于進程同步，也可用于線程同步。
POSIX互斥鎖 ＋ 條件變量：只能用于線程同步。
線程和進程的區別？
調度：線程是調度的基本單位（PC，狀態碼，通用寄存器，線程棧及棧指針）；進程是擁有資源的基本單位（打開文件，堆，靜態區，代碼段等）。
并發性：一個進程內多個線程可以并發（最好和CPU核數相等）；多個進程可以并發。
擁有資源：線程不擁有系統資源，但一個進程的多個線程可以共享隸屬進程的資源；進程是擁有資源的獨立單位。
系統開銷：線程創建銷毀只需要處理PC值，狀態碼，通用寄存器值，線程棧及棧指針即可；進程創建和銷毀需要重新分配及銷毀task＿struct結構。
9、如果系統中具有快表后，那么地址的轉換過程變成什么樣了？
①CPU給出邏輯地址，由某個硬件算得頁號、頁內偏移量，將頁號與快表中的所有頁號進行比較。②如果找到匹配的頁號，說明要訪問的頁表項在快表中有副本，則直接從中取出該頁對應的內存塊號，再將內存塊號與頁內偏移量拼接形成物理地址，最后，訪問該物理地址對應的內存單元。因此，若快表命中，則訪問某個邏輯地址僅需一次訪存即可。
③如果沒有找到匹配的頁號，則需要訪問內存中的頁表，找到對應頁表項，得到頁面存放的內存塊號，再將內存塊號與頁內偏移量拼接形成物理地址，最后，訪問該物理地址對應的內存單元。因此，若快表未命中，則訪問某個邏輯地址需要兩次訪存（注意：在找到頁表項后，應同時將其存入快表，以便后面可能的再次訪問。但若快表已滿，則必須按照－定的算法對舊的頁表項進行替換）
由于查詢快表的速度比查詢頁表的速度快很多，因此只要快表命中，就可以節省很多時間。
因為局部性原理，–般來說快表的命中率可以達到90％以上。
例：某系統使用基本分頁存儲管理，并采用了具有快表的地址變換機構。訪問－ －次快表耗時1us， 訪問一次內存耗時100us。若快表的命中率為90％，那么訪問一個邏輯地址的平均耗時是多少？
（1＋100） ＊ 0．9 ＋ （1＋100＋100） ＊ 0．1 ＝ 111 us
有的系統支持快表和慢表同時查找，如果是這樣，平均耗時應該是（1＋100） ＊ 0．9＋ （100＋100） ＊0．1＝110．9 us
若未采用快表機制，則訪問一個邏輯地址需要100＋100 ＝ 200us
顯然，引入快表機制后，訪問一個邏輯地址的速度快多了。
10、內存交換和覆蓋有什么區別？
交換技術主要是在不同進程（或作業）之間進行，而覆蓋則用于同一程序或進程中。
11、動態分區分配算法有哪幾種？可以分別說說嗎？
1、首次適應算法
算法思想：每次都從低地址開始查找，找到第–個能滿足大小的空閑分區。
如何實現：空閑分區以地址遞增的次序排列。每次分配內存時順序查找空閑分區鏈（ 或空閑分［表），找到大小能滿足要求的第－一個空閑分區。
2、最佳適應算法
算法思想：由于動態分區分配是一種連續分配方式，為各進程分配的空間必須是連續的一整片區域。因此為了保證當“大進程”到來時能有連續的大片空間，可以盡可能多地留下大片的空閑區，即，優先使用更小的空閑區。
如何實現：空閑分區按容量遞增次序鏈接。每次分配內存時順序查找空閑分區鏈（或空閑分區表），找到大小能滿足要求的第－一個空閑分區。
3、最壞適應算法
又稱最大適應算法（Largest Fit）
算法思想：為了解決最佳適應算法的問題—即留下太多難以利用的小碎片，可以在每次分配時優先使用最大的連續空閑區，這樣分配后剩余的空閑區就不會太小，更方便使用。
如何實現：空閑分區按容量遞減次序鏈接。每次分配內存時順序查找空閑分區鏈（或空閑分區表），找到大小能滿足要求的第－一個空閑分區。
4、鄰近適應算法
算法思想：首次適應算法每次都從鏈頭開始查找的。這可能會導致低地址部分出現很多小的空閑分區，而每次分配查找時，都要經過這些分區，因此也增加了查找的開銷。如果每次都從上次查找結束的位置開始檢索，就能解決上述問題。
如何實現：空閑分區以地址遞增的順序排列（可排成－一個循環鏈表）。每次分配內存時從上次查找結束的位置開始查找空閑分區鏈（或空閑分區表），找到大小能滿足要求的第一個空閑分區。
5、總結
首次適應不僅最簡單，通常也是最好最快，不過首次適應算法會使得內存低地址部分出現很多小的空閑分區，而每次查找都要經過這些分區，因此也增加了查找的開銷。鄰近算法試圖解決這個問題，但實際上，它常常會導致在內存的末尾分配空間分裂成小的碎片，它通常比首次適應算法結果要差。
最佳導致大量碎片，最壞導致沒有大的空間。
進過實驗，首次適應比最佳適應要好，他們都比最壞好。
12、虛擬技術你了解嗎？
虛擬技術把一個物理實體轉換為多個邏輯實體。
主要有兩種虛擬技術：時（時間）分復用技術和空（空間）分復用技術。
多進程與多線程：多個進程能在同一個處理器上并發執行使用了時分復用技術，讓每個進程輪流占用處理器，每次只執行一小個時間片并快速切換。
虛擬內存使用了空分復用技術，它將物理內存抽象為地址空間，每個進程都有各自的地址空間。地址空間的頁被映射到物理內存，地址空間的頁并不需要全部在物理內存中，當使用到一個沒有在物理內存的頁時，執行頁面置換算法，將該頁置換到內存中。
13、進程狀態的切換你知道多少？
就緒狀態（ready）：等待被調度
運行狀態（running）
阻塞狀態（waiting）：等待資源
應該注意以下內容：
只有就緒態和運行態可以相互轉換，其它的都是單向轉換。就緒狀態的進程通過調度算法從而獲得 CPU 時間，轉為運行狀態；而運行狀態的進程，在分配給它的 CPU 時間片用完之后就會轉為就緒狀態，等待下一次調度。
阻塞狀態是缺少需要的資源從而由運行狀態轉換而來，但是該資源不包括 CPU 時間，缺少 CPU 時間會從運行態轉換為就緒態。
分享
請輸入評論內容...
請輸入評論/評論長度6~500個字
