Categories
程式開發

看完這篇操作系統,和麵試官扯皮就沒問題了


解釋一下什麼是操作系統

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

看完這篇操作系統,和麵試官扯皮就沒問題了 1

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

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

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

管理計算機資源,這些資源包括 CPU、內存、磁盤驅動器、打印機等。提供一種圖形界面,就像我們前面描述的那樣,它提供了用戶和計算機之間的橋樑。為其他軟件提供服務,操作系統與軟件進行交互,以便為其分配運行所需的任何必要資源。

操作系統的種類有哪些

操作系統通常預裝在你購買計算機之前。大部分用戶都會使用默認的操作系統,但是你也可以升級甚至更改操作系統。但是一般常見的操作系統只有三種:Windows、macOS 和 Linux。

操作系統結構

單體系統

在大多數係統中,整個系統在內核態以單一程序的方式運行。整個操作系統是以程序集合來編寫的,鏈接在一塊形成一個大的二進制可執行程序,這種系統稱為單體系統。

在單體系統中構造實際目標程序時,會首先編譯所有單個過程(或包含這些過程的文件),然後使用系統鏈接器將它們全部綁定到一個可執行文件中

在單體系統中,對於每個系統調用都會有一個服務程序來保障和運行。需要一組實用程序來彌補服務程序需要的功能,例如從用戶程序中獲取數據。可將各種過程劃分為一個三層模型

看完這篇操作系統,和麵試官扯皮就沒問題了 2

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

分層系統

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

看完這篇操作系統,和麵試官扯皮就沒問題了 3

微內核

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

MINIX 3 是微內核的代表作,它的具體結構如下

看完這篇操作系統,和麵試官扯皮就沒問題了 4

在內核的外部,系統的構造有三層,它們都在用戶態下運行,最底層是設備驅動器。由於它們都在用戶態下運行,所以不能物理的訪問 I/O 端口空間,也不能直接發出 I/O 命令。相反,為了能夠對 I/O 設備編程,驅動器構建一個結構,指明哪個參數值寫到哪個 I/O 端口,並聲稱一個內核調用,這樣就完成了一次調用過程。

客戶-服務器模式

微內核思想的策略是把進程劃分為兩類:服務器,每個服務器用來提供服務;客戶端,使用這些服務。這個模式就是所謂的 客戶-服務器模式。

客戶-服務器模式會有兩種載體,一種情況是一台計算機既是客戶又是服務器,在這種方式下,操作系統會有某種優化;但是普遍情況下是客戶端和服務器在不同的機器上,它們通過局域網或廣域網連接。

看完這篇操作系統,和麵試官扯皮就沒問題了 5

客戶通過發送消息與服務器通信,客戶端並不需要知道這些消息是在本地機器上處理,還是通過網絡被送到遠程機器上處理。對於客戶端而言,這兩種情形是一樣的:都是發送請求並得到回應。

什麼是按需分頁

在操作系統中,進程是以頁為單位加載到內存中的,按需分頁是一種虛擬內存的管理方式。在使用請求分頁的系統中,只有在嘗試訪問頁面所在的磁盤並且該頁面尚未在內存中時,也就發生了缺頁異常,操作系統才會將磁盤頁面複製到內存中。

多處理系統的優勢

隨著處理器的不斷增加,我們的計算機系統由單機系統變為了多處理系統,多處理系統的吞吐量比較高,多處理系統擁有多個並行的處理器,這些處理器共享時鐘、內存、總線、外圍設備等。

看完這篇操作系統,和麵試官扯皮就沒問題了 6

多處理系統由於可以共享資源,因此可以開源節流,省錢。整個系統的可靠性也隨之提高。

什麼是內核

在計算機中,內核是一個計算機程序,它是操作系統的核心,可以控制操作系統中所有的內容。內核通常是在 boot loader 裝載程序之前加載的第一個程序。

這裡還需要了解一下什麼是 boot loader。

>boot loader 又被稱為引導加載程序,它是一個程序,能夠將計算機的操作系統放入內存中。在電源通電或者計算機重啟時,BIOS 會執行一些初始測試,然後將控制權轉移到引導加載程序所在的主引導記錄(MBR) 。

什麼是實時系統

實時操作系統對時間做出了嚴格的要求,實時操作系統分為兩種:硬實時和軟實時

硬實時操作系統規定某個動作必須在規定的時刻內完成或發生,比如汽車生產車間,焊接機器必須在某一時刻內完成焊接,焊接的太早或者太晚都會對汽車造成永久性傷害。

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

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

