第四章 存储器管理
第四章 存储器管理
装入和链接
连续分配方式
基本分页存储管理方式
基本分段存储管理方式
虚拟存储器
请求分页存储管理方式
页面置换算法
请求分段存储管理方式
程序的装入和链接
编辑―――编译―――链接―――装入―――运行
程序的装入
1、绝对装入：
编译后，装入前已产生了绝对地址（内存地址），装入时不再作地址重定位。
绝对地址的产生：（1）由编译器完成，（2）由程序员编程完成。
对（1）而言，编程用符号地址。
2、可重定位装入：
静态重定位：装入时完成，主要工作是对相对地址中的指令和数据地址的调整过程，例：图4－2
3.动态运行时装入
在执行时才完成相对—绝对地址的转换，且有硬件的支持,能保证进程的可移动性。
0
1000
2500
5000
LOAD 1, 2500
LOAD 1, 2500
365
365
10000
11000
12500
15000
作业地址空间
内存空间
图4-2
程序的链接
1、静态链接
程序运行之前，链接成完整的装入模块
a．对相对地址的修改
b．变换外部调用符号
2、装入时动态链接
目标模块在装入内存时，边装入边链接
a.便于修改和更新
b.便于实现对目标模块的共享
3、运行时动态链接
程序执行需要时，才将某些目标模块进行链接
模块A
CALL B;
RETURN
模块B
CALL C;
RETURN
模块C
RETURN
0
L-1
0
M-1
0
N-1
(a)目标模块
模块A
JSR L;
RETURN
模块B
JSR L+M;
RETURN
模块C
RETURN
0
L-1
L
L+M-1
L+M
L+M+N-1
(b)装入模块
连续分配方式
单一连续分配
用于单用户，单任务中
分区式分配
固定式
动态式
动态重定位
单一连续分配
单用户单任务
系统区+用户区
存贮保护
一般不设置保护也可，因单任务。
用户程序
位于RAM中的操作系统
0
0xfff…
用户程序
位于ROM中的操作系统
0
用户程序
位于RAM中的操作系统
0
位于ROM中的设备驱动程序
大型机和小型计算机上，现在很少用
掌上型计算机和嵌入式系统中
早期的PC中，BIOS (basic input output system)
固定分区
特点：内存划为n个分区，可同时装入n个作业/任务。
一、分区大小：
相等:缺乏灵活性
不相等：利用率更高。
二、内存分配：
将分区按大小排序，建立分区使用表，并将起始地址、大小、分配标识作记录
检索分区使用表找能满足要求的尚未分配的分区
放到能容纳作业的最小分区的队列中。
作业C
作业B
作业A
操作系统
20K
32K
64K
128K
256K
~
~
~
~
分配情况
已分配
128
128
4
已分配
64
64
3
已分配
32
32
2
已分配
20
12
1
状态
起址（K）
大小（K)
分区号
分区说明表
输入队列的组织
每个分区有独立输入队列：小分区的队列长，大分区的队列空，浪费
只维护一个输入队列：
一旦有分区空闲，就把该分区能容纳的作业中最接近队列前面的作业调入分区：小作业浪费大分区
对队列进行搜索，一旦有分区空闲，就取该分区所能容纳的最大的一个作业运行：对小作业不利
至少保留一个小分区，允许小作业运行，而不至于为小作业分配大分区
规定一个作业至多允许被跳过的次数，之后就不能被跳过了
操作系统
分区1
分区2
分区3
分区4
0
100k
200k
400k
700k
800k
操作系统
分区1
分区2
分区3
分区4
动态分区分配（比固定式分区有改善）
根据进程需要，动态地为之分配内存空间
一、数据结构
1．空闲分区表
2．空闲分区链
0
0
N+2
N+2
后向指针
N个字节可用
前向指针
动态分区分配
二、分配算法
1．首次适应算法FF。
要求：分区按低址――高址链接
特点：找到第一个大小满足的分区，划分。有外零头，低址内存使用频繁。
2．循环首次适应算法。
从1中上次找到的空闲分区的下一个开始查找。
特点：空闲分区分布均匀，提高了查找速度；缺乏大的空闲分区。
3．最佳适应算法
分区按大小递增排序；分区释放时需插入到适当位置。
动态分区分配
三、分区分配
1．分配：
请求分区
空闲分区
回收区
F1
F2
回收区
F2
回收区
F1
内存回收时的情况
2．回收：
（1）上邻空闲区：合并，改大小
（2）下邻空闲区：合并，改大小，首址。
（3）上、下邻空闲区：合并，改大小。
（4）不邻接，则建立一新表项。
可重定位分区分配
1.动态重定位的引入
连续式分配中，总量大于作业大小的多个小分区不能容纳作业。
紧凑
通过作业移动将原来分散的小分区拼接成一个大分区。
紧凑
用户程序9
26KB
14KB
用户程序6
30KB
用户程序3
10KB
用户程序1
操作系统
80KB
用户程序9
用户程序6
用户程序3
用户程序1
操作系统
10KB
用户程序3
必须对移动了的作业进行重定位。动态（因作业已经装入，随着对指令或数据的访问自动进行）
2、动态重定位的实现
365
load 1,2500
365
load 1,2500
0
100
2500
5000
2500
10000
10000
10100
+
12500
15000
作业J
处理机一侧
存储器一侧
重定位寄存器
相对地址
主存
动态分区分配算法流程图
对换
1 对换的引入
将阻塞进程，暂时不用的程序，数据换出。
将具备运行条件的进程换入。
类型：
整体对换：进程对换，解决内存紧张
部分对换：页面对换/分段对换：提供虚存支持
操作系统
A
操作系统
A
B
操作系统
A
B
C
操作系统
B
C
操作系统
D
C
操作系统
A
C
D
内存分配情况随着进程进出而变化
对换
2 对换空间的管理
外存
对换区比文件区侧重于对换速度。
因此，对换区一般采用连续分配。采用数据结构和分配回收类似于可变化分区分配。
对换
3 换出与换入
1）换出
a．选出被换出进程：
因素：优先级，驻留时间，进程状态
b．换出过程：
对于共享段：计数减1， 是0则换出，否则不换
修改PCB和MCB（或内存分配表）
2）换入：
a．选择换入进程：优先级，换出时间等。
b．申请内存。
c．换入
基本分页存储管理
连续分配引起:碎片
碎片问题的解决：紧凑方式,消耗系统开销。
换一种思路：离散分配
允许将一个进程直接分散的装入到许多不相邻的分区中
分页
分段
段页
页面与页表
1).页面(page)
进程的逻辑空间分成若干个大小相等的页面，编号
内存空间分为同等大小的物理块(frame)，编号
页面大小要适中：
页太小：内存碎片小，页表可能很长，换入/出效率低
页太大：页内碎片大。
2 的幂
2).地址结构
逻辑地址A 页面大小L
页号P和页内地址d:
P=INT[A/L] d=[A]mod L
如： L=1024B,A＝2170B. 则P=2, d=122
位移 W
页号 P
16 12 11 0
3).页表
为每个进程建立一张页面映像表
进程逻辑地址内存中对应的块号
函数，实现从页号到物理块号的地址映射
存取控制字段
读/写/执行
n页
5页
4页
3页
2页
1页
0页
5
9
4
8
3
6
2
3
1
2
0
9
8
7
6
5
4
3
2
1
0
用户程序
页表
页号
块号
内存
地址变换机构
实现：逻辑页号——物理块号的映射，借助页表完成。
1、基本地址变换机构：
每个进程对应一页表，其信息（如长度、始址）放在PCB中，执行时将其首地址和页表长度装入页表寄存器。
越界保护
例：已知某分页系统，内存容量为64KB，每页为1KB。对一个4页大的作业，其调入内存的页面对应的物理块号如下表：
将十进制的逻辑地址1023，4500转换为物理地址
以十进制的逻辑地址1023为例，画出地址转换图
7
3
6
2
4
1
2
0
物理块号
页号
1）对上述逻辑地址，可先计算出它们的页号和页内地址，然后通过页表转换成对应的物理地址：
1023：1023/1K=页号0，页内地址1023，物理快号2，则物理地址为：2*1K+1023=3071
4500： 4500 /1K=页号4，页内地址404，页号>页表长度，则越界中断
4
0 1023
2 1023
2
4
6
7
≤
2.具有快表的地址变换机构
不具快表，则需两次访问内存。
（1）访问页表，得到物理地址
（2）访问物理地址，得到所需内容
降低1/2的性能，发现只有少量的页表表项被反复读取
解决办法：设置一硬件设备，将虚拟地址直接映射到物理地址，速度提高。
联想寄存器（快表）
快表贵，不能太多。
2.具有快表的地址变换机构
例：有一页式系统，其页表存放在主存中：
①如果对主存的一次存取需要 μs,试问实现一次页面访问的存取时间是多少?
②如果系统加有快表,平均命中率为85%,当页表项在快表中时,其查找时间忽略为0, 试问此时的存取时间是多少?
答：若页表存放在主存中，则要实现一次页面访问需两次访问主存：一次是访问页表，确定所存取页面的物理地址（称为定位）。第二次才根据该地址存取页面数据。
■页表在主存的存取访问时间
=*2=3(μs)
■增加快表后的存取访问时间
=*+()*2*=(μs)
两级和多级页表
页表可能很大，将其离散存放在不同页块中。
建一“外部页表”来管理这些离散页表块。
相当于单级页表中的页表寄存器，一般应常驻内存。每项记录页表始址，且增加存在位。
64位机器页表一般>3级，最外层页表常驻。
基本分段存储管理
为了满足用户（程序员）在编程和使用上的要求
即多重定位分区管理
引入
每个段可有其逻辑意义及功能，使得便于
（1）方便编程；
（2）分段共享；
（3）分段保护；
（4）动态链接；
（5）动态增长；（如数据段的增长）
分段系统的基本原理
分段
地址空间被划分为若干个段，每段定义了一组逻辑信息。
段号+段内地址。
段表：
Mapping: 逻辑段物理内存区
每段分配一个连续分区，各段离散在不同分区中
地址变换机构：
分页与分段区别：
（1）页是信息的物理单位，段是逻辑单位
（2）页长度固定，段长度不固定（由用户指定）
（3）一维与二维
(Main)=0
30K
(X)=1
20K
(D)=2
30K
(S)=3
30K
40K
80K
120K
150K
0
信息共享
段式系统易于共享
例：图4-18及4-19 分页与分段共享比较
可重入码（纯代码）
各个进程应保留局部数据区
40个用户，程序中160K代码，40K数据,每页4K,则代码40个页面，数据区10个页面
data10
…
data1
ed40
…
ed2
ed1
70
…
61
60
…
22
21
ed40
data10
…
data1
data10
…
data1
…
ed2
ed1
…
进程1
进程2
页表
页表
data10
…
data1
ed40
…
ed2
ed1
80
…
71
60
…
22
21
主存
分页系统中共享editor
分段系统中共享editor
data1
editor
data2
editor
240
40
80
160
基址
段长
380
40
80
160
基址
段长
data2
…
data1
editor
段页式存储管理
一、基本原理
先将用户程序分成若干段，再把每个段分成若干页，并为每一段赋予一个段名
段号(S)
分页的优点：提高内存利用率
分段的优点：方便和满足用户
0
4K
8K
12K
15K
0
4K
8K
0
4K
8K
10K
段内页号(P)
页内地址(W)
主程序段
子程序段
数据段
？各取所长
段页式存储管理
二、地址变换
段表寄存器：存放段表始址和段长
4
3
2
1
0
页表始址
页表大小
段号
4
3
2
1
0
存储块号
页号
4
3
2
1
0
存储块号
页号
段表始址
段表大小
操作系统
段表寄存器
段表
页表
主存
利用段表和页表实现地址映射
段页式存储管理
二、地址变换
段表寄存器：存放段表始址和段长
段号S与段长进行比较，越界？
未越界，则
用段表始址和段号S求段表项的位置，读出该段的页表始址
用段内页号P求页表项的位置，读出物理块号b
用块号b和页内地址W构成物理地址
4
3
2
1
0
页表始址
页表大小
段号
4
b
3
2
1
0
存储块号
页号
段表长度
段表始址
段表寄存器
段表
页表
+
+
>
页号(P)
页内地址(W)
段号(S)
块内地址
块号b
段超长
段页式系统的地址变换机构
段页式存储管理
三次访内存操作
访问内存中的段表，得页表始址
访问内存中的页表，得到物理地址
访问物理地址，得到所需内容
为提高速度，在地址变换机构中增设一高速缓冲寄存器（Cache）
虚拟存储器
怎么办？
增加物理内存 or 逻辑上增加内存
全部装入内存后才能运行
？大作业：超出内存容量
？作业多：不能全部容纳
虚拟存储器的引入
1.常规存储管理的特征：
一次性（指全部装入）
不是所有的程序和数据都能用到，一次性装入是一种浪费
驻留性（指驻留在内存不换出）
I/O等待或仅运行一次的进程长期占据内存资源是一种浪费
问题：
是否需要一次性将作业全部装入
作业是否需要长期地驻留在内存
虚拟存储器的引入
2.局部性原理
程序在执行时将呈现出局部性规律：即在一较短时间内，程序的执行仅限于某个部分；相应地，它所访问的存储空间也局限于某个区域。
程序在执行时，除了少部分的转移和过程调用指令外，在大多数情况下仍是顺序执行的。
过程调用将会使程序的执行有一部分内存区域转至另一部分区域，在大多数情况下，过程调用的深度都不超过5。
循环结构将执行多次
程序中对数据结构的处理，往往都局限于小的范围内。
局部性表现
时间局部性：（循环）指令一旦执行，不久以后可能再次执行；数据结构被访问，则不久以后可能再次被访问
空间局部性：（顺序）一旦程序访问了某个存储单元，不久之后，其附近的存储单元也被访问
虚拟存储器的引入
3、虚拟存贮器
基于局部性原理，一个作业在运行之前，没有必要全部装入内存，而仅将那些当前要运行的那部分页面或段，先装入内存便可启动运行，其余部分暂时留在磁盘上。
定义：具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储系统。
实质：以时间换空间，但时间牺牲不大。
虚拟大小由内存容量和外存容量之和决定。
虚拟存储器的实现方法
虚拟存储器的实现，毫无例外地都是建立在离散分配存储管理方式的基础上的。
？？连续分配方式
需要动态重定位
虚拟存储器的实现方式
一、请求分页系统
在分页系统的基础上，增加请求调页功能和页面置换功能。
以页为单位进行置换
需硬件：
（1）请求分页的页表机制
（2）缺页中断机构
（3）地址变换机构
需实现请求分页机制的软件（置换软件等）
二、请求分段系统
在分段系统的基础上，增加请求调段功能和分段置换功能。
以段为单位进行置换
需硬件：
（1）请求分段的段表结构
（2）缺段中断机构
（3）地址变换机构
需实现请求分段机制的软件（置换软件等）
三、段页式虚拟存储器
虚拟存储器的特征
虚拟存储器最基本的特征是离散性，在此基础上又形成了多次性及对换性的特征。其所表出来的最重要的特征是虚拟性。
1、离散性
离散性是指在内存分配是采用离散分配方式，这是其他几个特征的基础。没有离散性，也就不可能实现虚拟存储器。
2、多次性
多次性是指一个作业被分成多次地调入内存运行
3、对换性
对换性是指允许在作业的运行过程中换进、换出。换进、换出能有效地提高内存利用率
4、虚拟性
虚拟性是指能够从逻辑上扩允内存容量，使用户所看到的内存容量远大于实现内存容量。
请求分页存储管理
在分页系统的基础上，增加请求调页功能和页面置换功能。
以页为单位进行置换——长度固定
实现简单，最常用
需硬件：
（1）请求分页的页表机制
（2）缺页中断机构
（3）地址变换机构
请求分页中的硬件支持
一、页表机制
页表项：
二、缺页中断机构：
每当所要访问的页面不在内存时，便要产生一缺页中断，请求OS将所缺之页调入内存。
外存地址
修改位M
访问字段A
状态位P
物理块号
页号
涉及6次缺页中断的指令
To B
copy A
A:
B:
6
5
4
3
2
1
请求分页中的硬件支持
三、地址变换机构
比简单分页机制，增加了缺页中断处理和页面置换
过程：
先检索快表，如果找到该页，则修改页表项中的访问位、修改位等，再计算形成物理地址；如果未找到，则应再到内存中去查找页表，看其页表项中的状态位P，确定该页是否调入内存。如果：
（1）该页已经调入内存：应将此页的页表项写入快表，当快表已满时，应先调出一个按某种算法所确定的页的页表项，然后再写入该页的页表项。
（2）该页尚未调入内存，这时便应产生缺页中断，请求OS从外存中把该页调入内存。
内存分配策略和分配算法
一、最小物理块数
是指能保证进程正常运行所需的最小物理块数。
单地址指令且采用直接寻址方式，最小物理块数为2
允许间接寻址时，则至少要求有3个物理块。
指令长度≥2，源地址和目的地址涉及的区域跨页面，则至少要求6个
内存分配策略和分配算法
二、物理块的分配策略
分配策略：固定和可变分配策略。
置换策略：全局置换和局部置换。
于是可组合出以下三种页面分配和置换策略。
1．固定分配局部置换。
缺点：难以确定固定分配的页数.(少：频繁缺页，置换率高 多：浪费)
2.可变分配全局置换
预先分配好，缺页时从系统空闲队列里取出分配，用完时选一页调出置换
3.可变分配局部置换
根据进程的缺页率进行页面数调整，进程之间相互不会影响。
三、分配算法
1．平均分配算法
将系统中所有可供分配的物理块，平均分配给各个进程：没考虑进程大小
2．按进程大小比例分配算法：
系统中各进程页面数的总和为：
每个进程所能分配到的物理块数为bi：
3．考虑优先权分配算法
把可供分配的物理块分成：一部分按比例地分给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。
调页策略
1.调入时机：
预调：采用一种以预测为基础的预调页策略，预计在不久之后便会被访问的程序或数据所在的页面，预先调入内存 成功率50％
请求调：当进程在运行中需要访问某部分程序的数据时，发现其所在的页面不在内存，需立即提出请求，由系统将其所需页面调入内存。较费系统开销
各有优劣
调页策略
2．从何处调页：
对换区空间足够大：全部从对换区调入所需页面，以提高调页速度。为此，在进程运行前，将进程有关文件从文件区拷贝到对换区。
对换区空间不够大：不会被修改的文件，直接从文件区调入；可能被修改的部分，换出时须先调到对换区，需要时从对换区调入。
UNIX方式：与进程有关的文件放在文件区，未运行过的页面，从文件区调入；运行过的而又被换出的页面，放在对换区，下次调入时从对换区调入。
3.页面调入过程
所需页面未在内存时，缺页中断，查找页表得到该页外存物理块号，再找置换页（回写问题），完成调入，改页表
页面置换算法
目的：减少对换量，提高系统性能
最佳置换算法和先进先出算法
一、最佳置换算法（理论上的）
缺页率：6/12
页置换算法
二、先进先出算法FIFO
缺页率：9/12
最近最久未用LRU置换
将“最近的过去”，作为“最近的将来”。
选择最近最久未使用的页面予以淘汰
所要解决的问题有：
一个进程在内存中的各个页面各有多久时间未被进程访问；
如何快速地知道哪一页最近最久未使用的页面
硬件支持：
1．位移寄存器：（定时右移）
R=Rn-1…R0
2．栈：
当进程访问某页时，将其移出压入“栈顶”，“栈底”换出。
LRU
缺页率：7/12
1
0
1
1
0
1
1
0
8
1
1
1
0
0
0
0
0
7
1
1
0
1
0
1
0
0
6
0
1
1
0
1
0
1
1
5
1
1
0
1
0
1
1
0
4
0
0
1
0
0
O
0
0
3
0
0
1
1
0
1
0
1
2
0
1
0
0
1
0
1
0
1
R0
R1
R2
R3
R4
R5
R6
R7
实页/R
4
4
7
4
7
0
4
0
7
4
0
7
1
4
7
1
0
7
1
0
6
4 7 0 7 1 0 6
clock置换算法
LRU的近似算法：硬件消耗少
一、简单算法：
设一访问位。被访问：置1
循环扫描，每次扫描时将访问位复位0。
选择访问位为0的页面换出
clock置换
二、改进：
访问位A；修改位M
首选 A=0; M=0
不改变A
扫描过的A=0
A=0
M=0
A=0
M=1
N
N
A=1
M=0
A=1
M=1
其它
一、最少使用（是频率）
与LRU类似（记录访问次数），设置一个访问计数器。
二、页面缓冲算法：
特点：淘汰的页只是修改标志；若页被修改过，则在欲复盖它时回写，否则成批回写。
在欲重访问该页时，若页换出则只需修改标志。
请求分段存储管理方式
段表：
二、缺段中断机构：
段不定长，处理起来比缺页中断复杂。图
三、地址变换机构
图
外存起址
增补位
存在位P
修改字段M
访问字段A
存取方式
段基址
段长
段名
分段的共享与保护
一、共享段表：（整个系统一张）
1.共享进程计数。
2.存取控制字段。
3.段号：不同的进程可以使用不同的段号去共享段。
存取控制
段号
进程号
进程名
状态
共享进程计数
外存地址
状态
内存地址
段长
段名
共享段表
共享段表项
分段的共享与保护
二、共享段的分配与回收
1.分配：
第一次访问：分配内存，（1）增加共享段表；（2）修改进程段表。
第二次访问：（1）修改共享段表；（2）修改进程段表。
2.回收： 释放该段：
撤销进程段表项 & count:=count-1
（1）count=0 回收内存，撤销共享段表项 （2）count≠0 取消调用者进程的共享段表中相关内容
分段的共享与保护
三、分段保护
1.越界检查
段号越界检查。
段内偏移越界检查。
2.存取控制检查。
R；R/W；E
3.环保护机构
（1）内环可访问外环数据；
（2）外环可请求内环服务。
作业
P142— 5, 11，23
23题加一问：采用OPT、LRU算法的缺页次数和缺页率
