Разработка честного алгоритма дискового планировщика для OC Windows (1187424), страница 9
Текст из файла (страница 9)
Берется меткавремени, соответствующая предыдущему изменению бюджета или началу периодаактивности (назовем ее). Продолжительность предыдущего периода активностиопределяется формулойесть разница между текущим моментом времени и окончанием предыдущегопериода активности и определяется следующим выражением:38()(16)Заметим, что при расчете нового бюджета нельзя рассчитать значениебез пересчета в битрейты (например, полагаянапрямую,). При пересчете в битрейтыконтролируется следующие моменты:Процесс не получит слишком большой битрейт, который повлиял бы на дисковуюактивность других процессов.Процесс получает гарантированный битрейт, если это ему нужно.
WF2 Q+контролирует, что процесс в среднем получит гарантированную долю битрейта набольших промежутках времени. MBFQ же контролирует, что процесс получаетгарантированный битрейт в каждый период активности.9.5.4. Основные свойстваРассмотрим некоторые свойства полученного результата.Свойство 1Битрейт процессазависит отследующим образом:Доказательство. В самом деле, это следует из формул (11) и (12).Свойство 2В любой момент времени сумма всех идеальных битрейтов процессов с учетом веса непревышает 1:∑■ Доказательство. Обозначим:∑Также обозначим сумму идеальных бюджетов остальных процессов ∑.В начале работы планировщика битрейты всех процессов полагаются равными весу.∑Далее рассмотрим, момент времени, когда MBFQ пересчитывает бюджет для i-гопроцесса.Из формулы (9) следует, что возможны три варианта:391)2)∑3);∑Итак, либо, либо.Если после изменения идеального битрейта i-го процесса, то в ходе шага 7алгоритма все процессы, битрейт которых превышает вес, получают битрейт, равный весу.Получаем:∑∑■Свойство 3MBFQ обладает свойством честности, гарантирует процессу получение битрейтаидает гарантии на задержки исполнения запроса.■ Доказательство.
Гарантии того, что процесс получит битрейт, следуют извычисления идеального битрейта (формула (9)).MBFQ предоставляет процессам те же гарантии честности и задержки исполнениязапросов, что и BFQ (формулы (1) и (2)). В самом деле, гарантии BFQ следуют из WF2 Q+ изависят только от максимального бюджета, веса процесса и размеров запросов, но не отметода распределения бюджета между процессами. По алгоритму MBFQ бюджет процессовтакже не превышает заданного максимального значения. Поэтому для MBFQ тожесправедливы гарантии, определяемые формулами (1) и (2). ■Свойство 4MBFQ предоставляет как минимум столько бюджета, сколько нужно процессу длятого, чтобы исполнить все свои запросы, пришедшие до или во время периода активности,если это не повлияет на битрейты других процессов и этот бюджет не превышает.■ Доказательство. В самом деле, в пункте 4 алгоритма MBFQ процессу присваиваетсябюджет больше,чем сумма размеров запросов в очереди процесса.
Таким образом, впериод активности процессу разрешается исполнить все запросы из очереди. Алгоритмтакже предоставляет процессу дополнительный бюджет, для того чтобы тот исполнилзапросы, пришедшие во время периода активности. Это достигается следующимиспособами:1) Если запросы синхронные, то планировщик ждет в течение времени, не придетли следующий синхронный запрос. Если запрос приходит, то бюджет процесса40увеличивается на, но не должен превышатьесть размер пришедшего(запроса).2) Если запросы асинхронные, то время их прихода не зависит от того, исполнили сь липредыдущие запросы. Поэтому из предыдущей истории запросов можно рассчитать,сколько примерно запросов придет во время периода активности процесса.
В формуле (7)рассчитывается примерное количество байт, которое необходимо добавить к бюджету,чтобы исполнить эти запросы.Таким образом, MBFQ обеспечивает выполнение всех запросов, пришедших до или вовремя периода активности. Тот факт, что это не повлияет на битрейты других процессов,гарантируется формулой (9). ■Это свойство положительно влияет на суммарную пропускную способность диска, т.к.в течение долгого времени исполняются запросы от одного и того же процесса. Скореевсего, эти запросы расположены на устройстве недалеко друг от друга, и головке дискаперемещается на меньшее расстояние при переходе к исполнению следующего запроса.9.5.5. Теорема о сравнении величин задержек запросовТеорема 1При использовании алгоритма планирования MBFQ в условиях изменения дисковойактивностивеличина задержкизапроса между моментом его приходаи моментомотправки к диску меньше, чем при использовании BFQ.■ Доказательство.
Рассмотрим случаи увеличения и уменьшения дисковой активностипроцесса.1) Увеличение дисковой активности.Обозначим размер j-го запроса в очереди i-го процесса как.Рассмотрим момент начала периода активности процесса. Обозначим период времени,в течение которого запросуже ждет в очереди, как.Подсчитаем величину задержки запроса, внесенную следующим периодом активности,в случае использования BFQ. Обозначим эту величину.Примечание.
В статье [1], где впервые был описан BFQ, утверждается, чтомаксимальная задержка не превышает максимума, определяемого формулой (2):41Однако с учетом того, чтозагруженных систем и порядкапоэтому мы оценимможет принимать значения порядкадля серверов,для не сильноявляется очень грубой оценкой ,более точно в зависимости от положения запроса в очереди.Обозначим величину бюджета, присвоенного процессу после предыдущего периодаактивности, как. Под увеличением дисковой активности понимаем следующее:∑(17)̅̅̅где– размер очереди запросов.Определимследующим образом:∑∑Такое j найдется, т.к. выполнено условие (17).Для тех запросов, которые успеют исполниться за период активности, т.е.
для всехзапросов с индексом, справедливо следующее:(18)Поясним формулу (18). Запросу нужно дождаться, пока исполняться запросы,находящиеся перед ним в очереди, т.е. не более чемне непрерывности вычисления параметра. Слагаемоевозникает из-за.Теперь подсчитаем задержку для тех запросов, которые не успеют исполниться затекущий период активности (т.е. с индексом). Таким запросам нужно будетдождаться следующего периода активности процесса, во время которого они, возможно,будут исполнены. Если они снова не поместятся в бюджет, то невыполненным запросампридется снова ждать следующего периода активности и т.д.
Для запросов, которыеисполнятся за следующий период активности, справедливо:где n – количество процессов, которые будут выбраны активными между периодамиактивностирассматриваемогопроцесса. Т.к. неизвестно, через сколько периодовактивности исполнится конкретный запрос, в общем случае формула для максимальнойзадержки выглядит следующим образом:()42где– количество периодов активности i-го процесса, через которое исполнится j-йзапрос. Отметим, что эта оценка не может превышать оценку, определяемую формулой (2).Оценим m для запроса.
За рассматриваемый период активности не успелиисполниться запросы с индексом j таким, что:∑За каждый последующий период активности бюджет увеличивается на величинуно не превосходит максимальную величину бюджета. Поэтому,есть минимальное целоечисло, для которого выполняется следующее:∑()()()Заметим, что∑()()(∑((∑Итак,()())()))определяется следующим образом:⌈(∑())⌉ (19)Итак, для BFQ задержки запросов можно оценить следующим образом:∑(20)()∑{гдеопределяется формулой (19).Теперь подсчитаем задержки в случае использования MBFQ. По свойству 4 процессполучает столько бюджета, сколько ему нужно для того, чтобы исполнить все своизапросы, пришедшие до или во время периода активности, если это не повлияет набитрейты других процессов и этот бюджет не превышает.43Рассмотрим случай, когда, т.е.
битрейт, который нужно обеспечить∑i-му процессу не помешает другим. Все запросы, для которых∑выполнятся за первый же период активности, т.е. за,. Запросы, непоместившиеся в бюджет, исполнятся в следующий период, если поместятся вКоличество периодов активности, через которое исполнится запрос сопределяется формулой (19) при.∑:∑()(21)Итак, максимальные задержки в случае MBFQ определяются следующим образом:∑(22)()∑{гдеопределяется формулой (21).При сравнении выражений (20) и (22) видно, что задержки при использовании MBFQменьше, чем при использовании BFQ.
Во-первых, запросы с индексом∑исполняются в случае MBFQ в первом же периоде активности, в отличие от BFQ. Длязапросов сколичество∑периодов активности, через которое j-й запросисполнится, меньше в случае MBFQ (формула (21)), чем в случае BFQ (формула (19)).Случай, когда∑, рассматривается аналогично. В этом случае втекущем периоде активности приложение, исходя из формулы (15), получает бюджет.2) Уменьшение дисковой активности.При уменьшении дисковой активности в условиях использования BFQ бюджетпроцесса оказывается больше, чем сумма размеров запросов в очереди, и BFQ исполняет ихвсе за один период активности. В MBFQ процессу присваивается бюджет больший, чемсумма размеров запросов в очереди, поэтому при использовании MBFQ все запросы такжеисполняться за один период активности.
Итак, в случае уменьшения дисковой активности,задержки запросов, вносимые текущим периодом активности, одинаковы. ■Теорема 2При использовании алгоритма планирования MBFQ время реакции на уменьшениедисковой активности меньше, чем при использовании BFQ.44■ Доказательство. Пусть дисковая активность процесса уменьшилась. Запросу нужнокак минимум дождаться следующего периода активности, чтобы эти изменения отразилисьна его бюджете. Обозначим время до следующего периода активности как.В случае MBFQ в начале периода активности бюджет пересчитывается исходя изтекущего уровня дисковой активности, поэтому время реакции на уменьшение дисковойактивности есть.В случае BFQ бюджет будет урезан только по окончании периода активности, т.е.время реакции в случае BFQ составляет, где S – сумма размеров запросов вочереди. Итак, в случае MBFQ время реакции на уменьшение дисковой активности меньше,чем в случае BFQ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
