4. 内存管理

• ​目标

  • ​内存分配，内存回收

  • ​提高内存空间利用率，内存访问速度

• ​存储器的层次结构

  • ​层次结构

    • ​寄存器

    • ​高速缓存

      • ​芯片内

      • ​芯片外

    • ​主存储器

    • ​本地二级存储

    • ​远程二级存储

  • ​局部性原理

    • ​时间局部性

      • ​某条指令一旦执行，不久后可能再次执行

    • ​空间局部性

      • ​访问了某个单元，不久后，附近的存储单元也被访问

• ​程序的链接和装入

  • ​链接

    • 将编译后的目标模块装配成一个可执行程序

    • ​分类

      • ​静态链接

        • ​任务

          • ​对逻辑地址修改

          • ​变换外部调用符号

        • ​优点

          • ​运行速度较快

        • ​缺点

          • ​内，外存开销大

          • ​程序开发不够灵活

        • ​程序运行前，用链接程序将目标模块连接成一个完整的装入模块

      • ​动态链接

        • ​将某些目标模块的链接推迟到模块中的函数被执行时进行

        • ​优点

          • ​节省内，外存空间

          • ​方便程序开发

        • ​缺点

          • ​运行时间开销大，速度慢

  • ​装入

    • ​1.绝对装入

      • ​单道程序

        • 事先已知，模块装入内存后无需对程序和数据的地址进行修改

    • ​2.可重定位装入（静态重定位）

      • ​装入时，逻辑地址映射为物理地址。

      • ​特点

        • ​编译程序使目标模块的起始地址从0开始

        • ​程序装入时，装入程序根据内存使用情况将装入模块装入到内存的某个位置并对模块进行重定位

      • ​重定位？

        • ​程序装入时对目标程序中的指令和数据地址的修改过程

    • ​3.动态运行时装入（动态重定位）

      • ​发生在虚拟存储的系统中

      • ​程序装入内存后还可能再移动

      • ​地址映射必须延迟到程序执行时再进行

• ​连续分配存储

  • ​~管理方式

    • ​1.单一连续分配

      • ​内存中只有一个用户区--单用户，单任务

      • cpu访问检查 内存单元的地址是否大于界限寄存器的值

        • ​大于则是非法地址

    • ​2.固定分区

      • ​将用户内存空间划分为若干个大小固定的区域

      • ​划分方法

        • ​分区大小相等

        • ​分区大小不等

      • ​数据结构

        • ​固定分区说明表

          • ​分区编号

          • ​分区大小

          • ​分区起始地址

          • ​分区状态

      • ​回收

        • ​把分区状态改为空闲，state=0

    • ​3.动态分区

      • ​原理

        • ​初始一个大空闲区，进程请求空间就给其划分空间

        • ​过段时间，空闲分区可能不连续

        • ​维护一个空闲分区表

      • ​数据结构

        • ​空闲分区表

          • ​分区编号

          • ​分区大小

          • ​分区起始地址

        • ​空闲分区链

          • ​分区大小

          • ​分区起始地址

          • ​指向前一个空闲分区节点的指针

          • ​指向后一个空闲分区节点的指针

      • ​算法

        • ​首次适应算法

          • ​地址递增，从链首开始，找到一个为止

          • ​缺点：

            • 低地址​留下难利用的小空闲区

            • ​高地址大空闲区多

        • ​循环首次适应算法

          • ​优点

            • ​空闲区分别均匀

            • ​查找开销较小

          • ​缺点

            • ​容易使系统缺乏大空闲区

        • ​最佳适应算法

          • ​分区大小递增

          • ​优点

            • ​避免大材小用, 提高内存利用率

            • ​容易留下难利用的小空闲区

      • ​分配与回收

        • ​分配

          • ​1.检索空闲分区链，找到满足m.size>=u.size的空闲区

          • ​2.m.size-u.size<=size ,则直接把空闲分区分配给进程，否则把差值的空闲空间作为一个新的空闲分区

          • ​3.将分配给进程的分区起始地址返回给内存分配程序的调用者

          • ​4.修改空闲分区链表

        • ​回收

          • ​1.释放一块连续的内存区域

          • ​2.如果释放的区域与其他空闲区相邻，则合并

          • ​3.修改空闲分区链

• ​分段+分页+段页

  • ​分页存储管理

    • ​基本原理

      • ​基本概念

        • ​页，页框，分页存储，业内碎片，页表（页号-页框号）

      • ​地址结构（32位时）

        • ​页号 （取整）高20位

        • ​页内偏移量 （取余）低12位

      • ​分页地址变换

        • ​逻辑地址到物理地址

        • ​过程

          • ​1. 进程执行，从pcb中页表起始地址，页表长度送CPU的页表寄存器

          • ​2.cpu访问逻辑单元A

          • ​3.分页地址硬件将A分为页号，和页内偏移量2部分

          • ​4.由硬件检索页表，得到A所在的页对应的页框号

          • ​5.页框号和页内偏移量送物理地址寄存器，计算物理地址

      • ​页大小

        • ​机器的体系结构和操作系统决定

        • ​因素

          • ​管理内存开销

          • ​内存利用率

    • ​快表

      • ​出现原因

        • ​减少cpu在有效访存的时间开销

        • ​提高访问速度

      • ​TLB

        • ​用来存放最近被访问过的页表项

          • ​键值对 64-1024

        • ​地址变换过程

          • ​1.cpu产生页号，页偏量将页号交给tlb

          • ​2.查找TLB, 找到页号，形成为例地址，否则TLB失效

          • ​3.TLB 失效，访问完后要写入TLB。 tlb已满时根据最近最少使用选择替换

    • ​空闲页框

      • ​位图

      • ​空闲页框的链表

    • ​虚拟存储系统

      • ​基本思想

        • ​部分装入

        • ​请求调入

        • ​置换

      • ​好处

        • ​提高内存利用率

        • ​提高多道程序度

        • ​把逻辑地址和物理地址分开

      • ​特征

        • ​离散型

        • ​多次性

        • ​虚拟性

        • ​对换性

      • ​实现方式

        • ​请求分页系统

          • ​硬件

            • ​页表

              • ​描述页的各种数据，逻辑地址到物理地址映射时需要的页号与页框号对应关系

              • ​各字段

                • ​页框号

                • ​状态为

                • ​访问字段

                • ​修改位

                • 保护位

            • ​缺页异常机构

              • ​作用

                • ​访问内存时发现缺页，产生缺页信号，cpu中断当前控制流的执行，转执行中断缺页异常处理程序

              • ​过程

                • ​1.检查页表状态位。是否在内存，不在就产生缺页信号

                • ​2.执行缺页异常处理过程-- 先在内存里找一个空页框，把需要的页放进去

                • ​3.修改页表，更新已调入页的存在位，页框号，访问位，等值

                • ​4.重新执行因为缺页而中断的指令

            • ​地址变换

              • ​1.由地址变换机构分离出页号好页内偏移地址

              • ​2.以页号为索引查找快表，读页框号，算物理地址、

              • ​3.若快表中没有，就到内存页表中查，根据状态位看是否调入到内存，已调入直接访问读页框号，算物理地址，更新到块表中

              • ​4.若内存页表没有，产生缺页中断，修改页表，重新执行中断指令

          • ​页分配策略

            • ​最少页框数

            • ​页分配和置换策略

              • ​从分配给进程的页框数

                • ​固定分配

                • ​可变分配

              • ​从选择淘汰页的候选页范围

                • ​局部置换

                • ​全局置换

            • ​分配算法

              • ​平均分配算法

              • ​按比例分配算法

              • ​考虑优先权分配

          • ​页调入策略

            • ​何时

              • ​预先调入--预计不久之后会被访问的页，以及相邻的页

            • ​何地

              • ​从对换区调入

              • ​unix

                • 先兑换区

                • ​后文件区

          • ​页置换算法

            • ​最佳置换算法

            • ​先进先出

            • ​最近醉酒未使用

            • ​其他

              • ​简单引用为

              • ​简单Clock

              • ​改进Clock

          • ​抖动

            • ​原因

              • ​进程数量太多，平均分配的太少，频繁请求调页

            • ​预防

              • ​局部置换策略

                • ​从本进程内存范围内换页

              • ​在cpu调度程序中引入工作集算法

              • ​挂起若干进程

  • ​分段存储管理

    • ​引入原因

      • ​逻辑地址一维，不方便程序员编程

      • ​分段引入后，把逻辑地址有关联的放在一个地址空间，方便编程

      • ​解决了部分存储空间动态增长，信息共享和信息保护

    • ​优点

      • ​方便编程

      • ​分段共享

      • ​分段保护

      • ​动态链接

      • ​存储空间动态增长

    • ​段表项

      • ​段号

      • ​段长

      • ​段基址

    • ​分段与分页

      • ​联系

        • ​离散分配方式

      • ​区别

        • 页​按物理单位划分，段按逻辑单位划分

        • ​页的大小是固定的，段大小不固定

        • ​分页地址一维，分段地址二维

  • ​段页式存储管理

    • ​原理

      • ​将用户进程的逻辑空间划分成若干个段，每个段划分成若干个页。

      • ​进程以页为单位在物理地址中离散存放，每个段中被离散存放的页具有逻辑相关性。

    • ​地址变换过程

      • ​1.以段号为索引，找到段S的段表项，得到段页表的起始地址

      • ​2.分页机制分离出页号和页内偏移量

      • ​3.以段内页号为索引找到搜索页号p对应的页表项

      • ​4.根据页号找到对应的页框号

      • ​5.计算出物理地址