Реализация директорий.

Распределение дискового пространства.

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

Для ОС Unix служебная область содержит:

1) суперблок – сохранение информации о ФС в целом – н-р, имя ФС.

- указывается размер логического блока

- размер файловой системы в целом

- размер таблицы индексных узлов

и т.д. Этот блок ограничен – число файлов на диске так же ограниченно.

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

- список свободных индексов и список свободных счетчиков

2) таблица индексов (размер фиксирован)

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

(директория – это файл, имеющий определенный системный формат)

Директория хранит ссылки на файлы.

В MS-DOS директория организуется следующим образом: таблица размещении файлов должна быть целиком помещена в ОС.ОС организуется так, чтобы она могла получить доступ к любому файлу. Логически директория – таблица с записями.

Запись

FAT 2^16 – максимальная нумерация файлов

FAT 12 – адрес до 2х Мб.

FAT16

FAT32 – длина адреса – 28 бит

Рассчитана на работу с директориями. Для выделения большего места под имя необходимо как-то увеличить размер соответствующего поля.

Директории в Windows: система длинных имен и поддержка FAT32в структуру директории включается указатель на длинное имя. Оставляется так же запись для совместимости с MS-DOS, образующаяся по внутренним правилам.

1 Мб – совместимость с Windows NT.

1 Мб – контрольная сумма для длинных имен

в 10 байт записывается:

4б - дата создания

2б – дата последнего доступа

2б – старшие биты № начального блока

используется 10-разрядная адресация

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

поля атрибутов – указывают на заведомо неправильную комбинацию символов в дополнительных записях, которые предшествовали описанию положения файла и нумеровались.

MS-DOS не знает о дополнительных записях в директориях, Для обеспечения совместимости MS-DOS и Windows каждому файлу присваивается два имени – длинное и короткое. Проблема: MS-DOS – не должна размещать на не удаленные длинные имена новые файлы – чтобы такого не произошло используются контрольные суммы.

Директории Unix: имеют простую структуру, вся дополнительная информация – в индексах.

Сохраняются сведения о длине длинных имен.

Лекция 11.

Надежность файловой системы:

Выделяют два вида сбоев:

Жесткие сбои – связанные с радикальной поломкой оборудования.

Мягкие сбои – возникают при внезапном отключении питания.

Жесткие сбои.

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

Мягкие сбои.

Нарушение данных ФС, носитель с данными остается неповрежденным, но данные могут быть потеряны. Для обнаружения сбоев существует понятие – целостность файловой системы – подразумевает непротиворечивость хранящихся в ней данных. Атомарность – неделимость. В ФС существуют атомарные операции, прерывание которых влечет нарушение целостности системы в результате потери данных в ОП. Целостность подразумевает целостность системных данных и данных пользователя. Однако, разработчики заботятся о целостности служебных данных.

Пр-р: блоки из файла удалены, но не добавлены в блок свободной памяти не включены – потерянные блоки.

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

Средства:

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

- позволяющие восстановить целостность ФС (при повреждении данных пользователем либо при некорректном выключении самой ОС)

-предотвращающие повреждения

1 группа – выбирается рациональный порядок действий

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

2 группа – scan disk или file system check

Непротиворечивость блоков с данными – fsck

создается таблица

Сканируются i-узлы. В этой таблице любой блок может встретиться ровно один раз в двух последних столбцах. Если в обоих столбцах напротив бока стоит ноль, то это потерянный блок, включается в список свободных, если в обоих по единице – исключается из списка свободных, если блок занят 2-мя файлами, то непонятно, какую информацию он в итоге содержит, он копируется в свободный блок, и по одной из ссылок записывается адрес этого нового блока.

Проверка целостности каталогов:

Корректируется таблица индексов и существующее число ссылок. Приводится в соответствие с количеством ссылок. Если файл не включен ни в один каталог, его место освобождается.

3 группа – сделать файловые операции неделимыми.

