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

Например, если программа обработки прерывания от диска работает с буферными очередями, то часть прерываемой программы, при выполнении которой ядро обрабатывает буферные очереди, является критической секцией по отношению к программе обработки прерывания от диска. Критические секции невелики по размеру и встречаются нечасто, поэтому их существование не оказывает практически никакого воздействия на производительность системы. В других операционных системах данный вопрос решается путем запрещения любых прерываний при работе в системных режимах или путем разработки схем блокировки, обеспечивающих целостность. В главе 12 мы еще вернемся к этому вопросу, когда будем говорить о многопроцессорных системах, где применения указанных мер для решения проблемы недостаточно.
 
       struct queue {
       } *bp, *bp1;
       bp1-›forp = bp-›forp;
       bp1-›backp = bp;
       bp-›forp = bp1; /* здесь рассмотрите возможность переключения контекста */
       bp1-›forp-›backp = bp1;
       Рисунок 2.7. Пример программы, создающей список с двунаправленными указателями
 

       Рисунок 2.8. Список с указателями, некорректный из-за переключения контекста
 
      Чтобы подвести черту, еще раз скажем, что ядро защищает свою целостность, разрешая переключение контекста только тогда, когда процесс переходит в состояние «сна», а также препятствуя воздействию одного процесса на другой с целью изменения состояния последнего. Оно также повышает приоритет прерывания процессора на время выполнения критических секций программ, запрещая таким образом прерывания, которые в противном случае могут вызвать нарушение целостности. Планировщик процессов периодически выгружает процессы, выполняющиеся в режиме задачи, для того, чтобы процессы не могли монопольно использовать центральный процессор.

2.2.2.4 «Сон» и пробуждение

      Процесс, выполняющийся в режиме ядра, имеет значительную степень автономии в решении того, как ему следует реагировать на возникновение системных событий. Процессы могут общаться между собой и «предлагать» различные альтернативы, но при этом окончательное решение они принимают самостоятельно. Мы еще увидим, что существует набор правил, которым подчиняется поведение процессов в различных обстоятельствах, но каждый процесс в конечном итоге следует этим правилам по своей собственной инициативе. Например, если процесс должен временно приостановить выполнение («перейти ко сну»), он это делает по своей доброй воле. Следовательно, программа обработки прерываний не может приостановить свое выполнение, ибо если это случится, прерванный процесс должен был бы «перейти ко сну» по умолчанию.
      Процессы приостанавливают свое выполнение, потому что они ожидают возникновения некоторого события, например, завершения ввода-вывода на периферийном устройстве, выхода, выделения системных ресурсов и т. д. Когда говорят, что процесс приостановился по событию, то имеется ввиду, что процесс находится в состоянии «сна» до наступления события, после чего он пробудится и перейдет в состояние «готовности к выполнению». Одновременно могут приостановиться по событию много процессов; когда событие наступает, все процессы, приостановленные по событию, пробуждаются, поскольку значение условия, связанного с событием, больше не является «истинным». Когда процесс пробуждается, он переходит из состояния «сна» в состояние «готовности к выполнению», находясь в котором он уже может быть выбран планировщиком; следует обратить внимание на то, что он не выполняется немедленно. Приостановленные процессы не занимают центральный процессор. Ядру системы нет надобности постоянно проверять то, что процесс все еще приостановлен, т. к. ожидает наступления события, и затем будить его.
      Например, процесс, выполняемый в режиме ядра, должен иногда блокировать структуру данных на случай приостановки в будущем; процессы, пытающиеся обратиться к заблокированной структуре, обязаны проверить наличие блокировки и приостановить свое выполнение, если структура заблокирована другим процессом. Ядро выполняет блокировки такого рода следующим образом:
 
      while (условие «истинно») sleep (событие: условие принимает значение «ложь»);
      set condition true;
 
      Ядро снимает блокировку и «будит» все процессы, приостановленные из-за этой блокировки, следующим образом:
 
      set condition false;
      wakeup (событие: условие «ложно»);
 
      На Рисунке 2.9 приведен пример, в котором три процесса, A, B и C оспаривают заблокированный буфер. Переход в состояние «сна» вызывается заблокированностью буфера. Процессы, однажды запустившись, обнаруживают, что буфер заблокирован, и приостанавливают свое выполнение до наступления события, по которому буфер будет разблокирован. В конце концов блокировка с буфера снимается и все процессы «пробуждаются», переходя в состояние «готовности к выполнению». Ядро наконец выбирает один из процессов, скажем, B, для выполнения. Процесс B, выполняя цикл «while», обнаруживает, что буфер разблокирован, блокирует его и продолжает свое выполнение. Если процесс B в дальнейшем снова приостановится без снятия блокировки с буфера (например, ожидая завершения операции ввода-вывода), ядро сможет приступить к планированию выполнения других процессов. Если будет при этом выбран процесс A, этот процесс, выполняя цикл «while», обнаружит, что буфер заблокирован, и снова перейдет в состояние «сна»; возможно то же самое произойдет и с процессом C. В конце концов выполнение процесса B возобновится и блокировка с буфера будет снята, в результате чего процессы A и C получат доступ к нему. Таким образом, цикл «while-sleep» обеспечивает такое положение, при котором самое большее один процесс может иметь доступ к ресурсу.
      Алгоритмы перехода в состояние «сна» и пробуждения более подробно будут рассмотрены в главе 6. Тем временем они будут считаться «неделимыми». Процесс переходит в состояние «сна» мгновенно и находится в нем до тех пор, пока не будет «разбужен». После того, как он приостанавливается, ядро системы начинает планировать выполнение следующего процесса и переключает контекст на него.

