[[326227]]

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

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

 

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

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

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

• 管理計(jì)算機(jī)資源，這些資源包括 CPU、內(nèi)存、磁盤(pán)驅(qū)動(dòng)器、打印機(jī)等。
• 提供一種圖形界面，就像我們前面描述的那樣，它提供了用戶和計(jì)算機(jī)之間的橋梁。
• 為其他軟件提供服務(wù)，操作系統(tǒng)與軟件進(jìn)行交互，以便為其分配運(yùn)行所需的任何必要資源。

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

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

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

4.1.單體系統(tǒng)

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

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

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

 

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

4.2.分層系統(tǒng)

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

 

4.3.微內(nèi)核

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

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

 

 

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

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

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

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

 

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

5.什么是按需分頁(yè)

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

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

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

 

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

7.什么是內(nèi)核

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

 

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

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

12.使用多線程的好處是什么

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

• 能夠提高對(duì)用戶的響應(yīng)順序
• 在流程中的資源共享
• 比較經(jīng)濟(jì)適用
• 能夠?qū)Χ嗑€程架構(gòu)有深入的理解

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

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

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

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

• 互斥(Mutual Exclusion)：一次只能有一個(gè)進(jìn)程使用資源。如果另一個(gè)進(jìn)程請(qǐng)求該資源，則必須延遲請(qǐng)求進(jìn)程，直到釋放該資源為止。
• 保持并等待(Hold and Wait)：必須存在一個(gè)進(jìn)程，該進(jìn)程至少持有一個(gè)資源，并且正在等待獲取其他進(jìn)程當(dāng)前所持有的資源。
• 無(wú)搶占(No Preemption)：資源不能被搶占，也就是說(shuō)，在進(jìn)程完成其任務(wù)之后，只能由擁有它的進(jìn)程自動(dòng)釋放資源。
• 循環(huán)等待(Circular Wait) ：必須存在一組 {p0，p1，..... pn} 的等待進(jìn)程，使 p0 等待 p1 持有的資源，p1 等待由 p2 持有的資源， pn-1 正在等待由 pn 持有的資源，而 pn 正在等待由 p0 持有的資源。

15.RAID 的不同級(jí)別

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

RAID 有不同的級(jí)別

• RAID 0 - 無(wú)容錯(cuò)的條帶化磁盤(pán)陣列
• RAID 1 - 鏡像和雙工
• RAID 2 - 內(nèi)存式糾錯(cuò)碼
• RAID 3 - 比特交錯(cuò)奇偶校驗(yàn)
• RAID 4 - 塊交錯(cuò)奇偶校驗(yàn)
• RAID 5 - 塊交錯(cuò)分布式奇偶校驗(yàn)
• RAID 6 - P + Q 冗余

16.什么是 DMA

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

17.多線程編程的好處是什么

對(duì)不起，我忍不住想偷笑

 

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

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

18.什么是設(shè)備驅(qū)動(dòng)程序

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

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

19.1.通信概念

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

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

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

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

 

 

 

 

1. 任何時(shí)候兩個(gè)進(jìn)程不能同時(shí)處于臨界區(qū)
2. 不應(yīng)對(duì) CPU 的速度和數(shù)量做任何假設(shè)
3. 位于臨界區(qū)外的進(jìn)程不得阻塞其他進(jìn)程
4. 不能使任何進(jìn)程無(wú)限等待進(jìn)入臨界區(qū)

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

解決方案

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

 

• 消息傳遞：消息傳遞是進(jìn)程間實(shí)現(xiàn)通信和同步等待的機(jī)制，使用消息傳遞，進(jìn)程間的交流不需要共享變量，直接就可以進(jìn)行通信;消息傳遞分為發(fā)送方和接收方
• 先進(jìn)先出隊(duì)列：先進(jìn)先出隊(duì)列指的是兩個(gè)不相關(guān)聯(lián)進(jìn)程間的通信，兩個(gè)進(jìn)程之間可以彼此相互進(jìn)程通信，這是一種全雙工通信方式
• 管道：管道用于兩個(gè)相關(guān)進(jìn)程之間的通信，這是一種半雙工的通信方式，如果需要全雙工，需要另外一個(gè)管道。
• 直接通信：在這種進(jìn)程通信的方式中，進(jìn)程與進(jìn)程之間只存在一條鏈接，進(jìn)程間要明確通信雙方的命名。
• 間接通信：間接通信是通信雙方不會(huì)直接建立連接，而是找到一個(gè)中介者，這個(gè)中介者可能是個(gè)對(duì)象等等，進(jìn)程可以在其中放置消息，并且可以從中刪除消息，以此達(dá)到進(jìn)程間通信的目的。
• 消息隊(duì)列：消息隊(duì)列是內(nèi)核中存儲(chǔ)消息的鏈表，它由消息隊(duì)列標(biāo)識(shí)符進(jìn)行標(biāo)識(shí)，這種方式能夠在不同的進(jìn)程之間提供全雙工的通信連接。
• 共享內(nèi)存：共享內(nèi)存是使用所有進(jìn)程之間的內(nèi)存來(lái)建立連接，這種類型需要同步進(jìn)程訪問(wèn)來(lái)相互保護(hù)。

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

