第四章 存储器管理

第四章存储器管理4.1存储器的层次结构4.2程序的装入和链接4.3连续分配方式4.4基本分页存储管理方式4.5基本分段存储管理方式4.6虚拟存储器的基本概念4.7请求分页存储管理方式4.8页面置换算法4.9请求分段存储管理方式

存储器是计算机系统的重要组成部分，操作系统中的存储管理是指对内存的管理，它是操作系统的重要功能之一。充分利用内存，为多道程序并发执行提供存储基础尽可能方便用户使用自动装入用户程序用户程序中不必考虑硬件细节系统能够解决程序空间比实际内存空间大的问题存储器管理的目的：程序的长度在执行时可以动态伸缩内存存取速度快存储保护与安全共享与通信及时了解有关资源的使用状况实现的性能和代价要合理内存空间的管理、分配与回收内存共享--代码共享，数据共享通过代码共享节省内存空间，提高内存利用率通过数据共享实现进程通信存储保护防止地址越界防止操作越权扩充内存容量

用户在编制程序时，不应该受内存容量限制，所以要采用一定技术来“扩充”内存的容量，使用户得到比实际内存容量大的多的内存空间，通过虚拟存储技术实现地址映射（重定位）存储器管理的功能：存储系统设计三个问题：容量、速度和成本容量：需求无止境速度：能匹配处理器的速度成本问题：成本和其它部件相比应在合适范围之内解决方案：采用层次化的存储体系结构当沿着层次下降时每比特的价格将下降，容量将增大速度将变慢，处理器的访问频率也将下降4.1存储器的层次结构4.1.1多级存储器结构容量愈来愈大访问数据的速度愈来愈慢价格愈来愈便宜寄存器高速缓存主存磁盘缓存磁盘可移动存储介质CPU寄存器主存辅存提高存储系统效能关键点：程序存储访问局部性原理程序执行时，有很多的循环和子程序调用，一旦进入这样的程序段，就会重复存取相同的指令集合对数据存取也有局部性，在较短的时间内，稳定地保持在一个存储器的局部区域,处理器主要和存储器的局部打交道,在经过一段时间以后，使用的代码和数据集合会改变设计多级存储的体系结构原则：访问级别较低存储器比率小于级别较高存储器比率例：假设两级存储器： 第I级包含1KB，存取时间为0.1μs 第II级包含1MB，存取时间为1μs存取I级中的内容，直接存取存取II级，首先被转移到I级，然后再存取假设确定内容所在位置时间可以忽略若在I级存储器中发现存取对象的概率是95%，则平均访问时间为：结果非常接近I级存储的存取时间存储保护设施对主存中的信息加以严格的保护，使操作系统及其它程序不被破坏，是其正确运行的基本条件之一.

问题：多个程序同时在同一台机器上运行怎样才能互不侵犯？为了保证软件程序只影响程序的内部硬件可提供如下功能：界地址寄存器（界限寄存器）存储键1.界地址寄存器（界限寄存器）在CPU中设置一对界限寄存器来存放该用户作业在主存中的下限和上限地址每当CPU要访问主存，硬件自动将被访问的主存地址与界限寄存器的内容进行比较，以判断是否越界如果未越界，则按此地址访问主存，否则将产生程序中断——越界中断（存储保护中断）10005000OSUser1

Jump6000User2将6000与上限地址5000比较，越界则越界中断10006000下界上界2.存储键每个存储块有一个由二进位组成的存储保护键一用户作业被允许进入主存，OS分给它一个唯一的存储键号并将分配给该作业各存储块存储键也置成同样键号当OS挑选该作业运行时，OS将它的存储键号放入程序状态字PSW存储键（“钥匙”）域中每当CPU访问主存时，都将该主存块的存储键与PSW中的“钥匙”进行比较A块B块C块001010100101000存储键取保护位0－不保护1－保护…………001007钥

Key11只要键匹配，存取均可键不匹配，则不可存是否可取要看保护位举例：存A，取A，均可以(键Key匹配)存B，取B，均不可以(键不匹配，且取保护)存C，不可以(键不匹配)

取C，可以，因取保护位为0，即不保护取程序状态字4.1程序的装入和链接

在多道程序环境下，要使程序运行，必须创建进程，而创建进程第一件事就是将程序和数据装入内存。一个用户源程序要变为在内存中可执行的程序，通常要进行以下处理：（1）编译：由编译程序将用户源程序编译成若干个目标模块；（2）链接：由链接程序将目标模块和相应的库函数链接成装入模块；（3）装入：由装入程序将装入模块装入内存。库目标程序块1目标程序块2第一步链接程序装入模块第二步装入程序第三步用户源程序编译程序……内存1.绝对装入方式如果在编译时，事先知用户程序在内存的驻留位置，则编译程序在编译时就产生绝对地址的目标代码。装入程序就直接把装入模块中的程序和数据装入到指定的位置，（不需进行地址转换）。程序中所使用的绝对地址，既可在编译或汇编时给出，也可由程序员直接赋予。但在由程序员直接给出绝对地址时，不仅要求程序员熟悉内存的使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。因此，通常是宁可在程序中采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址。

4.2.1程序的装入1.名空间、地址空间和存储空间在我们用汇编语言或高级语言编写程序时，总是通过符号名来访问某一单元。我们把程序中由符号名组成的空间称为名空间。源程序经过汇编或编译形成的程序，通常是以0为基址进行顺序编址，这样的地址表示形式称为相对地址,也叫做逻辑地址或虚地址，把该程序逻辑地址组成的集合叫做程序的逻辑地址空间(简称地址空间)。存储器中每个具体存储单元都有不同的编号，每个编号就是一个物理地址，整个程序在内存中存储后所占用的物理地址的集合形成程序的物理地址空间(简称存储空间)。2.重定位（地址映射）装入方式名空间、地址空间和存储空间的关系GotoL1L1：…源程序编译Goto2…目标代码0123名空间地址空间装入Gotoa＋2…内存(运行程序)aa＋1存储空间…a＋22.地址映射逻辑地址是一个“虚”的概念，处理机不能直接访问逻辑地址，而物理地址则是“实”的。因而，操作系统必须提供这样的功能，把程序执行时要访问的地址空间中的逻辑地址变换成内存空间中对应的物理地址。这种把虚地址变换成实地址的过程称作地址映射。若用A表示地址空间，用M表示内存空间，则地址映射可表示成：f：Ａ→Ｍ(1)静态映射：当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换。由重定位

