操作系統總結

作業系統總結#

一、概述#

並發和並行#

並發: 一個處理器同時處理多個任務，這裡的同時是宏觀概念，指的是在某個時間段內這些任務交替執行
並行: 多個處理器或者是多核的處理器同時處理多個不同的任務，這裡的同時就是同一時刻真正的一塊兒執行多個任務

共享#

共享是指系統中的資源可以被多個並發進程共同使用，有兩種共享方式：互斥共享和同時共享
互斥共享的資源稱為臨界資源，例如打印機等，在同一時間只允許一個進程訪問，需要用同步機制來實現對臨界資源的訪問

虛擬#

虛擬技術把一個物理實體轉換為多個邏輯實體，主要有兩種虛擬技術：時分復用技術和空分復用技術。例如多個進程能在同一個處理器上並發執行使用了時分復用技術，讓每個進程輪流占有處理器，每次只執行一小個時間片並快速切換

同步和異步#

同步就是整個處理過程順序執行，當各個過程都執行完畢，並返回結果。是一種線性執行的方式，執行的流程不能跨越。一般用於流程性比較強的程序，比如用戶登錄，需要對用戶驗證完成後才能登錄系統。
異步則是只是發送了調用的指令，調用者無需等待被調用的方法完全執行完畢；而是繼續執行下面的流程。是一種並行處理的方式，不必等待一個程序執行完，可以執行其它的任務，比如頁面數據加載過程，不需要等所有數據獲取後再顯示頁面。

內核態和用戶態#

內核態：cpu 可以訪問內存的所有數據，包括外圍設備，例如硬盤，網卡，cpu 也可以將自己從一個程序切換到另一個程序。
用戶態：只能受限的訪問內存，且不允許訪問外圍設備，占用 cpu 的能力被剝奪，cpu 資源可以被其他程序獲取
用戶態切換到內核態的 3 種方式: 系統調用、異常、外圍設備的中斷

二、進程與線程#

進程#

進程是一個正在執行程序的示例，擁有自己的程序計數器和內部狀態，是系統進行資源分配和調度的一個獨立單位。進程控制塊 (Process Control Block， PCB) 描述進程的基本信息和運行狀態，所謂的創建進程和撤銷進程，都是指對 PCB 的操作

線程#

線程是獨立調度的基本單位。一個進程中可以有多個線程，它們共享進程資源。就拿瀏覽器來說，瀏覽器進程裡面有很多線程，例如 HTTP 請求線程、事件響應線程、渲染線程等等，線程的並發執行使得在瀏覽器中點擊一個新鏈接從而發起 HTTP 請求時，瀏覽器還可以響應用戶的其它事件

區別#

擁有資源
進程是資源分配的基本單位，但是線程不擁有資源，線程可以訪問隸属進程的資源
調度
線程是獨立調度的基本單位，在同一進程中，線程的切換不會引起進程切換，從一個進程內的線程切換到另一個進程中的線程時，會引起進程切換
系統開銷
由於創建或撤銷進程時，系統都要為之分配或回收資源，如內存空間、I/O 設備等，所付出的開銷遠大於創建或撤銷線程時的開銷。類似地，在進行進程切換時，涉及當前執行進程 CPU 環境的保存及新調度進程 CPU 環境的設置，而線程切換時只需保存和設置少量寄存器內容，開銷很小
通信方面
進程間通信 (IPC) 需要進程同步和互斥手段的輔助，以保證數據的一致性。而線程間可以通過直接讀 / 寫同一進程中的數據段（如全局變量）來進行通信

進程的狀態#

就緒態 就是獲取了出 cpu 外的所有資源，只要處理器分配資源就可以馬上執行。
運行態 就是獲得了處理器分配的資源，程序開始執行。
阻塞態 當程序條件不夠時，需要等待條件滿足時才能執行，如等待 i/o 操作時，此刻的狀態就叫阻塞態。

線程的狀態#

新建（New）：線程在進程內派生出來，它即可由進程派生，也可由線程派生。
阻塞（Block）：如果一個線程在執行過程中需要等待某個事件發生，則被阻塞。
激活（Unblock）：如果阻塞線程的事件發生，則該線程被激活並進入就緒隊列。
調度（Schedule）：選擇一個就緒線程進入執行狀態。
結束（Finish）：如果一個線程執行結束，它的寄存器上下文以及堆棧內容等將被釋放

線程的實現方式#

