内存管理
为什么需要内存管理？ 不管存储器有多大，程序大小的增长速度比内存容量的增长速度要快的多
无存储器抽象 1.最简单的存储器抽象是无存储器 2.早期的大型机、小型机、个人计算机都是直接操控内存 3.这种情况下的计算机不可能会有两个应用程序同时在内存中
在没有存储器抽象的系统中实现并行性一种方式是使用多线程来编程。
注:人们通常希望能够在同一时间内运行没有关联的程序，而这正是线程抽象所不能提供的。
把当前内存中所有内容保存到磁盘文件中，然后再把程序读入内存即可
物理内存暴露的缺点
1.如果用户程序可以寻址内存的每个字节，它们就可以很容易的破坏操作系统
2.想要运行多个程序是很困难的
3.如果要使多个应用程序同时运行在内存中，必须要解决两个问题：保护和重定位。
一种存储器抽象：地址空间 1.进程可以用来寻址内存的地址集 2.每个进程都有它自己的地址空间，独立于其他进程的地址空间。 3.最简单的办法是使用动态重定位(dynamic relocation)技术，它就是通过一种简单的方式将每个进程的地址空间映射到物理内存的不同区域。 (1)基址寄存器和变址寄存器 (2)存储数据内存的起始位置和存储应用程序的长度 4.如果计算机的物理内存足够大来容纳所有的进程，那么之前提及的方案或多或少是可行的。
交换技术 把一个进程完整的调入内存，然后再内存中运行一段时间，再把它放回磁盘。
逻辑层面操作系统把数据分成不同的段来存储
代码段（codesegment/textsegment）
数据段（datasegment）
存储初始化好的静态和全局变量
bss段（bsssegment）
存储未初始化的静态和全局变量
rodata段
栈（stack）
堆（heap）
内存增长处理方式
1.如果一个进程与空闲区相邻，那么可把该空闲区分配给进程以供其增大。
2.如果进程相邻的是另一个进程，就会有两种处理方式：要么把需要增长的进程移动到一个内存中空闲区足够大的区域，要么把一个或多个进程交换出去，以变成生成一个大的空闲区。
3.如果一个进程在内存中不能增长，而且磁盘上的交换区也满了，那么这个进程只有挂起一些空闲空间（或者可以结束该进程）
空闲内存的管理
1.位图
2.空闲列表
按照地址顺序在链表中存放进程和空闲区
1.首次适配
(1)内存管理器会沿着段列表进行扫描
(2)首次适配算法是一种速度很快的算法，因为它会尽可能的搜索链表。
2.下次适配
(1)记录当时的位置，以便下次寻找空闲区时从上次结束的地方开始搜索
(2)性能略低于首次匹配
3.最佳适配
(1)试图找出最接近实际需要的空闲区
4.最差适配
(1)总是分配最大的内存区域
5.为进程和空闲区维护各自独立的链表以提高性能
6.快速匹配
(1)为那些常用大小的空闲区维护单独的链表
虚拟内存 基本思想 (1)每个程序都有自己的地址空间 (2)这个地址空间被划分为多个称为页面(page)的块。 (3)虚拟地址是对基址寄存器和变址寄存器的一种描述
分页技术
1.在任何一台计算机上，程序会引用使用一组内存地址
2.地址可以通过索引、基址寄存器、段寄存器或其他方式产生
3.这些程序生成的地址被称为虚拟地址(virtual addresses) 并形成虚拟地址空间(virtual address space)
存在映射的页如何映射
1.虚拟地址空间由固定大小的单元组成，这种固定大小的单元称为 页(pages)。
2.物理内存中也有固定大小的物理单元，称为 页框(page frames)。
3.程序试图访问地址时 MOV REG, 0
注:页框大小==页的大小
未映射的页如何映射
页表
1.虚拟地址被分为虚拟页号（高位部分）和偏移量（低位部分）。
2.虚拟页号可作为页表的索引用来找到虚拟页中的内容。由页表项可以找到页框号（如果有的话）。然后把页框号拼接到偏移量的高位端，以替换掉虚拟页号，形成物理地址
页表项
如何管理这个虚拟内存的抽象
1.虚拟地址到物理地址的映射速度必须要快
2.如果虚拟地址空间足够大，那么页表也会足够大
3.对大而且快速的页映射的需要成为构建计算机的一个非常重要的约束。
4.在启动一个进程时，操作系统会把保存在内存中进程页表读副本放入寄存器中。----->??????//不是很懂
加速分页过程
转换检测缓冲区（TLB）------>相联存储器
管理TLB软件
1.在以前，TLB管理都是由硬件设计完成。但是，许多现代的 RISC 机器，包括 SPARC、MIPS 和 HP PA，几乎所有的页面管理都是在软件中完成的。
2.当发生 TLB 访问丢失时，不再是由 MMU 到页表中查找并取出需要的页表项，而是生成一个 TLB 失效并将问题交给操作系统解决。
3.失效问题
(1)软失效
(2)硬失效
其他失效问题
1.所需的页面就在内存中，但是却没有记录在进程的页表中——次要缺页错误(minor page fault)。
2.如果需要从硬盘直接调入页面——严重缺页错误(major page falut)。
3.程序可能访问了一个非法地址，根本无需向 TLB 中增加映射——段错误(segmentation fault)
针对大内存的页表
1.多级页表
(1)避免把全部页表一直保存在内存中。不需要的页表就不应该保留
2.倒排页表
(1)针对分页层级结构中不断增加的问题
(2)实际内存中的每个页框对应一个表项，而不是每个虚拟页面对应一个表项。
页面置换算法 1.最优页面置换算法—–>理想状态 在缺页中断发生时，这些页面之一将在下一条指令（包含该指令的页面）上被引用。其他页面则可能要到 10、100 或者 1000 条指令后才会被访问。 每个页面都可以用在该页首次被访问前所要执行的指令数作为标记。 2.最近未使用页面算法（NRU） (1)状态位 a.每当引用页面（读入或写入）时都设置 R—->会定期清零 b.写入（即修改）页面时设置 M 注:由硬件来设置它们非常重要。如果硬件没有这些位，那么可以使用操作系统的缺页中断和时钟中断机制来进行模拟 (2)四种情况 a.R 0 M 0 b.R 0 M 1 c.R 1 M 0 d.R 1 M 1 3.先进先出置换算法（FIFO） (1)由操作系统维护一个所有在当前内存中的页面的链表，最早进入的放在表头，最新进入的页面放在表尾。 (2)在发生缺页异常时，会把头部的页移除并且把新的页添加到表尾。 4.第二次机会页面置换算法（SC） (1)避免把经常使用的页面置换出去 (2)我们检查最老页面的 R 位，如果是 0 ，那么这个页面就是最老的而且没有被使用，那么这个页面就会被立刻换出。 如果 R 位是 1，那么就清除此位，此页面会被放在链表的尾部，修改它的装入时间就像刚放进来的一样。然后继续搜索。 5.时钟页面置换算法（CLOCK） (1)对第二次机会算法的改进 在发生缺页中断时，检查表针指向的页面，根据R位采取动作: R = 0:淘汰并置换页面 R = 1:清除R位并向前移动表针 6.最近最少使用页面置换算法（LRU） (1)在缺页中断时，置换未使用时间最长的页面。 (2)用软件模拟LRU a.最不常使用置换（NFU） b.一个软件计数器来和每个页面关联 c.NFU 最主要的问题是它不会忘记任何东西 (3)老化算法 a.首先，在 R 位被添加进来之前先把计数器右移一位； b.第二步，R 位被添加到最左边的位而不是最右边的位。 7.工作集置换算法 (1)请求调页 a.刚启动进程时，在内存中并没有页面。此时如果 CPU 尝试匹配第一条指令，就会得到一个缺页异常，使操作系统装入含有第一条指令的页面。 (2)进程以局部性方式进行工作 (3)一个进程当前正在使用的页面的集合称为它的工作集(working set) a.如果内存太小从而无法容纳整个工作集，那么进程的运行过程中会产生大量的缺页中断，会导致运行速度也会变得缓慢——颠簸 (4)在多道程序的系统中，通常会把进程移到磁盘上（即从内存中移走所有的页面） (5)工作集模式 a.分页系统中都会设法跟踪进程的工作集，确保这些工作集在进程运行时被调入内存。这个方法叫做 工作集模式(working set model) b.预先调页
扫描所有页面检查R位
如果(R== 1)
设置上次使用时间为当前实际时间
如果(R==0&&生存时间> t)
移出这个页面
如果(R== 0&&生存时间<= t)
记住生存时间
注:t为时钟周期，生存时间为当前时间-上次使用时间
8.工作集时钟页面置换算法
(1)基于时钟算法但是却使用工作集的信息，这种算法称为WSClock(工作集时钟)。
(2)原则上来说，所有的页面都有可能因为磁盘I/O 在某个时钟周期内被调度。
a.为了降低磁盘阻塞，需要设置一个限制，即最大只允许写回 n 个页面。
(3)指针会绕一圈回到原点的，如果回到原点，它的起始点会发生什么？
a.至少调度了一次写操作
i.指针仅仅是不停的移动，寻找一个未被修改过的页面。
b.没有调度过写操作
ii.置换一个未被修改的页面来使用