預備知識

前驅圖

程式順序執行的特徵順序性順序執行封閉性獨佔資源可再現性只要程式執行環境和初始條件相同，重複執行時結果都相同

程式併發執行的特徵間斷性失去封閉性不可再現性因為程式併發執行時，是多個程式共享系統中的各種資源，因而這些資源的狀態是由多個程式來改變，致使程式的執行失去了封閉性。而程式一旦失去了封閉性也會導致其再失去可再現性。執行結果與併發程式的執行速度相關

程序的概念

非正式地說，程序是執行的程式。程序不只是程式程式碼，程式程式碼又稱為文字段或程式碼段。程序還包括當前活動（程式計數器的值、處理器暫存器的內容）。通常還包括程序堆疊（臨時資料）、資料段（全部變數）。還可能包括堆（程序執行時動態分配的記憶體）。

程序的特徵動態性程序有生命週期，最基本特徵。併發性可併發執行；引入程序的目的是為了使其程序實體能和其他程序實體併發執行獨立性程序實體是一個能獨立執行、獨立獲得資源和獨立接受排程的基本單位制約性程序間對資源的爭用而相互制約非同步性程序按照各自獨立的、不可預知的速度向前推進結構特徵程序=程式+資料+PCB

程序和程式的比較

程序是程式的一次執行過程，是一個動態實體，而程式是一個指令的集合，是靜態實體。程序具有生命週期，具有建立、執行和撤銷的過程，而程式一旦建立，可以永遠存在 。程序實體由程式段、資料段及程序控制塊組成。程序與程式之間不存在一一對應的關係，不同的程序可以對應相同的程式，一個程序中還可以同時呼叫多個程式。程序實體是一個能獨立執行的基本單位，可獨立獲得資源和獨立排程；而程式不能作為獨立的單位參加執行。程序可按非同步方式執行，程式不是執行實體，所以不可以非同步執行。

程序的狀態

就緒、執行、等待是三個基本狀態。

提交狀態後備狀態就緒狀態執行狀態等待狀態結束狀態

程序的掛起/解掛設定掛起/解掛的原因使用者需要：中間結果與預期不符。作業系統需要：系統某些功能故障。系統負荷過重 。父程序請求：修改或協調子程序 。對換的需要。

程序控制塊(PCB)

PCB是用以記錄與程序相關資訊的主存區，是程序存在的唯一標誌

具有相同狀態程序的PCB分別透過PCB中的連結字連結成一個佇列。

索引方式

系統根據所有程序狀態的不同，建立幾張索引表，並把索引表的首地址記錄在記憶體的專用單元中。

Linux PCB的例子

程序切換/上下文切換

切換CPU到另一個程序需要儲存當前程序狀態和恢復另一個程序的狀態，核心會將舊程序狀態儲存在PCB中，並載入排程新的程序。上下文切換的時間是純粹的開銷。有的處理器提供多個暫存器組，上下文切換隻需簡單改變當前暫存器組的指標（如果活動程序數量超過暫存器組的組數，系統仍要在暫存器和記憶體之間複製資料）。

程序的建立

程序圖

程序圖(有向樹)與前趨圖(有向無環圖)的2個區別：1、表示的含義不同；2、執行時處理不同：可併發執行

程序建立原語Creat()申請空白PCB為新程序分配資源初始化PCB新程序插入就緒佇列

父程序建立子程序

當一個程序建立子程序時，子程序會需要一定的資源。子程序可以直接從作業系統那獲得資源，也可以只從父程序那裡獲得資源子集。父程序可能要在子程序之間分配資源或共享資源。限制父程序只能使用父程序的資源，可以防止建立過多程序，導致系統超載。

父與子程序的執行可能父程序和子程序併發執行父程序等待，直到某個或某些子程序執行完畢新程序的地址空間的情況子程序完全複製父程序，擁有同樣的程式和資料子程序載入另一個新程式

Unix舉例fork()透過系統呼叫fork()建立新程序，新程序的地址空間複製了原來程序的地址空間。子程序和父程序都繼續執行fork()呼叫後的指令。但對於父程序，fork()返回子程序的程序標識。對於子程序，fork()返回0。exec()在呼叫fork()後，可以有個程序呼叫exec()，用新程式取代程序的地址空間（載入二進位制檔案到記憶體），並開始執行。wait()父程序建立子程序後，如果無事可做，就呼叫wait()把自己移除就緒佇列，直到子程序結束，wait()返回(可以獲得子程序的識別符號、退出狀態等資訊)，父程序從wait()的下一條指令開始繼續執行。

程序的終止

級聯終止

如果一個程序終止，那麼它的所有子程序也相應終止，稱為級聯終止。

殭屍程序

當一個程序終止時，作業系統會釋放它的資源，但是位與程序表中的條目還在，直到它的父程序呼叫wait()。因為程序表中包含了程序的退出狀態，當程序已經終止，但它的父程序還沒有呼叫wait()時，這樣的程序稱為殭屍程序。一旦父程序呼叫wait()，殭屍程序的程序識別符號和程序表中的條目就會被釋放。

孤兒程序

如果父程序沒有呼叫wait()就終止，它的子程序稱為孤兒程序。Linux和Unix的做法是，將init程序作為孤兒程序的父程序。init程序定期呼叫wait()，以便收集孤兒程序的退出狀態，釋放孤兒程序的識別符號和程序表條目。

程序間通訊

作業系統內的併發執行程式可以是獨立的，也可以是協作的，若是協作的，那麼就需要有一種程序間通訊(IPC)的機制。

生產者-消費者問題

程序通訊的型別

訊息傳遞對於較小數量的資料交換很有用，因為無需避免衝突。對於分散式系統，訊息傳遞也比共享記憶體更易實現。共享記憶體可能快於訊息傳遞，因為訊息傳遞的實現經常採用系統呼叫，需要消耗更多時間使核心介入。共享記憶體僅在建立共享記憶體區域使需要系統呼叫，建立後所有訪問都可作為常規記憶體訪問，無需藉助核心。

共享儲存器訊息傳遞

由作業系統提供機制，利用系統提供的通訊原語，以訊息或報文為單位進行資訊交換。

命名間接通訊同步快取管道通訊