内容程序的装入和链接连续分配存储管理方式覆盖与交换分页课件

1、华北电力大学计算机系目的及要求了解程序装入的方式和实现链接的方法；领会单一连续分配和固定分区分配机制的地址转换；理解并掌握动态分区分配的分配和回收算法，领会动态重定位分区分配算法；了解并领会对换技术；理解并掌握分页存储管理的基本方法、地址变换机构和页表机制；理解并掌握分段存储管理的基本原理，领会分页与分段的主要区别；了解并领会段页式存储管理方式；第五章存储器管理华北电力大学计算机系重点动态分区分配；分页存储管理的基本方法；分页存储管理方式的地址变换机构；分页存储管理方式的页表机制；分段存储管理的基本原理。难点动态分区分配算法；动态重定位分区分配算法；分页存储管理具有快表的地址变换机构；段页式存

2、储管理的地址变换过程。第五章存储器管理华北电力大学计算机系5.1.1 程序的装入5.1.2 程序的链接5.1 程序的装入和链接华北电力大学计算机系程序在成为进程前的准备工作编辑：形成源文件编译：形成目标模块链接：由多个目标模块或程序库生成装入模块装入：将装入模块装入内存5.1.1 程序的装入库编译程序编辑程序链接程序装入程序内存源文件目标模块目标模块装入模块.华北电力大学计算机系名字空间、地址空间、重定位和存储空间名字空间在源程序中，是通过符号名来访问子程序和数据的，我们把程序中符号名的集合称为“名字空间”。地址空间目标程序是以“0”作为参考地址的模块，我们把目标模块中的地址称为相对地址（或称

3、为“逻辑地址”、“虚地址”），而把相对地址的集合称为“相对地址空间”或简称为“地址空间”。5.1.1 程序的装入华北电力大学计算机系3. 存储空间我们把这一内存中存储单元的地址称为物理地址（绝对地址，实地址），其集合称为“绝对地址空间”或“存储空间”。4. 重定位装配模块虽然具有统一的地址空间，但是仍是以“0”作为参考地址。要把它装入内存执行，就要确定装入内存的实际物理地址，并修改程序中与地址有关的代码，这一过程称为地址重定位。所谓地址重定位是指把地址空间中的逻辑地址转换为存储空间的物理地址的过程又称为地址映射。由操作系统中的装入程序loader来完成。地址重定位的方式有静态重定位和动态重定位

4、。5.1.1 程序的装入华北电力大学计算机系5.1.1 程序的装入存储空间（绝对地址/物理地址/虚地址）名字空间（符号地址） 符 号源 程 序相对目标程序（装配模块）绝对目标程序 编译链接 地址重定位 装 入地址空间（相对地址/逻辑地址/虚地址）华北电力大学计算机系绝对装入方式(Absolute Loading Mode)在可执行文件中记录内存地址，装入时直接定位在上述(即文件中记录的地址)内存地址。优点：装入过程简单。缺点：过于依赖于硬件结构，不适于多道程序系统。5.1.1 程序的装入华北电力大学计算机系可重定位装入方式(Relocatable Loading Mode)即静态重定位，装人程

5、序把目标模块中的逻辑地址与本程序在内存中的起始地址相加得到正确的物理地址。0： 10000： 1000： LOAD 1，2500 11000： LOAD 1，12500 2500： 365 12500： 365 2600： 12600： 地址空间 存储空间优点：不需硬件支持，可以装入多道程序缺点：一个程序通常需要占用连续的内存空间，程序装入内存后不能移动。不易实现共享。5.1.1 程序的装入华北电力大学计算机系动态运行时装入方式(Dynamic Run-Tme Loading Mode) 即动态重定位，是在程序运行时完成的，靠硬件地址变换机构实现。装入内存的地址仍是相对地址。最简单的办法是利用

6、一个重定位寄存器。在程序实际运行前，由操作系统把程序在内存的起始地址送入重定位寄存器。在程序运行期间，凡遇到访问内存的操作，就由硬件机制自动地把用户程序的相对地址与重定位寄存器的内容相加，其和就是实际访问内存的有效地址。5.1.1 程序的装入华北电力大学计算机系 重定位寄存器 0： 10000： 100： LOAD 1，2500 10100： LOAD 1，2500 + 2500：365 12500： 365 5000： 15000： 地址空间 存储空间优点：OS可以将一个程序分散存放于不连续的内存空间，可以移动程序，有利用实现共享。缺点：需要硬件支持，OS实现较复杂。5.1.1 程序的装入1

