当前位置：文档之家 › 页式存储管理.ppt

页式存储管理.ppt

  • 格式：ppt
  • 大小：1.27 MB
  • 文档页数：55

下载文档原格式

  / 55

合集下载

南邮操作系统教程CH-04-存储管理PPT课件

南邮操作系统教程CH-04-存储管理PPT课件
ch414p1p2p3p40k0k1515kk38k38k4848kk68k68k80k80k110110kk120k120k空闲区表已分配区表长度标志15k23k未分配48k20k未分配80k30k未分配长度标志0k15kp138k10kp268k12kp3110k10kp4某一时刻的分配状态15k53k未分配ch415可变分区分配算法分配第一个足够大的分区可以从头开始查找也可以从上次分配结束的地点开始查找总是产生最小剩余分区丌浪费一个更大的空间但会寻致剩余分区太小难被再利用总是产生最大剩余分区它可能比最优适应产生的剩余分区更容易利用ch416可变分区的地址转换和存储保护基址基址寄存器逡辑地址cpu绝对地址操作系统区空闲分区1用户迚程1空闲分区2ch417紧凑技术经过一段时间的分配回收后内存中存在很多很小的空闲块
物理地址 = Base(0x4000) + 0x240 = 0x4240
从0x4240获取指令 “la $a0, varx”
Move 0x4050 $a0, Move PC+4 PC
下一条指令的逻辑地址=0x244，转换成物理地址=0x4244，得到 “jal strlen” Move 0x0248 $ra (return address!), Move 0x0360 PC
ch4.10
固定分区存储管理
存储分配：系统维护一张主存分配表，里面记载了 内存的分区划分和使用状态。分配主存时总选择那 些分区占用标志为0且长度小于等于进程所需空间的 分区块。回收只要相应分区占用位置0即可。
分区号 1 2 3 4 5 6
起始地址 8K 16K 32K 48K 64K 96K
长度 8K 16K 16K 16K 32K 32K
两个问题
内存中的进程如何交互？ 内核模式和用户模式如何切换？

页式存储管理.ppt

页式存储管理.ppt

4.5 段式存储管理
一个用户程序往往由几个程序段（主程序、子 程序和函数）所组成，当一个程序装入内存时，按 段进行分配，每个段的大小是不相等的。
程序地址的组成：S：W
例: S1：XXXX S2：XXXX S3；XXXX
1、分段与分页的区别： • 段是信息逻辑单位，页是物理单位（长度）。 • 段长不固定，页等长；页号连续，段号间无顺序关系。 • 段式作业地址空间是二维的，页式地址空间是一维的。
被修改时，其修改位M置1。
页号 0 1 2 3 4 5
内存块号 …… …… …… …… …… ……
访问位 0 1 1 0 0 1
修改位 1 0 1 0 1 0
在最近的一个时钟 周期（如20ms）内， 访问过页1、2、5。 自装入内存后，修 改过页0、2、4。
有四类页面： ① R=0，M=0 （最佳淘汰页） ② R=0，M=1 ③ R=1，M=0 ④ R=1，M=1（最不该淘汰）
2、段式管理的内存分配与释放： 每段要求一个连续的内存区，所以其分配和回收算法类 似于分区管理，如 FF，BF，WF，相邻区合并。
造成这样问题的主要原因是用户程序装入内 存时是连续装入的，为解决这个问题，提出了分 页存储管理技术。
二、分页的概念
程序地址空间分成大小相等的页面，同时把内存也分成与 页面大小相等的块，当一个用户程序装入内存时，以页面为单 位进行分配。页面的大小是为2n ,通常为1KB，2KB，nKB等。
页式存储管理要解决如下问题： 1、地址映射； 2、调入策略； 3、淘汰策略； 4、放置策略。
页将要运行，在其运行之前先行调入内存，这样在 程序运行的过程中就不会出现缺页中断。这样方法 从表面上看起来很好，但系统无法预计系统中作业 的运行情况，难以实现。 2、请调

请求页式存贮管理

