Implementation of lru, Operating System

Assignment Help:

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.)


Related Discussions:- Implementation of lru

Capability lists are typically kept within the address space, Q. Capabilit...

Q. Capability lists are typically kept within the address space of the user. How does the system make sure that the user cannot modify the contents of the list? Answer: An ap

What are the issues in designing a network, Normal 0 false fa...

Normal 0 false false false EN-US X-NONE X-NONE MicrosoftInternetExplorer4

Important system components, Organizational, Structural, Logical and Execut...

Organizational, Structural, Logical and Execution Relationships Between Important System Components in Linux Kernel Subsystems A. Description of the Project You are require

Differences among user-level threads and kernel-level thread, Q. What are t...

Q. What are two differences among user-level threads and kernel-level threads? Under what situations is one type better than the other? Answer: (1) User-level threads are un

What is time-stamping, time-stamping It is a method proposed by Lampor...

time-stamping It is a method proposed by Lamport, used to sequencing events in a distributed machine without the use of clocks. This process is intended to order events consis

Intranet, how intranet can make your business effective

how intranet can make your business effective

Explain the resource ownership and control, Explain the Resource Ownership ...

Explain the Resource Ownership and Control Operating systems are required to handle many different types of resources. CPU , memory, and I/O devices  are some of the varied sys

Under what circumstances do page faults occur, Under what circumstances do ...

Under what circumstances do page faults occur?  Describe the actions taken by the operating system when a page fault occurs. A page fault happens when an access to a page that

Deadlock-avoidance safety algorithm, Q. Presume that you have coded the de...

Q. Presume that you have coded the deadlock-avoidance safety algorithm as well as now have been asked to implement the deadlock-detection algorithm. Can you do thus by simply usin

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd