File Allocation Table

File Allocation Table

FAT (от англ. File Allocation Table — «таблица размещения файлов») — архитектура файловой системы, сейчас широко используемая в картах памяти фотоаппаратов и других устройств.

Разработана Биллом Гейтсом и Марком МакДональдом в 1977 году^[1]. Использовалась в качестве основной файловой системы в операционных системах DOS и Microsoft Windows (до версии Windows ME).

Структура FAT определена стандартом ECMA-107.

Структура системы FAT

Раздел диска, отформатированный в системе FAT, имеет следующую структуру:

	Загрузочный сектор	Информация о ФС (только в FAT32)	Дополнительные секторы	Таблица размещения файлов #1	Таблица размещения файлов #2	Корневой каталог (только в FAT12/16)	Область данных (для файлов и каталогов)
Размер (в секторах)	(количество зарезервированных секторов)			(Количество FAT таблиц)*(количество секторов в FAT)		(Количество записей в корне*32)/(количество байт в секторе)	количество кластеров*секторов в кластере

• загрузочный сектор;
• таблица размещения файлов — собственно FAT (традиционно в двух экземплярах, но вообще-то количество копий указано в загрузочном секторе);
• корневой каталог;
• файлы.

Для хранения файлов всё доступное для них пространство разбивается на кластеры. Таблица размещения файлов содержит ячейки, каждая из которых соответствует определённому кластеру диска. Если кластер принадлежит файлу, то соответствующая ему ячейка содержит номер следующего кластера этого же файла. Если ячейка соответствует последнему кластеру файла, то она содержит значение «FFFF». Таким образом выстраивается цепочка кластеров файла. Неиспользуемые кластеры помечены «0000». «Плохие» кластеры помечены специальным кодом «FFF7».

При удалении файла фактически только делается запись в каталоге, а цепочка кластеров не разрушается и данные не затираются. Это позволяет восстанавливать удалённые файлы, если на их место ещё не было ничего записано.

Максимальный размер кластера, который поддерживается в FAT, составляет 64 Кб. Зная, что максимальное количество кластеров, которое можно адресовать шестнадцатиразрядным указателем равно 65536, можно вычислить какой величины раздел можно отформатировать, применяя тот или иной размер кластера. Если взять размер кластера равным размеру физического кластера (сектора), то получим: 65536 * 512 = 32 Мб. Если взять кластер в 2 раза больше, то можно отформатировать раздел уже до 64 Мб. Ввиду того, что разрядность ФС - величина постоянная, для форматирования дисков различных размеров будут применяться разные размеры кластеров. Например, чтобы отформатировать диск более 1 Гб, нужно применять кластер 16 КБ. Поскольку размер кластера, являющийся максимально допустимым в этой ФС, равен 64 Кб, то можно определить, что максимальный размер раздела, форматируемый под FAT, равен 4 Гб.

Отказоустойчивость системы

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

Версии системы FAT

Существует четыре версии FAT — FAT12, FAT16, FAT32 и exFAT. Они отличаются количеством бит, отведённых для хранения номера кластера. FAT12 применяется в основном для дискет, FAT16 — для дисков малого объёма, а новая exFAT преимущественно для флэш-накопителей.

Изначально FAT не поддерживала иерархическую систему каталогов. Все файлы располагались в корневом каталоге. Это оказалось неудобно. И к тому же малый размер корневого каталога ограничивал количество файлов на диске файлов. Каталоги были введены с выходом MS-DOS 2.0.

В различных операционных системах также были внедрены различные расширения FAT. Например, в DR-DOS имеются дополнительные атрибуты доступа к файлам; в Windows 95, Linux и Proolix — поддержка длинных имён файлов (LFN) в формате Unicode (VFAT); в OS/2 — расширенные атрибуты всех файлов.

Характеристики

	FAT12	FAT16	FAT32
Разработчик	Microsoft
Полное название	File Allocation Table (русск. Таблица Размещения Файлов)
	(12-bit версия)	(16-bit версия)	(32-bit версия)
