第4章存储管理2ppt课件.ppt

4.3 页式存储管理页式存储管理4.3.1 根本思想〔任务原理〕根本思想〔任务原理〕1. 目的程序逻辑地址的划分目的程序逻辑地址的划分 把目的程序按逻辑地址划分成大小相等的把目的程序按逻辑地址划分成大小相等的部分部分, 称为页称为页(逻辑页逻辑页)从 0 开场编制页号开场编制页号, 页内地址是相对于页内地址是相对于 0 编址 页号页号P 页内位移量页内位移量W0111223编号编号0~4095相对地址相对地址0~4095逻辑地址逻辑地址 用户程序的划分是由系统自动完成的用户程序的划分是由系统自动完成的, 对对用户是透明的用户是透明的 一页的大小普通为一页的大小普通为 2 的整数的整数次幂次幂, 地址的高位部分为页号地址的高位部分为页号, 低位部分为低位部分为页内地址页内地址(页内位移量页内位移量) 2.内存物理空间的划分：内存物理空间的划分： 按页的大小划分为大小相等的区域，称按页的大小划分为大小相等的区域，称为页框为页框(物理页面物理页面) 3.内存分配：内存分配： 以页为单位进展分配，并按进程的页以页为单位进展分配，并按进程的页数多少来分配。

逻辑上相邻的页，物理上数多少来分配逻辑上相邻的页，物理上不一定相邻不一定相邻4.页表页表 (页面映像表页面映像表)和地址映射：和地址映射： 建立页表建立页表, 给出逻辑地址页号和内存给出逻辑地址页号和内存物理块号对应的关系物理块号对应的关系, 经过它进展地址映射经过它进展地址映射0页页1页页2页页3页页4页页5页页6页页0123456进程的进程的地址空间地址空间块号块号页号页号页表页表主存中页框主存中页框〔物理块〕〔物理块〕存取存取控制控制4.3.2 管理管理1. 建立页表：系统为每个进程都建立了一个页表建立页表：系统为每个进程都建立了一个页表2.空块管理空块管理——总页表总页表3.内存的分配与回收内存的分配与回收计算一个进程所需求的总块数计算一个进程所需求的总块数N查总页表查总页表, 看能否还有看能否还有N个空闲块个空闲块假设有相应空闲块假设有相应空闲块, 那么恳求页表区那么恳求页表区, 把页表起始把页表起始地址填入地址填入PCB, 页表长度为页表长度为N分配分配N个空闲块个空闲块, 将块号将块号(物理块物理块)填入页表填入页表修正总页表修正总页表4.页面大小的选择页面大小的选择 小页面的优缺陷、大页面的优缺陷小页面的优缺陷、大页面的优缺陷b页号页号 块号块号越界中断越界中断页表长度页表长度 l比较比较P>l页表始址页表始址 p0+页号页号p p 页内地址页内地址d dbd物理地址存放器物理地址存放器页表存放器页表存放器逻辑地址逻辑地址页表页表01..4.3.3 地址变换机构地址变换机构1. 根本地址变换机构根本地址变换机构 页表和页表存放器页表和页表存放器(页表始址页表始址 p0,页表长页表长度度 l )008003 4C8 003 4C8 2AC4C84C8比较比较0123+2AC2. 具有快表的地址变换机构具有快表的地址变换机构硬件支持硬件支持1)页表存放器一对：页表存放器一对： 页表始址存放器页表始址存放器:页表始址页表始址 p0 页表长度存放器页表长度存放器:页表长度页表长度 l2) 联想存放器联想存放器(68030有有22个个, 80486有有32个个)—快表快表 它是介于内存与存放器之间的存储机制它是介于内存与存放器之间的存储机制, 为加快地址变换速度而设置为加快地址变换速度而设置;它的访问速度比它的访问速度比页表快一个数量级页表快一个数量级, 它保管着正在运转进程的它保管着正在运转进程的页表的子集页表的子集(部分表项部分表项)。

存放当前频繁访问存放当前频繁访问的那些页表项的那些页表项, 快表项含快表项含:1) 页号页号 2) 页在内存的块号页在内存的块号3) 标识标识(形状形状)位位 4) 淘汰位淘汰位b页号页号 块号块号越越界界中中断断页表长度页表长度 l比较比较P>lpb快表快表页号页号 块号块号页表始址页表始址 p0+页号页号p p 页内地址页内地址d d物理地址存放器物理地址存放器页表存放器页表存放器逻辑地址逻辑地址地址映射机制地址映射机制页表页表01...bd CPU 给出有效逻辑地址后给出有效逻辑地址后, 自动自动将页号与快表中的一切页号进展比将页号与快表中的一切页号进展比较较有那么直接读出对应的物理块号送有那么直接读出对应的物理块号送物理地址存放器中物理地址存放器中无那么继续按页号检索页表无那么继续按页号检索页表,在页在页表中读出物理块号送物理地址存放表中读出物理块号送物理地址存放器中器中并同时修正快表并同时修正快表, 使快表中一直坚使快表中一直坚持着最近频繁访问的页信息持着最近频繁访问的页信息实践上快表和页表检索同时进展实践上快表和页表检索同时进展快表查到那么终止检索页表快表查到那么终止检索页表, 没查没查到那么继续检索页表到那么继续检索页表上述过程全部由硬件实现上述过程全部由硬件实现, 并行性并行性好速度快。

