Честное планирование дискового ввода-вывода с учетом разделяемых ресурсов файлового кэша (1187435), страница 7
Текст из файла (страница 7)
Драйвер-фильтр под файловой системой.Используется для регистрации всего дискового I/O, в том числе инициируемогосамой файловой системой. Данный фильтр расположен между драйвером файловойсистемы и драйвером диска и встраивается в стек устройств дисковых разделов.3.
Хуки функций менеджера файлового кэша и менеджера памяти.Используются для перехвата вызовов функций, связанных с кэшированным вводомвыводом и работой с отображаемыми в память файлами. Позволяют полноценнымобразом учитывать кэшированные операции, что особенно важно в контексте задачиобеспечения честного распределения битрейтов на уровне файлового кэша.4.
Контрольный драйвер.Центральный компонент системы мониторинга, осуществляющий управление ивзаимодействие между остальными компонентами. В нем также реализовансобственно планировщик ввода-вывода. Кроме того, он предоставляет интерфейсдля приложений режима пользователя для забора статистики дискового вводавывода и выставления параметров алгоритма дискового планировщика, в частности,задания весов процессов.6.1.2. Мониторинг кэшированного чтения и чтенияmemory mapped файловОбработка кэшированного чтения с точки зрения файловой системы разделяется на 2стадии. Начальной стадией является приход первичного IRP или Fast I/O запроса,синхронного или асинхронного. Основной стадии соответствует обработка вторичногоIRP чтения с диска. В случае синхронного запроса инициатором, очевидно, являетсятекущий процесс.
В случае асинхронного первичный IRP, перехватываемый драйверомфильтром над файловой системой, связывается с последующим вызовом функцииCcCopyRead() или CcMdlRead(), на которую устанавливается хук, через общие параметры:файл, смещение в файле, длина запроса.30Далее, при обработке драйвером вторичных IRP обработки страничных ошибок,чтение данных в кэш отсекается от других сценариев обработки page fault-ов на основаниитого, из какой функции этот page fault был вызван. В случае опережающего чтенияинициатором считается последний процесс, инициировавший кэшированное чтение изсоответствующего файла.Таким образом, система мониторинга учитывает первичные кэшированные запросыот всех процессов, а не только от того, в контексте которого будет происходить чтениеданных в кэш.
Полученная информация об этих запросах передается в дисковыйпланировщик, который вносит необходимые корректировки.Страничные ошибки, не связанные с файловым кэшем, можно разделитьна 2 категории: page fault в страничном файле и page fault при чтении из memory mappedфайла. Т.к. страничные ошибки обрабатываются синхронно, инициатором операции вданном случае является текущий процесс. Определение инициатора в случае page fault встранице, разделяемой между несколькими процессами, сильно усложняется. Проблемасостоит в том, что в отличие от ядра ОС Linux, в ядре ОС Windows не используетсямеханизм обратного отображения (reverse mapping), заключающийся в хранениисопоставления каждой странице физической памяти всех страниц виртуальной памяти,которые в нее отображаются.Таким образом, не существует простого способа узнать список процессов,разделяющих данную страницу памяти или memory mapped файла.
Тем не менее, можнополучить список процессов, вообще имеющих доступ к разделяемому memory mappedфайлу, и считать каждый из них инициатором операции чтения.6.1.3. Мониторинг кэшированной записи и записиmemory mapped файловНачальной стадией для записи в кэш, как и в случае кэшированного чтения, являетсяобработка файловой системой первичного IRP или Fast I/O запроса кэшированной записи.Основной стадией является сброс диапазонов файла на диск из ядерного потокаменеджеракэшафункциейCcFlushCache(),накоторуюустанавливаетсяхук.Сбрасываемый диапазон файла определяется из параметров внутренней функциименеджера памяти MmFlushSection(), на которую также устанавливается хук. Дляпервичных IRP сохраняется записываемый диапазон файла, по которому на основнойстадиипроисходитпоискначальногоконтекста.Аналогичноустанавливаютсяинициаторы для операций явного сброса кэшированных файлов, которые также сводятся квызову функции CcFlushCache().
В результате система мониторинга может определить31все процессы, писавшие в кэшированный файл, и информация о них передается вдисковый планировщик.Перейдем к рассмотрению записи отображаемых в память файлов. Менеджер памятиведет список модифицированных физических страниц, которые нужно сбросить на дискпри нехватке оперативной памяти. Основной причиной попадания в этот список являетсявытеснение страницы из рабочего набора процесса.
Вытеснение происходит в функцияхMiFreeWsle() и MiFreeWsleList(), установка хуков на которые позволяет определитьпроцесс, из рабочего набора которого страница была вытеснена.На основной стадии (записи модифицированных страниц памяти на диск)происходит проверка, была ли каждая из записываемых на диск страниц ранее вытеснена,и по адресам этих страниц находятся все процессы, из рабочих наборов которых они быливытеснены.
Эти процессы и считаются инициаторами операции. Более сложнымсценарием является запись модифицированных страниц при уничтожении процесса.Определениеинициаторавэтомслучаетребуетзначительноговмешательствав структуры менеджера памяти.6.1.4. Структуры данных для хранения информации обиспользовании кэшаПриведем описание структур данных, предназначенных для хранения информацииоб использовании процессами файлового кэша. Для сохранения информации о том, какиепроцессы считывают с диска в кэш определенные фрагменты файлов, используется т.н.«теневой кэш» (shadow cache).Для каждого открытого на чтение файла в системе, с которым процессы работаюткэшированным образом, хранится аналог карты кэша с гранулярностью от 64 до 256килобайт в зависимости от размера файла.
От величины этой гранулярности зависититоговый расход системной памяти на теневой кэш. Было решено выбрать ее равнойиспользуемой менеджером кэша для хранения карты отображения кэшированных файловв память, выделенную для кэша. В случае файлов меньшего размера, а таких в системеобычно большинство, хранится один элемент теневого кэша на весь файл.Для каждого фрагмента файла в теневом кэше хранится процесс, который прочиталэтот фрагмент, либо большую его часть, если таких процессов несколько, и списокпроцессов, которые к настоящему моменту успели прочитать этот фрагмент или его частьиз кэша.
Кроме того, для файлов, открытых для записи, для каждого фрагмента хранитсяеще и список процессов, записавших в этот фрагмент.32Для организации поиска элемента теневого кэша по смещению в файлеиспользуются хеш-таблицы, роль ключа в которых выполняет смещение от начала файла,выровненное на величину гранулярности. Таким образом, операция поиска фрагментакэша по смещению в файле выполняется в среднем за время( ). Операции вставкинового элемента и удаления существующего элемента также выполняются в среднемза время ( ).В то же время расход памяти на хранение теневого кэша является значительным.Потребление системной памяти на них всего на порядок меньше совокупных расходовменеджера кэша и менеджера памяти на хранение карт кэша и соответствующихотображений файлов в память.Для удаления устаревших фрагментов теневого кэша используется перехватвытеснения соответствующих фрагментов из файлового кэша путем установки хука нафункциюCcFreeVirtualAddress(),вызываемуюприудалениисоответствующегоотображения (unmapping) файла в память.
Таким образом, потребление памяти дляхранения теневого кэша ограничено реально используемым объемом файлового кэша.6.2. Особенности реализации в ОС WindowsРассмотрим наиболее важные особенности реализации планировщика дисковоговвода-вывода в ОС Windows. Эти особенности в основном связаны с отличиямиподсистем дискового ввода-вывода в ОС Windows и в ОС Linux, для которой былизначально реализован алгоритм BFQ.1. Большое количество асинхронных запросов (по сравнению с Linux). В частности,почти вся системная дисковая активность является асинхронной: сброс файлового кэша и отображаемых в память (memory mapped) файлов; опережающее чтение в файловый кэш (read ahead); загрузка исполняемых образов и т.п.2. Наличие запросов, исполнение которых нельзя задерживать надолго, иначе этоможет негативно отразиться на общей производительности системы: сброс страниц физической памяти в файл подкачки в случае ее нехватки; page fault-ы (ошибки отсутствия страниц), возникающие в коде ядра; page fault-ы, возникающие в потоках, обрабатывающих очереди оконныхсообщений и отрисовывающих графический интерфейс пользователя; записи в журнал файловой системы NTFS с целью поддержки восстановленияфайловой системы в случае сбоя и т.п.333.
Наличие запросов больших размеров (вплоть до 8 мегабайт), исполнение которыхзанимаетзначительноесточкизренияпланировщиквремя.Для сравнения, в ОС Linux размеры запросов дискового ввода-вывода ограничены512 килобайтами.4. Запросы ввода-вывода от пользовательских приложений могут разбиваться на болеемелкие, например, драйвером файловой системы. В результате может возникатьситуация, когда дисковый планировщик исполнил только часть «подзапросов», ипроцесс вынужден ждать исполнения оставшихся «подзапросов» перед тем какотсылать следующие (в случае синхронной дисковой активности).5. На том уровне стека драйверов дисковой подсистемы, куда удобно встраиватьдисковый планировщик (в силу особенностей реализации драйверов уровня ядра вОС Windows), реализована отличная от ОС Linux и оригинальной реализации BFQмодель взаимодействия с устройством диска.
Основное отличие состоит в том, что вОС Windows реализуемый нами дисковый планировщик (который являетсядрайвером-фильтром в стеке драйверов диска) сам отсылает запросы ввода-выводавниз к драйверу диска. В оригинальной реализации BFQ же предполагается, чтодрайвер диска сам запрашивает у планировщика следующий запрос на исполнение.В результате получается другая схема построения планировщика, описанная вследующем разделе.6. Обработка завершения запросов ввода-вывода драйверами дискового стекав ОС Windows производится отложенным образом. При завершении операцииввода-вывода возникает прерывание от устройства диска, обработчик которогозаказывает у системы DPC (deferred procedure call, отложенный вызов процедуры),которая будет исполнена при следующем вызове планировщика процессов.
В этойDPC происходит обработка завершения запроса, и именно после ее исполненияпроцесс-инициатор запроса узнает о его завершении. Задержка между приходомпрерывания о завершении запроса ввода-вывода и исполнением DPC можетдостигать величины периода системного таймера, значение которого по умолчаниюсоставляет 16 миллисекунд. Данная схема делает еще более актуальнымприменяемое в алгоритме BFQ дополнительное ожидание синхронных запросов. Вто же время, для возможности более точного измерения времени исполнения запросанеобходимо либо уменьшать период системного таймера, что может привести кувеличению энергопотребления в системе, либо перехватывать первоначальныепрерывания о завершениях запросов, что усложняет разработку планировщика.346.3. Общая архитектура системы планированияНа рисунке 1 изображена общая схема архитектуры разработанного дисковогопланировщика.
На схеме также приведены взаимодействия между компонентамипланировщика, а также между планировщиком и составными частями подсистемыдискового ввода-вывода и компонентами системы мониторинга дисковой активности.Рисунок 1356.4. Реализация базового алгоритма планирования BFQПерейдем к описанию реализации дискового планировщика. Он расположен вконтрольномпланировщикадрайвереиисистемыпредоставляетмониторинга.интерфейсыСхемадляработыдругихкомпонентовпланировщикаиеговзаимодействия с другими компонентами изображены на рисунке 2.Рисунок 2Нижнийдрайвер-фильтр(расположенныйнаддрайверомдиска)вызываетпланировщик при приходе и при завершении каждого запроса ввода-вывода.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
