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

Автор: Пользователь скрыл имя, 09 Марта 2011 в 11:30, курсовая работа

Краткое описание

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



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

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

Оглавление

Введение 3

1.Анализ предметной области 4
1.Структура кэш-памяти и схема ее работы 4
2.Алгоритмы кэширования 5
3.Ассоциативность и принципы локальности кэш-памяти 6
4.Словарь предметной области 7
2.Проектирование архитектуры разрабатываемой системы 8
1.Иерархия классов 8
2.Блок – схемы алгоритмов 8
3.Реализация системы на языке высокого уровня 10
4.Тестирование приложения 11
5.Исследование эффективности алгоритмов 13
Заключение 17

Список использованной литературы 18

Приложение 19

Скачать в ZIP (466.65 Кб) Сколько стоит заказать работу?
Файлы: 4 файла

Графики.xlsx

— 16.78 Кб (Открыть, Скачать)

Курсовая работа.docx

— 413.90 Кб (Скачать)
 

     Для определения эффективности алгоритма необходимо провести анализ. Эффективность определяется средним количеством попаданий при различных наборах (обращения процессора).

     Для этого берем 5 различных наборов и заполняем таблицы для двух алгоритмов (табл. 1, табл. 2), где H – среднее число кэш-попаданий           (, где Нi – количество попаданий при i-ом наборе), M – среднее число промахов (, где Mi – количество промахов при i-ом наборе), ∆ - процентное отношение объема кэша к объему оперативной памяти ( )

     Для LRU:

    ∆, %
    H
    M
    10
    64,8
    535,2
    20
    123,4
    476,6
    30
    178,6
    421,4
    40
    229,4
    370,6
    50
    276
    324
    60
    320
    280
    70
    359,4
    240,6
    80
    389,8
    210,2
    90
    410,2
    189,8
    100
    412,8
    187,2

Табл. 1. Результаты работы алгоритма LRU

 
 
 

     Для LFU:

    ∆, %
    H
    M
    10
    53,4
    546,6
    20
    115,6
    484,4
    30
    172,6
    427,4
    40
    225,4
    374,6
    50
    278
    322
    60
    319,8
    280,2
    70
    356,8
    243,2
    80
    385,8
    214,2
    90
    407,6
    192,4
    100
    412,8
    187,2

Табл. 2. Результаты работы алгоритма LFU

Рис. 13. График зависимости количества попаданий от отношения памяти

     Из  результатов анализа видно, что  при небольшом объеме кэша, количество попаданий больше у алгоритма LRU. Следовательно, этот алгоритм является более эффективным, т. к. кэш характеризуется  небольшим объемом памяти.

     Далее выясним, как влияет принцип пространственной и временной локальности на эффективность. Возьмем фиксированное значение отношения памяти (∆=10%), а будем изменять P – ту часть оперативной памяти, к которой обращается процессор (Xi – количество попаданий при i-ом проценте оперативной памяти, Yi - количество промахов при i-ом проценте оперативной памяти).

     Для LRU:

    P, %
    Xi
    Yi
    10
    581
    19
    20
    302
    298
    30
    199
    401
    40
    165
    435
    50
    127
    473
    60
    103
    497
    70
    93
    507
    80
    82
    518
    90
    78
    522
    100
    63
    537

Табл. 3. Результаты работы алгоритма LRU 
 
 
 

 

     Для LFU:

    P, %
    Xi
    Yi
    10
    581
    19
    20
    298
    302
    30
    197
    403
    40
    150
    450
    50
    98
    502
    60
    107
    483
    70
    74
    526
    80
    88
    512
    90
    62
    538
    100
    58
    542

Табл. 3. Результаты работы алгоритма LFU 

Рис. 14. График количества попаданий при использовании принципа локальности

     Из  результатов анализа видно, что при большем объеме кэша, количество попаданий больше у алгоритма LRU. При малом же объеме, значения двух алгоритмов примерно равны.

Заключение

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

     Была  разработана программа на языке  высокого уровня JAVA с использованием интегрированной среды и проведено тестирование реализованного приложения.

     Рассчитана  эффективность алгоритмов кэширования  данных LRU, LFU. В результате сравнительного анализа сделан вывод о том, что  алгоритм LRU наиболее эффективен (рис. 13,14), так как при нём наблюдается самое большое число попаданий. 
 
 
 
 
 
 
 
 
 
 
 

 

Список  использованной литературы

  1. Олифер В.Г., Олифер Н.А. Сетевые и операционные системы. – СПб.: Питер, 2001.
  2. Петцольд Ч. Программирование для Windows 95. – том 1,2. – СПб.: Русская редакция, 1997.
  3. Таненбаум Э. Современные операционные системы. – СПб.: Питер, 2006.
  4. Свободная энциклопедия Википедия [Электронный ресурс]: Алгоритмы кэширования – M., 2010 – Режим доступа:  http://ru.wikipedia.org/wiki/LRU#Least_Recently_Used_.28.D0.A0.D0.B5.D0.B4.D0.BA.D0.BE.D0.B8.D1.81.D0.BF.D0.BE.D0.BB.D1.8C.D0.B7.D1.83.D0.B5.D0.BC.D1.8B.D0.B9_.D1.8D.D0.BB.D0.B5.D0.BC.D0.B5.D0.BD.D1.82.29 - Загл. с экрана.
 
 
 
 
 
 
 
 
 
 
 
 
 

Приложение.docx

— 41.71 Кб (Открыть, Скачать)

Титульник и содержание.docx

— 21.73 Кб (Открыть, Скачать)

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