1.6.基本分页存储管理
1.6.1.基本分页存储管理的概念
1.若系统支持分页存储，系统将会把内存分为若干个大小相等的分区（页框）
2.①页框、页帧：内存在物理上被划分为若干个大小相等的分区
②页、页面：进程在逻辑上被分为和页框大小相等的部分
③页框、页帧和页、页面一一对应（操作系统通过页表记录这种关系）3.页表：操作系统通过页表能够知道进程的每个页面在内存中的存放位置（页表存储在PCB中）
①一个进程对应一个页表（一一对应）
②进程的每个页面对应一个页表项（页表的一行）
3.页表：操作系统通过页表能够知道进程的每个页面在内存中的存放位置（页表存储在PCB中）
①一个进程对应一个页表（一一对应）
②进程的每个页面对应一个页表项（页表的一行）
③页表项由页号和块号组成：反映进程页面和实际存放的内存块的映射关系（各个页面离散存放）
④每个页表项长度相同
⑤页表项占用存储空间的计算：通过内存块的总块数
仅需计算块号的占用空间，页号隐含，不占用存储空间（页表项连续存放，类似数组下表）
内存总大小 / 每个内存块的大小 = 内存块的总数m→ 最少能用n位二进制数表示m （n为bit数）→ n向上取8的倍数 / 8（按字节存放）
⑥页表中记录的是起始块号，而不是内存块的起始地址（起始地址 = 内存块号 * 内存块大小）
⑦实现逻辑地址到物理地址的转换：页号→该页起始地址→物理地址=该页起始地址 + 页内偏移量
页号 = 逻辑地址 / 页面长度；页内偏移量 = 逻辑地址 % 页面长度
实际在计算过程中，若页面大小为2 ^ K，后K位为页内偏移量，之前位为页面长度
若有N位表示页内偏移量，则每个页面共有2 ^ N个存储单元
若有M位表示页号，则该内存共有2 ^ M个页
1.6.2.基本地址变换机构
1.页表寄存器：存放页表在内存中的起始地址和页表长度（这两个信息只在进程被调度时存放在页表寄存器中；进程未被调度时，存放在PCB中）
2.逻辑地址转换成物理地址的过程：
其中，转换过程需要访问两次内存：①查找页表项 ②访问物理地址对应的内存单元
1.6.3.具有快表的地址变换机构
1.快表（TLB）的作用是加快地址转换速度（TLB是缓存，不是内存）：TLB存放的是最近访问的页表项的副本
2.快表是硬件，当发生进程切换时，快表的内容也会被清除
3.查询有两种方式：①先查询快表，后查询慢表 ②快表和慢表一起查询
4.若快表未命中（没有目标页表项），则需要查询内存中的页表（慢表），并将该页表项复制一份到快表中（若快表已满，则需要对其进行替换）；若快表命中，则无需访问内存（指的是查询页表项的步骤无需访问内存）
5.快表命中，访存一次：访问物理地址对应的内存单元；
快表未命中，访存两次：①查询内存中页表的页表项 ②访问物理地址对应的内存单元
6.快表大幅度提升工作效率的原因：局部性原理
1.6.4.两级页表
1.单级页表存在的问题：
①页表必须连续存放，若页表过大，则需要占用多个连续的页框
②根据局部性原理，不需要让整个页表都常驻内存，一段时间内可能只需要访问几个特定的页面
2.问题①的解决：用单级页表解决离散存放内存空间的思想
将页表分组，一个分组占用一个内存块，再为离散存放的页表再建立一张页表，该页表称为页目录表
3.①页号有20位→页表项有1M个（2 ^ 20）
②页面大小4KB，页表项大小为4B→一个页面可以存放1K个页表项（4KB / 4B = 1K）→所有页表项共需1K个页面存放（1M / 1K = 1K）
③为二级页表（这1K个页面）设置上一级页表（保存小页表间的相对顺序、存放的块号等）→页目录表（如图中0号页表存放在3号页块）
④页表结构也相应发生变化：一级页号占10位（表示某个二级页表所存放在哪个内存块号），二级页号占10位（表示具体某个页号存放在哪个内存块号）、页内偏移量占12位
4.地址转换过程：
5.问题②的解决：在需要该页面时，再将该页面调入内存。与此同时，就需要增加一个标志位，标记该页是否已经调入内存；若想访问的页面此时并不在内存中，则将会发生缺页中断，然后将目标页面调入内存中
6.①各级页表的大小不能超过一个页面：每个页面不得存放过多（超过其存储空间大小）的页表项
②多级页表的离散存储的特性是通过牺牲访存时间得来的：N级页表需要N+1次访存（没有快表）
1.7.基本分段存储管理
1.根据逻辑关系将进程分为若干个段（可以是根据不同的函数等等）
2.段内连续，段间离散
3.段号的位数决定最大段数；段内地址的位数决定每个段的最大长度
4.段表：操作系统通过段表能够知道进程的每个段在内存中的存放位置
①段表由段号、段长（每个段的长度可能不同）和段基址（段的起始地址）组成
②段表项长度相同：段长的最大长度被段内地址的位数限制，因此段长固定取最大长度；段基址由内存的地址空间决定，每个段的起始地址都需要相同位数的地址表示
③段号隐含，不占用存储空间（类似页号）
5.段表寄存器：存放段表在内存中的起始地址和段表长度（这两个信息只在进程被调度时存放在段表寄存器中；进程未被调度时，存放在PCB中）（类似页表寄存器）
6.地址转换过程：与页表的地址转换过程相比多④，原因是页表中每个页面的大小都相等，而段表中每个段的大小可能都不相同，因此需要对段内偏移量和段长进行对比和检查
7.分段和分页的对比：
①分页是系统行为，对用户不可见；分段是用户行为，对用户可见
②分页大小固定；分段大小不固定
③分页地址一维（地址）；分段地址二维（段名和段内地址）
④分段比分页更容易实现信息的共享和保护：分段仅需在各自的段表上增加关于同一个段的信息就可以实现对该段的共享；分页因为每个页面中可能既包含需要共享的内容，也包含不能共享的内容，难以进行区分，因此难以实现共享，而分段存储是根据逻辑进行分段，因此不会出现这种情况
⑤分段和分页都需要两次访存：①找到内存中的段表/页表 ②访问目标内存单元
在引入快表后，若快表命中，则都仅需一次访存：访问目标内存单元
1.8.段页式管理方式
1.分段/分页管理方式的优缺点：
2.先按逻辑分段，再将各段分页：将段内地址分为页号和页内偏移量
3.分段是用户行为，对用户可见；段内分页是系统行为，对用户不可见
4.段页式管理中段表由段号（隐含）、页表长度（该段占用几个页表）和页表存放块号（该内存块中存放该段所占用的若干页面所对应的内存块号，根据页号查询其所对应的页表项）
5.一个进程对应一个段表，但是可能会对应多个页表
6.地址转换过程：需要对页号进行越界检查，因为每个段长不同导致页数可能不同
快表未命中需要三次访存：①访问内存中的段表 ②访问内存中的页表 ③访问目标内存单元
快表命中仅需访存一次：访问目标内存单元
2.虚拟内存管理
2.1.虚拟存储的基本概念
1.传统存储管理方式的特征和缺点：
2.虚拟存储技术基于局部性原理（空间局部性和时间局部性）
3.虚拟内存的定义和特征：
①马上用到的装入，暂时用不到的不装入
②发生缺页时调入内存
③将内存中暂时用不到的调出外存
4.如何实现虚拟内存技术：
①请求调页/调段功能：访问的信息不在内存时，需要将该信息从外存调入内存
②页面置换/段置换功能：暂时用不到的信息换出外存
2.2.请求分页管理方式
1.请求分页管理方式的请求页表相较分页管理方式的基本页表需要新增几个字段：
2.缺页中断机构：缺页由当前执行指令引起，属于内中断；一条指令可能引发多次中断
（1）内存中尚有空闲的内存块：将外存的缺页信息放入空闲内存块中
①此时发生缺页，操作系统就需要根据请求页表中的直到该内存中缺失的页面存放在外存的位置
②内存块号a此时为空闲，因此可以将a分配给此时缺页的进程再把目标页面从外存放入内存中，并相应修改请求页表中的内容
（2）内存中没有空闲块：根据页面置换算法选择一个页面淘汰，若该淘汰页面修改过，则需要写回外存；未修改过，则不需要写回外存，直接淘汰。之后将缺页的信息调入内存占用该淘汰页面
3.地址转换过程中，相较于分页管理方式，请求分页管理方式需要多做三件事：
①请求调页：判断该页是否当前在内存中，即是否要将该页面从外存调入内存
②页面置换：如果该页并不在内存，且内存中没有空闲块，需要进行页面置换（换出内存某些页）
③修改页表：发生页面调入/调出/访问页面等等事件时需要对页表项进行修改
4.如果快表命中，就说明内存中一定有该页（快表就是内存的副本）
快表未命中，查询内存中的慢表，并且查询该表是否在内存中，如果不在则需要调入内存，即产生缺页中断（分页管理方式中，页面都在内存中，因此无需查询该页是否已调入内存）
5.补充细节：
①只有写指令才需要修改"修改位"，并且，一般只对快表中的数据进行修改，只有快表中的数据被替换的时候，才对内存中的数据进行修改（类似Cache的写回法）
②缺页中断处理需要保留CPU现场
③页面置换算法决定换出哪一个页面（内存满时）
④换入/换出页面需要慢速I/O设备的配合，因此将会导致系统开销
⑤页表调入内存后，不仅需要修改慢表，也需要将慢表中关于其的表项复制到快表中
2.3.页面置换算法
缺页未必会导致页面置换，有空闲内存块的缺页采用调页解决缺页；没有空闲内存块时的缺页采用页面置换解决缺页
2.3.1.最佳置换算法（OPT）
1.算法思想：淘汰以后用不使用或者最长时间不访问的页面
2.最佳置换算法需要提前知道进程的运行将会使用哪些页，因此，其无法实现，只是理想状态
2.3.2.先进先出置换算法（FIFO）
1.算法思想：淘汰最早进入内存的页面
2.缺点：没有考虑到先进入内存的页面在之后也可能经常访问到
2.3.3.最近最久未使用置换算法（LRU）
1.算法思想：淘汰当前最久未使用的页面
2.性能最接近最佳置换算法，但实现起来较困难
