存储器管理

1、物理地址、逻辑地址、虚拟地址和虚拟内存都是什么？

物理地址：是内存单元真正的地址。它是地址转换的最终地址，进程在运行时执行指令和访问数据最后都要通过物理地址从主存中存取。又叫绝对地址。
逻辑地址：是指计算机用户看到的地址。是指在计算机体系结构中是指应用程序角度看到的内存单元（memory cell）、存储单元（storage element）、网络主机（network host）的地址。 逻辑地址往往不同于物理地址（physical address），通过地址翻译器（address translator）或映射函数可以把逻辑地址转化为物理地址。逻辑地址并不一定 是元素存储的真实地址，即数组元素的物理地址（在内存条中所处的位置），并非是连续的，只是操作系统通过地址映射，将逻辑地址映射成连续的。
虚拟地址实际上是操作系统为应用程序提供的一个统一的内存访问接口，这样做的好处是——所有的应用程序只需要面向虚拟地址进行编写，而不用考虑实际的物理地址的使用情况。cup要访问虚拟内存地址时，需要经过通过专用的硬件内存管理单元（memory management unit）MMU来翻译成对应的内存物理地址（地址翻译）成物理地址才能访问。
虚拟内存是计算机系统内存管理的一种技术。它使得应用程序认为它拥有连续的可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。

2、什么是缓冲区溢出？有什么危害？

缓冲区为暂时置放输出或输入资料的内存。
缓冲区溢出是指当计算机向缓冲区填充数据时超出了缓冲区本身的容量，溢出的数据覆盖在合法数据上。
造成原因是程序中没有仔细检查用户输入是否合理。
危害主要有以下两点：程序崩溃导致拒绝服务和跳转并且执行一段恶意代码。

3、页面置换算法有哪些？

请求调页，也称按需调页，即对不在内存中的“页”，当进程执行时要用时才调入，否则有可能到程序结束时也不会调入。而内存中给页面留的位置是有限的，在内存中以帧为单位放置页面。为了防止请求调页的过程出现过多的内存页面错误（即需要的页面当前不在内存中，需要从硬盘中读数据，也即需要做页面的替换）而使得程序执行效率下降，我们需要设计一些页面置换算法，页面按照这些算法进行相互替换时，可以尽量达到较低的错误率。常用的页面置换算法如下：

先进先出置换算法（FIFO）

先进先出，即淘汰最早调入的页面。
实现方法：把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面。队列的最大长度取决于系统为进程分配了多少个内存块。
可能产生Belady异常，指当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。
虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问。算法性能差。

最佳置换算法（OPT）

选未来最远将使用的页淘汰，是一种最优的方案，可以保证缺页率最低。
但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的

最近最久未使用（LRU）算法

即选择最近最久未使用的页面予以淘汰。
实现：赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t。当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面。
该算法的实现需要专门的硬件支持，虽然算法性能好，但是实现困难，开销大。
需要寄存器和栈的硬件支持。LRU是堆栈类算法，理论上可以证明，堆栈类算法不可能出现Belady异常。

时钟（Clock）置换算法

时钟置换算法也叫最近未用算法 NRU（Not RecentlyUsed）。该算法为每个页面设置一位访问位，将内存中的所有页面都通过链接指针链成一个循环队列。
当某页被访问时，其访问位置为1。当需要淘汰-一个页面时，只需检查页的访问位。如果是0，就选择该页换出;如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第- - ~轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描(第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择–个淘汰页面最多会经过两轮扫描)
性能和开销较均衡，又叫最近未用算法。

改进型的时钟置换算法

简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过,就
不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。
改进型的时钟置换算法的思想：综合考虑某一内存页面的访问位和修改位来判断是否置换该页面。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/O操作。修改位=0，表示页面没有被修改过;修改位=1，表示页面被修改过。
用(访问位，修改位)的形式表示各页面状态。如(1, 1)表示一个页面近期被访问过，且被修改过。
算法规则：将所有可能被置换的页面排成一个循环队列，选择一个淘汰页面最多会进行四轮扫描：
第一轮:从当前位置开始扫描到第一个(A =0, M = 0)的帧用于替换。表示该页面最近既未被访问，又
未被修改，是最佳淘汰页；
第二轮:若第一轮扫描失败，则重新扫描，查找第一个(A =1, M = 0)的帧用于替换。本轮将所有扫描
过的帧访问位设为0。表示该页面最近未被访问，但已被修改，并不是很好的淘汰页。
第三轮:若第二轮扫描失败，则重新扫描，查找第一个(A =0, M = 1)的帧用于替换。本轮扫描不修改
任何标志位。表示该页面最近已被访问，但未被修改，该页有可能再被访问。
第四轮:若第三轮扫描失败，则重新扫描，查找第一个A =1, M = 1)的帧用于替换。表示该页最近已
被访问且被修改，该页可能再被访问。
改进型的时钟置换算法的优点：算法开销小，性能好。

4、分页与分段的区别？

相同点
均可离散存储，且需要通过地址映射机构实现地址变换
不同点
(1) 页是信息的物理单位,分页是为了实现非连续分配,以便解决内存碎片问题,提高内存利用率，是系统管理的需要，页的保护和共享受到限制。
段是信息的逻辑单位,它含有一组意义相对完整的信息,分段的目的是为了更好地实现共享,满足用户的需要.便于存储保护和信息的共享。
(2) 页的大小固定,由系统确定,将逻辑地址划分为页号和页内地址是由机器硬件实现的.
而段的长度却不固定,决定于用户所编写的程序,通常由编译程序在对源程序进行编译时根据信息的性质来划分.
(3) 分页的作业地址空间是一维的.分段的地址空间是二维的.
页式，一个程序的各页是根据你的程序空间连续编址的，程序地址空间只有一维；
而段式，一个程序拆分成各段，独立编址（各段都从零开始编址），程序地址空间有两维。
对于页式管理，给出地址a，根据页面大小就可以算出页号和页内偏移地址，所以是一维线性。段式管理则不同，必须给出段号，根据段表找出此段的起始地址，再根据段内地址进行定位，所以是二维的。

