Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 21)

•планирование выполнения операций обмена

Буферизация обмена

Введём следующие обозначения:

T – время обмена;

С – время выполнения программы между обменами

t – общее время выполнения программы

Схемы буферизации ввода-вывода

а) Без буферизации

В данном случае t = C+T.

б) Одинарная буферизация

Если обозначить за M – время перемещения, то здесь t = max(C,T)+M

в) Двойная буферизация

г) Циклическая буферизация

Это является большой оптимизацией, т.к. позволяет разделить потоки ввода/вывода.

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

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

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

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

Проблема: перемещение считавающей и записывающей головок. Эти перемещения иногда слишком большие, надо их как-то оптимизовать.

Стратегии планирования:

1. FIFO 2. SSTF 3. LIFO

5. SCAN 5. C-SCAN

1. FIFO. Не самая эффективная стратегия, но одна из самых простых.

2. SSTF - Shortest Service Time First – «жадный» алгоритм – на каждом шаге поиск обмена с минимальным перемещением. Более эффективная стратегия, но здесь возникает проблема голодания процессов.

3. LIFO. Менее эффективен, чем SSTF, но почти решает проблему голодания процессов.

4.

PRI – алгоритм, основанный на приоритетах процессов. Достаточно эффективен, но опять возникает та же проблема – голодание , запрос может «зависать» из-за прихода наиболее приоритетных.

5. SCAN - Алгоритм «лифта» - сначала «движение» в одну сторону до «упора», затем в другую, также до «упора». Для " набора запросов перемещений £ 2 х число_дорожек. Хорош тем, что он детерминирован, но опять присутствует голодание процессов.

6.

C-SCAN - Циклическое сканирование

Сканирование в одном направлении. Ищем минимальный номер дорожки, затем «движемся наверх». (обмен между длинами)

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

Все эти стратегии могут быть реализованы программно или через периферийные процессы.

RAID системы.

RAID – Redundant Array of Independent (Inexpensive) Disks –

избыточный массив независимых (недорогих) дисков.

RAID система - набор физических дисковых устройств, рассматриваемых операционной системой, как единое дисковое устройство (данные распределяются по физическим устройствам, образуется избыточная информация, используемая для контроля и восстановления информации).

Проблема: стоимость и быстродействие диска зависит от его характеристик, устройства большего объёма быстрее работают.

RAID системы помогают эту проблему решить – из недорогих компонентов можно строить хорошие вещи.

RAID системы были более популярны раньше, т.к. раньше описанная проблема была более актуальна.

Цели:

• за счёт избыточности RAID – избыточность информации

• повышение скорости

Семь уровней RAID систем.

1
. 1. RAID 0 (без избыточности)

(полосы циклически распределяются между устройствами)

2.

2. RAID 1 (зеркалирование)

(имеется 2 комплекта устройств, каждый обмен на них дублируется (на оба))

3. RAID 2 (избыточность с кодом Хэмминга)

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

4
. RAID 3 (чётность с чередующимися битами)

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

Это синхронизационная модель.

Пример: 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)

5. RAID 4 (упрощение RAID 3)

(Используется одно устройство, работа идёт не в терминах длины, а в терминах полос)

Пример: 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)

5. RAID 5 (распределенная четность – циклическое распределение «четности» )

6. RAID 6 (двойная избыточность – циклическое распределение четности с использованием двух схем контроля: N+2 дисков)

Каждая RAID-модель применяется в своей области. Наиболее распростарнено сейчас полное зеркалирование.

OC Unix: Работа с внешними устройствами

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

Иерархия драйверов

Как только мы говорим о драйверах, сразу появляется виртуальность.

Проблема именования устройств:

1. устройства, которые используются внутри ядра.

2. через специальные файлы устройств.

Специальные файлы устройств (/dev)

•Байт-ориентированные устройства

•Блок-ориентированные устройства

Вся информация о файле находится в его индексном дексрипторе (ИД). ИД содержит также и тип устройств (байт- и блок-ориентированность).

