计算机操作系统（第二版）课件：存储器管理

OperatingSystem

存储器管理第四章存储器管理为什么磁盘中存储的程序和数据必须加载进入内存才能执行？磁盘和内存都是存储器，它们有什么不一样？购买物理内存的时候应该关注哪些指标数据？内存里同时存储了那么多进程的代码和数据，相互之间不会影响吗？系统配置的内存会不会不够用？如果不够用系统会怎样？如果一个程序比系统总体内存还大，能运行吗？程序员在写代码时需要关心程序在内存中是如何存放的吗？目录1.存储器管理概述2.连续存储管理3.页式存储管理方式4.段式存储管理方式5.段页式存储管理6.虚拟存储系统7.Linux内存管理机制重点难点4.1存储器的管理概述存储器的层次体系结构存储器管理功能程序的装入和链接对于本节内容，你最需要老师讲解的内容是哪些？4.1存储器管理概述1、计算机系统中有哪些存储信息的部件？2、这些部件在性能上有什么特征？（访问速度、价格、容量等）3、在多级存储体系中，有效访存时间如何计算？4.1.1存储器的层次体系结构StorageHierarchySystemhttp://tsing.us/book/notes-computer-systems-programmers-perspective/chapter-1-tour-computer-systems4.1存储器管理概述思考题：在存储器体系结构中，CPU可直接访问的有哪些？4.1.1存储器的层次体系结构第一节存储器的管理概述4.1.1存储器的层次体系结构假设某系统中Cache访问周期TC为10纳秒，内存访问周期TM为100纳秒。数据存放在内存中，Cache中有部分缓存的数据，当访问Cache不命中的时候才访问内存读取数据。若访问Cache的命中率A为90%，则访问数据的有效时间TA是（）纳秒。102010090ABCD提交单选题10分4.1存储器管理概述有效访问时间＝命中率×访Cache时间＋

（1-命中率）×Cache不命中时花费的时间

即TA

＝A·TC＋(1-A)·(TC＋TM)近似公式：TA

＝A·TC＋(1-A)·TM4.1.1存储器的层次体系结构4.1.1存储器的层次体系结构4.1存储器管理概述性能提升约20倍程序局部性对执行效率的影响4.1.2存储器管理功能地址映射内存分配与回收内存共享与保护内存扩充基于虚拟存储器技术在逻辑上扩充主存空间-响应请求分配所需的主存空间-保护进程之间相互不受影响存储器-逻辑地址到物理地址的映射，又称地址重定位4.1存储器管理概述4.1存储器管理概述1、内存分配与回收静态分配、动态分配

、

连续分配、离散分配2、地址映射物理地址与主存空间逻辑地址与进程地址空间

地址映射概念

地址映射机构：连续分配时3、内存共享与保护界地址保护：上下界寄存器保护、基址限长寄存器保护4.内存扩充：可行性、实现思路4.1.2存储器管理功能1.内存分配与回收（1）相关数据结构（2）分配与回收算法4.1.2存储器管理功能2.地址映射（1）相关地址的概念：物理地址（绝对地址、实地址）计算机内存单元的真实地址，又称为绝对地址或实地址。主存空间物理地址的集合所对应的空间组成了主存空间。逻辑地址（相对地址、虚地址）用户程序地址（指令地址或操作数地址）均为逻辑地址。程序地址空间用户程序所有的逻辑地址集合对应的空间。4.1.2存储器管理功能32位Linux进程虚拟地址空间64位Linux进程虚拟地址空间4.1.2存储器管理功能movr1,[500]100100500599程序地址空间01000110015001599256k-1存储空间将程序地址空间中使用的逻辑地址变换成主存中的物理地址的过程，称为地址映射，又叫地址重定位movr1,[500]10Load（2）地址映射概念2.地址映射4.1.2存储器管理功能1500（1）静态重定位：边装入边进行地址修改作业地址空间10movr1,[500]0500599100+从第1000单元开始重定位装入程序movr1,[1500]01000150010256k-115991100存贮空间2.地址映射4.1.2存储器管理功能+1000重定位寄存器movr1,[500]01000150010256k-115991100内存空间10movr1,[500]0500599100程序地址空间500逻辑地址重定位寄存器的值可以动态不断变化1500物理地址硬件完成（2）动态重定位：边执行边修改2.地址映射4.1.2存储器管理功能链接得到的可执行程序所对应的地址空间是（）。绝对地址空间虚拟地址空间存储空间物理地址空间ABCD提交单选题10分为了保证一个程序在主存中改变了存放位置后仍能正确执行，则地址映射机制应采用（）技术。静态重定位动态重定位动态分配静态分配ABCD提交单选题10分3.内存共享与保护什么是内存共享什么是内存保护在多用户环境中，主存储器按区分配给各用户程序使用。为了互不影响，必须由硬件（软件配合）保证各用户程序只能在给定的存储区域内活动，这种措施叫做存储保护。实现方法界地址保护：连续分配方式

上下界寄存器保护、基址限长寄存器保护内存P1P2共享内存4.1.2存储器管理功能①上下界寄存器保护：

