第四章存储器管理

1第四章存储器管理

2第四章存储器管理如何对存储器进行有效的管理，不仅影响到存储器的利用率，而且还对系统性能有重大影响。存储器：内存（本章）外存（第六章）3主要内容new存储器的层次结构4.1程序的装入和链接4.2连续分配方式4.3基本分页存储管理方式4.4基本分段存储管理方式4.5虚拟存储器的基本概念4.6请求分页存储管理方式4.7页面置换算法4.8请求分段存储管理方式4本章学习目标了解存储管理的研究对象和目的了解存储管理的基本功能和有关的基本概念掌握分页存储管理和分段存储管理的基本概念掌握请求分页和请求分段存储管理的基本原理New4.1存储器的层次结构1.多级存储器结构2.主存储器与寄存器3.高速缓存与磁盘缓存51.多级存储器结构

寄存器高速缓存内存磁盘缓存磁盘可移动存储器6三层由快到慢寄存器与主存（前四者）由操作系统直接管理，可快速访问，称为可执行存储器。后两者需要通过I/O访问2.主存储器与寄存器1.主存储器容量大小2.寄存器速度与CPU完全协调长度以字为单位，几十至几百个73.高速缓存和磁盘缓存高速缓存局部性原理CPU与内存之间磁盘缓存频繁使用的磁盘数据暂存在内存中的磁盘高速缓存中89预备知识地址空间的概念1．内存空间(物理空间)

内存是由若干个存储单元组成的，每个存储单元的编号称为内存地址(或物理地址)2．逻辑空间经过汇编或编译后形成目标程序是以0为基址顺序进行编址的，目标程序占据的地址空间称为作业的逻辑地址空间。逻辑空间中的地址称为逻辑地址，这是一个相对地址。104.1程序的装入和链接为作业创建进程需将其装入内存。要把程序装入内存，就要对程序进行编译和链接。1.编译由编译程序把源程序翻译成若干个目标模块；2.链接由链接程序把目标模块以及相关的库函数链接在一起，形成完整的装入模块；3.装入由装入程序把装入模块装入内存。114.1.1程序的装入将一个装入模块装入内存时，有三种方式：绝对装入方式可重定位装入方式动态运行时装入方式关键在于将逻辑地址转换为物理地址的时机不同121.绝对装入方式

AbsoluteLoadingMode若编译时知道程序将在内存的(起始)驻留地址，编译程序将产生绝对(物理)地址的目标代码。只适用单道程序环境。装入模块不需再地址转换，直接装入内存。绝对地址，即可在编译或汇编时给出，也可由程序员直接给出。通常在程序中采用符号地址，在编译或汇编时，再将其转换为绝对地址。132.可重定位装入方式

RelocationLoadingMode多道程序环境下，各目标模块的起始地址均从0开始，程序中的其它地址都是相对于起始地址计算的，不是绝对的物理地址，编译程序无法预知目标模块应放于何处。装入时，需根据内存当前的情况，将模块装入到内存的适当位置，存在一个逻辑地址空间到内存物理地址空间的转换过程（即重定位）。142.可重定位装入方式

RelocationLoadingMode逻辑地址与实际装入内存的物理地址会不同。Load1,2500的作用是把2500单元中的数据送至寄存器1。在装入时，指令的地址会由原来的1000，变为11000，取数地址2500也会变为12500。该例中，在装入时对目标程序中指令和数据的地址修改过程称为重定位。该地址变换是在装入时一次完成的，不再改变，故称为静态重定位。153.动态运行时装入方式

DynamicRun-timeLoading把程序装入内存后，并不立即把装入模块中的逻辑地址转换为物理地址，仍是相对地址。逻辑地址到物理地址的转换直到程序真正运行时才进行。不仅允许装入模块装入到内存中的任何位置，而且允许程序在运行时在内存中移动。（动态重定位分区分配）164.1.2程序的链接根据链接时间的不同，可分为：静态链接装入时动态链接运行时动态链接关键在于进行链接的时机171.静态链接方式

StaticLinking在程序运行之前把各目标模块及库函数链接成一个完整的装入模块，以后不再拆开。装配时需解决两个问题：(1)对相对地址进行修改。(2)变换外部符号。18模块ABC在链接前其内部地址均是相对于起始地址0而言的。链接成一个装入模块后，BC的首地址分别变成了L和L+M，这就需要修改BC中的相对地址，将其全部加上L或L+M；对于ABC各模块中所使用的外部调用符号，也都需进行变换，CALLB需变换为JSLL。192.装入时动态链接

Load-timeDynamicLinking编译的目标模块在装入内存时，边装入边链接。即在装入一个目标模块时，若发生一个外部模块调用，将引起装入程序去找出相应的外部目标模块，并将它装入内存，还需修改目标模块中的相对地址。202.装入时动态链接

Load-timeDynamicLinking优点:VS静态链接

1.便于修改和更新

各目标模块分开存放，便于修改或更新。静态链接要修改或更新时，需重新打开装入模块，低效。

2.便于实现对目标模块的共享

可将一个目标模块链接到几个应用模块，实现多个应用程序对该模块的共享。静态链接，每个应用模块都必须含有该目标模块的完整拷贝，无法共享。213.运行时动态链接

Run-timeDynamicLinking把对某些模块的链接推迟到执行时进行。在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并链接到调用者模块上。优点：本次执行不需要的模块不链接。可加快装入过程，而且节省内存空间。224.1程序的装入和链接小结程序的装入绝对装入方式可重定位装入方式动态运行时装入方式程序的链接静态链接方式装入时动态链接运行时动态链接234.2连续分配方式

