Geum.ru

The design of the unix operating system by Maurice J

Вид материалаРеферат
4.7 Выделение дисковых блоков
4.8 Другие типы файлов
Подобный материал:
1   ...   6   7   8   9   10   11   12   13   ...   55

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

диску, при этом, начав просмотр с индекса с номером 499, оно сно-

ва обнаружит индексы 535 и 601.


Процесс A Процесс B Процесс C

-------------------------------------------------------------

│ Назначает индекс I

│ из суперблока

│

│ Приостанавливается

│ на время считывания

│ индекса (а)

│

│ Пытается назначить

│ индекс из суперблока

│

│ Суперблок пуст (б)

│

│ Просматривает диск в

│ поисках свободных ин-

│ дексов, помещение ин-

│ декса I в суперблок

│ (в)

│

│ Индекс I в памяти

│ Выполняются обычные

│ действия

│

│ Заканчивает просмотр,

│ назначает другой индекс

│ (г)

│

│ Назначает индекс I

│ из суперблока

│

│ Индекс I уже исполь-

│ зуется !

│

│ Назначает другой

│ индекс (д)

│

v Время


Рисунок 4.16. Конкуренция в назначении индексов


В предыдущем параграфе описывались простые случаи работы ал-

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

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

что ядро может и обнаружить, что индекс уже назначен. Несмотря на

редкость такой ситуации, обсудим этот случай (с помощью Рисунков

4.16 и 4.17). Пусть у нас есть три процесса, A, B и C, и пусть

ядро, действуя от имени процесса A (***), назначает индекс I, но

приостанавливает выполнение процесса перед тем, как скопировать

дисковый индекс в память. Алгоритмы iget (вызванный алгоритмом


---------------------------------------

(***) Как и в предыдущей главе, здесь под "процессом" имеется

ввиду "ядро, действующее от имени процесса".


│Время

│ ----T---T---T--------------------------------┐

│ (а) │ │ │ │ │

│ │ │ │ I │ │

│ │ │ │ │ │

│ L---+---+---+---------------------------------

│

│ ---------------------------------------------┐

│ (б) │ пусто │

│ │ │

│ │ │

│ L---------------------------------------------

│

│ ----T---T---T--------------------T---T---T---┐

│ (в) │ │ │ │ │ │ │ │

│ │ │ │ │ свободные индексы │ J │ I │ K │

│ │ ││││││ │

│ L---+---+---+--------------------+---+---+----

│

│ ----T---T---T--------------------T---T---T---┐

│ (г) │ │ │ │ │ │ │ │

│ │ │ │ │ свободные индексы │ J │ I │ │

│ │ ││││││ │

│ L---+---+---+--------------------+---+---+----

│

│ ----T---T---T----------------T---T---T---T---┐

│ (д) │ │ │ │ свободные │ │ │ │ │

│ │ │ │ │ индексы │ L │ │ │ │

│ │ │││││ │ │ │

│ L---+---+---+----------------+---+---+---+----

v


Рисунок 4.17. Конкуренция в назначении индексов (продолжение)


ialloc) и bread (вызванный алгоритмом iget) дают процессу A дос-

таточно возможностей для приостановления своей работы. Предполо-

жим, что пока процесс A приостановлен, процесс B пытается назна-

чить новый индекс, но обнаруживает, что список свободных индексов

в суперблоке пуст. Процесс B просматривает диск в поисках свобод-

ных индексов, и начинает это делать с индекса, имеющего меньший

номер по сравнению с индексом, назначенным процессом A. Возможно,

что процесс B обнаружит индекс I на диске свободным, так как про-

цесс A все еще приостановлен, а ядро еще не знает, что этот ин-

декс собираются назначить. Процесс B, не осознавая опасности, за-

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

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

Однако, индекс I остается в списке номеров свободных индексов в

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

вает назначение индекса I. Теперь допустим, что процесс C затем

затребовал индекс и случайно выбрал индекс I из списка в суперб-

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

из установки типа файла, что индекс уже назначен. Ядро проверяет

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

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

диск после его назначения в соответствии с алгоритмом ialloc сни-

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

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

Блокировка списка индексов в суперблоке при чтении с диска

устраняет другие возможности для конкуренции. Если суперблок не

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

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

полнение до завершения операции ввода-вывода. Предположим, что

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

вает, что список пуст. Он тоже попытается заполнить список с дис-

ка. В лучшем случае, оба процесса продублируют друг друга и пот-

ратят энергию центрального процессора. В худшем, участится

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

фе. Сходным образом, если процесс, освобождая индекс, не прове-

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

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

нять этот список информацией с диска. И опять участится конкурен-

ция вышеописанного типа. Несмотря на то, что ядро более или менее

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

Установка блокировки для списка свободных индексов в суперблоке

устраняет такую конкуренцию.


4.7 ВЫДЕЛЕНИЕ ДИСКОВЫХ БЛОКОВ


Когда процесс записывает данные в файл, ядро должно выделять

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

мой адресации и иногда под блоки косвенной адресации. Суперблок

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

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

