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

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

алгоритм alloc /* выделение блока файловой системы */ входная информация: номер файловой системы выходная информация: буфер для нового блока { выполнить (пока суперблок заблокирован) приостановиться (до того момента, когда с суперблока будет снята блокировка); удалить блок из списка свободных блоков в суперблоке; если (из списка удален последний блок) { заблокировать суперблок; прочитать блок, только что взятый из списка свобод- ных (алгоритм bread); скопировать номера блоков, хранящиеся в данном бло- ке, в суперблок; освободить блочный буфер (алгоритм brelse); снять блокировку с суперблока; возобновить выполнение процессов (после снятия бло- кировки с суперблока); } получить буфер для блока, удаленного из списка (алго- ритм getblk); обнулить содержимое буфера; уменьшить общее число свободных блоков; пометить суперблок как "измененный"; возвратить буфер; }

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

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

Содержание раздела