Title: Przetwarzanie równoległe i strumieniowe

PRS

Przetwarzanie równoległe i strumieniowe

Wykład 5

Klasyczne problemy synchronizacji procesów

Zaliczenie

Przetwarzanie równoległe

Problemy przetwarzania równoległego to problemy, które wymagają przetwarzania dużej ilości danych lub obliczeń,

które można podzielić na mniejsze, niezależne części i wykonywać równolegle na wielu procesorach lub rdzeniach.

https://www.reddit.com/r/ProgrammerHumor/comments/st360l/multi_mess/

Synchronizacja procesów

Synchronizacja procesów to proces koordynacji działania wielu procesów lub wątków, tak aby wykonywały swoje zadania w odpowiedniej kolejności i w sposób poprawny.

W przypadku programowania równoległego, synchronizacja procesów jest ważna, ponieważ wiele procesów może jednocześnie korzystać z tych samych zasobów, takich jak pamięć współdzielona, pliki lub urządzenia wejścia-wyjścia.

Sekcja krytyczna

Sekcja krytyczna to fragment kodu, który może być wykonywany tylko przez jeden wątek lub proces w danym czasie.

Sekcje krytyczne są często wykorzystywane w programowaniu równoległym, aby zapewnić bezpieczny i poprawny dostęp do współdzielonych zasobów, takich jak pamięć współdzielona, pliki lub urządzenia wejścia-wyjścia.

Sekcja krytyczna

W sekcji krytycznej wątek lub proces wykonuje określone operacje na zasobie, blokując tymczasowo dostęp do niego dla innych wątków lub procesów, które muszą czekać na zwolnienie zasobu przed wykonaniem swoich operacji.

Sekcja krytyczna powinna być krótka i zoptymalizowana, aby minimalizować czas blokowania dostępu do współdzielonych zasobów.

Sekcje krytyczne powinny być odpowiednio synchronizowane, zwykle za pomocą mechanizmów blokowania lub semaforów.

Sekcja krytyczna - przykład

Kolejka do okienka na poczcie może obrazować sekcję krytyczną.

Przy okienku może znajdować się i być obsługiwana tylko jedna osoba w danym momencie. Gdy osoba odchodzi od okienka reszta osówb zaczyna walczyć o dostęp do wolnego zasobu.

Problem synchronizacji w życiu

Problem „zbyt dużej ilości mleka”. Załóżmy, że dzielisz mieszkanie ze współlokatorem. Zdajesz sobie sprawę, że w lodówce nie ma mleka, a będąc dobrym współlokatorem, postanawiasz iść i kupić.

Twojego współlokatora nie ma w mieszkaniu, kiedy wychodzisz. Chwilę później, gdy jesteś jeszcze na zewnątrz, współlokator, który również jest miłym człowiekiem, postanawia również kupić mleko.

Teraz oboje kupujecie mleko, a mleka jest za dużo.

Jak to naprawić? Możesz np dokonać synchronizacji procesów poprzez umieszczenie notatki na lodówce!

Klasyczne problemy synchronizacji

https://www.memecreator.org/meme/what-are-u-studying-process-synchronization/

Problem producenta i konsumenta

W tym problemie istnieją dwa rodzaje procesów: producenci i konsumenci. Producent wytwarza produkty i umieszcza je w buforze, a konsument pobiera produkty z bufora i je konsumuje.

Problem polega na zaprojektowaniu algorytmu, który będzie koordynował pracę producentów i konsumentów, aby zapewnić poprawne działanie bufora.

Producent musi zaczekać, gdy bufor jest pełny, a konsument musi zaczekać, gdy bufor jest pusty.

Problem producenta i konsumenta

       +------------------------+
        |          Buffer        |
        |                        |
        |  +---+  +---+  +---+   |
        |  |   |  |   |  | X |   |
        |  +---+  +---+  +---+   |
        |                        |
        +------------------------+

          ^                     |
          |                     |
          |                     |
          |                     v
+-----------------+    +-----------------+
|    Producer     |    |     Consumer    |
+-----------------+    +-----------------+

Problem producenta i konsumenta

Proces producenta może wyglądać następująco:

1. Sprawdzenie, czy bufor nie jest pełny.
2. Jeśli bufor jest pełny, oczekiwanie na zwolnienie miejsca w buforze.
3. Wyprodukowanie nowych danych.
4. Umieszczenie nowych danych w buforze.

Problem producenta i konsumenta

Proces konsumenta może wyglądać następująco:

1. Sprawdzenie, czy bufor nie jest pusty.
2. Jeśli bufor jest pusty, oczekiwanie na pojawienie się nowych danych w buforze.
3. Pobranie danych z bufora.
4. Konsumowanie danych.

Problem producenta i konsumenta

Aby zapewnić poprawne działanie programu, proces producenta i konsumenta muszą być synchronizowane, tak aby uniknąć sytuacji, w których producent próbuje umieścić dane w pełnym buforze lub konsument próbuje pobrać dane z pustego bufora.

W tym celu, stosuje się odpowiednie mechanizmy synchronizacyjne, takie jak semafory, monitory, czy blokowanie sekcji krytycznych.

Rozwiązaniem tego problemu jest utworzenie dwóch semaforów zliczających „pełny” i „pusty”, aby śledzić aktualną liczbę elementów brakujących do przepełnienia i opróżnienia buforu.

Problem śpiącego fryzjera

Ten problem jest oparty na hipotetycznym zakładzie fryzjerskim z jednym fryzjerem.

Kiedy nie ma klientów, fryzjer śpi na swoim krześle. Jeśli jakikolwiek klient wejdzie, budzi fryzjera i siada na krześle dla oczekujących klientów. Jeśli nie ma wolnych krzeseł (kolejka jest pełna), klienci wracają do domu.

Kiedy fryzjer kończy z klientem, sprawdza, czy są jacyś oczekujący klienci. Jeśli tak, zaczyna strzyc kolejną osobę w kolejce. Jeśli nie ma oczekujących klientów, idzie spać.

Problem śpiącego fryzjera (pseudokod)

Lock fryzjerWolny
Lock blokadaKrzeseł
Semaphore czekajacychKlientów = 0
int liczbaWolnychKrzesel = N

def Barber():
    while true:
        acquire(czekajacychKlientów)
        acquire(blokadaKrzeseł)
        liczbaWolnychKrzesel += 1
        release(fryzjerWolny)
        release(blokadaKrzeseł)
        # ścinanie

def Customer():
    while true:
        acquire(blokadaKrzeseł)
        if liczbaWolnychKrzesel > 0:
            liczbaWolnychKrzesel -= 1
            release(czekajacychKlientów)
            release(blokadaKrzeseł)
            acquire(fryzjerWolny)
            # ścinanie
        else:
            release(blokadaKrzeseł)
            # ide do domu

Problem śpiącego fryzjera

Licznik dba o to, by czekających klientów nie było więcej niż krzeseł w poczekalni.

Operacje na poczekalni tworzą sekcję krytyczną i dlatego są synchronizowane.

Fryzjer jest wzbudzany przez czekającychKlientów i przechodzi do strzyżenia tylko gdy wie, że jest ktoś oczekujący w kolejce.

Problem jedzących filozofów

Problem jedzących filozofów polega na tym, że pięciu filozofów siedzi wokół okrągłego stołu i próbuje zjeść spaghetti. Pomiędzy każdymi dwoma filozofami jest widelec.

Filozof może jeść tylko wtedy, gdy trzyma w ręce oba widelce po swojej lewej i prawej stronie. Każdy filozof ma dwie czynności: jedzenie i myślenie.

https://en.wikipedia.org/wiki/Dining_philosophers_problem

Problem jedzących filozofów

Może dojść do blokady (ang. deadlock), gdy każdy filozof trzyma jeden widelec i czeka na drugi, który jest zajęty przez sąsiada.

Może również prowadzić do zakleszczenia (ang. livelock), gdy filozofowie stale próbują podnosić i odkładać widelce, a nigdy nie uda im się zjeść posiłku.

https://en.wikipedia.org/wiki/Dining_philosophers_problem

Problem jedzących filozofów

while True:
    # 1- myśl
    # 2- chwyć lewy widelec
    # 3- chwyć prawy widelec
    # 4- jedz
    # 5- odłóż lewy widelec
    # 6- odłoż prawy widelec

Działa tylko gdy jest 4 filozofów przy stole!

https://towardsdatascience.com/simulating-dining-philosophers-with-simpy-5abf5106e2ca

Problem jedzących filozofów

while True:
    # 1- myśl
    # 2- chwyć lewy widelec
    # 3- chwyć prawy widelec
    # 4- jedz
    # 5- odłóż lewy widelec
    # 6- odłoż prawy widelec

Filozof 1 - 4

while True:
    # 1- myśl
    # 2- chwyć prawy widelec
    # 3- chwyć lewy widelec
    # 4- jedz
    # 5- odłóż prawy widelec
    # 6- odłoż lewy widelec

5 filozof, rozwiązanie znane jako Chandy/Mishra Solution.

Problem jedzących filozofów - monitor

widelce ← [2,2,2,2,2]
lock array[0..4] jedz

def weźWidelec(integer i)
    if(fork[i]!=2):
        wait(jedz[i])

    fork[i+1] = fork[i+1]-1
    fork[i-1] = fork[i-1]-1

Każdy filozof:

 loop while(true) :
     p1 : myśl
     p2 : weźWidelec(i)
     p3 : jedz
     p4 : odłóżWidelec(i)

def odłóżWidelec(integer i) :
     fork[i+1] = fork[i+1]+1
     fork[i-1] = fork[i-1]
     if(fork[i+1]==2):
          notify(jedz[i+1])
     if(fork[i-1]==2):
          notify(jedz[i-1])

Problem czytelników i pisarzy

Mamy dwa rodzaje procesów: czytelników i pisarzy.

Dowolna liczba czytelników może jednocześnie czytać z udostępnionego zasobu, ale tylko jeden autor może pisać do udostępnionego zasobu.

Gdy program zapisujący zapisuje dane do zasobu, żaden inny proces nie może uzyskać dostępu do zasobu.

Pisarz nie może pisać do zasobu, jeśli w tym czasie jest niezerowa liczba czytelników uzyskujących dostęp do zasobu.

Problem czytelników i pisarzy

Pisarz

while(TRUE):
    wait(w)
    # pisz
    notify(w)

Czytelnicy

while(TRUE):
    wait(m);
    czytelnicy++;
    if(czytelnicy == 1): #pierwszy blokuje pisarza
        wait(w);
    notify(m);

    # Czytaj

    wait(m);
    czytelnicy--;
    if(czytelnicy == 0):
        notify(w);
    notify(m);

Przykłady praktyczne

- Producent-konsument

architektura serwera WWW: wątek zawartości lub serwera oraz wątek konsumenta lub przeglądarki
przesyłanie strumieniowe audio lub wideo: wątki sieci i odbiornika komunikują się za pośrednictwem wspólnego bufora

- Czytelnicy-pisarze

udostępniony plik na dysku, aplikacje bazodanowe

- Jedzący Filozofowie

zestaw procesów, które wymagają dostępu do wielu zasobów w tym samym czasie (np. plik i drukarka)