Морис Бах - Архитектура операционной системы UNIX

На Рисунке 4.20 показана последовательность операций alloc и free для случая, когда в исходный момент список свободных блоков содержал один элемент. Ядро освобождает блок 949 и включает номер блока в список. Затем оно выделяет этот блок и удаляет его номер из списка. Наконец, оно выделяет блок 109 и удаляет его номер из списка. Поскольку список свободных блоков в суперблоке теперь пуст, ядро снова наполняет список, копируя в него содержимое блока 109, являющегося следующей связью в списке с указателями. На Рисунке 4.20(г) показан заполненный список в суперблоке и следующий связной блок с номером 211.

алгоритм alloc /* выделение блока файловой системы */

входная информация: номер файловой системы

выходная информация: буфер для нового блока

{

do (пока суперблок заблокирован)

sleep (до того момента, когда с суперблока будет снята блокировка);

удалить блок из списка свободных блоков в суперблоке;

if (из списка удален последний блок) {

заблокировать суперблок;

прочитать блок, только что взятый из списка свободных (алгоритм bread);

скопировать номера блоков, хранящиеся в данном блоке, в суперблок;

освободить блочный буфер (алгоритм brelse);

снять блокировку с суперблока;

возобновить выполнение процессов (после снятия блокировки с суперблока);

}

получить буфер для блока, удаленного из списка (алгоритм getblk);

обнулить содержимое буфера;

уменьшить общее число свободных блоков;

пометить суперблок как «измененный»;

return буфер;

}

Рисунок 4.19. Алгоритм выделения дискового блока

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

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

Сама конструкция дисковых блоков наводит на мысль об использовании списков с указателями: в дисковом блоке легко разместить большие списки номеров свободных блоков. Но индексы не имеют подходящего места для массового хранения списков номеров свободных индексов.

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

Рисунок 4.20. Запрашивание и освобождение дисковых блоков

В системе UNIX поддерживаются и два других типа файлов: каналы и специальные файлы. Канал, иногда называемый fifo (сокращенно от «first-in-first-out» — «первым пришел — первым вышел» — поскольку обслуживает запросы в порядке поступления), отличается от обычного файла тем, что содержит временные данные: информация, однажды считанная из канала, не может быть прочитана вновь. Кроме того, информация читается в том порядке, в котором она была записана в канале, и система не допускает никаких отклонений от данного порядка. Способ хранения ядром информации в канале не отличается от способа ее хранения в обычном файле, за исключением того, что здесь используются только блоки прямой, а не косвенной, адресации. Конкретное представление о каналах можно будет получить в следующей главе.

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