操作系统页面调度算法-Toy模板网

这篇具有很好参考价值的文章主要介绍了操作系统页面调度算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

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

二、实验内容
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、设计两个程序模拟实现一个作业在内存中执行的页面置换,并计算缺页中断次数。 3,算法,图论

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、设计两个程序模拟实现一个作业在内存中执行的页面置换,并计算缺页中断次数。 3,算法,图论

五、实验结论

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

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

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

到了这里，关于操作系统页面调度算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！