ро распределяет буферы во вре- мя обработки обращений к операционной системе и освобождает их перед возвра- том управления процессам (***). В режиме задачи процессы непосредс- ---------------------------------------- (***) Исключением является системная операция 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. Пятый случай выделения буфера твенно не контролируют выделение буферов ядром системы, поэтому они не могут намеренно "захватывать" буферы. Ядро теряет контроль над буфером только тог- да, когда ждет завершения операции ввода-вывода между буфером и диском. Было задумано так, что если дисковод испорчен, он не может прерывать работу цент- рального процессора, и тогда ядро никогда не освободит буфер. Дисковод дол- жен следить за работой аппаратных средств в таких случаях и возвращать ядру код ошибки, сообщая о плохой работе диска. Короче говоря, ядро может гаран- тировать, что процессы, приостановленные в ожидании буфера, в конце концов возобновят свое выполнение. Можно также представить себе ситуацию, когда процесс "зависает" в ожида- нии получения доступа к буферу. В четвертом случае, например, если несколько процессов приостанавливаются, ожидая освобождения буфера, ядро не гарантиру- ет, что они получат доступ к буферу в той очередности, в которой они запро- сили доступ. Процесс может приостановить и возобновить свое выполнение, ког- да буфер станет свободным, только для того, чтобы приостановиться вновь из -за того, что другой процесс получил управление над буфером первым. Теорети- чески, так может продолжаться вечно, но практически такой проблемы не возни- кает в связи с тем, что в системе обычно заложено большое количество буфе- ров. 3.4 ЧТЕНИЕ И ЗАПИСЬ ДИСКОВЫХ БЛОКОВ Теперь, когда алгоритм выделения буферов нами уже рассмотрен, будет лег- че понять процедуру чтения и записи дисковых блоков. Чтобы считать дисковый 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 помещает буферы в этот список. 3.5 ПРЕИМУЩЕСТВА И НЕУДОБСТВА БУФЕРНОГО КЕША Использование буферного кеша имеет, с одной стороны, несколько преиму- ществ и, с другой стороны, некоторые неудобства. * Использование буферов позволяет внести единообразие в процедуру обраще- ния к диску, поскольку ядру нет необходимости знать причину ввода-выво- да. Вместо этого, ядро копирует данные в буфер и из буфера, невзирая на то, являются ли данные частью файла, индекса или суперблока. Буферизация ввода-вывода с диска повышает модульность разработки программ, поскольку те составные части ядра, которые занимаются вводом-выводом на диск, име- ют один интерфейс на все случаи. Короче говоря, упрощается проектирова- ние системы. * Система не накладывает никаких ограничений на выравнивание информации пользовательскими процессами, выполняющими ввод-вывод, поскольку ядро производит внутреннее выравнивание информации. В различных аппаратных реализациях часто требуется выравнивать информацию для ввода-вывода с диска определенным образом, т.е. производить к примеру двухбайтное или четырехбайтное выравнивание данных в памяти. Без механизма буферизации программистам пришлось бы заботиться самим о правильном выравнивании данных. По этой причине на машинах с ограниченными возможностями в вы- равнивании адресов возникает большое количество ошибок программирования и, кроме того, становится проблемой перенос программ в операционную сре- ду UNIX. Копируя информацию из пользовательских буферов в системные бу- феры (и обратно), ядро системы устраняет необходимость в специальном вы- равнивании пользовательских буферов, делая пользовательские программы более простыми и мобильными. * Благодаря использованию буферного кеша, сокращается объем дискового тра- фика и время реакции и повышается общая производительность системы. Про- цессы, считывающие данные из файловой системы, могут обнаружить информа- ционные блоки в кеше и им не придется прибегать ко вводу-выводу с диска. Ядро часто применяет "отложенную запись", чтобы избежать лишних обраще- ний к диску, оставляя блок в буферном кеше и надеясь на попадание блока в кеш. Очевидно, что шансы на такое попадание выше в системах с большим количеством буферов. Тем не менее, число буферов, которые можно заложить в системе, ограничивается объемом памяти, доступной выполняющимся про- цессам: если под буферы задействовать слишком много памяти, то система будет работать медленнее в связи с тем, что ей придется заниматься под- качкой и замещением выполняющихся процессов. * Алгоритмы буферизации помогают поддерживать целостность файловой систе- мы, так как они сохраняют общий, первоначальный и единственный образ дисковых блоков, содержащихся в кеше. Если два процесса одновременно по- пытаются обратиться к одному и тому же дисковому блоку, алгоритмы буфе- 55 ризации (например, getblk) параллельный доступ преобразуют в последова- тельный, предотвращая разрушение данных. * Сокращение дискового трафика является важным преимуществом с точки зре- ния обеспечения хорошей производительности или быстрой реакции системы, однако стратегия кеширования также имеет некоторые неудобства. Так как ядро в случае отложенной записи не переписывает данные на диск немедлен- но, такая система уязвима для сбоев, которые оставляют дисковые данные в некорректном виде. Хотя в последних версиях системы и сокращен ущерб, наносимый катастрофическими сбоями, основная проблема остается: пользо- ватель, запрашивающий выполнение операции записи, никогда не знает, в какой момент данные завершат свой путь на диск (****). * Использование буферного кеша требует дополнительного копирования инфор- мации при ее считывании и записи пользовательскими процессами. Процесс, записывающий данные, передает их ядру и ядро копирует данные на диск; процесс, считывающий данные, получает их от ядра, которое читает данные с диска. При передаче большого количества данных дополнительное копиро- вание отрицательным образом отражается на производительности системы, однако при передаче небольших объемов данных производительность повыша- ется, поскольку ядро буферизует данные (используя алгоритм getblk и от- ложенную запись) до тех пор, пока это представляется эффективным с точки зрения экономии времени работы с диском. 3.6 ВЫВОДЫ В данной главе была рассмотрена структура буферного кеша и различные способы, которыми ядро размещает блоки в кеше. В алгоритмах буферизации со- четаются несколько простых идей, которые в сумме обеспечивают работу меха- низма кеширования. При работе с блоками в буферном кеше ядро использует ал- горитм замены буферов, к которым наиболее долго не было обращений, предпола- гая, что к блокам, к которым недавно было обращение, вероятно, вскоре обратятся снова. Очередность, в которой буферы появляются в списке свободных буферов, соот- ветствует очередности их предыдущего использования. Остальные алгоритмы обс- луживания буферов, типа "первым пришел - первым вышел" и замещения редко ис- пользуемых, либо являются более сложными в реализации, либо снижают процент попадания в кеш. Использование функции хеширования и хеш-очередей дает ядру возможность ускорить поиск заданных блоков, а использование двунаправленных указателей в списках облегчает исключение буферов. Ядро идентифицирует нужный ему блок по номеру логического устройства и номеру блока. Алгоритм getblk просматривает буферный кеш в поисках блока и, если буфер присутствует и свободен, блокирует буфер и возвращает его. Если буфер заблокирован, обратившийся к нему процесс приостанавливается до тех пор, пока буфер не освободится. Механизм блокирования гарантирует, что толь- ко один процесс в каждый момент времени работает с буфером. Если в кеше блок отсутствует, ядро назначает блоку свободный буфер, блокирует и возвращает его. Алгоритм bread выделяет блоку буфер и при необходимости читает туда ин- формацию. Алгоритм bwrite копирует информацию в предварительно выделенный буфер. Если при выполнении указанных алгоритмов ядро не увидит необходимости в немедленном копировании данных на диск, оно пометит буфер для "отложенной записи", чтобы избежать излишнего ввода-вывода. К сожалению, процедура отк- --------------------------------------- (****) Стандартный набор операций ввода-вывода в программах на языке Си включает операцию fflush. Эта функция занимается подкачиванием данных из буферов в пользовательском адресном пространстве в рабочую область ядра. Тем не менее пользователю не известно, когда ядро запишет дан- ные на диск. 56 ладывания записи сопровождается тем, что процесс никогда не уверен, в какой момент данные физически попадают на диск. Если ядро записывает данные на диск синхронно, оно поручает драйверу диска передать блок файловой системе и ждет прерывания, сообщающего об окончании ввода-вывода. Существует множество способов использования ядром буферного кеша. Пос- редством буферного кеша ядро обеспечивает обмен данными между прикладными программами и файловой системой, передачу дополнительной системной информа- ции, например, индексов, между алгоритмами ядра и файловой системой. Ядро также использует буферный кеш, когда читает программы в память для выполне- ния. В следующих главах будет рассмотрено множество алгоритмов, использующих процедуры, описанные в данной главе. Другие алгоритмы, которые кешируют ин- дексы и страницы памяти, также используют приемы, похожие на те, что описаны для буферного кеша. 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), тре- буется, чтобы ядро перекачивало на диск содержимое всех буферов, которые помечены для "отложенной записи" в данной файловой системе. Опишите ал- горитм, реализующий перекачку буферов. Что произойдет с очередностью расположения буферов в списке свободных буферов в результате этой опера- ции ? Как ядро может гарантировать, что ни один другой процесс не подбе- рется к буферу с пометкой "отложенная запись" и не сможет переписать его содержимое в файловую систему, пока процесс перекачки приостановлен в 57 ожидании завершения операции ввода-вывода ? 12. Определим время реакции системы как среднее время выполнения системного вызова. Определим пропускную способность системы как количество процес- сов, которые система может выполнять в данный период времени. Объясните, как буферный кеш может способствовать повышению реакции системы. Способ- ствует ли он с неизбежностью увеличению пропускной способности системы ? 58