Sr-7-wyk-2.0-Slajd10
Z Studia Informatyczne
Algorytm Lamporta – wprowadzenie
Lamport był pierwszym, który podał rozproszony algorytm wzajemnego wykluczania, jako przykład zastosowania wymyślonego przez siebie schematu synchronizacji zegarów.
Jako Ri oznaczmy zbiór żądań (ang. request set ) procesu Pi , tzn. zbiór procesów, od których Pi wymaga pozwolenia, kiedy chce się dostać do sekcji krytycznej. W algorytmie Lamporta zbiór żądań każdego procesu jest zbiorem wszystkich innych procesów. Każdy proces Pi utrzymuje kolejkę kolejka_żądań(i ), która zawiera żądania wejścia do sekcji krytycznej uszeregowane według ich znaczników czasowych. Algorytm ten wymaga, aby wiadomości dostarczane były pomiędzy każdą parą procesów w kolejności FIFO (ang. First In , First Out – pierwszy na wejściu, pierwszy na wyjściu).
