【操作系统】存储器管理

相关文章(写的较烂):
【操作系统】处理机调度简述
【操作系统】之进程管理
【操作系统】经典的同步问题(http://www.cnblogs.com/libra-yong/p/6985526.html)

基本概念

多层结构的存储器系统

主存储器与寄存器

主存储器简称主存或内存, 用于保存程序运行时的指令和数据.

寄存器是有限存贮容量的高速存贮部件，它们可用来暂存指令、数据和地址.

通常, 处理机从指存中读出数据放入指令寄存器, 这一时间段我们称之为取指周期; 处理机从数存中读取数据放入数据寄存器, 再流入运算器, 这一时间段我们称之为执行周期.

高速缓存和磁盘缓存

高速缓冲存储器是介于寄存器和存储器之间的存储器, 主要用于备份主存中较常用的数据, 用来减少处理机对主存储器的访问次数, 提高运行效率.

磁盘缓存主要用于暂时存放频繁使用的一部分磁盘数据和信息, 以减少访问磁盘的次数.

程序在系统中若想成为可执行程序, 通常需要经历以下三个阶段:

• 编译 : 由编译程序对源程序进行编译, 形成若干个目标模块

• 链接 : 由链接程序将若干目标模块以及所需库函数连接在一起, 形成一个完成的装入模块

• 转入 : 由装入程序将装入模块装入内存

程序的链接和装入

程序的链接

用户程序经过编译后得到一组目标模块. 链接程序的功能便是将这组目标模块以及它们所需要的库函数转配成一个完整的装入模块. 在对目标模块进行装入时, 可把链接分为入下三种:

静态链接
在程序运行之前, 先将各目标模块及它们所需的库函数链接成一个完善的装配模块, 以后不再拆开.

装入时动态链接
用户源程序编译后的目标模块在转入内存时, 采用边装入边链接的方式.
在装入一个目标模块时, 若发生一个外部调用事件, 将引起装入程序去找出相应的外部目标模块, 并将它装入内存.

优点: 便于修改和更新, 便于实现对目标模块的共享.

运行时动态链接
将某些目标模块的链接推迟到程序时才执行.
在执行过程中, 当发现一个被调用模块尚未装入内存时, 立即由OS取找到该模块, 并将之装入内存, 将其链接到调用者模块上. 凡在执行过程中未被用到的目标模块, 都不会被调入内存和被链接到装入模块上, 这样不仅能加快程序的装入过程, 而且可节省大量的内存空间

程序的装入

绝对装入方式
在运行单道程序时, 可以知道程序驻留在内存中的位置, 程序经过编译后, 将产生绝对地址的目标代码.

可重定位装入方式
在多道程序环境下, 程序根据内存的具体的情况将装入到内存的适当位置.

动态运行时装入方式
此方式在的装入程序把转入模块装入内存后, 并不立即把装入模块中的逻辑地址转换为物理地址, 而是把这种地址转换推迟到程序真正要执行时才进行.

连续分配管理方式

连续分配是最早出现的一种存储器分配方式大致可分为四类:

• 单一连续分配
• 固定分区分配
• 动态分区分配
• 动态可重定位分区分配

单一连续分配

在单道程序环境下, 当时的存储器管理方式把内存分为系统区和用户区两部分, 系统区仅提供给OS使用, 它通常是放在内存的低址部分. 在用户区内存中, 仅装有一道用户程序, 即整个内存的用户空间由该程序独占.这样的存储器分配方式被称为单一连续分配方式.

固定分区分配

在多道程序环境下, 将用户空间划分为若干个固定大小的区域, 在每个分区中只装入一道作业. 这样就可以有个多个作业装入分区同时运行.

1. 划分分区方法
   • 分区大小相等
     将所有的内存分为分区大小的块
     缺点: 缺乏灵活性
   • 分区大小不等
     将内存分为较多较小的分区, 适量的中等的分区, 少量的大分区. 根据程序的大小为之分配适当的分区.
2. 内存分配
   为便于分配, 通常将分区按其大小排队, 并为之建立一张分区表. 其中各表项包括每个分区的起始地址, 大小及状态.

动态分区分配

又称为可变分区分配, 它根据实际需要, 动态地为之分配内存空间.

1. 动态分区中的数据结构
   • 空闲分区表
     在系统中设置一张空闲分区表, 用于记录每个空闲分区的情况. 每个空闲分区占一个表目, 表目中包括分区号, 分大小等原始数据项.
   • 空闲分区链
     在每个分区头尾部分别设置向前指针和向后指针, 分别指向前移分区和后一分区. 在分区头部设置一些控制分区的信息, 在分区尾部重复设置状态位和分区大小表.
2. 动态分区算法
   • 基于顺序索引的动态分区分配算法
     • 首次适应算法(First Fit)
       FF算法要求空闲分区链以地址递增的次序链接.
       在分配内存时, 从链首顺序查找大小满足的空闲分区, 按照作业大小从该分区中划分一块内存空间并分配给作业.
     • 循环首次适应算法(Next Fit)
       NF算法从上次找到的空闲分区开始查找, 直到找到一个满足的空闲从中划出一块与请求大小相等的内存空间分配个作业.该算法要求设置一起始指针(指向下一次起始查找的空闲分区), 并采用循环方式
     • 最佳适应算法(Best Fit)
       BF算法每次为作业分配内存时, 总能把满足要求, 又是最下的空闲分区分配给作业. 该算法要求所有的空闲分区按容量从小到大的顺序形成一个空闲分区链.
     • 最坏适应算法(Worst Fit)
       WF算法在扫描整个空闲分区表或空闲分区链表时, 总是挑选最大的空闲区, 从中分割一部分空间个作业.
   • 基于索引搜索的的动态分区分配算法
     • 快速适应算法
     • 伙伴系统
     • 哈希算法
3. 分区分配操作

   • 分配内存
     设请求的分区大小为u.size, 表中每个空闲分区的大小可表示为m.size-u.size<=size(size是事先规定的不再切割的剩余分区的大小).说明多余部分太小, 可不再切割, 将整个分区分配给请求者. 否则, 便从该分区中按请求的大小分出一块内存空间分配出去. 然后将分配区的首址返回给调用者.

   • 回收内存
     当进程运行完毕释放内存时, 系统根据回收区的首址, 从空闲区链表中找到相应的插入点, 此时可能出现以下四种情况之一:
     • 回收区与插入点的前一个空闲分区F1相邻, 此时应将回收区与插入点的前一分区合并, 不必为回收分区分配新表项, 只需修改其前一分区F1即可.
     • 回收分区与插入点的后一空闲分区F2相邻, 此时也可将两分区合并, 形成新的空闲分区, 但用回收区的首址作为新空闲区的首址, 大小为两者之和.
     • 回收区同时与插入点的前后连个分区邻接, 此时将三个分区合并, 使用F1的表项和F1的首址, 取消F2的表项, 大小为三者之和.
     • 回收区既不与F1邻接, 又不与F2邻接. 此时回收区建立一个新表项, 填写回收区的首址和大小, 并根据其首址插入到空闲链中的适当位置.

动态可重定位分区分配

通过移动内存中作业的位置, 把原来多个分散的小分区拼接成一个大分区的方法称为拼接或紧凑.
在动态运行时装入方式中, 作业转入内存后任然是(相对)逻辑地址, 在程序指令真正要执行时才转换为绝对地址. 地址变换机构将相对地址转换为绝对地址, 地址变换机构在进程执行期间, 随着对每条指令或数据的的方位自动进行的, 称为动态重定位

为了地址的转换不影响到指令的执行速度, 在地址变换机构中增设了一个重定位寄存器, 用来存储程序或数据在内存中的起始地址.

与连续分配管理方式对应的是非连续(离散)管理方式, 它们包括:

• 分页管理方式
• 分段管理方式
• 段页式管理方式

对换

对换
: 把内存中暂时不能运行的进程或者暂时不用的程序和数据换出到外存上, 以便腾出足够的内存空间, 再把已具备运行条件的进程或进程所需的程序和数据还如内存.

对换分为整体对换和页面(分段)对换.

• 整体对换
  处理机的中级调度实际就是存储器的对换功能, 在中级调度中对换是以进程为单位的, 故称之为进程对换或*整体对换**
• 页面(分段)对换
  该对换是以进程的一个页面或分段为单位进行的.

1. 对换空间的数据结构形式与动态分区分配方式相似, 在空闲分区表的每个表目中包含两项: 对换区的首址和其大小, 分别用盘块号和盘块数表示.
2. 对换空间的内存分配与回收与动态分区分配方式的相同.

进程的换出

将进程中的某些进程调出至兑换区, 以便腾出内存空间

1. 选择被换出的进程.
2. 进程换出
   

进程的换入

系统应定时地查看所有进程的状态，从中找出“就绪”状态但已换出的进程，将其中换出时间(换出到磁盘上)最久的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止

分页存储管理方式

该方式中将用户程序的地址空间分为若干个固定大小的区域, 称为页或页面, 将内存分为若干个大小的物理块或页框, 页和块大小相同, 这样就可以将用户的任意页放入任一物理块了, 实现离散分配.

页面: 分页存储管理将进程的逻辑地址空间分成若干页, 并为各页编号(0页, 1页, ...); 把内存的物理地址空间分为若干块(0#块, 1#块, ...);通常页和块的大小相同.

在进程分配内存时, 以块为单位, 将进程中的若干个页分别装入到多个可以不相邻接的物理块中.
进程的最后一页经常装不满一块, 块中剩余的空间又无法利用, 我们称之为页内碎片.

页面大小: 因为页内碎片的存在, 为了提高块的利用率, 页面的大小选择应适中, 页面大小为2的幂, 通常为1KB~8KB.

分页地址中的地址结构结构

P(31-12)	W(11-0)

分为页号P和偏移量W. 页号P有20个二进制位, 通过不同的0,1组合方式可以指向1M(即\(2^{20}\))个页. 偏移量W表示页内地址, 它有12个二进制位, 通过组合可以指向4K(即\(2^{12}\))个页内地址(存储单元), 即4KB, 也是每页的大小.

若给定逻辑空间地址A, 页面大小为L, 则页号P和页内地址W可求得:
\(P=INT[\frac{A}{L}]\), INT为整除函数
\(W=[A] MOD L\), MOD为取余函数

页表: 是一个页面映射表, 用来帮助进程地址空间的页找到内存中对应的物理块.
在进程空间的所有页, 依次在页表中有一个页表项, 其记录了相应页在内存中的物理块号.

地址变换机构

地址变换机构的功能便是将进程空间中的逻辑地址转变为内存空间中的物理地址.

具有快表的地址变换机构
快表: 实质为一个高速缓冲存储器.

分段存储管理方式

分段存储管理方式将用户的程序地址空间氛围若干个大小不同的段, 每段定义一组相对完整的信息. 段在内存中可以不相互邻接(离散分配). 存储器分配时以段为单位.

分段地址中的地址结构

段号	段内地址

该地址同分页存储管理方式类似, 分为段号P和段内地址W.
段号P可以指向64K个段(\(2^{16}\)), 每个段的最大长度为W为64KB(\(2^{16}\)).

段表: 每个段在表中占有一个表项, 其中记录了该段在内存中的段的长度和起始地址(基址).

地址变换机构

分页和分段的区别

1. 页是信息的物理单位, 段是信息的逻辑单位
2. 页的大小是固定的, 段的长度由程序决定
3. 分页的进程地址空间是一维的, 分段的进程地址空间是二维的

段页式存储管理方式

此方式将用户的程序氛围若干个段,并为每个段赋予段名, 再在将若干个段分为若干个页.

段页式的地址结构

段号(S)	段内页号P	页内地址W

分为段号S, 段内页号P, 页内地址W

段表和页表: 段表包括页表始址和页表长度等其他信息

地址表换过程