Состояние (информатика)

В информатике и теории автоматов состояние цифровой логической схемы или компьютерной программы является техническим термином для всей хранимой информации, к которой схема или программа в данный момент времени имеет доступ^[1]. Выходные данные цифровой схемы или компьютерной программы в любой момент времени полностью определяются её текущими входными данными и её состоянием.

Состояние цифровой логической схемы

Цифровые логические схемы могут быть разделены на два типа: комбинационной логики, чьи выходные сигналы зависят только от входных сигналов, и секвенциальной (последовательной) логики, чьи выходные данные являются функцией и от текущих, и от входных данных, поступавших на вход в прошлом^[2].

В секвенциальной логике информация, поступившая ранее на входы сохраняется в памяти электронных элементов, таких как триггеры, ячейки памяти. Сохраненные содержимое этих элементов памяти, в данный момент времени, в совокупности именуемое «состояние» схемы содержит всю информацию о прошлом, к которому устройство имеет доступ^[3].

Например, текущее состояние микропроцессора (компьютерной микросхемы) определяется содержимым всех его элементов памяти: аккумуляторов, регистров хранения, кэшей данных и флагов.

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

Аналогично сохраняется состояние процессора при обработке внешних прерываний программы внешними событиями, которые могут происходить в непредвиденные моменты времени. Для того, чтобы после завершения обработки прерывания прерванная текущая программа корректно возобновила свою работу, необходимо сохранение состояния тех регистров и памяти, которые используются обработчиком прерывания. Перед передачей управления прерванной программе, обработчик прерывания восстанавливает состояние регистров процессора и памяти и передает управление прерванной программе. Сохранение и восстановление состояния выполняет обработчик внешних прерываний.

Поскольку каждый двоичный элемент памяти, такой как триггер, или двоичный разряд регистра имеет только два возможных состояния — «логической единицы» или «логического нуля», и существует конечное число таких двоичных элементов памяти, всякая цифровая схема имеет конечное число возможных состояний. Если количество двоичных элементов памяти в схеме равно N, то максимально возможное количество состояний будет 2^N.

Состояние программы

Компьютерные программы хранят данные в переменных, представляющих собой области хранения данных в памяти компьютера, содержание этих областей памяти в любой момент времени исполнения программы называется состоянием программы^[4]^[5]^[6].

Императивное программирование — парадигма программирования (способ проектирования языка программирования), которая описывает в терминах состояний и операторов, которые изменяют состояние программы. В декларативных языках программирования, напротив, программа описывает желаемый результат, не указывая изменения состояний напрямую. Более специализированное определение состояния используется в некоторых компьютерных программах, которые работают последовательно с потоками данных, таких как синтаксические анализаторы, файрволы, протоколы передачи данных и программ шифрования. Последовательные программы обрабатывают поступающие данные, символы или пакеты, последовательно, по одному за раз. В некоторых из этих программ, информация о предыдущих полученных символах или пакетах данных, хранится в переменных и используется, чтобы повлиять на обработку текущего символа или пакета. Это называется «протоколом состояния», и данные, перенесенные из предыдущего цикла обработки называется «состоянием». В других случаях, программа не имеет никакой информации о предыдущем потоке данных и начинает «чистый» с каждого ввода данных; это называется «протокол без состояния».

Конечные автоматы

Выходная последовательная цепь или компьютерная программа в каждый момент времени полностью определена текущими входными данными и текущим состоянием. Поскольку каждый бинарный элемент памяти имеет только два возможных состояния, 0 или 1, общее количество состояний сети предполагается конечным и фиксированным по числу элементов памяти. Если количество двоичных элементов памяти в схеме — N, то максимально возможное количество состояний будет 2^N. Понятие состояния, оформленное в абстрактной математической модели вычислений, называется конечным автоматом, используемым для разработки как последовательные цифровые схемы так и компьютерных программ.

Типы состояний

Различают следующие типы состояний:

Совместимые состояния — это такие состояния в конечных автоматах, которые не противоречат никакими входным значениям. Таким образом, для каждого входного значения оба состояния должны иметь одинаковые значения на выходе, и оба состояния должны иметь одинакового наследника (либо, неопределенного), или оба должны остаться неизменными. Совместимые состояния являются избыточными, если имеют место в одном автомате.
Различимые состояния — это состояния в конечных автоматах, имеющие как минимум одну входную последовательность, вызывающую отличную от остальных выходную — независимо от того, какое состояние являлось начальным.
Эквивалентные состояния — это состояния в конечных автоматах, которые для каждой возможной входной последовательности будут производиться одинаковые — независимо от того, какое состояние является начальным.