什麼是虛擬內存

虛擬內存是一種內存分配方案,是一項可以用來輔助內存分配的機制。我們知道,應用程序是按頁裝載進內存中的。但並不是所有的頁都會裝載到內存中,計算機中的硬件和軟件會將數據從 RAM 臨時傳輸到磁盤中來彌補內存的不足。如果沒有虛擬內存的話,一旦你將計算機內存填滿後,計算機會對你說

看完這篇操作系統,和麵試官扯皮就沒問題了 7

呃,不,對不起,您無法再加載任何應用程序,請關閉另一個應用程序以加載新的應用程序。對於虛擬內存,計算機可以執行操作是查看內存中最近未使用過的區域,然後將其複製到硬盤上。虛擬內存通過複製技術實現了 妹子,你快來看哥哥能裝這麼多程序 的資本。複製是自動進行的,你無法感知到它的存在。

什麼是進程和進程表

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

操作系統負責管理所有正在運行的進程,操作系統會為每個進程分配特定的時間來佔用 CPU,操作系統還會為每個進程分配特定的資源。

操作系統為了跟踪每個進程的活動狀態,維護了一個進程表。在進程表的內部,列出了每個進程的狀態以及每個進程使用的資源等。

http://courses.cs.vt.edu/csonline/OS/Lessons/Processes/index.html 這個網站上面有一個關於進程狀態輪轉的動畫,做的真是太好了。

什麼是線程,線程和進程的區別

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

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

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

看完這篇操作系統,和麵試官扯皮就沒問題了 8

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

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

使用多線程的好處是什麼

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

能夠提高對用戶的響應順序在流程中的資源共享比較經濟適用能夠對多線程架構有深入的理解

什麼是 RR 調度算法

RR(round-robin) 調度算法主要針對分時系統,RR 的調度算法會把時間片以相同的部分並循環的分配給每個進程,RR 調度算法沒有優先級的概念。這種算法的實現比較簡單,而且每個線程都會佔有時間片,並不存在線程飢餓的問題。

導致系統出現死鎖的情況

死鎖的出現需要同時滿足下面四個條件

互斥(Mutual Exclusion):一次只能有一個進程使用資源。如果另一個進程請求該資源,則必須延遲請求進程,直到釋放該資源為止。保持並等待(Hold and Wait):必須存在一個進程,該進程至少持有一個資源,並且正在等待獲取其他進程當前所持有的資源。無搶占(No Preemption):資源不能被搶占,也就是說,在進程完成其任務之後,只能由擁有它的進程自動釋放資源。循環等待(Circular Wait) :必須存在一組{p0,p1,….. pn} 的等待進程,使p0 等待p1 持有的資源,p1 等待由p2 持有的資源, pn-1 正在等待由pn 持有的資源,而pn 正在等待由p0 持有的資源。

RAID 的不同級別

RAID 稱為 磁盤冗餘陣列,簡稱 磁盤陣列。利用虛擬化技術把多個硬盤結合在一起,成為一個或多個磁盤陣列組,目的是提升性能或數據冗餘。

RAID 有不同的級別

RAID 0 – 無容錯的條帶化磁盤陣列RAID 1 – 鏡像和雙工RAID 2 – 內存式糾錯碼RAID 3 – 比特交錯奇偶校驗RAID 4 – 塊交錯奇偶校驗RAID 5 – 塊交錯分佈式奇偶校驗RAID 6 – P + Q冗餘

什麼是 DMA

DMA 的中文名稱是直接內存訪問,它意味著 CPU 授予 I/O 模塊權限在不涉及 CPU 的情況下讀取或寫入內存。也就是 DMA 可以不需要 CPU 的參與。這個過程由稱為 DMA 控制器(DMAC)的芯片管理。由於 DMA 設備可以直接在內存之間傳輸數據,而不是使用 CPU 作為中介,因此可以緩解總線上的擁塞。 DMA 通過允許 CPU 執行任務,同時 DMA 系統通過系統和內存總線傳輸數據來提高系統並發性。

多線程編程的好處是什麼

對不起,我忍不住想偷笑

看完這篇操作系統,和麵試官扯皮就沒問題了 9

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

>ps:Doug Lea 大佬開發的 JUC 工具包,此處不加狗頭。

什麼是設備驅動程序

在計算機中,設備驅動程序是一種計算機程序,它能夠控製或者操作​​連接到計算機的特定設備。驅動程序提供了與硬件進行交互的軟件接口,使操作系統和其他計算機程序能夠訪問特定設備,不用需要了解其硬件的具體構造。

