Как уже говорилось в предыдущей главе, ядро операционной системы поддер-
живает файлы на внешних запоминающих устройствах больщой емкости, таких как
диски, и позволяет процессам сохранять новую информацию или вызывать ранее
сохраненную информацию. Если процессу необходимо обратиться к информации
файла, ядро выбирает информацию в оперативную память, где процесс сможет
просматривать эту информацию, изменять ее и обращаться с просьбой о ее пов-
торном сохранении в файловой системе. Вспомним для примера программу copy,
приведенную на Рисунке 1.3: ядро читает данные из первого файла в память и
затем записывает эти данные во второй файл. Подобно тому, как ядро должно
заносить данные из файла в память, оно так же должно считывать в память и
вспомогательные данные для работы с ними. Например, суперблок файловой сис-
темы содержит помимо всего прочего информацию о свободном пространстве, дос-
тупном файловой системе. Ядро считывает суперблок в память для того, чтобы
иметь доступ к его информации, и возвращает его опять файловой системе, ког-
да желает сохранить его содержимое. Похожая вещь происходит с индексом, ко-
торый описывает размещение файла. Ядро системы считывает индекс в память,
когда желает получить доступ к информации файла, и возвращает индекс вновь
файловой системе, когда желает скорректировать размещение файла. Ядро обра-
батывает такую вспомогательную информацию, не будучи прежде знакома с ней и
не требуя для ее обработки запуска каких-либо процессов.
Ядро могло бы производить чтение и запись непосредственно с диска и на
диск при всех обращениях к файловой системе, однако время реакции системы и
производительность при этом были бы низкими из-за низкой скорости передачи
данных с диска. По этой причине ядро старается свести к минимуму частоту об-
ращений к диску, заведя специальную область внутренних информационных буфе-
ров, именуемую буферным кешем (*) и хранящую содержимое блоков диска, к ко-
торым перед этим производились обращения.
На Рисунке 2.1 показано, что модуль буферного кеша занимает в архитекту-
ре ядра место между подсистемой управления файлами и драйверами устройств
(ввода-вывода блоками). Перед чтением информации с диска ядро пытается счи-
тать что-нибудь из буфера кеша. Если в этом буфере отсутствует информация,
ядро читает данные с диска и заносит их в буфер, используя алгоритм, который
имеет целью поместить в буфере как можно больше необходимых данных. Анало-
гично, информация, записываемая на диск, заносится в буфер для того, чтобы
находиться там, если ядро позднее попытается считать ее. Ядро также старает-
ся свести к минимуму частоту выполнения операций записи на диск, выясняя,
должна ли информация действительно запоминаться на диске или это промежуточ-
ные данные, которые будут вскоре затерты. Алгоритмы более высокого уровня
позволяют производить предварительное занесение данных в буфер кеша или за-
держивать запись данных с тем, чтобы усилить эффект использования буфера. В
этой главе рассматриваются алгоритмы, используемые ядром при работе с буфе-
рами в сверхоперативной памяти.
(*) Буферный кеш представляет собой программную структуру, которую не следу-
ет путать с аппаратными кешами, ускоряющими косвенную адресацию памяти.
39
3.1 ЗАГОЛОВКИ БУФЕРА
Во время инициализации системы ядро выделяет место под совокупность бу-
феров, потребность в которых определяется в зависимости от размера памяти и
производительности системы. Каждый буфер состоит из двух частей: области па-
мяти, в которой хранится информация, считываемая с диска, и заголовка буфе-
ра, который идентифицирует буфер. Поскольку существует однозначное соответс-
твие между заголовками буферов и массивами данных, в нижеследующем тексте
используется термин "буфер" в ссылках как на ту, так и на другую его состав-
ляющую, и о какой из частей буфера идет речь будет понятно из контекста.
Информация в буфере соответствует информации в одном логическом блоке
диска в файловой системе, и ядро распознает содержимое буфера, просматривая
идентифицирующие поля в его заголовке. Буфер представляет собой копию диско-
вого блока в памяти; содержимое дискового блока отображается в буфер, но это
отображение временное, поскольку оно имеет место до того момента, когда ядро
примет решение отобразить в буфер другой дисковый блок. Один дисковый блок
не может быть одновременно отображен в несколько буферов. Если бы два буфера
содержали информацию для одного и того же дискового блока, ядро не смогло бы
определить, в каком из буферов содержится текущая информация, и, возможно,
возвратило бы на диск некорректную информацию. Предположим, например, что
дисковый блок отображается в два буфера, A и B. Если ядро запишет данные
сначала в буфер A, а затем в буфер B, дисковый блок будет содержать данные
из буфера B, если в результате операций записи буфер заполнится до конца.
Однако, если ядро изменит порядок, в котором оно копирует содержимое буферов
на диск, на противоположный, дисковый блок будет содержать некорректные дан-
ные.
Заголовок буфера (Рисунок 3.1) содержит поле "номер устройства" и поле
"номер блока", которые определяют файловую систему и номер блока с информа-
цией на диске и однозначно идентифицируют буфер. Номер устройства - это ло-
гический номер файловой системы
+------------------+
| номер устройства |
+------------------+ указатель на
| номер блока | область данных
+------------------+ +------------->
указатель на | поле состояния | |
предыдущий буфер +------------------+ |
в хеш-очереди | ------+---+
<-------------+ +------------------+
| | ------+----------------->
| +------------------+ указатель на
+---+------ | следующий буфер
+------------------+ в хеш-очереди
| ------+---+
+------------------+ |
<-----------------+------ | |
указатель на +------------------+ +------------->
предыдущий буфер указатель на
в списке свободных следующий буфер
в списке свободных
Рисунок 3.1. Заголовок буфера
(см. раздел 2.2.1), а не физический номер устройства (диска). Заголовок бу-
фера также содержит указатель на область памяти для буфера, размер которой
должен быть не меньше размера дискового блока, и поле состояния, в котором
суммируется информация о текущем состоянии буфера. Состояние буфера предс-
тавляет собой комбинацию из следующих условий:
* буфер заблокирован (термины "заблокирован (недоступен)" и "занят" равноз-
40
начны, так же, как и понятия "свободен" и "доступен"),
* буфер содержит правильную информацию,
* ядро должно переписать содержимое буфера на диск перед тем, как переназна-
чить буфер; это условие известно, как "задержка, вызванная записью",
* ядро читает или записывает содержимое буфера на диск,
* процесс ждет освобождения буфера.
В заголовке буфера также содержатся два набора указателей, используемые
алгоритмами выделения буфера, которые поддерживают общую структуру области
буферов (буферного пула), о чем подробнее будет говориться в следующем раз-
деле.
3.2 СТРУКТУРА ОБЛАСТИ БУФЕРОВ (БУФЕРНОГО ПУЛА)
Ядро помещает информацию в область буферов, используя алгоритм поиска
буферов, к которым наиболее долго не было обращений: после выделения буфера
дисковому блоку нельзя использовать этот
+----------------------------------------------------------------+
| указатели вперед |
| +-------------------+ +-------+ +-------+ +-------+ |
+->| заголовок списка |--->| буфер |--->| буфер |--->| буфер |--+
+--| свободных буферов |<---| 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
3.3 МЕХАНИЗМ ПОИСКА БУФЕРА
Как показано на Рисунке 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, но не находит его в хеш-очереди, помеченной как
"блок 2 модуль 4". Поэтому ядро удаляет первый буфер из списка свободных бу-
феров (блок 3), назначает его блоку 18 и помещает его в соответствующую
хеш-очередь.
Если при выполнении алгоритма getblk имеет место случай 3, ядро так же
должно выделить буфер из списка свободных буферов. Однако, оно обнаруживает,
что удаляемый из списка буфер был помечен для отложенной переписи, поэтому
прежде чем использовать буфер ядро должно переписать его содержимое на диск.
Ядро приступает к асинхронной записи на диск и пытается выделить другой бу-
фер из списка. Когда асинхронная запись заканчивается, ядро освобождает бу-
фер и помещает его в начало списка свободных буферов. Буфер сам продвинулся
от конца списка свободных буферов к началу списка. Если после асинхронной
переписи ядру бы понадобилось поместить буфер в конец списка, буфер получил
бы "зеленую улицу" по всему списку свободных буферов, результат такого пере-
мещения противоположен действию алгоритма поиска буферов, к которым наиболее
долго не было обращений. Например, если обратиться к Рисунку 3.8, ядро не
смогло обнаружить блок 18, но когда попыталось выделить первые два буфера
(по очереди) в списке свободных буферов, то оказалось, что они оба помечены
для отложенной переписи. Ядро удалило их из списка, запустило операции пере-
писи на диск в соответствующие блоки, и выделило третий буфер из списка,
блок 4. Далее ядро присвоило новые значения полям буфера "номер устройства"
и "номер блока" и включило буфер, получивший имя "блок 18", в новую хеш-оче-
редь.
47
В четвертом случае (Рисунок 3.9) ядро, работая с процессом A, не смогло
найти дисковый блок в соответствующей хеш-очереди и предприняло попытку вы-
делить из списка свободных буферов новый буфер, как в случае 2. Однако, в
списке не оказалось ни одного буфера, поэтому процесс A приостановился до
тех пор, пока другим процессом не будет выполнен алгоритм brelse, высвобож-
дающий буфер. Планируя выполнение процесса A, ядро вынуждено снова просмат-
ривать хеш-очередь в поисках блока. Оно не в состоянии немедленно выделить
буфер из списка свободных буферов, так как возможна ситуация, когда свобод-
ный буфер ожидают сразу несколько процессов и одному из них будет выделен
вновь освободившийся буфер, на который уже нацелился процесс A. Таким обра-
зом, алгоритм поиска блока снова гарантирует, что только один буфер включает
содержимое дискового блока. На Рисунке 3.10 показана конкуренция между двумя
процессами за освободившийся буфер.
Последний случай (Рисунок 3.11) наиболее сложный, поскольку он связан с
комплексом взаимоотношений между несколькими процессами. Предположим, что
ядро, работая с процессом A, ведет поиск дискового блока и выделяет буфер,
но приостанавливает выполнение процесса перед освобождением буфера. Напри-
мер, если процесс A по-
пытается считать дисковый блок и выделить буфер, как в случае 2, то он при-
остановится до момента завершения передачи данных с диска. Предположим, что
пока процесс A приостановлен, ядро активизирует второй процесс, B, который
пытается обратиться к дисковому блоку, чей буфер был только что заблокирован
процессом A. Процесс B (случай 5) обнаружит этот захваченный блок в хеш-оче-
реди. Так как использовать захваченный буфер не разрешается и, кроме того,
нельзя выделить для одного и того же дискового блока второй буфер, процесс B
помечает буфер как "запрошенный" и затем приостанавливается до того момента,
когда процесс A освободит данный буфер.
В конце концов процесс A освобождает буфер и замечает, что он запрошен.
Тогда процесс A "будит" все процессы, приостановленные по событию "буфер
становится свободным", включая и процесс B. Когда же ядро вновь запустит на
выполнение процесс B, процесс B должен будет убедиться в том, что буфер сво-
заголовки хеш-очередей
+-----------------+ +-----------------+
| | |+----+ +----+| +----+
| блок 0 модуль 4 |---- ++ 28 ++ ++ 4 ++ | 64 |
| | +----+| |+----+ +----+
+-----------------+ | +------+
| | +----+| +----+| +----+
| блок 1 модуль 4 |---- | 17 || +-+ 5 ++ ++ 97 ++
| | +----+| | +----+ +-++----+|
+-----------------+ +--|отсрочка-+ +------+
| | +----+ | +----+ |+----+
| блок 2 модуль 4 |---- | 98 |+--+ | 50 | ++ 10 ++
| | +----+| +----+ +----+|
+-----------------+ | |
| | +----+| +----+ +----+|
| блок 3 модуль 4 |----+>| 3 ++ | 35 | | 99 ||
| | | +----+ +----+ +----+|
+-----------------+ |отсрочка |
+-----------------+ | |
|заголовок списка +----+ |
| | |
|свободных буферов|<---------------------------------+
+-----------------+
(а) При поиске блока 18 в списке свободных буферов обнаружены
блоки с отсроченной записью
48
заголовки хеш-очередей
+-----------------+
| | +----+ +----+
| блок 0 модуль 4 |----+>| 28 +------------+ | 64 |
| | | +----+ | +----+
+-----------------+ | |
| | | +----+ +----+ | +----+
| блок 1 модуль 4 |----| | 17 | | 5 | +-->| 97 ++
| | | +----+ +----+ +----+|
+-----------------+ | запись +------+
| | | +----+ +----+ |+----+ +----+
| блок 2 модуль 4 |----| | 98 | | 50 | ++ 10 ++ | 18 |
| | | +----+ +----+ +----+| +----+
+-----------------+ | |
| | | +----+ +----+ +----+|
| блок 3 модуль 4 |----| | 3 | | 35 | | 99 ||
| | | +----+ +----+ +----+|
+-----------------+ | запись |
+-----------------+ | |
|заголовок списка +----+ |
| | |
|свободных буферов|<---------------------------------+
+-----------------+
(б) Перепись блоков 3 и 5, переназначение блока 4 на блок 18
Рисунок 3.8. Третий случай выделения буфера
заголовки хеш-очередей
+-----------------+
| | +----+ +----+ +----+
| блок 0 модуль 4 |---- | 28 | | 4 | | 64 |
| | +----+ +----+ +----+
+-----------------+
| | +----+ +----+ +----+
| блок 1 модуль 4 |---- | 17 | | 5 | | 97 |
| | +----+ +----+ +----+
+-----------------+
| | +----+ +----+ +----+
| блок 2 модуль 4 |---- | 98 | | 50 | | 10 |
| | +----+ +----+ +----+
+-----------------+
| | +----+ +----+ +----+
| блок 3 модуль 4 |---- | 3 | | 35 | | 99 |
| | +----+ +----+ +----+
+-----------------+
+-----------------+
|заголовок списка +---------+
| | |
|свободных буферов|<--------+
+-----------------+
Поиск блока 18, список свободных буферов пуст
Рисунок 3.9. Четвертый случай выделения буфера
боден. Возможно, что третий процесс, C, ждал освобождения этого же буфера, и
49
ядро запланировало активизацию процесса C раньше B; при этом процесс C мог
приостановиться и оставить буфер заблокированным. Следовательно, процесс B
должен проверить то, что блок действительно свободен.
Процесс B также должен убедиться в том, что в буфере содержится первона-
чально затребованный дисковый блок, поскольку процесс C мог выделить данный
буфер другому блоку, как в случае 2. При выполнении процесса B может обнару-
житься, что он ждал освобождения буфера не с тем содержимым, поэтому процес-
су B придется вновь заниматься поисками блока. Если же его настроить на ав-
томатическое выделение буфера из списка свободных буферов, он может упустить
из виду возможность того, что какой-либо другой процесс уже выделил буфер
для данного блока.
Процесс A Процесс B
+-------------------------------------------------------------
| Не может найти блок b -
| в хеш-очереди -
| -
| Список свободных буфе- -
| ров пуст -
| -
| Процесс приостановлен -
| - Не может найти блок b
| - в хеш-очереди
| -
| - Список свободных буфе-
| - ров пуст
| -
| - Процесс приостановлен
| - -
| +------------------------------------------------------+
| | Некоторый процесс освобождает буфер: операция brelse |
| +------------------------------------------------------+
| - Выбирает буфер из
| - списка свободных буферов
| -
| - Назначает этот буфер
| - блоку b
| -
v
Время
Рисунок 3.10. Состязание за свободный буфер
В конце концов, процесс B найдет этот блок, при необходимости выбрав но-
вый буфер из списка свободных буферов, как в случае 2. Пусть некоторый про-
цесс, осуществляя поиск блока 99 (Рисунок 3.11), обнаружил этот блок в
хеш-очереди, однако он оказался занятым. Процесс приостанавливается до мо-
мента освобождения блока, после чего он запускает весь алгоритм с самого на-
чала. На Рисунке 3.12 показано содержимое занятого буфера.
Алгоритм выделения буфера должен быть надежным; процессы не должны "за-
сыпать" навсегда и рано или поздно им нужно выделить буфер. Ядро гарантирует
такое положение, при котором все процессы, ожидающие выделения буфера, про-
должат свое выполнение, благодаря тому, что ядро распределяет буферы во вре-
мя обработки обращений к операционной системе и освобождает их перед возвра-
том управления процессам (***). В режиме задачи процессы непосредс-
(***) Исключением является системная операция mount, которая зах-
50
ватывает буфер до тех пор, пока не будет исполнена операция
umount. Это исключение не является существенным, поскольку
общее количество буферов намного превышает число активных
монтированных файловых систем.
заголовки хеш-очередей
+-----------------+ +-----------------+
| | |+----+ +----+| +----+
| блок 0 модуль 4 |---- ++ 28 ++ ++ 4 ++ | 64 |
| | +----+| |+----+ +----+
+-----------------+ | +------+
| | +----+| +----+| +----+
| блок 1 модуль 4 |---- | 17 || ++ 5 ++ ++ 97 ++
| | +----+| |+----+ +-++----+|
+-----------------+ +---|--------+ +------+
| | +----+ |+----+ |+----+
| блок 2 модуль 4 |---- | 98 |+---+| 50 | ++ 10 ++
| | +----+| +----+ +----+|
+-----------------+ | |
| | +----+| +----+ +----+|
| блок 3 модуль 4 |----+>| 3 ++ | 35 | | 99 ||
| | | +----+ +----+ +----+|
+-----------------+ | занят|
+-----------------+ | |
|заголовок списка +----+ |
| | |
|свободных буферов|<---------------------------------+
+-----------------+
Поиск блока 99, блок занят
Рисунок 3.11. Пятый случай выделения буфера
твенно не контролируют выделение буферов ядром системы, поэтому они не могут
намеренно "захватывать" буферы. Ядро теряет контроль над буфером только тог-
да, когда ждет завершения операции ввода-вывода между буфером и диском. Было
задумано так, что если дисковод испорчен, он не может прерывать работу цент-
рального процессора, и тогда ядро никогда не освободит буфер. Дисковод дол-
жен следить за работой аппаратных средств в таких случаях и возвращать ядру
код ошибки, сообщая о плохой работе диска. Короче говоря, ядро может гаран-
тировать, что процессы, приостановленные в ожидании буфера, в конце концов
возобновят свое выполнение.
Можно также представить себе ситуацию, когда процесс "зависает" в ожида-
нии получения доступа к буферу. В четвертом случае, например, если несколько
процессов приостанавливаются, ожидая освобождения буфера, ядро не гарантиру-
ет, что они получат доступ к буферу в той очередности, в которой они запро-
сили доступ. Процесс может приостановить и возобновить свое выполнение, ког-
да буфер станет свободным, только для того, чтобы приостановиться вновь из
-за того, что другой процесс получил управление над буфером первым. Теорети-
чески, так может продолжаться вечно, но практически такой проблемы не возни-
кает в связи с тем, что в системе обычно заложено большое количество буфе-
ров.
3.4 ЧТЕНИЕ И ЗАПИСЬ ДИСКОВЫХ БЛОКОВ
Теперь, когда алгоритм выделения буферов нами уже рассмотрен, будет лег-
че понять процедуру чтения и записи дисковых блоков. Чтобы считать дисковый
51
Процесс A Процесс B Процесс C
+-------------------------------------------------------------
| Буфер выделен блоку b - -
| - -
| Буфер заблокирован - -
| - -
| Начат ввод-вывод - -
| - -
| Приостановлен до - -
| завершения ввода-вывода - -
| - - -
| - Поиск блока b -
| - в хеш-очереди -
| - -
| - Буфер заблокирован, -
| - приостановка -
| - - -
| - - Приостановлен
| - - в ожидании освобождения
| - - любого буфера
| - - (случай 4)
| +---------------------------+ - -
| | Ввод-вывод закончен, | - -
| | выполнение возобновляется | - -
| +---------------------------+ - -
| brelse(): возобновляются - -
| другие процессы - -
| - - Получает буфер,
| - - первоначально
| - - назначенный
| - - блоку b
| - -
| - - Переназначение
| - - буфера блоку b'
| - Буфер не содержит -
| - блок b -
| - -
| - Поиск начинается -
| - снова -
| Время
v
Рисунок 3.12. Состязание за свободный буфер
блок (Рисунок 3.13), процесс использует алгоритм getblk для поиска блока в
буферном кеше. Если он там, ядро может возвратить его немедленно без физи-
ческого считывания блока с диска. Если блок в кеше отсутствует, ядро прика-
зывает дисководу "запланировать" запрос на чтение и приостанавливает работу,
ожидая завершения ввода-вывода. Дисковод извещает контроллер диска о том,
что он собирается считать информацию, и контроллер тогда передает информацию
в буфер. Наконец, дисковый
контроллер прерывает работу процессора, сообщая о завершении операции во-
да-вывода, и программа обработки прерываний от диска возобновляет выполнение
приостановленного процесса; теперь содержимое дискового блока находится в
буфере. Модули, запросившие информацию данного блока, получают ее; когда бу-
фер им уже не потребуется, они освободят его для того, чтобы другие процессы
52
+------------------------------------------------------------+
| алгоритм bread /* чтение блока */ |
| входная информация: номер блока в файловой системе |
| выходная информация: буфер, содержащий данные |
| { |
| получить буфер для блока (алгоритм getblk); |
| если (данные в буфере правильные) |
| возвратить буфер; |
| приступить к чтению с диска; |
| приостановиться (до завершения операции чтения); |
| возвратить (буфер); |
| } |
+------------------------------------------------------------+
Рисунок 3.13. Алгоритм чтения дискового блока
получили к нему доступ.
В главе 5 будет показано, как модули более высокого уровня (такие как
подсистема управления файлами) могут предчувствовать потребность во втором
дисковом блоке, когда процесс читает информацию из файла последовательно.
Эти модули формируют запрос на асинхронное выполнение второй операции вво-
да-вывода, надеясь на то, что информация уже будет в памяти, когда вдруг
возникнет необходимость в ней, и тем самым повышая быстродействие системы.
Для этого ядро выполняет алгоритм чтения блока с продвижением breada (Рису-
нок 3.14). Ядро проверяет, находится ли в кеше первый блок, и если его там
нет, приказывает дисководу считать этот блок. Если в буферном кеше отсутст-
вует и второй блок, ядро дает команду дисководу считать асинхронно и его.
Затем процесс приостанавливается, ожидая завершения операции ввода-вывода
над первым блоком. Когда выполнение процесса возобновляется, он возвращает
буфер первому блоку и не обращает внимание на то, когда завершится операция
ввода-вывода для второго блока. После завершения этой операции контроллер
диска прерывает работу системы; программа обработки прерываний узнает о том,
что ввод-вывод выполнялся асинхронно, и освобождает буфер (алгоритм brelse).
Если бы она не освободила буфер, буфер остался бы заблокированным и по этой
причине недоступным для всех процессов. Невозможно заранее разблокировать
буфер, так как операция ввода-вывода, связанная с буфером, активна и, следо-
вательно, содержимое буфера еще не адекватно. Позже, если процесс пожелает
считать второй блок, он обнаружит его в буферном кеше, поскольку к тому вре-
мени операция ввода-вывода закончится. Если же, в начале выполнения алгорит-
ма breada, первый блок обнаружился в буферном кеше, ядро тут же проверяет,
находится там же и второй блок, и продолжает работу по только что описанной
схеме.
Алгоритм записи содержимого буфера в дисковый блок (Рисунок 3.15) похож
на алгоритм чтения. Ядро информирует дисковод о том, что есть буфер, содер-
жимое которого должно быть выведено, и дисковод планирует операцию ввода-вы-
вода блока. Если запись производится синхронно, вызывающий процесс приоста-
навливается, ожидая ее
завершения и освобождая буфер в момент возобновления своего выполнения. Если
запись производится асинхронно, ядро запускает операцию записи на диск, но
не ждет ее завершения. Ядро освободит буфер, когда завершится ввод-вывод.
Могут возникнуть ситуации, и это будет показано в следующих двух главах,
когда ядро не записывает данные немедленно на диск. Если запись "откладыва-
ется", ядро соответствующим образом помечает буфер, освобождая его по алго-
ритму brelse, и продолжает работу без планирования ввода-вывода. Ядро запи-
сывает блок на диск перед тем, как другой процесс сможет переназначить буфер
другому блоку, как показано в алгоритме getblk (случай 3). Между тем, ядро
надеется на то, что процесс получает доступ до того, как буфер будет перепи-
53
+------------------------------------------------------------+
| алгоритм breada /* чтение блока с продвижением */ |
| входная информация: (1) в файловой системе номер блока для |
| немедленного считывания |
| (2) в файловой системе номер блока для |
| асинхронного считывания |
| выходная информация: буфер с данными, считанными немедленно|
| { |
| если (первый блок отсутствует в кеше) |
| { |
| получить буфер для первого блока (алгоритм getblk);|
| если (данные в буфере неверные) |
| приступить к чтению с диска; |
| } |
| если (второй блок отсутствует в кеше) |
| { |
| получить буфер для второго блока (алгоритм getblk);|
| если (данные в буфере верные) |
| освободить буфер (алгоритм brelse); |
| в противном случае |
| приступить к чтению с диска; |
| } |
| если (первый блок первоначально находился в кеше) |
| { |
| считать первый блок (алгоритм bread); |
| возвратить буфер; |
| } |
| приостановиться (до того момента, когда первый буфер |
| будет содержать верные данные); |
| возвратить буфер; |
| } |
+------------------------------------------------------------+
Рисунок 3.14. Алгоритм чтения блока с продвижением
сан на диск; если этот процесс впоследствии изменит содержимое буфера, ядро
произведет дополнительную операцию по сохранению изменений на диске.
Отложенная запись отличается от асинхронной записи. Выполняя асинхронную
+------------------------------------------------------------+
| алгоритм bwrite /* запись блока */ |
| входная информация: буфер |
| выходная информация: отсутствует |
| { |
| приступить к записи на диск; |
| если (ввод-вывод синхронный) |
| { |
| приостановиться (до завершения ввода-вывода); |
| освободить буфер (алгоритм brelse); |
| } |
| в противном случае если (буфер помечен для отложенной |
| записи) |
| пометить буфер для последующего размещения в |
| "голове" списка свободных буферов; |
| } |
+------------------------------------------------------------+
Рисунок 3.15. Алгоритм записи дискового блока
54
запись, ядро запускает дисковую операцию немедленно, но не дожидается ее за-
вершения. Что касается отложенной записи, ядро отдаляет момент физической
переписи на диск насколько возможно; затем по алгоритму getblk (случай 3)
оно помечает буфер
как "старый" и записывает блок на диск асинхронно. После этого контроллер
диска прерывает работу системы и освобождает буфер, используя алгоритм
brelse; буфер помещается в "голову" списка свободных буферов, поскольку он
имеет пометку "старый". Благодаря наличию двух выполняющихся асинхронно опе-
раций ввода-вывода - чтения блока с продвижением и отложенной записи - ядро
может запускать программу brelse из программы обработки прерываний. Следова-
тельно, ядро вынуждено препятствовать возникновению прерываний при выполне-
нии любой процедуры, работающей со списком свободных буферов, поскольку
brelse помещает буферы в этот список.
3.5 ПРЕИМУЩЕСТВА И НЕУДОБСТВА БУФЕРНОГО КЕША
Использование буферного кеша имеет, с одной стороны, несколько преиму-
ществ и, с другой стороны, некоторые неудобства.
* Использование буферов позволяет внести единообразие в процедуру обраще-
ния к диску, поскольку ядру нет необходимости знать причину ввода-выво-
да. Вместо этого, ядро копирует данные в буфер и из буфера, невзирая на
то, являются ли данные частью файла, индекса или суперблока. Буферизация
ввода-вывода с диска повышает модульность разработки программ, поскольку
те составные части ядра, которые занимаются вводом-выводом на диск, име-
ют один интерфейс на все случаи. Короче говоря, упрощается проектирова-
ние системы.
* Система не накладывает никаких ограничений на выравнивание информации
пользовательскими процессами, выполняющими ввод-вывод, поскольку ядро
производит внутреннее выравнивание информации. В различных аппаратных
реализациях часто требуется выравнивать информацию для ввода-вывода с
диска определенным образом, т.е. производить к примеру двухбайтное или
четырехбайтное выравнивание данных в памяти. Без механизма буферизации
программистам пришлось бы заботиться самим о правильном выравнивании
данных. По этой причине на машинах с ограниченными возможностями в вы-
равнивании адресов возникает большое количество ошибок программирования
и, кроме того, становится проблемой перенос программ в операционную сре-
ду UNIX. Копируя информацию из пользовательских буферов в системные бу-
феры (и обратно), ядро системы устраняет необходимость в специальном вы-
равнивании пользовательских буферов, делая пользовательские программы
более простыми и мобильными.
* Благодаря использованию буферного кеша, сокращается объем дискового тра-
фика и время реакции и повышается общая производительность системы. Про-
цессы, считывающие данные из файловой системы, могут обнаружить информа-
ционные блоки в кеше и им не придется прибегать ко вводу-выводу с диска.
Ядро часто применяет "отложенную запись", чтобы избежать лишних обраще-
ний к диску, оставляя блок в буферном кеше и надеясь на попадание блока
в кеш. Очевидно, что шансы на такое попадание выше в системах с большим
количеством буферов. Тем не менее, число буферов, которые можно заложить
в системе, ограничивается объемом памяти, доступной выполняющимся про-
цессам: если под буферы задействовать слишком много памяти, то система
будет работать медленнее в связи с тем, что ей придется заниматься под-
качкой и замещением выполняющихся процессов.
* Алгоритмы буферизации помогают поддерживать целостность файловой систе-
мы, так как они сохраняют общий, первоначальный и единственный образ
дисковых блоков, содержащихся в кеше. Если два процесса одновременно по-
пытаются обратиться к одному и тому же дисковому блоку, алгоритмы буфе-
55
ризации (например, getblk) параллельный доступ преобразуют в последова-
тельный, предотвращая разрушение данных.
* Сокращение дискового трафика является важным преимуществом с точки зре-
ния обеспечения хорошей производительности или быстрой реакции системы,
однако стратегия кеширования также имеет некоторые неудобства. Так как
ядро в случае отложенной записи не переписывает данные на диск немедлен-
но, такая система уязвима для сбоев, которые оставляют дисковые данные в
некорректном виде. Хотя в последних версиях системы и сокращен ущерб,
наносимый катастрофическими сбоями, основная проблема остается: пользо-
ватель, запрашивающий выполнение операции записи, никогда не знает, в
какой момент данные завершат свой путь на диск (****).
* Использование буферного кеша требует дополнительного копирования инфор-
мации при ее считывании и записи пользовательскими процессами. Процесс,
записывающий данные, передает их ядру и ядро копирует данные на диск;
процесс, считывающий данные, получает их от ядра, которое читает данные
с диска. При передаче большого количества данных дополнительное копиро-
вание отрицательным образом отражается на производительности системы,
однако при передаче небольших объемов данных производительность повыша-
ется, поскольку ядро буферизует данные (используя алгоритм getblk и от-
ложенную запись) до тех пор, пока это представляется эффективным с точки
зрения экономии времени работы с диском.
3.6 ВЫВОДЫ
В данной главе была рассмотрена структура буферного кеша и различные
способы, которыми ядро размещает блоки в кеше. В алгоритмах буферизации со-
четаются несколько простых идей, которые в сумме обеспечивают работу меха-
низма кеширования. При работе с блоками в буферном кеше ядро использует ал-
горитм замены буферов, к которым наиболее долго не было обращений, предпола-
гая, что к
блокам, к которым недавно было обращение, вероятно, вскоре обратятся снова.
Очередность, в которой буферы появляются в списке свободных буферов, соот-
ветствует очередности их предыдущего использования. Остальные алгоритмы обс-
луживания буферов, типа "первым пришел - первым вышел" и замещения редко ис-
пользуемых, либо являются более сложными в реализации, либо снижают процент
попадания в кеш. Использование функции хеширования и хеш-очередей дает ядру
возможность ускорить поиск заданных блоков, а использование двунаправленных
указателей в списках облегчает исключение буферов.
Ядро идентифицирует нужный ему блок по номеру логического устройства и
номеру блока. Алгоритм getblk просматривает буферный кеш в поисках блока и,
если буфер присутствует и свободен, блокирует буфер и возвращает его. Если
буфер заблокирован, обратившийся к нему процесс приостанавливается до тех
пор, пока буфер не освободится. Механизм блокирования гарантирует, что толь-
ко один процесс в каждый момент времени работает с буфером. Если в кеше блок
отсутствует, ядро назначает блоку свободный буфер, блокирует и возвращает
его. Алгоритм bread выделяет блоку буфер и при необходимости читает туда ин-
формацию. Алгоритм bwrite копирует информацию в предварительно выделенный
буфер. Если при выполнении указанных алгоритмов ядро не увидит необходимости
в немедленном копировании данных на диск, оно пометит буфер для "отложенной
записи", чтобы избежать излишнего ввода-вывода. К сожалению, процедура отк-
(****) Стандартный набор операций ввода-вывода в программах на языке Си
включает операцию fflush. Эта функция занимается подкачиванием данных
из буферов в пользовательском адресном пространстве в рабочую область
ядра. Тем не менее пользователю не известно, когда ядро запишет дан-
ные на диск.
56
ладывания записи сопровождается тем, что процесс никогда не уверен, в какой
момент данные физически попадают на диск. Если ядро записывает данные на
диск синхронно, оно поручает драйверу диска передать блок файловой системе и
ждет прерывания, сообщающего об окончании ввода-вывода.
Существует множество способов использования ядром буферного кеша. Пос-
редством буферного кеша ядро обеспечивает обмен данными между прикладными
программами и файловой системой, передачу дополнительной системной информа-
ции, например, индексов, между алгоритмами ядра и файловой системой. Ядро
также использует буферный кеш, когда читает программы в память для выполне-
ния. В следующих главах будет рассмотрено множество алгоритмов, использующих
процедуры, описанные в данной главе. Другие алгоритмы, которые кешируют ин-
дексы и страницы памяти, также используют приемы, похожие на те, что описаны
для буферного кеша.
3.7 УПРАЖНЕНИЯ
1. Рассмотрим функцию хеширования применительно к Рисунку 3.3. Наилучшей
функцией хеширования является та, которая единым образом распределяет
блоки между хеш-очередями. Что Вы могли бы предложить в качестве опти-
мальной функции хеширования ? Должна ли эта функция в своих расчетах ис-
пользовать логический номер устройства ?
2. В алгоритме getblk, если ядро удаляет буфер из списка свободных буферов,
оно должно повысить приоритет прерывания работы процессора так, чтобы
блокировать прерывания до проверки списка. Почему ?
*3. В алгоритме getblk ядро должно повысить приоритет прерывания работы про-
цессора так, чтобы блокировать прерывания до проверки занятости блока.
(Это не показано в тексте.) Почему ?
4. В алгоритме brelse ядро помещает буфер в "голову" списка свободных буфе-
ров, если содержимое буфера неверно. Если содержимое буфера неверно, дол-
жен ли буфер появиться в хеш-очереди ?
5. Предположим, что ядро выполняет отложенную запись блока. Что произойдет,
когда другой процесс выберет этот блок из его хешочереди ? Из списка сво-
бодных буферов ?
*6. Если несколько процессов оспаривают буфер, ядро гарантирует, что ни один
из них не приостановится навсегда, но не гарантирует, что процесс не "за-
виснет" и дождется получения буфера. Переделайте алгоритм getblk так,
чтобы процессу было в конечном итоге гарантировано получение буфера.
7. Переделайте алгоритмы getblk и brelse так, чтобы ядро следовало не схеме
замещения буферов, к которым наиболее долго не было обращений, а схеме
"первым пришел - первым вышел". Повторите то же самое со схемой замещения
редко используемых буферов.
8. Опишите ситуацию в алгоритме bread, когда информация в буфере уже верна.
*9. Опишите различные ситуации, встречающиеся в алгоритме breada. Что прои-
зойдет в случае следующего выполнения алгоритма bread или breada, когда
текущий блок прочитан с продвижением ? В алгоритме breada, если первый
или второй блок отсутствует в кеше, в дальнейшем при проверке правильнос-
ти содержимого буфера предполагается, что блок мог быть в буферном пуле.
Как это может быть ?
10. Опишите алгоритм, запрашивающий и получающий любой свободный буфер из
буферного пула. Сравните этот алгоритм с getblk.
11. В различных системных операциях, таких как umount и sync (глава 5), тре-
буется, чтобы ядро перекачивало на диск содержимое всех буферов, которые
помечены для "отложенной записи" в данной файловой системе. Опишите ал-
горитм, реализующий перекачку буферов. Что произойдет с очередностью
расположения буферов в списке свободных буферов в результате этой опера-
ции ? Как ядро может гарантировать, что ни один другой процесс не подбе-
рется к буферу с пометкой "отложенная запись" и не сможет переписать его
содержимое в файловую систему, пока процесс перекачки приостановлен в
57
ожидании завершения операции ввода-вывода ?
12. Определим время реакции системы как среднее время выполнения системного
вызова. Определим пропускную способность системы как количество процес-
сов, которые система может выполнять в данный период времени. Объясните,
как буферный кеш может способствовать повышению реакции системы. Способ-
ствует ли он с неизбежностью увеличению пропускной способности системы ?
58