Операционные системы. Управление внешними устройствами

1. Операционные системы

Управление внешними устройствами

2. Управление внешними устройствами. Архитектура

ЦП
ОЗУ
Внешнее
устройство
1. Непосредственное управление внешними
устройствами центральным процессором
ОЗУ
ЦП
контроллер внешнего устройства
Внешние
устройства
2. Синхронное управление внешними устройствами
использованием контроллеров внешних устройств
3. Асинхронное управление внешними устройствами с
использованием контроллеров внешних устройств

3. Управление внешними устройствами. Архитектура

ОЗУ
ЦП
DMA
контроллер
+
контроллер
или процессор
ввода/вывода
Внешнее
устройство
4. Использование контроллера прямого доступа к
памяти (DMA) при обмене.
5. Управление внешними устройствами с
использованием процессора или канала
ввода/вывода.

4. Программное управление внешними устройствами

Драйверы логических устройств
Драйверы физических устройств
Программы обработки прерываний
Аппаратура

5. Программное управление внешними устройствами

• унификация программных интерфейсов доступа к
внешним устройствам (унификация именования,
абстрагирование от свойств конкретных устройств)
• обеспечение конкретной модели синхронизации при
выполнении обмена (синхронный, асинхронный
обмен)
• обработка возникающих ошибок (индикация ошибки,
локализация ошибки, попытка исправления ситуации);
• буферизация обмена
• обеспечение стратегии доступа к устройству
(распределенный доступ, монопольный доступ);
• планирование выполнения операций обмена

6. Планирование дисковых обменов

Рассмотрим модельную ситуацию:
головка HDD позиционирована на дорожке 15
Очередь запросов к дорожкам: 4, 40, 11, 35, 7, 14
FIFO
Путь
L
головки
11
15 4
36
4 40
40 11 29
11 35 24
28
35 7
7
7 14
общ. 135
средн. 22,5
0
4
7
11 14 15
35
40

7. Планирование дисковых обменов

Shortest Service Time First — «жадный» алгоритм — на
каждом шаге поиск обмена с минимальным
перемещением
SSTF
Путь
L
головки
1
15 14
3
14 11
4
11 7
3
7 4
31
4 35
5
35 40
общ. 47
средн. 7,83

8. Планирование дисковых обменов

PRI — алгоритм, основанный на приоритетах процессов.
SCAN
Путь
L
головки
15 35 20
5
35 40
40 14 26
3
14 11
4
11 7
3
7 4
общ. 61
средн. 10,16
«Лифт» — сначала «движение» в одну
сторону до «упора», затем в другую,
также до «упора»
Для набора запросов
перемещений 2 число_дорожек

9. Планирование дисковых обменов

С-SCAN
Путь
L
головки
11
15 4
3
4 7
4
7 11
3
11 14
14 35 21
5
35 40
общ. 47
средн. 7,83
Циклическое сканирование
Сканирование в одном направлении.
Ищем минимальный номер дорожки,
затем «движемся наверх»

10. Планирование дисковых обменов

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

11. RAID системы

RAID (Redundant Array of Independent (Inexpensive)
Disks) — избыточный массив независимых (недорогих)
дисков (1987, Беркли, Калифорния, США).
RAID система — набор физических дисковых
устройств, рассматриваемых операционной системой,
как единое дисковое устройство (данные распределяются
по физическим устройствам, образуется избыточная
информация,
используемая
для
контроля
и
восстановления информации).

12. Уровни RAID

полоса 0
полоса 1
полоса 2
полоса 3
полоса 4
полоса 5
полоса 6
полоса 7
полоса 8
полоса 9
полоса 10
полоса 11
полоса 12
полоса 13
полоса 14
полоса 15
RAID 0 (без избыточности)
полоса 0
полоса 0
полоса 1
полоса 1
полоса 2
полоса 2
полоса 3
полоса 3
RAID 1 (зеркалирование)

13. Уровни RAID

b0
b1
b2
b3
f0(b)
f1(b)
RAID 2 избыточность с кодами Хэмминга
f2(b)

14. Уровни RAID

Пример: 4 диска данных,
один — четности: Потеря
данных на первом диске
b0
b1
b2
b3
P(b)
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 3 (четность с
чередующимися битами)
XOR – исключающее или (сложение по модулю 2)
x
0
0
1
1
y
0
1
0
1
x XOR y
0
1
1
0
Некоторые Свойства:
• a XOR a = 0
• a XOR b = b XOR a
• (a XOR b) XOR c = a XOR (b XOR c)

15. Уровни RAID

