程序的描述與控制

文章目錄

• ​​1. 程序的基本概念​​

• ​​1.1 程式的順序執行​​
• ​​1.2 程式的并發執行​​
• ​​1.3 程序的定義與特征​​
• ​​1.4 程序的狀态​​

• ​​1.4.1 程序的基本狀态​​
• ​​1.4.2 程序的挂起狀态​​

• ​​1.5 程序控制塊​​

• ​​2. 程序控制​​

• ​​2.1 作業系統核心​​
• ​​2.2 程序的建立​​
• ​​2.3 程序的終止​​
• ​​2.4 程序的阻塞和喚醒​​
• ​​2.5 程序的挂起與激活​​

• ​​3. 程序同步​​

• ​​3.1 程序同步的概念​​

• ​​3.1.1 兩種制約形式​​
• ​​3.1.2 臨界資源和臨界區​​
• ​​3.1.3 同步機制應遵循的規則​​

• ​​3.2 信号量機制​​
• ​​3.3 信号量的應用​​

• ​​4. 經典程序的同步問題​​

• ​​4.1 生産者——消費者問題​​
• ​​4.2 哲學家進餐問題​​
• ​​4.3 讀者——寫者問題​​

• ​​5. 管程機制​​

• ​​5.1 管程的定義​​
• ​​5.2 條件變量​​
• ​​5.3 利用管程解決生産者——消費者問題​​

• ​​6. 程序通信​​

• ​​6.1 程序通信的類型​​
• ​​6.2 消息緩沖隊列通信機制​​

• ​​7. 線程​​

• ​​7.1 線程的基本概念​​
• ​​7.2 線程的控制​​
• ​​7.3 核心支援線程和使用者級線程​​

1. 程序的基本概念

1.1 程式的順序執行

程式的順序執行是指若幹個程式或程式段之間必須嚴格按照某種先後次序來執行,僅目前一段程式或程式段執行完後,才能執行後面的程式或程式段。

程式的順序執行具有下列特征：

1. 順序性。處理機按照程式所規定的順序執行。
2. 封閉性。程式在執行時獨占系統的全部資源，是以，系統資源狀态的改變隻與執行的程式有關，而不受外界因素的影響。
3. 可再現性。隻要初試條件相同，一個程式的多次重複執行将得到相同的結果。

1.2 程式的并發執行

程式的并發執行是指兩個或兩個以上的程式或程式段在同一時間間隔内同時執行。

程式的并發執行極大地提高了資源使用率和系統吞吐量，同時也産生了不同于順序執行的新特征：

1. 間斷性。由于資源共享和互相合作，并發執行的程式間形成了互相制約的關系，導緻程式的運作過程出現“執行——暫停——執行”的現象。
2. 失去封閉性。程式在執行時與其它并發執行的程式共享系統的資源，是以，資源狀态的改變還與其他程式有關，即程式本身的執行環境受到外界程式的影響。
3. 不可再現性。同樣的初始條件，一個程式的多次重複執行可能會得到不同的結果。

1.3 程序的定義與特征

程式并發執行時産生的不可再現性，決定了通常的程式是不能參與并發執行的。為了使程式能夠正确地并發執行，并且可以對并發執行的程式加以描述和控制，作業系統中引入了程序的概念，用程序來表示一個并發執行的程式。

傳統OS中程序定義：程序是程序實體的運作過程，是系統進行資源配置設定和排程的一個獨立機關。

特征：

1. 動态性。程序是程式一次執行過程，是以是動态的，程序的動态性還表現在程序具有一定的生命期，它必須由建立而産生、由排程而執行、由撤銷而消亡。動态性是程序的一個最基本的特征。
2. 并發性。并發性是指多個程序實體同存于記憶體中，且能在一段時間内同時執行。隻有為程式建立程序後，多個程式才能正确地并發執行。并發是引入程序的目的，也是程序的另一個最基本的特征。
3. 獨立性。程序實體是一個能夠獨立運作、獨立配置設定資源和獨立接受排程的基本機關。
4. 異步性。程序可按各自獨立的、不可預知的速度向前推進。雖然程序具有異步性，但作業系統必須保證程序并發執行的結果是再現的。

1.4 程序的狀态

1.4.1 程序的基本狀态

1. 就緒狀态。程序已經獲得CPU以外的所有必要資源，隻要得到CPU，便可立即執行。
2. 執行狀态。程序已得到CPU，其程式正在CPU上執行。
3. 阻塞狀态。正在執行的程序因某種事件（如I/O請求）的發生而暫時無法繼續執行，隻有等相應事件完成後，才能去競争CPU。

對單個程序而言，任何時刻，它隻能處于三種基本狀态之一。對整個系統而言，每個時刻允許同時有多個程序處于就緒狀态，通常它們組成一個或多個就緒隊列；也允許同時有多個程序處于阻塞狀态，并将它們組成一個或多個阻塞隊列；但對執行狀态的程序，每個處理機最多隻允許有一個。

