看完這篇操作系統(tǒng)，和面試官扯皮就沒問題了。

時間：2020-08-21 09:39:35

關(guān)鍵字：操作系統(tǒng)

手機(jī)看文章

掃描二維碼
隨時隨地手機(jī)看文章

[導(dǎo)讀]1 ? ? 解釋一下什么是操作系統(tǒng) 操作系統(tǒng)是運(yùn)行在計算機(jī)上最重要的一種軟件，它管理計算機(jī)的資源和進(jìn)程以及所有的硬件和軟件。它為計算機(jī)硬件和軟件提供了一種中間層通常情況下，計算機(jī)上會運(yùn)行著許多應(yīng)用程序，它們都需要對內(nèi)存和 CPU 進(jìn)行交互，操作系統(tǒng)的

解釋一下什么是操作系統(tǒng)

操作系統(tǒng)是運(yùn)行在計算機(jī)上最重要的一種軟件，它管理計算機(jī)的資源和進(jìn)程以及所有的硬件和軟件。它為計算機(jī)硬件和軟件提供了一種中間層

通常情況下，計算機(jī)上會運(yùn)行著許多應(yīng)用程序，它們都需要對內(nèi)存和 CPU 進(jìn)行交互，操作系統(tǒng)的目的就是為了保證這些訪問和交互能夠準(zhǔn)確無誤的進(jìn)行。

解釋一下操作系統(tǒng)的主要目的是什么

操作系統(tǒng)是一種軟件，它的主要目的有三種

管理計算機(jī)資源，這些資源包括 CPU、內(nèi)存、磁盤驅(qū)動器、打印機(jī)等。

提供一種圖形界面，就像我們前面描述的那樣，它提供了用戶和計算機(jī)之間的橋梁。

為其他軟件提供服務(wù)，操作系統(tǒng)與軟件進(jìn)行交互，以便為其分配運(yùn)行所需的任何必要資源。

操作系統(tǒng)的種類有哪些

操作系統(tǒng)通常預(yù)裝在你購買計算機(jī)之前。大部分用戶都會使用默認(rèn)的操作系統(tǒng)，但是你也可以升級甚至更改操作系統(tǒng)。但是一般常見的操作系統(tǒng)只有三種：Windows、macOS 和 Linux。

操作系統(tǒng)結(jié)構(gòu)

4.1

單體系統(tǒng)

在大多數(shù)系統(tǒng)中，整個系統(tǒng)在內(nèi)核態(tài)以單一程序的方式運(yùn)行。整個操作系統(tǒng)是以程序集合來編寫的，鏈接在一塊形成一個大的二進(jìn)制可執(zhí)行程序，這種系統(tǒng)稱為單體系統(tǒng)。

在單體系統(tǒng)中構(gòu)造實(shí)際目標(biāo)程序時，會首先編譯所有單個過程（或包含這些過程的文件），然后使用系統(tǒng)鏈接器將它們?nèi)拷壎ǖ揭粋€可執(zhí)行文件中

在單體系統(tǒng)中，對于每個系統(tǒng)調(diào)用都會有一個服務(wù)程序來保障和運(yùn)行。需要一組實(shí)用程序來彌補(bǔ)服務(wù)程序需要的功能，例如從用戶程序中獲取數(shù)據(jù)。可將各種過程劃分為一個三層模型

除了在計算機(jī)初啟動時所裝載的核心操作系統(tǒng)外，許多操作系統(tǒng)還支持額外的擴(kuò)展。比如 I/O 設(shè)備驅(qū)動和文件系統(tǒng)。這些部件可以按需裝載。在 UNIX 中把它們叫做共享庫(shared library)，在 Windows 中則被稱為動態(tài)鏈接庫(Dynamic Link Library,DLL)。他們的擴(kuò)展名為 .dll，在 C:\Windows\system32 目錄下存在 1000 多個 DLL 文件，所以不要輕易刪除 C 盤文件，否則可能就炸了哦。

4.2

分層系統(tǒng)

分層系統(tǒng)使用層來分隔不同的功能單元。每一層只與該層的上層和下層通信。每一層都使用下面的層來執(zhí)行其功能。層之間的通信通過預(yù)定義的固定接口通信。

4.3

微內(nèi)核

為了實(shí)現(xiàn)高可靠性，將操作系統(tǒng)劃分成小的、層級之間能夠更好定義的模塊是很有必要的，只有一個模塊 --- 微內(nèi)核 --- 運(yùn)行在內(nèi)核態(tài)，其余模塊可以作為普通用戶進(jìn)程運(yùn)行。由于把每個設(shè)備驅(qū)動和文件系統(tǒng)分別作為普通用戶進(jìn)程，這些模塊中的錯誤雖然會使這些模塊崩潰，但是不會使整個系統(tǒng)死機(jī)。

