3. Файловая структура данных

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

Имя файла может состоять из двух частей: собственно имени (обязательно) и расширения (не обязательно). Имя файлу дает пользователь компьютера по своему усмотрению. Расширение файла, по сути, отражает содержимое файла, то есть применяется для идентификации типа файла. Задание типа файла осуществляет либо сам пользователь, либо программа, порождающая файл. Программы часто присваивают наборам данных одни и те же расширения имен файлов. Например, текстовый редактор MICROSOFT WORD присваивает своим текстовым файлам расширение .DOC, электронные таблицы MICROSOFT EXCEL - .XLS. Нежелательно применять расширение, используемое какой-либо программой, для других файлов. Например, не стоит применять расширение .DOC для файлов, создаваемых программой PAINT, если Вы работаете с WORD, поскольку WORD ошибочно включит их в список своих файлов. В MS DOS собственно имя файла может иметь от одного до восьми символов. В имени файлов допустимы буквы, цифры и следующие знаки: (~), (_), (-), (!), (@), (#), ($), (%), (^), (&), ({}), ('), (()). Запрещается использовать в имени файла пробелы, символы: * и ? символы запятой и точки (за исключением точки, отделяющей основное имя файла от его расширения), а также зарезервированные слова (имена устройств) в начале имени: CLOCK$, CON (ввод - клавиатура, вывод - дисплей), AUX (асинхронный), COM1-COM4 (последовательные порты), LPT1-LPT3 (параллельные порты), NUL и PRN.

MS DOS не различает прописные и строчные буквы и сохраняет имя файла независимо от того, как оно введено (строчными символами). Восьмисимвольное имя файла - это только часть его полного имени. Имя файла может иметь расширение длиной от одного до трех символов, которое отделяется символом точки (.), в ограничение которого входят только символы  *  и  ? (табл. 1).

Главной отличительной чертой WINDOWS 95-2000 является возможность задавать имена файлов длиной до 255 символов (включая расширения). Длинные имена файлов являются более информативными и легкими для понимания и запоминания.

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

В длинных именах файлов не допускается использование зарезервированных Операционной системой слов (COM, LPT, CON, PRN, NULL, AUX) и следующих символов: * ? | \ / " : ,. В длинных именах файлов различаются строчные и заглавные буквы (длинное имя файла <Это МОЙ файл>) не является тем же, что и имя <Это мой файл>); в длинном имени файла можно использовать любое число точек.

 

Таблица 1

Отличие имен файлов MS DOS и WINDOWS 95,98,2000

MSDOS	WINDOWS
Имя файла может иметь от одного до восьми символов, расширение – от одного до трех и может отсутствовать (формат 8.3)	Имя и расширение вместе могут содержать до 255 символов. При создании файла автоматически генерируется короткое имя в формате 8.3. Программы, которые не поддерживают длинные имена файлов, рассматривают это имя как настоящее имя файла. Короткое имя создается из первых шести знаков длинного, тильды (~) и цифры, причем символы, не разрешенные к использованию в коротких именах, игнорируются.
Не различаются заглавные и строчные буквы.	Различаются заглавные и строчные буквы (например, файл «thesis.doc» будет отличаться от файла «Thesis.doc»).
В имени файла допускается использовать только одну точку, отделяющую имя от расширения.	В длинном имени файла можно использовать любое число точек

 

Спецификация файлов по расширению:

1) Исполнимые файлы: *.COM, *.EXE, *.BAT (здесь * - подстановочный символ, который означает, что имя файла может быть любое). Файлы запускают программы на выполнение. Причем файл с расширением .BAT называется пакетным командным файлом (от английского слова batch - пачка). Это текстовый файл, который содержит группу команд Операционной системы или обращений к прикладным программам, которые выполняются последовательно или в более сложном порядке, в зависимости от некоторых условий и интерпретируются командным интерпретатором COMMAND.COM.

2) Системные файлы (также драйверы устройств): *.SYS, *.BIN.

3) Текстовые файлы (любые файлы в кодировке ASCII): *.TXT, *.DOC, *.BAS, *.PAS, *.C, *.FOR, *.ASM.

4) Резервные копии со времени последнего изменения: *.BAK.

