精华内容
下载资源
问答
  • 请求分页式存储管理

    2012-12-10 18:44:57
    操作系统实验,请求分页式存储管理,无BUG版
  • 在请求分页存储管理方案中,若某用户空间为16个页面,长1KB,现有页表如下,则逻辑地址0A1F(H)所对应的物理地址为( )。 两种方式: 逻辑地址 % 1024 (即1k的页面大小) = 地址偏移量 逻辑地址 / 1024 (即1k...

    在请求分页存储管理方案中,若某用户空间为16个页面,页长1KB,现有页表如下,则逻辑地址0A1F(H)所对应的物理地址为( )。

    两种方式:

    1. 逻辑地址 % 1024 (即1k的页面大小) = 地址偏移量
    2. 逻辑地址 / 1024 (即1k的页面大小) = 页号
    3. 根据页号,查页表,可以得到块号
    4. 物理地址 = 块号 X 页大小 + 地址偏移量

    页长1KB 2^10=1k 页面长度为10位,
    故 逻辑地址0A1F(H)转化为二进制位 0000 1010 0001 1111(划线为页面)
    前面的2(二进制10)为页号,查表找块号为3,故物理地址为 0000 1110 0001 1111 (0E1F)
    因为是 分页存储管理,所以隐藏了页面大小等于页框大小这个条件。

    展开全文
  • 先说下什么是(页面)...第4章存储器管理,学习了分页式存储管理方式(是为了解决内存的碎片问题) 第5章虚拟存储器,学习了请求分页式管理方式(除了解决碎片问题外,又“扩充”了内存的大小(虚拟)) ...

    先说下什么是页(页面):就是将用户的程序的的地址空间分成固定大小的区域,称为”页“,或者”页面“

    之后将这些页离散的放进内存中,这样解决了内存的碎片问题

    记得老师上课说了下这两个概念不能混,现在区分下:

    在第4章存储器管理,学习了分页式存储管理方式(是为了解决内存的碎片问题)

    在第5章虚拟存储器,学习了请求分页式管理方式(除了解决碎片问题外,又“扩充”了内存的大小(虚拟))

    在这里为了使得固定数目的内存来运行较多的进程,增加了调页功能和页面置换功能。

    (在这可以看书或者笔记上的例题更好理解)

    请求分页式存储管理需要一些硬件设备的支持:

    1.请求页表机构

    页号,物理块号,状态位(该页是否调入内存),访问字段(用于选择换出页),修改位(换出页是否要重写到外存),外存地址(换入页的地址)

    2.缺页中断机构(这个是请求分页式存储管理特有的)

    3.地址转换机构

     

     

    就这些吧。

    转载于:https://www.cnblogs.com/ldphoebe/p/4845007.html

    展开全文
  • 软 件 学 院 操作系统实验报告 专 业 软件工程 班 级 RB软工互 学 号 学生姓名 指导教师 PAGE 第 PAGE 16 页 共 NUMPAGES 16 页 实验四请求页式存储管理 一实验目的 深入理解请求页式存储管理的原理重点认识其中的...
  • 操作系统课请求分页存储管理模拟模拟程序,程序相对简单,通过这个模拟程序能够帮助学习者会更好的学习os,供有需要的人学习使用。
  • 请求页式存储管理

    2011-12-31 08:11:24
    建立相关的数据结构:存储块表、页表等; (2) 实现基本分页存储管理,如...(3) 基本分页的基础上实现请求分页存储管理; (4) 给定一批作业/进程,选择一个分配或回收模拟; (5) 将整个过程可视化显示出来。
  • C语言模拟实现虚拟存储管理(请求分页存储管理

    千次阅读 多人点赞 2020-06-25 23:19:08
    本实验的目的是:通过编程模拟实现请求分页存储管理中硬件地址转换过程、缺页中断处理过程,以及先进先出页面置换算法,加深对页式虚拟存储管理的理解,了解虚拟存储技术的特点,掌握请求页式存储管理的页面置换方法...

    C语言模拟实现虚拟存储管理(请求分页存储管理)使用FIFO算法
    1)实验目的
    2)实验内容
    3)实验基本原理和解决方案
    4)数据结构、模块划分
    5)画出程序的基本结构框图和流程图(包括主程序流程图、模块详细设计流程图等),对程序的每一部分要有详细的设计分析说明,说明设计实现所用的原理。
    6)源代码,要求格式规范,适当加注释,以有助于说明问题为宜,注释不少于三分之一。
    7)运行的结果,要求有对结果的分析
    8)参考资料
    一、实验目的
    存储管理的主要功能之一是合理的分配空间。请求分页存储管理是一种常用的虚拟存储管理技术。本实验的目的是:通过编程模拟实现请求分页存储管理中硬件地址转换过程、缺页中断处理过程,以及先进先出页面置换算法,加深对页式虚拟存储管理的理解,了解虚拟存储技术的特点,掌握请求页式存储管理的页面置换方法;通过编写和调试地址转换过程的模拟程序以加强对地址转换过程的了解。

    二、实验内容
    阅读教材《计算机操作系统》第四章,掌握存储器管理相关概念和原理。
    (1)用C语言实现对分页式存储管理中的硬件的地址转换和产生缺页中断。
    (2)设计页表。
    页式虚拟存储系统是把作业的副本存放在磁盘上,当作业被选中时,可把作业的开始几页先装入主存且启动执行。为此,在为作业建立页表时,应说明哪些页已在主存,哪些页尚未装入主存,页表的格式为:
    页 号 标志 主存块号 修改标志 在磁盘上的位置

    其中:
    标志——用来表示对应页是否已经装入主存,标志位=1,则表示该页已经在主存中,标志位=0,则表示该页尚未装入主存。
    主存块号——用来表示已经装入主存的页所占的物理块号。
    修改标志——用来表示已经装入主存的页是否被修改过。为,则表示该页装入主存后被修改过;为0,则表示该页该页装入主存后未被修改过。
    在磁盘上的位置——用来指出作业副本的每一页被存放在磁盘上的位置。
    可根据页面置换算法的不同,页表的内容可以作适当的增删。

    三、实验基本原理和解决方案
    (1)地址计算。
    作业执行时,先根据指令中的逻辑地址算出参加运算的操作数存放的页号和页内地址,硬件的地址转换机构按页号查页表,若该页对应标志为“1”,则表示该页已在主存,根据关系式:
    绝对地址=块号*块长+页内地址
    计算出欲访问的主存单元地址。按计算出的绝对地址可以取到操作数,完成一条指令的执行。若访问的页标志为“0”,则表示该页不在主存,这时硬件发“缺页中断”信号,由OS按该页在磁盘上的位置,把该页信息从磁盘读出装入主存后再重新执行这条指令。
    (2)设计“地址转换”程序模拟硬件的地址转换工作。
    当访问的页在主存时,则形成绝对地址,但不去模拟指令的执行,而用输出转换后的地址来代替一条指令的执行。当访问的页不在主存时,则输出“*该页页号”,表示产生了一次缺页中断,执行缺页中断程序。该模拟程序的算法如下图所示。

    地址转换模拟流程图
    (3) 缺页中断模拟。
    在页式虚拟存储系统中,当硬件发出缺页中断请求后,引起操作系统来处理这个中断事件。如果主存有空闲物理块,则调入该页并修改页表;如果主存中没有空闲物理块,则可用FIFO页面置换算法或者LRU页面置换算法从该作业中在主存的页面中选一页淘汰,被淘汰的页是否需要重新写回磁盘,由修改标志决定。然后再把当前要访问的页装入该块。调出和装入后都要修改页表中的相应信息。
    四、数据结构、模块划分
    (1)存放页表的结构体
    struct info //页表信息结构体
    {
    int pageno;
    int flag; //页标志,1表示该页已在主存,0表示该页不在主存
    int block; //块号
    char disk[10]; //在磁盘上的位置
    int dirty; //更新标志(修改标志)

    }pagelist[SizeOfPage];
    (2)存放操作数、逻辑地址以及页表信息的结构体
    struct work{
    char operands[10];
    long adress;
    int pagenum; //页号
    int page_local;//页内地址
    int sign; //标志
    int Block;
    int page_adress;//物理地址
    int page_out; //淘汰页号
    int page_back;

    }worklist[12];

    (3)使用数组进行模拟分配的三个物理块,po始终指向最先进去的页号,模拟FIFO算法
    long po=0; //队列标记
    long P[M]={0,1,2}; //假设内存中最多允许M=3个页面
    (4)使用文本文件进行内存空间初始化
    存放操作数文本文件:
    在这里插入图片描述
    存放页表信息文本文件:
    在这里插入图片描述
    void init_ex1() //内存空间初始化。
    {
    FILE *fp = fopen(“page.txt”,“r”), *fq = fopen(“task.txt”,“r”);
    int i = 0;
    int a = 0, b = 0, c=0, d=0;
    char e[10];
    while(fscanf(fp,"%d%d%d%d%s",&a,&b,&c,&d,&e)!=EOF)
    {
    pagelist[i].pageno=a;
    pagelist[i].flag=b;
    pagelist[i].block=c;
    pagelist[i].dirty=d;
    strcpy(pagelist[i].disk, e);
    i++;
    }
    char s[10];
    long n = 0;
    int k=0;
    while(fscanf(fq,"%s%ld",&s,&n)!=EOF)
    {
    if(k >= 12)
    break;
    strcpy(worklist[k].operands, s);
    worklist[k].adress=n;
    k++;
    }

    fclose(fp);
    fclose(fq);
    

    }
    (5)输出函数
    void print()
    {
    /* char operands[10];
    long adress;
    int pagenum; //页号
    int page_local;//页内地址
    int sign; //标志
    int Block;
    int page_adress;//物理地址
    int page_out; //淘汰页号
    int page_back; //是否写回
    */
    printf(“以下数据1表示是,0表示否\n”);
    printf(“操作数\t逻辑地址\t页号\t页内地址\t是否命中\t物理块号\t物理地址\t淘汰页号\t是否写回\n”);
    for(int i=0;i<12;i++)
    {
    printf("%s\t%ld\t\t%d\t%d\t\t%d\t\t%d\t\t%d\t\t%d\t\t%d",worklist[i].operands,worklist[i].adress,worklist[i].pagenum,worklist[i].page_local,worklist[i].sign,worklist[i].Block,worklist[i].page_adress,worklist[i].page_out,worklist[i].page_back);
    printf("\n");
    }
    }

    (6)模拟FIFO页面调度算法
    void work_FIFO()
    {
    int i,j;
    for(i=0;i<12;i++)
    {
    worklist[i].pagenum=worklist[i].adress / 128;
    worklist[i].page_local=worklist[i].adress % 128;
    worklist[i].page_back = 0;

    	for(j=0;j<7;j++)
    	{
    		if(pagelist[j].pageno == worklist[i].pagenum)
    		{
    			if(pagelist[j].flag==1)
    			{
    				worklist[i].Block = pagelist[pagelist[j].pageno].block;
    				worklist[i].sign=1;
    				worklist[i].page_adress=(pagelist[pagelist[j].pageno].block* SizeOfBlock + worklist[i].page_local);//worklist[i].Block
    				worklist[i].page_out=-1;
    				if(!(strcmp(worklist[i].operands,"存")))
    				{
    					pagelist[worklist[i].pagenum].dirty = 1;		//是否写回磁盘,修改页表
    					worklist[i].page_back = 1;
    				}
    
    				
    			}
    			else
    			{
    				//printf("*%d\n",worklist[i].pagenum);
    				pagelist[P[po]].flag=0;   //将flag标志位置0,表示当前页面已被置换出去
    				worklist[i].page_out=P[po];
    				worklist[i].Block=pagelist[P[po]].block;
    				pagelist[j].block=pagelist[P[po]].block;
    				worklist[i].page_adress=(worklist[i].Block*SizeOfBlock+worklist[i].page_local);
    		   	  
    			   pagelist[j].flag=1;
    			   worklist[i].sign=0;
    			   P[po]=pagelist[j].pageno;   //保存当前页面所在的位置
    			   po=(po+1)%M; 
    
    			   if(!(strcmp(worklist[i].operands,"存")))
    				{
    					pagelist[worklist[i].pagenum].dirty = 1;		//是否写回磁盘,修改页表
    					worklist[i].page_back = 1;
    				}
    
    			}
    		}
    		else
    		{
    			continue;
    		}
    	}
    
    }
    

    }
    (7)主函数
    int main()
    {
    init_ex1();
    work_FIFO();
    print();
    return 0;
    }
    五、画出程序的基本结构框图和流程图(包括主程序流程图、模块详细设计流程图等),对程序的每一部分要有详细的设计分析说明,说明设计实现所用的原理。
    main()函数

    init_ex1()函数

    使用文本文件进行内存初始化工作
    (1)在程序所在目录下创建两个文本文件page.txt和task.txt
    (2)读取文件内容,用循环将文件内容赋值给页表结构体的成员(pagelist)和存放操作数等结构体的成员(worklist)
    work_FIFO()

    使用双重循环
    (1)逻辑地址进行计算页号和页内地址
    (2)进行条件判断,如果页号标志位1,即在主存中,进行物理地址转换,否则进行缺页中断处理,使用P[M]数组模拟三个分配的物理块,po始终指向最先进去的页号

    六、源代码,要求格式规范,适当加注释,以有助于说明问题为宜,注释不少于三分之一。
    #include<stdio.h>
    #include
    #define SizeOfPage 7
    #define SizeOfBlock 128
    #define M 3
    struct info //页表信息结构体
    {
    int pageno;
    int flag; //页标志,1表示该页已在主存,0表示该页不在主存
    int block; //块号
    char disk[10]; //在磁盘上的位置
    int dirty; //更新标志(修改标志)

    }pagelist[SizeOfPage];

    struct work{
    char operands[10];
    long adress;
    int pagenum; //页号
    int page_local;//页内地址
    int sign; //标志
    int Block;
    int page_adress;//物理地址
    int page_out; //淘汰页号
    int page_back;

    }worklist[12];

    long po=0; //队列标记
    long P[M]={0,1,2}; //假设内存中最多允许M=3个页面

    void init_ex1() //内存空间初始化。
    {
    //memset(pagelist,0,sizeof(pagelist)); 内存空间初始化,第一个值为指定的内存地址,块的大小由第三个参数指定,这个函数通常为新申请的内存做初始化工作, 其返回值为s。

    FILE *fp = fopen("page.txt","r"), *fq = fopen("task.txt","r");
    int i = 0;
    int a = 0, b = 0, c=0, d=0;
    char e[10];
    while(fscanf(fp,"%d%d%d%d%s",&a,&b,&c,&d,&e)!=EOF)
    {
    	pagelist[i].pageno=a;
    	pagelist[i].flag=b;
    	pagelist[i].block=c;
    	pagelist[i].dirty=d;
    	strcpy(pagelist[i].disk, e);
    	i++;
    }
    char s[10];
    long n = 0;
    int k=0;
    while(fscanf(fq,"%s%ld",&s,&n)!=EOF)
    {
    	if(k >= 12)
    		break;
    	strcpy(worklist[k].operands, s);
    	worklist[k].adress=n;
    	k++;
    }
    
    fclose(fp);
    fclose(fq);
    

    }

    void print()
    {
    /* char operands[10];
    long adress;
    int pagenum; //页号
    int page_local;//页内地址
    int sign; //标志
    int Block;
    int page_adress;//物理地址
    int page_out; //淘汰页号
    int page_back; //是否写回
    */
    printf(“以下数据1表示是,0表示否\n”);
    printf(“操作数\t逻辑地址\t页号\t页内地址\t是否命中\t物理块号\t物理地址\t淘汰页号\t是否写回\n”);
    for(int i=0;i<12;i++)
    {
    printf("%s\t%ld\t\t%d\t%d\t\t%d\t\t%d\t\t%d\t\t%d\t\t%d",worklist[i].operands,worklist[i].adress,worklist[i].pagenum,worklist[i].page_local,worklist[i].sign,worklist[i].Block,worklist[i].page_adress,worklist[i].page_out,worklist[i].page_back);
    printf("\n");
    }
    }
    void work_FIFO()
    {

    int i,j;
    for(i=0;i<12;i++)
    {
    	worklist[i].pagenum=worklist[i].adress / 128;
    	worklist[i].page_local=worklist[i].adress % 128;
    	worklist[i].page_back = 0;
        
    	for(j=0;j<7;j++)
    	{
    		if(pagelist[j].pageno == worklist[i].pagenum)
    		{
    			if(pagelist[j].flag==1)
    			{
    				worklist[i].Block = pagelist[pagelist[j].pageno].block;
    				worklist[i].sign=1;
    				//printf("物理块:%d\n",worklist[i].Block);
    				worklist[i].page_adress=(pagelist[pagelist[j].pageno].block* SizeOfBlock + worklist[i].page_local);//worklist[i].Block
    			//	printf("物理地址:%d\n",worklist[i].page_adress);
    				worklist[i].page_out=-1;
    				if(!(strcmp(worklist[i].operands,"存")))
    				{
    					pagelist[worklist[i].pagenum].dirty = 1;		//是否写回磁盘,修改页表
    					worklist[i].page_back = 1;
    				}
    
    				
    			}
    			else
    			{
    				//printf("*%d\n",worklist[i].pagenum);
    				pagelist[P[po]].flag=0;   //将flag标志位置0,表示当前页面已被置换出去
    				worklist[i].page_out=P[po];
    				worklist[i].Block=pagelist[P[po]].block;
    				pagelist[j].block=pagelist[P[po]].block;
    				worklist[i].page_adress=(worklist[i].Block*SizeOfBlock+worklist[i].page_local);
    		   	  
    			   pagelist[j].flag=1;
    			   worklist[i].sign=0;
    			   P[po]=pagelist[j].pageno;   //保存当前页面所在的位置
    			   po=(po+1)%M; 
    
    			   if(!(strcmp(worklist[i].operands,"存")))
    				{
    					pagelist[worklist[i].pagenum].dirty = 1;		//是否写回磁盘,修改页表
    					worklist[i].page_back = 1;
    				}
    
    			}
    		}
    		else
    		{
    			continue;
    		}
    	}
    
    }
    

    }

    int main()
    {
    init_ex1();
    work_FIFO();
    print();

    return 0;
    

    }
    七、运行的结果,要求有对结果的分析
    结果分析:
    页号=int(逻辑地址/每块长度(128)) 页内地址=逻辑地址%每块长度(128)
    初始内存时,存在主存的页号有0,1,2号页。下面进行三个举例验证输出结果是否正确:
    ①第一个操作数为“+”,逻辑地址为:389,页号=int(389/128)=3,页内地址=389%128=5
    此时,3号页不在主存中,未命中(为0),产生缺页中断,使用FIFO算法进行页面调度,淘汰最先进入主存的页号,即0页,故0号页淘汰,将淘汰页的物理块赋值给调入页号的物理块,极为5,物理地址为:5128+5=645,操作数不为“存”,不写回外存。
    ②第二个操作数为“+”,逻辑地址为:150,页号=int(150/128)=1,页内地址=150%128=22
    此时,在主存是页号有3,1,2,故命中(为1),物理块号为8,物理地址为:8
    128+22=1046,命中,无淘汰页号,即记为-1,操作数不为“存”,不写回外存。
    ③第四个操作数为“存”,逻辑地址为:78,页号=int(78/128)=0,页内地址=78%128=78
    此时,在主存中的页号有1,2,3,未命中,产生缺页中断,根据FIFO算法,淘汰1号页,调入0号页,物理块号为8,物理地址为:8*128+78=1102,操作数为“存”,写回外存,记为1。以此类推,现不再重复验证。
    八、主要参考资料
    [1] 汤子瀛等. 计算机操作系统(第三版). 西安:西安电子科技大学出版社2007
    [2] [美]William Stallings. 操作系统――内核与设计原理. 北京:电子工业出版社 2001
    [3] [美]Abraham Silberschatz等. 操作系统概念(第六版) 北京:高等教育出版社 2004
    [4] [荷]Andrews Tanenbaum. 现代操作系统(第2版)北京:机械工业出版社 2005
    [5] 谭浩强. C程序设计(第四版). 北京:清华大学出版社2010

    展开全文
  • 这是操作系统中请求分页式存储管理中的页面置换算法,有先进先出算法,OPT置换算法,LRu置换算法。
  • 操作系统课设 请求分页存储管理系统
  • 请求分页存储管理Python实现源代码+课设报告文档-海南大学信息学院操作系统课设。请求分页存储管理Python实现源代码+课设报告文档-海南大学信息学院操作系统课设。
  • FIFO 请求分页式存储管理 henbucuode daima
  • 请求分页存储管理系统设计与实现可课程设计
  • 请求分页存储管理系统采用java编写,含有详细的报告
  • 该程序采用C语言模拟操作系统对内存的请求分页式存储管理,程序代码较为简单。其中涉及到了三个算法:FIFO、LRU、OPT。其中OPT算法用于评价各个算法的优劣。当使用内存块为2kb、4kb时有一定的Bug,请读者自行优化。...
  • 操作系统 请求分页存储管理

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

    目录

    • 请求分页存储管理中的页表机制
    • 缺页中断机构
    • 地址转换
    • 页置换算法
    • 页分配和页置换策略
    • 工作集及抖动现象的消除
    • 请求分页存储管理的优缺点

    请求分页存储管理中的页表机制

    系统需要解决的问题

    • 系统如何获知进程当前所需页面不在主存
      当发现缺页时,如何把所缺页面调入主存
      当主存中没有空闲的页框时,为了要接受一个新页,需要把老的一页淘汰出去,根据什么策略选择欲淘汰的页面

    页表机制

    页描述子的扩充(页表机制 )

    • 状态位P(中断位)指示该页是在内存还是在外存
    • 访问位A 用于记录本页在一段时间内被访问的次数或记录本页在最近多长时间未被访问
    • 修改位M 表示该页在内存中是否被修改过
    • 外存地址 该页在外存上的地址,通常是物理块号

    在这里插入图片描述

    缺页中断机构

    • 在请求分页系统中,每当所要访问的页面不在内存时,便产生一缺页中断。相应的中断处理程序把控制转向缺页中断子程序,执行此子程序,即把所缺页面装入主存,然后处理机重新执行缺页时打断的指令。这时,就将顺利形成物理地址。
    • 缺页中断与一般中断的区别
      • 在指令执行期间产生和处理中断信号
      • 一条指令在执行期间可能产生多次缺页中断,例如:在请求分页存储管理中,当中断位反映出进程当前欲访问的页不在内存时(1表示该页在内存,0表示该页不在内存),就产生一次缺页中断。系统收到缺页中断信号后就立即执行相应的缺页中断处理程序。
      • 特点:
        (1)缺页中断的产生和处
        理(中断的响应)出现在一条指令的
        执行期内。
        (2)程序运行过程中,一条指令的执行
        期间内可能会产生多次缺页中断。
        在这里插入图片描述

    地址变换机构

    • 如果在快表中未找到该页的页表项,则应再到内存中去查找页表,再从找到的页表项中的状态位P,该页是否调入内存。其结果可能是:
      (1)该页已经调入内存,这是应将此页的页表项写入快表,当快表已满时,应先调出按某种算法所确定的页的页表项,然后再写入该页的页表项。
      (2)该页尚未调入内存,这时便应产生缺页中断,请求OS从外存中把该页调入内存。

    请求分页中的地址变换过程
    在这里插入图片描述
    页面调入过程

    在这里插入图片描述

    页置换算法

    缺页率

    • 假设一个进程的逻辑空间为n页,系统为其分配的内存物理块数为m(m≤n)
    • 如果在进程的运行过程中,访问页面成功(即所访问页面在内存中)的次数为S,访问页面失败(即所访问页面不在内存中,需要从外存调入)的次数为F,则该进程总的页面访问次数为A=S+F,那么该进程在其运行过程中的缺页率即为
      在这里插入图片描述

    影响缺页率的因素

    • 分配给进程的物理页面数
    • 页面本身的大小
    • 程序的编制方法
    • 页面淘汰算法

    最佳(Optimal)置换算法

    • 最佳置换算法是由Belady于1966年提出的一种理论上的算法
    • 其所选择的被淘汰页面,将是以后永不使用的,或许是在最长(未来)时间内不再被访问的页面
    • 采用最佳置换算法,通常可保证获得最低的缺页率
    • 采用最佳置换算法可保证获得最低的缺页率。
    • 由于人们目前还无法预知一个进程在内存的若干个页面中,哪一个页面是未来最长时间内不再被访问的,因而该算法也是无法实现的,但是可利用该算法去评价其它算法。

    利用最佳页面置换算法时的置换图

    在这里插入图片描述

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

    • 该算法总是淘汰最先进入内存的页面,即选择在内存中的驻留时间最久的页面予以淘汰。
    • 该算法实现简单,只需把一个进程已调入内存的页面,按先后次序链接成一个队列,并设置一个指针,称为替换指针,使它总是指向最老页面。
    • 但该算法与进程实际运行的规律不相适应,因为在进程中,有些页面经常被访问,含有全局变量、常用函数、例程等的页面,FIFO置换算法并不能保证这些页面不被淘汰。

    利用FIFO置换算法时的置换图

    在这里插入图片描述

    最近最久未使用(LRU)置换算法

    • 最近最久未使用(LRU)的页面置换算法,是根据页面调入内存后的使用情况。
    • 由于无法预测各页面将来的使用情况,只能利用“最近的过去”作为“最近的将来”的近似。
    • LRU置换算法是选择最近最久未使用的页面予以淘汰。

    LRU页面置换算法
    在这里插入图片描述

    LRU置换算法的硬件支持
    • 把LRU算法作为页面置换算法是比较好的,它对于各种类型的程序都能适用,但实现起来有相当大的难度,因为它要求系统具有较多的支持硬件。所要解决的问题有:

      • 一个进程在内存中的各个页面各有多久时间未被进程访问;
        如何快速地知道哪一页最近最久未使用的页面。
        为此,须利用以下两类支持硬件:
      1. 移位寄存器:
        定时右移
      2. 栈:
        当进程访问某页时,将其移出压入“栈顶”,“栈底”换出。
    • 寄存器

      • 为了记录某进程在内存中各页的使用情况,须为每个在内存中的页面配置一个移位寄存器,可表示为
        在这里插入图片描述

      • 访问时将Rn-1位置成1,定时信号每隔一时间间隔右移一位,则具有最小数值的寄存器所对应的页面,就是最近最久未使用的页面
        在这里插入图片描述
        某进程具有8个页面时的LRU访问情况
        在这里插入图片描述

      • 进程访问某页时,将该页面的页号从栈中移出,再压入栈顶
      • 用栈保存当前使用页面时栈的变化情况
        在这里插入图片描述

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

    • 为内存中的每个页面设置一个移位寄存器,用来记录该页面被访问的频率

    • 该算法选择在最近使用最少的页面作为淘汰页
      在这里插入图片描述

    • 与最近最少用算法LRU的区别

      • 只考虑一段时间内使用的次数,而不管其使用的

    注意:这种算法并不能真正反映出页面的使用情况,因在每一时间间隔内只是用寄存器的一位来记录页的使用情况,因此访问1次和10000次是等效的

    简单的Clock置换算法

    • 利用Clock算法时,只须为每页设置一位访问位,在将内存中的所有页面都通过链接指针链成一个循环队列。当某页被访问时,其访问位被置1。置换算法在选择一页淘汰时,只须检查其访问位。
      在这里插入图片描述
    • 各字段说明如下
      (1)状态位(存在位)P。用于指示该页是否调入内存,供程序访问时参考。
      (2)访问字段A。用于记录本页在一段时间内被访问的次数,或最近已有多长时间未被访问,提供给置换算法选择换出页面时参考
      (3)修改位M。表示该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本,因此,若未被修改,在置换该页时就不须将该写回到外存上,以减少系统的开销和启动磁盘的次数;若已被修改,则必须将该页重写到外存上,以保证外存中所保留的始终是最新副本。
      (4)外存地址。用于指出该页在外存上的地址,通常是物理块号,供调入该页时使用。

    简单的CLOCK置换算法(近似的LRU算法)

    • 当采用简单的CLOCK算法时,只需为每页设置一位访问位,再将内存中的所有页面都通过链接指针链接成一个循环队列
    • 当某页被访问时,其访问位被置1
    • 置换算法在选择一页淘汰时,只需检查页的访问位,是0换出,是1重新置0且暂不换出,再按FIFO检查下一个页面。检查到最后一个页面,若其访问位仍为1,则再返到队首检查
    • 由于该算法是循环地检查各页面的访问情况,故称为CLOCK算法,置换的是未使用过的页,又称为最近未用算法NRU(Not Recently Used)

    简单Clock置换算法的流程和示例
    在这里插入图片描述

    改进型Clock置换算法

    • 在将一个页面换出时,如果该页已被修改过,便须将它重新写到磁盘上;但如果该页未被修改过,则不必将它拷回磁盘。同时满足两条件的页面作为首选淘汰的页。

    在这里插入图片描述

    • 各字段说明如下:
      (1)状态位(存在位)P。用于指示该页是否调入内存,供程序访问时参考。
      (2)访问字段A。用于记录本页在一段时间内被访问的次数,或最近已有多长时间未被访问,提供给置换算法选择换出页面时参考。
      (3)修改位M。表示该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本,因此,若未被修改,在置换该页时就不须将该写回到外存上,以减少系统的开销和启动磁盘的次数;若已被修改,则必须将该页重写到外存上,以保证外存中所保留的始终是最新副本。

      (4)外存地址。用于指出该页在外存上的地址,通常是物理块号,供调入该页时使用。

    改进型Clock置换算法说明

    • 考虑使用情况和置换代价,换出的最好是未使用且未被修改过的
    • 由访问位A和修改位M组合:
      • 1类**(A=0, M=0)**:表示该页最近既未被访问,又未被修改,是最佳淘汰页
      • 2类**(A=0, M=1)**:表示该页最近未被访问,但已被修改,并不是很好的淘汰页
      • 3类**(A=1, M=0)**:最近已被访问,但未被修改, 该页有可能再被访问
      • 4类**(A=1, M=1)**:最近已被访问且被修改,该页可能再被访问
        在这里插入图片描述
    • 其执行过程可分成以下三步
    1. 从指针所指示的当前位置开始, 扫描循环队列, 寻找A=0且M=0的第一类页面, 将所遇到的第一个页面作为所选中的淘汰页。 在第一次扫描期间不改变访问位A
    2. 如果第一步失败,即查找一周后未遇到第一类页面, 则开始第二轮扫描,寻找A=0且M=1的第二类页面,将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间,将所有扫描过的页面的访问位A都置0
    3. 如果第二步也失败,亦即未找到第二类页面,则将指针返回到开始的位置,并将所有的访问位A复0。 然后重复第一步,如果仍失败,必要时再重复第二步,此时就一定能找到被淘汰的页

    改进型Clock置换算法-示例

    在这里插入图片描述

    未完待续。。。

    展开全文
  • 上海大学操作系统实验三(请求页式存储管理
  • 操作系统的实验请求页式存储管理的代码书写流程,PPt资料
  • 存储器管理ppt 4.1 程序的装入和链接 4.2 连续分配方式 4.3 基本分页存储管理方式 4.4 基本分段存储管理方式 4.5 虚拟存储器的基本概念 4.6 请求分页存储管理方式 4.7 页面置换算法 4.8 请求分段存储管理方式
  • 通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解。熟悉虚存管理的各种页面淘汰算法。通过编写和调试地址转换过程的模拟程序以加强对地址转换过程的了解。
  • 通过编写分页存储管理的模拟程序,加深对页式存储管理方式的理解,熟悉逻辑地址到物理地址的转换过程,掌握虚拟存储管理中的页面调度算法,认识分页式虚拟存储系统中缺页中断的处理过程。 二、实验内容 1、设计一...
  • 模拟仿真请求分页调度算法OPT、FIFO、LRU、LFU、CLOCK等模拟页面调度算法,并提供性能比较分析功能。
  • 请求分页存储管理方式

    千次阅读 2017-10-08 10:22:57
    ----- 请求分页系统是建立基本分页的基础上的,为了能支持虚拟存储器功能而增加了请求功能和页面置换功能。 相应地,每次调入和换出的基本单位都是长度固定的页面,这使得请求分页系统实现上要比请求分段...
  • 编写一个请求页式存储管理模拟程序,通过对页面置换过程的模拟,加深对请求页式存储管理方式基本原理及实现过程的理解。 要求: 1. 从键盘输入页面访问序列及分配给进程的内存块数; 2. 分别采用OPT、FIFO和LRU...
  • 一个请求分页存储管理系统中,一个作业的页面走向为4,3,2,1,4,3,5,4,3,2,1,5,当分配给该作业的物理块数分别为3和4时,试计算采用LRU和FIFO 淘汰算法时的缺页率(假设开始执行时主存中没有页面)。...
  • 目的:(1)通过编写程序实现请求分页存储管理页面Optimal、FIFO、LRU调度算法,使学生掌握虚拟存储管理中有关缺页处理方法等内容,巩固有关虚拟存储管理的教学内容。 (2)了解Windows2000/XP中内存管理机制,掌握...
  • 题目:1。存储管理 描述请求分页存储管理。 一. 产生一个作业及作业页面序列P(pi),例如:P(0,2,3,4,1,5,2,3,0,4,1,5)。 二.分配物理内存块数M。 三.采用FIFO,LRU置换算法。
  • 请求分页存储管理模拟实验

    千次阅读 2018-12-11 22:24:54
    设计一个请求页式存储管理方案。并编写模拟程序实现。 (1)产生一个需要访问的指令地址流。它是一系列需要访问的指令的地址。为不失一般性,你可以适当地(用人工指定地方法或用随机数产生器)生成这个序...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 131,088
精华内容 52,435
关键字:

在请求页式存储管理