Multithreading, parallelism, concurrency

Myślą przewodnią były różne podejścia do współbieżności (concurrency), równoległego wykonywania zadań (parallelism), i wielowątkowości (multithreading). Już na samym początku zaznaczone zostało, że to są różne rzeczy, a ja może przy okazji pokażę kilka obrazków, na których widać te różnice. Obrazki pochodzą z wpisu Understanding Async, Non-Blocking, Concurrent, Parallel and More na blogu Typesafe, a słowa kluczowe, które pozwoliły mi go ponownie odnaleźć, to concurrency, parallelism, multithreading i… dishwashing.

Na początku jest proces samodzielnego zmywania naczyń. Czyli po kolei: biorę talerze, spłukuję je wodą, potem zdrapuję resztki jedzenia, jeszcze raz spłukuję, a potem wstawiam do zmywarki. Zauważ, że biorę po kilka talerzy, więc już dokonuję jakiejś tam optymalizacji. (Wiem, możesz robić całkiem inaczej, sam robię inaczej i ciągle nie mam zmywarki, ale przykład przykładem, pochodzi z bloga Typesafe).

Co mogę zrobić? Wprowadzić nowy wątek, żeby zmywanie przebiegało szybciej. Przechodzimy do multithreading.

Mamy już kilka wątków, czyli spełniamy definicję wielowątkowości. A że jeden czeka i nie może dopchać się do procesu zmywania naczyń? Zatrzymajmy się na chwilę.

Taka sytuacja może mieć miejsce, kiedy mamy tylko jeden procesor, albo kiedy nie do końca dobrze zaprojektowaliśmy aplikację. Może być jednocześnie obsługiwanych wiele wątków, ale tylko jeden w danym czasie faktycznie coś robi. Czyli może dojść do sytuacji, kiedy mamy aplikację, która jest wielowątkowa, ale nieefektywnie korzysta z wielu wątków. Pomyśleliśmy o wielowątkowości (multithreading), ale nie pomyśleliśmy o zrównolegleniu operacji (parallelism).

Żeby jeszcze bardziej uwypuklić tę różnicę pomiędzy wielowątkością, a przetwarzaniem równoległym: zauważ, że możemy mieć aplikacją wielowątkową na maszynie jednoprocesorowej (z jednym wątkiem procesora). Wtedy też, mimo wielowątkowości, nie może być mowy o przetwarzaniu równoległym.

Na obrazku mężczyzna być może poczeka, aż kobieta włoży do zmywarki część naczyń (aż skończy wykonywać sekwencję działań), a potem się zamienią. Jednak ciągle nie mogą wykonywać tych czynności równocześnie. Co można zmienić?

Przechodzimy na nowy model, udaje nam się zmywać naczynia we dwójkę. Jeden z prostych przykładów, jak możemy do tego dojść: fork i join, znany na przykład z Javy.

Ponieważ udało nam się wygospodarować dwa stanowiska do zmywania naczyń, mamy wreszcie przetwarzanie równoległe (parallelism). Dwa wątki (mężczyzna i kobieta), w tym czasie robią to samo. Trzeba tylko pamiętać o tym, żeby włożyć wszystko do jednej zmywarki.

A współbieżność? To coś bardziej ogólnego.

Współbieżność nie wymaga faktycznie jednoczesnego przetwarzania zadań. Można mówić nawet o współbieżności na jednym procesorze, gdzie nie ma możliwości wykonywania kilku operacji jednocześnie. W zasadzie można nawet znaleźć opinie, że wielowątkowość i współbieżność to to samo. A nie do końca.

Meetup #96

Meetup #96 składał się w sumie z siedmiu prezentacji. Dla porządku poniżej wrzucam linki do poszczególnych pojęć i prezentujących:

1. Prezentacja wprowadzająca – Tomasz Borek
2. Actor Model – Marcin Piotr Miszczyk
3. Communicating Sequential Processes – Marcin Kostrzewa
4. Software Transactional Memory – Konrad Garus
5. Threads and Mutexes – Tomasz Borek
6. Data Parallelism – Andrzej Brożek
7. Lambda Architecture – Norbert Wójtowicz

