北邮 操作系统期末复习（上）

文章目录

• 一、绪论
• • 1.OS概述
  • 2.CPU概述
• 二、Boot,Process,Kernel
• • 1.BIOS
  • 2.Bootloader
  • 3.双模式
  • 4.进程
  • • 4.1 进程定义
    • 4.2 PCB
    • 4.3 进程&内存
  • 5.双模态
  • • 5.1 特权指令
    • 5.2 内存保护
    • • 5.2.1 分段
      • 5.2.2 分页
    • 5.3 时间片中断
    • 5.4 CPL
  • 6.小结
• 三、context switch
• • 1.用户态到内核态
  • • 1.1 中断
  • 2.从内核态到用户态
  • 3.X86概述
  • • 3.1 X86的中断处理
• 四、OS Interfaces and Syscalls
• • 1.进程管理
  • • 1.1 Windows中的API
    • 1.2 Linux中的API
    • • 1.2.1 fork()
      • 1.2.2 exec()
  • 2.输入/输出
  • • 2.1 通用输入/输出API
  • 3.系统调用的设计
• 五、threads
• • 1.线程抽象
  • • 1.1 线程的特点
    • 1.2 线程&进程
    • 1.3 线程API
    • 1.4 线程的生命周期
  • 2.线程实现
  • • 2.1 TCB
    • 2.2 内核线程的实现
    • • 2.2.1 创建线程
      • 2.2.2 删除线程
      • 2.2.3 线程切换
    • 2.3 用户线程的实现
• 六、Address Translation
• • 1.地址翻译概述
  • 2.分段
  • • 2.1 分段表
    • 2.2 X86视角
    • • 2.2.1 实模式
      • 2.2.2 保护模式
    • 2.3 小结
  • 3.分页
  • • 3.1 页目录
    • 3.2 页表
    • 3.3 MMU
    • 3.4 缺页中断
    • 3.5 COW
    • 3.6 小结
  • 4.分段&分页
• 七、TLB and Cache
• • 1.TLB
  • • 1.1 TLB Lookup
    • 1.2 TLB Miss
    • 1.3 超页
    • 1.4 TLB Consistency
  • 2.Cache
  • • 2.1 Cache Lookup
    • • 2.1.1 直接映射
      • 2.1.2 全相联映射
      • 2.1.3 组相联映射
    • 2.2 Cache Replacement
    • 2.3 Cache Write Policies
    • • • 2.3.1 全写法
        • 2.3.2 写回法
    • 2.4 TLB&Cache
    • 2.5 工作集
    • 2.6 页着色

这部分主要是针对北邮徐梦玮老师的操作系统课程做的考点总结，基本上期末考试的内容都是课堂上讲解过的以及平时作业中出现过的知识点。

注意复习这门课程不要去找网上的题刷，网上的题和实际徐老师的期末考题差异会非常大。

一、绪论

1.OS概述

操作系统的作用：

• 操作系统是硬件和用户/应用之间的桥梁
• 操作系统管理硬件，为应用和用户服务
• 操作系统是裁判、魔法师、胶带
  • 裁判：让应用之间隔离使用资源（用户态和内核态的设计）
  • 魔法师：让应用感受到似乎独占所有的硬件资源
  • 胶带：缝合了上层应用和底层硬件之间的gap，包括硬件的接口会改变、硬件的功能会进化、应用也会改变，操作系统给应用提供了一个统一的接口

2.CPU概述

OS与CPU之间频繁的进行交互，因此了解CPU的组成非常必要

二、Boot,Process,Kernel

1.BIOS

BIOS是一种固件，固件是一种软件，和普通软件和操作系统都不一样，通常放在不可改的存储器上面；

BIOS是第一个机器启动以后会运行的软件，BIOS主要执行以下的操作：

2.Bootloader

bootloader是OS的一部分，一般认为OS=bootloader+kernel；

bootloader主要完成下面的操作

关于bootloader和BIOS的区别

Q：为什么BIOS不直接load整个OS？

A：因为BIOS只能load很小的一部分的数据（历史的包袱），并且BIOS需要保持最简化的功能（固件最简化）；

