Алгоритмы выполнения типовых файловых операций

Файловая система

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

Для обеспечения доступа к файлам файловая система MS-DOS организует и поддерживает на логическом диске определеннуюфайловую структуру.

Структура дискового пространства

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

 

Информационная структура

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

Дисковое пространство представляется пользователю, как множество логических дисков, для обозначения которых используются буквы латинского алфавита от А до Z. При этом именаА и В зарезервированы для гибких дисков.

С каждым из логических дисков связано дерево каталогов. Дерево каталогов ОБЯЗАТЕЛЬНО содержит один корневой каталог (root directory) и множество иерархически подчиненных каталогов. Корневой каталог ВСЕГДА существует на отформатированном диске! Размер корневого каталога для данного диска - величина фиксированная, поэтому максимальное количество "привязанных" к нему файлов и других (дочерних) каталогов (подкаталогов) - строго определенное. Корневой каталог не имеет имени. Можно считать, что имя корневого каталога совпадает с именем соответствующего логического диска.

Подчиненные каталоги - это (по существу) файлы определенной структуры, аналогичной структуре корневого каталога. Размер подчиненного каталога не фиксирован - он динамически изменяется при добавлении и удалении регистрируемых в нем объектов (файлов или дочерних подкаталогов). Размер подчиненного каталога ограничивается только размером логического диска.

 

Рис. 1

MS-DOS поддерживает иерархическую (древовидную) структуру каталогов (рис.1). В отличие от корневого каталога, остальные каталоги (подкаталоги) создаются с помощью специальныхвнутренних команд MS-DOS. Основная цель такой структуры каталогов - организация эффективного хранения большого количества файлов на диске. КАЖДЫЙ каталог (кроме корневого) имеет "родителя". Т.е. КАЖДЫЙ каталог (кроме корневого) имеет другой каталог, к которому данный каталог "привязан". MS-DOS рассматривает каждый каталог (кроме корневого), как файл. Термин "привязан" иногда заменяется термином "зарегистрирован". На рис.1 каталог 2.1 привязан к каталогу 1.1, т.е. является дочерним по отношению к каталогу 1.1, и родительским по отношению к каталогам 3.1 и 3.2.

Физическая структура

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

Диск (пакет дисков) - физическое устройство для чтения-записи информации с автономным приводом.

Рабочая поверхность диска (Side) - магнитная поверхность диска, на которой хранятся данные. Она связана с магнитной головкойчтения-записи (Head).

Магнитная дорожка (Track) - дорожка на рабочей поверхности. Каждая дорожка поделена на секторы.

Сектор (Sector) - это минимальная единица дискового пространства, к которой можно обратиться для записи или чтения информации. Обычно сектор составляет 512 байтов.

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

Рис. 2

На рис.2 показана физическая структура дискеты. Не следует путать термины "дорожка" и "цилиндр". Хотя на данном рисунке может показаться, что цилиндр и дорожка - это одно и то же. Дискета на 1,4 МБ - двусторонняя (т.е. имеет две рабочие поверхности), поэтому на одном цилиндре расположены две дорожки.

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

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

Логическая структура

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

Рабочая область, расположенная непосредственно после системной, разделена на последовательно пронумерованныекластеры и предназначена для хранения файлов и подкаталогов. Кластер используется в качестве минимальной единицы, выделяемой операционной системой одному файлу или подкаталогу. Например, кластер Windows (FAT32) имеет размер 32 КБ. И если даже файл имеет размер 1 КБ, то для него все равно будет выделено на диске 32 КБ. В Windows все это можно увидеть, щелкнув по файлу правой кнопкой и выбрав пункт "Свойства".

Каждый кластер имеет уникальный номер и содержит несколько расположенных подряд секторов (1 или 2 сектора в кластере для гибких дисков, 4 и более - для жестких). Между номером кластера и списком абсолютных номеров секторов, которые в него входят, существует взаимно-однозначное соответствие.

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

• Блок загрузки (Boot-Sector)
• Корневой каталог (Root Directory)
• Таблица распределения файлов (FAT - File Allocation Table)

