Использование связанного списка адресов

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

						Область индексов

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

Этот способ используется в ФС FAT.

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

Недостатокочевиден: длина адреса зависит от размера файла и для большого файла может составить значительную величину.

Достоинство – высокая скорость доступа к произвольному кластеру, т.к. здесь используется прямая адресация, а не просмотр цепочек.

Фрагментация также отсутствует.

В качестве примера рассмотрим физическую организацию ФС FAT.

Логический раздел, отформатированный под ФС FAT, состоит из следующих областей (см. рис.):

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

· основная копия FAT. Содержит информацию о размещении файлов и каталогов на диске.

· резервная копия FAT

· область размером в 32 троки (16 Кбайт), что позволяет хранить 512 записей о файлах и каталогах, т.к. каждая запись каталога состоит из 32 байт.

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

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

Таблица FAT (основная и копия) состоит из массива индексных указателей, количество которых равно числу кластеров области данных. Между кластерами и индексными указателями имеется взаимно однозначное соответствие.

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

· кластер свободен;

· кластер используется файлом и не является последним кластером файла. В этом случае индексный указатель содержит номер следующего кластера файла;

· последний кластер файла;

· дефектный кластер;

· резервный кластер.

Таблица FAT – общая для всех файлов раздела.

В исходном состоянии, после форматирования, все кластеры свободны и все индексные указатели (кроме тех, которые соответствуют резервным и дефектным блокам) принимают значение «кластер свободен».

При размещении файла ОС просматривает FAT, начиная с начала, ищет первый свободный индексный указатель. После его обнаружения в поле записи каталога «номер первого кластера» фиксируется номер этого указателя. В кластер с этим номером записываются данные файла. Он становится первым кластером файла. Если файл умещается в одном кластера, то в указатель соответ

значение «последний кластер файла». Если размер файла больше .то ОС продолжает просмотр FAT и ищет следующий указатель на свободный кластер. После обнаружения в предыдущий указатель заносится номер этого кластера, и он становится следующим кластером файла.

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

Размер таблицы FAT и разрядность используемых в ней индексных указателей определяется количеством кластеров в области данных. Для уменьшения потерь из-за фрагментации желательно кластеры делать небольшими, а для сокращения объема адресной информации и повышения скорости обмена наоборот.

При формировании диска под FAT обычно выбирают компромиссное решение, и размеры кластеров выбираются из диапазона от 1 до 128 секторов или от 512 байт до 64 Кбайт.

Существует несколько разновидностей FAT отличающихся разрядностью индексных указателей, которая используется в качестве условного обозначения FAT12, FAT16 и FAT32. 12 разрядные указатели поддерживают 4096 кластеров, 16 разрядные – 65535, 32 разрядные – более 4 млн.

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

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

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

FAT12 и FAT16 применялись в ОС MS-DOS, Windows 3.1, Windows NT/2000 и Windows 95/98. В связи с ростом объемов дисков они вытесняются FAT32.

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

Файловые операции

Файловая система предоставляет пользователям определенный набор операций по работе с файлами.

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

· по символьному имени файла найти его характеристики, которые хранятся в файловой системе;

· скопировать характеристики файла в оперативную память;

· на основании характеристик файла проверить права пользователя на выполнение запрошенной операции (чтение, запись, удаление и т.п.);

· очистить область памяти, отведенную под временное хранение характеристик файла.

ОС может выполнять последовательность действий над файлом двумя способами:

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

· все универсальные действия выполняются в начале и конце последовательности операций, а для каждой промежуточной операции выполняются только уникальные действия.

Большинство ФС поддерживают второй способ организации файловых операций как более экономичный и быстрый.

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

Открытие файла

Системный вызов open работает с двумя аргументами: символьным именем открываемого файла и режимом открытия файла. Режим открытия говорит системе, какие операции будут выполняться над файлом в последовательности операций до закрытия файла

системному вызову close. Например, только чтение, только запись или чтение и запись.