地址转换过程的模拟实现课程设计报告

1、淮阴工学院操作系统课程设计报告选题名称: 地址转换过程的模拟实现 系（院）: 经济管理学院 专 业: 信息管理与信息系统 班 级: 姓 名: 学 号： 姓 名: 学 号： 姓 名: 学 号： 姓 名: 学 号： 指导教师: 学年学期: 学年 第 学期 年 月 日设计任务书课题名称地址转换过程的模拟实现设计目的1. 理解地址转换相关理论。2. 熟悉地址转换的过程。3. 掌握常用地址转换算法的实现过程。实验环境1. 硬件：PC机，奔腾IV以上CPU， 512MB以上内存，80G以上硬盘。2. 软件：Windows2000/XP、Microsoft Visual C+ 6.0。任务要求1. 搜集地址

2、转换过程的模拟实现可能涉及到的知识和相关资料。2. 应用Microsoft Visual C+ 6.0集成开发环境，设计并实现一个地址转换模拟程序。3. 确保地址转换模拟程序能正确运行。4. 参加答辩，撰写课程设计报告。工作进度计划序号起止日期工 作 内 容12013.12.14课题任务下达，查阅文献资料22013.12.152013.12.17课题总体设计、素材搜集与处理32013.12.182013.12.20课题详细设计、调试、完善设计42013.12.21答辩，撰写报告指导教师（签章）： 年 月 日 摘要：本课程设计主要针对地址转换相关理论进行设计，程序能模拟出操作系统常用的地址转换算

3、法，包括可变分区存储管理的地址转换、分页存储管理的地址转换、分段存储管理的地址转换和段页式存储管理的地址转换。具体来说，把整个内存分成大小相等内存块，内存块从0开始依次编号。把用户程序分成若干段，每段有个段名。页面的大小和内存块相同，每段的各个页面都分别从0开始依次编号。虚拟空间的最小单位是页而不是段，内存就被分为若干个页，且每段所拥有的程序和数据在内存中可以分开存放，分段大小也不再受内存可用区的限制。程序模拟实现了四种地址转换方式，从中观察各种方法的优缺点及应用特点。段页式存储管理系统，用分段的方法来分配和管理虚拟存储器，而用分页的方法来分配和管理主存。既有段式系统便于实现段的共享，段的保护

4、，动态链接和段的动态增长等一系列优点，又能像页式系统那样，很好地解决内存的外碎片问题。关键词：地址转换，虚拟地址，物理地址，偏移，越界目录1 需求分析11.1 可变分区存储管理的地址转换11.2 分页存储管理的地址转换41.3 分段存储管理的地址转换51.4 段页式存储管理的地址转换72 概要设计152.1 可变分区存储管理的地址转换的概要设计152.2 分页存储管理的地址转换的概要设计192.3 分段存储管理的地址转换的概要设计202.4 段页式存储管理的地址转换的概要设计243 详细设计263.1 可变分区存储管理的地址转换的详细设计263.2 分页存储管理的地址转换的详细设计323.3

5、分段存储管理的地址转换的详细设计373.4 段页式存储管理的地址转换的详细设计394 调试与操作说明444.1 可变分区存储管理的地址转换的操作说明444.2 分页存储管理的地址转换的操作说明444.3 分段存储管理的地址转换的操作说明454.4 段页式存储管理的地址转换的操作说明46总 结47致 谢48参考文献49附 录501 需求分析本课程设计题目：地址转换过程的模拟实现。课程设计任务及要求：（1）搜集地址转换过程的模拟实现可能涉及到的知识和相关资料。（2）应用Microsoft Visual C+ 6.0集成开发环境，设计并实现一个地址转换模拟程序。（3）确保地址转换模拟程序能正确运行。

6、（4）参加答辩，撰写课程设计报告。运行环境：Windows XP系统 Pentium（R） Dual-core CPU 3.20GHz 1.96G内存 200G硬盘。开发工具：本实验使用VC+ 6.0平台，使用基本的控制台应用程序，单文档结构，主要数据结构是结构体间的关系。打开VC+6.0建立一个新的C+源文件，根据数据结构编写代码。1.1 可变分区存储管理的地址转换一、任务要求该程序要对每一个虚地址计算其代表的有效地址所对应的物理地址，并进行越界判断，打印出每个虚地址的物理地址。能够输入进程名称和内存需求量，按页式存储管理方式把进程分成若干页，分配到内存中的若干个块中，同时生成并显示相应的页

7、表。输入一个逻辑地址能够转换并输出相应的物理地址。二、基本思想可变分区的基本原理是：可变分区是指在作业装入是，依据它对内存空间实际的需求量来划分内存的分区，因此，每个分区的尺寸与进入他的作业大小相同。它能有效解决固定分区的内存碎片问题，是一种较为常用的存储管理方法。因为在系统运行过程中，内存中分区的数目和大小都是可变的，所以这种可变式分区也称为动态分区8。三、存储器的基本性能参数评价存储器性能的参数主要有三个方面：容量、速度与价格。存储器容量用S=W×l×m表示，W为存储器字长，l为存储器字数，m则为存储器体数。评价存储器的速度一般有以下几个参数：访问时间（access t

8、ime）Ta：从存储器接到读请求到所读的字传送到数据总线上的时间间隔。存储周期Tm：连续两次访问存储器之间所必需的最小时间间隔。一般Tm > Ta。存储带宽Bm：存储器被连续访问时所提供的数据传输速流，单位是位（或字节）/秒。存储器的价格通常用单位字节价格来表示。若总容量为S的存储器的总价格为C，则单位字节价格cC/S。四、存储器层次结构的基本原理程序设计人员总是希望存储器的速度尽可能的高，以与处理器的速度相匹配；存储器的容量尽可能的大，以装下可能极大的程序；因此，高速度、大容量、低价格始终是存储体系的设计目标。一方面，经过几十年的发展，存储器的工艺实现技术有了突飞猛进的发展，高速、大容

9、量、低价的存储器件以惊人的速度生产出来。尽管如此，存储技术的发展证明单一工艺的单一存储器很难同时满足容量、价格、速度三方面的性能要求。事实上，对容量与速度、速度与价格、容量与价格的性能要求是相互有矛盾的。而且，存储器速度的改进始终跟不上CPU速度的提高 。另一方面，所有程序都具有这样的行为特性：程序倾向于再次使用最近刚用过的数据和指令。这样的局部性反映在空间和时间两个方面。空间局部性（spatial locality）：如果某个数据或指令被引用，那么地址邻近的数据或指令不久很可能也将被引用。时间局部性（temporal locality）：如果某个数据或指令被引用，那么不久它可能还将再次被引用

10、。为了满足对存储器的性能要求，随着存储技术的不断发展，根据程序本身这种局部性的行为特性以及小硬件速度更快的设计原则，基于不同容量和速度的多种存储器所构成的存储器层次结构很自然地就产生了。一个存储器层次结构由多级不同类型的存储器构成；越靠近CPU的存储器容量越小、速度越快、价格越高，离CPU越远的存储器容量越大、速度越慢、价格越低；第i级存储器存储的信息是第i-1级存储信息的子集（根据时间局部性），相邻两级存储器之间以块为单位进行信息交换（根据空间局部性）；各级存储器借助辅助软硬件构成一个整体，使得该存储体系具有接近于第n级存储器速度、接近于第1级存储器容量和单位字节价格的性能。存储器层次结构是

11、由多级存储器构成的，但管理是以两级存储器为单位来进行的，而且一般只有在相邻两级存储器之间可以进行信息交换。下面以两级存储器层次结构（简称存储层次）为例介绍存储器层次结构的一些基本概念。块（Block）：相邻两级存储器之间信息交换的最小单位。块大小一般是固定的，也可以是可变的。若块大小固定，则两级存储器的容量为块大小的整数倍。命中率（Hit Rate）H：CPU产生的有效地址可以直接在高层存储器中访问到的概率。失效率（Miss Rate）M：CPU产生的有效地址直接在高层存储器中访问不到的概率。M=1-H。命中时间（Hit Time）：访问高层存储器所需的时间，其中包括本次访问是命中还是失效的判

12、定时间。失效损失（Miss Penalty）：用低层存储器中相应的块替换高层存储器中的块，并将该块传送到请求访问的设备（通常是CPU）的时间。它又可细分为访问时间和传送时间（transfer time）两部分。其中前者指访问高层存储器失效时，在低层存储器中访问到块中第一个字的时间，又称访问延迟（access latency）。后者则是传送块内其它字的附加时间。访问时间与低层存储器的延迟有关，而传送时间则依赖于两级存储器之间的传输带宽和块大小。五、存储器层次结构的性能由于存储器层次结构的设计目标之一是使其速度接近于高层存储器的速度，因此容易根据命中率的高低来评价存储器层次结构性能的好坏。由于命中