下界寄存器：存放开始地址（首址）上界寄存器：存放末地址问题：如何判断是否越界？判别式：下界寄存器≤物理地址≤上界寄存器3.内存共享与保护：界地址保护4.1.2存储器管理功能②基址限长寄存器保护基址寄存器：存放开始地址（首址）限长寄存器：存放程序长度（字节数）问题：如何判断是否越界？判别式：逻辑地址<限长寄存器120k基址寄存器10k限长寄存器程序120k130k-103.内存共享与保护：界地址保护4.1.2存储器管理功能某系统采用基址、限长寄存器方法进行存储保护，在这种方法中下列判断是否越界的判别式中正确的是（）：被访问的物理地址<基址寄存器的内容被访问的物理地址≤基址寄存器的内容被访问的逻辑地址<限长寄存器的内容被访问的逻辑地址≤限长寄存器的内容ABCD提交单选题10分4.内存扩充必要性——主存容量不满足应用需求可行性——局部性特征时间局部性空间局部性实现方法程序的全部代码和数据存放在辅存中；程序当前执行所涉及的那部分程序代码放入主存中；程序执行时，当所需信息不在主存，由操作系统和硬件配合来从辅存中调入信息，程序继续执行。循环结构顺序执行intsumvec(intv[N]){ inti=0；sum=0; for(inti=0;i<N;i++) { sum+=v[i];} returnsum;}数组具有空间局部性，无时间局部性指令sum+=v[i];具有时间局部性4.1.2存储器管理功能4.1.1-4.1.2存储器体系结构及管理功能存储器体系结构构成多级存储体系结构中有效访存时间计算存储器管理的功能及含义逻辑地址（虚拟地址、相对地址）、物理地址（实地址、绝对地址）的概念内存连续分配方式中的保护机制两种地址映射方式的实现方法及性能特点本节知识小结哪个小组来总结下？4.1.3程序的装入和链接4.1存储器的管理概述库汇编编译主子1子2目标模块链接程序装入模块库主子1子2装入程序内存库主子1子21.程序的链接对相对地址的修改变换外部调用符号

4.1.3程序的装入和链接4.1存储器的管理概述CallB;0L-10500M-1模块A模块BB:……moveax,(500)ret;链接时机静态链接装入时动态链接运行时动态链接

（1）静态链接CallB;0L-10500M-10N-1静态链接装入模块模块A模块B模块CB:……moveax,(500)ret;0LL+500L+ML+M+N-1CallL;B:……

moveax,(L+500)ret;缺点：不便于软件版本的修改和更新；不便于实现目标模块的共享；装入之前由链接程序将所有的目标模块和程序需要的库函数模块链接形成一个整体，以后不再拆开。修改外部调用符号修改相对地址（1）静态链接缺点：不便于实现目标模块的共享：Prog1：main1.cutilities.cerrhdl1.cProg2：main2.cutilities.cerrhdl2.c编译Prog1：main1.outilities.oerrhdl1.oProg2：main2.outilities.oerrhdl2.o编译静态链接内存（2）装入时动态链接

装入时动态链接aa+La+L+500a+L+Ma+L+M+N-1CallB;B:……

ret;边装入边链接优点：便于修改和更新；便于磁盘共享。缺点：装入内容是静态的。CallB;模块A模块B模块CB:……ret;0L-10500M-10N-1L;或者a+L;4.1.3程序的装入和链接（2）装入时动态链接Prog1：main1.cutilities.cerrhdl1.cProg2：main2.cutilities.cerrhdl2.c编译Prog1：main1.outilities.oerrhdl1.oProg2：main2.outilities.oerrhdl2.o编译装入时动态链接内存Prog1：main1.outilities.oerrhdl1.oProg2：main2.outilities.oerrhdl2.o磁盘上共享内存里不共享内存（3）运行时动态链接

运行时动态链接aa+La+L+N-1边运行边链接；优点：最小化快速装入，节省内存。CallB;模块A模块B模块CB:……ret;0L-10500M-10N-1CallB;该指令本次没被执行4.1.3程序的装入和链接深入程序编译链接和装载过程_ZY-JIMMY-CSDN博客链接过程中需要完成的工作有（）修改指令中的相对地址修改指令中的绝对地址完成地址映射修改外部调用符号ABCD提交多选题10分2.程序的装入概念：就是把链接好的装入模块装入“内存”。装入方式：地址映射时机（1）绝对装入：单道（任务），装入位置是固定的。

程序员直接编址或由汇编、编译程序完成地址重定位。10movr1,[1500]1000150015991100作业地址空间movr1,[1500]01000150010256k-116001100存贮空间4.1.3程序的装入和链接（2）静态重定位装入：多道程序环境边装入边进行地址修改作业地址空间10movr1,[500]0500599100+从第1000单元开始重定位装入程序movr1,[1500]01000150010256k-115991100存贮空间2.程序的装入4.1.3程序的装入和链接（3）动态重定位装入边运行边进行地址修改+1000重定位寄存器movr1,[500]01000150010256k-116001100存贮空间10movr1,[500]0500599100作业地址空间500逻辑地址1500物理地址硬件支持4.1.3程序的装入和链接4.1.3程序的装入和链接程序三种链接方式的基本概念及性能特点程序三种装入方式的基本概念及性能特点本节知识小结算法基本概念？空闲分区链如何建立？如何分配？性能特点？4.2.1分区分配1、固定分区分配：概念、数据结构、分配与回收、地址映射、性能分析2、动态分区分配的概念及数据结构设计3、分配算法

首次适应算法

最佳适应算法

最坏适应算法4、动态分区的回收方法：若采用首次适应算法，每种情况如何修改数据结构？5、地址映射机制和存储保护机制6、碎片问题及拼接技术4.2连续存储管理方式如何改善碎片问题？最大的性能缺点是什么？产生内部碎片4.2.1固定分区分配1.概念：将内存空间划分为若干个固定大小的区域，每个分区中只装入一道作业。2.分区的划分：分区大小相等；分区大小不等4.2连续存储管理方式第4分区第3分区第2分区第1分区区号分区大小起始地址状态OS进程C（20K）

进程A（6K）

内部碎片4.2.1固定分区分配3.数据结构：分区使用表0：已分配1：未分配1 8K 20K 未使用2 32K 28K 未使用3 64K 60K 未使用4 132K 124K 未使用进程B（25K）20K28K60K124K256K-10K已使用已使用已使用进程A申请6K空间进程B申请25K空间进程C申请20K空间进程B释放25K空间4.内存分配与回收4.2.1固定分区分配5.地址转换

静态重定位优点：易于实现，开销小。缺点：内碎片造成浪费分区总数固定，限制了并发执行的程序数目。6.固定分区分配的特点空闲分区链20KB0

52KB66KB130KB230KB256KB1主存os程序1程序3程序452KBm-rib

