内存管理

前段时间看了进程管理，觉得对编程简直大有裨益，至少对于多线程编程方面，对系统的进程管理有了非常深刻的理解，看来还是要多学习。今天开始学习内存管理这一节，看了一遍没怎么看懂，于是在这里写下笔记，慢慢咀嚼，直到看明白。

1. 从源程序变成在内存中执行的程序

• 编译
  将源代码编译成若干个目标模块
• 链接
  将目标模块和需要的库函数链接在一起，形成完成的装入模块
• 装入
  由装入程序将装入模块装入内存执行

2. 程序链接三种方式

• 静态链接
  程序运行之前，将目标模块和库函数链接成完整的可执行程序
• 装入时动态链接
  在装入内存的时候，边装入边对目标模块和库函数进行链接
• 运行时候动态链接
  在程序执行的时候需要该目标模块的时候，才对其进行链接

3. 程序装入的时候的三种方式

• 绝对装入
  编译程序产生的是绝对地址的目标代码，绝对装入程序按照绝对地址，将程序和数据装入内存，程序的逻辑地址和实际内存的地址完全相同，所以不需要进行地址变换，只适用于单道程序环境。
• 可重定位装入
  多个目标模块的起始地址都是从0开始，程序中其它地址都是相对于起始地址的，根据内存当前情况，将装入模块装入到内存的适当位置，所以必须分配作业要求的全部内存空间。装入的时候对目标程序的指令和数据的修改过程称为重定位，地址变换是在装入时候一次性完成的，因此称为静态重定位。
• 动态运行时装入
  装入程序在把装入模块装入内存后，不把相对地址转换为绝对地址，直到程序真正执行的时候完成转换，所以装入内存后的所有地址均为相对地址，需要硬件重定位寄存器的支持。

4. 逻辑地址空间
   每个目标模块都是从0开始编址，称为目标模块的相对地址也称为逻辑地址，链接程序将依次将各个模块相对地址构成统一的从0开始编址的逻辑地址空间，不同进程可以有相同的逻辑地址，因为这些地址在装入内存的时候可以映射到主存的不同位置。

5. 物理地址空间
   内存中物理单元的集合，地址转换的最终地址，进程在运行的时候指令和数据都要通过物理地址从主存中存取。地址重定位就是将逻辑地址转换成物理地址。

6. 内存保护

• CPU设置一对上，下限寄存器
  存放用户作业在主存的下限和上线地址，CPU要访问一个地址的时候，分别与这两个地址进行比较，判断是否越界。
• 重定位寄存器（基址寄存器）和界地址寄存器（限长寄存器）
  首先逻辑地址和界地址寄存器进行比较，如果没有发生越界，加上重定位寄存器的值后映射成物理地址，送交内存单元。所以界地址寄存器含有逻辑地址的最大值。

7. 覆盖
   将用户空间分成一个固定区和几个覆盖区，程序中经常活跃的部分放在固定区，其余部分，将要访问的段放入覆盖区，其它段放在外存中，在需要调用前，系统将其掉入覆盖区，替换覆盖区原有的段。不在覆盖区的段会常驻内存。

8. 交换
   将处于等待状态的程序从内存移到辅存，换出。把准备好竞争CPU运行的程序从辅存移到内存，换入。内存管理器的交换过程速度足够快，总有进程在内存中可以执行。
   交换技术在不同进程或者作业中进行，覆盖用于同一个进程或者程序中。覆盖技术要求给出程序段之间的覆盖结构，对于主存无法存放用户程序的矛盾，是通过虚拟内存技术来解决的。

连续分配管理方式

给用户程序分配一个连续的内存空间。

这块将是非常关键而且重要的部分了，涉及了单一连续分配，固定区分配和动态分区分配。

1. 单一连续分配
   内存分为系统区和用户区，因为只有一道程序，所以无需内存保护，无外部碎片，可以采用覆盖技术，只能用于单用户单任务的操作系统，有内部碎片，存储器利用率低。

2. 固定分区分配
   将用户内存空间分为多个固定大小的区域，每个分区只装入一道作业，有空闲分区的时候再从外存的后备作业队列中，选择适当大小的作业装入该分区。

