计算机操作系统复习串讲第三讲课件

第四章存储器管理操作系统7/23/20231第四章存储器管理重点理解重定位的基本概念

掌握动态分区分配方式

掌握理解分页和分段存储管理方式

理解虚拟存储器的基本概念

掌握请求分页系统的基本原理

难点动态分区分配算法

分页和分段地址转换请求分页系统的地址转换及页面置换算法7/23/20232第四章存储器管理知识点重定位的基本概念

动态分区分配方式及分配算法、分区保护分页存储管理及地址变换、分段存储管理及地址变换，信息共享和保护虚拟存储器的基本概念、特征，页面置换技术

请求分页系统，页表机制、地址变换及页面置换算法

7/23/20233第四章存储器管理主存储器管理功能存储分配和回收分配和回收算法及相应的数据结构地址变换和重定位可执行文件生成中的链接技术程序加载(装入)时的重定位技术进程运行时硬件和软件的地址变换技术和机构存储共享和保护代码和数据共享地址空间访问权限（读、写、执行）存储器扩充：存储器的逻辑组织和物理组织；由应用程序控制：覆盖；由OS控制：交换（整个进程空间），虚拟存储的请求调入和预调入（部分进程空间）7/23/20234第四章存储器管理程序的装入和链接

连续分配方式

基本分页存储管理

基本分段存储管理虚拟存储器的基本概念请求分页存储管理方式页面置换算法请求分段存储管理方式7/23/20235程序的装入和链接程序的装入程序的链接7/23/202364.1.1程序的装入1.绝对装入方式(AbsoluteLoadingMode)2.可重定位装入方式(RelocationLoadingMode)3.动态运行时装入方式(DynamicRun-timeLoading)7/23/20237第四章存储器管理程序的装入和链接

连续分配方式

基本分页存储管理

基本分段存储管理虚拟存储器的基本概念请求分页存储管理方式页面置换算法请求分段存储管理方式7/23/20238连续分配方式单一连续分配固定分区分配动态分区分配可重定位分区分配对换（Swapping）7/23/20239单一连续分配连续分配方式为一个用户程序分配一个连续的内存空间单一连续分配是最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中把内存分为系统区：OS使用，通常放在内存低址部分用户区：用户可使用的全部内存空间存储器保护机构不健全，易造成系统破坏优点：易于管理缺点：对要求内存空间少的程序，造成内存浪费；程序全部装入，很少使用的程序部分也占用内存7/23/202310连续分配方式单一连续分配固定分区分配动态分区分配可重定位分区分配对换（Swapping）7/23/202311固定分区分配最简单的可运行多道程序的存储管理方式内存用户空间划分为若干个固定大小的区域，每个分区中只装入一道作业划分分区的方法分区大小相等：即使所有的内存分区大小相等太大：浪费太小：不够用分区大小不等：划分为多个大、中、小搭配的分区根据程序大小决定所使用的分区大班在大教室、小班在小教室7/23/202312内存分配分区的信息根据分区使用表管理固定分区分配20使用界地址寄存器采用静态重定位问题：并发进程数受分区个数的制约！出现：有内存却不能运行程序或大进程无法运行！7/23/202313连续分配方式单一连续分配固定分区分配动态分区分配可重定位分区分配对换（Swapping）7/23/202314动态分区分配根据进程的实际需要，动态地为之分配内存空间分配中数据结构空闲分区表记录每个空闲分区的情况空闲分区链实现对空闲分区的分配和链接7/23/202315动态分区分配分区分配算法

首次适应算法FF

循环首次适应算法最佳适应算法最差适应算法7/23/202316动态分区分配分区分配算法

首次适应算法FF