连续分配方式，指为一个用户程序分配一个连续的内存空间。4.2.1单一连续分区分配4.2.2固定分区分配4.2.3动态分区分配4.2.4动态重定位分区分配4.2.5对换(Swapping)244.2.1单一连续分区分配1.内存划分

(1)系统区仅提供给OS使用，通常为内存中的低址部分

(2)用户区单一分区，除系统区外的全部内存空间，只提供给用户使用2.适用环境只适用于单用户、单任务环境？254.2.2固定分区分配最早使用的一种可运行多道程序的存储管理方式。将内存空间划分为若干个固定大小的区域，在每个分区中可以装入一道作业，当内存中划分成几个分区时，便允许几道作业并发运行；当有一个空闲分区时，便可从外存的后备队列中，选择一个适当大小的作业装入该分区；当该作业结束时，又可从后备队列中找出另一个作业调入该分区。划分分区内存分配261.划分分区的方法1.分区大小相等 使所有的内存分区大小相等。适用于利用一台计算机去控制多个相同对象的场合。缺乏灵活性。2.分区大小不等 将内存区分为大小不等的多块，灵活性稍好，可根据程序的大小为之分配适当的分区。272.内存分配把分区按大小排队，并建立一个分区使用表。分区表中记录各分区的起始地址、大小和状态。分配内存时，检索分区表，如果存在大小合适且未分配的分区，就把其分配给相应的程序，然后置“已分配”标志；若未找到大小足够的分区，则拒绝为之分配内存。282.内存分配分区大小固定，灵活性仍不足，会产生内存碎片；在某些用于控制相同对象的场合仍有一定应用。作业2：30K作业1：112K294.2.3动态分区分配动态分区分配是根据进程的实际需要，动态地为之分配内存空间。又称为可变分区分配。示意图30可变分区内存使用示意图314.2.3动态分区分配三个问题分区分配中的数据结构分区分配算法分区分配操作321.分区分配中的数据结构记录内存的使用情况，为分配提供依据。(1)空闲分区表 在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。每个空闲分区占一个表目，表目中包括分区序号、分区始址及分区的大小等数据项。331.分区分配中的数据结构(2)空闲分区链 每个分区的起始部分，设置用于链接各分区的前向指针；在分区尾部设置一后向指针。通过前、后向链接指针，可将所有的空闲分区链接成一个双向链。前后向指针，大小，状态342.分区分配算法按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。常用的三种分配算法：首次适应算法循环适应算法最佳适应算法35(1)首次适应算法空闲分区以地址递增的次序链接。分配时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区；然后根据作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。优点：倾向于利用内存中低址的空闲区，保留了高址部分的大空闲区，为以后到达的大作业分配大的内存空间创造了条件。 缺点：低址不断被划分，会产生大量的碎片；每次从低址开始查找，会增加查找可用空间的开销。36(1)首次适应算法图中采用的空闲分区链按地址由小到大的顺序对空闲分区进行组织，开始指向以40k为首址的空闲分区（其大小为46k，下一个空闲分区为始址为118k）。作业5大小为36k37(2)循环首次适应算法分配时，不每次均从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到第一个能满足要求的空闲分区，并从中划出一块与请求的大小相等的内存空间分配给作业。需设置一起始查寻指针，以指示下一次起始查寻的空闲分区，并采用循环查找方式。即如果最后一个(链尾)空闲分区，其大小仍不能满足要求，应返回到第一个空闲分区，比较其大小是否满足要求。找到后，应立即调整起始查寻指针。优点：空闲分区分布均更均匀，减少了查找空闲分区的开销，但会导致缺乏大的空闲分区。38(3)最佳适应算法每次为作业分配内存时，总是把既能满足要求，又是最小的空闲分区分配给作业，避免了“大材小用”。为了加速寻找，要求将所有的空闲区，按其容量大小以递增的顺序形成一空闲区链。这样，第一次找到的满足要求的空闲区，必然是最优的。特点：每次似乎是最佳的，然而在宏观上却不一定。每次分配后所切割下来的剩余部分总是最小的，在存储器中会留下许多这样难以利用的小空闲区。39(3)最佳适应算法图中采用的空闲分区链按容量由小到大的顺序组织403.分区分配操作(分配－回收)1)分配内存 若m.size-u.size<=size，说明多余部分太小，可不再切割，将整个分区分配给请求者；否则，从该分区中划分出与请求的大小相等的内存空间分配出去，余下的部分仍留在空闲分区链或空闲分区表中。最后，将分配区的首址返回给调用者。m.size空闲分区大小u.size用户作业大小413.分区分配操作2)回收内存当一个进程（或程序）释放其所占内存区时，系统将首先检查回收区是否与其它空闲区相邻，若相邻则合并成一个空闲区，否则，将回收区插入空闲分区表（或空闲分区链）中的适当位置。回收情况：A.只有前邻空闲区B.只有后邻空闲区C.既有前邻空闲区又有后邻空闲区D.没有邻接空闲区根据不同情况，A、B、C有不同的合并策略。42回收内存示意图A.将R合并到f1，f1.addr；f1.size+R.size->f1.size

B.将f2

合并到R

，R.addr；f2.size+R.size->f2.size

