FAT (File Allocation Table)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 21:17, 27 июня 2016.

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

Созданная в 1977 и изначально предназначенная для дискет, FAT вскоре адаптировали и широко использовали почти повсеместно на жестких дисках в эры DOS и Windows 9x на протяжении двадцати лет. По мере развития жёстких дисков возможности файловых систем соответствующим образом расширялись, что привело в результате к различным вариантам файловых систем: FAT12, FAT16 и FAT32. Стандарт FAT был также расширен по другим направлениям, сохраняя совместимость с ПО.

С появлением более мощных компьютеров и ОС FAT перестала быть стандартной файловой системой для Microsoft Windows.

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

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

8-битная FAT
Полное название 8-битная File Allocation Table
Limits
Макс. размер файла ограничен размером тома
Степень детализации размера файла гранулированность по записям (128 bytes)
Макс. длина имени файла 6.3 filename (двоичные файлы), 9 characters (ASCII файлы)
Макс. глубина директории без поддиректорий
Разрешенные символы
в именах файлов
ASCII (0x00 и 0xFF запрещены в первом символе)
Features
Даты зарегистрирован Нет
Признаки Защищённая запись, EBCDIC конвертирование, Чтение после записи


Оригинальная 8-битная FAT

Оригинальная файловая система FAT (или структура FAT, как она называлась изначально) была разработана и запрограммирована Marc McDonald, который основывался на серии обсуждений между ним и Bill Gates. Она была представлена на 8-битных элементах (и возможным числом кластеров данных до 0xBF) в Microsoft's Standalone Disk BASIC-80 и более поздней модели NCR 7200 VI (терминал ввода данных, основанный на 8080, оборудованный 200мм входом для дискет) в 1977/1978. В 1978 Standalone Disk BASIC-80 был портирован на 8086 с использованием эмулятора DEC PDP-10, потому что реальные системы на 8086 уже стали доступны. FAT также использовалась в Microsoft's MDOS/MIDAS, операционной системе для платформ 8080/Z80, написанных McDonald с 1979. Сообщается, что MIDAS был подготовлен для того, чтобы поддерживать 10-битную, 12-битную и 16-битную FAT. В то время как размер объектов директории был 16 байт в Standalone Disk BASIC, MIDAS занимал 32 байта на объект.

FAT12

FAT12
Полное название 12-bit File Allocation Table
Limits
Макс. размер тома 16  MB (with 4  KB кластерами) 32  MB (с 8  KB кластерами)
Макс. размер файла ограничен размером тома
Степень детализации размера файла 1  байт
Макс. количество файлов 4,068 for 8 KB кластерами
Макс. длина имени файла 8.3 имя файла с OEM символами,255 UCS-2 символы с использованием LFN
Макс. глубина директории 32  уровня или 66 
Features
Даты зарегистрирован Дата модификации (86-DOS после 0.42), время модификации (исключая PC  DOS 1.0 и 86-DOS), дата/время создания (DOS 7.0 и позже), дата доступа
Диапазон дат 1980-01-01 до 2099-12-31
Дата резолюции 2  секунд со времени модификации, 10 ms от времени создания, 1 день даты доступа 2  секунд на удаление
Признаки Read-only (с DOS 2.0), Hidden, System, Volume (с MS-DOS 1.28 and PC DOS 2.0), Directory (с MS-DOS 1.40 and PC DOS 2.0), Archive (с DOS 2.0)
Прозрачное сжатие Per-volume, SuperStor, Stacker, DoubleSpace, DriveSpace
Транспорантное шифрование по томное (только в DR-DOS)

