Операционные системы/Управление внешними устройствами. Буферизация обмена.
Материал из eSyr's wiki.
[править] Буферизация обмена
T – время обмена; С – время выполнения программы между обменами t – общее время выполнения программы Схемы буферизации ввода-вывода
- Без буферизации
Если обмен проходит без буферизации, то совокупное время выполнения программы будет складываться из времени обмена и времени выполнения программы между обменами. - Одинарная буферизация
При использовании одиночной буферизации подавляется заказ на обмен с ОП, и процесс может в этом случае не ожидать. Целесообразно использовать, когда идет интенсивный поток заказов на обмен. - Двойная буферизация
Модель использования двойной буферизации следующая: в один буфер помещаются данные по обмену, в другой ОС готовит данные за предыдущий обмен. - Циклическая буферизация
Какую схему выбрать зависит от интенсивности буферизации и особенности действий
[править] Планирование дисковых обменов
Возможна ситуация, когда поток заказов на обмен > пропускной способности системы в некоторые моменты.
Тогда есть несколько вариантов действий:
- Принимаем решения о порядке обработки запросов
- начинаем учитывать приоритеты
- осуществляем случайный выбор.
Проблема: Обмены могут быть зависимы друг от друга. В таком случае некоторые варианты не подходят.
Пусть наш диск может сразу переходить i-ой дорожки на j-ую без начального позиционирования.
Рассмотрим модельную ситуацию:
головка HDD позиционирована на дорожке 15
Очередь запросов к дорожкам: 4, 40, 11, 35, 7, 14
Варианты решения 1. Простейшая модель – случайная выборка из очереди
2. FIFO
Общее время выполнения – 135ед. Среднее время выполнения – 21.5 ед.
3. SSTF
Приоритет имеет обмен, для которого потребуется наименьшее время. «Жадный» алгоритм на каждом шаге пытается получить максимальный эффект. Общая нагрузка на систему с точки зрения обмена сокращается в 3 раза. Возможно «залипание» головки в том случае, если обмен идет интенсивно с одними и теми же дорожками. Некоторые процессы будут дискриминированны.
4. LIFO
Смысл – попытка развязать последовательность обмена, связанную с новыми источниками.
5. SCAN
Приоритетный алгоритм (RPI) – это алгоритм, когда последовательность обменов (очередь) имеет характеристику приоритетов. При использовании приоритетных алгоритмов может возникать проблема голодания или дискриминации. Проблема дискриминации возникает при непрерывном поступлении более приоритетных запросов на обмен, в это время как менее приоритетные запросы простаивают.
6. C-SCAN
Выходим на минимальную (максимальную) дорожку, а затем движемся в одну сторону. Пройдем не более двух маршрутов.
7. N-step-SCAN
Разделение очереди на подочереди длины £ N запросов каждая (из соображений FIFO). Последовательная обработка очередей. Обрабатываемая очередь не обновляется. Обновление очередей, отличных от обрабатываемой.
Этот алгоритм срывает головку с залипания.
Распространенный пример: 2 очереди, одна обрабатывается, другая собирает вновь поступающие запросы.