Leeyuxun の note

BUPT | SCSS

操作系统内核-实验三

发表于 更新于 分类于

实验目的

  1. 理解内存页面调度的机理；
  2. 掌握几种理论调度算法实现；
  3. 通过实验比较各种调度算法的优劣；
  4. 通过实验了解HASH表数据结构的使用；

准备知识

  1. C++、指针和结构体(类)

  2. 哈希表查找方式

  3. 操作系统内存交换的知识

  4. 可能用到的几个函数

    1
    2
    3
    int getpid ()		//获得当前进程的pid
    void srand (int a)	//以a为种子产生随机数
    int rand ()			//根据前面的种子，返回一个随机数

实验内容

对比以下几种页面置换算法的命中率

  1. 先进先出的算法FIFO(First In First Out)
  2. 最近最少使用的算法LRU(Least Recently Used)
  3. 最近未使用算法NUR(Never Recently Used)
  4. 最佳置换算法OPT(Optimal Replacement)

页面置换算法介绍

FIFO页面置换算法

原理简述

  1. 在分配内存页面数(AP)小于进程页面数(PP)时，最先的AP个页面放入内存；
  2. 需要处理新页面时，将原来在内存中的AP个页面中最先进入的调出，放入新的页面；
  3. 算法特点：使用内存页面构成一个队列；

图表描述

  • 假设某个进程在硬盘上被划分为5个页面(PP=5)，以1、2、3、4、5分别表示，处理机调用它们的顺序为：1、4、2、5、3、3、2、4、2、5；

  • 假设内存控制的页面数为3(AP=3)，那么在FIFO算法时，这3个页面的内存使用情况如下图所示

    1571155503183

  • 共换入页面8次，diseffect=8；

算法实现

  • 要得到命中率，必然要有一个常量total_instruction记录页面总共使用次数；此外需要一个变量记录总共换入页面的次数(需要换出页面，总是因为没有命中而产生的)diseffect，可利用公式得到命中率(公式如下)。

    1. 初始化，设置两个数组page[ap]和pagecontrol[pp]分别表示进程页面数和内存分配的页面数，并产生一个的随机数序列main[total_instruction](当然这个序列由page[]的下标随机构成)，表示待处理的进程页面顺序，diseffect置0；

    2. 看main[]中是否有下一个元素，有就由main[]中获取该页面下标，并转到步骤3；若没有，就转到步骤7；

    3. 如果该page页已在内存中，就转到步骤2；否则就到步骤4，同时未命中的diseffect加1；

    4. 观察pagecontrol是否占满，如果占满需将使用队列(步骤六中建立的)中最先进入的(就是队列第一个单元)pagecontrol单元“清干净”，同时将对应的page[]单元置为“不在内存中”。

    5. 将该page[]与pagecontrol[]建立关系(可以改变pagecontrol[]的标示位，也可以采用指针连接。总之，至少要使对应的pagecontrol单元包含两个信息：一是它被使用了，二是哪个page[]单元使用的；page[]单元包含两个信息：对应的pagecontrol单元号、本page[]单元已在内存中)；

    6. 将用到的pagecontrol置入使用队列(这里的队列当然是一种先进先出的数据结构)，返回步骤2；

    7. 显示命中率(命中率公式如下) ，算法完成。
      $$
      hit_-rate=1-\frac{diseffect}{total_-instruction}\times100%
      $$

LRU页面置换算法

原理简述

  1. 在分配内存页面数(AP)小于进程页面数(PP)时，最先的AP个页面放入内存；
  2. 当需要调入页面进入内，而当前分配的内存页面不空闲时，选择其中最长时间没有用的那个页面调出，以控制内存来放置新调入的页面；
  3. 算法特点：每个页面都有属性表示有多长时间未被CPU使用的信息；

图表描述

  • 假设某个进程与内存可控制页面数不变：AP=3，PP=5；

  • 处理机调用它们的顺序不变：1、4、2、5、3、3、2、4、2、5

  • 使用LRU算法时，这3个页面的内存使用情况如下图所示

    1571062544372

  • 共换入页面7次，diseffect=7；