C.f1、R、f2合并到f1，f1.addr；f1.size+R.size+f2.size->f1.size；撤消f2空闲区表项D.R作为一个新空闲区，插入到空闲区表（链）的适当位置。434.2.4动态重定位分区分配1.动态重定位的引入2.动态重定位的实现3.动态重定位分区分配算法441.动态重定位的引入为了充分利用内存碎片，可利用“紧凑”操作把多个碎片处理为一个比较大的分区，以便利用。经过紧凑后的某些用户程序在内存中的位置发生了变化，此时需对程序和数据的地址加以修改（变换），即需要进行重定位。452.动态重定位的实现采用动态运行时装入方式，地址转换推迟到程序指令真正要执行时进行。为避免影响速度，必须有硬件地址变换机构的支持（重定位寄存器），用它来存放程序在内存中的起始地址。程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。地址变换过程是在程序执行期间，随着对每条指令和数据的访问而自动进行的，故称为动态重定位。当系统对内存进行了“紧凑”，而使若干程序从内存的某处移至另一处时，不需对程序做任何修改，只要用该程序的新起始地址，去置换原来的起始地址即可。462.动态重定位的实现473.动态重定位分区分配算法与动态分区分配算法基本相同，差别仅在于：增加了紧凑功能，在找不到足够大的空闲分区来满足用户需求时进行紧凑。483.动态重定位分区分配算法优点：解决了动态分区分配所引入的“内存零头”问题。消除内存碎片，提高内存利用率。缺点：提高硬件成本，紧凑时花费CPU时间。49动态重定位VS静态重定位静态重定位:当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换。动态重定位:在程序运行过程中要访问数据时再进行地址变换。由地址变换机构进行的地址变换，硬件上需要重定位寄存器的支持。

动态重定位分区分配VS动态分区分配 相对而言，前者具有紧凑功能，需要重定位寄存器支持504.2.5对换(Swapping)1.对换的引入把内存中暂时不能运行的进程或暂时不用的程序和数据，换出到外存，而把已具备运行条件的进程或进程所需要的程序和数据，换入内存，使其投入运行(从而提高内存利用率)。如果对换以整个进程为单位，称之为“整体对换”或“进程对换”。目的是为了解决内存紧张问题 如果对换以“页”或“段”为单位，则称之为“页面对换”或“分段对换”。目的是为了支持虚拟存储系统此小节仅介绍进程对换。为了进程对换，需三方面功能：对换空间的管理、进程的换出及换入。512.对换空间的管理把外存分为文件区和对换区文件区：用于存放文件；为了提高空间的利用率，对其采用离散分配方式。对换区：用于存放从内存换出的进程；因对换操作频繁，为提高进程换入换出速度，对其采用连续分配方式。

(对换是在内存与外存的对换区之间进行）522.对换空间的管理为了对对换区中的空闲盘块进行管理，在系统中应配置相应的数据结构，以记录外存的使用情况。与内存在动态分区分配方式中所用的数据结构相似，同样可以用空闲分区表或空闲分区链。对换空间的分配与回收，与动态分区分配方式中的内存分配与回收方法雷同。其分配算法可以是首次适应算法、循环首次适应算法或最佳适应算法。533.进程的换出和换入进程换出：选择处于阻塞状态且优先级最低的进程作为换出进程，将其程序和数据传送到外存的对换区上，然后便可回收其所占用的内存空间，并对其PCB作相应修改。进程换入：查找处于“就绪”状态但已换出的进程，将其中换出时间最久的进程作为换入进程，将其换入。544.2连续分配方式小结单一连续分配方式固定分区分配分区使用表动态分区分配首次适应算法循环首次适应算法最佳适应算法动态重定位分区分配“紧凑”动态重定位的实现（重定位寄存器）对换

554.3基本分页存储管理方式引入： 连续分配方式会形成许多“碎片”，虽然可通过“紧凑”方法将碎片拼接成可用的大块空间，但须为此付出较大开销。

?

如果允许将一个进程直接分散地分配到许多不相邻接的分区中，就不必再进行“紧凑”。基于这一思想而产生了离散分配方式，相异于4.2所述连续分配方式。564.3基本分页存储管理方式分段存储管理方式基本单位是段分页存储管理方式基本单位是页基本的分页存储管理方式，要求把每个作业全部装入内存后方能运行。（不具备页面对换功能）4.3.1页面和页表4.3.2地址变换机构4.3.3两级和多级页表574.3.1页面与页表1.页面1)页面和物理块页面：将一个进程的逻辑地址空间分成若干个大小相等的片物理块：内存物理空间分成与页相同大小的若干个存储块分配内存时，可将进程中的若干页(逻辑地址空间)分别装入多个可以不相邻接的块(物理地址空间)中。 “页内碎片”581.页面2)页面大小页面大小应适中，且页面大小应为2的幂，一般为512B~8KB。页面太小，减少了内存碎片，有利于提高内存利用率；但也会导致页面过多，页表过长页面太大，则会导致内存碎片较多592.分页存储的地址结构两部分，前一部分为页号P(220);后一部分为位移量W，即页内地址(212)。从逻辑地址获得页号p和页内偏移d p=INT(A/L) d=[A]MODL A——逻辑地址；L——页大小602.地址结构613.页表各页离散存储在任一物理块，系统需记录各页面对应的物理块。系统为每个进程建立一张页面映射表，简称页表。进程的所有页，依次在页表中有一页表项，其中记录了其对应的物理块号。页表的作用是实现从页号到物理块号的地址映射。查找页表，即可找到每页在内存中的物理块号。62页表的作用