Между апрелем и августом 1980, в процессе заимствования концепта FAT для операционной системы от SCP на 8086 - QDOS 0.10, Tim Paterson расширил элементы таблицы до 12 бит, понизил число FAT до двух, переопределил некоторые из зарезервированных значений для кластеров и модифицировал разметку диска, поэтому корневая директория стала находиться между FAT и областью данных в его реализации FAT12. Paterson также расширил девятисимвольное (6.3) имя файла до одиннадцати символов, чтобы поддерживать стиль имён файлов CP/M 8.3 и файл контрольных блоков. К августу 1980 QDOS была переименована в 86-DOS и, начиная с 86-DOS 0.42, размер и разметка директорий бы изменён с 16 байт до 32, чтобы добавить метку времени и повысить теоретический размер файла для 16 MB. 86-DOS 1.00 стала доступна в начале 1981. Позднее в 1981 86-DOS получила развитие в виде Microsoft's MS-DOS и IBM PC DOS. Возможность читать предыдущие 16-байтные директории была убрана в MS-DOS 1.20.

Изначально созданная для дискет, FAT12 использовала 12-битные записи для кластерных адресов в FAT, которые не только ограничивали максимальное число кластеров до 4078 (для кластеров данных 0x002 до 0xFEF) но также делали манипуляции с FAT сложными из-за наличия в ПК 8-битных и 16-битных регистров. (MS-DOS и PC DOS поддерживали до 4084 кластеров в разделах FAT12, значение кластера 0xFF0 выполняло роль завершающего маркера в любом разделе FAT12, начиная с MS-DOS/PC DOS 3.3.)

Размер диска хранился и вычислялся как 16-битный счетчик секторов, который ограничивал размер памяти до 32 MB при размере логического сектора в 512 байт. FAT12 использовался несколькими производителями с различными физическими форматами, но обычная дискета была размером 5.25 дюймов (130 мм), односторонняя, 40 дорожек, с восемью секторами на дорожке, что приводит к вместимости 160 KB как для системных областей, так и для файлов.

Согласно соглашению, все структуры были организованы таким образом, чтобы помещаться на первой дорожке, избегая таким образом продвижения вперед во время операций чтения и записи, хотя это зависит от производителя и физического формата диска. Любой повреждённый сектор в области структуры управления на нулевой дорожке мог привести диск в негодность. Утилита форматирования из DOS полностью отвергала такие диски. Повреждённые секторы были разрешены только в области файлов (начиная с DOS 2.0) и отмечались зарезервированным значением 0xFF7 в FAT. Это делало весь остальной кластер пригодным к использованию.

Когда 86-DOS поддерживала три дисковых формата (250.25 KB, 616 KB и 1232 KB с FAT IDs 0xFF и 0xFE) на 8-дюймовых дискетах, IBM PC DOS 1.0, выпущенная с IBM Personal Computer в 1981, поддерживала только 8-секторный формат дискет с вместимостью 160 KB (FAT ID 0xFE) для односторонних 5.25-дюймовых входов для дискеты, а PC DOS 1.1 добавил поддержку двухстороннего формата 320 KB (FAT ID 0xFF). PC DOS 2.0 предоставил поддержку 9-секторных дискет 180 KB (FAT ID 0xFC) и 360 KB (FAT ID 0xFD).

86-DOS 1.00 и PC DOS 1.0 записи директорий включали только одну дату, дату последней модификации. PC DOS 1.1 добавил поддержку времени последней модификации. PC DOS 1.x файловые атрибуты включали скрытый бит и системный бит, оставшиеся биты не определены. В то время DOS не поддерживал иерархическую файловую систему, что было до сих пор приемлемо, т. к. число файлов на диске редко превышало несколько дюжин.

BIOS Parameter Block (BPB) был введён в PC DOS 2.0, в этой версии также добавлены метки только для чтения, архив, том; биты атрибутов директорий для иерархии поддиректорий.

MS-DOS 3.0 предоставил поддержку плотно записываемых 1.2 MB 5.25-дюймовых дискет, у которых было 15 секторов на дорожке. FAT12 используется на дискетах, включая 1.44 MB и более поздние 2.88 MB диски.

FAT16

Начальная реализация FAT16 не предоставляла больший размер раздела, чем FAT12, начальное преимущество FAT16 было использование меньших кластеров, что делало использование диска более эффективным, особенно для большого числа файлов размером в несколько сотен байт.

