сеть образует любое свободное дерево. Автобус имеет конечную емкость, и желательно перевезти пассажиров к их местам назначения так, чтобы автобус прошел минимальное расстояние.

8. [М32] Пусть в задаче о лифте, рассмотренной в тексте раздела, Ь = 1. Сколько перестановок из п человек по п этажам дадут в (4) uj, < 1 при 1 < А: < п? [Например, перестановка 31459268 7.]

► 9. [М25] Найдите важную связь между шейкер-сортировкой, описанной в разделе 5.2.2 (см. рис. 16), и числами ui, иг, Un в (4) для Ь = 1.

10. [20] Как бы вы сортировали файлы на нескольких бобинах, имея только два лентопротяжных устройства?

*5.4.9. Диски и барабаны

До сих пор ленты рассматривались как единственное средство для внешней сортировки, однако нередко в нашем распоряжении оказываются и другие типы более функционально гибких устройств внешней па.мяти. Хотя существует множество конструкций таких запоминающих устройств большого объема или запоминающих устройств с прямым доступом, можно выделить следующие общие для них свойства.

1) Получить доступ к любой заданной части хранимой информации можно довольно быстро.

ii) Блоки данных, содержащие последовательные слова, могут быстро передаваться между внутренней (оперативной) и внешней памятью.

Накопители на магнитной ленте обладают свойством (ii), но не (i), поскольку перемотка ленты от одного конца к другому отнимает .много времени.

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

Одним из наиболее распространенных типов внешних запоминающих устройств, удовлетворяющих (i) и (ii), является накопитель на магнитном диске (НМД), схематически показанный на рис. 89. Данные хранятся на нескольких быстро вращающихся круглых дисках, покрытых магнитным материалом. Для записи или выборки информации используется держатель головок в виде гребешка, включающий одну или несколько головок чтения/записи для каждой поверхности диска. Каждая поверхность делится на концентрические кольца, называемые дорожками или треками, так что за время одного оборота диска под головкой чтения/записи проходит целая дорожка. Держатель головок может перемещаться в двух направлениях - внутрь и наружу, передвигая головки чтения/записи от одной дорожки к другой, но это движение требует времени. Множество дорожек, которые могут быть прочитаны или записаны без перемещения держателя головок, назьшается цилиндром. Например, на рис. 89 показан НМД, который имеет по одной головке чтения/записи на каждую поверхность; пунктирными линиями обозначен один из цилиндров, состоящий из всех дорожек, просматриваемых в настоящий момент головками.

Диски

Держатель головок

Рис. 89. Накопитель на магнитных дисках.

Чтобы конкретизировать эти рассуждения, рассмотрим гипотетический НМД MIXTEC, для которого

1 дорожка = 5000 символов, 1 цилиндр = 20 дорожек, 1 дисковый накопитель = 200 цилиндров.

На таком устройстве хранится 20 млн символов, т. е. чуть меньше того объема данных, который можно записать на одну магнитную ленту в НМЛ MIXT. В некоторых устройствах на дорожках вблизи центра содержится меньше символов, чем на дорожках, расположенных ближе к краю. Это значительно усложняет программирование, но MIXTEC, к счастью, не создает подобных проблем. (См. раздел 5.4.6, в котором обсуждаются характеристики НМЛ MIXT. Здесь будут рассматриваться классические технологии, пригодные для работы с типичными для 70-х годов устройствами; более современные диски имеют больший объем хранимой информации и большую скорость обращения к ней.)

Время, необходимое для чтения или записи на диск, представляет, по существу, сумму трех величин.

• Время поиска (время, затрачиваемое на перемещение держателя головок к нужному цилиндру).

• Время ожидания (задержка, связанная с вращением диска, пока головка чтения/записи не достигнет нужного места).

• Время передачи (задержка, связанная с вращением диска, пока данные проходят под головками).

В НМД MIXTEC время поиска для перехода от цилиндра г к цилиндру j равно 25 -f - j\ мс. Если г и j - случайно выбранные целые числа между 1 и 200, то среднее значение \i - j\ равно 2(2з1)/2002 « 66.7, т. е. среднее время поиска составляет приблизительно 60 мс. Диски MIXTEC совершают один оборот за 25 мс, так что время ожидания равно в среднем 12.5 мс. Время передачи п символов равняется (п/5000) х 25мс 5пмкс. (Это приблизительно в 3 раза больше, чем скорость передачи для НМЛ MIXT, использованного в примерах из раздела 5.4.6.)

Таким образом, основные различия между НМД MIXTEC и НМЛ MIXT, касающиеся сортировки, следующие.

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

b) Отдельная операция с диском, как правило, сопряжена со значительно большими накладными расходами (время поиска + время ожидания по сравнению со временем пуска и/или останова).

c) Скорость передачи у НМД выше.

Используя при работе с лентами разумные схемы слияния, можно до некоторой степени компенсировать недостаток (а). Теперь поставлена иная цель - найти такие рациональные алгоритмы сортировки на дисках, в которых компенсируется недостаток (Ь).

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

• Если мы считываем или записываем за один раз несколько дорожек одного цилиндра, то тем самым устраняем время ожидания (и время поиска) для всех дорожек, кроме первой. Вообще, зачастую можно таким образом синхронизировать вычисления с вращением диска, что при выполнении последовательности команд ввода-вьшода не будет задержек из-за ожидания.

• Рассмотрим, как можно считать половину дорожки данных (рис. 90): если команда чтения выдается, когда головка находится на оси А, то задержка на ожидание отсутствует и общее время чтения равно времени передачи, т. е. х 25 мс. Если вьшолнение команды начинается, когда головка находится в точке В, то требуется j оборота для ожидания и оборота для передачи; в итоге имеем х 25 мс. Наиболее интересен случай, когда головка первоначально находится в точке С: имея соответствующее оборудование и программное обеспечение, можно не потерять I оборота на ожидание. Можно немедленно начать чтение во вторую половину буфера ввода, затем после паузы длительностью х 25мс возобновить чтение в первую половину буфера, так что вьшолнение команды будет завершено, когда головка снова попадет в точку С. Поступая таким образом, можно гарантировать, что суммарное время ожидания и передачи никогда не превзойдет времени одного оборота независимо от начального положения диска. Среднее время ожидания уменьшается в результате с половины оборота до (1 - а;) оборота, если читается или записывается доля х дорожки (О < а; < 1). Если читается или записывается целая дорожка (х = 1), этим методом можно полностью устранить ожидание.

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