实现从页号到物理块号的地址映射作业每页1K内存每块1K634.3.2地址变换机构功能：完成从逻辑地址（页号+页内地址）到物理地址的转换。(页与物理块的大小完全一致，故)页内地址和内存物理块中的物理地址是一一对应的，无需再转换页号需转换成内存中的物理块号，这也是地址变换机构的实质需做的工作。借助于页表完成。两种实现方法基本的地址变换机构具有快表的地址变换机构641.基本的地址变换机构由于页表项的总数很多，不可能均用寄存器来实现，页表大多驻留在内存中。需设置一个页表寄存器PTR（TableRegister），存放页表在内存的始址和页表的长度。进程未执行时，这两个数据存于进程的PCB中；执行时，才将它们装入PTR。651.基本的地址变换机构地址变换过程：1)分页地址变换机构自动将有效地址分为页号和页内地址两部分，再以页号为索引去检索页表。2)在检索页表前，将页号与页表长度比较，如果越界则产生一越界中断，本次访问失败3)如果未越界，则页表始址+页号*页表项长度得到该页号在页表中的位置，从中可得到该页的物理块号，将之装入物理地址的物理块号部分。4)最后再将有效地址中的页内地址送入物理地址寄存器的块内地址中。66分页系统的地址变换机构67分页系统的地址变换实例逻辑地址为3BADH页面大小为2KB页表寄存器681.基本的地址变换机构一个问题？页表是存放在内存中的，这使CPU每次要存取一个数据时，都要两次访问内存。第一次是访问内存中的页表，从中找到该页的物理块号，将此块号与页内偏移量W拼接以形成物理地址；第二次访问内存时，才是从第一步所得地址中获得所需数据(或向此地址中写入数据)。将使计算机的处理速度降低近1/2。？692.具有快表的地址变换机构增设一个具有并行查寻能力的特殊高速缓冲寄存器，又称为“联想寄存器”(AssociativeMemory)或“快表”，用于存放当前访问的那些页表项。（意味着这些页表项不在存放在内存中）702.具有快表的地址变换机构地址变换过程：在CPU给出有效地址后，由地址变换机构自动地将页号P送入高速缓冲存储器（快表），将此页号与其中的页号进行比较若有相匹配的页号（在快表中），直接读出其所对应的物理块号，并送物理地址寄存器中。若没有匹配的，还需访问内存中的页表。找到后，把对应的物理块号送地址寄存器；也将此页表项存入快表中。但如果快表已满，则将一个老的且已被认为不再需要的页表项换出。712.具有快表的地址变换机构722.具有快表的地址变换机构由于成本，快表不可能做的很大，一般只存放16~512个页表项。但对于中小型作业来说，已有可能把全部页表项放在快表中，但对于大型作业，则只能将其一部分页表项放入其中。从快表中能找到所需页表项的机率，可达90%以上。73练习

例：有一页式系统，其页表存放在主存中：①如果对主存的一次存取需要1.5μs,试问实现一次页面访问的存取时间是多少?②如果系统加有快表,平均命中率为85%,当页表项在快表中时,其查找时间忽略为0,试问此时的存取时间是多少?74练习答：若页表存放在主存中，则要实现一次页面访问需两次访问主存：一次是访问页表，确定所存取页面的物理地址（称为定位）。第二次才根据该地址存取页面数据。■页表在主存的存取访问时间

=1.5*2=3(μs)■增加快表后的存取访问时间

=0.85*1.5+(1-0.85)*2*1.5=1.725(μs)75练习某存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面对应的物理块号如下表：页号物理块号051102437则逻辑地址0A5C（H）所对应的物理地址为：125C76练习0A5C＝0000,1010,0101,1100页号为2，对应块号为4，有：物理地址：0001，0010,0101,1100即：125C774.3.3两级和多级页表引入： 计算机支持的逻辑地址空间非常大(232~264)，每个进程的页表项也非常庞大，需占据大量的连续内存空间，这显然不现实。如何解决？

1.采用离散分配方式－－解决需大量连续内存空间问题

(将页表再次进行分块)

2.只将当前需要的部分页表项调入内存－－使页表需占用的内存减少781.两级页表将页表进行分页，并离散地将各个页面分别存放在不同的物理块中，同时为离散的页表再建立一张页表，称为外层页表，其每个表项记录了页表分页的物理块号。逻辑地址结构如下：791.两级页表页内地址:12位，页面大小为212，4KB外层页内地址:10位，每个页表分页中最多可包含210个页表项（对应210个物理块）外层页号:10位，最多允许210个页表分页80两级页表示意图外层页表的每个表项存放的是某页表分页的在内存中的物理块号页表(分页)的每个表项存放的是某页在内存中的物理块号可利用两级页表，实现逻辑地址到物理地址的转换这里只是物理块号，并不是内存单元的编号比如外层页号为1,外层页内地址也为1,寻址81具有两级页表的地址变换外层页表寄存器，用于存放外层页表的始址d01.以逻辑地址中的外层页号p1，作为外层页表的索引，找到d0和p1对应的表项，从中可知指定页表分页的始址d1(物理块号)；2.以外部页内地址p2，作为指定页内分页的索引，找到d1和p2对应的表项，从中可知该页在内存的物理块号b3.物理块号b与页内地址d，即构成了要访问的内存的物理地址。d0d182如何减少页表所占的内存空间上述离散分配空间的办法只解决了大页表无需大片连续存储空间的问题，并未减少页表所占的内存空间。如何减少？只把当前需要的一些页表项调入内存，以后再根据需要陆续调入其它的。在采用两级页表的情况下，需把外层页表全部调入内存，对于页表分页只需调入需要使用的。 在外层页表的表项中，需增设一个状态位，表示相应的页表分页是否已调入内存。 （请求分页存储，虚拟存储器中再作详细介绍）832.多级页表对于64位机器，若采用两级页表，页内地址12位，外部页内地址10位，这时外部页号会达42位，每个表项占4个字节，就需要244B的连续内存空间。显然无法接受。采用多级页表，将外层页表再进行分页，将各分页离散地装入到不相邻接的物理块中，再利用第2级的外层页表来映射它们之间的关系。844.3基本分页存储管理方式小结页面、物理块与页表分页地址结构：页号＋页内地址地址变换机构基本的地址变换机构具有快表的地址变换机构两级和多级页表854.4基本分段存储管理方式存储管理方式从固定分区到动态分区分配，进而到分页存储管理方式主要是为了提高内存的利用率。提出基本分段存储管理方式主要是为了满足用户（程序员）在编程和使用上的多方面的要求。864.4基本分段存储管理方式4.4.1分段存储管理方式的引入4.4.2分段系统的基本原理4.4.3信息共享4.4.4段页式存储管理方式874.4.1分段存储管理方式的引入为了满足用户和程序的如下需要：

