Разработка честного алгоритма дискового планировщика для OC Windows (1187424)
Текст из файла
Министерство образования и науки Российской ФедерацииМОСКОВСКИЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ(государственный университет)ФАКУЛЬТЕТ УПРАВЛЕНИЯ И ПРИКЛАДНОЙ МАТЕМАТИКИКАФЕДРА ТЕОРЕТИЧЕСКОЙ И ПРИКЛАДНОЙ ИНФОРМАТИКИ(Специализация 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].
Самый высокийприоритет получают процессы, для которых критичны задержки в обслуживании,например, процесс медиа-плеера, и который нужно исполнить вне зависимости от другихисполняемых процессов. Самый маленький приоритет имеют системные службы, которыепредпочтительней и сполнять во время простоя, чтобы они не задерживали обработкузапросов от процессов, с которыми на данный момент работает пользователь. Планировщикследит, чтобы в первую очередь исполнялись запросы с более высоким приоритетом.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
