Współbieżność w obiektowych językach programowania

Data dodania: 2011-10-07, Autor: doc. dr inż. Wiesław Porębski, Dodał: Karol, Wyświetleń: 464

Streszczenie

Praca przedstawia wyniki przemyśleń autora na temat koncepcji współbieżności i ich implementacji w językach programowania, w szczególności w językach obiektowych. Pokazano podstawowe mechanizmy współbieżności w językach Ada 95 i Java. Szczególną uwagę zwrócono na następujące zagadnienia:

• Relacje pomiędzy współbieżnością oferowaną przez system operacyjny a współbieżnością zdefiniowaną w języku programowania.
• Łatwość używania mechanizmów współbieżności implementowanych na poziomie języka.
• Mechanizmy komunikacji pomiędzy obiektami.
• Ograniczenia narzucane na wymianę informacji pomiędzy procesami/wątkami współbieżnymi.
• Problemy synchronizacji i wzajemnego wykluczania przy operacjach na zasobach współdzielonych przez zadania/wątki.
• Trudności w pogodzeniu koncepcji obiektów aktywnych z mechanizmami dziedziczenia i wirtualizacją operacji.

Podsumowaniem rozważań jest analiza efektywności rozwiązań i zwrócenie uwagi na problemy dotąd nierozwiązane.

WSTĘP

Współbieżność definiuje się jako jednoczesne wykonywanie procesów w systemie wieloprogramowym. W przypadku architektur jednoprocesorowych "jednoczesność wykonywania" oznacza w rzeczywistości tylko naprzemienne wykonywanie procesów lub wątków w dłuższej jednostce czasu. W systemach z podziałem czasu w celu uzyskiwania współbieżności procesor jest przydzielany procesom cyklicznie na krótkie kwanty czasu, dzięki czemu w systemie może działać jednocześnie wielu użytkowników. Najczęściej w takich systemach stosuje się algorytm rotacyjny (ang. round-robin algorithm). Prawdziwą współbieżność osiąga się w systemach wieloprocesorowych lub wielokomputerowych; nazywa się ją równoległością. W systemie rozproszonym współbieżność oznacza niezależność zachodzących zdarzeń w sensie relacji uprzedniości.

Od kilku już dziesięcioleci podejmowane są próby uzyskania odpowiedzi na pytanie: czy dla uzyskania współbieżności w programach należy wykorzystywać mechanizmy oferowane przez system operacyjny, czy też wyposażać w odpowiednie mechanizmy języki programowania? Za pierwszym rozwiązaniem przemawiają następujące argumenty:

• Różne języki mają różne modele współbieżności; łatwiej jest zestawić program z fragmentów napisanych w różnych językach, jeżeli wykorzystują one te same modele współbieżności systemu operacyjnego.
• Istnieją duże trudności w implementacji efektywnego obliczeniowo językowego modelu współbieżności nadbudowanego nad modelem systemu operacyjnego.
• Istnieją już ugruntowane standardy systemów operacyjnych, co zapewnia przenośność programów.

Rozwiązanie drugie ma także swoje zalety:

• Prowadzi do programów bardziej czytelnych i łatwiejszych w konserwacji.
• Istnieje wiele typów systemów operacyjnych; definiując współbieżność na poziomie języka otrzymujemy lepszą przenośność programów.
• Celem programu może być wbudowanie go w kontroler (sterownik), który obsługuje wiele współbieżnych zdarzeń. Ze względu na skąpe zasoby, w większości sterowników nie jest dostępny system operacyjny.

Jak dotąd nie ma definitywnej odpowiedzi na postawione wyżej pytanie. Dlatego - ważąc wszystkie wady i zalety - twórcy wielu języków programowania (np. Simula-67, Ada, Eiffel, Java, Modula-3, Smalltalk) wyposażyli je w modele współbieżności na poziomie języka. W niniejszej pracy skupimy się na zagadnieniu koegzystencji współbieżności z cechami obiektowymi w językach Ada 95 i Java.

PROCESY I WĄTKI

