爆肝操作系統面試題

面試季到了，希望這份操作系統面試題大集合能發揮作用。

這份面試題包含四十多道，涉及操作系統簡介篇、進程和線程篇、內存管理篇、文

件系統篇、10篇、死鎖篇，囊括了校招面試和社招面試，希望能對彼此有幫助！

?離文件累於性■的方K

文件JK0UI?魚號法

RAID"網*M

話不多說，下面我們直接進入面試題。

操作系統簡介篇

解釋一下什么是操作系統

操作系統是管理硬件和軟件的一種應用程序。操作系統是運行在計算機上最重要的

一種軟件，它管理計算機的資源和進程以及所有的硬件和軟件。它為計算機硬件和

軟件提供了一種中間層，使應用軟件和硬件進行分離，讓我們無需關注硬件的實現,

把關注點更多放在軟件應用上。

電子郵件

音樂播放器

web瀏覽器閱讀器

通常情況下，計算機上會運行著許多應用程序，它們都需要對內存和CPU進行交

互，操作系統的目的就是為了呆證這些訪問和交互能夠準確無誤的進行。

臊作系統的主要功能

一般來說，現代操作系統主要泥供下面幾種功能

進程管理：進程管理的主要作用就是任務調度，在單核處理器下，操作系統會為每

個進程分配一個任務，進程管理的工作十分簡單；而在多核處理器下，操作系統除

了要為進程分配任務外，還要解決處理器的調度、分配和回收等問題

內存管理：內存管理主要是操作系統負責管理內存的分配、回收，在進程需要時分

配內存以及在進程完成時回收內存，協調內存資源，通過合理的頁面置換算法進行

頁面的換入換出

設備管理：根據確定的設備分配原則對設備進行分配，使設備與主機能夠并行工作,

為用戶提供良好的設備使用界面。

文件管理：有效地管理文件的存儲空間，合理地組織和管理文件系統，為文件訪問

和文件保護提供更有效的方法及手段。

提供用戶接口：操作系統提供了訪問應用程序和硬件的接口，使用戶能夠通過應用

程序發起系統調用從而操縱硬件，實現想要的功能。

軟件訪問硬件的幾種方式

軟件訪問硬件其實就是一種10操作，軟件訪問硬件的方式，也就是I/O操作的

方式有哪些。

硬件在I/O上大致分為并行和串行，同時也對應串行接口和并行接口。

隨著計算機技術的發展，I/O控制方式也在不斷發展。選擇和衡量I/O控制方式

有如下三條原則

(1)數據傳送速度足夠快，能滿足用戶的需求但又不丟失數據;

(2)系統開銷小，所需的處理控制程序少；

(3)能充分發揮硬件資源的能力，使I/O設備盡可能忙，而CPU

等待時間盡可能少。

根據以上控制原則，I/O操作可以分為四類

直接訪問：直接訪問由用戶進程直接控制主存或CPU和外圍設備之間的信息傳送。

直接程序控制方式又稱為忙/等待方式。

中斷驅動：為了減少程序直接控制方式下CPU的等待時間以及提高系統的并行程

度，系統引入了中斷機制。中斷機制引入后，外圍設備僅當操作正常結束或異常結

束時才向CPU發出中斷請求。在I/O設備輸入每個數據的過程中，由于無需CPU

的干預，一定程度上實現了CPU與I/O設備的并行工作。

上述兩種方法的特點都是以CPU為中心，數據傳送通過一段程序來實現，軟件

的傳送手段限制了數據傳送的速度。接下來介紹的這兩種I/O控制方式采用硬件

的方法來顯示I/O的控制

DMA直接內存訪問：為了進一步減少CPU對I/O操作的干預，防止因并行操作設

備過多使CPU來不及處理或因速度不匹配而造成的數據丟失現象，引入了DMA控

制方式。

通道控制方式：通道，獨立于CPU的專門負責輸入輸出控制的處理機，它控制設

備與內存直接進行數據交換。有自己的通道指令，這些指令由CPU啟動，并在操

作結束時向CPU發出中斷信號。

解釋一下操作系統的主要目的是什么

操作系統是一種軟件，它的主要目的有三種

