Операционные системы: Лекции: Диски. Таймеры. (операционные системы)

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

| главная | лекции | лабораторные работы | литература | документация | выполнение работ | тесты | форум |

Лекция 10

Диски. Таймеры.

Литература

- Современные операционные системы, Э. Таненбаум, 2002, СПб, Питер, 1040 стр., подробнее>>
- Сетевые операционные системы Н. А. Олифер, В. Г. Олифер (в zip архиве 1.1Мбайт)
- Сетевые операционные системы Н. А. Олифер, В. Г. Олифер, 2001, СПб, Питер, 544 стр., подробнее>>

10.1 Аппаратная часть дисков

10.1.1 Магнитные диски

Основные понятия:

Головка (Head) - электромагнит, скользящий над поверхностью диска, для каждой поверхности используется своя головка. Нумерация начинается с 0.

Дорожка (Track) - концентрическая окружность, которое может прочитать головка в одной позиции. Нумерация дорожек начинается с внешней (первая имеет номер - 0).

Цилиндр (Cylinder) - совокупность всех дорожек с одинаковым номером на всех дисках, т.к. дисков может быть много и на каждом диске запись может быть с двух сторон.

Маркер - от него начинается нумерация дорожек, есть на каждом диске.

Сектор - на сектора разбивается каждая дорожка, сектор содержит минимальный блок информации. Нумерация секторов начинается от маркера.

Геометрия жесткого диска - набор параметров диска, количество головок, количество цилиндров и количество секторов.

У современных жестких дисков контроллер встроен в само устройство, и берет на себя большую часть работы, которую не видит ОС.

Например, скрывают физическую геометрию диска, предоставляя виртуальную геометрии.

Физическая и виртуальная геометрия диска

На внешних дорожках число секторов делают больше, а на внутренних меньше. На реальных дисках таких зон может быть несколько десятков.

10.1.2 RAID (Redundant Array of Independent Disk - массив независимых дисков с избыточностью)

Для увеличения производительности или надежности операций ввода-вывода с диском был разработан стандарт для распараллеливания или дублирования этих операций

Основные шесть уровней RAID:

- RAID 0 - чередующий набор, соединение нескольких дисков в один большой логический диск, но логический диск разбит так, что запись и чтение происходит сразу с несколько дисков. Например, записываем блок 1, 2, 3, 4, 5, каждый блок будет записываться на свой диск.
  Преимущества
  - удобство одного диска
  - увеличивает скорость записи и чтения
  Недостатки
  - уменьшает надежность (в случае выхода одного диска, массив будет разрушен), избыточность не предусмотрена.

- RAID 1 - зеркальный набор, параллельная запись и чтение на несколько дисков с дублированием (избыточность).
  Преимущества
  - дублирование записей
  - увеличивает скорость чтения (но не записи)
  Недостатки
  - требует в два раза больше дисковых накопителей

- RAID 2 - работает на уровне слов и даже байт. Например, берется полбайта (4 бита) и прибавляется 3 бита четности (1, 2, 4 - рассчитанные по Хэммингу), образуется 7-битовое слово. В случае семи дисков слово записывается побитно на каждый диск. Так как слово пишется сразу на все диски, они должны быть синхронизированы.
  Преимущества
  - надежность
  - увеличивает скорость записи и чтения (при потоке, но при отдельных запросах не увеличивает)
  Недостатки
  - нужна синхронизация дисков.

- RAID 3 - упрощенная версия RAID 2, для каждого слова считается только один бит четности.
  Преимущества
  - надежность
  - увеличивает скорость записи и чтения (при потоке, но при отдельных запросах не увеличивает)
  Недостатки
  - нужна синхронизация дисков.

- RAID 4 - аналогичен уровню RAID 0, но с добавлением диска четности. Если любой из дисков выйдет из строя, его можно восстановить с помощью диска четности.
  Преимущества
  - надежность
  - не нужна синхронизация дисков
  Недостатки
  - не дает увеличения производительности, узким местом становится диск четности при постоянных пересчетах контрольных сумм.

- RAID 5 - аналогичен уровню RAID 4, но биты четности равномерно распределены по дискам.

На практике, как правило, используют RAID 0, 1 и 5.

Системы RAID уровней от 0 до 5.

10.1.3 Компакт-диски

Запись на CD-ROM диски производятся с помощью штамповки.

Сначала CD-диски использовались только для записи звука, стандарт которого был описан ISO 10149 ("Красная книга").

