lru.cpp

模拟了操作系统的LRU调度算法

/*--------------------------------------------------------------------------
作用:操作系统模拟LRU调叶算法..... 

作者:谢亚龙
创建日期:2008年06月12日
最后修改日期:2008年06月14日

版权信息: xieyalong..Software school of HuNan University ..ChangSha...P.R.C

联系方式:[e-mail] 
--------------------------------------------------------------------------*/
#include "stdafx.h"
#include <iostream>
#include <time.h>
using namespace std;
const int page_size = 20;//假设进程有20个页
const int pagecontrol_size = 5;//假设内存中总共能放5个页

void InitDate(int* page,int page_end,int* pagecontrol,int pagecontrol_end)
{
     //对数据进行初始化....page_end  pageconrol_end分别标志数组的大小
     for(int i = 0;i < page_end;i++)
             page[i] = 0;
     for(int i = 0;i < pagecontrol_end;i++)
             pagecontrol[i] = -1;//-1表示没有被哪个页站用 
}

int HaveFreeSpace(int* pagecontrol,int pc_size)
{
    //从pagecontrol中访问看是否有未占用的内存空间，如果有，则返回可利用下标
    //如果没有，则返回-1
    int i = 0;
    for(;i < pc_size;i++)
            if(pagecontrol[i] == -1)
                              break;
    if(i < pc_size)
         return i;
    else
        return -1;         
}

int ChooseToExchange(int* page,int* pagecontrol,int pc_size)
{
    //选择一个被置换的页，条件是哪个页面是最长时间是没有使用的
    //返回的是pagecontrol中的下标位置，，而page的下标可以通过它找到 
    int min = page[ pagecontrol[0] ]; 
    int min_index = 0;
    for(int i = 1;i < pc_size;i++) 
            if(min > page[ pagecontrol[i] ])
            {
                   min = page[ pagecontrol[i] ];
                   min_index = i;
            }
    return min_index;
}

bool IsInMemory(int* pagecontrol,int pc_size,int value)
{
     //判断value的页是否在内存中
     for(int i = 0;i < pc_size;i++)
             if(pagecontrol[i] == value)
                               return true;
     return false;
} 

void ChangeInformation(int* page,int* pagecontrol,int pc_size,int value)
{
     //value页最近被使用，value的使用值变为10，而其他的页使用信息值减1.。。
     for(int i = 0;i < pc_size && pagecontrol[i] != -1;i++)
             page[ pagecontrol[i] ]--;
     page[value] = 10;       
} 
int _tmain(int argc, _TCHAR* argv[])
{
    int page[page_size];
    int pagecontrol[pagecontrol_size];
    int diseffect = 0;//记录缺页的数量 
    int num;
    cout << "请输入测试序列的个数: ";
    cin >> num;
    int* p_main = new int[num];
    srand(time(NULL));//设定随机数种子
    for(int i = 0;i < num;i++) 
            p_main[i] = rand() % page_size;
    cout << "进程所需的页的顺序为: ";
    for(int i = 0;i < num;i++)
            cout << p_main[i] << " ";
    cout << endl;
    
    InitDate(page,page_size,pagecontrol,pagecontrol_size);//数据初始化 
    for(int i = 0;i < num;i++)//对每个测试数据进行处理
    {
		cout << endl << "处理调页需求--调入 page " << p_main[i] << " -> "; 
        if(IsInMemory(pagecontrol,pagecontrol_size,p_main[i]))//如果这个页在内存中
             cout << "page " << p_main[i] << " 已经在内存中，不需要调用!" << endl; 
        else
        {
             diseffect++;//缺页数加1 
             int index = HaveFreeSpace(pagecontrol,pagecontrol_size);//看是否还有空余空间
             if(index != -1)//如果有，则把当前页调入到内存中就好了
             {
                    pagecontrol[index] = p_main[i];//标志已经进入到内存
                    cout << "有空余内存，装载 page " << p_main[i] << " 到内存中!" << endl; 
             } 
             else//没有可利用的空闲空间，则必须调页 
             {
					index = ChooseToExchange(page,pagecontrol,pagecontrol_size);//得到调换的页 
                    cout << "调页，调出最久没有使用的页 page " << pagecontrol[index] << endl;
                    pagecontrol[index] = p_main[i];//登记到内存使用中 
             }
        }
        //更新page中的最近使用信息
        ChangeInformation(page,pagecontrol,pagecontrol_size,p_main[i]);    
    } 
	printf("错误率:%.3f\n",(float)diseffect/num);
    return 0;
}