内存管理
内存的分配与回收
地址映射
编译器在对程序进行编译的时候，通常从 0开始为程序代码编址，程序中设计的所有地址都是相对起始地址0确定的，这种地址称为虚地址、相对地址或逻辑地址。相应地，这些地址构成的地址空间称为虚地址空间、程序空间或者逻辑地址空间。
当程序加载到内存中时，通常不是从 0开始的内存空间，程序在物理内存中的空间称为实地址、绝对地址或者物理地址，构成的地址空间称为是地址空间、内存空间或物理空间。虚地址空间可能是一维的连续空间，也可能是二维的非线性空间，这是存储器管理方式所决定的。而实地址空间总是一维线性的。
程序运行过程中使用的地址都是虚地址，而程序加载到物理内存的实际地址往往与虚地址不同，因此虚地址不能直接用于访存。
这个从虚地址映射到实际物理地址的地址转换功能称为地址映射，又称为地址重定位。
这个过程应该由操作系统负责，这样程序员只需要关注指令、数据的逻辑地址
程序运行过程中
内存的共享和保护
内存扩充
32位机器的4GB限制主要指虚拟地址空间，这是程序能直接“看到”的最大范围。
物理内存
每个地址1B
CPU最多可以访问 2^32字节内存，这个最多可以访问指的就是寄存器
所以是4GiB
而寄存器可以存储32位
RAM 只有1GiB甚至更少
我们将RAM称为物理内存，RAM的地址称为物理地址。
不用RAM内存和地址因为CPU还可以访问其它
什么是内存
内存中保存代码的指令和相关数据
根据物理地址
基于虚拟寻址
CPU发出的地址是逻辑/虚拟地址
但对于主存希望得到访存的地址依然是物理地址
将虚拟地址转换成物理地址，翻译的部件叫做MMU 内存管理单元
（虚拟）地址空间
{0，1，2….}
虚拟地址空间最大值，取决于虚拟地址的位数
虚拟地址的位数取决于什么呢？
处理器设计时定义了地址总线的位数（或虚拟地址的位数）。
32 位机器通常指处理器具有 32 位的通用寄存器、数据总线和地址总线。
32位机器（处理器），最大地址2^32-1
物理地址空间大小 取决于内存的大小
4G内存条——就有4G的内存空间
但绝不是操作系统使用的就是 4GB（并不是最大支持 4GB）
{0,1,2...}地址空间
| 虚拟地址的比特数 | 虚拟地址数 |
| ---------------- | ---------- |
| 8 | 2^8 |
| 32 | 2^32 |
物理地址：{0，1，2...,M-1}
在编译的过程中会有虚拟地址的概念
这是hello.o的反汇编，并没有赋予地址的概念
然而 hello 的反汇编，赋予了地址
好像是一个地址对应一个字节
CPU 在执行这些指令，读写的都是虚拟地址
0x200af5(%rip)，得到的是虚拟地址，还要经过 MMU 转换成物理地址
我就不需要考虑 4G/8G 等等内存大小
进程独占一个虚拟地址空间
# 程序的装入和链接
如何把逻辑地址转换为物理地址？
1、绝对装入
在编译时，编译程序将产生绝对地址的目标代码，装入程序按照装入模块中的地址
2、静态重定位
把地址重定位放在装入模块到内存的适当位置时不能移动位置
3、动态重定位
重定位寄存器
真正执行指令时，再将指令本身那个或指令中操作数的逻辑地址转换为物理地址
允许程序在内存中发生移动
需要一个数据结构将虚拟地址和物理地址对应关系
页表，放在内存里，记录虚拟页和物理页的映射关系
内存空间的分配与回收
从逻辑上对内存空间进行扩充
负责逻辑地址和物理地址转换——三种装入方式页式存储/段式存储 动态重定位
内存保护 设置上下限寄存器2、重定位寄存器（基址寄存器）和界地址寄存器（限长寄存器）进行越界检查
重定位寄存器存放到时进程的实际物理地址
界地址寄存器中存放的是最大物理地址
# 连续存储器管理方式
- 单一连续分区
- 固定分区
- 动态分区
- 分页存储管理
提高内存利用率
---
- 分段存储管理 方便用户
- 段页式存储管理 既提高内存利用率，又方便用户
---
- 请求调页
- 请求调段
- 请求段页式
逻辑上扩充内存，实现虚拟存储器方便用户运行大程序
提高内存作业道数，从而进一步提高资源利用率
# 单一连续分区
内存被分为系统区和用户区，内存中只能有一道用户程序
| 系统区 |
| --------- |
| 用户进程A |
| 用户区 |
从上到下：低地址——>高地址
有很大一部分用户区空闲，内存利用率低
固定分区
分区大小相等、分区大小不等
每个分区只装入一道程序
| 内存(分区大小相等) | 内存(分区大小不等) |
| ------------------ | ---------------------------------------------- |
| 系统区8MB | 8MB |
| 分区10MB | 分区1 2MB
分区 2 2MB
分区3 4MB |
| 分区2 10MB | 分区4 6MB |
| 分区3 10MB | 分区5 8MB |
| 分区4 10MB | 分区6 12MB |
操作系统需要建立一个数据结构一一分区说明表，来实现各个分区的分配与回收。每个表项对应一个分区，通常按分区大小排列。每个表项包括对应分区的大小、起始地址、状态（是否已分配）
| 分区号 | 大小（MB） | 起始地址（M） | 状态 |
| 1 | 2 | 8 | 未分配 |
| 2 | 2 | 10 | 未分配 |
| 3 | 4 | 12 | 已分配 |
| …… | …… | …… | …… |
无外部碎片
会产生内部碎片
外部碎片：系统进行分区后产生的碎片
内部碎片：进程无法将系统分配的分区全部使用
分区分配表和相对应的分配回收算法实现
# 可变分区方式
动态分区分配没有内部碎片，但是有外部碎片
内部碎片，分配给某进程的内存区域中，如果有些部分没有用上。
外部碎片，是指内存中的某些空闲分区由于太小而难以利用。
如果内存中空闲空间的总和本来可以满足某进程的要求，但由于进程需要的是一整块连续的内存空间，因此这些“碎片”不能满足进程的需求。
```mermaid
graph TD
A[操作系统8MB]---B[进程2 14MB]
B---C[6MB]
C---D[进程4 4MB]
D ---E[10MB]
E ---F[进程3 18MB]
F ---G[4MB]
```
没有内部碎片，但是有外部碎片
不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区
空闲分区表
空闲分区链
# 分配算法
# 1、 首次适应算法
空闲分区以地址递增的次序排列，每次分配内存时顺序查找空闲分区链，从第一个空闲分区开始查找，找到第一个可以满足需求的分区就进行必要的划分和分配
# 2、最佳适应算法
为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地流线大片空闲区
如何实现：空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链
容易产生外部碎片
# 3、最坏适应算法
根据分区链中根据分区查找与请求相差最大的分区
按容量递减的次序，找到大小能满足要求的一个空闲分区
大进程到达，就没有内存分区可用了
# 4、邻近适应算法
首次适应算法很想，每次都从上次查找结束的位置开始检索
构造一个循环链表，每次分配内存时从上次查找的结束位置开始查找
邻近适应算法无论低地址和高地址部分的空闲分区的概率使用，也就导致了无大分区可用
# 回收算法
1、 上邻接
2、 下邻接
3、上下邻接
4、 无邻接
# 非连续的分配方式
将内存的物理空间和程序逻辑空间划分为大小相等的块。划分为大小和数量都固定的基本分区
基本地址变换机构（用于实现逻辑地址到物理地址转换的一组硬件机构）
分页存储管理的基本原理
将物理内存划分成一块块（页）大小为4KB，叫做页框=页帧 = 内存块=物理块=物理页面
每个页框有一个编号，即“页框号” （页帧号 =内存块号=物理块号 =物理页号）
页框号从 0 开始
将进程的逻辑地址空间也分为页框大小相等的一个个部分
每个部分称为一个“页”（页面），每个页面也有一个编号，即页号，页号从 0 开始
操作系统以页框为单位为各个进程分配内存空间，进程的每个页面分别放入一个页框中。
也就是说，进程的页面与内存的页框有一一对应的关系。
不必连续存放，也无前后次序要求，只要求足够容纳所有的物理块即可。
将进程的逻辑地址空间
将物理地址空间也划分成一页页
通常大小和虚拟地址空间一样
物理地址空间的每一页也叫做页框
在物理地址空间已有的部分是已缓存的 cache 的
只要确定了每个页面的大小，逻辑地址结构就确定了。因此，页式管理中地址是一维的
Uncache 的，在磁盘上，还没在物理地址空间
Unallocated，在磁盘上也没有
PTE 页表项
PTED0 valid = 1 虚拟页 0 已经缓存在物理内存 address，根据 address 来在物理内存获取数据
=0，不在物理内存中，发生了缺页，进行缺页处理程序，从磁盘上调到虚拟内存里来
虚拟虚拟，其实并不存在，存在的是物理页
分页系统的逻辑地址空间分为两部分：页号P和页内地址d（又称为页内偏移量）
页面的大小决定页内地址的位数，页号位数决定了逻辑地址空间中页面的总数。
页表——为了直到每个页面在内存中存放到位置，要为每个进程创建一个页表
通常在PCB中
每一个页面对应一个页表项
每个页表项由页号和块号组成
页表记录进程页面和实际存放的内存块之间的映射关系
页表存储在内存中,只存储物理块号，页号不占用存储空间（因为是按页号是按顺序排列的，只有块号）
然后将页表的起始地址及长度保存在进程的 PCB 中，当以后调度进程到 CPU 上运行时，再
将 PCB 保存到页表起始地址及长度写入 CPU 的页表寄存器中
虽然进程的各个页面是离散存放的，但是页面内部是连续存放的
如果要访问逻辑地址A，则
1. 确定逻辑地址A对应的“页号”P？
2. 找到P号页面在两存中的起始地址（需要查页表）
3. 确定逻辑地址A的“页内偏移量”W？
逻辑地址A对应的物理地址=P号页面在内存中的起始地址+页内偏移量W
如何计算：
页号=逻辑地址/页面长度（取除法的整数部分）
页内偏移量 $\equiv$ 逻辑地址%页面长度（取除法的余数部分）
页号=110/50=2
页内偏移量=110%50=10
逻辑地址可以拆分为（页号，页内偏移量）
在计算机内部，地址是用二进制表示的，如果页面大小刚好是2的整数幂，则计算机硬件可以很快速的把逻辑地址拆分成（页号，页内偏移量）
假设某计算机用32个二进制位表示逻辑地址，页面大小为4KB=2^12B=4096B
0号页的逻辑地址范围应该是 $0 \sim 4 0 9 5$ ，用二进制表示应该是：
00000000000000000000000000000000~00000000000000000000111111111111
1号页的逻辑地址范围应该是4096~8191，用二进制表示应该是：
00000000000000000001000000000000~00000000000000000001111111111111
结论：如果每个页面大小为2^KB，用二进制数表示逻辑地址，则末尾K位即为页内偏移量，其余部分就是页号
0号内存块的起始物理地址是00000000000000000000000000000000
1号内存块的起始物理地址是00000000000000000001000000000000
2号内存块的起始物理地址是00000000000000000010000000000000
3号内存块的起始物理地址是00000000000000000011000000000000
根据页号可查询页表，而页表中记录的只是内存块号，而不是内存块的起始地址
J号内存块的起始地址=J*内存块大小
假设通过查询页表得知1号页面存放的内存块号是9（1001），则
9号内存块的起始地址=9*4096=00000000000000001001000000000000
则逻辑地址4097对应的物理地址= 页面在内存中存放的起始地址+页内偏移量
$$
= (0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1)
$$
| 31......12 | 11......0 |
| 页号P | 页内偏移量W |
地址结构包含两个部分：前一部分为页号，后一部分为页内偏移量W。在上图所示的例子中，地址长度为32位，其中0~11位为“页内偏移量”，或称“页内地址”； $\pmb { 1 2 \sim 3 1 }$ 位为“页号”
如果有K位表示“页内偏移量”，则说明该系统中一个页面的大小是$2^k$个内存单元
如果有M位表示“页号”，则说明在该系统中，一个进程最多允许有 $2 ^ { M }$ 个页面
$页面大小 \leftrightarrow页内偏移量位数 \rightarrow 逻辑地址结构$
Tips：有些奇葩题目中页面大小有可能不是2的整数次幂，这种情况还是得用最原始的方法计算页号=逻辑地址/页面长度（取除法的整数部分）
页内偏移量=逻辑地址%页面长度（取除法的余数部分）
VP0:根据虚拟页大小4KB，长度为12位，页内地址
在一个页4kb中的起始位置
虚拟页根据地址位数，32位， $3 2 - 1 2 = 2 0$ 位，虚拟页号20位，有 $2 \sim 2 0$ 个虚拟页。
分页系统的逻辑地址空间是一维线性地址空间
注意：页面大小是2的整数幂
设页面大小为L，逻辑地址A到物理地址E的变换过程如下：
1. 计算页号P和页内偏移量W（如果用十进制数手算，则P=A/L，W=A%L；但是在运行时，逻辑地址结构是固定不变的，因此计算机硬件可以更快地得到二进制表示内偏移量）
2. 比较页号P和页表长度M，若P≥M，则产生越界中断，否则继续执行。（注意：页号是从0开始的，而页表长度至少是1，因此P=M时也会越界）
3. 页表中页号P对应的页表项地址=页表起始地址F+页号P*页表项长度，取出该页即为内存块号。（注意区分页表项长度、页表长度、页面大小的区别。页表长度指表中总共有几个页表项，即总共有几个页；页表项长度指的是每个页表项占多大的；页面大小指的是一个页面占多大的存储空间）
4. 计算E=b*L+W，用得到的物理地址E去访存。（如果内存块号、页面偏移量是示的，那么把二者拼接起来就是最终的物理地址了）
假设页面 大小L=1KB，访问的内存块号b=2，页内偏移量W=1023
1. 用E=b*L+w计算目标物理地址
2. 尝试把内存块号、页内偏移量用二进制表示，把它们拼接起来的到物理地址。
Eg：假设某系统物理内存大小为4GB，页面大小为4KB，则每个页表项至少应该为多少字节？
内存块大小=页面大小=4KB=2^12B
→4GB的内存总共会被分为 $2 ^ { 3 2 } / 2 ^ { 1 2 } = 2 ^ { 2 0 }$ 个内存块
→内存块号的范围应该是 $0 \sim 2 ^ { 2 0 }$ -1
→内存块号至少要用20bit来表示
以字节编址，至少要用3B来表示块号（3*8=24bit）
每个页表项的长度是相同的，页号是隐含的。
Eg：假设某系统物理内存大小为4GB，页面大小为4KB，的内存总共会被分为 $2 ^ { 3 2 }$ /2^12=2^20个内存块，因此内存块号的范围应该是0~2^20-1
因此至少要20个二进制位才能表示这么多的内存块号，因此至少要3个字节才够（每个字节8个二进制位，3个字节共24个二进制位）
各页表项会按顺序连续地存放在内存中如果该页表在内存中存放的起始地址为X，则M号页对应的页表项是存放在内存地址为 $x + 3 ^ { * } M$
一个页面为4KB，则每个页框可以存放4096/3=1365个页表项，但是这个页框会剩余4096%3=1B页内碎片因此，1365号页表项存放的地址为X+3*1365+1
如果每个页表项占4字节，则每个页框刚好可存放1024个页表项
页表项时连续地存放在内存中！
理论上来说，3B即可表示内存块号的范围
但是为了方便页表的查询，常常让每个页面恰好可以装得下整数个页表项
虚拟页偏移量 =物理页偏移量
如何快速找到页表？
页表基址寄存器
每个页表项大小相同，4B
页表项是顺序的，0-n
假设虚拟地址32位
虚拟页大小是 4KB（即页内偏移量为 12 位）
有多少个虚拟页？2^32/2^12=2^20,即2 ^20个虚拟页
每一个虚拟页就有一个虚拟页号
再假设每一个页表项4B
那么就有 $2 ^ { \land } 2 0 { \times } 4 \mathsf { B }$ 即占4MB大小
每一个进程都有一个独立的页表（4MB）
页表占用了大量的内存空间
# 快表 TLB
不是内存，是一种高速缓存
与此对应，内存中的页表常称为慢表
用来存放最近访问的页表项的副本
1. CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。
2. 如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表命中，则访问某个逻辑地址仅需一次访存即可。
3. 如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表未命中，则访问某个逻辑地址需要两次访存（注意：在找到页表项后，应同时将其存入快表，以便后面可能的再次访问。但若快表已满，则必须按照一定的算法对旧的页表项进行替换）
由于查询快表的速度比查询页表的速度快很多，因此只要快表命中，就可以节省很多时间。
访问一次内存耗时100us,若块表的命中率为90 %,那么访问一个逻辑地址的平均耗时是多少？
（1+100）\*0.9+（1+100+100）\*0.1=111us
优点系统支持块表和慢表同时查找，那么
(1+100)*0.9+(100+100)\*0.1=110.9us
局部性原理
```
int i=0;
int a[100];
while(i <100)
{
a[i]=i;
i++;
}这个程序执行时，
会很频繁地访问10
号页面、23号页面
```
时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行：如果某个数据被访问过不久之后该数据很可能再次被访问。 (因为程序中存在大量的循环）
空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。（因为很多数据在内存中都是连续存放的）
10号页面
存放程序对应的指令
23号页面
因此我们要建立多级页表，减少内存存储页表的空间
多级页表
采用两级页表的形式
页表是连续存放在进程当中
问题一：页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框
问题二：没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问
因此，我们可以参照进程在内存中必须连续存储的问题，我们通过了页号 $^ +$ 页内偏移量+页表的机制
同样的可以解决页表必须连续存放的问题，把必须连续存放的页表再分页
如页面大小4KB，每个表项4B，每个页面可以存放 1K个页表项，因此每1K个连续的页表
项为一组，每组刚好占一个内存块，再将各组离散地存放到各个内存块中
要为离散分配的页表再建立一张页表，称为页目录表，或称外层页表、顶层页表
一个页面可以存放1024个页表
就要为这些小页表再建立一个表，叫做页目录表
10 位一级页号表示一共有多少个页面来存放每个小页表项（ $\scriptstyle \left( 2 \land 2 2 \mathsf { B } / 2 \land 1 2 \mathsf { B } = 1 0 2 4 \right)$
10 位二级页号表示每个页面（4KB）可以存放多少个页表项（ $( 4 \mathsf { K B } / 4 \mathsf { B } = 1 0 2 4 )$ ）
一共加起来20位表示一共可以有多少个页表
小页表叫做二级页表
页目录号：表示 $0 { - } 2 ^ { \wedge } 1 0 { - } 1$
页目录号对应页目录项（页表项的一种）
每一个页目录号可以寻址一个二级的页表
0-2^10-1 个
每一页是 4KB(页偏移量 12 位)，一个页表项最多有 $2 { \sim } 1 0$ 个，即最多占用的物理内存为 4MB
两级页表的逻辑地址结构
例：将逻辑地址（0000000000,0000000001,111111111111)转换为物理地址（用十进制表示）。
最终要访问的内存块为4，该内存块的起始地址为4*4096=16384
页内偏移量为1023
最终的物理地址为17407
而一共有 $2 { \sim } 1 0$ 个页目录项，共有 $4 \mathsf { M B } \times 2 { \wedge } 1 0 { = } 4 \mathsf { G B }$
则可以通过来记录整个虚拟内存4GB的映射关系。
48位的虚拟地址
对于问题二，可以在需要访问页面时才把也秒调入内存（虚拟存储技术）
属于内中断
问题二：没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面。
可以在需要访问页面时才把页面调入内存（虚拟存储技术）。可以在页表项中增加一个标志位，用于表示该页面是否已经调入内存
| 一级页号 | 内存块号 | 是否在内存中 |
| -------- | -------- | ------------ |
| 0 | 3 | 是 |
| 1 | 无 | 否 |
| ... | | |
| 1023 | ... | |
若想访问的页面不在内存中，则产生缺页中断(内中断)，然后将目标页面从外存调入内存
| 二级页号 | 内存块号 | 是否在内存中 |
| -------- | -------- | ------------ |
| 0 | 2 | 是 |
| 1 | 4 | 是 |
| ... | | |
| 1023 | ... | |
| |
| ---- |
| |
可以在页表项中增加一个标志位，表示该页面是否已经调入内存
7. 没有快表时访问一个数据需要访问内存的次数
- 1 次（连续分配）
- 2 次（一级分页存储管理、分段存储管理）
- 3 次（二级分页存储管理、段页式存储管理）
# 8. 动态分区分配
– 首次适应算法（空闲区按起始地址递增的次序拉链）
– 最佳适应算法（空闲区按分区大小递增的次序拉链）
– 回收时要进行分区的合并（具体有前后都没有空闲分区、只是前面有空闲区、只是后面有空闲区、前后都是空闲区这四种情况）
– 碎片问题可采用紧凑技术加以解决
– 采用紧凑技术后的动态分区分配方式也叫可重定位分区分配方式（因为它需要得到动态重定位技术的支持）
# 9. 对换
– 所谓“对换”，是指把内存中暂时不能运行的进程或暂时不用的程序或数据，调出到外存上，以便腾出足够的内存空间，再把具备运行条件的进程或进程所需要的程序和数据，调入内存。
– 整体对换：以进程为单位的对换。（但进程的 PCB 常驻内存不应该被换出；进程的程序段如果正在被其他进程共享，也不应该被换出内存）
– 部分对换：以“页”或“段”为单位的对换
# 请求调页
一种选择，在程序执行时将整个程序加载到物理内存问题是，最初可能不需要整个程序都处于内存
仅在需要时才加载页面，这种技术被称为请求调页对于请求调页的虚拟内存，页面只有在程序执行期间被请求时才被加载。因此，从未访问的页从不加载到物理内存中。
1、 各级页表的大小不能超过一个页面（4KB）
表对应页号应为10位。总共28位的页号至少要分为三级
逻辑地址：页号28位 页内偏移量12位
逻辑地址：一级页号8位 二级页号10位 三级页号10位 页内偏移量12位
2、 时间上的增多
分段存储管理
与分页最大的区别就是分配的地址空间不同
例如一个进程可以分为一个主程序段、子程序段、数据段等等
由于是按逻辑功能模块划分，用户编程更方便，程序的可读性更高
OAD1,[D]|；//将分段D中A单元内的值读入寄存器1
TORE1,[X]|;//将寄存器1的内容存入X分段的B单元中
分段系统的逻辑地址结构由段号（段名）和段内地址（段内偏移量）所组成。如：
# 段表
# 段号、段长和段基址
每个段对应一个段表项。因为在分页式管理当中，每个页面大小是相同的 4KB
每个段表项的长度相同
所以要对段内偏移量进行检查
这里不同的是，基址为整个物理地址（32位）
问题：程序分多个段，各段离散地装入内存，为了保证程序能正常运行，就必须能从物理内存中找到各个逻辑段的存放位置。为此，需为每个进程建立一张段映射表，简称“段表”。
页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。
段是信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。
页的大小固定且由系统决定。段的长度却不固定，决定于用户编写的程序。
分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址。
分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。
不能被修改的代码称为纯代码或可重入代码（不属于临界资源），这样的代码是可以共享的。可修改的代码是不能共享的（比如，有一个代码段中有很多变量，各进程并发地同时访问可能造成数据不一致）
页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。
段是信息的逻辑单位。分页的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。
页的大小固定且由系统决定。段的长度却不固定，决定于用户编写的程序。
分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址。
分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。
分段比分页更容易实现信息的共享和保护。不能被修改的代码称为纯代码或可重入代码（不属于临界资源），这样的代码是可以共享的。可修改的代码是不能共享的
访问一个逻辑地址需要几次访存？
分页（单级页表）：第一次访存一一查内存中的页表，第二次访存一一访问目标内存单元。总共两次
分段：第一次访存一一查内存中的段表，第二次访存一一访问目标内存单元。总共两次访存
与分页系统类似，分段系统中也可以引入快表机构，将近期访问过的段表项放到快表中，这样可以少一次访问，加快地址变换速度。
段页式
分段系统的逻辑地址结构由段号和段内地址（段内偏移量）组成。如：
| 31 | ...... | 16 | 15 | ...... | 0 |
| 段号 | | | 段内地址 | | |
段页式系统的逻辑地址结构由段号、页号、页内地址（页内偏移量）组成。如：
与此对应，段页式的段表存储的是段号（隐藏）、页表长度、页表存放块号组成
每个段表项长度相等
每个页面对应一个页表项，每个页表项由页号（隐含）、页面存放的内存块号组成，每个页表项长度相等
虚拟存储系统
虚拟存储系统的基本概念
将进程装入的一次性或者整体性改为多次性：改变进程必须全部装入内存才能开始运行的方式1、作业很大时，并不能全部装入内存，导致大作业无法运行。
当大量作业要求运行时，会只有少量作业能运行，导致多道程序并发度下降
将进程的驻留性改为置换性：当作业被装入内存，就会一直驻留在内存中。那么在需要时将暂时不用的部分换出到外存储器。
就可以让程序开始执行。
基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。
在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序
。
若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。
在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存。
操作系统虚拟性的一个体现，实际的物理内存大小没有变，只是在逻辑上进行了扩充。
多次性:无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。
对换性:在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出。
虚拟性:从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。
存储管理
主要区别：
主要区别:在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存（操作系统要提供请求调页(或请求调段)功能），然后继续执行程序若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存（操作系统要提供页面置换(或段置换)的功能）。
局部性原理：时间局部性：数据可能再次被访问
空间局部性：邻近的存储单元也有可能被访问到
请求分页存储管理方式
页面置换
页面置换策略
| 页号 | 内存块号 |
| ---- | -------- |
| 0 | a |
| 1 | b |
| 2 | c |
基本分页存储管理的页表
状态位：是否已调入内存
访问字段：可记录最近被访问过几次，或记录上次访问的时间，供置换算法选择换出页面时参考
修改位：页面调入内存后是否被修改过
外村地址：页面在外存中的存放位置
| 页号 | 内存块号 | 状态位 | 访问字段 | 修改位 | 外存地址 |
| ---- | -------- | ------ | -------- | ------ | -------- |
| 0 | 无 | 0 | 0 | 0 | x |
| 1 | b | 1 | 10 | 0 | y |
| 2 | c | 1 | 6 | 1 | z |
请求分页存储管理的页表
| 页号 | 内存块号 | 状态位 | 访问字段 | 修改位 | 外存地址 |
| 0 | c | 1 | 0 | 0 | x |
| 1 | b | 1 | 10 | 0 | y |
| 2 | 无 | 0 | 0 | 1 | z |
| ...
x号块
...
y号块
...
z号块
... |
| ------------------------------------------------------------ |
外存
> ...
>
> b号块
>
> ...
>
> ...
>
> ...
>
> c号块
>
> ...
内存
假设此时要访问逻辑地址=(页号，页内偏移量)=(0,1024)
在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。
此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。
如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项。
如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存。
①只有“写指令”才需要修改“修改位”。并且，一般来说只需修改快表中的数据，只有要将快表项删除时才需要写回内存中的慢表。这样可以减少访存次数。
②和普通的中断处理一样，缺页中断处理依然需要保留CPU现场。
③需要用某种“页面置换算法”来决定一个换出页面
④换入/换出页面都需要启动慢速的I/O操作，可见，如果换入/换出太频繁，会有很大的开销。
③页面调入内存后，需要修改慢表，同时也需要将表项复制到快
1、请求调页
2、页面置换
3、修改数据
页面置换算法
1、最佳置换算法OPT
将来不在访问的页面或者长时间内不会访问的页面
2、先进先出置换算法FIFO
最先调入内存的页面，或者在也内存中驻留时间最久的页面算法
3、 最近最久未使用置换算法 LRU
最近一段时间内最长没有被访问的页面
4、最近最少使用置换算法LFU
被访问的频次而不是LRU中的事件
淘汰过去一段话时间里访问次数最少的页面
5、 时钟置换算法（CLOCK）
简单的时钟置换算法
简单的CLOCK算法实现方法：为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接一个循环队列。当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的如果是0，就选择该页换出：如果是1，则将它置为0，暂不换出，继续检查下一个页面，若描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描）
例：假设系统为某进程分配了五个内存块，并考虑到有以下页面号引用串：
1,3,4,2,5,6,3,4,7
```mermaid
graph TD
A["6号页(1)"]-->B["3号页(0)"]
B-->C["4号页(0)"]
C-->D["7号页(1)"]
D-->E["5号页(0)"]
E -->A
```
改进型