5、操作系统在对内存进行管理的时候需要做些什么?

• 内存分配，负责内存空间的分配与回收。
• 内存保护，保证各进程在各自存储空间内运行，互不干扰。
• 地址映射，要提供地址转换功能，负责程序的逻辑地址与物理地址的转换。

• 内存扩充，需要提供某种技术从逻辑上对内存空间进行扩充。

  6、内存是什么，有什么作用？

  内存(Memory)是计算机的重要部件，也称内存储器和主存储器，它用于暂时存放CPU中的运算数据，以及与硬盘等外部存储器交换的数据。
  程序在执行时，程序和其所要访问的数据必须都在内存中。
  在多道程序环境下，系统中有多个程序并发执行，这些程序的数据会被同时放到内存中，区分方法是给内存的存储单元编地址。

  7、内存管理方式有哪些？

  内存分配方式

• 连续分配方式

  • 单一连续分配
  • 固定分区分配
  • 动态分区分配
  • 动态重定位分区分配
• 离散分配方式
  • 基本分页存储管理方式
  • 基本分段存储管理方式

• 虚拟存储

  • 请求分页存储管理方式
  • 请求分段存储管理方式

    连续分配

    指用户程序获得的内存空间具有连续性。

    单一连续分配

    内存被划分为低址部分的系统区和高址部分的用户区。系统区仅提供给OS使用，系统区外的用户区提供给用户使用。
    特点：

• 只适用于 单道程序 的情况。

• 若用户作业比用户区大，则无法运行
• 若用户作业比用户区小，则造成内存浪费

• 设置界限寄存器，限制用户程序访问操作系统

  固定分区分配

  原理

• 将内存用户空间划分为多个固定大小（大小分区可以不等）的区域， 每个区域内只装入一个进程，并发的进程数量取决于分区个数；

• 若当前某进程完成操作释放资源（包括分区），外存后备队列中的适当大小作业被装入分区，获得执行。
• 是最早及最简单的运行多道程序的存储管理方式，实现简单，但会浪费存储空间。

分区方法：

• 等大分区
• 非等大固定分区

缺点：

• 程序的大小受分区大小的限制；程序数受分区数限制；

• 每个分区都有可能产生 内部碎片，引起内存的浪费。

  动态分区分配

  根据进程实际需要动态的分配内存。空闲分区按照某种规则（由分配算法决定）排列成链表或纪录在表格中。作业或进程提出内存请求时，在链表或表格中寻找一个容量满足请求的分区为之分配，回收内存时合并相邻分区，插入空闲区链表或空闲区表格。
  算法：
  首次适应算法
  空闲区按起始地址升序链接为双向链表。
  分配时从链首开始查找第一个容量符合要求的空闲分区进行分配，在将该空闲分区划分出进程所需的空间后，剩余的空闲区域仍需以新空闲分区的身份记入链表，若无法找到满足容量要求的分区，则失败返回。
  优点：优先利用低址部分，保留了高址的大容量空闲区，便于运行大型作业 。
  缺点：低址部分可能出现大量难以利用的小空闲区， 每次查找时会增加开销。
  循环适应算法
  按照空闲区起始地址升序链接为环状链表，设置起始查寻指针，用于指示下一个可用空闲区位置 。
  每次查找时从上次所用分区的下一个空闲区开始，直到找到可以满足容量要求的空闲区，按照申请空间大小划分分区给作业（进程），若找不到这样的分区，则失败返回。
  优点：空闲区分布相对均匀，回收时合并成大空闲区的可能较大，减少查找开销 。
  缺点：缺乏大的空闲区保证大型作业运行。
  最佳适应算法
  按容量升序链接为空闲分区链 ，选择最小的能满足需求的空闲区分配给作业 。
  优点：尽可能的保存较大的空闲区
  缺点：切割后产生的小空闲区的数量不可小觑
  最坏适应算法
  空闲分区按照容量降序链接，选择容量最大的空闲分区分割并分配给作业（进程）
  优点：每次分配的剩余空闲区不会太小，查找效率高，利于中小型作业
  缺点：大型空闲分区少，不利于大作业
  快速适应算法
  按照容量大小对空闲区分类，相同容量的空闲区单独设立空闲分区链表，另外系统中还增设一个空闲区链表管理索引表，用来记录各链表的头指针
  分类时根据进程常用空间大小划分，特殊大小的分区可单独管理或插入容量最接近的链表。
  算法描述 ：根据进程申请空间大小选择最合适的链表，从中取出第一个空间分配给进程即可 。
  优点：查找效率高，不会产生内存碎片，可满足大型作业的空间需求
  缺点：分区回收复杂，系统开销大，各进程使用的分区中空间浪费严重
  伙伴系统（综合了固定分区和动态分区）

  动态重定位分区分配

  动态分区分配+紧凑 。
  地址变换过程发生在程序执行期间，随着指令和数据的访问自动进行。
  作业装入内存后的所有地址都是相对地址，在程序将要执行的时候，才会将相对地址转换为物理地址。
  系统中增设了一个重定位寄存器（即段寄存器、基址寄存器） ，用它来存放程序（数据）在内存中的起始地址。保证转换的快速性。
  程序真正执行时访问的地址是 重定位寄存器中的地址+相对地址 。

  离散分配

  原因：连续分配方式易形成碎片，若紧凑开销大。
  允许作业直接分散的装入到许多不相邻的分区中，无须紧凑。
  分类：

• 分页存储管理：以“页”为单位离散分配内存

• 分段存储管理：以“段”为单位离散分配内存

• 段页式存储管理：页式与段式的结合，广泛采用的存储管理方式

  基本分页存储管理方式

  页面：
  页面：对进程的逻辑地址空间进行分割而产生的若干大小相等的片，每个页面都有自己的编号。
  帧（块、页框）：内存物理空间也被相应分为与页面等大的若干个存储块，且同样有其独有编号。
  分配方式：为进程分配内存时，将进程中的若干页分别放入离散的物理帧中，最后一页可能有内碎片 。
  地址结构：
  
  设给定的逻辑地址为A，页面大小为L，则P=INT[A/L] ，W=[A] MOD L。
  大小：要合适。

• 页面过小 ，优点减少内碎片，提高内存利用率 ，缺点 每个进程占用页面过多，导致页表过长，降低页

面换进换出效率，

• 页面过大，优点减少页表长度，提高换进换出速度，缺点内碎片过大，浪费内存空间

页表
纪录每个进程的各页面与其在内存中的物理帧号的对应关系，进程执行时通过页表寻找数据和指令。每个页表项中都设置存取控制字段，以实现对其对应存储块的读写保护，错误的读写操作会引起系统中断.
地址变换机构
任务：将逻辑地址中的页号转换为内存中的物理块号，而页内地址（位移量）与块内的物理地址一一对应，无须转换。该任务需要页表的帮助。
组成：页表、页表寄存器PTR。
PTR中保存页表在内存中的始址和页表长度，当进程被调度执行时，其页表信息才从PCB中装入PTR 。
变换过程
分页地址变换机构自动将给定逻辑地址分为页号和偏移量两部分，利用特定硬件以页号为索引检索页表，当该页号不超出页表长度时，可由“页表始址+(页号页表项长度)”获得该页的物理块号，并赋值给物理地址寄存器， 接着将偏移量送入物理地址寄存器的块内地址字段就可以得到最终的转换结果。
两次访问内存，第一次获取页表条目以形成物理地址，第二次用于获取数据，这样导致内存访问效率减半 。
具有快表的地址变换机构
增设一个具有并行查寻能力的特殊高速缓存——快表（联想寄存器、翻译后备缓冲器TLB），用以存放最近一段时间甚至当前正在访问的部分页表项。
变换过程
地址变换机构自动将CPU给出的逻辑地址中分离出的页号提交给TLB，若找到了页号也就得到了帧号，可用来访问内存；若在TLB中找不到页号才访问本进程在内存中的页表以得到帧号，同时将页号和帧号添加到TLB（占用新条目或覆盖老条目，内核代码的条目通常不会被覆盖）
命中率
特定页码在TLB中被查到的百分比。
*问题
逻辑地址空间的扩大导致单页表不可用。例如32位逻辑地址空间采用分页系统时，若页面大小为标准值（4KB），则每个进程页表中的页表项将有1M个，每项占用 一字节时，存储页表需要1MB空间。
解决：

• 离散存放：形成两级或多级页表
• 按需调入页表项：利用虚存技术

两级页表
外层页表各表项纪录内层页表分页的物理帧号；内层页表各表项纪录各页面的物理帧号。


页表的离散分配不能解决使用较少内存空间存放大页表的需求.
解决：按需调入页表项：进程或作业装入内存时仅选择当前所需的一批页表项调入内存，以后再根据需要陆续调入以两级页表为例，外层页表必须调入内存，内层页表只调入需要的若干页，内层页是否调入内存需要在外部页表的对应表项的状态位中有所体现，程序运行时若发现该位为“尚未调入”，则产生中断，请求OS调入该页。
仍有问题：
对更加大型的逻辑地址空间（如64位），两级页表无能为力。———多级页表
反置页表
反置页表全OS仅一个，外部页表每个进程一个。
为内存中每个物理块设置一个页表项，并按照物理块号排序，如1号物理块对应的反置页表项为1号。
反置页表项的内容包括所属进程进程标识符和页号，例如进程A（ PID为119 ）的1号页面存储于内存的第2819号物理块中，则在编号为2819的反置页表项中填入存储进程PID（119）和对应该进程的页号（1）
每个进程中要保持一个外部页表，用于记录此进程不在内存的各页分别存储在外存的何处。
地址变换
根据进程标识符和页号检索反置页表，若能找到匹配项，就根据该项的编号找到对应物理块，再根据页内偏移生成物理地址，最后将地址送入地址寄存器；若找不到匹配项，表示该页不在内存，提示出错（无请求调页功能的系统）或调入该页（有请求调页功能的系统）

基本分段存储管理方式

为了简化地址管理，所以将虚拟内存空间中的 虚拟内存 按照其逻辑划分为代码段、数据段、堆段、栈段几部分。编译、连接、加载过程都以段为单位。编译用户程序时，编译器会自动根据输入程序构造段。编译器构造出的各段在内存中处于不同的连续分区，各段可以离散存储。
引入目的：
满足用户在编程和使用上的习惯和需求

• 方便编程：为满足用户作业的逻辑关系，将数据和指令分段存储，其地址由段名和段内偏移量共同组成
• 信息共享（以信息的逻辑单位为基础）
• 信息保护（以信息的逻辑单位为基础）
• 动态增长：保证使用过程中对内存的动态需求
• 动态链接：运行时动态加载需要的目标程序段

段的特点：(用户认为)

• 虚拟内存空间是段的集合。
• 每个段都有其名称和长度。
• 地址是由段名（段号）和段内偏移构成。

现实情况：内存是一个线性字节数组，可以放置指令或数据
位置
内存中设置段表，表中各项指明某段在内存中的基址和段界限，用以实现逻辑地址和物理地址的映射。有时也可以放在一组寄存器中以提高访问速度。
地址变换机构
段表寄存器：存放段表基址和段表长度TL
a、逻辑地址中的段号s与TL比较，若s＞TL，越界中断；反之，根据段表基址和段号所指示的段表项找到所需段在内存中的基址
b、逻辑地址中的段内偏移d和上一步找到的段长SL相比较，若d＞SL，越界中断；反之，将d与段基址相加得到数据物理地址。

