存储思维笔记模板_ProcessOn思维导图、流程图

对换

对换的引入

把内存中暂时不能运行的进程（或者暂时不用的程序和数据）调出到外存上，以便腾出内存空间；再把已具备运行条件的进程（或进程所需要的程序和数据）调入内存

对换目的：提高内存利用率

对换空间的管理

有对换功能的OS，把外存分为文件区和对换区

文件区：用于存放文件，主要目标是提高文件存储空间的利用率，所以采取离散分配方式

对换区：存放从内存换出的进程，进程在对换区中驻留时间短暂，对换操作频繁，目标是提高进程换入和换出的速度。所以采取的是连续分配方式

系统中应配置相应数据结构，以记录外存的使用情况

进程的换出和换入

进程的换出过程

选择阻塞且优先级最低的进程为换出进程.

（换出）启动磁盘，将进程的程序和数据传送到磁盘的对换区上

进程的换入过程

系统定时查看所有进程的状态，从中找出“就绪”状态但已换出的进程，将其中换出时间最久(在磁盘上)的进程作为换入进程

（换入）将它换入，直至已无可换入的进程或无可换出的进程为止

分页存储管理方式（Paging）

出现原因:动态分区使用“紧凑”技术，但是需要一直移来移去

分页存储管理的基本方法

页面 

进程的逻辑地址空间分成若干个大小相等的片，称为==页面或页==，并为各页加以==编号== （从0开始）

物理块

内存分成与页面相同大小的存储块，称为(物理)块或[页框frame]，同样进行编号。

页面大小

2^n Bytes 一般在512B ~ 8/32K （机器的地址结构决定）

地址结构

地址有两部分：前一部分为页号P，后一部分为位移量W(或称为页内地址)

计算方法

页表

作用：实现从页号到物理块号的地址映射(: 逻辑页号 → 物理块号) 进程在执行时，通过页表找到每页在内存中的物理块号

地址变换机构

基本的地址变换机构 

页表功能由一组专门寄存器来实现（速度快，但成本高）

系统设置一个页表寄存器PTR（页表始址、长度）

地址变换

块表地址变换机构

CPU每存取一个数据时，都要两次访问内存

① 访问内存中的页表，形成物理地址

② 访问数据内存

计算机的处理速度降低近1/2。 

解决办法：增设具有并行查寻能力的特殊高速缓冲寄存器(又称“联想寄存器” 或“快表”)，存放当前访问的那些页表项。

地址变换过程

访问内存的有效时间

EAT （Effective Access Time) =（第一次访问内存地址时间t （去页表取物理地址，页表在内存里））+（第二次访问内存地址时间t。（取数据））总时间

引入快表后

EAT = a X λ + (t+λ)(1- a) + t = 2t + λ - t X a

两级和多级页表

两级页表

现代计算机系统支持非常大的逻辑地址空间232～264，页表就变得非常大，要占用相当大的内存空间

为离散分配的页表再建立一张页表，称为外层页表(Outer Page Table)，每个页表项中记录页表页面的物理块号

多级页表

基本分页特点

优点

存在页内碎片，但碎片相对较小，内存利用率较高；

实现了离散分配，消除了程序浮动

便于存储访问控制，有利于代码共享

缺点

需要专门的硬件支持，尤其“快表”

内存访问的效率下降

不足：不能实现真正的共享，不支持动态链接

分段存储管理方式（Segmentation）

固定分区→动态分区→分页存储管理，提高内存利用率

引入分段存储管理的目的：为满足用户(程序员)在编程和使用上的要求

分段存储管理方式的引入

方便编程

程序划分为若干段，每个段都从0开始编址，并有自己的名字和长度。逻辑地址是由段名(段号)和段内偏移量(段内地址)决定的(fig)

信息共享

 程序和数据的共享，是以信息的逻辑单位为基础，段是信息的逻辑单位

信息保护：同样是对信息的逻辑单位进行保护。

动态增长：数据段使用过程中会不断地增长。

动态链接：要求以段作为管理的单位。

分段系统的基本原理

分段

地址空间分成若干段，每段定义了一组逻辑信息，并有自己的段名 各段都从0开始编址，并采用一段连续的地址空间 地址结构：段号 + 段内地址

段表

每段分配一个连续的分区，各段==离散==放入不同的分区 系统建立段映射表，记录段在内存中的起始地址和段长度

地址变换机构

逻辑地址→物理地址，系统设置段表寄存器：存放段表始址+段表长度TL

分段与分页的主要区别

信息共享

分段系统的突出优点：易于实现段的共享，即允许若干进程共享一个或多个分段，且对段的保护也十分简单易行。

在分页系统中，也能实现程序和数据的共享，但远不如分段系统来得方便。

