【教学课件】第四章存储器管理.ppt

1,2023/8/7,第四章 存储器管理,4.1 内存管理概述4.2 连续分配存储管理方式4.3 基本分页存储管理方式4.4 基本分段存储管理方式4.5 虚拟存储器概念及关键技术4.6 请求分页存储管理方式4.7 请求分段存储管理方式,2,2023/8/7,用户程序处理过程,内存,装入程序,源程序,装入模块,链接程序,库,编译程序,目标模块,符号名空间,目标地址空间,统一的目标地址空间,物理地址空间,数据和指令构成：存取访问问题,布局？,3,2023/8/7,程序处理与内存管理,程序地址空间及形成目标模块（由编译/汇编得到）：相对地址链接过程实现各目标模块相对地址的统一内存管理物理部件MMU负责将逻辑地址转换为物理地址X86体系结构MMU支持分页和分段机制内存管理方式实模式和保护模式,4,2023/8/7,程序的链接,链接过程根据外部访问符号名表，将经过编译或汇编得到的一组目标模块以及它们所需要的库函数，装配成一个完整的装入模块关键问题修改相对地址变换外部调用符号链接方式静态链接方式、装入/运行时动态链接方式,5,2023/8/7,程序的链接过程,6,2023/8/7,链接方式比较,静态链接方式可执行文件、难以实现“内存”模块共享装入时动态链接便于软件版本的修改和更新便于实现目标模块为多个应用程序共享运行时动态链接将某些目标模块的链接推迟到执行时根据是否需要再完成,7,2023/8/7,程序的装入,基本目标及相关问题由装入程序将装入模块载入到内存装入位置、地址变换（重定位）及时机关键概念相对地址、绝对地址、重定位及其寄存器装入方式绝对装入方式（单道程序环境）静态可重定位装入方式（多道程序环境）动态运行时装入方式（运行中移动位置）,8,2023/8/7,绝对装入模块和可重定位装入模块,9,2023/8/7,（静态/动态）可重定位,重定位程序装入或执行时对装入模块或目标程序中的指令及数据地址的修改过程静态重定位由重定位装入程序在将装入模块装入内存时一次性完成重定位需要连续存储空间，装入后不能移动动态重定位需要特殊硬件（地址变换机构）支持，以保证地址转换不会影响指令的执行速度便于动态链接和代码共享,10,2023/8/7,动态重定位示意图,CPU,10000,相对地址2500,+,重定位寄存器,内存,物理地址12500,10000,10100,12500,15000,0,100,2500,5000,作业J,11,2023/8/7,操作系统内存管理功能要求,内存分配使各得其所、提高利用率及适应动态增长要求连续分配/离散分配方式地址映射逻辑地址转换为物理地址，与分配方式相关内存保护基于地址的保护、存取访问控制保护内存扩充对换技术、虚拟存储技术,12,2023/8/7,作业题,4.1 谈谈你对程序处理过程及内存管理相关概念与关键问题的认识与理解。同时并就各种可能的程序链接方式和程序装入方式进行比较和展开讨论。,13,2023/8/7,第四章 存储器管理,4.1 内存管理概述4.2 连续分配存储管理方式4.3 基本分页存储管理方式4.4 基本分段存储管理方式4.5 虚拟存储器概念及关键技术4.6 请求分页存储管理方式4.7 请求分段存储管理方式,14,2023/8/7,4.2 连续分配存储管理方式,4.2.1 单一连续分配存储管理4.2.2 固定分区分配存储管理4.2.3 动态分区分配存储管理4.2.4 动态可重定位分区分配 对换技术,15,2023/8/7,单一连续分配方式,内存划分为系统区和用户区整个用户区为一个用户独占，仅驻留一道程序静态链接和动态重定位技术、存储器保护措施仅适用于单用户、单任务操作系统中,16,2023/8/7,4.2 连续分配存储管理方式,4.2.1 单一连续分配存储管理4.2.2 固定分区分配存储管理4.2.3 动态分区分配存储管理4.2.4 动态可重定位分区分配 对换技术,17,2023/8/7,固定分区分配方式,用户区分为若干固定区域每个分区可装入一道作业分区划分方法(等分/不等分)分区说明表与内存分配算法可用于多道程序存储管理,A:B:C=15:30:50,存储空间分配情况,18,2023/8/7,4.2 连续分配存储管理方式,4.2.1 单一连续分配存储管理4.2.2 固定分区分配存储管理4.2.3 动态分区分配存储管理4.2.4 动态可重定位分区分配 对换技术,19,2023/8/7,动态分区分配方式,基本思想根据进程的实际需求，动态地对内存空间进行分配、回收及划分关键问题分区分配用数据结构分区分配算法分区分配与回收操作碎片（零头）处理,？黑板教学,20,2023/8/7,分区分配用数据结构,空闲分区表,空闲分区链,N+4,N+4,N个字节可用,分区大小,21,2023/8/7,分区分配算法,首次适应算法FF要求空闲分区链以地址递增次序链接查找开销大，但有利于大作业分配循环首次适应算法首次适应+起始查寻指针+循环查找减少查找开销，但不利于大作业分配最佳适应算法追求既能满足要求且又最小的空闲分区 要求空闲分区按大小递增次序链接微观意义上的最佳与宏观上的零头问题,最坏适应算法？,22,2023/8/7,动态分区内存分配流程,分配单位？,23,2023/8/7,动态分区内存回收情况,24,2023/8/7,动态分区内存回收流程,25,2023/8/7,4.2 连续分配存储管理方式,4.2.1 单一连续分配存储管理4.2.2 固定分区分配存储管理4.2.3 动态分区分配存储管理4.2.4 动态可重定位分区分配 对换技术,26,2023/8/7,动态重定位分区分配方式,紧凑连续分配要求程序装入内存空间的连续性分区分配产生的零头/碎片问题通过移动把多个分散拼接成大分区用户程序内存地址变化及地址修正问题动态重定位动态运行时装入方式及重定位寄存器动态重定位分区分配算法动态分配分区算法+紧凑功能,27,2023/8/7,紧凑（拼接）技术,紧凑前,紧凑后,28,2023/8/7,动态重定位分区分配流程,29,2023/8/7,4.2 连续分配存储管理方式,4.2.1 单一连续分配存储管理4.2.2 固定分区分配存储管理4.2.3 动态分区分配存储管理4.2.4 动态可重定位分区分配 对换技术,30,2023/8/7,多道程序环境下的对换,对换的概念及意义内存（进程、程序、数据）外存提高内存利用率对换实现机制UNIX：对换进程（中级调度）对换实现方式进程对换：分时系统页面/分段对换：虚拟存储技术,31,2023/8/7,对换空间的管理,文件区和对换区功能、管理目标及管理方式对换区使用情况数据结构空闲盘区表/链（盘块组为基本单位）对换区分配与回收操作分配算法分配操作回收操作,32,2023/8/7,进程的换出和换入,进程的换出被换出进程的选择（进程状态+优先级+内存驻留时间）换出过程（换出非共享或不再共享的程序及数据段对换空间申请换出内存释放内存分配数据结构及PCB修改）进程的换入被换入进程的选择（进程状态+换出时间）换入过程（内存申请换入 PCB修改）,33,2023/8/7,4.2 连续分配存储管理方式,4.2.1 单一连续分配存储管理4.2.2 固定分区分配存储管理4.2.3 动态分区分配存储管理4.2.4 动态可重定位分区分配 对换技术,34,2023/8/7,作业题,4.2 从内存管理的各个方面比较单一连续分配、固定分区分配、动态分区分配以及动态可重定位分区等存储管理方式的异同，特别注意相关数据结构和算法的理解。4.3 谈谈你对覆盖技术与对换技术的认识与理解。,35,2023/8/7,第四章 存储器管理,4.1 内存管理概述4.2 连续分配存储管理方式4.3 基本分页存储管理方式4.4 基本分段存储管理方式4.5 虚拟存储器概念及关键技术4.6 请求分页存储管理方式4.7 请求分段存储管理方式,36,2023/8/7,4.3 基本分页存储管理方式,4.3.1 离散存储管理方式4.3.2 页面与页表4.3.3 地址变换机构 两级和多级页表 反置页表,37,2023/8/7,离散存储管理方式,连续存储管理方式弊端碎片问题及紧凑开销离散分配方式分页存储管理分段存储管理段页式存储管理,38,2023/8/7,4.3 基本分页存储管理方式,4.3.1 离散存储管理方式4.3.2 页面与页表4.3.3 地址变换机构 两级和多级页表 反置页表,39,2023/8/7,页面与页表,页面和物理块进程逻辑地址空间及内存空间的划分页面编号与物理块编号内存分配与页内碎片内存页表与进程页表页面映射表及其表项(物理块号、存取控制字段)页面大小选择由机器的地址结构所决定页面大/小评析29B8KB之间,40,2023/8/7,物理块表（内存页表）,41,2023/8/7,位示图,利用位示图（即二维数组Mapm,n）的一位（0/1）来表示一个内存物理块（或磁盘盘块）的使用情况，使内存所有物理块（或磁盘上所有盘块）都与一个二进制位相对应,1 1 0 0 0 1 0 0 1 0 1 0 0 1 1 0 1 0 0 1 0 0 0 1 0 1 0 0 1 1 1 11 1 0 1 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 0 1 0 1 0 0 0 1 0,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16,123m,42,2023/8/7,物理块（盘块）的分配,Var Map:array 1.m,1.n of bit;顺序扫描位示图，找出一个或一组其值均为空闲的二进制位将所找到的一个或一组二进制位Mapi,j的行/列号转换为与之对应的物理块（盘块）号b：b=n(i-1)+j-1按物理块（或盘块）号分配物理块（或盘块），同时修改位示图,43,2023/8/7,物理块（盘块）的回收,将回收物理块（或盘块）的物理块（或盘块）号b转换为位示图中的行号i和列号j：i=b DIV n+1;j=b MOD n+1;按物理块（或盘块）号回收物理块（或盘块）根据回收物理块（或盘块）对应二进制位的行/列号修改位示图,44,2023/8/7,（进程）页表,用户程序,页表,页号,块号,内存,45,2023/8/7,分页存储地址结构及地址变换,分页存储管理地址结构 31 12 11 0 页 号 页内地址逻辑地址与页号及页内偏移地址之间的换算PageNo=INTAddr/PageLengthPageOffset=Addr MOD PageLength举例：对于1KB页面，若给定逻辑地址2170B，则 PageNo=2，PageOffset=122地址变换任务关键在于页号到物理块号的转变,46,2023/8/7,4.3 基本分页存储管理方式,4.3.1 离散存储管理方式4.3.2 页面与页表4.3.3 地址变换机构 两级和多级页表 反置页表,47,2023/8/7,基本的地址变换机构,页表寄存器,逻辑地址寄存器,页表,物理地址寄存器,+,越界中断,页号,物理块号,0,1,2,3,48,2023/8/7,具有快表的地址变换机构,页表寄存器,逻辑地址寄存器,页表,物理地址寄存器,+,越界中断,页号,物理块号,0,1,2,3,输入寄存器,页号,物理块号,快表,49,2023/8/7,快表引入前后数据存取速度比较,假定快表检索时间为20ns，内存访问时间为100ns，则若能在快表中找到CPU给出的页号，CPU为存取一个数据将需要(100+20)=120ns；而若不能在快表中找到CPU给出的页号，CPU为存取一个数据将需要(100+100+20)=220ns。进一步说，若假定快表查找命中率为80%，则其有效访问时间为12080%220(180%)=140ns。,50,2023/8/7,4.3 基本分页存储管理方式,4.3.1 离散存储管理方式4.3.2 页面与页表4.3.3 地址变换机构 两级和多级页表 反置页表,51,2023/8/7,页表空间问题及对策,页表空间问题现代计算机系统支持非常大的逻辑地址空间(232264)，页表变得庞大。例如，对于具有32位逻辑地址空间的分页系统，规定页面大小为4KB即212B，则每个进程页表的页表项可达1M个；若同时设定页表项大小为4B，则每个进程仅页表便需占用4MB 内存空间，且要求是连续的解决方案多级页表(页表分页及对换)或反置页表,52,2023/8/7,两级页表结构基本方法,基本思想对页表按内存物理块大小进行分页，对它们进行编号并离散地存放于不同的物理块中；同时为离散分配的页表分页再建立一张页表，称之为外层页表，以记录各页表分页对应的物理块号以前述32位逻辑地址空间、页面大小为4KB的系统为例，若采用一级页表结构，则每个进程页表的页表项可达1M个；而若采用两级页表结构，由于各页表分页包含4KB/4B=1K个页表项，故需1K个页表分页即可，因此外层页表的外层页号及内层页号均为10位。此时逻辑地址结构为：31 22 21 12 11 0 外 层 页 号 内 层 页 号 页 内 地 址,53,2023/8/7,两级页表结构示意图,外层页表,第0页页表,内存,0,1,2,n,0,1,2,1023,第1页页表,0,1,1023,第n页页表,0,1,1023,1,2,6,7,114,0,4,5,3,115,1468,54,2023/8/7,具有两级页表的地址变换结构,外层页表寄存器,逻辑地址寄存器,页表,物理地址寄存器,+,越界中断,内层页号,物理块号,外层页表,外层页号,分页页表起始地址,+,55,2023/8/7,多级页表结构,对于64位计算机，如规定页面大小仍为4KB，则每个进程的页表项可达264/4K=252个，且外层页表可能有252/210=242个页表项；即使按每个页表分页1M个页表项来划分，页表分页将达到4MB，而外层页表仍有252/220=4G个页表项，要占用16GB的连续内存空间。可见，无论怎样划分，其结果都是不能接受的。因此，必须采用多级页表，将16GB的外层页表再进行分页，并将各个分页离散的分配到不相邻接的物理块中，在利用第二级的外层页表来映射它们之间的关系。事实上，对于64位的机器，用三级页表结构都很难适应,56,2023/8/7,4.3 基本分页存储管理方式,4.3.1 离散存储管理方式4.3.2 页面与页表4.3.3 地址变换机构 两级和多级页表 反置页表,57,2023/8/7,反置页表,一般页表的表项是按页号进行排序，而页表项内容包括物理块号的；反置页表则是为每一个物理块设置一个页表项并将它们按物理块的号数排序，页表项内容包括对应页号及其隶属进程的标识符在利用反置页表进行地址变换时，是用进程标识符和页号去检索反置页表。若找到与之匹配的表项，则以该表项序号即该页所在物理块号与页内地址构成物理地址；否则地址出错或产生调页中断请求进程外部页表的设立及反置页表Hash检索,58,2023/8/7,反置页表地址变换机构,逻辑地址寄存器,反置页表,物理地址寄存器,PID/页号,物理块号,0,1,59,2023/8/7,4.3 基本分页存储管理方式,4.3.1 离散存储管理方式4.3.2 页面与页表4.3.3 地址变换机构 两级和多级页表 反置页表,60,2023/8/7,作业题,4.4 从=分页内存管理的各个方面等存储管理方式的异同，特别注意相关数据结构和算法的理解。4.5 谈谈你对技术的认识与理解。,61,2023/8/7,第四章 存储器管理,4.1 内存管理概述4.2 连续分配存储管理方式4.3 基本分页存储管理方式4.4 基本分段存储管理方式4.5 虚拟存储器概念及关键技术4.6 请求分页存储管理方式4.7 请求分段存储管理方式,62,2023/8/7,4.4 基本分段存储管理方式,4.4.1 分段存储管理方式的引入4.4.2 分段系统的基本原理4.4.3 信息共享 段页式存储管理方式,63,2023/8/7,分段存储管理方式的引入,满足用户在编程和使用上的多方面要求方便编程（作业基于逻辑关系自然分段）LOAD 1,A|;STORE 1,B|;信息共享信息保护（分段作为信息的逻辑单位）动态链接动态增长（特别是数据段地动态增长）,64,2023/8/7,4.4 基本分段存储管理方式,4.4.1 分段存储管理方式的引入4.4.2 分段系统的基本原理4.4.3 信息共享 段页式存储管理方式,65,2023/8/7,分段,作业地址空间被划分为若干段，每个段定义了一组逻辑信息，如主程序MAIN、子程序段X、数据段D及栈段S，各段均有自己的名字（段号）每个段都从0开始编址，并采用一段连续的地址空间，且段的长度取决于相应的逻辑信息组的长度，因而各段长度可不等整个作业的地址空间是二维的，其逻辑地址有段号(名)和段内地址所组成31 16 15 0 段 号 段内地址,66,2023/8/7,利用段表实现地址映射示意图,作业空间,段表,内存,段长,段号,0,1,(MAIN)=0,0,30K,(X)=1,0,20K,(D)=2,0,15K,(S)=3,0,10K,基址,2,3,(MAIN)=030K,(X)=120K,(D)=2 15K,(S)=3 10K,40K,80K,120K,150K,67,2023/8/7,分段系统地址变换机构,段表寄存器,逻辑地址寄存器,段表,物理地址寄存器,+,越界中断,段长,段号,0,1,基址,2,3,+,越界中断,低四位为0,68,2023/8/7,分页与分段存储管理的比较,相似之处实现机制（离散分配、地址映射机构）目的及内涵系统管理需要/用户需要、物理/逻辑单位分页/段长度固定与否、决定因素(系统硬件/信息性质)作业地址空间维数一维/二维、程序员编程,69,2023/8/7,4.4 基本分段存储管理方式,4.4.1 分段存储管理方式的引入4.4.2 分段系统的基本原理4.4.3 信息共享 段页式存储管理方式,70,2023/8/7,可重入代码（纯代码）,一种允许多个进程同时访问的代码为使各个进程所执行的代码完全相同，绝对不允许可重入代码在执行中有任何改变，所以它是一种不允许任何进程对其进行修改的代码但事实上，大多数代码在执行时都有可能发生改变，例如其中用于控制程序执行次数的变量及指针、信号量及数组等。为此，在每个进程中都必须配备局部数据区，并把在执行中可能改变的部分都拷贝到该数据区。这样，在程序执行时，只去对属于特定进程私有的数据区中的内容进行修改，而不去改变共享的代码，这时的可共享代码即成为可重入代码,71,2023/8/7,信息共享比较举例说明,多个用户对文本编辑程序的共享某多用户系统，可同时接纳40个用户，假设均在执行Editor进行文本编辑。若该文本编辑程序含有160KB的代码区和40KB的数据区，则总共需有8000KB的内存空间来支持40个用户。如果该文本编辑程序代码是可重入的，则无论分页系统还是分段系统该程序代码都能被共享，即内存中只需保留一份文本编辑程序的副本，因而所需内存空间仅为4040+160=1760KB,72,2023/8/7,基于分页的文本编辑器共享,进程1,内存,22,进程2,进程1页表,进程2页表,21,24,23,61,60,80,71,70,160KB,40KB,160KB,40KB,73,2023/8/7,基于分段的文本编辑器共享,进程1,内存,80K,进程2,进程1段表,240K,段长,段号,0,1,基址,进程2段表,段长,段号,0,1,基址,280K,380K,420K,74,2023/8/7,4.4 基本分段存储管理方式,4.4.1 分段存储管理方式的引入4.4.2 分段系统的基本原理4.4.3 信息共享 段页式存储管理方式,75,2023/8/7,段页式存储管理方式的引入,分页与分段存储管理各有优缺点分页系统能有效地提高内存利用率分段系统则能很好地满足用户需要分页/段存储管理各取所长、有机结合既具有分段系统便于实现、分段可共享、易于保护、可动态链接等一系列优点；又能像分页系统那样很好地解决内存的外部碎片问题以及为各个分段离散地分配内存等问题,76,2023/8/7,段页式存储管理方法,分段与分页原理的结合先将用户程序按信息性质分为若干段（赋予一个段名），再把每个段划分为若干页,主程序段,0,4K,8K,12K,15K,16K,子程序段,0,4K,8K,数据段,0,4K,8K,10K,12K,段页式存储管理地址结构,77,2023/8/7,利用段表和页表实现地址映射,段表,第0段页表,内存,第1段页表,段表寄存器,78,2023/8/7,段页式系统的地址变换结构,段表寄存器,逻辑地址寄存器,页表,物理地址寄存器,+,越界中断,页号,物理块号,段表,段号,页表长度,+,页表始址,状态,越界中断,79,2023/8/7,4.4 基本分段存储管理方式,4.4.1 分段存储管理方式的引入4.4.2 分段系统的基本原理4.4.3 信息共享 段页式存储管理方式,80,2023/8/7,第四章 存储器管理,4.1 内存管理概述4.2 连续分配存储管理方式4.3 基本分页存储管理方式4.4 基本分段存储管理方式4.5 虚拟存储器概念及关键技术4.6 请求分页存储管理方式4.7 请求分段存储管理方式,81,2023/8/7,常规存储管理问题与对策,要求将一个作业全部装入内存方能运行一些对内存空间要求超过内存容量的大作业因不能全部装入内存而无法运行同时有大量作业要求运行，但由于内存容量不足以容纳所有这些作业，则只能将少数作业装入内存首先运行，而将其它大量作业留在外存上等待解决方法增加物理内存容量（系统成本和机器条件）从逻辑上扩充内存容量=虚拟存储技术,82,2023/8/7,一次性全部装入及驻留性问题,作业“一次性”全部装入内存并不必要许多作业在每次运行时并非用到其全部程序和数据作业常驻内存存在不合理性因输入输出操作尚未完成而处于长期等待状态的运行进程或某些一次性运行程序对宝贵内存资源的占据问题后果使一些需要运行的作业无法装入运行，从而严重降低内存利用率和减少系统吞吐量,83,2023/8/7,局部性原理,程序在执行时将呈现局部性规律，即在一较短时间内，程序的执行仅限于某个部分；相应地，它所访问的内存空间也仅局限于某个区域程序在大多数情况下的顺序执行特点过程调用深度及执行轨迹程序循环结构执行及数据结构操作特点局部性表现形式时间局部性（指令执行与数据结构访问）空间局部性（存储单元临近访问）,84,2023/8/7,虚拟存储器技术要点,作业部分装入内存即可启动运行其余部分暂留磁盘程序执行过程页段访问机制已调入内存则直接访问尚未调入内存则缺页/段中断及请求调入页段置换功能技术效果大用户程序在小内存空间的运行多道程序度的提高,85,2023/8/7,虚拟存储器的定义,所谓虚拟存储器，是指仅把作业的一部分装入内存便可运行作业的存储器系统。具体地说，所谓虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。实际上，用户看到的大容量只是一种感觉，是虚的，故而得名虚拟存储器。其逻辑容量由内存和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。,86,2023/8/7,请求分页虚拟存储系统,技术构成分页+请求调页+页面置换硬件支持请求分页的页表机制缺页中断机构地址变换机构软件支持请求调页页面置换,87,2023/8/7,请求分段虚拟存储系统,技术构成分段+请求调段+分段置换硬件支持请求分段的段表机制缺段中断机构地址变换机构软件支持请求调段分段置换,88,2023/8/7,虚拟存储器的特征,离散性离散分配方式多次性作业被分成多次调入内存和运行对换性程序和数据在作业运行过程中的换进/出虚拟性内存容量的逻辑扩充,89,2023/8/7,第四章 存储器管理,4.1 内存管理概述4.2 连续分配存储管理方式4.3 基本分页存储管理方式4.4 基本分段存储管理方式4.5 虚拟存储器概念及关键技术4.6 请求分页存储管理方式4.7 请求分段存储管理方式,90,2023/8/7,4.6 请求分页存储管理方式,4.6.1 请求分页中的硬件支持4.6.2 内存分配策略和分配算法4.6.3 调页策略 页面置换算法,91,2023/8/7,页表机制,页表项的扩充,92,2023/8/7,缺页中断机构,缺页中断之中断特征保护CPU现场分析中断原因转入缺页中断处理程序恢复CPU现场缺页中断之特殊性在指令执行期间产生和处理中断信号一条指令执行期间，可能产生多次缺页中断,6,5,4,1,2,3,页面,copy ATO B,B:,A:,93,2023/8/7,地址变换机构,在分页系统的地址变换机构的基础上，增加缺页中断产生和处理并页面置换功能而构成地址变换过程要领从页表找到对应分页的页表项获悉该页尚未调入内存时，应产生缺页中断，请求操作系统从外存把该页调入内存关于快表和页表的检索及表项修改,94,2023/8/7,请求分页系统地址变换过程,95,2023/8/7,页面中断处理算法流程,保护CPU现场,缺页中断处理,从外存中找到缺页,内存满否？,从内存选择某页换出,是,否,该页被修改否？,是,将该页写回外存,否,命令CPU从外存读取缺页,启动I/O硬件,将缺页从外存换入内存,修改页表相应表项状态位及物理块号,返回,恢复CPU现场,96,2023/8/7,4.6 请求分页存储管理方式,4.6.1 请求分页中的硬件支持4.6.2 内存分配策略和分配算法4.6.3 调页策略 页面置换算法,97,2023/8/7,最小物理块数的确定,保证进程正常运行所需的最少物理块数若系统为某进程分配的物理块数少于此值，进程将无法正常运行不同于使进程有效工作所需的物理块数与计算机的硬件结构有关，并取决于指令的格式（操作数个数）、功能和寻址方式（直接/间接）,98,2023/8/7,物理块分配与置换策略,固定分配局部置换为每个进程分配一固定页数的内存空间，在整个运行期间都不再改变可变分配全局置换系统设立一个空闲物理块队列可变分配局部置换依据缺页率酌情增加或减少物理块,99,2023/8/7,物理块分配算法,平均分配算法将系统可供分配的物理块平均分配按比例分配算法BlockOfPk=maxminBlocks,Blocks PagesOfPk/PagesOfPi考虑优先权的分配算法照顾重要或紧迫的作业能尽快完成,100,2023/8/7,4.6 请求分页存储管理方式,4.6.1 请求分页中的硬件支持4.6.2 内存分配策略和分配算法4.6.3 调页策略 页面置换算法,101,2023/8/7,何时调入页面,预调页策略将那些预计在不久之后便会被访问的程序或数据所在的页面，预先调入内存以预测为基础，主要用于进程首次调入请求调页策略当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，应立即提出请求，由系统将其所需页面调入内存；易于实现但系统开销大,102,2023/8/7,何处调入页面,对换区空间充分进程运行前，便须将与该进程有关的文件，从文件区拷贝到对换区对换区空间不足文件是否修改分别处理UNIX方式凡未运行过的页面都应从文件区调入，而对于曾运行过又被换出到对换区的页面则从对换区调入,103,2023/8/7,页面调入过程,缺页中断发生程序所访问的页面不在内存时产生缺页中断并转入缺页中断处理程序根据页表外存地址调入所缺页面页表项外存地址（物理块号）内存不足置换页面淘汰算法是否重写磁盘,104,2023/8/7,4.6 请求分页存储管理方式,4.6.1 请求分页中的硬件支持4.6.2 内存分配策略和分配算法4.6.3 调页策略 页面置换算法,105,2023/8/7,页面置换算法,4.6.4.1 抖动与缺页率4.6.4.2 最佳置换算法4.6.4.3 先进先出置换算法4.6.4.4 最近最久未使用置换算法4.6.4.5 Clock置换算法4.6.4.6 最少使用置换算法4.6.4.7 页面缓冲算法,106,2023/8/7,抖动与缺页率,抖动的定义如果所用置换算法不当，便可能导致这样一种情形：刚被换出的页面很快又被访问，需重新调入，为此，又需再选一页换出；而此刚被换出的页面，不久也被访问，故又需将它调入，如此频繁地更换页面，以致一个进程在运行中把大部分的时间耗费在页面置换的工作上，称该进程发生了抖动（或称之为颠簸）缺页率缺页率=缺页中断次数/页面访问次数,107,2023/8/7,页面置换算法,4.6.4.1 抖动与缺页率4.6.4.2 最佳置换算法4.6.4.3 先进先出置换算法4.6.4.4 最近最久未使用置换算法4.6.4.5 Clock置换算法4.6.4.6 最少使用置换算法4.6.4.7 页面缓冲算法,108,2023/8/7,最佳置换算法,基本思想选择永不使用或是在最长时间内不再被访问（即距现在最长时间才会被访问）的页面淘汰出内存评价理想化算法，具有最好性能（对于固定分配页面方式，本法可保证获得最低的缺页率），但实际上却难于实现，故主要用于算法评价参照,109,2023/8/7,最佳置换算法举例说明,某进程分配获得三个物理块缺页中断次数为6次，缺页率30%,页面访问序列,内存页面分布情况,页面预先装入,110,2023/8/7,页面置换算法,4.6.4.1 抖动与缺页率4.6.4.2 最佳置换算法4.6.4.3 先进先出置换算法4.6.4.4 最近最久未使用置换算法4.6.4.5 Clock置换算法4.6.4.6 最少使用置换算法4.6.4.7 页面缓冲算法,111,2023/8/7,先进先出置换算法,基本思想选择最先进入内存即在内存驻留时间最久的页面换出到外存进程已调入内存的页面按进入先后次序链接成一个队列，并设置替换指针以指向最老页面评价简单直观，但不符合进程实际运行规律，性能较差，故实际应用极少,112,2023/8/7,某进程分配获得三个物理块缺页中断次数为12次，缺页率60%,页面访问序列,内存页面分布情况,页面预先装入,先进先出置换算法举例说明,113,2023/8/7,页面置换算法,4.6.4.1 抖动与缺页率4.6.4.2 最佳置换算法4.6.4.3 先进先出置换算法4.6.4.4 最近最久未使用置换算法4.6.4.5 Clock置换算法4.6.4.6 最少使用置换算法4.6.4.7 页面缓冲算法,114,2023/8/7,最近最久未使用置换算法LRU,基本思想以“最近的过去”作为“最近的将来”的近似，选择最近一段时间最长时间未被访问的页面淘汰出内存评价适用于各种类型的程序，性能较好，但需要较多的硬件支持,115,2023/8/7,某进程分配获得三个物理块缺页中断次数为9次，缺页率45%,页面访问序列,内存页面分布情况,页面预先装入,最近最久未使用置换算法举例说明,116,2023/8/7,最近最久未使用置换算法硬件支持移位寄存器,117,2023/8/7,最近最久未使用置换算法硬件支持栈,4,7,0,7,1,0,1,2,1,2,6,某进程分配获得五个物理块,页面访问序列,118,2023/8/7,页面置换算法,4.6.4.1 抖动与缺页率4.6.4.2 最佳置换算法4.6.4.3 先进先出置换算法4.6.4.4 最近最久未使用置换算法4.6.4.5 Clock置换算法4.6.4.6 最少使用置换算法4.6.4.7 页面缓冲算法,119,2023/8/7,简单Clock置换算法(NRU),查寻指针,120,2023/8/7,改进型Clock置换算法,基本思想 从查寻指针当前位置起扫描内存分页循环队列，选择A=0且M=0的第一个页面淘汰；若未找到，转 开始第二轮扫描，选择A=0且M=1的第一个页面淘汰，同时将经过的所有页面访问位置0；若不能找到，转评价与简单Clock算法相比，可减少磁盘的I/O操作次数，但淘汰页的选择可能经历多次扫描，故实现算法自身的开销增大,121,2023/8/7,页面置换算法,4.6.4.1 抖动与缺页率4.6.4.2 最佳置换算法4.6.4.3 先进先出置换算法4.6.4.4 最近最久未使用置换算法4.6.4.5 Clock置换算法4.6.4.6 最少使用置换算法4.6.4.7 页面缓冲算法,122,2023/8/7,最少使用置换算法LFU,基本思想为内存各页设置一移位寄存器用于记录对应被访频率，并选择在最近时期使用次数最少的页面淘汰评价鉴于仅用移位寄存器有限各位来记录页面使用会导致访问一次与访问多次的等效性，本算法并不能真实全面地反映页面使用情况,123,2023/8/7,页面置换算法,4.6.4.1 抖动与缺页率4.6.4.2 最佳置换算法4.6.4.3 先进先出置换算法4.6.4.4 最近最久未使用置换算法4.6.4.5 Clock置换算法4.6.4.6 最少使用置换算法4.6.4.7 页面缓冲算法,124,2023/8/7,页面缓冲算法PBA,基本思想设立空闲页面链表和已修改页面链表采用可变分配和基于先进先出的局部置换策略，并规定被淘汰页先不做物理移动，而是依据是否修改分别挂到空闲页面链表或已修改页面链表的末尾空闲页面链表同时用于物理块分配当已修改页面链表达到一定长度如64个页面时，一起将所有已修改页面写回磁盘，故可显著减少磁盘I/O操作次数,125,2023/8/7,页面置换算法,4.6.4.1 抖动与缺页率4.6.4.2 最佳置换算法4.6.4.3 先进先出置换算法4.6.4.4 最近最久未使用置换算法4.6.4.5 Clock置换算法4.6.4.6 最少使用置换算法4.6.4.7 页面缓冲算法,126,2023/8/7,4.6 请求分页存储管理方式,4.6.1 请求分页中的硬件支持4.6.2 内存分配策略和分配算法4.6.3 调页策略 页面置换算法,127,2023/8/7,第四章 存储器管理,4.1 内存管理概述4.2 连续分配存储管理方式4.3 基本分页存储管理方式4.4 基本分段存储管理方式4.5 虚拟存储器概念及关键技术4.6 请求分页存储管理方式4.7 请求分段存储管理方式,128,2023/8/7,4.7 请求分段存储管理方式,4.7.1 请求分段中的硬件支持4.7.2 分段共享4.7.3 分段保护,129,2023/8/7,段表机制,段表项的扩充,起始盘块号,130,2023/8/7,地址变换机构,在分段系统的地址变换机构的基础上，增加缺段中断产生和处理并分段置换功能而构成地址变换过程要领从段表找到对应分段的段表项获悉该段尚未调入内存时，应产生缺段中断，请求操作系统从外存把该段调入内存关于快表和段表的检索及表项修改,131,2023/8/7,请求分段系统地址变换,132,2023/8/7,缺段中断机构及处理过程,133,2023/8/7,4.7 请求分段存储管理方式,4.7.1 请求分段中的硬件支持4.7.2 分段共享4.7.3 分段保护,134,2023/8/7,共享段表,共享进程计数存取控制字段共享段不同段号,共享进程计数count,分段共享进程描述,共享段表,135,2023/8/7,共享段的分配与回收,共享段的分配对于第一个请求使用某共享段的进程，由系统为该共享段进行内存区的分配和装入，同时把共享段信息填入对应进程段表中，并在共享段表中为之增加一个表项和填写相关内容；对于以后其它进程提出共享该段要求，则仅需对对应的进程段表表项及共享段表表项修正即可共享段的回收与共享段分配过程恰好相逆,136,2023/8/7,4.7 请求分段存储管理方式,4.7.1 请求分段中的硬件支持4.7.2 分段共享4.7.3 分段保护,137,2023/8/7,越界检查与存取控制检查,越界检查段号及段内地址合法性检查存取控制检查段表中对应表项存取控制字段为依据通常访问方式包括只读、只执行（既不可读也不可写）、读/写三种共享段的存取控制应对不同进程赋予不同权限，既要保证信息安全，又要满足运行需要,138,2023/8/7,环保护机构,程序间控制传输一个程序可调用驻留在相同环或较高特权环中的服务,数据访问一个程序可访问驻留在相同环或较低特权环中的数据,139,2023/8/7,4.7 请求分