Metody realizacji języków programowania/MRJP Wykład 13

From Studia Informatyczne

autor: Andrzej Salwicki (salwicki@mimuw.edu.pl)

Spis treści

Realizacja obiektów aktywnych (wątków, procesów) w języku z procesami współbieżnymi i rozproszonymi

Obiekty aktywne: współbieżne i rozproszone

W niektórych językach programowania obiektowego pewne obiekty mogą być aktywne tzn. wykonywać swoje własne instrukcje równocześnie z innymi obiektami aktywnymi.

Obiekty aktywne (alias procesy albo wątki) są dla nas obiektami, które posiadają możliwość wykonywania instrukcji równocześnie z innymi procesami. Mówiąc dokładniej, obliczenia procesów mogą być wykonywane:

  • współbieżnie (wiele procesów wykonywanych na jednym procesorze fizycznym),
  • w rozproszeniu (na maszynach połączonych siecią),
  • równolegle (na maszynie z wieloma procesorami, które dzielą się wspólną pamięcią).

Przypomnijmy, że zwykle obiekt jest kolekcją swych atrybutów: pól i metod. Taki obiekt nie wykonuje swoich własnych poleceń. W odróżnieniu od zwykłych obiektów klas istnieć mogą obiekty aktywne odpowiednio zadeklarowanych klas. W języku Java są to obiekty podklas klasy Thread. W Loglanie są to obiekty procesów. W Adzie zadania (ang. task) są wątkami współbieżnymi. Istnieje rozszerzenie o nazwie GLADE, które pozwala kompilatorowi "gnat" języka ADA z rodziny kompilatorów gcc (GNU C compiler) tłumaczyć i wykonywać programy w środowisku rozproszonym. A więc mamy sytuację podobną do tej w Javie. Poniżej przedstawiamy ciekawe, choc mało znane koncepcje zaproponowane przez Bolesława Ciesielskiego (koncepcja obcego wołania metod występujących w obiektach aktywnych czyli procesach) i Oskara Świdę koncepcja wieloprocesorowej maszyny wirtualnej.


Współbieżnie czy w rozproszeniu?

Pytanie takie pojawia sie bardzo wcześnie, gdy zamierzamy w języku programowania zawrzeć narzędzia programowania rozproszonego i współbieżnego. W Javie mamy dwie odrębne koncepcje: procesy współbieżne realizowane są jako obiekty podklas klasy Thread. Procesy rozproszone wymagają użycia mechanizmu [RMI]link RMI. Trzeba więc zapoznać się z dwoma odrębnymi koncepcjami i opanować ich własności.

W języku Loglan'82 zrealizowano rozproszoną współbieżność. Wyglądające jednakowo wyrażenie generowania nowego obiektu new MojProces (arg1, arg2, ) tworzy obiekt procesu, który jest alokowany na wirtualnej maszynie wskazanej przez wartość wyrażenia arg1. Jeśli ta wartość wynosi 0, to alokacja odbywa się na bieżącym procesorze i wtedy stary i nowy proces działają współbieżnie dzieląc się czasem maszyny wirtualnej. Jeśli wartość ta jest różna od zera, to nowy proces jest alokowany na procesorze o wskazanym numerze = arg1 i dalsze obliczenia odbywają sie w rozproszeniu. Łatwo dostrzec, że model ten dopuszcza wiele różnych odmian wykonywania obliczeń w rozproszeniu wymieszanym ze współbieżnościa.

Statyczna czy dynamiczna konfiguracja systemu procesów

Podstawowa decyzja jaką należy podjąć w zakresie konfiguracji systemu procesów w programie dotyczy tego, czy liczba obiektów aktywnych programu jest stała czy zmienna? W niektórych językach programowania współbieżnego, zwłaszcza tych, które służą tworzeniu sytemów czasu rzeczywistego lub procesów operacyjnych, wybiera się opcję statyczną. W językach obiektowych naturalny jest wybór opcji dynamicznej. Oznacza to, że liczba procesów aktywnych zmienia się w trakcie obliczeń, że w programie występują wyrażenia generujące obiekty aktywne.

