Честное планирование дискового ввода-вывода с учетом разделяемых ресурсов файлового кэша (1187435), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Реализация построенного по данной схеме дискового планировщика в ОС Windows.Предполагаетсяреализоватькакоригинальныйбазовыйалгоритм,такиалгоритмаимодифицированный, с целью дальнейшего сравнения.4. Проведениесравнительногоанализахарактеристикмодифицированного при помощи тестов.5базового3. Обзор предметной области и ее проблематикиВэтомразделемырассмотримболееподробноосновныепроблемыпроизводительности дискового ввода-вывода, о которых говорилось во введении, а такжеобсудим существующие методы их решения.3.1. Системы хранения данных и проблемы их производительностиС точки зрения задачи планирования ресурсов дисковый ввод-вывод во многомпохож на другие типы ввода-вывода, например, передачу данных по сети, но в то жевремя имеет и некоторые принципиальные отличия.

Главным из них является то, что всовременных ОС диск используется не только как средство хранения пользовательскихданных и программ, но и тесно связан с подсистемой управления памятью. В частности,диск, как устройство хранения, обладающее значительно большим объемом, чемоперативная память (но при этом значительно меньшей скоростью), используется ядромОС для подкачки памяти (свопа) – сброса на диск неиспользуемых данных из оперативнойпамяти в случае ее нехватки. С подсистемой управления памятью также неразрывносвязан файловый кэш – промежуточное хранилище данных в оперативной памяти с цельюускорения доступа к наиболее часто используемым данным.Проблемы производительности подсистемы дискового ввода-вывода в современныхвычислительных системах можно разделить на 2 основные категории, которые будутрассмотрены в следующих разделах: проблема обеспечения баланса между суммарной пропускной способностью диска ивременем ожидания исполнения для отдельных запросов; проблема обеспечения качества обслуживания для каждого отдельного клиентадисковой подсистемы.Далее мы рассмотрим некоторыми важные примеры проявления этих проблем всовременных вычислительных системах.Многим мультимедийным приложениям, в частности, проигрывателям музыки ивидео, необходимо иметь возможность поддержания постоянной ширины канала начтение данных с диска.

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

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

По аналогии с механизмом квот надисковое пространство нужен такой же механизм для канала доступа к диску.3.2. «Традиционные» дисковые планировщикиПроведем краткий обзор «традиционных» алгоритмов планирования доступа кдиску, не ставящих своей целью решить задачу честности распределения ресурсадисковой подсистемы. Их можно разделить на 3 основные группы: алгоритмы,максимизирующиесуммарнуюпропускнуюспособностьдискаблагодаря учету особенностей геометрии жестких дисков; алгоритмы, обеспечивающие ограниченное время ожидания исполнения отдельныхзапросов; алгоритмы, обеспечивающие некоторый баланс между суммарной пропускнойспособностью диска и временем ожидания для отдельных запросов.В современных жестких дисках подобные алгоритмы, учитывающие относительноерасположение запросов, реализуются в самих устройствах. Основным таким примеромявляется технология SATA NCQ (Native Command Queueing), поддерживаемая в7большинстве современных систем хранения данных.

Таким образом, учет геометриижестких дисков для оптимизации суммарной пропускной способности перестает бытьзадачей, которую необходимо решать на уровне операционной системы.Но в то же время учет относительного расположения запросов, в частности, т.н.локальности, на уровне ОС по-прежнему важен. Дело в том, что высокая степеньлокальности обращений к диску позволяет увеличить утилизацию аппаратного дисковогокэша (количество попаданий запросов в кэш), что приводит к увеличению общейпроизводительности диска.Далее мы рассмотрим основных представителей каждого из данных классовалгоритмов дисковых планировщиков.3.2.1. Планировщики для максимизации пропускнойспособности дискаКратко опишем некоторые наиболее важные из алгоритмов, относящихся кданной категории. Алгоритмы SCAN (Elevator) и C-SCAN.Приходящие от приложений запросы упорядочиваются в порядке их расположения впространстве логических адресов на диске. При приходе нового запроса ввода-вывода вмомент, когда диск простаивает, алгоритм выбирает в начальное направление обходаочереди запросов, совпадающее с направлением движения считывающей головкижесткого диска.

