Współprogram

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Współprogramy (ang. coroutines) - Pojęcie współprogramu ma dwie odmienne definicje(!). Obie definicje zgodnie stwierdzają, że współprogram cechuje się posiadaniem ciągu instrukcji do wykonania i ponadto możliwością zawieszania wykonywania jednego współprogramu A i przenoszenia wykonywania do innego współprogramu B. W szczególności można wznowić pracę zawieszonego współprogramu A, a wykonywanie będzie podjęte w miejscu, w którym zostało zawieszone. Tym co różni obie definicje jest zdolność współpracy z rekurencyjnymi procedurami. (Nb. W językach programowania funkcyjnego koncepcja współprogramu istnieje pod postacią kontynuacji - pojęcia wprowadzonego niemal równocześnie z współprogramami. )

Obiekt współprogramu jest quasi-wątkiem. Tak jak wątek ma ciąg instrukcji do wykonania, w odróżnieniu od wątków obiekty współprogramów nie działaja równolegle. Jest niezmiennikiem systemu współprogramów to, że w każdej chwili, dokładnie jeden obiekt współprogramu wykonuje swoje instrukcje:

 \color{blue}   card\{coroutine:\ coroutine\ is\ Active\  \}=1.\color{black}

W literaturze znaleźć można termin włókno (ang. fiber) dla odróżnienia od wątku (ang. thread).

Współprogramy jako specjalny rodzaj klas Współprogramy jako bogatszy rodzaj podprogramów
W językach programowania: Simula67, Loglan 82, BETA można tworzyć

moduły coroutine tj. współprogramów. Składnia współprogramu różni się od składni klasy tym, że zamiast słowa class piszemy coroutine, i co ważniejsze, wewnątrz takiego modułu wolno używać instrukcji atomowych attach oraz detach. Instrukcje takie mogą się też pojawiać wewnątrz metod zadeklarowanych w współprogramie. Stwarza to nowe i interesujące możliwości współpracy współprogramów i rekursji.

"Subroutines are special cases of ... coroutines." –Donald Knuth.[1]

W assemblerze od dawna występuje pojęcie podprogramu - nie należy go mylić z pojęciem procedury. Podprogram istnieje w kodzie programu i ma co najwyżej jedną instancję. Nie jest możliwe rekurencyjne wykonywanie podprogramów.
Przykład: Łączenie drzew BST por. [Dahl i Wang 1971 ↓] oraz [Szałas i Warpechowska 1991 ↓, s. 112-116]

 \begin{array}{l}
 \mathbf{var}\ T:\ arrayof\ Traverser; \\ \\
