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.

Posted Date: 3/12/2013 6:01:10 AM | Location : United States

Ask an Expert

Related Discussions:- Lru implementation details, Assignment Help, Ask Question on Lru implementation details, Get Answer, Expert's Help, Lru implementation details Discussions

Write discussion on Lru implementation details
Your posts are moderated

Write your message here..

Related Questions

Assignment, i need the job to be done within 3 days i need the job to be done within 3 days

Kernel to context switch between kernel level threads, Q. Explain the actio... Q. Explain the actions taken by a kernel to context switch between kernel level threads. Answer: Context switching among kernel threads classically requires saving the value

Describe the possible rmi invocation semantics, Question: (a) Explain t... Question: (a) Explain the similarities and differences between two different threads running in the same process and two independent processes. When would you want to use two t

What are the different thread levels?, What are the different thread levels... What are the different thread levels? There are two broad type of thread implementation: User-Level Threads -- Thread Libraries. Kernel-level Threads -- System Calls.

Explain the procedure for handling the page fault, The procedure for handli... The procedure for handling the page fault is as follows 1. We check the internal table to verify whether the reference was valid or invalid. 2. If the reference was invalid,

Interval between time of submission and completion of job, Interval among t... Interval among the time of submission and completion of the job is known as                    Interval among the time of submission and completion of the job is known as Turn

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

What is demand paging, What is Demand paging? Virtual memory is commonl... What is Demand paging? Virtual memory is commonly executed by demand paging. In demand paging, the pager brings only those essential pages into memory instead of swapping in a

Explain deadlock detection and recovery, Deadlock Detection and Recovery ... Deadlock Detection and Recovery It's a method of permitting the system to enter a deadlock state, detect it and then recover. Deadlock detection : Is the process of

What methods are used to monitor intrusion detection, Question : a) Wh... Question : a) What do you understand by a Directory Structure? Support your answer with a diagram. b) Give an example how Access Lists and Groups are arranged to mode of