Modele Współbieżności

Współbieżność - sposób wykonywania zadań, w którym klient systemu ma wrażenie że zadania wykonywane są jednocześnie. Istnieją dwa podstawowe modele współbieżności - thread-based concurrency oraz event-driven concurrency. Modele te różnią się mechanizmem zapewniania przeplotu zadań - pierwszy z nich bazuje na wątkach, drugi na obsłudze zdarzeń. Najpopularniejszym mechanizmem współbieżności jest model oparty na wątkach i na nim skupimy się analizując problemy i zagadnienia współbieżności.

Pożądane właściwości modelu

Współbieżność jest jedną z taktyk podnoszenia wydajności systemu, dzięki której sekwencyjne, powolne przetwarzanie zadań możemy zastąpić dużo bardziej wydajnym przetwarzaniem współbieżnym. Najbardziej pożądaną właściwością związaną z wydajnością jest tzw graceful degradation.

_Graceful degradation oznacza, że mimo wzrostu obciążenia współbieżnej usługi ponad pojemność systemu, przepustowość pozostaje wciąż na jednakowym poziomie a czasy odpowiedzi rosną nie szybciej niż liniowo. _

Należy zaznaczyć, że nie jest to cecha typowa dla aplikacji webowych, gdzie zazwyczaj wydajność usługi gwałtownie spada gdy obciążenie przekroczy pojemność systemu.

Problemy związane ze współbieżnością

Główne problemy współbieżności, które należy uwzględnić podczas projektowania aplikacji współbieżnych

  • zapewnienie spójności danych

  • zakleszczenie

  • zagłodzenie

Zapewnienie spójności danych

Zapewnianie spójności danych jest jednym z podstawowych problemów współbieżności:

  • Wątki utworzone na podstawie tego samego procesu współdzielą przestrzeń adresową

  • Model wywłaszczeniowy powoduje, że wątki mogą być wywłaszczone w dowolnej chwili, co może prowadzić do sytuacji, że dany wątek pozostawi dane w niespójnej postaci.

  • Sytuacja, gdy dwa wątki wykonują operacje na tych samych danych nazywamy interferencją wątków inaczej zwaną także wyścigami

Poniżej scenariusz obrazujący taką sytuację

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Counter {
    private int cnt = 0;
    public void increment() {
        int cnt2 = cnt; // 1
        cnt = cnt2 + 1; // 2
    }

    public void decrement() {
        int cnt2 = cnt;
        cnt = cnt2 - 1;
    }

    public int value() {
        return cnt;
    }
}
  1. Wątek A wykonuje metodę increment() na obiekcie typu Counter

  2. W momencie oznaczonym komentarzem „1” zostaje on wywłaszczony przez Scheduler. Na jego stosie zmienna cnt2 posiada wartość 0

  3. Wątek B otrzymuje procesor i także wykonuje metodę increment() na tym samym obiekcie typu Counter

  4. Po wykonaniu metody increment() przez wątek B zmienna cnt przyjmuje wartość 1

  5. Wątek A otrzymuje procesor i kończy metodę increment(). Do zmiennej cnt zostaje zapisana wartość 1 jako, że na stosie wątku A zmienna cnt2 ciągle posiada wartość 0

Sekcja krytyczna

Jednym ze sposobów zapewniania spójności danych podczas przetwarzania współbieżnego jest wydzielenie tzw sekcji krytycznej czyli fragmentu przepływu sterowania, który może być wykonywany tylko przez jeden wątek w danym czasie. Pozostałe wątki chcące uzyskać dostęp do sekcji krytycznej muszą poczekać na odpowiednie pozwolenie. Sekcję krytyczną można uzyskać dzięki zastosowaniu mechanizmu monitorów bądź semaforów.

Model sekcji krytycznej przedstawia poniższy diagram sekwencji. Na diagramie przedstawiłem dwa wątki konkurujące o dostęp do sekcji krytycznej pewnego obiektu.

Zakleszczenia

Zakleszczenie jest to sytuacja, w której dwa (lub więcej) wątki czekają na siebie wzajemnie. Sytuację przedstawia poniższy diagram czynności. Na diagramie przedstawione są dwa wątki wykonujące czynność oczekiwania na dane z drugiego wątku. Akcja oczekiwania będzie wykonywana w nieskończoność, ponieważ żaden wątek nie otrzyma danych od wątku drugiego.

Zagłodzenia

Zagłodzeniem nazywamy sytuację, w której niektóre wątki nie otrzymują przez długi czas (albo w ogóle) dostępu do współdzielonego zasobu - mówimy że są zagłodzone. Sytuację najczęściej można zaobserwować gdy operacje w sekcji krytycznej są długotrwałe, co uniemożliwia dostęp do niej przez inne wątki.

Sytuację zagłodzenia przedstawia poniższy diagram. Jak widać wątek thread3 jest zagłodzony przed pozostałe wątki thread1 i thread2 ponieważ nie może uzyskać dostępu do sekcji krytycznej.

Klasyczne problemy

Mechanizmy współbieżności

Algorytm Dekkera

Algorytm Petersona

Semafor

Monitor

Blokada

Bariera

Comments