1 Файловые системы Системное и прикладное программное обеспечение Малышенко Владислав Викторович

2 Содержание 1. Файлы 2. Каталоги 3. Реализация файловой системы 1. Структура файловой системы 2. Реализация файлов 3. Реализация каталогов 4. Примеры файловых систем 1. Файловые системы CD-ROM 2. Файловая система СР/М 3. Файловая система MS-DOS 4. Файловая система Windows Файловая система UNIXV7

3 Файловые системы. Требования 1. Устройства должны позволять хранить очень большие объемы данных; 2. Информация должна сохраняться после прекращения работы процесса, использующего ее; 3. Несколько процессов должны иметь возможность получения одновременного доступа к информации.

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

5 Файловые системы Файлами управляет операционная система. Важными пунктами устройства операционной системы: Структура, именование, использование, защита, реализация и доступ к файлам. Часть операционной системы, работающая с файлами, называется файловой системой.

6 Файлы. Именование файлов. Файлы относятся к абстрактному механизму. При создании файла процесс дает файлу имя. Все современные операционные системы поддерживают использование в качестве имен файлов 8-символьные текстовые строки. Многие файловые системы поддерживают имена файлов длиной до 255 символов. В некоторых файловых системах различаются прописные и строчные символы. Во многих операционных системах имя файла может состоять из двух частей, разделенных точкой, например prog.c. Часть имени файла после точки называется расширением файла и может содержать от 1 до 8 символов и обычно означает тип файла.

7 Некоторые типичные расширения файлов РасширениеЗначение file.bakРезервная копия файла file.cИсходный текст программы на С file.gifИзображение формата GIF file.hipФайл справки file.htmlДокумент в формате HTML (web-страница) file.jpgНеподвижное изображение стандарта JPEG file.mp3Музыка в формате MPEG-1 уровень 3 file.mpgФильм в формате MPEG file.оОбъектный файл (еще не скомпонованный выходной файл компилятора) file.pdfДокумент формата PDF (программы Adobe Acrobat) file.psДокумент формата PostScript file.texВходной файл для программы форматирования ТЕХ file.txtТекстовый файл общего назначения file.zipАрхив, сжатый с помощью алгоритма Зива-Лемпеля

8 Файлы. Именование файлов. Расширение файлов. В некоторых системах расширения файлов являются просто соглашениями, и операционная система не принуждает пользователя их строго придерживаться. Система Windows, напротив, назначает каждому расширению определенное значение. Пользователи (или процессы) могут регистрировать расширения в операционной системе, указывая программу, «владеющую» данным расширением.

9 Структура файлов. Способы структурирования: a. Файл представляет собой неструктурированную последовательность байтов. b. Файл представляет собой последовательность записей фиксированной длины, каждая со своей внутренней структурой. c. Файл представляет собой дерево записей, не обязательно одной и той же длины.

10 Структура файлов a. последовательность байтов; b. последовательность записей; c. дерево. 1 байт a 1 запись b Червь МуравейЛисаСвинья КотКороваСобака КозаЛевСова ПониКрыса КурицаИбисЯгненок c

11 Типы файлов В системах UNIX и Windows проводится различие между регулярными файлами и каталогами. К регулярным файлам относятся все файлы, содержащие информацию пользователя. Каталоги - это системные файлы, обеспечивающие поддержку структуры файловой системы. В системе UNIX также различаются символьные и блочные специальные файлы. Символьные специальные файлы имеют отношение к вводу-выводу и используются для моделирования последовательных устройств ввода-вывода, таких как терминалы, принтеры и сети. Блочные специальные файлы используются для моделирования дисков.

12 Типы файлов (2) Регулярные файлы в основном являются либо ASCII-файлами, либо двоичными файлами. ASCII-файлы – это файлы, состоящие из текстовых строк. Файлы называются двоичными, если они не являются ASCII-файлами.

13 Типы файлов (3)

14 Типы файлов (4) Все операционные системы должны распознавать по крайней мере один тип файлов - свои собственные исполняемые файлы, но некоторые операционные системы распознают и другие типы файлов.

15 Доступ к файлам В старых операционных системах предоставлялся только один тип доступа к файлам - произвольный доступ. В этих системах процесс мог читать байты или записи файла только по порядку от начала к концу. Такой доступ к файлам появился, когда дисков еще не было и компьютеры оснащались магнитофонами. С появлением дисков стало возможным читать байты или записи файла в произвольном порядке или получать доступ к записям по ключу. Файлы, байты которых могут быть прочитаны в произвольном порядке, называются файлами последовательного доступа. Такие файлы используются многими приложениями.

