操作系统课件

第七章虚拟存储器计算机系统中的另一个虚拟技术——虚存,通过交换技术将外存作为内存的扩充使用，解决内存容量过小的问题。7.1虚存管理的基本概念让程序的一部分装入主存是否可行？一、局部性原理程序执行过程中的一个较短时期，指令地址和操作数地址分别局限于一定区域。

7.1虚存管理的基本概念1.局部性可表现为A）时间局部性B）空间局部性时间局部性空间局部性步长为1步长为K的引用模式，空间局部性随步长增加而下降7.1虚存管理的基本概念intsummatrix(inta[M][N]){inti,j,sum=0;for(j=0;j<N;j++)for(i=0;i<M;i++)sum+=a[i][j];returnsum;}按列优先顺序访问，步长为N，空间局部性差按行优先顺序访问，步长为1，空间局部性好7.1虚存管理的基本概念总之：（1）重复引用同一变量的程序有良好的时间局部性（2）步长越小，空间局部性越好（3）循环有良好的时间和空间局部性，循环体越小，循环迭代次数越多，局部性越好。2.局部性原理的具体体现（1）程序执行的顺序性（2）过程调用嵌套深度不深（3）程序中存在相当多循环结构（4）程序中存在相当多对一定数据结构的操作7.1虚存管理的基本概念二、虚拟存储的基本原理程序运行前，不必全部装入内存。程序运行时，缺页或缺段，由OS调入相应页和段OS将暂时不用的段和页调出到外存上三、虚存的定义

虚存具有请求调入功能和置换功能用户感觉有一个大容量的主存（虚拟性）7.1虚存管理的基本概念四、引入虚存技术的好处1.在小内存中执行较大的程序2.提供大于内存空间的用户空间3.内存可容纳更多程序并发执行4.编程时，时空开销不再成为问题五、虚存技术的特征1.离散性2.对换性3.多次性4.虚拟性六、虚存技术的种类虚拟页式虚拟段式虚拟段页式7.2请求分页一、请求分页原理1.等分主存为“块”2.作业先存于外存文件区3.作业运行前至少装入执行所需的最少页面4.作业运行时，缺页，OS将其调入7.2请求分页二、请求分页中的硬件支持请求分页系统比纯分页系统复杂，需要提供更多硬件支持1.页表机制：需增设几项2.缺页中断机构：与普通中断不同3.地址变换机构:增加产生和处理中断功能、页面置换功能

7.2请求分页三、请求分页中的地址变换过程逻辑地址（未越界）查快表有记录形成物理地址无记录查页表在主存在辅存登记入快表发缺页中断保护现场有空块？无选择调出页面有装入所需页面调整页表并恢复现场硬件地址变换过程OS处理缺页中断过程7.2请求分页四、调度、分配和清除策略1.调页策略（1）何时调入页面:请求调页、预调页（2）何处调入页面：交换区、文件区（3）页面调入过程7.2请求分页2.物理块的分配策略（1）固定分配，局部置换（2）可变分配，全局置换（3）可变分配，局部置换3.清除策略（1）请求清除（2）预清除7.2请求分页五、缺页率和抖动1.缺页率缺页率：缺页中断发生的概率缺页率＝缺页次数/内存访问次数（1）影响缺页率的因素：

a）页面大小b）分配给进程的块数7.2请求分页2.抖动页面在内外存间频繁调度的现象原因：1）分配给进程的物理块数太少2）页面淘汰算法不合理7.3页面置换算法一、最佳置换算法（OPT）每次置换不再访问或最久才会访问的页面

具有理论价值二、先进先出置换算法（FIFO）淘汰最先调入主存的页面

可能出现Belady现象7.3页面置换算法三、最近最久未使用置换算法（LRU）淘汰最近一段时间最久未访问的页四、轮转置换算法（Clock）

最近未使用置换算法（NRU）简单Clock算法改进的Clock算法（1）页面分为4类（2）算法：a.找第一类页面b.找第二类页面,并将访问位置0c.重复查找第一、第二类页面7.3页面置换算法五、最少使用算法（LFU）选择到当前为止被访问次数最少的页面淘汰六、页面缓冲算法（PBA）是FIFO算法的发展，采用预清除策略。（1）按FIFO次序，预选一个被淘汰的本进程页面，将页面放入两个链表之一：空闲页面链表、已修改页面链表。（2）调入页面时，使用空闲页面链表的页。（3）已修改页面链表中的页达到一定数量时，一起调出到外存。7.4请求分段一、请求分段原理1.程序运行前，调入一个或若干个程序段2.运行时，缺段，则请求OS调入段二、地址变换1.段表：增加表项2.缺段中断3.地址变换过程7.4请求分段逻辑地址（未越界）查快表有记录形成物理地址无记录查段表在主存在辅存登记入快表发缺段中断保护现场无选择调出若干段有装入所需段调整段表并恢复现场硬件地址变换过程OS处理缺段中断过程有空闲区？7.4请求分段三、段的保护与共享1.段的保护目的:a)保护系统程序区不被用户侵犯（有意或无意）b)不允许用户读写不属于自己地址空间的数据。