Пит - единица записи информации (впадина при штамповке, темное пятно, прожженное в слое краски в CD-R, область фазового перехода)

Запись на CD-ROM производится спирально

В 1984 году была опубликована "Желтая книга", в которой описан следующий стандарт.

Для записи данных было необходимо повысить надежность, для этого каждый байт (8 бит) стали кодировать в 14 разрядное число (по размеру почти дублирование записи, но за счет кодирования эффективность может быть, как при тройной записи), чтобы можно было восстановить потерянные биты.

Логическое расположение данных на CD-ROM для режима 1

Заголовок содержит:

- Первые 12-ть байт заголовка содержат 00FFFFFFFFFFFFFFFFFFFF00, чтобы считывающее устройство могло распознать начало сектора.

- Следующие три байта содержат номер сектора.

- Последний байт содержит код режима

ECC (Error Correction Code) - код исправления ошибок.

В режиме 2 поле данных объединено с полем ECC в 2336-байтное поле данных. Этот режим можно использовать, если не требуется коррекция ошибок, например, видео и аудио запись.

Коррекция ошибок осуществляется на трех уровнях:

- внутри символа

- в кадре

- в CD-ROM-секторе

Поэтому 7203 байта содержат только 2048 байта полезной нагрузки, около 28%.

В 1986 году была выпущена "Зеленая книга", к стандарту была добавлена графика, и возможность совмещения в одном секторе аудио, видео и данных.

Файловая система для CD-ROM называется High Sierra , которая оформлена в стандарт ISO 9660.

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

- 1 уровень - файлы имеют имена формата, схожего с MS-DOS - 8 символов имя файла плюс до трех символов расширения, файлы должны быть непрерывными. Глубина вложенности каталогов ограничена восемью. Этот уровень понимают почти все операционные системы.

- 2 уровень - имена файлов могут быть до 32 символов, файлы должны быть непрерывными.

- 3 уровень - позволяет использовать сегментированные файлы.

Для этого стандарта существуют расширения:

- Rock Ridge - позволяет использовать длинные файлы, а также UID, GID и символические ссылки.

10.1.3.1 Компакт-диски с возможностью записи CD-R

Запись на CD-R диски производятся с помощью локального прожигания нанесенного слоя красителя.

Используются лазеры с двумя уровнями разной мощности, для записи 8-16 мВт, для чтения 0.5 мВт.

В 1989 году была выпущена "Оранжевая книга", это документ определяет формат CD-R, а также новый формат CD-ROM XA , который позволяет посекторно дописывать информацию на CD-R.

CD-R-дорожка - последовательно записанные за один раз секторы. Для каждой такой дорожки создается свой VTOC (Volume Table of Contents - таблица содержания тома), в котором перечисляются записанные файлы.

Каждая запись производится за одну непрерывную операцию, поэтому если у вас будет слишком загружен компьютер (мало памяти или медленный диск), то вы можете испортить диск, т.к. данные не будут поспевать поступать на CD-ROM.

10.1.3.2 Многократно перезаписываемые компакт-диски CD-RW

Запись на CD-RW диски производятся локального перевода слоя из кристаллического в аморфное состояние.

Используются лазеры с тремя уровнями разной мощности.

Эти диски можно отформатировать (UDF), использовать их в место дискет и дисков.

10.1.3.3 Универсальный цифровой диск DVD (Digital Versatile Disk)

Были сделаны следующие изменения:

- Размер пита уменьшили в два раза (с 0.8 мкм до 0.4мкм)

- Более тугая спираль (0.74 мкм между дорожками, вместо 1.6 у компакт-дисков)

- Уменьшение длины волны лазера (0.65 вместо 0.78)

Это позволило увеличить объем с 650 Мбайт до 4.7 Гбайт.

Определены четыре следующих формата:

1. Односторонний, одноуровневый (4.7 Гбайт)

2. Односторонний, двухуровневый (8.5 Гбайт), размеры пита второго уровня приходится делать больше, иначе не будут считаны, т.к. первый полуотражающий слой половину потока отразит и частично рассеет.

3. Двухсторонний, одноуровневый (9.4 Гбайт)

4. Двухсторонний, двухуровневый (17 Гбайт)

10.2 Форматирование дисков (программная часть)

10.2.1 Низкоуровневое форматирование

Низкоуровневое форматирование - разбивка диска на сектора, производится производителями дисков.

Каждый сектор состоит из:

- Заголовка (Prefix portion) - по которому определяется начало (последовательность определенных битов) сектора и его номер, и номер цилиндра.

- Область данных (как правило, 512 байт)

