Least recently Used (LRU)

Operating System Fundamentals
60
Hit Ratios Determining Which Replacement Policy to Use
Using each of the five main replacement policies to swap pages between main memory and the page file will result indifferent hit ratios. A hit ratio is the number of times that a page is actually found in main memory, as opposed to the number of page faults generated (requiring the memory manager to retrieve the page from virtual memory. To calculate the hit ratio, we divide the number of non page faults by the total number of page requests (the number of times that data has been sent between the CPU and main memory. Remember—page faults occur when a page is requested by the CPU that is not currently in the page table (in other words, not currently in RAM. The memory manager resolves the page fault be swapping an old page from RAM to the page file (on the hard disk, then retrieving the requested page from virtual memory to RAM, and then re-executing the instruction. Since there are extra steps involved in order to execute the instruction, and since retrieving a page from a hard disk is slower than RAM, page faults result in longer processing time. We use hit ratios to determine which replacement policy will result in the fewest number of page faults, and the fastest overall processing time. The policy that produces the lowest number of page faults is usually the policy we want to use.
Calculating Hit Ratios
To understand how to calculate hit ratios, we will examine an example that uses a RAM space of three (3) frames, and the following processing sequence
1 2 1 3 1 4 1 5 2 3 2 4 1 5 In these examples, Ya hit (the page is found in RAM, and Na page fault (the page must be retrieved from virtual memory. A frame is a segment of RAM that can be allocated to hold a page, and is typically the same size as a page. Frames 1-3 are located in RAM. Frames 4-5 represent pages located in virtual memory.

Download 2.34 Mb.

Share with your friends: