Programowanie współbieżne i rozproszone/PWR Wykład 3

Pojęcie krotki i przestrzeni krotek

Inne podejście do asynchronicznego modelu komunikacji zaproponował w latach osiemdziesiątych Gelernter. Wprowadził on notację o nazwie Linda, która udostępnia tzw. przestrzeń krotek, czyli coś w rodzaju nieskończonego bufora, za pomocą którego porozumiewają się ze sobą procesy. Jest jedna wielka, globalna przestrzeń krotek. Procesy porozumiewają się ze sobą umieszczając w przestrzeni krotek komunikaty i pobierając je z niej. Procesy nie muszą wiedzieć nic o sobie nawzajem, więcej mogą nie istnieć w tym samym czasie. Nadawca może odebrać komunikat od procesu, który już dawno zakończył swoje działanie.

Każdy komunikat przesyłany przez procesy to tzw. krotka.

Krotka

to ciąg (skończony), którego kolejnymi elementami są dane o określonych typach.

Przykładami krotek są:

• jednokrotki: (4), (3.14), ("żeton")
• pary: ('c', true), (5, 123)
• dłuższe krotki: (6, 'c', 3.14, "dane")

Każda krotka ma statycznie określoną długość. Nie może tworzyć krotek o dynamicznie zmienianej bądź wyliczanej długości. Typy poszczególnych elementów krotki mogą być dowolne typy proste lub typy złożone (tablice, rekordy). Nie ma jednak typu, którego wartościami byłyby krotki, więc krotka nie może być elementem krotki.

Sygnatura krotki

to ciąg, którego elementami są typy poszczególnych elementów krotki.

Sygnaturą krotki ('c', true, 3.14, "żeton") jest na przykład (char, boolean, real, string). W niektórych operacjach na przestrzeni krotek wymaga się podania sygnatury krotki.

Proste operacje na przestrzeni krotek

Linda nie jest tak naprawdę językiem programowania, ale raczej czymś w rodzaju biblioteki oferującej pewne operacje na przestrzeni krotek. Są to:

• Operacja wstawienia krotki t do przestrzeni krotek:

Output(t)

• Operacje odczytywania i obierania krotki o sygnaturze s:

Input (s) oraz Read (s)

• Nieblokujące wersje powyższych operacji w postaci funkcji logicznych:

Try_Input (s) oraz Try_Read (s)

Omówimy teraz po kolei powyższe operacji.

Wstawianie krotki

Ponieważ Linda jest rozproszonym mechanizmem asynchronicznym z nieograniczonym buforem, więc operacja wstawiania krotki do przestrzeni jest operacją nieblokującą. Ma ona postać

Output (t)

i w jej wyniku krotka t zostaje umieszczona w przestrzeni krotek. Jeśli taka krotka już się w niej znajdowała, to zostanie umieszczony kolejny egzemplarz takiej samej krotki. Przestrzeń krotek należy traktować jak multizbiór a nie zwykły zbiór krotek . Przykładowa operacja Output ('c', "ala", 4, 3.14) wstawi do przestrzeni krotek krotkę ('c', "ala", 4, 3.14) o sygnaturze (char, string, integer, real).

Wyjmowanie krotki

Do wyjmowania krotki z przestrzeni krotek służą dwie procedury blokujące:

input(s).

Argumentem obu tej procedury jest sygnatura krotki, na przykład:

input (x:integer, c: char)

wyjmuje z przestrzeni krotek krotkę o sygnaturze integer, char. Jeśli w danej chwili krotki o podanej sygnaturze nie ma w przestrzeni krotek, to proces wykonujący procedurę Input jest wstrzymywany tak długo aż żądana krotka pojawi się w przestrzeni krotek. Na skutek wykonania operacji Input z przestrzeni krotek jest usuwana jedna krotka o podanej sygnaturze, a poszczególne jej elementy są przypisywane na zmienne występujące w opisie sygnatury. W omawianym przykładzie pierwszy element krotki zostanie przypisany na zmienną x a drugi na zmienną c.

Jeśli w przestrzeni krotek jest wiele krotek o podanej sygnaturze, to wybór usuwanej krotki jest niedeterministyczny. Niedeterminizm ten jest jednak ograniczany zasadą sprawiedliwości: jeśli operacja Input z podaną sygnaturą jest wykonywana nieskończenie często, to w końcu każda krotka o tej sygnaturze zostanie wyjęta z przestrzeni krotek.

Podobna zasada obowiązuje przy budzeniu procesów oczekujących na operacji Input. Jeśli na krotkę o pewnej sygnaturze czeka ich wiele, i krotka pojawi się w przestrzeni, to wznawiany jest któryś z oczekujących procesów. Nie można zatem zakładać, że oczekujące procesy są kolejkowane, ale można oczekiwać sprawiedliwości. Mamy gwarancję, że jeśli krotka pojawi się nieskończenie wiele razy w przestrzeni, to każdy z oczekujących procesów w końcu zostanie obudzony.

Odczytywanie krotki

Procedura Read jest operacją bardzo podobną do Input. Jedyna różnica polega na tym, że krotka nie jest usuwana z przestrzeni krotek. Podobnie jak w przypadku Input proces wykonujący Read oczekuje aż w przestrzeni zjawi się krotka o podanej sygnaturze. Również procesy oczekujące są budzone w sposób sprawiedliwy.

Zauważmy, że po pojawieniu się krotki o sygnaturze, na którą czekają procesy wykonujące Read, mogą zostać obudzone wszystkie procesy oczekujące, bo każdy z nich jedynie odczytuje krotkę z przestrzeni pozostawiając ją tam. Jeśli jednak na taką samą krotkę oczekują procesy i na operacji Read i na operacji Input, to wtedy na skutek niederministycznego wyboru budzonych procesów możliwe są różne sytuacje. Może zdarzyć się tak, że zostanie obudzony tylko jeden proces oczekujący na Input, może też obudzić się kilka (niekoniecznie wszystkie) procesy czekające na operacji Read, a po nich dopiero proces oczekujący na Input.