操作系统课件：Chapter-04存储器管理

1存储器管理第四章4.1程序的装入和链接4.2连续分配方式4.3基本分页存储管理方式4.4基本分段存储管理方式4.5虚拟存储器的基本概念4.6请求分页存储管理方式4.7页面置换算法4.8请求分段存储管理方式2存储器分级理想中的存储器：更大、更快、更便宜的非易失性存储器。（本图摘自AndrewS.Tanenbaum：“ModernOperatingSystems”）3程序的装入与链接（1）4程序的装入与链接（2）程序的装入绝对装入方式可重定位方式（静态重定位）动态运行时装入方式（动态重定位）5程序的装入与链接（3）绝对装入方式绝对装入程序按照装入模块中的地址，将程序和数据装入内存。装入模块被装入内存后，由于程序中的逻辑地址和实际内存地址完全相同，故不需要对程序和数据的地址进行修改。6str5[200]

ldrR1,[200]

addR2,R1,3

strR2,[204]str5[200]

ldrR1,[200]

addR2,R1,3

strR2,[204]装入分区程序的装入与链接（4）编译链接intx,y;x=5;y=x+3;源程序0100200300......逻辑地址空间204xy1000......110012001300物理地址空间1204xy7程序的装入与链接（5）可重定位装入方式装入模块装入内存后，装入模块中的所有逻辑地址与实际装入内存的物理地址不同。通常把装入时对目标程序中指令和数据的修改过程称为重定位。通常地址变换一次完成，以后不再改变，故称为静态重定位。8str5[200]

ldrR1,[200]

addR2,R1,3

strR2,[204]装入分区0100200300......逻辑地址空间204程序的装入与链接（6）xy1000......110012001300物理地址空间str5[1200]

ldrR1,[1200]

addR2,R1,3

strR2,[1204]1204xy9程序的装入与链接（7）动态运行时装入方式动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是相对地址。101000200str5[200]

ldrR1,[200]

addR2,R1,3

strR2,[204]装入分区str5[200]

ldrR1,[200]

addR2,R1,3

strR2,[204]程序的装入与链接（8）0100200300......逻辑地址空间204xy1000......110012001300物理地址空间1204xy+基地址寄存器相对地址11程序的装入与链接（9）程序的链接1.静态链接方式(StaticLinking)模块ACALLB;Return;模块BCALLC;Return;模块CReturn;000L-1M-1N-1模块AJSR’L’;Return;模块BJSR’L+M’;Return;模块CReturn;0L-1LL+M-1L+ML+M+N-1变换外部调用符号相对地址发生变化12程序的装入与链接（10）程序的链接2.装入时动态链接(LoadtimeDynamicLinking)用户源程序经编译后所得到的目标模块，是在装入内存时，边装入边链接的。优点：便于软件版本的修改和更新。便于实现目标模块的共享。13程序的装入与链接（11）程序的链接3.运行时动态链接(Run-timeDynamicLinking)这种链接方式是将对某些模块的链接推迟到执行时才执行，亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。14程序的装入与链接（12）静态链接，静态装入15程序的装入与链接（13）静态链接，动态装入16程序的装入与链接（14）动态链接，动态装入17连续分配方式（1）内存分为两个区域：系统区，用户区。每次把一个应用程序装入到用户区运行，由它和操作系统来共享内存。当它运行结束后，操作系统再装入一个新的程序把它覆盖；优点：简单、开销小，易于管理；缺点：每次只能运行一个程序；对那些使用空间较少的程序，造成内存浪费；适合于单用户、单任务的OS。单一连续分配（单道程序内存分配方式）18连续分配方式（2）单一连续分配组织内存的3种简单方式19连续分配方式（3）内存分为两大区域：系统区，用户区。又把用户区划分为若干分区(partition)，分区大小可以相等，也可以不等。一个进程占用一个分区。特点：适合于多道程序系统和分时系统，支持多个程序并发执行；分为两类：固定分区和可变分区。分区存储管理20连续分配方式（4）各个用户分区的个数、位置和大小一旦确定以后，就固定不变。为了满足不同程序的存储需要，各分区的大小可相等，也可不等。分区大小相等：只适合于多个相同程序的并发执行（处理多个类型相同的对象）；分区大小不等：多个小分区、适量的中等分区、少量的大分区；当进程到来时，根据它的大小，把它放置到相应的输入队列当中，等待合适的空闲分区。两种实现方式：多个输入队列和单个输入队列。固定分区存储管理21连续分配方式（5）多个输入队列分区4分区3分区2分区1操作系统700K400K100K0200K800K对于每一个用户分区，都有一个输入队列。当一个新的进程到来时，把它加入到某个输入队

列当中，该输入队列所对应的分区，是能够装下该进程的最小分区。缺点：可能出现小分区的输入队列是满的，而大分区的输入队列却空着（如分区1和分区3的的情形），从而造成资源的浪费。22连续分配方式（6）单个输入队列分区4分区3分区2分区1操作系统700K400K100K0200K800K对于所有的用户分区，只有一个统一的输入队列。当一个新进程到来时，把它加入到该输入队列当中，然后当某个分区空闲时：离队首最近的、

能装入该分区的

进程被选中；搜索整个队列，

选择能装入该分

