Определение стратегии вытеснения PseudoLRU на ветвях бинарного дерева Евгений Корныхин, ВМК / ИСП РАН
2 Кэш-память a1a1 a2a2 a3a3 d1d1 d2d2 d3d3 a1a1 a2a2 d1d1 d2d … кэш-память оперативная память a … hit a : a {a 1, a 2, …, a n } miss a : a {a 1, a 2, …, a n } anan dndn на чьё место поместить а ?
3 PseudoLRU: определение на бинарном дереве A / B C / D AB / CD A B C D v1v1 v2v2 v3v3 0 1
4 PseudoLRU: определение на бинарном дереве A / B C / D AB / CD A B C D v1v1 v2v2 v3v3 0 1 hit A: v 10 v 2 0 hit B: v 10 v 2 1 hit C: v 1 1 v 3 0 hit D: v 1 1 v 3 1 направления дуг к вытесняемому противоположны меткам вершин
5 пример....
6
7