естественно, на практике нужно подходить на оборот - присвоить индексу популярности запрашиваемой страницы общий индекс популярности - увеличив его сперва на единицу - ноль на оборот
при переполнении нужно тупо делить на два или на три все значения в таблице + предварительно сократив большие разрывы если такие имеются между рейтингами
Vladimir Mozhenkovну, если в первом случае мы отталкиваемся от большего, то в этом будем отталкиватся от меньшего, и изначально присваивать старнице не ноль, а MAX_INT. просто сменим знак с > на
Артур Гончарук Логика меняется. Смотрите, у вас 3 страницы. Доступы, 1 1 1 1 2 2 3 (вытеснение). По LRU вытеснить надо 1-ую, так как она дольше всего не исполнялась, а вы её подняли наверх и теперь выбираете страницу с наименьшим значением (третью), которая вот только что использовалась.
Vladimir Mozhenkov мы же может идти в любую сторону - удалять страницы не с наибольшей, а с наименьшей меткой. например, чем меньше значение - тем меньшее количество раз страница была использована
Артур Гончарук Ну вы подумайте, как это будет работать. 4 страницы. Доступы 1 1 1 1 1 2 3 3 4 4 4. Удалить нужно сейчас первую. Доступы 2 3 3 4 4 4. Тоже нужно удалить первую. Доступы 1 2 3 4. Тоже первую. Опишите как будет работать ваш алгоритм, а то вы просто говорите "можно", а что именно "можно" не описываете, а когда пытаетесь пишите взаимоотрицающие вещи.
естественно, на практике нужно подходить на оборот - присвоить индексу популярности запрашиваемой страницы общий индекс популярности - увеличив его сперва на единицу - ноль на оборот
И тогда получите LFU, а не LRU
Уже не терпится увидеть видео о реально используемых алгоритмах в реальных системах.
Спасибо!
да и нужно как нибудь решить проблему с переполнением счетчика, так как страницы запрашиваются миллиарды раз в секунду
при переполнении нужно тупо делить на два или на три все значения в таблице + предварительно сократив большие разрывы если такие имеются между рейтингами
Professor Bisслишком медленно
Артур Гончарук слыхал про не циклическое смещение битов?
Professor Bis это обычное побитовое смещение. а что?
так можно не инкрементировать все, а только запрашиваемую
Артур Гончарук Ну и как вы из этого получите страницу, которая дольше всех не запрашивалась?
Vladimir Mozhenkovну, если в первом случае мы отталкиваемся от большего, то в этом будем отталкиватся от меньшего, и изначально присваивать старнице не ноль, а MAX_INT. просто сменим знак с > на
Артур Гончарук Логика меняется. Смотрите, у вас 3 страницы. Доступы, 1 1 1 1 2 2 3 (вытеснение). По LRU вытеснить надо 1-ую, так как она дольше всего не исполнялась, а вы её подняли наверх и теперь выбираете страницу с наименьшим значением (третью), которая вот только что использовалась.
Vladimir Mozhenkov мы же может идти в любую сторону - удалять страницы не с наибольшей, а с наименьшей меткой. например, чем меньше значение - тем меньшее количество раз страница была использована
Артур Гончарук Ну вы подумайте, как это будет работать. 4 страницы. Доступы 1 1 1 1 1 2 3 3 4 4 4. Удалить нужно сейчас первую. Доступы 2 3 3 4 4 4. Тоже нужно удалить первую. Доступы 1 2 3 4. Тоже первую. Опишите как будет работать ваш алгоритм, а то вы просто говорите "можно", а что именно "можно" не описываете, а когда пытаетесь пишите взаимоотрицающие вещи.