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