2、可重定位装入：


3.动态运行时装入

0
1000 LOAD 1, 2500
10000 11000 LOAD 1, 2500
2500
365
12500 15000
365
5000 作业地址空间 图4-2
内存空间
4.1.2

程序的链接
1、静态链接
程序运行之前，链接成完整的装入模块 a．对相对地址的修改 b．变换外部调用符号
不能容纳作业。

紧凑 通过作业移动将原来分散的小分区拼接成一个 大分区。
紧凑
操作系统 用户程序1 10KB 3 用户程序 用户程序 10KB 3 30KB 用户程序6 14KB 用户程序9 26KB
操作系统
用户程序1
用户程序3 用户程序6 用户程序9
80KB
必须对移动了的作业进行重定位。动态（因作业已经装入， 随着对指令或数据的访问自动进行）
空闲分区总和 否 >=u.size? 是 紧凑形成连 续空闲区 修改有关的 数据结构
将该分区从链中移出
2．回收： （1）上邻空闲区：合并，改大小 （2）下邻空闲区：合并，改大小，首址。 （3）上、下邻空闲区：合并，改大小。 （4）不邻接，则建立一新表项。
F1
回收区 回收区 F2
F1
回收区 F2
内存回收时的情况
4.2.4

可重定位分区分配
1.动态重定位的引入

连续式分配中，总量大于作业大小的多个小分区

2、装入时动态链接
目标模块在装入内存时，边装入边链接 a.便于修改和更新 b.便于实现对目标模块的共享

3、运行时动态链接
程序执行需要时，才将某些目标模块进行链接
0
模块A CALL B; RETURN
0
模块A JSR L; RETURN L-1 L
L-1
0
M-1 0
模块B CALL C; RETURN

2算法

4.2.3 动态分区分配

三、分区分配
1．分配： 请求分区 u.size 空闲分区 m.size
从头开始查表 Y
检索完否？ N m.size>u.size? Y m.sizeu.size<=size? N
返回
N
继续检索下一个表项
Y
从该分区中划出u.size大小的分区 将该分区分配，并修改相关结构 返回
分区4
800k 700k
分区4
分区3
分区3
400k
分区2 分区2
200k
分区1 操作系统
100k 0
分区1 操作系统
4.2.3 动态分区分配（比固定式 分区有改善）
根据进程需要，动态地为之分配内存空间 一、数据结构


1．空闲分区表 2．空闲分区链
前向 指针 N+2 0
N个字节可用
后向 指针 N+2 0
0
4.2.2
固定分区
20K
特点：内存划为n个分区，可同时装入n个作业/任务。 操作系统 一、分区大小： 分区 大小（K) 起址（K）状态
号 a. 1 b.
I.
相等:缺乏灵活性 不相等：利用率更高。 12 20 已分配
作业A 作业B
二、内存分配： 2 32 32
3 4 II.
III.
32K
已分配 将分区按大小排序，建立分区使用表，并将起始地址、大 64K 64 64 已分配 小、分配标识作记录 检索分区使用表找能满足要求的尚未分配的分区 作业C 128 128 已分配 放到能容纳作业的最小分区的队列中。
链接 程序
装入 模块
装入 程序
4.1.1


程序的装入
1、绝对装入：
编译后，装入前已产生了绝对地址（内存地址），装入时 不再作地址重定位。 绝对地址的产生：（1）由编译器完成，（2）由程序员编 程完成。 对（1）而言，编程用符号地址。
静态重定位：装入时完成，主要工作是对相对地址中的指 令和数据地址的调整过程，例：图4－2 在执行时才完成相对—绝对地址的转换，且有硬件的支持, 能保证进程的可移动性。
嵌入式系统中 算机上，现在很 一般不设置保护也可，因单任务。 少用 0xfff… 用户 程序 位于ROM中 的操作系统
早期的PC中， BIOS (basic input output system) 位于ROM中 的设备驱动 程序 用户 程序 位于RAM中 的操作系统
位于RAM中 的操作系统 0
用户 程序 0
第四章 存储器管理
第四章 存储器管理



装入和链接 连续分配方式 基本分页存储管理方式 基本分段存储管理方式 虚拟存储器 请求分页存储管理方式 页面置换算法 请求分段存储管理方式
4.1 程序的装入和链接

编辑―――编译―――链接―――装入―――运行
内存
库 编译程 序产生 的目标 模块
模块B JSR L+M; RETURN
L+M-1 L+M
模块C
RETURN
模块C
RETURN (b)装入模块
N-1 (a)目标模块
L+M+N-1
4.2 连续分配方式

单一连续分配

用于单用户，单任务中

分区式分配


固定式 动态式 动态重定位
4.2.1

单一连续分配
单用户单任务 系统区+用户区 存贮保护掌上型计算机和 大型机和小型计
128K
分区说明表
256K
~ ~ 分配情况
~ ~
输入队列的组织


每个分区有独立输入队列：小分区的队列长，大分 区的队列空，浪费 只维护一个输入队列：




一旦有分区空闲，就把该分区能容纳的作业中最接近队 列前面的作业调入分区：小作业浪费大分区 对队列进行搜索，一旦有分区空闲，就取该分区所能容 纳的最大的一个作业运行：对小作业不利 至少保留一个小分区，允许小作业运行，而不至于为小 作业分配大分区 规定一个作业至多允许被跳过的次数，之后就不能被跳 过了
4.2.3 动态分区分配

二、分配算法

1．首次适应算法FF。

要求：分区按低址――高址链接 特点：找到第一个大小满足的分区，划分。有外零头， 低址内存使用频繁。 从1中上次找到的空闲分区的下一个开始查找。 特点：空闲分区分布均匀，提高了查找速度；缺乏大的 空闲分区。 分区按大小递增排序；分区释放时需插入到适当位置。

2、动态重定位的实现
0 100
load 1,2500
相对地址 重定位寄存器 10000
2500 10000
10100
12500 +
365
load 1,2500
2500
365
5000
15000
作业J
处理机一侧
存储器一侧
主存
动态分区分配算法流程图
请求分配u.size 检索空闲分区链(表)
无法分配， 否 返回