進程間的通信方式

通信概念

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

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

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

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

1. 任何時候兩個進程不能同時處於臨界區

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

3. 位於臨界區外的進程不得阻塞其他進程

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

看完這篇操作系統,和麵試官扯皮就沒問題了 10

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

解決方案

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

看完這篇操作系統,和麵試官扯皮就沒問題了 11

消息傳遞:消息傳遞是進程間實現通信和同步等待的機制,使用消息傳遞,進程間的交流不需要共享變量,直接就可以進行通信;消息傳遞分為發送方和接收方先進先出隊列:先進先出隊列指的是兩個不相關聯進程間的通信,兩個進程之間可以彼此相互進程通信,這是一種全雙工通信方式管道:管道用於兩個相關進程之間的通信,這是一種半雙工的通信方式,如果需要全雙工,需要另外一個管道。直接通信:在這種進程通信的方式中,進程與進程之間只存在一條鏈接,進程間要明確通信雙方的命名。間接通信:間接通信是通信雙方不會直接建立連接,而是找到一個中介者,這個中介者可能是個對像等等,進程可以在其中放置消息,並且可以從中刪除消息,以此達到進程間通信的目的。消息隊列:消息隊列是內核中存儲消息的鍊錶,它由消息隊列標識符進行標識,這種方式能夠在不同的進程之間提供全雙工的通信連接。共享內存:共享內存是使用所有進程之間的內存來建立連接,這種類型需要同步進程訪問來相互保護。

進程間狀態模型

cat chapter1 chapter2 chapter3 | grep tree

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

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

看完這篇操作系統,和麵試官扯皮就沒問題了 12

圖中會涉及三種狀態

運行態,運行態指的就是進程實際佔用CPU 時間片運行時就緒態,就緒態指的是可運行,但因為其他進程正在運行而處於就緒狀態阻塞態,除非某種外部事件發生,否則進程不能運行

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

三種狀態會涉及四種狀態間的切換,在操作系統發現進程不能繼續執行時會發生狀態1的輪轉,在某些系統中進程執行系統調用,例如 pause,來獲取一個阻塞的狀態。在其他系統中包括 UNIX,當進程從管道或特殊文件(例如終端)中讀取沒有可用的輸入時,該進程會被自動終止。

轉換 2 和轉換 3 都是由進程調度程序(操作系統的一部分)引起的,進程本身不知道調度程序的存在。轉換 2 的出現說明進程調度器認定當前進程已經運行了足夠長的時間,是時候讓其他進程運行 CPU 時間片了。當所有其他進程都運行過後,這時候該是讓第一個進程重新獲得 CPU 時間片的時候了,就會發生轉換 3。

>程序調度指的是,決定哪個進程優先被運行和運行多久,這是很重要的一點。已經設計出許多算法來​​嘗試平衡系統整體效率與各個流程之間的競爭需求。

當進程等待的一個外部事件發生時(如從外部輸入一些數據後),則發生轉換 4。如果此時沒有其他進程在運行,則立刻觸發轉換 3,該進程便開始運行,否則該進程會處於就緒階段,等待 CPU 空閒後再輪到它運行。

調度算法都有哪些

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

批處理中的調度

先來先服務

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

看完這篇操作系統,和麵試官扯皮就沒問題了 13

這個算法的強大之處在於易於理解和編程,在這個算法中,一個單鍊錶記錄了所有就緒進程。要選取一個進程運行,只要從該隊列的頭部移走一個進程即可;要添加一個新的作業或者阻塞一個進程,只要把這個作業或進程附加在隊列的末尾即可。這是很簡單的一種實現。

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

最短作業優先

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

看完這篇操作系統,和麵試官扯皮就沒問題了 14

如上圖 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、d。第一個作業在時間 a 結束,第二個在時間 a + b 結束,以此類推。平均周轉時間為 (4a + 3b + 2c + d) / 4 。顯然 a 對平均值的影響最大,所以 a 應該是最短優先作業,其次是 b,然後是 c ,最後是 d 它就只能影響自己的周轉時間了。

>需要注意的是,在所有的進程都可以運行的情況下,最短作業優先的算法才是最優的。

最短剩餘時間優先

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

交互式系統中的調度

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

輪詢調度

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

看完這篇操作系統,和麵試官扯皮就沒問題了 15

優先級調度

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

看完這篇操作系統,和麵試官扯皮就沒問題了 16

它的基本思想很明確,每個進程都被賦予一個優先級,優先級高的進程優先運行。

