Разработка честного алгоритма дискового планировщика для OC Windows (1187424), страница 10
Текст из файла (страница 10)
■Отметим, что пока уменьшение дисковой активности еще не отразилось на бюджетепроцесса, WF2 Q+ будет выбирать следующий активный процесс с учетом старого значениябюджета, т.е. может несправедливо выбрать следующий активный процесс. Поэтомуменьшее время реакции на уменьшение дисковой активности способствует болеесправедливому распределению дискового ресурса.9.5.6.
Оценка частоты прихода и среднего размера запросовВ предыдущем пункте для подсчета идеального битрейта использовались понятиясреднего размера запроса и среднего времени между запросами. Для их вычисленияиспользуется история запросов процесса за период T. Подсчитать ̅ не составляет труда –точечная оценка среднего размера запроса считается как среднее арифметическое от всехзапросов, пришедших за последний период T. При подсчете же ̅ возникают некоторыесложности.Если взять в качестве ̅ среднее арифметическое от всех запросов за период T, тооценка получится необъективной. Имеет смысл рассчитывать ̅ на основании типа запроса– синхронный ли он или асинхронный.
Эта информация содержится в структуре IRP, в видекоторой запрос приходит в файловую систему.Рассмотрим пример типичной активности приложения в случае, если оно используетасинхронныеЗачастуюзапросы.отприложенийтакихзапросыприходят пачками, а неравномерно распределеныповременнойоси.45Подсчитав среднее время между запросами, получим среднее время между запросами впачке, однако это не то, чего хотелось бы добиться. Хотелось бы оценить, сколько придетзапросов во время периода активности, учитывая и периоды, когда приложение непосылало запросов. Для этого считаем, что приложение посылает запросы с постояннойинтенсивностью, где– количество запросов, пришедших за последний период T.Тогда ̅ оценим как обратную величину интенсивности:̅̅̅̅̅̅̅̅Теперь рассмотрим случай синхронных запросов. Здесь сложность состоит в том, чтоприложение посылает запрос только после исполнения предыдущего, т.е.
только в периодактивности. Это значит,что история за прошедшийпериодотражатьTнебудетактивностьприложения в следующийпериод активности. Заметим, что в период активности запросы приходят практически сразупосле окончания исполнения предыдущего, т.е. среднее время между запросами можнооценить как среднее время исполнения запроса от этого приложения:̅̅̅̅̅̅̅̅Итак, ̅ рассчитывается по следующей формуле:̅̅{9.5.7. Уменьшение времени ответа приложенияВ данном алгоритме мы стремимся уменьшить время ответа приложения.
Чтобы этогодобиться, недостаточно дать приложению, с которым в данный момент работаетпользователь, больше бюджета. Необходимо также, чтобы это приложение вызывалосьчаще других. Один из способов добиться этого – увеличить его вес. Разумно увеличить весровно насколько, чтобы задержка в исполнении запросов от этого приложения быланезаметна для пользователя, но BFQ выбирал не только данное приложение.Из формулы (2) имеем, что()(23)46– максимальная задержка выполнения запроса. По результатам экспериментовзадержка до 100 мс незаметна для человека. Используя это значение, можно вычислить вес,который нужно присвоить процессу, чтобы оно отвечало с приемлемой скоростью.
ТакойподходприменяетсявMBFQ:приложению,котороеявляетсяинтерактивным,увеличивается вес до величины, рассчитанной выше. Таким образом, гарантируется, чтоинтерактивное приложение будет испытывать задержки не более 100 миллисекунд.Отметим, что если) или((), тоуказанную задержку невозможно обеспечить.
В этом случае следует увеличить веспроцесса до максимально приемлемого (например, до ½ ).9.6.Оценка сложностиПодсчитаем сложность алгоритма MBFQ.Выбор следующего активного приложения осуществляется с помощью WF2 Q+,сложность которого O(log N), где N – количество процессов, имеющих запросы к диску.Первый шаг для расчета бюджета процесса – удаление слишком старых запросов изистории. Обозначим момент времени, позже которого запросы считаются слишкомстарыми, как. Запросы отсортированы по времени прихода. Этот шаг имеет оценкусложности O(1), например, храня запросы в виде хеш-таблицы, где ключ – время приходазапроса. По ключу находим запрос, который пришел в окрестности момента, иотбрасываем часть очереди до этого запроса (т.е. еще более старые запросы.)Далее нужно вычислить ̅ и ̅ из истории запросов.
Этот шаг также можно сделать заO(1), если хранить сумму размеров запросов, сумму интервалов между запросами, а такжеколичество запросов в очереди. Суммы корректируются при приходе нового запроса.Параметры,,вычисляются за О(1).Если сумма битрейтов стала больше 1, то для всех процессов, для которых справедливонужно выполнить.
Это действие нельзя выполнить быстрее, чем O(N).Однако это шаг выполняет только при условии, что сумма битрейтов стала больше 1.Шаги, выполняемые при завершении периода активности, выполняются за O(1).Таким образом, сложность алгоритма MBFQ составляет О(N).9.7. Приемы, заимствованные из BFQ Ожидание следующего синхронного запросаЕсли процесс посылает синхронные запросы, то планировщику не придет новыйзапрос, пока не исполнится предыдущий.
Поэтому когда последний из очереди процессабыл отправлен диску, BFQ ждет в течение, не придет ли планировщику новый запрос47от этого процесса. Это очень эффективный способ увеличить битрейт процесса ссинхронными запросами, несмотря на то, что диск простаивает во время ожиданияИсполняя больше.запросов от одного процесса подряд, мы в большинстве случаевсокращаем расстояние, которое надо преодолеть головке диска.
К тому же процесс неждет, пока его снова выберут активным для исполнения следующего синхронного запроса,т.е повышается время ответа приложения. Правило переноса отметок времени назад.Когда приходит новый запрос, алгоритм присваивает ему метку времени, равнуюмоменту окончания предыдущего запроса. Это помогает в ситуации, когда запрос пришелраньше, чем алгоритм стал обрабатывать событие прихода нового запроса.
Если быалгоритм присваивал запросу текущую метку времени, гарантии задержки могли бынарушаться.В оригинальном BFQ запросы переупорядочиваются в очереди в соответствии салгоритмом C-LOOK, с учетом их расположения на диске. В MBFQ это не используется,т.к. внутренний планировщик диска достаточно хорошо справляется с задачей оптимизациизапросов на с учетом геометрии диска. Переупорядочивать запросы еще и в MBFQ не имеетсмысла, т.к. то может мешать работе внутреннего планировщика,а также требуетдополнительных временных затрат.10. Сравнение модифицированного BFQ и оригинальногоBFQ на I/O тестахДля сравнения BFQ и MBFQ были проведены тесты, подтверждающие выводы,полученные в теории.
Все тесты проводились в виртуальной машине с использованиемфизического жесткого диска.1) Одновременная запись несколькими процессами.В данном тесте мы хотим показаться, что MBFQ сохраняет свойство честности, а такжене страдает потерей суммарной пропускной способности.В ходе этого теста запускались несколько процессов, которые одновременноосуществляли запись на диск, отправляя запросы разных размеров (от 32 Кб до 2 Мб), изамерялась скорость, с которой каждый из них писал на диск. Все процессы имелиодинаковый вес, поэтому их битрейты в соответствии с принципом честности должны бытьодинаковыми. Чтобы измерить, насколько отличались битрейты, вычислялась такаявеличина как среднеквадратичное отклонение битрейта (Рисунок 8). Т.к.
битрейты должныбыть одинаковыми, при честном распределении диска график должен быть как можноближе к нулю. На рисунке 8 видно, при отсутствии планировщика (NOOP), график48находится далеко от нулевой оси, т.е. скорость записи распределяется нечестно в этомслучае. В случае же BFQ и MBFQ график находится около нуля. На рисунке 9 та жевеличина, но в другом масштабе. Из этого графика видно, что MBFQ распределяет ресурсычуть более честно, чем BFQ.Среднеквадратичное отклонение битрейтаМб/c9876BFQ5MBFQ4NOOP32102357911Количество процессовРисунок 8Среднеквадратичное отклонение битрейтаМб/c0,350,30,250,2BFQ0,15MBFQ0,10,0502357911Количество процессовРисунок 9На рисунке 10 представлена суммарная пропускная способность, полученная в данномтесте.
У всех обоих планировщиков, а также в случае отсутствия планировщика (NOOP)они примерно одинакова, что является хорошим результатом, т.к. многие планировщикистрадают потерей суммарной пропускной способности.49Суммарная пропускная способностьМб/c 1008060BFQ40MBFQ20NOOP012357Количество процессов911Рисунок 10Также в этом тесте была измерена максимальная и средняя задержки между приходомзапроса и его отправкой к диску (рисунки 11 и 12). На этих графиках видно, то задержка вслучае MBFQ меньше, но не намного.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
