物理内存是什么
-
2023年3月17日发(作者：日常行为规范)操作系统学习笔记（⼋）---内存管理（分页、分段机制）
⽬录
⼀、内存管理硬件设计&地址空间
CPU能直接访问的存储器只有内存和处理器内的寄存器，机器指令可以⽤内存地址作参数⽽不能以磁盘地址作参数。因此，执⾏指令以及执
⾏使⽤的数据必须在这些可直接访问的存储设备上。
基地址寄存器（baseregister）和界限地址寄存器（limitregister）
每个进程都应该有独⽴的内存空间，需要确定⼀个进程可访问的合法地址的范围，并确保进程只访问其合法地址。基地址寄存器含有最⼩的
合法物理内存地址，界限地址寄存器决定了范围的⼤⼩。
e.g:
基地址寄存器值为300040，界限寄存器为120900，那么程序可以合法访问从300040~420940（含）的所有地址。
内存空间保护的实现，是通过CPU硬件对⽤户模式所产⽣的每⼀个地址与寄存器的地址进⾏⽐较来完成的。只有操作系统可以通过特殊的特
权指令来加载这两个寄存器。
地址空间
段机制启动、页机制未启动：逻辑地址->段机制处理->线性地址=物理地址
段机制和页机制都启动：逻辑地址->段机制处理->线性地址->页机制处理->物理地址
虚拟地址应该等价于逻辑地址（课本），但是因为对程序员⽽⾔可见的只有线性地址，有时候也把线性地址称为虚拟地址？
CPU所⽣成的地址通常称为逻辑地址（logicaladdress），⽽内存单元所看到的的地址（即被加载到内存地址寄存器（memory-address
register）中的地址）通常被称为物理地址（physicaladdress）。
由程序所⽣成的所有逻辑地址的集合称为逻辑地址空间（logicaladdressspace）
与这些逻辑地址相对应的所有物理地址的集合称为物理地址空间（physicaladdressspace）
物理地址空间的⼤致布局：
虚拟地址空间(VM)的三个特征
arency（透明性、不可见的）
每个进程都认为它有独⽴的物理地址空间且不会认识到物理内存被虚拟化了。操作系统和硬件负责完成虚拟地址到物理地址的转化。
ency（有效性）
从时间（不能让进程运⾏得很慢）、空间（不能占⽤过多的物理内存）等⾓度考虑，这就需要很多硬件⽀持，如TLB。
tion
OS需要保证进程之间以及进程与OS之间不会发⽣冲突/物理内存不会相互覆盖，保护机制允许了进城之间的共享代码/数据。
对虚拟地址空间的解释：OS需要建⽴⼀个便于使⽤的物理内存的抽象，这个抽象便是（虚拟）地址空间。对于进程⽽⾔，可见的只是（虚
拟）地址空间⽽不是物理内存，即其使⽤的地址都是虚拟地址，由OS转化为物理地址。
运⾏时从虚拟地址（这⾥指的是逻辑地址）到物理地址的映射是由内存管理单元（memory-managementunit,MMU）的硬件设备来完成
的。有许多⽅案可以完成这种映射。
⼀种简单的⽅案就是使⽤基地址寄存器，在这⾥称为重定位寄存器（relocationregister）。⽤户进程所⽣成的地址在送交内存之前，都将
加上重定位寄存器的值（如图）。
⼆、内存管理⽅法
内存通常分为两个区域：⼀个⽤于驻留操作系统，另⼀个⽤于⽤户进程。操作系统可以位于低内存，也可以位于⾼内存。影响这⼀决定的主
要因素是中断向量的位置，由于中断向量通常位于低内存，所以操作系统也常常位于低内存……
连续内存分配（contiguousmemoryallocation）
这⾥讨论的是如何为需要调⼊内存的进程分配内存空间的⽅案，采⽤连续内存分配时，每个进程位于⼀个连续的内存区域。
连续内存分配有两个重要的技术：SplittingandCoalescing（姑且翻译为分裂和合并）
Splitting简单来说就是⼀个空闲内存块有10B，⼀个进程需要1B，那么我们把这个空闲块分为2部分：1B和9B。
Coalescing是针对进程释放内存后的操作，即将连续的空闲块合并。
上图中的三个空闲块会合并（如上图）。
多分区⽅案（multiple-partitionmethod）
将内存分为多个⼤⼩固定的分区（partition），每个分区只能容纳⼀个进程。
当⼀个分区空闲时，可以从输⼊队列（等待队列）中选择⼀个进程，以调⼊到空闲分区。当进程终⽌时，其分区可以被其他进程所使⽤。
可变分区⽅案（variable-partition）
操作系统维护⼀个表，⽤于记录哪些可⽤和已被占⽤，把可⽤的内存块称为⼀个个的孔（hole）。
⼀开始所有内存作为1个孔，当有新进程需要内存时，为该进程查找⾜够⼤的孔，如果找到，为该进程分配所需的内存，孔内未分配的内存
可以下次再⽤。
如何为新的进程分配合适的孔？
⾸次适应（first-fit）：分配第⼀个⾜够⼤的孔，查找可以从头开始，也可以从上次first-fit结束时开始。
下次适应(next-fit):作为first-fit的优化⽽提出，使⽤⼀个指针记录上次搜索完成时的位置，下次分配时，从该记录位置开始搜索，到达链表
尾部则绕回。该指针在空闲链表内循环游动，从⽽避免了在链表头部区域堆积过多的碎⽚。
最佳适应（best-fit）:分配最⼩的⾜够⼤的孔。需要查找整个列表（或者列表按⼤⼩排序），这种⽅法可以产⽣最⼩剩余孔。
最差适应（worst-fit）：分配最⼤的孔。需要查找整个列表。这种⽅法可以产⽣最⼤剩余孔
性能分析：主要从时间和空间两个⽅⾯来考虑
First-fit:查询（空闲块）速度较好，但是会在空闲链表开始部分产⽣较多的碎⽚
Best-fit:时间开销⼤，减少了浪费的空间
Worst-fit:时间开销⼤，空间利⽤率低，往往不是很好
碎⽚（fragmentation）
外部碎⽚及其解决⽅案：
简单来说，外部碎⽚就是内存中进程之间的（⼩）空闲块。
紧缩（compaction）是⼀种解决外部碎⽚的⽅案（如图，开销很⼤）
内部碎⽚：简单来说就是分配个⼀个进程的内存空间中未使⽤的那部分内存。加⼊⼀个进程需要1000KB，我们分配了⼀个1002KB的孔，
那剩下的2KB就是碎⽚（这是⽆法使⽤的？）。
于是为了解决碎⽚问题就需要分段和分页技术，其根本思想是允许物理地址空间是⾮连续的。
⾮连续内存分配
段机制启动、页机制未启动：逻辑地址->段机制处理->线性地址=物理地址
段机制和页机制都启动：逻辑地址->段机制处理->线性地址->页机制处理->物理地址
分段机制（segmentation）
参考
先理解4个名词：
逻辑地址：分段机制下CPU把逻辑地址分为段选择⼦selector和段偏移offset
段描述符（描述段的属性）：由三部分参数组成：段基地址(BaseAddress)、段界限(Limit)和段属性(Attributes)
段描述符表（包含多个段描述符的“数组”）：分为GDT和LDT，⼤概就是全局和局部的关系。
段选择⼦（段寄存器，⽤于定位段描述符表中表项的索引）：细节见⽹址
然后简单介绍下逻辑地址转换成物理地址的过程：
CPU把逻辑地址（由段选择⼦selector和段偏移offset组成）中的段选择⼦的内容作为段描述符表的索引，找到表中对应的段描述符，然后
把段描述符中保存的段基址加上段偏移值，形成线性地址（LinearAddress）。如果不启动分页存储管理机制，则线性地址等于物理地
址。
上图是分段和分页机制的结合。
这个图是单纯的分段。
注意得到线性地址后会做⼀个检查，通过段描述符⾥的段基址和段界限
举个例⼦
4200这个逻辑地址（虚拟地址）被划分为段选择⼦和段偏移，
它的段偏移就是,orhex0x068,or104indecimal，段选择⼦01选的是34K，最后的线性地址（物理地址）就是
34K+104
注意段偏移是从上往下看还是从下往上看的问题，同时堆的计算和栈的计算（偏移不是实际的）是不⼀样的，最好先列出映射范围。下图给
出的是虚拟地址15KB转换成物理地址27KB的过程。
优点：⽀持⽤户视⾓，实现简单，可以有效利⽤内存。
缺点：⽆法利⽤碎⽚，必须搬移内存，造成性能损失（管理空闲空间较难）。
分页机制（paging）
分页（paging）内存管理⽅案允许进程的物理地址空间可以是⾮连续的。
基本概念：
将物理内存分为固定⼤⼩的块，称为帧（frame）；将逻辑内存也分为同样⼤⼩的块，称为页（page）。
每个进程有独⽴的页表。CPU⽣成的地址（虚拟地址）被分为两个部分：页号和偏移，页号作为页表中的索引，页表中的每⼀项称为页表条
⽬，页表条⽬存储地址转换的信息。
每新建⼀个进程OS都会为其新建⼀个页表，即使虚拟地址相同但映射到的物理地址是不同的。页表往往可能很⼤，所以存储在物理内存
中。
分页机制虚拟地址转换为物理地址的公式⼤致如下：
VPN_MASK⽤于从虚拟地址中获取部分位
PageTableBaseRegister（PTBR）：页基表寄存器，指向页表基址，改变页表只需要改变这个寄存器即可。
这样访问⼀个字节就需要两次内存访问（⼀次⽤于页表条⽬，⼀次⽤于字节）。
优点：易于对空闲空间的管理，更具有灵活性（能够有效地⽀持物理地址空间的抽象）
缺点：实现复杂，不正确地使⽤会导致速度过慢（获得进程的页表信息需要⼀次额外的内存访问），同时有很⼤的内存浪费（页表需要占⽤
物理内存）
TLB（translation-lookasidebuffer）
ATLBispartofthechip’smemory-managementunit(MMU),andissimplyahardwarecacheofpopularvirtual-to-physical
addresstranslations.
Uponeachvirtualmemoryreference,thehardwarefirstcheckstheTLBtoseeifthedesiredtranslationisheldtherein;ifso,
thetranslationisperformed(quickly)withouthavingtoconsultthepagetable.
TLB主要⽤于加速地址转换的过程，其是⼀个⼩⽽块的专⽤的硬件缓冲（硬件昂贵），通常TLB能存储64~1024个条⽬（页号和帧号组成
的键值对）。
注意VPN对于页表来说只是偏移，页表不存储VPN；
VPN对于TLB来说是需要存储的
⽽且对于页表条⽬和TLB条⽬来说其valid（有效位）的含义是不同的
页表条⽬的valid表⽰并没有给这个虚拟页分配/映射物理页
TLB的valid表⽰这个条⽬是否有效/存在
如果发⽣上下⽂切换（进程切换），TLB应该如何设置才能为进程提供地址保护？
如上图，假设PFN(100)为进程P1的，PFN(170)为进程P2的，TLB就⽆法区分。
解决⽅案：
①每次选择⼀个新的页表时，就flush（冲刷/删除）TLB，即设置所有的valid位为0，这明显会有较⼤的时间开销。
②在每个TLB条⽬中保存地址空间标识符（address-spaceidentifier,ASID），ASID可⽤来唯⼀地标识进程。当TLB试图解析虚拟页号
时，它确保当前运⾏进程的ASID与虚拟页相关的ASID相匹配。这样ASID就能允许TLB包含不同进程的条⽬。
TheMIPSR4000supportsa32-bitaddressspacewith4KBpages.
Thus,wr,thereareonly19bitsforthe
VPN;anduseraddresseswillonlycomefromhalftheaddressspace(therestreservedforthekernel)andhenceonly19
bitsofVPNareneeded.
TheVPNtranslatestouptoa24-bitphysicalframenumber(PFN),andhencecansupportsystemswithupto64GBof
(physical)mainmemory(2244KBpages)
概述⼀下TLB和页表⼀起使⽤的流程：
当CPU产⽣逻辑地址后，其VPN提交给TLB，如果TLB命中则得到了帧号并可⽤来访问内存。如果TLB失效，则需要访问页表，同时将页号
和帧号增加到TLB中。如果TLB条⽬已满，那么OS会选择⼀个来替换，替换策略有多种如LRU。另外，有的TLB允许某些条⽬固定，即不
会替换它们，如内核代码的条⽬。
到这⾥我们再回过头看看PTE中到底有什么
validbit：表⽰⼀个虚拟页到物理页的映射关系是否实际存在
protectionbit：表⽰⼀个页是否可读/写或和其他⼀些操作
presentbit：这个页在物理内存还是在磁盘（被换出了）
dirtybit：indicatingwhetherthepagehasbeenmodifiedsinceitwasbroughtintomemory.（脏位，该页是否被修改过）
Areferencebit(edbit):表⽰该页是否被访问过，⽤于页置换机制（如Clock算法）
多级页表
多级页表的⽬标是减少页表占⽤的物理内存。下⾯分析如何⽤⼆级页表表⽰⼀个线性页表。
Imagineasmalladdressspaceofsize16KB,,wehavea14-bitvirtualaddressspace,with8bits
fortheVPNand6bitsfortheoffset.
给出物理地址空间为16KB，页⼤⼩为64bytes，由此推算出虚拟地址空间多少位以及VPN和VPO
页⼤⼩决定了页偏移64Bytes->6bit
2^4X2^10/2^6=2^8即物理地址空间被分为256个物理页，则我们需要⽤8bit来表⽰物理页号PFN，⼜因为VPN与PFN⼀⼀对应，
所以VPN⽤8bit来表⽰
Alinearpagetablewouldhave2^8(256)entries（假如⽤线性页表表⽰）
要知道如何⽤⼆级页表表⽰这个线性页表，⾸先需要计算出这个线性页表所占⽤的物理内存
显然，这个页表有256个entries，假设每个PTE是4bytes（没有这个假设则⽆法计算），那么整个PTE就是1KB，需要分配16个64bytes
的物理页（每个物理页可分配16个页表条⽬）。
Thepagedirectoryneedsoneentryperpageofthepagetable;thus,ithas16entries.
Asaresult,weneed4bitsoftheVPNtoindexintothedirectory;weusethetopfourbitsoftheVPN,asfollows
对于页⽬录来说，每个页⽬录表条⽬对应的是页表的1个物理页，因此就有16个entries
PDBR⼀般⽤的是CR3寄存器，其锁定到⼀个物理页。CR3寄存器的保存与恢复是在与上下⽂切换相关任务的TSS段中进⾏的（每个进程不
同）。
CPU要读取某个数据，采⽤线性页表时，最坏情况下需要⼏次访存操作？采⽤⼆级页表时，最坏情况下需要⼏次访存操作？
线性页表：最坏情况下，假设该物理页在磁盘上（这⾥不考虑访问外存？以及中断恢复不需要重新访问页表？那最坏不就等同于必须了么，
⼆级页表必须3次）
->页表->(缺页异常处理)->内存字节
12
->页⽬录表->⼆级页表（可能需要创建）->(缺页异常处理)->内存字节
123
举个例⼦：⼆级页表的计算
Inthisexample,insteadofallocatingthefullsixteenpagesforalinearpagetable,weallocateonlythree:oneforthepage
directory,andtwoforthechunksofthepagetablethathavevalidmappings.
Hereisanaddressthatreferstothe0thbyteofVPN254:0x3F80.
Calculatethephysicaladdressof0x3F80
过程：0x3F80=000
PDI=1111PTI=1110VPO=000000
PageDirectory这⾥直接给出了，PDI就是个偏移（在锁定的物理页上的），我们找到第15个看valid为1得到PFN=101，这⾥的PFN指的
是物理页号（这⾥表⽰的是我们的⼆级页表在那个物理页，整个物理内存相当于⼀个0开始的PFN标记的序列）。然后我们找到PFN=101
的物理页，再看PTI这个偏移为14，找到第14个位置valid为1得到PFN=55，这个PFN也是物理页号（表⽰我们要找的byte在哪个物理页
上），最后拼接得到物理地址00
页置换策略
需要被换出的页的特征是什么？
需要被换出的页的特征是“不常⽤”。不同的页替换算法对该定义有不同的解释，FIFO页替换算法总是淘汰最先进⼊内存的页，时钟页替
换算法淘汰未被访问过的页。
FIFO：置换时选择最旧的页置换，可以创建⼀个FIFO队列来管理内存中的页。
OPT（optimalpage-replacementalgorithm）：最优页置换算法，假设已经知道之后要访问哪些页（这往往是不可能的），选择1个最
长时间不会⽤的页替换掉。
LRU（least-recently-used）：最近最少使⽤算法，将最长时间未使⽤的页置换掉。可以⽤计数器或栈来实现，⽆论⽤哪⼀种⽅法，每次
内存引⽤都必须更新时钟域或者栈，⾸先这需要硬件⽀持，其次如果每次更新都采⽤中断来实现时间开销将⼤幅度上升。
CLOCK（⼆次机会算法/近似模拟LRU）：选择⼀个页时，检查其引⽤位，如果值为0就直接置换该页，如果值为1，则给这个页第⼆次机
会（置为0）并继续往下选择。实现⽅法：通常页以循环队列组织管理，⽤⼀个指针表⽰下次要置换哪个页。
Belady现象
指的是对有的页置换算法，页错误率（缺页次数/总访问次数）可能随着分配的帧数的增加⽽增加。
举个例⼦说明Belady异常：⽤串1,2,3,4,1,2,5,1,2,3,4,5
推荐这么画过程
附：内核内存的分配
内核内存的分配通常是从空闲内存池中获取的，⽽不是从满⾜普通⽤户模式进程的内存链表中获取的。主要有如下两个原因：
1.内核需要为不同⼤⼩的数据结构分配内存，其中有的不到⼀页。因此，内核必须谨慎使⽤内存，并试图减低碎⽚浪费。
2.有的硬件要直接与物理内存打交道，⽽不需要经过虚拟内存接⼝，因此需要内存常驻在连续的物理页中。⽤户进程所分配的页不必要在连
续的物理内存中。
Buddy系统
概述：从物理上连续的⼤⼩固定的段上进⾏分配，内存按2的幂的⼤⼩来进⾏分配。
优点：可通过合并⽽快速地形成更⼤的段，解决了外碎⽚的问题
缺点：采⽤buddy算法，解决了外碎⽚问题，这种⽅法适合⼤块内存请求，不适合⼩内存区请求。虽然减少了内碎⽚，但没有显著提⾼系统
效率。
实现：
假设连续内存段的⼤⼩原来为256KB，⽽内核申请21KB内存，就会按如图所⽰来等分内存，直到得到⼀个最⼩的可满⾜需求的空闲内存块
（32KB再往下分不满⾜），最后⽤CL来满⾜内存请求。
如果上述CL被释放，则会⾃底向上合并为原来256KB的段。
Slab分配
Slab分配器思想
1）⼩对象的申请和释放通过slab分配器来管理。
2）slab分配器有⼀组⾼速缓存，每个⾼速缓存保存同⼀种对象类型，如i节点缓存、PCB缓存等。
3）内核从它们各⾃的缓存种分配和释放对象。
4）每种对象的缓存区由⼀连串slab构成，每个slab由⼀个或者多个连续的物理页⾯组成。这些页⾯种包含了已分配的缓存对象，也包含了
空闲对象。
主要优点：
①没有因碎⽚⽽引起的内存浪费。因为每个内核数据结构都有相应的cache，⽽每个cache都由若⼲slab组成，每个slab⼜分为若⼲个与对
象⼤⼩相同的部分。
②内存请求可以快速满⾜。