Saturday, June 5, 2010

Porównanie systemów: procesy i wątki

Ehh, zazwyczaj unikam tego tematu bo uważam, że porównywanie takich systemów jak Windows i Linux ma się tak do siebie, jak porównywanie samochodu osobowego z autokarem. Dlaczego? Bo według literatury informatycznej poświęconej budowie systemów operacyjnych na podstawie, której opracowałem ten wpis – system Windows to „jednoużytkownikowy wielozadaniowy system operacyjny”, o! Do wersji Serwer może się zalogować wiele osób jednocześnie. Wracając jeszcze do tych porównań, których ostatnio bardzo wiele widziałem w sieci typu: FreeBSD okiem linuksiarza, Linux okiem użytkownika FreeBSD, czy dlaczego Apple, którego sukcesu zresztą nie rozumiem mimo, iż mam z tymi komputerami do czynienia prawie na co dzień. Porównania te są pełne pasji, zapału i kontrowersyjnych wyzwań i zarzutów, na podstawie których można by było stworzyć oddzielne religie dla użytkowników każdego z tych systemów. W żadnym jednak nie przeczytałem o tym czym tak naprawdę różnią się wewnętrzne mechanizmy tych systemów operacyjnych i dlaczego jedne z nich są lepsze, a inne gorsze. Dlatego postanowiłem poruszyć sam ten temat na swoim blogu, ale pod kątem niestety niepraktykowanym jak dotąd w sieci. Tyle o motywacji, mam nadzieję, że znajdę w przyszłości czas aby opisywać kolejne mechanizmy w różnych systemach. Aha i jeszcze jedno. Opisując te zagadnienia wiem, że nie będzie to wystarczające wyjaśnienie poruszanej problematyki, bo jak to mawiał mój wykładowca od systemów operacyjnych „...a tam jest co robić” ;) Więc jeżeli kogoś poruszane zagadnienia poruszą to polecam kupić sobie książkę o tym – sam tak zrobiłem.

Teraz troszkę wprowadzenia do problematyki budowy systemów operacyjnych, bez którego czytelnik może nie docenić istoty opisywanych rozwiązań. System operacyjny to przede wszystkim sposób na wydajne zarządzanie zasobami na rzecz programów użytkownika. Przy czym należy zaznaczyć, że podczas wyboru metody użycia ograniczonych zasobów nie ma wyborów nieponoszących kosztów w rozumieniu zasobów sprzętowych, czasu bądź innych cennych elementów pracy komputera..

W tym wpisie opiszę troszkę procesy oraz wątki. Proces oznacza przestrzeń roboczą wykonywanego programu w pamięci komputera w obrębie której może on się poruszać. Wątki z kolei wiążą się z wykonywaniem tego samego programu jednocześnie w ramach jednego procesu. Tak brzmi mniej więcej definicja obu tych pojęć lecz obecnie granice między nimi trochę się zamazały. Przed chwilą użyłem słowa jednocześnie – no właśnie, i tu zaczyna się problem. Często używa się w systemach operacyjnych określenia współbieżność. Tak naprawdę te wykonywanie jednocześnie wielu rzeczy przez komputer to pewnego rodzaju złudzenie wynikające z ogromnych różnic w prędkości pracy procesora oraz ludzkiego oka. Aby lepiej to zobrazować narysowałem piękny rysunek.
Ten pierwszy przedstawia jak wykonywane są w rzeczywistość procesy przez system operacyjny na maszynie z jednym procesorem. Jak widzimy polega to na sekwencyjnym przetwarzaniu kolejnych procesów, gdzie między ich zmianą występuje coś co fachowo nazywa się zmianą kontekstu. Ten kawałek czasu reprezentuje pracę systemu. Czyli w analizowanym okresie czasu procesor nie zajmował się tylko wykonywaniem rozkazów naszych programów, wiele czasu zostało przeznaczone na pracę systemu operacyjnego. Mały przykład z konsoli wzięty:

grzesiek@home:~$ time icedove  
  
 real    0m19.292s 
 user    0m2.928s 
 sys     0m0.496s

Jak widać uruchomiłem klienta poczty, sprawdziłem pocztę i zakończyłem jego pracę mierząc czas jego działania. Jak rozumieć te wartość:
real – to rzeczywisty okres czasu w jakim program był uruchomiony ale widziany okiem użytkownika
user – to suma sekund jaką procesor rzeczywiście poświęcił na przetwarzania programu w trybie procesu uruchomionego gdzie procesor pracował w trybie użytkownika tzw. user mode
sys – to łączny czas pracy procesora w trybie systemu (czyli przez system) na rzecz wykonywanego programu, inaczej mówiąc jest to koszt działania, który jest przedmiotem optymalizacji programistów systemów operacyjnych.

Teraz policzymy jak bardzo ważna jest jakość system operacyjnego dla użytkowania komputera: 0.496/(2.928/100)=16,93989071 – prawie 17% czasu pracy procesora jest zużywana na sam mechanizm wykonywania programu jakim jest system operacyjny. To prawie 1/5, ale tylko w tym przypadku – nie jest to statystyka ogólna. W tych przykładowych 17% znajdują się wykonywane procedury systemu, z których korzysta program użytkownika. Dzieje się tak, ponieważ wiele operacji np. na sprzęcie dla bezpieczeństwa może wykonywać tylko jądro w tak zwanym trybie uprzywilejowanym, program musi poprosić o to system, aby ten np. odczytał dane z dysku w jego imieniu. Do tego wlicza się również przedstawiana na schemacie zmianę kontekstu.
Chyba udało mi się dobrze przedstawić zasób, który jest przedmiotem minimalizacji podczas projektowania systemu operacyjnego – to między innymi zmiana kontekstu. Jak wspomniałem to wszystko jest bardzo złożonym procesem i zainteresowanych odsyłam do książek.

Wracamy do rysunku, tym razem do drugiego schematu przedstawiającego prawdziwe symetryczne przetwarzanie wielu procesów. Tym czymś co łączy dwa procesory jest SMP (ang. Symmetric Multiprocessing). Nie będę się o tym rozpisywał. W tym schemacie błędnie przedstawiłem czas zmiany kontekstu procesów na obu procesorach, ponieważ odbywa się on jednocześnie w tym samym czasie. W pewnym sensie jest to możliwe, ale to już inna bajka. Po prostu łatwiej było mi go przygotować modyfikujące nieznacznie pierwszy schemat.

Teraz przejdziemy do sedna tego wpisu. Mimo, iż zasadniczo watki są podrzędne procesom to od nich zaczniemy. Na początku w systemach nie było wątków, były tylko procesy, które w systemie reprezentowały uruchomione aplikacje. Wątki oraz pojęcie wielowątkowości wprowadzono z kilku powodów. Po pierwsze umożliwiają złożonym programom wykonywanie symetrycznie dwóch czynności, np. programy do grafiki – w jednym wątku wykonuje obliczenia, a w drugim obsługuje graficzny interfejs użytkownika. Wiele produktów firmy Adobe tak działa. Pamiętajmy jednak, że na maszynie z jednym procesorem wielowątkowość nie oznacza rzeczywiście równoczesnego przetwarzania. Po drugie wątki umożliwiają niezależnie od wiedzy systemu na rozwidlenie kodu aplikacji dla programisty. Mowa tu o wątkach w przestrzeni użytkownika. To biblioteka, która działa jak każdy inny program i umożliwia wielowątkowe przetwarzanie. System zarządza procesem w takim przypadku ale nic nie wie o tym, że w procesie ma miejsce rozwidlenie wykonywanego kodu.
W końcu, po trzecie wątki poprzez swą zasadniczą różnicę do procesów, która polega na tym, że działają w przestrzeni adresowej jednego procesu nie wymagają przełączenia kontekstu przez system. To z kolei bardzo przyspiesza przełączanie się między zadaniami wykonywanymi przez program i nie wymaga w tym udziału jądra. W wątkach ważne jest jeszcze to, że mogą bardzo szybko wymieniać się swoimi wynikami pracy ponieważ pracują w tej samej przestrzeni pamięci.