管理訂算機資源，這些資源包括CPU、內存、磁盤驅動器、打卬機等。

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

為其他軟件提供服務，操作系統與軟件進行交互，以便為其分配運行所需的任何必

要資源。

操作系統的種類有哪些

操作系統通常預裝在你購買計算機之前。大部分用戶都會使用默認的操作系統，但

是你也可以升級甚至更改操作系統。但是一般常見的操作系統只有三種：Windows.

macOS和Linuxo

為什么Linux系統下的應用程序不能直接在Windows下運行

這是一個老生常談的問題了，在這里給出具體的回答。

其中一點是因為Linux系統和Windows系統的格式不同，格式就是協議，就是在

固定位置有意義的數據。Linux下的可執行程序文件格式是elf,可以使

用readelf命令查看elf文件頭。

ELFHeader

.text

.data

.bss

othersections

Sectionheadertable

StringTables

SymbolTables

而Windows下的可執行程序是PE格式，它是一種可移植的可執行文件。

還有一點是因為Linux系統和Windows系統的API不同，這個API指的就是

操作系統的API,Linux中的API被稱為系統調用，是通過int0x80這個軟

中斷實現的。而Windows中的API是放在動態鏈接庫文件中的，也就是Windows

開發人員所說的DLL,這是一個庫，里面包含代碼和數據。Linux中的可執行

程序獲得系統資源的方法和Windows不一樣，所以顯然是不能在Windows中運行

的。

操作系統結構

單體系統

在大多數系統中，整個系統在內核態以單一程序的方式運行。整個操作系統是以程

序集合來編寫的，鏈接在一塊形成一個大的二進制可執行程序，這種系統稱為單體

系統。

在單體系統中構造實際目標程序時，會首先編譯所有單個過程(或包含這些過程的

文件)，然后使用系統鏈接器將它們全部綁定到一個可執行文件中

在單體系統中，對于每個系統調用都會有一個服務程序來保障和運行。需要一組實

用程序來彌補服務程序需要的功能，例如從用戶程序中獲取數據。可將各種過程劃

分為一個三層模型

服務程序

實用程序

除了在計算機初啟動時所裝載的核心操作系統外，許多操作系統還支持額外的擴

展。比如I/O設備驅動和文件系統。這些部件可以按需裝載。在UNIX中把它們

叫做共享庫(shared1ibrary),在Windows中則被稱為動態鏈接庫(Dynamic

LinkLibrary,DLL)o他們的擴展名為.dll,在C:\Windows\system32目錄下

存在1000多個DLL文件，所以不要輕易刪除C盤文件,否則可能就炸了哦。

分層系統

分層系統使用層來分隔不同的功能單元。每一層只與該層的上層和下層通信。每一

層都使用下面的層來執行其功能。層之間的通信通過預定義的固定接口通信。

微內核

為了實現高可靠性，將操作系統劃分成小的、層級之間能夠更好定義的模塊是很有

必要的，只有一個模塊-一微內核--運行在內核態，其余模塊可以作為普通用

戶進程運行。由于把每個設備驅動和文件系統分別作為普通用戶進程，這些模塊中

的錯誤雖然會使這些模塊崩潰，但是不會使整個系統死機Q

MINIX3是微內核的代表作，它的具體結構如下

在內核的外部，系統的構造有三層，它們都在用戶態下運行，最底層是設備驅動器。

由于它們都在用戶態下運行，所以不能物理的訪問I/O端口空間，也不能直接發

出I/O命令。相反，為了能夠對I/O設備編程，驅動器構建一個結構，指明哪個

參數值寫到哪個I/O端口，并聲稱一個內核調用，這樣就完成了一次調用過程。

客戶-服務器模式

微內核思想的策略是把進程劃分為兩類：服務器，每個服務器用來提供服務；客戶

端，使用這些服務。這個模式就是所謂的客戶-服務器模式。

客戶-服務器模式會有兩種載體，一種情況是一臺計算機既是客戶又是服務器，在

這種方式下，操作系統會有某種優化；但是普遍情況下是客戶端和服務器在不同的

機器上，它們通過局域網或廣域網連接。

客戶通過發送消息與服務器通信，客戶端并不需要知道這些消息是在本地機器上處

