Исчисление процессов

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Исчисление процессов (алгебра процессов) — семейство связанных подходов к формальному моделированию параллельных систем.

Большой вклад в развитие данного направления теоретической информатики внесли Робин Милнер, разработавший исчисление взаимодействующих систем CCS (Calculus of Communicating Systems) и Энтони Хоар, разработавший теорию взаимодействующих последовательных процессов CSP (Communicating Sequential Processes). Другими примерами являются TCC (англ. timed concurrent constraints), алгебра общающихся систем (англ.) (ACP), LOTOS. Более современными методами являются пи-исчисление, исчисление окружений (англ.), PEPA (англ.), fusion calculus (англ.), join-calculus (англ.) и другие[1][2].

Метод рандеву[править | править вики-текст]

В случае CCS за основу положен механизм взаимодействия, называемый рандеву. Это предполагает, что взаимодействие между процессами происходит мгновенно. В случае CSP взаимодействие между процессами производится при помощи сообщений.

Отличительные черты[править | править вики-текст]

Несмотря на разнообразие существующих исчислений процессов, включающих варианты, имеющие дело со стохастическими процессами, временны́ми ограничениями и т. п., всем исчислениям присущи следующие основные черты[3]:

  • представление взаимодействий между независимыми процессами в виде передачи сообщений, а не изменения разделяемого процессами состояния;
  • описание процессов и систем при помощи ограниченного набора примитивов и операций для комбинирования этих примитивов;
  • определение алгебраических законов для операций над процессами, позволяющих проводить эквациональные рассуждения над процессными выражениями.

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Baeten, 2004
  2. Giurca, A. Handbook of Research on Emerging Rule-Based Languages and Technologies: Open Solutions and Approaches: Open Solutions and Approaches. — Information Science Reference, 2009. — P. 224. — 862 p. — ISBN 9781605664033.
  3. Pierce, 1997

Литература[править | править вики-текст]

  • Milner, R. Communication and Concurrency. — Prentice-Hall, Inc., 1989. — ISBN 0-13-115007-3.
  • Хоар Ч. Взаимодействующие последовательные процессы. — М.: Мир, 1989. — 264 с.
  • Pierce, Benjamin. The Computer Science and Engineering Handbook. — CRC Press, 1997. — P. 2190–2207. — ISBN 0-8493-2909-4.
  • Baeten, J.C.M. A brief history of process algebra (англ.) // Rapport CSR 04-02. — Vakgroep Informatica, Technische Universiteit Eindhoven, 2004..

Ссылки[править | править вики-текст]