64 байта <

16 бит л

- Время доступа

- Время модификации

- Время изменения состояния

Режим

Число ссылок

Размер файла

- Зона О

- Зона 1

- Зона 2

- Зона 3

- Зона 4

- Зона 5

- Зона 6

- Косвенная зона

- Косвенная зона второго уровня

- Не используется

Тип файла и биты rwx Записи в директориях для этого файла Идентифицирует владельца файла Группа владельца

Количество байт в файле

Время измеряется в секундах с 1 января 1970 года

Номера семи первых зон

Используются для файлов, занимающих больше семи зон

Можно использовать для косвенных зон третьего уровня вложенности

Рис. 5.2в. Структура i-узла в MINIX

5.6.5. Кэш блоков

Для повышения производительности файловой системы в MINIX применяется кэширование блоков. Кэш реализован в виде массива буферов, каждый из которых состоит из заголовка, содержащего указатели, счетчики и флаги, и тела - области памяти для хранения одного блока. Все неиспользуемые буферы связаны друг с другом в двунаправленный список, отсортированный от недавно использованных (MRU) к последним использованным (LRU). Это изображено на рис. 5.27.

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

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

Хеш-таблица Фронт (LRU)

Тыл (MRU)

Рис. 5.27. Связный список кэша блоков

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

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

По окончании работы запросившей блок процедуры, чтобы освободить блок, она вызывает другую процедуру, put block. Обычно блок используется сразу после выделения и затем освобождается, но так как сушествует возможность того, что перед освобождением блока будут сделаны дополнительные запросы, функция put bbck сначала уменьшает на единицу счетчик использования и помещает блок обратно в LRU-список в том и только том случае, если счетчик достиг нуля. Если он имеет ненулевое значение, блок не освобождается.

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

1. Поместить блок в начало или в конец LRU-списка.

2. Записать блок на диск немедленно (если он был модифицирован).

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

Модифицированный блок не записывается до тех пор, пока не произойдет одно из двух следующих событий.

1. Блок достиг начала LRU-списка и изгоняется из памяти.

2. Выполнен системный вызов sync.

Вызов sync не перебирает элементы LRU-списка. Вместо этого он обрабатывает массив буферов и записывает модифицированные буферы на диск даже в том случае, если они еще используются.

Тем не менее есть одно исключение. Модифицированный суперблок записывается на диск немедленно. В старой версии MINIX суперблок модифицировался при монтировании системы, поэтому, чтобы уменьшить вероятность повреждения файловой системы по причине неожиданного сбоя, он сохранялся без промедления. Сейчас суперблок не модифицируется, и код, отвечающий за его срочную запись, является анахронизмом. В стандартной конфигурации никакие другие блоки не записываются сразу. Но это поведение можно изменить, варьируя значение параметра ROBUST в файле конфигурации системы, include/minix/config.h. С его помощью можно сделать так, чтобы файловая система помечала г-узлы, каталоги, блоки косвенной адресации и блоки битовых карт как записываемые незамедлительно. Это должно сделать файловую систему более устойчивой, но ценой устойчивости является потеря производительности. Не совсем ясно и то, насколько это эффективно. Сбой питания, произошедший, когда еще не все блоки записаны на диск, вызовет головную боль, будь то блоки с данными или г-узлами.

Заметьте, что флаг в заголовке, означающий, что блок был модифицирован, устанавливается процедурой в файловой системе, которая его запросила и использует. Процедуры get block и put block занимаются только манипуляциями с однонаправленными списками. Они не имеют представления о том, какой процедуре файловой системы какой блок нужен и зачем.

5.6.6. Каталоги и пути

Другой важной составляющей файловой системы является система управления каталогами и путями. Многие системные вызовы, такие как open, в качестве аргумента принимают имя файла. Но в действительности нужен номер г-узла этого файла, поэтому файловая система должна просмотреть дерево каталогов и найти нужный г-узел.

В MINIX каталог состоит из файла, содержащего 16-байтовые записи. Первые два байта из шестнадцати формируют 16-битный номер г-узла, а оставшиеся 14 образуют имя файла. Это соответствует традиционной структуре каталога.