精华内容
下载资源
问答
我要提问
  • 操作系统实验3—实现请求页式存储管理模拟程序
    千次阅读
    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 算法的本质则是一种栈的实现。

    lru 页面替换算法
    更多相关内容

  • 操作系统实验三（请求页式存储管理）

     2021-03-23 21:48:08
    上海大学操作系统实验三（请求页式存储管理）
    收起

  • 请求页式存储管理及请求页式存储管理中常用页面置换算法模拟.doc

     2020-07-30 15:28:11
    软 件 学 院 操作系统实验报告 专 业 软件工程 班 级 RB软工互 学 号 学生姓名 指导教师 PAGE 第 PAGE 16 页 共 NUMPAGES 16 页 实验四请求页式存储管理 一实验目的 深入理解请求页式存储管理的原理重点认识其中的...
    收起

  • 实现请求页式存储管理模拟程序

     2018-01-26 16:47:31
    编写一个请求页式存储管理模拟程序，通过对页面置换过程的模拟，加深对请求页式存储管理方式基本原理及实现过程的理解。 要求： 1. 从键盘输入页面访问序列及分配给进程的内存块数； 2. 分别采用OPT、FIFO和LRU...
    收起

  • 动态页式存储管理的模拟实现C语言.doc

     2019-05-14 16:52:00
    基于C语言的动态页式存储管理的模拟实现，操作系统课程实验报告
    收起

  • 存储管理系统设计（页式存储管理模拟系统）

     2021-02-13 10:51:58
    本次课程设计采用一些常用的存储器分配算法，设计一个请求页式存储管理模拟系统并调试运行。通过随机数产生一个指令序列，将指令序列变成为页地址流，计算并输出下述各种算法在不同内存容量下的命中率。
    收起

  • 页式存储管理的模拟程序 FIFO

     2016-11-30 22:55:40
    通过编写和调试请求页式存储管理的模拟程序以加深对请求页式存储管理方案的理解。 为了简单起见。页面淘汰算法采用 FIFO页面淘汰算法，并且在淘汰一页时，判断它是否被改写过，如果被修改过，将它写回到辅存。 ...
    收起

  • 请求页式存储管理实验

     2016-11-11 14:09:00
    通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解。熟悉虚存管理的各种页面淘汰算法。通过编写和调试地址转换过程的模拟程序以加强对地址转换过程的了解。
    收起

  • 操作系统-页式存储管理

     2018-12-12 18:33:54
    js实现操作系统的页式存储管理的模拟
    收起
    操作系统

  • 段页式存储管理地址转换.cpp

     2019-12-03 22:36:26
    段页式存储管理地址转换 广工操作系统实验三
    收起

  • 操作系统课程设计：页式存储管理地址变换模拟过程

     2017-11-14 18:01:44
    采用多道程序设计思想设计一个程序，模拟页式存储管理地址变换的过程，可采用FIFO、LRU、LFU、OPT四种页面置换算法。使用的相关的开发软件为NetBeans IDE 8.2。 解决的主要问题： （1）需要建立访问页表线程、访问快...
    收起
    操作系统

  • 模拟请求页式存储管理中硬件的地址转换和缺页中断,并用先进先出调度算法(FIFO)处理缺页中断.docx

     2020-08-21 08:03:27
    课程名称 操作系统原理 实验名称 虚拟页式管理 姓 名 学号 专业班级 实验日期 成 绩 指导教师 实验目的实验原理主要仪器设备实验内容与步骤实验数据记录与处理实验 结果与分析问题建议 实验二 模拟请求页式存储管理...
    收起

  • 动态页式存储管理_动态页式存储管理_页式存储管理_

     2021-09-30 07:58:07
    动态页式存储管理
    收起

  • 页式存储管理、段式存储管理、段页式存储管理

     千次阅读 2020-07-24 21:51:17
    目录页式存储管理段式存储管理分页和分段存储管理的主要区别段页式存储管理 页式存储管理 1. 基本原理 页式存储管理是把主存储器划分成大小相等的若干区域，每个区域称为一块，并对它们加以顺序编号，如0#块、1#块...

    目录

    页式存储管理

    1. 基本原理

    页式存储管理是把主存储器划分成大小相等的若干区域，每个区域称为一块，并对它们加以顺序编号，如0#块、1#块等等。与此对应，用户程序的逻辑地址空间划分成大小相等的若干页，同样为它们加以顺序编号，从0开始，如第0页、第1页等。 页的大小与块的大小相等。
    分页式存储管理的逻辑地址由两部分组成：页号和页内地址。其格式为：
    在这里插入图片描述

    2. 存储空间的分配与去配
    分页式存储管理把主存空间划分成若干块，以块为单位进行主存空间的分配。由于块的大小是固定的，系统可以采用一张主存分配表来记录已分配的块、尚未分配的块以及当前剩余的空闲块总数。最简单的办法可用一张“位示图”来记录主存的分配情况。
    例如主存的用户区被划分成512块，则可用字长为32位的16个字的位示图来构成一张主存分配表，位示图中的每一位与一个物理块对应，用0/1表示对应块的占用标志（空闲/已占用），另用一个字节记录当前系统的剩余空闲块总数。
    在这里插入图片描述
    进行主存分配时，首先查看空闲块总数是否能够满足作业要求，若不能满足，则不进行分配；若能满足，则从位示图中找出为“0”的位，并且将其占用标志置为“1”，并从空闲块总数中减去本次占用的块数，按找到的位计算出对应的块号，建立该作业的页表，并把作业装入对应的物理块中。
    由于每一块的大小相等，在位示图中查找到一个为“0”的位后，根据它所在的字号、位号，按如下公式可计算出对应的块号：
    块号＝字号×字长＋位号
    当一个作业执行结束时，则应该收回作业所占的主存块。根据归还的块号计算出该块在位示图中对应的位置，将占用标志修改为“0”，同时把归还块数加入到空闲块总数中。假定归还块的块号为i，则在位示图中对应的位置为：
    字号＝[ i / 字长 ]， 位号＝i mod 字长
    其中[ ]表示对i除以字长后取其整数，而mod表示对i除以字长后取其余数部分。

    3. 页表与地址转换
    在分页式存储管理系统中，允许将作业的每一页离散地存储在主存的物理块中，但系统必须能够保证作业的正确运行，即能在主存中找到每个页面所对应的物理块。为此，系统为每个作业建立了一张页面映像表，简称页表。页表实现了从页号到主存块号的地址映像。作业中的所有页（0~n）依次地在页表中记录了相应页在主存中对应的物理块号。页表的长度由进程或作业拥有的页面数决定。
    在这里插入图片描述
    调度程序在选择作业后，将选中作业的页表始址送入硬件设置的页表控制寄存器中。地址转换时，只要从页表寄存器中就可找到相应的页表。当作业执行时，分页地址变换机构会自动将逻辑地址分为页号和页内地址两部分，以页号位索引检索页表，如果页表中无此页号，则产生一个“地址错”的程序性中断事件；如果页表中有此页号，则可得到对应的主存块号，再按逻辑地址中的页内地址计算出欲访问的主存单元的物理地址。因为块的大小相等，所以
    物理地址=块号×块长＋页内地址
    在这里插入图片描述

    4. 总结

    • 目的
      减少分区管理的“碎片”，提高内存利用率。
    • 实现原理
      各个进程的虚拟空间被划分为若干个长度相等的页，并为各页加以编号，如第0页、第1页等 ；
      内存空间也按相同的页大小划分为存储块，称为(物理)块或页框(frame)， 也同样为它们加以编号，如0＃块、1＃块等等。
      为进程分配内存时，以块为单位将进程的若干个页分别装入到多个可以不相邻接的物理块中。
      采用页表进行页和块的一一对应。
      在这里插入图片描述

    段式存储管理

    用户编制的程序是由若干段组成的：一个程序可以由一个主程序、若干子程序、符号表、栈以及数据等若干段组成。每一段都有独立、完整的逻辑意义，每一段程序都可独立编制，且每一段的长度可以不同。
    段式存储管理支持用户的分段观点，具有逻辑上的清晰和完整性，它以段为单位进行存储空间的管理。

    1. 原理
    每个作业由若干个相对独立的段组成，每个段都有一个段名，为了实现简单，通常可用段号代替段名，段号从“0”开始，每一段的逻辑地址都从“0”开始编址，段内地址是连续的，而段与段之间的地址是不连续的。
    其逻辑地址由段号和段内地址两部分所组成：
    在这里插入图片描述

    2. 空间的分配与去配
    分段式存储管理是在可变分区存储管理方式的基础上发展而来的。在分段式存储管理方式中，以段为单位进行主存分配，每一个段在主存中占有一个连续空间，但各个段之间可以离散地存放在主存不同的区域中。为了使程序能正常运行，即能从主存中正确找出每个段所在的分区位置，系统为每个进程建立一张段映射表，简称“段表”。每个段在表中占有一个表项，记录该段在主存储器中的起始地址和长度。段表实现了从逻辑段到主存空间之间的映射。
    在这里插入图片描述
    如果在装入某段信息时找不到满足该段地址空间大小的空闲区，则可采用移动技术合并分散的空闲区，以利于大作业的装入。
    当采用分段式存储管理的作业执行结束后，它所占据的主存空间将被回收，回收后的主存空间登记在空闲分区表中，可以用来装入新的作业。系统在回收空间时同样需要检查是否存在与回收区相邻的空闲分区，如果有，则将其合并成为一个新的空闲分区进行登记管理。
    段表存放在主存储器中，在访问一个数据或指令时至少需要访问主存两次以上。为了提高对段表的存取速度，通常增设一个相联寄存器，利用高速缓冲寄存器保存最近常用的段表项。

    3. 地址转换与存储保护
    段式存储管理采用动态重定位方式装入作业，作业执行时通过硬件的地址转换机构实现从逻辑地址到物理地址的转换工作，段表的表目起到了基址寄存器和限长寄存器的作用，是硬件进行地址转换的依据。
    在这里插入图片描述

    分页和分段存储管理的主要区别

    分页和分段系统都采用离散分配主存方式，都需要通过地址映射机构来实现地址变换，有许多相似之处。但两者又是完全不同的。具体表现如下。

    • 页是信息的物理单位，是系统管理的需要而不是用户的需要；而段则是信息的逻辑单位，它含有一组意义相对完整的信息，分段是为了更好地满足用户的需要。
    • 页的大小固定且由系统决定，因而一个系统只能有一种大小的页面；而段的长度却不固定，由用户所编写的程序决定，通常由编译程序对源程序进行编译时根据信息的性质来划分。
    • 分页式作业的地址空间是一维的，页间的逻辑地址是连续的；而分段式作业的地址空间则是二维的，段间的逻辑地址是不连续的。

    段页式存储管理

    段式存储管理支持了用户的观点，但每段必须占据主存储器的连续区域，有可能需要采用移动技术汇集主存空间，为此，兼用分段和分页的方法，构成可分页的段式存储管理，通常被称为是“段页式存储管理”。段页式存储管理兼顾了段式在逻辑上的清晰和页式在管理上方便的优点。

    1. 原理
    用户对作业采用分段组织，每段独立编程，在主存空间分配时，再把每段分成若干个页面，这样每段不必占据连续的主存空间，可把它按页存放在不连续的主存块中。
    段页式存储管理的逻辑地址格式如下：
    在这里插入图片描述
    段页式存储管理为每一个装入主存的作业建立一张段表，且对每一段建立一张页表。段表的长度由作业分段的个数决定，段表中的每一个表目指出本段页表的始址和长度。页表的长度则由对应段所划分的页面数所决定，页表中的每一个表目指出本段的逻辑页号与主存物理块号之间的对应关系。
    在这里插入图片描述

    2. 地址转换机制
    执行指令时，地址机构根据逻辑地址中的段号查找段表，得到该段的页表始址，然后根据逻辑地址中的页号查找该页表，得到对应的主存块号，由主存块号与逻辑地址中的页内地址形成可访问的物理地址。如果逻辑地址中的段号超出了段表中的最大段号或者页号超出了该段页表中的最大页号，都将形成“地址越界”的程序性中断事件。
    可以看出，由逻辑地址到物理地址的变换过程中，需要三次访问主存，第一次是访问主存中的段表，获得该段对应页表的始址，第二次是访问页表，获得指令或数据的物理地址，最后再按物理地址存取信息。
    在这里插入图片描述

    3. 特点

    • 每一段分为若干页，再按页式管理，页间不要求连续；
    • 用分段方法分配管理作业或进程，用分页方法分配管理内存；
    • 兼有段式和页式管理的优点,系统复杂性和开销增大.
    收起
    展开全文
    操作系统

  • 页式存储和段页式存储的地址转换过程

     2021-05-20 15:06:15
    页式存储-地址转换访问2次内存，第一次是页表，第二次是真正的物理内存。二级页表，访问3次内存两个例子的形式讲解逻辑地址到物理地址的转换：(1)页系统页表: 页号: 0 1 2 3 4 5 块号: 3 5 x 4 1 2每页2KB 计算逻辑...

    一.页式存储-地址转换

    访问2次内存，第一次是页表，第二次是真正的物理内存。

    二级页表，访问3次内存

    两个例子的形式讲解逻辑地址到物理地址的转换：

    (1)

    0818b9ca8b590ca3270a3433284dd417.png

    0818b9ca8b590ca3270a3433284dd417.png页系统页表

    0818b9ca8b590ca3270a3433284dd417.png

    0818b9ca8b590ca3270a3433284dd417.png: 页号: 0 1 2 3 4 5

    块号: 3 5 x 4 1 2

    每页

    0818b9ca8b590ca3270a3433284dd417.png

    0818b9ca8b590ca3270a3433284dd417.png

    0818b9ca8b590ca3270a3433284dd417.png2KB 计算逻辑

    0818b9ca8b590ca3270a3433284dd417.png址1369

    0818b9ca8b590ca3270a3433284dd417.png物理

    0818b9ca8b590ca3270a3433284dd417.png址

    0818b9ca8b590ca3270a3433284dd417.png

    解：

    页面大小为=2*1024，所以有：

    1369/(2*1024)=0 (取商，算出页号)1369%(2*1024)=1369(取余算出页内地址)

    3*2*1024+1369=7513

    (2)某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：

    页号

    物理块号

    0

    3

    1

    7

    2

    11

    3

    8

    则逻辑地址0A5C(H)所对应的物理地址是什么？要求：写出主要计算过程。

    解题过程：

    首先要知道页式存储管理的逻辑地址分为两部分：页号和页内地址。物理地址分为两部分：

    关系为：逻辑地址＝　页号＋页内地址

    物理地址＝　块号＋页内地址；

    分析题：已知：用户编程空间共３２个页面，２ˆ５　＝　３２　得知页号部分占５位，由“每页为1KB”，1K=210，可知内页地址占10位。

    由“内存为16KB”，２^４＝１６得知块号占4位。

    逻辑地址0A5C(H)所对应的二进制表示形式是：００００１０１００１０１１１００，后十位１００１０１１１００是页内地址，

    ０００１０为为页号，页号化为十进制是２，在对照表中找到２对应的物理块号是１１,１１转换二进制是１０１１，即可求出物理地址为１０１１１００１０１１１００，化成十六进制为２Ｅ５Ｃ；

    即则逻辑地址0A5C(H)所对应的物理地址是２Ｅ５Ｃ；

    总结：仔细研究上面的两种方法，其实是一样的。第二种的已经页面大小为1KB，然后就是2的10次方，所以后面10位是偏移地址，前面的是页号。其实用逻辑除页面大小2的10次方，结果是一样的。

    一.段页式存储-地址转换

    访问3次内存，第一次是段表，第二次是页表，第三次是真正物理内存

    1.基本原理：是分页与分段的结合，即先将拥护程序分为若干段，再把每个段分为若干页，并为每个段赋予一个段名。

    2.地址结构：

    0818b9ca8b590ca3270a3433284dd417.png

    3.地址变换：

    0818b9ca8b590ca3270a3433284dd417.png

    4.一个逻辑地址为：基地址x、段号s、页号p和页内地址d，求物理地址

    (((x)+s)+p)*2^(11)+d

    5.计算的方法和页式存储是一样的，首先除以页面大小，得到偏移地址，然后根据页面的多少，和段的多少得到他们分别占的位数就能计算出段号和页号了。

    收起
    展开全文

  • 操作系统存储管理之页式存储管理、段式存储管理

     千次阅读 2019-04-13 14:47:16
    页式存储管理 ** 一、页式存储管理的基本原理 【页式存储管理的基本原理】 分页存储器将主存划分成多个大小相同的页架 受页架尺寸限制，程序的逻辑地址也自然分页 不同的页可以放在不同页架中，不需要连续 页表用于...

    **

    页式存储管理

    **

    一、页式存储管理的基本原理

    【页式存储管理的基本原理】

    • 分页存储器将主存划分成多个大小相同的页架
    • 受页架尺寸限制，程序的逻辑地址也自然分页
    • 不同的页可以放在不同页架中，不需要连续
    • 页表用于维系进程的主存完整性
      在这里插入图片描述

    【页式存储管理中的地址】

    • 页式存储管理的逻辑地址由两部分组成：页号和单元号，逻辑地址形式：
      在这里插入图片描述
    • 页式存储管理的物理地址也有两部分组成：页架号和单元号，物理地址形式：
      在这里插入图片描述
    • 地址转换（直接把页号变为页架号）可以通过查页表完成

    【页式存储管理的地址转换思路】
    在这里插入图片描述

    【页式存储管理的内存分配/去配】

    • 可用一张位示图来记录主存分配情况
    • 建立进程页表维护主存逻辑完整性
      在这里插入图片描述

    【页的共享】

    • 页式存储管理能够实现多个进程共享程序和数据
    • 数据共享：不同进程可以使用不同页号共享数据页
    • 程序共享：不同进程必须使用相同页号共享代码页
      #共享代码中的（JMP<页内地址>）指令，使用不同页号时做不到

    二、页式存储管理的地址转换

    【页式存储管理的地址转换代价】

    • 页表放在主存：每次地址转换必须访问两次主存
      1.按页号读出页表中的相应页架号
      2.按计算出来的绝对地址进行读写
    • 存在问题：降低了存取速度
    • 解决方法：利用Cache存放部分页表

    【页式存储管理的快表】

    • 为提高地址转换速度，设置一个专用的高速存储器，用来存放页表的一部分
    • 快表：存放在高速存储器中的页表部分
    • 快表表项：页号，页架号
    • 这种高速存储器是联想存储器，即按照内容寻址，而非按照地址访问

    【引入快表后的地址转换代价】

    • 采用快表后，可以加快地址转换速度
    • 假定主存访问时间为200毫微秒，快表访问时间为40毫微秒，查快表的命中率是90%。平均地址转换代价为：（200+40）*90%+（200+200）*10%=256毫微秒
    • 比两次访问主存的时间（400毫微秒）下降了36%

    【基于快表的地址转换流程】

    • 按逻辑地址中的页号查快表
    • 若该页已在快表中，则由页架号和单元号形成绝对地址
    • 若该页不在快表中，则再查主存页表形成绝对地址，同时将该页登记到快表中
    • 当快表填满后，又要登记新页时，则需在快表中按一定策略淘汰一个旧登记项

    【多道程序环境下的进程表】

    • 进程表中登记了每个进程的页表
    • 进程占有处理器运行时，其页表起始地址和长度送入页表控制寄存器
      在这里插入图片描述

    【多道程序环境下的地址转换】
    在这里插入图片描述

    三、页式虚拟存储管理

    【页式虚拟存储管理的基本思想】

    • 把进程全部页面装入虚拟存储器，执行时先把部分页面装入实际内存，然后，根据执行行为，动态调入不在主存的页，同时进行必要的页面调出
    • 现代OS的主流存储管理技术
    • 首次只把进程第一页信息装入主存，称为请求页式存储管理

    【页式虚拟存储管理的页表】

    • 需要扩充页表项，指出
      #每页的虚拟地址、实际地址
      #主存驻留标志、写回标志、保护标志、引用标志、可移动标志
      在这里插入图片描述

    【页式虚拟管理的实现】

    • CPU处理地址
      #若页驻留，则获得块号形成绝对地址
      #若页不在内存，则CPU发出缺页中断
    • OS处理缺页中断
      #若有空闲页架，则根据辅存地址调入页，更新页表与快表等
      #若无空闲页架，则决定淘汰页，调出已修改页，调入页，更新页表与快表

    【页式虚拟存储管理的地址转换】
    在这里插入图片描述

    【缺页中断的处理流程】
    在这里插入图片描述

    四、页面调度

    【页面调度】

    • 当主存空间已满又需要装入新页时，页式虚拟存储管理必须按照一定的算法把已在主存的一些页调出去
    • 选择淘汰页的工作称为页面调度
    • 选择淘汰页的算法称为页面调度算法
    • 页面调度算法如果设计不当，会出现（刚被淘汰的页面立即又要调入，并如此反复）这种现象称为抖动或颠簸

    【缺页中断率】

    • 假定进程P共n页，系统分配页架数m个
    • P运行中成功访问次数为S，不成功访问次数为F，总访问次数A=S+F
    • 缺页中断率定义为：f=F/A
    • 缺页中断率是衡量存储管理性能和用户编程水平的重要依据

    【影响缺页中断率的因素】

    • 分配给进程的页架数：可用页架数越多，则缺页中断率就越低
    • 页面的大小：页面尺寸越大，则缺页中断率就越低
    • 用户的程序编制方法：在大数据量情况下，对缺页中断率也有很大影响

    【用户编程的例子】

    • 程序将数组置为“0”，假定仅分得一个主存页架，页面尺寸为128个字，数组元素按行存放，开始时第一页在主存
      在这里插入图片描述

    【OPT页面调度算法】

    • 理想的调度算法是：当要调入新页面时，首先淘汰以后不再访问的页，然后选择距现在最长时间后再访问的页
    • 该算法由Belady提出，称Belady算法，又称最佳算法（OPT）
    • OPT只可模拟，不可实现

    【先进先出FIFO页面调度算法】

    • 总是淘汰最先调入主存的那一页，或者说主存驻留时间最长的那一页（常驻的除外）
    • 模拟的是程序执行的顺序性，有一定合理性

    【最近最少用LRU页面调度算法】

    • 淘汰最近一段时间较久未被访问的那一页，即那些刚被使用过的页面，可能马上还要被使用到
    • 模拟了程序执行的局部属性，既考虑了循环性又兼顾了顺序性
    • 严格实现的代价大（需要维持特殊队列）

    【LRU算法的模拟实现】

    • 每页建一个引用标志，供硬件使用
    • 设置一个时间间隔中断：中断时页引用标志置0
    • 地址转换时，页引用标志置1
    • 淘汰页面时，从页引用标志为0的页中随机选择
    • 时间间隔多长是个难点

    【最不常用LFU页面调度算法】

    • 淘汰最近一段时间内访问次数较少的页面，对OPT的模拟性比LRU更好
    • 基于时间间隔中断，并给每一页设置一个计数器
    • 时间间隔中断发生后，所有计数器清0
    • 每访问页1次就给计数器加1
    • 选择计数值最小的页面淘汰

    【时钟CLOCK页面调度算法】

    • 采用循环队列机制构造页面队列，形成了一个类似于钟表面的环形表
    • 队列指针则相当于钟表面上的表针，指向可能要淘汰的页面
    • 使用页面引用标志位

    【CLOCK算法的工作流程】

    • 页面调入主存时，其引用标志位置1
    • 访问主存页面时，其引用标志位置1
    • 淘汰页面时，从指针当前指向的页面开始扫面循环队列
      #把所遇到的引用标志位是1的页面的引用标志位清0，并跳过
      #把所遇到的引用标志位是0的页面淘汰，指针推进一步

    五、反置页表

    【反置页表的提出】

    • 页表及相关硬件机制在地址转换、存储保护、虚拟地址访问中发挥了关键作用
    • 为页式存储管理设置专门硬件机构
    • 内存管理单元MMU：CPU管理虚拟/物理存储器的控制线路，把虚拟地址映射为物理地址，并提供存储保护，必要时确定淘汰页面
    • 反置页表IPT：MMU用的数据结构

    【反置页表的基本设计思想】

    • 针对内存中的每个页架建立一个页表，按照块号排序
    • 表项包含：正在访问该页架的进程标识、页号及特征位，和哈希链指针等
    • 用来完成内存页架到访问进程页号的对应，即物理地址到逻辑地址的转换

    【反置页表的页表项】

    • 页号：虚拟地址页号
    • 进程标志符：使用该页的进程号（页号和进程标志符结合起来标志一个特定进程的虚拟地址空间的一页）
    • 标志位：有效、引用、修改、保护和锁定等标志信息
    • 链指针：哈希链

    【基于反置页表的地址转换过程】

    • MMU通过哈希表把进程标识和虚页号转换成一个哈希值，指向IPT（反置页表）的一个表目
    • MMU遍历哈希链找到所需进程的虚页号，该项的索引就是页架号，通过拼接移位便可生成物理地址
    • 若遍历整个反置页表中未能找到匹配表项，说明该页不在内存，产生缺页中断，请求操作系统调入

    【反置页表下的地址转换示意】
    在这里插入图片描述

    • 未显示选择淘汰页面，同样由MMU完成

    **

    段式存储管理

    **

    一、段式存储管理

    【段式程序设计】

    • 每个程序可由若干段组成，每一段都可以从“0”开始编址，段内的地址是连续的
    • 分段存储器的逻辑地址由两部分组成
      #段号：单元号
      #和页式存储管理（段号：单元号）有本质区别。“段号：单元号”是用户程序设计自己设定的。而“页号：单元号”是系统自动切割的，用户并不知道。所以分页存储器是用户编程原则上不可见的，除了性能优化。而分段存储器是用户可控制的

    【程序的分段结构】
    在这里插入图片描述

    【段式存储管理的基本思想】

    • 段式存储管理基于可变分区存储管理实现，一个进程要占用多个分区
    • 硬件需要增加一组用户可见的段地址寄存器（代码段、数据段、堆栈段、附加段），供地址转换使用
    • 存储管理需要增加设置一个段表，每个段占用一个段表项，包括：段始址、段限长，以及存储保护、可移动、可扩充等标志位

    【段式存储管理的地址转换流程】
    在这里插入图片描述

    【段的共享】

    • 通过不通进程段表中的项指向同一个段基址来实现
    • 对共享段的信息必须进行保护，如规定只能读出不能写入，不满足保护条件则产生保护中断

    二、段式虚拟存储管理

    【段式虚拟存储管理的基本思想】

    • 把进程的所有分段都存放在辅存中，进程运行时先把当前需要的一段或几段装入主存，在执行过程中访问到不在主存的段时再把他们动态装入
    • 段式虚拟存储管理中断的调进调出是由OS自动实现的，对用户透明
    • 与段覆盖基数不同，它是用户控制的主存扩充技术，OS不感知

    【段式虚拟存储管理的段表扩充】

    • 段表的扩充
      #特征位：00（不在内存）01（在内存）11（共享段）
      #存取权限：00（可执行）01（可读）11（可写）
      #扩充位：0（固定长）1（可扩充）
      #标志位：00（未修改）01（已修改）11（不可移动）
      在这里插入图片描述

    【段式虚拟存储管理的地址转换】
    在这里插入图片描述

    三、段页式存储管理

    【段页式存储管理的基本思想】

    • 段式程序设计可以基于页式存储管理实现
    • 每一段不必占据连续的存储空间，可存放在不连续的主存页架中
    • 能够扩充位段页式虚拟存储管理
    • 装入部分段，或者装入段中部分页面

    【段页式存储管理的段表和页表】
    在这里插入图片描述

    【段页式存储管的地址转换】
    在这里插入图片描述

    【段页式虚拟存储管理的地址转换】
    在这里插入图片描述

    收起
    展开全文

  • 操作系统课程设计 段页式存储管理

     2011-05-07 21:18:40
    Visual Studio 2008,MFC,操作系统课程设计，段页式存储管理。。。。
    收起

  • 存储管理之页式、段式、段页式存储 以及 优缺点

     万次阅读 多人点赞 2018-09-14 18:08:44
    内存管理方式主要分为：页式管理、段式管理和段页式管理。 页式管理的基本原理是将各进程的虚拟空间划分为若干个长度相等的页。把内存空间按页的大小划分为片或者页面，然后把页式虚拟地址与内存地址建立一一对应的...
    收起

  • 存储管理系统课程设计——C语言实现请求页式存储管理模拟系统

     千次阅读 2021-02-13 10:11:09
    分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号，从0开始，如第0页、第1页等。相应地，也把内存空间分成与页面相同大小的若干个存储块，称为(物理)块或页框(frame)...
    收起
    操作系统 c语言 页面替换算法

  • 页式存储管理和段式存储管理（学习笔记）

     千次阅读 2020-04-02 15:22:45
    从页式管理开始，到之后的段式管理，都与之前的分区管理不同，最大的区别就在于一个是分区管理是连续存储，二这两种方式可以非连续。 实现原理 首先是必要概念： 物理块：将物理存储空间划分为大小相等的若干存储块...
    收起
    操作系统

  • 操作系统页式存储管理精编.ppt

     2020-12-21 18:45:14
    第四章存储管理 页式存储管理 页式虚拟存储技术 段式存储管理 分区存储管理的缺点 "碎片问题 原因:作业要求连续的存储空间 解决办法:允许作业占据不连续的空间 基本原理 "等分内存 把内存划分为大小相同的块 把用户...
    收起

  • 页式存储管理

     2013-11-26 22:09:24
    页式存储管理
    收起

  • 页式、段式、段页式存储管理和请求页式管理

     千次阅读 2019-11-19 23:39:22
    页式存储： 带块表的页式存储： 注意： 命中块表1次访存，未命中2次 二级页表： 段表： 注意： 比页表多了段长。命中块表1次访存，未命中2次 分段、分页优缺点： 段页式存储： 先查段表，通过段号确定页表地址...
    收起

  • 页式存储管理（FIFO）实现

     热门讨论 2010-02-10 20:32:36
    通过编写和调试请求页式存储管理的模拟程序以加深对请求页式存储管理方案的理解。 为了简单起见。页面淘汰算法采用 FIFO页面淘汰算法，并且在淘汰一页时，判断它是否被改写过，如果被修改过，将它写回到辅存。
    收起

  • 段页式存储管理方式详解

     万次阅读 多人点赞 2020-05-12 15:34:32
    段页式存储管理方式详解分段存储方式引入目的:基本原理分段段表地址变换机构信息保护信息共享分页与分段的主要区别:段页式存储管理方式引入原因：基本原理段表与页表地址变换机构 分段存储方式 引入目的: 满足用户在...
    收起

  • 请求页式存储管理的页面置换算法.doc

     2022-05-06 13:46:02
    请求页式存储管理的页面置换算法.doc
    收起

  • 计算机操作系统4.5段页式存储管理方式.ppt

     2020-11-24 07:26:49
    4.5 段页式存储管理 分段与分页的对比 (1) 用户地址空间的区别 页式系统中用户地址空间 一维地址空间 段式系统中用户地址空间 二维地址空间 (2) 分段和分页 分段 信息的逻辑划分 段长是可变的 分页 信息的物理划分 ...
    收起

  • 分页存储管理，分段存储管理，段页式存储管理

     千次阅读 2020-05-04 16:20:12
    概括的挺详细的，然后我加上了纯分页系统和请求式分页系统的基本概念，也对...同样，将内存空间也划分为与页面大小相同的若干个存储块，即物理块或页框。可将用户的任一页放在内存的任一块中，实现离散分配。 2、...
    收起
    操作系统

  • 内存管理 页式存储管理

     千次阅读 2020-11-03 10:05:39
    这就是页式管理的基本思想，结合前面的分区存储管理会更加容易理解。 相当于程序代码中所使用的逻辑地址划分成页，进程实际用的内存物理地址划分成存储块，且一个页与一个存储块大小一样，这样可以实现页内地址和...
    收起

  • 存储管理——页式存储管理

     千次阅读 2020-01-16 15:07:38
    一、页式存储管理的基本思想 *把主存划分成多个大小相等的页架 *程序受页架尺寸限制，程序的逻辑地址也自然分成页 *不同的页可以放在不同页架中不需要连续 *页表用于维系进程的主存完整性。 1、页式存储管理中的地址...
    收起
    操作系统

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 246,508
精华内容 98,603
热门标签
关键字：

页式存储