Lru implementation details, Operating System

Assignment Help:

Now, let us discuss two related algorithms for deciding which pages to evict. The clock algorithm is one of the most popular choices. It works by keeping frames in a circular structure. (Note that this circle may be very large: a 32-bit machine with 4k pages can have up to 220  1 million frames.) When a page fault occurs, it checks the reference bit of the next frame. If that bit is zero, it evicts that page and sets its bit to 1; if the reference bit is 1, the algorithm sets the bit to 0 and advances the pointer to next frame. 

An implementation which is often used in real operating systems is a segmented queue. This type of algorithm divides all existing pages into two sets of pages. The most-active one-third of all pages use a clock algorithm. After that, pages that are evicted out of the clock are moved to a "uncommon" linked list, in which we use exact LRU. This way, we approximate LRU for the frequently-referenced pages (1/3 of the page frames - fast clock algorithm), and at the same time use exact LRU on the infrequently accessed pages (2/3 of all page frames). Since the pages in the uncommon list are not accessed very frequently, it is okay if their accesses are a little slower due to some pointer manipulation.


Related Discussions:- Lru implementation details

Life of a page, Suppose your process starts up, and allocates some memory w...

Suppose your process starts up, and allocates some memory with malloc(). The allocator will then give part of a memory page to your process. The OS then updates the corresponding p

What is super block, What is super block A partition control block have...

What is super block A partition control block have partitions details, such as the number of blocks in the partition, size of the blocks, free-blocks and free-block pointers an

Ipc, Explain in detail about ipc in linux

Explain in detail about ipc in linux

Explain how the system can deal with the starvation problem, Q. Can a syste...

Q. Can a system detect that some of its processes are starving? If you answer "yes," explain how it can. If you answer "no," explain how the system can deal with the starvation pro

What is process migration, Question: (a) Describe blocking and non-bloc...

Question: (a) Describe blocking and non-blocking types of inter-process communication. What is easier to implement and why? Discuss their relative advantages and disadvantage

What are overlays, What are overlays? To enable a process to be larger ...

What are overlays? To enable a process to be larger than the amount of memory allocated to it, overlays are used. The idea of overlays is to keep in memory only those instructi

Semaphores, how do semaphores help us in eliminating deadlock conditions?

how do semaphores help us in eliminating deadlock conditions?

List the four steps that are essential to run a program, List the four step...

List the four steps that are essential to run a program on a completely dedicated machine. a. Reserve machine time. b. Manually load program into memory. c. Load starting

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