区的最大进程。23连续分配方式（7）分区号起始地址长度状态进程名数据结构：设置内存分配表内存分配：先放入输入队列，然后采用首次适应算法、最佳适应算法等。内存回收：简单24固定分区的优点：易于实现，开销小。固定分区的缺点：内存利用率不高，内碎片造成很大浪费。所谓内碎片，即进程所占用分区之内的未被利用的空间。分区的总数固定，限制了并发执行的程序个数，不够灵活。因此，人们又提出了可变分区（动态分区）的存储管理技术。连续分配方式（8）25连续分配方式（9）分区不是预先划分好的固定区域，而是动态创建的。系统生成后，操作系统会占用内存的一部分（一般在内存地址低端），其余空间为一个完整的大空闲区。当一个程序要求装入内存运行时，系统从这个空闲区中划分一块分配给它，当程序完成后释放所占用的存储区。可变分区存储管理26操作系统128K01024K128K空闲区896K操作系统128K01024K128K空闲区576K进程1320K448K连续分配方式（10）27操作系统128K01024K128K空闲区352K进程1320K448K进程2224K672K操作系统128K01024K128K空闲区64K进程1320K448K进程2224K672K进程3288K960K空闲区224K连续分配方式（11）28操作系统128K01024K128K空闲区64K进程1320K448K进程4128K672K进程3288K960K576K空闲区96K空闲区320K

可变分区的特点：在可变分区当中，分区的个

数、位置和大小都是随进程

的进出而动态变化的，非常

灵活，避免了在固定分区中

因分区大小不当所造成的内

碎片，提高了内存利用率。有外碎片，即各个占用分区

之间难以利用的空闲分区

（通常是小空闲分区）；使得内存的分配、回收和管

理更为复杂。连续分配方式（12）29连续分配方式（13）动态分区分配的实现内存管理的数据结构内存的分配算法内存的回收方法碎片问题30连续分配方式（14）动态分区的数据结构（1）空闲分区表用于为内存中每个尚未分配出去的分区设置一个表项，每个分区的表项包含分区序号、分区始址及分区大小等表目。（2）空闲分区链为了实现对空闲分区的分配和链接，在每个分区的起始部分，设置一些用于控制分区分配的信息，以及用于链接各分区的前向指针；再分区尾部则设置一后向指针；然后，通过前、后向指针将所有的分区链接成一个双向链。31连续分配方式（15）分区链表EDCBA05814182026293250占35空68占414占218空620占326占X329空空闲起始长度占用32连续分配方式（16）分区分配算法：当一个新的进程来到时，需为它寻找某个空闲分区，其大小必须大于或等于该进程的要求。若是大于要求，则将该分区分割成两个分区，其中一个分区为要求的大小并标记为“占用”，而另一个分区为余下部分并标记为“空闲”。分区的先后次序通常是从内存低端到高端。分区分配算法主要有：首次适应算法、循环首次适应、最佳适应算法、最坏适应算法。分区分配算法33连续分配方式（17）（1）首次适应算法：(FF)将空白区按存贮顺序链成一个队列，用一指针指向队首分配时将找到的第一个满足要求的空白区分配给它。指针10k60k90k20k有四块空白区(从低地址

高地址)，来了一个作业需分配19k内存。34连续分配方式（18）指针10k60k90k20k41k在高地址空白区中保持较大空白区(每次从10k开始分配寻找)。解：FF特点：35连续分配方式（19）(2)循环首次适应(Nextfit:NF)将空白区组成环状队列，按循环顺序寻找空白区。(与FF区别，头指针从低地址开始向高地址循环移动)12指针移动使得小空白区均匀分布，易于与其它空白区合并。NF特点：36连续分配方式（20）(3)最佳适应算法(Bestfit:BF)将空白区按大小排成队列，寻找时总是以最小的空白区开始，找到第一个合适的分区指针10k60k90k20k例：来一个19k的作业37连续分配方式（21）

最佳地利用分区；

开销比较大，并不是最好算法。指针10k20k60k90k1k特点：解：3816K16K16KWorstFit地址低端地址高端16K新进程连

续

分

配

方

式

（22）39连续分配方式（23）40连续分配方式（24）分区回收算法：当一个进程运行结束，释放它所占用的分区后，需要将相邻的几个空闲分区合并为一个大的空闲分区。具体来说，可分以下四种情况：在分区回收后，可以很方便地更新分区链表。41进程X空闲区50占35占68占(a)进程A进程B空50占35占68空(b)进程A进程X空闲区50占95空进程A空闲区50空35占68空(d)空闲区进程X空闲区140空空闲区(c)略…连

续

分

配

方

式

