Страница:
Когда ядру нужно выделить блок из файловой системы (алгоритм alloc, Рисунок 4.19), оно выделяет следующий из блоков, имеющихся в списке в суперблоке. Выделенный однажды, блок не может быть переназначен до тех пор, пока не освободится. Если выделенный блок является последним блоком, имеющимся в кеше суперблока, ядро трактует его как указатель на блок, в котором хранится список свободных блоков. Ядро читает блок, заполняет массив в суперблоке новым списком номеров блоков и после этого продолжает работу с первоначальным номером блока. Оно выделяет буфер для блока и очищает содержимое буфера (обнуляет его). Дисковый блок теперь считается назначенным и у ядра есть буфер для работы с ним. Если в файловой системе нет свободных блоков, вызывающий процесс получает сообщение об ошибке.
Если процесс записывает в файл большой объем информации, он неоднократно запрашивает у системы блоки для хранения информации, но ядро назначает каждый раз только по одному блоку. Программа mkfs пытается организовать первоначальный связанный список номеров свободных блоков так, чтобы номера блоков, передаваемых файлу, были рядом друг с другом. Благодаря этому повышается производительность, поскольку сокращается время поиска на диске и время ожидания при последовательном чтении файла процессом. На Рисунке 4.18 номера блоков даны в настоящем формате, определяемом скоростью вращения диска. К сожалению, очередность номеров блоков в списке свободных блоков перепутана в связи с частыми обращениями к списку со стороны процессов, ведущих запись в файлы и удаляющих их, в результате чего номера блоков поступают в список и покидают его в случайном порядке. Ядро не предпринимает попыток сортировать номера блоков в списке.
Рисунок 4.18. Список номеров свободных дисковых блоков с указателями
Алгоритм освобождения блока free — обратный алгоритму выделения блока. Если список в суперблоке не полон, номер вновь освобожденного блока включается в этот список. Если, однако, список полон, вновь освобожденный блок становится связным блоком; ядро переписывает в него список из суперблока и копирует блок на диск. Затем номер вновь освобожденного блока включается в список свободных блоков в суперблоке. Этот номер становится единственным номером в списке.
На Рисунке 4.20 показана последовательность операций alloc и free для случая, когда в исходный момент список свободных блоков содержал один элемент. Ядро освобождает блок 949 и включает номер блока в список. Затем оно выделяет этот блок и удаляет его номер из списка. Наконец, оно выделяет блок 109 и удаляет его номер из списка. Поскольку список свободных блоков в суперблоке теперь пуст, ядро снова наполняет список, копируя в него содержимое блока 109, являющегося следующей связью в списке с указателями. На Рисунке 4.20(г) показан заполненный список в суперблоке и следующий связной блок с номером 211.
алгоритм alloc /* выделение блока файловой системы */
входная информация: номер файловой системы
выходная информация: буфер для нового блока
{
do (пока суперблок заблокирован)
sleep (до того момента, когда с суперблока будет снята блокировка);
удалить блок из списка свободных блоков в суперблоке;
if (из списка удален последний блок) {
заблокировать суперблок;
прочитать блок, только что взятый из списка свободных (алгоритм bread);
скопировать номера блоков, хранящиеся в данном блоке, в суперблок;
освободить блочный буфер (алгоритм brelse);
снять блокировку с суперблока;
возобновить выполнение процессов (после снятия блокировки с суперблока);
}
получить буфер для блока, удаленного из списка (алгоритм getblk);
обнулить содержимое буфера;
уменьшить общее число свободных блоков;
пометить суперблок как «измененный»;
return буфер;
}
Рисунок 4.19. Алгоритм выделения дискового блока
Алгоритмы назначения и освобождения индексов и дисковых блоков сходятся в том, что ядро использует суперблок в качестве кеша, хранящего указатели на свободные ресурсы — номера блоков и номера индексов. Оно поддерживает список номеров блоков с указателями, такой, что каждый номер свободного блока в файловой системе появляется в некотором элементе списка, но ядро не поддерживает такого списка для свободных индексов. Тому есть три причины.
Ядро устанавливает, свободен ли индекс или нет, проверяя: если поле типа файла очищено, индекс свободен. Ядро не нуждается в другом механизме описания свободных индексов. Тем не менее, оно не может определить, свободен ли блок или нет, только взглянув на него. Ядро не может уловить различия между маской, показывающей, что блок свободен, и информацией, случайно имеющей сходную маску. Следовательно, ядро нуждается во внешнем механизме идентификации свободных блоков, в качестве него в традиционных реализациях системы используется список с указателями.
Сама конструкция дисковых блоков наводит на мысль об использовании списков с указателями: в дисковом блоке легко разместить большие списки номеров свободных блоков. Но индексы не имеют подходящего места для массового хранения списков номеров свободных индексов.
Пользователи имеют склонность чаще расходовать дисковые блоки, нежели индексы, поэтому кажущееся запаздывание в работе при просмотре диска в поисках свободных индексов не является таким критическим, как если бы оно имело место при поисках свободных дисковых блоков.
Рисунок 4.20. Запрашивание и освобождение дисковых блоков
4.8 ДРУГИЕ ТИПЫ ФАЙЛОВ
4.9 ВЫВОДЫ
4.10 УПРАЖНЕНИЯ
ГЛАВА 5. СИСТЕМНЫЕ ОПЕРАЦИИ ДЛЯ РАБОТЫ С ФАЙЛОВОЙ СИСТЕМОЙ
5.1 OPEN
5.2 READ
Если процесс записывает в файл большой объем информации, он неоднократно запрашивает у системы блоки для хранения информации, но ядро назначает каждый раз только по одному блоку. Программа mkfs пытается организовать первоначальный связанный список номеров свободных блоков так, чтобы номера блоков, передаваемых файлу, были рядом друг с другом. Благодаря этому повышается производительность, поскольку сокращается время поиска на диске и время ожидания при последовательном чтении файла процессом. На Рисунке 4.18 номера блоков даны в настоящем формате, определяемом скоростью вращения диска. К сожалению, очередность номеров блоков в списке свободных блоков перепутана в связи с частыми обращениями к списку со стороны процессов, ведущих запись в файлы и удаляющих их, в результате чего номера блоков поступают в список и покидают его в случайном порядке. Ядро не предпринимает попыток сортировать номера блоков в списке.
Рисунок 4.18. Список номеров свободных дисковых блоков с указателями
Алгоритм освобождения блока free — обратный алгоритму выделения блока. Если список в суперблоке не полон, номер вновь освобожденного блока включается в этот список. Если, однако, список полон, вновь освобожденный блок становится связным блоком; ядро переписывает в него список из суперблока и копирует блок на диск. Затем номер вновь освобожденного блока включается в список свободных блоков в суперблоке. Этот номер становится единственным номером в списке.
На Рисунке 4.20 показана последовательность операций alloc и free для случая, когда в исходный момент список свободных блоков содержал один элемент. Ядро освобождает блок 949 и включает номер блока в список. Затем оно выделяет этот блок и удаляет его номер из списка. Наконец, оно выделяет блок 109 и удаляет его номер из списка. Поскольку список свободных блоков в суперблоке теперь пуст, ядро снова наполняет список, копируя в него содержимое блока 109, являющегося следующей связью в списке с указателями. На Рисунке 4.20(г) показан заполненный список в суперблоке и следующий связной блок с номером 211.
алгоритм alloc /* выделение блока файловой системы */
входная информация: номер файловой системы
выходная информация: буфер для нового блока
{
do (пока суперблок заблокирован)
sleep (до того момента, когда с суперблока будет снята блокировка);
удалить блок из списка свободных блоков в суперблоке;
if (из списка удален последний блок) {
заблокировать суперблок;
прочитать блок, только что взятый из списка свободных (алгоритм bread);
скопировать номера блоков, хранящиеся в данном блоке, в суперблок;
освободить блочный буфер (алгоритм brelse);
снять блокировку с суперблока;
возобновить выполнение процессов (после снятия блокировки с суперблока);
}
получить буфер для блока, удаленного из списка (алгоритм getblk);
обнулить содержимое буфера;
уменьшить общее число свободных блоков;
пометить суперблок как «измененный»;
return буфер;
}
Рисунок 4.19. Алгоритм выделения дискового блока
Алгоритмы назначения и освобождения индексов и дисковых блоков сходятся в том, что ядро использует суперблок в качестве кеша, хранящего указатели на свободные ресурсы — номера блоков и номера индексов. Оно поддерживает список номеров блоков с указателями, такой, что каждый номер свободного блока в файловой системе появляется в некотором элементе списка, но ядро не поддерживает такого списка для свободных индексов. Тому есть три причины.
Ядро устанавливает, свободен ли индекс или нет, проверяя: если поле типа файла очищено, индекс свободен. Ядро не нуждается в другом механизме описания свободных индексов. Тем не менее, оно не может определить, свободен ли блок или нет, только взглянув на него. Ядро не может уловить различия между маской, показывающей, что блок свободен, и информацией, случайно имеющей сходную маску. Следовательно, ядро нуждается во внешнем механизме идентификации свободных блоков, в качестве него в традиционных реализациях системы используется список с указателями.
Сама конструкция дисковых блоков наводит на мысль об использовании списков с указателями: в дисковом блоке легко разместить большие списки номеров свободных блоков. Но индексы не имеют подходящего места для массового хранения списков номеров свободных индексов.
Пользователи имеют склонность чаще расходовать дисковые блоки, нежели индексы, поэтому кажущееся запаздывание в работе при просмотре диска в поисках свободных индексов не является таким критическим, как если бы оно имело место при поисках свободных дисковых блоков.
4.8 ДРУГИЕ ТИПЫ ФАЙЛОВ
В системе UNIX поддерживаются и два других типа файлов: каналы и специальные файлы. Канал, иногда называемый fifo (сокращенно от «first-in-first-out» — «первым пришел — первым вышел» — поскольку обслуживает запросы в порядке поступления), отличается от обычного файла тем, что содержит временные данные: информация, однажды считанная из канала, не может быть прочитана вновь. Кроме того, информация читается в том порядке, в котором она была записана в канале, и система не допускает никаких отклонений от данного порядка. Способ хранения ядром информации в канале не отличается от способа ее хранения в обычном файле, за исключением того, что здесь используются только блоки прямой, а не косвенной, адресации. Конкретное представление о каналах можно будет получить в следующей главе.
Последним типом файлов в системе UNIX являются специальные файлы, к которым относятся специальные файлы устройств ввода-вывода блоками и специальные файлы устройств посимвольного ввода-вывода. Оба подтипа обозначают устройства, и поэтому индексы таких файлов не связаны ни с какой информацией. Вместо этого индекс содержит два номера — старший и младший номера устройства. Старший номер устройства указывает его тип, например, терминал или диск, а младший номер устройства — числовой код, идентифицирующий устройство в группе однородных устройств. Более подробно специальные файлы устройств рассматриваются в главе 10.
Последним типом файлов в системе UNIX являются специальные файлы, к которым относятся специальные файлы устройств ввода-вывода блоками и специальные файлы устройств посимвольного ввода-вывода. Оба подтипа обозначают устройства, и поэтому индексы таких файлов не связаны ни с какой информацией. Вместо этого индекс содержит два номера — старший и младший номера устройства. Старший номер устройства указывает его тип, например, терминал или диск, а младший номер устройства — числовой код, идентифицирующий устройство в группе однородных устройств. Более подробно специальные файлы устройств рассматриваются в главе 10.
4.9 ВЫВОДЫ
Индекс представляет собой структуру данных, в которой описываются атрибуты файла, в том числе расположение информации файла на диске. Существует две разновидности индекса: копия на диске, в которой хранится информация индекса, пока файл находится в работе, и копия в памяти, где хранится информация об активных файлах. Алгоритмы ialloc и ifree управляют назначением файлу дискового индекса во время выполнения системных операций creat, mknod, pipe и unlink (см. следующую главу), а алгоритмы iget и iput управляют выделением индексов в памяти в момент обращения процесса к файлу. Алгоритм bmap определяет местонахождение дисковых блоков, принадлежащих файлу, используя предварительно заданное смещение в байтах от начала файла. Каталоги представляют собой файлы, которые устанавливают соответствие между компонентами имен файлов и номерами индексов. Алгоритм namei преобразует имена файлов, с которыми работают процессы, в идентификаторы индексов, с которыми работает ядро. Наконец, ядро управляет назначением файлу новых дисковых блоков, используя алгоритмы alloc и free.
Структуры данных, рассмотренные в настоящей главе, состоят из связанных списков, хеш-очередей и линейных массивов, и поэтому алгоритмы, работающие с рассмотренными структурами данных, достаточно просты. Сложности появляются тогда, когда возникает конкуренция, вызываемая взаимодействием алгоритмов между собой, и некоторые из этих проблем синхронизации рассмотрены в тексте. Тем не менее, алгоритмы не настолько детально разработаны и могут служить иллюстрацией простоты конструкции системы.
Вышеописанные структуры и алгоритмы работают внутри ядра и невидимы для пользователя. С точки зрения общей архитектуры системы (Рисунок 2.1), алгоритмы, рассмотренные в данной главе, имеют отношение к нижней половине подсистемы управления файлами. Следующая глава посвящена разбору обращений к операционной системе, обеспечивающих функционирование пользовательского интерфейса, и описанию верхней половины подсистемы управления файлами, из которой вызывается выполнение рассмотренных здесь алгоритмов.
Структуры данных, рассмотренные в настоящей главе, состоят из связанных списков, хеш-очередей и линейных массивов, и поэтому алгоритмы, работающие с рассмотренными структурами данных, достаточно просты. Сложности появляются тогда, когда возникает конкуренция, вызываемая взаимодействием алгоритмов между собой, и некоторые из этих проблем синхронизации рассмотрены в тексте. Тем не менее, алгоритмы не настолько детально разработаны и могут служить иллюстрацией простоты конструкции системы.
Вышеописанные структуры и алгоритмы работают внутри ядра и невидимы для пользователя. С точки зрения общей архитектуры системы (Рисунок 2.1), алгоритмы, рассмотренные в данной главе, имеют отношение к нижней половине подсистемы управления файлами. Следующая глава посвящена разбору обращений к операционной системе, обеспечивающих функционирование пользовательского интерфейса, и описанию верхней половины подсистемы управления файлами, из которой вызывается выполнение рассмотренных здесь алгоритмов.
4.10 УПРАЖНЕНИЯ
1. В версии V системы UNIX разрешается использовать не более 14 символов на каждую компоненту имени пути поиска. Алгоритм namei отсекает лишние символы в компоненте. Что нужно сделать в файловой системе и в соответствующих алгоритмах, чтобы стали допустимыми имена компонент произвольной длины?
2. Предположим, что пользователь имеет закрытую версию системы UNIX, причем он внес в нее такие изменения, что имя компоненты теперь может состоять из 30 символов; закрытая версия системы обеспечивает тот же способ хранения записей каталогов, как и стандартная операционная система, за исключением того, что записи каталогов имеют длину 32 байта вместо 16. Если пользователь смонтирует закрытую файловую систему в стандартной операционной среде, что произойдет во время работы алгоритма namei, когда процесс обратится к файлу?
*3. Рассмотрим работу алгоритма namei по преобразованию имени пути поиска в идентификатор индекса. В течение всего просмотра ядро проверяет соответствие текущего рабочего индекса индексу каталога. Может ли другой процесс удалить (unlink) каталог? Каким образом ядро предупреждает такие действия? В следующей главе мы вернемся к этой проблеме.
*4. Разработайте структуру каталога, повышающую эффективность поиска имен файлов без использования линейного просмотра. Рассмотрите два способа: хеширование и n-арные деревья.
*5. Разработайте алгоритм сокращения количества просмотров каталога в поисках имени файла, используя запоминание часто употребляемых имен.
*6. В идеальном случае в файловой системе не должно быть свободных индексов с номерами, меньшими, чем номер «запомненного» индекса, используемый алгоритмом ialloc. Как случается, что это утверждение бывает ложным?
7. Суперблок является дисковым блоком и содержит кроме списка свободных блоков и другую информацию, как показано в данной главе. Поэтому список свободных блоков в суперблоке не может содержать больше номеров свободных блоков, чем может поместиться в одном дисковом блоке в связанном списке свободных дисковых блоков. Какое число номеров свободных блоков было бы оптимальным для хранения в одном блоке из связанного списка?
2. Предположим, что пользователь имеет закрытую версию системы UNIX, причем он внес в нее такие изменения, что имя компоненты теперь может состоять из 30 символов; закрытая версия системы обеспечивает тот же способ хранения записей каталогов, как и стандартная операционная система, за исключением того, что записи каталогов имеют длину 32 байта вместо 16. Если пользователь смонтирует закрытую файловую систему в стандартной операционной среде, что произойдет во время работы алгоритма namei, когда процесс обратится к файлу?
*3. Рассмотрим работу алгоритма namei по преобразованию имени пути поиска в идентификатор индекса. В течение всего просмотра ядро проверяет соответствие текущего рабочего индекса индексу каталога. Может ли другой процесс удалить (unlink) каталог? Каким образом ядро предупреждает такие действия? В следующей главе мы вернемся к этой проблеме.
*4. Разработайте структуру каталога, повышающую эффективность поиска имен файлов без использования линейного просмотра. Рассмотрите два способа: хеширование и n-арные деревья.
*5. Разработайте алгоритм сокращения количества просмотров каталога в поисках имени файла, используя запоминание часто употребляемых имен.
*6. В идеальном случае в файловой системе не должно быть свободных индексов с номерами, меньшими, чем номер «запомненного» индекса, используемый алгоритмом ialloc. Как случается, что это утверждение бывает ложным?
7. Суперблок является дисковым блоком и содержит кроме списка свободных блоков и другую информацию, как показано в данной главе. Поэтому список свободных блоков в суперблоке не может содержать больше номеров свободных блоков, чем может поместиться в одном дисковом блоке в связанном списке свободных дисковых блоков. Какое число номеров свободных блоков было бы оптимальным для хранения в одном блоке из связанного списка?
ГЛАВА 5. СИСТЕМНЫЕ ОПЕРАЦИИ ДЛЯ РАБОТЫ С ФАЙЛОВОЙ СИСТЕМОЙ
В последней главе рассматривались внутренние структуры данных для файловой системы и алгоритмы работы с ними. В этой главе речь пойдет о системных функциях для работы с файловой системой с использованием понятий, введенных в предыдущей главе. Рассматриваются системные функции, обеспечивающие обращение к существующим файлам, такие как open, read, write, lseek и close, затем функции создания новых файлов, а именно, creat и mknod, и, наконец, функции для работы с индексом или для передвижения по файловой системе: chdir, chroot, chown, stat и fstat. Исследуются более сложные системные функции: pipe и dup имеют важное значение для реализации каналов в shell'е; mount и umount расширяют видимое для пользователя дерево файловых систем; link и unlink изменяют иерархическую структуру файловой системы. Затем дается представление об абстракциях, связанных с файловой системой, в отношении поддержки различных файловых систем, подчиняющихся стандартным интерфейсам. В последнем разделе главы речь пойдет о сопровождении файловой системы. Глава знакомит с тремя структурами данных ядра: таблицей файлов, в которой каждая запись связана с одним из открытых в системе файлов, таблицей пользовательских дескрипторов файлов, в которой каждая запись связана с файловым дескриптором, известным процессу, и таблицей монтирования, в которой содержится информация по каждой активной файловой системе.
Рисунок 5.1. Функции для работы с файловой системой и их связь с другими алгоритмами
На Рисунке 5.1 показана взаимосвязь между системными функциями и алгоритмами, описанными ранее. Системные функции классифицируются на несколько категорий, хотя некоторые из функций присутствуют более, чем в одной категории:
• Системные функции, возвращающие дескрипторы файлов для использования другими системными функциями;
• Системные функции, использующие алгоритм namei для анализа имени пути поиска;
• Системные функции, назначающие и освобождающие индекс с использованием алгоритмов ialloc и ifree;
• Системные функции, устанавливающие или изменяющие атрибуты файла;
• Системные функции, позволяющие процессу производить ввод-вывод данных с использованием алгоритмов alloc, free и алгоритмов выделения буфера;
• Системные функции, изменяющие структуру файловой системы;
• Системные функции, позволяющие процессу изменять собственное представление о структуре дерева файловой системы.
| Функции для работы с файловой системой | ||||||
|---|---|---|---|---|---|---|
| Возвращают дескрипторы файла | Используют алгоритм namei | Назначают индексы | Работают с атрибутами файла | Ввод-вывод из файла | Работают со структурой файловых систем | Управление деревьями |
| open creat dup pipe close | open stat creat link chdir chroot chown chmod unlink mknod mount umount | creat mknod link unlink | chown chmod stat | read write lseek | mount umount | chdir chown |
| Алгоритмы работы с файловой системой на нижнем уровне | ||||||
| namei iget iput bmap | ialloc ifree | alloc free bmap | ||||
| Алгоритмы работы с буферами | ||||||
| getblk brelse bread breada bwrite | ||||||
Рисунок 5.1. Функции для работы с файловой системой и их связь с другими алгоритмами
На Рисунке 5.1 показана взаимосвязь между системными функциями и алгоритмами, описанными ранее. Системные функции классифицируются на несколько категорий, хотя некоторые из функций присутствуют более, чем в одной категории:
• Системные функции, возвращающие дескрипторы файлов для использования другими системными функциями;
• Системные функции, использующие алгоритм namei для анализа имени пути поиска;
• Системные функции, назначающие и освобождающие индекс с использованием алгоритмов ialloc и ifree;
• Системные функции, устанавливающие или изменяющие атрибуты файла;
• Системные функции, позволяющие процессу производить ввод-вывод данных с использованием алгоритмов alloc, free и алгоритмов выделения буфера;
• Системные функции, изменяющие структуру файловой системы;
• Системные функции, позволяющие процессу изменять собственное представление о структуре дерева файловой системы.
5.1 OPEN
Вызов системной функции open (открыть файл) — это первый шаг, который должен сделать процесс, чтобы обратиться к данным в файле. Синтаксис вызова функции open:
fd = open(pathname, flags, modes);
где pathname — имя файла, flags указывает режим открытия (например, для чтения или записи), а modes содержит права доступа к файлу в случае, если файл создается. Системная функция open возвращает целое число [14], именуемое пользовательским дескриптором файла. Другие операции над файлами, такие как чтение, запись, позиционирование головок чтения-записи, воспроизведение дескриптора файла, установка параметров ввода-вывода, определение статуса файла и закрытие файла, используют значение дескриптора файла, возвращаемое системной функцией open.
Ядро просматривает файловую систему в поисках файла по его имени, используя алгоритм namei (см. Рисунок 5.2). Оно проверяет права на открытие файла после того, как обнаружит копию индекса файла в памяти, и выделяет открываемому файлу запись в таблице файлов. Запись таблицы файлов содержит указатель на индекс открытого файла и поле, в котором хранится смещение в байтах от начала файла до места, откуда предполагается начинать выполнение последующих операций чтения или записи. Ядро сбрасывает это смещение в 0 во время открытия файла, имея в виду, что исходная операция чтения или записи по умолчанию будет производиться с начала файла. С другой стороны, процесс может открыть файл в режиме записи в конец, в этом случае ядро устанавливает значение смещения, равное размеру файла. Ядро выделяет запись в личной (закрытой) таблице в адресном пространстве задачи, выделенном процессу (таблица эта называется таблицей пользовательских дескрипторов файлов), и запоминает указатель на эту запись. Указателем выступает дескриптор файла, возвращаемый пользователю. Запись в таблице пользовательских файлов указывает на запись в глобальной таблице файлов.
алгоритм open
входная информация:
имя файла
режим открытия
права доступа (при создании файла)
выходная информация: дескриптор файла
{
превратить имя файла в идентификатор индекса (алгоритм namei);
if (файл не существует или к нему не разрешен доступ) return (код ошибки);
выделить для индекса запись в таблице файлов, инициализировать счетчик, смещение;
выделить запись в таблице пользовательских дескрипторов файла, установить указатель на запись в таблице файлов;
if (режим открытия подразумевает усечение файла) освободить все блоки файла (алгоритм free);
снять блокировку (с индекса); /* индекс заблокирован выше, в алгоритме namei */
return (пользовательский дескриптор файла);
}
Рисунок 5.2. Алгоритм открытия файла
Предположим, что процесс, открывая файл «/etc/passwd» дважды, один раз только для чтения и один раз только для записи, и однажды файл «local» для чтения и для записи [15], выполняет следующий набор операторов:
fd1 = open("/etc/passwd", O_RDONLY);
fd2 = open("local", O_RDWR);
fd3 = open("/etc/passwd", O_WRONLY);
На Рисунке 5.3 показана взаимосвязь между таблицей индексов, таблицей файлов и таблицей пользовательских дескрипторов файла. Каждый вызов функции open возвращает процессу дескриптор файла, а соответствующая запись в таблице пользовательских дескрипторов файла указывает на уникальную запись в таблице файлов ядра, пусть даже один и тот же файл ("/etc/passwd") открывается дважды. Записи в таблице файлов для всех экземпляров одного и того же открытого файла указывают на одну запись в таблице индексов, хранящихся в памяти. Процесс может обращаться к файлу «/etc/passwd» с чтением или записью, но только через дескрипторы файла, имеющие значения 3 и 5 (см. Рисунок). Ядро запоминает разрешение на чтение или запись в файл в строке таблицы файлов, выделенной во время выполнения функции open. Предположим, что второй процесс выполняет следующий набор операторов:
fd1 = open("/etc/passwd", O_RDONLY);
fd2 = open("private", O_RDONLY);
Рисунок 5.3. Структуры данных после открытия
На Рисунке 5.4 показана взаимосвязь между соответствующими структурами данных, когда оба процесса (и больше никто) имеют открытые файлы. Снова результатом каждого вызова функции open является выделение уникальной точки входа в таблице пользовательских дескрипторов файла и в таблице файлов ядра, и ядро хранит не более одной записи на каждый файл в таблице индексов, размещенных в памяти.
Запись в таблице пользовательских дескрипторов файла по умолчанию хранит смещение в файле до адреса следующей операции ввода-вывода и указывает непосредственно на точку входа в таблице индексов для файла, устраняя необходимость в отдельной таблице файлов ядра. Вышеприведенные примеры показывают взаимосвязь между записями таблицы пользовательских дескрипторов файла и записями в таблице файлов ядра типа «один к одному». Томпсон, однако, отмечает, что им была реализована таблица файлов как отдельная структура, позволяющая совместно использовать один и тот же указатель смещения нескольким пользовательским дескрипторам файла (см. [Thompson 78], стр.1943). В системных функциях dup и fork, рассматриваемых в разделах 5.13 и 7.1, при работе со структурами данных допускается такое совместное использование.
Рисунок 5.4. Структуры данных после того, как два процесса произвели открытие файлов
Первые три пользовательских дескриптора (0, 1 и 2) именуются дескрипторами файлов: стандартного ввода, стандартного вывода и стандартного файла ошибок. Процессы в системе UNIX по договоренности используют дескриптор файла стандартного ввода при чтении вводимой информации, дескриптор файла стандартного вывода при записи выводимой информации и дескриптор стандартного файла ошибок для записи сообщений об ошибках. В операционной системе нет никакого указания на то, что эти дескрипторы файлов являются специальными. Группа пользователей может условиться о том, что файловые дескрипторы, имеющие значения 4, 6 и 11, являются специальными, но более естественно начинать отсчет с 0 (как в языке Си). Принятие соглашения сразу всеми пользовательскими программами облегчит связь между ними при использовании каналов, в чем мы убедимся в дальнейшем, изучая главу 7. Обычно операторский терминал (см. главу 10) служит и в качестве стандартного ввода, и в качестве стандартного вывода и в качестве стандартного устройства вывода сообщений об ошибках.
fd = open(pathname, flags, modes);
где pathname — имя файла, flags указывает режим открытия (например, для чтения или записи), а modes содержит права доступа к файлу в случае, если файл создается. Системная функция open возвращает целое число [14], именуемое пользовательским дескриптором файла. Другие операции над файлами, такие как чтение, запись, позиционирование головок чтения-записи, воспроизведение дескриптора файла, установка параметров ввода-вывода, определение статуса файла и закрытие файла, используют значение дескриптора файла, возвращаемое системной функцией open.
Ядро просматривает файловую систему в поисках файла по его имени, используя алгоритм namei (см. Рисунок 5.2). Оно проверяет права на открытие файла после того, как обнаружит копию индекса файла в памяти, и выделяет открываемому файлу запись в таблице файлов. Запись таблицы файлов содержит указатель на индекс открытого файла и поле, в котором хранится смещение в байтах от начала файла до места, откуда предполагается начинать выполнение последующих операций чтения или записи. Ядро сбрасывает это смещение в 0 во время открытия файла, имея в виду, что исходная операция чтения или записи по умолчанию будет производиться с начала файла. С другой стороны, процесс может открыть файл в режиме записи в конец, в этом случае ядро устанавливает значение смещения, равное размеру файла. Ядро выделяет запись в личной (закрытой) таблице в адресном пространстве задачи, выделенном процессу (таблица эта называется таблицей пользовательских дескрипторов файлов), и запоминает указатель на эту запись. Указателем выступает дескриптор файла, возвращаемый пользователю. Запись в таблице пользовательских файлов указывает на запись в глобальной таблице файлов.
алгоритм open
входная информация:
имя файла
режим открытия
права доступа (при создании файла)
выходная информация: дескриптор файла
{
превратить имя файла в идентификатор индекса (алгоритм namei);
if (файл не существует или к нему не разрешен доступ) return (код ошибки);
выделить для индекса запись в таблице файлов, инициализировать счетчик, смещение;
выделить запись в таблице пользовательских дескрипторов файла, установить указатель на запись в таблице файлов;
if (режим открытия подразумевает усечение файла) освободить все блоки файла (алгоритм free);
снять блокировку (с индекса); /* индекс заблокирован выше, в алгоритме namei */
return (пользовательский дескриптор файла);
}
Рисунок 5.2. Алгоритм открытия файла
Предположим, что процесс, открывая файл «/etc/passwd» дважды, один раз только для чтения и один раз только для записи, и однажды файл «local» для чтения и для записи [15], выполняет следующий набор операторов:
fd1 = open("/etc/passwd", O_RDONLY);
fd2 = open("local", O_RDWR);
fd3 = open("/etc/passwd", O_WRONLY);
На Рисунке 5.3 показана взаимосвязь между таблицей индексов, таблицей файлов и таблицей пользовательских дескрипторов файла. Каждый вызов функции open возвращает процессу дескриптор файла, а соответствующая запись в таблице пользовательских дескрипторов файла указывает на уникальную запись в таблице файлов ядра, пусть даже один и тот же файл ("/etc/passwd") открывается дважды. Записи в таблице файлов для всех экземпляров одного и того же открытого файла указывают на одну запись в таблице индексов, хранящихся в памяти. Процесс может обращаться к файлу «/etc/passwd» с чтением или записью, но только через дескрипторы файла, имеющие значения 3 и 5 (см. Рисунок). Ядро запоминает разрешение на чтение или запись в файл в строке таблицы файлов, выделенной во время выполнения функции open. Предположим, что второй процесс выполняет следующий набор операторов:
fd1 = open("/etc/passwd", O_RDONLY);
fd2 = open("private", O_RDONLY);
Рисунок 5.3. Структуры данных после открытия
На Рисунке 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, выполняющий чтение обычного файла. Ядро обращается в таблице файлов к записи, которая соответствует значению пользовательского дескриптора файла, следуя за указателем (см. Рисунок 5.3). Затем оно устанавливает значения нескольких параметров ввода-вывода в адресном пространстве процесса (Рисунок 5.6), тем самым устраняя необходимость в их передаче в качестве параметров функции. В частности, ядро указывает в качестве режима ввода-вывода «чтение», устанавливает флаг, свидетельствующий о том, что ввод-вывод направляется в адресное пространство пользователя, значение поля счетчика байтов приравнивает количеству байт, которые будут прочитаны, устанавливает адрес пользовательского буфера данных и, наконец, значение смещения (из таблицы файлов), равное смещению в байтах внутри файла до места, откуда начинается ввод-вывод. После того, как ядро установит значения параметров ввода-вывода в адресном пространстве процесса, оно обращается к индексу, используя указатель из таблицы файлов, и блокирует его прежде, чем начать чтение из файла.
алгоритм read
входная информация:
пользовательский дескриптор файла
адрес буфера в пользовательском процессе
количество байт, которые нужно прочитать
выходная информация: количество байт, скопированных в пользовательское пространство
{
обратиться к записи в таблице файлов по значению пользовательского дескриптора файла;
проверить доступность файла;
установить параметры в адресном пространстве процесса, указав адрес пользователя, счетчик байтов, параметры ввода-вывода для пользователя;
получить индекс по записи в таблице файлов;
заблокировать индекс;
установить значение смещения в байтах для адресного пространства процесса по значению смещения в таблице файлов;
do (пока значение счетчика байтов не станет удовлетворительным) {
превратить смещение в файле в номер дискового блока (алгоритм bmap);
вычислить смещение внутри блока и количество байт, которые будут прочитаны;
if (количество байт для чтения == 0) /* попытка чтения конца файла */ break; /* выход из цикла */
прочитать блок (алгоритм breada, если производится чтение с продвижением, и алгоритм bread — в противном случае);
скопировать данные из системного буфера по адресу пользователя;
скорректировать значения полей в адресном пространстве процесса, указывающие смещение в байтах внутри файла, количество прочитанных байт и адрес для передачи в пространство пользователя;
освободить буфер; /* заблокированный в алгоритме bread */
}
разблокировать индекс;
скорректировать значение смещения в таблице файлов для следующей операции чтения;
return (общее число прочитанных байт);
}
Рисунок 5.5. Алгоритм чтения из файла
modeчтение или запись
countколичество байт для чтения или записи
offsetсмещение в байтах внутри файла
addressадрес места, куда будут копироваться данные, в памяти пользователя или ядра
flagотношение адреса к памяти пользователя или к памяти ядра
Рисунок 5.6. Параметры ввода-вывода, хранящиеся в пространстве процесса
Затем в алгоритме начинается цикл, выполняющийся до тех пор, пока операция чтения не будет произведена до конца. Ядро преобразует смещение в байтах внутри файла в номер блока, используя алгоритм bmap, и вычисляет смещение внутри блока до места, откуда следует начать ввод-вывод, а также количество байт, которые будут прочитаны из блока. После считывания блока в буфер, возможно, с продвижением (алгоритмы bread и breada) ядро копирует данные из блока по назначенному адресу в пользовательском процессе. Оно корректирует параметры ввода-вывода в адресном пространстве процесса в соответствии с количеством прочитанных байт, увеличивая значение смещения в байтах внутри файла и адрес места в пользовательском процессе, куда будет доставлена следующая порция данных, и уменьшая число байт, которые необходимо прочитать, чтобы выполнить запрос пользователя. Если запрос пользователя не удовлетворен, ядро повторяет весь цикл, преобразуя смещение в байтах внутри файла в номер блока, считывая блок с диска в системный буфер, копируя данные из буфера в пользовательский процесс, освобождая буфер и корректируя значения параметров ввода-вывода в адресном пространстве процесса. Цикл завершается, либо когда ядро выполнит запрос пользователя полностью, либо когда в файле больше не будет данных, либо если ядро обнаружит ошибку при чтении данных с диска или при копировании данных в пространство пользователя. Ядро корректирует значение смещения в таблице файлов в соответствии с количеством фактически прочитанных байт; поэтому успешное выполнение операций чтения выглядит как последовательное считывание данных из файла. Системная операция lseek (раздел 5.6) устанавливает значение смещения в таблице файлов и изменяет порядок, в котором процесс читает или записывает данные в файле.
number = read(fd, buffer, count)
где fd — дескриптор файла, возвращаемый функцией open, buffer — адрес структуры данных в пользовательском процессе, где будут размещаться считанные данные в случае успешного завершения выполнения функции read, count — количество байт, которые пользователю нужно прочитать, number — количество фактически прочитанных байт. На Рисунке 5.5 приведен алгоритм read, выполняющий чтение обычного файла. Ядро обращается в таблице файлов к записи, которая соответствует значению пользовательского дескриптора файла, следуя за указателем (см. Рисунок 5.3). Затем оно устанавливает значения нескольких параметров ввода-вывода в адресном пространстве процесса (Рисунок 5.6), тем самым устраняя необходимость в их передаче в качестве параметров функции. В частности, ядро указывает в качестве режима ввода-вывода «чтение», устанавливает флаг, свидетельствующий о том, что ввод-вывод направляется в адресное пространство пользователя, значение поля счетчика байтов приравнивает количеству байт, которые будут прочитаны, устанавливает адрес пользовательского буфера данных и, наконец, значение смещения (из таблицы файлов), равное смещению в байтах внутри файла до места, откуда начинается ввод-вывод. После того, как ядро установит значения параметров ввода-вывода в адресном пространстве процесса, оно обращается к индексу, используя указатель из таблицы файлов, и блокирует его прежде, чем начать чтение из файла.
алгоритм read
входная информация:
пользовательский дескриптор файла
адрес буфера в пользовательском процессе
количество байт, которые нужно прочитать
выходная информация: количество байт, скопированных в пользовательское пространство
{
обратиться к записи в таблице файлов по значению пользовательского дескриптора файла;
проверить доступность файла;
установить параметры в адресном пространстве процесса, указав адрес пользователя, счетчик байтов, параметры ввода-вывода для пользователя;
получить индекс по записи в таблице файлов;
заблокировать индекс;
установить значение смещения в байтах для адресного пространства процесса по значению смещения в таблице файлов;
do (пока значение счетчика байтов не станет удовлетворительным) {
превратить смещение в файле в номер дискового блока (алгоритм bmap);
вычислить смещение внутри блока и количество байт, которые будут прочитаны;
if (количество байт для чтения == 0) /* попытка чтения конца файла */ break; /* выход из цикла */
прочитать блок (алгоритм breada, если производится чтение с продвижением, и алгоритм bread — в противном случае);
скопировать данные из системного буфера по адресу пользователя;
скорректировать значения полей в адресном пространстве процесса, указывающие смещение в байтах внутри файла, количество прочитанных байт и адрес для передачи в пространство пользователя;
освободить буфер; /* заблокированный в алгоритме bread */
}
разблокировать индекс;
скорректировать значение смещения в таблице файлов для следующей операции чтения;
return (общее число прочитанных байт);
}
Рисунок 5.5. Алгоритм чтения из файла
modeчтение или запись
countколичество байт для чтения или записи
offsetсмещение в байтах внутри файла
addressадрес места, куда будут копироваться данные, в памяти пользователя или ядра
flagотношение адреса к памяти пользователя или к памяти ядра
Рисунок 5.6. Параметры ввода-вывода, хранящиеся в пространстве процесса
Затем в алгоритме начинается цикл, выполняющийся до тех пор, пока операция чтения не будет произведена до конца. Ядро преобразует смещение в байтах внутри файла в номер блока, используя алгоритм bmap, и вычисляет смещение внутри блока до места, откуда следует начать ввод-вывод, а также количество байт, которые будут прочитаны из блока. После считывания блока в буфер, возможно, с продвижением (алгоритмы bread и breada) ядро копирует данные из блока по назначенному адресу в пользовательском процессе. Оно корректирует параметры ввода-вывода в адресном пространстве процесса в соответствии с количеством прочитанных байт, увеличивая значение смещения в байтах внутри файла и адрес места в пользовательском процессе, куда будет доставлена следующая порция данных, и уменьшая число байт, которые необходимо прочитать, чтобы выполнить запрос пользователя. Если запрос пользователя не удовлетворен, ядро повторяет весь цикл, преобразуя смещение в байтах внутри файла в номер блока, считывая блок с диска в системный буфер, копируя данные из буфера в пользовательский процесс, освобождая буфер и корректируя значения параметров ввода-вывода в адресном пространстве процесса. Цикл завершается, либо когда ядро выполнит запрос пользователя полностью, либо когда в файле больше не будет данных, либо если ядро обнаружит ошибку при чтении данных с диска или при копировании данных в пространство пользователя. Ядро корректирует значение смещения в таблице файлов в соответствии с количеством фактически прочитанных байт; поэтому успешное выполнение операций чтения выглядит как последовательное считывание данных из файла. Системная операция lseek (раздел 5.6) устанавливает значение смещения в таблице файлов и изменяет порядок, в котором процесс читает или записывает данные в файле.