算法实现

  • 和FIFO算法相同，只有先得到diseffect才能获得最终“命中率”；
    1. 初始化，主要是进程页面page[]和分配的内存页面pagecontrol[]，同时产生随机序列main[]，diseffect置0；
    2. 看序列main[]是否有下一个元素，有就由main[]中获取该页面下标，并转到步骤3；若没有，就转到步骤6；
    3. 如果该page页已在内存中，便改变页面属性，使它保留“最近使用”的信息，转到步骤2；否则就到步骤4，同时未命中的diseffect加1；
    4. 判断是否有空闲的内存页面，如果有，就返回页指针，转到步骤5；否则在内存页面中找出最长时间没有使用到的页面，将其“清干净”，并返回该页面指针；
    5. 在需要处理的page[]与步骤4中得到的pagecontrol[]建立关系，同时让对应的page[]单元保存“最新使用”的信息，返回步骤2；
    6. 如果序列处理完成，就输出命中率(命中率公式同上)，算法结束。

NUR页面置换算法

原理简述

  • 所谓的“最近未使用”首先要对“近”做一个界定，比如CLEAR_PERIOD=50，便是在CPU最近执行的50次进程页面处理工作中，找出这50次都没有处理的页面；
    1. 如果这样的页面只有一个，就将其换出，放入需处理的新页面；
    2. 如果有不止一个这样的页面，在这些页面中任取出一个换出，放入需处理的页面；
    3. 如果没有这样的页面，则随意换出一个页面(页码可以最大也可以最小)；
  • 算法特点：有一个循环周期，每达到这个周期，所有页面存放是否被CPU处理信息的属性均被置于初始态；

图表描述

  • 假设某个进程与内存可控制页面数不变：AP=3，PP=5；

  • 处理机调用它们的顺序不变：1、4、2、5、3、3、2、4、2、5；

  • 使用NUR算法时，这3个页面的内存使用情况如下图所示；

    1571157657346

算法实现

需要对数组设置“访问位”标识；

  1. 初始化，设置两个数组page[ap]和pagecontrol[pp]分别表示进程页面数和内存分配的页面数，并产生一个的随机数序列main[total_instruction]（当然这个序列由page[]的下标随机构成），表示待处理的进程页面顺序，diseffect置0，设定循环周期CLEAR_PERIOD；
  2. 看main[]中是否有下一个元素，有就从main[]中获得一个CPU将处理页面的序号；没有，就转到步骤8；
  3. 如果待处理的页面已在内存中，就转到步骤2；否则diseffect加1，并转到步骤4；
  4. 看是否有空闲的内存页面，如果有，返回空闲页面指针，转到步骤5；否则，在所有没有被访问且位于内存中的页面中按任意规则（或者取最近的一个页面；或者取下标最小的页面，等等）取出一个，返回清空后的内存页面指针；
  5. 在待处理进程页面与内存页面之间建立联系，并标注该页面被访问；
  6. 如果CPU已处理了CLEAR_PERIOD个页面，就将所有页面均设为“未访问”；
  7. 返回步骤2；
  8. 如果CPU所有处理工作完成，就返回命中率的结果，算法结束。

OPT页面置换算法

原理简述

在分配的内存页面占满的情况下，最佳置换算法是一种理想状况下的算法，他要求先遍历所有的CPU待处理的进程页面序列（实际上，由于待处理的页面有取决于先前处理的页面，所有很多情况下不可能得到完整的待处理页面序列。在这个层面上，才说该算法足理想的。)，在这些页面中，如果有已经在内存当中，而不再处理的，就将其换出：如果页面在内存中，并待处理，就取从当前位置算起，最后处理到的页面，将其换出。比如待处理的页面序列号为：

1571070639492

已经处理了5个页面，那么页面5是第一个待处理的页面：2是第二个；1是第四个；4是第五个；3是第六个。那么页面3就是针对当前位置而言，最后处理到的页面。

图表描述

  • 假设某个进程与内存可控制页面数不变：AP=3，PP=5；

  • 处理机调用它们的顺序不变：1、4、2、5、3、3、2、4、2、5

  • 使用OPT算法时，这3个页面的内存使用情况如下图所示；

    1571190143264

  • 一共发生了6次页面交换，diseffect=6；