MINIX 3 是微內(nèi)核的代表作，它的具體結(jié)構(gòu)如下

在內(nèi)核的外部，系統(tǒng)的構(gòu)造有三層，它們都在用戶態(tài)下運(yùn)行，最底層是設(shè)備驅(qū)動器。由于它們都在用戶態(tài)下運(yùn)行，所以不能物理的訪問 I/O 端口空間，也不能直接發(fā)出 I/O 命令。相反，為了能夠?qū)?I/O 設(shè)備編程，驅(qū)動器構(gòu)建一個結(jié)構(gòu)，指明哪個參數(shù)值寫到哪個 I/O 端口，并聲稱一個內(nèi)核調(diào)用，這樣就完成了一次調(diào)用過程。

4.4

客戶-服務(wù)器模式

微內(nèi)核思想的策略是把進(jìn)程劃分為兩類：服務(wù)器，每個服務(wù)器用來提供服務(wù)；客戶端，使用這些服務(wù)。這個模式就是所謂的客戶-服務(wù)器模式。

客戶-服務(wù)器模式會有兩種載體，一種情況是一臺計算機(jī)既是客戶又是服務(wù)器，在這種方式下，操作系統(tǒng)會有某種優(yōu)化；但是普遍情況下是客戶端和服務(wù)器在不同的機(jī)器上，它們通過局域網(wǎng)或廣域網(wǎng)連接。

客戶通過發(fā)送消息與服務(wù)器通信，客戶端并不需要知道這些消息是在本地機(jī)器上處理，還是通過網(wǎng)絡(luò)被送到遠(yuǎn)程機(jī)器上處理。對于客戶端而言，這兩種情形是一樣的：都是發(fā)送請求并得到回應(yīng)。

什么是按需分頁

在操作系統(tǒng)中，進(jìn)程是以頁為單位加載到內(nèi)存中的，按需分頁是一種虛擬內(nèi)存的管理方式。在使用請求分頁的系統(tǒng)中，只有在嘗試訪問頁面所在的磁盤并且該頁面尚未在內(nèi)存中時，也就發(fā)生了缺頁異常，操作系統(tǒng)才會將磁盤頁面復(fù)制到內(nèi)存中。

多處理系統(tǒng)的優(yōu)勢

隨著處理器的不斷增加，我們的計算機(jī)系統(tǒng)由單機(jī)系統(tǒng)變?yōu)榱硕嗵幚硐到y(tǒng)，多處理系統(tǒng)的吞吐量比較高，多處理系統(tǒng)擁有多個并行的處理器，這些處理器共享時鐘、內(nèi)存、總線、外圍設(shè)備等。

多處理系統(tǒng)由于可以共享資源，因此可以開源節(jié)流，省錢。整個系統(tǒng)的可靠性也隨之提高。

什么是內(nèi)核

在計算機(jī)中，內(nèi)核是一個計算機(jī)程序，它是操作系統(tǒng)的核心，可以控制操作系統(tǒng)中所有的內(nèi)容。內(nèi)核通常是在 boot loader 裝載程序之前加載的第一個程序。

這里還需要了解一下什么是 boot loader。

boot loader 又被稱為引導(dǎo)加載程序，它是一個程序，能夠?qū)⒂嬎銠C(jī)的操作系統(tǒng)放入內(nèi)存中。在電源通電或者計算機(jī)重啟時，BIOS 會執(zhí)行一些初始測試，然后將控制權(quán)轉(zhuǎn)移到引導(dǎo)加載程序所在的主引導(dǎo)記錄(MBR) 。

什么是實(shí)時系統(tǒng)

實(shí)時操作系統(tǒng)對時間做出了嚴(yán)格的要求，實(shí)時操作系統(tǒng)分為兩種：硬實(shí)時和軟實(shí)時

硬實(shí)時操作系統(tǒng)規(guī)定某個動作必須在規(guī)定的時刻內(nèi)完成或發(fā)生，比如汽車生產(chǎn)車間，焊接機(jī)器必須在某一時刻內(nèi)完成焊接，焊接的太早或者太晚都會對汽車造成永久性傷害。

軟實(shí)時操作系統(tǒng)雖然不希望偶爾違反最終的時限要求，但是仍然可以接受。并且不會引起任何永久性傷害。比如數(shù)字音頻、多媒體、手機(jī)都是屬于軟實(shí)時操作系統(tǒng)。

你可以簡單理解硬實(shí)時和軟實(shí)時的兩個指標(biāo)：是否在時刻內(nèi)必須完成以及是否造成嚴(yán)重?fù)p害。

