Zagadnienie ograniczonego buforowania powinno być już znane. Mówiliśmy o tym w segmencie 2 tej lekcji.

Jeżeli przyjmiemy, że mamy n buforów, a każdy z nich mieści 1 jednostkę, oraz że semafor mutex (umożliwiający wzajemne wykluczanie dostępu do buforów) jest na starcie równy 1, zaś semafory pusty i pełny zawierają informację o liczbie pustych (wartość początkowa n) i pełnych (wartość początkowa 0) buforów, to ogólna wersja algorytmu wygląda tak [1]:
repeat
    ...
    produkuj jednostkę w nowyprodukt
    ...
    poczekaj(pusty);
    poczekaj(mutex);
    ...
    dodaj jednostkę nowyprodukt do bufora bufor
    ...
    zasygnalizuj(mutex);
    zasygnalizuj(pełny);
until false

Proces producenta ...

repeat
    poczekaj(pełny);
    poczekaj(mutex);
    ...
    wyjmij jednostkę z bufora bufor do nowakonsumpcja
    ...
    zasygnalizuj(mutex);
    zasygnalizuj(pusty);
    ...
    konsumuj jednostkę z nowakonsumpcja
    ...
until false

... i proces konsumenta.

Instrukcje poczekaj oznaczają oczekiwanie z powodu faktu, że bufor jest pusty lub pełny. Instrukcja zasygnalizuj opisuje sytuację, w której bufor staje się pusty lub pełny, a także uruchomienie semafora mutex. Problem ten odnosi się do środowisk, w których zasoby mogą być dzielone. W takich środowiskach może zachodzić sytuacja dostępu do danego zasobu przez kilka procesów jednocześnie. Niektóre z tych procesów odczytują tylko zawartość obiektu dzielonego, inne zapisują do niego informacje (aktualizacja). Jak już Procesy odczytujące dane z obiektu dzielonego to czytelnicy, zaś zapisujące dane to pisarze.

Problem czytelników i pisarzy (ang. readers-writers problem) polega na zapewnieniu "prywatności" pisarzowi. Nie może zdarzyć się sytuacja, w której dany obiekt współdzielony jest przez pisarza i inny proces, czy to czytelnika, czy to innego pisarza. Problem ten ma kilka odmian. Najłatwiejsza z nich nazywana jest pierwszym problemem czytelników i pisarzy. Metoda ta zakłada, że żaden czytelnik nie musi czekać, pomimo tego że pisarz jest gotowy, na zakończenie pracy pozostałych czytelników. Kolejna odmiana problemu czytelników i pisarzy zakłada, że gotowość pisarza oznacza, że żaden nowy czytelnik nie będzie mógł współpracować z obiektem.

Ponieważ oba przedstawione powyżej schematy mogą powodować głodzenie, stosuje się również inne wersje rozwiązania tego problemu.

Poniżej zostanie opisane rozwiązanie pierwszego problemu czytelników i pisarzy. Załóżmy, że wszystkie z procesów mają wspólne następujące zmienne [1]:
var mutex, pisarz: semaphore;
    liczba_czytelnikow: integer;
// wartość początkowa "1" dla obu semaforów
// wartość początkowa "0"
Przed napiseniem struktury procesu czytelnika warto jeszcze nadmienić, że semafor mutex zajmuje się wzajemnym wykluczaniem procesów podczas nadpisywania zmiennej liczba_czytelnikow. Semafor pisarz daje gwarancję wzajemnego wykluczania pisarzy, a ponadto jest używany przez pierwszy proces wchodzący lub ostatni proces wychodzący z sekcji krytycznej czytelnika. Semafor ten nie jest natomiast używany przez czytelników wchodzących/wychodzących podczas, gdy inni czytelnicy znajdują się w sekcjach krytycznych. A oto i rozwiązanie naszego problemu [1].

Tak wygląda struktura procesu pisarza:
poczekaj(pisrz)
    ...
    teraz proces sobie pisze i pisze, i pisze ...
    ...
