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

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

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

Такойпланировщик предотвращает ситуации, когда низкоприоритетные запросы занимаютбольшую часть дискового ресурса, не давая исполняться запросам с большим приоритетом.Однаковвиду того,что большинство процессов имеет нормальный приоритет,значительная часть запросов никак не переупорядочивается, и качество обслуживания неповышается при использовании такого планировщика.Теперь рассмотрим, каким образом отсутствие планировщика, обеспечивающегокачество обслуживания, отражается на пользователях. Например, при одновременнойработе программ, пишущих или читающих с диска, некоторые из них работаютзначительно медленнее, чем другие. Особенно заметно, если программа пользователя«тормозит» из-за того, что на фоне запустилось антивирусное ПО, проверяющее файлы.Другой пример: при запуске одновременно нескольких копирований файлов можнонаблюдать, что хотя бы одно из них практически останавливается до тех пор, пока незакончатся другие.

Также проигрывание видео- и аудио-файлов перестает быть плавным ,если с диском параллельно работают еще несколько программ.4При использовании Windows на серверных системах и в контейнерной виртуализацииотсутствие планировщика заметно еще сильнее. Если дисковый ресурс распределяетсянечестно между процессами, обслуживающими клиентов, или контейнерами, то некоторымклиентам придется ждать ответа от сервера гораздо дольше, чем другим клиентам. Этокритично в случае видео-серверов и контейнеров, где информацию от сервера требуетсяполучать с минимальными задержками.

Осложняет ситуацию и то, что клиенты платят заиспользование контейнеров и могут быть недовольны тем, что с контейнер медленноработает, потому что ему не досталось пропускной способности диска.Итак, на данный момент в ОС Windows отсутствует дисковый планировщик, которыйбы помог решить описанные выше проблемы. Также отсутствуют какие-либо разработки поэтой теме ввиду сложного устройства дисковой подсистемы ОС Windows и закрытости еекода.Задача данной работы – разработать и реализовать планировщик дисковой активности,который бы решал задачу обеспечения качества обслуживания приложений.4. Существующие решения для планирования I/OСуществует множество решений для планирования ввода-вывода в разных областях. Вданном разделе будут рассмотрены как самые простые решения, так и сложные,осуществляющие практически честное распределение ресурсов между пользователями,процессами или запросами.4.1.Алгоритмы, учитывающие движение головки жесткого дискаПри подготовке пункта 4.1 использовался материал [8] и [9].SCANСамый простой алгоритм.

Его суть состоит в следующем: планировщик выстраиваетзапросы в очереди так, чтобы головка жесткого диска при их исполнении шла только водном направлении. Другими словами, запросы переупорядочиваются в соответствии с ихпорядком на диске. При этом минимизируются передвижения головки, однако времяотклика для конкретного запроса может быть очень большим, если все время будутприходить новые запросы с более «удобным» расположением на диске.Shortest Seek Time First (SSTF)Напоминает предыдущий алгоритм. Здесь после выполнения каждого запросапланировщик выбирает новый запрос, который лежит на диске ближе всех к текущему.Shortest Access Time First (SATF)Планировщик выбирает запрос с минимальной задержкой на поворот диска.5SATF и SSTF страдают от проблемы под названием «голодание» (starvation), то естьнекоторые запросы могут очень долго ждать в очереди на обслуживание.

Эту проблемурешает SATFUF.Shortest Access Time First With Urgent Forcing (SATFUF)Является модификацией SATF, но добавляется условие: если со времени приходазапроса прошел определенный промежуток времени, то запрос надо немедленно исполнить.При этом запросы, находящиеся на диске до него, можно переупорядочивать, если это небудет задерживать исполнения «старого» запроса.SATFUF обладает рядом недостатков: во-первых, когда планировщик собирается найтии выполнить устаревший запрос, по пути удается переупорядочить и обработать малозапросов; во-вторых если один раз была запущена процедура исполнения устаревшегозапроса, то издержки на это будут чаще всего очень большими, что при водит кпревращению алгоритма в FCFS, т.к.

тогда все запросы будут постепенно устаревать иобслуживаться вне очереди.Shortest Access Time First with Urgent Forcing (N)Выбираются N старых запросов и переупорядочиваются (Здесь N – константа). Такжеможно переупорядочить и выполнить запросы, встречающиеся по пути, если это незадержит исполнение устаревших запросов.Weighted Shortest Time FirstВ этом алгоритме предполагаемое время, которое будет затрачено на операцию ввода,умножается на величину веса W. Вес вычисляется из того, сколько времени остается доdeadline данного запроса. Время поиска с учетом веса определяется по формуле, где-- время с учетом веса,– предполагаемой время обслуживания IOзапроса ( запросы переупорядочиваются в порядке увеличения времени), M – deadlineзапроса, E – время, прошедшее с момента прихода запроса в очередь.Данный алгоритм дает среднее время обслуживания запроса, приблизительно равноеаналогичному значению для SSTF, но максимальное время обслуживания в WSTFзначительно меньше.Aged Shortest Access Time First (ASATF)Также решает проблему starvation.

