操作系统八内存管理

CＰＵ直接访问的存储器只有内存和处理器内的寄存器。

1.基本硬件

      CPU可以在一个cpu时钟内执行一个或多个其内置寄存器的指令。而访问内存需多个cpu时钟。由于内存频繁访问，可以再cpu与内存之间增加高速缓存

为确保进程有独立的内存空间，可用基地址寄存器和界限地址寄存器来确立一个合法地址以供其他进程访问。基地址寄存器含有最小的合法物理内存地址，界限地址寄存器决定合法地址大小。如基地址和界限地址寄存器分别为30050和120900，那么合法地址为30050到420950

2.逻辑地址空间与物理地址空间

      内存在字节的地址为物理地址，cpu生成的地址为逻辑地址。通常逻辑地址为虚拟地址，从虚拟地址到物理地址的映射是由称为内存管理设备单元MMU的硬件来完成的。

      用户进程只生成逻辑地址，且认为其地址空间为0到max。逻辑地址使用前需映射到内存的物理地址。MMU动态的将逻辑地址加上重定位寄存器的值后映射成物理地址。映射后的物理地址再送交内存单元。

3.连续分配内存

     内存通常分为两个区域，分别驻留操作系统和用户进程。由于中断向量通常位于低内存，操作系统也放在低内存。

3.1内存映射与保护

      通过重定位寄存器和界限地址寄存器可保护内存进程的独立空间。当cpu调度器选择一个进程执行时，作为上下文切换的一部分，调度程序会用正确的值初始化重定位寄存器和界限地址寄存器，保证其他进程不受该进程运行所影响。

3.2内存分配

      最为简单的内存分配方法是MFT，即将内存分为多个固定大小的分区，一个分区容纳一个进程。MFT已不再使用，MVT是他的推广，主用用于批处理系统。

      在可变分区方案里，系统中有一个表用来记录那些内存占用还是未占用。当有新进程需要内存时，为该内存寻找足够大的孔，从这个孔中为该进程分配所需的内存，孔内未分配的内存可为其他进程所用。从一组可用孔中选择一个空闲孔最常用的方法有：首次适应、最佳适应、最差适应。首次适应最快最好

      首次适应和最佳适应都有外部碎片问题。并不连续的小内存称为碎片。 解决碎片问题方法之一是允许物理地址空间为非连续：分页与分段。

4.分页

      传统上，分页由硬件处理。最近的设计是通过将硬件和系统相配合来实现分页的。

      进程需要在内存中以便运行，不过进程可以暂时从内存中交换到备份存储，当需要再次执行时再调回到内存中。如果进程地址绑定方式是在汇编时或加载时所定的，他只得移到原来内存空间。如果绑定是在运行时才确定，由于物理地址是在运行时才确定的，进程可移到不同地址空间。

4.1基本方法

      基本方法涉及将物理内存分为固定大小的块，称为帧（frame），而将逻辑内存也分为同样大小的块，称为页。当执行进程时，其页从备份存储（他也分固定大小的块，大小与内存帧一样）中调入到可用的内存帧中。

      由CPU生成的每个地址分为两个部分：页号P和页偏移d,页号作为页表的索引。页表包含每页所在物理内存的基地址，这些基地址与页偏移的组合就形成了物理地址，可送交给物理单元。

      页与帧的大小一样，是由硬件决定的。页的大小通常为2的幂，方便将逻辑地址转为页号和页偏移，根据计算机结构的不同，从512B到16M不等。

      当进程需要执行时，根据进程的大小计算页数n,从而内存中也应该至少有n个帧用来分配给新进程。进程的第一页装入一个分配的帧，帧号放入进程的页表中。

      如下图所示

      页大小为4B，而逻辑内存为32B（8页），逻辑地址0的页号为0，页号0对应帧5，因此逻辑地址映射为物理地址5*4+0=20.逻辑地址3映射物理地址5*4+3=23.。逻辑地址13映射到物理地址9.

      采用分页技术不会产生外部碎片，但可能产生内部碎片。内存的分配是以帧为单位进行的，每个进程平均可有半个帧大小的内部碎片。

      分页使用户视角的内存与实际物理内存想分离。用户无法访问其他用户程序占用的内存。

4.2硬件支持

      页表的硬件实现有多种方法。最简单的是将页表作为一组专用寄存器来实现

4.3保护

      分页环境下，内存保护是通过与每个帧相关联的保护位来实现的。这新保护位通常位于页表中。可用一个位来定义一个页是可读写的还是只读的的，当对一个只读的页进行写操作会使系统产生硬件陷阱。

4.4共享页

      分页的一个优点是可以看、共享公共代码，这种考虑对分时环境很重要。

5.页表结构

5.1层次页表

      大多数计算机系统支持大逻辑地址空间（2的32到64的幂）。这种情况下，页表本身非常大。我们并不可能在内存中连续的分配这个表。一个简单方法是将页表划分为更小部分。

      一种方法是使用两级分页算法，将页表在分页。以一个4kb页大小的32位系统为例。一个逻辑地址被分为20位的页码和12位的页偏移。因为要对页表进行再000分页，所以该页号可分为10位的页码和10位 的页偏移。这样一个逻辑地址就表示如下形式：

      p1是用来访问外部页表的索引，p2是外部页表的页偏移，采用这种结构地址转换方法如下图所示。由于地址转换由外向内，这种方案也称为向前映射页表。

5.2哈希页表

      处理超过32位地址空间的常用方法是使用哈希页表（hashed page  table)，并以虚拟页码作为哈希值。哈希页表的每一条目都包括一个链表的元素，这些元素哈希成同一位置。每个元素有三个域：虚拟页码 所映射的帧号 指向链表中下一个元素的指针。

      虚拟地址中的虚拟页号转换到哈希表中，用虚拟页号与链表中的每一个元素的第一个域相比较。如果匹配，那么相应的帧号就用来形成物理地址。如果不匹配，就对链表中的下一个节点进行比较，以寻找一个匹配的页号：

      群集页表类似于哈希页表，对于稀疏地址空间很有用，稀疏地址空间的地址引用不连续，且分散在整个地址空间

5.3反向页表

      通常每个进程都有一个相关页表。每个页表有很多项。这可能消耗大量物理内存。为解决这个问题，可以使用反向页表。

6.分段

      采用分页内存管理有一个不可避免的问题：用户视角的内存和实际内存的分离。分段支持这种用户视角：将内存看做一个线型数组，有的包含指令，有的包含数据。

      逻辑地址空间是由一组段组成的。每个段都有名字和长度。地址指定了段名称和段内偏移。因此用户通过两个量来指定地址：段名称和偏移。段是编号的，通过段号而非段名称来引用。因此逻辑地址由有序对构成：

           <segment-number,offset>

通常，编译程序时，编译器会自动根据输入程序来构造段。

      一个C编译器可能创建如下段：代码、 全局变量、堆、线程栈、C库函数。

6.1.硬件

      段表的每个条目都有段基地址和段界限。段基地址包括段在内存中的开始物理地址，段界限指定段长度  

      一个逻辑地址段号S和偏移d组成。段号用作段表的索引，逻辑地址的偏移d应位于0和段界限之间。段偏移一段基地址之和就是物理内存地址。因此段表是一组基地址和界限寄存器对。

      如图有5个段，编号0~4，例如段2为400B开始于位置4300.对段2第53字节的引用映射成位置4300+53=4353