Problem producenta i konsumenta

Problem producenta i konsumenta – klasyczny informatyczny problem synchronizacji. W problemie występują dwa rodzaje procesów: producent i konsument, którzy dzielą wspólny zasób – bufor – dla produkowanych (i konsumowanych) jednostek. Zadaniem producenta jest wytworzenie produktu, umieszczenie go w buforze i rozpoczęcie pracy od nowa. W tym samym czasie konsument ma pobrać produkt z bufora. Problemem jest taka synchronizacja procesów, żeby producent nie dodawał nowych jednostek gdy bufor jest pełny, a konsument nie pobierał gdy bufor jest pusty.

Rozwiązaniem dla producenta jest uśpienie procesu producenta w momencie gdy bufor jest pełny. Pierwszy konsument, który pobierze element z bufora budzi proces producenta, który uzupełnia bufor. W analogiczny sposób usypiany jest konsument próbujący pobrać z pustego bufora. Pierwszy producent, po dodaniu nowego produktu umożliwi dalsze działanie konsumentowi. Rozwiązanie wykorzystuje komunikację międzyprocesową z użyciem semaforów. Nieprawidłowa implementacja powyższego algorytmu może skutkować zakleszczeniem.

Rozważać można również nieco uproszczoną wersję problemu – z buforem o nieograniczonej pojemności, a także trudniejszą – z większą liczbą producentów i konsumentów.

Rozwiązanie

W rozwiązaniu poniżej używamy dwóch semaforów: pusty oraz pełny. Semafor pusty jest opuszczany przed dodaniem do bufora. Jeśli bufor jest pełny semafor nie może być opuszczony i producent zatrzymuje się przed dodaniem. W następnym uruchomieniu konsumenta semafor jest podniesiony, co umożliwia producentowi dodanie jednostki do bufora. Konsument działa w analogiczny sposób.

semaphore pełny = 0
semaphore pusty = ROZMIAR_BUFORA

procedure producent() {
    while (true) {
        produkt = produkuj()
        down(pusty)
        dodajProduktDoBufora(produkt)
        up(pełny)
    }
 }

procedure konsument() {
    while (true) {
        down(pełny)
        produkt = pobierzProduktZBufora()
        up(pusty)
        użyjProdukt(produkt)
    }
}

Powyższe rozwiązanie działa poprawnie w przypadku, gdy istnieje tylko jeden producent i tylko jeden konsument. W czasie działania wielu procesów może dojść do próby jednoczesnego odczytania bądź zapisania produktu w buforze w tym samym miejscu.

Zobacz też

• problem czytelników i pisarzy
• problem ucztujących filozofów

Bibliografia

• Wykłady z systemów operacyjnych (wazniak.mimuw.edu.pl)
• The Little Book of Semaphores, Allen B. Downey, wydanie 2