第五章—存储器管理

一、存储器分类

寄存器、高速缓存、内存、磁盘缓存（内存部分空间）、磁盘

---

二、程序的装入与链接

一个程序运行的过程：

1. 编译：对磁盘中即将运行的程序的源代码进行编译，形成若干个目标模块（这些模块的起始地址都是从0开始的，不是连续的，每个模块是独立的）。

2. 链接：将每一个目标模块和所需的库函数链接在一起，形成一个完整的模块。

3. 装入：将完整的模块装入内存中。

两种地址：

• 逻辑地址：相对地址，CPU生成的，所有程序的逻辑地址都是从0开始。

• 物理地址：绝对地址，内存中的地址。

（一）、程序的装入

重定位：把逻辑地址转换为物理地址

1. 绝对装入方式：适用于单道程序，程序员必须熟悉内存的使用情况。

2. 可重定位装入方式（静态重定位）：装入时所有的逻辑地址都转换为物理地址，以后不再改变。该方法会根据内存的使用情况，将装入模块装入内存的适当位置。物理地址=逻辑地址+内存起始位置。

   缺点：不允许程序运行时改变程序和数据的物理地址。然而实际情况是程序运行过程中会改变物理地址，如后面的内存空间不足时产生的对换现象。

3. 动态运行时装入方式（动态重定位）：模块装入内存后不会立即重定位，而是推迟到程序真正要执行时才进行重定位。

（二）、程序的链接

链接作用：因为每一个模块的地址都是从0开始的，不是一个完整的，所以通过链接后，这些模块就会是一块连续的地址的完整模块。

1. 静态链接：程序运行前就链接完成了，以后也不再拆开。

2. 装入时动态链接：装入内存时，采用边装入边链接的方式。

   缺点：这种方式是把所有目标模块链接了，可是有些模块根本不会被使用到，所以引出以下方法。

3. 运行时动态链接：对某些模块的链接推迟到程序执行时才进行。如：执行过程中，发现即将使用的模块没有被链接装入，这时就需要马上去调用链接装入到内存中来。

---

由于装入内存时，可能发生内存空间不足或所需空间大于系统提供的空间，需要以下两种技术解决问题。

三、对换与覆盖

###

---

四、重点：如何为装入进来的程序进行内存分配呢？采用什么样的方法和结构把程序放入内存当中？

连续分配存储管理方式、分页存储管理方式、分段存储管理方式、段页式存储管理方式

（一）连续分配存储管理方式、

1. 单一连续分配：适用于早期的单道程序，一次只能运行一个程序。

2. 固定分区分配：适用于多个相同程序的多道程序，把用户区划分为若干个大小一样的区域。

   分区使用表：包括了分区的起始地址、大小、状态。

3. 动态分区分配：需要一个数据结构来描述内存情况，如空闲区和已分配区，为分配提供依据。以下是数据结构的两种表现形式：

   空闲分区表：记录分区号、大小、起始地址、状态。按照分区大小排序，小分区号存放小空间。

   空闲分区链：把所有分区通过指前后指针形成一个双向链表

   分配算法：当程序装入时，使用分配算法选择一个合适的分区分配给作业。

   （1）顺序分配算法

   首次适应算法：从空闲分区的链首即第一个分区开始找，直到有一个满足作业要求的空间大小，然后按照作业的大小把该分区分割，留下小部分空间仍在空闲链中，但是起始地址大小已经改变（这也造成了碎片很多的问题）。

   循环首次适应算法：不再从链首开始找，而是从上一次查找过的位置开始。解决了由于许多无用小碎片带来了无用查找的开销问题。

   最佳适应算法：将空闲分区按照容量以小到大的顺序排列，从此顺序中找最合适大小的一个区域。

   最坏适应算法：将空闲分区按照容量以大到小的顺序排列，优点是产生的碎片少。

   （2）索引分配算法（使用于大系统）

   将分区大小进行分类，相同大小的为一类，每一类单独设立一个空闲分区链表，并设立一张索引表来管理这些空闲分区链表。

4. 动态重定位分区分配：

   解决的问题：由于分割导致的许多小碎片及其浪费内存空间，为了利用好小碎片，我们把已经在内存中的程序作业进行移动，使得他们相邻，剩下的就是小碎片空间了，就实现的小碎片的连接效果，称之为“紧凑”，但是每一次紧凑都需要改变更新被移动作业的地址。

   动态重定位实现原理：增加一个硬件地址变换结构，名字叫重定位寄存器（存放程序在内存中的起始地址），每一次紧凑后，只需要在重定位寄存器中把新的起始地址替换原来旧的起始地址就可以了。

