参考链接： Python中的置换和组合
（1）FIFO算法总是选择在内存驻留时间最长的一页将其淘汰。FIFO算法认为调入内存的页不再被可能性要比其他页大，因而选择最先调入内存的页换出。
（2）LRU算法基本思想：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。
（3）OPT算法基本思想：在访问串中将来再也不出现的或是在离当前最远的位置上出现的页。
主要算法实现代码部分在Onqueding（）
Code:
// 置换算法Dlg.cpp : implementation file // #include "stdafx.h" #include "置换算法.h" #include "置换算法Dlg.h" #ifdef _DEBUG #define new DEBUG_NEW #undef THIS_FILE static char THIS_FILE[] = __FILE__; #endif / // CAboutDlg dialog used for App About CRect rectSmall; //收缩 CRect rectLarge; //扩展 CRect rectrang_1; //边缘 bool flag=true; int i,j,k,m; int visit[19]; //访问数组 int *count; //停留标记 int *mem; //内存分配页 int FIFO(int *count_0,int num); int OPT(int *count_0,int i,int num,int *vis); 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() / // CMyDlg dialog CMyDlg::CMyDlg(CWnd* pParent /*=NULL*/) : CDialog(CMyDlg::IDD, pParent) { //{{AFX_DATA_INIT(CMyDlg) m_suanfa = -1; //}}AFX_DATA_INIT // Note that LoadIcon does not require a subsequent DestroyIcon in Win32 m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME); } void CMyDlg::DoDataExchange(CDataExchange* pDX) { CDialog::DoDataExchange(pDX); //{{AFX_DATA_MAP(CMyDlg) DDX_Control(pDX, IDC_rang, m_rang); DDX_Radio(pDX, IDC_RADIO1, m_suanfa); //}}AFX_DATA_MAP } BEGIN_MESSAGE_MAP(CMyDlg, CDialog) //{{AFX_MSG_MAP(CMyDlg) ON_WM_SYSCOMMAND() ON_WM_PAINT() ON_WM_QUERYDRAGICON() ON_WM_MOUSEMOVE() ON_BN_CLICKED(IDC_queding, Onqueding) //}}AFX_MSG_MAP END_MESSAGE_MAP() / // CMyDlg message handlers BOOL CMyDlg::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 /* CRect rect,rect_1; m_rang.GetWindowRect(&rect); GetWindowRect(&rect_1); rect_1.right=rect.right 2; SetWindowPos(NULL,0,0,rect_1.Width(),rect_1.Height(), SWP_NOMOVE | SWP_NOZORDER); */ m_rang.GetWindowRect(&rectrang_1); GetWindowRect(&rectLarge); rectSmall.top=rectLarge.top; rectSmall.left=rectLarge.left; rectSmall.right=rectrang_1.right; rectSmall.bottom=rectLarge.bottom; //默认为FIFO算法 m_suanfa=0; UpdateData(FALSE); return TRUE; // return TRUE unless you set the focus to a control } void CMyDlg::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 CMyDlg::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(); } CDC *pDC = GetWindowDC(); //获取窗口DC CDC *memDC = new CDC; //定义兼容DC // if(flag) // { memDC->CreateCompatibleDC(pDC); //加载位图 CBitmap pBit; pBit.LoadBitmap(IDB_BITMAP1); CBitmap *pOldBit; //选位图进memDC pOldBit=(CBitmap *)memDC->SelectObject(&pBit); CRect rect; CRect rectrang; m_rang.GetWindowRect(&rectrang); GetWindowRect(&rect); rect.right=rectrang.right; BITMAP bitmap; pBit.GetBitmap(&bitmap); //pDC->BitBlt(0,0,rect.Width(),rect.Height(),memDC,0,0,SRCCOPY); pDC->StretchBlt(0,0,rect.Width(),rect.Height(),memDC,0,0,bitmap.bmWidth,bitmap.bmHeight,SRCCOPY); memDC->SelectObject(pOldBit); pDC->SetBkMode(TRANSPARENT); // flag=false; // } } // The system calls this to obtain the cursor to display while the user drags // the minimized window. HCURSOR CMyDlg::OnQueryDragIcon() { return (HCURSOR) m_hIcon; } void CMyDlg::OnMouseMove(UINT nFlags, CPoint point) { // TODO: Add your message handler code here and/or call default if(point.x>= rectSmall.right-10) //扩展 { SetWindowPos(NULL,0,0,rectLarge.Width(),rectLarge.Height(), SWP_NOMOVE | SWP_NOZORDER); if(flag) { this->Invalidate(FALSE); flag=false; //只闪烁一次 } } else //收缩 { SetWindowPos(NULL,0,0,rectSmall.Width(),rectSmall.Height(), SWP_NOMOVE | SWP_NOZORDER); flag=true; } //this->Invalidate(FALSE); CDialog::OnMouseMove(nFlags, point); } void CMyDlg::Onqueding() { UpdateData(); CListCtrl *m_list = new CListCtrl(); m_list->Create(WS_CHILD | WS_VISIBLE |LVS_REPORT,CRect(20,20,545,400),this,102); //改为网状风格 DWORD dwStyle=m_list->GetExtendedStyle(); dwStyle |= LVS_EX_FULLROWSELECT; //整行高亮所选中的行只适用Report Style dwStyle |= LVS_EX_GRIDLINES; //网格线. 只适用Report Style m_list->SetExtendedStyle(dwStyle ); m_list->SetBkColor(RGB(50,200,50));//绿背景色 m_list->SetTextColor(RGB(0,0,220)); //蓝文本色 m_list->SetTextBkColor(RGB(50,200,50)); //绿文本背景色 m_list->InsertColumn(0,"访问序列",LVCFMT_LEFT,75); int m_proc=this->GetDlgItemInt(IDC_COMBO1); //获取组合框文本 int m_mem=this->GetDlgItemInt(IDC_COMBO2); int stay; CString cs; bool flag1=true; if(m_mem) //有值才动态定义 { mem = new int[m_mem]; //内存分配数组 memset(mem,-1,sizeof(int)*m_mem); //初始化为-1 count = new int[m_mem]; //标记驻留次数 memset(count,0,sizeof(int)*m_mem); //初始化为0 } if(m_proc) { for(j=1;j<19;j ) //初始化列 { visit[j]=rand()%m_proc; //访问序列初始化 cs.Format("%d",visit[j]); m_list->InsertColumn(j,cs,LVCFMT_LEFT,25); } } for(k=0;k<m_mem;k ) //初始化行，分配页 { char cha[2]; itoa(k,cha,10); cs="内存第页"; //汉字双字节，注意 cs.Insert(6,cha); m_list->InsertItem(k,cs); } if(m_mem &&m_proc) { for(i=1;i<19;i ) //列 { for(k=0;k<m_mem;k ,i ) //行 { for(j=0;j<m_mem;j ) //找出相等的内存页visit[i]与所有行比较 if(mem[j]==visit[i]) //若相等马上输出所有行 { switch(m_suanfa) { case 1: //FIFO变为LRU只需把逗留数组count置为0就可以了 count[j]=0; //相同的内存页把逗留次数置0 break; } for(m=0;m<m_mem;m ) //输出 { if(mem[m]!=-1) { cs.Format("%d",mem[m]); m_list->SetItemText(m,i,cs); count[m] ; } } k--; flag1=false; break;//找到相等的先输出所有行，，然后跳出 } /// if(flag1) { switch(m_suanfa) { case 0: //FIFO case 1: //LRU if(mem[m_mem-1]!=-1) //内存页满，开始置换 { stay=FIFO(count,m_mem); //谁的逗留时间最长 mem[stay]=visit[i]; //最长的被置换 count[stay]=0; //逗留次数清零 } else //内存页还没用完 { mem[k]=visit[i]; } break; case 2: //OPT if(mem[m_mem-1]!=-1) //内存页满，开始置换 { stay=OPT(mem,i,m_mem,visit); //谁的逗留时间最长 mem[stay]=visit[i]; //最长的被置换 } else //内存页还没用完 { mem[k]=visit[i]; } break; }//switch for(m=0;m<m_mem;m ) //输出所有行 if(mem[m]!=-1) { CString cst; cst.Format("%d",mem[m]); m_list->SetItemText(m,i,cst); count[m] ; //标记停留次数 } } flag1=true; /// }//for(k if(k==m_mem) i--; //有两个i }//for(i delete []count; delete []mem; }//if UpdateData(FALSE); } int FIFO(int *count_0,int num) { int Max=count_0[0]; int Max_stay=0; for(int n=1;n<num;n ) //找出最大数的下标 if(Max < count_0[n]) { Max=count_0[n]; Max_stay=n; } return Max_stay; } int *L; int OPT(int *temp_mem,int i,int num,int *vis) { int Max; int Max_stay; int p=i 1; L = new int[num]; memset(L,0,sizeof(int)*num); //从0开始 for(int n=0;n<num;n ) for(i=p;i<19;i ) //下一个开始比 if(temp_mem[n]!=vis[i]) L[n] ; else break; Max=L[0]; Max_stay=0; for(int h=0;h<num;h ) //找出最大数的下标 { if(Max < L[h]) { Max=L[h]; Max_stay=h; } } delete []L; return Max_stay; }
