16. Файловые системы: файлы, каталоги. Реализация файловой системы: реализация файлов, реализация каталогов. Организация дискового пространства, надежность файловой системы, производительность файловой системы.

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

Файловая система связывает носитель инфы и интерфейс для доступа к файлам. Когда прикладная прога обращается к файлу, она не имеет никакого представления о том, каким образом расположена инфа в конкретном файле, так же, как и на каком физическом типе носителя он записан. Всё, что знает прога — это имя файла, его размер и атрибуты. Эти данные она получает от драйвера файловой системы. Именно файловая система устанавливает, где и как будет записан файл на физическом носителе.

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

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

В широком смысле понятие "файловая система" включает:

Файлы идентифицируются именами. Пользователи дают файлам символьные имена, при этом учитываются ограничения ОС как на используемые символы, так и на длину имени. До недавнего времени эти границы были весьма узкими. Так в популярной файловой системе FAT длина имен ограничивается известной схемой 8 символов - имя, 3 символа - расширение, а в ОС UNIX System V имя не м. содержать более 14 символов. Но пользователю удобнее работать с длинными именами. Поэтому современ файловые сис-мы поддерживают длинные символьные имена файлов. Например, Windows NT в своей новой файловой системе NTFS устанавливает, что имя файла м. содержать до 255 символов, не считая завершающего нулевого символа.

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

Длинные имена поддерживаются не только новыми файловыми системами, но и новыми версиями хорошо известных файловых систем. Напр-р, в ОС Windows 95 используется файловая система VFAT, представляющая собой существенно измененный вариант FAT. Среди многих др усовершенствований 1 из главных «+»VFAT : поддержка длинных имен. Кроме проблемы генерации эквивалентных коротких имен, при реализации нового варианта FAT важной задачей была задача хранения длинных имен при условии, что принципиально метод хранения и структура данных на диске не должны были измениться.

Обычно разные файлы м. иметь одинак символьные имена. В этом случае файл однозначно идентифицируется составным именем, представляющем собой послед-ть символьных имен каталогов. В некотор системах одному и тому же файлу не м.б. дано неск-ко разных имен, а в др такое ограничение отсутствует. В последнем случае ОС присваивает файлу дополнит уникальное имя, так, чтобы м. было установить взаимно-однозначное соответствие между файлом и его уникальным именем. Уникальное имя представляет собой числовой идентификатор и используется прогами ОС (напр-р, № индексного дескриптора в системе UNIX).

Файлы бывают разных типов: обычные файлы, спец файлы, файлы-каталоги.

Обычные файлы подразделяются на текстовые и двоичные. Текстовые файлы состоят из строк символов, представленных в ASCII-коде. Это доки, исходные тексты прог и т.п. Текстовые файлы м. прочитать на экране и распечатать на принтере. Двоичные файлы не use ASCII-коды, они часто имеют слож внутр структуру, напр-р, объектный код проги или архивный файл. Все ОС должны уметь распознавать хотя бы 1 тип файлов - их собственные исполняемые файлы.

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

Каталог - это 1)группа файлов, объединенных пользователем исходя из некотор соображений, 2) файл, содержащий системную инфу о группе файлов, его составляющих. В каталоге содержится список файлов, входящих в него, и устанавливается соответствие между файлами и их хар-ками (атрибутами).

В разных файловых системах м. использоваться в кач-ве атрибутов разные хар-ки, напр-р:

Каталоги м. непосредственно содержать знач-я характеристик файлов, как это сделано в файловой системе MS-DOS, или ссылаться на табл, содержащие эти хар-ки, как это реализовано в ОС UNIX.

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

Интерфейс файловой системы.

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

Для организации хранения инфы на диске user вначале обычно выполняет его форматирование, выделяя на нем место для структур данных, кот описывают состояние файловой системы в целом. Затем  user создает нужную ему структуру каталогов (или директорий). И, наконец, заполняет дисковое пространство  файлами, приписывая их тому или иному каталогу. Т.о,  ОС должна предоставить в распоряжение userа совокупность сервисов традиционно реализованных через системные вызовы, кот обеспечивают:

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

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

