66. Методы выделения дискового пространства: выделение непрерывной последовательности блоков.

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

66. Методы выделения дискового пространства: связной список. В каждом блоке наряду с данными находятся указатель на следующий блок файла. Записи в директории указывается только номер первого блока этого файла. Для того, чтобы прочитать произвольный блок файла необходимо последовательно прочитать все блоки с первого и далее по указателям. Достоинства: отсутствие фрагментации, поскольку файл может размещаться в любых свободных блоках файловой системы. Недостатки: 1. В каждом блоке некоторые пространства отнимается для указателей. Таким образом, реальный размер блока данных меньше размера блока файловой системы, не является степенью двойки и усложняется его обработка. 2. Отсутствие прямого доступа к произвольному блоку файла, поскольку необходимо прочитать все блоки с первого. 3. В случае, если один из блоков файла не может быть прочитан, то теряется не только этот блок, но и вся цепочка файлов до конца, поскольку неизвестно в каком блоке продолжается эта цепочка.

66. Методы выделения дискового пространства: таблица отображения файлов. Модификация связного списка. Указатели находятся не в самих блоках, а в отдельной управляющей структуре таблицы отображения данных, которая находится в первых блоках дисков, а также продолжается в произвольных местах диска. Таблица отображения файлов представляет собой одномерный массив чисел. I-ый элемент массива содержит номер блока, в котором находится блок данных файла, следующий за i-ым. Если i-ый блок является последним блоком в файле, то i-ый элемент FAT содержит специальный символ, означающий конец файла. Запись о файле в директории содержит номер первого блока, по которому из FAT можно получить все остальные блоки. Достоинства: Размер блока данных не уменьшается из-за указателя и равен логическому блоку. Фрагментация отсутствует, поскольку блоки могут размещаться в любом свободном месте. Возможен прямой доступ к произвольному блоку файла, для этого необходимо прочитать файловую таблицу, пройти по цепочке элементов этой таблицы до нужного блока и прочитать этот блок. При невозможности чтения одного из блоков файла, теряется только этот блок, поскольку цепочка из остальных блоков описана не в нем, а в файловой таблице. Недостатки: при потере файловой таблицы теряются все файлы описанные в ней. Во избежание этого хранятся копии таблиц. Ограничение на максимальный размер файлов, поскольку файл может быть описан только в одной таблице отображения, а одна таблица отображения находящаяся в одном блоке описывает не более 4 гб.

66. Методы выделения дискового пространства: индексные узлы. Индексный узел представляет собой управляющую структуру, которая наряду с атрибутами файла содержит таблицу с номерами блоков файла. Запись о файле в директории содержит адрес индексного узла для данного файла. Индексный узел содержит таблицы с указателем на первые блоки файлов , благодаря чему для небольших файлов достаточно прочитать только индексный узел для получения доступа к произвольным блокам файла. Если файл большой, то индексный узел содержит кроме показателей на первые блоки указатели на блоки косвенной адресации. Если размер файла очень велик, то некоторые записи блоков косвенной адресации могут содержать указатели на блоки косвенной адресации второго уровня и т.д. Достоинства: гибкость структуры, наличие произвольного доступа к файлам, зависимость эффективности от размера файла.

66. Учет свободного места.

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

2. Связный список. Все свободные блоки диска организованы в связный список. Каждый свободный блок указывает на следующий свободный блок. В таком случае нахождение первого свободного блока является задачей очень простой, но нахождение последовательных n свободных блоков требует большого числа чтений с диска. Модификация связного списка: в одном блоке хранятся указатели на n блоков и на n+1 блок, который является главным для следующей группы блоков. Вариант столь же эффективен как и связный список. Для обращения к нескольким блокам, достаточно чтения главного блока с указателем.

3. Индексные дескрипторы(узлы). Свободное пространство учитывается как один файл и для него создаются соответствующие структуры файловой системы, например, индексный узел, который описывает все блоки, принадлежащие данному файлу.