W środowiskach operacyjnych (Unix/Linux, Windows) proces, nazywany także zadaniem lub procesem ciężkim, można traktować jako obiekt aktywny, reprezentujący wykonywany program. Używając terminologii obiektowej możemy powiedzieć, że proces jest wyposażony w pewne atrybuty i operacje [5]. Do atrybutów procesu zaliczymy:

• Własną, prywatną przestrzeń adresową.
• Trzy logiczne segmenty w przestrzeni adresowej: segment rozkazów (rozkazy maszynowe wykonywanego programu), segment danych oraz segment stosu.
• Blok kontrolny procesu (struktura w sensie języka C, utrzymywana przez jądro systemu operacyjnego).

Własna przestrzeń adresowa zapobiega interferencji danego procesu z biegnącymi współbieżnie innymi procesami. Pełna zawartość przestrzeni adresowej procesu nie musi rezydować w pamięci głównej komputera; przy wykonywaniu dużych programów system może umieszczać na dysku części segmentów i pobierać je stamtąd w miarę potrzeby. Mówimy wówczas o tzw. pamięci wirtualnej. Segment rozkazów jest dostępny tylko do odczytu. Umieszczony w tym segmencie kod musi być wznawialny (ang. reentrant); oznacza to, że może być współdzielony przez inne procesy. Segment rozkazów może ulec zmianie tylko wtedy, gdy proces zaczyna wykonywać inny program. Segment danych zawiera zainicjowane (globalne i statyczne) i niezainicjowane zmienne programu. Proces może rozszerzać lub zwężać swój segment danych przez wywołania systemowe. Segment stosu utrzymuje stos wykonania; jest on automatycznie rozszerzany przez jądro w miarę postępów wykonania procesu. Ponieważ proces może działać w dwóch trybach (użytkownika i systemowym), posiada de facto dwa stosy LIFO, po jednym dla każdego z trybów pracy. Blok kontrolny procesu (ang. Process Control Block - PCB) zawiera informacje potrzebne systemowi operacyjnemu dla sterowania procesem. Informacje te tworzą tzw. kontekst procesu.

Operacje wykonywane na rzecz procesu zawsze wymagają interwencji jądra. Spośród bogatego repertuaru takich operacji wymienimy kilka [7]: fork (tworzy nowy proces, będący potomkiem danego procesu), exec (ponowne zainicjowanie procesu na podstawie wskazanego programu), brk (zmiana wielkości segmentu danych), exit (kończy działanie tego procesu, który ją zainicjował), nice (zmień priorytet procesu), wait (oczekuje zakończenia procesu potomnego), kill (zakończ proces).

Przepływ sterowania przez kolejne rozkazy kodu nazywa się wątkiem wykonania, lub wątkiem sterowania. Gdy proces jest wywłaszczany z dostępu do procesora, wszystkie istotne informacje zawarte w jego bloku kontrolnym są zachowywane i ponownie odtwarzane przy wznowieniu dostępu.

Klasyczny proces systemu UNIX posiadał tylko jeden wątek wykonania. We współczesnych systemach operacyjnych proces może posiadać wiele wątków wykonywanych współbieżnie w przestrzeni adresowej procesu. Każdy wątek dysponuje własnym stosem wykonania i pamięcią statyczną dla własnych zmiennych lokalnych, zachowuje kontekst przy wywłaszczeniu, i ma dostęp do zasobów procesu. Wątki (nazywane też procesami lekkimi) mają szereg zalet w stosunku do procesów. Można tutaj wymienić:

• Mniej czasu na utworzenie nowego wątku niż na utworzenie procesu, ponieważ nowo utworzony wątek korzysta z bieżącej przestrzeni adresowej procesu.
• Mniej czasu na zakończenie wątku niż procesu.
• Mniej czasu na przełączenie pomiędzy dwoma wątkami w obrębie tego samego procesu, częściowo dlatego, że nowo tworzony wątek korzysta z bieżącej przestrzeni adresowej procesu.
• Mniejsze narzuty na komunikację - komunikacja pomiędzy wątkami jednego procesu jest prosta, ponieważ wątki współdzielą przestrzeń adresową procesu. Tak więc, dane produkowane przez jeden wątek są natychmiast dostępne dla wszystkich innych wątków.

