計算機操作系統第3章(編輯修改稿)

　

【文章內容簡介】 意的順序釋放和獲取數據塊的。執行 getspace就是獲取一個空數據塊，而執行release(ad)就是釋放一個地址為 ad的數據塊。然而，由下面的描述可以看到，在進程并發執行時，getspace或 release(ad)將有可能完不成所要求的功能。 getspace和 release(ad)可進一步描述為： getspace: begin local g g←stack ［ top ］ top←top 1 end release(ad): begin top ← top+1 stack ［ top ］ ← ad end 設時刻 t0時， top=h0，則 getspace和 release(ad)可能按以下順序執行： 首先 release(ad)的第一句執行， t0： top ← top+1 → top=h0+1； 接著 getspace 執行，得： t1： g ← stack ［ top］ → g=stack ［ h0+1］； t2： top ← top 1 → top=h0； 再是 release(ad)的第二句執行，得： t3： stack ［ top］ ← ad → stack ［ h0 ］ ← ad； 其結果是調用 getspace的進程取到的是 h0+1中的一個未定義值，而調用 release(ad)的進程把所釋放的空塊地址 ad重復放入了 h0中。 怎樣保證上述執行結果的正確性呢？ 一個較為明顯的答案是，如果把 getspace和 release(ad)抽象為兩個各以一個動作完成的順序執行單位，那么執行結果的正確性是可以保證的。 把不允許多個并發進程交叉執行的一段程序稱為臨界部分（ critical section ）或臨界區（ critical region）。 臨界區是由屬于不同并發進程的程序段共享公用數據或公用數據變量而引起的，例如上例中就是因為過程 getspace 和 release(ad)共同訪問棧Ｓ中的數據而引起的。臨界區不可能用增加硬件的方法來解決。因此，臨界區也可以被稱為訪問公用數據的那段程序。 2. 間接制約 一般來說，可以把那些不允許交叉執行的臨界區按不同的公用數據劃分為不同的集合。上例中，以公用數據棧Ｓ劃分的臨界區集合是 {getspace,release}。把這些集合稱為類（ class）。顯然，對類給定一個唯一的標識名，系統就會容易地區分它們。在程序的描述中，可用下列標準形式來描述臨界區： when〈 類名 〉 do〈 臨界區 〉 od 設類 {getspace， release} 的類名為 sp，則 getspace和release(ad)可重新描述為： getspace: when sp do getspce←stack ［ top ］ top←top 1 od release(ad): when sp do top← top+1 stack ［ top ］ ← ad od 把這種由于共享某一公有資源而引起的在臨界區內不允許并發進程交叉執行的現象，稱為由共享公有資源而造成的對并發進程執行速度的間接制約，簡稱間接制約。這里，“間接”二字主要是指各并發進程的速度受公有資源制約，而不是進程間直接制約的意思。 這里，受間接制約的類中各程序段在執行順序上是任意的。 顯然，對于每一類，系統應有相應的分配和釋放相應公有資源的管理辦法，以制約并發進程。這就是互斥。 3. 什么是互斥 可以把互斥定義為：一組并發進程中的一個或多個程序段，因共享某一公有資源而導致它們必須以一個不允許交叉執行的單位執行。也就是說，不允許兩個以上的共享該資源的并發進程同時進入臨界區稱為互斥。 這里，考慮類中只有一個元素，也就是只有一個程序段的情況是很有意思的。這時程序段本身為公有資源被并發進程共享。一般情況下，作為程序段的一個過程不允許多個進程共同訪問它。但如果該過程是純過程，則各并發進程可以同時訪問它。純過程是指在執行過程中不改變過程自身代碼的一類過程。 通常，在計算機系統中，有許多過程是被多個并發進程同時訪問共享，例如編輯程序、編譯程序等。把一個過程作成純過程可便于多個進程共享，但由于編制純過程必須對有關變量和工作區作相應的處理，從而其執行效率往往會受到一定的影響。 一組并發進程互斥執行時必須滿足如下準則： (1) 不能假設各并發進程的相對執行速度。即各并發進程享有平等的、獨立的競爭共有資源的權利，且在不采取任何措施的條件下，在臨界區內任一指令結束時，其他并發進程可以進入臨界區。 (2) 并發進程中的某個進程不在臨界區時，它不阻止其他進程進入臨界區。 (3) 并發進程中的若干個進程申請進入臨界區時，只能允許一個進程進入。 (4) 并發進程中的某個進程申請進入臨界區時開始，應在有限時間內得以進入臨界區。 這里，準則 (1)， (2)， (3)是保證各并發進程享有平等的、獨立的競爭和使用公有資源的權利，且保證每一時刻至多只有一個進程在臨界區。而準則 (4)則是并發進程不發生死鎖（將在后面講述）的重要保證。否則，由于某個并發進程長期占有臨界區，其他進程則因為不能進入臨界區而進入互相等待狀態。 在一組并發執行進程中，除了因為競爭公有資源而引起的間接制約帶來進程之間互斥之外，還存在有因為并發進程互相共享對方的私有資源所引起的直接制約。直接制約將使得各并發進程同步執行。下面，將討論互斥的實現方法。 互斥的加鎖實現 上節中，給出了臨界區的描述方法和并發進程互斥執行時所必要遵守的準則。但是，并沒有給出怎樣實現并發進程的互斥。人們可能認為只需把臨界區中的各個過程按不同的時間排列調用就行了。但事實上這是不可能的。因為這要求該組并發進程中的每個進程事先知道其他并發進程與系統的動作，由用戶程序執行開始的隨機性可知，這是不可能的。 一種可能的辦法是對臨界區加鎖以實現互斥。當某個進程進入臨界區之后，它將鎖上臨界區，直到它退出臨界區時為止。并發進程在申請進入臨界區時，首先測試該臨界區是否是上鎖的。如果該臨界區已被鎖住，則該進程要等到該臨界區開鎖之后才有可能獲得臨界區。 設臨界區的類名為Ｓ。為了保證每一次臨界區中只能有一個程序段被執行，又設鎖定位 key［Ｓ］ 。key［Ｓ］表示該鎖定位屬于類名為Ｓ的臨界區。加鎖后的臨界區程序描述如下： lock(key ［Ｓ］ ) 〈 臨 界 區 〉 unlock(key ［Ｓ］ ) 設 key ［Ｓ］ =1時表示類名為Ｓ的臨界區可用， key ［Ｓ］ =0時表示類名為Ｓ的臨界區不可用。則，unlock(key ［Ｓ］ )只用一條語句即可實現。即： key ［Ｓ］ ← 1 不過，由于 lock(key ［Ｓ］ )必須滿足 key ［Ｓ］ =0時，不允許任何進程進入臨界區，而 key ［Ｓ］ =1時僅允許一個進程進入臨界區的準則，因而實現起來較為困難。 一種簡便的實現方法是： lock (x)=begin local v repeat v←x untilv=1 x←0 end 這種實現方法是不能保證并發進程互斥執行所要求的準則 (3)的。因為當同時有幾個進程調用 lock(key ［Ｓ］ )時，在 x←0 語句執行之前，可能已有兩個以上的多個進程由于 key ［Ｓ］ =1而進入臨界區。為解決這個問題有些機器在硬件中設置了“測試與設置指令，保證第一步和第二步執行不可分離。 注意：在系統實現時鎖定位 key ［Ｓ］總是設置在公有資源所對應的數據結構中的。 信號量和Ｐ，Ｖ原語 1. 信號量（ semaphore） 盡管用加鎖的方法可以實現進程之間的互斥，但這種方法仍然存在一些影響系統可靠性和執行效率的問題。例如，循環測試鎖定位將損耗較多的 CPU計算時間。如果一組并發進程的進程數較多，且由于每個進程在申請進入臨界區時都得對鎖定位進行測試，這種開銷是很大的。 另外，使用加鎖法實現進程間互斥時，還將導致在某些情況下出現不公平現象。試考慮以下進程 PA和 PB反復使用臨界區的情況： PA A： lock(key［Ｓ］ ) 〈 Ｓ 〉 unlock(key［Ｓ］ ) Goto A PB B： lock(key ［Ｓ］ ) ＜Ｓ＞ unlock(key ［Ｓ］ ) Goto B 設進程Ｐ A已通過 lock(key ［Ｓ］ )過程而進入臨界區。顯然，在進程 PA執行 unlock(key ［Ｓ］ )過程之前，key ［Ｓ］ =0且進程 PB沒有進入臨界區的機會。然而，當進程 PA執行完 unlock(key ［Ｓ］ )過程之后，由于緊接著是一轉向語句，進程 PA將又立即去執行 lock(key ［Ｓ］ )過程。 此時，由于 unlock(key［Ｓ］ )過程已將 key［Ｓ］的值置為 1，也就是開鎖狀態，從而進程 PA又可進入臨界區Ｓ。只有在進程 PA執行完 unlock(key［Ｓ］ )過程之后、執行 Goto A語句之前的瞬間發生進程調度，使進程 PA把處理機轉讓給進程 PB，進程 PB才有可能得到執行。然而遺憾的是，這種可能性是非常小的。因此，進程 PB將處于永久饑餓狀態（ starvation）。 解決上述問題首先必須找到產生問題的原因。顯然，在用加鎖法解決進程互斥的問題時，一個進程能否進入臨界區是依靠進程自己調用 lock過程去測試相應的鎖定位。每個進程能否進入臨界區是依靠自己的測試判斷。這樣沒有獲得執行機會的進程當然無法判斷，從而出現不公平現象。而獲得了測試機會的進程又因需要測試而損失一定的 CPU 時間。 這正如某個學生想使用某個人人都可借用、且不規定使用時間的教室時一樣，他必須首先申請獲得使用該教室的權利，然后再到教室看看該教室是不是被鎖上了。如果該教室被鎖上了，他只好下次再來觀察，看該教室的門是否已被打開。這種反復將持續到他進門后為止。從這個例子中，可以得到解決加鎖法所帶來的問題的方法。一種最直觀的辦法是，設置一個教室管理員。從而，如果有學生申請使用教室而未能如愿時，教室管理員記下他的名字，并等到教室門一打開則通知該學生進入。這樣，既減少了學生多次來去教室檢查門是否被打開的時間，又減少了因為學生自發地檢查造成的不公平現象。在操作系統中，這個管理員就是信號量。信號量管理相應臨界區的公有資源，它代表可用資源實體。 信號量的概念和下面所述的Ｐ、Ｖ原語是荷蘭科學家 。信號是鐵路交通管理中的一種常用設備，交通管理人員利用信號顏色的變化來實現交通管理。在操作系統中，信號量 sem是一整數。在 sem大于等于零時代表可供并發進程使用的資源實體數，但 sem小于零時則表示正在等待使用臨界區的進程數。顯然，用于互斥的信號量sem的初值應該大于零，而建立一個信號量必須經過說明所建信號量所代表的意義，和賦初值以及建立相應的數據結構以便指向那些等待使用該臨界區的進程。 2. Ｐ，Ｖ原語 信號量的數值僅能由Ｐ，Ｖ原語操作改變 (Ｐ和Ｖ分別是荷蘭語 Passeren 和 Verhoog 的頭一個字母，相當于英文的 pass和 increment的意思 )。采用Ｐ，Ｖ原語，可以把類名為Ｓ的臨界區描述為 When Ｓ do Ｐ (sem)臨界區Ｖ (sem)od。 這里， sem是與臨界區內所使用的公用資源有關的信號量。一次Ｐ原語操作使得信號量 sem減 1，而一次Ｖ原語操作將使得信號量 sem加 1。必須強調的一點是，當某個進程正在臨界區內執行時，其他進程如果執行了Ｐ原語操作，則該進程并不像調用lock時那樣因進不了臨界區而返回到 lock的起點，等以后重新執行測試，而是在等待隊列中等待有其他進程做Ｖ原語操作釋放資源后，進入臨界區，這時，Ｐ原語的執行才算真正結束。 另外，當有好幾個進程執行Ｐ原語未通過而進入等待狀態之后，如有某進程作了Ｖ原語操作，則等待進程中的一個可以進入臨界區，但其他進程必須等待。 Ｐ原語操作的主要動作是： (1) sem減 1； (2) 若 sem減 1后仍大于或等于零，則進程繼續執行； (3) 若 sem減 1后小于零，則該進程被阻塞后與該信號相對應的隊列中，然后轉進程調度。 Ｐ原語操作的功能框圖如圖 。 圖 Ｐ原語操作功能 圖 Ｖ原語的操作主要動作是： (1) sem加 1； (2) 若相加結果大于零，進程繼續執行； (3) 若相加結果小于或等于零，則從該信號的等待隊列中喚醒一等待進程，然后再返回原進程繼續執行或轉進程調度。 Ｖ原語操作的功能框圖如圖 。 有了加鎖法的基礎，大家應該明白為什么Ｐ，Ｖ過程要以原語實現的原因。否則，如果多個進程同時調用Ｐ操作或Ｖ操作的話，則有可能在Ｐ操作剛把sem1而未把對應進程送入等待隊列時，Ｖ操作開始執行。從而，Ｖ操作將無法發現等待進程而返回。因此，Ｐ，Ｖ操作都必須以原語實現，且在Ｐ，Ｖ原語執行期間不允許中