What is page fault? How FIFO page replacement algorithm works?

Consider the following page trace: 4,3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5

Percentage of page fault that would occur if FIFO page replacement algorithm is used with number of frames for the JOB m = 4 will be                [Paper II June 2012]

(A) 8               

(B) 9

(C) 10            

(D) 12

Answer is C

Read detailed explanation with page fault and FIFO page replacement algorithm. 

What is page fault?

A page fault is the situation arises when running program tries to access the required page in Physical Memory (RAM) but the page is not available in RAM this is called page fault. when page is not available in RAM then operating system tries to find page data from virtual memory and load the page into RAM.

An invalid page fault or page fault error occurs when the operating system cannot find the data in virtual memory. This usually happens when the virtual memory area, that maps virtual addresses to real addresses, becomes corrupt.

The term page fault is a bit misleading as it implies that something went seriously wrong. Although page faults are undesirable – as they result in slow accesses to the hard disk – they are quite common in any operating system that uses virtual memory.

Now, we need to actually solve the problem. The easiest way to do this is to break the problem down into the number of pages. See what happens each time a page is referenced by the program, and at each step see whether a page fault is generated or not. Of course, we want to keep track of what pages are currently in the physical memory (the RAM).

The first four page accesses will result in page faults because the frames are initially empty. After that, if the program tries to access a page that’s already in one of the frames then there’s no problem. But if the page that the program is trying to access is not already in one of the frames then that results in a page fault. In this case, we have to determine which page we want to take out (or ‘swap’) from the RAM, and for that we use the FIFO algorithm.

Below is the explanation of page 4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5 and page frame size is 4.

Page	4	3	2	1	4	3	5	4	3	2	1	5
Sr. No.	1	2	3	4	5	6	7	8	9	10	11	12
1	4	4	4	4	4	4	5	5	5	5	1	1
2		3	3	3	3	3	3	4	4	4	4	5
3			2	2	2	2	2	2	3	3	3	3
4				1	1	1	1	1	1	2	2	2
Buffer of 4 Frame

As per above image we have size of 4 frame.  When operating system trying to access data 4 from physical memory then data is not available in physical memory so data 4 will be as page fault so operating system will search data page in virtual memory and load the frame with data 4, afterward data 3, 2, 1 also be a page fault. At column no. 5 demanding of data 4 which is available in physical memory (RAM) so no page fault, afterwards same as 3 is available in   physical memory.  At column no. 7 demanded of data 5 which is not available in physical memory and we have to follow FIFO page replacement algorithm so data 4 has came first so data 4 will be removed and data 5 will be placed as a page fault because it is not available in physical memory.  Same as all other data pages and procedure will work and at the end we can count grayed area which is demanded but does not available in physical memory and became page fault so total grayed area are 10. So page fault is 10.

what is cached memory and interleaved memory?

Cached and interleaved memories are ways of speeding up memory access between CPU’s and slower RAM. Which memory models are best suited (i.e. improves the performance most) for which programs?     [Paper II June 2012]

(i) Cached memory is best suited for small loops.

(ii) Interleaved memory is best suited for small loops

(iii) Interleaved memory is best suited for large sequential code.

(iv) Cached memory is best suited for large sequential code.

(A) (i) and (ii) are true.

(B) (i) and (iii) are true.

(C) (iv) and (ii) are true.

(D) (iv) and (iii) are true.

Anser is B.

What is Cache memory? How it works?

When you open any program like MS Word or any other program at that time operating system will read data from hard disk (slow moving storage device) to a faster device. This faster device is called RAM (Random Access Memory).

This RAM is type of DRAM (Dynamic Random Access Memory).  RAM is placed here because it is a faster device, and whenever any data or instruction required by Processor, RAM will provide them at a faster rate than slow storage devices. They serve as a cache memory for the storage devices.

RAM is much faster than slow storage device like hard disc but the processor processes at much a faster speed and they are not able to provide the needed data or instructions at that rate.

Cache memory

So there is need of a device that is much faster than RAM which can provide data from RAM to Processor at the speed rate as of processor.

Therefore the data required is transmitted to the next level of fast memory, which is known as CACHE memory. CACHE is also a type of RAM, but it is Static RAM – SRAM. SRAM are faster and costlier then DRAM because it has flip-flops (6 transistors) to store data unlike DRAM which uses 1 transistor and capacitor to store data in form of charge.

       The CPU uses cache memory to store instructions that are repeatedly required to run programs.

What is interleaved memory?

Memory interleaving is the technique used to increase the throughput. The main idea behind interleaved memory is to split the memory system into independent banks which can read and write requests independently and parallels.

Main memory divided into two or more sections which is called memory bank. The CPU can access alternate sections immediately, without waiting for memory to catch up (through wait state).

Main memory (Random Access Memory) is usually composed of a collection of DRAM memory chips, where a number of chips can be grouped together to form a memory bank

Interleaved memory is a technique to allocate memory address to each memory bank in turn which  resulting in higher memory throughputs due to reduced waiting for memory banks to become ready for desired operations.

Interleaved memory technique is used increased speed for the relatively slow speed of dynamic RAM (DRAM).

Memory interleaving implemented on main memory (RAM), which is slow as compared to Cache Memory and Main Memory (RAM) having less bandwidth.