zasygnalizuj(pisarz);

Struktura procesu czytelnika wygląda następująco:
poczekaj(mutex);
    liczba_czytelnikow:=liczba_czytelnikow+1;
    if liczba_czytelnikow=1 then poczekaj(pisarz);
zasygnalizuj(mutex);
    ...
    proces czyta sobie i czyta, i czyta ...
    ...
poczekaj(mutex);
    liczba_czytelnikow:=liczba_czytelnikow-1;
    if liczba_czytelnikow=0 then zasygnalizuj(pisarz);
zasygnalizuj(mutex);
Po wykonaniu przez proces pisarza operacji zasygnalizuj(pisarz) możliwe są dwie drogi: można wznowić działanie pojedynczego pisarza lub czekających czytelników, zależnie od wyboru planisty. Uwaga, wybieramy się na wycieczkę. Znajdujemy się teraz w miejscu bliżej nieokreślonym, w którym jest tylko jeden mebel - stół. Przy tymże stole siedzi pięć osób. Wszyscy mają przed sobą miseczki, a na środku stołu stoi misa z ryżem. Ponadto, na stole znajduje się pięć pałeczek rozmieszczonych pomiędzy miseczkami nieznanych nam osób. Po dokładniejszych oględzinach okazuje się, że ci ludzie są filozofami. A wiecie dlaczego? Ponieważ przez cały czas myślą, a gdy są głodni sięgają po pałeczki, aby zjeść trochę ryżu, potem znowu myślą. I tu dochodzimy do naszego problemu. Jak nasz drogi filozof ma wziąć dwie pałeczki, skoro sąsiad też może chcieć coś zjeść? Przecież filozof nie będzie wyrywał siłą koledze pałeczki z ręki.

Można by przypuszczać, że problem filozofów nie ma wiele wspólnego z synchronizacją. To nieprawda. Problem obiadujących filozofów jest klasycznym problemem konieczności przydziału wielu zasobów do wielu procesów w warunkach zagrożenia głodzeniem i zakleszczeniem [1].

[Myśliciele]

Rys. 5.2. Pięciu współczesnych obiadujących filozofów

Przedstawimy proste rozwiązanie tego problemu, oparte na semaforach, nie wolne jednak od niebezpieczeństw. Operacja poczekaj oznacza podniesienie przez filozofa pałeczki, zaś operacja zasygnalizuj oznacza pałeczki odłożenie. Nasza pałeczka wygląda natomiast następująco [1]:
var paleczka: array[0..4] of semaphore;
// wartość początkowa=1
Po wielu zmaganiach umysłowych będziemy wreszczie mogli zobaczyć jak wygląda struktura n-tego filozofa.
repeat
    poczekaj(pałeczka[n]);
    poczekaj(pałeczka[n+1 mod 5]);
    ...
        jedzenie, jedzenie, jedzenie, np. ryżu
    ...
    zasygnalizuj(pałeczka[n]);
    zasygnalizuj(pałeczka[n+1 mod 5]);
    ...
    myślnie nie boli, więc filozof myśli
    ...
until false

Struktura procesu n-tego filozofa [1]

Rozwiązanie powyżej przedstawione nie jest najlepsze. Zapewnia co prawda gwarancję, że dwaj sąsiedzi nie będą jedli jednocześnie, jednakże w przypadku gdy każdy z filozofów w tym samym czasie weźmie pałeczkę (by było to możliwe każdy z filozofów musi wziąć pałeczkę leżącą po tej samej stronie, np. prawej) tak, że wszystkie pałeczki zostaną podniesione (elementy tablicy pałeczka są równe "0"), nie będzie możliwe podniesienie przez któregokolwiek z filozofów pałeczki drugą ręką. Zatrzymamy się w pętli nieskończonej.

Naturalnie możliwa jest eliminacja takich zakleszczeń. A oto kilka na to sposobów:

NASTĘPNA