13、率或失效率与硬件速度无关，因而这样的评价是很片面的。更好的评价存储器层次结构的性能参数是平均存储访问时间（average memory-access time），其定义如下：平均存储访问时间命中时间 失效率 × 失效损失应该注意的是尽管用平均存储访问时间评价存储器层次结构的速度性能比简单的用命中率来评价要好，平均存储访问时间仍然是性能的一种间接测度，它无法完全替代执行时间这个最准确的性能参数。处理器的性能是计算机设计的最终依据，所以在选择降低平均存储访问时间的策略时应考虑对CPU性能的影响，保证设计方案不仅能降低平均存储访问时间，还能有益于改进CPU的性能，如同时提高CPI（Cycl

14、es Per Instruction，简称为指令的平均周期数）。下面讨论一下存储器层次结构设计对CPU设计的影响。在不支持存储器层次结构的系统中，由于所有的存储访问都需要相同的时间，所以处理器的设计相对简单。而在存储器层次结构中对高层存储器的访问存在失效问题，这意味着CPU必须能够处理可变的存储访问时间。当失效损失较小，只有几十个时钟周期时，CPU通常采用等待块传输结束的策略。而当失效损失很大，达到CPU时钟的几千倍时，仍让CPU空闲着等待传输结束就太浪费了。一般采用中断使CPU切换到其它进程去执行的办法。但用这种方法来避免失效损失带来的额外开销意味着任何存储访问都可能导致CPU中断。这样CP

15、U还必须能够恢复引起这种中断的存储地址，使系统在失效处理时知道要传送哪一块。当存储传送结束时，恢复原来被中断的进程，重新执行引起访问失效的那条指令。处理器还必须设有一些机制以确定所需信息是否在存储器层次结构的最高层存储器中。在每次存储访问时都要作这种判定检查，因而会影响命中时间。为了保证达到可接受的性能，这种检测机制通常用硬件实现。要实现存储器层次结构，处理机还必须有在相邻两级存储器之间传送信息块的机制。如果块传送只需几十个时钟周期，那么这种传送机制一般用硬件来控制；如果需要几千个时钟周期，则可以用软件方法实现。1.2 分页存储管理的地址转换一、任务要求这个程序要把给出的虚拟地址找到相对应的物

16、理地址，打印出相应的页号，内存块号及相应的物理地址。二、意义能够理解分页存储的思想，了解页表的结构。掌握逻辑地址与逻辑的转换。了解内存的分配及回收。当创建一个进程之后，根据这个进程的大小，会给这个进程分配内存，可能时连续的内存，页可能时不连续的。首先会将进程分成若干的页，每页对应的内存中的一个无力块。页的大小等于物理块的大小，这样就形成了页和内存块对应的页表。进程执行的会先访问页表。三、基本思想在存储器管理中，连续分配方式会形成许多“碎片”。虽然可能通过“紧凑”方法将许多碎片拼接成可用的大块空间，但须为之付出很大开销。如果允许将一个进程直接分散地装入到许多不相邻的分区中，则无须再进行“紧凑”。

17、基于这以思想而产生了离散式分配方式。如果离散分配的基本单位式页，则称为基本分页存储管理方式，或称之为纯分页存储方式，它将内存分成多个同样大小的存储区，每个进程页分成同样大小的页，较小的进程需要较少的页，较大的进程需要较多的页，进程在调入内存式，所有的进程页放入内存中的空闲页，并建立页表【1】。这种方法解决了分区方案中所固有的许多问题。分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，也把内存空间分成与页面相同大小的若干个存储块，称为（物理）块或页框（frame），页同样为它们加以编号。在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻的物理块中。

18、由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”。在分页系统中的页面其大小应适中。页面若太小，一方面虽然可使内存碎片减小，从而减少了内存碎片的总空间，有利于提高内存利用率，但另一方面也会使每个进程占用较多的页面，从而导致进程的页表过长，占用大量内存；此外，还会降低页面换进换出的效率。1.3 分段存储管理的地址转换一、任务要求该程序要对每一个虚地址计算其代表的有效地址所对应的物理地址，并进行越界判断，要求打印每个虚地址的所在段段号、段内偏移、内存始址及相对应的物理地址。二、基本思想把程序按内容或过程（函数）关系分成段，每段有自己的名字。一个用户作业或进程所包含的段对应于

19、一个二维线性虚拟空间，也就是一个二维虚拟存储器。段式管理程序以段为单位分配内存，然后通过地址映射机构把段式虚拟地址转换成实际的内存物理地址。和页式管理一样，段式管理也采用只把那些经常访问的段驻留内存，而把那些将来一段时间内不被访问的段放入外存，待需要时自动调入的方法实现二维虚拟存储器。在分段式存储管理中，作业的地址空间由若干个逻辑分段组成，每一分段式一组逻辑意义完整的信息集合，并有自己的名字（段名）。每一段都是以0开始的连续的一维地址空间，整个作业则构成了二维地址空间。分段式存储管理以段为基本单位分配内存，且每一段必须分配连续的内存空间，但各段之间不要求连续。由于各段的长度不一样，所以分配的内