算法实现

  1. 初始化，设置两个数组page[ap]和pagecontrol[pp]分别表示进程页面数和内存分配的页面数，并产生一个的随机数序列main[total_instruction]（当然这个序列由page[]的下标随机构成），表示待处理的进程页面顺序，diseffect置0，然后扫描整个页面访问序列,对vDistance[TOTAL_VP]数组进行赋值，表示该页面将在第几步被处理；
  2. 看main[]中是否有下一个元素，有就从main[]中获取一个CPU待处理的页面号；没有，就转到步骤6；
  3. 如果该page页已在内存中，就转到步骤2；否则就到步骤4，同时未命中的diseffect加1；
  4. 看是否有空闲的内存页面，如果有，就直接返回该页面指针；如果没有，遍历所有未处理的进程页面序列，如果有位于内存中的页面，而以后CPU不再处理，首先将其换出，返回页面指针；如果没有这样的页面，找出CPU最晚处理到的页面，将其换出，返回该内存页面指针；
  5. 在内存页面和待处理的进程页面之间建立联系，返回步骤2；
  6. 输出命中率，算法结束。（命中率在扫描时完成计算）

数据结构

数据结构的详细分析在注释中已经标注；

CPage类

1
2
3
4
5
6
7
class CPage{	//进程使用的页面
	public:
		int m_nPageNumber;		//页号 
		int	m_nPageFaceNumber;	//对应的物理内存页号，初始为INVALID 
		int	m_nCounter;			//计数 
		int	m_nTime;			//时间信息 
};

CPageControl类

1
2
3
4
5
6
class CPageControl{		//分配给进程的物理内存页面
	public:
		int m_nPageNumber;				//表示物理内存页号（帧号） 
		int m_nPageFaceNumber;			//表示物理内存的页号
		class CPageControl * m_pNext;	//指示下一个页面
};

CMemory类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class CMemory{
	public:
		CMemory();	//构造函数，用来初始化变量
    	//参数nTotal_pf表示分配的内存页面个数
		void initialize(const int nTotal_pf);	//初始化函数
		void FIFO(const int nTotal_pf);
		void LRU(const int nTotal_pf);
		void NUR(const int nTotal_pf);
		void OPT(const int nTotal_pf);

	private:
		vector<CPage> _vDiscPages;//进程使用的页向量,包含该进程空间内的所有页 
		vector<CPageControl> _vMemoryPages;	//为进程分配的物理内存页向量
		CPageControl *_pFreepf_head;	//空闲物理页头指针，用于LRU算法 
		CPageControl *_pBusypf_head;	//已使用页面头指针，用于FIFO算法
    	CPageControl *_pBusypf_tail;	//已使用页面尾指针，用于FIFO算法
		vector<int> _vMain;		//_vMain表示某进程随机产生的指令序列
    	vector<int> _vPage;		//_vPage表示待处理指令对应的页号 
    	vector<int> _vOffset;	//_vOffset表示剩余待处理的指令数
		int _nDiseffect;	//换入页面次数，即未命中次数 
};

CMemory类的构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
CMemory::CMemory():		//构造函数
    _vDiscPages(TOTAL_VP),
	_vMemoryPages(TOTAL_VP),
	_vMain(TOTAL_INSTRUCTION),
	_vPage(TOTAL_INSTRUCTION),
	_vOffset(TOTAL_INSTRUCTION) {
		int S,i,nRand;
		/*
			通过随机数产生一个指令序列(实际上是指令的逻辑地址序列)，共320条指令。
			指令的地址按下述原则生成：
				A：50%的指令是顺序执行的
				B：25%的指令要实现向前跳转，均匀分布在前地址部分
				C：25%的指令要实现向后跳转，均匀分布在后地址部分
			函数void srand(unsigned seed)；参数seed是rand()的种子，
			用来初始化rand()的起始值。
			由于每次运行时进程号不同，故可用来作为初始化随机数队列的“种子”
		*/ 
		srand(getpid()*10);
        /* 	函数int rand(void)；从srand (seed)中指定的seed开始，
        	返回一个[seed,RAND_MAX（32767）)间的随机整数。 */
		nRand=rand()%32767; 
		S=(float)319*nRand/32767+1;		//计算第一条指令的地址S 
		for(i=0;i<TOTAL_INSTRUCTION;i+=4)
		{
			_vMain[i]=S;	//地址S存入_Main[i]
			_vMain[i+1]=_vMain[i]+1;	//顺序执行S的下一条指令 
            /* 计算S的一条任意的前地址指令的地址S'属于[0，S+1],
            并存入_Main[i+2],表示向前跳转 */
			nRand=rand()%32767;
			_vMain[i+2]=(float)_vMain[i]*nRand/32767;
			_vMain[i+3]=_vMain[i+2]+1;	//顺序执行S'下一条指令 
            /* 计算S'的一条任意的后指令地址S属于[S'+1,319],表示向后跳转 */
			nRand=rand()%32767; 
			S=(float)nRand*(318-_vMain[i+2])/32767+_vMain[i+2]+2;
		}
		/*
			将指令序列变成页地址流
			页面大小为1K；
			用户内存容量4页到32页；
			用户虚存容量为32K.
			在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：
			第0 条-第9 条指令为第0页（对应逻辑地址为[0，9]）
			第10条-第19条指令为第1页（对应逻辑地址为[10，19]）
				………………………………
			第310条-第319条指令为第31页（对应逻辑地址为[310，319]）
			按以上方式，用户指令可组成32页。
		*/ 
		for(i=0;i<TOTAL_INSTRUCTION;i++)
		{
			_vPage[i]=_vMain[i]/10;
			_vOffset[i]=_vMain[i]%10;
			_vPage[i]%=32;
		}
	}

