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

Идея FAT - диск поделён на равные части - кластеры.

Непосредственно FAT - таблица использования диска

Таблица каталогов

Как всё это работает. Про таблицу использования диска пользователь ничего не обязан знать. Если пользователю нужно скопировать файл index.dat, то он заходит в соответствующий каталог (в данном случае в корневой каталог диска). Убеждается, что там лежит его файл (когда подаётся DOS-команда dir, то операционная система обращается к таблице каталогов и выдаёт оттуда соответствующую информацию об имени и расширении файла). Если пользователь даст команду скопировать этот файл на другой диск, то начнётся считываение этого файла в оперативную память компьютера. При этом операционная система обратится к таблице каталогов, выяснит, что файл index.dat начинается в кластере 10. Обратится к таблице использования диска, выяснит, что после десятого кластера нужно считывать 12-й. Выяснит, что следующим кластером после 12-го будет 14-й, потом - 13-й. Для 13-го кластера уже стоит признак EOF, то есть в нём файл закончится. Но этой информации мало, так как кластера 10, 12, 14 целиком заняты нужным файлом, а площадь 13-го кластера занята файлом не целиком. Операционная таблица обратится к Partition Table и выяснит, что для текущего диска размер кластера равен 4096 байт. Количество кластеров занятых целиком =3, соответственно в них находится 3*4096=12288. Соответственно кластер 13 будет содержать только первые два байта ценной информации. В оперативную память будет считано всё из 10, 12, и 14-го кластеров, а из 13-го кластера будут считаны оставшиеся 2 байта.

Пояснения: рисунок 1 и рисунок 2.

Примечание 0. С точки зрения DOS-подобной операционной системы (в том числе и Windows), таблица каталогов - это обычный файл, почти текстовый, но записанный по определённым правилам и открытие какого бы то ни было каталога означает для операционки команду на считываение соответствующего "файла" (содержащего таблицу каталогов). Смотри, например, каталог PAPKA.VAS

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

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

Задание. На рабочем столе Windows создайте любой документ. Правой по этому документу-> {Свойства}. В WinXP отображаются два размера: размер (подразумевается документа) и размер на диске (сумма размеров занимаемых кластеров).

Изменение размера кластера, как способ увеличить объём хранимых данных за счёт уменьшения скорости доступа к ним

Рис.А1.

Всё место на данном диске занято, так как нет ни одного свободного кластера. Правда место используется неэффективно.

Рис.А2.

Рис.А3.

Вывод. Если знаем, что на пользовательском диске мы будем работать с файлами небольшого размера, то при операции разбиении диска нужно указывать именно кластеры небольшого размера.

Понятие четырёх базовых атрибутов файла, характерных для файловой системы FAT.

Read-Only (Только для чтения).

Предназначение атрибута

• чтобы оградить важные файлы от изменения. Классические программы-редакторы не перезаписывают файлы с таким атрибутом.
• чтобы на уровне файловой системы оградить незаписываемые носители (CD-R) от попыток изменить файлы на них, так как неизвестно, насколько корректно написан драйвер этого носителя. Поэтому программы типа Nero Burning ROM при создании компакт-дисков автоматически проставляют на все файлы атрибут read-only.
• в классическом DOS попытка удалить файл с атрибутом read-only к успеху не приводит до тех пор, пока предварительно не будет отключен этот атрибут.
• в классических Norton-подобных оболочках при попытке удаления группы файлов, на каждый удаляемый файл с атрибутом read-only будет дополнительное диалоговое окно с запросом о том, нужно ли его удалить. Поэтому в оболочках предварительно для группы файлов очищают их атрибуты и только потом выполняют удаление.

Работа с атрибутом read-only.

Archive (Архивный)

Любая программа-редактор (текстовый, электронных таблиц) при сохранении изменений в документ проставляет этот атрибут.

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

НЕ ПУТАТЬ с программами сохранения системных дисков. Эти два вида программ дополняют друг-друга.

Работа с атрибутом archive.

Задание.