可重入代码（Reentrant Code，又称纯代码, 执行中不可改变)：允许多个进程同时访问的代码（不允许任何进程对它进行修改）

段页式存储管理方式

基本原理

分段和分页结合。先将用户程序分成若干个段，再把每个段分成若干个页；为每个段赋予一个段名,而对内存进行分页

地址结构

在段页式系统中，为了获得一条指令或数据，须三次访问内存

访问内存中的段表，从中取得页表始址

访问内存中的页表，从中取出该页所在的物理块号，并将块号与页内地址一起形成指令或数据的物理地址

真正从第二次访问所得的地址中，取出指令或数据

段页式地址变换机构

问题：小空间容纳大作业

时空要求

时：速度要快

空：占据存储空间小

解决

虚拟空间

空间上的调度算法

存储器层次结构

多级存储器结构

主存储器与寄存器

主存储器

别名：内存

所存内容：进程运行时的程序和数据

CPU的控制部件只能从主存储器中取得指令和数据

主存的访问速度远低于CPU执行指令的速度，为缓和这一矛盾，引入了寄存器和高速缓存

寄存器

访问速度最快，最靠近CPU，完全能与CPU协调工作

容量不可能做得很大，长度一般以字(word)为单位

用于加速存储器的访问速度，如用寄存器存放操作数，或用作地址寄存器加快地址转换速度等。

高速缓存和磁盘缓存

高速缓存

存在原因： CPU主频 = 外频 × 倍频，使CPU执行完一条指令后，要“等待”一段时间才能访问内存

大小：容量远大于寄存器，比内存约小2~3个数量级，从几十KB到几MB

速度：访问速度快于寄存器-

 原理：将主存中经常访问的数据存放在高速缓存中，减少访问主存储器的次数，大幅度提高程序执行速度

磁盘缓存

在内存空间中，划出一块，作为缓存：读缓存和写缓存，批量读、延迟写

存在原因：磁盘的I/O速度，远低于主存的访问速度

 目的：将频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数。

地理位置：利用主存中的存储空间，来暂存从磁盘中读出或写入的信息。

名空间、地址空间、存储空间

名空间

程序员在程序中定义的标识符

程序符号集合,由程序员自定义

没有地址的概念

地址空间 Logical Address

一个应用程序经编译、链接后的程序，其地址都是从“0”开始，程序中的其它地址都是相对于起始地址来计算，由这些地址所形成的地址范围称为地址空间。

程序用来访问信息所用地址单元的集合

地址空间的大小：由被编译的源程序决定

存储空间 Physical Address

物理存储器中全部物理存储单元的集合所限定的空间。每个存储单元都有自己的编号地址。由这些地址所形成的地址范围称为地址空间。

指主存中物理单元的集合

存储空间的大小：由系统的硬件配置决定的

一个程序只有从地址空间装入存储空间后才能运行

三者关系

逻辑地址与物理地址

逻辑地址（相对地址，虚地址）

不能用逻辑地址在内存中读取信息

目标代码通常采用相对地址的形式，其首地址为0

物理地址（绝对地址，实地址）

重定位的概念

