Стальнов А.Ф., Фомин А.И. Операционные системы. Учебное пособие

Подождите немного. Документ загружается.

221

шинстве современных ОС, в том числе в MS-DOS, Windows NT/2000,

NetWare. Неструктурированная модель файла позволяет легко организо-

вать разделение файла между несколькими приложениями: разные прило-

жения могут по-своему структурировать и интерпретировать данные, со-

держащиеся в файле.

Другая модель файла, которая применялась в ОС OS/360, DEC RSX и

VMS, а в настоящее время используется достаточно редко, – это структу

рированный файл. В этом случае поддержание структуры файла поручает-

ся файловой системе. Файловая система видит файл как упорядоченную

последовательность логических записей. Приложение может обращаться к

ФС с запросами на ввод-вывод на уровне записей, например “считать за-

пись 25 из файла FILE.DOC”. ФС должна обладать информацией о струк-

туре файла, достаточной для

того, чтобы выделить любую запись. ФС пре-

доставляет приложению доступ к записи, а вся дальнейшая обработка

данных, содержащихся в этой записи, выполняется приложением. Разви-

тием этого подхода стали системы управления базами данных (СУБД), ко-

торые поддерживают не только сложную структуру данных, но и взаимо-

связи между ними.

Логическая запись является наименьшим

элементом данных, которым

может оперировать программист при организации обмена с внешним уст-

ройством. Даже если физический обмен с устройством осуществляется

большими единицами, операционная система должна обеспечивать про-

граммисту доступ к отдельной логической записи.

Файловая система может использовать два способа доступа к логиче-

ским записям: читать или записывать логические записи последовательно

(последовательный доступ) или позиционировать файл на запись с ука-

занным номером (прямой доступ).

Очевидно, что ОС не может поддерживать все возможные способы

структурирования данных в файле, поэтому в тех ОС, в которых вообще

существует поддержка логической структуризации файлов, она существу-

ет для небольшого числа широко распространенных схем логической ор-

ганизации

файла.

К числу таких способов структуризации относится представление дан-

ных в виде записей, длина которых фиксирована в пределах файла (рис.

4.15, а). В таком случае доступ к n-й записи осуществляется либо путем

последовательного чтения (n-1) предшествующих записей, либо прямо по

адресу, вычисленному по ее порядковому номеру. Например, если L –

длина

записи, то начальный адрес n-й записи равен L×n. Заметим, что при

такой логической организации размер записи фиксирован в пределах фай-

ла, а записи в различных файлах, принадлежащих одной и той же файло-

вой системе, могут иметь различный размер.

222

l l l l l l l

Последовательность логических записей фиксированной длины

l1 l2 l3 l4 l5

Последовательность логических записей переменной длины

l2 l3 l4 l5

1в

Индексная логическая организация

8 6 2 5

Индексная таблица Запись 5Запись 4Запись 3Запись 2Запись 1

Индекс

Адрес

201

315

661

670

715

Индекс ключ

Рис. 4.15. Способы логической организации файлов

Другой способ структуризации состоит в представлении данных в виде

последовательности записей, размер которых изменяется в пределах одно-

го файла. Если расположить значения длин записей так, как это показано

на рис. 4.15, б, то для поиска нужной записи система должна последова-

тельно считать все предшествующие записи.

Вычислить адрес нужной за-

писи по ее номеру при такой логической организации файла невозможно,

а следовательно, не может быть применен более эффективный метод пря-

мого доступа.

Файлы, доступ к записям которых осуществляется последовательно, по

номерам позиций, называются неиндексированными, или последователь-

ными.

Другим типом файлов являются индексированные файлы, они допус-

кают более

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

дексированном файле (рис. 4.15, в) записи имеют одно или более ключе-

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

этих полей. Для быстрого поиска данных в индексированном файле пре-

дусматривается специальная индексная таблица, в которой значениям

ключевых полей ставится в соответствие

адрес внешней памяти. Этот ад-

223

рес может указывать либо непосредственно на искомую запись, либо на

некоторую область внешней памяти, занимаемую несколькими записями,

в число которых входит искомая запись. В последнем случае говорят, что

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

включает два этапа: прямой доступ по индексу к указанной области диска,

а затем последовательный просмотр

записей в указанной области. Ведение

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

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

Все вышесказанное в большей степени относится к обычным файлам,

которые могут быть как структурированными, так и неструктурированны-

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

структурой, известной файловой системе. Например, файловая система

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

файле типа “символьная связь”.

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

5.1. Структура магнитного диска

Представление пользователя о файловой системе как об иерархически

организованном множестве информационных объектов имеет мало обще-

го с порядком хранения файлов на

диске. Файл, имеющий образ цельного,

непрерывающегося набора байт, на самом деле очень часто разбросан “ку-

