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

Abstrakcyjne struktury danych

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

Orca zapewnia restryktywna kontrole typow. Wraz z definicja struktury obiektu dostarczana jest definicja metod dostepu. Obiekty sluza do synchronizowania pracy wspolbieznych procesow.

Procesy

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.

Komunikacja pomiedzy procesami

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

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


RTS

System 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

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
Realizacja replikacji (RTS 93)

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.

Statyczna analiza kodu

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 :

Umieszcza je nastepnie w kodzie obiektowym jako informacje dla RTS o dynamicznym profilu procesu.

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 :

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.

Uzgadnianie stanow obiektow

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. :

Rozproszony protokol aktualizacji

  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
Bezpieczne rozglaszanie

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.

Realizacja struktur danych.

Zarzadzanie strukturami danych jest wymagane przy :

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 :

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

Zarzadzanie procesami

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:

Zarzadzanie operacjami

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

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


ODNOSNIKI

Glowna strona Orki w Vrije Universitejt Amsterdam


BIBLIOGRAFIA

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