Страница:
ется, поскольку ядро буферизует данные (используя алгоритм getblk и от-
ложенную запись) до тех пор, пока это представляется эффективным с точки
зрения экономии времени работы с диском.
В данной главе была рассмотрена структура буферного кеша и различные
способы, которыми ядро размещает блоки в кеше. В алгоритмах буферизации со-
четаются несколько простых идей, которые в сумме обеспечивают работу меха-
низма кеширования. При работе с блоками в буферном кеше ядро использует ал-
горитм замены буферов, к которым наиболее долго не было обращений, предпола-
гая, что к
блокам, к которым недавно было обращение, вероятно, вскоре обратятся снова.
Очередность, в которой буферы появляются в списке свободных буферов, соот-
ветствует очередности их предыдущего использования. Остальные алгоритмы обс-
луживания буферов, типа "первым пришел - первым вышел" и замещения редко ис-
пользуемых, либо являются более сложными в реализации, либо снижают процент
попадания в кеш. Использование функции хеширования и хеш-очередей дает ядру
возможность ускорить поиск заданных блоков, а использование двунаправленных
указателей в списках облегчает исключение буферов.
Ядро идентифицирует нужный ему блок по номеру логического устройства и
номеру блока. Алгоритм getblk просматривает буферный кеш в поисках блока и,
если буфер присутствует и свободен, блокирует буфер и возвращает его. Если
буфер заблокирован, обратившийся к нему процесс приостанавливается до тех
пор, пока буфер не освободится. Механизм блокирования гарантирует, что толь-
ко один процесс в каждый момент времени работает с буфером. Если в кеше блок
отсутствует, ядро назначает блоку свободный буфер, блокирует и возвращает
его. Алгоритм bread выделяет блоку буфер и при необходимости читает туда ин-
формацию. Алгоритм bwrite копирует информацию в предварительно выделенный
буфер. Если при выполнении указанных алгоритмов ядро не увидит необходимости
в немедленном копировании данных на диск, оно пометит буфер для "отложенной
записи", чтобы избежать излишнего ввода-вывода. К сожалению, процедура отк-
---------------------------------------
(****) Стандартный набор операций ввода-вывода в программах на языке Си
включает операцию fflush. Эта функция занимается подкачиванием данных
из буферов в пользовательском адресном пространстве в рабочую область
ядра. Тем не менее пользователю не известно, когда ядро запишет дан-
ные на диск.
56
ладывания записи сопровождается тем, что процесс никогда не уверен, в какой
момент данные физически попадают на диск. Если ядро записывает данные на
диск синхронно, оно поручает драйверу диска передать блок файловой системе и
ждет прерывания, сообщающего об окончании ввода-вывода.
Существует множество способов использования ядром буферного кеша. Пос-
редством буферного кеша ядро обеспечивает обмен данными между прикладными
программами и файловой системой, передачу дополнительной системной информа-
ции, например, индексов, между алгоритмами ядра и файловой системой. Ядро
также использует буферный кеш, когда читает программы в память для выполне-
ния. В следующих главах будет рассмотрено множество алгоритмов, использующих
процедуры, описанные в данной главе. Другие алгоритмы, которые кешируют ин-
дексы и страницы памяти, также используют приемы, похожие на те, что описаны
для буферного кеша.
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), тре-
буется, чтобы ядро перекачивало на диск содержимое всех буферов, которые
помечены для "отложенной записи" в данной файловой системе. Опишите ал-
горитм, реализующий перекачку буферов. Что произойдет с очередностью
расположения буферов в списке свободных буферов в результате этой опера-
ции ? Как ядро может гарантировать, что ни один другой процесс не подбе-
рется к буферу с пометкой "отложенная запись" и не сможет переписать его
содержимое в файловую систему, пока процесс перекачки приостановлен в
57
ожидании завершения операции ввода-вывода ?
12. Определим время реакции системы как среднее время выполнения системного
вызова. Определим пропускную способность системы как количество процес-
сов, которые система может выполнять в данный период времени. Объясните,
как буферный кеш может способствовать повышению реакции системы. Способ-
ствует ли он с неизбежностью увеличению пропускной способности системы ?
58
ложенную запись) до тех пор, пока это представляется эффективным с точки
зрения экономии времени работы с диском.
В данной главе была рассмотрена структура буферного кеша и различные
способы, которыми ядро размещает блоки в кеше. В алгоритмах буферизации со-
четаются несколько простых идей, которые в сумме обеспечивают работу меха-
низма кеширования. При работе с блоками в буферном кеше ядро использует ал-
горитм замены буферов, к которым наиболее долго не было обращений, предпола-
гая, что к
блокам, к которым недавно было обращение, вероятно, вскоре обратятся снова.
Очередность, в которой буферы появляются в списке свободных буферов, соот-
ветствует очередности их предыдущего использования. Остальные алгоритмы обс-
луживания буферов, типа "первым пришел - первым вышел" и замещения редко ис-
пользуемых, либо являются более сложными в реализации, либо снижают процент
попадания в кеш. Использование функции хеширования и хеш-очередей дает ядру
возможность ускорить поиск заданных блоков, а использование двунаправленных
указателей в списках облегчает исключение буферов.
Ядро идентифицирует нужный ему блок по номеру логического устройства и
номеру блока. Алгоритм getblk просматривает буферный кеш в поисках блока и,
если буфер присутствует и свободен, блокирует буфер и возвращает его. Если
буфер заблокирован, обратившийся к нему процесс приостанавливается до тех
пор, пока буфер не освободится. Механизм блокирования гарантирует, что толь-
ко один процесс в каждый момент времени работает с буфером. Если в кеше блок
отсутствует, ядро назначает блоку свободный буфер, блокирует и возвращает
его. Алгоритм bread выделяет блоку буфер и при необходимости читает туда ин-
формацию. Алгоритм bwrite копирует информацию в предварительно выделенный
буфер. Если при выполнении указанных алгоритмов ядро не увидит необходимости
в немедленном копировании данных на диск, оно пометит буфер для "отложенной
записи", чтобы избежать излишнего ввода-вывода. К сожалению, процедура отк-
---------------------------------------
(****) Стандартный набор операций ввода-вывода в программах на языке Си
включает операцию fflush. Эта функция занимается подкачиванием данных
из буферов в пользовательском адресном пространстве в рабочую область
ядра. Тем не менее пользователю не известно, когда ядро запишет дан-
ные на диск.
56
ладывания записи сопровождается тем, что процесс никогда не уверен, в какой
момент данные физически попадают на диск. Если ядро записывает данные на
диск синхронно, оно поручает драйверу диска передать блок файловой системе и
ждет прерывания, сообщающего об окончании ввода-вывода.
Существует множество способов использования ядром буферного кеша. Пос-
редством буферного кеша ядро обеспечивает обмен данными между прикладными
программами и файловой системой, передачу дополнительной системной информа-
ции, например, индексов, между алгоритмами ядра и файловой системой. Ядро
также использует буферный кеш, когда читает программы в память для выполне-
ния. В следующих главах будет рассмотрено множество алгоритмов, использующих
процедуры, описанные в данной главе. Другие алгоритмы, которые кешируют ин-
дексы и страницы памяти, также используют приемы, похожие на те, что описаны
для буферного кеша.
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), тре-
буется, чтобы ядро перекачивало на диск содержимое всех буферов, которые
помечены для "отложенной записи" в данной файловой системе. Опишите ал-
горитм, реализующий перекачку буферов. Что произойдет с очередностью
расположения буферов в списке свободных буферов в результате этой опера-
ции ? Как ядро может гарантировать, что ни один другой процесс не подбе-
рется к буферу с пометкой "отложенная запись" и не сможет переписать его
содержимое в файловую систему, пока процесс перекачки приостановлен в
57
ожидании завершения операции ввода-вывода ?
12. Определим время реакции системы как среднее время выполнения системного
вызова. Определим пропускную способность системы как количество процес-
сов, которые система может выполнять в данный период времени. Объясните,
как буферный кеш может способствовать повышению реакции системы. Способ-
ствует ли он с неизбежностью увеличению пропускной способности системы ?
58