1)方便编程 用户通常将作业按逻辑关系划分为若干段。希望要访问的逻辑地址是由段名和段内偏移量决定。2)信息共享 实现共享是以信息的逻辑单位－段为基础的。为实现段的共享，希望存储管理能与用户程序分段的组织方式相适应。884.4.1分段存储管理方式的引入3)信息保护 对信息的逻辑单位－段进行保护4)动态增长 段在使用过程中可能会不断增长，唯有分段存储可较好解决该问题5)动态链接 动态链接在运行时，只将主程序对应的目标程序段装入内存。在需调用某些段时才将其装入，需要以段作为存储管理的单位。894.4.2分段系统的基本原理1.分段2.段表3.地址变换机构901.分段作业的地址空间被划分为若干个段，每个段用来定义一组逻辑信息，均从0开始编址，并采用一段连续的地址空间。段的长度由相应的逻辑信息组的长度决定，因而各段长度不等。逻辑地址由段号和段内地址组成。912.段表进程的多个段被离散的放入内存不同位置。为了能将物理内存与逻辑段地址对应起来，需为每个进程建立一张段映射表。每个段在表中占有一个表项，记录了该段在内存中的始址和段的长度。进程可通过查找段表，找到每个段对应的内存区，实现从逻辑段到物理内存区的映射。92利用段表实现地址映射933.地址变换机构段表寄存器存放段表始址和段表长度SL。94与分页系统一样，当段表放在内存中时，每访问一个数据，都须访问两次内存。解决方法也类似，增设一个高速缓冲寄存器用于保存最近常用的段表项。954.分页和分段的主要区别分页是出于系统管理的需要，分段是出于用户应用的需要一条指令或一个操作数可能会跨越两个页的分界处，而不会跨越两个段的分界处。页大小是系统固定的，而段大小则通常不固定。逻辑地址表示：分页是一维地址空间，各个模块在链接时组织成同一个地址空间；只利用一个标记符即可表示一个地址。分段是二维地址空间，各个模块在链接时可以每个段组织成一个地址空间；标识地址需给出段名和段内地址。通常段比页大，因而段表比页表短，可以缩短查找时间，提高访问速度。964.4.3信息共享分段系统的突出优点，易于实现段的共享，即允许若干个进程共享一个或多个分段。分页系统也可实现程序和数据的共享，但不如分段系统来得方便。（举例对比）可重入代码：一种允许多个进程同时访问（可被共享）的代码；不允许任何进程对它进行修改。974.4.3信息共享例：多用户系统，可同时接纳40个用户，每个用户均可执行文本编辑程序。文本编辑程序有160KB代码和40KB数据区，若代码为非可重入的，需要8000KB内存空间支持40个用户。如果160KB程序代码为可重入的，则不论在分页还是在分段系统中该代码均可被共享，此时所需内存空间为160+40*40=1760KB。984.4.3信息共享分页系统中：假定每个页面大小为4KB，代码需占用40个页面，数据需占10页面。每个用户进程的页表中均需建立相应的页表项。如图:99ed1ed2…ed40data1…data102122…6061…70…ed1ed2…ed40data1…data10data1…data10进程1进程2页表页表ed1ed2…ed40data1…data102122…6071…80主存分页系统中共享editor，需建立比较复杂的页表021226061707180100分段系统中共享editor示意editordata1editordata2段长基址1608040240段长基址1608040380editordata1…data2进程2进程1在分段系统中，实现共享只需在每个进程的段表中为文本编辑程序代码段设置一个段表项，比分页系统简单的多。101略过：关于共享的进一步说明页式地址是一维的，即每个逻辑地址是一个整数，由硬件将其分成：页号|页内位移,故页号是唯一的，程序段的共享必须用相同页号。如：

call2148—〉call2|100段式地址是二维的，两个数字。各进程的段号未必一致，因此不同的进程可用不同的段号共享同一段。如：