在用戶空間中實現線程
用戶級線程指不需要內核支持而在用戶程序中實現的線程，其不依賴於操作系統核心，應用進程利用線程庫提供創建、同步、調度和管理線程的函數來控制用戶線程。不需要用戶態 / 核心態切換，速度快，操作系統內核不知道多線程的存在，因此一個線程阻塞將使得整個進程（包括它的所有線程）阻塞。由於這裡的處理器時間片分配是以進程為基本單位，所以每個線程執行的時間相對減少。
在內核中實現線程
內核級線程由操作系統內核創建和撤銷。內核維護進程及線程的上下文信息以及線程切換。一個內核線程由於 I/O 操作而阻塞，不會影響其它線程的運行。
在用戶空間中實現線程的優勢
1. 可以在不支持線程的操作系統中實現。
2. 創建和銷毀線程、線程切換代價等線程管理的代價比內核線程少得多
3. 允許每個進程定制自己的調度算法，線程管理比較靈活
4. 線程能夠利用的表空間和堆棧空間比內核級線程多
在用戶空間中實現線程的缺點
1. 同一進程中只能同時有一個線程在運行，如果有一個線程使用了系統調用而阻塞，那麼整個進程都會被掛起。
2. 頁面失效也會導致整個進程都會被掛起。
3. 內核線程的優缺點剛好跟用戶線程相反。實際上，操作系統可以使用混合的方式來實現線程

協程#

協程，英文 Coroutines，是一種比線程更加輕量級的存在。正如一個進程可以擁有多個線程一樣，一個線程也可以擁有多個協程。最重要的是，協程不是被操作系統內核所管理，而完全是由程序所控制（也就是在用戶態執行）。這樣帶來的好處就是性能得到了很大的提升，不會像線程切換那樣消耗資源。其本質是用戶空間下的線程。（即不存在上下文切換，用戶與內核地址空間切換，但協程是在單線程中運行）

協程的應用#

Lua 從 5.0 版本開始使用協程，通過擴展庫 coroutine 來實現。
Python 可以通過 yield/send 的方式實現協程。在 python 3.5 以後，async/await 成為了更好的替代方案。
Go 語言對協程的實現非常強大而簡潔，可以輕鬆創建成百上千個協程並發執行。
Java 語言並沒有對協程的原生支持，但是某些開源框架模擬出了協程的功能，Kilim 框架的源碼

疑問和思考#

網上關於進程和線程狀態的介紹太雜，不太能理解這兩者的關係，目前在我理解來看，其實進程應該也包括新建和結束，這就和線程其實是一樣的，而且我認為只有運行、就緒、阻塞這三種算是基本狀態，其他比如新建結束、喚醒等應該只能算作是切換狀態的操作
在 Java 的線程還多了一種等待(Waiting)狀態，其實只是把阻塞狀態更細化分成了BLOCKED和WAITING兩種，區別在於等待是主動等待，阻塞是被動阻塞，就是說等待的狀態下只有主動去喚醒它才能進入就緒狀態，而阻塞的情況下線程本身一直在爭搶鎖，一旦搶到了不需要別人主動去喚醒它自己就會切換到就緒狀態

參考鏈接#

三、進程間通信方式#

管道#

管道是連接兩個讀進程和一個寫進程之間用於實現數據交換的一個共享文件

它是半雙工的（即數據只能在一個方向上流動），具有固定的讀端和寫端，只有同時有讀端和寫端，管道才有存在意義
當讀端發現管道為空的時候需要睡眠等待，直到有數據的時候被喚醒，相應的寫端也是在管道已滿的時候等待直到被喚醒
它可以看成是一種特殊的文件，對於它的讀寫也可以使用普通的 read、write 等函數。但是它不是普通的文件，並不屬於其他任何文件系統，並且只存在於內存中
互斥：統一時刻只能有一個進程對管道進行讀寫；
包括無名管道和有名管道兩種，前者用於父進程和子進程間的通信，後者用於運行於同一台機器上的任意兩個進程間的通信

消息隊列#

是消息的鏈接表，存放在內核中。一個消息隊列由一個標識符（即隊列 ID）來標識。

消息隊列是面向記錄的，其中的消息具有特定的格式以及特定的優先級
消息隊列獨立於發送與接收進程，進程終止時，消息隊列及其內容並不會被刪除
消息隊列可以實現消息的隨機查詢，消息不一定要以先進先出的次序讀取，也可以按消息的類型讀取

信號 (signal)#

一種比較複雜的通信方式，用於通知接收進程某個事件已經發生，是進程間通信機制中唯一的異步通信機制

