algorytm.org

Algorytm Morris'a

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm Morris'a
Ocena użytkowników:***** / 1
SłabyŚwietny 
Wpisany przez Bartosz Wikiera, 16 lutego 2012 15:10

Algorytm Morrisa rozwiązuje problem wzajemnego wykluczania skończonej liczby procesów (nie dopuszczając do zagłodzenia) przy użyciu semaforów binarnych.
Zanim przejdę do omówienia rozwiązania zaproponowanego przez Morrisa najpierw przedstawię pokrótce problem wzajemnego wykluczania i przybliżę pojęcie semafora.

Wzajemne wykluczanie
Wzajemne wykluczanie jest to użytkowanie określonego zasobu przez nie mniej niż dwa procesy, które dzielą się tym zasobem. Procesy te nie mogą jednocześnie korzystać z zasobu. Przykładem z życia wziętym może być często występujące ostrzeżenie w systemach Windows kiedy próbujemy np. usunąć plik aktualnie używany przez inny program. Jeśli chcemy by proces usuwający dane mógł zrealizować swój cel musimy zakończyć wykonywanie programu używającego tego zasobu. Procesy muszą czekać na przyznanie im zasobu o ile jest zajęty.

Realizacja wzajemnego wykluczania uznawana jest za poprawną jeśli spełnia następujące warunki:

Implementacja wzajemnego wykluczania procesów nakłada kolejne ograniczenia:

Semafory
Semafor S jest zmienną typu całkowitego na której można wykonywać zaledwie dwie operacje oraz jej inicjację. Istnieją dwa rodzaje semaforów – binarne (jak łatwo się domyślić mogą one przyjąć wartości 0 lub 1) oraz semafory zliczające (przyjmują nieujemne wartości całkowite).

Operacje semaforowe to:

Jeśli wykonujemy operacje P(S) i w pewnym momencie S przyjmie wartość ujemną to wykonywanie procesu zatrzymuje się. Może ono zostać wznowione gdy zadziała instrukcja V(S). Semaforów binarnych używa się do wzajemnego wykluczania dostępu do wspólnych zasobów/zmiennych.

Algorytm Morrisa
a := 1 //semafor chroniacy zmienna q
b := 1 //semafor chroniacy zmienna p
m := 0 //semafor chroniacy wspoldzielony zasob/zmienna
p := 0
q := 0

//-----------//
funkcja k-ty-proces

  // dowolne instrukcje

  P(b)
  p++
  V(b)
  //---------------//

  P(a)
  q++
  P(b)
  p--
  //--------------//

  Jeśli p == 0
     V(b)
     V(m)
  W przeciwnym razie
     V(b)
     V(a)

  P(m)
  q--
  // rozpoczęcie użytkowania zasobu
  .....
  // zakończenie użytkowania zasobu

  Jeśli q == 0
     V(a)
  W przeciwnym razie
     V(m)

  // dalsze instrukcje

koniec.

W programie k-ty proces który chce wejść do swojego obszaru krytycznego zwiększa wartość p o 1 (instrukcja ta jest chroniona operacjami semaforowymi na zmiennej b). Po wykonaniu tej instrukcji p wskazuje liczbę procesów gotowych do wykonania operacji P(a). Druga zmienna q podaje liczbę procesów które już wykonały operację P(a), lecz jeszcze nie wykonały operacji P(m). Proces, który opuszcza obszar krytyczny P(a),P(b), pozwala innym procesom wejść do tego obszaru, o ile są procesy chcące tego dokonać. Natomiast jeśli brakuje procesów gotowych do wejścia do tego obszaru (p == 0) to wykonanie przez proces operacji V(m) umożliwia wejście do obszaru znajdującego się między P(m) a V(m). Procesy będą wchodzić do tego obszaru kolejno przy czym ostatni z nich wykonując operacje V(a) – drugą z wyszczególnionych w treści programu – otworzy wejście nowym procesom do pierwszego z obszarów krytycznych zawartych między P(a) i V(a). Działanie to wynika z każdorazowej znajomości zmiennych p i q. Uniemożliwia ono wstrzymywanie bez końca jednych procesów kosztem drugich.
Nie jest natomiast znana liczba procesów czekających na wykonanie drugiej operacji P(b). Stąd też, gdy ostatni proces opuszcza obszar zawarty między P(a) a V(b) i wykonuje operację V(m), to umożliwia on wejście do obszaru krytycznego chronionego operacjami semaforowymi P(b) i V(b) nawet wówczas, gdy brak jest procesów wstrzymanych dzięki operacji P(b). Jest to niewątpliwie wada powyższego rozwiązania.

Stosowanie operacji semaforowych nie jest bez wad są to m.in.:
Opracowane na podstawie „Wstęp do projektowania systemów operacyjnych” Jerzy Martyna
Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 30 lipca 2012 18:45
Dodaj komentarz