（25）42连续分配方式（26）动态重定位的引入经过一段时间的分配与回收后，内存中存在着很多不连续的很小的空闲分区（外碎片）。当一个新进程到来时，这些小的空闲区都不足以满足分配要求，但其总和满足分配要求。这就是（外）碎片问题。可重定位分区分配43连续分配方式（27）内存紧凑（Compaction）：把所有的进程尽可能地往地址低端移动，相应的，那些空闲的小分区就会往地址的高端移动，从而形成一个大的空闲区。所有进程的移动需要大量的CPU时间；如何解决程序移动后，地址的重定位问题？可重定位分区分配44连续分配方式（28）可重定位分区分配45连续分配方式（29）动态重定位的实现46连续分配方式（30）无法分配返回空闲分区总和>=u.size进行紧凑形成连续空闲区返回分区号及首址找到大于u.size的可用区否?修改有关的数据结构简缩空闲分区链（表）请求分配u.size分区动态分区分配修改有关的数据结构NNYY47连续分配方式（31）内存中某些进程，等待事件发生而被阻塞，占用了大量内存空间。许多作业在外存等待，因无内存无法进入内存运行。所谓对换，就是系统根据需要把主存中暂时不运行的某个(或某些)作业部分或全部移到外存，而把外存中的某个(或某些)作业移到相应的主存区，并使其投入运行。包括“进程对换”，“页面对换”，“分段对换”对换（Swapping）48连续分配方式（32）49连续分配方式（33）通常把外存分为文件区和对换区。文件区：存放文件，需要提高文件存储空间利用率，离散分配方式对换区：用于存放从内存换出的进程，需要提高进程换入和换出的速度，连续分配方式对外存空闲盘块管理：空闲分区表，空闲分区链分配算法与分配过程同其他连续分配方式对换空间的管理50连续分配方式（34）Bitmap管理空闲内存单元5个进程，3个空闲区bitmap分区链表51分页存储管理（1）引入：分区存储管理方案的一个特性是连续性，即系统对每个程序都分配一片连续的内存区域。连续性导致了碎片问题（内碎片和外碎片），降低了内存资源的利用率。对于内碎片，难以避免；对于外碎片，用于合并碎片的内存紧缩技术又需要花费大量的CPU时间。52分页存储管理（2）页式存储管理方案，目的是打破存储分配的连续性，使得一个程序的逻辑地址空间可以分布在若干个离散的内存块上，从而达到充分利用内存，提高内存利用率的目的。把物理内存划分为许多个固定大小的内存块，称为物理页面，或页框（pageframe）；把逻辑地址空间划分为大小相同的块，称为逻辑页面，或简称页面（page）；分页原理53分页存储管理（3）页面大小为2n，一般在512字节到8K字节之间；（小了会如何，大了会如何？）对某特定机器，其地址结构是一定的。这种划分是由系统自动完成的，对用户是透明的。当一个用户程序装入内存时，以页面为单位进行分配。若要运行一个大小为n个页面的程序，需要有n个空闲的物理页面把它装入，这些页面不必是连续的。分页原理54分页存储管理（4）为各页加以编号，从0开始，如第0页、第1页等；同样为内存块加以编号，如0＃块、1＃块等等。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”。分页原理55分页存储管理（5）操作系统操作系统进程2第0页进程2第1页进程1第0页进程1第1页进程2第2页进程3第0页0K1K2K3K4K5K6K7K8K9K10K0K1K2K进程1地址空间进程2地址空间0K1K2K3K0K1K进程3地址空间内存56分页存储管理（6）用于存储管理的数据结构是什么？当一个进程到来时，如何给它分配内存？当一个进程运行结束，释放它所占用的内存空间后，如何回收内存？当一个进程被加载到内存以后，它如何正确运行（地址重定位）？分页存储面临的问题57分页存储管理（7）如何用一种数据结构描述逻辑页面和物理页面的关系？58分页存储管理（8）页表：系统为每一个进程都建立了一个页表，页表给出了逻辑页面号和具体内存块号（物理页面号）之间的对应关系。逻辑页号内存块号页表01n-159分页存储管理（9）60分页存储管理（10）0310/10/10/10/10/1017……空闲页数……位示图页面位示图：如图是8个32位的字表示256个页面61分页存储管理（11）内存的分配与回收算法与物理页面表的具体实现方法有关。这里以位示图为例。内存的分配：计算一个进程所需要的页面数N，并查看位示图，看是否还有N个空闲页面；若有，则申请一个页表，其长度为N，并把页表的起始地址填入PCB；分配N个空闲的物理页面，将其编号填入页表；修改位示图（0→1，空闲页面数－N）内存分配与回收62分页存储管理（12）内存的回收：当一个进程运行结束，释放它所占用的内存空间后，需要对这些物理页面进行回收。对于每一个物理页面，根据它的编号计算出它在位示图当中的相应位置，并将相应位的值从1改成0；修改位示图中的空闲页面数：加上N。内存分配与回收63分页存储管理（13）why地址映射？一个进程的各个连续的逻辑页面，被分散地装入到内存的各个物理页面当中，在这种情形下，怎样才能保证程序能够正确地运行？必须采用动态的地址映射方法，在程序运行过程中，将逻辑地址转换为物理地址，以确保数据访问和指令运行的正确性。地址映射64分页存储管理（14）MMU-内存管理单元65分页存储管理（15）16个4KB页面情况下MMU的内部操作66分页存储管理（16）把逻辑地址划分为两部分：逻辑页面号和页内偏移地址。这种划分是由系统自动完成的，对用户是透明的。由于页面的大小一般为2的整数次幂，因此，地址的高位部分即为页号，低位部分即为页内偏移地址。页面编号从0开始，页内偏移地址也是相对于0编址。逻辑地址划分页号页内地址67分页存储管理（17）页面大小1KB，虚地址是3BADH11101110101101页号0EH,偏移3ADH如果页面大小是2KB呢？11101110101101页号07H,偏移3ADH地址映射:16进制68分页存储管理（18）页号＝虚地址/页大小位移量＝虚地址%页大小例如：假设页面大小为2KB，计算逻辑地址7145和3412的逻辑页面号和页内偏移地址。地址映射:10进制页号：7145/2048＝3页内偏移：7145%2048＝1001页号：3412/2048＝1页内偏移：3412%2048＝136469分页存储管理（19）页表保存在内存当中；设置一个页表基地址寄存器（tablebaseregister，PTBR），用来指向页表的起始地址；设置一个页表长度寄存器（tablelengthregister，PTLR），用来指示页表的大小；页表的具体实现70分页存储管理（20）71分页存储管理（21）72分页存储管理（22）在现有的方案中，每一次访问内存（数据/指令）时，都要做两次访问内存的工作，第一次是读页表，第二次是真正访问数据/指令。这样，降低了存取速度，将会影响整个系统的使用效率。为缩短页表的查找时间，可以采用一种特殊的快速查找硬件：TLB(TranslationLookasideBuffer)或称associativememory,用来存放那些最常用的页表项。Speeduppaging-TLB73分页存储管理（23）先后74分页存储管理（24）TLB的内容75分页存储管理（25）优点：没有外碎片，内碎片的大小不超过页面的大小；一个程序不必连续存放；便于管理；缺点：程序必须全部装入内存；系统必须为每个进程维护一张页表。分页存储的特点76分页存储管理（26）WindowsNT等使用x86的CPU的32位地址，使用4KB的页面(212)。问题：可以使用的逻辑地址？页面有多少？如果页表项4byte，页表有多大？这样的页表可以放主存吗？两级和多级页表77分页存储管理（27）32bitaddresswith2pagetablefieldsTwo-levelpagetables78分页存储管理（28）两级页表的地址映射方法79分页存储管理（29）多级页表通过二级页表的地址映射访问主存存取数据需要三次访问主存(一次页目录，一次页表，最后是数据所在物理地址)，所需时间是原来的三倍。当然对64位的地址，也可组织成三级、四级页表，但性能的影响是不可忽视的。80分段存储管理（1）页式存储管理（和分区存储管理）只有一个逻辑地址空间，即一维的线性连续空间，从0到某个最大的逻辑地址。但是从程序员的角度来说，一个程序是由一组模块（片段）所组成的，每个片段是一个逻辑单元，如：主程序、函数、全局变量、栈、符号表等。为了体现这些逻辑单元的独立性，便于它们的共享、保护和修改，人们提出了段式存储管理的方法。81分段存储管理（2）对于程序当中的每一个逻辑单元，设立一个完全独立的地址空间，称为“段”。在每个段的内部，是一维的线性连续地址，从0一直到某个最大的地址。每个段的大小一般是不相等的，它所包含的内容也是不一样的；对于物理内存来说，采用可变分区（动态分区）的管理方法；当一个程序需要装入内存时，以段为单位进行分配，把每一个段装入到一个内存分区当中，这些内存分区不必是连续的。82用户空间1324子函数主函数栈符号表分段存储管理（3）1423物理内存空间0n83分段存储管理（4）[MAIN]loadYD12345C段号段长主存始址01k6k15004k23008k32009200SB段表LOAD1,11001234501k05000300020010002k4k45966k7k8k8292849294009200[x][A][B]分段映射存储[MAIN]=084分段存储管理（5）在段式存储管理当中，为了指明用户空间当中的某个地址，程序必须给出一个二元的地址组：〈段号，段内偏移地址〉段表：系统为每一个进程都建立了一个段表，它给出了进程当中的每一个段与它所对应的内存分区之间的映射关系。具体实现4004300400630010001400段长度所对应内存分区的起始地址段号01285分段存储管理（6）具体实现段表保存在内存当中设置一个段表基地址寄存器（Segment-tablebaseregister，STBR），用来指向内存当中段表的起始地址；设置一个段表长度寄存器（Segment-tablelengthregister，STLR），用来指示段表的大小，即程序当中的段的个数；86分段存储管理（7）段式地址映射87分段存储管理（8）01231K6K6004K5008K2009200段号段长基址>+段表始址段表长度