callac1|100进程1：ac1=2；进程2：ac1=41024.4.4段页式存储管理方式分页系统能有效地提高内存利用率，而分段系统则能很好地满足用户需要。？段页式系统1031.基本原理将分段和分页原理结合，先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名。段页式系统中，地址结构由段号、段内页号及页内地址三部分组成。页104利用段表和页表实现地址映射每个作业一张段表，每段一张页表。先查段表，再查该段的页表，才能找到物理块号。再将其与页内地址组合1052.地址变换过程1.利用段表始址d0和段号s来求出该段所对应的段表项在段表中的位置，从中得到该段的页表始址d1；2.利用页表始址d1和段内页号P获得对应页的页表项位置，从中读出该页所在的物理块号P’；3.利用块号P’和页内地址d来构成物理地址。1062.地址变换过程1.利用段表始址和段号来求出该段所对应的段表项在段表中的位置，从中得到该段的页表始址；2.利用页表始址和段内页号P获得对应页的页表项位置，从中读出该页所在的物理块号b；3.利用块号b和页内地址来构成物理地址。1072.地址变换过程段页式系统中，访问数据需三次访问内存。 第一次访问内存中的段表，取得页表始址；第二次访问内存的页表，取得该页的物理块号，并与页内地址一起组成实际的物理地址；第三次从物理地址中取出指令或数据。为了避免每次均需三次访问，可在地址变换机构中增设一个高速缓冲寄存器，将常用的段表和页表存储在高速缓冲中。1084.4基本分段存储管理方式小结分段存储管理方式的引入方便用户分段系统的基本原理分段系统的地址变换过程段表始址+段号->段的基址与段内地址结合->物理地址信息共享分页系统与分段系统的比较段页式存储管理方式段表始址+段号->页表始址与页号结合->页面对应的物理块号与页内地址结合->物理地址1094.5虚拟存储器的基本概念连续分配方式、基本分页、基本分段存储管理方式均需将一个作业全部装入内存后方能运行，这将导致大作业无法运行。解决方法：物理上增加内存容量有一定限制从逻辑上扩充内存容量此即虚拟存储器所要解决的主要问题1104.5虚拟存储器的基本概念4.5.1虚拟存储器的引入4.5.2虚拟存储器的实现方法4.5.3虚拟存储器的特征1114.5.1虚拟存储器的引入1.常规存储器管理方式的特征一次性：作业运行前需一次性全部装入内存这可能导致大作业无法装入并非全部程序和数据都需用到，一次装入，浪费内存驻留性：一旦装入便一直驻留内存直至作业结束不再运行的程序模块仍将占用宝贵的内存资源一次性及驻留性是否是必需的？1124.5.1虚拟存储器的引入2.局部性原理程序执行时的特点：程序执行时，除少部分转移和过程调用指令外，大多仍是顺序执行的。过程调用虽可导致程序由一区域转至另一区域，但调用深度大多不超过5。程序在一段时间内都局部于这些过程的范围内执行。程序中存在循环结构，它们将多次执行程序中对数据结构的处理，往往局限于较小的范围内1134.5.1虚拟存储器的引入2.局部性原理局部性的表现：空间局限性。一段时间内所访问的地址可能集中于一定的范围之内。（程序的顺序执行）时间局限性。某条指令或数据可能被再次执行或访问。（循环操作）根据局部性原理，程序在运行之前没有必要一次性全部装入，也没必要长期驻留内存。1144.5.1虚拟存储器的引入引入虚拟存储器基于局部性原理，程序可仅将需运行的部分页或段装入内存便可开始执行。执行中，如果访问的页段已调入内存便可继续；否则，应利用OS提供的请求调页(段)功能将它们调入内存。若此时内存已满，应利用页(段)置换功能，将暂时不用的调出，腾出地方调入需要的页(段)。这样，便可使一个大的程序在较小的空间中运行;也可使内存中同时装入更多的进程并发执行。1154.5.1虚拟存储器的引入3.虚拟存储器定义具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储系统。实质：以时间换空间，但时间牺牲不大。虚拟大小由内存容量和外存容量之和决定。1164.5.2虚拟存储器的实现方法虚拟存储器是建立在离散分配的存储管理方式基础上的。为什么？虚拟存储器请求调入页面转换若采用连续分配方式，一次性将全部数据调入，无需虚拟存储。实现的两种方式:请求分页请求分段1171.分页请求系统在分页系统的基础上，增加了请求调页功能和页面置换功能。只装入部分页面即可运行，可通过调页和页面置换功能，调入需要的页面，同时将暂不需要的换出。以页为单位置换需硬件：请求分页的页表机制缺页中断机构地址变换机构需软件：实现请求调页的软件实现页面置换的软件1182.请求分段系统在分段系统的基础上，增加了请求调段及分段置换功能。只装入部分段即可运行，可通过调段和段置换功能，调入需要的段，同时将暂不需要的调出。以段为单位置换需硬件：请求分段的段表结构缺段中断机构地址变换机构需软件：请求调段和置换软件1194.5.3虚拟存储器的特征1.离散性：离散分配内存2.多次性：多次装入3.对换性：允许作业运行中进行换进换出4.虚拟性：从逻辑上扩充内存虚拟性以多次性和对换性为基础，而多次性和对换性又必须建立在离散分配的基础上。最本质的特征是离散性，在此基础上又形成了多次性和对换性，所表现出来的最重要的特征是