1. На диске D: (Common) создать папку. Назвать её "Для архивирования ФИО" (ФИО - Ваши инициалы). В папке создать 5 текстовых и 5 документов MS Word. В каждый документ набрать по несколько слов. Принудительно снять атрибут Archive (просто отключив соответствующую галочку в свойствах документа) у половины документов.
2. После этого запустите "Архивацию данных". С помощью ссылки на "Расширенный режим" и типа архивирования "Добавочный" сохраните свою папку в файл D:\Save001FIO.bkf (FIO - Ваши инициалы).
3. Папку D:\"Для архивирования ФИО"  удалите.
4. Воспользуйтесь архивом для восстановления папки.
5. За собой удалите всё, что сегодня создавали: папку и архив.

Hidden (скрытый)

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

Работа с атрибутом hidden.

Примечание. Если на компьютере пользователь включает отображение скрытых файлов, а при следующем входе в окно настройки выясняется, что отображение скрытых файлов отключено - это признак того, что на компьютере активен вирус.

System (системный)

Атрибут принадлежности файла системе. Удаление такого файла вызывает у системы дополнительные вопросы при удалении.

Работа с атрибутом system.

Примитивное понятие об удалении файла на логическом уровне

Было - Таблица каталогов

Стало - Таблица каталогов

Удаление файла на логическом уровне. Отметка об удалении файла. Восстановление файла (unerase, undelete). ЭТОТ пункт "на вырост"

Norton DiskEditor и Unerase

• Запуск DiskEdit, чтобы увидеть фактическую организацию хранения данных на дискете, в том числе наличие отметки удалённых фалов (русская буква x ставится на первое место имени и в кластерной цепочке вместо EOF или номера следующего кластера в цепочке ставится 0).
• Осмотр из DiskEdit того, как выглядит описание не удалённых файлов.
• Неудачная попытка запуска Norton Unerase в многозадачной среде (Windows) для попытки восстановления файлов на диске.
• Ручное восстановление файла из DiskEditor (не очень корректное, так как забыл поправить FAT). Внимание!! Попытку восстановления файла вручную из DiskEditor надо выполнять загрузившись в DOS, в крайнем случае в Win9х. В таком случае достаточно просто заменить первую букву имени x на любой допустимый символ, например на цифру. Неплохо, хотя и не обязательно, так же в соответствующем месте FAT указать метку <EOF>.
• Неудачная попытка запуска Unerase (не хватило памяти) и копирование дистрибутивного пакета утилит на жёсткий диск
• Удачная попытка запуска Unerase (памяти хватило после трассировки, об этом процессе позже в лекциях)

Выводы. Если какой-то файл (каталог) был ошибочно удалён, то с носителем (диском, дискетой) нужно совершать как можно меньше действий, в том числе: установок программ, перезагрузок операционной системы (если он в ней участвует).

Примечание 1. На западе директора крупных компаний в соответствии с велениями моды раз в несколько лет покупают себе дорогие суперсовременные мобильные телефоны (с ценой $1000 - $7000). А ставшие устаревшими модели продают за полцены перекупщикам. При этом нередко перекупщики восстанавливают стёртую информацию (письма электронной почты, документы Word, SMS) и продают её конкурентам.

Примечание 2 (на вырост). Когда на диске создаются или на него копируются файлы из Norton Cmmander (или VC), то делается запись по правилам файловой таблицы FAT и в DiskEditor эти файлы будут отображаться белым цветом. Когда ту же операцию выполняет Win, то запись делается по правилам longFAT и те же имена файлов будут отображаться красным цветом.

На вырост. Linux. Сторонняя статья (англ.) о методах восстановления Partition Table и FAT (ext3).

Все *.deb пакеты, которые мы испольховали: smb://zoo/distrib1/00_LINUX.FOR/utils/recovery/

Удаление файла на физическом уровне - "Wipe - Вытирание".

Рис. 1. Изначальная запись данных на магнитном носителе.

