AOP_Tom3 (1021738), страница 95
Текст из файла (страница 95)
а) При работе с лентами возможен только последовательный доступ к данным. Ь) Отдельная операция с диском, как правило, сопряжена со значительно ббльшими накладными расходами (время поиска + время ожидания по сравнению со временем пуска и/нли останова). с) Скорость передачи у НМД выше. Используя при работе с лентами разумные схемы слияния, можно до некоторой степени компенсировать недостаток (а). Теперь поставлена иная цель — найти такие рациональные алгоритмы сортировки на дисках, в которых компенсируется недостаток (Ь). Способы сокращения времени ожидания. Рассмотрим сначала задачу минимизации задержек, причина которых заключается в том, что в момент, когда необходимо начать выполнение команды ввода-вывода, диск, как правило, не находится в подходящей позиции.
Нельзя заставить диск вращаться быстрее, но всетаки можно прибегнуть к разным уловкам, которые уменьшат или даже полностью устранят время ожидания. ° Если мы считываем или записываем за один раз несколько дорожек одного цилиндра, то тем самым устраняем время ожидания (и время поиска) для всех дорожек, кроме первой. Вообще, зачастую можно таким образом синхронизиронать вычисления с вращением диска, что при выполнении последовательности команд ввода-вывода не будет задержек из-за ожидания. ° Рассмотрим, как можно считать половину дорожки данных (рис. 90): если команда чтения выдается, когда головка находится на оси А, то задержка на ожидание отсутствует и общее время чтения равно времени передачи, т.
е, > х 25 мс. Если выполнение команды начинается, когда головка находится в точке В, то требуется -' оборота для ожидания и -' оборота для передачи; в итоге имеем з х 25 мс. Наиболее интересен случай, когда головка первоначально находится в точке С: имея соответствующее оборудование и программное обеспечение, можно не потерять з оборота на ожидание. Можно немедленно начать чтение во вторую половину 4 > г буфера ввода, затем после паузь> длительностью — х 25 мс нозобновить чтение в 2 первую половину буфера, так что выполнение команды будет завершено, когда головка снова попадет в точку С. Поступая таким образом, можно гарантировать, что суммарное время ожидания и передачи никогда не превзойдет времени одного оборота независимо от начального положения диска. Среднее время ожидания уменьшается в результате с половины оборота до —.'(1 — х ) оборота, если читается или записывается доля х дорожки (О < х < 1).
Если читается или записывается целая дорожка (х = 1), этим методом можно полное>пью устранить ожидание. Барабаны: случай, когда поиск не нужен. На некоторых устройствах внешней памяти установлено по одной головке чтения/записи для каждой дорожки, и поэтому время на поиск не отводится. Еш>и на таком устройстне используется метод, продемонстрированный на рис. 90, то как время поиска, так и время ожидания сведены к нулю (при условии, что мы всегда чвтаем или записываем всю дорожку целиком).
В этой идеальной ситуации время передачи является единственным ограничивающим фактором. 11Онениин дорожки данных Рис. 90. Анализ времени ожидания при чтении полонины дорожки Рассмотрим вновь пример из раздела 5.4.6, н катарам сартируются 100,000 записей по 100 символов и используется оперативная память емкостью 100 000 символов. Весь объем сартируемых данных занимает половину диска И1ХТЕС. Обычно невозможно одновременно выполнять считывание и запись на одном дисковом устрайствее поэтому предположим, что имеется два диска и чтение и запись можно совместить.
Пока будем считать, что диски — это фактически барабаны с 4000 дорожек по 5 000 символов и никакого времени поиска не требуется. Какой алгоритм сортировки следует использовать? Естественно выбрать метод слияния; друтие методы внутренней сортировки не столь хороши н применении к дискам, за исключением, возможно, поразрядных методов, описанных в разделе 5.2.5.
Но анализ, приведенный в разделе 5.4.7, показывает, что поразрядная сортировка обычно проигрывает слиннию в большинстве приложений общего назначении, поскольку теорема двойственности, сформулированная н этом разделе, применима к дискам точно так же, как и к лентам, Поразрядная сортировка действительна имеет преимущество в случае, когда ключи равномерно распределены и параллельно используется множество дисков, поскольку исходное распределение цифр ключей может помочь разделить всю процедуру на несколько независимых падпроцессав, никак не обменивающихся информацией.
(См., например, В. С. Абагжа1, 81СМОП Яесоге) 25, 2 (Яппе, 1996), 240-246.) В дальнейшем основное внимание будет уделено сортировке методом слияния. Чтобы начать такую сортировку, можно использовать выбор с замещением с двумя буферами ввода по 5000 символов и двуми буферами вывода по 5000 символов. Фактически можно свести требования к оперативной памяти к трем буферам по 5000 символов, если замещать записи в текущем буфере ввода записями, выводимыми из дерева выбора. Остается еще 85000 символов (850 записей) для дерева выбора, так чта один проход на данным, которые используются в этой книге в качестве примера, позволит сформировать около 60 начальных серий (см.
формулу 5.4.6-(3)). Этот проход занимает лишь около 50 с, если предположить, что скорость внутренней обработки достаточно высока, чтобы успеть за вводом-выводом (каждые 500 мкс в буфер вывода должна передаваться запись). Если же сортируемые исходные данные находятся на НМЛ М1ХТ, а не на барабане, этот проход будет выполняться медленнее и время будет зависеть от скорости обмена данными с НМЛ. Нетрудно видеть, что при использовании двух барабанов и при чтении/записи полньж дорожек общее время передачи для Р-путевого слияния уменьшается с уве- личением Р. К сожалению, нельзя выполнить одно только 60-путевое слияние всех начальных серий, так как в памяти нет места для 60 буферов.
(Если размер буферов будет меньше 5000 символов, то появится нежелательное время ожидания. Прошу не забывать, что мы все еще находимся в начале 70-х годов. когда возможности использования оперативной памяти бьшн весьма ограничены.) Есчн выполнять Р-путевое с ~ияние, переписывая все данные с одного барабана на друтой таким образом, что чтение и запись совмещены, то число проходов слияния равно ~~1обр 601; следовательно, можно завершить работу за двв прохода, если 8 < Р ( 59. С уменьшением Р уменьшается объем сопутствующих вычислений, поэтому выберем Р = 8; если будет образовано 65 начальных серий, выберем Р = 9. Если будет образовано 82 или больше начальных серий, можно взять Р = 10, но, так как имеется место только для 18 буферов ввода и двух буферов вывода, могут возникнуть задержки в процессе слияния (см.
алгоритм 5.4.6Е). В таком случае, вероятно, лучше выполнить два ~астичных прохода, обрабатывая небольшую ласть данных, и сократить таким образом число начальных серий до 81 или меньше. При наших предположениях каждый проход сз~ияния займет около 50 с, так что вся сортировка в этой идеальной ситуации будет завершена за '2.5 мип (плюс несколько секунд на инициализацию и другие вспомогательные операции). Это в шесть раз быстрее, чем при наилучшей из сортировок с шестью лентами, рассмотренных в разделе 5.4,6. Причинами такого ускорения являются увеличенная скорость передачи данных между внешней и оперативной памятью (она в 3.5 раза выше), более вьюокий порядок слияния (мы не можем осуществить 8-путевое слияние на лентах, не имея девяти или более лент) и то, что выводные данные остаются на диске (нет необходимости в заключительной перемотке и других аналогичных операциях).
Если исходные данные и рассортированный результат должны находиться на НМЛ И1ХТ, а барабаны использоваться только для слияния, то понадобится около 8.2 мин, Если имеется не два барабана, а только один, .то время ввода-вывода увеличится вдвое, поскольку чтение и запись придется вьнюлнять по отдельности. (На самом деле операции ввода-вывода займут в три раза больше времени, поскольку запись будет осуществляться поверх исходных данных. В таких случаях целесообразно за каждой операцией записи выполнг ть операцию контрольного чтения, чтобы не потерять необратимо какие-либо исходные данные, если только оборудование не обеспечивает автоматическую проверку записанной информации.) Однако часть этого дополнительного времени можно использоаать эффективно, поскольку можно реализовать метод частичных проходов, при котором одни записи обрабатываютси чаще других. Применение двух барабанов предполагает, что все данные обрабатываются четное или нечетное число раз, но в случае одного барабана можно использовать более общие схемы слияния.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