\left \{ \begin{array}{l}
\mathbf{unit}\ Traverser:\ \mathbf{coroutine}(n: node); \\
\quad   \mathbf{var}\ kolejny:\ integer; \\
\left \vert \begin{array}{l}
\quad   \mathbf{unit}\ traverse:\ \mathbf{procedure}(m:\ node); \\
\quad   \mathbf{begin} \\
\qquad      \mathbf{if}\ m \neq none \\
\qquad      \mathbf{then} \\
\qquad\ \ \          \mathbf{call}\ traverse(m.left); \\
\qquad\ \ \          kolejny:=m.val; \\ 
\qquad \ \ \  \mathbf{detach};\ \ (*\ instrukcja\ \mathbf{detach}\ wznawia \\
\qquad \ \quad \ \ \ \      wspolprogram\ w,\ ktory\ ostatnio\ uaktywnil\ \\
\qquad \ \quad  \ \ \ \   ten\,(\mathrm{this})\ obiekt\ Traverser\ wykonujac\ \mathbf{attach}(.)\ *)   \\
\qquad\ \ \          \mathbf{call}\ traverse(m.right); \\
\qquad      \mathbf{fi} \\
\quad    \mathbf{end}\ traverse; 
\end{array} \right .  \\
\mathbf{begin} \\
\quad   \mathbf{return}; \\
\quad   \mathbf{call}\ traverse(n) \\
\mathbf{end}\ Traverser; 
\end{array} \right . \\
( Stworz\ drzewa\ BST,\ w\ liczbie\ np.\, k\ drzew.\ Dla \ kazdego\ drzewa\ d\ \\
stworz\ T[i]:=\mathbf{new}\ Traverser(d) \\
( Kolejne\ uaktywnienie\ tego\ wspolprogramu\ \mathbf{attach}(T[i])\ spowoduje \\
 wykrycie\ kolejnego\ co\ do\ wielkosci   elementu\ z\ drzewa\ d )
\end{array}

Przykład [2]

 \left . \begin{array}{l}  \mathbf{var}\ q := \mathbf{new}\ kolejka \\  
\mathbf{coroutine}\ produkuj \\
\quad    \mathbf{loop} \\
\qquad \mathbf{while}\ q\ nie\ jest\ pelna  \\   
\qquad \ \              stworz\ troche\ nowych\ przedmiotow  \\
\qquad \ \               wstaw\ przedmioty\ do\ q  \\
\qquad \ \           \mathbf{yield\ to}\ konsumuj \\
 \\
 \mathbf{coroutine}\ konsumuj \\
\quad      \mathbf{loop}  \\
\qquad          \mathbf{while}\ q\ jest\ niepusta \\
\qquad \ \               pobierz\ troche\ przedmiotow\ z\ q \\
\qquad \ \               uzyj\ te\ przedmioty \\
\qquad \ \           \mathbf{yield\ to}\ produkuj \\ 
\end{array} \right .


Uwagi. 1°.Mamy tu do czynienia z dynamicznym systemem współprogramów. Wyrażenia generujące postaci

new Traverser(...) umożliwiają stworzenie wielu obiektów typu współprogram Traverser. 2°. Obiekt współprogramu Traverser wywołuje metodę traverse(). Łańcuch dynamiczny tego obiektu wydłuża się o rekord aktywacji metody traverse. Łąncuch taki może być tak długi jak gałąź odwiedzanego drzewa BST. 3°. Instrukcje attach() oraz detach mogą wystąpić nie tylko w ciągu instrukcji współprogramu, lecz także w metodach współprogramu. 4°. Przełączenie wykonywania odbywa się pomiędzy łańcuchami dynamicznymi współprogramów.

Uwagi. 1°. Ten system współprogramów jest statyczny: zawiera dwa współprogramy.

Deklaracja coroutine automatycznie tworzy obiekty typu produkuj i konsumuj. 2°. W tym systemie sa dwa punkty wejścia. Otrzymany graf składa sie z dwu współprogramów i dwu przełączeń yield.

W latach 60 XX wieku współprogram był fragmentem kodu napisanego w assemblerze. wątki o następujących właśnosciach:

  • dokładnie jeden współprogram wykonuje swoje instrukcje, tzn. jest aktywny,
  • współprogram aktywny może przejść w stan pasywny wskazując przy tym na inny wątek, który ma być uaktywniony,
  • współprogram x uaktywniony w efekcie wykonania instrukcji attach(x) (w dotychczas aktywnym współprogramie y) kontynuuje wykonywanie instrukcji od odpowiedniego punktu wejścia, dokładniej: pierwsze uruchomienie instrukcji wątku współprogramu spowoduje wykonanie pierwszej instrukcji wątku, każda następna instrukcja attach(x) wznawiająca wykonywanie wątku współprogramu x rozpoczyna wykonywanie instrukcji od punktu wejścia wyznaczonego przez ostatnio wykonaną w nim instrukcję attach(...).

Zasada działania współprogramów[edytuj | edytuj kod]

System współprogramów można nazwać systemem quasi-współbieżnym. Nazwa ta jest uzasadniona dwojako: liczne przykłady programów współbieżnych np. producent-konsument, czytelnicy-pisarze itd. zapisane przy pomocy współprogramów okazuja się wystarczająco adekwatne do zastosowań. Inny argument wspierający użycie tej nazwy to fakt, że od bardzo dawna stosuje się współprogramy do symulacji systemów, np. w Simuli67, Loglanie'82 i in. Odpowiednia klasa Simulation dostarcza klasę wewnętrzną simproces - obiekty klas pochodnych od klasy simproces symulują rzeczywiste procesy np. pacjentów w systemie symulacji epidemii choroby, pojazdy w systemie symulacji ruchu w mieście itp.

Wielu autorów uważa, iż "współprogramy to podprogramy wykonywane w taki sposób, że sterowanie może zostać przekazywane pomiędzy nimi wielokrotnie, przy czym wywołanie danego współprogramu powoduje wykonywanie instrukcji od miejsca ostatniego przerwania wykonania (ostatniego punktu wyjścia), a nie od początku". Nie jest to całkiem ścisłe. Podprogramy (funkcja, metoda) tworzą rekordy aktywacji. Po opuszczeniu takiego rekordu jest on automatycznie usuwany i nie ma możliwości wznowienia go. Współprogramy wymagają więc wątków i są realizowane jako obiekty odpowiednich klas, a nie jako podprogramy czy procedury. Cytowany wyżej pogląd mocno zawęża koncepcję współprogramów. Co więcej, nie można zapominać, że instrukcjami wątku współprogramu mogą być instrukcje wywołania jego prywatnych metod(procedur). Metody te mogą zawierać instrukcje attach(...) przekazujące sterowanie z jednego do innego współprogramu. Dokładniej, instrukcja attach przekazując sterowanie z jednego do drugiego współprogramu przenosi je z łańcucha dynamicznego jednego współprogramu do łańcucha dynamicznego innego współprogramu.

Łańcuch dynamiczny współprogramu zawiera obiekt i wątek współprogramu i ponadto, jeśli wykonano instrukcję procedury, to do łańcucha dynamicznego dołączony jest rekord aktywacji procedury. Zakończenie wykonywania instrukcji procedury(metody) powoduje skrócenie łańcucha dynamicznego. Instrukcja attach(x) wykonana w rekordzie aktywacji procedury powoduje przejście do punktu wejścia w łańcuchu dynamicznym współprogramu x. Punktem wejścia (powrotu) dla dotychczas aktywnego współprogramu jest instrukcja w rekordzie aktywacji procedury występująca bezpośrednio za instrukcją attach(x). Widać stąd, że liczba punktów wejścia (powrotu) danego współprogramu może być zmienna w czasie i może nie być niczym ograniczona!

Podsumowując, współprogramy to więcej niż obiekty zwyczajnych klas, a mniej niż obiekty aktywne wątków (ang. threads).

Schemat zmian stanów obiektu współprogramu[edytuj | edytuj kod]

Schemat zmian stanów obiektu współprogramu

Współprogramy w języku Loglan '82[edytuj | edytuj kod]

  • instrukcją przenoszenia sterowania z aktywnego współprogramu do drugiego współprogramu x jest attach(x),
  • moduł współprogramu jest specyficzną klasą (stosuje się słowo 'coroutine' zamiast 'class'),
  • instrukcja attach(x) może występować nie tylko w wątku współprogramu, lecz także w prywatnych metodach współprogramu(!),
  • punktami wejścia do współprogramu są: pierwsza instrukcja wątku współprogramu oraz każda instrukcja następna po instrukcji attach(x),
  • można też używać bezparametrowej instrukcji detach, odpowiada instrukcji 'attach(ten współprogram, który ostatnio mnie wezwał)'.

Instrukcje przenoszenia sterowania między współprogramami w różnych językach programowania[edytuj | edytuj kod]

Instrukcje przenoszące sterowanie z jednego do drugiego współprogramu to

Argument x wskazuje na współprogram pasywny w danej chwili.

Przykładowe zastosowania współprogramów[edytuj | edytuj kod]

  • historycznie pierwsze współprogramy to skaner i Analizator składniowy kompilatora[Conway 1963 ↓],
  • podobny schemat występuje w wielu sytuacjach np. jeden współprogram zbiera wyniki pomiarów i zapisuje je w bazie danych, a drugi współprogram opracowuje zebrane wyniki, ogólny schemat to producent-konsument,
  • jeżeli jakaś metoda (funkcja lub procedura) jest wykonywana wielokrotnie z tymi samymi parametrami aktualnymi, to warto utworzyć odpowiednie obiekty współprogramu (tablicę współprogramów) dla każdego zestawu parametrów aktualnych. Następnie każdą instrukcję wywołania procedury zastępujemy odpowiednią instrukcją attach(..). Zysk może okazać się znaczny, ponieważ wykonanie instrukcji attach jest znacznie prostsze od tworzenia rekordu aktywacji procedury.
  • Jeśli współprogramy są klasami wyposażonymi w instrukcję attach(...) to można tworzyć hierarchie współprogramów wykorzystując dziedziczenie.
  • główne zastosowanie współprogramów to narzędzia symulacji, takie jak klasy Simulation w Simuli 67 i w Loglanie'82.



Przypisy

  1. Donald Ervin Knuth: The Art of Computer Programming. T. 1 Fundamental Algorithms. Addison-Wesley, 1997, s. 193-200. ISBN 0-201-89683-4..
  2. (porównaj en:coroutine)


Bibliografia[edytuj | edytuj kod]

  1. M.E. Conway. Design of a separable transition-diagram compiler. „Communications of the ACM”, July 1963. 
  2. Ole-Johann Dahl, Bjarne Myhrhaug, Kristen Nygaard: Common Base Language (Simula67). Oslo: NCC, 1970.
  3. O.-J. Dahl, A. Wang. Coroutine sequencing in a block structured environment. „BIT”, s. 425-449, 1971. 
  4. W. M. Bartol, i in.: Report on the Loglan'82 Programming Language. Warszawa Łódź: PWN, 1984.
  5. Andrzej Szałas, Jolanta Warpechowska: Loglan'82. Warszawa: WNT, 1991.