空闲分区链以地址递增顺序链接分配时从链首开始查找，找到一个大小可满足的空闲分区，划出一块给请求者优点：简单；优先利用低地址空闲区，保留高地址大空闲区缺点：会造成在低地址部分很多难以利用的小空闲分区，查找效率低循环首次适应算法每次分配时从上一次找到空闲分区的下一个空闲区开始查找优点：减少查找空闲分区开销，空闲分区分布更均匀缺点：缺乏大的空闲区7/23/202317动态分区分配最佳适应算法空闲区按容量由小到大排序每次分配时，把能满足要求、又是最小的分区分配给作业优点：不缺乏大的空闲区缺点：会在存储器中留直许多难以利用的小分区——“零头（或碎片）”；查找效率低最差适应算法空闲区按容量由大到小排序每次分配时，把能满足要求、又是最大的分区分配给作业优点：剩余的空间最大化，不出现太小的“零头”缺点：缺乏大的空闲区首次适应被认为最好、最快，其次是循环，最佳最差（每次分配后剩下小碎片，难再分，不得不经常压缩内存，反而浪费CPU）7/23/202318动态分区分配空闲区回收区回收区空闲区空闲区回收区空闲区回收区情况1情况2情况3情况47/23/2023192)回收内存回收区F1F2回收区F2回收区F1回收区回收区7/23/202320动态分区分配分区式存储管理的优缺点优点：便于动态申请内存便于共享内存便于动态链接缺点： 碎片问题(外碎片)，要求连续的内存空间，内存利用率不高，受实际内存容量限制7/23/202321连续分配方式单一连续分配固定分区分配动态分区分配可重定位分区分配对换（Swapping）7/23/2023224.2.4可重定位分区分配1.动态重定位的引入操作系统用户程序110kb用户程序330kb用户程序614kb用户程序926kb80kb用户程序9用户程序6用户程序3用户程序1操作系统紧凑7/23/202323可重定位分区分配动态重定位的引入连续分配存在的问题

必须有足够大的连续空间才能分配解决方法：“拼接”或“紧凑”的引入7/23/202324可重定位分区分配动态重定位的实现作业装入内存后的所有地址仍是相对地址，将相对地址转换成物理地址的工作在指令执行时进行需要有硬件地址变换机构的支持7/23/2023253.动态重定位分区分配算法动态重定位分区分配算法，与动态分区分配算法基本上相同；差别仅在于：在这种分配算法中，增加了“紧凑”功能，通常是在找不到足够大的空闲分区来满足用户需求时，进行紧凑。图4-10示出了动态重定位分区分配算法框图。7/23/202326可重定位分区分配可重定位分区的优缺点优点:解决了可变分区分配所引入的“外零头”问题。消除内存碎片，提高内存利用率。缺点:提高硬件成本，紧凑时花费ＣＰＵ时间。7/23/202327连续分配方式单一连续分配固定分区分配动态分区分配可重定位分区分配对换（Swapping）7/23/2023284.2.5对换(Swapping)对换的引入

所谓“对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存。对换是提高内存利用率的有效措施如果对换是以整个进程为单位，称为“整体对换”或“进程对换”如果对换是以“页”或“段”为单位进行的，则称为“页面对换”或“分段对换”，又统称为“部分对换”7/23/2023294.2.5对换(Swapping)为了实现进程对换，系统必须能实现以下三方面的功能：（1）对换空间的管理；（2）进程的换出；（3）进程的换入。7/23/2023304.4

基本分页存储管理方式连续分配方式会形成许多“碎片”，通过“紧凑”方法将碎片拼接成可用的大块空间，但须为此付出很大开销。根据离散分配时所用基本单位的不同，又可把离散分配方式分以下三种：

1、分页存储管理

2、分段存储管理

3、段页式存储管理7/23/2023314.4

