AOP_Tom3 (1021738), страница 84
Текст из файла (страница 84)
О 0 20,000,000 5,ООО.ООО 15,000,000 Число символов от точки загрузки Рис. В2. Приблизительное время счета при двух обычно используемых методах перемотки. Снова о слиянии. Обратимся вновь к процессу Р-путевого слияния, сосредоточив на сей рвз внимание на функционировании устройств ввода и вывода. Будем считать, что для вводных и выводного файлов используется Р + 1 НМЛ. Наша цель — максимально совместить операции ввода-вывода одну с другой и со счетом по программе так, чтобы минимизировать общее время слияния. Поучительно рассмотреть следующий частный случай, в котором на возможную степень одновременности наложены серьезные ограничения.
Предположим, что а) в каждый момент времени можно выполнить запись не более чем на одну ленту; Ь) в каждый момент времени можно читать не более чем с одной ленты; с) чтение, запись и вычисления могут происходить одновременно, только если операции чтения и записи были начаты одновременно.
Оказывается, что даже при таких ограничениях достаточна иметь 2Р буферов ввода и 2 буфера вывода для поддержки, в сущности, максимальной скорости движения лент, если талька мы имеем дело не с очень медленным компьютером. Заметим, что (а) не является на самом деле ограничением, так как имеется толька одна выводная лента.
Кроме того, объем ввода равен объему вывода, так что читается в среднем только одна лента в любой данный момент времени; если условие (Ь) не выполняется, та обязательно должны быть периоды, когда ввод вообще не происходит. Следовательно, для того чтобы минимизировать время слияния, достаточно поддерживать выводную ленту в рабочем состоянии. Желаемый эффект дает важный метод, называемый предсказанием или прогнозированием ([огесавг[пб). Во время выполнения Р-путевого слияния обычно имеется Р текущих буферов ввода, которые используются как источники данных; одни из них заполнены больше других в зависимости от того, какая часть данных в них уже просмотрена. Если все они опустошатся примерно в одно и то же время, то, прежде чем продолжить работу, нам придется выполнить много операций чтения, если только мы не предпримем нужных мер заранее.
К счастью, всегда можно сказать, какой буфер первым станет пустым, просто посмотрев на последнюю запись в каждом буфере. Буфер, последняя запись которого имеет наименьший ключ, обязательно станет первым пустым буфером независимо ат значений каких-либо других ключей, так что мы всегда знаем, какой файл послужит причиной следующей команды ввода.
Алгоритм Г раскрывает этот принцип в деталях. Алгоритм Р [Прогнозирование с плавающими буферами). Этот алгоритм (рис, 83) управляет буферизацией во время Р-путевого слияния длинных файлов при Р > 2. Допустим, чта вводные ленты и файлы пронумерованы так: 1,2,..., Р. В алгоритме используются 2Р буферов ввода, 1 [1],..., 1[2Р], два буфера вывода, 0 [0] и 0 [И, и следующие вспомогательные массивы. А [1], 1 < 1' < 2Р: О, если в буфер 1 [1'] можно вводить данные; 1 — в противном случае й [П, 1 < 1 < Р; Буфер, содержащий последний прочитанный блок из файла 1 СИ, 1 <1< Р: Буфер, используемый в настоящий момент для ввода из файла[ 1.[1], 1 <1< Р: Последний ключ, прочитанный из файла ю' 8 [Я, 1 <1 < 2Р: Буфер, который следует использовать, когда 1 [Я опустошится В описываемом виде алгоритм никогда не остановит работу. Подходящий способ его "выключения" обсуждается ниже.
Рис. ВЗ. Прогнозирование с плавающими буферами. Г1. [Начальная установка.] Прочитать первый блок с ленты 1 в буфер 1[Н, установить АИ г — 1, А[Р+ 13 +- О, В[1] г — г, С[13 < — 1 и установить 0 [13 равным ключу последней записи в 1И при 1 < 1 < Р, Затем найти гп, такое, что 1[гп] = ппп(1,[1],..., В[Р] ), и установить 1 < — О, Й г — Р+ 1. Начать чтение с ленты т в буфер 1 [А]. Г2. (Слияние.) Сливатьзаписиизбуферов1[С[Ц],....,1[С[Р]] вО[П, покаОИ не заполнится.
Если во время этого процесса какой-нибудь буфер ввода, скажем 1[С[Н], станет пустым, а ОИ еще не будет заполнен, то установить А[СБ]] е — О, С[13 < — Я[СИ3 и продолжать слияние. ГЗ. (Ввод-вывод завергпен.) Ожидать, пока не завершится предыдущая операция чтения [или чтения/записи), Затем установить А[А] г — 1, 8[В[из]] г — А, В[пг] ей и установить 1 [из] равным ключу последней записи в 1[1], Г4. )Прогнозирование.) Найти т, такое, что 1[пт] = ппп[ь [13,, В[Р] ), и найти й, такое, что А Уе] = О.
Гб. ~Чтение/запись.) Начать чтение с ленты т в буфер 1 [А] и выполнить запись из буфера 0[13 на выводную ленту, затем положить Ф +- 1 — си вернуться к Г2. $ В примере на рис. 84 показано, как работает метод прогнозирования при Р = 2 в предположении, что каждый блок на ленте содержит только две записи. Здесь представлено содержимое буферов ввода во все моменты, когда мы достигаем начала шага Г2. Алгоритм Г, в сущности, образует Р очередей буферов, где С[г] — на начало [-й очереди, В [13 — на ее конец, Б [Я указывает на преемника буфера 1 [3]; этим у казаниям на рис.
84 соответствуют стрелки. Строка 1 отражает состояние дел после начальной установки. Для каждого вводного файла есть один буфер, и еще один блок читается из файла 1 (так как 08 < 05). Строка 2 показывает положение вещей после того, как слит первый блок: мы выводим блок, содержащий [О1 02~), и вводим следующий блок из файла 2 (так как 05 < 09). Заметим, что в строке 3 три из четырех буферов авода, по сути дела, предоставлены файлу 2, так как мы выполняем чтение из этого файла и в его очереди уже есть полный буфер и частично заполненный буфер. Этот механизм плавающих буферов является важной чертой Содержимое файла 1 01 ОЗ 04 09 11 13 1б 16 Содержимое Файла 2 02 05 Об 07 08 10 12 14 Затем исходные данные Буфера файла 2 читаются иа 1-го файла Номер строки Буфера файла 1 2-го Файла 2-го файла 1-го файла 2-го файла 1-го файла 2-го файла Рис.
84. Очереди буферов в соответствии с алгоритмом Р. алгоритма Г. поскольку мы не смогли бы продолжить работу в строке 4, если бы в строке 3 выбрали файл 1 для ввода вместо файла 2. Чтобы доказать работоспособность алгоритма Г, мы должны проверить выполнение двух условий во время реализации алгоритма: 1) всегда имеется свободный буфер 1т. е. всегда можно найти к на шаге Р4); й) если буфер ввода исчерпывается во время слияния, то его преемник уже присутствует в памяти 1т.
е. Я [С Н3 ) на шаге Е2 имеет осмысленное значение). Допустим, что условие 11) не выполняется, т. е. все буфера заняты в некоторый момент, когда мы достигаем шага Г4. Каждый раз„когда мы приходим к этому шагу, суммарный объем необработанных данных во всех буферах составляет ровно Р емкостей буфера, т. е. данных ровно столько, сколько нужно для заполнения Р буферов, ибо данные вводятся и выводятся с одинаковой скоростью. Некоторые буфера заполнены лишь частично, однако для каждого файла частично заполнен максимум один буфер, так что всего таких буферов не более Р, По предположению все 2Р буферов заняты, так что по меньшей мере Р из них должны быть заполнены целиком.
Это может случиться, только если Р буферов полны и Р пусты, иначе мы бы имели слишком много данных. Но максимум один буфер может быть одновременно пуст и недоступен; следовательно, условие (1) не может не выполняться. Допустим, что условие (й) не выполняется, т. е. ддя некоторого файла в памяти нет необработанных записей, но текущий буфер вывода еще не полон. Согласно принципу прогнозирования нужно иметь не более одного блока данных для всех остальных файлов, так как мы не читаем блок из файла, если этот блок не потребуется прежде, чем будут исчерпаны буфера какого-нибудь другого файла. Таким образом, общее число необработанных записей составляет максимум Р— 1 блоков; добавление неполного буфера вывода дает привод к менее чем Р буферным емкостям данных в памяти; значит, получено противоречие.
Этот анализ подтверждает работоспособность алгоритма Г; он также показывает, что возможны особые ситуации, при которых алгоритм едва-едва избегает круспения. Нами здесь не упомянута еще одна важная тонкость, касающаяся возможного равенства ключей; это обсуждается в упр. 5. [См. также упр. 4, в котором рассматривается случай Р = Ц Один из способов изящного завершения алгоритма Г состоит в присвоении 1[си] значения оо на шаге ГЗ, если только что прочитанный блок был последним в серии, (Конец серии всегда некоторым особым образом помечается.) Посла того как будут прочитаны все данные во всех файлах, мы, в конце концов, обнаружим на шаге Г4, что все б равны оо; тогда обычно можно начать чтение первых блоков следующих серий в каждом файле, выполняя начальную установку' для следующей фазы слияния по мере вывода последних Р + 1 блоков.
Таким образом, можно поддерживать полную скорость работы выводной ленты, осуществляя чтение в любое время не более одной ленты. Исключение из этого правила встречается на шаге Г1, где было бы полезно читать сразу несколько лент, чтобы обеспечить возможность начать работу; но обычно шаг Г1 можно организовать так, чтобы он совмещался с предыдущей частью вычислений. Идея просмотра последней записи каждого блока, чтобы предсказать, какой буфер первым станет пустым, была высказана в 1953 году Ф. Э.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