信號量（semaphore）#

與已經介紹過的 IPC 結構不同，它是一個計數器。信號量用於實現進程間的互斥與同步，而不是用於存儲進程間通信數據。

信號量用於進程間同步，若要在進程間傳遞數據需要結合共享內存
信號量基於操作系統的 PV 操作，程序對信號量的操作都是原子操作
每次對信號量的 PV 操作不僅限於對信號量值加 1 或減 1，而且可以加減任意正整數。
支持信號量組
注意⚠️: 信號量和信號不是一個概念，兩者區別很大

共享內存（Shared Memory）#

指兩個或多個進程共享一個給定的存儲區。

共享內存是最快的一種 IPC，因為進程是直接對內存進行存取
因為多個進程可以同時操作，所以需要進行同步
信號量 + 共享內存通常結合在一起使用，信號量用來同步對共享內存的訪問

套接字#

套接字也是一種進程間通信機制，可以實現不同主機間的進程通信。一個套接口可以看做是進程間通信的端點，每個套接口的名字是唯一的，其他進程可以訪問，連接和進行數據通信

總結#

管道：速度慢，容量有限
消息隊列：容量受到系統限制，且要注意第一次讀的時候，要考慮上一次沒有讀完數據的問題
信號量：不能傳遞複雜消息，只能用來同步
共享內存區：能夠很容易控制容量，速度快，但要保持同步，比如一個進程在寫的時候，另一個進程要注意讀寫的問題，相當於線程中的線程安全，當然，共享內存區同樣可以用作線程間通訊，不過沒這個必要，線程間本來就已經共享了同一進程內的一塊內存

四、同步機制#

背景#

多進程（線程）並發執行會出現進程間相互制約的情況發生，例如兩個進程需要：
1. 共享唯一的硬件設備
2. 共享同一塊內存區域
3. 一個進程的運行依賴另一進程對共享資源的執行結果

如果多個進程間存在時序關係，需要協同工作以完成一項任務，則稱為同步；如果不滿足協同的條件，而只是因為共享具有排他性資源時所產生的關係稱為互斥，互斥是一種特殊的同步

對於同步機制，需要遵循以下四個規則
1. 空閒則入：沒有進程 / 線程在臨界區時，任何進程可以進入；
2. 忙則等待：有進程 / 線程在臨界區時，其他進程均不能進入臨界區；
3. 有限等待：等待進入臨界區的進程 / 線程不能無限期等待；
4. 讓權等待（可選）：不能進入臨界區的進程 / 線程，應該釋放 CPU，如轉換到阻塞態

信號量#

信號量和PV原語操作是由 Dijkstra 發明的，它是最為廣泛的互斥方法之一
信號量和 PV 操作原理：
1. 當進程想要進入共享區時，首先執行 P 操作，S-1
2. 當進程想要退出共享區時，執行 V 操作，S+1
3. 進程進出共享區的操作，是原子操作（執行過程不允許被中斷）
缺陷：程序的易讀性相對較差，對於信號量的管理也分散在各個參與對象中，因此有可能引起死鎖，進程餓死等問題

管程 (進程同步獨有)#

管程是對 Semaphore 機制的延伸和改善，是一種更簡單的同步手段
管程是可以被多個進程 / 線程安全訪問的對象或模塊
管程匯總的方法是受到 Mutex 保護的，意味著同一時刻只允許一個訪問者來使用它們
特性: 安全性、互斥性、共享性

臨界區（線程同步）#

通過對多線程的串行化來訪問公共資源或一段代碼，速度快，適合控制數據訪問
在任意時刻只允許一個線程對共享資源進行訪問，如果有多個線程試圖訪問公共資源，那麼在有一個線程進入後，其他試圖訪問公共資源的線程將被掛起，並一直等到進入臨界區的線程離開，臨界區在被釋放後，其他線程才可以搶占

互斥#

互斥不僅能實現同一應用程序的公共資源安全共享，還能實現不同應用程序的公共資源安全共享
互斥量比臨界區複雜。因為使用互斥不僅僅能夠在同一應用程序不同線程中實現資源的安全共享，而且可以在不同應用程序的線程之間實現對資源的安全共享

事件（線程同步）#

通過通知操作的方式來保持線程的同步，還可以方便實現對多個線程的優先級比較的操作

進程和線程之間同步機制的差異#