什么是虛擬內(nèi)存

虛擬內(nèi)存是一種內(nèi)存分配方案，是一項可以用來輔助內(nèi)存分配的機(jī)制。我們知道，應(yīng)用程序是按頁裝載進(jìn)內(nèi)存中的。但并不是所有的頁都會裝載到內(nèi)存中，計算機(jī)中的硬件和軟件會將數(shù)據(jù)從 RAM 臨時傳輸?shù)酱疟P中來彌補(bǔ)內(nèi)存的不足。如果沒有虛擬內(nèi)存的話，一旦你將計算機(jī)內(nèi)存填滿后，計算機(jī)會對你說

呃，不，對不起，您無法再加載任何應(yīng)用程序，請關(guān)閉另一個應(yīng)用程序以加載新的應(yīng)用程序。對于虛擬內(nèi)存，計算機(jī)可以執(zhí)行操作是查看內(nèi)存中最近未使用過的區(qū)域，然后將其復(fù)制到硬盤上。虛擬內(nèi)存通過復(fù)制技術(shù)實(shí)現(xiàn)了妹子，你快來看哥哥能裝這么多程序的資本。復(fù)制是自動進(jìn)行的，你無法感知到它的存在。

什么是進(jìn)程和進(jìn)程表

進(jìn)程就是正在執(zhí)行程序的實(shí)例，比如說 Web 程序就是一個進(jìn)程，shell 也是一個進(jìn)程，文章編輯器 typora 也是一個進(jìn)程。

操作系統(tǒng)負(fù)責(zé)管理所有正在運(yùn)行的進(jìn)程，操作系統(tǒng)會為每個進(jìn)程分配特定的時間來占用 CPU，操作系統(tǒng)還會為每個進(jìn)程分配特定的資源。

操作系統(tǒng)為了跟蹤每個進(jìn)程的活動狀態(tài)，維護(hù)了一個進(jìn)程表。在進(jìn)程表的內(nèi)部，列出了每個進(jìn)程的狀態(tài)以及每個進(jìn)程使用的資源等。

http://courses.cs.vt.edu/csonline/OS/Lessons/Processes/index.html ( http://courses.cs.vt.edu/csonline/OS/Lessons/Processes/index.html ) 這個網(wǎng)站上面有一個關(guān)于進(jìn)程狀態(tài)輪轉(zhuǎn)的動畫，做的真是太好了。

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

這又是一道老生常談的問題了，從操作系統(tǒng)的角度來回答一下吧。

我們上面說到進(jìn)程是正在運(yùn)行的程序的實(shí)例，而線程其實(shí)就是進(jìn)程中的單條流向，因?yàn)榫€程具有進(jìn)程中的某些屬性，所以線程又被稱為輕量級的進(jìn)程。瀏覽器如果是一個進(jìn)程的話，那么瀏覽器下面的每個 tab 頁可以看作是一個個的線程。

下面是線程和進(jìn)程持有資源的區(qū)別

線程不像進(jìn)程那樣具有很強(qiáng)的獨(dú)立性，線程之間會共享數(shù)據(jù)

創(chuàng)建線程的開銷要比進(jìn)程小很多，因?yàn)閯?chuàng)建線程僅僅需要堆棧指針和程序計數(shù)器就可以了，而創(chuàng)建進(jìn)程需要操作系統(tǒng)分配新的地址空間，數(shù)據(jù)資源等，這個開銷比較大。

使用多線程的好處是什么

多線程是程序員不得不知的基本素養(yǎng)之一，所以，下面我們給出一些多線程編程的好處

能夠提高對用戶的響應(yīng)順序

在流程中的資源共享

比較經(jīng)濟(jì)適用

能夠?qū)Χ嗑€程架構(gòu)有深入的理解

什么是 RR 調(diào)度算法

RR(round-robin) 調(diào)度算法主要針對分時系統(tǒng)，RR 的調(diào)度算法會把時間片以相同的部分并循環(huán)的分配給每個進(jìn)程，RR 調(diào)度算法沒有優(yōu)先級的概念。這種算法的實(shí)現(xiàn)比較簡單，而且每個線程都會占有時間片，并不存在線程饑餓的問題。

導(dǎo)致系統(tǒng)出現(xiàn)死鎖的情況

死鎖的出現(xiàn)需要同時滿足下面四個條件

互斥(Mutual Exclusion)：一次只能有一個進(jìn)程使用資源。如果另一個進(jìn)程請求該資源，則必須延遲請求進(jìn)程，直到釋放該資源為止。

保持并等待(Hold and Wait)：必須存在一個進(jìn)程，該進(jìn)程至少持有一個資源，并且正在等待獲取其他進(jìn)程當(dāng)前所持有的資源。