2100控制寄存器段号S位移量W有效地址+8292物理地址越界主存8K82928692分段系统的地址变换过程88分段存储管理（9）优点：程序通过分段来划分多个模块，每个模块可以分别编写和编译，可以针对不同类型的段采取不同的保护，可以按段为单位来进行共享；一个程序不必连续存放，没有内碎片；便于改变进程所占用空间的大小。缺点：程序必须全部装入内存、外碎片等。分段的优缺点89分段存储管理（10）分页是出于系统管理的需要，分段是出于用户应用的需要。页式：为减少碎片，提高内存的使用效率，因此把内存划分为许多个固定大小的物理页面。相应的，把逻辑地址空间也划分为大小相同的逻辑页面；段式：为了实现程序当中的各个逻辑单元的独立性，便于它们的共享、保护和修改，从而为每一个逻辑单元设立一个单独的“段”。相应的，在物理内存的分配和回收上，采用可变分区的存储管理方法。分页与分段对比90分段存储管理（11）程序员对所采用的存储管理技术的关注：页式：对于程序员而言，页式存储管理完全是透明的，不必关心。对逻辑地址空间的分页，是由系统自动完成的，每个页面当中的内容，也是偶然的。程序员甚至不知道分页的发生。段式：程序员知道各个逻辑单元的存在，因此可以对它们进行不同的处理。页大小是系统固定的，而段大小则通常不固定；通常段比页大，因此段表比页表短，可以缩短查找时间，提高访问速度；91分段存储管理（12）从逻辑地址的表示来看：页式：逻辑地址是一维的线性连续地址，各模块在链接时必须组织成同一个地址空间；段式：逻辑地址是二维的，即段号和段内的偏移地址，各个模块在链接时可以为每个段组织一个地址空间。从退化形式来看：页式：如果页面比较大，能装下整个程序，那么就退化为一种固定分区的方法；段式：如果段的个数为1，那么就退化为一种可变分区的方法。92分段存储管理（13）例如：一个多用户系统，可同时接纳40个用户。他们同时使用文本编辑器编辑文本。如果程序占用160KB，而每人编辑的内容占用40KB。如果程序是可重入的，则所需的空间为160＋40×40＝1760KB。可重入代码：允许多个进程同时访问的代码。此代码不允许任何进程对之进行修改。分页与分段信息共享方面的表现93分段存储管理（14）分页系统中共享editor的示意图94分段存储管理（15）分段系统中共享editor的示意图95段页式存储管理方式（1）段式存储和页式存储各有特点：段式存储管理为用户提供了一个二维的逻辑地址空间，可以满足程序和信息的逻辑分段要求，反映了程序的逻辑结构，有利于段的共享、保护和动态增长；页式存储管理的特征是等分内存，它有效地克服了碎片问题，提高了内存的利用率。为了保持页式在存储管理上的优点和段式在逻辑上的优点，人们又提出了段页式存储管理技术。96段页式存储管理方式（2）基本思想：先把程序划分为段，然后在段内分页。逻辑地址：内存划分：按页式存储管理方案内存分配：以页面为单位进行分配页内地址页号段内地址段号97段页式存储管理方式（3）作业地址空间和地址结构98段页式存储管理方式（4）段表：记录了每一段的页表起始地址和页表长度，而不是该段所在内存分区的起始地址。页表：记录了逻辑页面号与物理页面号之间的对应关系。（每一段有一个，一个程序可能有多个页表）需要的硬件支持：段表基地址寄存器（STBR）和段表长度寄存器（STLR）。具体实现99段页式存储管理方式（5）利用段表和页表实现地址映射100段页式存储管理方式（6）101虚拟存储器概念（1）如果是程序太大，超过了内存的容量，可以采用覆盖（overlay）技术，只把需要的指令和数据保存在内存当中；如果是程序太多，超过了内存的容量，可以采用交换（swapping）技术，把暂时不能执行的程序送到外存中；虚拟内存以前的技术102虚拟存储器概念（2）其目标是在较小的可用内存中运行较大的程序。常用于多道程序系统，与分区存储管理配合使用。原理：把程序按照其自身的逻辑结构，划分为若干个功能上相对独立的程序模块，那些不会同时执行的模块共享同一块内存区域，按时间先后来运行。覆盖技术103虚拟存储器概念（3）将程序的必要部分（常用功能）的代码和数据常驻内存；可选部分（不常用功能）在其他程序模块中实现,平时存放在外存中，在需要用到时才装入内存；不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖，即这些模块共用一个分区。覆盖技术104程序X的常驻区

