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 przedmioty nie będziemy układać algorytmów równoległych. Zajmiemy się jedynie zagadnieniami związanymi z synchronizacją: problemami, mechanizmami i notacjami.