空闲区队列230KB014KB026KB

4.2.2动态分区分配1.分区分配数据结构每个链表节点中需要记录哪些信息？（1）分区分配思路①

寻找空闲块依申请者所要求的主存区的大小，分区分配程序在空闲分区链表中按一定算法寻找一个满足用户需要的空闲分区；②

若找到了所需的空闲区，有两种情况ⅰ空闲区与要求的大小相等，将该空闲区分配并从队列中摘除；ⅱ空闲区大于所要求的的大小，将空闲区分为两部分：一部分成为已分配区，建立已分配区的描述器；剩下部分仍为空闲区。返回所分配区域的首址；③否则，告之不能满足要求。2.分区分配4.2.2动态分区分配程序1申请

32KB0

256KB1主存20KBos20KB0

52KB256KB1主存os程序1程序2申请

14KB20KB0

52KB66KB256KB1主存os程序1程序2程序3申请

64KB20KB0

52KB66KB130KB256KB1主存os程序1程序2程序3程序4申请

100KB20KB0

52KB66KB130KB230KB256KB1主存os程序1程序2程序3程序4程序5申请

50KB（2）动态分区的分配过程2.分区分配4.2.2动态分区分配①首次适应算法：是将程序装入到主存中足够装入且地址最低的空闲区中。

空闲分区链按分区起始地址递增的顺序链接。2.分区分配（1）分区分配算法考虑到分配效率，应如何建立空闲分区链？算法概念？4.2.2动态分区分配20K256K-1100K160K210K0OS

在使用

在使用

在使用首次适应算法举例：有一作业序列：作业A要求18K，作业B要求25K，作业C要求30K。5K46K30K20K链首20K30k100K20k160K5k210K46k∧始址大小B12K21KA特点：内存低端会留下小的空闲区（外部碎片），高端有大的空闲区。作业A、B、C会分别从哪个空闲分区中分配？作业C分配失败！②最佳适应算法是将程序装入到主存中与其大小最接近的空闲区中。

空闲分区按大小递增的次序排列。2.分区分配（1）分区分配算法考虑到分配效率，应如何建立空闲分区链？算法概念？4.2.2动态分区分配20K256K-1100K160K210K0OS

在使用

在使用

在使用最佳适应算法举例：有一作业序列：作业A要求18K，作业B要求25K，作业C要求30K。5K46K30K20KBAC特点：尽量利用存储器中小的空闲区，而尽量保存大的空闲区。会留下大量小碎片作业A、B、C会分别从哪个空闲分区中分配？③最坏适应算法：是将程序装入到主存中与其大小差距最大的空闲区中。空闲分区按大小递减的次序排列2.分区分配（1）分区分配算法考虑到分配效率，应如何建立空闲分区链？4.2.2动态分区分配256K-120K100K160K210K05K46KOS30K20K

在使用

在使用

在使用210k210K46k20k20K30k100k100K20k160k160K5k∧

最坏适应算法举例：有一作业序列：作业A要求18K，作业B要求25K，作业C要求30K。

特点：尽量利用存储器中的大空闲区，使剩余空闲区较大。不容易留下大分区。作业A、B、C会分别从哪个空闲分区中分配？（1）分区回收思路①

检查释放分区(即为回收分区)在主存中的邻接情况若上、下邻接空闲区，则合并，成为一个连续的空闲区②若回收分区不与任何空闲区相邻接

建立一个新的空闲区，并加入到空闲区队列中。③修改相关数据结构3.分区回收4.2.2动态分区分配（2）分区回收算法：①回收区与插入点的前一个空闲分区相邻接，两者合并；回收作业F1

R作业F2F1作业作业F23.分区回收需要修改哪些数据结构？4.2.2动态分区分配②回收区与插入点的后一个空闲分区相邻接，两者合并；作业RF2作业回收作业F2作业F1F1需要修改哪些数据结构？（2）分区回收算法：3.分区回收4.2.2动态分区分配③回收区与插入点的前后两个空闲分区相邻接，三者合并；回收作业F1作业作业F1RF2作业需要修改哪些数据结构？（2）分区回收算法：3.分区回收4.2.2动态分区分配④回收区不与任何一个空闲分区相邻接，插入一个新节点；F1作业F3作业F2F1作业R作业F2回收需要修改哪些数据结构？（2）分区回收算法：3.分区回收4.2.2动态分区分配20分区的回收过程举例：程序2

完成程序4完成20KB0

52KB66KB130KB230KB256KB1主存程序1程序2程序3程序4os20KB0

52KB66KB130KB230KB256KB1主存程序1程序3程序4os20KB0

52KB66KB130KB230KB256KB1主存os程序1程序33.分区回收4.2.2动态分区分配碎片问题在已分配区之间存在着的一些太小而难以利用的空闲区，称为碎片。碎片影响主存的利用率。拼接技术是指移动主存中已分配区，使分散的小空闲区连成一个大的空闲区。20KB

54KB58KB135KB254KB256KB1主存138KB程序20os程序3程序1拼接前20KB0

54KB131KB247KB256KB1主存os程序1程序2程序3拼接后分区分配中的存储区拼接4.碎片问题及拼接技术4.2.2动态分区分配外部碎片是指（）存储分配完后所剩的空闲区没有被使用的存储区不能被使用的存储区未被使用，而又不容易满足用户大小要求的存储区ABCD提交单选题10分当内存外部碎片总容量大于某一作业所申请的内存容量时，（）可以为该作业直接分配内存不可以为该作业分配内存拼接后，可以为该作业分配内存一定能为该作业分配内存ABCD提交单选题10分若某系统采用伙伴系统管理内存，假设某进程申请300B内存空间，则它实际分配到的空间大小是（）。300B512B1024B不确定ABCD提交单选题10分三.伙伴系统（Buddy)4.2连续存储管理方式所有分区的大小均为2k(l

≤k≤m):2l表示最小分区的大小；

2m表示最大分区的大小（通常是整个可分配内存的大小）。

