Страница:
"блок 2 модуль 4". Поэтому ядро удаляет первый буфер из списка свободных бу-
феров (блок 3), назначает его блоку 18 и помещает его в соответствующую
хеш-очередь.
Если при выполнении алгоритма getblk имеет место случай 3, ядро так же
должно выделить буфер из списка свободных буферов. Однако, оно обнаруживает,
что удаляемый из списка буфер был помечен для отложенной переписи, поэтому
прежде чем использовать буфер ядро должно переписать его содержимое на диск.
Ядро приступает к асинхронной записи на диск и пытается выделить другой бу-
фер из списка. Когда асинхронная запись заканчивается, ядро освобождает бу-
фер и помещает его в начало списка свободных буферов. Буфер сам продвинулся
от конца списка свободных буферов к началу списка. Если после асинхронной
переписи ядру бы понадобилось поместить буфер в конец списка, буфер получил
бы "зеленую улицу" по всему списку свободных буферов, результат такого пере-
мещения противоположен действию алгоритма поиска буферов, к которым наиболее
долго не было обращений. Например, если обратиться к Рисунку 3.8, ядро не
смогло обнаружить блок 18, но когда попыталось выделить первые два буфера
(по очереди) в списке свободных буферов, то оказалось, что они оба помечены
для отложенной переписи. Ядро удалило их из списка, запустило операции пере-
писи на диск в соответствующие блоки, и выделило третий буфер из списка,
блок 4. Далее ядро присвоило новые значения полям буфера "номер устройства"
и "номер блока" и включило буфер, получивший имя "блок 18", в новую хеш-оче-
редь.
47
В четвертом случае (Рисунок 3.9) ядро, работая с процессом A, не смогло
найти дисковый блок в соответствующей хеш-очереди и предприняло попытку вы-
делить из списка свободных буферов новый буфер, как в случае 2. Однако, в
списке не оказалось ни одного буфера, поэтому процесс A приостановился до
тех пор, пока другим процессом не будет выполнен алгоритм brelse, высвобож-
дающий буфер. Планируя выполнение процесса A, ядро вынуждено снова просмат-
ривать хеш-очередь в поисках блока. Оно не в состоянии немедленно выделить
буфер из списка свободных буферов, так как возможна ситуация, когда свобод-
ный буфер ожидают сразу несколько процессов и одному из них будет выделен
вновь освободившийся буфер, на который уже нацелился процесс A. Таким обра-
зом, алгоритм поиска блока снова гарантирует, что только один буфер включает
содержимое дискового блока. На Рисунке 3.10 показана конкуренция между двумя
процессами за освободившийся буфер.
Последний случай (Рисунок 3.11) наиболее сложный, поскольку он связан с
комплексом взаимоотношений между несколькими процессами. Предположим, что
ядро, работая с процессом A, ведет поиск дискового блока и выделяет буфер,
но приостанавливает выполнение процесса перед освобождением буфера. Напри-
мер, если процесс A по-
пытается считать дисковый блок и выделить буфер, как в случае 2, то он при-
остановится до момента завершения передачи данных с диска. Предположим, что
пока процесс A приостановлен, ядро активизирует второй процесс, B, который
пытается обратиться к дисковому блоку, чей буфер был только что заблокирован
процессом A. Процесс B (случай 5) обнаружит этот захваченный блок в хеш-оче-
реди. Так как использовать захваченный буфер не разрешается и, кроме того,
нельзя выделить для одного и того же дискового блока второй буфер, процесс B
помечает буфер как "запрошенный" и затем приостанавливается до того момента,
когда процесс A освободит данный буфер.
В конце концов процесс A освобождает буфер и замечает, что он запрошен.
Тогда процесс A "будит" все процессы, приостановленные по событию "буфер
становится свободным", включая и процесс B. Когда же ядро вновь запустит на
выполнение процесс B, процесс B должен будет убедиться в том, что буфер сво-
заголовки хеш-очередей
+-----------------+ +-----------------+
| | |+----+ +----+| +----+
| блок 0 модуль 4 |---- ++ 28 ++ ++ 4 ++ | 64 |
| | +----+| |+----+ +----+
+-----------------+ | +------+
| | +----+| +----+| +----+
| блок 1 модуль 4 |---- | 17 || +-+ 5 ++ ++ 97 ++
| | +----+| | +----+ +-++----+|
+-----------------+ +--|отсрочка-+ +------+
| | +----+ | +----+ |+----+
| блок 2 модуль 4 |---- | 98 |+--+ | 50 | ++ 10 ++
| | +----+| +----+ +----+|
+-----------------+ | |
| | +----+| +----+ +----+|
| блок 3 модуль 4 |----+>| 3 ++ | 35 | | 99 ||
| | | +----+ +----+ +----+|
+-----------------+ |отсрочка |
+-----------------+ | |
|заголовок списка +----+ |
| | |
|свободных буферов|<---------------------------------+
+-----------------+
(а) При поиске блока 18 в списке свободных буферов обнаружены
блоки с отсроченной записью
48
заголовки хеш-очередей
+-----------------+
| | +----+ +----+
| блок 0 модуль 4 |----+>| 28 +------------+ | 64 |
| | | +----+ | +----+
+-----------------+ | |
| | | +----+ +----+ | +----+
| блок 1 модуль 4 |----| | 17 | | 5 | +-->| 97 ++
| | | +----+ +----+ +----+|
+-----------------+ | запись +------+
| | | +----+ +----+ |+----+ +----+
| блок 2 модуль 4 |----| | 98 | | 50 | ++ 10 ++ | 18 |
| | | +----+ +----+ +----+| +----+
+-----------------+ | |
| | | +----+ +----+ +----+|
| блок 3 модуль 4 |----| | 3 | | 35 | | 99 ||
| | | +----+ +----+ +----+|
+-----------------+ | запись |
+-----------------+ | |
|заголовок списка +----+ |
| | |
|свободных буферов|<---------------------------------+
+-----------------+
(б) Перепись блоков 3 и 5, переназначение блока 4 на блок 18
Рисунок 3.8. Третий случай выделения буфера
заголовки хеш-очередей
+-----------------+
| | +----+ +----+ +----+
| блок 0 модуль 4 |---- | 28 | | 4 | | 64 |
| | +----+ +----+ +----+
+-----------------+
| | +----+ +----+ +----+
| блок 1 модуль 4 |---- | 17 | | 5 | | 97 |
| | +----+ +----+ +----+
+-----------------+
| | +----+ +----+ +----+
| блок 2 модуль 4 |---- | 98 | | 50 | | 10 |
| | +----+ +----+ +----+
+-----------------+
| | +----+ +----+ +----+
| блок 3 модуль 4 |---- | 3 | | 35 | | 99 |
| | +----+ +----+ +----+
+-----------------+
+-----------------+
|заголовок списка +---------+
| | |
|свободных буферов|<--------+
+-----------------+
Поиск блока 18, список свободных буферов пуст
Рисунок 3.9. Четвертый случай выделения буфера
боден. Возможно, что третий процесс, C, ждал освобождения этого же буфера, и
49
ядро запланировало активизацию процесса C раньше B; при этом процесс C мог
приостановиться и оставить буфер заблокированным. Следовательно, процесс B
должен проверить то, что блок действительно свободен.
Процесс B также должен убедиться в том, что в буфере содержится первона-
чально затребованный дисковый блок, поскольку процесс C мог выделить данный
буфер другому блоку, как в случае 2. При выполнении процесса B может обнару-
житься, что он ждал освобождения буфера не с тем содержимым, поэтому процес-
су B придется вновь заниматься поисками блока. Если же его настроить на ав-
томатическое выделение буфера из списка свободных буферов, он может упустить
из виду возможность того, что какой-либо другой процесс уже выделил буфер
для данного блока.
Процесс A Процесс B
+-------------------------------------------------------------
| Не может найти блок b -
| в хеш-очереди -
| -
| Список свободных буфе- -
| ров пуст -
| -
| Процесс приостановлен -
| - Не может найти блок b
| - в хеш-очереди
| -
| - Список свободных буфе-
| - ров пуст
| -
| - Процесс приостановлен
| - -
| +------------------------------------------------------+
| | Некоторый процесс освобождает буфер: операция brelse |
| +------------------------------------------------------+
| - Выбирает буфер из
| - списка свободных буферов
| -
| - Назначает этот буфер
| - блоку b
| -
v
Время
Рисунок 3.10. Состязание за свободный буфер
В конце концов, процесс B найдет этот блок, при необходимости выбрав но-
вый буфер из списка свободных буферов, как в случае 2. Пусть некоторый про-
цесс, осуществляя поиск блока 99 (Рисунок 3.11), обнаружил этот блок в
хеш-очереди, однако он оказался занятым. Процесс приостанавливается до мо-
мента освобождения блока, после чего он запускает весь алгоритм с самого на-
чала. На Рисунке 3.12 показано содержимое занятого буфера.
Алгоритм выделения буфера должен быть надежным; процессы не должны "за-
сыпать" навсегда и рано или поздно им нужно выделить буфер. Ядро гарантирует
такое положение, при котором все процессы, ожидающие выделения буфера, про-
должат свое выполнение, благодаря тому, что ядро распределяет буферы во вре-
мя обработки обращений к операционной системе и освобождает их перед возвра-
том управления процессам (***). В режиме задачи процессы непосредс-
----------------------------------------
(***) Исключением является системная операция mount, которая зах-
50
ватывает буфер до тех пор, пока не будет исполнена операция
umount. Это исключение не является существенным, поскольку
общее количество буферов намного превышает число активных
монтированных файловых систем.
заголовки хеш-очередей
+-----------------+ +-----------------+
| | |+----+ +----+| +----+
| блок 0 модуль 4 |---- ++ 28 ++ ++ 4 ++ | 64 |
| | +----+| |+----+ +----+
+-----------------+ | +------+
| | +----+| +----+| +----+
| блок 1 модуль 4 |---- | 17 || ++ 5 ++ ++ 97 ++
| | +----+| |+----+ +-++----+|
+-----------------+ +---|--------+ +------+
| | +----+ |+----+ |+----+
| блок 2 модуль 4 |---- | 98 |+---+| 50 | ++ 10 ++
| | +----+| +----+ +----+|
+-----------------+ | |
| | +----+| +----+ +----+|
| блок 3 модуль 4 |----+>| 3 ++ | 35 | | 99 ||
| | | +----+ +----+ +----+|
+-----------------+ | занят|
+-----------------+ | |
|заголовок списка +----+ |
| | |
|свободных буферов|<---------------------------------+
+-----------------+
Поиск блока 99, блок занят
Рисунок 3.11. Пятый случай выделения буфера
твенно не контролируют выделение буферов ядром системы, поэтому они не могут
намеренно "захватывать" буферы. Ядро теряет контроль над буфером только тог-
да, когда ждет завершения операции ввода-вывода между буфером и диском. Было
задумано так, что если дисковод испорчен, он не может прерывать работу цент-
рального процессора, и тогда ядро никогда не освободит буфер. Дисковод дол-
жен следить за работой аппаратных средств в таких случаях и возвращать ядру
код ошибки, сообщая о плохой работе диска. Короче говоря, ядро может гаран-
тировать, что процессы, приостановленные в ожидании буфера, в конце концов
возобновят свое выполнение.
Можно также представить себе ситуацию, когда процесс "зависает" в ожида-
нии получения доступа к буферу. В четвертом случае, например, если несколько
процессов приостанавливаются, ожидая освобождения буфера, ядро не гарантиру-
ет, что они получат доступ к буферу в той очередности, в которой они запро-
сили доступ. Процесс может приостановить и возобновить свое выполнение, ког-
да буфер станет свободным, только для того, чтобы приостановиться вновь из
-за того, что другой процесс получил управление над буфером первым. Теорети-
чески, так может продолжаться вечно, но практически такой проблемы не возни-
кает в связи с тем, что в системе обычно заложено большое количество буфе-
ров.
Теперь, когда алгоритм выделения буферов нами уже рассмотрен, будет лег-
че понять процедуру чтения и записи дисковых блоков. Чтобы считать дисковый
51
Процесс A Процесс B Процесс C
+-------------------------------------------------------------
| Буфер выделен блоку b - -
| - -
| Буфер заблокирован - -
| - -
| Начат ввод-вывод - -
| - -
| Приостановлен до - -
| завершения ввода-вывода - -
| - - -
| - Поиск блока b -
| - в хеш-очереди -
| - -
| - Буфер заблокирован, -
| - приостановка -
| - - -
| - - Приостановлен
| - - в ожидании освобождения
| - - любого буфера
| - - (случай 4)
| +---------------------------+ - -
| | Ввод-вывод закончен, | - -
| | выполнение возобновляется | - -
| +---------------------------+ - -
| brelse(): возобновляются - -
| другие процессы - -
| - - Получает буфер,
| - - первоначально
| - - назначенный
| - - блоку b
| - -
| - - Переназначение
| - - буфера блоку b'
| - Буфер не содержит -
| - блок b -
| - -
| - Поиск начинается -
| - снова -
| Время
v
Рисунок 3.12. Состязание за свободный буфер
блок (Рисунок 3.13), процесс использует алгоритм getblk для поиска блока в
буферном кеше. Если он там, ядро может возвратить его немедленно без физи-
ческого считывания блока с диска. Если блок в кеше отсутствует, ядро прика-
зывает дисководу "запланировать" запрос на чтение и приостанавливает работу,
ожидая завершения ввода-вывода. Дисковод извещает контроллер диска о том,
что он собирается считать информацию, и контроллер тогда передает информацию
в буфер. Наконец, дисковый
контроллер прерывает работу процессора, сообщая о завершении операции во-
да-вывода, и программа обработки прерываний от диска возобновляет выполнение
приостановленного процесса; теперь содержимое дискового блока находится в
буфере. Модули, запросившие информацию данного блока, получают ее; когда бу-
фер им уже не потребуется, они освободят его для того, чтобы другие процессы
52
+------------------------------------------------------------+
| алгоритм bread /* чтение блока */ |
| входная информация: номер блока в файловой системе |
| выходная информация: буфер, содержащий данные |
| { |
| получить буфер для блока (алгоритм getblk); |
| если (данные в буфере правильные) |
| возвратить буфер; |
| приступить к чтению с диска; |
| приостановиться (до завершения операции чтения); |
| возвратить (буфер); |
| } |
+------------------------------------------------------------+
Рисунок 3.13. Алгоритм чтения дискового блока
получили к нему доступ.
В главе 5 будет показано, как модули более высокого уровня (такие как
подсистема управления файлами) могут предчувствовать потребность во втором
дисковом блоке, когда процесс читает информацию из файла последовательно.
Эти модули формируют запрос на асинхронное выполнение второй операции вво-
да-вывода, надеясь на то, что информация уже будет в памяти, когда вдруг
возникнет необходимость в ней, и тем самым повышая быстродействие системы.
Для этого ядро выполняет алгоритм чтения блока с продвижением breada (Рису-
нок 3.14). Ядро проверяет, находится ли в кеше первый блок, и если его там
нет, приказывает дисководу считать этот блок. Если в буферном кеше отсутст-
вует и второй блок, ядро дает команду дисководу считать асинхронно и его.
Затем процесс приостанавливается, ожидая завершения операции ввода-вывода
над первым блоком. Когда выполнение процесса возобновляется, он возвращает
буфер первому блоку и не обращает внимание на то, когда завершится операция
ввода-вывода для второго блока. После завершения этой операции контроллер
диска прерывает работу системы; программа обработки прерываний узнает о том,
что ввод-вывод выполнялся асинхронно, и освобождает буфер (алгоритм brelse).
Если бы она не освободила буфер, буфер остался бы заблокированным и по этой
причине недоступным для всех процессов. Невозможно заранее разблокировать
буфер, так как операция ввода-вывода, связанная с буфером, активна и, следо-
вательно, содержимое буфера еще не адекватно. Позже, если процесс пожелает
считать второй блок, он обнаружит его в буферном кеше, поскольку к тому вре-
мени операция ввода-вывода закончится. Если же, в начале выполнения алгорит-
ма breada, первый блок обнаружился в буферном кеше, ядро тут же проверяет,
находится там же и второй блок, и продолжает работу по только что описанной
схеме.
Алгоритм записи содержимого буфера в дисковый блок (Рисунок 3.15) похож
на алгоритм чтения. Ядро информирует дисковод о том, что есть буфер, содер-
жимое которого должно быть выведено, и дисковод планирует операцию ввода-вы-
вода блока. Если запись производится синхронно, вызывающий процесс приоста-
навливается, ожидая ее
завершения и освобождая буфер в момент возобновления своего выполнения. Если
запись производится асинхронно, ядро запускает операцию записи на диск, но
не ждет ее завершения. Ядро освободит буфер, когда завершится ввод-вывод.
Могут возникнуть ситуации, и это будет показано в следующих двух главах,
когда ядро не записывает данные немедленно на диск. Если запись "откладыва-
ется", ядро соответствующим образом помечает буфер, освобождая его по алго-
ритму brelse, и продолжает работу без планирования ввода-вывода. Ядро запи-
сывает блок на диск перед тем, как другой процесс сможет переназначить буфер
другому блоку, как показано в алгоритме getblk (случай 3). Между тем, ядро
надеется на то, что процесс получает доступ до того, как буфер будет перепи-
53
+------------------------------------------------------------+
| алгоритм breada /* чтение блока с продвижением */ |
| входная информация: (1) в файловой системе номер блока для |
| немедленного считывания |
| (2) в файловой системе номер блока для |
| асинхронного считывания |
| выходная информация: буфер с данными, считанными немедленно|
| { |
| если (первый блок отсутствует в кеше) |
| { |
| получить буфер для первого блока (алгоритм getblk);|
| если (данные в буфере неверные) |
| приступить к чтению с диска; |
| } |
| если (второй блок отсутствует в кеше) |
| { |
| получить буфер для второго блока (алгоритм getblk);|
| если (данные в буфере верные) |
| освободить буфер (алгоритм brelse); |
| в противном случае |
| приступить к чтению с диска; |
| } |
| если (первый блок первоначально находился в кеше) |
| { |
| считать первый блок (алгоритм bread); |
| возвратить буфер; |
| } |
| приостановиться (до того момента, когда первый буфер |
| будет содержать верные данные); |
| возвратить буфер; |
| } |
+------------------------------------------------------------+
Рисунок 3.14. Алгоритм чтения блока с продвижением
сан на диск; если этот процесс впоследствии изменит содержимое буфера, ядро
произведет дополнительную операцию по сохранению изменений на диске.
Отложенная запись отличается от асинхронной записи. Выполняя асинхронную
+------------------------------------------------------------+
| алгоритм bwrite /* запись блока */ |
| входная информация: буфер |
| выходная информация: отсутствует |
| { |
| приступить к записи на диск; |
| если (ввод-вывод синхронный) |
| { |
| приостановиться (до завершения ввода-вывода); |
| освободить буфер (алгоритм brelse); |
| } |
| в противном случае если (буфер помечен для отложенной |
| записи) |
| пометить буфер для последующего размещения в |
| "голове" списка свободных буферов; |
| } |
+------------------------------------------------------------+
Рисунок 3.15. Алгоритм записи дискового блока
54
запись, ядро запускает дисковую операцию немедленно, но не дожидается ее за-
вершения. Что касается отложенной записи, ядро отдаляет момент физической
переписи на диск насколько возможно; затем по алгоритму getblk (случай 3)
оно помечает буфер
как "старый" и записывает блок на диск асинхронно. После этого контроллер
диска прерывает работу системы и освобождает буфер, используя алгоритм
brelse; буфер помещается в "голову" списка свободных буферов, поскольку он
имеет пометку "старый". Благодаря наличию двух выполняющихся асинхронно опе-
раций ввода-вывода - чтения блока с продвижением и отложенной записи - ядро
может запускать программу brelse из программы обработки прерываний. Следова-
тельно, ядро вынуждено препятствовать возникновению прерываний при выполне-
нии любой процедуры, работающей со списком свободных буферов, поскольку
brelse помещает буферы в этот список.
Использование буферного кеша имеет, с одной стороны, несколько преиму-
ществ и, с другой стороны, некоторые неудобства.
* Использование буферов позволяет внести единообразие в процедуру обраще-
ния к диску, поскольку ядру нет необходимости знать причину ввода-выво-
да. Вместо этого, ядро копирует данные в буфер и из буфера, невзирая на
то, являются ли данные частью файла, индекса или суперблока. Буферизация
ввода-вывода с диска повышает модульность разработки программ, поскольку
те составные части ядра, которые занимаются вводом-выводом на диск, име-
ют один интерфейс на все случаи. Короче говоря, упрощается проектирова-
ние системы.
* Система не накладывает никаких ограничений на выравнивание информации
пользовательскими процессами, выполняющими ввод-вывод, поскольку ядро
производит внутреннее выравнивание информации. В различных аппаратных
реализациях часто требуется выравнивать информацию для ввода-вывода с
диска определенным образом, т.е. производить к примеру двухбайтное или
четырехбайтное выравнивание данных в памяти. Без механизма буферизации
программистам пришлось бы заботиться самим о правильном выравнивании
данных. По этой причине на машинах с ограниченными возможностями в вы-
равнивании адресов возникает большое количество ошибок программирования
и, кроме того, становится проблемой перенос программ в операционную сре-
ду UNIX. Копируя информацию из пользовательских буферов в системные бу-
феры (и обратно), ядро системы устраняет необходимость в специальном вы-
равнивании пользовательских буферов, делая пользовательские программы
более простыми и мобильными.
* Благодаря использованию буферного кеша, сокращается объем дискового тра-
фика и время реакции и повышается общая производительность системы. Про-
цессы, считывающие данные из файловой системы, могут обнаружить информа-
ционные блоки в кеше и им не придется прибегать ко вводу-выводу с диска.
Ядро часто применяет "отложенную запись", чтобы избежать лишних обраще-
ний к диску, оставляя блок в буферном кеше и надеясь на попадание блока
в кеш. Очевидно, что шансы на такое попадание выше в системах с большим
количеством буферов. Тем не менее, число буферов, которые можно заложить
в системе, ограничивается объемом памяти, доступной выполняющимся про-
цессам: если под буферы задействовать слишком много памяти, то система
будет работать медленнее в связи с тем, что ей придется заниматься под-
качкой и замещением выполняющихся процессов.
* Алгоритмы буферизации помогают поддерживать целостность файловой систе-
мы, так как они сохраняют общий, первоначальный и единственный образ
дисковых блоков, содержащихся в кеше. Если два процесса одновременно по-
пытаются обратиться к одному и тому же дисковому блоку, алгоритмы буфе-
55
ризации (например, getblk) параллельный доступ преобразуют в последова-
тельный, предотвращая разрушение данных.
* Сокращение дискового трафика является важным преимуществом с точки зре-
ния обеспечения хорошей производительности или быстрой реакции системы,
однако стратегия кеширования также имеет некоторые неудобства. Так как
ядро в случае отложенной записи не переписывает данные на диск немедлен-
но, такая система уязвима для сбоев, которые оставляют дисковые данные в
некорректном виде. Хотя в последних версиях системы и сокращен ущерб,
наносимый катастрофическими сбоями, основная проблема остается: пользо-
ватель, запрашивающий выполнение операции записи, никогда не знает, в
какой момент данные завершат свой путь на диск (****).
* Использование буферного кеша требует дополнительного копирования инфор-
мации при ее считывании и записи пользовательскими процессами. Процесс,
записывающий данные, передает их ядру и ядро копирует данные на диск;
процесс, считывающий данные, получает их от ядра, которое читает данные
с диска. При передаче большого количества данных дополнительное копиро-
вание отрицательным образом отражается на производительности системы,
однако при передаче небольших объемов данных производительность повыша-
феров (блок 3), назначает его блоку 18 и помещает его в соответствующую
хеш-очередь.
Если при выполнении алгоритма getblk имеет место случай 3, ядро так же
должно выделить буфер из списка свободных буферов. Однако, оно обнаруживает,
что удаляемый из списка буфер был помечен для отложенной переписи, поэтому
прежде чем использовать буфер ядро должно переписать его содержимое на диск.
Ядро приступает к асинхронной записи на диск и пытается выделить другой бу-
фер из списка. Когда асинхронная запись заканчивается, ядро освобождает бу-
фер и помещает его в начало списка свободных буферов. Буфер сам продвинулся
от конца списка свободных буферов к началу списка. Если после асинхронной
переписи ядру бы понадобилось поместить буфер в конец списка, буфер получил
бы "зеленую улицу" по всему списку свободных буферов, результат такого пере-
мещения противоположен действию алгоритма поиска буферов, к которым наиболее
долго не было обращений. Например, если обратиться к Рисунку 3.8, ядро не
смогло обнаружить блок 18, но когда попыталось выделить первые два буфера
(по очереди) в списке свободных буферов, то оказалось, что они оба помечены
для отложенной переписи. Ядро удалило их из списка, запустило операции пере-
писи на диск в соответствующие блоки, и выделило третий буфер из списка,
блок 4. Далее ядро присвоило новые значения полям буфера "номер устройства"
и "номер блока" и включило буфер, получивший имя "блок 18", в новую хеш-оче-
редь.
47
В четвертом случае (Рисунок 3.9) ядро, работая с процессом A, не смогло
найти дисковый блок в соответствующей хеш-очереди и предприняло попытку вы-
делить из списка свободных буферов новый буфер, как в случае 2. Однако, в
списке не оказалось ни одного буфера, поэтому процесс A приостановился до
тех пор, пока другим процессом не будет выполнен алгоритм brelse, высвобож-
дающий буфер. Планируя выполнение процесса A, ядро вынуждено снова просмат-
ривать хеш-очередь в поисках блока. Оно не в состоянии немедленно выделить
буфер из списка свободных буферов, так как возможна ситуация, когда свобод-
ный буфер ожидают сразу несколько процессов и одному из них будет выделен
вновь освободившийся буфер, на который уже нацелился процесс A. Таким обра-
зом, алгоритм поиска блока снова гарантирует, что только один буфер включает
содержимое дискового блока. На Рисунке 3.10 показана конкуренция между двумя
процессами за освободившийся буфер.
Последний случай (Рисунок 3.11) наиболее сложный, поскольку он связан с
комплексом взаимоотношений между несколькими процессами. Предположим, что
ядро, работая с процессом A, ведет поиск дискового блока и выделяет буфер,
но приостанавливает выполнение процесса перед освобождением буфера. Напри-
мер, если процесс A по-
пытается считать дисковый блок и выделить буфер, как в случае 2, то он при-
остановится до момента завершения передачи данных с диска. Предположим, что
пока процесс A приостановлен, ядро активизирует второй процесс, B, который
пытается обратиться к дисковому блоку, чей буфер был только что заблокирован
процессом A. Процесс B (случай 5) обнаружит этот захваченный блок в хеш-оче-
реди. Так как использовать захваченный буфер не разрешается и, кроме того,
нельзя выделить для одного и того же дискового блока второй буфер, процесс B
помечает буфер как "запрошенный" и затем приостанавливается до того момента,
когда процесс A освободит данный буфер.
В конце концов процесс A освобождает буфер и замечает, что он запрошен.
Тогда процесс A "будит" все процессы, приостановленные по событию "буфер
становится свободным", включая и процесс B. Когда же ядро вновь запустит на
выполнение процесс B, процесс B должен будет убедиться в том, что буфер сво-
заголовки хеш-очередей
+-----------------+ +-----------------+
| | |+----+ +----+| +----+
| блок 0 модуль 4 |---- ++ 28 ++ ++ 4 ++ | 64 |
| | +----+| |+----+ +----+
+-----------------+ | +------+
| | +----+| +----+| +----+
| блок 1 модуль 4 |---- | 17 || +-+ 5 ++ ++ 97 ++
| | +----+| | +----+ +-++----+|
+-----------------+ +--|отсрочка-+ +------+
| | +----+ | +----+ |+----+
| блок 2 модуль 4 |---- | 98 |+--+ | 50 | ++ 10 ++
| | +----+| +----+ +----+|
+-----------------+ | |
| | +----+| +----+ +----+|
| блок 3 модуль 4 |----+>| 3 ++ | 35 | | 99 ||
| | | +----+ +----+ +----+|
+-----------------+ |отсрочка |
+-----------------+ | |
|заголовок списка +----+ |
| | |
|свободных буферов|<---------------------------------+
+-----------------+
(а) При поиске блока 18 в списке свободных буферов обнаружены
блоки с отсроченной записью
48
заголовки хеш-очередей
+-----------------+
| | +----+ +----+
| блок 0 модуль 4 |----+>| 28 +------------+ | 64 |
| | | +----+ | +----+
+-----------------+ | |
| | | +----+ +----+ | +----+
| блок 1 модуль 4 |----| | 17 | | 5 | +-->| 97 ++
| | | +----+ +----+ +----+|
+-----------------+ | запись +------+
| | | +----+ +----+ |+----+ +----+
| блок 2 модуль 4 |----| | 98 | | 50 | ++ 10 ++ | 18 |
| | | +----+ +----+ +----+| +----+
+-----------------+ | |
| | | +----+ +----+ +----+|
| блок 3 модуль 4 |----| | 3 | | 35 | | 99 ||
| | | +----+ +----+ +----+|
+-----------------+ | запись |
+-----------------+ | |
|заголовок списка +----+ |
| | |
|свободных буферов|<---------------------------------+
+-----------------+
(б) Перепись блоков 3 и 5, переназначение блока 4 на блок 18
Рисунок 3.8. Третий случай выделения буфера
заголовки хеш-очередей
+-----------------+
| | +----+ +----+ +----+
| блок 0 модуль 4 |---- | 28 | | 4 | | 64 |
| | +----+ +----+ +----+
+-----------------+
| | +----+ +----+ +----+
| блок 1 модуль 4 |---- | 17 | | 5 | | 97 |
| | +----+ +----+ +----+
+-----------------+
| | +----+ +----+ +----+
| блок 2 модуль 4 |---- | 98 | | 50 | | 10 |
| | +----+ +----+ +----+
+-----------------+
| | +----+ +----+ +----+
| блок 3 модуль 4 |---- | 3 | | 35 | | 99 |
| | +----+ +----+ +----+
+-----------------+
+-----------------+
|заголовок списка +---------+
| | |
|свободных буферов|<--------+
+-----------------+
Поиск блока 18, список свободных буферов пуст
Рисунок 3.9. Четвертый случай выделения буфера
боден. Возможно, что третий процесс, C, ждал освобождения этого же буфера, и
49
ядро запланировало активизацию процесса C раньше B; при этом процесс C мог
приостановиться и оставить буфер заблокированным. Следовательно, процесс B
должен проверить то, что блок действительно свободен.
Процесс B также должен убедиться в том, что в буфере содержится первона-
чально затребованный дисковый блок, поскольку процесс C мог выделить данный
буфер другому блоку, как в случае 2. При выполнении процесса B может обнару-
житься, что он ждал освобождения буфера не с тем содержимым, поэтому процес-
су B придется вновь заниматься поисками блока. Если же его настроить на ав-
томатическое выделение буфера из списка свободных буферов, он может упустить
из виду возможность того, что какой-либо другой процесс уже выделил буфер
для данного блока.
Процесс A Процесс B
+-------------------------------------------------------------
| Не может найти блок b -
| в хеш-очереди -
| -
| Список свободных буфе- -
| ров пуст -
| -
| Процесс приостановлен -
| - Не может найти блок b
| - в хеш-очереди
| -
| - Список свободных буфе-
| - ров пуст
| -
| - Процесс приостановлен
| - -
| +------------------------------------------------------+
| | Некоторый процесс освобождает буфер: операция brelse |
| +------------------------------------------------------+
| - Выбирает буфер из
| - списка свободных буферов
| -
| - Назначает этот буфер
| - блоку b
| -
v
Время
Рисунок 3.10. Состязание за свободный буфер
В конце концов, процесс B найдет этот блок, при необходимости выбрав но-
вый буфер из списка свободных буферов, как в случае 2. Пусть некоторый про-
цесс, осуществляя поиск блока 99 (Рисунок 3.11), обнаружил этот блок в
хеш-очереди, однако он оказался занятым. Процесс приостанавливается до мо-
мента освобождения блока, после чего он запускает весь алгоритм с самого на-
чала. На Рисунке 3.12 показано содержимое занятого буфера.
Алгоритм выделения буфера должен быть надежным; процессы не должны "за-
сыпать" навсегда и рано или поздно им нужно выделить буфер. Ядро гарантирует
такое положение, при котором все процессы, ожидающие выделения буфера, про-
должат свое выполнение, благодаря тому, что ядро распределяет буферы во вре-
мя обработки обращений к операционной системе и освобождает их перед возвра-
том управления процессам (***). В режиме задачи процессы непосредс-
----------------------------------------
(***) Исключением является системная операция mount, которая зах-
50
ватывает буфер до тех пор, пока не будет исполнена операция
umount. Это исключение не является существенным, поскольку
общее количество буферов намного превышает число активных
монтированных файловых систем.
заголовки хеш-очередей
+-----------------+ +-----------------+
| | |+----+ +----+| +----+
| блок 0 модуль 4 |---- ++ 28 ++ ++ 4 ++ | 64 |
| | +----+| |+----+ +----+
+-----------------+ | +------+
| | +----+| +----+| +----+
| блок 1 модуль 4 |---- | 17 || ++ 5 ++ ++ 97 ++
| | +----+| |+----+ +-++----+|
+-----------------+ +---|--------+ +------+
| | +----+ |+----+ |+----+
| блок 2 модуль 4 |---- | 98 |+---+| 50 | ++ 10 ++
| | +----+| +----+ +----+|
+-----------------+ | |
| | +----+| +----+ +----+|
| блок 3 модуль 4 |----+>| 3 ++ | 35 | | 99 ||
| | | +----+ +----+ +----+|
+-----------------+ | занят|
+-----------------+ | |
|заголовок списка +----+ |
| | |
|свободных буферов|<---------------------------------+
+-----------------+
Поиск блока 99, блок занят
Рисунок 3.11. Пятый случай выделения буфера
твенно не контролируют выделение буферов ядром системы, поэтому они не могут
намеренно "захватывать" буферы. Ядро теряет контроль над буфером только тог-
да, когда ждет завершения операции ввода-вывода между буфером и диском. Было
задумано так, что если дисковод испорчен, он не может прерывать работу цент-
рального процессора, и тогда ядро никогда не освободит буфер. Дисковод дол-
жен следить за работой аппаратных средств в таких случаях и возвращать ядру
код ошибки, сообщая о плохой работе диска. Короче говоря, ядро может гаран-
тировать, что процессы, приостановленные в ожидании буфера, в конце концов
возобновят свое выполнение.
Можно также представить себе ситуацию, когда процесс "зависает" в ожида-
нии получения доступа к буферу. В четвертом случае, например, если несколько
процессов приостанавливаются, ожидая освобождения буфера, ядро не гарантиру-
ет, что они получат доступ к буферу в той очередности, в которой они запро-
сили доступ. Процесс может приостановить и возобновить свое выполнение, ког-
да буфер станет свободным, только для того, чтобы приостановиться вновь из
-за того, что другой процесс получил управление над буфером первым. Теорети-
чески, так может продолжаться вечно, но практически такой проблемы не возни-
кает в связи с тем, что в системе обычно заложено большое количество буфе-
ров.
Теперь, когда алгоритм выделения буферов нами уже рассмотрен, будет лег-
че понять процедуру чтения и записи дисковых блоков. Чтобы считать дисковый
51
Процесс A Процесс B Процесс C
+-------------------------------------------------------------
| Буфер выделен блоку b - -
| - -
| Буфер заблокирован - -
| - -
| Начат ввод-вывод - -
| - -
| Приостановлен до - -
| завершения ввода-вывода - -
| - - -
| - Поиск блока b -
| - в хеш-очереди -
| - -
| - Буфер заблокирован, -
| - приостановка -
| - - -
| - - Приостановлен
| - - в ожидании освобождения
| - - любого буфера
| - - (случай 4)
| +---------------------------+ - -
| | Ввод-вывод закончен, | - -
| | выполнение возобновляется | - -
| +---------------------------+ - -
| brelse(): возобновляются - -
| другие процессы - -
| - - Получает буфер,
| - - первоначально
| - - назначенный
| - - блоку b
| - -
| - - Переназначение
| - - буфера блоку b'
| - Буфер не содержит -
| - блок b -
| - -
| - Поиск начинается -
| - снова -
| Время
v
Рисунок 3.12. Состязание за свободный буфер
блок (Рисунок 3.13), процесс использует алгоритм getblk для поиска блока в
буферном кеше. Если он там, ядро может возвратить его немедленно без физи-
ческого считывания блока с диска. Если блок в кеше отсутствует, ядро прика-
зывает дисководу "запланировать" запрос на чтение и приостанавливает работу,
ожидая завершения ввода-вывода. Дисковод извещает контроллер диска о том,
что он собирается считать информацию, и контроллер тогда передает информацию
в буфер. Наконец, дисковый
контроллер прерывает работу процессора, сообщая о завершении операции во-
да-вывода, и программа обработки прерываний от диска возобновляет выполнение
приостановленного процесса; теперь содержимое дискового блока находится в
буфере. Модули, запросившие информацию данного блока, получают ее; когда бу-
фер им уже не потребуется, они освободят его для того, чтобы другие процессы
52
+------------------------------------------------------------+
| алгоритм bread /* чтение блока */ |
| входная информация: номер блока в файловой системе |
| выходная информация: буфер, содержащий данные |
| { |
| получить буфер для блока (алгоритм getblk); |
| если (данные в буфере правильные) |
| возвратить буфер; |
| приступить к чтению с диска; |
| приостановиться (до завершения операции чтения); |
| возвратить (буфер); |
| } |
+------------------------------------------------------------+
Рисунок 3.13. Алгоритм чтения дискового блока
получили к нему доступ.
В главе 5 будет показано, как модули более высокого уровня (такие как
подсистема управления файлами) могут предчувствовать потребность во втором
дисковом блоке, когда процесс читает информацию из файла последовательно.
Эти модули формируют запрос на асинхронное выполнение второй операции вво-
да-вывода, надеясь на то, что информация уже будет в памяти, когда вдруг
возникнет необходимость в ней, и тем самым повышая быстродействие системы.
Для этого ядро выполняет алгоритм чтения блока с продвижением breada (Рису-
нок 3.14). Ядро проверяет, находится ли в кеше первый блок, и если его там
нет, приказывает дисководу считать этот блок. Если в буферном кеше отсутст-
вует и второй блок, ядро дает команду дисководу считать асинхронно и его.
Затем процесс приостанавливается, ожидая завершения операции ввода-вывода
над первым блоком. Когда выполнение процесса возобновляется, он возвращает
буфер первому блоку и не обращает внимание на то, когда завершится операция
ввода-вывода для второго блока. После завершения этой операции контроллер
диска прерывает работу системы; программа обработки прерываний узнает о том,
что ввод-вывод выполнялся асинхронно, и освобождает буфер (алгоритм brelse).
Если бы она не освободила буфер, буфер остался бы заблокированным и по этой
причине недоступным для всех процессов. Невозможно заранее разблокировать
буфер, так как операция ввода-вывода, связанная с буфером, активна и, следо-
вательно, содержимое буфера еще не адекватно. Позже, если процесс пожелает
считать второй блок, он обнаружит его в буферном кеше, поскольку к тому вре-
мени операция ввода-вывода закончится. Если же, в начале выполнения алгорит-
ма breada, первый блок обнаружился в буферном кеше, ядро тут же проверяет,
находится там же и второй блок, и продолжает работу по только что описанной
схеме.
Алгоритм записи содержимого буфера в дисковый блок (Рисунок 3.15) похож
на алгоритм чтения. Ядро информирует дисковод о том, что есть буфер, содер-
жимое которого должно быть выведено, и дисковод планирует операцию ввода-вы-
вода блока. Если запись производится синхронно, вызывающий процесс приоста-
навливается, ожидая ее
завершения и освобождая буфер в момент возобновления своего выполнения. Если
запись производится асинхронно, ядро запускает операцию записи на диск, но
не ждет ее завершения. Ядро освободит буфер, когда завершится ввод-вывод.
Могут возникнуть ситуации, и это будет показано в следующих двух главах,
когда ядро не записывает данные немедленно на диск. Если запись "откладыва-
ется", ядро соответствующим образом помечает буфер, освобождая его по алго-
ритму brelse, и продолжает работу без планирования ввода-вывода. Ядро запи-
сывает блок на диск перед тем, как другой процесс сможет переназначить буфер
другому блоку, как показано в алгоритме getblk (случай 3). Между тем, ядро
надеется на то, что процесс получает доступ до того, как буфер будет перепи-
53
+------------------------------------------------------------+
| алгоритм breada /* чтение блока с продвижением */ |
| входная информация: (1) в файловой системе номер блока для |
| немедленного считывания |
| (2) в файловой системе номер блока для |
| асинхронного считывания |
| выходная информация: буфер с данными, считанными немедленно|
| { |
| если (первый блок отсутствует в кеше) |
| { |
| получить буфер для первого блока (алгоритм getblk);|
| если (данные в буфере неверные) |
| приступить к чтению с диска; |
| } |
| если (второй блок отсутствует в кеше) |
| { |
| получить буфер для второго блока (алгоритм getblk);|
| если (данные в буфере верные) |
| освободить буфер (алгоритм brelse); |
| в противном случае |
| приступить к чтению с диска; |
| } |
| если (первый блок первоначально находился в кеше) |
| { |
| считать первый блок (алгоритм bread); |
| возвратить буфер; |
| } |
| приостановиться (до того момента, когда первый буфер |
| будет содержать верные данные); |
| возвратить буфер; |
| } |
+------------------------------------------------------------+
Рисунок 3.14. Алгоритм чтения блока с продвижением
сан на диск; если этот процесс впоследствии изменит содержимое буфера, ядро
произведет дополнительную операцию по сохранению изменений на диске.
Отложенная запись отличается от асинхронной записи. Выполняя асинхронную
+------------------------------------------------------------+
| алгоритм bwrite /* запись блока */ |
| входная информация: буфер |
| выходная информация: отсутствует |
| { |
| приступить к записи на диск; |
| если (ввод-вывод синхронный) |
| { |
| приостановиться (до завершения ввода-вывода); |
| освободить буфер (алгоритм brelse); |
| } |
| в противном случае если (буфер помечен для отложенной |
| записи) |
| пометить буфер для последующего размещения в |
| "голове" списка свободных буферов; |
| } |
+------------------------------------------------------------+
Рисунок 3.15. Алгоритм записи дискового блока
54
запись, ядро запускает дисковую операцию немедленно, но не дожидается ее за-
вершения. Что касается отложенной записи, ядро отдаляет момент физической
переписи на диск насколько возможно; затем по алгоритму getblk (случай 3)
оно помечает буфер
как "старый" и записывает блок на диск асинхронно. После этого контроллер
диска прерывает работу системы и освобождает буфер, используя алгоритм
brelse; буфер помещается в "голову" списка свободных буферов, поскольку он
имеет пометку "старый". Благодаря наличию двух выполняющихся асинхронно опе-
раций ввода-вывода - чтения блока с продвижением и отложенной записи - ядро
может запускать программу brelse из программы обработки прерываний. Следова-
тельно, ядро вынуждено препятствовать возникновению прерываний при выполне-
нии любой процедуры, работающей со списком свободных буферов, поскольку
brelse помещает буферы в этот список.
Использование буферного кеша имеет, с одной стороны, несколько преиму-
ществ и, с другой стороны, некоторые неудобства.
* Использование буферов позволяет внести единообразие в процедуру обраще-
ния к диску, поскольку ядру нет необходимости знать причину ввода-выво-
да. Вместо этого, ядро копирует данные в буфер и из буфера, невзирая на
то, являются ли данные частью файла, индекса или суперблока. Буферизация
ввода-вывода с диска повышает модульность разработки программ, поскольку
те составные части ядра, которые занимаются вводом-выводом на диск, име-
ют один интерфейс на все случаи. Короче говоря, упрощается проектирова-
ние системы.
* Система не накладывает никаких ограничений на выравнивание информации
пользовательскими процессами, выполняющими ввод-вывод, поскольку ядро
производит внутреннее выравнивание информации. В различных аппаратных
реализациях часто требуется выравнивать информацию для ввода-вывода с
диска определенным образом, т.е. производить к примеру двухбайтное или
четырехбайтное выравнивание данных в памяти. Без механизма буферизации
программистам пришлось бы заботиться самим о правильном выравнивании
данных. По этой причине на машинах с ограниченными возможностями в вы-
равнивании адресов возникает большое количество ошибок программирования
и, кроме того, становится проблемой перенос программ в операционную сре-
ду UNIX. Копируя информацию из пользовательских буферов в системные бу-
феры (и обратно), ядро системы устраняет необходимость в специальном вы-
равнивании пользовательских буферов, делая пользовательские программы
более простыми и мобильными.
* Благодаря использованию буферного кеша, сокращается объем дискового тра-
фика и время реакции и повышается общая производительность системы. Про-
цессы, считывающие данные из файловой системы, могут обнаружить информа-
ционные блоки в кеше и им не придется прибегать ко вводу-выводу с диска.
Ядро часто применяет "отложенную запись", чтобы избежать лишних обраще-
ний к диску, оставляя блок в буферном кеше и надеясь на попадание блока
в кеш. Очевидно, что шансы на такое попадание выше в системах с большим
количеством буферов. Тем не менее, число буферов, которые можно заложить
в системе, ограничивается объемом памяти, доступной выполняющимся про-
цессам: если под буферы задействовать слишком много памяти, то система
будет работать медленнее в связи с тем, что ей придется заниматься под-
качкой и замещением выполняющихся процессов.
* Алгоритмы буферизации помогают поддерживать целостность файловой систе-
мы, так как они сохраняют общий, первоначальный и единственный образ
дисковых блоков, содержащихся в кеше. Если два процесса одновременно по-
пытаются обратиться к одному и тому же дисковому блоку, алгоритмы буфе-
55
ризации (например, getblk) параллельный доступ преобразуют в последова-
тельный, предотвращая разрушение данных.
* Сокращение дискового трафика является важным преимуществом с точки зре-
ния обеспечения хорошей производительности или быстрой реакции системы,
однако стратегия кеширования также имеет некоторые неудобства. Так как
ядро в случае отложенной записи не переписывает данные на диск немедлен-
но, такая система уязвима для сбоев, которые оставляют дисковые данные в
некорректном виде. Хотя в последних версиях системы и сокращен ущерб,
наносимый катастрофическими сбоями, основная проблема остается: пользо-
ватель, запрашивающий выполнение операции записи, никогда не знает, в
какой момент данные завершат свой путь на диск (****).
* Использование буферного кеша требует дополнительного копирования инфор-
мации при ее считывании и записи пользовательскими процессами. Процесс,
записывающий данные, передает их ядру и ядро копирует данные на диск;
процесс, считывающий данные, получает их от ядра, которое читает данные
с диска. При передаче большого количества данных дополнительное копиро-
вание отрицательным образом отражается на производительности системы,
однако при передаче небольших объемов данных производительность повыша-