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

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

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

手機看文章

掃描二維碼
隨時隨地手機看文章

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

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

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

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

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

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

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

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

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

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

操作系統(tǒng)通常預裝在你購買計算機之前。大部分用戶都會使用默認的操作系統(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)以單一程序的方式運行。整個操作系統(tǒng)是以程序集合來編寫的，鏈接在一塊形成一個大的二進制可執(zhí)行程序，這種系統(tǒng)稱為單體系統(tǒng)。

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

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

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

4.2

分層系統(tǒng)

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

4.3

微內(nèi)核

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

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

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

4.4

客戶-服務器模式

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

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

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

什么是按需分頁

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

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

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

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

什么是內(nèi)核

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

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

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

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

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

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

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

你可以簡單理解硬實時和軟實時的兩個指標：是否在時刻內(nèi)必須完成以及是否造成嚴重損害。

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

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

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

什么是進程和進程表

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

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

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

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)于進程狀態(tài)輪轉(zhuǎn)的動畫，做的真是太好了。

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

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

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

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

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

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

使用多線程的好處是什么

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

能夠提高對用戶的響應順序

在流程中的資源共享

比較經(jīng)濟適用

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

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

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

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

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

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

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

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

循環(huán)等待(Circular Wait) ：必須存在一組 {p0，p1，..... pn} 的等待進程，使 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 - 比特交錯奇偶校驗

RAID 4 - 塊交錯奇偶校驗

RAID 5 - 塊交錯分布式奇偶校驗

RAID 6 - P + Q 冗余

什么是 DMA

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

多線程編程的好處是什么

對不起，我忍不住想偷笑

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

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

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

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

進程間的通信方式

19.1

通信概念

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

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

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

一個好的解決方案，應該包含下面四種條件

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

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

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

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

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

19.2

解決方案

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

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

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

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

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

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

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

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

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

cat chapter1 chapter2 chapter3 | grep tree

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

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

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

運行態(tài)，運行態(tài)指的就是進程實際占用 CPU 時間片運行時

就緒態(tài)，就緒態(tài)指的是可運行，但因為其他進程正在運行而處于就緒狀態(tài)

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

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

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

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

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

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

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

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

21.1

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

先來先服務

很像是先到先得。。。可能最簡單的非搶占式調(diào)度算法的設計就是先來先服務(first-come,first-serverd)。使用此算法，將按照請求順序為進程分配 CPU。最基本的，會有一個就緒進程的等待隊列。當?shù)谝粋€任務從外部進入系統(tǒng)時，將會立即啟動并允許運行任意長的時間。它不會因為運行時間太長而中斷。當其他作業(yè)進入時，它們排到就緒隊列尾部。當正在運行的進程阻塞，處于等待隊列的第一個進程就開始運行。當一個阻塞的進程重新處于就緒態(tài)時，它會像一個新到達的任務，會排在隊列的末尾，即排在所有進程最后。

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

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

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

批處理中，第二種調(diào)度算法是最短作業(yè)優(yōu)先(Shortest Job First)，我們假設運行時間已知。例如，一家保險公司，因為每天要做類似的工作，所以人們可以相當精確地預測處理 1000 個索賠的一批作業(yè)需要多長時間。當輸入隊列中有若干個同等重要的作業(yè)被啟動時，調(diào)度程序應使用最短優(yōu)先作業(yè)算法

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

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

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

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

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

21.2

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

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

輪循調(diào)度

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

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

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

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

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

最短進程優(yōu)先

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

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

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

彩票調(diào)度

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

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

公平分享調(diào)度

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

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

頁面置換算法都有哪些

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

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

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

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

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

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

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

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

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

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