System ORCA

Jezyk Orca sluzy do pisania programow wspolbieznych pracujacych w obiektowym i rozproszonym srodowisku. Pozwala implementowac algorytmy slabo wyrazalne w standardowym modelu przetwarzania rozproszonego polegajacym na przekazywaniu komunikatow. System Orka pozwala na wykorzystanie rozproszonej pamieci dzielonej. W zamierzeniu autorow uzytkownikami tego jezyka maja byc osoby wykorzystujace algorytmy rozproszone do rozwiazywania "prawdziwych" problemow takkich jak np. problem TSP. Jezyk ten nie dostarcza mechanizmow wspierajacych programowanie systemowe i niskopoziomowe. Nie wymaga od programisty recznego zarzadzania pamiecia operacyjna. Przekompilowane i skonsolidowane programy dzialaja w oparciu o system wspomagajacy (Orca RTS).

Jezyk

Obiektami jezyka Orca sa statyczne Abstrakcyjne Typy Danych wyposazone w metody dostepu do lokalnych zmiennych. Sa one bezpieczne poniewaz w Orce

• brak niskopoziomowych mechanizmow dostepu do danych (wskazniki),
• brak problemow z pakowaniem argumentow wywolania zdalnych procedur,
• latwo migruja pomiedzy procesami,
• latwo daja sie replikowac.

Procesy sa dynamicznymi i wspobieznymi watkami sterowania. Wykonuja operacje na obiektach lokalnych i wspoldzielonych. Sa uruchamiane za pomoca wywolania operacji fork. W momencie inicjalizacji sa przypisywane do wirtualnych procesorow udostepnianych przez system Orca RTS.

Dane przekazywane jako wejsciowe sa kopiowane do przestrzni adresowej odbiorcy. Dane przekazywane jako wspoldzielone musza byc obslugiwane w specjalny sposob. Dostep do nich musi byc nadzorowany przez system RTS.

Procesy komunikuja sie za posrednictwem swoich argumentow wywolania zadeklarowanych jako zmienne klasy shared. Prawo dostepu do zmiennych wspoldzielonych jest przekazywane w chwili utworzenia procesu.

Jezyk dostarcza dwoch mechanizmow synchronizujacych prace procesow. Pierwszym z nich jest wzajemne wykluczanie przy wspolbieznym dostepie do danych lokalnych obiektu. Dostep ten jest realizwany wylacznie za pomoca metod obiektu. Drugim mechanizmem sa wartowniki, czyli warunki umieszczone w ciele metody i poprzedone slowem kluczowym guard. Wstrzymuja one wykonywanie procesu az do chwili zajscia oczekiwanego zdarzenia.

Operacje na obiektach dokonywane przez procesy sa

• atomowe,
• niezalezne,
• synchroniczne.

Kazda operacja dotyczy tylko jednego obiektu co oznacza ze jezyk nie dostaracza mechanizmow umoziwiajacych przetwarzanie transakcyjne zwiazanego z dostepem do wielu obiektow.

RTS

Decyduje on o semantyce srodowiska. Jest latwo wymienialny. Zostal zraalizowany w kilku wersjach min. jako samodzielny system, jako system pracyjacy w opaciu o srodowisko systemow UNIX i Amoeba.

RTS dostarcza mechanizmow dla

• implementacji strukturalnych typow danych
• uzgadniania stanu obiektow
• lokalizacji obiektow
• replikacji obiektow
• pakowania, kopiowania, porownywania obiektow
• zarzadzania pamiecia operacyjna,
• komunikacji pomiedzy procesami

Replikacja obiektow zwieksza odpornosc systemu, przyspiesza dostep do wspoldzielonych danych, umozliwia odczyt duzych wspoldzielonych obiektow bez generowania dodatkowego ruchu w sieci, zwieksza wspolbieznosc aplikacji. Replikacja w Orce jest powiazana z relokacja obiektow.

Mozliwe strategie replikacji:

1. Brak replikacji.
2. Pelna replikacja.
3. Czesciowa replikacja w oparciu o informacje
   • zbierane w czasie wykonania programu,
   • dostarczone przez kompilator,
   • kombinacje obu rozwiazan.