2.3 СТРУКТУРЫ ДАННЫХ ЯДРА

      Большинство информационных структур ядра размещается в таблицах фиксированного размера, а не в динамически выделенной памяти. Преимущество такого подхода состоит в том, что программа ядра проста, но в ней ограничивается число элементов информационной структуры до значения, предварительно заданного при генерации системы. Если во время функционирования системы число элементов информационной структуры ядра выйдет за указанное значение, ядро не сможет динамически выделить место для новых элементов и должно сообщить об ошибке пользователю, сделавшему запрос. Если, с другой стороны, ядро сгенерировано таким образом, что выход за границы табличного пространства будет маловероятен, дополнительное табличное пространство может не понадобиться, поскольку оно не может быть использовано для других целей. Как бы то ни было, простота алгоритмов ядра представляется более важной, чем сжатие последних байтов оперативной памяти. Обычно в алгоритмах для поиска свободных мест в таблицах используются несложные циклы и этот метод более понятен и иногда более эффективен по сравнению с более сложными схемами выделения памяти.

2.4 УПРАВЛЕНИЕ СИСТЕМОЙ

      К управляющим процессам, грубо говоря, относятся те процессы, которые выполняют различные функции по обеспечению благополучной работы пользователей системы. К таким функциям относятся форматирование дисков, создание новых файловых систем, восстановление разрушенных файловых систем, отладка ядра и др. С концептуальной точки зрения, между управляющими и пользовательскими процессами нет разницы. Они используют один и тот же набор обращений к операционной системе, доступный для всех. Управляющие процессы отличаются от обычных пользовательских процессов только правами и привилегиями, которыми они обладают. Например, режимы разрешения доступа к файлу могут предусматривать предоставление возможности работы с файлами для управляющих процессов и отсутствие такой возможности для обычных пользователей. Внутри системы ядро выделяет особого пользователя, именуемого суперпользователем, и наделяет его особыми привилегиями, о чем мы еще поговорим ниже. Пользователь может стать суперпользователем, если соответствующим образом зарегистрируется в системе или запустит специальную программу. Привилегии суперпользователя будут рассмотрены в следующих главах. Если сказать коротко, ядро системы не выделяет управляющие процессы в отдельный класс.

       Рисунок 2.9. Многократная приостановка выполнения процессов, вызванная блокировкой