Оптимизация в системе. В частности, использовуется кэш-буферизация (для блок-ориентированных устройств) – исполняет её ОС. Это минимизует обмены с системными устройствами. В системе есть устройства, которые одновременно могут быть и байт- и блок-ориентированными, например, это RAM.

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

Содержимое файлов устройств размещается исключительно в соответствующем индексном дескрипторе

Структура ИД файла устройства:

•«Старший номер» (major number) устройства

•Тип файла устройства

•«Младший номер» (minor number) устройства

(старший номер драйвера – номер группы устройств, соответствующий драйверу, младший номер – номер устройства в этой группе)

Две системные таблицы драйверов устройств:

•bdevsw(блок-ориентированные устройства)

•cdevsw(байт-ориентированные устройства)

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

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

Типовой набор точек входа в драйвер:

•bopen(), bclose()

•bread(), bwrite()

•bioctl()

•bintr()

•bstrategy()

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

•Инициализация устройства или старт системы, определение ядром состава доступных устройств

•Обработка запроса ввода/вывода

•Обработка прерывания, связанного с данным устройством (это не очевидно, с одним устройством может быть связано два и более драйвера. ОС внутри решает, что делать по умолчанию.)

•Выполнение специальных команд управления

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

«Жёсткое», статистическое встраивание драйверов в код ядра

Динамическое включение драйвера в систему

• Загрузка и динамическое связывание драйвера с кодом ядра

•Инициализация драйвера и соответствующего ему устройства

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

Для организации интерфейса работы с файлами ОС использует информационные структуры и таблицы двух типов:

•ассоциированные с процессом

•ассоциированные с ядром ОС

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

Таблица файлов (размещается в памяти ОС)

Таблица открытых файлов

Пример:

Пример:

1. Начальное состояние.

2. Добавили один процесс.

3. Первый процесс использовал системный вызов fork().

Т.е.:

Свяжем ещё один ИД – значит, в ТИДОФ должно быть 2 – значит, с файлом работает 2 процесса, у каждого свой указатель чтения/записи. Освобождаем ИД – получаем там 0. Возникает проблема надёжности. Но прикаждом изменении ИД мы не сбрасываем содержимое на диск, т.е. они периодически не соответствуют друг другу. Поэтому в ОС существует параметр, позволяющий ОС периодически сбрасывать информацию на диск. Это можно сделать и вручную.

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

Пул буферов размера в один блок каждый

Имеется таблица буферовю Размер буфера – один блок. При боращении к блоку всё происходит, как при кэш-буферизации.

Плюсы:

Оптимизация работы ОС, за счет минимизации реальных обращений к физическому устройству

(Всесь UNIX - фактически эшелонированная буферизация: оптимизация работы с ИД в обмене)

Минусы:

•Критичность к несанкционированным отключениям питания (тз-за этого может возникнуть потеря информации в ИД, в блоках)

•Разорванность во времени факта обращения к системе за обменом и реальным обменом

Схема работы:

1.Поиск заданного блока в буферном пуле. Нашли- переходим на шаг 4.

2.Поиск буфера в буферном пуле для чтения и размещения заданного блока.

3.Чтение блока в найденный буфер.

4.Изменение счётчика времени во всех буферах.

5.Содержимое данного буфера передаётся в качестве результата.

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

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

Пользовательская команда SYNC (примерно то же самое)

Избыточность системы, позволяющая восстанавливать информацию

7. Управление оперативной памятью (ОП)

Основные задачи:

1.Контроль состояния каждой единицы памяти (свободна/распределена). Система должна иметь достоверную информацию о том, какие единицы заняты, кем и на сколько. Это реализуется и аппаратно, и программно.

2.Стратегия распределения памяти (кому, когда и сколько памяти должно быть выделено).

3.Выделение памяти (выбор конкретной области, которая должна быть выделена).

4.Стратегия освобождения памяти (процесс освобождает, ОС “забирает” окончательно или временно).

Характеристики

Список файлов лекций