装入程序完成，它把分配给目标程序的内存区的起始地址B作为基地址，在把该程序装入指定内存区的同时，将程序中的所有逻辑地址翻译成相对于基地址B的物理地址，即ｆ（ａ）＝Ｂ＋ａ优点:容易实现，无需硬件支持，地址重定位由专门设计的程序来完成。在早期的操作系统中大多数都采用这种方法。缺点:程序经地址重定位后就不能移动了，因而不能重新分配内存，不利于内存的有效利用。

0：B=10000

100：

LOAD1，2500

10100：

LOAD1，12500

2500：

365

12500：

365

2600：12600：

逻辑地址空间物理地址空间例如：LOAD1，2500这条指令是把相对地址为2500的存储单元的内容365装入1号累加器。而这时内容为365的存储单元的实际物理地址为12500（起始地址10000+相对地址2500），所以LOAD1，2500这条指令中的直接地址码要作相应的修改，即改为LOAD1，12500。

(2)动态映射：指在程序执行过程中进行地址重定位，即在每次访问内存单元前才进行地址变换。动态重定位可使程序不加任何修改就装入内存，但是它需要硬件—重定位寄存器的支持。对每一个有效地址都要加上重定位寄存器中的内容，以形成绝对地址。优点:程序在内存中的搬移不会对程序的正确执行造成影响，使内存得以被充分利用。缺点:需要附加的硬件支持，实现存储管理的软件算法比较复杂。03456......LOAD1200......0100200300.........LOAD12003456逻辑地址空间110012001300物理地址空间200有效地址+1000BR10004.2.2程序的链接一种事先链接方式，即在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装入模块(执行文件)，以后不再拆开。实现静态链接应解决:1）相对地址的修改2）变换外部调用符号存在问题：1）不便于对目标模块的修改和更新。2）无法实现对目标模块的共享。模块ACALLB;RETURN;模块BCALLC;RETURN;模块CRETURN;0L-10M-10N-1目标模块0L-1LL+M-1L+ML+M+N-1模块CReturn；模块BJSR“L+M”Return；模块AJSR“L”Return；装入模块1.静态链接方式指将一组目标模块在装入内存时，边装入边链接的方式。具有便于修改和更新、便于实现对目标模块的共享。存在问题：

由于程序运行所有可能用的目标模块在装入时均全部链接在一起，所以将会把一些不会运行的目标模块也链接进去。如程序中的错误处理模块。2.装入时动态链接方式在程序运行中需要某些目标模块时，才对它们进行链接的方式。具有高效且节省内存空间的优点。3.运行时动态链接方式单一用户(连续)分配是一种简单的存储分配方案，主要用于单用户单任务操作系统。它的实现方案如下：(1)内存分配：整个内存划分为系统区和用户区。系统区是操作系统专用区，不允许用户程序直接访问，一道用户程序独占用户区.

4.3.1单一用户存储管理方案注意:我们所涉及的内存分配与回收一般都指用户区的分配与回收。进程1OS系统区用户区4.3连续分配方式地址错界限寄存器重定位寄存器(基址)CPU<内存逻辑地址YN物理地址+(3)内存保护：通过基址寄存器保证用户程序不会从系统区开始；另外系统需要一个界限寄存器，里边存储程序逻辑地址范围，若需要进行映射的逻辑地址超过了界限寄存器中的值，则产生一个越界中断信号。(2)地址映射：物理地址=用户区基地址+逻辑地址。单一连续分配方案的优点是方法简单，易于实现；缺点是它仅适用于单道程序，因而不能使处理机和内存得到充分利用。例：一个容量为256KB的内存，操作系统占用32KB，剩下224KB全部分配给用户作业，如果一个作业仅需64KB，那么就有160KB的存储空间被浪费。操作系统作业0KB32KB96KB256KB-1分配给用户的空间4.3.2固定分区分配作业装入之前，内存就被划分成若干个分区。划分工作可以由系统管理员完成或由操作系统实现。一旦划分完成，在系统运行期间不再重新划分，即分区的个数不可变，分区的大小不可变，且每个分区装一个且只能装一个作业。可将内存的用户区域划分成大小相等或不等的分区。分区大小相等：只适合于多个相同程序的并发执行（处理多个类型相同的对象）。分区大小不等：多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。系统有一张分区说明表，每个表目说明一个分区的大小、起始地址和是否已分配的使用标志。

固定分区示例例：在某系统中，采用固定分区分配管理方式，内存分区（单位字节）情况如图所示，现有大小为1K、9K、33K、121K的多个作业要求进入内存，试画出它们进入内存后的空间分配情况，并说明主存浪费多大？10k20k28k60k180k511k234内存分区图OS区号大小起址状态18k20k未分配232k28k未分配3120k60k未分配4331k180k未分配分区说明表区号大小起址状态18k20k已分配232k28k已分配3120k60k已分配4331k180k已分配（2）分区说明表(3)主存浪费空间=(8-1)+(32-9)+(120-33)+(331-121)=7+23+87+210=327(k)解：根据分区说明表，将4个分区依次分配给4个作业，同时修改分区说明表，其内存分配和分区说明表如下所示：0k20k28k60k180k511k23(1)内存分配图1K9K33K121K4.3.3动态（可变）分区分配作业装入内存时，从可用的内存中划出一块连续的区域分配给它，且分区大小正好等于该作业的大小。可变式分区中分区的大小和分区的个数都是可变的，而且是根据作业的大小和多少动态地划分。在分配时，首先找到一个足够大的空闲分区，即这个空闲区的大小比作业要求的要大，系统则将这个空闲分区分成两部分：一部分成为已分配的分区，剩余的部分仍作为空闲区。在回收撤除作业所占领的分区时，要检查回收的分区是否与前后空闲的分区相领接，若是，则加以合并，使之成为一个连续的大空间。常用的数据结构有内存分配表（由已分配区表和空闲区表组成）和空闲分区链两种。0K15K38K48K68K80K110K120K空闲区表已分配区表始址长度标志15K23K未分配48K20K未分配80K30K未分配空空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ4空空J1J2J3J40K15K38K48K68K80K110K120K空闲区表已分配区表始址长度标志15K23K未分配48K20K未分配98K12K未分配空空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ480K5KJ585K13KJ685K98KJ1J2J3J4J5J6可变分区示例2.分区分配算法为了将一个作业装入内存，应按照一定的分配算法从空闲分区表（链）中选出一个满足作业需求的分区分配给作业，如果这个空闲分区的容量比作业申请的空间要大，则将该分区一分为二，一部分分配给作业，剩下的部分仍然留在空闲分区表（链）中，同时修改空闲分区表（链）中相应的信息。目前常用分配算法有：首次适应算法循环首次适应算法最佳适应算法最坏适应算法快速适应法首次适应算法（最先适应算法）算法

