第八章内存管理
1.地址捆绑
输入队列：在磁盘上等待调入内存以便执行的进程形成了输入队列
捆绑是从一个地址到另一个地址的映射。
编译时：如果在编译时就知道进程将在内存中的驻留地址，那么就可生成绝对代码
加载时：如果在编译时并不知到进程将驻留在何处，那么编译器就必须生成可重定位代码执行时：如果进程在执行时可以从一个内存段转移到另一个内存段，那么捆绑必须延迟到执行时才进行
2.逻辑地址（相对地址，虚拟地址）：CPU所生成的地址or 用户程序中使用的地址
物理地址（内存地址，绝对地址）：内存单元所看到的地址
编译时和加载时的地址捆绑生成相同的逻辑地址和物理地址运行时不同
重定位寄存器（relocation register）即基址寄存器（base register）
内存管理单元（MMU）：运行时实现从虚拟地址到物理地址的映射（map）的硬件设备
3.动态加载
①所有的子程序只有在调用时才被加载
②提高内存空间使用率，不用的子程序绝不会被装入内存
③如果大多数代码需要处理异常情况时是非常有用的。
④不需要操作系统的特别支持，通过程序设计实现。操作系统可能会为程序员提供实现动态装入的库函数。
4.动态链接库
①动态链接直到执行时才进行链接。
②利用动态链接，在映象中为每个库函数引用（library-routine reference）包含一个占位程序（stub）。占位程序是一小段代码，它指明了怎样定位驻留在内存中的库函数或函数不在内存中时怎样装入库。占位程序执行时，它检查所需的函数（routine）是否已经在内存中。如果没有，就把函数装入内存。或者以另外一种方式，占位程序用函数地址取代自身并执行这个函数。这样，下一次到达这段代码时，可以直接执行库函数（library routine）而无需动态
链接。利用这种机制，使用一个语言库的所有的程序只需要执行一份库代码拷贝。
③动态链接通常需要操作系统的支持。如果内存中的进程受到保护，那么只有操作系统才能够检查所需的程序是否位于另一个进程的内存空间中；或者说只有操作系统才可以允许多个进程访问同样的内存地址空间。
5.交换
①进程可以暂时从内存中交换出来到备份存储上，随后可以被换回内存继续执行。
②备份区—是一个固定的足够大的可以容纳所有用户内存映像的拷贝；对于可以让这些内存映像直接存取。
③滚入，滚出（roll in，roll out）——交换用于基于优先级的算法，低优先级的进程被换出，这样高优先级的进程可以被装入和执行。
④交换时间的主要部分是传输时间，总的传输时间直接同交换的内存的数量成比例。
系统有一个就绪队列，它包括在备份存储或在内存中准备运行的所有进程。当CPU调度程序决定执行进程时，它调用调度程序。调度程序检查队列中的下一进程是否在内存中，如果不在就执行交换。
⑤通常一个交换出的进程需要交换回他原来所占有的内存空间。若捆绑是在汇编时或加载时所定的，那么久不可以移动到不同的位置；若捆绑是在运行时耵，由于物理地址是在运行时才确定的，进程可以移动到不同的地址空间。
6.连续内存分配——每个进程位于一个连续的内存分配
①内存保护
重定位寄存器包含最小的物理地址；界限寄存器包含逻辑地址的值
●每个逻辑地址必须小于界限寄存器；MMU动态地将逻辑地址加上重定位寄存器的值后
映射成物理地址。映射后的物理地址再送交给内存单元。
●上下文切换时，内核装入新的base/limit值；用户无法改变其值
②内存分配
分区（hole）—可用的内存块,不同大小的分区分布在整个内存中；
当一个进程到来的时候,它将从一个足够容纳它分区中分配内存；
操作系统包含以下信息：已分配的分区；未分配的分区；
动态存储分配：
?首先适应策略（first-fit）：分配第一个足够大的连续空间。可以从连续空间列表的最开头开始搜寻，也可以从上一次搜寻的结尾开始。找到一个足够的大空闲空间时停止搜寻。?最佳适应策略（best-fit）：分配空间足够大的连续空间中最小的那个。除非列表按大小排序否则必须搜寻整个列表。这个策略将产生最小的剩余空间。
?最差适应策略（worst-fit）：分配最大的连续空间。除非列表按大小排序否则也必须搜寻整个列表。这个策略会产生最大的剩余连续空间，这个连续空间比用best-fit 方法产生的更小的剩余空间有用。
以上三种方法都有外部碎片问题
练习：Given four free memory partitions of 30KB, 20KB, 5KB and 46KB, how would each of the first-fit, best-fit, and worst-fit algorithms place processes of 18KB, 25KB, and 30KB (in order)? Which algorithm makes the most efficient use of memory?
③碎片
外部碎片：整个内存空间用来满足一个请求,但它不是连续的
内部碎片：通常把物理内存分成固定大小的块，以块大小为单元分配内存。利用这种方法，分配给进程的内存可能会比请求的内存稍大。块内多余的内存就是内部碎片——内存在一个块内部，但是不被使用。
紧凑（compaction ）——解决外部碎片问题：紧凑是为了将内存中的内容移动到一起以合并零碎的空闲内存空间
7.分页（paging ）——允许进程的物理地址空间可以是非连续的
物理内存分为固定大小的块，称为帧（frame ）；
逻辑内存也分为同样大小的块，称为页；
例子：
分页也是一种动态重定位。每个逻辑地址由分页硬件捆绑为一定的物理地址。
allocated allocated allocated P ：页表的索引（page number ）
D ：页的偏移（page offset ）
采用分页技术不会产生外部碎片，但会产生内部碎片
分页的另一个重要特点是用户观点的内存和实际的物理内存的分离
帧表：每个条目对应着一个帧，以表示该帧是空闲的还是已被占用，若被占用个，是为那个进程哪个页所占用。
保存页表：绝大多数都为每个进程分配一个页表，页表的指针与其他信息（如指令寄存器）一起存入进程控制块中。
Page-table base register (PTBR）页表基寄存器：指向页表
Page-table length register (PRLR) 页表长度寄存器：存放页表的长度值
?用PTBR访问内存：若要访问位置i，那么必须先用PTBR中的值再加上页码i的偏移来查找页表。这一任务需要内存访问。根据所得的帧号，再加上页偏移，就得到了真正的物理地址。接着就可以访问内存中所需位置的地址。访问一个字节需要两次内存访问（一次页表条目，一次字节）
?associative memory or translation look-aside buffers (TLBs) 快表
组成：键（标签），值
有效内存访问时间的计算：
Hit ratio = 80% ；Take 20ns to access TLB ；Take 100ns to access page table or memory Then
EAT = (20+100)x0.8 + (20+100+100)x0.2
= 140ns
If Hit ration=98%
EAT = (20+100)x0.98 + (20+100+100)x0.0.02
= 122ns
保护：有效-无效位V/I 如果该位为无效时，该值表示相关的页不在进程的逻辑地址空间内?页表结构
①层次化分页（Hierarchical Paging）
（32位机）
P1:访问外部页表的索引；p2：外部页表的页偏移
由于地址转换由外向内，这种方案也称向前映射页表
②哈希页表（hash page table）
哈希页表的每一个条目都包括一二链接组的元素；每个元素有三个域：虚拟页码，所映射的帧码，指向链表中下一个元素的指针
工作方式：虚拟地址中的虚拟页码转换到哈希页表中。用虚拟页码与链表中的每一个元素的第一个域相比较，如果匹配，那么相应的帧码（第二个域）就用来形成物理地址。如果不匹配，就对链表中的下一个域进行比较页码。
③反向页表（inverted page table）
④共享页
8.分段——支持用户观点的内存管理方案
逻辑地址空间是有一组段组成，每个段都有名称和长度。地址制定了段名称和段内偏移
段表：基地址（段在内存中的开始物理地址）段界限（指定该段的长度）
Segment-table base register (STBR) points to the segment table’s location in memory Segment-table length register (STLR) indicates number of segments used by a program; segment number s is legal if s < STLR