请求页式存贮管理
操作系统
请求页式存贮管理
1 虚拟存储器
前面的存贮管理的特点是作业运行时， 整个作业的地址空间必须全部装入主存。而 当作业的地址空间大于主存可用空间时，该 作业就无法运行。这种存贮管理技术叫实存 管理技术。
与实存管理技术相对应的是虚拟存贮技 术。现在许多功能较强的计算机，无论是微 型、小型、中大型机，均采用了虚拟存贮技 术。
请求页式存贮管理
4 缺页中断
如果内存中有空闲块，则分配一页， 将新调入页装入内存，并修改页表中相应 页表项目的驻留位及相应的内存块号。
若此时内存中没有空闲块，则要淘汰 某页，若该页在内存期间被修改过，则要 将其写回外存。
4 缺页中断
缺页次数F
由图可知，
10000
当主存容量增加
9000
时，缺页中断次
请求页式存贮管理
2 页式虚拟存储管理实现原理
为了有效选择被淘汰的页，通常页表中再 增加两个标志位：访问位和修改位。
访问位指示该页最近是否被访问过。“1” 表示访问，“0”表示没有被访问。
修改位指示该页调入主存后是否被修改过。 “1”表示修改过，0表示未修改过。
选择一页淘汰时，要选择访问位为0、修 改位也为0的页。若这样的页没有找到，则选 择访问位为0修改位为1的页淘汰。当淘汰这 样一页时，要将被淘汰的页写回到辅存上去， 以保证信息的一致性。
页2 3 3 3 4 4 4 4 4 2 2 2
页3
2223333311
xxxxxxxvvxxv
共缺页中断9次 命中率=3/12*100%=25%
先进先出页面淘汰算法（FIFO）
FIFO算法虽然易于实现，但出现抖动外，还 会有一种异常现象。Belady在1969年发现，采用 FIFO算法时，为作业分配的主存块越多，反而缺 页中断次数越多。这种奇怪的现象就叫做Belady 异常。下面举例说明这一异常。某作业有5个页 面，执行时引用的页序列为：

chn2页式存储管理

chn2页式存储管理

4.3.5（3）多级页表地址转换过程
目录dir位移 页表页位移page 页内位移offset
逻辑地址
1
页目录表 控制寄存器
4 6 3
页表 地址 页框 地址
2
5
页框号
offset
物理地址
进程一级页表 进程二级页表
逻辑地址结构有三部分组成：页目录位移、页 表页位移和页内位移。
4.3.6反置页表Inverted Page Table（IPT）(1)
例题：逻辑地址是5499，页框大小是1024问题该地址在 第几页，偏移量是多少？页号=5499/1024=5,偏移
=5499%1024=379
4.3.1 分页式存储管理基本原理
三、（2）地址转换算法
第一：运行时CPU读逻辑地址； 第二：在页表寄存器内读取页表首地址； 第三：计算确定页号；
第四：找对应的页框号；
练习：一个进程，逻辑空间为3 页长，每个页面长度为1k（1024 字节），页表如右图所示。进程 中指令 Load 1，2500（从有效
页表 页号 块号 0 1 2 2 3 8
地址2500取数据放入1号寄存器
中）的逻辑地址为100，如何找
到该指令的内存物理地址及数据
存放地址？
解：1、由虚地址为100可知，指令 Load 1，
练习：
页号与页框对应模式
4 5 6
4.3.4分页存储空间的页面共享和保护
分页代码共享概念
4.3.4分页存储空间的页面共享和保护
共享本质：被共享的部分在内存只有一个副本，即共享代码
或数据指向内存同一物理地址段。 分页技术的数据共享（用于通信）：页号指向各自页框。 分页技术的代码共享（节省内存）：因为程序运行必须链接 好，链接后代码页号必须固定所以共享页号逻辑号必须联系 且须编号相同，才能保障代码完整执行。 共享保护技术：页表中增加权标识位。

4.3请求页式存储管理

4.3请求页式存储管理
每个页面设一计数器，每访问一次计数器加一，缺页时选择计数最 小的页面先淘汰，每隔某个时间内对计数器清零。缺点是代价较高。
5、最近没有使用页面先淘汰（NUR）
利用在页表中设置一个访问位即可实现，当某页被访问时，访问位置 “1”，否则访问位置“0”当需要淘汰一页时，从那些访问位为“0” 的页中选一页进行淘汰。系统周期性地对所有访问位清零。
4.3请求页式存储管理

