Файл: 14. Управление внешней памятью. Основные операции с файлами.pdf

берутся именно из него, а когда этот фрагмент списка закончится, в память 

загружается  следующий  блок  со  следующим  набором  номеров  свободных 

блоков.  Аналогично,  при  удалении  файла  занимаемые  им  блоки 

освобождаются  и  добавляются  в  находящийся  в  памяти  фрагмент  списка. 

Когда  этот  фрагмент  полностью  заполнится,  он  записывается  на  диск,  а  на 

его  место  загружается  следующий.  Эта  простейшая  схема  имеет  ряд 

усовершенствований [1]. 

Второй  способ  –  это  создание  и  поддержка  битового  массива  для  ВСЕХ 

блоков  диска.  Значение  бита  1  соответствует  занятому  состоянию  блока,  а 

значение  0  –  свободному  (можно  и  наоборот).  Для  10  млн.  блоков  надо  10 

млн.  битов,  т.е.  немного  больше  1  Мб.  Такой  массив  можно  постоянно 

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

блоки  и  хранить  на  диске.  Для  этого  может  потребоваться,  например,  256 

дисковых блоков.  

Преимуществом  данного  метода  является  его  простота.  При  удалении 

файла  и  освобождении  его  блоков  просто  обнуляются  соответствующие 

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

массиве ищет нулевые биты и инвертирует их значения.  

Номер блока 

1  2  3 

4 

5 

6 

7 

8 

9 

10 

. . . 

999999  1000000 

Состояние блока  1  1  1  0 

0 

0 

1 

0 

1 

0 

0 

0 

Основные  операции  с  файлами  –  это  создание  и  удаление,  открытие  и 

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

требуют  установления  соответствия  символьного  имени  файла  и  его 

физического  расположения  на  диске.  Поскольку  все  основные  современные 

ФС  поддерживают  иерархическую  организацию  файлов  в  виде  дерева 

каталогов,  необходимо  сначала  кратко  рассмотреть  возможные  структуры 

каталогов.  

Ранее уже было отмечено, что каталог – это просто специальный файл, в 

котором собирается информация о включенных в него файлах. Фактически, 

каталог – это набор записей, по одной для каждого файла. Структура записей 

различна для разных ФС. Например, записи каталога системы  FAT16/32 для 

каждого  файла  содержат  символьное  имя  файла,  атрибуты  файла  и  номер 

первого дискового блока, выделенного файлу. 

Наоборот,  в  Unix-системах  атрибуты  файла  хранятся  в  его  индексном 

узле,  а  запись  в  каталоге  содержит  лишь  2  поля  –  символьное  имя  файла 

(куда же пользователю без него!) и номер выделенного системой индексного 

узла. 

Теперь  более  понятным  становится  алгоритм  поиска  файла  по  его 

полному имени в дереве каталогов: 

прежде  всего  из  полного  имени  файла  выделяется  первая  компонента 

(разделитель – прямая или обратная косая черта); 

система  обращается  к  корневому  каталогу,  положение  которого  на 

диске всегда ей известно и который загружается в память при запуске 

системы; 

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

совпадает с выделенной компонентой полного имени; 

из  найденной  записи  напрямую  (для  FAT-систем)  или  косвенно  через 

индексный  узел  определяется  номер  дискового  блока  с  очередной 

порцией информации; 

в  память  считываются  данные  из  этого  блока,  из  полного  имени 

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

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

Для поиска в каталоге как массиве записей могут использоваться разные 

методы: 

простейший 

линейный 

просмотр, 

двоичный 

поиск 

в 

отсортированном  наборе,  хеш-поиск  и  даже  поиск  с  использованием  В-

деревьев. 

Следующая пара операций – это создание и уничтожение файлов. Запрос 

на  создание  файла  обычно  включает  полное  имя  создаваемого  файла  и  ряд 

его параметров. Отработка этого запроса включает в себя: 

поиск  каталога  для  хранения  имени  файла  и  просмотр  его  на  случай 

наличия заданного имени; 

включение новой записи в каталог и заполнение ее полей; 

поиск  для  создаваемого  файла  либо  первого  свободного  блока  (FAT-

системы),  либо  свободного  индексного  узла  с  занесением  этой 

информации в соответствующее поле записи каталога; 

если  размер  создаваемого  файла  известен  заранее,  то  выделяется 

необходимое  число  свободных  дисковых  блоков  и  связывание  их  в 

цепочку. 

Обратный запрос на уничтожение файла может включать в себя: 

поиск файла по его полному имени; 

определение в каталоге адреса первого блока файла или номера 

индексного узла; 

просмотр цепочки выделенных файлу блоков и освобождение их; 

удаление записи о файле из каталога. 

Важнейшая  пара  операций  –  открытие  и  закрытие  существующих 

файлов.  Открытие  обычно  производится  перед  выполнением  основных 

операций  чтения  или  записи  данных  и  состоит  в  выполнении 

подготовительных  операций,  упрощающих  и  ускоряющих  последующий 

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

поддерживает  одну  или  несколько  связанных  таблиц.  После  получения 

запроса на открытие файла выполняются следующие действия: 

поиск файла по его полному имени с определением текущего каталога; 

выполнение необходимых проверок на возможность открытия файла; 

формирование новой записи в системной таблице открытых файлов, 

важнейшим компонентом которой является индексный узел файла; 

создание новой записи в таблице дескрипторов файлов процесса; 

возврат  пользовательскому  процессу  созданного  дескриптора  для 

использования в последующих операциях 

Очевидно,  что  закрытие  файла  означает  лишь  уничтожение 

соответствующих записей в системных таблицах. 

Запрос  на  чтение  данных  из  открытого  файла  обычно  включает 

следующие  параметры:  дескриптор  файла,  адрес  буфера  ввода  для 

временного хранения прочитанных данных, количество считываемых байтов. 

По  дескриптору  файла  с  помощью  таблицы  открытых  файлов  легко 

определяется 

набор 

необходимых 

дисковых 

блоков. 

Аналогично 

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

выделенных  файлу  блоков  недостаточно,  система  должна  выделить 

дополнительные блоки.