Во время движения головки диска исполняются только запросы,расположенные в текущем направлении, в порядке их расположения. Когда головкадоходит до конца диска, направление движения меняется на противоположное, и т.д.Таким образом, данный алгоритм напоминает работу лифта, благодаря чему и получилсвое название.В результате минимизируются времена передвижения головки к следующемузапросу, и таким образом достигается увеличение общей пропускной способности диска.Однако время ожидания исполнения для отдельных запросов может быть слишкомвелико, из-за чего в явном виде данный алгоритм неприменим в системах, в которых стоитзадача обеспечения качества обслуживания.Существует также модификация данного алгоритма C-SCAN, отличающаяся тем,что считывающая головка все время движется в одном направлении, и при достиженииконца диска перемещается в его начало.

Обычно такой сброс головки выполняетсязначительно быстрее, чем ее «обычное» перемещение в обратном направлении во времяисполнения запросов.8 Алгоритмы LOOK и C-LOOK.В основе алгоритма LOOK лежит та же идея, что и в алгоритме SCAN. Отличиесостоит в том, что при использовании алгоритма LOOK в случае, если после исполнениязапроса в текущем направлении запросов больше нет, головка диска сразу начинаетдвигаться в противоположном направлении, не доходя до конца диска.Аналогично SCAN, для алгоритма LOOK существует модификация C-LOOK,отличающаяся сбросом головки в начало диска вместо движения в противоположномнаправлении.

Алгоритм C-LOOK используется для упорядочения запросов дисковоговвода-вывода во многих современных ОС, в частности, в ОС Windows, а также в ОС Linuxв качестве составной части планировщиков CFQ и BFQ, которые будут описаны вследующем разделе.3.2.2. Планировщики для ограничения времени ожиданияисполнения запросаАлгоритмы, относящиеся к данной категории, также называют алгоритмами real-timeпланирования (режима реального времени). Для каждого запроса дискового ввода-выводавводится т.н. deadline – момент времени, к которому запрос должен быть исполнен.

Такимобразом, при условии соблюдения deadline для каждого запроса планировщикобеспечиваетгарантированноемаксимальноевремяожиданияисполнениядлякаждого запроса.Простейшим алгоритмом такого рода является EDF (Earliest Deadline First),исполняющий запросы в порядке наступления ихdeadline. Существует также«гибридный» алгоритм SCAN-EDF, группирующий запросы согласно величине deadline:непрерывная ось времени делится на некоторые дискретные промежутки, и в одну группупопадают запросы, deadline которых лежит в одном и том же промежутке. Планировщикисполняет запросы по группам в порядке наступления deadline, причем в каждой группезапросы исполняются в порядке, определяемом алгоритмом SCAN.Существует также класс приоритетных планировщиков, исполняющих запросы впорядке уменьшения приоритета, а внутри каждой группы по приоритету запросыисполняются в соответствии с одним из традиционных алгоритмов планирования.Примером приоритетного планировщика является планировщик, реализованный в ОСWindows начиная с версии Windows Vista/Windows Server 2008.93.3.

Проблема честного планирования доступа к диску исуществующие решенияПерейдем к описанию класса т.н. честных алгоритмов планирования доступа кдиску. Суть задачи честного планирования состоит в распределении ширины каналадоступа к диску между многими процессами в соответствии с некоторыми заданными дляэтих процессов весами. При этом для каждого процесса гарантируется некоторая доляпропускной способности дисковой подсистемы в независимости от дисковой активностиостальных приложений в системе.Далее мы рассмотрим некоторые существующие честные алгоритмы планирования,причем особое внимание уделим алгоритму BFQ (Budget Fair Queueing), на основекоторого в дальнейшем будет построен алгоритм для решения поставленной в даннойработе задачи.3.3.1. Простейшие алгоритмыБольшинство существующих на данный момент честных алгоритмов планированиядоступа к диску в некотором смысле основаны на одном общем подходе – GPS(Generalized Processor Sharing).

Характеристики

Список файлов ВКР