3.双模式

实模式和保护模式的区别 – 历史的包袱，因为硬件不断演化，操作系统需要兼容，甚至硬件之间也要相互兼容；

保护模式能够真正的保护进程的一些信息；

实模式和保护模式实际上是CPU运行的两种状态，实模式下一般只能访问16bit的数据，为了访问更高位数的数据并兼容16bit出现了保护模式；

4.进程

4.1 进程定义

进程的定义：一个程序的运行时，包含一些权限限制

Q：进程和普通程序的区别？

A：

4.2 PCB

4.3 进程&内存

对一个进程/程序来说似乎独占所有硬件资源，一般进程会分为几个段，其中堆向上生长，栈向下生长

注：这里讨论的地址都是虚拟地址，一个可执行的程序已经指定好了段的大小等信息；

5.双模态

操作系统设计了双模态的概念，即CPU在执行的时候可选择两种状态，其中内核态拥有更高的权限，能够做更多的事情；

双模态由OS和硬件共同实现，其中硬件主要完成以下四部分的功能

5.1 特权指令

特权指令：只有CPU在内核态的时候才能执行

一个不严谨的说法是，影响其他进程的指令就是特权指令

如何执行特权指令呢？让操作系统帮进程执行特权指令，其中系统调用是操作系统暴露给用户态程序的一些接口

如果程序执行了特权指令会被检测到并kill

5.2 内存保护

硬件需要提供的第二部分是内存保护，使得地址是隔离的

5.2.1 分段

分段法是最简单的方法，每个程序使用bounds大小的内存空间，缺点是共享、碎片化问题

5.2.2 分页

因为分段存在很大的问题，所以现代操作系统一般都使用分页的方法；

由硬件(CPU)来执行虚拟地址到物理地址之间的映射，由软件OS来决定映射的策略；

OS和CPU的中间体就是页表，页表存在内存中；

一般多个进程的kernel代码都是相同的，映射到同一块区域

Q：为什么内核代码存放在高地址空间？

A：历史的包袱 – 方便进程用户态从低地址处理

5.3 时间片中断

5.4 CPL

6.小结

三、context switch

上下文切换，主要讲解用户空间和内核空间的上下文切换（这个话是老师的原话，但是我感觉和上下文切换完全没有关系）

1.用户态到内核态

有三种可能CPU会从用户态切换到内核态

1.1 中断

中断处理对用户来说是不可见的，对进程的状态不会影响；

中断向量表

中断向量表是在实模式下使用的，中断向量表一般保存在一个固定的位置

中断描述符表

中断描述符表IDT是在保护模式下使用的，有更多专有名词，其中的每个元素称为一个门，一共有256个门，中断描述符表不是在固定的位置，通常其位置存放在一个寄存器IDTR中，该寄存器的值可以动态加载

Q：具体如何从中断发生定位到中断处理程序？

A：首先IDTR会指向中断描述符表的开始位置，接着根据中断号找到中断描述符表中对应的项，在项中提取出offset，因为分段的原因可能还需要加上一个基地址，就可以找到相应的中断处理程序

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-42EHQ7GP-1678871761625)(https://img2023.cnblogs.com/blog/2922190/202301/2922190-20230111133719282-1962803577.png)]

Q：如何知道中断号呢？如何知道现在发生的是第几号中断呢？

A：只有硬件知道，硬件层面会通知这个中断是第几号；

中断向量表和中断描述符表的区别，首先它们的共性是可以实现隔离，所有用户态的代码要进入内核态只有这几道门，这两个表决定了门的数量和种类，因此在写内核的时候只需要保证这几个门的安全性即可

中断屏蔽

不是所有的中断都必须要发生，操作系统可以mask一些中断，有些中断可以屏蔽有些不可以；

中断屏蔽只是推迟了中断的发生，并不是直接忽略的中断的发生；

中断栈

在内核的中断处理程序在处理中断的时候需要栈，这个栈放在内核态（因为用户态的栈会被修改）；

如果没有中断产生的时候中断栈是空的，因为不需要处理任何事情；

操作系统中的中断栈的计算公式

数字1的原因是第一次中断就是我们常见的中断，将用户态转换为内核态，一般情况下可以在一层中断的基础上嵌套实现第二层中断，这个中断可以共享第一次的中断栈，二第三层中断一般不被允许直接导致OS重启；

每一个线程或者进程都会有一个自己的中断栈，是为了使得操作系统能够更好的处理不同进程/线程的中断（多个进程可能同时产生中断）

2.从内核态到用户态

如下情况（或者方式）会导致CPU从内核态切换到用户态

3.X86概述

X86使用的是分段

其中CS寄存器的值只能使用以下指令改变

3.1 X86的中断处理

当中断/异常/系统调用发生的时候，硬件会进行如下操作

Q：为什么需要临时寄存器？

A：因为第三步切换栈是修改SS:ESP的地址，如果没有临时寄存器就根本不能保护现场即回不去之前的状态了

硬件处理之前的栈状态

硬件处理之后的栈状态

中断发生的时候硬件会做上面的事，OS会做什么操作呢？

Q：专门的寄存器指向当前栈，但是为什么没有专门指向堆的寄存器？

A：因为不需要，指向栈是因为OS需要用到栈，但是堆是用户自己操控的；

四、OS Interfaces and Syscalls

操作系统给应用/用户提供了非常多的功能

1.进程管理

1.1 Windows中的API

在Windows下通常使用CreateProcess这个API来创建进程

1.2 Linux中的API

在Linux中会使用fork()和exec()函数创建一个新的进程；

1.2.1 fork()

fork没有任何参数，会完全拷贝一个当前进程，返回值为0则是子进程，父进程会得到子进程的进程ID，是一个大于0的值，父进程和子进程之间唯一的区别就是返回值不同，父进程和子进程不共享地址空间，但是它们的地址空间的值完全相同；

Q：为什么父进程和子进程的环境相同还需要拷贝再赋值？

A：实际上这涉及Linux的优化问题，并不会是简单的值拷贝；

1.2.2 exec()

exec将会从磁盘下载并执行一个程序，需要注意的是exec不会创建任何新的进程；

并不是每个fork后面都需要紧跟一个exec，例如浏览器中打开新的tag实际就是打开一个新的进程，但是这个进程实际上是和原来的进程使用的同一套代码，就不需要再load一个新的程序

Linux中除了fork()和exec()以外，还有其他辅助函数

2.输入/输出

OS除了提供进程管理功能，还提供I/O功能；

计算机有很多I/O设备，最简单的管理方法就是给每一个设备一个系统调用，但是Unix将所有的设备抽象为文件，好处是接口简洁、统一；

有文件就有相应的结构体来描述，Unix中使用文件描述符来描述，文件描述符本质上就是一个int类型的值；

怎么使用int值来描述文件？操作系统有一个文件描述符表，每一个文件描述符可以在里面寻址到相应的文件的信息；

需要注意的是每个进程都有自己的文件描述符表，只有打开的文件才有文件描述符（文件描述符是open函数的返回值，一个文件可以被open多次）；

2.1 通用输入/输出API

注意点：

• 每一类设备都对应一类文件描述符；
• 要求所有的文件先打开再使用；
• 文件描述符是有上下文的，多次read会累加进行；
• 以字节为单位进行操作；
• 内核对读写操作有缓冲作用；
• 每一个文件描述符都要close帮助垃圾回收；

open

close

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eTzFgsrO-1678871761636)(https://img2023.cnblogs.com/blog/2922190/202301/2922190-20230111133920955-1933871181.png)]

read

write

3.系统调用的设计

对应用来说操作系统看起来就是提供了很多的函数（系统调用）而已，设计系统调用难点是如何保证内核态的安全性，Unix中的系统调用基本都是如下流程实现

Q：如果不拷贝，内核可以直接访问用户态的参数吗？

A：当然可以，内核的权限高于用户；

Q：为什么参数一定要拷贝到内核的内存中？

A：直接使用会出现一些问题，本质上就是用户态的代码随时可能被改变不安全，所以一般不建议；

Q：可不可以先检查再拷贝？

A：如果在检查以后再拷贝进来就没办法修改了（内核态的代码不能修改），容易导致系统漏洞；

五、threads

1.线程抽象

Q：为什么需要线程？

• 线程通常和并发联系在一起，并发是指多个任务同时进行；

  • 多任务和并发：多任务强调不同的任务，并发一般侧重多个任务“同时”执行；

  • 并发和并行：并行是真正的同时执行；

• 有些程序在逻辑上就应该是实现并发的（代码自上而下执行很别扭）

• 某些线程不应该影响另一些线程的体验：前台线程和后台线程分离执行

• 多线程/多进程可以使用多个核

  • 并不是核越多越快，可能还有其他的瓶颈比如CPU、存储等速度限制

• 其他线程阻塞的时候可以让CPU一直保持忙碌状态

线程定义：一个可以被单独调度的顺序执行序列，即线程可以随便被挂起、恢复

线程就是同一个进程中不同的函数，可以交替执行，线程是操作系统最小的调度单位；

1.1 线程的特点

线程之间不会共享栈，因为栈是执行的上下文，线程是被单独调用的，不能共享上下文；

线程共享地址空间但是不共享栈、寄存器（上下文）；

线程的执行速度是不可预测的，因为它随时可能被挂起（同步问题）

1.2 线程&进程

1.3 线程API

1.4 线程的生命周期

2.线程实现

2.1 TCB

和进程控制块类似，线程也有控制块

Q：一个进程可以有很多线程，那么线程的栈的大小有限制吗？

A：栈的大小实际上和递归的深度有关，在内核中，因为要处理中断所以需要中断栈，但是因为比较简洁所以中断栈不需要很大；

同一个进程中的线程共享代码和地址空间、全局变量，因为线程共享地址空间，所以可能会导致一些危险；

线程如何实现呢？这里循序渐进，先讲内核中如何实现线程，再讲用户态如何实现线程，需要注意的是内核线程永远运行在内核态，其数据也存放在内核空间中，由内核态线程可以扩展到用户态线程；

2.2 内核线程的实现

2.2.1 创建线程

下面这段代码是一个简单的在内核中创建线程的例子

2.2.2 删除线程

怎么删除一个线程？只需要把这个线程从List中删除即可，再将相应的空间释放掉

综上，一个线程不能销毁自己！！！解决办法是使用其他线程来帮助自己free掉finished的list中的线程；

2.2.3 线程切换

主要分为两种切换方式，一种是主动切换，另一种是被动切换（中断、异常）；

注意这里的线程切换不是指CPU状态的切换，因为内核线程只能运行在内核态，这里指的是将一个正在运行的内核线程挂起，运行另一个内核线程；

主动切换的流程如下

实例代码如下

被动切换的流程相对简单

2.3 用户线程的实现

实现用户态的多线程主要有如下几种方法：

假如要实现一个用户态的create_thread函数

第二种方式就是完全使用用户态下的库函数，整个过程没有内核的参与，库维护了用户空间所需的一切状态；

Q：如何使得在用户态下实现并发的多线程？

A：操作系统并不知道用户线程的存在，内核线程可以实现线程的并发是基于时间片的中断，但是用户态根本感知不到时间片的中断（时间片是内核的东西），一个解决办法是主动让出，或者是抢占式的upcall

Q：用户态线程如何切换程序指针或栈指针呢？

A：用户态线程改变PC下一条指令使用jump指令实现，改变栈指针很简单，直接修改寄存器的值即可；

下面总结用户线程和内核线程的异同

六、Address Translation

1.地址翻译概述

用户看到的所有地址都是虚拟地址，从虚拟地址到物理地址有一个转换的过程，被称为地址翻译，地址翻译并不仅仅做翻译的事

地址翻译的目标如下

地址翻译需要硬件和操作系统同时协作实现；

地址翻译主要有两种实现方式，分别是分段和分页，一般分段都使用16为操作系统，分页一般使用32位操作系统进行讲解；

在分段和分页同时存在的情况下，虚拟地址经过分段后称为线性地址，线性地址经过分页过后才是物理地址；

2.分段

2.1 分段表

在实模式下不存在分段表

2.2 X86视角

X86规定程序只能有6个段，并且规定了每个段怎么使用，默认会添加段前缀

2.2.1 实模式

最多能访问2²⁰的物理地址，并且同一个物理地址可能有多种组合情况；

2.2.2 保护模式

保护模式下，分段表被称为GDT全局描述符表和LDT局部描述符表

2.3 小结

分段很强大，主要有以下功能

分段最大的问题就是很容易产生碎片化

3.分页

分页和分段最大的区别就是分页将物理地址分为一个个固定大小的页，以页位单位进行内存的映射；

页表用于实现虚拟页和内存页之间的映射，记录了每一个虚拟页对应的物理页；使用页不再需要bound这个限制，因为页的大小已经固定；使用分页后，在虚拟地址看起来连续的页在物理地址上几乎是完全随机的；

分页的好处：

• 在分配内存的时候非常方便，直接以页为单位分配即可；

• 分页很容易实现内存的共享，将页表项映射到同一个物理页；

下图是一个最基本的分页的地址翻译的过程，使用的是一级页表

当我们限定地址的大小为32bit的时候，需要会计算页表和物理页的大小

可以看到一个页表大小为4MB，很多进程甚至都用不到4MB，而且每一个进程都需要这么大的页表，无疑会造成浪费，所以现代操作系统出现了多级页表

Q：本质上二级页表并没有增大逻辑地址或者物理地址，二级页表是怎么节省空间的呢？

A：这是因为借助了稀疏性，只调用需要的页表即可；

Q：在上下文切换的时候（指的是进程），什么也需要切换？

A：CR3寄存器的值，也就是页目录的起始地址；

3.1 页目录

3.2 页表

每个进程和内核都有自己的页表，因为地址隔离，但是线程是共享地址空间的所以线程共享页表（页目录同理）；

3.3 MMU

整个翻译的过程是由一个被称为MMU的硬件完成，不是操作系统实现的（因为操作系统实现地址翻译非常缓慢）；

PS：页的大小非常重要，页太小会导致页表非常大（页变多了），页表太大会浪费空间；

3.4 缺页中断

简单理解缺页中断就是CPU/MMU在进行映射的时候发现内存中并不存在与逻辑页对应的物理页；

出现缺页中断的情况：页表项不存在（最后一个比特为0）、权限不足、页表不存在（最后一个比特为0）；

3.5 COW

这个概念的全称是Copy-on-Write，是Linux中节省空间的做法

拿fork举例，子进程和父进程完全一样，但是很可能子进程执行的动作完全不同，因此浪费大量时间在复制内存上，使用COW在复制页表的时候不会复制具体的内存的值，简单来说COW会检查页表项的比特来处理是否进行写入操作，对应的考题如下

3.6 小结

下面给出几道练习题

4K是指一个物理页的大小是2¹²bit，一共有多少个物理页呢？一共有2¹⁰*2¹⁰的物理页框，故计算得到最大寻址空间为4GB

Q：操作系统只能使用虚拟地址，那么操作系统如何知道一个虚拟地址的物理地址？

A：使用自映射，需要页表项的物理地址就映射一次，需要页目录项的物理地址就映射两次；

4.分段&分页

实际上分段和分页是可以合并使用的，逻辑/虚拟地址经过分段称为线性地址，线性地址经过分页之后变成物理地址

缓存是一个非常广泛的概念（有各种各样的缓存），本质上是一段存储，访问速度非常快

平均响应时间如下

为什么需要缓存？存储器的提升并没有CPU的迭代速度快，缓存就是用于填补这部分的gap的

缓存命中率取决于时间局部性和空间局部性：

• 时间局部性：一个地址可能在短时间内被访问多次；
• 空间局部性：要访问的内容在上次访问内容的附近；

缓存可以构成如下架构

常见的缓存如下

七、TLB and Cache

1.TLB

地址翻译最大的缺点就是使得内存的访问变慢；

TLB是在MMU内部的一个加速地址翻译的缓存，为什么地址翻译可以被缓存？因为局部性原理：

• 时间局部性：地址翻译过程中会重复访问一个地址（for循环）；
• 空间局部性：访问的虚拟地址在原来地址的附近（代码顺序执行）；

TLB中的翻译实际上是以页为单位，换句话来说，地址翻译都是以页为单位；

TLB能够很好的工作的原因就是因为其命中率很高；

TLB的工作过程非常简单：可以将TLB理解为具有如下三项的列表，分别是虚拟页号（之所以不是虚拟地址是因为地址翻译是以页对齐，因此只需要操作页）、物理页号和访问权限

1.1 TLB Lookup

通过引入TLB极大的减少了地址翻译的时间

1.2 TLB Miss

TLB不命中的原因：页没有被访问过、TLB内存有限等其他原因

如何解决TLB的Miss呢？当我们按照完整的地址翻译过程找到虚拟地址对应的物理地址之后，需要将其更新到TLB中，现在基本上都让硬件来完成更新的操作（因为硬件速度快）；

1.3 超页

TLB最重要的一点就是需要保持一个非常高的命中率，如何进一步提高TLB的命中率呢？页大一点还是小一点更加容易命中？因为大一点可以导致页更少，因此只需要缓存更少的页即可，那么缓存命中的概率就更大；

超页：向操作系统申请多个连续的极其大的页（物理地址上连续），这在一定程度上能够提高局部性原理，但是页变大了不够灵活浪费空间，并且物理页需要连续增加开销；

一个超页在TLB中是对应了一个TLB项（如果对应多个TLB超页就没有存在的意义了，超页可以看作是多个页的集合体）；

1.4 TLB Consistency

无论是什么缓存（包括TLB），都需要具备一个非常重要的概念，即一致性，原因就是避免缓存和内存的值不同；

主要在一下情况需要保持一致性：进程上下文切换、权限变换、TLB击落（多处理器访问）；

进程上下文切换

权限变换

当改变了页表的权限（权限降低，从可写改变成只读），解决办法是直接将整个TLB或者单个的TLB项丢弃；

权限增大的时候是不需要做什么事情的，miss之后重新去页表中更新TLB即可；

TLB Shutdown

在多处理器系统中，如果多个处理器在跑同一个进程的多个线程（内核线程），它们的页表是相同的（因为是同一个进程），但是它们的TLB不同，因为TLB在CPU的MMU中，多处理器意味着多个CPU当然TLB也就不同，那么当一个处理器将页表改变过后，它不仅需要修改自己的TLB，还需要告知其它处理器对TLB进行修改；

2.Cache

此处的Cache就是CPU和内存之间的告诉缓存，块是Cache中的单位，块的大小取决于硬件的设计；

2.1 Cache Lookup

主要分为全相联映射、直接映射和N路组相联映射，理解这几种映射需要做题；

2.1.1 直接映射

地址映射规则：将主存分区，每个区域内的主存块数与Cache内的块数相同；

1. 主存中的每一块只能映射到Cache内的固定行，规则为
   
   其中i为Cache的行号，j为主存的块号，m为Cache的总块数

2. 不使用替换算法，产生冲突直接替换原有内容；

3. 为了在Cache中记住自己存储的数据块属于主存中的哪一个区，Cache需要额外在Cache行中设置标记字段，假设主存有256块，Cache有8块，则主存要划分32个区，Cache需要5位标记字段来标记区号，3位标记Cache行号；

4. 使用直接映射，则CPU使用的内存地址结构为：

   

5. 地址变换过程为：先按照Cache行号找到Cache中的块，接着用标记字段与Cache中的区号/标记进行比较，如果相同则命中，使用块内地址在Cache中取出需要的数据；

2.1.2 全相联映射

地址映射规则：主存的任意一块可以映射到Cache中的任意一块

1. 主存与缓存分成相同大小的数据块。

2. 主存的某一数据块可以装入缓存的任意一块空间中。

3. 为了在Cache中记住自己存储的数据块来自主存中的哪一块，Cache需要额外在Cache行中设置标记字段，假设主存有2048个地址块，则Cache标记字段的位数为11位

4. 假设使用全相联映射，则CPU使用的内存地址结构为：

   

5. 地址变换过程为：先按照标记找到存储主存块数据的Cache块，若找到则代表命中，接着使用块内地址在Cache块中取出需要的数据；

2.1.3 组相联映射

地址映射规则：将主存分区，将Cache分组，要求主存的每个区的块数与Cache的组数相同（主存中一个区分为4块所以Cache中需要4组）

为了在Cache中记住自己存储的数据块来自主存中的哪一个区，Cache额外增加了标记字段；

假设每组有r个Cache块，则称为r路组相联；

1. Cache组间采用直接映射（主存块存放到哪个组是固定的），组内采用全相联映射（主存块存放到组内的哪一行是灵活的）

组间直接映射规则：

2.使用组相联映射，CPU的内存地址结构为：

​ 标记：主存区号的标记 组号：Cache组的地址 块内地址：Cache中的字块内的地址

3.地址变换过程：首先使用组号找到Cache中的组，然后将标记与该组所有Cache块中的区号比较，如果相同则命中，使用块内地址取出需要的数据；

2.2 Cache Replacement

采用全相联或组相联映射方式的时候，从主存向Cache映射一个块，当Cache或Cache组中的空间被占满时候，需要使用替换算法（直接映射没有选择直接替换，故不考虑替换算法）；

• 随机算法：随机确定要替换的Cache块；
• FIFO算法：选择最早调入的Cache进行替换；

• LRU算法：

2.3 Cache Write Policies

Cache中的内容是主存的副本，当Cache中的内容更新的时候，需要选择写策略使得Cache与主存内容保持一致；

2.3.1 全写法

也称为写直通法、write-throught：

• 当CPU对Cache写命中时，将数据同时写入Cache和主存；
• 当Cache某块需要替换时，不必将这块写回主存（因为Cache和主存随时同步），直接用新调入的Cache块覆盖即可；

优点是简单，随时保持主存数据的正确性；

缺点是增加了访存次数，降低了Cache效率，我们可以适当在Cache和主存之间增加一个写缓冲 —— CPU同时将数据写入写缓冲和Cache，写缓冲再将内容写入主存，由此解决速度不匹配的问题；

2.3.2 写回法

write-back：

• 当CPU对Cache写命中时，只修改Cache的内容，不会立刻写入主存，只有当该Cache块被替换出的时候才写回主存；

这种方法减少了访存次数，但是增加了不一致的风险 —— 采用这种策略时每个Cache块必须设置一个标志位脏位以标志此块是否被CPU修改过；

上述两种方法都应对的是Cache写命中（也就是要修改的单元在Cache中）；

2.4 TLB&Cache

Q：Cache中的地址是虚拟地址还是物理地址？

A：从图中可以知道是物理地址（从MMU中出来的都是物理地址）

如果Cache的命中率高但是TLB的命中率低则还是不能很好的协同工作，所以需要考虑如何使得TLB和Cache能够协同工作

2.5 工作集

一个进程需要工作，一般需要一块内存，该内存的大小就是该进程常驻在内存中的大小，过大浪费，过小需要不停的换入换出；

工作集的定义就是进程在一段时间需要的内存，可以适当的将工作集放在Cache中进一步提升工作速度；

2.6 页着色

当Cache使用的是虚拟地址的时候会存在别名问题，原因是操作系统和用户程序可能对同一个物理地址使用两种以上不同形式的虚拟地址来访问，这些地址被称作别名，他们会导致同一个数据在使用虚拟地址的cache中存在两个副本，如果其中一个数据被修改，那么另外一个就是错误的；

解决别名问题的方法之一就是使用页着色：

• 如果强行要求别名的某些地址位相同，就可以用软件很容易地解决这一问题（如SUN公司的UNIX要求所有使用别名的地址最后18位都相同，这种限制被称为页着色）；
• 上述页着色的限制使得容量不超过2^18字节（256KB）的直接映射Cache中不可能出现Cache块有重复物理地址的情况，所有别名将被映射到同一Cache块位置；

总结：

• 相同的color在内存中离散存在；
• 相同的color在Cache中连续存在；