Операционные системы/Управление внешними устройствами. Буферизация обмена.

Материал из eSyr's wiki.

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: == Буферизация обмена == T – время обмена; С – время выполнения программы между обменами t – общее время...)
(Новая: == Буферизация обмена == T – время обмена; С – время выполнения программы между обменами t – общее время...)
 

Текущая версия

[править] Буферизация обмена

T – время обмена; С – время выполнения программы между обменами t – общее время выполнения программы Схемы буферизации ввода-вывода

  1. Без буферизации
    Изображение:Buf 0.jpg

    Если обмен проходит без буферизации, то совокупное время выполнения программы будет складываться из времени обмена и времени выполнения программы между обменами.
  2. Одинарная буферизация
    Изображение:Buf 1.jpg

    При использовании одиночной буферизации подавляется заказ на обмен с ОП, и процесс может в этом случае не ожидать. Целесообразно использовать, когда идет интенсивный поток заказов на обмен.
  3. Двойная буферизация
    Изображение:Buf 2.jpg

    Модель использования двойной буферизации следующая: в один буфер помещаются данные по обмену, в другой ОС готовит данные за предыдущий обмен.
  4. Циклическая буферизация
    Изображение:Buf 3.jpg

    Какую схему выбрать зависит от интенсивности буферизации и особенности действий

[править] Планирование дисковых обменов

Возможна ситуация, когда поток заказов на обмен > пропускной способности системы в некоторые моменты.

Тогда есть несколько вариантов действий:

  1. Принимаем решения о порядке обработки запросов
  2. начинаем учитывать приоритеты
  3. осуществляем случайный выбор.

Проблема: Обмены могут быть зависимы друг от друга. В таком случае некоторые варианты не подходят.

Пусть наш диск может сразу переходить i-ой дорожки на j-ую без начального позиционирования.

Рассмотрим модельную ситуацию:

головка HDD позиционирована на дорожке 15

Очередь запросов к дорожкам: 4, 40, 11, 35, 7, 14

Варианты решения 1. Простейшая модель – случайная выборка из очереди

2. FIFO

Изображение:Dev fifo.jpg

Общее время выполнения – 135ед. Среднее время выполнения – 21.5 ед.


3. SSTF

Приоритет имеет обмен, для которого потребуется наименьшее время. «Жадный» алгоритм на каждом шаге пытается получить максимальный эффект. Общая нагрузка на систему с точки зрения обмена сокращается в 3 раза. Возможно «залипание» головки в том случае, если обмен идет интенсивно с одними и теми же дорожками. Некоторые процессы будут дискриминированны.

4. LIFO

Изображение:Dev sstf lifo.jpg

Смысл – попытка развязать последовательность обмена, связанную с новыми источниками.

5. SCAN

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

Изображение:Dev scan.jpg

6. C-SCAN

Выходим на минимальную (максимальную) дорожку, а затем движемся в одну сторону. Пройдем не более двух маршрутов.

Изображение:Dev c-scan.jpg

7. N-step-SCAN

Разделение очереди на подочереди длины £ N запросов каждая (из соображений FIFO). Последовательная обработка очередей. Обрабатываемая очередь не обновляется. Обновление очередей, отличных от обрабатываемой.

Этот алгоритм срывает головку с залипания.

Распространенный пример: 2 очереди, одна обрабатывается, другая собирает вновь поступающие запросы.

Получено с http://esyr.org/wiki/%D0%9E%D0%BF%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D1%8B%D0%B5_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D1%8B/%D0%A3%D0%BF%D1%80%D0%B0%D0%B2%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B2%D0%BD%D0%B5%D1%88%D0%BD%D0%B8%D0%BC%D0%B8_%D1%83%D1%81%D1%82%D1%80%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B0%D0%BC%D0%B8._%D0%91%D1%83%D1%84%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BE%D0%B1%D0%BC%D0%B5%D0%BD%D0%B0.
Личные инструменты
Разделы