Содержание к диссертации
Введение
Глава 1. Принципы организации файловых систем серверов мультимедиа 13
1.1. Методы обеспечения непрерывного воспроизведения потоковых данных 13
1.1.1. Методы нахождения количества отсчетов, считываемых за один цикл 17
1.1.2. Методы дискового планирования 18
1.1.3. Алгоритмы управления допуском 22
1.2. Методы размещения данных 25
1.2.1. Методы организации дискового пространства 25
1.2.2. Методы размещения файлов на нескольких дисках 28
1.3. Парадигмы файловых систем 32
1.4. Методы построения мультимедийных файловых систем 34
1.4.1. Файловые системы раздельной архитектуры 35
1.4.2. Файловые системы интегрированной архитектуры 36
1.5. Показатели эффективности сервера мультимедиа 41
1.5.1. Показатели качества обслуживания 41
1.5.2. Характеристики оперативности и производительности 43
1.6. Выводы 46
Глава 2. Исследование методов хранения и доступа к текст ориентированным данным 48
2.1. Параметры и характеристики моделирования 50
2.2. Разработка моделей для метода поблочного чередования данных 54
2.2.1. Аналитические модели для алгоритмов дискового планирования БСБЗ и ЬООК 54 2.2.2. Проверка адекватности аналитических моделей 62
2.3. Исследование влияния длины блока на эффективность дисковой подсистемы 66
2.4. Разработка моделей для метода экстентного размещения данных 70
2.4.1. Аналитические модели для алгоритмов дискового планирования FCFShLOOK 70
2.4.2. Проверка адекватности аналитических моделей 71
2.5. Сравнительный анализ методов хранения и доступа к текст- ориентированным данным 75
2.5.1. Равномерное распределение нагрузки по набору дисков 75
2.5.2. Неравномерное распределение нагрузки по набору дисков 80
2.6. Выводы 84
Глава 3. Исследование методов хранения и доступа к потоковым данным 86
3.1. Параметры и характеристики моделирования 88
3.2. Разработка моделей для метода размещения файлов согласно постоянному шагу данных 92
3.2.1. Аналитическая модель для циклического метода доступа и алгоритма дискового планирования LOOK 92
3.2.2. Проверка адекватности аналитической модели 97
3.3. Исследование влияния длины блока на эффективность дисковой подсистемы 101
3.4. Разработка моделей для метода размещения файлов согласно постоянному шагу времени 107
3.4.1. Аналитическая модель для циклического метода доступа и алгоритма дискового планирования LOOK 107
3.4.2. Проверка адекватности аналитической модели 109
3.5. Сравнительный анализ методов хранения и доступа к потоковым данным 112
3.6. Выводы 117
Глава 4. Разработка и исследование метода дискового планирования для серверов мультимедиа интегрированной архитектуры 118
4.1. Принципы организации методов дискового планирования 120
4.1.1. Дисциплины обслуживания запросов в течение цикла 122
4.1.2. Дисциплины ограничения числа запросов, выбираемых на обслуживание 125
4.1.3. Дисциплины обслуживания очереди запросов 127
4.2. Исследование методов дискового планирования 128
4.2.1. Сравнительный анализ методов дискового планирования 129
4.2.2. Анализ влияния длительности периода на производительность подсистемы ввода/вывода 133
4.2.3. Анализ и аналитическое описание границы области допустимой нагрузки 138
4.3 Сравнительный анализ архитектур построения мультимедийных файловых систем 142
4.4 Выводы 150
- Методы обеспечения непрерывного воспроизведения потоковых данных
- Параметры и характеристики моделирования
- Параметры и характеристики моделирования
- Дисциплины обслуживания запросов в течение цикла
Введение к работе
Актуальность темы. Стремительный рост объема цифровых неструктурированных данных и развитие \УеЬ-технологий привели к появлению систем сетевого доступа к разнообразным источникам информации, таким как периодические и литературные издания, корпоративные и публичные цифровые библиотеки, приложения News-On- Бетапс!, УМео-Оп-Эетапс!, интерактивное телевидение и т.д. Отличительной чертой подобных приложений является то, что они обеспечивают доступ к мультимедийной информации, включающей в себя как текстовые данные и графические изображения (текст-ориентированные данные), так и цифровые аудио/видео данные (потоковые данные). При этом предоставляемый пользователю мультимедийный документ может состоять из данных нескольких типов, объединенных в единое интерактивное представление. Например, одновременно с прослушиванием аудио записи пользователь должен иметь возможность просматривать изображения и текстовые комментарии, интересующие его согласно выбранной тематике.
Типичная архитектура рассматриваемых систем подразумевает использование серверов мультимедиа, обеспечивающих централизованное хранение информации, предоставляющих доступ к текст-ориентированным данным и реализующих потоковое воспроизведение аудио/видео файлов через высокоскоростные каналы связи. Для хранения данных и обслуживания запросов, предписывающих их чтение/запись, в таких серверах чаще всего используется дисковая подсистема ввода/вывода. При этом обращения к дисковой подсистеме выполняются на несколько порядков медленнее, чем к другим подсистемам памяти, и ее производительность становиться доминирующим фактором в общей производительности указанных систем. В то же время, дисковая подсистема является наиболее дорогим компонентом современного хранилища данных. Для увеличения производительности и более эффективного использования ресурсов сервера используются различные методы размещения файлов на наборе дисков и алгоритмы дискового планирования.
Подобные методы, обеспечивающие работу с обычными текст- ориентированными данными, представлены и исследованы в работах таких ученых, как С.А. Майоров, О.И. Авен, Я.А. Коган, D.A. Patterson, P.M. Chen, Т. Teorey, Т.В. Pinkerton, E.G. Coffman, С. Ruemmler и др. Однако методы хранения и доступа к потоковым данным должны существенно отличаться от традиционных, поскольку аудио/видео файлы обладают двумя отличительными характеристиками.
Непрерывное воспроизведение в реальном времени. В отличие от обычных текст-ориентированных данных аудио или видео данные состоят из последовательности отсчетов (таких как видеокадры или отсчеты аудиопотока), имеющих смысл только в случае непрерывного воспроизведения в реальном времени. Для этого система должна предоставить пользователю очередной фрагмент потоковых данных не позже момента завершения воспроизведения предыдущего фрагмента. В свою очередь организация доступа к текст-ориентированным данным обычно не требует жестких сроков завершения дисковых операций и направлена на увеличение пропускной способности системы.
Высокие скорости передачи и большие размеры аудио/видео файлов. Типичный размер аудио или видео файла значительно превосходит размеры текстовых файлов и графических изображений, что приводит к различию эффективных методов организации дискового пространства для данных каждого типа. Кроме того, воспроизведение цифрового аудио или видео потока требует высоких скоростей считывания. При этом для потоковых данных характерен периодический и последовательный доступ, в то время как доступ к текстовым данным обычно непредсказуем.
Разработка моделей и анализ эффективности работы дисковой подсистемы при использовании различных алгоритмов дискового планирования и методов размещения текст-ориентированных и потоковых данных для случаев раздельного обслуживания запросов каждого типа.
Оценка погрешности разработанных аналитических моделей с использованием методов имитационного моделирования, и, в некоторых случаях, путем экспериментальных исследований.
Разработка и исследование метода дискового планирования, определяющего порядок обслуживания запросов к данным обоих типов и позволяющего увеличить производительность подсистемы ввода/вывода сервера мультимедиа в рамках требуемого качества обслуживания.
Разработка аналитического метода расчета предельной нагрузки, возлагаемой на дисковую подсистему сервера мультимедиа интегрированной архитектуры, при заданных ограничениях на стохастические показатели качества обслуживания для управления допуском клиентов на обслуживание.
Аналитические модели, позволяющие оценивать эффективность работы дисковой подсистемы ввода/вывода при использовании различных алгоритмов дискового планирования и методов размещения текст- ориентированных и потоковых данных для случаев раздельного обслуживания запросов каждого типа.
Обоснование преимуществ предложенного для использования в серверах мультимедиа способа размещения текст-ориентированных и потоковых данных на наборе дисков.
Метод смешанного динамического дискового планирования FCFS с дисциплиной обслуживания LOOK очереди запросов к диску, определяющий порядок обслуживания запросов к данным обоих типов.
Аналитический метод расчета предельной нагрузки, возлагаемой на дисковую подсистему сервера мультимедиа интегрированной архитектуры, при заданных ограничениях на стохастические показатели качества обслуживания.
Разработанные аналитические модели работы дисковой подсистемы для случаев раздельного обслуживания запросов каждого типа могут применяться в задачах определения оптимальной конфигурации дисковой подсистемы и при контроле нагрузки для обеспечения требуемого качества обслуживания клиентов.
Предложенный для применения способ размещения данных на наборе дисков позволяет достичь более высокой эффективности использования ресурсов серверов мультимедиа и увеличения производительности.
Применение разработанного метода смешанного динамического дискового планирования FCFS с дисциплиной обслуживания LOOK очереди запросов к диску позволяет обеспечить наибольшую производительность дисковой подсистемы сервера мультимедиа в рамках требуемого качества обслуживания.
На основе разработанного аналитического метода расчета предельной нагрузки, возлагаемой на дисковую подсистему сервера мультимедиа, при заданных ограничениях на стохастические показатели качества обслуживания становиться возможной реализация метода управления допуском клиентов на обслуживание, гарантирующего заданное качество обслуживания.
Это послужило толчком к разработке специфических методов размещения аудио/видео файлов на наборе дисков и методов их воспроизведения в реальном времени. Подобные методы работы с потоковыми данными представлены в работах авторов DJ. Gemmell, P.V. Rangan, H.M. Vin, D.D. Kandlur, D. Anderson, C.L. Liu, J.W. Layland, A.L. Narasimha Reddy, S. Ghandeharizadeh и др. Однако указанные методы не предусматривают работу с текстовыми данными и графическими изображениями и опираются на свойства периодичности и последовательности доступа к потоковым данным для увеличения пропускной способности сервера.
Таким образом, для управления данными с различными характеристиками и требованиями к их считыванию/записи требуются новые эффективные методы размещения файлов на наборе дисков и алгоритмы дискового планирования, предназначенные для работы с данными обоих типов. В связи с этим, становится актуальной задача исследования и разработки методов хранения и доступа к данным в серверах мультимедиа.
В серверах мультимедиа обслуживание запросов к текстовым данным не должно влиять на качество воспроизведения цифровой аудио/видео информации и, наоборот, воспроизведение аудио/видео файлов не должно вызывать значительных задержек считывания текстовых данных. Поэтому для контроля перегрузок требуется построение специальных методов управления допуском, осуществляющих допуск нового клиента на обслуживание только при условии сохранения гарантий на качество обслуживания для всех клиентов. Для этой цели необходимо в реальном времени оценивать качество обслуживания клиентов при различных нагрузках. В связи с этим, также актуальной становится задача разработки аналитического метода расчета предельной нагрузки, возлагаемой на дисковую подсистему сервера мультимедиа, при заданных ограничениях на показатели качества обслуживания.
Цель диссертационной работы состоит в анализе существующих методов размещения данных и алгоритмов дискового планирования с использованием методов математического моделирования, определении способов повышения производительности серверов мультимедиа за счет увеличения производительности их дисковой подсистемы и разработке аналитического метода расчета предельной нагрузки при заданных ограничениях на стохастические показатели качества обслуживания.
Основные направления исследования.
Методы исследования основаны на положениях теории вычислительных систем, математическом аппарате теории массового обслуживания, теории вероятностей, математической статистики и технологии имитационного моделирования.
Научная новизна. В работе получены следующие научные результаты, которые выносятся на защиту.
Практическая значимость работы.
Внедрение результатов. Результаты диссертационной работы использованы Представительством АО «ОРК Софтвер Ист», г. Санкт- Петербург при разработке собственной корпоративной цифровой библиотеки, а также компанией ООО «Квантел» при построении центров хранения данных. Предложенные аналитические модели внедрены в курс лекций «Моделирование» кафедры вычислительной техники (ВТ) Санкт- Петербургского государственного университета информационных технологий, механики и оптики (СПбГУ ИТМО) для студентов специальности 2201 - «Вычислительные машины, комплексы, системы и сети», а разработанные имитационные модели используются при выполнении лабораторных работ.
Апробация работы. Основные положения диссертационной работы докладывались на первой всероссийской научно-практической конференции «Опыт практического применения языков и программных систем имитационного моделирования в промышленности и прикладных разработках» ИММОД 2003 (г. Санкт-Петербург, 2003), XXXI и XXXII конференциях профессорско-преподавательского состава СПбГУ ИТМО (г. Санкт-Петербург, 2002 и 2003), семинарах кафедры Вычислительной Техники
(ВТ) СПбГУ ИТМО «Модели и методы исследования вычислительных систем и сетей» (г. Санкт-Петербург, 2002, 2003 и 2004).
Публикации. Основные результаты диссертационной работы отражены в 7 публикациях, в числе которых 2 статьи во всероссийском журнале «Известия вузов. Приборостроение».
Структура и объем работы. Диссертационная работа состоит из четырех глав, введения, заключения, списка литературы, включающего 139 наименований. Общий объем работы - 168 страниц. Диссертация содержит 45 рисунков, 16 таблиц.
Краткое содержание работы.
В главе 1 проводится сравнительный анализ методов хранения и доступа к обычным текст-ориентированным данным и методов, характерных для работы с потоковыми данными. Проанализированы подходы к организации файловой системы сервера мультимедиа, предназначенного для работы с данными обоих типов. Вводится понятие качества обслуживания для 4 запросов к текст-ориентированным и потоковым данным. Определяются
стохастические показатели качества обслуживания и характеристики оперативности и производительности. Выделены направления исследования.
В главе 2 разрабатываются аналитические модели работы дисковой подсистемы ввода/вывода при использовании методов поблочного чередования и экстентного размещения текст-ориентированных данных совместно с такими алгоритмами дискового планирования как FCFS и LOOK. С использованием предложенных моделей исследуется влияние длины блока файловой системы на эффективность работы дисковой подсистемы. Проводится сравнительный анализ указанных методов в условиях равномерного и неравномерного распределения нагрузки по набору дисков. Определены метод размещения текст-ориентированных данных и алгоритм дискового планирования, повышающие производительность подсистемы ввода/вывода.
В главе 3 разрабатываются аналитические модели работы дисковой подсистемы ввода/вывода при использовании методов размещения аудио/видео файлов согласно постоянному шагу данных и согласно постоянному шагу времени совместно с циклическим методом доступа и алгоритмом дискового планирования LOOK. С помощью построенных моделей проводится сравнительный анализ указанных методов и исследуется влияние различных параметров на эффективность работы дисковой подсистемы. Определены метод размещения аудио/видео файлов и алгоритм доступа к данным, повышающие производительность подсистемы ввода/вывода. Рассматриваются методики определения оптимальной длины блока файловой системы для серверов, обеспечивающих хранение и доступ к текст-ориентированным данным, и серверов, обеспечивающих работу с потоковыми данными. Для серверов мультимедиа интегрированной архитектуры определен предпочтительный метод размещения данных обоих типов.
В главе 4 описываются методы дискового планирования, определяющие порядок обслуживания запросов к текст-ориентированным и потоковым данным. С помощью построенных имитационных моделей проводится их сравнительный анализ. Предлагается и исследуется метод дискового планирования, позволяющий увеличить производительность дисковой подсистемы ввода/вывода в рамках требуемого качества обслуживания. Для данного случая разрабатывается аналитический метод определения предельной нагрузки при заданных ограничениях на стохастические показатели качества обслуживания. Проводится анализ эффективности работы дисковой подсистемы ввода/вывода для случаев раздельной и интегрированной архитектур построения файловых систем серверов мультимедиа.
Методы обеспечения непрерывного воспроизведения потоковых данных
Результатом оцифровки аудио или видео информации является последовательность отсчетов или видеокадров соответственно. В дальнейшем такую последовательность будем называть потоком данных, который имеет смысл только в случае непрерывного воспроизведения во времени. Таким образом, при записи цифровой аудио/видео информации необходимо непрерывно сохранять отсчеты, генерируемые источником, во избежание переполнения буфера устройства. Аналогично, при считывании потока данных необходимо предоставлять его отсчеты с требуемой для воспроизводящего устройства скоростью. При этом, как показано в [23], с точки зрения представления в реальном времени эти процессы математически эквивалентны. В связи с этим в данной работе ограничимся рассмотрением лишь методов считывания цифровой аудио/видео информации, предполагая, что механизмы записи будут построены по аналогичным принципам.
Процесс считывания данных вычислительными системами обычно является неравномерным во времени и имеет скачкообразный характер [3]. Поэтому для непрерывного воспроизведения потоков информации применяется буферизация их фрагментов. В этом случае основная задача сервера мультимедиа будет заключаться в поддержке достаточного количества данных в буфере, выделенном для каждого потока, на протяжении всего времени воспроизведения [45]. При этом далее будем полагать, что сетевая инфраструктура обладает необходимой пропускной способностью и обеспечивает своевременную доставку требуемых данных.
В простейшем случае, требуемая непрерывность может быть гарантирована путем буферизации всего потока до начала его воспроизведения. Однако подобный подход приводит к необходимости размещения буфера большого размера и к большим задержкам начала воспроизведения. Отсюда следует, что проблема эффективного управления потоками данных сводится к поддержке непрерывности их воспроизведения при минимизации размеров буферов и начальных задержек воспроизведения (рис. 1.1), которые, как показано в [45], являются взаимосвязанными величинами: уменьшение первой ведет к уменьшению второй и наоборот.
Пропускная способность современных накопителей на магнитных дисках (НМД) значительно превышает требования одиночного потока данных. Поэтому традиционные файловые системы [13, 18], такие как FAT, NTFS [112], UFS, FFS [79], SGI EFS [139], Sun NFS [63, 99], Linux ext2fs [30], Veritas VxFS [123] и др., могут обеспечивать непрерывное воспроизведение изолированного потока при весьма умеренных требованиях к размеру используемого буфера. Однако на практике, серверам мультимедиа приходится одновременно обслуживать запросы от множества клиентов к различным потокам данных или различным частям одного и того же потока. Тогда наиболее простое решение, гарантирующее непрерывность воспроизведения, заключалось бы в назначении отдельного НМД на обслуживание каждого отдельного потока. Но в этом случае допустимое ф количество обслуживаемых в каждый момент времени потоков будет ограничиваться количеством используемых НМД. Кроме того, подобный подход ведет к неэффективному использованию пропускной способности НМД, т.к. существует возможность увеличения количества обслуживаемых клиентов путем назначения нескольких потоков на обслуживание одному НМД. В этом случае необходимо применение дополнительных методов, позволяющих удовлетворить требованию непрерывности воспроизведения для всех обслуживаемых потоков. Почти все такие методы основываются на следующих принципах [47, 136].
Циклический метод доступа к потоковым данным. Благодаря периодической природе воспроизведения мультимедийных данных, сервер может обслуживать множество клиентов с использованием циклического метода доступа, когда в течение каждого цикла считывается определенное количество отсчетов для каждого из потоков [45, 73].
Предоставление данных потока с требуемой для него скоростью. Количество отсчетов, предоставляемых сервером в течение каждого цикла, должно быть не меньше требуемого для воспроизведения в течение длительности данного цикла. Иными словами, скорость считывания данных никогда не должна быть меньше скорости их воспроизведения. Тем самым обеспечивается сохранение количества буферизованных данных, а алгоритмы с таким свойством называют сохраняющими размер буфера [23, 46].
В общем случае в серверах мультимедиа возможно применение методов доступа к данным, не обладающих свойством сохранения размера буфера. При этом серверу будет разрешаться в течение одного цикла предоставлять недостаточное количество отсчетов, в расчете на восполнение недостающих данных за последующие циклы. Однако такой подход приводит к значительному усложнению методов доступа и не используется на практике. Отсюда следует, что требование сохранения размера буфера является достаточным, но не необходимым условием непрерывности воспроизведения потока. Таким образом, если перед началом воспроизведения в буфере находится достаточно данных для воспроизведения в течение цикла с наибольшей продолжительностью и используется алгоритм, сохраняющий размер буфера, то непрерывность воспроизведения будет гарантирована.
Для первоначальной буферизации такого количества данных требуется знание максимальной продолжительности цикла. Продолжительность цикла определяется временем обслуживания всех запросов на считывание данных за текущий цикл, которое в свою очередь зависит от количества запрашиваемых отсчетов, метода дискового планирования и метода размещения данных на наборе дисков подсистемы ввода/вывода. В связи с этим, далее будут представлены подходы к определению количества отсчетов, считываемых за один цикл для каждого потока, и различные методы дискового планирования, специально предназначенные для работы с потоковыми данными. Кроме того, будут рассмотрены алгоритмы управления допуском клиентов на обслуживание, которые позволяют гарантировать то, что максимальное время обслуживания всех запросов в дисковой подсистеме ввода/вывода не превысит времени воспроизведения уже буферизованных данных. Методы размещения данных на наборе дисков подсистемы ввода/вывода требуют отдельного рассмотрения и будут представлены в следующем параграфе.
Параметры и характеристики моделирования
Время обслуживания запросов в дисковой подсистеме ввода/вывода носит стохастический характер и может рассматриваться как случайная величина, характеристики распределения которой зависят от структурных и функциональных параметров НМД, используемого метода дискового планирования, относительного расположения данных на наборе дисков подсистемы ввода/вывода и от значений длин запрашиваемых блоков данных. При этом на время обслуживания запросов от различных клиентов могут накладываться различные ограничения, определяющие качество их обслуживания. На сегодняшний день определено три уровня качества обслуживания (quality of service (QoS)) [43]. 1. Детерминированный: гарантируется завершение обслуживания запросов в требуемые моменты времени. 2. Стохастический: завершение обслуживания запросов в требуемые моменты времени обеспечивается с заданной вероятностью. Например, клиенту может быть предоставлен сервис, гарантирующий предоставление в срок по крайней мере 90% всех отсчетов воспроизводимого потока. 3. Максимального усилия (best effort): не дается никаких гарантий на завершение обслуживания запросов в требуемые моменты времени. Сервер лишь «прикладывает максимальное усилие» на обслуживание таких запросов вовремя. Т.е. для данного уровня QoS запросы назначаются на обслуживание только в случае возможности их обслуживания после клиентов с детерминированным и стохастическим уровнями QoS.
Традиционные файловые системы [13, 18], такие как FAT, NTFS [112], UFS, FFS [79], SGI EFS [139], Sun NFS [63, 99], Linux ext2fs [30], Veritas VxFS [123] и др., разрабатывались согласно 3-ему уровню QoS максимального усилия и не обеспечивают никаких гарантий на завершение обслуживания в заданные моменты времени. Для воспроизведения потоковых данных в таких файловых системах используется несколько методов обработки ситуаций, когда не удается завершить обслуживание запросов в срок. Например, в некоторых случаях запрещается пропускать какие-либо отсчеты проигрываемого потока, и все они должны быть доставлены до клиента вне зависимости от возможных разрывов в потоке воспроизводимой информации. Подобный подход приводит к увеличению эффективной длительности воспроизведения цифрового аудио/видео файла. В случае, когда требуется временная координация различных потоков, предпочтительной может оказаться потеря нескольких отсчетов одного из потоков для сохранения синхронности воспроизведения. Однако все перечисленные методы приводят к несомненному ухудшению качества воспроизводимой информации [92].
В связи с этим, мультимедийные файловые системы должны обеспечивать детерминированный и/или стохастический уровни качества обслуживания. Для контроля перегрузок в таких файловых системах применяют специальные алгоритмы управления допуском [24, 125, 126]. Они осуществляют допуск нового клиента на обслуживание только при условии сохранения гарантий на качество обслуживания для всех клиентов. Для этой цели указанным алгоритмам необходимо предсказывать производительность сервера и оценивать качество обслуживания клиентов при различных нагрузках.
Для детерминированного уровня ( оБ алгоритмы управления допуском должны реализовываться в предположении наихудших значений дополнительных издержек, связанных со временем установки механизма позиционирования на заданный цилиндр и временем ожидания подхода заданного сектора к магнитной головке [46, 78, 90, 94, 119]. На самом деле, в большинстве случаев указанные издержки будут намного меньше своих наихудших значений. Т.е. возможно увеличение числа обслуживаемых клиентов при применении алгоритма управления допуском, учитывающего стохастическую природу времени обслуживания запросов, и, соответственно, обеспечивающего 2-ой стохастический уровень качества обслуживания [86, 127].
Заметим, что использование стохастического уровня С оБ актуально не только из-за изменяющихся значений дополнительных издержек в обслуживании запросов, но и при изменяющихся требованиях к скорости передачи данных для компрессированных мультимедийных файлов. В этом случае необходимо знание стохастических характеристик всех составляющих времени обслуживания запросов в подсистеме ввода/вывода. При этом подсистему ввода/вывода рассматривают как устройство, обслуживающее совокупность входящих потоков запросов, предписывающих чтение/запись либо текст-ориентированных данных, либо очередных фрагментов мультимедийных данных. В качестве входящего потока запросов к текстовым данным обычно рассматривается ординарный поток без последействия, характерный для серверов глобальных вычислительных сетей (ГВС), обслуживающих большое количество пользователей (например, серверов). Т.е. предполагается, что запросы поступают независимо друг от друга с интенсивностью Л, ив каждый момент времени может появиться только один запрос. В свою очередь, при использовании циклического метода доступа к мультимедийным данным соответствующий входящий поток запросов можно представить как неординарный, когда в начале каждого цикла формируется N запросов для воспроизведения N аудио/видео файлов.
Параметры и характеристики моделирования
Среди основных существующих работ, посвященных построению мультимедийных файловых систем интегрированной архитектуры, можно выделить проект Fellini [78, 90], проект Symphony [106 - 108] и Hermes [84 - 87]. Подобные файловые системы в достаточной степени свободны от указанных недостатков, присущих файловым системам раздельной архитектуры. Так, благодаря наличию единого дискового пула, становится возможным размещение файлов большого размера с низкими требованиями к скорости воспроизведения совместно с файлами малого размера, но с высокими требованиями к скорости считывания/записи, чем достигается большая эффективность использования ресурсов сервера. Кроме того, из-за возможности динамического выделения ресурсов, файловая система интегрированной архитектуры является предпочтительной в случае изменяющейся во времени нагрузки. В отличие от файловых систем раздельной архитектуры в этом случае потенциально обеспечивается обслуживание большего количества клиентов одного типа при малых нагрузках к данным другого типа. Наконец, благодаря тому, что на обслуживание каждого запроса выделяется больше ресурсов, подобный подход потенциально может обеспечить лучшую оперативность.
Перечисленные выше предположения вытекают из концептуального сходства рассматриваемого вопроса разделения пропускной способности подсистемы ввода/вывода с вопросом разделения пропускной способности сети передачи данных. Применительно к вопросам построения сетевых решений, в [105] было показано, что сетевая инфраструктура, использующая раздельные сети для обслуживания приложений разных типов, является наименее эффективной, в то время как сеть интегрального обслуживания обеспечивает не меньшую, и чаще всего значительно большую производительность. Действительно, рассмотрим две раздельные сети, каждая из которых предназначена для обслуживания отдельного типа приложений и имеет пропускную способность С, и сеть интегрального обслуживания с пропускной способностью 2 С. Далее предположим, что данные приложений каждого типа передаются в пакетах одинакового размера (случай пакетов разного размера рассмотрен в [25]). Тогда, применяя простой алгоритм поочередного обслуживания, получаем, что в сети интегрального обслуживания приложения каждого типа будут получать пропускную способность С как и в случае раздельных сетей. Однако, если приложение одного типа использует свою пропускную способность не полностью, она может быть использована приложением другого типа, что и обуславливает увеличение производительности сети передачи данных с точки зрения этого приложения.
Для иллюстрации рассмотренных предположений применительно к вопросам построения мультимедийных файловых систем рассмотрим следующий пример. Пусть для сервера с файловой системой раздельной архитектуры выделено )7 и И2 НМД для поддержки текстовых и мультимедийных данных соответственно. При этом для требуемого качества обслуживания предельно допустимое значение интенсивности входящего потока запросов к текстовым данным составляет ЛПРЕД, а предельно допустимое количество одновременно воспроизводимых потоков - /1РЕД. В свою очередь для сервера с файловой системой интегрированной архитектуры будет выделено 01+02 НМД для поддержки данных обоих типов. Тогда при гарантии того же качества обслуживания идеальный сервер с файловой системой интегрированной архитектуры должен обслуживать в ()7+ 2)/ 2 раз большее количество мультимедийных потоков информации и выдерживать в (р1+02)Ю1 раз большую интенсивность входящего потока запросов к текстовым данным. Кроме того, граница области допустимой нагрузки должна иметь линейную форму (рис. 1.7). При этом все точки {И, Л), расположенные левее и ниже представленной границы, соответствуют нагрузкам, которые могут быть поддержаны дисковой подсистемой с требуемым качеством обслуживания; все точки, расположенные правее и выше границы, соответствуют нагрузкам, поддержка которых с требуемым качеством обслуживания невозможна. Поэтому для построения метода, обеспечивающего управление допуском клиентов на обслуживание, достаточно определить значения ЛПРЕД и /7РЕД. Остальные пограничные значения (ТУ, Л) могут быть получены исходя из свойства линейности границы области допустимой нагрузки.
Отсюда следует, что для случая идеального сервера интегрированной архитектуры задача исследования и разработки эффективных методов хранения и доступа к данным в серверах мультимедиа сводится к нахождению методов, позволяющих увеличивать предельно допустимые для заданного качества обслуживания значения ЯПРЕД и 1/1РЕД. В связи с этим, одной из задач настоящей работы будет исследование методов хранения и доступа к данным каждого типа в отсутствии нагрузки к данным другого типа и разработка моделей, позволяющих оценивать производительность дисковой подсистемы ввода/вывода для нахождения.
В действительности же работа дисковой подсистемы ввода/вывода значительно отличается от работы сети передачи данных. И аргументы, аналогичные приведенным выше для случая сетей передачи данных, оказываются непригодными для сравнения интегрированной и раздельной архитектур файловых систем по следующим причинам.
Дисциплины обслуживания запросов в течение цикла
Для исследования методов хранения и доступа к текст- ориентированным данным чаще всего используются имитационные и аналитические модели, позволяющие оценивать влияние различных параметров на работу подсистемы ввода/вывода. При этом большинство работ в этом направлении посвящено исследованию метода поблочного чередования, рассмотренного в п. 1.2, и направлено на поиск размера блока чередования, увеличивающего эффективность работы дисковой подсистемы ввода/вывода [34, 35, 72, 103, 121].
В [34, 35, 72] предложены методы определения оптимального размера блока, построенные на основе моделей в виде замкнутых сетей массового обслуживания с фиксированным уровнем мультипрограммирования. Однако подобный подход оказывается непригодным для рассматриваемых серверов хранения и доставки документов по сети, работающих в условиях меняющейся во времени нагрузки и обслуживающих большое число клиентов. В [121] рассматривается аналитическая модель для оценки пропускной способности массивов НМД RAID 1/0. В работе [103] предложен метод определения оптимального размера блока в условиях пуассоновского входящего потока и при предположении равномерного распределения нагрузки по набору НМД. Благодаря высокой скорости расчета, предлагаемые в [103, 121] модели могут применяться в задачах определения оптимальной конфигурации дисковой подсистемы ввода/вывода. В то же время они не позволяют получать оценку среднего времени пребывания запросов в подсистеме ввода/вывода при заданном размере блока чередования и, следовательно, не могут быть использованы для сравнения метода поблочного чередования с другими методами размещения данных. Кроме того, указанные модели не рассматривают стохастический показатель качества обслуживания (1.2) и поэтому не могут применяться при контроле нагрузки для обеспечения требуемого качества обслуживания клиентов.
В связи с этим, в данной главе предлагаются аналитические модели нахождения среднего времени пребывания запросов в подсистеме ввода/вывода для метода поблочного чередования [10]. В отличие от [103] наряду с методом дискового планирования FCFS рассматривается алгоритм обслуживания LOOK, повышающий производительность НМД. На основе неравенства Чебышева предлагается оценка стохастического показателя качества обслуживания (1.2), что позволяет ограничивать время пребывания в подсистеме ввода/вывода для каждого отдельного запроса.
Проводится исследование рассмотренного в п. 1.2 метода экстентного размещения данных, применяемого в основном для размещения аудио/видео файлов и позволяющего снизить негативные эффекты внешней и внутренней фрагментации. Для данного метода также построены аналитические модели, позволяющие оценивать как среднее время пребывания запросов в подсистеме ввода/вывода, так и значение стохастического показателя качества обслуживания [10].
Проверка адекватности предлагаемых аналитических моделей осуществляется по отношению к имитационным моделям, описывающим соответствующие методы размещения данных и алгоритмы дискового планирования, и, в частных случаях, при помощи экспериментальных исследований. Моделирования проводится при использовании значений структурных параметров современных НМД IBM UltraStar 36ГБ [56] вместо устаревших Seagate Elite3, рассматриваемых в [103], и нагрузочных параметров, полученных из наблюдений за реальными системами [54, 101], а не гипотетическим путем.
С использованием предложенных моделей исследуется влияние длины блока на эффективность работы дисковой подсистемы. Проводится сравнительный анализ методов поблочного чередования и экстентного размещения данных совместно с такими алгоритмами дискового планирования как FCFS и LOOK в условиях равномерного и неравномерного распределения нагрузки по набору дисков [8].
Предлагаемые в данной главе модели описывают работу подсистемы ввода/вывода, состоящей из D дисков, необходимых для хранения и считывания запрашиваемых текст-ориентированных данных.
При использовании метода поблочного чередования файлы разбиваются на непрерывные блоки фиксированного размера SU, которые затем распределяются по набору НМД в циклическом порядке (рис. 1.3). При этом, как указывалось в п. 1.2, в данной работе рассматривается чередование данных, осуществляемое средствами файловой системы на уровне блока. Кроме того, рассматривается смежное размещение расположенных на одном диске блоков, принадлежащих одному файлу, что приводит к уменьшению накладных расходов, связанных со временем позиционирования читающих головок НМД. Таким образом, согласно методу поблочного чередования запрос, пришедший в дисковую подсистему, разбивается на подзапросы, размеры которых кратны размеру блока чередования SU. Обозначим через R средний размер запроса, а через S средний размер подзапроса. Соответственно, количество подзапросов, соответствующих одному запросу, может варьироваться от 1 до D. При этом каждый подзапрос обслуживается отдельным НМД и время пребывания запроса TD в дисковой подсистеме будет определяться временем пребывания его последнего подзапроса. Тогда количество НМД, обслуживающих один запрос, назовем степенью параллелизма и обозначим через Рг.