系统中共有m个空闲分区链，空闲分区按其大小2k位于对应的空闲分区链中。分配时，搜索最接近要求的、大小为2i的空闲分区链，如果有空闲分区，则将其中的一个分配出去；否则，搜索大小为2i+1的空闲分区链，如果有，则将一个分区分成一对伙伴，其中的一个分配出去，另一个插到大小为2i的空闲分区链中；……回收时，如果回收区的伙伴不在空闲分区链中，则只需将它插入相应大小的空闲分区链中；否则，需要将该分区及其伙伴合并成一个大分区；……1.概念2.分配举例：设内存可分配的空间为128KB，现有进程A申请20KB的空间。128K-10K64K32KAfree[]01…0K64K32K17128K64K32K2l16K分区大小161514三.伙伴系统（Buddy)4.2连续存储管理方式实际要给A分配多大的空间？空闲块起始地址3.回收举例：依次释放分区B，C，D:free[]01…16K96Km-l128K64K32K2l16K分区大小128K0K64K32KBC16K48K96K32K32K96KE伙伴伙伴伙伴D0K特点：空间利用率有所降低；时间上性能更佳。二.伙伴系统（Buddy)4.2连续存储管理方式这两个空闲分区是伙伴吗？如何快速发现回收块的伙伴块是否空闲以便确定是否合并？4.2连续存储管理方式外部碎片与内部碎片的概念的概念固定分区分配方式的实现方法、性能优缺点可变分区分配方式的基本概念可变分区方式的3种分配算法及性能特点可变分区方式的分区回收方法拼接的概念伙伴系统的基本概念、分配与回收方法、性能特点本节知识小结哪个小组来总结下？分页存储管理方式基本概念页面和物理块的概念分页系统的逻辑地址结构的理解页表的概念地址转换机构二级页表及地址转换4.3页式存储管理方式关于分页存储管理方式，你希望老师重点讲解的内容有哪些？在分页存储管理方式中，如果没有引入快表，则CPU每次从内存中取一次数据需要访问内存的次数为（）次。1234ABCD提交单选题10分在分页存储管理方式中，如果采用单级页表，则进程的页表会（）。连续存放在进程用户区离散存放在进程用户区连续存放在系统内核区离散存放在系统内核区ABCD提交单选题10分分页管理方式中，页表的作用是（）保存进程的代码保存进程的数据实现地址转换实现内存保护ABCD提交单选题10分一个系统页面大小为1KB，某进程共有4个页面，依次存放在内存的3,10,8,15号块中，则逻辑地址2000的物理地址是（）。2000819211216地址越界ABCD提交单选题10分某分页系统将页表存储在内存中，同时配置了快表。若一次访存周期为100ns，一次快表访问时间为10ns，若快表命中率为80%，则读取一次数据的内存有效访问时间是多少？（忽略快表更新时间）110ns200ns130ns128nsABCD提交单选题10分第三节

页式存储管理方式80x86的控制寄存器：页面的概念：将进程逻辑空间划分为若干等长的区域，称为页（或页面）对每个页面顺序编号，称为页号页面大小：2nB通常为512B～8KB04K-14K8K-18K12K-112K16K-116K20K-120K23K-1页号012345进程地址空间4.3页式存储管理方式4.3.1基本原理4.3页式存储管理方式4.3.1基本原理页面的概念：将进程逻辑空间划分为若干等长的区域，称为页（或页面）对每个页面顺序编号，称为页号页面大小：2nB通常为512B～8KBIntelPentium:4KB,4MBARMv864位：4KB,16KB,64KBMIPSR4000:4KB,16KB,64KB,256KB,1MB,4MB,16MBIntel：CR4寄存器中的第5位:

PSE位=0:4KBMIPSR4000:PageMask寄存器二.逻辑地址结构页号4512K-116K-120K-1进程地址空间

04K-14K8K-18K12K16K20K24K-10410024K27K6页内位移d页号P4100#单元123一维线性地址4K8K-10141#页面4100…4095对于一个线性逻辑地址，如何得到它的页号和页内地址？4.3页式存储管理方式页内位移4页面14.3.1基本原理页号P和页内地址d的计算公式P＝INT[A/L]d＝[A]%LA：逻辑地址空间中的地址L：页面大小4.3页式存储管理方式二.逻辑地址结构4.3.1基本原理某系统的页面大小为1KB，则逻辑地址2180对应的页号和页内地址分别是（）。页号1，页内地址180页号1，页内地址132页号2，页内地址180页号2，页内地址132ABCD提交单选题10分二.逻辑地址结构：页面大小是2的幂：=2nB当页面大小为4KB时：=212B位移量（页内地址）d页号P例如，页面大小为4KB时，逻辑地址4100可表示为：113112110……12页号P位移量（页内地址）d3100000,0000,0000,0000,00010000,0000,0100将内存空间划分为与页面等长的若干区，称为物理块或页框。块大小与页面大小一致

内存空间04K-14K8K-18K12K-112K16K-116K20K-120K24K-1块号012345100008K12K-11000001180840952#块4.3页式存储管理方式可以用什么数据结构来记录内存块的使用情况？物理地址结构：一维线性地址块内位移块号4.3.1基本原理三.物理块的概念四.页表01234567891110内存第0页第1页第2页第3页第4页第5页第6页用户进程块号页号1051169453327120页表第0页第1页第2页第3页第4页第5页第6页页表：存放在内存系统区的一个连续空间中；PCB：存有进程页表在内存的首地址和页表长度；页内碎片页表内容存哪里？页表始址存哪里？4.3页式存储管理方式地址变换机构的任务：实现地址映射页表：存放在内存系统区的一片连续空间中PCB：存有进程页表在内存的首地址和页表长度；页表寄存器PTR：存放当前进程页表在内存的首地址和页表长度