基本分页存储管理方式在分页存储管理的方式中，如果不具备页面对换功能，则称为基本的（纯）分页管理方式，它不具有支持实现虚拟存储器的功能，它要求把每个作业全部装入内存后方能运行。7/23/202332基本分页存储管理页面与页表地址变换机构两级和多级页表7/23/202333离散分配方式连续分配方式要求为一个进程分配连续的内存空间，会形成许多“碎片”，尽管采用“紧凑”技术可以解决这个问题，但要为移动大量信息花去不少的处理机时间，代价较高如果允许一个进程直接分散地装入到许多不相邻接的分区中，称为离散分配方式离散分配方式有分页存储管理方式和分段存储管理方式分页：把用户程序按逻辑页划分成大小相等的部分，称为页或虚页。从0开始编制页号，页内地址是相对于0编址。7/23/202334页面与页表页面页面和物理块页面：将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并加以编号，从0开始编制页号，页内地址是相对于0编址。物理块：内存按页的大小划分为大小相等的区域，称为物理块（物理页面，页框(frame)，帧），同样加以编号，如0＃块、1＃块等等在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”7/23/202335页面与页表页面页面大小页面的大小应选择的适中，且页面大小应是2的幂，通常为512B~8KB页面若太小虽然可使内存碎片减小，从而减少了内存碎片的总空间，有利于提高内存利用率，但也会使每个进程占用较多的页面，从而导致进程的页表过长，占用大量内存；此外，还会降低页面换进换出的效率如果选择的页面较大虽然可以减少页表的长度，提高页面换进换出的速度，但却又会使页内碎片增大。7/23/202336对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得：例如：其系统的页面大小为1KB，设A=2170B，则由下式可以求得P=，d=。

2.地址结构分页地址中的地址结构如下：页号P位移量W3112110页内地址212=4*2104KB220=210*2101M21222048-1227/23/202337页面与页表例：系统页面大小为1KB，逻辑地址为2170，求页号与页内偏移量页号P=INT[2170/1024]=2页内偏移量d=2170mod1024=122第0页0~1023第1页1024~2047第2页2048~3071表示为(2,122)7/23/202338页面与页表页表分页系统中，将进程的每一页离散地存储在内存的任一物理块中，为每个进程建立一张页面映像表，简称页表

作用：实现页号到物理块号的映射7/23/202339页面与页表页表列出了用户程序的逻辑地址与其在主存中的物理地址间的对应关系。一个页表中包含若干个表目，表目的自然序号对应于用户程序中的页号，表目中的块号是该页对应的物理块号。页表的每一个表目除了包含指向页框的指针外，还包括一个存取控制字段。表目也称为页描述子。7/23/202340页面与页表进程A页表00页号块号1124354859…………程序A00程序A11程序B02程序B13程序A24程序A35程序B26程序B37程序A48内存程序A59程序A0页1页2页3页4页5页n页程序B0页1页2页3页4页5页m页进程B页表02页号块号132637…………7/23/202341基本分页存储管理页面与页表地址变换机构两级和多级页表7/23/202342地址变换机构基本地址变换机构实现从逻辑地址到物理地址的转换，将逻辑地址中的页号转换为内存中的物理块号，通过页表来完成页表的实现寄存器：变换速度快、成本高，适应小型系统。页表驻留在内存：速度较低、成本低，适应大系统。页表大多驻留在内存中，在系统中设置页表寄存器PTR(Page–TableRegister)，在其中存放页表在内存中的始址和页表的长度进程未执行时，页表的始址和页表长度存放在本进程的PCB中，当调度程序调度到某进程时，才将这两个数据装入页表寄存器7/23/202343地址变换机构地址结构例如：32位地址，0~11为偏移量，12~31为页号，最大可以有1M（220）页，每页4KB（212）。页号P偏移量W31121107/23/2023444.3.2地址变换机构1.基本的地址变换机构每个进程对应一页表，其信息（如长度、始址）放在PCB中，执行时将其首地址装入页表寄存器。当进程要访问某个进程逻辑地址中的数据时，分为页号和页内地址两部分；如果页号大于或等于页表长度，则表示本次所访问的地址已经超越进程的地址空间。7/23/202345地址变换机构7/23/2023462.具有快表的地址变换机构由于页表是存放在内存中的，这使CPU每次要存取一个数据时，都要两次访问内存。

第一次是访问内存中的页表，从中找到该页的物理块号，将此块号与页内偏移量W拼接以形成物理地址。

