1 Файловые системы. Физическое размещение файлов на диске. Соответствие между логической организацией файлов и физической организацией размещения данных на диске Записи являются логической единицей доступа к файлу, в то время как единицами ввода-вывода при сохранении данных на носителе являются блоки. Для выполнения физических операций с файлами необходимо реорганизовывать записи в блоки. На физическом уровне все пространство диска разбивается на области по 512 байт (операция форматирования диска), которые называются секторами. При форматировании между секторами выделяется физическое пространство – разделители. Дисковое пространство под размещение файлов выделяется так называемыми блоками (кластерами). Каждый блок (кластер) содержит целое число секторов, кратное степени двойки. Конкретный размер блока зависит от типа файловой системы ОС, размерности внутреннего обмена и физического объема диска.

2 Файловые системы. Физическое размещение файлов на диске. Например, для файловых систем FAT32 и NTFS, используемых ОС Windows2000 и Windows XP, применяется следующее разбиение диска на кластеры (для стандартных дисков сектор = 512 байт). ТОМ (диск)Количество секторов в кластере (блоке) Размер кластера (блока) 512 Мб1512 байт 512 Мб – 1 Гб21 Кб 1 Гб – 2 Гб42 Кб 2 Гб – 4 Гб84 Кб 4 Гб – 8 Гб168 Кб 8 Гб – 16 Гб3216 Кб 16 Гб – 32 Гб6432 Кб Свыше 32 Гб12864 Кб Соответствие между логической организацией файлов и физической организацией размещения данных на диске

3 Файловые системы. Физическое размещение файлов на диске. Соответствие между логической организацией файлов и физической организацией размещения данных на диске Поскольку, как правило, размер записи не совпадает с размером блока (кластера), НЕОБХОДИМО применять различные способы группировки логических записей в физические блоки. 1. Фиксированное группирование R1R2R3R4R5 Физические разделители Блок 1 Блок 2Блок 3 Используются записи фиксированной длины и в блоке хранится целое количество записей (какой тип файла?). Может появиться неиспользуемое пространство (внутренняя фрагментация).

4 Файловые системы. Физическое размещение файлов на диске. 2. Сцепленное группирование переменной длины R1R2R3R4R6R6 Физические разделители Блок 1 Блок 2Блок 3 Используются записи переменной длины (какие типы файла?). Упаковка происходит без фрагментации. Некоторые записи как бы «сцепляют» блоки. При этом запись должна содержать информацию о том, является ли она целой записью или частью уже размещенной в другом блоке записи. Таким образом, появляется необходимость хранения внутри собственно данных дополнительной служебной информации. R3R3R5R5R6R6 Сцепление записей

5 Файловые системы. Физическое размещение файлов на диске. 3. Группирование переменной длины без сцепления R1R2R3R4R4 Физические разделители Блок 1 Блок 2Блок 3 Используются записи переменной длины, но сцепления не происходит. При этом в большинстве блоков появляется внутренняя фрагментация (неиспользуемое пространство). Приведенные рисунки иллюстрируют случай, когда файл размещается на диске в виде последовательности непрерывных блоков. На самом деле существуют еще два способа размещения файлов: связанные блоки и индексированные блоки.

6 Файловые системы. Физическое размещение файлов на диске. Любая файловая система (ФС), как важнейшая часть ОС, решает две взаимосвязанные задачи: 1.Управление размещением файлов. 2.Управление свободным пространством на диске. Для решения обеих задач существуют различные подходы и механизмы, использование которых обусловлено особенностями ОС и спецификой конкретных ситуаций.

7 Файловые системы. Управление размещением файлов на диске. В общем смысле существует две стратегии размещения: - предварительное размещение, - динамическое размещение по мере необходимости. В ряде случаев максимальное пространство, необходимое для размещения того или иного файла, может быть предварительно оценено (компиляция исполняемых программ, получение файлов сводных данных и т.п.). Такая стратегия достаточно эффективна для организации управления распределенным пространством. Однако чаще всего предварительную оценку необходимого объема памяти для размещения файла невозможно сделать в принципе. Поэтому распределение дискового пространства динамическим способом путем выделения некоторого количества кластеров по мере необходимости является по сути единственно возможным. 1. Стратегии размещения 1.1. Предварительное размещение 1.2. Динамическое размещение по мере необходимости