Уровень магнитного сигнала ниже 0,4 воспринимается как 0 (стандартная установка).

Уровень магнитного сигнала выше 0,6 воспринимается как 1 (стандартная установка).

То есть зона неопределённости находится в значениях от 0,4 до 0,6.

С этой точке зрения записанное выражение интерпретируется в виде 001110001 (оригинальное значение).

Рис.2. Первая перезапись данных на магнитном носителе единицами. При этом уровень (сила) перезаписанного сигнала в каждом участке носителя пропорциональна первоначальному сигналу.

Уровень магнитного сигнала ниже 0,4 воспринимается как 0 (стандартная установка).

Уровень магнитного сигнала выше 0,6 воспринимается как 1 (стандартная установка).

С этой точке зрения записанное выражение интерпретируется в виде 111111111.

Рис.2г. Зону неопределённости подняли до значений от 0,7 до 0,8:

Уровень магнитного сигнала ниже 0,7 воспринимается как 0 (стандартная установка).

Уровень магнитного сигнала выше 0,8 воспринимается как 1 (стандартная установка).

С этой точке зрения записанное выражение интерпретируется в виде 001110001 (полное соответствие оригинальному значению) .

Рис.2д. Произведена многократная перезапись данных поверх.

Невозможно подобрать зону неопределённости настолько чутко, чтобы прочитать данные.

С этой точке зрения записанное выражение интерпретируется в виде 111111111.

Вывод. Надо произвести неоднократную (обычно 3, 5, 7 раз) перезапись единицами, чтобы уровень (сила) перезаписанного сигнала в каждом участке носителя не была пропорциональна первоначальному сигналу, а находилась на максимально возможном, равном для всех участков уровне.

Следовательно. Полное форматирование = однократному вытиранию (Wipe).

Примечание. Для удаления файла, инфицированного вирусом, не нужно применять ничего сложнее быстрого форматирования.

УСТАРЕЛО. Norton Utilites Wipe, как средство поднять уровень сигнала во всех байтах до значения 0,99 от максимального уровня сигнала.

• Установка Norton Utilites for DOS
• Вытирание файла средствами NU Wipe for DOS
• Результат вытирания файла.

УСТАРЕЛО. Norton System Works: современный комплект Norton Utilites. ЭТОТ пункт "на вырост"

• Установка Norton System Works
• Неудачная попытка использования Win Unerase
• Удачная попытка использования Win Wipe

Некоторые современные выводы из понятий удаление файла физическое и удаление файла логическое

Уровни форматирования магнитного диска - см. рис.

Уровни проверки магнитного диска на наличие ошибок - см. рис.

Физические ошибки при организации хранения и передачи данных. Технологии поиска (и исправления) такого рода ошибок

См. рис. B2 - понятие BAD-кластера.

Рис.3. Идеология S.M.A.R.T., состоящая в выделении и постоянном контроле двух дополнительных зон уровня сигнала, непосредственно прилегающих сверху и снизу к уровню нормы.

ВОПРОСЫ:

• можно ли использовать зону неопределённого сигнала для хранения дополнительного бита данных.

Включение S.M.A.R.T. на уровне BIOS, в качестве потенциально опасного параметра, способного привести к зависанию компьютера.

Рис.4. Идеология контроля и (или) коррекции хранимых или передаваемых данных по уровню чётности.

Рис.5. Применение механизма циклической суммы, как альтернативного контролю чётности способа. ВНИМАНИЕ: приведена операция арифметического сложения, она не имеет ничего общего с операцией логического сравления, используемого при шифровании.

Пример расёта циклической суммы:

Создайте документ Word. Назовите. Откройте. Наберите в него немного текста. Закройте с сохранением.

Заархивируйте его с использованием WinRAR. Откройте архив и посмотрите, что напротив файла появиласть его CRC32 - 32-х битная циклическая сумма.

Примечание 1-б. Защита целостности архива при создании, хранении, передаче и распаковке с использованием контрольной суммы.

