Kiedy proces spawnuje inny proces

Moje doświadczenie dotyczy teorii / logiki złożoności (gdzie przez większość czasu jest tylko jeden proces) oraz przetwarzania rozproszonego (gdzie jest procesów, a jeden lub więcej może zawieść z czasem). Jednak chcę teraz móc powiedzieć coś o procesie odradzania / tworzenia / wydzielania innego procesu. Czy istnieje rygor w obliczeniach równoległych, systemach operacyjnych itp., Który to wyjaśnia? $n$

Motywacja:

Próbuję skonstruować modele, które wyodrębnią niektóre cechy interakcji molekularnych. Chciałbym powiedzieć, że zestaw reakcji chemicznych jest procesem niezależnym i że w pewnym etapie czasu powstaje kolejny niezależny proces . Intuicyjnie te rzeczy wydają się niezależnymi procesami, ponieważ nie mają ze sobą kontaktu po czasie - lub bardzo mało kontaktu, a jedynie „wiadomości”. $S$ $t$ $S'$ $t$

Bardziej formalnie:

(1) Czy istnieją wcześniej zdefiniowane definicje CS, które wychwytują pojęcie jednego procesu odradzającego inny niezależny proces? Szczególnie interesuje mnie możliwość wytyczenia miejsca, w którym zatrzymuje, a i dlaczego to jest „rozsądne”. $S$ $S'$

(2) Jeśli istnieje więcej niż jedna odpowiedź na (1), jakie są zalety i wady różnych definicji?

(Uwaga: nie mam pojęcia, jak odpowiednio to oznaczyć i planuję ponownie oznaczyć w zależności od odpowiedzi).

dc.parallel-comp process-algebra Aaron Sterling
źródło

Zawsze uważałem, że forkwywołanie systemowe w systemach operacyjnych uniksopodobnych jest bardzo eleganckie. Możesz to postrzegać jako operację atomową, która powiela bieżący proces. Przed rozwidleniem był tylko jeden proces , zaś po rozwidleniu były dwa procesy i . Jeśli nadmiernie uprościmy rzeczy, i są identyczne we wszystkich innych aspektach, z wyjątkiem tego, że istnieje jednobitowy wskaźnik, który informuje , że jest to „nowy” proces, podczas gdy wie, że jest to proces „oryginalny”. Po tym i mogą kontynuować osobno, a nawet mogą

S

$S$

S

$S$

