doubt

Question

Consider a simple system running a single process. The size of physical frames and logical pages is 16 bytes. The RAM can hold 3 physical frames. The virtual addresses of the process are 6 bits in size. The program generates the following 20 virtual address references as it runs on the CPU: 0, 1, 20, 2, 20, 21, 32, 31, 0, 60, 0, 0, 16, 1, 17, 18, 32, 31, 0, 61. (Note: the 6-bit addresses are shown in decimal here.) Assume that the physical frames in RAM are initially empty and do not map to any logical page.
Calculate the number of page faults genrated by the accesses above, assuming a LRU page replacement algorithm

Comments

@Mohan

6 bits of logical address is divided into 2 parts :- 4 bits for page size and rest 2 bits for page no.

Generally we are given the page nos. In the question. But here we are given the virtual addresses. So we need to find the page nos.

Remember the last 4 digits are for page size. And there can be 4 pages here because of 2 bits given.

A single page can contain 0000-1111 addresses i.e. 16 addresses.

So for page 0, the addresses would look like 00 0000, 00 0001,00 0010 and so on.

This was just to give you the concept.

So now you can see that page 0 will have addresses from 00 0000 to 00 1111 i.e. 0-15.

Page 1 will have addresses from 01 0000 to 01 1111 i.e. 16 to 31.

Page 2 : 10 0000 to 10 1111 i.e. 32 to 47.

Page 3: 11 0000 to 11 1111 i.e. 48 to 63.

Now replace the given addresses with their corresponding page nos. And solve.

---

@MiNiPanda Got my mistake. Forgot to include the first 3 as page faults :P

---

@ vishal chugh      0,0,1,0,1,1,2,1,0,3  ,0,0,1,0,1,1,2,1,0,3     8 misses is correct the answer

Answer 1

Answer 2

For 6 bit virtual addresses, and 4 bit page offsets (page size 16 bytes), the most significant 2 bits of a virtual address will represent the page number. So the reference string is 0, 0, 1, 0,1, 1, 2, 1, 0, 3 (repeated again). Page faults with FIFO = 8. Page faults on 0,1,2,3 (replaced 0), 0 (replaced 1), 1 (replaced 2), 2 (replaced 3), 3.