В каждом каталоге есть записи с именами . и которые добавляются при создании каталога. Записи . соответствует г-узел самого каталога, а ссылается на г-узел каталога верхнего уровня. Таким образом, если дано имя файла ../dick/prog.с, система найдет в текущем каталоге, получит г-узел родительского и будет искать в нем dick. Для обработки таких имен не применяется никаких специальных алгоритмов. С точки зрения системы каталогов, это обычные ASCII-строки, ничем не отличающиеся от прочих имен.

5.3.3. Организация дискового пространства

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

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

Размер блока

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

Если выбрать большую единицу хранения, такую как цилиндр, это будет означать, что любой файл, даже состоящий из одного байта, займет как минимум целый цилиндр. Опыт показал, что средний размер файла в системе UNIX около 1 Кбайт, поэтому при выделении каждому файлу 32-килобайтового блока будет расходоваться понапрасну 31/32 или 97 % общего дискового пространства [90].

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

Например, представьте себе диск с 131 072 байтами (128 Кбайт) на дорожку, периодом вращения 8,33 мс и средним временем поиска 10 мс. При этом время.

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

10 + 4,165 + {k/ШШ) X 8,33.

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

Поэтому обычно выбирается компромиссное рещение, и размер блока делается равным 512 байт, 1 Кбайт или 2 Кбайт. Если сектор диска имеет размер 512 байт, а блока - 1 Кбайт, то файловая система всегда будет считывать или записывать два последовательных сектора, рассматривая их как единый, неделимый элемент. Какое бы решение ни было принято, его необходимо периодически пересматривать, так как по мере развития технологий пользователи, получив больше ресурсов, начинают требовать еще больше. Один из системных администраторов сообщил нам, что средний размер файлов в университетской системе медленно возрастал год за годом и к 1997 году достиг 12 Кбайт для студентов и 15 Кбайт для факультета.

1-узел 6 содержит данные

Корневой каталог о каталоге /usr

Блок 132 содержит каталог 132

1-узел 26 содержит

о каталоге /usr/ast

Блок 40S содержит каталог /usr/ast

Размер Времена

Режимный код Размер Времена

В результате

поиска элемента usr получаем нуэел 6

Bi-узлеб указывается, что /usr находится в блоке 132

Запись/usr/ast ссылается на 1-узел 26

В i-узле 26 указывается, что /usr/ast находится в блоке 406

Запись /usr/ast/ml x ссылается на 1-узвл 60

Рис. 5.13. Зависимость скорости чтения/записи данных диска (жирная линия, левая шкала) и эффективности использования дискового пространства (штриховая линия, правая шкала) от размера блоков. Все файлы по 2 Кбайт

Учет свободных блоков

После того как мы выбрали размер блоков, следует определиться, как учитывать свободные и занятые блоки. Широкое распространение получили два метода, представленные на рис. 5.14. Первый метод - не что иное, как использование списка блоков диска. При этом в каждом блоке списка содержится столько номеров свободных блоков, сколько может поместиться в один блок. При размере блока, равном 1 Кбайт, и 32-разрядных номерах блоков каждый блок списка свободных блоков может содержать номера 255 свободных блоков. (Одно 32-разрядное слово

нужно для указателя на следующий блок списка.) Для 16-гигабайтового диска потребуется список свободных блоков, состоящий из 16 794 блоков, чтобы охватить все 2 дисковых блока. Часто для списка резервируется нужное число блоков в начале диска.

Блоки диска 16, 17, 18

1-килобайтный блок диска может содержать 256 32-разрядных номеров блока

Битовый массив

Рис. 5.14. a - хранение информации о свободных блоках в виде списка; б - битовый

массив

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

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