操作系统页面调度算法_1、设计两个程序模拟实现一个作业在内存中执行的页面置换,并计算缺页中断次数。 3

实验项目名称：操作系统页面调度算法

一、实验目的和要求
目的：对操作系统中使用的页面调度算法进行设计。
要求：对教材中所讲述的几种页面调度算法进行深入的分析，通过请求页式存储管理中页面置换算法模拟设计,了解虚拟存储技术的特点,掌握请求页式存储管理的页面置换算法。

二、实验内容
1、设计两个程序模拟实现一个作业在内存中执行的页面置换，并计算缺页中断次数。
2、编制两种页面置换算法：
1）FIFO页面置换算法；
2）LRU页面置换算法。

三、实验原理
1、FIFO页面置换算法：总是选择在其内存中驻留的时间最长的一页将其淘汰。
2、LRU页面置换算法：选择最近一段时间内最长时间没有被访问过的页面予以淘汰。

四、实验操作过程及实验结果记录
1、FIFO页面置换算法：

#include <stdio.h>
#include <stdlib.h>
#define maxpagenum 100
typedef struct page
{
    int pagenum;
    struct page *next;
}Page;
int FIFO(Page *block,int pages[maxpagenum],int pagenum,int blocknum)
{
    int i = 0,j = 0;
    int time = 0;
    Page *old = block,*check = NULL;
    while(i<pagenum){
        check = block;
        j = 0;
        while(j < blocknum){
            if(pages[i]==check->pagenum)// 命中
                break;
            check = check->next;
            j++;
        }
        if(j == blocknum){//没有命中，替换
            old->pagenum = pages[i];
            old = old->next;
            time += 1; //缺页次数+1
        }
        i++;
    }
    return time;
}
Page* creatblock(int blocknum)
{
    int i;
    Page *head = NULL,*cur = NULL,*tail = NULL;
    for(i = 0;i < blocknum;i++){
        if(!head){
            cur = (Page*)malloc(sizeof(Page));
            cur->pagenum = -1;
            cur->next = NULL;
            head = tail = cur;
        }
        else{
            cur = (Page*)malloc(sizeof(Page));
            cur->pagenum = -1;
            tail->next = cur;
            tail = cur;
        }
    }
    tail->next = head;
    return head;
}
int main()
{
    int time;
    int pages[maxpagenum];
    int i,blocknum,pagenum;
    Page *head=NULL;
    printf("请输入块号：\n");
    scanf("%d",&blocknum);
    head = creatblock(blocknum);
    printf("请输入待访问的页面数量：\n");
    scanf("%d",&pagenum);
    printf("请输入待访问的页面号：\n");
    for(i=0;i<pagenum;i++){
        scanf("%d",&pages[i]);
    }
    time = FIFO(head,pages,pagenum,blocknum);
    printf("缺页次数：%d，中断率：%.2f%%\n",time,time*1.0/pagenum*100);
    return 0;
}
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
68
69
70
71

运行截图：

2、LRU页面置换算法：

#include<stdio.h>
int block_num;   /*分配的物理块数*/
int page_num;   /*要访问的页面序列个数*/
int page[100]; /*要访问的页面序列*/
int memory[10]; /*物理块中的页号*/
int table[100][10]; /*显示矩阵*/
int reg[10];  /*寄存器--记录页面的访问时间*/
char Que[100];  /*数组，记录是否缺页*/

/*主函数*/
int main()
{	
    int count=0; /*记录缺页次数*/    
    int i,j,k;	
	while(1) 
	{
		printf("请输入分配的物理块的个数(M<=10):\n");
		scanf("%d",&block_num);
		if(block_num>10)
			printf("输入不合法，请重新输入"); 
		printf("\n");
		break;
	}
		
	while(1)
	{
		printf("请输入要访问的页面序列个数(P<=100):\n");
		scanf("%d",&page_num);			
		if(page_num>100)
			printf("输入不合法，请重新输入");
		printf("\n");
		break;
	}
	
	printf("请依次输入要访问的页面序列，以空格隔开:\n");
	for(i=0;i<page_num;i++)
	{
		scanf("%d",&page[i]);
		Que[i] = 'N';
	}
		 	
	for(i=0;i<block_num;i++)
	     memory[i]=-1;   //初始内存块中默认为空，用-1表示

    //访问页面
	for(i=0;i<page_num;i++)
	{
		if(i==0)   //访问的第一个页面
		{
			memory[i]=page[i];
			reg[i]=i;
			for(j=0;j<block_num;j++)
				table[i][j]=memory[j];
			Que[i]='Y';
			count++;
		}
		else
		{    /*判断新页面号是否在物理块中*/   
			for(j=0,k=0;j<block_num;j++)
			{
				if(memory[j]!=page[i])
					k++;
				else
				{    /*新页面在内存块中*/
					reg[j]=i;  //刷新该页面的访问时间
					for(int n=0;n<block_num;n++)
						table[i][n]=memory[n];
				}
			}
		}
		if(k==block_num)   /*新页面不在物理块中，缺页*/
		{
			int q=0;
			Que[i]='Y';
		    count++;
			for(int j=0;j<block_num;j++)
			{
				if(memory[j]==-1)   /*内存块未满*/
				{
					memory[j]=page[i];
				    reg[j]=i;
				    for(int n=0;n<block_num;n++)
					    table[i][n]=memory[n]; 
					break;
				}
				else   
					q++;	
			}
			if(q==block_num)/*内存块已满，需采用LRU置换算法选择换出页*/ 
			{
			 int min=0;  //记录换出页
        	    for(int m=1;m<block_num;m++)
			        if(reg[m]<reg[min])
				    	min=m;
		        memory[min]=page[i];
                reg[min]=i; /*记录该页的访问时间（新到的页面进入之前min的位置，需将min位置的访问时间更改）*/
                for(int n=0;n<block_num;n++)
			       table[i][n]=memory[n];
			}
		}
    }
    
 	/*输出运行过程及结果*/   
	printf("采用LRU页面置换算法结果如下: \n");
	printf("\n");
	printf("\n");
	printf("页号:");
	for(i=0;i<page_num;i++)
		printf("%3d",page[i]);
	printf("\n");
	printf("-----------------------------------------------------\n");
	for(i=0;i<block_num;i++) 	
	{
		printf("块%2d:",i);	 
		for(j=0;j<page_num;j++)
			printf("%3d",table[j][i]);
		printf("\n");
	}
    printf("-----------------------------------------------------\n");
	printf("缺页:");
	for(i=0;i<page_num;i++)
	    printf("%3c",Que[i]);
	printf("\n");
	
	printf("-----------------------------------------------------\n");
	printf("\t缺页次数:%d\n",count);
	printf("\t缺页率:%d/%d\n",count,page_num);
	printf("-----------------------------------------------------\n");
}
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

运行截图：

五、实验结论

FIFO调度算法，是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。可以得出先来先服务算法和最近最久未使用算法性能相近,同时对比不同内存块数下的程序运行结果能够看出，算法的缺页率与分配的内存块数有关系，分配的内存块数越多，缺页率越低。

六、实验过程中所遇问题思考与讨论

在具体的实验操作中，采用C语言实现发生缺页中断的初始页号这部分时不太理解具体代码细节，最终通过在网上搜索解决了相关问题，复习之前遗忘的知识点，学习新的知识。通过这次试验让我们对操作系统的页面置换算法有了更深入的了解。