SOP wyk nr 11-Slajd28: Różnice pomiędzy wersjami
Nie podano opisu zmian |
drobne zmiany treści opisu |
||
| Linia 1: | Linia 1: | ||
==Wzajemne wykluczanie n procesów — | ==Wzajemne wykluczanie n procesów — algorytm piekarni (1)== | ||
[[Image:SOP_wyk_nr_11-Slajd28.PNG|Wzajemne wykluczanie n procesów — | [[Image:SOP_wyk_nr_11-Slajd28.PNG|Wzajemne wykluczanie n procesów — algorytm piekarni (1)]] | ||
Idea algorytm piekarni, zaproponowanego przez Lamporta, opiera się na przydzielaniu kolejnego numeru w kolejce oczekujących petentów i wpuszczaniu petenta z najniższym numerem. Algorytm stosowany jest w niektórych urzędach, bankach oraz przychodniach lekarskich. | Idea algorytm piekarni, zaproponowanego przez Lamporta, opiera się na przydzielaniu kolejnego numeru w kolejce oczekujących petentów i wpuszczaniu petenta z najniższym numerem. Algorytm stosowany jest w niektórych urzędach, bankach oraz przychodniach lekarskich. | ||
Etap algorytmu, w którym przydzielany jest numer, nazywany jest przejściem przez drzwi. Jest to część sekcji wejściowej. Proces przechodząc przez drzwi odczytuje numer wszystkich pozostałych, wybiera maksymalny z nich, zwiększa go o 1 i w ten sposób ustala swój własny numer. | Etap algorytmu, w którym przydzielany jest numer, nazywany jest przejściem przez drzwi. Jest to część sekcji wejściowej. Proces, przechodząc przez drzwi, odczytuje numer wszystkich pozostałych, wybiera maksymalny z nich, zwiększa go o 1 i w ten sposób ustala swój własny numer. Proces, który wykonuje resztę, ma numer 0. Numery przydzielone procesom przechowywane są w tablicy współdzielonej ''numer'' . Pozycja ''i'' -ta tej tablicy jest zmienną wyjściową procesu ''Pi'' , a wszystkie pozostałe pozycje tablicy są dla niego zmiennymi wejściowymi. Wynika to z rozwinięcia operacji max, która w pełnej postaci mogłaby wyglądać następująco: | ||
''tmp'' := ''numer'' [0]; | ''tmp'' := ''numer''[0]; | ||
'''for''' ''k'' := 1 '''to''' ''n'' -1 '''do''' | '''for''' ''k'' := 1 '''to''' ''n'' -1 '''do''' | ||
'''if''' ''numer'' [''k'' ] > ''tmp'' '''then''' ''tmp'' := ''numer'' [''k'' ]; | '''if''' ''numer''[''k''] > ''tmp'' '''then''' ''tmp'' := ''numer''[''k'']; | ||
''numer'' [''i'' ] := ''tmp'' ; | ''numer''[''i''] := ''tmp''; | ||
Dodatkowo można by jeszcze wykluczyć przypadek ''k'' = ''i'' w pętli. Początkowo tablica ''numer'' wypełniona jest oczywiście wartościami 0. | Dodatkowo można by jeszcze wykluczyć przypadek ''k'' = ''i'' w pętli. Początkowo tablica ''numer'' wypełniona jest oczywiście wartościami 0. | ||
Wersja z 23:55, 4 wrz 2006
Wzajemne wykluczanie n procesów — algorytm piekarni (1)
Idea algorytm piekarni, zaproponowanego przez Lamporta, opiera się na przydzielaniu kolejnego numeru w kolejce oczekujących petentów i wpuszczaniu petenta z najniższym numerem. Algorytm stosowany jest w niektórych urzędach, bankach oraz przychodniach lekarskich.
Etap algorytmu, w którym przydzielany jest numer, nazywany jest przejściem przez drzwi. Jest to część sekcji wejściowej. Proces, przechodząc przez drzwi, odczytuje numer wszystkich pozostałych, wybiera maksymalny z nich, zwiększa go o 1 i w ten sposób ustala swój własny numer. Proces, który wykonuje resztę, ma numer 0. Numery przydzielone procesom przechowywane są w tablicy współdzielonej numer . Pozycja i -ta tej tablicy jest zmienną wyjściową procesu Pi , a wszystkie pozostałe pozycje tablicy są dla niego zmiennymi wejściowymi. Wynika to z rozwinięcia operacji max, która w pełnej postaci mogłaby wyglądać następująco:
tmp := numer[0];
for k := 1 to n -1 do
if numer[k] > tmp then tmp := numer[k];
numer[i] := tmp;
Dodatkowo można by jeszcze wykluczyć przypadek k = i w pętli. Początkowo tablica numer wypełniona jest oczywiście wartościami 0.
W celu kontroli przydziału numeru każdy proces ustawia na swojej pozycji w tablicy wybieranie wartość true na czas ustalania swojego numeru. Początkowo tablica wypełniona jest oczywiście wartościami false.
Analizując szczegóły operacji na zmiennych współdzielonych, można zauważyć, że wszystkie zmienne są modyfikowane przez 1 proces, a czytane przez pozostałe. Są to tzw. współdzielone rejestry typu „jeden zapisujący wielu odczytujących” (ang. single-writer-multiple-readers shared registers).
