Разработка честного алгоритма дискового планировщика для OC Windows (1187424), страница 8
Текст из файла (страница 8)
удаляются запросы, для которых выполнено2) По запросам, хранящимся в истории запросов, вычисляется средний размер запросов̅ и средний интервал между запросами ̅ , как описано в пункте 9.5.6.3) Из истории изменения бюджетов вычисляетсяпо формуле (16).4) Из размеров запросов в очереди процесса, а также ̅ и ̅ вычисляется суммаразмеров запросов, которые надо исполнить.5) Извычисляется по формулам (7) и (8).вычисляется предварительное значение идеального битрейта6) Вычисляем идеальный битрейт с учетом весапо формуле (4)по формуле (9).7) Корректируем сумму идеальных битрейтов по всем приложениям (формула (10)).Если сумма битрейтов стала больше 1, то для всех процессов, для которых справедливовыполняем.328) По формуле (15) получаем значение нового бюджета, тодля i-го процесса.
Если.После окончания периода активности:1) Еслиприложениеиспользовалоневесьсвойбюджет,тонеобходимоскорректировать идеальный битрейт следующим образом:(где)– оставшийся бюджет.2) Если запрос синхронный, то планировщик ждет в течение времени, не придетли следующий синхронный запрос. Если запрос приходит, то бюджет процессаувеличивается на, но не должен превышать(– размер пришедшегозапроса).9.5. Математическое обоснованиеПокажем, почему данный алгоритм позволяет добиться поставленных в пункте 9.1целей.9.5.1.
Основные понятия и обозначенияВведем следующие обозначения:– вес i-го приложения,— битрейт i-го приложения— битрейт i-го приложения после корректировки— идеальный битрейт— идеальный битрейт c учетом веса— максимальная пропускная способность дискаT — интервал времени, в течение которого собирается история запросов– бюджет i-го процессаПоясним, что есть интервал времени T. Это интервал времени, в течение которогособирается история запросов процессов.
На основе истории впоследствии предсказываетсяактивность процесса в будущем, поэтому период T должен быть достаточно большим,чтобы история запросов за этот период была репрезентативной. В данной работе за Tпринимаетсязначение,гдеN–среднеечислопроцессоввсистеме,предпринимающих дисковую активность, т.е. время, за которое N процессов израсходуютсвои бюджеты.33Пересчет битрейта и бюджета происходит перед началом следующего периодаактивности.
Битрейт считается за период активности, а также за предыдущее время«простоя»приложения(т.е. пока оно былонеактивным).Наследующийпериодактивности нужно выбратьтакойбюджет,чтобысредний битрейт засоответствовалРисунок 7идеальному.активности будет прочитано или записаноЗапериодбайт (т.е. количество, равное бюджету),поэтому битрейт определяется следующим выражением:((3))Отметим, что под битрейтом будем понимать всегда нормализованный битрейт, т.е.разделенный на максимальную пропускную способность:9.5.2.
Оценка идеального битрейтаОдна из целей планировщика – скорректировать битрейт так, чтобы он совпадал сидеальным битрейтом. Под идеальным битрейтом в момент временибудем пониматьбитрейт, который нужен процессу, чтобы исполнить все запросы из очереди, а также всезапросы, которые придут во время периода активности (сумму размеров таких запросовобозначим).Итак, формула для идеального битрейта имеет следующий вид:(4)Однако если какие-то из этих запросов будут исполняться долго (дольше, чем периодактивности), то их исполнение имеет смысл отложить до следующего периода активности.Поэтому будем считать суммутолько по тем запросам, у которых время завершения непозже времени окончания периода активности:(5)Здесь использованы следующие обозначения:– размер j-го запроса34– время прихода j-го запроса– приблизительное время завершения j-го запроса– текущий момент времени.Поясним левую часть формулы:(6)Во время периода активности i-го процесса исполняется запросы только этогопроцесса.
Поэтому битрейт, с которым исполняются эти запросы, равен максимальномубитрейту. Тогдаобразом,есть время исполнения j-го запроса в период активности. Такимравно приблизительному времени завершения j-го запроса.Аналогично,– время исполнениябайт, т.е.
длительность периода активности.Отметим, что битрейты пересчитываются непосредственно перед тем, как процесс станетактивным, и подподразумевается именно начало периода активности.Итак, идеальным битрейтом считаем тот, который позволяет выполнить за следующийпериод активности все запросы, находящиеся в очереди, для которых справедливо, а также запросы, которые придут во время следующего периода активности, длякоторых также справедливо, где– текущий момент времени,— времязавершения -го запроса i-го процесса.Подсчитаем количество запросов, которые придут в течение промежутка времени.Для них справедливо:гдеи— время прихода и размер k-го запроса соответственно.Пусть запросы во время периода активности приходят через промежутки времени ̅ .Обозначим средний размер запроса ̅ .
Обозначимпридут за– количество запросов, которые. Учитывая, что в период активности момент прихода запроса и моментначала его исполнения практически не отличаются, справедливо следующее:̅̅̅̅35̅(Обозначим сумму размеровсправедливо)запросов,, через ∑̅̅̅находящихся вочереди,для которых. Итак, подсчитаем, сколько байт надо будетпрочитать или записать в следующем периоде активности (обозначим эту величину∑Заметим, что в случае̅∑̅̅̅).(7)̅ новые запросы не успеют прийти во время периодаактивности. В этом случаесчитаем без последнего слагаемого:∑(8)При идеальном битрейте в период активности процесс должен успеть исполнитьзапросы из очереди и запросы, которые придут за период активности.
Идеальный битрейт,напомним, считается за период активности и предыдущий период неактивностиприложения. Тогда идеальный битрейт имеет следующий вид:()()(∑̅̅̅)Однако идеальный битрейт может оказаться чересчур большим. Если дать такойбитрейт процессу, это может существенно помешать дисковой активности другихпроцессов и нарушить их гарантии. Поэтому необходимо скорректировать идеальныйбитрейт с учетом веса процесса.Идеальный битрейт с учетом весарассчитывается следующим образом:∑(9)∑{Поясним данную формулу. Если процесс хочет иметь битрейт меньше, чем вес, топланировщикобязандатьемутакойбитрейт,т.к.планировщиком.
Если процесс хочет получить больше, чембитрейтгарантируется, то нужно учесть, позволяютли битрейты других процессов дать такой битрейт. Для этого смотрим сумму идеальныхбитрейтов всех остальных процессов. Если ее отличие от единицы (т.е. от максимума)больше, чем i-й процесс желает получить, то такой битрейт можно предоставить процессу.36Если же сумма битрейтов остальных процессов не позволяет дать i-му процессу такойбитрейт, то планировщик дает ему гарантированный битрейтДалее корректируем сумму ∑.с учетом нового идеального битрейта:∑(10)Отметим, что сумма битрейтов ∑может превышать единицу.
Это происходит приследующем сценарии: одному из процессов понадобился большой битрейт, превышающийего вес. Сумма битрейтов других процессов позволяла дать этому процессу такой битрейт,т.е. сумма битрейтов не превысит единицу. Однако следующему активному процесс такжепонадобилось увеличить битрейт до величины, не превышающей его вес. В соответствии сгарантиями алгоритм не может не дать ему такой битрейт. Однако теперь сумма битрейтовпревышает единицу. Для того, чтобы сделать битрейт равным 1, урежем битрейты темпроцессам, у которых битрейт превышает вес:По свойству 2 сумма битрейтов станет равна единице.9.5.3. Расчет нового бюджетаТеперь вычислим, какой бюджет нужно дать процессу, чтобы его битрейт изменился нанужную величину. Мы хотим добиться, чтобы новый битрейт совпадал с идеальным:.
Для этого новый бюджет должен удовлетворять следующему условию:(Отметим, чтои(11))также зависят от:(12)()(Из формулы (9) следует, что)может принимать два значения:и. Рассмотримоба случая.Случай 1()37()(13)Случай 2(()̅(∑)̅̅∑̅̅̅(∑̅̅)∑(̅)̅̅̅̅∑̅̅̅∑̅̅̅̅∑̅∑̅(14)̅Итак, из (9), (13) и (14) получаем окончательную формулу для̅̅):̅̅̅̅∑(15)∑{Отметим, что если величинаменьше, чем размер следующего запроса в очереди,то имеет смысл увеличить бюджет хотя бы до размера следующего запроса. Такжеотметим, что если вычисленный из идеального битрейта бюджет превышает максимум, топроцессу присваивается максимальный бюджет.вычисляется следующим образом: в истории изменения бюджетов хранятсяметки времени, соответствующие моментам изменения бюджетов процесса.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