無搶占(No Preemption)：資源不能被搶占，也就是說，在進(jìn)程完成其任務(wù)之后，只能由擁有它的進(jìn)程自動釋放資源。

循環(huán)等待(Circular Wait) ：必須存在一組 {p0，p1，..... pn} 的等待進(jìn)程，使 p0 等待 p1 持有的資源，p1 等待由 p2 持有的資源， pn-1 正在等待由 pn 持有的資源，而 pn 正在等待由 p0 持有的資源。

RAID 的不同級別

RAID 稱為磁盤冗余陣列，簡稱磁盤陣列。利用虛擬化技術(shù)把多個硬盤結(jié)合在一起，成為一個或多個磁盤陣列組，目的是提升性能或數(shù)據(jù)冗余。

RAID 有不同的級別

RAID 0 - 無容錯的條帶化磁盤陣列

RAID 1 - 鏡像和雙工

RAID 2 - 內(nèi)存式糾錯碼

RAID 3 - 比特交錯奇偶校驗(yàn)

RAID 4 - 塊交錯奇偶校驗(yàn)

RAID 5 - 塊交錯分布式奇偶校驗(yàn)

RAID 6 - P + Q 冗余

什么是 DMA

DMA 的中文名稱是直接內(nèi)存訪問，它意味著 CPU 授予 I/O 模塊權(quán)限在不涉及 CPU 的情況下讀取或?qū)懭雰?nèi)存。也就是 DMA 可以不需要 CPU 的參與。這個過程由稱為 DMA 控制器（DMAC）的芯片管理。由于 DMA 設(shè)備可以直接在內(nèi)存之間傳輸數(shù)據(jù)，而不是使用 CPU 作為中介，因此可以緩解總線上的擁塞。DMA 通過允許 CPU 執(zhí)行任務(wù)，同時 DMA 系統(tǒng)通過系統(tǒng)和內(nèi)存總線傳輸數(shù)據(jù)來提高系統(tǒng)并發(fā)性。

多線程編程的好處是什么

對不起，我忍不住想偷笑

說直白點(diǎn)，為什么單線程能夠處理的卻要用多線程來處理？當(dāng)然是為了提高程序的裝逼并行能力了。多線程在某些情況下能夠使你程序運(yùn)行的更快，這也是為什么多核 CPU 會出現(xiàn)，但是多核 CPU 的出現(xiàn)會導(dǎo)致數(shù)據(jù)的一致性問題，不過這些問題程序員就能解決。另一個角度來說，多線程編程能夠提高程序員的編程能力和編程思維。同時也能提高程序員的管理能力，你如果把每條線程流當(dāng)作羅老師時間管理的女主一樣，能夠及時協(xié)調(diào)好所有 P 友的關(guān)系，那你也是超神程序員了，所以，是誰說程序員不會做管理的？Doug Lea 大佬牛逼?。?！

ps：Doug Lea 大佬開發(fā)的 JUC 工具包，此處不加狗頭。

什么是設(shè)備驅(qū)動程序

在計算機(jī)中，設(shè)備驅(qū)動程序是一種計算機(jī)程序，它能夠控制或者操作連接到計算機(jī)的特定設(shè)備。驅(qū)動程序提供了與硬件進(jìn)行交互的軟件接口，使操作系統(tǒng)和其他計算機(jī)程序能夠訪問特定設(shè)備，不用需要了解其硬件的具體構(gòu)造。

進(jìn)程間的通信方式

19.1

通信概念

進(jìn)程間的通信方式比較多，首先你需要理解下面這幾個概念

競態(tài)條件：即兩個或多個線程同時對一共享數(shù)據(jù)進(jìn)行修改，從而影響程序運(yùn)行的正確性時，這種就被稱為競態(tài)條件(race condition)。

臨界區(qū)：不僅共享資源會造成競態(tài)條件，事實(shí)上共享文件、共享內(nèi)存也會造成競態(tài)條件、那么該如何避免呢？或許一句話可以概括說明：禁止一個或多個進(jìn)程在同一時刻對共享資源（包括共享內(nèi)存、共享文件等）進(jìn)行讀寫。換句話說，我們需要一種互斥(mutual exclusion) 條件，這也就是說，如果一個進(jìn)程在某種方式下使用共享變量和文件的話，除該進(jìn)程之外的其他進(jìn)程就禁止做這種事（訪問統(tǒng)一資源）。

一個好的解決方案，應(yīng)該包含下面四種條件

任何時候兩個進(jìn)程不能同時處于臨界區(qū)

不應(yīng)對 CPU 的速度和數(shù)量做任何假設(shè)