理，還是通過網絡被送到遠程機器上處理。對于客戶端而言，這兩種情形是一樣的：

都是發送請求并得到回應。

為什么稱為陷入內核

如果把軟件結構進行分層說明的話，應該是這個樣子的，最外層是應用程序，里面

是操作系統內核。

應用程序處于特權級3,操作系統內核處于特權級0o如果月戶程序想要訪問操

作系統資源時，會發起系統調用，陷入內核，這樣CPU就進入了內核態，執行內

核代碼。至于為什么是陷入，我們看圖，內核是一個凹陷的構造，有陷下去的感覺，

所以稱為陷入。

什么是用戶態和內核態

用戶態和內核態是操作系統的兩種運行狀態。

內核態：處于內核態的CPU可以訪問任意的數據，包括外圍設備，比如網卡、硬

盤等，處于內核態的CPU可以從一個程序切換到另外一個程序，并且占用CPU不

會發生搶占情況，一般處于特權級0的狀態我們稱之為內核態。

用戶態：處于用戶態的CPU只能受限的訪問內存，并且不允許訪問外圍設備，用

戶態下的CPU不允許獨占，也就是說CPU能夠被其他程序獲取。

那么為什么要有用戶態和內核態呢？

這個主要是訪問能力的限制的考量，計算機中有一些比較危險的操作，比如設置時

鐘、內存清理，這些都需要在內核態下完成，如果隨意進行這些操作，那你的系統

得崩潰多少次。

用戶態和內核態是如何切換的？

所有的用戶進程都是運行在用戶態的，但是我們上面也說了，用戶程序的訪問能力

有限，一些比較重要的比如從便盤讀取數據，從鍵盤獲取數據的操作則是內核態才

能做的事情，而這些數據卻又對用戶程序來說非常重要。所以就涉及到兩種模式下

的轉換，即用戶態->內核態->用戶態，而唯一能夠做這些操作的只有系統調

用，而能夠執行系統調用的就只有操作系統。

一般用戶態->內核態的轉換我們都稱之為trap進內核，也被稱之為陷阱指令

(trapinstruction)。

他們的工作流程如下：

首先用戶程序會調用glibc庫，glibc是一個標準庫，同時也是一套核心庫,

庫中定義了很多關鍵APIo

glibc庫知道針對不同體系結構調用系統調用的正確方法，它會根據體系結構應用

程序的二進制接口設置用戶進程傳遞的參數，來準備系統調用。

然后，glibc庫調用軟件中斷指令(SWI),這個指令通過更新CPSR寄存器將

模式改為超級用戶模式，然后跳轉到地址0x08處。

到目前為止，整個過程仍處于用戶態下，在執行SWI指令后，允許進程執行內核

代碼，MMU現在允許內核虛擬內存訪問

從地址0x08開始，進程執行加載并跳轉到中斷處理程序，這個程序就是ARM中

的vectorswi()。

在vector_swi()處，從SWI指令中提取系統調用號SCNO,然后使用SCNO作

為系統調用表sys_call_table的索引，調轉到系統調用函數。

執行系統調用完成后，將還原用戶模式寄存器，然后再以用戶模式執行。

什么是內核

在計算機中，內核是一個計算機程序，它是操作系統的核心，可以控制操作系統中

所有的內容。內核通常是在bootloader裝載程序之前加載的第一個程序。

這里還需要了解一下什么是bootloadero

bootloader又被稱為引導加載程序，能夠將計算機的操作系統放入

內存中。在電源通電或者計算機重啟時，BIOS會執行一些初始測試，

然后將控制權轉移到引導加載程序所在的主引導記錄(M3R)o

什么是實時系統

實時操作系統對時間做出了嚴珞的要求，實時操作系統分為兩種：硬實時和軟實時

硬實時操作系統規定某個動作必須在規定的時刻內完成或發生，比如汽車生產車

間，焊接機器必須在某一時刻內完成焊接，焊接的太早或者太晚都會對汽車造成永

久性傷害。

軟實時操作系統雖然不希望偶爾違反最終的時限要求，但是仍然可以接受。并且不

會引起任何永久性傷害。比如數字音頻、多媒體、手機都是屬于軟實時操作系統。