Mechanizmy komunikacji procesów rozproszonych

Podstawowym mechanizmem komunikacji procesów rozproszonych jest przekazywanie komunikatów. Pomysł B. Ciesielskiego jest zbudowany na dwu składnikach:

  1. komunikaty mają postać wywołania metody w procesie czyli obiekcie aktywnym,
  2. procesy mogą dynamicznie zmieniać status swoich metod z prywatnej na publiczna (enable) i odwrotnie (disable).

W efekcie mamy prostą i pełną znaczeń wspólną realizację instrukcji wywołania metody przez procesy: wywołujący (ang. caller) i wywoływany (ang. callee).

Tworzenie procesu i jego scenariusz

Proces powstaje w wyniku obliczenia wartości wyrażenia new MojProces(nrMaszynyWirtualnej, inne parametry). Nowoutworzony proces może zostać zapamiętany jako wartość zmiennej typu MojProces. Poniższy rysunek przedstawia stany procesu i instrukcje powodujące zmiany stanu.

diagram stanów procesu Typ wartości pierwszego parametru powinien byc integer. Wartość tego parametru wskaże, na której maszynie wirtualnej zostanie umieszczony nowy proces. Wartość równa zeru nakazuje umieszczenie procesu na tej samej maszynie wirtualnej, która oblicza wartość wyrażenia newMojProces(...).

Po zakonczeniu wykonywania instrukcji konstruktora proces przechodzi w stan PASYWNY z MASKą pustą. Zmienna x typu MojProces może zapamiętać wartość wyrażenia.

Uruchomienie (lub wznowienie) wątku wymaga, by inny proces, posiadający zmienną x wskazującą na nasz proces, wykonał instrukcję resume(x) Proces x przechodzi w stan AKTYWNY i wykonuje instrukcje swego wątku równocześnie z instrukcjami innych procesów. Równocześnie tzn. współbieżnie z innymi procesami aktywnymi na tej samej maszynie wirtualnej i równolegle z procesami aktywnymi wykonywanymi na innych maszynach wirtualnych wieloprocesorowej, sieciowej maszyny wirtualnej.

Wykonanie instrukcji:

  • stop spowoduje przejście procesu w stan PASYWNY.
  • enable metoda1, metoda 2; spowoduje dodanie nazw metod metoda1 i metoda2 do MASKi.
  • disable metoda 2; spowoduje usunięcie metody metoda2 z MASKi.
  • accept metoda3, metoda2; spowoduje dodanie nazw metod metoda3 i metoda2 do MASKi i oczekiwanie na to, by inny proces wezwał jakąś metodę znajdującą się w MASce.
  • call y.Metoda(parametry) jest tzw. obcym wołaniem metody (zob. poniżej)

Obce wołanie metod w procesach

Na czym to polega?

Składniowo wygląda to jak wołanie metody w obiekcie

    x.TaMetoda(parametry aktualne)

gdzie x jest nazwą obiektu procesu czyli wartością zmiennej x jest obiekt procesu, TaMetoda jest nazwą pewnej metody w obiekcie x.

Semantyka to cały protokół porozumiewania się procesu y wykonującego tę instrukcję procedury z wzywanym procesem x.

proces wywołujący y:

  oblicz parametry aktualne                     
  sprawdź, czy proces x istnieje
     jeśli NIE, to czekaj
     jeśli TAK, to sprawdź, czy proces x jest aktywny
                              jeśli NIE, to czekaj
                              jeśli TAK, to sprawdź, czy TaMetoda jest w masce
                                   jeśli NIE, to czekaj
                                   jeśli TAK, to przekaż parametry procesowi x
                                                oczekuj na podpowiedź;
                                                odbierz wyniki;


