【正文】 ) 根據(jù)被終止進(jìn)程的標(biāo)識(shí)符 ， 從 PCB集合中檢索出該進(jìn)程的 PCB， 從中讀出該進(jìn)程的狀態(tài) 。 (2) 若被終止進(jìn)程正處于執(zhí)行狀態(tài) ， 應(yīng)立即終止該進(jìn)程的執(zhí)行 ， 并置調(diào)度標(biāo)志為真 ， 用于指示該進(jìn)程被終止后應(yīng)重新進(jìn)行調(diào)度 。 (3) 若該進(jìn)程還有子孫進(jìn)程 ， 還應(yīng)將其所有子孫進(jìn)程予以終止 ， 以防他們成為不可控的進(jìn)程 。 (4) 將被終止進(jìn)程所擁有的全部資源 ， 或者歸還給其父進(jìn)程 ， 或者歸還給系統(tǒng) 。 (5) 將被終止進(jìn)程 (它的 PCB)從所在隊(duì)列 (或鏈表 )中移出， 等待其他程序來搜集信息。 3 進(jìn)程的阻塞與喚醒 1. 引起進(jìn)程阻塞和喚醒的事件 1) 請(qǐng)求系統(tǒng)服務(wù) 2) 啟動(dòng)某種操作 3) 4) 正在執(zhí)行的進(jìn)程 ， 當(dāng)發(fā)現(xiàn)上述某事件時(shí) ， 由于無法繼續(xù)執(zhí)行 ， 于是進(jìn)程便通過調(diào)用阻塞原語 block把自己阻塞 。 可見 ，進(jìn)程的阻塞是進(jìn)程自身的一種主動(dòng)行為 。 進(jìn)入 block過程后 ，由于此時(shí)該進(jìn)程還處于執(zhí)行狀態(tài) ， 所以應(yīng)先立即停止執(zhí)行 ，把進(jìn)程控制塊中的現(xiàn)行狀態(tài)由 “ 執(zhí)行 ” 改為阻塞 ， 并將 PCB插入阻塞隊(duì)列 。 如果系統(tǒng)中設(shè)置了因不同事件而阻塞的多個(gè)阻塞隊(duì)列 ， 則應(yīng)將本進(jìn)程插入到具有相同事件的阻塞 (等待 )隊(duì)列 。 最后 ， 轉(zhuǎn)調(diào)度程序進(jìn)行重新調(diào)度 ， 將處理機(jī)分配給另一就緒進(jìn)程 ， 并進(jìn)行切換 ， 亦即 ， 保留被阻塞進(jìn)程的處理機(jī)狀態(tài) (在PCB中 )， 再按新進(jìn)程的 PCB中的處理機(jī)狀態(tài)設(shè)置 CPU的環(huán)境 。 3. 當(dāng)被阻塞進(jìn)程所期待的事件出現(xiàn)時(shí) ， 如 I/O完成或其所期待的數(shù)據(jù)已經(jīng)到達(dá) ， 則由有關(guān)進(jìn)程 (比如 ， 用完并釋放了該 I/O設(shè)備的進(jìn)程 )調(diào)用喚醒原語 wakeup( )， 將等待該事件的進(jìn)程喚醒 。 喚醒原語執(zhí)行的過程是：首先把被阻塞的進(jìn)程從等待該事件的阻塞隊(duì)列中移出 ， 將其 PCB中的現(xiàn)行狀態(tài)由阻塞改為就緒 ， 然后再將該 PCB插入到就緒隊(duì)列中 。 4 進(jìn)程的掛起與激活 1. 當(dāng)出現(xiàn)了引起進(jìn)程掛起的事件時(shí) ， 比如 ， 用戶進(jìn)程請(qǐng)求將自己掛起 ， 或父進(jìn)程請(qǐng)求將自己的某個(gè)子進(jìn)程掛起 ， 系統(tǒng)將利用掛起原語 suspend( )將指定進(jìn)程或處于阻塞狀態(tài)的進(jìn)程掛起 。 掛起原語的執(zhí)行過程是：首先檢查被掛起進(jìn)程的狀態(tài) ， 若處于活動(dòng)就緒狀態(tài) ， 便將其改為靜止就緒；對(duì)于活動(dòng)阻塞狀態(tài)的進(jìn)程 ， 則將之改為靜止阻塞 。 為了方便用戶或父進(jìn)程考查該進(jìn)程的運(yùn)行情況而把該進(jìn)程的 PCB復(fù)制到某指定的內(nèi)存區(qū)域 。 最后 ， 若被掛起的進(jìn)程正在執(zhí)行 ， 則轉(zhuǎn)向調(diào)度程序重新調(diào)度 。 進(jìn)程的激活過程 當(dāng)發(fā)生激活進(jìn)程的事件時(shí) ， 例如 ， 父進(jìn)程或用戶進(jìn)程請(qǐng)求激活指定進(jìn)程 ， 若該進(jìn)程駐留在外存而內(nèi)存中已有足夠的空間時(shí) ， 則可將在外存上處于靜止就緒狀態(tài)的進(jìn)程換入內(nèi)存 。這時(shí) ， 系統(tǒng)將利用激活原語 active( )將指定進(jìn)程激活 。 激活原語先將進(jìn)程從外存調(diào)入內(nèi)存 ， 檢查該進(jìn)程的現(xiàn)行狀態(tài) ， 若是靜止就緒 ， 便將之改為活動(dòng)就緒；若為靜止阻塞便將之改為活動(dòng)阻塞 。 假如采用的是搶占調(diào)度策略 ， 則每當(dāng)有新進(jìn)程進(jìn)入就緒隊(duì)列時(shí) ， 應(yīng)檢查是否要進(jìn)行重新調(diào)度 ， 即由調(diào)度程序?qū)⒈患せ钸M(jìn)程與當(dāng)前進(jìn)程進(jìn)行優(yōu)先級(jí)的比較 ， 如果被激活進(jìn)程的優(yōu)先級(jí)更低 ， 就不必重新調(diào)度；否則 ， 立即剝奪當(dāng)前進(jìn)程的運(yùn)行 ， 把處理機(jī)分配給剛被激活的進(jìn)程 。 3 進(jìn) 程 同 步 進(jìn)程同步的基本概念 1. 兩種形式的制約關(guān)系 (1) 間接相互制約關(guān)系。 (2) 直接相互制約關(guān)系。 臨界資源 (Critical Resouce) 生產(chǎn)者 消費(fèi)者 (producerconsumer)問題是一個(gè)著名的進(jìn)程同步問題 。 它描述的是：有一群生產(chǎn)者進(jìn)程在生產(chǎn)產(chǎn)品 ，并將這些產(chǎn)品提供給消費(fèi)者進(jìn)程去消費(fèi) 。 為使生產(chǎn)者進(jìn)程與消費(fèi)者進(jìn)程能并發(fā)執(zhí)行 ， 在兩者之間設(shè)置了一個(gè)具有 n個(gè)緩沖區(qū)的緩沖池 ， 生產(chǎn)者進(jìn)程將它所生產(chǎn)的產(chǎn)品放入一個(gè)緩沖區(qū)中； 消費(fèi)者進(jìn)程可從一個(gè)緩沖區(qū)中取走產(chǎn)品去消費(fèi) 。 盡管所有的生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程都是以異步方式運(yùn)行的 ，但它們之間必須保持同步 ， 即不允許消費(fèi)者進(jìn)程到一個(gè)空緩沖區(qū)去取產(chǎn)品；也不允許生產(chǎn)者進(jìn)程向一個(gè)已裝滿產(chǎn)品且尚未被取走的緩沖區(qū)中投放產(chǎn)品 。 我們可利用一個(gè)數(shù)組來表示上述的具有 n個(gè) (0， 1， …， n1)緩沖區(qū)的緩沖池 。 用輸入指針 in來指示下一個(gè)可投放產(chǎn)品的緩沖區(qū) ， 每當(dāng)生產(chǎn)者進(jìn)程生產(chǎn)并投放一個(gè)產(chǎn)品后 ， 輸入指針加 1；用一個(gè)輸出指針 out來指示下一個(gè)可從中獲取產(chǎn)品的緩沖區(qū) ， 每當(dāng)消費(fèi)者進(jìn)程取走一個(gè)產(chǎn)品后 ， 輸出指針加 1。 由于這里的緩沖池是組織成循環(huán)緩沖的 ， 故應(yīng)把輸入指針加1表示成 in∶ =(in+1)mod n；輸出指針加 1表示成 out∶ =(out+1) mod n。 當(dāng) (in+1) mod n=out時(shí)表示緩沖池滿；而 in=out則表示緩沖池空 。 此外 ， 還引入了一個(gè)整型變量 counter, 其初始值為 0。 每當(dāng)生產(chǎn)者進(jìn)程向緩沖池中投放一個(gè)產(chǎn)品后 ， 使counter加 1；反之 ， 每當(dāng)消費(fèi)者進(jìn)程從中取走一個(gè)產(chǎn)品時(shí) ， 使 counter減 1。 生產(chǎn)者和消費(fèi)者兩進(jìn)程共享下面的變量： Var n, integer。 type item=…。 var buffer:array［ 0, 1, …, n1］ of item。 in, out: 0, 1, …, n1。 counter: 0, 1, …, n。 指針 in和 out初始化為 1。 在生產(chǎn)者和消費(fèi)者進(jìn)程的描述中 ， noop是一條空操作指令 ， while condition do noop語句表示重復(fù)的測試條件 (condication)， 重復(fù)測試應(yīng)進(jìn)行到該條件變?yōu)?false(假 )， 即到該條件不成立時(shí)為止 。 在生產(chǎn)者進(jìn)程中使用一局部變量 nextp， 用于暫時(shí)存放每次剛生產(chǎn)出來的產(chǎn)品；而在消費(fèi)者進(jìn)程中 ， 則使用一個(gè)局部變量 nextc,用于存放每次要消費(fèi)的產(chǎn)品 。 producer: repeat … produce an item in nextp。 … while counter=n do noop。 buffer［ in ∶ = nextp。 in ∶ = in+1 mod n。 counter ∶ = counter+1。 until false。 consumer: repeat while counter=0 do noop。 nextc ∶ = buffer［ out］ 。 out ∶ = (out+1) mod n。 counter ∶ = counter1。 consumer the item in nextc。 until false。 雖然上面的生產(chǎn)者程序和消費(fèi)者程序 ， 在分別看時(shí)都是正確的 ， 而且兩者在順序執(zhí)行時(shí)其結(jié)果也會(huì)是正確的 ， 但若并發(fā)執(zhí)行時(shí) ， 就會(huì)出現(xiàn)差錯(cuò) ， 問題就在于這兩個(gè)進(jìn)程共享變量 counter。 生產(chǎn)者對(duì)它做加 1操作 ， 消費(fèi)者對(duì)它做減 1操作 ，這兩個(gè)操作在用機(jī)器語言實(shí)現(xiàn)時(shí) ， ?？捎孟旅娴男问矫枋觯? register 1 ∶ = counter。 register 2∶ = counter。 register1 ∶ = register 1+1。 register 2∶ = register 21。 counter ∶ = register 1。 counter ∶ = register 2。 假設(shè)： counter的當(dāng)前值是 5。 如果生產(chǎn)者進(jìn)程先執(zhí)行左列的三條機(jī)器語言語句 ， 然后消費(fèi)者進(jìn)程再執(zhí)行右列的三條語句 ， 則最后共享變量 counter的值仍為 5；反之 ， 如果讓消費(fèi)者進(jìn)程先執(zhí)行右列的三條語句 ， 然后再讓生產(chǎn)者進(jìn)程執(zhí)行左列的三條語句 ， counter值也還是 5， 但是 ， 如果按下述順序執(zhí)行： register 1 ∶ = counter。 (register 1=5) register 1 ∶ = register 1+1。 (register 1=6) register 2 ∶ = counter。 (register 2=5) register 2 ∶ = register 21。 (register 2=4) counter ∶ = register 1。 (counter=6) counter ∶ = register 2。 (counter=4) 3. 臨界區(qū) (critical section) repeat critical section。 remainder section。 until false。 entry section exit section 4. 同步機(jī)制應(yīng)遵循的規(guī)則 (1) 空閑讓進(jìn)。 (2) 忙則等待。 (3) 有限等待。 (4) 讓權(quán)等待。 信號(hào)量機(jī)制 1. 最初由 Dijkstra把整型信號(hào)量定義為一個(gè)整型量 ， 除初始化外 ， 僅能通過兩個(gè)標(biāo)準(zhǔn)的原子操作 (Atomic Operation) wait(S)和 signal(S)來訪問 。 這兩個(gè)操作一直被分別稱為 P、 V操作 。 wait和 signal wait(S): while S≤0 do noop S ∶ =S1。 signal(S): S ∶ =S+1。 記錄型信號(hào)量 在整型信號(hào)量機(jī)制中的 wait操作 ， 只要是信號(hào)量 S≤0， 就會(huì)不斷地測試 。 因此 ， 該機(jī)制并未遵循 “ 讓權(quán)等待 ” 的準(zhǔn)則 ， 而是使進(jìn)程處于 “ 忙等 ” 的狀態(tài) 。 記錄型信號(hào)量機(jī)制 ， 則是一種不存在 “ 忙等 ” 現(xiàn)象的進(jìn)程同步機(jī)制 。 但在采取了 “ 讓權(quán)等待 ” 的策略后 ， 又會(huì)出現(xiàn)多個(gè)進(jìn)程等待訪問同一臨界資源的情況 。 為此 ， 在信號(hào)量機(jī)制中 ， 除了需要一個(gè)用于代表資源數(shù)目的整型變量 value外 ， 還應(yīng)增加一個(gè)進(jìn)程鏈表 L， 用于鏈接上述的所有等待進(jìn)程 。 記錄型信號(hào)量是由于它采用了記錄型的數(shù)據(jù)結(jié)構(gòu)而得名的 。 它所包含的上述兩個(gè)數(shù)據(jù)項(xiàng)可描述為： type semaphore=record value:integer。 L:list of process。 end 相應(yīng)地， wait(S)和 signal(S) procedure wait(S) var S: semaphore。 begin ∶ = 。 if ＜ 0 then block(S,L) end procedure signal(S) var S: semaphore。 begin ∶ = +1。 if ≤0 then wakeup(S,L)。 end 在記錄型信號(hào)量機(jī)制中 ， 資源的數(shù)目 ， 因而又稱為資源信號(hào)量 ， 對(duì)它的每次 wait操作 ，意味著進(jìn)程請(qǐng)求一個(gè)單位的該類資源 ， 因此描述為 ∶ =； 當(dāng) ＜ 0時(shí) ， 表示該類資源已分配完畢 ， 因此進(jìn)程應(yīng)調(diào)用 block原語 ， 進(jìn)行自我阻塞 ， 放棄處理機(jī) ， 并插入到信號(hào)量鏈表 。 可見 ， 該機(jī)制遵循了 “ 讓權(quán)等待 ” 準(zhǔn)則 。 此時(shí) 的數(shù)目 。 對(duì)信號(hào)量的每次 signal操作 ， 表示執(zhí)行進(jìn)程釋放一個(gè)單位資源 ， 故 ∶ =+1操作表示資源數(shù)目加 1。 若加 1后仍是 ≤0， 則表示在該信號(hào)量鏈表中 ， 仍有等待該資源的進(jìn)程被阻塞 ， 故還應(yīng)調(diào)用 wakeup原語 ， 將 的第一個(gè)等待進(jìn)程喚醒 。 如果 1， 表示只允許一個(gè)進(jìn)程訪問臨界資源 ， 此時(shí)的信號(hào)量轉(zhuǎn)化為互斥信號(hào)量 。 3. AND型信號(hào)量 在兩個(gè)進(jìn)程中都要包含兩個(gè)對(duì) Dmutex和 Emutex的操作 ， 即 process A: process B: wait(Dmutex)。 wait(Emutex)。