仍然需要两次访问内存（第一次访问段表，第二次访问数据），使得内存响应效率降低50％
解决方法：增加快表，用来保存最近访问过的段表项.
信息保护
分段有助于实现将段与对其对应的保护机制相关联。
现代OS中，指令不可自我修改，故指令段只能定义为只读或只执行，内存映射硬件会检查段表项中的保护位，以防止对内存的非法访问（对只读段的写、将代码段视为数据等）。 数据则放在特定数组中，当需要访问数据时会对数组下标进行检测，超界时会产生越界中断。
信息共享
在每个进程的段表中对多进程共享的可重入代码设置一个段表项，当需要使用这部分代码时，应保证在执行时不会修改它，每个进程的私有数据和局部变量必须使用独立的段保存且不提供共享。
可重入代码（纯代码）：允许多个进程同时访问的代码，且为保证每个进程所执行的代码完全相同，决不允许执行过程中修改代码。

• 分页系统信息共享：使用可重入代码时，各进程的部分逻辑页面将被映射到可重入代码使用的各帧中，但其私有数据和局部变量所使用的帧则各不相同，且所有这些页面和帧的对照关系需要存入页表（长度可能会极大）

• 分段系统信息共享：使用可重入代码时，只需在段表中为其设置一个段表项，并将执行时用到的部分数据copy到局部数据区，用来支持对执行时不可避免的代码修改的支持即可

  段页式存储管理

  结合分段和分页思想，先将用户程序分成若干段并分别赋予段名，再将这些段分为若干页
  地址结构：由段号、段内页号和页内地址三项共同构成地址
  
  地址变换机构
  本系统中使用段表寄存器存放段表基址和段表长度TL。
  CPU提供的逻辑地址中的段号S首先和段表长度TL比较，若未越界则根据S和段表基址找到相应段表项中纪录的该段所在页表基址，接着使用段内页号P获得对应页面的页表项位置，从中找到帧号b，最后拼接上页内地址W得到数据的物理地址。
  该过程需要三次访问内存，为提高执行速度，可以增加一个快表，访问数据时利用段号和页号检索它，若可以命中，直接取出物理帧号；否则，进行上述三次内存访问过程获得数据。
  

  虚拟分配

  引入原因
  基本段页式存储管理的缺陷在于作业执行时必须全部装入内存，使得大型作业被拒绝或部分作业需要在外存长期等待。基本存储管理方式的一次性（装入）和驻留性特征使得作业的响应效率大幅降低。
  解决办法

• 物理扩充

• 逻辑扩充

局部性原理
主要分为时间局部性和空间局部性。
程序执行时表现出时间和空间的局限性。一段时间内程序执行局限在某段代码，访问的存储空间也局限于某区域。

• 时间局部性: 如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行;如果某个数据被访

问过，不久之后该数据很可能再次被访问。(因为程序中存在大量的循环)

• 空间局部性:一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。(因为

很多数据在内存中都是连续存放的，并且程序的指令也是顺序地在内存中存放的)
虚拟存储器
具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。
逻辑容量
虚存的逻辑容量由内外存容量之和决定，运行速度接近于内存，每bit成本接近于外存。
特征

• 多次性(作业可被分为多次调入内存,虚存的独有特征)
• 对换性(允许作业换入换出,显著提高内存利用率)
• 虚拟性(虚存对内存实行逻辑扩充)

虚拟性以多次性和对换性为基础，后二者又以离散分配为基础.
实现方法
程序运行前：仅装入当前要运行的主程序需要的部分页面或段。
程序运行时：

• 若要访问的页（段）已装入内存，继续执行
• 若产生缺页或缺段且内存中还有足够的空间，则启动OS的请求调页（段）功能调入需要的页（段）
• 若产生缺页或缺段且内存空间不足时，先启动页（段）置换功能，将内存中暂时不用的页（段）调出内存，接着启动请求调页（段）程序调入需要的页（段）

存储模式
离散存储
分类

• 请求分页系统
  • 在基本分页系统中增加请求调页和页面置换功能
  • 硬件支持：请求分页的页表机制、缺页中断机构、地址变换机构
  • 软件支持：请求调页程序、页面置换程序

• 请求分段系统

  • 在基本分段系统中增加请求调段和段置换功能
  • 硬件和软件支持与请求分页系统类似

    请求分页系统

    实现简单：数据换入和换出的基本单位都是长度固定的页面。
    需要请求分页页表机制、缺页中断机构和地址变换机构的支持。
    与基本分页系统的页表相比，需要增加支持页面换入、换出的数据结构，其页表项如下
    

• 状态位：指示该页是否已被调入内存

• 访问字段：纪录本页在一段时间内被访问的次数或上次访问时间等信息
• 修改位：该页调入内存后是否被修改过，置换页面时若该位表示曾修改过，需要覆盖外存中的副本，以保证外存中的页面始终为最新
• 外存地址：指出该页对应外存物理帧号

缺页中断机构
当所要访问的页面不在内存时，启动缺页中断，请求OS在程序中断期间将需要的页面调入内存。
缺页中断处理过程：保护现场、分析中断原因、转入缺页中断处理程序、恢复现场
特点（与普通中断相比）

• 指令执行期间产生和处理中断信号
• 指令执行时可能会产生多次缺页中断

地址变换机构

内存物理帧分配策略和分配算法
考虑三方面问题

• 最小（最少）物理块数如何确定
• 物理块的分配策略
• 物理块的分配算法

最小物理块数
保证进程运行所需最小物理帧数与其所在硬件结构相关，不同的指令格式、功能和寻址方式对物理帧数的要求不同

• 单字节指令、直接寻址方式：2个帧
• 单字节指令、间接寻址方式：3个帧
• 多字节指令：6个以上的帧

物理帧分配策略
内存可采用固定和可变两种策略进行分配，置换时有全局和局部置换，因此物理帧的分配策略可分为:

• 固定分配局部置换

根据进程类型或程序员要求，为进程分配固定数目的物理帧，进程运行期间不再新增空间，换出时从本进程占有的页面中选择一页；难度在于物理帧数目难以确定，过多或过少都有不良影响.

• 可变分配全局置换

进程获取的物理帧数在运行过程中可以变化，换出时的页面可以是内存中的任意进程的页面，该方法会增加其他进程的缺页率

• 可变分配局部置换

根据进程类型或程序员要求分配初始数量的物理帧，换出时只从本进程占有页面中选择，但若缺页中断经常产生，则为该进程新增部分页面，以使缺页中断发生频度下降，即利用增减帧数量的方法来控制缺页率
物理帧分配算法
采用固定分配策略时，可以使用下述算法：

• 平均分配算法

物理块平均分配给各进程，小进程浪费空间，大进程缺页率高

• 根据进程大小按比例分配

根据本进程页面数与系统中各进程页面数总和之比分配帧，但至少要满足最小物理块要求

• 按优先权分配

高优先权的进程获得的物理帧多将帧分类，一类按比例分，一类专用来满足高优先权进程的额外需求
调页策略
调入时机

• 预调页策略：在程序首次调入时，选择预计不久会被访问的页面调入内存，其性能优劣取决于预测准确度
• 请求调页策略：需要某页面时向OS提出请求，调入的页一定会在短时间内被用到，但一次调入一页使得系统开销大，增加了I/O时间

调入来源

• 来自于对换区：对换区大的系统可直接将进程的所有页面装入对换区，运行时直接从中高速置换
• 来自于文件区：对换区小的系统，其进程页面的最初版本从文件区调入，若在运行时没有修改，置换时不必换出，直接覆盖即可；反之，将修改过的页面换出到对换区，需要时从对换区调入
• UNIX方式：未运行过的页面，放在文件区等待调入；曾经运行过且被换出的页面放在对换区等待再次调入。再配合页面共享机制，使得当前进程所需页面可能已被其他进程调入内存或换出到对换区

调入过程

• 页面不在内存时，进程向cpu发送缺页中断
• 中断处理程序保存现场，转入缺页中断处理过程
• 若内存未满，则换入并修改页表若内存已满，选页换出：换出页未修改者可直接覆盖，已修改者需要保存到磁盘，新页入内存后修改页表，置存在位为1，同时将其写入快表
• 形成物理地址，访问数据

缺页率影响因素：

• 页面大小：页面大缺页率低
• 物理块数：块数多缺页率低
• 页面置换算法
• 程序固有特性：程序的局部化程度越高，缺页率越低

页面置换算法

• 最佳置换算法（OPT)
• 先进先出算法（FIFO）
• 最近最久未使用置换算法（LRU）
• Clock置换算法
• 最少使用置换算法
• 页面缓冲算法

最佳置换算法（OPT)
是理想化算法。该算法选择的换出页面将是以后永不使用的，或是在最长（未来）时间内不再被访问的页面。可以保证最低缺页率。最佳页面的无法预知性使得该算法不可实现，但可以作为评价其他算法的标尺
先进先出算法（FIFO）
换出时选择最早进入内存的页面
实现方法：将所有已调入内存的页面按照不同进程组织为时间升序的队列，并在每个队列中设置替换指针，使其指向驻留在内存中最久的页面。
特点：实现简单，但页面调入的先后顺序不一定符合实际运行规律
最近最久未使用置换算法（LRU）
根据页面调入内存后的使用情况进行选择
选择最近最久未使用的页面予以换出，每个页面的访问字段都纪录了该页面自上次被访问以来所经历的时间t，换出时选择t值最大的页面，即最近最久未使用的页面。
性能较优，其面临的主要问题是如何确定一个按照上次使用时间定义的排序序列，可选择如下两种方式：

• 计数器：每个位于内存中的页面都要配置一个计数器用来标识进入内存的时间
  • 移位寄存器：每个页面配置一个n位移位寄存器，当进程访问某页面时，将其最高位设置为1，每过一个时钟周期将其右移一位。换出时选择移位寄存器值最小的页面
  • 逻辑时钟：每个页面项中设置一个使用时间域，每次内存引用时，时钟寄存器的内容会复制到相应页的使用时间域中。换出时选择该域中值最小的页面。
  • 该算法需要搜索页表以查找计数值最小的页面，系统的时空开销需要考虑
• 页码堆栈：每当引用一个已在堆栈的页时，都将该页从堆栈中删除并压入顶部
  • 堆栈使用双向链表实现
  • 进程访问某页面时，若该页在栈内，则从中删除并压入栈顶；若该页不在栈内，则从栈底删除最近最久未使用的页面，并将新页面压入栈顶
  • 该算法中，栈顶总是最近访问的页面，栈底总是最近最久未使用的页面

最少使用置换算法
通过在各页表项中设置一个纪录访问次数的计数器，可以形成LFU算法。
由于活跃页应该有较大的访问次数纪录值，因此可以将该计数器值最小的页面换出。
每次访问某页时，将移位寄存器的最高位置位，每隔一定时间右移一次，则最近一段时间内使用最少的页面其按位相加之和最小。
Clock置换算法
对LRU的改进，硬件支持要求低。
使用访问位帮助实现页置换：

• 内存中所有页面链接为一个循环队列
• 访问位存在于页表项内，初值为0，每当读写一个页时均对其硬件置位
• 分类：基本clock置换算法（二次机会算法）和改进型clock置换算法

二次机会算法
算法思想：选择换出页时首先检查访问位，若其值为0就直接置换该页；若为1就清零其访问位，且设其到达时间为当前时间，接着对下一个页面进行同样的检查。
实现方法：采用循环队列。用一个指针标识下一个要置换的页，当需要一个帧时，指针向前移动直到找到一个访问位为0的页（移动的同时清零访问位），新页将插入该页位置
最坏情况：所有页面的访问位均已清零，指针会遍历整个循环队列，以便给所有页面第二次机会，此时再选择页时将转变为FIFO置换
改进型clock置换算法
算法思想：将访问位和修改位两个字段组成有序对（A,M）来改进上述算法，其中有序对的组合可能有：

