Конечные автоматы: мозг устройства управления

Урок вводит конечный автомат — модель, по которой работает устройство управления процессора.

Конечный автомат (FSM) — система с конечным набором состояний, которая по входным сигналам переходит из состояния в состояние и выдаёт выходы. В железе текущее состояние хранится в регистре, переходы вычисляет комбинационная логика.

Зачем автоматы в процессоре

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

Анатомия автомата

  входы ──→┌──────────────┐
           │ логика        │──→ следующее состояние
   тек.    │ переходов     │
 состояние→└──────────────┘
     ↑                         ┌──────────┐
     └─────────────────────────┤ регистр  │←── такт
                               │ состояния│
                               └──────────┘
            │ логика выходов │──→ выходные сигналы

  Состояние = "память" автомата (где мы сейчас)
  Переходы  = комбинационная логика (куда идти дальше)

Как работает под капотом: автомат светофора

Классический пример — светофор: состояния «зелёный → жёлтый → красный → зелёный...». Это маленький FSM. Смоделируем его, чтобы увидеть, как состояние + такт порождают поведение во времени:

# таблица переходов: состояние -> (следующее, выходной сигнал)
transitions = {
    "GREEN":  ("YELLOW", "ехать"),
    "YELLOW": ("RED",    "внимание"),
    "RED":    ("GREEN",  "стоп"),
}

state = "GREEN"
print("такт | состояние | сигнал | следующее")
for t in range(6):
    nxt, signal = transitions[state]
    print(f"  {t}  | {state:<7}   | {signal:<8} | {nxt}")
    state = nxt

Вывод:

такт | состояние | сигнал | следующее
  0  | GREEN     | ехать    | YELLOW
  1  | YELLOW    | внимание | RED
  2  | RED       | стоп     | GREEN
  3  | GREEN     | ехать    | YELLOW
  4  | YELLOW    | внимание | RED
  5  | RED       | стоп     | GREEN

Автомат, реагирующий на вход

Настоящий FSM меняет переходы в зависимости от входов. Сделаем распознаватель: автомат, который ловит подпоследовательность «два разреза подряд» — выдаёт сигнал, когда видит две единицы кряду:

def run_fsm(bits):
    state = "S0"           # S0: видели 0 единиц; S1: видели одну
    outputs = []
    for b in bits:
        out = 0
        if state == "S0":
            state = "S1" if b == 1 else "S0"
        elif state == "S1":
            if b == 1:
                out = 1            # две единицы подряд!
                state = "S1"
            else:
                state = "S0"
        outputs.append(out)
    return outputs

seq = [1, 0, 1, 1, 1, 0, 1, 1]
print("вход: ", seq)
print("выход:", run_fsm(seq))

Вывод:

вход:  [1, 0, 1, 1, 1, 0, 1, 1]
выход: [0, 0, 0, 1, 1, 0, 0, 1]

Мили и Мур

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

Глубже в тему

Чтобы прочувствовать конечный автомат, полезно увидеть, из чего он физически собран. У любого FSM ровно три части: регистр состояния (это «память» автомата — те самые триггеры из прошлых уроков, хранящие, где мы сейчас), комбинационная логика переходов (она по текущему состоянию и входам вычисляет следующее состояние) и логика выходов (она формирует выходные сигналы). По фронту такта регистр защёлкивает вычисленное «следующее состояние», и цикл повторяется. То есть FSM — это не какая-то отдельная экзотическая схема, а аккуратная сборка уже знакомого: регистр плюс комбинационная логика, замкнутые в петлю обратной связью через тактирование.

Слово «конечный» в названии не случайно и важно: число состояний строго ограничено, потому что их хранит регистр фиксированной разрядности. Регистр из n триггеров может закодировать не более 2 в степени n состояний. Это и сила, и предел модели: FSM прекрасно описывает управляющие последовательности и протоколы, но в чистом виде не может, например, считать неограниченно или помнить произвольно длинную историю — для этого нужна внешняя память (так из автомата с памятью-лентой получается уже модель машины Тьюринга). Для устройства управления процессора конечности более чем достаточно: число шагов исполнения команды заведомо ограничено.

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

И главная связь со всем курсом: исполнение машинной команды — это последовательность шагов «выбрать → расшифровать → исполнить → записать», и кто-то должен помнить, на каком шаге мы сейчас, и по такту переходить к следующему. Эту роль и играет устройство управления (control unit), которое по своей сути есть большой конечный автомат. Его состояния — это фазы цикла команды, входы — код операции и флаги АЛУ, а выходы — те самые управляющие сигналы, что открывают регистры, задают операцию АЛУ и разрешают запись. Когда в разделе про цикл выборки-декодирования-исполнения мы будем разбирать его по фазам, держите в уме: за сменой фаз стоит ровно такой автомат. Не забывайте и про сигнал сброса: без определённого начального состояния FSM стартует непредсказуемо, поэтому у реального устройства управления всегда есть вход reset, приводящий его в известную стартовую точку.

Частые ошибки

Забывать про начальное состояние. FSM без определённого старта ведёт себя непредсказуемо (нужен сигнал сброса).
Делать слишком много состояний. Лишние состояния = больше триггеров и логики; их минимизируют.
Путать Мили и Мура. Мур: выход от состояния; Мили: выход от состояния и входа.

Итог

FSM = конечный набор состояний + переходы по входам; состояние хранится в регистре.
Устройство управления процессора — это большой конечный автомат.
Типы: Мур (выход от состояния) и Мили (выход от состояния и входа).