第二次访问内存时，才是从第一步所得地址中获得所需数据（或向此地址中写入数据），并将此页号与高速缓存中的所有页码进行比较。7/23/202347地址变换机构具有快表的地址变换机构由于页表是存放在内存中，因此每次CPU存取一个数据要两次访问内存为提高地址变换速度，在地址变换机构中增设一个具有并行查询能力的高速缓冲寄存器，又称为“联想寄存器”（AssociativeMemory）或“快表”，用以存放当前访问的那些页表项快表通常可存放16-512个表项，如果设计得当，命中率可达90％以上7/23/202348地址变换机构页表寄存器页表始址页表长度＞页号页内地址＋逻辑地址L越界中断块号b页表页号页号输入寄存器块号bb快表d物理地址具有快表的地址变换机构7/23/202349基本分页存储管理页面与页表地址变换机构两级和多级页表7/23/202350两级和多级页表两级和多级页表

现代的大多数计算机系统，都支持非常大的逻辑地址空间(232~264)。在这样的环境下，页表就变得非常大，要占用相当大的内存空间例如，对于一个具有32位逻辑地址空间的分页系统，若规定页面大小为4KB即212B，则在每个进程页表中的页表项可达1M(220)个之多。若每个表项占用4个字节(32bit)，故每个进程仅仅其页表就要占用4MB的内存空间，而且还要求是连续的页号P偏移量W3112110232/212=22032/8=44*1M=4M7/23/202351两级和多级页表可以采用这样两个方法来解决这一问题采用离散分配方式来解决难以找到一块连续的大内存空间的问题只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入7/23/202352两级和多级页表两级页表(Two-LevelPageTable)

可利用将页表分页，并离散地将各个页面分别存放在不同的物理块中，同样要为离散分配的页表再建立一张页表，称为外层页表（OuterPageTable），每个页表项中记录了页表页面的物理块号210=1024210=1024212=4KB210=1024=1K210=1024=1K212=4*1024=4K7/23/202353两级和多级页表101110780121742n第0页页表146…012…1023第1页页表11411501…1023外部页表01234567……1141151468第n页页表1468012…1023内存空间两级页表结构每个物理块为4KB，恰好放一个1页页表（1024个项，每项4BYTE），共需1024个这样的块7/23/202354两级和多级页表具有两级页表的地址变换机构外部页号P1P2外部页内地址页内地址d逻辑地址+外部页表寄存器外部页表+db页表页表物理地址……7/23/202355两级和多级页表多级页表对于32位的机器，采用两级页表结构是合适的；但对于64位的机器，如果页面大小仍采用4KB即212B，那么还剩下52位，假定仍按物理块的大小(212位)来划分页表，则将余下的42位用于外层页号。此时在外层页表中可能有4096G个页表项，要占用16384GB的连续内存空间。必须采用多级页表，将外层页表再进行分页，也是将各分页离散地装入到不相邻接的物理块中，再利用第2级的外层页表来映射它们之间的关系7/23/202356具有64位地址的分页存储管理242=4096G210=1024212=4KB64两级和多级页表对于64位的计算机，如果要求它能支持264(=1844744TB)规模的物理存储空间，则即使是采用三级页表结构也是难以办到的；而在当前的实际应用中也无此必要7/23/202357例某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面对应的物理块号如下表：页号物理块号051102437则逻辑地址0A5C（H）所对应的物理地址为：______7/23/2023580A5C＝0000,1010,0101,1100页号为2，对应块号为4，有：物理地址：0001，0010,0101,1100即：125C页号物理块号0511024377/23/202359第四章存储器管理程序的装入和链接

连续分配方式

基本分页存储管理

