2022-10-21 11:17 上海理工大学嵌入式工程师发布于上海

关注

Linux内存管理--cache--MMU

1.操作系统功能

1.CPU管理

其工作主要是进程调度，在单用户单任务的情况下，处理器仅为一个用户的一个任务所独占，进程管理的工作十分简单。但在多道程序或多用户的情况下，组织多个作业或任务时，就要解决处理器的调度、分配和回收等问题。

2.存储管理

分为几种功能：存储分配、存储共享、存储保护、存储扩张。

3.设备管理

分为以下功能：设备分配、设备传输控制、设备独立性。

4.文件管理

文件存储空间的管理、目录管理、文件操作管理、文件保护。

5.作业管理

是负责处理用户提交的任何要求。

2.内存基础知识

1.缺页中断

1.缺页异常

malloc和mmap函数在分配内存时只是建立了进程虚拟地址空间，并没有分配虚拟内存对应的物理内存。当进程访问这些没有建立映射关系的虚拟内存时，处理器自动触发一个缺页异常。

2.缺页中断

缺页异常后将产生一个缺页中断，此时操作系统会根据页表中的外存地址在外存中找到所缺的一页，将其调入内存。

3.缺页中断与一般中断

与一般中断一样，需要经历四个步骤：保护CPU现场、分析中断原因、转入缺页中断处理程序、恢复CPU现场，继续执行。

4.缺页中断与一般中断区别

（1）在指令执行期间产生和处理缺页中断信号
（2）一条指令在执行期间，可能产生多次缺页中断
（3）缺页中断返回的是执行产生中断的一条指令，而一般中断返回的是执行下一条指令。

分段错误：程序访问了非法位置的内存。
分页错误：指针试图访问当前未映射到物理内存的地址空间页面
分段/分页错误的区别：前者是非法情况，该程序通常将被中止；后者是完全正常的，程序甚至不知道它。

2.缺页置换算法

1.先进先出（First In First Out, FIFO）

队列，删除队首的页即可

2.最近最久未使用置换（Least Recently Used，LRU）

置换最近一段时间以来最长时间未访问的页面。

实现方式
利用链表和哈希表。
具体的做法是
当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部，如果不存在，则新建一个节点，放到链表头部，若缓存满了，则把链表最后一个节点删除即可。
在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。
物理解释
1. 假设我们有一块内存，一共能够存储 5 数据块。
2. 依次向内存存入A、B、C、D、E，此时内存已经存满。
3. 再次插入新的数据时，会将在内存存放时间最久的数据A淘汰掉。
4. 当我们在外部再次读取数据B时，已经处于末尾的B会被标记为活跃状态，提到头部，数据C就变成了存放时间最久的数据。
5. 再次插入新的数据G，存放时间最久的数据C就会被淘汰掉。

3.最近最少使用（Least Frequently Used，LFU）

置换最近一段时间以来访问频率最低的页面。

3.内存溢出/内存泄漏

1.内存溢出 out of memory

是指程序在申请内存时，没有足够的内存空间供其使用，出现out of memory。

2.内存泄露 memory leak

内存泄漏是在堆内存中，所以对我们来说并不是可见的，是指程序在申请内存后，疏忽或错误造成程序未能释放已经不再使用的内存。一次内存泄露危害可以忽略，但内存泄露堆积后果很严重，无论多少内存，迟早会被占光。

- 内存泄漏不是进程死了内存没释放
- 内存泄漏是进程活着，但随着时间的推移，内存消耗越来越多。

3.内存泄漏的原因

大量使用静态变量。
链接资源未关闭（例如数据库连接，文件输入输出流、网络连接）。
堆上申请的空间没有被释放。
子类继承父类时，父类析构函数不是虚函数。

4.内存泄漏的检测和定位方法

链接

对于Windows平台下

Windows平台下面Visual Studio 调试器和C运行时库(CRT) 为我们提供了检测和识别内存泄漏的有效方法
原理大致如下：内存分配要通过CRT在运行时实现，只要在分配内存和释放内存时分别做好记录，程序结束时对比分配内存和释放内存的记录就可以确定是不是有内存泄漏。
在程序的开头添加：#define _CRTDBG_MAP_ALLOC、#include <crtdbg.h>
在程序的结尾添加_CrtDumpMemoryLeaks()来检测是否有内存泄漏。

