Geum.ru

The design of the unix operating system by Maurice J

Вид материалаРеферат
Системные операции для работы
Подобный материал:
1   ...   7   8   9   10   11   12   13   14   ...   55

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

когда процесс обратится к файлу ?

*10. Рассмотрим работу алгоритма namei по преобразованию имени

пути поиска в идентификатор индекса. В течение всего просмотра

ядро проверяет соответствие текущего рабочего индекса индексу

каталога. Может ли другой процесс удалить (unlink) каталог ?

Каким образом ядро предупреждает такие действия ? В следующей

главе мы вернемся к этой проблеме.

*11. Разработайте структуру каталога, повышающую эффективность

поиска имен файлов без использования линейного просмотра.

Рассмотрите два способа: хеширование и n-арные деревья.

*12. Разработайте алгоритм сокращения количества просмотров ката-

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

ребляемых имен.

*13. В идеальном случае в файловой системе не должно быть

свободных индексов с номерами, меньшими, чем номер "запомнен-

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

что это утверждение бывает ложным ?

14. Суперблок является дисковым блоком и содержит кроме списка

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

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

содержать больше номеров свободных блоков, чем может помес-

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

дисковых блоков. Какое число номеров свободных блоков было бы

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

*15. Рассмотрим вариант системной реализации, в котором свободные

дисковые блоки отслеживаются с помощью битовой маски вместо

использования списка блоков с указателями. Каковы преимущества

и неудобства такой схемы ?

СИСТЕМНЫЕ ОПЕРАЦИИ ДЛЯ РАБОТЫ

С ФАЙЛОВОЙ СИСТЕМОЙ


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

для файловой системы и алгоритмы работы с ними. В этой главе речь

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

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

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

файлам, такие как open, read, write, lseek и close, затем функции

создания новых файлов, а именно, creat и mknod, и, наконец, функ-

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

ме: chdir, chroot, chown, stat и fstat. Исследуются более сложные

системные функции: pipe и dup имеют важное значение для реализа-

ции каналов в shell'е; mount и umount расширяют видимое для поль-

зователя дерево файловых систем; link и unlink изменяют иерархи-

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

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

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

В последнем разделе главы речь пойдет о сопровождении файловой

системы. Глава знакомит с тремя структурами данных ядра: таблицей

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

системе файлов, таблицей пользовательских дескрипторов файлов, в

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

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

ция по каждой активной файловой системе.

На Рисунке 5.1 показана взаимосвязь между системными функция-

ми и алгоритмами, описанными ранее. Системные функции классифици-

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

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


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

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

+------T--------------T--------T-------T-------T---------T-------+

│ Воз- │ Используют │ Назна- │ Рабо- │ Ввод- │ Работа- │ Управ-│

│ вра- │ алгоритм │ чают │ тают │ вывод │ ют со │ ление │

│ щают │ namei │ индек- │ с ат- │ из │ структу-│ де- │

│ деск-│ │ сы │ рибу- │ файла │ рой фай-│ ревь- │

│ рип- │ │ │ тами │ │ ловых │ ями │

│ торы │ │ │ файла │ │ систем │ │

│ файла│ │ │ │ │ │ │

+------+--------------+--------+-------+-------+---------+-------+

│ open │ open stat │ │ │ │ │ │

│ creat│ creat link │ creat │ chown │ read │ │ │

│ dup │ chdir unlink│ mknod │ chmod │ write │ mount │ chdir │

│ pipe │ chroot mknod │ link │ stat │ lseek │ umount │ chown │

│ close│ chown mount │ unlink │ │ │ │ │

│ │ chmod umount│ │ │ │ │ │

+------+--------------+--------+-------+-------+---------+-------+

L---T--+--------------+--------+-------+-------+---------+----T---

│ Алгоритмы работы с файловой системой на нижнем уровне │

+-------------T------------------T------------------------+

│ namei │ │ │

+-------------+ ialloc ifree │ alloc free bmap │

│ iget iput │ │ │

+-------------+------------------+------------------------+

+---------------------------------------------------------+

│ алгоритмы работы с буферами │

+---------------------------------------------------------+

│ getblk brelse bread breada bwrite │

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


Рисунок 5.1. Функции для работы с файловой системой и их

связь с другими алгоритмами


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

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

* Системные функции, использующие алгоритм namei для анализа

имени пути поиска;

* Системные функции, назначающие и освобождающие индекс с ис-

пользованием алгоритмов ialloc и ifree;

* Системные функции, устанавливающие или изменяющие атрибуты

файла;

* Системные функции, позволяющие процессу производить ввод-вы-

вод данных с использованием алгоритмов alloc, free и

алгоритмов выделения буфера;

* Системные функции, изменяющие структуру файловой системы;

* Системные функции, позволяющие процессу изменять собственное

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


5.1 OPEN


Вызов системной функции open (открыть файл) - это первый шаг,

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

ле. Синтаксис вызова функции open:

fd = open(pathname,flags,modes);

