#algorithm #policy
Вопрос:
Мне интересно, правильно ли я ответил на этот вопрос:
Ссылки на страницы расположены в следующей последовательности: *ABCBADACEBEFBEFBA При замене страницы LFU, сколько ошибок на страницах возникнет?
| слот | A | B | C | B | A | D | A | C | E | B | E | F | B | E | F | B | A |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | A | x | x | x | |||||||||||||
| 2 | B | x | x | x | x | ||||||||||||
| 3 | C | D | C | E | x | F | E | F |
Судя по отслеживанию, которое я сделал. Я пришел к выводу, что существует 9 ошибок на страницах. Я подсчитываю частоту каждого использования страницы и сбрасываю ее до 0 всякий раз, когда они удаляются из своего слота (заменяются). Это правильный способ сделать это?
| слот | A | B | C | B | A | D | A | C | E | B | E | F | B | E | F | B | A |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | A | x | x | x | |||||||||||||
| 2 | B | x | C | B | F | B | F | B | |||||||||
| 3 | C | D | E | x | x |
Решение, которое мне дали, похоже на то, что дает нам 11 ошибок на страницах. Однако я не могу понять, почему второй C будет заменен на слоте 2, когда частота B равна 2, а частота D в слоте 3 равна только 1.
Ответ №1:
Вам следует вернуться к определению LFU, которое вам дали в классе. Похоже, что вы интерпретируете это как
удалите запись с наименьшим количеством обращений с момента ее заполнения.
в этом случае ваш ответ (первая таблица) действительно правильный.
Однако, похоже, что политика LFU, используемая в ожидаемом ответе (вторая таблица), является
выселите запись с наименьшим коэффициентом
freq(X) = number of hits / its age.
В таком случае на 2-м С у вас есть
freq(A) = 3/7 = 0.429 freq(B) = 2/6 = 0.333 freq(D) = 1/2 = 0.500 и запись с наименьшей частотой действительно является B.
Я бы ожидал, что LFU реализует 2-ю стратегию, потому что, как только у вас в кэше появятся записи разного возраста, вам придется учитывать, что у них меньше или больше времени для накопления статистики. Ваш подход даст правильные частоты только в пределе, если записи никогда не будут удалены, что практически не представляет интереса.
Комментарии:
1. В этом есть большой смысл. В моем классе они только что упомянули: политика заменяет наименее часто используемую страницу, когда должно произойти выселение. Поэтому я поискал на YouTube, и большинство видео используют первый метод. Хотя большое спасибо!
2. теперь, когда я снова смотрю на это, беря следующую букву » Б «после буквы «В», о которой я спрашивал.
freq(A) = 3/9 = 0.33, freq(C)=1/2 = 0.5, freq(E)=1/1=1Однако для выселения было выбрано С, а не А. Частота А становится все меньше и меньше, но ее никогда не выселяют.3. @aujau: это действительно выглядит странно. Вам следует спросить об этом своего инструктора.