Честное планирование дискового ввода-вывода с учетом разделяемых ресурсов файлового кэша (1187435), страница 8
Текст из файла (страница 8)
При приходезапроса планировщик принимает решение, пропустить ли этот запрос вниз к драйверудиска сразу, на основании типа этого запроса, т.к. задержки некоторых запросов могутприводить к снижению общей производительности системы. Если же запрос непропускается (это верно для большинства запросов), он поступает в распоряжение36планировщика, инижнийдрайвер-фильтр переводитеговсостояниеpending(задержанный) и возвращает управление менеджеру ввода-вывода.Далее соответствующий запросу пакет IRP помещается в одну из очередей запросовсогласно тому, какой процесс является его инициатором.
Имеется выделенная очередь накаждый процесс в системе (и, соответственно, на каждый диск, если в системе имеетсянесколько дисков).На каждый диск в системе в планировщике создается отдельный поток исполнения,который пробуждается при возникновении любого из следующих событий: приход нового запроса ввода-вывода; завершение одного из ранее отправленных вниз запросов; по таймеру; период по умолчанию составляет 100 миллисекунд.После этого, в соответствии с алгоритмом WF2Q+, выбирается активный процесс, и потокпланировщика начинает отправлять вниз запросы из очереди этого процесса.Планировщик предоставляет функции для системы мониторинга, в которыхпересчитываются виртуальные времена на основе использования разделяемых данных вкэше и подгоняются веса процессов на основе битрейтов над кэшем. Кроме того,планировщик предоставляет интерфейс для задания весов процессов.Важным отличием от оригинальной реализации BFQ в ОС Linux является то, что впланировщике для ОС Windows нет необходимости реализовывать алгоритм C-LOOK,используемый для переупорядочивания запросов внутри очередей процессов с цельюоптимизации их геометрии.
Дело в том, что в дисковом стеке ОС Windows этот алгоритмуже реализован, причем в драйвере, расположенном ниже по стеку, чем реализуемыйнами дисковый планировщик.6.5. Сравнение рассмотренных алгоритмов планированияПриведем результаты проведенных тестов, показывающие, что модифицированныйпланировщик дисковой активности на основе BFQ обеспечивает более честноераспределение пропускной способности на уровне приложений по сравнению соригинальным алгоритмом BFQ. Сравнение проводится между тремя планировщиками: NOOP, т.е. используется стандартный планировщик ОС, BFQ-original, реализация оригинального алгоритма BFQ, BFQ-cache-aware, реализация разработанного в ходе данной работе алгоритма,учитывающего наличие файлового кэша.37В ходе тестов некоторое число процессов читают общие данные с диска, причемнекоторые из них считывают фрагменты файлов раньше, чем другие. Таким образом,тесты пока имеют синтетический характер. Кроме того, они в значительно большейстепени отражают влияние фактора разделяемых данных, чем фактора нечестностираспределения ресурса файлового кэша.
Для проведения тестов реальных систем, вкоторых проявляется проблема нечестности использования кэша, в частности, системвиртуализации, необходима интеграция планировщика в эти системы виртуализации, чтопредставляет собой отдельную инженерную задачу.6.5.1. Честность распределения пропускной способности надфайловым кэшемНа рисунке 3 изображен график сравнения показателей нечестности распределенияпропускной способности на уровне приложений (квадратичное относительное отклонениеот идеального распределения) для рассмотренных алгоритмов при различном числечитающих разделяемые данные процессов.Рисунок 3Из графиков видно, что модифицированный алгоритм обеспечивает более честноераспределение битрейтов на уровне приложений.386.5.2.
Общая производительность дисковой подсистемыНа рисунке 4 изображен график сравнения суммарной пропускной способностидисковой подсистемы (совокупная пропускная способность диска и файлового кэша,мегабайт в секунду) для рассмотренных алгоритмов при различном числе читающихразделяемые данные процессов.Рисунок 4Из графиков видно, что падение общей производительности дисковой подсистемыпри использовании модифицированного алгоритма является незначительным.397. Заключение. Результаты и пути дальнейшего развитияЦелью данной работы являлось создание алгоритмы планирования дисковойактивности, обеспечивающего честность распределения ресурсов дискового ввода-выводана уровне приложений, а не только на уровне диска.В рамках работы было проведено исследование существующих алгоритмов честныхдисковых планировщиков.
Был сделан вывод о том, что существующие решения неучитывают наличие разделяемого между различными процессами ресурса дисковойподсистемы – файлового кэша. На основании этого была поставлена задача построениячестного дискового планировщика, который учитывает использование процессами этогоразделяемого ресурса.Для решения поставленной задачи было предложено взять уже существующийалгоритм планирования для использования в качестве базового (на уровне диска) и внестив него некоторые модификации для корректного учета кэшированной дисковойактивности. В качестве базового алгоритма был выбран BFQ, и был разработан способ егокорректировки для обеспечения честности на уровне файлового кэша.
Был реализованпрототип разработанного алгоритма для операционной системы Windows.Среди возможных путей дальнейшего развития проекта можно отметить следующие. Тестирование реализованного прототипа на реальных системах – серверах сбольшим количеством контейнеров или виртуальных машин с общими данными. Доработка предложенного алгоритма подстройки весов процессов в планировщикена уровне диска с целью минимизации нечестности на уровне кэша, в частности,поиск других возможных метрик для нечестности распределения пропускнойспособности дисковой подсистемы. Учет аппаратного дискового кэша в алгоритме планировщика; построениенеобходимой для этого в силу прозрачности дискового кэша для операционнойсистемы его вероятностной модели. Учет внутреннего дискового планировщика в алгоритме планирования.40Список использованных источников1.P. Valente, F.
Checconi. High throughput disk scheduling with fair bandwidth distribution.// IEEE Transactions on Computers, 2010.2.P. Valente. New version of BFQ, benchmark suite and experimental results.[Электронный ресурс]http://algo.ing.unimo.it/people/paolo/disk_sched/bf1-v1-suite-results.pdf3.P. Valente, M. Andreolini. Improving Application Responsiveness with the BFQ Disk I/OScheduler.
// Proceedings of the 5th Annual International Systems and Storage Conference(SYSTOR ’12). ACM, 2012.4.J.C.R. Bennett, H. Zhang. Hierarchical packet fair queueing algorithms.// IEEE/ACM Transactions on Networking, 1997.5.B.L. Worthington, G.R. Ganger, Y.N. Patt. Scheduling algorithms for modern disk drives.// SIGMETRICS ’94, 1994.6.S. Iyer, P.
Druschel. Anticipatory Scheduling: A Disk Scheduling Framework to OvercomeDeceptive Idleness in Synchronous I/O. // 18th ACM SOSP, 2001.7.A.L.N. Reddy, J. Wyllie. Disk scheduling in a multimedia I/O system. // MULTIMEDIA ’93:Proceedings of the first ACM international conference on Multimedia. ACM, 1993.8.A.K. Parekh, R.G. Gallager. A generalized processor sharing approach to flow control inintegrated services networks: The single-node case.
// IEEE/ACM Transactionson Networking, 1993.9.M. Shreedhar, G. Varghese. Efficient Fair Queueing Using Deficit Round Robin.// IEEE/ACM Transactions on Networking, 1996.10. H.P. Chang, R.I. Chang, W.K. Shih, R.C. Chang. Real-Time Disk Scheduling with on-DiskCache Conscious. Lecture Notes in Computer Science, 2003.11. D. Solomon, M. Russinovich. Windows Internals, 6th edition.
Microsoft Press, 2012.12. D. Probert. Lectures on Windows Kernel at the University of Tokyo.[Электронный ресурс]http://i-web.i.u-tokyo.ac.jp/edu/training/ss/lecture/new-documents/Lectures13. Microsoft. Windows Research Kernel. [Электронный ресурс]http://www.microsoft.com/education/facultyconnection/articles/articledetails.aspx?cid=241614. Love R. Linux Kernel Development. 3rd edition. Addison-Wesley, 2010.15.
Linux Kernel Documentation. CFQ (Complete Fairness Queueing). [Электронный ресурс]https://www.kernel.org/doc/Documentation/block/cfq-iosched.txt4116. Linux Kernel Documentation. Block I/O Controller. [Электронный ресурс]https://www.kernel.org/doc/Documentation/cgroups/blkio-controller.txt17. G.
Thelen, M. Lespinasse. Shared-memory accounting in memory cgroups[Электронный ресурс]https://lwn.net/Articles/51654118. Linux Kernel Documentation. Memory Resource Controller. [Электронный ресурс]https://www.kernel.org/doc/Documentation/cgroups/memory.txt19. Храбров А.В., Рубанова Ю.В. Мониторинг дисковой активности в ОС Windows.// Труды 54-й научной конференции МФТИ «Проблемы фундаментальных иприкладных естественных и технических наук в современном информационномобществе», 2011.20.
Храбров А.В., Рубанова Ю.В. Планирование ресурсов дискового ввода-выводав ОС Windows. // Труды 55-й научной конференции МФТИ «Проблемыфундаментальных и прикладных естественных и технических наук в современноминформационном обществе», 2012.42.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
