lrudlg.cpp

操作系统内存管理的页面置换算法 LRU 同学做的 已试验过

// LRUDlg.cpp : implementation file
//

#include "stdafx.h"
#include "LRU.h"
#include "LRUDlg.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// Dialog Data
	//{{AFX_DATA(CAboutDlg)
	enum { IDD = IDD_ABOUTBOX };
	//}}AFX_DATA

	// ClassWizard generated virtual function overrides
	//{{AFX_VIRTUAL(CAboutDlg)
	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
	//}}AFX_VIRTUAL

// Implementation
protected:
	//{{AFX_MSG(CAboutDlg)
	//}}AFX_MSG
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
	//{{AFX_DATA_INIT(CAboutDlg)
	//}}AFX_DATA_INIT
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAboutDlg)
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
	//{{AFX_MSG_MAP(CAboutDlg)
		// No message handlers
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CLRUDlg dialog

CLRUDlg::CLRUDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CLRUDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CLRUDlg)
	m_NumCache = 3;
	m_NumPage = 12;
	m_rand = _T("");
	m_ChangeNum = 0;
	m_QueNum = 0;
	m_QuePre = 0.0;
	m_ChangePre = 0.0;
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CLRUDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CLRUDlg)
	DDX_Control(pDX, IDC_LIST, m_List);
	DDX_Control(pDX, IDC_SPIN_Page, m_SpinPage);
	DDX_Control(pDX, IDC_SPIN_Cache, m_SpinCache);
	DDX_Text(pDX, IDC_EDIT_Cache, m_NumCache);
	DDX_Text(pDX, IDC_EDIT_Page, m_NumPage);
	DDX_Text(pDX, IDC_EDIT_rand, m_rand);
	DDX_Text(pDX, IDC_CHANG_NUM, m_ChangeNum);
	DDX_Text(pDX, IDC_NUM_QUE, m_QueNum);
	DDX_Text(pDX, IDC_PRE_QUE, m_QuePre);
	DDX_Text(pDX, IDC_CHANGE_PRE, m_ChangePre);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CLRUDlg, CDialog)
	//{{AFX_MSG_MAP(CLRUDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDC_BUTTON_RAND, OnButtonRand)
	ON_BN_CLICKED(IDC_BUTTON_LRU, OnButtonLru)
	ON_BN_CLICKED(IDC_CLEAR, OnClear)
	ON_BN_CLICKED(IDD_ABOUT, OnAbout)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CLRUDlg message handlers

BOOL CLRUDlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// Add "About..." menu item to system menu.

	// IDM_ABOUTBOX must be in the system command range.
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon
	
	// TODO: Add extra initialization here
	m_List.SetHorizontalExtent(1000);

	m_SpinCache.SetRange(1,10);
	m_SpinPage.SetRange(1,50);
	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CLRUDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.

void CLRUDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // device context for painting

		SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

		// Center icon in client rectangle
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// Draw the icon
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();
	}
}

// The system calls this to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CLRUDlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}

void CLRUDlg::OnButtonRand() 
{
	// TODO: Add your control notification handler code here
	CString str1="Page(";
	CString str2="";
	
	UpdateData(true);
	
	if(m_NumCache<=0 || m_NumPage<=0)
	{
		AfxMessageBox("请输入合适的物理块数或页面总数!");
	}
	else if(m_NumCache>m_NumPage)
	{
		AfxMessageBox("访问页面数应不小于物理块数!");
	}
	else if(m_NumCache>10)
	{
		AfxMessageBox("页面总数应不大于10!");
	}
	else if(m_NumPage>50)
	{
		AfxMessageBox("页面总数应不大于40!");
	}
	else
	{
		rands[0]=abs(rand())%m_NumPage+1;
		str2.Format("%d",rands[0]);
		str1+=str2;
		for(int i=1;i<m_NumPage;i++)
		{
			rands[i]=abs(rand())%m_NumPage+1;
			str1+=',';
			str2.Format("%d",rands[i]);
			str1+=str2;
		}
		str1+=')';
		m_rand=str1;
	}
	UpdateData(false);
}

