首先,讓我介紹一些術語。 關鍵部分(CS)是一系列指令,可以同時執行至多一個進程。使用關鍵部分時,代碼可分爲以下幾部分:
// Some arbitrary code (such as initialization).
EnterCriticalSection(cs);
// The code that constitutes the CS.
// Only one process can be executing this code at the same time.
LeaveCriticalSection(cs);
// Some arbitrary code. This is called the remainder section.
第一部分包含一些代碼,如初始化代碼。我們沒有該部分的名稱。第二部分是試圖進入CS的代碼。第三部分是CS本身。第四部分是離開關鍵部分的代碼。第五和最後一節稱爲剩餘部分它可以包含任何代碼。請注意,CS本身在進程間可能不同(例如,考慮從客戶端接收請求並將其插入隊列的進程以及處理這些請求的另一進程)。
爲確保關鍵部分的實施能正常工作,必須滿足三個條件。你提到了其中兩個(我將在下面解釋)。三是互相排斥,這顯然是至關重要的。值得注意的是,互斥只適用於CS和休假部分。但是,其他三個部分並不是唯一的。
第一個條件是進度。這種情況的目的是確保某個進程當前在CS中並且正在進行一些工作,或者如果至少有一個進程想要進入CS,那麼它將會做一些工作。在這兩種情況下,一些工作正在完成,因此所有進程都在整體上取得進展。
進展情況:如果沒有進程在臨界區執行和 一些進程希望進入其關鍵的部分,那麼只有未在其剩餘部分執行這些 過程可以 參與決定其將進入臨界部分接下來, 和這個選擇不能無限期推遲。
讓我們逐句理解這個定義。
如果沒有進程在臨界區執行
如果在臨界區執行過程中(即使未顯式聲明,這包括假節爲好),那麼這意味着有些工作正在完成。所以我們正在取得進展。否則,如果這是不是這樣的......
和一些進程希望如果沒有進程想進入其關鍵部分進入其關鍵部分
,那麼就沒有更多的工作要做。否則,如果有一個希望進入臨界區的至少一個過程......
那麼只有那些沒有在他們的剩餘部分的執行進程
這意味着我們所談論的那些這被用在前兩節(記住,沒有進程在臨界區執行或許可部分)的執行流程...
可以參與決定,將在明年進入臨界區,
由於至少有一個進程希望進入其CS,所以我們必須選擇其中的一個進入其CS。但誰來做出這個決定?那些已經申請進入其關鍵部門許可的流程有權參與作出此決定。此外,那些可能希望進入他們的CS但尚未請求這樣做(這意味着他們正在執行的第一部分)的進程也有權參與作出此決定。
這個選擇不能無限期地推遲。
這表明,它將花費有限的時間來選擇進入其CS的過程。特別是,不會出現deadlock or livelock。所以在這段有限的時間之後,一個過程將進入其CS並做一些工作,從而取得進展。
現在我將解釋最後一個條件,即有界等待。此條件的目的是確保每個流程都有機會真正進入臨界區域,因此無需進程starves forever。但請注意,這種條件和進度都不能保證公平。 CS的實現不一定要公平。
界等待:存在一個結合或限制對 倍其他進程被允許進入其臨界區 一個進程取得請求之前請求是進入其臨界區和 後的數理所當然的。
讓我們從最後一句開始逐句理解這個定義。
一個進程已經提出請求進入其關鍵部分並且 在該請求被授予之前。
換句話說,如果有一個進程已經請求進入其CS但尚未進入它。我們稱這個過程爲P.
存在一個約束或限制,對 次數其他進程被允許進入其關鍵部分
而P正在等待進入的CS,其他進程也可能正在等待,並且某個進程正在其CS中執行。當它離開CS時,必須選擇其他一些進程來進入可能或可能不是P的CS。假設選擇了P以外的進程。這種情況可能會一再發生。也就是說,其他進程有機會進入他們的CS,但從來沒有P。注意進展正在進行,但是由其他進程而不是由P進行。問題是P沒有得到任何工作的機會。爲了防止飢餓,必須保證P最終會進入CS。要發生這種情況,其他流程進入其CS的次數必須受到限制。在這種情況下,P肯定有機會進入它的CS。
我想提一下,CS的定義可以概括,以便至多N個進程在它們的臨界區執行,其中N是任何正整數。還有讀寫器關鍵部分的變體。
精彩的逐行解釋 –
你真了不起。很好的解釋! – void