操作系统 内存管理

操作系统 内存管理

Posted by julyerr on February 24, 2018

内存管理涉及内容较多,本文从目标程序链接,装载,内存分配和虚拟存储等方面进行总结。

程序装入

上图为用户程序到可执行程序流程图

内存地址

  • 物理地址 实际在内存条中的地址编号
  • 逻辑地址 用户程序编译为目标模块之后,对模块内部程序或者数据等编好的地址

程序链接

将用户编译后的目标代码和需要的库函数链接在一起,生成一个可以运行的装入模块,通常有两种方式

  • 静态链接(static link) 将多个目标模块链接成一个完成的模块,确定下模块中每条指令的逻辑地址
  • 动态链接(dynamic link) 生成的装入模块可以包含对外部模块的引用,在装入模块装入或者运行时才发生链接,确定下代码的逻辑地址

静态和动态链接比较
静态链接

  • 代码装载速度快,执行速度快;
  • 静态链接库被多个应用程序使用,会发生多次装载,浪费内存
  • 静态库改变之后,程序需要重新编译

动态链接

  • 动态链接库被多应用程序使用,只会发生一次加载;
  • 动态库升级方便

装入内存方式
装入模块需要加载到内存中才能运行

  • 绝对装入 单道程序环境中,可以确定程序驻留在内存的位置,编译生成目标代码采用绝地地址进行编址。
  • 可重定位装入 逻辑地址和物理地址的转换在装入的时候一次完成
  • 动态运行装入 地址转换过程在程序执行期间发生,需要硬件支持(定位寄存器)。

内存划分和分配

内存碎片

  • 内碎片 分区中未被利用的空间
  • 外碎片 难以利用的空闲分区

内存划分两种方式

  • 静态划分 一旦划分完毕,分区大小和数量不再改变,通常有分区和分页两种方式。 特点:易于实现,但是容易产生较多内碎片,造成浪费。
  • 动态划分 根据程序需求和划分策略动态创建分区。针对大于程序需求的分区,将该分区分割成两个分区,其中一个分区为要求的大小并标记为“占用”,而另一个分区为余下部分并标记为“空闲”;释放过程需要将相邻空闲分区合并成一个大的空闲分区。

常见的动态内存划分方式

  • 首次适应算法 从内存的某一端开始查找,选择一个超过进程申请大小的空闲分区。较大的空闲分区可以被保留在内存高端,随着低端分区不断划分会产生较多小分区,每次分配时查找时间开销便会增大。
  • 下次适应算法 从上次分配位置之后进行查找,选择大小足够的空闲分区。空间分区分布相对均匀,但较大空闲分区不易保留。
  • 最佳适应算法 将所有的空闲分区按照大小从小到大排序在空闲分区表中,从表头选择满足申请需求且长度最小的空闲分区。容易形成较多外碎片,较大的空闲分区可以被保留。
  • 最差适应算法 将所有的空闲分区按照大小从大到小排序在空闲分区表中,从表头选择第一个满足进程需求的分区。不容易留下小的空闲分区,较大的空闲分区不容易被保留。

伙伴系统

静态划分方式容易造成内碎片的空间浪费,动态划分在分配和回收处理中系统开销较大;伙伴系统是两种方式的一种折衷方案。
伙伴系统中已经分配和空闲分区大小都是2^k大小(由于分配策略导致的),并且同样大小的分区通过双向链表串起来。
分配过程
当需要为进程分配一个长度为n 的存储空间时:

  • 首先计算一个i 值,使 2^(i-1)<n≤2^i,然后在空闲分区大小为2^i的空闲分区链表中查找。
  • 若找到,即把该空闲分区分配给进程;否则,表明长度为2^i的空闲分区已经耗尽,则在分区大小为2^(i+1)的空闲分区链表中寻找。
  • 若存在 2^(i+1)的一个空闲分区,则把该空闲分区分为相等的两个分区,这两个分区称为一对伙伴,其中的一个分区用于分配,而把另一个加入分区大小为2^i的空闲分区链表中。
  • 若大小为2^(i+1)的空闲分区也不存在,则需要查找大小为2^(i+2)的空闲分区,进行类似的处理。

回收过程
回收过程同样可能经过多次合并操作,如回收大小为2^i的空闲分区时,若事先已存在2^i的空闲分区时,则应将其与伙伴分区合并为大小为2^i+1的空闲分区,若事先已存在2^i+1的空闲分区时,又应继续与其伙伴分区合并为大小为2^i+2的空闲分区,依此类推。

内存管理方面的技术支持

内存紧缩 将各个占用分区向内存一端移动,然后将各个空闲分区合并成为一个空闲分区。 覆盖技术 将程序必要部分(常用功能)的代码和数据常驻内存;可选部分(不常用功能)平时存放在外存(覆盖文件)中,在需要时才装入内存。 交换技术 将暂时不能执行的程序(进程)送到外存中,从而获得空闲内存空间来装入新程序(进程)。

页式存储管理

将程序的逻辑地址空间划分为固定大小的页(page),而物理内存划分为同样大小的页框(page frame)。 页式存储地址结构如果所示,前一部分表示页号,后一部分表示页内地址。
操作系统为支持多进程,需要为每个进程记录已经分配的页面,每个进程也有一个页表记录逻辑页面顺序和物理页面的对应关系,如下图所示:

页式地址转换 CPU中的内存管理单元(MMU)按逻辑页号通过查进程页表得到物理页框号,将物理页框号与页内地址相加形成物理地址。上述处理过程中需要访问两次内存,时间开销比较大;为缩短查找时间,通常将页表存储在CPU内部的关联存储器(快表);在CPU给出有效地址后,由地址变换机构自动将页号送入快表;如果存在相匹配的页号,直接读出物理页号即可;不存在,需要重新访问主存并且更新块表内容。

段式存储管理

将程序的地址空间划分为若干个段(segment),例如代码段、数据段、共享段等 段地址结构如上图所示
段式管理地址转换 访问内存的时候根据段号和段表项的长度计算当前访问段在段表中的位置,然后访问段表,得到该段的物理地址,根据该物理地址以及段内偏移量就可以得到需要访问的内存。由于也是两次内存访问,所以分段管理中同样引入了联想寄存器。

页式和段式存储管理比较

  • 页是信息的物理单位,是出于系统内存利用率的角度提出的离散分配机制;段是信息的逻辑单位,每个段含有一组意义完整的信息,是出于用户角度提出的内存管理机制。
  • 页的大小是固定的,由系统决定;段的大小是不确定的,由用户决定。
  • 页地址空间是一维的,段地址空间是二维的。

段页式存储管理

将用户程序分为若干个段,然后再把每个段分成若干个页,并且为每一个段赋予一个段名称。 系统中设置了一个段表寄存器,存放段表的起始地址和段表的长度。地址变换时,根据给定的段号(还需要将段号和寄存器中的段表长度进行比较防止越界)以及寄存器中的段表起始地址,就可以得到该段对应的段表项,从段表项中得到该段对应的页表的起始地址,然后利用逻辑地址中的段内页号从页表中找到页表项,从该页表项中的物理块地址以及逻辑地址中的页内地址拼接出物理地址,最后用这个物理地址访问得到所需数据。由于访问一个数据需要三次内存访问,所以段页式管理中也引入了高速缓冲寄存器。


虚拟内存

通过系统提供缺页/段中断功能和交换技术,动态装入进程的程序代码和数据到内存运行。 下图较为全面的描述了地址转换过程中可能出现的情况

页面置换算法 下面内容摘抄自1,原作者总结不错

  • 最优页面置换算法
    只具有理论意义的算法,用来评价其他页面置换算法。置换策略是将当前页面中在未来最长时间内不会被访问的页置换出去。
  • 先进先出置换算法
    由操作系统维护一个所有当前在内存中的页面的链表,最新进入的页面放在表尾,最早进入的页面放在表头;当发生缺页中断时,淘汰表头的页面并将新调入的页面追加到表尾。简单粗暴的一种置换算法,没有考虑页面访问频率信息。
  • 最近最少使用算法LRU
    算法赋予每个页面一个访问字段,用来记录上次页面被访问到现在所经历的时间t,每次置换的时候把t值最大的页面置换出去(实现方面可以采用寄存器或者栈的方式实现)。
  • 时钟置换算法(也被称为最近未使用算法NRU)
    页面设置一个访问位,页面被访问的时候访问位设置为1;并将所有页面保存在一个循环队列中,表针指向最老的页面。页面置换的时候,如果当前指针所指页面访问为为0,那么置换,否则将其置为0,循环直到遇到一个访问为位0的页面。
  • 改进型Clock算法
    在Clock算法的基础上添加一个修改位,替换时根据访问位和修改位综合判断。优先替换访问位和修改位都是0的页面,其次是访问位为0修改位为1的页面。
  • 最少使用算法LFU
    淘汰一段时间内,使用次数最少的页面。

虚拟内存一定程度上解决了内存不足的情况,但是也是以牺牲性能为代价的

  • 虚存的管理需要建立很多数据结构,占用额外内存;
  • 虚拟地址到物理地址的转换,增加了指令执行时间;
  • 页式的换入换出需要磁盘I/O,耗费时间.

参考资料