2.5 ВЫВОДЫ И ОБЗОР ПОСЛЕДУЮЩИХ ГЛАВ

      В этой главе описана архитектура ядра операционной системы; его основными компонентами выступают подсистема управления файлами и подсистема управления процессами. Подсистема управления файлами управляет хранением и выборкой данных в пользовательских файлах. Файлы организованы в виде файловых систем, которые трактуются как логические устройства; физическое устройство, такое как диск, может содержать несколько логических устройств (файловых систем). Каждая файловая система имеет суперблок, в котором описывается структура и содержимое файловой системы, каждый файл в файловой системе описывается индексом, хранящим атрибуты файла. Системные операции работают с файлами, используя индексы.
      Процессы находятся в различных состояниях и переходят из состояния в состояние, следуя определенным правилам перехода. В частности, процессы, выполняющиеся в режиме ядра, могут приостановить свое выполнение и перейти в состояние «сна», но ни один процесс не может перевести в это состояние другой процесс. Ядро является невыгружаемым и это означает, что процесс, выполняющийся в режиме ядра, будет продолжать свое выполнение до тех пор, пока не перейдет в состояние «сна» или пока не вернется в режим задачи. Ядро обеспечивает целостность своих информационных структур благодаря своей невыгружаемости, а также путем блокирования прерываний на время выполнения критических секций программы.
      В остальных частях главы детально описываются подсистемы, изображенные на Рисунке 2.1, а также взаимодействие между ними, начиная с подсистемы управления файлами и включая подсистему управления процессами. В следующей главе рассматривается буфер сверхоперативной памяти (кеш) и описываются алгоритмы управления буфером, используемые в главах 4, 5 и 7. В главе 4 рассматриваются внутренние алгоритмы файловой системы, включая обработку индексов, структуру файлов, преобразование имени пути в индекс. В главе 5 рассматриваются системные операции, которые, используя приведенные в главе 4 алгоритмы, обращаются к файловой системе, т. е. такие, как open, close, read и write. Глава 6 имеет дело с понятием контекста процесса и его адресным пространством, а глава 7 рассматривает системные операции, связанные с управлением процессами и использующие алгоритмы главы 6. Глава 8 касается планирования выполнения процессов, в главе 9 обсуждаются алгоритмы распределения памяти. Глава 10 посвящена драйверам устройств, рассмотрение которых до того откладывалось, чтобы прежде объяснить связь драйвера терминала с управлением процессами. В главе 11 представлено несколько форм взаимодействия процессов. Наконец, в последних двух главах рассматриваются вопросы, связанные с углубленным изучением особенностей системы, в частности, особенности многопроцессорных систем и распределенных систем.

2.6 УПРАЖНЕНИЯ

      1. Рассмотрим следующий набор команд:
      grep main a.c b.c c.c › grepout&
      wc -1 ‹ grepout&
      rm grepout&
      Амперсанд (символ "&") в конце каждой командной строки говорит командному процессору shell о том, что команду следует выполнить на фоне, при этом shell может выполнять все командные строки параллельно. Почему это не равноценно следующей командной строке?
      grep main a.c b.c c.c | wc -1
      2. Рассмотрим пример программы, приведенный на Рисунке 2.7. Предположим, что в тот момент, когда при ее выполнении встретился комментарий, произошло переключение контекста и другой процесс убрал содержимое буфера из списка указателей с помощью следующих команд:
      remove(gp)
      struct queue *gp;
      {
       gp-›forp-›backp = gp-›backp;
       gp-›backp-›forp = gp-›forp;
       gp-›forp = gp-›backp = NULL;
      }
      Рассмотрим три случая:
      Процесс убирает из списка с указателями структуру bp1.
      Процесс убирает из списка с указателями структуру, следующую после структуры bp1.
      Процесс убирает из списка структуру, которая первоначально следовала за bp1 до того, как структура bp была наполовину включена в указанный список.
      В каком состоянии будет список после того, как первый процесс завершит выполнение части программы, расположенной после комментариев?
      3. Что произошло бы в том случае, если ядро попыталось бы возобновить выполнение всех процессов, приостановленных по событию, но в системе не было бы к этому моменту ни одного такого процесса?

