Морис Бах - Архитектура операционной системы UNIX
Ядро могло бы производить чтение и запись непосредственно с диска и на диск при всех обращениях к файловой системе, однако время реакции системы и производительность при этом были бы низкими из-за низкой скорости передачи данных с диска. По этой причине ядро старается свести к минимуму частоту обращений к диску, заведя специальную область внутренних информационных буферов, именуемую буферным кешем[7] и хранящую содержимое блоков диска, к которым перед этим производились обращения.
На Рисунке 2.1 показано, что модуль буферного кеша занимает в архитектуре ядра место между подсистемой управления файлами и драйверами устройств (ввода-вывода блоками). Перед чтением информации с диска ядро пытается считать что-нибудь из буфера кеша. Если в этом буфере отсутствует информация, ядро читает данные с диска и заносит их в буфер, используя алгоритм, который имеет целью поместить в буфере как можно больше необходимых данных. Аналогично, информация, записываемая на диск, заносится в буфер для того, чтобы находиться там, если ядро позднее попытается считать ее. Ядро также старается свести к минимуму частоту выполнения операций записи на диск, выясняя, должна ли информация действительно запоминаться на диске или это промежуточные данные, которые будут вскоре затерты. Алгоритмы более высокого уровня позволяют производить предварительное занесение данных в буфер кеша или задерживать запись данных с тем, чтобы усилить эффект использования буфера. В этой главе рассматриваются алгоритмы, используемые ядром при работе с буферами в сверхоперативной памяти.
3.1 ЗАГОЛОВКИ БУФЕРА
Во время инициализации системы ядро выделяет место под совокупность буферов, потребность в которых определяется в зависимости от размера памяти и производительности системы. Каждый буфер состоит из двух частей: области памяти, в которой хранится информация, считываемая с диска, и заголовка буфера, который идентифицирует буфер. Поскольку существует однозначное соответствие между заголовками буферов и массивами данных, в нижеследующем тексте используется термин «буфер» в ссылках как на ту, так и на другую его составляющую, и о какой из частей буфера идет речь будет понятно из контекста.
Информация в буфере соответствует информации в одном логическом блоке диска в файловой системе, и ядро распознает содержимое буфера, просматривая идентифицирующие поля в его заголовке. Буфер представляет собой копию дискового блока в памяти; содержимое дискового блока отображается в буфер, но это отображение временное, поскольку оно имеет место до того момента, когда ядро примет решение отобразить в буфер другой дисковый блок. Один дисковый блок не может быть одновременно отображен в несколько буферов. Если бы два буфера содержали информацию для одного и того же дискового блока, ядро не смогло бы определить, в каком из буферов содержится текущая информация, и, возможно, возвратило бы на диск некорректную информацию. Предположим, например, что дисковый блок отображается в два буфера, A и B. Если ядро запишет данные сначала в буфер A, а затем в буфер B, дисковый блок будет содержать данные из буфера B, если в результате операций записи буфер заполнится до конца. Однако, если ядро изменит порядок, в котором оно копирует содержимое буферов на диск, на противоположный, дисковый блок будет содержать некорректные данные.
Заголовок буфера (Рисунок 3.1) содержит поле «номер устройства» и поле «номер блока», которые определяют файловую систему и номер блока с информацией на диске и однозначно идентифицируют буфер. Номер устройства — это логический номер файловой системы (см. раздел 2.2.1), а не физический номер устройства (диска). Заголовок буфера также содержит указатель на область памяти для буфера, размер которой должен быть не меньше размера дискового блока, и поле состояния, в котором суммируется информация о текущем состоянии буфера. Состояние буфера представляет собой комбинацию из следующих условий:
• буфер заблокирован (термины «заблокирован (недоступен)» и «занят» равнозначны, так же, как и понятия «свободен» и «доступен»),
• буфер содержит правильную информацию,
• ядро должно переписать содержимое буфера на диск перед тем, как переназначить буфер; это условие известно, как «задержка, вызванная записью»,
• ядро читает или записывает содержимое буфера на диск,
• процесс ждет освобождения буфера.
В заголовке буфера также содержатся два набора указателей, используемые алгоритмами выделения буфера, которые поддерживают общую структуру области буферов (буферного пула), о чем подробнее будет говориться в следующем разделе.
Рисунок 3.1. Заголовок буфера
3.2 СТРУКТУРА ОБЛАСТИ БУФЕРОВ (БУФЕРНОГО ПУЛА)
Ядро помещает информацию в область буферов, используя алгоритм поиска буферов, к которым наиболее долго не было обращений: после выделения буфера дисковому блоку нельзя использовать этот буфер для другого блока до тех пор, пока не будут задействованы все остальные буферы. Ядро управляет списком свободных буферов, который необходим для работы указанного алгоритма. Этот список представляет собой циклический перечень буферов с двунаправленными указателями и с формальными заголовками в начале и в конце перечня (Рисунок 3.2). Все буферы попадают в список при загрузке системы. Если нужен любой свободный буфер, ядро выбирает буфер из «головы» списка, но если в области буферов ищется определенный блок, может быть выбран буфер и из середины списка. И в том, и в другом случае буфер удаляется из списка свободных буферов. Если ядро возвращает буфер буферному пулу, этот буфер добавляется в хвост списка, либо в «голову» списка (в случае ошибки), но никогда не в середину. По мере удаления буферов из списка буфер с нужной информацией продвигается все ближе и ближе к «голове» списка (Рисунок 3.2). Следовательно, те буферы, которые находятся ближе к «голове» списка, в последний раз использовались раньше, чем буферы, находящиеся дальше от «головы» списка.
Рисунок 3.2. Список свободных буферов
Когда ядро обращается к дисковому блоку, оно сначала ищет буфер с соответствующей комбинацией номеров устройства и блока. Вместо того, чтобы просматривать всю область буферов, ядро организует из буферов особые очереди, хешированные по номеру устройства и номеру блока. В хеш-очереди ядро устанавливает для буферов циклическую связь в виде списка с двунаправленными указателями, структура которого похожа на структуру списка свободных буферов. Количество буферов в хеш-очереди варьируется в течение всего времени функционирования системы, в чем мы еще убедимся дальше. Ядро вынуждено прибегать к функции хеширования, чтобы единообразно распределять буферы между хеш-очередями, однако функция хеширования должна быть несложной, чтобы не пострадала производительность системы. Администраторы системы задают количество хеш-очередей при генерации операционной системы.
Рисунок 3.3. Буферы в хеш-очередях
На Рисунке 3.3 изображены буферы в хеш-очередях: заголовки хеш-очередей показаны в левой части рисунка, а квадратиками в каждой строке показаны буферы в соответствующей хеш-очереди. Так, квадратики с числами 28, 4 и 64 представляют буферы в хеш-очереди для «блока 0 модуля 4». Пунктирным линиям между буферами соответствуют указатели вперед и назад вдоль хеш-очереди; для простоты на следующих рисунках этой главы данные указатели не показываются, но их присутствие подразумевается. Кроме того, на рисунке блоки идентифицируются только своими номерами и функция хеширования построена на использовании только номеров блоков; однако на практике также используется номер устройства.
Любой буфер всегда находится в хеш-очереди, но его положение в очереди не имеет значения. Как уже говорилось, никакая пара буферов не может одновременно содержать данные одного и того же дискового блока; поэтому каждый дисковый блок в буферном пуле существует в одной и только одной хеш-очереди и представлен в ней только один раз. Тем не менее, буфер может находиться в списке свободных буферов, если его статус «свободен». Поскольку буфер может быть одновременно в хеш-очереди и в списке свободных буферов, у ядра есть два способа его обнаружения. Ядро просматривает хеш-очередь, если ему нужно найти определенный буфер, и выбирает буфер из списка свободных буферов, если ему нужен любой свободный буфер. В следующем разделе будет показано, каким образом ядро осуществляет поиск определенных дисковых блоков в буферном кеше, а также как оно работает с буферами в хеш-очередях и в списке свободных буферов. Еще раз напомним: буфер всегда находится в хеш — очереди, а в списке свободных буферов может быть, но может и отсутствовать.
