程序描述和控制
計算機最初的主要任務之一就是高效的自動化我們的工作，完成使用者傳遞的任務。而這種任務在計算機中的表示就是一個個的程序。從上一篇文章中描述的計算機的發展曆史我們能發現，無論是單道批處理系統還是多道批處理系統，作業系統的目的都是圍繞對程序的控制和排程，進而實作執行使用者任務。是以，系統必須滿足的大多數操作都涉及程序。而為了 控制程序，作業系統必須為每一個程序 維護一個資料結構，這個資料結構描述程序的狀态和資源的所有權。
什麼是程序
1、定義
- 正在執行的程式
- 正在計算機上執行的程式程式執行個體
- 能配置設定給處理器并由處理器執行的實體
- 一組指令序列的執行、一個目前狀态和相關的系統資源集
程序的兩個基本元素是程式代碼和相關聯的資料集。
2、程序控制塊
程序控制塊 是由作業系統建立和管理的具有一個程序充分資訊的資料結構。通過使用程序控制塊，作業系統可以透明的中斷和恢複一個程序。它是作業系統能夠支援多程序和提供多處理的關鍵工具。
程序控制塊通常包括以下内容：
- 辨別符
- 狀态
- 優先級
- 程式計數器：程式中即将被執行的下一條指令的位址
- 記憶體指針：包括程式代碼和程序相關資料的指針，還有和其他程序共享記憶體塊的指針
- 上下文資料：程序執行時處理器的寄存器中的資料（用于恢複執行）
- I/O 狀态資訊
- 記賬資訊
現在，可以認為一個程序是由代碼段，資料段和程序控制塊組成。
程序狀态
作業系統的基本職責就是控制程序的執行，這包括确定交替執行的方式和給程序配置設定資源。在設計控制程序的程式時，第一步就是描述程序所表現出的行為。
1、兩狀态程序模型
通過觀察可知，一個程序可以處于兩種狀态，運作和未運作，是以可以構造最簡單的程序狀态模型，隻有兩個狀态，運作态和未運作态。由于多道程式設計的原因，一個程式在未結束前将會在這兩個狀态之間進行切換。之後随着更多因素的加入，模型将會變得更為具體。
兩狀态程序模型将維護一個 FIFO 隊列，其中儲存未在運作的程序的資料結構。分派程式（監控程式的一部分）每次從中選擇一個程序執行。
2、程序的建立和終止
程序的建立
當一個程序添加到那些正在被管理的程序集合中去時，作業系統需要建立用于管理該程序的資料結構（之後介紹），并在記憶體中給他配置設定位址空間。
導緻程序被建立的條件：
- 建立的批處理作業
- 互動登入
- 作業系統因為提供一項服務而建立
- 由現有的程序派生
導緻程序被結束的原因：
- 正常完成
- 超過時限
- 運作錯誤
- 無可用記憶體
- 越界
- 算數溢出
- 指令錯誤
- 等
- 父程序終止
- 操作員或系統幹涉
- 父程序請求子程序結束
3、五狀态模型
兩狀态模型中的待執行隊列采用先進先出的方式（不考慮優先級）從未運作的程序中選擇下一個被執行的程序。但是這種模型是不合适的。當隊列中有正在等待事件的被阻塞的程序時，這個程序可能會因為不能執行而再次被放回隊尾，等到他解除阻塞時，他可能排在了新加入程序的後面，是以這種政策不會每次選擇在隊列中存在時間最久的程序。為解決這種情況的一種比較自然的方法是将未運作狀态分成兩個狀态：就緒态 和 阻塞态。另外還可以增加兩個有用的狀态，建立态和退出态。
狀态圖：
五種狀态：
- 運作态
- 就緒态：程序做好了準備，有機會就開始執行
- 阻塞/等待态：程序在某些事件發生前不能執行，比如 I/O 操作完成
- 建立态：剛剛建立的程序，作業系統還沒有把他加入到可執行程序組中。通常是程序控制塊已經建立但是還沒有加載到記憶體中的新程序
- 退出态：作業系統從可執行程序組中釋放出的程序，或自身停止，或者是因為某種原因被取消
基于新的模型的新的程序隊列：
采用這種模型，分派器每次不在是采用先進先出的方式從就緒隊列中選取程序，而是搜尋整個就緒隊列，查找在隊列中未被阻塞且等待時間最久的程序來執行。
多級隊列
對于之前簡單的例子，上圖給出了各個狀态的轉化關系。基于這種模型，系統會維護兩個隊列。一個為就緒程序隊列，另一個為阻塞程序隊列。當作業系統打算選擇一個程序運作時，便從就緒程序隊列中選取一個執行。相應的，阻塞隊列放置正在等待事件的被阻塞的程序。當一個事件發生時，所有等待該事件的處于阻塞中的程序都被轉換到就緒隊列中。這種方案意味着，如果一個事件發生，那麼作業系統必須搜尋整個阻塞隊列來尋找等待這個事件的程序。在大型作業系統中，隊列中可能有幾百個甚至幾千個程序，是以擁有多個隊列将會很有效，一個事件可以對用一個隊列。
被挂起的程序
交換的需要
現在在之前模型的基礎上考慮再加入一種新的狀态——挂起态。
事實證明加入這一狀态是很有必要的。暫時假設作業系統未采用虛拟記憶體技術，由于 CPU 速度比 I/O 快很多，是以很常見的一種情況是所有的程序都已經執行到了等待 I/O 的指令并處于阻塞狀态，此時記憶體中全部是阻塞中的程序而沒有可執行的程序，CPU 是以處于空閑狀态（降低了計算機效率）。
一種解決方案是采用更大的記憶體以裝載更多的程序進而盡量避免這種情況的發生，但是這種方案有兩種缺陷。首先是記憶體的價格在達到兆和千兆位後價格會随之增加。另一方面是，程式對記憶體空間需求的增長速度要比記憶體價格下降的速度要塊。是以，更大的記憶體往往導緻更大的程序，而不是更多的程序。
另一種解決方案是采用__交換__，将記憶體中某一程序的一部分或者全部移動到磁盤中，并維護一個挂起隊列，進而使記憶體空間有更多的空餘以容納新的程序加入。
新加入的狀态
當作業系統已經執行了一個挂起操作，此時記憶體中有了空餘的空間，作業系統将有兩個選擇來利用這塊空間。一是容納一個建立的程序，二是調入一個以前被挂起的程式。顯然，通常比較傾向于調入一個以前被挂起的程序，給他提供服務，而不是增加系統中的負載總數。
但是這種方案也帶來了一個問題，所有的被挂起的程序在挂起時都處于阻塞态。很明顯，這時如果将一個被阻塞的程序放回記憶體沒有任何意義。是以我們需要更新之前的模型，新加入兩個狀态：
- 阻塞/挂起态：程序在外存中等待一個事件
- 阻塞/就緒态：程序在外存中，隻要被載入記憶體就可以執行
新的狀态轉換圖：
各個狀态之間的轉換原則暫且不表（: P）。
導緻程序挂起的原因
- 交換：作業系統需要釋放足夠多的記憶體空間，以調入并執行處于就緒态的程序
- 其他 OS 原因：作業系統可能挂起背景程序或工具程序，或者懷疑導緻問題的程序
- 互動式使用者請求：使用者可能希望挂起一個程式的執行，目的是為了調試，檢查并修改程式資料，或者與一個資源的使用進行連接配接。
- 定時：一個程序可能周期性的執行，而且可能在等待下一個時間間隔時被挂起
- 父程序請求：父程序可能會希望挂起後代程序的執行，以檢查或修改挂起的程序，或者協調不同後代程序之間的行為
程序描述
作業系統的控制結構
作業系統為了管理程序和資源，必須掌握關于每個程序和資源的目前狀态的資訊。普遍使用的方法是：作業系統構造并維護他所管理的每個實體的資訊表。比如記憶體表，I/O 表，檔案表和程序表。
程序控制結構
程序的位置
作業系統在管理和控制程序時，首先必須知道程序的位置，再者，它必須知道在管理時所必須的程序屬性（比如程序ID，程序狀态）。
一個程序的實體表示展現為在記憶體中的一塊資料，儲存着程序的程式（代碼）和資料。此外，程式的執行還涉及到用于跟蹤過程調用和過程間參數傳遞的棧。最後，與每個程序相關聯的還有作業系統用于控制程序的許多屬性。通常，這些屬性的集合稱為程序控制塊。
程式、資料、棧和屬性的集合稱作程序映像。
程序映像中的典型元素：
- 使用者資料：使用者空間中可修改部分，可包括程式資料、使用者棧區域和可修改的程式
- 使用者程式：将被執行的程式
- 系統棧：每個程序有一個或多個後進先出（LIFO）系統棧。棧用于儲存參數、過程調用位址和系統調用位址
- 程序控制塊：作業系統控制程序所需要的資料
程序映像的位置依賴于使用的記憶體管理方案。最簡單的情況就是它位于記憶體中的一塊連續的空間。考慮其他更為複雜的記憶體管理方案時程序映像的位置和實體組織将随之發生變化（比如虛拟記憶體隻載入程序的一部分到記憶體，分頁使得程序在記憶體中分布不一定連續等）。
程序屬性
複雜的多道程式設計系統需要關于每個程序 的大量資訊，如前所述，這些資訊可以儲存在程序控制塊中。
可以把程序控制資訊分成三類：
- 程序辨別資訊
- 處理器狀态資訊
- 程序控制資訊
關于處理器狀态資訊
處理器狀态資訊包括處理器寄存器的内容。當一個程序正在運作時，其資訊儲存在處理器中，當程序被中斷時，所有的寄存器資訊都必須儲存起來，使得程序恢複執行時這些資訊都可以被恢複。
具體包括：
- 使用者可見寄存器
- 控制和狀态寄存器
- 棧指針
- 排程和狀态資訊
- 資料結構
- 等等
關于辨別符
實際上在所有的作業系統中，對于程序辨別符，每個程序都被配置設定了一個唯一的__數字辨別符__。程序辨別符可以簡單辨別為主程序表中的一個索引（直接映射）。否則，必須有一個映射，使得作業系統可以根據程序辨別符定位相應的表（間接映射）。這個辨別符在其他地方也很有用，作業系統控制的許多其他表可以使用程序辨別符__交叉引用程序表__。
程序控制塊的作用
程序控制塊是作業系統中最重要的資料結構。每個程序控制塊包含作業系統所需要的關于程序的__所有資訊__。實際上，作業系統中的每個子產品，包括那些涉及排程、資源配置設定、中斷處理、性能監控和分析的子產品，都可能讀取和修改他們。可以說，資源控制塊集合定義了作業系統的狀态。
這其實也帶來了一個重要的設計問題，我們通路程序控制塊很容易，但是保護他們不被錯誤的修改确是個難題。具體表現為下面兩個方面。
- 一個例程中有錯誤，可能會破壞程序控制塊，進而破壞了系統對受影響程序的管理能力。
- 程序控制塊的結構或語義的設計變化可能會影響到作業系統中的許多子產品。
程序控制
執行模式
在繼續讨論作業系統管理程序的方式之前，需要區分通常與作業系統相關聯的以及與使用者程式相關聯的__處理器執行模式__。通常處理器提供至少兩種執行模式——特權态，非特權态。
特權态通常被稱為核心态，而非特權态通常被稱為使用者态。
使用兩種模式的__原因__是，他可以__保護__作業系統和重要的作業系統表（比如程序控制塊）不受使用者程式的幹擾。在核心态下，軟體具有對處理器以及所有指令、寄存器和記憶體的控制能力，這一級的控制對使用者程式不是必需的，并且安全起見也不是使用者程式可以通路的。
那麼，處理器是如何知道他正在處于什麼模式下執行以及如何改變這一模式的？
答案是 程式狀态字。程式狀态字（處理器中的一個寄存器）中有一位用于表示執行模式。當程式以使用者态運作時，程式狀态字被設定進而使處理器為使用者态，相應的核心态也是如此。
程序建立
之前提過了建立一個程序的事件和與程序相關的資料結構，現在将簡單的描述實際建立程序時包含的步驟。
步驟如下：
- 配置設定程序辨別符 此時，在主程序表中增加一個新表項，表中的每個新表項對應一個程序。
- 給程序配置設定空間
- 初始化程式控制塊
- 設定正确的連接配接
- 建立或擴充其他資料結構
程序切換
從表面上看，程序切換的功能是很簡單的。在某一時刻，有個正在運作的程序被中斷，作業系統指定另一個程序為運作态，并把控制權交給這個程序。但是這會引發若幹問題。首先，什麼事件觸發程序的切換？其次，模式切換和程序切換之間有什麼的差別？最後，為實作程序的切換，作業系統必須對他控制的各種資料結構做些什麼？
何時切換程序
程序切換可以在作業系統從目前正在運作的程序中獲得控制權的任何時刻發生。
首先考慮中斷：
- 時鐘中斷 時間片用盡
- I/O 中斷 程序狀态的切換（考慮五種程序狀态模型）導緻的程序切換
- 記憶體失效 記憶體失效的程序可能會被設定為阻塞态，作業系統有可能切換另一個程式執行
實際上，大多數作業系統區分兩種類型的系統中斷。一種稱為中斷，另一種稱為__陷阱__。前者與目前正在運作的程序無關的某種類型的外部事件相關。比如 I/O 信号。後者與目前正在運作的程序所産生的錯誤或異常條件相關。
對于陷阱而言，作業系統将根據錯誤的嚴重性決定将程序轉換為退出态，切換其他的程序執行，還是報告一條警告消息繼續執行。
模式切換
中斷階段是指令周期的一部分（即循環的出現）。在中斷階段，處理器檢查是否發生了中斷，這通過中斷信号來表示。如果沒有，處理器繼續取指令周期，即目前程序中的下一條指令。如果存在一條未處理的中斷，處理器需要做以下工作：
- 把程式計數器設定成中斷處理程式的開始位址（開始執行中斷處理程式）
- 從使用者态切換到核心态，使得中斷處理代碼可以包含有特權指令
當中斷發生後，被中斷的程序上下文儲存在被中斷的程序控制塊中。環境上下文必須包括稱作處理器狀态資訊的程序控制塊部分，這包括程式計數器（執行到了哪條指令）、其他處理器寄存器和棧資訊。以實作程序的恢複。
作業系統的執行
基于之前讨論過的事實：
- 作業系統與普通的計算機軟體以同樣的方式運作，也即他是由處理器執行的一個程式。
- 作業系統經常釋放控制權，并且依賴與處理器恢複控制權
我們将讨論作業系統在計算機中執行的方式。
無程序的核心
這種模式下，作業系統是作為所有的程序之外被執行的。作業系統有自己的記憶體區和系統棧，用于控制過程調用和傳回，進行中斷，程序排程。作業系統是作為一個在特權模式下工作的實體被執行。這種模式一般存在于許多老的作業系統中。
在使用者程序中執行
在較小的機器的作業系統中，常見的方法是在使用者程序的上下文中執行幾乎所有的作業系統軟體。其觀點是作業系統從根本上說是使用者調用的一組例程。在這種模式下，每個程序都包含作業系統，每個程序映像包括核心程式的程式、資料和棧區域（以共享記憶體的形式）。
基于程序的作業系統
基于程序的作業系統是将作業系統作為一組程序來實作。與其他選擇一樣，作為核心一部分的軟體在核心态下執行。不過在這種情況下，主要的核心函數被組織成獨立的程序，同樣，還可能有一些在任何程序之外的程序切換代碼。