导图社区 存储管理
操作系统的存储管理知识梳理，存储管理的目的，是充分利用内存，尽可能方便用户使用，解决程序空间大于实际内存空间的问题。四大功能讲解。覆盖和交换，覆盖技术，交换技术。
操作系统第一章知识梳理
社区模板帮助中心，点此进入>>
项目时间管理6大步骤
项目管理的五个步骤
安全教育的重要性
电商部人员工作结构
个人日常活动安排思维导图
暮尚正常运转导图
产品经理如何做好项目管理
西游记主要人物性格分析
车队管理
17种头脑风暴法
存储管理
概述
存储的重要意义及与操作系统的关系
存储器是计算机系统的重要管理资源。
任何程序和数据以及各种控制用的数据结构都必须占用一定的存储空间， 故存储管理直接影响着系统的性能。
操作系统的任务之一是尽可能地方便用户使用存储器， 以及提高主存储器的利用率
操作系统负责协调各存储器的使用
存储组织和层次结构
内存
含义：由存储单元（字节或字）组成的一维连续的地址空间
功能：存放当前正在运行程序的代码及数据，是程序中指令本身地址所指的、亦即程序计数器所指的存储器
分类： 系统区：用于存放操作系统 用户区：用于装入并存放用户程序和数据。
使用技术分类
全部装载至内存才能执行
程序的载入和链接 连续分配存储管理 分页式存储管理 分段式存储管理 段页式存储管理
程序的编译、链接与装入
静态链接 装入时动态链接 运行时动态链接
装入程序（程序的名空间、地址空间及存储空间）
①绝对装入——不适合多道程序设计 ②静态装入——地址静态再（重）定位 ③动态装入——地址动态再（重）定位
静态分配和静态再定位
程序中列出各个需要重定位的地址单元和相对地址值。当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换（一般在装入内存时由软件完成）。即装入时根据所定位的内存地址去修改每个重定位地址项，添加相应偏移量。 优：不需硬件支持，可以装入有限多道程序。 缺：一个程序通常需要占用连续的内存空间，程序装入内存后不能移动。
动态分配和动态再定位
在程序执行过程中，占用的存储空间大小与位置均是可变的。程序中虚拟内存地址，装入和执行时通过硬件地址变换机构，完成虚拟地址到实际内存地址的变换。 优点：1. OS可以将一个程序分散存放于不连续的内存空间，可以移动程序，有利用实现共享。 2. 能够支持程序执行中产生的地址引用，如指针变量（而不仅是生成可执行文件时的地址引用）。 缺点：1. 需要硬件支持（通常是CPU），OS实现较复杂。2. 它是虚拟存储的基础。
地址变换(地址再定位,地址映射)
名空间——程序 逻辑空间——逻辑地址（相对地址，虚地址） 存储空间——物理地址（绝对地址，实地址） 地址映射
逻辑地址（相对地址，虚地址）：用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式。 其首地址为0，其余指令中的地址都相对于首地址来编址。不能用逻辑地址在内存中读取信息。 物理地址（绝对地址，实地址）：内存中存储单元的地址。物理地址可直接寻址。 地址映射：将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址。 当程序装入内存时, 操作系统要为该程序分配一个合适的内存空间，由于程序的逻辑地址与分配到内存物理地址不一致, 而CPU执行指令时，是按物理地址进行的，所以要进行地址转换。
源程序—编译连接——>逻辑地址空间——地址映射——>物理地址空间
部分装载至内存即可执行
虚拟内存技术
存储管理机构要解决的问题
存储分配问题。 重点是研究存储共享和各种分配算法。 地址再定位问题。 研究各种地址变换机构， 以及静态和动态再定位方法。 存储共享问题。 研究多个进程如何共享内存。 存储保护问题。 研究保护各类程序、 数据区的方法。 存储扩充问题。 主要研究虚拟存储器问题及其各种调度算法。
存储管理的功能
存储分配和回收：分配和回收算法及相应数据结构。
存储共享和保护：代码和数据共享 地址空间访问权限（读、写、执行）
内存共享：两个或多个进程共用内存中相同区域 目的：节省内存空间，提高内存利用率，实现进程通信（数据共享） 共享内容：代码共享（要求代码为纯代码）数据共享
保护目的： 为多个程序共享内存提供保障，使在内存中的各道程序，只能访问它自己的区域，避免各道程序间相互干扰，特别是当一道程序发生错误时，不致于影响其他程序的运行。 通常由硬件完成保护功能，由软件辅助实现。
保护系统程序区不被用户侵犯（有意或无意的） 不允许用户程序读写不属于自己地址空间的数据（系统区地址空间，其他用户程序的地址空间）
保护过程
防止地址越界（ 每个进程都有自己独立的进程空间，如果一个进程在运行时所产生的地址在其地址空间之外，则发生地址越界。）
基址<=被访问地址<=基址+界限 上界<=被访问地址<=下界
防止操作越权（共享存储区域的保护 对于允许多个进程共享的存储区域，每个进程都有自己的访问权限。如果一个进程对共享区域的访问违反了权限规定，则发生操作越权，即读写保护。）
地址变换（地址再定位、地址映射）： 可执行文件生成中的链接技术 程序加载(装入)时的重定位技术 进程运行时硬件和软件的地址变换技术和机构
存储器扩充：存储器的逻辑组织和物理组织
由应用程序控制：覆盖
由OS控制：交换（整个进程空间），虚拟存储的请求调入和预调入（部分进程空间）
早期存储管理
单一连续分配
单用户系统在一段时间内，只有一个进程在内存 内存分为两个区域，一个供操作系统使用，一个供用户使用。 应用程序装入到用户区，可使用用户区全部空间。
优点：内存分配管理十分简单，适用于单用户、单任务的OS 缺点内存利用率低。 对要求内存空间少的程序，造成内存浪费； 程序全部装入，很少使用的程序部分也占用内存。
分区分配
系统把内存用户区划分为若干分区，分区大小可以相等，也可以不等。每个进程占据一个分区。
分区方式： 固定分区 可变分区 再定位分区 多重分区
固定分区 预先把可分配的主存储器空间分割成若干个连续区域，称为一个分区。每个分区的大小可以相同也可以不同，但分区大小固定不变，每个分区装一个且只能装一个作业。存储分配：如果有一个空闲区, 则分配给进程。 分区大小相等：只适合于多个相同程序的并发执行（处理多个类型相同的对象）。 分区大小不等：多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。
优点：易于实现，开销小。 缺点：内碎片造成浪费。分区总数固定，限制了并发执行的程序数目。
内存分配表
固定分区进程队列 由于固定分区的大小一经定义无法改变，所以一个程序到达时，尽可能把它放入能容纳它的最小分区内。
可变分区 基本思想：是一种动态划分存储器分区的方法，并不预先划分好分区。 在装入程序时按其初始要求分配，分区大小可变，分区数目可变。当作业装入时，根据作业的需求和内存空间的使用情况来决定是否分配。若有足够的空间，则按需要分割一部分分区给该进程；否则令其等待主存空间。 或在其执行过程中通过系统调用进行分配或改变分区大小。 内存管理的数据结构： 空闲分区表——设置额外的数据结构记录空闲区起始地址和长度 空闲分区链——利用每个分区头部若干区域存放当前分区的大小和指向下一个空闲分区的指针
再定位分区（动态重定位分区分配技术） 动态重定位分区分配算法与动态分区分配算法基本相同， 差别在于： 在这种分配算法中增加了拼接功能，通常是在找不到足够大的空闲分区来满足作业要求，而系统中空闲分区容量总和大于作业要求时进行拼接。
内存紧缩
即拼接技术：将存储器中所有已分配分区移动到主存的一端，使本来分散的多个小空闲区连成一个大的空闲区。这种通过移动把多个分散的小分区拼接成一个大分区的方法称为拼接或紧凑，也可称为紧缩。 拼接时机 在某个分区回收时立即进行拼接，开销大。 当找不到足够大的空闲分区且总容量可以满足作业要求时进行拼接。
优点: 解决了可变分区分配所引入的“外部碎片”问题。消除内存碎片，提高内存利用率。 缺点: 提高硬件成本，紧凑时花费CPU时间。
多重分区分配 目的：依据程序结构分配多个分区，提高共享 为了支持结构化程序设计，操作系统往往把一道作业分成若干片段如子程序、主程序、数据组等）。 需要增加一些重定位寄存器，来控制一道作业片段之间的调用。 采用这种方法时，作业可以在其执行期间申请附加的分区。
主要优点： (1) 实现了主存的共享，因而有助于多道程序设计，更有效地利用了处理机和I/O设备，从而使系统的吞吐量和作业周转时间得到改善。至于主存利用率，可变式分区比固定式分区高些， 可再定位式分区则更高些。 (2) 相对于后面介绍的存储管理方式，本方案为实现分区分配所使用的表格、占用的存储容量相对较少，算法也相对简单。 (3) 实现存储保护的措施也比较简单。 (4) 多重分区分配方案能实现对子程序、 数据段的共享。
主要缺点： (1) 主存仍不能充分利用，除了可再定位式分区法外，都存在着严重的碎片问题。另外，即使不把存储器分碎，整个空白区也可能因容纳不下一个作业而造成浪费。 (2) 不能实现对主存的扩充。 因此， 作业的大小受到主存可用空间的限制。 (3) 和单一连续分配一样，要求一个作业在执行之前必须全部装入主存，因此在主存中可能包含从未使用过的信息。 (4) 采用靠拢方法，虽然能解决碎片问题，但有时需移动大量信息，从而损失了处理机时间。 (5) 除多重分区外，几个共行作业之间不能共享存入主存的单一信息副本(如公用子程序、数据段等)。
原理：把内存分为一些大小相等或不等的分区(partition)，每个应用进程占用一个或几个分区。操作系统占用其中一个分区。 特点：适用于多道程序系统和分时系统 支持多个程序并发执行 难以进行内存分区的共享 问题：可能存在内碎片和外碎片。 内碎片：占用分区之内未被利用的空间。 外碎片：占用分区之间难以利用的空闲分区。
分区的数据结构：分区表，或分区链表 可以只记录空闲分区，也可以同时记录空闲和占用分区 分区表中，表项数目随着内存的分配和释放而动态改变，可以规定最大表项数目。 分区表可以划分为两个表格：空闲分区表，占用分区表。空闲分区表中按不同分配算法相应对表项排序。
算法
按照一定的分配算法从空闲分区表（或空闲分区链）中选出一个满足作业需求的分区分配给作业。 如果这个空闲分区的容量比作业申请的空间容量要大，那么将该分区的一部分分配给作业，剩下的一部分仍然留在空闲分区表（或空闲分区链） 中，同时需要对空闲分区表（或空闲分区链）中的有关信息进行修改。
首次适应算法(First Fit: FF)
每次都从低地址开始查找，找到第一个能满足的空闲分区
简单，查找次数少，在高地址区中保持较大自由区域。 优点：优先利用内存低地址部分的空闲分区，从而保留了高地址部分的大的空闲分区，无内部碎片。 缺点：由于低地址部分不断被划分，致使低地址端留下许多难以利用的很小的空闲分区（外部碎片），而每次查找又都是从低地址部分开始，将导致增加查找可用空闲分区的开销。
循环首次适应(Next fit: NF)
对首次适应法的改进。将空闲队列改为循环队列（依然是将空闲分区按照地址递增的次序排列）。 分配内存时，系统不是从空闲分区表的开始处开始查找，而是从上次分配分区后的位置开始查找，找到第一个满足要求的空闲分区，分配并分割该空闲分区。
优点： 这样使得空闲分区的分布更加均匀，减少了查找空闲分区的开销。 缺点： 导致缺乏大的空闲分区。
最佳适应算法(Best fit: BF)
将空闲分区按照容量大小递增的次序排列。每 次为作业分配内存空间时，总是将能满足空间大小需要的最小空闲分区分配给作业，因此将产生最小的内存空闲分区。
优点：这种方法总能分配给作业最恰当的分区，并保留大的分区。 缺点：导致产生很多难以利用的碎片空间，查找效率降低。
最坏适应算法(Worst fit: WF)
空闲分区按照容量大小递减的次序排列。每次为作业分配内存空间时，总是将满足要求且最大的内存空间分配给作业。
缺点：由于最大的空闲分区总是因首先分配而被划分，当有大作业到来时，其存储空间的申请会得不到满足。
动态分区分配
优点： ①实现了多道程序共用主存（共用是指多进程同时存在于主存中的不同位置）； ②管理方案相对简单、不需要更多开销； ③实现存储保护的手段比较简单。 缺点： ①主存利用不够充分，存在外部碎片； ②无法实现多进程共享存储器信息（共享是指多进程都使用同一个主存段）； ③无法实现主存的扩充，进程地址空间受实际存储空间的限制。
内存回收
需要修改： 空闲区首地址； 空闲区大小。
分区释放算法：需要将相邻的空闲分区合并成一个空闲分区。(这时要解决的问题是：合并条件的判断和合并时机的选择)
非连续分区分配管理
分页存储管理（或称页式存储管理） 根据分区大小是否固定 分为分页存储管理方式和分段存储管理方式
覆盖和交换
覆盖
引入：其目标是在较小的可用内存中运行较大的程序。常用于多道程序系统，与分区存储管理配合使用。 原理：一个程序的几个代码段或数据段，按照时间先后来占用公共的内存空间。 将程序的必要部分（常用功能）的代码和数据常驻内存； 可选部分（不常用功能）在其他程序模块中实现，平时存放在外存中（覆盖文件），在需要用到时才装入到内存； 不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。(即不同时用的模块可共用一个分区)
缺点：1. 编程时必须划分程序模块和确定程序模块之间的覆盖关系，增加编程复杂度。2. 从外存装入覆盖文件，以时间延长来换取空间节省。
交换
引入：多个程序并发执行，可以将暂时不能执行的程序送到外存中，从而获得空闲内存空间来装入新程序，或读入保存在外存中而目前到达就绪状态的进程。交换单位为整个进程的地址空间。 原理：暂停执行内存中的进程，将整个进程的地址空间保存到外存的交换区中，而将外存中由阻塞变为就绪的进程的地址空间读入到内存中，并将该进程送到就绪队列。
优点：增加并发运行的程序数目，并且给用户提供适当的响应时间；编写程序时不影响程序结构； 缺点：对换入和换出的控制增加处理机开销；程序整个地址空间都进行传送，没有考虑执行过程中地址访问的统计特性。
与覆盖技术相比，交换技术不要求用户给出程序段之间的逻辑覆盖结构；而且，交换发生在进程或作业之间，而覆盖发生在同一进程或作业内。此外，覆盖只能覆盖那些与覆盖段无关的程序段。
