Д. Кнут - Искусство программирования том 1 (1119450), страница 60
Текст из файла (страница 60)
НАЗНАЧИТЬ ЯТ1 9Р 1Н ЛЖО СОИТЕОЬ(О) А1. Овс вть славия и < Х СМР6 =И= ЗЕ 1В ю4 низ аа гиии а, ~и', ЬОХ -1,4 ЯТХ СЛЕДЯ 9Н 1МР Выход. $ АЗ. П о вин ть СЛ 3 Программа В. (ОСВОБОДИТЬ; исиольгуешсл е сопрограмме СОМРОТЕ). г16 = и. Этот маленький фрагмент следует вставлять везде, где нужно выполнить операцию ВЕЬЕАЯЕ. 1МС6 1 Н1. Увеличить и.
1ВЕО СОИТЕОЬ(О) Возможен переход к сопрограмме СОИТЛОЬ. Программа В (Сопрограмма СОИТЕО1.). г16 = п, г15 = СЛЕДК. СОИТ1 )МР СОМРОТЕ В1. Вычисление. 1Н 362 ь-1 В2. и=ОХ Ьи О,ЬЮ ВЗ. И,а,В~В. Л1Р СОМРОТЕ В4. Вычисление. 1.05 -1,5 В5. П вин ть СЛ РЕСб 1 Вб. Уменыпить п. 1МР 1В $ "Управление" и "вычисление", — Прим, иерее. В этих алгоритмах присутствуют два независимых процесса, выполняющихся водновременно",— программа управления буферизацией и вычислительная программа.
Фактически эти процессы являются сопрограммами, которые мы назовем СОИТЕОЬ и СОМРОТЕ*. Сопрограмма СОИТЕОЬ вызывает СОМРОТЕ на шагах В1 и В4; сопрограмма СОМРОТЕ вызывает СОИТЕОЬ с помощью команд "перехода при готовности", которые разбросаны в программе через случайные промежутки. Запрограммировать этот алгоритм для М1Х чрезвычайно просто. Для удобства будем считать, что буфера связаны таким образом, что слово, иредшесгиеующее каждому из них,— это адрес следующего буфера. Например, при )ч' = 3 имеем СОИТЕМТЯ(ВОР1 — 1) = ВОР2„ СОМТЕИТЯ(ВОР2 — 1) = ВОРЕ и СОИТЕМТЯ(ВОРЗ вЂ” 1) = ВОР 1. Помимо приведенного выше кода, имеем также обычные команды связи сопрограмм: СОИТВОЬ ЗТ2 СОМРОТЕХ СОМРОТЕ ЗТЛ СОИТВОЬХ СОИТВОЬХ ЛМР СОИТ1 СОМРОТЕХ 2МР СОМР1 Кроме того, команду "Л~ЕО СОИТВОЬЯ)" следует помещать внутри программы СОМРОТЕ примерно через каждые 50 команд.
Таким образом, программы множественной буферизации состоят, в сущности, только из семи команд для СОИТВОЬ, восьми — для НАЗНАЧИТЬ и двух — для ОСВОБОДИТЬ. Здесь есть один замечательный факт; один и тото же алгоритм можно применять и для ввода, и для вывода. Но в чем же отличие между этими двумя процессами? Как программа управления определяет, что нужно делать — опережать (в случае ввода) или запаздывать (в случае вывода)? Ответ на этот вопрос кроется в начальных условиях. При вводе мы начинаем с и = Ф (все буфера красные), а при выводе — с п = 0 (все буфера зеленые).
И после того как программа запустится при соответствующих начальных условиях, она уже будет себя вести либо как процесс ввода, либо как процесс вывода. Другим начальным условием является ИЕХТВ = ИЕХТО, т. е. обе стрелки должны указывать на один из буферов. Для завершения программы необходимо остановить процесс ввода-вывода (если это ввод) нли подождать, пока он закончится (если это вывод); подробности мы оставляем читателю (см. упр. 12 и 13).
Здесь возникает важный вопрос: "Какое значение В' является оптимальным?", Конечно, по мере увеличения ?Ч скорость работы программы не уменьшится, но и не будет неограниченно расти, поэтому рано или поздно скорость роста снизится. Давайте снова обратимся к величинам С и Т, которые представляют время вычислений между операторами В/В и само время В/В.
Точнее, пусть С— это промежуток времени между последовательными операциями НАЗНАЧИТЬ, а Т— промежуток времени, за которое передается один блок. Если С всегда больше Т, то вполне достаточно будет значения Ю = 2, так как нетрудно показать, что с двумя буферами компьютер будет постоянно занят. Если С всегда меньше Т„ то и в такой ситуации достаточно значения Ж = 2, поскольку устройство В/В будет постоянно занято (за исключением случая, когда устройство имеет особые ограничения на время использования, как в упр.
19). Следовательно, ббльшие значения Х полезны, главным образом, тогда, когда С принимает то малые, то большие значения. При этом, если большие значения С существенно превосходят Т, подходящим значением?Ь'является среднее число последовательных малых величин С плюс 1. (Нужно заметить, однако, что преимущества буферизации фактически сводятся на нет, если ввод полностью выполняется в начале программы, а вывод— полностью в конце.) Если промежуток времени между операциями НАЗНАЧИТЬ и ОСВОБОДИТЬ всегда достаточно мал, то во всех описанных выше случаях значение В' можно уменьшить на 1, что почти не окажет влияния на время выполнения. Этот подход к буферизации можно изменять различными способами, и мы кратко расскажем о некоторых из них.
До сих пор предполагалось, что используется только одно устройство В/В, но, конечно, на практике вы будете применять несколько устройств одновременно. Существует несколько подходов к ситуации, когда используется несколько устройств. В простейшем случае у нас будет отдельное кольцо буферов для каждого устройства. Для каждого устройства будут заданы свои значения и, Х, СЛЕДК, СЛЕДЗ и ТЕКУЩИИ, а также собственная сопрограмма СОИТИОЪ. В результате мы будем иметь эффективную буферизацию одновременно на всех устройствах В/В. Можно также создать "пул" буферных областей одинакового размера, чтобы два или более устройств совместно использовали буфера из общего списка.
Это можно осуществить с помощью методов связывания памяти, которые описываются в главе 2, когда все красные буфера ввода связываются в один список, а все зеленые буфера вывода — в другой. В данном случае возникает необходимость отличать ввод от вывода, т. е. нужно переписать алгоритмы, чтобы в них не йспользовались и и Х Если все буфера в пуле окажутся заполненными входными данными, полученными методом опережающего ввода, то алгоритм будет неизменно останавливатыя.
Поэтому необходимо убедиться, что существует по крайней мере один буфер (причем желательно по одному для каждого устройства), который не является зеленым буфером ввода. И только если программа СОИрОТЕ останавливается на шаге А1 для некоторого устройства ввода, следует разрешить ввод данных с этого устройства в последний буфер пула. Некоторые машины имеют дополнительные ограничения на использование устройств ввода-вывода, делающие невозможной одновременную передачу данных с определенных пар устройств. (Например, несколько устройств можно подключить к компьютеру с помощью единственного "канала".) Это ограничение также оказывает влияние на нашу программу буферизации. Как сделать правильный выбор, когда нужно решить, какое устройство В/В инициировать следующим? Это называется задачей прогнозирования.
Лучшее правило прогнозирования для общего случая, видимо, состоит в том, чтобы отдать предпочтение устройству, буферное кольцо которого имеет наибольшее значение и)Х. При этом предполагается, что число буферов в кольце было выбрано обдуманно. Рис. 28. Ввод н вывод е одном и том же кольце буферов. следа И в заключение рассмотрим полезный метод выполнения и ввода, и вывода с помощью одного и шого огсе кольца буферов, который можно применять при определенных условиях. На рис. 26 показан новый вид буфера — фиолетовый.
В этой ситуации зеленые буфера представляют опережающий ввод; в результате операции НАЗНАЧИТЪ зеленый буфер становится желтым, а затем, после операции ОСВОНОДИТЪ, — красным и представляет блок, который нужно вмеестп. Процессы ввода и вывода, как и раньше, независимо двигаются по кругу, только сейчас после выполнения операции вывода красные буфера становятся фиолетовыми, а при вводе фиолетовый буфер превращается в зеленый. Необходимо гарантировать, что указатели СЛЕДЗ, СЛЕДЕ и СЛЕДФ не будут обгонять друг друга. В момент, показанный на рис. 26, программа выполняет вычисления между операциями НАЗНАЧИТЬ и ОСВОЕОДИТЬ, работая с желтым буфером; одновременно производится ввод в буфер, на который указывает стрелка СЛЕДФ, и вывод из буфера, на который указывает стрелка СЛЕДИ.
УПРАЖНЕНИЯ 1. [05] Будет лн последовательность команд (3) по-прежнему правильной, если поместить команды МОЧЕ перед командой 1303, а не после нее? А если поместить команды МОЧЕ после команды 1М? 2. [10] С помощью команд "ООТ 1000(6); 1303 э(6)" можно вывести блок данных на ленту, не используя буферизацию, точно так же, как команды (1) делают это в случае ввода. Предложите метод, аналогичный (2) н (3), который буферизирует этот вывод, используя команды МОЧЕ н вспомогательный буфер, занимающий ячейки 2000 — 2099. 3. [22] Напишите подпрограмму вывода с помощью свопннга, аналогичную (4). Эта подпрограмма с именем Чойпопт должна сохранять слово в гА в качестве следующего слова вывода, а когда буфер будет заполнен, записывать 100 слов на магнитную ленту (устройство Ч). В индексном регистре 5 должен храниться адрес текущего буфера.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
