Морис Бах - Архитектура операционной системы UNIX

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). Ядро помещает буфер в конец списка свободных буферов, если только перед этим не произошла ошибка ввода-вывода или если буфер не помечен как «старый» — момент, который будет пояснен далее; в остальных случаях буфер помещается в начало списка. Теперь буфер свободен для использования любым процессом.