16 Доступ к файлам Файлы произвольного доступа очень важны для многих приложений, например для баз данных. Для указания места начала чтения используются два метода. В первом случае каждая операция read задает позицию в файле. При втором способе используется специальная операция поиска seek, устанавливающая текущую позицию. После выполнения операции seek файл может читаться последовательно с текущей позиции. В некоторых старых операционных системах способ доступа к файлу указывался в момент создания файла. В современных операционных системах такого различия не проводится.

17 Атрибуты файла У каждого файла есть имя и данные. Все операционные системы связывают с каждым файлом также и другую информацию, например дату и время создания файла, а также его размер – дополнительные сведения – атрибуты файла. Список атрибутов значительно варьируется от системы к системе.

18 Атрибуты файла 1. Атрибуты защиты файла содержат информацию о том, кто может получить доступ к файлу. 2. Флаги представляют собой биты, управляющие некоторыми специфическими свойствами. 3. Атрибуты длина записи, позиция ключа и длина ключа. 4. Атрибуты даты создания, изменения и доступа к файлу. 5. Текущий размер файла.

19 Атрибуты файла (2)

20 Операции с файлами 1. Create (создание). 2. Delete (удаление). 3. Open (открытие). 4. Close (закрытие). 5. Read (чтение). 6. Write (запись). 7. Append (добавление). 8. Seek (поиск). 9. Get attributes (получение атрибутов). 10. Set attributes (установка атрибутов). 11. Rename (переименование).

21 Каталоги

22 Одноуровневые каталоговые системы Простейшая форма системы каталогов состоит в том, что имеется один каталог, в котором содержатся все файлы. Иногда его называют корневым каталогом, но поскольку он в таких системах единственный, его название не имеет значение. Такая система была весьма распространена на ранних персональных компьютерах, в частности потому, что у них было всего по одному пользователю. Недостаток ?!

23 Одноуровневые каталоговые системы

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

25 Двухуровневая система каталогов

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

27 Иерархические каталоговые системы

28 Имя пути При организации файловой системы в виде дерева каталогов требуется некоторый способ указания файла. Одно и то же имя пути в этих трех операционных системах будет выглядеть следующим образом: Windows \usr\ast\mailbox UNIX /usr/ast/mailbox MULTICS >usr>ast>mailbox Если первой буквой имени пути был разделитель, это означало, независимо от используемого в качестве разделителя символа, что путь абсолютный. Применяется и относительное имя пути. Оно используется вместе с концепцией рабочего каталога (также называемого текущим каталогом).

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

30 Имя пути (3)

31 Операции с каталогами 1. Create. Создать каталог. 2. Delete. Удалить каталог. 3. Opendir. Открыть каталог. 4. Closediг. Закрыть каталог. 5. Readdir. Прочитать следующий элемент открытого каталога. 6. Rename. Переименование каталога. 7. Link. Связывание представляет собой технику, позволяющую файлу появляться сразу в нескольких каталогах. 8. Unlink. Удаление ссылки на файл из каталога.

32 Реализация файловой системы

33 Структура файловой системы Файловые системы хранятся на дисках. Большинство дисков делятся на несколько разделов с независимой файловой системой на каждом разделе. Сектор 0 диска называется главной загрузочной записью (MBR, Master Boot Record) и используется для загрузки компьютера. В конце главной загрузочной записи содержится таблица разделов. В этой таблице хранятся начальные и конечные адреса (номера блоков) каждого раздела. Один из разделов помечен в таблице как активный. При загрузке компьютера BIOS считывает и исполняет MBR-запись, после чего загрузчик в MBR-записи определяет активный раздел диска, считывает его первый блок, называемый загрузочным, и исполняет его. Программа, находящаяся в загрузочном блоке, загружает операционную систему, содержащуюся в этом разделе. Для единообразия каждый дисковый раздел начинается с загрузочного блока, даже если в нем не содержится загружаемой операционной системы.

34 Структура файловой системы (пример)

35 Структура файловой системы Строение раздела диска меняется от системы к системе. Часто файловые системы содержат некоторые общие элементы. Суперблок – содержит ключевые параметры файловой системы и считывается в память при загрузке компьютера или при первом обращении к файловой системе. Следом располагается информация о свободных блоках файловой системы, например в виде битового массива или списка указателей.

36 Реализация файлов.