虚拟性.1204.5虚拟存储器小结虚拟存储器的引入大作业小内存运行局部性原理 具有请求调入功能和置换功能，能从逻辑上扩充内存虚拟存储器的实现方法分页请求系统 请求分段系统虚拟存储器的特征离散性 多次性 对换性 虚拟性1214.6请求分页存储管理方式建立在基本分页基础上，为了支持虚拟存储器功能，而增加了请求调页功能和页面置换功能。每次调入和换出的基本单位是固定长度的页。1224.6请求分页存储管理方式4.6.1请求分页中的硬件支持4.6.2内存分配策略和分配算法4.6.3调页策略1234.6.1请求分页中的硬件支持1.页表机制由于应用程序只是一部分调入内存即只有部分页位于内存中，须在页表中增加若干项，供程序（数据）换进换出时参考。页号物理块号状态位P访问字段A修改位M外存地址P:是否已调入内存A:一段时间内使用的次数或多久未使用M:调入内存后是否修改过1244.6.1请求分页中的硬件支持2.缺页中断机构当访问的页不在内存中时便产生缺页中断，请求OS将其调入。缺页中断具有一般中断的入栈、转中断处理、出栈等过程，但又其特殊性：在指令执行期间产生和处理中断。发现访问的页不在内存即产生；通常是在等到指令执行完毕后。一条指令在执行期间，可能要产生多次中断。（如图）125涉及6次缺页中断的指令页面6543211264.6.1请求分页中的硬件支持3.地址变换机构大致步骤：1)在地址变换时，首先检索快表，试图从中找到要访问的页。如找到，修改其访问位；对于“写”指令，还要设置修改位的值。如未找到，则转3。2)利用页表项中的物理块号和页内地址，形成物理地址，结束。3)查找页表，找到页表项后，判断其状态位P，查看该页是否在内存中。如果在，则将该页写入快表（若快表已满，则应该先调出某个或某些页表项）。如果不在，则产生缺页中断，由OS从外存将该页调入内存。返回1。参图4-241271284.6.2内存分配策略和分配算法三个问题最小物理块数的确定物理块的分配策略物理块的分配算法1291.最小物理块数的确定最小物理块数是指保证进程正常运行所需的最少物理块数。与计算机的硬件机构有关，取决于指令的格式、功能和寻址方式。单地址指令且采用直接寻址方式，最少物理块数为2(指令页面数据页面)单地址指令且采用间接寻址方式，3多字节指令，6（幻灯片125页）1302.物理块的分配策略1)固定分配局部置换2)可变分配全局置换3)可变分配局部置换1312.物理块的分配策略1)固定分配局部置换每个进程分配固定数目的物理块数，在整个运行期间都不改变如果缺页，则只能从该进程在内存的页面中选中一页，进行换出操作，然后再调入一页。特点：为每个进程分配多少页是合适的值难以确定。此外，在对换时会浪费比较多的时间。1322.物理块的分配策略2)可变分配全局置换每个进程预先分配一定数目的物理块，同时OS也保持一个空闲物理块队列。（进程的块数运行时可能会有变化）当缺页时，首先将对OS所占有的空闲块进行分配，从而增加各进程的物理块数。当OS的空闲块全部用完，将引起换出操作。（换出的页可能是任一进程的中的一页）1332.物理块的分配策略3)可变分配局部置换思路：先为进程分配部分物理块运行；系统根据缺页率动态调整各进程占有的物理块数目，使其保持在一个比较低的缺页率状态下（轻微缺页时，仅允许从进程自身的页面中选一页换出再换入需要的；只有频繁缺页时，系统才为其分配附加的物理块）。特点：使大部分进程可以达到比较近似的性能。1343.物理块的分配算法

－－针对固定分配策略平均分配算法将物理块平均分配给各进程未考虑进程本身的大小（页数有多有少）按比例分配算法根据进程大小按比例分配物理块

m为物理块总数,S代表各进程页数之和

b取整，且应大于最小物理块数考虑优先权的分配算法物理块分为两部分：一部分按比例分配；一部分根据各进程优先权分配1354.6.3调页策略1.何时调入页面2.从何处调入页面3.页面调入过程1361.何时调入页面根据将进程运行时所缺页面调入内存的时机预调页策略将那些预计在不久之后便会被访问的页面预先调入内存预测成功率仅约50%请求调页策略在运行中，发现要访问的页面不在内存中，便提出请求，由OS将其调入每次仅能调入一页，增加了磁盘的启动频率，系统开销较大1372.从何处调入页面请求分页系统中外存分两个部分：文件区和对换区。一般应当尽量使用对换区来调入页面。对于不同情况，采用不同的策略：系统有足够的对换空间全部由对换区调入，事先需将有数据从文件区拷贝到对换区系统对换空间不足凡是不会被修改的文件都直接从文件区调入，换出时不必再改动文件区；对于需修改的部分，换出时便调到对换区，需要时再从对换区调入。UNIX的调入方式未运行过的页面均从文件区调入；对于曾经运行过但又被换出的页面放在对换区，以后从对换区调入。1383.页面调入过程

进程需要的页面不在内存，引起缺页中断 中断处理程序保留现场环境，转入缺页中断处理程序

中断处理程序如何调入页面？

1.中断处理程序查找页表，得到对应的外存物理块号。如果内存有空闲，则启动磁盘操作，将所缺的页面读入，并修改页表。否则，即内存无空闲时，转2。

2.执行置换算法，选出要换出的页面（如果该页修改过，应将其写入磁盘）然后将所缺页调入内存，修改相应表项，将其状态位设为"1"，并放入快表。

3.利用修改后的页表，形成物理地址，访问内存数据。1394.6请求分页存储管理方式小结请求分页中的硬件支持页表机制 缺页中断机构 地址变换机构内存分配策略和分配算法最小物理块的确定物理块的分配策略固定分配局部置换可变分配全局置换可变分配局部置换物理块分配算法平均分配按比例分配考虑优先权的分配调页策略何时调入（预调、请求）从何处调入（对换区）页面调入过程（内存是否有空闲）1404.7页面置换算法请求分页存储管理方式，若访问的页面不在内存，且内存已无空闲空间时，需首先从内存中调出一页程序或数据，然后调入。需根据一定的算法来确定将哪个页面调出，此算法即页面置换算法，用来选择需调出的页面。理论目标：减少对换量，具有较低的页面更换频率。应优先将那些以后不再访问或较长时间内不再访问的页面调出。1414.7页面置换算法4.7.1最佳置换算法和先进先出置换算法4.7.2最近最久未使用(LRU)置换算法4.7.3Clock置换算法4.7.4其它置换算法 具体7种1424.7.1最佳置换算法和先进先出

