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

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

Как только получен новый буфер, во все его поля, включая поле b dev, записываются новые значения, и можно считывать данные блока с диска. Есть только два случая, в которых считывать диск с блока необязательно. Функция get block может быть вызвана с параметром only search. Это может означать, что выполняется упреждающее выделение блока. Упреждающее выделение подразумевает, что содержимое обнаруженного буфера при необходимости перезаписывается на диск и ему назначается новый номер, но в поле b dev заносится значение NO DEV, как свидетельство того, что блок не содержит данных. Применение этого мы увидим, когда станем обсуждать функцию rw scattered. Кроме того, only search может использоваться тогда, когда блок нужен файловой системе для полной перезаписи его содержимого. Тогда считывание старых данных было бы пустым расточительством. И в этом и в том случае параметры блока обновляются, но реальное чтение не выполняется. Когда новый блок готов и при необходимости считан, get block возвращает указатель на него в вызывающую программу.

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

Функция put block отвечает за возврат блока в LRU-список, а также в некоторых случаях перезаписывает его содержимое на диск. Второй условный оператор в коде этой функции принимает решение о том, будет ли блок помещен в начало или в конец списка, в зависимости от флага block type. Блоки, для которых в ближайшем времени ожидаются новые обращения, записываются в конец списка, где они будут храниться еще некоторое время. Блоки, проявление интереса к которым маловероятно, заносятся в начало списка, в расчете на их передачу другим операциям. Например, в начало списка записываются суперблоки.

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

мало востребована. С другой стороны, можно так отредактировать макрос ROBUST в файле include/minix/config.h, чтобы немедленно записывались г-узлы, блоки каталогов, а также другие блоки, важные для функционирования самой файловой системы.

По мере роста файла необходимо время от времени выделять новые зоны для хранения его данных. За выделение зон отвечает процедура alloc zone. Она ищет свободную зону по битовой карте зон. Если это первая зона файла, то перебирать всю битовую карту не нужно, так как поле s zsearch в суперблоке всегда указывает на первую свободную зону на диске. В противном случае, чтобы зоны располагались вместе, ищется ближайшая к последней зоне файла свободная зона. Соответственно, поиск начинается с последней зоны файла. В последней строке процедуры номер бита в битовой карте преобразуется в номер зоны (таким образом, что бит 1 соответствует первой зоне данных).

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

При работе с кэшем требуется записывать и считывать блоки. Простой интерфейс для взаимодействия с диском обеспечивает функция rw block. Она записывает или считывает один блок. Аналогично, функция rwjnode записывает или считывает один г-узел.

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

Функцию flushall вызывает системный вызов sync, для того чтобы сбросить на диск все измененные буферы, принадлежащие какому-то одному монтированному устройству. Эта функция работает с кэшем буферов как с одномерным массивом, поэтому она может обнаруживать измененные буферы даже в том случае, если их нет в списке LRU. Весь массив буферов сканируется, и указатели на те из них, что принадлежат указанному устройству и содержат обновленные данные, добавляются в массив указателей dirty. Последний массив, чтобы не выделять его в стеке, объявлен как static. Затем массив передается rw scattered.

Функция rw scattered получает на входе идентификатор устройства, указатель на массив указателей на буферы, размер этого массива и флаг, указывающий, вьшолняется чтение или запись. Первым делом функция сортирует переданный ей массив указателей, чтобы передача данных происходила в наиболее эффективном порядке. С флагом WRHING ее может вызывать только описанная выше процедура flushall. В этом случае несложно понять происхождение номеров блоков, так как передаваемые буферы содержат данные, которые были ранее считаны, а теперь изменены. Для чтения rw scattered вызывается только из функции rahead в файле read.c. Сейчас мы не будем углубляться в детали ее работы, скажем лишь, что перед вызовом rw scattered несколько раз в режиме подготовки

вызывается get block, тем самым резервируется группа буферов. Буферам назначается номер блока, а номер устройства - нет, но это не проблема, поскольку номер устройства передается в качестве одного из аргументов в rw scattered.

Есть важное отличие между тем, как драйвер устройства реагирует на чтение и запись из rw scattered. Запрос на запись некоторого количества блоков обязательно должен быть выполнен полностью, в то время как запрос на чтение обрабатывается разными драйверами по-разному, в зависимости от того, что более эффективно для данного конкретного драйвера. Функция rahead зачастую вызывает rw scattered, передавая ей список буферов, которые в действительности могут быть не нужны. Поэтому лучше всего считать только те блоки, до которых легко добраться, не выискивая их по всему устройству и теряя драгоценное время. Например, драйвер гибкого диска может остановиться на границе дорожки, а другие драйверы будут читать только последовательные блоки. Выполнив чтение, rw scattered помечает прочитанные блоки, вписывая в содержащие их буферы номер устройства.

Последняя функция из табл. 5.5, rm lru, предназначена для того, чтобы удалять блок из LRU-списка. Она используется только внутри функции get block, поэтому вместо PUBLIC объявлена как PRIVATE, с целью скрыть ее от процедур в других файлах.

Прежде чем закончить изучение кэша блоков, скажем несколько слов о его тонкой настройке. Значение параметра NR BUF HASH должно быть степенью двойки. Если оно больше, чем NR BUFS, средняя длина хеш-цепочки будет меньше единицы. Но когда хватает памяти для большого количества буферов, ее хватит и для большого количества хеш-цепочек, поэтому значение этого параметра обычно выбирается равным ближайшей степени двойки, большей NR BUFS. В обсуждаемом в тексте исходном коде заведено 512 буферов и 1024 хеш-цепочки. Оптимальный размер зависит от характера эксплуатации системы, поскольку определяет, сколько информации будет кэшироваться. Опытным путем было установлено, что увеличение числа буферов выше 1024 не дает прироста производительности при перекомпиляции MINIX, видимо, потому, что этого достаточно, чтобы хранить промежуточные файлы для всех проходов компилятора. Для некоторых задач более адекватной будет меньшая емкость, а другим может потребоваться увеличить кэш ради подъема быстродействия.

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

Говоря о кэше блоков, следует заметить, что на 16-разрядных машинах Intel размер сегмента памяти офаничен 64 Кбайт, что делает невозможной реализа-