zamyatin_posobie

Главное достоинство данного подхода состоит в том, что по таблице отображения можно судить о физическом соседстве блоков, располагающихся на диске, и при выделении нового блока можно легко найти свободный блок диска, находящийся поблизости от других блоков данного файла. Минусом данной схемы может быть необходимость хранения в памяти этой довольно большой таблицы. Более подробно особенности использования таблицы размещения файлов рассмотрены в п. 5.5.1 при описании файловой системы FAT.

Индексные узлы. Четвертый и последний способ «выяснения принадлежности» блока к файлу – связать с каждым файлом маленькую таблицу, называемую индексным узлом (i-node), которая перечисляет атрибуты и дисковые адреса блоков файла (рис. 41). Каждый файл имеет свой собственный индексный блок, который содержит адреса блоков данных. Запись в директории, относящаяся к файлу, содержит адрес индексного блока. По мере заполнения файла указатели на блоки диска в индексном узле принимают осмысленные значения. Индексирование поддерживает прямой доступ к файлу, без ущерба от внешней фрагментации.

Атрибуты

файла

Блок

данных

Блок

Блок

Адреса

данных

данных

блока

данных

Блок

Блок

данных

данных

Адрес

Блок

блока

косвенной

данных

адресации

Адрес

Блока

Блок

двойной

данных

косвенной

адресации

Адрес

Блок

Блока

данных

тройной

косвенной

Блок

адресации

данных

Блок

данных

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

131

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

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

5.2.5Управление дисковым пространством

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

Учет при помощи организации битового вектора. Часто список свободных блоков диска реализован в виде битового вектора (bit map или bit vector). Каждый блок представлен одним битом, принимающим значение 0 или 1, в зависимости от того занят он или свободен. Напри-

мер, 00111100111100011000001... .

Главное преимущество этого подхода – относительная простота и эффективность при нахождении первого свободного блока или n последовательных блоков на диске. Многие компьютеры (например, Intel и Motorola) имеют специальные инструкции манипулирования битами, при помощи которых можно легко локализовать первый единичный бит в слове.

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

Учет при помощи организации связного списка. Другой под-

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

14 Например, диск размером 1.3 Гб с блоками по 512 байт нуждается в таблице размером 332Кбайт.

132

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

5.2.6Размер логического блока

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

Проведенные исследования показали, что большинство файлов имеет небольшой размер (в Unix приблизительно 85% файлов имеют размер менее 8 Кб и 48% – менее 1 Кб). На рис. 42 изображены две зависимости от размера блока: одна показывает убывающую степень утилизации (использования) диска, а вторая – возрастающую скорость обмена данных с диском. Зависимости имеют общую точку при размере блока 3 Кб. Обычный компромисс – выбор блока размером 512 б, 1 Кб, 2 Кб.

Скорость обмена с диском

Процент использования

(Кб/c)

дискового пространства

200

100

Утилизация

диска

Скорость

обмена

с диском

0 128

1k

2k

4k

8k Размер блока

Рисунок 42 – Результаты исследований при определении оптимального размера блока

133

5.3Особенности загрузки ОС

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

Процедура начальной загрузки (англ. bootstrap loader) вызывается как программное прерывание (BIOS INT 19h). Эта процедура определяет первое готовое устройство из списка разрешенных и доступных (гибкий или жесткий диск, а в современных компьютерах это могут быть еще и компакт-диск, привод ZIP-drive, сетевой адаптер или иное устройство) и пытается загрузить с него в ОП короткую главную программу-загрузчик. Для накопителей на жестких магнитных дисках – это известный главный или внесистемный загрузчик (NSB) из MBR, и ему передается управление.

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

сы BIOS.

Необходимо отметить, что в современных мультипрограммных ОС большинство сервисов BIOS, изначально расположенных в ПЗУ, как правило, заменяются собственными драйверами ОС, поскольку они должны работать в режиме прерываний, а не в режиме сканирования готовности.