Jednak wątki użytkownika posiadają również jedną poważną wadę. Jak pisałem wcześniej, każda decyzja w zarządzaniu ograniczonymi zasobami posiada swoją cenę. Ceną wątków realizowanych przez biblioteki użytkownika (w systemie Linux najpopularniejsza to pthread) jest to, że system wszystkie je widzi jako jedne proces. W wyniku tego niemożliwe jest rzeczywiste przetwarzanie dwóch wątków jednocześnie nawet na maszynie z dwoma procesorami. Dzieje się tak, ponieważ jądro zajmuje się przydzielaniem czasu procesora dla procesów, a jak pisałem wcześniej wątków w przestrzeni użytkownik jądro po prostu nie widzi i dlatego nie może przydzielać im oddzielnie czasu procesorów. Ponad to, gdy w jednym z wątków wystąpi jakieś żądanie, którego system nie może zrealizować natychmiast (np. operacje we/wy) jądro przerywa działanie całego procesu wraz z jego wszystkimi watkami i przenosi go do kolejki oczekujących. Po szersze omówienie stanów w jakich mogą znajdować się procesy odsyłam do literatury.

Z powodu wspomnianej największej wady wątków użytkownika wprowadzono wątki jądra. Te mogą być rzeczywiście przetwarzane równolegle, np. przez dwa procesory. Dodatkowo, gdy jeden z wątków jądra zostanie przerwany w wyniku jakiejś operacji system może przełączyć działanie procesu na jego drugi wątek i proces nadal będzie wykonywany. Kolejną zaletą wątków jądra jest to, że jądro może je niezależnie szeregować oraz wykorzystać wielowątkowość do realizacji własnych zadań co jest bardzo korzystne. Wspomniane szeregowanie również jest bardzo ciekawym tematem, polega na podejmowaniu decyzji, który z procesów ma zostać wykonany jako kolejny. Podałem już zalety, czas na wady.

Więc główną wadą wątków jądra jest to, że do przełączenia się między nimi wymagane jest przejście procesora w tryb jądra co jest bardzo kosztowne. Z prezentowanych testów w literaturze przeprowadzonych na systemie UNIX wynika, że operacje na wątkach użytkownika są 24 szybsze od wątków jądra, a te z kolei są 11 razy szybsze od procesów.
Z powodu tych znacznych korzyści w szybkości powstało wiele kombinacji między procesami i wątkami, z których każda ma swoje wady i zalety. Główne z nich przedstawiłem na kolejnym rysunku.
1:N – jeden proces jest rozgałęziany bez wiedzy jądra w przestrzeni użytkownika
1:1 – aplikacja tworzy wątki poprzez API systemu, który realizuje dla niej wielowątkowość
M:N (w najprostszej konfiguracji daje 1:1) – to specjalne rozwiązanie, które pozwala zablokowanemu wątkowi przełączyć się na inny wątek procesu realizowany przez jądro

Ostatnia opcja jest najbardziej interesująca i skomplikowana w implementacji, dlatego w nie wieku systemach została wdrożona. Do tej pory pisałem o wątkach w takim sensie, iż można się między nimi przełączać w obrębie jednego procesu, natomiast model M:N pozwala wątkowi przełączać się między procesami ale będącymi w jednej grupie, czasami zwanej domenami. W modelu 1:1 gdy jeden wątek zostanie zablokowany, jądro może przełączyć działanie procesu na inny jego wątek ale w modelu M:N to wątek może zmienić proces w obrębie jednej grupy. Więc gdy proces zostanie wstrzymany, wątek może przeskoczyć na inny i nie czekać na wznowienie. To ciekawa możliwość aczkolwiek nieczęsto wykorzystywana.