定位内存泄漏是对应用程序的内存状态拍快照。 CRT 库提供一种结构类型 _CrtMemState，您可用它存储内存状态的快照：_CrtMemDifference 比较两个内存状态（s1 和 s2），生成这两个状态之间差异的结果（s3）。在程序的开始和结尾放置_CrtMemCheckpoint 调用，并使用_CrtMemDifference 比较结果，是检查内存泄漏的另一种方法。如果检测到泄漏，则可以使用 _CrtMemCheckpoint 调用通过二进制搜索技术来划分程序和定位泄漏。

对于Linux平台下
1. 原理相同的方法——mtrace
2. ccmalloc
3. 工具valgrind

Valgrind工具组提供了一套调试与分析错误的工具包，能够帮助你的程序工作的更加准确，更加快速。这些工具之中最有名的是Memcheck。
命令：valgrind --leak-check=yes myprog arg1 arg2
其中：myprog arg1 arg2为编译后的可执行文件，例如如果可执行文件为example，则命令为valgrind --leak-check=yes ./example

4.代码分区

1.全局区

全局变量和静态变量和部分常量，由操作系统释放。全局变量被定义的时候操作系统会对其初始化。其中常量为：字符串常量和const修饰全局变量。
全局区分为两块，一块存放程序中的已初始化的全局变量和静态变量（数据段data），另一块存放程序中未初始化的全局变量和静态变量（BSS段）。
注意：
const修饰的全局常量放在全局区
const修饰的局部常量不在全局区
局部变量也不放在全局区
图片说明

2.代码段

通常是指用来存放程序执行代码的一块内存区域

3.堆

存放进程运行中被动态分配的内存段，它的大小并不固定，可动态扩张或缩减，这一块在程序运行前就已经确定了。

在堆区分别申请两个1个字节的内存，其内存空间会连续吗？为什么？

堆分配的空间在逻辑地址上是连续的，但在物理地址上可能不是连续的（因为采用了页式内存管理，windows下有段机制、分页机制）因为有可能相邻的两个字节是在不同的物理分页上。如果逻辑地址空间上已经没有一段连续且足够大的空间，则分配内存失败。

堆区和栈区出现数组越界，各自的表现？
1. 对于栈空间，首先它是很少的，主要靠它的循环利用和换页操作才满足我们对于它的需求。所以需要多少就分配多少，你的程序里需要1个字节，那么也就分配一个字节，想往一个字节空间里放10个字节，那么其他9个字节就要占用（覆盖）其他空间，其他空间不是属于自己的，那么就会出错。
2. 对于堆空间，首先相对于栈空间，它还是很丰富的，并且是一块比较大的空间供我们的程序调用和手动释放。申请1个字节，但是分配会多于一个字节（包括用于存放申请信息），虽然这样不会出错，但是不等于数据一直是对的，因为不是某个变量申请的空间，但占用了这部分空间，这部分空间还是未分配状态，那么其他变量一样可以申请这部分空间，一旦新申请的变量往里写数据了，就会覆盖上次溢出的数据。因此不能保证数据的正确性。

4.栈

栈又称堆栈，存放程序的局部变量（不包括static声明的变量）。当局部变量被初始化的时候，系统不会对其初始化。除此以外，在函数被调用时，栈用来传递参数和返回值。(函数栈的切换)

5.共享区

位于堆和栈之间的文件映射区。

5.数组和指针存储

函数内的指针变量 p和数组变量 s 是分配在栈上。

char *p="123456";
char s[] = "abc";
函数结束以后，变量 p， s 就都不存在了。p 指向的地址仍是有效的，s 所在地址的内容就不确定了。对于字符数组是将字符串放到为数组分配的存储空间去，而对于字符指针是先将字符串存放到内存，然后将存放字符串的内存起始地址送到指针p中。

