Способы выделения дискового пространства. Управление дисковым пространством. Размер логического блока
Ключевой вопрос реализации файлов системы – способ связывания файлов с блоками диска.
В ОС используют несколько способов выделения файлу дискового пространства, для каждого и которых сведения о локации блоков данных файла можно извлечь из записи в директории, соответствующей символьному имени файла.
Выделение непрерывной последовательностью блоков.
Простейший способ – хранить каждый файл как непрерывную последовательность блоков диска. При непрерывном расположении файл характеризуется адресом и длиной (в блоках). Файл, стартующий с блока b, занимает затем блоки b+1, b+2,… b+n-1.
<<+>>:
Легкая реализация, т.к. выяснение местонахождения файла сводится к вопросу , где находится первый блок;
Обеспечивает хорошую производительность, потому что целый файл может быть считан за одну дисковую операцию.
<<->>:Трудности в поиске места для нового файла.
Наличие существенной внешней фрагментации.
Не применим, пока не известен максимальный размер файла.
Индексные узлы.
<<+>>:
При фиксированном, относительно небольшом размере индексного узла, можно поддерживать работу с файлами, размер которых может меняться от нескольких байт до нескольких гигабайт. Используется в ОС Unix, файловыми системами HPFS, NTFS и др.
Управление дисковым пространством.
Одной из основных функций файловых систем является управление свободным и занятым пространством внешней памяти, включая учет используемого места на диске. Рассмотрим битовый вектор и связный список.
Битовый вектор. Список свободных блоков диска реализован в виде битового вектора. Каждый блок представлен одним битом, принимающим значение 0 или 1, в зависимости от того занят ли он или свободен. Например, 000111101111110000000111…
<<+>>:
Простота и эффективность при нахождении первого свободного блока или n последовательных блоков на диске. Многие компьютеры имеют специальные инструкции манипулирования битами, при помощи которых можно легко реализовать первый единичный бит в слове.
<<->>:
Эффективен только если битовый вектор помещается в памяти целиком, что возможно только для относительно небольших дисков. Используется в Apple Macintosh.
Связный список. Связывают в список все свободные блоки, поддерживая указатель на первый свободный блок в специальном месте диска, попутно кэшируя в памяти эту информацию.
<<->>:
Если необходим не первый свободный блок, то схема не будет эффективна, т.к. для трассирования списка нужно сделать достаточно много обращений к диску.
Размер логического блока (кластера).
Размер логического блока является одним из ключевых параметров, влияющих в целом на эффективность работы файловой системы. В некоторых системах (к примеру, Unix) он может быть задан при форматировании.
Небольшие размеры блока:
<<+>>: меньше внутренней фрагментации
<<->>: существенные задержки при чтении
Большие размеры блока:
<<+>>: более высокая скорость обмена с диском
<<->>: в среднем половина последнего блока каждого файла пропадает -> снижается доля полезного дискового пространства.
Большинство файлов имеет небольшой размер (в Unix около 85% файлов имеют размер менее 8 Кбайт и 48% - менее 1 Кб).
Обычный компромисс – выбор блока размером 512 байт, 1 Кбайт, 2 Кбайт, 4 Кбайт.