欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

《操作系统原理》实验报告四

程序员文章站 2024-03-18 11:55:52
...

一、实验目的
(1)理解页面淘汰算法原理,编写程序演示页面淘汰算法。
(2)验证 Linux 虚拟地址转化为物理地址的机制
(3)理解和验证程序运行局部性的原理。

二、实验内容
(1)在Windows环境下编写一个程序,模拟实现OPT,FIFO,LRU等页面淘汰算法。可以使用数组模拟内存,数组中的元素模拟为指令或数据。写不同方式的程序去 访问数组来模拟 CPU 访问内存的情况。分析运算结果,在分配不同的物理块情况下, 各算法的缺页情况有什么规律?可以 srand( )和 rand( )等函数定义和产生“指令”
序列,然后将指令序列变换成相应的页地址流,并针对不同的算法计算出相应的
命中率。 例如,实验中可以产生 320 条“指令”,每个“虚拟页”存放 10 条指令。 进程分配的页框是 4(可变,例如 32)。
(2)在 Linux 环境下,编写一个小程序,获取该程序中的某个变量的虚拟地址,
虚拟页号,页内偏移地址,物理页框号,页内偏移地址,物理地址,并将它们打 印出来。建议使用/proc/pid/pagemap 技术。
(3)在Windows 环境下,编写一个函数(特点:比较耗时,比如大型的多维数
组读写),用不同的方法测试其所花费的时间。在不同环境下比较其时间是否不同,并分析其含义。测量时间的函数请 baidu。

三、实验过程
(一)实验步骤
1)模拟实现OPT,FIFO,LRU等页面淘汰算法(Windows)
1.定义内存帧,指令序列,引用串,内存容量,虚拟内存容量;

1.		#define MAX_VIR_SIZE 64  
2.	#define MAX_MEM_SIZE 32  
3.	#define VIR_NO 2  
4.	#define MEM_NO 3  
5.	#define FALSE -1  
6.	  
7.	int mem_frame[MAX_MEM_SIZE];        //内存帧   
8.	  
9.	int instruction[MAX_VIR_SIZE * 10];   //指令序列   
10.	int reference[MAX_VIR_SIZE * 10];     //引用串   
11.	  
12.	int mem_size[MEM_NO] = { 4, 18, 32 }; //内存容量   
13.	int vir_size[VIR_NO] = { 32, 64 };    //虚存容量   
  1. 初始化页地址流,指令序列全为-1,引用串全为-1;
  2. 产生页地址流
1.	int generate_page(int vsize)  
2.	{  
3.	    srand((unsigned)time(NULL)); /*播种子*/  
4.	    //产生指令序列   
5.	    for (int i = 0; i < vsize * 10; i += 5) {  
6.	        instruction[i] = rand() % (vsize * 10 - 1);  
7.	        instruction[i + 1] = instruction[i] + 1;  
8.	        instruction[i + 2] = rand() % instruction[i + 1];  
9.	        instruction[i + 3] = instruction[i + 2] + 1;  
10.	        instruction[i + 4] = rand() % (vsize * 10 - instruction[i + 3] - 2) + instruction[i + 3] + 1;  
11.	    }  
12.	  
13.	    //将指令序列变换为对应的页地址流  
14.	    for (int i = 0; i < vsize * 10; i++)  
15.	        instruction[i] /= 10;  
16.	  
17.	    reference[0] = instruction[0];  
18.	  
19.	    int base = 0, j = 1;  
20.	    for (int i = 1; i < vsize * 10; i++) {  
21.	        if (instruction[i] != instruction[base]) {  
22.	            reference[j] = instruction[i];  
23.	            j++;  
24.	  
25.	            base = i;  
26.	        }  
27.	    }  
28.	    return j;    //返回引用串,即页地址流的长度   
29.	}  
  1. 用不同方式的算法去访问数组来模拟 CPU 访问内存的情况,计算命中率
    OPT算法 :淘汰以后不再需要或最远的将来才会用到的页面