- Конец сектора (Suffix portion) - содержит контрольную сумму ECC (Error Correction Code - код корректировки ошибок). Позволяет обнаружить или даже исправить ошибки чтения. Размер зависит от производителя, и показывает, как производитель относится к надежности работы диска.

Сектор диска

На диске могут быть запасные сектора, которые могут быть использованы для замены секторов с дефектами (а они почти всегда есть). За счет этого обеспечивается одинаковая емкость на выходе.

При низкоуровневом форматировании часть полезного объема уменьшается, примерно до 80%.

Перекос цилиндров

Перекос цилиндров - сдвиг 0-го сектора каждой последующей дорожки, относительно предыдущей. служит для увеличения скорости. Головка тратит, какое то время на смену дорожки, и если 0-й сектор будет начинаться в том же месте, что и предыдущий, то головка уже проскочит его, и будет ждать целый круг.

Перекос цилиндров

Перекос цилиндров делают разным в зависимости скоростей вращения и перемещения головок.

Перекос головок - приходится применять, т.к. на переключение с головки на головку тратится время..

Чередование секторов

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

Чтобы этого не случилось, применяют чередование секторов.

Чередование секторов

Если копирование очень медленное, может применяться двукратное чередование, или больше.

10.2.2 Разделы диска

После низкоуровневого форматирования диск разбивается на разделы, эти разделы воспринимаются ОС как отдельные диски.

Для чего можно использовать разделы:

- Отделить системные файлы от пользовательских (например, своп-файлы)

- Более эффективно использовать пространство (например, для администрирования).

- На разные разделы можно установить разные ОС.

Основные разделы диска:

- Первичный (Primary partition) - некоторые ОС могут загружаться только с первичного раздела.

- Расширенный (Extended partition) - непосредственно данные не содержит, служит для создания логических дисков (создается, что бы обойти ограничение в 4-ре раздела).

- Логический (Logical partition) - может быть любое количество.

Информация о разделах записывается в 0-м секторе 0-го цилиндра, головка 0. И называется таблицей разделов.

Таблица разделов (Partition Table) - содержит информацию о разделах, номер начальных секторов и размеры разделов. На Pentium-компьютерах в таблице есть место только для четырех записей, т.е. может быть только 4 раздела (к логическим это не относится, их может быть не ограниченное количество).

Этот сектор называется главной загрузочной записью.

Главная загрузочная запись MBR (Master Boot Record) - содержит загрузочную программу и таблицу разделов.

Активный раздел - раздел, с которого загружается ОС, может быть и логическим. В одном сеансе загрузки может быть только один активный раздел.

Пример структуры разделов

В Windows разделы будут называться устройствами C:, D:, E: и т.д.

10.2.3 Высокоуровневое форматирование

Высокоуровневое форматирование (создание файловой системы) - проводится для каждого раздела в отдельности, и выполняет следующее:

- Создает загрузочный сектор (Boot Sector)

- Создает список свободных блоков (для UNIX) или таблицу (ы) размещения файлов (FAT - File Allocation Table) (для FAT или NTFS)

- Создает корневой каталог

- Создает, пустую файловую систему

- Указывает, какая файловая система

- Помечает дефектные кластеры

Кластеры и блоки - единица хранения информации в файловых системах, файлы записываются на диск, разбитыми на блоки ли кластеры.

При загрузке системы, происходит следующее:

1. Запускается BIOS

2. BIOS считывает главную загрузочную запись, и передает ей управление

3. Загрузочная программа определяет, какой раздел активный

4. Из этого раздела считывается и запускается загрузочный сектор

5. Программа загрузочного сектора находит в корневом каталоге определенный файл (загрузочный файл)

6. Этот файл загружается в память и запускается (ОС начинает загрузку)

10.3 Алгоритмы планирования перемещения головок

Факторы, влияющие на время считывания или записи на диск:

- Время поиска (время перемещения головки на нужный цилиндр)

- Время переключения головок

- Задержка вращения (время, требуемое для поворота нужного сектора под головку)

- Время передачи данных

Для большинства дисков самое большое, это время поиска. Поэтому, оптимизируя время поиска можно существенно повысить быстродействие.

Алгоритмы могут быть реализованы в контроллере, в драйверах, в самой ОС.

10.3.1 Алгоритм "первый пришел - первым обслужен" FCFS (First Come, First Served)

Рассмотрим пример. Пусть у нас на диске из 28 цилиндров (от 0 до 27) есть следующая очередь запросов:

27, 2, 26, 3, 19, 0

и головки в начальный момент находятся на 1 цилиндре. Тогда положение головок будет меняться следующим образом:

Алгоритм FCFS

Как видно алгоритм не очень эффективный, но простой в реализации.

10.3.2 Алгоритм короткое время поиска первым (или ближайший цилиндр первым) SSF (Shortest Seek First)

Для предыдущего примера алгоритм даст следующую последовательность положений головок:

Алгоритм SSF

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

10.3.3 Алгоритмы сканирования (SCAN, C-SCAN, LOOK, C-LOOK)

SCAN – головки постоянно перемещаются от одного края диска до его другого края, по ходу дела обслуживая все встречающиеся запросы. Просто, но не всегда эффективно.

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

C-SCAN - циклическое сканирование. Когда головка достигает одного из краев диска, она без чтения попутных запросов перемещается на 0-й цилиндр, откуда вновь начинает свое движение.

C-LOOK - по аналогии с предыдущим.

10.4 Обработка ошибок

Т.к. создать диск без дефектов сложно, а вовремя использования появляются новые дефекты.

Поэтому системе приходится контролировать и исправлять ошибки.

Ошибки могут быть обнаружены на трех уровнях:

- На уровне дефектного сектора ECC (используются запасные, делает сам производитель)

- Дефектные блоки или кластеры могут обрабатываться контроллером или самой ОС.

Блоки и кластеры не должны содержать дефектные сектора, поэтому система должна уметь помечать дефектные сектора.

Способы замены дефектных кластеров

10.5 Стабильное запоминающее устройство

RAID могут защитить от выхода из строя сектора и даже целые диски, но они не могут защитить от сбоев во время записи (могут быть записаны не верные данные, или не туда).

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

В рассматриваемой модели учитывается следующее:

- Запись блока может быть проверена при последующем чтении и изучении ECC.

- Правильно записанный сектор может стать дефектным и не читаться (но это происходит редко).

- Допускается выход из строя центрального процесса.

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

Для достижения этой цели определены три операции:

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

2. Стабильная операция чтения состоит из следующих шагов:
   - считывается блок с диска 1
   - проверяется на ошибки, если обнаружены считывание повторяется, и так несколько раз.
   - если все попытки с 1-м диском не удачны, все повторяется для второго

3. Восстановление от сбоев (например, по питанию) состоит из следующих шагов:
   - после сбоя программа восстановления сканирует оба диска и сравнивает соответствующие блоки
   - если у одного обнаружена ошибка, то на место дефектного записывается нормальный блок
   - если ошибок нет, но блоки не совпадают, то блок с диска 1 пишется поверх диска 2 (на диске 1 всегда более свежий блок)

10.6 Таймеры

10.6.1 Аппаратная часть таймеров

Таймер состоит из:

- Кварцевого генератора

- Счетчика

- Регистра хранения

Программируемый таймер

Есть несколько режимов работы таймера.

Алгоритм работы первого режима:

- Значение счетчика загружается из регистра.

- Когда значение счетчика достигает нуля, он вызывает прерывание процессора.

- Счетчик останавливается, до того пока его не запустят программно.

Алгоритм работы второго режима:

- Значение счетчика загружается из регистра.

- Когда значение счетчика достигает нуля, он вызывает прерывание процессора.

- Значение счетчика автоматически загружается из регистра и все повторяется.

Преимущество программируемого таймера в том, что частота прерываний может задаваться программно.

10.6.2 Программное обеспечение таймеров

Все, что делает таймер, аппаратно - он инициирует прерывание через определенные интервалы времени. Все остальное делается программно.

Для работы часов, необходим драйвер часов.

В обязанности драйвера входит:

- Следить за текущим временем

- Не позволять процессам работать больше, чем им положено (при запуске процесса планировщик записывает в счетчик выделенное процессу время)

- Вести учет использования процессора

- Поддерживать следящие таймеры для ОС (создаются виртуальные таймеры)

- Ведут наблюдение, анализ и сбор статистики

При 60 Грц 32-разрядный счетчик переполнится через два года.

Три способа реализации текущего времени:

1. Можно использовать 64-разрядный счетчик

2. Можно хранить время не в тиках, а в секундах, но нужен дополнительный счетчик, переводящий секунды в тики.

3. Можно учитывать время только с момента загрузки системы, а не с 1 января 1970 года

Три способа реализации текущего времени

| главная | лекции | лабораторные работы | литература | документация | выполнение работ | тесты | форум |

bogomolov@kfti.knc.ru