程序排程

時間片完

等待I/O操作或其他事件

I/O操作或其他事件完成

建立

就緒

執行

阻塞

終止

1.4.2 程序的挂起狀态

挂起實質是程序不能繼續執行，即使挂起後的程序處于就緒狀态，它也不能參與CPU競争。挂起常被用在程序的對換中，此時，挂起（即換出）程序可以騰出記憶體空間給就緒程序使用；挂起還可以用在其它場合，如用來調節系統的符合、友善使用者考查自己的運作程序或父程序考查子程序、友善作業系統檢查系統運作中的資源使用情況或進行記賬等。

挂起

激活

時間片用完

排程

I/O請求

I/O完成

挂起

激活

I/O完成

挂起

活動就緒

靜止就緒

執行

活動阻塞

靜止阻塞

1.5 程序控制塊

為了描述和控制程序的運作，構造的一種特殊資料結構——PCB。PCB 是程序實體的一個組成部分，在 PCB 中記錄了 OS 所需的、用于描述程序的目前情況以及控制程序的全部資訊。

PCB 的作用是将程式變成可并發執行的程序。系統根據 PCB 感覺到程序的存在，并通過 PCB 對程序進行控制，是以，PCB 是程序存在的唯一标志。

程序控制塊中通常包含以下資訊：

1. 程序辨別符。用于唯一辨別系統中的每個程序；缺點父子關系。
2. 處理機狀态。用于 CPU 切換時儲存現場資訊和恢複現場資訊。
3. 程序排程資訊。程序排程資訊主要包括程序狀态、優先級、等待和使用 CPU 的時間總和等資訊，用作程序排程和對換的依據。
4. 程序控制資訊。包括了程式和資料的位址、程序同步和通信資訊、資源清單和程序隊列指針等。

為了便于管理，系統通常用線性方式或連結方式或索引方式将這些 PCB 組織起來。

2. 程序控制

作業系統的核心通過原語​​1​​實作。

2.1 作業系統核心

現代作業系統一般将 OS 劃分為若幹層次，再将 OS 的不同功能，分别設定在不同的層次中。通常将一些與硬體緊密相關的子產品（如中斷處理程式等）、各種常用裝置的驅動程式以及運作頻率較高的子產品（如時鐘管理、程序排程和許多子產品所公用的一些基本操作），安排在緊靠硬體的軟體層次中，将它們常駐記憶體，這部分通常稱為 OS 核心。

為了使作業系統核心代碼和資料不會遭受使用者程式的破壞，通常将處理機的執行狀态分為系統态和使用者态兩種不同狀态：

1. 系統态：也叫管态或核心态，它具有較高的特權，能執行一切指令，通路所有寄存器和存儲區。
2. 使用者态：也叫目态，是一種具有較低特權的執行狀态，它隻能執行規定的指令，通路特定的寄存器區和存儲區。

通常，作業系統核心運作在系統态，而使用者程式都運作在使用者态。

2.2 程序的建立

導緻一個程序去建立另一個程序的典型事件有分時系統中的使用者登入和批處理系統中的作業排程。另外，應用程式本身也可以根據需要去建立新的程序。建立程序是通過建立原語完成的，被建立的程序稱作子程序，而建立子程序的程序稱作父程序。

程序建立原語的主要任務是建立 PCB。具體：先從 PCB 集合中申請一個空閑的 PCB，再為新程序配置設定記憶體等資源，并根據父程序提供的參數和配置設定到的資源情況來對 PCB 程序初始化，最後将新程序插入到就緒隊列。

2.3 程序的終止

實質是收回 PCB。具體：找到要終止程序的 PCB；若該程序正在執行，則終止它的執行，并設定重新排程标志；終止屬于該程序的所有子孫程序；釋放程序所擁有的全部資源；将終止程序移出它所在的隊列并收回 PCB。

2.4 程序的阻塞和喚醒

當正在執行的程序需要等待某種事件的完成或本身無新工作可做時，應調用阻塞原語将自己從執行狀态轉換成阻塞狀态。具體：停止程序的執行，将其狀态改為阻塞狀态，并把它的 PCB 插入相應的阻塞隊列，轉排程程式重新排程。當阻塞程序所等待的事件完成時，應調用喚醒原語将該程序的狀态從阻塞狀态換成就緒狀态。在阻塞隊列中移出該程序的 PCB，将其設定成就緒狀态，并把它插入就緒隊列。

2.5 程序的挂起與激活