8 Файловые системы. Управление размещением файлов на диске. Увеличение объемов дисковых накопителей, а также размеров обрабатываемых файлов обусловило переход от понятия «кластер», понимаемого как минимальный объем единовременного обмена данными в ПК (запись/чтение/передача), к более общему понятию «ПОРЦИЯ». Порцией называется непрерывный участок дискового пространства, состоящий из одного или нескольких кластеров (блоков). Конкретный размер порции определяется как компромисс между эффективной работой с одним файлом и общей эффективностью работы файловой системы.

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

10 Файловые системы. Управление размещением файлов на диске. Анализ перечисленных условий позволяет определить два наиболее оптимальных варианта распределения пространства порциями: Большие непрерывные порции переменной длины: (+) Повышение производительности; (+) Минимизация фрагментации; (+) Таблицы размещения файлов небольшие; (-) Трудности в повторном использовании выделенного пространства. Порция = блоку (кластеру), т.е фиксированные порции небольшого размера: (+) Обеспечение большей гибкости в распределении пространства; (-) Таблицы размещения файлов большие и сложно структурируемые; (-) Непрерывность пространства диска фактически отсутствует; (+) Порции выделяются по мере необходимости, что позволяет эффективно организовывать операции по изменению файлов. 2. Варианты размещения порциями 2.1. Непрерывные порции большого размера переменной длины 2.2. Фиксированные порции небольшого размера (порция = блоку)

11 Файловые системы. Управление размещением файлов на диске. Любой из рассмотренных вариантов с той или иной степенью эффективности совместим как со стратегией предварительного, так динамического размещения файлов. 2. Варианты 1. Стратегии 2.1. Непрерывные порции большого размера переменной длины 2.2. Фиксированные порции небольшого размера 1.1. Стратегия предварительного размещения Файл размещается предварительно как непрерывная группа блоков (порция). Необходимость в таблице размещения файлов минимизируется: нужно зафиксировать первый блок и общее количество выделенных блоков в порции. Все порции (кластеры) размещаются одновременно, но не всегда непрерывным участком. Таблица размещения файла имеет фиксированный размер и содержит адреса всех выделенных блоков (кластеров) Стратегия динамического размещения Непрерывные порции переменного размера привносят значительную фрагментацию свободного пространства. Таблица размещения файлов незначительно усложняется. Фрагментации нет, поскольку пространство выделяется по мере необходимости блоками, однако увеличивается размер и усложняется структура таблицы размещения файлов. ?

12 Файловые системы. Управление размещением файлов на диске. Наиболее существенным ограничением, влияющим на общую эффективность работы файловой системы, является фрагментация. Для минимизации фрагментации в файловых системах используются три основных способа: Первый подходящий. Выбор первой неиспользуемой непрерывной группы порций (блоков) подходящего размера из списка свободных блоков. Наилучший подходящий. Выбор наименьшей неиспользуемой группы порций (блоков), размер которой достаточен. Ближайший подходящий. Выбор неиспользуемой группы порций (блоков) подходящего размера, которая ближе всего (в смысле физических адресов) находится к последнему размещенному файлу.

13 Файловые системы. Управление размещением файлов на диске. В реальных файловых системах используется три метода размещения пространства, основанных на сочетании преимуществ описанных стратегий и вариантов размещения. Методы размещения Метод связанных блоков (цепочечный) НепрерывныйМетод индексированных блоков Наиболее эффективен: Стратегия Вариант 2.1. Наиболее эффективен: Стратегия Вариант 2.2. Одинаково эффективен: Стратегия Вариант 2.1. Стратегия Вариант 2.2.