3.3页式存储管理的优点
1、优点：
a、虛存量大，适合多道程序运行，用户不必担心内存不够的调度操作 b、内存利用率高，不常用的页面尽量不留在内存 c、不要求作业连续存放，有效地解决了“碎片”问题。与分区式比， 不需移动作业；与多重分区比，无零星碎片产生。 2、缺点：
a、要处理页面中断、缺页中断处理等，系统开销较大 b、有可能产生“抖动” c、地址变換机构复杂，为提高速度采用硬件实现，增加了机器成本
2、循环检测法
让循环多的页面留在内在。适合循环多的大程序，时空开销大， 系统要判断每个页面的驻留时间。
4.3请求页式存储管理

3.2请求淘汰换页算法3、最近最少使用Fra bibliotekLRU）页面先淘汰
截取一段最近的绝对时间，选择离当前时间最近一段时间内最久没 有使用过的页面先淘汰。
4、最不经常使用（LFU）的页面先淘汰
4.3请求页式存储管理

3.2请求淘汰换页算法
6、最优淘汰算法（OPT）
它是一种理想的淘汰算法，系统预测作业今后要访问的页面，淘汰页 是将来不被访问的页面或者最长时间后才能被访问的页面。淘汰该页 不会造成刚淘汰出去又立即要把它调入的现象。
7、随机数淘汰页面算法
在系统设计人员无法确定那些页的访问概率较低时，随机地选择某个 用户的页面进行淘汰也是一种方法。

页式管理

页式管理
页式管理
• • • • • • • 问题提出 页式管理的思想 分页管理的地址结构 静态页面管理 动态页面管理 存储保护 分页管理的优劣
问题提出
• • • • 分区管理的优劣： 分区管理的优劣： 实现方式简单。 优：实现方式简单。 碎片问题； 劣：①碎片问题； 分区内，作业或进程连续， ②分区内，作业或进程连续，作业或进 程大小受分区大小限制； 程大小受分区大小限制； • ③不利程序段和数据的共享。 不利程序段和数据的共享。
扩充页表
• 扩充页表的内容包括：
动态页面管理的流程
• 缺页调入的过程 • 缺页中断
淘汰算法
• ①随机淘汰算法（random glongram）： glongram）： 随机淘汰算法（ 随机地选择某个用户的页面将其淘汰。 随机地选择某个用户的页面将其淘汰。 • ②轮转法（round robin）:轮流换出内 轮转法（ robin） 存可用区的页面。 存可用区的页面。
3 1 4 3
5 4 3 2 1 5 5 4 3 2 2 2 4 1 1 3 3 5 缺缺 缺
缺页 缺 缺 缺 缺 缺 缺 缺
缺页率：10/12
走向 块1 块2 块3 块4 缺页
4 4
3 4 3
2 4 3 2
1 4 4 3 2 1
3
5 4 3 2 1 4 3 5 1 缺 4 4 3 3 2 1 1 2
1 4 1 1 3 4 2 2
3 1 4 3
5 4 3 2 1 5 5 4 3 5 5 2 2 3 1 缺缺
缺页 缺 缺 缺 缺 缺 缺 缺
缺页率：9/12
走向 4 块1 块2 块3 块4 4
3 4 3
2 4 3 2
1 4 4 3 2 1

课件：页式虚拟存储管理


