shanirx 2011-11-03

1962年，狄克斯特拉離開數學中心進入位於荷蘭南部的艾恩德霍芬技術大學（Eindhoven Technical University）任數學教授。在這裡，他參加了X8計算機的開發，設計與實現了具有多道程式執行能力的作業系統——THE Multiprogramming System。THE是艾恩德霍芬技術大學的荷蘭文Tchnische Hoogeschool Eindhov –en的詞頭縮寫。狄克斯特拉在THE這個系統中所提出的一系統方法和技術奠定了計算機現代作業系統的基礎，尤其是關於多層體系結構，順序程序之間的同步和互斥機制這樣一些重要的思想和概念都是狄克斯特拉在THE中首先提出併為以後的作業系統如UNIX等所採用的。為了在單處理機的情況下確定程序（process）能否佔有處理機，狄克斯特拉將每個程序分為“就緒”（ready）、“執行”（running）和“阻塞”（blocking）三個工作狀態。由於在任一時刻最多隻有一個程序可以使用處理機，正佔用著處理機的程序稱為“執行”程序。當某程序已具備了使用處理機的條件，而當前又沒有處理機供其使用，則使該程序處於“就緒”狀態。當執行程序由於某種原因無法繼續執行下去時，就停止其佔用處理機，使之進入“阻塞”狀態，待造成其退出執行的條件解除，再進入“就緒”狀態。而對系統中所有同時執行的程序，在一個程序訪問共享資料時，另一個程序不訪問該資料）和互斥（mutually- exclusive，指兩個程序不能同時在一個臨界區中使用同一個可重複使用的資源，諸如讀寫緩衝區）兩個關係，狄克斯特拉巧妙地利用火車執行控制系統中的“訊號燈”（semaphore，或叫”訊號量”）概念加以解決。所謂訊號燈，實際上就是用來控制程序狀態的一個代表某一資源的儲存單元。例如，P1和P2是分別將資料送入緩衝B和從緩衝B讀出資料的兩個程序，為了防止這兩個程序併發時產生錯誤，狄克斯特拉設計了一種同步機制叫“PV操作”，P操作和V操作是執行時不被打斷的兩個作業系統原語。執行P操作P（S）時訊號量S的值減1，若結果不為負則P（S）執行完畢，否則執行P操作的程序暫停以等待釋放。執行V操作V（S）時，S的值加1，若結果不大於0則釋放一個因執行P（S）而等待的程序。對P1和P2可定義兩個訊號量S1和S2，初值分別為1和0。程序P1在向緩衝B送入資料前執行P操作P（S1），在送入資料後執行V操作V（S2）。程序P2在從緩衝B讀取資料前先執行P操作P（S2），在讀出資料後執行V操作V（S1）。當P1往緩衝B送入一資料後訊號量S1之值變為0，在該資料讀出後S1之值才又變為1，因此在前一數未讀出前後一數不會送入，從而保證了P1和P2之間的同步。我國讀者常常不明白這一同步機制為什麼叫PV操作，原來這是狄克斯特拉用荷蘭文定義的，因為在荷蘭文中，透過叫passeren，釋放叫vrijgeven，PV操作因此得名。這是在計算機術語中不是用英語表達的極少數的例子之一。 訊號量 訊號量是最早出現的用來解決程序同步與互斥問題的機制， 包括一個稱為訊號量的變數及對它進行的兩個原語操作。

訊號量的概念

1．訊號量的型別定義 每個訊號量至少須記錄兩個資訊：訊號量的值和等待該訊號量的程序佇列。它的型別定義如下：（用類PASCAL語言表述） semaphore = record value： integer； queue： ^PCB； end； 其中PCB是程序控制塊，是作業系統為每個程序建立的資料結構。 s。value>=0時，s。queue為空； s。value<0時，s。value的絕對值為s。queue中等待程序的個數； 2．PV原語 對一個訊號量變數可以進行兩種原語操作：p操作和v操作，定義如下： procedure p（var s：samephore）； { s。value=s。value-1； if （s。value<0） asleep（s。queue）； } procedure v（var s：samephore）； { s。value=s。value+1； if （s。value<=0） wakeup（s。queue）； } 其中用到兩個標準過程： asleep（s。queue）；執行此操作的程序的PCB進入s。queue尾部，程序變成等待狀態 wakeup（s。queue）；將s。queue頭程序喚醒插入就緒佇列 s。value初值為1時，可以用來實現程序的互斥。 p操作和v操作是不可中斷的程式段，稱為原語。如果將訊號量看作共享變數，則pv操作為其臨界區，多個程序不能同時執行，一般用硬體方法保證。一個訊號量只能置一次初值，以後只能對之進行p操作或v操作。 由此也可以看到，訊號量機制必須有公共記憶體，不能用於分散式作業系統，這是它最大的弱點。 V原語的主要操作是： （1）sem加1； （2）若相加結果大於零，則程序繼續執行； （3）若相加結果小於或等於零，則喚醒一阻塞在該訊號量上的程序，然後再返回原程序繼續執行或轉程序排程。

典型理解偏差

三個問題： 一，以V原語的1、2步來做，Sem不就永遠大於0，那程序不就一直迴圈執行成為死迴圈了？ 二，Sem大於0那就表示有臨界資源可供使用，為什麼不喚醒程序？ 三，Sem小於0應該是說沒有臨界資源可供使用，為什麼還要喚醒程序？ 析疑： 一，P操作對sem減1的。P、V原語必須成對使用！從而不會造成死迴圈。 二，Sem大於0的確表示有臨界資源可供使用，而且這個時候沒有程序被阻塞在這個資源上，也就是說沒有程序因為得不到這類資源而阻塞，所以沒有被阻塞的程序，自然不需要喚醒。 三，V原語操作的本質在於：一個程序使用完臨界資源後，釋放臨界資源，使Sem加1，以通知其它的程序，這個時候如果Sem<0，表明有程序阻塞在該類資源上，因此要從阻塞佇列裡喚醒一個程序來“轉手”該類資源。 比如，有兩個某類資源，四個程序A、B、C、D要用該類資源，最開始Sem=2，當A進入，Sem=1，當B進入Sem=0，表明該類資源剛好用完， 當C進入時Sem=-1，表明有一個程序被阻塞了，D進入，Sem=-2。當A用完該類資源時，進行V操作，Sem=-1，釋放該類資源，而這時Sem<0，表明有程序阻塞在該類資源上，於是喚醒一個。 為了進一步加深理解，再引入二個問題： 四，如果是互斥訊號量的話，應該設定訊號量Sem=1，但是當有5個程序都訪問的話，最後在該訊號量的連結串列裡會有4個在等待，也是說S=-4，那麼第一個程序執行了V操作使S加1，釋放了資源，下一個應該能夠執行，但喚醒的這個程序在執行P操作時因S〈0 ，也還是執行不了，這是怎麼回事呢？ 五，Sem的絕對值表示等待的程序數，同時又表示臨界資源，這到底是怎麼回事？ 析疑： 四，當一個程序阻塞了的時候，它已經執行過了P操作，並卡在臨界區那個地方。當喚醒它時就立即進入它自己的臨界區，並不需要執行P操作了，當執行完了臨界區的程式後，就執行V操作。 五，當訊號量Sem小於0時，其絕對值表示系統中因請求該類資源而被阻塞的程序數目。S大於0時表示可用的臨界資源數。注意在不同情況下所表達的含義不一樣。當等於0時，表示剛好用完。