具體：若程序處于活動阻塞狀态，則将它的狀态轉換成靜止阻塞狀态；否則，将它轉換成就緒狀态；将 PCB 複制到指定的記憶體區域供使用者或父程序考查；若挂起程序正在執行，則轉排程程式重新進行程序排程。如果挂起是為了對換，則在挂起程序時還必須将它換出到記憶體中。若程序處于禁止阻塞狀态，則将它轉換成活動阻塞狀态，否則将它裝換成活動就緒狀态；若程序轉換成活動就緒狀态，而系統又采用搶占排程政策，則應檢查該程序是否有權搶占CPU，若有則應進行程序排程。同樣，如果挂起是為了對換，則在激活被挂起的程序時還必須将它調入記憶體。

3. 程序同步

3.1 程序同步的概念

3.1.1 兩種制約形式

1. 間接互相制約。源于資源共享。
2. 直接互相制約。源于程序合作。

3.1.2 臨界資源和臨界區

在計算機中有許多資源一次隻能允許一個程序使用，如果多個程序同時使用這些資源，則有可能造成系統混亂，這些資源被稱作臨界資源。

每個程序中，通路臨界資源的那段代碼稱作臨界區。

3.1.3 同步機制應遵循的規則

1. 空閑讓進。臨界資源空閑時，應允許一個請求進入臨界區的程序立即進入自己的臨界區，以便有效地利用資源。
2. 忙則等待。當臨界資源正被通路時，其他要求進入臨界區的程序必須等待，以保證對臨界資源的互斥使用。
3. 有限等待。任何要求通路臨界資源的程序應能在有限的時間内進入自己的臨界區，以免“死等”。
4. 讓權等待。不能進入臨界區的程序應立即釋放CPU，以免“忙等”。

3.2 信号量機制

1. 整型信号量。
2. 記錄型信号量。

3.3 信号量的應用

1. 利用信号量實作前趨關系
2. 利用信号量實作互斥

4. 經典程序的同步問題

4.1 生産者——消費者問題

4.2 哲學家進餐問題

4.3 讀者——寫者問題

5. 管程機制

5.1 管程的定義

管程利用共享資料結構抽象地表示系統中的共享資源，并且将對該共享資料結構實施的特定操作定義為一組過程。換句話說，管程是由一組局部的共享變量、對局部變量進行操作的一組過程以及對局部變量進行初始化的語句序列構成的一個軟體子產品。

管程具有以下特點：

1. 管程内的局部變量隻能被局部于管程的過程所通路，反之亦然，即局部于管程内的過程隻能通路管程内的變量和形式參數。
2. 任何程序隻能通過調用管程提供的過程入口進入管程。
3. 任一時刻，最多隻能有一個程序在管程中執行。

5.2 條件變量

5.3 利用管程解決生産者——消費者問題

6. 程序通信

6.1 程序通信的類型

1. 共享存儲器系統。
2. 管道通信。
3. 消息傳遞系統。
4. 客戶機——伺服器系統。

1. 套接字。
2. 遠端過程調用和遠端方法調用。

6.2 消息緩沖隊列通信機制

1. 消息緩沖隊列通信機制中的資料結構。
2. 發送原語。
3. 接受原語。

7. 線程

7.1 線程的基本概念

7.2 線程的控制

7.3 核心支援線程和使用者級線程

1. 使用者級線程。使用者級線程僅存在于使用者空間中，與核心無關。就核心而言，它隻是管理正常的程序——即單線程程序，感覺不到使用者級線程的存在。使用者級線程的優點是不需要得到核心的支援。線程切換無須陷入核心，故切換開銷小。線程庫對使用者線程的排程算法與 OS 的排程算法無關，是以，線程庫可提供多種排程算法供應用程式選擇使用。但在純使用者級線程的系統中，對應用程式來講，當一個線程因為執行系統調用而阻塞時，将導緻對應程序中所有程序的阻塞，另外，使用者級線程無法享用多處理機系統中多個處理器帶來的好處。
2. 核心支援線程。核心支援線程是在核心空間實作的。核心為每個線程在核心空間中設定了一個線程控制塊，用來登記該線程的線程辨別符、寄存器值、狀态、優先級等資訊。所有對線程的操作，如建立、撤銷和切換等，都是通過系統功能調用核心中的相應處理程式完成的。核心支援線程克服了使用者級線程的兩個缺點，首先，核心可以把同一個程序中的多個線程排程到多個處理器中；其次，如果程序中的一個線程被阻塞，核心可以排程同一個程序中的另一個線程。它的另一個優點是核心本身也可以使用多線程的方式來實作。它的主要缺點是即使 CPU 在用一個程序内的多個線程之間切換，也需要陷入核心，是以，其速度和效率不如使用者級線程。
3. 組合方式。n(使用者級線程):1(核心線程)、1:1、n(使用者線程):m(核心線程)。

1. 原語是指由若幹條指令組成、用來實作某個特定操作的一個過程。原語的執行具有原子性，即原語在執行過程中不允許被中斷，通常常駐記憶體，且在系統态下執行。​​↩︎​​