полоса 0
полоса 1
полоса 2
полоса 3
P(0-3)
полоса 4
полоса 5
полоса 6
полоса 7
P(4-7)
полоса 8
полоса 9
полоса 10
полоса 11
P(8-11)
полоса 12
полоса 13
полоса 14
полоса 15
P(12-15)
RAID 4
Изначально: X4(i) = X3(i) XOR X2(i) XOR X1(i) XOR X0(i)
После обновления полосы на диске X1:
X4new(i) = X4(i) XOR X1(i) XOR X1new(i) – почему?
X4new (i) = X3(i) XOR X2(i) XOR X1new (i) XOR X0(i)
/* добавляем: XOR X1(i) XOR X1 (i) ==0*/
=X3(i) XOR X2(i) XOR X1new (i) XOR X0(i) XOR X1(i) XOR X1 (i)
/* переставляем, выделяем: X3(i) XOR X2(i) XOR X1(i) XOR X0(i) X4(i) */
= X4(i) XOR X1(i) XOR X1new(i) !!!
Восстановление потерянного диска данных аналогично RAID 3

16. Уровни RAID

полоса 0
полоса 1
полоса 2
полоса 3
P(0-3)
полоса 4
полоса 5
полоса 6
P(4-7)
полоса 7
полоса 8
полоса 9
P(8-11)
полоса 10
полоса 11
полоса 12
P(12-15)
полоса 13
полоса 14
полоса 15
P(16-19)
полоса 16
полоса 17
полоса 18
полоса 19
RAID 5 (распределенная четность — циклическое
распределение «четности»)

17. Уровни RAID

полоса 0
полоса 1
полоса 2
полоса 3
P(0-3)
Q(0-3)
полоса 4
полоса 5
полоса 6
P(4-7)
Q(4-7)
полоса 7
полоса 8
полоса 9
P(8-11)
Q(8-11)
полоса 10
полоса 11
полоса 12
P(12-15)
Q(12-15)
полоса 13
полоса 14
полоса 15
RAID 6 (двойная избыточность — циклическое
распределение четности с использованием двух схем
контроля: N+2 дисков)

18. UNIX: Работа с внешними устройствами

1. Файлы устройств, драйверы
1.1.
1.2.
1.3.
1.4.
Файлы устройств
Системные таблицы драйверов устройств
Ситуации, вызывающие обращение к функциям драйвера
Включение/удаление драйверов в системе
2. Организация обмена данных с файлами
3. Буферизация при блок-ориентированном обмене
4. Борьба со сбоями

19. Файлы устройств, драйверы

• Иерархия драйверов
• Специальные файлы устройств (/dev)
• Байт-ориентированные устройства
• Блок-ориентированные устройства
Файловая система
Блок-ориентированные
устройства
Оперативная память
Байт-ориентированный
интерфейс обмена
Блок-ориентированный
интерфейс обмена

20. Файлы устройств

• Содержимое файлов устройств размещается
исключительно в соответствующем индексном
дескрипторе
• Структура ИД файла устройства:
• «Старший номер» (major number) устройства
• Тип устройства
• «Младший номер» (minor number) устройства
• Системные таблицы драйверов устройств:
• bdevsw
• cdevsw

21. Системные таблицы драйверов устройств

• Запись таблицы — коммутатор устройства
• Типовой набор точек входа в драйвер:
open(), close()
read(), write()
ioctl()
intr()
strategy()

22. Ситуации, вызывающие обращение к функциям драйвера

• Старт системы, определение ядром состава
доступных устройств
• Обработка запроса ввода/вывода
• Обработка прерывания, связанного с данным
устройством
• Выполнение специальных команд управления

23. Включение/удаление драйверов в систему

• «Жёсткое», статистическое встраивание драйверов
в код ядра
• Динамическое включение драйвера в систему
Загрузка и динамическое связывание драйвера с кодом
ядра
• Инициализация драйвера и соответствующего ему
устройства

24. Организация обмена данными с файлами

• Таблица индексных дескрипторов открытых файлов
(размещается в памяти ядра ОС)
• Таблица файлов (размещается в памяти ОС)
• Таблица открытых файлов

25. Пример

ТОФ 1
ТИДОФ
12 Дескрипт.
ТФ
12 pointer1
1 pointer2
name
ТОФ 3
name
ТОФ 2
name
fork

26. Буферизация при блок-ориентированном обмене

Буферизация при блокориентированном обмене
1. Поиск заданного блока в буферном пуле. Нашли-
переходим на шаг 4
2. Поиск буфера в буферном пуле для чтения и
размещения заданного блока
3. Чтение блока в найденный буфер
4. Изменение счётчика времени во всех буферах
5. Содержимое буфера передаётся в качестве
результата

27. Буферизация при блок-ориентированном обмене

Буферизация при блокориентированном обмене
• Оптимизация работы ОС, за счет минимизации
реальных обращений к физическому устройству
• Недостатки:
• Критичность к несанкционированным отключениям
питания
• Разорванность во времени факта обращения к системе
за обменом и реальным обменом

28. Борьба со сбоями

• Наличие параметра, определяющего периоды времени,
через которые осуществляется сброс системных
данных, который может оперативно меняться
• Пользовательская команда SYNC
• Избыточность системы, позволяющая восстанавливать
информацию