Буферный пул с страницами переменного размера. Нужен высокопроизводительный способ объединения страниц, когда входящая страница больше, чем страница, которую нужно удалить
В реализации пула буферов базы данных (пула памяти) у меня есть буфер, который состоит из страниц в памяти.
Страницы имеют разные размеры (все целое кратное 512 КБ).
Скажем, моя политика выселения — LRU (используется не так давно), но страница, которую я пытаюсь выселить, имеет меньший размер, чем то, что мне нужно заменить. Если я тоже хочу следовать за LRU, я должен удалить столько страниц LRU, сколько необходимо для моя новая страница
Предположим, мне нужно n недавно использованные страницы будут выселены. Тем не менее, эти страницы не обязательно являются последовательными в пуле буферов / памяти.
Простой подход, о котором я думал, это объединить эти n страниц, что означает, что мне нужно соответствующим образом переупорядочить буферный пул.
Самый простой подход — скопировать весь буфер, перезаписать постоянный буфер и соответствующим образом обновить типы данных. Тем не менее, это предполагает, что у нас достаточно ОЗУ для копирования всего буфера для этой операции. Есть ли разумный подход, когда мне не нужно копировать весь буфер?
Спасибо
Решение
Как только вы будете перемещать буферы, на мой взгляд, это не будет «высокой производительностью», как насчет этого:
Страницы, которые вы собираетесь выселить, имеют общий размер К раз размер страницы 512 кБ, то есть размер входящей страницы.
Наихудшее расположение выглядит примерно так (четыре символа (кроме баров |) == 512 кБ):
|X1 |1 |2 |X2 |3 |4 |
Два XЭто страницы для выселения. Проблема в том, что для того, чтобы буферы были последовательными, вам нужно переместить X2 рядом с X1 (или наоборот). Мой подход заключается в перемещении страниц после X1 вправо (в X2) на месте. Мы можем переопределить X2потому что мы все равно хотим его выселить.
Таким образом, нам нужно всего лишь обновить 3 страницы, а не копировать весь буфер.
Более сложная проблема будет:
|X1 |1 |2 |X2 |3 |X3 |4 |5 |
Можно по-прежнему использовать наивный алгоритм сверху, но возможны оптимизации. Например, можно смело двигаться 1 в X2 не касаясь 2потому что он там подходит. То же самое касается 2, который может быть перемещен в X3,
Так что на самом деле вы всегда можете воспользоваться простой техникой перемещения, известной как вставка и замена динамического массива, но, возможно, было бы целесообразно проверить возможные оптимизации, в этом случае перечислить страницы, которые должны быть перемещены наивным алгоритмом, и сначала попытайтесь вписать их прямо в выселяемое пространство. Только после этого (как в первом примере) происходит перемещение.
Копирование всего буфера должно быть необходимым, только если вам нужна атомарность. В этом случае оптимизированный подход сверху также будет работать, но у вас возникнут проблемы, как только вы не сможете разместить страницы, находящиеся на вашем пути, на страницах, подлежащих выселению. В этом случае вы должны использовать алгоритм выселения, чтобы найти подходящие места, возможно, выбрасывая больше страниц.
Другие решения
Других решений пока нет …