Общая структура файловой системы

Система хранения данных на дисках м.б. структурирована в виде уровней.

Нижний уровень - оборудование. Это магнитные диски с подвижными головками - основные устр-ва внеш памяти.

Файловая система имеет дело с логическими блоками, кажд из кот. имеет № (от 0 или 1 до N). Размер этих логических блоков файла совпадает или кратен размеру физич блока диска и м.б. задан равным размеру страницы виртуал памяти, поддерживаемой аппаратурой компа совместно с ОС.

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

                 Рис. 12.1 Блок схема файловой системы

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

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

Методы выделения дискового пространства

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

Выделение непрерывной послед-тью блоков

Простейший способ - хранить кажд файл, как непрерывную послед-ть  блоков диска. При непрерывном расположении файл хар-ся адресом и длиной (в блоках). Файл,  стартующий с блока b, занимает затем блоки b+1, b+2, ... b+n-1.

Эта схема имеет 2 «+».1)ее легко реализовать. 2) она обеспечивает хорошую производительность, т.к. целый файл м. б. считан за 1 дисковую операцию.

Непрерывное выделение useся в ОС IBM/CMS, в ОС RSX-11 (для выполняемых файлов) и в ряде др.

Основная  проблема, вследствие чего этот способ мало распространен  - трудно найти место для нового файла. В процессе эксплуатации  диск представляет собой некотор совокупность свободных и занятых фрагментов. Проблема непрерывного расположения м. рассматриваться как частный случай более общей проблемы выделения n блоков из списка свободных дыр.  Наиболее  распространенные стратегии реш-я этой проблемы - first fit, best fit и worst fit. Т.о,  метод страдает от внеш фрагментации, в зав-ти от размера диска и среднего размера файла,  в большей или меньшей степени.

Кроме того, непрерывное распределение внеш памяти не применимо до тех пор, пока не известен max  размер файла.  Иногда размер выходного файла оценить легко (при копировании). Но чаще это трудно сделать. Если места не хватило, то пользовательская прога м.б. приостановлена, предполагая выделение дополнит места для файла при последующем рестарте. Некотор ОС use модифицированный вариант непрерывного выделения основные блоки файла + резервные блоки. Но с выделением блоков из резерва возникают те же проблемы,  возникает задача выделения непрерывной послед-ти блоков диска теперь уже из совокупности резервных блоков.

Связный список

Метод  распределения блоков в виде связного списка решает основную проблему непрерывного выделения, устраняет внеш фрагментацию.  Кажд файл - связный список блоков диска. Запись в директории содержит указатель на I и последний блоки файла. Кажд блок содержит указатель на след блок.

Рис. Хранение файла в виде связного списка дисковых блоков.

Внеш фрагментация для данного метода отсутствует. Любой свободный блок м.б. use для удовлетворения запроса. Нет необход-ти декларировать размер файла в момент создания. Файл м. неограниченно расти.

Связное выделение имеет неск-ко существенных «-».

1) выборка логически  смежных записей, кот  занимают  физически  несмежные секторы, может  требовать много времени. 

2) низкая надежность.  Наличие дефектного блока в списке приводит к потере инфы в остаточной части файла и, к потере дискового пространства отведенного под этот файл.

3) для указателя на след блок внутри блока нужно выделить место. Емкость блока, традиционно являющаяся степенью двойки, перестает быть степенью двойки, т.к. указатель отбирает неск-ко байтов.

Поэтому метод связного списка обычно не use в чистом виде.

Связный список с использованием индекса

«-» предыдущего способа м.б. устранены путем изъятия указателя из кажд дискового блока и помещения его в индексную табл в памяти, кот наз-ся FAT (file allocation table).  Этой схемы придерживаются многие ОС (MS-DOS, OS/2, MS Windows и др.)

Рис. Метод связного списка, с использованием табл в оператив памяти

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

Минусом этой схемы м.б. необходимость поддержки в памяти этой довольно большой табл.

Индексные узлы