Prezentacje są raczej w kolejności, w jakiej się pojawiały, nie jestem tylko pewien czwórki i piątki, być może były odwrotnie.

Actor model

Jeśli rozważamy współbieżność, warto wprowadzić jeszcze jedno pojęcie, pojęcia asynchroniczności. W uproszczeniu: jeśli coś jest synchroniczne, czekamy na rezultat. Jeśli coś jest asynchroniczne, możemy poczekać na część rezultatu, potem na kolejną część i tak dalej.

Kiedy na początku tego wpisu pokazałem dwa obrazki, jeden miał podpis “synchroniczny”, a drugi “asynchroniczny”. Zobacz jeszcze raz:

Zwróć uwagę, że oba procesy nie są wykonywane równolegle. Tym, co je tak naprawdę różni jest to, że w drugim przypadku zmywający mogą się zmienić. Zatem nie musimy przeprowadzić procesu zmywania naczyń od początku do końca. Nie musimy zrobić wszystkiego naraz.

W ten podział na kawałki można wejść głębiej i usprawnić proces zmywania naczyń. Można na przykład rozdzielić poszczególne czynności z procesu zmywania naczyń, o tak:

Ten przykład można łatwo rozpisać na modelu aktorowym. Już chyba samo nasuwa się, że mamy dwóch aktorów, kobietę (K) i mężczyznę (M). Ci aktorzy mogą obsługiwać zdarzenia, które do nich docierają. W naszym procesie zmywania naczyń zdarzeniami będą brudny talerz (t_br) i talerz wstępnie oczyszczony (t_wo)

Kobieta bierze brudne talerze, wstępnie je płucze, usuwa resztki jedzenia i odkłada. Mężczyzna bierze wstępnie oczyszczone talerze, jeszcze raz je płucze i wkłada do zmywarki. Czyli przekładając to na język aktorów: K przyjmuje zdarzenia t_br, przetwarza je na zdarzenie t_wo i przesyła M. M przyjmuje zdarzenia t_wo i je przetwarza.

Oczywiście poprzedni przykład (kiedy mężczyzna czeka) też można opisać na modelu aktorowym. Znów mamy dwóch aktorów, K i M, i mamy też zdarzenia t_br, które każdy z aktorów może przeprowadzić do końca. Więcej, a w zasadzie wszystko, dzieje się wewnątrz aktorów.

(dygresja osobista)

Kiedy po raz pierwszy, w sumie już jakieś 6-7 lat temu, zetknąłem się z modelem aktorowym programowania współbieżnego, zapragnąłem nauczyć się Erlanga. Jeszcze jako student, przeładowany byłem nie do końca zrozumiałymi pojęciami wątków, muteksów i tym podobnych. Kiedy dowiedziałem się o lekkich wątkach i przesyłaniu komunikatów, zamiast synchronizacji wątków, doznałem obiawienia.

W zasadzie od tego zaczęła się moja historia ze Scalą. Kilka miesięcy potem zrobiłem pierwszy eksperyment, porównujący dwie technologie. Wyświetlałem na standardowym wyjściu komunikaty pochodzące z różnych wątków, takie rozproszone Hello World. W Javie to były chyba trzy klasy i ponad dwieście linijek kodu. W Scali – czterdzieści osiem linijek. (Sprawdziłem na Wikipedii: pierwsza wersja Akka wyszła w lipcu 2009, więc pewnie wydarzyło się to wszystko jakoś w 2010 roku).

Po dwóch latach, kiedy w zasadzie nie miałem ze Scalą kontaktu, zrobiłem na Courserze Functional Programming Principles in Scala, które diametralnie zmieniło moje podejście do programowania. Jakiś czas później skończyłem Reactive Programming, który był częsciowo poświęcony Akka, potem byłem już na prezentacjach z Akka kilka razy, raz nawet prowadzonej przez samego Jonas Bonéra, kiedy przygotowywał się przed Geekonem w Krakowie, więc trudno powiedzieć, żebym dowiedział się czegoś nowego.

Niemniej jednak podobała mi się prezentacja o Aktorach. Marcin Piotr Miszczyk pokazywał proste programiki w Erlangu i opowiadał o zaletach korzystania z tego modelu współbieżności.

