Страница:
Как уже говорилось в предыдущей главе, ядро операционной системы поддер-
живает файлы на внешних запоминающих устройствах больщой емкости, таких как
диски, и позволяет процессам сохранять новую информацию или вызывать ранее
сохраненную информацию. Если процессу необходимо обратиться к информации
файла, ядро выбирает информацию в оперативную память, где процесс сможет
просматривать эту информацию, изменять ее и обращаться с просьбой о ее пов-
торном сохранении в файловой системе. Вспомним для примера программу copy,
приведенную на Рисунке 1.3: ядро читает данные из первого файла в память и
затем записывает эти данные во второй файл. Подобно тому, как ядро должно
заносить данные из файла в память, оно так же должно считывать в память и
вспомогательные данные для работы с ними. Например, суперблок файловой сис-
темы содержит помимо всего прочего информацию о свободном пространстве, дос-
тупном файловой системе. Ядро считывает суперблок в память для того, чтобы
иметь доступ к его информации, и возвращает его опять файловой системе, ког-
да желает сохранить его содержимое. Похожая вещь происходит с индексом, ко-
торый описывает размещение файла. Ядро системы считывает индекс в память,
когда желает получить доступ к информации файла, и возвращает индекс вновь
файловой системе, когда желает скорректировать размещение файла. Ядро обра-
батывает такую вспомогательную информацию, не будучи прежде знакома с ней и
не требуя для ее обработки запуска каких-либо процессов.
Ядро могло бы производить чтение и запись непосредственно с диска и на
диск при всех обращениях к файловой системе, однако время реакции системы и
производительность при этом были бы низкими из-за низкой скорости передачи
данных с диска. По этой причине ядро старается свести к минимуму частоту об-
ращений к диску, заведя специальную область внутренних информационных буфе-
ров, именуемую буферным кешем (*) и хранящую содержимое блоков диска, к ко-
торым перед этим производились обращения.
На Рисунке 2.1 показано, что модуль буферного кеша занимает в архитекту-
ре ядра место между подсистемой управления файлами и драйверами устройств
(ввода-вывода блоками). Перед чтением информации с диска ядро пытается счи-
тать что-нибудь из буфера кеша. Если в этом буфере отсутствует информация,
ядро читает данные с диска и заносит их в буфер, используя алгоритм, который
имеет целью поместить в буфере как можно больше необходимых данных. Анало-
гично, информация, записываемая на диск, заносится в буфер для того, чтобы
находиться там, если ядро позднее попытается считать ее. Ядро также старает-
ся свести к минимуму частоту выполнения операций записи на диск, выясняя,
должна ли информация действительно запоминаться на диске или это промежуточ-
ные данные, которые будут вскоре затерты. Алгоритмы более высокого уровня
позволяют производить предварительное занесение данных в буфер кеша или за-
держивать запись данных с тем, чтобы усилить эффект использования буфера. В
этой главе рассматриваются алгоритмы, используемые ядром при работе с буфе-
рами в сверхоперативной памяти.
-----------------------------------------
(*) Буферный кеш представляет собой программную структуру, которую не следу-
ет путать с аппаратными кешами, ускоряющими косвенную адресацию памяти.
39
Во время инициализации системы ядро выделяет место под совокупность бу-
феров, потребность в которых определяется в зависимости от размера памяти и
производительности системы. Каждый буфер состоит из двух частей: области па-
мяти, в которой хранится информация, считываемая с диска, и заголовка буфе-
ра, который идентифицирует буфер. Поскольку существует однозначное соответс-
твие между заголовками буферов и массивами данных, в нижеследующем тексте
используется термин "буфер" в ссылках как на ту, так и на другую его состав-
ляющую, и о какой из частей буфера идет речь будет понятно из контекста.
Информация в буфере соответствует информации в одном логическом блоке
диска в файловой системе, и ядро распознает содержимое буфера, просматривая
идентифицирующие поля в его заголовке. Буфер представляет собой копию диско-
вого блока в памяти; содержимое дискового блока отображается в буфер, но это
отображение временное, поскольку оно имеет место до того момента, когда ядро
примет решение отобразить в буфер другой дисковый блок. Один дисковый блок
не может быть одновременно отображен в несколько буферов. Если бы два буфера
содержали информацию для одного и того же дискового блока, ядро не смогло бы
определить, в каком из буферов содержится текущая информация, и, возможно,
возвратило бы на диск некорректную информацию. Предположим, например, что
дисковый блок отображается в два буфера, A и B. Если ядро запишет данные
сначала в буфер A, а затем в буфер B, дисковый блок будет содержать данные
из буфера B, если в результате операций записи буфер заполнится до конца.
Однако, если ядро изменит порядок, в котором оно копирует содержимое буферов
на диск, на противоположный, дисковый блок будет содержать некорректные дан-
ные.
Заголовок буфера (Рисунок 3.1) содержит поле "номер устройства" и поле
"номер блока", которые определяют файловую систему и номер блока с информа-
цией на диске и однозначно идентифицируют буфер. Номер устройства - это ло-
гический номер файловой системы
+------------------+
| номер устройства |
+------------------+ указатель на
| номер блока | область данных
+------------------+ +------------->
указатель на | поле состояния | |
предыдущий буфер +------------------+ |
в хеш-очереди | ------+---+
<-------------+ +------------------+
| | ------+----------------->
| +------------------+ указатель на
+---+------ | следующий буфер
+------------------+ в хеш-очереди
| ------+---+
+------------------+ |
<-----------------+------ | |
указатель на +------------------+ +------------->
предыдущий буфер указатель на
в списке свободных следующий буфер
в списке свободных
Рисунок 3.1. Заголовок буфера
(см. раздел 2.2.1), а не физический номер устройства (диска). Заголовок бу-
фера также содержит указатель на область памяти для буфера, размер которой
должен быть не меньше размера дискового блока, и поле состояния, в котором
суммируется информация о текущем состоянии буфера. Состояние буфера предс-
тавляет собой комбинацию из следующих условий:
* буфер заблокирован (термины "заблокирован (недоступен)" и "занят" равноз-
40
начны, так же, как и понятия "свободен" и "доступен"),
* буфер содержит правильную информацию,
* ядро должно переписать содержимое буфера на диск перед тем, как переназна-
чить буфер; это условие известно, как "задержка, вызванная записью",
* ядро читает или записывает содержимое буфера на диск,
* процесс ждет освобождения буфера.
В заголовке буфера также содержатся два набора указателей, используемые
алгоритмами выделения буфера, которые поддерживают общую структуру области
буферов (буферного пула), о чем подробнее будет говориться в следующем раз-
деле.
Ядро помещает информацию в область буферов, используя алгоритм поиска
буферов, к которым наиболее долго не было обращений: после выделения буфера
дисковому блоку нельзя использовать этот
+----------------------------------------------------------------+
| указатели вперед |
| +-------------------+ +-------+ +-------+ +-------+ |
+->| заголовок списка |--->| буфер |--->| буфер |--->| буфер |--+
+--| свободных буферов |<---| 1 |<---| 2 |<---| n |<-+
| +-------------------+ +-------+ +-------+ +-------+ |
| указатели назад |
+----------------------------------------------------------------+
до
после
+----------------------------------------------------------------+
| указатели вперед |
| +-------------------+ +-------+ +-------+ |
+->| заголовок списка |---------------->| буфер |--->| буфер |--+
+--| свободных буферов |<----------------| 2 |<---| n |<-+
| +-------------------+ +-------+ +-------+ |
| указатели назад |
+----------------------------------------------------------------+
Рисунок 3.2. Список свободных буферов
буфер для другого блока до тех пор, пока не будут задействованы все осталь-
ные буферы. Ядро управляет списком свободных буферов, который необходим для
работы указанного алгоритма. Этот список представляет собой циклический пе-
речень буферов с двунаправленными указателями и с формальными заголовками в
начале и в конце перечня (Рисунок 3.2). Все буферы попадают в список при
загрузке системы. Если нужен любой свободный буфер, ядро выбирает буфер из
"головы" списка, но если в области буферов ищется определенный блок, может
быть выбран буфер и из середины списка. И в том, и в другом случае буфер
удаляется из списка свободных буферов. Если ядро возвращает буфер буферному
пулу, этот буфер добавляется в хвост списка, либо в "голову" списка (в слу-
чае ошибки), но никогда не в середину. По мере удаления буферов из списка
буфер с нужной информацией продвигается все ближе и ближе к "голове" списка
(Рисунок 3.2). Следовательно, те буферы, которые находятся ближе к "голове"
списка, в последний раз использовались раньше, чем буферы, находящиеся даль-
ше от "головы" списка.
Когда ядро обращается к дисковому блоку, оно сначала ищет буфер с соот-
ветствующей комбинацией номеров устройства и блока. Вместо того, чтобы прос-
матривать всю область буферов, ядро организует из буферов особые очереди,
41
хешированные по номеру устройства и номеру блока. В хеш-очереди ядро уста-
навливает для буферов циклическую связь в виде списка с двунаправленными
указателями, структура которого похожа на структуру списка свободных буфе-
ров. Количество буферов в хеш-очереди варьируется в течение всего времени
функционирования системы, в чем мы еще убедимся дальше. Ядро вынуждено при-
бегать к функции хеширования, чтобы единообразно распределять буферы между
хеш-очередями, однако функция хеширования должна быть несложной, чтобы не
пострадала производительность системы. Администраторы системы задают коли-
чество хеш-очередей при генерации операционной системы.
заголовки хеш-очередей
+-----------------+
| | +----+ +----+ +----+
<----| блок 0 модуль 4 |------| 28 |-----| 4 |-----| 64 |---->
| | +----+ +----+ +----+
+-----------------+
| | +----+ +----+ +----+
<----| блок 1 модуль 4 |------| 17 |-----| 5 |-----| 97 |---->
| | +----+ +----+ +----+
+-----------------+
| | +----+ +----+ +----+
<----| блок 2 модуль 4 |------| 98 |-----| 50 |-----| 10 |---->
| | +----+ +----+ +----+
+-----------------+
| | +----+ +----+ +----+
<----| блок 3 модуль 4 |------| 3 |-----| 35 |-----| 99 |---->
| | +----+ +----+ +----+
+-----------------+
Рисунок 3.3. Буферы в хеш-очередях
На Рисунке 3.3 изображены буферы в хеш-очередях: заголовки хеш-очередей
показаны в левой части рисунка, а квадратиками в каждой строке показаны бу-
феры в соответствующей хеш-очереди. Так, квадратики с числами 28, 4 и 64
представляют буферы в хеш-очереди для "блока 0 модуля 4". Пунктирным линиям
между буферами соответствуют указатели вперед и назад вдоль хеш-очереди; для
простоты на следующих рисунках этой главы данные указатели не показываются,
но их присутствие подразумевается. Кроме того, на рисунке блоки идентифици-
руются только своими номерами и функция хеширования построена на использова-
нии только номеров блоков; однако на практике также используется номер уст-
ройства.
Любой буфер всегда находится в хеш-очереди, но его положение в очереди
не имеет значения. Как уже говорилось, никакая пара буферов не может однов-
ременно содержать данные одного и того же дискового блока; поэтому каждый
дисковый блок в буферном пуле существует в одной и только одной хеш-очереди
и представлен в ней только один раз. Тем не менее, буфер может находиться в
списке свободных буферов, если его статус "свободен". Поскольку буфер может
быть одновременно в хеш-очереди и в списке свободных буферов, у ядра есть
два способа его обнаружения. Ядро просматривает хеш-очередь, если ему нужно
найти определенный буфер, и выбирает буфер из списка свободных буферов, если
ему нужен любой свободный буфер. В следующем разделе будет показано, каким
образом ядро осуществляет поиск определенных дисковых блоков в буферном ке-
ше, а также как оно работает с буферами в хеш-очередях и в списке свободных
буферов. Еще раз напомним: буфер всегда находится в хеш -очереди, а в списке
свободных буферов может быть, но может и отсутствовать.
42
Как показано на Рисунке 2.1, алгоритмы верхнего уровня, используемые яд-
ром для подсистемы управления файлами, инициируют выполнение алгоритмов уп-
равления буферным кешем. При выборке блока алгоритмы верхнего уровня уста-
навливают логический номер устройства и номер блока, к которым они хотели бы
получить доступ. Например, если процесс хочет считать данные из файла, ядро
устанавливает, в какой файловой системе находится файл и в каком блоке фай-
ловой системы содержатся данные, о чем подробнее мы узнаем из главы 4. Соби-
раясь считать данные из определенного дискового блока, ядро проверяет, нахо-
дится ли блок в буферном пуле, и если нет, назначает для него свободный бу-
фер. Собираясь записать данные в определенный дисковый блок, ядро проверяет,
находится ли блок в буферном пуле, и если нет, назначает для этого блока
свободный буфер. Для выделения буферов из пула в алгоритмах чтения и записи
дисковых блоков используется операция getblk (Рисунок 3.4).
Рассмотрим в этом разделе пять возможных механизмов использования getblk
для выделения буфера под дисковый блок.
1. Ядро обнаруживает блок в хеш-очереди, соответствующий ему буфер сво-
боден.
2. Ядро не может обнаружить блок в хеш-очереди, поэтому оно выделяет бу-
фер из списка свободных буферов.
3. Ядро не может обнаружить блок в хеш-очереди и, пытаясь выделить буфер
из списка свободных буферов (как в случае 2), обнаруживает в списке
буфер, который помечен как "занят на время записи". Ядро должно пере-
писать этот буфер на диск и выделить другой буфер.
4. Ядро не может обнаружить блок в хеш-очереди, а список свободных буфе-
ров пуст.
5. Ядро обнаруживает блок в хеш-очереди, но его буфер в настоящий момент
занят.
Обсудим каждый случай более подробно.
Осуществляя поиск блока в буферном пуле по комбинации номеров устройства
и блока, ядро ищет хеш-очередь, которая бы содержала этот блок. Просматривая
хеш-очередь, ядро придерживается списка с указателями, пока (как в первом
случае) не найдет буфер с искомыми номерами устройства и блока. Ядро прове-
ряет занятость блока и в том случае, если он свободен, помечает буфер "заня-
тым" для того, чтобы другие процессы (**) не смогли к нему обратиться. Затем
ядро удаляет буфер из списка свободных буферов, поскольку буфер не может од-
новременно быть занятым и находиться в указанном списке. Если другие процес-
сы попытаются обратиться к блоку в то время, когда его буфер занят, они при-
остановятся до тех пор, пока буфер не освободится. На Рисунке 3.5 показан
первый случай, когда ядро ищет блок 4 в хеш-очереди, помеченной как "блок 0
модуль 4". Обнаружив буфер, ядро удаляет его из списка свободных буферов,
делая блоки 5 и 28 соседями в списке.
----------------------------------------
(**) Из предыдущей главы напомним, что все операции ядра производятся в кон-
тексте процесса, выполняемого в режиме ядра. Таким образом, слова "дру-
гие процессы" относятся к процессам, тоже выполняющимся в режиме ядра.
Эти слова мы будем использовать и тогда, когда будем говорить о взаимо-
действии нескольких процессов, работающих в режиме ядра; и будем гово-
рить "ядро", когда взаимодействие между процессами будет отсутствовать.
43
+------------------------------------------------------------------+
| алгоритм getblk |
| входная информация: номер файловой системы номер блока |
| выходная информация: буфер, который можно использовать для блока|
| { выполнить если (буфер не найден) |
| { если (блок в хеш-очереди) |
| { если (буфер занят) /* случай 5 */ |
| { |
| приостановиться (до освобождения буфера); |
| продолжить; /* цикл с условием продолжения */ |
| } |
| пометить буфер занятым; /* случай 1 */ |
| удалить буфер из списка свободных буферов; |
| вернуть буфер; |
| } |
| в противном случае /* блока нет в хеш-очереди */ |
| { |
| если (в списке нет свободных буферов) /*случай 4*/ |
| { |
| приостановиться (до освобождения любого буфера); |
| продолжить; /* цикл с условием продолжения */ |
| } |
| удалить буфер из списка свободных буферов; |
| если (буфер помечен для отложенной переписи) |
| /* случай 3 */ |
| { |
| асинхронная перепись содержимого буфера на диск; |
| продолжить; /* цикл с условием продолжения */ |
| } |
| /* случай 2 -- поиск свободного буфера */ |
| удалить буфер из старой хеш-очереди; |
| включить буфер в новую хеш-очередь; |
| вернуть буфер; |
| } |
| } |
| } |
+------------------------------------------------------------------+
Рисунок 3.4. Алгоритм выделения буфера
заголовки хеш-очередей
+-----------------+ +-----------------+
| | |+----+ +----+| +----+
| блок 0 модуль 4 |---- ++ 28 ++ ++ 4 ++ | 64 |
+-----------------+ +----+| +------+ +----+
| | +----+| +----+| +----+
| блок 1 модуль 4 |---- | 17 || ++ 5 ++ ++ 97 ++
| | +----+| |+----+ +-++----+|
+-----------------+ +---|--------+ +------+
| | +----+ |+----+ |+----+
| блок 2 модуль 4 |---- | 98 |+---+| 50 | ++ 10 ++
+-----------------+ +----+| +----+ +----+|
| | +----+| +----+ +----+|
| блок 3 модуль 4 |----+>| 3 ++ | 35 | | 99 ||
+-----------------+ | +----+ +----+ +----+|
+-----------------+ | |
|заголовок списка +----+ |
|свободных буферов|<---------------------------------+
+-----------------+
(а) Поиск блока 4 в первой хеш-очереди
44
заголовки хеш-очередей
+-----------------+ +--------------+
| | +----+| +----+ |+----+
| блок 0 модуль 4 |---- ++ 28 ++ | 4 | || 64 |
| | |+----+ +----+ |+----+
+-----------------+ +-----------------+ |
| | +----+ +----+| |+----+
| блок 1 модуль 4 |---- | 17 | ++ 5 ++ ++ 97 ++
| | +----+ |+----+ +----+|
+-----------------+ | +------+
| | +----+ |+----+ |+----+
| блок 2 модуль 4 |---- | 98 |+---+| 50 | ++ 10 ++
| | +----+| +----+ +----+|
+-----------------+ | |
| | +----+| +----+ +----+|
| блок 3 модуль 4 |----+>| 3 ++ | 35 | | 99 ||
| | | +----+ +----+ +----+|
+-----------------+ | |
+-----------------+ | |
|заголовок списка +----+ |
| | |
|свободных буферов|<---------------------------------+
+-----------------+
(б) Удаление блока 4 из списка свободных буферов
Рисунок 3.5. Поиск буфера - случай 1: буфер в хеш-очереди
+------------------------------------------------------------+
| алгоритм brelse |
| входная информация: заблокированный буфер |
| выходная информация: отсутствует |
| { |
| возобновить выполнение всех процессов при наступлении |
| события, связанного с освобождением любого буфера; |
| возобновить выполнение всех процессов при наступлении |
| события, связанного с освобождением данного буфера; |
| поднять приоритет прерывания процессора так, чтобы |
| блокировать любые прерывания; |
| если (содержимое буфера верно и буфер не старый) |
| поставить буфер в конец списка свободных буферов |
| в противном случае |
| поставить буфер в начало списка свободных буферов |
| понизить приоритет прерывания процессора с тем, чтобы |
| вновь разрешить прерывания; |
| разблокировать (буфер); |
| } |
+------------------------------------------------------------+
Рисунок 3.6. Алгоритм высвобождения буфера
Перед тем, как перейти к остальным случаям, рассмотрим, что произойдет с
буфером после того, как он будет выделен блоку. Ядро системы сможет читать
данные с диска в буфер и обрабатывать их или же переписывать данные в буфер
и при желании на диск. Ядро оставляет у буфера пометку "занят"; другие про-
45
цессы не могут обратиться к нему и изменить его содержимое, пока он занят,
таким образом поддерживается целостность информации в буфере. Когда ядро за-
канчивает работу с буфером, оно освобождает буфер в соответствии с алгорит-
мом brelse (Рисунок 3.6). Возобновляется выполнение тех процессов, которые
были приостановлены из-за того, что буфер был занят, а также те процессы,
которые были приостановлены из-за того, что список свободных буферов был
пуст. Как в том, так и в другом случае, высвобождение буфера означает, что
буфер становится доступным для приостановленных процессов несмотря на то,
что первый процесс, получивший буфер, заблокировал его и запретил тем самым
получение буфера другими процессами (см. раздел 2.2.2.4). Ядро помещает бу-
фер в конец списка свободных буферов, если только перед этим не произошла
ошибка ввода-вывода или если буфер не помечен как "старый" - момент, который
будет пояснен далее; в остальных случаях буфер помещается в начало списка.
Теперь буфер свободен для использования любым процессом.
Ядро выполняет алгоритм brelse в случае, когда буфер процессу больше не
нужен, а также при обработке прерывания от диска для высвобождения буферов,
используемых при асинхронном вводе-выводе с диска и на диск (см. раздел
3.4). Ядро повышает приоритет прерывания работы процессора так, чтобы запре-
тить возникновение любых прерываний от диска на время работы со списком сво-
бодных буферов, предупреждая искажение указателей буфера в результате вло-
женного выполнения алгоритма brelse. Похожие последствия могут произойти,
если программа обработки прерываний запустит алгоритм brelse во время выпол-
нения процессом алгоритма getblk, поэтому ядро повышает приоритет прерывания
работы процессора и в стратегических моментах выполнения алгоритма getblk.
Более подробно эти случаи мы разберем с помощью упражнений.
При выполнении алгоритма getblk имеет место случай 2, когда ядро прос-
матривает хеш-очередь, в которой должен был бы находиться блок, но не нахо-
дит его там. Так как блок не может быть ни в какой другой хеш-очереди, пос-
кольку он не должен "хешироваться" в
заголовки хеш-очередей
+-----------------+ +-----------------+
| | |+----+ +----+| +----+
| блок 0 модуль 4 |---- ++ 28 ++ ++ 4 ++ | 64 |
| | +----+| |+----+ +----+
+-----------------+ | +------+
| | +----+| +----+| +----+
| блок 1 модуль 4 |---- | 17 || ++ 5 ++ ++ 97 ++
| | +----+| |+----+ +-++----+|
+-----------------+ +---|--------+ +------+
| | +----+ |+----+ |+----+
| блок 2 модуль 4 |---- | 98 |+---+| 50 | ++ 10 ++
| | +----+| +----+ +----+|
+-----------------+ | |
| | +----+| +----+ +----+|
| блок 3 модуль 4 |----+>| 3 ++ | 35 | | 99 ||
| | | +----+ +----+ +----+|
+-----------------+ | |
+-----------------+ | |
|заголовок списка +----+ |
| | |
|свободных буферов|<---------------------------------+
+-----------------+
(а) Поиск блока 18 - отсутствует в кеше
46
заголовки хеш-очередей
+-----------------+ +-----------------+
| | |+----+ +----+| +----+
| блок 0 модуль 4 |---- ++ 28 ++ ++ 4 ++ | 64 |
| | +----+| |+----+ +----+
+-----------------+ | +------+
| | +----+| +----+| +----+
| блок 1 модуль 4 |---- | 17 || +->| 5 ++ ++ 97 ++
| | +----+| | +----+ +-++----+|
+-----------------+ +-|----------+ +------+
| | +----+ | +----+ |+----+ +----+
| блок 2 модуль 4 |---- | 98 | | | 50 | ++ 10 ++ | 18 |
| | +----+ | +----+ +----+| +----+
+-----------------+ | |
| | | +----+ +----+|
| блок 3 модуль 4 |---- | | 35 | | 99 ||
+-----------------+ | +----+ +----+|
+-----------------+ | |
|заголовок списка +--------------+ |
|свободных буферов|<---------------------------------+
+-----------------+
(б) Удаление первого блока из списка свободных буферов, назначение блока 18
Рисунок 3.7. Второй случай выделения буфера
другом месте, следовательно, его нет в буферном кеше. Поэтому ядро удаляет
первый буфер из списка свободных буферов; этот буфер был уже выделен другому
дисковому блоку и также находится в хеш-очереди. Если буфер не помечен для
отложенной переписи, ядро помечает буфер занятым, удаляет его из хеш-очере-
ди, где он находится, назначает в заголовке буфера номера устройства и бло-
ка, соответствующие данному дисковому блоку, и помещает буфер в хеш-очередь.
Ядро использует буфер, не переписав информацию, которую буфер прежде хранил
для другого дискового блока. Тот процесс, который будет искать прежний дис-
ковый блок, не обнаружит его в пуле и получит для него точно таким же обра-
зом новый буфер из списка свободных буферов. Когда ядро заканчивает работу с
буфером, оно освобождает буфер вышеописанным способом. На Рисунке 3.7, нап-
ример, ядро ищет блок 18, но не находит его в хеш-очереди, помеченной как
живает файлы на внешних запоминающих устройствах больщой емкости, таких как
диски, и позволяет процессам сохранять новую информацию или вызывать ранее
сохраненную информацию. Если процессу необходимо обратиться к информации
файла, ядро выбирает информацию в оперативную память, где процесс сможет
просматривать эту информацию, изменять ее и обращаться с просьбой о ее пов-
торном сохранении в файловой системе. Вспомним для примера программу copy,
приведенную на Рисунке 1.3: ядро читает данные из первого файла в память и
затем записывает эти данные во второй файл. Подобно тому, как ядро должно
заносить данные из файла в память, оно так же должно считывать в память и
вспомогательные данные для работы с ними. Например, суперблок файловой сис-
темы содержит помимо всего прочего информацию о свободном пространстве, дос-
тупном файловой системе. Ядро считывает суперблок в память для того, чтобы
иметь доступ к его информации, и возвращает его опять файловой системе, ког-
да желает сохранить его содержимое. Похожая вещь происходит с индексом, ко-
торый описывает размещение файла. Ядро системы считывает индекс в память,
когда желает получить доступ к информации файла, и возвращает индекс вновь
файловой системе, когда желает скорректировать размещение файла. Ядро обра-
батывает такую вспомогательную информацию, не будучи прежде знакома с ней и
не требуя для ее обработки запуска каких-либо процессов.
Ядро могло бы производить чтение и запись непосредственно с диска и на
диск при всех обращениях к файловой системе, однако время реакции системы и
производительность при этом были бы низкими из-за низкой скорости передачи
данных с диска. По этой причине ядро старается свести к минимуму частоту об-
ращений к диску, заведя специальную область внутренних информационных буфе-
ров, именуемую буферным кешем (*) и хранящую содержимое блоков диска, к ко-
торым перед этим производились обращения.
На Рисунке 2.1 показано, что модуль буферного кеша занимает в архитекту-
ре ядра место между подсистемой управления файлами и драйверами устройств
(ввода-вывода блоками). Перед чтением информации с диска ядро пытается счи-
тать что-нибудь из буфера кеша. Если в этом буфере отсутствует информация,
ядро читает данные с диска и заносит их в буфер, используя алгоритм, который
имеет целью поместить в буфере как можно больше необходимых данных. Анало-
гично, информация, записываемая на диск, заносится в буфер для того, чтобы
находиться там, если ядро позднее попытается считать ее. Ядро также старает-
ся свести к минимуму частоту выполнения операций записи на диск, выясняя,
должна ли информация действительно запоминаться на диске или это промежуточ-
ные данные, которые будут вскоре затерты. Алгоритмы более высокого уровня
позволяют производить предварительное занесение данных в буфер кеша или за-
держивать запись данных с тем, чтобы усилить эффект использования буфера. В
этой главе рассматриваются алгоритмы, используемые ядром при работе с буфе-
рами в сверхоперативной памяти.
-----------------------------------------
(*) Буферный кеш представляет собой программную структуру, которую не следу-
ет путать с аппаратными кешами, ускоряющими косвенную адресацию памяти.
39
Во время инициализации системы ядро выделяет место под совокупность бу-
феров, потребность в которых определяется в зависимости от размера памяти и
производительности системы. Каждый буфер состоит из двух частей: области па-
мяти, в которой хранится информация, считываемая с диска, и заголовка буфе-
ра, который идентифицирует буфер. Поскольку существует однозначное соответс-
твие между заголовками буферов и массивами данных, в нижеследующем тексте
используется термин "буфер" в ссылках как на ту, так и на другую его состав-
ляющую, и о какой из частей буфера идет речь будет понятно из контекста.
Информация в буфере соответствует информации в одном логическом блоке
диска в файловой системе, и ядро распознает содержимое буфера, просматривая
идентифицирующие поля в его заголовке. Буфер представляет собой копию диско-
вого блока в памяти; содержимое дискового блока отображается в буфер, но это
отображение временное, поскольку оно имеет место до того момента, когда ядро
примет решение отобразить в буфер другой дисковый блок. Один дисковый блок
не может быть одновременно отображен в несколько буферов. Если бы два буфера
содержали информацию для одного и того же дискового блока, ядро не смогло бы
определить, в каком из буферов содержится текущая информация, и, возможно,
возвратило бы на диск некорректную информацию. Предположим, например, что
дисковый блок отображается в два буфера, A и B. Если ядро запишет данные
сначала в буфер A, а затем в буфер B, дисковый блок будет содержать данные
из буфера B, если в результате операций записи буфер заполнится до конца.
Однако, если ядро изменит порядок, в котором оно копирует содержимое буферов
на диск, на противоположный, дисковый блок будет содержать некорректные дан-
ные.
Заголовок буфера (Рисунок 3.1) содержит поле "номер устройства" и поле
"номер блока", которые определяют файловую систему и номер блока с информа-
цией на диске и однозначно идентифицируют буфер. Номер устройства - это ло-
гический номер файловой системы
+------------------+
| номер устройства |
+------------------+ указатель на
| номер блока | область данных
+------------------+ +------------->
указатель на | поле состояния | |
предыдущий буфер +------------------+ |
в хеш-очереди | ------+---+
<-------------+ +------------------+
| | ------+----------------->
| +------------------+ указатель на
+---+------ | следующий буфер
+------------------+ в хеш-очереди
| ------+---+
+------------------+ |
<-----------------+------ | |
указатель на +------------------+ +------------->
предыдущий буфер указатель на
в списке свободных следующий буфер
в списке свободных
Рисунок 3.1. Заголовок буфера
(см. раздел 2.2.1), а не физический номер устройства (диска). Заголовок бу-
фера также содержит указатель на область памяти для буфера, размер которой
должен быть не меньше размера дискового блока, и поле состояния, в котором
суммируется информация о текущем состоянии буфера. Состояние буфера предс-
тавляет собой комбинацию из следующих условий:
* буфер заблокирован (термины "заблокирован (недоступен)" и "занят" равноз-
40
начны, так же, как и понятия "свободен" и "доступен"),
* буфер содержит правильную информацию,
* ядро должно переписать содержимое буфера на диск перед тем, как переназна-
чить буфер; это условие известно, как "задержка, вызванная записью",
* ядро читает или записывает содержимое буфера на диск,
* процесс ждет освобождения буфера.
В заголовке буфера также содержатся два набора указателей, используемые
алгоритмами выделения буфера, которые поддерживают общую структуру области
буферов (буферного пула), о чем подробнее будет говориться в следующем раз-
деле.
Ядро помещает информацию в область буферов, используя алгоритм поиска
буферов, к которым наиболее долго не было обращений: после выделения буфера
дисковому блоку нельзя использовать этот
+----------------------------------------------------------------+
| указатели вперед |
| +-------------------+ +-------+ +-------+ +-------+ |
+->| заголовок списка |--->| буфер |--->| буфер |--->| буфер |--+
+--| свободных буферов |<---| 1 |<---| 2 |<---| n |<-+
| +-------------------+ +-------+ +-------+ +-------+ |
| указатели назад |
+----------------------------------------------------------------+
до
после
+----------------------------------------------------------------+
| указатели вперед |
| +-------------------+ +-------+ +-------+ |
+->| заголовок списка |---------------->| буфер |--->| буфер |--+
+--| свободных буферов |<----------------| 2 |<---| n |<-+
| +-------------------+ +-------+ +-------+ |
| указатели назад |
+----------------------------------------------------------------+
Рисунок 3.2. Список свободных буферов
буфер для другого блока до тех пор, пока не будут задействованы все осталь-
ные буферы. Ядро управляет списком свободных буферов, который необходим для
работы указанного алгоритма. Этот список представляет собой циклический пе-
речень буферов с двунаправленными указателями и с формальными заголовками в
начале и в конце перечня (Рисунок 3.2). Все буферы попадают в список при
загрузке системы. Если нужен любой свободный буфер, ядро выбирает буфер из
"головы" списка, но если в области буферов ищется определенный блок, может
быть выбран буфер и из середины списка. И в том, и в другом случае буфер
удаляется из списка свободных буферов. Если ядро возвращает буфер буферному
пулу, этот буфер добавляется в хвост списка, либо в "голову" списка (в слу-
чае ошибки), но никогда не в середину. По мере удаления буферов из списка
буфер с нужной информацией продвигается все ближе и ближе к "голове" списка
(Рисунок 3.2). Следовательно, те буферы, которые находятся ближе к "голове"
списка, в последний раз использовались раньше, чем буферы, находящиеся даль-
ше от "головы" списка.
Когда ядро обращается к дисковому блоку, оно сначала ищет буфер с соот-
ветствующей комбинацией номеров устройства и блока. Вместо того, чтобы прос-
матривать всю область буферов, ядро организует из буферов особые очереди,
41
хешированные по номеру устройства и номеру блока. В хеш-очереди ядро уста-
навливает для буферов циклическую связь в виде списка с двунаправленными
указателями, структура которого похожа на структуру списка свободных буфе-
ров. Количество буферов в хеш-очереди варьируется в течение всего времени
функционирования системы, в чем мы еще убедимся дальше. Ядро вынуждено при-
бегать к функции хеширования, чтобы единообразно распределять буферы между
хеш-очередями, однако функция хеширования должна быть несложной, чтобы не
пострадала производительность системы. Администраторы системы задают коли-
чество хеш-очередей при генерации операционной системы.
заголовки хеш-очередей
+-----------------+
| | +----+ +----+ +----+
<----| блок 0 модуль 4 |------| 28 |-----| 4 |-----| 64 |---->
| | +----+ +----+ +----+
+-----------------+
| | +----+ +----+ +----+
<----| блок 1 модуль 4 |------| 17 |-----| 5 |-----| 97 |---->
| | +----+ +----+ +----+
+-----------------+
| | +----+ +----+ +----+
<----| блок 2 модуль 4 |------| 98 |-----| 50 |-----| 10 |---->
| | +----+ +----+ +----+
+-----------------+
| | +----+ +----+ +----+
<----| блок 3 модуль 4 |------| 3 |-----| 35 |-----| 99 |---->
| | +----+ +----+ +----+
+-----------------+
Рисунок 3.3. Буферы в хеш-очередях
На Рисунке 3.3 изображены буферы в хеш-очередях: заголовки хеш-очередей
показаны в левой части рисунка, а квадратиками в каждой строке показаны бу-
феры в соответствующей хеш-очереди. Так, квадратики с числами 28, 4 и 64
представляют буферы в хеш-очереди для "блока 0 модуля 4". Пунктирным линиям
между буферами соответствуют указатели вперед и назад вдоль хеш-очереди; для
простоты на следующих рисунках этой главы данные указатели не показываются,
но их присутствие подразумевается. Кроме того, на рисунке блоки идентифици-
руются только своими номерами и функция хеширования построена на использова-
нии только номеров блоков; однако на практике также используется номер уст-
ройства.
Любой буфер всегда находится в хеш-очереди, но его положение в очереди
не имеет значения. Как уже говорилось, никакая пара буферов не может однов-
ременно содержать данные одного и того же дискового блока; поэтому каждый
дисковый блок в буферном пуле существует в одной и только одной хеш-очереди
и представлен в ней только один раз. Тем не менее, буфер может находиться в
списке свободных буферов, если его статус "свободен". Поскольку буфер может
быть одновременно в хеш-очереди и в списке свободных буферов, у ядра есть
два способа его обнаружения. Ядро просматривает хеш-очередь, если ему нужно
найти определенный буфер, и выбирает буфер из списка свободных буферов, если
ему нужен любой свободный буфер. В следующем разделе будет показано, каким
образом ядро осуществляет поиск определенных дисковых блоков в буферном ке-
ше, а также как оно работает с буферами в хеш-очередях и в списке свободных
буферов. Еще раз напомним: буфер всегда находится в хеш -очереди, а в списке
свободных буферов может быть, но может и отсутствовать.
42
Как показано на Рисунке 2.1, алгоритмы верхнего уровня, используемые яд-
ром для подсистемы управления файлами, инициируют выполнение алгоритмов уп-
равления буферным кешем. При выборке блока алгоритмы верхнего уровня уста-
навливают логический номер устройства и номер блока, к которым они хотели бы
получить доступ. Например, если процесс хочет считать данные из файла, ядро
устанавливает, в какой файловой системе находится файл и в каком блоке фай-
ловой системы содержатся данные, о чем подробнее мы узнаем из главы 4. Соби-
раясь считать данные из определенного дискового блока, ядро проверяет, нахо-
дится ли блок в буферном пуле, и если нет, назначает для него свободный бу-
фер. Собираясь записать данные в определенный дисковый блок, ядро проверяет,
находится ли блок в буферном пуле, и если нет, назначает для этого блока
свободный буфер. Для выделения буферов из пула в алгоритмах чтения и записи
дисковых блоков используется операция getblk (Рисунок 3.4).
Рассмотрим в этом разделе пять возможных механизмов использования getblk
для выделения буфера под дисковый блок.
1. Ядро обнаруживает блок в хеш-очереди, соответствующий ему буфер сво-
боден.
2. Ядро не может обнаружить блок в хеш-очереди, поэтому оно выделяет бу-
фер из списка свободных буферов.
3. Ядро не может обнаружить блок в хеш-очереди и, пытаясь выделить буфер
из списка свободных буферов (как в случае 2), обнаруживает в списке
буфер, который помечен как "занят на время записи". Ядро должно пере-
писать этот буфер на диск и выделить другой буфер.
4. Ядро не может обнаружить блок в хеш-очереди, а список свободных буфе-
ров пуст.
5. Ядро обнаруживает блок в хеш-очереди, но его буфер в настоящий момент
занят.
Обсудим каждый случай более подробно.
Осуществляя поиск блока в буферном пуле по комбинации номеров устройства
и блока, ядро ищет хеш-очередь, которая бы содержала этот блок. Просматривая
хеш-очередь, ядро придерживается списка с указателями, пока (как в первом
случае) не найдет буфер с искомыми номерами устройства и блока. Ядро прове-
ряет занятость блока и в том случае, если он свободен, помечает буфер "заня-
тым" для того, чтобы другие процессы (**) не смогли к нему обратиться. Затем
ядро удаляет буфер из списка свободных буферов, поскольку буфер не может од-
новременно быть занятым и находиться в указанном списке. Если другие процес-
сы попытаются обратиться к блоку в то время, когда его буфер занят, они при-
остановятся до тех пор, пока буфер не освободится. На Рисунке 3.5 показан
первый случай, когда ядро ищет блок 4 в хеш-очереди, помеченной как "блок 0
модуль 4". Обнаружив буфер, ядро удаляет его из списка свободных буферов,
делая блоки 5 и 28 соседями в списке.
----------------------------------------
(**) Из предыдущей главы напомним, что все операции ядра производятся в кон-
тексте процесса, выполняемого в режиме ядра. Таким образом, слова "дру-
гие процессы" относятся к процессам, тоже выполняющимся в режиме ядра.
Эти слова мы будем использовать и тогда, когда будем говорить о взаимо-
действии нескольких процессов, работающих в режиме ядра; и будем гово-
рить "ядро", когда взаимодействие между процессами будет отсутствовать.
43
+------------------------------------------------------------------+
| алгоритм getblk |
| входная информация: номер файловой системы номер блока |
| выходная информация: буфер, который можно использовать для блока|
| { выполнить если (буфер не найден) |
| { если (блок в хеш-очереди) |
| { если (буфер занят) /* случай 5 */ |
| { |
| приостановиться (до освобождения буфера); |
| продолжить; /* цикл с условием продолжения */ |
| } |
| пометить буфер занятым; /* случай 1 */ |
| удалить буфер из списка свободных буферов; |
| вернуть буфер; |
| } |
| в противном случае /* блока нет в хеш-очереди */ |
| { |
| если (в списке нет свободных буферов) /*случай 4*/ |
| { |
| приостановиться (до освобождения любого буфера); |
| продолжить; /* цикл с условием продолжения */ |
| } |
| удалить буфер из списка свободных буферов; |
| если (буфер помечен для отложенной переписи) |
| /* случай 3 */ |
| { |
| асинхронная перепись содержимого буфера на диск; |
| продолжить; /* цикл с условием продолжения */ |
| } |
| /* случай 2 -- поиск свободного буфера */ |
| удалить буфер из старой хеш-очереди; |
| включить буфер в новую хеш-очередь; |
| вернуть буфер; |
| } |
| } |
| } |
+------------------------------------------------------------------+
Рисунок 3.4. Алгоритм выделения буфера
заголовки хеш-очередей
+-----------------+ +-----------------+
| | |+----+ +----+| +----+
| блок 0 модуль 4 |---- ++ 28 ++ ++ 4 ++ | 64 |
+-----------------+ +----+| +------+ +----+
| | +----+| +----+| +----+
| блок 1 модуль 4 |---- | 17 || ++ 5 ++ ++ 97 ++
| | +----+| |+----+ +-++----+|
+-----------------+ +---|--------+ +------+
| | +----+ |+----+ |+----+
| блок 2 модуль 4 |---- | 98 |+---+| 50 | ++ 10 ++
+-----------------+ +----+| +----+ +----+|
| | +----+| +----+ +----+|
| блок 3 модуль 4 |----+>| 3 ++ | 35 | | 99 ||
+-----------------+ | +----+ +----+ +----+|
+-----------------+ | |
|заголовок списка +----+ |
|свободных буферов|<---------------------------------+
+-----------------+
(а) Поиск блока 4 в первой хеш-очереди
44
заголовки хеш-очередей
+-----------------+ +--------------+
| | +----+| +----+ |+----+
| блок 0 модуль 4 |---- ++ 28 ++ | 4 | || 64 |
| | |+----+ +----+ |+----+
+-----------------+ +-----------------+ |
| | +----+ +----+| |+----+
| блок 1 модуль 4 |---- | 17 | ++ 5 ++ ++ 97 ++
| | +----+ |+----+ +----+|
+-----------------+ | +------+
| | +----+ |+----+ |+----+
| блок 2 модуль 4 |---- | 98 |+---+| 50 | ++ 10 ++
| | +----+| +----+ +----+|
+-----------------+ | |
| | +----+| +----+ +----+|
| блок 3 модуль 4 |----+>| 3 ++ | 35 | | 99 ||
| | | +----+ +----+ +----+|
+-----------------+ | |
+-----------------+ | |
|заголовок списка +----+ |
| | |
|свободных буферов|<---------------------------------+
+-----------------+
(б) Удаление блока 4 из списка свободных буферов
Рисунок 3.5. Поиск буфера - случай 1: буфер в хеш-очереди
+------------------------------------------------------------+
| алгоритм brelse |
| входная информация: заблокированный буфер |
| выходная информация: отсутствует |
| { |
| возобновить выполнение всех процессов при наступлении |
| события, связанного с освобождением любого буфера; |
| возобновить выполнение всех процессов при наступлении |
| события, связанного с освобождением данного буфера; |
| поднять приоритет прерывания процессора так, чтобы |
| блокировать любые прерывания; |
| если (содержимое буфера верно и буфер не старый) |
| поставить буфер в конец списка свободных буферов |
| в противном случае |
| поставить буфер в начало списка свободных буферов |
| понизить приоритет прерывания процессора с тем, чтобы |
| вновь разрешить прерывания; |
| разблокировать (буфер); |
| } |
+------------------------------------------------------------+
Рисунок 3.6. Алгоритм высвобождения буфера
Перед тем, как перейти к остальным случаям, рассмотрим, что произойдет с
буфером после того, как он будет выделен блоку. Ядро системы сможет читать
данные с диска в буфер и обрабатывать их или же переписывать данные в буфер
и при желании на диск. Ядро оставляет у буфера пометку "занят"; другие про-
45
цессы не могут обратиться к нему и изменить его содержимое, пока он занят,
таким образом поддерживается целостность информации в буфере. Когда ядро за-
канчивает работу с буфером, оно освобождает буфер в соответствии с алгорит-
мом brelse (Рисунок 3.6). Возобновляется выполнение тех процессов, которые
были приостановлены из-за того, что буфер был занят, а также те процессы,
которые были приостановлены из-за того, что список свободных буферов был
пуст. Как в том, так и в другом случае, высвобождение буфера означает, что
буфер становится доступным для приостановленных процессов несмотря на то,
что первый процесс, получивший буфер, заблокировал его и запретил тем самым
получение буфера другими процессами (см. раздел 2.2.2.4). Ядро помещает бу-
фер в конец списка свободных буферов, если только перед этим не произошла
ошибка ввода-вывода или если буфер не помечен как "старый" - момент, который
будет пояснен далее; в остальных случаях буфер помещается в начало списка.
Теперь буфер свободен для использования любым процессом.
Ядро выполняет алгоритм brelse в случае, когда буфер процессу больше не
нужен, а также при обработке прерывания от диска для высвобождения буферов,
используемых при асинхронном вводе-выводе с диска и на диск (см. раздел
3.4). Ядро повышает приоритет прерывания работы процессора так, чтобы запре-
тить возникновение любых прерываний от диска на время работы со списком сво-
бодных буферов, предупреждая искажение указателей буфера в результате вло-
женного выполнения алгоритма brelse. Похожие последствия могут произойти,
если программа обработки прерываний запустит алгоритм brelse во время выпол-
нения процессом алгоритма getblk, поэтому ядро повышает приоритет прерывания
работы процессора и в стратегических моментах выполнения алгоритма getblk.
Более подробно эти случаи мы разберем с помощью упражнений.
При выполнении алгоритма getblk имеет место случай 2, когда ядро прос-
матривает хеш-очередь, в которой должен был бы находиться блок, но не нахо-
дит его там. Так как блок не может быть ни в какой другой хеш-очереди, пос-
кольку он не должен "хешироваться" в
заголовки хеш-очередей
+-----------------+ +-----------------+
| | |+----+ +----+| +----+
| блок 0 модуль 4 |---- ++ 28 ++ ++ 4 ++ | 64 |
| | +----+| |+----+ +----+
+-----------------+ | +------+
| | +----+| +----+| +----+
| блок 1 модуль 4 |---- | 17 || ++ 5 ++ ++ 97 ++
| | +----+| |+----+ +-++----+|
+-----------------+ +---|--------+ +------+
| | +----+ |+----+ |+----+
| блок 2 модуль 4 |---- | 98 |+---+| 50 | ++ 10 ++
| | +----+| +----+ +----+|
+-----------------+ | |
| | +----+| +----+ +----+|
| блок 3 модуль 4 |----+>| 3 ++ | 35 | | 99 ||
| | | +----+ +----+ +----+|
+-----------------+ | |
+-----------------+ | |
|заголовок списка +----+ |
| | |
|свободных буферов|<---------------------------------+
+-----------------+
(а) Поиск блока 18 - отсутствует в кеше
46
заголовки хеш-очередей
+-----------------+ +-----------------+
| | |+----+ +----+| +----+
| блок 0 модуль 4 |---- ++ 28 ++ ++ 4 ++ | 64 |
| | +----+| |+----+ +----+
+-----------------+ | +------+
| | +----+| +----+| +----+
| блок 1 модуль 4 |---- | 17 || +->| 5 ++ ++ 97 ++
| | +----+| | +----+ +-++----+|
+-----------------+ +-|----------+ +------+
| | +----+ | +----+ |+----+ +----+
| блок 2 модуль 4 |---- | 98 | | | 50 | ++ 10 ++ | 18 |
| | +----+ | +----+ +----+| +----+
+-----------------+ | |
| | | +----+ +----+|
| блок 3 модуль 4 |---- | | 35 | | 99 ||
+-----------------+ | +----+ +----+|
+-----------------+ | |
|заголовок списка +--------------+ |
|свободных буферов|<---------------------------------+
+-----------------+
(б) Удаление первого блока из списка свободных буферов, назначение блока 18
Рисунок 3.7. Второй случай выделения буфера
другом месте, следовательно, его нет в буферном кеше. Поэтому ядро удаляет
первый буфер из списка свободных буферов; этот буфер был уже выделен другому
дисковому блоку и также находится в хеш-очереди. Если буфер не помечен для
отложенной переписи, ядро помечает буфер занятым, удаляет его из хеш-очере-
ди, где он находится, назначает в заголовке буфера номера устройства и бло-
ка, соответствующие данному дисковому блоку, и помещает буфер в хеш-очередь.
Ядро использует буфер, не переписав информацию, которую буфер прежде хранил
для другого дискового блока. Тот процесс, который будет искать прежний дис-
ковый блок, не обнаружит его в пуле и получит для него точно таким же обра-
зом новый буфер из списка свободных буферов. Когда ядро заканчивает работу с
буфером, оно освобождает буфер вышеописанным способом. На Рисунке 3.7, нап-
ример, ядро ищет блок 18, но не находит его в хеш-очереди, помеченной как