【正文】 的概念，進(jìn)程的狀態(tài)及其轉(zhuǎn)換，進(jìn)程的同步與互斥，進(jìn)程通信與調(diào)度，進(jìn)程死鎖的概念及解決死鎖的方法，線程的概念及其實現(xiàn)， Linux中進(jìn)程的實現(xiàn)。 圖 1 程序的順序執(zhí)行 由上述順序程序的執(zhí)行情況可以看出，程序的順序執(zhí)行具有如下特點： ① 順序性。也 就是說， CPU 在執(zhí)行程序的兩個動作之間如有停頓不會影響程序的執(zhí)行結(jié)果，如果程序的初始條件不變，當(dāng)重復(fù)執(zhí)行時，一定能得到相同的結(jié)果。在多道程序操作系統(tǒng)支持下，不但在多機系統(tǒng)中它可同時執(zhí)行多個不同的程序，即使是在單機系統(tǒng)中，從邏輯上或宏觀上看，多個程序也能并 發(fā)執(zhí)行 。 圖 2 程序的并發(fā)執(zhí)行 程序的并發(fā)執(zhí)行，是否還能保持順序執(zhí)行時的特性呢？下面我們通過例子來說明程序并發(fā)執(zhí)行時的特性。而 產(chǎn)生了如下一些新的特征： ① 間斷性 如果 并發(fā)執(zhí)行的程序與其 它 程序競爭資源 失敗 而阻塞， 或 運行 到 一個時間片 結(jié)束 ， 它都會 放棄 CPU，使自己無法繼續(xù)運行下去，但是當(dāng)別的程序釋放資源，使它能獲得申請的資源并再次被調(diào)度選中時，它又能繼續(xù)運行下去。 ⑵ 并發(fā)程序間存在相互制約關(guān)系 資源共享和程序的并發(fā)執(zhí)行使得系統(tǒng)的工作情況變得錯綜復(fù)雜，尤其表現(xiàn)在系統(tǒng)中并 發(fā)程序間的相互依賴和制約方面。 ② 間接制約關(guān)系是由于兩個并發(fā)程序段由于競爭使用同一資源引起的，得到資源的程序段可以繼續(xù)執(zhí)行，得不到資源的程序段就只好暫停等待，直至獲得可用資源時再繼續(xù)運行。 進(jìn)程定義 如上所述，在多道程序的環(huán)境下，程序的并發(fā)執(zhí)行代替了程序的順序執(zhí)行，它破壞了程序的封閉性和可再現(xiàn)性，使得程序和計算不再一一對應(yīng)，而且由于資源共享和程序的并發(fā)執(zhí)行導(dǎo)致在各個程序活動之間可能存在相互制約關(guān)系。 ④ 順序進(jìn)程 (有時稱為任務(wù) )是一個程序與其數(shù)據(jù)集一道順序通過 CPU 的執(zhí)行所發(fā)生的活動（ Alan ）。進(jìn)程正在 CPU上運行的狀態(tài)，該進(jìn)程已獲得必要的資源，包括 CPU，該程序正在 CPU上運行。在一個系統(tǒng)中，處于就緒狀態(tài)的進(jìn)程可能有多個，統(tǒng)稱排成一個隊列，稱為就緒隊列。處于運行狀態(tài)的進(jìn)程申請新資源而又不能立即被滿足時，進(jìn)程狀態(tài)由運行變成阻塞。這種狀態(tài)變化通常出現(xiàn)在分時操作系統(tǒng)中。當(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í)行。 進(jìn)程控制塊 由于多個程序并發(fā)執(zhí)行，各程序需要輪流使用 CPU， 當(dāng)某程序不在 CPU 上運行時，必須保留其被中斷的程序的現(xiàn)場，包括：斷點地址、程序狀態(tài)字、通用寄存器的內(nèi)容、堆棧內(nèi)容、 中國最大的管理資源中心 35 程序當(dāng)前狀態(tài)、程序的大小、運行時間等信息，以便程序再次獲得 CPU時，能夠正確執(zhí)行。有的系統(tǒng)只用其中之一。 ⑤ 進(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的情況如圖 7。并發(fā)性是進(jìn)程的重要特性，也是操作系統(tǒng)的重要特性。 進(jìn)程通常分為兩類，一類是系統(tǒng)進(jìn)程，另一類是用戶進(jìn)程。通常允許一個進(jìn)程創(chuàng)建和控制另一個進(jìn)程，前者稱為父進(jìn)程，后者稱為子進(jìn)程，子進(jìn)程又可創(chuàng)建其子進(jìn)程，從而形成了一個樹形結(jié)構(gòu)的進(jìn)程家族，如圖 8所示。 1. 創(chuàng)建進(jìn)程原語 通過創(chuàng)建原語完成創(chuàng)建一個新進(jìn)程的功能。這是因為一個程序段可能是幾個進(jìn)程的一部分，即可能有多個進(jìn)程共享該程序段。但是，有時相互合作的進(jìn)程需要在某些確定的點上協(xié)調(diào)它們的工作，以各自的執(zhí)行結(jié)果為對方的執(zhí)行條件，從而限制各進(jìn)程的執(zhí)行速度，產(chǎn)生直接制約關(guān)系。我們把某段時間內(nèi)只能允許一個進(jìn)程使用的資源稱為臨界資源。 互斥工具 進(jìn)程互斥可以用若干種方式實現(xiàn)，下面介紹兩種方式：硬件方式和軟件方式。 testset指令定義如下： boolean testset(int i) { if(i==0) { i=1。 臨界區(qū) 中國最大的管理資源中心 42 bolt =0。 } 該指令交換一個寄存器和一個存儲器單元的內(nèi)容。 parbegin(P⑴ , P⑵ .... ,P(n))。 ? 可能發(fā)生餓死現(xiàn)象。 int turn。 while ( turn == 0) /* 什么也不做 */ flag [1] = true。當(dāng) P0希望進(jìn)入自己的臨界區(qū)時，它把自己的 flag置為 true，然后繼續(xù)檢查 P1的 flag，如果 P1的 flag為 false， P0可以立即進(jìn)入自己的臨界區(qū)，否則 P0檢查 turn，如果它發(fā)現(xiàn) turn=0，那么它知道自己該堅持進(jìn)入，從而周期性地檢查 Pl的 flag； Pl在某一點上將注意到應(yīng)把 turn賦為 0，隨后把其 flag 置為 false，允許 P0 進(jìn)入；在 P0 結(jié)束其臨界區(qū)后，把自己的 flag置為 false，釋放臨界區(qū)，并把 turn置為 1，從而把堅持進(jìn)入的權(quán)力轉(zhuǎn) 交給 P1。 臨界區(qū) flag [0] = false。 /* 其余部分 */。在這兩個原語中設(shè)置一個公共變量 X代表某個臨界資源的 狀態(tài)。這是因為任何想進(jìn)入臨界區(qū)的進(jìn)程都不能直接進(jìn)入，它們必須不停地循環(huán)檢查 X的值，等待 X 變?yōu)?0。 V操作原語定義如下： V（ S） { S++； if S=0 wakeup ( )； } 即：當(dāng)執(zhí)行 V操作時，表示進(jìn)程釋放資源，將信號燈變量 S的值加 1，如果 S≤ 0，則喚醒 S 信號量隊列隊首的阻塞進(jìn)程，將其狀態(tài)從阻塞狀態(tài)轉(zhuǎn)變到就緒狀態(tài)，執(zhí)行 V（ S）者繼續(xù)執(zhí)行。 我們再來看一個用 P/V操作解決進(jìn)程間同步問題的例子。用 P 原語申請資源時，可能引起調(diào)用進(jìn)程的等待，而用 V原語釋放資源時，則可能啟動某一等待進(jìn)程。 一個管程主要由三部分組成： ① 局部于該管程的共享數(shù)據(jù)，這些數(shù)據(jù)表示了相應(yīng)資源的狀態(tài)； ② 局部于該管程的一組操作過程，每個過程完成對上述數(shù)據(jù)的某種規(guī)定操作； ③ 對局部于該管程的數(shù)據(jù)的初始化。對于條件變量 x 有兩種操作： 和 ，其中 x 為條件變量。這里既存在合作同步問題，也存在臨界區(qū)互斥問題。 } } void consumer( ) /*消費者進(jìn)程 */ { while⑴ { P(full)； P(mutex)； product =buffer[j]； j=(j+1) % n； V(mutex)。 condition notfull, notempty 。 out =(out+l) % n。 } 由此可見，利用管程機制解決進(jìn)程同步問題，大大簡化了程序員的工作，減少了出錯機會，同時也可以避免死鎖的發(fā)生。 readcount++。 } } void writer( ) { while ⑴ { P(wsem)。隨后其它的讀者到來，這樣只要 有一個讀者活躍，隨后而來的讀者都被允許訪問數(shù)據(jù)庫。 P(rsem)。 readcount。 WRITE。 V(mrc)。 readcount++。假如每 2秒鐘來一個讀者，而 該 操作時間為 5 秒鐘，則寫者將永遠(yuǎn)不能訪問數(shù)據(jù)庫，或者說寫者發(fā)生了饑餓現(xiàn)象。 V(wsem)。 V(mutex)。顯然，如果有兩個甚至更多個讀者同時訪問這個可共享數(shù)據(jù)對象，那么任何一個讀者的訪問結(jié)果都 是正確的。 if 。 buffer [in]=nextp。 consume the product； } } void main( ) { parbegin (producer( ), consumer( ))。這是相互合作同步。 經(jīng)典同步問題 把同步問題歸納為幾個典型的范例，就是經(jīng)典的同步問題。因此管程就如同一堵圍墻把關(guān)于某個共享資源的抽象數(shù)據(jù)結(jié) 構(gòu)以及對這些數(shù)據(jù)施行特定操作的若干過程圍了起來。在同一時刻只允許一個進(jìn)程執(zhí)行 P 或 V操作。 P P2 之間存在互斥關(guān)系（兩個進(jìn)程不能同時對緩沖區(qū)進(jìn)行操作），也存在同步關(guān)系（一個進(jìn)程的能否執(zhí)行與另一個進(jìn)程密切相關(guān)）。 P/V 操作的物理解釋是：信號燈變量 S 可以表示某類臨界資源，其值可以看作是可用資源數(shù)，執(zhí) 行一次 P 操作，相當(dāng)于申請一個資源，執(zhí)行一次 V操作，相當(dāng)于釋放一個資源。 1965 年 引進(jìn) 了比 lock/unlock原語的更一般的形式 P/V操作來克服這種忙碌等待現(xiàn)象，大大地簡化了進(jìn)程的同步與互 斥。當(dāng) X=1 時，表示資源正在使用，于是返回繼續(xù)進(jìn)行檢查；當(dāng) X=0時，表示資源可以使用，則置 X 為 1（關(guān)鎖）。 考慮進(jìn)程 P0，一旦它把 flag[0]置為 true， Pl不能進(jìn)入其臨界區(qū)；如果 P1已經(jīng)在臨界區(qū)中，則flag[1]=true，且 P0 被阻止進(jìn)入臨界區(qū)。 } } void P1( ) { while (true) { flag [1] = true。 中國最大的管理資源中心 45 int turn。 flag[1]= false。 while (flag[1]) if(turn==l) { flag[0] = false。 ? 可能發(fā)生死鎖現(xiàn)象。進(jìn)程離開臨界區(qū)時，它把 bolt重置為 0，允許另一個進(jìn)程進(jìn)入臨界區(qū)。 用 exchange指令實現(xiàn)互斥舉例： const int n = / * 進(jìn)程數(shù) * / int bolt。 parbegin (P⑴ , P⑵ ? , P(n))。 } else return false。進(jìn)程可以通過下面的方法實現(xiàn)互斥。我們把訪問臨界資源的代碼段稱為臨界區(qū)。另外，還有一些進(jìn)程由于共享某一公有資源，而這類資源對于不同的進(jìn)程必須交叉使用，如打印機，當(dāng)一個進(jìn)程正在使用時，另一個進(jìn)程必須等待，這就產(chǎn)生間接制約關(guān) 系。其實現(xiàn)過程是：首先中斷 CPU，停止進(jìn)程運行， 將 CPU 的現(xiàn)行狀態(tài)存放到 PCB 的 CPU 狀態(tài)保護(hù)區(qū)中，然后將該進(jìn)程置阻塞狀態(tài)，并把它插入到等待隊列中。所以，創(chuàng)建一個新進(jìn)程的過程是：首先申請 PCB空間，根據(jù)建立的進(jìn)程名字查找 PCB表，若找到了則非正常終止 (即已有同名進(jìn)程 )，否則，申請分配一塊 PCB 空間；其次，為新進(jìn)程分配資源，若進(jìn)程的程序或數(shù)據(jù)不在內(nèi)存中，則應(yīng)將它們從外存調(diào)入分配的內(nèi)存中；然后把有關(guān)信息 (如進(jìn)程名字、信號量和狀態(tài)位等 )分別填入 PCB 的相應(yīng)欄目中；最后把 PCB 插入到就緒隊列中。 進(jìn)程的控制通常由原語完成。 ② 系統(tǒng)進(jìn)程之間的關(guān)系由操作系統(tǒng)自己負(fù)責(zé)， 這樣有利于增加系統(tǒng)的并行性，提高資源的利用率；用戶進(jìn)程之間的關(guān)系主要由用戶自己負(fù)責(zé)，為了便于用戶管理自己的任務(wù)，操作系統(tǒng)提供一套簡便的任務(wù)調(diào)用命令作為協(xié)調(diào)手段，并 在用戶區(qū)根據(jù)用戶作業(yè)的性質(zhì)（是單任務(wù)還是多任務(wù)）裝入相應(yīng)的任務(wù)調(diào)度程序 。 ③ 進(jìn)程具有結(jié)構(gòu)特性。 ① 進(jìn)程具有動態(tài)性。目前常用的 PCB的組織方式有以下三種： ① 線性表方式：不論進(jìn)程的狀態(tài)如何，將所有的 PCB 連續(xù)地存放在內(nèi)存的系統(tǒng)區(qū)。 ⑥ 資源清單。指出 進(jìn)程的程序和數(shù)據(jù)部分在內(nèi)存或外存中的物理位置。 進(jìn)程控制塊是進(jìn)程存在