LRU Page Replacement Algorithm

Student ID: 1811562126 Name: 潘安

Class: 191c 软工

Experiment task Write a C/C++ program to implement the LRU page replacement algorithm. Input There are two parts in the input. The first part contains two positive integers n and m representing the number of page frames and the length of the reference string. The second part is the following m reference page numbers. Output The output include two parts. The first part contains m lines, and each line has 3 page numbers representing the page loaded into the page frame (Page number "-1" means the page frame is free). The second part is the following one number, namely, the page fault rate. Sample Input (blue) and Output (red) (1) Test 1 38 24320212 2,-1,-1 2,4,-1 2,4,3 2,4,3 2,0,3 2,0,3 2,0,1 2,0,1 0.625

(2) Test 2 4 12 432143543215 4,-1,-1,-1 4,3,-1,-1 4,3,2,-1 4,3,2,1 4,3,2,1 4,3,2,1 4,3,5,1 4,3,5,1 4,3,5,1 4,3,5,2 4,3,1,2 5,3,1,2 0.667

(3) Test 3 4 20 1

70120304230321201701 7,-1,-1,-1 7,0,-1,-1 7,0,1,-1 7,0,1,2 7,0,1,2 3,0,1,2 3,0,1,2 3,0,4,2 3,0,4,2 3,0,4,2 3,0,4,2 3,0,4,2 3,0,4,2 3,0,1,2 3,0,1,2 3,0,1,2 3,0,1,2 7,0,1,2 7,0,1,2 7,0,1,2 0.400

Reference Text book: p213-215, The Least Recently Used (LRU) Page Replacement Algorithm Program source code Please list your program source code here. At least 30% of the source code lines should be annotated. #include /* run this program using the console pauser or add your own getch, system("pause") or input loop */ #include #include #include using namespace std; /* lru Function declaration input parameter description ： pageframeNum：the number of page frames allocated to a process pageCallSequence ： enter the length of page call sequence of the process */ void lru(int pageframeNum, vector &pageCallSequence); int main() { int i, pageFrameNum, n; cin >> pageFrameNum; // enter the number of page boxes allocated to a process cin >> n; //enter the length of page call sequence of the process vector vector pageCallSequence(n); // page call sequence for (i = 0; i < n; i++) 2

{ cin >> pageCallSequence[i]; } lru(pageFrameNum, pageCallSequence); cin>>n; return 0; } struct SPageFrameItem { int pageFrameNr; // page frame number int sequenceNr; // sequence number }; void lru(int pageFrameNum, vector &pageCallSequence) { vector::iterator current, last; vector pageFrameItemVector; pageFrameItemVector.resize(pageFrameNum); int i = 0, j, k, s = 0, sequenceNr = 0; current = pageCallSequence.begin(); last = pageCallSequence.end(); for (j = 0; j < pageFrameNum; j++) { pageFrameItemVector[j].pageFrameNr = -1; } for (; current != last; current++) { if (i < pageFrameNum) // the first pageFrameNum calls the page and there are free physical boxes. { for (j = 0; j < i; j++) { int tmp; tmp = *current; if (pageFrameItemVector[j].pageFrameNr == *current) { s++; // s record the number of successful page visits pageFrameItemVector[j].sequenceNr = sequenceNr++; goto lbNextPageCall; } } pageFrameItemVector[i].pageFrameNr = *current; pageFrameItemVector[i].sequenceNr = sequenceNr++; i++; } else { for (j = 0; j < pageFrameNum; j++) { if (*current == pageFrameItemVector[j].pageFrameNr) { 3

s++; // s Record the number of successful page visits pageFrameItemVector[j].sequenceNr = sequenceNr++; goto lbNextPageCall; } } for (j = 1, k = 0; j < pageFrameNum; j++) // Search the earliest page, k records the frame number of the earliest page { if (pageFrameItemVector[j].sequenceNr < pageFrameItemVector[k].sequenceNr) { k = j; } } pageFrameItemVector[k].pageFrameNr = *current; pageFrameItemVector[k].sequenceNr = sequenceNr++; } lbNextPageCall: for (j = 0; j < pageFrameNum - 1; j++) { cout << pageFrameItemVector[j].pageFrameNr << ","; } cout << pageFrameItemVector[j].pageFrameNr << endl; continue; } int m = (int)pageCallSequence.size(); double f = (m - s) / (double)m; cout.setf(ios::fixed); cout << setprecision(3) << f; }

Program test Please list two sets of test data here. Each set of data include one set of input data and the corresponding output data. You can paste the screenshots of the test results.

(1) Test 1 3 10 3021704602 3,-1,-1 3,0,-1 3,0,2 1,0,2 1,7,2 1,7,0 4,7,0 4,6,0 4,6,0 2,6,0 4

0.900

(2) Test 2 4 10 3027143101 3,-1,-1,-1 3,0,-1,-1 3,0,2,-1 3,0,2,7 1,0,2,7 1,4,2,7 1,4,3,7 1,4,3,7 1,4,3,0 1,4,3,0 0.800

5

(3) Test 3 4 18 51703172015272910503 5,-1,-1,-1 5,1,-1,-1 5,1,7,-1 5,1,7,0 3,1,7,0 3,1,7,0 3,1,7,0 3,1,7,2 0,1,7,2 0,1,7,2 0,1,5,2 0,1,5,2 7,1,5,2 7,1,5,2 7,9,5,2 7,9,1,2 0,9,1,2 0,9,1,5 0.722

6

7