Этот элементарный метод применялся в программе из раздела 1.4.2 (см. строки 07-08 и 52-53). Но он слишком неэкономно расходует время работы компьютера, так как большая часть времени, которую можно было бы использовать для вычислений, скажем ЮООы или даже ЮОООы, тратится на многократное повторение команды "JBUS". Если это время использовать для вычислений, то скорость выполнения программы можно удвоить. (См. упр. 4 и 5.)

Один из способов избежать такого "цикла ожидания" - использовать две области памяти для ввода. Можно считывать данные в одну область, в то же время выполняя вычисления над данными в другой. Например, программу можно начать командой

IN 2000(5) Начать чтение первого блока. (2)

И теперь каждый раз, когда понадобится прочитать блок с ленты, можно дать пять следующих команд.

ENT1 1000 Подготовиться к выполнению оператора MOVE.

JBUS *(5) Ожидать готовности устройства 5.

MOVE 2000(50) (2000-2049)(1000-1049). (3)

MOVE 2050(50) (2050-2099)(1050-1099).

IN 2000(5) Начать чтение следующего блока.

В целом, это дает такой же эффект, как и применение команды (1), но лента с входными данными остается занятой, пока программа работает над данными, находящимися в ячейках 1000-1099.

Последняя команда (3) начинает считывание блока данных с ленты в ячейки 2000-2099 до того, как был обработан предыдущий блок. Это называется досрочным чтением или опережающим вводом и делается в расчете на то, что данный блок в конце концов понадобится. Но на самом деле, начав обработку блока в ячейках 1000-1099, можно обнаружить, что никаких данных больше не нужно. Мы уже встречались с аналогичной ситуацией, например, в сопрограмме из раздела 1.4.2, где входные данные поступали с перфокарт, а не с ленты. Появление "." в любом месте перфокарты означало, что это последняя карта колоды. Подобная ситуация делает опережающий ввод невозможным. Исключение составляют случаи, когда можно предположить, что (а) за колодой перфокарт с входными данными следует пустая перфокарта или специальная дополнительная карта некоторого другого вида, либо (Ь), скажем, в колонке 80 последней карты колоды появляется опознавательная метка (например, "."). При использовании опережающего ввода для правильного завершения ввода в конце программы всегда должны быть предусмотрены специальные Средства.

Метод параллельного вьшолнения вычислений и операций В/В называется буферизацией, в то время как элементарный метод (1) называется небуферизирован-ным вводом. Область ячеек памяти 2000-2099, которая используется для сохранения опережающего ввода в (3), а также область ячеек 1000-1099, в которые перемещаются входные данные, называется буфером. В словаре Вебстера (Webster) JVew World Dictionary слово "буфер" определяется как "Любой человек или предмет, который служит для смягчения удара". Этот термин нам подходит, так как для буферизации характерна более ровная работа устройств В/В. (Инженеры-электронщики часто используют слово "буфер" в другом смысле, обозначая им часть устройства В/В, в которой сохраняется информация во время ее передачи. Но в этой книге

термин "буфер" будет означать область памяти, используемую программистом для хранения данных В/В.)

Последовательность (3) не всегда лучше, чем (1), хотя исключения из этого правила достаточно редки. Давайте сравним их время выполнения. Пусть Т - время, необходимое для ввода 100 слов, и пусть С - время вьтолнения, которое проходит между запросами на ввод данных. Для метода (1) требуется, в основном, Т + С времени на блок ленты, а для метода (3) - в основном, тах(С,Г) + 202ы. (Величина 202и - это время, необходимое для выполнения двух команд MOVE.) Один из способов оценки времени выполнения состоит в том, чтобы рассмотреть время прохождения критического пути; в данном случае-промежуток времени между моментами использования устройства В/В, в течение которого оно не занято. В методе (1) устройство остается незанятым в течение С единиц времени, а в методе (3) - 202 единиц времени (в предположении, что С < Г).

Относительно медленно работающие команды MOVE из (3) использовать нежелательно, особенно потому, что они отнимают время прохождения критического пути, когда накопитель на магнитной ленте должен быть неактивным. Но существует почти очевидный способ улучшения этого метода, который позволит избежать использования команд MOVE. Внешнюю программу можно переделать так, чтобы она обращалась поочередно к ячейкам 1000-1099 и 2000-2099. Во время считывания данных в один буфер можно выполнять вычисления в другом буфере; затем можно начать считывание в другой буфер, в то же время проводя вычисления над данными в первом буфере. Этот важный метод называется свопингом. Адрес текущего буфера сохраняется в индексном регистре (или, если нет свободных индексных регистров, в ячейке памяти). Мы уже встречались с методом свопинга, когда он применялся к выходным данным алгоритма 1.3.2Р (см. шаги Р9-Р11) и к сопутствующей программе.

Рассмотрим пример применения метода свопинга ко вводу. Предположим, каждый блок ленты состоит из 100 отдельных элементов, содержащих по одно.му слову. Ниже приведена подпрограмма, которая берет следующее слово из входных данных и начинает считывание нового блока, если текущий исчерпан.

В этой программе для адресации последнего слова ввода используется регистр 6. Предполагается, что вызывающая программа не изменяет его значение. Символ U

обозначает накопитель на магнитной ленте, а символ SENTINEL-это значение, о котором известно (из характеристик программы), что его нет ни в одном блоке на ленте.

По поводу данной подпрограммы необходимо отметить следующее.

1) Константа-маркер (8еп11пе1)появляется в качестве 101-го слова каждого буфера и представляет собой удобное средство для обозначения окончания буфера. Но во многих задачах этот метод не будет надежным, так как на ленте может появиться любое слово. Если вводить данные с перфокарт, то подобный метод (когда 17-е слово буфера является маркером) всегда можно использовать, не опасаясь сбоя. В этом случае маркером может служить любое отрицательное число, так как при вводе в MIX с перфокарт всегда получаются неотрицательные слова.

2) В каждом буфере содержится адрес другого буфера (см. строки 07, 11 и 14). Эта "взаимосвязь" облегчает процесс свопинга.

3) Нет необходимости в команде JBUS, так как следующий ввод инициируется до того, как происходит обращение к какому-либо слову из предыдущего блока. Если величины С и Г, как и раньше, обозначают время вычисления и время ввода данных с ленты, то время вьшолнения из расчета на блок ленты теперь составляет шах (С, Г). Поэтому, если С < Т, ленту можно оставить работать на полной скорости. {Примечание. В данном отношении MIX - идеализированный компьютер, так как программа не должна обрабатывать никаких ошибок В/В. На большинстве машин непосредственно перед командой IN в этой программе необходимо было бы использовать команды проверки успешного завершения предыдущей операции.)

4) Чтобы подпрограмма (4) работала правильно, необходимо запустить еще кое-что, как только программа начнет работать. Мы предоставляем читателю самостоятельно разобраться в деталях (см. упр. 6).

5) Благодаря подпрограмме WORDIN для всей остальной программы дело выглядит таким образом, как будто блоки на магнитной ленте имеют длину, равную 1, а не 100. Такой способ разбиения одного блока на ленте на несколько программно-ориентированных записей называется блокировкой записей.

Методы, продемонстрированные здесь для ввода, с небольшими изменениями применимы и для вывода (см. упр. 2 и 3).

Множественная буферизация. Свопинг - это только частный случай при N = 2 общего метода для Л буферов. В некоторых задачах желательно иметь более двух буферов. Для примера рассмотрим следующий тип алгоритма.

Шаг 1. Прочитать пять блоков один за другим.

Шаг 2. На основе этих данных вьшолнить достаточно трудоемкие вычисления. Шаг 3. Вернуться к шагу 1.

В данном случае желательно иметь пять-шесть буферов, чтобы во время вьшолнения шага 2 можно было читать следующую порцию данных из пяти блоков. Благодаря этой тенденции передавать для В/В пакеты данных множественная буферизация получает большие преимущества по сравнению со свопингом.

Предположим, имеется Л буферов для некоторого процесса ввода или вывода, выполняющегося с помощью единственного устройства В/В. Будем представлять себе, что эти буфера расположены по кругу, как показано на рис. 23. Можно считать.