内存管理

内存管理概念

• 内存管理的功能:
  • 内存空间的分配与回收
  • 内存转换:从逻辑地址到物理地址的转换
  • 内存扩展:虚拟存储,把外存当做内存用
  • 内存保护:进程只在自己的领域活动,不跑到别的进程的地址空间

    有两种方法：

    1. 在CPU中设置一对儿上下限寄存器，访问的时候直接和这俩值相比
    2. 用基地址（基地址寄存器）和偏移量（界地址寄存器）这种方法

  • 内存共享:让多个进程访问同一内存段,实现进程的通信
• 编译、链接、装入：
  • 编译是把源代码变成目标语言，这种语言可能是机器语言或者是某种中间表示形式
  • 链接是把目标文件和库文件连在一起，生成可执行文件，逻辑地址就是在这个阶段形成的
  • 装入是由装入程序把可执行文件装入内存，这个阶段中，逻辑地址变为物理地址。

    装入有三种方式：

    1. 绝对装入：逻辑地址就是物理地址，程序直接放到内存
    2. 可重定位装入：程序的地址从0开始，所有地址相当于偏移量，装入的时候修改基地址就好
    3. 动态运行时装入：先把这个程序装入内存，直到程序执行的时候才变换地址，这种方式可以动态申请内存，还可以不连续存放

• 连续分配管理方式：
  • 单一连续分配：把内存划分为用户区和系统区，用户区就一个用户程序，最垃圾，只适合单任务，单用户的操作系统使用，内存利用率也超级低
  • 固定分区分配：把内存划分为固定的分区供程序装入
    • 分区相等：没有灵活性，程序太大无法装入，程序太小碎片老多
    • 分区不等：多个小分区，适量中分区，一点大分区
  • 动态分区分配：来一个程序排一个程序，中间有程序撤退的时候，把来的程序看情况塞到中间的空挡里；这种方法用的时间长的话内部碎片会越来越多
    回收的时候有四种情况：
    1. 回收区的前边是空闲分区，合并的时候修改前一个分区表项的大小即可
    2. 回收区的后边是空闲分区，合并的时候修改后一个分区表项的始址和大小
    3. 回收区的前边和后边都是空闲分区，合并的时候取消后一个分区的表项，修改前一个分区的大小
    4. 回收区前后都没有空闲分区，为这个分区新建一个表项，把这个表项插入到空闲分区链中
• 基于顺序搜索的分配算法：
  • 首次适应算法（first fit）：把地址从小到大开始排，从头开始找适合的分区
  • 邻近适应算法（next fit）：在first fit的基础上，从上一个结束查找的位置开始查找，也就是循环查找，通常比first fit的性能更差
  • 最佳适应算法（best fit）：把容量从小到大开始排，从头开始找到合适的分区，会产生最多的外部碎片。
  • 最坏适应算法（worst fit）：把容量从大到小开始排，从头开始找到合适的分区
    综合来看：首次适应算法的性能最好。
• 基于索引搜索的分配算法：对每类大小相同的空闲分区单独设立一个空闲分区链，然后设置一张索引表来管理这些空闲分区链
  • 快速适应算法：分配过程有两部：1.根据进程的长度在索引表中找到一个刚好能容纳这个进程的空闲分区链；2. 从链表中取出第一块分配给进程
    • 优点：查找快，不产生内部碎片；
    • 缺点：回收分区要有效合并分区系统开销大
  • 伙伴系统：分区的大小为1、2、4、8、……，假如有个进程大小是3 ，那就先找4的空闲分区链，如果4的空闲分区链用完了，那就找8的空闲分区链，然后把8分区链里边拿出一个8分成两个4（这两个4就是伙伴），一个4归进程用，另一个4加入4的空闲分区链
  • 哈希算法：建立哈希函数，构建一个以空闲分区大小为关键字的哈希表，分配时根据分区大小通过哈希函数计算得到哈希表中的位置，从而得到相应的空闲分区链表（我不是太懂哈希，数据结构没学好，这个好抽象）

基本分页存储管理

• 固定分区会产生内部碎片，动态分区会产生外部碎片
• 分页存储的基本概念：
  • 逻辑地址的页面叫页号；物理地址的页面叫页框号；页号与页框号一一对应；（可烦人，这俩名字有可多小名，弄嘞人可迷）
  • 逻辑地址的地址结构：
    页面太小会导致页面数过多，占用大量内存；
    页面太大会导致内部碎片过多，降低内存使用率；
    页面的大小可以根据页内偏移量计算
  • 页表的作用是逻辑地址到物理地址的转换
    页表由页号和块号（页框号） 组成，页表的页表项是连续存储的，就按顺序来数页表项也和页号对应，所以页号不用存储，实际上就一个块号
    从逻辑地址到物理地址的计算过程：
    • 计算页号和偏移量
    • 判断页号是否越界
    • 根据页号得到块号（页框号）
    • 根据块号和偏移量得到物理地址
