Честное планирование дискового ввода-вывода с учетом разделяемых ресурсов файлового кэша (1187435), страница 5
Текст из файла (страница 5)
Будемсчитать, что в каждый момент времени диск моет обрабатывать более 1 запроса.Исполнение запросов диском описывается функцией) , которую можно(рассматривать как некоторую случайную величину, определяемую параметрами диска иего текущим состоянием, в частности, состоянием дискового кэша.Введем определение битрейта (скорости передачи данных), являющееся одним изцентральных в постановке задачи.
Итак, битрейтом процессабудем называтьследующую величину:( )( ∑ ( )) ⁄{ | ( )20( )[]}(4)Соответствующие функции определяются для битрейта на уровне приложений (надфайловым кэшем) –( ), и на уровне диска –Величина промежутка времени( ).выбирается, исходя из следующих соображений.Она должна быть достаточно большой, чтобы битрейты процессов не были равны 0большую часть времени (при наличии дисковой активности). В то же времябыть достаточно малым, чтобы функциядолжно( ) отражала изменения интенсивностидисковой активности процесса с течением времени.Возможны и другие определения для функции битрейта, в том числе использующиеразличные методы сглаживания, а также учитывающие не только уже исполненныезапросы, но и только отправленные на исполнение, однако в данной работе онирассматриваться не будут.5.1.2. Определения характеристик дискового планировщикаВведем формальное определение понятия честности для планировщика дисковойактивности.
Пустьпромежуток времени [() – величина «сервиса», полученного процессом(за], т.е.)∑ ( ){ | ( )( )[]}(5)Алгоритм планирования будем называть честным, если он обеспечивает выполнениеследующего условия:⇒ | (где {)∑()|{}(6)} – множество процессов, имеющих непустую очередь запросов к диску втечение промежутка времени []. Авторами алгоритма BFQ было показано, что онявляется честным именно в терминах этого определения. Понятие честности вводится длядисковой активности процессов как на уровне диска, так и на уровне приложений (т.е.
надфайловым кэшем).Приведемтакжеальтернативноеопределениепонятиячестности.Внемиспользуется т.н. метрика нечестности распределения битрейтов – величина, равная 0 вслучае идеально честного распределения битрейтов, соответствующего весам процессов,и растущая с увеличением отклонения от этого идеального распределения. Приведемпример такой функции – сумма квадратов относительных отклонений битрейтов отбитрейтов, соответствующих заданным весам:21()√∑ (( )∑∑( )( ))(7)где, как и в предыдущем определении честности, учитываются только процессы,имеющие дисковую активность (т.е.
непустую очередь запросов к диску, ожидающихисполнения) в момент времени .В качестве альтернативного определения, алгоритм планирования будем называтьчестным, если он обеспечивает выполнение следующего условия:⇒( )(8)т.е. в некотором смысле минимизирует величину метрики нечестности в течение всеговремени работы системы.5.1.3. Цель корректировки алгоритма планированияСформулируем в терминах описанной ранее математической модели дисковойподсистемы те свойства дискового планировщика, которых мы хотим добиться путемкорректировки базового алгоритма планирования с учетом использования процессамифайлового кэша.1.
Минимизация нечестности распределения битрейтов процессов над файловымкэшем в терминах 2-го определения честности для случая нечестного распределенияресурса файлового кэша:|()∑()|(9)2. Обеспечение честности доступа к ресурсу дисковой подсистемы на уровнеприложений в рамках 1-го определения честности для случая наличия разделяемыхмежду несколькими процессами данных в файловом кэше:( )√∑ (( )∑∑( )( ))(10)3.
Сохранение суммарной пропускной способности дисковой подсистемы:(∑ ( ) )(∑ ( ) )22(11)5.2. Анализ возможности расположения планировщика надфайловым кэшемПрежде чем приступить к описанию предложенного решения поставленной задачи,проанализируем возможность другого подхода к построению дискового планировщикадля учета наличия файлового кэша, а именно расположения планировщика над файловымкэшем, а не непосредственно на уровне диска.Все известные на данный момент честные алгоритмы планирования доступа к дискуосновываются на очередях запросов. Приходящие от приложений запросы к дискукладутся в соответствующие этим приложениям очереди, и далее в зависимости оталгоритма планирования исполняются в некотором порядке.
Таким образом, началоисполнения для значительной части запросов к диску задерживается на некоторое время.Если расположить планировщик над файловым кэшем, он будет задерживать выполнениезапросов, которые попадают в кэш и могли бы быть исполнены быстро. В результатеможетснизитьсяутилизацияфайловогокэшаиобщаяпроизводительностьдисковой подсистемы.Для обхода этого недостатка расположенный над файловым кэшем планировщикмог бы пропускать без задержки запросы, про которые известно, что они попадут в кэш.Нотогдатакойпланировщикбудетфактическиэквивалентенпланировщику,расположенному на уровне диска.Кроме того, расположенный над файловым кэшем планировщик не учитываетдополнительную дисковую активность, создаваемую файловой системой.
К такойактивности можно отнести, в частности, работу с метаданными файловой системы изапись в ее журнал. Возможен также и обратный эффект – например, при работе ст.н. разреженными (sparse) файлами и сжатыми файлами объем данных, прочитанных илизаписанных на уровне диска, меньше, чем на уровне приложений, работающихс такими файлами.Таким образом, расположение планировщик дисковой активности на уровнефайлового кэша является нецелесообразным. Необходимо создание планировщика,учитывающего запросы ввода-вывода, как на уровне диска, так и на уровнефайлового кэша. В следующих разделах будет описано построение такого планировщикана основе корректировки базового алгоритма планирования на уровне диска с учетоминформации об использовании процессами файлового кэша.235.3.
Динамическая корректировка весов процессов на уровне дискаПерейдем к рассмотрению общего метода корректировки базового алгоритма,учитывающего возможную нечестность распределения ресурсов файлового кэша междупроцессами. Суть его заключается в подстройке весов процессов в планировщике науровне диска с целью уменьшения значения метрики нечестности для распределениябитрейтов на уровне файлового кэша.5.3.1. Описание метода корректировкиВыберем в качестве метрики нечестности распределения пропускной способностинад файловым кэшем функцию, вычисляемую по формуле (7). Будем исходить изпредположения, что битрейты в ней вычисляются на достаточно больших промежуткахвремени, чтобы было выполнено условие:⇒( )( )( )( )( )∑(12)Запишем выражение для метрики нечестности на уровне файлового кэша как функциювесов процессовв базовом планировщике на уровне диска:()Минимизируемданное∑(выражение()(приусловии))равенства(13)суммыэтихвесов единице, предполагая, что суммарная пропускная способность диска( )изменяется с течением времени незначительно:()∑(14)Получаем задачу минимизации квадратичной функции при линейных ограничениях,решаемую аналитически методом множителей Лагранжа.
Решение существует в силувыпуклости рассматриваемой функции и ограничений.Корректировку весов предлагается проводить с некоторым «сглаживанием»:(где коэффициентВ)()(()())(15)выбирается порядка .модифицированномдисковомпланировщикепредполагаетсяпроводитькорректировку весов по формуле (15) через некоторые промежутки времени. Средивозможных вариантов выбора величины этих промежутков можно отметить следующие:24 корректировкавесоввсехпроцессовчерезравныепромежуткивремени(порядка секунды); корректировка веса для отдельно взятого процесса при выборе его в качествеактивного (специфично для алгоритмов наподобие BFQ).5.3.2.
Оценки алгоритмической сложностиАлгоритмическаясложностьописаннойкорректировкивесовпроцессоввпланировщике на уровне диска зависит от того, каким именно образом и в какие моментывремени производить корректировку.Если корректировка происходит для весов всех процессов через некоторыепромежутки времени, то алгоритмическая сложность есть (для каждого из), т.к. при этом требуетсяпроцессов вычислить новое значение веса за время ( ).Если же корректировка происходит для отдельно взятого процесса, например, привыборе его в качестве активного в алгоритме планирования BFQ, то ее алгоритмическаясложность есть ( ), где– число процессов.5.4. Обоснование выбора алгоритма на основе BFQв качестве базовогоПриведем обоснование выбора алгоритма планирования, используемого в качествебазового(науровнедиска)вданнойработе–алгоритманаосновеBFQ(Budget Fair Queueing), реализованного для ОС Linux.В алгоритмах, основанных на выделении процессам бюджетов на выполнениезапросов ввода-вывода, в частности в BFQ, все вычисления происходят в терминахпрочитанных/записанных байт, в отличие от, например, CFQ – основного дисковогопланировщика в ОС Linux, который выделяет процессам некоторые кванты времени наисполнение запросов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
