Разработка честного алгоритма дискового планировщика для OC Windows (1187424), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

в наборе один запрос), то обслужим его. Иначе пустьбудет первымзапросом в направлении сканирования. Обслужим3) Переходим на шаг 1.Направление сканирования выбирается в соответствии с CSCAN, т.е. выбирается тотзапрос, который ближе расположен на диске.Deadline модифицируются следующим образом:Пусть-- deadline запросов, а– номер запроса в порядке его местонахождения надиске относительно текущего запроса.

Тогда(задает время, прибавляемое к deadline, исходя из номерадостаточно малы, чтобы выполнялось()), где f – функция, которая. Эти прибавки должны быть(), еслии j должны быть обслужены в порядке их положения на диске, если()или (), и запросы i. Можно взять.Как правило, периодические запросы нуждаются в ответе со стороны системы. Дляэтого система ввода-вывода создает буфер, в который кладет ответ для текущего запроса.Распределение места в буфере для каждого из процессов – также отдельная задача.

Такжеимеет значение размер буфера. Если размер маленький, то каждый процесс можетиспользовать маленькую часть буфера короткие промежутки времени. Если же буфер9большой, каждый процесс может использовать более значительную часть буфера на болеедолгие промежутки времени. К тому же большой буфер позволяет обслуживать большееколичество процессов.Управление критическими временами также может положительно сказаться напроизводительности системы. К примеру, можно поставить крайний срок исполнения,являющийся суммой времени прихода запроса L и времени его обработки p.

Однако еслипоставить крайний срок исполнения, например, для двух запросов, то планировщиксможет успеть переупорядочить эти два запроса оптимальным образом. Таким образом,крайний срок исполнения лучше присваивать значение, где m – некоторое число.Стоит отметить, что для m запросов, ожидающих своей очереди, требуется место вбуфере для хранения данных этих запросов, т.е. нужно как минимумсвободногоместа в буфере. S – размер данных, хранимых одним запросом.4.3.2. Deadline-Modification-Scan SchemeНиже приведен алгоритм, модифицирующий крайние сроки исполнения, чтобы найтиоптимальный порядок исполнения запросов.Пусть есть набор запросовзапросов{( )}. Планировщик Z порождает очередность{( ) }.( )Будем называть Real-Time Disk scheduling (RTDS) планировщик Z, который набор} преобразовывает{притом, что( )( )и( ){( )для( )( ) },( )где( )минимально,.Определим Максимальную сканируемую группу (MSG) следующим образом:Пусть дан набор запросов, обработанный планировщикомМаксимальная сканируемая группа, начинающаяся с запросагруппаудовлетворяющая{( )()() },( ){( )( ) }.( ), есть максимальная( )и( )( )для.Алгоритм поиска MSG:101) Дан набор {}.2)3)(()()()):=i;Поиск MU_MSG (mutually exclusive and un-scanned MSG groups)1)есть направление сканирования//2)()/* MSG просканирована тогда и только тогда, когда scan_direction есть +1, … -1или -1, … -1 */;3)(4))(()если)оптимизирована по поисследследар ппаар ппаEndDeadline-Modification-Scan алгоритм для MSGВ этом алгоритме для каждой пары запросов{модифицируются deadline}, чтобы удовлетворить требованиям EDF планировщика.

Это и естьdeadline modification.для каждого1) Store2)()айти всер пп дл в оде о на ора запросов11Найти все MU_MSG группы из MSG групп.()(3) Recover)дл все// восстанавливаем начальные deadline.4.4. Честный алгоритм: Deficit Round-RobinПри подготовке пункта 4.4 использовался материал [14]Примером честного алгоритма может служить Deficit Round-Robin. Он схож с RoundRobin, но в то же время ограничивает объем исполняемых запросов для каждого процесса.Пусть fi -- квота, данная процессу с номером i. Qi – некоторая константа (квант). Пусть( ) Определим fi как. Введем также переменную DCi .

Путьвначале DCi равно Qi для всех процессов. Алгоритм обходит все процессы по кругу. Если вРисунок 1очереди процесса есть пакет, размер которого меньше DCi , то этот пакет убираем изочереди, отправляем на обработку, а значение DCi уменьшаем на величину размера пакета.Если размер пакета больше DCi , пропускаем этот процес и прибавляем к DCi значение Q i.Deficit round-robin – честный алгоритм, у которого выбор следующего процесса иследующего исполняемого запроса осуществляется за ( ).4.5.Планировщики в системе LinuxПри подготовке пункта 4.5 были использованы источники [6] и [15].Рассмотрим, какие планировщики имеются в ОС Linux.В Linux используется 4 планировщика:NOOPDealine.Anticipatory.12Сompletely Fair Queeing (CFQ) – планировщик по умолчанию.Рассмотрим их подробнее:4.5.1. Noop (no operation – с отсутствием операций)Наиболее простой из перечисленных.Данный планировщик в соответствии с названием практически ничего не делает.