14 Файловые системы. Управление размещением файлов на диске. НепрерывныйЦепочечныйИндексированный Предварительное размещение НеобходимоВозможно Фиксированный или переменный размер порций ПеременныйФиксированные блоки Переменный Размер порцийБольшойМалый Средний Частота размещений Одинарное размещение ЛюбаяВысокаяНизкая Время размещения СреднееДлительноеКороткоеСреднее Размер таблицы размещения файлов Одна запись БольшойСредний

15 Файловые системы. Управление размещением файлов на диске Имя файлаНачальный блок Количество блоков File A23 File B95 File C188 File D263 Непрерывный метод. Создаваемому файлу выделяется отдельное непрерывное пространство (Стратегия Вариант 2.1.) Каждая запись таблицы размещения файлов состоит из двух числовых полей: (1) номер начального физического блока; (2) количество размещенных блоков. Непрерывность наилучшим образом подходит для размещения последовательных файлов, поскольку допускает одновременную обработку большого числа блоков.

16 Файловые системы. Управление размещением файлов на диске Имя файлаНачальный блок Количество блоков File A03 File B35 File C88 File D163 Непрерывный метод. Основная проблема – внешняя фрагментация, которая усложняет поиск непрерывных порций подходящего размера. Для этого необходимо выполнять упаковку информации с корректным изменением таблицы размещения файлов.

17 Файловые системы. Управление размещением файлов на диске Имя файлаНачальный блок Количество блоков File A23 File B95 Метод связанных блоков (цепочечный). Размещение производится по одному блоку, каждый предыдущий блок содержит указатель (индекс) на последующий блок (преимущественно используется при Стратегии Вариант 2.2.) Каждая запись таблицы размещения файлов состоит из двух числовых полей: (1) номер начального физического блока; (2) количество размещенных блоков. При необходимости дополнительного выделения памяти под файл в цепочку добавляется очередной блок Уже занятые блоки

18 Файловые системы. Управление размещением файлов на диске Имя файлаНачальный блок Количество блоков File A23 File B95 Метод связанных блоков (цепочечный). Внешняя фрагментация отсутствует, поскольку блоки выделяются по одному. Наилучшим образом данный метод поддерживает размещение последовательных файлов. Ключевыми недостатками являются: - Невозможность одновременного доступа к нескольким блокам; - Потеря «однородности» информации (каждый блок помимо собственной информации файла резервирует место и хранит служебную информацию о связях блоков). ОС, поддерживающие данный метод, имеют служебные процедуры уплотнения (сжатия) Уже занятые блоки

19 Файловые системы. Управление размещением файлов на диске Имя файлаНачальный блок Количество блоков File A23 File B255 Метод связанных блоков (цепочечный) Уже занятые блоки После сжатия большинство файлов размещаются в непрерывные цепочки связанных блоков.

20 Файловые системы. Управление размещением файлов на диске Имя файлаИндексный блок File A29 File B30 Решает некоторые проблемы непрерывного и цепочечного методов. Прежде всего, данный метод в рамках стратегии 1.2. достаточно эффективно оба варианта размещения: фиксированными малыми и непрерывными переменными порциями. (варианты 2.1. и 2.2) Метод индексированных блоков. При выделении фиксированными малыми порциями (блоками) фрагментации нет. В индексный блок файла помещаются указатели на блоки, выделенные под размещения файла. Таблица размещения также проста – каждому файлу соответствует номер его индексного блока. По мере необходимости файлу может выделен дополнительное пространство в виде нескольких доступных блоков.

21 Файловые системы. Управление размещением файлов на диске Имя файлаИндексный блок File A29 File B Метод индексированных блоков При реализации варианта выделения пространства непрерывными порциями переменной длины повышается возможность одновременного доступа к нескольким блокам в рамках одной порции. Индексный блок содержит указатель на первый блок порции и ее длину. Таблица размещения файлов не усложняется.