信號量、管程、互斥是進程的同步機制，而信號量、互斥也可用於線程的同步，但管程只在進程同步中被用到；
線程的同步除了信號量、互斥外，還有臨界區、事件，沒有看到說將這兩種方式作為進程的同步方式（不知道）；

經典同步問題#

生產者-消費者問題
哲學家就餐問題
讀者-寫者問題

具體參考:

參考鏈接#

五、死鎖#

死鎖是指多個進程在運行過程中，因為爭奪資源而造成的一種僵局，如果沒有外力推進，處於僵局中的進程就無法繼續執行

產生死鎖的原因#

系統資源不足。
進程運行推進的順序不當。
資源分配不當等

產生死鎖的四個必要條件#

互斥條件: 進程對所分配的資源進行排他性的使用
請求和保持條件：進程被阻塞的時候並不釋放鎖申請到的資源
不可剝奪條件：進程對於已經申請到的資源在使用完成之前不可以被剝奪
環路等待條件：發生死鎖的時候存在的一個進程 - 資源環形等待鏈

死鎖處理#

預防死鎖：破壞產生死鎖的 4 個必要條件中的一個或者多個；實現起來比較簡單，但是如果限制過於嚴格會降低系統資源利用率以及吞吐量
避免死鎖：在資源的動態分配中，防止系統進入不安全狀態（可能產生死鎖的狀態）- 如銀行家算法，參考銀行家算法
檢測死鎖：允許系統運行過程中產生死鎖，在死鎖發生之後，採用一定的算法進行檢測，並確定與死鎖相關的資源和進程，採取相關方法清除檢測到的死鎖。實現難度大
解除死鎖：與死鎖檢測配合，將系統從死鎖中解脫出來（撤銷進程或者剝奪資源）。對檢測到的和死鎖相關的進程以及資源，通過撤銷或者掛起的方式，釋放一些資源並將其分配給處於阻塞狀態的進程，使其轉變為就緒態。實現難度大

六、調度算法#

`先來先服務FCFS`#

既可以作為作業調度算法也可以作為進程調度算法；按作業或者進程到達的先後順序依次調度；因此對於長作業比較有利。

`短作業優先SPF`#

作業調度算法，算法從就緒隊列中選擇估計時間最短的作業進行處理，直到得出結果或者無法繼續執行；缺點：不利於長作業；未考慮作業的重要性；運行時間是預估的，並不可靠。

`高優先權優先HRRF`#

既可以作為作業調度也可以作為進程調度算法；調度作業時，從就緒隊列中選擇優先級最高的作業進行處理；由於涉及到了優先級，因此可以分為搶佔式和非搶佔式；而且優先級的確定也可以分為靜態優先級（事先根據進程類型，進程對資源的需求，用戶要求等方面確定一個固定值）；動態優先級（隨進程的推進或者等待時間而增加或者減少）。

`最高響應比優先HRN`#

FCFS 可能造成短作業用戶不滿，SPF 可能使得長作業用戶不滿，於是提出 HRN，選擇響應比最高的作業運行。響應比 = 1 + 作業等待時間 / 作業處理時間。

`時間片輪轉`#

按到達的先後對進程放入隊列中，然後給隊首進程分配 CPU 時間片，時間片用完之後計時器發出中斷，暫停當前進程並將其放到隊列尾部，循環。

`多級反饋隊列`#

目前公認較好的調度算法；設置多個就緒隊列並為每個隊列設置不同的優先級，第一個隊列優先級最高，其餘依次遞減。優先級越高的隊列分配的時間片越短，進程到達之後按 FCFS 放入第一個隊列，如果調度執行後沒有完成，那麼放到第二個隊列尾部等待調度，如果第二次調度仍然沒有完成，放入第三隊列尾部…。只有當前一個隊列為空的時候才會去調度下一個隊列的進程

七、內存管理#

基本知識#

連接#

生成裝入模塊形成完整邏輯地址
三種連接方式：

靜態連接: 裝入前連接
裝入時動態連接: 運行前邊裝入邊連接
運行時動態連接: 運行時需要才裝入並連接

目的：確定完整的邏輯地址

裝入#

裝入內存形成物理地址

三種裝入方式：

絕對裝入：編譯時產生絕對地址，單道程序環境
靜態重定位：裝入時將邏輯地址轉化為物理地址，多道批處理操作系統
動態重定位：運行時將邏輯地址轉化為物理地址，需要設置定位寄存器，現代操作系統

目的：確定最終的物理地址

碎片#

內部碎片（已分配），分配給某進程的內存區域中，而之有些部分沒有用上
外部碎片（未分配），內存中某些空閒分區由於太小而難以利用

