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:

• Jeśli kilka procesów jednocześnie żąda przyznania im zasobu, wówczas jego udostępnienie musi nastąpić po upływie skończonego czasu.
• Jeśli proces korzysta z zasobu, to musi go zwrócić w skończonym czasie.
• Czas oczekiwania na udostępnienie zasobu nie wpływa na czas korzystania z zasobu.
• Co najwyżej jeden proces może korzystać z zasobu

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

• Implementacja powinna odbywać się bez specjalnych instrukcji assemblera (dopuszczalne są jedynie instrukcje sprawdzające i uaktualniające zawartość pamięci operacyjnej). Instrukcje muszą być nieprzerywalne
• Szybkości wykonywania się procesów mogą być dowolne
• Procesy znajdujące się poza danym zasobem nie zabezpieczają go przed udostępnianiem go innym procesom

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:

• P(S) – dekrementacja
• V(S) – inkrementacja

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.:

• Brak wpływu jednego procesu na zakończenie działania innego procesu
• Brak możliwości zawieszenia procesu na określony przedział czasu

Opracowane na podstawie „Wstęp do projektowania systemów operacyjnych” Jerzy Martyna