Teraz możemy już odnieść się do tego jak to zaimplementowano w różnych systemach.


Jeżeli chodzi o implementacje wątków w systemach to na początek trzeba powiedzieć, że wątki jądra są dostępne chyba już w każdym systemie. Z modelem 1:1 będziemy mieli do czynienia w systemach Windows, Linux, FreeBSD i Solaris. W każdym systemie można też użyć modelu 1:N bo jest to rozwiązanie realizowane przez oprogramowanie użytkownika, a nie systemowe.

Pierwszą i obecnie chyba najlepszą implementacje wątków posiada Solaris. Jest to model M:N i wyróżni się w nim aż cztery pojęcia związane z procesami i watkami. Pierwszy jest standardowy proces. W procesie mogą być tworzone wątki użytkownika, o których system nie ma pojęcia. Solaris posiada jeszcze inną odmianę procesu zwaną procesami lekkimi. Są to pewnego rodzaju odwzorowania wątków użytkownika na wątki jądra. Za taki wątkiem jądra może kryć się wiele wątków użytkownika – czyli 1:N. Na najniższym poziomie działania systemu znajdują się wątki jądra, które są podstawowym typem szeregowania przez system.
Takie zróżnicowanie pozwala pisać bardziej wydajne programy, w których pewne zadania wymagające interwencji system są realizowane w oddzielnych procesach lekkich dzięki czemu będą mogły się wykonywać jednocześnie lub gdy jeden z nich zostanie zablokowany. Jeden proces może korzystać z wielu procesów lekkich.
Solaris posiada dosyć ciekawą funkcje, chodzi o to, że system ten odwzorowuje przerwania systemowe na wątki jądra z wyższym priorytetem. Przerwań nie będę tutaj omawiał, ponieważ to bardzo długi temat. Programiści na pewno kojarzą o co chodzi, zwłaszcza Ci, którzy bawili się kiedyś assemblerem. Otóż przerwania występują wtedy, gdy wciśniesz klawisz, zakończy się zapis na dysku lub karty sieciowej dotrze pakiet. Wtedy system musi przerwać całą swoją robotę, czyli zapisać obecne stany procesorów jeżeli ma ich więcej niż jeden oraz wywołać funkcję obsługującą dane przerwanie. Oczywiście wiecie, że obsługa przerwania może zostać przerwane przez inne przerwanie o wyższym priorytecie :) - mówiłem tu jest co robić. Do tego potrzebny jest kompletny oraz skomplikowany mechanizm. Solaris zastępuje go i tak już istniejący mechanizm w jądrze, który rozwiązuje te same problemy jak w przypadku przerwań. Mowa tu o mechanizmach zabezpieczających przed jednoczesnym dostępem do krytycznych danych podczas realizowania wielu zadań jednocześnie przez system. Dzięki temu jądro systemu Solaris jest mniej obciążone, a obsługa przerwań bardziej wydajna niż w innych systemach. Problem, który opisałem jest o wiele bardziej skomplikowany niż to przedstawiłem.
Z ciekawostek o Solarisie pamiętam, że bodajże NASA wykorzystuje go w promach kosmicznych. Jest jeszcze jedna ciekawostka związana z tym systemem, która jednocześnie wiąże go z kolejnym systemem, o którym zaraz wspomnę. Tym systemem jest FreeBSD nad rozwojem, którym pracował niejaki pan Bill Joy. Wprowadził do niego wiele ciekawych rozwiązań a następnie porzucił pracę na uniwersytecie aby założyć własną firmę znaną do niedawna jako Sun Microsystems. Ponadto Bill Joy pracował nad językiem Java, który obecnie jest wzorcem dla innych języków programowania obiektowego.

