PC_非连续内存分配方式@分页存储管理@地址变换机构@快表
文章目录
- 非连续内存分配方式
- 🎈分页存储管理
- 基本分页存储管理
- 页面和页面大小
- 分块和碎片
- 逻辑地址结构
- 页表
- 页表项结构
- 页表项和地址比较🎈
- 页表项地址
- 地址变换机构
- 基本地址变换机构
- 结构图
- 映射过程
- Note:页表长度@页表项长度@页表大小
- 例
- 小结
- ref
- 具有快表的地址变换机构
- 结构图
- 过程
- 两级页表(多级页表)
- 多级页表下的内存地址结构
- tips
- 例
- 例
非连续内存分配方式
- 在连续分配方式中，我们发现，即使内存有超过R大小的空闲空间，但若没有连续的R的空间，对于需要总大小为R的内存空间的作业仍然是无法运行的;
- 但若采用非连续分配方式(离散式分配)，则作业所要求R大小的内存空间可以分散地分配在内存的各个区域
- 这也需要额外的空间去存储(标记)它们(分散区域)的索引
- 这使得非连续分配方式的存储密度低于连续分配方式。
- 这也需要额外的空间去存储(标记)它们(分散区域)的索引
- 非连续分配方式根据分区的大小是否固定，分为
- 分页存储管理
- 分段存储管理
🎈分页存储管理
- 在分页存储管理中，又根据运行作业时是否要把作业的所有页面都装入内存才能运行，分为
- 基本分页存储管理
- 请求分页存储管理(可以用来实现虚拟内存的管理方式)
基本分页存储管理
- 固定分区会产生内部碎片,动态分区会产生外部碎片,这两种技术对内存的利用率都比较低
- 我们希望内存的使用能尽量避免碎片的产生，这就引入了分页的思想:
页面和页面大小
- 不同上下文中的块的别称,包括以下两方面
- 进程中的块称为页或页面(Page)
- 属于某个进程所持有(process-page)
- 内存中的块称为页框或页帧( Page Frame)(形容尚未被使用的内存块)
- 可能属于为分配的空闲内存块(memory-page)
- 外存也以同样的单位块进行划分，直接称为块或盘块（Block)
- 进程在执行时需要申请主存空间
- 🎈要为每个页面分配主存中的可用页框，页和页框的一一对应。
分块和碎片
-
把主存空间划分为大小相等且固定的块，块相对较小，作为主存的基本单位。
-
每个进程也以块为单位进行划分，进程在执行时，以块为单位逐个申请主存中的块空间。
-
分页的方法从形式上看，像分区相等的固定分区技术，分页管理不会产生外部碎片。
- 但它又有本质的不同点:
- 块的大小相对分区要小很多，而且进程也按照块进行划分，进程运行时按块申请主存可用空间并执行。
- 这样，进程只会在为最后一个不完整的块申请一个主存块空间时，才产生主存碎片，
- 所以尽管会产生内部碎片，但这种碎片相对于进程来说也是很小的，每个进程平均只产生半个块大小的内部碎片(也称页内碎片)
- 但它又有本质的不同点:
-
为方便地址转换，页面大小应是2的整数幂。
-
同时页面大小应该适中
- 页面太小会使进程的页面数过多，这样页表就会过长，占用大量内存，
- 而且也会增加硬件地址转换的开销，降低页面换入/换出的效率;
-
页面过大又会使页内碎片增多，降低内存的利用率。
逻辑地址结构
-
简称为地址结构
-
页号P
- 假设地址的高p位用来表示页号,P∈[0,2p−1]\in[0,2^{p}-1]∈[0,2p−1]
-
页内偏移W
- 假设地址的低w位用来表示页内的字,W∈[0,2w−1]W\in[0,2^w-1]W∈[0,2w−1]
-
地址结构决定了虚拟内存的寻址空间有多大
页表
-
为了便于在内存中找到进程的每个页面所对应的物理块，系统为每个进程建立一张页表
- 它记录页面在内存中对应的物理块号，页表一般存放在内存中。
-
在配置页表后，进程执行时，通过查找该表，即可找到每页在内存中的物理块号。
-
可见，页表的作用是实现页号到物理块号的映射
-
页表是由页表项组成的
页表项结构
- 有两部分组成
- 页号
- 块号
页表项和地址比较🎈
- 页表项与(存储单元(字))逻辑地址都可以看做是由两部分构成，
- 第一部分都是页号，
- 第二部分
- 页表项的是物理内存中的块号N;(PBN:physical (memory) Block Number)
- 地址的是页内偏移W;(PIO:page inner offset )
- PBN+PIO共同组成物理地址
页表项地址
- 一般指的是页表中的(某个)页表项相对于页表起始地址的偏移量
地址变换机构
- 地址变换机构,记为AT:(Address Translation)
- 主要分为两类:基本地址变换机构和具有快表的地址变换机构
基本地址变换机构
结构图
映射过程
-
地址变换机构的任务是将逻辑地址转换为物理地址
-
地址变换借助于页表(page table,简单记为PT或T)实现
- 将T视为可调用对象,约定页表项表达式:T.P或T(P)T.P或T(P)T.P或T(P)🎈
- T.PT.PT.P访问的是:页表T中的页号为P的页表项PTI🎈(Page Table Item)
-
在系统中通常设置一个页表寄存器(PTR(page table register)),存放以下内容(2个字段):
- 页表在内存的起始地址FFF🎈
- 页表长度MMM🎈
-
进程未执行时，页表的始址和页表长度存放在本进程的PCB中
-
进程被调度执行时，才将页表始址和页表长度装入页表寄存器PTR中
-
设页面大小为LLL🎈
-
需要被计算物理地址的*某个字的*逻辑地址为AAA🎈
-
A对应的到物理地址E🎈
-
A→EA\to{E}A→E的变换过程如下(记为函数(映射)E:E=E(A)E=E(A)E=E(A))
- 假设逻辑地址、页号、每页的长度都是十进制数:
-
由给定的逻辑地址A计算对应的页号和页内偏移量
- 页号P🎈
- P=A/LP= A/LP=A/L
- (向下取整整除运算P=floor(A/L)P=floor(A/L)P=floor(A/L))
- 页内偏移量W🎈
- W=A%LW= A\%LW=A%L
- 描述的是某个页内的哪一个存储字
- 也就得到了二元组逻辑地址A的(P,W)(P,W)(P,W)
- 页号P🎈
-
比较页号P和页表(每个进程都有自己的页表)长度M
- 若P⩾MP\geqslant MP⩾M,则产生越界中断，
- 否则继续执行
- 即,P
- 即,P
-
页表中:
-
记:页号P对应的页表项地址为T.PT.PT.P
-
T.P=F+P×LT.P=F+P\times{L} T.P=F+P×L
- 类似于访问二维数组的第P行(页号充当一个行索引的角色)
- 取出该页表项T.P块号字段内容:b=T.P.bb=T.P.bb=T.P.b,就是所求的物理块号
- 通常,页表是给出的,计算出T.P后,就可以直接从页表中读取出来T.P页表项的内容(即,(物理)块号)
-
-
最后计算E=bL+WE=bL+ WE=bL+W,用得到的物理地址E去访问内存(具体的存储单元)
-
以上整个地址变换过程均是由硬件自动完成的。
-
Note:页表长度@页表项长度@页表大小
- 页表长度是指一共有多少页,
- 页表项长度(大小)是指页地址占多大的存储空间
- 页表大小:
- 指页表占用的存储空间
- 假设页表长度为N,页表项长度为L
- 页表大小L(PT)=N×LL(PT)=N\times{L}L(PT)=N×L
例
- 例如，某计算机的页面大小L为1KB，页表中的页号2对应的物理块为b=8,
- 问,该逻辑地址A = 2500的物理地址E?:
- 取1K=210=10241K=2^{10}=10241K=210=1024
- P= 2500/1K=2
- W= 2500%1K =452
- 又由已知的页表(页表项(逻辑块号,物理块号)二元组(2,8))
- 即,查找得到页号P=2对应的物理块的块号b=8，
- E=8×1024+452=8644。E= 8\times 1024 + 452 = 8644。E=8×1024+452=8644。
- Note:对于计算条件用十进制数和用二进制数给出，过程会稍有不同。
- 问,该逻辑地址A = 2500的物理地址E?:
小结
- 页式管理只需给出一个整数就能确定对应的物理地址，因为页面大小L是固定的。
- 因此，页式管理中地址空间是一维的。
- 页表项的大小L,不是随意规定的，而是有所约束的。如何确定页表项的大小(主要讨论下限的计算)?
- 页表项的作用是找到该页在内存中的位置。
- 以32位逻辑地址空间、字节编址单位、一页4KB为例，
- 地址空间内共有232B/4KB=1M2^{32}B/4KB = 1M232B/4KB=1M页
- 因此需要log21M=20\log_2{1M} = 20log21M=20位才能保证表示范围能容纳所有页面
- 又因为以字节作为编址单位
- 以字节作为编址单位,主要是指,把二进制串的位数不符合8的倍数的时候加上一个对齐因子f∈[0,7],其中7=8−1f\in[0,7],其中7=8-1f∈[0,7],其中7=8−1
- 可以处理为向上取整
- 所以,页表项的大小L⩾⌈20/8⌉=3BL\geqslant\lceil{20}/{8}\rceil= 3BL⩾⌈20/8⌉=3B.
- 所以在这个条件下，为了保证页表项能够指向所有页面，页表项的大小应该大于等于3B,
- 当然，也可选择更大的页表项
- 让一个页面能够正好容下整数个页表项，进而方便存储(如取成4B,这样一页正好可以装下1K个页表项)，或增加一些其他信息。
- 下面讨论分页管理方式存在的两个主要问题:
- ①每次访存操作都需要进行逻辑地址到物理地址的转换，地址转换过程必须足够快，否则访存速度会降低;
- ②每个进程引入页表，用于存储映射机制，页表不能太大，否则内存利用率会降低.
ref
- 逻辑地址：CPU所生成的地址。
- CPU产生的逻辑地址被分为 :
- p （页号） 它包含每个页在物理内存中的基址，用来作为页表的索引；
- d （页偏移），同基址相结合，用来确定送入内存设备的物理内存地址。
- CPU产生的逻辑地址被分为 :
- 物理地址：内存单元所看到的地址。
- 逻辑地址空间为2m2^m2m，且页大小为2n2^n2n，那么逻辑地址的高p=m－np=m－np=m－n位表示页号，低n位表示页偏移。
- 逻辑地址空间:由程序所生成的所有逻辑地址的集合。
- 物理地址空间:与逻辑地址相对应的内存中所有物理地址的集合,用户程序看不见真正的物理地址。
- 注：用户只生成逻辑地址，且认为进程的地址空间为0到max。
- 物理地址范围从R+0到R+max，R为基地址
- 地址映射－将程序地址空间中使用的逻辑地址变换成内存中的物理地址的过程。
- 由内存管理单元（MMU）来完成。
- 分页逻辑地址 =P(页号).d(页内位移)
- 分页物理地址=f(页帧号).d(页内位移)
- P=线性逻辑地址/页面大小P = 线性逻辑地址/页面大小P=线性逻辑地址/页面大小
- d=线性逻辑地址−P×页面大小d= 线性逻辑地址-P\times页面大小d=线性逻辑地址−P×页面大小
具有快表的地址变换机构
结构图
-
-
观察改过程,可以发现比其仅包含慢表的地址变换机构,包含快表的地址变换机构多了快表这条高速路径,快速计算出物理块号b,从而通过E=bL+W得到物理地址
- 如果访问快表命中成功,则只需要访问一次主存(直接根据E从主存取数据)
- 否则访问2次主存(一次慢表,一次物理地址从主存取数据)
过程
-
若页表全部放在内存中，则存取一个数据或一 条指令至少要访问两次内存:
-
第一次是访问页表， 确定所存取的数据或指令的物理地址;
-
第二次是根据该地址存取数据或指令。
-
显然，这种方法比通常执行指令的速度慢了一半。
-
为此，在地址变换机构中增设具有并行查找能力的高速缓冲存储器-快表
- 可以用相联存储器来实现快表(TLB),
- 相联存储器（associative memory)
- 也称为按内容访问存储器（content addressed memory)
- 用来存放当前访问的若干页表项，以加速地址变换的过程。
- 与此对应，主存中的页表常称为慢表。
- 可以用相联存储器来实现快表(TLB),
-
在具有快表的分页机制中，地址的变换过程如下:
- CPU给出逻辑地址后，由硬件进行地址转换，将页号送入高速缓存寄存器，并将此页号与快表中的所有页号进行比较。
- 若找到匹配的页号，说明所要访问的页表项在快表中，则直接从中取出该页对应的页框号，与页内偏移量拼接形成物理地址。这样，存取数据仅1次访存便可实现。
- 若未找到匹配的页号，则需要访问主存中的页表(慢表)，读出页表项后，应同时将其存入快表，
以便后面可能的再次访问。- 若快表己满，则须按特定的算法淘汰一 个旧页表项
- CPU给出逻辑地址后，由硬件进行地址转换，将页号送入高速缓存寄存器，并将此页号与快表中的所有页号进行比较。
两级页表(多级页表)
-
考虑到页表大小在某些情况下会占用较多的内存空间,采用页表分级的机制,解决这种可能出现的不利情况
-
以某个需要40MB内存的进程(系统分配给该进程共40MB)的内存(页框)为例,体会进程的页表可能占用掉相当客观的内存
- 页面大小L§=4KB
- 设页表项长度L(PTI)=4B
- 那么页表长度(项数)N(I)=40MB4KB=10KN(I)=\frac{40MB}{4KB}=10KN(I)=4KB40MB=10K
- 页表大小L(PT)=N(I)×L(PTI)=40KBL(PT)=N(I)\times{L(PTI)}=40KBL(PT)=N(I)×L(PTI)=40KB
- 也就是说40MB的进程页表开销要再占用40KB
- 换算为页面大小,页表需要40KB/4KB=10个页面
- 而根据局部性原理,大多情况下,映射所需要的页表项都在页表的同一个页面中
- 不需要(同时)将进程的所有的页表项全部载入到内存中
-
为了压缩页表，我们进一步延伸页表映射的思想，就可得到二级分页,即使用层次结构的页表:
- 承接上述的例子,将页表的10页空间也进行地址映射，建立上一级页表(高一级页表(类比容量大小权重))，用于存储页表的映射关系。
- 这个方案就和当初引进页表机制的方式一样，实际上就是构造一个页表的页表，也就是二级页表。
- 容易知道,这里对页表的10个页面进行映射只需要10个页表项，所以上一级页表只需要1页就已足够
- 每一页可以存储4KB4B=1K\frac{4KB}{4B}=1K4B4KB=1K= 1024个页表项,1024>>10,绰绰有余
- 一个一级页表项可以代表一个二级页表
- 一个二级页表又可以代表(映射)1024个页面(0级页表)
- 🎈页表的级别(数值)越低,页表的每一项代表的容量就越大
- 比如,一个K级页表的每一项代表的容量相当于一张K+1级的页表(整张表)的容量
- 可见,类似于计数进位制(比如十进制,百位权重为10210^2102,十位权重10110^1101,个位权重为100=110^0=1100=1)
多级页表下的内存地址结构
-
1级(顶级)页号字段(页目录号) 2级页号字段 … k级字段 页内偏移 -
在进程执行时，只需要将这一页的上一级页表调入内存即可
-
进程的页表和进程本身的页面可在后面的执行中再调入内存。
-
根据上面提到的条件(32位逻辑地址空间、页面大小4KB、页表项大小4B，以字节为编址单位)，我们来构造一个适合的页表结构。
-
页面大小为4KB
- 则页内偏移地址为log24K=12\log_24K= 12log24K=12位，
- 页号部分(字段)占用剩下的bit,即32-12=20位
-
若不采用分级页表,且映射全部的地址空间,共有2202^{20}220个页面,相应地需要2202^{20}220个页表项记录,每个页表项又是占用4B,页面大小为4KB，则仅这些页表项页表就要占用220×4B/4KB=10242^{20}\times4B/4KB = 1024220×4B/4KB=1024 页，这大大超过了许多进程自身需要的页面，对于内存来说是非常浪费资源的
-
若不把这些页表放在连续的空间里，则需要一张索引表来告诉我们第几张页表该上哪里去找，这能解决页表的查询问题，且不用把所有的页表都调入内存，只在需要它时才调入(下节介绍的虚拟存储器思想)，因此能解决占用内存空间过大的问题。
-
🎈为查询方便，顶级页表(代表力权重最高的页面)最多只能有1个页面(一定要记住这个规定),
-
对于本例而言,无论划分为多少级页表,顶级页表(1级页表)总共可以容纳4KB/4B = IK个页表项，它占用的地址位数为log21K=10\log_2{1K}= 10log21K=10 位
-
而之前已经计算出页内偏移地址占用了12 位，因此一个32位的逻辑地址空间就剩下了10 (32-10-12=10)位，正好使得二级页表的大小在一页之内， 这样就得到了逻辑地址空间的格式
-
1级页号 2级页号 页内偏移 10 10 12
-
-
tips
- 求解这类问题,通常先计算出(IPP,Blocks,N)
- 每页面可以保存多少个页表项IPP(Items per page)
- 每页容量L§
- 每个表项大小L(I)
- IPP=L(P)L(I)IPP=\frac{L(P)}{L(I)}IPP=L(I)L(P)
- 逻辑地址空间对应多少个页表项(页面数或块数)Blocks
- 所有(一级)页表共占用的页面数N=BlocksIPPN=\frac{Blocks}{IPP}N=IPPBlocks
- 每页面可以保存多少个页表项IPP(Items per page)
例
-
某计算机采用二级也报的分页存储管理方式
-
按照字节编址
-
页面大小为L§=2102^{10}210B
-
页表项大小L(I)=2B
-
逻辑地址空间大小为2162^{16}216
-
逻辑地址结构为:
-
页目录号 页号 页内偏移
-
-
表示整个逻辑地址空间的页目录表中包含的表项个数N至少是?
-
-
分析:
- 每个页面可以容纳的表项数IPP=2102=29\frac{2^{10}}{2}=2^92210=29
- 逻辑地址空间需要Blocks=216Blocks=2^{16}Blocks=216页面
- N=21629=27=128N=\frac{2^{16}}{2^9}=2^7=128N=29216=27=128
例
- 在采用二级页表的分页系统中,cpu页表机制寄存器中的内容是:
- 当前进程的一级页表(顶级页表)的起始物理地址