Geum.ru

The design of the unix operating system by Maurice J

Вид материалаРеферат
Буфер сверхоперативной памяти (кеш)
3.1 Заголовки буфера
3.2 Структура области буферов (буферного пула)
3.3 Механизм поиска буфера
Подобный материал:
1   2   3   4   5   6   7   8   9   ...   55

В остальных частях главы детально описываются подсистемы,

изображенные на Рисунке 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. Что произошло бы в том случае, если ядро попыталось бы возоб-

новить выполнение всех процессов, приостановленных по событию,

но в системе не было бы к этому моменту ни одного такого про-

цесса ?

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


Как уже говорилось в предыдущей главе, ядро операционной сис-

темы поддерживает файлы на внешних запоминающих устройствах боль-

щой емкости, таких как диски, и позволяет процессам сохранять но-

вую информацию или вызывать ранее сохраненную информацию. Если

процессу необходимо обратиться к информации файла, ядро выбирает

информацию в оперативную память, где процесс сможет просматривать

эту информацию, изменять ее и обращаться с просьбой о ее повтор-

ном сохранении в файловой системе. Вспомним для примера программу

copy, приведенную на Рисунке 1.3: ядро читает данные из первого

файла в память и затем записывает эти данные во второй файл. По-

добно тому, как ядро должно заносить данные из файла в память,

оно так же должно считывать в память и вспомогательные данные для

работы с ними. Например, суперблок файловой системы содержит по-

мимо всего прочего информацию о свободном пространстве, доступном

файловой системе. Ядро считывает суперблок в память для того,

чтобы иметь доступ к его информации, и возвращает его опять фай-

ловой системе, когда желает сохранить его содержимое. Похожая

вещь происходит с индексом, который описывает размещение файла.

Ядро системы считывает индекс в память, когда желает получить

доступ к информации файла, и возвращает индекс вновь файловой

системе, когда желает скорректировать размещение файла. Ядро об-

рабатывает такую вспомогательную информацию, не будучи прежде

знакома с ней и не требуя для ее обработки запуска каких-либо

процессов.

Ядро могло бы производить чтение и запись непосредственно с

диска и на диск при всех обращениях к файловой системе, однако

время реакции системы и производительность при этом были бы низ-

кими из-за низкой скорости передачи данных с диска. По этой при-

чине ядро старается свести к минимуму частоту обращений к диску,

заведя специальную область внутренних информационных буферов,

именуемую буферным кешем (*) и хранящую содержимое блоков диска,

к которым перед этим производились обращения.

Буферный кеш представляет собой программную структуру,

которую не следует путать с аппаратными кешами, ускоряющими

косвенную адресацию памяти.

На Рисунке 2.1 показано, что модуль буферного кеша занимает в

архитектуре ядра место между подсистемой управления файлами и

драйверами устройств (ввода-вывода блоками). Перед чтением инфор-

мации с диска ядро пытается считать что-нибудь из буфера кеша.

Если в этом буфере отсутствует информация, ядро читает данные с

диска и заносит их в буфер, используя алгоритм, который имеет


целью поместить в буфере как можно больше необходимых данных.

Аналогично, информация, записываемая на диск, заносится в буфер

для того, чтобы находиться там, если ядро позднее попытается счи-

тать ее. Ядро также старается свести к минимуму частоту выполне-

ния операций записи на диск, выясняя, должна ли информация дейс-

твительно запоминаться на диске или это промежуточные данные,

которые будут вскоре затерты. Алгоритмы более высокого уровня

позволяют производить предварительное занесение данных в буфер

кеша или задерживать запись данных с тем, чтобы усилить эффект

использования буфера. В этой главе рассматриваются алгоритмы, ис-

пользуемые ядром при работе с буферами в сверхоперативной памяти.


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


Во время инициализации системы ядро выделяет место под

совокупность буферов, потребность в которых определяется в зави-

симости от размера памяти и производительности системы. Каждый

буфер состоит из двух частей: области памяти, в которой хранится

информация, считываемая с диска, и заголовка буфера, который

идентифицирует буфер. Поскольку существует однозначное соответс-

твие между заголовками буферов и массивами данных, в нижеследую-

щем тексте используется термин "буфер" в ссылках как на ту, так и

на другую его составляющую, и о какой из частей буфера идет речь

будет понятно из контекста.

Информация в буфере соответствует информации в одном логичес-

ком блоке диска в файловой системе, и ядро распознает содержимое

буфера, просматривая идентифицирующие поля в его заголовке. Буфер

представляет собой копию дискового блока в памяти; содержимое

дискового блока отображается в буфер, но это отображение времен-

ное, поскольку оно имеет место до того момента, когда ядро примет

решение отобразить в буфер другой дисковый блок. Один дисковый

блок не может быть одновременно отображен в несколько буферов.

Если бы два буфера содержали информацию для одного и того же дис-

кового блока, ядро не смогло бы определить, в каком из буферов

содержится текущая информация, и, возможно, возвратило бы на диск

некорректную информацию. Предположим, например, что дисковый блок

отображается в два буфера, A и B. Если ядро запишет данные снача-

ла в буфер A, а затем в буфер B, дисковый блок будет содержать

данные из буфера B, если в результате операций записи буфер за-

