Разработка прототипа системы управления объектно-ориентированной базой данных



         

Система управления кэшированием объектов - часть 3


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

Для определения подмножества объектов кэша, подлежащих вытеснению, можно применить алгоритм решения задачи о рюкзаке. Если бы все объекты имели одинаковую длину, без этого можно было бы обойтись. Хотя алгоритм решения задачи о рюкзаке NP-сложен, решение можно компактно записать в виде рекурсивного алгоритма, нахо­дя­ще­го решение за счет применения принципа динамического программирования Беллмана. Такой способ наиболее эффективен, когда размер кэша составляет 32 объекта, посколь­ку множество выбранных объектов можно представить битовыми полями в длинном слове. При большем размере кэша возрастают потери памяти и быстродействия, и во­зникает вопрос о месте расположения данных промежуточных вызовов. Рекурсивный вызов в среде ДССП требует малых затрат ресурсов, а время расчета окупается за счет времени обмена с внешней памятью, работа с которой много медленнее, чем с оператив­ной.




Содержание  Назад  Вперед