W głąb C #2,
[ Pobierz całość w formacie PDF ]
62 Wgłąb języka C IV. Programowanie współbieżne Język C nie zawiera oczywiście żadnych mechanizmów umożliwiających progra- mowanie współbieżne (np. takich, jak w języku Ada). W rozdziale niniejszym przedstawię implementację modułu umożliwiającego pseudo-współbieżne wyko- nywanie funkcji w języku C. Termin "pseudo-współbieżność" jest tutaj bardzo ważny, gdyż w żadnym wypadku zastosowane rozwiązanie nie umożliwia realiza- cji rzeczywistej współbieżności na maszynach wieloprocesorowych. Pomimo tego, dla zwiększenia czytelności opisu, będę w dalszej jego części używał terminów "współbieżny" oraz "pseudo-współbieżny" wymiennie. Implementacja wspomnianego modułu będzie pretekstem do zastosowania wielu technik opisanych w poprzednich rozdziałach tej książki. Dlatego też przed przy- stąpieniem do czytania tego rozdziału polecam przeczytanie rozdziałów po- przednich. Z drugiej strony implementacja ta jest przykładem niecodziennego stylu programowania w języku C, charakteryzującego się bardzo intensywnym użyciem preprocesora. Współbieżne wykonywanie funkcji nie będzie realizowane na poziomie systemu operacyjnego lecz na poziomie programu wC, ibędzie ono wykonane z wykorzystaniem jedynie elementów języka standardowego. Oznacza to między innymi, że moduł będzie przenośny zarówno na różne kompilatory (należy jed- nak ostrożnie stosować opcje optymalizacji) jak i różne platformy sprzętowe. In- ną konsekwencją realizacji przełączania zadań całkowicie na poziomie języka C jest "gruboziarnistość" zrealizowanej pseudo-współbieżności. Jeżeli dwa (lub więcej) zadania (funkcje, programy) mają być wykonywane w sposób współ- bieżny na jednym procesorze, to w rzeczywistości na zmianę wykonywane są pewne małe fragmenty tych zadań. Najmniejszą taką cząstką może być instruk- cja procesora, która nie może już być podzielona. Takie rozwiązanie byłoby pseudo-współbieżnością "drobnoziarnistą" i gwarantowałoby maxymalne złu- dzenie rzeczywistej współbieżności. W przedstawionym poniżej module naj- mniejszą częścią funkcji, która musi być wykonana, zanim sterowanie zostanie przekazane do innej funkcji, jest jedna instrukcja (ang. statement ) języka C. 1.Dlaczego współbieżność? Klasyczne programy współbieżne są wykonywane na maszynach wieloprocesoro- wych. Celem zastosowania równoległych komputerów i równoległych programów jest zmniejszenie złożoności czasowej rozwiązywanego zadania. Jest sprawą oczywistą, że w przypadku programu wykonywanego pseudo-współbieżnie na komputerze jednoprocesorowym nie można liczyć na zwiększenie prędkości obli- czeń. Co więcej, wykonanie w takim przypadku kilku zadań musi trwać dłużej niż trwałoby wykonanie tych zadań sekwencyjnie jedno po drugim. Dzieje się tak dlatego, że oprócz kodu zadań procesor musi wykonywać pewien kod związany IV Programowanie współbieżne 63 z ich przełączaniem. Można by wtakim razie powiedzieć, że pseudo- współbieżność jest sztuką dla sztuki. Nie jest to prawdą, a najlepszym na to dowo- dem jest popularność programów typu DESQview czy Windows, umożliwiających pseudowspółbieżne wykonywanie programów. Twierdzenie, że wielozadaniowość realizowana na jednym procesorze nie może przynieść zysków czasowych jest prawdą dopóty, dopóki zadania cały czas wymagają pracy procesora. W rzeczywistości częste są sytuacje, gdy większość czasu pracy zadania nie jest zużywana na pracę procesora. Na przykład operacje na pamięci zewnętrznej są zwykle na tyle wolne w porównaniu z szybkością procesora, że mógłby on równo- cześnie wykonywać inną pracę. Jeszcze bardziej skrajnym przypadkiem jest cze- kanie przez zadanie na dane wprowadzane przez użytkownika z klawiatury. Jeżeli jedno z zadań utknęło w takim wąskim gardle, procesor może poświęcić swój czas na wykonanie innych zadań. Można to zrealizować właśnie poprzez pseudo- współbieżność. Zyskiwanie czasu w takich sytuacjach nie jest jednak jedynym motywem zasto- sowania wielozadaniowości. Programy wykonujące kilka zadań na raz mogą być bardzo wygodne dla użytkownika. Przykładem niech będzie edytor tekstów zapi- sujący co jakiś czas redagowany tekst "w tle". Jak już wcześniej wspomniałem, realizacja współbieżnego wykonywania funkcji będzie polegała na wykonywaniu na zmianę kolejnych fragmentów każdej z funkcji. Do przekazywania sterowania z jednej funkcji do drugiej posłużą nam funkcje setjmp i longjmp . 2.Funkcje setjmp i longjmp Deklaracje tych funkcji wyglądają następująco: int setjmp(jmp_buf); void longjmp(jmp_buf,int); Są one funkcjami standardowymi. Ich deklaracje, oraz deklaracja typu jmp_buf znajdują się w pliku nagłówkowym " setjmp.h ". Służą one do zapamiętania, a następnie odtworzenia stanu programu. W praktyce oznacza to, że funkcja lon- gjmp umożliwia wykonanie skoku do jakiegoś miejsca, w którym stan programu został wcześniej zapamiętany przy pomocy funkcji setjmp . Jak wskazuje sama nazwa funkcji, jest to skok daleki, nie ograniczony do wnętrza funkcji (jak skok przy pomocy instrukcji goto Wywołanie funkcji setjmp powoduje zapamiętanie w zmiennej typu jmp_buf, przekazanej do niej jako argument, informacji o stanie programu. Funkcja zwraca wartość 0. Funkcję longjmp wywołuje się z dwoma argumentami. Pierwszym jest zmienna, w której wcześniej zapamiętano stan programu przy pomocy funkcji setjmp . Drugi argument jest liczbą całkowitą. Wywołanie funkcji longjmp powoduje jmp_buf definiuje strukturę, w której prze- chowywane są informacje o stanie programu. 64 Wgłąb języka C odtworzenie stanu programu jaki został zapamiętany w zmiennej typu jmp_buf przekazanej jako pierwszy argument. W wyniku takiego wywołania funkcji lon- gjmp program znajduje się w punkcie powrotu z funkcji setjmp (bo w takim momencie został zapamiętany stan programu), przy czym wartość zwracana przez funkcję setjmp jest równa drugiemu argumentowi funkcji longjmp (lub 1 jeżeli drugi argument był równy 0). Na podstawie wartości funkcji setjmp , program jest w stanie odróżnić czy została ona normalnie wywołana w wyniku zinterpreto- wania kolejnej instrukcji, czy też nastąpił skok przy pomocy funkcji longjmp . Działanie funkcji setjmp i longjmp jest czasami trudne do zrozumienia. Poniż- szy przykład powinien wyjaśnić niejsności. if(setjmp(buf)) { /* ci ą g instrukcji */ } /* ... */ longjmp(buf,3); Po wywołaniu funkcji setjmp warunek nie będzie spełniony (setjmp zwróci wartość 0) i ciąg instrukcji nie zostanie wykonany. W efekcie wywołania funkcji longjmp w innej części programu, sterowanie zostanie przekazane do miejsca powrotu z funkcji setjmp , ale tym razem zostanie zwrócona wartość równa 3, a więc warunek będzie spełniony i ciąg instrukcji zostanie wykonany. Ponieważ po "powrocie" funkcja setjmp zwraca wartość przekazaną jako argu- ment funkcji longjmp , nic nie stoi na przeszkodzie, żeby przy pomocy różnych funkcji longjmp przekazywać różne wartości i na ich postawie identyfikować miejsce, z którego nastąpił daleki skok, na przykład przy pomocy instrukcji swi- tch switch(setjmp(buf)) { case1:/*zpunktu 1 */ break; case2:/*zpunktu 2 */ break; case3:/*zpunktu 3 */ break; } 3.Przełączanie zadań Zastanówmy się na początek, w jaki sposób dokonać przełączenia procesora pomiędzy dwiema funkcjami. Jak wcześniej napisałem, użyjemy pary funkcji setjmp i longjmp do wykonania dalekich skoków pomiędzy procesami (funkcjami). Dla każdego procesu będziemy potrzebować jednej zmiennej typu jmp_buf służącej do zapamiętania stanu programu w momencie przekazania sterowania do drugiego procesu. Obie zmienne mu- szą być globalne, aby obie funkcje mogły się do nich odwołać. jmp_buf buf1,buf2; W celu wykonania skoku do funkcji f1 będziemy używać wywołania IV Programowanie współbieżne 65 longjmp(buf1,1); Analogicznie, żeby skoczyć do funkcji f2 longjmp(buf2,1); Przed wykonaniem skoku do drugiego procesu, każda funkcja musi wywołać funkcję setjmp (buf). Zapamiętane przez tę funkcję informacje o stanie programu będą mogły być w przyszłości wykorzystane do powrotu do miejsca, w którym działanie funkcji zostało zawieszone. Tak więc sekwencje przełączające zadania będą wyglądały mniej więcej tak: if(setjmp(buf1)==0)longjmp(buf2,1); /* w funkcji f1 */ if(setjmp(buf2)==0)longjmp(buf1,1); /* w funkcji f2 */ Funkcja longjmp zostanie wywołana tylko wtedy, gdy setjmp zwróci wartość ze- ro. Nastąpi to więc po wywołaniu setjmp w celu zapamiętania kontekstu programu, a nie nastąpi po powrocie w to miejsce przy pomocy dalekiego skoku. Spróbujmy teraz uogólnić to rozwiązanie na nieznaną z góry ilość procesów. Trzeba zdefiniować jakąś strukturę danych, która zapewniałaby istnienie jednego bufora typu jmp_buf dla każdej funkcji, a także umożliwiałaby określenie jaka jest następna funkcja w "łańcuszku". struct el { jmp_buf buf; struct el *next; }; Każdą funkcja będzie posiadała własny element typu struct el. W polu buf tego elementu będzie zapamiętywany kontekst tej funkcji w chwili przełączania stero- wania do kolejnego zadania. Pole next struktury będzie wskazywało element typu struct el skojarzony z funkcją, do której ma być przekazane sterowanie. W ten spo- sób powstanie zapętlona lista o węzłach typu struct el. Lista jest jednokierunkowa, gdyż każdy jej element zawiera tylko pole wskazujące następny element. Do pełnej manipulacji listą jednokierunkową (w tym do usuwania elementów z listy) po- trzebne są co najmniej dwie zmienne, wskazujące na dwa kolejne węzły listy: struct el *cur,*last; Zmienna cur będzie zawsze wskazywać na węzeł odpowiadający aktywnej funkcji, zaś zmienna last - na węzeł odpowiadający poprzedniej funkcji. Sekwencja przełą- czania zadań zapisana przy użyciu tych zmiennych będzie wyglądała następująco: if(setjmp(cur->buf)==0) longjmp((last=cur,cur=(cur->next))->buf,1); Argumentem funkcji longjmp jest dość skomplikowane wyrażenie: (last=cur,cur=(cur->next))->buf Analiza tego wyrażenia rozpocznie się od przypisania zmiennej last wartości zmiennej cur. Następnie zmiennej cur jest przypisywany wskaźnik do następnego 66 Wgłąb języka C węzła listy. Pole buf tego węzła zostaje argumentem funkcji longjmp (zostanie wykonany skok do następnej funkcji). Pola buf w liście muszą być zainicjowane przed pierwszym wywołaniem sekwen- cji przełączającej zadania. Żeby to osiągnąć, umieścimy na początku każdej funk- cji następujący warunek: if(setjmp(cur->buf)==0)return; Jeżeli funkcja zostanie wywołana, to jej kontekst zostanie zapamiętany w polu cur->buf i nastąpi od razu powrót do funkcji wywołującej. Pozostaje jeszcze zastanowić się, co zrobić po zakończeniu działania procesu. Trzeba go oczywiście usunąć z listy, żeby nie był więcej wykonywany. Doko- nuje się tego instrukcją cur=last->next=cur->next; W tym miejscu przydaje się zadeklarowana wcześniej na wyrost zmienna last. Na- stępnie trzeba przekazać sterowanie do kolejnego procesu: longjmp(cur->buf,1); 4.Zapis praktyczny Przedstawione powyżej konstrukcje robią dobry użytek z funkcji setjmp i longjmp umożliwiając przełączanie funkcji - zadań, ale w żadnym wypadku nie nadają się do praktycznego zastosowania w programowaniu. Stosując definicje preprocesora można zapisać te sekwencje w sposób dużo czytelniejszy. Załóżmy, że zapis ten musi spełniać następujące warunki: zamiana napisanej i uruchomionej wcześniej funkcji na postać, w której mogłaby ona być wykonywana współbieżnie, musi być prosta, prawie automatyczna, funkcja przystosowana do wykonywania współbieżnego powinna dalej móc być wywoływana w normalny sposób, jeżeli funkcja jest ostatnim procesem (wszystkie inne zakończyły już działa- nie) to nie powinna być wykonywana sekwencja przełączania zadań. Pierwszym krokiem będzie zastąpienie omówionych w poprzednim podrozdziale sekwencji odpowiednimi definicjami preprocesora: #define BEGIN if(setjmp(cur->buf)==0)return; #define END cur=last->next=cur->next; \ longjmp(cur->buf,1); #define _ if(setjmp(cur->buf)==0) \ longjmp((last=cur,cur=(cur->next))->buf,1); [ Pobierz całość w formacie PDF ] |