ГЛАВА 3. БУФЕР СВЕРХОПЕРАТИВНОЙ ПАМЯТИ (КЕШ)

      Как уже говорилось в предыдущей главе, ядро операционной системы поддерживает файлы на внешних запоминающих устройствах большой емкости, таких как диски, и позволяет процессам сохранять новую информацию или вызывать ранее сохраненную информацию. Если процессу необходимо обратиться к информации файла, ядро выбирает информацию в оперативную память, где процесс сможет просматривать эту информацию, изменять ее и обращаться с просьбой о ее повторном сохранении в файловой системе. Вспомним для примера программу copy, приведенную на Рисунке 1.3: ядро читает данные из первого файла в память и затем записывает эти данные во второй файл. Подобно тому, как ядро должно заносить данные из файла в память, оно так же должно считывать в память и вспомогательные данные для работы с ними. Например, суперблок файловой системы содержит помимо всего прочего информацию о свободном пространстве, доступном файловой системе. Ядро считывает суперблок в память для того, чтобы иметь доступ к его информации, и возвращает его опять файловой системе, когда желает сохранить его содержимое. Похожая вещь происходит с индексом, который описывает размещение файла. Ядро системы считывает индекс в память, когда желает получить доступ к информации файла, и возвращает индекс вновь файловой системе, когда желает скорректировать размещение файла. Ядро обрабатывает такую вспомогательную информацию, не будучи прежде знакома с ней и не требуя для ее обработки запуска каких-либо процессов.
      Ядро могло бы производить чтение и запись непосредственно с диска и на диск при всех обращениях к файловой системе, однако время реакции системы и производительность при этом были бы низкими из-за низкой скорости передачи данных с диска. По этой причине ядро старается свести к минимуму частоту обращений к диску, заведя специальную область внутренних информационных буферов, именуемую буферным кешем и хранящую содержимое блоков диска, к которым перед этим производились обращения.
      На Рисунке 2.1 показано, что модуль буферного кеша занимает в архитектуре ядра место между подсистемой управления файлами и драйверами устройств (ввода-вывода блоками). Перед чтением информации с диска ядро пытается считать что-нибудь из буфера кеша. Если в этом буфере отсутствует информация, ядро читает данные с диска и заносит их в буфер, используя алгоритм, который имеет целью поместить в буфере как можно больше необходимых данных. Аналогично, информация, записываемая на диск, заносится в буфер для того, чтобы находиться там, если ядро позднее попытается считать ее. Ядро также старается свести к минимуму частоту выполнения операций записи на диск, выясняя, должна ли информация действительно запоминаться на диске или это промежуточные данные, которые будут вскоре затерты. Алгоритмы более высокого уровня позволяют производить предварительное занесение данных в буфер кеша или задерживать запись данных с тем, чтобы усилить эффект использования буфера. В этой главе рассматриваются алгоритмы, используемые ядром при работе с буферами в сверхоперативной памяти.

3.1 ЗАГОЛОВКИ БУФЕРА

      Во время инициализации системы ядро выделяет место под совокупность буферов, потребность в которых определяется в зависимости от размера памяти и производительности системы. Каждый буфер состоит из двух частей: области памяти, в которой хранится информация, считываемая с диска, и заголовка буфера, который идентифицирует буфер. Поскольку существует однозначное соответствие между заголовками буферов и массивами данных, в нижеследующем тексте используется термин «буфер» в ссылках как на ту, так и на другую его составляющую, и о какой из частей буфера идет речь будет понятно из контекста.
      Информация в буфере соответствует информации в одном логическом блоке диска в файловой системе, и ядро распознает содержимое буфера, просматривая идентифицирующие поля в его заголовке. Буфер представляет собой копию дискового блока в памяти; содержимое дискового блока отображается в буфер, но это отображение временное, поскольку оно имеет место до того момента, когда ядро примет решение отобразить в буфер другой дисковый блок. Один дисковый блок не может быть одновременно отображен в несколько буферов. Если бы два буфера содержали информацию для одного и того же дискового блока, ядро не смогло бы определить, в каком из буферов содержится текущая информация, и, возможно, возвратило бы на диск некорректную информацию. Предположим, например, что дисковый блок отображается в два буфера, A и B. Если ядро запишет данные сначала в буфер A, а затем в буфер B, дисковый блок будет содержать данные из буфера B, если в результате операций записи буфер заполнится до конца. Однако, если ядро изменит порядок, в котором оно копирует содержимое буферов на диск, на противоположный, дисковый блок будет содержать некорректные данные.
      Заголовок буфера (Рисунок 3.1) содержит поле «номер устройства» и поле «номер блока», которые определяют файловую систему и номер блока с информацией на диске и однозначно идентифицируют буфер. Номер устройства — это логический номер файловой системы (см. раздел 2.2.1), а не физический номер устройства (диска). Заголовок буфера также содержит указатель на область памяти для буфера, размер которой должен быть не меньше размера дискового блока, и поле состояния, в котором суммируется информация о текущем состоянии буфера. Состояние буфера представляет собой комбинацию из следующих условий:
      • буфер заблокирован (термины «заблокирован (недоступен)» и «занят» равнозначны, так же, как и понятия «свободен» и «доступен»),
      • буфер содержит правильную информацию,
      • ядро должно переписать содержимое буфера на диск перед тем, как переназначить буфер; это условие известно, как «задержка, вызванная записью»,
      • ядро читает или записывает содержимое буфера на диск,
      • процесс ждет освобождения буфера.
      В заголовке буфера также содержатся два набора указателей, используемые алгоритмами выделения буфера, которые поддерживают общую структуру области буферов (буферного пула), о чем подробнее будет говориться в следующем разделе.

       Рисунок 3.1. Заголовок буфера

