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
properies of Batch oriented and interactive operating system.

Define Virtual memory Virtual memory is employed in all major commercial operating systems

Explain the ScheduleWorkToDo Function used in Netware ScheduleWorkToDo(MyThread Function, arg, workToDo) The ScheduleWorkToDo ( ) function is specific to NetWare 4.0. This c

What is sector sparing is proper definition

Inverted page table In page table the page table has one entry for every page that the process is using. The operating system must translate this reference into a physical memo

Explain working of the logical file system The logical file system manages metadata information. Metadata contains all of the file-system structure, excluding actual data. It h

Gopher Gallery consists of a shopping mall and a cart ride that covers the 150 acre habitat. There are m visitors and n single-person vehicles. Visitors stroll around the mall at t

Tree structured directories: This is the main common directory structure. The tree has a root directory as well as every file in the system has a unique path name. A directory

What are the methods for handling deadlocks ? The technique for handling the deadlocks are: We are able to use protocol to prevent or avoid the deadlock, make sure tha

What is external fragmentation? As process are removed from and loaded to the memory free memory space is bracken into pieces .external fragmentation take place when enough mem