A（20K）A20KE20KF40KC30KB50KD30K程序X的调用结构覆盖区0（50K）覆盖区1（40K）

CB

F

E

D总共：190K总共：110K

A虚拟存储器概念（4）覆盖技术105虚拟存储器概念（5）缺点：由程序员来把一个大的程序划分为若干个小的功能模块，并确定各个模块之间的覆盖关系，费时费力，增加了编程的复杂度；覆盖模块从外存装入内存，实际上是以时间延长来换取空间节省。覆盖技术106虚拟存储器概念（6）引入：多个进程并发运行，可将暂时不能运行的进程送到外存，从而获得空闲内存空间来装入新进程，或读入保存在外存中而目前到达就绪状态的进程。交换单位为整个进程的地址空间。常用于多道程序系统或小型分时系统，与分区存储管理配合使用；进程暂时不能运行的可能原因：处于阻塞状态，低优先级（确保高优先级进程执行）；交换技术107虚拟存储器概念（7）交换技术108虚拟存储器概念（8）交换技术需注意的问题交换时机的确定：何时需要发生交换？只当内存空间不够或有不够的危险时换出；交换区的大小：必须足够大以存放所有用户进程的所有内存映像的拷贝；必须能对这些内存映像进行直接存取；程序换入时的重定位：换出后再换入的内存位置一定要在原来的位置上吗？最好采用动态地址映射的方法。109虚拟存储器概念（9）交换技术需注意的问题在内存不够用的情形下，可以采用覆盖技术和交换技术，但是：覆盖技术：需要程序员自己把整个程序划分为若干个小的功能模块，并确定各个模块之间的覆盖关系，增加了程序员的负担;交换技术：以进程作为交换的单位，需要把进程的整个地址空间都换进换出，增加了处理器的开销。解决之道：虚拟存储管理技术。110虚拟存储器概念（10）象覆盖技术那样，不是把程序的所有内容都放在内存中，因而能够运行比当前的空闲内存空间还要大的程序。但做得更好，由系统自动来完成，无须程序员的干涉；象交换技术那样，能够实现进程在内存与外存之间的交换，因而获得更多的空闲内存空间。但做得更好，只对进程的部分内容在内存和外存之间进行交换。虚拟存储集中了覆盖和交换的优点111虚拟存储器概念（11）局部性原理(principleoflocality)：指程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。这可以表现为：时间局部性：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内；空间局部性：当前指令和邻近的几条指令，当前访问的数据和邻近的几个数据都集中在一个较小区域内。112虚拟存储器概念（12）程序在执行时，大部分是顺序执行的指令，少部分是转移和过程调用指令；过程调用的嵌套深度一般只有几层（递归除外），因此执行的范围不超过这组嵌套的过程；程序中存在相当多的循环结构，它们由少量指令组成，而被多次执行；程序中存在相当多对一定数据结构的操作，如数组操作，往往局限在较小范围内。局部性原理的具体表现113虚拟存储器概念（13）程序的局部性原理表明，从理论上来说，虚拟存储技术是能够实现的，而且在实现了以后应该是能够取得一个满意的效果的。114虚拟存储器概念（14）根据局部性原理，只需将用户进程的部分实体装入内存，通过局部实体之间的内外存交换，仅将进程当前需要执行的部分实体存于内存，且一进程的内存空间不必连续。虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存进行扩充的一种存储器系统。虚拟存储器定义115虚拟存储器概念（15）虚拟存储器建立在离散分配的存储器管理方式基础之上分页请求系统它是在分页系统的基础上，增加了请求调页功能，页面置换功能所形成的页式虚拟存储系统。分段请求系统这是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。116虚拟存储器概念（16）多次性-多次调入内存对换性-作业在运行中换进、换出虚拟性-逻辑上扩充容量117请求分页存储管理（1）当一个用户程序要调入内存运行时，不是将该程序的所有页面都装入内存，而是只装入部分的页面，就可启动程序运行。在运行的过程中，如果发现要运行的程序或要访问数据不在内存，则向系统发出缺页中断请求，系统在处理这个中断时，将外存中相应的页面调入内存，使得该程序能够继续运行。请求分页的思路118请求分页存储管理（2）物理页号驻留位保护位修改位访问位逻辑页号i请求分页系统的页表项119请求分页存储管理（3）驻留位：表示该页是在内存还是在外存。如果该位等于1，表示该页位于内存当中，即该页表项是有效的，可以使用；如果该位等于0，表示该页当前还在外存当中，如果访问该页表项，将导致缺页中断；保护位：表示允许对该页做何种类型的访问，如只读、可读写、可执行等；120请求分页存储管理（4）修改位：表明此页在内存中是否被修改过。当系统回收该物理页面时，根据此位来决定是否把它的内容写回外存；访问位：如果该页面被访问过（包括读操作或写操作），则设置此位。用于页面置换算法。121请求分页存储管理（5）16位的逻辑地址，从0到64K。物理内存只有32K。页面大小为4K。X表示驻留位为0。1、movreg,02、movreg,32780会有什么样的结果？1、movreg,81922、32780/4k=8

