Выбор в соответствии с источником запроса

RSS Случайное планирование Для анализа и моделирования

FIFO "Первым вошел — первым вышел" Наиболее беспристрастный метод

PRI Приоритет процесса Очередь запросов к диску

управляется извне

LIFO "Последним вошел — первым Максимизация локализации и

вышел" использования ресурса

Выбор в соответствии с содержимым запроса

SSTF Выбор самого короткого времени Высокая степень использования,

обслуживания малые очереди

SCAN Перемещение вперед и назад Лучшее распределение обслужи-

по диску вания

C-SCAN Однонаправленное перемещение Низкая изменчивость

с быстрым возвратом обслуживания

N-step-SCAN SCAN с N записями в одном пакете Гарантия обслуживания

FSCAN N-step-SCAN, где N — размер оче- Чувствительный к загрузке

реди в начале цикла SCAN

Приоритеты

В системе с использованием приоритета (PRI) управление планированием явля­ется внешним по отношению к программному обеспечению управления диском. Та­кой подход не имеет отношения к оптимизации использования диска, но зато удов­летворяет некоторым другим целям операционной системы. Коротким пакетным за­даниям, а также интерактивным заданиям часто присваивается более высокий приоритет, чем длинным заданиям, требующим более длительных вычислений. Эта схема позволяет быстро завершить большое количество коротких заданий в системе и обеспечивает малое время отклика. Однако при использовании этого метода у больших заданий оказывается слишком длительным ожидание выполнения диско­вых операций. Кроме того, такая стратегия может привести к противодействию со стороны пользователей, которые будут разделять свои задания на малые подзадания. Не подходит эта стратегия и для работы с базами данных.

Последним вошел — первым вышел

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

Три рассмотренные стратегии планирования — FIFO, PRI и LIFO — основа­ны исключительно на атрибутах очереди или запрашивающего процесса. Однакоесли планировщику известна текущая дорожка, то появляется возможность ис­пользования стратегии планирования, основанной на содержимом запроса.

SSTF

Стратегия выбора наименьшего времени обслуживания (Shortest Service Time First — SSTF) заключается в выборе того дискового запроса на ввод-вывод, который требует наименьшего перемещения головок из текущей позиции. Сле­довательно, мы минимизируем время поиска. Естественно, постоянный выбор минимального времени поиска не дает гарантии, что среднее время поиска при всех перемещениях будет минимальным, но тем не менее эта стратегия обеспе­чивает лучшую по сравнению с FIFO производительность дисковой системы. По­скольку головки могут перемещаться в двух направлениях, то при равных рас­стояниях для принятия решения может быть использован случайный выбор на­правления.

На рис. 11.8,6 и в табл. 11.2,6 показана производительность стратегии SSTF для той же последовательности запросов, что и при рассмотрении стратегии FIFO.

SCAN

Все стратегии, описанные к настоящему времени (за исключением FIFO), могут оставить некоторый запрос невыполненным до тех пор, пока не освободит­ся вся очередь — т.е. при работе всегда могут иметься новые запросы, которые будут выбраны до уже имеющегося в очереди. Избежать такого рода голодания можно при использовании стратегии SCAN.

При использовании этого алгоритма перемещение головки происходит только в одном направлении, удовлетворяя те запросы, которые соответствуют выбранному направлению. После достижения последней дорожки в выбранном направлении (или когда исчерпаются возможные запросы), направление изме­нится на противоположное.

Стратегия SCAN представлена на рис. 11.8,в и в табл. 11.2,6. Как видите, стратегия SCAN ведет себя почти так же, как и стратегия SSTF. Фактически, ес­ли предположить, что изначально головка перемещается в сторону меньших но­меров дорожек, то схема планирования окажется идентичной для SSTF и SCAN. Однако это статический пример, в котором в очередь не добавляется ни один за­прос. Однако даже при динамическом изменении очереди стратегии SCAN и SSTF выглядят, как правило, очень похоже.

Нетрудно увидеть, что стратегия SCAN оказывает предпочтение тем заданиям, чьи запросы относятся к дорожкам, находящимся ближе всего к центру либо наибо­лее удаленным от него, а также отдает предпочтение запросам, поступившим по­следними. Первой проблемы можно избежать путем применения стратегии C-SCAN; вторая же проблема решается с помощью стратегии N-step-SCAN.

C-SCAN

Стратегия C-SCAN (циклическое сканирование) ограничивает сканирование только одним направлением. Когда обнаруживается последняя дорожка в задан­ном направлении, головка возвращается в противоположный конец диска, и сканирование начинается снова. Это уменьшает максимальную задержку, вы­званную новыми запросами. Если при использовании стратегии SCAN ожидаемое время сканирования от внутренней к внешней дорожке равно t, то ожидае­мый интервал обслуживания секторов, находящихся на периферии, будет равен 2t. При использовании стратегии C-SCAN этот интервал будет порядка t+s_max, где s_max — максимальное время поиска.

Поведение стратегии C-SCAN показано на рис. 11.8,г и в табл. 11.2,г.

N-step-SCAN и FSCAN

При использовании стратегий SSTF, SCAN и C-SCAN может оказаться возмож­ной ситуация, когда один или несколько процессов с высокой частотой обращений к одной дорожке монополизируют устройство за счет многочисленных повторений за­просов к одной и той же дорожке. Наиболее характерна эта особенность для много­поверхностных дисков с большой плотностью записи. Для предотвращения такого "залипания головки" очередь дисковых запросов может быть сегментирована, при­чем за один прием полностью выполняется весь сегмент заданий. Примерами такого подхода являются стратегии N-step-SCAN и FSCAN.

Стратегия N-step-SCAN позволяет произвести сегментацию очереди диско­вых запросов на подочереди длиной N. Каждая подочередь обрабатывается за один прием с использованием стратегии SCAN. В ходе обработки очереди к не­которой другой очереди могут добавляться новые запросы. Если в конце текуще­го сканирования доступными оказываются менее N запросов, то все они обраба­тываются в следующем цикле сканирования. При больших значениях N выпол­нение алгоритма N-step-SCAN похоже на выполнение SCAN; предельный случай N=1 соответствует стратегии FIFO.

FSCAN — стратегия, использующая две подочереди. С началом сканирова­ния все запросы находятся в одной из очередей; другая при этом остается пус­той. Во время сканирования первой очереди все новые запросы попадают во вто­рую очередь. Таким образом, обслуживание новых очередей откладывается, пока не будут обработаны все старые запросы.