где pathname - имя файла, flags указывает режим открытия (напри-

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

файлу в случае, если файл создается. Системная функция open возв-

ращает целое число (*), именуемое пользовательским дескриптором

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


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

(*) Все системные функции возвращают в случае неудачного заверше-

ния код -1. Код возврата, равный -1, больше не будет упоми-

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


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

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

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

возвращаемое системной функцией open.

Ядро просматривает файловую систему в поисках файла по его

имени, используя алгоритм namei (см. Рисунок 5.2). Оно проверяет

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

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

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

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

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

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

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

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

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

в конец, в этом случае ядро устанавливает значение смещения, рав-

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

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

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

запоминает указатель на эту запись. Указателем выступает дескрип-

тор файла, возвращаемый пользователю. Запись в таблице пользова-

тельских файлов указывает на запись в глобальной таблице файлов.


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

│ алгоритм open │

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

│ режим открытия │

│ права доступа (при создании файла) │

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

│ { │

│ превратить имя файла в идентификатор индекса (алгоритм │

│ namei); │

│ если (файл не существует или к нему не разрешен доступ) │

│ возвратить (код ошибки); │

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

│ зировать счетчик, смещение; │

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

│ файла, установить указатель на запись в таблице файлов;│

│ если (режим открытия подразумевает усечение файла) │

│ освободить все блоки файла (алгоритм free); │

│ снять блокировку (с индекса); /* индекс заблокирован │

│ выше, в алгоритме │

│ namei */ │


│ возвратить (пользовательский дескриптор файла); │

│ } │

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


Рисунок 5.2. Алгоритм открытия файла


Предположим, что процесс, открывая файл "/etc/passwd" дважды,

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

ды файл "local" для чтения и для записи (**), выполняет следующий

набор операторов:


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


(**) В описании вызова системной функции open содержатся три па-

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

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

них. Компилятор с языка Си не проверяет правильность коли-

чества параметров. В системе первые два параметра и третий

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

обычно ядру. Ядро не проверяет наличие третьего параметра,

если только необходимость в нем не вытекает из значения вто-

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

два параметра.


таблица пользова-

тельских дескрип-

торов файла таблица файлов таблица индексов

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

0│ │ │ │ │ │

+---------+ │ │ │ │

1│ │ │ │ │ │

+---------+ +------------+ │ │

2│ │ │ │ │ │

+---------+ │ │ │ │

3│ ----+----┐ │ │ │ │

+---------+ │ │ │ +--------------+

4│ ----+---┐│ │ │ ----->│ счет- │

+---------+ ││ │ │ │---->│ чик (/etc/ │

5│ ----+--┐││ +------------+ ││ │ 2 passwd)│

+---------+ │││ │ счет- │ ││ +--------------+

6│ │ ││L-->│ чик Чтение+---│ │ │

+---------+ ││ │ 1 │ │ │ │

7│ │ ││ +------------+ │ │ │

+---------+ ││ │ │ │ │ │

│ │ ││ │ │ │ │ │

│ │ ││ │ │ │ │ │

│ │ ││ │ │ │ │ │

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

││ │ счет- Чте-│ │ │ │

│L--->│ чик ние-+---│-┐ │ │

│ │ 1 Запись│ │ │ │ │

│ +------------+ │ │ │ │


│ │ │ │ │ +--------------+

│ │ │ │ │ │ счет- │

│ │ │ │ L->│ чик (local)│

│ │ │ │ │ 1 │

│ │ │ │ +--------------+

│ │ │ │ │ │

│ +------------+ │ │ │

│ │ счет- │ │ │ │

L---->│ чик Запись+---- │ │

│ 1 │ │ │

+------------+ │ │

│ │ │ │

│ │ │ │

│ │ │ │

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


Рисунок 5.3. Структуры данных после открытия


fd1 = open("/etc/passwd",O_RDONLY);

fd2 = open("local",O_RDWR);

fd3 = open("/etc/passwd",O_WRONLY);


На Рисунке 5.3 показана взаимосвязь между таблицей индексов,

таблицей файлов и таблицей пользовательских дескрипторов файла.

Каждый вызов функции open возвращает процессу дескриптор файла, а

соответствующая запись в таблице пользовательских дескрипторов

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

даже один и тот же файл ("/etc/passwd") открывается дважды. Запи-


таблицы пользова-

тельских дескрип-

торов файла

(процесс A) таблица файлов таблица индексов

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

0│ │ │ │ │ │

+---------+ │ │ │ │

1│ │ │ │ │ │

+---------+ +------------+ │ │

2│ │ │ │ │ │

+---------+ │ │ │ │

3│ ----+----┐ │ │ │ │

+---------+ │ │ │ +--------------+

4│ ----+---┐│ │ │ ----->│ счет- │

+---------+ ││ │ │ │---->│ чик (/etc/ │

5│ ----+--┐││ +------------+ ││--->│ 3 passwd)│

+---------+ │││ │ счет- │ │││ +--------------+

│ │ ││L-->│ чик Чтение+---││ │ │

│ │ ││ │ 1 │ ││ │ │

│ │ ││ +------------+ ││ │ │

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

││ │ │ ││ │ │

(процесс B) ││ │ │ ││ │ │

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

0│ │ ││ +------------+ ││ │ │

+---------+ ││ │ счет- Чте-│ ││ │ │

1│ │ │L--->│ чик ние-+---││┐ │ │

+---------+ │ │ 1 Запись│ │││ │ │

2│ │ │ +------------+ │││ │ │

+---------+ │ │ │ │││ +--------------+

3│ ----+--│--┐ │ │ │││ │ счет- │

+---------+ │ │ │ │ ││L->│ чик (local)│

4│ ----+-┐│ │ │ │ ││ │ 1 │

+---------+ ││ │ │ │ ││ +--------------+

5│ │ ││ │ │ │ ││ │ │

+---------+ ││ │ +------------+ ││ │ │

│ │ ││ │ │ счет- │ ││ │ │

│ │ ││ L->│ чик Чтение+----│ │ │

│ │ ││ │ 1 │ │ │ │

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

││ │ │ │ │ │

││ │ │ │ │ │

││ │ │ │ │ │

││ │ │ │ +--------------+

││ │ │ │ │ счет- │

││ +------------+ │-->│ чик (private)│

││ │ счет- │ ││ │ 1 │

│L---->│ чик Запись+-----│ +--------------+

│ │ 1 │ │ │ │

│ +------------+ │ │ │

│ │ │ │ │ │

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

│ │ │ │

│ +------------+ │

│ │ счет- │ │

L----->│ чик Чтение+------

│ 1 │

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


Рисунок 5.4. Структуры данных после того, как два процесса

произвели открытие файлов


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

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

ся в памяти. Процесс может обращаться к файлу "/etc/passwd" с

чтением или записью, но только через дескрипторы файла, имеющие

значения 3 и 5 (см. рисунок). Ядро запоминает разрешение на чте-

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

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

полняет следующий набор операторов:

fd1 = open("/etc/passwd",O_RDONLY);

fd2 = open("private",O_RDONLY);

На Рисунке 5.4 показана взаимосвязь между соответствующими

структурами данных, когда оба процесса (и больше никто) имеют от-

крытые файлы. Снова результатом каждого вызова функции open явля-

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

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

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

памяти.

Запись в таблице пользовательских дескрипторов файла по умол-

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

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

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

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

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

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

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

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

смещения нескольким пользовательским дескрипторам файла (см.

[Thompson 78], стр.1943). В системных функциях dup и fork, расс-

матриваемых в разделах 5.13 и 7.1, при работе со структурами дан-

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

Первые три пользовательских дескриптора (0, 1 и 2) именуются

дескрипторами файлов: стандартного ввода, стандартного вывода и

стандартного файла ошибок. Процессы в системе UNIX по договорен-

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

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

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

для записи сообщений об ошибках. В операционной системе нет ника-

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

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

вые дескрипторы, имеющие значения 4, 6 и 11, являются

специальными, но более естественно начинать отсчет с 0 (как в

языке Си). Принятие соглашения сразу всеми пользовательскими

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

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

кий терминал (см. главу 10) служит и в качестве стандартного вво-

да, и в качестве стандартного вывода и в качестве стандартного

устройства вывода сообщений об ошибках.


5.2 READ


Синтаксис вызова системной функции read (читать):

number = read(fd,buffer,count)

где fd - дескриптор файла, возвращаемый функцией open, buffer -

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

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

нения функции read, count - количество байт, которые пользователю

нужно прочитать, number - количество фактически прочитанных байт.

На Рисунке 5.5 приведен алгоритм read, выполняющий чтение обычно-

го файла. Ядро обращается в таблице файлов к записи, которая со-

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


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

│ алгоритм read │

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

│ адрес буфера в пользовательском про- │

│ цессе │

│ количество байт, которые нужно прочи- │

│ тать │

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

│ зовательское пространство │

│ { │

│ обратиться к записи в таблице файлов по значению пользо-│

│ вательского дескриптора файла; │

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

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

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

│ ввода-вывода для пользователя; │

│ получить индекс по записи в таблице файлов; │

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

│ установить значение смещения в байтах для адресного │

│ пространства процесса по значению смещения в таблице │

│ файлов; │

│ выполнить (пока значение счетчика байтов не станет удов-│

│ летворительным) │

│ { │

│ превратить смещение в файле в номер дискового блока │

│ (алгоритм bmap); │

│ вычислить смещение внутри блока и количество байт, │

│ которые будут прочитаны; │

│ если (количество байт для чтения равно 0) │

│ /* попытка чтения конца файла */ │

│ прерваться; /* выход из цикла */ │

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

│ чтение с продвижением, и алгоритм bread - в против- │

│ ном случае); │

│ скопировать данные из системного буфера по адресу │

│ пользователя; │


│ скорректировать значения полей в адресном простран- │

│ стве процесса, указывающие смещение в байтах внутри │