《作業系統導論》讀書筆記1——CPU虛擬化，程序

系列文章目錄和關於我

一丶CPU的虛擬化

一個桃子，我們稱之為物理（physical）桃子。但有很多想吃這個桃子的 人，我們希望向每個想吃的人提供一個屬於他的桃子，這樣才能皆大歡喜。我們把給每個 人的桃子稱為虛擬（virtual）桃子。我們通過某種方式，從這個物理桃子創造出許多虛擬桃子。重要的是，在這種假象中，每個人看起來都有一個物理桃子，但實際上不是。

以最基本的計算機資源 CPU 為例， 假設一個計算機只有一個 CPU（儘管現代計算機一般擁有 2 個、4 個或者更多 CPU），虛擬化要做的就是將這個 CPU 虛擬成多個虛擬 CPU 並分給每一個程序使用，因此，每個應用都以為自己在獨佔 CPU，但實際上只有一個 CPU。這便是CPU的虛擬化

二丶程序

1.概念

程序就是執行中的程式。程式本身是沒有生命週期的，它只是存在磁碟上面的一些指令（也可能是一些靜態資料）。是作業系統讓這些位元組執行起來，讓程式發揮作用。

2.程序的機器狀態

程式在執行時可以讀取或更新的內容。在任何時刻，機器的哪些部分對執行該程式很重要（程序執行過程中會使用到機器的哪些部分）

• 記憶體

  指令存在記憶體中。正在執行的程式讀取和寫入的資料也在記憶體中。因此程序可以存取的記憶體（稱為地址空間，address space） 是該程序的一部分

• 暫存器

  許多指令明確地讀取或更新暫存器

• 程式計數器

  代表程式當前正在執行哪個指令；類似地，棧指標（stack pointer）和相關的影格指標（frame pointer）用於 管理函數引數棧、區域性變數和返回地址。

• 持久儲存裝置

  此類 I/O 資訊可能包含當前開啟的檔案列表

3.時分共用

通過讓一個程序只執行一個時間片，然後切換到其他程序，作業系統提供了存在多個虛擬 CPU 的假象。這就是時分共用（time sharing）CPU 技術。

磁碟空間是一個空分共用資源，因為一旦將塊分配給檔案，在使用者刪除檔案之前，不可能將它分配給其他檔案。

4.程式如何轉化為程序

作業系統如何啟動並執行一個程式？程序建立實際如何進行？

• 程式最初以某種可執行格式駐留在磁碟上

  作業系統需要將程式碼和所有靜態資料（例如初始化變數）載入（load）到記憶體中，載入到程序的地址空間中

  

• 為程序分配空間

  為程式的執行時棧分配一些記憶體。程式使用棧存放區域性變數、函數引數和返回地址。作業系統分配這些記憶體，並提供給程序。

• 為程式的堆分配一些記憶體

  C語言程式通過呼叫 malloc()來請求這樣的空間

• 其他初始化任務

  如在UNIX系統中，預設情況下每個程序都有 3 個開啟的檔案描述符（file descriptor），用於標 準輸入、輸出和錯誤。這些描述符讓程式輕鬆讀取來自終端的輸入以及列印輸出到螢幕。

  作業系統需要初始化這三個檔案描述符

5.程序的狀態

• 執行

在執行狀態下，程序正在處理器上執行。這意味著它正在執行 指令。

• 就緒

在就緒狀態下，程序已準備好執行,但沒有被CPU進行排程

• 阻塞

在阻塞狀態下，一個程序執行了某種操作，直到發生其他事件時才會準備執行。一個常見的例子是，當程序向磁碟發起 I/O 請求時，它會被阻塞， 因此其他程序可以使用處理器。

為了跟蹤每個程序的狀態，作業系統使用程序列表，跟蹤當前正在執行的程序的一些附加資訊。作業系統還必須以某種方式跟蹤被阻塞的程序(當 I/O 事件完成時，作業系統應確保喚醒正確的程序，讓它準備好再次執行)

對於停止的程序，暫存器上下文將儲存其暫存器的內容。當一個程序停止時，它的暫存器將被儲存到這個記憶體位置。 通過恢復這些暫存器（將它們的值放回實際的物理暫存器中），作業系統實現恢復執行該程序。

殭屍狀態:一個程序處於已退出但尚未清理的最終狀態。其他程序（通常是建立程序的父程序）可以檢查殭屍程序的返回程式碼，並檢視剛剛完成的程序是否成功執行。

6.程序API

6.1.fork

呼叫fork函數，父程序fork函數返回的是子程序的程序id，子程序將返回0，如果返回小於0的數表示fork失敗。

6.2.exec

使用exec系統呼叫，需要給定可執行程式的名稱以及需要的引數，隨後exec將從可執行程式中載入程式碼和靜態資料，並用它複寫自己的程式碼段，靜態資料，堆，棧以及其他記憶體空間也會被重新初始化，然後作業系統就執行該程式。

因此exec()並沒有建立新程序，而是直接將執行的程式替換成另一個程式。

6.4.wait

父程序呼叫 wait()，延遲自己的執行，直到子程序執行完畢。當子程序結束時，父程序才從wait返回。

三丶程序的排程

為了虛擬化 CPU，作業系統需要以某種方式讓許多程序共用物理 CPU，讓它們看起來像是同時執行。作業系統使用時分共用：執行一個程序一段時間，然後執行另一個程序實現cpu的虛擬化。

實現時分共用面臨的挑戰：

• 效能

  如何在不增加系統開銷的情況下，實現虛擬化cpu