連續分配管理方式#

單一連續分配: 內存分為系統區和用戶區，只能有一道用戶程序（無外部碎片，有內部碎片）
固定分區分配: 將整個用戶空間劃分若干個固定大小的分區，分區大小可相等也可不相等，每個分區只能裝入一道作業，分區說明表進行管理（無外部碎片，有內部碎片）
動態分區分配: 根據進程的大小動態地建立分區，使用空閒分區表或空閒分區鏈進行管理，動態分區算法選擇合適的空閒分區分配（有外部碎片，無內部碎片）

動態分區分配算法#

`首次適應算法（FF）`#

在分配內存時，從空閒分區表的頭開始查找，直到找到第一個大小能夠滿足的空閒分區為止。
該算法實現簡單，優先利用低地址的空閒分區，從而保留了高地址部分的大空閒分區，為後期的大作業分配大的內存空間創造了條件，缺點是低地址部分不斷被劃分，留下了很多難以利用的，很小的空閒分區，且每次查找都是從地址址部分開始查找，無疑會增加查找的開銷

`循環首次適應算法（NF）`#

和首次適應算法所不同，在為進程分配內存空間時，不再是每次都從低地址開始查找，而是從上次找到的空閒分區的下一個空閒分區開始查找，因此需要設置一個查詢指針，用來指示下一次起始查詢的空閒分區，如果最後一個空閒分區的大小仍然不能滿足要求，則應該返回到第一個空閒分區。該算法使空閒分區二分內部得更均勻，適當減少了查找空閒分區時候的開銷，但這樣容易拆分大的空閒分區

`最佳適應算法（BF）`#

每次為作業分配內存的時候，總是把滿足要求的，但又是最小的空閒分區分配給進程，即尋找一個空閒分區，使得的值最小，這樣可以避免 “大材小用”，但是容易產生細小的碎片

`最壞適應算法（WF）`#

和最佳適應算法相反，它總是為進程挑選滿足要求的，但又是最大的空閒區分配給進程，即尋找一個空閒分區，使得的值最大，這樣可以使產生碎片的可能性最小，對中小作業有利

非連續分配管理方式#

基本分頁存儲管理#

基本分頁存儲管理中不具備頁面置換功能（即沒有實現虛擬內存的功能），因此需要整個程序的所有頁面都裝入內存之後才可以運行。因為程序數據存儲在不同的頁面中，而頁面又離散的分布在內存中，因此需要一個頁表來記錄邏輯地址和實際存儲地址之間的映射關係，以實現從頁號到物理塊號的映射。由於頁表也是存儲在內存中的，因此和不適用分頁管理的存儲方式相比，訪問分頁系統中內存數據需要兩次的內存訪問（一次是從內存中訪問頁表，從中找到指定的物理塊號，加上頁內偏移得到實際物理地址；第二次就是根據第一次得到的物理地址訪問內存取出數據）。

為了減少兩次訪問內存導致的效率影響，分頁管理中引入了快表（或者聯想寄存器）機制（聯想到緩存機制），包含快表機制的內存管理中，當要訪問內存數據的時候，首先將頁號在快表中查詢，如果查找到說明要訪問的頁表項在快表中，那麼直接從快表中讀取相應的物理塊號；如果沒有找到，那麼訪問內存中的頁表，從頁表中得到物理地址，同時將頁表中的該映射表項添加到快表中，可能存在快表換出算法

優缺點：沒有外部碎片，內存利用率高。但各頁中內容沒有關聯，不利於編程和共享

補充概念：

頁框 = 頁幀 = 內存塊 = 物理塊 = 物理頁面（內存分區）
頁 = 頁面（進程邏輯地址空間分區）
頁面和頁框一一對應（頁表，頁表項由 “頁號” 和 “塊號” 組成，頁號不占用內存空間）
頁表長度是指這個頁表中總共有幾個頁表項，即總共有幾個頁；
頁表項長度是指每個頁表項占多大的存儲空間；
頁面大小是指一個頁面占多大的存儲空間

基本分段存儲管理#

把程序按內容或過程（函數）關係分成段，每段有自己的名字。一個用戶作業或進程所包含的段對應一個二維線形虛擬空間，也就是一個二維虛擬存儲器。段式管理程序以段為單位分配內存，然後通過地址影射機構把段式虛擬地址轉換為實際內存物理地址

