参考视频讲解
数据结构
$\color{red}{\text{红黑树}}$
红黑树p1
红黑树p2
为什么要发明红黑树?
红黑树的定义和性质
红黑树的思维导图
黑高h最少的节点个数
$\color{red}{\text{并查集}}$
王道辅导2022没有删除这个内容
并查集未优化的时间复杂度
并查集union的优化
树高不超过 $\lfloor log_2 n \rfloor + 1$
并查集的应用-判断图的连通分量的个数
并查集的应用-判断图的连通分量的个数，代码
并查集的应用-判断图的连通分量的个数，代码
并查集的应用-kruskal，：时间复杂度$elog_2e$
并查集的思维导图
并查集find的操作：路径压缩
并查集的两次优化的时间复杂度对比
计算机组成原理
$\color{red}{\text{补码加减运算器}}$
要求掌握运算器硬件的基本原理
加法器的原理
加法器的原理
补码加/减法运算方法
补码加/减法运算方法
补码加减运算器的设计
无符号数和有符号数的实现逻辑是一样的
有符号数
无符号数的例子
$\color{red}{\text{标志位的生成}}$
加减法中产生CF、OF、ZF、SF标志位的原理，王道书2.4.2内容
有符号数看OF
无符号数看CF
标志位的生成的思维导图
2018，2011的真题
真题
真题
$\color{red}{\text{乘法电路和除法电路的基本结构}}$
乘法电路和除法电路的基本结构
乘法电路结构
无符号数和有符号数乘法电路的对比
双符号位需要多一次加法
32位无符号数乘法运算的逻辑结构图
图2.1中，部分积和被乘数X做无符号数加法时，可能产生进位，因此需要一个专门的进位位C。乘积寄存器Р初始时置0。计数器 $C_n$ 初值为32，每循环一次减1。ALU是乘法核心部件，对乘积寄存器Р和被乘数寄存器X的内容做“无符号加法”运算，运算结果送回寄存器P，进位存放在C中。每次循环都对进位位C、乘积寄存器Р和乘数寄存器Y实现同步“逻辑右移”，此时，进位位C移入寄存器Р的最高位，寄存器Y的最低位移出。每次从寄存器Y移出的最低位都被送到控制逻辑，以决定被乘数是否“加”到部分积上。
图2.2补码一位乘法的逻辑结构图
图2.2是实现32位补码一位乘法的逻辑结构图，和图2.1所示的逻辑结构很类似。因为是带符号数运算，不需要专门的进位位。每次循环，乘积寄存器Р和乘数寄存器Y是实现同步“算术右移”，每次从寄存器Y移出的最低位和它的前一位来决定是 $-[x]{\text{补}}$ ， $+[x]{\text{补}}$ 还是+0。
除法电路
n位定点数的除法运算,实际上是用一个2n位的数去除以一个n位的数,得到一个n位的商，因此需要对被除数进行扩展。对于n位定点正小数，只要在被除数的低位添n个0即可;对于n位定点正整数，只要在被除数的高位添n个0即可。
图2.3是一个32位除法逻辑结构图，它和除法逻辑结构也很类似。
图2.3 32位除法运算的逻辑结构图
初始时，寄存器R存放扩展被除数的高位部分，寄存器Q存放扩展被除数的低位部分。ALU是除法器核心部件，对余数寄存器R和除数寄存器Y的内容做“加/减”运算，运算结果送回寄存器R。每次循环，寄存器R和Q实现同步左移，左移时，Q的最高位移入R的最低位，Q中空出的最低位被上商。每次由控制逻辑根据ALU运算结果的符号来决定上商为0还是1。
加减交替法，不恢复余数法
定点数小数除法
定点整数的除法
DRAM芯片和内存条
DRAM芯片和内存条
$\color{red}{\text{固态硬盘SSD}}$
固态硬盘的知识点
固态硬盘(SSD)是一种基于闪存技术的存储器。它与U盘并没有本质差别，只是容量更大,存取性能更好。一个SSD由一个或多个闪存芯片和闪存翻译层组成，闪存芯片替代传统旋转磁盘中的机械驱动器,而闪存翻译层是将来自CPU的逻辑块读写请求翻译成对底层物理设备的读写控制信号，因此，这个闪存翻译层相当于扮演了磁盘控制器的角色。
图3.3 固态硬盘（SSD)
如图3.3所示，一个闪存由B个块组成，每个块由Р页组成。通常，页的大小是512B～4KB,每个块由 32～128个页组成，块的大小为16KB~512KB。数据是以页为单位读写。只有在一页所属的块整个被擦除之后，才能写这一页。不过，一旦一个块被擦除了，块中的每一个页都可以直接再写一次。若某一个块进行了约10万次重复写之后，就会磨损坏，不能再使用。
随机写很慢，有两个原因。首先，擦除块比较慢，1ms级，比访问页高一个数量级。其次，如果写操作试图修改一个包含已有数据的页 $P_i$ ，那么这个块中所有含有用数据的页都必须被复制到一个新（擦除过的）块，然后才能进行对页$P_i$的写。
比起传统磁盘，SSD有很多优点，它由半导体存储器构成，没有移动的部件，因而随机访问时间比机械磁盘要快很多，也没有任何机械噪声和震动，能耗更低，抗震性好，安全性高等。不过，SSD也有缺点，因为反复写之后，闪存块会磨损，所以SSD也容易磨损。闪存翻译层中有一个平均磨损逻辑试图通过将擦除平均分布在所有的块上来最大化每个块的寿命。实际上，平均磨损逻辑处理得非常好，要很多年SSD才会磨损坏。
随着技术的不断发展，价格也不断下降，SSD会有望逐步取代传统机械硬盘。
$\color{red}{\text{高级语言程序与机器级代码之间的对应}}$
19年的45题，17年的44题
14年，12年的44题
X86汇编语言
OP + 数
数: 寄存器、内存
标志位码的含义
ebp+8代表当前函数的局部变量
编译器，汇编器和链接器的基本概念
编译器、汇编器和链接器的基本概念已在第一章中介绍过。
编译器、汇编器和链接器的基本概念
务必先看王道书X86汇编指令。这里补充机器指令的一点内容:
由于32或64位体系结构都是由16位扩展而来，因此术语“字(word)”表示16位。大多数GCC 生成的汇编代码指令都有一个字符的后缀，表明操作数的大小。例如，数据传送指令有四个变种: movb(传送字节)、movw（传送字)、movl(传送双字)、movq(传送四字)。
过程（函数)调用对应的机器级表示（csapp164）
前面提到的call/ret 指令主要用于过程调用，它们都属于一种无条件转移指令。
假定过程Р(调用者）调用过程Q（被调用者)，过程调用的执行步骤如下:
1)Р将入口参数（实参）放在Q能访问到的地方。
2)Р将返回地址存到特定的地方，然后将控制转移到Q。
3)Q保存Р的现场（通用寄存器的内容)，并为自己的非静态局部变量分配空间。
4）执行过程Q。
5)Q恢复Р的现场，将返回结果放到Р能访问到的地方，并释放局部变量所占空间。
6）О取出返回地址，将控制转移到P。
第2）步是由call 指令实现的，第6）步通过ret 指令返回到过程P。在上述步骤中，需要为入口参数、返回地址、过程Р的现场、过程Q的局部变量、返回结果找到存放空间。但用户可见寄存器数量有限，为此需要设置一个专门的存储区域来保存这些数据，这个存储区域就是栈。寄存器EAX、ECX和EDX是调用者保存寄存器，其保存和恢复的任务由过程Р负责，当Р调用Q时，Q就可以直接使用这三个寄存器。寄存器EBX、ESI、EDI是被调用者保存寄存器，Q必须先将它们的值保存在栈中才能使用它们，并在返回P之前先恢复它们的值。
每个过程都有自己的栈区，称为栈帧，因此，一个栈由若干栈帧组成。帧指针寄存器EBP指示栈帧的起始位置（栈底)，栈指针寄存器ESP指示栈顶（栈顶)栈从高地址向低地址增长，因此，当前栈帧的范围在帧指针EBP和 ESP指向的区域之间。
下面用一个简单的C语言程序来说明过程调用的机器级实现。
代码
经GCC 编译后 caller过程对应的代码如下人#后面的文字是注释)。
p1
p2
p3
异常和中断
异常的分类、及与外中断的区别已在第七章中介绍过。
这里再补充两段:
内部异常和外部中断的识别方式不大相同，通常采用软件识别方式来检测内部异常。软件识别方式是指，CPU 设置一个异常状态寄存器，用于记录异常原因。操作系统使用一个统一的异常查询程序，该程序按一定的优先级顺序查询异常状态寄存器，先查询到的异常先被处理.
像故障和陷阱之类的内部异常通常是在执行某条指令时发现的，可以通过对指令执行过程中某些条件的判断来发现是否发生了异常，而且一旦发现可以马上进行处理，所以，内部异常事件也可以不通过专门的查询程序来识别，而在发现异常时直接得到异常错误代码，根据不同的错误代码，转到相应的异常处理程序即可，80x86的处理方式就是这样的。
异常和中断的处理过程基本是相同的，这是为什么有的教材把两者统称为中断的原因。
$\color{green}{\text{多处理器基本概念}}$
例题
SISD、SIMD、MIMD、向量处理器的基本概念
基于指令流的数量和数据流的数量，对计算机体系结构分为SISD、SIMD、MISD和 MIMD四类。常规的单处理器属于SISD，而常规的多处理器属于MIMD。
思维导图
单指令流单数据流机器(SISD)
SISD机器是一种传统的串行计算机，它的硬件不支持任何形式的并行计算所有的指令都是串行执行。并且在某个时钟周期内，CPU只能处理一个数据流因此这种机器被称作单指令流单数据流机器。早期的计算机都是SISD机器，如 $\color{green}{\text{冯诺.依曼架构}}$ ，如IBM PC机，早期的巨型机和许多8位的家用机等。
SISD是传统的串行计算机结构,这种计算机通常仅包含一个处理器和一个存储器，处理器在一段时间内仅执行一条指令，按指令流规定的顺序串行执行指令流中的若干条指令。为了提高速度，有些SISD计算机采用流水线的方式，因此，SISD处理器有时会设置多个功能部件，并采用多模块交叉方式组织存储器。本书前面介绍的内容多属于SISD结构。
SISD
SISD
单指令流多数据流机器(SIMD)
SIMD是指一个指令流同时对多个数据流进行处理，一般称为数据级并行技术。这种结构的计算机通常由一个指令控制部件、多个处理单元组成。每个处理单元虽然都执行的是同一条指令，但每个单元都有自己的地址寄存器，这样每个单元都有不同的数据地址，因此，不同处理单元执行的同一条指令所处理的数据是不同的。一个顺序应用程序编译后，可能按SISD 组织并运行于串行硬件上，也可能按 SIMD组织并运行于并行硬件上。
SIMD在使用for循环处理数组时最有效，比如，一条分别对16对数据进行运算的SIMD指令如果在16个ALU中同时运算，则仅需一次运算时间就能完成这16对数据的运算。SIMD在使用case或switch语句时效率最低，此时每个执行单元必须根据不同的数据执行不同的操作。
Intel处理器实现的MMXTM、SSE ( Streaming SIMD Extensions) .SSE2及SSE3扩展指令集，都能在单个时钟周期内处理多个数据单元。也就是说我们现在用的单核计算机基本上都属于SIMD机器。
SIMD
SIMD王道
多指令流单数据流机器(MISD)
MISD是指同时执行多条指令，处理同一个数据，实际上不存在这样的计算机。
MISD
多指令流多数据流机器(MIMD)
MIMD机器可以同时执行多个指令流，这些指令流分别对不同数据流进行操作。最新的多核计算平台就属于MIMD的范畴，例如Intel和AMD的双核处理器等都属于MIMD。
MIMD是指同时执行多条指令分别处理多个不同的数据,MIMD分为多计算机系统或多处理器系统。多计算机系统中的每个计算机节点都具有各自的私有存储器，并具有独立的主存地址空间，不能通过存取指令来访问不同节点的私有存储器，而是通过消息传递进行数据传送，也称为消息传递MIMD。多处理器系统是共享存储多处理器(SMP）系统的简称，它具有共享的单一地址空间，通过存取指令来访问系统中的所有存储器，也称为共享存储 MIMD.
MIMD
MIMD王道
MIMD王道-多计算机系统
向量处理器
向量处理器是SIMD 的变种，它是一种实现了直接操作一维数组(向量）指令集的CPU，而串行处理器只能处理单一数据集。其基本理念是将从存储器中收集的一组数据按顺序放到一组向量寄存器中，然后以流水化的方式对它们依次操作，最后将结果写回寄存器。向量处理器在特定工作环境中极大地提升了性能，尤其是在数值模拟或者相似领域。
SIMD和 MIMD是两种并行计算模式，其中 SIMD是一种数据级并行模式，而MIMD是一种并行程度更高的线程级并行或线程级以上并行计算模式。
向量处理器的结构
向量处理器的思维导图
硬件多线程的基本概念
在传统CPU 中，线程的切换包含一系列的开销，频繁的切换会极大影响系统性能，为了减少线程切换过程中的开销，便诞生了硬件多线程。在支持硬件多线程的CPU中，必须为每个线程提供单独的通用寄存器组、单独的程序计数器等，线程的切换只需激活选中的寄存器，从而省略了与存储器数据交换的环节，大大减少了线程切换的开销。
硬件多线程有3种实现方式:细粒度多线程、粗粒度多线程和同时多线程（SMT)。
细粒度多线程
多个线程之间轮流交叉执行指令，多线程之间的指令是不相关的，可以乱序并行执行。这种方式下，处理器能在每个时钟周期切换线程。例如，在时钟周期i,将线程A中的多条指令发射执行;在时钟周期i+1，将线程B中的多条指令发射执行。
细粒度多线程：实现指令级的并行，没有实现线程级的并行
粗粒度多线程
仅在一个线程出现了较大开销的阻塞时，才切换线程，如 Cache缺失。这种方式下，当发生流水线阻塞时，必须清除被阻塞的流水线,新线程的指令开始执行前需要重载流水线，因此， $\color{green}{\text{线程切换的开销比细粒度多线程更大}}$ 。
粗粒度多线程：实现指令级的并行，没有实现线程级的并行
同时多线程
同时多线程(SMT）是上述两种多线程技术的变种，它实现指令级并行的同时实现线程级并行，即，它在同一时钟周期中，发射多个不同线程中的多条指令执行。
同时多线程： $\color{green}{\text{实现指令级的并行}}$ ， $\color{green}{\text{实现线程级的并行}}$
图5.1分别是三种硬件多线程实现方式的调度示例。
5.1三种硬件多线程方式的调度示例
Intel处理器中的超线程（Hyper-threading)即为同时多线程SMT，在一个单处理器或单个核中设置了多套线程状态部件，而共享高速缓存和功能部件。
多核处理器(multi-core)的基本概念
多核处理器是将多个处理单元集成到单个CPU中，每个处理单元称为一个核(core)。每个核可以有独自的 Cache，也可以共享同一Cache。所有核一般都是对称的，并共享主存储器，因此多核属于共享存储的对称多处理器(SMP)。图5.1是一个不共享Cache的双核CPU结构。
图5.1不共享Cache的双核CPU结构
在多核计算机系统中，如要充分发挥硬件的性能，必须采用多线程（或多进程）执行，使得每个核在同一时刻都有线程在执行。和单核上的多线程不同，多核上的多个线程是在物理上并行执行的，是真正意义上的并行执行，在同一时刻有多个线程在并行执行。而单核上的多线程是一种多线程交错执行，实际上在同一时刻只有一个线程在执行。
通过一个例子来理解相关概念。假设要将四个圆石头滚到马路对面，滚动每个石头平均需花费1分钟。串行处理器会逐一滚动每个石头，花费4,分钟。拥有两个核的多核处理器让两个人去滚石头，即每人滚两个，花费2分钟。向量处理器找一根长木板，放在四个石头后面，推动木板即可同时滚动四个石头，理论上只需要1分钟。多核处理器相当于拥有多个工人，而向量处理器拥有一种方法，可以同时对多件事进行相同的操作。
共享内存多处理器(SMP)的基本
具有共享的单一物理地址空间的多处理器称为共享内存多处理器(SMP)。处理器通过存储器中的共享变量互相通信，所有处理器都能通过存取指令访问任何存储器位置。注意，即使这些系统共享同一个物理地址空间，它们仍然可以在自己的虚拟地址空间中单独地运行程序。
单一地址空间的多处理器有两种类型。第一类，每个处理器对所有存储单元的访问时间是大致相同的，即访问时间与哪个处理器提出访存请求及访问哪个字无关，这类机器称为统一存储访问（UMA)多处理器。第二类，某些访存请求会比其他的快，这取决于是哪个处理器提出访问请求、及访问哪个字，这是由于主存被分割并分配给同一个芯片上的不同的处理器或内存控制器，这类机器称为非统一存储访问(NUMA）多处理器。
- 统一存储访问（UMA）多处理器:根据处理器与共享存储器之间的链接方式，分为基于总线、基于交叉开关网络和基于多级交换网络连接等几种处理器。
- 非统一存储访问(NUMA）多处理器:处理器中不带高速缓存时，被称为NC-NUMA;处理器中带有一致性高速缓存时，被称为CC-NUMA。
由于可能会有多个处理器同时访问同一共享变量，所以在操作共享变量时需要进行同步。否则，一个处理器可能会在其他处理器尚未完成对共享变量的修改时就开始使用该变量了。常用方法是通过对共享变量加锁的方式来控制对共享变量互斥访问。在一个时刻只能有一个处理器获得锁，其他要操作该共享变量的处理器必须等待，直到该处理器解锁该变量为止。
共享内存多处理器和多计算机系统的区别
$\color{red}{\text{总线事务}}$
从请求总线到完成总线使用的操作序列称为总线事务，它是在一个总线周期中发生的一系列活动。典型的总线事务包括请求操作、裁决操作、地址传输、数据传输和总线释放。
1）请求操作。主设备(CPU或DMA）发出总线传输请求，并获得总线控制权。
2）仲裁阶段。总线仲裁机构决定将下一传输周期的总线使用权授予某一申请者。
3）寻址阶段。主设备通过总线给出要访问的从设备地址及有关命令，启动从模块.
4）传输阶段。主模块和从模块进行数据交换，可单向或双向进行数据传送。
5）释放阶段。主模块的有关信息均从系统总线上撤除，让出总线使用权。
操作系统
程序运行时内存映像与地址空间
程序的链接与装入、地址空间，王道书第3章P149。
不同于存放在硬盘上的可执行程序文件，当一个程序调入内存运行时就构成了进程的内存映像，一个进程的内存映像一般有几个要素:
- 代码段:即程序的二进制代码，代码段是只读的，可以被多个进程共享。
- 数据段:即程序运行时加工处理对象，包括全局变量和静态变量。
- 进程控制块（PCB）:存放在系统区。操作系统通过PCB来控制和管理进程。
- 堆:用来存放动态分配的变量。
- 栈:用来实现函数调用。
代码段和数据段在程序调入内存时就指定了大小，而堆和栈不一样。当调用像malloc和 free这样的C标准库函数时，堆可以在运行时动态地扩展和收缩。用户栈在程序运行期间也可以动态地扩展和收缩，每次调用一个函数，栈就会增长;/从一个函数返回时，栈就会收缩。
图1.1是一个进程在内存中的映像。其中，共享库用来存放进程用到的共享函数库代码，如printf()函数等。在只读代码段中，.init是程序初始化时调用的_init 函数; .text是用户程序的机器代码;.rodata是只读数据。在读/写数据段中，.data是已初始化的全局变量和静态变量;.bss是未初始化及所有初始化为0的全局变量和静态变量。
图1.1 内存中的一个进程
每个进程都有一个独立的地址空间，这个地址空间的地址为虚拟地址，对于32位系统，虚拟地址空间的范围为0～ $2^{32}$ -1。进行在运行时，看到和使用的地址都是虚拟地址。
系统中还有一个物理地址空间，对应于系统中物理内存的所有可寻址单元。
操作系统通过内存管理部件（MMU）将进程使用的虚拟地址转换为物理地址。进程使用虚拟内存中的地址，操作系统在相关硬件的协助下，把它“转换”成真正的物理地址。虚拟地址通过页表映射到物理内存，页表由操作系统维护并被处理器引用。
分层、模块化、外核
各种类型操作系统的区别、优缺点
微内核vs大内核
外核
随着操作系统功能的不断增多和代码规模的不断扩大，提供合理的结构，对于降低操作系统复杂度、提升操作系统安全与可靠性来说变得尤为重要。
分层法
分层法是将操作系统分为若干层次，最底层（层0)为硬件，最高层（层N）为用户接口，每层只能调用紧邻它的低层的功能和服务（单向依赖）。这种分层结构如图1.2所示。
图1.2分层的操作系统
分层法的优点:①便于系统的调试和验证，简化了系统的设计和实现。第1层可先调试而无需考虑系统其他部分，因为它只使用了基本硬件。第1层调试完且验证正确之后，就可调试第2层，如此向上。如果在调试某层时发现错误，那么错误应在这层上，这是因为其低层都已调试好了。②易扩充和易维护。在系统中增加、修改或替换一个层次中的模块或整个层次时，只要不改变相应层次间的接口，就不会影响其他层次。
分层法的问题:①合理定义各层比较困难。因为依赖关系固定后，往往就显得不够灵活。②效率较差。操作系统每执行一个功能，通常要自上而下穿越多个层，每层之间都有相应的层次间通信机制，这无疑增加了额外的开销，导致系统效率降低。
模块化
模块化是将操作系统按功能划分为若干个具有一定独立性的模块。每个模块具有某方面的管理功能，并规定好各模块间的接口，使各模块之间能通过接口进行通信。还可以进一步将各模块细分为若干个具有一定功能的子模块，同样也规定好各子模块之间的接口。把这种设计方法称为模块-接口法，图1.3所示为由模块、子模块等组成的模块化操作系统结构。
模块化结构的操作系统
在划分模块时，如果将模块划分得太小，虽然能降低模块本身的复杂性，但会引起模块之间联系过多，而造成系统比较混乱;如果模块划分得过大，又会增加模块内部的复杂性，显然应在两者间进行权衡。此外，在划分模块时，要充分考虑模块的独立性问题，因为模块独立性越高，各模块间的交互就越少，系统的结构也就越清晰。衡量模块的独立性主要由两个标准:
- 内聚性，模块内部各部分间联系的紧密程度。内聚性越高，模块独立性越好。
- 耦合度，模块间相互联系和相互影响的程度。耦合度越低，模块独立性越好。
模块化的优点:①提高了操作系统设计的正确性、可理解性和可维护性;②增强了操作系统的可适应性;③加速了操作系统的开发过程。
模块化的缺点:①模块间的接口规定很难满足对接口的实际需求。②各模块设计者齐头并进，每个决定无法建立在上一个已验证正确决定的基础上，因此无法寻找到一个可靠的决定顺序。
宏内核
从操作系统的内核架构来划分，可分为宏内核和微内核。
宏内核，也称单内核或大内核，是指将系统的主要功能模块都作为一个紧密联系的整体运行在核心态，从而为用户程序提供高性能的系统服务。因为各管理模块之间共享信息，能有效利用相互之间的有效特性，所以具有无可比拟的性能优势。
随着体系结构和应用需求的不断发展，需要操作系统提供的服务越来越复杂，操作系统的设计规模急剧增长，操作系统也面临着“软件危机”困境。就像一个人，越胖活动起来就越困难。所以就出现了微内核技术，就是将一些非核心的功能移到用户空间去，这种设计带来的好处就是方便扩展系统，所有新服务都可以在用户空间增加，内核基本不用去做改动。
从操作系统的发展来看，宏内核获得了绝对的胜利，目前主流的操作系统，如 Windows.Android、iOS、macOS、Linux 等，都是基于宏内核的构架。
微内核
为了解决操作系统的内核代码难以维护的问题，提出了微内核构架。它将内核中最基本的功能（如进程管理等）保留在内核，而将那些不需要在核心态执行的功能移到用户态执行，从而降低了内核的设计复杂性。那些移出内核的操作系统代码根据分层的原则被划分成若干服务程序，它们的执行相互独立，交互则都借助于微内核进行通信。
在现代操作系统设计中，即使是在单机环境下，大多也采用基于客户/服务器模式的微内核结构，将操作系统划分为两大部分:微内核和多个服务器。微内核是指精心设计的、能实现操作系统最基本核心功能的小型内核，通常包含;①与硬件处理紧密相关的部分;②一些较基本的功能;③客户和服务器之间的通信。这些部分只是为构建通用操作系统提供一个重要基础，这样就可以确保把操作系统内核做得很少。操作系统中绝大部分功能都放在微内核外都一组服务器（进程)中实现，如用于提供对进程（线程)进行管理的进程（线程）服务器、提供虚拟存储器管理功能的虚拟存储器服务器等，它们都是作为进程来实现的，运行在用户态，客户与服务器之间是借助微内核提供的消息传递机制来实现交互的。图1.4展示了单机环境下的客户/服务器模式。
单机环境下的客户/服务器模式
在微内核结构中，为了实现高可靠性，只有微内核运行在内核态，其余模块都运行在用户态，一个模块中的错误只会使这个模块崩溃，不会使整个系统崩溃。例如，文件服务代码运行时出了问题，宏内核因为文件服务是运行在内核态的，直接就系统崩溃了。而微内核的文件服务是运行在用户态的，只要把文件服务功能强行停止然后重启就可以继续使用了，系统不会崩溃。
微内核结构的优点主要有:
①扩展性和灵活性。许多功能从内核中分离出来，当要修改某些功能或增加新功能时，只需在相应的服务器中修改或新增功能，或再增加一个专门的服务器，而无需改动内核代码。
②可靠性和安全性。前一段中已举例说明。
③可移植性。与CPU和IO硬件有关的代码均放在内核，而其他各种服务器，均与硬件平台无关，因而把操作系统移植到另一个平台上所需作的修改是比较小的。
④分布式计算。客户和服务器之间、服务器和服务器之间的通信采用消息传递机制，这就使得微内核系统能很好地支持分布式系统和网络系统。
微内核结构的主要问题是性能问题，因为需要频繁地在核心态和用户态之间进行切换，操作系统的执行开销偏大。为了改善运行效率，可以将那些频繁使用的系统服务又移回内核，从而保证系统性能，但这又会使微内核的容量明显地增大。
虽然宏内核在桌面操作系统中取得了绝对的胜利，但微内核在实时、工业、航空及军事应用中特别流行，这些领域都是关键任务，需要有高度的可靠性。
外核
不同于虚拟机克隆真实机器，另一种策略是对机器进行分区。给每个用户整个资源的一个子集。这样，某个虚拟机可能得到磁盘的0至1023盘块，而另一台虚拟机会得到1024至2047盘块，等等。在底层中，一种称为外核( exokernel)的程序在内核态中运行。它的任务是为虚拟机分配资源，并检查使用这些资源的企图，以确保没有机器会使用他人的资源。每个用户层的虚拟机可以运行自己的操作系统，但限制只能使用已经申请并且获得分配的那部分资源。
外核机制的优点是减少了映射层。在其他的设计中，每个虚拟机都认为它有自己的磁盘，其盘块号从0到最大编号,这样虚拟机监控程序必须维护一张表格以重映像磁盘地址(或其他资源),有了外核，这个重映射处理就不需要了。外核只需要记录已经分配给各个虚拟机的有关资源即可。这个方法还有一个优点，它将多道程序（在外核内）与用户操作系统代码（在用户空间内）加以分离，而且相应负载并不重，这是因为外核所做的只是保持多个虚拟机彼此不发生冲突。
操作系统引导
重点掌握unix的操作系统
操作系统的引导过程
操作系统（如 windows、Linux等)是一种程序，程序以数据的形式存放在硬盘中，而硬盘通常分为多个区，一个计算机中又有多个或多种外部存储设备。操作系统引导就是，计算机利用CPU运行特定程序，通过程序识别硬盘，识别硬盘分区，识别硬盘分区上的操作系统，最后又通过程序启动操作系统，一环扣一环地完成上述过程。
常见操作系统的引导过程如下:
①激活CPU。激活的CPU读取ROM里的 boot程序，将指令寄存器置为BIOS（基本输入输出系统，存放在CMOS 中)的第一条指令，即开始执行BIOS的指令。
${\textstyle\unicode{x2461}}$ 硬件自检。启动BIOS程序后，先进行硬件自检，检查硬件是否出现故障。如有故障，主板会发出不同含义的蜂鸣，启动中止;如无故障，屏幕会显示CPU、内存、硬盘等信息。
③加载带有操作系统的硬盘。硬件自检后，BIOS开始读取 Boot Sequence(在COMS里设置的启动顺序)，把控制权交给启动顺序排在第一位的存储设备，然后CPU将该存储设备引导扇区的内容加载到内存中。CPU本身并不知道谁是系统硬盘，而是通过遍历的方式寻找带有主引导记录的系统硬盘，主引导记录的作用是告诉CPU去硬盘的哪个主分区去找操作系统。
④加载主引导记录MBR。硬盘以特定的标识符区分引导硬盘和非引导硬盘。如果发现一个存储设备不是可引导盘，就检查下一个存储设备。如无其他启动设备，就会死机。
${\textstyle\unicode{x2464}}$ 加载硬盘分区表。主引导记录获得控制权后，需要找出哪个硬盘分区含有操作系统，于是开始扫描硬盘分区表，进而识别含有操作系统的硬盘分区（活动分区)。其中，MBR包含硬盘分区表，硬盘分区表以特定的标识符区分活动分区和非活动分区。
⑥加载磁盘活动分区。主引导记录在找到硬盘活动分区后，开始加载硬盘活动分区。每个分区可以安装不同的操作系统，主引导记录必须知道将控制权交给哪个分区。
⑦加载分区引导记录PBR。读取活动分区的第一个扇区，这个扇区叫分区引导记录PBR，其作用是寻找并激活分区根目录下，用于引导操作系统的程序（启动管理器)。
⑧加载启动管理器。分区引导记录搜索活动分区中的启动管理器，加载启动管理器。
${\textstyle\unicode{x2468}}$ 加载操作系统。
虚拟机
虚拟机是一个逻辑的计算机，它是指利用特殊的虚拟化技术，通过隐藏特定计算平台的实际物理特性，为用户提供抽象的、统一的、模拟的计算环境。有两类虚拟化方法
第一类虚拟机管理程序和第二类虚拟机管理程序
两类虚拟机管理程序(VMM)的对比
第一类虚拟机管理程序
从技术上讲，第一类虚拟机管理程序就像一个操作系统，因为它是唯一一个运行在最高特权级的程序。它在裸机上运行并且具备多道程序功能。虚拟机管理程序向上层提供了若干台虚拟机，这些虚拟机是裸机硬件的精确复制品。由于每台虚拟机都与裸机相同，所以不同的虚拟机上可以运行任何不同的操作系统。图1.5a展示了第一类虚拟机管理程序。
1.5两类虚拟机管理程序在系统中的位置
虚拟机作为用户态的一个进程运行，不允许执行敏感指令。然而，虚拟机上的操作系统认为自己运行在内核态（实际上不是)，称为虚拟内核态.虚拟机中的用户进程认为自己运行在用户态(实际上确实是的)。当虚拟机操作系统执行了一条CPU处于内核态才允许执行的指令时，会陷入虚拟机管理程序。在支持虚拟化的CPU上虚拟机管理程序检查这条指令是由虚拟机中的操作系统执行的还是用户程序执行的。如果是前者，虚拟机管理程序将安排这条指令功能的正确执行。否则，虚拟机管理程序将模拟真实硬件面对用户态执行敏感指令时的行为。
在过去不支持虚拟化的CPU上，真实硬件不会直接执行虚拟机中的敏感指令，这些敏感指令被转为对虚拟机管理程序的调用，由虚拟机管理程序模拟这些指令的功能。
第二类虚拟机管理程序
图1.5b展示了第二类虚拟机管理程序。它是一个依赖于Windows、Linux等操作系统分配和调度资源的程序，很像一个普通的进程。第二类虚拟机管理程序仍伪装成具有CPU和各种设备的完整计算机。VMware Workstation是首个X86平台的第二类虚拟机管理程序。
运行在两类虚拟机管理程序上的操作系统都称作客户操作系统。对于第二类虚拟机管理程序，运行在底层硬件上的操作系统称作宿主操作系统。
首次启动时，第二类虚拟机管理程序像一个刚启动的计算机那样运转，期望找到的驱动器可以是虚拟设备。然后将操作系统安装到虚拟磁盘上（其实只是宿主操作系统中的一个文件）。客户操作系统安装完成后，就能启动并运行了。
虚拟化在Web主机领域很流行。没有虚拟化，服务商只能提供共享托管（不能控制服务器的软件）及独占托管（成本较高）。当服务商提供租用虚拟机时，一台物理服务器就可以运行许多虚拟机，每个虚拟机看起来都是一台完全的服务器，客户可以在虚拟机上安装自己想用的操作系统和软件，但是只需支付较低的费用。这就是市面上常见的“云”主机。
线程的状态与转换
线程的状态与转换
与进程一样，各线程之间也存在着共享资源和相互合作的制约关系，致使线程在运行时也具有间断性。相应地，线程在运行时也具有下面三种基本状态:
执行状态:线程已获得处理机而正在运行。
就绪状态:线程已具备各种执行条件，只需再获得CPU便可立即执行。
阻塞状态:线程在执行中因某事件受阻而处于暂停状态。
线程这三种状态之间的转换和进程状态之间的转换是一样的。
线程库
线程库vs内核级线程的区别
在线程实现方式的介绍中，提到了通过线程库来创建和管理线程。线程库(thread library)是为程序员提供创建和管理线程的API。实现线程库主要的方法有两种:
在用户空间中提供一个没有内核支持的库。这种库的所有代码和数据结构都位于用户空间。这意味着，调用库内的一个函数只是导致了用户空间的一个本地函数的调用。
实现由操作系统直接支持的内核级的一个库。对于这种情况，库内的代码和数据结构位于内核空间。调用库中的一个API函数通常会导致对内核的系统调用。
目前使用的三种主要线程库是:POSIX Pthreads、Window API、Java。Pthreads作为POSIX标准的扩展，可以提供用户级或内核级的库。Window线程库是用于Window操作系统的内核级线程库。Java线程API允许线程在Java程序中直接创建和管理。然而，由于JVM实例通常运行在宿主操作系统之上，Java线程API通常采用宿主系统的线程库来实现，因此在Windows系统中Java线程通常采用Windows API来实现，在类UNIX系统中采用Pthreads,来实现。
线程的组织与控制
线程的组织与控制
(1)线程控制块
与进程类似，系统也为每个线程配置了一个线程控制块TCB，用于记录控制和管理线程的信息。线程控制块通过包括:①线程标识符;②一组寄存器，包括程序计数器、状态寄存器和通用寄存器;③线程运行状态;④优先级;⑤线程专有存储区,线程切换时用于保存现场等;⑥堆栈指针，用于过程调用时保存局部变量及返回地址，等。
同一进程中的所有线程都完全共享进程的地址空间和全局变量。各个线程都可以访问进程地址空间的每个单元，所以一个线程可以读、/写或甚至清除另一个线程的堆栈。
(2）线程的创建
线程也是具有生命期的,它由创建而产生，由调度而执行，由终止而消亡相应的，在操作系统中就有用于创建线程和终止线程的函数（或系统调用）。
用户程序启动时，通常仅有一个称为“初始化线程”的线程在执行，其主要功能是用于创建新线程。在创建新线程时，需要利用一个线程创建函数，并提供相应的参数，如指向线程主程序的入口指针、堆栈的大小√线程优先级等。在线程的创建函数执行完后，将返回一个线程标识符。
(3）线程的终止
当一个线程完成自己的任务后，或是线程在运行中出现异常而须被强制终止时，由终止线程调用相应的函数执行终止操作。但有些线程（主要是系统线程)，它们一旦被建立起来，便一直运行而不会被终止。通常，线程被终止后并不立即释放它所占对资源，只有当进程中其它线程执行了分离函数，被终止线程才与资源分离，此时的资源才能被其他线程利用。
被终止但尚未释放资源的线程仍可被其它线程所调用，以使被终止线程重新恢复运行。
调度器
调度器的调度时机
在操作系统中，用于调度和分派CPU的组件称为调度程序，它通常由三部分组成:
图2.4 调度程序的结构
1）排队器。将系统中的就绪进程按照一定的策略排成一个或多个队列，以便于调度程序选择。每当有进程转变为就绪态时，排队器便将它插入相应的就绪队列。
2）分派器。依据调度程序所选的进程，将其从就绪队列中取出，将CPU分配给新进程。3）上下文切换器。在对处理机进行切换时，会发生两对上下文的切换操作:第一对，将保存当前进程的上下文，而装入分派程序的上下文，以便分派程序运行，—第二对，移出分派程序的上下文，而把新选进程的CPU现场信息装入到处理机的各相应寄存器中。
在上下文切换时，要执行大量load和 store指令，以保存寄存器的内容，花费较多的时间。现在已有硬件实现的方法来减少上下文切换时间。通常采用两组寄存器，其中一组供内核使用，一组供用户使用。这样，上下文切换时，只需改变指针，让其指向当前寄存器组即可。
闲逛进程
闲逛进程
在进程切换时，如果系统中没有就绪进程，就会调度闲逛进程（idle）运行，如果没有其他进程就绪，该进程一直运行，并在执行过程中测试中断。闲逛进程的优先级最低，只要没有就绪进程才会运行闲逛进程，只要有进程就绪就会立即让出处理机。
闲逛进程不需要CPU之外的资源，它不会被阻塞。
内核级线程与用户级线程调度
内核级线程与用户级线程调度的区别
(1)用户级线程
由于内核并不知道线程的存在，所以内核还是和以前一样，选择一个进程，并给予时间控制。由进程中的调度程序决定哪个线程运行。
用户级线程的优点:①线程切换不需要转换到内核空间，节省了模式切换到开销。②调度算法可以是进程专用的，可以根据自身需要选择不同的调度算法。③用户级现场的实现与操作系统平台无关，易于在不同的平台上实现。
用户级线程的缺点:①进程中的一个线程被阻塞，整个进程也会被阻塞，进程内的所有线程都会被阻塞。而在内核级线程方式中，进程中的其它线程仍然可以运行。②内核每次分配给一个进程仅有一个CPU，进程中仅有一个线程能执行，因此，不能发挥多处理器并行处理的优点。在该线程放弃CPU之前，其他线程只能等待。
(2)内核级线程
内核选择一个特定线程运行，通常不用考虑该线程属于哪个进程。对被选择的线程赋予一个时间片，如果超过了时间片，就会强制挂起该线程。
内核级线程的优点:①在多处理器中，内核能同时调度同一进程中的多个线程并行执行。进程中的一个线程被阻塞，内核可以调度该进程中的其它线程运行。③内核本身也可以采用多线程技术，可以提高系统的执行速度和效率。
内核级线程的缺点主要是性能，用户级线程的线程切换仅需少量的机器指令，而内核级线程需要完整的上下文切换、修改内存映像、使高速缓存失效，这导致了若干数量级的延迟。
多级队列调度算法
多级队列调度算法
上下文及其切换机制
最大的开销在地址空间的切换
上下文及其切换机制
上下文及其切换机制即“进程切换”，见王道书2.1.3，P32。
锁
解决临界区最简单的工具就是互斥锁( mutex lock)。一个进程在进入临界区时应获得锁;在退出临界区时释放锁。函数acquire()获得锁，而函数release()释放锁。
每个互斥锁有一个布尔变量available，表示锁是否可用。如果锁是可用的,调用acqiure()会成功，且锁不再可用。当一个进程试图获取不可用的锁时，会被阻塞，直到锁被释放。
图片详情
acquire()或release()的执行必须是原子操作，因此互斥锁通常采用硬件机制来实现。
互斥锁的主要缺点是 $\color{green}{\text{忙等待}}$ ，当有一个进程在临界区中，任何其他进程在进入临界区时必须连续循环调用acquire()。当多个进程共享同一CPU时，就浪费了CPU周期。因此，互斥锁通常用于多处理器系统，一个线程可以在一个处理器上等待，不影响其他线程的执行。
本节后面，将会研究如何使用互斥锁解决经典同步问题。
- 需忙等，进程时间片用完才下处理机，违反“让权等待”
- 优点:等待期间不用切换进程上下文，多处理器系统中，若上锁的时间短，则 $\color{green}{\text{等待代价很低}}$ 常用于多处理器系统，一个核忙等，其他核照常工作，并快速释放临界区
- 不太适用于单处理机系统，忙等的过程中不可能解锁
条件变量
应用于管程中，见王道书2.3.4，P83。
条件变量
信号量和条件变量的对比
锁实现互斥
条件变量实现同步
内存共享
内存共享是指允许多个进程访问内存的同一部分。例如，多个合作进程可能需要访问同一块数据。因此，内存管理必须支持对内存共享区域进行受控访问。
内存共享通过内存映射实现
内存映射文件
内存映射文件的内容
内存映射文件(Memory-Mapped Files）与虚拟内存有些相似，将磁盘文件的全部或部分内容与进程虚拟地址空间的某个区域建立映射关系，便可以直接访问被映射的文件，而不必执行文件IO操作也无需对文件内容进行缓存处理。这种特性非常适合用来管理大尺寸文件。
使用内存映射文件所进行的任何实际交互都是在内存中进行，并以标准的内存地址形式来访问。磁盘的周期性分页是由操作系统在后台隐蔽实现的，对应用程序而言是完全透明的。系统内存中的所有页面由虚拟存储器负责管理，虚拟存储器以统一的方式处理所有磁盘IO。当进程退出或显式地解除文件映射时，所有被改动的页面会被写回到磁盘文件中。
多个进程允许并发地内存映射同一文件，以便允许数据共享。实际上，很多时候，共享内存是通过内存映射来实现的。进程可以通过共享内存来通信，而共享内存是通过映射相同文件到通信进程的虚拟地址空间来实现的。内存映射文件充当通信进程之间的共享内存区域，如图3.1所示。一个进程在共享内存上完成了写操作，此刻当另一个进程在映射到这个文件的虚拟地址空间上执行读操作时，就能立刻看到上一个进程写操作的结果。
图3.1采用内存映射IO的共享内存
虚拟存储器性能的影响因素及改进方式
图片详情
文件元数据
文件元数据就是文件的属性，通常用FCB维护文件元数据。FCB存放在inode表。
元数据和索引节点
目录的操作
王道书P222已介绍了部分目录操作，这里再补充几点。
创建目录。在树形目录结构中，用户可创建自己的用户文件目录，并可再创建子目录。
删除目录。有两种方式:①不删除非空目录，删除时须先删除目录中的所有文件，及递归地删除子目录。②可删除非空目录，目录中的文件和子目录也同时被删除。
移动目录。将文件或子目录在不同的父目录之间移动，文件的路径名也将随之改变。
目录的操作
文件系统的全局结构
本内容翻遍各种教材和黑书都难觅相关内容，待咸鱼学长更新完课程后再补充。
文件系统在内存中的结构
目录和索引节点
虚拟文件系统
普通的文件系统
虚拟文件系统
虚拟文件系统2
vnode/inode的区别
为了给用户进程提供统一的文件系统视图，在用户进程和底层文件系统之间加入了一个抽象层，即虚拟文件系统(VFS)，进程所有的文件操作都通过VFS，由VFS来适配底层各种不同的文件系统，完成实际的文件操作。虚拟文件系统的实现如图4.1所示。
4.1 虚拟文件系统的示意图
VFS是物理文件系统与服务之间的一个接口层，它对每个文件系统的所有细节进行抽象，隐藏了它们的实现细节，使得不同的文件系统在系统中运行的其他进程看来，都是相同的。严格来说，VFS并不是一种实际的文件系统，它只存在于内存中，不存在于任何外存空间。VFS在系统启动时建立，在系统关闭时消亡。
对于用户来说，不需要关心不同文件系统的具体操作过程，而只是对一个虚拟的文件操作界面来进行操作。每一个文件系统之间互不干扰，而只是调用相应的程序来实现其功能。虚拟文件系统作为内核中的一个软件层，用于给用户空间的程序提供文件系统接口，同时也提供了内核中的一个抽象功能，允许不同的文件系统很好的共存。
文件系统挂载
磁盘或分区创建好文件系统后，需要挂载到一个目录才能够使用。
Windows或Mac系统会进行自动挂载，一旦创建好文件系统后会自动挂载到系统，Windows上称之为C盘、D盘等。Linux需要手工进行挂载操作或配置系统进行自动挂载，使用命令mount来挂载文件系统，使用命令umount来卸载已挂载的文件系统。
这部分也没有太多可参考的相关理论内容，大家可以结合王道书P260。
文件系统挂载
输入/输出应用程序接口
输入/输出应用程序接口
输入/输出应用程序接口
网络设备接口
在I/O系统与高层之间的接口中，根据设备类型的不同，又进一步分为若干个接口。
(1）字符设备接口
字符设备是指数据的存取和传输是以字符为单位的设备，如键盘、打印机等。基本特征是传输速率较低、不可寻址，并且在输入/输出时常采用中断驱动方式。
get和 put操作。由于字符设备不可寻址，只能采取顺序存取方式，通常为字符设备建立一个字符缓冲区，用户程序通过get操作从缓冲区获取字符，通过 put操作输出字符到缓冲区。
in-control指令。字符设备类型繁多，差异甚大，因此在接口中提供一种通用的in-control指令来处理它们（包含了许多参数，每个参数表示一个与具体设备相关的特定功能）。
字符设备都属于独占设备，为此接口中还须提供打开和关闭操作，以实现互斥共享。
(2)块设备接口
块设备是指数据的存取和传输是以数据块为单位的设备，典型的块设备是磁盘。基本特征是传输速率较高、可寻址。磁盘设备的I/O常采用DMA方式。
隐藏了磁盘的二维结构。在二维结构中，每个扇区的地址需要用磁道号和扇区号来表示。块设备接口将磁盘的所有扇区从0到n-1依次编号，这样，就将二维结构变为一种线性序列。
将抽象命令映射为低层操作。块设备接口支持上层发来的对文件或设备的打开、读、写和关闭等抽象命令，该接口将上述命令映射为设备能识别打较低层具体操作。
内存映射接口提供通过内存的字节数组来访问磁盘，而不提供读和写操作。映射文件到内存的系统调用返回包含文件副本的一个虚拟内存地址。只有需要访问内存映像时，才会由虚拟存储器实际调页。内存映射文件的访问如同内存读写一样简单，极大的方便了程序员。
(3）网络设备接口
现代操作系统都提供了面向网络的功能，因此也须提供相应的网络软件和网络通信接口，使计算机能通过网络与网络上的其它计算机进行通信或上网浏览。
许多操作系统提供的网络IO接口为网络套接字接口，套接字接口的系统调用使应用程序创建的本地套接字，连接到远程应用程序创建的套接字，通过此连接发送和接收数据。
(4）阻塞/非阻塞I/O
操作系统的IO接口还涉及两种模式:阻塞和非阻塞。
阻塞I/O是指当用户进程调用IO操作时，进程就被阻塞，需要等待I/O操作完成，进程才被唤醒继续执行。非阻塞IO是指用户进程调用I/O操作时，不阻塞该进程，该IO调用返回一个错误返回值，通常，进程需要通过轮询的方式来查询I/O操作是否完成。
大多数操作系统提供的1/O接口都是采用阻塞I/O。
图片详情
设备驱动程序接口
如果每个设备驱动程序与操作系统的接口都不同，那每次出现一个新设备时，都必须为此修改操作系统。因此，要求每个设备驱动程序与操作系统之间都有着相同,或相近的接口。这样会使添加一个新的设备驱动程序变得很容易，同时也方便开发人员编制设备驱动程序。
对于每一种设备类型，例如磁盘，操作系统定义一组驱动程序必须支持的函数。对磁盘而言，这些函数自然包含读、写、格式化等。驱动程序中通常包含一张表格，这张表格具有针对这些函数指向驱动程序自身的指针。当驱动程序装载时，操作系统记录下这张函数指针表的地址，所以当操作系统需要调用一个函数时，它可以通过这张表格发出间接调用。这张函数指针表定义了驱动程序与操作系统其余部分之间的接口。给定类型的所有设备都必须服从这一要求。
与设备无关的软件还要负责把符号化的设备名映射到适当的驱动程序上。例如，在UNIX中，设备名/devdisk0唯一确定了一个特殊文件的i节点，这个i节点包含了主设备号(用于定位相应的驱动程序）和次设备号人用来确定要读写的具体设备）。
在UNIX和 Windows中，设备使作为命名对象出现在文件系统中的，因此针对文件的常规保护规则也适用于IO设备。系统管理员可以为每一个设备设置适当的访问权限
设备驱动程序接口
图片详情
固态硬盘
见计组
csapp的例题
计算机网络
VLAN基本概念与基本原理
VLAN产生的历史原因
VLAN基本概念
基于端口的实现方式
基于mac地址的实现
交换机之间贴标签
IEEE 802.1Q
例题
一个以太网是一个广播域，当一个以太网包含的计算机太多时，往往会导致:
- 以太网中出现大量的广播帧，特别是经常使用的ARP和 DHCP协议（第4章)。
- 一个单位的不同部门共享一个局域网，对信息保密和安全不利。
通过虚拟局域网(Virtual LAN)，可以把一个较大的局域网，分割成一些较小的逻辑上的VLAN，而每个VLAN是一个较小的广播域。
802.3ac标准定义了支持VLAN的以太网帧格式的扩展。它在以太网帧中插入一个4字节的标识符（插入在源地址字段和类型字段之间)，称为VLAN标签，用来指明发送该帧的计算机属于哪个虚拟局域网。插入VLAN标签的帧称为802.1Q帧，如图3.1所示。由于VLAN帧的首部增加了4个字节，因此以太网的最大帧长从原来的1518字节，变为1522字节。
图3.1 插入VLAN标签后变成了802.1Q帧
VLAN标签的前2个字节置为0x8100，表示这是一个802.1Q帧。VLAN标签的后两个字节中,前4位没有用,后12位是该VLAN的标识符VID,它唯一标志了该802.1Q帧属于哪个VLAN。12位的VID可识别4096个不同的LAN。插入VID后，802.1Q帧的FCS必须重新计算。
如图3.2所示，交换机1连接了7台计算机，该局域网划分为两个虚拟局域网VLAN-10和VLAN-20，这里的10和20就是802.1Q帧中的VID字段的值，由交换机管理员设定。各主机并不知道自己的VID值（但交换机必须知道)，主机与交换机之间交互的都是标准以太网帧。一个VLAN的范围可以跨越不同的交换机，前提是所使用的交换机能够识别和处理VLAN。交换机2连接了5台计算机，并与交换机1相连。交换机2中的2台计算机加入到VLAN-10，另外3台加入到VLAN-20。这两个VLAN虽然都跨越了两个交换机，但都各自是一个广播域。
图3.2 利用以太网交换机构成虚拟局域网
假定A向B发送帧，交换机1根据帧首部的目的MAC地址，识别B属于本交换机管理的VLAN-10，因此就像帧普通以太网中那样直接转发帧。假定A向E发送帧，交换机1必须把帧转发到交换机2，但在转发前，要插入VLAN标签，否则交换机2不知道应把帧转发给哪个VLAN。因此在交换机端口之间的链接上传送的帧是802.1Q帧。交换机2在向E转发帧之前，要拿走已插入的VLAN标签，因此E收到的帧是A发送的标准以太网帧，而不是802.1Q帧。如果A向C发送帧，那么情况就复杂了，因为这是在不同网络之间的通信，虽然A和C都连接在同一个交换机，但它们已处在不同的网络（VLAN-10和 VLAN-20）中，需要通过上层的路由器来解决，也可以在交换机中嵌入专用芯片来进行转发，这样就在交换机中实现了第3层的转发功能。
虚拟局域网只是局域网给用户提供的一种服务，并不是一种新型局域网。
SDN基本概念
网络层的主要任务是转发和路由选择。可以把网络层抽象地划分为数据层面(也称转发层面)和控制层面，转发是数据层面实现的功能，而路由选择是控制层面实现的功能。
软件定义网络（SDN)是一种创新的网络架构，它通过集中式的控制层面和分布式的数据层面，两个层面相互分离，控制层面利用控制―数据接口对数据层面上的路由器进行集中式控制，方便软件来控制网络。在传统互联网中，每个路由器既有转发表又有路由选择软件，也就是说既有数据层面也有控制层面。但在图4.1所示的SDN结构中,路由器都变得简单了，它的路由选择软件都不需要了，因此路由器之间不再相互交换路由信息。在网络的控制层面有一个逻辑上的远程控制器（可以由多个服务器组成)。远程控制器掌握各主机和整个网络的状态，为每个分组计算出最佳路由，通过Openflow协议（也可以通过其他途径）将转发表下发给路由器。路由器的工作很单纯，即收到分组、查找转发表、转发分组。
图片详情
数据平面
传统控制平面
sdn控制平面
图片详情
sdn控制平面
sdn的三层结构
例题
总结