基本分段存储管理虚拟存储器的基本概念请求分页存储管理方式页面置换算法请求分段存储管理方式7/23/202360基本分段存储管理分段存储管理方式的引入分段系统的基本原理信息共享段页式存储管理方式7/23/202361基本分段存储管理...0S工作区段[B]主程序段[M]......0EP子程序段[X]0K...CALL[X][E].........CALL[Y][F]CALL[A]1160116N数组[A]12345.........0FL子程序段[Y]不便于信息共享、保护、动态增长和链接7/23/202362分段存储管理方式的引入分页存储管理的主要目的是为了提高内存利用率分段存储管理的主要目的是为了满足用户在编程和使用上的要求分段管理的主要目的方便编程用户作业通常按逻辑关系分若干个段信息共享程序与数据的共享是以信息的逻辑单位为基础信息保护动态增长动态链接7/23/202363基本分段存储管理分段存储管理方式的引入分段系统的基本原理信息共享段页式存储管理方式7/23/202364分段系统的基本原理1.分段分段存储管理方式中，作业的地址空间被分成若干个段(segment)，每个段定义了一组逻辑信息分段地址中的地址具有如下结构分段方式已得到许多编译程序的支持段号段内地址3116150216=26*210=64K216=26*210=64K7/23/202365分段系统的基本原理2.段表在分段式存储管理系统中，为每个分段分配一个连续的分区，而进程中的各个段可以离散地移入内存中的不同的分区中系统为每个进程建立一张段映射表，简称为“段表”每个段在段表中占一个表项，其中记录了该段在内存中的起始地址（又称为“基址”）和段的长度7/23/202366分段系统的基本原理段表

它记录了段号，段的首（地）址和长度之间的关系每一个程序设置一个段表，放在内存,属于进程的现场信息段号012段首址段长度58K20K100K110K260K140K7/23/202367分段系统的基本原理作业空间(MAIN)＝0030K(X)＝1020K(D)＝2015K(S)＝3010K(MAIN)＝030K(X)＝120K(D)＝215K(S)＝310K040K80K120K150K内存空间30K20K15K10K40K80K120K150K段长基址段号段表0123利用段表实现地址映射7/23/202368分段系统的基本原理3.硬件支持系统设置一对寄存器段表始址寄存器用于保存正在运行进程的段表的始址段表长度寄存器用于保存正在运行进程的段表的长度7/23/202369分段系统的基本原理控制寄存器段表始址段表长度＞2100＋段号S越界1K段长600段号01236K4K5002008K9200基址位移量W＋82928K82928692主存物理地址逻辑地址分段系统的地址变换过程7/23/202370段表始址寄存器段表长度寄存器逻辑地址

Cl

Cb+段号S段内地址d比较比较b+d段表S>=Cl快表物理地址lb...Slb地址越界d>=ld>=l地址映射及存储保护机制地址越界地址越界比较S7/23/2023714.分页和分段的主要区别

(1)页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率。或者说，分页仅仅是由于系统管理的需要而不是用户的需要。段则是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。7/23/202372

(2)页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。

(3)分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址；而分段的作业地址空间则是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。7/23/202373分段系统的基本原理分块方式使用碎片长度目的分页存储管理物理分块系统需要对程序员是不可见，使用简单每个进程只有一个内部碎片，大小不超过1页固定提高内存的利用率分段存储管理逻辑分块，大小与信息块有关，满足用户需要对程序员可见，使方便，但难度大每个进程会产生多个外部碎片不确定便于信息保护与共享，方便用户分页和分段的主要区别7/23/202374基本分段存储管理分段存储管理方式的引入分段系统的基本原理信息共享段页式存储管理方式7/23/202375信息共享分段存储的一个优点是易于实现段的共享，即允许若干个进程共享一个或多个分段分页系统中虽然也能实现程序和数据的共享，但远不如分段系统方便可重入代码（ReentrantCode）又称为“纯代码”（PureCode）是一种允许多个进程同时访问的代码。可重入代码是一种不允许任何进程对它进行修改的代码7/23/2023764.4.3信息共享

例如，有一个多用户系统，可同时接纳40个用户，他们都执行一个文本编辑程序。如果文本编辑程序有160KB的代码和另外40KB的数据区，则总共需有8MB的内存空间来支持40个用户。如果160KB的代码是可重入的，则无论在分页系统还是在分段系统中，该代码都能被共享，在内存中只需保留一份文本编辑程序的副本，此时所需的内存空间仅为：

40*40+160=1760KB，而不是8000KB。假定每个页面的大小为4KB，那么，

160KB的代码将占用40个页面，数据区占10个页面。

7/23/202377信息共享ed1ed2…ed40data1…data10进程12122…6061…70页表ed1ed2…ed40data1…data10进程22122…6071…80…ed1ed2…ed4