Это алгоритм из класса политик, применяемых для управления страницами виртуальной памяти.
Кеш задан очередью FIFO, где у каждого элемента помимо кешируемого значения есть признак используемости. При добавлении нового элемента, он добавляется в начало очереди, возможно вызывая вытеснение элемента с конца очереди. Признак используемости у вновь добавленного элемента не выставлен.
При вытеснении элемента у него проверяется признак используемости и если он выставлен, то элемент не удаляется совсем, а помещается в начало очереди (возможно также вызывая новое вытеснение), при этом признак используемости этого элемента сбрасывается.
Возврат вытесненного, но "спасённого" признаком используемости элемента в очередь происходит до помещения туда нового элемента, чья вставка вызвала вытеснение. Таким образом, вновь вставленный в кеш элемент всегда будет в начале очереди, а все изменения, связанные с вытеснением и возможным возвратом в очередь будут происходить до его вставки (но с очередью, чей эффективный размер на единицу меньше размера кеша).
Возможно, что в очередь все элементы имеют признак используемости - тогда добавление нового элемента и вытеснение одного из старых элементов:
- сбросит все признаки используемости
- удалит из кеша элемент из конца очереди
При поиске элемента, если он найден, то он не меняет своей позиции в очереди, но у него выставляется признак используемости.
В реализации кеша допустимо предполагать, что все хранимые там объекты имеют в иерархии наследования предка, задаваемого шаблонным параметром KeyProvider, который, в свою очередь, имеет оператор равенства с ключом (задаваемым шаблонным параметром Key).
Требуется модифицировать pool аллокатор так, чтобы его методы allocate/deallocate принимали произвольный размер в байтах.
При этом требуется поддерживать определённый уровень фрагментированности пула: если новая аллокация размера X невозможна (нет нужного свободного фрагмента), но пул заполнен менее, чем на N - 2 * X, где N - это полный размер пула, то требуется провести процедуру дефрагментации и успешно выделить запрошенную память.