Блок загрузки (Boot-Sector)

Блок загрузки всегда занимает нулевой сектор и содержит таблицу параметров формата диска и короткую программу загрузки DOS. Структура блока загрузки показана в таблице 1.

Таблица 1. Структура блока загрузки.

Смещение	Длина, байт	Содержимое
+00		Команда перехода на программу загрузки (JMP)
+03		Служебная информация программы форматирования
+0Bh		Размер сектора в байтах
+0Dh		Количество секторов в кластере
+0Eh		Количество секторов перед первой FAT (кол-во резервных секторов в начале диска)
+10h		Количество копий FAT (стандарт - две)
+11h		Максимальное число элементов корневого каталога
+13h		Общее число секторов на логическом диске
+15h		Дескриптор носителя - тип формата диска (то же, что и 1-й байт FAT)
+16h		Количество секторов в одной FAT
+18h		Количество секторов на дорожке
+1Ah		Количество головок чтения-записи (поверхностей)
+1Ch		Количество скрытых секторов
+1Eh		Размер форматированной порции корневого сектора
		Начало кода и данных загрузки

Корневой каталог (Root Directory)

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

Таблица 2. Структура корневого каталога (одной записи).

Смещение	Длина, байт	Содержимое
+00		Имя файла или каталога
+08		Расширение
+0Bh		Атрибуты файла
+0Ch	0Ah	Резерв
+16h		Время создания/модификации (в специальном формате)
+18h		Дата создания/модификации (в специальном формате)
+1Ah		Номер начального кластера
+1Ch		Размер файла в байтах
+20h		Размер элемента оглавления

Байт атрибутов файла. Шесть младших битов байта атрибутов используются как битовые флаги. Единичное значение каждого бита задает определенное свойство соответствующего объекта:

Таблица 3. Байт атрибутов файла

Бит	Значение	Свойство
		Только чтение (R/O - Read Only)
		Скрытый (Hid - Hidden)
		Системный (Sys - System)
		Метка тома (Vol - Volume)
		Элемент подкаталога (Dir - Directory)
		Архивная копия файла НЕ создавалась (Arc)

Информация, хранимая в атрибутах, используется операционной системой при выполнении файловых операций. Например, значение атрибута Dir позволяет отличать файл от подчиненного каталога, а по значению атрибута Arc отбираются файлы для резервного копирования. Атрибут R/O запрещает изменять и удалять файл, а атрибут Hid делает файл "невидимым" (команда DIR не выводит его имя в списке). Если в записи корневого каталога установлено единичное значение атрибута Vol, то поля "Имя" и "Расширение" этой записи (всего 11 байтов) будут трактоваться как метка тома, а остальные данные этой записи будут игнорироваться.

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

Время

Часы (0-23)

Минуты (0-59)

2-секундные единицы (0-30)

Дата

Год (0-119)+1980

Месяц (1-12)

День (0-31)

Подчиненные каталоги по своей структуре подобны корневому каталогу - то есть содержат множество 32-байтовых регистрационных записей. В отличие от корневого, каждый подчиненный каталог имеет две служебные записи:

1. Запись подкаталога в поле "Имя" содержит символ "." (точка), а в поле "номер начального кластера" ссылку "на самого себя".
2. Запись подкаталога с символами ".." (две точки) в поле "Имя" - это ссылка на родительский каталог (если родительским является корневой каталог, то в качестве номера кластера указывается "0").

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

Таблица распределения файлов (FAT)

Таблица распределения файлов (FAT) - это связанный список, который обеспечивает возможность фрагментарного расположения файлов на диске (т.е. расположения файлов по частям в разных местах диска). Этот список используется файловой системой для определения последовательности кластеров, выделенных файлу или подкаталогу, а также для поиска свободного пространства, необходимого для записи новых файлов и подкаталогов. Число элементов этого списка равно числу кластеров в рабочей области диска. Каждому кластеру соответствует один "одноименный" (т.е. имеющий такой же номер) элемент FAT.

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

