unit1.cpp

请求分页式存储管理 henbucuo de daima

//---------------------------------------------------------------------------

#include <vcl.h>
#pragma hdrstop

#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
	: TForm(Owner)
{
}
//---------------------------------------------------------------------------
const PAGES = 5;
const INSTRUCTIONS = 50;
const PAGE_SIZE = 10;
struct PAGE_TABLE
{       
    int pNum;	//页号
    int mNum;	//物理块号
	bool flag;	//状态位,用于批示该页是否已调入内存
    int aNum;	//访问字段,用于记录本页被访问的次数
    bool modify;	//修改位,表示该页在调入内存后是否被修改过
    int address;	//物理地址    
} page_table[PAGES];

#define MAXQSIZE 5	//最大队列长度,即最大的内存块数加1
typedef struct
{
	int *base;	//初始化的动态分配存储空间
    int front;	//头指针,若队列不空,指向队列头元素
    int rear;	//尾指针,若队列不空,指向队列尾元素的下一个位置
}SqQueue;

SqQueue Q;

struct INSTRUCTION	
{
	int pNum;	//所在页的页号
    int pAddress;	//页内地址
}ins[INSTRUCTIONS];

int lack = 0;
//---------------------------------------------------------------------------
//初始化队列,构造一个空的队列Q
bool InitQueue(SqQueue &Q)
{
	Q.base = (int *) malloc (MAXQSIZE * sizeof(int));
    if(!Q.base) return false;
    Q.front = Q.rear = 0;
    return true;
}
//---------------------------------------------------------------------------
//插入元素e为Q的新的队尾元素
bool EnQueue(SqQueue &Q,int e)
{
	if((Q.rear + 1) % MAXQSIZE == Q.front) return false;
	Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXQSIZE;
    return true;
}
//---------------------------------------------------------------------------
//若队列不空则删除Q的队头元素,用e返回其值
bool DeQueue(SqQueue &Q,int &e)
{
	if(Q.front == Q.rear) return false;
    e = Q.base[Q.front];
    Q.front = (Q.front + 1) % MAXQSIZE;
    return true;
}
//---------------------------------------------------------------------------
void Display(int i,int address)
{
	Form1->Memo1->Lines->Add("指令" + IntToStr(i) + "\t的物理地址为： 0x" + IntToHex(address,8));
}
//---------------------------------------------------------------------------

void run(int a,int m)
{
	int pNum,address = 0,e = 0;
    pNum = ins[m].pNum;
	if(pNum >= PAGES || pNum < 0)
    {
    	MessageBox(NULL,"内存地址越界!","警告",false);
        return;
    }
    //页面已在内存中
    if(page_table[pNum].flag == 1)
    {
    	//如果选择的是LRU算法
    	if(a == 1)
        {
        	int ar[MAXQSIZE] = {-1,-1,-1,-1,-1};
            int last = 0;
            //以下两个for循环实现了将最久未使用的项移到队头
        	for(int i = 0;i < MAXQSIZE && Q.front != Q.rear;i++)
            {//将队列的元素转存到数组,同时找到当前所用到的页面的页号
            	DeQueue(Q,e);
                ar[i] = e;
                if(e == pNum) last = i;
            }
            for(int i = 0;ar[i] != -1;i++)
            {//将数组元素重新按原来顺序放回队列,除了当前所用的页面
            	if(i != last) 
                {
                	EnQueue(Q,ar[i]);
                    ar[i] = -1;
                }
            }
            EnQueue(Q,ar[last]);//将当前所用页面插入队列尾部
        }
    }
    //页面不在内存,缺页中断
    else
    {
    	Form1->Memo1->Lines->Add("缺页中断,请求调入页面：" + IntToStr(pNum));
        lack++;//缺页数加1
        //队列不满,则直接插入队列
        if((Q.rear + 1) % MAXQSIZE != Q.front) EnQueue(Q,pNum);
        else
        {
        	DeQueue(Q,e);
            page_table[e].flag = 0;
            EnQueue(Q,pNum);	
        }
        page_table[pNum].flag = 1;
    }
    page_table[pNum].aNum++;
    //地址转换,物理块号的后16位接页内地址
    address = (page_table[pNum].mNum << 16) + ins[m].pAddress;
    //显示指令的物理地址
    Display(m,address);
}
//---------------------------------------------------------------------------
 
void __fastcall TForm1::Btn_RunClick(TObject *Sender)
{
	int a,m,len,array[INSTRUCTIONS],ins_array[INSTRUCTIONS];
    len = INSTRUCTIONS;
    if(FIFO->Checked) a = 0;
    else if(LRU->Checked) a = 1;
    //初始化页表
    for(int i = 0;i < PAGES;i++)
    {
        page_table[i].pNum = i;
    	for(int j = 0;j < PAGE_SIZE;j++)
        {
        	ins[i * 10 + j].pNum = page_table[i].pNum;
            ins[i * 10 + j].pAddress = + j;
        }
        page_table[i].mNum = i;
        page_table[i].flag = 0;
        page_table[i].aNum = 0;
        page_table[i].modify = 0;
        page_table[i].address = i;
    }
    InitQueue(Q);
    srand((unsigned)time(NULL));//产生随机数的种子
    //以下两个for循环用于产生指令访问的随机序列,存入数组ins_array[]
    for(int i = 0;i < INSTRUCTIONS;i++)
    {
    	array[i] = i;
    }
    for(int n = 0;n < INSTRUCTIONS;n++)
    {
    	if(n == 0) m = random(len);
        else if(n%2 == 0) 
        {
        	if(n/2%2 == 1)m = random(m);
            else m = len - random(len + 1 - m);
        }
        if(m == len) m = 0;
        ins_array[n] = array[m];
        for(int i = m;i < len;i++)
        {
        	array[i] = array[i + 1];
        }
        len--;
    }
    free(array);
    //执行指令序列
    for(int i = 0;i < INSTRUCTIONS;i++)
    {
    	run(a,ins_array[i]);	
    }
    free(ins_array);
    Form1->Memo1->Lines->Add("缺页率:" + FloatToStr((float)lack/(float)PAGES));
}
//---------------------------------------------------------------------------