O replikacji obiektu w RTS 93 decyduje zarowno system RTS jak i kompilator. W czasie dzialania programu status i pooozenie obiektu moga sie zmieniac. Jezyk Orca nie zawiera element¢w uniemozliwiajacych statyczna analize profilu programu tj.

• wskaznikow
• zmiennych globalnych
• niskopoziomowych operacji na zmiennych dzielonych

Dla kazdego procesu kompilator tworzy rekord deskryptora procesu. Deskryptor procesu zawiera informacje o zmiennych dzielonych wykorzystywanych przez proces. Kompilator oblicza dla kazdego procesu graf przydzialu zasobow. Dla kazdego z obiektow z grafu tworzy wzorzec dostepu do danych i oblicza oczekiwane wartosci :

• Nreads - oczekiwana ilosc operacji odczytu
• Nwrites - oczekiwana ilosc operacji zapisu

Wzorce dostepu do danych sa to wyrazenia regularne opisujace dynamiczny profil dostepu do danych. Wartosci Nreads i Nwrites sa obliczane przez kompilator na podstawie heurystycznych regul tj :

• kazdy dostep do zmiennej ma wage 1
• iteracja zwieksza oczekiwana ilosc dostepow do danych a wiec wspolczynnik dla operacji witerowanych wynosi 16
• uprzednie sprawdzanie warunku zmniejsza prawdopodobienstwo wykonania danej operacji, a wiec wspolczynnik dla operacji warunkowych wynosi 1/2.

RTS decyduje o replikacji obiektu dopiero wtedy gdy obiekt jest tworzony przez proces po wykonaniu operacji fork. RTS trzymuje aktualna informacje o rzeczywistym stanie obiektow dzielonych. Komunikat z poleceniem wykonania operacji fork jest rozglaszany do wszystkich procesorow wirtualnych, ktore przeliczaja wartosci Nreads i Nwrites dla kazdego z obiektow.

Decyzja o replikacji obiektu zapada wtedy gdy oczekiwany koszt aktualizacji stanu replikowanego obiektu jest mniejszy od oczekiwanego kosztu aktualizacji jednej kopii przydzielonej np. do procesora ktory intensywnie z niego korzysta. Te dane moga byc uzyskane tylko dzieki statycznej analizie kodu. W sytuacji gdy jeden procesor zaczyna intensywnie korzystac z obiektu najlepiej jest zaprzestac replikacji i przeslac caly obiekt do danego procesora.

Zastosowanie strategii aktualizowania stanow obiektow po zapisie pozwala na przyspieszenie obslugi operacji zapisu wiekszych obiektow, jest jednak trudniejsze w realizacji niz strategia uniewazniania po zapisie. Moze jednak byc ona byc latwo zaimplementowana zarowno za pomoca bezpiecznego protokolu rozgloszeniowego jak i protokolu dwufazowej aktualizacji.

Operacje odczytu zmiennych dzielonych sa szybkie. Sa czesciej wykonywne niz operacje zapisu. Operacje zapisu korzystaja z sieci i sa bardziej kosztowne. Istnieje niebezpieczenstwo naruszenia spojnosci systemu przez niezalezne zapisy danych wspoldzielonych, np. danych replikowanych przez dwa rownoczesne zapisy.

Najprostsza strategia aktualizacji jest protokol aktualizacji kopii glownej. W roznych implementacjach RTS zostal zastosowany wraz z roznymi protokolami komunikacyjnymi tj. :

• komunikacja punkt - punkt,
• bezpieczna komunikacja rozgloszeniowa,
• niepewna komunikacja rozgloszeniowa.

1. Do zmienianiania stanu obiektow stosuje sie bezpieczny protokol rozgloszeniowy dostarczny przez system operacyjny tj. np. system Amoeba.
2. Komunikaty docieraja do kazdego z wirtualnych procesorow w sposob uporzadkowany.
3. Komunikaty nie moga zaginac.
4. Operacja zapisu polega na
   • zablokowaniu wszystkich kopii obiektu,
   • rozeslaniu nowej wartosci do wszystkich procesorow,
   • odblokowaniu wszystkich kopii.

