Посчитай количество промахов страниц (page faults) при политике вытеснения LRU (Least Recently Used — «дольше всех не использовалась»).
Функция LRUMisses(refs []int, capacity int) int принимает:
refs — поток обращений к страницам (номера страниц по порядку);capacity — сколько страниц помещается в кэше (число кадров).
Считаем промах, когда нужной страницы в кэше нет. Первые загрузки в пустой
кэш — тоже промахи. Если при промахе кэш уже полон, вытесняем ту страницу,
к которой дольше всего не обращались (LRU). Любое обращение к странице
(и при попадании, и при загрузке) делает её «самой свежей».
Вернуть нужно общее число промахов.
Правила и краевые случаи:
capacity >= 1 в обычном случае; но если capacity <= 0, кэшировать негде —
тогда каждое обращение это промах, верни len(refs);- пустой
refs → 0;
- если
capacity больше числа уникальных страниц, вытеснений не будет —
промахов ровно столько, сколько уникальных страниц встретилось впервые;
- повторные обращения к уже загруженной странице промахом не считаются.
LRUMisses([]int{1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5}, 3)
// → 10
LRUMisses([]int{1, 1, 1, 1}, 2)
// → 1 (первое обращение — промах, остальные попадания)
Трассировка для refs = [7,0,1,2,0,3,0,4], capacity = 3
(слева — самая «старая» страница, справа — самая свежая):
ref 7 : промах кэш=[7]
ref 0 : промах кэш=[7,0]
ref 1 : промах кэш=[7,0,1]
ref 2 : промах вытесняем 7 кэш=[0,1,2]
ref 0 : попад. кэш=[1,2,0]
ref 3 : промах вытесняем 1 кэш=[2,0,3]
ref 0 : попад. кэш=[2,3,0]
ref 4 : промах вытесняем 2 кэш=[3,0,4]
итого промахов: 6
Подробнее про вытеснение страниц — в главе «Подкачка (swapping)».