• 控制權

  如何有效地執行程序，同時保留對 CPU 的控制？控制權對於作業系統尤為重要，因為作業系統負責資源管理。如果沒有控制權，一個程序可以簡單地無限制執行並接管機器，或存取沒有許可權的資訊。因此，在保持控制權的 同時獲得高效能，這是構建作業系統的主要挑戰之一。

1.使用者態/核心態

• 使用者模式

  此模式下執行的程式碼會受到限制。例如，在使用者模式下執行時，程序不能發出 I/O 請求。這 樣做會導致處理器引發異常，作業系統可能會終止程序。

  應用程式在使用者態下無法完全的存取硬體資源。

• 核心模式

  與使用者模式不同的核心模式，作業系統（或核心）就以這種模式執行。在此模式下作業系統可以存取機器的全部資源。

如果使用者態的程序希望執行一些特權操作（比如讀取磁碟），那麼需要執行作業系統向外提供的系統呼叫。

要執行系統呼叫，程式必須執行特殊的陷阱指令。執行陷阱指令可以切換到核心態，完成指令後，作業系統將呼叫一個特殊的從陷阱返回指令，該指令會返回到發起呼叫的使用者程式中，同時將 特權級別降低，回到使用者模式。

在 x86 上執行陷阱指令時，處理器會將程式計數器、標誌和其他一些暫存器中的資訊儲存到每個程序的核心棧上。從陷阱中返回時將從棧彈出這些值，並恢復執行使用者模式程式。

2.程序切換

2.1 共同作業和搶佔

• 共同作業模式

  作業系統相信系統的程序會合理執行。執行時間過長的程序被假定會定期放棄 CPU，以便作業系統可以決定執行其他任務。

  程序通過呼叫系統呼叫的方式將cpu控制權轉移給作業系統，例如使用yield系統呼叫。

• 搶佔模式

  操心繫統通過時鐘中斷,時鐘裝置可以程式設計為每隔幾毫秒產生一次中斷。產生中斷時，當前正在執行的程序停止，作業系統中預先設定的中斷處理程式會執行。此時，作業系統重新獲得 CPU 的控制權，可以進行程序切換。

2.2 上下文切換

當作業系統進行程序切換的時候，需要

• 為當前執行的執行緒

  來儲存通用暫存器、程式計數器，以及當前正在執行的程序的核心棧指標

• 為即將執行的程序

  恢復暫存器、程式計數器，並切換核心棧，供即將執行的程序使用

3.程序排程演演算法

3.1 衡量演演算法的指標

• 週轉時長

  完成時間 - 到達時間

• 響應時間

  首次執行 - 到達時間

• CPU利用率

  cpu執行任務時間/總cpu時間

• 吞吐量

  完成任務數量/執行任務花費的時間

3.2 演演算法

3.2.1 先進先出/先到先服務

• 優點：簡單，而且易於實現。
• 缺點：一些耗時較少的潛在資源消費者被排在重量級的資源消費者之後。當大任務排在小任務前的時候，小任務的週轉時長指標很差勁

3.2.1 最短任務優先

這種策略在所有任務都是一起到達的時候，週轉時長指標很優秀 。但是現實情況下，大任務可能比小任務先到達。這是由於最短任務優先是一個非搶佔式的排程演演算法。

3.3.3 最短完成時間優先

受到最短任務優先的啟發，在它之上加上排程程式的搶佔行為，每當新工作進入系統時，它就會確定剩餘工作和新工作中， 誰的剩餘時間最少，然後排程該工作

3.3.4 輪轉

在一個時間片內執行一個工作，然後切換到執行佇列中的下一個任務，而不是執行一個任務直到結束。它反覆執行，直到所有任務完成。時間片長度必須是時鐘中斷週期的倍數。因此，如果時鐘中斷是每 10ms 中斷一次， 則時間片可以是 10ms、20ms 或 10ms 的任何其他倍數。

時間片越短，那麼在響應時間指標上更優先。但是頻繁的上下文切換是影響整體上下文的。

輪轉演演算法在週轉時長指標上表現很糟糕，但是在程序執行io等操作時候進行輪轉切換，這對於cpu的利用率和效率是有益的。

如上圖7.9在執行磁碟io操作的時候，作業系統排程其他的緊湊，讓兩個任務執行總時間更短。

3.3.5 多級反饋佇列

多級反饋佇列中有許多獨立的佇列，每個佇列有不同的優先順序。任何 時刻，一個工作只能存在於一個佇列中。多級反饋佇列總是優先執行較高優先順序的工作（即在較高階佇列中的工作）。同一個佇列中的任務具備相同的優先順序，相同優先順序的任務使用輪轉。

多級反饋佇列任務的優先順序，會根據觀察程序的行為進行調整。如果一個工作不斷放棄 CPU 去等待鍵盤輸入，這是互動型程序的可能行為， 因此會讓它保持高優先順序。相反，如果一個工作長時間地佔用 CPU，會降低其優先順序。

高優先順序佇列通常只有較短的時間片，因而這一層的互動工作(例如等待鍵盤輸入這樣的io操作)可以更快地切換。相反，低優先順序佇列中更多的是 CPU 密集型工作，設定更長的時間片會取得更好的效果。

3.3.6 比例份額

基本思想很簡單：每隔一段時間，都會舉行一次彩票抽獎，以確定接下來應該執行哪個程序。越是應該頻繁執行的程序，越是應該擁有更多地贏得彩票的機會。

彩票數代表了程序佔有某個資源的份額。一個程序擁有的彩票數佔總彩票數的百分比，就是它佔有資源的份額。