Любая операция – транзакция, и либо выполняется полностью, либо не выполняется вообще. Н-р, применяется занесение действий в журнал (журналируемые ОС) транзакций. При сбое происходит откат.

Все эти действия снижают эффективность данной системы.

Производительность ФС:

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

Рассмотрим методы модификации алгоритмов чтения – записи.

Кэширование блоков.

В ОП создается буферный КЭШ. Предусматриваются буферы различной емкости. Можно записывать индексные файлы. Сохраняется первый элемент связанных блоков и индекс блоков. Если происходит обращение к блоку, проверяется, есть ли блок в буфере, а затем ищется на диске. Проблема: накапливаются различия в информации- необходимо обеспечить доступ в две стороны и обмен. Вторая проблема – ограниченность памяти.

Кэширование со сквозной записью (MS-DOS) –данные моментально записываются в постоянную память.

Структура буферного КЭШа в ОС Unix:

Любой буфер состоит из двух частей:

- заголовочной

- области данных

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

Область данных совпадает по размерам с дисковым блоком, заголовок состоит из нескольких полей для определения:

- номер устройства

- номер блока=адрес блока (идентифицируется по номеру устройства)

- указатель текущего состояния – заблокирован (занят, т.к. с ним работают ОС или непосредственно процессор) или доступен – определяется по флагу

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

- путь к соответствующему блоку

- ФС поддерживает в рамках ОС буфера КЭШ структуры

- поддерживает ХЭШ - очередь

- указатели на следующий и предыдущий буферы

ХЭШ – очередь создается в виде таблицы. Эта таблица состоит из массива, каждый элемент которого может содержать несколько ключей, определение идет по индексу

Список свободных буферов:

Каждый буфер, который не занят вводом/выводом, должен находиться в списке свободных буферов. Ос обращается к этому списку и забирает первый немодифицированный блок. После освобождения блока, он возвращается в список буферов, если ошибок не было, блок включается в конец списка, иначе - в начало. В буферном ХЭШе хранятся как системные, так и пользовательские данные, но сохраняются по-разному. Для быстрого доступа к буферам организуется ХЭШ – таблица.

В любых данных выделяется поле – ключ. Поиск организуется по ключу. Данные представляются массивом, в котором порядковый номер данных совпадает с ключом: индекс=ключ. Возникает проблема: массив не может быть слишком большим, а диапазон значений требуемых ключей существенно больше индексов. Или наоборот, набор используемых ключей оказывается существенно меньше определяемого массивом диапазона. Т.о. массив индексов берется небольшой, а массив ключей отображается на реальное значение индексов. Значение ключа приводится к диапазону индексов целочисленным делением. Но в этом случае несколько ключей попадают на один элемент массива. В ХЭШ- табл. С элементом массива сопоставляется список элементов с разным значением ключа для одного индекса.

стараются, чтобы ХЭШ – очереди, в которых придется выполнять линейный поиск, были небольшие. ХЭШ – функция или функция хэширования должна как можно более случайно сопоставлять ключ и индекс.

В ХЭШ – функцию необходимо передать номер устройства и номер блока.

Этапы:

- вычисляется ХЭШ – функция

- вычисляется индекс

- осуществляется линейный поиск

список свободных буферов и ХЭШ – таблица накладываются друг на друга, список свободных блоков переписывается в ХЭШ – таблице, однако в ней не отображаются неоднозначно свободные блоки.

Хранение индексов:

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

Для хранения индексов организуется ХЭШ - таблица свободных блоков и таблица свободных индексов.

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

Организация работы ядра ОС с буферным КЭШем. Если ядро обращается за поиском блока, оно обрпfoftncz к ХЭШ – таблице. Если в данный момент блок свободен, не блокирован другой процедурой, то ядру немедленно предоставляется блок. Если же блок занят, то новый процесс приостанавливается (редактирование и перезапись). Если происходит обращение к блоку, которого нет в таблице блоков, то выделяется свободный буфер и в него считывается информация с диска. Если список свободных буферов пуст, процесс приостанавливается.

Лекция 12.