• (0,0)最近没有使用且没有修改——用于置换的最佳页面，若换出需要I/O一次
• (0,1)最近没有使用但修改过——换出前需要将页写入外存，若换出需要I/O二次
• (1,0)最近使用过但未修改——可能很快要再使用，若换出需要I/O一次
• (1,1)最近使用过且修改过——可能很快要再使用，且换出前需要将页面写入外存，若换出需要I/O二次

为修改过的页面赋予较高优先级，降低了I/O次数，但可能经过多轮扫描才能找到可以用来置换的页面，算法运行开销增大。
页面缓冲算法
采用可变分配和局部置换方式，以及FIFO算法。

• 该算法中要求设置两个链表——空闲帧（页面）链表和已修改帧（页面）链表，被选中的页面若未被修改就插入前一链表，否则插入后一链表。
• 被插入空闲帧链表的页面并不换出内存，将来直接被覆盖；被插入已修改链表的页面暂时不写入磁盘，待累积达到一定数量时才调出内存
• 当进程缺页率低时，新调入的页面在本进程中局部置换；当进程缺页率高时，新调入的页面直接使用空闲页面链表的第一个元素
• 这种方法可以显著减少I/O次数，且能以较小系统开销将这些页面再次分配给原进程使用

访问时间
具有快表的请求分页管理方式中有三种内存访问操作，其有效内存访问时间EAT也不同。

• 页在内存，且页表项在快表
  • EAT=λ+t （ λ：访快表时间，t访内存时间）
  • 访快表一次生成物理地址，访内存寻数据
• 页在内存，且页表项不在快表
  • EAT= λ+t+λ+t=2*(λ+t)
  • 访快表一次未命中，访页表一次生成物理地址，再次访快表一次添加页表项，最后访问内存数据
• 页不在内存
  • EAT= λ+t+ε+ λ+t （ ε：缺页中断处理时间）
  • 访快表未命中，访页表发现页不在内存，做缺页中断处理，修改页表，访问数据

颠簸（抖动）
某进程由于缺页而产生置换，但在不久又请求新的页面甚至是刚换出的页面，需要再次置换，这种频繁的页调度行为称为颠簸或抖动。
若一个进程在换页上使用的时间多于执行时间，称这个进程在抖动。
采用全局置换算法可能导致系统颠簸。
工作集理论
最近n次内存访问的页面集合，数字n被称为工作集窗口，也就是工作集的大小。
经常被使用的页面会在工作集中，而若一个页面不再被使用，将会被从工作集中丢弃。当一个进程寻址一个不在工作集内的页面时，会产生一个缺页中断。在处理缺页中断时，更新工作集并在需要时从磁盘中读入此页面。
原理

• 让操作系统监视各个进程的工作集，主要是监视各个工作集的大小（窗口大小）。
• 正确选择工作集窗口大小，对存储器的有效利用率和系统吞吐量的提高都将产生重要影响。

抖动预防

• 采取局部置换策略
  • 将抖动限制在进程级
  • 简单易行，但抖动进程会加入外存等待队列，导致其他进程缺页处理时间增长
• 把工作集算法融入处理机调度中
  • 当CPU利用率低下时，先检查每个进程的内存驻留页面是否足够
  • 若是则装入新作业以增加多道程序度，若否则将物理帧优先分配给缺页率高的进程，不再装入新作业
• 利用“L=S”准则调节缺页率
  • L：平均缺页间隔时间，S：平均缺页处理时间
  • L>S：缺页率低，磁盘性能利用不充分
  • L<S：缺页率高，磁盘处理能力已经不能满足缺页处理要求
  • L=S：磁盘和CPU的处理能力最大化

• 选择暂停的进程

  • 采取与CPU调度算法一致的策略，选优先级低、占据内存空间大、剩余执行时间长的进程

    请求分段系统

    在基本段式管理基础上增加请求调段功能和段置换功能。
    运行时先调入若干分段，需要新段时置换暂时不用的段
    硬件支持：段表机制、缺段中断机构、地址变换机构。
    段表：
    

• 存取方式：标识存取属性为读、写、执行的组合

• 增补位：请求分段存储管理的特有字段，表示本段运行过程中是否有动态增长
• 访问字段A、修改位M、状态位P、外存基址的定义同页式管理

缺段中断机构
、
地址变换机构

分段的共享
共享段表
各共享分段在共享段表中均有一对应表项，其中含有段号、共享进程计数器、存取控制字段等。

• 共享进程计数器：纪录当前有多少个进程共享该段
• 段号：某进程使用该共享段时为其取的段号码
• 存取控制字段：说明不同进程的操作权限

分配
第一个使用共享段的进程促使系统为共享段分配空间，并在其自身段表项中纪录该空间基址，同时设置共享进程计数器为1；后继申请者只需在自身段表项中设置相应字段即可，同时将共享进程计数器加1
回收
共享某段的进程释放该段时检查共享进程计数器的值，若为1就释放物理空间并修改自身段表项的相关字段；若不为1，仅需修改自身段表项的相关字段，并对共享进程计数器减1。
保护措施

