操作系統圖解
重讀William Stallings的Operating System的個人總結，未涉及安全和分布式部分（這部分在英文版中被閹割了）。
上一張完成的大圖，然后再慢慢畫起（在每個圖后面加鏈接看大圖）。另外這里只是簡單的知識點羅列，同樣發布了一篇完整的（2w字，還沒來得及校對）總結，歡迎查看。
計算機組成
先從最簡單的開畫，這里計算機的組成員工就三層：應用程序、操作系統、硬件。操作系統的作用是管理資源（各種硬件、計算資源、時間等），職稱程序的運行（提供了必要的庫支持）。
硬件層
先來看硬件層東西：
CPU：快的不得鳥的東西，它總是被人拖后腿，所以有了跟中緩沖。除此還可以考慮下CPU性能提升的技術：流水化、超標量設計、多核心。
主存：除去CPU的高速緩沖，最快的就是主存了。當時數據不能永久保存、價格高是硬傷。
總線：連接了所有設備。又分為多級總線，總線設備之間沖突的解決因此需要總線決策。
I/O設備：各種輸入輸出。進化過程：可編程I/O、I/O中斷、DMA。
局部性原理：分為空間局部性和時間局部性，這是緩存有價值的基礎。
操作系統&進程
操作系統目標：
- 方便：提供方便的交互和資源管理
- 有效：分配資源，更有效的資源利用（內存管理、處理器調度、I/O調度等）
- 擴展能力：不中斷服務增加系統特性的能力
操作系統發展：
串行-->簡單批處理-->多道程序批處理-->分時系統
- 串行：這個時候根本就沒有操作系統概念。
- 簡單批處理：人工組織任務，操作系統負責調度完成一個后繼續下一個，省下了每次人工復位輸入任務的時間。
- 多道程序設計：最計算資源有了時間片劃分，CPU不用因為一個進程I/O阻塞而空轉了。
- 分時系統：計算資源昂貴的背景下，每個用戶的分時。
程序執行的最小單位。進程的組成包括：用戶程序、數據、棧、進程控制塊。
進程狀態切換：
五個狀態如上圖：新建、就緒、運行、阻塞、退出
進程的切換：
將進程切換到硬盤的特定區域，目的是追求更多的進程可以同時運行——因為即便引入了多道程序設計CPU仍然很空閑（其它設備太慢了，特別是I/O），所有越多的進程進入進來，CPU的利用率越高。
進程執行模式
內核模式、用戶模式，模式區分的目的是對進程功能的限制，高風險的CPU指令應該只有操作系統可以執行。
大圖聊完進程聊線程，一個進程可以是多線程的。有了進程之后還要有線程的原因是進程的換入換出、數據交換開銷太大，線程遠遠小于進程的開銷。首先，進 程之間通信需要獲取共享資源鎖，而同一進程內的線程完全享有進程獲得的資源，也因此線程的編寫要特別注意同步問題。第二，進程的創建成本很高，涉及空間分 配、初始化棧、初始化數據等，而線程的創建成本低很多可以包括操作系統創建和進程調用庫自己創建。于是有了兩種不同類型的線程——用戶級別和內核級別。第 三，多道程序設計中線程的換入換出比進程來得快多了，因為不需要保存進程控制塊等一大堆數據嘛（當然要保存線程控制塊，但是成本很低）。最后，銷毀成本 低。
說到線程的兩種類型——用戶、內核。用戶級別的線程是進程調用線程庫創建的，對操作系統是透明的，是進程中通過代碼實現切換的因此因此一旦一個線程引起了 I/O阻塞從操作系統的視角就是進程阻塞，所以要阻塞整個進程；而內核級別的線程是操作系統創建的，所以該阻塞線程的不會阻塞整個進程，當然效率也就沒有 用戶級別的高。
多線程的應用場景：
- 用戶界面和后臺數據運行：用戶界面渲染和后臺數據運算使用不同的線程，沒有喜歡后臺一運算界面就卡死的程序吧。
- 異步計算：不如實時備份，一個線程定時觸發就可以了，沒必要進程定時的檢查是不是該備份了。
- 速度敏感的計算：可以并發計算的、多核處理的，在計算和組織上線程更具優勢。
- 模塊化：模塊化的程序有時候很適合用多線程來設計。
并發性
大圖 多道程序設計帶來了效率的提升也帶來復雜性的提升。進程之間、線程之間的競爭可能會壞菜，有幾種方式導致壞菜——競爭條件、死鎖、饑餓。競爭條件——多個 進程同時訪問一個資源，最后狀態與各個進程的競爭順序敏感；死鎖：多個進程各持有一個資源請求另外的資源，大家互不相讓；饑餓：競爭不過的進程一直得不到 所請求的資源，結果耗著不動了。
有三個經典的并發問題：
- 生產者/消費者：消費者不能消耗還沒來得及生產的資源，生產者不能在容器滿了以后繼續往里面塞。
- 讀者/寫者問題：資源可以被多個進程讀，但是同一時間只能有一個寫者并且寫者與讀者互斥。
- 哲學家就餐問題：這個是一個死鎖的問題，五個哲學家沒用要用兩個叉子吃飯，他們先拿起左手叉子，再拿起右手叉子，然后進餐，然后釋放叉子。桌上一共五個作為五把叉子，如果哲學家同時坐下就會發生死鎖。
互斥：進程間嘗試訪問不可共享的資源時應該是互斥的，這個資源成為臨界資源（critical resource），程序中訪問臨界資源的代碼段成為臨界區。
既然有競爭和并發，就需要提供必要的支持。一種是硬件提供的如CPU特定的指令Compare&Swap、Exchange等，這種方案有一個要 命的問題是效率差需要忙等待，另外還有死鎖和饑餓的問題，軟件級別提供的支持是更好的途徑，包括信號量、監視者、消息傳遞。
關于并發性的支持很好的解決了競爭條件的問題，下一個問題是死鎖。操作系統對死鎖的解決方案包括三個區域：死鎖的預防、死鎖的阻止、死鎖解決。
死鎖的預防目的在于阻止死鎖形成條件中的一個的形成，這里有四個條件：進程互斥、存在持有和等待（資源）、不存在搶占、形成環路。總的來說死鎖的預防存在不可能實現（進程互斥）、條件苛刻、效率地等問題。
死鎖的阻止這是更加實際的途徑，有兩個切入點：1，進程預先聲明需要的資源，只有資源滿足情況下才允許進程啟動——效率低。2，只有不會導致死鎖情況下才分配資源給進程。
死鎖的解決，這個聽起來有點粗暴。前提條件是死鎖可以回滾，一旦發生了死鎖就取消所有進程，回滾到之前的狀態重新競爭，并不斷重復類似的過程——由于競爭的不確定性，最終一定會解決死鎖。
內存管理
這塊大概是最精彩的了。先說內存分區的集中方式——固定大小，等大小的劃分限制了進程大小并且存在明顯浪費（每塊尾部都有剩余），稍微改進一點變成不等大 小的固定劃分一定程度上能加入更大的程序了，但是限制仍然存在效率也非常低——很多內部碎片。動態劃分，來一個進程劃分一塊的方式會產生外部碎片，需要不 斷的進行壓縮才能保證有足夠的連續空間給新進程。分頁，把內存劃分成固定大小的很多小塊需要頁表的支持，但是內存的利用提高了很多，會產生很少的內部碎 片。分段，很分頁的思路一樣都是進程可以劃分到不連續的內存區域中，需要段表支持。段頁結合，每個段內劃分成頁，這樣進程更利于數據共享（分段的便利）， 同時消除了外部碎片（段釋放后無論如何都是若干頁），存在少量的內部碎片。
還有一處漂亮的地方是虛擬內存，由于局部性原理。進程中常用的數據往往只是一部分，其它部分只有在需要時在換入就可以了。在進程運行過程中常駐內存的部分稱為常駐集。虛擬內存作用就是在硬盤上劃分了一塊區域用于進程的換入換出，雖然硬盤也很慢但是比它更慢的是I/O，有了虛擬內存就能把阻塞的進程及時換出，換入就緒進程的部分或者全部，讓更多的進程同時運行提升CPU的利用率。
有了駐留集的感念就該涉及到駐留集的管理了，首先駐留集可以有幾種分配方式：
- 固定分配，局部范圍：每個進程的駐留集是固定不變的，在進程啟動時決定，塊的換入換出總發生在進程內部。
- 動態分配，局部范圍：進程的駐留集是動態調整的，內存塊的交換限制在進程內部（即一個進程的數據被請求時，只能替換自己的塊出去）
- 動態分配，全局范圍：同上，但是在替換策略上可以換成任意進程中的內存塊。
在駐留集固定分配情況下，頁的替換策略包括：先入先出、最近最少使用、始終。
當駐留集動態分配時，頁的替換策略變得更精彩：工作集（很理想，開銷太大）、頁錯誤頻率（定期查看頻率，決定擴充或清理）、采樣間隔可變的工作集（考慮頁錯誤頻率在局部性發生偏移時或膨脹的改進方案，間隔時間是可變的）。
除此以外還有加載側路的問題——多道程序設計導致加入的進程太多時，同樣會導致每個進程的駐留集太小導致頁錯誤率居高的情況。
處理器調度
大圖
處理器調度在單處理器和多處理器的系統中呈現出完全不同的側重，單處理器的情況下系統CPU利用率、響應時間稱為非常重要的關注點，多處理器下由于計算資 源較多響應時間能夠很好的保證，CPU的利用率變得不太重要，如何能有效的減少進程交換、線程依賴導致的阻塞等成為了更關注的點。在單處理器下進程的調度 策略包括：
- 先來先服務：最簡單、最懶的辦法，效果一般，偏向于長進程。
- 輪轉：平均分配每個進程的時間，增加了進程的切換次數，對I/O密集型的進程不公平。
- 最短進程優先：需要估計進程的運行時間，偏向于短進程。
- 最少剩余時間優先：上面策略的搶占版本，有助于提高吞吐率，但是如果短進程不斷到來，長進程可能會饑餓。
- 最高響應比優先：(w+s)/s，w為等待時間，s是服務時間，偏向于短進程，但是當長進程等待時間不斷增加時它的響應比會增大，最后超越短進程。
- 反饋：不需要估計進程運行時間的策略，分多級優先級遞減的隊列，進程運行中會被超時中斷，加入到次一級的隊列中。也就是運行時間越長優先級會越低，同樣可能導致長進程饑餓，因此在等待時間超過一定長度時嘗試把進程重新拿到高優先級隊列來。
多處理器的調度則不太相同，主要關注多線程的調度策略包括：
- 負載分配：任務池和處理器池，始終保持處理器忙碌。
- 組調度：考慮到線程間可能存在依賴的情形，一組相關的線程分配一對一的處理器同時運行。
- 專用處理器分配：組調度的升級版，對進程分配特定的處理器，進程內的所有線程在專用處理器上運行直到進程運行結束才回收處理器。
- 動態分配：進程的線程數可以動態改變，由操作系統和程序共同決定分配和負載。
I/O調度
大圖
I/O功能的邏輯結構
邏輯I/O：邏輯I/O層將I/O設備視為邏輯資源，不關心底層的細節。邏輯I/O代表用戶進程管理的一般I/O功能，允許它們根據設備標識符以及諸如打開、關閉、讀取等操作與設備打交道。
設備I/O：請求的操作和數據（緩沖的數據、記錄等）被轉換成適當的I/O指令序列、通道命令和控制器指令。可以使用緩存技術以提高使用率。
調度和控制：關于I/O操作的排隊、調度和控制發生在這一層，可以在這一次處理中斷，收集和報告I/O狀態。這一層是與I/O設備真正打交道的軟件層。
I/O的慢是出了名的，所以更需要緩沖，需要指出的是緩存是一種技術旨在平緩I/O請求峰值的，當進程需求的I/O平均值大于I/O傳輸速度是再多的緩沖也不能解決問題。
- 單緩沖：系統在發送I/O指令后給I/O設備分配一塊位于主存中的緩沖區，傳輸數據被放在緩沖區中，當傳輸完成時立即嘗試讀取下一塊。根據局部性原理有理由期望下一塊被讀取，這種機制稱為超前讀。
- 雙緩沖：單緩沖時I/O設備必須等待讀 取緩沖區中數據被完全讀出才能再次寫入，雙緩沖設置兩塊緩存區域以平滑這種趨勢。設C為進程處理塊的時間，T位讀取塊的時間，我們可以粗略估計塊的執行時 間位max（C，T），當C>=T是進程將不需要等待I/O，當C
- 循環緩沖：當爆發性的執行大量的I/O操作時，則僅有雙緩沖就不夠了，這種情況下使用多于兩個緩沖的方案來緩解，這種緩沖區域自身被當成循環區域使用。
- 先進先出：先來的請求先服務，由于數據的請求式隨機的，會導致較高的尋址時間，效率差。
- 優先級：優先級是高優先級的請求先服務，一般是為了滿足操作系統的特定目的，并沒有改善磁盤性能的能力。
- 后進先出（LIFO）：令人驚訝的是這 種選取最近請求的策略有許多優點。把設備資源提供給最近（使用系統）的用戶時會導致磁頭臂在一個順序文件中移動時移動的很少，甚至不移動。利用這種局部性 原理可以提高吞吐量減少隊列長度，只要一個作業積極的使用磁盤它就能盡快得到處理。
- 最短服務時間優先（SSTF）：總是選擇磁頭臂移動最少的請求響應，對于移動距離相等的請求可以隨機移動向一邊。同樣如果一個進程大量的請求臨近的數據會導致其它請求饑餓。
- SCAN：SCAN要求磁頭臂向一個方 向移動，移動過程中響應在當前磁道的請求。當磁頭臂到達最外（內）層磁道時，再反向掃描。這種算法并沒有很好的利用局部性原理（對最近橫跨過的區域不公 平，不如SSTF和LIFO好），由于兩側的數據被快速的掃描了兩次因此它偏向于外圍數據（局部性原理）。
- C-SCAN：限定在一個方向掃描，當達到最后一個磁道時，磁頭臂返回到相反方向的磁道末端重新開始掃描。
- N-step-SCAN和FSCAN： 為了克服進程的粘滯性，在SCAN和C-SCAN中一個或多個進程對一個磁道有較高的訪問速度時可能會壟斷這個磁道一段時間。N-step-SCAN設置 若干個N個請求的隊列，每次掃描只響應一個隊列里的請求，當開始掃描時新的請求需要加入到下一個隊列中。
除了好的調度策略，另一個減少開銷的辦法是在主存中建立硬盤的高速緩沖，進行預讀。高速緩沖的替換策略包括：
- LRU：最少訪問，將緩沖區設置為一個棧，當一個塊被訪問后加入到棧中，如果再次得當訪問則把該塊從當前位置移動到棧頂，隨著塊的加入那些不被訪問的將會擠出棧中。
- LFU：最小頻率訪問，對緩存中的塊增加計數特性，每次被訪問到時計數加1。當訪問輔存時，把計數最小的塊移除，加入最近的塊。由于局部性的問題，一個塊可能短時間內多次訪問使得計次很高，但是這之后并不意味著還會再次訪問它，所以LFU并不是一個好的算法。
- 基于頻率的替換算法：克服LFU的確定，在LRU的棧模型中劃分出位于棧頂的若干幀為新區，當塊位于新區是重復訪問不增加訪問次數。
文件管理
大圖
文件結構：
- 域（Field）：基本的數據單元，一個域包含一個值，如雇員名字、日期等。
- 記錄（Record）：一組相關域的集合，可以看做應用程序的一個單元。
- 文件（File）：一組相關記錄的集合，它被用戶或應用程序看做一個實體，并可以通過名字訪問。
- 數據庫（DB）：一組相關數據的集合，它的本質特征是數據之間存在著明確的關系，可供不同的應用程序使用。
- 堆：最簡單的文件系統。數據按它們到達的順序被組織，通過特定的分隔符或特定的域指明。每個域應該是自描述的，數據之間不一定存在聯系或相同的格式。當數據在處理器采集并存儲時或者當數據難以存儲時會用到堆。只能窮舉搜索，對大多數應用都不適用。
- 順序文件：文件具有固定的格式，所有的記錄都有相同的格式，具有相同數目、長度固定的域按照順序組成。每條記錄第一個域稱為關鍵域，唯一標識了這條記錄。交互的表現較差，需要順序的搜索。一種情況下順序文件按照順序存儲在磁盤上，在發生文件修改時需要移動數據，可能的處理方式是把數據存在臨時堆上，定期的將數據批量寫回順序文件。另一種情況文件可能采用鏈式存儲，該方法帶來一些方便，但是是以額外的處理和開銷為代價的。
- 索引順序文件：彌補了順序文件檢索的問題。檢索文件可以是簡單的順序文件，每條記錄包括兩個值一個關鍵域和指向文件的指針。簡單的檢索可以是一級的，也可以由多級檢索。查找文件時找到相等的域或者關鍵域值之前最大的域。
- 索引文件：順序文件和索引順序文件只能是順序檢索或對關鍵域檢索，索引文件對感興趣的域提供了索引，索引文件本身可以是順序的。索引文件分為完全索引和部分索引，差別在于被索引的域是全部域還僅僅是感興趣的域。索引文件一般只提供索引訪問的方式，不再支持順序訪問，因此記錄的組織也不必是順序的，應用程序只能通過指針訪問。
- 直接文件或散列文件：直接文件或散列文件開發直接訪問磁盤中任何一個地址一致的塊的能力，要求每條記錄中都有一個關鍵域，但這里不存在順序的概念。
二級存儲管理
文件分配
預分配：文件請求時聲明需要的空間，一次性分配。
動態分配：根據文件的增長每次分配一定的空間，或者一塊。
分配方法：
- 連續分配：始終給文件分配連續的空間。這種分配方式對于順序文件非常高效，并且可以簡單的檢索到需要的文件塊。但是會產生外部碎片，并且需要實時運行壓縮程序以消除外部碎片。
- 鏈式分配：文件不需要順序保存，每塊尾部通過指針指向下一塊數據，文件分配表中同樣只要保存一個表項。鏈式分配的一個后果是局部性不再被利用，如果要順序的讀取一個文件時需要一連串訪問磁盤的不同部分，這對系統的影響很嚴重。一些系統周期性的的對文件進行合并。
- 索引分配：每個文件在文件分配表中有一個一級索引，分配給文件的每個分區在索引中都有一個表項，典型的文件索引在物理上并不保存在文件分配表上，而是保存在獨立的一個塊上，文件分配表中該文件索引指向這個塊。可以消除外部碎片，按大小可變的分區分配可以提高局部性，任何情況下（大小可變分區、按塊保存）都需要不時的對文件進行合并。使用大小可變的分區情況下合并可以減少文件索引。索引分配支持順序和直接讀取數據，是最普遍的一種文件分配形式。
- 位表：每塊占用一位，如果被占用了用1表示否則用0，占用的空間很小，并且需要在主存中，需要順序的檢索空閑空間，當剩余空閑空間很小時效率非常低。
- 鏈式空閑區：幾乎不需要保存空間，每個空閑塊直接通過指針連成鏈狀，尋找連續空間的效率比較低，無法利用局部性。
- 索引：通過索引指明空閑的區域和長度，在大小可變的分配下很有效。
- 空閑塊列表：最常用的方法。通過棧保存了每塊空余區域的地址，由于可以部分加載在主存中所以有很高的效率。
</ul>
空閑空間管理