Когда жесткие диски стали больше, и FAT12 и FAT16 в MS-DOS / PC DOS не обеспечивали преимущества по использованию дополнительного пространства памяти, несколько производителей создали свои варианты FAT.

Некоторые вендоры (AST и NEC) поддерживали восемь вместо стандартных четырёх главных записей в их расширенной Master Boot Record (MBR). Другие вендоры работали с размерами томов, которые задавались 16-битными записями секторов и соответствующей арифметикой, повышая размер секторов, с которыми работает ОС. Эти, так называемые, логические секторы были больше (до 8192 байт), чем размер физического сектора (в основном, 512 байт), который диктовал ROM-BIOS INT 13H или аппаратным обеспечением. DOS-BIOS или System BIOS комбинировали несколько физических секторов в логические секторы, с которыми затем работала файловая система. Недостатком этого подхода была менее эффективная буферизация секторов, а также повышенное потребление памяти структурами данных в DOS.

В ноябре 1987 вместе с Compaq Personal Computer DOS 3.31 было представлено то, что сегодня просто известно, как формат FAT16, с расширением 16-битного счётчика секторов диска до 32-битного в BPB. Хотя изменения диска были минимальны, драйвер диска в DOS пришлось переписать для работы с 32-битными номерами секторов, эта задача была трудна, т. к. этот драйвер был написан на 16-битном ассемблере. Изначально результат был назван DOS 3.31 Large File System. Microsoft's DSKPROBE упоминает название BigFAT. Технически данная версия известна как FAT16B.

В 1988 улучшение FAT16B стало доступно в DR DOS 3.31, PC DOS 4.0, OS/2 1.1, и MS-DOS 4.0. Ограничение на размеры разделов диктовались 8-битным счетчиком со знаком для числа секторов в кластере (всего 64). Учитывая стандартный размер сектора на жёстком диске в 512 байт, присутствует ограничение на размер кластера в 32 KB, что ограничивало размер раздела в FAT16 до 2 GB для размера сектора в 512. Намного позже в Windows NT максимальный размер кластера был повышен до 64 KB, используя рассмотрение счетчика секторов в кластере как беззнакового. Однако получившийся формат был не совместим с другими реализациями FAT и приводил к большей фрагментации.


FAT32