3.2 СТРУКТУРА ОБЛАСТИ БУФЕРОВ (БУФЕРНОГО ПУЛА)

      Ядро помещает информацию в область буферов, используя алгоритм поиска буферов, к которым наиболее долго не было обращений: после выделения буфера дисковому блоку нельзя использовать этот буфер для другого блока до тех пор, пока не будут задействованы все остальные буферы. Ядро управляет списком свободных буферов, который необходим для работы указанного алгоритма. Этот список представляет собой циклический перечень буферов с двунаправленными указателями и с формальными заголовками в начале и в конце перечня (Рисунок 3.2). Все буферы попадают в список при загрузке системы. Если нужен любой свободный буфер, ядро выбирает буфер из «головы» списка, но если в области буферов ищется определенный блок, может быть выбран буфер и из середины списка. И в том, и в другом случае буфер удаляется из списка свободных буферов. Если ядро возвращает буфер буферному пулу, этот буфер добавляется в хвост списка, либо в «голову» списка (в случае ошибки), но никогда не в середину. По мере удаления буферов из списка буфер с нужной информацией продвигается все ближе и ближе к «голове» списка (Рисунок 3.2). Следовательно, те буферы, которые находятся ближе к «голове» списка, в последний раз использовались раньше, чем буферы, находящиеся дальше от «головы» списка.

       Рисунок 3.2. Список свободных буферов
 
      Когда ядро обращается к дисковому блоку, оно сначала ищет буфер с соответствующей комбинацией номеров устройства и блока. Вместо того, чтобы просматривать всю область буферов, ядро организует из буферов особые очереди, хешированные по номеру устройства и номеру блока. В хеш-очереди ядро устанавливает для буферов циклическую связь в виде списка с двунаправленными указателями, структура которого похожа на структуру списка свободных буферов. Количество буферов в хеш-очереди варьируется в течение всего времени функционирования системы, в чем мы еще убедимся дальше. Ядро вынуждено прибегать к функции хеширования, чтобы единообразно распределять буферы между хеш-очередями, однако функция хеширования должна быть несложной, чтобы не пострадала производительность системы. Администраторы системы задают количество хеш-очередей при генерации операционной системы.

       Рисунок 3.3. Буферы в хеш-очередях
 
      На Рисунке 3.3 изображены буферы в хеш-очередях: заголовки хеш-очередей показаны в левой части рисунка, а квадратиками в каждой строке показаны буферы в соответствующей хеш-очереди. Так, квадратики с числами 28, 4 и 64 представляют буферы в хеш-очереди для «блока 0 модуля 4». Пунктирным линиям между буферами соответствуют указатели вперед и назад вдоль хеш-очереди; для простоты на следующих рисунках этой главы данные указатели не показываются, но их присутствие подразумевается. Кроме того, на рисунке блоки идентифицируются только своими номерами и функция хеширования построена на использовании только номеров блоков; однако на практике также используется номер устройства.
      Любой буфер всегда находится в хеш-очереди, но его положение в очереди не имеет значения. Как уже говорилось, никакая пара буферов не может одновременно содержать данные одного и того же дискового блока; поэтому каждый дисковый блок в буферном пуле существует в одной и только одной хеш-очереди и представлен в ней только один раз. Тем не менее, буфер может находиться в списке свободных буферов, если его статус «свободен». Поскольку буфер может быть одновременно в хеш-очереди и в списке свободных буферов, у ядра есть два способа его обнаружения. Ядро просматривает хеш-очередь, если ему нужно найти определенный буфер, и выбирает буфер из списка свободных буферов, если ему нужен любой свободный буфер. В следующем разделе будет показано, каким образом ядро осуществляет поиск определенных дисковых блоков в буферном кеше, а также как оно работает с буферами в хеш-очередях и в списке свободных буферов. Еще раз напомним: буфер всегда находится в хеш — очереди, а в списке свободных буферов может быть, но может и отсутствовать.