сочками” по всему диску, причем это разбиение никак не связано с логи-

ческой структурой файла, например, его отдельная логическая запись мо-

жет быть расположена в несмежных секторах диска. Логически объеди-

ненные файлы из одного каталога совсем

не обязаны соседствовать на

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

на реальном устройстве описываются физической организацией файловой

системы. Очевидно, что разные файловые системы имеют разную физиче-

скую организацию.

Основным типом устройства, которое используется в современных вы-

числительных системах для хранения файлов, являются дисковые накопи-

тели. Эти устройства предназначены

для считывания и записи данных на

жесткие и гибкие магнитные диски. Жесткий диск состоит из одной или

нескольких стеклянных или металлических пластин, каждая из которых

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

диск в общем случае состоит из пакета пластин (рис. 4.16). Однако обычно

под термином “жесткий диск” понимают

весь пакет магнитных дисков.

224

Дорожка N

Дорожка 0

Дорожка 1023

Сторона 0

Сектор

Пластина 1

Пластина 2

Цилиндр 0

Головка 1 Головка 2

Рис. 4.16. Схема устройства жесткого диска

На каждой стороне каждой пластины размечены тонкие концентриче-

ские кольца – дорожки (traks), на которых хранятся данные. Количество

дорожек зависит от типа диска. Нумерация дорожек начинается с 0 от

внешнего края к центру диска. Головка может позиционироваться над за-

данной дорожкой. Головки перемещаются над поверхностью диска дис-

кретными шагами, каждый шаг соответствует сдвигу на одну дорожку.

Совокупность дорожек одного радиуса на всех поверхностях всех пла-

стин пакета называется цилиндром (cylinder). Каждая дорожка разбивается

на фрагменты, называемые секторами (sectors), или блоками (blocks), так

что все дорожки имеют равное число секторов, в которые можно макси-

мально записать одно и то же число байт

. Сектор имеет фиксированный

для конкретной системы размер, выражающийся степенью двойки. Чаще

всего размер сектора составляет 512 байт. Учитывая, что дорожки разного

радиуса имеют одинаковое число секторов, плотность записи становится

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

секторов на винчестере представляет его неформатированную емкость.

Физический адрес сектора на диске

определяется с помощью трех “ко-

ординат”, то есть представляется триадой [c-h-s], где с – номер цилиндра

(дорожки на поверхности диска, cylinder), h – номер рабочей поверхности

диска (магнитной головки, head), a s – номер сектора на дорожке. Номер

цилиндра с лежит в диапазоне 0..С-1, где С – количество цилиндров. Но-

мер рабочей поверхности диска h принадлежит диапазону 0..Н-1,

где H –

число магнитных головок в накопителе. Номер сектора на дорожке s ука-

зывается в диапазоне 1..S, где S – количество секторов на дорожке. На-

225

пример, триада [1-0-2] адресует сектор 2 на дорожке 0 (обычно верхняя

рабочая поверхность) цилиндра 1.

Операционная система при работе с диском использует, как правило,

собственную единицу дискового пространства, называемую кластером

(cluster). Иногда кластер называют блоком (например, в ОС Unix), что мо-

жет привести к терминологической путанице. Вообще, терминология, ис-

пользуемая при описании форматов дисков и файловых

систем, зависит от

аппаратной платформы (RISC, Wintel и т. п.) и операционной системы.

Это нужно учитывать и трактовать термины в зависимости от контекста.

При создании файла место на диске ему выделяется кластерами. На-

пример, если файл имеет размер 2560 байт, а размер кластера в файловой

системе определен в 1024 байта, то файлу будет выделено на

диске 3 кла-

стера.

Дорожки и секторы создаются в результате выполнения процедуры фи-

зического, или низкоуровневого, форматирования диска, предшествующей

использованию диска. Для определения границ блоков на диск записыва-

ется идентификационная информация. Низкоуровневый формат диска не

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

зовать.

Разметку диска под конкретный тип

файловой системы выполняют

процедуры высокоуровневого, или логического, форматирования. При вы-

сокоуровневом форматировании определяется размер кластера и на диск

записывается информация, необходимая для работы файловой системы, в

том числе информация о доступном и неиспользуемом пространстве, о

границах областей, отведенных под файлы и каталоги, информация о по-

врежденных областях. Кроме того, на диск

записывается загрузчик опера-

ционной системы – небольшая программа, которая начинает процесс ини-

циализации операционной системы после включения питания или рестар-

та компьютера.

Жесткий диск может быть разбит на несколько разделов (partition), ко-

торые, в принципе затем могут использоваться либо одной ОС, либо раз-

личными ОС. Причем самым главным является то, что на

каждом разделе

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

даже одной-единственной файловой системы необходимо определить, по

крайней мере, один раздел.