void CLRUDlg::OnButtonLru() 
{
	// TODO: Add your control notification handler code here
	CString str="";
	CString strn="";
	CString str1="";
	CString str2="";
	CString str_info="";
	int q_times=0,z_times=0;									//定义缺页次数，缺页率，置换次数和置换率
	if(m_rand.IsEmpty())
	{
		AfxMessageBox("请生成随机页面序列!");
	}
	else
	{
		UpdateData(true);
		m_List.ResetContent();
		
		for(int ii=0;ii<m_NumCache;ii++)
		{
			cache[ii].mState=false;
			cache[ii].mNumber=-1;
			cache[ii].mTime=0;
		}
		str+="=============欢迎使用LRU页面置换算法==============";
		m_List.InsertString(m_List.GetCount(),str);

		str_info+="访问序列   页面置换形式  ";
		for(int z=1;z<=m_NumCache;z++)
		{
			str_info+="页块";
			strn.Format("%d",z);
			str_info+=strn;
			str_info+="  ";
		}
		str_info+="有无中断 ";
		m_List.InsertString(m_List.GetCount(),str_info);
	
		int i=0;
		while(i<m_NumPage)
		{
			int j=0;
			while(j<m_NumCache)											
			{
				//与Cache块中的页面相同，即命中，不考虑是否要置换
				if(rands[i]==cache[j].mNumber)
				{
					cache[j].mTime=0;										//设置当前的页面在内存中的时间为0
					PageUnusing(j);

					CString ss="";
					ss.Format("%4d",rands[i]);
					str2+=ss;
					str2+="        访问页面    ";	
					for(int k=0;k<m_NumCache;k++)
					{
						if(cache[k].mNumber==-1)							// 内存实页为空
						{
							str2+="       ";
						}
						else
						{
							str1.Format("%4d   ",cache[k].mNumber);
							str2+=str1;
						}
					}
					m_List.InsertString(m_List.GetCount(),str2);			//输出每执行一个页面后物理块的使用情况
					str2="";
									
					i++;
					break;
				}
				
				//Cache有空闲块,不考虑是否要置换，直接调入页面
				if((cache[j].mState==false)&&(rands[i]!=cache[j].mNumber))		
				{
					cache[j].mNumber=rands[i];				//设置当前内存页面状态
					cache[j].mState=true;
					cache[j].mTime=0;
					
					PageUnusing(j);

					CString ss="";
					ss.Format("%4d",rands[i]);
					str2+=ss;
					str2+="        调入页面    ";
					for(int k=0;k<m_NumCache;k++)
					{
						if(cache[k].mNumber==-1)							// 内存实页为空
						{
							str2+="       ";
						}
						else
						{
							str1.Format("%4d   ",cache[k].mNumber);
							str2+=str1;
						}
					}
					str2+="    √   ";
					m_List.InsertString(m_List.GetCount(),str2); //输出每执行一个页面后物理块的使用情况
					str2="";
					
					i++;
					q_times++;
					break;
				}
				j++;
			}
			//Cache块已满，没有与其相同的页面，则考虑置换
			if(j==m_NumCache)
			{
				int minUsing=GetReplacedPage();
				cache[minUsing].mNumber=rands[i];				//置换
				cache[minUsing].mTime=0;
				
				PageUnusing(j);
				
				CString ss="";
				ss.Format("%4d",rands[i]);
				str2+=ss;
				str2+="        置换页面    ";
				for(int k=0;k<m_NumCache;k++)
				{
					if(cache[k].mNumber==-1)							// 内存实页为空
					{
						str2+="      ";
					}
					else
					{
						str1.Format("%4d   ",cache[k].mNumber);
						str2+=str1;
					}
				}
				str2+="    √   ";
				m_List.InsertString(m_List.GetCount(),str2); //输出每执行一个页面后物理块的使用情况
				str2="";

				i++;
				q_times++;
				z_times++;
			
			}
		}
		m_QueNum = q_times;
		m_QuePre = (double)q_times/m_NumPage;
		m_ChangeNum = z_times;
		m_ChangePre = (double)z_times/m_NumPage;
		UpdateData(false);
	}
}
//更新Cache块没被替换的时间mTime加1
void CLRUDlg::PageUnusing(int unUsing)
{

	int k1=0;
	while(k1<m_NumCache)										  //更改其他内存模块的状态
	{
		if(k1!=unUsing&&cache[k1].mNumber!=-1)
		{
			cache[k1].mTime++;
		}
		k1++;
	}
}


//使用LRU算法获得内存中最久未使用的页面 
int CLRUDlg::GetReplacedPage()
{
	
	int k3;												//遍历查找要替换的Cache块号.
	int minUsing=0;
	for(k3=1;k3<m_NumCache;k3++)						
	{
		if(cache[k3].mTime>cache[minUsing].mTime)
		{               
			minUsing=k3;
		}
	}
	return minUsing;
}

void CLRUDlg::OnClear() 
{
	// TODO: Add your control notification handler code here
	m_NumCache=3;
	m_NumPage=12;
	m_rand="";
	m_ChangeNum=0;
	m_ChangePre=0;
	
	m_QueNum=0;
	m_QuePre=0;
	UpdateData(FALSE);
	m_List.ResetContent();

}

void CLRUDlg::OnAbout() 
{
	// TODO: Add your control notification handler code here
	CAboutDlg adlg;
	adlg.DoModal();
}