Честное планирование дискового ввода-вывода с учетом разделяемых ресурсов файлового кэша (1187435)
Текст из файла
Министерство образования и науки Российской ФедерацииМОСКОВСКИЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ(государственный университет)ФАКУЛЬТЕТ УПРАВЛЕНИЯ И ПРИКЛАДНОЙ МАТЕМАТИКИКАФЕДРА ТЕОРЕТИЧЕСКОЙ И ПРИКЛАДНОЙ ИНФОРМАТИКИ(Специализация 010956«Математические и информационные технологии»)ЧЕСТНОЕ ПЛАНИРОВАНИЕ ДИСКОВОГО ВВОДА-ВЫВОДА СУЧЕТОМ РАЗДЕЛЯЕМЫХ РЕСУРСОВ ФАЙЛОВОГО КЭШАМагистерская диссертациястудента 873 группыХраброва Алексея ВикторовичаНаучный руководительКостюшко А.В.г. Долгопрудный2014Содержание1. Введение ....................................................................................................................................
42. Цели и задачи ............................................................................................................................ 53. Обзор предметной области и ее проблематики ..................................................................... 63.1. Системы хранения данных и проблемы их производительности ................................. 63.2. «Традиционные» дисковые планировщики .................................................................... 73.2.1. Планировщики для максимизации пропускной способности диска .................... 83.2.2. Планировщики для ограничения времени ожидания исполнения запроса ......... 93.3. Проблема честного планирования доступа к диску и существующие решения ....... 103.3.1.
Простейшие алгоритмы ........................................................................................... 103.3.2. Алгоритм CFQ – Completely Fair Queueing ............................................................ 103.3.3. Алгоритм BFQ – Budget Fair Queueing ................................................................... 113.4. Файловый кэш .................................................................................................................. 123.5. Аппаратный дисковый кэш............................................................................................. 134. Проблема учета разделяемых ресурсов файлового кэша в дисковом планировщике .....
154.1. Проблема нечестного распределения ресурса файлового кэша.................................. 154.2. Проблема учета разделяемых данных в файловом кэше ............................................. 164.3. Примеры проявления в реальных системах ..................................................................
164.4. Обзор аналогичной проблемы учета разделяемой памяти .......................................... 175. Создание алгоритма планирования для учета использования файлового кэша ............... 195.1. Постановка задачи ........................................................................................................... 195.1.1. Математическая модель дисковой подсистемы .................................................... 195.1.2. Определения характеристик дискового планировщика........................................
215.1.3. Цель корректировки алгоритма планирования ...................................................... 225.2. Анализ возможности расположения планировщика над файловым кэшем .............. 235.3. Динамическая корректировка весов процессов на уровне диска ............................... 245.3.1.
Описание метода корректировки ............................................................................ 245.3.2. Оценки алгоритмической сложности ..................................................................... 255.4. Обоснование выбора алгоритма на основе BFQ в качестве базового ....................... 255.5. Корректировка BFQ для учета разделяемых данных в файловом кэше ................... 265.5.1. Описание метода корректировки ............................................................................
265.5.2. Свойства полученного алгоритма ........................................................................... 275.5.3. Оценки алгоритмической сложности ..................................................................... 2726. Реализация альтернативного дискового планировщика в ОС Windows ..........................
286.1. Система мониторинга дисковой активности ................................................................ 286.1.1. Общая архитектура ................................................................................................... 296.1.2. Мониторинг кэшированного чтения и чтения memory mapped файлов ............ 306.1.3. Мониторинг кэшированной записи и записи memory mapped файлов .............. 316.1.4. Структуры данных для хранения информации об использовании кэша ............ 326.2. Особенности реализации в ОС Windows .......................................................................
336.3. Общая архитектура системы планирования ................................................................. 356.4. Реализация базового алгоритма планирования BFQ .................................................... 366.5. Сравнение рассмотренных алгоритмов планирования ................................................ 376.5.1. Честность распределения пропускной способности над файловым кэшем .......
386.5.2. Общая производительность дисковой подсистемы .............................................. 397. Заключение. Результаты и пути дальнейшего развития ..................................................... 40Список использованных источников......................................................................................... 4131.
ВведениеОдним из наиболее важных аспектов использования современных вычислительныхсистем является хранение данных. Системы хранения данных должны удовлетворятьопределенным требованиям надежности, гибкости и производительности.Основными устройствами хранения цифровой информации являются жесткие диски(HDD – Hard Disk Drive).
Работа с ними происходит медленно (на несколько порядковмедленнее обращений к оперативной памяти), что в первую очередь связано с ихмеханическимустройством:дляперемещениясчитывающихголовоккместурасположения нужных данных требуется значительное время (десятки миллисекунд). Впоследние годы получили распространение также SSD-диски (Solid State Drive),основанные на flash-памяти и не содержащие никакой механики. Они работаютзначительно быстрее HDD, но все же гораздо медленнее оперативной памяти.
Поэтомудля систем на их основе в целом характерны те же проблемы производительности, что идля систем с обычными жесткими дисками.Дисковая подсистема зачастую становится наиболее узким местом многих систем,ограничивая скорость их работы.
В частности, это характерно для высоконагруженныхсерверов, а также приложений мультимедиа. Оптимизация производительности дисковоговвода-вывода – одна из важных задач, решаемых разработчиками операционных систем.В частности, было создано множество алгоритмов планирования дисковых операций.Одна из наиболее важных проблем производительности состоит в обеспечениикачества обслуживания для каждого отдельного клиента дисковой подсистемы –приложения, либо виртуальной машины или контейнера в системах виртуализации.Она решается т.н. честными дисковыми планировщиками, которые обеспечиваютраспределение пропускной способности между клиентами в соответствии с некоторымизаданными весами или приоритетами.
В данной работе задача создания честногодискового планировщика решается для ОС Windows.Существующиечестныеалгоритмыпланированиянеучитываютналичиенеотъемлемого компонента дисковой подсистемы ОС – файлового кэша, поэтому дажепри наличии честного распределения пропускной способности на уровне дискараспределение на уровне приложений может быть нечестным.
В данной работепроводится исследование этой проблемы и предлагается метод ее решения.42. Цели и задачиЦелью данной работы является создание алгоритма планирования доступа к диску,обеспечивающегочестностьраспределенияпропускнойспособностидисковойподсистемы на уровне приложений, а не непосредственно на уровне диска, каксуществующие алгоритмы планирования. Предлагается строить алгоритм на основеодного из существующих подходов к планированию, в частности, реализованных всовременных ОС, таких как Linux.Для достижения данной цели требуется решить ряд вспомогательных задач.1.
Выбор существующего честного алгоритма планирования для использования науровне диска. Алгоритм должен быть пригодным для добавления в неговозможности учета использования файлового кэша. Далее будем называть этоталгоритм базовым.2. Модификация выбранного базового алгоритма с целью корректного учетаиспользования файлового кэша. Корректировка должна быть произведена такимобразом, чтобы не ухудшить при этом общую производительность дисковойподсистемы.Полученныйалгоритмдолженбудетобеспечиватьчестноераспределение ресурса дисковой подсистемы над файловым кэшем.3.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