進程的地址空間：按照程序自身的邏輯關係劃分為若干個段，每段有段名且每段從 0 開始編址；
邏輯地址結構：段號和段內地址（段內偏移量）；
內存分配規則：以段為單位進行分配，每個段在內存中占據連續的空間，各段不相鄰；
段表中的段表項由段號（隱含的，不占存儲空間）、段長、基地址組成；
與頁表地址轉換的不同之處在於增加了還要根據段表中記錄的段長來檢查段內地址是否越界

優缺點:

可以針對不同類型的段採取不同的保護
可以按段為單位來進行共享，包括通過動態鏈接進行代碼共享
不會產生內部碎片，但會產生外部碎片，內存利用率比分頁低

分段和分頁的區別#

頁是信息的物理單位，是出於系統內存利用率的角度提出的離散分配機制；段是信息的邏輯單位，每個段含有一組意義完整的信息，是出於用戶角度提出的內存管理機制。
頁的大小是固定的，由系統決定；段的大小是不確定的，由用戶決定。
分頁的邏輯地址結構是一維的（偏移量），分段是二維的（段名 + 偏移量）

段頁式存儲管理#

將進程按邏輯模塊分段後再將每個段分頁，不會產生外部碎片，只會產生少量內部碎片；
邏輯地址結構（二维）：段號、頁號、頁內偏移地址 + 頁號、頁面存放的塊號；

地址變換：由邏輯地址得到短號、頁號、頁內偏移量 --> 段號與段表寄存器中的段長度比較，檢查是否越界 --> 由段表始址、段號找到對應段表項 --> 根據段表中記錄的頁表長度，檢查頁號是否越界 --> 由段表中的頁表地址、頁號查詢頁表項 --> 由塊號和頁內偏移得到物理地址 --> 訪問目標單元

簡單來說，流程就是 3 次訪存：查段表 --> 查頁表 --> 訪問目標單元（設置了快表的話可以做到 1 次訪存）

內存空間的擴充#

覆蓋技術#

覆蓋技術包含一個固定區（區內程序段在運行過程中不會調入調出）和若干覆蓋區（區內程序段在運行過程中需要調入和調出），對用戶不透明增加用戶編程負擔，是在同一個程序或者進程中進行的

交換技術#

交換技術是內存緊張時，換出某些進程以騰出內存空間，再換入某些進程，而外存磁碟分為文件區和對換區，換出的進程放在對換區，是在不同進程（或作業）之間的

虛擬存儲技術（虛擬內存）#

虛擬內存使用的原理：局部性原理（聯想到 Mysql 中利用 B 樹作為索引的數據結構原因）
1. 時間局部性：現在訪問的指令和數據在不久後會被訪問
2. 空間局部性：現在訪問的內存單元周圍的內存空間，很可能在不久後會被訪問
3. 高速緩存技術：使用頻繁的數據放到更高速的存儲器中

基於局部性原理，在程序裝入時，可以將程序的一部分裝入內存，而將其餘部分留在外存，就可以啟動程序執行。在程序執行過程中，當所訪問的信息不在內存時，由操作系統將所需要的部分調入內存，然後繼續執行程序。另一方面，操作系統將內存中暫時不使用的內容換出到外存上，從而騰出空間存放將要調入內存的信息。這樣，系統好像為用戶提供了一個比實際內存大得多的存儲器，稱為虛擬存儲器

虛擬內存的定義：程序不需要全部裝入即可運行，運行時動態調入，若內存不夠則進行置換
虛擬內存的特徵
1. 多次性：無需在作業運行時一次性全部裝入內存，而是允許被分為多次調入內存
2. 對換性：無需在作業運行時一直常駐內存，而是允許在作業運行過程中，將作業換入和換出
3. 虛擬性：邏輯上擴充內存容量，用戶看到的內存容量遠大於實際容量
虛擬內存技術的實現: 請求分頁存儲管理，請求分段存儲管理，請求段頁式存儲管理
使用虛擬內存的代價
1. 虛存的管理需要建立很多數據結構，占用額外內存。
2. 虛擬地址到物理地址的轉換，增加了指令執行時間。
3. 頁式的換入換出需要磁碟 I/O，耗費時間。
4. 如果一頁中只有部分數據，浪費內存

頁面置換算法#

`最優頁面置換算法(OPT)`#

只具有理論意義的算法，用來評價其他頁面置換算法。置換策略是將當前頁面中在未來最長時間內不會被訪問的頁置換出去。

`先進先出置換算法(FIFO)`#

