Producent – produkuje produkty - dobra (o określonym typie i rozmiarze)
Konsument – konsumuje (przetwarza) produkty wytworzone przez producenta
Między producentem a konsumentem stawiamy magazyn (bufor) nakładając ograniczenie postaci:
- konsument może tylko pobierać produkty z magazynu
- producent może tylko wkładać produkty do magazynu
- Producent i konsument może przebywać jednocześnie w magazynie ale w innych miejscach magazynu
Jeżeli magazyn ma ograniczone wymiary to:
- producent może produkować tak długo produkty i umieszczać je w magazynie dopóki magazyn nie jest pełny
- konsument może pobierać produkty z magazynu dopóki magazyn nie jest pusty
W konkretnych zastosowaniach warto stosować bufor cykliczny przez co nie trzeba przesuwać danych w buforze.
Problemy
- wykluczenie jednoczesnego przebywania producenta i konsumenta w tym samym miejscu magazynu
- zawieszenie konsumpcji gdy magazyn jest pusty
- zawieszenie produkcji gdy magazyn jest pełny
- wzajemne wykluczanie kilku producentów
- wzajemne wykluczanie kilku konsumentów
Rozwiązanie
Do rozwiązania problemu będzie potrzebna wiedza na temat semaforów oraz atomowych funkcji wait i signal.
Przypomnienie:
Semafor ogólny to zmienna (najczęściej globalna), która przyjmuje wartości całkowite (możemy wyróżnić też semafory binarne o 2 stanach zero lub jeden).
Na zmiennych semaforowych można wykonywać jedynie dwie operacje wait lub signal oraz init. Bezpośredni dostęp do zmiennej semaforowej jest zabroniony (bezpośredni odczyt lub zapis zmiennej).
Init nadaje wartość początkową semafora dla uproszczenia zapisu określiłem wartość semafora przy jego deklaracji.
Funkcja wait odczytuje i zmniejsza wartość semafora ogólnego w jednym kroku programu – niepodzielnie (operacja atomowa) a następnie w zależności od odczytanej wartości semafora pozwala wejść do sekcji krytycznej (wartość semafora większa od zera) bądź nie (wartość semafora nie większa od zera).
Funkcja signal odczytuje i zwiększa wartość semafora ogólnego w jednym kroku programu.
ad 1
Wykluczenie jednoczesnego przebywania producenta i konsumenta w tym samym miejscu magazynu
Zakładając że bufor (magazyn) jest rozmiaru M tworzymy dwa semafory jeden o wartości początkowej M a drugi o wartości początkowej zero. Oraz dwie zmienne (indeksy) mówiące, w której części bufora jest producent, a w której konsument.
Ogólna postać sekcji krytycznej:
wait(&semafor);
//sekcja krytyczna
signal(&semafor);
Postać konsumenta i producenta:
#define M 10 int buf[M]; Semafor miejsce_wolne=M; Semafor miejsce_zajęte=0; int i_kon=i_prod=0; void producent() { int produkt; produkuj(&produkt); wait(&miejsce_wolne); buf[i_prod]=produkt; i_prod++; i_prod%=M; signal(&miejsce_zajęte); } void konsument() { int produkt; wait(&miejsce_zajęte); produkt=buf[i_kon]; i_kon++; i_kon%=M; signal(&miejsce_wolne); konsumuj(&produkt); }
ad 2
Zawieszenie konsumpcji gdy magazyn jest pusty
Konsument wykonując polecenie wait(&miejsce_zajęte); sprawdza czy semafor miejsce_zajęte ma wartość większą od zera i zmniejsza jego wartość o jeden. Polecenie wykonane jest atomowo – niepodzielnie. Jeśli wartość semafora jest większa od zera wtedy proces wykonuje sekcje krytyczną i podnosi semafor miejsce_wolne (operacja signal dokonywana niepodzielnie- atomowo) pozwalając producentowi umieścić produkt w to miejsce. Jeśli wartość semafora jest nie większa od zera to konsument czeka na produkt (magazyn jest pusty). Dzieje się tak w przypadku jeśli konsument konsumuje szybciej niż producent zdąży wyprodukować.
ad 3
Zawieszenie produkcji gdy magazyn jest pełny
Producent wykonując polecenie wait(&miejsce_wolne); sprawdza czy semafor miejsce_wolne jest większe od zera. Jeśli tak oznacza to że jest jeszcze miejsce wolne w buforze i może dodać kolejny produkt do magazynu. W przeciwnym przypadku musi poczekać aż konsument skonsumuje jakiś produkt z magazynu. Producent po dodaniu produktu do magazynu podnosi semafor miejsce_zajęte o jeden (operacja wykonywana jest atomowo) informując konsumenta o nowym produkcie.
ad 4
Wzajemne wykluczanie kilku producentów
semafor_bin produkcja=0; //0-semafor wolny //1-semafor zajęty void producent() { int produkt,i_prod_temp; produkuj(&produkt); wait(&miejsce_wolne); wait_bin(&produkcja); i_prod_temp=i_prod++; i_prod%=M; signal_bin(&produkcja); buf[i_prod_temp]=produkt; signal(&miejsce_zajęte); }
ad 5
Wzajemne wykluczanie kilku konsumentów
semafor_bin konsumpcja=0; //0-semafor wolny //1-semafor zajęty void konsument() { int produkt,i_kon_temp; wait(&miejsce_zajęte); wait_bin(&konsumpcja); i_kon_temp=i_kon++; i_kon%=M; signal_bin(&konsumpcja); produkt=buf[i_kon_temp]; signal(&miejsce_wolne); konsumuj(&produkt); }
następna » |
---|