你可以簡單理解硬實時和軟實時的兩個指標：是否在時刻內必須完成以及是否造成

嚴重損害。

Linux操作系統的啟動過程

當計算機電源通電后，BIOS會進行開機自檢(PowerOn-Self-Test,POST),對硬件

進行檢測和初始化。因為操作系統的啟動會使用到磁盤、屏幕、鍵盤、鼠標等設備。

下一步，磁盤中的第一個分區，也被稱為MBR(MasterBootRecord)主引導記

錄，被讀入到一個固定的內存區域并執行。這個分區中有一個非常小的，只有512

字節的程序。程序從磁盤中調入boot獨立程序，boot程序將自身復制到高位地

址的內存從而為操作系統釋放低位地址的內存。

復制完成后，boot程序讀取啟動設備的根目錄。boot程序要理解文件系統和目錄

格式。然后boot程序被調入內核，把控制權移交給內核。直到這里，boot完成

了它的工作。系統內核開始運行。

內核啟動代碼是使用匯編語言完成的，主要包括創建內核堆棧、識別CPU類型、

計算內存、禁用中斷、啟動內存管理單元等，然后調用C語言的main函數執行

操作系統部分。

這部分也會做很多事情，首先會分配一個消息緩沖區來存放調試出現的問題，調試

信息會寫入緩沖區。如果調試出現錯誤，這些信息可以通過診斷程序調出來。

然后操作系統會進行自動配置，檢測設備，加載配置文件，被檢測設備如果做出響

應，就會被添加到已鏈接的設備表中，如果沒有相應，就歸為未連接直接忽略。

配置完所有硬件后，接下來要做的就是仔細手工處理進程0,設置其堆棧，然后運

行它，執行初始化、配置時鐘、掛載文件系統。創建init進程（進程1）和守

護進程（進程2）。

init進程會檢測它的標志以確定它是否為單用戶還是多用戶服務。在前一種情況

中，它會調用fork函數創建一個shell進程，并且等待這人進程結束。后一種

情況調用fork函數創建一個運行系統初始化的shell腳本（即/etc/rc）的進

程，這個進程可以進行文件系統一致性檢測、掛載文件系統、開啟守護進程等。

然后/etc/rc這個進程會從/etc/ttys中讀取數據，/etc/ttys列出了所有的終

端和屬性。對于每一個啟用的終端，這個進程調用fork函數創建一個自身的副本，

進行內部處理并運行一個名為getty的程序。

getty程序會在終端上輸入

login:

等待用戶輸入用戶名，在輸入用戶名后，getty程序結束，登陸程

序/bin/login開始運行。login程序需要輸入密碼，并與保存

在/etc/passwd中的密碼進行對比，如果輸入正確，login程序以用戶shell

程序替換自身，等待第一個命令。如果不正確，login程序要求輸入另一個用戶名。

整個系統啟動過程如下

執行硬件初始化

MBRKernel

自檢完成，導入MBR

BIOS調入內核

開機自檢BOOT

手工設置

文件系統

磁盤鍵盤

進程和線程篇

多處理系統的優勢

隨著處理器的不斷增加，我們的計算機系統由單機系統變為了多處理系統，多處理

系統的吞吐量比較高，多處理系統擁有多個并行的處理器，這些處理器共享時鐘、

內存、總線、外圍設備等。

多處理系統由于可以共享資源，因此可以開源節流，省錢。整個系統的可靠性也隨

之提高。

什么是進程和進程表

進程就是正在執行程序的實例，比如說Web程序就是一個進程，shell也是一個

進程，文章編輯器typora也是一個進程。

操作系統負責管理所有正在運行的進程，操作系統會為每個進程分配特定的時間來

占用CPU,操作系統還會為每個進程分配特定的資源。

操作系統為了跟蹤每個進程的活動狀態，維護了一個進程表。在進程表的內部，列

出了每個進程的狀態以及每個進程使用的資源等。

什么是線程，線程和進程的區別

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

我們上面說到進程是正在運行的程序的實例，而線程其實就是進程中的單條流向，

因為線程具有進程中的某些屬性，所以線程又被稱為輕量級的進程。瀏覽器如果是

