【正文】 它破壞了程序的封閉性和可再現(xiàn)性，使得程序和計(jì)算不再一一對(duì)應(yīng)，而且由于資源共享和程序的并發(fā)執(zhí)行導(dǎo)致在各個(gè)程序活動(dòng)之間可能存在相互制約關(guān)系。為了準(zhǔn)確地描述程序的執(zhí)行過程，設(shè)計(jì)出高質(zhì)量的操作系統(tǒng)，就不能再用靜態(tài)的觀點(diǎn)，而應(yīng)該用動(dòng)態(tài)的觀點(diǎn)來刻畫程序。使用程序這一概念只能是簡(jiǎn)單、孤立、靜止地研究分析它們，而不能深刻地揭示它們之間的內(nèi)在活動(dòng)、相互聯(lián)系及狀態(tài)變化。因此，每個(gè)可以并發(fā)執(zhí)行的程序段，都可能會(huì)因外界條件的限制而不能運(yùn)行，被迫處于阻塞狀態(tài)。 ② 間接制約關(guān)系是由于兩個(gè)并發(fā)程序段由于競(jìng)爭(zhēng)使用同一資源引起的，得到資源的程序段可以繼續(xù)執(zhí)行，得不到資源的程序段就只好暫停等待，直至獲得可用資源時(shí)再繼續(xù)運(yùn)行。 ① 直接制約關(guān)系通常是在彼此之間有邏輯關(guān)系的兩個(gè)并發(fā)執(zhí)行的程序之間發(fā)生的，一般是由于各個(gè)程序段要求共享信息引起的。這就是說，系統(tǒng)中各個(gè)并發(fā)程序活動(dòng)具有獨(dú)立性的一面，但在兩個(gè)并發(fā)程序活動(dòng)之間有時(shí)也會(huì)有相互依賴和相互制約關(guān)系。像上例中的觀察者與報(bào)告者程序，它們各自完成獨(dú)立的工作，通過共享變量 n 又建立了相互依賴與制約關(guān)系。 ⑵ 并發(fā)程序間存在相互制約關(guān)系 資源共享和程序的并發(fā)執(zhí)行使得系統(tǒng)的工作情況變得錯(cuò)綜復(fù)雜，尤其表現(xiàn)在系統(tǒng)中并 發(fā)程序間的相互依賴和制約方面。如前所述，程序在順序執(zhí)行時(shí)，程序和“計(jì)算”之間保持一一對(duì)應(yīng)的關(guān)系，但在并發(fā)執(zhí)行時(shí)，一個(gè)并發(fā)程序可為多個(gè)用戶作業(yè)調(diào)用，而使該程序處于多個(gè)“執(zhí)行”過程中，從而形成了多個(gè)“計(jì)算”，這就是說，多個(gè)“計(jì)算’可能是在不同數(shù)據(jù)集上執(zhí)行同一程序，所以程序和“計(jì)算”不再一一對(duì)應(yīng)。 程序的并發(fā)執(zhí)行所表現(xiàn)出的特性說明以下兩個(gè)問題： ⑴ 程序和計(jì)算機(jī)執(zhí)行程序的活動(dòng)不再一一對(duì)應(yīng) 程序和計(jì)算機(jī)執(zhí)行程序的活動(dòng)是兩個(gè)概念，程序是指令的有序集合，是靜態(tài)的概念；而計(jì)算機(jī)執(zhí)行程序的活動(dòng)是指令序列在 CPU 上的執(zhí)行過程，或 CPU 按照程序執(zhí)行指令序列的過程。 ② 失去封閉性 程序在并發(fā)執(zhí)行時(shí)， 多個(gè)程序共享系統(tǒng)中的所有資源，因此這些資源的使用狀態(tài)將由多個(gè)程序改變，使程序運(yùn)行失去了封閉性。而 產(chǎn)生了如下一些新的特征： ① 間斷性 如果 并發(fā)執(zhí)行的程序與其 它 程序競(jìng)爭(zhēng)資源 失敗 而阻塞， 或 運(yùn)行 到 一個(gè)時(shí)間片 結(jié)束 ， 它都會(huì) 放棄 CPU，使自己無法繼續(xù)運(yùn)行下去，但是當(dāng)別的程序釋放資源，使它能獲得申請(qǐng)的資源并再次被調(diào)度選中時(shí)，它又能繼續(xù)運(yùn)行下去。 void observer(void) { while (1) { ? n=n+1； remainder of observer； } } void reporter(void) { while(TRUE) { ? print(n)； n=0； remainder of reporter； } } void main( ) 中國最大的管理資源中心 31 { parbegin(observer( ),reporter( ))。此時(shí)我們可以寫出如下程序，其中 parbegin 表示多個(gè)程序可以并發(fā)執(zhí)行。在一條單向行駛的公路上經(jīng)常有卡車通過。 圖 2 程序的并發(fā)執(zhí)行 程序的并發(fā)執(zhí)行，是否還能保持順序執(zhí)行時(shí)的特性呢？下面我們通過例子來說明程序并發(fā)執(zhí)行時(shí)的特性。此外從圖中可以看出： I2 與 Cl、 I3 與 C2 與 P I4 與 C3 與 中國最大的管理資源中心 30 P2是重疊的。在該例中 I1先于 Cl和 I2， Cl先于 Pl和 C2， Pl先于 P2， I2 先于 C2 和 I3，??。例如：輸入程序在完成第 i 個(gè)程序的輸入操作后，計(jì)算程序在對(duì)第 i 個(gè)程序進(jìn)行計(jì)算的同時(shí)，可再啟動(dòng)輸入程序，進(jìn)行第 i+1 個(gè)程序的輸入操作，這就使得第 i+1 個(gè)程序 的輸入操作和第 i 個(gè)程序的計(jì)算操作能并發(fā)執(zhí)行。在多道程序操作系統(tǒng)支持下，不但在多機(jī)系統(tǒng)中它可同時(shí)執(zhí)行多個(gè)不同的程序，即使是在單機(jī)系統(tǒng)中，從邏輯上或宏觀上看，多個(gè)程序也能并 發(fā)執(zhí)行 。 程序的并發(fā)執(zhí)行及其特性 現(xiàn)代計(jì)算機(jī)在 物理 設(shè) 計(jì)和邏輯設(shè)計(jì)中采用并行操作技術(shù)，使多種硬件設(shè)備能并行工作。所謂可再現(xiàn)性是指當(dāng)該程序重復(fù)執(zhí)行時(shí)，必將獲得相同的結(jié)果。 所謂順序性指的是 程序的各部分能夠嚴(yán)格地按程序所確定的邏輯次序順序地執(zhí)行。也 就是說， CPU 在執(zhí)行程序的兩個(gè)動(dòng)作之間如有停頓不會(huì)影響程序的執(zhí)行結(jié)果，如果程序的初始條件不變，當(dāng)重復(fù)執(zhí)行時(shí)，一定能得到相同的結(jié)果。 ③ 結(jié)果無關(guān)性。 ② 獨(dú)占資源。除了人為的干預(yù)造成機(jī)器暫時(shí)停頓外，前一動(dòng)作的結(jié)束就意味著后一動(dòng)作的開始。 圖 1 程序的順序執(zhí)行 由上述順序程序的執(zhí)行情況可以看出，程序的順序執(zhí)行具有如下特點(diǎn)： ① 順序性。在單道環(huán)境下，每一程序的這三個(gè)程序只能是一個(gè)接一個(gè)地順序執(zhí)行，也就是輸入、計(jì)算和打印三者串行工作，并且前一個(gè)程序結(jié)束后，才能執(zhí)行下一個(gè)程序。例如，用戶要求計(jì)算機(jī)完成一道程序的運(yùn)行時(shí)，通常先輸入用戶的程序和數(shù)據(jù)，然后運(yùn)行程序進(jìn)行計(jì)算，最后將結(jié)果打印出來 。掌握進(jìn)程通信、死鎖的概念 及其解決方法，了解 Linux中進(jìn)程的實(shí)現(xiàn)技術(shù)。 1. 程序的順序執(zhí)行及其特性 教學(xué)要點(diǎn)： 本章主要內(nèi)容是程序的并發(fā)執(zhí)行及進(jìn)程的概念，進(jìn)程的狀態(tài)及其轉(zhuǎn)換，進(jìn)程的同步與互斥，進(jìn)程通信與調(diào)度，進(jìn)程死鎖的概念及解決死鎖的方法，線程的概念及其實(shí)現(xiàn)， Linux中進(jìn)程的實(shí)現(xiàn)。 程序的并發(fā)執(zhí)行是在多道程序環(huán)境下完成的，而在單道程序工作環(huán)境中，程序是順序執(zhí)行的。我們目前使用的計(jì)算機(jī)幾乎都是單 CPU的機(jī)器，但是都能為我們同時(shí)完成幾件不同的工作，就是采用的CPU 分時(shí)原理。在單 CPU條件下同時(shí)運(yùn)行幾道程序，從宏觀上看，這幾道程序是同時(shí)向前推進(jìn)，但從微觀上觀察則是由單 CPU 按照時(shí)間段輪流執(zhí)行每個(gè)程序的一小段，使每個(gè)程序都運(yùn)行到程序的開始與結(jié)束之間的某一處。我們知 道，計(jì)算機(jī)為我們自動(dòng)地做某事，實(shí)際上是 CPU自動(dòng)執(zhí)行存放在內(nèi)存中的程序，同時(shí)做幾件事就是同時(shí)執(zhí)行幾道不同的程序。在我們使用計(jì)算機(jī)運(yùn)行程序的時(shí)候，時(shí)常會(huì)一邊聽著光盤上的音樂，一邊從網(wǎng)上下載著軟件，一邊還編輯著文本文件。本章就來闡述有關(guān)進(jìn)程的問題。 中國最大的管理資源中心 28 進(jìn)程管理 操作系統(tǒng)中最核心的概念是進(jìn)程，進(jìn)程是對(duì)正在運(yùn)行的程序的一種抽象，是資源分配和獨(dú)立運(yùn)行的基本單位，操作系統(tǒng)的所有內(nèi)容都是圍繞進(jìn)程展開的，操作系統(tǒng)的四大特征也是基于進(jìn)程而形成的。所以操作系統(tǒng)的學(xué)習(xí)者和設(shè)計(jì)者都要盡早地理解進(jìn)程。 1 進(jìn)程的概念 程序的并發(fā)執(zhí)行 現(xiàn)在所有的計(jì)算機(jī)都能同時(shí)做幾件事情。在某一時(shí)段同時(shí)發(fā)生幾件事的現(xiàn)象稱為并發(fā)。如果這幾道程序同時(shí)在不同的 CPU 上執(zhí)行，則稱之為“并行”，如果它們分時(shí)地運(yùn)行在同一個(gè) CPU 上則稱之為“并發(fā)”。從邏輯上講，這幾道程序都在運(yùn)行，但從 CPU的執(zhí)行軌跡上觀察，卻是輪流地為每個(gè)程序執(zhí)行一段時(shí)間，循環(huán)往復(fù)，直 到所有程序依次完成。因此，邏輯上的并行稱為“并發(fā)”。程序的這兩種不同的執(zhí)行方式，體現(xiàn)出不同的特性。 讀者應(yīng)重點(diǎn)掌握進(jìn)程及線程的概念及其狀態(tài)轉(zhuǎn)換，實(shí)現(xiàn)進(jìn)程同步與互斥的方法以及進(jìn)程的各種調(diào)度策略。 中國最大的管理資源中心 29 一個(gè)具有獨(dú)立功能的程序獨(dú)占 CPU運(yùn)行，直至得到最終結(jié)果的過程稱為程序的順序執(zhí)行。 假設(shè)系統(tǒng)中有 2個(gè)程序，而每個(gè)程序都由三個(gè)程序段 I、C、 P 組成，其中， I 表示從輸入機(jī)上讀入程序的信息， C 表示執(zhí)行程序的計(jì)算過程， P 表示在打印機(jī)上打印出程序的計(jì)算結(jié)果。執(zhí)行順序如圖 1所示。當(dāng)順序程序在 CPU 上執(zhí)行時(shí)， CPU嚴(yán)格地順序執(zhí)行程序規(guī)定的動(dòng)作，每個(gè)動(dòng)作都必須在前一動(dòng)作結(jié)束后才能開始。程序和計(jì)算機(jī)執(zhí)行程序的活動(dòng)嚴(yán)格一一對(duì)應(yīng)。程序在執(zhí)行過程中，獨(dú)占全部資源，除了初始狀態(tài)外，只有程序本身規(guī)定的動(dòng)作才能改變這些資源的狀態(tài)。程序的執(zhí)行結(jié)果與其執(zhí)行速度無關(guān)。 上述特點(diǎn)概括起來就是程序的順序性、封閉性和可再現(xiàn)性。 所謂封 閉性指的是程序一旦開始執(zhí)行，其計(jì)算結(jié)果就只取決于程序本身，除了人為改變機(jī)器運(yùn)行狀態(tài)或機(jī)器故障外，不受外界因素的影響。這給程序的調(diào)試帶來了很大的方便。硬件的并行操作技術(shù)為程序的并發(fā)執(zhí)行提供了物質(zhì)基礎(chǔ)。 對(duì)于任何一個(gè)程序 i，其輸入操作 Ii、計(jì)算操作 Ci、打印操作 Pi這三者必須順序執(zhí)行，但對(duì) n 個(gè)程序來說，則有可能并發(fā)執(zhí)行。圖 2 給出了輸入、計(jì)算、打印程序?qū)σ慌绦蜻M(jìn)行處理的執(zhí)行順序。這說明有些操作必須在其它操作之后執(zhí)行，另外有些操作卻可以并行地執(zhí)行。 多道程序的并發(fā)執(zhí)行大大地提高 了 系統(tǒng)的處理能力，改善了系統(tǒng)資源的利用效率。 設(shè)有觀察者和報(bào)告者并行工作。觀察者不斷觀察并對(duì)通過的卡車計(jì)數(shù)，報(bào)告者定時(shí)地將觀察者的計(jì)數(shù)值打印出來，然后將計(jì)數(shù)器重新清“ 0”。 int n=0。 } 由于觀察者和報(bào)告 者各自獨(dú)立地并行工作， n=n+1的操作，既可以在報(bào)告者的 print (n) 和 n=0操作之前，也可以在其后，還可以在 print (n) 和 n=0之間，即可能出現(xiàn)以下三種執(zhí)行序列： ① n=n+1； print(n) ； n=0； ② print(n) ； n=0 ； n=n+1； ③ print(n) ； n=n+1 ； n=0； 假設(shè)在開始某個(gè)循環(huán)之前， n 的值為 s，則在完成一個(gè)循環(huán)后，對(duì)上述三個(gè)執(zhí)行序列打印機(jī)打印的 n 值和執(zhí)行后的 n 值如下表所示： 表 1 執(zhí)行序列 ① ② ③ 打印的 值 s+1 s s 執(zhí)行后的值 0 1 0 由上表可見，由于觀察者和報(bào)告者的執(zhí)行速度不同，導(dǎo)致了計(jì)算結(jié)果的不同，這就是說，程序并發(fā)執(zhí)行已喪失了順序執(zhí)行所保持的封閉性和可再現(xiàn)性。這就 使 并發(fā)執(zhí)行的程序具有 執(zhí)行 — 暫停 — 執(zhí)行的活動(dòng)規(guī)律。 ③ 不可再現(xiàn)性 由于程序的并發(fā)執(zhí)行，打破了由某一道程序獨(dú)占系統(tǒng)資源時(shí)的封閉性，也必將導(dǎo)致失去程序執(zhí)行的可再現(xiàn)性。通常把計(jì)算機(jī)執(zhí)行程序的活動(dòng)，稱為“計(jì)算”，顯 然，“計(jì)算”是一個(gè)動(dòng)態(tài)的概念。例如在分時(shí)系統(tǒng)中，內(nèi)存中一個(gè)編譯程序的副本同時(shí)為幾個(gè)用戶作業(yè)編 中國最大的管理資源中心 32 譯時(shí)，該編譯程序的幾次執(zhí)行，便對(duì)應(yīng)了幾個(gè)“計(jì)算”。系統(tǒng)中各個(gè)并發(fā)程序的活動(dòng)都有一定的獨(dú)立性，它們分別提供一種用戶或系統(tǒng)功能，如各用戶作業(yè)的活動(dòng)各提供一種用戶需要的功能，它們之間相互獨(dú)立，而又有相互依賴和制約關(guān)系。又如，操作系統(tǒng)中對(duì) CPU 的調(diào)度和對(duì)各種外部設(shè)備的控制活動(dòng)，兩者之間基本上也是獨(dú)立的，各自提供一種系統(tǒng)功能。程序之間的 制約關(guān)系有兩種：直接制約關(guān)系和間接制約關(guān)系。例如，一個(gè)正在執(zhí)行的程序段需要另一程序段的計(jì)算結(jié)果，只有當(dāng)另一程序段在某一時(shí)刻送來計(jì)算結(jié)果時(shí)，正在執(zhí)行的程序段才能繼續(xù)執(zhí)行下去，否則它就一直等待，無法執(zhí)行。 正是因?yàn)樵谶@些可以并發(fā)執(zhí)行的程序段 之間，存在著某種相互制約的關(guān)系，所以每個(gè)程序段的運(yùn)行都與運(yùn)行環(huán)境密切相關(guān)，它不僅要受到其它程序段活動(dòng)的制約，而且還要依賴當(dāng)時(shí)系統(tǒng)資源的分配情況。這樣，對(duì)于這些可以并發(fā)執(zhí)行的程序段，只用“程序”這一概念就不能說明問題的本質(zhì)。因此，必須從變化的角度，動(dòng)態(tài)地分析研究這些可以并發(fā)執(zhí)行的程序段，真實(shí)地反映出系統(tǒng)的獨(dú)立性、并發(fā) 性、動(dòng)態(tài)性和相互制約性。為此，在操作系統(tǒng)中引入了“進(jìn)程”的概念?？傊绦蚧顒?dòng)不再處于一個(gè)封閉系統(tǒng)中，而出現(xiàn)了許多新的特征，即：獨(dú)立性、并發(fā)性、動(dòng)態(tài)性和相互制約性。為此， 20 世紀(jì) 60 年代中期MULTICS 系統(tǒng)的設(shè)計(jì)者和以 為首的 系統(tǒng)的設(shè)計(jì)者開始廣泛使用“進(jìn)程”（ process） 這一新概念來描述系統(tǒng)和用戶的程序活動(dòng)。但是，迄今為止，對(duì)這一概念尚無一個(gè)非常確切的、令人滿意的、統(tǒng)一的定義，不同的人，站在不同的角度，對(duì)進(jìn)程進(jìn)行了不同的描述，下面列舉幾個(gè)操作系統(tǒng)的權(quán)威人士對(duì)“ 進(jìn)程”所下的定義： ① 行為的一個(gè)規(guī)則叫做程序，程序在 CPU上執(zhí)行時(shí)所發(fā)生的活動(dòng)稱為進(jìn)程（ Dijkstra）。 ③ 進(jìn)程是這樣的計(jì)算部分，它可以與別的進(jìn)程并發(fā)執(zhí)行（ Madniek and Donovan）。 ⑤ 一個(gè)進(jìn)程是由偽 CPU 執(zhí)行的一個(gè)程序（ ）。為了強(qiáng)調(diào)進(jìn)程的并發(fā)性和動(dòng)態(tài)性，我們給進(jìn)程作如下定義：進(jìn)程是可并發(fā)執(zhí)行的程序在一個(gè)數(shù)據(jù)集合上的運(yùn)行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。由于進(jìn)程執(zhí)行時(shí)的間斷性，決定了進(jìn)程可能具 有多種狀態(tài)。 ① 運(yùn)行狀態(tài)。在單 CPU系統(tǒng)中，只有一個(gè)進(jìn)程處于運(yùn)行狀態(tài)；在多 CPU系統(tǒng)中，可以有多個(gè)進(jìn)程處于運(yùn)行狀態(tài)。進(jìn)程等待某種事件完成（例如，等待輸入 /輸出操作的完成）而暫時(shí)不能運(yùn)行的狀態(tài)。 ③ 就緒狀態(tài)。該進(jìn)程運(yùn)行所需的一切資源，除 CPU 以外，都得到滿足，但因 CPU個(gè)數(shù)少于進(jìn)程個(gè)數(shù)，所以該進(jìn)程不能運(yùn)行，而必須等待分配 CPU資源，一旦 獲得 CPU 就立即投入運(yùn)行。 進(jìn)程的各個(gè)狀態(tài)變遷如圖 3。處于就緒狀態(tài)的進(jìn)程，已具備了運(yùn)行的條件，但由于未能獲得 CPU，故仍然不能運(yùn)行。進(jìn)程調(diào)度程序根據(jù)調(diào)度算法把 CPU 分配給某個(gè)就緒進(jìn)程，建立該進(jìn)程運(yùn)行狀