Прерывания в конвейеризированных процессорах

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

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

Если когда-нибудь вы задумывались над тем, что значат слова «the processor supports precise aborts» в даташите, прошу под кат.

Немного терминологии: процессор, процессы и прерывания

Чтобы не пытаться объять необъятное, я не буду рассматривать:

• Процессоры с экзотическими архитектурами (стековыми, потоковыми, асинхронными и так далее), потому что их доля на рынке весьма мала, а в качестве примера логичнее использовать распространенную архитектуру. RISC я выбрал исключительно по религиозным соображениям
• Многоядерные процессоры, потому что каждое процессорное ядро обрабатывает свои прерывания независимо от других ядер
• Суперскалярные, многопоточные и VLIW процессоры, потому что с точки зрения организации прерываний они похожи на скалярные процессоры (хотя, разумеется, гораздо сложнее).

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

Итак, процессор — это устройство, выполняющее последовательность команд (программу) для решения некоторой задачи. Для каждой команды, в свою очередь, процессор должен выполнить последовательность операций, называемую циклом команды (instruction cycle) и состоящую из следующих этапов:

1. Выборка команды из памяти
2. Декодирование команды
3. Исполнение команды
4. Запись результатов в регистры и/или память

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

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

Процесс — это выполняющаяся программа. Процесс должен давать одинаковые результаты вне зависимости от того, выполняется ли он на процессоре с последовательным или параллельным выполнением команд. Состояние процесса определяется содержимым:

• счетчика команд процессора (program counter, он же instruction pointer)
• регистров процессора (общего назначения, статусных, флагов и так далее)
• оперативной памяти

В системах реального времени необходимо также учитывать влияние кэш-памяти, буферов ассоциативной трансляции MMU (translation lookaside buffer, TLB) и таблиц динамического предсказания переходов.

Каждая выполненная команда каким-то образом обновляет состояние процесса:

• арифметические и логические команды обновляют содержимое регистров и счетчика команд
• команды перехода обновляют содержимое счетчика команд и таблицы динамического предсказания переходов
• команды загрузки обновляют содержимое регистров, счетчика команд и кэш-памяти (при промахе кэша; если потребуется замещение линии кэша — то еще и оперативной памяти)
• команды сохранения обновляют содержимое оперативной памяти (или кэш-памяти) и счетчика команд

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

В зависимости от источника прерывания оно может быть:

1. Внутренним, если вызвано выполнением команды в процессоре:
   
   • Программным (software interrupt), если вызвано специальной командой
   • Исключением (exception, fault, abort – это все оно), если вызвано ошибкой при выполнении команды

2. Внешним, если вызвано произошедшим снаружи процессора событием

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

Сохранение и восстановление состояния процесса может быть реализовано аппаратно, программно или программно-аппаратно. В дальнейшем я буду рассматривать простейший программно-аппаратный вариант, при котором:

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

После возврата управления прерванному процессу он должен иметь возможность продолжить работу так, как будто его и не прерывали. Это требование тривиально, однако для большинства современных процессоров его довольно сложно выполнить. Настолько сложно, что иногда от него отказываются. Прерывания, которые гарантируют выполнение этого требования, называют точными (precise), а прочие — неточными (imprecise).

Точные и неточные прерывания

Формально прерывание называется точным, если выполнены все перечисленные ниже условия:

1. все команды, предшествующие прерываемой, были полностью выполнены и корректно сохранили состояние процесса
2. все команды, следующие за прерываемой, не были выполнены и ни коим образом не изменили состояние процесса
3. прерываемая команда, в зависимости от типа прерывания, либо была полностью выполнена, либо не была выполнена вовсе

Первые два условия точности не нуждаются в комментариях. Третье условие обусловлено следующим:

• Команда, выполнявшаяся в момент прихода внешнего прерывания, должна обновить состояние процесса перед тем, как оно будет сохранено. То же самое касается команды, вызвавшей программное прерывание. В обоих случаях РАВ будет указывать на команду, которая, не случись прерывания, должна была быть выполнена следующей. Она и будет выполнена сразу после возврата из обработчика прерывания
• Команда, вызвавшая исключение — «плохая» команда. Ее результаты, скорее всего, некорректны, поэтому она не должна обновлять состояние процесса. Вместо этого в РАВ сохраняется ее адрес, после чего вызывается обработчик прерывания, который попытается исправить ошибку. После возврата из обработчика эта команда будет выполнена повторно. Если она снова вызовет такое же исключение, значит ошибка неисправима и процессор сгенерирует фатальное прерывание

Очевидно, что внешние прерывания должны быть точными всегда. Кому нужен процессор, который не может корректно восстановить процесс после обработки прерывания от таймера?

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

В микроконтроллерах исключения могут быть неточными. Например, если команда сохранения вызвала исключение из-за ошибки памяти, то вместо того, чтобы пытаться как-то исправить ошибку и повторно выполнить эту команду, можно просто перезагрузить микроконтроллер и начать выполнять программу заново (то есть сделать то же самое, что делает сторожевой таймер, когда программа зависла).

В большинстве учебников по архитектуре компьютеров (включая классику типа Patterson&Hennessy и Hennessy&Patterson) точные прерывания обходятся стороной. Кроме того, неточные прерывания не представляют никакого интереса. По-моему, это отличные причины продолжить рассказ именно про точные прерывания.

Точные прерывания в процессорах с последовательным выполнением команд

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

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

Место, где процессор должен определить, позволить ли команде обновить состояние процесса или нет, называется точкой фиксации результатов (commit point). Если процессор сохраняет результаты команды, то есть команда не вызвала исключение, то говорят, что эта команда зафиксирована (на сленге — закоммичена).

