計算機結構

現代計算機模型是基於-「馮諾依曼計算機模型」

計算機在運行時，先從內存中取出第一條指令，通過控制器的解碼，按指令的要求，從存儲器中取出數據進行指定的運算和邏輯操作等加工，然後再按地址把結果送到內存中去，接下來，再取出第二條指令，在控制器的指揮下完成規定操作，依此進行下去。直至遇到停止指令

程序與數據一樣存貯，按程序編排的順序，一步一步地取出指令，自動地完成指令規定的操作是計算機最基本的工作模型

「計算機五大核心組成部分」

控制器：是整個計算機的中樞神經，其功能是對程序規定的控制信息進行解釋，根據其要求進行控制，調度程序、數據、地址，協調計算機各部分工作及內存與外設的訪問等。

運算器：運算器的功能是對數據進行各種算術運算和邏輯運算，即對數據進行加工處理。

存儲器：存儲器的功能是存儲程序、數據和各種信號、命令等信息，並在需要時提供這些信息。

輸入：輸入設備是計算機的重要組成部分，輸入設備與輸出設備合你為外部設備，簡稱外設，輸入設備的作用是將程序、原始數據、文字、字元、控制命令或現場採集的數據等信息輸入到計算機。

常見的輸入設備有鍵盤、滑鼠器、光電輸入機、磁帶機、磁碟機、光碟機等。

輸出：輸出設備與輸入設備同樣是計算機的重要組成部分，它把外算機的中間結果或最後結果、機內的各種數據符號及文字或各種控制信號等信息輸出出來，微機常用的輸出設備有顯示終端CRT、印表機、激光印字機、繪圖儀及磁帶、光碟機等。

「計算機結構分成以下 5 個部分：」

輸入設備；輸出設備；內存；中央處理器；匯流排。

內存

在馮諾依曼模型中，程序和數據被存儲在一個被稱作內存的線性排列存儲區域。

存儲的數據單位是一個二進位位，英文是 bit，最小的存儲單位叫作位元組，也就是 8 位，英文是 byte，每一個位元組都對應一個內存地址。

內存地址由 0 開始編號，比如第 1 個地址是 0，第 2 個地址是 1， 然後自增排列，最後一個地址是內存中的位元組數減 1。

我們通常說的內存都是隨機存取器，也就是讀取任何一個地址數據的速度是一樣的，寫入任何一個地址數據的速度也是一樣的。

CPU

馮諾依曼模型中 CPU 負責控制和計算，為了方便計算較大的數值，CPU 每次可以計算多個位元組的數據。

• 如果 CPU 每次可以計算 4 個 byte，那麼我們稱作 32 位 CPU；
• 如果 CPU 每次可以計算 8 個 byte，那麼我們稱作 64 位 CPU。

這裡的 32 和 64，稱作 CPU 的位寬。

「為什麼 CPU 要這樣設計呢？」

因為一個 byte 最大的表示範圍就是 0~255。

比如要計算 20000*50，就超出了byte 最大的表示範圍了。

因此，CPU 需要支持多個 byte 一起計算，當然，CPU 位數越大，可以計算的數值就越大，但是在現實生活中不一定需要計算這麼大的數值，比如說 32 位 CPU 能計算的最大整數是 4294967295，這已經非常大了。

「控制單元和邏輯運算單元」

CPU 中有一個控制單元專門負責控制 CPU 工作；還有邏輯運算單元專門負責計算。

「寄存器」

CPU 要進行計算，比如最簡單的加和兩個數字時，因為 CPU 離內存太遠，所以需要一種離自己近的存儲來存儲將要被計算的數字。

這種存儲就是寄存器，寄存器就在 CPU 里，控制單元和邏輯運算單元非常近，因此速度很快。

常見的寄存器種類：

• 通用寄存器，用來存放需要進行運算的數據，比如需要進行加和運算的兩個數據。
• 程序計數器，用來存儲 CPU 要執行下一條指令所在的內存地址，注意不是存儲了下一條要執行的指令，此時指令還在內存中，程序計數器只是存儲了下一條指令的地址。
• 指令寄存器，用來存放程序計數器指向的指令，也就是指令本身，指令被執行完成之前，指令都存儲在這裡。

多級緩存

現代CPU為了提升執行效率，減少CPU與內存的交互(交互影響CPU效率)，一般在CPU上集成了多級緩存架構

「CPU緩存」即高速緩衝存儲器，是位於CPU與主內存間的一種容量較小但速度很高的存儲器

由於CPU的速度遠高於主內存，CPU直接從內存中存取數據要等待一定時間周期，Cache中保存著CPU剛用過或循環使用的一部分數據，當CPU再次使用該部分數據時可從Cache中直接調用，減少CPU的等待時間，提高了系統的效率，具體包括以下幾種：

「L1-Cache」

L1- 緩存在 CPU 中，相比寄存器，雖然它的位置距離 CPU 核心更遠，但造價更低，通常 L1-Cache 大小在幾十 Kb 到幾百 Kb 不等，讀寫速度在 2~4 個 CPU 時鐘周期。

「L2-Cache」

L2- 緩存也在 CPU 中，位置比 L1- 緩存距離 CPU 核心更遠，它的大小比 L1-Cache 更大，具體大小要看 CPU 型號，有 2M 的，也有更小或者更大的，速度在 10~20 個 CPU 周期。

「L3-Cache」

L3- 緩存同樣在 CPU 中，位置比 L2- 緩存距離 CPU 核心更遠，大小通常比 L2-Cache 更大，讀寫速度在 20~60 個 CPU 周期。

L3 緩存大小也是看型號的，比如 i9 CPU 有 512KB L1 Cache；有 2MB L2 Cache； 有16MB L3 Cache。

當 CPU 需要內存中某個數據的時候，如果寄存器中有這個數據，我們可以直接使用；如果寄存器中沒有這個數據，我們就要先查詢 L1 緩存；L1 中沒有，再查詢 L2 緩存；L2 中沒有再查詢 L3 緩存；L3 中沒有，再去內存中拿。

「總結：」

存儲器存儲空間大小：內存>L3>L2>L1>寄存器；

存儲器速度快慢排序：寄存器>L1>L2>L3>內存；

安全等級

「CPU運行安全等級」

CPU有4個運行級別，分別為：

• ring0，ring1，ring2，ring3

ring0隻給操作系統用，ring3誰都能用。

ring0是指CPU的運行級別，是最高級別，ring1次之，ring2更次之……

系統（內核）的代碼運行在最高運行級別ring0上，可以使用特權指令，控制中斷、修改頁表、訪問設備等等。

應用程序的代碼運行在最低運行級別上ring3上，不能做受控操作。

如果要做，比如要訪問磁碟，寫文件，那就要通過執行系統調用（函數），執行系統調用的時候，CPU的運行級別會發生從ring3到ring0的切換，並跳轉到系統調用對應的內核代碼位置執行，這樣內核就為你完成了設備訪問，完成之後再從ring0返回ring3。

這個過程也稱作用戶態和內核態的切換。

局部性原理

在CPU訪問存儲設備時，無論是存取數據抑或存取指令，都趨於聚集在一片連續的區域中，這就被稱為局部性原理

「時間局部性（Temporal Locality）：」

如果一個信息項正在被訪問，那麼在近期它很可能還會被再次訪問。

比如循環、遞歸、方法的反覆調用等。

「空間局部性（Spatial Locality）：」

如果一個存儲器的位置被引用，那麼將來他附近的位置也會被引用。

比如順序執行的代碼、連續創建的兩個對象、數組等。

程序的執行過程

程序實際上是一條一條指令，所以程序的運行過程就是把每一條指令一步一步的執行起來，負責執行指令的就是 CPU 了。

「那 CPU 執行程序的過程如下：」

• 第一步，CPU 讀取程序計數器的值，這個值是指令的內存地址，然後 CPU 的控制單元操作地址匯流排指定需要訪問的內存地址，接著通知內存設備準備數據，數據準備好後通過數據匯流排將指令數據傳給 CPU，CPU 收到內存傳來的數據後，將這個指令數據存入到指令寄存器。
• 第二步，CPU 分析指令寄存器中的指令，確定指令的類型和參數，如果是計算類型的指令，就把指令交給邏輯運算單元運算；如果是存儲類型的指令，則交由控制單元執行；
• 第三步，CPU 執行完指令後，程序計數器的值自增，表示指向下一條指令。這個自增的大小，由 CPU 的位寬決定，比如 32 位的 CPU，指令是 4 個位元組，需要 4 個內存地址存放，因此程序計數器的值會自增 4；

簡單總結一下就是，一個程序執行的時候，CPU 會根據程序計數器里的內存地址，從內存裡面把需要執行的指令讀取到指令寄存器裡面執行，然後根據指令長度自增，開始順序讀取下一條指令。