由操作系統維護一個所有當前在內存中的頁面的鏈表，最新進入的頁面放在表尾，最早進入的頁面放在表頭；當發生缺頁中斷時，淘汰表頭的頁面並將新調入的頁面追加到表尾。簡單粗暴的一種置換算法，沒有考慮頁面訪問頻率信息。

`最近最少使用算法(LRU)`#

算法賦予每個頁面一個訪問字段，用來記錄上次頁面被訪問到現在所經歷的時間 t，每次置換的時候把 t 值最大的頁面置換出去（實現方面可以採用寄存器或者棧的方式實現）。

`時鐘置換算法(也被稱為最近未使用算法NRU)`#

頁面設置一個訪問位，頁面被訪問的時候訪問位設置為 1；並將所有頁面保存在一個循環隊列中，表針指向最老的頁面。頁面置換的時候，如果當前指針所指頁面訪問為為 0，那麼置換，否則將其置為 0，循環直到遇到一個訪問為位 0 的頁面。

`改進型Clock算法`#

在 Clock 算法的基礎上添加一個修改位，替換時根據訪問位和修改位綜合判斷。優先替換訪問為和修改位都是 0 的頁面，其次是訪問位為 0 修改位為 1 的頁面。

`最少使用算法(LFU)`#

設置寄存器記錄頁面被訪問次數，每次置換的時候置換當前訪問次數最少的。存在問題是該訪問寄存器並不能真正反映當前頁面訪問次數，因為訪問速度比較快，所以在更新寄存器的時間間隔內訪問 1 次和訪問 100 次都是一樣的。另外，LFU 和 LRU 是很類似的，支持硬件也是一樣的，但是區分兩者的關鍵在於一個以時間為標準，一個以次數為標準（例如對於寄存器 pa 001111 和 pb 111000，兩個頁面，如果採用 LRU，那麼被淘汰的是 pa，如果採用 LFU 那麼被淘汰的是 pb）。

`頁面緩衝算法(PBA)`#

置換的時候，頁面無論是否被修改過，都不被置換到磁碟，而是先暫留在內存中的頁面鏈表（已修改頁面鏈表和未修改頁面鏈表，也可以不區分）裡面，當其再次被訪問的時候可以直接從這些鏈表中取出而不必進行磁碟 IO，當鏈表中已修改也難數目達到一定數量之後，進行依次寫磁碟操作（相當於將多次 IO 合併為一次）

頁面分配策略#

駐留集：是指請求分頁存儲管理中給進程分配的物理塊的集合（即是系統給進程分配的物理塊數）

固定分配局部置換：進程運行前就分配好駐留集，缺頁時只能換出進程自己的某一頁

可變分配全局置換：只要缺頁就分配新的物理塊，可能來自空閒物理塊，也可能需換出別的進程頁面

可變分配局部置換：根據發生缺頁的頻率來動態地增加或減少進程的物理塊

何時調入頁面：預調頁策略（運行前）；請求調頁策略（運行時）

何處調用頁面：UNIX 方式：第一次使用的頁面都從文件區調入，調出的頁面都寫回對換區，再次使用時從對換區調入

抖動（顛簸）現象：由於分配給進程的物理塊不夠導致，剛剛換出的頁面馬上又換入主存，剛剛換入的頁面馬上就要換出主存 ------> 如果是因為頁面替換策略失誤，可以修改替換算法來解決這個問題；如果是因為運行的程序太多，造成程序無法同時將所有頻繁訪問的頁面調入內存，則要降低多道程序的數量；否則終止該進程或者增加駐留集大小

工作集：是指在某段時間間隔裡，進程實際訪問頁面的集合（駐留集大小一般不小於工作集大小來防止抖動現象）

補充:

缺頁中斷（或頁錯誤）: 當程序引用到一部分不在物理內存中的地址空間時，由操作系統負責將缺失部分裝入物理內存並重新執行失敗的指令
一道計算缺頁中斷的例題
Belady異常：採用 FIFO 算法時，如果對一個進程未分配它所要求的全部頁面，有時就會出現分配的頁面數增多但缺頁率反而提高的異常現象

八、文件系統#

磁碟調度算法#

