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

用先进先出(FIFO)页面调度算法处理缺页中断。

程序员文章站 2022-05-12 13:39:07
...

用先进先出(FIFO)页面调度算法处理缺页中断。

(1) 在分页式虚拟存储系统中,当硬件发出“缺页中断”后,引出操作系统来处理这个中断事件。如果主存中已经没有空闲块,则可用FIFO页面调度算法把该作业中最先进入主存的一页调出,存放到磁盘上,然后再把当前要访问的页装入该块。调出和装入后都要修改页表中对应页的标志。
(2) FIFO页面调度算法总是淘汰该作业中最先进入主存的那一页,因此可以用一个数组来表示该作业已在主存的页面。假定作业被选中时,把开始的m个页面装入主存,则数组的元素可定为m个。例如:
P[0],P[1],….,P[m-1]
其中每一个P[i](i=0,1,….,m-1)表示一个在主存中的页面号。它们的初值为:
P[0]:=0,P[1]:=1,….,P[m-1]:=m-1
用一指针k指示当要装入新页时,应淘汰的页在数组中的位置,k的初值为“0”。
当产生缺页中断后,操作系统选择P[k]所指出的页面调出,然后执行:
P[k]:=要装入页的页号
k:=(k+1) mod m
再由装入程序把要访问的一页信息装入到主存中。重新启动刚才那条指令执行。
(3) 编制一个FIFO页面调度程序,为了提高系统效率,如果应淘汰的页在执行中没有修改过,则可不必把该页调出(因在磁盘上已有副本)而直接装入一个新页将其覆盖。因此在页表中增加是否修改过的标志,为“1”表示修改过,为“0”表示未修改过,格式为:
页号 标志 主存块号 修改标志 在磁盘上的位置

由于是模拟调度算法,所以,不实际启动输出一页和装入一页的程序,而用输出调出的页号和装入的页号来代替一次调出和装入的过程。
把第一题中程序稍作修改,与本题结合起来,FIFO页面调度模拟算法如图6-2。
(4) 磁盘上,在磁盘上的存放地址以及已装入主存的页和作业依次执行的指令序列都同第一题中(4)所示。于是增加了“修改标志”后的初始页表为:
页号 标志 主存块号 修改标志 在磁盘上的位置
0 1 5 0 011
1 1 8 0 012
2 1 9 0 013
3 1 1 0 021
4 0 0 022
5 0 0 023
6 0 0 121
按依次执行的指令序列,运行你所设计的程序,显示或打印每次调出和装入的页号,以及执行了最后一条指令后的数组P的值。
(5) 为了检查程序的正确性,可再任意确定一组指令序列,运行设计的程序,核对执行的结果。

c语言源码

#include "stdio.h"
#define N 15
#define M 4
void main()
{
	int a[N],i,j,q,b[M]={0},c[M][N],count=0;
	char flag,f[N];
	printf("请输入页面访问序列:\n");
	for(i=0;i<N;i++)                    
		scanf("%d",&a[i]);
	for(i=0;i<N;i++)                    //查页表,看是否缺页
	{  
		q=0;
		while((a[i]!=b[q])&&(q!=M))
		{
			q++;
		}		
 		if(q==M) 
		{
			flag='*';
			count++; 
		}//缺页,则置标志flag为'*'
		else flag=' ';
 		if(flag=='*')
 		{
			for(j=M-1;j>0;j--)              //淘汰最先调入的页面调入当前访问的
 				b[j]=b[j-1];
 				b[0]=a[i];
		//	printf("发生缺页的页面是:%3d\n",b[j]);
 		}
 		for(j=0;j<M;j++)               
 			c[j][i]=b[j];
 			f[i]=flag;
			if(c[j][3]==0)
			{
				printf(" ");
			}
			else
			{
				printf("被淘汰的页面是:%3d\n",c[j][3]);
			}
	 }
	 
	 printf("输出结果为下表(0代表为空,*代表有缺页):\n");
	 printf("*********************************************************\n");
	 printf("页面走向:");//输出页面走向
	 for(i=0;i<N;i++)
		 printf("%3d",a[i]);
		 printf("\n");
	 printf("*********************************************************\n");
	 for(i=0;i<M;i++)//每块内的页面变化
	 {
		printf("   %d号块:",i);
		for(j=0;j<N;j++)
			printf("%3d",c[i][j]);
		printf("\n");
	 }
	 printf("*********************************************************\n");
	 printf("缺页情况:");
	 for(i=0;i<N;i++)//缺页的情况
		printf("%3c",f[i]);
	 printf("\n");
	 printf("*********************************************************\n");
     printf("\n发生缺页的次数=%d\n",count);
	 printf("缺页中断率=%.2f%%%\n",(float)count/N*100);
}

运行结果

输入15个数然后回车,每个数之间用空格隔开
用先进先出(FIFO)页面调度算法处理缺页中断。

相关标签: 操作系统