CPU 從程序計數器讀取指令、到執行、再到下一條指令，這個過程會不斷循環，直到程序執行結束，這個不斷循環的過程被稱為 「CPU 的指令周期」。

匯流排

CPU 和內存以及其他設備之間，也需要通信，因此我們用一種特殊的設備進行控制，就是匯流排。

• 地址匯流排，用於指定 CPU 將要操作的內存地址；
• 數據匯流排，用於讀寫內存的數據；
• 控制匯流排，用於發送和接收信號，比如中斷、設備複位等信號，CPU 收到信號後自然進行響應，這時也需要控制匯流排；

當 CPU 要讀寫內存數據的時候，一般需要通過兩個匯流排：

• 首先要通過地址匯流排來指定內存的地址；
• 再通過數據匯流排來傳輸數據；

輸入、輸出設備

輸入設備向計算機輸入數據，計算機經過計算，將結果通過輸出設備向外界傳達。

如果輸入設備、輸出設備想要和 CPU 進行交互，比如說用戶按鍵需要 CPU 響應，這時候就需要用到控制匯流排。

基礎知識

中斷

「中斷的類型」

• 按照中斷的觸發方分成同步中斷和非同步中斷；
• 根據中斷是否強制觸發分成可屏蔽中斷和不可屏蔽中斷。

中斷可以由 CPU 指令直接觸發，這種主動觸發的中斷，叫作同步中斷。

❝

同步中斷有幾種情況。

❞

• 比如系統調用，需要從用戶態切換內核態，這種情況需要程序觸發一個中斷，叫作陷阱（Trap），中斷觸發後需要繼續執行系統調用。
• 還有一種同步中斷情況是錯誤（Fault），通常是因為檢測到某種錯誤，需要觸發一個中斷，中斷響應結束後，會重新執行觸發錯誤的地方，比如後面我們要學習的缺頁中斷。
• 最後還有一種情況是程序的異常，這種情況和 Trap 類似，用於實現程序拋出的異常。

另一部分中斷不是由 CPU 直接觸發，是因為需要響應外部的通知，比如響應鍵盤、滑鼠等設備而觸發的中斷，這種中斷我們稱為非同步中斷。

CPU 通常都支持設置一個中斷屏蔽位（一個寄存器），設置為 1 之後 CPU 暫時就不再響應中斷。

對於鍵盤滑鼠輸入，比如陷阱、錯誤、異常等情況，會被臨時屏蔽。

但是對於一些特別重要的中斷，比如 CPU 故障導致的掉電中斷，還是會正常觸發。

「可以被屏蔽的中斷我們稱為可屏蔽中斷，多數中斷都是可屏蔽中斷。」

內核態和用戶態

「什麼是用戶態和內核態」

Kernel 運行在超級許可權模式下，所以擁有很高的許可權。

按照許可權管理的原則，多數應用程序應該運行在最小許可權下。

因此，很多操作系統，將內存分成了兩個區域：

• 內核空間（Kernal Space），這個空間只有內核程序可以訪問；
• 用戶空間（User Space），這部分內存專門給應用程序使用。

用戶空間中的代碼被限制了只能使用一個局部的內存空間，我們說這些程序在用戶態 執行。

內核空間中的代碼可以訪問所有內存，我們稱這些程序在內核態 執行。

❝

按照級別分：

❞

當程序運行在0級特權級上時，就可以稱之為運行在內核態

當程序運行在3級特權級上時，就可以稱之為運行在用戶態

運行在用戶態下的程序不能直接訪問操作系統內核數據結構和程序。

當我們在系統中執行一個程序時，大部分時間是運行在用戶態下的，在其需要操作系統幫助完成某些它沒有權力和能力完成的工作時就會切換到內核態（比如操作硬體）

「這兩種狀態的主要差別」

處於用戶態執行時，進程所能訪問的內存空間和對象受到限制，其所處於佔有的處理器是可被搶佔的

處於內核態執行時，則能訪問所有的內存空間和對象，且所佔有的處理器是不允許被搶佔的。

「為什麼要有用戶態和內核態」

由於需要限制不同的程序之間的訪問能力，防止他們獲取別的程序的內存數據，或者獲取外圍設備的數據，並發送到網路

「用戶態與內核態的切換」

所有用戶程序都是運行在用戶態的，但是有時候程序確實需要做一些內核態的事情， 例如從硬碟讀取數據，或者從鍵盤獲取輸入等，而唯一可以做這些事情的就是操作系統，所以此時程序就需要先操作系統請求以程序的名義來執行這些操作

「用戶態和內核態的轉換」

❝

系統調用

❞

用戶態進程通過系統調用申請使用操作系統提供的服務程序完成工作，比如fork()實際上就是執行了一個創建新進程的系統調用

而系統調用的機制其核心還是使用了操作系統為用戶特別開放的一個中斷來實現，例如Linux的int 80h中斷

「舉例：」

如上圖所示：內核程序執行在內核態（Kernal Mode），用戶程序執行在用戶態（User Mode）。

當發生系統調用時，用戶態的程序發起系統調用，因為系統調用中牽扯特權指令，用戶態程序許可權不足，因此會中斷執行，也就是 Trap（Trap 是一種中斷）。

發生中斷後，當前 CPU 執行的程序會中斷，跳轉到中斷處理程序，內核程序開始執行，也就是開始處理系統調用。

內核處理完成後，主動觸發 Trap，這樣會再次發生中斷，切換回用戶態工作。

❝

異常

❞

當CPU在執行運行在用戶態下的程序時，發生了某些事先不可知的異常，這時會觸發由當前運行進程切換到處理此異常的內核相關程序中，也就轉到了內核態，比如缺頁異常

❝

外圍設備的中斷

❞

當外圍設備完成用戶請求的操作後，會向CPU發出相應的中斷信號，這時CPU會暫停執行下一條即將要執行的指令轉而去執行與中斷信號對應的處理程序，如果先前執行的指令是用戶態下的程序，那麼這個轉換的過程自然也就發生了由用戶態到內核態的切換

比如硬碟讀寫操作完成，系統會切換到硬碟讀寫的中斷處理程序中執行後續操作等

線程

線程：系統分配處理器時間資源的基本單元，是程序執行的最小單位

線程可以看做輕量級的進程，共享內存空間，每個線程都有自己獨立的運行棧和程序計數器，線程之間切換的開銷小。

在同一個進程（程序）中有多個線程同時執行（通過CPU調度，在每個時間片中只有一個線程執行）

進程可以通過 API 創建用戶態的線程，也可以通過系統調用創建內核態的線程。

用戶態線程

用戶態線程也稱作用戶級線程，操作系統內核並不知道它的存在，它完全是在用戶空間中創建。

用戶級線程有很多優勢，比如：

• 管理開銷小：創建、銷毀不需要系統調用。
• 切換成本低：用戶空間程序可以自己維護，不需要走操作系統調度。

但是這種線程也有很多的缺點：

• 與內核協作成本高：比如這種線程完全是用戶空間程序在管理，當它進行 I/O 的時候，無法利用到內核的優勢，需要頻繁進行用戶態到內核態的切換。
• 線程間協作成本高：設想兩個線程需要通信，通信需要 I/O，I/O 需要系統調用，因此用戶態線程需要額外的系統調用成本。
• 無法利用多核優勢：比如操作系統調度的仍然是這個線程所屬的進程，所以無論每次一個進程有多少用戶態的線程，都只能並發執行一個線程，因此一個進程的多個線程無法利用多核的優勢。

操作系統無法針對線程調度進行優化：當一個進程的一個用戶態線程阻塞（Block）了，操作系統無法及時發現和處理阻塞問題，它不會更換執行其他線程，從而造成資源浪費。

內核態線程

內核態線程也稱作內核級線程（Kernel Level Thread），這種線程執行在內核態，可以通過系統調用創造一個內核級線程。

內核級線程有很多優勢：

• 可以利用多核 CPU 優勢：內核擁有較高許可權，因此可以在多個 CPU 核心上執行內核線程。
• 操作系統級優化：內核中的線程操作 I/O 不需要進行系統調用；一個內核線程阻塞了，可以立即讓另一個執行。

當然內核線程也有一些缺點：

• 創建成本高：創建的時候需要系統調用，也就是切換到內核態。
• 擴展性差：由一個內核程序管理，不可能數量太多。
• 切換成本較高：切換的時候，也同樣存在需要內核操作，需要切換內核態。

「用戶態線程和內核態線程之間的映射關係」

如果有一個用戶態的進程，它下面有多個線程，如果這個進程想要執行下面的某一個線程，應該如何做呢？

❝

這時，比較常見的一種方式，就是將需要執行的程序，讓一個內核線程去執行。

❞

畢竟，內核線程是真正的線程，因為它會分配到 CPU 的執行資源。

如果一個進程所有的線程都要自己調度，相當於在進程的主線程中實現分時演算法調度每一個線程，也就是所有線程都用操作系統分配給主線程的時間片段執行。