7.4请求分段措施：a）越界检查：段表寄存器段表中段长字段b）存取控制检查：段表中的存取控制字段c）环保护：处理器状态分为多个级别（环）可访问同环或更低级别环的数据

可调用同环或更高级别环的服务7.4请求分段2.段的共享建立共享段表cos共享段表内存段表7.4请求分段四、虚拟段页式存储将虚拟段式与虚拟页式相结合1.原理（1）内存分“块”（2）地址空间分“段”，段内分“页”（3）作业运行前，部分投入页面7.4请求分段2.地址变换（1）页表：需增加若干位（同请求分页）（2）段表：增加若干位（同请求分段？）（3）缺页中断（4）缺段中断（5）地址变换过程7.4请求分段逻辑地址查快表有记录形成物理地址无记录查段表有页表查页表在内存登记入快表无页表发缺段中断在外存发缺页中断继续执行指令7.5UNIX虚拟内存管理UNIX系统中普遍采用请求分页的存储管理技术。一、请求调页管理的数据结构（1）页表（2）磁盘块描述表（3）页框数据表（4）对换使用表7.5UNIX虚拟内存管理1.页表（1）页框号：物理块号（2）年龄：记录页面最近多久未被访问（3）访问位：记录页面是否被访问过（4）修改位：记录页面是否被修改过（5）有效位：指示该页是否有效，访问无效的页面会报错（6）写时拷贝：共享的页面是否已有拷贝（7）保护位：指示页面允许的访问方式7.5UNIX虚拟内存管理2.磁盘块描述表描述页面在外存磁盘中的位置情况（1）存储器类型：file、disk（对换区）（2）对换设备号（3）设备块号7.5UNIX虚拟内存管理3.页框数据表描述内存物理块的信息（1）页状态：指示页面拷贝在对换设备还是文件区（2）引用计数（3）逻辑设备（4）逻辑块号（5）指针1和指针24.对换使用表描述了对换设备上的每一页引用计数：记录引用该页的进程数7.5UNIX虚拟内存管理页框号有效位……103无效……页表66k类型块……disk847……磁盘块描述表页框号块引用数…..……..…页框数据表块引用数……8470对换使用表117768471有效1776例如，系统中某进程的一个区大小为68k，如果进程在存取虚地址66k时产生一个有效错（访问无效页），应如何处理？7.5UNIX虚拟内存管理二、页面淘汰－－偷页页在内存123…n未被引用的页年龄增加可以换出页不在内存换出换入7.5UNIX虚拟内存管理1.换出页面（1）对换设备上没有该页复本（2）对换设备上有该页复本，且页未修改（3）对换设备上有该页复本，且页被修改（1）－－－多页统一换出到对换设备上（2）－－－无需换出，直接将该页清为无效，并链入空闲链表（3）－－－需统一换出到对换设备7.5UNIX虚拟内存管理2.核心向对换设备写一页面（1）清除页表项有效位（2）将页框数据表引用计数减一，若减为0，则将其链入链表，换出或重新分配3.调入所缺页面（1）缺页在文件区：从文件区调入（2）缺页在对换设备上：从对换区调入（3）缺页在内存中：修改表项和链表练习判断：请求分页管理系统，若把页面大小增加一倍，则缺页中断次数会减少一半判断：虚地址即程序执行时所要访问的内存地址在请求分页存储管理系统中，地址变换过程可能会因为（）原因而发生中断虚存的理论基础是（）练习虚存中LRU算法，分配3页，每页存200个整数，其中第一页存放程序，程序已在内存，数组A按先行后列存储，求程序A和B的缺页次数分别为多少？程序A：程序B：Fori:=1to100doForj:=1to100doForj:=1to100doFori:=1to100doA[i,j]:=0A[i,j]:=0练习请求分页管理系统中，某页表如图

：

页面大小为4KB，一次内存的访问时间是100ns，一次快表（TLB）的访问时间是10ns，处理一次缺页的平均时间为108ns（已含更新TLB和页表的时间），进程的驻留集大小固定为2，采用LRU算法和局部淘汰策略。假设:①TLB初始为空；②忽略访问页表之后的TLB更新时间；③有效位为0表示页面不在内存，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2362H、1565H、25A5H，请问：

（1）

依次访问上述三个虚地址，各需多少时间？给出计算过程。

（2）

基于上述访问序列，虚地址1565H的

物理地址是多少？

页号页框号有效位0101H11--02254H1练习设某计算机的逻辑地址空间和物理地址空间均为64KB.按字节编址。若某进程最多需要6页（Page）数据存储空间，页的大小为1KB.操作系统采用固定分配局部置换策略为此进程分配4个页框（PageFame）当该进程执行到时刻260时，要访问逻辑地址为17CAH的数据，请问答下列问题：

1）该逻辑地址对应的页号是多少？

2）采用FIFO置换算法，该逻辑地址对应的物理地址是多少？3）若采用时钟（CLOCK）置换算法，该逻辑地址对应的物理地址是多少？（当前指针指向2号页框）页号页框号装入时刻访问位071301142301222001391601练习关于请求分页系统的页面置换策略如下：从0时刻开始扫描，每隔5个时间单位扫描一轮驻留集（扫描时间忽略不计），且在本轮没有访问过的页框将被回收，并放