37 Непрерывные файлы. Простейшей схемой выделения файлам определенных блоков на диске является система, в которой файлы представляют собой непрерывные наборы соседних блоков диска. Тогда на диске, состоящем из блоков по 1 Кбайт, файл размером в 50 Кбайт будет занимать 50 последовательных блоков. При 2-килобайтных блоках такой файл займет 25 соседних блоков.

38 Непрерывные файлы.

39 Непрерывные файлы. У непрерывных файлов есть два существенных преимущества: 1. Такую систему легко реализовать, так как системе, чтобы определить, какие блоки принадлежат тому или иному файлу, нужно следить всего лишь за двумя числами: номером первого блока файла и числом блоков в файле. Зная первый блок файла, любой другой его блок легко получить при помощи простой операции сложения. 2. При работе с непрерывными файлами производительность просто превосходна, так как весь файл может быть прочитан с диска за одну операцию. Требуется только одна операция поиска (для первого блока). После этого более не нужно искать цилиндры и тратить время на ожидания вращения диска, поэтому данные могут считываться с максимальной скоростью, на которую способен диск. Таким образом, непрерывные файлы легко реализуются и обладают высокой производительностью. У непрерывных файлов есть два существенных преимущества: 1. Такую систему легко реализовать; 2. При работе с непрерывными файлами производительность просто превосходна, так как весь файл может быть прочитан с диска за одну операцию.

40 Непрерывные файлы. К сожалению, у такого способа распределения дискового пространства имеется серьезный недостаток: со временем диск становится фрагментированным. По мере удаления файлов диск становится все более «дырявым». Вначале эта фрагментация не представляет проблемы, так как каждый новый файл может быть записан в конец диска, вслед за предыдущим файлом. Однако в конце концов диск заполнится и либо потребуется специальная операция по уплотнению используемого пространства диска, либо надо будет изыскать способ использовать свободное пространство на месте удаленных файлов.

41 Непрерывные файлы. Пример. Пользователь запускает текстовый редактор или текстовой процессор, чтобы создать документ. Первое, что интересует программу, это сколько байтов будет в документе. На этот вопрос следует дать ответ, в противном случае программа не сможет работать. Если пользователь укажет слишком маленькое число, программа может закончиться аварийно, как как свободный участок диска окажется заполнен и будет негде разместить остальную часть файла. Если пользователь попытается обойти эту проблему, задав заведомо большой окончательный размер, например 100 Мбайт, может случиться, что редактор не сможет найти такой большой свободный участок и сообщит, что не может создать файл. Конечно, пользователь может поторговаться и снизить свои требования до 50 Мбайт и т. д. до тех пор, пока не найдется подходящий свободный участок. Тем не менее такая схема вряд ли доставит удовольствие пользователям.

42 Непрерывные файлы. Файловые системы, состоящие из непрерывных файлов, применялись на магнитных дисках много лет назад благодаря их простоте и высокой производительности. И все-таки есть ситуации, в которых непрерывные файлы могут применяться и в самом деле широко используются: на компакт-дисках. Здесь все размеры файлов известны заранее и не могут меняться при последующем использовании файловой системы CD-ROM.

43 Связные списки Второй метод размещения файлов состоит в представлении каждого файла в виде связного списка из блоков диска. Первое слово каждого блока используется как указатель на следующий блок. В остальной части блока хранятся данные. В отличие от систем с непрерывными файлами, такой метод позволяет использовать каждый блок диска. Нет потерь дискового пространства на фрагментацию. Кроме того, в каталоге нужно хранить только адрес первого блока файла. Всю остальную информацию можно найти там. С другой стороны, хотя последовательный доступ к такому файлу несложен, произвольный доступ будет довольно медленным. Чтобы получить доступ к блоку n, операционная система должна сначала прочитать первые n-1 блоков по очереди. Очевидно, такая схема оказывается очень медленной.

44 Связные списки

45 Файловая система FAT Физическая организация FAT

46 Физическая организация FAT Логический раздел FAT состоит из: Загрузочный сектор Основная копия FAT Резервная копия FAT Корневой каталог Область данных

47 Физическая организация FAT Загрузочный сектор (512 байт) FAT 1 FAT 2 (копия) Элементы (указатели) FAT Root directory Data … Кластеры данных 32 бита – одна запись каталога

48 Файловая система FAT FAT поддерживает два типа фалов: Обычный файл; Каталог. Файловая система распределяет память только из области данных, причем использует в качестве минимальной единицы дискового пространства кластер.