类成员函数initialize(const int nTotal_pf)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void CMemory::initialize(const int nTotal_pf)
{	//初始化函数，参数表示分配的内存页面个数
	int ix;				//辅助变量，用于计数
	_nDiseffect=0;		//换入页面次数置零
	for(ix=0;ix<_vDiscPages.size();ix++)		//初始化进程使用的页向量
	{
		_vDiscPages[ix].m_nPageNumber=ix;
		_vDiscPages[ix].m_nPageFaceNumber=INVALID;
		_vDiscPages[ix].m_nCounter=0;
		_vDiscPages[ix].m_nTime=-1;
	}
	for(ix=1;ix<nTotal_pf;ix++)			//初始化为进程分配的物理内存页向量
	{
		_vMemoryPages[ix-1].m_pNext=&_vMemoryPages[ix];
		_vMemoryPages[ix-1].m_nPageFaceNumber=ix-1;
	}
	_vMemoryPages[nTotal_pf-1].m_pNext=NULL;
	_vMemoryPages[nTotal_pf-1].m_nPageFaceNumber=nTotal_pf-1;
	_pFreepf_head=&_vMemoryPages[0];	//初始化空闲物理页头指针
}

类成员函数FIFO(const int nTotal_pf)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
void CMemory::FIFO(const int nTotal_pf)
{
	int i;	//辅助变量，用于计数
	CPageControl *p;	//辅助变量，用于中间过渡
	initialize(nTotal_pf);	//初始化
	_pBusypf_head=_pBusypf_tail=NULL;	//将已使用页面的头指针和尾指针置空
	for(i=0;i<TOTAL_INSTRUCTION;i++)
	{
		if(_vDiscPages[_vPage[i]].m_nPageFaceNumber==INVALID)
		{	//如果页面页号不在物理内存中
			_nDiseffect+=1;
			if(_pFreepf_head==NULL)  //如果分配给进程的物理内存页面无空闲 
			{
				/* 将队列中最先进入的(就是队列第一个单元)pagecontrol单元“清干净”*/ 
				p=_pBusypf_head->m_pNext;
                //将p指向已使用头指针指向的页面的下一个页面，即第二个已使用的页面 
				_vDiscPages[_pBusypf_head->m_nPageNumber].
                    m_nPageFaceNumber=INVALID;
                //将已使用页面头指针指向的内存单元清理干净 
				_pFreepf_head=_pBusypf_head;//将已使用页面头指针置为空闲页面头指针 
				_pFreepf_head->m_pNext=NULL;//将空闲页面头指针的下一个指针置空 
				_pBusypf_head=p;//将已使用页面头指针指向下一个页面 
			}
			/* 将待处理指令对应的页面调入内存 */ 
			p=_pFreepf_head->m_pNext;	//将p指向空闲头指针的指向的页面的下一个页面 
			_pFreepf_head->m_pNext=NULL;	//将空闲头指针指向页面的下一个页面置空 
			_pFreepf_head->m_nPageNumber=_vPage[i];	
            //将待处理指令对应的页号放入空闲头指针指向的页面的页号中 
			_vDiscPages[_vPage[i]].m_nPageFaceNumber=_pFreepf_head->m_nPageFaceNumber;
            //将进程页向量的页号置为待处理指令对应的页号 
			if(_pBusypf_tail==NULL)	
			{	//如果已使用页面尾指针为空，即在此之前内存没有被占用 
				_pBusypf_head=_pBusypf_tail=_pFreepf_head; 	
                //将已使用页面的头指针、尾指针都指向的页面即待处理指令 
			} 
			else{		//如果已使用页面尾指针不为空，即在此之前已经有页面放入内存中 
				_pBusypf_tail->m_pNext=_pFreepf_head;
                //已使用页面的尾指针的下一个指针指向空闲页面头指针指向的页面 
				_pBusypf_tail=_pFreepf_head;
                //已使用页面的尾指针指向空闲页面头指针指向的页面 
			}
			_pFreepf_head=p;//将空闲页面的头指针指向下一个页面 
	    }
	}
 	cout<<"FIFO: "<<fixed<<setprecision(6)<<1-(float)_nDiseffect/320<<"\t";	
    //打印出命中率 
}