Задание 2-б. Рассчитайте восьмибитную контрольную сумму для числа 10000001.11000011.11100111.11111111.10101010.01010101

У меня получилось:

 10000001
 11000011
 --------
101000100
 11100111
 --------
100101011
 11111111
 --------
100101010
 10101010
---------
 11010100
 01010101
---------
100101001

Упрощение решения этой задачи можно выполнить с помощью обычного калькулятора Windows при переводе его вида в инженерный и простановки ему двоичного счисления BIN. Отбрасывание всех знаков левее восьмого можно выполнить в самый последний момент.

Дойдя до этого момента многие начали инересоваться особенностями двоичного счисления и перевода его в десятичное и обратно, развлечения ради поместил сюда вот это.

Те же действия по вычислению контрольной суммы можно сделать без перехода к двоичному счислению, а используя побайтное счисление. Пример: 5.7.250.57.84. В любом месте может находиться число со значением от 0 до 255 (всего чисел 256, что характерно классическому подходу к кодировке текстового, например, файла).

5 + 7 = 12 (< 256)

12 + 250 = 262 (>256), следовательно 262-256= 6

6 + 57 = 63 (< 256)

63 + 84= 147. ЭТО и есть контрольная сумма при восьмибитном (= ОДНОБАЙТНОМ) счислении.

Логические ошибки на диске при организации хранения данных. Их исправление.

Наиболее часто встречающаяся ошибка - Cross Linking Files - пересекающиеся цепочки файлов.

Когда файлN1.txt записан в кластерах 56-80-81-99-101-102 и файлN5.txt записан в кластерах 40-41-57-101-102 очевидно, что один из файлов (а может быть и оба) претендует на кластер, который ему не принадлежит. Программа исправления может лишь сделать копии со спрорных кластеров, оставив на волю пользователя разбираться, какой файл содержит не те данные, то есть будет сделанно следующее:

• файлN1.txt: 56-80-81-99-101-102
• файлN5.txt: 40-41-57-103-104, причём кластер 103 будет копией со 101, и кластер 104 будет копией со 102.
• см. рис. B1.

Вторая возможная ошибка - неверный размер файла. Так как размер определяет то место в последнем кластере вплоть до которого будут читаться данные, то размер больше суммарного объёма кластеров (или меньше объёма всех кластеров - 1) говорит о невозможности определить точку окончания чтения данных. Программа исправления может лишь поставить этот размер по суммарному объёму всех кластеров:

• см. рис. B3;
• см. рис. B4.

Внимание. Если DOS-версию программы-исправления логических ошибок запустить на диск lFAT (элФАТ, эта таблица фактически используется в Windows, она рассмотрена в книге Фигурнова "Полная версия"), то есть содержащий длинные имена, то программа может воспринять все нестандартные имена как ошибочные и "исправить".

Вопрос: Зачем в курс включено название утилиты исправления ошибок Scandisk?

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

Исправление логических ошибок.

Рис.7а. Более полный перечень ошибок диска FAT.

Рис.7б. Дополнение ошибок для диска FAT32.

Первый пример опасности ошибки даты файла.

Второй пример. На серверах Win2000 администратор сервера по-умолчанию имеет привилегии дешифровки документов пользователей. Но только в диапазоне от момента установки сервера. Если кто-то при установке сервера поставит дату вперёд (некоторые странные сис. админы так поступают, чтобы не платить за лицензирование Win2000 Terminal Server, а после подключений с клиентской машины выставляют дату назад), то попытка администратором дешифровать документы к успеху не приведёт, так как его сертификат дешифровки начинает действовать в будущем!

Идея простейшей оптимизации

Эта идея изначально состоит из двух частей:

Часть I. Данные из начала диска (первых кластеров) читаются быстрее, чем из последних кластеров диска. Так на жёстком диске 4 Gb данные из первых кластеров читались на 15% быстрее чем из конца. В отношении дисков в 400Gb эта разница будет ещё больше. Соответствено операционная система должна бы изначально стремится записывать данные в начало, но это не так, если пишущая головка стоит уже в конце диска, то перемещать её в начало для записи туда долго, проще произвести запись в ближайший свободный кластер от текущего положения головки.

