Programowanie współbieżne i rozproszone/PWR Wykład 1

Wstęp

Próba definicji

Praca współbieżna polega na tym, że składające się na nią zjawiska, czynności i działania odbywają się równocześnie. Istotny jest przy tym punkt widzenia obserwatora.

Zadaniem przedmiotu Programowanie współbieżne jest przedstawienie problematyki związanej z tworzeniem programów, w których wiele czynności może odbywać się równocześnie. Zajmiemy się przede wszystkim problematyką właściwej synchronizacji czynności składających się na program współbieżny i zagadnieniami związanymi z ich poprawnością.

Motywacja

Pisanie programów jest trudne. Jest to stwierdzenie prawdziwe już w przypadku programów sekwencyjnych, gdy na raz wykonuje się jedna instrukcja i nie trzeba rozważać wszystkich możliwych interakcji z innymi działającymi w tym samym czasie programami. Wprowadzenie współbieżności jeszcze bardziej utrudnia programowanie. Dlaczego zatem warto i należy rozważać programy współbieżne?

Odpowiedzieć na to pytanie można na wiele sposobów.

1. Niektóre problemy są z natury współbieżne, ich rozwiązania dają się łatwo i elegancko wyrazić w postaci niezależnie wykonujących się procedur. Przypuśćmy, że chcemy napisać grę akcji, w której wiele postaci porusza się na ekranie wykonując pewne działania. Taką scenę możemy oprogramować sekwencyjnie rozważając akcje wszystkich postaci w jednym fragmencie kodu. Jednak znacznie elegantszym rozwiązaniem jest oprogramowanie z osobna każdej postaci (można to zrobić obiektowo, nadając każdej z nich pewne indywidualne cechy), a następnie uruchomienie współbieżne tylu procesów, ile postaci chcemy uzyskać na ekranie. Oczywiście wymaga to także prawidłowej synchronizacji działania wszystkich procesów, co obejmuje działania takie jak na przykład wykrywanie kolizji i zapobieganie im.
2. Współczesne systemy operacyjne zezwalają na uruchamianie wielu procesów jednocześnie. Gdy pewien proces czeka na zakończenie operacji wejścia/wyjścia, to inny proces może być w tym czasie wykonywany. Ta możliwość współbieżnego wykonania sięga nawet dalej.
3. System operacyjny z podziałem czasu potrafi wykonywać wiele procesów współbieżnie dzieląc czas procesora między wiele procesów. Odbywa się to w ten sposób, że proces otrzymuje pewien kwant czasu (rzędu milisekund), w czasie którego korzysta z procesora. Gdy kwant skończy się, system operacyjny przełącza procesy: odkłada ten, który się wykonywał na później i zajmuje się innym. Ponieważ przełączanie odbywa się często, więc użytkownicy komputera mają wrażenie, że komputer zajmuje się wyłącznie ich procesem. Co więcej rozwiązując pewien problem, użytkownik może uruchomić "jednocześnie" dwa procesy, które ze sobą w pewien sposób współpracują. Jest to powszechnie stosowane na przykład w środowisku systemu operacyjnego Unix, który umożliwia wykonywanie programów w potoku, np.: ls -l | grep moje | more. Wszystkie trzy programy wchodzące w skład takiego potoku wykonują się współbieżnie z tym, że wyniki generowane przez pierwszy z nich są podawane na wejście drugiego, wyniki drugiego --- na wejście trzeciego itd.
4. Malejące ceny sprzętu sprzyjają powstawaniu architektur wieloprocesorowych, w których można uzyskać prawdziwą współbieżność, tzn. wykonywać jednocześnie wiele procesów na różnych procesorach. Wtedy system operacyjny nie musi już "oszukiwać" dzieląc czas jedynego procesora między wiele procesów, lecz może wykonywać każdy z nich na innym procesorze (przynajmniej dopóki wystarczy procesorów). Nowoczesne układy zawierają udogodnienia takie jak: wielowątkowość (hyperthreading), czy wręcz kilka rdzeni w jednej kości procesora.
5. Rozpowszechnienie się sieci komputerowych stwarza jeszcze inne możliwości współbieżnego wykonywania. Poszczególne obliczenia składające się na duże zadanie mogą być wykonywane na różnych komputerach połączonych siecią. Rozproszone systemy operacyjne potrafią zarządzać czasem wielu procesorów, znajdujących się w wielu różnych węzłach sieci.

A oto przykłady "prac", które można realizować współbieżnie.

1. Przypuśćmy, że chcemy obliczyć wartość wyrażenia $a\cdot b-(c+d)\cdot (e-f)$. Oczywiście można to robić od lewej do prawej, ale można też takie wyrażenie obliczać następująco:

Rysunek

Strzałki w powyższym grafie oznaczają kolejność czynności. Jednak nie wszystkie czynności są uporządkowane. Te, które znajdują się na różnych ścieżkach można wykonywać współbieżnie

1. Kolejny przykład to sortowanie tablicy N liczb. Sortowanie to można wykonywać za pomocą algorytmu sortowania przez scalanie:

procedure sortuj (i, j) { sortuje tablicą A[i..j] }
begin
  ...
  m := (i+j) div 2;
  sortuj (i, m);
  sortuj (m+1, j);
  scal (i, m, j);
end 

Zauważmy, że oba wywołania rekurencyjne procedury są tu niezależne od siebie --- dotyczą rozłącznych fragmentów tablicy. Nic nie stoi na przeszkodzie, aby były wykonywane w tym samym czasie: na różnych procesorach lub nawet na jednym z podziałem czasu. Taki równoległy algorytm możemy zapisać w postaci:

procedure sortuj (i, j) { sortuje tablicą A[i..j] }
begin
  ...
  m := (i+j) div 2;
  cobegin
    sortuj (i, m);
    sortuj (m+1, j);
  coend
  scal (i, m, j);
end 

Słowa kluczowe cobegin i coend oznaczają, że znajdujące się między nimi można wykonywać współbieżnie. Algorytm ten dobrze ilustruje również problem właściwej synchronizacji. Co stałoby się, gdybyśmy także wywołanie scal umieścili między cobegin i coend? Wówczas scalanie odbywałoby się współbieżnie z sortowaniem obu fragmentów tablicy. Wtedy scalanie mogłoby działać na jeszcze nie uporządkowanych fragmentach tablicy, co spowodowałoby niepoprawne działanie całego algorytmu. Na marginesie zauważmy, że w trakcie tego przedmiotu nie będziemy układać algorytmów równoległych. Zajmiemy się jedynie zagadnieniami związanymi z synchronizacją: problemami, mechanizmami i notacjami.

1. Współbieżność może także uprościć zapis programu. Na przykład przetwarzanie potokowe (wspomniane już uprzednio) łatwo zapisuje się współbieżnie:

cobegin
  while true do
  begin
    wczytaj znak z klawiatury;
    wypisz go do bufora
  end 
  while true do
  begin
    wczytaj znak z bufora;
    wypisz go na ekran
  end 
end 

Równoległość a współbieżność

Wspomnieliśmy o tym, że akcje współbieżne mogą być wykonywane faktycznie jednocześnie lub też (pod kontrolą systemu operacyjnego z podziałem czasu) fragment po fragmencie naprzemiennie z akcjami innego procesu. Opisując wykonanie pewnego procesu będziemy używać następującej terminologii:

1. Wykonanie sekwencyjne. Poszczególne akcje procesu są wykonywane jedna po drugiej. Dokładniej: kolejna akcja rozpoczyna się po całkowitym zakończeniu poprzedniej.
2. Wykonanie równoległe. Kilka akcji jest wykonywanych w tym samym czasie. Jest to "prawdziwa" współbieżność" możliwa do uzyskania na komputerze z wieloma procesorami.
3. Wykonanie w przeplocie. Choć jednocześnie odbywa się wykonanie tylko jednej akcji, to jednak jest wiele czynności rozpoczętych i wykonywanych na zmianę krótkimi fragmentami.
4. Wykonanie współbieżne. Kolejna akcja rozpoczyna się przed zakończeniem poprzedniej. Zauważmy, że nie mówimy nic na temat tego, czy akcje te są wykonywane w tym samym czasie czy też w przeplocie. Tak naprawdę wykonanie współbieżne jest abstrakcją równoległości i zawiera w sobie zarówno wykonania równoległe jak i wykonania w przeplocie.

Oto rysunek ilustrujący różne wykonania dwóch procesów.

Rysunek

Proces a program

Zanim przejdziemy do dalszego ciągu wykładu, przypomnijmy różnicę między procesem a programem. Program to obiekt statyczny --- tekst wykonywanego przez proces kodu. Proces to obiekt dynamiczny, "żywy", to wykonanie programu w pewnym środowisku lub wstrzymane wykonanie (w oczekiwaniu na jakiś zasób). Proces ma przydzielone zasoby (pamięć, urządzenia we/wy) i rywalizuje o dostęp do procesora. Procesy wykonują się pod kontrolą systemu operacyjnego. Przypomnijmy kilka najważdniejszych faktów dotyczących zarządzania procesami.

Założenia o środowisku działania programów

Każdy proces znajduje się w jednym z kilku możliwych stanów. Dokładna analiza tych stanów została przedstawiona na systemach operacyjnych. Do zrozumienia dalszego ciągu zajęć potrzebna nam będzie jednak wiedza o trzech możliwych stanach procesu:

Rysunek

1. Proces może być gotowy do wykonania. Oznacza to, że ma wszystkie potrzebne zasoby z wyjątkiem procesora. Gdy tylko otrzyma procesor może rozpocząć wykonanie.
2. Proces może być wykonywany, jeśli jest gotowy i ma procesor. Jest tyle procesów wykonywanych, ile procesorów znajduje się w systemie.
3. Proces wykonywany może zrzec się procesora i stać się wstrzymany, jeśli próbuje wykonać jakąś operacji, której nie może zrealizować natychmiast, bo na przykład nie ma niezbędnych zasobów. Klasycznym przykładem jest wykonanie operacji wejścia/wyjścia i konieczność poczekania aż niezbędne informacje zostaną sprowadzone z pamięci zewnętrznej. System operacyjny po sprowadzeniu niezbędnych zasobów zmieni stan procesu na gotowy.

Zauważmy, że w rywalizacji o przydział procesora biorą udział procesy gotowe. Zakładamy, że jeśli jakiś proces jest gotowy do wykonania, to w końcu stanie się wykonywany. Jest to bardzo ważne założenie, które będziemy nazywać sprawiedliwością systemu operacyjnego. Oznacza ono, że każdy proces, który ma niezbędne zasoby w skończonym czasie zacznie się wykonywać. Nie zdarzy się tak, że pewien proces P jest gotowy do wykonania i za każdym razem gdy dochodzi do przełączenia konktekstu, procesor otrzymuje inny proces. Bez założenia o sprawiedliwości systemu operacyjnego nie będziemy w stanie wykazać poprawności żadnego programu współbieżnego.

Zauważmy również