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

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

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

    Если когда-нибудь вы задумывались над тем, что значат слова «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. Да-да, ваш новейший Интел Кор Ай Семь работает именно так, как описано в этой статье двадцатипятилетней давности. Добро пожаловать в восьмидесятые!
    Поделиться публикацией
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 25
    • НЛО прилетело и опубликовало эту надпись здесь
      • +18
        гораздо хуже когда читаешь отличную статью, хочешь плюсануть карму — а не можешь, так как уже давно плюсанул
        • 0
          Да, есть такое дело.
          А статья реально интересная, моё уважение и благодарности автору!
        • 0
          Еще тоскливее то, что в области RISC до сих пор все трансляторы на уровне 50тых — тупо трансляторы.
          Даже тупо расчитать оптимальный JMP => SJMP/AJMP/LJMP в случае прямого прыжка не могут :D
          • +1
            Вы это про «трансляцию» ассемблера?
            Сишный код нынешние компиляторы замечательно оптимизируют, порой смотришь на листинги и узнаешь много новых способов использования инструкций проца)
            • +1
              «компиляторы» это вы о icc/gcc?
              контроллерные компиляторы сишные на том же уровне отставания, что и трансляторы асма…
              • 0
                Безосновательное заявление, сравните что ли результат работы того же gcc при -O0 и -O2 для ARMовских архитектур. Для x86 понятное дело оптимизаторы работают лучше, но там и спрос другой.
                • +1
                  я говорю про микроконтроллеры. avr, 8051, pic.
                  Посмотрите на «оптимизаторы» для них.

                  Я же говорю — «большая тройка»(gcc/llvm/iar) для «жирных» SoC — хорошо работает.
                  А вот для всего по-мельче — до сих пор прошлый век.
                  • 0
                    Как-то странно у вас в микроконтроллеры попали только AVR, 8051 и PIC, а все остальное вы записали уже в «жирные» SoC.
                    А как же микроконтроллеры таких популярных ARM ядрах как ARM7TDMI, CORTEX M3, CORTEX M0?
                    Или для вас какой-нибудь LPC1114 это уже не микроконтроллер, а SoC?
                    Сейчас ARM глубоко проник в нишу мелких микроконтроллеров и принес за собой туда нормальные компиляторы.
                    • +4
                      ARM — это жирный контроллер. Очень жирный. Простите, но когда вам доступна 32битная адресация, 32битная арифметика, когда даже в Cortex-M0 уже есть 13 регистров общего назначения все-со-всеми, это уже далеко не RISC по возможностям, и да, он очень жЫрен.
                      Да и блин, когда у слабенького контроллера до 50 мегагерц рабочая частота…
                      То там оптимизации дааалеко не всегда нужны, кроме сложной математики.

                      Зато да, в таких ресурсах автоматическая оптимизация делается уже хорошо.
                      А теперь когда операции доступны только с одним регистром, стека почти нет, свободных ресурсов вообще — то есть когда оптимизатор нужен как воздух…
                    • 0
                      Да, насчет 51 согласен. В свое время отказались от него по той причине, что писать нужно было на ассемблере исключительно. Сишный код раздувало нереально. Но сейчас они почти не используются.
                      На pic коллега как-то переводил программу с ассемблера на си, не сказал бы, что она стала сильно больше места занимать или медленнее работать.

                      PS что называть микроконтроллер, а что SoC — отдельная тема. На электрониксе была как-то дискуссия — сошлись на том, что SoC — скорее маркетинговый термин, чем технический.
                      • 0
                        мик/сок — согласен, холивар, для себя я соком зову «жирные», с высокой производительностью, а миками как раз 51/pic/avr — то есть дохлятинку.

                        ну и по поводу 51го — мы всё на нем делаем (исторически сложилось) — их хватает за глаза и за уши. а вот отсутствие компиляторов… и все доступные трансляторы с асма — тоже тупее пробки. и это обидно.
                      • 0
                        Не знаю как под AVR, но вот например под MSP430 gcc отлично компиляет. Я использовал gcc 4.7. И оптимизирует он весьма неплохо.
              • +1
                Отличная статья. Язык изложения четкий и последовательный, легко для понимания. Пишите еще, автор! По этой теме же есть еще много чего сказать. Например: возможность выполнить уже выбранные и декодированные команды без ущерба для времени реакции на прерывание; delay slots и иже с ними.
                • +5
                  Отличная статья… Наверное все таки не хватает простыней на verilog и километров временных диаграмм для особо интересующихся…
                  • 0
                    Отличная статья, спасибо!
                    Если я правильно понимаю, то в ARM PC равен ССК, и как такового АСК нет в принципе.
                    • +2
                      АРМы бывают разные. Например, когда случается исключение в Cortex-M4, в регистр адреса возврата сохраняется адрес, который в конце обработчика нужно вручную уменьшить на 8 и записать в PC, если требуется повторить команду, и на 4, если команду повторять не нужно. То есть вполне возможно, что в явном виде АСК там нет. При этом точные прерывания этот процессор поддерживает (да даже ARM7TDMI поддерживает — например, к нему можно прикрутить внешний MMU).

                      Интереснее было бы посмотреть на реализацию прерываний в Cortex-R или Cortex-A. Минимальная длина конвейера в этих процессорах — восемь стадий, в отличие от трехстадийных Cortex-M, и я не очень представляю, как они могли бы работать без АСК.
                      • 0
                        Я думаю, что для абстрагирования от длины конвейера(и для программной совместимости) в ARM всегда присуствует только 2 «зафиксированных» шага перед точкой выполнения инструкции.
                        Но было бы интересно услышать мнение эксперта.
                    • +2
                      В своё врем удивило, как на процессорах типа TI C6000 (которые конвеерные, и могут выполнять, например, четыре команды одновременно) выполняется обработка прерываний. Так как сохранить состояние процессора (когда каждая из выполняемых команд находится в «промежуточном» состоянии) мягко говоря, сложно — то используется такой трюк. Все циклы, которые должны выполнятся в конвейере — выполняются с запрещёнными прерываниями. Но что делать, если цикл будет слишком долгий? Значит, все какие циклы будут разбиты на двойные циклы — снаружи с последовательностью: запретили прерывания, выполнили конвейеризованный код, разрешили прерывания, а внутри — всё быстро и оптимизированно.

                      Этот подход поддерживается самим компилятором C/C++ — у него есть отдельный параметр командной строки, «сколько тактов он имеет право работать на запрещённых прерываниях».
                      • 0
                        Циклы, в общем, ни при чём — просто в них чаще используется конвейерная оптимизация. Оно и понятно: линейный код всё равно в кэш не попадает, его приходится читать по мере выполнения, и запихивать 8 команд в один такт большого смысла нет. А так, зависит от программиста, какой код писать — устойчивый к прерываниям, или нет. Принцип устойчивого кода — нельзя использовать старое значение регистра, если в конвейере уже выполняется команда, которая через какое-то время поменяет его значение (например, загрузка из памяти).
                      • +2
                        Если у вас сохранилась полная верисия статьи с километрами кода на верилоге, опубликуйте пожалуйста.
                        • +2
                          В этом вся проблема — она не готова, и я не уверен, что соберусь ее закончить. По крайней мере, не в формате статьи для Хабра точно.
                        • +3
                          По теме внутреннего устройства процессоров есть хорошая книга «Computer Architecture, Fifth Edition: A Quantitative Approach (The Morgan Kaufmann Series in Computer Architecture and Design) (5th Edition), 2011».
                          Был еще курс на coursera, который читал David Wentzlaff из принстона но сейчас его оттуда почему-то убрали.
                          • +2
                            На эту книжку у меня в статье ссылка, между прочим. А курс на Coursera был достойный, подтверждаю. Лично я сохранил его себе на память :)
                            • +1
                              А можно попросить у Вас этот курс? :)

                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.