但是也不意味著高優先級的進程能夠永遠一直運行下去,調度程序會在每個時鐘中斷期間降低當前運行進程的優先級。如果此操作導致其優先級降低到下一個最高進程的優先級以下,則會發生進程切換。或者,可以為每個進程分配允許運行的最大時間間隔。當時間間隔用完後,下一個高優先級的進程會得到運行的機會。

最短進程優先

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

看完這篇操作系統,和麵試官扯皮就沒問題了 17

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

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

彩票調度

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

可以把彩票理解為 buff,這個 buff 有 15% 的機率能讓你產生 速度之靴 的效果。

公平分享調度

如果用戶 1 啟動了 9 個進程,而用戶 2 啟動了一個進程,使用輪轉或相同優先級調度算法,那麼用戶 1 將得到 90 % 的 CPU 時間,而用戶 2 將之得到 10 % 的 CPU 時間。

為了阻止這種情況的出現,一些系統在調度前會把進程的擁有者考慮在內。在這種模型下,每個用戶都會分配一些CPU 時間,而調度程序會選擇進程並強制執行。因此如果兩個用戶每個都會有 50% 的 CPU 時間片保證,那麼無論一個用戶有多少個進程,都將獲得相同的 CPU 份額。

頁面置換算法都有哪些

| 算法 | 註釋 |

| :——————– | :———————– |

| 最優算法 | 不可實現,但可以用作基準 |

| NRU(最近未使用) 算法 | 和 LRU 算法很相似 |

| FIFO(先進先出) 算法 | 有可能會拋棄重要的頁面 |

| 第二次機會算法 | 比 FIFO 有較大的改善 |

| 時鐘算法 | 實際使用 |

| LRU(最近最少)算法 | 比較優秀,但是很難實現 |

| NFU(最不經常食用)算法 | 和 LRU 很類似 |

| 老化算法 | 近似 LRU 的高效算法 |

| 工作集算法 | 實施起來開銷很大 |

| 工作集時鐘算法 | 比較有效的算法 |

最優算法在當前頁面中置換最後要訪問的頁面。不幸的是,沒有辦法來判定哪個頁面是最後一個要訪問的,因此實際上該算法不能使用。然而,它可以作為衡量其他算法的標準。 NRU 算法根據 R 位和 M 位的狀態將頁面氛圍四類。從編號最小的類別中隨機選擇一個頁面。 NRU 算法易於實現,但是性能不是很好。存在更好的算法。 FIFO 會跟踪頁面加載進入內存中的順序,並把頁面放入一個鍊錶中。有可能刪除存在時間最長但是還在使用的頁面,因此這個算法也不是一個很好的選擇。第二次機會算法是對 FIFO 的一個修改,它會在刪除頁面之前檢查這個頁面是否仍在使用。如果頁面正在使用,就會進行保留。這個改進大大提高了性能。時鐘 算法是第二次機會算法的另外一種實現形式,時鐘算法和第二次算法的性能差不多,但是會花費更少的時間來執行算法。 LRU 算法是一個非常優秀的算法,但是沒有特殊的硬件(TLB)很難實現。如果沒有硬件,就不能使用 LRU 算法。 NFU 算法是一種近似於 LRU 的算法,它的性能不是非常好。老化 算法是一種更接近 LRU 算法的實現,並且可以更好的實現,因此是一個很好的選擇最後兩種算法都使用了工作集算法。工作集算法提供了合理的性能開銷,但是它的實現比較複雜。 WSClock 是另外一種變體,它不僅能夠提供良好的性能,而且可以高效地實現。

最好的算法是老化算法和WSClock算法。他們分別是基於 LRU 和工作集算法。他們都具有良好的性能並且能夠被有效的實現。還存在其他一些好的算法,但實際上這兩個可能是最重要的。

影響調度程序的指標是什麼

會有下面幾個因素決定調度程序的好壞

CPU 使用率:

CPU 正在執行任務(即不處於空閒狀態)的時間百分比。

等待時間

這是進程輪流執行的時間,也就是進程切換的時間

吞吐量

單位時間內完成進程的數量

響應時間

這是從提交流程到獲得有用輸出所經過的時間。

周轉時間

從提交流程到完成流程所經過的時間。

什麼是殭屍進程

殭屍進程是已完成且處於終止狀態,但在進程表中卻仍然存在的進程。殭屍進程通常發生在父子關係的進程中,由於父進程仍需要讀取其子進程的退出狀態所造成的。

看完這篇操作系統,和麵試官扯皮就沒問題了 18