DAY07 (Старые версии Машбука или нечто подобное)

5

Лекция №7

Лекция №7

Подходы к организации файловых систем.

На сегодняшней лекции мы рассмотрим основные подходы к организации файловых систем.

1. Одноуровневая модель файлов с непрерывными сегментами.

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

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

Чтения/запись происходит почти без дополнительных обменов, так как при открытии файла мы получаем диапазон размещения данных. Замечу, что реально данные в файле могут занимать несколько меньше места чем разность между конечным и начальным адресами файла, о чем будет сказано позже. Обмен при чтении происходит очень быстро.

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

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

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

1. Файловая система с блочной организацией файлов.

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

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

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

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

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

1. Иерархическая файловая система.

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

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

Узлы дерева отличные от листа являются файлами-каталогами (Это, если пошло дело говорить на языке математического анализа, достаточное условие). В итоге получается дерево, в узлах которого находятся каталоги, а листьями могут быть либо файлы, либо пустые каталоги.

Взглянем на наше дерево. В нем 5 каталогов: «/», «work», «games», «office», «text» и 7 файлов: «delphi», «cpp», «word», «referat», «artikel», «spo», «jokes». Каталог «games» пример пустого каталога (играть некогда - скоро сессия), каталога который является листом. В каталоге «office» есть подкаталог «texts», в котором расположены файлы-документы.

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

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

Пример: «/office/texts/artikel». Кратким именем файла или каталога (или просто именем) называется название конкретного узла (без указания полного пути от каталога нулевого уровня до данного узла). Полное имя файла (каталога) будет уникальным при условии, что в пределах любого каталога имена всех каталогов (файлов) уникальны.

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

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

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

Глава III. Операционная система UNIX

История и основные характеристики

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

Сначала немного истории. В середине 60-х годов в Bell Laboratories фирмы AT&T проводились исследования и разработка одной из первых операционных систем в современном ее понимании - операционной системы Multics. Эта операционная система обладала свойствами операционной системы разделения времени, многопользовательской системы, а также в этой системе были предложены основные решения по организации файловых систем, в частности, была предложена иерархическая древообразная файловая система. От этой разработки через некоторое время получила начало операционная система UNIX. Одна из историй разработки этой системы говорит о том, что на фирме был ненужный компьютер PDP-7 с очень малоразвитым программным обеспечением и требовалась машина, которая позволяла бы организовывать комфортную работу пользователя, в частности, обработку текстовой информации. Известная группа людей - это Кен Томпсон и Деннис Ритчи, занялись разработкой новой операционной системы. Другой вариант этой истории гласит о том, что якобы они занимались реализацией некоторой игры и те средства, которые были им доступны, оказались неудобны - тогда они решили поиграть с этой машиной. В результате появилась операционная система UNIX.

Особенностью этой системы являлось то, что она была первой системной программой, которая была написана с использованием языка, отличного от машинного языка (ассемблера). Для целей написания этого системного программного обеспечения, в частности, операционной системы UNIX, также проводились работы, которые начинались от языка BCPL. Из него был образован язык B, который оперировал с машинными словами. Далее абстракция машинных слов - BN, и, наконец, язык Си. С 1983 года операционная система UNIX (ее первоначальная версия) была переписана на язык Си, и получилось, что около 90% операционной системы было написано на языке высокого уровня, не зависящем от архитектуры машины, а 10% этой системы были написаны на ассемблере. В эти десять процентов вошли наиболее критичные по времени части операционной системы.

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

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