段式虚拟存储管理.docx

1、段式虚拟存储管理学 号：课程设计题目段页式虚拟存储管理学院计算机科学与技术专业班级姓名指导教师吴利军2013 年 1 月 16 日课程设计任务书学生姓名：指导教师： 吴利军 工作单位： 计算机科学与技术学院题 目 : 模拟设计段页式虚拟存储管理中地址转换初始条件：1预备内容：阅读操作系统的内存管理章节内容，理解段页式存储管理的思想及 相应的分配主存的过程。2实践准备：掌握一种计算机高级语言的使用。要求完成的主要任务 : （包括课程设计工作量及其技术要求， 以及说明书撰写等具体要求）1实现段页式存储管理中逻辑地址到物理地址的转换。能够处理以下的情形： 能指定内存的大小， 内存块的大小， 进程的个

2、数， 每个进程的段数及段内页 的个数； 能检查地址的合法性，如果合法进行转换，否则显示地址非法的原因。2设计报告内容应说明： 需求分析； 功能设计（数据结构及模块说明） ； 开发平台及源程序的主要部分； 测试用例，运行结果与运行情况分析； 自我评价与总结：i）你认为你完成的设计哪些地方做得比较好或比较出色； ii）什么地方做得不太好，以后如何改正；iii ）从本设计得到的收获（在编写，调试，执行过程中的经验和教训） ； iv ）完成本题是否有其他方法（如果有，简要说明该方法） ；时间安排：设计安排一周：周 1、周 2：完成程序分析及设计。周 2 、周 3：完成程序调试及测试。周 4 、周 5：

3、验收、撰写课程设计报告。注意事项：严禁抄袭，一旦发现，一律按 0 分记）指导教师签名：系主任（或责任教师）签名：一、需求分析：页式管理基本原理： 各个进程的虚拟空间被划分成若干个长度相等的页。 页长的划分和内存与外存之间的数据传 输速度及内存大小等有关。一般每个页长大约为 1 4K ，经过页划分之后，进程的虚拟地址变为页号 p 与页内地址 w 所组成。除了将进程的虚拟空间划分为大小相等的页之外， 页式管理还把内存空间也按页的大小 划分为片或者页面。 这些页面为系统中的任一进程所共享。 从而与分区管理不一样， 分页管 理时， 用户进程在内存空间内除了在每个页面内地址连续之外， 每个页面之间不再连

4、续。 第 一是实现了内存中碎片的减少， 因为任意碎片都会小于一个页面。 第二是实现了由连续存储 到非连续存储的这个飞跃， 为在内存中局部地、 动态地存储那些反复执行或即将执行的程序 和数据段打下了基础。怎样由页式虚拟地址转变为内存页面物理地址？页式管理把页式虚拟地址与内存页面 物理地址建立一一对应页表，并用相应的硬件地址变换机构，来解决离散地址变换问题。静态页面管理： 静态页面管理方法是在作业或进程开始执行之前， 把该作业或进程的程序段和数据全部 装入内存的各个页面， 并通过页表和硬件地址变换机构实现虚拟地址到内存物理地址的地址 映射。1、内存页面的分配与回收 静态分页管理的第一步是为要求内存

5、的作业或进程分配足够的页面。 系统依靠存储页面 表、请求页面表以及页表来完成内存的分配。（ 1）页表 最简单的页表由页号与页面号组成， 页表在内存中占有一块固定的存储区。 页表的 大小有进程或作业的长度决定。每个进程至少要拥有一个页表。（2）请求表 用来确定作业或进程的虚拟空间的各页在内存中的实际对应位置。 系统必须知道每 个作业或进程的页表起始地址和长度， 以进行内存的分配和地址变换， 另外请求表中还 应包括每个作业或进程所要求的页面数。（3）存储页面 存储页面表也是整个系统一张，存储页面表指出内存各个页面是否已被分配出去， 以及未被分配页面总数。 存储页面表也有两种构成方法， 一种是在内存

6、中划分一块固定 区域， 每个单元的每个比特代表一个页面， 如果该页面已被分配， 则对应比特位置置 1， 否则置 0。另一种方法空闲页面链，不占内存空间。2、分配算法3、地址变换 在程序执行过程中， 执行的是虚拟空间中的代码， 代码中的指令是相对于虚拟空间 的，需要到内存的实际空间中寻找对应的要执行的指令。静态页式管理的缺陷： 虽然解决了分区管理时的碎片问题， 但是由于静态页式管理要求进程或作业在执行前全 部装入内存，如果可用页面数小于用户要求时，改作业或进程只好等待。而且，作业或进程 的大小仍受内存可用空间的限制。动态页式管理：动态页式管理是在静态页式管理的基础上发展起来的。 它分为请求页式管

