

下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、學(xué)習(xí)復(fù)習(xí)#1 操作系統(tǒng)課程設(shè)計報告 課課程程名名稱稱: 操操作作系系統(tǒng)統(tǒng)課課程程設(shè)設(shè)計計 課程設(shè)計題目課程設(shè)計題目: 頁面置換算法頁面置換算法 學(xué)院:學(xué)院: 計算機科學(xué)與技術(shù)學(xué)院計算機科學(xué)與技術(shù)學(xué)院 專專業(yè)業(yè): 科科技技 小小組組成成員員 : : 龐龐思思慧慧 E E0 01 11 11 14 40 08 81 1 王王蒙蒙 E E0 01 11 11 14 41 16 61 1 姚姚慧慧喬喬 E E0 01 11 11 14 43 34 49 9 朱朱潮潮潮潮 E E0 01 11 11 14 44 40 08 8 指導(dǎo)老師:指導(dǎo)老師: 邱劍鋒邱劍鋒 學(xué)習(xí)復(fù)習(xí)#2 目錄目錄 1實驗?zāi)康膶嶒災(zāi)?/p>
2、的 .3 2實驗要求實驗要求 .3 3實驗內(nèi)容與步驟實驗內(nèi)容與步驟 .3 4算法思想算法思想 .4 5模塊設(shè)計模塊設(shè)計 .4 6程序設(shè)計程序設(shè)計 .5 7測試結(jié)果測試結(jié)果 .7 8結(jié)果分析結(jié)果分析 .9 9程序代碼程序代碼 .9 10課程設(shè)計小結(jié)課程設(shè)計小結(jié) .24 學(xué)習(xí)復(fù)習(xí)#3 頁面置換算法模擬設(shè)計頁面置換算法模擬設(shè)計 1.1.實驗?zāi)康膶嶒災(zāi)康?(1)通過模擬實現(xiàn)幾種基本頁面置換的算法,了解虛擬存儲技術(shù)的特點。 (2)掌握虛擬存儲請求頁式存儲管理中幾種基本頁面置換算法的基本思想,并至少用三種 算法來模擬實現(xiàn)。 (3)通過對幾種置換算法命中率的比較,來對比他們的優(yōu)缺點。 2.2.實驗要求實驗要
3、求 計算并輸出下述各種算法在不同內(nèi)存容量下的命中率。 A A 先進先出的算法(FIFO) B B 最近最少使用算法(LRU) C C 最佳淘汰算法(OPT) 3.3.實驗內(nèi)容與步驟實驗內(nèi)容與步驟 (1)通過隨機數(shù)產(chǎn)生一個指令序列,共 320 條指令,具體的實施方法是: A 0,319的指令地址之間隨機選取一起點 M; B 順序執(zhí)行一條指令,即執(zhí)行地址為 M+1 的指令; C 在前地址0,M+1中隨機選取一條指令并執(zhí)行,該指令的地址為 M; D 順序執(zhí)行一條指令,其地址為 M+1; E 在后地址M+2,319中隨機選取一條指令并執(zhí)行; F重復(fù) AE,直到執(zhí)行 320 次指令。 (2)指令序列變換
4、成頁地址流 A.頁面大小為 1K; 學(xué)習(xí)復(fù)習(xí)#4 B.用戶內(nèi)存容量為 4 頁到 32 頁; C.用戶虛存容量為 32K。 在用戶虛存中,按每 K 存放 10 條指令排列虛存地址,即 320 條指令在虛存中的 存放方式為: 第 0 條第 9 條指令為第 0 頁(對應(yīng)虛存地址為0,9) ; 第 10 條第 19 條指令為第 1 頁(對應(yīng)虛存地址為10,19) ; 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 第 310 條第 319 條指令為第 31 頁(對應(yīng)虛存地址為310,319) ; (3)計算并輸出上述各種算法在不同內(nèi)存容量下的命中率。 命中率=1-缺
5、頁次數(shù)/頁地址流長度 4.4.算法思想算法思想 在進程運行過程中,若其所要訪問的頁面不在內(nèi)存而需把它們調(diào)入內(nèi)存,但內(nèi)存已無 空閑空間時,為了保證該進程能正常運行,系統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù),送磁 盤的對換區(qū)中。但應(yīng)將哪 個頁面調(diào)出,須根據(jù)一定的算法來確定。通常,把選擇換出頁面 的算法稱為頁面置換算法。一個好的頁面置換算法,應(yīng)具有較低的頁面更換頻率。從理論 上講,應(yīng)將那些以后不再會訪問的頁面換出,或?qū)⒛切┰谳^長時間內(nèi)不會再訪問的頁面調(diào) 出。 1.先進先出算法 FIFO: 這是最早出現(xiàn)的置換算法。該算法總是淘汰最先進入內(nèi)存的頁面,即選擇在內(nèi)存中駐留 時間最久的頁面予以淘汰。該算法實現(xiàn)簡單只
6、需把一個進程已調(diào)入內(nèi)存的頁面,按先后次 序鏈接成一個隊列,并設(shè)置一個指針,稱為替換指針,使它總是指向最老的頁面。 2.最近最久未使用算法 LRU(least recently used): 算法的基本思想:當需要淘汰某一頁時,選擇離當前時間最近的一段時間內(nèi)最久沒有使用 過的頁先淘汰。該算法的主要出發(fā)點是,如果某頁被訪問了,則它可能馬上還被訪問?;?者反過來說,如果某頁很長時間未被訪問,則它在最近一段時間不會被訪問。 3.最佳淘汰算法 OPT 其所選擇的被淘汰的頁面將是以后永不使用,或許是未來最長時間內(nèi)不使用的頁面,該算 法可保證獲得最低的淘汰率,但在實際運用中無法實現(xiàn),可用來評價其他算法的命中
7、率。 5.5.模塊設(shè)計模塊設(shè)計 學(xué)習(xí)復(fù)習(xí)#5 入口 產(chǎn)生隨機數(shù)、要調(diào)入的頁面、離現(xiàn)在處理時間最長的頁面、 最長的頁面 初始化頁面情況 t1N 根據(jù)選擇的算法進行 置換,缺頁數(shù)加 1 計算缺頁率,并輸出數(shù) 據(jù) 結(jié)束 Y N 直接存入內(nèi)存 開始 輸入內(nèi)存數(shù) 調(diào)用各種置換算法, ,并顯示地址流、 頁面流、頁面置換過程和命中率 命中率比較 結(jié)束結(jié)束 總模塊圖總模塊圖 主程序圖 學(xué)習(xí)復(fù)習(xí)#6 6.6.程序設(shè)計程序設(shè)計 struct Pro /內(nèi)存頁的結(jié)構(gòu)體 int num; /記錄頁面號 int time; /頁面從未被利用的時間 ; #define M 320 /定義指令條數(shù) Pro PM; /產(chǎn)生的
8、隨機指令數(shù)組 void Input() /產(chǎn)生隨機數(shù) int s; /隨機數(shù) int i; srand(time(0); s = rand()%M; /coutn-隨機產(chǎn)生指令流-n; for (i=0; iM; i+=4) /產(chǎn)生指令隊列 pi.num=s; /任選一指令訪問點 m pi+1.num=pi.num+1; /順序執(zhí)行一條指令 pi+2.num=(int)(float)pi.num*(rand()/(RAND_MAX+1.0); /執(zhí)行前地址指令 m pi+3.num=pi+2.num+1; /順序執(zhí)行一條指令 s=(int)(float)(319-pi+2.num)*(rand
9、()/(RAND_MAX+1.0) + pi+2.num; for(i=0;iM;i+) pi.time=0; int Search(int e,Pro*page1,int N) /查找內(nèi)存中是否存在要調(diào)入的頁面 int t; Pro*page=new ProN; page=page1; for(int i=0;iN;i+) t=e/10; if(t=pagei.num) return i; 學(xué)習(xí)復(fù)習(xí)#7 return -1; int Max(Pro*page1,int N)/查找最久最久未被使用的頁面 Pro*page=new ProN; page=page1; int e=page0.ti
10、me,i=0; while(iN) if(epagei.time) e=pagei.time; /找最長時間 i+; for(i=0;iCLOCKFIFO。實際上, 在內(nèi)存頁面數(shù)較少(45 頁面)時,3 種算法的命中率差別不大,可是 50%左右。在內(nèi)存頁 面為 725 個頁面之間時,3 種算法的訪內(nèi)命中率大致在 52%至 87%之間變化。在內(nèi)存頁面 學(xué)習(xí)復(fù)習(xí)#11 為 2532 個頁面時,由于用戶進程的所有指令基本上都已裝入內(nèi)存,從而命中率已較大。 從而算法之間的差別不大。 9.9.程序代碼程序代碼 / 頁面置換算法模擬設(shè)計 Dlg.cpp : implementation file #inc
11、lude stdafx.h #include 頁面置換算法模擬設(shè)計.h #include 頁面置換算法模擬設(shè)計 Dlg.h #ifdef _DEBUG #define new DEBUG_NEW #undef THIS_FILE static char THIS_FILE = _FILE_; #endif / / CMyDlg dialog CMyDlg:CMyDlg(CWnd* pParent /*=NULL*/) : CDialog(CMyDlg:IDD, pParent) /AFX_DATA_INIT(CMyDlg) m_iFifo = 0; N = 0; MZL = 0.0; /AFX
12、_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_EDIT4, m_suiji2); DDX_Control(pDX, IDC_EDIT5, m_yem
13、ian); DDX_Control(pDX, IDC_EDIT3, m_suiji); DDX_Radio(pDX, IDC_RADIO1, m_iFifo); DDX_Text(pDX, IDC_EDIT1, N); DDX_Text(pDX, IDC_EDIT2, MZL); /AFX_DATA_MAP 學(xué)習(xí)復(fù)習(xí)#12 BEGIN_MESSAGE_MAP(CMyDlg, CDialog) /AFX_MSG_MAP(CMyDlg) ON_WM_PAINT() ON_WM_QUERYDRAGICON() ON_BN_CLICKED(IDC_BUTTON1, OnButton1) ON_BN_C
14、LICKED(IDC_RADIO1, OnRadio1) ON_BN_CLICKED(IDC_RADIO2, OnRadio2) ON_BN_CLICKED(IDC_RADIO3, OnRadio3) ON_EN_CHANGE(IDC_EDIT2, OnChangeEdit2) ON_BN_CLICKED(IDC_BUTTON2, OnButton2) ON_BN_CLICKED(IDC_BUTTON3, OnButton3) /AFX_MSG_MAP END_MESSAGE_MAP() / / CMyDlg message handlers BOOL CMyDlg:OnInitDialog(
15、) CDialog:OnInitDialog(); / Set the icon for this dialog. The framework does this automatically / when the applications 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 return TRUE; / return TRUE unless y
16、ou set the focus to a control / 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() 學(xué)習(xí)復(fù)習(xí)#13 CPaintDC dc(this); / d
17、evice 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( int x = (rect.Width() - cxIcon + 1) / 2; int y = (rect.Height() - c
18、yIcon + 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 CMyDlg:OnQueryDragIcon() return (HCURSOR) m_hIcon; #include #include #include #define M 320 int N; struct P
19、ro /內(nèi)存頁的結(jié)構(gòu)體 學(xué)習(xí)復(fù)習(xí)#14 int num,time; ; Pro pM; void Input() /輸入函數(shù),輸入實際頁號和實際頁數(shù) int s; /隨機數(shù) inti; srand(time(0); /每次運行時進程號不同,用來作為初始化隨機數(shù)隊列的種子 s = rand()%M; /coutn-隨機產(chǎn)生指令流-n; for (i=0; iM; i+=4) /產(chǎn)生指令隊列 pi.num=s; /任選一指令訪問點 m pi+1.num=pi.num+1; /順序執(zhí)行一條指令 pi+2.num=(int)(float)pi.num*(rand()/(RAND_MAX+1.0); /
20、執(zhí)行前地址指令 m pi+3.num=pi+2.num+1; /順序執(zhí)行一條指令 s=(int)(float)(319-pi+2.num)*(rand()/(RAND_MAX+1.0) + pi+2.num; for(i=0;iM;i+) pi.time=0; /*p0.num=10;p1.num=22;p2.num=33;p3.num=44;p4.num=50; p5.num=13;p6.num=32;p7.num=22; /測試數(shù) 據(jù) 1,2,3,4,5,1,3,2 fifo 5,1,2,4 LRU 5,1,3,2 opt 置換 1,2,3,5 */ int Search(int e,Pr
21、o*page1,int N) /查找內(nèi)存中是否存在要調(diào)入的頁面 學(xué)習(xí)復(fù)習(xí)#15 int t; Pro*page=new ProN; page=page1; for(int i=0;iN;i+) t=e/10; if(t=pagei.num) return i; return -1; int Max(Pro*page1,int N) /找出離現(xiàn)在時間最長的頁面 Pro*page=new ProN; page=page1; int e=page0.time,i=0; while(iN) if(epagei.time) e=pagei.time; /找最長時間 i+; for(i=0;iN;i+)
22、if(e=pagei.time) return i; /找最長時間的下標 return -1; int Compfu(Pro*page1,int i,int t,Pro pM) /找到最久不使用的頁面 Pro*page=new ProN; page=page1; int count=0; for(int j=i;jM;j+) 學(xué)習(xí)復(fù)習(xí)#16 if(paget.num=pj.num/10) break; /當前頁面開始往后查找在內(nèi)存中的頁幀號 else +count; return count; void CMyDlg:OnButton1() / TODO: Add your control n
23、otification handler code here UpdateData(true); Input(); /地址流 CString str1,tmp1; tmp1=str1=; int k=0,t=0,i=0; for(i=0;iM;i+) tmp1.Format(%-4d,pi.num); str1+=tmp1; k+; if(k%16=0) str1+=nrnrnr; m_suiji.SetWindowText(_T(str1); /頁面流 CString str2,tmp2; tmp2=str2=; for(i=0;iM;i+) tmp2.Format(%-4d,pi.num/1
24、0); str2+=tmp2; k+; if(k%16=0) str2+=nrnrnr; 學(xué)習(xí)復(fù)習(xí)#17 m_suiji2.SetWindowText(_T(str2); Pro*page=new ProN; for(int j=0;jN;j+)/初始化頁面基本情況 pagej.num=-1; pagej.time=j; if(m_iFifo=0)/FIFO 頁面置換 float n=0;/記錄缺頁數(shù) int i=0; CString str3,tmp3; str3=; m_yemian.SetWindowText(_T(str3); while(i=0) +i;/找到相同的頁面 else n
25、+; paget.num=pi.num/10;/如果沒有找到相同的頁,則進行頁面 替換,缺頁數(shù)加一 / tmp3=; m_yemian.GetWindowText(_T(str3); for(int i=0;iN;i+) if(pagei.num=-1) tmp3.Format(%s, ); str3+=tmp3; else tmp3.Format(%-4d,pagei.num); str3+=tmp3; str3+=nrnrnr; 學(xué)習(xí)復(fù)習(xí)#18 m_yemian.SetWindowText(_T(str3); / t=(+t)%N; MZL=1-n/M; if(m_iFifo=1) /LR
26、U 頁面置換 int p2; float n=0;/記錄缺頁數(shù) int i=0; int t1=t=0; CString str3,tmp3; str3=; m_yemian.SetWindowText(_T(str3); while(i=0) pagek.time=0; for(p2=0;p2N;p2+) if(p2!=k) pagep2.time+; else if(t1N) n+; paget.num=pi.num/10;/如果沒有找到相同的頁,則進行 頁面替換,缺頁數(shù)加一 +t1; 學(xué)習(xí)復(fù)習(xí)#19 t+; paget.time=0; / tmp3=; m_yemian.GetWindo
27、wText(_T(str3); for(int i=0;iN;i+) if(pagei.num=-1) tmp3.Format(%s, ); str3+=tmp3; else tmp3.Format(%-4d,pagei.num); str3+=tmp3; str3+=nrnrnr; m_yemian.SetWindowText(_T(str3); / else n+; t=Max(page,N); paget.num=pi.num/10; paget.time=0; / tmp3=; m_yemian.GetWindowText(_T(str3); for(int i=0;iN;i+) if
28、(pagei.num=-1) tmp3.Format(%s, ); str3+=tmp3; else tmp3.Format(%-4d,pagei.num); str3+=tmp3; 學(xué)習(xí)復(fù)習(xí)#20 str3+=nrnrnr; m_yemian.SetWindowText(_T(str3); / for(p2=0;p2N;p2+) if(p2!=t) pagep2.time+; i+; MZL=1-n/M; if(m_iFifo=2)/OPT 頁面置換 int i=0; float n=0;/記錄缺頁數(shù) int t=0,t1=0; CString str3,tmp3; str3=; m_yem
29、ian.SetWindowText(_T(str3); while(i=0)i+; else if(t1N) n+; paget.num=pi.num/10;/如果沒有找到相同的頁,則進行頁面替換,缺頁數(shù)加 1 +t1; t+; i+; / tmp3=; m_yemian.GetWindowText(_T(str3); for(int i=0;i=N) int temp=-1,cn; for(t=0;tN;t+)/查找下次訪問距離最遠的那個頁面 if(tempCompfu(page,i,t,p) temp=Compfu(page,i,t,p);/下次命中經(jīng)歷的頁面計數(shù) cn=t;/最遠的頁面號
30、 pagecn.num=pi.num/10; n+; / tmp3=; m_yemian.GetWindowText(_T(str3); for(int i=0;iN;i+) if(pagei.num=-1) tmp3.Format(%s, ); str3+=tmp3; else tmp3.Format(%-4d,pagei.num); 學(xué)習(xí)復(fù)習(xí)#22 str3+=tmp3; str3+=nrnrnr; m_yemian.SetWindowText(_T(str3); / i+; else break; MZL=1-n/M; UpdateData(false); void CMyDlg:OnR
31、adio1() / TODO: Add your control notification handler code here void CMyDlg:OnRadio2() / TODO: Add your control notification handler code here void CMyDlg:OnRadio3() / TODO: Add your control notification handler code here void CMyDlg:OnChangeEdit2() / TODO: If this is a RICHEDIT control, the control
32、 will not / send this notification unless you override the CDialog:OnInitDialog() / function and call CRichEditCtrl().SetEventMask() / with the ENM_CHANGE flag ORed into the mask. 學(xué)習(xí)復(fù)習(xí)#23 / TODO: Add your control notification handler code here void CMyDlg:OnButton2() / TODO: Add your control notific
33、ation handler code here MessageBox(_T(確認退出?); ExitProcess(0); void CMyDlg:OnButton3() UpdateData(true); Input(); Pro*page=new ProN; for(int j=0;jN;j+)/初始化頁面基本情況 pagej.num=-1; pagej.time=j; int t1=0; int i1=0; float n1=0; float s1,s2,s3; /FIFO 頁面置換 n1=0;/記錄缺頁數(shù) while(i1=0) +i1;/找到相同的頁面 else n1+; paget1.num=pi1.num/10;/
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025至2030商用車項目發(fā)展趨勢分析與未來投資戰(zhàn)略咨詢研究報告
- 2025至2030中國自動販賣機行業(yè)市場深度分析及有效策略與實施路徑評估報告
- 2025至2030中國自動清罐機行業(yè)市場深度研究及發(fā)展前景投資可行性分析報告
- 2025至2030中國自動開縫機行業(yè)發(fā)展趨勢分析與未來投資戰(zhàn)略咨詢研究報告
- 酒店服務(wù)質(zhì)量與經(jīng)營效率提升策略
- 2025至2030中國自體基質(zhì)誘導(dǎo)軟骨形成行業(yè)市場深度研究及發(fā)展前景投資可行性分析報告
- 2025至2030中國腰椎前路椎間融合行業(yè)市場占有率及投資前景評估規(guī)劃報告
- 2025至2030中國脫模膜行業(yè)產(chǎn)業(yè)運行態(tài)勢及投資規(guī)劃深度研究報告
- 2025至2030中國脂肪乳注射液行業(yè)發(fā)展分析及競爭策略與趨勢預(yù)測報告
- 2025至2030中國膠凝纖維敷料行業(yè)產(chǎn)業(yè)運行態(tài)勢及投資規(guī)劃深度研究報告
- 2024屆河北省唐山市玉田縣物理高一第二學(xué)期期末質(zhì)量檢測試題含解析
- 第三方醫(yī)療消毒供應(yīng)中心項目可行性研究報告
- 貨架安裝施工方案
- 美羅培南課件
- 128個常用自然拼讀發(fā)音規(guī)則和1000句生活口語
- 異口同音公開課
- 專利代理人資格考試實務(wù)試題及參考答案
- 運用信息技術(shù)助力勞動教育創(chuàng)新發(fā)展 論文
- GB/T 602-2002化學(xué)試劑雜質(zhì)測定用標準溶液的制備
- GB/T 4074.8-2009繞組線試驗方法第8部分:測定漆包繞組線溫度指數(shù)的試驗方法快速法
- 2023年涉縣水庫投資管理運營有限公司招聘筆試模擬試題及答案解析
評論
0/150
提交評論