Czy współbieżność to równoległość ?

Dziś temat iście akademicki, który może wydawać się banalny. Zauważyłem jednak, że programiści dyskutując o współbieżności często używają wymiennie terminu równoległości. Czy wobec tego są to pojęcia tożsame? Nie do końca. Oba te „twory” radzą sobie dobrze razem, jak i oddzielnie. Żeby jednak tematyka nie zrobiła się nazbyt poważna (tym samym niezrozumiała), omówmy przykład, który mam nadzieję trochę nam wszystkim rozjaśni w głowach. Wyobraźmy sobie, że naszym zadaniem jest zorganizowanie turnieju szachowego, w którym 10 amatorów będzie miało szanse zagrać z arcymistrzem. Ten, kto pokona przeciwnika, wygrywa (zakładamy możliwość wygrania przez kilka osób). Założenia są następujące:

  • Uczestników turnieju jest 10.
  • Każdy uczestnik może zagrać z arcymistrzem tylko jeden raz .
  • Dla uproszczenia przyjmijmy, że czas ruchu arcymistrza wynosi 10 sek, a amatora 50 sekund (zawsze).
  • Każda gra trwa maksymalnie 20 min.

Przed nami stoi teraz zadanie organizacji partii, aby turniej odbył się możliwie szybko.

 

Wykonanie sekwencyjne

Naszym pierwszym pomysłem jest odbywanie jednej partii po drugiej. Zawodnik siada na stanowisku, gra z arcymistrzem 20 min, po czym wchodzi następny uczestnik zmagań. Pomysł choć prosty, nie jest najlepszy. Zauważmy, że partia może mieć maksymalnie 20 tur, z tego blisko 83% czasu przypada na ruch amatora, a jedynie 17% dla arcymistrza. Łatwo licząc widzimy, że czas trwania turnieju wynosi w tym przypadku 200 min. Sprowadzając problem do informatyki możemy powiedzieć, że każda partia to jedno zadanie do wykonania, a nasz plan jest najzwyklejszym przetwarzaniem sekwencyjnym tzn. jedna operacja musi zostać zakończona, aby rozpocząć kolejną. Poniżej prosta ilustracja, która to obrazuje:

 

sample1

 

Przy tej okazji warto wspomnieć, że procesory jedno-rdzeniowe w chwili t są w stanie wykonać na raz tylko jedno zadanie.

 

Wykonanie współbieżne

No dobra, pierwsza próba nie należała do najlepszych, ale w naszej głowie narodziła się kompletnie inna koncepcja. Skoro tyle czasu arcymistrz marnuje oczekując na ruch rywala, może lepszym rozwiązaniem będzie dla niego rozegranie wszystkich partii na raz? Zauważcie, że nie użyłem zwrotu ” w tym samym czasie”. Plan jest następujący, ustawiamy dziesięć stołów obok siebie, a arcymistrz podchodzi po kolei do każdego wykonując swój ruch. Po odbyciu jednego cyklu powraca na pierwsze stanowisko. Dla ułatwienia obliczeń załóżmy, że czas przejścia do kolejnego stołu jest zerowy. Zauważmy co się teraz dzieje. Czas trwania jednego cyklu dla szachowego guru wynosi 100 sek. Do momentu gdy powróci do tej samej osoby, rywal zdąży już wykonać ruch (100 > 50). Zgodnie z naszymi poprzednimi obliczeniami wiemy, że maksymalnie jesteśmy w stanie rozegrać 20 tur. Cały turniej rozegramy zatem w 2000 sekund, czyli ok. 33 min. Poniżej obrazek, który ilustruje nasz aktualny pomysł:

 

sample2

 