1.	void OPT(int ref_len, int vsize)  
2.	{  
3.	    int mem_no, msize, i, find, miss, j, k;  
4.	    int first;  
5.	    int longest, rep;  
6.	    float rate = 0;  
7.	  
8.	    printf("OPT");  
9.	  
10.	    for (mem_no = 0; mem_no < MEM_NO; mem_no++) {  
11.	        miss = 0;  
12.	        ini_mem();                          //初始化内存工作区   
13.	        msize = mem_size[mem_no];  
14.	        for (i = 0; i < ref_len; i++) {  
15.	            find = search(msize, reference[i]);  
16.	            if (find != FALSE && mem_frame[find] == -1) {     //内存工作区未满   
17.	                miss++;  
18.	                mem_frame[find] = reference[i];//页置换   
19.	            }  
20.	            else if (find == FALSE) {        //内存工作区已满且没找到  
21.	                miss++;  
22.	                longest = 0;  
23.	                first = 0;  
24.	                for (j = 0; j < msize; j++) {  
25.	                    for (k = i + 1; k < ref_len; k++) {  
26.	                        if (mem_frame[j] == reference[k]) {  
27.	                            if (k > longest) {  
28.	                                longest = k;  
29.	                                rep = j;     //找到向前看距离最远的一帧   
30.	                            }  
31.	                            break;  
32.	                        }  
33.	                        if (k == ref_len && first == 0) {  
34.	                            longest = k;  
35.	                            first = 1;  
36.	                            rep = j;  
37.	                        }  
38.	                    }  
39.	                }  
40.	                mem_frame[rep] = reference[i];//页置换   
41.	            }  
42.	            else//找到页对应的帧                
43.	        }  
44.	        rate = 1 - ((float)miss) / ((float)ref_len);          //计算命中率   
45.	        printf("\t\t%4d/%2d\t\t%.2f\n", msize, vsize, rate);  
46.	    }  
47.	} 

FIFO算法:淘汰在内存中停留时间最长的页面

1.	void FIFO(int ref_len, int vsize)  
2.	{  
3.	    printf("FIFO");  
4.	    for (int mem_no = 0; mem_no < MEM_NO; mem_no++) {  
5.	        int miss = 0;  
6.	        ini_mem(); //初始化内存工作区                            
7.	        int msize = mem_size[mem_no];  
8.	        int rep = 0;  
9.	        for (int i = 0; i < ref_len; i++) {  
10.	            int find = search(msize, reference[i]);  
11.	            //内存工作区未满   
12.	            if (find != FALSE && mem_frame[find] == -1) {  
13.	                miss++;  
14.	                mem_frame[find] = reference[i];  
15.	            }  
16.	            //内存工作区已满且没找到  
17.	            else if (find == FALSE) {  
18.	                miss++;  
19.	                mem_frame[rep] = reference[i];//页置换  
20.	                //下一个将要被置换的帧的位置   
21.	                rep = (rep + 1) % msize;  
22.	            }  
23.	            else//找到页对应的帧  
24.	                ;  
25.	        }  
26.	        float rate = 1 - ((float)miss) / ((float)ref_len);           //计算命中率   
27.	        printf("\t\t%4d/%2d\t\t%.2f\n", msize, vsize, rate);  
28.	    }  
29.	}  

LRU算法:淘汰最长时间未被使用的页面

1.	void LRU(int ref_len, int vsize)  
2.	{  
3.	    int mem_no, msize, i, find, miss, j, k, longest, rep, dis;  
4.	    float rate = 0;  
5.	  
6.	    printf("LRU");  
7.	  
8.	    for (mem_no = 0; mem_no < MEM_NO; mem_no++) {  
9.	        miss = 0;  
10.	        ini_mem();  //初始化内存工作区                           
11.	        msize = mem_size[mem_no];  
12.	        for (i = 0; i < ref_len; i++) {  
13.	            find = search(msize, reference[i]);  
14.	            //内存工作区未满   
15.	            if (find != FALSE && mem_frame[find] == -1) {  
16.	                miss++;  
17.	                mem_frame[find] = reference[i];//页置换   
18.	            }  
19.	            //内存工作区已满且没找到  
20.	            else if (find == FALSE) {  
21.	                miss++;  
22.	                longest = 0;  
23.	                for (j = 0; j < msize; j++) {  
24.	                    for (k = i - 1; k >= 0; k--) {  
25.	                        if (mem_frame[j] == reference[k]) {  
26.	                            dis = i - k;  
27.	                            if (dis > longest) {  
28.	                                longest = dis;  
29.	                                rep = j;     //找到向后看距离最远的一帧   
30.	                            }  
31.	                            break;  
32.	                        }  
33.	                    }  
34.	                }  
35.	                mem_frame[rep] = reference[i];//页置换   
36.	            }  
37.	            else//找到页对应的帧  
38.	                ;  
39.	        }  
40.	        rate = 1 - ((float)miss) / ((float)ref_len);          //计算命中率   
41.	        printf("\t\t%4d/%2d\t\t%.2f\n", msize, vsize, rate);  
42.	    }  
43.	}  