Представлена	1980 (Microsoft Disk BASIC)	Ноябрь 1987 (MS-DOS 3.31)	Август 1996 (Windows 95 OSR2)
Идентификатор тома	0x01 (MBR)	0x04, 0x06, 0x0E (MBR)	0x0B, 0x0C (MBR) EBD0A0A2-B9E5-4433 -87C0-68B6B72699C7 (GPT)
Структуры
Содержимое директории	Таблица
Размещение файлов	Линейный список
Сбойные блоки	Тегирование кластера
Ограничения
Максимальный размер файла	32 MiB	2 GiB	4 GiB
Максимальное количество кластеров	4.077 (212-19)	65.517 (216-19)	268.435.437 (228-19)
Максимальная длина имени файла	8.3, или 255 символов при использовании LFN
Максимальный размер тома	32 MiB	2 GiB 4 GiB (64 КБ кластер — мало где поддерживается)	2 TiB 8 TiB (2КБ сектор)
Возможности
Сохраняемые даты	Создания, модификации, доступа
Диапазон дат	1 января, 1980 — 31 декабря, 2107
Дополнительные данные	Изначально не поддерживаются
Attributes	Только для чтения, скрытый, системный, метка тома, подкаталог, архивный
Разграничение прав доступа	Нет
Прозрачное сжатие	Per-volume, Stacker, DoubleSpace, DriveSpace		Нет
Прозрачное шифрование	Per-volume only with DR-DOS		Нет

Лицензирование

Майкрософт запатентовала некоторые алгоритмы работы с FAT и VFAT.

В США при повторном рассмотрении^{[когда?]} было принято решение аннулировать некоторые из патентов, но потом его отменили.

В октябре 2006 года в Германии был аннулирован за очевидность патент на VFAT, выданный Европейским патентным бюро.^[2]

Со временем FAT стали широко использовать в различных устройствах для совместимости между DOS, Windows, OS/2, Linux. Майкрософт не выказывала намерений принуждать к их лицензированию^{[уточнить]}.^[3]

В феврале 2009 года Майкрософт подала в суд на компанию TomTom, производителя автомобильных навигационных систем на основе Linux, обвиняя её в нарушении патентов.^[4]

По мнению Джереми Эллисона^{[уточнить]}, цель Майкрософт — поставить различные компании перед выбором: заключить с Майкрософт договор о патентной защите (такой, который с ней заключила Novell в ноябре 2006 года), нарушив тем самым лицензию GNU GPL, и сделав невозможным для себя использование Linux, или не заключать такого договора, и быть обвинённой в нарушении патентов, защита по которым предоставляется при его заключении при условии неразглашения.^[5][6]

В марте 2009 года TomTom подала встречный иск о нарушении патентов.^[7]

Примечания

1. ↑ http://cd.textfiles.com/megademo2/INFO/OS2_HPFS.TXT
2. ↑ Federal Patent Court declares FAT patent of Microsoft null and void (англ.). heise online. Heise Zeitschriften Verlag (2 марта 2007). Проверено 10 марта 2009.
3. ↑ Brian Kahin Microsoft Roils the World with FAT Patents (англ.). The Huffington Post. HuffingtonPost.com, Inc. (10 марта 2009). Проверено 10 марта 2009.
4. ↑ Ryan Paul Microsoft suit over FAT patents could open OSS Pandora's Box (англ.). Ars Technica. Condé Nast Publications (25 февраля 2009). Проверено 9 марта 2009.
5. ↑ Glyn Moody The Real Reason for Microsoft's TomTom Lawsuit (англ.). ComputerworldUK. International Data Group Inc. (5 марта 2009). Проверено 9 марта 2009.
6. ↑ Steven J. Vaughan-Nichols Linux companies sign Microsoft patent protection pacts (англ.). Блоги Computerworld. International Data Group Inc. (5 марта 2009). Проверено 9 марта 2009.
7. ↑ Erica Ogg TomTom countersues Microsoft in patent dispute (англ.). CNET News. CBS Interactive Inc (19 марта 2009). Проверено 20 марта 2009.

Ссылки

• ECMA-107 стандарт FAT(англ.)

См. также

• FAT32
• exFAT
• NTFS

• ext2
• ext3
• ext4
• reiserFS