20、存空间大小也不一样。因此，所谓分段式管理，就是管理由若干段组成的作业，并且按段来进行存储分配。由于分段式管理的作业地址空间是二维的，所以分段式存储管理的关键在于如何把分段地址结构变成一维的地址结构。与分页存储管理一样，分段式存储管理采用动态重定位技术来进行地址转换4。三、段的共享与保护1 段的共享在多道环境下，常常有许多子程序和应用程序是被多个用户所使用的。如果每个用户进程或作业都在内存保留它们共享程序和数据的副本，那就会极大地浪费内存空间。最好的办法是内存中只保留一个副本，供多个用户使用，称为共享。一段程序为多个进程共享时（1） 要求在执行过程中，该段程序的指令和数据不能被修改。（2） 在段

21、表中设立相应的共享位来判别该段是否正被某个进程调用。显然 一个正在被某个进程使用或即将被某个进程使用的共享段是不应该调出内存的。2 段的保护与页式管理时相同，段式管理的保护主要有两种：地址越界保护法和存取方式控制保护法。图1.1 段的共享1.4 段页式存储管理的地址转换一、任务要求该程序要实现段页式存储管理中逻辑地址到物理地址的转换，打印出访问序号、虚地址、段号、段内页号、页内偏移、内存块号、物理地址和越界判断信息。并且能够检查地址的合法性，如果合法则进行转换，否则显示地址非法的原因。二、基本思想各个进程的虚拟空间被划分成若干个长度相等的页。页长的划分和内存与外存之间的数据传输速度及内存大小等

22、有关。一般每个页长大约为14K，经过页划分之后，进程的虚拟地址变为页号p与页内地址w所组成。除了将进程的虚拟空间划分为大小相等的页之外，页式管理还把内存空间也按页的大小划分为片或者页面。这些页面为系统中的任一进程所共享。从而与分区管理不一样，分页管理时，用户进程在内存空间内除了在每个页面内地址连续之外，每个页面之间不再连续。第一是实现了内存中碎片的减少，因为任意碎片都会小于一个页面。第二是实现了由连续存储到非连续存储的这个飞跃，为在内存中局部地、动态地存储那些反复执行或即将执行的程序和数据段打下了基础。怎样由页式虚拟地址转变为内存页面物理地址？页式管理把页式虚拟地址与内存页面物理地址建立一一对

23、应页表，并用相应的硬件地址变换机构，来解决离散地址变换问题。段页式系统的基本原理，是基本分段存储管理方式和基本分页存储管理方式原理的结合，即先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名。图1.2示出了一个作业的地址空间和地址结构。图1.2 段页式的地址空间和地址结构该作业有三个段，页面大小为4 KB。在段页式系统中，其地址结构由段号、段内页号及页内地址三部分所组成，如下图1.3所示。  图1.3 段页式的地址结构组成具体来说，把整个内存分成大小相等内存块，内存块从0开始依次编号。把用户程序分成若干段，每段有个段名。页面的大小和内存块相同，每段的各个页面都

24、分别从0开始依次编号。虚空间的最小单位是页而不是段，内存就被分为若干个页，且每段所拥有的程序和数据在内存中可以分开存放，分段大小也不再受内存可用区的限制。段式和页式存储管理各有优缺点，段页式存储管理系统，用分段的方法来分配和管理虚拟存储器，而用分页的方法来分配和管理主存。既有段式系统便于实现段的共享，段的保护，动态链接和段的动态增长等一系列优点，又能像页式系统那样，很好地解决内存的外碎片问题3。设计时需要结合分段和分页的各自特点，扬长避短充分发挥各自优势。下表列出的是简单分页、简单分段、虚拟内存分页和虚拟内存分段各自的特点。表1.1 分页和分段的特点简单分页简单分段虚拟内存分页虚拟内存分段内存

