Алгоритмы кэширования данных и их эффективность

ВВЕдение

     В качестве элементной базы основной памяти в большинстве ЭВМ используются микросхемы динамических ОЗУ (DRAM), на порядок уступающие по быстродействию центральному процессору. В результате, процессор вынужден простаивать несколько периодов тактовой частоты. Приемлемое решение этой проблемы возможно при использовании двухуровневой памяти, когда между основной памятью и процессором размещается небольшая, но быстродействующая буферная память или кэш-память.

     Впервые слово «кэш» в компьютерном контексте  было использовано в 1967 году в журнале «IBM Systems Journal». Статья касалась модернизации памяти в модели 85 из серии IBM System/360. Редактор журнала Лайл Джонсон попросил придумать более описательный термин, нежели “высокоскоростной буфер”, но из-за отсутствия идей сам предложил слово «кэш».

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

     Объект  исследования – алгоритмы кэширования данных.

     Предмет исследования – алгоритмы кэширования  данных LRU, LFU.

     Цель  исследования – выявить эффективность  алгоритмов кэширования данных LRU, LFU.

     

     Задачи исследования:

• проанализировать предметную область;
• спроектировать и реализовать программную систему для анализа эффективности алгоритмов кэширования данных LRU, LFU;
• провести сравнительный анализ эффективности алгоритмов кэширования данных LRU, LFU.

1. Анализ предметной области

1. Структура  и схема  работы кэш-памяти

     Как было сказано выше, кэш – промежуточный  буфер с быстрым доступом, содержащий информацию, которая может быть запрошена  с наибольшей вероятностью. Кэш состоит  из набора записей. Каждая запись ассоциирована  с элементом данных, либо блоком данных, которая является копией элемента данных в основной памяти. Также  запись имеет идентификатор, определяющий соответствие между элементами данных в кэше и их копиями в основной памяти (рис.1).

     

     Рис. 1. Диаграмма кэш памяти 

     Когда клиент кэша обращается к данным, прежде всего, исследуется кэш. Если в кэше найдена запись с идентификатором затребованного элемента данных, то используется элементы данных в кэше, происходит “быстрый ответ” (рис.2). Такой случай называется попаданием кэша.

     

       
 
 

 
 

Рис.2. Схема работы кэш-памяти

     Если  в кэше не найдена запись, содержащая затребованный элемент, то он читается из основной памяти в кэш, и становится доступным для последующих обращений. Такой случай называется промахом кэша, следовательно “медленный ответ” (рис.2).  

     

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

     Так как кэш ограничен в объеме, то при промахе может быть принято  решение отбросить некоторую  запись для освобождения пространства. Для выбора этой записи используют разные алгоритмы вытеснения (кэширования).

     От  алгоритма вытеснения зависит процент  попаданий и, следовательно, эффективность  кэширования. Поиск блока в кэш-памяти должен производиться достаточно быстро, чтобы задержки в принятии решения  не сводили на нет выигрыш от применения быстродействующей памяти.

     Далее рассмотрим следующие алгоритмы  кэширования:

• Алгоритм Белади;
• LRU(Least Recently Used);
• LFU(Least Frequently Used);
• LRR(Least Recently Replaced).

     Алгоритм  Белади наиболее эффективный алгоритм вытеснения, т.к. по нему будет всегда отбрасываться информация, в которой  мы не будем нуждаться дольше всего. Оптимальный результат достигается  за счет алгоритма предвидения. Так  как невозможно предсказать, когда именно в будущем потребуется эта информация, то на практике подобная реализация невозможна.

     

     LRU (наименее новый из запрашиваемых) – запись идет в строку, находящаяся в которой информация запрашивалась в последний раз наиболее давно. 

     LFU (наименее часто запрашиваемый)  - для записи выбирается строка, находящаяся в которой информация запрашивалась наименее часто.

     LRR (наименее новый из записанных) – другое название FIFO (первым пришел, первым ушел) – вытесняется строка, находящаяся в которой информация характеризуется наиболее старой записью. 

     

