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

Linux, what is I/O management Linux

what is I/O management Linux

Demand paging, Demand paging gives that pages could only be brought into ...

Demand paging gives that pages could only be brought into memory if the running process acts them. This is usually referred to as lazy evaluation as only those pages operated by

Multiprogramming, ? FREE ASSOCIATION ASSIGNMENTS of multiprograming

? FREE ASSOCIATION ASSIGNMENTS of multiprograming

What lead to the concept of paging?, What lead to the concept of paging? ...

What lead to the concept of paging? The main memory is separated into two parts that are one for the resident operating system, and one for the user processes. We may perhaps p

Search and print between two words/patterns, what if we need the portion fr...

what if we need the portion from a text based on some keyword. For eg. My file is like below, ------------------------------------------------ Order=[ 1 2 3 4 5 Order=[ 6 7 8 9

Explain independent process and a cooperating process, Question: a) Ea...

Question: a) Each process is represented in the operating system by a process control block (PCB). The PCB contains many pieces of information associated with a specific proce

Explain general graph directory structure, General Graph Directory A s...

General Graph Directory A serious trouble with using an acyclic graph structure is making sure that there are no cycles. When links are further added to an existing tree struc

Explain the sleep (ms) function, Explain the Sleep (ms) Function  This ...

Explain the Sleep (ms) Function  This call places the current thread in a suspended state for the number of milliseconds passed as the parameter (ms). After that Windows NT wil

#title.paging, explain hierarchical,hashed and inverted paging

explain hierarchical,hashed and inverted paging

Peripharal device, 50 peripharal device name ,diagram and uses

50 peripharal device name ,diagram and uses

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