25、分为小的固定的区域，称为帧内存不划分内存分为小的固定的区域，称为帧内存不划分程序由编译器或内存管理系统分页由程序员决定段的划分程序由编译器或内存管理系统分页由程序员决定段的划分帧内有碎片无内部碎片帧内有内部碎片无内部碎片无外部碎片有外部碎片无外部碎片有外部碎片操作系统必须为每个进程建立一个页表，以显示页在内存的哪一帧操作系统必须为每个进程建立一个段表，以显示每个段载入内存的地址和段长操作系统必须为每个进程建立一个页表，以显示页在内存的哪一帧操作系统必须为每个进程建立一个段表，以显示每个段载入内存的地址和段长操作系统必须建立一个空帧表操作系统必须建立一个内存的空闲块表操作系统必须建立一个空帧表操

26、作系统必须建立一个内存的空闲块表处理机用页号和页位移量来计算绝对地址处理机用段号和段位移量来计算绝对地址处理机用页号和页位移量来计算绝对地址处理机用段号和段位移量来计算绝对地址进程运行时，该进程所有的页都必须调入内存进程运行时，该进程所有的段都必须调入内存进程运行时，并不需要将其所有的页调入内存，页在其需要时才读入内存进程运行时，并不需要将其所有的段调入内存，段在其需要时才读入内存对段页式的评价：段页式基本上结合了段式和页式的优点，而克服了二者的缺点。段页式的内存利用率比段式高，比页式低。由于以页面为单位划分内存，段页式消除了段式的外部存储碎片，但和页式一样存在内部碎片，其内部碎片比页式要多页

27、式式平均每个程序有一页有碎片，段页式则是平均每段有一页有碎片。段页式的共享实现和保护实现与段式一样好，比页式好。只要欲共享作业的段表中有相应的表目指向该共享段在内存中的页表地址即可。段页式的动态扩充实现得比段式和页式都要好，提供了动态链接的便利。但是段页式的表空间支出、地址映射时间等管理代价比段式与页式都高。需要的内存和硬件也有所增加，如果不采用快速辅助寄存器的方式提高CPU访问速度，将使运行速度大大下降。段页式管理对大中型机来说是使用的最广泛、最灵活的一种存储管理技术9。三、静态页面管理静态页面管理方法是在作业或进程开始执行之前，把该作业或进程的程序段和数据全部装入内存的各个页面，并通过页表

28、和硬件地址变换机构实现虚拟地址到内存物理地址的地址映射。1 内存页面的分配与回收静态分页管理的第一步是为要求内存的作业或进程分配足够的页面。系统依靠存储页面表、请求页面表以及页表来完成内存的分配。（1）页表最简单的页表由页号与页面号组成，页表在内存中占有一块固定的存储区。页表的大小有进程或作业的长度决定。每个进程至少要拥有一个页表。（2）请求表用来确定作业或进程的虚拟空间的各页在内存中的实际对应位置。系统必须知道每个作业或进程的页表起始地址和长度，以进行内存的分配和地址变换，另外请求表中还应包括每个作业或进程所要求的页面数。（3）存储页面存储页面表也是整个系统一张，存储页面表指出内存各个页面是

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

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

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

32、者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。（2）先进先出置换算法（FIFO）：优先淘汰最早进入的页面，亦即在内存中驻留时间最久的页面。（3）最近最久未使用（LRU）算法：选择最近最长时间未访问过的页面予以淘汰。内存保护：页式管理提供两种方式的内存保护：一是：地址越界保护。二是：通过页表控制对内存信息的存取操作方式以提供保护。地址越界保护：由地址变换机构中的控制存储器的值页表长度和所要访问的虚地址相比较来完成。存取控制保护的实现则是在页表中增加相应的保护位即可。五、段式管理分区式管理和页式管理时的进程的地址空间结构都是线性的，这要求对源程序进行编译连接时，把源程序中的主程序

33、、子程序、数据区等按线性空间的一维地址顺序排列起来。共享子程序和数据变得很困难，再者从链接的角度来看，分区管理和页式管理只能采用静态链接。段式存储管理是基于为用户提供一个方便的灵活的程序设计环境而提出来的。段式管理的基本思想是：把程序按内容或过程（函数）关系分成段，每段都有自己的名字。一个用户进程或作业所包含的段对应于一个二维线性虚拟空间，也就是二维虚拟存储器。段式管理程序以段为单位分配内存，然后通过地址映射机构把段式虚拟地址转换成实际的内存物理地址。和页式管理一样，段式管理也采用只把那些经常访问的段驻留内存，而把那些在将来一段时间内不被访问的段放在外存，待需要时自动调入的方法实现二维虚拟存储