• 分区大小相等
• 分区大小不等

便于内存分配，将分区按照大小排队，建立一张分区说明表。回忆之。包含每个分区的起始地址，大小和状态。
两个问题，程序可能太大而放不进任何一个分区里，这时需要使用覆盖技术来使用内存空间。内部碎片，当程序小于固定分区大小的时候，也占用了一个完整的内存分区空间。

3. 动态分区分配
   可变分区分配，动态划分内存的分区方法，根据进程的大小动态建立分区，使得分区大小正好适合进程的需要。系统中的分区大小和数目是可以变化的。
   在系统运行过程中，会产生较多的小的内存块，称为外部碎片。克服外部碎片可以通过紧凑技术解决，操作系统不时的对进程进行移动和整理，需要动态重定位寄存器的支持。
   动态分区的分配策略，是指将内存中的空闲块如何分配给进程使用：

• 首次适应算法
  空闲分区按照地址递增的顺序，分配内存的时候按照顺序查找，找到第一个能满足要求的分区
• 最佳适应算法
  空闲分区按照容量递增排序，找到第一个能够满足要求的分区
• 最坏适应算法
  空闲分区按照容量递减排序，找到第一个能够满足要求的分区
• 邻近适应算法
  分配内存的时候从上次查找结束的位置开始继续寻找，循环首次适应算法

首次适应算法会使得在内存的低地址处出现很多小的空闲分区（因为一般在内存低地址处分配空间），每次分配查找的时候，要经过这些分区，增加了查找的开销。
邻近适应算法会在内存的末尾分配空间，内存在前面使用后释放，不会参与分配，然后分裂成小碎片，通常比首次适应算法的结果要差。
最佳适应算法以容量递增的形式分配分区，会留下很小的难以利用的内存块，因此会产生最多的外部碎片。
最坏适应算法以容量递减的形式分配分区，会把最大的连续内存划分开，会很快导致没有可用的大的内存块。

内部碎片：存在于固定分区中，分区内部有空间浪费，称为内部碎片。
外部碎片：指在所有分区外的存储空间会变成越来越多的碎片，存在于动态分区分配中，各个进程将内存区域分配后，内存区域会残留的小的内存块。

非连续分配管理方式

允许一个程序分散的装入到不相邻的内存分区中，需要额外的空间去存储它们分散区域的索引，非连续分配方式的存储密度小于连续存储方式。

包括分页存储管理方式和分段存储管理方式，其中分页存储管理方式分为基本分页存储管理方式和请求分页存储管理方式。

1. 基本分页存储管理方式
   把主存空间划分为大小相等而且固定的比较小的块，作为主存的基本单位，每个进程也以块为单位进行划分，进程在执行的时候，以块为单位逐个申请主存中的块空间。
   这样的分配方法不会产生外部碎片，进程只会为最后一个不完整的块申请一个主存块空间的时候，产生主存碎片，不过这个碎片相对于进程来讲也是非常小的，每个进程平均产生半个块大小的内部碎片，页内碎片。
   • 页面
     进程的块称之为页。
     内存中的块称之为页框，也称为页帧。
     外存中也以同样的单位进行划分，称为块。
     进程在执行时候需要申请主存空间，就是为每个页面分配主存中可用的页框，所以页和页框一一对应。
     页面大小就是说进程分成的基本单位页的大小，应该是2的整数幂。页面大小适中，太小会导致页面数过多，页表就太长，占用大量内存，增加硬件地址转换的开销，降低页面换入/换出效率。页面过大导致页内碎片增大，降低内存的利用率。
   • 地址结构
     前一部分为页号12-31位，所以地址空间最多有2^20页，后一部分是页内偏移量W，12位，0-11位，所以每页大小为4KB。地址结构决定了虚拟内存的寻址空间有多大。
     其实整个页面就是地址的集合，所以页面便移量也就确定了一定位置的物理地址。从而确定了从逻辑地址转换到物理地址的一个位置。

• 页表
  在内存中找到进程的每个页面所对应的物理块，系统为每个进程建立了一个页表。记录页面在内存中对应的物理块号，页面存放在内存中。
  页表由页表项组成，页表项第一部分是进程的页号，第二部分是物理内存中的块号，该块号和地址的第二部分页内偏移量共同组成物理地址。
  页表的作用是实现从页号到物理块号的地址映射。

2. 基本地址变换机构
   页表长度指的是一共有多少页M。
   页表项长度指的是每一页表项占多大的内存空间。
   页面大小是指每一页占多大的内存空间L。
   所以地址变换机构将逻辑地址转换成内存的物理地址的一般步骤如下：

• 从逻辑地址A计算页号P和页内偏移量，P=A/L，W=A%L。L是页面大小。
• 比较页号P和页表长度M，P>=M，则产生越界中断，否则继续执行。
• 计算对应页号的页表项地址，从该页表项中提取物理块号。对应的页表项地址=P*页表项长度+F(页表起始地址F)，索引到该页表项后，取得物理块号b
• 计算出内存中物理地址E＝b*L+W,因为进程中的页面和内存中的页面大小都是一致的，一一对应。所以通过物理块号乘以页面大小，加上页面便移量就可以找到对应的物理地址。
  页式管理只要给出一个整数就能确定对应的物理地址，因为页面大小L是固定的，页式管理中地址空间是一维的。
• 页表项大小的确定
  页表项是为了找到相应页在内存中的位置。32位的逻辑地址空间(4GB)，一页4KB，那么地址空间内一共可以有1M页面，所以至少需要20位来表示所有页面，所以页表项大小至少有3B(20/8)，为了保证页表项能够指向所有页面，页表项的大小应该大于3B，当然可以选择更大的页表项让一个页面正好容下整个页表项以方便存储，如果是4B，那么一页存储1024个页表项。一个页表是由页表项组成的，但是有多少页表项是由有多少页面来决定的，多少页面又是由多少进程来决定的。

3. 具有快表的地址变换机构
   如果页表全部放在内存中，则存取一个数据或一条指令需要访问两次内存：第一次试访问页表，找到物理地址，然后通过物理地址存取数据和指令。
   在地址变换机构中增设了一个具有并行查找能力的高速缓冲存储器－快表，又称为联想寄存器TLB，用来存放当前访问的若干页表项，加速地址变换的过程，主存中页表称为慢表。
   具有快表的分页机制中，地址的变换过程：

• CPU给出逻辑地址后，由硬件进行地址转换将页号送入高速缓存寄存器中，将页号和快表中的所有页号进行比较。
• 如果找到匹配的页号，那么直接从中取出该页对应的页框号，也就是物理块号，算出物理地址，存取数据仅需要访问一次主存。
• 没有找到，那么访问主存中的页表，读出页表项后放入快表，快表满了的话，按照一定的算法对旧的页表进行替换。

4. 两级页表

• 对页表以及相应过程的进一步理解
  页面就是将进程以块为单位进行划分，所以比如40M的进程，页表项就是40MB/4KB*4B，4KB是页面大小，也就是每一块的大小，所以需要1万个页面，乘以4B页表项大小，也就是页表的大小。如果将所有的页表项内容保存在内存中，需要10个内存页框来保存整个页表，因为每个页面框可以保存1024个页表项，4KB/4B。
  页框也是将主存进行同样的划分，所以对于32位的逻辑地址空间，页面大小4KB，页表项4B，实现进程对整个逻辑地址空间进行映射，则每个进程需要2^20，100万个页表项，所以每个进程仅页表这一项就要4MB的主存空间，并且需要100万*4B/4KB=1024页，也就是说页表需要1024页才能存储完。

但是实际执行的时候只需要几十个页面进入内存页框就可以运行，但是如果要将10个页面的页表都放入内存，却只用几十个页面，不到一个页面的页表，这样就极大的降低了内存利用率。并且大部分情况下，映射需要的页表项都在页表的同一个页面中。
使用层次结构的页表：将页表的10页空间也进行地址映射，建立上一级页表，存储页表的映射关系，10个页面进行映射只需要10个页表项，而上一级页表仅仅需要1页就足够了，1页可以存储1024个页表项。
所以需要一张索引表来寻找对应的表，并且不用把所有的页表都调入内存，只有需要的时候才调入。构造一个页表的页表，就是二级页表。顶级页表最多只能由1个页面，也就是1024个页表项，对应1024个页面，占用的地址位数是10位，log2(1024)=10
所以对于一个32位的逻辑地址空间，32－10-12(页内偏移地址)=10位，所以二级页表大小也在一页之内。
所以假设第一级页表有10个页表项，则说明页表有10个页面，如果第一级页表有1024个页表项，说明页表有1024个页面，也就是32位逻辑空间最大的页表项了。然后第一级页表的页表项分别索引第二级页表，假设第一个页表项下的第二级页表，这就是说明索引了原来第一个页表页面的所有页表项。所以10个页面的页表恰好被整个二级页表索引完全。第一级页表大小在一页之内，第二级页表大小也在一页之内。
换一种说法就是第一级页表的页表项表示你想索引哪一个页面的页表，第二级页表的页表项就是表明你想索引的页面的页表的所有能索引到物理块的页表项都在这里了。

5. 基本分段存储管理方式
   分段管理方式是考虑用户和程序员，以满足方便编程，信息保护和共享，动态增长及动态链接等多方面的需要。

• 分段
  段式管理方式按照用户进程中的自然段划分逻辑空间，段内要求连续，段间不要求连续，整个作业的地址空间是二维的，这里的意思指的是一个进程可以分为好几个段的逻辑地址。
  逻辑地址由段号S和段内偏移量W两部分组成，S有16位，因此一个作业最多有65536个段，W有16位，最大段长为64KB。
  段式系统中，段号和段内偏移量必须由用户显示提供，高级程序设计语言中，工作由编译程序完成。
• 段表
  每一个段表项对应进程的一个段，段表项记录段号，段长以及段在内存中的起始地址。执行中的进程可以通过查找段表，找到每个段对应的内存区。段表用于实现从逻辑段到物理内存区的映射。
• 地址变换机构
  段表寄存器：用于存放段表起始地址F和段表长度M。
  • 从逻辑地址A取出前几位是段号S，后几位是段内偏移量W，段式管理一般以二进制给出逻辑地址。
  • 比较段号S和段表长度M，如果S>=M，产生越界中断，否则继续执行。
  • 求出段号S对应的段表项的地址=段表起始地址F+段号S*段表项长度，然后取出段长C，如果段内偏移量>=C，产生越界中断，否则继续执行，取出段在内存的起始地址b，从这里可以看出其实段表只有两项，就是段长和段在内存中的起始地址。段号其实可以省略。
  • 计算物理内存地址E=b+W
• 段的共享和保护
  段的共享是通过两个作业的段表中相应表项指向被共享的段的同一个物理副本来实现的，纯代码或者可重入代码和不能修改的数据是可以共享的，可修改的代码和数据不能共享。
  分段管理的保护由两种：
  • 存取控制保护
  • 地址越界保护
    段表寄存器中段表长度和逻辑地址中的段号进行比较。
    另外一个是段表项中的段长和逻辑地址中的段内位移进行比较。

段号和段内偏移一定要显示给出，因此分段管理的地址空间是二维的。

6. 段页式管理方式
   作业的地址空间首先被分成了若干个逻辑段，每段都有自己的段号，然后将每一段分成若干个大小固定的页，对内存空间的管理和分页存储管理一样，将其分为若干个和页面大小相同的存储块，对内存的分配以存储块为单位。

• 地址变换
  每个进程一个段表，每个分段一张页表，段表表项中至少包括段号，页表长度和页表起始地址，页表表项中至少包括页号和块号。
  系统中还有段表寄存器，作业的段表起始地址和段表长度，还有一个页表寄存器。作用有两个，一是段表或者页表中寻址，二是判断是否越界。在一个进程中，段表只有一个，页表有多个。
  地址变换，通过段表查到页表起始地址，通过页表找到页帧号，最后形成物理地址。一次访问要访问三次主存，可以添加快表来加快查找速度，关键字由段号，页号组成，值是对应的页帧号和保护码。
  段页式管理的地址空间是二维的。