Разработка честного алгоритма дискового планировщика для OC Windows (1187424), страница 5
Текст из файла (страница 5)
В этот промежуток времени честность нарушается.Однако процессы с большим бюджетом будут редко выбираться BFQ в качестве активных,поэтому в среднем на больших интервалах времени честность сохраняется.Один из лучших честных планировщиков на сегодняшний день – CFQ, дисковыйпланировщик Linux по умолчанию. Как и BFQ, он отдает диск в пользование толькоодномупроцессу(активному),чтопомогаетувеличитьсуммарнуюпропускнуюспособность диска, т.к. головке диска приходится меньше перемещаться между запросамина диске . Однако CFQ отдает диск процессу на фиксированный интервал времени, а не нафиксированное значение бюджета, как BFQ.
Это может сильно сказываться на честности,т.к. за один и тот же интервал времени процессы могут записать или прочитать абсолютноразное количество байт. В частности, если процесс читает из разных мест, удаленных другот друга, то большая часть времени может уйти только на перемещение головки диска. CFQобслуживает процессы по алгоритму Round-Robin. Это означает, что в худшем случаезапросы будет исполнены с задержкой O(N), где N – количество процессов, желающихполучить доступ к диску. Задержка, зависящая от количества процессов, недопустима впользовательских системах, т.к.
с ростом числа процессов задержки неограниченно растут.6.2. Гарантии задержек исполнения запросовВторым существенным преимуществом BFQ является его гарантии по времени.Утверждается, что для любого пришедшего запроса промежуток времени от момента егоприхода до начала его исполнения не превышает:(2)где– размер j-го запроса в очереди i-го процесса,19– задержка j-го запроса в очереди i-го процесса,– суммарная пропускная способность диска.Как нетрудно видеть, значениене зависит от времени и от поведения другихпроцессов и не накапливается со временем. Так же, как и гарантии честности, это оченьхороший результат для дискового планировщика.
В Linux ввиду ограничений намаксимальный размер запроса в системеи относительно маленьких значениях(128 Кб) значение максимальной задержкине превышает 0,7 секунды, чтоудовлетворяет требованиям аудио и видео приложений.В то же времязависит от максимального бюджета, присвоенного i-муприложению. Аудио и видео приложения выполняют маленькие периодические запросы,что позволяет присвоить им маленькое значение бюджета. Поэтому максимальная задержкадля таких приложений маленькая, что позволяет аудио и видео приложениям работать беззадержек независимо от активности других приложений.
Это свойство важно дляпользователей.Аналогичнымсвойствомобладаютreal-timeпланировщики,которыепереупорядочивают запросы на основе отметок времени. Однако они зачастую не могутдать как гарантии честности, так и высокую суммарную пропускную способность диска.6.3. Проблема отложенного прихода (delayed arrival)Проблема отложенного прихода или delayed arrival касается планировщиков, которыераспределяют запросы на основе отметок времени (timestamp). В момент, когда запросприходит к планировщику, тот может быть занят, например, обработкой другого запроса. Вэтом случае планировщик обработает событие о том, что пришел новый запрос, позже, чемзапрос фактически пришел, и, как следствие, поставит ему более позднюю отметкувремени.
Таким образом, запрос начнет и закончит исполняться позже, чем должен был всоответствии с честным распределением диска. Если запрос синхронный, то следующий заним синхронный запрос также придет позже. В результате битрейт этого процессаснижается, и гарантии битрейта нарушаются.В BFQ эта проблема решается следующим образом:если запрос приходит отактивного приложения, то его отметка времени его прихода считается равной времениокончания предыдущего исполненного запроса. Таким образом, отметки времени сдвинутыназад по сравнению с текущим моментом времени и более корректно отражают времяприхода данного запроса [1].206.4. Проблема обманчивого бездействия (deceptive idleness)В алгоритме BFQ учтено, что если процесс посылает синхронные запросы, топланировщику не придет новый запрос, пока не исполнится предыдущий.
При этом сразупосле того, как запрос отправлен диску, планировщик может ошибочно посчитать, чтопроцесс больше не хочет исполнять дисковую активность, и выбрать в качестве активногодругой процесс. Для того чтобы избежать такой ситуации, в BFQ введен интервал времениTwait . Когда последний запрос из очереди irp процесса был отправлен диску, BFQ ждет втечение Twait , не придет ли планировщику новый запрос от этого процесса. Это оченьэффективный способ увеличить битрейт процесса с синхронными запросами, не смотря нато, что диск простаивает во время ожидания Twait .
Во-первых, BFQ не приходится выбиратьновый активный процесс после исполнения каждого синхронного запроса. Во-вторых,каждый выбор активного процесса часто сопровождается перемещением головки диска набольшое расстояние. Исполняя большезапросов от одного процесса подряд, мы вбольшинстве случаев сокращаем расстояние, которое надо преодолеть головке диска. Втретьих, процесс не ждет, пока его снова выберут активным для исполнения следующегосинхронного запроса. Т.е.
повышается время ответа приложения. Однако к выбору времениTwait нужно подходить осторожно, т.к. в этот интервал времени диск простаивает, и прибольшом Twait можно существенно снизить пропускную способность диска.6.5. Условия гарантий честностиОдной из особенностей BFQ является то, что бюджет, основной параметр, влияющийна время ответа приложения, не влияет на честность распределения дискового ресурса. Каквидно из формулы (1), на гарантии четности влияют только максимумы бюджетов иразмеров запросов. Это свойство будет использоваться в данной работе.
Благодаря этомусвойству, процессу можно присваивать любое значение бюджета, не превышающеемаксимум, не заботясь о соблюдении гарантий честности.7. Недостатки алгоритма BFQКак и любой планировщик, BFQ обладает некоторыми недостатками и ограничениямиприменения. BFQ разрабатывался в первую очередь для машин с постоянной и высокойдисковой активностью, где честность распределения ресурсов важнее, чем время ответаприложения.BFQхорошосправляетсяспоставленнымизадачами,однаконапользовательских машинах, где важно быстрое реагирование системы на действияпользователя, у этого планировщика заметны существенные недостатки.7.1. Продолжительное ожидание синхронных запросов21В Windows введение параметра Twait , спасающего BFQ от проблемы обманчивогобездействия или deceptive idleness, не так эффективно, как в Linux.
Когда запросисполнился, обработка события, что запрос исполнен, выполняется не сразу, а позже.Максимальная задержка исполнения этого обработчика составляет 16 мс. Таким образом,чтобы дождаться следующего синхронного запроса, нужно не только подождать, покаисполнится текущий запрос и процесс отреагирует на это событие, но и дождаться DPC.Стоит также учитывать, что у диска есть внутренний планировщик запросов и очередьзапросов, поэтому нельзя гарантировать, что запрос начнет исполняться, как только BFQпошлет его вниз. Для того, чтобы гарантировать, что через интервал времени Twait процесспришлет следующий синхронный запрос, нужно, чтобы Twait удовлетворяло, что как минимум больше 16 мс.Однако такое большое время простоя диска после каждого синхронного запроса негативноотражается на суммарной пропускной способности диска и времени ответа приложения.7.2.
Обратный эффект честностиЧестность – основное свойство, которого мы стремимся добиться, разрабатываяпланировщик. Однако не менее важным свойством для пользователя является время ответаприложений, ради которого можно временно пожертвовать честностью, и BFQ неучитывает данный факт. Один из наиболее часто встречающихся сценариев, где этозаметно, -- запуск приложения.
Приложению на старте нужно считать какие-либо данные,необходимые ей для дальнейшей работы. При этом другие процессы также конкурируют задисковый ресурс. Эксперименты показывают, что на системе без планировщикаприложение запустится гораздо быстрее, чем на системе с честным планировщиком, т.к.
впоследнем случае дисковая активность будет распределяться честно, и приложениеполучит только гарантированную ему долю пропускной способности. Такое поведениенедопустимо на пользовательских системах.7.3. Учитывает геометрию жесткого диска.В алгоритме BFQ запросы внутри очереди каждого процесса переупорядочиваются всоответствии с алгоритмом C-LOOK. Цель такого приема – расположить запросы в очередитак, чтобы головка диска совершала как можно меньше перемещений,и запросыисполнялись быстрее. Однако такой подход совершенно не оправдывает себя. Всесовременныежесткиедискиимеютвнутреннююочередь,вкоторойзапросыпереупорядочиваются с учетом геометрии (технология NCQ [19] [20] для SATA устройств).Таким образом, разрабатывая планировщик дисковой активности, мы избавлены отнеобходимости заботиться о геометрии. Стоит упомянуть, что переупорядочиваниезапросов во внутренней очереди диска может влиять как на гарантии честности, так и на22задержки выполнения запросов, однако это проблема касается всех планировщиков, а нетолько BFQ.7.4.
Стремление сократить бюджет процессуЕсли процесс не расходует весь бюджет за период активности, то в следующий раз BFQприсвоит ему бюджет, равный количеству использованного бюджета в предыдущемпериоде. С одной стороны это обусловлено тем, что чем меньше бюджет процесса, темменьшие задержки будут испытывать как запросы данного процесса, так и запросы другихпроцессов. С другой стороны, урезать бюджет, оставляя ровно столько, сколько былоиспользовано в предыдущий раз, нерационально.
Весьма вероятно, что в следующий разпроцессу понадобится исполнить больше запросов, и учитывая медленную реакцию BFQ наувеличение дисковой активности, такой подход вызовет еще более заметное увеличениевремени ответа приложения.Рассмотрим один из сценариев, где проявляется этот недостаток. Допусти м, процессстабильно много читает или пишет. Однако в один из периодов активности он записалменьше, чем в предыдущие.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