第8页尚未读入内存

缺页中断122请求分页存储管理（6）每当用户程序所要访问的页面不在内存时，产生一缺页中断，请求OS将所缺之页调入内存。与一般中断的区别(1)指令执行期间产生和处理(2)一条指令可能产生多次缺页中断缺页中断机构123请求分页存储管理（7）涉及6次缺页中断的指令124请求分页存储管理（8）1、如果在内存中有空闲的物理页面，则分配一页，设为f，然后转第4步；否则转第2步；2、采用某种页面置换算法，选择一个将被替换的物理页面f，它所对应的逻辑页面为p‘。如果该页在内存期间被修改过，则需把它写回外存；缺页中断过程125请求分页存储管理（9）对p‘所对应的页表项进行修改，把驻留位置为0；将需要访问的页面p’装入到物理页面f当中，并修改p‘所对应的页表项的内容，把驻留位置为1，把物理页面号设置为f；重新运行被中断的指令。缺页中断过程126请求分页存储管理（10）请求分页系统的地址变换127请求分页存储管理（11）1.最小物理块数的确定最小物理块数是指能保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时，进程将无法运行。——与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式内存分配策略和分配算法128请求分页存储管理（12）2.物理块的分配策略在请求分页系统中，可采取两种内存分配策略，即固定和可变分配策略。在进行置换时，也可采取两种策略，即全局置换和局部置换。于是可组合出以下三种适用的策略。固定分配局部置换可变分配全局置换可变分配局部置换内存分配策略和分配算法129请求分页存储管理（13）3.物理块分配算法1)平均分配算法这是将系统中所有可供分配的物理块，平均分配给各个进程。例如，当系统中有100个物理块，有5个进程在运行时，每个进程可分得20个物理块。内存分配策略和分配算法130请求分页存储管理（14）2)按比例分配算法如果系统中共有n个进程，每个进程的页面数为Si，则系统中各进程页面数的总和为：又假定系统中可用的物理块总数为m，则每个进程所能分到的物理块数为bi，将有：B应该取整，它必须大于最小物理块数。内存分配策略和分配算法131请求分页存储管理（15）3)考虑优先权的分配算法在实际应用中，为了照顾到重要的、紧迫的作业能尽快地完成，应为它分配较多的内存空间。通常采取的方法是把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。在有的系统中，如重要的实时控制系统，则可能是完全按优先权来为各进程分配其物理块的。内存分配策略和分配算法132请求分页存储管理（16）1、何时调入页面1）预调页策略：将那些预计在不久之后便会被访问的程序或数据所在的页面，预先调入内存。2）请求调页策略：发现要访问的页面不在内存，请求OS调入。调页策略133请求分页存储管理（17）1、何时调入页面1）预调页策略：将那些预计在不久之后便会被访问的程序或数据所在的页面，预先调入内存。2）请求调页策略：发现要访问的页面不在内存，请求OS调入。调页策略134请求分页存储管理（18）2.从何处调入页面在请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。由于对换区是采用连续分配方式，而文件区是采用离散分配方式，故对换区的磁盘I/O速度比文件区的高。这样，每当发生缺页请求时，系统应从何处将缺页调入内存，可分成如下三种情况：(1)系统拥有足够的对换区空间(2)系统缺少足够的对换区空间(3)UNIX方式调页策略135请求分页存储管理（19）3.页面调入过程（见126页）注意快表（TLB）与页面置换的作用调页策略136页面置换算法（1）功能：当缺页中断发生，需要调入新的页面而内存已满时，选择内存当中哪个物理页面被置换。目标：尽可能地减少页面的换进换出次数（即缺页中断的次数）。具体来说，把未来不再使用的或短期内较少使用的页面换出，通常只能在局部性原理指导下依据过去的统计数据来进行预测；页面锁定(framelocking)：用于描述必须常驻内存的操作系统的关键部分或时间关键(time-critical)的应用进程。实现的方法是：在页表中添加锁定标志位(lockbit)。137页面置换算法（2）最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。最优置换算法（Optimal）138页面置换算法（3）假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1139页面置换算法（4）这只是一种理想情况，在实际系统中是无法实现的，因为操作系统无从知道每一个页面要等待多长时间以后才会再次被访问。可用作其他算法的性能评价的依据（在一个模拟器上运行某个程序，并记录每一次的页面访问情况，在第二遍运行时即可使用最优算法）。140页面置换算法（5）基本思路：选择在内存中驻留时间最长的页面并淘汰之。具体来说，系统维护着一个链表，记录了所有位于内存当中的逻辑页面。从链表的排列顺序来看，链首页面的驻留时间最长，链尾页面的驻留时间最短。当发生一个缺页中断时，把链首页面淘汰出局，并把新的页面添加到链表的末尾。性能较差，调出的页面有可能是经常要访问的页面，并且有Belady异常现象。先进先出置换算法（FIFO）141页面置换算法（6）假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1142页面置换算法（7）Belady'sAnomaly143页面置换算法（8）基本思路：当一个缺页中断发生时，选择最久未使用的那个页面，并淘汰之。它是对最优页面置换算法的一个近似，其依据是程序的局部性原理，即在最近一小段时间（最近几条指令）内，如果某些页面被频繁地访问，那么在将来的一小段时间内，它们还可能会再一次被频繁地访问。反过来说，如果在过去某些页面长时间未被访问，那么在将来它们还可能会长时间地得不到访问。最近最久未使用置换算法(LRU)144页面置换算法（9）假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1145页面置换算法（10）为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为LRU算法的硬件支持R=Rn-1Rn-2Rn-3