• 越界检查：段号不能超过段表长度、段内偏移不能超过段长
• 存取控制检查：不同进程对同一个共享分段的存取控制权限（只读、读写、只执行）不同，为各进程设置存取权限时要同时保证信息安全和运行需要
• 环保护机构：根据程序的重要程度和关联度将其分类，分别放置在三层软件环中，各程序的访问和调用遵循如下原则
  • 访问：限制在本环或低特权环中
  • 调用：限制在本环或高特权环中
  • 高特权环编号小且接近底层，低特权环编号大且接近用户

    8、什么是快表，你知道多少关于快表的知识？

    快表，又称联想寄存器(TLB) ，是一种访问速度比内存快很多的高速缓冲存储器，用来存放当前访问的
    若干页表项，以加速地址变换的过程。与此对应，内存中的页表常称为慢表。

    9、地址变换中，有快表和没快表，有什么区别？

    | | 地址变换过程 | 访问一个逻辑地址的访存次数 | | —- | —- | —- | | 基本地址变换机构 | ①算页号、页内偏移量 ②检查页号合法性 ③查页表，找到页面存放的内存块号 ④根据内存块号与页内偏移量得到物理地址 ⑤访问目标内存单元 | 两次访存 | | 具有快表的基本地址变换机构 | ①算页号、页内偏移量 ②检查页号合法性 ③查快表。若命中，即可知道页面存放的内存块号，可直接进行⑤;若未命中则进行④ ④查页表，找到页面存放的内存块号，并且将页表项复制到快表中 ⑤根据内存块号与页内偏移量得到物理地址 ⑥访问目标内存单元 | 快表命中，只需一次访存快表未命中， 需要两次访存 |

10、抖动你知道是什么吗？它也叫颠簸现象

刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为
抖动，或颠簸。产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数(分配给进程的物
理块不够) 。
为进程分配的物理块太少，会使进程发生抖动现象。为进程分配的物理块太多，又会降低系统整体的并
发度，降低某些资源的利用率 。
为了研究为应该为每个进程分配多少个物理块，Denning 提出了进程“工作集” 的概念。

11、对换是什么？

多道程序环境下的对换技术指：
把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存的备份存储空间，以便腾出足够的内存空间，再把备份存储空间中已具备运行条件的进程或进程需要的程序和数据调入内存.
意义：
对换是提高内存利用率的有效措施，可直接提高CPU利用率和系统吞吐量
理想情况下，内存管理器能以足够快的速度对换进程，以便当CPU工作时总有进程在内存中等待执行。
对换类型：整体对换和页面（分段）对换
对换空间的管理-目标：

• 对文件区：主要目标是提高文件存储空间利用率，次要目标是提高对文件的访问速度。采用离散分配方式
• 对对换空间：主要目标是提高进程换入和换出的速度，次要目标是提高文件存储空间的利用率。 采用连续分配方式，较少考虑外存碎片

换入和换出
对换策略的某些变种常被用于基于优先权的调度算法中，即高优先级进程到达且请求CPU服务时，内存管理器首先对换出低优先级的进程，以便装入和执行高优先级的进程，待其执行完毕，低优先级进程交换回内存继续执行，这种对换有时被称为换出（roll out）、换入（roll in）。

• 换入进程通常需要对换回它原来所占有的内存空间

这一方式的实现取决于地址捆绑方式：若捆绑发生在编译或加载时，则换入时必须回到原来位置；若是运行时捆绑，则进程可以改变位置

• 对换需要备份存储空间

备份存储空间通常是快速磁盘，且位于独立分区，采用特殊文件系统，其空间采用连续分配方式，较少考虑外存碎片问题

• 对换工作只有在多道程序环境中发生内存空间紧张的情况下才会启动，通常不执行

Linux系统安装时通常需要划分swap分区。

12、存储器的扩充方式有哪些？

• 覆盖：由应用程序控制
• 对换和虚拟存储：由OS控制

覆盖

• 在任何时候只在内存中保留所需的最基本指令和数据，当需要其他指令时，它们会装入到不再需要的指令所占用的空间内。
• 程序占用的内存被分为固定区和覆盖区，前者放置的是在程序运行期间一直起作用的指令和数据，后者放置一段时间内有效的指令和数据。
• 覆盖区的指令和数据在完成当前任务后失效，系统等待其退出内存后再选择下一个进程及其运行所需数据。

是什么，特点是？
由于程序运行时并非任何时候都要访问程序及数据的各个部分（尤其是大程序），因此可以把用户空间分成为一个固定区和若干个覆盖区。将经常活跃的部分放在固定区，其余部分按照调用关系分段，首先将那些即将要访问的段放入覆盖区，其他段放在外存中，在需要调用前，系统将其调入覆盖区，替换覆盖区中原有的段。
覆盖技术的特点：是打破了必须将一个进程的全部信息装入内存后才能运行的限制，但当同时运行程序的代码量大于主存时仍不能运行，再而，大家要注意到，内存中能够更新的地方只有覆盖区的段，不在覆盖区的段会常驻内存。

13、对换和覆盖有什么区别？

交换技术主要是在不同进程（或作业）之间进行，而覆盖则用于同一程序或进程中。

14、内存对换是什么？有什么特点？什么时候发生？

交换(对换)技术的设计思想：内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已
具备运行条件的进程换入内存(进程在内存与磁盘间动态调度)
换入：把准备好竞争CPU运行的程序从辅存移到内存。
换出：把处于等待状态（或CPU调度原则下被剥夺运行权力）的程序从内存移到辅存，把内存空间腾出
来。
内存交换通常在许多进程运行且内存吃紧时进行，而系统负荷降低就暂停。例如:在发现许多进程运行时经常发生缺页，就说明内存紧张，此时可以换出一些进程;如果缺页率明显下降，就可以暂停换出。

15、对换空间和虚拟内存什么关系？