В нем запросы обслуживаются в соответствии свеличиной, где w – константа, обозначающая вес (в секторах в секунду),– время, которое запрос провел в очереди,-- время доступа к блоку на диске дляэтого запроса.6Этот алгоритм дает гарантии на то, что запрос будет обслужен, то при этом вновьпришедшие процессы могут ждать в очереди момента, пока их обслужат, довольно долгоевремя. LOOKАлгоритм LOOK похож на алгоритм SCAN. В этом алгоритме запросы такжепереупорядочиваются в соответствии с расположением на диске, чтобы головка диска шлатолько в одном направлении. Но, в отличие от SCAN, этот алгоритм также отслеживает,есть ли еще запросы по направлению движения головки диска. Если запросов нет, тоголовка начинает движение в обратном направлении, обслуживая запросы, находящиеся вэтом направлении.

Таким образом, головка не доходит до конца диска, если там ненаходятся никакие запросы.C-LOOKОдним из вариантов LOOK является С-LOOK. В алгоритме C-LOOK головка движетсятолько в одном направлении. Когда по направлению движения головки больше нетзапросов, головка возвращается в начало диска. Эффективность данного алгоритма связанас тем, что многие диски могут быстро переместить головку диска с последней дорожки нанулевую, причем даже за меньшее время, чем время поиска одной дорожки.Данные алгоритмы являются самыми простыми из возможных ввиду отсутствияограничений на время исполнения запроса. Если же такое ограничение присутствует, тонеобходимо применять более сложные, например, честные, алгоритмы.Алгоритмы для систем реального времени.4.2.Системами реального времени называются системы, в которых каждый запрос имеетсвой крайний срок исполнения. Например, мультимедиа-системы являются системамиреального времени.

Приведем несколькоалгоритмов, позволяющих соблюсти крайниесроки исполнения запросов.Введем следующие понятия:– минимальное время, когда запрос можно начать исполнять (например, моментего прихода в очередь)– самое позднее время, к которому запрос может быть завершен.– время, когда запрос начал исполняться.– время, когда запрос фактически закончил исполняться.Чтобы удовлетворить ограничения для real-time систем, должно быть выполненои.7Можно выделить два вида таких систем: строгие (в которых невыполнение dealineприводит к катастрофическим последствиям) и нестрогие (в которых несоблюдениеdeadline приводит к небольшим неудобствам работы системы.Алгоритм EDСамое простое, что можно придумать для таких систем – обслуживание запросов впорядке их крайнего срока исполнения.Алгоритм P-SCANАлгоритм есть модификация SCAN, но с учетом приоритетов.

Каждому запросуприсваивается значение приоритета. Внутри каждого уровня приоритета алгоритм работаеткак обычный SCAN, т.е. обслуживаются все запросы данного уровня приоритета,встречающиеся на пути. Когда в данном направлении не остается запросов данного уровня,планировщик проверяет, нет ли запросов более высокого уровня. Если есть, то переходимна более высокий уровень. Если нет, то на более низкий.SSEDO (Shortest Seek and Earliest Deadline by Ordering)Каждому запросу в очереди присваивается определенный вес.

Затем вычисляетсязначение приоритета, равное весу, умноженному на расстояние между текущим блоком иблоком запроса, для которого вычисляется значение. Запросы обслуживают в порядкеприоритета. Если у двух запросов одинаковый приоритет, то первым обслуживается запросс меньшим крайним сроком исполнения.В этом алгоритме те запросы, крайний срок исполнения для которых уже близко,получат высокий приоритет и будут обслужены раньше других.Данный алгоритм плохо работает, например, в следующей ситуации: если крайний срокисполнения запроса A уже близок, а крайний срок исполнения запроса B далеко, но блокзапроса B находится ближе, чем блок запроса A, то первым будет обслужен B.

В это жевремя запрос A может уже выйти за свой крайний срок исполнения.SSEDV (Shortest Seek and Earliest Deadline by Value)Алгоритм в некотором роде есть модификация SSEDO. Запросы обслуживаются впорядке возрастания их приоритета, который определяется какнекий параметр,(), где a –, d – расстояние от текущего блока до блока запроса, l –оставшееся время до deadline.SSEDO и SSEDV дают значительное улучшение производительности по сравнению спростейшими алгоритмами.8Алгоритмы для мультимедиа4.3.При подготовке пункта 4.3 использовались материалы [10], [11], [12] и [13].В большинстве алгоритмов периодические запросы исполняются в порядке истечениякритического срока их исполнения.

Как уже упоминалось, мультимедиа системы являютсясистемами реального времени. В предыдущем разделе уже описаны некоторые решения длясистем реального времени. Добавим в этот список описание алгоритмов, более подходящихдля мультимедиа.4.3.1. Алгоритм SCAN-EDFSCAN-EDF–модификацияописанноговышеалгоритмаSCAN.Запросыобслуживаются в порядке их deadline. Но если у запросов один и тот же крайний срокисполнения, то они обслуживаются в порядке их расположения на диске. Таким образом,этот алгоритм дает выигрыш только в системах, где часто несколько запросов имеют одини тот же крайний срок исполнения. Однако можно применить хитрый прием,увеличивающий количество запросов с одинаковым крайним сроком исполнени.Например, можно устанавливать крайние сроки исполнения, кратные определенным p.Опишем алгоритм в виде псевдокода:1) Пусть T -- набор из запросов с самыми близкими крайними сроками исполненя.2) Если |T|=1 (т.е.

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

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