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