❝

這種做法，相當於操作系統調度進程的主線程；進程的主線程進行二級調度，調度自己內部的線程。

❞

這樣操作劣勢非常明顯，比如無法利用多核優勢，每個線程調度分配到的時間較少，而且這種線程在阻塞場景下會直接交出整個進程的執行許可權。

由此可見，用戶態線程創建成本低，問題明顯，不可以利用多核。

內核態線程，創建成本高，可以利用多核，切換速度慢。

因此通常我們會在內核中預先創建一些線程，並反覆利用這些線程。

協程

協程，是一種比線程更加輕量級的存在，協程不是被操作系統內核所管理，而完全是由程序所控制（也就是在用戶態執行）。

這樣帶來的好處就是性能得到了很大的提升，不會像線程切換那樣消耗資源。

「子程序」

或者稱為函數，在所有語言中都是層級調用，比如A調用B，B在執行過程中又調用了C，C執行完畢返回，B執行完畢返回，最後是A執行完畢。

所以子程序調用是通過棧實現的，一個線程就是執行一個子程序。

子程序調用總是一個入口，一次返回，調用順序是明確的。

「協程的特點在於是一個線程執行，那和多線程比，協程有何優勢？」

• 極高的執行效率：因為子程序切換不是線程切換，而是由程序自身控制，因此，沒有線程切換的開銷，和多線程比，線程數量越多，協程的性能優勢就越明顯；
• 不需要多線程的鎖機制：因為只有一個線程，也不存在同時寫變數衝突，在協程中控制共享資源不加鎖，只需要判斷狀態就好了，所以執行效率比多線程高很多。

線程安全

如果你的代碼所在的進程中有多個線程在同時運行，而這些線程可能會同時運行這段代碼。

如果每次運行結果和單線程運行的結果是一樣的，而且其他的變數的值也和預期的是一樣的，就是線程安全的。

進程

在系統中正在運行的一個應用程序；程序一旦運行就是進程；是資源分配的最小單位。

在操作系統中能同時運行多個進程；

開機的時候，磁碟的內核鏡像被導入內存作為一個執行副本，成為內核進程。

進程可以分成「用戶態進程和內核態進程」兩類，用戶態進程通常是應用程序的副本，內核態進程就是內核本身的進程。

如果用戶態進程需要申請資源，比如內存，可以通過系統調用向內核申請。

每個進程都有獨立的內存空間，存放代碼和數據段等，程序之間的切換會有較大的開銷；

「分時和調度」

每個進程在執行時都會獲得操作系統分配的一個時間片段，如果超出這個時間，就會輪到下一個進程（線程）執行。

❝

注意，現代操作系統都是直接調度線程，不會調度進程。

❞

「分配時間片段」

如下圖所示，進程 1 需要 2 個時間片段，進程 2 只有 1 個時間片段，進程 3 需要 3 個時間片段。

因此當進程 1 執行到一半時，會先掛起，然後進程 2 開始執行；進程 2 一次可以執行完，然後進程 3 開始執行，不過進程 3 一次執行不完，在執行了 1 個時間片段後，進程 1 開始執行；就這樣如此周而復始，這個就是分時技術。

創建進程

用戶想要創建一個進程，最直接的方法就是從命令行執行一個程序，或者雙擊打開一個應用，但對於程序員而言，顯然需要更好的設計。

首先，應該有 API 打開應用，比如可以通過函數打開某個應用；

另一方面，如果程序員希望執行完一段代價昂貴的初始化過程後，將當前程序的狀態複製好幾份，變成一個個單獨執行的進程，那麼操作系統提供了 fork 指令。

也就是說，每次 fork 會多創造一個克隆的進程，這個克隆的進程，所有狀態都和原來的進程一樣，但是會有自己的地址空間。

如果要創造 2 個克隆進程，就要 fork 兩次。

❝

那如果我就是想啟動一個新的程序呢？

❞

操作系統提供了啟動新程序的 API。

如果我就是想用一個新進程執行一小段程序，比如說每次服務端收到客戶端的請求時，我都想用一個進程去處理這個請求。

如果是這種情況，建議你不要單獨啟動進程，而是使用線程。

因為進程的創建成本實在太高了，因此不建議用來做這樣的事情：要創建條目、要分配內存，特別是還要在內存中形成一個個段，分成不同的區域。所以通常，我們更傾向於多創建線程。

不同程序語言會自己提供創建線程的 API，比如 Java 有 Thread 類；go 有 go-routine（注意不是協程，是線程）。

進程狀態

「創建狀態」

進程由創建而產生，創建進程是一個非常複雜的過程，一般需要通過多個步驟才能完成：如首先由進程申請一個空白的進程式控制制塊(PCB)，並向PCB中填寫用於控制和管理進程的信息；然後為該進程分配運行時所必須的資源；最後，把該進程轉入就緒狀態並插入到就緒隊列中

「就緒狀態」

這是指進程已經準備好運行的狀態，即進程已分配到除CPU以外所有的必要資源後，只要再獲得CPU，便可立即執行，如果系統中有許多處於就緒狀態的進程，通常將它們按照一定的策略排成一個隊列，該隊列稱為就緒隊列，有執行資格，沒有執行權的進程

「運行狀態」

這裡指進程已經獲取CPU，其進程處於正在執行的狀態。對任何一個時刻而言，在單處理機的系統中，只有一個進程處於執行狀態而在多處理機系統中，有多個進程處於執行狀態，既有執行資格，又有執行權的進程

「阻塞狀態」

這裡是指正在執行的進程由於發生某事件（如I/O請求、申請緩衝區失敗等）暫時無法繼續執行的狀態，即進程執行受到阻塞，此時引起進程調度，操作系統把處理機分配給另外一個就緒的進程，而讓受阻的進程處於暫停的狀態，一般將這個暫停狀態稱為阻塞狀態

「終止狀態」

進程間通信IPC

每個進程各自有不同的用戶地址空間，任何一個進程的全局變數在另一個進程中都看不到，所以進程之間要交換數據必須通過內核，在內核中開闢一塊緩衝區，進程1把數據從用戶空間拷到內核緩衝區，進程2再從內核緩衝區把數據讀走，內核提供的這種機制稱為進程間通信

「管道/匿名管道」

管道是半雙工的，數據只能向一個方向流動；需要雙方通信時，需要建立起兩個管道。

• 只能用於父子進程或者兄弟進程之間(具有親緣關係的進程);
• 單獨構成一種獨立的文件系統：管道對於管道兩端的進程而言，就是一個文件，但它不是普通的文件，它不屬於某種文件系統，而是自立門戶，單獨構成一種文件系統，並且只存在與內存中。
• 數據的讀出和寫入：一個進程向管道中寫的內容被管道另一端的進程讀出，寫入的內容每次都添加在管道緩衝區的末尾，並且每次都是從緩衝區的頭部讀出數據。

「有名管道(FIFO)」

匿名管道，由於沒有名字，只能用於親緣關係的進程間通信。

為了克服這個缺點，提出了有名管道(FIFO)。

有名管道不同於匿名管道之處在於它提供了一個路徑名與之關聯，以有名管道的文件形式存在於文件系統中，這樣，即使與有名管道的創建進程不存在親緣關係的進程，只要可以訪問該路徑，就能夠彼此通過有名管道相互通信，因此，通過有名管道不相關的進程也能交換數據。

「信號」

信號是Linux系統中用於進程間互相通信或者操作的一種機制，信號可以在任何時候發給某一進程，而無需知道該進程的狀態。

如果該進程當前並未處於執行狀態，則該信號就有內核保存起來，知道該進程回復執行並傳遞給它為止。

如果一個信號被進程設置為阻塞，則該信號的傳遞被延遲，直到其阻塞被取消是才被傳遞給進程。

「消息隊列」

消息隊列是存放在內核中的消息鏈表，每個消息隊列由消息隊列標識符表示。

與管道（無名管道：只存在於內存中的文件；命名管道：存在於實際的磁碟介質或者文件系統）不同的是消息隊列存放在內核中，只有在內核重啟(即操作系統重啟)或者顯示地刪除一個消息隊列時，該消息隊列才會被真正的刪除。

另外與管道不同的是，消息隊列在某個進程往一個隊列寫入消息之前，並不需要另外某個進程在該隊列上等待消息的到達

「共享內存」

使得多個進程可以直接讀寫同一塊內存空間，是最快的可用IPC形式，是針對其他通信機制運行效率較低而設計的。

為了在多個進程間交換信息，內核專門留出了一塊內存區，可以由需要訪問的進程將其映射到自己的私有地址空間，進程就可以直接讀寫這一塊內存而不需要進行數據的拷貝，從而大大提高效率。

由於多個進程共享一段內存，因此需要依靠某種同步機制（如信號量）來達到進程間的同步及互斥。

共享內存示意圖：