位于臨界區(qū)外的進(jìn)程不得阻塞其他進(jìn)程

不能使任何進(jìn)程無限等待進(jìn)入臨界區(qū)

忙等互斥：當(dāng)一個進(jìn)程在對資源進(jìn)行修改時，其他進(jìn)程必須進(jìn)行等待，進(jìn)程之間要具有互斥性，我們討論的解決方案其實(shí)都是基于忙等互斥提出的。

19.2

解決方案

進(jìn)程間的通信用專業(yè)一點(diǎn)的術(shù)語來表示就是 Inter Process Communication，IPC，它主要有下面幾種通信方式

消息傳遞：消息傳遞是進(jìn)程間實(shí)現(xiàn)通信和同步等待的機(jī)制，使用消息傳遞，進(jìn)程間的交流不需要共享變量，直接就可以進(jìn)行通信；消息傳遞分為發(fā)送方和接收方

先進(jìn)先出隊列：先進(jìn)先出隊列指的是兩個不相關(guān)聯(lián)進(jìn)程間的通信，兩個進(jìn)程之間可以彼此相互進(jìn)程通信，這是一種全雙工通信方式

管道：管道用于兩個相關(guān)進(jìn)程之間的通信，這是一種半雙工的通信方式，如果需要全雙工，需要另外一個管道。

直接通信：在這種進(jìn)程通信的方式中，進(jìn)程與進(jìn)程之間只存在一條鏈接，進(jìn)程間要明確通信雙方的命名。

間接通信：間接通信是通信雙方不會直接建立連接，而是找到一個中介者，這個中介者可能是個對象等等，進(jìn)程可以在其中放置消息，并且可以從中刪除消息，以此達(dá)到進(jìn)程間通信的目的。

消息隊列：消息隊列是內(nèi)核中存儲消息的鏈表，它由消息隊列標(biāo)識符進(jìn)行標(biāo)識，這種方式能夠在不同的進(jìn)程之間提供全雙工的通信連接。

共享內(nèi)存：共享內(nèi)存是使用所有進(jìn)程之間的內(nèi)存來建立連接，這種類型需要同步進(jìn)程訪問來相互保護(hù)。

進(jìn)程間狀態(tài)模型

cat chapter1 chapter2 chapter3 | grep tree

第一個進(jìn)程是 cat，將三個文件級聯(lián)并輸出。第二個進(jìn)程是 grep，它從輸入中選擇具有包含關(guān)鍵字 tree 的內(nèi)容，根據(jù)這兩個進(jìn)程的相對速度（這取決于兩個程序的相對復(fù)雜度和各自所分配到的 CPU 時間片），可能會發(fā)生下面這種情況，grep 準(zhǔn)備就緒開始運(yùn)行，但是輸入進(jìn)程還沒有完成，于是必須阻塞 grep 進(jìn)程，直到輸入完畢。

當(dāng)一個進(jìn)程開始運(yùn)行時，它可能會經(jīng)歷下面這幾種狀態(tài)

圖中會涉及三種狀態(tài)

運(yùn)行態(tài)，運(yùn)行態(tài)指的就是進(jìn)程實(shí)際占用 CPU 時間片運(yùn)行時

就緒態(tài)，就緒態(tài)指的是可運(yùn)行，但因?yàn)槠渌M(jìn)程正在運(yùn)行而處于就緒狀態(tài)

阻塞態(tài)，除非某種外部事件發(fā)生，否則進(jìn)程不能運(yùn)行

邏輯上來說，運(yùn)行態(tài)和就緒態(tài)是很相似的。這兩種情況下都表示進(jìn)程可運(yùn)行，但是第二種情況沒有獲得 CPU 時間分片。第三種狀態(tài)與前兩種狀態(tài)不同的原因是這個進(jìn)程不能運(yùn)行，CPU 空閑時也不能運(yùn)行。

三種狀態(tài)會涉及四種狀態(tài)間的切換，在操作系統(tǒng)發(fā)現(xiàn)進(jìn)程不能繼續(xù)執(zhí)行時會發(fā)生狀態(tài) 1的輪轉(zhuǎn)，在某些系統(tǒng)中進(jìn)程執(zhí)行系統(tǒng)調(diào)用，例如 pause，來獲取一個阻塞的狀態(tài)。在其他系統(tǒng)中包括 UNIX，當(dāng)進(jìn)程從管道或特殊文件（例如終端）中讀取沒有可用的輸入時，該進(jìn)程會被自動終止。