Чтобы понять, где же должна быть расположена точка фиксации результатов, полезно вспомнить этапы цикла команды:

1. Выборка команды из памяти
2. Декодирование команды
3. Исполнение команды
4. Запись результатов в регистры и/или память

По определению, она должна находиться до записи результатов, но к этому моменту уже должно быть известно, вызвала команда исключение или нет. Исключение может произойти на любом из четырех этапов, например:

1. ошибка памяти при выборке команды
2. неизвестный код операции при декодировании
3. деление на ноль при исполнении
4. ошибка памяти при записи результатов

Очевидно, что реализация точных прерываний невозможна до тех пор, пока не решена проблема записи результатов в память:

• нельзя фиксировать команду и разрешать ей записывать результаты в память до тех пор, пока не станет ясно, что команда не вызвала исключение
• нельзя узнать, что исключение не вызвано, не записав результаты в память (для этого нужно получить подтверждение от контроллера памяти, что запись произведена успешно)

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

Точные прерывания в процессорах с параллельным выполнением команд

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

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

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

Для этого результаты каждого этапа, кроме последнего, сохраняются во вспомогательных элементах памяти (регистрах), расположенных между этапами:

1. Результат выборки — закодированная команда — сохраняется в регистре, расположенном между этапами выборки и декодирования
2. Результат декодирования — тип операции, значения операндов, адрес результата — сохраняются в регистрах между этапами декодирования и исполнения
3. Результаты исполнения — новое значение счетчика команд для условного перехода, вычисленный в АЛУ результат арифметической операции и так далее — сохраняются в регистрах между этапами исполнения и записи результатов
4. На последнем этапе результаты и так записываются в регистры и/или память, поэтому никакие вспомогательные регистры не нужны.

Вот так работает получившийся конвейер:

 Такт  СК    Выборка   Декодирование   Исполнение   Запись_результатов 1     0x00  Команда1  -               -            - 2     0x04  Команда2  Команда1        -            - 3     0x08  Команда3  Команда2        Команда1     - 4     0x0C  Команда4  Команда3        Команда2     Команда1             5     0x10  Команда5  Команда4        Команда3     Команда2             

Обратите внимание на столбец СК («счетчик команд»). Его значение меняется каждый такт и определяет адрес в памяти, откуда выбирается команда.
Внимательный читатель уже заметил небольшую неувязочку — для обеспечения точности прерываний первая команда не имеет права изменить счетчик команд раньше четвертого такта. Чтобы это исправить, мы должны перенести счетчик команд за точку фиксации результата (предположим, что она находится между третьим и четвертым этапами):

 Такт  Выборка   Декодирование  Исполнение  Запись_результатов  СК 1     Команда1  -              -           -                   0х00 2     -         Команда1       -           -                   0х00 3     -         -              Команда1    -                   0х00 4     Команда2  -              -           Команда1            0х04 5     -         Команда2       -           -                   0х04 

Производительность процессора немного упала, не так ли? На самом деле, решение лежит на поверхности – нам нужно два счетчика команд! Один должен находиться в начале конвейера и указывать, откуда читать команды, второй – в конце, и указывать на ту команду, которая должна быть зафиксирована следующей.
Первый называется «спекулятивным», второй – «архитектурным». Чаще всего спекулятивный счетчик команд не существует сам по себе, а встроен в предсказатель переходов. Выглядит это вот так:

 Такт  ССК   Выборка   Декодирование  Исполнение  Запись_результатов  АСК 1     0x00  Команда1  -              -           -                   0х00 2     0x04  Команда2  Команда1       -           -                   0х00 3     0x08  Команда3  Команда2       Команда1    -                   0х00 4     0x0C  Команда4  Команда3       Команда2    Команда1            0х04 5     0x10  Команда5  Команда4       Команда3    Команда2            0х08 

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

• Если пришло внешнее прерывание, команда коммитится, но адрес следующей команды записывается не в АСК, а в РАВ. В АСК записывается адрес вектора прерывания.
• Если возникло исключение, команда не коммитится, вместо этого в АСК записывается адрес вектора соответсвующего исключения, а адрес команды записывается в РАВ.
• Если адрес команды не равен АСК, она тоже не коммитится (об этом позже). Если адрес равен АСК и исключения не произошло – процессор фиксирует команду и обновляет АСК (записывает адрес перехода в случае команды ветвления или просто инкрементирует в случае другой команды)

Почему ССК может быть не равен АСК? Возьмем мой любимый пример: процессор только что включили, и он выбирает первую команду из таблицы прерываний, которая является ни чем иным как командой перехода в далекую даль (по адресу 0х1234):

 Такт  ССК     Выборка      Декодирование  Исполнение   Запись_результатов  АСК 1     0x00    jump 0x1234  -              -            -                   0х00 2     0x04    Команда2     jump 0x1234    -            -                   0х00 3     0x08    Команда3     Команда2       jump 0x1234  -                   0х00 4     0x0C    Команда4     Команда3       Команда2     jump 0x1234         0х1234 *** Для Команды2 на четвертом такте ее адрес (0х04) не равен АСК, потому что переход был предсказан неверно*** 5     0x1234  Команда666   -              -            -                   0х1234 6     0x1238  Команда667   Команда666     -            -                   0х1234 7     0x1240  Команда668   Команда667     Команда666   -                   0х1234 8     0x1244  Команда669   Команда668     Команда667   Команда666          0х1238 

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

Желающим усугубить взрыв мозга рекомендую ознакомиться с Implementation of precise interrupts in pipelined processors. Да-да, ваш новейший Интел Кор Ай Семь работает именно так, как описано в этой статье двадцатипятилетней давности. Добро пожаловать в восьмидесятые!