Операционные системы. Макушкина Л.А - 38 стр.

    Популярным способом, применяемым, например, в файловой системе FAT,
является использование связанного списка индексов (рисунок 17, в). Этот способ
является некоторой модификацией предыдущего. Файлу также выделяется память
в виде связанного списка кластеров. Номер первого кластера запоминается в
записи каталога, где хранятся характеристики этого файла. Остальная адресная
информация отделена от кластеров файла. С каждым кластером диска связывается
некоторый элемент — индекс. Индексы располагаются в отдельной области диска
— в MS-DOS это таблица FAT (File Allocation Table), занимающая один кластер.
Когда память свободна, все индексы имеют нулевое значение. Если некоторый
кластер N назначен некоторому файлу, то индекс этого кластера становится
равным либо номеру М следующего кластера данного файла, либо принимает
специальное значение, являющееся признаком того, что этот кластер является для
файла последним. Индекс же предыдущего кластера файла принимает значение N,
указывая на вновь назначенный кластер.
    При такой физической организации сохраняются все достоинства предыдущего
способа: минимальность адресной информации, отсутствие фрагментации,
отсутствие проблем при изменении размера. Кроме того, данный способ обладает
дополнительными преимуществами. Во-первых, для доступа к произвольному
кластеру файла не требуется последовательно считывать его кластеры, достаточно
прочитать только секторы диска, содержащие таблицу индексов, отсчитать нужное
количество кластеров файла по цепочке и определить номер нужного кластера.
Во-вторых, данные файла заполняют кластер целиком, а значит, имеют объем,
равный степени двойки.
    Необходимо отметить, что при отсутствии фрагментации на уровне кластеров
на диске все равно имеется определенное количество областей памяти небольшого
размера, которые невозможно использовать, то есть фрагментация все же
существует. Эти фрагменты представляют собой неиспользуемые части последних
кластеров, назначенных файлам, поскольку объем файла в общем случае не кратен
размеру кластера. На каждом файле в среднем теряется половина кластера. Это
потери особенно велики, когда на диске имеется большое количество маленьких
файлов, а кластер имеет большой размер. Размеры кластеров зависят от размера
раздела и типа файловой системы. Примерный диапазон, в котором может
меняться размер кластера, составляет от 512 байт до десятков килобайт.
    Еще один способ задания физического расположения файла заключается в
простом перечислении номеров кластеров, занимаемых этим файлом (рисунок 17,
г). Этот перечень и служит адресом файла. Недостаток данного способа очевиден:
длина адреса зависит от размера файла и для большого файла может составить
значительную величину. Достоинством же является высокая скорость доступа к
произвольному кластеру файла, так как здесь применяется прямая адресация,
которая исключает просмотр цепочки указателей при поиске адреса
произвольного кластера файла. Фрагментация на уровне кластеров в этом способе
также отсутствует.




                                     38