Wątki są tworzone na poziomie użytkownika poprzez wykorzystanie biblioteki wątków (pthread w specyfikacji POSIX), lub na poziomie jądra systemu operacyjnego poprzez wywołania systemowe. Obie metody mają swoje zalety i wady i w rezultacie niektóre systemy operacyjne (np. Solaris) pozwalają na dostęp do obu poziomów.

OBIEKTY PASYWNE, AKTYWNE, I REAKTYWNE

W programowaniu obiektowym obiekt jest bytem, grupującym prywatne dane i publiczne operacje. Bieżące wartości danych nazywa się stanem obiektu. Publiczne operacje, nazywane też interfejsem obiektu, mogą podawać lub zmieniać stan obiektu. W obiektowym programie jednowątkowym typowymi obiektami są obiekty pasywne, tj. takie, które nie mają własnego wątku sterowania, ale są w stanie świadczyć usługi na rzecz innych obiektów. Obiekty są wystąpieniami zadeklarowanych wzorców, nazywanych klasami (C++, Eiffel, Java, Simula-67, Smalltalk) lub typami (Ada 95, Modula-3 [3]); można również tworzyć obiekty klas lub typów anonimowych. W fazie wykonania program obiektowy można uważać za zbiór współdziałających obiektów; współdziałanie polega na przesyłaniu pomiędzy obiektami komunikatów; w przypadku obiektów pasywnych mechanizm ten sprowadza się do wywoływania na danym obiekcie odpowiednich funkcji lub procedur składowych na rzecz innych obiektów, wywoływanych przez klienta zewnętrznego w stosunku do zbioru obiektów. Obiektem aktywnym jest taki obiekt, który ma własny wątek wykonania - jest zdolny do podjęcia działań spontanicznych. Pociąga to za sobą brak zgodności z paradygmatem obiektowym; wymaga on, aby obiekt (w domyśle pasywny) był repozytorium usług, czekającym na klienta (inny obiekt), który sam wybierze potrzebną mu usługę. Tymczasem obiekt aktywny wykonuje operacje uszeregowane według własnego harmonogramu.

W programie wielowątkowym wyróżnione obiekty powinny mieć dzielony dostęp do pewnych zasobów. Dzielone zasoby występują z reguły w obiektach pasywnych i reaktywnych. Obiektem reaktywnym nazwiemy taki obiekt, który posiada wątek sterowania dla kontroli dostępu do dzielonego zasobu. Para obiektów: aktywny-reaktywny tworzy układ, nazywany modelem klient/serwer, w którym serwerem jest obiekt reaktywny, a klientem obiekt aktywny. Kontrola dostępu do zasobów dzielonych opiera się na zasadzie wzajemnego wykluczania. Oznacza to, że w danej chwili tylko jeden klient ma wyłączny dostęp do zasobów serwera. Niepodzielny ciąg instrukcji, które operują na zasobach serwera, nazywa się sekcją krytyczną.

WSPÓŁBIEŻNOŚĆ W JĘZYKU ADA 95

Ada 95 jest językiem hybrydowym, łączącym cechy proceduralnego języka Ada 83 z obiektowością. Precyzyjnie zdefiniowana składnia i semantyka oraz przyjęta w języku silna typizacja uczyniły go narzędziem dla konstrukcji bezpiecznego oprogramowania.

Ada 95 zawiera prawie wszystkie cechy języków obiektowych: obiekty, ukrywanie informacji, hermetyzację (częściową), dziedziczenie (pojedyncze), przeciążanie metod, polimorfizm, wiązanie dynamiczne. Odpowiednikiem klasy znanej z innych języków obiektowych jest pakiet ze specyfikacją typu znakowanego (rekordu) o prywatnej implementacji. Wbudowany w język mechanizm współbieżności, niezależny od jego cech obiektowych, jest zrealizowany za pomocą dwóch typów: zadaniowego i chronionego. Wystąpienia typu zadaniowego (zadania) są obiektami aktywnymi lub reaktywnymi, zaś obiekty typu chronionego - pasywnymi. Zadania reprezentują wątki sterowania; mogą być wykonywane niezależnie od siebie, lub przesyłać między sobą komunikaty. W tym drugim przypadku tworzą układ serwer/klient. Specyfikacja serwera zawiera nazwane wejścia, do których klienci wysyłają żądania wykonania usług w postaci komunikatów: nazwa_serwera.nazwa_wejścia(argumenty).