好速度快008比较比较03 4C8 03 4C8 4C84C82AC03 2AC+2AC2AC03 2AC CPU 给出有效逻辑地址后给出有效逻辑地址后, 自动将页号与快表中自动将页号与快表中的一切页号进展比较的一切页号进展比较, 有那么直接读出对应的物理块有那么直接读出对应的物理块号送物理地址存放器中号送物理地址存放器中, 无那么继续按页号检索页表无那么继续按页号检索页表,在页表中读出对应的物理块号送物理地址存放器中在页表中读出对应的物理块号送物理地址存放器中, 并同时修正快表并同时修正快表, 使快表中一直坚持着最近频繁访问使快表中一直坚持着最近频繁访问的页信息实践上快表和页表检索是同时进展的的页信息实践上快表和页表检索是同时进展的, 快快表查到那么终止检索页表表查到那么终止检索页表, 没查到那么继续检索页表没查到那么继续检索页表上述过程全部由硬件实现上述过程全部由硬件实现, 并行性好速度快其中并行性好速度快其中:物理块号物理块号 b 的地址的地址= 页表始址页表始址+页号页号*页表项长度页表项长度物理地址物理地址 P = 物理块号物理块号*页的大小页的大小+页内地址页内地址快表的命中率普通为：快表的命中率普通为：80%~90%页式管理的优点页式管理的优点: 处理了碎片问题、便于管理处理了碎片问题、便于管理 缺陷缺陷: 不易实现共享、不便于动态衔接不易实现共享、不便于动态衔接4.3.3 两级和多级页表两级和多级页表 对于对于32位逻辑地址空间位逻辑地址空间, 页面大小为页面大小为4096B那么那么页表项可达页表项可达1兆兆, 整个页表最多可占整个页表最多可占4兆延续空间兆延续空间, 可采用两级或多级可采用两级或多级(64位位)页表来处理这一问题。

页表来处理这一问题 每页最多可包容每页最多可包容1024个页表项个页表项, 将将1兆个页表项兆个页表项分为分为1024个子表个子表,子表分页存储在内存中子表分页存储在内存中, 每个子表每个子表有有1024个页表项建立一个外层页表个页表项建立一个外层页表, 它的每个页它的每个页表项存储各子表的物理块号表项存储各子表的物理块号, 经过两级查表即可得经过两级查表即可得到逻辑地址页对应的物理块号逻辑地址构造为：到逻辑地址页对应的物理块号逻辑地址构造为： 31 22 21 12 11 0外部页号外部页号p1 内层页号内层页号p2 页内地址页内地址d01...0页页表页页表主存中页框主存中页框〔物理块〕〔物理块〕01...1页页表页页表......01...外部页表外部页表地址映射机制地址映射机制b1 l1越界中断越界中断页表长度页表长度 l比较比较p1 p2b快表快表页号页号 块号块号页表始址页表始址 p0+外部页号外部页号p1 内层页号内层页号p2 页内地址页内地址dbd物理地址存放器物理地址存放器外部页表存放器外部页表存放器逻辑地址逻辑地址外部页表外部页表01...比较比较b01..+p1号页表号页表比较比较外部页号外部页号p1 内层页号内层页号p2 页内地址页内地址ddp1 p2bbb1 l1+比较比较b+bp1 p2b4.3.4 反置页表反置页表 当逻辑地址非常大时当逻辑地址非常大时, 页表项占内存太多页表项占内存太多, 用反用反置页表可以减少此项开销置页表可以减少此项开销,它将页表反置它将页表反置, 即页表项即页表项内容是逻辑页号和进程标识符内容是逻辑页号和进程标识符, 表项的顺序按物理表项的顺序按物理块号排序块号排序, 一切加载在内存的进程公用一个反置页一切加载在内存的进程公用一个反置页表表,进展进展 地址变换时地址变换时, 用进程标识符和页号检索反置用进程标识符和页号检索反置页表页表,查不到时那么按一定的算法置换查不到时那么按一定的算法置换, 将该页调入将该页调入内存内存; 因此在外存上每个进程都有一个外部页表因此在外存上每个进程都有一个外部页表, 该该表中包含了该进程每页在外存中的物理位置。