逻辑地址：物理地址：页内位移d页号P块内位移块号查找页表两者相等如何实现？页内位移与块内位移有什么关系？4.3页式存储管理方式五.地址变换机构(1)基本地址变换机构页表始址7页表寄存器＜页表块号页号53327120物理地址寄存器逻辑地址4100越界中断页表长度14页号页内地址块号31121100000,0000,0000,0000,01110000,0000,0100=页表始址指针+页号块内地址

74哪位同学来说说这个逻辑地址如何转变成物理地址？CPU每执行一次访存指令，实际要访问几次内存？已知某分页系统，主存容量为64kB，页面大小为1kB，对一个4页大的作业，第0、1、2、3页被分配到内存的2、4、6、7块中。则十进制逻辑地址1023对应的物理地址是（）102340233071地址越界ABCD提交单选题10分已知某分页系统，主存容量为64kB，页面大小为1kB，对一个4页大的作业，第0、1、2、3页被分配到内存的2、4、6、7块中。则十进制逻辑地址4500对应的物理地址是（）76727500无法计算地址越界ABCD提交单选题10分在一个分页存储管理系统中，逻辑地址的结构长度为为18位，其中11～17位表示页号，0～10表示页内偏移量。若有一个作业共3个页面，各页依次装入2、3、7号物理块中，逻辑地址1500对应的物理地址是多少？150055963548地址越界ABCD提交单选题10分设某进程有8页的逻辑空间，每页有1024字节，它们被映射到32块的物理存储区中，那么该进程逻辑地址的有效位是（）位。10131518ABCD提交单选题10分五.地址变换机构：2.具有快表的地址变换机构快表（联想存储器，按内容查找）：具有并行查询能力4.3页式存储管理方式快表输入寄存器检索项关键字值快表命中关键字匹配值页号块号Linux快表表项：页号块号有效位修改位保护位

几K到几百K，只含有部分页表项（16~512个）如：intelx86:32项具有快表的地址映射过程页表始址页表长度页表寄存器＜页表块号页号5332712031250物理地址21250逻辑地址越界中断快表块号页号205327120输入寄存器快表命中仅在快表不命中时进行快表命中时，访问一个地址的时间包括哪几个部分？哪个小组来分析这个逻辑地址转换成物理地址的过程？具有快表的地址映射过程页表始址页表长度页表寄存器＜页表块号页号5332712051250物理地址31250逻辑地址越界中断快表块号页号205327120输入寄存器快表未命中仅在快表不命中时进行快表块号页号205327153哪个小组来分析这个逻辑地址转换成物理地址的过程？快表未命中时，访问一个地址的时间包括哪几个部分？某分页系统将页表存储在内存中，同时配置了快表。若一次访存周期为100ns，一次快表访问时间为10ns，若快表命中率为90%，则读取一次数据的内存有效访问时间是（）ns。（忽略快表更新时间）100120119110ABCD提交单选题10分课堂练习：如果一个程序占用200M大小空间，若页面大小为4KB，每个页表项4B，它的页表需要多大的空间存储？页表也存储在内存中，那么如果页表比一个页面还要大会怎么样？有哪些办法解决这个问题？50K个页面，页表大小200KB2.大页表问题的解决思路：对页表本身采用离散分配方式存储；只将当前需要的部分页表调入内存，其余的页表仍驻留在磁盘上，需要时再调入。大家自己算一下，用弹幕给出第一题答案？本次课前学习中不理解的问题、希望老师重点讲解的内容有哪些？用弹幕给出1、说明分页系统的基本概念：页面，页表，逻辑地址结构2、分析说明分页系统地址转换过程。前期知识回顾4.3页式存储管理方式016002k进程地址空间…页号012345399940000进程页表4000外部页号01234.3.2两级和多级页表页号块号010111……10231033页表分页…页号块号3072308230733083……40004010032M…块号01234581920页页表1页页表2页页表3页页表外部页号块号01122435外部页表又称为页目录表进程页表：页号块号010111……102310331024103410251035……204720572048205820492059……307130813072309230733093……400040100#页表分页：1024个页表项1#页表分页：1024个页表项2#页表分页：1024个页表项3#页表分页：929个页表项假设每个页表项4B逻辑地址结构：页号页内地址3112110外部页号外部页内地址页内地址31222112110CPU给出：32位线性地址进程地址空间分页：4KB进程页表分页：4.3.2两级和多级页表页目录号页表索引进程页表10331023……111100块号页号页表分页…40104000……3093307330923072块号页号0号页表分页3号页表分页01928页号块号010111……102310331024103410251035……204720572048205820492059……307130813072309230733093……40004010地址变换过程：外部页表外部页表寄存器物理地址…………页表分页块号块内地址外部块号页号块号页号外部页表始址、长度外部页号外部页内地址页内地址31222112110小组讨论下两级页表下地址转换过程？？4.3.2两级和多级页表外部页号块号01122435外部页表10物理地址外部页号P1外部页内地址P2页内地址d块号块内地址3#页表分页外部页表寄存器外部页表始址、长度00000000110000000001000000001010页号块号307215307316……4000800164.3.2两级和多级页表ARMv8MMU及Linux页表映射：TLB4.3.2两级和多级页表已知系统为32位实地址，采用48位虚拟地址，页面大小4KB，页表项大小为8B。假设系统使用纯页式存储，若最高级页表能保存在一个块内，则要采用（）。单级页表二级页表三级页表四级页表ABCD提交单选题10分1.为满足264地址空间的运行，采用多级页表管理方式，假设页面大小为8KB，页表中的每个页表项需要占8B，且最高级页表只能占用一个块存储，则该分页系统至少应采用几级页表？2.在1题的条件下，如果系统没有引入快表，一次内存访存周期为100ns，则读取一次数据的内存有效访问时间是多少？3.在1题的条件下，系统配置了快表，一次内存访存周期为100ns，一次快表访问时间为10ns，若快表命中率为90%，则读取一次数据的内存有效访问时间是多少？小组讨论（8分钟）小组讨论分析：1、页面大小：8KB=213B，所以一个块中可以存放210个页表项，即逻辑地址结构中每个中间层页号（外部页内地址）需要占用10个二进制位，所以需要的页表级数为：

