作業系統原理第三章：程序

目錄

• 1 程序概念
• • 1.1 順序執行環境
  • 1.2 并發執行環境
  • 1.3 程序的定義
• 2 程序狀态
• 3 程序控制塊PCB
• • 3.1 程序控制塊PCB中的内容
  • 3.2 PCB的組織方式
• 4 作業系統排程
• 5 程序操作
• 6 建立程序
• 7 程序通信：共享存儲
• 8 程序通信：消息傳遞

1 程序概念

作業系統的基本特性是并發與共享，即在系統中同時存在幾個互相獨立的程式，他們交叉地運作，并共享資源，在這樣的過程中就會出現諸多問題，比如多個程式就要進行資源的競争，程式之間的合作和協同，程式之間的通信，要解決這些問題 ， 用程式的概念已經不能描述程式在記憶體中運作的狀态 ，必須引入新的概念程序。

1.1 順序執行環境

順序環境計算機系統隻有一個程式在運作，該程式獨占系統中所有資源，其執行不受外界影響，下圖是順序執行的兩個作業的執行過程圖：

順序執行的特征：

• 順序性：按照程式結構所指定的次序（可能有分支或循環）；
• 封閉性：獨占系統的資源；
• 可再現性：初始條件相同則結果相同。如：可通過空指令控制時間關系。

1.2 并發執行環境

并發環境一定時間内，實體機器上有兩個或兩個以上的程式同處于開始運作但尚未結束的狀态，并且次序不是事先确定的，如下圖所示：

并發執行的特征：

• 間斷(異步)性：“走走停停”，一個程式可能走到中途停下來，失去原有的時序關系；
• 失去封閉性：共享資源，受其他程式的控制邏輯的影響。如：一個程式寫到存儲器中的資料可能被另一個程式修改，失去原有的不變特征；
• 失去可再現性：失去封閉性導緻失去可再現性；外界環境在程式的兩次執行期間發生變化，失去原有的可重複特征。

例如：觀察者/報告者，有兩個循環程式A和B，它們共享一個變量N。程式A每執行一次時都要做

N＝N＋1

操作；程式B每執行一次時，都要做

print(N)

操作，然後再将N置成“0”，程式A和B以不同的速度運作。可能出現多報或漏報。（假定某時刻變量N的值為5）

• 程式執行為A->B：

  N=N+1

  在

  print(N)

  和

  N=0

  之前，

  N=6，N=6，N=0

  ；
• 程式執行為B->A：

  N=N+1

  在

  print(N)

  和

  N=0

  之後，

  N=5，N=0，N=1

  ；
• 程式執行為B->A->B：

  N=N+1

  在

  print(N)

  和

  N=0

  之間，

  N=5，N=6，N=0

  。

是以多道程式設計對作業系統提出了新的要求：

• 如何描述并發程式的執行：引入程序及其狀态；
• 如何實作并發程式運作：程序控制與排程；
• 如何處理資源的競争與程式間的合作：并發控制與通信；
• 如何解決死鎖：死鎖政策。

1.3 程序的定義

為了描述程式在并發執行時對系統資源的共享，我們需要一個描述程式執行時動态特征的概念，這就是程序，一個具有一定獨立功能的程式在一個資料集合上的一次動态執行過程，相比程式，程式是一個靜态的實體，而程序是一個動态的實體，引入多程序，提高了對硬體資源的使用率，但又帶來額外的空間和時間開銷，增加了作業系統的複雜性

一個程序包括如下内容：

• 程式代碼(Program code)；
• 目前活動(Current activity)；
• 相關資料(Related data)：棧、堆、資料段，棧通常是一些臨時資料，如函數參數，傳回位址，局部變量等，堆通常是程式運作時申請的動态記憶體，資料段通常是全局變量。

程序和程式的差別：

• 程序是動态的，程式是靜态的：程式是有序代碼的集合；程序是程式的執行。通常程序不可在計算機之間遷移；而程式通常對應着檔案、靜态和可以複制；
• 程序是暫時的，程式是永久的：程序是一個狀态變化的過程，程式可長久儲存；
• 程序與程式的組成不同：程序的組成包括程式、資料和程序控制塊（即程序狀态資訊）；
• 程序與程式的對應關系：通過多次執行，一個程式可對應多個程序；通過調用關系，一個程序可包括多個程式。

程序的特征：

• 結構特征：程序實體=程式段+相關的資料段+PCB；
• 動态性：程序的實質是程序實體的一次執行過程，是以動态性是程序的最基本的特征；
• 并發性：多個程序實體同存在于記憶體中，且能在一段時間内同時運作。是最重要的特征；
• 獨立性：指程序實體是一個能獨立運作、獨立配置設定資源和獨立接受排程的基本機關；
• 異步性：程序按各自獨立的、不可預知的速度向前推進。

程序描述資訊：