…R2R1R0

146页面置换算法（11）LRU算法的硬件支持-寄存器147页面置换算法（12）LRU算法的硬件支持-栈148页面置换算法（13）为每页设置一位访问位，再将内存中的所有页面都通过链接指针链成一个循环队列。置换算法在选择一页淘汰时，只须检查其访问位，如果是0，就选择该页换出；若为1，则重新将它复0，暂不换出给该页第二次驻留内存的机会。Clock置换算法149页面置换算法（14）为每页设置一位访问位，再将内存中的所有页面都通过链接指针链成一个循环队列。置换算法在选择一页淘汰时，只须检查其访问位，如果是0，就选择该页换出；若为1，则重新将它复0，暂不换出给该页第二次驻留内存的机会。当检查到队列中最后一个页面时，若访问位仍为1，再返回队首检查第一个页面。Clock置换算法150页面置换算法（15）001100110001页面访问位页面置换前000000110001页面置换后M151页面置换算法（16）152页面置换算法（17）主要的不同在于增加了一修改位M（访问位A）页面可分为4种类型：A=0,M=0:最近未访问，未修改，最佳淘汰页A=0,M=1:最近未访问，已修改，不是很好的淘汰页A=1,M=0:最近已访问，未修改，可能再次被访问A=1,M=1:最近已访问，已修改，可能再次被访问Clock置换算法改进版153页面置换算法（18）算法的执行过程如下：（A代表访问位，M代表修改位）1：寻找A=0且M=0的页面，找到则淘汰，算法结束；否则donothing2：寻找A=0且M=1的页面，找到则淘汰，算法结束；对扫描的所有页面访问位置0。3：goto1Clock置换算法改进版154请求分段存储管理（1）段表段名段长段的基址存取方式访问字段A修改位M存在位P增补位外存始址155请求分段存储管理（2）请求分段系统中的中断处理过程156请求分段存储管理（3）请求分段系统的地址变换过程157分段的共享与保护（1）共享段表158分段的共享与保护（2）1、共享进程记数count：用于记录有多少各进程需要共享该分段。2、存取控制字段：用于控制进程的存取权限。3、段号：不同的进程可以使用不同的段号去共享同一个段。159分段的共享与保护（3）共享段的分配与回收1)共享段的分配第一个请求使用该共享段的进程其它进程需要调用该共享段2)共享段的回收一般共享段最后一个共享段160分段的共享与保护（4）分段保护1、越界检查段号越界（段表寄存器中存有段表长度信息）段内地址越界（段表内存储段长）2、存取控制检查只读只执行读/写161分段的共享与保护（5）分段保护3、环保护机构规定：低编号的环具有高优先级，OS核心在0环，操作系统服务在中间环，一般应用程序在外环访问调用规则：（1）一个程序可以访问驻留在相同环或较低特权环中的数据（2）一个程序可以调用驻留在相同环或较高特权环中的服务162分段的共享与保护（6）环保护机构16380386的地址变换（1）最常用的微机系统是x86微机系统。80386体系结构并非特别针对Intel80386CPU，而是包括80386、Pentium、PentiumPro、PII、PIII等一系列向下兼容的32位芯片。16480386的地址变换（2）80386具有两种存储器管理模式：实地址模式：程序地址=物理地址只能寻址1MB内存MS-DOS工作于实模式受保护的虚地址模式

