Разработка честного алгоритма дискового планировщика для OC Windows

Министерство образования и науки Российской ФедерацииМОСКОВСКИЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ(государственный университет)ФАКУЛЬТЕТ УПРАВЛЕНИЯ И ПРИКЛАДНОЙ МАТЕМАТИКИКАФЕДРА ТЕОРЕТИЧЕСКОЙ И ПРИКЛАДНОЙ ИНФОРМАТИКИ(Специализация 010956 «Математические и информационные технологии»)РАЗРАБОТКА ЧЕСТНОГО АЛГОРИТМА ДИСКОВОГОПЛАНИРОВЩИКА ДЛЯ ОС WINDOWS НА ОСНОВЕ ВЫДЕЛЕНИЯБЮДЖЕТОВ С ОБЕСПЕЧЕНИЕМ КАЧЕСТВА ОБСЛУЖИВАНИЯ НАКОРОТКИХ ВРЕМЕННЫХ ИНТЕРВАЛАХМагистерская диссертациястудентки 873 группыРубановой Юлии ВикторовныНаучный руководительКостюшко А.В.г. Долгопрудный2014Оглавление1.ВВЕДЕНИЕ ............................................................................................................................22.ОСНОВНЫЕ ПОНЯТИЯ ....................................................................................................23.ПОСТАНОВКА ЗАДАЧИ ...................................................................................................44.СУЩЕСТВУЮЩИЕ РЕШЕНИЯ ДЛЯ ПЛАНИРОВАНИЯ I/O.

...............................56.АЛГОРИТМ BFQ ...............................................................................................................167.ПРЕИМУЩЕСТВА BFQ...................................................................................................188.НЕДОСТАТКИ АЛГОРИТМА BFQ...............................................................................219.ОСОБЕННОСТИ РЕАЛИЗАЦИИ BFQ В ОС WINDOWS.........................................2510.МОДИФИЦИРОВАННЫЙ BFQ (MBFQ) .....................................................................2910.1.

ЦЕЛИ СОЗДАНИЯ MBFQ.........................................................................................................3010.2. ПРЕДПОЛОЖЕНИЯ ...................................................................................................................3110.3. СХЕМА РАБОТЫ ПЛАНИРОВЩИКА ..........................................................................................3110.4. АЛГОРИТМ ..............................................................................................................................3210.5. МАТЕМАТИЧЕСКОЕ ОБОСНОВАНИЕ ........................................................................................3310.6. О ЦЕНКА СЛОЖНОСТИ .............................................................................................................4710.7. ПРИЕМЫ, ЗАИМСТВОВАННЫЕ ИЗ BFQ....................................................................................4711.СРАВНЕНИЕ МОДИФИЦИРОВАННОГО BFQ И ОРИГИНАЛЬНОГО BFQ НАI/O ТЕСТАХ.........................................................................................................................4812.ДАЛЬНЕЙШЕЕ РАЗВИТИЕ РАБОТЫ .........................................................................5413.ЗАКЛЮЧЕНИЕ ..................................................................................................................57СПИСОК ЛИТЕРАТУРЫ ..........................................................................................................5711.

ВведениеДиск – самый медленный вид памяти современных компьютеров. Зачастуюбыстродействие приложений определяется именно скоростью взаимодействия системы сдиском.Сразвитием интернета проблема низкой производительности дисковойподсистемы стала особенно актуальной, т.к. веб-серверу нужно постоянно читать с дискабольшие объемы данных, в то время как пользователи, запрашивающие данные у вебсервера, не готовы ждать продолжительное время.Предметом внимания в данной работе является планирование ввода-вывода в дисковойподсистеме ОС Windows. До сих пор для данной системы не создано программ, способныхэффективно оптимизировать запросы ввода-вывода. Это связано, в первую очередь, сосложной структурой этой ОС, а также с закрытостью ее кода. Первой задачей даннойработы является реализация одного из существующих алгоритмов планирования для ОСWindows.Существует множество алгоритмов планирования ввода-вывода.

Лучшие из них сточки зрения обеспечения честности [5], такие как BFQ [1] и CFQ [6], реализованы под ОСLinux и широко применяются для оптимизации дисковой активности на серверныхсистемах. Однако они обладают существенными недостатками. Будучи разработаннымидля серверных систем, эти алгоритмы не учитывают, комфортно ли пользователю будетработать на машине с таким планировщиком.Вторая и наиболее важная цель данной работы – разработать планировщик дисковойактивности в ОС Windows, подходящий для работы на машине пользователя.2. Основные понятияВведем формальные понятия, которыми будем оперировать в представленной работе.Когда какое-либо приложение желает считать или записать что-то на диск, оноформирует запрос (в случае Windows это IRP пакет), посылаемый в файловую систему,которая в свою очередь пересылает его к диску, если запрашиваемой страницы нет в кэше.Приложения могутотправлять запросыввода-вывода двух основных типов:синхронные и асинхронные. Синхронный ввод-вывод.При этом типе запроса приложение ждет, пока запрос не будет выполнен и не вернулкод статуса завершения операции ввода-вывода.

После такой операции полученные данныемогут быть немедленно использованы. Большинство приложений использует запросыименно такого типа.2 Асинхронный ввод-выводПозволяет приложению отправить запрос на ввод-вывод, но не дожидаться полученияданных с устройства. Это позволяет решать другие задачи, пока выполняется операцияввода-вывода. Очевидным минусом является невозможность использовать данные с дисканемедленно.

Также при этом нужно следить за тем, чтобы не было обращений к данным доих получения с диска.Битрейтом процесса называется скорость, с которой процесс читает или пишет данныена диск. Механизм жесткого диска устроен так, что время чтения или записи одного и тогоже количества байт может сильно меняться в зависимости от текущего местонахожденияголовки диска, от того, шлет ли процесс запросы с последовательным расположением надиске или нет, от того, насколько часто диск переключается на исполнение запросов отдругого процесса, и других факторов.Чтобы увеличить суммарный битрейт и битрейт каждого процесса в отдельности,применяются планировщики дисковой активности. В алгоритмах планирования каждомупроцессу сопоставлено некоторое значение, называемое весом. При честном планированиипроцесс получает долю пропускной способности диска, соответствующую его весу.В алгоритмах с распределением бюджета BFQ [1] и MBFQ, описание которогоприводится в данной работе, планировщик отдает каждому процессу диск на некотороевремя, т.е.

в течение некоторого периода времени на диске исполняются запросы только отэтого процесса. Назовем такие периоды периодами активности, а процесс, запросыкоторого исполняются на диске в данный момент – активными.Все планировщики дисковой активности стремятся, чтобы пропускная способностьдиска распределялась между процессами так же, как в идеальной системе [5]. Идеальнойсистемой называется система, в которой дисковая активность исполняется неп рерывно ичетко в соответствии с весами процессов и в которой несколько процессов могутодновременно исполнять свои запросы к диску.В идеальной машине предполагается следующее:Запросы приходят не в виде пакетов, а в виде непрерывного потока данных.Одновременно диск может читать или писать данные от нескольких процессов .Каждый процесс получает долю максимальной пропускной способности диска, равнуюего весу.Такая концепция носит название Generalized Process Sharing (GPS) [5].

К сожалению,существующие жесткие диски не отвечают этим требованиям, потому что дисковаяактивность исполняется пакетами, а не непрерывно. Тем не менее, планировщики дисковойактивности позволяют в реальных условиях добиться того, что запросы исполняются не3намного позже, чем в идеальной машине, и что каждый процесс получает долю пропускнойспособности диска, равную весу.3. Постановка задачиОС Windows – одна из самых популярных и используемых операционных систем.Однако на сегодняшний день в ней нет дискового планировщика, который бы обеспечивалкачествообслуживанияприложений.Подобеспечениемкачестваобслуживанияподразумеваются гарантии, что каждый процесс получит свою долю пропускнойспособности диска в течение определенного промежутка времени (свойство честности [5])и что каждый отдельно взятый запрос не будет ждать в очереди слишком долго.До версии Windows 7 в ОС Windows применялся планировщик, переупорядочивающийзапросы в соответствии с геометрией, а, начиная с Windows 7, появился так называемыйприоритетный планировщик, который функционирует следующим образом: запросы вводавывода разделяются на три категории, согласно их приоритетности [7].

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