• 處于某種狀态（運作、就緒、等待）；
• 程序控制塊PCB（資料結構）；
• 程序的執行程式（一個可執行檔案）；
• 程序位于某個隊列(就緒、等待某事件隊列)；
• 占用某些系統資（記憶體，打開某些檔案、處理機、外設）。

2 程序狀态

程序在執行時，會不斷地改變其狀态，程序有以下的狀态：

• 建立(new)：建立程序，構造了程序辨別符，建立了 管理程序所需的表格；
• 就緒(ready)：程序等待配置設定處理器，存在于處理機排程隊列中的那些程序，它們已經準備就緒，一旦得到CPU，就立即可以運作（有多個程序處于此狀态），如程序所配置設定的時間片用完後，會用運作狀态轉換為就緒狀态，等待下一次配置設定時間片；
• 運作(running)：指令在執行，當程序由排程/分派程式分派後，得到CPU控制權，它的程式正在運作（在系統中，總隻有一個程序處于此狀态）；
• 等待(waiting)：程序等待某些事件發生，程序正在等待某個事件的發生（如等待I/O的完成），而暫停執行即使給它CPU時間，它也無法執行；
• 終止(terminated)：程序執行完畢，終止後程序移入該狀态，它不再有執行資格，表格和其它資訊暫時由輔助程式保留，如為處理使用者帳單而累計資源使用情況的帳務程式，當資料不再需要後，程序(和它的表格)被删除。

各個狀态之間的轉換關系如下圖所示：

3 程序控制塊PCB

上面說到程序有多種狀态，但作業系統該如何知曉目前程序的狀态呢，是以我們要把程序的狀态儲存下來，這裡就引入了一種描述程序資訊的資料結構-程序控制塊PCB(Process Control Block)：

• PCB (Process Control Block)一個專門的資料結構，系統用它來記錄程序的外部特征，描述程序的運動變化過程；
• PCB是程序管理和控制的最重要的資料結構，在建立程序時，建立PCB，并伴随程序運作的全過程，直到程序撤消而撤消，跟随程序的生命周期；
• PCB是系統感覺程序存在的唯一标志，程序與PCB是一一對應的，有一個程序就會有一個PCB，有一個PCB就會有一個程序；
• PCB經常被系統通路，如，排程程式、資源配置設定程式、中斷處理程式等，是以PCB應常駐記憶體。

3.1 程序控制塊PCB中的内容

程序控制塊PCB儲存了同程序有關的資訊，一般有下面這些必要内容：

• 程序狀态(Process state)：說明程序目前所處的狀态；
• 程式計數器(Program counter)：指向執行程式的下個指令的位址；
• CPU寄存器(CPU registers)：當程序因某種原因不能繼續占用CPU時（如:等待列印機），釋放CPU，這時就要将CPU的各種狀态資訊保護起來，為将來再次得到處理機恢複CPU的各種狀态，繼續運作；
• CPU排程資訊(CPU scheduling information)：包括CPU優先級，排程隊列指針等；
• 記憶體管理資訊(Memory-management information)：包括基址寄存器，界限寄存器以及頁表或段表等；
• 計賬資訊(Accounting information)：包括CPU時間，實際使用時間，作業或程序數量等；
• I/O狀态資訊(I/O status information)：包括配置設定給程序的I/O裝置清單，打開檔案清單等。

  

3.2 PCB的組織方式

系統把 PCB 組織在一起，并放在記憶體的固定區域，就構成了 PCB 表，PCB 表的個數決定了系統中最多可同時存在的程序個數，稱為系統的并發度，PCB表的組織方式有兩種：

• 連結方式：一般通過連結清單的方式；
• 索引方式：建立索引表。

4 作業系統排程

在作業系統中多個程式并發的執行，但在單CPU機器中隻有一個CPU，那麼到底由哪一個程式來使用CPU呢，這就是一個排程問題，程序一般會在下面這些隊列被排程：

• 作業隊列：在系統中的所有程序的集合；
• 就緒隊列：在主記憶體中的，就緒并等待執行的所有程序的集合；
• 裝置隊列：等待某一I/O裝置的程序隊列。

其實上面所講的程序狀态的變化，實際上是在這些隊列上不停的遷移，如下圖所示：

下圖是程序排程的描述圖：

在作業系統的排程分為不同級别的排程：

• 長程排程（或作業排程）：選擇可以進入就緒隊列的程序，也可以說是從外存中選擇進入記憶體的排程過程；
• 短程排程（或 CPU 排程）：選擇可被下一個執行并配置設定 CPU；
• 中程排程：為了緩和記憶體緊張的情況，将記憶體中處于阻塞狀态的程序換至外存上（ 挂起 ），降低多道程式的度。當這些程序重新具備運作條件時，再從外存上調入記憶體，如下圖所示：

  

在作業系統中程序可以分為兩類：

• I/O型程序：花費I/O 時間多于計算，許多短CPU處理；
• CPU 型程序：花費更多時間于計算，許多長CPU處理。