（64-13）/10=6（向上取整）2、700ns3、90%*（10+100）+10%*（10+700）=170ns多级页表系统中快表的重要性！4.3页式存储管理方式分页存储管理的基本思想页面的概念及大小、逻辑地址结构页表概念及作用分页系统地址转换过程快表的作用及有效访存时间的计算二级/多级页表的概念及地址转换过程本节知识小结4.4段式存储管理方式分段存储管理的基本原理：

段、逻辑地址结构、段表、

地址转换机构分段共享与分段保护分段与分页的区别本节学习内容采用段式存储管理时，一个程序如何分段是在（）时决定的。分配主存时用户编程时装入作业时程序执行时ABCD提交单选题10分段表的作用是（）描述进程有几个分段用于地址映射方便进程执行提高内存利用率ABCD提交单选题10分分段系统中逻辑地址是（）一维线性地址二维地址结构三维地址结构都不对ABCD提交单选题10分段页式系统中，如果没有快表，CPU每取一个数据或指令，实际需要访问（）次内存1234ABCD提交单选题10分4.4段式存储管理方式Main（0）分段存储管理的基本概念分段系统的逻辑地址结构段表的概念分段系统的地址转换机构分段共享与分段保护分段与分页的区别对分段与分页的性能做比较分析？4.4段式存储管理方式Main（0）1.什么是段分段是程序中自然划分的一组逻辑意义完整的信息集合。

每个段有段名和段号分段：代码分段、数据分段、栈段。一.分段系统的基本原理stack（3）Main（0）f1（1）data（2）4.4段式存储管理方式Main（0）2.程序地址空间由若干个逻辑分段组成，每个分段是一个连续的地址区stack(3)Main(0)F1(1)data(2)3k08k07k0015k一.分段系统的基本原理3.地址结构：stack(3)Main(0)F1(1)data(2)3k08k07k0015k1000段号段内地址0151631二维地址结构100010001000如果要访问0号段的1000号单元，能否像分页系统中只给出1项地址信息：1000？一.分段系统的基本原理（1）每个段在段表中占一个表项（2）段号、段基址、段长、段状态等（3）段表连续存放在OS内核所在区域（4）段表始址及段表长度保存在进程PCB中第0段第1段第2段第3段第0段第1段第2段第3段20k35k50k65k段表段号段长段基址015k+120k17k+165k28k+135k33k+150k段表在内存的始址保存到哪里最合适？说说你对分段系统中段表的理解？你认为分段系统中物理内存用什么数据结构进行管理？一.分段系统的基本原理4.段表分段系统中要进行几次越界检查？分别是什么？4.4段式存储管理方式二.段式地址变换机构段表寄存器存放段表的起始地址和段表长度；越界检查逻辑地址的段号与段表长度比较；段内地址与段表中保存的段长比较；段表始址段表长度段表寄存器＜段号3段内地址105逻辑地址越界中断段表基址段长50K3k+135K8k+165K7k+120K15k+13210段号＜51305物理地址内存二.段式地址变换机构哪个小组来说说这个逻辑地址如何转变成物理地址？假如一个作业的段表如下所示，其中存取控制字段中W表示可写，R表示可读，E表示可执行。分别说明下面指令执行时，地址转换的情况。（1）STORER1,[0,70]；（2）STORER1[1,20]（3）LOADR1,[3,100]；（4）JMP[2,100]段号 内存始址 段长存取控制 0 500 100RW 1 1000 30 R 2 3000 200 E 3 8000 80 R 4 5000 40 R三个判断：1.段号是否越界？2.段长是否越界？3.存取权限是否相符？（1）STORER1,[0,70]：

=500+70=570；段号 内存始址 段长存取控制 0 500 100RW 1 1000 30 R 2 3000 200 E 3 8000 80 R 4 5000 40 R结果是什么？（2）STORER1,[1,20]：

段号 内存始址 段长存取控制 0 500 100RW 1 1000 30 R 2 3000 200 E 3 8000 80 R 4 5000 40 R结果是什么？存取控制不符合，硬件将产生保护性中断信号。（3）LOADR1,[3,100]：

段内地址超过了段长，将产生越界中断信号。段号 内存始址 段长存取控制 0 500 100RW 1 1000 30 R 2 3000 200 E 3 8000 80 R 4 5000 40 R结果是什么？（4）JMP[2,100]：

=3000+100=3100段号 内存始址 段长存取控制 0 500 100RW 1 1000 30 R 2 3000 200 E 3 8000 80 R 4 5000 40 R结果是什么？

三.分段共享与保护4.4段式存储管理方式codedatastack如何设置该页面保护属性？可读？可写？只执行？某程序地址空间大而稀疏内存codedatastack空闲空闲

三.分段共享与保护共享段表：每个共享段占一个表项4.4段式存储管理方式公用信息：段名、段长、内存始址、存在位、共享计数私用信息：每个共享该段的进程一项

进程PID，段号、存取控制字段等

分段保护

四.分段与分页的区别（1）页是信息的物理单位，段是信息的逻辑单位；（2）页的大小固定，段的大小动态变化；（3）分页系统中的逻辑地址空间是一维的，分段系统中的是二维的（4）分页对用户不可见，分段对用户可见（5）分段比分页更方便信息的共享和保护（6）分段比分页更适合动态链接的实现4.4段式存储管理方式哪个小组来总结下分段与分页两种管理方式的区别？某分段系统中，作业的段表如下表所示，则逻辑地址[1,1500]对应的物理地址是（）。250060002500地址越界ABCD提交单选题10分4.4段式存储管理方式分段存储管理的基本思想分段系统二维逻辑地址结构段表概念及作用分段系统地址转换过程分段共享与保护的实现方法分页与分段的区别本节知识小结