轉(zhuǎn)換 2 和轉(zhuǎn)換 3 都是由進(jìn)程調(diào)度程序（操作系統(tǒng)的一部分）引起的，進(jìn)程本身不知道調(diào)度程序的存在。轉(zhuǎn)換 2 的出現(xiàn)說明進(jìn)程調(diào)度器認(rèn)定當(dāng)前進(jìn)程已經(jīng)運(yùn)行了足夠長的時間，是時候讓其他進(jìn)程運(yùn)行 CPU 時間片了。當(dāng)所有其他進(jìn)程都運(yùn)行過后，這時候該是讓第一個進(jìn)程重新獲得 CPU 時間片的時候了，就會發(fā)生轉(zhuǎn)換 3。

程序調(diào)度指的是，決定哪個進(jìn)程優(yōu)先被運(yùn)行和運(yùn)行多久，這是很重要的一點(diǎn)。已經(jīng)設(shè)計出許多算法來嘗試平衡系統(tǒng)整體效率與各個流程之間的競爭需求。

當(dāng)進(jìn)程等待的一個外部事件發(fā)生時（如從外部輸入一些數(shù)據(jù)后），則發(fā)生轉(zhuǎn)換 4。如果此時沒有其他進(jìn)程在運(yùn)行，則立刻觸發(fā)轉(zhuǎn)換 3，該進(jìn)程便開始運(yùn)行，否則該進(jìn)程會處于就緒階段，等待 CPU 空閑后再輪到它運(yùn)行。

調(diào)度算法都有哪些

調(diào)度算法分為三大類：批處理中的調(diào)度、交互系統(tǒng)中的調(diào)度、實(shí)時系統(tǒng)中的調(diào)度

21.1

批處理中的調(diào)度

先來先服務(wù)

很像是先到先得。。?？赡茏詈唵蔚姆菗屨际秸{(diào)度算法的設(shè)計就是先來先服務(wù)(first-come,first-serverd)。使用此算法，將按照請求順序?yàn)檫M(jìn)程分配 CPU。最基本的，會有一個就緒進(jìn)程的等待隊列。當(dāng)?shù)谝粋€任務(wù)從外部進(jìn)入系統(tǒng)時，將會立即啟動并允許運(yùn)行任意長的時間。它不會因?yàn)檫\(yùn)行時間太長而中斷。當(dāng)其他作業(yè)進(jìn)入時，它們排到就緒隊列尾部。當(dāng)正在運(yùn)行的進(jìn)程阻塞，處于等待隊列的第一個進(jìn)程就開始運(yùn)行。當(dāng)一個阻塞的進(jìn)程重新處于就緒態(tài)時，它會像一個新到達(dá)的任務(wù)，會排在隊列的末尾，即排在所有進(jìn)程最后。

這個算法的強(qiáng)大之處在于易于理解和編程，在這個算法中，一個單鏈表記錄了所有就緒進(jìn)程。要選取一個進(jìn)程運(yùn)行，只要從該隊列的頭部移走一個進(jìn)程即可；要添加一個新的作業(yè)或者阻塞一個進(jìn)程，只要把這個作業(yè)或進(jìn)程附加在隊列的末尾即可。這是很簡單的一種實(shí)現(xiàn)。

不過，先來先服務(wù)也是有缺點(diǎn)的，那就是沒有優(yōu)先級的關(guān)系，試想一下，如果有 100 個 I/O 進(jìn)程正在排隊，第 101 個是一個 CPU 密集型進(jìn)程，那豈不是需要等 100 個 I/O 進(jìn)程運(yùn)行完畢才會等到一個 CPU 密集型進(jìn)程運(yùn)行，這在實(shí)際情況下根本不可能，所以需要優(yōu)先級或者搶占式進(jìn)程的出現(xiàn)來優(yōu)先選擇重要的進(jìn)程運(yùn)行。

最短作業(yè)優(yōu)先

批處理中，第二種調(diào)度算法是最短作業(yè)優(yōu)先(Shortest Job First)，我們假設(shè)運(yùn)行時間已知。例如，一家保險公司，因?yàn)槊刻煲鲱愃频墓ぷ?，所以人們可以相?dāng)精確地預(yù)測處理 1000 個索賠的一批作業(yè)需要多長時間。當(dāng)輸入隊列中有若干個同等重要的作業(yè)被啟動時，調(diào)度程序應(yīng)使用最短優(yōu)先作業(yè)算法

如上圖 a 所示，這里有 4 個作業(yè) A、B、C、D ，運(yùn)行時間分別為 8、4、4、4 分鐘。若按圖中的次序運(yùn)行，則 A 的周轉(zhuǎn)時間為 8 分鐘，B 為 12 分鐘，C 為 16 分鐘，D 為 20 分鐘，平均時間內(nèi)為 14 分鐘。