一旦這樣的內存映射到共享它的進程的地址空間，這些進程間數據傳遞不再涉及到內核，換句話說是進程不再通過執行進入內核的系統調用來傳遞彼此的數據。

「信號量」

信號量是一個計數器，用於多進程對共享數據的訪問，信號量的意圖在於進程間同步。

為了獲得共享資源，進程需要執行下列操作：

1. 創建一個信號量：這要求調用者指定初始值，對於二值信號量來說，它通常是1，也可是0。
2. 等待一個信號量：該操作會測試這個信號量的值，如果小於0，就阻塞，也稱為P操作。
3. 掛出一個信號量：該操作將信號量的值加1，也稱為V操作。

「套接字(Socket)」

套接字是一種通信機制，憑藉這種機制，客戶/伺服器（即要進行通信的進程）系統的開發工作既可以在本地單機上進行，也可以跨網路進行。也就是說它可以讓不在同一台計算機但通過網路連接計算機上的進程進行通信。

信號

信號是進程間通信機制中唯一的非同步通信機制，可以看作是非同步通知，通知接收信號的進程有哪些事情發生了。

也可以簡單理解為信號是某種形式上的軟中斷

可運行kill -l查看Linux支持的信號列表：

kill -l
 1) SIGHUP  2) SIGINT  3) SIGQUIT  4) SIGILL  5) SIGTRAP
 6) SIGABRT  7) SIGBUS  8) SIGFPE  9) SIGKILL 10) SIGUSR1
11) SIGSEGV 12) SIGUSR2 13) SIGPIPE 14) SIGALRM 15) SIGTERM
16) SIGSTKFLT 17) SIGCHLD 18) SIGCONT 19) SIGSTOP 20) SIGTSTP
21) SIGTTIN 22) SIGTTOU 23) SIGURG 24) SIGXCPU 25) SIGXFSZ
26) SIGVTALRM 27) SIGPROF 28) SIGWINCH 29) SIGIO 30) SIGPWR
31) SIGSYS 34) SIGRTMIN 35) SIGRTMIN+1 36) SIGRTMIN+2 37) SIGRTMIN+3
38) SIGRTMIN+4 39) SIGRTMIN+5 40) SIGRTMIN+6 41) SIGRTMIN+7 42) SIGRTMIN+8
43) SIGRTMIN+9 44) SIGRTMIN+10 45) SIGRTMIN+11 46) SIGRTMIN+12 47) SIGRTMIN+13
48) SIGRTMIN+14 49) SIGRTMIN+15 50) SIGRTMAX-14 51) SIGRTMAX-13 52) SIGRTMAX-12
53) SIGRTMAX-11 54) SIGRTMAX-10 55) SIGRTMAX-9 56) SIGRTMAX-8 57) SIGRTMAX-7
58) SIGRTMAX-6 59) SIGRTMAX-5 60) SIGRTMAX-4 61) SIGRTMAX-3 62) SIGRTMAX-2
63) SIGRTMAX-1 64) SIGRTMAX

「幾個常用的信號：」

信號描述SIGHUP當用戶退出終端時，由該終端開啟的所有進程都會接收到這個信號，默認動作為終止進程。SIGINT程序終止(interrupt)信號, 在用戶鍵入INTR字元(通常是Ctrl+C)時發出，用於通知前台進程組終止進程。SIGQUIT和SIGINT類似, 但由QUIT字元(通常是Ctrl+)來控制，進程在因收到SIGQUIT退出時會產生core文件, 在這個意義上類似於一個程序錯誤信號。SIGKILL用來立即結束程序的運行，本信號不能被阻塞、處理和忽略。SIGTERM程序結束(terminate)信號, 與SIGKILL不同的是該信號可以被阻塞和處理。通常用來要求程序自己正常退出。SIGSTOP停止(stopped)進程的執行. 注意它和terminate以及interrupt的區別:該進程還未結束, 只是暫停執行，本信號不能被阻塞, 處理或忽略

進程同步

「臨界區」

通過對多線程的串列化來訪問公共資源或一段代碼，速度快，適合控制數據訪問

優點：保證在某一時刻只有一個線程能訪問數據的簡便辦法

缺點：雖然臨界區同步速度很快，但卻只能用來同步本進程內的線程，而不可用來同步多個進程中的線程

「互斥量」

為協調共同對一個共享資源的單獨訪問而設計的

互斥量跟臨界區很相似，比臨界區複雜，互斥對象只有一個，只有擁有互斥對象的線程才具有訪問資源的許可權

優點：使用互斥不僅僅能夠在同一應用程序不同線程中實現資源的安全共享，而且可以在不同應用程序的線程之間實現對資源的安全共享

「信號量」

為控制一個具有有限數量用戶資源而設計，它允許多個線程在同一時刻訪問同一資源，但是需要限制在同一時刻訪問此資源的最大線程數目，互斥量是信號量的一種特殊情況，當信號量的最大資源數=1就是互斥量了

信號量（Semaphore）是一個整型變數，可以對其執行 down 和 up 操作，也就是常見的 P 和 V 操作

• 「down」 : 如果信號量大於 0 ，執行 -1 操作；如果信號量等於 0，進程睡眠，等待信號量大於 0；
• 「up」 ：對信號量執行 +1 操作，喚醒睡眠的進程讓其完成 down 操作。

down 和 up 操作需要被設計成原語，不可分割，通常的做法是在執行這些操作的時候屏蔽中斷。

如果信號量的取值只能為 0 或者 1，那麼就成為了 「互斥量（Mutex）」 ，0 表示臨界區已經加鎖，1 表示臨界區解鎖。

「事件」

用來通知線程有一些事件已發生，從而啟動後繼任務的開始

優點：事件對象通過通知操作的方式來保持線程的同步，並且可以實現不同進程中的線程同步操作

「管程」

管程有一個重要特性：在一個時刻只能有一個進程使用管程。

進程在無法繼續執行的時候不能一直佔用管程，否則其它進程永遠不能使用管程。

管程引入了 「條件變數」 以及相關的操作：「wait()」 和 「signal()」 來實現同步操作。

對條件變數執行 wait() 操作會導致調用進程阻塞，把管程讓出來給另一個進程持有。

signal() 操作用於喚醒被阻塞的進程。

使用信號量機制實現的生產者消費者問題需要客戶端代碼做很多控制，而管程把控制的代碼獨立出來，不僅不容易出錯，也使得客戶端代碼調用更容易。

上下文切換

對於單核單線程CPU而言，在某一時刻只能執行一條CPU指令。

上下文切換(Context Switch)是一種將CPU資源從一個進程分配給另一個進程的機制。

從用戶角度看，計算機能夠並行運行多個進程，這恰恰是操作系統通過快速上下文切換造成的結果。

「在切換的過程中，操作系統需要先存儲當前進程的狀態(包括內存空間的指針，當前執行完的指令等等)，再讀入下一個進程的狀態，然後執行此進程。」

進程調度演算法

「先來先服務調度演算法」

該演算法既可用於作業調度，也可用於進程調度，當在作業調度中採用該演算法時，每次調度都是從後備作業隊列中選擇一個或多個最先進入該隊列的作業，將它們調入內存，為它們分配資源、創建進程，然後放入就緒隊列

「短作業優先調度演算法」

從後備隊列中選擇一個或若干個估計運行時間最短的作業，將它們調入內存運行

「時間片輪轉法」

每次調度時，把CPU分配給隊首進程，並令其執行一個時間片，時間片的大小從幾ms到幾百ms，當執行的時間片用完時，由一個計時器發出時鐘中斷請求，調度程序便據此信號來停止該進程的執行，並將它送往就緒隊列的末尾

然後，再把處理機分配給就緒隊列中新的隊首進程，同時也讓它執行一個時間片，這樣就可以保證就緒隊列中的所有進程在一給定的時間內均能獲得一時間片的處理機執行時間

「最短剩餘時間優先」

最短作業優先的搶佔式版本，按剩餘運行時間的順序進行調度，當一個新的作業到達時，其整個運行時間與當前進程的剩餘時間作比較。

如果新的進程需要的時間更少，則掛起當前進程，運行新的進程。否則新的進程等待。

「多級反饋隊列調度演算法」：

前面介紹的幾種進程調度的演算法都有一定的局限性，如「短進程優先的調度演算法，僅照顧了短進程而忽略了長進程」，多級反饋隊列調度演算法既能使高優先順序的作業得到響應又能使短作業迅速完成，因而它是目前「被公認的一種較好的進程調度演算法」，UNIX 操作系統採取的便是這種調度演算法。

舉例：

多級隊列，就是多個隊列執行調度，先考慮最簡單的兩級模型

上圖中設計了兩個優先順序不同的隊列，從下到上優先順序上升，上層隊列調度緊急任務，下層隊列調度普通任務。

只要上層隊列有任務，下層隊列就會讓出執行許可權。

