Дискретные детермирированные процессы : реальное время, параллелизм, сложность, языки описания

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Доступ платный или только для подписчиков

Аннотация

Рассмотрены модели и языки, предназначенные для описания и управления выполнением в реальном времени дискретных детерминированных процессов. Процессы разделены на свободные и зависимые от реального времени, введены характеристики сложности процессов, учитывающие фактор одновременности (параллелизма) при их выполнении. Предложены унифицированные операции композиции вычислимых функций, на основе которых создан язык, позволяющий в естественной форме описывать параллелизм алгоритмических процессов. Показано, каким образом фактор реального времени может быть отражен в процессах путем расширения языка примитивами управления изменением состояний процесса в зависимости от контролируемого времени.

Полный текст

Доступ закрыт

Об авторах

В. П. Кутепов

Национальный исследовательский университет “МЭИ”

Автор, ответственный за переписку.
Email: kutepov@appmat.ru
Россия, Москва

Список литературы

  1. Agha G., Mason I., Smith S. Talcott C. Towards a Theory of Actor Computations// Third International Conf. on Concurrency Theory (CONCUR ‘92). Springer-Verlag, 1992. P. 565–579.
  2. Вальковский В.А., Котов В.Е., Марчук А.Г., Миренков Н.Н. Элементы параллельного программирования // Радио и связь. 1983. 240 c.
  3. Питерсон Дж. Теория сетей Петри и моделирование систем. М.: Мир, 1984. 264 c.
  4. Keller R.M. Parallel Program Schemata and Maximal Parallelism // J. ACM. 1973. V.20. № 3. P. 514–537.
  5. Milner R. A Calculus of Communicating Systems // Lecture Notes in Computer Science. Springer-Verlag, 1980. P. 184.
  6. Хоар Ч. Взаимодействующие параллельные процессы. М.: Мир, 1992. 184 с.
  7. Кутепов В.П., Фальк В.Н. Функциональные системы: теоретический и практический аспекты // Кибернетика. 1979. № 1. С. 45–58.
  8. Кутепов В.П. Модели и языки для описания параллельных процессов // Изв. РАН. ТиСУ. 2018. № 3. С. 116–127.
  9. Хьюз К., Хьюз Т. Параллельное и распределенное программирование с использованием С++. М.: Вильямс, 2004. 667 с.
  10. Cesarini F., Thompson S. ERLANG Programming: a Concurrent Approach to Software Development. Sebastopol, California, O’Reilly Media, 2009. 496 p.
  11. Кутепов В.П., Шамаль П.Н. Реализация языка функционального параллельного программирования FPTL на многоядерных компьютерах // Изв. РАН. ТиСУ. № 3. С. 46–60.
  12. Кутепов В.П., Зубов М.И. Реализация и экспериментальное исследование эффективности упреждающего параллелизма // Вестн. МЭИ. 2019. № 4. C. 119–126.
  13. Кутепов В.П., Ефанов А.А. Параллельные процессы и программы: модели, языки, реализация на системах // Программные продукты и системы. 2020. Т. 33. № 3. С. 375–384.
  14. Кутепов В.П. Интеллектуальное управление процессами и загруженностью в вычислительных системах // Изв. РАН. ТиСУ. 2007. № 5. С. 58–73.
  15. Бражникова Ю.Н., Горицкий Ю.А., Кутепов В.П., Панков Н.А. Исследование методов прогнозирования загруженности компьютеров и компьютерных систем // Программные продукты и системы. 2015. № 2. С. 135–146.
  16. Кутепов В.П., Фальк В.Н. Алгоритмические параллельные процессы и их сложность // Вестн. МЭИ. 2020. № 3. С. 102–110.
  17. Apt K. Formal Justification of a Proof System for Communicating Sequential Process // J. ACM. 1983. V. 30. № 1. P. 197–216.
  18. Pnueli A. Temporal Logic of Programs // Proc. 18-th IEEE Sympos. of Foundation of Computer Science. Tel Aviv, Israel, 1977. P. 46–57.
  19. Lamport L. The Temporal Logic of Actions // ACM Transactions on Programming Languages. 1993. V. 7. № 3. P. 1–52.
  20. Stanford Encyclopedia of Philosophy. Temporal Logic. 2019. Р. 1–17. https://plato.stanford.edu/entries/logic-temporal/
  21. Allen J.F. Maintaining Knowledge About Temporal Intervals // Communications of ACM. 2010. V. 26. № 11. P. 832–843.
  22. Orgun M., Wadge W. Theory and Practice of Temporal Logic Programming // J. Logic Programming. 1992. V. 13. P. 413–440.
  23. Buchi J.R. On a Decision Method in Restricted Second Order Arithmetic // Proc. Intern. Congr. Logic, Method and Philos., Sci. Stanford University, 1960. P. 1–12.
  24. Vardi M.Y., Wolper P. Reasoning About Infinite Computations // Information and Computation. 1994. V. 115. № 1. P. 1–37.
  25. Finger M., Gabbay Dov. Adding a Temporal Dimension to a Logic System // J. Logic, Language and Information. 1992. V. 1. P. 203–233.
  26. Gabbay P., Pnueli A., Shelah S., Stavi J. On the Temporal Analysis of Fairness // The ACM Sympos. on Principles of Programming Languages. Las Vegas, 1980. P. 163–173.
  27. Клини С. Введение в метаматематику. М.: Из-во иностр. лит., 1957. 520 c.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
2. Рис. 1. Временная диаграмма абсолютно параллельного вычисления значения функции 𝐹(X).

Скачать (65KB)
3. Рис. 2. Трасса выполнения процесса.

Скачать (68KB)
4. Рис. 3. Все трассы выполнения процесса  X10*(p1→a1)*X11.

Скачать (95KB)

© Российская академия наук, 2025