Другое решение – перечисление всех занимаемых файлом кластеров

Третья попытка

Чтобы избавиться от недостатков второго способа, попробуем список ссылок вынести в заранее определенное место – некоторую таблицу. В результате у нас получится принцип организации файловой системы FAT!

В файловой системе FAT используется системная структура – таблица FAT. С каждым блоком диска (кластером) связывается одна запись таблицы FAT (номер записи = номеру кластера). Если кластер с номером К распределен некоторому файлу, то в К-той записи таблицы FAT содержится номер следующего кластера данного файла (это число является также и номером той записи таблицы FAT, в которой содержится информация о продолжении файла!).

При такой физической организации сохраняются все достоинства предыдущего способа, но снимаются оба отмеченных недостатка. Во-первых, для доступа к произвольному месту файла достаточно прочитать только таблицу FAT (она небольшая), отсчитать нужное количество записей по цепочке и определить номер нужного кластера. И, во-вторых, данные файла занимают кластер целиком, а значит, имеют объем, равный степени двойки.

Итак, FAT – таблица, содержащая столько строк, сколько кластеров на диске. В каждой строке содержатся данные одного из четырех типов: свободный кластер (на рисунке пусто), сбойный кластер (на рисунке отмечен буквой b), ссылка на следующий кластер файла (на рисунке числа), признак конца файла (на рисунке #).

Таблица FAT

1	2	3	4	5	6	7	8	9
			#	#		#		b

Диск

A1	A2	B1	C1	B2	A3	A4

Каталог
А
B
C

Т.к. нам надо записать в строку FAT номер кластера, то количество бит, выделяемых под номер должно быть достаточным для представления самого большого возможного на данном диске номера. Пусть на диске 4 кластера, тогда для адресации достаточно 2 бит (2²=4), если на диске 2000 кластеров, то требуется 11 бит (2¹¹=2048). Было принято решение выделять под адрес на диске 16 битов, позволивший адресовать 65532 кластера. Так родилась FAT16. На дискетах принято выделять под адрес 12 бит (FAT12).

С течением времени емкость жестких дисков возрастала, и потребовалось адресовать большее количество кластеров. И потому появилась FAT32, адресующая 2³²=4,294,967,296 кластеров.

Теперь рассмотрим задание физического расположения файла путем простого перечисления номеров блоков, занимаемых этим файлом. В этом случае в некоторой системной таблице должно быть выделено место под номера всех кластеров файла. Так как файлы могут занимать самое разное количество кластеров, то какого размера должно быть это место? Для быстроты поиска системные таблицы обычно имеют фиксированный размер записи, следовательно, если выберем большой размер, то у большинства файлов это место будет просто не использоваться. Если же выберем маленький размер, то не сможем записать на диск файл из большого количества кластеров. Где же выход?

В NTFS принято следующее решение: действительно запись в MFT – файле имеет достаточно большой размер (1 Кб = 1024 байт). Кроме того, различаются начальные записи и записи продолжений, и если файл занимает очень много места, ему может быть выделена одна запись начальная и несколько записей – продолжений. В начальной записи стоит ссылка на запись продолжение. А в записи – продолжении перечисляются номера следующих кластеров файла и стоит ссылка на запись-продолжение (возможно, пустая). Таким образом, информация о занимаемых кластерах может занять несколько записей в файле MFT. Эти записи в общем случае располагаются не рядом (так как они занимаются по мере необходимости).

Проведем достаточно грубый подсчет. NTFS является 32-разрядной файловой системой, следовательно под номер кластера выделяется 32 бита (4 байта), размер кластера принято брать равным 8 секторов, то есть 8сек = 8*512 = 4096 байт (далее будем приближенно брать 4000 байт). Если файл имеет размер 2 мегабайта, то он занимает 2 000 000 байт = 2000000 байт: 4000 байт/кластер = 500 кластеров. В одной записи MFT – файла помещается не более 1000 байт: 4 байта = 250 номеров, очевидно, что в начальной записи еще меньше. Следовательно, в MFT – файле потребуется занять 500: 250 = 2, а с учетом особенностей начальной записи – 3 записи MFT – файла. Так как ссылка на продолжение содержится в записи MFT – файла, то чтобы добраться до конца файла приходится последовательно читать все MFT – записи (некоторое замедление!).

NTFS фрагмент MFT- файла
	…
	имя атрибуты дата время 37 38 … 57 112…190 начальная 33
	191 192 235 2 3 4 5 300 301 302 303 304…503 продолжение нет
	…

Дата добавления: 2014-12-07