5) Промежуточные файлы работы трансляторов, компиляторов, интерпретаторов: *.BIR, *.OBJ.

6) Файлы электронных таблиц: *.XLS.

7) Графические файлы: *.BMP, *.PCX, *.TIF, .*.JPG, *.WMF, *.GIF и др..

8) Файлы-видео: *.MPG, *.AVI.

9) Файлы-аудио: *.WAV, *.MID.

10) Web-страницы Internet: *.HTM (L), *.ASP.

11) Архивные файлы: *.RAR, *.ZIP, *.LZH, *.HA, *.ARJ.

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

Существуют различные кодировки символов: двоичные, десятичные, шестнадцатеричные (в шестнадцатеричной кодировке используются 10 арабских цифр (0-9) и первые 6 букв латинского алфавита: A,B,C,D,E,F).

Набор символов, которые можно представить в компьютере, называется кодовой страницей (Америка-437, Россия-866, 855). Причем каждый символ кодовой таблицы можно представить в различных кодировках.

Например:

 

Двоичные файлы - файлы компилированных программ и прочесть их с помощью какого-либо текстового редактора не удается (если открыть их в, предположим, в программе MS WORD, то на экране монитора высветится «абракадабра»).

3.1. Маски файлов

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

Подстановочный  символ  "вопросительный знак" (?)

Символ "?" соответствует любому единичному символу и отсутствию символа, если он находится в конце имени файла или расширения. Например, маска TR?CK соответствует именам TRACK, TRICK, TRUCK и т.п.. Следует отметить, что эта маска не соответствует именам файлов с расширениями, поскольку в TR?CK расширение отсутствует. Маска GRAD?.TXT соответствует файлам GRAD.TXT, GRADY.TXT, GRADE.TXT и т. п.. В маске имени файла допускается указывать несколько вопросительных знаков. Например, маска ?ART??.?? соответствует любому имени файла до 6 символов, содержащему ART во второй, третьей и четвертой символьной позициях, еще до трех символов в самом имени файла и еще до двух символов в расширении. Соответствующими именами будут PART, CARTER.JE, MART.T, но не ARTS.23.

Подстановочный  символ  "звездочка" (*)

Подстановочный символ "*" соответствует любому количеству любых символов, включая отсутствие символа в конце имени файла или расширения. В маске имени файла можно использовать до двух символов “*” - один в собственно имени файла и второй - в расширении (*.*).Операционная система игнорирует все символы после звездочки в любой части имени файла. Например, маска TR* соответствует именам TR, TRY, TREK, TRIPTALK, но не TRUST.ME, так как расширение не указано. Маска CHAP01.* соответствует любому файлу, имеющему имя CHAP01 и любое расширение (или вообще без расширения).

3.2. Атрибуты файлов

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

READ ONLY (R),

ARCHIVE (A),

HIDDEN (H),

SYSTEM (S),

DIRECTORY (D).

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

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

Атрибут "Hidden" ("спрятанный") означает, что программа должна пропускать файл с этим атрибутом при выборе файлов для обработки. Например, команда DIR обычно не показывает "спрятанный" файл (но это можно отменить). "Спрятанный" файл не высвечивается в панелях NORTON COMMANDER'a и в Проводнике WINDOWS (при соответствующей конфигурации данный файл высвечивается с заглавным первым символом и сеточкой между именем файла и расширением в панелях NORTON COMMANDER’a - в таком виде файл не защищен от удаления).

Атрибут "System" ("системный") по своему назначению схож с атрибутом "спрятанный". Этот атрибут имеют основные программные файлы Операционной системы: IO.SYS, MSDOS.SYS и DRVSPACE.BIN (драйвер для сжатия дисков).

Атрибут "Directory" ("директория") присваивается операционной системой любому некорневому каталогу (в действительности это просто файл, которому приписан данный атрибут).

3.3. Каталог

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

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