Для гибких дисков используются 12-битовые элементы FAT, а для жестких - 16-ти и 32-битовые. Длина элемента FAT определяет разрядность хранимого в нем двоичного числа. Поэтому длина элемента FAT ограничивает максимальное количество кластеров, которые могут быть сформированы в рабочей области тома (для FAT-12: 2¹² = 4096; для FAT-16: 2¹⁶ = 65535; для FAT-32: 2³² = 4294967296).
Каждый из элементов FAT представляет один кластер и может содержать следующие коды:

 

(0)000h	Доступный (свободный) кластер
(0)002h до (F)FEFh	Номер следующего кластера
(F)FF0h до (F)FF7h	Зарезервированный кластер
(F)FF7h	Плохой кластер (BAD)
(F)FF8h до (F)FFFh	Конец цепочки (EOF)

Первый байт FAT имеет особый статус и содержит так называемый "дескриптор носителя" (FAT ID-байт), в котором закодирована информация о типе и формате диска. Следующие 5 байтов (FAT-12) или 7 байтов (FAT-16) содержат код 0FFh. (На стандартной дискете элементы FAT начинаются с 3-го байта). Далее следуют собственно элементы FAT.

Пример:

Пусть элемент некоторого каталога содержит регистрационную запись о файле, в которой содержится ссылка на начальный кластер (кластер № 18) из цепочки кластеров, выделенных этому файлу.

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

 

1A

1B

1C

1D

1E

1F

FF8

1A

1B

 

2A

2B

2C

2D

2E

2F

FF7

2A

2B

FF8

Рис. 3

Из приведенного на рис.3 фрагмента FAT следует:

• Файл занимает цепочку из десяти кластеров: 18h-19h-1Аh-1Bh-25h-26h-27h-29h-2Ah-2Bh. Каждый элемент указывает на следующий элемент цепочки - значение элемента № 18h равно 19h, значение элемента 19h равно 1Аh и т.д. Последний элемент содержит специальный код EOF (FF8h) - конец файла.
• Еще одна цепочка начинается с кластера № 12h и кончается кластером № 15h. Чтобы узнать, какому файлу (или подкаталогу) распределены эти кластеры, нужно отыскать в каком-либо каталоге тома регистрационную запись, содержащую ссылку на начальный кластер № 12h.
• Кластер № 28h помечен, как BAD (FF7) и не входит ни в одну из цепочек. При поиске свободных кластеров для записи нового файла этот кластер будет игнорироваться.
• Кластеры № 10h, 11h, 16h, 17h, 1Ch…24h и 2Ch…2Fh пусты (точнее - объявлены таковыми). Они доступны для распределения под вновь записываемые файлы.
• Каждая цепочка кластеров, выделенных системой для одного файла (подкаталога), упорядочена в порядке возрастания их номеров.

Особенности структуры жесткого диска

Жесткий диск может быть разделен на несколько логических дисков (разделов, томов). Каждый из них рассматривается как автономный диск. Каждый логический диск имеет собственную системную и рабочую области. Любой логический диск может выступать в качестве загрузочного (системного) диска.

Для обеспечения процесса начальной загрузки операционной системы, а также для хранения данных о физическом расположении логических дисков, в первом секторе жесткого диска (0-й цилиндр, 0-я сторона, 1-й сектор) создается специальная информационная структура - главная загрузочная запись (Master Boot Record, сокращенно MBR). MBR содержит код программы начальной загрузки и таблицу разделов диска (Partition Table).

Каждый раздел в таблице представлен одним 16-байтовым элементом, содержимое которого формируется программой форматирования жесткого диска (например, FDISK). Для просмотра разделов можно использовать утилиту DiskEdit. Хотя работать с ней нужно очень осторожно. Здесь как у сапера - ошибаться нельзя - можно потерять всю информацию.

Таблица 4. Структура таблицы разделов диска.

