複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/Lamport/3199348
複製
複製成功

Lamport

鎖定
Lamport算法：又稱麪包房算法，先來先服務算法。跟很多銀行採用的排隊機制一樣。客户到了銀行，先領取一個服務號。一旦某個窗口出現空閒，擁有最小服務號的客户就可以去空閒窗口辦理業務。Lamport算法利用前述的事件定序方案統一定序所有對臨界段的請求，按先來先服務的原則讓請求臨界資源的進程進入其臨界段，進/出臨界段1次需要3×(n-1)條消息。
外文名
Lamport
別    名
麪包房算法
Lamport算法基本假定如下：
A. 進程Pi發送的請求消息形如request(Ti , i)，其中Ti = Ci是進程Pi發送此消息時對應的邏輯時鐘值，i代表消息內容。
B.每個進程保持一個請求隊列，隊列中的請求消息根據Þ關係定序，隊列初始為空。
Lamport算法描述
當進程Pi請求資源時，它把請求消息request(Ti , i)排在自己的請求隊列中，同時也把該消息發送給系統中的其他進程； 當進程Pj接收到外來消息request(Ti , i)後，發送回答消息reply(Tj , j)，並把request(Ti , i)放入自己的請求隊列。應當説明，若進程Pj在收到request(Ti , i)前已提出過對同一資源的訪問請求，那麼其時間戳應比(Ti , i)小。 若滿足下述兩條件，則允許進程Pi訪問該資源(即允許進入臨界段)：
A. Pi自身請求訪問該資源的消息已處於請求隊列的最前面；
B. Pi已收到從所有其他進程發來的回答消息，這些回答消息的時間戳均晚於(Ti, i). 為了釋放該資源，Pi從自己的隊列中撤銷請求消息，併發送一個打上時間戳的釋放消息release給其他進程；
當進程Pj收到Pi的release消息後，它撤銷自己隊列中的原Pi的request(Ti , i)消息。
下面是我寫的代碼
procedure Procesus is
type MsgTypes is (REQUETE, QUITTANCE, LIBERE);
task TacheUsager;
task ExcluionMutuelle is
entry demande;
entry attente;
entry fin;
entry recoit(msgType : in MsgType; estampille, emetteur : in integer);
end ExcluionMutuelle;
task body TacheUsager is
begin
ExclusionMutuelle.demande;
ExclusionMutuelle.attente;
ExclusionMutuelle.fin;
....
....
end TacheUsager;
task body ExclusionMutuelle is
me: constant := ...;
N : constant := ...;
Time_Logique : integer:= 0;
scAccorde : boolean := false;
type t_file is record
msgType : msgTypes := LIBERE;
estampille : integer := 0;
end record;
file array (1..N) if t_file;
function Permission (me : in integer) return boolean is
accord : boolean := true;
begin
for j in 1..N loop
if j/= me then
accord := accord and (file(me).estampille < file(j).estampille) or (file(me).estampille = file(j).estampille and me < j);
end if;
end loop;
return accord;
end Permission;
begin -- ExclusionMutuelle
loop
select
accept demande;
Time_Logique := Time_Logique +1;
file(me) := (REQUETE, Time_Logique);
for j in 1..N loop
if j/= me then sent((REQUETE, Time_Logique, me),j);
end if;
end loop;
scAccorde := Permission(me);
or
when scAccorde => accept attente;
or
when seAccorde => accept fin;
file(me):= (LIBERE, Time_Logique);
for j in 1..N loop
if j/= me then sent((LIBERE, Time_Logique, me) j);
end if
end loop;
scAccord := false;
or
accept recoit(msgType : in MsgTypes; estampille, emetteur : in integer) do
Time_Logique := integer'max(Time_Logique, estampille) + 1;
case msyType is
when REQUETE => file(emetteur) := (REQUETE, estampille);
sent((QUITTANCE, Time_Logoque, me), emetteur);
when LIBERE => file(emetteur) := (LIBERE, estampille);
when QUITTANCE => if file(emetteur).msgType /= REQUETE then
file(emetteur) := (QUITTANCE, estampille);
end if
end case;
scAccorde := file(me).msgType = REQUETE and then Permission(me);
end recoit;
end select;
end loop;
end ExclusionMutuelle;
end Processus;