空闲分区（链）按地址递增的次序排列。在进行内存分配时,从空闲分区表/链首开始顺序查找,直到找到第一个满足其大小要求的空闲分区为止。然后再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲分区表（链）中。区号大小起址132k20k28k52k3120k60k4331k180k空闲分区表解：按首次适应算法，

申请作业100k，分配3号分区，剩下分区为20k，起始地址160K；

申请作业30k，分配1号分区，剩下分区为2k，起始地址50K；

申请作业7k，分配2号分区，剩下分区为1k，起始地址59K；其内存分配图及分配后空闲分区表如下：例：系统中的空闲分区表如下，现有三个作业分配申请内存空间100K、30K及7K。给出按首次适应算法的内存分配情况及分配后空闲分区表。区号大小起址12k50k21k59k320k160k4331k180k(2)该算法分配后的空闲分区表0k20k50k52k59k60k160k180k511k(1)内存分配图首次适应算法的特点

优先利用内存低地址部分的空闲分区,从而保留了高地址部分的大空闲区。但由于低地址部分不断被划分,致使低地址端留下许多难以利用的很小的空闲分区(碎片或零头),而每次查找又都是从低地址部分开始,这无疑增加了查找可用空闲分区的开销。循环首次适应算法算法要求

又称为下次适应算法，由首次适应算法演变而来。在为作业分配内存空间时,不再每次从空闲分区表/链首开始查找,而是从上次找到的空闲分区的下一个空闲分区开始查找,直到找到第一个能满足其大小要求的空闲分区为止。然后，再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲分区表/链中。区号大小起址132k20k28k52k3120k60k4331k180k空闲分区表解：按循环首次适应算法，申请作业100k，分配3号分区，剩下分区为20k,起始地址160K；

申请作业30k，分配4号分区，剩下分区为301k，起始地址210K；申请作业7k，分配1号分区，剩下分区为25k，起始地址27K；其内存分配图及分配后空闲分区表如下:例：系统中的空闲分区表如下，现有三个作业分配申请内存空间100K、30K及7K。给出按循环首次适应算法的内存分配情况及分配后空闲分区表。区号大小起址12k27k21k52k320k160k4131k210k(2)该算法分配后的空闲分区表算法特点

使存储空间的利用更加均衡，不致使小的空闲区集中在存储区的一端，但这会导致缺乏大的空闲分区。

0k20k27k52k60k160k180k210k511k(1)内存分配图最佳适应算法算法要求：

总是把满足要求的、又是最小的空闲分区分给作业。为了加速寻找，空闲分区表/链按容量大小递增的次序排列。在进行内存分配时，从空闲分区表/链的首开始顺序查找，直到找到第一个满足其大小要求的空闲分区为止。按这种方式为作业分配内存，就能把既满足作业要求又与作业大小最接近的空闲分区分配给作业。如果该空闲分区大于作业的大小，则与首次适应算法相同，将剩余空闲分区仍留在空闲分区表/链中。例：系统中的空闲分区表如下，现有三个作业分配申请内存空间100K、30K及7K。给出按最佳适应算法的内存分配情况及分配后空闲分区表。区号大小起址18k52k232k20k3120k60k4331k180k分配前的空闲分区表内存分区

0k20k52k60k180k511k2134解：按最佳适应算法，分配前的空闲分区表如上表。

申请作业100k，分配3号分区，剩下分区为20k,起始地址160K；

申请作业30k，分配2号分区，剩下分区为2k，起始地址50K；

申请作业7k，分配1号分区，剩下分区为1k，起始地址59K；其内存分配图及分配后空闲分区表如下：区号大小起址18k52k320k160k232k20k4331k180k作业100K分配后的空闲分区表区号大小起址22k50k18k52k320k160k4331k180k作业30K分配后的空闲分区表区号大小起址11k59k22k50k320k160k4331k180k作业7K分配后的空闲分区表(2)该算法分配后的空闲分区表0k20k52k60k180k511k(1)内存分配图50K59K160K180K区号大小起址11k59k22k50k320k160k4331k180k算法特点

若存在与作业大小一致的空闲分区,则它必然被选中，若不存在与作业大小一致的空闲分区，则只划分比作业稍大的空闲分区，,从而保留了大的空闲分区,但空闲区一般不可能正好和它申请的内存空间大小一样,因而将其分割成两部分时,往往使剩下的空闲区非常小,从而在存储器中留下许多难以利用的小空闲区（碎片或零头）。最坏适应算法算法要求

总是挑选一个最大的空闲区分割给作业使用，空闲分区表/链按容量大小递减的次序排列。在进行内存分配时，从空闲分区表/链的首开始顺序查找，直到找到第一个比之大的空闲分区为止。剩下的空闲仍留在空闲分区表/链中。区号大小起址1331k180k2120k60k332k20k48k52k空闲分区表例：系统中的空闲分区表如下，现有三个作业分配申请内存空间100K、30K及7K。给出按最坏适应算法的内存分配情况及分配后空闲分区表。区号大小起址1231k280k2120k60k332k20k48k52k作业100K分配后的空闲分区表区号大小起址1201k310k2120k60k332k20k48k52k作业30K分配后的空闲分区表区号大小起址1194k317k2120k60k332k20k48k52k作业7K分配后的空闲分区表解：按最坏适应算法，分配前的空闲分区表如上表。