S^{'}

$S'$

S

$S$

S^{'}

$S'$

S^{'}

$S'$

S

$S$

S

$S$

S^{'}

$S'$ modyfikować się .

Jukka Suomela,

@Jukka: Dziękuję :-) Byłoby miło, gdyby istniał sposób na połączenie tego, co robię, z prymitywnym Uniksem.

Aaron Sterling

Odpowiedzi:

Oczywiście istnieje wiele systemów do modelowania procesów. Należą one do kategorii algeb procesu . Kluczowymi przykładami są -calculus , CCS , ACP i CSP . $\pi$

Rachunki procesów mają podstawowe mechanizmy określania zachowania procesu, w tym: wysyłanie i odbieranie wiadomości (synchronicznie lub asynchronicznie), tworzenie procesów równoległych, niedeterministyczny wybór między zachowaniami oraz replikacja procesów. Chociaż kamień nazębny jest niewielki pod względem liczby konstruktów, są one bardzo ekspresyjne i przeprowadzono wiele badań w celu zbadania ich właściwości.

W -calculus różni się od pozostałych tym, że pozwala w istocie, procesy są przekazywane jako wartości klas. W rzeczywistości umożliwia przekazywanie nazw kanałów jako wartości pierwszej klasy, umożliwiając zmiany w topologii dynamicznej. Prawdopodobnie jest to rachunek, którego potrzebujesz, ponieważ oferuje on największą dynamikę. $\pi$

CSP (komunikowanie procesów sekwencyjnych) jest trochę dziwne, patrząc z perspektywy modelowania cząsteczek. Ma wiele teorii wsparcia i narzędzi. (Wymyślony przez CAR Hoare.)

CCS i ACP mają mniejszą dynamikę niż calculus, ale są znacznie łatwiejsze do analizy i symulacji. Solidny zestaw narzędzi o nazwie CRL (i CRL2) jest dostępny dla ACP. Podobne narzędzia z pewnością istnieją w CCS. $\pi$ $\mu$ $\mu$

Zacznę od zbadania powiązanej pracy (patrz poniżej), a następnie znajdę, który formalizm modelowania pasuje do tego, czego szukasz.

W rzeczywistości przeprowadzono sporo pracy przy modelowaniu reakcji chemicznych i procesów biologicznych przy użyciu algebry procesowej. Prawdopodobnie najlepszym miejscem do obejrzenia jest lista publikacji Lucy Cardelli . Cała jego linia badań nad BioComputing ma prawdopodobnie 30 artykułów na ten temat. Ta rozmowa zawiera przegląd większości jego prac. To jeden jest nieco bardziej formalny, choć czytając gazety jest naprawdę jedynym sposobem, aby zobaczyć szczegóły.

Jednym z podejść, które bezpośrednio modeluje procesy chemiczne, jest CHAM (chemiczna maszyna abstrakcyjna). Kluczowym składnikiem jest tutaj rozwiązanie cząsteczek i błon. Istnieją zasady podgrzewania i chłodzenia w celu uporządkowania cząsteczek i usuwania śmieci. Te zasady są odwracalne. Wreszcie rządzą reakcje, które modelują reakcje. W przeciwieństwie do algeb procesu, modele CHAM nie martwią się tak bardzo składnią procesów, więc możesz wymyślić własną reprezentację cząsteczek.

Przepisz logikę zrealizowaną w zestawie narzędzi Maude oferuje inne mniej lub bardziej bezpośrednie podejście do określania takich reakcji. Trzeba tylko określić zasady przepisywania, przekazywanie „zupy” odbywa się automatycznie. Zestaw narzędzi umożliwiłby symulację i analizę (niewielkich) reakcji chemicznych. Istnieje również probabilistyczny wariant Maude.

Dave Clarke
źródło

Czy wśród możliwości można również rozważyć sieci petri? rozwidlenie można wymodelować, mając miejsce z dwoma wychodzącymi przejściami.

M. Alaggan,

Mówiąc bardziej ogólnie, interakcje w stylu petri-net mogą być modelowane w logice liniowej (na przykład, choć nie jedyny, patrz „Równoczesna struktura logiczna: fragment propozycji” autorstwa Watkinsa i in., TYPES 2003)

Rob Simmons,

Dziękuję, Dave. Być może z humoru jednym z moich projektów jest przedłużenie pracy, którą Cardelli wykonał w kilku artykułach na tej stronie, do której linkujesz. Moja wiedza na temat algebry procesów jest ograniczona, więc starałem się unikać formalizowania rzeczy w ten sposób, jeśli to możliwe. Cardelli definiuje bio-wersje -calculus, ale nie rozumiem ich zbyt dobrze. Z pewnością pomaga ci myśleć, że może to być najlepszy kierunek. To kolejny powód, dla którego muszę nauczyć się nowego formalizmu.

π

$\pi$

Aaron Sterling

@M. Alaggan: Na pierwszy rzut oka wydaje się, że sieci Petriego mogłyby to zrobić. Każde miejsce można uznać za pulę chemikaliów. Każde przejście można uznać za reakcję. Zatem gdybyśmy mieli miejsca o nazwach H i O i H2O, przejście mogłoby wziąć dwa tokeny z H jeden z O i umieścić jeden token w H2O. Problem z modelowaniem w ten sposób polega na tym, że tylko jedno z takich przejść może strzelać jednocześnie, w przeciwieństwie do algebr procesowych, które umożliwiłyby uruchomienie wielu takich przejść jednocześnie.

Dave Clarke

@Aaron: w zależności od tego, co próbujesz zrobić, przydatne mogą być bardziej nowoczesne rachunki procesowe, takie jak BioPEPA.

András Salamon,

Inną linią pracy, która - jak sądzę - jest związana z BioComputing, ale nie jest taka sama (niestety nie jestem zbyt dobrze zorientowana w tej dziedzinie), jest „przetwarzanie membranowe”.

Moje rozumienie obliczeń membranowych polega na tym, że wykorzystuje metafory szeroko rozwinięte w świecie procesów kakaowych (odpowiedź Dave'a Clarke'a podała tam dobry zestaw wskaźników) wprost do modelowania interakcji komórkowych. Dobrym przewodnikiem po komputerach membranowych jest prawdopodobnie trafnie nazwany Przewodnik po komputerach membranowych autorstwa Paun i Rozenberga w TCS. To było kilka lat temu (i nie jestem teraz w ścianie płatniczej, aby to sprawdzić), ale wierzę, że niektóre modele przetwarzania membranowego mają pojęcie „rozwidlenia”, które ma jakoś odzwierciedlać mitozę komórkową.

Rob Simmons
źródło

Dzięki, Rob. O ile mi wiadomo, praca Cardellego nie dotyczy przetwarzania membranowego. Bardziej koncentruje się na budowaniu teorii języka programowania dla obwodów DNA. Doceniam wskaźnik, ale myślę, że szukam czegoś bardziej „głównego nurtu” (co oznacza, że nie jest w żaden sposób związane z biologią).

Aaron Sterling

To z pewnością alternatywa. @Aaron: Cardelli's Brane Calculus lucacardelli.name/Papers/Brane%20Calculi.pdf modeluje membrany.

Dave Clarke,

Ha! Moc crowdsourcingu! Dzięki jeszcze raz! :-)

Aaron Sterling