根据表中包含了该进程每页在外存中的物理位置根据它可将所需页调入内存它可将所需页调入内存 为了加快地址变换时用进程标识符和页号检索为了加快地址变换时用进程标识符和页号检索的查找速度的查找速度, 可利用哈希表可利用哈希表, 还应有相应的处理冲突还应有相应的处理冲突的方法4.4 段式存储管理段式存储管理 4.4.1 根本思想〔任务原理〕根本思想〔任务原理〕用户需求用户需求: 信息共享信息共享,信息维护信息维护,动态增长动态增长,动态链接动态链接1. 用户程序划分用户程序划分 程序的地址空间按本身的逻辑关系划分为假设程序的地址空间按本身的逻辑关系划分为假设干个段干个段, 每个段定义了一组逻辑信息例如每个段定义了一组逻辑信息例如: 主程主程序段序段Main, 子程序段子程序段X,子程序段子程序段Y, 数据段数据段D, 堆栈段堆栈段S等等; 每个段都有本人的名字每个段都有本人的名字, 可用段号来替代段名可用段号来替代段名, 段号从段号从0开场编号每个段内都也从开场编号每个段内都也从0开场编址开场编址, 段内地址空间是延续的段内地址空间是延续的, 各段的长度不等整个程各段的长度不等。

整个程序的地址空间是二维的序的地址空间是二维的, 段号维和段内地址维段号维和段内地址维 程序逻辑地址程序逻辑地址:段号段号 段内地址段内地址...0S堆栈段堆栈段[S]主程序段主程序段[M]......0EP子程序段子程序段[X]0K...CALL [X] [E].........CALL [Y] [F]CALL [A] 116......0FL子程序段子程序段[Y]0116N数据段数据段[D]12345...例如：例如：2. 内存物理空间的划分内存物理空间的划分 内存空间被动态的划分为假设干个长度不一样内存空间被动态的划分为假设干个长度不一样的物理段的物理段, 每个物理段由起始地址和长度确定每个物理段由起始地址和长度确定3. 内存分配内存分配 以段为单位分配内存以段为单位分配内存, 每个段在内存中占据延续每个段在内存中占据延续空间空间(内存随机分割内存随机分割, 需求多少分配多少需求多少分配多少), 但各段之但各段之间可以不延续存放间可以不延续存放4. 经过段表进展地址映射经过段表进展地址映射 段表记录各段的首段表记录各段的首(地地)址和长度址和长度.....S0RD0NY0LX0PM0K逻辑段号逻辑段号逻辑地址空间逻辑地址空间PKRLN主存主存K 320kP 150kL 600kN 800kR 500k长度长度 段首址段首址 OS100k320k500k600k800k150k段表段表4.4.2 管理管理1. 每个程序设一个段表每个程序设一个段表2. 空闲块管理：记录空闲区起始地址和长度空闲块管理：记录空闲区起始地址和长度3. 内存的分配算法：内存的分配算法： 首先适配；最正确适配；最坏适配首先适配；最正确适配；最坏适配段号段号 段首址段首址 段长度段长度 0 50k 40k 1 120k 110k 2 260k 220k4.4.3 地址变换机制地址变换机制硬件支持硬件支持1. 一对存放器：一对存放器：段表始址存放器段表始址存放器: 保管运转进程的段表始址保管运转进程的段表始址Cb段表长度存放器段表长度存放器: 保管运转进程的段表长度保管运转进程的段表长度Cl2. 相联存放器相联存放器—快表快表 (并行快速查找并行快速查找) 它是介于内存与存放器之间的存储机制它是介于内存与存放器之间的存储机制, 为加快地址变换速度而设置为加快地址变换速度而设置;它的访问速度比它的访问速度比段表快一个数量级段表快一个数量级, 它保管着正在运转进程的它保管着正在运转进程的段表的子集段表的子集(部分表项部分表项)。

存放当前频繁访问存放当前频繁访问的那些段表项的那些段表项,表项含表项含:段号；段号； 段始址；段始址； 段长度；段长度；标识标识(形状形状)位；访问位，位；访问位， 淘汰位淘汰位段表长度段表长度Cl段表始址段表始址Cb+段号段号S 位移量位移量d 比较比较b + d比较比较段表段表段号段号 段长段长 基址基址S>=Cl快表快表物理地址存放器物理地址存放器控制存放器控制存放器有效逻辑地址有效逻辑地址lbSlbd>=l地址映射及存储维护机制地址映射及存储维护机制地地址址越越界界地址越界地址越界01...+段式管理的优点：便于动态恳求内存段式管理的优点：便于动态恳求内存 易于维护、便于共享、可动态链接、可动态增长易于维护、便于共享、可动态链接、可动态增长缺陷：产生碎片缺陷：产生碎片分页和分段的主要区别分页和分段的主要区别页是物理单位页是物理单位, 分页是为了消减内存的外零头以提分页是为了消减内存的外零头以提高内存的利用率高内存的利用率, 仅仅是系统的需求仅仅是系统的需求 段是逻辑单位段是逻辑单位, 分段是为了更好地满足用户需求。

分段是为了更好地满足用户需求页的大小固定且由系统确定页的大小固定且由系统确定, 分页由硬件实现分页由硬件实现 段的长度不固定段的长度不固定, 由编译时根据程序信息来划分由编译时根据程序信息来划分分页的作业地址空间是一维的线性空间标识地址分页的作业地址空间是一维的线性空间标识地址时时, 只需给出一个逻辑地址只需给出一个逻辑地址 分段的作业地址空间是二维的分段的作业地址空间是二维的, 标识地址时标识地址时, 必必需给出段名和段内地址需给出段名和段内地址4.4.4 段的共享与维护段的共享与维护P 122分页系统中的共享分页系统中的共享:图图4-18分段系统中的共享分段系统中的共享:图图4-19纯码纯码数据数据1进程进程1段长段长 基址基址纯码纯码数据数据1段长段长 基址基址分段系统中的共享分段系统中的共享:图图4-19页表页表0页页1页页2页页3页页4页页01234进程进程1块号块号页号页号存取存取控制控制0页页1页页2页页3页页4页页5页页6页页0123456进程进程2纯码纯码数据数据数据数据分页系统中的共享分页系统中的共享:图图4-184.5 段页式存储管理段页式存储管理4.5.1 产生背景及根本思想产生背景及根本思想背景：结合了二者优点、抑制了二者的缺陷背景：结合了二者优点、抑制了二者的缺陷 即：提高利用率，满足用户要求即：提高利用率，满足用户要求根本思想：根本思想： 用户程序划分用户程序划分: 按段式划分按段式划分(对用户来讲对用户来讲, 按段的按段的逻逻 辑关系进展划分辑关系进展划分; 对系统讲对系统讲, 按页划分每一段按页划分每一段) 逻辑地址：逻辑地址： 内存划分：按页式存储管理方案内存划分：按页式存储管理方案 内存分配：以页为单位进展分配内存分配：以页为单位进展分配 段内地址段内地址段号段号 页号页号 页内地址页内地址4.5.2 管理管理1.段表：记录了每一段的页表始址和页表长度段表：记录了每一段的页表始址和页表长度2.页表：记录了逻辑页号与内存块号的对应关系。

页表：记录了逻辑页号与内存块号的对应关系〔每一段有一个，一个程序能够有多个页表〕〔每一段有一个，一个程序能够有多个页表〕3.空块管理：空块管理：4.分配：同页式管理分配：同页式管理硬件支持硬件支持 段表始址存放器段表始址存放器 段表长度存放器段表长度存放器 相联存储器〔快表〕相联存储器〔快表〕地址映射机制地址映射机制 与两级页表类与两级页表类似似b1 l1越界中断越界中断段表长度段表长度Cl比较比较s pb快表快表段页号段页号 块号块号段表始址段表始址Cb+段号段号s 段内页号段内页号p 页内地址页内地址dbd物理地址存放器物理地址存放器段表存放器段表存放器逻辑地址逻辑地址段表段表01...比较比较b01..+S段页表段页表本段页表本段页表始址长度始址长度8.页式存储管理页式存储管理(系统需求系统需求, 处理碎片处理碎片) 离散分配方式、页面大小的选择离散分配方式、页面大小的选择 建进程页表、空块管理建进程页表、空块管理—总页表、内存的分配与回收总页表、内存的分配与回收 地址变换机构地址变换机构: 页表存放器、页表、快表页表存放器、页表、快表(联想存放器联想存放器)9. 两级和多级页表反置页表两级和多级页表反置页表10. 段式存储管理段式存储管理用户需求用户需求: 信息共享信息共享,信息维护信息维护,动态增长动态增长,动态链接动态链接用户程序划分用户程序划分: 程序二维地址空间段号维和段内地址维程序二维地址空间段号维和段内地址维地址变换机构地址变换机构: 段表存放器、段表、快表段表存放器、段表、快表(联想存放器联想存放器)11. 段页式存储管理段页式存储管理 结合两者之优点处理系统需求和用户需求结合两者之优点处理系统需求和用户需求 用户地址空间二维、内存分配方式分页用户地址空间二维、内存分配方式分页 地址变换机构地址变换机构: 段表存放器、段表、页表、快表段表存放器、段表、页表、快表作业作业: P142 10、、12、、14。