Терминальное состояние в вычислительных системах¶
Терминальное состояние — состояние вычислительной системы, процесса или объекта, в котором завершены все выполняемые операции и дальнейшая обработка данных не предполагается. Термин применяется в информатике, теории автоматов, теории вероятностей, логике программирования и смежных дисциплинах. В зависимости от контекста терминальным называют состояние, из которого система не может перейти в другое состояние (в теории автоматов), состояние, в котором процесс завершает выполнение (в операционных системах), или состояние, достигаемое в конце определённой последовательности шагов (в формальных методах верификации).
¶Терминальные состояния в теории автоматов
В теории автоматов и формальных языков терминальное состояние (конечное состояние) — состояние конечного автомата, из которого переходы не определены. Автомат, остановившийся в таком состоянии, считается принявшим (или не принявшим) входную строку в зависимости от того, является ли это состояние финальным (принимающим). Терминальные состояния играют ключевую роль при определении языков, распознаваемых автоматами: множество финальных состояний задаёт множество строк, которые автомат принимает.
Для недетерминированных автоматов (НКА) терминальное состояние имеет дополнительное значение: если хотя бы одна из ветвей недетерминированного вычисления приводит в финальное состояние, строка считается принятой. При детерминизации НКА в ДКА терминальные состояния нового автомата формируются как объединения подмножеств состояний исходного НКА, и строка принимается, если хотя бы одно из входящих в подмножество состояний было финальным.
¶Терминальные состояния в теории вероятностей и марковских цепях
В теории вероятностей и теории марковских цепей терминальное состояние (поглощающее состояние) — состояние, из которого невозможно выйти: вероятность перехода из него в любое другое состояние равна нулю, а вероятность остаться в нём — единице. Марковская цепь, имеющая хотя бы одно поглощающее состояние, называется поглощающей цепью.
Ключевое свойство поглощающих цепей: из любого начального состояния, достижимого до попадания в поглощающее, рано или поздно цепь обязательно попадёт в одно из терминальных состояний с вероятностью, равной единице. Распределение вероятностей того, в какое именно терминальное состояние попадёт цепь, вычисляется через фундаментальную матрицу, описывающую среднее время пребывания в непоглощающих состояниях. Метод применяется при моделировании случайных блужданий, игр, процессов отказов и восстановления технических систем.
¶Терминальные состояния в логике программирования
В логике программирования и семантике программ терминальным называется состояние выполнения программы, в котором программа завершила свою работу — все операторы отработали, управление не передаётся дальше. Семантика оператора while (цикл с предусловием) определяется через терминальные состояния: тело цикла выполняется до тех пор, пока предусловие истинно, и цикл завершается ровно тогда, когда предусловие впервые становится ложным, переводя систему в терминальное состояние.
При верификации программ терминальные состояния используются для доказательства корректности: программа считается корректной относительно спецификации, если из любого начального состояния, удовлетворяющего предусловию, выполнение программы приводит к терминальному состоянию, удовлетворяющему постусловию. Методы доказательства завершаемости программ (well-founded ordering, лексикографические порядки) направлены на то, чтобы показать: любая последовательность выполнения программы неизбежно достигает терминального состояния.
¶Терминальные состояния в операционных системах
В операционных системах терминальным называется состояние процесса, в котором процесс завершил выполнение и ожидает, пока ресурсы (таблица страниц, дескрипторы файлов, память) будут освобождены родительским процессом или системой. Стандартная модель жизненного цикла процесса включает состояния: создание, готовность, выполнение, ожидание, завершение. Терминальное состояние — финальное: из него процесс не может быть переведён в другое состояние.
В UNIX-подобных системах терминальное состояние процесса связано с механизмом «зомби»: завершившийся процесс остаётся в таблице процессов до тех пор, пока родитель не вызовет wait() и не прочитает код завершения. Если родитель завершается раньше, процесс переходит к процессу-инициализатору (init или systemd), который выполняет очистку.
¶Терминальные состояния в теории игр и экономике
В теории игр терминальным называется состояние игрового дерева, в котором партия завершена и определён выигрыш участников. Терминальные узлы дерева несут числовые метки — выплаты игрокам. Алгоритмы минимакс и альфа-бета отсечение работают путём рекурсивного обхода дерева до терминальных узлов и обратного распространения значений выплат.
В экономике и теории принятия решений терминальным называют состояние системы, в котором все агенты достигли равновесия и не имеют стимулов к изменению своего поведения. Такие состояния моделируются как терминальные узлы в деревьях решений.
¶Применение
Терминальные состояния используются при формальной верификации аппаратных и программных систем, моделировании случайных процессов, проектировании протоколов, анализе алгоритмов и синтезе автоматов. Понятие лежит в основе определений детерминированности, завершаемости и корректности в информатике.
Источники:
- Гинзбург С. «Алгебраические теории автоматов»
- Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ»
- Сипсер М. «Введение в теорию вычислений»
- Попов В. Н. «Конечные автоматы»
- Клейни Г. «Автоматы и формальные языки»
