分页式存储管理

非连续分配方式1．基本内容：页式存储管理基本思想、数据结构、地址转换过程。

段式存储管理以及段页式存储管理。

2．学习要求：；掌握页式存储管理、段式存储管理以及段页式存储管理的实现原理、数据结构、地址转换机构等内容。

3．教学要求：本单元共安排4学时。

采用教员课堂讲授方法实施教学。

该部分内容抽象，是本章学习重点与难点。

课后可通过课程设计使学员加深对于抽象理论的理解和掌握。

4．重点：各种管理实现原理、数据结构、地址转换机构。

5．难点：段式存储管理。

分页存储管理可重定位分区分配虽然可以解决碎片和共享问题，但由于信息的大量移动而损失了许多宝贵的CPU时间，且存储用户的作业受到实际存储容量的限制。

多重分区分配虽在一定程度上解决了这些问题，但由于要求各分区设置分段的重定位寄存器，存储分配策略较复杂，且需较多的硬件支持。

分页式管理技术通过地址转换机制，能明显消除内、外存之间的差别，将外存看作内存的扩充和延伸。

并能很好解决“外零头”的问题。

一、分页在储管理实现的基本思想：在分页存储管理中，将每个作业的逻辑地址空间分为大小相同的块，称为虚页面或页（page）,通常页面大小为2的整数次幂（512K~4K）。

同样地，将物理空间也划分为与页面大小相等的块，称之为存储块或页框（page frame），为作业分配存储空间时，总是以页框为单位。

例如：一个作业的地址空间有M页，那么只要分配给它M个页框，每一页分别装入一个页框即可。

纯分页系统的定义：指在调度一个作业时，必须把它的所有页一次装入到主存的矾框。

若当时页框数不足，则该作业必须等待，系统再调度其他作业。

这里，并不要求这些页框是相邻的。

即连续逻辑地址空间的页面，通过页面地址转换机构可以映射到不连续的内存块中。

对地址空间的分页是由系统自动进行的，其逻辑地址由相对页号和页内位移量（页内地址）两部分组成（下面a）。

图中设逻辑地址长度为16位，可表示64K的逻辑地址空间。

物理地址也由块号及块内移量（块内地址）两部分组成（下图b）。

简述分页存储管理基本方法分页存储管理是计算机系统中一种用于管理内存空间的技术。

它将内存空间划分成若干个大小相等的块，称为页，然后通过管理这些页来实现内存空间的有效利用。

分页存储管理的基本方法包括：
1.页表法：将所有的页映射到一张表中，表中的每一项
记录了该页所在的位置。

在访问内存时，先根据地址
查找页表，然后获取该页所在的位置，最后再访问该
位置的内存。

2.页式存储法：将内存空间划分为若干个区域，每个区
域包含若干个页。

在访问内存时，先根据地址确定所
在的区域，然后再访问该区域的内存。

3.段页式存储法：将内存空间划分为若干个段，每个段
再划分为若干个页。

在访问内存时，先根据地址确定
所在的段，然后再根据地址确定所在的页，最后访问
内存。

分页存储管理能够有效提高内存的利用率，减少内存碎片的问题，但同时也会增加访问内存的时间开销。

第十六讲存储器管理之请求分页存储管理方式1 基本概述请求分页管理是建立在基本分页基础上的，为了能支持虚拟存储器而增加了请求调页功能和页面置换功能。

基本原理：地址空间的划分同页式；装入页时，可装入作业的一部分(运行所需)页即可运行。

2 请求分页的硬件支持为实现请求分页，需要一定的硬件支持，包括：页表机制、缺页中断机构、地址变换机构。

2.1 页表机制作用：将用户地址空间的逻辑地址转换为内存空间的物理地址。

因为请求分页的特殊性，即程序的一部分调入内存，一部分仍在外存，因此页表结构有所不同。

如图：说明：（1）状态位P：指示该页是否已调入内存。

（2）访问字段A：记录本页在一段时间内被访问的次数或最近未被访问的时间。

（3）修改位M：表示该页在调入内存后是否被修改过。

若修改过，则换出时需重写至外存。

（4）外存地址：指出该页在外存上的地址。

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

缺页中断与一般中断的区别：（1）在指令执行期间产生和处理中断信号（2）一条指令在执行期间，可能产生多次缺页中断2.3 地址变换机构请求分页系统的地址变换机构。

是在分页系统地址变换机构的基础上，又增加了一些功能。

例：某虚拟存储器的用户空间共有32个页面，每页1KB，主存16KB。

假定某时刻系统为用户的第0、1、2、3页分别分配的物理块号为5、10、4、7，试将虚拟地址0A5C和093C 变换为物理地址。

解：虚拟地址为：页号（2^5=32）5位页内位移（1K =2^10=1024）10位物理地址为物理块号（2^4=16）4位因为页内是10 位，块内位移（1K =2^10=1024）10位虚拟地址OA5C对应的二进制为：00010 1001011100即虚拟地址OA5C的页号为2，页内位移为1001011100，由题意知对应的物理地址为：0100 1001011100即125C同理求093C。

实验7 分页存储器管理实验性质：验证＋设计建议学时：2学时一、实验目的● 学习i386处理器的二级页表硬件机制，理解分页存储器管理原理。

● 查看EOS应用程序进程和系统进程的二级页表映射信息，理解页目录和页表的管理方式。

● 编程修改页目录和页表的映射关系，理解分页地址变换原理。

二、预备知识阅读本书第6章。

了解i386处理器的二级页表硬件机制，EOS操作系统的分页存储器管理方式，以及进程地址空间的内存分布。

三、实验内容3.1 准备实验按照下面的步骤准备本次实验：1. 启动OS Lab。

2. 新建一个EOS应用程序项目。

3.2 查看EOS应用程序进程的页目录和页表使用OS Lab打开本实验文件夹中的memory.c和getcr3.asm文件（将文件拖动到OS Lab窗口中释放即可打开）。

仔细阅读这两个文件中的源代码和注释，main函数的流程图可以参见图16-1。

按照下面的步骤查看EOS应用程序进程的页目录和页表：1. 使用memory.c文件中的源代码替换之前创建的EOS应用程序项目中EOSApp.c文件中的源代码。

2. 右键点击“项目管理器”窗口中的“源文件”文件夹节点，在弹出的快捷菜单中选择“添加”中的“添加新文件”。

3. 在弹出的“添加新文件”对话框中选择“asm 源文件”模板。

4. 在“名称”中输入文件名称“func”。

5. 点击“添加”按钮添加并自动打开文件func.asm。

6. 将getcr3.asm文件中的源代码复制到func.asm文件中。

7. 按F7生成修改后的EOS应用程序项目。

8. 按F5启动调试。

9. 应用程序执行的过程中，会将该进程的二级页表映射信息输出到虚拟机窗口和OS Lab“输出”窗口中，输出内容如图16-2（a）。

10. 将“输出”窗口中的内容复制到一个文本文件中。

图16-2：（a）EOS应用程序进程的二级页表映射信息（b）有应用程序进程时，系统进程的二级页表映射信息图16-2（a）中第一行是CR3寄存器的值，也就是页目录所在的页框号。

实验六：请求分页存储管理一．实验目的深入理解请求页式存储管理的基本概念和实现方法，重点认识其中的地址变换、缺页中断、置换算法等实现思想。

二．实验属性该实验为综合性、设计性实验。

三．实验仪器设备及器材普通PC386以上微机四．实验要求本实验要求2学时完成。

本实验要求完成如下任务：（1）建立相关的数据结构：页表、页表寄存器、存储块表等；（2）指定分配给进程的内存物理块数，设定进程的页面访问顺序；（3）设计页面置换算法，可以选择OPT、FIFO、LRU等，并计算相应的缺页率，以比较它们的优劣；（4）编写地址转换函数，实现通过查找页表完成逻辑地址到物理地址的转换；若发生缺页则选择某种置换算法（OPT、FIFO、LRU等）完成页面的交换；（5）将整个过程可视化显示出来。

实验前应复习实验中所涉及的理论知识和算法，针对实验要求完成基本代码编写并完成预习报告、实验中认真调试所编代码并进行必要的测试、记录并分析实验结果。

实验后认真书写符合规范格式的实验报告（参见附录A），并要求用正规的实验报告纸和封面装订整齐，按时上交。

三、设计过程3.1算法原理分析OPT算法是未来最远出现，当当前内存中没有正要访问的页面时，置换出当前页面中在未来的访问页中最远出现的页面或再也不出现的页面。

FIFO算法是先进先出，当当前内存中没有正要访问的页面时，置换出最先进来的页面。

LRU算法是最近最久未使用，当当前内存中没有正要访问的页面时，置换出在当前页面中最近最久没有使用的页面。

3.2数据定义int length,num_page,count,seed; //length记录访问串的长度，num_page页面数，count记录缺页次数int result[20][30],order[30],a[10]; //result记录结果,order存储访问串,a存储当前页面中的值int pos1,flag1,flag2,flag3; //pos1位置变量，flag1等为标志变量 char result1[30]; //记录缺页数组 void opt() //最佳void fifo() //先进先出bool search(int n) //查找当前内存中是否已存在该页3.3流程图与运行截图图6.1 FIFO （）函数流程图;否是 是否 开始得到执行的指令指令是否在内存中最先存入指令被淘汰下面是否还有指令 结束得出命中率图2.2 OPT算法流程图四、小结本次课程设计目的是通过请求页式管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。

分页和分段有什么区别（内存管理）？
分页和分段有什么区别（内存管理）？
段式存储管理是⼀种符合⽤户视⾓的内存分配管理⽅案。

在段式存储管理中，将程序的地址空间划分为若⼲段（segment），如代码段，数据段，堆栈段；这样每个进程有⼀个⼆维地址空间，相互独⽴，互不⼲扰。

段式管理的优点是：没有内碎⽚（因为段⼤⼩可变，改变段⼤⼩来消除内碎⽚）。

但段换⼊换出时，会产⽣外碎⽚（⽐如4k的段换5k的段，会产⽣1k的外碎⽚）
页式存储管理⽅案是⼀种⽤户视⾓内存与物理内存相分离的内存分配管理⽅案。

在页式存储管理中，将程序的逻辑地址划分为固定⼤⼩的页（page），⽽物理内存划分为同样⼤⼩的帧，程序加载时，可以将任意⼀页放⼊内存中任意⼀个帧，这些帧不必连续，从⽽实现了离散分离。

页式存储管理的优点是：没有外碎⽚（因为页的⼤⼩固定），但会产⽣内碎⽚（⼀个页可能填充不满）。

两者的不同点：
⽬的不同：分页是由于系统管理的需要⽽不是⽤户的需要，它是信息的物理单位；分段的⽬的是为了能更好地满⾜⽤户的需要，它是信息的逻辑单位，它含有⼀组其意义相对完整的信息；
⼤⼩不同：页的⼤⼩固定且由系统决定，⽽段的长度却不固定，由其所完成的功能决定；
地址空间不同：段向⽤户提供⼆维地址空间；页向⽤户提供的是⼀维地址空间；
信息共享：段是信息的逻辑单位，便于存储保护和信息的共享，页的保护和共享受到限制；
内存碎⽚：页式存储管理的优点是没有外碎⽚（因为页的⼤⼩固定），但会产⽣内碎⽚（⼀个页可能填充不满）；⽽段式管理的优点是没有内碎⽚（因为段⼤⼩可变，改变段⼤⼩来消除内碎⽚）。

但段换⼊换出时，会产⽣外碎⽚（⽐如4k的段换5k的段，会产⽣1k的外碎⽚）。

实验八请求分页存储管理设计一、虚拟存储器的相关知识：1.概述：虚拟存储器(Virtual Memory)：在具有层次结构存储器的计算机系统中，自动实现部分装入和部分替换功能，能从逻辑上为用户提供一个比物理贮存容量大得多，可寻址的“主存储器”。

虚拟存储区的容量与物理主存大小无关，而受限于计算机的地址结构和可用磁盘容量。

作用：虚拟内存的作用内存在计算机中的作用很大，电脑中所有运行的程序都需要经过内存来执行，如果执行的程序很大或很多，就会导致内存消耗殆尽。

为了解决这个问题，Windows中运用了虚拟内存技术，即拿出一部分硬盘空间来充当内存使用，当内存占用完时，电脑就会自动调用硬盘来充当内存，以缓解内存的紧张。

举一个例子来说，如果电脑只有128MB物理内存的话，当读取一个容量为200MB的文件时，就必须要用到比较大的虚拟内存，文件被内存读取之后就会先储存到虚拟内存，等待内存把文件全部储存到虚拟内存之后，跟着就会把虚拟内存里储存的文件释放到原来的安装目录里了。

下面，就让我们一起来看看如何对虚拟内存进行设置吧。

2.请求分页虚拟存储系统是将作业信息的副本存放在磁盘这一类辅助存储器中，当作业被调度投入运行时，并不把作业的程序和数据全部装入主存，而仅仅装入立即使用的那些页面，至少要将作业的第一页信息装入主存，在执行过程中访问到不在主存的页面时，再把它们动态地装入。

用得较多的分页式虚拟存储管理是请求分页（demand paging），当需要执行某条指令或使用某个数据，而发现它们并不在主存时，产生一个缺页中断，系统从辅存中把该指令或数据所在的页面调入内存。

3.替换算法：替换规则用来确定替换主存中哪一部分，以便腾空部分主存，存放来自辅存要调入的那部分内容。

常见的替换算法有4种。

随机算法用软件或硬件随机数产生器确定替换的页面。

先进先出先调入主存的页面先替换。

近期最少使用算法替换最长时间不用的页面。

最优算法替换最长时间以后才使用的页面。

页式存储管理一、实验目的：掌握分页式存储管理的基本概念和实现方法。

要求编写一个模拟的分页式管理程序，并能对分页式存储的页面置换算法进行编写和计算各个算法的缺页率。

二、程序设计：首先创建页面链指针数据结构，并设计页面映像表，采用数组的方法给定页面映像。

申请缓冲区，将一个进程的逻辑地址空间划分成若干个大小相等的部分，每一部分称做页面或页。

每页都有一个编号，叫做页号，页号从0开始依次编排，如0，1，2……。

设置等大小的内存块。

初始状态：将数据文件的第一个页面装入到该缓冲区的第0块。

设计页面置换算法，这里分别采用最佳页面置换算法OPT和最近最久未使用置换算法LRU,并分别计算它们的缺页率，以比较它们的优劣。

三、算法说明：执行程序时，当主存没有可用页面时，为了选择淘汰主存中的哪一页面，腾出1个空闲块以便存放新调入的页面。

淘汰哪个页面的首要问题是选择何种置换算法。

该程序采用人工的方法选择，依置换策略选择一个可置换的页，并计算它们的缺页率以便比较。

/*分页式管理实验-源程序*/#include"stdio.h"#define N 16#define num 5 /*进程分配物理块数目*/int A[N]={1,2,3,4,5,6,7,8,5,2,3,2,7,8,1,4}; /*页表映像*/typedef struct page{ int address; /*页面地址*/struct page *next;}page;struct page *head,*run,*rear;void jccreat() /*进程分配物理块*/{ int i=1;page *p,*q;head=(page *)malloc(sizeof(page)); p=head;for(i=1;i<=num;i++) { q=(page *)malloc(sizeof(page));p->next=q; q->address=0; q->next=NULL; p=q; }rear=p;}int search(int n){page *p;int i=0;p=head;while(p->next){if(p->next->address==n){printf("Get it at the page %d\n",i+1);run=p;return 1;}p=p->next;i++;}return 0;}void changeOPT(int n,int position){int i;int total=0;int flag=1;int distance[num];int MAX;int order=0;page *p,*q;p=head->next;q=head->next;for(i=0;i<num;i++)distance[i]=100;i=0;while(p){if(p->address==0){flag=0;break;}p=p->next;i++;}if(!flag){p->address=n;printf("Change the page %d\n",i+1);}else{while(q){for(i=position;i<N;i++){if(q->address==A[i])distance[total]=i-position;}total++;q=q->next;}MAX=distance[0];for(i=0;i<num;i++){if(distance[i]>MAX){MAX=distance[i];order=i;}}printf("Change the page %d\n",order+1);i=0;while(p){if(i==order)p->address=n;i++;p=p->next;}}}void changeLRU(int n){int i=0;int flag=1;page *p,*delect;p=head->next;while(p){if(p->address==0){flag=0;p->address=n;printf("Change the page %d\n",i+1);break;}p=p->next;i++;}if(flag){delect=head->next;head->next=delect->next;printf("Delect from the head, and add new to the end.\n");delect->address=n;rear->next=delect;rear=delect;rear->next=NULL;}}float OPT(){int i;int lose=0;float losef;float percent;for(i=0;i<N;i++){if(search(A[i])==0){lose++;changeOPT(A[i],i);}}losef=lose;percent=1-(losef/N);return percent;}float LRU(){int i;int lose=0;float losef;float percent;page *p;for(i=0;i<N;i++){if(search(A[i])==0){lose++;changeLRU(A[i]);}else{p=run->next;run->next=p->next;rear->next=p;rear=p;rear->next=NULL;printf("Move it to end of queue.\n");}}losef=lose;percent=1-(losef/N);return percent;}main() /*主函数部分*/{float percent;int choice;printf("Select the arithmetic:\n(1)OPT\n(2)LRU\nyour choice is:"); scanf("%d",&choice);/*选择页面置换算法*/jccreat(); /*创建进程*/if(choice==1) /*采用OPT算法置换*/{percent=OPT(); /*计算OPT时的缺页率*/ printf("The percent of OPT is %f",percent);}else if(choice==2) /*采用LRU算法置换*/ {percent=LRU(); /*计算LRU时的缺页率*/ printf("The percent of OPT is %f",percent);}else printf("Your choice is invalid.");getch();}四．运行结果:最佳（Optimal）置换算法：最近最久未使用(LRU)置换算法：五、心得体会掌握分页式存储管理的基本概念和实现方法。