静态存储区与栈区
```
char* p = “Hello World1”;
char a[] = “Hello World2”;
p[2] = ‘A’;
a[2] = ‘A’;
char* p1 = “Hello World1”
```
这个程序是有错误的，错误发生在p[2] = ‘A’这行代码处，因为变量p和变量数组a都存在于栈区中。但是，数据“Hello World1”和数据“Hello World2”是存储于不同的区域的。
因为数据“Hello World2”存在于数组中，所以，此数据存储于栈区，对它修改是没有任何问题的。而指针变量p仅仅能够存储某个存储空间的地址，数据“Hello World1”为字符串常量，所以存储在静态存储区。虽然通过p[2]可以访问到静态存储区中的第三个数据单元，即字符‘l’所在的存储的单元。但是因为数据“Hello World1”为字符串常量，不可以改变，所以在程序运行时，会报告内存错误。
并且，如果此时对p和p1输出的时候会发现p和p1里面保存的地址是完全相同的。换句话说，在数据区只保留一份相同的数据，栈中只是该数据的起始地址。

6.指针与函数

当函数A准备调用函数B时，需要先把A中调用语句的下一条语句保存起来，通常都是保存到栈里面，这样当函数B返回后，将之前压入栈中的待执行语句从栈中弹出，然后执行流从这条语句接着执行，即函数A继续执行。
函数入口参数按从右到左的顺序入栈，由被调用者清理栈中的参数，返回值放在eax寄存器中。
ebp寄存器为栈帧寄存器（高地址），用来保存每一个函数的栈底位置（内存地址）；esp寄存器为栈顶寄存器（低地址），用来保存每一个函数当前的栈顶位置。EIP存储着下一条指令的地址。

附录：

4个数据寄存器(EAX、EBX、ECX和EDX)
2个变址和指针寄存器(ESI和EDI)
2个指针寄存器(ESP和EBP)
1. 堆与栈

char* f1(){
    char* p = NULL;
    char* q = "stupiddzz";
    /* 对于指针q,虽然运行不会出错，但是函数f1的设计理念却错了，因为函数内的"stupiddzz" 是常量字符串，存放在
       代码段的常量区，生命期内恒定不变，只读不可修改。
    */
    char a;
    p = &a;
    return p;
}
char* p ;
p = f1();
*p = ‘a’;

char* f2(){
    char* p = NULL:
    p =(char*) new char[4];
    return p;
}

void f(){
…
    char * p;
    p = (char*)new char[100];
…
}

f1()函数虽然返回的是一个存储空间，但是此空间为临时空间。也就是说，此空间只有短暂的生命周期，它的生命周期在函数f1()调用结束时，也就失去了它的生命价值，即：此空间被释放掉。如果执行后面的操作此时，编译并不会报告错误，但是在程序运行时，会发生异常错误。因为，你对不应该操作的内存（即，已经释放掉的存储空间）进行了操作。
f2()函数不会有任何问题。因为，new这个命令是在堆中申请存储空间，一旦申请成功，除非你将其delete或者程序终结，这块内存将一直存在。
f()虽然申请了堆内存，p保存了堆内存的首地址。但是此变量是临时变量，当函数调用结束时p变量消失。也就是说，再也没有变量存储这块堆内存的首地址，我们将永远无法再使用那块堆内存了。f函数没有将堆上的首地址返回，该函数结束后，指针p会被释放掉，会造成堆上的内容无法被释放掉，及内存泄漏。

7.堆栈的区别

1.空间大小

堆是不连续的内存区域（因为系统是用链表来存储空闲内存地址，自然不是连续的），堆大小受限于计算机系统中有效的虚拟内存（32bit系统理论上是4G），所以堆的空间比较灵活，比较大。
栈是一块连续的内存区域，大小是操作系统预定好的，windows下栈大小是2M（也有是1M，在编译时确定，VC中可设置）。

2.碎片问题

对于堆，频繁的new/delete会造成大量碎片，使程序效率降低。
对于栈，它是一个先进后出的队列，进出一一对应，不会产生碎片。

3.生长方向

堆向上，向高地址方向增长。
栈向下，向低地址方向增长。

4.分配方式

堆都是动态分配（没有静态分配的堆）。
栈有静态分配和动态分配，静态分配由编译器完成（如局部变量分配），动态分配由alloca函数分配，但栈的动态分配的资源由编译器进行释放，无需程序员实现。

8.函数栈的切换

#include<stdio.h>

int ADD(int x,int y)
{
    int z =  x + y;
    return z;
}

int main()
{
    int a = 10;
    int b = 20;
    int sum = 0;
    sum = ADD(a,b);
    return 0;
}

函数使用默认的调用惯例ADD函数，即参数从右到左入栈，由调用方负责将参数出栈。