Скорость доступа к жёсткому диску можно посмотреть из Nero. Эксперимент правда не очень чистый, потому что сравнивается не один кластер из самого начала HDD с одним кластером из самого конца HDD, а целый логический диск.

Часть II. Активная работа пользователя с файлами приводит к тому, что даже имеющийся файл, зачастую оказывается записан разными частями.

Пример. ПРИЧИНЫ произвольного разброса частей файлов по диску

Пусть у нас примитивный жёсткий диск который состоит всего из восьми частей ("кластеров").

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

Рис. 4.1. Начало работы (о - основной)

Действие 4.2. Теперь пользователь открыл файл и серьёзно его дополнил. В редакторе он поставил признак "сохранять резервную копию" (см. "БукварьПК" динамическая копия). Нажал "сохранить" в результате старый файл, хранившийся на диске в первом кластере не удалился, он переименовался в файл "Копия", а новый файл будет записан в ближайшие свободные кластеры:

Рис. 4.2. Первое сохранение (к - копия)

Действие 4.3. Потом пользователь ещё раз дополнил файл и нажал сохранить. Старая копия при этом будет удалена:

Рис. 4.3.

Действие 4.4. Старый основной файл будет переименован в копию.

Рис. 4.4.

Где после этого будет находится пишущая головка?

Точно не известно. Если не включено кэширование записи на диск, то она скорее всего будет в самом начале диска исправлять таблицу FAT.

Но скорее всего кзширование записи включено (запущен smartdrv.exe или его эквивалент). В таком случае исправление таблицы FAT будет отложено на потом, а пишущая головка будет находится после IV кластера (потому что в результате действия 4.3 последним дописывался кусок о3), она даже чуть чуть может залететь за начало кластера V (из за инерционных явлений). В таком случае новый основной файл может быть записан системой в виде:

Рис. 4.5.

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

Пример. РЕЗУЛЬТАТЫ записи файла разными частями

Рис. 4.11.

Посчитаем действия на чтение файла с диска

Считывание, конечно, происходит дольше, чем переход, но непроизводительные действия приводят к заметному замедлению работы.

Пример. ПРОЦЕСС дефрагментации (оптимизации доступа)

Пусть рассматривается всё та же простейшая ситуация показанная на рисунке 4.11 (на практике будет сложнее, так как файлов будет множество). Компьютеру нужно разложить этот файл в последовательности от о1 до о7.

Он может

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

Первым действием будет, очевидно, освобождение I кластера:

Рис. 4.21.

Затем исполдьзование первого кластера:

Рис. 4.22.

Использование второго кластера:

Рис. 4.23.

Использование третьего кластера:

Рис. 4.24.

Освобождение четвёртого кластера:

Рис. 4.25.

Использование четвёртого кластера:

Рис. 4.26.

Использование седьмого кластера:

Рис. 4.27.

Выводы. Процесс оптимизации это длительный процесс. Скорость его выполнения зависит от следующих факторов:

• насколько много частей файла уже находятся в тех кластерах, в которых они должны оказаться;
• объёма оперативной памяти (чем больший объём файла удасться считывать в память, тем меньше непроизводительных действий по временной записи частей файла в конец жёсткого диска нужно будет выполнить);
• количества свободного места на диске, чем больше, тем меньше нужно будет временно передвигать неправильно расположенные части файлов в конец диска.

Практика дефрагментации

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

Открыть "Мой компьютер". Правой мышью по нужному диску. Свойства. Карточка сервис. Выполнить дефрагментацию....

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

Отключение электроэнергии (или зависание) во время процесса дефрагментации может привести к массовым потерям документов и прочих файлов.

Самый надёжный способ дефрагментации: копирование файла на чистый диск (история про телеоператора):

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

Простейший способ выяснить, какая файловая система используется на диске.

Рис. FAT.

Рис. FAT32.