将该页登记入快表
硬件处理 操作系统处理
• 现代OS的主流存储管理技术
• 首次只把进程第一页信息装入主存， 称为请求页式存储管理
页式虚拟存储管理的页表
• 需要扩充页表项，指出：
– 每页的虚拟地址、实际地址 – 主存驻留标志、写回标志、保护标志、
引用标志、可移动标志
标志位 主存块号 辅助存储器地址 第0页
第n页
页式虚拟存储管理的实现
• CPU处理地址 –若页驻留，则获得块号形成绝对地址 – 若页不在内存，则CPU发出缺页中断
• OS处理缺页中断 –若有空闲页架，则根据辅存地址调入 页，更新页表与快表等 –若无空闲页架，则决定淘汰页，调出 已修改页，调入页，更新页表与快表
页式虚拟存储管理的地址转换
按逻辑地址查快表
否 查页表
该页在快表 中有登记吗？
否 该页在主存？ 是
发缺页中断
形成绝对地址
是 形成绝对地址 继续执行指令
保护现场
计算机操作系统
3 存储管理 – 3.3 页式存储管理 3.3.3 页式虚拟存储管理
掌握页式虚拟存储管理的基本思 想
掌握页式虚拟存储管理的页表 掌握页式虚拟存储管理的地址转
换 掌握缺页中断的处理流程源自页式虚拟存储管理的基本思想
• 把进程全部页面装入虚拟存储器，执 行时先把部分页面装入实际内存，然 后，根据执行行为，动态调入不在主 存的页，同时进行必要的页面调出

《操作系统》课件(五)页式存储管理


段的共享和保护
共享：在不同用户的段表中添入相同的 段表表项。
保护：在段表中添加一个保护位。 思 考：为什么段式存储管理比页式存储
管理更容易实现共享和保护？
段式和页式的问题和优点
页式：解决了碎片问题。但不便于用户作业 的共享和保护。由于用户调入的页可能只用 到其中的一部分，因此系统的效率不高。
210=1024，25=32
（2）根据给定的逻辑地址得到页号和页内地址。
035E（H）=（0000001101011110）2 从左边 数10位为页内地址，剩余为页号。页号为0。
（3）根据页号查页表，得到块号为5。
（4）将块号与块内地址组合为物理地址：
01011101011110=175E（H）
页表的实现—快表
块号
5 12
保护位
R WR
5
5
5
5
5
用户1
用户2
用户3
页式虚拟存储技术
虚拟存储器：内存扩充技术，为用户提供一 个比实际内存大得多的内存空间。
实现虚拟的三个三个条件；
程序中的哪些页已经加载内存。 当要访问的页不在内存时，如何将其掉如内存？ 若此时内存空间已满，如何选择换出的页？
页式虚拟的基本原理：加载作业时，只加载 那些最活跃的页，其余的页需要时再加载。 “请求调页技术”和“预调页技术”。
从上述地址变换过程可以看出：CPU每取一条 指令或数据，都必须经过页表。
因此，页表的每一个表项都是一个动态重定位 机构。
如何实现页表，将影响系统的效率。 方式：
硬件实现：用寄存器组。但代价太高，特别是内存 很大时，是不可能的。
软件实现：将页表放在内存中。每取一条指令，要 两次访问内存。

分页存储管理方式

15
练习题 【例4】：有一页式系统，其页表存放在主存中
①如果对主存的一次存取需要1.5μs,试问实现一次页面访 问的存取时间是多少? ②如果系统加有快表,平均命中率为85%,当页表项在快表 中时,其查找时间忽略为0, 试问此时的存取时间是多少?
答：若页表存放在主存中，则要实现一次页面访问需两次 访问主存：一次是访问页表，确定所存取页面的物理地 址（称为定位）。第二次才根据该地址存取页面数据。
① 将逻辑地址转换成二进制； ② 按页的大小分离出页号P和位移量W（低位部分是位
移量，高位部分是页号）；
③ 将位移量直接复制到内存地址寄存器的低位部分； ④ 以页号查页表，得到对应页装入内存的块号B，将
块号转换成二进制数填入地址寄存器的高位部分， 从而形成内存地址。
14
练习题：
例1：设有8页的逻辑地址空间，每页有1024个字节，它们被 映射到32块的物理存储区，那么逻辑地址的有效位是多少， 物理地址至少多少位？
越界保护
查页表前，将页号与PTR中的页表长度比较，超出
(>=)则越界
10
页表寄存器 页表始址 址 页号（3) 页内地址
＋
页号 0 1 2 3
块号 1
b
页表
物理地址
分页系统地址变换机构
11
具有快表的地址变换机构
对于基本的地址变换机构(无快表)，每存取一个数据， 需要访问两次内存
将页表全部放入。大作业虽然无法全部放入，但由于程序和数据访问的
局部性，也可以取得较好的效果。据统计：命中率>90%
13
分页管理中的地址映射问题
【注意】将逻辑地址线性分割求出页号P和页内位移W： 1、逻辑地址以十进制数给出： 页号P=逻辑地址 / 页大小