рамма mkfs ("make file system" - создать файловую систему) орга-

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

указателями так, что каждый элемент списка указывает на дисковый

блок, в котором хранится массив номеров свободных дисковых бло-

ков, а один из элементов массива хранит номер следующего блока

данного списка.

Когда ядру нужно выделить блок из файловой системы (алгоритм

alloc, Рисунок 4.19), оно выделяет следующий из блоков, имеющихся

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

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

является последним блоком, имеющимся в кеше суперблока, ядро

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

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

новым списком номеров блоков и после этого продолжает работу с

первоначальным номером блока. Оно выделяет буфер для блока и очи-

щает содержимое буфера (обнуляет его). Дисковый блок теперь счи-

тается назначенным и у ядра есть буфер для работы с ним. Если в

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

ет сообщение об ошибке.

Если процесс записывает в файл большой объем информации, он

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

но ядро назначает каждый раз только по одному блоку. Программа

mkfs пытается организовать первоначальный связанный список номе-

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

лу, были рядом друг с другом. Благодаря этому повышается произво-

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

ожидания при последовательном чтении файла процессом. На Рисунке

4.18 номера блоков даны в настоящем формате, определяемом ско-

ростью вращения диска. К сожалению, очередность номеров блоков в

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

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

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

его в случайном порядке. Ядро не предпринимает попыток сортиро-

вать номера блоков в списке.


список в суперблоке

------T-----T-----T-----T---------------------┐

│ 109 │ 106 │ 103 │ 100 │ │

L--+--+-----+-----+-----+----------------------

-------

│

│ 109

│ ------T-----T-----T-----T---------------T-----┐

L->│ 211 │ 208 │ 205 │ 202 │ │ 112 │

L--+--+-----+-----+-----+---------------+------

-------

│

│ 211

│ ------T-----T-----T-----T---------------T-----┐

L->│ 310 │ 307 │ 304 │ 301 │ │ 214 │

L--+--+-----+-----+-----+---------------+------

-------

│

│ 310

│ ------T-----T-----T-----T---------------T-----┐

L->│ 409 │ 406 │ 403 │ 400 │ │ 313 │

L--+--+-----+-----+-----+---------------+------

│

v


Рисунок 4.18. Список номеров свободных дисковых блоков

с указателями


Алгоритм освобождения блока free - обратный алгоритму выделе-

ния блока. Если список в суперблоке не полон, номер вновь осво-

божденного блока включается в этот список. Если, однако, список

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

переписывает в него список из суперблока и копирует блок на диск.

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

бодных блоков в суперблоке. Этот номер становится единственным

номером в списке.

На Рисунке 4.20 показана последовательность операций alloc и

free для случая, когда в исходный момент список свободных блоков

содержал один элемент. Ядро освобождает блок 949 и включает номер

блока в список. Затем оно выделяет этот блок и удаляет его номер

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

списка. Поскольку список свободных блоков в суперблоке теперь

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

ка 109, являющегося следующей связью в списке с указателями. На

Рисунке 4.20(г) показан заполненный список в суперблоке и следую-

щий связной блок с номером 211.

Алгоритмы назначения и освобождения индексов и дисковых бло-

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

кеша, хранящего указатели на свободные ресурсы - номера блоков и

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

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

теме появляется в некотором элементе списка, но ядро не поддержи-

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


-------------------------------------------------------------┐

│ алгоритм alloc /* выделение блока файловой системы */ │

│ входная информация: номер файловой системы │

│ выходная информация: буфер для нового блока │

│ { │

│ выполнить (пока суперблок заблокирован) │

│ приостановиться (до того момента, когда с суперблока│

│ будет снята блокировка); │

│ удалить блок из списка свободных блоков в суперблоке; │

│ если (из списка удален последний блок) │

│ { │

│ заблокировать суперблок; │

│ прочитать блок, только что взятый из списка свобод- │

│ ных (алгоритм bread); │

│ скопировать номера блоков, хранящиеся в данном бло- │

│ ке, в суперблок; │

│ освободить блочный буфер (алгоритм brelse); │

│ снять блокировку с суперблока; │

│ возобновить выполнение процессов (после снятия бло- │

│ кировки с суперблока); │

│ } │

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

│ ритм getblk); │

│ обнулить содержимое буфера; │

│ уменьшить общее число свободных блоков; │

│ пометить суперблок как "измененный"; │

│ возвратить буфер; │

│ } │

L-------------------------------------------------------------


Рисунок 4.19. Алгоритм выделения дискового блока


1. Ядро устанавливает, свободен ли индекс или нет, проверяя: если

поле типа файла очищено, индекс свободен. Ядро не нуждается в

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

оно не может определить, свободен ли блок или нет, только

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

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

щей сходную маску. Следовательно, ядро нуждается во внешнем

механизме идентификации свободных блоков, в качестве него в

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

телями.

2. Сама конструкция дисковых блоков наводит на мысль об использо-

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

большие списки номеров свободных блоков. Но индексы не имеют

подходящего места для массового хранения списков номеров сво-