22 Файловые системы. Управление размещением файлов на диске. Метод индексированных блоков наиболее универсальный, поскольку позволяет достаточно эффективно распределять пространство диска в условиях Стратегии динамического размещения при обоих возможных вариантах: фиксированные блоки и непрерывные переменные порции. Индексированный метод поддерживает как последовательный, так и прямой доступ к файлам и, поэтому, является наиболее популярным методом файлового размещения и реализован во всех современных ОС.

23 Файловые системы. Управление размещением файлов на диске. В реальных файловых системах используется три метода размещения пространства, основанных на сочетании преимуществ описанных стратегий и вариантов размещения. Методы размещения Метод связанных блоков (цепочечный) НепрерывныйМетод индексированных блоков Наиболее эффективен: Стратегия Вариант 2.1. Наиболее эффективен: Стратегия Вариант 2.2. Одинаково эффективен: Стратегия Вариант 2.1. Стратегия Вариант 2.2.

24 Файловые системы. Управление свободным пространством на диске. Так же, как требуется управление пространством, выделяемым файлам, любой файловой системе необходимо осуществлять управление свободным (незанятым в текущий момент) пространством диска. Применяя любую из описанных технологий размещения файлов, ОС должна владеть оперативной информацией о том, какие блоки на диске доступны. Для этого, наряду с таблицей размещения файлов, необходима общая таблица (карта) дискового пространства. Существуют четыре основных модели реализации такой информации, которые наиболее эффективно работают в условиях того или иного варианта размещения: - Битовые таблицы; - Цепочки свободных порций; - Индексирование свободного пространства; - Список свободных блоков.

25 Файловые системы. Управление свободным пространством на диске. Битовые таблицы. Все пространство диска, изначально разбитое на физические блоки, соотносится с одномерным массивом, элементами которого являются биты: «0» - соответствует свободному блоку, «1» - занятому. Преимущества: - Простота поиска как отдельного свободного блока, так и непрерывной группы свободных блоков (порции); - Наименьший размер самой таблицы из всех возможных ее представлений. Объем памяти для хранения битовой таблицы размещения вычисляется по формуле: Размер диска в байтах 8 х размер блока ФС Чем меньше размер блока и больше объем диска, тем внушительнее размер памяти, необходимый для хранения битовой таблицы. Например, для диска 16 Гб с размером блока 16 Кб битовая таблица займет: 16х2 10 х2 10 х210 / 8х16х2 10 = 128х2 10 = 128 Кб. Для террабайтового диска (1024 Гб) и размера блока 64Кб – размер битовой таблицы – уже 2 Мб. А если размер блока ФС равен физическому сектору?

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

27 Файловые системы. Управление свободным пространством на диске. Индексирование свободного пространства. При индексировании свободное пространство диска рассматривается как индексированный файл. Каждая свободная порция переменной длины имеет уникальный элемент (индекс) в индексной таблице, по которому осуществляется доступ. Данный подход обеспечивает эффективную поддержку всех методов размещения файлов. Список свободных блоков. Каждому блоку диска присваивается порядковый номер, а список номеров всех свободных блоков содержится в зарезервированной области на диске. Преимуществом данного способа является однозначная идентификация (по уникальному номеру) всех свободных блоков, что позволяет эффективно поддерживать цепочечный метод размещения файлов. Однако при таком подходе, в зависимости от размера диска, для хранения порядкового номера одного блока необходимо 24 или 32 бит. Т.е. размер списка свободных блоков получается значительно большим, чем битовая таблица размещения, что, очевидно, не дает возможности поместить весь список свободных блоков в основную память целиком.

