快速hodl，操作系統精華摘要

在實踐的道路上走的太遠，就需要回頭看一下理論。操作系統，可以說是基礎知識中的重中之重。

它不像汽車的發動機一樣，加油就可以跑。相反，操作系統並不是一個精密的、固定的儀器，它脆弱、多變，在不同的場景中充滿了不確定性。

調度永遠是操作系統的核心，包括進程調度、內存調度等。而I/O的調度是設計最困難的部分。

在整個的操作系統中，每個部件爲了高效的完成工作，大量使用了緩存、緩衝、批量、對齊等手段。當然，核心還是數據結構。

在實際的落地中，操作系統也並不是枯燥無味的學術派。相反，它的某些關鍵部件，經過了嚴格的實踐和多角度的評測，最終，我們所使用的操作系統，只是在整體上達到了比較好的狀態，它仍然是大量互斥資源的tradeoff。

瞭解操作系統，可以助力設計效率更高的高併發應用、多線程應用，在高吞吐、穩定性方面也能有更多的思考。

【重要理論】根據局部性原理，當一塊數據被取人高速緩存，以滿足一次存儲器訪問時，很可能緊接着多次訪問的數據是該塊中的其他字節。

進程的兩個基本元素，是程序代碼和代碼相關的數據集，而進程控制快包含了充分的信息，可以根據這些信息中斷和恢復進程的執行，就好像進程未被中斷過那樣。

進程的5種狀態：運行態、就緒態、阻塞/等待、新建態、退出態。另外，還有一個掛起的概念。進程的掛起，一般是交換（SWAP）的需要，在大內存容量的今天，處於這種狀態的進程很少。掛起的進程又可能處於阻塞狀態，也有可能處於就緒狀態。

上面提到程序的基本元素，實際上，所有處理器設計，都包含一個或者一組稱爲程序狀態字（PSW）的寄存器，操作系統設計要面對這些寄存器進行編程。舉個例子，PSW通過狀態位，就可以控制程序是運行在內核模式還是用戶模式。

進程切換需要依靠中斷。中斷前，需要保存進程控制塊部分，包括程序計數器、其他處理器寄存器和棧信息。操作系統如在用戶進程內運行，則發生中斷、陷阱或者系統調用的時候，處理器處於內核模式，控制權轉交給操作系統，需要保存模式上細文並切換模式，再切換到一個操作系統例程，但此時，仍然是在當前用戶進程內繼續執行，不需要切換進程，只是在同一個進程內切換模式。

在UNIX中，只有在進程準備從內核模式轉換到用戶模式的時候才能發生搶佔，所以UNIX並不適用於實時處理。

比起進程來，我們通常將分派的單位稱爲線程或者輕量級進程（LWP），而將擁有資源所有權的單位稱爲進程（process）或任務（task）。

進程中的所有線程共享該進程的狀態和資源，所有線程都駐留在同一塊地址空間中，並可以訪問相同的數據，所以切換開銷很小。

Linux提供一種不區分進程和線程的解決方案，這種解決方案使用一種類似Solaris輕量級進程的方法，將用戶級線程映射到內核級別的進程，所以它們是一回事。Linux甚至都沒有爲線程定義專門的數據結構。pthread庫（POSIX thread），根本就不屬於內核。

雖然屬於同一個進程組的克隆進程共享同一內存空間，但不能共享同一個用戶棧。所以clone()調用會爲每個進程創建獨立的棧空間。

基於這種特性，Linux的命名空間可以對這些數據結構進行隔離，形成輕量級虛擬化的基礎。

併發是所有問題的基礎，也是操作系統設計的基礎。對於併發來說，支持併發進程的基本需求是加強互斥能力。有三種互斥方式：信號量、管程和消息傳遞。

互斥軟件通常會建設在哪吃訪問級別實現基本的互斥。spin waiting，也就是自旋方式獲取控制權的方式（CAS），實際上是一種協同程序（coroutine）。爲了提高效率，CAS會在硬件級別實現，也就是XCHG指令。自旋鎖很容易實現，但又一個缺點，即鎖外面的線程會以忙等待的方式繼續執行。這裡會涉及到兩個非常著名的互斥算法：Dekker和Peterson。

互斥最好的例子就是生產者還消費者問題，在語言層面比在操作系統層面更容易理解。除了互斥（mutual exclusion），競爭進程還面臨死鎖（deadlock）和飢餓（starvation）的問題。這些不僅在操作系統，在語言級別也是大問題。

信號量是用於在進程間傳遞信號的一個整數值。如果只有0和1兩個值，則它就變成了二元信號量。另外，還有一個互斥量（mutex）的概念，也是0和1，但它與二元信號量的區別是，爲互斥量加鎖的進程和解鎖的進程，必須是同一個進程---解鈴還需繫鈴人。

然後再提到管程。管程是由一個或者多個進程、一個初始化序列和局部數據組成的軟件模塊。Java的wait、notify，或者Contidion的wait和signal等，都是這樣的實現。

死鎖產生的條件，包括：互斥、佔有且等待、不可搶佔、循環等待等。

與併發管理中的其他問題不同，思索問題並沒有有效的通用解決方案。這是因爲死鎖發生的原因，通常隱藏在複雜的程序邏輯中，檢測起來非常困難。處理可重用資源死鎖的一個策略是，給系統設計施加關於資源請求順序的約束。

在資源固定，請求也可知的情況下，可使用資源分配拒絕策略，也就是傳說中的銀行家算法（banker algorithm）。通過Resource和Available向量、Claim和Allocation矩陣，來判斷接下來的操作是否會造成死鎖。