可以試想若是排程選擇的大多數都是I/O型程序，少數CPU 型程序，那麼各個程序會在CPU上執行短暫的時間後轉到 I/O 裝置上，此時 I/O 裝置就非常的忙碌，而CPU就相對空閑，反之CPU型的程序過多，也會造成CPU的忙碌，而I/O裝置的空閑，這顯然不是高效的排程方式

當程序在運作中發生了中斷，如I/O操作，那麼會執行CPU的切換。如下圖所示，在切換時要儲存當且 P C B 0 PCB_0 PCB0​的資訊，然後加入切換的 P C B 1 PCB_1 PCB1​資訊，然後運作完成後再恢複 P C B 0 PCB_0 PCB0​的資訊：

上述切換的過程，我們稱為上下文切換，當CPU切換至另一個程序時，系統必須儲存舊程序狀态并為新程序調入所保留的狀态，而上下文切換的時間開銷較重；在切換時，系統沒有做有用的工作，時間取決于硬體的支援

5 程序操作

• 程序是有生命周期的：産生、運作、暫停、終止。對程序的這些操作叫程序控制，對程序的操作如下圖所示；
• 程序控制的職責是對系統中程序實施有效的管理，它是CPU管理的一部分（還有程序同步、通信和排程）；
• 當系統允許多程序并發執行時，為了實作共享、協調并發程序的關系，處理機管理必須對程序實行有效的管理。

  

6 建立程序

程序建立的時機有以下幾種：

• 作業排程：批處理系統中，作業排程程式排程到某個作業以後，就把這個作業裝入記憶體，并配置設定必要的資源，建立程序，插入就緒隊列；
• 使用者登入：在分時系統中，使用者在終端鍵入登入指令後，若是合法使用者，系統建立一個程序，并插入就緒隊列；
• 提供服務：使用者向系統提出請求後，系統專門建立一個程序為使用者服務。如列印請求；
• 應用請求：應用程序的需要，由它自己建立一個新程序，使新程序以并發運作方式完成特定任務（輸入資料并将處理結果輸出到表格上）。

一個程序建立之後還可以建立程序，也就是父程序建立子程序，如此輪流建立程序下去，構成一個程序樹，典型UNIX系統中的程序樹如下圖所示：

關于資源共享問題，有如下三種情況：

• 父程序子程序共享所有的資源
• 子程序共享父程序資源的子集
• 父程序和子程序無資源共享

關于程序執行問題，有如下兩種情況：

• 父程序和子程序并發執行
• 父程序等待，直到子程序終止

關于程序位址空間問題，有如下兩種情況：

• 子女複制雙親
• 子女有一個程式被調入

7 程序通信：共享存儲

由生産者-消費者問題讨探程序之間是如何共享存儲，生産者-消費者問題是一類問題的抽象，它描述的是一類事物提供另一類事物所需的事物，比如某一個程序提供計算資料，另一個程序負責計算輸出結果，不提供資料就無法進行計算輸出，此時提供計算資料的程序就是生産者，負責計算輸出的程序就是消費者，如下圖所示，這個問題抽象出來的資料模型就是共享隊列：

8 程序通信：消息傳遞

消息傳遞是作業系統中的一個機制，能夠使程序之間進行消息傳遞，若P與Q要通信，需要建立通信連接配接，通過

send/receive

交換消息，通信鍊路的實作分為兩種，一種是實體上的通過電子線路的實作，另一種是邏輯上的實作，我們主要考慮的是邏輯上的實作連接配接的建立分為兩種：

• 直接通信：程序必須顯式的命名，如

  send (P, message)

  向程序P發消息，

  receive(Q, message)

  從程序Q收消息，這種情況下連接配接自動建立，連接配接精确的與一對在通信的程序相關，在每一對之間就存在一個連接配接，連接配接可以無向，但通常是雙向的，這種通信方式的缺點就是收子產品化限制，比如某個時候程序P名字被修改，那麼所有代碼都需要修改；

直接通信也有一個特殊的通信方式就是非對稱通信方式(asymmetric communication)，也就是說發送消息的時候是顯示命名的，但接收消息的時候不指明接收方

• 間接通信：程序雙方不是直接建立連接配接的，而是通過一個媒介，可以想象成一個信箱或端口，每個信箱都有一個唯一的ID，不管是發送消息還是接收消息，都是通過這個信箱來完成的，如

  send(A, message)

  為向信箱A發送消息，

  receive(A, message)

  為從信箱A接收消息，此時僅當程序共有一個信箱時連接配接才能建立，連接配接可同多個程序相關，每一對程序可共享多個通信連接配接，連接配接可是無向或雙向的，但是為了确定發送者和接受者的唯一性，間接通信允許一個連接配接最多同2個程序相關，并且隻允許一個時刻有一個程序執行接受操作，通過允許系統任意選擇接收者，發送者被通知誰是接收者，這樣發送方和接收方就被唯一的确定。

相應的對信箱也有對應的操作，如建立新的信箱，通過信箱發送和接收消息，通信結束後銷毀信箱等