Сформулируйте алгоритм выбора кандидата на удаление из кэша “Наименее недавно использовавшийся” (lru). Опишите его работу на простом примере. В чем его преимущества и недостатки?
Кэш или кеш (англ. cache, от фр. cacher — прятать; произносится [kæʃ] — кэш) — промежуточный буфер с быстрым доступом, содержащий информацию, которая может быть запрошена с наибольшей вероятностью. Доступ к данным в кэше идёт быстрее, чем выборка исходных данных из оперативной (ОЗУ) и быстрее внешней (жёсткий диск или твердотельный накопитель) памяти, за счёт чего уменьшается среднее время доступа и увеличивается общая производительность компьютерной системы.
В информатике под алгоритмами кэширования (часто называемыми алгоритмами вытеснения или политиками вытеснения, а также «алгоритмами/политиками замещения») понимают оптимизацию инструкций — алгоритмы — особая компьютерная программа или аппаратно поддерживаемая структура, способная управлять кэшем информации, хранимой в компьютере. Когда кэш заполнен, алгоритм должен выбрать, что именно нужно удалить из него, чтобы иметь возможность записи (в кэш) новой, более актуальной информации.
«Уровень попаданий» кэша означает то, насколько часто искомые данные обнаруживаются в кэше. Более эффективные политики вытеснения отслеживают обращения к наиболее используемой информации, чтобы улучшить уровень попаданий (при том же размере кэша).
«Латентность» кэша означает насколько быстро кэш может вернуть запрошенные данные непосредственно после запроса (в случае, если происходит «попадание»). Более быстрые стратегии вытеснения обычно отслеживают наименее используемую информацию — или, в случае кэша прямого отображения (direct-mapped cache), отсутствие информации, чтобы снизить затраты времени на обновление информации.
Каждая стратегия вытеснения является компромиссом между уровнем попаданий и латентностью.
Least Recently Used (Наиболее давно использовавшийся)
Least Recently Used (LRU): в первую очередь, вытесняется неиспользованный дольше всех. Этот алгоритм требует отслеживания того, что и когда использовалось, что может оказаться довольно накладно, особенно если нужно проводить дополнительную проверку, чтобы в этом убедиться. Общая реализация этого метода требует сохранения «бита возраста» для строк кэша и за счет этого происходит отслеживание наименее использованных строк (то есть за счет сравнения таких битов). В подобной реализации, при каждом обращении к строке кэша меняется «возраст» всех остальных строк.
Вывод:
LRU (Least Recently Used) — вытесняется буфер, неиспользованный дольше всех;
Применение того или иного алгоритма зависит от стратегии кэширования данных. LRU наиболее эффективен, если данные гарантированно будут повторно использованы в ближайшее время.
Сформулируйте алгоритм выбора кандидата на удаление из кэша “Второй шанс”. Опишите его работу на простом примере. В чем его преимущества и недостатки? Кэш или кеш (англ. cache, от фр. cacher — прятать; произносится [kæʃ] — кэш) — промежуточный буфер с быстрым доступом, содержащий информацию, которая может быть запрошена с наибольшей вероятностью. Доступ к данным в кэше идёт быстрее, чем выборка исходных данных из оперативной (ОЗУ) и быстрее внешней (жёсткий диск или твердотельный накопитель) памяти, за счёт чего уменьшается среднее время доступа и увеличивается общая производительность компьютерной системы. В информатике под алгоритмами кэширования (часто называемыми алгоритмами вытеснения или политиками вытеснения, а также «алгоритмами/политиками замещения») понимают оптимизацию инструкций — алгоритмы — особая компьютерная программа или аппаратно поддерживаемая структура, способная управлять кэшем информации, хранимой в компьютере. Когда кэш заполнен, алгоритм должен выбрать, что именно нужно удалить из него, чтобы иметь возможность записи (в кэш) новой, более актуальной информации. «Уровень попаданий» кэша означает то, насколько часто искомые данные обнаруживаются в кэше. Более эффективные политики вытеснения отслеживают обращения к наиболее используемой информации, чтобы улучшить уровень попаданий (при том же размере кэша). «Латентность» кэша означает насколько быстро кэш может вернуть запрошенные данные непосредственно после запроса (в случае, если происходит «попадание»). Более быстрые стратегии вытеснения обычно отслеживают наименее используемую информацию — или, в случае кэша прямого отображения (direct-mapped cache), отсутствие информации, чтобы снизить затраты времени на обновление информации. Каждая стратегия вытеснения является компромиссом между уровнем попаданий и латентностью.
Что такое “старение”, и как этот подход может применяться для улучшения работы алгоритмов выбора кандидата на удаления из кэша? Приведите простой пример. Какую проблему решает использование этого подхода?
Стареющий
алгоритм - потомок алгоритма NFU
с модификациями, чтобы сделать это
знающий об отрезке времени использования.
Вместо того, чтобы только увеличить
прилавки страниц на который ссылаются,
ставящий равный акцент на ссылках
страницы независимо от времени,
справочный прилавок на странице сначала
перемещен право (разделенный на 2),
прежде, чем добавить бит, на который
ссылаются, налево от того двоичного
числа. Например, если страница сослалась
на биты 1,0,0,1,1,0 у прошлых 6 клещей часов,
его прилавок, на который ссылаются,
будет похож на это: 10000000, 01000000, 00100000,
10010000, 11001000, 01100100. Ссылки страницы ближе
на настоящее время оказывают больше
влияния чем ссылки страницы давно. Это
гарантирует, что у страниц, на которые
ссылаются позже, хотя менее часто
ссылающийся, будет более высокий
приоритет над страницами более часто
ссылаемым в прошлом. Таким образом,
когда страница должна быть обменяна,
страница с самым низким прилавком будет
выбрана.Отметьте, что старение отличается от LRU в том смысле, что старение может только отследить ссылки в последнем 16/32 (в зависимости от диаметра долота целых чисел процессора) временные интервалы. Следовательно, две страницы, возможно, сослались на прилавки 00000000, даже при том, что на одну страницу сослались 9 интервалов назад и другие 1000 интервалов назад. Вообще говоря, знание использования в пределах прошлых 16 интервалов достаточно для того, чтобы принять хорошее решение относительно который страница обменяться. Таким образом старение может предложить почти оптимальную работу за умеренную цену.
В чем разница между копированием при записи (copy-on-write) и изменением на месте (in-place modification)? В чем преимущества и недостатки этих способов изменения хранимых данных? В каких случаях эффективно применять каждый из них? Что такое сквозной кэш?
Механизм копирования при записи (англ. Copy-On-Write, COW) используется для оптимизации многих процессов, происходящих в операционной системе, таких как например работа с памятью или файлами на диске (пример — ext3cow).
Главная идея Copy-on-write — при копировании областей данных создавать реальную копию только когда ОС обращается к этим данным с целью записи.
Например, при работе unix-функции fork() вместо копирования выполняетcя отображение образа памяти материнского процесса в адресное пространство дочернего процесса, после чего ОС запрещает обоим процессам запись в эту память. Попытка записи в отображённые страницы вызывает исключение (exception), после которого часть данных будет скопирована в новую область.
"Копия на пишет" (иногда называемый "КОРОВОЙ" с англ.), стратегия оптимизации, используемая в программировании. Фундаментальная идея состоит в том, что, если многократные гости просят ресурсы, которые первоначально неразличимы, они могут все быть данными подсказками к тому же самому ресурсу. Эта функция может быть поддержана, пока гость не пытается изменить ее "копию" ресурса, в котором пункте истинная частная копия создана, чтобы предотвратить изменения, становящиеся видимой всем остальным. Все это происходит прозрачно с гостями. Основное преимущество состоит в том, что, если гость никогда не делает модификаций, никакая частная копия не должна никогда быть созданной.
"Копия на пишет" в виртуальной памяти
"Копия на пишет", находит ее главное использование в операционных системах виртуальной памяти; когда процесс создает копию себя, страницы в памяти, которая могла бы быть изменена или процессом или его копией, отмечены "копия на, пишут". Когда один процесс изменяет память, ядро операционной системы перехватывает операцию и копирует память так, чтобы изменения в памяти одного процесса не были видимы к другому.
Другое использование вовлекает функцию calloc. Это может быть осуществлено при наличии страницы физической памяти, заполненной нолями. Когда память ассигнована, страницы возвратились, все обращаются к странице нолей и все отмечены, как "копия на пишет". Этим путем количество физической памяти, ассигнованной для процесса, не увеличивается, пока данные не написаны. Это типично только сделано для больших распределений.
"Копия на пишет", может быть осуществлен, сообщая MMU, что определенные страницы в адресном пространстве процесса только для чтения. Когда данные написаны этим страницам, MMU поднимает исключение, которое обработано ядром, которое выделяет новое место в физической памяти и делает страницу написанной, соответствуют тому новому местоположению в физической памяти.
Одно главное преимущество КОРОВЫ - способность использовать память редко. Поскольку использование физической памяти только увеличивается, поскольку данные хранятся в этом, очень эффективные хеш-таблицы могут быть осуществлены, которые только используют немного больше физической памяти, чем необходимо, чтобы хранить объекты, которые они содержат. Однако, такие программы рискуют исчерпывать действительное адресное пространство — действительные страницы, неиспользованные хеш-таблицей, не могут использоваться другими частями программы. Главная проблема с КОРОВОЙ на ядерном уровне - сложность, которую это добавляет, но проблемы подобны поднятым более основными проблемами виртуальной памяти, такими как обменивающиеся страницы к диску; то, когда ядро пишет страницам, оно должно скопировать любые такие страницы, отметило "копию на, пишут".
http://hackerboss.com/copy-on-write-101-part-1-what-is-it/
http://stackoverflow.com/questions/628938/what-is-copy-on-write
???? in-place modification - ????
Traditional data structures are mutable. Let’s look at a simple binary search tree, for example:
Each node in the tree consists of a value (the number) and zero, one, or two arrows pointing to other nodes. Say you want to add a new node, a 34, in this tree. That’s easy, we just draw the new node in the right place:
Note that the tree is now changed. We had to update node 21 to point to node 34 in addition to 13. The original tree for all practical purposes does not exist anymore. Well, OK, it does on this page right here, but you get the point. At any one time, there is exactly one version of the tree in existence in your program.