Морис Бах - Архитектура операционной системы UNIX
Алгоритмы, описанные в этой главе, уровнем выше по сравнению с алгоритмами управления буферным кешем, рассмотренными в предыдущей главе (Рисунок 4.1). Алгоритм iget возвращает последний из идентифицированных индексов с возможностью считывания его с диска, используя буферный кеш, а алгоритм iput освобождает индекс. Алгоритм bmap устанавливает параметры ядра, связанные с обращением к файлу. Алгоритм namei преобразует составное имя пользовательского файла в имя индекса, используя алгоритмы iget, iput и bmap. Алгоритмы alloc и free выделяют и освобождают дисковые блоки для файлов, алгоритмы ialloc и ifree назначают и освобождают для файлов индексы.
Алгоритмы работы с файловой системой на нижнем уровне namei alloc free ialloc ifree iget iput bmap алгоритмы работы с буферами getblk brelse bread breada bwriteРисунок 4.1. Алгоритмы файловой системы
4.1 ИНДЕКСЫ
4.1.1 Определение
Индексы существуют на диске в статической форме и ядро считывает их в память прежде, чем начать с ними работать. Дисковые индексы включают в себя следующие поля:
• Идентификатор владельца файла. Права собственности разделены между индивидуальным владельцем и «групповым» и тем самым помогают определить круг пользователей, имеющих права доступа к файлу. Суперпользователь имеет право доступа ко всем файлам в системе.
• Тип файла. Файл может быть файлом обычного типа, каталогом, специальным файлом, соответствующим устройствам ввода-вывода символами или блоками, а также абстрактным файлом канала (организующим обслуживание запросов в порядке поступления, «первым пришел — первым вышел»).
• Права доступа к файлу. Система разграничивает права доступа к файлу для трех классов пользователей: индивидуального владельца файла, группового владельца и прочих пользователей; каждому классу выделены определенные права на чтение, запись и исполнение файла, которые устанавливаются индивидуально. Поскольку каталоги как файлы не могут быть исполнены, разрешение на исполнение в данном случае интерпретируется как право производить поиск в каталоге по имени файла.
• Календарные сведения, характеризующие работу с файлом: время внесения последних изменений в файл, время последнего обращения к файлу, время внесения последних изменений в индекс.
• Число указателей на файл, означающее количество имен, используемых при поиске файла в иерархии каталогов. Указатели на файл подробно рассматриваются в главе 5.
• Таблица адресов на диске, в которых располагается информация файла. Хотя пользователи трактуют информацию в файле как логический поток байтов, ядро располагает эти данные в несоприкасающихся дисковых блоках. Дисковые блоки, содержащие информацию файла, указываются в индексе.
• Размер файла. Данные в файле адресуются с помощью смещения в байтах относительно начала файла, начиная со смещения, равного 0, поэтому размер файла в байтах на 1 больше максимального смещения. Например, если пользователь создает файл и записывает только 1 байт информации по адресу со смещением 1000 от начала файла, размер файла составит 1001 байт. В индексе отсутствует составное имя файла, необходимое для осуществления доступа к файлу.
владелец mjb группа os тип обычный файл права доступа rwxr-xr-x последнее обращение 23 Окт 1984 13:45 последнее изменение 22 Окт 1984 10:30 коррекция индекса 23 Окт 1984 13:30 размер 6030 байт дисковые адресаРисунок 4.2. Пример дискового индекса
На Рисунке 4.2 показан дисковый индекс некоторого файла. Этот индекс принадлежит обычному файлу, владелец которого — «mjb» и размер которого 6030 байт. Система разрешает пользователю «mjb» производить чтение, запись и исполнение файла; членам группы «os» и всем остальным пользователям разрешается только читать или исполнять файл, но не записывать в него данные. Последний раз файл был прочитан 23 октября 1984 года в 13:45, запись последний раз производилась 22 октября 1984 года в 10:30. Индекс изменялся последний раз 23 октября 1984 года в 13:30, хотя никакая информация в это время в файл не записывалась. Ядро кодирует все вышеперечисленные данные в индексе. Обратите внимание на различие в записи на диск содержимого индекса и содержимого файла. Содержимое файла меняется только тогда, когда в файл производится запись. Содержимое индекса меняется как при изменении содержимого файла, так и при изменении владельца файла, прав доступа и набора указателей. Изменение содержимого файла автоматически вызывает коррекцию индекса, однако коррекция индекса еще не означает изменения содержимого файла.
Копия индекса в памяти, кроме полей дискового индекса, включает в себя и следующие поля:
• Состояние индекса в памяти, отражающее
- заблокирован ли индекс,
- ждет ли снятия блокировки с индекса какой-либо процесс,
- отличается ли представление индекса в памяти от своей дисковой копии в результате изменения содержимого индекса,
- отличается ли представление индекса в памяти от своей дисковой копии в результате изменения содержимого файла,
- находится ли файл в верхней точке (см. раздел 5.15).
• Логический номер устройства файловой системы, содержащей файл.
• Номер индекса. Так как индексы на диске хранятся в линейном массиве (см. раздел 2.2.1), ядро идентифицирует номер дискового индекса по его местоположению в массиве. В дисковом индексе это поле не нужно.
• Указатели на другие индексы в памяти. Ядро связывает индексы в хеш-очереди и включает их в список свободных индексов подобно тому, как связывает буферы в буферные хеш-очереди и включает их в список свободных буферов. Хеш-очередь идентифицируется в соответствии с логическим номером устройства и номером индекса. Ядро может располагать в памяти не более одной копии данного дискового индекса, но индексы могут находиться одновременно как в хеш-очереди, так и в списке свободных индексов.
• Счетчик ссылок, означающий количество активных экземпляров файла (таких, которые открыты).
Многие поля в копии индекса, с которой ядро работает в памяти, аналогичны полям в заголовке буфера, и управление индексами похоже на управление буферами. Индекс так же блокируется, в результате чего другим процессам запрещается работа с ним; эти процессы устанавливают в индексе специальный флаг, возвещающий о том, что выполнение обратившихся к индексу процессов следует возобновить, как только блокировка будет снята. Установкой других флагов ядро отмечает противоречия между дисковым индексом и его копией в памяти. Когда ядру нужно будет записать изменения в файл или индекс, ядро перепишет копию индекса из памяти на диск только после проверки этих флагов.
Наиболее разительным различием между копией индекса в памяти и заголовком буфера является наличие счетчика ссылок, подсчитывающего количество активных экземпляров файла. Индекс активен, когда процесс выделяет его, например, при открытии файла. Индекс находится в списке свободных индексов, только если значение его счетчика ссылок равно 0, и это значит, что ядро может переназначить свободный индекс в памяти другому дисковому индексу. Таким образом, список свободных индексов выступает в роли кеша для неактивных индексов. Если процесс пытается обратиться к файлу, чей индекс в этот момент отсутствует в индексном пуле, ядро переназначает свободный индекс из списка для использования этим процессом. С другой стороны, у буфера нет счетчика ссылок; он находится в списке свободных буферов тогда и только тогда, когда он разблокирован.
4.1.2 Обращение к индексам
Ядро идентифицирует индексы по имени файловой системы и номеру индекса и выделяет индексы в памяти по запросам соответствующих алгоритмов. Алгоритм iget назначает индексу место для копии в памяти (Рисунок 4.3); он почти идентичен алгоритму getblk для поиска дискового блока в буферном кеше. Ядро преобразует номера устройства и индекса в имя хеш-очереди и просматривает эту хеш-очередь в поисках индекса. Если индекс не обнаружен, ядро выделяет его из списка свободных индексов и блокирует его. Затем ядро готовится к чтению с диска в память индекса, к которому оно обращается. Ядро уже знает номера индекса и логического устройства и вычисляет номер логического блока на диске, содержащего индекс, с учетом того, сколько дисковых индексов помещается в одном дисковом блоке. Вычисления производятся по формуле