34、器。段式管理把一个进程的虚拟空间设计成二维结构，即段号s与段内相对地址w。与页式管理不一样的是，页式管理中，被划分的页号按顺序编号递增排列，属一维空间，而段式管理中段号与段号之间无顺序关系。另外段的划分也不像页的划分那样具有相同的页长，段的长度是不固定的。每个段定义一组逻辑上完整的程序或数据。例如，一个进程中的程序和数据可划分为主程序段、子程序段、数据段与工作区段。每个段是一个首地址为零的、连续的一维线性空间。根据需要段长可以动态的增长。对端式虚拟空间地址的访问包括两个部分：段名和段内地址。段式管理中以端为单位分配内存，每段分配一个连续的内存区，由于各段长度不等，所以这些存储区的大小不一，而且

35、统一进程所包含的各段之间不要求连续。段式管理的内存分配与释放在作业或进程的执行过程中动态进行。首先，段式管理程序为一个准备进入内存准备执行的进程或作业分配部分内存，以作为该进程的工作区和放置即将执行的程序段。随着进程的执行，进程根据需要随时申请调入新段和释放老段。进程对于内存区的申请和释放可分为两种情况。一种是当进程要求调入某一段时，内存中有足够的空闲区满足该段的内存要求。另一种是内存中没有足够的空闲区。对于第一种情况，系统要用相应的表格或数据结构来管理内存空闲区，以便对用户进程或作业的有关程序段进行内存分配和回收。事实上，可以采用和动态分区式管理相同的空闲区管理方式。即把内存各空闲区按物理地

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

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

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

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

40、二维空间地址，这与段式管理相同。首先一个进程中所包含的具有独立逻辑功能的程序或数据仍被划分为段，并有各自段号s。这反映了段式管理的特征。其次，对于段s中的程序或数据，则按照一定的大小将其划分为不同的页。和页式系统一样最后不足一页的部分仍然占一页。这反映了页式特征。从而段页式管理时的进程的虚拟空间中的虚拟地址由三部分组成即段号s，页号p和页内相对地址d，如下图1.4所示： wSpd图1.4 虚拟地址的s、p和d程序员可见的仍是段号s和段内相对地址w。p和d是由地址变换机构把w高几位解释成页号p，以及把剩下的低位解释成页内地址d。由于虚拟空间的最小单位是页而不是段，从而内存可用区也就被划分为若干个

41、大小相等的页面，且每段所拥有的程序和数据在内存中可以分开存放。分段的大小也不受内存可用区的限制。段表和页表：为了实现段页式管理，系统必须为每个作业或进程建立一张段表，管理内存分配与释放、缺段处理、存储保护和地址变换等。另外，由于一个段又被划分成了若干页，每个段又必须建立一张页表，把段中虚页转变成内存中的实际页面。显然与页式管理相同，页表中也要有实现缺页中断处理和页面保护等功能的表项。另外由于在段页式管理中，页表不再是属于进程而是属于某个段，因此段表中应该有指出该段所对应的页表始址和页表长度。动态地址变换过程：在一般使用段页式存储管理的计算机系统中，都在内存中辟出一块固定的区域存放进程的段表和页

42、表。因此，在段页式管理系统中，要对内存中指令或数据进行一次存取的话，至少需要访问3次以上的内存。2 概要设计2.1 可变分区存储管理的地址转换的概要设计一、可变存储分区存储管理技术的模拟实现（1） 建立空闲表。（2） 从取值范围为02047的随机数序列中选出20各随机数，分别作为访问数据的MAIN和段X的虚地址。（3） 对每一个虚地址计算其代表的有效地址随对应的物理地址，并进行越界判断（4） 要求打印每个虚地址的所在对应的物理地址和越界判断。二、可变分区的实现原理 1 空间的分配与回收 采用可变分区存储管理，系统中的分区个数与分区的大小都在不断地变化，系统利用“空闲区表”来管理内存中的空闲分区

43、，其中登记空闲区的起始地址、长度和状态。当有作业要进入内存时，在“空闲区表”中查找状态为“未分配”且长度大于或等于作业的空闲分区分配给作业，并做适当调整；当一个作业运行完成时，应将该作业占用的空间作为空闲区归还给系统。可以采用首先适应算法、最佳（优）适应算法和最坏适应算法三种分配策略之一进行内存分配。图2.1 内存分配流程图2.2 内存回收时的状况2 地址转换和存储保护可变分区存储管理一般采用动态重定位的方式，为实现地址重定位和存储保护，系统设置相应的硬件：基址/限长寄存器（或上界/下界寄存器）、加法器、比较线路等。基址寄存器用来存放程序在内存的起始地址，限长寄存器用来存放程序的长度。处理机在