Implementacja obsługi każdego wejścia ma postać instrukcji blokowej o postaci accept nazwa_wejścia(parametry). Zwykle każdemu wejściu odpowiada oddzielna instrukcja accept. Serwer czeka przy instrukcji accept na wywołanie wejścia przez klienta; podczas czekania zwalnia wszelkie zasoby przetwarzające (np. procesor), których używa, a jego stan określa się jako zawieszony lub zablokowany. Na czas wykonania instrukcji accept zawieszeniu ulega zadanie klienta. Ponieważ instrukcje accept operują na współdzielonych zasobach serwera, podlegają zasadzie wzajemnego wykluczania, która jest tutaj przyjętym sposobem synchronizacji. Ponadto, jeżeli jest więcej zadań czekających na wykonanie tej samej usługi, to są one ustawiane w kolejkę przy żądanym wejściu.

Jeżeli w odpowiedzi na żądanie klienta serwer przejdzie do wykonania instrukcji accept, to taką sytuację nazywa się spotkaniem (rendezvous). Z zasady wzajemnego wykluczania wynika, że sekwencja działań od wywołania do wykonania instrukcji accept musi być operacją niepodzielną (atomową), a zatem sama instrukcja accept jest sekcją krytyczną.

Obiekt chroniony jest wystąpieniem typu chronionego (nazwanego lub anonimowego). Hermetyzuje on chronione dane i chronione operacje. Operacje na chronionych danych są możliwe jedynie za pośrednictwem chronionych wejść i podprogramów. Chronione wejścia i procedury pozwalają modyfikować chronione dane; są one wykonywane zgodnie z zasadą wzajemnego wykluczania; chronione funkcje pozwalają tylko na współbieżny odczyt danych.

Obiekt chroniony występuje zwykle zwykle pomiędzy dwoma zadaniami aktywnymi, które traktują go jako zasób współdzielony, dostępny asynchronicznie. Dla zapewnienia bezpieczeństwa każde chronione wejście jest dozorowane przez barierę, tj. wyrażenie logiczne. Jeżeli bariera ma wartość true, możliwe jest wykonywanie treści wejścia; jeżeli false - zadanie wywołujące wejście pozostaje zawieszone dotąd, dopóki bariera nie uzyska wartości true i nie ma żadnych aktywnych zadań wewnątrz chronionego obiektu. Przykładowe deklaracje zawarto w pakiecie rodzajowym GenBuffer i w procedurze głównej ProdCon:

Generic type  Element is private;
package GenBuffer is -- pakiet rodzajowy GenBuffer
type Element_Array is array (Positive range<> ) of Element;
protected type Buffer(Max : Natural) is -typ chroniony
entry Put(Item: in Element);
entry Get( Item: out Element);
private
Data : Element_Array(1..Max); --dane dzielone
Next_in, Next_Out : Integer := 1; Count : Natural := 0;
end Buffer;
end GenBuffer;
package body GenBuffer is - treść pakietu GenBuffer
protected body Buffer is
entry Put(Item: in Element) when Count<Max is --bariera
begin
Data(Next_In) := Item;
Next_In := (Next_In mod Max)+1; Count := Count+1;
end Put;
entry Get(Item: out Element) when Count>0 is --bariera
begin
Item := Data(Next_Out);
Next_Out := (Next_Out mod Max)+1; Count := Count-1;
end Get;
end Buffer;
end GenBuffer;
with GenBuffer;
procedure ProdCon is - procedura główna
package Int_Buffer_Pkg is new GenBuffer(Integer);
use Int_Buffer_Pkg;
Buff : Buffer(20);
task Producer;
task body Producer is
begin
for J in 1..100 loop delay 0.5; Buff.Put(J); end loop;
end Producer;
task Consumer;
task body Consumer is
K : Integer;
begin
for J in 1..100 loop Buff.Get(K); delay 1.0; end loop;
end Consumer;
begin
null; 
-- wait for tasks to terminate
end ProdCon;