cat chapter1 chapter2 chapter3 | grep tree  

第一個(gè)進(jìn)程是

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

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

 

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

1. 運(yùn)行態(tài)，運(yùn)行態(tài)指的就是進(jìn)程實(shí)際占用 CPU 時(shí)間片運(yùn)行時(shí)
2. 就緒態(tài)，就緒態(tài)指的是可運(yùn)行，但因?yàn)槠渌M(jìn)程正在運(yùn)行而處于就緒狀態(tài)
3. 阻塞態(tài)，除非某種外部事件發(fā)生，否則進(jìn)程不能運(yùn)行邏輯上來(lái)說(shuō)，運(yùn)行態(tài)和就緒態(tài)是很相似的。這兩種情況下都表示進(jìn)程可運(yùn)行，但是第二種情況沒(méi)有獲得 CPU 時(shí)間分片。第三種狀態(tài)與前兩種狀態(tài)不同的原因是這個(gè)進(jìn)程不能運(yùn)行，CPU 空閑時(shí)也不能運(yùn)行。

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

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

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

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

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

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

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

先來(lái)先服務(wù)

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

 

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

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

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

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

 

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

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

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

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

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

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

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

輪循調(diào)度

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

 

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

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

 

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

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

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

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

 

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

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

彩票調(diào)度

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

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

公平分享調(diào)度

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

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

22.頁(yè)面置換算法都有哪些

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

• 最優(yōu)算法在當(dāng)前頁(yè)面中置換最后要訪問(wèn)的頁(yè)面。不幸的是，沒(méi)有辦法來(lái)判定哪個(gè)頁(yè)面是最后一個(gè)要訪問(wèn)的，因此實(shí)際上該算法不能使用。然而，它可以作為衡量其他算法的標(biāo)準(zhǔn)。
• NRU 算法根據(jù) R 位和 M 位的狀態(tài)將頁(yè)面分為四類。從編號(hào)最小的類別中隨機(jī)選擇一個(gè)頁(yè)面。NRU 算法易于實(shí)現(xiàn)，但是性能不是很好。存在更好的算法。
• FIFO 會(huì)跟蹤頁(yè)面加載進(jìn)入內(nèi)存中的順序，并把頁(yè)面放入一個(gè)鏈表中。有可能刪除存在時(shí)間最長(zhǎng)但是還在使用的頁(yè)面，因此這個(gè)算法也不是一個(gè)很好的選擇。
• 第二次機(jī)會(huì)算法是對(duì) FIFO 的一個(gè)修改，它會(huì)在刪除頁(yè)面之前檢查這個(gè)頁(yè)面是否仍在使用。如果頁(yè)面正在使用，就會(huì)進(jìn)行保留。這個(gè)改進(jìn)大大提高了性能。
• 時(shí)鐘 算法是第二次機(jī)會(huì)算法的另外一種實(shí)現(xiàn)形式，時(shí)鐘算法和第二次算法的性能差不多，但是會(huì)花費(fèi)更少的時(shí)間來(lái)執(zhí)行算法。
• LRU 算法是一個(gè)非常優(yōu)秀的算法，但是沒(méi)有特殊的硬件(TLB)很難實(shí)現(xiàn)。如果沒(méi)有硬件，就不能使用 LRU 算法。
• NFU 算法是一種近似于 LRU 的算法，它的性能不是非常好。
• 老化 算法是一種更接近 LRU 算法的實(shí)現(xiàn)，并且可以更好的實(shí)現(xiàn)，因此是一個(gè)很好的選擇
• 最后兩種算法都使用了工作集算法。工作集算法提供了合理的性能開(kāi)銷，但是它的實(shí)現(xiàn)比較復(fù)雜。WSClock 是另外一種變體，它不僅能夠提供良好的性能，而且可以高效地實(shí)現(xiàn)。最好的算法是老化算法和 WSClock 算法。他們分別是基于 LRU 和工作集算法。他們都具有良好的性能并且能夠被有效的實(shí)現(xiàn)。還存在其他一些好的算法，但實(shí)際上這兩個(gè)可能是最重要的。

23.影響調(diào)度程序的指標(biāo)是什么

會(huì)有下面幾個(gè)因素決定調(diào)度程序的好壞

• CPU 使用率：

CPU 正在執(zhí)行任務(wù)(即不處于空閑狀態(tài))的時(shí)間百分比。

• 等待時(shí)間

這是進(jìn)程輪流執(zhí)行的時(shí)間，也就是進(jìn)程切換的時(shí)間

• 吞吐量

單位時(shí)間內(nèi)完成進(jìn)程的數(shù)量

• 響應(yīng)時(shí)間

這是從提交流程到獲得有用輸出所經(jīng)過(guò)的時(shí)間。

• 周轉(zhuǎn)時(shí)間

從提交流程到完成流程所經(jīng)過(guò)的時(shí)間。

24.什么是僵尸進(jìn)程

僵尸進(jìn)程是已完成且處于終止?fàn)顟B(tài)，但在進(jìn)程表中卻仍然存在的進(jìn)程。僵尸進(jìn)程通常發(fā)生在父子關(guān)系的進(jìn)程中，由于父進(jìn)程仍需要讀取其子進(jìn)程的退出狀態(tài)所造成的。