Разделы диска могут быть двух типов – primary (обычно этот термин

переводят как первичный) и extended (расширенный). Максимальное число

primary-разделов равно четырем. При этом на диске обязательно должен

быть по крайней мере один primary-раздел.

Согласно спецификациям на одном жестком диске может быть только

один extended-раздел, который, в свою очередь, может быть разделен на

большое количество подразделов – логических дисков (logical). Во многих

операционных системах используется термин “том” (volume). В разных

ОС толкование этого термина имеет свои нюансы, но

чаще всего он обо-

226

значает логическое устройство, отформатированное под конкретную фай-

ловую систему.

Один из primary-разделов должен быть активным, именно с него долж-

на загружаться программа загрузки операционной системы, или так назы-

ваемый менеджер загрузки, назначение которого – загрузить программу

загрузки ОС из какого-нибудь другого раздела, и уже с ее помощью за-

гружать операционную

систему. Поскольку до загрузки ОС система

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

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

мате [c-h-s].

По физическому адресу [0-0-1] на винчестере располагается главная за-

грузочная запись (master boot record, MBR), содержащая внесистемный за-

грузчик (non-system bootstrap – NSB), а также таблицу разделов (partition

table, PT). Эта запись занимает ровно один сектор, она

размещается в па-

мяти, начиная с адреса 0:7С00h, после чего управление передается коду,

содержащемуся в этом самом первом секторе магнитного диска. Таким

образом, в самом первом (стартовом) секторе физического жесткого диска

находится не обычная запись boot record, как на дискете, a master boot re-

cord.

MBR является основным средством загрузки с жесткого диска, под-

держиваемым BIOS. В MBR находятся

три важных элемента:

1. Программа начальной загрузки (non-system bootstrap). Именно она

запускается BIOS после успешной загрузки в память первого сектора с

MBR и служит для поиска с помощью partition table активного раздела,

копирования в оперативную память компьютера загрузчика system boot-

strap из выбранного раздела и передачи ему управления, что позволяет

осуществить загрузку ОС.

2. Таблица описания разделов диска (partition table). Располагается в

MBR по смещению 0x1BE и занимает 64 байта.

3. Сигнатура MBR. Последние два байта MBR должны содержать число

АА55h. По наличию этой сигнатуры BIOS проверяет, что первый блок был

загружен успешно. Сигнатура эта выбрана не случайно. Ее успешная про-

верка позволяет установить, что все линии передачи данных могут пере-

давать и нули, и единицы.

Таблица partition table

описывает размещение и характеристики имею-

щихся на винчестере разделов. Можно сказать, что эта таблица разделов –

одна из наиболее важных структур данных на жестком диске. Если эта

таблица повреждена, то не только не будет загружаться операционная сис-

тема (или одна из операционных систем, установленных на винчестере),

но перестанут быть доступными и данные

, расположенные на винчестере,

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

Упрощенно структура MBR представлена в табл. 4.1.

227

Таблица 4.1

Структура MBR

Смещение

(Offset)

Размер (Size)

(байт)

Содержимое

(Contents)

0 446 Программа анализа Partition Table

и загрузки System Bootstrap

с активного раздела жесткого диска

+1BEh 16 Partition 1 entry (Описатель раздела)

+1CEh 16 Partition 2 entry

+1DEh 16 Partition 3 entry

+1EEh 16 Partition 4 entry

+1FEh 2 Сигнатура (АА55h)

Из рисунка видно, что в начале этого сектора располагается программа

анализа таблицы разделов и чтения первого сектора из активного раздела

диска. Сама таблица partition table располагается в конце MBR, и для опи-

сания каждого раздела в этой таблице отводится по 16 байтов. Первым

байтом в элементе раздела идет флаг активности раздела boot indicator (0 –

не активен, 128 (80Н) –

активен). Он служит для определения, является ли

раздел системным загрузочным и есть ли необходимость производить за-

грузку операционной системы с него при старте компьютера. Активным

может быть только один раздел. За флагом активности раздела следует

байт номера головки, с которой начинается раздел. За ним следует два

байта, означающие соответственно номер сектора

и номер цилиндра за-

грузочного сектора, где располагается первый сектор загрузчика операци-

онной системы. Затем следует кодовый идентификатор System ID (длиной

в один байт), указывающий на принадлежность данного раздела к той или

иной операционной системе и установке на нем соответствующей файло-

вой системы. За байтом кода операционной системы расположен байт но-

мера

головки конца раздела, за которым идут два байта – номер сектора и

номер цилиндра последнего сектора данного раздела. Номера сектора и

номер цилиндра секторов в разделах занимают по 6 и 10 бит соответст-

венно (рис. 4.17).

Биты номера цилиндра Биты номера сектора

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

Рис. 4.17. Формат записи номера сектора и номера цилиндра

Вслед за сектором MBR размещаются собственно сами разделы

(рис. 4.18).

228

Master Boot RecordПервичный раздел

Расширенный раздел

Не использован

Загрузочный сектор

Расширенная таблица

разделов

Загрузочный сектор

Расширенная таблица

разделов

Загрузочный сектор

Главная таблица

разделов

Логический диск D:

Адрес таблицы

для диска E:

Не использован

Первая расширенная

таблица разделов

0-конец цепочки

Не использован

Логический диск E:

Вторая расширенная

таблица разделов

Первичный

раздел DOS

(диск C:)

Расширенный

раздел DOS

с логическими

дисками D: и E:

Рис. 4.18. Разбиение диска на разделы

В процессе начальной загрузки сектора MBR, содержащего таблицу

partition table, работают программные модули BIOS. Начальная загрузка

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

делов содержит допустимую информацию.

В MS-DOS в первичном разделе может быть сформирован только один

логический диск, а в расширенном – любое их количество. Каждый

логи-

ческий диск “управляется” своим логическим приводом. Каждому логиче-

скому диску на винчестере соответствует своя (относительная) логическая

нумерация. Физическая же адресация жесткого диска сквозная.

Первичный раздел DOS включает только системный логический диск

без каких-либо дополнительных информационных структур.

Расширенный раздел DOS содержит вторичную запись MBR (secondary

MBR, SMBR), в состав которой вместо partition table входит таблица логи-

ческого

диска (LDT, logical disk table), ей аналогичная. Таблица LDT опи-

сывает размещение и характеристики раздела, содержащего единственный

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

SMBR. Следовательно, если в расширенном разделе DOS создано К логи-

ческих дисков, то он содержит К экземпляров SMBR, связанных в список.

229

Каждый элемент этого списка описывает соответствующий логический

диск и ссылается (кроме последнего) на следующий элемент списка.

Утилиты, позволяющие разбить диск на разделы и тем самым сформи-

ровать как partition table, так и, возможно, списковую структуру из LDT

(подобно тому, как это изображено на рис. 4.18), обычно называются

FDISK (от form disk), хотя есть утилиты и с другим

названием, умеющие

выполнить разбиение диска. Напомним, что FDISK от MS-DOS позволяет

создать только один primary-раздел и один extended, который, в свою оче-

редь, предлагается разделить на несколько логических дисков. Аналогич-

ные утилиты других ОС имеют существенно больше возможностей. Так,

например, FDISK системы OS/2 позволяет создавать несколько primary-

разделов, причем их можно выделять не только последовательно, начиная

с первых цилиндров, но и с конца свободного дискового пространства.

Это удобно, если нужно исключить из работы некоторый диапазон диско-

вого пространства (например, из-за дефектов на поверхности магнитного

диска).

В последнее время появилось большое количество утилит, которые

предоставляют возможность более наглядно представить разбиение диска

на разделы, поскольку в них используется

графический интерфейс. Эти

программы успешно и корректно работают с наиболее распространенны-

ми типами разделов (разделы под FAT, FAT32, NTFS). Однако созданы

они в основном для работы в среде Win32API, что часто ограничивает

возможность их использования. Одной из самых известных и мощных

программ для работы с разделами жесткого диска является Partition Magic

фирмы Power Quest.

5.2. Файловые системы современных

операционных систем

5.2.1. Физическая организация и адресация файла

Важным компонентом физической организации файловой системы яв-

ляется физическая организация файла, то есть способ размещения файла

на диске. Основными критериями эффективности физической организа-

ции файлов являются:

скорость доступа к данным;

объем адресной информации файла;

степень фрагментированности дискового пространства;

максимально возможный размер

файла.

Непрерывное размещение – простейший вариант физической организа-

ции (рис. 4.19, а), при котором файлу предоставляется последовательность

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

230

файл

область

индексов

3 5

файл

2,4,5,7

Рис. 4.19. Физическая организация файла: непрерывное размещение (а);

связанный список кластеров (б); связанный список индексов (в);

перечень номеров кластеров (г)

Основным достоинством этого метода является высокая скорость дос-

тупа, так как затраты на поиск и считывание кластеров файла минималь-

ны. Также минимален объем адресной информации – достаточно хранить

только номер первого

кластера и объем файла. Данная физическая органи-

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

этот вариант имеет существенные недостатки, которые затрудняют его

применимость на практике, несмотря на всю его логическую простоту.

При более пристальном рассмотрении оказывается, что реализовать эту

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

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

ции может увеличить свой размер? Еще более серьезной проблемой явля-

ется фрагментация. Спустя некоторое время после создания файловой

системы в результате выполнения многочисленных операций создания и

удаления файлов пространство диска неминуемо превращается в “лоскут-