Каждый диск имеет, по крайней мере, один каталог. Он создается операционной системой при форматировании и его удалить или переименовать уже нельзя. Этот каталог называется корневым. Он имеет имя: A:\ или B:\ - для гибких дисков; C:\, D:\, E:\ и т.д. - для жесткого диска и его логических разделов (каждый логический раздел имеет один корневой каталог). Любой же другой каталог может иметь определяемое пользователем имя и расширение. Требования, предъявляемые к именам каталогов те же, что и к именам файлов. Основное отличие: каталог на экране дисплея представлен заглавными буквами в MS DOS и значком папки в WINDOWS. В действительности с точки зрения операционной системы любой некорневой каталог является просто файлом, которому приписан специальный атрибут подкаталога D (DIRECTORY), кроме корневого. У Операционной системы CP/M вообще был только один (корневой) каталог.

В корневом каталоге регистрируются файлы и каталоги первого уровня, в каталогах первого уровня могут быть зарегистрированы каталоги второго уровня и другие файлы и т.д.. Таким образом, на дисках создается иерархическая файловая структура, корню которой соответствует корневой каталог. Если каталог WORK зарегистрирован в каталоге LEXICON, то говорят, что WORK - подкаталог LEXICON'а, LEXICON - надкаталог или родительский каталог для WORK.

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

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

C:\LEXICON\WORK\Letter.txt.

Данную запись еще называют полным именем файла.

Файлы объединяют в каталоги по разным признакам:

1) файлы, имеющие однотипную информацию (Папка "Мои документы": *.TXT, *.DOC).

2) файлы программ (GAME, LEXICON, WINDOWS).

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

 

3.4. Принцип записи файла на диск

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

Сектор – величина физическая. Самый распространенный размер сектора - 512 байт. Каждый сектор имеет адрес; для нахождения нужного сектора схемы накопителя (дисковода) считывают эти адреса. В каждом секторе наряду с адресом хранится контрольный код избыточного циклического контроля (CRC - Cyclic Redundancy Check), помогающий контролировать правильность данных в секторе. При записи данных в сектор контроллер накопителя вычисляет для данных значение кода CRC и сохраняет его с адресом сектора. Когда контроллер накопителя считывает сектор, он повторно вычисляет код CRC и сравнивает его с хранящимся в секторе. Если коды CRC не совпадают, контроллер фиксирует ошибку и отказывается использовать данные; при этом на экран монитора выводится сообщение об ошибке.

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

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

Распределение на диске кластерами имеет несколько несоответствий, которые запутывают многих пользователей. Например, при копировании небольшого файла (скажем 200 байт) с диска, имеющего кластеры в 1 Кбайт (1024 байт) на жесткий диск с кластерами по 4 Кбайта размер файла окажется тем же (т.е. 200 байт), но занимает он на жестком диске уже 4096 байта. Если попытаться скопировать группу из 20 небольших файлов (по 200 байт), суммарный размер которых 4 Кбайта, на жесткий диск, для них может не хватить места при наличии свободного пространства в 800 Кбайт.

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

Рассмотрим, каким образом Операционная система следит за распределением пространства на диске. Диск по функциональному признаку можно разделить на две области: системная область и область данных (рис. 4).

Системная область (для жестких дисков эта область занимает доли процента от общего объема диска, для дискет - 1-2%) разбита на четыре зоны:

1) MBR (Master Boot Record) - сектор, где хранится специальная программа загрузки и запись о разбиении диска на разделы (логические диски - partitions). Эта область отсутствует у дискет;

2) BR (Boot Record) - сектор начального загрузчика, здесь записываются данные о типе диска, а также программа начальной загрузки Операционной Системы;

3) FAT (File Allocation Table) - таблица размещения файлов; содержит последовательность номеров кластеров на диске (цепочку номеров), в которых записано содержимое файла, то есть здесь указывается физическое местонахождение файла, а также информация о свободных и дефектных кластерах на диске;

4) RDir (Root Directory) - корневой каталог диска, содержит записи имен файлов и подкаталогов первого уровня, сведения о размерах файла в байтах, дату и время создания или последнего редактирования файла, номер первого кластера и атрибуты файла;

5) Область хранения данных (Data) - содержит запись собственно содержимого файлов и подкаталогов диска, кроме корневого.

В табл. 2 приведен пример системной таблицы. Она содержит по одному элементу для каждого кластера на диске.

