Разработка честного алгоритма дискового планировщика для OC Windows (1187424), страница 11
Текст из файла (страница 11)
Это связано с тем, что активность процессовпостоянна, и в этом случае и не предполагалось получить большую разницу между BFQ иMBFQ.Средняя задержка исполнения запросамc 50403020BFQ10MBFQ012357911Количество процессовРисунок 1150Максимальная задержка исполнения запросамc 1008060BFQ40MBFQ200123579Количество процессов11Рисунок 122) Время старта программОсновной эксперимент, показывающий преимущества MBFQ – измерение временистарта программ при наличии фоновой дисковой активности (рисунок 13) и без нее(рисунок 14). Измерения проводились для таких распространенных программ как VLC,Adobe Photoshop, Microsoft Word, Visual Studio и VmWare Workstation.
Стоит отметить, чтовремя запуска VLC измерялось при открытии видео-файла размером 4 Гб, а время запускаWord – при открытии файла .doc размером 11 Мб.Из рисунка 14 видно, что при отсутствии активности преимущества почти нет, т.к. всезапросы исполняются сразу. На рисунке 13 же заметно, что при наличии дисковойактивности MBFQ имеет значительное преимущество перед BFQ, давая в случае Photoshopулучшение производительности в 2 раза.Время запуска программ при наличии фоновой активности600NOOPBFQMBFQВремя (в секундах)5004003002001000VLCPhotoshopWordVisual StudioVmWareРисунок 1351Время запуска программ без фоновой активности90BFQMBFQ80Время (в секундах)NOOP706050403020100VLCPhotoshopWordVisual StudioVmWareРисунок 143) Медиа-серверЭтот тест также показывает степень честности распределения ресурсов, однако не всинтетических условиях, как в первом тесте, а в реальных. В данном тесте была сделанаимитациявидео-сервера–намашинебылозапущенонесколькоэкземпляроввидеопроигрывателя VLC, каждый из который проигрывал свой видео-файл.
Измерялоськоличество потерянных кадров в зависимости от количества одновременно проигрываемыхфильмов. Чем честнее распределяется дисковый ресурс, тем более одинаковым являетсяпроцент потерянных кадров для каждого экземпляра VLC и тем меньше средний процентпотерянных кадров.На графике 8 видно, что при отсутствии планировщика процент потерянных кадроврастет гораздо быстрее, чем при использовании MBFQ или BFQ.
На рисунке 16представлены те же графики, что и на рисунке 15, но в другом масштабе. Из них следует,что с MBFQ процент потерянных кадров меньше, чем с BFQ.52Процент потерянных кадровПроцент потерянных кадров40,00%35,00%30,00%25,00%20,00%15,00%10,00%5,00%0,00%-5,00%246BFQ810121012Количество фильмовMBFQNOOPРисунок 15Процент потерянных кадровПроцент потерянных кадров12,00%10,00%8,00%6,00%4,00%2,00%0,00%-2,00%2468Количество фильмовBFQMBFQРисунок 16На рисунках 17 и 18 представлена дисперсия потерянных кадров. При честномраспределении ресурсов график должен быть около нуля. На этих графиках видно, чтоMBFQ дает преимущество в честности по сравнению с BFQ.53Процент дисперсии потерянных кадровДисперсия потерянных кадров12,00%10,00%8,00%6,00%4,00%2,00%0,00%-2,00%246810121012Количество фильмовBFQMBFQNOOPРисунок 17Процент дисперсии потерянныхкадровДисперсия потерянных кадров1,80%1,60%1,40%1,20%1,00%0,80%0,60%0,40%0,20%0,00%2468Количество фильмовBFQMBFQРисунок 1811.
Дальнейшее развитие работыРабота над планировщиком дисковой активности предоставляет большое поле длядальнейших исследований.11.1.Учитываем, что запросы приходят в виде пакетовВ первую очередь хотелось бы учесть в алгоритме планирования интереснуюособенность подсистемы ввода-вывода в Windows – запросы посылаются файловой системе54в вид пакетов, и могут быть разбиты на более мелкие. Можно изучить работоспособность иэффективность следующих соображений: Сейчас при больших запросах (например, 1 Мб и больше) нужно давать процессубюджет, превышающий размер запроса, т.е. минимум 1 Мб. Как уже рассчитывалось выше,при таких бюджетах задержки между приходом запроса и началом его исполнениястановятся слишком большими и неприемлемыми для пользователя.
Если запрос слишкомбольшой, то планировщик может дробить его на более мелкие пакеты. Это позволитсущественно сократить размер бюджета, который необходимо выделять процессу и, какследствие, сократить задержки исполнения. Допустим, синхронный запрос был разбит на более мелкие.
Имеет смысл находить вочереди пакеты, которые относятся к одному и тому же запросу. В частности, если былиисполнены все части запроса, кроме одной (по какой-либо причине – закончился бюджет,либо она отделена в очереди от других частей запроса еще какими-то запросами), то можноувеличить бюджет и выполнить эту оставшуюся часть запроса. Тогда приложение, откоторого пришел этот запрос, продолжит свою деятельность сразу же. В противном случаеему придется ждать следующего периода активности.11.2.Использование бюджета полностьюВыше уже отмечалось, что гарантии соблюдаются лучше, если приложение используетвесь свой бюджет. В связи с этим предлагается улучшить алгоритм планированияследующим образом: Допустим, на следующий запрос в очереди не хватает бюджета, однако еслиувеличить бюджет на маленькую величину, то оставшегося бюджета хватит, чтобывыполнить следующий запрос.
В таком случае следует увеличить бюджет и выполнитьзапрос, на который раньше не хватало бюджета. Если бюджет не израсходован полностью, и в очереди еще остались запросы (т.е.следующий запрос в очереди уже не помещается в бюджет), то можно найти в очередизапрос, подходящий по размеру, чтобы израсходовать оставшуюся часть бюджета. Можно заметить, что многие приложения шлют запросы одинакового размера.Поэтому можно каждому приложению присваивать бюджет кратный стандартному размеруего запросов, чтобы использовать бюджет полностью.11.3.Учитываем внутренний планировщик дискаЕще одним направлением дальнейшей работы является изучение влияния внутреннегопланировщика диска на гарантии честности и время ответа приложения.
Также, возможно,потребуется внести корректировки с MBFQ с учетом того, что на диске имеется еще один55планировщик, чтобы последний по крайней мере не сводил на нет преимущества MBFQ.Например, заставить MBFQ не вынимать из очереди запросов процесса все запросы, дажеесли это позволяет бюджет. Вместо этого можно вынуть ограниченное число запросов,дождаться их выполнения и только потом вынимать оставшиеся. Дело в том, что есливынимать сразу все запросы из очереди, то внутренний планировщик диска может ихсильно переупорядочить, нарушив тем самым гарантии. К примеру, запросы, лежащие вначале очереди, могут быть исполнены в конце очереди.
Более того, если MBFQ послеэтого выбирает следующий активный процесс и посылает его запросы диску, то запросы отпредыдущего активного процесса могут быть выполнены после выполнения запросов оттекущего активного процесса, если так будет выгоднее исходя из расположения запросов надиске. В этом случае гарантии нарушаются еще больше.11.4.Оценка суммарной пропускной способности дискаПри расчетах битрейта и бюджета часто используется понятие суммарной илимаксимальной пропускной способности диска. Однако у каждого диска свое значениепропускной способности.
Отсюда возникает вопрос, как оценить это параметр.В BFQ применяется следующий подход: для каждого активного процесса измеряетсявремя, в течение которого он исполнял свои запросы, и сумма размеров этих запросов. Изэтих параметров и вычисляется битрейт, с которым читал или писал активный процесс.Если битрейт оказался больше, чем имеющееся значение максимального битрейта, томаксимальный битрейт корректируется, причем таким образом, чтобы максимальныйбитрейт изменялся не скачками, а более или менее равномерно.
Учитывается также, чтомаксимальная пропускная способность диска достигается только если в течение долгоговремени исполнять запросы от одного и того же процесса, особенно если процессисполняет последовательные чтение или запись. Поэтому битрейт пересчитывается толькодля приложений, исполнявших запросы больше 20 миллисекунд, т.к. иначе можно получитьнеправдоподобные результаты. Следующий код осуществляет пересчет максимальногобитрейта:if ((Time >= 20 ms) && (bytesProcessed / Time > MaximumBitrate)){MaximumBitrate = (bytesProcessed / difference) * 1/8 + MaximumBitrate * 7/8 ;}Как уже упоминалось, при реализации BFQ и MBFQ в Windows используется другаямодель отправки запросов к диску, чем в BFQ в Linux.
В BFQ в Linux планировщиквыбирает и отправляет на исполнение следующий запрос только когда исполнилсяпредыдущий. В Windows, напротив, к диску отправляется сразу все запросы, которые56бюджет позволяет исполнить, не дожидаясь окончания уже отправленных. По этой причинеоценить, сколько времени активный процесс исполнял свои запросы, сложнее. Необходимобудет отлавливать события окончания исполнения запросов и определять, к какомупроцессу и к какому периоду активности относилось их исполнение.11.5.Исследование зависимости производительности системы отмаксимального бюджетаПроизводительность системы сильно зависит от величины максимального бюджета.Также от максимального бюджета зависят гарантии процесса, как это можно видеть изформул (1) и (2). По этой причине важно исследовать, какой диапазон максимальныхбюджетов больше всего подходит для работы на пользовательской машине и обеспечиваетбыстрый уровень ответа большинства программ.12.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