死鎖方面的問題有點多，包括常考的哲學家就餐問題。其實，基於上面的信號量和管程，都能夠實現。

內存管理是操作系統中最複雜的部分。它包含重定位、保護、共享、邏輯組織和物理組織等內容。

其中，內存保護需求必須有處理器（硬件）而非操作系統（軟件）來滿足，因爲操作系統不能預測程序可能產生的所有內存訪問。內存的分段有助於實現保護機制和共享機制。

進程內的所有內存都是基於邏輯地址，這些邏輯地址會在運行時動態的轉換爲物理地址。簡單的映射方案會導致內存訪問時間加倍。爲克服這個問題，大多數虛擬內存方案都爲頁表項使用了一個特殊的高速緩存，通常稱爲轉換監測緩衝區（TLB）。

虛擬地址轉換爲實際地址時，需要訪問頁表項，而頁表項可能在TLB中，也可能在內存或者磁盤中，而被訪問的字可能在高速緩存中、內存中或者磁盤中。所以，一次內存訪問可能產生兩次缺頁中斷：第一次讀取所需要的頁表部分，第二次讀取進程頁。

一個進程可以劃分爲許多塊（段和頁），這些快不需要連續的位於內存中。在使用分頁技術時，每個進程在內存中浪費的空間，僅僅是進程最後一頁的一小部分形成的碎片。沒有任何外部碎片。

其中，進程執行的任何時候，都在內存的部分稱爲進程的常駐集（resident set）。處理器需要訪問一個不在內存中的邏輯地址時，會產生一箇中斷，這表明出現了內存訪問故障。操作系統會把被中斷的進程置於阻塞狀態。要繼續執行這個進程，操作系統必須把包含引發故障的邏輯地址的進程塊讀入內存。

使用磁盤來模擬內存，叫做虛擬內存（virtual memory）。虛存支持更有效的系統併發度，並能接觸用戶與內存之間沒有必要的緊密約束。但是，虛存輝導致一種稱爲系統抖動（thrashing）的情況：處理器大部分時間都用於交換塊，而非執行指令。

Linux使用夥伴系統做內存分配。它將根據內存請求的大小動態的把內存的某一塊，一分爲2，直到找到合適的大小。用完之後，還會判斷相近的內容，再來一次合併。

早期的UNIX實現中，不提供虛存的原因是，系統運行的處理器不支持分頁或者分段。若沒有對地址轉換和其他基本功能的硬件支持，則這些技術都無法實際使用。

內存不夠時，要交換到磁盤，所以會涉及到置換策略，在數據庫環境中問題尤其突出。所有策略的目標，都是移出最近不可能訪問的頁。

但是，LRU在內存管理級別可能不那麼現實，因爲它在內核級別比較難以實現。一種實現方式是給每一個頁增加一個最後一次訪問的時間戳，並在每次訪問的時候更新這個時間戳。但即使有支持這種方案的硬件，開銷仍然非常大。另一種方法是維護一個關於訪問頁的棧，但開銷同樣很大。

FIFO雖然傻，但它是一種實現起來最簡單的頁面置換策略。

在Linux中，有後臺進程會週期性的掃描全局頁池，而當它在內存的所有頁間循環時，將掃描的每一頁的age變量減1。內核進程kswapd在後臺週期性的執行各個區域的內存回收，它掃描那些與系統頁框對應的頁表項。

Linux的內核也會產生非常非常小的內存小塊，爲了適應它們，Linu在分配頁的時候使用了SLAB分配方案。

處理器調度的目的，以滿足系統目標（如響應時間、吞吐率、處理器效率）的方式，把進程分配到一個或者多個處理器上執行。從用戶角度看，響應時間是系統中最重要的一個特性；從系統的角度來看，吞吐量或者處理器利用率是最重要的。

進程調度根據生命週期，分爲長程調度、中程調度、短程調度。長程調度指的是進程的心間和銷燬，中程調度指的是進行的掛起，而我們常說的調度，指的是短程調度。

調度算法要關注系統交互的響應時間，還有吞吐量，這和服務接口的指標是一致的。常用的調度算法是時間片（time slicing），因爲每個進程在被搶佔之前都會給定一片時間。注意，當一個時間片比運行時間最長的進程還要長的時候，輪轉法就會退化成FCFS。

CPU調度的算法大多數是通過實驗得來的，在多核環境下，簡單的FCFS效率並不低，已經足夠了。在多核環境下，操作系統必須保證多個處理器不會選擇同一個進程，進程也不會從隊列中丟失，因此必須採用某些技術來解決和同步對資源的競爭需求。

研究證明，多處理器系統中的時間分配問題，更加類似於單處理器中的存儲器分配問題，而非單處理器中的調度問題。在這些理論基礎上，一個類似於虛存中的工作集的術語--活動工作集（activity working set）被提了出來。

Linux在2.6採用了一個全新的優先級調度程序，稱爲O(1)調度。這個程序的設計原則是，不管系統的負載和處理器的數量如何變化，選擇合適的任務並執行的時刻，都是恆定的。但事實證明，它太笨重，算法太複雜。

從2.6.23開始，Linux開發了完全公平調度器（CFS），CFS爲每個任務維護一個虛擬的運行時間。一個任務的虛擬運行時間越短（即任務被允許訪問處理器的時間越短），代表它對處理器的需求越強。

這個算法，到現在仍在運行着。

3.4.5.6.7.