1, Experimental purpose
One of the main functions of storage management is to allocate space reasonably. Request page management is a common virtual storage management technology. The purpose of this experiment is to understand the characteristics of virtual storage technology and master the page replacement algorithm of request page storage management through the simulation design of page replacement algorithm in request page storage management.
2, Experimental content
1. By calculating the hit rate of different algorithms, the advantages and disadvantages of the algorithms are compared. At the same time, the impact of user memory capacity on hit rate is also considered.
2. The number of page failures is the number of times that the page corresponding to the instruction is not in memory each time the corresponding instruction is accessed.
3. In this experiment, it is assumed that the page size is 1k, the user virtual memory capacity is 32k, and the user memory capacity is 4 to 32 pages.
3, Experimental requirements
1. Calculate and output the hit rate of subordinate algorithms under different memory capacity.
1) First in first out (FIFO);
2) Least recently used algorithm (LRU);
2. address generates a sequence of 320 instructions through random numbers.
The address of the instruction is 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
4, Experimental process
The specific implementation methods are:
1) Randomly select a starting point m between the instruction addresses of [0319];
2) Execute one instruction in sequence, that is, execute the instruction with address m+1;
3) Randomly select an instruction from the previous address [0, m+1] and execute it
Address m1;
4) Execute one instruction in sequence, the instruction with address m1+1
5) Randomly select an instruction from the back address [m1+2319] and execute it;
6) Repeat steps 1) ~ 5) above until 320 instructions are executed
5, Experimental analysis and Implementation
1. Avoid pseudo-random number generation and use c + + time H's Library
#include <time.h>
It is implemented using srand((unsigned)time(NULL)) and rand()
Address::Address()
{
cout<<"Start memory management."<<'\n';
cout<<"Producing address flow, wait for while, please."<<'\n';
int j=0;
flag=true;
srand((unsigned)time(NULL));
/* Generate instruction sequence */
while(j<320)
{
/* Randomly select a starting point m between the instruction addresses of [0319]; */
m=rand()%320;
/* Execute one instruction in sequence, that is, execute the instruction with address m+1 */
order[j]=m+1;
cout<<order[j++]<<'\t';
/* Randomly select an instruction from the previous address [0, m+1] and execute it. The address of the instruction is m1 */
m1=rand()%(m+2);
/* Execute one instruction in sequence, the instruction with address m1+1 */
order[j]=m1+1;
cout<<order[j++]<<'\t';
/* Randomly select an instruction from the back address [m '+ 2319] and execute it */
order[j]=(m1+2)+(rand()%(320-m1-2));
cout<<order[j++]<<'\t';
}
}
2. The implementation of the data structure of the queue uses the template class to implement the queue
linkqueue.h documents:
#include <iostream>
using namespace std;
template <class T>
struct Node
{
T data;
Node<T> *next;
};
template <class T>
class LinkQueue
{
public:
LinkQueue(); /* Constructor to initialize an empty chain queue */
~LinkQueue(); /* Destructor to release the storage space of each node in the chain queue */
void EnQueue(T x); /* Queue element x */
T DeQueue(); /* Remove the team head element from the team */
void DeQueue(T x); /* Remove the team head element from the team */
void SetNullQueue(); /* Queue emptying */
bool Empty(); /* Determine whether the queue is empty */
bool Exist(T x); /* Determine whether this page exists in the queue */
int GetLength(); /* Returns the length of the queue */
// friend void FIFO(); /* First in first out algorithm*/
// friend void LRU(); /* Most recently unused algorithm*/
private:
Node<T> *front, *rear;
int length;/* Calculate queue length */
int m,m1;/* Starting point m,m1 */
int S; /* Algorithm number */
bool flag; /* Judge whether the input algorithm number meets the requirements */
int Msize=2; /* User memory space */
};
template <class T>
LinkQueue<T>::LinkQueue()
{
Node <T> *s;
s=new Node<T>;
s->next=NULL;
front=rear=s;
}
template <class T>
LinkQueue<T>::~LinkQueue()
{
while(front)
{
Node <T> *p;
p=front->next;
delete front;
front=p;
}
}
/* Queue function */
template<class T>
void LinkQueue<T>::EnQueue (T x)
{
Node<T> *s;
s=new Node<T> ; /* Generate node s */
s->data=x;
s->next =NULL;
rear->next=s ; /* Connect node s to the end of the queue */
rear=s ; /* The tail pointer points to the new tail node */
length++;
}
template <class T>
T LinkQueue<T>:: DeQueue ()
{
Node<T>*p;
T x;
if(rear==front)
throw "Underflow";
p=front->next;
x=p->data; /* Temporary queue header element */
front->next=p->next; /* Take off the chain of the node where the team head element is located */
if (p->next==NULL)
rear=front; /* Determine whether the queue length in front of the queue is 1 */
length--;
delete p;
return x;
}
template <class T>
void LinkQueue<T>::DeQueue (T x)
{
Node<T>*p,*s;
if(rear==front)
throw "Underflow";
p=front;
s=front->next;
while(p!=rear)
{
if(s->data==x)
{
p->next=s->next; /* Take off the chain of the node where the element is located */
}
s=s->next;
p=p->next;
}
if (p->next==rear)
rear=front; /* Determine whether the queue length in front of the queue is 1 */
length--;
delete p,s;
}
/* Function to judge whether the chain queue is empty */
template <class T>
bool LinkQueue<T>::Empty()
{
if(front==rear)
return 1;
else
return 0;
}
/* Queue emptying function */
template <class T>
void LinkQueue<T>::SetNullQueue ()
{
rear = front;
}
/* Return queue length */
template <class T>
int LinkQueue<T>::GetLength ()
{
return length;
}
/* Determine whether this page exists in the queue */
template <class T>
bool LinkQueue<T>::Exist(T x)
{
Node<T> *p;
if(rear==front)
throw "Underflow";
p=front->next;
while(p!=rear->next)
{
if(p->data==x)
{
return 1;
}
else
p=p->next;
}
return 0;
}
3. Implement the most recently unused algorithm
Steps:
Determine whether the page is in the physical block of the queue. If it does not exist, first judge whether all 29 physical blocks are occupied. If not, insert this page directly at the back of the queue. If all of them are occupied, remove the queue header element of the advanced queue, and then join the page. The number of missing pages + 1; If it exists, this page will be out of the queue first, then join the queue last, and the most recently unused page will be placed at the head of the queue.
/* Most recently unused algorithm */
void LRU(int order[],int size)
{
int number=0; /* Initialization page missing times */
LinkQueue<int> q;
/* Execute 320 instruction sequences */
for(int i=0;i<size;i++)
{
/* If the queue is empty, put this page in the queue of the physical block */
if(q.Empty())
{
q.EnQueue(order[i]);
number++;
}
else
{
/* Determine whether the page is in the queue physical block
* If not, first judge whether all 29 physical blocks are occupied,
* If it is not fully occupied, insert this page directly at the end of the queue,
* If all are occupied, the queue head element of the advanced queue will be taken out of the queue, and then this page will be put into the queue
* Page missing times + 1;
* If it exists, this page will be out of the queue first, then join the queue last, and the most recently unused page will be placed at the head of the queue*/
if(!q.Exist(order[i]))
{
if(q.GetLength()<=29)
q.EnQueue(order[i]);
else
{
q.DeQueue();
q.EnQueue(order[i]);
}
number++;
}
else if(q.Exist(order[i]))
{
q.DeQueue(order[i]);
q.EnQueue(order[i]);
}
}
}
/* Record hit rate */
double rate=1-number/320.0;
cout<<"LRU Algorithm hit rate: "<<rate<<'\t';
}
6, Problems and corresponding thoughts in the process of experiment
1. How to implement FIFO algorithm?
Solution: use data structure queue
2. The template class instance definition is invalid
Solution: the template class cpp file content added to h file.
Thinking: the implementation of template class can not be compiled separately without specific use; It is also undesirable to separate the declaration from the implementation. All the implementation must be written in the header file. Or use the keyword export in the class definition source file, and then other files only need to include the class definition header file.
3. How to use the existing code (implemented FIFC algorithm) to implement LRU algorithm
Solution: take the recently used pages out of the queue and insert them at the back of the queue. The recently unused pages are at the front of the queue
7, Appendix
address.h Document content:
/* c++Header file */
#include <iostream>
#include <time.h>
using namespace std;
/* Instruction class, generating instruction sequence */
class Address
{
public:
Address();/* Generate instruction sequence */
int Judge(int m);/* Judge whether the input algorithm number is in [1, 4] */
void GetOrder(int a[]);
private:
int m,m1;/* Starting point m,m1 */
int order[320];/* Instruction sequence */
int S; /* Algorithm number */
bool flag; /* Judge whether the input algorithm number meets the requirements */
};
algorithm.h file
/* First in first out algorithm */
void FIFO(int order[],int size);
/* Most recently unused algorithm */
void LRU(int order[],int size);
linkqueue.h File:
#include <iostream>
using namespace std;
template <class T>
struct Node
{
T data;
Node<T> *next;
};
template <class T>
class LinkQueue
{
public:
LinkQueue(); /* Constructor to initialize an empty chain queue */
~LinkQueue(); /* Destructor to release the storage space of each node in the chain queue */
void EnQueue(T x); /* Queue element x */
T DeQueue(); /* Remove the team head element from the team */
void DeQueue(T x); /* Remove the team head element from the team */
void SetNullQueue(); /* Queue emptying */
bool Empty(); /* Determine whether the queue is empty */
bool Exist(T x); /* Determine whether this page exists in the queue */
int GetLength(); /* Returns the length of the queue */
// friend void FIFO(); /* First in first out algorithm*/
// friend void LRU(); /* Most recently unused algorithm*/
private:
Node<T> *front, *rear;
int length;/* Calculate queue length */
int m,m1;/* Starting point m,m1 */
int S; /* Algorithm number */
bool flag; /* Judge whether the input algorithm number meets the requirements */
int Msize=2; /* User memory space */
};
template <class T>
LinkQueue<T>::LinkQueue()
{
Node <T> *s;
s=new Node<T>;
s->next=NULL;
front=rear=s;
}
template <class T>
LinkQueue<T>::~LinkQueue()
{
while(front)
{
Node <T> *p;
p=front->next;
delete front;
front=p;
}
}
/* Queue function */
template<class T>
void LinkQueue<T>::EnQueue (T x)
{
Node<T> *s;
s=new Node<T> ; /* Generate node s */
s->data=x;
s->next =NULL;
rear->next=s ; /* Connect node s to the end of the queue */
rear=s ; /* The tail pointer points to the new tail node */
length++;
}
template <class T>
T LinkQueue<T>:: DeQueue ()
{
Node<T>*p;
T x;
if(rear==front)
throw "Underflow";
p=front->next;
x=p->data; /* Temporary queue header element */
front->next=p->next; /* Take off the chain of the node where the team head element is located */
if (p->next==NULL)
rear=front; /* Determine whether the queue length in front of the queue is 1 */
length--;
delete p;
return x;
}
template <class T>
void LinkQueue<T>::DeQueue (T x)
{
Node<T>*p,*s;
if(rear==front)
throw "Underflow";
p=front;
s=front->next;
while(p!=rear)
{
if(s->data==x)
{
p->next=s->next; /* Take off the chain of the node where the element is located */
}
s=s->next;
p=p->next;
}
if (p->next==rear)
rear=front; /* Determine whether the queue length in front of the queue is 1 */
length--;
delete p,s;
}
/* Function to judge whether the chain queue is empty */
template <class T>
bool LinkQueue<T>::Empty()
{
if(front==rear)
return 1;
else
return 0;
}
/* Queue emptying function */
template <class T>
void LinkQueue<T>::SetNullQueue ()
{
rear = front;
}
/* Return queue length */
template <class T>
int LinkQueue<T>::GetLength ()
{
return length;
}
/* Determine whether this page exists in the queue */
template <class T>
bool LinkQueue<T>::Exist(T x)
{
Node<T> *p;
if(rear==front)
throw "Underflow";
p=front->next;
while(p!=rear->next)
{
if(p->data==x)
{
return 1;
}
else
p=p->next;
}
return 0;
}
address.cpp content
#include "address.h"
Address::Address()
{
cout<<"Start memory management."<<'\n';
cout<<"Producing address flow, wait for while, please."<<'\n';
int j=0;
flag=true;
srand((unsigned)time(NULL));
/* Generate instruction sequence */
while(j<320)
{
/* Randomly select a starting point m between the instruction addresses of [0319]; */
m=rand()%320;
/* Execute one instruction in sequence, that is, execute the instruction with address m+1 */
order[j]=m+1;
cout<<order[j++]<<'\t';
/* Randomly select an instruction from the previous address [0, m+1] and execute it. The address of the instruction is m1 */
m1=rand()%(m+2);
/* Execute one instruction in sequence, the instruction with address m1+1 */
order[j]=m1+1;
cout<<order[j++]<<'\t';
/* Randomly select an instruction from the back address [m '+ 2319] and execute it */
order[j]=(m1+2)+(rand()%(320-m1-2));
cout<<order[j++]<<'\t';
}
}
int Address::Judge(int m)
{
S=m;
/* Judge whether the input algorithm number is in [1, 4] */
switch(S)
{
case 1:
flag=true;
break;
case 2:
flag=true;
break;
case 3:
flag=true;
cout<<"Wait for this algorithm to be written"<<'\n';
break;
case 4:
flag=true;
cout<<"Wait for this algorithm to be written"<<'\n';
break;
default:
cout<<"there is not the algorithm in the program"<<'\n';
flag=false;
}
return flag;
}
void Address::GetOrder(int a[])
{
for(int i=0;i<320;i++)
{
a[i]=order[i];
}
}
algorithm.cpp content
#include "algorithm.h"
#include "linkqueue.h"
/* First in first out algorithm */
void FIFO(int order[],int size)
{
int number=0;
LinkQueue<int> q;
/* Execute 320 instruction sequences */
for(int i=0;i<size;i++)
{
/* If the queue is empty, put this page in the queue of the physical block */
if(q.Empty())
{
q.EnQueue(order[i]);
number++;
}
else
{
/* Determine whether the page is in the queue physical block
* If not, first judge whether all 29 physical blocks are occupied,
* If it is not fully occupied, insert this page directly at the end of the queue,
* If all are occupied, the queue head element of the advanced queue will be taken out of the queue, and then this page will be put into the queue
* Page missing times + 1;
* If so, proceed to the next page*/
if(!q.Exist(order[i]))
{
if(q.GetLength()<=29)
q.EnQueue(order[i]);
else
{
q.DeQueue();
q.EnQueue(order[i]);
}
number++;
}
else if(q.Exist(order[i]))
continue;
}
}
double rate=1-number/320.0;
cout<<"FIFO Algorithm hit rate: "<<rate<<'\t';
}
/* Most recently unused algorithm */
void LRU(int order[],int size)
{
int number=0; /* Initialization page missing times */
LinkQueue<int> q;
/* Execute 320 instruction sequences */
for(int i=0;i<size;i++)
{
/* If the queue is empty, put this page in the queue of the physical block */
if(q.Empty())
{
q.EnQueue(order[i]);
number++;
}
else
{
/* Determine whether the page is in the queue physical block
* If not, first judge whether all 29 physical blocks are occupied,
* If it is not fully occupied, insert this page directly at the end of the queue,
* If all are occupied, the queue head element of the advanced queue will be taken out of the queue, and then this page will be put into the queue
* Page missing times + 1;
* If it exists, this page will be out of the queue first, then join the queue last, and the most recently unused page will be placed at the head of the queue*/
if(!q.Exist(order[i]))
{
if(q.GetLength()<=29)
q.EnQueue(order[i]);
else
{
q.DeQueue();
q.EnQueue(order[i]);
}
number++;
}
else if(q.Exist(order[i]))
{
q.DeQueue(order[i]);
q.EnQueue(order[i]);
}
}
}
/* Record hit rate */
double rate=1-number/320.0;
cout<<"LRU Algorithm hit rate: "<<rate<<'\t';
}
main.cpp content
#include "address.h"
#include "algorithm.h"
#include "linkqueue.h"
int main()
{
int order[320];/* instructions */
int S; /* Algorithm number */
Address ad;
cout<<"There are algorithms in the program"<<'\n';
cout<<"\t1, Optimization algorithm"<<'\n';
cout<<"\t2, Least recently used algorithm"<<'\n';
cout<<"\t3, First in first out algorithm"<<'\n';
cout<<"\t4, Least frequently used algorithm"""<<'\n';
cout<<" Select an algorithm number, please."<<endl;
while(true)
{
cin>>S;
if(ad.Judge(S))
{
break;
}
}
ad.GetOrder(order);
/* Judge whether the input algorithm number is in [1, 4] */
switch(S)
{
case 1:
cout<<"1";
FIFO(order,320);
break;
case 2:
cout<<"2";
LRU(order,320);
break;
case 3:
cout<<"3";
break;
case 4:
cout<<"4";
break;
default:
cout<<"there is not the algorithm in the program"<<'\n';
}
}