把程序地址空间的逻辑地址转换为存储空间的物理地址叫地址重定位(地址映射，地址变换

地址空间的逻辑地址与存储空间的物理地址不一致

处理机执行用户程序时，要访问的指令和数据地址必须是实际的物理地址

类型

静态

地址转换工作，在程序执行前由装入程序集中一次完成

程序执行期间不能移动，导致主存利用率低；

动态

程序和数据装入存储区后，把这个存储区的起始地址送入重定位寄存器中。程序执行时，再将相对地址转换成绝对地址。

主存利用率高。在存储区域可移动用户程序。移动后，只要修改重定位寄存器即可。

程序的装入和链接

程序装入步骤

创建进程的第一件事：将程序和数据装入内存

步骤

编译(源代码编译成若干个目标模块)

链接(一组目标模块、库函数链接成装入模块)

装入(模块装入内存)

 绝对装入

逻辑地址与实际内存地址完全相同，故不须对程序和数据的地址进行修改。

程序中的绝对地址，可在编译或汇编时给出，也可由程序员直接赋予

通常是在程序中采用符号地址，然后在编译、汇编时，将这些符号地址转换为绝对地址

缺点

绝对装入方式缺点：只能将目标模块装入到内存中事先指定的位置

可重定位装入

静态重定位：地址变换在装入时一次完成的，以后不再改变，称为静态重定位。

目标模块的起始地址从0开始的，其它地址都相对于起始地址计算

装入时对目标程序中指令和数据的修改过程称为重定位（因为地址变换是在装入时一次完成，以后不再改变，故称静态重定位）

动态运行时装入

可重定位装入方式可用于多道程序环境,但不允许程序运行时在内存中移动

程序在运行过程中,它在内存中的位置经常要改变，应采用动态运行时装入的方式

地址转换推迟到程序真正要执行时才进行，装入内存后的所有地址都仍是相对地址

需要硬件支持（重定位寄存器）

程序的链接方式

静态链接  

事先将各目标模块、库函数链接成完整的装配模块

装入时动态链接

源程序经编译后的各个目标模块，是在装入内存时边装入边链接的

优点

- 便于修改和更新

- 便于实现目标模块的共享

运行时动态链接

在执行过程中，发现一个被调用模块尚未装入内存时，立即由OS把该模块装入内存，并链接到调用者模块上。如此不仅可加快程序的装入过程，而且可节省大量的内存空间。

特点

链接在执行时才进行(未用到的不被链接)

增加了程序执行时的链接开销  

连续分配存储管理方式

单一连续分配 Single-partition allocation

·内存分为系统区、用户区，系统区供OS使用(常放在低址部分)；其余全部内存空间是用户区。

特点

只能用于单用户、单任务的OS中。

软件简单，硬件要求低（无需存储保护）

可设置保护机构（基址寄存器，界限寄存器）

固定分区分配 Fixed partition allocation

内存划分成若干个连续区域，称为分区。每个分区只存储一个程序，而且程序也只能在它所驻留的分区中运行。

划分分区的方法

分区大小相等

划分简单。

缺点：缺乏灵活性

分区太大，空间浪费（程序小）；分区太小，不足以装入程序，无法运行

分区大小不等

划分成：多个小分区 + 适量中等分区 + 少量大分区这样，便可根据程序的大小为之分配适当的分区

内存分配管理

建立分区使用表，将分区按大小进行排队

内存分配程序检索该表，找出能满足要求的、尚未分配的分区，分配给程序

动态分区分配 Dynamic Storage-Allocation

基本思想

根据进程的实际需要，动态地分配内存空间

分配中的数据结构

为实现分区分配，须配置相应的数据结构，来描述空闲分区和已分配分区的情况，为分配提供依据

常用的数据结构

空闲分区表

空闲分区链

分区分配操作

分配内存：从空闲分区表中找所需分区

回收内存：以首地址寻找相应插入点，可能存在四种情况

① 同前一分区相邻接→同前一分区合并

② 同后一分区相邻接→同后一分区合并(改变首址、大小

③同前后分区邻接 → 三分区合并(前一分区表项改变大小)(c)找到其大小与要求相差最小的空闲分区（分区小 →大）

④不邻接 → 建立新表项

基于顺序搜索的动态分区分配算法

首次适应（FF）算法

按分区的先后次序，从头查找，找到符合要求的第一个分区（地址小 →大）

循环首次适应（NF）算法

按分区的先后次序，从上次分配的分区查找（到最后分区时再回到开头），找到符合要求的第一个分区（地址小 →大）

最佳适应（BF）算法

找到其大小与要求相差最小的空闲分区（分区小 →大）

最坏适应（WF）算法

总是挑选一个最大的空闲区分割给作业使用（分区大 →小）

基于索引搜索的动态分区分配算法

快速适应（QF）算法

空闲分区按容量大小分类，每类设立空闲分区链表，并设管理索引表

哈希算法

宜用管理索引表查找所需空间对应的表项，得到对应空闲分区链表的表头指针，得到一个空闲分区

利用空间表中的分布规律，构造一张以空闲分区大小为关键字的哈希表，每个表项记录一个对应的空闲分区链表表头指针

伙伴系统（BS）

固定分区和动态分区的不足之处

固定分区：限制活动进程的数目，进程大小与空闲分区大小不匹配时，内存空间利用率很低

动态分区：算法复杂，回收空闲分区时需进行分区合并等，系统开销较大

伙伴系统方式是对以上两种内存方式的一种折衷方案

分区划分：无论已分配分区或空闲分区，大小均为2的k次幂，k为整数，l ≤ k ≤ m，2^m^是最大分区的大小。

最坏的情况下，可能需要对2^k的空闲分区进行k次分割才能得到所需分区

时间性能：比前面所述的分类搜索算法差，但比顺序搜索算法好；

空间性能：远优于分类搜索法，比顺序搜索法略差

动态可重定向分区分配

动态重定位：与动态分区基本相同，只是增加了紧凑功能

在每次“紧凑”后，都必须对移动了的程序或数据进行重定位

优点

解决了可变分区分配所引入的“外零头”问题。消除内存碎片，提高内存利用率

缺点

需要动态重定位“硬件”机构支持，增加了系统成本，并轻度降低了程序执行速度，“紧凑”处理增加了系统开销

分配算法

实现