类成员函数LRU(const int nTotal_pf)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
void CMemory::LRU(const int nTotal_pf)
{
	int i,j,nMin,minj,nPresentTime(0);	//辅助变量，用于计数和作为中间变量过渡 
	initialize(nTotal_pf);	//初始化 
	for(i=0;i<TOTAL_INSTRUCTION;i++)
	{
		if(_vDiscPages[_vPage[i]].m_nPageFaceNumber==INVALID)
		{	//如果页面页号不在物理内存中
			_nDiseffect++;
			/* 寻找最近最少使用的页面并将其调出内存 */ 
			if(_pFreepf_head==NULL)	//如果分配给进程的物理内存页面无空闲
			{
    			nMin=32767;
    			/*
					循环结束后，得到最近最少使用的页面的页号,
					nMin表示最近最少使用页面的访问次数;
					minj表示需要换出的页号
				*/ 
				for(j=0;j<TOTAL_VP;j++)
				{
					if((nMin>_vDiscPages[j].m_nTime)&&
                       (_vDiscPages[j].m_nPageFaceNumber!=INVALID))	 
					{	//进程页面访问次数小于nMin且页面页号在物理内存中 
						nMin=_vDiscPages[j].m_nTime;
		    			minj=j;
					}
				}
				_pFreepf_head=&_vMemoryPages[_vDiscPages[minj].
                                             m_nPageFaceNumber];
                //将空闲页面的头指针指向需要换出的页号
				_vDiscPages[minj].m_nPageFaceNumber=INVALID;
                //将需要换出的页面移出物理内存 
				_vDiscPages[minj].m_nTime=-1;//将需要换出的页面的访问次数设置为-1 
				_pFreepf_head->m_pNext=NULL;//将空闲头指针的下一个指针置空 
			}
			/* 将待执行指令的页面调入内存 */ 
			_vDiscPages[_vPage[i]].m_nPageFaceNumber=
                _pFreepf_head->m_nPageFaceNumber;	
            //将需要换入的页面的页号置为之前空闲头指针指向的页面的页号，
            //即将要换入的页面放入内存中 
			_vDiscPages[_vPage[i]].m_nTime=nPresentTime;	
            //将要放入的页面的访问次数设置为nPresentTime 
			_pFreepf_head=_pFreepf_head->m_pNext;
            //将空闲头指针指向下一个指针指向的页面 
		}
		else{	//如果页面页号已经在物理内存中 
			_vDiscPages[_vPage[i]].m_nTime=nPresentTime;
            //将页面的访问次数设置为nPresentTime
		}
		nPresentTime++;
	}
	cout<<"LRU: "<<fixed<<setprecision(6)<<1-(float)_nDiseffect/320<<"\t";	
    //打印出命中率 
}