Онобрабатывает поступающие запросы по принципу FIFO. Noop выполняет толькообъединение приходящих запросов со смежными.Предназначен для работы с ОЗУ, флэш-носителями или устройствами, уже имеющимисвой планировщик. К примеру, у плат флеш-памяти нет особых затрат на поиск, поэтомунет необходимости применять специальные алгоритмы вставки или объединения.4.5.2. Лифтовый алгоритм Линуса (Linus elevator)Этоосновнойпланировщик вверсии2.4.Предназначендля того,чтобыминимизировать поиск по диску в запросах очереди в целом, чтобы в конечном итогеголовка диска проходила по диску практически по прямой.Метод заключается в следующем: когда запрос добавляется в очередь, он сравниваетсясо всеми ожидающими запросами, чтобы найти подходящую пару для объединения.

Затемопределяется тип объединения: если найденный запрос предшествует только чтопришедшему, что происходит добавление в конец запроса (back merging), а если следует заним, то добавление в начало запроса (front merging). Если подходящей пары не найдено,планировщик вставляет новый запрос в очередь в позицию, которая наилучшим образомсоответствует ему по номер сектора. Если и такой позиции не найдено, запрос помещаетсяв конец очереди. Чтобы избежать ситуации, когда вновь прибывшие запросы не даютвыполняться более старым из-за того, что больше подходят по номеру сектора и становятсяв очередь раньше, было введено еще одно условие: если в очереди есть достаточно старыйзапрос, то вновь пришедшие запросы добавляются в конец очереди.Однако и такой метод не позволяет полностью избежать задержек: может возникнутьситуация, когда поступает много запросов к одному и тому же участку диска, при этомзапросы к другим участкам практически не обрабатываются. Такой алгоритм не можетобеспечить общедоступность и честность распределения ресурсов.Более того, возникает проблема задержки обслуживания чтения при обслуживаниизаписи.

Когда ядру приходит запрос на запись, эта операция может начать выполняться несразу, а тогда, когда это удобно ядру. Это связано с тем, что операция записи выполняетсяасинхронно по отношению к приложению, т.е. оно не ждет окончания процесса записи.Однако при операции чтения приложения имеют обыкновение зависать до окончания13последней, что существенно сказывается на производительности системы. По этой причиневремя задержки исполнения операции чтения важно минимизировать, в то время как времязадержки операции записи не столь важно.Положение усугубляет и тот факт, что часто приложение выполняет несколькопоследовательных операций чтения размером с буфер.

При этом приложение ждетвыполнение каждой из операций чтения. Это приводит к сложению задержек чтения ивлечет за собой недопустимо большое время ожидания в целом.4.5.3. Dealine – планировщик ввода-вывода с лимитом времениВ основном данный планировщик работает так же, как алгоритм Линуса (он тожеподдерживает очередь запросов в отсортированном по номерам секторов состоянии).

Припоступлении нового запроса Deadline аналогично Linus elevator осуществляет объединениеи вставку запросов в очередь.Однако цель этого планировщика – минимизировать задержки I/O операций. Для этоговводится еще две очереди запросов --FIFO очередь запросов чтения и FIFO очередьзапросов записи. Когда приходит новый запрос, он помещается в одну из двух очередей взависимости от его типа.

В отличие от основной очереди, очереди чтения и записиотсортированы по времени поступления запроса, а не по секторам диска. В них введенопонятие времени ожидания (expiration time). По умолчанию это 500 миллисекунд дляопераций чтения и 5 секунд для операций записи.Алгоритм Deadline планировщика заключается в следующем: запросы берутся изосновной очереди и помещаются в очередь диспетчеризации, из которой они отправляютсянепосредственно к диску. Если для запроса чтения или записи в FIFO очередях истекаетвремя ожидания, то начинают выполняться запросы из соответствующей очереди.Таким образом, Deadline дает большее предпочтение операциям чтения, чем операциямзаписи, причем мы можем гарантировать, что через фиксированное время операция будетотправлена на обработку.

Характеристики

Список файлов ВКР