Typ ochronny Buffer pozwala deklarować obiekty, które są buforami cyklicznymi. Jego specyfikacja zawiera wyróżnik (discriminant) Max, co jest wygodnym sposobem przekazywania parametrów do obiektów, tworzonych po konkretyzacji pakietu rodzajowego GenBuffer. Zadaniami aktywnymi są Producer i Consumer. "Producent" wstawia element do bufora, wywołując wejście put bufora, zaś "Konsument" pobiera element z bufora traktowanego jako kolejka FIFO, wywołaniem wejścia get bufora. Producent jest blokowany gdy bufor jest pełny, a konsument jest blokowany, gdy bufor jest pusty. Zauważmy, że kod producenta jest wykonywany dwukrotnie szybciej niż kod konsumenta, tak że ostatecznie bufor będzie pełny.

WSPÓŁBIEŻNOŚĆ W JĘZYKU JAVA

Java należy do grupy języków "czysto obiektowych". Wbudowany mechanizm współbieżności wykorzystuje cechy obiektowe języka. Każdy program zawiera co najmniej jeden wątek główny - ten, który wykonuje metodę main klasy, dostarczanej jako argument startowy do maszyny wirtualnej (JVM). Podczas inicjowania JVM mogą być także uruchamiane w tle inne, wewnętrzne wątki (np. kolektor nieużytków), nazywane demonami. Wątek użytkownika jest tworzony w dwóch krokach: najpierw konstruuje się obiekt klasy Thread lub jej klasy pochodnej, wywołując odpowiedni konstruktor z wątku głównego. Wywołanie konstruktora tworzy nowy wątek, ale nie inicjuje jego wykonania. W drugim kroku wywołuje się metodę start tej klasy. Metoda start automatycznie wywołuje metodę run z nowego wątku, po czym następuje powrót i wykonanie treści metody run. Jeżeli chcemy, aby nasza klasa tworząca wątek nie była podklasą bezpośrednią klasy Thread, implementujemy w niej interfejs Runnable. Można wtedy zredukować wyżej opisane dwa kroki do jednego, definiując odpowiednio konstruktor naszej klasy:

class ActiveObject implements Runnable {
private Thread active;
public ActiveObject() {
  active = new Thread(this); active.start(); }
 public void run()  {
  if(active==Thread.currentThread())
  {...} else active = null; }}

Wówczas utworzenie nowego obiektu klasy ActiveObject:

ActiveObject LightProcess = new ActiveObject();

będzie równoznaczne z utworzeniem obiektu aktywnego z wątkiem wykonania startującym natychmiast, bez żadnej zewnętrznej interwencji. Zauważmy też, że składnia konstruktora nie pozwala klientowi klasy ActiveObject wywołać metody run bezpośrednio na obiekcie LightProcess, gdyż w takim przypadku nie powstanie obiekt aktywny.

Każdy obiekt (począwszy od wystąpienia klasy Object, która jest "korzeniem" drzewa klas) w języku Java jest skojarzony ze swoim własnym obiektem współbieżnej ochrony, nazywanym monitorem, utrzymywanym wewnętrznie przez JVM. Monitor posiada mechanizm wzajemnego wykluczania i synchronizacji wątków oraz tzw. zbiór oczekiwań (wait set), który wykorzystują jedynie metody wait, notify, notifyAll, i Thread.interrupt. W programie wielowątkowym, w którym wątki rywalizują o dostęp do zasobów dzielonych (dane, pliki, etc.), monitor jest argumentem bloku synchronizowanego lub parametrem metody synchronizowanej. Przejęcie monitora (nazywanego też synchronizatorem lub blokadą) przez wątek gwarantuje, że cały blok synchronizowany lub treść metody synchronizowanej staje się sekcją krytyczną, traktowaną jak jedna niepodzielna operacja atomowa.

Oprócz metod wystąpienia (niestatycznych), które można wywoływać na obiektach, klasa Thread zawiera metody statyczne, wywoływane dla bieżącego wątku. Na przykład metoda Thread.currentThread zwraca odnośnik (referencję) do bieżącego wątku. Odnośnik ten można następnie użyć do wołania metod niestatycznych, np.

