This article shares the specific code of C language to implement page permutation algorithm for your reference. The specific content is as follows
1. Design Purpose
Deepen the understanding of the implementation principles of request page storage management and master the first-in-first-out algorithm in the page permutation algorithm.
2. Design content
Design a program with a virtual memory area and a memory work area, implement any two of the following three algorithms, and calculate the access hit rate (hit rate = 1 - page failure times/page address stream length). Additional requirements: Ability to display the page replacement process.
The length of the page address stream of the system is 320, and the number of page failures is the number of times the page corresponding to the instruction is not in memory each time the corresponding instruction is accessed.
The program first uses the srand() and rand() functions to initialize, define random numbers and generate instruction sequences respectively, then converts the instruction sequence into the corresponding page address stream, and calculates the corresponding hit rate for different algorithms.
A sequence of instructions is generated by random numbers. There are 320 instructions in total, and the addresses of the instructions are generated according to the following principles:
(1) 50% of the instructions are executed sequentially.
(2) 25% of the instructions are evenly distributed in the front address part.
(3) 25% of the instructions are evenly distributed in the back address part.
The specific implementation methods are as follows:
Randomly select the point m between the instruction addresses of [0,319].
Execute one instruction in sequence, that is, execute the instruction with the address m+1.
In the previous address [0,m+1], a random instruction is selected and executed, and the address of the instruction is m'.
Execute an instruction in sequence with the address m'+1.
Randomly select an instruction in the latter address [m'+2,319] and execute it.
Repeat steps (1)-(5) until 320 commands.
Convert the instruction sequence into a page address stream.
set up:
The page size is 1KB.
User memory capacity is 4 pages to 32 pages.
The user's virtual memory capacity is 32KB.
In user virtual memory, 10 instructions are stored in virtual memory per K, that is, the storage method of 320 instructions in virtual memory is:
Article 0 to 9 are page 0 (corresponding to virtual storage address [0, 9]).
Instructions 10 to 19 are page 1 (corresponding to virtual storage addresses [10, 19]).
……
Instructions 310 to 319 are page 31 (corresponding to virtual addresses are [310, 319]).
According to the above method, user instructions can form 32 pages.
Calculate the hit rate of each algorithm at different memory capacity.
III. Program structure
First, use the srand() and rand() functions to initialize, define random numbers and generate instruction sequences respectively;
Next, convert the instruction sequence into the corresponding page address stream;
Then, the first-in-first-out algorithm calculates the corresponding hit rate and output page replacement process.
Source program:
#include<>
#include<>
#define N 320
int num[N]; //Storage random numbersint page[N]; //Storage page address streamint mc[33]; //memory capacity memory capacity and initialize to 0
void randomnumber()//random number random number The first step of the program is to generate 320 instruction sequences{
int pc;
int flag=0;
scanf("%d",&pc);
printf("\nThe 320 random numbers generated between 0-319 are as follows:\n");
for(int i=0;i<320;i++)
{
num[i]=pc;
if(flag%2==0) pc=++pc%320; //flag=0||2 50% of the instructions are executed sequentially if(flag==1) pc=rand()% (pc-1); //flag=1 25% of the instructions are evenly distributed in the front address part if(flag==3) pc=pc+1+(rand()%(320-(pc+1))); //flag=3 25% of the instructions are evenly distributed in the back address part flag=++flag%4;
printf("%3d ",num[i]);
if((i+1)%10==0) printf("\n"); //Only output 10 numbers per line }
}
void pageaddress() //pageaddress page address The second step of the program is to convert the instruction sequence into a page address stream{
for(int i=0;i<320;i++)
{
printf("%3d ",page[i]=num[i]/10);
if((i+1)%10==0) printf("\n"); //Only output 10 numbers per line }
}
int FIFO(int capacity)
{
int j,x,y,m;
int sum=0; //The number of allocated in mc int exist=0; //Number of hits int flag; //The flag is hit flag=0 failed flag=1 hit int ep=1; //elimination position mc[1]=page[0];
printf(" %2d join \t",page[0]);
for(m=1;m<=capacity;m++) //Output the current memory block storage status printf("%2d ",mc[m]);
printf("\n");
sum+=1;
for(j=1;j<320;j++)
{
flag=0;
for(y=1;y<=sum;y++) //Judge whether the page address stream hits if(mc[y]==page[j]) {
exist++;
flag=1;
printf("%2d hit \t",page[j]);
for(m=1;m<=capacity;m++) //Output the current memory block storage status printf("%2d ",mc[m]);
printf("\n");
break;}
//Impossible if(flag==0)
{
if(sum<capacity) //There are still free blocks {for(x=1;x<=capacity;x++) //Find the first empty block in the memory block if(mc[x]==-1) {
mc[x]=page[j];
sum++;
printf(" %2d join \t",page[j]);
for(m=1;m<=capacity;m++) //Output the current memory block storage status printf("%2d ",mc[m]);
printf("\n");
break;}
}
else if(sum>=capacity)
{
int t=mc[ep];
mc[ep]=page[j];
printf("%2d replace %2d\t",page[j],t);
for(m=1;m<=capacity;m++) //Output the current memory block storage status printf("%2d ",mc[m]);
printf("\n");
ep+=1;
if(ep==capacity+1) ep=1;
}
}
}
printf("\nexist=%d\nHit rate=%lf",exist,exist/320.0);
}
int main()
{
int capacity; //Number of memory blocks printf("Please enter the first command number(0~319):");
randomnumber();
printf("\nThe page address stream corresponding to the instruction sequence:\n");
pageaddress();
printf("\n\n\n\t\tFirst-in-first-out algorithm(FIFO):\n\n");
printf("Please enter the number of memory blocks (4-32):");
scanf("%d",&capacity);
for(int i=1;i<=32;i++) // Assign initial value to the array mc[i]=-1;
FIFO(capacity);
return 0;
}
The above is all the content of this article. I hope it will be helpful to everyone's study and I hope everyone will support me more.