申请作业100k，分配1号分区，剩下分区为231k,起始地址280K；

申请作业30k，分配1号分区，剩下分区为201k，起始地址310K；

申请作业7k，分配1号分区，剩下分区为194k，起始地址317K；其内存分配图及分配后空闲分区表如下：区号大小起址1194k317k2120k60k332k20k48k52k(2)该算法分配后的空闲分区表30k20k52k60k180k511k(1)内存分配图20K52K60K280K310K317K算法特点总是挑选满足作业要求的最大的分区分配给作业。这样使分给作业后剩下的空闲分区也较大，可装下其它作业。但由于最大的空闲分区总是因首先分配而划分，当有大作业到来时，其存储空间的申请往往会得不到满足。快速适应算法（分类搜索法）算法要求

将空闲分区根据其容量大小进行分类，每一类相同容量的所有空闲分区，单独设立一个空闲分区链表，同时在内存中设立一张管理索引表，每一表项对应了一种空闲分区类型，并记录头指针。进程根据自己的长度，寻找能容纳它的最小空闲区链表，取下第一块进行分配即可。3.分区分配操作_分配内存和回收内存（1）分配内存系统利用某种分配算法，从空闲分区表/链中找到所需大小的分区。分区的切割：设请求的分区大小为u.size，空闲分区的大小为m.size,若m.size-u.sizesize(size是事先规定的不再切割的剩余分区的大小)，说明多余部分大小，可不再切割，将整个分区分配给请求者；否则，从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区表/链中，然后，将分配区的首址返回给调用者。

分配流程图如下：从头开始查表从该分区中划出u.size大小的分区检索完否？返回m.size>u.sizem.size-u.sizesize将该分区分配给请求者，修改有关数据结构返回将该分区从分区表/链中移出继续检索下一个表项YYYNNN内存分配流程图（2）回收内存当作业执行结束时，应回收已使用完毕的分区。系统根据回收分区的大小及首地址，在空闲分区表中检查是否有邻接的空闲分区，如有，则合成为一个大的空闲分区，然后修改有关的分区状态信息。回收分区与已有空闲分区的相邻情况有以下四种：1）回收分区上邻接一个空闲分区,合并后首地址为空闲分区的首地址,大小为二者之和。2）回收分区下邻接一个空闲分区,合并后首地址为回收分区的首地址,大小为二者之和。3）回收分区上下邻接空闲分区,合并后首地址为上空闲分区的首地址,大小为三者之和。4）回收分区不邻接空闲分区，这时在空闲分区表中新建一表项，并填写分区大小等信息。4.3.6可重定位分区分配1.动态重定位的引入

在分区存储管理方式中，必须把作业装入到一片连续的内存空间。如果系统中有若干个小的分区，其总容量大于要装入的作业，但由于它们不相邻接，也将致使作业不能装入内存。例：如图所示系统中有四个小空闲分区，不相邻，但总容量为90KB，如果现有一作业要求分配40KB的内存空间，由于系统中所有空闲分区的容量均小于40KB，故此作业无法装入内存。这种内存中无法被利用的存储空间称为“零头”或“碎片”。根据碎片出现的情况分为以下两种：操作系统作业A20KB作业B30KB作业C15KB作业D25KB系统中的碎片os用户程序p4p1p20k20k56k65k125k135k内部碎片内部碎片内部碎片25KB作业D15KB作业C30KB作业B20KB作业A操作系统外部碎片外部碎片外部碎片外部碎片内部碎片外部碎片内部碎片：指分配给作业的存储空间中未被利用的部分。如固定分区中存在的碎片。外部碎片：指系统中无法利用的小的空闲分区。如动态分区中存在的碎片。碎片问题的解决方法拼接或紧凑或紧缩技术将内存中所有作业移到内存一端（作业在内存中的位置发生了变化，这就必须对其地址加以修改或变换即称为重定位），使本来分散的多个小空闲分区连成一个大的空闲区。如图所示。这种通过移动作业从把多个分散的小分区拼接成一个大分区的方法称为拼接或紧凑或紧缩。拼接时机：分区回收时；当找不到足够大的空闲分区且总空闲分区容量可以满足作业要求时。操作系统作业A作业B作业C作业D20KB30KB90KB15KB25KB2.动态重定位的实现动态重定位可使程序不加任何修改就装入内存，但是它需要硬件—重定位寄存器的支持。对每一个有效地址都要加上重定位寄存器中的内容，以形成绝对地址。03456......LOAD1200......0100200300.........LOAD12003456逻辑地址空间110012001300物理地址空间200有效地址+1000BR1000动态重定位分区分配算法流程图有大于x的空闲分区吗？返回分区号空闲分区总和大于x吗？拼接并修改相应数据结构返回修改有关数据结构按动态分区分配方式进行分配YYNN无法分配，返回请求分配一个大小为x的分区3.动态重定位分区分配算法

在动态分区分配算法中增加拼接功能，在找不到足够大的空闲分区来满足作业要求，而系统中总空闲分区容量可以满足作业要求时，进行拼接。可重定位分区分配方式主要特点

可以充分利用存储区中的“零头/碎片”，提高主存的利用率。但若“零头/碎片”过多，则拼接频率过高会使系统开销加大。4.3.7覆盖技术与交换技术1.覆盖技术引入：其目标是在较小的可用内存中运行较大的程序。常用于多道程序系统，与分区存储管理配合使用。原理：一个程序的几个代码段或数据段，按照时间先后来占用公共的内存空间。将程序的必要部分（常用功能）的代码和数据常驻内存；可选部分（不常用功能）在其他程序模块中实现，平时存放在外存中（覆盖文件），在需要用到时才装入到内存；不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。(即不同时用的模块可共用一个分区)缺点：编程时必须划分程序模块和确定程序模块之间的覆盖关系，增加编程复杂度。从外存装入覆盖文件，以时间延长来换取空间节省。A20KD20KE40KC30KB50KF30K作业X的调用结构作业X的常驻区A（20K）覆盖区0（50K）覆盖区1（40K）BCDEF注：另一种覆盖方法：(100K)A(20K)占一个分区：20K；B(50K)、D(20K)和E(40K)共用一个分区：50K；F(30K)和C(30K)共用一个分区：30K；Total:190KTotal:110K2.交换技术引入：多个程序并发执行，可以将暂时不能执行的程序送到外存中，从而获得空闲内存空间来装入新程序，或读入保存在外存中而目前到达就绪状态的进程。交换单位为整个进程的地址空间。常用于多道程序系统或小型分时系统中，与分区存储管理配合使用。又称作"对换"或"滚进/滚出(roll-in/roll-out)"；程序暂时不能执行的可能原因：处于阻塞状态，低优先级（确保高优先级程序执行）；原理：暂停执行内存中的进程，将整个进程的地址空间保存到外存的交换区中（换出swapout），而将外存中由阻塞变为就绪的进程的地址空间读入到内存中，并将该进程送到就绪队列（换入swapin）。返回优点：增加并发运行的程序数目，并且给用户提供适当的响应时间；编写程序时不影响程序结构缺点：对换入和换出的控制增加处理机开销；程序整个地址空间都进行传送，没有考虑执行过程中地址访问的统计特性。考虑的问题：程序换入时的重定位；减少交换中传送的信息量，特别是对大程序；对外存交换区空间的管理：如动态分区方法；4.4基本分页存储管理方式我们把逻辑地址空间划分为一些相等的片，这些片称为页或页面。物理地址空间也被划分为同样大小的片，称为块。这样用户程序进入内存时，就可以一页对应存入到一个块中。对整个程序来说，只有可能在最后一块存在碎片（称为页内碎片），而且碎片大小不会超过一块，所以内存利用率可以大大提高。用户程序的逻辑地址:4.4.1页面与页表页号页内地址页面(或块)的大小由系统硬件地址结构规定，通常是2的幂，例如512B，1KB、2KB等。这样的规定可以使地址映射容易实现。页面不能过大，也不能过小。过小会造成页面过多，增加了系统开销；过大又会造成页内碎片太大，内存利用率不高。早期的页面大小一般都在512B～4KB，随着计算机性能的提高，现在一般在2KB～8KB，甚至有的系统支持多种页面大小。例：对于一个32位的地址结构，如果页面大小为4KB，则页内地址由0～11这12位表示，剩余12～31在表示页号（页内地址）例：在页面大小为4KB的系统中，若逻辑地址为28024，则可求得页号为6，页内偏移量为3448。而计算机内部如何得到页号和页内地址呢？28024的二进制用32位表示为：(00000000000000000110110101111000)2，因为页面大小为4KB，则取低12位为页内地址，剩余高位是页号。把这两部分换算为十进制，我们可以验算出通过上述公式计算的结果的正确性。000000000000000001101101011110002802463448系统为每个进程建立一个页表，记录了进程每个页号及其对应的存储块号。整个系统一张存储分块表，记录每个存储块及其状态（已分配或空闲）。当有一个进程进入系统时，为页表分配一个存储区，然后搜索存储分块表，查看有哪些存储块是空闲的，如有空闲的存储块，则将存储块号填入页表。当该进程所需的块数都分配完后，系统便可按照页表的内容对该进程进行处理。当某个进程因为结束或者其它一些原因退出系统，则归还原来所占用的物理块。首先修改存储分块表，将归还的物理块块号在表中的状态栏改为空闲标志，然后释放该进程页表所占用的空间。管理上的考虑页表、存储分块表及其关系页号012块号103920号页表1号页表页号01块号953…块号0…状态0…31……91101……存储分块表由于页和块大小是一致的，每页的页内地址与物理块的块内单元地址也完全一致，所以在逻辑地址到物理地址的映射中，主要从一个页找到对应的内存块，而这种页与块的对应关系是页表记录的。每个进程调度时，从该进程PCB中取得页表始址和页表长度（页表长度指页表的项数），装入到系统中设置的页表寄存器内。4.4.2地址变换机构1．动态地址映射机构分页式地址变换过程例：页大小为1024B，给定逻辑地址3795，即得出页号为3，页内地址为723。页表始址页表长度＋页表寄存器＞页号3页内地址723越界中断①①②②11×1024＋723页号块号01615425311……RR＋iR＋3i……365……物理地址11987④11987内存内存中的页表逻辑地址3795③③①页号3与页表寄存器中的页表长度比较判断是否越界，如果越界，则转错误中断处理，否则转②；②页表中该项在内存中的对应地址=页表始地址R+页号3×页表项长度i，访问该地址R+3i，得到物理块号11；③11(页号)×1024(页大小)+723(页内地址)=11987(物理地址)；④访问内存11987单元，得到需要的数据365。页表存放在内存中，每条指令都必须两次访问内存储器，增加了指令执行的机器时间，影响了计算机的速度。一次是访问页表，由页号找到对应的物理块号；另一次是在物理地址中实际存取所要的数据或指令。为了加快查表速度，在地址映射机构中加入一组高速寄存器(8个或16个)，构成了一个容量较小的存储器，称之为联想存储器（也称快表）。在联想存储器中，存放正在运行进程的当前最常用的页号和相应块号，这个联想存储器具有并行查询能力，使地址转换时间大大下降。2.快表的引入(联想存储器)引入快表的地址映射页表始址页表长度＋页表寄存器＞页号页内地址越界中断①①⑥③b…365……物理地址④内存逻辑地址页号块号b…内存⑥页号块号b…⑦②⑦快表⑤由于对程序和数据的访问往往带有局限性，所以快表的命中率可以达到90%左右。例:假设检索联想存储器的时间为20ns，访问内存的时间为100ns，访问联想存储器的的命中率为85%，则CPU存取一个数据的平均时间为T=0.85*120+0.15*200=132ns，如果不引入联想存储器，访问2次主存，将达200ns。问题

若逻辑地址空间很大，则划分的页就很多，页表就很大，其占用的存储空间（要求连续）就大，实现较难。解决问题的方法

1、只将当前需用的部分页表项调入内存，其余的需用时再调入。

2、多级页表二级页表

(1)将页表再进行分页，并离散地将各个页表页面存放在不同的物理块中，同时也再建立一张页表（外层页表）用以记录页表页面对应的物理块号。