3. Ассоциативность и принципы локальности  кэш-памяти

     Оптимально  используют кэш-память задачи, следующие  принципам временной и пространственной локальности (temporal and spatial locality).

     Принцип временной локальности предполагает, что информация, которая была использована в недалёком прошлом, с большой  степенью вероятности будет запрошена  и в ближайшем будущем. Принцип  пространственной локальности предполагает, что информация, соседствующая с  уже запрошенной, также потребуется  в ходе дальнейшего выполнения задачи.

     Ассоциативность кэш-памяти является непосредственным показателем её логической сегментации: сколько каналов, столько и сегментов. Следовательно, кэш-память с N-канальной  ассоциативностью предполагает, что  информация, размещённая по некоторому адресу в оперативной памяти, может  находиться в N местах (строках) этой кэш-памяти (рис.3).

     

     Рис. 3. Ассоциативность кэш- памяти

     

     а) Кэш прямого отображения; б) Двухканальный  кэш;

4. Словарь предметной области

     Ассоциативность – информация, размещенная по некоторому адресу в основной памяти может находится  в N местах кэш памяти.

     Буфер - это область памяти, используемая для временного хранения данных при вводе или выводе.

     Доля  попаданий – доля обращений, найденных  в кэше.

     Кроссплатформенное  программное обеспечение — программное обеспечение, работающее более чем на одной аппаратной платформе и/или операционной системе.

     Кэш - промежуточный буфер с быстрым  доступом, содержащий информацию, которая  может быть запрошена с наибольшей вероятностью.

     Кэш попадание – в кэше найдена  искомая запись, данные читаются из кэш памяти.

     Кэш промах – в кэше не найдена искомая  запись, данные читаются из основной памяти и записываются в кэш.

     Объектно  – ориентированное программирование – программирование, основанное на совокупности объектов и трех базовых  понятиях: инкапсуляция, наследование и полиморфизм.

     Оперативная память (ОЗУ – оперативное запоминающее устройство, она же RAM) – память, предназначенная для временного хранения и передачи данных и команд процессору, для выполнения им операций.

     Процессор – это основное устройство (совокупность устройств), предназначенное для выполнения действий (последовательных арифметических или логических операций) в строгой последовательности, в соответствии с заданной программой, управления режимом работы и действиями сопряженных с ним устройств, осуществляющих функционирование с ним в единой системе.

 

2. Проектирование  архитектуры программной  системы
1. Иерархия классов

                                  
 
 
 
 

Рис.4. Схема иерархии классов. 

2. Блок  схемы алгоритмов

 

1. Алгоритм  работы приложения.

 
 
 

 

 
 
 
 

Рис.5. Блок-схема работы приложения.

2. Алгоритм LRU.

 
 
 
 
 
 
 
 
 
 
 
 
 

Рис.6. Блок-схема алгоритма LRU

3. Алгоритм LFU

 

 

Рис.7. Блок-схема алгоритма LFU

3. Реализация системы на языке высокого уровня

     Программа написана на ЯВУ JAVA. Данный язык был  выбран, т.к. данный язык предоставляет возможность объектно – ориентированного программирования. При разработке использовалась интегрированная среда разработки NetBeans 6.8. Ниже приведена структура проекта. 

     

     Рис. 8. Структура проекта 

     Библиотеки, используемые в приложении:

     Swing — библиотека для создания графического интерфейса на языке Java. Swing был разработан компанией Sun Microsystems. Он содержит ряд графических компонентов, таких как кнопки, поля ввода, таблицы и т. д. Swing предоставляет более гибкие интерфейсные компоненты, чем более ранняя библиотека AWT. В отличие от AWT, компоненты Swing разработаны для одинаковой кроссплатформенной работы, в то время как компоненты AWT повторяют интерфейс исполняемой платформы без изменений.

     java.util.Random – генератор случайных чисел.

     java.util.StringTokenizer – предназначен для выделения отдельных элементов из строк типа String.

     

       

4. Тестирование  приложения
1. Интерфейс приложения.

Рис.9. Интерфейс приложения

2. Работа приложения

Рис.10. Выполнение алгоритма LRU 
 
 

 

3. Завершение  работы приложения

Рис.11. Результаты выполнения без принципа локальности 

Рис.12. Результаты выполнения с использованием принципа локальности 
 
 
 

 
 

5. Исследование  эффективности алгоритмов кэширования