【正文】 態(tài)性，我們給進(jìn)程作如下定義：進(jìn)程是可并發(fā)執(zhí)行的程序在一個數(shù)據(jù)集合上的運行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個獨立單位。 ③ 進(jìn)程是這樣的計算部分，它可以與別的進(jìn)程并發(fā)執(zhí)行（ Madniek and Donovan）。為此， 20 世紀(jì) 60 年代中期MULTICS 系統(tǒng)的設(shè)計者和以 為首的 系統(tǒng)的設(shè)計者開始廣泛使用“進(jìn)程”（ process） 這一新概念來描述系統(tǒng)和用戶的程序活動。為此，在操作系統(tǒng)中引入了“進(jìn)程”的概念。這樣，對于這些可以并發(fā)執(zhí)行的程序段，只用“程序”這一概念就不能說明問題的本質(zhì)。例如，一個正在執(zhí)行的程序段需要另一程序段的計算結(jié)果，只有當(dāng)另一程序段在某一時刻送來計算結(jié)果時，正在執(zhí)行的程序段才能繼續(xù)執(zhí)行下去，否則它就一直等待，無法執(zhí)行。又如，操作系統(tǒng)中對 CPU 的調(diào)度和對各種外部設(shè)備的控制活動，兩者之間基本上也是獨立的，各自提供一種系統(tǒng)功能。例如在分時系統(tǒng)中，內(nèi)存中一個編譯程序的副本同時為幾個用戶作業(yè)編 中國最大的管理資源中心 32 譯時，該編譯程序的幾次執(zhí)行，便對應(yīng)了幾個“計算”。 ③ 不可再現(xiàn)性 由于程序的并發(fā)執(zhí)行，打破了由某一道程序獨占系統(tǒng)資源時的封閉性，也必將導(dǎo)致失去程序執(zhí)行的可再現(xiàn)性。 } 由于觀察者和報告 者各自獨立地并行工作， n=n+1的操作，既可以在報告者的 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è)在開始某個循環(huán)之前， n 的值為 s，則在完成一個循環(huán)后，對上述三個執(zhí)行序列打印機打印的 n 值和執(zhí)行后的 n 值如下表所示： 表 1 執(zhí)行序列 ① ② ③ 打印的 值 s+1 s s 執(zhí)行后的值 0 1 0 由上表可見，由于觀察者和報告者的執(zhí)行速度不同，導(dǎo)致了計算結(jié)果的不同，這就是說，程序并發(fā)執(zhí)行已喪失了順序執(zhí)行所保持的封閉性和可再現(xiàn)性。觀察者不斷觀察并對通過的卡車計數(shù)，報告者定時地將觀察者的計數(shù)值打印出來，然后將計數(shù)器重新清“ 0”。 多道程序的并發(fā)執(zhí)行大大地提高 了 系統(tǒng)的處理能力，改善了系統(tǒng)資源的利用效率。圖 2 給出了輸入、計算、打印程序?qū)σ慌绦蜻M(jìn)行處理的執(zhí)行順序。硬件的并行操作技術(shù)為程序的并發(fā)執(zhí)行提供了物質(zhì)基礎(chǔ)。 所謂封 閉性指的是程序一旦開始執(zhí)行，其計算結(jié)果就只取決于程序本身，除了人為改變機器運行狀態(tài)或機器故障外，不受外界因素的影響。程序的執(zhí)行結(jié)果與其執(zhí)行速度無關(guān)。程序和計算機執(zhí)行程序的活動嚴(yán)格一一對應(yīng)。執(zhí)行順序如圖 1所示。 中國最大的管理資源中心 29 一個具有獨立功能的程序獨占 CPU運行，直至得到最終結(jié)果的過程稱為程序的順序執(zhí)行。程序的這兩種不同的執(zhí)行方式，體現(xiàn)出不同的特性。從邏輯上講，這幾道程序都在運行，但從 CPU的執(zhí)行軌跡上觀察，卻是輪流地為每個程序執(zhí)行一段時間，循環(huán)往復(fù)，直 到所有程序依次完成。在某一時段同時發(fā)生幾件事的現(xiàn)象稱為并發(fā)。所以操作系統(tǒng)的學(xué)習(xí)者和設(shè)計者都要盡早地理解進(jìn)程。本章就來闡述有關(guān)進(jìn)程的問題。我們知 道，計算機為我們自動地做某事，實際上是 CPU自動執(zhí)行存放在內(nèi)存中的程序，同時做幾件事就是同時執(zhí)行幾道不同的程序。我們目前使用的計算機幾乎都是單 CPU的機器，但是都能為我們同時完成幾件不同的工作，就是采用的CPU 分時原理。 1. 程序的順序執(zhí)行及其特性 教學(xué)要點： 本章主要內(nèi)容是程序的并發(fā)執(zhí)行及進(jìn)程的概念，進(jìn)程的狀態(tài)及其轉(zhuǎn)換，進(jìn)程的同步與互斥，進(jìn)程通信與調(diào)度，進(jìn)程死鎖的概念及解決死鎖的方法，線程的概念及其實現(xiàn)， Linux中進(jìn)程的實現(xiàn)。例如，用戶要求計算機完成一道程序的運行時，通常先輸入用戶的程序和數(shù)據(jù)，然后運行程序進(jìn)行計算，最后將結(jié)果打印出來 。 圖 1 程序的順序執(zhí)行 由上述順序程序的執(zhí)行情況可以看出，程序的順序執(zhí)行具有如下特點： ① 順序性。 ② 獨占資源。也 就是說， CPU 在執(zhí)行程序的兩個動作之間如有停頓不會影響程序的執(zhí)行結(jié)果，如果程序的初始條件不變，當(dāng)重復(fù)執(zhí)行時，一定能得到相同的結(jié)果。所謂可再現(xiàn)性是指當(dāng)該程序重復(fù)執(zhí)行時，必將獲得相同的結(jié)果。在多道程序操作系統(tǒng)支持下，不但在多機系統(tǒng)中它可同時執(zhí)行多個不同的程序，即使是在單機系統(tǒng)中，從邏輯上或宏觀上看，多個程序也能并 發(fā)執(zhí)行 。在該例中 I1先于 Cl和 I2， Cl先于 Pl和 C2， Pl先于 P2， I2 先于 C2 和 I3，??。 圖 2 程序的并發(fā)執(zhí)行 程序的并發(fā)執(zhí)行，是否還能保持順序執(zhí)行時的特性呢？下面我們通過例子來說明程序并發(fā)執(zhí)行時的特性。此時我們可以寫出如下程序，其中 parbegin 表示多個程序可以并發(fā)執(zhí)行。而 產(chǎn)生了如下一些新的特征： ① 間斷性 如果 并發(fā)執(zhí)行的程序與其 它 程序競爭資源 失敗 而阻塞， 或 運行 到 一個時間片 結(jié)束 ， 它都會 放棄 CPU，使自己無法繼續(xù)運行下去，但是當(dāng)別的程序釋放資源，使它能獲得申請的資源并再次被調(diào)度選中時，它又能繼續(xù)運行下去。 程序的并發(fā)執(zhí)行所表現(xiàn)出的特性說明以下兩個問題： ⑴ 程序和計算機執(zhí)行程序的活動不再一一對應(yīng) 程序和計算機執(zhí)行程序的活動是兩個概念，程序是指令的有序集合，是靜態(tài)的概念；而計算機執(zhí)行程序的活動是指令序列在 CPU 上的執(zhí)行過程，或 CPU 按照程序執(zhí)行指令序列的過程。 ⑵ 并發(fā)程序間存在相互制約關(guān)系 資源共享和程序的并發(fā)執(zhí)行使得系統(tǒng)的工作情況變得錯綜復(fù)雜，尤其表現(xiàn)在系統(tǒng)中并 發(fā)程序間的相互依賴和制約方面。這就是說，系統(tǒng)中各個并發(fā)程序活動具有獨立性的一面，但在兩個并發(fā)程序活動之間有時也會有相互依賴和相互制約關(guān)系。 ② 間接制約關(guān)系是由于兩個并發(fā)程序段由于競爭使用同一資源引起的，得到資源的程序段可以繼續(xù)執(zhí)行，得不到資源的程序段就只好暫停等待，直至獲得可用資源時再繼續(xù)運行。使用程序這一概念只能是簡單、孤立、靜止地研究分析它們，而不能深刻地揭示它們之間的內(nèi)在活動、相互聯(lián)系及狀態(tài)變化。 進(jìn)程定義 如上所述，在多道程序的環(huán)境下，程序的并發(fā)執(zhí)行代替了程序的順序執(zhí)行，它破壞了程序的封閉性和可再現(xiàn)性，使得程序和計算不再一一對應(yīng)，而且由于資源共享和程序的并發(fā)執(zhí)行導(dǎo)致在各個程序活動之間可能存在相互制約關(guān)系。進(jìn)程是現(xiàn)代操作系統(tǒng)中的一個最基本也是最重要的概念，掌握這個概念對于理解操作系統(tǒng)實質(zhì)，分析、設(shè)計操作系統(tǒng)都有其非常重要的意義。 ④ 順序進(jìn)程 (有時稱為任務(wù) )是一個程序與其數(shù)據(jù)集一道順序通過 CPU 的執(zhí)行所發(fā)生的活動（ Alan ）。 進(jìn)程狀態(tài)及其轉(zhuǎn)換 1. 進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換 有了進(jìn)程的概念，就可以用動態(tài)的觀點分析進(jìn)程的狀態(tài)變化及相互制約關(guān)系。進(jìn)程正在 CPU上運行的狀態(tài)，該進(jìn)程已獲得必要的資源，包括 CPU，該程序正在 CPU上運行。處于該狀態(tài)的 進(jìn)程不能參加競爭 CPU，因為此時即使分配給它 CPU，它也不能運行。在一個系統(tǒng)中，處于就緒狀態(tài)的進(jìn)程可能有多個，統(tǒng)稱排成一個隊列，稱為就緒隊列。對于單 CPU 系統(tǒng)而言，因為處于就緒狀態(tài)的進(jìn)程往往不止一個，同一時刻就緒 執(zhí)行 阻塞 中國最大的管理資源中心 34 只能有一個就緒進(jìn)程獲得 CPU。處于運行狀態(tài)的進(jìn)程申請新資源而又不能立即被滿足時，進(jìn)程狀態(tài)由運行變成阻塞。被阻塞的進(jìn)程在其被阻塞的原因獲得解除后，并不能立即投人運行，需要通過進(jìn)程調(diào)度程序統(tǒng)一調(diào)度才能獲得 CPU，于是將其狀態(tài)由阻塞狀 態(tài)變成就緒狀態(tài)繼續(xù)等待 CPU。這種狀態(tài)變化通常出現(xiàn)在分時操作系統(tǒng)中。 具有掛起狀態(tài) 的進(jìn)程狀態(tài)轉(zhuǎn)換 在許多系統(tǒng)中，進(jìn)程除了具有上述三種基本狀態(tài)以外，又增加了一些新狀態(tài)，其中最重要的是掛起狀態(tài)，引入掛起狀態(tài)的主要原因是內(nèi)存資源不足。當(dāng)進(jìn)程處于未被掛起的就緒狀態(tài)時，稱此為活動就緒狀態(tài)，當(dāng)用掛起原語將該進(jìn)程掛起后，該進(jìn)程便轉(zhuǎn)變?yōu)殪o止就緒狀態(tài)，處于靜止就緒狀態(tài)的進(jìn)程不再被調(diào)度執(zhí)行。處于靜止就緒狀態(tài)的進(jìn)程，若用激活原語激活后，該進(jìn)程將轉(zhuǎn)變?yōu)榛顒泳途w狀態(tài)。 進(jìn)程控制塊 由于多個程序并發(fā)執(zhí)行，各程序需要輪流使用 CPU， 當(dāng)某程序不在 CPU 上運行時，必須保留其被中斷的程序的現(xiàn)場，包括：斷點地址、程序狀態(tài)字、通用寄存器的內(nèi)容、堆棧內(nèi)容、 中國最大的管理資源中心 35 程序當(dāng)前狀態(tài)、程序的大小、運行時間等信息，以便程序再次獲得 CPU時，能夠正確執(zhí)行。 掛起 時間片到 激活 掛起 釋放 激活 釋放 掛起 圖 4 具有掛起狀態(tài)的進(jìn)程狀態(tài)變遷圖 在通常的操作系統(tǒng)中， PCB應(yīng)包含如下一些信息： ① 進(jìn)程標(biāo)識信息。有的系統(tǒng)只用其中之一。指出進(jìn)程當(dāng)前所處的狀態(tài)，作為進(jìn)程調(diào)度、分配 CPU的依據(jù)。 ⑤ 進(jìn)程現(xiàn)場保護(hù)區(qū)。這一部分指出資源需求、分配和控制信息。 這里給出的只是一般操作系統(tǒng)中 PCB所應(yīng)具有的內(nèi)容，不同操作系統(tǒng)的 PCB結(jié)構(gòu)是不同執(zhí)行 活動 阻塞 靜止 阻塞 活動 就緒 靜止 就緒 調(diào)度 請求 I/O 中國最大的管理資源中心 36 的，我們將在 8 節(jié)介紹 Linux系統(tǒng)的 PCB結(jié)構(gòu)。按線性方式組織 PCB的情況如圖 5。按索引方式組織 PCB的情況如圖 7。進(jìn)程的動態(tài)性不僅表現(xiàn)在“程序的執(zhí)行”， 而且還表現(xiàn)在它由創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行，由撤銷而消亡的生命周期。并發(fā)性是進(jìn)程的重要特性，也是操作系統(tǒng)的重要特性。 ④ 進(jìn)程具有獨立性。 進(jìn)程通常分為兩類，一類是系統(tǒng)進(jìn)程，另一類是用戶進(jìn)程。 PCB1 PCB2 PCB3 PCB4 PCB5 PCB6 PCB7 PCB8 PCB9 …… 執(zhí)行指針 就緒表指針 阻塞表指針 5 7 ?? 3 9 ?? 中國最大的管理資源中心 38 ④ 在進(jìn)程調(diào)度中，系統(tǒng)進(jìn)程的優(yōu)先級高于用戶進(jìn)程。通常允許一個進(jìn)程創(chuàng)建和控制另一個進(jìn)程，前者稱為父進(jìn)程，后者稱為子進(jìn)程，子進(jìn)程又可創(chuàng)建其子進(jìn)程，從而形成了一個樹形結(jié)構(gòu)的進(jìn)程家族，如圖 8所示。 ?? 圖 8 進(jìn)程家族結(jié)構(gòu)圖 在操作系統(tǒng)中，某些被進(jìn)程調(diào)用的操作，例如隊列操作、對信號燈的操作、檢查啟動外設(shè)操作等，一旦開始執(zhí)行，就不能被中斷，否則就會出現(xiàn)操作錯誤，造成系統(tǒng)混亂。 1. 創(chuàng)建進(jìn)程原語 通過創(chuàng)建原語完成創(chuàng)建一個新進(jìn)程的功能。前三種由系統(tǒng)內(nèi)核直接調(diào)用創(chuàng)建原語創(chuàng)建新進(jìn)程，后一種由用戶調(diào)用操作系統(tǒng)提供的系統(tǒng)調(diào)用完成創(chuàng)建任務(wù)，如 Linux中的 fork( )系統(tǒng)調(diào)用。這是因為一個程序段可能是幾個進(jìn)程的一部分，即可能有多個進(jìn)程共享該程序段。 4. 喚醒進(jìn)程原語 當(dāng)某進(jìn)程所需要的資源出現(xiàn)時，由釋放資源的進(jìn)程調(diào)用喚醒原語，喚醒等待該資源的進(jìn)程。但是，有時相互合作的進(jìn)程需要在某些確定的點上協(xié)調(diào)它們的工作，以各自的執(zhí)行結(jié)果為對方的執(zhí)行條件，從而限制各進(jìn)程的執(zhí)行速度，產(chǎn)生直接制約關(guān)系。把因間接制約而導(dǎo)致交替執(zhí)行的過程稱為進(jìn)程間的互斥。我們把某段時間內(nèi)只能允許一個進(jìn)程使用的資源稱為臨界資源。系統(tǒng)只能 讓它們按次序交替使用，而不能同時使用，即只有進(jìn)程 A執(zhí)行完 CS1 程序段釋放了 V之后，才允許 B 進(jìn)程執(zhí)行 CS2 程序段來使用 V，我們把公用變量 V 稱為臨界資源，把 CS1 和 CS2 這種必須互斥執(zhí)行的程序段稱為相對于臨界資源 V的臨界區(qū)。 互斥工具 進(jìn)程互斥可以用若干種方式實現(xiàn)，下面介紹兩種方式：硬件方式和軟件方式。但該方法代價太高，因為 CPU被限制于只能交替執(zhí)行程序，執(zhí)行效率明顯降低。 testset指令定義如下： boolean testset(int i) { if(i==0) { i=1。如果 i為 0，則用 1取代并返回 true，這可以表示臨界資源未被使用時，進(jìn)程占用臨界資源；如果 i為 1， i值不變，返回 false，這可以表示臨界資源已被使用時，進(jìn)程不能再占用臨界資源。 臨界區(qū)