4.PDF

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

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.

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

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

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);

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: