操作系统实验-页面置换算法.docx

四种页面置换算法一、实验原理：在内存运行过程中，若其所要访问的页面不在内存而需要把他们调入内存，但内存已经没有空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应将那个页面调出，需根据一定的算法来确定。通常，把选择换出页面的算法成为页面置换算法。置换算法的好坏，将直接影响到系统的性能。一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面置换出，或者把那些在较长时间内不会在访问的页面调出。目前存在着许多种置换算法（如FIFO，OPT，LRU），他们都试图更接近理论上的目标。二、实验目的1通过模拟实现几种基本页面置换的算法，了解虚拟存储技术的特点。2掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想，并至少用三种算法来模拟实现。3通过对几种置换算法页面的比较，来对比他们的优缺点，并通过比较更换频率来对比它们的效率。三、实验分析在进程运行过程中，若其所访问的页面不存在内存而需要把它们调入内存，但内存已无空闲时，为了保证该进程能够正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应调出哪个页面，需根据一定的算法来确定，算法的好坏，直接影响到系统的性能。4、 运行结果 5、 代码#include stdafx.h#define M 3 /物理页数#define N 20/需要调入的页数typedef struct page int num;int time;int temp;Page;/物理页项，包括调入的页号和时间 Page ppM; /M个物理页int queue120, queue220, queue320;/记录置换的页int K = 0, S = 0, T = 0;/置换页数组的标识int pos = 0;/记录存在最长时间项int changenum = 0;int AN;/初始化内存页表项及存储内存情况的空间void INIT()int i;for (i = 0; iM; i+)ppi.num = -1;ppi.time = 0;ppi.temp = 0; /取得内存中存在时间最久的位置int GetMax()int max = -1; int i;for (i = 0; i max)max = ppi.time;pos = i;return pos;/检查最长时间不使用页面 int longestTime(int mxatimep,int temp) int i;int max = -1;for (i = 0; iM; i+)ppi.temp = 0;for (i = temp; i= 1)pp0.time-;elsepp0.temp+;if (pp1.num != Ai)pp1.time+;if (pp1.temp = 1)pp1.time-;elsepp1.temp+;if (pp2.num != Ai)pp2.time+;if (pp2.temp = 1)pp2.time-;elsepp2.temp+;for (i = 0; imax)max = ppi.time;pos = i;return pos;/检查某页是否在内存int Equation(int fold)int i;for (i = 0; iM; i+)if (ppi.num = fold)return i;return -1;/检查物理内存是否已满,-1表满，其他不满int Check()int i;for (i = 0; iM; i+)if (ppi.num = -1)return i;return -1;void FIFO(int fold,int temp)int i;int a, b, c;a = Equation(fold);/页已存在if (a != -1)/页不存在elseb = Check();/内存还有空闲if (b != -1)ppb.num = fold;/内存已满，需要置换else c = GetMax();ppc.num = fold;ppc.time = 0;changenum+;queue1K+ = fold;for (i = 0; iM; i+)if (ppi.num != -1)ppi.time+;void OPT(int fold,int temp)int a, b, c;a = Equation(fold);if (a = -1)/页不在内存b = Check();/内存还有空闲if (b != -1)ppb.num = fold;/内存已满，需要置换elsec = longestTime(fold,temp);ppc.num = fold;ppc.time = 0;changenum+;queue3T+ = fold;void LRU(int fold,int temp)int i;int a, b;int p;a = Equation(fold);if (a != -1)/页已在内存/把此项移动到链表最后一项if (a = 2)/此项已经在最后，不需要做任何改动elsep = Equation(-1);if (p = -1)/链表是满的for (; a2; a+)ppa.num = ppa + 1.num;pp2.num = fold;else if (p = 3)/链表不满for (; ap - 1; a+)ppa.num = ppa + 1.num;ppa.num = fold;elseb = Check();if (b != -1)/不满ppb.num = fold;elsefor (i = 0; i2; i+)ppi.num = ppi + 1.num;pp2.num = fold;changenum+;queue2S+ = fold;int _tmain(int argc, _TCHAR* argv)int BN;int i;INIT();changenum = 0;printf(请依次输入%d个页面号：n, N);for (i = 0; iN; i+)scanf_s(%d, &Ai);/OPTprintf(n);printf(1.最佳置换算法（Opt）n);INIT();changenum = 0;for (i = 0; iN; i+)Bi = Ai;for (i = 0; iN; i+)OPT(Bi, i);printf(n);printf(OPT算法，调入页面顺序为：);for (i = 0; iT; i+)printf(%3d, queue3i);printf(n页面置换次数为：%6dn缺页率：%16.2fnn, changenum, (float)changenum / N);/FIFOprintf(2.先进先出页面置换算法（FIFO)n);INIT();changenum = 0;for (i = 0; iN; i+)Bi = Ai;for (i = 0; iN; i+)FIFO(Bi, i);printf(FIFO算法，调入页面顺序为：);for (i = 0; iK; i+)printf(%3d, queue1i);printf(n页面置换次数为：%6dn缺页率：%16.2fnn, changenum, (float)changenum / N);/LRUprintf(3.最近最久未使用算法（LRU)n);INIT();changenum = 0;for (i = 0; iN; i+)Bi = Ai;for (i = 0; iN; i+)LRU(Bi, i);print