计算机操作系统操作系统第4章

第四章 存储器管理,4.1 存储器的层次结构 4.2 程序的装入和链接 4.3 连续分配方式 4.4 基本分页存储管理方式 4.5 基本分段存储管理方式 4.6 虚拟存储器的基本概念 4.7 请求分页存储管理方式 4.8 页面置换算法 4.9 请求分段存储管理方式,4.1 存储器的层次结构,4.1.1 多级存储器结构,4.1.2 主存储器与寄存器 1主存储器 容量一般为数十MB到数GB。 CPU的控制部件只能从主存储器中取得指令和数据，数据能够从主存读取并将它们装入到寄存器中，或者从寄存器存入到主存储器。,2寄存器 寄存器访问速度最快，但价格十分昂贵。寄存器长度一般以字(word)为单位。寄存器可能有几十个甚至上百个。,4.1.3 高速缓存和磁盘缓存 1高速缓存 高速缓存容量大于或远大于寄存器，比内存约小两到三个数量级，从几十KB到几MB，访问速度快于主存储器。 程序执行的局部性原理:一较短时间内，程序执行仅局限于某个部分。 将主存中一些经常访问的信息存放在高速缓存中，减少访问主存储器的次数，可大幅度提高程序执行速度。,2磁盘缓存 磁盘的I/O速度远低于对主存的访问速度，频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数。 磁盘缓存利用主存的存储空间，来暂存从磁盘中读出(或写入)的信息。,4.2 程序的装入和链接,4.2.1 程序的装入 1绝对装入方式(Absolute Loading Mode) 在编译时，知道程序将驻留在内存的什么位置，编译程序产生绝对地址的目标代码。,2可重定位装入方式(Relocation Loading Mode) 多道程序环境下，目标模块的起始地址通常从0开始，程序中的其它地址也相对于起始地址计算。采用可重定位装入方式，根据内存的当前情况，将装入模块装入到内存的适当位置。,作业装入内存时的情况,指令LOAD 1，2500，将2500单元中的整数365取至寄存器1。 因为地址变换通常是在装入时一次完成的，以后不再改变，故称为静态重定位。 3动态运行时装入方式(Dynamic Run-time Loading) 实际情况，在运行过程中进程在内存中的位置可能经常要改变，采用动态运行时装入的方式。,4.3 连续分配方式,4.3.1 单一连续分配 是最简单的一种存储管理方式，只能用于单用户、单任务的操作系统中。把内存分为系统区和用户区两部分，系统区仅提供给OS使用，通常是放在内存的低址部分；用户区是指除系统区以外的全部内存空间，提供给用户使用。,4.3.2 固定分区分配 1划分分区方法 把内存区划分成含有多个较小的分区、适量的中等分区及少量的大分区。可根据程序的大小为之分配适当的分区。 2内存分配 将分区按大小进行排队，建立一张分区使用表。 当有一用户程序要装入时，由内存分配程序检索该表，从中找出一个能满足要求的、尚未分配的分区，将之分配给该程序，然后将该表项中的状态置为“已分配”；,固定分区使用表,4.3.3 动态分区分配 1分区分配中的数据结构,分区起始部分设置用于控制分区分配的信息，以及用于链接各分区所用的前向指针； 分区尾部设置一后向指针，通过前、后向链接指针将所有的空闲分区链接成一个双向链。 当分区被分配出去以后，把状态位由“0”改为“1”，此时，前、后向指针已无意义。,2分区分配算法 1) 首次适应算法FF(first fit) 从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。 优点：优先利用低址部分的空闲分区，保留了高址部分的大空闲区。 缺点：低址部分不断被划分，会留下许多难以利用的、很小的空闲分区。,2) 循环首次适应算法(next fit) 从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。 优点：使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销。 缺点：缺乏大的空闲分区。,3) 最佳适应算法(best fit) 分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业。 算法要求将所有空闲分区按其容量以从小到大的顺序形成一空闲分区链。 缺点：每次分配后所切割下来的剩余部分总是最小的，在存储器中会留下许多难以利用的小空闲区。,4) 最坏适应算法(worst fit) 总是挑选最大的空闲区分割给作业使用。 优点：剩下的空闲区不至于太小。 算法要求将所有的空闲分区按容量从大到小顺序形成空闲分区链。 缺点：存储器中缺乏大的空闲分区。,5) 快速适应算法(quick fit) 将空闲分区根据容量大小进行分类，对每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表。 空闲分区分类根据进程常用的空间大小进行划分，如2 KB、4 KB、8 KB等。 优点：查找效率高，根据进程的长度，寻找到能容纳它的最小空闲区链表，并取下第一块进行分配即可。 不对任何分区产生分割，不会产生内存碎片。 缺点：分区归还主存时算法复杂，系统开销较大。,3分区分配操作 1) 分配内存 u.size：请求的分区大小 m.size ：表中每个空闲分区大小 size：事先规定的不再切割的剩余分区的大小,内存分配流程,2) 回收内存 (1) 回收区与插入点前一个空闲分区F1相邻接 (图a)。将分区合并，修改前一分区F1的大小。 (2) 回收分区与插入点的后一空闲分区F2相邻接， (图b)。将分区合并，回收区的首址作为新空闲区的首址，大小为两者之和。 (3) 回收区同时与插入点的前、后两个分区邻接(图c)。将三个分区合并，使用F1的表项和F1的首址，取消F2的表项，大小为三者之和。 (4) 回收区既不与F1邻接，又不与F2邻接。为回收区单独建立一新表项，根据首址插入到空闲链中的适当位置。,内存回收时的情况,4.3.4 伙伴系统 伙伴系统规定，无论已分配分区或空闲分区，其大小均为2的k次幂，k为整数，lkm。 系统空间容量为2m个字，则系统开始运行时，是一个大小为2m的空闲分区。 系统运行中，不断的划分形成若干个不连续的空闲分区，将空闲分区根据大小进行分类，对每一类单独设立空闲分区双向链表。 链表数：0km,分配长度为n的存储空间，2i1n2i，在空闲分区大小为2i的空闲分区链表中查找并分配。 若长度为2i的空闲分区已耗尽，则在分区大小为2i1的空闲分区链表中寻找。把该空闲分区分为相等的两个分区，这两个分区称为一对伙伴，其中的一个分区用于分配，而把另一个加入分区大小为2i的空闲分区链表中。 大小为2i2的空闲分区，若找到则对其进行两次分割,4.3.6 可重定位分区分配 1动态重定位的引入 要求大的内存分配时，常常需要将内存中的所有作业进行移动，把原来分散的多个小分区拼接成一个大分区，称为“拼接”或“紧凑”。 经过紧凑后的程序在内存中的位置发生了变化，“紧凑”后必须对移动了的程序或数据进行重定位。,2动态重定位的实现 程序执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加形成的。 当系统对内存进行了“紧凑”而使程序从内存的某处移至另一处时，不需对程序做任何修改，只要用该程序在内存的新起始地址，去置换原来的起始地址即可。,动态重定位示意图,动态分区分配算法流程图,4.3.7 对换 1对换(Swapping)的引入 “对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据调入内存。 “进程对换”用于分时系统中。 “页面对换”或“分段对换”，又统称为“部分对换”，用于虚拟存储系统。,2对换空间的管理 外存分为文件区和对换区。对换操作频繁，对换空间管理的主要目标是提高进程换入和换出的速度，采取连续分配方式。,3进程的换出与换入 (1) 进程的换出。系统选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动磁盘，将该进程的程序和数据传送到磁盘的对换区上。 (2) 进程的换入。系统定时地查看所有进程的状态，从中找出“就绪”状态但已换出的进程，将其中换出时间最久的进程换入，直至已无可换入的进程或无可换出的进程为止。,4.4 基本分页存储管理方式,4.4.1 页面与页表 1页面 1) 页面和物理块 将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页。 相应地，把内存空间分成与页面相同大小的若干个存储块，称为(物理)块或页框(frame)。 分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。,2) 页面大小 小页面，页内碎片小，内存利用率高，但进程页表过长，占用大量内存；页面换进换出效率低。 反之，页表长度小，页面换进换出速度高，但页内碎片大。 通常页面大小为512 B8 KB，是2的幂。,2地址结构,地址长度为32位。 011位为页内地址，每页4 KB； 1231位为页号，地址空间最多允许有1 M页。,给定一个逻辑地址空间地址为A，页面的大小为L，则页号P和页内地址d可按下式求得：,其中，INT是整除函数，MOD是取余函数。 例：系统页面大小为1 KB，设A = 2170 B，则由上式可以求得P = 2，d = 122。,3页表：系统为每个进程建立了一张页表。,4.4.2 地址变换机构 1基本的地址变换机构 页表驻留在内存中。页表寄存器PTR(Page-Table Register)存放页表在内存的始址和页表长度。平时，页表的始址和页表长度存放在进程的PCB中。当调度程序调度进程时，将这两个数据装入页表寄存器中。,1）逻辑地址分为页号和页内地址两部分，以页号为索引去检索页表，查找操作由硬件执行。 2）若页号大于或等于页表长度，则地址越界，系统产生地址越界中断。 3）页表始址与页号和页表项长度的乘积相加，得到该表项在页表中的位置。 4）从页表项得到页的物理块号，装入物理地址寄存器。页内地址送入物理地址寄存器的块内地址字段。,分页系统的地址变换机构,2具有快表的地址变换机构 页表存放在内存中，CPU在每存取一个数据时，都要两次访问内存。计算机处理速度降低近1/2。以此高昂代价来换取存储器空间利用率的提高，是得不偿失的。,在地址变换机构中增设一个特殊高速缓冲寄存器（快表），存放当前访问的那些页表项。 1）CPU给出有效地址后，地址变换机构将页号送入快表。若要访问的页表项在快表中，直接从快表读物理块号。 2）若快表中未找到，则访问内存的页表，并重新修改快表（OS找到一个老的且已被认为不再需要的页表项换出）。,具有快表的地址变换机构,4.4.3 两级和多级页表 现代计算机系统支持非常大的逻辑地址空间。 例，逻辑地址空间：32位 页面大小：4 KB（12位） 进程页表中页表项：20位（1兆个） 每个页表项：1个字节 每个进程的页表：占用1 M内存（要求连续的）,两级页表(Two-Level Page Table) 32位逻辑地址 页面大小： 4 KB时(12位) 两级页表（对页表进行分页）： 每页210个页表项，最多210个页表分页,两级页表结构,外层页表寄存器存放外层页表的始址，利用逻辑地址中的外层页号，作为外层页表的索引，从中找到指定页表分页的始址； 利用P2作为指定页表分页的索引，找到指定的页表项，其中即含有该页在内存的物理块号。,具有两级页表的地址变换机构,4.5 基本分段存储管理方式,4.5.1 分段存储管理方式的引入 段是存储信息的逻辑单位。 逻辑地址由段名(段号)和段内偏移量决定： LOAD 1，A |D； 段A中D单元内的值读入寄存器1 STORE 1，B |C； 寄存器1的内容存入B段C单元中,利用段表实现地址映射,4.5.2 分段系统的基本原理 主程序段:MAIN 子程序段:X 数据段:D 栈段:S 每个段从0开始编址，采用一段连续的地址空间。 逻辑地址由段号(