4.5段页式存储管理方式段页式存储管理的基本思想段页式系统的逻辑地址结构段页式系统的页表、段表如何建立？段页式系统地址转换机构1.作业分段：按逻辑信息进行，每个段有段名和段号2.段内分页：3k08k07k0015kstack(3)Main(0)F1(1)data(2)0012103210第五节段页式存储管理方式3210Main（0段）015K100008K12K-11000001180840950段2#页3.逻辑地址结构：二维地址结构段号页内地址0151631段内页号1211段号段内地址0151631段内分页第五节段页式存储管理方式12进程地址空间页号01233k08k07k0stack(3)Main(0)f1(1)data(2)015k0100内存空间8192块号032M…0123450段0页0段1页2段1页1段1页6789100段2页0段3页1段0页2段0页2段2页3段0页1112130段页表822110块号页号6351401段页表112101302段页表13段页表130进程段表13322140页表始址页表长度段号第五节段页式存储管理方式：4.段表及页表：最多会产生几个内部碎片？第五节段页式存储管理方式：

5.地址转换机构：段表始址段表长度段表寄存器逻辑地址页号P页内地址段号S≤段表块号块内地址物理地址越界中断页表210块号页号段号页表长度页表始址0123CPU访问一次内存，实际要访问几次内存？哪位同学说说地址转换过程？

第五节.段页式存储管理方式例题：在一个段页式系统中，某作业的段表、页表格式如下图所示，计算虚拟地址[1,7000]的物理地址。大家算一下结果是多少？？4.5段页式存储管理方式段页式存储管理的基本思想段页式系统逻辑地址结构段页式系统中段表及页表的设置段页式系统地址转换过程本节知识小结一.虚拟存储器的基本概念4.6虚拟存储系统局部性特征？什么是虚拟存储器？具有请求调入功能和置换功能，能够利用外存空间从逻辑上扩充内存容量的一种存储器系统。特征多次性置换性虚拟性与前面学习过的传统存储管理方式比较，虚拟存储器有哪些不同的特征呢？说说你对局部性特征的理解？第0页第1页第2页第0页第1页第2页第3页第4页第5页第6页二.请求分页存储管理方式4.6虚拟存储系统只装入部分页面1.扩充页表功能：页号物理块号状态位P访问字段A修改位M外存地址状态位P：用于指示该页是否已调入内存访问字段A：记录本页在一段时间内被访问的情况修改位M：该页在调入内存后是否被修改过外存地址：指示该页在外存上的地址0：不在内存1：在内存0：未被修改1：已被修改4.6虚拟存储系统二.请求分页存储管理方式哪个小组来分析下这些字段的含义？什么时候会检查这些字段的值？案例：Win2000中的页表项二.请求分页存储管理方式2.缺页中断处理:所要访问的页不在内存时，便引发一次缺页中断

启动要处理的指令给出虚地址

得到页号该页在主存?有空闲块?

缺页中断执行完该指令

准备执行下条指令选一页淘汰

从外存读入所需的页

调整存储分配表和页表

重新启动被中断的指令

调整存储分配表和页表要重写入?该页写入外存YNNY硬件实现软件实现YN二.请求分页存储管理方式普通中断的处理过程是怎样的？普通中断与缺页中断有什么不同呢?执行指令的过程中发生和处理的需要修改页表项哪些信息？分析缺页中断处理过程？本次课前学习中不理解的问题、希望老师重点讲解的内容有哪些？用弹幕给出1、说明虚拟存储器的基本概念，分析与常规存储管理方式相比较的特点2、分析说明虚拟存储系统中，页表的字段设置及用途3、分析说明缺页中断处理过程前期知识回顾4.3页式存储管理方式思考题：某请求分页系统中，若其指令系统指令长16位，每个操作数的地址码长6位，操作码4位，每个操作数16位，则执行一条双操作数指令，则最多可能发生几次缺页中断？二.请求分页存储管理方式（1）固定分配局部置换（2）可变分配全局置换（3）可变分配局部置换3.内存分配与页面置换策略4.地址映射过程缺页中断处理需要修改页表哪些信息？其实这里要先访问快表哪个小组来分析地址映射过程？若某进程访问内存时产生缺页，则下列选项中，操作系统可能执行的操作有（）置换页面装入缺页处理越界错误分配内存ABCD提交多选题10分5.页面置换算法选择淘汰页面的策略缺页中断率假定程序p共有n页，系统分配m块，有1≤m≤n；

若程序p在运行中：成功的访问次数为s，不成功的访问次数为f；缺页中断率：f′=f/(s+f)f′=f(r，m，p)；