49 Файловая система FAT (2) Таблица FAT состоит из массива индексных указателей, количество которых равно количеству кластеров области данных. Индексный указатель может принимать следующие значения: Кластер свободен; Кластер используется файлом и не является последним, содержит номер следующего кластера; Последний кластер файла; Дефектный кластер; Резервный кластер.

50 Файловая система FAT. Разрядность. Существует несколько разновидностей FAT: FAT12 (4096 кластеров) – 16 Мбайт; FAT16 (65536 кластеров) – 512 Мбайт; FAT32 (4 миллиарда кластеров) – 8 Гбайт.

51 Файловая система FAT. Восстановление файлов. При удалении файла из файловой системы FAT в первый байт заносится специальный признак, свидетельствующий о том, что запись свободна. Существует большое количество утилит восстановления удаленных файлов.

52 Файловая система FAT. Резервная копия FAT. Резервная копия FAT всегда синхронизируется с основной копией при любых операциях с файлами, поэтому резервную копию нельзя использовать для отмены ошибочных действий пользователя. Резервная копия полезна в случае выхода из строя основной FAT.

53 Файловая система FAT. Имена файлов. Имена файлов состоят из 12 символов по схеме «8.3». В версии FAT16 для Windows NT использовались имена длиной до 255 символов. В FAT32 у каждого файла для имени длинное и короткое для совместимости со старыми версиями.

54 Файловая система NTFS

55 Физическая организация NTFS. Особенности. Поддержка больших файлов и больших дисков объемом до 2 64 байт; Восстанавливаемость после сбоев и отказов программ и аппаратуры; Высокая скорость операций; Низкий уровень фрагментации; Гибкая структура ФС; Устойчивость к отказам дисковых накопителей; Поддержка длинных символьных имен; Контроль доступа к каталогам и файлам.

56 Структура тома NTFS Основой структуры тома NTFS является главная таблица файлов (Master File Table, MFT). Для каждого файла одна запись в MFT. Размер записи 1, 2 и 4 Кбайт. Файл идентифицируется номером позиции в таблице MFT.

57 Структура тома NTFS Том NTFS состоит из последовательности кластеров. Первый номер кластера называется логическим номером кластера (Logical Cluster Number, LCN) Файл состоит из последовательности кластеров внутри файла. Порядковый номер кластера в файле называется виртуальным номером кластера (Virtual Cluster Number, VCN).

58 Структура тома NTFS Загрузочный сектор … 15 MFT Системный файл 1 Системный файл n Копия MFT Файл N-1 Копия загрузочного блока MFT Файл M Первый отрезок MFT Второй отрезок MFT Третий отрезок MFT

59 Структура тома NTFS

60 Структура файлов NTFS Каждый файл состоит из набора атрибутов: Attribute list (список атрибутов) File name (имя файла) MS-DOS name (имя MS-DOS) Version (версия) Security descriptor (дескриптор безопасности) Volume version (версия тома) Volume name (имя тома) Data (данные) MFT bitmap (битовая карта MFT) Index root (корень индекса) Index allocation (размещение индекса) Standard information (стандартная информация)

61 Структура файлов NTFS. Размер файлов. Небольшие Большие Очень большие Сверхбольшие

62 Структура файлов NTFS. Небольшой файл. SIFNDataSD Записи MFT SI стандартная информация FN имя файла Data данные SD дескриптор безопасности

63 Структура файлов NTFS. Большой файл. SIFN Data VCN 1, VCN 2, VCN 3 LCN 1, LCN 2, LCN 3 k 1, k 2, k 3 SD Записи MFT Отрезокданные 1 Отрезокданные 2 Отрезокданные 3

64 Структура файлов NTFS. Очень большой файл. Записи MFT Отрезокданные 1 Отрезокданные 2 Отрезокданные 3 Отрезокданные m Data VCN 1, VCN 2, VCN m, LCN 1, LCN 2, LCN m k 1, k 2, k m SIALFNSD

65 Структура файлов NTFS. Сверх больший файл. Записи MFT Отрезокданные 1 Отрезокданные 2 Отрезокданные 3 Отрезокданные m Data SIALFNSD Data

66 Каталоги NTFS Каталог представляет собой один вход в таблицу MFT, который содержит атрибут Index root. Индекс содержит список файлов. Индексы позволяют сортировать файлы для ускорения поиска.

67 Каталоги NTFS. Форма хранения списка файлов. Небольшие каталоги Большие каталоги

68 Каталоги NTFS. Небольшие каталоги. SIFN IR SD

69 Каталоги NTFS. Большие каталоги. SIFN IR SD IR IA VCN1, VCN2 LCN1, LCN2 k1, k2 IR IR