7、理和与调 入页式管理（调入方式上） 。请求页式管理和预调入页式管理在作业或进程开始执行之前都不把作业或进程的 程序段和数据段一次性的调入内存， 而是只装入被认为是经常反复执行和调用的工作区 部分。其他部分都在执行过程中动态的装入。请求式页式管理： 当需要执行某条指令或某些数据时而又发现他不在内存中时， 从 而发生缺页中断，系统将相应的页面调入内存。预调入： 系统对于那些在外存中的页进行调入顺序计算， 估计出这些页中指令和数据的执行和被访问的顺序，并按此顺序将他们顺次调入和调出内存。请求页式管理的地址变换与静态页式相同， 也是通过页表查出相应的页面号， 由页 面号与页内相对地址相加而得到实际物理

8、地址。 由于只有进程或程序的部分存在内存中 因此怎样发现这些不在内存中的虚页以及怎样处理这种情况是必须解决的两个基本问 题。怎样发现这些不在内存中的虚页：扩充页表的方法。 即与每个虚页号相对应， 除了页面号之外， 再增设该页是否在内存中的中断位以及 该页在外存中的副本起始地址。（1）采用何种方法将所缺的页调入内存。（2）如果内存中没有空闲页面时，把调进来的页面放在什么地方。即采用什么策 略淘汰已占据内存的页。 还有就是如果内存中的也被淘汰， 但该页被修改过， 显然该页 应当被重新写到外存加以保存。所以还要增加一项记录是否该页已经被改变。 常见的置换算法：（1）随机淘汰（2）轮转法和先进先出法（

9、3）最近最久未使用内存保护： 页式管理提供两种方式的内存保护： 一是：地址越界保护。二是： 通过页表控制对内存 信息的存取操作方式以提供保护。地址越界保护： 由地址变换机构中的控制存储器的值页表长度和所要访问的虚地址 相比较来完成。存取控制保护的实现则是在页表中增加相应的保护位即可。段式管理： 分区式管理和页式管理时的进程的地址空间结构都是线性的， 这要求对源程序进行编译 连接时，把源程序中的主程序、 子程序、 数据区等按线性空间的一维地址顺序排列起来。共 享子程序和数据变得很困难， 再者从链接的角度来看， 分区管理和页式管理只能采用静态链 接。段式存储管理是基于为用户提供一个方便的灵活的程序

10、设计环境而提出来的。 段式管理 的基本思想是：把程序按内容或过程（函数）关系分成段，每段都有自己的名字。一个用户 进程或作业所包含的段对应于一个二维线性虚拟空间， 也就是二维虚拟存储器。 段式管理程 序以段为单位分配内存，然后通过地址映射机构把段式虚拟地址转换成实际的内存物理地 址。和页式管理一样， 段式管理也采用只把那些经常访问的段驻留内存， 而把那些在将来一 段时间内不被访问的段放在外存，待需要时自动调入的方法实现二维虚拟存储器。段式管理把一个进程的虚拟空间设计成二维结构， 即段号 s 与段内相对地址 w。与页式 管理不一样的是，页式管理中， 被划分的页号按顺序编号递增排列，属一维空间，

11、而段式管 理中段号与段号之间无顺序关系。 另外段的划分也不像页的划分那样具有相同的页长， 段的 长度是不固定的。 每个段定义一组逻辑上完整的程序或数据。 例如， 一个进程中的程序和数 据可划分为主程序段、子程序段、数据段与工作区段。每个段是一个首地址为零的、 连续的一维线性空间。 根据需要段长可以动态的增长。 对 端式虚拟空间地址的访问包括两个部分：段名和段内地址。段式管理中以端为单位分配内存， 每段分配一个连续的内存区， 由于各段长度不等， 所 以这些存储区的大小不一，而且统一进程所包含的各段之间不要求连续。段式管理的内存分配与释放在作业或进程的执行过程中动态进行。 首先，段式管理程序 为一

