SO-1st-2.3-w11.tresc-1.0-Slajd29: Różnice pomiędzy wersjami
Nie podano opisu zmian |
Nie podano opisu zmian |
||
| Linia 6: | Linia 6: | ||
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. Proces, który wykonuje resztę, ma numer 0. Numery przydzielone procesom przechowywane są w tablicy współdzielonej ''numer'' . Pozycja ''i-ta | 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 ''P<sub>i</sub>'' , 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 | '''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. | ||
Aktualna wersja na dzień 13:44, 22 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).
