Честное планирование дискового ввода-вывода с учетом разделяемых ресурсов файлового кэша (1187435), страница 6
Текст из файла (страница 6)
Учет использования процессами файлового кэша также можновести только в терминах размеров запросов. Поэтому алгоритмы на основе выделениябюджетовнаилучшимобразомподходятдлякорректировкидляучетаиспользования кэша.BFQ является одним из наиболее эффективных среди существующих честныхалгоритмов планирования доступа к диску, причем как с точки зрения честностираспределения ресурса диска, так и с точки зрения суммарной производительностидисковой подсистемы. В частности, он демонстрирует более хорошие результаты вразнообразных тестах дисковой активности, чем CFQ.
Кроме того, алгоритм BFQобеспечивает гарантиичестности распределения битрейтов процессов, а также25гарантированную верхнюю границу времени ожидания начала исполнения длякаждого запроса.Таким образом, представляется целесообразным выбрать BFQ в качестве основы дляпостроения базового алгоритма дискового планировщика в данной работе.5.5. Корректировка BFQ для учета разделяемых данныхв файловом кэшеПерейдем к описанию метода корректировки базового алгоритма планирования,специфичного для алгоритма BFQ (Budget Fair Queueing), используемого в качествебазового. Суть метода состоит во внесении поправок в значения виртуальных временпроцессов в алгоритме WF2Q+ при чтении разделяемых данных процессами изфайлового кэша.
В результате использование процессами общих данных корректноучитывается планировщиком.5.5.1. Описание метода корректировкиСуть метода состоит в том, что с точки зрения алгоритма планирования запрос начтение с диска в кэш «делится» поровну между всеми процессами, которые впоследствиииспользуют соответствующие данные, читая их из файлового кэша. Для этого вносятсясоответствующие поправки в виртуальные времена процессов, используемые в алгоритмеWF2Q+ для выбора активного процесса.При этом для процесса, прочитавшего фрагмент разделяемых данных с диска,виртуальное время уменьшается, для процессов, читающих этот фрагмент из кэша,увеличивается. Таким образом, процессы, читающие данные из кэша, получают за этонекий «штраф», учитываемый планировщиком.Пусть– размер фрагмента данных, разделяемого междупроцессами.– процесс, прочитавший этот фрагмент с диска в файловый кэш.
{ } – множество,состоящее изпроцессов, прочитавших фрагмент из кэша к настоящему моменту(в том числе процесс). Тогда при чтении этого фрагмента из кэша процессомпоправки виртуального времени вычисляются следующим образом. Для каждого процессаиз множества { }:( Для процесса())⁄(16):(26)⁄(17)5.5.2. Свойства полученного алгоритмаВ результате описанной коррекции виртуальных времен процессов в соответствии сформулами (16), (17) получаем, что в любой момент времени после завершения всехчтений из кэша некоторого фрагмента разделяемых данных верно следующееутверждение. Количество полученного сервиса (виртуальное время) для каждого процессаравно тому, которое этот процесс получил бы, если бы каждый запрос на чтение из дискав кэш разделяемых междупроцессами данных размерабыл заменен назапросовразмера ⁄ , отправленных каждым из этих процессов.Таким образом, для временных промежутков длиной порядка характерного временижизни данных в кэше (время от попадания в кэш до вытеснения из него) выполняетсяусловие честности в терминах прочитанных/записанных байт за промежутки времени.Кроме того, такая корректировкавиртуальных времен исключает возможностьнакопления систематической нечестности при работе с разделяемыми данными.5.5.3.
Оценки алгоритмической сложностиВ следующей главе данной работы, при описании реализации систем мониторинга ипланирования дискового ввода-вывода для ОС Windows, будетпоказано, чтоалгоритмическая сложность в среднем для операций со вспомогательными структурамиданных, используемыми для хранения информации об операциях с разделяемымиданными в файловом кэше, есть ( ).Каждая операции корректировки виртуального времени отдельно взятого процессапроисходит за время ( ). Всего на каждую кэшированную операцию с разделяемымиданными выполняется( ) таких операций корректировки, где– число процессов,обращающихся к разделяемым данным.
Таким образом, алгоритмическая сложностькорректировки есть ( ) на каждую кэшированную операцию.276. Реализация альтернативного дискового планировщикав ОС WindowsВ данном разделе мы опишем практическую реализацию рассмотренных ранееалгоритмов в ОС Windows.
Она включает в себя важную подзадачу – создание системымониторингадисковойактивности,позволяющейотслеживатькаждыйзапросввода-вывода на уровне диска и на уровне файловой системы. Система мониторингапозволяет определять принадлежность запросов конкретным процессам в системе, причемдаже в сложных случаях, когда запрос исполняется в контексте ядра ОС. Также онапозволяет вести учет использования процессами файлового кэша на уровне отдельныхзапросов и соответствующих фрагментов файлов.Далее приводится описание архитектуры собственно планировщика дисковойактивностииописаниереализациибазовогоалгоритмапланирования(BFQ).Рассматриваются некоторые важные особенности реализации дискового планировщика,специфичные для ОС Windows.Крометого,приведенырезультатысравнениярассмотренныхалгоритмовпланирования (оригинального BFQ и его модификации для учета файлового кэша) натестах дисковой активности, демонстрирующие, что реализованный планировщикдействительно решает поставленную задачу.6.1.
Система мониторинга дисковой активностиПостановку задачи мониторинга дисковой активности можно сформулироватьследующим образом. Для каждого запроса дискового ввода-вывода, обрабатываемогосистемой, требуется определить процесс, являющийся реальным инициатором этогозапроса. Сложность решения задачи состоит в том, что значительная часть файловыхопераций в ОС Windows обрабатываются в контексте ядра системы, а не тогопользовательского процесса, который инициировал операцию. Примером такой операцииввода-вывода является сброс файлового кэша на диск.Для решения этой задачи необходима глубокая интеграция в работу составляющихдисковой подсистемы в ядре ОС: драйвера файловой системы, менеджера файловогокэша, менеджера виртуальной памяти и драйвера диска.
Реализация этого осложняетсятем фактом, что Windows является системой с закрытым кодом. Это приводит кнеобходимости использования различных способов встраивания в систему, как28предусмотренных самой ОС, так и более сложных – требующих модификации бинарногокода системы во время исполнения.Реализованный метод определения инициатора запроса в сложных сценарияхсостоит в том, что на начальной стадии исполнения запроса (когда процесс-инициатореще известен) информация о запросе и его инициаторе (т.н.
начальный контекст)сохраняется системой мониторинга. Затем, на основной стадии (при обработке запросадрайвером файловой системы или драйвером диска), производится поиск начальногоконтекста по некоторым параметрам запроса, которые известны как на начальной стадии,так и на основной.Помимо установления инициаторов отдельных запросов ввода-вывода, системамониторингапозволяетполучатьнеобходимуюдлякорректировкиалгоритмапланирования информацию об использовании процессами файлового кэша.
Далее мырассмотрим архитектуру реализованной системы мониторинга и то, каким образом онаобрабатывает исполнение запросов ввода-вывода в сценариях дисковой активности,связанных с использованием файлового кэша.Для встраивания в процесс обработки запросов ввода-вывода используются 2механизма – драйверы-фильтры и хуки функций ядра. Механизм драйверов-фильтровявляется штатным средством расширения функциональности подсистемы ввода-вывода исостоит в возможности встроить сторонний драйвер над (почти) любым из имеющихся встекедрайверов.Приэтомфильтрперехватываетвсезапросыввода-вывода,предназначенные целевому драйверу.Механизм хуков функций заключается в модификации «на лету» (во времяисполнения) бинарного кода ядра ОС таким образом, что при вызове целевой функцииуправление передается некоторому стороннему коду (этот код также называется хуком).Таким образом, при помощи установки хука можно «дописать» произвольный код вначало и конец любой функции ядра ОС.6.1.1.
Общая архитектураПриведем описание предназначения каждого из компонентов системы мониторингаи реализованной в них функциональности. В следующем разделе на рисунке 3 изображенасхема компонентов системы мониторинга, их расположение в дисковом стеке ивзаимодействия с компонентами дисковой подсистемы ОС и с реализованнымдисковым планировщиком.Итак, система мониторинга дисковой активности состоит из следующего набораосновных компонентов.291. Драйвер-фильтр над файловой системой.Основой системы мониторинга является драйвер-фильтр, который встраивается встек над устройствами смонтированных томов файловых систем. Этот фильтрперехватывает все IRP (I/O Request Packet, пакет запроса ввода-вывода) и Fast I/O(механизм обработки кэшированных запросов без создания IRP) запросы, каккэшированные, так и некэшированные, предназначенные драйверам файловыхсистем,атакжевстраиваетсявцепочкуобработкизавершениявсехперехватываемых IRP.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