полнится до конца. Однако, если ядро изменит порядок, в котором

оно копирует содержимое буферов на диск, на противоположный, дис-

ковый блок будет содержать некорректные данные.


-------------------┐

│ номер устройства │

+------------------+ указатель на

│ номер блока │ область данных

+------------------+ -------------->

указатель на │ поле состояния │ │

предыдущий буфер +------------------+ │

в хеш-очереди │ ------+----

<-------------┐ +------------------+

│ │ ------+----------------->

│ +------------------+ указатель на

L---+------ │ следующий буфер

+------------------+ в хеш-очереди

│ ------+---┐

+------------------+ │

<-----------------+------ │ │

указатель на L------------------- L------------->

предыдущий буфер указатель на

в списке свободных следующий буфер

в списке свободных


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


Заголовок буфера (Рисунок 3.1) содержит поле "номер устройс-

тва" и поле "номер блока", которые определяют файловую систему и

номер блока с информацией на диске и однозначно идентифицируют

буфер. Номер устройства - это логический номер файловой системы

(см. раздел 2.2.1), а не физический номер устройства (диска). За-

головок буфера также содержит указатель на область памяти для бу-

фера, размер которой должен быть не меньше размера дискового бло-

ка, и поле состояния, в котором суммируется информация о текущем

состоянии буфера. Состояние буфера представляет собой комбинацию

из следующих условий:

* буфер заблокирован (термины "заблокирован (недоступен)" и "за-

нят" равнозначны, так же, как и понятия "свободен" и "досту-

пен"),

* буфер содержит правильную информацию,

* ядро должно переписать содержимое буфера на диск перед тем, как

переназначить буфер; это условие известно, как "задержка, выз-

ванная записью",

* ядро читает или записывает содержимое буфера на диск,

* процесс ждет освобождения буфера.

В заголовке буфера также содержатся два набора указателей,

используемые алгоритмами выделения буфера, которые поддерживают

общую структуру области буферов (буферного пула), о чем подробнее

будет говориться в следующем разделе.


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


-----------------------------------------------------------------┐

│ указатели вперед │

│ --------------------┐ --------┐ --------┐ --------┐ │

L->│ заголовок списка │--->│ буфер │--->│ буфер │>│ буфер │---

---│ свободных буферов │<---│ 1 │<---│ 2 │<│ n │<-┐

│ L-------------------- L-------- L-------- L-------- │

│ указатели назад │

L-----------------------------------------------------------------

до


после

-----------------------------------------------------------------┐

│ указатели вперед │

│ --------------------┐ --------┐ --------┐ │

L->│ заголовок списка │---------------->│ буфер │>│ буфер │---

---│ свободных буферов │<----------------│ 2 │<│ n │<-┐

│ L-------------------- L-------- L-------- │

│ указатели назад │

L-----------------------------------------------------------------


Рисунок 3.2. Список свободных буферов


Ядро помещает информацию в область буферов, используя алго-

ритм поиска буферов, к которым наиболее долго не было обращений:

после выделения буфера дисковому блоку нельзя использовать этот

буфер для другого блока до тех пор, пока не будут задействованы

все остальные буферы. Ядро управляет списком свободных буферов,

который необходим для работы указанного алгоритма. Этот список

представляет собой циклический перечень буферов с двунаправленны-

ми указателями и с формальными заголовками в начале и в конце пе-

речня (Рисунок 3.2). Все буферы попадают в список при загрузке

системы. Если нужен любой свободный буфер, ядро выбирает буфер из

"головы" списка, но если в области буферов ищется определенный

блок, может быть выбран буфер и из середины списка. И в том, и в

другом случае буфер удаляется из списка свободных буферов. Если

ядро возвращает буфер буферному пулу, этот буфер добавляется в

хвост списка, либо в "голову" списка (в случае ошибки), но никог-

да не в середину. По мере удаления буферов из списка буфер с нуж-

ной информацией продвигается все ближе и ближе к "голове" списка

(Рисунок 3.2). Следовательно, те буферы, которые находятся ближе

к "голове" списка, в последний раз использовались раньше, чем бу-

феры, находящиеся дальше от "головы" списка.

Когда ядро обращается к дисковому блоку, оно сначала ищет бу-

фер с соответствующей комбинацией номеров устройства и блока.

Вместо того, чтобы просматривать всю область буферов, ядро орга-

низует из буферов особые очереди, хешированные по номеру устройс-

тва и номеру блока. В хеш-очереди ядро устанавливает для буферов

циклическую связь в виде списка с двунаправленными указателями,

структура которого похожа на структуру списка свободных буферов.

Количество буферов в хеш-очереди варьируется в течение всего вре-

мени функционирования системы, в чем мы еще убедимся дальше. Ядро

вынуждено прибегать к функции хеширования, чтобы единообразно

распределять буферы между хеш-очередями, однако функция хеширова-

ния должна быть несложной, чтобы не пострадала производительность

системы. Администраторы системы задают количество хеш-очередей

при генерации операционной системы.


заголовки хеш-очередей

------------------┐

│ │ -----┐ -----┐ -----┐

<│ блок 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------------------


Рисунок 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 соседями в списке.


-------------------------------------------------------------┐