算法高级教程3.10.1Onlinecachingproblem.pptVIP

* Online Caching Algorithms The problem we consider a processor whose full memory has n addresses; it is also equipped with a cache containing k slots of memory that can be accessed very quickly. We can keep copies of k items from the full memory in the cache slots, and when a memory location is accessed, the processor will first check the cache to see if it can be quickly retrieved. The goal of a Cache Maintenance Algorithm is to minimize the number of cache misses. * * Cache Data brought from slow memory into small fast memory (cache) of size k Sequence of requests: equal size pages Hit: page in cache, Misses: page not in cache Minimized the number of Misses. Analyzing the caching process Two kinds of memory: Fast memory: cache of size k Slow memory: disc of size n Examples: hard disc versus processor cache network resources versus local memory Problem: In each step a request for a value arrives; If the value is in cache then answering does not cost anything, otherwise it costs one unit (of access to the slow memory) Performance measure: Count the number of accesses to the slow memory Compute competitive ratio Marking Algorithms MarkingAlgorithm() 1 Each item in cache is either marked or unmarked 2 At the beginning of each phase all items are unmarked 3 for a request to item s do 4 Mark s 5 if s in cache then evict nothing 6 else 7 if all items in cache are marked then 8 Declare the phase over 9 Processing of s is deferred to start of next phase 10 else evict an unmarked item from the cache * * Evict strategies The key step—evict an unmarked item from the cache—does not specify which unmarked item should be selected. The evict strategies are as follows: First-in, First-out(FIFO): Evict the page that has been in the cache the longest Least recently used (LRU): Evict the page whose last request occurred furthest in the past. Random: Choose a page at ra