Разработка честного алгоритма дискового планировщика для OC Windows (1187424), страница 6
Текст из файла (страница 6)
К примеру, при копировании файлов приложениюпонадобилось спросить у пользователя, нужно ли заменять файл, и ждет реакциипользователя. BFQ определяет, что у приложения кончились запросы и урезает емубюджет. Однако в следующем периоде активности приложению снова нужен большойбюджет. Как показано в следующем пункте увеличение битрейта этого приложения можетпроисходить очень долго.7.5. Медленная реакция на увеличение дисковой активностиЕсли процесс израсходовал весь свой бюджет, но в его очереди все еще осталисьзапросы, то BFQ увеличивает ему бюджет на некоторую фиксированную величину(назовем ее) на следующий период активности. Подобный подход порождает главныйнедостаток BFQ, на который жалуются пользователи,медленная реакция системы наувеличение дисковой активности приложения, в частности, медленный старт приложений.Этому способствуют следующие факторы:BFQ увеличивает бюджет приложения на, однако воспользоваться увеличеннымбюджетом процесс может только в следующем периоде активности.
Таким образом,запросам, не успевшим исполниться в предыдущий период активности нужно будет ждатьпорядка()̅, чтобы начать исполняться. Здесь N – число процессов, исполняющихдисковую активность, ̅ — средний бюджет приложений,– суммарная пропускнаяспособность диска. Оценим это значение.
Возьмем количество процессов порядка 10.Средний бюджет процесса порядка 4 *байт, т.е. порядка максимального размер23запроса в OC Windows (более подробно будет пояснено в пункте 9.7). Суммарнаяпропускная способность диска составляетбайт/секунду.)̅(Ясно, что для пользовательского приложения задержки в 1 секунду существенны.Допустим, приложение резко увеличило свою дисковую активность.
Это частовстречающая ситуация, например, когда приложение стартует или сбрасывает результатысвоей деятельности на диск. Если до этого приложение исполняло мало дисковойактивности, что его бюджет будет маленьким (см. пункт 6.4.). Тогда BFQ будетпоследовательно увеличивать бюджет этому процессу наувеличениями будет проходить время порядка() ̅, причем между каждыми. Так, если приложение хочетисполнить в этом периоде активности S байт, то последний запрос из S исполнится через nпериодов активности, где n определяется следующим выражением:()()()откуда n равно:√Время ожидания исполнения последнего запроса составит порядка()̅Допустим, приложение записало или прочитало 100 Кб (активности. Потом ему понадобилось записать 10 Мб (Тогдаи время ожидания составить) за предыдущий период).
Пусть.секунд.Если в очереди процесса после исчерпания бюджета осталось мало запросов (сумма ихразмеров может быть меньше), то бюджет все равно будет увеличен на, несмотряна то, что в этом нет необходимости.Итак, из-за своего подхода к обработке увеличения дисковой активности BFQ страдаетиз-за больших времен задержек между приходом запроса и началом его исполнения, чтоприводит к высокому времени ответ пользовательских приложений.7.6. BFQ не учитывает количество запросов в очереди процессаBFQ не принимает во внимание, сколько запросов в очереди у процесса при подсчетабюджета. Планировщик учитывает только, был ли израсходован в прошлый раз весьбюджет, и если нет, то какая его часть была израсходована. Однако такой подход не верен.24Если в очереди процесса мало запросов, то нет причин давать ему большой бюджет.
Еслиже их много, то имеет смысл дать большой бюджет, т.к. в противном случае процесс невыполнит не все запросы из очереди, и в следующий раз все равно его бюджет необходимобудет увеличить, но процессу нужно будет дождаться, пока его выберут активным вследующий раз (снова увеличивается время ответа приложения).7.7. Невыполнение гарантий задержекГарантии задержек BFQ могут не соблюдаться при некоторых условиях. Допустим, у i-го процесса появились запросы в очереди и так случилось, что егопараметроказался меньше, чем у процесса, который активен в данный момент.В этом случае i-му процессу придется ждать, пока закончит исполнять свои запросыактивный процесс, хотя в идеальной системе его запросы закончили бы исполнятьсяраньше. Активный процесс не израсходовал весь свой бюджет.
Это значит, что ранее этомупроцессу было присвоено значениебольше, чем на самом деле, и, возможно,из-за этого он стал активным позже, чем должен был.Условия, при которых гарантии задержек не выполняются, следуют из алгоритмавыбора активного процесс WF2 Q+.
В данной работе WF2 Q+ используется в неизменномвиде, поэтому эти недостатки остаются.8. Особенности реализации BFQ в ОС WindowsПри реализации BFQ на ОС Windows возникли сложности,связанные в первую очередь с тем, что некоторые предположенияBFQ не выполняются в реальных операционных системах. Такжевозникли проблемы ввиду того, что алгоритм предназначен впервую очередь для Linux, а I/O подсистема Windows в корнеотлична от I/O подсистемы Linux.8.1.
Список процессов не постояненВ реальных системах практически никогда не встречаютсяситуации, когда в течение долгого времени с диском работаютодни и те же процессы. Как правило, процессы обращаются кдиску, затем прекращают свою активность, обращаются снова иРисунок 3т.д. Во время бездействия процесса (в плане дисковой активности)нет необходимости его держать в очереди активных процессов, пересчитывать для негоfinish_time, start_time, бюджет и другие параметры. В тоже время встает вопрос о том, какправильно обработать ситуацию, когда появляется новый инициатор, т.к.
ему нужно25установить бюджет, достаточный для того, чтобы время ответа приложения оставалосьприемлемым, но при этом не нарушалась значительно честность распределения дисковойактивности для других приложений.8.2. У процесса не всегда есть запросы к дискуBFQ гарантирует, что дисковая активность распределяется честно, предполагая, что уинициатора всегда есть запросы к диску, однако это не так. Возникает проблема, какобрабатывать часто встречающую ситуацию, когда у процесса заканчиваются запросы кдиску и в течение долгого времени запросы от этого процесса больше не приходят.8.3. В системе может быть несколько дисковBFQ не подразумевает, что в системе может быть несколько дисков.
При этом скаждым из них нужно обеспечить честность процессов и максимизировать суммарнуюдисковую активность. Самый простой способ достижения этой цели – дать каждому дискуего собственный планировщик BFQ. Однако в связи с недостатками существующейсистемы мониторинга, на основе которой разрабатывался планировщик, тяжело сделать,чтобы каждый диск работал со своим собственным BFQ. Это повлекло за собойнеобходимость некоторой модификации BFQ, в которой для каждого инициатора естьданные, общие для всех дисков, с которыми он работает, и есть данные, уникальные длякаждого диска.
Данные, общие для всех дисков, – это вес процесса и его максимальныйбюджет. Для каждого раздела у инициатора есть своя очередь запросов ввода-вывода,бюджет, start_time и finish_time.8.4. Диск – черный ящикВ оригинальном BFQ функция dispatch() вызывается, когда предыдущий запрос кдиску исполнился и диск запрашивает у планировщика следующий запрос, который нужноисполнить.
Предполагается, что диск в каждый момент времени исполняет только одинзапрос. Когда процесс выбран BFQ как активный, только он исполняет запросы на диске.Однако такой подход не применим к современным HDD, т.к. они имеют собственнуюочередь запросов и собственный планировщик, переупорядочивающий запросы с цельюминимизации перемещения головки диска (технологии NCQ [19] [20] и TCQ [21]). Большенельзя гарантировать, что запрос начнет исполняться сразу же после того, как BFQ послалего вниз, и что в данный конкретный момент исполняются запросы только от одногопроцесса. К тому же, необходимо решить, когда вызывать функцию dispatch().В модификации BFQ для Windows функция BFQProcessQueue (аналог функцииdispatch()), выбирающая следующий активный процесс и посылающая запросы диску,вызывается, когда приходит новый запрос, когда заканчивается какой-либо запрос, либо по26таймеру через промежутки времени Tprocess_queue .
При каждом вызове BFQProcessQueue изочередей вынимается и отправляется диску N запросов. Число N не должно быть равно 1,как в оригинальном BFQ, т.к. это повредит суммарной пропускной способности диска. Nтакже не должно быть слишком большим, т.к. иначе во внутренней очереди диска скопитсямного запросов и внутренний планировщик диска их переупорядочит в соответствии сгеометрией, что отразится на гарантиях честности и времени ответа.8.5. Внутренний планировщик диска.Современные жесткие диски обладают собственными планировщиками запросов(технологии NCQ и TCQ). которые оптимизируют запросы с учетом геометрии диска. Содной стороны они был разработаны с целью улучшить производительность диска идолжны дополнять функциональность планировщика в ОС, т.к тот переупорядочиваетзапросы исходя из соображений честности, а не геометрии.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