Thread.currentThread().getName());

Inne zalecane do używania metody statyczne dla wątku bieżącego: Thread.interrupted, Thread.sleep, Thread.yield.

PODSUMOWANIE I WNIOSKI

Analiza modeli współbieżności na poziomie języka obiektowego wyraźnie pokazuje, jak trudno jest wbudować ją w paradygmat obiektowy. W językach, w których model ten wprowadzono niezależnie od modelu obiektowego, nie udało się wprowadzić dziedziczenia typów. W omawianych konstrukcjach Ady 95 ani typ zadaniowy, ani typ chroniony nie są nawet jednostkami bibliotecznymi. W językach, w których mechanizm współbieżności wbudowano w model obiektowy (Java), istnieje konflikt pomiędzy współbieżnością a dziedziczeniem, nazywany "anomalią dziedziczenia" [1],[4]. Konflikt ten polega na tym, że wprawdzie można tworzyć klasy pochodne od klas wątków, ale w pewnych okolicznościach synchronizowany kod nie może być efektywnie dziedziczony bez nietrywialnych redefinicji klasy pochodnej i jej superklasy. Usunięcie tej kolizji a priori wymagałoby dokładnego zaplanowania przez superklasę swojej klasy potomnej, co jest sprzeczne z zasadą "open-closed" sformułowaną przez B. Meyera [4].

Następny problem wiąże się z propagacją wyjątków [1],[2]. W programie sekwencyjnym semantyka propagacji i obsługi wyjątków jest prosta: wyjątek będzie się propagował przez zwinięcie stosu, zanim znajdzie odpowiedni kod obsługi; jeżeli nie znajdzie, proces się zakończy. Natomiast w środowisku współbieżnym, gdy zostanie zgłoszony wyjątek podczas wykonywania wątku (zadania), który nie jest w stanie go obsłużyć, to wątek (zadanie) zostanie zaniechany bez żadnego komunikatu.

Te, i inne problemy (np. zagnieżdżanie wątków/zadań, zagadnienie migracji obiektów aktywnych po sieci), rodzą potrzebę dalszych badań dotyczących współistnienia modelu obiektowego z mechanizmem współbieżności.

Otrzymano, 23.04.2003

BIBLIOGRAFIA

• Brosgol B. M. A comparison of the Concurrency and Real-Time Features of Ada 95 and Java. Tri-Ada Conference Papers, 1999.
• Burns A., Wellings A. Concurrency in Ada. Cambridge University Press, 1998.
• Dagenais M. R. Building Distributed OO Applications: Modula-3 Objects at Work. Computer Based Learning Unit, University of Leeds, 1997.
• Meyer B. Object-Oriented Software Construction. Prentice Hall, 1997.
• Porębski W. : Obiektowe języki programowania. Komputerowa Oficyna Wydawnicza "HELP", Warszawa, 1994.
• Porębski W. : Język Java. Wprowadzenie do programowania. Komputerowa Oficyna Wydawnicza "HELP", 2000.
• Rochkind M.J. Programowanie w systemie Unix dla zaawansowanych. WNT, 1993.
• Snyder, B. Vetter: Eiffel: An Advanced Introduction. www.progsoc.uts.ed.au/~geldridg/eiffel/ advance-intro/, 1998.

CONCURRENCY IN OBJECT-ORIENTED LANGUAGES

Summary

Considered author's view-point of concurrency ideas and their implementations in object-oriented languages is presented in the paper. Basic concurrency mechanisms in Ada 95 and Java are discussed in detail. Special attention has been paid to the following problems:

• Relationships between concurrency at the operating system level and that of language level.
• Ease of use of a language-level concurrency.
• Support for communication between objects.
• Constraints imposed on information exchange between concurrent processes/threads.
• Issues of synchronisation and mutual exclusion while accessing shared resources.
• Issues surrounding conflict between concurrency and object-oriented model.

In a final part of this paper issues concerned with efficiency of particular approaches are discussed and non-solved problems are shown.