a. Ш

1 2 3 4 5 6 7

Время От завершения предыдущей операции до инициализации следующей команды контроллера НМЛ

Рис. 81. Вычисление времени стартстопной задержки. (Оно добавляется ко времени, затрачиваемому на чтение или запись блоков и промежутков.)

времени чтения/записи ко времени перемотки обычно находится в диапазоне между 2 и 3, но оно не дает адекватной модели эффекта комбинированной нормальной и быстрой перемотки, имеющейся во многих других моделях НМЛ (рис. 82).

При первоначальной установке и/или перемотке к началу лента помещается в точку загрузки и для любой операции чтения или записи, начинающейся из этого положения, требуется дополнительно 110 мс. Если лента не находится в точке загрузки, она может быть прочитана в обратном направлении; 32 мс добавляется ко времени выполнения любой операции чтения/записи в обратном направлении, если она следует за операцией в прямом направлении, и к любой операции чтения/записи в прямом направлении, следующей за операцией, которая выполняется при обратном направлении движения ленты.

S S 2

вГ 2

5,000,000 15,000,000

Число символов от точки загрузки

23,000,000

Рис. 82. Приблизительное время счета при двух обычно используемых методах перемотки.

Снова о слиянии. Обратимся вновь к процессу Р-путевого слияния, сосредоточив на сей раз внимание на функционировании устройств ввода и вывода. Будем

считать, что для вводных и выводного файлов используется Р + 1 НМЛ. Наша цель - максимально совместить операции ввода-вывода одну с другой и со счетом по программе так, чтобы минимизировать общее время слияния.

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

a) в каждый момент времени можно вьшолнить запись не более чем на одну ленту;

b) в каждый момент времени можно читать не более чем с одной ленты;

c) чтение, запись и вычисления могут происходить одновременно, только если операции чтения и записи были начаты одновременно.

Оказывается, что даже при таких ограничениях достаточно иметь 2Р буферов ввода и 2 буфера вывода для поддержки, в сущности, максимальной скорости движения лент, если только мы имеем дело не с очень медленным компьютером. Заметим, что (а) не является на самом деле ограничением, так как имеется только одна выводная лента. Кроме того, объем ввода равен объему вывода, так что читается в среднем только одна лента в любой данный момент времени; если условие (Ь) не выполняется, то обязательно должны быть периоды, когда ввод вообще не происходит. Следовательно, для того чтобы минимизировать время слияния, достаточно поддерживать выводную ленту в рабочем состоянии.

Желаемый эффект дает важный метод, называемый предсказанием или прогнозированием (forecasting). Во время выполнения Р-путевого слияния обычно имеется Р текущих буферов ввода, которые используются как источники данных; одни из них заполнены больше других в зависимости от того, какая часть данных в них уже просмотрена. Если все они опустошатся примерно в одно и то же время, то, прежде чем продолжить работу, нам придется выполнить много операций чтения, если только мы не предпримем нужных мер заранее. К счастью, всегда можно сказать, какой буфер первым станет пустым, просто посмотрев на последнюю запись в каждом буфере. Буфер, последняя запись которого имеет наименьший ключ, обязательно станет первым пустым буфером независимо от значений каких-либо других ключей, так что мы всегда знаем, какой файл послужит причиной следующей команды ввода. Алгоритм F раскрывает этот принцип в деталях.

Алгоритм F {Прогнозирование с плавающими буферами). Этот алгоритм (рис. 83) управляет буферизацией во время Р-путевого слияния длинных файлов при Р > 2. Допустим, что вводные ленты и файлы пронумерованы так: 1,2,..., Р. В алгоритме используются 2Р буферов ввода, I [1],..., IС2Р], два буфера вывода, О [0] и О [1], и следующие вспомогательные массивы.

А СЛ Д < j < 2Р: О, если в буфер IС j] можно вводить данные;

1 - в противном случае В [г], 1 < г < Р: Буфер, содержащий последний прочитанный блок из файла г С Сг], 1 < г < Р: Буфер, используемый в настоящий момент для ввода из файла г L [г], 1 < г < Р: Последний ключ, прочитанный из файла i

S ijl, 1 < i < 2Р: Буфер, который следует использовать, когда IС j] опустошится

В описываемом виде алгоритм никогда не остановит работу. Подходящий способ его "выключения" обсуждается ниже.

F5. Чтение/запись

Рис. 83. Прогнозирование с плавающими буферами.

F1. [Начальная установка.] Прочитать первый блок с ленты i в буфер iCi], установить АСг] <- 1, А[Р-(-«] <г- О, ВШ <г- i, СМ <- г и установить LB] равным ключу последней записи в 1Сг] при 1 < г < Р. Затем найти тп, такое, что LCm] = min{LCl],...,LCP]}, и установить t <- О, А; <- Р Н-1. Начать чтение с ленты т в буфер I [А;].

F2. [Слияние.] Сливать записи из буферов I [С [1] ],..., I [С [Р] ] в О [t], пока О ш не заполнится. Если во время этого процесса какой-нибудь буфер ввода, скажем 1СС[г]], станет пустым, а OCt] еще не будет заполнен, то установить А [С [г]] <- О, СМ <- SCCCi]] и продолжать слияние.

F3. [Ввод-вывод завершен.] Ожидать, пока не завершится предыдущая операция чтения (или чтения/записи). Затем установить А [А;] <- l,S[BCm]] <- А;, B[m] <-к и установить L [т] равным ключу последней записи в I [А;].

F4. [Прогнозирование.] Найти т, такое, что L[m] = min{L[l],... ,LCP]}, и найти к, такое, что А [А;] = 0.

F5. [Чтение/запись.] Начать чтение с ленты m в буфер I [А;] и выполнить запись из буфера О [i] на выводную ленту, затем положить t <- 1 - t и вернуться к F2.

В примере на рис. 84 показано, как работает метод прогнозирования при Р = 2 в предположении, что каждый блок на ленте содержит только две записи. Здесь представлено содержимое буферов ввода во все моменты, когда мы достигаем начала шага F2. Алгоритм F, в сущности, образует Р очередей буферов, где С [г] - на начало г-й очереди, В [г] - на ее конец, SCj] указывает на преемника буфера iCj]; этим указаниям на рис. 84 соответствуют стрелки. Строка 1 отражает состояние дел после начальной установки. Для каждого вводного файла есть один буфер, и еще один блок читается из файла 1 (так как 03 < 05). Строка 2 показывает положение вещей после того, как слит первый блок: мы выводим блок, содержащий 01 02 , и вводим следующий блок из файла 2 (так как 05 < 09). Заметим, что в строке 3 три из четырех буферов ввода, по сути дела, предоставлены файлу 2, так как мы выполняем чтение из этого файла и в его очереди уже есть полный буфер и частично заполненный буфер. Этот механизм плавающих буферов является важной чертой-