【操作系统】分页存储
- 连续分配的缺点
- 一个进程占用一片连续的空间
- 且一个分区（块）只能给一个进程使用，导致内存碎片的产生
- 非连续分配
- 一个进程所需的内存可以离散分配
- 分页管理内存计算
- 需要知道页号 、页内偏移量、内存中的页框号（页框号也叫块号）
- 页号由逻辑地址除以页长取整
- 页内偏移量由逻辑地址除以页长取余
- 页框号由页号查页表得到
- 这样设计的目的是红色部分直接是页号、黑色部分直接是偏移地址
- 页表
- 一个进程对应一张页表
- 每一页对应一个页表项
- 页表项由页号和块号组成
- 局部性原理
- 时间局部性：如果执行了某条指令，不久后很有可能再次执行；若某个数据被访问过，不久后很可能再次访问（因为程序中循环结构的存在）
- 空间局部性：一旦访问了某个存储单元，其附近的单元也很有可能会被访问（很多数据在内存中是连续存放的）
- 快表
- 访问速度比内存快很多的**高速缓冲存储器，**用于存储当前访问的若干页表项，加速地址变换。所以内存中的页表也叫慢表
- 只需要访问一次内存
- 由于局部性原理，快表命中率可达到九十多
- 两级页表
-
单级页表的问题
- 页表必须连续存放，当页表过大时，光页表就占用很多连续的页框（不符合离散分配的理念）
- 局部性原理，当页表过大时，我们只会访问其中的很小的一部分，没必要让整个页表常驻内存
-
实现两级页表
- 将逻辑地址划分为三段，解决第一个问题
- 可以在访问时才把页面调入内存（虚拟存储技术），增加一个标志位，用于标识是否调入内存
- n级页表访问内存的次数为n+1次，所以要利用快表进行性能的提升
- 虚拟内存
- 传统存储方式的缺点：
- 一次性：需要一次性分配进程所需的全部内存，这样会导致大作业无法运行；系统的并发度下降
- 驻留性：一旦进程开始，就会一直驻留在内存中，直到进程结束
- 虚拟内存也是利用局部性原理
- 将很快会用到的部分装入内存，暂时不用的放在外存，需要时通过操作系统进行调用
- 虚拟地址的实际容量=min（内存+外存，CPU寻址范围）
- 虚拟内存的实现
- 采用调用和置换
- 采用离散分配的方式
- 根据存储的类型不同分为：请求分页、请求分段、请求段页式
- 采用置换算法将暂时不用的信息换出内存
- 请求分页
- 通过在原来的页表加入四个字段实现：状态位、访问字段、修改位、外存地址
- 当页面调用时内存空间不够，使用页面置换算法
- 页面置换算法
- 页面置换算法核心问题就是决定将哪个页面置换到外存中
- 常见的有五种算法
-
最佳置换算法（OPT）：每次淘汰的页面是以后不使用，或者最长时间不再被访问的页面，这样可以保证最低的缺页率；OPT是一种理想的结果，无法实现，通常用来衡量其他算法
-
先进先出置换算法（FIFO）：每次淘汰最早进入的页面；唯一会产生Belady异常算法，即分配更多的内存，但是可能有更多的缺页次数
-
最近最久未使用置换算法（LRU）：淘汰最近最久没使用的页面；性能好，但是开销大
-
时钟置换算法（NRU）
-
改进型时钟置换算法
-