Буфер кэша

Буфер кэша в UNIX является, по сути, кэшем диска. Дисковые операции ввода-вывода работают через этот буфер. Передача данных между буфером и пространст­вом пользовательского процесса всегда происходит с использованием DMA. Посколь­ку и буфер, и область ввода-вывода процесса размещены в основной памяти, DMA используется для осуществления копирования "память-память". В этом случае процессор не используется, но расходуются циклы шины.

Для управления буфером кэша поддерживаются три списка.

• Список свободных слотов. Список всех слотов кэша (в UNIX слот рассмат­ривается как буфер; каждый слот хранит один сектор диска), доступных для распределения.

• Список устройств. Список всех буферов, связанных в данный момент с ка­ждым диском.

• Очередь драйвера ввода-вывода. Список буферов, участвующих в операциях ввода-вывода конкретного устройства (или находящихся в состоянии ожидания операций).

Каждый буфер должен находиться либо в списке свободных слотов, либо в списке очереди драйвера ввода-вывода. Буфер, однажды назначенный устройст­ву, остается назначенным ему, даже если он попадает в свободный список, — до тех пор, пока он не будет реально востребован и назначен другому устройству. Реально эти списки представляют собой списки указателей на буфера.

При обращении к номеру физического блока определенного устройства опера­ционная система прежде всего выполняет проверку наличия этого блока в буфере кэша. Для минимизации времени поиска список устройства организован в виде хэш-таблицы с использованием методики, аналогичной методу переполнения с цепочка­ми, рассматривавшемуся в приложении к главе 8 (рис. 8.24,6). Общая организация буфера кэша показана на рис. 11.15. Хэш-таблица фиксированной длины содержит указатели на буфер кэша. Каждая ссылка на (устройство  блок ) отображается в определенную запись хэш-таблицы. Указатель в этой записи указывает на первыйбуфер в цепочке. Указатель, связанный с каждым буфером, указывает на следую­щий буфер в цепочке. Следовательно, для всех обращений вида (устройство  блок ), соответствующих одной записи хэш-таблицы, искомый блок окажется в це­почке этой записи поля хэш-таблицы, если, конечно, данный блок имеется в кэше. Таким образом, при использовании хэш-таблицы длиной N длительность поиска в кэше снижается в N раз.

Рис. ll.l5. Организация буфера кэша в UNIX

Для замещения блоков используется алгоритм LRU. После того как диско­вому блоку выделяется буфер, он не может быть использован для другого блока до тех пор, пока все остальные буфера не окажутся занятыми, причем позднее рассматриваемого. Список свободных слотов сохраняет этот порядок.

Очередь символов

Кэш способен эффективно обслуживать такие блочно-ориентированные уст­ройства, как диск и магнитная лента. Для символьно-ориентированных уст­ройств, таких, как терминалы и принтеры, требуется иная форма буферизации. Информация либо записывается в очередь символов устройством ввода-вывода и считывается процессом, либо записывается процессом и считывается устройством. В обоих случаях используется модель производителя/потребителя, изучав­шаяся нами в главе 5, "Параллельные вычисления: взаимоисключения и много­задачность". Следовательно, символы из очереди могут быть считаны только один раз: прочитанный из очереди символ уничтожается. В этом и состоит отли­чие от буфера кэша, где процедура чтения может выполняться неоднократно и, следовательно, применима модель читателей/писателей (которая также рассмат­ривалась в главе 5.