操作系统（11）----内存管理3：https://developer.aliyun.com/article/1511165
总结：
如何进行分区的分配与回收操作?假设系统采用的数据结构是“空闲分区表，该如何分配?
分区的分配：
若将进程5（4MB）放入分区号为1的分区，那么表项就会做如下改变
若进程5（4MB）放入分区号为3的分区，分区3大小刚好为4MB，那么分区表就会将此分区删除。
分区的回收：
① 若进程4运行完毕需要进行回收，回收区的后面有一个相邻的空闲分区，那么就合并两个相邻的空闲分区。
那么需要改变分区的大小与起始地址：
② 若回收区前面有一个相邻的空闲分区，那么需要将两个空闲分区合并为一个。
那么不需要改变起始地址，只需要改变分区大小：
③ 若回收区的前、后各有一个相邻的空闲分区,需要将3个空闲分区合并为一个
空闲分区表修改如下：
④ 回收区的前、后都没有相邻的空闲分区
就需要新增表项：
注：各表项的顺序不一定按照地址递增顺序排列，具体的排列方式需要依据动态分区分配算法来确定。
动态分区分配的特点：动态分区分配没有内部碎片，但是有外部碎片。
2.非连续分配管理方式
连续分配指的是为用户进程分配的必须是一个连续的内存空间，而非连续分配指的是为用户进程分配的可以是一些分散的内存空间。
（1）基本分页存储管理
•页框和页
将内存空间分为一个个大小相等的分区(比如:每个分区4KB)，每个分区就是一个“页框”(页框=页帧=内存块=物理块=物理页面)。每个页框有一个编号，即“页框号”(页框号=页帧号=内存块号=物理块号=物理页号)，页框号从0开始。
将进程的逻辑地址空间也分为与页框大小相等的一个个部分：每个部分称为一个“页”或“页面”。每个页面也有一个编号，即“页号”，页号也是从0开始。操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一 一对应的关系。
•页表
操作系统会建立一张页表，记录页面和页框的一 一对应关系，即知道每个进程的每个页面在内存中存放的位置。页表一般存放在PCB（进程控制块）中。
1.一个进程对应一张页表
2.进程的每个页面对应一个页表项
3.每个页表项由“页号”和“块号”组成
注意：页表记录的只是内存块号，而不是内存块的起始地址。J号内存块的起始地址 =J*内存块大小
4.页表记录进程页面和实际存放的内存块之间的映射关系
每个页表项占多少字节？
假设某系统物理内存大小为4GB，页面大小为4KB，则每个页表项至少应该为多少字节?
因为页面和内存块大小相等，所以
内存块大小=页面大小=4KB=2^12B
4GB的北村总共会被分为2^32/2^12=2^20个内存块
内存块号的范围应该是0~2^20-1
内存块号至少要用20bit来表示
那么以字节为单位分配的话，即至少要用3B来表示块号（3*8=24bit）
页号需要占多少字节？
页表项连续存放，因此页号可以是隐含的，不占存储空间的（类比数组的下标）
例如：
假设页表中的各页表项从内存地址为x的地方开始连续存放..…如何找到页号为i的页表项?
i号页表项的存放地址=X+3*i
由于页号是隐含的，因此每个页表项占3B，存储整个页表至少需要 3*(n+1)B。
所以一个页表项逻辑上需要存放页号和块号两个信息，实际物理上只需要存放块号这一信息
如何实现地址转换？
在连续存放中，CPU将重定位寄存器中的起始位置与某内存单元存储的逻辑地址相加得到最终目标地址，这一逻辑地址相当于"偏移量"
对于非连续存放而言：
虽然进程的各个页面是离散存放的，但是页面内部是连续存放的
如果要访问逻辑地址 A，则
①首先确定逻辑地址A对应的"页号"P
②操作系统再根据页号查询页表，找到页号对应的块号，得出P号页面在内存中的起始地址，即内存块大小*块号
③确定逻辑地址A的"页内偏移量"W
④那么逻辑地址A对应的物理地址=P号页面在内存中的起始地址+页内偏移量W
步骤①中，如何确定页号和页内偏移量？
页号=110/50=2
页内偏移量=110%50=10
根据上图，可以很清楚的知道逻辑地址对应的页号为2号页面，页内偏移量为10。
页号=逻辑地址/页面长度(取除法的整数部分)
页内偏移量=逻辑地址%页面长度(取除法的余数部分)
逻辑地址可以拆分为(页号，页内偏移量)
通过页号查询页表，可知页面在内存中的起始地址
页面在内存中的起始地址+页内偏移量=实际的物理地址
注：在计算机内部，地址是用二进制表示的如果页面大小 刚好是2的整数幂，则计算机硬件可以很快速的把逻辑地址拆分成(页号，页内偏移量)
可以观察到，在32位2进制中，前面的红色部分（20位）就是页号，后面的黑色部分(12位)就是页内偏移量，具体的例子如下：
结论：如果每个页面大小为 2^K B，用二进制数表示逻辑地址则末尾K位即为页内偏移量，其余部分就是页号
逻辑地址结构：
所以，通过页面大小可推出页内偏移量，通过页内偏移量也可以推出页面大小，再通过地址位数，可以得到逻辑地址的结构。
若某些题目中页面大小不是2的整数幂，那么只能用常规的方法：
若题目中页面大小是2的整数幂，那么如果知道页面大小就可以推出页号，例如用 32 个二进制位表示逻辑地址，页面大小为
4KB=2^12B，所以页内偏移量占12位，页号占20位，0号页（00000000000000000000）
1号页（00000000000000000001）……
以上是逻辑地址的拆分，其实，若页面大小为2的整数幂，对于物理地址的计算也很方便：
我们之前知道J号内存块的起始地址=J*内存块大小，但是，如果页面大小是2的整数幂，那么起始物理地址就是等于内存块号，如下图例子，后面页内偏移量占12位，前面内存块号占20位，所以3号内存块的起始地址就为前面的20位（00000000000000000011），以及后面的12位（000000000000）结合而成
例如：
假设通过查询页表得知1号页面存放的内存块号是9(1001)，则
则逻辑地址4097对应的物理地址=页面在内存中存放的起始地址+页内偏移量
（页内偏移量=4097%4096=1），最后得到：
结论:如果页面大小刚好是2的整数幂，则只需把页表中记录的物理块号拼接上页内偏移量就能得到对应的物理地址。而如果不是2的整数幂，那么页面在内存中存放的起始地址必须通过
内存块大小*块号计算
总结：页面大小刚好是2的整数幂有什么好处?
①逻辑地址的拆分更加迅速，如果每个页面大小为 2^K B，用二进制数表示逻辑地址，则末尾K位即为页内偏移量，其余部分就是页号。因此，如果让每个页面的大小为2的整数幂，计算机硬件就可以很方便地得出一个逻辑地址对应的页号和页内偏移量，而无需进行除法运算，从而提升了运行速度。
②物理地址的计算更加迅速,根据逻辑地址得到页号，根据页号查询页表从而找到页面存放的内存块号，将二进制表示的内存块号和页内偏移量拼接起来，就可以得到最终的物理地址。
•基本地址变换机构
基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。
通常会在系统中设置一个页表寄存器(PTR)，存放页表在内存中的起始地址F和页表长度M。进程未执行时，页表的始址和页表长度放在进程控制块(PCB)中，当进程被调度时，操作系统内核会把它们放到页表寄存器中。
设页面大小为L，逻辑地址A到物理地址E的变换过程如下:
注：页面大小是2的整数幂
若某进程被调度，则需要上处理机运行，那么进程切换相关的内核程序就会负责恢复进程运行环境，进程运行环境相关的信息本来是保存在内存的系统区的PCB中的，之后，内核程序会把这些数据放到一系列寄存器中，其中包括页表寄存器。
同时程序计数器PC中的数据也需要恢复，即指向这一进程下一条指令的逻辑地址A
那么CPU怎么怎么通过逻辑地址找到相应的物理地址?
①计算页号P和页内偏移量W(如果用十进制数手算，则P=A/L，W=A%L；但是在计算机实际运行时，逻辑地址结构是固定不变的，因此计算机硬件可以更快地得到二进制表示的页号、页内偏移量)
②比较页号P和页表长度M，若P≥≥M，则产生越界中断，否则继续执行。(注意:页号是从0开始的，而页表长度至少是1，因此 P= M 时也会越界)
③若不越界，页表中页号P对应的页表项地址=页表起始地址F+页号P*页表项长度，取出该页表项内容b，即为内存块号。
注意区分页表项长度、页表长度、页面大小的区别。页表长度指的是这个页表中总共有几个页表项，即总共有几个页；页表项长度指的是每个页表项占多大的存储空间；页面大小指的是一个页面占多大的存储空间。
④计算E=b*L+W，用得到的物理地址E去访存。(如果内存块号、页面偏移量是用二进制表示的，那么把二者拼接起来就是最终的物理地址了)
可以看到以上操作总共需要访问两次内存：
第一次访问：查页表
第二次访问：访问目标内存单元
例：若页面大小L为1K字节，页号2对应的内存块号b=8，将逻辑地址A=2500转换为物理地址E。等价描述:某系统按字节寻址，逻辑地址结构中，页内偏移量占10位（2^10B=1KB），页号2对应的内存块号b=8，将逻辑地址 A=2500 转换为物理地址E。
在分页存储管理(页式管理)的系统中，只要确定了每个页面的大小，逻辑地址结构就确定了。因此，页式管理中地址是一维的。即，只要给出一个逻辑地址，系统就可以自动地算出页号、页内偏移量两个部分，并不需要显式地告诉系统这个逻辑地址中页内偏移量占多少位。
每个页表项的长度是相同的，页号是“隐含”的
例如：假设某系统物理内存大小为4GB，页面大小为4KB，的内存总共会被分为2^32/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个页表项
1024号页表项虽然是存放在下一个页框中的，但是它的地址依然可以用X+4*1024得出
结论：理论上，页表项长度为3B即可表示内存块号的范围，但是，为了方便页表的查询，常常会让一个页表项占更多的字节，使得每个页面恰好可以装得下整数个页表项。
•具有快表的地址变换机构
快表，又称联想寄存器(TLB，translation lookaside buffer)，是一种访问速度比内存快很多的高速缓存(TLB不是内存)，是用SRAM实现的，而主存是用DRAM实现的，SRAM比DRAM快，快表用来存放最近访问的页表项的副本，是一种“相联存储器”，可以按内容寻访，即可以通过硬件电路快速找到快表中是否有匹配的页号，这样可以加速地址变换的速度。与此对应，内存中的页表常称为慢表。
注：TLB 和 普通 Cache 的区别：
TLB 中只有页表项的副本，而普通 Cache 中可能会有其他各种数据的副本
若在告诉缓存中已经找到了想要的数据，那么就不必访问内存了，并且CPU从Cache高速缓存存取数据的速度比内存快很多，所以使用此方法，CPU在进行地址变换时，查询页表的速度就快的多。
能否把整个页表都放在TLB中？不行
与高速缓存一样，他的容量小，且更贵。
操作系统（11）----内存管理5：https://developer.aliyun.com/article/1511172
