Алгоритм кэширования 2Q

Алгоритм кэширования 2Q (Two Queues) представляет собой метод управления кэш-памятью. Этот алгоритм состоит из двух очередей: q1 и q2. q1 является буфером, в который добавляются данные только в начале и замещаются из конца, а q2 используется для хранения "недавно использованных" данных.

Генератор тестов

Генератор тестов - src/test_gen.py спрашивает количество тестов и создает pytests.txt Чтобы сгенерировать тесты нужно написать в терминал

Программа спросит количество тестов и сгенерирует файл pytest.txt в tests

ideal_test_gen

сгенирирует один тест в файле ideal_pytest.txt для идеального кэша, все значения случайны

Сборка

Cmake

1. Написать в терминале
   cmake -DCMAKE_BUILD_TYPE=Release -S. -B build
2. 'cmake --build build'
3. 'cd build'
4. Запустите необходимый бинарник './Q2'

Принцип работы

Когда данные добавляются в кэш, они помещаются в начало q1. Если данные извлекаются из кэша, они перемещаются из q1 в начало q2. Если данные снова запрашиваются и они находятся в q2, они перемещаются в конец q1. Если данные снова запрашиваются и их уже нет в кэше, они добавляются в начало q1, а если q1 заполнена, то данные из конца q1 удаляются и добавляются новые данные в начало q1.

Тестирование

Тестирование 2Q кэша:

После сборки в папке ./build можно запустить

При указании файла будет запущен конкретный тест

./test_cache "test_file_name"

Если файл не указан, будет запущен стандартный

/tests/ideal_pytest.txt

Если путь не указан, то программа будет использовать тест test/pytest.txt

Тестирование идеального кэша

Если путь не указан, то программа будет использовать тест

./tests/ideal_pytest.txt

Преимущества

Эффективность:

алгоритм 2Q обладает хорошей производительностью и способен эффективно управлять кэш-памятью.

Адаптивность:

алгоритм автоматически регулируется в зависимости от обращаемости данных, приспосабливаясь к изменениям в запросах.

Недостатки

Не подходит для всех типов данных: алгоритм 2Q неэффективен для случаев, когда данные необходимо хранить в определённом порядке. Сложность реализации: реализация алгоритма кэширования 2Q может быть более сложной, чем у других методов управления кэш-памятью.