44、执行时，用程序中的相对地址加上基址寄存器中的基地址，形成一个绝对地址，并将相对地址与限长寄存器进行计算比较，检查是否发生地址越界。图2.3 可变分区地址转换示例3 存储碎片与程序的移动 所谓碎片是指内存中出现的一些零散的小空闲区域。由于碎片都很小，无法再利用。如果内存中碎片很多，将会造成严重的存储资源浪费。解决碎片的方法是移动所有的占用区域，使所有的空闲区合并成一片连续区域，这一技术称为移动技术（紧凑技术）。移动技术除了可解决碎片问题还使内存中的作业进行扩充。显然，移动带来系统开销加大，并且当一个作业如果正与外设进行I/O时，该作业是无法移动的。图2.4 移动技术（紧凑技术）Cache/主存的

45、写策略所有的取指访问是读操作，而大部分指令不对存储器进行写操作， 所以，对于Cache的访问主要是读操作。根据第三章指令使用频度分析数据可知，一般程序的数据传送指令中，取数操作（Load）大约是存数操作（Store）的2倍，而且在存储器数据传送（memory transfer）中，写操作所占比例不到10%。根据高频事件高速处理的设计原则，在Cache中应尽量优化读操作的能力，同时由Amdahl定律可知，面向高性能的设计不能忽视写操作的速度。通常，Cache的读操作较易快速实现。一般，在读取并比较标志的同时就可以读取相应数据行，即一得到来自CPU的块帧地址就可以开始读操作。如果读命中，则读出的数

46、据行立即送往CPU，而如果读失效，读出的数据作废，这样作既没好处，也没损失。写操作的情况就不同了。处理器指定写操作的数据宽度一般在18字节之间，即一个写操作仅改变一个数据块某一部分的内容。通常写操作又细分为三个步骤：（1）读取源数据块；（2）修改其中的一部分；（3） 写回修改后的数据。因为修改步骤不能与标志检查并行进行，所以一定要等标志检查确定命中后才能进行修改步骤。这样，写操作所需的时间通常比读操作长。在Cache设计中有多种不同的写策略，基本的写策略有如下两种：（1）直写技术（write through）信息被写入Cache行的同时，利用CPU和主存之间的直接数据通路写入主存的对应块中。（

47、2）回写技术（write back）信息只写入Cache的相应行。仅当被修改过的行被替换出Cache时，才将它写入主存的相应存储块中。根据Cache行的信息与对应主存块中的信息相同与否，采用回写技术的Cache行被分为“干净的”或“脏的”两种。“干净的”行即该数据行在Cache中未被修改过，数据与其主存中的对应块相同。而“脏的”行即该数据块在Cache中已被修改过。因此当“干净的”行被替换出Cache时，不必将该行写回主存。相反，当“脏的”行被替换时，必须将其写回主存。为区分行是“干净的”还是“脏的”，通常为每个Cache行设置一个称为“脏位”（也称“修改位”）的标志位，指示该Cache行是否

48、曾被修改过。回写技术和直写技术各有利弊。回写技术的优点是：Cache命中时，写操作是以写Cache的速度进行，而且在一个数据块内的多次写操作只需要对低层存储器写一次。由于每个写操作都不必写主存，因而回写技术有利于降低Cache/主存存储器层次结构对主存带宽的要求。这一性质使回写技术在多处理器（机）系统设计中颇具吸引力。对于直写技术，读操作引起的Cache失效不会导致对低层存储器的写操作，而且直写技术的硬件实现更为简单。直写技术的另一个优点是主存中总是保存着数据的最新拷贝，这一性质对I/O和处理器（机）系统都非常重要。这样，在多处理器（机）系统的设计中，既希望利用回写技术减少每个处理器（机）与主

49、存之间的数据传输量，又希望用直写技术保证Cache和主存的一致性。如果采用直写技术，那么在对低层存储器的写操作期间，CPU必须停下来等待，CPU的这段等待时间被称为写停顿延迟。通常所用的减少写停顿延迟的办法是设置写缓冲，使CPU在存储器更新期间能继续工作。当出现写失效时，无论直写技术还是回写技术都存在是否要将修改的数据块装入Cache的问题，一般有两种选择方案：（1）写分配（write allocate）将要写的数据装入Cache，然后进行和写命中时相同的操作。这种方法与读失效时的处理方法类似。（2）无写分配（no write allocate）也称为绕写（write around）。直接对低