所以在栈中还没有为main函数创建栈帧的时候，esp寄存器指向的是前一个函数的栈顶。
调用main函数后开始为main函数创建函数栈帧。将ebp的地址压入栈中，esp值传给ebp，然后开辟出一块global_data空间。

接着在将需要保存的寄存器压入栈中、为新开辟出来的赋值CC CC CC CC。

ebx：是“基地址”(base)寄存器，在内存寻址时存放基地址。链接前是0x00000000
sei/sdi：分别叫做"源/目标索引寄存器"(source/destination index)，因为在很多字符串操作指令中。ESI指向源串，而EDI指向目标串。作用主要是存放存储单元在段内的偏移量，用它们可实现多种存储器操作数的寻址方式，为以不同的地址形式访问存储单元提供方便。
这样main函数的函数栈帧就创建好了，然后开始执行main函数中的语句。

当执行到sum = ADD(a,b)之前，把局部变量存入globale_data区。
当执行到sum = ADD(a,b)后，要先把传递的参数和将返回地址压入栈中，其中eax这里即作为返回值的接受，也作为b值的传参。ecx作为参数a值的传递。并且将将返回地址压入栈中。
之后就可以创建ADD函数的函数栈帧了(准备流程和创建main函数时很相似)

图片说明

执行ADD函数中的操作

图片说明
每一条指令为4个字节大小，因此ebp+8为ecx寄存器，其值为10。ebp+0C为eax寄存器，其值为20。

调用ADD结束后就会销毁该函数的栈帧

图片说明

之后main函数得到返回值：执行计算和存储然后main函数调用完毕，销毁main函数的栈帧。

图片说明

2.内存管理

1.基本概念

1.虚拟地址

虚拟地址是CPU保护模式下的一个概念。程序在运行时都处于虚拟内存当中，虚拟内存里的所有地址都是不直接的，所以你有时候可以看到一个虚拟地址对应不同的物理地址。
解释：

是防止程序对物理地址写数据造成一些不可必要的问题，比如知道了A进程的物理地址，那么向这个地址写入数据就会造成A进程出现问题，在虚拟内存中运行程序永远不知道自己处于内存中那一段的物理地址上！
虚拟内存管理采用一种拆东墙补西墙的形式，所以虚拟内存的内存会比物理内存要大许多。
在进入虚拟模式之前CPU以及Bootloader，操作系统内核均运行在实模式下，直接对物理地址进行操作！

2.逻辑地址

逻辑地址即程序中的段地址，比如说0x1到0x4为一个页面，那么0x1-0x4之间的段地址称为逻辑地址，逻辑地址可以通过内存中的段数组里寻找段选择符+段偏移地址轻易得到物理地址。逻辑地址由两部份组成，段标识符和段内偏移量。
一般操作系统需要维护两个段描述表：GDT（全局描述符表GDT（GlobalDescriptor Table）在整个系统中，全局描述符表GDT只有一张(一个处理器对应一个GDT)，GDT可以被放在内存的任何位置。LDT（局部描述符表可以有若干张，每个进程任务都有一张，LDT对应GDT里的某段子描述符，可以把LDT理解成二级描述符。
局部的表示进程自己的，仅进程自己可以使用，全局的则表示操作系统等所有进程都可以使用！

3.线性地址

线性地址是逻辑地址到物理地址之间的一个中间层变换，程序代码会产生逻辑地址，或者说是段中的偏移地址，加上相应段的基地址就生成了一个线性地址。段的基地址是通过局部LDT段描述符获取的。
如果启用了分页机制，那么MMU内存管理单元会在内存映射表里寻找与线性地址对应的物理地址。若没有启用分页机制，那么线性地址直接就是物理地址。

4.物理地址

物理地址是内存中的内存单元实际地址。

2.连续内存管理

1.单一连续分配

只支持单道程序，内存分为系统区和用户区，用户程序放在用户区。
特点：无外部碎片，有内部碎片。

2.固定分区分配

支持多道程序，内存用户空间分为若干个固定大小的分区，每个分区只能装一道作业。
特点：无外部碎片，有内部碎片。

3.动态分区分配

支持多道程序，在程序装入内存的时候，根据进程的大小动态的建立分区。
特点：无内部碎片，有外部碎片。

3.非连续内存管理

