Организация хранения данных на диске

2.1. Организация хранения  данных на диске

 

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

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

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

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

Имена файлов обычно представляют собой символьные строки ограниченной длины (как правило, до 8 или до 255 символов), которые кратко описывают данные, хранимые в файле. Обычно существует ряд символов, запрещенных к использованию в именах файлов. В UNIX-системах это символы *, ?, /, \, <, >, &, $, I и др.

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

 

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

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

Что же представляет собой файл с  точки зрения ОС, а точнее, с точки  зрения файловой системы как части  ядра ОС?

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

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

Все дисковое пространство, используемое файловой системой, разбивается на отдельные блоки — кластеры (обычно имеющие размер 1, 2, 4, 8 или 16 Кбайт). Каждый кластер имеет свой номер и хранит либо данные пользователя, либо служебную информацию. Эта служебная информация используется в том числе и для сборки блоков в наборы данных. Размер кластера устанавливается при создании файловой системы. Например, служебный блок может хранить последовательность номеров блоков (кластеров), входящих в набор данных (рис. 2.1).

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

 

РИС 2.1

 

Рис. 2.1. Файловая система со ссылками на все блоки  набора данных: (       ) — служебный блок; Q ] — блок данных; \    / — кластер

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

Второй  подход к организации блоков данных состоит в том, что наборы данных размещаются в последовательных кластерах. В этом случае в служебном  блоке достаточно хранить номера первого и последнего кластера (рис. 2.2). При частых изменениях данных этот метод организации неудобен — при увеличении размера набора данных нужно или всегда иметь достаточное количество свободных блоков после последнего, или каждый раз перемещать набор данных на свободное место. Тем не менее такой подход положен в основу организации данных на CD-ROM-носителях, а ранее использовались в ОС «РАФОС».

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

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

 

РИС 2.2

Рис. 2.2. Файловая система" с последовательной организацией блоков данных:

С      ) — служебный блок; |     | — блок данных; \ I — кластер

РИС 2.3

• соглашения о структуре хранения данных на носителе — определение типов информации, которая может быть размещена на носителе (например, пользовательская/служебная информация), а также набор правил, согласно которым данные размещаются на носителе;
• соглашения о правилах обработки данных — набор правил, согласно которым данные обрабатываются, например, «файл должен быть открыт до того, как в него будут записаны данные»;
• процедуры обработки данных, которые входят в состав ядра ОС и подчиняются определенным выше соглашениям.

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

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

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

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

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

РИС 2.4

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

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

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

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

РИС 2.5

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

Интерфейс драйвера с дисковым контроллером определяет режим доступа к устройству: при символьном доступе информация считывается последовательно по одному символу, при блочном —  блоками фиксированного размера (обычно кратного размеру сектора). Драйвер представляет собой дисковое пространство в виде неструктурированной последовательности пронумерованных физических блоков¹. Размер физического блока обычно равен размеру сектора. При переходе от физического представления данных к логическому физические блоки объединяются в кластеры, с которыми работает файловая система.

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

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

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

 

2.2. Каталоги

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

На рис. 2.6 элементы, имена которых начинаются с dir, являются каталогами; элементы, имена которых начинаются с file, — файлами. Если каталог содержится внутри другого каталога, то внешний каталог называется родительским для первого каталога, или надкаталогом. Содержащийся внутри каталог называется подкаталогом. Например, каталог dir3 является родительским для dir5, а каталог dir2 — подкаталогом dir1. Каталог, находящийся на верхнем уровне иерархии и не имеющий родительского каталога, называется корневым каталогом.

Использование каталогов в современных ОС обусловлено  тремя факторами:

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

РИС 2.6

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