2)编写程序获取、打印该程序中的某个变量的信息(Linux 环境)
重要函数和相关计算
getpagesize(); //调用此函数获取系统设定的页面大小
v_pageIndex = vaddr / pageSize; //计算此虚拟地址相对于0x0的经过的页面数
v_offset = v_pageIndex * sizeof(uint64_t); //计算在/proc/pid/page_map文件中的偏移量
page_offset = vaddr % pageSize; //计算虚拟地址在页面中的偏移量
uint64_t phy_pageIndex = (((uint64_t)1 << 55) - 1) & item; //计算物理页号,即取item的bit0-54
*paddr = (phy_pageIndex * pageSize) + page_offset; //再加上页内偏移量就得到了物理地址

1.	void mem_addr(unsigned long vaddr, unsigned long *paddr)  
2.	{  
3.	    int pageSize = getpagesize(); //调用此函数获取系统设定的页面大小  
4.	    printf("页面大小为%d\n", pageSize);    
5.	    unsigned long v_pageIndex = vaddr / pageSize; //计算此虚拟地址相对于0x0的经过的页面数  
6.	    printf("页面数为:%u\n", v_pageIndex);  
7.	    unsigned long v_offset = v_pageIndex * sizeof(uint64_t); //计算在/proc/pid/page_map文件中的偏移量  
8.	    unsigned long page_offset = vaddr % pageSize;            //计算虚拟地址在页面中的偏移量  
9.	    printf("偏移量为:%x\n", page_offset);  
10.	    uint64_t item = 0;                             //存储对应项的值  
11.	    int fd = open("/proc/self/pagemap", O_RDONLY); //以只读方式打开/proc/pid/page_map  
12.	  
13.	    lseek(fd, v_offset, SEEK_SET);            //将游标移动到相应位置,即对应项的起始地址且判断是否移动失败  
14.	    read(fd, &item, sizeof(uint64_t)) != sizeof(uint64_t); //读取对应项的值,并存入item中,且判断读取数据位数是否正确    
15.	    if ((((uint64_t)1 << 63) & item) == 0) //判断present是否为0  
16.	    {  
17.	        printf("page present is 0\n");  
18.	        return;  
19.	    }  
20.	    printf("物理页号为%u\n", ((uint64_t)1 << 63) & item);  
21.	    uint64_t phy_pageIndex = (((uint64_t)1 << 55) - 1) & item; //计算物理页号,即取item的bit0-54  
22.	    printf("物理页号为%u\n", item);  
23.	    *paddr = (phy_pageIndex * pageSize) + page_offset; //再加上页内偏移量就得到了物理地址  
24.	}  

3)用不同的方法测试函数所花费的时间(Windows)
1.所测试函数为循环1000000000的循环;
2.使用了四种不同的方法
clock_t clock(void);
返回进程启动到调用函数时所经过的CPU时钟计时单元(clock tick)数,在MSDN中称之为挂钟时间(wal-clock),以毫秒为单位。clock_t实际是个long长整型typedef long clock_t;
头文件:#include <time.h>

1.	clock_t start = clock();  
2.	   test(); //待测试函数  
3.	   clock_t end = clock();  
4.	   double runtime = (double)(end - start) / CLOCKS_PER_SEC;  

高精度计时,以微秒为单位(1毫秒=1000微秒)
先看二个函数的定义BOOL QueryPerformanceCounter(LARGE_INTEGER *lpPerformanceCount);得到高精度计时器的值(如果存在这样的计时器)。BOOL QueryPerformanceFrequency(LARGE_INTEGER *lpFrequency);返回硬件支持的高精度计数器的频率(次每秒),返回0表示失败。
再看看LARGE_INTEGER它其实是一个联合体,可以得到__int64 QuadPart;也可以分别得到低32位DWORD LowPart和高32位的值LONG HighPart。在使用时,先使用QueryPerformanceFrequency()得到计数器的频率,再计算二次调用QueryPerformanceCounter()所得的计时器值之差,用差去除以频率就得到精确的计时了。
头文件:直接使用#include <windows.h>就可以了。

