ных блоков в суперблоке; | | если (из списка удален последний блок) | | { | | заблокировать суперблок; | | прочитать блок, только что взятый из списка свобод- | | ных (алгоритм bread); | | скопировать номера блоков, хранящиеся в данном бло- | | ке, в суперблок; | | освободить блочный буфер (алгоритм brelse); | | снять блокировку с суперблока; | | возобновить выполнение процессов (после снятия бло- | | кировки с суперблока); | | } | | получить буфер для блока, удаленного из списка (алго- | | ритм getblk); | | обнулить содержимое буфера; | | уменьшить общее число свободных блоков; | | пометить суперблок как "измененный"; | | возвратить буфер; | | } | +------------------------------------------------------------+ Рисунок 4.19. Алгоритм выделения дискового блока 81 4.20(г) показан заполненный список в суперблоке и следующий связной блок с номером 211. Алгоритмы назначения и освобождения индексов и дисковых блоков сходятся в том, что ядро использует суперблок в качестве кеша, хранящего указатели на свободные ресурсы - номера блоков и номера индексов. Оно поддерживает список номеров блоков с указателями, такой, что каждый номер свободного блока в файловой системе появляется в некотором элементе списка, но ядро не поддер- живает такого списка для свободных индексов. Тому есть три причины. 1. Ядро устанавливает, свободен ли индекс или нет, проверяя: если поле типа файла очищено, индекс свободен. Ядро не нуждается в другом механизме опи- сания свободных индексов. Тем не менее, оно не может определить, свободен ли блок или нет, только взглянув на него. Ядро не может уловить различия между маской, показывающей, что блок свободен, и информацией, случайно имеющей сходную маску. Следовательно, ядро нуждается во внешнем механизме идентификации свободных блоков, в качестве него в традиционных реализаци- ях системы используется список с указателями. 2. Сама конструкция дисковых блоков наводит на мысль об использовании спис- ков с указателями: в дисковом блоке легко разместить большие списки номе- ров свободных блоков. Но индексы не имеют подходящего места для массового хранения списков номеров свободных индексов. 3. Пользователи имеют склонность чаще расходовать дисковые блоки, нежели ин- дексы, поэтому кажущееся запаздывание в работе при просмотре диска в по- исках свободных индексов не является таким критическим, как если бы оно имело место при поисках свободных дисковых блоков. список в суперблоке +-----+-----+-----+-----+---------------------+ | 109 | 106 | 103 | 100 | ------------------- | +--+--+-----+-----+-----+---------------------+ +-----+ | 109 | +-----+-----+-----+-----+---------------+-----+ +->| 211 | 208 | 205 | 202 | ------------- | 112 | +-----+-----+-----+-----+---------------+-----+ (а) Первоначальная конфигурация список в суперблоке +-----+-----+---------------------------------+ | 109 | 949 | ------------------------------- | +--+--+-----+---------------------------------+ +-----+ | 109 | +-----+-----+-----+-----+---------------+-----+ +->| 211 | 208 | 205 | 202 | ------------- | 112 | +-----+-----+-----+-----+---------------+-----+ (б) После освобождения блока с номером 949 список в суперблоке +-----+-----+-----+-----+---------------------+ | 109 | 106 | 103 | 100 | ------------------- | +--+--+-----+-----+-----+---------------------+ +-----+ | 109 | +-----+-----+-----+-----+---------------+-----+ +->| 211 | 208 | 205 | 202 | ------------- | 112 | +-----+-----+-----+-----+---------------+-----+ (в) После назначения блока с номером 949 82 список в суперблоке +-----+-----+-----+-----+---------------+-----+ | 211 | 208 | 205 | 202 | ------------- | 112 | +--+--+-----+-----+-----+---------------+-----+ +-----+ | 211 | +-----+-----+-----+-----+---------------+-----+ +->| 344 | 341 | 338 | 335 | ------------- | 243 | +-----+-----+-----+-----+---------------+-----+ (г) Новое заполнение списка в суперблоке после назначения блока с номером 109 Рисунок 4.20. Запрашивание и освобождение дисковых блоков 4.8 ДРУГИЕ ТИПЫ ФАЙЛОВ В системе UNIX поддерживаются и два других типа файлов: каналы и специ- альные файлы. Канал, иногда называемый fifo (сокращенно от "first-in-first-out" - "первым пришел - первым вышел" - поскольку обслужива- ет запросы в порядке поступления), отличается от обычного файла тем, что со- держит временные данные: информация, однажды считанная из канала, не может быть прочитана вновь. Кроме того, информация читается в том порядке, в кото- ром она была записана в канале, и система не допускает никаких отклонений от данного порядка. Способ хранения ядром информации в канале не отличается от способа ее хранения в обычном файле, за исключением того, что здесь исполь- зуются только блоки прямой, а не косвенной, адресации. Конкретное представ- ление о каналах можно будет получить в следующей главе. Последним типом файлов в системе UNIX являются специальные файлы, к ко- торым относятся специальные файлы устройств ввода-вывода блоками и специаль- ные файлы устройств посимвольного ввода-вывода. Оба подтипа обозначают уст- ройства, и поэтому индексы таких файлов не связаны ни с какой информацией. Вместо этого индекс содержит два номера - старший и младший номера устройст- ва. Старший номер устройства указывает его тип, например, терминал или диск, а младший номер устройства - числовой код, идентифицирующий устройство в группе однородных устройств. Более подробно специальные файлы устройств рас- сматриваются в главе 10. 4.9 ВЫВОДЫ Индекс представляет собой структуру данных, в которой описываются атри- буты файла, в том числе расположение информации файла на диске. Существует две разновидности индекса: копия на диске, в которой хранится информация ин- декса, пока файл находится в работе, и копия в памяти, где хранится информа- ция об активных файлах. Алгоритмы ialloc и ifree управляют назначением файлу дискового индекса во время выполнения системных операций creat, mknod, pipe и unlink (см. следующую главу), а алгоритмы iget и iput управляют выделением индексов в памяти в момент обращения процесса к файлу. Алгоритм bmap опреде- ляет местонахождение дисковых блоков, принадлежащих файлу, используя предва- рительно заданное смещение в байтах от начала файла. Каталоги представляют собой файлы, которые устанавливают соответствие между компонентами имен фай- лов и номерами индексов. Алгоритм namei преобразует имена файлов, с которыми работают процессы, в идентификаторы индексов, с которыми работает ядро. На- конец, ядро управляет назначением файлу новых дисковых блоков, используя ал- горитмы alloc и free. 83 Структуры данных, рассмотренные в настоящей главе, состоят из связанных списков, хеш-очередей и линейных массивов, и поэтому алгоритмы, работающие с рассмотренными структурами данных, достаточно просты. Сложности появляются тогда, когда возникает конкуренция, вызываемая взаимодействием алгоритмов между собой, и некоторые из этих проблем синхронизации рассмотрены в тексте. Тем не менее, алгоритмы не настолько детально разработаны и могут служить иллюстрацией простоты конструкции системы. Вышеописанные структуры и алгоритмы работают внутри ядра и невидимы для пользователя. С точки зрения общей архитектуры системы (Рисунок 2.1), алго- ритмы, рассмотренные в данной главе, имеют отношение к нижней половине под- системы управления файлами. Следующая глава посвящена разбору обращений к операционной системе, обеспечивающих функционирование пользовательского ин- терфейса, и описанию верхней половины подсистемы управления файлами, из ко- торой вызывается выполнение рассмотренных здесь алгоритмов. 8. В версии V системы UNIX разрешается использовать не более 14 символов на каждую компоненту имени пути поиска. Алгоритм namei отсекает лишние сим- волы в компоненте. Что нужно сделать в файловой системе и в соответствую- щих алгоритмах, чтобы стали допустимыми имена компонент произвольной дли- ны ? 9. Предположим, что пользователь имеет закрытую версию системы UNIX, причем он внес в нее такие изменения, что имя компоненты теперь может состоять из 30 символов; закрытая версия системы обеспечивает тот же способ хране- ния записей каталогов, как и стандартная операционная система, за исклю- чением того, что записи каталогов имеют длину 32 байта вместо 16. Если пользователь смонтирует закрытую файловую систему в стандартной операци- онной среде, что произойдет во время работы алгоритма namei, когда про- цесс обратится к файлу ? *10. Рассмотрим работу алгоритма namei по преобразованию имени пути поиска в идентификатор индекса. В течение всего просмотра ядро проверяет соответс- твие текущего рабочего индекса индексу каталога. Может ли другой процесс удалить (unlink) каталог ? Каким образом ядро предупреждает такие дейст- вия ? В следующей главе мы вернемся к этой проблеме. *11. Разработайте структуру каталога, повышающую эффективность поиска имен файлов без использования линейного просмотра. Рассмотрите два способа: хеширование и n-арные деревья. *12. Разработайте алгоритм сокращения количества просмотров каталога в поис- ках имени файла, используя запоминание часто употребляемых имен. *13. В идеальном случае в файловой системе не должно быть свободных индексов с номерами, меньшими, чем номер "запомненного" индекса, используемый ал- горитмом ialloc. Как случается, что это утверждение бывает ложным ? 14. Суперблок является дисковым блоком и содержит кроме списка свободных блоков и другую информацию, как показано в данной главе. Поэтому список свободных блоков в суперблоке не может содержать больше номеров свободных блоков, чем может поместиться в одном дисковом блоке в связанном списке свободных дисковых блоков. Какое число номеров свободных блоков было бы оптимальным для хранения в одном блоке из связанного списка ? 84