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

DMA block diagram, I need help,i want a brief and easy explanation to under...

I need help,i want a brief and easy explanation to understand and write in exams and easy to understand topic of DMA block diagram which Is of I/O management and scheduling? can u

How are file sharing and protection implemented, How are file sharing and p...

How are file sharing and protection implemented? To execute file sharing and protection the system have to maintain more file and directory attributes than are needed on a sing

Define the non monolithic coding, Define the Non Monolithic Coding Fir...

Define the Non Monolithic Coding First off, client - server developers must adopt a new programming mindset. Much as with the shift to object - oriented design, developers sho

Explain objectives of the file management system, Problem: a) Define a ...

Problem: a) Define a ‘file' and list the objectives of the file management system. b) List the ways in which programs access files and determine for what file types you woul

Blocking locks, We have talked about blocking locks, which voluntarily yiel...

We have talked about blocking locks, which voluntarily yield, and spinlocks, which just spin until they acquire the lock. At ?rst, it seems like spinlocks are verywasteful, and tha

VB. Net & XML, Write a XML with database with book details (BOOK ID, Title,...

Write a XML with database with book details (BOOK ID, Title, Author, subject, publisher year, language, vendor, and price)

Identify main functions of an operating system, Question: Introduction to ...

Question: Introduction to Operating Systems a) Define the term ‘Operating System' and identify main functions of an operating system. b) What are the characteristics of a go

Parent process: why not finishing and how to make finish, #include #inclu...

#include #include #include #include #include int main(void) { int pchan[2], pid, rval, cvar; char buf[20]; if (pipe(pchan) == -1){

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