操作系统入门（四）存储器管理
一学期的可也算是基本上完了，不知道大家学的怎样。 应朋友之约，我来总结一下这学期学的操作系统课程，方便大家复习。
概述
存储体系
－计算机系统中存储器一般分为内存储器和辅助存储器两级 －内存可以分成系统区和用户区两部分，系统区用来存储操作系统等系统软件，用户区用于分配给用户作业使用
存储管理目的
为用户提供方便、安全和充分大的存储空间.
存储管理的任务
地址转换
逻辑地址 物理地址
内存的分配和回收
当用户作业要装入内存时，需向操作系统提出申请，操作系统按一定策略分配存储空间，若某作业执行完毕，需归还内存空间时。
内存储器的地址保护
为避免内存中若干道程序相互干扰，尤其是为了防止用户程序侵犯系统程序所在的内存区域，必须对内存采取保护措施 ，内存储器的地址保护功能一般由硬件和软件配合实现。
内存储器的共享
为提高内存利用率，需要进行内存空间的共享，包括两方面的含义： －共享内存储器资源 －共享内存储器的某些区域
内存储器的扩充
内存储器的扩充不是硬件设备上的扩充，而是用虚拟技术来实现的逻辑上的扩充，即虚拟存储概念
程序的链接和装入
程序的链接
静态链接方式
在程序运行以前，将各个目标模块及它们所需要的库函数，链接成一个完整的装入模块，又可称为可执行文件，通常不再拆开。
装入时动态链接
用户源程序经编译后所得的目标模块，在装入内存时，边装入边链接，即在装入一个目标模块时，如果发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存，进行链接。 优点：①便于修改和更新。②便于实现对目标模块的共享。
运行时动态链接
这种链接方式是将对某些模块的链接推迟到执行时才进行。在执行过程中，当发现一个被调用模块尚未调入内存时，立即由操作系统去找到该模块并装入内存，再把它链接到调用者模块上。
程序的装入
绝对装入方式
逻辑地址转换成物理地址的过程发生在程序编译或汇编时
可重定位装入方式（静态重定位）
逻辑地址转换成物理地址的过程发生在程序装入到内存时进行。
动态运行时装入方式（动态重定位）
逻辑地址转换成物理地址的过程推迟到程序真正执行时。
各种存储管理方式
单一连续分配
基本思想： 内存的用户区一次只分配给一个用户程序使用 存储保护机制： 基址寄存器和界限地址寄存器 特点： 这种管理方式的分配、去配算法非常简单，内存的利用率很低
分区分配
分区分配的存储管理是为了适应多道程序设计技术而产生的最简单的管理方式
固定分区
- 基本思想 系统预先把内存中的用户区分成若干个连续的区域，每个区域称为一个“分区”。程序装入时，根据它对内存大小的需求量，系统将按照一定的策略，把能满足它要求的一个分区分配给该程序
- 分配和回收 固定分区分配表，内容包括分区号、起始地址、长度、占用标志等.
存储保护机制
上、下限寄存器或基址、长度寄存器
优点
－优点：简单易行，适用于专用系统 －缺点：内存利用不充分，作业的大小受到分区大小的限制
可变分区
系统并不预先划分内存区间，而是在程序装入时根据程序的实际需要动态地划分内存空间。若无空闲的存储空间或无足够大的空闲存储空间供分配时，则令该程序等待。 常用的数据结构有已分分区表和空闲分区表或空闲分区链表 。
分区分配算法
首次适应算法
要求空闲分区链以地址递增的次序链接，在进行内存分配时，从链首开始顺序查找，直至找到一个能满足其大小要求的空闲分区为止
循环首次适应算法
在为程序分配内存空间时，不再每次从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找。直至找到第一个能满足要求的空闲分区
最佳适应算法
把既能满足要求、又是最小的空闲分区分配给程序
最差适应算法
每次为程序分配内存时，总是找到一个满足程序长度要求的最大空闲分区进行分配
内存分区回收操作
当进程运行完毕释放内存时，系统根据回收区的首址，从空闲分区表（链）中找到相应的插入点，进行回收，此时可能出现以下四种情况：
－回收区与插入点的前一个分区相邻接，两分区合并 －回收区与插入点的后一个分区相邻接 ，两分区合并 －回收区同时与插入点的前、后两个分区邻接 ，三分区合并 －回收区与插入点前、后两个分区都不相邻 ，单独一个分区
内存回收算法
假定进程归还的分区起始地址为S，长度为L，则： ① 归还区有下邻空闲区 如果S+L正好等于空闲区表中某个登记栏目（假定为第j栏）的起始地址，则表明归还区有一个下邻空闲区。这时只要修改第j栏登记项的内容： 起始地址=S； 第j栏长度=第j栏长度+L；
② 归还区有上邻空闲区 如果空闲区表中某个登记栏目（假定为第k栏）的“起始地址+长度”正好等于S，则表明归还区有一个上邻空闲区。这时要修改第k栏登记项的内容（起始地址不变）： 第k栏长度=第k栏长度+L；
③ 归还区既有上邻空闲区又有下邻空闲区 如果S+L正好等于空闲区表中某个登记栏目（假定为第j栏）的起始地址，同时还有某个登记栏目（假定为第k栏）的“起始地址+长度”正好等于S，这表明归还区既有一个上邻空闲区又有一个下邻空闲区。此时对空闲区表的修改如下： 第k栏长度=第k栏长度+第j栏长度+L；（第k栏起始地址不变） 第j栏状态=“空”；（将第j栏登记项删除）
④ 归还区既无上邻空闲区又无下邻空闲区 如果在检查空闲区表时，无上述三种情况出现，则表明归还区既无上邻空闲区又无下邻空闲区。这时，应该在空闲区表中查找一个状态为“空”的栏目（假定查到的是第t栏），则第t栏的内容修改如下： 第t栏起始地址=S； 第t栏长度=L； 第t栏状态=“未分配”
可变分区分配的优缺点
优点：有助于多道程序设计，提高了内存的利用率
要求硬件支持少，代价低 管理算法简单，实现容易
缺点：必须给作业分配一连续的内存区域
碎片问题严重，内存仍不能得到充分利用 不能实现对内存的扩充
覆盖技术
所谓覆盖，是指同一内存区可以被不同的程序段重复使用。
－可以相互覆盖的程序段叫做覆盖 －可共享的内存区叫做覆盖区 －把程序执行时并不要求同时装入内存的覆盖组成一组，叫覆盖段，并分配同一个内存区
交换技术
所谓交换，就是系统根据需要把内存中暂时不运行的某个(或某些)作业部分或全部移到外存，而把外存中的某个(或某些)作业移到相应的内存区，并使其投入运行
分页存储管理方式
将程序的逻辑地址空间和存储空间按相同长度为单位进行等划分。把每个程序逻辑空间分成一些大小相同的片段，叫做页面或页。把内存的存储空间也分成大小与页面相同的片段，叫做物理块或页框。分配的物理块可以连续也可以不连续。
页表
页表的作用是实现从页号到物理块号的映射 系统在内存空间设置一片区域作为页表区，系统为每个进程提供一个页表。进程页表的起始地址存放在进程PCB中。
存取控制
在页表的表项中设置一存取控制字段，用于对该存储块中的内容进行保护。
地址变换
地址变换即通过地址变换机构把逻辑地址变换成相应的物理地址，实际上是将逻辑地址中的页号，转 换为内存中的物理块号。因为页表的作用就是用于实现页号到物理块号的变换，因此，地址变换任务是借助于页表来完成的 除此以外，系统设置了一个页表寄存器PTR其中存放页表在内存的始址和页表的长度
动态地址变换
逻辑地址可以分解成：页号、页内位移量（页内地址） 物理地址可以分解成：物理块号、物理块内位移（物理块内地址）
p=逻辑地址/页面大小 d=逻辑地址-p×页面大小
地址变换过程
⑴ 根据逻辑地址计算出页号p和页内地址d， p=逻辑地址/页面大小 d=逻辑地址%页面大小 ⑵ 根据页号p查页表，得到对应块号f ⑶ 块内地址和页内地址相同，计算物理地址 物理地址=f×块大小+d （块大小等于页大小）
若页面大小为2的幂，则页号和页内地址可以直接取高位和地位部分获得，物理地址可以用块号和块内地址拼接而成
分页系统中的地址变换机构
快表
由于页表存储在内存中，所以当要按照给定的逻辑地址进行读/写时，需要两次访问内存: 第一次是根据页号访问页表，读出页表相应栏中的块号以便形成物理地址； 第二次是根据物理地址进行读/写操作。 这样比通常执行指令的速度慢一倍。为了提高存取速度，在地址变换机构中增设了一个具有并行查寻能力的特殊高速缓冲存储器，又称为“联想存储器”或“快表”
利用快表的地址变换机构
两级和多级页表
现代的大多数计算机系统都支持非常大的逻辑地址空间，此时，页表就变得非常大，要为它分配一大段连续的内存空间将变得十分困难
解决办法： ①采用离散分配方式来解决难以找到一块连续的内存空间问题； ②只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。
分段存储管理
基本思想
每个程序的地址空间按照自身的逻辑关系划分成若干段（比如主程序段、子程序段、数据段、堆栈段等）每个段都有自己的名字，通常可用一个段号来代替段名，每个段都从0开始独立编址，段内地址连续。段的长度由相应的逻辑信息组的长度决定，因而各段的长度不等。分配内存时，为每个段分配一连续的存储空间，段间地址空间可以不连续
段表
段表实现了从逻辑段到物理内存区的映射.系统为每个进程建立了一张段映射表，简称“段表”。进程的每个段在段表中占有一个表项，在其中记录了该段在内存中的起始地址（基址）和段的长度
段与页的差别
基本思想 每个程序的地址空间按照自身的逻辑关系划分成若干段（比如主程序段、子程序段、数据段、堆栈段等）每个段都有自己的名字，通常可用一个段号来代替段名，每个段都从0开始独立编址，段内地址连续。段的长度由相应的逻辑信息组的长度决定，因而各段的长度不等。分配内存时，为每个段分配一连续的存储空间，段间地址空间可以不连续 段表 段表实现了从逻辑段到物理内存区的映射.系统为每个进程建立了一张段映射表，简称“段表”。进程的每个段在段表中占有一个表项，在其中记录了该段在内存中的起始地址（基址）和段的长度
段页式
内存分成大小相同的块，每个程序地址空间按照逻辑关系分成若干段，并为每个段赋予一个段名，每段可以独立从0编址，每段按内存块大小分成页，每段分配与其页数相同的内存块，内存块可以连续也可以不连续。系统为每段建立页表记录每页对应的块，同时还为该程序建立段表记录每段对应的页表
地址变换
为了实现地址变换，配置一段表寄存器，在该寄存器中存放段表的始址和段长
在段页式存储管理方式中，执行一条指令需要三次访问内存。第一次访问段表，从中得到页表的位置，第二次访问页表，得出该页所对应的物理块号，第三次按照得到的物理地址访问内存 －为了提高地址变换速度，同样可以和分页存储管理方式和分段存储管理方式一样，设置一高速缓寄存器，利用段号和页号去检索该寄存器，得到相应的物理块号