操作系统原理教程第3章 存储器管理 本章教学目标 l熟悉存储管理的基本功能l掌握各种存储管理方式下主存分配与回收、地址转换与存储保护、管理特点l熟悉在各种存储管理方式下提高主存利用率的方法 本章主要内容 l3.1 存储器管理概述 l3.2 单用户连续存储管理方式 l3.3 固定分区存储管理方式 l3.4 可变分区存储管理方式 l3.5 页式存储管理方式 l3.6 段式存储管理方式 l3.7 段页式存储管理方式 l3.8 虚拟存储管理方式 3.1 存储器管理概述 l3.1.1 存储器管理的主要任务 l3.1.2 存储器管理的主要功能 l3.1.3 程序的装入与链接 l3.1.4 存储管理方式 3.1.1 存储器管理的主要任务 l存储管理的主要任务是尽可能方便用户和提高主存储器的使用效率，使主存储器在成本、速度和规模之间获得较好的权衡 3.1.2 存储器管理的主要功能 l1．主存空间的分配和回收 l2．地址转换 l3．主存空间的共享与保护 l4．主存空间的扩充 3.1.3 程序的装入与链接 l1．源程序的执行过程 l2．程序的链接 l3．程序的装入 1．源程序的执行过程 l通常要经过编译、链接和装入几个步骤，其控制示意如图3-1所示。
l（1〕编译由编译程序将用户源代码编译成若干个目标模块l（2〕链接由链接程序将编译后形成的目标模块以及它们所需要的库函数，链接在一起，形成一个装入模块l（3〕装入由装入程序将装入模块装入主存的过程 2．程序的链接 l链接程序的功能是将经过编译或汇编后所得到的一组目标模块以及它们所需要的库函数，装配成一个完整的装入模块l实现链接的方法有三种l静态链接：事先进行链接，以后不再拆开的链接方式 l装入时动态链接：用户源程序经编译后所得到的目标模块，是在装入主存时，边装入边链接的 l运行时动态链接：可将某些目标模块的链接，推迟到执行时才进行 3．程序的装入l程序的装入就是把程序装入内存空间l采用三种方式 l（1〕绝对装入方式：是由装入程序根据装入模块中的地址，将程序和数据装入主存 l（2〕可重定位方式 ：是由装入程序根据主存当前的实际使用情况，将装入模块装入到主存适当的地方 l（3〕动态运行时装入方式：动态运行时的装入程序，在把装入模块装入主存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序要真正执行时才进行 3.1.4 存储管理方式l单用户连续存储管理方式 l固定分区存储管理方式 l可变分区存储管理方式 l页式存储管理方式 l段式存储管理方式 l段页式存储管理方式 l虚拟存储管理方式 3.2 单用户连续存储管理方式 l3.2.1 基本原理 l3.2.2 主存空间的分配与回收 l3.2.3 地址转换与存储保护 l3.2.4 管理特点 3.2.1 基本原理 l这是最早出现的一种存储管理方式。
l在主存中仅驻留一道程序，整个用户区为一用户独占当用户作业空间大于用户区时，该作业不能装入l这种分配方式仅能用于单用户、单任务的操作系统中，不能用于多用户系统和单用户多任务系统中 3.2.2 主存空间的分配与回收 l1．主存空间的分配 l采用这种存储管理方式时，主存分为两个分区〔系统区 和用户区），如图3-4所示 l其分配过程是：首先，从作业队列中取出队首作业；判断作业的大小是否大于用户区的大小，若大于则作业不能装入，否则，可以把作业装入用户区它一次只能装入一个作业 l其主存分配流程如图3-5所示 l2．主存空间的回收l作业一旦进入主存，就要等到它结束后才能释放主存，再装入第二个作业即可 3.2.3 地址转换与存储保护 l1．地址转换l2．存储保护 1．地址转换 l它采用静态分配方式 l处理器设置两个寄存器：界限寄存器和重定位寄存器界限寄存器用来存放主存用户区的长度，重定位寄存器用来存放用户区的起始地址 l地址转换过程是：CPU获得的逻辑地址首先与界限寄存器的值比较，若大于界限寄存器的值，产生“地址越界〞中断信号，由相应的中断处理程序处理；若不大于界限寄存器的值，就与重定位寄存器中的基址相加，得到物理地址，对应于主存中的一个存储单元。
l其转换过程如图3-6所示 2．存储保护 l处理器在执行指令时，要检查其逻辑地址是否小于界限寄存器的值，l若小于，则与重定位寄存器中的基址相加，产生物理地址，到主存中去执行l否则，产生一个“地址越界〞中断信号，由操作系统进行处理，以达到存储保护的目的 3.2.4 管理特点l（1〕管理简单它把主存分为两个区，用户区一次只能装入一个完整的作业，且占用一个连续的存储空间它需要很少的软硬件支持，且便于用户了解和使用l（2〕在主存中的作业不必考虑移动的问题，并且主存的回收不需要任何操作l（3〕资源利用率低不管用户区有多大，它一次只能装入一个作业，这样造成了存储空间的浪费，使系统整体资源利用率不高l（4〕这种分配方式不支持虚拟存储器的实现 3.3 固定分区存储管理方式 l3.3.1 基本原理 l3.3.2 主存空间的分配与回收 l3.3.3 地址转换与存储保护 l3.3.4 管理特点l3.3.5 对固定分区存储管理方式的改进 l3.3.6 固定分区存储管理举例 3.3.1 基本原理 l把主存中可分配的用户区域预先划分成若干个固定大小的区域，每一个区域称为一个分区，每个分区中可以装入一个作业，一个作业也只能装入一个分区中，这样可以装入多个作业，使它们并发执行。
当有一个空闲分区时，便可从外存的后备队列中，选择一个适当大小的作业装入该分区；当该作业运行完时，又可从后备队列中选择另一个作业装入该分区 l固定分区存储管理方式是最早使用的一种可运行多道程序的存储管理方式l它仍然要求把作业全部装入主存，且装入一个连续的存储空间 3.3.2 主存空间的分配与回收 l1．采用的数据结构 l2．主存空间的分配 l3．主存空间的回收 1．采用的数据结构 l为了记录各个分区的基本情况和使用情况，方便主存空间的分配与回收操作，设置了一张分区分配表l分区分配表的内容包括：分区序号、起始地址、大小、状态l状态栏的值为“0〞表示分区空闲，可以装入作业；当装入作业后，其值改为作业名，表示这个分区被该作业占有l如表3-1所示 2．主存空间的分配 l在作业分配之前，根据主存分区的划分，在分区分配表填入每个分区的始址、大小，在状态栏中一律填入“0”，表示该分区可用，当作业装入时，填入作业名l当有作业申请主存空间时，主存空间的分配步骤为：l从作业队列中取出队首作业，检查分区分配表，选择状态标志为“0〞的分区，根据作业地址空间的大小与状态标志为“0〞的分区的大小比较，当所有分区长度都不能容纳该作业时，则该作业暂时不能装入，显示主存不足的信息。
l当某一个分区长度能容纳该作业时，则把作业装入该分区，且把作业名填到该分区的状态栏里l然后，再分配下一个作业l主存分配流程如图3-7所示 3．主存空间的回收l当作业运行结束时，根据作业名到分区分配表中进行检查，从状态栏的记录可知该作业占用的分区，把该分区的状态标志置成“0”，表示该分区就空闲了，可以用来装入新的作业 3.3.3 地址转换与存储保护 l1．地址转换 l2．存储保护 1．地址转换 l采用静态重定位方式 l处理器设置两个寄存器：下限寄存器和上限寄存器下限寄存器用来存放分区低地址，即起始地址；上限寄存器用来存放分区的高地址，即末址 l地址转换过程lCPU获得的逻辑地址首先与下限寄存器的值相加，产生物理地址；l然后与上限寄存器的值比较，若大于上限寄存器的值，产生“地址越界〞中断信号，由相应的中断处理程序处理；若不大于界限寄存器的值，得到物理地址就是合法地址，它对应于主存中的一个存储单元l地址转换过程如图3-10所示 2．存储保护l系统设置了一对寄存器，称为“下限寄存器〞和“上限寄存器〞记录当前在CPU中运行作业在主存储器中的下限和上限地址l当处理机执行该作业的指令时必须核对表达式“下限地址<=绝对地址<=上限地址〞是否成立。
l若成立，就执行该指令，否则就产生“地址越界〞中断事件，停止执行该指令l运行的作业在让出处理器时，调度程序选择另一个可运行的作业，同时修改当前运行作业的分区号和下限、上限寄存器的内容，以保证处理器能控制作业在所在的分区内正常运行 3.3.4 管理特点 l（1〕一个作业只能装入一个分区，不能装入两个或多个相邻的分区一个分区只能装入一个作业，当分区大小不能满足作业的要求时，该作业暂时不能装入l（2〕通过对“分区分配表〞的改写，来实现主存的分配与回收作业在执行时，不会改变存储区域，所以采用静态地址重定位方式此方法易于实现，系统开销小l（3〕当分区较大作业较小时，仍然浪费许多主存空间并且分区总数固定，限制了并发执行的作业数目 3.3.5 对固定分区存储管理方式的改进 l一个分区只装入一个作业，分区的其它部分闲置不用，降低了主存的利用率可采用下列算法提高主存的利用率：l（1〕根据经常出现的作业的大小和数量来划分分区，尽可能使各个分区充分利用l（2〕划分分区时按分区的大小顺序排列，低地址部分是较小的分区，高地址部分是较大的分区各分区按从小到大的顺序登记在分区表中l（3〕按作业对主存的需求量排成多个作业队列，一个作业队列对应一个分区，互不借用。
3.3.6 固定分区存储管理举例 l【例3-1】l在某系统中采用固定分区分配管理方式，主存分区〔单位字节〕情况如图3-9〔a〕所示现有大小为1KB、9KB、33KB、121KB的多个作业要求进入主存，试画出它们进入主存后的空间分配情况，并说明主存浪费有多大？ 3.4 可变分区存储管理方式 l3.4.1 基本原理 l3.4.2 主存空间的分配与回收 l3.4.3 地址转换与存储保护 l3.4.4 管理特点 l3.4.5 采用技术 l3.4.6 可变分区存储管理举例 3.4.1 基本原理 l可变分区存储管理方式是在作业要求装入主存时，根据作业的大小动态地划分分区，使分区的大小正好适应作业的要求各分区的大小是不定的，主存中分区的数目也是不定的l可变分区存储管理方式必须解决三个问题：l一是分区分配中所用的数据结构l二是分区的分配算法l三是分区的分配和回收 3.4.2 主存空间的分配与回收 l1．采用的数据结构 l2．主存空间的分配 l3．常用的主存分配算法 l4．主存空间的回收 1．采用的数据结构 l为了实现分区分配，系统中必须配置相应的数据结构，用来记录主存的使用情况，包括空闲分区的情况和使用分区的情况，为作业分配主存空间提供依据。
为此，设置了两个表，即已分分区表和空闲分区表，如表3-2和表3-3所示l① 已分分区表记录主存中已分配作业分区的情况，包括分区序号、起始地址、大小和状态〔作业名）l② 空闲分区表记录主存中空闲分区的情况，包括空闲分区序号、起始地址和大小为了便于处理，一般情况下空闲分区表中的空闲分区记录以地址递增的顺序排列 2．主存空间的分配 l先从小地址分配，再分配大地址空闲分区表中记录的排列也是从小地址向大地址排列的l首次分配时，只有一个空闲区分配的区被收回后，还可以分给其它的作业再分给其它作业时，该分区被分成两部分，一部分被作业占据，另一部分又成为一个较小的分区当小到一定程度时，全部分给该作业l主存的分配过程如下：l首先初始化已分分区表〔0个记录〕和空闲分区表〔1个记录），整个用户区为一个空闲区，在空闲分区表中填入用户区的始址和大小l其次，从作业队列中取出队首作业，在空闲分区表中找一个不小于作业的空闲区，装入作业，在已分分区表中增加一个记录，填上作业所占分区的序号、始址、大小、作业名，并修改空闲分区表相应记录的始址和大小；若找不到一个空闲区，则显示主存不足的信息，删除该作业或把作业放到队尾，等待大的空闲区。
l然后，再分配下一个作业，直到所有作业分配完毕l主存空间的分配流程如图3-12 所示 3．常用的主存分配算法 l（1〕最先适应分配算法〔FF） l（2〕最优适应分配算法(BF) l（3〕最坏适应分配算法〔WF） l三种分配算法的比较 （1〕最先适应分配算法〔FF） l原理l对空闲分区表记录的要求是按地址递增的顺序排列的，每次分配时，总是从第1条记录开始顺序查找空闲分区表，找到第一个能满足作业长度要求的空闲区，分割这个空闲区，一部分分配给作业，另一部分仍为空闲区 l特点l一是分配算法简单；二是容易产生过多的小地址碎片；三是降低了主存空间利用率 l改进l采用循环首次适应算法 （2〕最优适应分配算法(BF) l原理l是按作业要求从所有的空闲分区中挑选一个能满足作业要求的最小空闲区，这样可保证不去分割一个更大的区域，使装入大作业时比较容易得到满足为实现这种算法，把空闲区按长度递增次序登记在空闲区表中，分配时，顺序查找 l特点l一是解决了大作业的分配问题；二是容易产生不可利用的空闲区，降低了主存空间的利用率；三是收回主存时，要按长度递增顺序插入到空闲区表中 （3〕最坏适应分配算法〔WF）l原理l每次分配主存时总是挑选一个最大的空闲区，分割一部分给作业使用，使剩下的部分不至于太小，仍可供使用。
为实现这种算法，把空闲区按长度递减次序登记在空闲区表中，分配时，顺序查找 l特点l一是不会产生过多的碎片；二是影响大作业的分配；三是收回主存时，要按长度递减的顺序插入到空闲区表中 三种分配算法的比较l从搜索速度和回收过程上看：最先适应分配算法〔FF〕具有最佳性能；l从空间利用上看：最先适应分配算法〔FF〕比最优适应分配算法〔BF〕好，最优适应分配算法〔BF〕比最坏适应分配算法〔WF〕要好；最优适应分配算法〔BF〕找到的空闲区是最佳的，但在某些情况下，不一定能提高主存的利用率l最先适应分配算法〔FF〕的另一个优点是尽可能地利用了低地址空间，从而保证高地址有较大的空闲区来放置较大的作业l最坏适应分配算法〔WF〕由于过多的分割大的空闲区，当遇到较大作业申请时，无法满足其申请的可能性较大，该算法对中、小作业比较有利因而，在实际系统中，最先适应分配算法〔FF〕法用得最多 4．主存空间的回收l当一个作业运行结束后，在已分分区表中找到该作业，根据该作业所占主存的始址和大小，去修改空闲分区表相应的记录其修改情况分4种，如图3-13所示〔斜线部分为已被作业占有的主存区域） l（1〕回收的分区前后没有相邻的空闲分区。
在空闲分区表中要增加一条记录，该记录的始址和大小，即为回收分区的始址和大小如图3-13〔a〕所示l（2〕回收分区的前面有相邻的空闲区在空闲分区表中找到这个空闲区〔查找的方法是比较空闲分区的始址＋空闲分区的大小与回收分区的始址是否相等），修改这个空闲区的大小，即加上回收分区的大小，始址不变如图3-13〔b〕所示l（3〕回收分区的后面有相邻的空闲分区在空闲分区表中找到这个空闲区〔查找的方法是回收分区的始址－回收分区的大小与空闲分区的始址比较是否相等），修改这个空闲区的始址和大小始址为回收分区的始址，大小为回收分区的大小与空闲区的大小之和如图3-13〔c〕所示l（4〕回收分区的前后都有相邻的空闲分区在空闲分区表中找到这两个空闲区，修改前面相邻的空闲区的大小，其始址不变大小改为相邻两个空闲区和回收分区的大小之和，然后从空闲分区表中，删除后一个相邻空闲分区的记录如图3-13〔d〕所示l最后，在已分分区表中删除该分区的记录 3.4.3 地址转换与存储保护 l1．地址转换 l2．存储保护 1．地址转换 l采用动态重定位方式装入作业它需要设置硬件地址转换机构：两个专用寄存器，即基址寄存器和限长寄存器，以及一些加法、比较电路。
地址转换步骤如下：l① 当作业占用处理器时，进程调度把该作业所占分区的起始地址送入基址寄存器，把作业所占分区的最大地址送入限长寄存器l② 作业执行过程中，处理器每执行一条指令，都要由硬件的地址转换机构把逻辑地址转换成物理地址l③ 当取出一条指令后，把该指令中的逻辑地址与基址寄存器内容相加得到物理地址，该物理地址必须满足：物理地址<=限长寄存器的值 l基址寄存器和限长寄存器总是存放当前占用处理器的作业所占分区的始址和末址一个作业让出处理器时，应先把这两个寄存器的内容保存到该作业所对应进程的PCB中，然后再把新作业所占分区的始址和末址存入这两个专用寄存器中如图3-14所示 2．存储保护l系统设置了一对寄存器，称为“基址寄存器〞和“限长寄存器〞记录当前在CPU中运行作业在主存中所占分区的始址和末址l当处理机执行该作业的指令时必须核对表达式“始址<=绝对地址<=末址〞是否成立若成立，就执行该指令，否则就产生“地址越界〞中断事件，停止执行该指令l运行的作业在让出处理器时，调度程序选择另一个可运行的作业，同时修改当前运行作业的分区号和基址寄存器、限长寄存器的内容，以保证处理器能控制作业在所在的分区内正常运行。
3.4.4 管理特点 l一是，分区的长度不是预先固定的，而是按作业的实际需求来划分的分区的个数也不是预先确定的，而是由装入的作业数决定的l二是，分区的大小由作业的大小来定，提高了主存的使用效率l三是，在主存分配过程中，会产生许多主存“碎片”主存“碎片〞是指小的无法使用的主存空间使主存空间仍有一定的浪费 3.4.5 采用技术 l为了提高主存空间的利用率，可以采用移动技术和对换技术，来合并空闲区，满足作业的要求，或把暂时不运行的作业从主存中对换到外存上，运行紧迫的作业，然后再把对换到外存上的作业调入主存 l1．移动技术 l2．对换技术 1．移动技术 l将主存中的所有作业进行移动，使它们相邻接这样，原来分散的多个小分区便拼接成一个大分区，从而就可以把作业装入该区l这种通过移动，把多个分散的小分区拼接成大分区的方法被称为“拼接〞或“紧凑”，改变作业在主存中位置的工作称为“挪动”l在移动的时候，需要注意，移动会增加系统开销〔操作系统所占有的系统资源和所需要的处理器的时间称为“系统开销”）l移动是有条件的：当作业不与外围设备交换信息时，可以移动，否则不能移动 2．对换技术l对换是指把主存中暂时不能运行的进程，或暂时不用的程序和数据，换出到外存上，把已具备运行条件的进程，或进程所需要的程序或数据，换入主存的技术。
l对换有两种方式，l如果对换是以整个进程为单位，便称之为“整体对换〞或“进程对换”，这种对换被广泛地应用于分时系统中，其目的是用以解决主存紧张问题，并可进一步提高主存的利用率；l如果对换是以“页〞或“段〞为单位进行，则分别称之为“页面对换〞或“分段对换”，又统称为“部分对换”，这种对换方法是实现请求分页及请求分段式存储器的基础，其目的是为了支持虚拟存储系统 3.4.6 可变分区存储管理举例l【例3-2】l主存有两个空闲区F1、F2如图3-15图〔a〕所示F1为220KB，F2为120KB，另外依次有J1 、J2、J3三个作业请求加载运行，它们的主存需求量分别是40KB、160KB、100KB，试比较最先适应算法、最优适应算法和最坏适应算法的性能l【例3-3】l下表给出了某系统中的空闲分区表，系统采用可变式分区存储管理策略现有以下作业序列：96KB、20KB、200KB若用最先适应算法和最优适应算法解答中的也做相应修改来处理这个作业序列，试问哪一种算法可以满足该作业序列的请求，为什么？ 3.5 页式存储管理方式 l3.5.1 基本原理 l3.5.2 主存空间的分配与回收 l3.5.3 地址转换与存储保护 l3.5.4 对页式存储管理的改进 l3.5.5 管理特点 l3.5.6 页式存储管理举例 3.5.1 基本原理 l将用户作业的地址空间分成若干个大小相同的区域，称为页面或页，并为每个页从“0〞开始编号；l相应地，主存空间也分成与页大小相同的若干个存储块，或称为物理块或页框(frame)，并且采用同样的方式为它们进行编号，从0开始：0块，1块，…，n-1块。
l程序的逻辑地址由页号和页内地址组成，页号的长度决定了分页的多少，页内地址的长度决定了页面的大小l在为作业分配主存时，以块为单位将作业中的若干页分别装入多个可以不相邻接的块中作业执行时根据逻辑地址中的页号找到它所在的块号，再确定当前指令要访问的主存的物理地址l它的地址转换属于动态重定位 3.5.2 主存空间的分配与回收 l1．采用的数据结构 l2．主存空间的分配 l3．主存空间的回收 1．采用的数据结构 l为了实现页式存储管理方式，系统设置了主存分配表、位示图和页表，记录主存空间的使用情况和每个作业的分配情况 l主存分配表：它记录主存中各作业的作业名、页表始址和页表长度，页表长度为页表中的最大序号整个系统设置一个主存分配表，如表3-5所示 l位示图：包括标志位和空闲块数 l页表：系统为每个作业建立一张页面映射表，简称页表指出逻辑地址中的页号与主存块号的对应关系 2．主存空间的分配 l主存空间的分配过程为：l首先，系统要初始化位示图，即把位示图中的标志位全部置为“0”，空闲块数置为主存的块数l其次，在进行主存分配时，从作业队列中取出队首作业，计算该作业的页数，然后，与位示图中的空闲块数比较，若不能满足作业的要求，则作业不能装入，显示主存不足的信息，把该作业放到队尾或删除该作业；若能满足作业的空间要求，则为该作业建立页表，并根据位示图中主存块的状态标志，找出标志为“0〞的那些位，置上占用标志“1”，根据该位在位示图中的字号和位号，利用下列公式可以计算住该页所对应的块号l把作业页装入对应的主存块，并在页表中填入对应的块号。
直到所有作业页全部装入l最后，修改位示图中空闲块数，即原有空闲块数减去本次占用的块数〔页数），并在主存分配表中增加一条记录，登记该作业的作业名、页表始址和页表的长度 3．主存空间的回收l当一个作业执行结束，则应收回该作业所占用的主存块l根据主存分配表中的记录，取出该作业的页表从该作业的页表中取出每一个归还的块号计算出该块在位示图中的位置，将占用标志位清为“0”；l最后，把归还的块数加入到空闲块数中，删除该作业的页表，并把分区分配表中该作业的记录删除 3.5.3 地址转换与存储保护 l1．地址转换 l2．页的共享和保护 1．地址转换 l页式存储管理采用动态重定位方式装入作业 l页表的功能可以由一组专门的寄存器来实现 l在执行检索之前，先将页号与页表长度进行比较，如果页号大于页表长度，则表示本次所访问的地址已超越作业的地址空间这一错误将被系统发现并产生“地址越界〞中断若未出现越界错误，则将页表始址与页号相加，便得到该表项在页表中的位置，可以从中得到该页的物理块号，将块号装入物理地址寄存器中与此同时，再将逻辑地址寄存器中的页内地址，直接送入物理地址寄存器的块内地址字段中经过硬件机制，把物理地址寄存器中的块号和块内地址，转换成物理地址。
这样，便完成了从逻辑地址到物理地址的变换 l页式地址转换过程如图3-18所示 2．页的共享和保护 l（1〕页的共享 l共享的方法是使各自页表中的有关表目指向共享信息的主存块如表3-6所示，页表1所代表作业的第2页与页表2所代表作业的第1页，共享第9块主存空间 l（2〕页的保护 l共享页的保护l不同作业所占空间的保护l逻辑地址转换成物理地址的保护 3.5.4 对页式存储管理的改进 l1. 有快表的地址变换l2．两级页表的地址转换 3.5.5 管理特点 l一是，可以使程序和数据存放在不连续的主存空间，不必象可变分区管理那样通过增加系统开销来解决“碎片〞问题，它有效地解决了“碎片〞多的问题l二是，通过位示图和页表来记录主存的使用情况和每个作业的分配情况，当主存很大，并且作业也很大时，位示图和页表都有可能占用较大的存储空间l另外，它要求有相应的硬件支持，从而增加了系统成本，也增加了系统开销如需要地址变换机构、快表等并且它仍然存在不可利用的空间，如最后一页的部分空间没有放满等它还要求页的大小固定，不能随程序的大小而变，对程序的共享和使用造成了许多困难 3.5.6 页式存储管理举例l【例3-4】l在一个页式存储管理系统中，页面大小为1KB，主存中用户区的起始地址为1000，假定页表如下。
现有一逻辑地址，页号为2，页内地址为20，试设计相应的物理地址，并画图说明地址转换过程l【例3-5】l设一页式存储管理系统，向用户提供逻辑地址空间最大为16页，每页2048字节，主存总共有8个存储块，试问逻辑地址应为多少位？主存空间有多大？l【例3-6】l在一个页式存储管理系统中，某作业的页表如下左表所示已知页面大小为1024字节，用户区的基址为1000，试将逻辑地址1011、2148、3000、4000、5012转换为相应的物理地址 3.6 段式存储管理方式 l3.6.1 基本原理 l3.6.2 主存空间的分配与回收 l3.6.3 地址转换与存储保护 l3.6.4 管理特点 l3.6.5 分页和分段的主要区别 l3.6.6 段式存储管理举例 3.6.1 基本原理 l在段式存储管理方式中，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息 l它以段为单位分配主存，每段分配一个连续的主存空间，但各段之间不要求连续 l供用户使用的逻辑地址为段号+段内地址在装入作业时，用一张段表记录每个分段在主存中的起始地址和长度若装入作业的某段信息找不到足够大的空闲区，可采用移动技术，合并分散的空闲区。
l主存的分配与回收类似于动态分区分配，采用动态重定位 3.6.2 主存空间的分配与回收 l1．采用的数据结构 l2．主存空间的分配 l3．主存空间的回收 1．采用的数据结构 l为了记录主存中空闲分区的始址和大小，以及作业中每个段分配主存的情况，在段式存储管理方式下，设置了空闲分区表、段表和主存分配表l空闲分区表：用于记录主存中空闲区的序号、起始地址和大小，整个主存设置一个 l段表：系统为每个作业建一个段表，用于记录每个作业的每个段在主存中所占分区的起始地址和大小，如表3-8所示 l③ 主存分配表整个系统设置一个主存分配表，用于记录主存中各作业的作业名、段表始址和段表长度，段表长度为段表中的最大序号，如表3-9所示 2．主存空间的分配 l作业分配时，用作业的长度与空闲分区表的所有记录的长度之和进行比较若大于则不能装入否则，可以装入，为该作业创建一个段表l根据作业段的大小在空闲分区表中查找满足其大小的空闲块，把该段装入，该块剩余部分仍作为空闲分区登记在空闲分区表中，并在段表中填入该段的段长和段的起始地址，直至所有段分配完毕l若找不到足够大的空闲分区，可以采用移动技术，合并分散的空闲区后，再装入该作业段。
最后，在主存分配表中，登记该作业段表的起始地址和段表的长度l其主存分配流程如图3-22所示 3．主存空间的回收l当作业运行结束时，根据该作业段表的每一条记录，去修改空闲分区表修改的方式与可变分区回收主存空间相同，根据回收区是否与空闲区相邻，分4种情况处理l删除该作业的段表l删除主存分配表中该作业的记录 3.6.3 地址转换与存储保护 l1．地址转换 l2．段的共享 l3．段的保护 1．地址转换 l在进行地址转换时，系统将逻辑地址中的段号与段表中的段表长度进行比较，l若超过段表长度则表示段号越界，产生“地址越界〞中断信号l若未越界，则根据段表起始地址和段号得到该段在主存中的起始地址l然后，检查段内地址是否超过该段的段长，若超过，则发出“越界〞中断信号若未越界，则把起始地址加上段内地址就得到欲访问主存的物理地址l地址转换过程如图3-23所示 2．段的共享 l在段式管理系统中，段是信息的逻辑单位，而段式系统的一个突出优点是易于实现段的共享l分段的共享是通过两个作业段表中相应表目都指向被共享的同一物理副本来实现l如表3-10中段表1的第1段和段表2的第2段是共享的 3．段的保护l保护主要有两种：l一是，地址越界保护，包括对段号的判断和对段内地址的判断。
l二是，存取控制保护l如表3-11所示 3.6.4 管理特点 l（1〕段长可以根据需要动态增长这样，便于对具有完整逻辑功能的信息段共享，便于实现程序的动态链接l（2〕采用这种管理方式，硬件支持更多，成本较高仍然存在碎片问题，若采用移动技术合并空闲区，会增加系统开销另外，段的大小受主存可用空闲区大小的限制 3.6.5 分页和分段的主要区别 l（1〕页是信息的物理单位，分页是为了实现离散的分配方式，以消减主存“碎片”，提高主存的利用率或者说，分页仅仅是由于系统管理的需要，而不是用户的需要段是信息的逻辑单位，它包含一组意义相对完整的信息分段的目的是为了能更好地满足用户的需要l（2〕页的大小固定且由系统确定，把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而一个系统只能有一种大小的页面段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分l（3〕分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需要利用一个记忆符，即可表示一个地址分段的作业地址空间是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址 3.6.6 段式存储管理举例l【例3-7】 3.7 段页式存储管理方式 l3.7.1 基本原理 l3.7.2 主存空间的分配与回收 l3.7.3 地址转换与存储保护 l3.7.4 管理特点 3.7.1 基本原理 l段页式存储管理方式的基本原理是段式和页式系统工作原理的组合。
l即先把用户程序分成若干个段，并为每个段赋予一个段名，每段可以独立从“0〞编址再把每个段划分成大小相等的若干个页，把主存分成与页大小相同的块l每段分配与其页数相同的主存块，主存块可以连续，也可以不连续 3.7.2 主存空间的分配与回收 l1．采用的数据结构 l2．主存空间的分配 l3．主存空间的回收 1．采用的数据结构 l为了实现段页式存储管理方式，系统设置了位示图、段表和页表，记录主存的使用情况和作业的分配情况其管理层次如图3-25所示 l① 位示图记录主存块的使用情况和空闲块数 l② 段表系统为每个作业配置了一张段表，记录作业段的分配情况 l③ 页表记录每个段内页的分配情况 l④ 主存分配表整个系统设置一个主存分配表，用于记录主存中各作业的作业名、段表始址和段表长度，段表长度为段表中的最大序号 2．主存空间的分配 l作业分配时，首先，根据程序模块划分作业的段，对每个段再划分若干个页，计算该作业所需的所有的总页数，l用作业的总页数与位示图中的空闲块数进行比较若大于空闲块数，则不能装入否则，可以装入l装入时，为该作业创建一个段表，再为每个段创建页表，在段表中填上每个段的段号、页表长度和页表始址；根据作业段的页表中页号，在位示图中查找标志位为“0〞的空闲块，找到后，装入该页，并把标志位由“0〞改为“1”，计算出对应的块号〔计算方法同页式存储管理），填入到相应的页表中。
直至所有段的所有页分配完毕后，把位示图中的空闲块数减去该作业的总页数l最后，在主存分配表中，登记该作业段表的的起始地址和段表长度l其分配过程如图3-26所示 3．主存空间的回收l当作业运行结束时，根据该作业段表每一条记录所对应的页表，去修改位示图中的标志位和空闲块数，把标志位由“1〞改为“0”，空闲块数增加上页数大小最后，删除每段对应的页表，以及该作业的段表 3.7.3 地址转换与存储保护 l1．地址转换 l2．段的共享与保护 1．地址转换 l在进行地址转换时，首先利用段号，将它与段表寄存器中的段长进行比较，若大于段长则产生越界中断否则，利用段表始址和段号在段表中找到相应页表的始址l再利用逻辑地址中的页号，与段表中的页长比较，若页号大于该页表长度，产生越界中断，否则，在页表中找出其对应的块号，再与逻辑地址中的页内地址一起组成物理地址l地址转换如图3-27所示 2．段的共享与保护 l段的共享是通过在各作业的段表中的共享段指向相同的页表始址 l段的保护主要有2种：l一是，地址越界保护它是利用段表寄存器的段表长度与逻辑地址中的段号进行比较，若段号超界，则产生越界中断再利用段表项中的页长与逻辑地址中的页号进行比较，若页号大于页长也产生越界中断。
l二是，存取控制保护同段式存储管理一样，在段表中增加一个权限位，设置存取信息的权限〔读、写、读和写等），若本次操作与标志位权限不符，则由硬件捕获并发出保护性中断，l如表3-12所示 3.7.4 管理特点l一是，根据作业模块把作业分成若干段，再根据页面大小把每一段分成若干页，主存仍然分成与页大小相等的块分配主存时，把作业的每一段的页分配到主存块中l二是，这种分配方式既照顾到了用户共享和使用方便的需求，又考虑到了主存的利用率，提高了系统的性能l三是，这种分配方式的空间浪费要比页式管理的多作业各段的最后一页都有可能浪费一部分空间另外段表和页表占用空间，都比页式和段式的多，这样就增加了系统开销 3.8 虚拟存储管理方式l3.8.1 基本概念 l3.8.2 分页式虚拟存储管理 l3.8.3 分页式虚拟存储管理例题 3.8.1 基本概念 l1．问题的提出 l2．虚拟存储器的定义 l3．虚拟存储器存储的特点 l4．虚拟存储器的实现方法 1．问题的提出 l在程序的某次运行，执行了这部分程序就不会执行另一部分程序 l当把作业全部装入主存后，作业执行时实际上只使用部分信息，甚至有些部分在作业执行的整个过程中都不会被使用到〔局部性原理）。
l是否需要一次性地将作业全部装入？作业是否需要长期地驻留在主存？不少学者已进行了广泛的研究，这些研究结果为虚拟存储器的实现奠定了基础 2．虚拟存储器的定义 l虚拟存储器是指仅把作业的一部分装入主存便可运行作业的存储器系统具体地说，所谓虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对主存容量进行扩充的一种存储器系统实际上，用户所看到的大容量只是一种感觉，是虚的，故而得名虚拟存储器l虚拟存储器逻辑容量由地址寄存器的位数决定的如计算机地址寄存器是24位，地址按单字节编址，则虚拟存储器的容量是224Bl虚拟存储器的运行速度接近于主存速度，而其成本却又接近于外存可见，虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用广泛地应用于各类计算机中 3．虚拟存储器存储的特点 l（1〕离散性离散性是指在主存分配时采用离散分配方式，这是虚拟存储器的基础 l（2〕多次性多次性是指一个作业被分成多次调入主存运行 l（3〕对换性对换性是指允许在作业的运行过程中换进、换出 l（4〕虚拟性虚拟性是指能够从逻辑上扩充主存容量，使用户所看到的主存容量远大于实际主存容量 4．虚拟存储器的实现方法l（1〕分页式虚拟存储管理 l它是在分页式存储管理系统上增加了请求调页功能、页面置换功能所形成的页式虚拟存储管理系统。
l（2〕分段式虚拟存储管理 l它是在分段式存储管理系统上增加了请求调段功能、分段置换功能所形成的段式虚拟存储管理系统 3.8.2 分页式虚拟存储管理 l1．基本原理 l2．采用的数据结构 l3．主存空间的分配与回收 l4．地址转换与存储保护 l5．分配物理块 l6．作业在主存中块数的分配算法 l7．页面置换算法 l8．管理特点 1．基本原理 l它是建立在纯分页基础上的，增加了请求调页功能、页面置换功能所形成的页式虚拟存储管理系统l把作业分成大小相等的若干页，把主存分成与页大小相等的若干块；对每个作业限定分给它的主存块数，先把作业的部分页装入主存的这些块中，在作业运行时再装入所需要的页 2．采用的数据结构 l（1〕位示图 l与页式存储管理相同，主存空间的使用情况仍用位示图表示，它包括标志位和空闲块数 l（2〕页表 l页表用来记录作业的分配情况 l（3〕主存分配表 l主存分配表记录主存中每个作业的作业名、页表始址、页表长度和分配的主存块数，其格式如表3-14所示l（4〕缺页中断机构 l在请求分页系统中，每当所要访问的页面不在主存时，便要产生一次缺页中断，请求操作将所缺的页调入主存。
缺页中断作为中断，它同样需要经历诸如保护CPU环境、分析中断原因、转入缺页中断处理程序进行处理、恢复CPU环境等几个步骤 3．主存空间的分配与回收 l（1〕主存空间的分配 l当给一个作业分配主存时，首先，计算该作业的页数，比较是否“M>位示图中空闲块数”，若大于则该作业暂时不能装入；否则，可以装入一部分，为其建立页表，初始化表中的数据装入过程与页式存储管理方式的一样，只不过是要累计个数，到M个页时，停止装入，修改位示图中空闲块数〔减去调入主存的该作业页数）并在主存分配表中增加一条记录，记录该作业的作业名、页表始址、页表长度和所分得的物理块数l其余页等到程序运行时，访问到该页时再装入l（2〕主存空间的回收 l当作业运行结束时，根据页表去修改位示图，把归还块的占用标志位改为“0”，然后修改空闲块数，增加上M最后，删除该作业的页表和该作业在主存分配表中的记录 4．地址转换与存储保护 l（1〕地址转换 l地址的正常转换与页式存储管理相同〔如图3-18所示） l（2〕存储保护 l其存储保护的方法与页式存储管理的很相似，在此不在赘述 5．分配物理块 l在为作业分配物理块时，将涉及到三个问题：l第一，确定为保证作业正常运行所需要的最少物理块数；l第二，为每个作业分配的物理块，其数目是固定的还是可变的；l第三，对各作业所分配的物理块数，是采取平均分配算法还是根据作业的大小按比例分配等。
6．作业在主存中块数的分配算法 l（1〕平均分配算法 l（2〕按比例分配算法 l（3〕优先权分配算法 7．页面置换算法 l（1〕最佳置换算法 l（2〕先进先出置换算法〔FIFO） l（3〕最近最久未使用算法〔LRU） l（4〕最近最不经常使用调度算法〔LFU） l（5〕最近未使用算法NUR 8．管理特点 l（1〕要运行的作业可以不必全部装入主存，就能运行事先要把作业分成大小相等的“页”，把主存分成与页大小相等的块，先装入一些必须的页，运行时再装入所需要的页l（2〕这样与全部装入主存的存储管理方式相比，可以节省主存空间，增加并发执行的作业个数，提高系统的利用率l（3〕由于运行时，没有把作业全部装入主存，其余作业页是在运行时，利用中断和页面置换算法装入的，这样，增加了程序运行的时间，加大了系统的硬件开销 3.8.3 分页式虚拟存储管理例题l【例3-8】 l【例3-9】 l【例3-10】 本章小结 l存储器管理的主要任务是分配存储器，l主要目的是提高存储器的使用效率它l的主要功能有：存储器的分配与回收、地址转换与保护、主存的扩充 l熟悉和掌握以下基本概念： l逻辑地址、物理地址、地址转换、静态重定位、动态重定位、主存“碎片”、对换技术l熟悉和掌握以下基本知识： l1．连续存储管理方式 2．非连续存储管理方式 l3．虚拟存储管理方式 习 题 l一、单项选择题 l1--20题l二、填空题 l1--15题l三、判断题 l1--10题l四、名词解释题 l1--10题l五、简答题 l1--6题l六、应用题 l1--12题 。