一個進程的話，那么瀏覽器下面的每個tab頁可以看作是一個個的線程。

下面是線程和進程持有資源的區別

每個進程中的內容每個線程中的內容

地址空間程序計數器

全局變量寄存器

打開文件堆棧

子進程狀態

即將發生的定時器

信號與信號處理程序

賬戶信息

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

創建線程的開銷要比進程小很多，因為創建線程僅僅需要堆棧指針和程序計數器就

可以了，而創建進程需要操作系統分配新的地址空間，數據資源等，這個開銷比較

大。

什么是上下文切換

對于單核單線程CPU而言，在某一時刻只能執行一條CPU指令。上下文切換

(ContextSwitch)是一種將CPU資源從一個進程分配給另一個進程的機制。從

用戶角度看，計算機能夠并行運行多個進程，這恰恰是操作系統通過快速上下文切

換造成的結果。在切換的過程中，操作系統需要先存儲當前進程的狀態(包括內存

空間的指針，當前執行完的指令等等），再讀入下一個進程的狀態，然后執行此進

程。

使用多線程的好處是什么

多線程是程序員不得不知的基本素養之一，所以，下面我們給出一些多線程編程的

好處

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

在流程中的資源共享

比較經濟適用

能夠對多線程架構有深入的理解

進程終止的方式

進程的終止

進程在創建之后，它就開始運行并做完成任務。然而，沒有什么事兒是永不停歇的,

包括進程也一樣。進程早晚會發生終止，但是通常是由于以下情況觸發的

正常退出（自愿的）

錯誤退出（自愿的）

嚴重錯誤（非自愿的）

被其他進程殺死（非自愿的）

正常退出

多數進程是由于完成了工作而終止。當編譯器完成了所給定程序的編譯之后，編譯

器會執行一個系統調用告訴操作系統它完成了工作。這個調用在UNIX中

是exit,在Windows中是ExitProcesso面向屏幕中的軟件也支持自愿終止

操作。字處理軟件、Internet瀏覽器和類似的程序中總有一個供用戶點擊的圖標

或菜單項，用來通知進程刪除它所打開的任何臨時文件，然后終止。

錯誤退出

進程發生終止的第二個原因是發現嚴重錯誤，例如，如果用戶次行如下命令

ccfoo.C

為了能夠編譯foo.c但是該文件不存在，于是編譯器就會發出聲明并退出。在給

出了錯誤參數時，面向屏幕的交互式進程通常并不會直接退出，因為這從用戶的角

度來說并不合理，用戶需要知道發生了什么并想要進行重試，所以這時候應用程序

通常會彈出一個對話框告知用戶發生了系統錯誤，是需要重試還是退出。

嚴重錯誤

進程終止的第三個原因是由進程引起的錯誤，通常是由于程序中的錯誤所導致的。

例如，執行了一條非法指令，引用不存在的內存，或者除數是0等。在有些系統

比如UNIX中，進程可以通知操作系統，它希望自行處理某種類型的錯誤，在這類

錯誤中，進程會收到信號（中斷），而不是在這類錯誤出現時直接終止進程。

被其他進程殺死

第四個終止進程的原因是，某個進程執行系統調用告訴操作系統殺死某個進程。在

UNIX中，這個系統調用是kil1o在Win32中對應的函數是TerminateProcess

（注意不是系統調用）。

進程間的通信方式

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

競態條件：即兩個或多個線程同時對一共享數據進行修改，從而影響程序運行的正

確性時，這種就被稱為競態條件（racecondition）o

臨界區：不僅共享資源會造成競態條件，事實上共享文件、共享內存也會造成競態

條件、那么該如何避免呢？或許一句話可以概括說明：禁止一個或多個進程在同一

時刻對共享資源（包括共享內存、共享文件等）進行讀寫。換句話說，我們需要一

種互斥（mulualexclusion）條件，這也就是說，如果一個進程在某種方式下使

用共享變量和文件的話，除該進程之外的其他進程就禁止做這種事（訪問統一資

源）。

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

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

2.

3.

不應對CPU的速度和數量做任何假設

4.

5.

位于臨界區外的進程不得阻塞其他進程

6.

7.

不能使任何進程無限等待進入臨界區

8.

忙等互斥：當一個進程在對資源進行修改時，其他進程必須進行等待，進程之間要

具有互斥性，我們討論的解決方案其實都是基于忙等互斥提出的。

進程間的通信用專業一點的術語來表示就是InterProcessCommunication,IPC,

它主要有下面7。種通信方式

消息傳遞：消息傳遞是進程間實現通信和同步等待的機制，使用消息傳遞，進程間

的交流不需要共享變量，直接就可以進行通信；消息傳遞分為發送方和接收方

先進先出隊列：先進先出隊列指的是兩個不相關聯進程間的通信，兩個進程之間可

以彼此相互進程通信，這是一種全雙工通信方式

管道：管道用于兩個相關進程之間的通信，這是一種半雙工的通信方式，如果需要

全雙工，需要另外一個管道。

直接通佶：在這種進程通信的方式中，進程與進程之間只存在一條鏈接，進程間要

明確通信雙方的命名。

間接通信：間接通信是通信雙方不會直接建立連接，而是找到一個中介者，這個中

介者可能是個對象等等，進程可以在其中放置消息，并且可以從中刪除消息，以此

達到進程間通信的目的。

消息隊列：消息隊列是內核中存儲消息的鏈表，它由消息隊列標識符進行標識，這

種方式能夠在不同的進程之間泥供全雙工的通信連接。

共享內存：共享內存是使用所有進程之間的內存來建立連接，這種類型需要同步進

程訪問來相互保護。

進程間狀態模型

進程的三態模型

當一個進程開始運行時，它可能會經歷下面這幾種狀態

圖中會涉及三種狀態

1.

運行態：運行態指的就是進程實際占用CPU時間片運行時

2.

3.

就緒態：就緒態指的是可運行，但因為其他進程正在運行而處于就緒狀態

4.

5.

阻塞態：阻塞態又被稱為睡眠態，它指的是進程不具備運行條件，正在等待被CPU

調度。

6.

邏輯上來說，運行態和就緒態是很相似的。這兩種情況下都表示進程可運行，但是

第二種情況沒有獲得CPU時間分片。第三種狀態與前兩種狀態不同的原因是這個

進程不能運行，CPU空閑時也不能運行。

三種狀態會涉及四種狀態間的刃換，在操作系統發現進程不能繼續執行時會發生狀

態1的輪轉，在某些系統中進程執行系統調用，例如pause,來獲取一個阻塞的

狀態。在其他系統中包括UNIX,當進程從管道或特殊文件（例如終端）中讀取沒

有可用的輸入時，該進程會被芻動終止。

轉換2和轉換3都是由進程調度程序（操作系統的一部分）引起的，進程本身不

知道調度程序的存在。轉換2的出現說明進程調度器認定當前進程已經運行了足

夠長的時間，是時候讓其他進程運行CPU時間片了。當所有其他進程都運行過后，

這時候該是讓第一個進程重新獲得CPU時間片的時候了，就會發生轉換3。

程序調度指的是，決定哪個進程優先被運行和運行多久，這是很重

要的一點。已經設計出許多算法來嘗試平衡系統整體效率與各個流程

之間的競爭需求。

當進程等待的一個外部事件發生時（如從外部輸入一些數據后），則發生轉換4。

如果此時沒有其他進程在運行：則立刻觸發轉換3,該進程便開始運行，否則該進

程會處于就緒階段，等待CPU空閑后再輪到它運行。

進程的五態模型

在三態模型的基礎上，增加了兩個狀態，即新建和終止狀態。

新建態：進程的新建態就是進程剛創建出來的時候

創建進程需要兩個步驟：即為新進程分配所需要的資源和空間，設置

進程為就緒態，并等待調度執行。

終止態：進程的終止態就是指進程執行完畢，到達結束點，或者因為錯誤而不得不

中止進程。

終止一個進程需要兩個步驟：

1.

先等待操作系統或相關的進程進行善后處理。

2.

3.

然后回收占用的資源并被系統刪除。

4.

調度算法都有哪些

調度算法分為三大類：批處理中的調度、交互系統中的調度、實時系統中的調度

批處理中的調度

先來先服務

很像是先到先得。。。可能最簡單的非搶占式調度算法的設計就是先來先服務

(first-come,firstserverd),使用此算法，將按照請求順序為進程分配CPU。最

基本的，會有一個就緒進程的等待隊列。當第一個任務從外部進入系統時，將會立

即啟動并允許運行任意長的時間。它不會因為運行時間太長而中斷。當其他作業進

入時，它們排到就緒隊列尾部＜當正在運行的進程阻塞，處于等待隊列的第一個進

程就開始運行。當一個阻塞的進程重新處于就緒態時，它會像一個新到達的任務，

會排在隊列的末尾，即排在所有進程最后。

這個算法的強大之處在于易于理解和編程，在這個算法中，一個單鏈表記錄了所有

就緒進程。要選取一個進程運行，只要從該隊列的頭部移走一個進程即可；要添加

一個新的作業或者阻塞一個進程，只要把這個作業或進程附加在隊列的末尾即可。

這是很簡單的一種實現。

不過，先來先服務也是有缺點的，那就是沒有優先級的關系，試想一下，如果有100

個I/O進程正在排隊，第101個是一個CPU密集型進程，那豈不是需要等100

個I/O進程運行完畢才會等到一個CPU密集型進程運行，這在實際情況下根本不

可能，所以需要優先級或者搶占式進程的出現來優先選擇重要的進程運行。

最短作業優先

批處理中，第二種調度算法是最短作業優先(ShortestJobFirst),我們假設運

行時間已知。例如，一家保險公司，因為每天要做類似的工作，所以人們可以相當

精確地預測處理1000個索賠的一批作業需要多長時間。當輸入隊列中有若干個同

等重要的作業被啟動時，調度程序應使用最短優先作業算法

8444444

ABCDBCD

ab

按原有次數運行4個作業按1R短作業優先次序進行

如上圖a所示，這里有4個作業A、B、C、D,運行時間分別為8、4、4、4分

鐘。若按圖中的次序運行，則A的周轉時間為8分鐘，B為12分鐘，C為16

分鐘，D為20分鐘，平均時間內為14分鐘。

現在考慮使用最短作業優先算法運行4個作業，如上圖b所示，目前的周轉時間

分別為4、8、12、20,平均為11分鐘，可以證明最短作業優先是最優的。考慮

有4個作業的情況，其運行時間分別為a、b、c、do第一個作業在時間a結束，

第二個在時間a+b結束，以此類推。平均周轉時間為(4a+3b+2c+d)/4。

顯然a對平均值的影響最大，所以a應該是最短優先作業，其次是b,然后是

c,最后是d它就只能影響自己的周轉時間了。

需要注意的是，在所有的進程都可以運行的情況下，最短作業優先的

算法才是最優的。

最短剩余時間優先

最短作業優先的搶占式版本被稱作為最短剩余時間優先(ShortestRemaining

TimeNext)算法。使用這個算法，調度程序總是選擇剩余運行時間最短的那個進

程運行。當一個新作業到達時，其整個時間同當前進程的剩余時間做比較。如果新

的進程比當前運行進程需要更少的時間，當前進程就被掛起，而運行新的進程。這

種方式能夠使短期作業獲得良好的服務。

交互式系統中的調度

交互式系統中在個人計算機、服務器和其他系統中都是很常用的，所以有必要來探

討一下交互式調度

輪詢調度

一種最古老、最簡單、最公平并且最廣泛使用的算法就是輪詢算法

(round-robin)0每個進程都會被分配一個時間段，稱為時間片(quantum),在這個

時間片內允許進程運行。如果時間片結束時進程還在運行的話，則搶占一個CPU并

將其分配給另一個進程。如果進程在時間片結束前阻塞或結束，則CPU立即進行

切換。輪詢算法比較容易實現。調度程序所做的就是維護一個可運行進程的列表，

就像下圖中的a,當一個進程用完時間片后就被移到隊列的末尾，就像下圖的bo

當前進程下一個進程

a

可運行進程列表

當前進程

進程B用完時間片后的可運行列表

優先級調度

事實情況是不是所有的進程都是優先級相等的。例如，在一所大學中的等級制度，

首先是院長