低優先順序隊列可以考慮搶佔 + 優先順序隊列的方式實現，這樣每次執行一個時間片段就可以判斷一下高優先順序的隊列中是否有任務。

高優先順序隊列可以考慮用非搶佔（每個任務執行完才執行下一個）+ 優先順序隊列實現，這樣緊急任務優先順序有個區分，如果遇到十萬火急的情況，就可以優先處理這個任務。

上面這個模型雖然解決了任務間的優先順序問題，但是還是沒有解決短任務先行的問題，可以考慮再增加一些隊列，讓級別更多。

比如下圖這個模型：

緊急任務仍然走高優隊列，非搶佔執行。

普通任務先放到優先順序僅次於高優任務的隊列中，並且只分配很小的時間片；如果沒有執行完成，說明任務不是很短，就將任務下調一層。

下面一層，最低優先順序的隊列中時間片很大，長任務就有更大的時間片可以用。

通過這種方式，短任務會在更高優先順序的隊列中執行完成，長任務優先順序會下調，也就類似實現了最短作業優先的問題。

實際操作中，可以有 n 層，一層層把大任務篩選出來，最長的任務，放到最閑的時間去執行，要知道，大部分時間 CPU 不是滿負荷的。

「優先順序調度」

為每個流程分配優先順序，首先執行具有最高優先順序的進程，依此類推，具有相同優先順序的進程以 FCFS 方式執行，可以根據內存要求，時間要求或任何其他資源要求來確定優先順序。

守護進程

守護進程是脫離於終端並且在後台運行的進程，脫離終端是為了避免在執行的過程中的信息在終端上顯示，並且進程也不會被任何終端所產生的終端信息所打斷。

守護進程一般的生命周期是系統啟動到系統停止運行。

Linux系統中有很多的守護進程，最典型的就是我們經常看到的服務進程。

當然，我們也經常會利用守護進程來完成很多的系統或者自動化任務。

孤兒進程

父進程早於子進程退出時候子進程還在運行，子進程會成為孤兒進程，Linux會對孤兒進程的處理，把孤兒進程的父進程設為進程號為1的進程，也就是由init進程來託管，init進程負責子進程退出後的善後清理工作

殭屍進程

子進程執行完畢時發現父進程未退出，會向父進程發送 SIGCHLD 信號，但父進程沒有使用 wait/waitpid 或其他方式處理 SIGCHLD 信號來回收子進程，子進程變成為了對系統有害的殭屍進程

子進程退出後留下的進程信息沒有被收集，會導致佔用的進程式控制制塊PCB不被釋放，形成殭屍進程，進程已經死去，但是進程資源沒有被釋放掉

「問題及危害」

如果系統中存在大量的殭屍進程，他們的進程號就會一直被佔用，但是系統所能使用的進程號是有限的，系統將因為沒有可用的進程號而導致系統不能產生新的進程

任何一個子進程(init除外)在exit()之後，並非馬上就消失掉，而是留下一個稱為殭屍進程(Zombie)的數據結構，等待父進程處理，這是每個子進程在結束時都要經過的階段，如果子進程在exit()之後，父進程沒有來得及處理，這時用ps命令就能看到子進程的狀態是Z。

如果父進程能及時處理，可能用ps命令就來不及看到子進程的殭屍狀態，但這並不等於子進程不經過殭屍狀態

產生殭屍進程的元兇其實是他們的父進程，殺掉父進程，殭屍進程就變為了孤兒進程，便可以轉交給 init 進程回收處理

死鎖

「產生原因」

系統資源的競爭：系統資源的競爭導致系統資源不足，以及資源分配不當，導致死鎖。

進程運行推進順序不合適：進程在運行過程中，請求和釋放資源的順序不當，會導致死鎖。

「發生死鎖的四個必要條件」

互斥條件：一個資源每次只能被一個進程使用，即在一段時間內某資源僅為一個進程所佔有，此時若有其他進程請求該資源，則請求進程只能等待

請求與保持條件：進程已經保持了至少一個資源，但又提出了新的資源請求時，該資源已被其他進程佔有，此時請求進程被阻塞，但對自己已獲得的資源保持不放

不可剝奪條件:進程所獲得的資源在未使用完畢之前，不能被其他進程強行奪走，即只能由獲得該資源的進程自己來釋放（只能是主動釋放)

循環等待條件: 若干進程間形成首尾相接循環等待資源的關係

這四個條件是死鎖的必要條件，只要系統發生死鎖，這些條件必然成立，而只要上述條件之一不滿足，就不會發生死鎖

「只要我們破壞其中一個，就可以成功避免死鎖的發生」

其中，互斥這個條件我們沒有辦法破壞，因為我們用鎖為的就是互斥

1. 對於佔用且等待這個條件，我們可以一次性申請所有的資源，這樣就不存在等待了。
2. 對於不可搶佔這個條件，佔用部分資源的線程進一步申請其他資源時，如果申請不到，可以主動釋放它佔有的資源，這樣不可搶佔這個條件就破壞掉了。
3. 對於循環等待這個條件，可以靠按序申請資源來預防，所謂按序申請，是指資源是有線性順序的，申請的時候可以先申請資源序號小的，再申請資源序號大的，這樣線性化後自然就不存在循環了。

「處理方法」

主要有以下四種方法：

• 鴕鳥策略
• 死鎖檢測與死鎖恢復
• 死鎖預防，破壞4個必要條件
• 死鎖避免，銀行家演算法

「鴕鳥策略」

把頭埋在沙子里，假裝根本沒發生問題。

因為解決死鎖問題的代價很高，因此鴕鳥策略這種不採取任務措施的方案會獲得更高的性能。

當發生死鎖時不會對用戶造成多大影響，或發生死鎖的概率很低，可以採用鴕鳥策略。

「死鎖檢測」

不試圖阻止死鎖，而是當檢測到死鎖發生時，採取措施進行恢復。

1. 每種類型一個資源的死鎖檢測
2. 每種類型多個資源的死鎖檢測

「死鎖恢復」

• 利用搶佔恢復
• 利用回滾恢復
• 通過殺死進程恢復

哲學家進餐問題

五個哲學家圍著一張圓桌，每個哲學家面前放著食物。

哲學家的生活有兩種交替活動：吃飯以及思考。

當一個哲學家吃飯時，需要先拿起自己左右兩邊的兩根筷子，並且一次只能拿起一根筷子。

如果所有哲學家同時拿起左手邊的筷子，那麼所有哲學家都在等待其它哲學家吃完並釋放自己手中的筷子，導致死鎖。

哲學家進餐問題可看作是並發進程並發執行時處理共享資源的一個有代表性的問題。

「為了防止死鎖的發生，可以設置兩個條件：」

• 必須同時拿起左右兩根筷子；
• 只有在兩個鄰居都沒有進餐的情況下才允許進餐。

銀行家演算法

銀行家演算法的命名是它可以用了銀行系統，當不能滿足所有客戶的需求時，銀行絕不會分配其資金。

當新進程進入系統時，它必須說明其可能需要的每種類型資源實例的最大數量這一數量不可以超過系統資源的總和。

當用戶申請一組資源時，系統必須確定這些資源的分配是否處於安全狀態，如何安全，則分配，如果不安全，那麼進程必須等待指導某個其他進程釋放足夠資源為止。

「安全狀態」

在避免死鎖的方法中，允許進程動態地申請資源，但系統在進行資源分配之前，應先計算此次資源分配的安全性，若此次分配不會導致系統進入不安全狀態，則將資源分配給進程；否則，令進程等待

因此，避免死鎖的實質在於：系統在進行資源分配時，如何使系統不進入不安全狀態

Fork函數

fork函數用於創建一個與當前進程一樣的子進程，所創建的子進程將複製父進程的代碼段、數據段、BSS段、堆、棧等所有用戶空間信息，在內核中操作系統會重新為其申請一個子進程執行的位置。

fork系統調用會通過複製一個現有進程來創建一個全新的進程，新進程被存放在一個叫做任務隊列的雙向循環鏈表中，鏈表中的每一項都是類型為task_struct的進程式控制制塊PCB的結構。

每個進程都由獨特換不相同的進程標識符（PID），通過getpid()函數可獲取當前進程的進程標識符，通過getppid()函數可獲得父進程的進程標識符。

一個現有的進程可通過調用fork函數創建一個新進程，由fork創建的新進程稱為子進程child process，fork函數被調用一次但返回兩次，兩次返回的唯一區別是子進程中返回0而父進程中返回子進程ID。

「為什麼fork會返回兩次呢？」

因為複製時會複製父進程的堆棧段，所以兩個進程都停留在fork函數中等待返回，因此會返回兩次，一個是在父進程中返回，一次是在子進程中返回，兩次返回值是不一樣的。

• 在父進程中將返回新建子進程的進程ID
• 在子進程中將返回0
• 若出現錯誤則返回一個負數