12、个准备进入内存准备执行的进程或作业分配部分内存， 以作为该进程的工作区和放置即 将执行的程序段。 随着进程的执行， 进程根据需要随时申请调入新段和释放老段。 进程对于 内存区的申请和释放可分为两种情况。 一种是当进程要求调入某一段时， 内存中有足够的空 闲区满足该段的内存要求。 另一种是内存中没有足够的空闲区。 对于第一种情况， 系统要用 相应的表格或数据结构来管理内存空闲区， 以便对用户进程或作业的有关程序段进行内存分 配和回收。 事实上， 可以采用和动态分区式管理相同的空闲区管理方式。 即把内存各空闲区 按物理地址从低到高排列或按空闲区的大小从小到大或从大到小排列。 与这几种空闲区自由 链

13、相对应， 分区式管理时所用的几种分配算法：最先适应算法、最佳适应算法、最坏适应法 都可以用来进行空闲区分配。 当然分区式内存管理时用到的内存回收方法也可以用在段式管 理中。另一种内存管理的分配与回收方法是在内存中没有足够的空闲区满足调入段的内存时 使用的。这时段式管理程序根据给定的置换算法淘汰内存中在今后一段时间内不再被 CPU 访问的段， 也就是淘汰那些访问率最低的段。 不过任何一个段的长度都不允许超过内存的可 用区长度。除了段的初始分配之外，段的动态分配是在 CPU 所要访问的指令和数据不在内存时产 生缺页中断的情况下发生的。因此段的淘汰或置换算法实际上是缺页中断处理过程的一部 分。段式管

14、理的地址变换：由于段式管理只存放部分用户信息副本在内存，而大部分信息在外存中，这必然引起 CPU 访问内存时发成所访问的段不在内存中的情况， CPU 如何感知所要访问的段不在内存 中而启动中断处理程序呢？还有， 段式虚拟地址属于一个二维的虚拟空间。 一个二维空间虚 拟地址怎样变为一个一维的线性物理地址呢。（1）段表 （2）段式管理程序在进行初始内存分配之前，首先根据用户要求的内存大小为一个作业或 一个进程建立一个段表， 以实现动态地址变换和缺页中断处理及存储保护等。 段式管理是通 过段表来进行内存管理的。（3）段号与用户指定的段名一一对应，始址和长度分别表示该段在内存或外存的物理地址 和实际长

15、度。 存取方式是用来对该段进行存取保护的。 只有处理机状态字中的存取控制位与 段表中的存取方式一致时才能访问该段。 内外栏是指该段现在存储在外存还是内存中。 如果 如果该栏目指出所访问段在外存的话， 则发生缺页中断。 而访问位则是根据淘汰算法的需要 而设的。（4）5）动态地址变换一般在内存中给出一块固定的区域放置段表。 当某进程开始执行的时候， 管理程序首先 把该进程的段表始址放入段表地址寄存器。 通过访问段表寄存器， 管理程序得到该进程段表 始址从而可以开始访问段表。 然后由虚拟地址中的段号 s 为索引，查段表。若该段在内存中， 则判断其存取方式是否有错。 如果存取方式正确， 则从段表相应表

16、目中查出该段在内存中的 起始地址，并将其和段内相对地址 w 相加，从而得到实际内存地址。如果该段不在内存，则产生缺页中断将 CPU 控制权交给内存分配程序。内存分配程序 首先检查空闲区链， 以找到足够长度的空闲区来装入所需要的段。 如果可用的空闲区总数小 于所要求的段长，检查段表中的访问位，以淘汰那些访问概率低的段并将所需要的段调入。 段页式：页式管理和段式管理各有特长。 段式管理为用户提供了一个二维的虚拟空间地址， 反映 了程序的逻辑结构有利于段的动态增长以及共享和内存保护， 方便了用户， 而分页式管理则 有效地克服了碎片问题， 提高了存储器的利用率。 段页式则是将段式管理与页式管理相结合，

17、 取长补短。段页式管理一般只用在大型系统中。段页式管理的实现原理：一个进程任然拥有一个自己的二维空间地址， 这与段式管理相同。 首先一个进程中所包 含的具有独立逻辑功能的程序或数据仍被划分为段，并有各自段号 s。这反映了段式管理的特征。其次，对于段 s 中的程序或数据，则按照一定的大小将其划分为不同的页。和页式系 统一样最后不足一页的部分仍然占一页。 这反映了页式特征。 从而段页式管理时的进程的虚 拟空间中的虚拟地址由三部分组成即段号 s，页号 p和页内相对地址 d，如图 1 所示：wsPd图1程序员可见的仍是段号 s和段内相对地址 w。P和 d 是由地址变换机构把 w 高几位解释 成页号 p

18、，以及把剩下的低位解释成页内地址 d。由于虚拟空间的最小单位是页而不是段， 从而内存可用区也就被划分为若干个大小相等的页面， 且每段所拥有的程序和数据在内存中可以分开存放。 分段的大小也不受内存可用区 的限制。段表和页表：为了实现段页式管理， 系统必须为每个作业或进程建立一张段表， 管理内存分配与释放、 缺段处理、 存储保护和地址变换等。 另外，由于一个段又被划分成了若干页，每个段又必须 建立一张页表， 把段中虚页转变成内存中的实际页面。 显然与页式管理相同， 页表中也要有 实现缺页中断处理和页面保护等功能的表项。 另外由于在段页式管理中， 页表不再是属于进 程而是属于某个段，因此段表中应该有

19、指出该段所对应的页表始址和页表长度。动态地址变换过程：在一般使用段页式存储管理的计算机系统中， 都在内存中辟出一块固定的区域存放进程 的段表和页表。 因此，在段页式管理系统中， 要对内存中指令或数据进行一次存取的话，至 少需要访问 3 次以上的内存。二、功能设计定义一个数组来表示一个内存空间。 只做一个数组来管理内存空间， 应当能够显示当前可用 的内存，管理内存的表应当占据空间最小，由于是段页式管理，所以将内存划分为页， 最理 想的方式是用一位来表示内存的一个页面，当内存页面在使用时，将其置为 1，不使用时，将其置为 0，这样内存管理所占用的空间才是最小。由于使用位来管理内存空间页面在程序 的

20、处理方面比较麻烦，所以采用 char类型来表示内存空间的一个页面， char类型只占一个字节，并且内存空间的大小是定长的。所以可用内存表即为：char mmemMax;egmentFlag=0)void single()tartAddr=&n; ageNum=j-n+1;j.MemPgnum=findIdlePage();tartAddr=&n; ageNum=j-n+1; emPgnum=findIdlePage();ageNum,i.MemPgnum);*/void mapping()int s,p,d;int i;printf( 请输入段号，页号，页内地址 :s,p,dn);scanf(

21、%d,%d,%d,&s,&p,&d);for(i=0;ip)if(d=100)printf( 没有该段！ n);void swch()int flag=1,f=0;while(flag)int n;printf(0 退出 0n);printf(1 程序段处理 1n);printf(2 地址转换 2n);printf(3 显示段页内存映射表 3n);getchar();scanf(%d,&n);switch(n)case 0:flag=0;break;case 1:single();f=1;break;case 2:if(f!=0)mapping();elseprintf( 请先输入程序段！ n

22、);break;case 3:if(f!=0)prspm();elseprintf( 请先输入程序段！ n);break; default:printf( 输入有误！ n);void prspm()printf( 段页内存映射表 n); printf( n);for(int i=0;i200;i+) ifi.segmentFlag!=0) printf(%d,i.segNum); ength); ength;j+) /*页号 * 页面号 */ printf( %d %dn,i.startAddrj.pageNum,i.startAddrj.MemPgnum); printf(n);printf

23、( n);int main()printf( 现在进行初始化设置。n);printf( 请指定内存的大小 scanf(%d,&memLen);(MB) ：);printf( 请设置页的大小( for(int i=0;i1024;i+) i.pageFlag=0;swch();/*for(int i=0;i1024;i+) ifi.pageFlag!=0) printf(%d,i);KB )：); egmentFlag=0;printf( 页 号：%d,i.pageNum);printf( 页面号：%dn,i.MemPgnum);*/*for(int i=0;imemMax;i+)if(mi!=

24、0)printf( 内存： %d:%dn,i,mi); */system(pause);四、运行结果与运行情况分析：初始界面如下图：1、可以指定内存大小，页面大小一般页面大小为 1-4KB 左右，然后根据需要输入选项。选择选项 1，就会提示需要输入的段数，然后依次输入段长。输入完成之后就会再次提 示所需的操作。但是一开始只能选择 0，或者 1。因为没有程序段就没有地址转换，同样也没有段页内 存映射表。如果一开始就输入了 2 或者 3，就会提示重新输入。2、选择选项 2，就会提示要转换的段页表，按要求输入之后，就会计算出内存实际地 址，如果出错就会提示相应的出错原因。当输入不存在的段时，程序就会

25、提示不存在该段。并重新返回菜单页面，如上图。当输入段内不存在的页时，就会有提示说没有该页，再次转入菜单页面，如上图。当输入某一段某页的偏移地址超出了页的范围时， 就会有提示说偏移地址偏出该页， 并 重新返回菜单页面，如上图。3、当选择选项 3 时，该程序就会打印段页内存映射表，这个段页内存映射是采用树结 构来显示的，如下图。第一列的数字代表段号， 段号后面的数字表示该段有多少页。 段的下面的第一列数字表 示该段的页表的页号，而页号后面的数字代表内存的页面号。五、自我评价与总结：总体来说我觉得比较优秀出彩的地方是段表和页表的设计方面， 我觉得段表和页表的设 计是在给定条件下最完美的实现。采用划分

26、固定的区域来设置段页表，是一个很好的方法， 因为如果设置链表的话， 虽然会节省一部分的内存空间， 但是采用链表的话， 就会产生一个 很明显的链表的固有缺陷， 就是不能够随机存取， 存取速度就会大打折扣， 对于操作系统来 说是致命的缺陷。 但是采用结构体数组的话， 这个问题就不会存在了， 但是会有数组上的固 有缺陷，就是数组的大小固定，没有办法动态的增加，这样就可能会浪费一定的内存空间。 在权衡取舍的时候， 还是决定使用结构体数组来表示段表和页表还有内存空间， 这样可以获 得较高的访问速度，这对操作系统来说是相当重要的。所以选择了固定长度的段表和页表。还有一点就是在页表的设计时候采用的一种方法，

27、 段页式管理中的页表要求每一个段都 有一个长度由段表指定的顺序存储的页表， 再设计的时候需要认真考虑， 由于每个页表的长 度可变，一开始想到的是采用链表， 但是链表不是顺序存储的，所以不行。 但是数组长度又 不可变。 最终方案还是采用数组， 只要活用指针就能够达到像是变长数组的效果， 并且方法 相当的简单。 首先先设置一个总的页表， 用来装载每一段的页表， 在对每段进行页表的设计 的时候， 在总页表中寻找连续的空闲的页表空间， 将这个页表分配之后， 返回这个页表的数 组的首地址， 保存在段表的始址这个变量中。 这样就相当于每个页表都是变长的， 只是总页 表是定长的，正好符合要求，我觉得这样是一

28、个很好的设计。最后在最后的输出上， 我觉得我的设计方案很不错， 就是有一个树状结构的段页内存映 射图。最后的结果清晰直观，效果很不错。不好的地方：内存管理方面不够节约，在内存管理的时候我采用的是使用 char 数组，使用一个字符来管理一个页面是否是在使用中，即用 8bit 来表示一个页面，但是实际上还 是太过浪费了，可以使用 1bit 来表示一个页面，这样表示内存空间的那块区域就会缩小 8 倍。在改进的时候可以还是可以是 char 数组，不过可以使用一位来表示一个页面，但以后的操作就不是赋值操作，而是位操作，进行与、或、异或和移位等运算。这是一个缺陷，在 内存很大的时候，内存的管理数组也将变得

29、巨大。 8 倍的差距将会大大缩小内存管理的区域 大小。没有实现页面和段的调度置换算法，当段表填满的时候怎样进行段的置换 ,当页表填满的时候怎样进行页表的置换， 这是一个很复杂， 同时这也不是很容易进行模拟， 现在做的这 个程序只能在你填满段表或页表的时候进行提醒说段表或页表已经填满。还有一个缺陷就是指定内存大小， 设计的时候要求指定内存大小， 但是从一般现实来考 虑，实际成活中的内存大小都是固定的， 要模拟动态大小的内存空间， 就必须使用链表来进 行内存空间的管理， 我觉得这是很不合适的， 这样会有两种方案来模拟， 一种是使用链表来 对内存进行映射， 即每一个节点代表内存的每一个页面， 但是这

30、样不如使用数组迅速， 而且 这样的方法的内存开销也不一定比数组小， 因为每一个节点都会增加一个指针变量。 另一种 是将内存使用链表串联起来， 但是在模拟过程中实际上这是很难实现的， 因为实际的内存空 间并不是真正划分了的，而是模拟出来的，所以在实现过程中还是采用了 char 数组来表示 内存管理， 并不真正的模拟内存。 所以只能先设置一个较大的内存管理空间， 当指定内存的 时候只用其中的一部分。虽然会浪费一定的内存空间，但是我觉得比链表法要好很多。我的收获： 这次我的收获是相当的多， 段页式内存管理， 首先为了搞懂什么是段页式内 存管理， 我不得不去翻书查找资料， 我在翻课本的时候我发现， 课本上段式内存管理讲了很 多，页式管理也讲了不少，唯独段页式管理， 只讲了一点，所以我为了搞明白段页式管理我 不得不将