FAT32
Полное название 32-битная File Allocation Table
Limits
Мин . размер тома 32 MB-4.5 KB (с 65525 кластерами и 512 байтными секторами)
256 MB-36 KB (c 65525 кластерами и 4 KB секторами)
Макс. размер тома 2 TB (c 512  байтными секторами)
8 TB (c 2 KB секторами и 32 KB кластерами)
16 TB (с 4 KB секторами и 64  KB кластерами)
Макс. размер файла 2,147,483,647 байт (2  GB (без LFS)
4,294,967,295 байт (4  GB – 1 (с LFS)
274,877,906,943 байт (256  GB – 1) (только с FAT32+)
Степень детализации размера файла 1 байт
Макс. количество файлов 268,173,300 для 32 KB кластеров
Макс. длина имени файла имя файла 8.3 в кодировке OEM,
255 символов UCS-2 с использованием LFN
Макс. глубина директории 32 уровня или 66 символов (с CDS),
60 уровней или более (без CDS)
Features
Даты зарегистрирован дата/время модификации, дата/время создания (только для DOS 7.0 и выше), дата доступа (доступна только с разрешенным ACCDATE), дата/время удаления (только с DELWATCH 2)
Диапазон дат 1980-01-01 до 2107-12-31
Дата резолюции 2 секунды для времени последней модификации,
10 мс для времени создания,
1 день для даты доступа,
2 секунды для времени удаления
Признаки только для чтения, скрыт,системный, том, директория, архив
Прозрачное сжатие нет
Транспорантное шифрование нет

FAT32 — последняя версия файловой системы FAT и улучшение предыдущей версии, известной как FAT16. Она была создана, чтобы преодолеть ограничения на размер тома в FAT16, позволяя при этом использовать старый код программ MS-DOS и сохранив формат. FAT32 использует 32-разрядную адресацию кластеров. FAT32 появилась вместе с Windows 95 OSR2.

Максимально возможное число кластеров в FAT32 равно 268 435 445, что позволяет использовать тома (логические диски) объёмом до 8 ТБ. Размер кластера по умолчанию для файловой системы FAT32 составляет от 512 байт до 32 КБ в зависимости от размера тома и конкретной версии ОС. При использовании размера кластера, равного 32768 байт, максимальный размер тома составит чуть менее 8 ТБ. Хотя размер сектора может быть любым, традиционно он считается равным 1 сектору диска и равен 512 байт и т.к. эта величина не менялась с момента создания — она может считаться некоторым ПО как константа. Это может вызвать некоторые проблемы совместимости. Средство ScanDisk, входящее в состав Microsoft Windows 95 и Microsoft Windows 98, является 16-разрядной программой. Для таких программ максимальный размер кластера отдельного фрагмента памяти составляет 16 МБ минус 64 КБ. Следовательно, ScanDisk в Windows 95 или Windows 98 не может работать с томами FAT32, у которых размер таблицы FAT превышает 16 МБ минус 64 КБ. Запись в таблице FAT на томе с файловой системой FAT32 имеет размер 4 байта, поэтому ScanDisk не может работать с таблицей FAT на диске FAT32, описывающей более 4 177 920 кластеров (включая два резервных). С учётом самих таблиц FAT и при максимальном размере кластера 32 КБ размер тома может быть до 127,53 ГБ.

Максимально возможный размер файла для тома FAT32 — ~ 4 ГБ — 4 294 967 295 байт (в FAT32 под размер файла отведено 4 байта. 4 байта - это 32 бита. 232-1 — 4 294 967 295 байт. Поэтому размер файла не может быть больше этого значения, иначе не получится указать его длину. Хотя цепочку в FAT таблице можно продолжать и дальше, но тогда для определения размера файла придется каждый раз пробегать по всей цепочке, а это будет занимать много времени. К тому же в FAT таблице указаны только номера кластеров, поэтому тогда можно будет узнать только округлённое значение длины файла) — это весьма важный фактор для смены файловой системы. FAT32 не поддерживает установку разрешений на доступ к файлам и папкам и некоторые другие функции современных файловых систем. Все эти причины привели к тому, что сейчас наблюдается тенденция отказа от FAT32 в пользу более продвинутых файловых систем, таких как NTFS, Ext2/Ext3. Чаще всего недоверие к NTFS возникает у пользователей из-за трудностей с назначением прав доступа (так как чаще всего они единственные владельцы файлов) и её закрытости.

Производные от FAT системы

Turbo FAT

В своей NetWare File System (NWFS) Novell реализовала сильно модифицированный вариант FAT для операционной системы theNetWare. Для больших файлов она использовала метод повышения производительности, названный Turbo FAT.

FATX

FATX - семейство файловых систем для жестких дисков и карт памяти в консоли Microsoft's Xbox, представленной в 2001.

Используя те же идем, что и в FAT16 и FAT32, дисковые структуры FATX16 и FATX32 были упрощены, но стали фундаментально несовместимыми с обычными FAT16 и FAT32, что сделало невозможным для обычных драйверов FAT монтировать тома таких файловых систем.

Сектор, размером 4 KB, содержит 18 байтную структуру, похожую на BPB. Размер кластера 16 KB, присутствует только одна копия FAT в Xbox. Размер записей директории - 64 байта вместо обычных 32-х. У файлов могут быть имена до 42 символов при использовании набора символов OEM, максимальный размер -- 4 GB - 1 байт. Метки времени содержат даты создания, модификации и доступа, а также их время, но вместо эпохи 1980 используется 2000.

exFAT

exFAT, иногда называется FAT64 — проприетарная файловая система, предназначенная главным образом для флэш-накопителей. Впервые представлена фирмой Microsoft для встроенных устройств в Windows Embedded CE 6.0. Размер кластера по умолчанию для файловой системы exFAT составляет от 4 КБ до 128 КБ в зависимости от размера тома.

Основными преимуществами exFAT перед предыдущими версиями FAT являются:

  • Уменьшение количества перезаписей одного и того же сектора, что важно для флеш-накопителей, у которых ячейки памяти необратимо изнашиваются после определённого количества операций записи (это сильно смягчается выравниванием износа (wear leveling), встроенным в современные USB-накопители и SD-карты). Это было основной причиной разработки exFAT.
  • Теоретический лимит на размер файла 264 байт (16 эксабайт).
  • Максимальный размер кластера увеличен до 225 байт (32 мегабайта).
  • Улучшение распределения свободного места за счёт введения бит-карты свободного места, что может уменьшать фрагментацию диска.
  • Введена поддержка списка прав доступа.
  • Поддержка транзакций (опциональная возможность, должна поддерживаться устройством).

Краткий обзор разметки

Порядок стркутур в FAT
Contents Загрузочный сектор Сектор FSInfo (только в FAT32) Другие зарезервированные секторы (опционально) Область таблицы FAT #1 Область таблицы FAT #2 ... (условно) Корневая директория (только в FAT12/FAT16) Область данных (для всех файлов и директорий) ... (до конца диска)
Размер в секторах (число зарезервированных секторов) (число FAT) * (число секторов в FAT) (число корневых объектов * 32) / (число байт в секторе) (число кластеров) * (секторов в кластере)

В файловой системе FAT смежные секторы диска объединяются в единицы, называемые кластерами. Количество секторов в кластере равно степени двойки (см. далее). Для хранения данных файла отводится целое число кластеров (минимум один), так что, например, если размер файла составляет 40 байт, а размер кластера 4 кбайт, реально занят информацией файла будет лишь 1 % отведенного для него места. Для избежания подобных ситуаций целесообразно уменьшать размер кластеров, а для сокращения объёма адресной информации и повышения скорости файловых операций — наоборот. На практике выбирают некоторый компромисс. Так как ёмкость диска вполне может и не выражаться целым числом кластеров, обычно в конце тома присутствуют т. н. surplus sectors — «остаток» размером менее кластера, который не может отводиться ОС для хранения информации.

Пространство тома FAT32 логически разделено на три смежные области:

  • Зарезервированная область. Содержит служебные структуры, которые принадлежат загрузочной записи раздела (Partition Boot Record — PBR, для отличия от Master Boot Record — главной загрузочной записи диска; также PBR часто некорректно называется загрузочным сектором) и используются при инициализации тома;
  • Область таблицы FAT, содержащая массив индексных указателей («ячеек»), соответствующих кластерам области данных. Обычно на диске представлено две копии таблицы FAT в целях надежности;
  • Область данных, где записано собственно содержимое файлов — то есть текст текстовых файлов, кодированное изображение для файлов рисунков, оцифрованный звук для аудиофайлов и т. д. — а также т. н. метаданные — информация относительно имен файлов и папок, их атрибутов, времени создания и изменения, размеров и размещения на диске.

В FAT12 и FAT16 также специально выделяется область корневого каталога. Она имеет фиксированное положение (непосредственно после последнего элемента таблицы FAT) и фиксированный размер в 32-хбайтных элементах, т.е. при описании в Partition Boot Record указывается именно количество 32-хбайтных элементов, каждый из которых описывает какой-либо элемент корневого каталога (будь то файл или другой вложенный каталог).

Если кластер принадлежит файлу, то соответствующая ему ячейка в таблице FAT содержит номер следующего кластера этого же файла. Если ячейка соответствует последнему кластеру файла, то она содержит специальное значение (FFFF16 для FAT16). Таким образом выстраивается цепочка кластеров файла. Неиспользуемым кластерам в таблице соответствуют нули. «Плохим» кластерам (которые исключаются из обработки, например, по причине нечитаемости соответствующей области устройства) также соответствует специальный код.

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

Ссылки