因此可以通過fork的返回值來判斷當前進程是子進程還是父進程。

「fork執行執行流程」

當進程調用fork後控制轉入內核，內核將會做4件事兒：

1. 分配新的內存塊和內核數據結構給子進程
2. 將父進程部分數據結構內容（數據空間、堆棧等）拷貝到子進程
3. 添加子進程到系統進程列表中
4. fork返回開始調度器調度

「為什麼pid在父子進程中不同呢？」

其實就相當於鏈表，進程形成了鏈表，父進程的pid指向子進程的進程ID，因此子進程沒有子進程，所以PID為0，這裡的pid相當於鏈表中的指針。

設備管理

磁碟調度演算法

讀寫一個磁碟塊的時間的影響因素有：

• 旋轉時間
• 尋道時間實際的數據傳輸時間

其中，尋道時間最長，因此磁碟調度的主要目標是使磁碟的平均尋道時間最短。

先來先服務 FCFS, First Come First Served

按照磁碟請求的順序進行調度，優點是公平和簡單，缺點也很明顯，因為未對尋道做任何優化，使平均尋道時間可能較長。

最短尋道時間優先，SSTF, Shortest Seek Time First

優先調度與當前磁頭所在磁軌距離最近的磁軌， 雖然平均尋道時間比較低，但是不夠公平，如果新到達的磁軌請求總是比一個在等待的磁軌請求近，那麼在等待的 磁軌請求會一直等待下去，也就是出現飢餓現象，具體來說，兩邊的磁軌請求更容易出現飢餓現象。

電梯演算法，SCAN

電梯總是保持一個方向運行，直到該方向沒有請求為止，然後改變運行方向， 電梯演算法（掃描演算法）和電梯的運行過程類似，總是按一個方向來進行磁碟調度，直到該方向上沒有未完成的磁碟 請求，然後改變方向，因為考慮了移動方向，因此所有的磁碟請求都會被滿足，解決了 SSTF 的飢餓問題

內存管理

「邏輯地址和物理地址」

我們編程一般只有可能和邏輯地址打交道，比如在 C 語言中，指針裡面存儲的數值就可以理解成為內存里的一個地址，這個地址也就是我們說的邏輯地址，邏輯地址由操作系統決定。

物理地址指的是真實物理內存中地址，更具體一點來說就是內存地址寄存器中的地址，物理地址是內存單元真正的地址。

編譯時只需確定變數x存放的相對地址是100 ( 也就是說相對於進程在內存中的起始地址而言的地址)。

CPU想要找到x在內存中的實際存放位置，只需要用進程的起始地址+100即可。

相對地址又稱邏輯地址，絕對地址又稱物理地址。

「內存管理有哪幾種方式」

1. 「塊式管理」：將內存分為幾個固定大小的塊，每個塊中只包含一個進程，如果程序運行需要內存的話，操作系統就分配給它一塊，如果程序運行只需要很小的空間的話，分配的這塊內存很大一部分幾乎被浪費了，這些在每個塊中未被利用的空間，我們稱之為碎片。
2. 「頁式管理」：把主存分為大小相等且固定的一頁一頁的形式，頁較小，相對相比於塊式管理的劃分力度更大，提高了內存利用率，減少了碎片，頁式管理通過頁表對應邏輯地址和物理地址。

1. 「段式管理」： 頁式管理雖然提高了內存利用率，但是頁式管理其中的頁實際並無任何實際意義， 段式管理把主存分為一段段的，每一段的空間又要比一頁的空間小很多 ，段式管理通過段表對應邏輯地址和物理地址。
2. 「段頁式管理機制：「段頁式管理機制結合了段式管理和頁式管理的優點，簡單來說段頁式管理機制就是把主存先分成若干段，每個段又分成若干頁，也就是說」段頁式管理機制」中段與段之間以及段的內部的都是離散的。

虛擬地址

現代處理器使用的是一種稱為**虛擬定址(Virtual Addressing)**的定址方式

「使用虛擬定址，CPU 需要將虛擬地址翻譯成物理地址，這樣才能訪問到真實的物理內存。」

實際上完成虛擬地址轉換為物理地址轉換的硬體是 CPU 中含有一個被稱為**內存管理單元（Memory Management Unit, MMU）**的硬體

「為什麼要有虛擬地址空間」

沒有虛擬地址空間的時候，「程序都是直接訪問和操作的都是物理內存」。

但是這樣有什麼問題？

1. 用戶程序可以訪問任意內存，定址內存的每個位元組，這樣就很容易破壞操作系統，造成操作系統崩潰。
2. 想要同時運行多個程序特別困難，比如你想同時運行一個微信和一個 QQ 音樂都不行，為什麼呢？舉個簡單的例子：微信在運行的時候給內存地址 1xxx 賦值後，QQ 音樂也同樣給內存地址 1xxx 賦值，那麼 QQ 音樂對內存的賦值就會覆蓋微信之前所賦的值，這就造成了微信這個程序就會崩潰。

「通過虛擬地址訪問內存有以下優勢：」

• 程序可以使用一系列相鄰的虛擬地址來訪問物理內存中不相鄰的大內存緩衝區。
• 程序可以使用一系列虛擬地址來訪問大於可用物理內存的內存緩衝區。
• 不同進程使用的虛擬地址彼此隔離，一個進程中的代碼無法更改正在由另一進程或操作系統使用的物理內存。

「MMU如何把虛擬地址翻譯成物理地址的」

對於每個程序，內存管理單元MMU都為其保存一個頁表，該頁表中存放的是虛擬頁面到物理頁面的映射。

每當為一個虛擬頁面尋找到一個物理頁面之後，就在頁表裡增加一條記錄來保留該映射關係，當然，隨著虛擬頁面進出物理內存，頁表的內容也會不斷更新變化。

虛擬內存

很多時候我們使用點開了很多佔內存的軟體，這些軟體佔用的內存可能已經遠遠超出了我們電腦本身具有的物理內存

通過 「虛擬內存」 可以讓程序可以擁有超過系統物理內存大小的可用內存空間。

另外，虛擬內存為每個進程提供了一個一致的、私有的地址空間，它讓每個進程產生了一種自己在獨享主存的錯覺（每個進程擁有一片連續完整的內存空間），這樣會更加有效地管理內存並減少出錯。

「虛擬內存」是計算機系統內存管理的一種技術，我們可以手動設置自己電腦的虛擬內存

「虛擬內存的重要意義是它定義了一個連續的虛擬地址空間」，並且 「把內存擴展到硬碟空間」

「虛擬內存的實現有以下三種方式：」

1. 「請求分頁存儲管理」 ：請求分頁是目前最常用的一種實現虛擬存儲器的方法，請求分頁存儲管理系統中，在作業開始運行之前，僅裝入當前要執行的部分段即可運行，假如在作業運行的過程中發現要訪問的頁面不在內存，則由處理器通知操作系統按照對應的頁面置換演算法將相應的頁面調入到主存，同時操作系統也可以將暫時不用的頁面置換到外存中。
2. 「請求分段存儲管理」 ：請求分段儲存管理方式就如同請求分頁儲存管理方式一樣，在作業開始運行之前，僅裝入當前要執行的部分段即可運行；在執行過程中，可使用請求調入中斷動態裝入要訪問但又不在內存的程序段；當內存空間已滿，而又需要裝入新的段時，根據置換功能適當調出某個段，以便騰出空間而裝入新的段。
3. 「請求段頁式存儲管理」

不管是上面那種實現方式，我們一般都需要：

一定容量的內存和外存：在載入程序的時候，只需要將程序的一部分裝入內存，而將其他部分留在外存，然後程序就可以執行了；

缺頁中斷

如果「需執行的指令或訪問的數據尚未在內存」（稱為缺頁或缺段），則由處理器通知操作系統將相應的頁面或段「調入到內存」，然後繼續執行程序；

在分頁系統中，一個虛擬頁面既有可能在物理內存，也有可能保存在磁碟上。

如果CPU發出的虛擬地址對應的頁面不在物理內存，就將產生一個缺頁中斷，而缺頁中斷服務程序負責將需要的虛擬頁面找到並載入到內存。

缺頁中斷的處理步驟如下，省略了中間很多的步驟，只保留最核心的幾個步驟：

頁面置換演算法

當發生缺頁中斷時，如果當前內存中並沒有空閑的頁面，操作系統就必須在內存選擇一個頁面將其移出內存，以便為即將調入的頁面讓出空間。

用來選擇淘汰哪一頁的規則叫做頁面置換演算法，我們可以把頁面置換演算法看成是淘汰頁面的規則