3.3 МЕХАНИЗМ ПОИСКА БУФЕРА

      Как показано на Рисунке 2.1, алгоритмы верхнего уровня, используемые ядром для подсистемы управления файлами, инициируют выполнение алгоритмов управления буферным кешем. При выборке блока алгоритмы верхнего уровня устанавливают логический номер устройства и номер блока, к которым они хотели бы получить доступ. Например, если процесс хочет считать данные из файла, ядро устанавливает, в какой файловой системе находится файл и в каком блоке файловой системы содержатся данные, о чем подробнее мы узнаем из главы 4. Собираясь считать данные из определенного дискового блока, ядро проверяет, находится ли блок в буферном пуле, и если нет, назначает для него свободный буфер. Собираясь записать данные в определенный дисковый блок, ядро проверяет, находится ли блок в буферном пуле, и если нет, назначает для этого блока свободный буфер. Для выделения буферов из пула в алгоритмах чтения и записи дисковых блоков используется операция getblk (Рисунок 3.4).
      Рассмотрим в этом разделе пять возможных механизмов использования getblk для выделения буфера под дисковый блок.
      1. Ядро обнаруживает блок в хеш-очереди, соответствующий ему буфер свободен.
      2. Ядро не может обнаружить блок в хеш-очереди, поэтому оно выделяет буфер из списка свободных буферов.
      3. Ядро не может обнаружить блок в хеш-очереди и, пытаясь выделить буфер из списка свободных буферов (как в случае 2), обнаруживает в списке буфер, который помечен как «занят на время записи». Ядро должно переписать этот буфер на диск и выделить другой буфер.
      4. Ядро не может обнаружить блок в хеш-очереди, а список свободных буферов пуст.
      5. Ядро обнаруживает блок в хеш-очереди, но его буфер в настоящий момент занят.
      Обсудим каждый случай более подробно.
      Осуществляя поиск блока в буферном пуле по комбинации номеров устройства и блока, ядро ищет хеш-очередь, которая бы содержала этот блок. Просматривая хеш-очередь, ядро придерживается списка с указателями, пока (как в первом случае) не найдет буфер с искомыми номерами устройства и блока. Ядро проверяет занятость блока и в том случае, если он свободен, помечает буфер «занятым» для того, чтобы другие процессы не смогли к нему обратиться. Затем ядро удаляет буфер из списка свободных буферов, поскольку буфер не может одновременно быть занятым и находиться в указанном списке. Если другие процессы попытаются обратиться к блоку в то время, когда его буфер занят, они приостановятся до тех пор, пока буфер не освободится. На Рисунке 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). Ядро помещает буфер в конец списка свободных буферов, если только перед этим не произошла ошибка ввода-вывода или если буфер не помечен как «старый» — момент, который будет пояснен далее; в остальных случаях буфер помещается в начало списка. Теперь буфер свободен для использования любым процессом.
      Ядро выполняет алгоритм brelse в случае, когда буфер процессу больше не нужен, а также при обработке прерывания от диска для высвобождения буферов, используемых при асинхронном вводе-выводе с диска и на диск (см.