Implementation of lru, Operating System

1. On every access, mark the page with a timestamp. Whenever we need to evict a page, we search through memory for the oldest page, the least-recently used page. But we need memory accesses to be fast. With this approach, on every memory access we would also need to read(load) a clock (or counter) and perform a store.

2. Maintain a queue of pages. Every time we touch a page, wemove that page to the beginning of the queue. When we need to evict a page, we evict the last element of the queue. Again, the pointer manipulation to do this would slow down the memory accesses, which we need to be fast on average.

3. Use a hash table rather than a queue. In this case, we have to compute a hash address on every memory access. Bad idea.

4. Approximate LRU.We can do this by maintaining reference bits for every page. On each memory access, the MMU hardware sets the page's reference bit to 1. Periodically, the OS tells the MMU to reset all the reference bits. Whenever we need to evict a page, we select one that has a reference bit not set. (So eviction may require an O(n) search through page tables to ?nd a page with reference bit not set, but the common case, cache hits, are very fast, done in hardware.) This algorithm considers any page which is zeroed to be "old enough". Then, although we can't know exactly what is the least-recently used, we do know that whatever is marked is a least more recent than something not marked. In practice, this approach works pretty well.

LRU is already only an approximation to OPT. In practice, we also approximate LRU itself. Our LRU approximation optimizes for the common case, which is cache hits, rather than cache misses. (If the common case is not cache hits, then your cache is not helping you.)

Posted Date: 3/12/2013 6:00:04 AM | Location : United States

Related Discussions:- Implementation of lru, Assignment Help, Ask Question on Implementation of lru, Get Answer, Expert's Help, Implementation of lru Discussions

Write discussion on Implementation of lru
Your posts are moderated
Related Questions
Some CPUs provide for more than two modes of operation. What are two possible uses of these multiple modes?

Define caching. A cache is a region of fast memory that holds copies of data. Access to the cached copy is well-organized than access to the original. Caching and buffering are

A-  In a table format, compare between Programmed I/O, Interrupt -driven I/O, and Direct Memory Access (DMA) in terms of basic idea, Advantages, disadvantages, and the operating en

Develop a utility in C language which will run in Linux operating systems to display following properties of the system: ? Processor speed ? Ram size ? Computer name ? System time

what are the design issues of network OS

Describe the file system architecture. File System Architecture contains the subsequent components:- Device Driver 1 Device Driver 2 Device Driver 3 Basic fi

Is it probable to have a deadlock involving only one single process? Describe your answer. Answer: No This pursue directly from the hold-and-wait condition.

Present your own fully documented and tested programming example illustrating the prevention of a data race in a parallelised program. This is an example where total number of p

Define UFD and MFD. In the two-level directory structure, every user has her own user file directory (UFD). Every UFD has a similar structure, but lists only the files of a one

An operating system involves 3 user processes each one requiring 2 units of resource R .The minimum number of units of R like no deadlocks will ever take place is The minimum