Программное управление внешними устройствами
Цели, которые стоят перед программным обеспечением:
1. унификация программных интерфейсов доступа к внешним устройствам (унификация именования, абстрагирование от свойств
конкретных устройств);
2. обеспечение конкретной модели синхронизации при выполнении обмена (синхронный, асинхронный обмен);
3. обработка возникающих ошибок (индикация ошибки, локализация ошибки, попытка исправления ситуации);
корректно обработать эту ситуацию, минимизировать негативные последствия.
4. буферизация обмена – в системе очень многоуровневая, применяется на всех этапах:
- развитые канала ввода-вывода могут иметь встроенный КЭШ, который управляется внутри этих каналов. Эта функция
остается на уровне ОС, этот КЭШ ОС полностью программноориентирован.
5. обеспечение стратегии доступа к устройству (распределенный доступ, монопольный доступ);
6. планирование выполнения операций обмена – возникает, когда возникает конкуренция за доступ к ресурсу.
Билет 53. Управление внешними устройствами. Буферизация обмена. Планирование дисковых обменов, основные алгоритмы.
Буферизация обмена
T – время обмена;
С – время выполнения программы между обменами
t – общее время выполнения программы
Схемы буферизации ввода-вывода
а) Без буферизации
Если обмен проходит без буферизации, то совокупное время выполнения программы будет складываться из времени обмена и времени выполнения программы между обменами.
б) Одинарная буферизация
При использовании одиночной буферизации подавляется заказ на обмен с ОП, и процесс может в этом случае не ожидать. Целесообразно использовать, когда идет интенсивный поток заказов на обмен.
в) Двойная буферизация
Модель использования двойной буферизации следующая: в один буфер помещаются данные по обмену, в другой ОС готовит данные за предыдущий обмен.
г) Циклическая буферизация
Какую схему выбрать зависит от интенсивности буферизации и особенности действий
Планирование дисковых обменов
Возможна ситуация, когда поток заказов на обмен > пропускной способности системы в некоторые моменты.
Тогда есть несколько вариантов действий:
1.Принимаем решения о порядке обработки запросов
2. начинаем учитывать приоритеты
3. осуществляем случайный выбор.
Проблема: Обмены могут быть зависимы друг от друга. В таком случае некоторые варианты не подходят.
Пусть наш диск может сразу переходить i-ой дорожки на j-ую без начального позиционирования.
Рассмотрим модельную ситуацию:
головка HDD позиционирована на дорожке 15
Очередь запросов к дорожкам: 4, 40, 11, 35, 7, 14
Варианты решения
1. простейшая модель – случайная выборка из очереди
2.
Общее время выполнения – 135ед.
Среднее время выполнения – 21.5 ед.
3.SSTF
Приоритет имеет обмен, для которого потребуется наименьшее время. «Жадный» алгоритм на каждом шаге пытается получить максимальный эффект. Общая нагрузка на систему с точки зрения обмена сокращается в 3 раза. Возможно «залипание» головки в том случае, если обмен идет интенсивно с одними и теми же дорожками. Некоторые процессы будут отделены.
4.LIFO
Смысл – попытка развязать последовательность обмена, связанную с новыми источниками.
Приоритетный алгоритм (RPI) – это алгоритм, когда последовательность обменов (очередь) имеет характеристику приоритетов. При использовании приоритетных алгоритмов может возникать проблема голодания или дискриминации. Проблема дискриминации возникает при непрерывном поступлении более приоритетных запросов на обмен, в это время как менее приоритетные запросы простаивают.
Находясь в начальной позиции сначала двигаемся в одну сторону до конца, затем в другую до конца.
Для " набора запросов
перемещений £ 2 х число дорожек
Выходим на минимальную (максимальную дорожку, а затем движемся в одну сторону). Пройдем не более двух маршрутов.
N-step-SCAN
Разделение очереди на подочереди длины £ N запросов каждая (из соображений FIFO). Последовательная обработка очередей. Обрабатываемая очередь не обновляется. Обновление очередей, отличных от обрабатываемой.
Этот алгоритм срывает головку с залипания.
Распространенный пример: 2 очереди, одна обрабатывается, другая собирает вновь поступающие запросы.
Билет 54 .RAID системы.
Существуют проблемы с организацией больших потоков данных.
В общем случае для дисковых систем имеют место как минимум две проблемы:
- Эффективность. Допустим, в системе присутствуют все уровни КЭШ, но производительности не хватает, так как обмены, которые производятся на дисковых устройствах, медленные.
- Надежность. Является одним из основных качеств любого программного решения. Соответственно есть необходимость создания надежных дисковых систем.
Все это обусловило появление так называемых RAID систем. Вначале RAID переводили как избыточный массив недорогих дисков. Со временем понятие RAID системы изменилось и на сегодняшний день оно переводится как избыточный массив независимых дисков.
Итак, RAID система представляет собой набор независимых дисков, которые рассматриваются ОС как единое дисковое устройство, где данные представляются в виде последовательности записей, которые называются полосы. /*Полосы цилиндрически распределены по дисковому устройству. */
Рассмотрим модели организации многодисковых систем, которые относятся к классу RAID.
Семь уровней RAID систем.
RAID 0 (без избыточности)
Не является настоящим RAIDуровнем, поскольку не использует избыточность для повышения эффективности.
Пользовательские и системные данные распределяются по всем дискам массива. Это лучше, чем использовать один большой диск, так как появляется вероятность того, что два
различных блока памяти, к которым поступили два различных запроса ввода\вывода, размещены на различных дисках, вследствие чего эти два запроса могут обрабатываться параллельно.
Все пользовательские и системные данные рассматриваются как хранящиеся на одном логическом диске. Диск делится на полосы, которые могут быть физическими блоками, селекторами или другими единицами хранения. Полосы циклически размещаются на последовательных дисках массива. В n-дисковом массиве первые n полос располагаются как первые полосы каждого из n дисков; вторые n- как вторые полосы каждого из n дисков и т.д.
«+» Если один запрос ввода\вывода обращается к множеству логически последовательных полос, то параллельно может быть обработано до n полос. Уменьшается время обработки.
RAID 1 (зеркалирование Предполагает наличие массивов устройств. 1ая группа – циклическое распределение устройств по уровням 2ая группа-копия первой. Запись идет параллельно и независимо)
«+»
1. Запрос на чтение может быть обслужен любым из двух дисков, содержащих необходимые данные; для обслуживания выбирается диск, у которого минимальное время поиска.
2. Для запроса на запись необходимо обновление обеих полос, что может быть выполнено в параллельном режиме. Поэтому скорость записи определяется самой медленной из них (т.е. той, для которой время поиска оказывается большим). Однако никаких дополнительных расходов на запись не требуется.
3. Простота восстановления данных в случае сбоя
RAID первого уровня это достаточно дорогостоящая конструкция, потому что получается двойное резервирование, но тем не менее эта система наиболее просто организована.
RAID 2 избыточность с кодами Хэмминга (Hamming, исправляет одинарные и выявляет двойные ошибки) Также используется разделение на полосы. Полосы оказываются очень малыми; нередко они соответствуют одному байту или слову. Обмен с синхронизацией головок чтения записи. Часть дисковых устройств предназначены для хранения содержательной части информации. Существует несколько дисковых устройств, в которых реализованы коды Хемминга.
При считывании осуществляется одновременный доступ ко всем дискам. Данные запроса и код коррекции ошибок передаются контролеру массива. При наличии однобитовой ошибки контролер способен быстро ее откорректировать, так что доступ для чтения в этой схеме не замедляется.
При записи происходит одновременное обращение ко всем дискам массива.
. Имеют место 2 проблемы:
1.Соответственно избыточность меньше, чем у RAID 1, но все равно она присутствует.
2. Есть зависимые обмены, т.е. обмены, которые организованы на специализированных движениях головок. И соответственно информация сильно распределена по RAID массиву. Т.е. последовательная информация за счет маленького размера полосок распределена. Т.е. одновременно происходит обращение ко всей цепочке. Т.е. нет независимых обменов в каждом дисковом устройстве.
RAID 3 (четность с чередующимися битами) 4 диска содержательные – для размещения логических данных. 5ый – контрольная избыточная информация.
Суть: Если представить, что модель RAID состоит из 5 дисков. В этих 5 дисках 4 диска содержательные, т.е. для размещения логического диска с соответствующими полосками. 5-й диск – это контрольная избыточная информация. Содержимое пятого диска выражается по формулам через содержимое первых 4.То есть определенный разряд 5-го диска представляется как «исключающее или» для соответствующих ему содержательных разрядов. В случае гибели какого-нибудь из устройств утверждается, что информацию на этом устройстве можно восстановить по второй, приведенной ниже, формуле. Т.е. имеет место избыточность, которая с одной стороны дает синхронизированный параллельный доступ, а с другой имеется функция, которая восстанавливает информацию в случае гибели устройства.
Пример: 4 диска данных, один – четности:
Потеря данных на первом диске
X4(i)=X3(i)XOR X2(i)XOR X1(i)XOR X0(i)
X1(i)=X4(i)XOR X3(i)XOR X2(i)XOR X0(i)
RAID 4
Он не синхронизированный, т.е. в этом плане он аппаратно организован проще, чем предыдущие. Схема примерно та же самая: имеется 4 устройства для логического диска, на которых располагаются полосы, и 5-е устройство, в котором находятся контрольные суммы. Контрольная сумма вычисляется по той же самой формуле, что и в RAID 3. И здесь есть проблема работы в случае независимого обмена.
Пример: 4 диска данных, один – четности:
При независимом обмене происходит обновление следующим образом: предположим, что обновление произошло на первом диске.
X4(i)=X3(i)XOR X2(i)XOR X1(i)XOR X0(i)
все разряды на 4-м будут обновлены по следующей формуле:
X4new(i)=X4(i)XOR X1(i)XOR X1new(i)
Восстановление информации проходит по предыдущей схеме (это схема обновления, потому что обмены могут быть независимыми, т.е. обмен может происходить только по одной полоске, но для этого необходимо скорректировать содержимое контрольной полоски и использовать ее для восстановления).
RAID 5 (распределенная четность – циклическое распределение «четности»)
RAID 5 - это использование циклического распределения контрольного диска.
Суть: в RAID 3 и RAID 4 есть некоторая диспропорция в распределении потока обмена, т.е. сильно нагружено последнее устройство (это плохо тем, что рано или поздно это устройство выйдет из строя первым), на котором находится контрольная сумма. Т.о. контрольный диск циклически распределен по всем устройствам, т.е. вся работа равномерно распределяется.
RAID 6 (двойная избыточность – циклическое распределение четности с использованием двух схем контроля: N+2 дисков)
RAID 6 – это двойная избыточность. Делается еще одно дополнительное устройство для хранения избыточной информации.
Какие-то из RAID массивов можно реализовать чисто программно. Какие-то из них можно реализовать только аппаратно. Какие-то из них можно реализовать в зависимости от решения. Это все относится к проблеме управления внешними устройствами: качеством и свойством работы внешних устройств в системе.
Уровни RAID (сравнение)
| Категория | Уровень | Описание | Скорость обработки запросов | Скорость передачи данных | Типичное применение |
| Расщепление | Без избыточности | Большие полосы: отлично | Малые полосы: отлично | Приложения с некритическими данными, требующие высокой производительности | |
| Зеркалирование | Зеркалирование | Хорошо/ удовлетворительно | удовлетворительно/ удовлетворительно | Системные диски, важные файлы | |
| Параллельный доступ | Избыточность с кодами Хэмминга | Плохо | Отлично | ||
| Четность с чередующимися битами | Плохо | Отлично | Приложения с большими запросами ввода/вывода (графич. редакторы, САПР) | ||
| Независимый доступ | Четность с чередующимися блоками | Отлично/ удовлетворительно | Удовлетворительно/ плохо | ||
| Распределенная четность с чередующимися блоками | Отлично/ удовлетворительно | Удовлетворительно/ плохо | Высокая скорость запросов, интенсивное чтение, поиск данных | ||
| Двойная распределенная четность с чередующимися блоками | Отлично/плохо | Удовлетворительно/ плохо | Приложения, требующие исключительно высокой надежности |