Смещение	Длина, байт	Содержимое
1-й элемент (для первого раздела диска)
+00		Флаг загрузки: 0 - не загружаемый 80h - загружаемый (BootAble)
+01		Начало раздела: Hds (№ головки)
+02		Начало раздела: Sec (№ сектора - 6 младших битов) Cyl (№ цилиндра - 10 старших битов)
+04		Код системы: 0 - неизвестна 1 - DOS (FAT-12) 4 - DOS (FAT-16)
+05		Конец раздела: HdE (№ головки)
+06		Конец раздела: Sec (№ сектора - 6 младших битов) Cyl (№ цилиндра - 10 старших битов)
+08		Абсолютный номер начального сектора раздела (соответствует номерам сектора, головки и цилиндра начала раздела): Cyl*сект./дор.*дор./цил.+Hds*сект./дор.+(Sec-1)
+0Ch		Число секторов раздела
2-й элемент (для второго раздела диска)
+10h		Флаг загрузки
...	...	...
...	...	...
Последний элемент (после описания последнего раздела диска)
		0AA55h

Процесс загрузки системы с жесткого диска начинается со считывания MBR в ОЗУ и передачи управления на код находящейся в MBR программы. Эта программа читает таблицу разделов диска и определяет первый из разделов, помеченный как BootAble. Затем в память считывается boot-сектор этого раздела и ему передается управление. Далее работает программа начальной загрузки, находящаяся в boot-секторе раздела, которая загружает все необходимые системные файлы.

Алгоритмы выполнения типовых файловых операций

Чтение файла

Чтение файла с диска (например, при выполнении команды TYPE D:\TEXT\name.txt) реализуется следующей процедурой:

• В корневом каталоге логического диска D находится регистрационная запись, у которой:
• поле "Имя" = ТЕХТ
• поле "Расширение" = пусто
• атрибут Dir = 1

В этой записи читается значение поля "Номер начального кластера" (N)

• Читается первая копия FAT логического диска D и определяется цепочка номеров кластеров (которая начинается с N и оканчивается EOF), выделенных каталогу ТЕХТ.
• Читается каталог ТЕХТ:
• последовательно считываются все кластеры этой цепочки, начиная с N-го
• находится регистрационная запись, у которой:
• поле "Имя" = name
• поле "Расширение" = txt
• атрибут Dir = 0

В этой записи читается значение поля "Номер начального кластера" (N1).

• Читается первая копия FAT диска D и определяется цепочка номеров кластеров (которая начинается с N1 и оканчивается EOF), выделенных файлу name.
• Читается файл name: последовательно считываются все кластеры этой "цепочки", начиная с N1-го.

 

Запись файла

При записи на диск нового файла выполняется следующая процедура (приводится с упрощениями):

• По результатам анализа FAT определяется первый свободный ее элемент, номер которого записывается в очередную запись соответствующего каталога в качестве номера начального кластера.
• По данным таблицы формата диска, расположенной в его boot-секторе, и известному размеру файла в байтах вычисляется количество кластеров, необходимых для размещения файла.
• Начиная с начального элемента FAT, определяется цепочка свободных элементов (содержащих "0"), расположенных в порядке возрастания их номеров. При этом в каждый элемент записывается номер следующего элемента цепочки, а в последний элемент записывается код (F)FF9h (EOF).
• Файл последовательно записывается в кластеры рабочей области диска, номера которых соответствуют номерам элементов FAT, включенных в цепочку.

Например (см. рис.3), при записи файла размером 1234 байта на дискету стандартного формата (512 байтов в секторе, 1 сектор в кластере), этому файлу будет выделено три кластера с номерами 10, 11 и 16. При этом последний (16-й) кластер будет занят лишь частично.

Удаление файла

При удалении файла стандартными средствами (командой DEL):

• Рабочая область диска не модифицируется, то есть файл физически сохраняется в кластерах, выделенных ему при записи.
• Сохраняется также и регистрационная запись об этом файле в соответствующем каталоге, в том числе длина файла и ссылка на номер его начального кластера.
• Первый символ имени удаляемого файла в его регистрационной записи заменяется на код E5h (этот код соответствует строчной русской букве "х", недопустимой с точки зрения соглашения об именах MS DOS) - наличие такого символа в начале имени файла является признаком того, что файл логически удален.
• Обнуляется вся цепочка элементов FAT удаляемого файла, что делает соответствующие кластеры доступными для последующей записи.

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