Wspomniałem o FreeBSD nie przypadkiem, będzie on drugim analizowanym systemem, ponieważ podobnie do Solarisa również jest wyjątkowy. Na stronie tego projektu w zakładce Features znajdziemy listę funkcji, które zaimplementowano w tym systemie. To chyba jedyny z tych najbardziej znanych systemów, na stronie którego znajdziemy tak dokładne informacje pisane technicznym językiem. Co świadczy do kogo system ten jest kierowany. Teraz gdy przeczytasz tam o jednej z właściwości zwanej: „M:N application threading via pthreads...” będziesz wiedział o czym mowa. FreeBSD korzysta z mechanizmu zwanego KSE, który implementuje model M:N. W tym mechanizmie zastosowano grupy wątków na poziomie jądra. Taka grupa jest podstawowym typem szeregowanym przez jądro. W grupie znajduje się wiele wątków, które mogą ale nie muszą być powiązane z wątkami użytkownika. O KSE można sobie poczytać w sieci.
FreeBSD ma chyba najbardziej przejrzystą implementacje modelu M:N. Tak samo jak w Solarisie wykorzystano to do obsługi przerwań w wątkach, ponadto jądro dzięki tak dobrze rozbudowanym mechanizmom procesów oraz wątków łatwiej było zaimplementować jako mikrojądro. Wątki oraz procesy są bardzo związane z architekturą mikrojądra, właściwie bez nich nie mogło by istnieć.

Czas na naszego Linuksa, nie posiada on implementacji modelu M:N ale 1:1 czy jak kto woli 1:N. Linux jeżeli chodzi o przedstawioną teorie w pierwszej części tego wpisu bije ją na głowę :) Piszę tak dlatego, ponieważ system ten nie odróżnia procesów od wątków. Procesy takie należą do grupy posiadającej ten samem identyfikator ID. Tworzysz proces, a potem następny powiązany z nim, lecz określasz jak bardzo ma być powiązany. Czy mają razem dzielić pamięć, czy mają dzielić otwarte pliki tid.. Oryginalne rozwiązanie ale w pełni wystarczające. Tak jak w przypadku wszystkich systemów Uniksowych w systemie jest możliwość używania kilku bibliotek do realizacji wątków, we FreeBSD istnieje nawet oddzielny plik konfiguracyjny, w którym można wybrać ten mechanizm dla poszczególnych aplikacji. Chcąc dowiedzieć się więcej o wątkach w Linuksie warto poczytać np. o NPTL.

Przyszedł czas na system Windows. Po pierwsze należy zaznaczyć, że system ten ma obiektową architekturę jądra co jest uznawane za nowoczesne rozwiązanie tak samo jak programowanie obiektowe. Z tego wynika, że przedstawiane do tej pory rozwiązania nie są podobne to tych w Windows. Większość systemów uniksowych korzysta z ujednoliconego trendu, choć Linux nie.
Dla przeciwników systemu Windows nie mam dobrej wiadomości. System ten obsługuje współbieżność wątków w procesie, a nawet pozwala na przenoszenie wątków na inne procesy, czyni mamy tu możliwość podobną do tej z modelu M:N tylko, że realizowaną dzięki obiektowemu modelowi jądra. Zarówno procesy jaki i wątki mogą się ze sobą komunikować. Wątki mogą nawet między dwoma procesami wymieniać się informacjami dzięki współdzielonej pamięci dla obu procesów.

Podsumowując, jeżeli chcesz używać wolnego systemu to pod względem mechanizmu wątków najlepszy będzie FreeBSD oraz OpenSolaris. Jeżeli chodzi o Linux i Windows to oba radzą sobie mniej więcej tak samo, w nietypowy sposób dla siebie. Biorąc pod uwagę licencje oraz architekturę jądra (mikrojądro) oraz resztę czynników zwycięzcą ogłaszam FreeBSD. No, no panowie, teraz to już inaczej patrzy się na projekt GNU/kFreeBSD.