1, Experimental purpose
1. Understand the characteristics of virtual storage technology, master the basic idea and implementation process of several basic page replacement algorithms in virtual storage request page storage management, and compare their efficiency.
2. Understand programming techniques and the causes of memory leaks
2, Experimental content
1. Simulation of several basic page replacement algorithms for requesting page storage management
(1) Best elimination algorithm (OPT)
(2) First in first out algorithm (FIFO)
(3) Most recently unused algorithm (LRU)
3, Experimental principle
1. Virtual storage system
In UNIX, in order to improve memory utilization, internal and external memory process exchange mechanism is provided; The allocation and recycling of memory space are carried out in pages; A process can run only by calling a part (segment or page) into memory; It also supports the storage management mode of requesting paging.
When a process needs to access some programs and data during operation, if it finds that its page is not in memory, it immediately makes a request (sends a missing interrupt to the CPU) and the system calls its required page into memory. This page transfer in method is called request page transfer.
In order to realize page adjustment request, the core is configured with four data structures: page table, page frame number, access bit, modify bit, valid bit, protection bit, etc.
2. Page replacement algorithm
When the CPU receives the page missing interrupt signal, the interrupt processing program shall first save the site, analyze the interrupt reason, and transfer to the page missing interrupt processing program. The program obtains the physical block number of the external memory where the page is located by looking up the page table. If the memory is not full at this time and can accommodate new pages, start disk I/O, transfer the missing pages into memory, and then modify the page table. If the memory is full, you must select a page from the memory according to a replacement algorithm to replace it. Whether to write to the disk again is determined by the modification bit of the page table, and then transfer the missing page in to modify the page table. Use the modified page table to form the physical address of the data to be accessed, and then access the memory data. The transfer in process of the whole page is transparent to users.
(1) Best elimination algorithm (OPT)
Select a page that will never be used or will not be accessed for the longest time in the future to replace it.
(2) First in first out algorithm (FIFO)
Select the page that has been in memory for the longest time to replace.
(3) Most recently unused algorithm (LRU)
Select the page that has not been accessed for the longest time in the past to replace it.
3. Define and generate instruction sequences
Firstly, srand() and rand() functions are used to define and generate the instruction sequence, then the instruction sequence is transformed into the corresponding page address stream, and the corresponding hit rate is calculated according to different algorithms.
(1) Generate an instruction sequence through random numbers, with a total of 320 instructions. The address of the instruction is generated according to the following principles:
A: 50% of the instructions are executed sequentially
B: 25% of the instructions are evenly distributed in the front address part
C: 25% of the instructions are evenly distributed in the back address part
The specific implementation methods are:
A: Randomly select a starting point m between the instruction addresses of [0319]
B: Execute one instruction in sequence, that is, execute the instruction with address m+1
C: Randomly select an instruction from the previous address [0,m+1] and execute it. The address of the instruction is m '
D: Execute an instruction in sequence with the address m '+ 1
E: Randomly select an instruction from the back address [m '+ 2319] and execute it
F: Repeat steps A-E until 320 commands
(2) Transform an instruction sequence into a page address stream
Set: the page size is 1K;
User memory capacity: 4 pages to 32 pages;
The virtual memory capacity of the user is 32K.
In the user virtual memory, the virtual memory addresses are arranged according to 10 instructions per K, that is, 320 instructions are stored in the virtual memory as follows:
Article 0 - Article 9 instruction is page 0 (the corresponding virtual memory address is [0, 9])
Article 10 - Article 19 instruction is page 1 (the corresponding virtual memory address is [10, 19])
....................................
Article 310 - instruction 319 is page 31 (the corresponding virtual memory address is [310319])
In the above manner, user instructions can form 32 pages.
4, Experimental requirements
1. Draw the flow chart of each page replacement algorithm;
(1) Best elimination algorithm (OPT)
(2) First in first out algorithm (FIFO)
(3) Most recently unused algorithm (LRU)
2. Program code
#include <iostream>
#include <ctime>
#include <vector>
#include <algorithm>
#define N 320 / / number of instructions
int Instructions[N]; //Execution sequence of instructions
int page[N]; //Page number corresponding to the sequence
using namespace std;
void OPT(int index, int *memory, int Max);
void FIFO(int index, int *memory, int Max, int &fistPage);
void LRU(int index, int *memory, int Max);
//findValue() returns the position of the element value in the array arr[start,end] (starting from the left)
int findValue(int arr[], int start, int end, int value)
{
int i = start;
for (; i < end; i++)
if (arr[i] == value)
return i;
return -1;
}
//findValueForR() returns the position of the element value in the array arr[start,end] (starting from the right)
int findValueForR(int arr[], int start, int end, int value)
{
int i = end;
for (; i > start; i--)
if (arr[i] == value)
return i;
return -1;
}
//(1) Optimal elimination algorithm (OPT): select the page that will never be used or will not be accessed for the longest time in the future. Index: the index instruction memory: memory, Max: number of memory blocks
void OPT(int index, int *memory, int Max)
{
int MT_WithoutAccess = -2; //Maximum time without access: the maximum time that a page will never be used or will no longer be accessed in the future
int pageNums = -1; //The location in memory of pages that will never be used or will not be accessed for the longest time in the future
int temp;
for (int i = 0; i < Max; i++)
{
temp = findValue(page, index, N, memory[i]);
if (temp == -1) //Pages never used
{
pageNums = i;
break;
}
else if (temp > MT_WithoutAccess) //Pages that are no longer accessed for the longest time
{
pageNums = i;
MT_WithoutAccess = temp;
}
}
memory[pageNums] = page[index]; //Replace page
}
//(2) First in first out (FIFO): select the page with the longest residence time in memory to replace it. Index: the index instruction memory: memory, fistPage: the first page in memory, Max: the number of memory blocks
void FIFO(int index, int *memory, int Max, int &fistPage)
{
memory[fistPage] = page[index]; //Replace page
fistPage = (fistPage + 1) % Max;
}
//(3) Most recently unused algorithm (LRU): select the page that has not been accessed for the longest time in the past to replace it. Index: the index instruction memory: memory, Max: number of memory blocks
void LRU(int index, int *memory, int Max)
{
int MT_WithoutAccess = 320; //The location of the instruction that has not been accessed for the longest time in the past
int pageNums = -1;
int temp;
for (int i = 0; i < Max; i++)
{ //Find the page in memory that was last used in the page
temp = findValueForR(page, index, N, memory[i]);
if (temp < MT_WithoutAccess)
{
MT_WithoutAccess = temp;
pageNums = i;
}
}
memory[pageNums] = page[index]; //Replace page
}
//Page replacement algorithm
void PageReplacement(int Max) //Max: memory size, that is, the maximum number of pages that can be stored
{
int OPTmemory[Max] = {-1}; //Memory
int FIFOmemory[Max] = {-1};
int LRUmemory[Max] = {-1};
int OPTnums = 0, FIFOnums = 0, LRUnums = 0; //Is the record memory full
int OPTMisspere = 0, FIFOMisspere = 0, LRUMisspere = 0; //Number of missing pages Misspere
int fistPage = 0; //The first page to enter in memory is used for FIFO algorithm
for (int i = 0; i < 320; i++)
{
if (findValue(OPTmemory, 0, Max, page[i]) == -1) //Page missing interrupt
{ //Memory is not full. New pages can be accommodated directly
if (OPTnums < Max)
OPTmemory[OPTnums++] = page[i];
else
{ //Memory is full, replace new page
OPT(i, OPTmemory, Max); //1) Best elimination algorithm (OPT)
OPTMisspere++; //Record the number of missing pages
}
}
if (findValue(FIFOmemory, 0, Max, page[i]) == -1) //Page missing interrupt
{ //Memory is not full. New pages can be accommodated directly
if (FIFOnums < Max)
FIFOmemory[FIFOnums++] = page[i];
else
{ //Memory is full, replace new page
FIFO(i, FIFOmemory, Max, fistPage); //2) First in first out algorithm (FIFO)
FIFOMisspere++;
}
}
if (findValue(LRUmemory, 0, Max, page[i]) == -1) //Page missing interrupt
{ //Memory is not full. New pages can be accommodated directly
if (LRUnums < Max)
LRUmemory[LRUnums++] = page[i];
else
{ //Memory is full, replace new page
LRU(i, LRUmemory, Max); //(3) Most recently unused algorithm (LRU)
LRUMisspere++;
}
}
}
cout << "Optimal elimination algorithm( OPT)Hit rate:" << (320 - Max - OPTMisspere) * 100.0 / 320 << "%" << endl;
cout << "First in first out algorithm( FIFO)Hit rate:" << (320 - Max - FIFOMisspere) * 100.0 / 320 << "%" << endl;
cout << "Most recently unused algorithm( LRU)Hit rate:" << (320 - Max - LRUMisspere) * 100.0 / 320 << "%" << endl;
}
//Generate test data
void init()
{
srand((unsigned)time(NULL));
int i = 0, n, m, x;
bool flag = true;
while (i < 319)
{
m = rand() % 320; //A
Instructions[i] = m;
page[i] = m / 10;
if (i >= 319)
continue;
Instructions[++i] = m + 1; //B
page[i] = (m + 1) / 10;
if (i >= 319)
continue;
n = rand() % (m + 2);
Instructions[++i] = n; //C
page[i] = n / 10;
if (i >= 319)
continue;
Instructions[++i] = n + 1; //D
page[i] = (n + 1) / 10;
while (flag && i < 320)
{
x = rand() % 320;
if (x >= n + 2 && x <= 319)
{
Instructions[++i] = x; //E
page[i] = x / 10;
flag = false;
}
}
}
}
//menu
void show()
{
cout << "***********menu**************" << endl;
cout << "*****************************" << endl;
cout << "****** 1,Clear screen ******" << endl;
cout << "****** 2,memory management ******" << endl;
cout << "****** Any number exit ******" << endl;
cout << "*****************************" << endl;
cout << "*****************************" << endl;
}
int main()
{
while (true)
{
int select;
show();
cout << "Please enter the command!" << endl;
cin >> select;
switch (select)
{
case 1:
{
system("cls");
break;
}
case 2:
{
init();
// int n;
// Cout < < "please enter the memory size!"<< endl;
// cin >> n;
// PageReplacement(n);
srand((unsigned)time(NULL));
for (int i = 4; i < 32; i++)
{
cout << "Number of memory blocks:" << i << endl;
PageReplacement(i);
}
break;
}
default:
system("pause");
return 0;
}
}
};
5, Screen capture and output the experimental results;
Hit rate comparison