50、级存储器中的数据块做改写操作，不再将此数据块装入Cache。虽然这两种方案对直写技术或回写技术都适用，但通常的做法是在采用回写技术时选择写分配，这样对该数据块的后续写操作可以在Cache中进行（时间局部性原理的自然应用）；采用直写技术时一般选择无写分配，因为按直写技术，即使该数据块有后续写操作仍需对主存作改写操作。三、动态重定位可变分区存储技术的优缺点优点：1 所有的内存碎片通过程序浮动的方式把他们重新组合成一个新的分区在利用因而内存的使用效率非常高。2 地址转换要到最后，即CPU准备开始执行线程时才进行。因此，操作系统在地址转换的方面的开销是极小的3 建立在可变分区基础之上，对于不同的进程内

51、存可以调剂。操作系统运行应用程序的能力大大提高。缺点：空闲区表的形成，分区起始物理地址数据表的生成，都要消耗相当多的操作系统资源。2.2 分页存储管理的地址转换的概要设计一、数据结构void Pagination() /（2）建立两个作业的页表（用两个数组或一个数组）int PT12=5,7 /申明页表变量int RN1M,RN2M,temp /引入随机数short p,d /将虚地址分解成页号P和页内位移dGetchar() /获得一个字符cout<<"访问序号 虚地址t 物理地址 页号t 页内位移 块号t 越界判断信息n"/定义输出次序二、方法原理图2.5

52、分页系统的地址变换机构当进程要访问某个逻辑地址中的数据时，分页地址变换机构会自动地将有效地址（相对地址）分为页号和页内地址两部分，再以页号为索引去检索页表。查找操作由硬件执行。在执行检索之前，先将页号与页表长度进行比较，如果页号大于或等于页表的长度，则表示本次所访问的地址已超越进程的地址空间。于是，这一错误将被系统发现并产生一地址越界中断。若未出现越界错误，则将页表始地址与页号和页表项长度的乘积相加，便得到该表项在页表中的位置，于是可从中得到该页的物理块号，将之装入物理地址寄存器中。与此同时，再将有效地址寄存器中的页内地址送入物理地址寄存器的块内地址字段中。这样便完成了从逻辑地址到物理地址的变

53、换【2】。2.3 分段存储管理的地址转换的概要设计一、功能模块在此段式存储管理系统中，我们采用以下数据结构来存储数据，存储结构用结构体和结构体数组来实现：表2.1 段式数据结构段长起始逻辑地址实际起始地址Struct duanlong capacity；/该段的长度long addr；/起始逻辑地址long realaddr；/该段实际起始地址表2.2 段表的数据结构段进程名调用情况段数该进程的总占用量struct duanbiaoduan duans10;char processname20; / 进程的名字int Isdiaoyong; /是否被调用int num; /段的数目long t

54、otal; /该进程的总占用量;二、分段系统数据结构段表：每个进程建立一个，用于描述进程的分段情况，记载进程的各个段在物理内中分区的映射情况，其中包含段号，段长，段基址及对相段存取控制权限信息。空闲分区表：用于记载物理内存中的空闲分区情况。地址变换1）根据逻辑地址中的段号检索进程段表，获得指定段的段表项。2）判断是否地址越界，比较逻辑地址中的段内偏称量与段表中段长，若超过段的长度，则产生存储保护中断（该中断将由操作系统处理）。3）把逻辑地址中的段内偏称量与段表表项中的段基址相加，从而得到物理地址。段表寄存器1 段表同样被保存在物理内存中分页：记在页表地址寄存储器中（当前运行进程页表起始地址和页

55、表长度）。2 段表寄存器：实现快速地址变换，用来存放当前执行进程的段表在物理内存中的起始位置。3 当创建进程，将进程的程序和数据装入内存时，系统为之建立段表，并将段表的起始地址。三、分段存储管理的地址转换的模拟实现图2.6 分段存储管理的模拟实现（1） 建立段表、作业表、主存分块表MBT。（2） 从取值范围为02047的随机数序列中选出20各随机数，分别作为段MAIN和段X的虚地址。（3） 对每一个虚地址计算其代表的有效地址随对应的物理地址，并进行越界判断。（4） 要求打印每个虚地址的所在段段号、段内偏移、内存始址及对应的物理地址。段式存储的实现原理：1 段式虚存空间段式管理管理把一个进程的虚拟地址空间设计成二维结构，即短号s与段内相对地址w。与页式管理时不一样的是，页式管理中，被划分的页号按顺序编号递增排列，属一维空间，而段式管理中的段号与段号之间无顺序关系。另外，段的划分也不像页的划分那样具有相同的页长，段的长度的不固定的。每个段定义一组逻辑上完整的程序或数据。每个段是一个首地址为零、连续的一维线性空间。根据需要，段长课