操作系统ppt课件完整版


2024/1/30
10
进程同步与通信
2024/1/30
进程同步
多个进程在执行过程中需要协调其推进速度，以保证它们之 间正确的协作关系。进程同步的主要任务是使并发执行的诸 进程之间能有效地共享资源和相互合作，从而使程序的执行 具有可再现性。
进程通信
进程通信是指进程之间的信息交换。在分布式系统中，进程 通信是实现分布式计算和协同工作的基础。常见的进程通信 方式包括管道（pipe）、消息队列（message queue）、信 号（signal）等。
2024/1/30
9
进程调度算法
调度算法的分类
根据调度策略的不同，进程调度算法可分为先来先服务（FCFS）、短作业优先（ SJF）、优先级调度（Priority Scheduling）、时间片轮转（RR）等。
调度算法的选择
在选择调度算法时，需要考虑系统的整体性能、资源利用率、响应时间等因素。 不同的调度算法适用于不同的应用场景和需求。
将程序的逻辑地址空间划分为固定大小的页，而物理内存划分为同样大 小的页框。程序加载时，可将任意一页放入内存中任意一个页框，实现 离散分配。
页表
记录逻辑页与物理页框的对应关系。
2024/1/30
03
优缺点
提高了内存利用率，减少了碎片；但增加了系统开销，可能产生抖动现
象。
15
段式存储管理
基本思想
把程序按内容或过程（函数）关 系分成段，每段有自己的名字。 一个用户作业或进程所包含的段 对应于一个二维线性虚拟空间，
即一个段表。
段表
记录各段在内存中的起始地址和 段的长度。
优缺点
便于实现共享和保护；但容易产 生碎片，浪费内存空间。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
不是将该程序全部装入内存，而是只装入部分页 到内存，就可启动程序运行，在运行的过程中， 如果发现要运行的程序或要访问数据不在内存， 则向系统发出缺页中断请求，系统在处理这个中 断时，将在外存相应的页调入内存，该程序继续 运行。
虚拟存储器
一、程序的局部性原理 在一段小的时间间隔内，被访问过的某指令或数
4.4.3 请调策略
一、问题的提出 在页式存储管理提高了内存的利用效率，但
并不为用户提供虚存，换句话说，当一个用户程 序的页数大于当前总空闲内存块数时，系统就不 能将该程序装入运行。即用户程序将受到物理内 存大小的限制。为了解决这个问题，人们提出请 求分页存储管理技术。
二、请求分页概念 请求分页技术当一个用户程序要调入内存时，
页号 0 1 2 3
块号 5 3 7 6
解答
页表首址
+
页号 块号
0
5
1
3
2
7
3
6
00001 00101011100
10
0
00011 00101011100
物理地址为：0x195C
四、采用相应技术加快页表的查询速度
在页式存储技术中，每访问一次内存，就要 做两次访问内存的工作，即查页表时要作一次访 问内存的工作，然后是访问程序要求访问的内存 ，这样，存取速度降低一倍，将会影响整个系统 的使用效率。
虚地址 3412 P＝3412 ％ 2048 ＝1 W＝ 3412 mod 2048 ＝ 1364 MR=9*2048+1364=19796 虚地址3412的内存地址 是：19796
练习
在分页存储管理系统中，有一作业大小为4页，页 长为2K，页表如下。试借助地址变换图（即要求画 出地址变换图）求出逻辑地址0x095C所对应的物理 地址。
在早期的计算机系统中有的采用联想存储器 的技术来加快查表的速度，有的采用寄存器做页 表。
具有快表的地址变换机构：
快表：将页表中作业运行最常用的部分放入快表。
页表寄存器
越界
程序地址L
页表起址 页表长度
页号p
页内地址w
<
页表
页号 块号 0 1 2 p’ 3 4 5 6
页号 块号
输3
入5
寄2
存 器
1 4
第四章 存储器管理
4.1 概述 4.2 存储管理的功能 4.3 分区存储管理 4.4 页式存储管理 4.5 段式存储管理 4.6 段页式存储管理 4.7 UNIX系统的存储管理
4.4 页式存储管理
4.4.1 页式系统应解决的问题
一、问题的提出 分区存储管理的主要问题是碎片问题。
在采用分区存储管理的系统中，会形成一些非 常小的空闲分区，最终这些非常小的分区不能被 系统中的任何用户（程序）利用而浪费。
据，很快会被再次访问（时间局部性）；作业访问的 地址空间往往集中在某个区域（空间局部性）。 二、虚拟存储器
具有请求调入功能和置换功能，能从逻辑上对内 存容量进行扩充。实际容量由内存和外存之和决定。 速度接近于内存，每位的成本接近于外存。
三、请求分页要解决的问题 1、如何发现执行的程序或访问的数据不在内存； 2、程序或数据什么时候调入内存，调入策略； 3、当一些页调入内存时，内存没有空闲内存时， 将淘汰哪些页，淘汰策略。
2.虚地址以十进制数给出 页号＝虚地址％页大小 位移量＝虚地址 mod 页大小
根据题意产生页表； 以页号查页表，得到对应页装入内存的块号 内存地址＝块号×页大小＋位移量
例1：有一系统采用页式存储管理，有一作业大小是 8KB，页大小为2KB，依次装入内存的第7、9、A、5 块，试将虚地址0AFEH，1ADDH转换成内存地址。
4.4.2 页式地址变换
一、页表 页表是页式存储管理的数据结构，它包括用户程 序空间的页面与内存块的对应关系、页面的存储 保护和存取控制方面的信息。
页号 内存块号 存取控制 状态 其它
用户程序
0页 1页 2页 3页 4页 5页 6页 7页
页表
页号 0 1 2 3 4 5 6 7
块号 5 2 4 6 7 10 9 11
造成这样问题的主要原因是用户程序装入内 存时是连续装入的，为解决这个问题，提出了分 相等的页面，同时把内存也分成与 页面大小相等的块，当一个用户程序装入内存时，以页面为单 位进行分配。页面的大小是为2n ,通常为1KB，2KB，nKB等。
页式存储管理要解决如下问题： 1、地址映射； 2、调入策略； 3、淘汰策略； 4、放置策略。
虚地址0AFEH 0000 1010 1111 1110 P＝1 W＝010 1111 1110 MR＝0100 1010 1111 1110
＝4AFEH
例2：有一系统采用页式存储管理，有一作业大小 是8KB，页大小为2KB，依次装入内存的第7、9、10 、5块，试将虚地址7145，3412转换成内存地址。
P
15 10 9
W
0
三、页式地址映射
程序地址 P W
页表寄存器 页表起址 页表长度
页表 越界
P P’
P’+W
拼接
内存
程序地址L 页号（P=2） 页内地址W
< 页表
页号 块号 05 12 24 36
P’=4 W 物理地址
1. 虚地址（逻辑地址、程序地址）以十六进制、 八进制、二进制的形式给出 将虚地址转换成二进制的数； 按页的大小分离出页号和位移量（低位部分是位移 量，高位部分是页号）； 根据题意产生页表； 将位移量直接复制到内存地址寄存器的低位部分； 以页号查页表，得到对应页装入内存的块号，并将 块号转换成二进制数填入地址寄存器的高位部分， 从而形成内存地址。
p’
快表
p’
w
物理地址
例:设访问内存的时间为200 ns，访问快表（高速缓 冲）的时间为40 ns，如果快表命中率为90%，则将 逻辑地址转换成物理地址进行内存访问的平均时间 为： 40* 90%+200* 10% +200= 256 ns。 不用快表时，需访问两次内存，需要200*2 = 400 ns。
内存
0 1 2 3 4 5 6 7 8 9 10 11 ……
二、虚地址结构 虚地址是用户程序中的逻辑地址，它包括页号
和页内地址（页内位移）。 区分页号和页内地址的依椐是页的大小，页内
地址占虚地址的低位部分，页号占虚地址的高位 部分。
假定页面大小1024字节，虚地址共占用2个字 节(16位)
页号 页内地址（位移量）