28 Файловые системы. Управление свободным пространством на диске. Однако существуют модели достаточно эффективного использования подхода «список номеров свободных блоков», которые базируются на помещении в основную память только некоторой части списка и ее динамического изменения по мере необходимости. Модель «СТЭК». Список номеров свободных блоков организуется в оперативной памяти по принципу стакана: «последний заходит – первый выходит». Первые несколько тысяч элементов списка сразу же наполняют стэк. Блок с данным номером предоставляется для размещения Блок с данным номером возвращается в стэк после освобождения пространства Процесс обмена между стэком в ОП и списком на диске происходит только тогда, когда стэк опустошается (все блоки с номерами, помещенными до этого в стэк распределены), либо переполняется (освобождено блоков больше, чем может быть помещено в стэк номеров).

29 Файловые системы. Управление свободным пространством на диске. При организации моделей «Стэк» и «Очередь» обращения к диску минимизируются (при средней интенсивности размещения, корректировки и удаления файлов), что повышает производительность. Модель «Очередь». Первый заходит – первый выходит. Блок с данным номером предоставляется для размещения Блок с данным номером возвращается в очередь после освобождения пространства Процесс обмена между очередью в ОП и списком на диске происходит аналогично стэковой модели: когда очередь опустошается (все блоки с номерами, помещенными до этого в ОП распределены), либо переполняется (освобождено блоков больше, чем может быть помещено в очередь номеров).

30 Файловые системы. FAT-32 Данная ФС разработана для ОС Windows-95 и поддерживается всеми последующими ОС семейства Windows, включая Windows ХР. FAT-32 предусматривает следующую организацию дискового пространства: Область размещения файлов Главная запись загрузки Таблица разбиения диска ( битовая таблица или список номеров блоков) Запись текущей загрузки Таблица размещения файлов Корневой каталог Таблица размещения файлов (ТРФ) представляет собой БД, связывающую кластеры дискового пространства с файлами. Первые два элемента (записи) ТРФ содержат служебную информацию о самой ТРФ. Начиная с третьей записи, содержится информация о выделении кластеров под размещение файлов. Существуют зарезервированные значения элементов, показывающие: свободен ли кластер, содержит ли кластер сектора с физическими дефектами, является ли кластер последним из выделенной под файл группы кластеров. Для любого из выделенных под файл кластеров (кроме последнего) содержится ссылка на следующий выделенный кластер. Таким образом, в FAT-32 реализуется метод связанных блоков (цепочечный метод) распределения физического пространства диска.

31 Файловые системы. FAT-32 Каждый каталог (включая корневой) является БД, записи которой состоят из 8 полей: Смещение СодержаниеИмя файла Расши- рение АтрибутЗарезервиро- ваны, используются только в особых случаях ВремяДатаНачальный кластер Размер файла Размер8 байт3 байта 1 байт2 байта 4 байта Размер записи – 32 байта При запросе файла ОС просматривает запись каталога для данного файла для поиска начального кластера. Затем идет обращение к ТРФ к элементу, соответствующему данному кластеру и производятся поиск и восстановление всей цепочки, организованной при размещении файла. В FAT-32 файлам выделяется целое число кластеров, поэтому при размещении большого количества небольших файлов возникает внутренняя фрагментация. Поскольку в настоящее время FAT-32 работает с большими дисками, количество кластеров в которых существенно возросло, для указания начального кластера (а также, если используются длинные имена файлов) выделяются дополнительные байты из резервной области (12-21).

32 Файловые системы. NTFS Файловая система NTFS разработана специально для ОС Windows NT, хотя Windows NT поддерживает и FAT-32. Ключевые возможности NTFS: Способность восстановления данных В случае сбоев системы и работы физических дисков NTFS способна реструктурировать дисковые тома и вернуть их к согласованному состоянию. Для этого используется избыточное хранение критических данных файловой системы. Безопасность Используется объектная модель, при которой каждый открытый файл реализуется как файловый объект со специальным параметром (дескриптором), определяющим свойства безопасности. Диски и файлы больших размеров NTFS более эффективно поддерживает работу с большими дисками и файлами, нежели любая другая ФС.

