学而不思则惘，思而不学则殆第三章存储器管理1 源程序变为内存中可执行的程序需要经过哪些步骤？这些步骤分别有哪几种方式？A 编译：源代码编译成目标模块.obj B 链接：与库函数链接在一起，形成装入模块（静态链接、装入内存时动态链接、运行时动态链接）C 装入：装入内存运行。有绝对装入（绝对地址）、可重定位装入（静态重定位；装入时地址重定位） 、动态运行时装入（动态重定位；运行时地址重定位，需要重定位寄存器支持） ；2 什么叫重定位？动态重定位特点是什么？（重定位的好处）在存储器管理中什么是重定位？为什么要引进重定位技术？2014 当装入程序将可执行代码装入内存时，把逻辑地址转换成物理地址的过程，叫重定位。（一般没特殊说明，指的就是动态重定位）1 将程序分配到不连续的存储器中；2 只需投入部分代码即可运行；3 运行期间，根据代码需求动态申请内存；4 便于程序段的共享，可用向用户提供一个比存储空间大很多大地址空间。3 内存是如何进行保护的？（访问内存的地址是如何识别正确性的？）（内存保护是为了确保操作系统的地址区不受用户进程的影响）使用重定位寄存器（含最小物理地址）和界地址寄存器（逻辑地址）来保护的。首先将逻辑地址与界地址比较，小于则与重定位地址相加映射成物理地址；大于则出现越界中断。4 什么是覆盖技术、交换技术？覆盖： 把用户空间分成一个固定区和若干的覆盖区，经常活跃的放在固定区，其他按需要调入覆盖区。覆盖优缺点：打破了将进程全部信息装入内存才能运行的限制；当同时运行的程序代码量大于内存仍不能运行、并且用户需给出覆盖区的结构交换：即中级调度的进程的换入和换出。（现在已经不使用覆盖技术，现在是通过虚拟存储技术来解决的）1 内存分配管理有哪些方式？根据作业是否在同一分区划为连续分配和非连续分配。A 连续分配： 1 单一连续分配、2 固定分区、 3 动态分区。B 非连续分配： 1 分页、 2 分段、 3 段页式（每个又根据是否使用虚拟内存技术分为基本和请求）2 简述连续分配管理的方式有哪些？优缺点有什么？A 单一连续分配：分为系统区和用户区。无需内存保护。优缺点：有内部碎片，内存利用率低，且只适用于单任务单用户的OS中。B 固定分区分配：将内存空间划分为固定大小区域，每个区域只装入一道作业。缺点：程序太大放不进去、主存利用率低、产生内部碎片。C动态分区分配：根据进程大小动态建立分区，使分区大小正好适应进程需要。缺点：刚开始的时候是比较好的，后面会导致外部碎片的产生。3 什么是内部碎片？外部碎片、通过什么技术来解决？内部碎片：程序小于固定分区大小，导致分区内部空间有剩余。外部碎片：在分区外部产生难以使用的碎片。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 7 页学而不思则惘，思而不学则殆外部碎片通过“紧凑”技术来解决。4 动态分区分配的空闲分区的分配策略有哪些？优缺点是什么？首次适应算法First Fit：空闲分区按地址顺序次序链接起来，每次都分配第一个；最佳适应算法Best Fit：空闲分区按从小到大链接起来，每次分配最能适应程序大小的那一个；最坏适应算法Worst Fit：空闲分区按从大到小顺序链接起来，每次分配最大的空间；循环首次适应算法Next Fit：首次适应算法；只不过下一次寻找是从上一次结束位置开始。First Fit：最简单，且效果最好、最快的。缺点是内存低址部分出现很多小的分区，且每次查找都要经过这些分区。Best Fit：实际上比较差，因为每次分配都留下难以利用的内存块，产生最多的碎片。Worst Fit：导致很快没有可用的大的内存块。Next Fit：它试图解决首次适应算法的问题，但实际上会导致在内存末尾分配空间。比首次还差。1 连续分配的固定分区分配与 非连续的分页管理有什么不同？分页在形式上看与固定分区一样，但实际上不一样；分页的大小比固定分区小很多，且分页是按进程分页，内存分块（页框），进程按块为单位申请空间， 所以只会在最后一块中产生页内碎片，所以不会产生外部碎片。这会使一个作业的进程可能被分到了不同的块中。2 什么是页表？分页存储管理系统中， 页表的主要作用是什么？现代大多数计算机系统都支持非常大的逻辑地址空间，这给页表设计带来什么问题？（页表太大）2014 页表是为了便于在内存中找到进程中每个页面对应的物理块号，系统为每一个进程建立一张页表，记录在内存中物理块号，页表也一般放在内存中。3 分页管理方式存在哪两种主要的问题？每次访问内存需要逻辑地址转化到物理地址，所以转化速度必须快；【快表】每个进程引入页表机制，页表不能太大， 否则内存利用率低【多级分页和请求分页】 （见下）4 页表太大会带来什么问题？解决方法有哪些？难以在内存中找到一块连续的地址，放下这么大的页表。即便是找到， 也会占用内存很大的空间，内存的空间利用率下降。1 采用离散分配方式解决难以找到一块连续的大内存空间；【多级页表】2 只需将当前需要的部分页表项调入内存，其余页表项驻留在外存上。【请求分页】5 页表是什么组成的？分页的地址结构？整张页表，是由一个个页表项组成。每一个页表项由页号和所对应的块号组成。分页的地址结构由“页号”+“页内偏移量”组成。例如地址长度32 位（页号3112，页内偏移 110）则1“页号” 就是整张页表中页表项的偏移量。 （现在页号20 位，即能支持的页表项个数为 220个。最大页表项所对应的页号是220-1。2 如果把一页里面放满页表编号（不是页号，页号是一页里面的页表项的偏移量），即该一页中的页号中的一位对应一张页表，就是能支持最大页数。（地址空间所允许的最大页数为 220页）3“页内偏移量”就是一页的大小。（现在页内偏移量为12 位，即 212B=4KB 。即现在一页的大小为4KB）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 7 页学而不思则惘，思而不学则殆6 慢表的地址变换过程？（整个过程由硬件自动完成）整个过程就是把逻辑地址的页号替换成物理块号，就变为了物理地址。（假设页面大小L=1KB ，页号 2 对应物理块8，计算逻辑地址2500 的物理地址？）1 系统常设“页表寄存器”，存放该页表的内存开始地址F 和页表长度M。 （平时放在PCB中，要用时才调入寄存器）（先找到该页表，页表长度为1024B）2 根据逻辑地址计算页号P 和页内偏移量W - 比较页号P与页表长度M（页号是页表的里面一个页表项的偏移量与 页表长度，即总的页表项相比较） - （页号 p=逻辑地址 /页面大小；页内偏移量W=逻辑地址 %页面大小）（现在页号p= 2500/1024B=2；页内偏移量W=2500%1024B=452）3 P （21024，继续找到2 对应 8）4 最后形成物理地址（注意：块号在高位上，快内偏移在低位上，不能直接相加，需要把块号 *快内偏移最大量+快内偏移）（物理地址 =8*1024+452=8644 ）7 什么是快表？有快表和只有慢表访存到次数是多少？页式管理中为什么要设置页表和快表？（加快地址重定位速度，从而加快了存取速度）2011 快表：在高速缓冲器Cache中增设当前访问的若干表项，它是内存中页表（慢表）的一个很小的副本。只有慢表需访问两次：一次访问内存的页表，转化成物理地址后，再一次访问内存。（命中的）快表访问一次内存：虽然是一次Cache一次内存，但访问内存只有1 次。8 快表地址变换过程？快表计算有些是慢表快表同时查找、有些是先找快表（一般不用同时查找）；1 快表找到则直接可以形成物理地址。2 快表找不到，则找到慢表中的表项时，同时更新快表。然后再次从头访问。如果是请求分页，还可能出现该页 （不是页表项） 不在内存的情况， 需要缺页中断处理，调入该页、并且修改页表。最后一定要记住分页快表中拿到的是地址，还需要再次访问内存拿到数据。例：现在记快表访问时间为A，缺页中断处理时间为B，访问内存时间为C 则能命中快表的总的访问时间：A+C （访问 A 拿到地址，再访问C 拿数据）不能命中快表的总的访问时间：A+C+C （访问 A 失败，访问C拿到地址，再访问C拿数据）不能命中快表且内存中没有该页框：A+C+B+A+C （访问 A 失败，访问C 失败，中断处理B，然后再访问A 拿到地址，再访问C拿到数据）9 两级分页的地址转换过程？先找顶级页表（只有一张），然后找到对应的页表项，取到二级页表的块号；根据该块号找二级页表，然后找到对应的页表项，取到对应的块号；最后块号与页内偏移形成最终的物理地址。10 两级分页的地址结构？“顶级页表” +“二级页表” +“页内偏移量” （假设 32 位地址， 3122 顶级页表， 2112二级页表， 110 页内偏移量）1 二级分页就是把顶级页表的一页来装二级分页的页表编号，所以顶级页表的一位对应二级分页的一张页表。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 7 页学而不思则惘，思而不学则殆2 二级页表总的页表项数=顶级页表数目* 每一个顶级页表对应的二级页表数目（210*210=220项，就是两个位数相加）3 分页：一页大小为aKB，一个页表项大小为bKB，则一页可放a/b 个页表项；进程大小为cKB，则该进程可以分为c/a 页作为二级页表；固二级页表项有c/a 个项，将其分页，可以分为(c/a)/(a/b)=cb/a2页；这些页对应出来的就是就是顶级页表的页表项数cb/a2项。4 32 位系统分页（ 32 位，即 232B=4GB，假设一页4KB，页表项大小为4B）则一页可容纳4KB/4B=210个页表项；这些地址空间可以分为4GB/4KB=220个页面，这些页面对应页表项也有这么多，固向上分页可以分出220/210=210个页面， 这些页面对应的页表项刚好塞进一页，固只需要二级分页即可。5 64 位系统分页（ 64 位，即 264B，假设一页4KB，页表项大小为8B，偏移字段12 位）则一页可容纳4KB/8B=29个页表项，即每一次分页占9 位；这些地址空间64 位=12+（9+9+9+9+9+7） ，即需要6 级分页。（实际上没有使用全部 64 位寻址，只用了45 位，分了4 级页表出来）1 基本分页和基本分段异同？分页时从计算机角度考虑的，提高计算机内存利用率，且是通过硬件实现的，对用户完全透明； 分段则是从程序员角度考虑的，以满足方便编程、 信息保护、 信息共享、 动态增长、动态链接等多方面需要。页的大小固定，由机器硬件实现地址重定位；段的大小不固定，由编译程序决定。分页的作业地址空间是一维的；分段则是二维的，程序员标识一个地址既要给出段名，也要给出段内地址。2 页表、段表、段页式的页表、段表每一项由什么组成？页表、段表、段页式地址结构由什么组成？A 页表项由“页号” 、 “块号 (就是首地址 )”段表项由“段号” 、 “段首地址” 、 “段长”（因为每一段长度不同）段页式的段表“段号” 、 “页表首地址” 、 “段长”段页式的页表（同上页表）B 页表地址由“页号”+“页内偏移量”段表地址由“段号”+“段内偏移量（以所有段中的最大段长来设计）”段页式由“段号”+“页号” +“页内偏移量”2 什么叫纯代码？或者叫可重入代码？有什么作用？不能进行修改的代码叫纯代码，可重入代码。可以共享给其他进程。如某程序有160KB 代码和40KB 的数据区，有40 个进程使用，则需要40*200KB=8MB的内存空间； 如果代码是可重入的， 则需要 40*40KB+160KB=1760KB。（对于可重入代码来说，每个进程的段表都指向同一内存区域）3 段页式是如何进行管理的？作业先进行分段，再将每一段分为若干页。所以逻辑地址是由段号、页号、页内偏移组成。系统为每个进程建立一张段表，每个分段有一张页表。4 段页式地址变换时需几次访存？三次：先找内存中的段表，再一次找页表，根据页表转化为物理地址后，访存。1 什么是局部性原理？精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 7 页学而不思则惘，思而不学则殆分为时间局部性原理（某条指令被执行过，则不久后将再次执行）和空间局部性（一旦访问某个存储单元，则其附近的存储单元也会被访问）原理。2 什么是虚拟存储器技术？为什么要引入虚拟存储技术？什么是虚拟存储器？为什么要引入虚拟存储技术？2013 （基于局部性原理， 程序在装入时， 将程序一部分装入内存；当访问的信息不在内存时，再请求将所需的部分调入内存。如果内存已满， 则利用置换功能， 将内存中不用的页调出去，再将其调入。 这样， 系统好像为用户提供了一个比内存大得多的内存空间，这样的技术称为虚拟存储技术）虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上扩充内存的一种存储器技术。虚拟存储器的容量与物理主存大小无关，受限于地址结构和可用磁盘容量。主要目的是提供系统的内存空间、利用率和系统吞吐量。3 虚拟存储器的三个主要特征？多次性：作业分成多次调入内存。对换性：允许作业在运行时换入换出。虚拟性：从逻辑上扩充， 使用户看到一个远大于实际内存空间的容量。（最重要的特征）4 覆盖技术与虚拟存储器技术有什么不同？交换技术与虚拟存储器技术的调入调出有什么不同？覆盖技术受到内存容量大小的限制，而虚拟存储器则没有；且覆盖的覆盖区需要程序员设计，虚拟存储器则没有；交换技术， 或者说中级调度，调入调出的是一个进程；而虚拟存储器的调入调出的是进程都一些页面。5 请求分页需要考虑什么问题？基本分页存储管理和请求分页存储管理的异同？2012 请求分页不是装入所有页面到内存，而是装入程序运行时必须的页面（需要修改页表项） ，当需要一个页面时，再从外存调入（需要缺页中断机构）。没有空间时，则采用置换算法置换出去（需要考虑置换算法、置换策略、置换时机地点）。6 请求分页需要哪些支持？请求分页的页表机制相对于基本分页应该如何修改？需要有页表机制、地址变换机构、缺页中断机构。页表项应该包括（页号、物理块号、（状态位、访问位、修改位、外存地址）状态位：指示该页是否已经调入内存访问字段：记录该页在一段时间被访问的次数。修改位：调入内存是否被修改过；若改过，则应该讲该页写回外存上，以保证外存保留最新的副本。外存地址：指出该页在外存上的地址。7 带快表的请求分页地址变换过程？缺页中断与一般的中断有什么不同？首先与基本分页一样：计算页号和页内偏移；比较页号和页表长度（大于产生越界中断）；检索快表，快表没有检索内存（内存中有，则更新快表）；内存没有，则产生缺页中断、请求调页最后，找到该页后，修改访问位和修改位，形成物理地址。缺页中断过程：保护CPU现场；从外存中找到该页；内存是否已满， 已满选择一页调出 （如果该页被修改， 需要先写回外存）启动 I/O 读取该页到内存；精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 7 页学而不思则惘，思而不学则殆修改页表中的该项的状态位、访问位、修改位等。恢复 CPU现场。（注： 流程图的话开始结束画椭圆，写开始和结束；一般步骤写矩形框；选择写菱形框，并在菱形的延伸出两条线上写是、否，并指向是、否的下一个步骤）区别有：在指令执行期间产生和处理中断信号、一条指令执行期间可能多次缺页中断。8 虚拟存储器技术中当访问的页面不在内存，且内存无空间时，选择页面置换的算法有哪些？（注：内存刚开始空的时候，也在缺页中断，所以一定也要计入缺页次数）（缺页率 =缺页次数 /总次数）最佳置换算法OPT：往未来置换的方向看，最远不被访问的页置换出去。无法实现，只作为评价。FIFO算法：最早进入内存的最先置换出去。最近最久未使用LRU：基于局部性原理，过去一段时间未访问，则最近的将来也不会访问。往已经置换的方向往回看，最远的被置换出去。使用堆栈。时钟 Clock 算法 NRU：简单的 CLOCK ：看成一个循环的缓冲区；当某一页被替换，则指针指向下一个页面；附加一个使用位u1；只要被访问了就再次置为1；当需要置换出去的时候，就利用指针一个一个扫描u0 的页面； 算法每次经过一个页面就置u0 然后跳到下一个页面；如果所有都是1，则把所有变0 后，找原来最初的位置上的页面；（u0 的过程表示最近没有使用过NRU）改进的 Clock：多附加一个修改位m0，只要该页面被修改过m 1；初始 u=1 m=0；首先找 u=0 m0 的页；没有则找u0 m1 的页，在这步中扫描过的u 都让它 0；（优点在于首先替换没有修改的页）9 什么叫 Belady 异常？哪个页面置换算法会发生？即分配的物理块数增大，缺页次数却不减反而增加的现象。FIFO算法会出现；LRUOPT算法都不会出现。1 页面分配策略有些？固定分配局部置换：只为每个进程分配一定数量的物理块，固定不再改变。 置换时从该进程的内存页面中选择一页置换；可变分配全局置换：OS 自身保持一个空闲物理块队列，缺页时将该队列中一个取出分配。可变分配局部置换：同上， 只是平时置换时置换该进程的内存块，如果频繁置换则从空闲物理块队列中选择一个分配。2 页面调入的时机有哪些？从何处调入的页面？【时机】 预调入策略 （一次性调入相邻的若干页）、请求调页策略 （请求时再调入一页）【何处】外存分为文件区（离散、非连续分配方式）和对换页面的对换区（连续分配方式） ，固分为如下三种：1 系统拥有足够对换区：可从对换区调入所需页面。但是在该进程运行前，需将与进程有关的文件区的文件拷贝到对换区；2 系统缺失足够的对换区：不会修改的文件从文件区调入；会修改的先复制到对换区，再从对换区调入。3UNIX方式：未运行过的页面从文件区调入；曾经运行过然后被调出的（放到了对换区） ，精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 7 页学而不思则惘，思而不学则殆以后再调入的时候从对换区调入。3 什么叫抖动？产生抖动的原因？刚刚换入主存的页面又要换出，而刚刚换出的页面又要换入。某个进程频繁访问的页面数目大于可用的物理块数。4 什么叫工作集 /驻留集？某段时机内， 进程要访问页面的集合。经常使用的页面需要在工作集中，长期不用的需要丢弃。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 7 页