The design of the unix operating system by Maurice J
| Вид материала | Реферат |
| 3.4 Чтение и запись дисковых блоков 3.5 Преимущества и неудобства буферного кеша Внутреннее представление |
- Лекция 10. Файловые системы Unix, 116.79kb.
- Уровни рассмотрения, 314.07kb.
- Курс по операционным системам (на примере ос windows) Основан на учебном курсе Windows, 29.21kb.
- Выполнил ученик 11 «А» класса, 443.51kb.
- Ос лекция 1 (2-й семестр – временно), 101.4kb.
- Operating System, 7686.97kb.
- Unix-подобные операционные системы, характеристики, особенности, разновидности, 40.63kb.
- 1. ms sql server. Общие сведения, 66.03kb.
- Shanti ananda maurice, 89.84kb.
- Методические материалы, 3002.45kb.
│ алгоритм getblk │
│ входная информация: номер файловой системы │
│ номер блока │
│ выходная информация: буфер, который можно использовать для│
│ блока │
│ { │
│ выполнить если (буфер не найден) │
│ { │
│ если (блок в хеш-очереди) │
│ { │
│ если (буфер занят) /* случай 5 */ │
│ { │
│ приостановиться (до освобождения буфера); │
│ продолжить; /* цикл с условием продолжения */│
│ } │
│ пометить буфер занятым; /* случай 1 */ │
│ удалить буфер из списка свободных буферов; │
│ вернуть буфер; │
│ } │
│ в противном случае /* блока нет в хеш-очереди */ │
│ { │
│ если (в списке нет свободных буферов) /*случай 4*/│
│ { │
│ приостановиться (до освобождения любого буфера);│
│ продолжить; /* цикл с условием продолжения */│
│ } │
│ удалить буфер из списка свободных буферов; │
│ если (буфер помечен для отложенной переписи) │
│ /* случай 3 */ │
│ { │
│ асинхронная перепись содержимого буфера на диск;│
│ продолжить; /* цикл с условием продолжения */│
│ } │
│ /* случай 2 -- поиск свободного буфера */ │
│ удалить буфер из старой хеш-очереди; │
│ включить буфер в новую хеш-очередь; │
│ вернуть буфер; │
│ } │
│ } │
│ } │
L-------------------------------------------------------------
Рисунок 3.4. Алгоритм выделения буфера
заголовки хеш-очередей
------------------┐ ------------------┐
│ │ │-----┐ -----┐│ -----┐
│ блок 0 модуль 4 │ L+ 28 +┐ -+ 4 +- │ 64 │
│ │ L-----│ │L----- L-----
+-----------------+ │ L------┐
│ │ -----┐│ -----┐│ -----┐
│ блок 1 модуль 4 │ │ 17 ││ -+ 5 +- -+ 97 +┐
│ │ L-----│ │L----- ---L-----│
+-----------------+ L---│--------- --------
│ │ -----┐ │-----┐ │-----┐
│ блок 2 модуль 4 │ │ 98 │-----│ 50 │ L+ 10 +┐
│ │ L-----│ L----- L-----│
+-----------------+ │ │
│ │ -----┐│ -----┐ -----┐│
│ блок 3 модуль 4 │->│ 3 +- │ 35 │ │ 99 ││
│ │ │ L----- L----- L-----│
L------------------ │ │
------------------┐ │ │
│заголовок списка +----- │
│ │ │
│свободных буферов│<----------------------------------
L------------------
(а) Поиск блока 4 в первой хеш-очереди
заголовки хеш-очередей
------------------┐ ---------------┐
│ │ -----┐│ -----┐ │-----┐
│ блок 0 модуль 4 │ -+ 28 +- │ 4 │ ││ 64 │
│ │ │L----- L----- │L-----
+-----------------+ L-----------------┐ │
│ │ -----┐ -----┐│ │-----┐
│ блок 1 модуль 4 │ │ 17 │ -+ 5 +- L+ 97 +┐
│ │ L----- │L----- L-----│
+-----------------+ │ --------
│ │ -----┐ │-----┐ │-----┐
│ блок 2 модуль 4 │ │ 98 │-----│ 50 │ L+ 10 +┐
│ │ L-----│ L----- L-----│
+-----------------+ │ │
│ │ -----┐│ -----┐ -----┐│
│ блок 3 модуль 4 │->│ 3 +- │ 35 │ │ 99 ││
│ │ │ L----- L----- L-----│
L------------------ │ │
------------------┐ │ │
│заголовок списка +----- │
│ │ │
│свободных буферов│<----------------------------------
L------------------
(б) Удаление блока 4 из списка свободных буферов
Рисунок 3.5. Поиск буфера - случай 1: буфер в хеш-очереди
-------------------------------------------------------------┐
│ алгоритм brelse │
│ входная информация: заблокированный буфер │
│ выходная информация: отсутствует │
│ { │
│ возобновить выполнение всех процессов при наступлении │
│ события, связанного с освобождением любого буфера; │
│ возобновить выполнение всех процессов при наступлении │
│ события, связанного с освобождением данного буфера; │
│ поднять приоритет прерывания процессора так, чтобы │
│ блокировать любые прерывания; │
│ если (содержимое буфера верно и буфер не старый) │
│ поставить буфер в конец списка свободных буферов │
│ в противном случае │
│ поставить буфер в начало списка свободных буферов │
│ понизить приоритет прерывания процессора с тем, чтобы │
│ вновь разрешить прерывания; │
│ разблокировать (буфер); │
│ } │
L-------------------------------------------------------------
Рисунок 3.6. Алгоритм высвобождения буфера
Перед тем, как перейти к остальным случаям, рассмотрим, что
произойдет с буфером после того, как он будет выделен блоку. Ядро
системы сможет читать данные с диска в буфер и обрабатывать их
или же переписывать данные в буфер и при желании на диск. Ядро
оставляет у буфера пометку "занят"; другие процессы не могут об-
ратиться к нему и изменить его содержимое, пока он занят, таким
образом поддерживается целостность информации в буфере. Когда яд-
ро заканчивает работу с буфером, оно освобождает буфер в соот-
ветствии с алгоритмом brelse (Рисунок 3.6). Возобновляется выпол-
нение тех процессов, которые были приостановлены из-за того, что
буфер был занят, а также те процессы, которые были приостановлены
из-за того, что список свободных буферов был пуст. Как в том, так
и в другом случае, высвобождение буфера означает, что буфер ста-
новится доступным для приостановленных процессов несмотря на то,
что первый процесс, получивший буфер, заблокировал его и запретил
тем самым получение буфера другими процессами (см. раздел
2.2.2.4). Ядро помещает буфер в конец списка свободных буферов,
если только перед этим не произошла ошибка ввода-вывода или если
буфер не помечен как "старый" - момент, который будет пояснен да-
лее; в остальных случаях буфер помещается в начало списка. Теперь
буфер свободен для использования любым процессом.
Ядро выполняет алгоритм brelse в случае, когда буфер процессу
больше не нужен, а также при обработке прерывания от диска для
высвобождения буферов, используемых при асинхронном вводе-выводе
с диска и на диск (см. раздел 3.4). Ядро повышает приоритет пре-
рывания работы процессора так, чтобы запретить возникновение лю-
бых прерываний от диска на время работы со списком свободных бу-
феров, предупреждая искажение указателей буфера в результате
вложенного выполнения алгоритма brelse. Похожие последствия могут
произойти, если программа обработки прерываний запустит алгоритм
brelse во время выполнения процессом алгоритма getblk, поэтому
ядро повышает приоритет прерывания работы процессора и в страте-
гических моментах выполнения алгоритма getblk. Более подробно эти
случаи мы разберем с помощью упражнений.
------------------┐ ------------------┐
│ │ │-----┐ -----┐│ -----┐
│ блок 0 модуль 4 │ L+ 28 +┐ -+ 4 +- │ 64 │
│ │ L-----│ │L----- L-----
+-----------------+ │ L------┐
│ │ -----┐│ -----┐│ -----┐
│ блок 1 модуль 4 │ │ 17 ││ -+ 5 +- -+ 97 +┐
│ │ L-----│ │L----- ---L-----│
+-----------------+ L---│--------- --------
│ │ -----┐ │-----┐ │-----┐
│ блок 2 модуль 4 │ │ 98 │-----│ 50 │ L+ 10 +┐
│ │ L-----│ L----- L-----│
+-----------------+ │ │
│ │ -----┐│ -----┐ -----┐│
│ блок 3 модуль 4 │->│ 3 +- │ 35 │ │ 99 ││
│ │ │ L----- L----- L-----│
L------------------ │ │
------------------┐ │ │
│заголовок списка +----- │
│ │ │
│свободных буферов│<----------------------------------
L------------------
(а) Поиск блока 18 - отсутствует в кеше
заголовки хеш-очередей
------------------┐ ------------------┐
│ │ │-----┐ -----┐│ -----┐
│ блок 0 модуль 4 │ L+ 28 +┐ -+ 4 +- │ 64 │
│ │ L-----│ │L----- L-----
+-----------------+ │ L------┐
│ │ -----┐│ -----┐│ -----┐
│ блок 1 модуль 4 │ │ 17 ││ -->│ 5 +- -+ 97 +┐
│ │ L-----│ │ L----- ---L-----│
+-----------------+ L-│----------- --------
│ │ -----┐ │ -----┐ │-----┐ -----┐
│ блок 2 модуль 4 │ │ 98 │ │ │ 50 │ L+ 10 +┐ │ 18 │
│ │ L----- │ L----- L-----│ L-----
+-----------------+ │ │
│ │ │ -----┐ -----┐│
│ блок 3 модуль 4 │ │ │ 35 │ │ 99 ││
│ │ │ L----- L-----│
L------------------ │ │
------------------┐ │ │
│заголовок списка +--------------- │
│ │ │
│свободных буферов│<----------------------------------
L------------------
(б) Удаление первого блока из списка свободных буферов, наз-
начение блока 18
Рисунок 3.7. Второй случай выделения буфера
При выполнении алгоритма getblk имеет место случай 2, когда
ядро просматривает хеш-очередь, в которой должен был бы
находиться блок, но не находит его там. Так как блок не может
быть ни в какой другой хеш-очереди, поскольку он не должен
"хешироваться" в заголовки хеш-очередей другом месте,
следовательно, его нет в буферном кеше. Поэтому ядро удаляет
первый буфер из списка свободных буферов; этот буфер был уже
выделен другому дисковому блоку и также находится в хеш-очереди.
Если буфер не помечен для отложенной переписи, ядро помечает
буфер занятым, удаляет его из хеш-очереди, где он находится,
назначает в заголовке буфера номера устройства и блока,
соответствующие данному дисковому блоку, и помещает буфер в
хеш-очередь. Ядро использует буфер, не переписав информацию,
которую буфер прежде хранил для другого дискового блока. Тот
процесс, который будет искать прежний дисковый блок, не
обнаружит его в пуле и получит для него точно таким же образом
новый буфер из списка свободных буферов. Когда ядро заканчивает
работу с буфером, оно освобождает буфер вышеописанным способом.
На Рисунке 3.7, например, ядро ищет блок 18, но не находит его в
хеш-очереди, помеченной как "блок 2 модуль 4". Поэтому ядро
удаляет первый буфер из списка свободных буферов (блок 3),
назначает его блоку 18 и помещает его в соответствующую
хеш-очередь.
Если при выполнении алгоритма getblk имеет место случай 3,
ядро так же должно выделить буфер из списка свободных буферов.
Однако, оно обнаруживает, что удаляемый из списка буфер был поме-
чен для отложенной переписи, поэтому прежде чем использовать бу-
фер ядро должно переписать его содержимое на диск. Ядро приступа-
ет к асинхронной записи на диск и пытается выделить другой буфер
из списка. Когда асинхронная запись заканчивается, ядро освобож-
дает буфер и помещает его в начало списка свободных буферов. Бу-
фер сам продвинулся от конца списка свободных буферов к началу
списка. Если после асинхронной переписи ядру бы понадобилось по-
местить буфер в конец списка, буфер получил бы "зеленую улицу" по
всему списку свободных буферов, результат такого перемещения про-
тивоположен действию алгоритма поиска буферов, к которым наиболее
долго не было обращений. Например, если обратиться к Рисунку 3.8,
ядро не смогло обнаружить блок 18, но когда попыталось выделить
первые два буфера (по очереди) в списке свободных буферов, то
оказалось, что они оба помечены для отложенной переписи. Ядро
удалило их из списка, запустило операции переписи на диск в соот-
ветствующие блоки, и выделило третий буфер из списка, блок 4. Да-
лее ядро присвоило новые значения полям буфера "номер устройс-
тва" и "номер блока" и включило буфер, получивший имя "блок 18",
в новую хеш-очередь.
В четвертом случае (Рисунок 3.9) ядро, работая с процессом A,
не смогло найти дисковый блок в соответствующей хеш-очереди и
предприняло попытку выделить из списка свободных буферов новый
буфер, как в случае 2. Однако, в списке не оказалось ни одного
буфера, поэтому процесс A приостановился до тех пор, пока другим
процессом не будет выполнен алгоритм brelse, высвобождающий бу-
фер. Планируя выполнение процесса A, ядро вынуждено снова прос-
матривать хеш-очередь в поисках блока. Оно не в состоянии немед-
ленно выделить буфер из списка свободных буферов, так как
возможна ситуация, когда свободный буфер ожидают сразу несколько
процессов и одному из них будет выделен вновь освободившийся бу-
фер, на который уже нацелился процесс A. Таким образом, алгоритм
поиска блока снова гарантирует, что только один буфер включает
содержимое дискового блока. На Рисунке 3.10 показана конкуренция
между двумя процессами за освободившийся буфер.
заголовки хеш-очередей
------------------┐ ------------------┐
│ │ │-----┐ -----┐│ -----┐
│ блок 0 модуль 4 │ L+ 28 +┐ -+ 4 +- │ 64 │
│ │ L-----│ │L----- L-----
+-----------------+ │ L------┐
│ │ -----┐│ -----┐│ -----┐
│ блок 1 модуль 4 │ │ 17 ││ --+ 5 +- -+ 97 +┐
│ │ L-----│ │ L----- ---L-----│
+-----------------+ L--│отсрочка-- --------
│ │ -----┐ │ -----┐ │-----┐
│ блок 2 модуль 4 │ │ 98 │---- │ 50 │ L+ 10 +┐
│ │ L-----│ L----- L-----│
+-----------------+ │ │
│ │ -----┐│ -----┐ -----┐│
│ блок 3 модуль 4 │->│ 3 +- │ 35 │ │ 99 ││
│ │ │ L----- L----- L-----│
L------------------ │отсрочка │
------------------┐ │ │
│заголовок списка +----- │
│ │ │
│свободных буферов│<----------------------------------
L------------------
(а) При поиске блока 18 в списке свободных буферов обнаружены
блоки с отсроченной записью
заголовки хеш-очередей
------------------┐
│ │ -----┐ -----┐
│ блок 0 модуль 4 │->│ 28 +------------┐ │ 64 │
│ │ │ L----- │ L-----
+-----------------+ │ │
│ │ │ -----┐ -----┐ │ -----┐
│ блок 1 модуль 4 ││ │ 17 │ │ 5 │ L-->│ 97 +┐
│ │ │ L----- L----- L-----│
+-----------------+ │ запись --------
│ │ │ -----┐ -----┐ │-----┐ -----┐
│ блок 2 модуль 4 ││ │ 98 │ │ 50 │ L+ 10 +┐ │ 18 │
│ │ │ L----- L----- L-----│ L-----
+-----------------+ │ │
│ │ │ -----┐ -----┐ -----┐│
│ блок 3 модуль 4 ││ │ 3 │ │ 35 │ │ 99 ││
│ │ │ L----- L----- L-----│
L------------------ │ запись │
------------------┐ │ │
│заголовок списка +----- │
│ │ │
│свободных буферов│<----------------------------------
L------------------
(б) Перепись блоков 3 и 5, переназначение блока 4 на блок 18
Рисунок 3.8. Третий случай выделения буфера
заголовки хеш-очередей
------------------┐
│ │ -----┐ -----┐ -----┐
│ блок 0 модуль 4 │ │ 28 │ │ 4 │ │ 64 │
│ │ L----- L----- L-----
+-----------------+
│ │ -----┐ -----┐ -----┐
│ блок 1 модуль 4 │ │ 17 │ │ 5 │ │ 97 │
│ │ L----- L----- L-----
+-----------------+
│ │ -----┐ -----┐ -----┐
│ блок 2 модуль 4 │ │ 98 │ │ 50 │ │ 10 │
│ │ L----- L----- L-----
+-----------------+
│ │ -----┐ -----┐ -----┐
│ блок 3 модуль 4 │ │ 3 │ │ 35 │ │ 99 │
│ │ L----- L----- L-----
L------------------
------------------┐
│заголовок списка +---------┐
│ │ │
│свободных буферов│<---------
L------------------
Поиск блока 18, список свободных буферов пуст
Рисунок 3.9. Четвертый случай выделения буфера
Последний случай (Рисунок 3.11) наиболее сложный, поскольку
он связан с комплексом взаимоотношений между несколькими процес-
сами. Предположим, что ядро, работая с процессом A, ведет поиск
дискового блока и выделяет буфер, но приостанавливает выполнение
процесса перед освобождением буфера. Например, если процесс A по-
пытается считать дисковый блок и выделить буфер, как в случае 2,
то он приостановится до момента завершения передачи данных с дис-
ка. Предположим, что пока процесс A приостановлен, ядро активизи-
рует второй процесс, B, который пытается обратиться к дисковому
блоку, чей буфер был только что заблокирован процессом A. Процесс
B (случай 5) обнаружит этот захваченный блок в хеш-очереди. Так
как использовать захваченный буфер не разрешается и, кроме того,
нельзя выделить для одного и того же дискового блока второй бу-
фер, процесс B помечает буфер как "запрошенный" и затем приоста-
навливается до того момента, когда процесс A освободит данный бу-
фер.
В конце концов процесс A освобождает буфер и замечает, что он
запрошен. Тогда процесс A "будит" все процессы, приостановленные
по событию "буфер становится свободным", включая и процесс B.
Когда же ядро вновь запустит на выполнение процесс B, процесс B
должен будет убедиться в том, что буфер свободен. Возможно, что
третий процесс, C, ждал освобождения этого же буфера, и ядро зап-
ланировало активизацию процесса C раньше B; при этом процесс C
мог приостановиться и оставить буфер заблокированным. Следова-
тельно, процесс B должен проверить то, что блок действительно
свободен.
Процесс B также должен убедиться в том, что в буфере
содержится первоначально затребованный дисковый блок, поскольку
процесс C мог выделить данный буфер другому блоку, как в случае
2. При выполнении процесса B может обнаружиться, что он ждал ос-
вобождения буфера не с тем содержимым, поэтому процессу B придет-
ся вновь заниматься поисками блока. Если же его настроить на ав-
томатическое выделение буфера из списка свободных буферов, он
может упустить из виду возможность того, что какой-либо другой
процесс уже выделил буфер для данного блока.
Процесс A Процесс B
--------------------------------------------------------------
│ Не может найти блок b
│ в хеш-очереди
│
│ Список свободных буфе-
│ ров пуст
│
│ Процесс приостановлен
│ Не может найти блок b
│ в хеш-очереди
│
│ Список свободных буфе-
│ ров пуст
│
│ Процесс приостановлен
│
│
│
│ -------------------------------------------------------┐
│ │ Некоторый процесс освобождает буфер: операция brelse │
│ L-------------------------------------------------------
│ Выбирает буфер из
│ списка свободных буферов
│
│ Назначает этот буфер
│ блоку b
│
v
Время
Рисунок 3.10. Состязание за свободный буфер
В конце концов, процесс B найдет этот блок, при необходимости
выбрав новый буфер из списка свободных буферов, как в случае 2.
Пусть некоторый процесс, осуществляя поиск блока 99 (Рисунок
3.11), обнаружил этот блок в хеш-очереди, однако он оказался за-
нятым. Процесс приостанавливается до момента освобождения блока,
после чего он запускает весь алгоритм с самого начала. На Рисунке
3.12 показано содержимое занятого буфера.
заголовки хеш-очередей
------------------┐ ------------------┐
│ │ │-----┐ -----┐│ -----┐
│ блок 0 модуль 4 │ L+ 28 +┐ -+ 4 +- │ 64 │
│ │ L-----│ │L----- L-----
+-----------------+ │ L------┐
│ │ -----┐│ -----┐│ -----┐
│ блок 1 модуль 4 │ │ 17 ││ -+ 5 +- -+ 97 +┐
│ │ L-----│ │L----- ---L-----│
+-----------------+ L---│--------- --------
│ │ -----┐ │-----┐ │-----┐
│ блок 2 модуль 4 │ │ 98 │-----│ 50 │ L+ 10 +┐
│ │ L-----│ L----- L-----│
+-----------------+ │ │
│ │ -----┐│ -----┐ -----┐│
│ блок 3 модуль 4 │->│ 3 +- │ 35 │ │ 99 ││
│ │ │ L----- L----- L-----│
L------------------ │ занят│
------------------┐ │ │
│заголовок списка +----- │
│ │ │
│свободных буферов│<----------------------------------
L------------------
Поиск блока 99, блок занят
Рисунок 3.11. Пятый случай выделения буфера
Алгоритм выделения буфера должен быть надежным; процессы не
должны "засыпать" навсегда и рано или поздно им нужно выделить
буфер. Ядро гарантирует такое положение, при котором все процес-
сы, ожидающие выделения буфера, продолжат свое выполнение, благо-
даря тому, что ядро распределяет буферы во время обработки обра-
щений к операционной системе и освобождает их перед возвратом
управления процессам (***).
(***) Исключением является системная операция mount, которая зах-
ватывает буфер до тех пор, пока не будет исполнена операция
umount. Это исключение не является существенным, поскольку
общее количество буферов намного превышает число активных
монтированных файловых систем.
В режиме задачи процессы непосредственно не контролируют
выделение буферов ядром системы, поэтому они не могут намеренно
"захватывать" буферы. Ядро теряет контроль над буфером только
тогда, когда ждет завершения операции ввода-вывода между буфером
и диском. Было задумано так, что если дисковод испорчен, он не
может прерывать работу центрального процессора, и тогда ядро
никогда не освободит буфер. Дисковод должен следить за работой
аппаратных средств в таких случаях и возвращать ядру код ошибки,
сообщая о плохой работе диска. Короче говоря, ядро может
гарантировать, что процессы, приостановленные в ожидании буфера,
в конце концов возобновят свое выполнение.
Можно также представить себе ситуацию, когда процесс "зависа-
ет" в ожидании получения доступа к буферу. В четвертом случае,
например, если несколько процессов приостанавливаются, ожидая ос-
вобождения буфера, ядро не гарантирует, что они получат доступ к
буферу в той очередности, в которой они запросили доступ. Процесс
может приостановить и возобновить свое выполнение, когда буфер
станет свободным, только для того, чтобы приостановиться вновь из
-за того, что другой процесс получил управление над буфером пер-
вым. Теоретически, так может продолжаться вечно, но практически
такой проблемы не возникает в связи с тем, что в системе обычно
заложено большое количество буферов.
Процесс A Процесс B Процесс C
--------------------------------------------------------------
│ Буфер выделен блоку b
│
│ Буфер заблокирован
│
│ Начат ввод-вывод
│
│ Приостановлен до
│ завершения ввода-вывода
│
│ Поиск блока b
│ в хеш-очереди
│
│ Буфер заблокирован,
│ приостановка
│
│ Приостановлен
│ в ожидании освобождения
│ любого буфера
│ (случай 4)
│ ----------------------------┐
│ │ Ввод-вывод закончен, │
│ │ выполнение возобновляется │
│ L----------------------------
│ brelse(): возобновляются
│ другие процессы
│ Получает буфер,
│ первоначально
│ назначенный
│ блоку b
│
│ Переназначение
│ буфера блоку b'
│ Буфер не содержит
│ блок b
│
│ Поиск начинается
│ снова
│ Время
v
Рисунок 3.12. Состязание за свободный буфер
3.4 ЧТЕНИЕ И ЗАПИСЬ ДИСКОВЫХ БЛОКОВ
Теперь, когда алгоритм выделения буферов нами уже рассмотрен,
будет легче понять процедуру чтения и записи дисковых блоков.
Чтобы считать дисковый блок (Рисунок 3.13), процесс использует
алгоритм getblk для поиска блока в буферном кеше. Если он там,
ядро может возвратить его немедленно без физического считывания
блока с диска. Если блок в кеше отсутствует, ядро приказывает
дисководу "запланировать" запрос на чтение и приостанавливает ра-
боту, ожидая завершения ввода-вывода. Дисковод извещает контрол-
лер диска о том, что он собирается считать информацию, и контрол-
лер тогда передает информацию в буфер. Наконец, дисковый
контроллер прерывает работу процессора, сообщая о завершении опе-
рации вода-вывода, и программа обработки прерываний от диска во-
зобновляет выполнение приостановленного процесса; теперь содержи-
мое дискового блока находится в буфере. Модули, запросившие
информацию данного блока, получают ее; когда буфер им уже не пот-
ребуется, они освободят его для того, чтобы другие процессы полу-
чили к нему доступ.
-------------------------------------------------------------┐
│ алгоритм bread /* чтение блока */ │
│ входная информация: номер блока в файловой системе │
│ выходная информация: буфер, содержащий данные │
│ { │
│ получить буфер для блока (алгоритм getblk); │
│ если (данные в буфере правильные) │
│ возвратить буфер; │
│ приступить к чтению с диска; │
│ приостановиться (до завершения операции чтения); │
│ возвратить (буфер); │
│ } │
L-------------------------------------------------------------
Рисунок 3.13. Алгоритм чтения дискового блока
В главе 5 будет показано, как модули более высокого уровня
(такие как подсистема управления файлами) могут предчувствовать
потребность во втором дисковом блоке, когда процесс читает инфор-
мацию из файла последовательно. Эти модули формируют запрос на
асинхронное выполнение второй операции ввода-вывода, надеясь на
то, что информация уже будет в памяти, когда вдруг возникнет не-
обходимость в ней, и тем самым повышая быстродействие системы.
Для этого ядро выполняет алгоритм чтения блока с продвижением
breada (Рисунок 3.14). Ядро проверяет, находится ли в кеше первый
блок, и если его там нет, приказывает дисководу считать этот
блок. Если в буферном кеше отсутствует и второй блок, ядро дает
команду дисководу считать асинхронно и его. Затем процесс приос-
танавливается, ожидая завершения операции ввода-вывода над первым
блоком. Когда выполнение процесса возобновляется, он возвращает
буфер первому блоку и не обращает внимание на то, когда завершит-
ся операция ввода-вывода для второго блока. После завершения этой
операции контроллер диска прерывает работу системы; программа об-
работки прерываний узнает о том, что ввод-вывод выполнялся асинх-
ронно, и освобождает буфер (алгоритм brelse). Если бы она не ос-
вободила буфер, буфер остался бы заблокированным и по этой
причине недоступным для всех процессов. Невозможно заранее разб-
локировать буфер, так как операция ввода-вывода, связанная с бу-
фером, активна и, следовательно, содержимое буфера еще не адек-
ватно. Позже, если процесс пожелает считать второй блок, он
обнаружит его в буферном кеше, поскольку к тому времени операция
ввода-вывода закончится. Если же, в начале выполнения алгоритма
breada, первый блок обнаружился в буферном кеше, ядро тут же про-
веряет, находится там же и второй блок, и продолжает работу по
только что описанной схеме.
-------------------------------------------------------------┐
│ алгоритм breada /* чтение блока с продвижением */ │
│ входная информация: (1) в файловой системе номер блока для │
│ немедленного считывания │
│ (2) в файловой системе номер блока для │
│ асинхронного считывания │
│ выходная информация: буфер с данными, считанными немедленно│
│ { │
│ если (первый блок отсутствует в кеше) │
│ { │
│ получить буфер для первого блока (алгоритм getblk);│
│ если (данные в буфере неверные) │
│ приступить к чтению с диска; │
│ } │
│ если (второй блок отсутствует в кеше) │
│ { │
│ получить буфер для второго блока (алгоритм getblk);│
│ если (данные в буфере верные) │
│ освободить буфер (алгоритм brelse); │
│ в противном случае │
│ приступить к чтению с диска; │
│ } │
│ если (первый блок первоначально находился в кеше) │
│ { │
│ считать первый блок (алгоритм bread); │
│ возвратить буфер; │
│ } │
│ приостановиться (до того момента, когда первый буфер │
│ будет содержать верные данные); │
│ возвратить буфер; │
│ } │
L-------------------------------------------------------------
Рисунок 3.14. Алгоритм чтения блока с продвижением
Алгоритм записи содержимого буфера в дисковый блок (Рисунок
3.15) похож на алгоритм чтения. Ядро информирует дисковод о том,
что есть буфер, содержимое которого должно быть выведено, и дис-
ковод планирует операцию ввода-вывода блока. Если запись произво-
дится синхронно, вызывающий процесс приостанавливается, ожидая ее
завершения и освобождая буфер в момент возобновления своего вы-
полнения. Если запись производится асинхронно, ядро запускает
операцию записи на диск, но не ждет ее завершения. Ядро освободит
буфер, когда завершится ввод-вывод.
Могут возникнуть ситуации, и это будет показано в следующих
двух главах, когда ядро не записывает данные немедленно на диск.
Если запись "откладывается", ядро соответствующим образом помеча-
ет буфер, освобождая его по алгоритму brelse, и продолжает работу
без планирования ввода-вывода. Ядро записывает блок на диск перед
тем, как другой процесс сможет переназначить буфер другому блоку,
как показано в алгоритме getblk (случай 3). Между тем, ядро наде-
ется на то, что процесс получает доступ до того, как буфер будет
переписан на диск; если этот процесс впоследствии изменит содер-
жимое буфера, ядро произведет дополнительную операцию по сохране-
нию изменений на диске.
-------------------------------------------------------------┐
│ алгоритм bwrite /* запись блока */ │
│ входная информация: буфер │
│ выходная информация: отсутствует │
│ { │
│ приступить к записи на диск; │
│ если (ввод-вывод синхронный) │
│ { │
│ приостановиться (до завершения ввода-вывода); │
│ освободить буфер (алгоритм brelse); │
│ } │
│ в противном случае если (буфер помечен для отложенной │
│ записи) │
│ пометить буфер для последующего размещения в │
│ "голове" списка свободных буферов; │
│ } │
L-------------------------------------------------------------
Рисунок 3.15. Алгоритм записи дискового блока
Отложенная запись отличается от асинхронной записи. Выполняя
асинхронную запись, ядро запускает дисковую операцию немедленно,
но не дожидается ее завершения. Что касается отложенной записи,
ядро отдаляет момент физической переписи на диск насколько воз-
можно; затем по алгоритму getblk (случай 3) оно помечает буфер
как "старый" и записывает блок на диск асинхронно. После этого
контроллер диска прерывает работу системы и освобождает буфер,
используя алгоритм brelse; буфер помещается в "голову" списка
свободных буферов, поскольку он имеет пометку "старый". Благодаря
наличию двух выполняющихся асинхронно операций ввода-вывода -
чтения блока с продвижением и отложенной записи - ядро может за-
пускать программу brelse из программы обработки прерываний. Сле-
довательно, ядро вынуждено препятствовать возникновению прерыва-
ний при выполнении любой процедуры, работающей со списком
свободных буферов, поскольку brelse помещает буферы в этот спи-
сок.
3.5 ПРЕИМУЩЕСТВА И НЕУДОБСТВА БУФЕРНОГО КЕША
Использование буферного кеша имеет, с одной стороны, несколь-
ко преимуществ и, с другой стороны, некоторые неудобства.
* Использование буферов позволяет внести единообразие в проце-
дуру обращения к диску, поскольку ядру нет необходимости
знать причину ввода-вывода. Вместо этого, ядро копирует дан-
ные в буфер и из буфера, невзирая на то, являются ли данные
частью файла, индекса или суперблока. Буферизация ввода-выво-
да с диска повышает модульность разработки программ, посколь-
ку те составные части ядра, которые занимаются вводом-выводом
на диск, имеют один интерфейс на все случаи. Короче говоря,
упрощается проектирование системы.
* Система не накладывает никаких ограничений на выравнивание
информации пользовательскими процессами, выполняющими
ввод-вывод, поскольку ядро производит внутреннее выравнивание
информации. В различных аппаратных реализациях часто требует-
ся выравнивать информацию для ввода-вывода с диска определен-
ным образом, т.е. производить к примеру двухбайтное или
четырехбайтное выравнивание данных в памяти. Без механизма
буферизации программистам пришлось бы заботиться самим о пра-
вильном выравнивании данных. По этой причине на машинах с ог-
раниченными возможностями в выравнивании адресов возникает
большое количество ошибок программирования и, кроме того,
становится проблемой перенос программ в операционную среду
UNIX. Копируя информацию из пользовательских буферов в сис-
темные буферы (и обратно), ядро системы устраняет необходи-
мость в специальном выравнивании пользовательских буферов,
делая пользовательские программы более простыми и мобильными.
* Благодаря использованию буферного кеша, сокращается объем
дискового трафика и время реакции и повышается общая произво-
дительность системы. Процессы, считывающие данные из файловой
системы, могут обнаружить информационные блоки в кеше и им не
придется прибегать ко вводу-выводу с диска. Ядро часто приме-
няет "отложенную запись", чтобы избежать лишних обращений к
диску, оставляя блок в буферном кеше и надеясь на попадание
блока в кеш. Очевидно, что шансы на такое попадание выше в
системах с большим количеством буферов. Тем не менее, число
буферов, которые можно заложить в системе, ограничивается
объемом памяти, доступной выполняющимся процессам: если под
буферы задействовать слишком много памяти, то система будет
работать медленнее в связи с тем, что ей придется заниматься
подкачкой и замещением выполняющихся процессов.
* Алгоритмы буферизации помогают поддерживать целостность фай-
ловой системы, так как они сохраняют общий, первоначальный и
единственный образ дисковых блоков, содержащихся в кеше. Если
два процесса одновременно попытаются обратиться к одному и
тому же дисковому блоку, алгоритмы буферизации (например,
getblk) параллельный доступ преобразуют в последовательный,
предотвращая разрушение данных.
* Сокращение дискового трафика является важным преимуществом с
точки зрения обеспечения хорошей производительности или быст-
рой реакции системы, однако стратегия кеширования также имеет
некоторые неудобства. Так как ядро в случае отложенной записи
не переписывает данные на диск немедленно, такая система уяз-
вима для сбоев, которые оставляют дисковые данные в некор-
ректном виде. Хотя в последних версиях системы и сокращен
ущерб, наносимый катастрофическими сбоями, основная проблема
остается: пользователь, запрашивающий выполнение операции за-
писи, никогда не знает, в какой момент данные завершат свой
путь на диск (****).
* Использование буферного кеша требует дополнительного копиро-
вания информации при ее считывании и записи пользовательскими
процессами. Процесс, записывающий данные, передает их ядру и
ядро копирует данные на диск; процесс, считывающий данные,
получает их от ядра, которое читает данные с диска. При пере-
даче большого количества данных дополнительное копирование
отрицательным образом отражается на производительности систе-
мы, однако при передаче небольших объемов данных производи-
тельность повышается, поскольку ядро буферизует данные (ис-
пользуя алгоритм getblk и отложенную запись) до тех пор, пока
это представляется эффективным с точки зрения экономии време-
ни работы с диском.
3.6 ВЫВОДЫ
В данной главе была рассмотрена структура буферного кеша и
различные способы, которыми ядро размещает блоки в кеше. В алго-
ритмах буферизации сочетаются несколько простых идей, которые в
сумме обеспечивают работу механизма кеширования. При работе с
блоками в буферном кеше ядро использует алгоритм замены буферов,
к которым наиболее долго не было обращений, предполагая, что к
---------------------------------------
(****) Стандартный набор операций ввода-вывода в программах на
языке Си включает операцию fflush. Эта функция занимается
подкачиванием данных из буферов в пользовательском адрес-
ном пространстве в рабочую область ядра. Тем не менее
пользователю не известно, когда ядро запишет данные на
диск.
блокам, к которым недавно было обращение, вероятно, вскоре обра-
тятся снова. Очередность, в которой буферы появляются в списке
свободных буферов, соответствует очередности их предыдущего ис-
пользования. Остальные алгоритмы обслуживания буферов, типа "пер-
вым пришел - первым вышел" и замещения редко используемых, либо
являются более сложными в реализации, либо снижают процент попа-
дания в кеш. Использование функции хеширования и хеш-очередей да-
ет ядру возможность ускорить поиск заданных блоков, а использова-
ние двунаправленных указателей в списках облегчает исключение бу-
феров.
Ядро идентифицирует нужный ему блок по номеру логического ус-
тройства и номеру блока. Алгоритм getblk просматривает буферный
кеш в поисках блока и, если буфер присутствует и свободен, блоки-
рует буфер и возвращает его. Если буфер заблокирован, обративший-
ся к нему процесс приостанавливается до тех пор, пока буфер не
освободится. Механизм блокирования гарантирует, что только один
процесс в каждый момент времени работает с буфером. Если в кеше
блок отсутствует, ядро назначает блоку свободный буфер, блокирует
и возвращает его. Алгоритм bread выделяет блоку буфер и при необ-
ходимости читает туда информацию. Алгоритм bwrite копирует инфор-
мацию в предварительно выделенный буфер. Если при выполнении ука-
занных алгоритмов ядро не увидит необходимости в немедленном
копировании данных на диск, оно пометит буфер для "отложенной за-
писи", чтобы избежать излишнего ввода-вывода. К сожалению, проце-
дура откладывания записи сопровождается тем, что процесс никогда
не уверен, в какой момент данные физически попадают на диск. Если
ядро записывает данные на диск синхронно, оно поручает драйверу
диска передать блок файловой системе и ждет прерывания, сообщаю-
щего об окончании ввода-вывода.
Существует множество способов использования ядром буферного
кеша. Посредством буферного кеша ядро обеспечивает обмен данными
между прикладными программами и файловой системой, передачу до-
полнительной системной информации, например, индексов, между ал-
горитмами ядра и файловой системой. Ядро также использует буфер-
ный кеш, когда читает программы в память для выполнения. В
следующих главах будет рассмотрено множество алгоритмов, исполь-
зующих процедуры, описанные в данной главе. Другие алгоритмы, ко-
торые кешируют индексы и страницы памяти, также используют прие-
мы, похожие на те, что описаны для буферного кеша.
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), требуется, чтобы ядро перекачивало на диск содер-
жимое всех буферов, которые помечены для "отложенной записи"
в данной файловой системе. Опишите алгоритм, реализующий пе-
рекачку буферов. Что произойдет с очередностью расположения
буферов в списке свободных буферов в результате этой опера-
ции ? Как ядро может гарантировать, что ни один другой про-
цесс не подберется к буферу с пометкой "отложенная запись" и
не сможет переписать его содержимое в файловую систему, пока
процесс перекачки приостановлен в ожидании завершения опера-
ции ввода-вывода ?
12. Определим время реакции системы как среднее время выполнения
системного вызова. Определим пропускную способность системы
как количество процессов, которые система может выполнять в
данный период времени. Объясните, как буферный кеш может
способствовать повышению реакции системы. Способствует ли он
с неизбежностью увеличению пропускной способности системы ?
ВНУТРЕННЕЕ ПРЕДСТАВЛЕНИЕ
ФАЙЛОВ
Как уже было замечено в главе 2, каждый файл в системе UNIX
имеет уникальный индекс. Индекс содержит информацию, необходимую
любому процессу для того, чтобы обратиться к файлу, например,
права собственности на файл, права доступа к файлу, размер файла
и расположение данных файла в файловой системе. Процессы обраща-
ются к файлам, используя четко определенный набор системных вызо-
вов и идентифицируя файл строкой символов, выступающих в качестве
составного имени файла. Каждое составное имя однозначно определя-
ет файл, благодаря чему ядро системы преобразует это имя в индекс
файла.
Эта глава посвящена описанию внутренней структуры файлов в
операционной системе UNIX, в следующей же главе рассматриваются
обращения к операционной системе, связанные с обработкой файлов.