1.	  LARGE_INTEGER BegainTime;  
2.	   LARGE_INTEGER EndTime;  
3.	   LARGE_INTEGER Frequency;  
4.	   QueryPerformanceFrequency(&Frequency);  
5.	   QueryPerformanceCounter(&BegainTime);  
6.	   test(); //待测试函数  
7.	   QueryPerformanceCounter(&EndTime);  
8.	   double runtime = (double)(EndTime.QuadPart - BegainTime.QuadPart) / 

Frequency.QuadPart;

time_t time(time_t *timer);
	返回以格林尼治时间(GMT)为标准,从1970年1月1日00:00:00到现在的此时此刻所经过的秒数。
	time_t实际是个long长整型typedef long time_t;

头文件:#include <time.h>

1.	time_t timeBegin, timeEnd;  
2.	   timeBegin = time(NULL);  
3.	   test();  
4.	   timeEnd = time(NULL);  
5.	   double runtime = (double)(timeEnd - timeBegin); 

DWORD timeGetTime(VOID);
返回系统时间,以毫秒为单位。系统时间是从系统启动到调用函数时所经过的毫秒数。注意,这个值是32位的,会在0到2^32之间循环,约49.71天。头文件:#include <Mmsystem.h>
引用库:#pragma comment(lib, “Winmm.lib”)

6.	DWORD  dwBegin, dwEnd;  
7.	   dwBegin = timeGetTime();  
8.	   test();  
9.	   dwEnd = timeGetTime();  
10.	   double runtime = (double)(dwEnd - dwBegin)/1000;  

(二)解决错误和优化
1.编译错误。错误消息:使用了未定义类型“type”,类型只有经过定义才能使用。若要解决该错误,请确保在引用类型前已对其进行了完全定义。有可能声明一个指向已
2.声明但未定义的类型的指针。但是 Visual C++ 不允许引用未定义的类型。
编译错误。错误消息:非法 break,break 仅在 do、for、while 或 switch 语句中合法。
3.运行时错误。由于在OPT、FIFO算法函数内部未初始化内存难以得到预期结果,故需要在每个页面淘汰算法函数内加上ini_mem(),初始化内存工作区。
4.特殊语法错误, C26451 算术溢出: 使用 4 字节值上的运算符 - ,然后将结果转换到 8 字节值。在调用运算符 - 之前将值强制转换为宽类型可避免溢出(io.2)。
5.编译错误,错误 LNK2019 无法解析的外部符号 [email protected],该符号在函数 “void __cdecl method_4(void)” ([email protected]@YAXXZ) 中被引用,原因是未加头文件。
Windows系统API函数timeGetTime()、GetTickCount()及QueryPerformanceCounter() DWORD timeGetTime(VOID);返回系统时间,以毫秒为单位。系统时间是从系统启动到调用函数时所经过的毫秒数。注意,这个值是32位的,会在0到2^32之间循环,约49.71天。必须加头文件:#include <Mmsystem.h> 引用库:#pragma comment(lib, “Winmm.lib”)
6. 特殊语法错误,linux c之提示format‘%d’ expects argument of type ‘int’, but argument 2 has type ‘long int’ 。解决办法md,m为指定的输出字段的宽度。如果数据的位数小于m,则左端补以空格,若大于m,则按实际位数输出。%ld(%mld 也可),输出长整型数据。最后 printf(“data is %ld”, data)解决。

四、实验结果
1)模拟实现OPT,FIFO,LRU页面淘汰算法
《操作系统原理》实验报告四
从左到右以此为算法、内存容量/虚拟内存容量、命中率。

2)编写程序获取、打印该程序中的某个变量的信息
《操作系统原理》实验报告四

3)用不同的方法测试函数所花费的时间
《操作系统原理》实验报告四
四种方法用时如上。

五、体会
通过本次实验,我对页面淘汰算法有了更深的了解,对每一种算法的特点有了更好的掌握,学习到了如何验证Linux虚拟地址转化为物理地址的机制,通过在网上查阅也了解并实现了WINDOWS环境下计算程序运行消耗时间的几种方法。
但通过本次实验,我发现自己的动手写代码的能力仍有不足,经常出错,需要加强。