计算机操作系统原理主讲：王凤广
2003.2
第四章 存储器管理
第一节 存储器管理概述
第二节 分区存储管理
第三节 虚拟存储器
第四节 分页存储管理
第五节 段式存储管理
第六节 段页式存储管理第一节 存储器管理概述
1.存储器层次
2.地址重定位
3.存储管理功能三级存储器结构：
高速缓冲存储器主存储器外存储器第一节 存储器管理概述
1.存储器层次
2.地址重定位
3.存储管理功能名字空间：
用户编写程序，用名字表示地址。
源程序中，符号名字组成的空间，叫名字空间。
地址空间：
编译程序在对源程序进行编译时，无法确定其实际的存储地址，因此，总是从零开始为其分配地址，这个地址叫逻辑地址。
逻辑地址组成的空间叫地址空间。
第一节 存储器管理概述
1.存储器层次
2.地址重定位
3.存储管理功能物理空间：
一个程序运行，必须把它装到实际的物理存储器中，每条指令就有一个实实在在的存储器地址，这个地址就是物理地址。
物理地址的集合就物理空间。
第一节 存储器管理概述
1.存储器层次
2.地址重定位
3.存储管理功能地址重定位：
在多道程序环境下，用户无法事先确定自己使用的主存区，即地址空间和物理空间是不一致的，逻辑地址和物理地址通常不同。因此，程序调入内存时，必须对地址进行调整。
由于一个作业装入到与其地址空间不一致的物理空间中,而引起的对有关地址部分的调整过程叫地址重定位。
第一节 存储器管理概述
1.存储器层次
2.地址重定位
3.存储管理功能地址重定位分类：
静态重定位 在程序装入时，由操作系统一次完成由逻辑地址到物理地址的映射。在执行过程中不再进行地址转换。
特点：
实现简单，不需要硬件支持，执行速度快。
作业的存储空间必须连续；必须事先确定所需存储容量；难以共享。
第一节 存储器管理概述
1.存储器层次
2.地址重定位
3.存储管理功能地址重定位分类：
动态重定位 在程序装入时，不对逻辑地址进行任何处理，在执行过程中进行地址转换。
特点：
作业的存储空间可以不连续；作业可以动态申请内存和在主存中移动；便于共享。
需要硬件支持，管理软件复杂。
第一节 存储器管理概述
1.存储器层次
2.地址重定位
3.存储管理功能
存储的分配和去配
地址的映射
存储器的扩充
存储器的共享
存储器的保护第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理用于单道程序的操作系统。
把用户空间一次分配给一个作业。
示意图第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
原理：
系统初始化时，把用户空间划分成若干任意大小的区间；在存储分配时，一个区间分配给一个作业。
区间一旦设定好，在系统运行期间不能改变。
一个作业只能在一个区间内运行。
示意图第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
原理：
系统初始化时，把用户空间划分成若干任意大小的区间；在存储分配时，一个区间分配给一个作业。
特点：
实现简单，不需要硬件支持。
使用不灵活，内存利用率不高。
存储空间要求连续。
存在内零头。（分配给分配给作业而未被使用的存储空间）
第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
分配和去配：
数据结构：
分区说明表分区号 大小 始址 状态
1 12K 20K 0
2 32K 32K 0
3 64K 64K 0
4 128K 128K 0
OS区 20K
12K
32K
64K
128K
作业序列：
A,9K
B,65K
C,7K
D,70K
第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
分配和去配：
数据结构：
分区说明表分区号 大小 始址 状态
1 12K 20K 1
2 32K 32K 1
3 64K 64K 0
4 128K 128K 1
OS区
A
C
B
作业序列：
A,9K
B,65K
C,7K
D,70K
第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
分配和去配：
分配,
1）查找符合要求的最小分区；
2）把状态改成“已分配”；
3）返回分区的起始地址。
去配,
1）查找要释放的分区；
2）把状态改成“未分配”。
第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
原理：
作业装入时，按一定算法找出一块合适的空闲空间，从中切出一块连续区域分配给作业，
且分区大小正好适合作业的要求。分区的大小和个数不是事先划分定，而是根据装入的作业动态划分。
内存分区动态变化第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
分配和去配：
数据结构空闲分区表 占用分区表始址 大小 状态
4K 48K 1
0
0
0
0
始址 大小 状态
0
0
0
0
0
作业序列,A:4K,B:8K,C:3K,D:2K
第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
分配和去配：
数据结构空闲分区表 占用分区表始址 大小 状态
21K 31K 1
0
0
0
0
始址 大小 状态
4K 4K 1
8K 8K 1
16K 3K 1
19k 2K 1
0
作业序列,A:4K,B:8K,C:3K,D:2K
第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
分配和去配：
数据结构空闲分区表 占用分区表始址 大小 状态
21K 31K 1
0
0
0
0
始址 大小 状态
4K 4K 1
8K 8K 1
16K 3K 1
19k 2K 1
0
作业序列,A:4K,B:8K,C:3K,D:2K
时刻 X,作业 B完成第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
分配和去配：
数据结构空闲分区表 占用分区表始址 大小 状态
21K 31K 1
8K 8K 1
0
0
0
始址 大小 状态
4K 4K 1
0
16K 3K 1
19k 2K 1
0
作业序列,A:4K,B:8K,C:3K,D:2K
时刻 X,作业 B完成第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
分配和去配：
分配算法最佳适应算法 选择符合要求的最小分区最坏适应算法 选择符合要求的最大分区首次适应算法 选择符合要求的首个分区第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
分配和去配：
分配：申请分配 nKB的空间
1）从空闲分区表中按指定算法查找符合要求的分区；
2）如果没有找到出错返回
3）如果找到形成大小为 nK，始址为当前空闲分区始址的已占用分区查找该占用分区在已占用分区表中的位置把该占用分区插入已占用分区表中把空闲分区的始址增加 nK，大下减小 nK
4）返回分区的始址第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
分配和去配：
去配：释放始址为 nK的分区
1）在已占用分区中查找始址为 nK的分区
2）把分区变成无效，形成一空闲分区
3）在未占用分区表中查找适当的位置
4）插入新分区，并作上联合下联处理。
第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
特点：
使用简单，和固定分区比起来，使用更加灵活，内存利用率高。
作业的物理空间仍然要求连续；
存在外零头（由于内存太小而无法使用的存储区间）可以采用拼接的方式解决，但系统开销大。
难以实现虚拟存储，存储扩充困难。
第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
分区存储管理的地址映射静态重定位作业在调入内存的过程中，把逻辑地址转换为物理地址。
第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
分区存储管理的地址映射动态重定位设置基地址寄存器,CPU中设一地址转换机制，在进行存储器操作时，该转换机制自动把逻辑地址和基地址相加形成物理地址。
第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
分区式存储管理的存储保护：
1,界地址法系统设置一个上,下界寄存器,访问存储器的地址和这两个寄存起的值比较 。
2,保护键法系统每个存储块分配一个单独的保护键 （ 相当于一把锁 ） 。
在程序状态字中设置保护键字段 。
对不同作业赋予不同代码,相当于钥匙 。
第三节 虚拟存储器让大的作业在一个小的存储空间上运行－－－存储扩充
程序的局部性原理：
空间局部性 一个单元被访问后，在不久的将来它附近的单元也可能被访问。
时间局部性 一个单元被访问后，在不久的将来它可能再次被访问。
在一段时间内，程序的执行局限在一个区间内。
让一个大的作业在一个小的内存上运行是可行的。
第三节 虚拟存储器让大的作业在一个小的存储空间上运行－－－存储扩充用户层面（逻辑层面）
1）用户的程序是在一个以 0为起始地址的逻辑空间内。
2）逻辑地址（用户程序中用的地址）和物理地址（系统物理存储器的实际地址）是两套独立的地址系统。逻辑地址的位数可以大于物理地址的位数，逻辑地址空间可以远远大于物理地址空间。
3）逻辑地址到物理地址的映射，由操作系统自动完成，对用户透明。
4）用户认为系统为自己提供了一个非常大的存储空间，其大小为 2n（ n为逻辑地址的位数）。
虚拟存储器的两个层面：
第三节 虚拟存储器让大的作业在一个小的存储空间上运行－－－存储扩充物理层面
1）只把作业的一部分调入内存。
2）当作业访问的内容不在内存时，系统自动把这些内容从外存调入内存。
3）当物理内存不够时，系统便自动把内存的一部分调到外存中，以空出更多的内存。
4）内存和外村的交换过程是由系统自动完成的（需要硬件支持），对用户透明 。
虚拟存储器的两个层面：
第三节 虚拟存储器让大的作业在一个小的存储空间上运行－－－存储扩充
1）用表格为用户构造一个虚空间
2）提供一个大容量的高速外存来存放进入虚空间的实际信息，这是实现虚拟存储器的物理基础。
3）把主存作为用户虚存空间中程序和数据得以运行的缓冲区。缓冲区的管理有操作系统完成，对用户透明。
实现的基本手段：
第三节 虚拟存储器让大的作业在一个小的存储空间上运行－－－存储扩充
总之,
在一个操作系统下，如果不要求任意用户程序所占的物理空间都大于等于该用户程序的逻辑地址空间，而且这种功能对用户来说是透明的，则称该操作系统实现了虚存技术，
相应的用户进程空间称为虚存空间，系统为用户提供的作业运行空间叫虚拟存储器。
虚拟存储器的大小受逻辑地址的位数和外存容量的限制第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
1,等分主存把主存划分成大小相等的块,称为页架
（ Page Frame),每块的大小为 2n。
2,作业的地址空间分页作业的地址空间划分成若干个与块相等的页 。 在存储分配时,每页分配一块 。
3,逻辑地址的表示逻辑地址分成两部分：页号和页内偏移量 。
逻辑地址的高位表示页号,低位表示页内偏移量第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
原理采用分页方式,把一个作业一次全部装入内存中 。
系统能满足一个作业所需的全部块数,此作业才能被装入内存,否则,不为它分配任何内存 。
地址空间是连续的,物理空间是不连续的第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
地址映射数据结构在内存中为作业创建一个页号和块号对照表－－页表页表的表项页号 块号
CPU:
逻辑地址,20位页长,1K
一个作业的长度,
3.3K
内存大小 256K:
其中空闲块为：
100,128,64,75，
190,……
该例作业的页表为页号 块号
0 100
1 128
2 64
3 75
地址映射的过程第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
地址映射数据结构 在内存中为作业创建一个页号和块号对照表－－页表页表的表项页号 块号
CPU:
逻辑地址,20位页长,1K
一个作业的长度,
3.3K
内存大小 256K:
其中空闲块为：
100,128,64,75，
190,……
该例作业的页表为页号 块号
0 100
1 128
2 64
3 75
mov AX,[3100]的 地址映射的过程第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
地址映射性能的改进，采用联想存储器第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
内存的分配和去配物理块的组织位示图法链表法第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
页面的共享共享分数据共享和程序共享数据共享,允许不同的作业对共享的数据页面用不同的页号,只要让各自页表中的有关表目指向共享的信息块即可 。
程序共享,逻辑地址空间是连续的,程序运行的当前页号是固定的 。
对共享程序,在各个作业中的页号必须是统一的 。
第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
特点优点作业的存储空间不再要求连续易于实现存储共享缺点需要硬件支持存在内零头效率降低未实现存储扩充第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
原理运行一个作业时,并不把所有页面调入内存,
而是只调入一部分,其余仍保存在外存上,
以后据作业运行的需要,再调入内存 。
处理的两个问题
A,执行到不在内 存 的 页,如何调入内存；
如何判断？ 如何处理？
B,当欲调入页,而内存不够怎么办第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
实现
1） 扩充页表页号 块号 存取控制 改变位 引用位中断位 外存地址
2） 地址映射时中断位为零,页面在内存中,遵循简单分页系统的过程 。
中断位不为零,产生缺页中断,CPU自动转到中断处理程序执行,执行完中断处理程序,
在未执行完的指令继续执行 。
第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
实现
3） 缺页中断处理完成内存和外存的对换第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
页面的淘汰算法页面的淘汰算法选择不好,容易产生颠簸 （ 抖动 ） 现象 。
刚调出的页面,马上又要用到,从而造成频繁的调入调出,消耗大量 CPU时间,使 CPU难以进行正常处理 。
系统设计要尽量避免抖动的发生 。
第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
页面的淘汰算法先进先出页面置换算法 （ FIFO）
先进入的页面先淘汰第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
页面的淘汰算法最佳置换算法 （ Opt）
选择将来不用的页面或将来最长时间不用的页面淘汰掉 。
效率最高的一种淘汰算法由于程序的执行难以实现确定,即页面的访问顺序无法事先知道,该算法难以实现 。
第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
页面的淘汰算法最近最久未用页面置换算法（ LRU)
选择最近一段时间,,最老,的页面淘汰掉 。
根据页面过去的走向,预测未来的走向 。
第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
特点优点：
和简单分页存储管理比较起来,实现了存储器的扩充 。
缺点：
管理复杂第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
练习
CPU的逻辑地址是 24位,页的大小是 4K,物理内存 128K。
1)虚拟存储器最大是多少？
2)内存有多少块？ 虚拟存储器有多少页？
3)一个作业的最大长度是多少？
4)逻辑地址 8580在第几页？ 页内偏移量是多少？
第五节 分段存储管理
1.分段存储管理
3.段页式存储管理
原理把作业按内在的逻辑关系分成若干段,每一段是一个独立的逻辑单位 。 在进行存储分配时,每段分配一块内存 。
每一段是一个以 0为起址的连续地址空间 。
地址空间是 2维的,逻辑地址分为两部分：
段号和段内偏移量作业的存储空间段内是连续的,段间可以不连续 。
段式虚拟空间 大小为 2nX 2m
第五节 分段存储管理
1.分段存储管理
3.段页式存储管理
地址转换数据结构段表段号 段长 始址 存取控制 状态位 访问位改变位 增补位地址映射地址转换 — 分段第五节 分段存储管理
1.分段存储管理
3.段页式存储管理
段的共享采用动态链接技术,可以方便地实现共享 。
不再要求代码段在各作业中具有相同的段号 。
第五节 分段存储管理
1.分段存储管理
3.段页式存储管理
段的保护段表表目本身起到基址／限长寄存器的作用；
建立存取控制设段保护键第五节 分段存储管理
1.分段存储管理
3.段页式存储管理
分段和分业的区别
1） 页是定长的,而段不是 。
2） 页是信息的物理单位,分业是系统的要求,分页对用户透明；
段是信息的逻辑单位,分段是作业的逻辑上的要求,分段用户可见 。
3） 逻辑地址的分解不同分页：逻辑地址分成页号＋位移量是硬件功能,无越界分段：逻辑地址定义成段号＋位移量是用户定义,存在越界第五节 分段存储管理
1.分段存储管理
3.段页式存储管理
分段和分业的区别
4） 从地址空间 （ 用户 ） 的角度分页：地址空间是一维的分段：地址空间是二维的分段的地址间是二维的,但存储空间是一维的第五节 分段存储管理
1.分段存储管理
3.段页式存储管理
分段的特点优点：
1） 便于程序的模块化处理,便于处理变化的数据结构；
2） 便于动态链接和共享；
3） 实现了虚拟存储器 。
第五节 分段存储管理
1.分段存储管理
3.段页式存储管理
分段的特点缺点：
1） 增加系统开销,使操作系统复杂化；
2） 磁盘对换以段为单位,效率低；
3） 分段的最大尺寸受到内存空闲区间的影响；
4） 存在外零头 。
第五节 分段存储管理
1.分段存储管理
3.段页式存储管理
原理
1） 对内存分成固定大小的块
2） 作业的地址空间采用段式分割
3） 存储分配时,对作业的每一段又采用页式划分 。
从用户的角度看 采用分段管理从机器的角度看 采用分页管理第五节 分段存储管理
1.分段存储管理
3.段页式存储管理
特点优点综合了分段和分页的优点缺点：
系统更加复杂,系统开销更大；
内零头更严重 。
第七节 Linux存储管理总览一,Linux的地址空间结构
1G系统空间
C0000000-FFFFFFFF
3G用户空间
(0-BFFFFFFF)
3G 3G…
第七节 Linux存储管理总览二,Linux物理空间的结构
描述物理块的数据结构 page (include/linux/mm.h)
每一个物理块，都有一个 page结构的数据。
typedef struct page {
……
} mem_map_t;
第七节 Linux存储管理总览二,Linux物理空间的结构
物理页面仓库 ---数组 mem_map
系统初始化时，根据物理内存的大小，建立一个 page结构的数组，作为物理页面的仓库。
Mem_map中的每个元素，代表着一个页面；元素的下标，代表该物理块的序号。
第七节 Linux存储管理总览二,Linux物理空间的结构
物理块的分区管理在物理块管理时，为了满足不同的要求，提高系统效率，把
mem_map划分成不同区域（ ZONE）。
划分成三个分区 (include/linux/mmzone.h)
#define ZONE_DMA 0
#define ZONE_NORMAL 1
#define ZONE_HIGHMEM 2
第七节 Linux存储管理总览二,Linux物理空间的结构
空闲块的链式结构为了提高内存块分配的效率，每个区中的空闲块组成若干个链表。
每个管理区都有一个数据结构 zone_struct来描述，在 zone_struct中，
有一组空闲区间队列。为什么是一组而不是一个队列呢？这是因为常常需要成块的分配在物理空间中连续的多个页面，所以，要按块的大小分别加以管理。
因此，在 zone_struct中有 MAX_ORDER个对列，每个队列分别用来管理连续块长度分别为 1,2,4,8……2 MAX_ORDER空闲块。
用到的数据结构如下 (include/linux/mmzone.h)
第七节 Linux存储管理总览
＃ define MAX_ORDER 10
typedef struct free_area_struct {
struct list_head free_list;
unsigned long *map;
} free_area_t;
typedef struct zone_struct {
......
struct list_head inactive_clean_list;
free_area_t free_area[MAX_ORDER];
spinlock_t lru_lock;
......
} zone_t;
第七节 Linux存储管理总览二,Linux物理空间的结构
空闲块的链式结构第七节 Linux存储管理总览三,Linux虚存结构
地址映射模型虚存划分的二级结构 (页号和页内偏移量），无法满足大地址空间的要求。
因此,LINUX采用三级地址结构。
第七节 Linux存储管理总览三,Linux虚存结构
地址空间结构物理空间是从“供”的角度来管理的，页就是“仓库中还有什么”；虚存空间的管理是从“需”的角度来管理的，就是我们
“需要虚存空间的那些部分”。
进程并不会用完全部 3G的虚存空间，同时，一个进程所使用的虚存空间中的各部分又未必是连续的，通常形成若干个离散的虚存“区间”。
因此，通过 vm_area_struct，描述一个虚存区间
(include/linux/mm.h)。
第七节 Linux存储管理总览
struct vm_area_struct {
struct mm_struct * vm_mm; /* The address space we belong to,*/
unsigned long vm_start; /* Our start address within vm_mm,*/
unsigned long vm_end; /* The first byte after our end address within vm_mm,*/
struct vm_area_struct *vm_next;
pgprot_t vm_page_prot; /* Access permissions of this VMA,*/
unsigned long vm_flags; /* Flags,listed below,*/
rb_node_t vm_rb;
……
struct vm_operations_struct * vm_ops;
struct file * vm_file; /* File we map to (can be NULL),*/
unsigned long vm_raend; /* XXX,put full readahead info here,*/
void * vm_private_data; /* was vm_pte (shared mem) */
};
第七节 Linux存储管理总览三,Linux虚存结构
地址空间结构还有一个数据结构,mm_struct(include/linux/sched.h)，描述整个进程的虚存情况，因此，它是比 vm_area_struct更高层次上使用的数据结构。
一个进程只有一个 mm_struct，但一个 mm_struct可能对应几个进程。
第七节 Linux存储管理总览
struct mm_struct {
struct vm_area_struct * mmap; /* list of VMAs */
rb_root_t mm_rb;
struct vm_area_struct * mmap_cache; /* last find_vma result */
unsigned long free_area_cache; /* first hole */
pgd_t * pgd;
atomic_t mm_users; /* How many users with user space? */
atomic_t mm_count; /* How many references to "struct mm_struct" (users count as 1) */
int map_count; /* number of VMAs */
struct rw_semaphore mmap_sem;
spinlock_t page_table_lock; /* Protects task page tables and mm->rss */
struct list_head mmlist; /* List of all active mm's,These are globally strung
unsigned long start_code,end_code,start_data,end_data;
unsigned long start_brk,brk,start_stack;
unsigned long arg_start,arg_end,env_start,env_end;
……
};
第七节 Linux存储管理总览三,Linux虚存结构
地址空间结构进程的 task_struct
中又一个指针
mm，指向该进程的 mm_struct，
mm_struct中的
mmap指向
vm_area_struct队列。
第七节 Linux存储管理总览三,Linux虚存结构
地址空间结构
mm_struct和
vm_area_struct说明了对页面的需求； page、
zone_struct等说明了对页面的供应；而页面目录、
中间目录、页面表则是二者之间的桥梁。
单一连续分区
OS区用户区返回动态重定位返回作业
Mov ax,[0h]
0H
1K-1
100H
内存
0H
Mov ax,[0h]
CPU
基地址寄存器逻辑地址动态重定位返回作业
Mov ax,[0h]
0H
1K-1
100H
内存
0H
Mov ax,[0h]
CPU
基地址寄存器
100H
0H
逻辑地址
＋
固定分区返回
OS区 16K
4K
8K
8K
16K
12K
分段式存储管理地址映射返回分页存储管理地址映射返回页表大小 页表始址
L b
执行指令 MOV AX，［ 3100］
页号 页内偏移量
3 28 逻辑地址页表寄存器页号 块号
0 100
1 128
2 64
3 75
物理地址内存 0
256K－ 1
75 28
76828
(01001011 0000011100)
(01001011 0000011100)
2003.2
第四章 存储器管理
第一节 存储器管理概述
第二节 分区存储管理
第三节 虚拟存储器
第四节 分页存储管理
第五节 段式存储管理
第六节 段页式存储管理第一节 存储器管理概述
1.存储器层次
2.地址重定位
3.存储管理功能三级存储器结构：
高速缓冲存储器主存储器外存储器第一节 存储器管理概述
1.存储器层次
2.地址重定位
3.存储管理功能名字空间：
用户编写程序，用名字表示地址。
源程序中，符号名字组成的空间，叫名字空间。
地址空间：
编译程序在对源程序进行编译时，无法确定其实际的存储地址，因此，总是从零开始为其分配地址，这个地址叫逻辑地址。
逻辑地址组成的空间叫地址空间。
第一节 存储器管理概述
1.存储器层次
2.地址重定位
3.存储管理功能物理空间：
一个程序运行，必须把它装到实际的物理存储器中，每条指令就有一个实实在在的存储器地址，这个地址就是物理地址。
物理地址的集合就物理空间。
第一节 存储器管理概述
1.存储器层次
2.地址重定位
3.存储管理功能地址重定位：
在多道程序环境下，用户无法事先确定自己使用的主存区，即地址空间和物理空间是不一致的，逻辑地址和物理地址通常不同。因此，程序调入内存时，必须对地址进行调整。
由于一个作业装入到与其地址空间不一致的物理空间中,而引起的对有关地址部分的调整过程叫地址重定位。
第一节 存储器管理概述
1.存储器层次
2.地址重定位
3.存储管理功能地址重定位分类：
静态重定位 在程序装入时，由操作系统一次完成由逻辑地址到物理地址的映射。在执行过程中不再进行地址转换。
特点：
实现简单，不需要硬件支持，执行速度快。
作业的存储空间必须连续；必须事先确定所需存储容量；难以共享。
第一节 存储器管理概述
1.存储器层次
2.地址重定位
3.存储管理功能地址重定位分类：
动态重定位 在程序装入时，不对逻辑地址进行任何处理，在执行过程中进行地址转换。
特点：
作业的存储空间可以不连续；作业可以动态申请内存和在主存中移动；便于共享。
需要硬件支持，管理软件复杂。
第一节 存储器管理概述
1.存储器层次
2.地址重定位
3.存储管理功能
存储的分配和去配
地址的映射
存储器的扩充
存储器的共享
存储器的保护第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理用于单道程序的操作系统。
把用户空间一次分配给一个作业。
示意图第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
原理：
系统初始化时，把用户空间划分成若干任意大小的区间；在存储分配时，一个区间分配给一个作业。
区间一旦设定好，在系统运行期间不能改变。
一个作业只能在一个区间内运行。
示意图第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
原理：
系统初始化时，把用户空间划分成若干任意大小的区间；在存储分配时，一个区间分配给一个作业。
特点：
实现简单，不需要硬件支持。
使用不灵活，内存利用率不高。
存储空间要求连续。
存在内零头。（分配给分配给作业而未被使用的存储空间）
第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
分配和去配：
数据结构：
分区说明表分区号 大小 始址 状态
1 12K 20K 0
2 32K 32K 0
3 64K 64K 0
4 128K 128K 0
OS区 20K
12K
32K
64K
128K
作业序列：
A,9K
B,65K
C,7K
D,70K
第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
分配和去配：
数据结构：
分区说明表分区号 大小 始址 状态
1 12K 20K 1
2 32K 32K 1
3 64K 64K 0
4 128K 128K 1
OS区
A
C
B
作业序列：
A,9K
B,65K
C,7K
D,70K
第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
分配和去配：
分配,
1）查找符合要求的最小分区；
2）把状态改成“已分配”；
3）返回分区的起始地址。
去配,
1）查找要释放的分区；
2）把状态改成“未分配”。
第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
原理：
作业装入时，按一定算法找出一块合适的空闲空间，从中切出一块连续区域分配给作业，
且分区大小正好适合作业的要求。分区的大小和个数不是事先划分定，而是根据装入的作业动态划分。
内存分区动态变化第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
分配和去配：
数据结构空闲分区表 占用分区表始址 大小 状态
4K 48K 1
0
0
0
0
始址 大小 状态
0
0
0
0
0
作业序列,A:4K,B:8K,C:3K,D:2K
第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
分配和去配：
数据结构空闲分区表 占用分区表始址 大小 状态
21K 31K 1
0
0
0
0
始址 大小 状态
4K 4K 1
8K 8K 1
16K 3K 1
19k 2K 1
0
作业序列,A:4K,B:8K,C:3K,D:2K
第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
分配和去配：
数据结构空闲分区表 占用分区表始址 大小 状态
21K 31K 1
0
0
0
0
始址 大小 状态
4K 4K 1
8K 8K 1
16K 3K 1
19k 2K 1
0
作业序列,A:4K,B:8K,C:3K,D:2K
时刻 X,作业 B完成第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
分配和去配：
数据结构空闲分区表 占用分区表始址 大小 状态
21K 31K 1
8K 8K 1
0
0
0
始址 大小 状态
4K 4K 1
0
16K 3K 1
19k 2K 1
0
作业序列,A:4K,B:8K,C:3K,D:2K
时刻 X,作业 B完成第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
分配和去配：
分配算法最佳适应算法 选择符合要求的最小分区最坏适应算法 选择符合要求的最大分区首次适应算法 选择符合要求的首个分区第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
分配和去配：
分配：申请分配 nKB的空间
1）从空闲分区表中按指定算法查找符合要求的分区；
2）如果没有找到出错返回
3）如果找到形成大小为 nK，始址为当前空闲分区始址的已占用分区查找该占用分区在已占用分区表中的位置把该占用分区插入已占用分区表中把空闲分区的始址增加 nK，大下减小 nK
4）返回分区的始址第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
分配和去配：
去配：释放始址为 nK的分区
1）在已占用分区中查找始址为 nK的分区
2）把分区变成无效，形成一空闲分区
3）在未占用分区表中查找适当的位置
4）插入新分区，并作上联合下联处理。
第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
特点：
使用简单，和固定分区比起来，使用更加灵活，内存利用率高。
作业的物理空间仍然要求连续；
存在外零头（由于内存太小而无法使用的存储区间）可以采用拼接的方式解决，但系统开销大。
难以实现虚拟存储，存储扩充困难。
第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
分区存储管理的地址映射静态重定位作业在调入内存的过程中，把逻辑地址转换为物理地址。
第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
分区存储管理的地址映射动态重定位设置基地址寄存器,CPU中设一地址转换机制，在进行存储器操作时，该转换机制自动把逻辑地址和基地址相加形成物理地址。
第二节 分区存储管理
1.单一连续区管理
2.固定分区管理
3.可变分区管理
分区式存储管理的存储保护：
1,界地址法系统设置一个上,下界寄存器,访问存储器的地址和这两个寄存起的值比较 。
2,保护键法系统每个存储块分配一个单独的保护键 （ 相当于一把锁 ） 。
在程序状态字中设置保护键字段 。
对不同作业赋予不同代码,相当于钥匙 。
第三节 虚拟存储器让大的作业在一个小的存储空间上运行－－－存储扩充
程序的局部性原理：
空间局部性 一个单元被访问后，在不久的将来它附近的单元也可能被访问。
时间局部性 一个单元被访问后，在不久的将来它可能再次被访问。
在一段时间内，程序的执行局限在一个区间内。
让一个大的作业在一个小的内存上运行是可行的。
第三节 虚拟存储器让大的作业在一个小的存储空间上运行－－－存储扩充用户层面（逻辑层面）
1）用户的程序是在一个以 0为起始地址的逻辑空间内。
2）逻辑地址（用户程序中用的地址）和物理地址（系统物理存储器的实际地址）是两套独立的地址系统。逻辑地址的位数可以大于物理地址的位数，逻辑地址空间可以远远大于物理地址空间。
3）逻辑地址到物理地址的映射，由操作系统自动完成，对用户透明。
4）用户认为系统为自己提供了一个非常大的存储空间，其大小为 2n（ n为逻辑地址的位数）。
虚拟存储器的两个层面：
第三节 虚拟存储器让大的作业在一个小的存储空间上运行－－－存储扩充物理层面
1）只把作业的一部分调入内存。
2）当作业访问的内容不在内存时，系统自动把这些内容从外存调入内存。
3）当物理内存不够时，系统便自动把内存的一部分调到外存中，以空出更多的内存。
4）内存和外村的交换过程是由系统自动完成的（需要硬件支持），对用户透明 。
虚拟存储器的两个层面：
第三节 虚拟存储器让大的作业在一个小的存储空间上运行－－－存储扩充
1）用表格为用户构造一个虚空间
2）提供一个大容量的高速外存来存放进入虚空间的实际信息，这是实现虚拟存储器的物理基础。
3）把主存作为用户虚存空间中程序和数据得以运行的缓冲区。缓冲区的管理有操作系统完成，对用户透明。
实现的基本手段：
第三节 虚拟存储器让大的作业在一个小的存储空间上运行－－－存储扩充
总之,
在一个操作系统下，如果不要求任意用户程序所占的物理空间都大于等于该用户程序的逻辑地址空间，而且这种功能对用户来说是透明的，则称该操作系统实现了虚存技术，
相应的用户进程空间称为虚存空间，系统为用户提供的作业运行空间叫虚拟存储器。
虚拟存储器的大小受逻辑地址的位数和外存容量的限制第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
1,等分主存把主存划分成大小相等的块,称为页架
（ Page Frame),每块的大小为 2n。
2,作业的地址空间分页作业的地址空间划分成若干个与块相等的页 。 在存储分配时,每页分配一块 。
3,逻辑地址的表示逻辑地址分成两部分：页号和页内偏移量 。
逻辑地址的高位表示页号,低位表示页内偏移量第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
原理采用分页方式,把一个作业一次全部装入内存中 。
系统能满足一个作业所需的全部块数,此作业才能被装入内存,否则,不为它分配任何内存 。
地址空间是连续的,物理空间是不连续的第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
地址映射数据结构在内存中为作业创建一个页号和块号对照表－－页表页表的表项页号 块号
CPU:
逻辑地址,20位页长,1K
一个作业的长度,
3.3K
内存大小 256K:
其中空闲块为：
100,128,64,75，
190,……
该例作业的页表为页号 块号
0 100
1 128
2 64
3 75
地址映射的过程第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
地址映射数据结构 在内存中为作业创建一个页号和块号对照表－－页表页表的表项页号 块号
CPU:
逻辑地址,20位页长,1K
一个作业的长度,
3.3K
内存大小 256K:
其中空闲块为：
100,128,64,75，
190,……
该例作业的页表为页号 块号
0 100
1 128
2 64
3 75
mov AX,[3100]的 地址映射的过程第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
地址映射性能的改进，采用联想存储器第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
内存的分配和去配物理块的组织位示图法链表法第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
页面的共享共享分数据共享和程序共享数据共享,允许不同的作业对共享的数据页面用不同的页号,只要让各自页表中的有关表目指向共享的信息块即可 。
程序共享,逻辑地址空间是连续的,程序运行的当前页号是固定的 。
对共享程序,在各个作业中的页号必须是统一的 。
第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
特点优点作业的存储空间不再要求连续易于实现存储共享缺点需要硬件支持存在内零头效率降低未实现存储扩充第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
原理运行一个作业时,并不把所有页面调入内存,
而是只调入一部分,其余仍保存在外存上,
以后据作业运行的需要,再调入内存 。
处理的两个问题
A,执行到不在内 存 的 页,如何调入内存；
如何判断？ 如何处理？
B,当欲调入页,而内存不够怎么办第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
实现
1） 扩充页表页号 块号 存取控制 改变位 引用位中断位 外存地址
2） 地址映射时中断位为零,页面在内存中,遵循简单分页系统的过程 。
中断位不为零,产生缺页中断,CPU自动转到中断处理程序执行,执行完中断处理程序,
在未执行完的指令继续执行 。
第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
实现
3） 缺页中断处理完成内存和外存的对换第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
页面的淘汰算法页面的淘汰算法选择不好,容易产生颠簸 （ 抖动 ） 现象 。
刚调出的页面,马上又要用到,从而造成频繁的调入调出,消耗大量 CPU时间,使 CPU难以进行正常处理 。
系统设计要尽量避免抖动的发生 。
第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
页面的淘汰算法先进先出页面置换算法 （ FIFO）
先进入的页面先淘汰第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
页面的淘汰算法最佳置换算法 （ Opt）
选择将来不用的页面或将来最长时间不用的页面淘汰掉 。
效率最高的一种淘汰算法由于程序的执行难以实现确定,即页面的访问顺序无法事先知道,该算法难以实现 。
第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
页面的淘汰算法最近最久未用页面置换算法（ LRU)
选择最近一段时间,,最老,的页面淘汰掉 。
根据页面过去的走向,预测未来的走向 。
第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
特点优点：
和简单分页存储管理比较起来,实现了存储器的扩充 。
缺点：
管理复杂第四节 分页存储管理
1.分页基本原理
2.简单分页式管理
3.请求分页式管理
练习
CPU的逻辑地址是 24位,页的大小是 4K,物理内存 128K。
1)虚拟存储器最大是多少？
2)内存有多少块？ 虚拟存储器有多少页？
3)一个作业的最大长度是多少？
4)逻辑地址 8580在第几页？ 页内偏移量是多少？
第五节 分段存储管理
1.分段存储管理
3.段页式存储管理
原理把作业按内在的逻辑关系分成若干段,每一段是一个独立的逻辑单位 。 在进行存储分配时,每段分配一块内存 。
每一段是一个以 0为起址的连续地址空间 。
地址空间是 2维的,逻辑地址分为两部分：
段号和段内偏移量作业的存储空间段内是连续的,段间可以不连续 。
段式虚拟空间 大小为 2nX 2m
第五节 分段存储管理
1.分段存储管理
3.段页式存储管理
地址转换数据结构段表段号 段长 始址 存取控制 状态位 访问位改变位 增补位地址映射地址转换 — 分段第五节 分段存储管理
1.分段存储管理
3.段页式存储管理
段的共享采用动态链接技术,可以方便地实现共享 。
不再要求代码段在各作业中具有相同的段号 。
第五节 分段存储管理
1.分段存储管理
3.段页式存储管理
段的保护段表表目本身起到基址／限长寄存器的作用；
建立存取控制设段保护键第五节 分段存储管理
1.分段存储管理
3.段页式存储管理
分段和分业的区别
1） 页是定长的,而段不是 。
2） 页是信息的物理单位,分业是系统的要求,分页对用户透明；
段是信息的逻辑单位,分段是作业的逻辑上的要求,分段用户可见 。
3） 逻辑地址的分解不同分页：逻辑地址分成页号＋位移量是硬件功能,无越界分段：逻辑地址定义成段号＋位移量是用户定义,存在越界第五节 分段存储管理
1.分段存储管理
3.段页式存储管理
分段和分业的区别
4） 从地址空间 （ 用户 ） 的角度分页：地址空间是一维的分段：地址空间是二维的分段的地址间是二维的,但存储空间是一维的第五节 分段存储管理
1.分段存储管理
3.段页式存储管理
分段的特点优点：
1） 便于程序的模块化处理,便于处理变化的数据结构；
2） 便于动态链接和共享；
3） 实现了虚拟存储器 。
第五节 分段存储管理
1.分段存储管理
3.段页式存储管理
分段的特点缺点：
1） 增加系统开销,使操作系统复杂化；
2） 磁盘对换以段为单位,效率低；
3） 分段的最大尺寸受到内存空闲区间的影响；
4） 存在外零头 。
第五节 分段存储管理
1.分段存储管理
3.段页式存储管理
原理
1） 对内存分成固定大小的块
2） 作业的地址空间采用段式分割
3） 存储分配时,对作业的每一段又采用页式划分 。
从用户的角度看 采用分段管理从机器的角度看 采用分页管理第五节 分段存储管理
1.分段存储管理
3.段页式存储管理
特点优点综合了分段和分页的优点缺点：
系统更加复杂,系统开销更大；
内零头更严重 。
第七节 Linux存储管理总览一,Linux的地址空间结构
1G系统空间
C0000000-FFFFFFFF
3G用户空间
(0-BFFFFFFF)
3G 3G…
第七节 Linux存储管理总览二,Linux物理空间的结构
描述物理块的数据结构 page (include/linux/mm.h)
每一个物理块，都有一个 page结构的数据。
typedef struct page {
……
} mem_map_t;
第七节 Linux存储管理总览二,Linux物理空间的结构
物理页面仓库 ---数组 mem_map
系统初始化时，根据物理内存的大小，建立一个 page结构的数组，作为物理页面的仓库。
Mem_map中的每个元素，代表着一个页面；元素的下标，代表该物理块的序号。
第七节 Linux存储管理总览二,Linux物理空间的结构
物理块的分区管理在物理块管理时，为了满足不同的要求，提高系统效率，把
mem_map划分成不同区域（ ZONE）。
划分成三个分区 (include/linux/mmzone.h)
#define ZONE_DMA 0
#define ZONE_NORMAL 1
#define ZONE_HIGHMEM 2
第七节 Linux存储管理总览二,Linux物理空间的结构
空闲块的链式结构为了提高内存块分配的效率，每个区中的空闲块组成若干个链表。
每个管理区都有一个数据结构 zone_struct来描述，在 zone_struct中，
有一组空闲区间队列。为什么是一组而不是一个队列呢？这是因为常常需要成块的分配在物理空间中连续的多个页面，所以，要按块的大小分别加以管理。
因此，在 zone_struct中有 MAX_ORDER个对列，每个队列分别用来管理连续块长度分别为 1,2,4,8……2 MAX_ORDER空闲块。
用到的数据结构如下 (include/linux/mmzone.h)
第七节 Linux存储管理总览
＃ define MAX_ORDER 10
typedef struct free_area_struct {
struct list_head free_list;
unsigned long *map;
} free_area_t;
typedef struct zone_struct {
......
struct list_head inactive_clean_list;
free_area_t free_area[MAX_ORDER];
spinlock_t lru_lock;
......
} zone_t;
第七节 Linux存储管理总览二,Linux物理空间的结构
空闲块的链式结构第七节 Linux存储管理总览三,Linux虚存结构
地址映射模型虚存划分的二级结构 (页号和页内偏移量），无法满足大地址空间的要求。
因此,LINUX采用三级地址结构。
第七节 Linux存储管理总览三,Linux虚存结构
地址空间结构物理空间是从“供”的角度来管理的，页就是“仓库中还有什么”；虚存空间的管理是从“需”的角度来管理的，就是我们
“需要虚存空间的那些部分”。
进程并不会用完全部 3G的虚存空间，同时，一个进程所使用的虚存空间中的各部分又未必是连续的，通常形成若干个离散的虚存“区间”。
因此，通过 vm_area_struct，描述一个虚存区间
(include/linux/mm.h)。
第七节 Linux存储管理总览
struct vm_area_struct {
struct mm_struct * vm_mm; /* The address space we belong to,*/
unsigned long vm_start; /* Our start address within vm_mm,*/
unsigned long vm_end; /* The first byte after our end address within vm_mm,*/
struct vm_area_struct *vm_next;
pgprot_t vm_page_prot; /* Access permissions of this VMA,*/
unsigned long vm_flags; /* Flags,listed below,*/
rb_node_t vm_rb;
……
struct vm_operations_struct * vm_ops;
struct file * vm_file; /* File we map to (can be NULL),*/
unsigned long vm_raend; /* XXX,put full readahead info here,*/
void * vm_private_data; /* was vm_pte (shared mem) */
};
第七节 Linux存储管理总览三,Linux虚存结构
地址空间结构还有一个数据结构,mm_struct(include/linux/sched.h)，描述整个进程的虚存情况，因此，它是比 vm_area_struct更高层次上使用的数据结构。
一个进程只有一个 mm_struct，但一个 mm_struct可能对应几个进程。
第七节 Linux存储管理总览
struct mm_struct {
struct vm_area_struct * mmap; /* list of VMAs */
rb_root_t mm_rb;
struct vm_area_struct * mmap_cache; /* last find_vma result */
unsigned long free_area_cache; /* first hole */
pgd_t * pgd;
atomic_t mm_users; /* How many users with user space? */
atomic_t mm_count; /* How many references to "struct mm_struct" (users count as 1) */
int map_count; /* number of VMAs */
struct rw_semaphore mmap_sem;
spinlock_t page_table_lock; /* Protects task page tables and mm->rss */
struct list_head mmlist; /* List of all active mm's,These are globally strung
unsigned long start_code,end_code,start_data,end_data;
unsigned long start_brk,brk,start_stack;
unsigned long arg_start,arg_end,env_start,env_end;
……
};
第七节 Linux存储管理总览三,Linux虚存结构
地址空间结构进程的 task_struct
中又一个指针
mm，指向该进程的 mm_struct，
mm_struct中的
mmap指向
vm_area_struct队列。
第七节 Linux存储管理总览三,Linux虚存结构
地址空间结构
mm_struct和
vm_area_struct说明了对页面的需求； page、
zone_struct等说明了对页面的供应；而页面目录、
中间目录、页面表则是二者之间的桥梁。
单一连续分区
OS区用户区返回动态重定位返回作业
Mov ax,[0h]
0H
1K-1
100H
内存
0H
Mov ax,[0h]
CPU
基地址寄存器逻辑地址动态重定位返回作业
Mov ax,[0h]
0H
1K-1
100H
内存
0H
Mov ax,[0h]
CPU
基地址寄存器
100H
0H
逻辑地址
＋
固定分区返回
OS区 16K
4K
8K
8K
16K
12K
分段式存储管理地址映射返回分页存储管理地址映射返回页表大小 页表始址
L b
执行指令 MOV AX，［ 3100］
页号 页内偏移量
3 28 逻辑地址页表寄存器页号 块号
0 100
1 128
2 64
3 75
物理地址内存 0
256K－ 1
75 28
76828
(01001011 0000011100)
(01001011 0000011100)