先來先服務（FCFS）
最短尋道時間優先（SSTF）：讓離當前磁道最近的請求訪問者啟動磁碟驅動器，即是讓查找時間最短的那個作業先執行，而不考慮請求訪問者到來的先後次序，這樣就克服了先來先服務調度算法中磁臂移動過大的問題
掃描算法（SCAN）或電梯調度算法：總是從磁臂當前位置開始，沿磁臂的移動方向去選擇離當前磁臂最近的那個柱面的訪問者。如果沿磁臂的方向無請求訪問時，就改變磁臂的移動方向。在這種調度方法下磁臂的移動類似於電梯的調度，所以它也稱為電梯調度算法。
循環掃描算法（CSCAN）：循環掃描調度算法是在掃描算法的基礎上改進的。磁臂改為單項移動，由外向內。當前位置開始沿磁臂的移動方向去選擇離當前磁臂最近的哪個柱面的訪問者。如果沿磁臂的方向無請求訪問時，再回到最外，訪問柱面號最小的作業請求
NStepSCAN算法: N 步 SCAN 算法將磁碟請求隊列分成若干個長度為 N 的子序列，磁碟調度按 FCFS 算法依次處理這裡子隊列，而每個子隊列的內部是根據 SCAN 算法進行處理的。當 N 很大的時候，算法接近於 SCAN 算法，當 N=1 時，退化成 FCFS 算法。N 步 SCAN 算法可以有效避免 “磁臂粘著” 的現象

九、IO 模型#

參考: 操作系統中的 I/O，及高性能 IO 模型

設備之間的 IO#

輪詢方式
CPU 主動在各種設備中輪詢檢查狀態，有數據就 IO
中斷方式
設備有數據的時候，發出中斷，由 CPU 決定要不要響應中斷，然後中斷，去處理設備的 IO。CPU 不用經常輪詢設備狀態。被動接收中斷就行
直接內存存取（DMA）訪問方式
如果 1 個字節的數據中斷一次，傳 1KB 的數據得中斷 1024 次，太浪費 CPU 時間，於是有了 DMA 方式，CPU 只需要把開頭和結束的地址告訴 DMA，中間由 DMA 完成數據 IO。CPU 從字節干預解放到數據塊的干預
通道控制方式
DMA 方式只能控制一個設備的一塊數據，多塊數據還是要 CPU 干預多次。於是有了通道來控制 IO，它比 DMA 更強大，能控制多塊數據，多個設備的 IO，更加解放了 CPU 參與 IO 過程

用戶進程間的 IO#

阻塞
用戶線程調用某些系統函數去內核取數據，直到數據到達內核 cache 前，該線程處於阻塞狀態，等待數據到達
非阻塞
用戶線程去取數據，不管內核 cache 有沒有數據，都直接返回，可能拿到數據，也可能拿不到，不會使線程進入阻塞態
IO多路復用
多路就是一個線程管理多路 IO，線程還是被阻塞調用，其中一路或幾路 IO 有數據了就返回。需要線程遍歷全部 IO，判斷是哪个 IO 有數據。
例如 socket 的 select () 函數，線程調用 select () 進入阻塞態，任何一個 IO 有數據了，線程就退出阻塞態，獲得機會繼續執行。
信號驅動IO
給一個 IO 註冊一個信號和信號觸發的回調函數，一旦信號被觸發，回調函數裡讀取數據。
例如給 socket 註冊一個 “可讀” 的信號，當數據來了，可讀的時候，信號被觸發，執行回調函數從內核 cache 複製數據到用戶空間
異步IO
異步 IO 中，操作系統完成了數據從內核到用戶空間的拷貝後，以信號的方式通知用戶線程可以下一步操作。省去了用戶線程阻塞下來拷貝數據的過程

select，epoll，kqueue 原理#

select
select 管理多個 socket，select 收到一個來自網卡 IO 中斷就返回，不知道這個中斷對應是哪个 socket fd 的。需要用戶線程遍歷判斷
epoll
epoll 收到一個 IO 中斷，會去查找這個中斷對應哪個 socket fd。
epoll 中建立一個紅黑樹（平衡二叉樹的一種），紅黑樹查找很高效。
用戶註冊感興趣的 socket 事件，就是把這個 socket fd 插入到紅黑樹中，用中斷號做 key，可以理解為（中斷號，socket fd）的二元組。
用戶移除事件就是，刪除樹上的某個節點。

然後收到一個 IO 中斷，epoll 把網卡數據拷貝到內核 cache，根據中斷號在紅黑樹中查找對應的 fd，把 fd 加入到就緒鏈表中，準備返回給用戶線程。用戶直接得到就緒的 fd

kqueue
收到 socket IO 中斷去哈希表中查找對應的 socket fd，再把它放到一個鏈表裡，返回。
用戶註冊一個感興趣的事件，就是往哈希表中添加一個 fd