Ячейки в таблице имеют последовательные номера, начиная с 0, причем первые два кластера заняты системными записями. Каждый кластер в накопителе имеет свой номер, начинающийся с 2. Элемент каталога для файла содержит адрес первого кластера файла. В ячейке FAT, которая соответствует первому кластеру, содержится ссылка на второй кластер файла, в ячейке, соответствующей второму кластеру - ссылка на третий кластер файла и т.д. Такая цепочка продолжается, пока не будет достигнут последний кластер файла, элемент FAT которого содержит специальный код, означающий конец файла (EOF - End-Of-File, в шестнадцатеричном коде FFFF = 15*16³+15*16²+15*16¹+15*16⁰=65535).

 

 

 

 

 

 

 

 

Рис. 4 Логическая схема диска (кроме CD ROM)

Предположим, что элемент каталога для файла WORK.TXT показывает, что файл начинается в кластере 12. Этот элемент FAT содержит число 13, поэтому продолжение файла нужно искать в тринадцатом кластере. Согласно FAT, из тринадцатого кластера следует перейти в четырнадцатый, из четырнадцатого - в шестнадцатый. В элементе FAT для шестнадцатого кластера находится маркер конца файла. Таким образом, этот файл занимает четыре кластера, что должно согласовываться с размером файла, указанным в элементе каталога. Файл WORK.TXT является также примером фрагментированного файла. Вместо расположения в соседних кластерах файл разделен на два фрагмента. Чтобы использовать все дисковое пространство, Операционная система часто вынуждена фрагментировать файлы. Особенно высока вероятность фрагментации при расширении файла. Если, например, при расширении файла WORK.TXT потребовался дополнительный кластер, Операционная система не может выделить кластеры 17,18 так как они дефектны. Для файла приходится искать следующий свободный кластер, начиная с начала диска, отмеченный в FAT нулем (0); в данный момент это будет кластер 11. При этом образуется еще один фрагмент.

 

Таблица 2

Пример таблицы размещения файлов (первые 38 элементов)

 

Для небольших файлов требуется всего один кластер. Предположим, что файл READ.ME начинается в кластере 15. В приведенной табл.2 кластер 15 содержит маркер конца файла, следовательно, это единственный кластер файла.

Поскольку FAT играет очень важную роль в управлении файлами и распределении дискового пространства, Операционная система формирует две идентичные таблицы, одна из которых служит резервом (если первая таблица окажется поврежденной). Операционная система, тем не менее, ни при каких обстоятельствах не будет использовать копию. Она может оказаться полезной при восстановлении файлов вручную. При создании нового файла и изменении его размера Операционная система обновляет обе таблицы FAT. Если прервать работу Операционная система до окончания обновления таблиц, порядок в них нарушается, и правильный доступ к некоторым файлам становится невозможным. Чтобы избежать этого, нельзя производить перезагрузку или выключать питание при светящемся индикаторе накопителя. Светящийся индикатор показывает, что Операционная система обращается к накопителю. При записи файлов иногда возникают сбои (также при заражении вирусами), что приводит к созданию так называемых потерянных кластеров (Lost Cluster). Потерянные кластеры - это участки диска, не принадлежащие ни одному из файлов и не числящиеся в Таблице Размещения Файлов как свободные. В данной ситуации потребуется программа типа NDD или Scandisk, которая предложит либо сохранить эту информацию в виде отдельных файлов в корневом каталоге на диске, либо пометить эти участки как свободные в FAT.

Корневой каталог имеет для разных по характеристикам дисков разный, но фиксированный объем, определяемый величиной зоны Root Directory в системной области диска.

В табл. 3 представлена структура записей в корневом каталоге диска.

При удалении файла (при помещении его в "Корзину" Windows) Операционная система не стирает его данные с диска в области Data (поэтому при необходимости можно его восстановить). Для удаления файла в  первый символ его элемента каталога (в области System) помещается специальный код удаления, а в соответствующие файлу элементы FAT помещаются нули. В результате элемент каталога и элементы FAT становятся доступными для других файлов. При создании нового файла или расширении какого-либо другого файла используется элемент каталога удаленного файла и часть его кластеров (или все). Таким образом, затираются данные на диске удаленного файла. После чего восстановление данных на диске практически невозможно.

Таблица 3

Структура записей в корневом каталоге диска