Д. Кнут - Искусство программирования том 1 (1119450), страница 58
Текст из файла (страница 58)
Поэтому самый простой способ считать блок данных с ленты в ячейки 1000-1099 так, чтобы информация была на месте, — воспользоваться двумя командами: 1й 1000(5); 0ВВВ я(5), Этот элементарный метод применялся в программе из раздела 1.4.2 (см. строки 07- 08 и 52 — 53). Но он слишком неэкономно расходует время работы компьютера, так как большая часть времени, которую можно было бы использовать для вычислений, скажем 1000и или даже 10000и, тратится на многократное повторение команды 63ВОЯ".
Если это время использовать для вычислений, то скорость выполнения программы можно удвоить. (См. упр. 4 и 5.) Один из способов избежать такого "цикла ожидания" — использовать две области памяти для ввода. Можно считывать данные в одну область, в то же время выполняя вычисления над данными в другой. Например, программу можно начать командой 1М 2000(6) Начать чтение первого блока. (2) И теперь каждый раз, когда понадобится прочитать блок с ленты, можно дать пять следующих команд. ЕМТ1 1000 Подготовиться к выполнению оператора МОУЕ. ВЗВОЯ в(6) Ожидать готовности устройства 5.
МОУЕ 2000(60) (2000-2049) -> (1000 — 1049). (3) МОУЕ 2060(50) (2050 †20) -+ (1050 †10). 1М 2000(6) Начать чтение следующего блока. В целом, это дает такой же эффект, как и применение команды (1), но лента с входными данными остается занятой, пока программа работает над данными, находящимися в ячейках 1000 — 1099. Последняя команда (3) начинает считывание блока данных с ленты в ячейки 2000 — 2099 до того, как был обработан предыдущий блок.
Это называется досрочным чтением или опережаюи1им вводом и делается в расчете на то, что данный блок в конце концов понадобится. Но на самом деле, начав обработку блока в ячейках 1000 — 1099, можно обнаружить, что никаких данных больше не нужно. Мы уже встречались с аналогичной ситуацией, например, в сопрограмме из раздела 1.4.2, где входные данные поступали с перфокарт, а не с ленты.
Появление "." в любом месте перфокарты означало, что это последняя карта колоды. Подобная ситуация делает опережающий ввод невозможным. Исключение составляют случаи, когда можно предположить, что (а) за колодой перфокарт с входными данными следует пустая перфокарта или специальная дополнительная карта некоторого другого вида, либо (Ъ), скажем, в колонке 80 последней карты колоды появляется опознавательная метка (например, ".'). При использовании опережающего ввода для правильного завершения ввода в конце программы всегда должны быть предусмотрены специальные средства.
Метод параллельного выполнения вычислений и операций В/В называется буферизацией, в то время как элементарный метод (1) называется небуферизированным вводом. Область ячеек памяти 2000 — 2099, которая используется для сохранения опережающего ввода в (3), а также область ячеек 1000 — 1099, в которые перемещаются входные данные, называется буфером. В словаре Вебстера (%еЪэгег) №в ИогМ Псбопагу слово "буфер" определяется как "Любой человек или предмет, который служит для смягчения удара".
Этот термин нам подходит, так как для буферизации характерна более ровная работа устройств В/В. (Инженеры-электронщики часто используют слово "буфер" в другом смысле, обозначая им часть устройства В/В, в которой сохраняется информация во время ее передачи, Но в этой книге 01 ЫОЙО1И Ог 00 2Н 04 00 1Н 00 07 08 00 1ИВОР1 10 11 1Я 1ИВОР2 10 14 ЯТЗ 1Р 1ИС6 1 ЫА 0,6 СИРА =ЯЕИТ1ИЕ1.
ЛИЕ 1И -100,6(О) Ыб 1,6 ЗМР 2В ОВ10 г+100 СОИ ЯЕИТ1ИЕЕ СОМ к+1 ОВ10 *+100 СОМ ЯЕИТ1ИЕЕ СОИ 1ИВОР1 Сохранить адрес выхода. Перейти к следующему слову. Это конец буфера? Если нет, выйти. Пополнить этот буфер. Переключиться иа другой буфер и вернуться. Первый буФер. Маркер конца буфера. Адрес другого буфера.
Второй буфер. Маркер конца буфера. Адрес другого буфера. 1 (4) В этой программе для адресации последнего слова ввода используется регистр б. Предполагается, что вызывающая программа не изменяет его значение. Символ О термин "буфер" будет означать область памяти, используемую программистом для хранения данных В/В.) ' Последовательность (3) не всегда лучше, чем (1), хотя исключения из этого правила достаточно редки. Давайте сравним их время выполнения. Пусть Т— время, необходимое для ввода 100 слов, и пусть С вЂ” время выполнения, которое проходит между запросами на ввод данных.
Для метода (1) требуется, в основном, Т + С времени на блок ленты, а для метода (3) — в основном, тах(С,Т) + 202и. (Величина 202и — это время, необходимое для выполнения двух команд МОЧЕ.) Один из способов оценки времени выполнения состоит в том, чтобы рассмотреть время прохождения критического пути; в данном случае — промежуток времени между моментами использования устройства В/В, в течение которого оно не занято, В методе (1) устройство остается незанятым в течение С единиц времени, а в методе (3) — 202 единиц времени (в предположении, что С < Т).
Относительно медленно работающие команды МОЧЕ из (3) использовать нежелательно, особенно потому, что они отнимают время прохождения критического пути, когда накопитель на магнитной ленте должен быть неактивным. Но существует почти очевидный способ улучшения этого метода, который позволит избежать использования команд МОЧЕ. Внешнюю программу можно переделать так, чтобы она обращалась поочередно к ячейкам 1000 — 1099 и 2000 — 2099.
Во время считывания данных в один буфер можно выполнять вычисления в другом буфере; затем можно начать считывание в другой буфер, в то же время проводя вычисления над данными в первом буфере. Этот важный метод называется свацингам. Адрес текущего буфера сохраняется в индексном регистре (или, если нет свободных индексных регистров, в ячейке памяти). Мы уже встречались с методом свопинга, когда он применялся к выходным данным алгоритма 1.3.2Р (см.
цгаги Р9-Р11) и к сопутствующей программе. Рассмотрим пример применения метода свопинга ко вводу. Предположим, каждый блок ленты состоит из 100 отдельных элементов, содержащих по одному слову. Ниже приведена подпрограмма, которая берет следующее слово из входных данных и начинает считывание нового блока, если текущий исчерпан. обозначает накопитель на магнитной ленте., а символ БЕИТ1ИЕ1.— это значение, о котором известно (из характеристик программы), что его нет ни в одном блоке на ленте.
По поводу данной подпрограммы необходимо отметить следующее. 1) Константа-маркер (вепс1пе1)появляется в качестве 101-го слова каждого буфера и представляет собой удобное средство для обозначения окончания буфера. Но во многих задачах этот метод не будет надежным, так как на ленте может появиться любое слово. Если вводить данные с перфокарт, то подобный метод (когда 17-е слово буфера является маркером) всегда можно использовать, не опасаясь сбоя. В этом случае маркером может служить любое отрицательное число, так как при вводе в И1Х с перфокарт всегда получаются неотрицательные слова. 2) В каждом буфере содержится адрес другого буфера (см.
строки 07, 11 и 14). Эта "взаимосвязь" облегчает процесс свопинга. 3) Нет необходимости в команде ЛВ0Б, так как следующий ввод инициируется до того, как происходит обращение к какому-либо слову из предыдущего блока. Если величины С и Т, как и раньше, обозначают время вычисления и время ввода данных с ленты, то время выполнения из расчета на блок ленты теперь составляет шах(С,Т). Поэтому, если С < Т, ленту можно оставить работать на полной скорости. (Примечание. В данном отношении И1Х вЂ” идеализированный компьютер, так как программа не должна обрабатывать никаких ошибок В/В. На большинстве машин непосредственно перед командой 1И в этой программе необходимо было бы использовать команды проверки успешного завершения предыдущей операции.) 4) Чтобы подпрограмма (4) работала правильно, необходимо запустить еще коечто, как только программа начнет работать.
Мы предоставляем читателю самостоятельно разобраться в деталях (см. упр. б). 5) Благодаря подпрограмме в0301й для всей остальной программы дело выглядит таким образом, как будто блоки на магнитной ленте имеют длину, равную 1, а не 100. Такой способ разбиения одного блока на ленте на несколько программно- ориентированных записей называется блокировкой записей. Методы, продемонстрированные здесь для ввода, с небольшими изменениями применимы и для вывода (см. упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
