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

What is starvation?, What is starvation? A main problem related to dead...

What is starvation? A main problem related to deadlock is starvation. Starvation is the circumstances where process waits indefinitely within the semaphore. Indefinite blocking

Explain disadvantages of the two-level directory, How do we overcome the di...

How do we overcome the disadvantages of the two-level directory? Give links from one user directory to another, creating path names; system files become available by letting th

What is page fault?, What is page fault? In the computer storage techno...

What is page fault? In the computer storage technology a page fault is an exception which is raised by the memory management unit when a requested page isn't mapped in physical

Explain medium term scheduling, Medium term scheduling This is componen...

Medium term scheduling This is component of the swapping function. Usually the swapping in decision is based on the need to manage the degree of multiprogramming. At a system t

How several bits are there in the logical address, Q. Regard as a logical a...

Q. Regard as a logical address space of eight pages of 1024 words every mapped onto a physical memory of 32 frames. a. How several bits are there in the logical address? b. H

Define a state which is not a fundamental process state, Define a state whi...

Define a state which is not a fundamental process state Answer: Blocked state is not a fundamental process state

What are the reasons for process suspension, Q. What are the reasons for pr...

Q. What are the reasons for process suspension? Reasons for process suspension 1.  Swapping 2.  Timing 3.  Interactive user request 4.  Parent process request

Explain message passing among systems, Q. Explain Message passing among sys...

Q. Explain Message passing among systems? Communications- Message passing among systems requires messages to be turned into packets of information and sent to the network contr

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