• 地址转换不能太慢，要不进程访存就很卡，然后就引入了快表(TLB)
  • 具有快表的地址变换和访问cache差不多（cache和TLB是不同的两个硬件机构）：
    • 根据CPU给出的逻辑地址查快表
    • 快表有就命中，直接根据找到的页框号访问物理地址，快表里边没有就上内存查页表，然后把这个页表项存到快表里边
• 两级页表：
  • 二级页表的逻辑地址结构：
  • 二级页表地址变换示意图：
  • 地址变换的过程：
    • 根据二级页号找到外层页表（第二级页表）对应的页表项的块号
    • 这个块号又成了下一级页表的页号，根据这个页号找到对应的一级页表项在哪个具体的一级页表
    • 再根据逻辑地址给出的页号在上一步找到的页表里边找对应的页表项，这次就找到了最终的物理块号

基本分段存储管理

• 分段和分页差不多：分段是根据程序的逻辑分的，就像按书的章节分一样；分页就是无脑把内存均分成相等的空间，跟书页的一面一面分一样
  • 段表的内容：其实段表里边就存了段长和这一段在主存中的基址，因为段表和页表一样也是按段表项连续存放的
    段长的作用就是和偏移量比较看有没有越界
    计算物理地址直接后一基址+偏移量就得出了

    哦哦哦~~~，这也就是为什么说分页的地址是一维的，分段是二维的。好无语，就这还起一个抽象的一维二维的名字，不就是地址是一个东西还是两个东西

• 段的共享与保护：
  • 共享：分页系统也能实现共享但是没有分段系统方便，比如一个程序要进行共享，分页的话要建立很多页表项指向要分享的页框，但是在分段系统中，只需要一个段表项指向要分享的段就行
    比如，我向你分享一个故事情节，我可告诉你这个情节在第几页到第几页，但是我也可以直接告诉你情节在哪一段，显然第二个更方便
  • 保护：地址越界保护，分页是看页号越界了没有，分段直接拿段长和偏移量比较看越界了没

段页式存储管理

• 分页存储管理能有效地提高内存利用率，而分段存储管理能反映程序的逻辑结构并有利于段的共享和保护
• 段页式的逻辑地址：每个程序有一个段表，每个段有一个页表
• 在段式和段页式分配方式下，CPU的访存次数：
  • 段式：
    • 第一次访存为了特定段的基址
    • 第二次访存根据基址和偏移量得到数据
  • 段页式：
    • 第一次为了特定段和页表的基址
    • 第二次根据段和页表得到物理块号
    • 第三次根据物理块号和偏移量得到数据

虚拟内存管理

• 虚拟内存对应手机上设置里边那个扩展内存；
  • 传统的内存管理，一个作业想要运行需要把整个作业装入内存，一是占地大，二是可多程序需要装入内存的时候就能装几个，降低了系统的并发性
    • 一次性
    • 驻留性
  • 然后就有了虚拟内存，根据局部性原理，只需要把用的到页或段调入内存作业就能运行
    • 多次性
    • 对换性
    • 虚拟性
• 虚拟内存的实现方式：
  • 请求分页存储管理
  • 请求分段存储管理
  • 请求段页式存储管理

请求分页管理方式

• 页表项的组成：可以看到多了后边四个（又解锁一个小名：物理块号，目前有：页框号、块号、物理块号）

  • 状态位：程序是否调入内存
  • 访问字段：记录本页的访问次数，给调出算法提供指示
  • 修改位：这一页是否被修改过
  • 外存地址：记录本页在外存存放的物理块号

• 缺页处理的过程和进程状态的变化：

  1. 产生缺页中断：当进程要访问的页面不在内存时，便产生一个缺页中断，请求操作系统的缺页中断处理程序处理。
  2. 阻塞进程：此时缺页的进程被阻塞，并放入阻塞队列。
  3. 判断内存页框情况
     • 有空闲页框：若内存中有空闲页框，则为进程分配一个页框，将所缺页面从外存装入该页框，并修改页表中的相应表项。
     • 无空闲页框：若内存中没有空闲页框，则由页面置换算法选择一个页面淘汰。若该页在内存期间被修改过，则还要将其写回外存；未被修改过的页面不用写回外存。
  4. 唤醒进程：调页完成后，将被阻塞的进程唤醒，放回就绪队列。
  5. 中断处理步骤：缺页中断作为中断，要经历保护 CPU 环境、分析中断原因、转入缺页中断处理程序、恢复 CPU 环境等步骤。

     • 缺页中断属于内部异常
     • 一条指令在执行期间可能会产生多次缺页中断

• 地址变换的过程：要实现虚拟内存，在一般的分页系统地址变换的基础上增加了缺页中断的功能

  1. 先查看快表
     • 命中：取出该页的块号，修改访问位
     • 未命中：去内存的页表里边查
  2. 查看页表：
     • 命中：取出该页的块号，把该页写进快表
     • 未命中：产生缺页中断，请求系统（哦~~~，请求分页原来是这个意思）把该页从外存拉到内存，然后更新页表和快表（这种最坏的情况俩表都要更新）
  3. 根据物理块号和页内地址（小名，又是可恶的小名，偏移量）拼接成物理地址

页框分配

• 驻留集：在内存中给单个进程分配的页框的集合就叫驻留集
  • 驻留集越小，内存可以容纳的进程就越多，系统的并发性就越强，但是进程的缺页率会升高
  • 驻留集越大，大到一定程度时对缺页率的改善就不明显了，这样就浪费内存空间而且还降低了系统的并发能力
• 内存分配策略：
  • 分配有两种：
    • 固定分配：每个程序的驻留集（在内存中分配的页框）在整个程序运行时都保持不变
    • 可变分配：可变就是运行的时候程序占的页数一直在动态调整
  • 置换也有两种：
    • 全局置换：缺页调换页时，这个程序的页可以和其他程序的页进行调换，也就是占用别人的空间了
    • 局部置换：缺页调换页时，只能在本程序内进行调换
  • 常理来说，这四个可以两两搭配组合成4种分配策略，但是，没有固定分配全局置换，因为全局置换会占用别人的空间，而固定分配每个程序的空间已经固定下来了
• 固定分配时物理块调入：
  • 平均分配：把空闲的内存均分给每个进程
  • 按比例分配：根据进程的大小按比例分配空闲内存
  • 优先权分配：为优先权高的进程多分配一些内存

    通常可以把内存分成两个部分：一部分按比例分配，一部分按优先权分配

• 调入页面的时机：
  • 预调入策略：又是局部性原理，但是这种策略的准确率不高，也就50%，所以主要用于首次调入
  • 请求调页策略：需要哪一个调入哪一个，这是虚拟存储器大多采用的策略，但是I/O开销比较大
• 从什么地方调入页面的三种情况：
  分页系统把外存分为两部分：
  对换区：用于存放对换页面，连续存储所以I/O比较快
  文件区：离散存放，I/O慢
  1. 系统拥有足够的对换区空间：把与进程有关的页面全部复制到对换区，全部页面都从对换区调入
  2. 系统缺少对换区空间：把需要修改的页面调入对换区，把只用读的文件还停放在文件区
  3. UNIX方式：未运行过得页面从文件区调入，曾经运行过但是被调出的页面放到对换区

页面置换算法

• 最佳置换算法（OPT）：
  例如:给某个进程分配了三个页框，访问的页面序列：7、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、7、0、1
• 先进先出算法（FIFO）：没有利用局部性原理，所以性能较差，而且这个算法还会出现Belady异常，因为就算分配的再多页框数，这个算法访问的页面不按常理访问，一点都不遵循局部性原理
• 最近最久未使用算法（LRU）：和最佳置换算法差不多，OPT是根据未来选择最近最久未使用的页面置换，LRU是根据过去选择最近最久未使用的页面置换，但是过去与未来没有必然的联系，就这样这个算法也是性能最接近OPT的，就是实现起来消耗太大
• 时钟（CLOCK）置换算法：
  • 把每个页面设置一个访问位并且赋值为1，然后弄一个循环指针在页面上转圈，转到谁，谁减一，也就是说给这些页面一次驻留内存的机会，一旦这个指针转到0的页面上边就把这个页面淘汰出去
  • 改进型CLOCK算法：增加一个修改位，和传统的办法差不多，这个是把页面分成了4个等级，没有修改没有访问等级最低最先被淘汰，而且！！！，修改位比访问位更重要
• TLB和cache的综合