类成员函数NUR(const int nTotal_pf)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
void CMemory::NUR(const int nTotal_pf){
	int i,j,nDiscPage,nOld_DiscPage;
	bool bCont_flag;//设置循环条件 
	initialize(nTotal_pf);//初始化 
	nDiscPage=0;//将nDiscPage置为0 
	for(i=0;i<TOTAL_INSTRUCTION;i++)
	{
		if(_vDiscPages[_vPage[i]].m_nPageFaceNumber==INVALID)
		{	//如果页面页号不在物理内存中
			_nDiseffect++;
			if(_pFreepf_head==NULL)	 
			{	//如果分配给进程的物理内存页面无空闲，则将最近未使用的页面调出内存 
    			bCont_flag=true;	
    			nOld_DiscPage=nDiscPage;
				while(bCont_flag)
				{
                    if(_vDiscPages[nDiscPage].m_nCounter==0&&
                       _vDiscPages[nDiscPage].m_nPageFaceNumber!=INVALID) 
					{	//如果页面计数为零并且该页面的页号不在物理内存中 
						bCont_flag=false;
					}
					else{	//如果页面计数不为零并且该页面的页号在物理内存中  
						nDiscPage++;
						if(nDiscPage==TOTAL_VP) 
						{	//一个循环后，重新置零 
							nDiscPage=0;
						} 
						if(nDiscPage==nOld_DiscPage)
						{
							for(j=0;j<TOTAL_VP;j++) 
							{	//将所有页面的计数清零
								_vDiscPages[j].m_nCounter=0;
							}
						}
	   				}
				}
				_pFreepf_head=&_vMemoryPages[_vDiscPages[nDiscPage].
                                             m_nPageFaceNumber];	
                //将空闲页面的头指针指向该物理页面的页号 
				_vDiscPages[nDiscPage].m_nPageFaceNumber=INVALID;	
                //将该物理页面的页号置为不在内存中 
    			_pFreepf_head->m_pNext=NULL;	
                //将空闲头指针的下一个地址设置为空 
			}
			/* 将待执行的指令的页面调入内存中 */ 
			_vDiscPages[_vPage[i]].m_nPageFaceNumber=
                _pFreepf_head->m_nPageFaceNumber;	
            //将待执行页面的页号设置为空闲头指针指向的页号 
			_pFreepf_head=_pFreepf_head->m_pNext;	
            //将空闲头指针指向下一个页面 
		}
		else{	//如果页面页号已经在物理内存中 
			_vDiscPages[_vPage[i]].m_nCounter=1;//将该页面的计数＋1 
		}
		/* 定期将所有页面存放是否被CPU处理信息的属性均置于初始态 */ 
		if(i%CLEAR_PERIOD==0)
		{
			for(j=0;j<TOTAL_VP;j++)	 
			{	//将所有页面的计数清零
				_vDiscPages[j].m_nCounter=0;
			}
		}
    }
	cout.setf(ios::fixed);
	cout<<"NUR:"<<fixed<<setprecision(6)<<1-(float)_nDiseffect/320<<"\t";	
    //打印命中率 
}

类成员函数OPT(const int nTotal_pf)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
void CMemory::OPT(const int nTotal_pf)
{
	int i,j,max,maxpage,nDistance,vDistance[TOTAL_VP];
    //vDistance[TOTAL_VP]表示页面在第几步被处理,其它的是辅助变量，用于计数和中间过渡 
	initialize(nTotal_pf);	//初始化 
	for(i=0;i<TOTAL_INSTRUCTION;i++)
	{
		if(_vDiscPages[_vPage[i]].m_nPageFaceNumber==INVALID) 
		{	//如果页面页号不在物理内存中 
			_nDiseffect++;
			/* 将不在处理的页面或者最后待处理的页面调出内存 */ 
			if(_pFreepf_head==NULL)
			{	//如果分配给进程的物理内存页面无空闲 
				for(j=0;j<TOTAL_VP;j++)
				{
					if(_vDiscPages[j].m_nPageFaceNumber!=INVALID)
					{	//如果虚页j已经在物理内存中，将其设置为最后处理 
						vDistance[j]=32767;
					}
					else{	//如果虚页j不在物理内存中，将vDistance[j]置为0
						vDistance[j]=0;
					}
				} 
				nDistance=1; 
				for(j=i+1;j<TOTAL_INSTRUCTION;j++)
				{	//遍历所有页面，得到所有页面在第几步被处理 
					if((_vDiscPages[_vPage[j]].m_nPageFaceNumber!=INVALID)&&
                       (vDistance[_vPage[j]]==32767))
					{	//如果虚页j在物理内存中并且在第32767步被处理，
                        //则将处理步数重置为nDistance 
						vDistance[_vPage[j]]=nDistance;
					}
					nDistance++;
				}
    			max	=-1;
    			for(j=0;j<TOTAL_VP;j++)
				{	//遍历所有页面找出找出最后处理的页面 
					if(max<vDistance[j])
	  				{
					    max=vDistance[j];
					    maxpage=j;
					}
				}
				/* 将最后处理的页面调出 */ 
				_pFreepf_head=&_vMemoryPages[_vDiscPages[maxpage].
                                             m_nPageFaceNumber];	
                //将空闲头指针指向最后处理的页面 
				_pFreepf_head->m_pNext=NULL;//将空闲头指针指向的下一个位置置空 
				_vDiscPages[maxpage].m_nPageFaceNumber=INVALID;	
                //将最后处理的页面调出内存 
			}
			_vDiscPages[_vPage[i]].m_nPageFaceNumber=
                _pFreepf_head->m_nPageFaceNumber;	
            //将待执行指令的页号置为空闲头指针指向的页号 
			_pFreepf_head=_pFreepf_head->m_pNext;//将空闲头指针指向下一个页面 
		}
   }
	cout.setf(ios::fixed);
	cout<<"OPT:"<<fixed<<setprecision(6)<<1-(float)_nDiseffect/320<<"\t";
    //打印命中率 
}