7、00002500华北电力大学计算机系程序的目标模块在装入内存时，与地址有关的指令都无须进行修改，如在图中LOAD 1，2500这条指令中仍保持相对地址2500。当该模块被操作系统调度到处理机上执行时，操作系统首先把该模块装入的实际起始地址减去目标模块的相对基地址（图中该模块的基地址为0），然后将其差值装入重定位寄存器。当CPU取一条访问内存的指令时，地址变换硬件逻辑自动将指令中的相对地址与重定位寄存器中的值相加，再根据和值作为内存的绝对地址去访问该单元的数据。5.1.1 程序的装入华北电力大学计算机系链接程序的功能是将经过编译或汇编得到的一组目标模块以及它们所需的库函数，装配成一个完整的装入模

8、块，实现链接的方法有三种：静态链接、装入时动态链接和运行时动态链接。5.1.2 程序的链接华北电力大学计算机系5.1.2 程序的链接静态链接(Static Linking)事先进行链接，形成一个完整的装入模块，即可执行模块，以后不再拆开，要运行时可直接调入内存。对相对地址进行修改变换外部调用符号华北电力大学计算机系5.1.2 程序的链接装入时动态链接(Load-Time Dynamic Linking)目标模块在装入内存时，边装入边链接，即在装入一个目标模块时，若发生一个外部模块调用，将引起装入程序去找出相应的外部目标模块，并将之装入内存。优点便于软件版本的修改和更新便于实现目标模块的共享缺点

9、进程执行期间，装入模块是不改变的每次运行时，装入模块都是相同的运行时动态链接(Run-Time Dynamic Linking)将某些目标模块的链接，推迟到执行时在进行，即在执行过程中，若发现一个被调用模块尚未装入内存，由OS去找到该模块，将它装入内存，并把它链接到调用模块上。华北电力大学计算机系5.1.2 程序的链接Windows NT动态链接库构造动态链接库DLL是包含函数和数据的模块，它的调用模块可为EXE或DLL，它由调用模块在运行时加载；加载时，它被映射到调用进程的地址空间。在VC中有一类工程用于创建DLL。库程序文件 .C：相当于给出一组函数定义的源代码；模块定义文件 .DEF：相

10、当于定义链接选项，也可在源代码中定义；如：DLL中函数的引入和引出(dllimport和dllexport)。编译程序利用 .C文件生成目标模块 .OBJ库管理程序利用 .DEF文件生成DLL输入库 .LIB和输出文件 .EXP链接程序利用 .OBJ和 .EXP文件生成动态链接库 .DLL。华北电力大学计算机系5.1.2 程序的链接DLL的装入方法装入时动态链接在编程时显式调用某个DLL函数，该DLL函数在可执行文件中称为引入(import)函数。链接时需利用 .LIB文件。在可执行文件中为引入的每个DLL建立一个IMAGE_IMPORT_DESCRIPTOR结构。在装入时由系统根据该DLL映

11、射在进程中的地址改写Import Address Table中的各项函数指针。Hint是DLL函数在DLL文件中的序号，当DLL文件修改后，就未必指向原先的DLL函数。在装入时，系统会查找相应DLL，并把它映射到进程地址空间，获得DLL中各函数的入口地址，定位本进程中对这些函数的引用；华北电力大学计算机系5.1.2 程序的链接装入时动态链接过程注：Import Address Table是在装入时依据DLL模块的加载位置确定。华北电力大学计算机系5.1.2 程序的链接 DLL函数的调用过程华北电力大学计算机系5.1.2 程序的链接运行时动态链接(run-time)：在编程时通过LoadLibr

12、ary（给出DLL名称，返回装入和链接之后该DLL的句柄）, FreeLibrary, GetProcAddress（其参数包括函数的符号名称，返回该函数的入口指针）等API来使用DLL函数。这时不再需要引入库（import library）。LoadLibrary或LoadLibraryEx把可执行模块映射到调用进程的地址空间，返回模块句柄；GetProcAddress获得DLL中特定函数的指针，返回函数指针；FreeLibrary把DLL模块的引用计数减1；当引用计数为0时，拆除DLL模块到进程地址空间的映射；华北电力大学计算机系5.1.2 程序的链接运行时动态链接的例子HINSTANCE

