Useful Infomation

---

A page fault occurs when the referenced page is not found in the main memory

Page fault handling routine is executed on the occurrence of page fault

The time taken to service the page fault is called as page fault service time.

---

1. Tutorial 01

---

1.1. Exercise 1

1.1.1. Question

• In a demand-paging system, it takes 250 ns to satisfy a memory access when the requested page is in the resident set.
• If it is not in the resident set, then the request takes 10 ms if a free frame is found or the page to be replaced is not modified. Such requests are 3% of all the accesses.
• Otherwise, if there is no free frame and the page to be replaced is modified, then it takes 20 ms. Such pages are 7% of all the accesses.
• If the Page Fault Rate PFR in the system is 10%, then what will be the EAT?

1.1.2. Analysis

• Page Fault Rate = Page Fault with Free Frame Rate + Page Fault without Free Frame Rate
• Page Fault Time = Page Fault with Free Frame Time + Page Fault without Free Frame Time
• Page Fault with Free Frame Time = Page Fault with Free Frame Rate x 10 ms
• Page Fault without Free Frame Time = Page Fault without Free Frame Rate x 20 ms

1.1.3. Solution

• 

1.2. Exercise 2

1.2.1. Question

• Calculate the number of page faults for the following reference string using FIFO algorithm with frame size as 3 and then as 4
• 4 3 2 1 4 3 5 4 3 2 1 5
• FIFO - the oldest page is chosen

1.2.2. Solution

• Frame size = 3
  4	3	2	1	4	3	5	4	3	2	1	5
  4	4	4	1	1	1	5			5	5
  	3	3	3	4	4	4			2	2
  		2	2	2	3	3			3	1
  Number：9

• Frame size = 4
  4	3	2	1	4	3	5	4	3	2	1	5
  4	4	4	4			5	5	5	5	1	1
  	3	3	3			3	4	4	4	4	5
  		2	2			2	2	3	3	3	3
  			1			1	1	1	2	2	2
  Number：10

1.3. Exercise 3

1.3.1. Question

• Calculate the number of page faults for the following reference string using optimum algorithm with frame size as 3
• 5 0 2 1 0 3 0 2 4 3 0 3 2 1 3 0 1 5
• OA – replace a page that will not be used for longest period of time

1.3.2. Solution

• optimum algorithm with frame size as 3
  5	0	2	1	0	3	0	2	4	3	0	3	2	1	3	0	1	5
  5	5	5	1		3			3				3	3				5
  	0	0	0		0			0				0	0				0
  		2	2		2			4				2	1				1
  Number：9

1.4. Exercise 4

1.4.1. Question

• Calculate the number of page faults for the following reference string using LRU page-replacement algorithm with frame size as 3.
• 5 0 2 1 0 3 0 2 4 3 0 3 2 1 3 0 1 5
• throw out the page that has been unused for the longest time

1.4.2. Solution

• optimum algorithm with frame size as 3
  5	0	2	1	0	3	0	2	4	3	0	3	2	1	3	0	1	5
  5	5	5	1		1		2	2	2	0		0	1		1		1
  	0	0	0		0		0	0	3	3		3	3		3		5
  		2	2		3		3	4	4	4		2	2		0		0
  Number：13

---

2. PAGE FAULT

---

2.1. Exercise 2

2.1.1. Question

• Let the page fault service time be 10 ms in a computer with average memory access time being 20 ns. If one page fault is generated for every memory accesses, what is the effective access time for the memory?
  • a. 21 ns
  • b. 30 ns
  • c. 23 ns
  • d. 35 ns

2.1.2. Solution

• Option (B) is correct
  • 
  • 
  • 
  • 
  • 

---

3. PAGE REPLACEMENT ALGORITHMS

---

3.1. Problem-01

3.1.1. Question

• A system uses 3-page frames for storing process pages in main memory. It uses the First in First out (FIFO) page replacement policy. Assume that all the page frames are initially empty. What is the total number of page faults that will occur while processing the page reference string given below?
• 4 , 7, 6, 1, 7, 6, 1, 2, 7, 2
• Also calculate the hit ratio and miss ratio

3.1.2. Solution

• FIFO algorithm with frame size as 3
  4	7	6	1	7	6	1	2	7	2
  4	4	4	1				1	1
  	7	7	7				2	2
  		6	6				6	7
  Total number of references = 10 Total number of page misses or page faults = 6 Total number of page hits = 4

• Hit ratio = Total number of page hits / Total number of references = 4 / 10 = 40%
• Miss ratio = 1 - Hit ratio = 1 - 40% = 60%

3.2. Problem-02

3.2.1. Question

• A system uses 3-page frames for storing process pages in main memory. It uses the Least Recently Used (LRU) page replacement policy. Assume that all the page frames are initially empty. What is the total number of page faults that will occur while processing the page reference string given below?
• 4 , 7, 6, 1, 7, 6, 1, 2, 7, 2
• Also calculate the hit ratio and miss ratio

3.2.2. Solution

• LRU algorithm with frame size as 3
  4	7	6	1	7	6	1	2	7	2
  4	4	4	1				1	1
  	7	7	7				2	2
  		6	6				6	7
  Total number of references = 10 Total number of page misses or page faults = 6 Total number of page hits = 4

• Hit ratio = Total number of page hits / Total number of references = 4 / 10 = 40%
• Miss ratio = 1 - Hit ratio = 1 - 40% = 60%

3.3. Problem-03

3.2.1. Question

• A system uses 3-page frames for storing process pages in main memory. It uses the Optimal page replacement policy. Assume that all the page frames are initially empty. What is the total number of page faults that will occur while processing the page reference string given below?
• 4 , 7, 6, 1, 7, 6, 1, 2, 7, 2
• Also calculate the hit ratio and miss ratio

3.2.2. Solution

• LRU algorithm with frame size as 3
  4	7	6	1	7	6	1	2	7	2
  4	4	4	1				1
  	7	7	7				7
  		6	6				2
  Total number of references = 10 Total number of page misses or page faults = 5 Total number of page hits = 5

• Hit ratio = Total number of page hits / Total number of references = 5 / 10 = 50%
• Miss ratio = 1 - Hit ratio = 1 - 50% = 50%