бодных индексов.

3. Пользователи имеют склонность чаще расходовать дисковые блоки,

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

просмотре диска в поисках свободных индексов не является таким

критическим, как если бы оно имело место при поисках свободных

дисковых блоков.


список в суперблоке

------T-----T-----T-----T---------------------┐

│ 109 │ 106 │ 103 │ 100 │ │

L--+--+-----+-----+-----+----------------------

-------

│

│ 109

│ ------T-----T-----T-----T---------------T-----┐

L->│ 211 │ 208 │ 205 │ 202 │ │ 112 │

L-----+-----+-----+-----+---------------+------


(а) Первоначальная конфигурация


список в суперблоке

------T-----T---------------------------------┐

│ 109 │ 949 │ │

L--+--+-----+----------------------------------

-------

│

│ 109

│ ------T-----T-----T-----T---------------T-----┐

L->│ 211 │ 208 │ 205 │ 202 │ │ 112 │

L-----+-----+-----+-----+---------------+------


(б) После освобождения блока с номером 949


список в суперблоке

------T-----T-----T-----T---------------------┐

│ 109 │ 106 │ 103 │ 100 │ │

L--+--+-----+-----+-----+----------------------

-------

│

│ 109

│ ------T-----T-----T-----T---------------T-----┐

L->│ 211 │ 208 │ 205 │ 202 │ │ 112 │

L-----+-----+-----+-----+---------------+------


(в) После назначения блока с номером 949


список в суперблоке

------T-----T-----T-----T---------------T-----┐

│ 211 │ 208 │ 205 │ 202 │ │ 112 │

L--+--+-----+-----+-----+---------------+------

-------

│

│ 211

│ ------T-----T-----T-----T---------------T-----┐

L->│ 344 │ 341 │ 338 │ 335 │ │ 243 │

L-----+-----+-----+-----+---------------+------


(г) Новое заполнение списка в суперблоке после

назначения блока с номером 109


Рисунок 4.20. Запрашивание и освобождение дисковых блоков


4.8 ДРУГИЕ ТИПЫ ФАЙЛОВ


В системе UNIX поддерживаются и два других типа файлов: кана-

лы и специальные файлы. Канал, иногда называемый fifo (сокращенно

от "first-in-first-out" - "первым пришел - первым вышел" - пос-

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

обычного файла тем, что содержит временные данные: информация,

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

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

сана в канале, и система не допускает никаких отклонений от дан-

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

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

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

адресации. Конкретное представление о каналах можно будет полу-

чить в следующей главе.

Последним типом файлов в системе UNIX являются специальные

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

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

да-вывода. Оба подтипа обозначают устройства, и поэтому индексы

таких файлов не связаны ни с какой информацией. Вместо этого ин-

декс содержит два номера - старший и младший номера устройства.

Старший номер устройства указывает его тип, например, терминал

или диск, а младший номер устройства - числовой код, идентифици-

рующий устройство в группе однородных устройств. Более подробно

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


4.9 ВЫВОДЫ


Индекс представляет собой структуру данных, в которой описы-

ваются атрибуты файла, в том числе расположение информации файла

на диске. Существует две разновидности индекса: копия на диске, в

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

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

Алгоритмы ialloc и ifree управляют назначением файлу дискового

индекса во время выполнения системных операций creat, mknod, pipe

и unlink (см. следующую главу), а алгоритмы iget и iput управляют

выделением индексов в памяти в момент обращения процесса к файлу.

Алгоритм bmap определяет местонахождение дисковых блоков, принад-

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

тах от начала файла. Каталоги представляют собой файлы, которые

устанавливают соответствие между компонентами имен файлов и номе-

рами индексов. Алгоритм namei преобразует имена файлов, с которы-

ми работают процессы, в идентификаторы индексов, с которыми рабо-

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

вых блоков, используя алгоритмы alloc и free.

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

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

алгоритмы, работающие с рассмотренными структурами данных, доста-

точно просты. Сложности появляются тогда, когда возникает конку-

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

которые из этих проблем синхронизации рассмотрены в тексте. Тем

не менее, алгоритмы не настолько детально разработаны и могут

служить иллюстрацией простоты конструкции системы.

Вышеописанные структуры и алгоритмы работают внутри ядра и

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

темы (Рисунок 2.1), алгоритмы, рассмотренные в данной главе, име-

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

Следующая глава посвящена разбору обращений к операционной систе-

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

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

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


8. В версии V системы UNIX разрешается использовать не более 14

символов на каждую компоненту имени пути поиска. Алгоритм

namei отсекает лишние символы в компоненте. Что нужно сделать

в файловой системе и в соответствующих алгоритмах, чтобы стали

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

9. Предположим, что пользователь имеет закрытую версию системы

UNIX, причем он внес в нее такие изменения, что имя компоненты

теперь может состоять из 30 символов; закрытая версия системы

обеспечивает тот же способ хранения записей каталогов, как и

стандартная операционная система, за исключением того, что за-

писи каталогов имеют длину 32 байта вместо 16. Если пользова-

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