Разработка честного алгоритма дискового планировщика для OC Windows (1187424), страница 4
Текст из файла (страница 4)
Также мы можем гарантировать, что операции записи не будутпрепятствовать выполнению операций чтения, т.е. минимизируются важные дляпроизводительности задержки операций чтения.Такой алгоритм подходит для систем, где количество операций чтения превышаетколичество операций записи, например, базы данных. В операционных системах такойалгоритм малоприменим. Дело в том, что из-за большого приоритета чтения в ситуации,когда разные запросы на чтение приходят один за другим,выполнение последнихзапускается сразу же. Для каждой операции чтения запускается операция п оиска.
Такимобразом, большой приоритет операций чтения приводит к малым возможностям пооптимальному упорядочиванию запросов, что влечет большие задержки.144.5.4. Прогнозирующий планировщик (Anticipatory I/O scheduler)Предназначен для минимизации задержек чтения и во том же время обеспечениемхорошей общей производительности. Данный планировщик, как и Deadline, использует триочереди запросов и учитывает время ожидания каждого из них. Отличительной жеособенностью его является использование эвристического прогнозирования (anticipationheuristic), направленного на исключения обилия поступающих друг за другом операцийчтения.Алгоритм заключается в следующем:Когда планировщик получает запрос на чтение, он его выполняет.
Далее anticipatoryждет некоторое время (около 6 миллисекунд). Наиболее вероятно, что за это время придетеще несколько запросов на чтение. Вместо того, чтобы как Deadline, отправлять навыполнение практически следующий непосредственно за ним запрос на чтение, anticipatoryвыбирает из пришедших за 6 миллисекунд запросов те, которые обращены к соседнимсекторам диска, и отправляет их в очередь диспетчеризации. Таким образом, оносуществляет упорядочивание запросов так, чтобы минимизировать скачки головки подиску.В результате если за время ожидания придут запросы к соседним секторам, затраты наожидания окупаются за счет предотвращения двух лишних операций поиска. Если же за этовремя не было никакой дисковой активности к соседним секторам, то время ожиданияпросто теряется.Более того, планировщик ведет статистику операций ввода-вывода по каждомупроцессу.
Анализируя полученные данные, он пытается предсказать действия приложения.При удаче в предсказаниях, планировщик может существенно снизить затраты на поиск, атакже больше уделить внимание тем запросам, которые хуже всего сказываются напроизводительности системы.Недостаток планировщика в том, что задержки каждого конкретного процесса могутбыть непростительно велики.Данный планировщик хорошо работает на большинстве систем. Однако для некоторыхсистем, рассчитанных на большое количество поиска (например, серверы баз данных),anticipatory не дает преимущества.4.5.5. Сompletely Fair Queeing (CFQ)Является планировщиком по умолчанию начиная с версии 2.6.9. Как следует изназвания, этот планировщик является честным.Принцип работы CFQ в корне отличается от упомянутых выше.
В данномпланировщике для каждого процесса, отправляющего запросы ввода-вывода, создается15отдельная очередь, куда и складываются запросы от соответствующего процесса. Внутрикаждой очереди запросы объединяются и сортируются. Таким образом, CFQ, как и другиепланировщики, поддерживает свои очереди в упорядоченном состоянии.Далее, CFQ берет из одной из очередей несколько запросов (по умолчанию 4), которыеи отправляет на исполнение. Затем планировщик переходит к следующей очереди. Так онобходит очереди всех процессов по кругу.Преимуществом такого планировщика в том, что можно гарантировать отсутствиебольших задержек для каждого конкретного процесса. Это особенно важно длямультимедийных приложений.Алгоритм подходит для систем, где многим приложениям требуется доступ к диску,как, например, в привычных нам операционных системах.
Стоит отметить, что онпозволяет получить хорошую производительность на разных типах нагрузки.5.Алгоритм BFQВ качестве первого этапа данной работы было решено реализовать для ОС Windowsодин из существующих планировщиков и исследовать его преимущества и недостатки. Входе данной работы для реализации в Windows был выбран алгоритм Budget Fair Queuing(BFQ). Это наилучший честный алгоритм планирования на данный момент, несмотря на всеего недостатки.Алгоритм BFQ относится к классу честных. Он предоставляет гарантии того, чтокаждый процесс получит долю пропускной способности диска, независимо от поведениядругих процессов. Для BFQ доказано, что при его использовании запросы исполняются ненамного позже, чем в идеальной машине, и что каждый процесс получает долю пропускнойспособности диска, равную весу.BFQ разрабатывался как замена CFQ – планировщику Linux по умолчанию нанастоящий момент.
По результатам тестов BFQ показывает более хороший результат начтении файлов, чем CFQ. Скорость чтения с BFQ была выше, чем с CFQ, и отклонениебитрейта от среднего значения не превышало 3% против 28% у CFQ в условияходновременного запуска нескольких процессов, исполняющих дисковую активность. Вчастности, с BFQ вещающий VLC видеосервер смог обслужить 24 параллельных потока безощутимой потери пакетов, против 15 с CFQ [4]. В марте 2014 было объявлено, чторазработчики готовят код для слияния с основной веткой ядра Linux [3].BFQ работает на основе распределения бюджетов. Бюджет – количество байт, которыеможет прочитать или записать процесс за один раз.
Когда у процесса появляются запросы кдиску, BFQ присваивает ему некоторое значение бюджета. BFQ выбирает какой-либо16процесс из списка тех, у кого есть запросы к диску (в дальнейшем будем называть егоактивным процессом). Этот процесс будет исполнять активность в течение следующегопромежутка времени. В соответствии с BFQ, в каждый момент времени работать с дискомможет только один процесс. Если бюджет процесса израсходован или у процесса большенет запросов к диску, процесс прекращает быть активным, и BFQ выбирает следующийактивный процесс.Рассмотрим подробнее, как работает алгоритм BFQ. Первым шагом является выборпроцесса, который будет следующим исполнять свои запросы, т.н.
активного процесса. Дляэтой цели BFQ использует алгоритм Worst-case Fair Weighted Fair Queuing (WF2 Q+) [16][17] [18], , который осуществляет выбор активного процесса на основе его веса и отметоквремени.Алгоритм WF2 Q+опирается на понятие идеальной системы. Алгоритм выбираетследующий активный процесс из тех процессов, запросы которых уже начали быисполняться к этому моменту в идеальной системе, причем выбирает тот процесс, которыйраньше закончил бы свою деятельность в идеальной системе. Для этого в WF2 Q+ введенопонятие виртуального времени. Виртуальное время измеряется в количестве исполненнойна данном диске дисковой активности. Также для каждого процесса считаетсяи– время, когда начнут и закончат исполнение все запросы, находящиеся вочереди запросов данного процесса.ипересчитываются каждыйраз, когда процесс попадает в очередь ожидающих, т.е. когда у него появляются запросы кдиску.равно времени прихода последнего исполненного запроса от этогопроцесса (это помогает избежать проблемы обманчивого бездействия (deceptive idleness), окоторой пойдет речь ниже).
Finish time рассчитывается по формуле, где—вес процесса, а– размер дисковойактивности, которую процессисполнит.Когдапроцесспопадаетвочередьожидающих,считаетсяравнымт.к.бюджету,этомаксимальное количество байт,которыепроцессисполнит,когда WF2 Q+ выберет его вследующий раз. После того, какРисунок 217WF2 Q+ выбрал этот процесс, в случае если процесс израсходовал не весь свой бюджет,корректируется с учетом того, что величинасоставила меньше, чемзначение бюджета.После выбора активного процесса наступает стадия выбора бюджета для активногопроцесса.
Эта и есть стадия, введенная BFQ, и отличающая его от WF2 Q+ в чистом виде. ВBFQ алгоритм выбора бюджета достаточно прост: если запросы в очереди процессакончились до того, как был полностью использован бюджет, то в следующем периодеактивности бюджет процесса будет урезан на величину, равную неиспользованномубюджету. Если же после использования всего бюджета в очереди еще остались запросы, тов следующем периоде активности бюджет будет увеличен на некоторую константу, ноне более чем максимальное значение бюджета.После выбора величины бюджета запросы, помещающиеся в бюджет (т.е. сумма ихразмеров не превышает бюджет), отправляются к диску, и процесс перестает считатьсяактивным.
WF2 Q+ корректирует метки времени, если процесс использовал не весь свойбюджет, и выбирает следующий активный процесс. Запросам предыдущего процесса,которые не поместились в бюджет, придется ждать, пока WF2 Q+ выберет этот процессследующий раз.Сложность алгоритма WF2 Q+, лежащего в основе BFQ, – O(log N) в худшем случае, гдеN – количество процессов, конкурирующих за дисковый ресурс. Сложность операций,осуществляемых BFQ при приходе нового запроса или выборе активного процесса и работес ним, – O(1). Таким образом, сложность BFQ составляет O(log N) в худшем случае.Преимущества BFQ6.АлгоритмBFQпостроентаким образом,чтобыизбежать многих проблем,встречающихся у других планировщиков.6.1.Соблюдение гарантий честностиВ статье [1] утверждается, что для любого интервала времени, в течение которого упроцесса есть запросы к диску, выполнено следующее:(где((()(1)— вес i-го процесса,) – количество байт, прочитанных или записанных на диск за интервал времени) в идеальной машине,(()) – количество байт, прочитанных или записанных на диск за интервал времени) i-м процессом на реальной машине,– максимальный размер бюджета,18– максимальный размер бюджета для i-го процесса,—максимальный размер запроса.Таким образом, первое преимущество BFQ состоит в том, что он гарантирует,записанное или прочитанное количество байт конкретного процесса в реальной машине) отличается от аналогичной величины() в идеальной машине не более,(чем на фиксированную величину, не зависящую от поведения других процессов.
Этосильное утверждение. Учитывая, что другие планировщики не могут дать такие гарантии,можно назвать BFQ наиболее честным из существующих планировщиков.Примечательно также, что BFQ гарантирует, что процесс получит свою долюпропускной способности диска вне зависимости от его бюджета. С одной стороны, процессс большим бюджетом долго исполняет свою дисковую активность, не давая другимпроцессам исполнять свои запросы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
