Кольцевой буфер
В разделе «Прерывания» мы уже встретились с основным свойством обработчика прерываний: обрабатывать надо быстро. Поэтому вся логика обработки должна находится в пользовательской программе, а обработчику, скажем, клавиатурного прерывания остаётся только перекладывать из регистра ввода куда-нибудь.
С другой стороны, приведённый там пример обработчика мало чем отличается от традиционного поллинга — та же проверка, был ли ввод или не было, только вместо регистра готовности опрашиваем ячейку памяти. Если делать это слишком редко, легко пропустить очередной ввод, а если слишком часто — потратить время на опрос вместо полезных действий.
Итак, главная проблема — синхронность побайтового ввода и обработки прерываний. И задача в том, чтобы обеспечить рассинхронизацию ввода и вывода: прерывание обрабатывается, когда оно происходит, а программа вводит свои байты, когда может.
Разумеется, для этого надо хранить не один обработанный, но ещё не запрошенный программой байт, а несколько. Эффективная структура, решающая такую задачу — кольцевой буфер.
Кольцевой буфер — массив (реже — список) данных, предназначенный для временного хранения асинхронно поступающих и асинхронно отбывающих данных.
- Буфер имеет фиксированный размер
- «Поверхность» буфера (HI) — адрес первой свободной ячейки буфера
- Когда поступят новые данные, они будут записаны в эту ячейку, а HI передвинется на следующую
- «Дно» буфера (LO) — адрес последней занятой ячейки буфера
- Когда понадобится забрать очередной элемент данных, его возьмут из этой ячейки, а LO передвинется на следующую
Размер буфера не является ограничением: когда HI подберётся к концу, в начале уже образуются свободные места и HI при очередном сдвиге начнёт указывать в начало
Аналогично произойдёт и с LO.
Вполне возможна ситуация, когда данных больше не прибыло, а программа требует ещё ввода. Эта ситуация называется исчерпанием буфера и распознаётся по тому, что HI и LO содержат один и тот же адрес:
Вариантов обработки исчерпания два:
- Заданным образом уведомить программу, что данных ещё нет (например, вернуть специальное служебное значение)
Это называется неблокирующим вводом
- Задержать операцию снятия данных до тех пор, пока они не появятся
Это называется блокирующим вводом
- Продолжить скакать по уже введённым когда-то данным, как если бы исчерпания не было
это называется грубой ошибкой алгоритма!
Заметим, что в момент создания кольцевой буфер находится в состоянии исчерпания (HI и LO указывают на нулевой элемент)
Другая ситуация — переполнение буфера: данные всё прибывают, а забирать их никто не хочет. Переполнение кольцевого буфера распознаётся по тому, что LO содержит адрес ячейки, следующей за HI (в кольце):
Вариантов обработки переполнения 2 (два других — плохие, негодные):
- Продолжать вводить, но не увеличивать HI. При этом все прибывшие после переполнения данные, кроме последнего элемента, исчезают.
Если источник данных позволяет, можно заранее уведомить его о переполнении — может, он приостановит передачу на время.
- Правда, для этого надо усложнить алгоритм работы, введя «верхний урез» поверхности буфера, при котором устройство уведомляется о приближающемся переполнении, и «нижний урез», при котором оно уведомляется о том, что переполнение больше не грозит.
- Выбрасывать все вновь прибывающие данные, пока для них нет места в буфере.
- См. примечания выше
- Продолжать как ни в чём ни бывало вводить и увеличивать HI.
При этом внезапно™ возникает ситуация исчерпания и пропадает всё содержимое буфера
- Задерживать ввод до тех пор, пока свободное место в буфере не появится.
Если обрабатывать таким образом прерывание ввода, то возникнет т. н. взаимоблокировка (deadlock): пока мы не вышли из прерывания, программа не может забрать данные из буфера, а пока программа не забрала данные из буфера, мы сидим в прерывании и ждём
⇒ никаких ожиданий в обработчике прерываний! Нет — значит, нет.