4.4.3多级页表两级页表结构174210781011…6411151141468……012n012102301210230121023第0页页表第1页页表第n页页表0121141151468内存空间外部页表(2)逻辑地址：(3)地址转换p1p2d页表页面号页号页内偏移地址dp2p1页表页面号页号页内地址外部页表寄存器…

…

外部页表++页表bd物理地址多级页表

将外层页表再进行分页，也将各外层页表页面离散地存放在不同的物理块中，再利用第2级的外层页表来记录它们之间的对应的关系。逻辑地址：p1p2d外层页表页面号页表页面号页号页内偏移地址p3便于多道程序设计，提高了内存的利用率，而不必像动态分区分配那样执行紧凑操作。分页存储管理的优缺点优点：采用动态地址映射会增加计算机成本和降低处理机的速度。各种表格要占用一定容量的内存空间，而且还要花费一部分处理机时间来建立和管理这些表格。虽然消除了大量碎片，但每个作业的最后一页一般都有不能充分利用的空白区存储扩充问题仍未得到解决。当没有足够空间能装下整个作业地址空间时，该作业还是无法运行。缺点：1．把作业地址空间中使用的逻辑地址变成内存中物理地址称为（）。A.加载B.重定位C.物理化D.逻辑化3．在内存分配的“最佳适应法”中，空闲块是按（）。A.始地址从小到大排序B.始地址从大到小排序C.块的大小从小到大排序D.块的大小从大到小排序4．分区管理和分页管理的主要区别是（）。A.分区管理中的块比分页管理中的页要小B.分页管理有地址映射而分区管理没有C.分页管理有存储保护而分区管理没有D.分区管理要求一道程序存放在连续的空间内而分页管理没有这种要求。2．在可变分区存储管理中的紧凑技术可以()。A.集中空闲区B.增加主存容量C.缩短访问时间D.加速地址转换BACD5．设内存的分配情况如下图所示。若要申请一块40K字节的内存空间，若采用最佳适应算法，则所得到的分区首址为（）。A.100KB.190KC.330KD.410K占用

占用

占用

占用

┇000K100K180K190K280K330K390K410K512K-1C一个用户作业的程序按其逻辑结构可划分为若干段，例如主程序段、子程序段、数据段、堆栈段等。这些段中的每一段在逻辑上都是完整的，因此每一段都是一组逻辑信息，有自己的名字，且都有一段连续的地址空间。在分段式存储管理中，段名用段号代替，段地址从0开始编址，因为各段的逻辑信息内容不同，所以段长度不同。这样用段号和段内地址构成用户程序的逻辑地址。当一个用户程序装入内存时，系统为每个段分配一个连续的内存区域，而各个段之间可以离散存放。4.5.2分段系统的基本原理段号段内地址4.5基本分段存储管理方式地址映射机构段表分段式地址变换过程段表始址段表长度段表寄存器＞段号3段内地址723越界中断①①逻辑地址＋②②段号段长2000段基址16K400154K15025K90038K……8K＋723…365………③④8K8915物理地址内存中的段表内存3号段③例：给定逻辑地址中段号为3，段内地址为723分页和分段的主要区别分页是出于系统管理的需要，分段是出于用户应用的需要。一条指令或一个操作数可能会跨越两个页的分界处，而不会跨越两个段的分界处。页大小是系统固定的，而段大小则通常不固定。逻辑地址表示：分页是一维的，各个模块在链接时必须组织成同一个地址空间；分段是二维的，各个模块在链接时可以每个段组织成一个地址空间。通常段比页大，因而段表比页表短，可以缩短查找时间，提高访问速度。返回4.5.3信息共享分页系统中共享editor的示意图例:一个多用户系统可同时容纳40个用户，都执行一个文本编辑程序（160KB代码和40KB数据区），代码是可重入的假定页面大小为4KB。分段系统中共享editor的示意图editor进程1data1进程2editordata2段表段长基址16080402401608040380editordata1…data280240280380420方便了用户编程。多个逻辑段形成作业这种组织方式，使用户可以清晰地设计和了解程序的结构。便于实现程序和数据的共享与保护。程序的动态链接实现方便。通常一个源程序经过编译后所形成的若干个目标程序，还需再经过链接，形成可执行代码后才能运行，这种在装入时进行的链接称为静态链接。动态链接是指在作业运行之前，并不把几个目标程序段都链接起来，而是先将主程序对应的目标程序装入内存并启动运行，当运行过程中又需要调用某段时，再将该段（目标程序）调入内存并链接起来。所以，动态链接是以段为基础的。应用中会发生数据动态增长的情况，而且这种增长是无法预知的，采用分段管理可以很好地解决这个问题。分段存储管理的优缺点优点：缺点：有碎片问题。4.5.4段页式存储管理方式在段页式存储管理系统中，处理机给出的有效地址被划分为三部分：段号、段内页号和页内地址。段页式存储管理中，记录逻辑地址到物理地址的映射表包括段表和页表。它们的结构和映射功能如图所示。段号S段内页号P页内位移量W

段号页表长度页表始址03122段表页号0块号120段的页表页号0块号11段的页表内存系统区例:给定某个逻辑地址中，段号为2，段内地址为6015，若系统规定块大小为1KB，则采用段页式管理，该逻辑地址表示：段号为2，段内页号为5，页内地址为895。其地址变换过程如图所示。段表始址段表长度段表寄存器＞越界中断①①＋②②段号页表长度0页表始址12③内存＋16页号块号…页表段号2页号5页内地址895…③16895……365…物理地址17279内存内存逻辑地址④⑤①段号2与段表寄存器中存放的段表长度比较以判断是否越界，如果越界，则转错误中断处理，否则转②；②段表始地址+段号×段表项长度，就得到属于该段的页表始地址和页表长度；③页号与页表长度进行越界检查，页表始地址+页号×页表项长度，就得到内存页表中记录的该页对应的物理块号16；④16(块号)×1024(块大小)+895(页内地址)=17279(一个物理地址号)；⑤访问内存17279单元，得到需要的数据365。采用段页式存储管理，从逻辑地址到物理地址的变换过程中要三次访问内存，一次是访问段表，一次是访问页表，再一次是访问内存物理地址。这就是说，当访问内存中的一条指令或数据时，至少要访问内存三次，这将使程序的执行速度大大降低。为此，可以像在分页存储管理中那样，使用联想存储器的方法来加快查表速度。4.6虚拟存储器的基本概念常规存储管理方式的共同点：要求一个作业全部装入内存后方能运行。问题：

