1.- Consider the following page reference string: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1,
ID: 655409 • Letter: 1
Question
1.- Consider the following page reference string:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
How many page faults would occur for the FIFO replacement algorithms, assuming one, five, six, seven frames? Remember that all the frames are initially empty, so your first unique pages will all cost one fault each.
2.- Consider the following page reference string:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
How many page faults would occur for the LRU replacement algorithms, assuming one, five, six, seven frames? Remember that all the frames are initially empty, so your first unique pages will all cost one fault each.
3.- Find the working set (WS) for each locality assuming that the WS is computed each 6 references for the following reference string:
1 3 8 5 9 3 4 3 4 1 3 4 5 6 7 5 6 5 7 8 7 8 7 8 7 9 1 2 5 4
4.- Consider the two-dimensional array A:
int A[][] = new int[100][100];where A[0][0] is at location 200 in a paged memory system with pages of size 200. A small process that manipulates the matrix resides in page 0 (locations 0 to 199). Thus, every instruction fetch will be from page 0. For three page frames, how many page faults are generated by the following array-initialization loops, using LRU replacement and assuming that page frame 1 contains the process and the other two are initially empty?
a. for (int j = 0; j < 100; j++)
for (int i = 0; i < 100; i++)
A[i][j] = 0;
b. for (int i = 0; i < 100; i++)
for (int j = 0; j < 100; j++)
A[i][j] = 0
Explanation / Answer
1-
In LRU : Least Recently Used, so whenever all the three frames are full and we want to access new page, we replace the least recently used page with the required page. So doing this way, for the above given page reference string , hits occured at 2 positions which are bold in the below string.
7 2 3 1 2 5 3 4 6 7 7 1 0 5 4 6 2 3 0 1 . So remainging 18 are page faults.
With LRU replacement and 3 frames:- 7 7,2 7,2,3 1,2,3 1,2,5 1,3,5 4,3,5 4,3,6 4,7,6 1,7,6 1,7,0 1,5,0 4,5,0 4,5,6 4,2,6
3,2,6
3,2,0
3,1,0
Hence, with LRU replacement algorithm 18 page faults would be necessary.
2-
In FIFO : FIrst In First Out, so whenever all the three frames are full and we want to access new page, we replace the page which came First into these frames with the required page. So doing this way, for the above given page reference string , hits occured at 3 positions which are bold in the below string.
b)With FIFO replacement and since we have three frames 7 7,2
7,2,3 <-frames are displayed in fist come to left order 2,3,1 3,1,5 1,5,4 5,4,6 4,6,7 6,7,1 7,1,0 1,0,5 0,5,4 5,4,6 4,6,2 6,2,3 2,3,0
3,0,1
Hence with 3 frames and FIFO replacement with demand paging 16 page faults would occur.
3-
7 2 3 1 2 5 3 4 6 7 7 1 0 5 4 6 2 3 0 1 . So remainging 17 are page faults.
In Optimal : According to this algo, whenever all the three frames are full and we want to access new page, we replace the page which we are going to access last(in the future) with the required page. So doing this way, for the above given page reference string , hits occured at 7 positions which are bold in the below string.
7 2 3 1 2 5 3 4 6 7 7 1 0 5 4 6 2 3 0 1 . So remainging 13 are page faults.
4-
a) There are 50 pages and 100 faults per page.
Hence We have, 50 x 100 = 5000 Page faults.
b) 50 Page faults.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.