現(xiàn)在考慮使用最短作業(yè)優(yōu)先算法運(yùn)行 4 個作業(yè)，如上圖 b 所示，目前的周轉(zhuǎn)時間分別為 4、8、12、20，平均為 11 分鐘，可以證明最短作業(yè)優(yōu)先是最優(yōu)的?？紤]有 4 個作業(yè)的情況，其運(yùn)行時間分別為 a、b、c、d。第一個作業(yè)在時間 a 結(jié)束，第二個在時間 a + b 結(jié)束，以此類推。平均周轉(zhuǎn)時間為 (4a + 3b + 2c + d) / 4 。顯然 a 對平均值的影響最大，所以 a 應(yīng)該是最短優(yōu)先作業(yè)，其次是 b，然后是 c ，最后是 d 它就只能影響自己的周轉(zhuǎn)時間了。

需要注意的是，在所有的進(jìn)程都可以運(yùn)行的情況下，最短作業(yè)優(yōu)先的算法才是最優(yōu)的。

最短剩余時間優(yōu)先

最短作業(yè)優(yōu)先的搶占式版本被稱作為最短剩余時間優(yōu)先(Shortest Remaining Time Next) 算法。使用這個算法，調(diào)度程序總是選擇剩余運(yùn)行時間最短的那個進(jìn)程運(yùn)行。當(dāng)一個新作業(yè)到達(dá)時，其整個時間同當(dāng)前進(jìn)程的剩余時間做比較。如果新的進(jìn)程比當(dāng)前運(yùn)行進(jìn)程需要更少的時間，當(dāng)前進(jìn)程就被掛起，而運(yùn)行新的進(jìn)程。這種方式能夠使短期作業(yè)獲得良好的服務(wù)。

21.2

交互式系統(tǒng)中的調(diào)度

交互式系統(tǒng)中在個人計算機(jī)、服務(wù)器和其他系統(tǒng)中都是很常用的，所以有必要來探討一下交互式調(diào)度

輪循調(diào)度

一種最古老、最簡單、最公平并且最廣泛使用的算法就是輪循算法(round-robin)。每個進(jìn)程都會被分配一個時間段，稱為時間片(quantum)，在這個時間片內(nèi)允許進(jìn)程運(yùn)行。如果時間片結(jié)束時進(jìn)程還在運(yùn)行的話，則搶占一個 CPU 并將其分配給另一個進(jìn)程。如果進(jìn)程在時間片結(jié)束前阻塞或結(jié)束，則 CPU 立即進(jìn)行切換。輪循算法比較容易實(shí)現(xiàn)。調(diào)度程序所做的就是維護(hù)一個可運(yùn)行進(jìn)程的列表，就像下圖中的 a，當(dāng)一個進(jìn)程用完時間片后就被移到隊列的末尾，就像下圖的 b。

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

事實(shí)情況是不是所有的進(jìn)程都是優(yōu)先級相等的。例如，在一所大學(xué)中的等級制度，首先是院長，然后是教授、秘書、后勤人員，最后是學(xué)生。這種將外部情況考慮在內(nèi)就實(shí)現(xiàn)了優(yōu)先級調(diào)度(priority scheduling)

它的基本思想很明確，每個進(jìn)程都被賦予一個優(yōu)先級，優(yōu)先級高的進(jìn)程優(yōu)先運(yùn)行。

但是也不意味著高優(yōu)先級的進(jìn)程能夠永遠(yuǎn)一直運(yùn)行下去，調(diào)度程序會在每個時鐘中斷期間降低當(dāng)前運(yùn)行進(jìn)程的優(yōu)先級。如果此操作導(dǎo)致其優(yōu)先級降低到下一個最高進(jìn)程的優(yōu)先級以下，則會發(fā)生進(jìn)程切換。或者，可以為每個進(jìn)程分配允許運(yùn)行的最大時間間隔。當(dāng)時間間隔用完后，下一個高優(yōu)先級的進(jìn)程會得到運(yùn)行的機(jī)會。

最短進(jìn)程優(yōu)先

對于批處理系統(tǒng)而言，由于最短作業(yè)優(yōu)先常常伴隨著最短響應(yīng)時間，一種方式是根據(jù)進(jìn)程過去的行為進(jìn)行推測，并執(zhí)行估計運(yùn)行時間最短的那一個。假設(shè)每個終端上每條命令的預(yù)估運(yùn)行時間為 T0，現(xiàn)在假設(shè)測量到其下一次運(yùn)行時間為 T1，可以用兩個值的加權(quán)來改進(jìn)估計時間，即aT0+ (1- 1)T1。通過選擇 a 的值，可以決定是盡快忘掉老的運(yùn)行時間，還是在一段長時間內(nèi)始終記住它們。當(dāng) a = 1/2 時，可以得到下面這個序列

可以看到，在三輪過后，T0 在新的估計值中所占比重下降至 1/8。

有時把這種通過當(dāng)前測量值和先前估計值進(jìn)行加權(quán)平均從而得到下一個估計值的技術(shù)稱作老化(aging)。這種方法會使用很多預(yù)測值基于當(dāng)前值的情況。

彩票調(diào)度

有一種既可以給出預(yù)測結(jié)果而又有一種比較簡單的實(shí)現(xiàn)方式的算法，就是彩票調(diào)度(lottery scheduling)算法。他的基本思想為進(jìn)程提供各種系統(tǒng)資源的彩票。當(dāng)做出一個調(diào)度決策的時候，就隨機(jī)抽出一張彩票，擁有彩票的進(jìn)程將獲得資源。比如在 CPU 進(jìn)行調(diào)度時，系統(tǒng)可以每秒持有 50 次抽獎，每個中獎進(jìn)程會獲得額外運(yùn)行時間的獎勵。

可以把彩票理解為 buff，這個 buff 有 15% 的幾率能讓你產(chǎn)生速度之靴的效果。

公平分享調(diào)度

如果用戶 1 啟動了 9 個進(jìn)程，而用戶 2 啟動了一個進(jìn)程，使用輪轉(zhuǎn)或相同優(yōu)先級調(diào)度算法，那么用戶 1 將得到 90 % 的 CPU 時間，而用戶 2 將之得到 10 % 的 CPU 時間。

為了阻止這種情況的出現(xiàn)，一些系統(tǒng)在調(diào)度前會把進(jìn)程的擁有者考慮在內(nèi)。在這種模型下，每個用戶都會分配一些 CPU 時間，而調(diào)度程序會選擇進(jìn)程并強(qiáng)制執(zhí)行。因此如果兩個用戶每個都會有 50% 的 CPU 時間片保證，那么無論一個用戶有多少個進(jìn)程，都將獲得相同的 CPU 份額。

頁面置換算法都有哪些

算法	注釋
最優(yōu)算法	不可實(shí)現(xiàn)，但可以用作基準(zhǔn)
NRU(最近未使用) 算法	和 LRU 算法很相似
FIFO(先進(jìn)先出) 算法	有可能會拋棄重要的頁面
第二次機(jī)會算法	比 FIFO 有較大的改善
時鐘算法	實(shí)際使用
LRU(最近最少)算法	比較優(yōu)秀，但是很難實(shí)現(xiàn)
NFU(最不經(jīng)常使用)算法	和 LRU 很類似
老化算法	近似 LRU 的高效算法
工作集算法	實(shí)施起來開銷很大
工作集時鐘算法	比較有效的算法

最優(yōu)算法在當(dāng)前頁面中置換最后要訪問的頁面。不幸的是，沒有辦法來判定哪個頁面是最后一個要訪問的，因此實(shí)際上該算法不能使用。然而，它可以作為衡量其他算法的標(biāo)準(zhǔn)。

NRU 算法根據(jù) R 位和 M 位的狀態(tài)將頁面分為四類。從編號最小的類別中隨機(jī)選擇一個頁面。NRU 算法易于實(shí)現(xiàn)，但是性能不是很好。存在更好的算法。

FIFO 會跟蹤頁面加載進(jìn)入內(nèi)存中的順序，并把頁面放入一個鏈表中。有可能刪除存在時間最長但是還在使用的頁面，因此這個算法也不是一個很好的選擇。

第二次機(jī)會算法是對 FIFO 的一個修改，它會在刪除頁面之前檢查這個頁面是否仍在使用。如果頁面正在使用，就會進(jìn)行保留。這個改進(jìn)大大提高了性能。

時鐘算法是第二次機(jī)會算法的另外一種實(shí)現(xiàn)形式，時鐘算法和第二次算法的性能差不多，但是會花費(fèi)更少的時間來執(zhí)行算法。

LRU 算法是一個非常優(yōu)秀的算法，但是沒有特殊的硬件(TLB)很難實(shí)現(xiàn)。如果沒有硬件，就不能使用 LRU 算法。

NFU 算法是一種近似于 LRU 的算法，它的性能不是非常好。

老化算法是一種更接近 LRU 算法的實(shí)現(xiàn)，并且可以更好的實(shí)現(xiàn)，因此是一個很好的選擇

最后兩種算法都使用了工作集算法。工作集算法提供了合理的性能開銷，但是它的實(shí)現(xiàn)比較復(fù)雜。WSClock 是另外一種變體，它不僅能夠提供良好的性能，而且可以高效地實(shí)現(xiàn)。