proces x:

       wykonuj swoje instrukcje; po każdej z nich (przy ;) sprawdzaj, czy inny proces 
              nie wzywa do wykonania twojej otwartej (ang. enabled) metody;
          jeśli TAK, to zapisz MASKę na stos;
                       wyzeruj MASKę;
                       wykonaj wzywaną metodę z otrzymanymi od innego procesu parametrami;
                       po jej zakonczeniu wyślij wyniki tzn. parametry out;
                       odtwórz MASKę ze stosu;
                       wykonaj instrukcję
                       return disable M,N enable M',N', P'; 
                       kończącą wykonywanie wezwanej metody;

Tak więc polecenie x.Tametoda(...) wykonane w procesie y przerywa pracę procesu x. Proces x sprawdza, czy jest gotów do przyjęcia tego przerwania, tzn. czy metoda Tametoda znajduje się w masce procesu x. Jeśli tak, jest to proces x wykonujący wzywaną metodę. Po zakończeniu tego zadania proces x powraca do wykonywania swego wątku poleceń. Trochę inaczej przebiega ta komunikacja, gdy proces x wykona polecenie accept mt1, ..., mtk; Instrukcja accept w procesie x jest wykonywana wspólnie z instrukcją innego procesu wywołującą taką metodę procesu x, która znajduje się w jego masce. Metody mt1, ... , mtk wyliczone po słowie accept powiększają maskę na czas wykonywania instrukcji accept. Oznacza to, że instrukcja accept oczekuje na wywołanie metody znajdującej się w masce aktualnego procesu.

Opis realizacji mechanizmu obcego wołania metod

Poniżej opisujemy realizację zaproponowaną przez Bolesława Ciesielskiego w 1988.

Sieciowe wskaźniki do obiektów procesów

Wskaźnik do obiektu-procesu ma udostępniać obiekt aktywny, który być może jest umieszczony na odległym komputerze, lub być może znajduje sie na tej samej maszynie wirtualnej. Przyjęto, że globalny wskaźnik do procesu ma trzy pola:

  • nr węzła (tj. nr maszyny wirtualnej) w sieci,
  • nr procesu w węźle,
  • licznik służący do wykrywania wskażników do procesów martwych (istotne dla celów kompaktyfikacji i odśmiecania).

Struktury

Pamięć procesów

Każdy proces jest traktowany jako proces rozproszony nawet wtedy, gdy działa współbieżnie z innymi na tej samej maszynie wirtualnej. Każdy proces posiada więc własną pamięć w postaci tablicy M jednowskaźnikowej. Nazwa tej tablicy jest umieszczona w deskryptorze procesu. W tablicy M zapisywane są: kod programu, statyczne struktury danych maszyny wirtualnej, sterta obiektów oraz tablica H adresów wirtualnych.

Deskryptory procesów

Deskryptor procesu jest rekordem zawierajacym pewne globalne struktury danych maszyny wirtualnej - właściwe dla danego procesu. Globalna tablica deskryptorów procesów jest zadeklarowana statycznie (w obecnej eksprymantalnej wersji ma ona 64 elementy). Czyli nr procesu mieści sie w jednym bajcie (por. wskaźnik do procesu).

Kolejka procesów gotowych - AKTYWNYCH

Procesy, które nie są PASYWNE (po wykonaniu instrukcji stop) ani oczekujące na obce wywołanie metody (po wykonaniu instrukcji accept), są zapisane do kolejki procesów gotowych. Pierwszy element tej kolejki to proces aktualnie wykonywany. Zmienna thispix zawiera idetyfikator procesu wykonywanego bieżąco, zmienna thisp zawiera deskryptor bieżącego procesu.


Komunikaty