---

（二）分页存储管理方式、

实现方法：

将程序分割成若干个大小相同的区域（常见的有1KB、2KB……），叫作“页”或“页面”，同时把内存空间分割成若干个物理块。页和块的大小相同，就可以把程序的页放入内存中的任何一个块中，使用页表来表示页号与块号的映射关系。

页面和物理块：都要编号，从0号开始。

分页地址结构：

长度32位，前20位是页号，后12位是页内地址（一个页里面自己的地址），两者结合就是页的地址。

页表：

记录每一个页所对应哪一个块，实现页号到物理块号的地址映射。页表存放在内存中的，但是页表的起始地址和页表长度是存放于页表寄存器中的，未执行程序时，页表在本进程的PCB中，调用进程时才把页表放入页表寄存器中。

地址变换机构：将逻辑地址变换为物理地址

页内地址与块内地址相同，只需要实现将逻辑地址中的页号变换为内存中的物理地址块号。

物理地址的获取原理：首先访问页表寄存器得到该页表在内存中的位置，因为页表是在内存中的，接着需要CPU去访问内存中的页表，找到逻辑地址提供的页号所对应的物理块号，自此完毕。最后物理地址=块号+页内地址。

做题常用式子：

逻辑地址=页号*页面大小+页内地址

页号=逻辑地址/页面大小

页内地址=逻辑地址%页面大小

物理地址=块号*块大小+页内地址

有效存取时间的计算：

3个因素决定：内存访问时间t（地址变换后到内存取到数据的这段时间）、快表的命中率a、快表的访问时间m

有效访问时间=a * m + (1-a) * (t+m) + t

（三）分段存储管理方式、

实现方法：

将程序分割成若干个大小不同的区域，叫作“段”，段是连续的空间，每一个段可以离散的存放在内存中任何位置。

段的逻辑地址：

段号+段内地址，短号16位、段内地址16位。

（四）段页式存储管理方式

分段和分页相结合，把用户程序分成若干段，再把每段分成若干页。

---

五、重点习题

题目：

1、某系统采用动态分区分配方式管理内存，内存空间为640KB，高端40KB用来存放OS。在分配内存时，系统优先使用空闲区低端的空间。对下列的请求序列：作业1申请130KB、作业2申请60KB、作业3申请100KB、作业2释放60KB、作业4申请200KB、作业3释放100KB、作业1释放130KB、作业5申请140KB、作业6申请60KB、作业7申请50KB、作业6释放60KB，请分别画图表示出使用首次适应算法和最佳适应算法进行内存分配和回收后，内存的实际使用情况。

解答：

首次适应算法将空闲区按起始地址递增的次序排序，而最佳适应算法则将空闲区按分区大小递增的次序排序。在分配时，它们都是从开始顺序查找，直至找到一个足够大的空闲分区为止，然后按作业大小从该分区中划出一块内存空间分配给请求者，余下的分区（如果有的话）仍按上述原则留在空闲分区链中；在释放时，则需分别按地址递增或大小递增的次序将空闲分区插入空闲分区表（链），并合并空闲分区。表5-2-6给出了使用这两种算法进行上述内存分配和回收的具体过程。

使用首次适应算法和最佳适应算法进行上述内存的分配和回收后，内存的实际使用情况分别如图（a）和（b）所示。

---

2、

（1）逻辑地址3064H=0011 0000 0110 0100B，则p=0011B=3D,页内地址w=0000 0110 0100B=100D,查页表得知3号页存在7号块，因此物理地址为：

0111 0000 0110 0100B = 7064H=28772D 或者

7×4KB+100=28KB+100=28772

（2）在请求分页存储管理中，系统是通过页表进行地址转换。先将逻辑地址分解成页号P和页内地址W两部分，然后查页表，可得页号P对应的物理块号为B，拼接B和W，从而得到物理地址。也可用公式换出对应的物理地址为：物理地址=块号×页面大小+页内地址

 解题步骤：

1、逻辑地址的十六进制转为二进制形式

2、由逻辑地址二进制知页内地址、页号的二进制形式

如何知道？页面大小4KB转换为2的幂次方，幂次方就是页内地址的位数，剩下的就是页号的位数

3、根据页号二进制得十进制页号，看表知块号，把块号转二进制

4、块号二进制+页内地址二进制=物理地址二进制、物理地址可以转为十六进制