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

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

Три рассмотренные стратегии планирования — 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,г.