main()函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <string>
#include <vector>	//vector是一种顺序容器，事实上和数组差不多，但它比数组更优越。一般来说数组不能动态拓展，因此在程序运行的时候不是浪费内存，就是造成越界。而vector正好弥补了这个缺陷，它的特征是相当于可分配拓展的数组，它的随机访问快，在中间插入和删除慢，但在末端插入和删除快，而且如果用.at()访问的话，也可以做越界检查。
#include <cstdlib>	//同<stdlib.h>，c开头是C++的习惯，.h结尾是C的习惯 
#include <cstdio>	//同<stdio.h>，c开头是C++的习惯，.h结尾是C的习惯  
#include <unistd.h>	//封装了类UNIX系统下的很多固定名称的system_call系统调用，提供对POSIX操作系统API的访问功能。所以，这个函数是依赖于编译器，依赖于操作系统的。 
#include <iomanip>	//声明流操作符，规范输出格式
#define INVALID -1
using namespace std;
const int TOTAL_INSTRUCTION(320);	//声明全局静态变量指令总数(TOTAL_INSTRUCTION)为320 
const int TOTAL_VP(32);				//声明虚页长度(TOTAL_VP)为32 
const int CLEAR_PERIOD(50);			//声明进程清零周期(CLEAR_PERIOD)为50
#include "Page.h"
#include "PageControl.h"
#include "Memory.h"
int main(){
	int i;
	CMemory a;
	for(i=4;i<=32;i++)
	{
		a.FIFO(i);	//FIFO算法命中率 
 	    a.LRU(i);	//LRU算法命中率 
		a.NUR(i);	//NUR算法命中率
		a.OPT(i);	//OPT算法命中率 
		cout<<"\n";
	}
	return 0;	//5p2O5rK76ZyW== 
}

实验结果及分析

  1. 在RED Hat Linux中通过输入以下命令执行程序；

    1
    2
    g++ -o main mian.cpp
    ./main

  2. 得到程序结果如下；

    1571280409171

  3. 结果分析；

    1. 四种页面置换算法OPT算法的命中率最高，其它三种基本相同；
    2. 随着分配内存页面逐渐增加，每种页面置换算法的命中率也会相应增加，并且趋于一个稳定值90%；
    3. 如果次数非常大，这四种置换算法的命中率基本一致；

实验难点与收获

难点

  1. 对OPT置换算法和对NUR置换算法的理解；
  2. C++编程中类的使用规范等；

收获

  1. 学习了四种置换算法的基本原理和C++语言实现；
  2. 通过实验结果，对比得到了四种算法的优劣；
  3. 了解了内存页面调度的机理；
  4. 进一步熟悉了C++中类的调用规范；

实验思考

实验通过对四种页面置换算法进行横向对比和纵向对比，展示了四种算法的优缺点；但是实验结果对实验的原理体现的不太明显，可以在实验结果中增加每种算法的执行过程，让算法原理理解。