置换算法1.最佳置换算法 理论上的算法，其所选择的被淘汰页将是以后永不使用，或者是最长时间内不再被访问的页。 无法预知页面被访问的次序，无法实现，但可用来评价其它算法。1431.最佳置换算法每次选择最长时间内不再访问的页面调出内存“向后看”缺页次数为6，缺页率6/12＝50%1442.先进先出(FIFO)页面置换算法最早出现的置换算法总是淘汰最先进入内存的页面实现简单，只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个替换指针（总是指向最老的页面）该算法不能保证经常使用的页面不被淘汰，会导致缺页率较高。1452.先进先出(FIFO)页面置换算法每次选择最早进入的页面调出内存缺页次数为9，缺页率9/12＝75%1464.7.2最近最久未使用(LRU)

置换算法1.算法描述LeastRecentlyUsed根据页面调入内存后的使用情况进行决策，利用“最近的过去”作为“最近的将来”的近似，选择最近最久未使用的页面予以淘汰。为每个页面设置一个访问字段，记录一个页面自上次被访问以来所经历的时间t。1471.LRU算法描述每次选择最近最久未使用的页面调出内存“向前看”缺页次数为7，缺页率7/12＝58.3%1482.LRU置换算法的硬件支持LRU算法为了记录哪一页是最近最久未使用的页面，需要以下两类硬件之一支持寄存器栈1491)寄存器为每个在内存中的页面配置一个n位移位寄存器，R=Rn-1Rn-2Rn-3…R2R1R0定时将所有寄存器右移一位（其值将会减小）；当进程访问某页时，便将该页相应寄存器的最高位Rn-1置1（其值将会增大）。最久未访问的页面对应的寄存器的值肯定最小，据此可找到要淘汰的页面。1501)寄存器1512)栈利用一个特殊的栈来记录页面的使用次序当进程访问某页时，将其从栈中移出压入“栈顶”；换出时，将“栈底”换出。这样可以保证：栈顶总是最新被访问页面的页号，而栈底则是最近最久未使用页面的页号。1522)栈进程访问页面的序列为：

4,7,0,7,1,0,1,2,1,2,6栈的变化情况访问6时缺页将栈底换出1534.7.3Clock置换算法LRU算法较好，但硬件要求较高，在实际应用中多采用其近似算法，Clock算法是其中一种。1.简单的Clock置换算法2.改进型Clock置换算法1541.简单的Clock置换算法内存中所有页面通过链接指针形成一个循环队列每页有一个使用访问位(usebit)，若该页被访问则置其usebit=1。缺页置换时采用一个指针，从当前指针位置开始按地址依次检查各页：寻找usebit=0的页面作为被置换页指针经过的userbit=1的页都修改userbit=0,暂不换出最后指针停留在被置换页的下一个页。1551.简单的Clock置换算法1562.改进型Clock置换算法该算法中，除考虑页面的最近使用情况外，还须再增加一个因素－－置换代价。在页面换出时，如果该页修改过，便须将它重新写回磁盘，相对于未修改过的页面，其置换代价就高。1572.改进型Clock置换算法选择页面时，尽量选择既未使用又没有修改的页面。页面（访问位A，修改位M）有四种不同情形：1类(A=0,M=0）既未访问，又没有修改，最佳淘汰页2类(A=0,M=1）最近未访问，但已被修改，效率低的淘汰页3类(A=1,M=0）被访问，但没有修改，可能再次被访问4类(A=1,M=1）既被访问，又有修改 淘汰页优先选择前两类，实在没有才考虑后两类1582.改进型Clock置换算法执行过程：（1）指针从当前位置开始，开始第一轮扫描循环队列，寻找未访问且没有修改过的页面（第1类页面），找到则可换出。（2）如果找不到，则开始第二轮扫描，寻找未访问但修改过的页面（第2类页面），并且每经过一个页面时，将其访问位A设置为0（未访问）。如果找到一个第2类页面，则可换出。（3）如果仍旧未找到合适的换出页面，则此时指针回到初始位置，且所有页面其访问位A置为0。再转回（1）继续工作，这时肯定可以经由前两步找到换出页面。可有效减少磁盘I/O操作，但算法本身开销有所增大1594.7.4其它置换算法1.最少使用(LFU:LeastFrequentlyUsed)置换算法2.页面缓冲算法(PBA:PageBufferingAlgorithm)1601.最少使用置换算法LFU目的：选择到当前时间为止被访问次数最少的页面被置换；实现方法1：每页设置访问计数器，每当页面被访问时，该页面的访问计数器加1；发生缺页中断时，淘汰计数值最小的页面；因页面访问次数可能极多，要求计数器容量极大，此法不可行。实现方法2：类似于LRU算法，每个页面设立n位移位寄存器：被访问时左边最高位置1，定期右移并且最高位补0，这样，在最近一段时间内时用最少的页面将是ΣRi最小的页。1612.页面缓冲算法PBA对FIFO算法的发展，通过被置换页面的缓冲，有机会找回刚被置换的页面；被置换页面的选择和处理：由操作系统中专门的页面置换进程，用FIFO算法选择被置换页，把被置换的页面放入内存中的两个链表（空闲页面链表和已修改页面链表）之一：如果页面未被修改，就将其归入到空闲页面链表的末尾否则将其归入到已修改页面链表。1622.页面缓冲算法这种算法被换出的页面，链接在空闲页面链表和已修改页面链表中，仍留在内存中。当进程再访问时，只需花