• 「OPT 頁面置換演算法（最佳頁面置換演算法）」 ：該置換演算法所選擇的被淘汰頁面將是以後永不使用的，或者是在最長時間內不再被訪問的頁面，這樣可以保證獲得最低的缺頁率，但由於人們目前無法預知進程在內存下的若千頁面中哪個是未來最長時間內不再被訪問的，因而該演算法無法實現，一般作為衡量其他置換演算法的方法。
• 「FIFO（First In First Out） 頁面置換演算法（先進先出頁面置換演算法）」 : 總是淘汰最先進入內存的頁面，即選擇在內存中駐留時間最久的頁面進行淘汰。
• 「LRU （Least Currently Used）頁面置換演算法（最近最久未使用頁面置換演算法）」 ：LRU演算法賦予每個頁面一個訪問欄位，用來記錄一個頁面自上次被訪問以來所經歷的時間 T，當須淘汰一個頁面時，選擇現有頁面中其 T 值最大的，即最近最久未使用的頁面予以淘汰。
• 「LFU （Least Frequently Used）頁面置換演算法（最少使用頁面置換演算法）」 : 該置換演算法選擇在之前時期使用最少的頁面作為淘汰頁。

局部性原理

局部性原理是虛擬內存技術的基礎，正是因為程序運行具有局部性原理，才可以只裝入部分程序到內存就開始運行。

局部性原理表現在以下兩個方面：

1. 「時間局部性」 ：如果程序中的某條指令一旦執行，不久以後該指令可能再次執行；如果某數據被訪問過，不久以後該數據可能再次被訪問，產生時間局部性的典型原因，是由於在程序中存在著大量的循環操作。
2. 「空間局部性」 ：一旦程序訪問了某個存儲單元，在不久之後，其附近的存儲單元也將被訪問，即程序在一段時間內所訪問的地址，可能集中在一定的範圍之內，這是因為指令通常是順序存放、順序執行的，數據也一般是以向量、數組、表等形式簇聚存儲的。

時間局部性是通過將近來使用的指令和數據保存到「高速緩存存儲器」中，並使用高速緩存的層次結構實現。

空間局部性通常是使用較大的高速緩存，並將預取機制集成到高速緩存控制邏輯中實現。

頁表

操作系統將虛擬內存分塊，每個小塊稱為一個頁（Page）；真實內存也需要分塊，每個小塊我們稱為一個 Frame。

Page 到 Frame 的映射，需要一種叫作頁表的結構。

上圖展示了 Page、Frame 和頁表 （PageTable）三者之間的關係。

Page 大小和 Frame 大小通常相等，頁表中記錄的某個 Page 對應的 Frame 編號。

頁表也需要存儲空間，比如虛擬內存大小為 10G， Page 大小是 4K，那麼需要 10G/4K = 2621440 個條目。

如果每個條目是 64bit，那麼一共需要 20480K = 20M 頁表，操作系統在內存中劃分出小塊區域給頁表，並負責維護頁表。

「頁表維護了虛擬地址到真實地址的映射。」

每次程序使用內存時，需要把虛擬內存地址換算成物理內存地址，換算過程分為以下 3 個步驟：

• 通過虛擬地址計算 Page 編號；
• 查頁表，根據 Page 編號，找到 Frame 編號；
• 將虛擬地址換算成物理地址。

多級頁表

引入多級頁表的主要目的是為了避免把全部頁表一直放在內存中佔用過多空間，特別是那些根本就不需要的頁表就不需要保留在內存中

「一級頁表：」

假如物理內存中一共有1048576個頁，那麼頁表就需要總共就是1048576 * 4B = 4M。

也就是說我需要4M連續的內存來存放這個頁表，也就是一級頁表。

隨著虛擬地址空間的增大，存放頁表所需要的連續空間也會增大，在操作系統內存緊張或者內存碎片較多時，這無疑會帶來額外的開銷。

頁表定址是用寄存器來確定一級頁表地址的，所以一級頁表的地址必須指向確定的物理頁，否則就會出現錯誤，所以如果用一級頁表的話，就必須把全部的頁表都載入進去。

「二級頁表：」

而使用二級頁表的話，只需要載入一個頁目錄表(一級頁表)，大小為4K，可以管理1024個二級頁表。

可能你會有疑問，這1024個二級頁表也是需要內存空間的，這下反而需要4MB+4KB的內存，反而更多了。

其實二級頁表並不是一定要存在內存中的，內存中只需要一個一級頁表地址存在存器即可，二級頁表可以使用缺頁中斷從外存移入內存。

「多級頁表屬於時間換空間的典型場景」

快表

為了解決虛擬地址到物理地址的轉換速度，操作系統在「頁表方案」基礎之上引入了「快表」來加速虛擬地址到物理地址的轉換

我們可以把快表理解為一種特殊的「高速緩衝存儲器（Cache）」，其中的內容是頁表的一部分或者全部內容，作為頁表的 Cache，它的作用與頁表相似，但是提高了訪問速率，由於採用頁表做地址轉換，讀寫內存數據時 CPU 要訪問兩次主存，有了快表，有時只要訪問一次高速緩衝存儲器，一次主存，這樣可加速查找並提高指令執行速度。

「使用快表之後的地址轉換流程是這樣的：」

1. 根據虛擬地址中的頁號查快表；
2. 如果該頁在快表中，直接從快表中讀取相應的物理地址；
3. 如果該頁不在快表中，就訪問內存中的頁表，再從頁表中得到物理地址，同時將頁表中的該映射表項添加到快表中；
4. 當快表填滿後，又要登記新頁時，就按照一定的淘汰策略淘汰掉快表中的一個頁。

內存管理單元

在 CPU 中一個小型的設備——內存管理單元（MMU）

當 CPU 需要執行一條指令時，如果指令中涉及內存讀寫操作，CPU 會把虛擬地址給 MMU，MMU 自動完成虛擬地址到真實地址的計算；然後，MMU 連接了地址匯流排，幫助 CPU 操作真實地址。

在不同 CPU 的 MMU 可能是不同的，因此這裡會遇到很多跨平台的問題。

解決跨平台問題不但有繁重的工作量，更需要高超的編程技巧。

動態分區分配演算法

內存分配演算法，大體來說分為：「連續式分配 與 非連續式分配」

連續式分配就是把所以要執行的程序 「完整的，有序的」 存入內存，連續式分配又可以分為「固定分區分配 和 動態分區分配」

非連續式分配就是把要執行的程序按照一定規則進行拆分，顯然這樣更有效率，現在的操作系統通常也都是採用這種方式分配內存

所謂動態分區分配，就是指「內存在初始時不會劃分區域，而是會在進程裝入時，根據所要裝入的進程大小動態地對內存空間進行劃分，以提高內存空間利用率，降低碎片的大小」

動態分區分配演算法有以下四種：

首次適應演算法（First Fit）

空閑分區以地址遞增的次序鏈接，分配內存時順序查找，找到大小滿足要求的第一個空閑分區就進行分配

鄰近適應演算法（Next Fit）

又稱循環首次適應法，由首次適應法演變而成，不同之處是分配內存時從上一次查找結束的位置開始繼續查找

最佳適應演算法（Best Fit）

空閑分區按容量遞增形成分區鏈，找到第一個能滿足要求的空閑分區就進行分配

最壞適應演算法（Next Fit）

又稱最大適應演算法，空閑分區以容量遞減的次序鏈接，找到第一個能滿足要求的空閑分區（也就是最大的分區）就進行分配

「總結」

首次適應不僅最簡單，通常也是最好最快，不過首次適應演算法會使得內存低地址部分出現很多小的空閑分區，而每次查找都要經過這些分區，因此也增加了查找的開銷。

鄰近演算法試圖解決這個問題，但實際上，它常常會導致在內存的末尾分配空間分裂成小的碎片，它通常比首次適應演算法結果要差。

最佳適應演算法導致大量碎片，最壞適應演算法導致沒有大的空間。

內存覆蓋

覆蓋與交換技術是在程序用來擴充內存的兩種方法。

早期的計算機系統中，主存容量很小，雖然主存中僅存放一道用戶程序，但是存儲空間放不下用戶進程的現象也經常發生，這一矛盾可以用覆蓋技術來解決。

「覆蓋的基本思想是：」

由於程序運行時並非任何時候都要訪問程序及數據的各個部分（尤其是大程序），因此可以把用戶空間分成一個固定區和若干個覆蓋區。

將經常活躍的部分放在固定區，其餘部分按調用關係分段。

首先將那些即將要訪問的段放入覆蓋區，其他段放在外存中，在需要調用前，系統再將其調入覆蓋區，替換覆蓋區中原有的段。

覆蓋技術的特點是打破了必須將一個進程的全部信息裝入主存後才能運行的限制，但當同時運行程序的代碼量大於主存時仍不能運行。

內存交換

「交換的基本思想」

把處於等待狀態（或在CPU調度原則下被剝奪運行權利）的程序從內存移到輔存，把內存空間騰出來，這一過程又叫換出；

把準備好競爭CPU運行的程序從輔存移到內存，這一過程又稱為換入。

例如，有一個CPU釆用時間片輪轉調度演算法的多道程序環境。