(1)有的作业很大,所需内存空间大于内存总容量,使作业无法运行。

(2)有大量作业要求运行，但内存容量不足以容纳下所有作业，只能让一部分先运行，其它在外存等待。解决方法

（1）增加内存容量。（2）从逻辑上扩充内存容量

----覆盖

----对换

----虚拟存储器4.6.1虚拟存储器的引入常规存储器管理方式的特征（1）一次性：作业在运行前需一次性地全部装入内存。将导致上述两问题。（2）驻留性：作业装入内存后，便一直驻留内存，直至作业运行结束。局部性原理

指程序在执行时呈现出局部性规律，即在一较短时间内，程序的执行仅限于某个部分，相应地，它所访问的存储空间也局限于某个区域。局部性又表现为时间局部性(由于大量的循环操作，某指令或数据被访问后，则不久可能会被再次访问)和空间局部性（如顺序执行，指程序在一段时间内访问的地址，可能集中在一定的范围之内）。虚拟存储器的概念基于局部性原理，程序在运行之前，没有必要全部装入内存，仅须将当前要运行的页（段）装入内存即可。运行时，如访问的页（段）在内存中，则继续执行，如访问的页未在内存中（缺页或缺段），则利用OS的请求调页（段）功能，将该页（段）调入内存。如内存已满，则利用OS的页（段）置换功能，按某种置换算法将内存中的某页（段）调至外存，从而调入需访问的页。

虚拟存储器是指仅把作业的一部分装入内存便可运行作业的存储管理系统，它具有请求页调入功能和页置换功能，能从逻辑上对内存容量进行扩充，其逻辑容量由外存容量和内存容量之和决定，其运行速度接近于内存，成本接近于外存。4.6.2虚拟存储器的实现方法1、分页请求系统在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页式虚拟存储器系统。它允许只装入若干页的用户程序和数据，便可启动运行，以后在硬件支持下通过调页功能和置换页功能，陆续将要运行的页面调入内存，同时把暂不运行的页面换到外存上，置换时以页面为单位。

系统须设置相应的硬件支持和软件：

（1）硬件支持：请求分页的页表机制、缺页中断机构和地址变换机构。（2）软件：请求调页功能和页置换功能的软件。2、分段请求系统在分段系统的基础上，增加了请求调段功能及分段置换功能，所形成的段式虚拟存储器系统。它允许只装入若干段的用户程序和数据，便可启动运行，以后在硬件支持下通过请求调段功能和分段置换功能，陆续将要运行的段调入内存，同时把暂不运行的段换到外存上，置换时以段为单位。系统须设置相应的硬件支持和软件：

（1）硬件支持：请求分段的段表机制、缺段中断机构和地址变换机构

（2）软件：请求调段功能和段置换功能的软件4.6.3虚拟存储器的特征1、多次性多次是虚拟存储器最重要的特征。指一个作业被分成多次调入内存运行。2、对换性对换性指允许在作业运行过程中进行换进、换出。换进、换出可提高内存利用率。3、虚拟性虚拟性是指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。虚拟性是虚拟存储器所表现出来的最重要的特征，也是实现虚拟存储器最重要的目标。注：虚拟性以多次性和对换性为基础，而多次性和对换性又是离散分配为基础。4.7请求分页存储管理方式在简单页式存储管理的基础上，增加请求调页和页面置换功能。1.对页表的修改状态位（中断位）：表示该页是在内存还是在外存访问位：根据访问位来决定淘汰哪页（由不同的算法决定）修改位：表示该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本，因此，若未被修改，在置换该页时就不需将该页写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本页号块号状态位访问字段修改位外存地址在请求分页系统中，每当所要访问的页面不在内存时，便要产生一缺页中断，请求OS将所缺页调入内存。2．缺页中断机构与一般中断的主要区别在于：缺页中断在指令执行期间产生和处理中断信号，而一般中断在一条指令执行完后检查和处理中断信号。缺页中断返回到该指令的开始重新执行该指令，而一般中断返回到该指令的下一条指令执行。一条指令在执行期间，可能产生多次缺页中断。3.地址变换机构开始页号>页表长度？CPU检索快表NNY页表项在快表中？访问页表页在内存？修改访问位和修改位修改快表形成物理地址地址变换结束越界中断程序请求访问一页YN缺页中断处理Y保留CPU现场内存满吗？将一页从外存换入内存OS命令CPU从外存读缺页启动I/O硬件Y从外存中找到缺页选择一页换出该页被修改否？将该页写回外存修改页表NYN4.7.2内存分配策略和分配算法在请求分页系统中，为进程分配内存时，将涉及以下三个问题：1、最小物理块数的确定最小物理块数指能保证进程正常运行所需的最小的物理块数，与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。2、物理块的分配策略

（1）固定分配局部置换：为每个进程分配固定数目n的物理块，在整个运行中都不改变。如出现缺页，则从中置换一页。

（2）可变分配全局置换：分配固定数目的物理块，但OS自留一空闲块队列，若发现缺页，则从空闲块队列中分配一空闲块与该进程，并调入缺页于其中。当空闲块队列用完时，OS才从内存中任选择一页置换。

（3）可变分配局部置换：分配一定数目的物理块，若发现缺页，则从该进程的页面中置换一页，根据该进程缺页率高低，则可增加或减少物理块。

3、物理块分配算法在采用固定分配策略时，将系统中可供分配的所有物理块分配给各个进程，可采用以下几种算法：

（1）平均分配算法：平均分配给各个进程。

（2）按比例分配算法：根据进程的大小按比例分配给各个进程。

（3）考虑优先权的分配算法：将系统提供的物理块一部分根据进程大小先按比例分配给各个进程，另一部分再根据各进程的优先权适当增加物理块数。4.7.3页面调入策略

调入策略决定什么时候将一个页面由外存调入内存，从何处将页面调入内存。何时调入页面

