Управление свободной внешней памятью

Для управления свободной памятью на диске система использует битовый вектор длины n, где n – общее число блоков на диске, каждый бит которого описывает состояние соответствующего блока: bit[i] = 0, если block[i] свободен, 1 – если блок занят. При таком представлении информации о свободных и занятых блоках, номер первого занятого блока вычисляется по простой формуле:

номер первого занятого блока = число битов в слове * число нулевых слов + номер первой 1.

Битовые шкалы, используемые для управления блоками, требуют дополнительной памяти. Например, при размере блока в 2¹² байтов и размере диска в 2³⁰ байтов (1 GB) длина битового вектора будет равна n = 2³⁰/2¹² = 2¹⁸ битов (или 32 KB).

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

Для предотвращения ситуаций рассогласованности информации о свободной дисковой памяти, операционной системе необходимо защищать указатель на список свободной памяти, либо битовую шкалу (в зависимости от способа представления информации о свободной памяти). Битовый вектор должен храниться на диске. Однако его копии в памяти и на диске могут различаться. Нельзя допустить, чтобы block[i] имел такую ситуацию, когда bit[i] = 1 в памяти и bit[i] = 0 на диске. Решение этой проблемы в том, чтоты согласовывать значения битов на диске и в памяти по следующему алгоритму:

• Установить bit[i] = 1 на диске;
• Разместить block[i];
• Установить bit[i] = 1 в памяти.

Представление информации о свободной дисковой памяти в виде списка блоков иллюстрируется на рис. 20.7.

Рис. 20.7. Список свободной дисковой памяти.

Дата добавления: 2013-12-13