Способ и устройство для управления доступом к диску для записи данных
Использование: в технике накопления информации, в частности в устройствах памяти быстродействуюших компьютеров. Сущность изобретения: способ и устройство управления доступом к диску для записи данных обеспечивают определение сдвига, указывающего угловую разность в направлении вращения диска для записи данных между началами соседних блоков данных, который минимизирует время ожидания, обусловленное вращением диска для записи данных на среднем расстоянии перемещения головки при обращении головки к диску для записи данных. Положение блока данных на диске для записи данных определяется на основании, по меньшей мере, определенного сдвига, планируется порядок множества входных запросов доступа к диску для записи данных для минимизации величины перемещения головки при обращении головки к диску для записи данных. Обращение головки к диску для записи данных осуществляется на основании результата планирования. Благодаря такому техническому решению обеспечивается высокоскоростной произвольный доступ к хранимой на диске информации, что является предпочтительным для хранения мультимедийных данных. 5 с. и 28 з.п. ф-лы, 16 ил.
Настоящее изобретение относится к способу управления доступом к диску для записи данных, требующему высокой скорости передачи и доступа к отдельным участкам на диске (случайного доступа), и устройству для осуществления способа.
Предшествующий уровень техники С увеличением быстродействия компьютеров все более важными становятся устройства памяти на дисках, которые дают возможность осуществить быстрый случайный доступ. В последние годы, особенно в технологии для мультимедиа, основное внимание уделяется в первую очередь выборке с высокой скоростью движущихся изображений и аудиоданных, хранимых на диске в виде цифровых данных, и с участков на диске, отделенных один от другого. А именно, требуются высокая скорость передачи и возможность обработки в реальном времени для хранения мультимедийных данных, таких как движущиеся изображения и аудиоданные. Высокая скорость передачи, естественно, становится необходимой при обработке большого количества движущихся изображений и аудиоданных. Кроме того, свойство реального времени требует, чтобы верхний предел времени обработки не был превышен. Например, движение становится прерывистым, если в движущемся изображении не отображается 30 кадров в секунду с постоянными интервалами. Далее, если не обеспечивается поддержание характеристик диска и имеется недостаточное количество аудиоданных, звук прерывается и генерируется неприятный шум. Таким образом, если мультимедийные данные не подготовлены и не используются в соответственно заданное для них время, ценность информации резко падает. Соответственно, в устройствах памяти для мультимедиа важно, чтобы гарантировался верхний предел, то есть чтобы обработка была выполнена за это время даже в наихудшем случае. В противном случае, даже если удовлетворяются технические условия в смысле средней эффективности, возможно, что данные будут слишком запаздывать в некоторые периоды времени. Обеспечение максимального значения времени обработки относится к так называемому свойству реального времени и является обязательной функцией в области мультимедиа. В устройствах хранении информации для компьютеров увеличение средней эффективности является первостепенной задачей. Наихудшее значение не всегда поддерживалось низким, т. е. существовал большой разброс в характеристике времени обработки в устройствах хранения данных. Это положение противоречит требованиям, предъявляемым к устройствам хранения данных для мультимедиа. К тому же, в основных областях применения мультимедиа необходимо обеспечивать последовательный доступ к данным на физически разделенных участках (случайный доступ) с высокой скоростью. Напри мер, система типа "видео-по-требованию" (VOD) позволяет большому количеству зрителей вызывать и просматривать желаемые программы в удобное для них время. Для реализации такого режима необходимо параллельно обрабатывать запросы от многих зрителей и быстро подготавливать данные программ, которые зрители просматривают в данное время. По этой причине становится необходимым с высокой скоростью отслеживать источники видеосюжетов и т.д., хранимых во множестве местоположений на диске. В последние годы видеопрограммы и кинофильмы выпускаются с использованием не магнитных лент и пленок, а дисков. На магнитной ленте при вставке сцены продолжительностью в несколько секунд в положение, близкое к началу программы продолжительностью, например, один час, для предотвращения наложения записи необходимо сдвинуть к концу все видеоданные после этого положения вставки и поэтому перезаписать программу. В отличие от высокоскоростного воспроизведения аналоговых магнитных лент аудиокассет такая перезапись видеопрограмм требует затрат времени примерно одной программы, т.е. эффективность мала. С использованием диска, однако, так как возможен случайный доступ, имеется возможность разместить вставляемую часть в другое место на диске, перейти в это положение и выбрать вставленные данные во время воспроизведения, а затем возвратиться в исходную позицию и продолжить воспроизведение видеоданных. Известен способ, при котором каждую сцену (отрезок) программы размещают на различных участках диска и отслеживают их с высокой скоростью во время воспроизведения так, что кажется, что воспроизводится одна лента. Таким образом, возможно переключать сцены и изменять продолжительность воспроизведения, просто изменяя порядок отслеживания данных на диске. Эффективность такого редактирования чрезвычайно высока. Такой способ определяется как нелинейное редактирование. Отметим, что в этом случае также необходимо отслеживать физически разделенные участки на диске с высокой скоростью. Как видно в этих примерах, в областях применения мультимедиа чрезвычайно важно выбирать данные с высокой скоростью, в то же время отслеживая разобщенные данные на диске (это относится к так называемому случайному доступу), но для перемещения к разобщенным участкам требуется время для перемещения головки к требуемому цилиндру (группе дорожек дискового пакета), которое называется временем поиска, и время ожидания, когда диск повернется до положения, при котором в цилиндре появятся данные начала, которое называется временем задержки вращения. Эти интервалы времени относятся к так называемым накладным расходам на обеспечение доступа. Чем больше это время по сравнению с временем реальной выборки данных, тем большее время требуется для передачи данных с диска и поэтому тем ниже эффективность. Принимая время поиска для диска равным Ts и время задержки вращения равным Tr, накладные расходы на доступ к диску становятся равными Ts + Tr. Когда головка диска позиционирована в области данных и время реального доступа к данным равно Tt, эффективность по сравнению со случаем отсутствия перехода головки в конкретное положение становится низкой, как следует из уравнения (1): Tt/(Tt+Ts+Tr) А именно, по сравнению со случаем, когда данные на диске последовательно выбираются от начала до конца, в случае, когда выполняется случайный доступ при отслеживании данных в отдельных участках, необходимо иметь в виду, что эффективность снижается на эту величину. Соответственно, задачей, связанной с дисками для мультимедиа, является предотвращение снижения эффективности в режиме случайного доступа при одновременном сохранении свойства реального времени (для определения верхнего предела времени обработки и обеспечения работы с интервалом времени, равным или меньшим этому верхнему пределу). В последние годы были проведены исследования, связанные со способом обеспечения свойства реального времени при доступе к диску. Например, в работе D. Anderson, Y. Osawa and R. Govindan, "A File System for Continuous Media", ASM Transactions on Computer Systems, Vol. 10, N. 4, стр. 311-337, 1992 была сделана попытка увеличить эффективность системы посредством оптимизации соотношения между объемом буферной памяти для временного хранения данных, считанных с диска, и количеством данных, которые должны быть считаны во время одной выборки. При рассмотрении накладных расходов на выборку с диска для облегчения анализа предполагается, что возможны наихудшие значения для времени поиска и времени задержки вращения в каждом случайном доступе. А именно, время поиска от крайней внутренней окружности до наиболее крайней окружности принимается в качестве времени поиска, а время ожидания для одного полного оборота принимается в качестве времени задержки вращения. Конечно, если делается такое предположение, то оценка наихудшего значения времени обработки является наиболее надежной, но такая операция проводится в действительности не каждый раз, и поэтому оценка для наихудшего значения становится очень низкой по сравнению с эффективностью, которая может быть достигнута в реальном случае, и такая оценка имеет низкую значимость в качестве параметра конструирования. В работе V. Rangan и H.Vin "Efficient Storage Technique for Digital Continuous Multimedia", IEEE Transactions on Knowledge and Data Engineering, Vol. 5, N 4, стр. 564-573, 1993 исследовано, как при вставке видеофайла в множество сегментов и запоминания различных сегментов на различных участках определить длины сегментов и интервалов между сегментами так, чтобы сохранить свойство реального времени. Здесь, однако, при переходах между сегментами (во время случайной выборки) также предполагается, что наивысшие накладные расходы имеют место каждый раз таким же образом, как описано к работе Anderson, т.е. существует аналогичная проблема. Также имели место попытки поддержать наихудшее значение ниже по сравнению с указанными в этих исследованиях для обеспечения случайного доступа в реальном времени с более высокой эффективностью. В работах N. Reddy и J. Wyllie "Disk Scheduling in a Multimedia I/O System", ASM multimedia 93, стр. 225-233, 1993, J. Gemmel, J. Han, et.al., "Delay-Sensitive Multimedia on Disk", IEEE Multimedia 1994, стр. 56-57 и M.Chen, D.Kandlur, and P. Yu, "Optimization of the Grouped Sweeping Scheduling (GSS) with Heterogeneous Multimedia Streams", ASM multimedia 93, стр. 235-242, 1993 делались попытки снизить накладные расходы с помощью алгоритма планирования головки, называемого "SCAN". "Планирование головки" характеризует собой способ сокращения времени поиска путем изменения порядка доступа, когда необходим доступ к множеству участков на диске. SCAN- алгоритм, изображенный на фиг. 1, является алгоритмом, в котором заданное множество запросов ввода/вывода (#1, #2,...) сортируются в радиальном направлении диска и последовательно обрабатываются. Движения головки в противоположных направлениях, которые будут иметь место, если обработка выполняется в порядке прихода запросов ввода/вывода (#1, #2,. . . ), могут быть предотвращены и, в свою очередь, соответствующие интервалы времени поиска могут быть сокращены. Известно множество алгоритмов, используемых в качестве алгоритма планирования головки. Они подробно описаны, например, в Н. Deitel, "Operating Systems", Addison Wesley, стр. 360-372,1990. Работы Reddy, Gemmel и Chen основаны на предположении использования SCAN-алгоритма, поэтому дают возможность уменьшить время поиска. Соответственно, возможно понизить наихудшее значение для накладных расходов и обеспечить более высокую эффективность по сравнению с указанной в работах Anderson и Rangan. Однако, в SCAN-алгоритме можно уменьшить только время поиска. До сих пор не было сделано никаких упоминаний о сокращении времени задержки вращения. В работе Reddy предполагается, что для диска существует специальная функция, называемая механизмом доступа с нулевой латентностью (нулевым временем ожидания). Механизм доступа с нулевой латентностью характеризует собой способ, в котором данные последовательно считываются даже с середины данных в момент времени, когда головка достигает требуемой дорожки, а начальная часть данных, которая не была считана вовремя, считывается снова, когда диск делает один оборот, и этот участок возвращается. Соответственно, когда диск делает один оборот, требуемые данные могут быть надежно считаны и поэтому сумма задержки вращения и выборки данных становится равной времени одного оборота в качестве максимального значения. Однако, поскольку немного реальных дисков используют этот механизм, можно предположить, что способ, изложенный в работе Reddy, не пригоден для практического использования. С другой стороны, в работе Gemmel описан способ оценки накладных расходов, при котором всегда прибавляется максимальное значение для учета того, что задержка вращения является интервалом времени, в течение которого управление и предсказание невозможны. Такое решение надежно, но обуславливает большие потери, которые вызывают проблемы. В работе Chen задержка вращения трактуется как пренебрежимо малая составляющая коррекции времени, но это не является реалистичным. Например, в современных высокоскоростных дисках цикл вращения составляет 8,3 мс, в то время как при использовании SCAN-алгоритма максимальное значение времени поиска может быть уменьшено до 6 мс или менее. Поэтому задержка вращения является преобладающей. Кроме того, с учетом сопротивления воздуха и потребляемой двигателем электрической мощности и выделяемого в результате тепла трудно ожидать фундаментальных усовершенствований с точки зрения увеличения скорости вращения. Уменьшение задержки вращения является наибольшей проблемой, которая должна быть решена. Отметим, что в обычной файловой системе компьютеров уменьшение задержки вращения также является важным. В работе S. Ng, "Improving Disk Performance Via Latency Reduction", IEEE Transactions on Computers, Vol. 40, N 1, январь 1991, стр. 22-30, 1991 описан способ уменьшения среднего времени задержки вращения во время операции считывания с помощью способа подготовки копии данных, сдвинутых по фазе в направлении вращения и т.д. Однако, этот способ трудно применить для мультимедийных приложений, которые связаны с использованием огромного количества данных. Сущность изобретения Задачей настоящего изобретения является создание способа и устройства для управления доступом к диску для записи данных, обеспечивающих высокоскоростной случайный доступ и одновременно свойство реального времени посредством снижения времени поиска и времени задержки вращения. Такой способ управления доступом к диску для записи данных и устройство для осуществления способа являются предпочтительными для хранения мультимедийных данных, потребность в котором все время повышается. Поставленная задача решается тем, что способ управления доступом к диску для записи данных включает этапы определения сдвига, указывающего угловую разность в направлении вращения диска для записи данных между началами соседних блоков данных, который минимизирует время ожидания, обусловленное вращением диска для записи данных на среднем расстоянии перемещения головки при обращении головки к диску для записи данных, определения положения блока данных на диске для записи данных на основании, по меньшей мере, определенного сдвига, планирования порядка множества входных запросов доступа к диску для записи данных для минимизации величины перемещения головки при обращении головки к диску для записи данных, и доступа к диску для записи данных с помощью головки на основании результатов планирования. Кроме того, в способе управления доступом к диску для записи данных, согласно настоящему изобретению, предпочтительно определяют положения блока данных на диске для записи данных на основании, в дополнение к определенному сдвигу, интервала, указывающего угловую разность между началом и окончанием одного и того же блока данных. Кроме того, в способ управления доступом к диску для записи данных, согласно настоящему изобретению, предпочтительно дополнительно включают этапы определения комбинаций данных, каждая из которых представляет собой комбинацию сдвига и интервала, для множества блоков данных, и селективного использования комбинаций данных в соответствии с положением каждого блока данных на диске для записи данных. Кроме того, в способе управления доступом к диску для записи данных, согласно настоящему изобретению, размер блока данных изменяют так, что интервал, указывающий угловую разность между началом и окончанием одного и того же блока данных, является постоянным по всей области от внешнего края до внутреннего края диска для записи данных. Кроме того, в способе управления доступом к диску для записи данных, согласно настоящему изобретению, предпочтительно сдвиг определяют в соответствии с изменением интервала, указывающего угловую разность между началом и окончанием одного и того же блока данных, на основании разности радиусов дорожек записи. Кроме того, в способе управления доступом к диску для записи данных, согласно настоящему изобретению, предпочтительно на этапе планирования изменяют порядок множества запросов на доступ к диску так, что они распределяются в порядке, начиная с ближайшего к головке, при движении головки от текущей позиции по направлению к позиции на внутренней дорожке диска для записи данных, а этап определения положения блока данных на диске для записи данных осуществляют на основании дополнительно к сдвигу интервала, указывающего угловую разность между началом и окончанием одного и того же блока данных так, что разность между временем задержки вращения Tr, в данном случае - временем ожидания, обусловленного вращением диска для записи данных Td(L) и временем поиска Ts(L) вблизи среднего расстояния поиска La мала по сравнению с периодом вращения, при этом: Td(L) = (L








Lt - максимальное значение расстояния между положениями доступа при упорядочении запросов доступа, выраженное через количество цилиндров,
N - количество обращений, которые могут быть одновременно обработаны, и
m - выбрано так, чтобы стать минимальным в диапазоне, где Td(L) превышает время поиска Ts(L) на расстоянии L поиска. Кроме того, в способе управления доступом к диску для записи данных, согласно настоящему изобретению, предпочтительно на этапе планирования изменяют порядок множества запросов на доступ к диску для записи данных для их упорядочивания в процессе появления при перемещении головки от текущего положения по направлению к внутренней дорожке или внешней дорожке диска для записи данных, а этап определения положения блока данных на диске для записи данных осуществляют на основании, дополнительно к сдвигу интервала, указывающего угловую разность между началом и окончанием одного и того же блока данных так, чтобы время ожидания, обусловленное вращением диска для записи данных Td(L) было всегда больше времени поиска Ts(L), и разность между временем Td(L) и временем Ts(L) стала малой по сравнению с периодом вращения диска для записи данных, причем:
Td(L) = (L





где L - расстояние поиска, выраженное через количество цилиндров,
Bc - количество блоков данных в одном цилиндре,



Td(L) = (L






La=Lt/(N-1), (6)
где L - расстояние поиска, выраженное через количество цилиндров,
Bc - количество блоков данных в одном цилиндре,



Lt - максимальное значение расстояния между положениями доступа при упорядочении запросов доступа, выраженное через количество цилиндров,
N - количество обращений, которые могут быть одновременно обработаны, и
m - выбрано так, чтобы стать минимальным в диапазоне, где Td(L) превышает время поиска Ts(L) на расстоянии L поиска. При этом в устройстве управления доступом к диску для записи данных, согласно настоящему изобретению, средство планирования предпочтительно выполнено с возможностью изменения порядка множества запросов на доступ к диску для записи данных для их упорядочивания в порядке появления при перемещении головки от текущего положения по направлению к позиции либо на внутренней дорожке, либо на внешней дорожке диска для записи данных, а средство упорядочения блоков данных выполнено с возможностью определения положения блоков данных на диске для записи данных на основании дополнительно к сдвигу интервала так, чтобы время ожидания, обусловленного вращением диска для записи данных Td(L), заданное нижеследующим уравнением, было всегда больше времени поиска Ts(L), а разность между временем Td(L) и временем Ts(L) стала малой по сравнению с периодом вращения диска для записи данных, при этом:
Td(L) = (L





где L - расстояние поиска, выраженное через количество цилиндров,
Bc - количество блоков данных в одном цилиндре,



Td(L) = (L






La=Lt/(N-1), (9)
где L - расстояние поиска, выраженное через количество цилиндров,
Bc - количество блоков данных в одном цилиндре,



Lt - максимальное значение расстояния между положениями доступа при упорядочении запросов доступа, выраженное через количество цилиндров,
N - количество обращений, которые могут быть одновременно обработаны, и
m - выбрано так, чтобы стать минимальным в диапазоне, где Td(L) превышает время поиска Ts(L) на расстоянии L поиска. При этом в устройстве управления доступом к диску для записи данных средство планирования предпочтительно выполнено с возможностью изменения порядка множества запросов на доступ к диску для записи данных так, чтобы они были упорядочены в порядке появления, когда головка перемещается от текущего положения по направлению к внутренней дорожке или внешней дорожке диска для записи данных, а устройство распределения блоков данных выполнено с возможностью определения положения блоков данных на диске для записи данных, дополнительно к сдвигу, на основании интервала, указывающего угловую разность между началом и окончанием одного и того же блока данных так, чтобы время ожидания, обусловленное вращением диска для записи данных Td(L), заданное нижеследующим уравнением, было всегда больше времени поиска Ts(L), и разность между временем Td(L) и временем Ts(L) стала малой по сравнению с периодом вращения диска для записи данных, где
Td(L) = (L





где L - расстояние поиска, выраженное через количество цилиндров,
Bc - количество блоков данных в одном цилиндре,



Указанные и другие задачи и особенности настоящего изобретения станут более ясными из последующего описания предпочтительных вариантов воплощения, приведенных со ссылками на чертежи, на которых представлено следующее:
фиг. 1 - схематичное представление для пояснения предшествующего уровня техники,
фиг. 2 - блок-схема конфигурации устройства для управления доступом к диску для записи данных в соответствии с первым вариантом воплощения настоящего изобретения,
фиг. 3 - блок-схема последовательности операций при обработке в устройстве распределения блоков, изображенном на фиг. 2,
фиг. 4 - блок-схема последовательности операций при обработке в устройстве планирования, изображенном на фиг. 2,
фиг. 6 - схематичное представление, поясняющее способ упорядочения блоков на диске устройством распределения блоков,
фиг. 7 - диаграмма, поясняющая содержание карты распределения блоков,
фиг. 8 - диаграмма, поясняющая содержание обработки на этапе S3, изображенном на фиг.3,
фиг. 9 - график, поясняющий содержание обработки на этапе S3, изображенном на фиг.3,
фиг. 10 - график, поясняющий накладные расходы в случае, когда учитываются и поиск, и задержка вращения,
фиг. 11A, 11B и 11C - диаграммы, поясняющие возможный пример распределения обращений на диске,
фиг. 12 - график, иллюстрирующий накладные расходы для обычного SCAN- алгоритма,
фиг. 13 - график, поясняющий соотношение между расстоянием L поиска и задержкой в случае использования возрастающей выпуклой функции, огибающей пилообразную функцию,
фиг. 14 - диаграмма, поясняющая обработку в устройстве распределения блоков устройства управления доступом к диску для записи данных согласно второму варианту воплощения настоящего изобретения,
фиг. 15 - блок-схема последовательности операций, поясняющая обработку в устройстве распределения блоков в устройстве управления доступом к диску для записи данных, изображенном на фиг. 14,
фиг. 16 - диаграмма, поясняющая содержание карты распределения блоков в устройстве управления доступом к диску для записи данных, изображенном на фиг. 13. Предпочтительные варианты осуществления изобретения
Ниже приводится объяснение способа и устройства управления доступом к диску для записи данных согласно вариантам воплощения настоящего изобретения. Первый вариант воплощения
Фиг.2 изображает блок-схему конфигурации устройства для управления доступом к диску для записи данных согласно настоящему варианту воплощения изобретения. Устройство управления доступом к диску для записи данных, согласно настоящему варианту воплощения, реализуется работой программного обеспечения, например, в компьютере. Каждый блок, изображенный на фиг.2, представляет собой основной программный модуль или основную структуру данных. Устройство 1 распределения блоков (средство упорядочения) определяет, как данные упорядочены на диске 5 на основании заданного параметра 10 формата. Диск 5 может быть, например, магнитным диском, магнито-оптическим диском или жестким диском. Параметр 10 формата включает в себя размер первого блока данных, среднее расстояние La перемещения головки при выполнении SCAN-планирования, функцию Ts(L) времени поиска используемого дисковода и физический формат диска 5. Среднее расстояние La перемещения головки определяется следующим уравнением (8), исходя из общего количества цилиндров Lt диска и количества N обращений, обработанных посредством одного сканирования. La=Lt/(N-1) (8)
Время поиска Ts(L) для дисковода является функцией расстояния L поиска (количества цилиндров). Его значение определяется механическими характеристиками используемого дисковода. Пример изображен на фиг.5. Насколько много запросов обрабатываются одновременно при сканировании, определяется особенностями системы, использующей этот диск, требуемой эффективностью, величиной буферной памяти, которая может быть использована, и т.д. Чем больше количество N запросов на обращение, которые должны быть сканированы вместе, тем более высокую эффективность случайного доступа должен иметь диск, но существует побочный эффект, заключающийся в том, что время отклика увеличивается, когда величина требуемой буферной памяти увеличивается. Эти параметры 10 формата определяются центральным процессором (не изображен), имеющим управляющую программу, которая управляет всей системой, и эти параметры 10 формата подаются в устройство 1 распределения блоков. В примере, в котором данный вариант воплощения используется для нелинейного редактирования, устройству 1 распределения блоков были заданы N = 10, a La = 300. Кроме того, размер первого блока данных соответствует одному листу данных образа и составляет приблизительно 700 К. (килобайт) в случае использования вещающими станциями формата CCIR-601 и т.д. Конечно, эти количественные характеристики могут быть произвольно установлены в соответствии с назначением и различными специальными техническими условиями. Устройство 1 распределения блоков на основании заданного параметра 10 формата определяет, в какую позицию на диске 5 должен быть помещен каждый блок. В данном примере один блок равен одному кадру изображения, но, конечно, основная концепция аналогична как при работе с данными, полученными путем деления MPEG-данных или другого сжатого изображения на подходящие длины, так и с аудиоданными. К диску 5 может быть осуществлен доступ к каждой области, которая обычно называется "сектором". Один сектор обычно имеет размер от 512 байт до приблизительно 4 К. Область в виде тороида, в которой эти сектора образуют окружность, называют "дорожкой". Далее, цилиндрическая область, содержащая группу одинаковых дорожек из перекрывающегося множества магнитных сред, называется "цилиндром". Один блок видео- или аудиоданных обычно больше одного сектора, поэтому устройство 1 распределения блоков назначает множество секторов для каждого блока. Фиг.5 изображает простой пример для случая, когда существует одна магнитная среда (носитель информации). Заштрихованная часть на фиг.6, т.е. полная окружность дорожки "1", и сектора от "0" до "6" дорожки "2" соответствуют одному блоку. В этом примере, поскольку существует только один носитель, то термины "дорожка" и "цилиндр" имеют одно и то же значение, но в случае дисковода, имеющего множество магнитных дисков, при полностью используемых всех частях одного цилиндра блоки назначаются с возможностью использования соседних цилиндров. Распределение на сектора выполняется для всех блоков. Результат записывается в карту 3 распределения блоков, после чего работа устройства 1 распределения блоков заканчивается. Устройство 1 распределения блоков обозначает позицию сектора путем установки номера цилиндра, номера носителя (который по счету слой носителя) и номера сектора. Однако, в дисководах спецификации SCSI (ANSI интерфейс малой компьютерной системы), которые становятся наиболее популярны в последние годы, последовательные номера (локальные номера секторов, называемые в SCSI "адресами логических блоков", здесь называются номерами логических секторов так, чтобы избежать путаницы с блоками видео- и аудиоданных) присваиваются всем секторам в дисководе и используются для доступа к данным. По этой причине соответствие между номерами логических секторов, определенное с помощью диска, и физическими адресами, т. е. номерами цилиндров, номерами среды и номерами секторов, предварительно запоминается в таблице 7 физических адресов. Устройство 1 распределения блоков преобразует требуемый физический адрес в номер логического сектора, определенный SCSI, обращаясь к таблице 7, и вносит его в карту 3 распределения блоков. Фиг. 7 изображает пример карты распределения блоков. Информация, соответствующая блоку "0", соответствует заштрихованной части на фиг.6. С другой стороны, планировщик 2 работает следующим образом. Сначала центральный процессор для управления всей системой определяет параметр 20 планирования и выдает параметр 20 планирования в планировщик 2. Параметр 20 планирования включает в себя константу N, указывающую, сколько запросов на доступ обрабатывается за одно сканирование. Когда оператор дает команду начать воспроизведение изображения движущейся картинки, записанной на диске 5, центральный процессор, имеющий подходящую управляющую программу, выдает запросы на доступ к блокам, в которых изображение, образующее движущееся изображение картинки, хранится для каждого изображения. Эти запросы 40 на доступ сохраняются в буфере 4 запросов на доступ. Планировщик 2 последовательно извлекает N номеров запросов 40 на доступ, хранимых в буфере 4 запросов на доступ, из тех запросов на доступ, которые поступили раньше, находит на диске 5 положение данных, соответствующих этим запросам, обращаясь к карте 3 распределения блоков, изменяет порядок запросов на доступ так, чтобы количество перемещений головки стало минимальным, и генерирует команду на доступ к диску 5. Команда на доступ сделана совпадающей с внешним интерфейсом дисковода и поэтому преобразуется в SCSI протокол дисководом 6 SCSI, а затем передается на диск 5. Данные, считанные с диска 5, временно запоминаются в буфере 8 данных и затем передаются на видеоинтерфейс устройства. Когда оператор дает команду начать запись изображения движущейся картинки, записанной на диске 5, центральный процессор, имеющий подходящую управляющую программу, выдает запросы на доступ к блоку, в котором изображение, образующее изображение движущейся картинки, хранится для каждого изображения. Эти запросы 40 на доступ сохраняются в буфере 4 запросов на доступ. В это же время данные 80 изображения, образующие движущуюся картинку, передаются из видеоинтерфейса (не изображен) в буфер 8 данных, и эти данные 80 изображения временно запоминаются в буфере 8 данных. Планировщик 2 последовательно извлекает N номеров запросов 40 на доступ, хранимых в буфере 4 запросов на доступ, из тех запросов на доступ, которые поступили раньше. Затем планировщик 2 находит на диске 5 положение данных, соответствующих этим запросам, обращаясь к карте 3 распределения блоков. К тому же планировщик 2 изменяет порядок запросов на доступ так, чтобы количество перемещений головки стало минимальным, и генерирует команду на доступ к диску 5. Команда на доступ согласована с внешним интерфейсом дисковода и поэтому преобразуется в SCSI протокол дисководом 6 SCSI, а затем передается на диск 5. Ниже приводится подробное описание работы устройства 1 распределения блоков. В качестве параметра 10 формата, изображенного на фиг.2, когда заданы размер одного блока, среднее расстояние La перемещения головки при выполнении SCAN-планирования, функция Ts(L) времени поиска используемого дисковода, физический формат диска 5 (количество цилиндров, количество секторов на одной дорожке и количество сред, составляющих цилиндр), то устройство 1 распределения блоков определяет положение каждого блока на диске 5 с помощью этапов S1 - S5 процедуры, изображенной на фиг.3. На этапе SI вычисляется, сколько блоков изображения имеется в одном цилиндре (Bc). Общее количество секторов в одном цилиндре получается умножением количества секторов на дорожке на количество сред. Если это число разделить на количество секторов, необходимых для хранения одного блока, получается значение Bc. Интервал





Td(L) = (L






где L - расстояние поиска, измеряемое в количестве цилиндров,
Bc - количество блоков данных в одном цилиндре,



m - любое целое число, при котором Td(L) становится положительным. Фиг.8 поясняет уравнение (9) на диске. Предполагается (фиг.8), что обращение к блоку "0" только что завершено. Предполагается, что головка расположена в направлении угла 70, если смотреть из центра. Теперь при необходимости доступа к блоку "0" опять необходимо ожидать до тех пор, пока диск повернется точно на величину интервала







Td(L) = (L





Последующие этапы S3-2, S3-3 и S3-4 являются этапами для выбора сдвига


(1) позади распределенного блока и
(2) в области, в которой сектор, имеющий угловую разность от начала 0-го блока, ближайшую к N-му, определяется в качестве начального. Ниже приведено пояснение случая наихудших накладных расходов в способе управления доступом к диску для записи данных согласно рассматриваемому варианту осуществления. В общем случае запрос 40 на доступ генерируется по отношению ко всем позициям на диске 5. Позиции, обработанные за одно сканирование, имеют неравномерности в распределении, как изображено на фиг. 11A или 11B, и наоборот, распределены равномерно, как изображено на фиг. 11C. В этом примере головка перемещается в соответствии с шестью запросами 40 на доступ, поэтому при этом реализуются пять процедур случайного доступа и соответствующие им накладные расходы. Общая сумма накладных расходов по отношению к этим пяти случайным доступам соответствует наихудшему случаю, если все доступы равномерно распределены, когда график функции накладных расходов имеет выпуклую вверх форму (фиг. 11C). Когда имеются неравномерности в распределении, общая сумма накладных расходов становится меньше, чем в данном случае. Другими словами, когда накладные расходы на среднем расстоянии перемещения La головки генерируются повторно, общая сумма накладных расходов становится наихудшей (наибольшей). График Td(L) на фиг. 10 является пилообразной функцией. Если Td(L) заменить на функцию, имеющую выпуклую вверх форму и огибающую ее сверху, то приведенная выше теория в основном выполняется. Пример такой функции приведен на фиг. 12. Т.е. наихудшие накладные расходы на один доступ представляют собой значение, полученное считыванием значения Td(L) в положении, когда расстояние равно La на графике, изображенном на фиг. 10 (Tmax на чертеже). Как отмечено выше, это является аппроксимацией, но как в примере на фиг. 10, функция Td(L) и огибающая ее сверху функция обычно совпадают друг с другом вблизи La, поэтому можно считать, что в действительности ошибка отсутствует. Далее, аппроксимация осуществляется со стороны надежной оценки (т.е. при условии, когда оценка накладных расходов превышает
реальное их значение), поэтому нет риска оценки наихудшего значения в меньшей степени, чем исходное значение. На этапе S3, изображенном на фиг.3, сдвиг выбран так, что одна из групп прямых линий для задержки вращения, заданных уравнением (9), расположены в положении выше, чем функция Ts(L) времени поиска, но максимально близко к ней. Таким образом, Td(L) может иметь меньшее значение вблизи расстояния La и, следовательно, наихудшие накладные расходы Тmax могут быть уменьшены. Фиг. 12 иллюстрирует накладные расходы обычного SCAN-алгоритма. В обычном SCAN-алгоритме общая сумма накладных расходов также становится наихудшей, когда обращения равномерно распределены. Однако, в отличие от рассматриваемого варианта осуществления, не учитывается задержка вращения, поэтому даже после того, как операции поиска завершены, должно учитываться, что в наихудшем случае генерируется задержка вращения для одного оборота. По этой причине значение, полученное суммированием цикла Trot одного оборота и времени поиска Ts(La) при La, характеризует собой наихудшие накладные расходы. Как видно из сравнения фиг. 12 и фиг. 10, эта величина значительно превышает значение, полученное при использовании способа согласно рассматриваемому варианту осуществления. В экспериментах заявителя было подтверждено, что наихудшие накладные расходы в рассматриваемом варианте составляют почти половину по сравнению с их величиной в обычном SCAN-алгоритме. Как объяснялось выше, в устройстве управления доступом к диску для записи данных, согласно данному варианту осуществления, посредством подходящего выбора сдвига и интервала возможно уменьшить накладные расходы Td(L) при среднем расстоянии La перемещения головки до самого низкого уровня, и время задержки вращения может быть уменьшено таким же образом. На блок-схеме, изображенной на фиг.3, размер блока имел заданное фиксированное значение, но в соответствии с задачей размер блока может быть выбран в некотором диапазоне. В этом случае и интервал


Планировщик 2, описанный выше применительно к первому воплощению, перемещается к крайней внешней позиции доступа в начале следующей операции сканирования. А именно, когда выполняется последнее обращение на этапах S12-4 и S12-5 на фиг.4, головка выполняет обращение к крайней внутренней позиции из N позиций доступа. При первом обращении цикла обработки следующих N обращений имеет место перемещение к внешнему цилиндру, имеющему наименьший номер цилиндра. При этом перемещении реализуются операция поиска наибольшей длины от крайней внутренней окружности к крайней внешней окружности и задержка вращения на один оборот, что соответствует наихудшему случаю. Так как это имеет место для каждых N обращений и так как выборка данных не может выполняться в течение этого времени, оно должно быть добавлено к общей сумме накладных расходов всей операции сканирования. Конечно, эффективность снижается на эту величину. Конечно, возможно обращаться к диску даже во время перемещения от внутренней окружности по направлению к внешней окружности, но, так как направление перемещения головки становится реверсивным, первый член уравнения (15), т. е. знак сдвига, меняется на противоположный. По этой причине оптимальные сдвиг и интервал в случае перемещения от внешней окружности к внутренней окружности не всегда становятся подходящими параметрами для перемещения в обратном направлении. Это является причиной снижения эффективности, когда головка движется в обратном направлении. Устройство для управления доступом к диску для записи данных согласно второму воплощению настоящего изобретения, которое будет описано ниже, позволяет решить эту проблему и обеспечивает способ выполнения высокоскоростной передачи данных, даже когда головка возвращается от внутренней окружности к внешней окружности. Сначала устройство 1 распределения блоков разделяет цилиндры на цилиндры 50, обозначенные штриховкой, используемые при выполнении сканирования от внешней стороны к внутренней, как изображено на фиг. 14. На фиг. 14 цилиндры 50, обозначенные буквами F, используются при выполнении сканирования от внешней стороны к внутренней, а цилиндры 50, обозначенные буквами В, используются при выполнении сканирования от внутренней стороны к внешней. На фиг. 14 цилиндры разделяются на группы из двух цилиндров, но количество цилиндров в группе этим числом не ограничивается. Цилиндры могут быть разделены на группы из подходящего количества цилиндров. Таким же образом, как в устройстве управления доступом к диску для записи данных согласно описанному выше первому воплощению, обработка на этапах S4 и S5, изображенных на фиг.3, после определения сдвига и интервала согласно этапу S1 на фиг.3 изменяется, как показано на фиг. 15. Как показано на фиг. 15, на этапе S31 указатель физического адреса устанавливается в начальное состояние таким же способом, как в первом варианте. Затем соответствующие блоки распределяются на диск на этапе S32. Этап 32 представляет собой цикл, повторяемый для всех блоков. На этапе S32-1 проверяется, принадлежит ли целый блок областям F или областям В на основании физического адреса блока во время обработки. Этап S32-2 является разветвлением, основанным на результате этой проверки. Если весь блок принадлежит областям F, то выполняются этапы S32-3 - S32-7. При этом этап S32-3 соответствует этапу S5-1 на фиг.3 и является этапом проверки соответствующего номера логического сектора с использованием таблицы физических адресов, в то время как на этапе S32-4 выполняется операция записи в карту 3 распределения блоков тем же способом, что и на этапе S5-2 на фиг.3. По сравнению с картой 3 распределения блоков в первом варианте, изображенной на фиг.7, в карте 3 распределения блоков в данном варианте добавляется флаг, указывающий, находится ли этот блок в областях F или в областях В. Эта ситуация изображена на фиг. 16. Этап S32-5 является этапом записи F в этой части. Если на этапе S32-2 определено, что блок не принадлежит полностью областям F, размещение по этому физическому адресу не выполняется и отыскивается физический адрес, который полностью принадлежит областям F. На этапе S32-6 определяется следующий физический адрес исходя из сдвига и интервала и далее проверяется, каким областям он принадлежит. На этапе S32-7 определяется, считана ли внутренняя окружность. Если нет, программа обработки переходит к этапу S32- 1, после которого на этапе S32-2 опять выполняется проверка. Таким образом, повторяются попытки получения физического адреса, принадлежащего целиком областям F. Данный адрес назначается блоку. Например, как показано на фиг. 16, в случае системы, выполненной в соответствии с первым вариантом, следующий блок N 5 был размещен с физическим адресом (1/5/8), но вторая половина блока накладывается на цилиндр N 2. Цилиндр N 2 является областью В, поэтому эти области не назначаются, и затем отыскивается следующий адрес, который может быть назначен. Указатель физического адреса последовательно получает приращения, и физический адрес (4/2/0) назначается блоку N 5. Как и в первом варианте, в способе назначения блоков без пропуска средней части и в способе для назначения блоков с пропуском средней части, как в данном варианте, соотношение между расстоянием (количеством цилиндров) радиального направления и величиной сдвига должно быть постоянными, поэтому используется способ назначения, как объяснено выше. Это является причиной, почему использование не начинается с начала (4/0/0) цилиндра N4. Описанная выше обработка повторяется до тех пор, пока физический адрес не достигнет крайней внутренней окружности. На этапах S33 - S36 выполняется аналогичная обработка по отношению к областям В. Началом областей В является цилиндр N 2, как изображено на фиг. 14, поэтому указатель физического адреса устанавливается равным этому адресу на этапе S33. Затем знак сдвига изменяется на обратный на этапе S34. К областям В осуществляется обращение от внутренней окружности по направлению к внешней окружности, поэтому величина перемещения цилиндров становится отрицательной. Поэтому, когда в соответствии с этим изменяется знак сдвига, получается оптимальный сдвиг для перемещения головки от внутренней части к внешней. Этап S35 является этапом реальной записи данных на карту 3 распределения блоков. Эта часть обработки аналогична этапам S32-1 - S32-6. Отметим, однако, что существует отличие от этапов S32-1 - S32-7, заключающееся в следующем:
(1) данные записываются в карту распределения блоков, только когда целый блок находится в областях В. В противном случае делаются другие попытки с помощью нового физического адреса,
(2) В записывается в карту распределения блоков. Наконец, на этапе S36 определяется, все ли блоки, подлежащие обработке, обработаны. Если нет, процесс обработки возвращается на этап S31. Если все подлежащие обработке блоки обработаны, то обработка останавливается. Фиг. 16 соответствует случаю, когда всего 5012 блоков распределены в области F. Поэтому номер блока из областей В начинается с 5013 и назначение блоков повторяется до тех пор, пока головка снова не достигнет крайней внутренней окружности. Так как устройство 1 распределения блоков имеет заданную конфигурацию, описанную выше, планировщик 2 выбирает только запросы для обращения к областям В из буфера запросов адреса для планирования, когда головка перемещается в направлении от внешней окружности к внутренней окружности, и выбирает только запросы для обращения к областям В из буфера запросов адреса для планирования, когда эта операция полностью завершена и головка перемещается от внутренней окружности к внешней окружности. Благодаря этому, вне зависимости от направления перемещения головки, задержка вращения может быть всегда снижена до минимального уровня. В первом варианте воплощения для головки, достигшей внутренней окружности, при возвращении к внешней окружности имело место время задержки, однако во втором варианте воплощения не существует такого времени задержки, поэтому эффективность диска повышается. В первом варианте воплощения было упомянуто, что когда один большой блок располагался на множестве дорожек и секторов, эффективность была хорошей, если был задан другой сдвиг, учитывающий соответствующие интервалы времени. В данном втором варианте воплощения возможно использование аналогичной методики. В данном втором варианте, когда головка перемещается от внутренней окружности по направлению к внешней окружности, она последовательно перемещается от внутреннего цилиндра к внешнему цилиндру, также при обращениях внутри блока, поэтому сдвиг для получения времени, необходимого для движения цилиндра, может быть задан в обратном направлении для перемещения от внешней окружности по направлению к внутренней окружности. Отметим, что, как изображено на фиг. 14, задавая цилиндр 50 и цилиндр 51 так, чтобы они были распределены от крайней внутренней окружности к крайней внешней окружности на диске, эффективность обращения к диску может быть дополнительно увеличена. Как указано выше, в соответствии со способом управления доступом к диску для записи данных, согласно настоящему изобретению, и устройством для его реализации, накладные расходы для диска, т.е. сумма времени поиска и времени задержки вращения, могут быть снижены и может быть обеспечено их максимальное значение на низком уровне. Кроме того, в соответствии со способом управления доступом к диску для записи данных, согласно настоящему изобретению, и устройством для его реализации, задавая сдвиг, соответствующий направлению перемещения головки для каждой области, возможно снизить накладные расходы независимо от направления перемещения головки. Должно быть понятно, что во время обращения или после интервала времени обращения головки к диску определяется планирование для следующего перемещения доступа. Когда начинается это следующее обращение, головка перемещается к начальной позиции, определенной планированием для такого следующего перемещения головки для обращения. В случае первого перемещения головки для обращения после включения устройства, изображенного на фиг.2, головка перемещается в начальную позицию, определенную первой операцией планирования после включения питания. Хотя настоящее изобретение было описано со ссылками на предпочтительные варианты воплощения, оно не ограничивается этими вариантами воплощения и включает в себя все модификации, очевидные для специалистов.
Формула изобретения
Td(L) = (L






La = Lt/(N-1),
где L - расстояние поиска, выраженное через количество цилиндров;
Вс - количество блоков данных в одном цилиндре;



Lt - максимальное значение расстояния между положениями доступа при упорядочении запросов доступа, выраженное через количество цилиндров;
N - количество обращений, которые могут быть одновременно обработаны;
m - выбрано так, чтобы стать минимальным в диапазоне, где Td(L) превышает время поиска Ts(L) на расстоянии L поиска. 7. Способ по п.1, отличающийся тем, что на этапе планирования изменяют порядок множества запросов на доступ к диску для записи данных для их упорядочения в процессе появления при перемещении головки от текущего положения по направлению к внутренней дорожке или внешней дорожке диска для записи данных, а этап определения положения блока данных на диске для записи данных осуществляют на основании, дополнительно к сдвигу, интервала, указывающего угловую разность между началом и окончанием одного и того же блока данных так, чтобы время ожидания, обусловленное вращением диска для записи данных Td(L), было всегда больше времени поиска Ts(L) и разность между временем Td(L) и временем Ts(L) стала малой по сравнению с периодом вращения диска для записи данных, причем
Td(L) = (L





где L - расстояние поиска, выраженное через количество цилиндров;
Вс - количество блоков данных в одном цилиндре;



Td(L) = (L






La = Lt/(N-1), (2)
где L - расстояние поиска, выраженное через количество цилиндров;
Вс - количество блоков данных в одном цилиндре;



Lt - максимальное значение расстояния между положениями доступа при упорядочении запросов доступа, выраженное через количество цилиндров;
N - количество обращений, которые могут быть одновременно обработаны;
m - выбрано так, чтобы стать минимальным в диапазоне, где Td(L) превышает время поиска Ts(L) на расстоянии L поиска. 16. Устройство по п.10, отличающееся тем, что средство планирования выполнено с возможностью изменения порядка множества запросов на доступ к диску для записи данных для их упорядочения в порядке появления при перемещении головки от текущего положения по направлению к позиции либо на внутренней дорожке, либо на внешней дорожке диска для записи данных, а средство упорядочения блоков данных выполнено с возможностью определения положения блоков данных на диске для записи данных на основании, дополнительно к сдвигу интервала, так, чтобы время ожидания, обусловленного вращением диска для записи данных Td(L), заданное нижеследующим уравнением, было всегда больше времени поиска Ts(L), а разность между временем Td(L) и временем Ts(L) стала малой по сравнению с периодом вращения диска для записи данных, при этом
Td(L) = (L





где L - расстояние поиска, выраженное через количество цилиндров;
Вс - количество блоков данных в одном цилиндре;



Td(L) = (L






La = Lt/(N-1), (2)
где L - расстояние поиска, выраженное через количество цилиндров;
Вс - количество блоков данных в одном цилиндре;



Lt - максимальное значение расстояния между положениями доступа при упорядочении запросов доступа, выраженное через количество цилиндров;
N - количество обращений, которые могут быть одновременно обработаны;
m - выбрано так, чтобы стать минимальным в диапазоне, где Td(L) превышает время поиска Ts(L) на расстоянии L поиска. 31. Устройство по п.25, отличающееся тем, что средство планирования выполнено с возможностью изменения порядка множества запросов на доступ к диску для записи данных так, чтобы они были упорядочены в порядке появления, когда головка перемещается от текущего положения по направлению к внутренней дорожке или внешней дорожке диска для записи данных, а устройство распределения блоков данных выполнено с возможностью определения положения блоков данных на диске для записи данных, дополнительно к сдвигу, на основании интервала, указывающего угловую разность между началом и окончанием одного и того же блока данных так, чтобы время ожидания, обусловленное вращением диска для записи данных Td(L), заданное нижеследующим уравнением, было всегда больше времени поиска Ts(L), и разность между временем Td(L) и временем Ts(L) стала малой по сравнению с периодом вращения диска для записи данных, где
Td(L) = (L





где L - расстояние поиска, выраженное через количество цилиндров;
Вс - количество блоков данных в одном цилиндре;



РИСУНКИ
Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7, Рисунок 8, Рисунок 9, Рисунок 10, Рисунок 11, Рисунок 12, Рисунок 13, Рисунок 14, Рисунок 15, Рисунок 16