精华内容
下载资源
问答
  • 2022-01-29 13:19:10

    操作系统实验3—实现请求页式存储管理模拟程序

    实验描述

    实验内容:

    编写一个请求页式存储管理程序,模拟请求页式存储管理方式下的内存分配和页面置换。

    实验目的:

    内存管理是操作系统中的核心模块,能够合理利用内存,在很大程度上将影响到整个计算机系统的性能。内存的分配和回收与内存管理方式有关。本实验要求学生独立设计并实现请求页式存储管理方式下的内存分配与页面置换模拟程序,以加深对页面置换算法和请求页式存储管理方式的理解。

    实验要求:

    1. 可以随机输入分配给一个进程的内存块数,以及该进程的页面访问序列,具体信息见测试用例格式输入部分说明。
    2. 分别采用最佳算法OPT(当有多个页面可置换时,按照先进先出原则进行置换)、先进先出算法FIFO和最近最少使用算法LRU进行页面置换,其中LRU算法采用栈式方法实现。
    3. 显示页面变化时内存块装入页面列表的详细情况,并显示是否产生页面置换,并计算缺页次数及缺页率。具体信息见测试用例格式输出部分说明。

    测试用例格式如下:

    输入:

    算法(1--OPT,2--FIFO,3--LRU)
    内存块数
    页面序列(页面1,页面2,页面3,...)
    

    输出:

    页面变化时内存块装入页面列表1-是否命中/页面变化时内存块装入页面列表2-是否命中/...
    缺页次数
    
    其中:
    页面变化时内存块装入页面列表:
      (1) 内存块1装入页面,内存块2装入页面,内存块3装入页面...,未装入任何页面时由"-”表示
      (2) 是否命中:1-命中,0-缺页
    
    测试输入期待的输出时间限制内存限制额外进程
    测试用例 11
    3
    1,2,3,4,1,2,5,1,2,3,4,5
    1,-,-,0/1,2,-,0/1,2,3,0/1,2,4,0/1,2,4,1/1,2,4,1/1,2,5,0/1,2,5,1/1,2,5,1/3,2,5,0/3,4,5,0/3,4,5,1
    7
    1秒64M0
    测试用例 22
    4
    1,2,3,4,1,2,5,1,2,3,4,5
    1,-,-,-,0/1,2,-,-,0/1,2,3,-,0/1,2,3,4,0/1,2,3,4,1/1,2,3,4,1/5,2,3,4,0/5,1,3,4,0/5,1,2,4,0/5,1,2,3,0/4,1,2,3,0/4,5,2,3,0
    10
    1秒64M0
    测试用例 33
    3
    1,2,3,4,1,2,5,1,2,3,4,5
    1,-,-,0/1,2,-,0/1,2,3,0/2,3,4,0/3,4,1,0/4,1,2,0/1,2,5,0/2,5,1,1/5,1,2,1/1,2,3,0/2,3,4,0/3,4,5,0
    10
    1秒64M0

    设计思路

    虽然每次输入的页面数据只有页面序号,但是在算法中需要计算每个页面访问过之后的优先级变化,以及当前页面下一次访问所需要的距离信息,所以采用结构体数组的形式将需要用到的信息全部存储起来。

    临时数组在 LRU 算法中起辅助输出的作用。

    struct Memory
    {
    	int id;			//序号
    	int priority;	//最前面的内存优先级为0,往后依次加1 
    	int distance;	//下次访问与当前距离
    }memory[1010], memory2[1010];//内存序列,临时数组
    

    程序概要设计如下图所示:
    概要设计

    1. main()函数是主程序的入口,控制程序流程,并按照输入的调度信号选择相应的算法模块进行运行
    2. input()函数是输入函数,接受程序输入
    3. output()函数是输出函数,将页面命中与缺页置换的信息进行输出
    4. OPT()函数是最佳置换算法,根据已知的页面序列和优先级顺序算出最佳的页面调度方案
    5. FIFO()函数是先进先出算法,根据页面的到来顺序进行页面置换
    6. LRU()函数是最近最久未使用算法,根据页面的使用情况进行页面调度,这里使用了临时数组来辅助信息输出
    int main();		//主程序入口
    void input();	//输入函数
    void output(int k);//输出函数
    void OPT();		//最佳置换算法
    void FIFO();	//先进先出算法
    void LRU();		//最近最久未使用算法
    

    上机代码

    代码使用 C++ 语言进行编写

    #define _CRT_SECURE_NO_WARNINGS 
    #include<iostream> 
    #include<cstdio> 
    #include<cstdlib> 
    #include<algorithm> 
    #include<string> 
    using namespace std;
    struct Memory
    {
    	int id;//序号 
    	int priority;//最前面的内存优先级为0,往后依次加1 
    	int distance;//下次访问与当前距离 
    }memory[1010], memory2[1010];//内存序列,临时数组
    int que[1010];//页面序列 
    void input();//输入函数 
    void output(int k);//输出函数 
    void OPT();//最佳置换算法
    void FIFO();//先进先出算法
    void LRU();//最近最久未使用算法
    int sig;//算法选择标志 
    int memoryk, num, total;//内存块数,页面数量,缺页次数 
    int pageFlag;//缺页标志 
    const int isPage = 1;//命中 
    const int noPage = 0;//缺页 
    int main()
    {
    	//程序输入 
    	input();
    
    	//选择算法 
    	switch (sig)
    	{
    		case 1:OPT(); break;
    		case 2:FIFO(); break;
    		case 3:LRU(); break;
    	}
    	return 0;
    }
    void input()
    {
    	//freopen("osin.txt", "r", stdin); 
    	//freopen("osout.txt", "w", stdout); 
    
    	sig = 0;
    	cin >> sig;//算法选择标志 
    
    	memoryk = 0;
    	total = 0;
    	cin >> memoryk;//内存块数 
    
    	num = 0;
    	char c;
    	while (scanf("%d", &que[num]))//输入页面序列 
    	{
    		num++;
    		c = getchar();
    		if (c == '\n')//遇到换行符则输入结束 
    		{
    			break;
    		}
    		else if (c == ',')//遇到逗号则继续读取 
    		{
    			continue;
    		}
    	}
    	for (int i = 0; i < memoryk; i++)//内存初始化 
    	{
    		memory[i].id = -1;
    		memory[i].priority = i;
    	}
    }
    void output(int k)
    {
    	for (int i = 0; i < memoryk; i++)//输出内存中页面序列 
    	{
    		if (memory[i].id != -1)//内存有页面 
    		{
    			printf("%d,", memory[i].id);
    		}
    		else//内存没有页面 
    		{
    			printf("-,");
    		}
    	}
    	if (k != num - 1)//没到最后一页 
    	{
    		printf("%d/", pageFlag);
    	}
    	else//最后一页 
    	{
    		printf("%d\n", pageFlag);
    		printf("%d\n", total);
    	}
    }
    void OPT()
    {
    	int optFlag = 0;//OPT页面替换标志,替换下标为optFlag的页面 
    	for (int i = 0; i < num; i++)
    	{
    		int tmp = 0;//内存块下标 
    		while (tmp < memoryk)
    		{
    			if (que[i] == memory[tmp].id)//内存中有此页就输出 
    			{
    				pageFlag = isPage;
    				output(i);
    				break;
    			}
    			if (memory[tmp].id == -1)//内存中无此页则加入内存 
    			{
    				memory[tmp].id = que[i];
    				total++;
    				pageFlag = noPage;
    				output(i);
    				break;
    			}
    			tmp++;
    		}
    		//运行到此处证明找遍内存仍未命中页面 
    		  //淘汰下次访问距当前最远的那些页中序号最小的页,距离相等则淘汰优先级低的页 
    		if (tmp == memoryk)
    		{
    			for (int j = 0; j < memoryk; j++)//距离初始化 
    			{
    				memory[j].distance = 99999;
    			}
    			for (int j = 0; j < memoryk; j++)//计算距离 
    			{
    				int dis = 0;
    				for (int k = i + 1; k < num; k++)//记录下一个序号相同页面的距离 
    				{
    					dis++;
    					if (que[k] == memory[j].id)//更新距离 
    					{
    						memory[j].distance = dis;
    						break;
    					}
    				}
    			}
    			int max_dis = memory[0].distance;//找最大距离 
    			int min_prority = memory[0].priority;//找最小优先级 
    			for (int k = 0; k < memoryk; k++)
    			{
    				if (memory[k].distance == max_dis)
    				{
    					if (memory[k].priority <= min_prority)
    					{
    						min_prority = memory[k].priority;
    						max_dis = memory[k].distance;
    						optFlag = k;
    					}
    				}
    				else if (memory[k].distance > max_dis)
    				{
    					min_prority = memory[k].priority;
    					max_dis = memory[k].distance;
    					optFlag = k;
    				}
    			}
    			//调整优先级 
    			memory[optFlag].priority = memoryk;
    			for (int k = 0; k < memoryk; k++)
    			{
    				memory[k].priority--;
    			}
    			//缺页处理 
    			memory[optFlag].id = que[i];
    			pageFlag = noPage;
    			total++;
    			output(i);
    		}
    	}
    }
    void FIFO()
    {
    	int fifoFlag = 0;//FIFO页面替换标志,替换下标为fifoFlag的页面 
    	for (int i = 0; i < num; i++)
    	{
    		int tmp = 0;//内存块下标 
    		while (tmp < memoryk)
    		{
    			if (que[i] == memory[tmp].id)//内存中有此页就输出 
    			{
    				pageFlag = isPage;
    				output(i);
    				break;
    			}
    			if (memory[tmp].id == -1)//内存中无此页则加入内存 
    			{
    				memory[tmp].id = que[i];
    				total++;
    				pageFlag = noPage;
    				output(i);
    				break;
    			}
    			tmp++;
    		}
    		//运行到此处证明找遍内存仍未命中页面 
    		//按照FIFO的顺序进行页面淘汰 
    		if (tmp == memoryk)
    		{
    			if (fifoFlag == memoryk)//保证替换范围在[0-memoryk)之间 
    			{
    				fifoFlag = 0;
    			}
    			//缺页处理 
    			memory[fifoFlag].id = que[i];
    			fifoFlag++;
    			pageFlag = noPage;
    			total++;
    			output(i);
    		}
    	}
    }
    void LRU()
    {
    	int empty;//内存块中是否含有空闲区
    	int lruFlag = 0;//LRU页面替换标志,记录第一个空闲区下标
    	int x;//临时数组下标
    	for (int i = 0; i < num; i++)
    	{
    		empty = 0;
    		lruFlag = 0;
    
    		for (int j = 0; j < memoryk; j++)//寻找空闲区
    		{
    			if (memory[j].id == -1)
    			{
    				empty = 1;
    				lruFlag = j;
    				break;
    			}
    		}
    
    		int tmp = 0;//内存块下标
    		while (tmp < memoryk)
    		{
    			if (memory[tmp].id == que[i])//内存中有此页
    			{
    				if (empty == 1)//有空闲区
    				{
    					x = 0;
    					//调整输出顺序
    					for (int k = tmp + 1; k < lruFlag; k++)
    					{
    						memory2[x].id = memory[k].id;
    						x++;
    					}
    					x = 0;
    					for (int k = tmp; k < lruFlag - 1; k++)
    					{
    						memory[k].id = memory2[x].id;
    						x++;
    					}
    					memory[lruFlag - 1].id = que[i];
    
    					//输出
    					pageFlag = isPage;
    					output(i);
    					break;
    				}
    				else//没有空闲区
    				{
    					x = 0;
    					//调整输出顺序
    					for (int k = tmp + 1; k < memoryk; k++)
    					{
    						memory2[x].id = memory[k].id;
    						x++;
    					}
    					x = 0;
    					for (int k = tmp; k < memoryk - 1; k++)
    					{
    						memory[k].id = memory2[x].id;
    						x++;
    					}
    					memory[memoryk - 1].id = que[i];
    
    					//输出
    					pageFlag = isPage;
    					output(i);
    					break;
    				}
    			}
    			tmp++;
    		}
    		//运行到此处证明找遍内存仍未命中页面 
    		//淘汰上次使用距当前最远的页
    		if (tmp == memoryk)
    		{
    			if (empty == 1)//有空闲区
    			{
    				memory[lruFlag].id = que[i];//直接装入
    				pageFlag = noPage;
    				total++;
    				output(i);
    			}
    			else//淘汰页面
    			{
    				//调整输出顺序
    				int y = 0;
    				for (int k = 1; k < memoryk; k++)
    				{
    					memory2[y].id = memory[k].id;
    					y++;
    				}
    				y = 0;
    				for (int k = 0; k < memoryk - 1; k++)
    				{
    					memory[k].id = memory2[y].id;
    					y++;
    				}
    				memory[memoryk - 1].id = que[i];
    
    				//缺页处理
    				pageFlag = noPage;
    				total++;
    				output(i);
    			}
    		}
    	}
    }
    

    测试结果

    程序采用黑盒测试的方式,提交到 OJ 系统上进行在线评测
    测试
    可以看到,OJ 的测试用例全部通过

    心得体会

    通过本次实验,上机代码模拟实现了三种页面调度置换算法,对操作系统内部的页面置换方式有了更深刻的认识和感受。OPT 算法是理想型的算法,因为现实生活中根本不知道下一个到来的页面是哪一个,所以只能作为评判页面置换算法优劣的一个标准。LRU 算法的本质则是一种栈的实现。

    更多相关内容
  • 本设计通过请求页式存储管理中页面置换算法模拟设计,了解虚拟存储技术的特点,掌握请求页式管理的页面置换算法。 (1)从置换算法中任选 2 种(OPT、 FIFO、LRU、Clock);(2)建立页表;(3) 设计的输入数据要能...
  • 操作系统课请求分页存储管理模拟模拟程序,程序相对简单,通过这个模拟程序能够帮助学习者会更好的学习os,供有需要的人学习使用。
  • 编写一个请求页式存储管理模拟程序,通过对页面置换过程的模拟,加深对请求页式存储管理方式基本原理及实现过程的理解。 要求: 1. 从键盘输入页面访问序列及分配给进程的内存块数; 2. 分别采用OPT、FIFO和LRU...
  • 请求分页存储管理--课程设计报告和代码
  • 通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解。熟悉虚存管理的各种页面淘汰算法。通过编写和调试地址转换过程的模拟程序以加强对地址转换过程的了解。
  • 4、扩充页表,变成请求式的二维页表(增加存在位等)完成地址转换。 5、输入分配给本作业的块数,模拟作业执行的逻辑地址转换成页面调度次序; 6、分别采用OPT、FIFO、LRU置换算法,利用堆栈结构完成页面置换;记录...
  • 软 件 学 院 操作系统实验报告 专 业 软件工程 班 级 RB软工互 学 号 学生姓名 指导教师 PAGE 第 PAGE 16 页 共 NUMPAGES 16 页 实验四请求页式存储管理 一实验目的 深入理解请求页式存储管理的原理重点认识其中的...
  • 通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解。熟悉虚存管理的各种页面淘汰算法。通过编写和调试地址转换过程的模拟程序以加强对地址转换过程的了解。
  • 上海大学操作系统实验三(请求页式存储管理
  • 1. 请求分页存储管理方式 请求分页系统是建立在基本分页基础上的,为了能支持虚拟存储器功能,而增加了请求功能和页面置换功能。 相应地,每次调入和换出的基本单位都是长度固定的页面。因此,请求分页便称为...

    1. 请求分页存储管理方式

    请求分页系统是建立在基本分页基础上的,为了能支持虚拟存储器功能,而增加了请求调页功能页面置换功能

    相应地,每次调入和换出的基本单位都是长度固定的页面。因此,请求分页便称为目前最常用的一种实现虚拟存储器的方式。

    1.1 请求分页中的硬件支持

    为了实现请求分页,系统必须提供一定的硬件支持。计算机系统除了要求一定容量的内存和外存外,还需要有请求页表机制缺页中断机制以及地址变换机构

    1.1.1 请求页表机制

    在请求分页系统中需要的主要数据结构是请求页表,其基本作仍然是将用户地址空间中的逻辑地址映射为内存空间中的物理地址

    为了满足页面换进换出的需要,在请求页表中又增加了四个字段。

    在这里插入图片描述

    • 状态位(存在位)P用于指示该页是否已调入内存

    • 访问字段A用于记录本页在一段时间内被访问的次数

    • 修改位M标识该页在调入内存后是否被修改过

    • 外存地址用于指出该页在外存上的地址

    1.1.2 缺页中断机构

    在请求分页系统中,每当所要访问的页面不在内存时,便产生一缺页中断,请求OS将所缺之页调入内存。

    缺页中断是一种特殊的中断,它与一般的中断相比有着明显的区别,主要表现在两个方面:

    • 指令执行期间产生和处理中断信号
    • 一条指令在执行期间可能产生多次缺页中断

    在这里插入图片描述

    1.1.3 地址变换机构

    如图展示请求分页系统中的地址变换过程

    在这里插入图片描述

    2. 页面置换算法

    2.1 介绍

    在进程运行过程中,若其所要访问的页面不在内存,而需把它们调入内存,但内存已无空闲空间时,为了保证该进程能正常运行,系统必须从内存中调出一页程序或数据送到磁盘的对换区中。但应将哪个页面调出,须根据一定的算法来确定。通常,把选择换出页面的算法称为页面置换算法(Page-Replacement Algorithm)。

    不适当的算法可能会导致进程发生“抖动”(Thrashing),即刚被换出的页很快又要被访问,需要将它重新调入,此时又需要再选一页调出,而此刚被换出的页很快又要被访问,又需将它调入,因此我们称该进程发生了“抖动”。

    2.2 最佳(Optimal)置换算法

    介绍:

    最佳置换算法是一种较为极端,理想化的算法,它具有最好的性能,但实际上是无法实现的。通常以其为标准,来衡量其它算法的优劣。

    原理:

    其所选择的被淘汰页面将是以后永不使用的,或许是在最长(未来)时间内不再被访问的页面

    特点:

    • 可保证获得最低的缺页率

    • 因人们无法预知一个进程在内存的若干个页面中,究竟哪个是未来最长时间内不再被访问的,故该算法无法实现

    在这里插入图片描述

    在这里插入图片描述

    2.3 先进先出页面置换算法(FIFO)

    原理:

    总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单,只需把一个进程已调入的页面按先后次序链接成一个队列,并设置一个指针,称为替换指针,使它总指向最老的页面。

    特点:

    通常与进程实际运行的规律不相适应,因为有些页面会经常被访问,如全局变量、常用函数等,故可能是性能最差的算法,实际应用极少。

    在这里插入图片描述

    2.4 最近最久未使用置换算法(LRU,Least Recently Used)

    原理:

    该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间t。当需淘汰一个页面时,选择现有页面中其t值最大的,即最近最久未使用的页面予以淘汰。

    特点:

    • 该算法是根据页面调入内存后的使用情况做出决策的

    • 要求系统有较多的支持硬件,为了了解一个进程在内存中的各个页面各有多少时间未被进程访问,以及如何快速地知道哪一页是最近最久未使用的页面,须有寄存器两类硬件之一的支持。

    在这里插入图片描述

    2.5 最少使用置换算法(LFU, Least Frequently Used)

    原理:

    该算法为在内存中的每个页面设置一个移位寄存器,用来记录该页面被访问的频率。每次访问某页时,便将该移位寄存器的最高位置1,再每隔一定时间(例如100ms)右移一次。LFU置换算法的页面访问图与上面的LRU置换算法的访问图完全相同

    或者说,利用一套硬件既可实现LRU算法,又可实现LFU算法。

    特点:

    这种算法并不能真正反映出页面的使用情况,因为在每一时间间隔内,只是用寄存器的一位来记录页的使用情况。因此,在该时间间隔内,对某页访问一次和访问100次效果等效。

    2.6 简单的Clock置换算法

    介绍:

    LRU算法需要较多硬件支持,成本较高,实际应用中,大多采用LRU的近似算法。Clock算法就是用得较多的一种LRU近似算法。

    原理:

    当利用简单的Clock置换算法时,只需为每页设置一位访问位,再将内存中的所有页面都通过链接指针链接成一个循环队列。

    当某页被访问时,其访问位被置1。置换算法在选择一页淘汰时,只需检查页的访问位。如果是0,选择该页换出;若为1,则重新将它置0,暂不换出,给予该页第二次驻留内存的机会,

    再按照FIFO算法检查下一个页面。当检查到队列中的最后一个页面,若其访问为仍为1,则再返回到队首去检查第一个页面。

    特点:

    该算法是循环地检查各页面的使用情况,故称为Clock算法

    因该算法只有一位访问位,只能用其表示该页是否已经使用过,而置换是将未使用过的页面换出去,故该算法又称为最近未用算法或者NRU(Not Recently Used)算法

    在这里插入图片描述

    2.7 页面缓冲算法(PBA,Page Buffering Algorithm)

    内存分配策略上采用了可变分配和局部置换方式,系统为每个进程分配一定数目的物理块,系统自己保留一部分空闲物理块。

    为了能显著地降低页面换进、换出地频率,在内存中设置了如下两个链表

    • 空闲页面链表

    实际上该链表是一个空闲物理块链表,是系统掌握地空闲物理块,用于分配给频繁发生缺页的进程,已降低该进程的缺页率。

    当进程需要读入一个页面时,便可利用空闲物理链表中的第一个物理块来装入该页;

    当有一个未被修改的页要换出时,实际上并不将它换出到外存,而是把它们所在的物理块挂在空闲链表的末尾

    • 修改页面链表

    该链表是由已修改的页面所形成的链表。设置该链表的目的是为了减少已修改页面换出的次数。

    当进程需要将一个已修改的页面换出时,系统并不立即把它换出到外存上,而是将它所在的物理块挂在修改页面链表的末尾

    • PBA算法特点:

    1. 显著地降低了页面换进、换出的频率,使磁盘I/O的操作次数大为减少,减少了页面换进、换出的开销。
    2. 正是由于换入换出的开销大幅度减小,才能使其采用一种较简单的置换策略,如先进先出(FIFO)算法,它并不需要特殊硬件的支持,实现起来非常简单。

    参考:《计算机操作系统》(第四版,汤小凤)

    看教材枯燥,码字记录提神,根据计算机操作系统(第四版,汤小凤)个人整理,仅作学习记录 :)
    
    展开全文
  • os 虚拟存储器 请求分页存储管理方式

    请求分页系统是建立在基本分页基础上的,为了能支持虚拟存储器功能,而增加了请求调页功能页面置换功能。相应地,每次调入和换出的基本单位都是长度固定的页面,这使得请求分页系统在实现上要比请求分段系统简单(后者在换进和换出时是可变长度的段)。因此,请求分页便成为目前最常用的一种实现虚拟存储器的方式。

    请求分页中的硬件支持

    为了实现请求分页,系统必须提供一定的硬件支持。计算机系统除了要求一定容量的内存和外存外,还需要有请求页表机制、缺页中断机构以及地址变换机构

    1.请求页表机制

    在请求分页系统中需要的主要数据结构是请求页表,其基本作用仍然是将用户地址空间中的逻辑地址映射为内存空间中的物理地址。为了满足页面换进换出的需要,在请求页表中又增加了四个字段。这样,在请求分页系统中的每个页表应含以下诸项:
    在这里插入图片描述

    • (1)状态位(存在位) P :由于在请求分页系统中,只将应用程序的一部分调入内存,还有一部分仍在外存磁盘上,故须在页表中增加一个存在位字段。由于该字段仅有一位,故又称位字。它用于指示该页是否已调入内存,供程序访问时参考
    • (2)访问字段 A :用于记录本页在一段时间内被访问的次数,或记录本页最近已有多长时间未被访问,提供给置换算法(程序)在选择换出页面时参考。
    • (3)修改位 M标识该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本,因此,在置换该页时,若未被修改,就不需再将该页写回到外存上,以减少系统的开销和启动磁盘的次数;若已被修改,则必须将该页重写到外存上,以保证外存中所保留的副本始终是最新的。简而言之, M 位供置换页面时参考。
    • (4)外存地址:用于指出该页在外存上的地址,通常是物理块号,供调入该页时参考。

    2.缺页中断机构

    在请求分页系统中,每当所要访问的页面不在内存时,便产生一缺页中断,请求 OS 将所缺之页调入内存。缺页中断作为中断,它们同样需要经历诸如保护 CPU 环境、分析中断原因、转入缺页中断处理程序进行处理,以及在中断处理完成后再恢复 CPU 环境等几个步骤。但缺页中断又是一种特殊的中断,它与一般的中断相比有着明显的区别,主要表现在下面两个方面:

    • (1)在指令执行期间产生和处理中断信号。通常, CPU 都是在一条指令执行完后,才检查是否有中断请求到达。若有,便去响应,否则,继续执行下一条指令。然而,缺页中断是在指令执行期间,若发现所要访问的指令或数据不在内存时,便立即产生和处理缺页中断信号,以便能及时将所缺之页面调入内存。
    • (2)一条指令在执行期间可能产生多次缺页中断。在图5-1中示出了一个例子。如在执行一条指令 copy A to B 时,可能要产生6次缺页中断,其中指令本身跨了两个页面, A 和 B 又分别各是一个数据块,也都跨了两个页面。基于这些特征,系统中的硬件机构应能保存多次中断时的状态,并保证最后能返回到中断前产生缺页中断的指令处继续执行
      在这里插入图片描述

    3.地址变换机构

    请求分页系统中的地址变换机构是在分页系统地址变换机构的基础上,为实现虚拟存储器,再增加了某些功能所形成的,如产生和处理缺页中断,以及从内存中换出一页的功能等等。下图示出了请求分页系统中的地址变换过程。
    在这里插入图片描述
    在进行地址变换时,首先检索快表,试图从中找出所要访问的页。若找到,便修改页表项中的访问位,供置换算法选换出页面时参考。对于写指令,还须将修改位置成“1”,表示该页在调入内存后已被修改。然后利用页表项中给出的物理块号和页内地址形成物理地址。地址变换过程到此结束。
    如果在快表中未找到该页的页表项,则应到内存中去查找页表,再从找到的页表项中的状态位 P 来了解该页是否已调入内存。若该页已调入内存,这时应将该页的页表项写入快表。当快表已满时,则应先调出按某种算法所确定的页的页表项,然后再写入该页的页表项;若该页尚未调入内存,这时应产生缺页中断,请求 OS 从外存把该页调入内存。


    请求分页中的内存分配

    在为进程分配内存时,将涉及到三个问题:

    • 第一,为保证进程能正常运行,所需要的最小物理块数的确定;
    • 第二,在为每个进程分配物理块时,应采取什么样的分配策略,即所分配的物理块是固定的,还是可变的;
    • 第三,为不同进程所分配的物理块数,是采取平均分配算法,还是根据进程的大小按比例分配。

    1.最小物理块数的确定

    一个显而易见的事实是,随着为每个进程所分配的物理块的减少,将使进程在执行中的缺页率上升,从而会降低进程的执行速度。为使进程能有效地工作,应为它分配一定数目的物理块,但这并不是最小物理块数的概念。
    最小物理块数是指能保证进程正常运行所需的最小物理块数,当系统为进程分配的物理块数少于此值时,进程将无法运行。至于进程应获得的最少物理块数,与计算机的硬件结构有关,取决于指令的格式、功能和寻址方式。对于某些简单的机器,若是单地址指令,且采用直接寻址方式,则所需的最少物理块数为2。其中,一块是用于存放指令的页面,另一块则是用于存放数据的页面。如果该机器允许间接寻址,则至少要求有三个物理块。对于某些功能较强的机器,其指令长度可能是两个或多于两个字节,因而其指令本身有可能跨两个页面,且源地址和目标地址所涉及的区域也都可能跨两个页面。正如前面所介绍的在缺页中断机构中要发生6次中断的情况一样,对于这种机器,至少要为每个进程分配6个物理块,以装入6个页面。

    2.内存分配策略

    在请求分页系统中,可采取两种内存分配策略,即固定可变分配策略。在进行置换时,也可采取两种策略,即全局置换局部置换。于是可组合出以下三种适用的策略。

    • 1)固定分配局部置换( Fixed Allocation , Local Replacement )
      所谓固定分配,是指为每个进程分配一组固定数目的物理块,在进程运行期间不再改变。所谓局部置换,是指如果进程在运行中发现缺页,则只能从分配给该进程的 n 个页面中选出一页换出,然后再调入一页,以保证分配给该进程的内存空间不变。采用该策略时,为每个进程分配多少物理块是根据进程类型(交互型或批处理型等)或根据程序员、程序管理员的建议来确定的。实现这种策略的困难在于:应为每个进程分配多少个物理块难以确定。若太少,会频繁地出现缺页中断,降低了系统的吞吐量。若太多,又必然使内存中驻留的进程数目减少,进而可能造成 CPU 空闲或其它资源空闲的情况,而且在实现进程对换时,会花费更多的时间。
    • 2)可变分配全局置换( Variable Allocation , Global Replacement )
      所谓可变分配,是指先为每个进程分配一定数目的物理块,在进程运行期间,可根据情况做适当的增加或减少。所谓全局置换,是指如果进程在运行中发现缺页,则将 os 所保留的空闲物理块(一般组织为一个空闲物理块队列)取出一块分配给该进程,或者以所有进程的全部物理块为标的,选择一块换出,然后将所缺之页调入。这样,分配给该进程的内存空间就随之增加。可变分配全局置换这可能是最易于实现的一种物理块分配和置换策略,已用于若干个 os 中。在采用这种策略时,凡产生缺页(中断)的进程,都将获得新的物理块,仅当空闲物理块队列中的物理块用完时, os 才能从内存中选择一页调出。被选择调出的页可能是系统中任何一个进程中的页,因此这个被选中的进程拥有的物理块会减少,这将导致其缺页率增加。
    • 3)可变分配局部置换( Variable Allocation , Local Replacement )
      该策略同样是基于进程的类型或根据程序员的要求,为每个进程分配一定数目的物理块,但当某进程发现缺页时,只允许从该进程在内存的页面中选择一页换出,这样就不会影响其它进程的运行。如果进程在运行中频繁地发生缺页中断,则系统须再为该进程分配若干附加的物理块,直至该进程的缺页率减少到适当程度为止。反之,若一个进程在运行过程中的缺页率特别低,则此时可适当减少分配给该进程的物理块数,但不应引起其缺页率的明显增加。

    3.物理块分配算法

    在采用固定分配策略时,如何将系统中可供分配的所有物理块分配给各个进程,可采用下述几种算法;

    • (1)平均分配算法,即将系统中所有可供分配的物理块平均分配给各个进程。例如,当系统中有100个物理块,有5个进程在运行时,每个进程可分得20个物理块。这种方式貌似公平,但由于未考虑到各进程本身的大小,会造成实际上的不公平。假设系统平均分配给每个进程20个物理块,这样,一个进程只有10页,闲置了10个物理块,而另外一个进程有200页,也仅被分配了20块,显然,后者必然会有很高的缺页率。
    • (2)按比例分配算法,即根据进程的大小按比例分配物理块。如果系统中共有 n 个进程,每个进程的页面数为 Si,则系统中各进程页面数的总和为:
      S = ∑ i = 1 n S i S=\sum_{i=1}^{n}S_i S=i=1nSi
      又假定系统中可用的物理块号总数为m,则每个进程所能分到的物理块号为bi可由下式计算:
      b   i   = S   i   S × m b~i~=\frac{S~i~}{S}\times m b i =SS i ×m
      这里, bi 应该取整,它必须大于最小物理块数
    • (3)考虑优先权的分配算法。在实际应用中,为了照顾到重要的、紧迫的作业能尽快地完成,应为它分配较多的内存空间。通常采取的方法是把内存中可供分配的所有物理块分成两部分:一部分按比例地分配给各进程;另一部分则根据各进程的优先权进行分配,为高优先进程适当地增加其相应份额。在有的系统中,如重要的实时控制系统,则可能是完全按优先权为各进程分配其物理块的。

    页面调入策略

    为使进程能够正常运行,必须事先将要执行的那部分程序和数据所在的页面调入内存。现在的问题是:

    • (1)系统应在何时调入所需页面;
    • (2)系统应从何处调入这些页面;
    • (3)是如何进行调入的。

    1.何时调入页面

    为了确定系统将进程运行时所缺的页面调入内存的时间,可采取预调页策略或请求调页策略,现分述如下。

    (1)预调页策略。

    如果进程的许多页是存放在外存的一个连续区域中,一次调入若干个相邻的页会比一次调入一页更高效些。但如果调入的一批页面中的大多数都未被访问, 则又是低效的。于是便考虑采用一种以预测为基础的预调页策略,将那些预计在不久之后会被访问的页面预先调入内存。如果预测较准确,那么这种策略显然是很有吸引力的。但遗憾的是,目前预调页的成功率仅约50%。
    但预调页策略又因其特有的长处取得了很好的效果。首先可用于在第一次将进程调入内存时,此时可将程序员指出的那些页先调入内存。其次是,在采用工作集的系统中,每个进程都具有一张表,表中记求有运行时的工作集,每当程序被调度运行时,将工作集中的所有页调入内存。

    (2)请求调页策略。

    当进程在运行中需要访问某部分程序和数据时,若发现其所在的页面不在内存,便即提出请求,由 OS 将其所需页面调入内存。由请求调页策略所确定调入的页是一定会被访问的,再加之请求调页策略比较易于实现,故在目前的虚拟存储器中,大多来用此策略。但这种策略每次仅调入一页,故须花费较大的系统开销增加了磁盘 I / O 的启动频率

    2.从何处调入页面

    将请求分页系统中的外存分为两部分:用于存放文件的文件区和用于存放对换页面的对换区。通常,由于对换区是采用连续分配方式,而文件区是采用离散分配方式,所以对换区的数据存取(磁盘 I / O )速度比文件区的高。这样,每当发生缺页请求时,系统应从何处将缺页调入内存,可分成如下三种情况进行:
    (1)系统拥有足够的对换区空间,这时可以全部从对换区调入所需页面,以提高调页速度。为此,在进程运行前,便须将与该进程有关的文件从文件区拷贝到对换区。
    (2)系统缺少足够的对换区空间,这时凡是不会被修改的文件,都直接从文件区调入;而当换出这些页面时,由于它们未被修改,则不必再将它们重写到磁盘(换出),以后再调入时,仍从文件区直接调入。但对于那些可能被修改的部分,在将它们换出时便须调到对换区,以后需要时再从对换区调入。
    (3) UNIX 方式。由于与进程有关的文件都放在文件区,故凡是未运行过的页面,都应从文件区调入。而对于曾经运行过但又被换出的页面,由于是被放在对换区,因此在下次调入时应从对换区调入。由于 UNIX 系统允许页面共享,因此,某进程所请求的页面有可能已被其它进程调入内存,此时也就无需再从对换区调入。

    3.页面调入过程

    每当程序所要访问的页面未在内存时(存在位为“0”),便向 CPU 发出一缺页中断,中断处理程序首先保留 CPU 环境,分析中断原因后转入缺页中断处理程序。该程序通过查找页表得到该页在外存的物理块后,如果此时内存能容纳新页,则启动磁盘I/O,将所缺之页调入内存,然后修改页表。如果内存已满,则须先按照某种置换算法,从内存中选出一页准备换出;如果该页未被修改过(修改位为“0”),可不必将该页写回磁盘;但如果此页已被修改(修改位为“1”),则必须将它写回磁盘,然后再把所缺的页调入内存,并修改页表中的相应表项,置其存在位为“1”,并将此页表项写入快表中。在缺页调入内存后,利用修改后的页表形成所要访问数据的物理地址,再去访问内存数据。整个页面的调入过程对用户是透明的。

    4.缺页率

    假设一个进程的逻辑空间为 n 页,系统为其分配的内存物理块数为 m ( m ≤ n )。如果在进程的运行过程中,访问页面成功(即所访问页面在内存中)的次数为 S ,访问页面失败(即所访问页面不在内存中,需要从外存调入)的次数为 F ,则该进程总的页面访问次数为 A = S + F ,那么该进程在其运行过程中的缺页率即为
    f = F A f=\frac{F}{A} f=AF
    通常,缺页率受到以下几个因素的影响:

    • (1)页面大小。页面划分较大,则缺页率较低;反之,缺页率较高。
    • (2)进程所分配物理块的数目。所分配的物理块数目越多,缺页率越低;反之则越高。
    • (3)页面置换算法。算法的优劣决定了进程执行过程中缺页中断的次数,因此缺页率是衡量页面置换算法的重要指标。
    • (4)程序固有特性。程序本身的编制方法对缺页中断次数有影响,根据程序执行的局部性原理,程序编制的局部化程度越高,相应执行时的缺页程度越低

    事实上,在缺页中断处理时,当由于空间不足,需要置换部分页面到外存时,选择被置换页面还需要考虑到置换的代价,如页面是否被修改过。没有修改过的页面可以直接放弃,而修改过的页面则必须进行保存,所以处理这两种情况时的时间也是不同的。假设被置换的页面被修改的概率是 β,其缺页中断处理时间为ta,被置换页面没有被修改的缺页中断时间为 tb,那么,缺页中断处理时间的计算公式为
    t = β × t   a   + ( 1 − β ) × t   b   t=\beta\times t~a~+(1-\beta)\times t~b~ t=β×t a +(1β)×t b 


    展开全文
  • 请求分页存储管理Python实现源代码+课设报告文档-海南大学信息学院操作系统课设。请求分页存储管理Python实现源代码+课设报告文档-海南大学信息学院操作系统课设。
  • 操作系统原理 实验名称 虚拟页式管理 姓 名 学号 专业班级 实验日期 成 绩 指导教师 实验目的实验原理主要仪器设备实验内容与步骤实验数据记录与处理实验 结果与分析问题建议 实验二 模拟请求页式存储管理中硬件的...
  • 请求分页存储管理系统设计与实现可课程设计
  • 请求分页存储管理方式

    千次阅读 2021-04-29 16:39:41
    请求分页中的硬件支持 1.页表机制 ●基本作用:地址转换 ●增加页表字段,供程序在换入换出时参考 状态位P:用于指示该是否已调入内存 访问字段A:记录本在一段时间内被访问的次数 修改位M:该在调入内存后是否被...

    请求分页中的硬件支持
    1.页表机制
    ●基本作用:地址转换
    ●增加页表字段,供程序在换入换出时参考
    在这里插入图片描述
    状态位P:用于指示该页是否已调入内存
    访问字段A:记录本页在一段时间内被访问的次数
    修改位M:该页在调入内存后是否被修改过
    外存地址:指示该页在外存上的地址(物理块号)
    2.缺页中断机构:
    ●缺页中断与其他中断的不同:
    (1)在指令执行期间产生和处理中断信号
    (2)一条指令在执行期间可能产生多次缺页中断
    在这里插入图片描述
    3.地址变换机构
    在这里插入图片描述
    内存分配策略和分配算法
    1.最小物理块数的确定:
    ●保证进程正常运行所需的最小物理块数;
    ●与硬件结构有关,取决于指令的格式、功能和寻址方式。
    2.物理块的分配策略:
    ●两种内存分配策略:
    ■固定分配:为进程分配的物理块数固定不变。
    ■可变分配:先为每个进程分配一定 数目的物理块,若发生缺页中断,再增加物理块数。
    ●两种置换策略:
    ■局部置换:只能将自己的某个内存页换出。
    ■全局置换:可将系统中任一进程的内存页换出。
    ●组合出以下三种适用策略:
    ■(1) 固定分配局部置换
    ■(2) 可变分配全局置换
    ■(3)可变分配局部置换
    3.物理块分配算法:
    ●(1)平均分配算法
    ●(2)按比例分配算法:根据进程大小按比例分
    配(Si/s)*m (m:物理块总数,S:各进程页面总数)
    ●(3)考虑优先权的分配算法:一-部分按比例分配;另一部分为优先权高的进程增加分配份额
    调页策略
    1.调入页面的时机:
    ●预调页策略:进程首次调入内存时,由程序员指出应该先调入哪些页。
    ●请求调页策略:进程运行中发生缺页时,提出请求,由OS将其所需页面调入内存。
    2.确定从何处调入页面:
    请求分页系统将外存分为两部分:
    文件区(离散分配)、 对换区(连续分配)
    ●发生缺页请求时,有以下三种情况:
    系统拥有足够的对换区空间
    系统缺少足够的对换区空间
    UNIX方式
    3.页面调入过程:
    ①若发生缺页,便向CPU发出缺页中断
    ②中断处理程序保存CPU环境,转中断处理程序
    ③该程序查找页表,得到该页在外存中的块号
    ④若内存未满,启动磁盘I/O调入页面;若内存已满,先置换再调入
    ⑤修改页表项内容,并写入快表。

    展开全文
  • 操作系统 请求分页存储管理

    千次阅读 2020-12-22 13:06:04
    请求分页存储管理中的页表机制 缺页中断机构 地址转换 置换算法 分配和置换策略 工作集及抖动现象的消除 请求分页存储管理的优缺点 请求分页存储管理中的页表机制 系统需要解决的问题 系统如何获知进程当前...
  • C语言模拟实现虚拟存储管理(请求分页存储管理

    千次阅读 多人点赞 2020-06-25 23:19:08
    本实验的目的是:通过编程模拟实现请求分页存储管理中硬件地址转换过程、缺页中断处理过程,以及先进先出页面置换算法,加深对页式虚拟存储管理的理解,了解虚拟存储技术的特点,掌握请求页式存储管理的页面置换方法...
  • 申请缓冲区,将一个进程的逻辑地址空间划分成若干个大小相等的部分,每一部分称做页面或。每都有一个编号,叫做页号,页号从0开始依次编排,如0,1,2……。设置等大小的内存块。初始状态:将数据文件的第一个...
  • 通过模拟实现请求页式存储管理的几种基本页面置换算法,了解虚拟存储技术的特点,掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程,并比较它们的效率。 二、实验内容与基本要求 基于一个...
  • 分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片,称为页面或,并为各加以编号,从0开始,如第0、第1等。相应地,也把内存空间分成与页面相同大小的若干个存储块,称为(物理)块或框(frame)...
  • 5.2请求分页存储管理方式

    千次阅读 2020-05-22 11:32:10
    将虚拟技术和分页存储结合起来,那么当一个程序内存无法装下时,就先装入部分程序执行,分页存储管理方式是将程序分成一个个,那么内存中也就是先存放部分。 步骤: 在虚拟技术的管理下,页表的属性不在页号和...
  • # include<stdlib.h> # include<stdio.h> # define pagesize 8 // 页面尺寸大小 typedef struct BLOCK // 声明一种新类型 --物理块类型 { int pagenum; // 页号 int accessed; // 访问量其值表示多久未被访问 }BLOCK...
  • 这是操作系统中请求分页式存储管理中的页面置换算法,有先进先出算法,OPT置换算法,LRu置换算法。
  • C++编写的请求分页储存管理置换算法模拟程序,模拟OPT,FIFO和LRU算法。可以输入序列也可以随机生成访问序列。可以输出整个调度的流程(表),缺页次数和缺页率。
  • 模拟请求分页存储管理一、实验内容二、实验要求三、实验过程1、设计思想2、数据结构四、实验代码五、实验结果 一、实验内容 模拟请求分页存储管理方式。 二、实验要求 1、模拟请求分页存储管理方式,采用最近最久未...
  • 分页式虚拟存储管理中,要求通过键盘输入分配给一个作业的物理块数和作业依次访问的10个页面号,采用先进先出(FIFO)页面置换后,顺序输出缺页中断时所淘汰的页面号,并计算缺页中断率。 #include<cstdio> ...
  • 题目:1。存储管理 描述请求分页存储管理。 一. 产生一个作业及作业页面序列P(pi),例如:P(0,2,3,4,1,5,2,3,0,4,1,5)。 二.分配物理内存块数M。 三.采用FIFO,LRU置换算法。
  • 请求页式存储管理

    2011-12-31 08:11:24
    建立相关的数据结构:存储块表、页表等; (2) 实现基本分页存储管理,如...(3) 在基本分页的基础上实现请求分页存储管理; (4) 给定一批作业/进程,选择一个分配或回收模拟; (5) 将整个过程可视化显示出来。
  • 目的:(1)通过编写程序实现请求分页存储管理页面Optimal、FIFO、LRU调度算法,使学生掌握虚拟存储管理中有关缺页处理方法等内容,巩固有关虚拟存储管理的教学内容。 (2)了解Windows2000/XP中内存管理机制,掌握...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 148,861
精华内容 59,544
关键字:

请求页式存储管理