Операционные системы 5 (стр. 9 из 43)
А в чем заключается упомянутая выше связь между синхронными/асинхронными операциями и способами организации ввода/вывода, рассмотренными в предыдущем пункте? Ответьте сами на этот вопрос.
2.6. Буферизация и кэширование
2.6.1. Понятие буферизации
Буферизацию в самом широком смысле можно определить как такую организацию ввода/вывода, при которой данные не передаются непосредственно с устройства в заданную область памяти (или из области памяти на устройство), а предварительно направляются во вспомогательную область памяти, называемую буфером. Как правило, организуемые системой буферы невидимы для прикладного программиста, он получает данные как готовый результат. Нередко данные «по дороге» проходят через несколько буферов разного назначения.
Существует несколько причин для использования буферизации, важнейшие из которых рассмотрены ниже.
2.6.2. Сглаживание неравномерности скоростей процессов
Достаточно часто в работе ОС встречается ситуация, когда один процесс порождает данные, которые должны оперативно обрабатываться другим процессом. В качестве примера можно привести прием по сети данных, которые должны обрабатываться браузером или другой прикладной программой.
Скорость приема данных очень неравномерна: интервалы времени интенсивного поступления данных перемежаются с интервалами простоя. Обработка данных прикладной программой тоже не обязательно идет с постоянной скоростью. В результате, хотя средняя скорость обработки может быть вполне достаточной, не исключено, что в некоторые моменты обрабатывающая программа будет «захлебываться» данными. Это может привести к потере части данных, не успевших пройти обработку.
Стандартным решением в этой ситуации является использование буфера, размер которого достаточно велик, чтобы вместить все данные, ожидающие обработки. Чем больше буфер, тем меньше вероятность потери данных из-за его переполнения.
2.6.3. Распараллеливание ввода и обработки
Во многих вычислительных системах имеются аппаратные возможности совместить во времени выполнение операций ввода/вывода и обработку данных процессором. Чтобы использовать эти возможности, данные при вводе направляются в буфер. После заполнения буфера его данные пересылаются в обрабатывающую программу, а их обработка выполняется параллельно с накоплением следующей порции данных в буфере.
Еще более эффективна схема работы с двумя переключаемыми буферами. Пока в первом буфере накапливаются вводимые данные, предыдущая порция данных обрабатывается во втором буфере, без потери времени на пересылку. Затем буфера меняются ролями: в первом буфере обрабатывается следующая введенная порция данных, а второй буфер используется для ввода, и т.д.
Аналогичным образом буферизация может использоваться и при выводе данных.
В некоторых случаях оказывается выгодно выполнять ввод «с опережением», т.е. вводить те данные, которые пока не запрошены обрабатывающим процессом, но по всей вероятности скоро понадобятся.
2.6.4. Согласование размеров логической и физической записи
Логической записью называют порцию данных, указанную в операторе ввода/вывода. Размер логической записи определяется логикой работы программы или, например, логической структурой базы данных.
При фактическом выполнении чтения или записи на блочное устройство обрабатывается порция данных, называемая физической записью или блоком. Размер физической записи определяется особенностями устройства (для диска это один сектор) и никак не связан с логикой программы.
На рис. 2‑2 показана ситуация, когда логическая запись содержит 100 байт, а физическая – 512 байт.
Рис. 2‑2
Предположим, что логические записи в последовательном порядке записываются в файл на диске. Если каждый оператор вывода логической записи будет вызывать немедленную запись на диск, то выдача первых пяти логических записей потребует пять раз выполнить последовательность операций: «чтение физической записи с диска – изменение 100 байт – запись измененной записи на диск». На шестой раз получится еще хуже, поскольку придется читать – изменять – записывать не одну, а две физических записи.
Использование буфера для накопления данных до размера физической записи позволяет резко сократить количество операций записи на диск и почти полностью исключить чтение с диска.
2.6.5. Редактирование при интерактивном вводе
Несколько особняком от других форм буферизации стоит использование буфера строки при вводе с клавиатуры.
Для пользователя привычно, что в процессе ввода числовых или строковых значений он может легко откорректировать ошибки ввода: «забить» неверный символ, вернуться в любое место вводимой строки и внести там изменения и т.п. При этом прикладная программа «не видит» процесса редактирования строки, она получает всю строку целиком после нажатия, например, клавиши Enter. Чтобы обеспечить возможность редактирования вводимой строки, используется буфер строки, выделяемый либо ОС, либо библиотекой времени выполнения конкретной системы программирования. Все редактирование выполняется над символами, которые помещаются в этот буфер подпрограммами ввода с клавиатуры. После нажатия Enter происходит либо копирование символов из буфера в массив, выделенный прикладной программой, либо передача этой программе указателя на буфер.
Очень важной, специфической формой буферизации является кэширование[2]. Этот термин означает использование сравнительно небольшой по объему, но быстродействующей памяти для того, чтобы уменьшить количество обращений к более медленной памяти большого объема.
Идея кэширования основывается на так называемой гипотезе о локальности ссылок. Эта гипотеза заключается в следующем. Если в какой-то момент времени произошло обращение к определенному участку данных, то в ближайшее время можно с высокой вероятностью ожидать повторения обращений к тем же самым данным или же к соседним участкам данных. Конечно, локальность ссылок нельзя считать законом, однако практика показывает, что эта гипотеза оправдывается для подавляющего большинства программ.
В современных вычислительных системах может использоваться несколько уровней кэширования. В данном курсе не рассматривается аппаратный кэш процессора, позволяющий сократить число обращений к основной памяти за счет использования быстродействующих регистров. К работе ОС более прямое отношение имеет программное кэширование устройств произвольного доступа (дисковых накопителей). В этом случае гипотезу о локальности ссылок можно переформулировать более конкретно: если программа выполнила чтение или запись данных из некоторого блока диска, то весьма вероятно, что в скором будущем последуют еще операции чтения или записи данных из того же блока.
В роли быстродействующей памяти (кэша) здесь выступает массив буферов, размещенный в системной памяти. Каждый буфер состоит из заголовка и блока данных, соответствующего по размеру блоку (сектору) диска. Заголовок буфера содержит адрес блока диска, копия которого в данный момент содержится в буфере, и несколько флагов, характеризующих состояние буфера.
Когда система получает запрос на чтение или запись определенного блока данных диска, она прежде всего проверяет, не содержится ли в данный момент копия этого блока в одном из буферов кэша. Для этого требуется выполнить поиск по заголовкам буферов. Если блок найден в кэше, то обращение к диску выполняться не будет. Вместо этого данные читаются из буфера или, соответственно, записываются в буфер. В случае записи данных следует также в заголовке буфера отметить с помощью специального флага, что буфер стал «грязным», т.е. его содержимое не соответствует данным на диске.
Если требуемый блок диска не найден в кэше, то для него должен быть выделен буфер. Проблема в том, что общее количество буферов кэша ограничено. Чтобы отдать один из них под требуемый блок, надо «вытеснить» из кэша один из блоков, которые там хранились. При этом, если вытесняемый блок «грязный», то он должен быть «очищен», т.е. записан на диск. При вытеснении «чистого» блока никаких операций с диском выполнять не надо.
Какой из блоков, хранящихся в кэше, следует выбрать для вытеснения, чтобы сократить общее количество обращений к диску? Это крайне важный вопрос, и если он будет решаться неправильно, то вся работа системы может затормозиться из-за постоянных обращений к диску.
Имеется теоретически оптимальное решение данной задачи, которое заключается в следующем. Число обращений к диску будет минимально, если каждый раз выбирать для вытеснения тот блок данных, к которому в будущем дольше всего не будет обращений. К сожалению, воспользоваться этим правилом на практике невозможно, так как последовательность обращений к блокам диска непредсказуема. Данный теоретический результат полезен только как недостижимый идеал, с которым можно сравнивать результаты применения более реалистичных алгоритмов выбора.
Среди алгоритмов, используемых на практике, лучшим считается алгоритм LRU (LeastRecentlyUsed, в вольном переводе «давно не использовавшийся»). Он заключается в следующем: выбирать для вытеснения следует тот блок, к которому дольше всего не было обращений. Здесь как раз используется принцип локальности ссылок: раз обращений давно не было, то, вероятно, их и не будет в ближайшее время.
Как на практике реализуется выбор блока по правилу LRU? Очевидное решение – при каждом обращении к буферу записывать в его заголовке текущее время, а при выборе для вытеснения искать самую раннюю запись – слишком громоздко и медленно. Есть гораздо лучшая возможность.
Все буферы кэша связываются в линейный список. В заголовке каждого буфера хранится ссылка на следующий по порядку списка буфер (фактически хранится индекс этого буфера в массиве буферов). При каждом обращении к блоку данных для чтения или записи выполняется также перемещение соответствующего буфера в конец списка. Это не означает перемещения данных, хранящихся в буфере, изменяются только несколько ссылок в заголовках.