13、 hInstLibrary;/模块句柄定义DWORD (WINAPI *InstallStatusMIF)(char*, char*, char*, char*, char*, char*, char*, BOOL);/函数指针定义if (hInstLibrary = LoadLibrary(ismif32.dll)/映射 InstallStatusMIF = (DWORD (WINAPI *)(char*,char*,char*, char*, char*, char*, char*, BOOL) GetProcAddress(hInstLibrary, InstallStatusMIF);

14、/获得函数指针if (InstallStatusMIF) if (InstallStatusMIF(“office97”, “Microsoft”, “Office 97”, “999.999”, “ENU”, “1234”, ”Completed successfully”, TRUE) !=0)/调用DLL模块中的函数FreeLibrary(hInstLibrary);/拆除映射 华北电力大学计算机系连续分配是指为一个用户程序分配一个连续的内存空间，有两种方式，即单一连续分配方式和分区分配方式。其中，分区分配方式是一种可用于多道程序的较简单的存储管理方式，它又可以进一步细分为固定分区方式和

15、可变(动态)分区方式。5.2.1 单一连续分配5.2.2 固定分区分配5.2.3 动态分区分配5.2.4 动态重定向分区分配5.2.5 MS DOS中的分区存储管理5.2 连续分配存储管理方式华北电力大学计算机系这是一种最简单的存储管理方式，但只能用于单用户、单任务的操作系统，如在8位和16位微机上CP/M和MS-DOS操作系统。它将内存分为两个区： 系统区：仅供操作系统使用，通常设置在内存的低段； 用户区：指除系统区以外的全部内存空间，提供给用户使用。地址重定位时，只要将指令或数据的逻辑地址加上用户区基地址，就可以形成物理地址。为了防止操作系统程序受到用户程序有意或无意的破坏，需要设置内存保

16、护机构，如采用基址寄存器和界限寄存器机制。5.2.1 单一连续分配华北电力大学计算机系5.2.1 单一连续分配界限寄存器重定位寄存器 (基址)+CPU内存地址错逻辑地址YN物理地址u.size m.size-u.sizesize？从该分区中划出u.size大小的分区继续检索下一个表项将该表目以上的所有表目下移一格将该分区分配给申请者修改有关的数据结构 返 回YNNYNY 返 回华北电力大学计算机系回收内存当一个作业运行完毕释放内存时，系统根据释放区的首地址，从空闲区说明表中找到相应的插入点，此时可能出现下列四种情况（如下图所示，其中F1，F2表示回收区的前、后空闲区）：当回收区只与插入点的前一

17、个分区F1相领接时，应将回收区与插入点的前一个分区合并，不再为回收区分配新的表目，而只需修改F1分区表目的大小m_size即可。5.2.3 动态分区分配 F1回收区华北电力大学计算机系当回收区只与插入点的后一个分区F2相领接时，将把两个空闲区合并，修改F2分区的表目，把回收区的起址作为新空闲区的起址，大小为两个分区之和。5.2.3 动态分区分配 回收区 F2华北电力大学计算机系回收区与插入点的前、后两个分区（F1和F2）都相领接时（如D），合并三个分区，用F1表目的起址作为新空闲区的起址，修改其大小为三块分区之和，最后取消F2的表目。5.2.3 动态分区分配 F1回收区 F2华北电力大学计算机

18、系当回收区既不与F1领接，又不与F2领接时（如A），应为回收区单独建立一项新表目，填写回收区的起址和大小，并根据其起址，插入到空闲区说明表的适当位置。5.2.3 动态分区分配 回收区 华北电力大学计算机系回收流程5.2.3 动态分区分配是否否是是否将该表目以上的所有表目上移一格，并插入新释放的可用区表目顺序地检索可用资源表直至找到某表目的m.addraa或m.size=0不是第一个表目且与前一可用区 相邻？与后一可用分区相邻且不为空表 目？ 把所释放的可用区 与前一分区合并所释放的可用区与后一可用区合并所释放可用区的size=0 ?与后一可用 区 相邻？ 与后一可用区合并将该表目以上的所有表目

19、下移一格 返 回mfree是否华北电力大学计算机系拼接/紧凑虽然可能所有零头的总和超过某一个作业的要求，但是由于不连续而无法分配。解决零头的方法是拼接（或称紧凑），即向一个方向（例如向低地址端）移动已分配的作业，使那些零散的小空闲区在另一方向连成一片。分区的拼接技术，一方面是要求能够对作业进行重定位，另一方面系统在拼接时要耗费较多的时间5.2.4 动态重定向分区分配华北电力大学计算机系5.2.4 动态重定向分区分配操作系统用户程序110KB用户程序330KB用户程序614KB用户程序926KB操作系统用户程序1用户程序3用户程序6用户程序980KB紧凑前紧凑后华北电力大学计算机系重定位寄存器

20、0： 10000： 100： LOAD 1，2500 10100： LOAD 1，2500 + 2500：365 12500： 365 5000： 15000： 地址空间 存储空间5.2.4 动态重定向分区分配100002500动态重定位华北电力大学计算机系动态重定位分区分配算法 动态重定位分区管理中何时进行存储器紧缩有二种不同的解决办法：在某个分区被释放后立即进行紧缩，系统总是只有一个连续的分区而无碎片，此法很花费机时。当“请求分配模块”找不到足够大的自由分区分给用户时再进行紧缩，这样紧缩的次数比上种方法少得多，但管理复杂。采用此法的动态重定位分区分配算法流程如下：5.2.4 动态重定向分区

21、分配华北电力大学计算机系动态重定位分区分配算法流程5.2.4 动态重定向分区分配请求分配u.size分区检索空闲分区链（表）无法分配 返回空闲分区总和u.size找到大于u.size的可用 区否？ 进行紧凑形成 连续空闲区修改有关的数据结构 按动态分区方式 进行分配修改有关的 数据结构返回分区号 及首址是否否是华北电力大学计算机系DOS提供动态分区管理；通过DOS功能调用int 21h，支持分区的创建(48h)、释放(49h)和改变分区大小(4Ah)设置或查询分区的分配策略(58h)：最先匹配法、最佳匹配法、最后匹配法（last-fit，从内存高端向低端查找）5.2.5 MS DOS中的分区存

22、储管理华北电力大学计算机系数据结构为单向链表。每个分区以一个MCB(Memory Control Block)结构开始，MCB占16个字节，按段边界对齐（起始地址可被16整除）PSP(Program Segment Prefix)：起进程控制块的作用，其起始地址可作为进程IDtypedef struct BYTE type;/* M = in chain; Z = at end*/ WORD owner;/* PSP of the owner process, 0 = free */ WORD size;/* in 16-byte paragraphs */ BYTE unused3; BYT

23、E dos48;/* program name(DOS 4.x)*/ MCB;5.2.5 MS DOS中的分区存储管理华北电力大学计算机系5.3.1 覆盖(overlay)5.3.2 交换(swapping)5.3 覆盖与交换华北电力大学计算机系引入：其目标是在较小的可用内存中运行较大的程序。常用于多道程序系统，与分区存储管理配合使用。原理：一个程序的几个代码段或数据段，按照时间先后来占用公共的内存空间。将程序的必要部分（常用功能）的代码和数据常驻内存；可选部分（不常用功能）在其他程序模块中实现，平时存放在外存中（覆盖文件），在需要用到时才装入到内存；不存在调用关系的模块不必同时装入到内存，从

24、而可以相互覆盖。(即不同时用的模块可共用一个分区)5.3.1 覆盖华北电力大学计算机系5.3.1 覆盖华北电力大学计算机系缺点：编程时必须划分程序模块和确定程序模块之间的覆盖关系，增加编程复杂度。从外存装入覆盖文件，以时间延长来换取空间节省。5.3.1 覆盖华北电力大学计算机系交换技术最早用在麻省理工学院的兼容分时系统CTSS中，该系统是单用户系统，所有用户都驻留在外存的后备队列中，每次只调入一个作业进入内存运行，此作业的时间的时间片用完时，又将该作业调至外存，再将后备队列中的一个作业调入内存运行一个时间片。这是早期的简单分时系统，它采用早期的交换（调进凋出）来满足多个程序共享主存的需要。5.

25、3.2 交换华北电力大学计算机系5.3.2 交换华北电力大学计算机系多道程序环境下的对换 在多道程序环境下为了提高内存和CPU的利用率，增加系统吞吐量，系统中增设了对换，把内存中暂不能运行的进程调出到外存上，以腾出足够的内存空间，把已具备运行条件的进程换入内存。 UNIX早期已引入对换功能并一直保留至今，UNIX系统设置一个对换进程完成以上功能。为了实现进程对换，系统必须能实现对对换空间的管理，进程换入和进程换出等三项功能。 5.3.2 交换华北电力大学计算机系对换空间的管理外存分为文件区和对换区。文件区用于存放文件，对文件区管理目标是提高文件存储空间的利用率，为此系统采用离散分散方式；对换区

26、用于存放从内存频繁换出的进程，它的管理目标是提高进程换入换出速度，为此系统采用连续分配方式。UNIX对换区采用空闲分区表和首次适应算法的动态分区管理，类同早期内存管理。5.3.2 交换华北电力大学计算机系进程的换出与换入当内核发现内存不足时调用对换进程，对换进程检查驻留在内存的进程，选择处于阻塞状态的进程换出;如无则选择优先级低的驻留内存时间长的处于就绪状态的进程换出。而当内存又空时对换进程在对换区中选择换出时间长的处于就绪态的进程调入。5.3.2 交换华北电力大学计算机系优点增加并发运行的程序数目，并且给用户提供适当的响应时间；编写程序时不影响程序结构缺点对换入和换出的控制增加处理机开销；程

27、序整个地址空间都进行传送。5.3.2 交换华北电力大学计算机系5.4.1 分页存储管理的基本方法5.4.2 地址变换机构5.4.3 两级和多级页表5.4.4 反置页表5.4 分页存储管理方式华北电力大学计算机系5.4.1 分页存储管理的基本方法页面和物理块分页存储管理是将一个进程的地址空间划分成若干个大小相等的区域，称为页或页面相应地，将内存空间划分成与页相同大小的若干个存储块，称为物理块或页框。在为进程分配内存时，将进程中的若干页分别装入多个不相邻接的块中。华北电力大学计算机系5.4.1 分页存储管理的基本方法华北电力大学计算机系5.4.1 分页存储管理的基本方法华北电力大学计算机系优点：没

28、有外碎片页内碎片（进程的最后一页经常装不满一块，形成的不可利用利用的碎片）不超过页大小。一个程序不必连续存放。缺点：程序全部装入内存。5.4.1 分页存储管理的基本方法华北电力大学计算机系5.4.1 分页存储管理的基本方法地址结构分页系统的地址结构如下图所示，它由两部分组成：前部分为页号P；后一部分为位移量W，即页内地址d。图中的地址长度为32位，其中011位为页内地址（每页的大小为4KB），1231位为页号，所以允许地址空间的大小最多为1MB个页。若给定逻辑地址A，页面大小L，则例如：L=1kB,A=2170B,则，P=2,d=122 页号 P 位移量W31 12 11 0华北电力大学计算机

29、系页表在将进程的每一页离散地分配到内存的多个物理块中后，系统应能保证能在内存中找到每个页面所对应的物理块。为此，系统为每个进程建立了一张页面映射表，简称页表（如下图所示）。每个页在页表中占一个表项，记录该页在内存中对应的物理块号。进程在执行时，通过查找页表，就可以找到每页所对应的物理块号。可见，页表的作用是实现从页号到物理块号的地址映射。5.4.1 分页存储管理的基本方法页号块号存储控制0213华北电力大学计算机系5.4.1 分页存储管理的基本方法华北电力大学计算机系页面大小的选择由机器的地址结构所决定的，即由硬件所决定。某一种机器只能采用一种大小的页面。通常是：几KB到几十KB。小内碎片小，

30、内存利用率高，但页面数目多，使页表过长，占大量内存，管理开销大；大页表短，管理开销小，内碎片大，内存利用率低5.4.1 分页存储管理的基本方法华北电力大学计算机系地址变换机构的基本任务是利用页表把用户程序中的逻辑地址变换成内存中的物理地址，实际上就要将用户程序中的页号变换成内存中的物理块号。5.4.2 地址变换机构华北电力大学计算机系基本的地址变换机构为了实现地址变换功能，在系统中设置页表寄存器，用来存放页表的始址和页表的长度。在进程未执行时，每个进程对应的页表的始址和长度存放在进程的PCB中，当该进程被调度时，就将它们装入页表寄存器。当进程访问某个逻辑地址中的数据时，分页地址变换机构自动地将

31、逻辑地址分为页号和页内地址两部分，送入逻辑地址寄存器；将页号与页表长度进行比较，如果页号大于页表长度，则访问越界，产生越界中断。如未出现越界，则将页表始址加上页号与页表项大小的乘积，计算出该页在页表中的位置，得到该页的物理块号，将此物理块号装入物理地址寄存器中。与此同时，将逻辑地址寄存器中页内地址直接装入物理地址寄存器的块内地址字段中，这样便完成了从逻辑地址到物理地址的变换。5.4.2 地址变换机构华北电力大学计算机系 越界中断 页表寄存器 逻辑地址2500 页号 块 号 0 1 2 每页1KB(1024) 物理地址5572 5*1024+452块号5 块内地址452 页 号2 页内地址452

32、页表始址 页表长度2 4 55.4.2 地址变换机构华北电力大学计算机系5.4.2 地址变换机构华北电力大学计算机系5.4.2 地址变换机构华北电力大学计算机系5.4.2 地址变换机构华北电力大学计算机系具有快表的地址变换机构如果页表存放在内存中，则每次访问内存时，都要先访问内存中的页表，然后根据所形成的物理地址再访问内存。这样CPU存取一个数据必须访问两次内存，从而使计算机的处理速度降低了1/2。为了提高地址变换的速度，在地址变换机构中增设了一个具有并行查询功能的特殊的高速缓冲存储器，称为“联想存储器”或“快表”，用以存放当前访问的那些页表项。此时地址变换过程为：在CPU给出有效地址后，地址

33、变换机构自动地将页号送入高速缓存，确定所需要的页是否在快表中。若是，则直接读出该页所对应的物理块号，送入物理地址寄存器；若在快表中未找到对应的页表项，则需再访问内存中的页表，找到后，把从页表中读出的页表项存入快表中的一个寄存器单元中，以取代一个旧的页表项。5.4.2 地址变换机构华北电力大学计算机系 越界中断 页表寄存器 逻辑地址页 号 块 号页号 块号 0 2 0 1 4 1 2 5 2 快 表 页 表 物理地址 页 号 页内地址页表始址 页表长度 2 4 5块号 块内地址 输入寄存器5.4.2 地址变换机构华北电力大学计算机系5.4.2 地址变换机构华北电力大学计算机系5.4.2 地址变换

34、机构华北电力大学计算机系5.4.2 地址变换机构华北电力大学计算机系由于成本的原因，快表不可能做得很大，通常只能存放16512个页表项。例如，在Intel80486中有32个。这对中、小型作业来说，已可能把全部页表项放入快表中；但对于大型作业来说，则只能将一部分页表放入快表中。通常快表的命中率可以达到80%90%。例如，假设检索联想存储器的时间为20ns，访问内存的时间为100ns，访问联想存储器的的命中率为85%，则CPU存取一个数据的平均时间为T=0.85*120+0.15*220=135ns，所以访问时间只增加35%。如果不引入联想存储器，其访问将延长一倍（达200ns）。5.4.2 地

35、址变换机构华北电力大学计算机系80386的逻辑地址有232B，如页面大小为4KB（212B），则页表项达1M个，每个页表项占用4B，故每个进程的页表占用4MB内存空间，还要求是连续的，显然这是不现实的。解决的办法有两种：一是只将当前所需要的部分页表项调入内存，其余部分仍然驻留在磁盘上，需要时再将它们调入内存。 二是对页表所需的空间，采用离散分配方式，形成两级（甚至多级页表）；5.4.3 两级和多级页表华北电力大学计算机系两级页表（Two-Level Page Table）基本方法是将页表进行分页，每个页面的大小与内存物理块的大小相同，并为它们进行编号，可以离散地将各个页面分别存放在不同的物理块

36、中，为此再建立一张页表，称为外层页表（页表目录），即第一级页表，其中的每个表目是页表页面的物理块号。第二级才是页表，其中的每个表目所存放的才是页的物理块号。5.4.3 两级和多级页表华北电力大学计算机系逻辑地址结构两级页表系统将32位逻辑地址空间的地址分成三段：其中，页表目录号（外层页号p1）和页号（外层页内地址p2）两项各占10位，偏移量（页内地址d）占12位。 31 22 21 12 11 05.4.3 两级和多级页表 外层页号p1 外层页内地址p2 页内地址d华北电力大学计算机系两级页表结构 第0页页表（物理块号10） 内 存 0 1 0 1 1023 2 第1页页表（物理块号25） 0

37、 1 1023 第N页页表（物理块号120） 0 1 1023 外层页表 10235.4.3 两级和多级页表1025120121432351511520112131432333435151152华北电力大学计算机系两级页表地址变换机构 外层页表 页表 物理地址 5.4.3 两级和多级页表 外层页号p1 外层页内地址p2 页内地址d外层页表寄存器+ b d华北电力大学计算机系多级页表SUN SPARC 三级页表5.4.3 两级和多级页表华北电力大学计算机系5.4.4 反置页表反置页表不是依据进程的页号来组织，而是依据该进程在内存中的物理块号来组织（即：按物理块号排列）。华北电力大学计算机系5.5

38、.1 分段存储管理方式的引入5.5.2 分段系统的基本原理5.5.3 共享与保护5.5.4 段页式存储管理方式5.5 分段存储管理方式华北电力大学计算机系便于编程 通常用户常常把自己的作业按照逻辑关系划分成若干个段，每个段都有自己的名字，且都从零开始编址，这样，用户程序再执行中可用段名和段内地址进行访问。例如：LOAD 1，A | 这条指令的含义是将分段A中的D单元内的值读入寄存器1。分段共享 在实现程序和数据的共享时，常常以信息的逻辑单位为基础，而分页系统中的每一页只是存放信息的物理单位，其本身没有完整的意义，因而不便于实现信息的共享，而段却是信息的逻辑单位，有利于信息的共享。5.5.1 分

39、段存储管理方式的引入华北电力大学计算机系分段保护 信息保护是对相对完整意义的逻辑单位（段）进行保护。动态连接当运行过程中又需要调用某段时，再将该段（目标程序）调入内存并链接起来。所以，动态链接是以段为基础的。动态增长 在实际系统中，往往有些数据段会不断地增长，而事先却无法知道数据段会增长到多大，分段存储管理方式可以较好地解决这个问题。5.5.1 分段存储管理方式的引入华北电力大学计算机系分段在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段是一组完整的逻辑信息，如有主程序段MAIN、子程序段X、数据段D及堆栈段S等，每个段都有自己的名字，都是从零开始编址的一段连续的地址空间，各段长度

40、是不等的。分段系统的地址结构如下图所示，逻辑地址由段号（名）和段内地址两部分组成。在该地址结构中，允许一个作业最多有64 K个段，每个段的最大长度为64 KB。31 16 15 05.5.2 分段系统的基本原理 段 号 段 内 地 址华北电力大学计算机系段表在分段式存储管理系统中，为每个段分配一个连续的分区，而进程中的各个段可以离散地分配到内存中不同的分区中。在系统中为每个进程建立一张段映射表，简称为“段表”。每个段在表中占有一表项，在其中记录了该段在内存中的起始地址（又称为“基址”）和段的长度，如下图所示。进程在执行中，通过查段表来找到每个段所对应的内存区。可见，段表实现了从逻辑段到物理内存

41、区的映射。5.5.2 分段系统的基本原理华北电力大学计算机系 作业空间 (MAIN）=0 0 段 表 30K 段号 段长 基址 （X）=1 0 0 20K 1 （D）=2 0 2 15K （S）=3 3 0 10K 内存空间 0 40k：80k：120k：150k：30K 40K20K 80K15K 120K10K 150K（MAIN）=0 30K（X）=1 20K（D）=2 15K （S）=3 10K5.5.2 分段系统的基本原理华北电力大学计算机系地址变换机构为了实现从逻辑地址到物理地址的变换功能，系统中设置了段表寄存器，用于存放段表始址和段表长度。在进行地址变换时，系统将逻辑地址中的段号

42、S与段表长度TL进行比较。若 STL，表示段号太大，访问越界，于是产生越界中断信号；若未越界，则根据段表的始址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存中的起始地址，然后再检查段内地址d是否超过该段的段长SL。若超过，即 dSL，同样发出越界中断信号；若未越界，则将该段的基址与段内地址d相加，得要访问的内存物理地址。5.5.2 分段系统的基本原理华北电力大学计算机系段表寄存器 越界中断 逻辑地址 段号 段长SL 基址 0 1 2 3 段表始址 段表长度 TL段号S 位移量d 2 1001K 6K600 4K500 8K200 9200 物理地址 8k+1005.5.2 分段系

43、统的基本原理华北电力大学计算机系5.5.2 分段系统的基本原理华北电力大学计算机系5.5.2 分段系统的基本原理华北电力大学计算机系分页和分段的主要区别分页是出于系统管理的需要，分段是出于用户应用的需要。页是信息的物理单位，段是信息的逻辑单位页大小是系统固定的，而段大小则通常不固定。逻辑地址表示：分页的程序地址空间是一维的，各个模块在链接时必须组织成同一个地址空间；分段的程序地址空间是二维的，各个模块在链接时可以每个段组织成一个地址空间。通常段比页大，因而段表比页表短，可以缩短查找时间，提高访问速度。5.5.2 分段系统的基本原理华北电力大学计算机系5.5.3 共享与保护段是信息的逻辑单位,因

44、此分段系统的一个突出的优点是易于实现段的共享。即允许若干个进程共享一个或多个段，而且对段的保护也十分简单。在分页系统中，虽然也能实现程序和数据的共享，但远不如分段系统来得方便。图是分段系统中共享 editor编辑程序的示意图。华北电力大学计算机系5.5.3 共享与保护华北电力大学计算机系分页和分段存储管理方式都各有其优缺点。如果对两种存储管理方式“各取所长”后，则可以形成一种新的存储管理方式的系统段页式系统。这种新系统既具有分页系统能有效地提高内存利用率的优点，又具有分段系统能很好地满足用户需要的长处，显然是一种比较有效的存储管理方式。5.5.4 段页式存储管理方式华北电力大学计算机系基本原理

45、段页式系统的基本原理是先将整个主存划分成大小相等的物理块，把用户程序按程序的逻辑关系分为若干个段，并为每个段赋予一个段名，再把每个段划分成若干页，以页为单位离散分配。在段页式系统中，其地址结构由段号、段内页号和页内地址三部分组成，作业地址空间的结构如图下所示。5.5.4 段页式存储管理方式 段号（S） 段内页号（P） 页内地址（W）华北电力大学计算机系 段表寄存器5.5.4 段页式存储管理方式段表大小段表始址华北电力大学计算机系地址变换过程在段页式系统中，有一个段表寄存器，存放段表始址和段长TL。在进行地址变换时，首先利用段号S，将它与段长TL进行比较。若STL，表示未越界，于是利用段表始址和

46、段号求出该段对应的段表项在段表中的位置，从中得到该段的页表始址，并利用逻辑地址中的段内页号P来获得对应页的页表项位置，从中读出该页所在的物理块号b，再用块号 b和页内地址构成物理地址。下图说明了段页式系统中的地址变换机构。5.5.4 段页式存储管理方式华北电力大学计算机系 段表寄存器 越界中断 段表始址 段表长度 +段号（S）段内页号（P）页内地址（W） +块 号b 块内地址 段 表0123 页表01235.5.4 段页式存储管理方式华北电力大学计算机系5.5.4 段页式存储管理方式华北电力大学计算机系5.5.4 段页式存储管理方式华北电力大学计算机系在段页式系统中，为了获得一条指令或数据，需三次访问内存：第一次访问内存中的段表，从中取得页表始址；第二次访问内存中的页表，从中取出该页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理地址；第三次访问才是真正根据所得的物理地址取出指令或数据。显然，这使访问内存的次数增加了近两倍。为了提高执行的速度，在地址变换机构中增设一