Разработка честного алгоритма дискового планировщика для OC Windows (1187424), страница 7
Текст из файла (страница 7)
Однако иногда внутреннийпланировщик мешает работе планировщика в ОС. Рассмотрим, каких случаях это можетпроисходить. BFQ посылает запросы на исполнение исходя из их размера и приоритета. NCQ жеможет отложить исполнения высокоприоритетного запроса и выполнять те, которые болееудобно выполнить исходя из их местоположения на диске, тем самым нарушая гарантиизадержки. После исполнения синхронного запроса BFQ ждет некоторое время, не придет лиследующий синхронный запрос, заставляя диск простаивать. В это время NCQ можетначать исполнять другие запросы, чтобы избежать простоя диска. Это сводит на нетпреимущества этого приема BFQ, так как во время ожидания следующего синхронногозапроса головка диска уже могла переместиться в другое место на диске.Влияние внутреннего планировщика на работу планировщика в ОС в данной работе неисследуется.8.6. Некоторые запросы системы нельзя задерживатьДалее рассмотрим особенности, связанные с устройством подсистемы ввода-вывода вWindows.В ОС Windows есть запросы, которые нельзя задерживать, иначе система выдаст синийэкран.
К таким относятся, например, обработка ядерного page fault, записи в журнал NTFSи сброс оперативной памяти на диск в условиях нехватки памяти (своп). Данные типызапросов в модификации BFQ для Windows идут в обход BFQ, попадая в очередь к дискунапрямую.
Если таких запросов слишком много, их исполнение может отразиться нагарантиях честности. Но, как правило, подобная системная активность (кроме сбросаоперативной памяти) имеет маленькие размеры и не влияет на дисковую активность других27процессов. В случае же сброса оперативной памяти в условиях нехватки памяти ни очестности, ни о заботе о времени ответа приложения, речи уже не идет.8.7.Запросы могут быть большимиВ Linux по умолчанию максимальный размер запроса ограничен 512 Кб. В Windows нетмаксимума на размер запроса.
При проведении тестов были зафиксированы запросыразмером 4 Мб. В BFQ максимальная задержка для запроса зависит от максимальногоразмера запроса (формула (1)), и есть в Windows размер запроса настолько большой, тогарантируемая максимальная задержка в BFQ оказывается слишком большой и неотвечающей требованиям на время ответа приложения.Более того, от максимального размера запроса неявно зависитзапроса окажется больше. Если размер, то он никогда не исполнится, а следовательно, и всеостальные запросы от этого процесса, т.к. у процесса всегда будет не хватать бюджета дляего исполнения.
С другой стороны, можно сделатьдостаточно большим, чтобыразмеры запросов были всегда меньше этой величины. Тогда каждый процесс сможет заодну итерацию писать или читатьбайт, а другие процессы будут в это время ждать.Подсчитаем, какими будут гарантии BFQ в условиях большихпроведенных на ОС Windows,может достигать 4 Мб.
Возьмеми=. Из тестов,и. BFQ утверждает, что разница между количеством байт, прочитанных илизаписанных на диск i-м процессом в идеальной машине, и аналогичной величиной нареальной машине определяется следующим выражением:()()В этом контексте 6 Мб – очень большое число, и данное свойство теряет свой смысл.Рассмотрим теперь выражение для максимальной задержки между приходом запроса иначалом его исполнения.
Возьмем в качестве максимальной пропускной способности40 Мб/c.Если вес процессабольшой (например, 1/2), то задержка имеет весьма приемлемоезначение. Однако если брать более реалистичный вес процесса (1/10 или 1/100 для большихсистем), то задержкааждо о запроса будет составлять от 1.5 секунд до несколькихсекунд, что недопустимо для пользователя.288.8. Запросы могут разбиваться на более мелкиеЕще одна особенность связана с тем, что файловая система может разбивать запросы наболее мелкие и планировщика они доходят уже в раздробленном виде.
В еслиреализовывать оригинальный BFQ в ОС Windows, то могут возникать ситуации, когданесколько частей синхронного запроса отправлены планировщиком на исполнение, аоставшимся BFQ не дал исполниться за текущую итерацию, потому что у процессакончился бюджет. Следовательно, следующий синхронный запрос от этого процессапланировщик получит только после того, как этот процесс будет выбран снова, оставшиесячасти синхронного запроса будут обработаны, и процесс обработает событие, что егодисковый запрос исполнен.
Такой сценарий также снижает суммарную пропускнуюспособность диска.9. Модифицированный BFQ (MBFQ)Приреализациипланировщика BFQ в ОСWindows было выявлено несколько существенныхнедостатков,мешающихработепользователя.Поэтому в рамках данной работы была создана новаямодель распределения бюджетов между процессами,учитывающая недостатки оригинального BFQ.Рисунок 4Модифицированный BFQ или MBFQ – планировщик, также использующий понятиебюджета ля управления дисковым ресурсом. Как и BFQ, данная модель использует WF2 Q+для соблюдения гарантий честности.
Однако здесь предложена совершенно иная модельраспределения бюджетов между процессами,позволяющаяулучшитьвремяответаприложения и сделать планировщик болееподходящим для использования на машинахпростых пользователей. МодифицированныйBFQ предугадывает дальнейшее поведениепроцесса исходя из его истории запросов.Благодаря этому удается предсказать, сколькобюджета понадобится процессу в следующийпериод активности, чтобы дать процессуименностолькобюджета,сколькоРисунок 5емупонадобится.
В то же время MBFQ контролирует, чтобы бюджет процесса не был слишкомбольшим, и процесс не задерживал исполнение запросов других процессов. Гарантии,29предоставляемые оригинальным BFQ, не зависят от значения бюджета процесса, только отего максимального значения, поэтому для MBFQ справедливы те же гарантии честности,что и для BFQ.Сохраняя все преимущества BFQ, MBFQ исправляет самый заметный и раздражающийнедостаток оригинального планировщика – медленную реакцию на изменение активностиприложения.9.1.Цели создания MBFQСформулируем цели, которых хотелось бы добиться в алгоритме MBFQ.1) Сохранение свойства честности. К счастью, свойство честности обеспечиваетсяалгоритмом выбора активного процесса WF2 Q+, на котором базируется MBFQ, поэтому вMBFQ не нужно заботиться об этом.2) Гарантированный битрейт, равный весу.
Если процессу нужен битрейт, меньшийлибо равный его весу, планировщик обязан представить его вне зависимости от активностидругих процессов.3) Битрейт процесса должен быть равен идеальному. Определим ошибкубитрейтадля i-го процесса следующим образом:,где— битрейт i-го приложения,— идеальный битрейт i-го приложения cучетом веса. Задача MBFQ – минимизировать данную ошибку.4) Улучшение времени ответа приложения: алгоритм должен давать процессу столькобюджета, сколько тот может израсходовать. Оценка нужного процессу бюджета – важнаясоставляющая MBFQ.
Размер бюджета сильно влияет на время ответа приложения. Еслибюджет слишком мал, то активные процессы меняются чаще, и головке диска нужно чащеперемещаться, чтобы считать данные для другого процесса. Также если запрос большой, онможет просто не поместиться в бюджет. Если же бюджет большой, то существенноувеличивается интервал времени между приходом запроса и фактическим началом егоисполнения, т.к.
приложению нужно дождаться, пока текущий активный процесс закончитсвою деятельность.5) Быстрая реакция на изменение активности приложения. Как указано в пункте 7.4 и7.5, BFQ очень медленно реагирует на изменение активности, а именно на ее увеличение,что сказывается на времени ответа приложения. В MBFQ необходимо обеспечить быструюреакцию на увеличение количества запросов от приложения. Это свойство пересекаетсяпредыдущим: алгоритм даст процессу больше бюджета, если тот начал присылать большезапросов.306) Суммарная пропускная способность диска должна быть как можно ближе кмаксимальной.
Отметим, что максимальная пропускная способность диска достигаетсятолько если в течение долгого времени исполнять запросы от одного и того же процесса,особенно если процесс исполняет последовательные чтение или запись. Если же процессисполняет случайные чтение или запись, то никакой планировщик не поможет достичьмаксимальной пропускной способности.9.2.ПредположенияВ предложенном нами алгоритме используются следующие предположения:1) Активность процесса в текущем периоде будет происходить так же, как и в прошлом(в плане времени прихода и размеров запросов)2) За прошлый период T планировщик выбирал данный процесс примерно столько жераз, сколько в прошлом периоде.
Данное предположение следует из предположения 1), т.к.в соответствии с WF2 Q+ планировщик выбирает приложение, основываясь на времениприхода и размере его запросов.9.3.Схема работы планировщикаПоясним общую схему работы планировщика. Один цикл его работы включается в себяследующие этапы:I)Стадия выбора активного процесса1) С помощью WF2 Q+ выбираетсяследующий активный процесс2) В числ етсновоезначениеджетаII) Период активности процессаПланировщик отправляет к дискувсе запросы, пока их сумма непревышает бюджет.III) Завершение периода активности1) Корректируются метки времениРисунок 6в WF2 Q+2) Корре тир етс значение идеально о итрейтаЭтапы, выделенные курсивом, определяются алгоритмом BFQ или MBFQ, и именно этачасть планировщика была изменена в рамках MBFQ.319.4.АлгоритмАлгоритм MBFQ вычисляет количество бюджета, который нужно дать процессу.Пояснения всех формул, используемых в алгоритме, могут быть найдены в пункте 9.5.Для алгоритма необходимо хранить следующие структуры:1)История запросов {} – размер запроса, его время прихода и расчетное времяокончания исполнения Хранится для всех запросов, пришедших в течение прошлогопериода T.2)История бюджетов {} – бюджет, а также время, когда бюджет был изменен (т.е.когда процесс был выбран алгоритмом).Начальные данные алгоритма:Веса процессовпо умолчанию равны , где– количество процессов.
Веса такжеможно задавать вручную каждому процессу.Идеальные битрейтыБюджетыравны весу.равныПоследнее требование не принципиально, т.к. для всех периодов активности, кромепервого, бюджет пересчитывается заново. Начальное значение бюджета используетсятолько в первом периоде активности, т.к. этот момент у процесса может не бытьрепрезентативной истории запросов.Шаги алгоритма для расчета бюджета i-го процесса:1)Из истории запросов удаляются запросы, которые пришли раньше, чем, где— текущий момент времени. Т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