1.基本分页存储管理

一、基础知识
思想：把进程分页，各个页面可离散地放到各个内存快中。
虚拟地址：页
物理地址：页框
逻辑地址分为页号和页内偏移量

二、逻辑地址到物理地址的转换

首先计算逻辑地址的页号和页内偏移量
1. 页号=逻辑地址/页面长度
2. 页内偏移量=逻辑地址%页面长度
页号合法性检查
页号合法，根据页表的起始地址和页号找到对应的页表项（页表项大小相等）。
根据页表项中的内存块号和页内偏移量计算得到物理地址。(物理地址 = 页面的起始地址 + 偏移量)
访问物理单元。

三、块表（TLB）
块表又名TLB又名，联想存储器，是一种访问速度要比内存快的多的高速缓存寄存器，用来存放当前访问的若干个页表项，来加速地址的变换过程。与之相对应的是内存当中的页表叫做慢表。
目的：减少访问页表的次数，加速地址的变换。

地址变换过程：

给出逻辑地址，由硬件算出页号和页偏移量，然后与快表中的页号进行对比。
如果对比成功，则说明要访问的页表项在快表中有副本，则直接取出该页对应的内存快号，再将内存快号和偏移量组合成物理地址。
如果匹配失败，则说明块表中没有对应的副本，则需要访问内存中的页表，找到对应的页表项，得到相应的内存快号，然后将内存快号和偏移量组合成物理地址。最后注意将找到的页表项，存入块表。

四、总结

慢表（页表）
总共访问内存2次。第一次为访问页表项，第二次为访问物理实际地址。
块表
块表没有命中，总共访问内存2次。第一次为访问页表项，第二次为访问物理实际地址。块表命中，总共访问内存1次。即访问物理的实际地址。
页式内存管理，没有外部碎片，有内部碎片。

2.基本分段存储管理

一、基础知识
将地址空间按照程序自身的逻辑关系划分为若干个段，每个段都是从0开始。每个段在内存中占据连续地址空间，各个段之间地址不连续。
逻辑地址由段号和段内偏移量组成。

二、逻辑地址到物理地址的转换

逻辑地址由段号和段内地址偏移组成。
段号和段内寄存器地址长度进行对比，检测是否越界。（相等也是越界）
由段表的起始地址和段号找到对应的段表项
段表项由基址和段长组成，检测段内的地址是否已经超过了段长（多出来的部分）！！！
由段内地址偏移和基址得到对应的物理地址
访问相应的目标

三、总结

第一次查询内存中的段表，然后访问目标内存单元，总共两次。对应分段系统中也可以引入快表机构（TLB），将近期访问过的段表项放到块表中，这样可以少一次访问，加快地址变换速度。
段式内存管理，没有内部碎片，有外部碎片。
分段相比于分页优点是：更容易实现信息的共享和保护。

3.段页式存储管理

一、基础知识
将地址空间按照程序自身的逻辑关系划分为若干个段，将各个段分为大小相等的页。逻辑地址由段号、页号、页内（地址）偏移量组成。
图片说明
每个段对应一个段表项，各个段表项的长度相等，由段号（隐藏）、页表长度（长度）、页表存放地址（基址）组成。
每个页对应一个页表项，各个页表项的长度相等，由页号（隐藏）和页面存放的内存块号组成。

二、逻辑地址转换为线性地址再转换为物理地址

由逻辑地址得到段号、页号和页内偏移量。
段号与段表寄存器中的段长度比较，检查是否越界。
由段表起始地址、段号找到对应的段表项。
根据段表中记录的页表长度，检查页号是否越界。
由段表中的页表地址、页号得到查询页表，找到相应页表项。
由页面存放的内存块号、页内偏移量的到最终的物理地址。
访问目标单元

三、总结

总共三次访问内存，第一次查询段表、第二次查询页表、第三次访问目标单元。
引入块表TLB，以段号和页号为关键字查询块表，即可找到物理地址。仅需要一次访问内存。
段页式内存管理，没有外部碎片，有少量的内部碎片。(减少内存的内部和外部碎片)

4.减少内部碎片和外部碎片的方法

1.段页式内存管理

2.内存池

5.Linux三级页表转换

逻辑地址转线性地址：段起始地址+段内偏移地址=线性地址
线性地址转物理地址：

