3.3 МЕХАНИЗМ ПОИСКА БУФЕРА
Как показано на Рисунке 2.1, алгоритмы верхнего уровня, используемые ядром для подсистемы управления файлами, инициируют выполнение алгоритмов управления буферным кешем. При выборке блока алгоритмы верхнего уровня устанавливают логический номер устройства и номер блока, к которым они хотели бы получить доступ. Например, если процесс хочет считать данные из файла, ядро устанавливает, в какой файловой системе находится файл и в каком блоке файловой системы содержатся данные, о чем подробнее мы узнаем из главы 4. Собираясь считать данные из определенного дискового блока, ядро проверяет, находится ли блок в буферном пуле, и если нет, назначает для него свободный буфер. Собираясь записать данные в определенный дисковый блок, ядро проверяет, находится ли блок в буферном пуле, и если нет, назначает для этого блока свободный буфер. Для выделения буферов из пула в алгоритмах чтения и записи дисковых блоков используется операция getblk (Рисунок 3.4).
Рассмотрим в этом разделе пять возможных механизмов использования getblk для выделения буфера под дисковый блок.
1. Ядро обнаруживает блок в хеш-очереди, соответствующий ему буфер свободен.
2. Ядро не может обнаружить блок в хеш-очереди, поэтому оно выделяет буфер из списка свободных буферов.
3. Ядро не может обнаружить блок в хеш-очереди и, пытаясь выделить буфер из списка свободных буферов (как в случае 2), обнаруживает в списке буфер, который помечен как «занят на время записи». Ядро должно переписать этот буфер на диск и выделить другой буфер.
4. Ядро не может обнаружить блок в хеш-очереди, а список свободных буферов пуст.
5. Ядро обнаруживает блок в хеш-очереди, но его буфер в настоящий момент занят.
Обсудим каждый случай более подробно.
Осуществляя поиск блока в буферном пуле по комбинации номеров устройства и блока, ядро ищет хеш-очередь, которая бы содержала этот блок. Просматривая хеш-очередь, ядро придерживается списка с указателями, пока (как в первом случае) не найдет буфер с искомыми номерами устройства и блока. Ядро проверяет занятость блока и в том случае, если он свободен, помечает буфер «занятым» для того, чтобы другие процессы[8] не смогли к нему обратиться. Затем ядро удаляет буфер из списка свободных буферов, поскольку буфер не может одновременно быть занятым и находиться в указанном списке. Если другие процессы попытаются обратиться к блоку в то время, когда его буфер занят, они приостановятся до тех пор, пока буфер не освободится. На Рисунке 3.5 показан первый случай, когда ядро ищет блок 4 в хеш-очереди, помеченной как «блок 0 модуль 4». Обнаружив буфер, ядро удаляет его из списка свободных буферов, делая блоки 5 и 28 соседями в списке.
алгоритм getblk
входная информация: номер файловой системы номер блока
выходная информация: буфер, который можно использовать для блока
{
do if (буфер не найден) {
if (блок в хеш-очереди) {
if (буфер занят) { /* случай 5 */
sleep (до освобождения буфера);
continue; /* цикл с условием продолжения */
}
пометить буфер занятым; /* случай 1 */
удалить буфер из списка свободных буферов;
return буфер;
}
else { /* блока нет в хеш-очереди */
if (в списке нет свободных буферов) { /*случай 4*/
sleep (до освобождения любого буфера);
continue; /* цикл с условием продолжения */
}
удалить буфер из списка свободных буферов;
if (буфер помечен для отложенной переписи) { /* случай 3 */
асинхронная перепись содержимого буфера на диск;
continue; /* цикл с условием продолжения */
}
/* случай 2 — поиск свободного буфера */
удалить буфер из старой хеш-очереди;
включить буфер в новую хеш-очередь;
return буфер;
}
}
}
Рисунок 3.4. Алгоритм выделения буфера
Рисунок 3.5. Поиск буфера — случай 1: буфер в хеш-очереди
алгоритм brelse
входная информация: заблокированный буфер
выходная информация: отсутствует
{
возобновить выполнение всех процессов при наступлении события, связанного с освобождением любого буфера;
возобновить выполнение всех процессов при наступлении события, связанного с освобождением данного буфера;
поднять приоритет прерывания процессора так, чтобы блокировать любые прерывания;
if (содержимое буфера верно и буфер не старый) поставить буфер в конец списка свободных буферов;
else поставить буфер в начало списка свободных буферов;
понизить приоритет прерывания процессора с тем, чтобы вновь разрешить прерывания;
разблокировать (буфер);
}
Рисунок 3.6. Алгоритм высвобождения буфера
Перед тем, как перейти к остальным случаям, рассмотрим, что произойдет с буфером после того, как он будет выделен блоку. Ядро системы сможет читать данные с диска в буфер и обрабатывать их или же переписывать данные в буфер и при желании на диск. Ядро оставляет у буфера пометку «занят»; другие процессы не могут обратиться к нему и изменить его содержимое, пока он занят, таким образом поддерживается целостность информации в буфере. Когда ядро заканчивает работу с буфером, оно освобождает буфер в соответствии с алгоритмом brelse (Рисунок 3.6). Возобновляется выполнение тех процессов, которые были приостановлены из-за того, что буфер был занят, а также те процессы, которые были приостановлены из-за того, что список свободных буферов был пуст. Как в том, так и в другом случае, высвобождение буфера означает, что буфер становится доступным для приостановленных процессов несмотря на то, что первый процесс, получивший буфер, заблокировал его и запретил тем самым получение буфера другими процессами (см. раздел 2.2.2.4). Ядро помещает буфер в конец списка свободных буферов, если только перед этим не произошла ошибка ввода-вывода или если буфер не помечен как «старый» — момент, который будет пояснен далее; в остальных случаях буфер помещается в начало списка. Теперь буфер свободен для использования любым процессом.
8
Из предыдущей главы напомним, что все операции ядра производятся в контексте процесса, выполняемого в режиме ядра. Таким образом, слова «другие процессы» относятся к процессам, тоже выполняющимся в режиме ядра. Эти слова мы будем использовать и тогда, когда будем говорить о взаимодействии нескольких процессов, работающих в режиме ядра; и будем говорить «ядро», когда взаимодействие между процессами будет отсутствовать.