2.3. Способы организации файлов

Под организацией файлов имеется в виду способ расположения записей файла во внешней памяти. В настоящее время наиболее известны следующие способы организации файлов :

- последовательное размещение;

- размещение с помощью сцепленных блоков;

- организация на основе таблиц размещения;

- размещение с использованием таблицы индексов;

- индексно-последовательное размещение;

- библиотечная структура данных.

2.3.1. Последовательное размещение

При последовательном размещении каждый файл занимает во внешней памяти совокупность последовательных блоков. Такой способ является единственно возможным на магнитной ленте: файлы последовательно распределяются на ленте и каждый файл отделяется от последующего специальным символом, который называется конец­ файла. Двойной конец файла обозначает конец используемой части ленты. Дескриптор файла обычно располагается в начале и иногда повторяется в конце файла. Дескриптор файла содержит указатель на первый блок, а также число занятых блоков (рис.2.2). Символ конца файла автоматически распознается контроллером лентопротяжки. Операция «поиск конца файла» позволяет быстро переходить от одного начала файла к другому, например чтобы найти файл с данным именем.

Рис.2.2.

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

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

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

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

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

- рассматриваются очень простые системы для микрокомпьютеров или основным требованием является простота реализации.

2.3.2. Размещение с помощью сцепленных блоков

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

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

Рис. 2.3.

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

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

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