時間片到，內存管理器將剛剛執行過的進程換出，將另一進程換入到剛剛釋放的內存空間中。

同時，CPU調度器可以將時間片分配給其他已在內存中的進程。

每個進程用完時間片都與另一進程交換。

理想情況下，內存管理器的交換過程速度足夠快，總有進程在內存中可以執行。

交換技術主要是在不同進程（或作業）之間進行，而覆蓋則用於同一個程序或進程中。

由於覆蓋技術要求給出程序段之間的覆蓋結構，使得其對用戶和程序員不透明，所以對於主存無法存放用戶程序的矛盾

現代操作系統是通過虛擬內存技術來解決的，覆蓋技術則已成為歷史；而交換技術在現代操作系統中仍具有較強的生命力。

常見面試題

「進程、線程的區別」

操作系統會以進程為單位，分配系統資源（CPU時間片、內存等資源），進程是資源分配的最小單位。

調度：線程作為CPU調度和分配的基本單位，進程作為擁有資源的基本單位；

並發性：不僅進程之間可以並發執行，同一個進程的多個線程之間也可並發執行；

擁有資源：

進程是擁有資源的一個獨立單位，線程不擁有系統資源，但可以訪問隸屬於進程的資源。

進程所維護的是程序所包含的資源（靜態資源）， 如：地址空間，打開的文件句柄集，文件系統狀態，信號處理handler等；

線程所維護的運行相關的資源（動態資源），如：運行棧，調度相關的控制信息，待處理的信號集等；

系統開銷：

在創建或撤消進程時，由於系統都要為之分配和回收資源，導致系統的開銷明顯大於創建或撤消線程時的開銷。

但是進程有獨立的地址空間，一個進程崩潰後，在保護模式下不會對其它進程產生影響，而線程只是一個進程中的不同執行路徑。

線程有自己的堆棧和局部變數，但線程之間沒有單獨的地址空間，一個進程死掉就等於所有的線程死掉，所以多進程的程序要比多線程的程序健壯，但在進程切換時，耗費資源較大，效率要差一些。

「一個進程可以創建多少線程」

理論上，一個進程可用虛擬空間是2G，默認情況下，線程的棧的大小是1MB，所以理論上最多只能創建2048個線程。

如果要創建多於2048的話，必須修改編譯器的設置。

在一般情況下，你不需要那麼多的線程，過多的線程將會導致大量的時間浪費在線程切換上，給程序運行效率帶來負面影響。

「外中斷和異常有什麼區別」

外中斷是指由 CPU 執行指令以外的事件引起，如 I/O 完成中斷，表示設備輸入/輸出處理已經完成，處理器能夠發送下一個輸入/輸出請求，此外還有時鐘中斷、控制台中斷等。

而異常時由 CPU 執行指令的內部事件引起，如非法操作碼、地址越界、算術溢出等。

「解決Hash衝突四種方法」

開放定址法

• 開放定址法就是一旦發生了衝突，就去尋找下一個空的散列地址，只要散列表足夠大，空的散列地址總能找到，並將記錄存入。

鏈地址法

• 將哈希表的每個單元作為鏈表的頭結點，所有哈希地址為i的元素構成一個同義詞鏈表。即發生衝突時就把該關鍵字鏈在以該單元為頭結點的鏈表的尾部。

再哈希法

• 當哈希地址發生衝突用其他的函數計算另一個哈希函數地址，直到衝突不再產生為止。

建立公共溢出區

• 將哈希表分為基本表和溢出表兩部分，發生衝突的元素都放入溢出表中。

「分頁機制和分段機制有哪些共同點和區別」

共同點

• 分頁機制和分段機制都是為了提高內存利用率，較少內存碎片。
• 頁和段都是離散存儲的，所以兩者都是離散分配內存的方式。但是，每個頁和段中的內存是連續的。

區別

• 頁的大小是固定的，由操作系統決定；而段的大小不固定，取決於我們當前運行的程序。
• 分頁僅僅是為了滿足操作系統內存管理的需求，而段是邏輯信息的單位，在程序中可以體現為代碼段，數據段，能夠更好滿足用戶的需要。
• 分頁是一維地址空間，分段是二維的。

「介紹一下幾種典型的鎖」

讀寫鎖

• 可以同時進行多個讀
• 寫者必須互斥（只允許一個寫者寫，也不能讀者寫者同時進行）
• 寫者優先於讀者（一旦有寫者，則後續讀者必須等待，喚醒時優先考慮寫者）

互斥鎖

一次只能一個線程擁有互斥鎖，其他線程只有等待

互斥鎖是在搶鎖失敗的情況下主動放棄CPU進入睡眠狀態直到鎖的狀態改變時再喚醒，而操作系統負責線程調度，為了實現鎖的狀態發生改變時喚醒阻塞的線程或者進程，需要把鎖交給操作系統管理，所以互斥鎖在加鎖操作時涉及上下文的切換。

互斥鎖實際的效率還是可以讓人接受的，加鎖的時間大概100ns左右，而實際上互斥鎖的一種可能的實現是先自旋一段時間，當自旋的時間超過閥值之後再將線程投入睡眠中，因此在並發運算中使用互斥鎖（每次佔用鎖的時間很短）的效果可能不亞於使用自旋鎖

條件變數

互斥鎖一個明顯的缺點是他只有兩種狀態：鎖定和非鎖定。

而條件變數通過允許線程阻塞和等待另一個線程發送信號的方法彌補了互斥鎖的不足，他常和互斥鎖一起使用，以免出現競態條件。

當條件不滿足時，線程往往解開相應的互斥鎖並阻塞線程然後等待條件發生變化。

一旦其他的某個線程改變了條件變數，他將通知相應的條件變數喚醒一個或多個正被此條件變數阻塞的線程。

總的來說「互斥鎖是線程間互斥的機制，條件變數則是同步機制。」

自旋鎖

如果進線程無法取得鎖，進線程不會立刻放棄CPU時間片，而是一直循環嘗試獲取鎖，直到獲取為止。

如果別的線程長時期佔有鎖，那麼自旋就是在浪費CPU做無用功，但是自旋鎖一般應用於加鎖時間很短的場景，這個時候效率比較高。

雖然它的效率比互斥鎖高，但是它也有些不足之處：

• 自旋鎖一直佔用CPU，在未獲得鎖的情況下，一直進行自旋，所以佔用著CPU，如果不能在很短的時間內獲得鎖，無疑會使CPU效率降低。
• 在用自旋鎖時有可能造成死鎖，當遞歸調用時有可能造成死鎖。

「如何讓進程後台運行」

1.命令後面加上&即可，實際上，這樣是將命令放入到一個作業隊列中了

2.ctrl + z 掛起進程，使用jobs查看序號，在使用bg %序號後台運行進程

3.nohup + &，將標準輸出和標準錯誤預設會被重定向到 nohup.out 文件中，忽略所有掛斷（SIGHUP）信號

nohup ping www.ibm.com &

4.運行指令前面 + setsid，使其父進程變成init進程，不受SIGHUP信號的影響

[root@pvcent107 ~]# setsid ping www.ibm.com
[root@pvcent107 ~]# ps -ef |grep www.ibm.com
root     31094     1  0 07:28 ?        00:00:00 ping www.ibm.com
root     31102 29217  0 07:29 pts/4    00:00:00 grep www.ibm.com

上例中我們的進程 ID(PID)為31094，而它的父 ID（PPID）為1（即為 init 進程 ID），並不是當前終端的進程 ID。

5.將命令+ &放在()括弧中，也可以是進程不受HUP信號的影響

[root@pvcent107 ~]# (ping www.ibm.com &)

「異常和中斷的區別」

中斷

當我們在敲擊鍵盤的同時就會產生中斷，當硬碟讀寫完數據之後也會產生中斷，所以，我們需要知道，中斷是由硬體設備產生的，而它們從物理上說就是電信號，之後，它們通過中斷控制器發送給CPU，接著CPU判斷收到的中斷來自於哪個硬體設備（這定義在內核中），最後，由CPU發送給內核，有內核處理中斷。

下面這張圖顯示了中斷處理的流程：

異常

CPU處理程序的時候一旦程序不在內存中，會產生缺頁異常；當運行除法程序時，當除數為0時，又會產生除0異常。

「異常是由CPU產生的，同時，它會發送給內核，要求內核處理這些異常」

下面這張圖顯示了異常處理的流程：

相同點

• 最後都是由CPU發送給內核，由內核去處理
• 處理程序的流程設計上是相似的

不同點

• 產生源不相同，異常是由CPU產生的，而中斷是由硬體設備產生的
• 內核需要根據是異常還是中斷調用不同的處理程序
• 中斷不是時鐘同步的，這意味著中斷可能隨時到來；異常由於是CPU產生的，所以它是時鐘同步的
• 當處理中斷時，處於中斷上下文中；處理異常時，處於進程上下文中