储存管理 ######################################## 虚拟储存器 ######################################## - 管理程序可以将程序按需调入或调出内存 - 虚拟储存器的容量为内、外存之和 - 每个程序都有自己的虚拟储存器 地址重定位 **************************************** 进程在编译时获得的地址是以0为起始地址的虚拟地址，要将虚拟地址转化为内存的真实地址，需要用到 ``地址重定位`` （或地址映射）。 实现地址重定位的方法有两种：``静态地址重定位`` 和 ``动态地址重定位`` 静态地址重定位 ======================================== 静态地址重定位由程序的装配程序完成地址映射工作，虚拟地址一旦映射为内存中的真实地址便无法改变。 优点： - 不需要硬件支持 缺点： - 程序在执行前必须将所有相关部分全部装入 - 程序在装入内存后无法移动 - 程序在内存中必须占据连续的内存空间，程序和数据之间很难共享 - 无法实现虚拟储存器 动态地址重定位 ======================================== 动态地址重定位是在程序执行期间，由 CPU 和寄存器共同完成地址映射。动态地址重定位依赖于一个（或多个）基址寄存器 BR 和一个（或多个）虚拟地址寄存器。 其中，基址寄存器储存了程序在内存中的实际地址，虚拟地址寄存器储存了程序代码在其虚拟空间中的地址，程序代码在内存中的实际地址为： ``[BR] + [VR]`` 。（ []代表获取寄存器中的内容 ） .. image:: assets/动态地址重定位.jpg :scale: 20 优点： - 可以对内存进行非连续分配 - 可以按需、动态地将程序调入或调出内存 - 程序段之间容易共享 内外存数据传输控制 **************************************** 虚拟储存器需要动态地将程序调入或调出内存，这就要求对程序执行时哪些部分需要调入，哪些部分需要需要调出进行决策。决策方式可以由程序控制，也可以由操作系统控制。 #. 覆盖（overlay） 覆盖技术将程序获取的内存分为常驻区和可覆盖区，当可覆盖区内的数据不需要使用后，后来的数据可以覆盖已经使用的数据占用的内存 - 覆盖主要发生在同一个进程中 - 程序控制内外存数据交换 - 用户必须清楚了解程序结构 - 程序段的最大长度依然受内存容量制约 #. 交换（swaping） 操作系统将处于等待状态下的程序 **换出** 到外存，将准备就绪的程序 **换入** 到内存 - 交换发生在进程之间 - 操作系统控制数据交换 - 处于等待状态的进程将被调出内存，处于就绪状态的进程将被调入内存 - 一般不进行部分交换，而是直接将整个进程进行调入或调出 #. 请求调入（on demand） - 操作系统控制数据交换 - 当程序要访问的数据不存在时，操作系统将缺少的数据调入内存 #. 预调入（on prefetch） - 操作系统控制数据交换 - 操作系统将可能将被访问的数据调入内存 .. note:: 只有请求调入和预调入方式可以实现不受内存容量限制的虚拟储存器 内存信息的保护 **************************************** 由于内存被所有程序共享，因此，除了被允许的部分进行共享外，又要限制程序仅能在自己的储存区活动，而不会破坏其他进程的数据。内存保护方法有硬件法、软件法和软硬件保护法。具体方法如下： #. 上下界保护法 - 硬件法 - 每个程序将被设置上下界寄存器，上下界寄存器限制了程序访问的范围 - 若访问的范围超出上下界，则产生越界中断 #. 保护键法 - 软件法 - 为储存块分配单独的保护键 - 保护键可以设置为保护读、保护写、保护读写、不受保护 .. image:: assets/保护键法.jpg :scale: 20 #. 界限寄存器和CPU状态共同保护 - 软硬件共同保护 - 用户态进程只能访问界限寄存器规定范围内的部分 - 核心态进程可以访问整个内存地址空间 分区储存管理 **************************************** 分区储存管理将内存划分为不同的分区，通过为程序的数据分配不同的分区来满足并发的需求。根据分区的时机不同，可以分为： - 固定分区法：分区在加载程序之前进行划分。分区一旦划分，则程序的整个执行过程中分区不会再发生改变。 - 动态分区法：系统在程序的执行过程中根据程序的情况进行内存的分配和回收。 分区储存管理通过 ``分区说明表`` 管理内存。该表记录了当前内存的分区大小、数量、分配情况等数据。 分区的分配和回收 ======================================== 固定分区在程序加载时找出满足需求的空间，并将其分配给程序，结束后回收内存。 动态分区的回收有以下几种算法： - 最先适应算法：系统从找到的第一个满足需求的内存中划分内存分配给程序。这种方法尽可能利用了低地址空间 - 最佳适应算法：系统从最接近程序需要的分区中划分内存分配给程序。这种方法会造成内存碎片比较多 - 最坏适应算法：系统从最大的空闲分区中划分内存并分配给程序 .. note:: 分区储存管理划分的内存页面比较大，有以下特点： - 比较简单 - 内存碎片问题严重 - 内存利用率不高 页式储存管理 **************************************** 相比分区储存管理而言，页式储存管理将内存划分为更小的、相同大小的页。页式存储管理解决了以下问题： - 内存中的碎片大小绝对不会大于一个页的大小 - 程序分配的内存从连续分配变为不连续分配 - 页式存储管理使用 ``请求调入`` 或 ``预调入`` 的方式交换内存数据 页式内存管理同样分为静态和动态两种，静态需要将程序的所有数据装入内存，解决了内存碎片的问题。 在发生缺页中断时，有以下几种算法： - :abbr:`最佳置换 (OPT)` 算法：理想状态下的，实际上不可能。就是将永不使用的页面置换出去 - :abbr:`先进先出 (FIFO)` 算法：将最旧的页面置换出去 - :abbr:`最久未使用 (LRU)` 算法：将最久没有使用的页面置换出去 - :abbr:`时钟 (Clock)` 置换算法：又称为最近未使用算法。 - 采用 FIFO 算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象，这是由 Belady 于 1969 年发现，故称为 Belady 异常，只有 FIFO 算法可能出现 Belady 异常，而 LRU 和 OPT 算法永远不会出现 Belady 异常。 - LRU 性能较好，但需要寄存器和栈的硬件支持。LRU 是堆栈类的算法。理论上可以证明，堆栈类算法不可能出现 Belady 异常。FIFO 算法基于队列实现，不是堆栈类算法。 - 时钟算法可以简述如下：给内存页加上一个标志位，每当页面被使用时就将此标志为设为 1。用于替换的候选帧集合看做一个循环缓冲区，并且有一个指针与之相关联。当某一页被替换时，该指针被设置成指向缓冲区中的下一帧。当需要替换一页时，操作系统扫描缓冲区，以查找使用位被置为 0 的一帧。每当遇到一个使用位为 1 的帧时，操作系统就将该位重新置为 0；如果在这个过程开始时，缓冲区中所有帧的使用位均为 0，则选择遇到的第一个帧替换；如果所有帧的使用位均为 1, 则指针在缓冲区中完整地循环一周，把所有使用位都置为 0，并且停留在最初的位置上，替换该帧中的页 CLOCK 算法的性能比较接近 LRU，而通过增加使用的位数目，可以使得 CLOCK 算法更加高效。在使用位的基础上再增加一个修改位，则得到改进型的 CLOCK 置换算法。这样，每一帧都处于以下四种情况之一： - 最近未被访问，也未被修改(u=0, m=0)。 - 最近被访问，但未被修改(u=1, m=0)。 - 最近未被访问，但被修改(u=0, m=1)。 - 最近被访问，被修改(u=1, m=1)。 算法执行如下操作步骤： - 从指针的当前位置开始，扫描帧缓冲区。在这次扫描过程中，对使用位不做任何修改。选择遇到的一个帧 (u=0, m=0) 用于替换。 - 如果第 1)步失败，则重新扫描，查找 (u=0, m=1) 的帧。选择遇到的第一个这样的帧用于替换。在这次扫描过程中，对每个跳过的帧，把它的使用位设置成 0。 - 如果第 2)步失败，指针将回到它的最初位置，并且集合中所有帧的使用位均为 0。重复第 1 步，并且如果有必要，重复第 2 步。这样将可以找到供替换的帧。 改进型的 CLOCK 算法优于简单 CLOCK 算法之处在于替换时首选没有变化的页。由于修改过的页在被替换之前必须写回，因而这样做会节省时间。 .. note:: - 最常使用的就是最近最少使用算法 - 另外还有一种 LRU-K 的算法，称为最久未使用 K 次淘汰算法。相比 LRU 而言，其避免了大量冷数据的情况 .. seealso:: - `Belady异常 `_ - `操作系统之页面置换算法 `_ 地址变换 ======================================== 页式内存管理需要三种表： - 页表：每个程序一张，用于记录程序的虚拟地址 - 请求表：整个系统一张，用于记录虚拟地址在内存中的实际地址 - 储存页面表：整个系统一张，用于记录内存中各页面的分配情况 在动态管理中，当程序请求的页面不在内存中时，将会发生 ``缺页中断``。 如果系统中的刚刚调入的页面又被调出，而后又重复此动作，导致系统的页面调度非常频繁，将导致系统运行的大部分时间都处于页面调度中，这种情况成为 ``抖动`` 现象。 段式内存管理 **************************************** 分区和页式内存管理时进程的空间是线性的，而段式内存管理则将内存管理拓展为二维。段式内存管理将程序分为数据段和程序段，主要目的是权限管理 总结 **************************************** 首先，段式、页式和段页式内存管理都涉及到了内存的换入换出，因此都可能发生内存抖动的情况 第二，三级页表的索引上限是 4GB，四级页表的索引上限是 256GB 为了防止不同进程同一时刻在物理内存中运行而对物理内存的争夺和践踏，采用了虚拟内存。 [#newVir]_ 虚拟内存技术使得不同进程在运行过程中，它所看到的是自己独自占有了当前系统的 4G 内存。所有进程共享同一物理内存，每个进程只把自己目前需要的虚拟内存空间映射并存储到物理内存上。 事实上，在每个进程创建加载时，内核只是为进程 “创建” 了虚拟内存的布局，具体就是初始化进程控制表中内存相关的链表，实际上并不立即就把虚拟内存对应位置的程序数据和代码（比如. text .data 段）拷贝到物理内存中，只是建立好虚拟内存和磁盘文件之间的映射就好（叫做存储器映射），等到运行到对应的程序时，才会通过缺页异常，来拷贝数据。还有进程运行过程中，要动态分配内存，比如 malloc 时，也只是分配了虚拟内存，即为这块虚拟内存对应的页表项做相应设置，当进程真正访问到此数据时，才引发缺页异常。 请求分页系统、请求分段系统和请求段页式系统都是针对虚拟内存的，通过请求实现内存与外存的信息置换。 虚拟内存的好处： #. 扩大地址空间； #. 内存保护：每个进程运行在各自的虚拟内存地址空间，互相不能干扰对方。虚存还对特定的内存地址提供写保护，可以防止代码或数据被恶意篡改。 #. 公平内存分配。采用了虚存之后，每个进程都相当于有同样大小的虚存空间。 #. 当进程通信时，可采用虚存共享的方式实现。 #. 当不同的进程使用同样的代码时，比如库文件中的代码，物理内存中可以只存储一份这样的代码，不同的进程只需要把自己的虚拟内存映射过去就可以了，节省内存 #. 虚拟内存很适合在多道程序设计系统中使用，许多程序的片段同时保存在内存中。当一个程序等待它的一部分读入内存时，可以把 CPU 交给另一个进程使用。在内存中可以保留多个进程，系统并发度提高 #. 在程序需要分配连续的内存空间的时候，只需要在虚拟内存空间分配连续空间，而不需要实际物理内存的连续空间，可以利用碎片 虚拟内存的代价： #. 虚存的管理需要建立很多数据结构，这些数据结构要占用额外的内存 #. 虚拟地址到物理地址的转换，增加了指令的执行时间。 #. 页面的换入换出需要磁盘 I/O，这是很耗时的 #. 如果一页中只有一部分数据，会浪费内存。 .. [#newVir] `【C++工程师面试宝典】学习说明_互联网校招面试真题面经汇总 `_