Д. Кнут - Искусство программирования том 1 (1119450), страница 59
Текст из файла (страница 59)
2 и 3). Множественная буферизация. Свопинг — это только частный случай при Х = 2 общего метода для Х буферов. В некоторых задачах желательно иметь более двух буферов. Для примера рассмотрим следующий тип алгоритма. Шаг 1. Прочитать пять блоков один за другим. Шаг 2.
На основе этих данных выполнить достаточно трудоемкие вычисления. Шаг 3. Вернуться к шагу 1. В данном случае желательно иметь пять-шесть буферов, чтобы во время выполнения шага 2 можно было читать следующую порцию данных из пяти блоков. Благодаря этой тенденции передавать для В/В пакеты данных множественная буферизация получает большие преимущества по сравнению со свопингом.
Предположим, имеется Х буферов для некоторого процесса ввода или вывода, выполняющегося с помощью единственного устройства В/В. Будем представлять себе, что эти буфера расположены по кругу, как показано на рис. 23. Можно считать, что внешняя для процесса буферизации программа имеет следующий общий вид относительно нашего устройства В/В. НАЗНАЧИТЬ ОСВОБОДИТЬ НАЗНАЧИТЬ ОСВОБОДИТЬ Другими словами, можно считать, что в программе чередуются действие под названием НАЗНАЧИТЬ и действие под названием ОСВОБОДИТЬ, между которыми выполняются другие вычисления, не оказывающие влияния на распределение буферов.
НАЗНАЧИТЬ означает, что программа получает адрес следующей буферной области; этот адрес присваивается как значение некоторой переменной, использующейся в программе. ОСВОБОДИТЬ означает, что программа закончила работу с текущей буферной областью. Рис. 23. Кольцо буферов (Х = б). Между НАЗНАЧИТЬ и ОСВОБОДИТЬ программа работает с одним из буферов, который называется шекущеб буферной областью, а между ОСВОБОДИТЬ и НАЗНАЧИТЬ программа не обращается нн к одной буферной области. Понятно,что НАЗНАЧИТЬ может непосредственно следовать за ОСВОБОДИТЬ.
Рассмотрение вопросов буферизации часто основывалось на этом предположении. Но если ОСВОБОДИТЬ выполняется как можно быстрее, то процесс буферизации является более независимым и более эффективным. Разделяя эти две, по существу, разные функции, т. е. НАЗНАЧИТЬ и ОСВОБОДИТЬ, мы обнаружим, что метод буферизации остается легким для восприятия, а наше обсуждение — содержательным даже при Х = 1.
Для большей определенности давайте рассмотрим операции ввода и вывода по отдельности. Для операции ввода будем предполагать, что мы имеем дело с устрой- ством чтения перфокарт. Действие НАЗНАЧИТЬ означает, что программе нужна информация с новой перфокарты. Поэтому следует занести в индексный регистр адрес ячейки памяти, в которой находится образ следующей карты. Действие ОСВОБОДИТЬ выполняется, когда информация об образе текущей перфокарты больше ие нужна, так как она некоторым способом обработана программой (возможно, скопирована в другую часть памяти и т. д.).
Поэтому текущую буферную область теперь можно заполнить следующей порцией опережающего ввода. Для операции вывода рассмотрим АЦПУ. Действие НАЗНАЧИТЬ происходит, когда нужна свободная буферная область, в которую помещается образ строки для печати. Мы хотим занести в индексный регистр адрес ячейки памяти, с которой начинается такая область. Действие ОСВОБОДИТЬ происходит, когда этот образ строки полностью помещен в буферную область в виде, готовом для печати. Пример. Чтобы напечатать содержимое ячеек 0800 — 0823, можно записать следующее.
3ИР АЯЯТОИР (Занести в г15 адрес буфера.) ЕНТО О,б (5) ИОУЕ 800(24) Переместить 24 слова в выходной буфер. ЗИР НЕЬЕАЯЕР Здесь АЯЯТОНР и НЕЬЕАЯЕР— это подпрограммы, выполняющие две описанные функции буферизации для АЦПУ. В оптимальной ситуации с точки зрения компьютера для выполнения операции НАЗНАЧИТЬ времени практически не требуется. Для ввода это означает, что каждый образ перфокарты будет введен с опережением, так что данные уже имеются в наличии, когда программа готова их принять.
А для вывода это означает, что в памяти всегда будет свободное место для записи образа строки. В любом случае время на ожидание устройств В/В не тратится. Чтобы получше описать алгоритм буферизации и сделать его более красочным, будем говорить, что буферная область либо зеленая, либо желтая, либо красная (на рис.
24 они обозначены буквами 3, Ж и К). Зеленый цвет означает, что область готова для того, чтобы ее НАЗНАЧИЛИ, т. е. заполнена информацией с опережением (в случае ввода) либо является свободной (в случае вывода). Желтый цвеш означает, что область уже НАЗНАЧЕНА, но еще не СВОБОДНА, т. е.
это текущий буфер, с которым работает программа. Красный цвеш означает, что область уже СВОБОДНА, т. е. это свободная область (в случае ввода) или область, заполненная информацией (в случае вывода). На рис. 23 изображены два "указателя", направленных на обозначенные кружочками буферные области. Это, по сути, индексные регистры в программе. СЛЕДЯ и СЛЕДК расшифровываются как "следующий зеленый" и "следующий красный" буфер соответственно. Третий указатель, ТЕКУЩИЙ (рис. 24), указывает на желтый буфер, если он есть.
Приведенные ниже алгоритмы можно с одинаковым успехом применять как для ввода, так и для вывода, но для определенности сначала рассмотрим случай ввода с устройства чтения перфокарт. Предположим, что программа достигла состояния, показанного на рис. 23. Это означает, что четыре образа перфокарт были введены (а) (с) (Ь) Рис, 24. Состояния буферов: (а) после НАЗНАЧИТЬ, (Ь) после завершения В/В и (с) после ОСВОБОДИТЬ. с опережением с помощью процесса буферизации н находятся в зеленых буферах. В этот момент одновременно происходят два действия: (а) программа проводит вычисления по командам, следующим за ОСВОБОДИТЬ, и (Ь) перфокарта считывается в буфер, на который указывает СЛЕДК, Это состояние дел сохранится до тех пор, пока не завершится цикл ввода (и тогда устройство перейдет из состояния "занято" в состояние "готово") или пока программа не выполнит операцию НАЗНАЧИТЬ.
Предположим, что сначала произошло последнее. Тогда буфер, на который указывает стрелка СЛЕДЗ, станет желтым (т. е. текущим), стрелка СЛЕДЗ сместится по часовой стрелке и получится конфигурация, изображенная на рис, 24, (а). Если к этому моменту ввод завершится, то останется еще один блок, введенный с опережением. Поэтому красный буфер станет зеленым, и стрелка СЛЕДК переместится, как показано на рис. 24, (Ь). Если следующей идет операция ОСВОБОДИТЬ, то получится конфигурация, изображенная на рис.
24, (с). Пример, касающийся вывода, приведен на рис. 27 на с. 264. Здесь "цвета" буферных областей представлены как функция от времени. При этом рассматривается программа, которая начинает работу с четырех быстрых выводов, затем медленно выдает еще четыре вывода и в конце концов выдает два вывода подряд. В этом примере используются три буфера, Указатели СЛЕДК и СЛЕДЗ весело продвигаются по кругу по часовой стрелке, каждый со своей скоростью.
Это состязание между программой (которая делает зеленые буфера красными) и процессами буферизации В/В (которые делают красные буфера зелеными). В подобном случае могут возникнуть две конфликтные ситуации. а) Если СЛЕДЗ пытается обогнать СЛЕДК, то программа опережает устройство В/В и вынуждена ждать, пока оно будет готово. Ь) Если СЛЕДК пытается обогнать СЛЕДЗ, то устройство В/В опережает программу и необходимо остановить его до тех пор, пока не будет выполнена следующая операция НЕЬЕАЯЕ. Обе эти ситуации отображены на рис. 27 (см.
упр. 9). ИАзнАчить ОСВОЬОДИТЬ УПРАВЛЕНИЕ ЬУФЕРАИИ Да ВЗ. Иниции вать В/В ет 'Вб. Продвинуть СЛЕДЕ Вб. Уменьшить и В1. Вычис- ление В4. Вычис- ление Рис. 25. Алгоритмы множественной буферизации. К счастью, несмотря на довольно длинное объяснение, которое только что было приведено по поводу кольца буферов, сами алгоритмы обработки данной ситуации довольно просты. В следующем описании будем использовать такие обозначения: Х вЂ” общее число буферов: и — текущее число красных буферов.
(6) В приведенном ниже алгоритме переменная п используется для того, чтобы СЛЕДЗ и СЛЕДК не мешали один другому. Алгоритм К (ОСВОБОДИТЬ). Этот алгоритм состоит из шагов, которые определя- ются операцией ОСВОБОДИТЬ в вычислительной программе, как описано выше. В.1.
(Увеличить п ] Увеличить п на единицу. 1 Алгоритм Б ( Управление буферами). Этот алгоритм осуществляет реальную инициацию операторов В/В в машине; он должен выполняться одновременно с главной программой, в том смысле, как описано ниже. В1. [Вычисление.] Позволить главной программе в течение короткого времени проводить вычисления. Шаг В2 выполняется после некоторой задержки, когда устройство В/В готово для следующей операции. Алгоритм А (НАЗНАЧИТЬ), Этот алгоритм (рис.
25) состоит из шагов, которые определяются операцией НАЗНАЧИТЬ в вычислительной программе, как описано выше, А1. [Ждать условия и с Ю.] Если п = Ю, остановить программу, пока не будет выполнено условие п < Х. (Если п = 1у', следовательно, ни один буфер не готов к тому, чтобы быть назначенным. Но приведенный ниже алгоритм В, работающий параллельно с данным алгоритмом в конце концов достигнет успеха в получении зеленого буфера.) А2.[ТЕКУЩИД ~ — СЛЕДЗ.] Присвоить СОННЕИТ ~ — НЕКТО (назначая, таким образом, текущий буфер). АЗ. [Продвинуть СЛЕДЗ.] Продвинуть СЛЕДЗ к следующему буферу по часовой стрелке. 1 В2. [и = О?] Если и = О, перейти к В1.
(Таким образом, если нет ни одного красного буфера, нельзя Йыполнить ни одну операцию В/В.) ВЗ. [Инициировать г4/В.] Инициировать передачу данных между буферной обла- стью, на которую указывает СЛЕДК, и устройством В/В. В4. [Вычисление.] Позволить главной программе работать в течение некоторого времени; затем, когда операция В/В будет завершена, перейти к шагу В5. В5. [Продвинуть СЛЕДК.] Продвинуть СЛЕДК к следующему буферу по часовой стре- лке. Вб. [Уменьшить и.] Уменьшить и на единицу и перейти к шагу В2. 3 Программа А (НАЗНАЧИТЬ; подпрограмма е сопрограмме СОМРОТЕ). г14 = ТЕКУЩИЙ; г16 г— н и; последовательность вызова: 1МР Аяя1ОИ; на выходе в гХ содержится СЛЕДЯ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