每一个32位的线性地址被划分为三部分：页目录索引（10位）、页表索引（10位）、页内偏移（12位）

从cr3中取出进程的页目录地址（操作系统调用进程时，这个地址被装入寄存器中）
页目录地址 + 页目录索引 = 页表地址
页表地址 + 页表索引 = 页地址
页地址 + 页内偏移 = 物理地址

3.cache/TLB

1.概述

1.cache

Cache是介于CPU与主内存之间、或者主内存与磁盘之间的高速缓冲器，其作用是解决系统中数据读写速度不匹配的问题。其中介于CPU与主内存之间的缓冲器又称为RAM Cache通常简称的Cache，而介于主内存与磁盘驱动器之间的缓冲器则称之为Disk Cache。
CPU的运算速度比主内存的读写速度要快得多，这就使得CPU在访问内存时要花很长的等待时间，从而造成系统整体性能的下降。为了解决这种速度不匹配的问题，需要在CPU与主内存之间加入比主内存更快的SRAM（Static Ram，静态存储器）。SRAM储存了主内存中的数据(专业术语称为“映象”)，使CPU可以直接通过访问SRAM来读写数据。它能将CPU用过的数据，以及结果保存起来，让CPU下次处理时先来访问Cache，如果没有可用的数据再去别处找，以此来提高运行速度。

2.cache组成

Cache由标记存储器和数据存储器两个基本部分组成。标记存储器是用来储存Cache的控制位与块地址标签。
控制位：用于管理Cache的读写操作
块地址标签：记录着Cache中各块的地址，
这个地址包含了与主内存映射的块地址，并且都与Cache中的一块“数据”相对应。而这块“数据”正是贮存于Cache的数据存储器中。

3.cache命中流程

当CPU读取数据时，先通过地址总线把物理地址送到Cache中，与Cache中的块地址标签进行对比。若相符合，则表示此数据已经存在于Cache中（此情况被戏称为“命中”），这时只需把Cache中的对应数据经由数据总线直接传送给CPU即可。但如果CPU送来的物理地址无法与Cache中的块地址标签相符，则表明这一数据不在Cache中（称为“失误”），这时需要由主内存把CPU所需的数据地址拷贝到Cache中，再由Cache把数据传送给CPU。

4.cache缺陷

从这个过程我们可以看到，若CPU读取“命中”，存取速度确实可以提高许多，但如果“失误”，则Cache的存在反而减慢了CPU的读取速度。因此，采用何种技术和方法提高读写命中率、减少失误率，就成了Cache设计的关键。加大Cache的容量当然可以提高命中率，但因成本问题，Cache不可能无限增大，但可以通过采用适当的映射方式和块替代方式来提高命中率。

2.提高命中率的办法

1.映射方式

1.直接映射（多对一的映射关系）
图片说明
如果主内存上的块只能映射到Cache中的特定块，我们称这种映射方式为直接映射。直接映射的存取速度最快，但失误率也最高。
例如：
cache的大小称之为cahe size，代表cache可以缓存最大数据的大小。我们将cache平均分成相等的很多块，每一个块大小称之为cache line，其大小是cache line size。64 Bytes大小的cache，并且cache line大小是8字节。cache line是cache和主存之间数据传输的最小单位。
图片说明
CPU从0x0654地址读取一个字节，cache控制器是如何判断数据是否在cache中命中呢？

所以cache肯定是只能缓存主存中极小一部分数据。我们如何根据地址在有限大小的cache中查找数据。硬件采取的做法是对地址进行散列（可以理解成地址取模操作）。
我们一共有8行cache line，cache line大小是8 Bytes。所以我们可以利用地址低3 bits（如上图地址蓝色部分）用来寻址8 bytes中某一字节，我们称这部分bit组合为offset。同理，8行cache line，为了覆盖所有行。我们需要3 bits（如上图地址黄色部分）查找某一行，这部分地址部分称之为index。只由index无法判断地址是否真的已经在cache中，因此引入tag array区域（标记数组），tag array和data array一一对应。每一个cache line都对应唯一一个tag，tag中保存的是整个地址位宽去除index和offset使用的bit剩余部分。因此tag、index和offset三者组合就可以唯一确定一个地址了。当我们根据地址中index位找到cache line后，取出当前cache line对应的tag，然后和地址中的tag进行比较，如果相等，这说明cache命中。
tag旁边还有一个valid bit，这个bit用来表示cache line中数据是否有效（例如：1代表有效；0代表无效）。当系统刚启动时，cache中的数据都应该是无效的，因为还没有缓存任何数据。cache控制器可以根据valid bit确认当前cache line数据是否有效。
index指向的每个cache line后面Dirty的1代表dirty，0代表没有写过数据，即非dirty。

