操作系统课件第5章 存储管理(2)

缺页中断(Page Fault) 处理
• 如果内存中有空闲块，则分配一个块，将 要调入的页装入该块，并修改页表中相应 页表项的状态位及相应的内存块号；
• 若此时内存中没有空闲块，则要淘汰某页 （若被淘汰页在内存期间被修改过，则要 将其写回外存）。
5.4.4 请求页式管理中的置换算法
• 功能：需要调入页面时，选择内存中哪个 物理页面被置换。称为replacement policy。
• 原理：一个程序的几个代码段或数据段， 按照时间先后来占用公共的内存空间。
覆盖技术
覆盖技术
缺点： • 编程时必须划分程序模块和确定程序模块 之间的覆盖关系，增加编程复杂度。 • 从外存装入覆盖文件，以时间延长来换取 空间节省。
交换技术(swapping)
• 原理：暂停执行内存中的进程，将整个进 程的地址空间保存到外存的交换区中（换 出swap out），而将外存中由阻塞变为就 绪的进程的地址空间读入到内存中，并将 该进程送到就绪队列（换入swap in）。
m=3时，缺页中断9次 m=4时，缺页中断10次
• FIFO页面淘汰算法会产生异常现象 （Belady现象），即：当分配给进程的物 理页面数增加时，缺页次数反而增加
最近最久未使用置换算法（LRU）
置换原理 • 选择最后一次访问时间距离当前时间最长 的一页并淘汰之。即淘汰最长时间没有使 用的页。 特点 • 局部性原理的合理近似，性能接近最佳置 换算法。实现代价很高（软件方法或硬件 方法）
• 覆盖与交换的区别： （1）与覆盖技术相比，交换不要求程序员给 出程序段之间的覆盖结构。
（2）交换是在进程或作业之间进行，而覆盖 则主要在同一个作业或进程内进行。覆盖 只能覆盖那些与覆盖程序段无关的程序段
5.4 页式管理
• 固定分区管理存在内碎片，可变分区管理 存在外碎片。对外碎片的移动要浪费处理 机的许多时间，而且存储每个用户作业都 要受到实际存储容量的限制，这就使内存 的空闲空间得不到充分利用。 • 这个问题的主要原因是一个作业必须存放 在一段连续的内存区域中。
分段存储管理基本思想
内存划分 • 内存空间被动态的划分为若干个长度不相同的 区域，称为物理段，每个物理段由起始地址和 长度确定。(物理内存的管理采用动态分区) 内存分配 • 以段为单位分配内存，每一个段在内存中占据 连续空间（内存随机分割，需要多少分配多 少），但各段之间可以不连续存放。
5.5.2 段式管理的实现原理
3. 地址变换
• 指令所给出地址分为两部分：逻辑页号， 页内偏移地址－>查进程页表，得物理页号 －>物理地址
5.4.3 动态页式管理
• 请求页式管理 • 预调入页式管理
5.4.3 -- 请求分页存储管理
1、基本思想 在进程开始运行之前，不是装入全部页面， 而是装入几个或零个页面，之后根据进程 运行的需要，动态装入其它页面；当内存 空间已满，而又需要装入新的页面时，则 根据某种算法淘汰某个页面，以便装入新 的页面。
• 页式管理正是为了减少碎片以及为了只在 内存存放那些反复执行或即将执行的程序 段与数据部分，而把那些不经常执行的程 序段和数据存放于外存，待需要执行时调 入，以提高内存利用率而提出来的。
5.4.1 页式管理的基本原理
• 用户程序划分 • 把用户程序的逻辑地址空间划分成大小相 等的部分，称为页（page） 。从0开始编 制页号，页内地址是相对于0编址。
5.4.2 静态页面管理
• 静态页面管理方法是在作业或进程开始执 行之前，把该作业或进程的程序段和数据 按页全部装入内存的各个页面中，这些也 不必连续，并通过页表(page mapping table)和硬件地址变换机构实现虚拟地址到 内存物理地址的映射。
1. 内存页面分配与回收
1、页表 将页号和页内地址转换成内存地址，必须 要有一个数据结构，用来登记页号和块的 对应关系和有关信息。 • 这样的数据结构称为页表。 • 系统为每个进程建立一个页表，页表的长 度和首地址存放在该进程的进程控制块 （PCB）中。
3. 段式地址变换
5.5.3 段式管理的优缺点
分段与分页主要有以下差别： • 分页是出于系统管理的需要，分段是出于 用户应用的需要。 • 一条指令或一个操作数可能会跨越两个页 的分界处，而不会跨越两个段的分界处。 • 页大小是系统固定的，而段大小则通常不 固定。
优点： • 没有内碎片，外碎片可以通过内存紧缩来 消除。 • 便于改变进程占用空间的大小。 缺点： • 进程全部装入内存。
页表内容
页表包含以下几个表项： • 页号：登记程序地址空间的页号。 • 块号(页面号)：登记相应的页所对应的内存 块号。 • 其它：登记与存储信息保护有关的信息。
页表内容
• 例 ������ 进程A有4页分别装入内存的第0，1，2， 3 块；进程B有3页装入内存的第4，5，6块； 进程C有4页装入内存的第7,8,9,10块；某 一时刻，进程B执行结束，进程D进入内存， 它有5页，被装入内存的第4，5，6，11， 12块。
进程页表
静态页式管理的数据结构
2、请求表 整个系统有一个请求表，描述系统内各个 进程或作业页表的位置和大小，用于内存 分配和地址转换，也可以结合到各进程的 PCB里
3、存储页面表 • 一个系统只有一张存储页面表。它指出内 存各页面是否被分配，以及未分配页面的 总数。 • 数据结构：位示图，空闲页面链表 • 位示图：在内存中划分一块固定区域，每 个单元的每个位代表一个页面，如果该页 面已被分配，则对应比特位置1，否则置0。 占据一部分内存容量。
段表和页表
动态地址变换
5.6 局部性原理
• 局部性原理(principle of locality)：指程序 在执行过程中的一个较短时期，所执行的 指令地址和指令的操作数地址，分别局限 于一定区域。 • 时间局部性 • 空间局部性
局部性原理的具体体现 • 程序在执行时，大部分是顺序执行的指令， 少部分是转移和过程调用指令。 • 过程调用的嵌套深度一般不超过5，因此执 行的范围不超过这组嵌套的过程。 • 程序中存在相当多的循环结构，它们由少 量指令组成，而被多次执行。 • 程序中存在相当多对一定数据结构的操作， 如数组操作，往往局限在较小范围内。
• Belady现象的原因：FIFO算法的置换特征 与进程访问内存的动态特征是矛盾的，即 被置换的页面并不是进程不会访问的。
先进先出页面置换算法(FIFO)(例)
有一虚拟存储系统，采用先进先出的页面淘 汰算法。在内存中为每个进程分配3块。进 程执行时使用页号的顺序为4 3 2 1 4 3 5 43215 (1) 该进程运行时总共出现几次缺页。 (2) 若每个进程在内存有4块，又将产生几次 缺页。 (3) 如何解释所出现的现象。
2、页表机制
• 状态位：表示该页是否装入内存； • 访问位：此页在一段时间被访问的次数，可用 来决定淘汰哪页（由不同的算法决定）； • 修改位：查看此页是否在内存中被修改过； • 外存地址：该页在外存上的位置。
缺页中断
• 在地址映射过程中，在页表中发现所要访 问的页不在内存，则产生缺页中断。 • 操作系统接到此中断信号后，就调出缺页 中断处理程序，根据页表中给出的外存地 址，准备将该页调入内存。 • 此时应将缺页的进程挂起（调页完成唤醒）
2. 分配算法
• 请求表给出进程或作业要求的页面数。然 后，由存储页面表检查是否有足够的空闲 页面，如果没有，则本次无法分配。如果 有则首先分配设置页表，并填写请求表中 的相应表项后，按一定的查找算法搜索出 所要求的空闲页面，并将对应的页面号填 入页表中。
• 页面回收：当进程执行完毕时，拆除对应
的页表，并把页表中的各页面插入存储页 面即可。
5.5.4 段页式存储管理基本思想
• 用户程序划分 按段式划分（对用户来讲，按段的逻辑关系 进行划分；对系统讲，按页划分每一段） • 逻辑地址
• 内存划分 按页式存储管理方案 • 内存分配 以页为业建立一张段表，记 录了每一段的页表始址和页表长度 • 页表：系统为每个段建立一张页表，记录 了逻辑页号与内存块号的对应关系（每一 段有一个，一个程序可能有多个页表） • 内存分配管理：同页式管理
逻辑地址 • 用户程序的划分是由系统自动完成的，对 用户是透明的。一般一页的大小为2的整数 次幂。经过页划分之后，用户程序的逻辑 地址变为页号p与页内地址w所组成。
内存空间 • 按页的大小划分为大小相等的区域，称为 块或内存块（物理页面，页框）。
内存分配 • 以页为单位进行分配，并按作业的页数多 少来分配。逻辑上相邻的页，物理上不一 定相邻。
先进先出页面置换算法(FIFO)
置换原理 • 选择建立最早的页面被置换。可以通过链 表来表示各页的建立时间先后。 特点 • 性能较差。较早调入的页往往是经常被访 问的页，这些页在FIFO算法下被反复调入 和调出。并且有Belady现象
• Belady现象：采用FIFO算法时，如果对一 个进程未分配它所要求的全部页面，有时 就会出现分配的页面数增多，缺页率反而 提高的异常现象。
例题
• 某程序在内存中分配三个块，访问页的走 向为4，3，2，1，4，3，5，4，3，2，1， 5，按FIFO、LRU算法分别计算缺页次数。 假设开始时所有页均不在内存。
FIFO
LRU
5.5 段式与段页式存储管理
5.5.1 分段存储管理基本思想
用户程序划分 • 按程序自身的逻辑关系划分为若干个程序 段，每个程序段都有一个段名，且有一个 段号。段号从0开始，每一段段内也从0开 始编址，段内地址是连续的。 • 逻辑地址
• 目标：把未来不再使用的或短期内较少使 用的页面调出，通常只能在局部性原理指 导下依据过去的统计数据进行预测；
5.4.4 页面置换分类
• 先进先出页面置换算法（FIFO） • 轮转算法（clock） • 最近最久未使用页面置换算法(LRU, Least Recently Used) • 最不经常使用(LFU, Least Frequently Used)