Другой аспект распределения дисковой памяти
Рисунок 7.4. Размещение файла в файловой системе s5
Другой аспект распределения дисковой памяти - учет свободного пространства на диске. Как и для учета размещения файлов, здесь применяются либо карта дискового пространства, либо списки свободных блоков. В случае, если размещение файлов отслеживается картой размещения, на этой же карте могут быть отображены и свободные блоки. Если же используются различные механизмы отслеживания размещения и учета свободного пространства, то карта свободной памяти может состоять из однобитовых элементов со значением 0 - свободен, 1 - занят. Поиск свободного участка заданного размера сводится к поиску в карте цепочки нулевых бит заданной длины. Если для системы имеет значение выделение дисковой памяти непрерывными участками, то состояние дискового пространства может отображаться в двух или более картах разного "масштаба". Наряду с обязательной картой свободных блоков, самой "мелкомасштабной", может существовать карта свободных дорожек и карта свободных цилиндров. Наличие "крупномасштабных" карт позволяет ускорить поиск больших непрерывных свободных участков.
Списки свободных блоков организуются точно так же, как и списки блоков, принадлежащих файлу. Дескриптор диска содержит указатель на начало списка свободных блоков. Последовательная природа списка не оказывает влияния на эффективность его обработки, так как список свободных блоков может обрабатываться по дисциплине LIFO - выборка блока происходит из начала списка, и новый свободный блок также добавляется в начало списка. Изящный пример работы со свободными блоками показывает та же ФС s5, пример относится к категории "ленивых политик", свойственных этой ОС Unix.
В дескрипторе диска s5 (суперблоке) содержится массив из 10 номеров свободных блоков. Поскольку суперблок в процессе работы хранится в оперативной памяти, первые 10 свободных блоков могут быть выбраны без обращений к внешней памяти. Если этот "запас" свободных блоков исчерпан, то используется последний элемент этого массива, который ссылается на свободный блок, содержащий еще 10 номеров свободных блоков. Эти новые номера заново заполняют массив в суперблоке и т.д. При необходимости включить в список новые свободные блоки их номера сохраняются в массиве суперблока, пока в нем есть свободные места. Если же свободные места исчерпаны, массив выводится в блок на внешней памяти, добавдяемый в список, а место в суперблоке освобождается.
