Буферизация и кэширование
В UNIX каждый кэш-буфер может входить одновременно в два линейных списка. Один из них, называемый «списком свободных блоков», это знакомый нам LRU-список, используемый для определения блока, подлежащего вытеснению. Слово «свободный» не значит «пустой»; в данном случае это слово означает блок, не занятый в текущий момент в операции чтения/записи, выполняемой каким-нибудь процессом. Другой список называется «хеш-цепочкой» и используется для ускорения поиска нужного блока.
При записи в буфер данных, соответствующих некоторому блоку диска, номер хеш-цепочки, в которую будет помещен этот буфер, определяется как остаток от деления номера блока на N – количество хеш-цепочек. Для наглядности на рисунке принято значение N = 10. Таким образом, блоки с номерами 120, 40, 90 попадают в цепочку 0, блоки 91, 1, 71 – в цепочку 1 и т.д. Когда система ищет в кэше блок с определенным номером, она прежде всего по номеру блока определяет, в какой из хеш-цепочек этот блок должен находиться. Если блока нет в этой цепочке, то его вообще нет в кэше. Таким способом удается сократить поиск в лучшем случае в N раз (это если все цепочки окажутся одинаковой длины).
Перемещение буфера из одной хеш-цепочки в другую, как и его перемещение в конец списка свободных блоков, не требует перезаписи всего блока данных в памяти и выполняется путем изменения ссылок в заголовках блоков.
Еще одна особенность кэширования дисков в UNIX состоит в том, что при обнаружении в начале списка свободных блоков «грязных» буферов система запускает процессы их очистки, но не дожидается завершения этих процессов, а выбирает для вытеснения первый по списку чистый блок. После завершения очистки блоки возвращаются в начало списка свободных блоков, оставаясь первыми кандидатами на вытеснение.
предыдущаяследующая