r：置换算法；m：系统分配的块数；p：程序特征二.请求分页存储管理方式5.页面置换算法（1）先进先出页面置换算法FIFO（2）最佳置换算法OPT（3）最近最久未使用置换算法LRU（4）最近最少使用置换算法LFU（5）时钟置换算法CLOCK（讲授）（6）改进的CLOCK算法（7）页缓冲思想二.请求分页存储管理方式基本概念、实现思路、性能优缺点总是先淘汰那些最先进入系统，即驻留主存时间最长的页。例1：在一个请求分页系统中，假定系统分给一个作业的物理块数为3，刚开始没有一个页面装入内存，并且此作业的页面走向为2，3，2，1，5，2，4，5，3，2，5，2。用FIFO计算缺页次数和缺页率。缺页次数：9，缺页率：(9/12)*100%=75%特点：实现简单与进程实际的运行不相适应5.页面置换算法二.请求分页存储管理方式基本概念？如何实现？（1）先进先出页面置换算法（FIFO）性能优缺点？例2：在一个请求分页系统中，假如一个作业的页面走向为1，2，3，4，1，2，5，1，2，3，4，5,当分给该作业的物理块数M分别为3和4时，请用FIFO计算缺页次数和缺页率，并比较所得的结果。5.页面置换算法（1）先进先出页面置换算法（FIFO）物理块数为3：缺页次数为9物理块数为4：缺页次数为10这种异常现象称为Belady现象。结果分别是多少？5.页面置换算法（2）最佳置换算法（OPT）选择以后永远不会被访问的页面或将来最长时间内不会被访问的页面淘汰出去。基本概念？如何实现？在一个请求分页系统中，假定系统分给一个作业的物理块数为3，刚开始没有一个页面装入内存，并且此作业的页面走向为2，3，2，1，5，2，4，5，3，2，5，2。使用OPT置换算法，则缺页次数是（）。5678ABCD提交单选题10分缺页中断32532532+532534534+534532+532+13232+32+21252354251232页面走向OPT算法：缺页次数：6，缺页率：6/12特点：理论上，性能最佳；实际上，无法实现；通常用该算法来评价其他算法的优劣。（3）最近最久未使用置换算法（LRU）选择在最近一段时间内最长时间未被使用（访问）的页面淘汰出去。5.页面置换算法缺页中断32253253+253+453452+452152+152+13232+32+21252354251232页面走向缺页次数：7缺页率：7/12特点：性能较好，但精确实现较困难（3）最近最久未使用置换算法（LRU）5.页面置换算法LRU算法的实现用引用位考察页面的使用情况；当访问页面时，将引用位置1，并记时；当要淘汰一页时，选择时间最长的一页淘汰。硬件方法：采用移位寄存器软件方法：采用页号栈极偶尔的情况下，性能会很差假设一个进程顺序访问N+1个页面后再循环地访问这些页面，若进程分配到的内存块数为N块。如：顺序访问1,2,3,4,5,6,7，再循环访问它们，进程分配到的内存块为6个块，缺页情况如何？如果让你来设计，你会怎么实现以便快速找到淘汰页面？使用页号栈实现LRU算法（3）最近最久未使用置换算法（LRU）5.页面置换算法缺页中断252354251232页面走向23223123512251425542354235523253+++++++缺页次数：7，缺页率：7/12你能使用链表来实现这个特殊的栈结构吗？本次课前学习中不理解的问题、希望老师重点讲解的内容有哪些？用弹幕给出1、分析说明最佳页面置换算法的基本概念、性能特点？2、分析说明LRU页面置换算法的基本概念、性能特点？如何实现LRU算法？前期知识回顾4.6虚拟存储系统选择过去一段时间里访问次数最少的页面进行淘汰。

思考：如何实现该算法？（5）最近最少使用置换算法（LFU）5.页面置换算法

①简单的clock置换算法：每页设置一位访问位。当某页被访问了，则访问位置“1”。内存中的所有页链接成一个循环队列；再设置一个起始查询指针置换算法：循环检查各页面的使用情况:若访问位为“0”，选择该页淘汰；若访问位为“1”，复位访问位为“0”；查询指针前进一步。又称为“最近未使用”置换算法（NRU）（4）Clock置换算法（引导讲授）5.页面置换算法CLOCK算法流程描述：

入口检查查询指针指向的页面移动指针指向下一个页面

访问位为0?选择该页淘汰，记录该页的页号、块号移动查询指针指向下一个页面返回置访问位为0YN很关键简单的clock置换算法：1210访问位页号块号1311101216131514115150121603041730202181040000000案例：Linux的双表针clock置换算法12101311101216131514115150121603040731202181040000例：在一个请求分页系统中，假定系统分给一个作业的物理块数为3，刚开始没有一个页面装入内存，并且此作业的页面走向为2，3，2，1，5，2，4，5，3，2，5，2。采用Clock置换算法，则缺页次数是（）。6789ABCD提交单选题10分②改进型Clock置换算法：考虑置换代价访问位A、修改位M，共同表示一个页面的状态页面的四种状态：

00：(A=0;M=0)最近未被访问也未被修改

01：(A=0;M=1)最近未被访问但已被修改

10：(A=1;M=0)最近已被访问但未被修改

11：(A=1;M=1)最近已被访问且被修改（4）Clock置换算法5.页面置换算法当用A、M两位来表示页面状态时，内存中的页面可以分为几种状态的页面？②改进型Clock置换算法：三轮扫描：第一轮：查找A=0,M=0页面，未找到，下一步；第二轮：查找A=0,M=1页面，A位复位为“0”，未找到，下一步；第三轮：把所有A置为“0”，重复第一轮，必要时再重复第二轮。（4）Clock置换算法5.页面置换算法哪个小组来说说如何查找淘汰页面？5.页面置换算法可变分配局部置换策略，FIFO页面置换算法给淘汰页面再一次驻留内存的机会空闲页面链表：已修改页面链表：空闲内存块空白内存块或未修改淘汰页所在内存块已修改淘汰页所在内存块淘汰页未被修改已被修改（6）页面缓冲置换算法本次课前学习中不理解的问题、希望老师重点讲解的内容有哪些？用弹幕给出1、分析说明最佳页面置换算法的基本概念、性能特点？2、分析说明LRU页面置换算法的基本概念、性能特点？如何实现LRU算法？3、分析说明clock页面置换算法查找淘汰页面的过程？4、分析说明页面缓冲置换算法的基本思想？前期知识回顾4.6虚拟存储系统案例：Windows2000空闲块链表（1）零初始化链表；（2）空闲链表；（3）后备链表：未修改淘汰页；（4）修改链表：已修改淘汰页修改页面写回器零页线程

在某请求分页管理系统中，一个作业共5页，作业执行时依次访问如下页面：1，4，3，1，2，5，1，4，2，1，4，5，若分配给该作业的主存块数为4，刚开始没有一个页面在内存，若分别采用LRU和Clock页面置换算法，则缺页中断次数分别是（）。6，76，87，77，8ABCD提交单选题10分（1）缺页率对有效访问时间的影响：设缺页率为P，则有效访问时间为：=(1-P)*内存访问时间+P*缺页中断处理时间缺页中断处理时间保存和恢复现场信息所需时间读入缺页所需时间（可能置换）更新页表和快表所需时间重新执行访存指令时间。6.请求分页存储管理的性能分析二.请求分页存储管理方式如果不缺页，那么访问一次内存包含哪些时间？如果缺页，访问时间又包含哪些？例：（2009年统考真题）某请求分