To co z tą współbieżnością?

Przekładając wprost na polski słowa z jednego z wątków na Stack Overflow: Współbieżność jest wtedy, kiedy dwa zadania mogą się rozpocząć, trwać i zakończyć w nakładających się na siebie przedziałach czasu. (Zauważ, że to wcale nie znaczy, że coś musi się dziać równocześnie).

Wróćmy do przykładu z fork join:

Dla tego przykładu możemy rozpatrywać współbieżność przede wszystkim w kontekście tego, co się stanie, kiedy jednocześnie mężczyzna i kobieta będą chcieli włożyć naczynia do zmywarki. To jest potencjalne miejsce konfliktu, kiedy dwa wątki potrzebują w tym samym czasie dostępu do tego samego zasobu. Dany system będzie współbieżny (przypominam: concurrent), kiedy będzie mógł sobie z taką sytuacją poradzić.

Wróćmy jeszcze do przykładu z podziałem odpowiedzialności, na którym opisałem na modelu aktorowym:

Zarówno w fork join, jak i tutaj można jeszcze mówić o współbieżności na poziomie całego procesu. Czy może dojść do sytuacji, kiedy do procesu wchodzą nowe naczynia, a poprzednie jeszcze nie znalazły się w zmywarce? Jeśli mogą, możemy mówić o współbieżności.

Gdybym miał w kilku prostych słowach podumować różnicę pomiędzy tymi trzema pojęciami:

• Wielowątkowość (multithreading) – zdolność do wykonywania w wielu wątkach (nacisk na izolację).
• Przetwarzanie równoległe (parallelism) – proces równoczesnego wykonywania operacji (nacisk na równoczesność).
• Współbieżność (concurrency) – zdolność do obsługi wielu zapytań jednocześnie (nacisk na komunikację).

I na koniec jeszcze dwa pytania, nad którymi możesz się zastanowić: Co może być współbieżne i wielowątkowe, ale nie ma w nim przetwarzania równoległego? Co może być współbieżne, ale ani nie jest wielowątkowe, anie nie ma w nim przetwarzania równoległego?

O kilku innych prezentacjach

W prezentacji Communicating Sequential Processes było o czymś, czego jeszcze nie znałem, a tylko gdzieś obiło mi się o uszy; o modelu programowania współbieżnego, gdzie anonimowe nie są komunikaty, ale aktorzy. W taki sposób działają właśnie channels w Go. Nie miałem do tej pory jeszcze rozeznania w tym podejściu, więc podążanie za tokiem prezentacji okazało się stosunkowo trudne. Źródło, które wydaje się być dobre na początek, to ta prezentacja i wideo do niej.

W Threads and Mutexes, która też była dość ciekawa, dowiedzieliśmy ponownie, że programowanie wielowątkowe jest strasznie trudne i bardzo łatwo w nim coś zepsuć.

Lambda Architecture to była prezentacja z gatunku tych inspirujących. Mało tekstu, dużo obrazków i dużo ciekawego opowiadania. Podejście całkiem inne niż w pozostałych prezentacjach, bardziej ogólne. Dużo materiałów można znaleźć na stronie innego spotkania: Meetup #85 - Lambda Architecture.

Do poczytania

• O zmywaniu naczyń z blogu Typesafe: Understanding Async, Non-Blocking, Concurrent, Parallel and More
• Wideo Concurrency is not Parallelism z konferencji Waza 2013 (+ prezentacja)
• Dyskusja na Stack Overflow
• Między innymi o tym, jak się ma concurrency do mulithtreading: Concurrency vs Multi-threading vs Asynchronous Programming : Explained
• O mitologii, która kryje się za Akka: Akka (spirit). Serio. Wiedzieliście, że Akka to duch w mitologii fińskiej i lapońskiej?

Przykładowe odpowiedzi na pytania

1. Np. system operacyjny na maszynie jednoprocesorowej.
2. Np. JavaScript w przeglądarce internetowej (nie zawsze, ale generalnie; por: Stack Overflow). Albo sposób, w jaki piszę tego bloga: jednocześnie mogę zajmować tylko jednym wpisem, choć mam kilka niedokończonych.