预调页策略：将那些预计在不久便被访问的页预先调入内存。这种调入策略提高了调页的效率，减少了I/O次数。但由于这是一种基于局部性原理的预测，若预调入的页面在以后很少被访问，则造成浪费，故这种方式常用于程序的首次调入。请求调页策略：当进程运行中访问的页出现缺页时，则发出缺页中断，提出请求调页，由OS将所需页调入内存。这种策略实现简单，应用于目前的虚拟存储器中，但易产生较多的缺页中断，且每次调一页，系统开销较大，容易产生抖动现象。从何处调入页面

在请求分页系统中，通常将外存分成了文件区和对换区，文件区按离散分配方式存放文件，对换区按连续分配方式存放对换页。

对换区：系统有足够的对换区空间，运行前可将与进程相关的文件从文件区复制至对换区，以后缺页时，全部从对换区调页。文件区：系统没有足够的对换区空间，凡是不会被修改的文件，每次都直接从文件区调页。文件区、对换区：系统没有足够的对换区空间，对可能会修改的文件第一次调页直接从文件区，换出时换至对换区，以后从对换区调页。UNIX方式：凡未运行过的页面均从文件区调页，运行过的页面和换出的页面均从对换区调页。4.8页面置换算法发生了6次面置换，9次缺页中断。4.8.1最佳（OPT:Optimal）置换算法它是一种理想化的算法，性能最好，但在实际上难于实现。即选择那些永不使用的，或者是在最长时间内不再被访问的页面置换出去。但是要确定哪一个页面是未来最长时间内不再被访问的，目前来说是很难估计的，所以该算法通常用来评价其它算法。例：假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：7，0，l，2，0，3，0，4，2，3，0，3，2，l，2，0，l，7，0，1。页面引用70120304230321201701777222222222222227770000004440000000000物理块1111333333331111111缺页xxxxxxxxx物理块2物理块3(2)先进先出（FIFO）置换算法

算法的基本思想是，总是先淘汰那些驻留在内存时间最长的页面，即先进入内存的页面先被淘汰。这种算法实现起来比较简单，性能最差。会出现BeLady异常现象。BeLady异常：一般来说，如果分给进程的页框数增加，则缺页的频率应该减少。但这个结论并不普遍成立，对于某些页面访问序列，FIFO有随着分给的页框数增加，缺页频率也增加的异常现象。利用FIFO算法对上例进行页面置换的结果如下:发生了12次面置换，15次缺页中断。页面引用70120304230321201701701223042300012227017011230423330111270物理块1700123042223000127缺页xxxxxxxxxxxxx物理块2物理块3xxBeLady异常现象9104.8.2最近最久未使用置换算法

（LRU：LeastRecentlyUsed）该算法是选择最近最久未使用的页面予以淘汰，系统在每个页面设置一个“计时”标记，用以记录这个页面自上次被访问以来所经历的时间T，当要淘汰一个页面时，选择T最大的页面。但在实现时需要硬件的支持。利用LRU算法对上例进行页面置换的结果如下:发生了9次面置换，12次缺页中断。页面引用70120304230321201701701203042303212017017012030423032120170物理块1701223042203312017缺页xxxxxxxxx物理块2物理块3xxxＮＲＵ是一种最为流行的、低开销的ＬＲＵ近似算法。它所依据的理由是：在最近一段时间内未使用过的页在最近的将来不大可能被使用。在具体实现中，系统为每个页增加两个硬件位(用软件模拟)：（4）最近未使用算法ＮＲＵ（NotRecentlyUsed）设置修改位的意义在于，如果被淘汰的页没被修改过，由于每页在外存都有副本，因此不必把它再写回外存，否则必须写回外存。显然最好的选择是淘汰没修改过的页，这样可以减少系统开销。初始时，所有实页的引用位和修改位都置为０，当访问某页时，该页的引用位置为１，一旦修改了某页，便置其修改位为１。当要淘汰时按下列页类的次序选择:首先选择１类实页进行淘汰，然后次之。为了避免到某一时刻大多数甚至所有实页的引用位都为１，从而无法区别哪一页最应该被淘汰，系统需要周期性地（设周期为ｔ）将所有引用位都置０。１类：未引用过，未修改过２类：未引用过，修改过３类：引用过，未修改过４类：引用过，修改过(1)分配给进程的物理页面数(2)页面本身的大小(3)程序的编制方法5.影响缺页次数的因素(4)页面淘汰算法例：一程序把128*128的数组置初值0，每个元素为一个字。假定每页128个字，数组每一行元素存放在一页中，只有一块内存，初始时第一页在内存。程序编制方法1：Forj:=1to128Fori:=1to128A[i,j]:=0;128*128-1次缺页中断程序编制方法2：Fori:=1to128Forj:=1to128A[i,j]:=0;128-1次缺页中断5.7.4性能问题1.颠簸（抖动）操作系统会对CPU的工作情况进行监督，如果发现CPU出现空闲，它会调入新的进程来增加多道程序度，保持CPU的高利用率。但是在采用全局置换的方式下，它会导致其它进程的某些页被置换出内存，而该进程执行时会因此产生缺页，所以它又会置换另外进程的页，由此造成连锁反应，使得整个系统中页面置换频繁发生。在每次置换过程中，都需要启动磁盘I/O，这种低速的延迟操作会造成CPU等待，操作系统发现CPU空闲后，又开始增加多道程序度……于是整个系统就在进行频繁的页面置换，这种状况就称为“抖动”，它会严重地影响到系统的性能。抖动的发生CPU利用率抖动多道程序度为了减少抖动的产生，保证系统性能，可以采用局部置换的方法。发生缺页的进程不能置换其它进程的物理块，只能从系统为自己所分配的地址空间中置换。这样当一个进程发生抖动时，不会造成其它进程后继抖动，将抖动的影响限制在一个小的范围内。但是，这种方法有一定的局限性，因为发生抖动的进程会因为频繁进行磁盘I/O而形成一个等待队列，这个等待队列也会造成正常的进程置换页面时间的增加，从而影响CPU的吞吐量。为了预防抖动，应该给进程尽可能提供一段时间所需的所有页面，但系统又如何得知到底需要哪些页面呢？有多种技术