Komunikaty to jedyny sposób porozumiewania sie węzłow rozproszonej maszyny wirtualnej. Każdy komunikat zawiera numer węzła i numer procesu nadawcy. Każdy komunikat zawiera nr procesu odbiorcy. Rodzaje komunikatów (każdemu typowi komunikatu mogą towarzyszyć inne parametry: resume - wznowienie procesu create - utworzenie procesu creack - po zakończeniu utworzenia procesu, killpr - zabicie procesu rpcall - obce wołanie metody rpcack - powrót z obcego wołania askpro - zapytanie o nr prototypu proack - odpowiedź, numer prototypu errsys - błąd, numer błędu

Globalna kolejka komunikatów

Każdy odebrany komunikat zostaje umieszczony w globalnej kolejce komunikatów.

Kolejka procesów czekających na obsługę obcego wołania metody

Komunikaty domagajace się obsłużenia poprzez obce wołanie umieszczane są w lokalnej kolejce danego procesu.

Stos masek metod

Dla każdego procesu musimy zapamietywać w stosie wartości zmiennej systemowej MASKa. Po wyjści z obcego wołania procedury zdejmujemy ze stosu MASKę zapisaną tam uprzednio przy rozpoczęciu wykonywania obcego wołania metody.

Algorytmy

Inicjowanie maszyny wirtualnej

Lokalna maszyna wirtualna powoduje otwarcie okienka - konsoli. W tym okienku mozna wykonywać polecenia dotyczące wykonywania programów - są one zgrupowane w menu Execute, inne polecenia zgrupowane w menu Machine pozwalają dołączyc lokalną maszne wirtualnę do innej(innych) maszyn wirtualnych. Trzecia grupa poleceń umożliwia kompilacje i edycje programów.

Zarządzanie procesami

Generowanie procesu

Generowanie procesu rozpoczyna się tak jak tworzenie obiektu klasy.

Powrót z generacji procesu

Po zakończeniu wykonywania konstruktora procesu (w Loglanie jest to ciag instrukcji wykonywany począwszy od linii begin w deklaracji procesu do polecenia return)

Zakończenie procesu

Po wykonywaniu ostatniej instrukcji wątku procesu obiekt tego procesu staje się zbędny. Nie mozna go reaktywowac np. poprzez instrukcję resume, nie można też uzyskac dostepu do pól ani metod tego procesu ponieważ każdy proces wszystkie swoje atrybuty chroni jako prywatne. Wobec tego obiekt taki może i powinien zostac usuniety.

Usuwanie procesu

Zwalniane jest pole obiektu procesu.

Podział czasu

Czas procesora fizycznego przydzielany jest procesom oczekującym w kolejce procesów gotowych.

Obce wołanie metod

Rozpoczęcie
Instrukcja accept
Operacje na maskach metod
Obsługa błędów

Wysyłanie komunikatu

Do obsługi wysyłania komunikatów użyto mechanizmu gniazdek (ang. socket)

Zestaw poleceń dotyczących procesów

  • x := new MojProces(nrWęzła, inne parametry)
  • resume(x) — zmienna x wskazuje na istniejący i pasywny proces
  • /* call */ x.Metoda(...)— x wskazuja na istniejący aktywny proces
  • enable <lista metod które wejdą do MASKi>
  • disable <lista metod usuwanych z MASKi>
  • accept <lista metod dodawanych do MASKi na czas wykonywania tej instrukcji>
  • return disable <metody> enable <metody>
  • stop

Łączenie maszyn wirtualnych w wieloprocesorową wirtualną maszynę wirtualną

Poniżej przytaczam opis eksperymentalnej realizacji. Każda loglanowska maszyna wirtualna VLP zainstalowana w sieci, niekoniecznie lokalnej, posiada swój numer identyfikacyjny 0<nr<256. Numery te powinny różnić sie między sobą. Maszyna wirtualna A może dołączyć do innej (innych) maszyn wirtualnych. W tym celu jej operator powinien wykonać polecenie

- Machine -> Connect 
- wskazać IP lub URL maszyny wirtualnej B do której chce dołączyć
- zatwierdzić

Od tej pory maszyny połączone z maszyną B tworzą razem z maszyną A jedną wieloprocesorową sieciową maszynę wirtualną A + B.

Od tego momentu aż do momentu wykonania polecenia Disconnect ... Maszyna wirtualna pozwala wykonywanemu programowi alokować nowo tworzone procesy bądź na lokalnej maszynie wirtualnej bądź na maszynie wirtualnej o wskazanym numerze.

Ponadto maszyny wirtualne mogą wymieniać sie komunikatami i w efekcie realizować obce wołanie metod w sposób synchroniczny bądź asynchroniczny.