在保护模式下，x86提供了实现虚拟存储器的硬件机制，是OS实现多任务存储管理的基础实模式与保护模式16580386的地址变换（3）物理地址：80386中地址总线为32位，物理内存空间最大为4G字节。逻辑地址：80386指令系统提供的的逻辑地址为48位，由它确定的虚拟地址空间可达64T字节。80386地址空间16680386的地址变换（4）80386把虚拟存储器的空间分成性质不同的两部分：全局地址空间、局部地址空间。全局地址空间通常存放操作系统本身的代码和数据，它是系统中所有的进程共享的地址空间。局部地址空间由系统分配给各个进程使用，用于存储进程各自的代码和数据等。80386的全局地址空间和局部地址空间最大都可达32TB。80386地址空间16780386的地址变换（5）x86通过分段机制把虚拟地址空间分成大小不同的段。一个段的空间最大可达4GB。64TB的虚拟地址空间最多可以分为16K个段。全局段和局部段最多可以各有8K个段。80x86地址空间16880386的地址变换（6）16980386的地址变换（7）17080386的地址变换（8）171Linux的内存管理（1）Linux操作系统采用了请求式分页虚拟存储管理方法。系统为每个进程提供了4GB的虚拟内存空间。各个进程的虚拟内存彼此独立。Linux把进程的虚拟内存分成两部分，内核区和用户区。操作系统内核的代码和数据等被映射到内核区。进程的可执行映像（代码和数据）映射到虚拟内存的用户区。172Linux的内存管理（2）注意：Linux操作系统不使用段的概念但是必须兼容Intel处理器的两次地址转换173Linux的内存管理（3）Linux的花招：所有段的base地址都是0。USER_CSUSER_DSKERNEL_CSKERNEL_DS……在Linux下，逻辑地址与线性地址总是一致! 174Linux的内存管理（4）linux下3级页表管理175Linux的内存管理（5）Linux对内存空闲空间的管理采用Buddy算法，Buddy是“伙伴”、“搭档”的意思。Buddy算法是把内存中的所有页面按照2n划分，其中n=0～5，对一个内存空间按1个页面、2个页面、4个页面、8个页面、16个页面、32个页面进行六次划分。Buddy算法176Linux的内存管理（6）划分后形成了大小不等的存储块，称为页面块，简称页块。包含1个页面的页块称为1页块，包含2个页面的称为2页块，依此类推。Linux把物理内存划分成了1、2、4、8、16、32六种页块。对于每种页面块按前后顺序两两结合成一对Buddy“伙伴”按照1页面划分后，0和1页、2和3页…是1页块Buddy。按照2页面划分，0-1和2-3、4-5和6-7…是2页块Buddy。Buddy算法177Linux的内存管理（7）Buddy算法178Linux的内存管理（7）Buddy算法位图中每一位（bit）表示一对Buddy页面的使用情况当一对Buddy的两个页面块中有一个是空闲的，而另一个全部或部分被占用时，该位置1。当这两个页面块都是空闲，或都被全部或部分占用时，对应的位置0。179Linux的内存管理（8）Buddy算法180Linux的内存管理（9）Buddy算法181选择题（1）在存储器管理中,采用覆盖与交换技术的目的是A节省内存空间B物理扩充内存C提高CPU效率D实现内存共享182选择题（2）可变式分区存储管理的拼接技术可以()A集中空闲区B增加内存容量C缩短访问周期D加速地址转换183选择题（3）在固定分区分配中,每个分区的大小是()A相同B随作业长度变化C可以不同但预先固定D可以不同但随作业长度固定184选择题（4）采用分段存储管理的系统中,若地址用24位表示,其中8位表示段号,则允许每段的最大长度是()A224B216C28D232185选择题（5）作业在执行时发生了缺页中断,经操作系统处理后,应让其执行()指令A被中断的前一条B被中断的C被中断的后一条D启动时的第一条186选择题（6）在段页式存储管理系统中，内存等分成（），程序按逻辑模块划分为若干（）。A块B基址C分区D段E页号F段长187选择题（7）可变式分区分配方案中，某一作业完成后，系统收回其内存空间并与相邻空闲区合并，为此修改空闲区表，造成空闲区减1的情况是A无上邻空闲区也无下邻空闲区B有上邻空闲区但无下邻空闲区C有下邻空闲区但无上邻空闲区D有上邻空闲区也有下邻空闲区188选择题（8）把作业地址空间使用的逻辑地址变成内存的物理地址称为()A加载B重定位C物理化D逻辑化189选择题（9）页式虚拟存储的主要特点A不要求将作业装入到内存的连续区域B不要求将作业同时全部装入到内存的连续区域C不要求进行缺页中断处理D不要求进行页面置换190选择题（10）请求分页存储管理中,若采用FIFO页面淘汰算法,则当分配的页面数增加时,缺页中断的次数()A减少B增加C无影响D可能增加也可能减少191选择题（11）虚拟存储管理系统的基础是程序的()理论A局部性B全局性C动态性D虚拟性192选择题（12）如果一个程序为多个进程所共享,那么该程序的代码在执行的过程中不能被修改,程序是()A可置换码B可重入码C可改变码D可再现码193选择题（13）在请求页式存储管理中，当查找的页不在（）中时，要产生缺页中断。A.外存B.虚存C.内存D.地址空间194选择题（14）设基址寄存器内容为1000，在采用动态重定位的系统中，当执行指令“LOADA,2000”时，操作数的实际地址是（）。A.1000B.2000C.3000D.4000195选择题（15）虚拟存储器的最大容量（

）。A.为内外存容量之和B.由计算机的地址结构决定C.是任意的D.由作业的地址空间决定196选择题（16）很好地解决了“零头”问题的存储管理方法是（）。A.页式存储管理B.段式存储管理C.多重分区管理D.可变式分区管理197选择题（17）在分页系统环境下，程序员编制的程序，其地址空间是连续的，分页是由（