W tym momencie ktoś mógłby powiedzieć: „Chwila, dopiero co napisałeś, że jeden rdzeń w chwili t jest w stanie wykonać tylko jedną czynność! A przecież kiedy arcymistrz myśli nad swoim ruchem to pozostała dziesiątka także to robi”. W takim razie ja zadam pytanie. Jak to możliwe, że 15 lat temu nasze komputery (z procesorami jedno-rdzeniowymi) były w stanie jednocześnie odtwarzać film, muzykę oraz renderować kursor kiedy ruszaliśmy myszką? Musimy zdać sobie sprawę, że nasz procesor posiada tzw. CPU time, czyli czas dostępu do niego (mierzony w tzw. clock tick, czyli najmniejszej, sprzętowej jednostce czasu). Zakładając, że każda z czynności zostanie uruchomiona na osobnym wątku, procesor (w dużym uproszczeniu) wykona w ramach CPU time część jednego zadania, po czym przełączy się na inne zadanie (jest to tzw. context switching). Dodatkowo weźmy pod uwagę, że wszystkie czynności generują pewien czas oczekiwania na urządzenia WE/WY np. wyrenderowanie piksela na monitorze czy oczekiwanie na zmianę położenia głowicy dysku twardego. Delegując takie zadania procesor nie „stoi w bezruchu”, ponieważ nie ma na to czasu, a zamiast tego wykonuje kolejną „porcję” innego zadania. W ogólnym rozrachunku takie skakanie daje wrażenie wykonywania operacji w tym samym czasie. Widzicie już analogię ? W naszym przykładzie z turniejem, arcymistrz jest rdzeniem procesora, a amatorzy są zadaniami. Ze współbieżnością jest związanych wiele pojęć jak zagnieżdżenia, zakleszczenie, zagłodzenia wątków, sekcja krytyczna czy choćby semafory i mutexy. Jeżeli temat wyda się wam ciekawy to dajcie znać w komentarzach, a ja postaram się wyprodukować kolejne wpisy 🙂

 

Wykonanie równoległe

Druga opcja wydaje się całkiem dobra, ale znów doznajemy olśnienia. Na turniej zaprosimy dwóch arcymistrzów, a partie będą odbywały się równocześnie na dwóch stołach jedna po drugiej. Jak widać w tym przypadku całkowity czas imprezy wyniesie już 100 min, czyli dwa razy mniej od pierwotnego planu. Tutaj możemy już powiedzieć o równoległości, którą ilustruje poniższy rysunek:

 

sample3

Posiadając dwa rdzenie (arcymistrzów) dopiero teraz, możemy faktycznie wykonywać dwie czynności na raz.

 

Wykonanie współbieżne i równoległe

Przyszedł czas na ostatnią możliwość. Co by było gdyby połączyć dwa poprzednie pomysły? Moglibyśmy przecież sprawić, aby każdy z guru rozegrał w tym samym czasie pięć partii na raz! Wówczas długość cyklu dla jednego z nich wynosiłaby 50 sek (5 * czas na zastanowienie się równe 10 sek). Mnożąc to przez 20 partii, otrzymujemy 1000 sekund czyli ok. 17 min. To spora różnica w porównaniu do początkowych 200 min. Poniżej wersja graficzna:

 

sample4

Zwróćcie uwagę na to co osiągneliśmy. Każdy z rdzeni działa równolegle w tym samym czasie, jednocześnie uruchamiając powierzone mu zadanie współbieżnie.

 

Myślę, że temat doskonale dopełnią słowa Roba Pike-a:

 

Concurrency is about dealing with lots of things at once. Parallelism is about doing lots of things at once.

 

To jest istota tych dwóch zagadnień. Dobrze przemyślana współbieżność może zostać dodatkowo zrównoleglona, ale nie musi.

 

Powiem szerze, że mi osobiście bardzo podeszła tematyka, bo przypomniałem sobie wiele ciekawych zagadnień ze studiów. Tak jak wspomniałem, jeżeli Wy także jesteście zainteresowani to dajcie znać ! Póki co mogę polecić obejrzenie prezentacji Roba pt. „Concurrency is not Parallelism”.  Link macie tu. Jak zwykle zachęcam Was do śledzenia mnie na twitterze facebooku, gdyż to własnie tam pojawiają się informacje o kolejnych wpisach 🙂 A my spotykamy się na blogu w środę, gdzie pojawi się kolejny odcinek DevReview !

Cześć !

 

You may also like...