33 Файловые системы. NTFS Ключевые возможности NTFS: Множественные потоки данных Содержимое любого файла рассматривается как поток байтов. В NTFS можно определить несколько потоков данных для одного файла (многонитиевость). Файл можно разделить как минимум на две составляющие: собственно данные файла и служебную информацию о файле (характеристики доступа, даты создания и модификации, размер и т.д.). NTFS рассматривает эти две компоненты как два потока данных и организует параллельную обработку обоих потоков. Это дает возможность применять Windows NT при работе с удаленными системами Macintosh для хранения и передачи файлов. Обобщенная индексация NTFS связывает с каждым файлом набор атрибутов (характеристик, полей), который является записью специализированной реляционной БД. Поэтому файлы могут быть проиндексированы по любому атрибуту (модель индексированного файла).

34 Файловые системы. NTFS Минимальной единицей размещения в NTFS является кластер, ФС не распознает физические сектора, поэтому NTFS без проблем поддерживает работу нестандартных дисков (у которых сектор 512 байт). Кластеры выделяются под размещение и хранение изменений файлов по мере необходимости целым количеством. При этом допускается фрагментация – кластеры необязательно должны образовывать непрерывную порцию. Основной метод размещения файлов в NTFS – метод индексированных блоков. Данный метод позволяет наиболее эффективно работать с большими и малыми файлами, поскольку ФС отслеживает путем индексирования каждый кластер диска. Максимальный размер файла, поддерживаемый NTFS, составляет 2 32 байт.

35 Файловые системы. NTFS Том NTFS. Файловая система использует концепцию «тома». Том – логический раздел диска, состоящий из некоторого количества кластеров и используемый ФС для распределения дискового пространства. Том состоит из служебной информации ФС, набора файлов и перераспределенного пространства для размещения новых файлов. Том может занимать как весь диск, так и его часть. Максимальный размер тома – 2 64 байт. Схема тома NTFS. Каждый элемент тома представляет собой файл с определенным набором свойств (атрибутов). Даже данные, хранящиеся в том или ином файле являются его свойством (атрибутом). При таком подходе достаточно сравнительно небольшого числа функций общего назначения для организации и управления файловой системой. Область размещения файлов Загрузочный сектор тома Главная файловая таблица Системные файлы

36 Файловые системы. NTFS Область размещения файлов Загрузочный сектор тома Главная файловая таблица (Master File Table) Системные файлы Занимает несколько физических секторов (до 16) и содержит информацию о схеме тома и структурах файловой системы, начальную загрузочную запись и код загрузки. MFT – содержит информацию обо всех файлах и каталогах (которые рассматриваются как файлы определенной структуры) этого тома, а также сведения о свободном пространстве на данном томе. MFT – это БД, состоящая из записей переменной длины, каждая из которых описывает файл или каталог, включая и саму MFT, которая рассматривается как файл. Если размер файла позволяет, то он весь вместе содержимым полностью помещается в запись MFT. Иначе запись MFT содержит индексный кластер, в котором помещаются указатели на кластеры, распределенные под файл в области размещения файлов, т.е. реализуется метод индексированных блоков.

37 Файловые системы. NTFS Структура записи MFT Тип атрибутаОписание Стандартная информация Включает атрибуты доступа (чтение, запись и т.п.); временные метки: время создания и последней модификации файла; количество каталогов, указывающих на файл (счетчик связей) Список атрибутов Список атрибутов, включая данные (содержимое) файла Имя файла Файл или каталог имеет одно или несколько имен Дескриптор безопасности Определяет владельца файла и пользователей, которым разрешен доступ к файлу Данные Содержимое файла. Файл содержит один неименованный атрибут данных по умолчанию (если файл полностью помещается в одну запись MFT и может иметь один или несколько именованных атрибутов данных, если файл размещается в области данных. Корневой индекс Используется для реализации каталогов Размещение индекса Используется для реализации каталогов Информация о томе Включает информацию, относящуюся к тому, например, версия, имя и размер тома Битовая карта Карта, предоставляющая указатели на записи, используемые MFT и каталогами.

38 Файловые системы. NTFS