Download presentation
Presentation is loading. Please wait.
Published by曲 咸 Modified 7年之前
1
§2 虚拟存储器 1961年英国曼彻斯特大学Kilbrn等人提出 70年代广泛地应用于大中型计算机系统中 目前许多微型机也开始使用虚拟存储器
§2 虚拟存储器 1961年英国曼彻斯特大学Kilbrn等人提出 70年代广泛地应用于大中型计算机系统中 目前许多微型机也开始使用虚拟存储器 是进一步完善主存-辅存存储层次,解决主存容量提出的。
2
虚拟存储器的特点 多个进程可以共享主存空间 程序员不必做存储管理工作 采用动态再定位,简化了程序的装入
3
目录 不同的虚拟存储管理方式 页式虚拟存储器构成 页式虚拟存储器实现中的问题
4
虚拟地址空间 实际地址空间 压缩 映射
5
不同的虚拟存储管理方式 通过增设地址映像表机构来实现程序在主存中的定位。这种定位技术是将程序分割成若干较小的段或页,用相应的映像表机构来指明程序的某段或某页是否已装入内存。 段式管理 页式管理 段页式管理
6
段式管理 段为程序的逻辑单位 段表,本身也是段,常驻内存,也可以在辅存,需要时调入主存。 能使大程序分模块编制,并行编程,缩短时间
段表结构: 段名、地址、装入位、段长、访问方式。 段表基址寄存器:指明段表的启始地址。 能使大程序分模块编制,并行编程,缩短时间 便于几道程序共用已在内存内的程序和数据; 各段是按其逻辑特点组合的,容易以段为单位实现存储保护。人工建立。
7
+ 3k A 4 1.5k 0段 1段 2段 3段 4段 5段 6段 1k 2k 4k a 7 1 6 5 3 2 5k 段名 地址 装入位
1 + 6 5 3 2 5k 段名 地址 装入位 段长 访问方式 已装入 段表长度 段表基地址 段表基址寄存器 实主存空间 A道程序的 程序空间 A道程序的段表 2.5k
8
段号 段长 起址 主程序 (0段) 1k 8k 8k 1k 1 500 16k 9k 1段 2 200 9k 500 3 200 30k 16k 2段 200 30k 3段 程序 空间 200 主存储器
9
地址映象方法:每个程序段都从0地址开始编址,长度可长可短,可以在程序执行过程中动态改变程序段的长度。
地址变换方法: 由用户号找到基址寄存器 从基址寄存器中读出段表的起始地址 把起始地址与多用户虚地址中段号相加得到段表地址 把段表中给出的起始地址与段内偏移D相加就能得到主存实地址
10
多用户 虚地址 用户号U 段号S 段内偏移D 主存实地址 As 1 6 As 2 1 3 n-1 4 段表 长度 段表 基址 段名 起始 地址 装入 位 段长 访问 方式 段表基址寄存器 一个用户(一道作业)的段表
11
段式管理优缺点 优点 缺点 程序的模块化性能好 便于程序和数据的共享 程序的动态链接和调度比较容易 便于实现信息保护
地址变换所花费的时间比较长,做两次加法运算 主存储器的利用率往往比较低 对辅存(磁盘存储器)的管理比较困难
12
段分配算法 首先分配:顺序扫描可用区域表,当找到第一个不小于调 入段长度的可用区时,立即分配。
最佳分配:先扫描全部可用区域表,然后寻找一个可用区进行分配,使之分配后段间可用区零头最小。
13
举例 主存 程序 (a)需依次调入 D、E、F段 (b)首先分配法 D、E、F段全被调入 (c)最佳分配法 F段无法调入 C B A D E
0.5k 3k 7k 8k 10k C B A D E F 1k 2.5k 2k 主存 程序 4k 6.5k 5.5k 9k (a)需依次调入 D、E、F段 (b)首先分配法 D、E、F段全被调入 (c)最佳分配法 F段无法调入
14
页式管理 页式虚拟存储器把虚拟地址空间划分成一个个固定大小的块,每块称为一页,把主存储器的地址空间也按虚拟地址空间同样的大小划分为页。页是一种逻辑上的划分,它可以由系统软件任意指定。 虚拟地址空间中的页称为虚页,主存地址空间中的页称为实页。 每个用户使用一个基址寄存器(在CPU内),通过用户号U可以直接找到与这个用户程序相对应的基址寄存器,从这个基址寄存器中读出页表起始地址。访问这个页表地址,把得到的主存页号p与虚地址中的页内偏移直接拼接起来得到主存实地址。
15
页式管理 把主存空间和程序空间机械地等分成固定大小的页,按顺序编号; 页表。如下图。 特点: 页表项简单,查找速度快;
页面大小固定不利于系统的效率, 有些系统可调整其大小。例:MC 应用程序 4kb 系统程序512kb 页式管理在存储空间较大时,由于页表过大,效率降低。 存储空间的保护困难。
16
D b Nv Nr nr nv 7 6 D道程序页表 2 7 1 6 D道程序页表 A B C 4k-1 32k-1 程序标志号 A B C
1 2 4k D道程序 程序空间 虚存页号 A B C 4k-1 32k-1 D 程序标志号 b Nv Nr nr nv 7 6 D道程序页表 虚存 页号 主存 起点 装如 位 访问 方式 专用 基号 虚页号 页内偏移 实页号 1 2 4k D道程序 程序空间 虚存页号 A B C 4k-1 32k-1 2 7 1 6 D道程序页表 虚存 页号 主存 起点 装如 位 访问 方式 专用
17
X Nv Nr x nv nr 由u转换成基号b 1 多用户 虚地址 用户标志u 用户虚页号 页内位移 多用户虚页号 某道程序的地址
页表基址寄存器 nv nr 实页号 装入位 1 已装入 主存 主存地址寄存器
18
举例 虚地址空间32位,页面大小为1kb(10位) 页表地址段将达22位, 32-10=22
页表的长度为4兆行(222 =4096k=4M) 如主存容量为8MB 则页表字段为13位,每行为2+1字节 则页表容量为 4MB*3=12MB>主存容量
19
页号 主存页号 0页 1 1页 2 2页 3 页表 3页 用户程序 主存储器 页式虚拟存储器的地址映象
20
用户号U 虚页号P 页内偏移D 实页号p 页内偏移d Pa Pa 2 p 装入 修改 主存页号 标志 页表基址 页表
21
页式管理的优缺点 优点 缺点 主存储器的利用率比较高 页表相对比较简单 地址变换的速度比较快 对磁盘的管理比较容易 程序的模块化性能不好
页表很长,需要占用很大的存储空间。
22
段页式管理 页式:对应用程序员完全透明,由系统划分.
硬件较少,地址变换速度快, 调入操作简单,静态连接程序; 段式:段独立,有利于程序员灵活实现段的连接、段的扩大/缩小和修改,而不影响其他段,易于针对其特定类型实现保护,把共享的程序或数据单独构成一个段,从而易于实现多个用户、进程对共用段的管理,动态连接程序; 特点:访存两次。 段页式:把实存机械地等分成固定大小的页,程序按模块分段,每个段又分成与主存页面大小相同的页。
24
地址变换方法: 先查段表,得到该程序段的页表起始地址和页表长度 再查页表找到要访问的主存实页号
最后把实页号p与页内偏移d拼接得到主存的实地址。
25
用户号U 段号S 虚页号P 页内偏移 实页号p 页内偏移 As A As 1 0/1 Ap 1 p 0/1 装入 修改 页表 地址 装入 实页号 修改 标志
26
页式虚拟存储器构成
27
u Nv’ Nr nr nv 虚存总空间 多用户虚地址Ns 2Nr 直接 实存地址np 2Nv页包括2u个 实存空间 用户,每个用户
28
地址映象和变换 地址映象:是将每个虚存单元按某种规则(算法)装入(定位于)实存,即建立多用户虚地址Ns与实存地址np之间的对应关系。
页面争用(实页冲突):发生两个以上的虚页想要进入主存中同一个页面位置的现象。
29
地址变换的原则 减少实页冲突 硬件少、成本低 实现方便、变换速度快。 由于虚存空间远远大于实存空间,因此页式虚拟存储器常采用全相联映像。
30
全相联映像 任何虚页可以映象装入到任何实页位置。冲突概率最低。 虚存 主存 每道程序任何 虚页可映像到 任何实页位置 页0 页1 页2
页面位置0 页面位置1
31
全相联映像的页表法 页表法 nv 装入位 2u+Nv行
32
全相联映像的相联目录表法 相联目录表法 u+Nv nv 2nv行 相联比较
33
页表法与相联目录表法的比较 页表法 相联目录表法 访问方式 地址 内容 存储容量 存取速度 慢 快 入口个数 入口宽度
34
替换算法 页面替换发生时间: 当发生页面失效时,要从磁盘中调入一页到主存。如果主存所有页面都已经被占用,必须从主存储器中淘汰掉一个不常使用的页面,以便腾出主存空间来存放新调入的页面。 替换算法的确定 主存的命中率 是否便于实现,软、硬件成本
35
页面替换算法的使用场合 虚拟存储器中,主存页面的替换,一般用软件实现 Cache块替换一般用硬件实现
虚拟存储器的快慢表中,快表存储字的替换,用硬件实现 虚拟存储器中,用户基地址寄存器的替换,用硬件实现 在有些虚拟存储器中目录表的替换
36
替换算法(续) 随机算法(Random ,RAND):用软的或硬的随机数产生器来形成主存重要被替换页的页号。
简单,易于实现 没有利用历史信息 命中率低,很少使用 先进先出算法(First-In First-Out ,FIFO):选择最早装入主存的页作为被替换的页。 配置计数器字段 虽然利用历史信息,但不一定反映出程序的局部性
37
替换算法(续) 近期最少使用算法(Least Recently Used ,LRU):选择近期最少访问的页作为被替换的页。
配有计数器字段。 比较正确反映程序的局部性。 优化替换算法(Optimal Replacement Algorithm, OPT):是在时刻t找出主存中每个页将要用到时刻ti,然后选择其中ti-t最大的那一页作为替换页。 理想化算法
38
举例1 设有一道程序,有1至5共5页,执行时的地址流为: 2,3,2,1,5,2,4,5,3,2,5,2
分别采用FIFO、LRU、OPT算法。
40
说明 命中率与地址流有关 命中率与分配给程序的主存页数有关。 例如:一个循环程序,FIFO、LRU的命中率明显低于OPT。(下一张)
颠簸现象:连续不断出现页面失效。 命中率与分配给程序的主存页数有关。 主存页数增加,LRU命中率提高,至少不会下降,而FIFO不一定。(P115,图4.17)
41
举例 一个循环程序,依次使用P1,P2,P3,P4四个页面,分配给这个程序的主存页面数为3个。FIFO、LRU和OPT三种页面替换算法对主存页面的调度情况如下图所示。在FIFO和LRU算法中,总是发生下次就要使用的页面本次被替换出去的情况,这就是“颠簸”现象。
43
举例2 一个程序共有5个页面组成,程序执行过程中的页地址流如下:
P1, P2, P1, P5, P5, P1, P3, P4, P3, P4 假设分配给这个程序的主存储器共有3个页面。给出FIFO、LRU、OPT 三种页面替换算法对这3页主存的使用情况,包括调入、替换和命中等。
45
堆栈型替换算法的定义 对任意一个程序的页地址流作两次主存页面数分配,分别分配m个主存页面和n个主存页面,并且有m≤n。如果在任何时刻t,主存页面数集合Bt都满足关系:Bt(m)Í Bt(n),则这类算法称为堆栈型替换算法。
46
堆栈型算法的基本特点 随着分配给程序的主存页面数增加,主存的命中率也提高,至少不下降。 提出使系统性能可以更优的动态算法。
LRU、OPT都是堆栈型算法 FIFO是非堆栈型算法 提出使系统性能可以更优的动态算法。 由操作系统来动态调节分配给每道程序的实页数。
47
虚拟存储器工作的全过程 书中 P
49
页式虚拟存储器实现中的问题 页面失效的处理 页面失效会在一条指令的分析或执行过程中发出。 页面失效时一种故障,不是一般的中断;
注意保护现场,采用后援寄存器技术、预判技术; 选择合适的替换算法;
50
页式虚拟存储器实现中的问题 提高虚拟存储器等效访问速度的措施 要求:提高命中率,加快访存时间;
命中率受很多因素影响,如:地址流、页面调度策略、替换算法、页面大小、主存容量等。 访存时间,解决Ns-np的转换。 快表:相联目录表,慢表:页表 快表-慢表存储层次的替换算法一般采用LRU法。
51
实页号 用户号U 页内偏移D p 虚页号P 多用户 虚地址 快表(按内容相联访问) 页内偏移d 实页号p 多用户虚页号 U, P 主存实地址 装入 1 慢表
52
散列函数 目的:把相联访问变成按地址访问,从而加大快表容量 散列(Hashing)函数:Ah=H(Pv), 20位左右 5~8位
采用散列变换实现快表按地址访问 避免散列冲突:采用相等比较器 地址变换过程:相等比较与访问存储器同时进行
53
实页号 用户号U 页内偏移D p 虚页号P 多用户 虚地址 按地址访问的快表 页内偏移d 实页号p 多用户虚页号 Pv 主存实地址 散列变 换(硬 件实现) 相等比较 查慢表 快表地址 Ah 快表 命中
54
虚拟存储器举例 I BM370/168计算机的虚拟存储器快表结构及地址变换过程。虚拟地址长36位,页面大小为4KB,每个用户最多占用4K个页面,最多允许16个用户,但同时上机的用户数一般不超过6个。 采用了两项新的措施: 采用两个相等比较器 用相联寄存器组把24位用户号U压缩成3位
56
页式虚拟存储器实现中的问题 影响主存命中率CPU效率的某些因素 程序地址流、替换算法、实页数、页面调度策略 页面大小通常为1KB到4KB。
H S1:某道程序的主存容量 Sp:页面大小 S1一定时: Sp由小增大,H逐渐增大 增达到最大值,下降。 增大S1可增大Sp。 2S1 S1 页面大小Sp
57
主存容量与命中率的关系 1.0 命中率 H 主存容量S 主存命中率H随着分配给该程序的主存容量S的增加而单调上升。
在S比较小的时候,H提高得非常快。随着S的逐渐增,H提高的速度逐渐降低。当S增加到某一个值之后,H几乎不再提高。 命中率 H 主存容量S 1.0
58
页面调度方式与命中率的关系 请求式: 预取式: 当使用到的时候,再调入主存
在程序重新开始运行之前,把上次停止运行前一段时间内用到的页面先调入到主存储器,然后才开始运行程序。 可以避免在程序开始运行时,频繁发生页面失效的情况。 如果调入的页面用不上,浪费了调入的时间,占用了主存资源。
Similar presentations