对换空间
Linux 中的对换空间（Swap space）在物理内存（RAM）被充满时被使用。
如果系统需要更多的内存资源，而物理内存已经充满，内存中不活跃的页就会被移到交换空间去。虽然交换空间可以为带有少量内存的机器提供帮助，但是这种方法不应该被当做是对内存的取代。交换空间位于硬盘驱动器上，它比进入物理内存要慢。
交换空间可以是一个专用的交换分区，交换文件，或两者的组合。
交换空间的总大小应该相当于你的计算机内存的两倍和 32 MB这两个值中较大的一个，但是它不能超过
2048MB（2 GB）。
虚拟内存
虚拟内存是文件数据交叉链接的活动文件。是WINDOWS目录下的一个”WIN386.SWP”文件，这个文件
会不断地扩大和自动缩小。
就速度方面而言,CPU的L1和L2缓存速度最快，内存次之，硬盘再次之。但是虚拟内存使用的是硬盘的空间，为什么我们要使用速度最慢的硬盘来做 为虚拟内存呢？因为电脑中所有运行的程序都需要经过内存来执行，如果执行的程序很大或很多，就会导致我们只有可怜的256M/512M内存消耗殆尽。而硬盘空间动辄几十G上百G，为了解决这个问题，Windows中运用了虚拟内存技术，即拿出一部分硬盘空间来充当内存使用。

16、内存交换中，被换出的进程保存在哪里？

保存在磁盘中，也就是外存中。具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区两部分。文件区主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式;对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区。由于对换的速度直接影响到系统的整体速度，因此对换区空间的管理主要追求换入换出速度，因此通常对换区采用连续分配方式 。总之，对换区的I/O速度比文件区的更快。

17、内存交换中，被换出的进程保存在哪里？

可优先换出阻塞进程;可换出优先级低的进程;为了防止优先级低的进程在被调入内存后很快又被换出，
有的系统还会考虑进程在内存的驻留时间。(注意: PCB 会常驻内存，不会被换出外存）

18、内存交换你知道有哪些需要注意的关键点吗？

1. 交换需要备份存储，通常是快速磁盘，它必须足够大，并且提供对这些内存映像的直接访问。
   2. 为了有效使用CPU，需要每个进程的执行时间比交换时间长，而影响交换时间的主要是转移时间，转移时间与所交换的空间内存成正比。
   3. 如果换出进程，比如确保该进程的内存空间成正比。
   4. 交换空间通常作为磁盘的一整块，且独立于文件系统，因此使用就可能很快。
   5. 交换通常在有许多进程运行且内存空间吃紧时开始启动，而系统负荷降低就暂停。
   6. 普通交换使用不多，但交换的策略的某些变种在许多系统中（如UNIX系统）仍然发挥作用。

   19、虚拟技术你了解吗？

   虚拟技术把一个物理实体转换为多个逻辑实体。
   主要有两种虚拟技术：时（时间）分复用技术和空（空间）分复用技术。
   多进程与多线程：多个进程能在同一个处理器上并发执行使用了时分复用技术，让每个进程轮流占用处理器，每次只执行一小个时间片并快速切换。
   虚拟内存使用了空分复用技术，它将物理内存抽象为地址空间，每个进程都有各自的地址空间。地址空间的页被映射到物理内存，地址空间的页并不需要全部在物理内存中，当使用到一个没有在物理内存的页时，执行页面置换算法，将该页置换到内存中。

   19、虚拟内存的目的是什么？

   虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。
   为了更好的管理内存，操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。
   这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败的指令。
   从上面的描述中可以看出，虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存，也就是说一个程序不需要全部调入内存就可以运行，这使得有限的内存运行大程序成为可能。

   20、程序从堆中动态分配内存时，虚拟内存上怎么操作的

   页表：是一个存放在物理内存中的数据结构，它记录了虚拟页与物理页的映射关系
   在进行动态内存分配时，例如malloc()函数或者其他高级语言中的new关键字，操作系统会在硬盘中创建或申请一段虚拟内存空间，并更新到页表（分配一个页表条目（PTE），使该PTE指向硬盘上这个新创建的虚拟页），通过PTE建立虚拟页和物理页的映射关系。

   21、虚拟内存？使⽤虚拟内存的优点？什么是虚拟地址空间？

   1) 虚拟内存，虚拟内存是⼀种内存管理技术，它会使程序⾃⼰认为⾃⼰拥有⼀块很⼤且连续的内存，然⽽，这个程序在内存中不是连续的，并且有些还会在磁盘上，在需要时进⾏数据交换;
   2) 优点：可以弥补物理内存⼤⼩的不⾜；⼀定程度的提⾼反应速度；减少对物理内存的读取从⽽保护内存延⻓内存使⽤寿命；
   3) 缺点：占⽤⼀定的物理硬盘空间；加⼤了对硬盘的读写；设置不得当会影响整机稳定性与速度。
   4) 虚拟地址空间是对于⼀个单⼀进程的概念，这个进程看到的将是地址从0000开始的整个内存空间。虚拟存储器是⼀个抽象概念，它为每⼀个进程提供了⼀个假象，好像每⼀个进程都在独占的使⽤主存。每个进程看到的存储器都是⼀致的，称为虚拟地址空间。从最低的地址看起：程序代码和数据，堆，共享库，栈，内核虚拟存储器。⼤多数计算机的字⻓都是32位，这就限制了虚拟地址空间为4GB。

   22、碎片是什么？怎么解决？

   内存中出现的不能被利用的小分区。

• 外部碎片：进程装入和移出时形成的不连续且长期无法满足作业对空间需求的小分区。内存中某些空闲区因为比较小，而难以利用上，一般出现在内存动态分配方式中
• 内部碎片：大小为n的分区中装入大小为m的作业，且n＞m时，该分区中形成的大小为n-m的未使用空间顺序搜索类的分配算法均存在外部碎片问题。分配给某些进程的内存区域中有些部分没用上，常见于固定分配方式。

解决：

• 拼接（紧凑）：将内存中所有作业进行移动，使之前后相邻，则原来分散的小空闲区可以成为一个大空闲分区。紧凑过后的某些用户程序在内存中的位置发生变化，需要对程序和数据进行动态重定位以保证其执行，且相对费时。
• 内存交换

  23、为什么分段式存储管理有外部碎片而无内部碎片？为什么固定分区分配有内部碎片而不会有外部碎片？

  分段式分配是按需分配，而固定式分配是固定分配的方式