Морис Бах - Архитектура операционной системы UNIX
• Алгоритмы буферизации помогают поддерживать целостность файловой системы, так как они сохраняют общий, первоначальный и единственный образ дисковых блоков, содержащихся в кеше. Если два процесса одновременно попытаются обратиться к одному и тому же дисковому блоку, алгоритмы буферизации (например, getblk) параллельный доступ преобразуют в последовательный, предотвращая разрушение данных.
• Сокращение дискового трафика является важным преимуществом с точки зрения обеспечения хорошей производительности или быстрой реакции системы, однако стратегия кеширования также имеет некоторые неудобства. Так как ядро в случае отложенной записи не переписывает данные на диск немедленно, такая система уязвима для сбоев, которые оставляют дисковые данные в некорректном виде. Хотя в последних версиях системы и сокращен ущерб, наносимый катастрофическими сбоями, основная проблема остается: пользователь, запрашивающий выполнение операции записи, никогда не знает, в какой момент данные завершат свой путь на диск[10].
• Использование буферного кеша требует дополнительного копирования информации при ее считывании и записи пользовательскими процессами. Процесс, записывающий данные, передает их ядру и ядро копирует данные на диск; процесс, считывающий данные, получает их от ядра, которое читает данные с диска. При передаче большого количества данных дополнительное копирование отрицательным образом отражается на производительности системы, однако при передаче небольших объемов данных производительность повышается, поскольку ядро буферизует данные (используя алгоритм getblk и отложенную запись) до тех пор, пока это представляется эффективным с точки зрения экономии времени работы с диском.
3.6 ВЫВОДЫ
В данной главе была рассмотрена структура буферного кеша и различные способы, которыми ядро размещает блоки в кеше. В алгоритмах буферизации сочетаются несколько простых идей, которые в сумме обеспечивают работу механизма кеширования. При работе с блоками в буферном кеше ядро использует алгоритм замены буферов, к которым наиболее долго не было обращений, предполагая, что к блокам, к которым недавно было обращение, вероятно, вскоре обратятся снова. Очередность, в которой буферы появляются в списке свободных буферов, соответствует очередности их предыдущего использования. Остальные алгоритмы обслуживания буферов, типа «первым пришел — первым вышел» и замещения редко используемых, либо являются более сложными в реализации, либо снижают процент попадания в кеш. Использование функции хеширования и хеш-очередей дает ядру возможность ускорить поиск заданных блоков, а использование двунаправленных указателей в списках облегчает исключение буферов.
Ядро идентифицирует нужный ему блок по номеру логического устройства и номеру блока. Алгоритм 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. Определим время реакции системы как среднее время выполнения системного вызова. Определим пропускную способность системы как количество процессов, которые система может выполнять в данный период времени. Объясните, как буферный кеш может способствовать повышению реакции системы. Способствует ли он с неизбежностью увеличению пропускной способности системы?
ГЛАВА 4. ВНУТРЕННЕЕ ПРЕДСТАВЛЕНИЕ ФАЙЛОВ
Как уже было замечено в главе 2, каждый файл в системе UNIX имеет уникальный индекс. Индекс содержит информацию, необходимую любому процессу для того, чтобы обратиться к файлу, например, права собственности на файл, права доступа к файлу, размер файла и расположение данных файла в файловой системе. Процессы обращаются к файлам, используя четко определенный набор системных вызовов и идентифицируя файл строкой символов, выступающих в качестве составного имени файла. Каждое составное имя однозначно определяет файл, благодаря чему ядро системы преобразует это имя в индекс файла.
Эта глава посвящена описанию внутренней структуры файлов в операционной системе UNIX, в следующей же главе рассматриваются обращения к операционной системе, связанные с обработкой файлов. Раздел 4.1 касается индекса и работы с ним ядра, раздел 4.2 — внутренней структуры обычных файлов и некоторых моментов, связанных с чтением и записью ядром информации файлов. В разделе 4.3 исследуется строение каталогов — структур данных, позволяющих ядру организовывать файловую систему в виде иерархии файлов, раздел 4.4 содержит алгоритм преобразования имен пользовательских файлов в индексы. В разделе 4.5 дается структура суперблока, а в разделах 4.6 и 4.7 представлены алгоритмы назначения файлам дисковых индексов и дисковых блоков. Наконец, в разделе 4.8 идет речь о других типах файлов в системе, а именно о каналах и файлах устройств.