IV и последний метод выяснения принадлежности блока к файлу - связать с кажд файлом маленькую табл, называемую индексным узлом (i-node), кот  перечисляет атрибуты и дисковые адреса блоков файла (см. рис 12.4). 

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

Индексирование поддерживает прямой доступ к файлу, без ущерба от внеш фрагментации.

             Рис.   Структура индексного узла

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

Эту схему use Unix (а также  файловые системы HPFS, NTFS и др.). Такой подход позволяет при фиксированном, отн-но небольшом размере индексного узла,  поддерживать работу с файлами, размер кот м. меняться от неск-ких байт до неск-ких гигабайт.  Для маленьких файлов useся только прямая адресация, обеспечивающая max производительность.

Надежность файловой системы.

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

Целостность файловой системы.

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

В соврем ОС предусмотрены меры, кот позволяют свести к минимуму ущерб от порчи файловой сис-мы и, затем, восстановить ее целостность.

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

Др средством поддержки целостности явл-ся способ реализации файловой операции в виде транзакции, примерно как, как это делается в СУБД.  Послед-ть действий с объектами во время файловой операции протоколируется,  и, если произошел останов сис-мы, то, имея в наличии протокол, м. осуществить откат сис-мы назад в исходное целостное состояние, в кот она пребывала до начала операции. Такого рода журналирование реализовано в NTFS.

Если же нарушение все же произошло, то для устранения проблемы несовместимости м. прибегнуть к утилитам (fsck, chkdsk, scandisk и др.), кот  проверяют целостность файловой сис-мы. Они м. запускаться после загрузки или после сбоя и осуществляют многократное сканирование разнообразных  структур данных файловой сис-мы в поисках противоречий.

Управление плохими блоками.

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

1)  хранить список плохих  блоков в контроллере диска. Когда контроллер инициализируется, он читает плохие блоки и замещает дефектный  блок  резервным, помечая отображение в списке плохих блоков. Все реальные запросы будут идти к  резервному блоку.  При этом механизм подъемника (наиб распространенный механизм обработки запросов к блокам диска) будет работать неэффективно. 2)Решение на уровне ОС. Необходимо  тщательно сконструировать файл, содержащий плохие блоки. Тогда они изымаются из списка свободных блоков.  Затем нужно сделать так, чтобы к этому файлу не было обращений. Если это возможно, то  проблема решена.

Производительность файловой системы

Наиболее типичная техника повышения скорости работы с диском кэширование. Обращение к диску обычно в 100000 раз медленнее, чем к памяти. (Обращение к памяти – неск-ко сотен наносек, а чтение блока с диска - десятки миллисекунд).  За счет кэширования дисковой инфы в памяти м. сократить число дисковых операций,  храня часть блоков диска, к кот перед этим производились обращения, в спец обл-ти памяти, именуемой буферным кэшем. Это оказывается возможным вследствие присущего ОС св-ву локальности.

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

Аккуратная реализация кэширования требует решения неск-ких проблем.

1)емкость буфера кэша ограничена. Когда блок д.б. загружен в  заполненный буфер кэша, возникает проблема замещения блоков, т.е. отдельные блоки д.б. удалены из него. Эта ситуация очень напоминает  ситуацию с выталкиванием страниц памяти, и  здесь useся те же алгоритмы, напр-р,  FIFO, Second Chance и LRU. Разница лишь в том, что ссылки кэша не столь часты, как ссылки на страницы памяти.

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

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

Кэширование - не единственный способ увеличения производительности сис-мы. 

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

Современные архитектуры файловых систем

Современные ОС предоставляют пользователю возможность работать сразу с неск-кими файловыми сис-мами (Linux работает с Ext2fs, FAT и др.).  Файловая сис-ма в традиционном понимании становится частью более общей многоуровневой структуры (см. рис. 12.12).

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

          Рис.  Архитектура современной файловой системы

Вывод:Реализация файловой системы связана с такими вопросами, как поддержка понятия логического блока диска, связывания имени файла и блоков его данных, проблемами разделения файлов и проблемами управления дискового пространства.

Наиб распространенные способы выделения дискового пространства: непрерывное выделение, организация связного списка и сис-ма с индексными узлами.

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

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