22操作系统原理第七章 主存管理

17.1主存共享特征——空间分片现代OS区分两类主存：物理主存和逻辑主存物理主存（共享的基础）由0～（m－1）个物理地址组成，是计算机主存单元的真实地址，又称绝对地址或实地址。物理地址的集合对应的空间组成主存空间。逻辑主存由逻辑地址组成，逻辑地址集合对应的空间为程序地址空间。空间分片主存以分片方式共享，分片方式：1.分为大小不等的区域（按区和按段分配）；2.分为大小相等的块（按页分配）27.2主存管理功能为方便用户使用，系统必须为每个用户提供0~n-1的一组逻辑地址（虚地址）。每个逻辑地址在主存当中并没有一个固定的、真实的物理单元与之对应。根据逻辑地址还不能直接到主存中去存取信息，它是一个虚地址或称为相对地址。为了支持多道程序运行，主存管理还必须实现主存分配、主存保护、主存扩充等功能。因此，存储管理的功能可归纳为以下几点：①映射逻辑地址到物理主存地址。②在多用户之间分配物理主存。③对操作系统以及各用户的信息提供保护措施。④扩充逻辑主存区。37.2主存管理功能一、虚拟存储器当系统提供大容量的辅存时，操作系统把主存和辅存一起管理，实现信息的自由移动和覆盖。虚拟存储器将用户的逻辑主存与物理主存分开，这是现代计算机对虚拟的实质性描述。主存空间的分配由系统完成；逻辑地址转换成物理地址是通过地址变换机构自动完成。虚拟存储的核心问题：让程序的访问地址和主存的可用地址相脱离。实现虚拟存储的物质基础：1、主存；2、辅存；3、地址变换机构。47.2主存管理功能二、主存映射1.什么是地址映射作业的相应进程在处理机上运行时，所要访问的指令和数据的实际地址和地址空间中的地址是不同的。这种情况可用图7.1来说明将程序地址空间中使用的逻辑地址变换成主存中的物理地址的过程，称为地址映射。57.2主存管理功能地址映射方式地址变换功能就是要建立虚一实地址间的对应关系。物理存储器的管理办法就直接取决于实现这种对应关系的方式和时刻。编程或编译时确定地址映射关系在程序编写或程序编译时确定虚、实地址之间的对应关系，结果是一个不能浮动的程序模块，其程序地址就是物理地址。6静态地址映射在作业装入过程中随即进行的地址变换方式称为静态重定位或静态地址映射。程序无法在主存中移动，当从辅存中调入主存时必须放到同一位置。动态地址映射在程序执行期间，随着每条指令和数据的访问自动地连续地进行地址映射。7.2主存管理功能77.2主存管理功能动态重定位能满足以下目标具有给用户程序任意分配一个主存区域的能力；为了能更多的容纳用户程序，具有只装入用户程序的部分代码即可投入运行的能力。具有在任何时刻，在主存可用空间中重新分配一个程序的能力；在改变系统装备时，具有不需要重新编程和重新编辑的能力；对于一个用户程序，具有以间断方式分配主存的能力。静态地址映射与动态地址映射的区别87.2主存管理功能三、程序的逻辑组织计算机的主存储器是一个一维存储空间，地址从0开始到上界顺序编号，这是存储器的组织方式。程序的逻辑组织一般可有两种组织方式：1.一维地址结构；所有的程序和数据经编译、连接后成为一个连续的地址空间，确定在线性地址空间中的指令地址或操作数地址只需要一个信息。2.二维地址结构。程序分成若干模块或过程，并把可修改的数据和不可修改的数据分开，则，一个程序可由代码段、数据段、栈段、特别分段等组成确定在线性地址空间中的指令地址或操作数地址需要两个信息：信息所在的分段和该信息在段内的偏移量。97.2主存管理功能四、主存分配在多道程序环境中，主存分配的功能包括：制定分配策略构造分配用的数据结构响应主存分配请求决定用户程序的主存位置并将其装入主存管理存储器策略放置策略：决定主存中放置信息的区域。调入策略：决定信息装入主存的时机。淘汰策略：主存中没有空闲时，决定哪些信息可以从主存中移走。107.2主存管理功能主存区域划分的方式：划分成大小不等的区域按区分配或段式分配采用第一种划分方式。它可以使主存区域可以存放一个作业程序的连续的地址空间（区分配），或存放一个作业的逻辑分段的地址空间（段式系统）。等分成一系列大小相等的块页式系统一般采用这种方法。它将一个作业程序的地址空间划分成一系列页面，然后放置到主存块中去。117.2主存管理功能调入策略对页式系统或非页式系统没有多大区别，而淘汰策略和放置策略在页式和非页式系统中不同，页式系统中页的大小固定，非页式系统处理的信息块大小可变。进行主存分配必须建立相应的数据结构：主存资源信息块（m_rib）、空闲区队列或存储分块表。127.2主存管理功能五、存储保护1.什么是存储保护在多用户环境中，主存储器按区分配给各用户程序使用。为了互不影响，必须由硬件(软件配合)保证每道程序只能在给定的存储区域内活动，这种措施叫做存储保护。2.存储保护方法存储保护的目的：防止用户之间互相干扰。通常的存储保护方法：界地址保护存储键保护：这种方法是为主存的每一页配一个键，称为存储键。访问键赋予每道程序，并保存在该道程序的状态寄存器中。当数据要写入主存的某一页时，访问键要与存储键相比较。若两键相符，则允许访问该页，否则拒绝访问。137.2主存管理功能3.界地址保护(1)上、下界防如何设置上下界寄存器内容如何判断是否越界满足20KB≤D＜24KB允许访问,否则发生越界中断。movr1,[500]123020KB256KB1存储空间24KB下界寄存器20KB上界寄存器24KB147.2主存管理功能(2)基地址、限长防护如何设置基址、限长寄存器内容，如何判断是否越界？满足逻辑地址＜4KB允许访问，否则发生越界中断。movr1,[500]123020KB256KB1存储空间24KB基址寄存器20KB限长寄存器4KB157.3分区存储管理一.动态分区分配1.什么是动态分区分配在处理作业的过程中，建立分区，依用户请求的大小分配分区。作业队列：作业132KB；作业214KB；作业364KB；作业4100KB；作业550KB167.3分区存储管理在动态分区方案中，主存中的作业在开始充入时，只有主存高址区可能有空闲，但当系统运行一段时间后，作业陆续完成时，它们要释放主存区域，在主存中形成一些空闲区。这些区可以被其他作业使用，但由于空闲区和容纳的作业的大小不一定正好相等，因而这样剩余的空闲区域变得更小。当系统运行相当长一段时间后，主存中会出现一些更小的空闲区。为此，可从以下几个方面来讨论分区存储管理技术：①在分区存储管理方案中，如何实现地址映射。②动态分区的分配机构。③分区的分配和回收。④三种最基本的放置策略。2.动态分区的分配、回收过程17动态分区的回收过程0020KB0os作业1作业2作业3作业452KB66KB130KB230KB256KB120KBos作业1作业3作业452KB66KB130KB230KB256KB1作业2完成作业4完成20KBos作业1作业352KB66KB130KB230KB256KB17.3分区存储管理187.3分区存储管理二、分区分配机构1.主存资源信息块在动态分区方法中，描述主存资源的数据结构是主存资源信息块m_rib，结构如下：等待队列指针空闲区队列指针主存分配程序入口指针2.分区描述器和空闲队列主存中的每一个分区都有相应的分区描述器（pd）说明分区的特征信息。flag：为0—空闲区;为1—已分配区size：分区大小next：空闲区—自由主存队列中的勾链字;已分配区—此项为零m_ribpd分配标志flag分区大小size勾链字next192.自由主存队列(或空闲区队列)结构在主存分配中，主要讨论空闲区描述器和空闲区队列。下面是在t时刻的主存分布、空闲区描述器的内容和空闲区队列结构。020KBos作业1作业3作业452KB66KB130KB230KB256KB1主存52KBm-rib014KB230KB026KB空闲区队列结构7.3分区存储管理207.3分区存储管理分区的分配与回收主存分配程序包括分配一个主存块和释放一个主存块这两个函数。当进程需要一个大小为size的主存区域时，可以通过系统服务请求的方式向主存资源信息块m_rib提出申请。其调用命令形式为request（size），调用结果得到分配区域的首地址。当进程释放所占用的主存区时，使用的系统调用为release（baddr），此调用无返回值。1.分配一个主存块当request系统调用执行时，分配主存块函数getmb（）被调用。21getmb算法输入：请求主存大小size输出：分配块的首址baddr{size加上分区描述器的大小得xize1；for（自由主存队列中的每一个空闲块）{if（当前块大小≥size1）break;/*已找到*/}if（自由队列已空）return(0);当前块大小减去size得剩余块大小；if（剩余块门限值）{flag=1;/*建立已分配区描述器*/Next=NULL;}else{修改剩余块大小：/*该块仍留在自由主存队列上*/当前块首址加剩余块大小得分配块首址flag=1;/*建立已分配区描述器*/size=size1;next=NULL;}分配块首址加上描述器大小得baddr；return(baddr);}227.3分区存储管理2.回收一个主存块当执行release系统调用时，回收一个主存块的函数remb（）被调用。主要任务是将首地址为baddr的主存块归还给主存资源信息块。（1）分区收回的原则主要工作是首先检查是否有邻接的空闲区，如有则合并，然后修改有关的分区描述器信息。237.3分区存储管理分区回收的实现该程序的功能是先计算释放分区f的首地址，然后判断这一释放块是否邻接空闲区；若有上邻或者下邻空闲区，则合并成一个新的自由区，并将它插入到自由主队列合适的位置上。算法relmb输入：释放分区首址baddr输出：无{释放分区首址减3得自由块f首址；计算自由块f的末址：首址加大小；For（自由主存队列中每一块）{If(f与当前块f1是上邻){合并为一个自由块f；f1撤消；break;}}For（自由队列中的每一块）{if（f与当前块f2是下邻）{合并为一个自由块f；f1撤消；break;}}f入自由主存队列；}247.3分区存储管理四、几种基本的放置策略选择空闲区的策略，称为放置策略。常用的放置策略：首次匹配(首次适应算法)最佳匹配(最佳适应算法)最坏匹配(最坏适应算法)无论何种策略都应遵循：当分配一个空闲区时，按分配一个主存块的算法进行分配，而放置策略只是描述空闲区队列的排序原则；当回收一个空闲区时，必须按照队列的排序原则，将把空闲区插入到队列适当的位置中以保证队列排序规则不变。257.3分区存储管理1.首次适应算法什么是首次适应算法首次适应算法是将输入的作业放置到主存里第一个足够装入它的可利用的空闲区中。特点：自由主存队列结构--空闲区地址由低到高排序。优点：简单，速度快，尽量利用低地址部分的空闲块，以便在高地址部分形成大的空闲区。作业A18KBos在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1267.3分区存储管理2.最佳适应算法什么是最佳适应算法最佳适应算法是将输入的作业放置到主存中与它所需大小最接近的空闲区中。特点自由主存队列结构--空闲区大小由小到大排序。优点：如果一个作业申请空间的大小正好与某空闲块相等，则该空闲块必被选中，选择最合适的空间，不会去划分更大空间。缺点：尽可能地利用存储器中小的空闲区，而尽量保存大的空闲区。作业A18KBos在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1277.3分区存储管理3.最坏适应算法什么是最坏适应算法最坏适应算法是将输入