1. 基础知识

(1). 逻辑地址和物理地址

​ 物理地址是当前数据在整个计算机内存中的绝对位置,逻辑地址是指当前数据在本进程之内的偏移量地址.

​ 逻辑地址+进程首地址=物理地址

2. 内存管理的概念

(1). 内存管理的内容

• 内存空间的分配与回收
• 使用虚拟技术对内存空间进行扩充
• 将逻辑地址与物理地址进行转换
• 内存保护功能,保证各个进程在各自的内存空间中运行,互不干扰
  • 上限寄存器和下限寄存器之间的内存可以访问
  • 重定位寄存器+逻辑地址(界地址寄存器存放最大逻辑地址)

(2). 覆盖与交换

​ 程序大小通常超过物理内存总和

1). 覆盖技术

​ 覆盖技术是指将程序分为多个段,使用的那一部分调入内存,不使用的部分在需要时才会调入内存.

​ 常驻内存的段放在固定区中,调入后不在调出.不常住的段放在覆盖区,需要时调入,采取覆盖策略

​ 程序员必须显式声明覆盖结构

2). 交换技术

​ 当内存空间紧张时,将内存中某些进程暂时调出外存,把外存中某些已经具备运行条件的进程调入内存(内存和磁盘中动态调度)

​ 中级调度就是判断哪一些进程适应给被调入的.

​ 暂时换出外存等待的进程状态被称为挂起态.

​ 对应于此,磁盘空间也被分为对换区和文件区.对换区追求文件换入换出速度,采用连续分配方式.文件区追求空间的利用率,采用离散分配方式.总之对换区的I/O速度比文件区更快.

3. 连续分配管理方式

​ 连续分配是指为用户进程分配的必须是一个连续的内存空间.

​ 外部碎片:没有分配的内存过小,无法分配给进程

​ 内部碎片:分配给进程的内存无法被全部利用

(1). 单一连续分配

​ 将整个内存空间全部分配给一个用户区

​ 无外部碎片但是有大量的内部碎片,并且只能用于单用户单道

​ 存储器利用率极低

(2). 固定分区分配

​ 系统将用户空间划分为若干固定大小的区,每一个进程占用一个区.

• 分区大小相等

  • 缺乏灵活性
  • 但是很适合控制多个相同对象

• 分区大小不相等

  • 增加了灵活性
  • 常在系统中根据作业的大小分配内存

  无外部碎片

  有大量的内部碎片

[图片上传失败...(image-d7648a-1582351682748)]

(3). 动态分区分配

​ 不会预先划分内存分区,而是在进程装入内存时,根据进程的大小动态的建立分区.

​ 空闲分区表:记录了每一个未被分配的分区(由已分配分区划分而出)的相关信息.

​ 没有内部碎片,但是有外部碎片

​ 可以通过紧凑技术解决外部碎片.

4. 动态分区分配算法

(1). 首次适应算法(First Fit)

​ 空闲分区以地址递增的次序排列,每次按顺序查找大小能满足的第一个空闲分区.

(2). 最佳适应算法(Best Fit)

​ 空闲分区按大小递增排列,每次查找的都是满足大小的第一个.

​ 尽可能的减少外部碎片,但是查找的耗时较长

(3). 最坏适应算法(Worst Fit)

​ 空闲分区按照大小递减排列,每次找到大小满足的第一个空闲分区.

​ 好处是匹配起来非常快,坏处是后面的大进程可能会无空间可用.

(4). 邻近适应算法(Next Fit)

​ 每次都从上次结束的位置开始检索.

​ 循环链表实现.

1574606595169

5. 基本分页存储管理

(1). 概念

​ 把内存分为一个个相等的小分区,称为页框,再按照分区大小将用户进程分为若干小分区,成为页面.每一个页面都对应分配一个页框.

​ 分区大小越小,内部碎片就越小,内存利用率越高

​ 各个页面不必连续存放,也不必按照先后顺序来,可以放到不相邻的各个页框中.

​ 操作系统为每个进程建立一张页表,其中按顺序存储了进程中每一个页对应的页框号(内存中的映射).

(2). 实现地址的转换

​ 每一个页表都对应一个进程内部的页面分配情况.也就是说,内存的逻辑地址就是内存在业表内的偏移地址.

​ 那么使用==逻辑地址/页大小==得出当前内存==所在页的页号==和在==当前页中的偏移量==.

​ 然后会对页号和页表长度进行对比,如果超出范围,则产生越界中断

​ 使用==页号 * 页大小 + 页表起始地址==计算得出当前页表项的地址,从中取出内存块号

​ ==内存块号 * 页大小 + 偏移地址==就能得到偏移地址

​ 页面大小一般为2的n次幂,取余操作可以使用&(n-1)快速完成.并且,页的数量可以直接用逻辑地址的前32(地址位数)-n位表示.

1574686605556

(3). 快表

​ 程序中对一块内存的访问往往都是一段时间内多次的(循环).

​ 对一块内存的使用一般也导致使用相邻的内存(内存连续存放).

​ 那么如果对内存的访问加上缓存,就会极大地提高效率.

​ 产生了快表:快表中存储了==最近使用的几个页号和对应内存块号==,对内存的访问前会先到快表中查询,查询不到再去通过页表计算,获取相应块中的内存.在找到页表项之后会存入快表中作为缓存使用.

​ 一旦内存发生更改,会删除快表中的缓存.

(4). 多级页表

​ 单级页表存在一个问题:页表的项数通常很大.一个支持32位逻辑地址的机器,使用4K的页大小.那么会出现2²⁰个页,一个页表项如果为4B,那么需要2²²的内存才能存储下这个页表.

​ 这么大的连续空间分配起来难以进行.

​ 所以出现了多级页表.

​ 使用顶级页表来二级页表,进而管理最低级的页表.

​ 接上面的问题.4K的页最多存放2¹⁰个页表项,那么使用一个二级页表存放2¹⁰个页表项,每一个页表项指向一个存放2¹⁰个页表项的页表,这样就可以离散的存放下2²⁰个页.

1574688651692

​ 如果使用多级页表存储,那么一个页表的大小不能超过一个页面,因为一个页表就存储在一个页面中.

6. 基本分段存储管理

(1). 概念

​ 分段就是按照一些逻辑上的意义将内存进行划分,这样一来,每个段的大小是不固定的.每一个段会唯一对应一个段号,而段号是在编译阶段由段名替换而来的,段名已经显式的具有实际意义了,是开发者在代码中定义的.

​ 可以这么理解,一个端中存储的是一个对象的所有内存,编译时根据对象名得到端号,再由段号得到段.

​ 段表中存储了端长和基址(本段在物理地址中的起始地址),端表项是固定的,所以不需要显示的声明段表项.

(2). 地址转换

​ 地址变换时会提供段号和段内地址(对象名和属性在对象内的偏移量).根据段号查找到相应的段表项,根据段长判断是否越界,是否产生越界中断.然后查找到基址,加上段内地址就得到了物理地址.

1574689838112

(3). 和分页存储的对比

​ 页是信息的物理单位,对用户不可见.段是地址的逻辑单位,对用户可见.

​ 页的地址空间是一维的,只通过逻辑地址就可以得到物理地址.段的地址空间是二维的,需要给出段号和段内地址.

​ 分段比分页更容易实现信息共享,因为信息的共享通常都是按照一定的逻辑一起进行共享的.但分段式管理会产生外部碎片.

7. 段页式管理方式

(1). 概念

​ 之前讨论了多级页表管理的分页存储管理方式,又讨论了分段式管理易于进行共享的特点.

​ 将二者进行结合,就可以取得二者的优点.

​ 利用分段式管理来管理页表,然后通过分页式管理来管理页.这样使用段表将页进行逻辑上的划分,也能实现易于共享的需求了.

​ 这里的段表存放的就不是基址了,而是页表长度和页表存放块号.

​ 每次地址转换会提供逻辑地址(逻辑地址可以得到段号,页号和业内偏移量),先根据段号得到页表长度和页表存放块号,根据业内偏移量和页表长度判断是否越界.然后根据页号和页表存放块号得到页,再根据业内偏移量得到物理内存.

1574691926289

8. 虚拟内存

(1). 概念

​ 在进行装入时,只将很快会用到的部分内存装入内存,暂时用不到的内存留在外存中.当要访问的信息不在内存中时,操作系统将其从外存中调入内存.当内存空间不够时,操作系统负责将暂时不用的内存换出外存.

​ 在用户看来,似乎能加载很多的内存,这就是虚拟内存.

​ 虚拟内存中,内存管理是离散分配的,因为内存的调入是不同时进行的,要进行连续分配不现实.

​ 页表中新增了状态位(是否已经调入内存),访问字段(最近被访问的次数或者时间),修改位(是否被修改,决定下一次是否覆盖页面中的旧数据),外存地址.

(2). 页面置换算法

1). 最佳置换算法(OPT)

​ 选择在之后最长时间内不会被访问的内存.(不可能实现,因为不可能预知未来对内存的访问)

2). 先进先出置换算法(FIFO)

​ 淘汰最先进入内存的页面.算法性能差.

3). 最近最久未使用置换算法(LRU)

​ 每次置换之前应该会有若干的无需置换的内存访问,这里置换的是最早未被使用的页面.

4). 时钟置换算法(CLOCK)

​ 访问位标志是否被使用(0和1).

​ 每次进行算法时,进行扫描,扫描到页如果被使用过,标志位置为0.如果没有使用过,置换出.

​ 最差的状况就是全部都有被使用,那么第一轮扫描会全部置0,下一次一定能找到为0的页面.

5). 改进的时钟置换算法

1574691846583