2.完全映射
在这种映射方式下，主内存上的块可以映射到Cache的任意块之中，当CPU欲读取某一个块时，Cache会把CPU送来的地址与Cache中的所有地址标签进行对比。由于是完全对比，因此存取时间最长，但失误率也最低。

3.结合映射（多路组映射）
这种映射方式是把Cache分成若干个页面（组），每个页面会有相同数目的块。主内存中数据块可以映射到Cache中指定页面的任一块中。这种映射方式可以看成是直接映射与完全映射的折衷，是效率最高的映射方式。
图片说明
假设64 Bytes cache size，cache line size是8 Bytes。什么是路（way）的概念。我们将cache平均分成多份，每一份就是一路。
我们将所有索引一样的cache line组合在一起称之为组。例如，上图中一个组有两个cache line，总共4个组（set）。
先根据index找到set，然后将组内的所有cache line对应的tag取出来和地址中的tag部分对比，如果其中一个相等就意味着命中。
差异：一个地址对应的数据可以对应2个cache line，而直接映射缓存一个地址只对应一个cache line，降低了cache颠簸（同一个cache line对应多个地址）的频率。

2.块（cache line）代替

由于当CPU的存取出现“失误”时，必须从主内存把相应的块地址与数据写入Cache中，若此时Cache已经饱和，写入的数据必然会覆盖掉Cache中原有的数据，这就是“块替代”。
1.先入先出
新写入的块取代最先存放到Cache中的旧块。
2.随机替代
新写入的块随机地取代Cache中的旧块。
3.最近、最不常用替代方式（LRU，Least Recent Used）
新写入的块将取代Cache中最少被CPU访问的旧块。

3.块的替换引发的问题

在CPU的读取操作中，Cache中的数据与主内存上的数据是一致的。但是当CPU向Cache写入新的数据时，则会出现Cache与主内存之间数据不一致的情况。解决的方法有两种。

1.写通（Write through）

当CPU向Cache写入数据时，同时也把数据写入主内存，或同时把数据写到一个缓冲器中，待CPU空闲时再把数据写入主内存。此方式简单可靠，但由于CPU每次写入数据时都要同时对主内存的相应数据进行刷新，因而速度较慢。

2.写回（Write back）

当CPU要进行写入操作时，只把数据写入Cache，而不直接写入主内存。这时，Cache与主内存之间会出现暂时不一致的数据块。当Cache中的不一致数据块将要被替代时，再把数据写回主内存，从而使Cache中的数据与主内存中的数据又再保持一致。即通过index指向的每个cache line后面都有一个Dirty位。1代表写过数据，0代表没有写过数据。

4.cache与TLB的区别

cache与TLB不同在于TLB中的对应项不必同步，因为运行在现有CPU上的进程可以使用同一线性地址与不同物理地址发送联系。cache是在物理地址上做操作的。

4.I/O设备实现输入和输出的方式有三种

方式一：系统调用

用户程序发出一个系统调用，设备驱动程序启动I/O并在一个循环中不断检查该设备，看该设备是否完成了工作。当I/O结束后，设备驱动程序把数据送到指定的地方（若有需要），并返回。然后操作系统将控制返回给调用者。这种方式是忙等待，缺点是要占据CPU，CPU一直轮询设备知道对应的I/O操作完成。这样效率并不高。

方式二：中断

设备驱动程序启动设备并且让该设备在操作完成时发出一个中断。

方式三：DMA

为I/O使用一种特殊的直接存储器访问（Direct Memory Access，DMA）芯片，它可以直接控制外围设备的数据流，而无需持续的CPU干预。这样效率就很高了，但对应成本就相对高些，因为DMA是由专门的硬件（ DMA）控制。DMA传送主要用于需要高速大批量数据传送的系统中，以提高数据的吞吐量。
因为无需CPU干预，那么DMA要进行数据传输就必须有三个条件：