Przy tej strategii wybor procesora na ktorym ma dzialac modul szeregujacy zdarzenia w systemie odbywa sie zgodnie z algorytmem wyboru lidera. Protokol ten jest odporny na utrate lidera, po wylaczeniu go z gry latwo wybrac nowego.

Zarzadzanie strukturami danych jest wymagane przy :

• pakowaniu przesylanych obiektow,
• kopiowaniu ich w czasie wywolan procedur,
• por¢wnywaniu zawartosci obiektow,
• przydziale i zwalnianiu pamieci operacyjnej na stercie lub stosie

Dane strukturalne tak samo jak procesy i obiekty abstarakcyjne sa reprezentowane w pamieci operacyjnej za pomoca deskryptorow. Kazda z operacji na zdefiniowanych przez uzytkownika strukturach danych jest wiec wykonywana przez jedna procedure co eliminuje koniecznosc pisania specjalnych metod :

• kopiujacych,
• pakujacych,
• porownujacych.

To podejscie pozwala programiscie nie przejmowac sie przydzielaniem i zwalnianiem pamieci operacyjnej.

Semantyka i szczegoly implementacyjne procesow zaleza od konkretnego systemu RTS. Podobnie jak dane, procesy sa reprezentowane przez deskryptory. RTS dostarcza podstawowych procedur obslugi procesow, sa to min. funkcje wbudowane jezyka:

• FORK(cpu, deskryptor-procesu, argumenty)
• NCPUS()

Dla kazdej z metod obiektu kompilator generuje deskryptor operacji. Wykonanie operacji na obiekcie polega na wykonaniu procedury systemu RTS :

• INVOKE(obiekt, deskryptor-operacji, argumenty)

Wywolanie operacji jest bardziej zlozone niz uruchomienie procesu, poniwaz zwiazane jest z blokowaniem dostepu do obiektow i wlaczeniem sprawdzania stanu wartownikow.

Bal, H.E. and Kaashoek, M.F.:
"Object Distribution in Orca using Compile-Time and Run-Time Techniques",
Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA '93),
Sep. 1993, Washington D.C., pp. 162-177.

Bhoedjang, R., Ruhl, T., Hofman, R., Langendoen, K, and Bal, H.:
"Panda: A Portable Platform to Support Parallel Programming Languages,"
Symposium on Experiences with Distributed and Multiprocessor
Systems III, Newport Beach, March 1992, pp. 297-312

Bal, H.E., Kaashoek, M.F., Tanenbaum, A.S., and Jansen, J.:
"Replication Techniques for Speeding up Parallel Applications on Distributed Systems"
Concurrency Practice & Experience, Vol. 4, No. 5, pp. 337-355, Aug. 1992

Tanenbaum, A.S., Kaashoek, M.F., and Bal, H.E.:
"Parallel Programming using Shared Objects and Broadcasting",
IEEE Computer, Vol. 25, No. 8, Aug. 1992, pp. 10-19.

Levelt, W.G., Kaashoek, M.F. Bal, H.E., and Tanenbaum, A.S.:
"A Comparison of Two Paradigms for Distributed Shared Memory",
Software--Practice and Experience, vol. 22, Nov. 1992, pp. 985-1010

Bal. H.E., Kaashoek, M.F., and Tanenbaum A.S.:
"Orca: A Language for Parallel Programming of Distributed Systems",
IEEE Transactions on Software Engineering,
vol. 18, No. 3, March 1992, pp. 190-205.

Kaashoek, M.F., Michiels, R., Bal. H.E., and Tanenbaum A.S,:
"Transparent Fault-tolerance in Parallel Orca Programs"
Symposium on Experiences with Distributed and Multiprocessor
Systems III, Newport Beach, March 1992, pp. 297-312

Bal, H.E.: "A Comparative Study of Five Parallel Programming Languages,"
EurOpen Spring 1991 Conference on Open Distributed Systems, Tromso,
20-24 May 1991, pp. 209-228 (Best Paper Award).