Прежде чем форматировать диск под определенную файловую систему, он может быть поделен на разделы – непрерывные части физического диска, которую ОС представляет пользователю как логические устройства (логические диски, логические разделы)15. Логическое устройство функционирует так, как если бы это был отдельный физический диск. Именно с логическими устройствами работает пользователь, обращаясь к ним по символьным именам, используя, например, обозначения А, В, С, SYS и т.п. Операционные системы разного типа используют единое для всех них представление о разделах, но создают на его основе логические устройства, специфические для каждого типа ОС. Так же как файловая система, с которой работает одна ОС, в общем случае не может интерпретироваться ОС другого типа, логические устройства

15 Во многих ОС используется термин «том» (англ. volume), хотя толкование этого термина в разных ОС имеет свои нюансы.

134

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

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

На разных логических устройствах одного и того же физического диска могут располагаться файловые системы разного типа. На рис. 43 показан пример диска, разбитого на три раздела, в которых установлены две файловых системы NTFS (разделы С и Е) и одна файловая система FAT (раздел D).

Файловая система С:

NTFS

Файловая система D:

FAT

Файловая система E:

NTFS

Рисунок 43 – Схематичное представление разбиения диска на разделы

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

16 RAID (англ. redundant array of independent/inexpensive disks) – дисковый массив независимых дис-

ков, предназначенный для повышения надѐжности хранения данных и/или для повышения скорости чтения/записи информации.

135

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

5.4Файлы и файловая система

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

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

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

Norton Commander или Windows Explorer, в символьных составных име-

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

5.4.1Цели и задачи файловой системы

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

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

136

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

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

Файловая система, являющаяся неотъемлемой частью любой современной ОС, включает:

совокупность всех файлов на диске;

наборы структур данных, используемых для управления файлами (каталоги файлов, дескрипторы файлов, таблицы распределения свободного и занятого пространства на диске);

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

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

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

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

137

(например, MS-DOS). Основные функции в такой файловой системе сведены к следующему перечню:

именование файлов;

программный интерфейс для приложений;

отображение логической модели файловой системы на физическую организацию хранилища данных;

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

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

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

идентификация файлов – связывание имени файла с выделенным ему пространством внешней памяти;

распределение внешней памяти между файлами – для работы с конкретным файлом не требуется иметь информацию о местоположении этого файла на внешнем носителе информации (сторона магнитного диска, цилиндр, сектор);

обеспечение надежности и отказоустойчивости;

обеспечение защиты от несанкционированного доступа;

обеспечение совместного доступа к файлам (пользователь не должен прилагать специальных усилий по обеспечению синхронизации доступа);

обеспечение высокой производительности.

5.4.2Типы файлов

Файловые системы поддерживают несколько функционально различных типов файлов, в число которых, как правило, входят:

обычные файлы;

файлы-каталоги;

138

специальные файлы;

отображаемые в память файлы;

именованные конвейеры;

другие.

Рассмотрим каждый из этих типов файлов.

Обычные файлы, или просто файлы, содержат информацию произвольного характера, которую заносит в них пользователь или которая образуется в результате работы системных и пользовательских программ. Большинство современных ОС (например, Unix или MS Windows) никак не ограничивает и не контролирует содержимое и структуру обычного файла. Содержание обычного файла определяется приложением, которое с ним работает. Обычные файлы бывают двух типов – текстовые17 и двоичные18. Обычно прикладные программы, работающие с файлами, распознают тип файла по его имени в соответствии с общепринятыми соглашениями. Например, файлы с расширениями .c,

.pas, .txt – ASCII-файлы, файлы с расширениями .exe – исполняемые, файлы с расширениями .obj, .zip – бинарные и т.д. Все ОС должны уметь распознавать хотя бы один тип файлов – собственные исполняемые файлы.

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

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

17Текстовые файлы состоят из строк символов, представленных в ASCII-коде, их можно прочитать на экране и распечатать на принтере.

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

139

(например, в одну группу объединяются файлы, содержащие документы одного договора, или файлы, составляющие один программный пакет), с другой стороны – это файл, содержащий системную информацию о группе файлов, его составляющих.

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

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

Специальные файлы, так же как и устройства ввода-вывода, делятся на блок-ориентированные19 и байт-ориентированные20. Следует пом-

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

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

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

20 Обеспечивают посимвольный небуферированный ввод/вывод, не адресуемы и не позволяют производить операцию поиска, генерируют или потребляют последовательность байтов (например, терминалы, строчные принтеры, сетевые адаптеры).

140