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