编程技术分享

# 软件设计师

# P1 软件设计师考试介绍

考试形式：

  • 计算机与软件工程知识，150分钟，笔试，选择题。
  • 软件设计，150分钟，笔试，问答题。

历年考试知识点：

历年考试知识点

历年考试软件设计题型：

历年考试软件设计题型

# P2 计算机组成与体系结构

课程内容提要 (6分)：

  • 数据的表示。
    • 涉及到数据进制的转换，计算机中使用二进制数据，但是在日常生活习惯使用十进制。
    • 为了计算的方便，提出了八进制，十六进制等，这些进制在计算某些问题的时候有可能用到。比如如在存储体系这一块有计算用多少块芯片组成多大的存储空间；网络部分计算IP地址，子网掩码等。
  • 计算机结构。
    • 涉及的内容比较多，但真正考察的比较多的是CPU中寄存器划分的问题。
    • 哪些寄存器是放在运算器中，哪些寄存器是属于控制器，这些要区分得清楚。
    • 对于常见的寄存器，我们还要了解它的基本特性是什么？它是做什么用的。
  • Flynn分类法。
    • 计算机的分类方法，把计算机分成4大类别，实际应用过程中并没有区分哪么严格，有些类别只是在理论层面的东西。
  • CISC和RISC。
    • 计算机的指令集，这两种指令集的特点需要区分开。
  • 流水线技术。
    • 主要是考察一些计算方面的问题。
  • 存储系统。
    • 即有概念也有计算方面的问题需要了解和掌握。
  • 总线系统。
    • 了解最基础的总线的分类和概念。
  • 可靠性。
    • 串联，并联，串并混合的情况。
  • 校验码。
    • 校验码的作用。
    • 常见的校验码有哪些。
    • CRC校验码，海明校验码各自的特点，编码解码过程。

# P3 数据的表示(进制的转换)

  • 数据的表示

    • 任何进制转换成十进制，都是使用按权展开法进行处理。
    • R进制转十进制使用按权展开法，其具体操作方式为：将R进制数的每一位数值用Rk形式表示，即幂的底数为R,指数为k,k与该位和小数点之间的距离有关，当该位位于小数点左边，k值是该位和小数点之间数码的个数，而当该位位于小数点右边，k值是负值，其绝对值是该位和小数点之间数码的个数加1。
    • 例如二进制 10100.01=1 * 24 + 1 * 22 + 1 * 2-2
    • 例如七进制 604.01=6 * 72 + 4 * 70 + 1 * 7-2
    • 十进制转R进制使用短除法，例如将94转换成二进制数为：
    2|94 余 0
2|47 余 1
2|23 余 1
2|11 余 1
2|5  余 1
2|2  余 0
2|1  余 1
  0
从下往上面开始读取余数值，所以最后的结果是 1011110
    1
    2
    3
    4
    5
    6
    7
    8
    9

  • 二进制转八进制与十六进制。

    • 在计算机上面要用到的是二进制，但我们在计算过程中使用二进制就比较繁杂，二进制数比较长，十进制只有4位数时，二进制多达十多位，不太好计算，操作起来不太好操作。
    • 二进制与八进制、十六进制之间有严整的对应关系。
    • 每三个二进制位可以对应一个八进制位，从右到左每三个二进制位三位三位的分段，然后再把每一个段转成八进制。
    • 每四个二进制位对应一个埂十六进制位，从右到左每四个二进制位四位四位的分段，然后再把每一个段转成十六进制位。

    如将上面的94对应的二进制1011110转成八进制和十六进制：

    十进制 94
二进制 1011110

转成八进制
分段 1 011 110
转换 1   3   6
即：94 = 1*8*8 + 3*8 + 6
八进制为 136

转成十六进制
分段 101 1110
转换   5    e
即： 94 = 5*16 + e = 80 + 14
十六进制中，0，1，2，3，4，5，6，7，8，9，10(a)，11(b)，12(c)，13(d)，14(e)，15(f)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14

你可以在 https://tool.lu/hexconvert/ (opens new window) 页面验证你的进制转换。

# P4 数据的表示(原码反码补码移码)

  • 各种数值在计算机中表示的形式称为机器数。
  • 移码主要是为了在数轴上面将负数显示在下方正数显示在上方。
  • 原码、反码、补码和移码
    • 正数： 原码 = 反码 = 补码，移码 = 补码符号位取反
    • 负数：反码 = 原码符号位不变，其他位取反；补码 = 反码 + 1；移码 = 补码符号位取反
数值1 数值-1 1-1
原码 0000 0001 1000 0001 1000 0010
反码 0000 0001 1111 1110 1111 1111
补码 0000 0001 1111 1111 0000 0000
移码 1000 0001 0111 1111 1000 000
  • 取值范围
    • n为机器字长，如n=8
    • 原码 ： -(2n-1 - 1) ~ (2n-1 - 1) ，如n=8，则范围为-127~127
    • 反码 ： -(2n-1 - 1) ~ (2n-1 - 1) ，如n=8，则范围为-127~127
    • 补码 ： -2n-1 ~ (2n-1 - 1) ，如n=8，则范围为-128~127
    • 移码 ： -2n-1 ~ (2n-1 - 1) ，如n=8，则范围为-128~127

# P5 数据的表示(浮点数运算)

  • 浮点数表示 N = M * Re
  • 其中，M称为尾数，e是指数，R为基数。
  • 操作时，先要对阶，再进行尾数计算，最后再进行结果格式化。

# P6 CPU结构(运算器和控制器的组成)

  • CPU是中央处理单元，是计算机的核心部件，它负责获取程序指令、对指令进行译码并加以执行。
  • 主机是计算机的核心部分，整个计算机的组成就是主机+外设。主机并不是平常所说的主机箱里面的部件呢，不是这么回事。
  • 计算机结构里面所说的主机比主机箱里面的部件要少。
  • 主机只包括两个部分：CPU和主存储器（也就是内存）。
  • 像硬盘、显卡、声卡等归为外设。只有CPU和内存属于主机的！
  • CPU中包含运算器和控制器。
  • 运算器和控制器的构成是经常考到的一个知识点。
  • 运算器主要功能有：执行所有的算术运算；执行所有的逻辑运算并进行逻辑测试。
  • 运算器主要部件有算术逻辑单元ALU（实现对数据的算术和逻辑运算），累加寄存器AC(通用寄存器，不仅仅只做加法运算，减法运行也会用到这个寄存器)，数据缓冲寄存器DR(对内存储器进行读写操作时，用来暂存数据), 状态条件寄存器PSW（这个寄存器非常有特色，经常被考到，用来存在运算标志、标志位、状态等信息的，主要分为状态标志和控制标志）。
  • 控制器主要部件有指令寄存器IR，程序计数器PC(程序运行当前指令时需要了解下一条指令在什么位置，这个就是由程序计数器来完成)，指令译码器ID，时序部件。

# P7 Flynn分类法简介

  • Flynn分类是一种计算机体系结构分类方法。
  • Flynn分类依据是两个指标：指令流、数据流。
  • 指令流、数据流都可以分为两种类型，单和多。如单指令流、单数据流、多指令流、多数据流。实际上是按穷举的方式进行分类。
  • 分类就会分成4种：单指令流单数据流，单指令流多数据流，多指令流单数据流，多指令流多数据流。
  • 单指令流单数据流（Single Instruction stream Single Data stream, SISD）。
  • 单指令流多数据流（Single Instruction stream Multiple Data stream, SIMD）。
  • 多指令流单数据流（Multiple Instruction stream Single Data stream, MISD）。
  • 多指令流多数据流（Multiple Instruction stream Multiple Data stream, MIMD）。
体系结构类型 结构 关键特性 代表
单指令流单数据流 SISD 控制部分：一个；处理器：一个；主存模块：一个 单处理器系统，在PC/服务器领域已经看不到了，在单片机系统上面仍然存在，并且比较多见
单指令流多数据流 SIMD 控制部分：一个；处理器：多个；主存模块：多个 各处理器以异步的形式执行同一条指令（每个运算部件的输入可能不一样） 并行处理机，主要应用在阵列处理机，超级向量处理机。阵列处理机适合去处理数组相关的计算
多指令流单数据流MISD 控制部分：多个；处理器：一个；主存模块：多个 被证明是不可能，至少是不实际，是理论上面的模型 目前没有，有文献称流水线计算机为此类
多指令流多数据流MIMD 控制部分：多个；处理器：多个；主存模块：多个 能够实现作业、任务、指令等各级全面并行 目前来说最见的。多处理机系统，多计算机

# P8 CISC和RISC

  • CISC - Complex Instruction Set Computer 复杂指令集计算机。
  • RISC - Reduced Instruction Set Computer 精简指令集计算机。
指令系统类型 指令 寻址方式 实现方式 其他
复杂指令集计算机 CISC 数量多，使用频率差别大，可变长格式 支持多种 微程序控制技术(微码) 研制周期长，成本高，出错几率大
精简指令集计算机 RISC 数量少，使用频率接近，定长格式，大部分为单周期指令，操作寄存器，只有Load/Store操作内存 支持方式少 增加了通用寄存器，硬布线逻辑控制为主，适合采用流水线 优化编译，有效支持高级语言
  • 如何理解CISC和RISC：
    • CISC是以前比较常用的指令集，是在计算机没有大规模使用前提出来的，在这个时候计算机是奢侈品，比如一个机构需要一台计算机，这个时候需要找到厂商为我们定制一台计算机，这台计算机从硬件到指令系统都是定制的，比如这台计算机需要用来处理天气预报信息，需要根据运算能力来设计这台计算机，这台计算机不是我们看到的笔记本或台式机那么大，而是一间房子那么大，很多元器件组起来的，然后你要进行什么样的业务处理，就给你设计哪些指令，然后再在指令基础上来编程去完成业务，这还是很多年前的事情。有这样的历史背景和环境之后，我们就可以知道CISC为什么是复杂指令集，是因为这种指令系统根据不同的用户，会做不同的指令，而且指令非常多，数量多。
    • 在计算机的发展过程中，原来基本都是各个单位的专用设备，后来计算机成为通用设备，每个计算机买回去，安装上软件就希望能够直接跑。因此需要考虑精简计算机的指令系统，希望它适应能力更强一些，而且需要做优化。我们开始把繁杂的指令系统开始简化，简化到最基本的操作，然后复杂的操作都用基本的操作来替代，比如乘法指令比较复杂，我们将乘法指令移除掉，而是将乘法看成多个加法指令的累加这样的形式来完成，这样一来大大的降低了整个系统的指令数量，所以叫精简指令集。
    • 所以再来看表中的内容，指令数量毫无疑问是复杂指令集CISC的多一些，复杂指令集中有很多的指令，有些指令可能需要频繁使用到，如简单指令，而复杂指令使用频率不见得高，这就是需要将复杂指令排除掉的原因，因此使用频率差别大；一般使用可变长度的指令，这是指令在系统上面会有二进制编码，编码长度可以不同，而在精简指令集中，指令数量少，使用频率也差不多，就用定长格式，所有的指令长度是一样的，精简指令集为了提高效率，引入了寄存器，绝大部分操作都是针对寄存器进行的，寄存器速度极快，效率极高，寄存器只用Load(读取)/Store(存入)操作内存，其他的都读取寄存器，所以得到了比较高的效率。
    • RISC大大超越CISC，RiSC是主流。

# P9 流水线的基本概念

  • 流水线概念

    • 流水线是指在程序执行时多条指令重叠进行操作的一种准并行处理实现技术。各种部件同时处理是针对不同指令而言的，它们可同时为多条指令的不同部分进行工作，以提高各部件的利用率和指令的平均执行速度。
    • 指令的执行步骤： 取指 --> 分析 --> 执行 -->
    • 指令的控制方式有顺序方式、重叠方式和流水方式3种。
    • 顺序方式是指各条机器指令之间顺序串行地执行，执行完一条指令后才取下一条指令，而且每条机器指令内部的各个微操作也是顺序串行地执行。这种方式的优点是控制简单，缺点是速度慢，机器各部件利用率低。
    • 重叠方式是指解释第K条指令的操作完成之前就可以开始解释第K+1条指令。通常采用的是一次重叠，即在任何时候，指令分析部件和指令执行部件都只有相邻两条指令在重叠解释。这种方式的优点是速度有所提高，控制也不复杂，缺点是会出现冲突、转移和相关等问题。
    • 流水方式是模仿工业生产过程的流水线（如汽车装配线）而提出的一种指令控制方式。

流水线

左边图是没有使用流水线执行指令情况，右边是使用流水线执行指令情况。

左边顺序执行在取指后、分析指令、再执行指令。这三个步骤是由不同部件来完成的，可以看出有大量部件是处于空隙状态的（如图中的空白位置），可以看到顺序执行时间只使用了少量的时间片，而大量的时间片被空隙浪费了。

而右边的流水线执行指令情况下，取出第1条指令后，该部件马上去对第2条指令进行取指，这样这个部件的时间就没有浪费；而分析指令部件在分析完第1条指令后马上就分析第2条指令，时间片也没有浪费；执行部件在执行完第1条指令后马上执行第2条指令，时间片也没有浪费。即不需要第1条执行执行完成才进行第2条指令的取指工作。

这就好比在工业领域第一次应用流水线技术，福特工司在没有利用流水线技术时，组装环节，分班组进行组装，一个班组把一辆汽车🚙组装完成后，再立即进行另一辆车的组装，看似没有时间空隙，但实际上在组装一台车的过程中有大量的工人在处于休息状态（空隙），如有些人只装配发动机、有些人只装配轮胎，我们知道不可能所有人同一时间一拥而上一起来组装车辆，而是在车架上面先装发动机，再装变速箱，再装外壳，再装玻璃之类的，这个过程一开始装发动机的人在忙活，装玻璃的人在休息，装变速箱的人忙活的时候装玻璃的人仍然在休息，。。。，安装玻璃的人忙活的时候其他的工人却在休息，这样可以看到大量的工人处于休息状态，造成大量人工的浪费。

福特指出利用流水线技术，由流水线的传送带把车传送过来，每个工人只负责他们需要做的一小部分工作，比如说工人需要把轮胎放在轴上，车辆到达工人面前，他只需要把轮胎放在轴上，不需要管别的，传送带将车辆传到下一个环节，下一个环节的工人再进行轮胎螺丝的安装，因此针对安装轮胎的这个工人，他只需要在有车辆过来，并将轮胎放在轴上即可，然后接着给下一辆车将轮胎放在轴上，这样看工人的时间被充分利用了，浪费的人工时间比较少，工作效率大大提高了！

流水线不仅仅只应用于计算机相应领域，也用在工业领域!

# P10 流水线周期及流水线执行时间计算

  • 流水线周期是指(取指、分析和执行操作中)执行时间最长的一段。如取指2ns，分析2ns，执行1ns，则周期是2ns。即指令执行过程中的几个步骤(如取指阶段、分析阶段、执行阶段)中最耗时的阶段。
  • 流水线计算公式为：
    • 1条指令执行时间 + (指令条数-1)* 流水线周期
    • 理论公式：(t1 + t2 + t3 + ... + tk) + (n -1) * Δt
    • 实践公式： (k + n -1) * Δt ， 其中k是分几段

因为不工整的时间片导致后面计算带来不便，可以将每个阶段看成执行时长都是一个周期，这样所有阶段的执行时间都是一个周期，这时看实践公式计算就方便一些。

流水线执行过程：

例题：

由于取指2ns，分析2ns，执行1ns，那么周期按最长的一段计算，最长的一段是取指或分析，都是2ns，因此周期Δt是2ns。

那么100条指令执行时间：

理论公式：(2 + 2 + 1) + (100 -1) * 2 = 5 + 200 -2 = 203 ns

实践公式： (3 + 100 -1) * 2 = 204ns

考试中两种方式的可能性都有，首先使用理论公式，如果理论公式没有正确答案则使用实践公式。

# P11 流水线吞吐率计算

  • 流水线吞吐率概念

  • 流水线的吞吐率(Though Put rate, TP)是指在单位时间内流水线所完成的任务数量或输出的结果数量。

  • TP = 指令条数 / 流水线执行时间

  • 流水线最大吞吐率：

我们经常听到某港口的年吞吐率指一年内进出港口的货物情况数量。

我们来计算P10中示例的吞吐率为例。

TP = 指令条数100 / 流水线执行时间 203ns

TPmax = 1 / Δt = 1 / 2ns

# P12 流水线的加速比

  • 流水线的加速比是指完成同样的一批任务，不使用流水线所用的时间与使用流水线所使用的时间之比。
  • 流水线加速比 S = 不使用流水线执行时间 / 使用流水线执行时间 。

我们看一下，P10中的示例，来计算一下加速比。

不使用流水线需要的时间 = （取指2ns + 分析2ns + 执行1ns） * 100条指令 = 500 ns

使用流水线需要的时间 = (2 + 2 + 1) + (100 -1) * 2 = 5 + 200 -2 = 203 ns

因此流水线的加速比 = 500ns / 203ns = 2.46

$ echo 'scale=2;500/203'|bc
2.46
1
2

加速比越高说明使用流水线的效果越明显！

  • 流水线的效率： 流水线的效率是指流水线的设备利用率。在时间图中，流水的线的效率定义为n个任务占用的时空区与k个流水段总的时间区之比。

如上面这个图中，S1、S2、S3前三个阶段都是Δt ，S4阶段是3Δt。

此时流水线执行完4个任务所用的时间 = （1 + 1 + 1 + 3）* Δt * 4 = 20 Δt

而此时总的时间片时间 = 15 Δt * 4 = 60 Δt

此时可以看到流水线的效率 = 24Δt / 60Δt = 40%

流水线效率其实是衡量在整个在时间片的空间上面，有多少空间被我们的流水线所利用。提出这个值的含义、价值在于提醒我们，如何去设置流水线来让流水线效率更高。

上面的示例可以看到，有一个阶段S4耗时比较长，其他阶段时间都差不多，这个流水线的效率比较低。

流水线如果各个阶段之间的时间都差不多，就像前面P10中各个阶段的时间差不多，效率相对来说比较高。

# P13 计算机层次化存储结构

  • 在存储这一块我们主要要了解以下几方面内容：
    • 存储的整体结构
    • cache相关知识
    • 内存相关知识
  • 层次化存储结构， 我们需要了解到：
    • 基本的存储结构是如何划分的？
    • 哪些存储器性能比较好，哪些存储器容量比较大？
    • 为什么要以这种层次化来组织存储结构？

  • 在整个存储结构中，性能最高速度最快的是寄存器，存在于CPU内。

  • Cache是高速缓存存储器

    • Cache不是必须的，拿走Cache的话，也可以，内存也可以与CPU交互，但是这时候速度会很慢，速度可能慢上100百，Cache单位级别是KB、MB等。
    • Cache相对于内存来说，容量极小，但是加了Cache后，速度提升了十倍百倍，速度提升非常大，为什么会这样？之所以会这样，是因为存在局部性原理，因为程序在执行某条指令后，还有可能再次执行该条指令，频繁不断的执行相同块里面的内容，这称之为时间局部性，比方循环语句结构就具备这种特点，如循环体执行100 0000次，循环体执行一百万次，循环体之上和之下的语句（如初始化语句和输出语句）往往只执行一次，如果将循环体语句调入到cache中，CPU只需要与cache交互，不需要与内存进行交互，这样就大大提升了效率，速度。
    • 内存与外存之间也有类似的情况，外存里面的数据会先调入到内存。需要运行的程序数据都会先从外存调入到内存。
    • Cache是按内容存取。存信息时考虑信息的内容，不同内容存储到不同的块中，按内容存取的存储器又叫做相联存储器，它的速度和效率远高于按地址存取存储器。
    • 引入Cache的目的是提高速度的同时，不增加太多的成本，是性价比方案。

  • 内存，也称为主存，容量小，速度快，单位级别是GB,如1G/2G/4G/8G/16GB等。

  • 外存，也称为辅存，硬盘、光盘、U盘等。

# P14 Cache的基本概念

  • Cache是高速缓存。
  • Cache高速缓存用来存放当前最活跃的程序和数据，其特点是：位于CPU与主存之间；容量在几千KB和几MB之间；速度一般比主存快5-10倍，由快速半导体存储器构成；其内容是主存局部域的副本，对程序员来说是透明的。
  • Cache的功能是提高CPU数据输入输出的速率，突破冯.诺依曼瓶颈，即CPU与存储系统间数据传送带宽限制。
  • 在计算机的存储系统体系中，Cache是(除寄存器之外)访问速度最快的层次。
  • 由于寄存器容量极小，速度极快，并且集成在CPU当中，平时并没有把它当做最顶级的存储器来看待。如果问存储器速度最快的是哪一个？有寄存器的话，选寄存器，没有寄存器话，则选Cache是速度最快的。
  • 使用Cache改善系统性能的依据是程序的局部性原理。
  • Cache设计的目标是在成本允许的条件下达到较高的命中率。

# 使用Cache+主存存储器的系统的平均周期的计算

使用高速缓存Cache时，CPU首先会在Cache中查找需要的数据，如果找到，则说明命中；如果找不到，则会去内存（主存）中去查找数据，这时称为未命中。

所以可以计算使用高级缓存+主存的平均周期时间：

Tcache+主存 = h * Tcache + (1 - h ) * T主存

如果 Cache访问命中率h为95%的话，Cache的周期时间(或存取时间)为1ns，主存的周期时间(或存取时间)为1000ns的话，则此时的使用高级缓存+主存的平均周期时间计算如下：

Tcache+主存 = h * Tcache + (1 - h ) * T主存 = 95% * 1ns + (1- 95%) * 1000ns = 0.95 ns + 50 ns = 50.95 ns

没有引入Cache时，需要1000ns，引入Cache后只需要50.95ns，这时可以看到引入Cache后，速度提升差不多达20倍(19.62倍)。

$ echo 'scale=2;1000/50.95'|bc
19.62
1
2

# P15 时间局部性和空间局部性

局部性原理：

  • 时间局部性
  • 空间局部性
  • 工作集理论：工作集是进程运行时被频繁访问的页面集合。

局部性原理到底是怎么一回事，计算机在处理相关的数据和程序的时候，一般都会有在某一个时段集中的去访问某些指令，或在某一个时段集中去读取某些空间的数据，这样的特性，之所以要把这种特性拿出来研究，它对于我们采用多级存储体系，来解决存储的量和速度之间的矛盾的解决方案。我们之前也讲了，速度快的，成本太高，代价太大，所以只能做小容量，而成本便宜的速度又上不去，所以有了局部性原理，我们将它们组合起来，得到最高的性价比。

#include <stdio.h>

int main(int argc, const char * argv[]) {
    int i,j,s = 0;
    for(i=1; i<1000; i++)
        for(j=1; j<1000; j++)
            s += j;
    printf("结果为:%d\n", s);
    return 0;
}
1
2
3
4
5
6
7
8
9
10

如上面的c代码，第4行初始化语句只执行一次，中间的两个for循环语句，使得里面的s += j;将会执行100 0000次，这一百万次都不需要从内存里面调数据，只需要从Cache中读取数据，这就是时间局部性。

  • 空间局部性是指一旦程序访问了某个存储单元，则不久之后，其附近的存储单元也将被访问。

如对数组进行处理的时候，当程序访问数组A[0]时，马上又访问附近的数据A[1]，A[2]等等。

  • 工作集原理就是将被频繁访问的页面集合打包起来，频繁访问可以一起调用进来，短时间不会被替换掉，以此来提高效率。

# P16 随机存储器和只读存储器

主存的分类：

  • 随机存取存储器: Random Access Memory, RAM,即能读取数据也能存入数据的存储器，内存就是随机存取存储器，内存一断断电，内存中所有数据都不会保存下来。
  • 只读存储器：Read Only Memory, ROM，断电后只读存储器数据仍然会保存下来。
    • ROM， 固定只读存储器，内容只能读出，不能改变。一般用于存放系统程序BIOS和用于微程序控制。
    • PROM 可编程的只读存储器 Programmable Read Only Memory, 其中的内容可由用户一次性地写入，写入后不能再修改。
    • EPROM 可擦除(Erasable)可编程的只读存储器。
    • EEPROM 电擦除可编程的只读存储器。
    • Flash Memory, 闪存。
  • 主存-编码

地址单元计算过程：

  • 地址单元数 = 大的地址 - 小的地址 + 1
  • 内存地址中最后的H表示16进制，H不参与计算。

所以示例中地址单元数 = C7FFF - AC000 + 1 = C7FFF + 1 - AC000 = C8000 - AC000 = 1C000

   C8000
-  AC000
---------
=  1C000

注意：
16进制中 A代表10，B代表11，C代表12
1
2
3
4
5
6
7

1C000 = 1* 164 + 12 * 163 = 1 * pow(2, 44) + 12 * pow(2, 43) = pow(2, 6 + 10) + 12 * pow(2, 2+10)

​ = pow(2, 6) * pow(2, 10) + 12 * pow(2, 2) * pow(2, 10)

​ = (64 + 48) * pow(2, 10)

​ = 112 * pow(2, 10)

​ = 112 * 210

所以总共有 112 * 210 字节 个地址单元

转换成KB的话，1kb = 210 b

所以共用112 K个地址单元。

所有的内存地址总的存储容量 = 112K * 16bit

设芯片每个存储单元存储X位，则28片存储芯片的总容量 = 28 * 16K * X

上面的两个值应该相等，即 112K * 16 bit = 28 * 16K * X

所以X = 112K * 16bit / (28 * 16K) = 4 bit

因此，示例中第1题选B， 第2题选A。

注意 8bit = 1b (字节)。

# P17 磁盘工作原理

  • 磁盘结构与参数

  • 磁盘基本动作的原理，即我们要知道在读取一次数据的过程中，磁盘需要做哪些动作，需要消耗哪些方面的时间，这个是我们需要掌握的。

  • 磁盘是用环线的盘片，上面涂上特殊的材质来保存数据，盘面用来保存数据，读取数据需要专业的设备，就是磁头。

  • 像多碟的磁盘，会有多张盘在里面，每个盘面都会存储一定的信息，要读取信息，磁头先要移动到相应的磁道上，存信息是存在磁道上面。

  • 读信息时，首先要将磁头定位到目标的磁道上面，这个动作需要一定的时间，这个时间称为寻道时间。

  • 旋转延迟时间，又称为等待时间，在一个磁道上面，会分很多扇区，我们存储的数据就在扇区上面，我们需要旋转磁盘，将数据转到磁头下面，这时就可以读取到数据。旋转延迟时间是磁盘转一圈的时间。

  • 最好的情况是直接读取数据，最差的情况是磁盘需要几乎转一圈，所以平均的旋转延迟时间是磁盘转一圈的时间。

  • 教材中介绍：

    • 为了正确正确地存储信息，将盘片划分成许多同心圆，称为磁道，从外向里编号，最外一圈为0道。
      • 沿径向的单位距离的磁道道称为道密度。
      • 将一个磁道沿圆周等分为若干段，每段称为一个扇段或扇区，每个扇区内可以存放一个固定长度的数据块，如512B。 - 磁道上单位距离可记录的位数称为位密度。 - 因为每条磁道上的扇区数相同，而每个扇区的大小又一样，所以每条磁道都记录同样多的信息。又因为里圈磁道圆周比外圈磁道的圆周小，所以里圈磁道的位密度要比外圈磁道的位密度高。最内圈的位密度称为最大位密度。

简单理解的话，磁盘上面每个磁道上面的存储的数据一样多，虽然里面磁道周长小一些，但里面的磁道与外面的磁盘存储的数据量是一致的，因此这时候里面的位密度就要高一些。

考试示例：

题止目中所说的物理块就是扇区！

绘制一个圆环读取，依次将11个逻辑记录放在圆环上面。

因为磁盘的旋转周期是33ms，而用11个逻辑记录，因此读取一个逻辑记录需要 33ms / 11 = 3 ms。

这也就意味着我们读取一个记录需要消耗3ms。

因为现在磁头在R0的开头的位置，我们此时可以直接读取R0的数据，需要3ms，如果对R0进行处理，也需要3ms。

因为系统使用单缓存区顺序处理这些记录，如果不是单缓存区的话，会存在什么区别？如果是多缓存区的话，我们可以将数据依次读取出来都放在缓存区里面，现在因为是单缓存区，如果我们读取到R0放在缓存区后，这个时候不能不能读取R1数据放在缓存区的，原因是我们对R0进行处理的时候需要3ms时间，必须等到R0处理完成后才能再处理下一个数据。

但是，特别重要的一点是，在处理R0数据的时候，磁盘并没有停下面，还在匀速的转动，这个时候当R0数据处理完成后，磁头已经不在R1的开头位置，而是R2的开头位置。

如果要在处理R0后，马上处理R1，则当前磁头需要旋转1圏再加1个逻辑记录，也就是需要使用的时间是 33ms + 3ms ,也就是从开始处理，到处理R0完成后，并将磁头旋转到R1开始的位置，则需要 36ms。

处理R1，R2, ...， R9,这些逻辑记录，也都需要36ms。

最后的R10，因为后面再没有其他的逻辑记录需要处理，因此磁头只需要读取到R10逻辑记录即可，这时需要3ms， 再在缓存区的处理需要3ms，也就是处理R10需要6ms。

因此，总的处理时间 = 36ms * 10 + 6ms = 366ms。

求最小时间，因为我们可以修改逻辑记录的布局。最理想的是，处理完R0时，立即处理R1，也就是将R1放在原来R2的位置，即隔一个逻辑记录放一个新的逻辑记录，因此最后磁盘布局如下：

按这种布局，磁头读取R0后，再在缓存区进行处理后，刚好磁头转到R1的位置，这时经过了3ms + 3ms = 6ms时间（读取3ms，处理3ms），然后接着处理R2、R3、...、R9、R10,每个逻辑记录都需要6ms，因此最小使用时间为11 * 6ms = 66ms。

因此示例中第1题选C 366ms，第2题选B 66ms。

# P18 计算机总线

  • 所谓总线(Bus)，是指计算机设备和设备之间传输信息的公共数据通道。
  • 总线是连接计算机硬件系统内多种设备的通信线路，它的一个重要特征是由总线上的所有设备共享，因此可以将计算机系统内的多种设备连接到总线上。

根据总线所处的位置不同，总线通常被分为三种类型，分别是：

  • 内部总线，往往是指微机内部各个外转芯片与处理器之间的总线，是芯片这个级别。
  • 系统总线， 是微机中各个插件板和系统板之间的总线，是属于插件板这一层级的，比如我们平常所接触到的PCI、VGA。
    • 具体要进一步了解的是系统总线。系统总线又分为以下三种总线：
    • 数据总线(Data Bus, DB)， 用来传输数据信息的，是双向的，即可以通过DB从内存或输入设备读取数据，也可通过DB将内部数据送到内存或输出设备。DB的宽度决定了CPU和计算机其他设备之间每次交换数据的位数。计算机是32位还是64位的，如果是32位，则计算机的一个字是32个bit位，这说明总线的宽度是32个bit位，则一次能够传输的数据量是32个bit位。
    • 地址总线(Address Bus, AB)， 用于传送CPU发出的地址信息，是单向的。假设地址总线是32位，代表地址总线是2^32次方，即代表4G内存，当有的时候需要将总线作为其他用途的时候，可能就没有这么多可用总线，如果需要用的内存超过4G，则可以考虑使用64位操作系统，否则操作系统管理不了这么多的内存空间的。当然这只是一个举例，因为在系统上面也有这种概念的区分，你的系统之所以能安装64位操作系统，是因为你的硬件/地址总线有这个宽度带支持。 地址总线的宽度决定了CPU的最大寻址能力 ！
    • 控制总线(Control Bus, CB), 发送控制信息的总线，如控制信息、时序信息和状态信息等，也是双向的。
  • 外部总线， 微机与外部设备的总线。

# P19 串联系统与并联系统可靠性计算

  • 计算机的可靠性是指从它开始运行(t=0)到某一个时间t这段时间内能正常运行的概率，用R(t)表示。
  • 失效率，所谓失效率，是指单位时间内失效的元件数与元件总数的比例，用 lambda λ 表示。
  • 两次故障之间系统能正常工作的时间的平均值称为平均无故障时间MTBF，即 MTBF = 1 / λ 。
  • 串联系统可靠性R = R1 * R2 * R3 * ... * RN ，即需要各个子系统全部正常运行时，系统才可靠。
  • 失效率 λ = λ1 + λ2 + λ3 + ... + λN， 注意这仅是一个简单计算公式，不一定准确，如20个子系统，每个子系统的失效率λ=0.1, 这时按这个公式计算最终整个系统的失效率λ = 0.1 * 20 = 2 = 200 %,而这是不可能的！！！ 这个公式是个近似公式，简化公式，当失效率极低的时候，可以使用这个公式进行计算。

示例，设计算机系统由CPU、存储器、I/O三部分组成，其可靠性分别是0.95、0.90和0.85，求计算机系统的可靠性。

此时计算机的可靠性 R = R1 * R2 * R3 = 0.95 * 0.90 * 0.85 = 0.73

  • 并联系统，只要有一个子系统正常工作，系统就正常工作，这样的系统称为并联系统。
  • 并联系统的整个系统的可靠性 R = 1 - (1 - R1) * (1 -R2) * (1 -R3) * ... * (1 -RN)
  • 在并联系统中只有一个子系统是真正需要的，其余N - 1个子系统为冗余子系统，随着冗余子系统数量的增加，系统的平均无故障时间增加了。

示例，设一个系统由3个相同的子系统构成，其可靠性为0.9，求整个系统的可靠性？

整个系统的可靠性 = 1 - (1 - 0.9) ^ 3 = 0.999

  • N模冗余系统，N模冗余系统由N个(N = 2n + 1) 相同的子系统和一个表决器组成，表决器把N个子系统多数相同结果的输出作为系统的输出，通过表决将错误屏蔽掉了，使用这种系统能够提高系统的可靠性。其可靠性可按如下公式计算：

提高计算机的可靠性一般采取如下两项措施：

  • 提高元器件质量，改进加工工艺与工艺结构，完善电路设计。
  • 发展容错技术，使得在计算机硬件有故障的情况下，计算机仍然能继续运行，得出正确的结果。

# P20 校验码的概念

# 差错控制 - CRC与海明校验码

  • 什么是检错和纠错？

    • 检错：检查出错误。
    • 纠错：不断要检查出错误，还需要纠正错误。
    • 要达到检错和纠错，需要增加冗余信息来实现。而在编码的过程中，往往是通过增大码距来实现检错和纠错。

  • 计算机系统运行时，为了确保数据在传送过程中正确无误，一是提高硬件电路的可靠性，二是提高代码的校验能力，包括检错和纠错。

  • 通常使用校验码来检测传送的数据是否出错。其基本思路是把数据可能出现的编码分为两类：

    • 合法编码，合法编码用于传送数据。
    • 错误编码，错误编码是不允许在数据中出现的编码。

  • 码距：一个编码系统的码距是指整个编码系统中任意(所有)两个码字的最小距离。也就是任意两个合法编码之间至少有多少个二进制位不同。

  • 例：

    • 若用1位长度的二进制编码，若A=1, B=0，这样A,B之间的最小码距为1。
    • 若用2位长度的二进制编码，若以A=11,B=00为例，A,B之间的最小码距为2。
    • 若用3位长度的二进制编码，可选用111，000作为合法编码，A,B之间的蹑小码距为3。
    • 比如我们要传输A和B这两个数据，若码距为1，正常传输过去的话，A=1,B=0，如果传输后获取的第一个数据是0，这个时候不知道这个0是否是错误的编码，因为0也是合法的，所以此时不知道至道要传输的数据是0还是1。
    • 我们可以使用两位编码来传输，正常传输A=11表示1，B=00表示0,即你要传输1的话，就传输两个1，要传输0的话，就传输两个0，这个时候我们就可以正常发现是否出错错误，如接收到的数据是1100,这时可以发现传输的数据是正确； 如果接收到的数据是1000的话，这时候就发现10是不对的，因为我们约定只能传输11或00,而你传输的是10,不在约定的传输列表中，因此就可以发现10传输是异常的，也就是检错出来了。但这时候并不能纠错，因为不能确定10对应的正确码到底是11还是00，因此此时不能纠错。
    • 我们可以通过再增加码距带进行纠错。假如我们使用3位长度的二进制来编码。即码距为3，用111编码数字1，用000编码数字0。这时候正常接收的编码是 111 000,表示传输了数据1和0。如果我们接收到了 110 000的话，就可以发现 110是一个错误编码，因为111和000是合法编码，这个时候能够正常检错。同时，我们发现110这个错误编码与111这个合法编码更接近，因为我们就可以进行纠错，将110变成111，纠错后获取的数据就是 111 000，也就是需要正常传输过来的数据了。这就说明这时候正常纠错了！

  • 码距与检错、纠错有何关系？

    • 在一个码组内为了检测e个误码，要求最小码距d应满足： d >= e + 1
    • 在一个码组内为了纠正t个误码，要求最小码距d应满足: d >= 2t + 1

# P21 校验码-循环校验码CRC

  • CRC是指循环冗余校验码（Cyclic Redundancy Check, CRC)。
  • 循环冗余校验码由两部分组成： 左边是信息码(数据)， 右边是校验码。
  • 我们使用信息码 / 校验码 来看余数是否为0，即是否能够完成整除，如果能够整除，则说明传输的数据是正常的，如果余数非0，则传输的数据是异常的，说明传输过程中出现了错误。
  • 上面信息码 除以 校验码 所使用的除法不是普通的除法，而是模2除法，与普通除法是有区别的。除数计算的时候使用异或运算（异或：同则为0，不同则为1）。模2除法不向上位借位，直接进行除法异或计算即可。
    • 如100101除以1110，结果得到商为110，余数为1。

示例：

校验码计算示例：原始报文为"110 0101 0101"，其生成多项式为："x^4 + x^3 + x + 1"，对其进行CRC编码后的结果为多少？

解答：

首先要先多项式转成二进制形式的，多项式转成二进制形式为11011。

然后将原始报文左移5 -1 =4位，即生成多项式的长度减1位，多项式长度为5，因此后面补4个0，也就是在原始报文后面被4个0，即变成 110 0101 0101 0000。

然后再使用被0后在数字模2除法除以11011，并计算除数。

1 0 0 1 1 1 1 1
1 1 0 1 1 除 1 1 0 0 1 0 1 0 1 0 1 0 0 0 0
减 1 1 0 1 1
余 1 0 0 1 0
减 1 1 0 1 1
余 1 0 0 1 1
减 1 1 0 1 1
余 1 0 0 0 0
减 1 1 0 1 1
余 1 0 1 1 1
减 1 1 0 1 1
余 1 1 0 0 0
减 1 1 0 1 1
余 0 0 1 1

所以将最后的余数0011作为校验码，因此CRC编码为：1100 1010 101 0011。

我们用这个CRC编码除以11011，检查一下结果是否为0 。

这个相对来说比较复杂。我们来个简单一点的计算。

  • 检错计算举例

实际的CRC校验码生成是采用二进制的模2算法（即减法不借位、加法不进位）计算出来的，这是一种异或操作。下面通过一些例子来进一步解释CRC的基本工作原理。假设：

(1)设约定的生成多项式为G(x)=x4+x+1，其二进制表示为10011，共5位，其中k=4。

(2)假设要发送数据序列的二进制为101011(即f(x))，共6位。

(3)在要发送的数据后面加4个0(生成f(x)*xk)，二进制表示为1010110000，共10位。

(4)用生成多项式的二进制表示10011去除乘积1010110000，按模2算法求得余数比特序列为0100（注意余数一定是k位的）。

(5)将余数添加到要发送的数据后面，得到真正要发送的数据的比特流：1010110100，其中前6位为原始数据，后4位为CRC校验码。

(6)接收端在接收到带CRC校验码的数据后，如果数据在传输过程中没有出错，将一定能够被相同的生成多项式G(x)除尽，如果数据在传输中出现错误，生成多项式G(x)去除后得到的结果肯定不为0。

我们来计算一下这个例子：

多项式g(x) = x^4 + x + 1，对应的二进制为 10011，即多项式长5位，我们需要在原码后面补5-1 = 4 个0。

原码为 101011，补4个0后，就变成了 10 1011 0000。

再用补0后的数据与10011进行模2除法。

1 0 1 1 0 0
1 0 0 1 1 除 1 0 1 0 1 1 0 0 0 0
减 1 0 0 1 1
余 1 1 0 1 0
减 1 0 0 1 1
余 1 0 0 1 0
减 1 0 0 1 1
余 1 0 0

所以最后4位是0100，也就是CRC校验码是 0100，CRC编码结果为 1010110100。

再看一个例子：

任意一个由二进制位串组成的代码都可以和一个系数仅为‘0’和‘1’取值的多项式一一对应。例如：代码1010111对应的多项式为x^6+x^4+x^2+x+1，而多项式为x^5+x^3+x^2+x+1对应的代码101111。

假设使用的生成多项式是G(X)=X^3+X+1。4位的原始报文为1010，求编码后的报文。

我们来计算一下。

多项式为g(x) = x^3 + x + 1，转换成对应的二进制就是 1011，多项式长度为4，需要在原始报文后面补充 4 -1 = 3 个0。

因此补0后的报文为 1010 000。

然后再计算模2除法，使用 1010 000 除以 1011。

1 0 0 1
1 0 1 1 除 1 0 1 0 0 0 0
减 1 0 1 1
余 1 0 0 0
减 1 0 1 1
余 0 1 1

可以看到最后余数为011，因此将011添加到原始报文后面，就变成了 1010 011。

即CRC校验码为011，最终发送的编码为 1010 011 。

我们验证一下，用 1010 011 除以 1011 看一下结果是否为0：

1 0 0 1
1 0 1 1 除 1 0 1 0 0 1 1
减 1 0 1 1
余 1 0 1 1
减 1 0 1 1
余 0

此时刚好除尽，余数为0，说明我们计算正确。

说明，以上计算过程之所以使用表格形式，主要是为了使各个二进制位对齐，便于计算！

通过上面的例子我们大概的就了解了如何去计算一个信息字段的CRC校验码，可以把求CRC校验码的步骤总结如下：

1、将X的最高次幂为R的生成多项式G(X)转换成对应的R+1位二进制数。

2、将信息码左移R位，相当于对应的信息多项式C(X)*2^R。

3、用生成多项式（二进制数）对信息码做除，得到R位的余数(注意：这里的二进制做除法得到的余数其实是模2除法得到的余数，并不等于其对应十进制数做除法得到的余数。)。

4、将余数拼到信息码左移后空出的位置，得到完整的CRC码。

# P22 校验码-海明校验码

  • 海明校验码是一种利用奇偶性来检错和纠错的检验方法。
  • 海明码的构建方法是的2的幂次位上，如0,1,2,4,8,16,32, ...等等位上面放置校验码。即在数据位的之间的特定位置上插入r个检验位，通过扩大码距来实现检错和纠错。
  • k个数据信息位与r个校验位的关系： 2^r - 1 >= k + r
  • 理解上面的公式：r个校验位(校验位是0或1)可以表示2^r 种可能，其中只用一种是正常状态，其余 2^r -1种状态表示有错误在某一个位上，而总共有 k + r 位，校验的可能性（异常时）要大于等于所有的位数，因此就有 2^r - 1 >= k + r 。
17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 位数
D11 D10 D9 D8 D7 D6 D5 D4 D3 D2 D1 D0 信息位
R4 r3 2 r1 r0 校验位
  • k值与r值表格对应关系
数据信息位k值 校验位r值
1 2
2~4 3
5~11 4
12~26 5
27~57 6
58~120 7
  • 我们要记住以下关系：
数据位 位与2的幂次方的关系 数据位与校验位的关系
D0 3 = 2 ^ 1 + 2 ^ 0 D与r0、r1有关
D1 5 = 2 ^ 2 + 2 ^ 0 D1与r0、r2有关
D2 6 = 2 ^ 2 + 2 ^ 1 D2与r1、r2有关
D3 7 = 2 ^ 2 + 2 ^ 1 + 2 ^ 0 D3与r0、r1、r2有关
D4 9 = 2 ^ 3 + 2 ^ 0 D4与r0、r3有关
D5 10 = 2 ^ 3 + 2 ^ 1 D5与r1、r3有关
D6 11 = 2 ^ 3 + 2 ^ 1 + 2 ^ 0 D6与r0、r1、r3有关
D7 12 = 2 ^ 3 + 2 ^ 2 D7与r2、r3有关

​

  • 通过上表的数据位与校验位的关系，我们可以知道校验位与数据位的关系如下：
校验位 与校验位相关的数据位
r0 D0、D1、D3、D4、D6
r1 D0、D2、D3、D5、D6
r2 D1、D2、D3、D7
r3 D4、D5、D6、D7
  • 计算校验位时的值时，把相关的各个数据位异或(同则为0，不同则为1)求值即可。
    • 所以有以下等式：
    • r0 = D0 Xor D1 Xor D3 Xor D4 Xor D6
    • r1 = D0 Xor D2 Xor D3 Xor D5 Xor D6
    • r2 = D1 Xor D2 Xor D3 Xor D7
    • r3 = D4 Xor D5 Xor D6 Xor D7

所以按如上公式进行编码，信息数据 0110 1001，有8位数据，此时我们知道需要4位校验码。

12 11 10 9 8 7 6 5 4 3 2 1 位数
D7 D6 D5 D4 D3 D2 D1 D0 信息位
0 1 1 0 1 0 0 1 真实数据
r3 r2 r1 r0 校验位
0 1 0 1 实际校验位数据

所以：

  • r0 = D0 Xor D1 Xor D3 Xor D4 Xor D6 = 1 Xor 0 Xor 1 Xor 0 Xor 1 = 1
  • r1 = D0 Xor D2 Xor D3 Xor D5 Xor D6 = Xor(1, 0, 1, 1, 1) = 0
  • r2 = D1 Xor D2 Xor D3 Xor D7 = Xor(0, 0,1, 0) = 1
  • r3 = D4 Xor D5 Xor D6 Xor D7 = Xor(0, 1, 1, 0) = 0

将上面的几个校验位填写到表格中，最后获取到海明码为： 0110 0100 1101。

如果实际获取到的海明码是： 0110 0011 1101,这个时候就实际的海明码与正确的海明码异常就可以知道第7位数据是异常的（正常应全为0，非0的则为异常）。

注意：

  • 以上操作都是按偶校验进行操作的。
  • 如果采用奇校验，则将各校验位的偶校验值取方即可。

# P23 操作系统概述

操作系统基本原理在考试中一般考到7分，比较重要。对于操作系统概念，本身大家不陌生，因为使用计算机，天天都要与操作系统打交道。但是对于操作系统相关的原理，大家平时不会去深入的研究。我们需要展开相关的内容。在讲具体的知识点之前，给大家讲一下操作系统的基本情况。

  • 操作系统是用来管理整个系统的软硬件资源的。
  • 如果一台计算机买回来后，如果没有安装操作系统，你将无法控制计算机的资源。只有安装了操作系统，你才能操作、控制这些资源。
  • 操作系统是人和硬件之间的一种接口。比如说我们可以通过点击鼠标来往硬盘里面存放数据，都要依赖于操作系统。
  • 其他的一些应用软件，也是工作在操作系统上的，比如Office应用软件。所以操作系统即是人机接口，也是应用软件与硬件之间的接口。
  • 接口往往是命令，比如以前的DOS系统，你需要通过命令来控制系统，往往不那么直观，后来出现了Windows系统，图形化界面比较直观。
  • 应用软件和硬件之间的接口是指API接口，指操作系统为应用软件专门提供的API接口，来实现相关的功能。

操作系统具体具备哪些方面的管理也只能：

  • 进程管理
  • 存储管理
  • 文件管理
  • 作业管理
  • 设备管理

以上五个大的方面都会包含一系列小的知识点。

  • 进程管理包含 进程的状态、前趋图、PV操作、死锁的问题。
  • 存储管理包含 段页式存储、页面置换算法。
  • 文件管理包含 索引文件、位示图。
  • 微内核操作系统包含 虚设备与SPOOLING技术等。
  • 作业管理与设备管理考得比较少。

# P24 进程状态转换图

  • 进程的状态

    • 定义：进程状态是指在操作系统当中，对进程进行管理时，为进程指定了几种状态，以便于给进程分配相应的资源，把它管理起来。

  • 进程的状态（三态模型）：

    • 最初的时候把进程分为运行态、就绪态、等待态三种状态。
    • 运行态：进程所需要的所有资源全部配齐了，并且分配了CPU资源，这时候就处于运行状态。
    • 就绪态：指其他的所有资源全部配齐，就是缺少CPU资源，这时候处于就绪态。这是一种万事俱备，只欠东风的状态。
    • 等待态：除了没有CPU资源，还缺少其他资源，比如和外设有交互，等待用户输入指令等，这时候处于等待状态。

  • 进程状态的转换：

    • 在运行态，如果缺少某种资源，需要等待某个事件的发生，这个时候就会从运行态转换成等待态。一旦缺少某些资源就进入到等待状态。
    • 如果等待的这些资源现在可以调配过来，这时候等待态可以转换成就绪态。注意，没有箭头从等待状态指向运行状态。不能从等待态直接转换运行态。需要重新排队，获取最为核心的CPU资源。
    • 就绪状态排队之后，等待CPU给出调度指令，这时就进入到运行状态。
    • 注意一点，进入到运行状态后，不见得一次性能完成自身的全部任务，因为CPU资源相当宝贵，如果你是一个大的任务，进去之后就完整的占用了CPU资源，别的程序就无法运行。因此采用了CPU时间片轮转的方案来分配CPU资源。意思就是一个进程，从就绪到运行态，只能运行一个时间片，等你的时间片用完，即使你的任务还没有完成，你也必须先退出运行态，你得退出运行态，进入到就绪态，等下一次调度，等下一个CPU时间片轮到你的时候才能进入到运行态。
    • 以上是三种状态之间基本转换的原则。

  • 细分进程状态及其转换---五态模型

    • 等到三种状态应用比较成熟后，发现其中存在一个问题，就是三种状态不足以含盖常见的各种情况。
    • 比方说，人为地希望将某一个进程暂停、挂起起来，管控起来，这时候用三态模型已经无法做到这一点，所以提出了五态模型。
    • 比原先三态模型多出了静止就绪态和静止阻塞态。
    • 活跃阻塞态对应三态模型中的等待态（也叫阻塞态、睡眠状态）。
    • 活跃就绪态对应三态模型中的就绪态。
    • 运行态对应三态模型中的运行态。
    • 提出了一种挂起操作。
    • 运行状态挂起时就会进入到静止就绪态，因为这个时候是人为地想把进程搁置起来不处理，进程并不缺少其他的资源，这时就是静止就绪态。
    • 静止就绪态可以恢复或激活，就进入到活跃就绪态，（通俗一点讲，比方说我正在听歌，突然来了个电话，歌声会影响我接电话，我就将歌曲暂停，这就是一个挂起动作，挂起之后，等到我接完电话，我就点击恢复播放歌曲，这个时候就激活了，就进入到活跃就绪态）。活跃就绪态再经过调度就可以运行了。
    • 静止阻塞也可以通过激活到达活跃阻塞（等待态）。

# P25 前趋图

  • 前趋图试图解决什么样的问题？

    • 北方人喜欢包饺子吃。包饺子有多道工序，包括A绞肉、B切葱末、C切姜末、D搅拌、E包饺子。
    • 我们要完成包饺子这件事件，可以按顺序方式进行，如果按左侧的A->B->C->D-E，先绞肉再切葱末再切姜末再搅拌再包饺子，这个操作是没有问题的，但平常我们不是这样的，因为大家人多力量大，一般都可以多人一起操作，不需要一个人从头忙到尾，所以这个时候就需要考虑哪些任务是有先后顺序的，哪些任务是可以并行做的。
    • 如果我们按左边的图来表示，就会给人一种误解，只能够先绞肉，再切葱末，再切姜末，这个逻辑就会有问题，所以我们用前趋图的形式来表达的是要完成的一系列的活动的先后约束关系。
    • 比方如通过前面的讲解我们可以了解到绞肉、切葱末、切姜末可以并行的处理，所以将A/B/C放在同样的一条线上，它们之间没有A做完才能做B开始，所以他们之间没有连线，但是必须要完成前面三个活动才能搅拌，所以必须完成A、B、C活动才能开始D活动，因此就有A->D、B->D、C->D的制约关系，D完成之后，才能完成包饺子E的工作。
    • 通过这个图可以直观的看到，哪些任务可以并行，哪些任务有先后关系，这也就是前趋图想表达的东西，这就是前趋图的基本理念。

  • 前趋图是一个有向无循环图，由结点和有向边组成，结点代表各程序段的操作（任务），而结点间的有向边表示两个程序段操作（任务）之间存在的前趋关系(-->)。 程序段Pi和Pj的前趋关系表示成Pi->Pj，其中，Pi是Pj的前趋，Pj是Pi的后继，其含义是Pi执行结束后Pj才能执行。

# P26 进程的同步与互斥

  • 同步与互斥是进行PV操作的前提。如果没有理解什么叫做进程的同步，什么叫做进程的互斥，就很难进行PV操作的实际问题。
  • 互斥：互斥就是指的在同一时刻，只允许某一个进程去使用资源。同一个资源不能同时服务于多个进程。
    • 比如说千军万马过独木桥，独木桥就是一个资源，不允许很多人同时上独木桥，会出现安全事故。
    • 所以要求人员是一个一个通过的，一个人占用了独木桥资源，其他人得等待，这叫互斥使用资源。
    • 如果不是独木桥，而是一个人行天桥，供多人同时使用，那我们认为这是一个共享资源。

同步与互斥在PV操作里面，提得非常多，就像一对双胞胎，经常说同步与互斥。请思考一个问题，同步与互斥是不是互为反义词，它们不是反义词。

  • 同步的反义词是异步。
  • 互斥的反义司是共享。

不要把概念给弄混了。

  • 同步：速度有差异，有一定情况下停下等待。
    • 比方说张三步行，李四骑自行车从起点A到终点B（商场），他们从同样的起点到同样的终点，步行速度比较慢，骑自行车速度比较快，如果张三和李四都以全速前进，毫无疑问，李四速度快会先到，这时候他们约定要一起到，这时候李四骑一段时间后，发现超越张三很远了，就停下来等一等，这被称为同步的过程。
    • 同步说白了就是有速度匹配的要求，当差距拉得比较大的时候，要求速度快的停下来等一等，这就是同步的过程。

# 进程的同步与互斥

我们来看一下PV操作里面的经典问题，生产者与消费者问题，哪里会存在同步，哪里会存在互斥。

  • 首先讨论单缓存区情况
    • 单缓存区情况是市场容量为1，存放了一个东西，就不能存放第二个。
    • 对于市场的操作，不能说既有生产生去存放东西，也有消费者去搬东西，这不允许。同一时刻只允许有一个人进入到市场来进行操作。这就是互斥，市场是一个互斥资源，只允许一个人操作，不能够同时去操作，这就是互斥的问题。
    • 同步的问题：生产者把东西放在市场上去，放了一个后，市场容量为1，此时市场就满了，如果再接着存放一个商品的话，就会产生溢出问题，所以不允许再存放一个商品。只有等到消费者把市场里面的商品拿走消费掉，才允许生产者往市场里面放东西。这个过程与停下来等别人是一回事，生产者要停下来等消费者消费完商品，生产者才能往市场里面存放东西。这就是同步的问题。
  • 再来讨论一下多缓冲区情况
    • 多缓冲区情况类似
    • 同步的时候步子迈得大一些。原先只能放一个，现在可以放十个之类的。
    • 现在可以等市场放满后再停下来等消费者消费。

以上就是生产者与消费者里面的同步与互斥的问题。

对于PV操作，必须要分析清楚同步在哪些地方，互斥在哪些地方，你才能够准确的定位哪里要写P操作，哪里要写V操作。

# P27 进程管理-PV操作

需要利用同步与互斥的理念来解决实际的问题，所用到的工具是PV操作。PV操作内容是在整个操作系统部分是最难的部分。

PV操作操作不见得多复杂，就是应用比较灵活。

下面我们来了解相关的概念，并以例题来说明PV操作在整个并发进程系统中起到什么作用。

  • 临界资源：进程间需要互斥访问的一些资源，比方说打印机、磁带等。
  • 临界区：每个进程中访问临界资源的那段代码称为临界区。通俗一点讲就是临界区是程序代码段，不是缓冲区之类的。
  • 信号量：是一种特殊的变量。在PV操作中离不开信号量。应用于PV操作的一种专属变量。

看一下PV操作到底是怎么回事：

  • PV操作是两大原子操作的一个组合，有P操作，有V操作。
  • P(S)操作：
    • 首先对信号量S进行自减一操作，即（S = S - 1)，如原先S=10,则自减一后S就变成了9。
    • 判断信号量S是否小于0，即 if S < 0：
      • 如果为T(True)，即S<0,则会阻塞当前进程继续执行的状态，把这个进程放到进程队列里面，则会将P(S)这个进程阻塞起来，让这个进程进入到等待状态。
      • 如果为F(False)，如S=0,1,2之类的，会继续向下执行当前程序。
  • V(S)操作：
    • 首先对信号量S进行自加一操作，即（S = S + 1)，如原先S=10,则自加一后S就变成了11。
    • 判断信号量S是否小于或等于0，即 if S <= 0：
      • 如果为T(True)，即S<=0,则会进程队列里面唤醒一个进程，让它继续执行。
      • 如果为F(False)，会继续向下执行当前程序。
  • PV操作本身并不复杂，是将几个简单的操作组合起来。

下面将PC操作带到一个具体的问题当中，看PV操作解决了什么问题。

假设没有PV操作，系统中有两个进程，一个生产者进程，一个消费者进程。生产者负责生产产品，并送到缓冲区，消费者从缓冲区取出产品，并把产品消费掉。

仍然以单缓存区为例，也就是只有一个市场容量的生产者和消费者为例来说明。

最初的时候，市场是空的（缓冲区是空的），这个时候，允许生产者往里面放东西。假设这时候，生产者进程执行，将一个产品放到缓冲区，这个过程没有问题。这个时候如果消费者进程没有运行，生产者进程如果再运行一次，再生产一个产品，再往缓冲区存放产品，因为缓冲区已经有一个产品（缓冲区满了），再放一个产品的话，就会产生溢出问题。

正是由于这个原因，考虑加入PV操作。

上面是生产者进程先执行，这比较片面，也有可能是消费者进程先执行。

如果我们先让消费者进程先执行，想从市场（缓存区）中取出一个产品，但是由于市场刚开始是空的，即没有产品，这个时候如果执行消费者进程，可以发现没有可用的产品，执行也会出问题。

因此可以看到无论从生产者开始执行，还是从消费者进程开始执行，都有可能产生一定的问题。因此就引入了PV操作，来解决这个问题。

下面将PV操作引入进来，看看情况会怎么样：

加入PV操作后，给定了信号量S1和S2的初值，S1初值为1，S2初值为0。我们再按原来的方式执行生产者进程或消费者进程。

首先我们来执行生产者进程：

生产者进程，生产一个产品后，需要执行P操作，P(S1)操作会对S1信号量进行自减1操作，S1 = S1 - 1 = 0，再进行判断，此时S < 0 条件判断为False(因为S1 = 0,不小于0，此时程序不会被阻塞)，因此生产者进程继续向下执行，因此会送产品到缓冲区。再执行V操作，V(S2)操作对S2信息量进行自加1操作，S2 = S2 + 1 = 0 + 1 =1。 这时候的状态是：S1 = 0, S2 = 1。

此时若我们不执行消费者进程，再次执行生产者进程：再生产一个产品，然后执行P操作，P(S1)操作会对S1信号量进行自减1操作，S1 = S1 - 1 = 0 - 1 = -1，再进行判断，此时S < 0 条件判断为True(因为S1 = -1,小于0，此时程序会被阻塞，进入到等待队列)，因此生产者进程会被阻塞，不会继续向下执行。

加入PV操作后，第二次生产的产品不会被送到缓冲区，就不会产生溢出。这种情况可以顺利的执行下去。

有些同学可能会有一定的疑惑，就是咱们把生产者进程阻塞进来了，不能继续往下面执行。如果消费者消费完产品，如何去让生产者知道然后继续执行下去呢？

我们在刚才的生产者阻塞状态下执行消费者进程。此时S1 = -1, S2 = 1 。下面我们看一下消费者进程。

消费者进程先执行P(S2)操作，对S2信号量进行自减1操作，S2 = S2 - 1 = 1 - 1 = 0，再进行判断，此时S < 0 条件判断为False(因为S2 = 0,不小于0，此时程序不会被阻塞)，因此消费者进程继续向下执行，因此会从缓冲区取出产品，此时缓冲区就变成了空的了（表示生产者可以放产品进去）。再执行V(S1)操作，V(S1)操作对S1信息量进行自加1操作，S1 = S1 + 1 = -1 + 1 = 0， 再进行判断，此时S <= 0条件判断为True(因为S1 = 0，小于或等于0，此时就会从等待队列里面将等待进程激活，相当于唤醒生产者进程)。 这时候的状态是：S1 = 0, S2 = 0。

现在从另外一个方面看，如果一开始不运行生产者进程，而直接运行消费者进程。看看情况会怎么样。

即初值S1 = 1, S2 = 0。

执行消费者进程，先进行P(S2)操作，P操作需要对信息量S2进行自减1操作，S2 = S2 - 1 = 0 - 1 = -1，再进行判断，此时S<0条件判断为True(因为S2 = -1，小于0，此时程序会被阻塞）,说明开始时缓冲区是空的，消费者进程不能硬执行，可以看出消费者进程产生的错误也可以用PV操作来避免。

PV操作所解决的问题，其实是并发进程之间某些约束关系的解决。因为没加PV操作会存在一些异常，加了PV操作会很好的解决这些问题，所以在以后做题也需要这样进行分析，给你几个进程，走到哪一步需要其他进程进行配合需要P操作来阻塞当前进的状态，使用V操作进行唤醒操作。

# P28 PV操作练习题1

在考试的时候PV操作有一定的难度，考试的时候主要考虑进程间的约束关系，在哪些位置应该要阻塞起来，等待另位的进程进行相关的操作，等待完成后再进行下一步的操作。

这个题有一些的难度，首先来看该书店最多允许N个购书者进入，这要如何实现。在日常中经常遇到，比方如停车场在进入口有一个闸门，显示还有多少停车位，只在当停车场还有车位时，才让新的车辆进入停车场，有车进入时进入P操作，消费资源，否则不让新的车辆进入。只有当有车驶离停车场调用V操作释放资源，才允许新的车辆进入。

P(Sn)/V(Sn) 实现的功能就是允许n个购书者进入书店，有人进入的时候Sn信号量减1，有购书者离开后Sn信号量加1。

购书者付款操作，只有购书者一个人是不能完成的，必须要收银员配合才能完成付款动作。

假设没有a1,a2,b1,b2操作，让收银员进程进行操作，不停的收费，周而复始的收费，但是这是不行的，没有人买书付款是不能收费的，因为没有付款动作，收费是没有意义。因此在b1位置需要一个P操作，而这个P操作需要付款位置的V操作来唤醒收银员进行收费操作。

这个P/V操作需要针对同一个信号量。由于S1/S2/Sn的初值是0、0、n。

由于Sn已经使用了，那么此我我们可以选择信号量S1填写入P( )、V( )操作中，也可以选择S2信号量填写，需要配对，即：

b1处填写P(S1)，a1处填写V(S1)。 或者：b1处填写P(S2)，a1处填写V(S2)。

同时，V操作不具备阻塞功能的，比如付款，不是购书者直接把钱甩给收银员就可以立即拿着东西就走，而是需要收银员先进行书的总价的计算以及将书中的磁条处理完成，也就是购书者也有一个阻塞操作，因此a2和b2处也有一对P/V操作，a2处填写P操作，b2处理填写V操作，若之前的操作使用的S1信号量，那么就只我剩下S2信号量了，那么：

a2处填写P(S2)，b2处填写V(S2)。 或者： a2处填写P(S1)，b2处填写V(S1)。

因此可填写的组合为：

a1： V(S1) , a2: P(S2), b1: P(S1). b2: V(S2)

或者：

a1： V(S2) , a2: P(S1), b1: P(S2). b2: V(S1)

所以选择：A,C

从这里可以看到PV操作解题的核心是找出这种约束关系，在这个过程中，不防先进行某个进程会出现什么问题，应该在哪里添加什么约束；假设执行另外一个进程，又会出现什么问题，需要加什么约束，然后加入PV操作能解决这个问题，那么这时候的PV操作就是正确答案了。

# P29 PV操作与前趋图

把前趋图（P25，进行的活动之间的关系）转换成PV操作的形式。

即将前趋图的操作转换成相应的进程，按前趋图的前后顺序执行PV操作。

A/B/C/D/E代表一系列的进程，A、B、C一开始就可以执行，并不受什么约束，D操作必须先完成A、B、C操作，E操作必须先完成D操作。

因此在进程D中增加了三个锁🔒P(Sa)、P(Sb)和P(Sc)，代表A、B、C进程没有完成是不能进行搅拌工作的，因此在A、B、C进程中增加V操作，唤醒D操作中的阻塞的进程，代表只有绞肉(V(Sa))、切葱末(V(Sb))、切姜末(V(Sc))完成后，才能进入后续操作，D完成后(V(Sd))才能进入进程E操作。

我们看一下示例：

在每个箭头处填写信号量，从上到下，从左到右依次填写信号量，像下面的这样的：

因为我们有4个信号量，因此在P3左侧是上: S1信号量， 下: S2信号量，在P3右侧是上: S3信号量， 下: S4信号量

这样更处理更简单。

在箭头的开始(起点)位置需要一个V操作，箭头的结束(终点)位置需要一个P操作。再把箭头对应的信号量写入到PV操作中即可。

因此：

P1位置：起点V(S1) 终点（P3处）需要填写P(S1)。

P2位置：起点V(S2) 终点（P3处）需要填写P(S2)。

P3位置：开始的位置需要填写P(S1)、P(S2)， 因为有两条信号量引出，因此，指向终点（P4处）需要填写V(S3)、指向终点（P5处）需要填写V(S4)。

P4位置：开头位置P(S3) 。

P5位置：开头位置P(S4) 。

最终的选择如下：

这样解决这个问题非常的高效。

# P30 死锁问题

  • 进程管理是操作系统的核心，但如果设计不当，就会出现死锁问题。如果一个进程在等待一个不可能发生的事，则进程就死锁了。而如果一个或多个进程产生死锁，就会造成系统死锁。
  • 所谓死锁，是指两个以上的进程互相都需要对方已经占有的资源导致无法继续运行下去的现象。

给定一定数据的进程，每个进程需要多少资源，计算至少需要多少资源才不会发生死锁。

  • 所谓死锁，就是指的系统当中有一系列的资源，有一系列需要用到这些资源的进程，这些进程需要系统分配资源才能运行，如果系统在某一时刻，发现所有的可用资源都已经分配出去了，而所有进程都没有办法完成它本身的职责任务，从而释放已经占有的资源，这就会产生死锁，所有进程都在等待别人给他资源，而自己又不想把自己的资源分享给别人。这样样就造成了系统无法完成一系列任务，就会产生死锁问题。

我们先看一下，哪些情况下就会发生死锁。

假设系统只有5个资源，系统有没有可能发生死锁呢？有可能的，如A进程分配2个资源，B进程分配2个资源，C进程分配1个资源，这个时候系统进程用完了，再没有进程分配给任何一个进程，这时候就死锁了。5个资源有没有可能不发生死锁呢？可能的，如将5个资源全部分配给A进程，此时A进程需要的资源得到的满足，就会执行自己的任务，执行完成后就会释放所占用的资源（5个），依次再把全部的资源给B进程和C进程，这样就不会发生死锁。因此5个资源是有可能发生死锁的。

那假设系统有10个资源，这时候有没有可能发生死锁呢？也是有可能的，如A进程分配4个资源，B进程也分配4个资源，C进程分配2个资源，这时候资源全部分配完成，没有可用资源了，这时候又发生死锁了。即10个资源也可能发生死锁问题。

那假设系统有15个资源，这个时候有没有可能发生死锁呢？因为A、B、C进程每个进程都需要5个资源，我们可以直接给每个进程分配5个资源，分配完成后系统资源用完，但这个时候由于A、B、C所需要的资源都已经满足了，就会去执行自己的任务，执行完成任务后就会将用占用的资源释放掉，这时候系统的15个资源又都空闲了，因此这时候不会发生死锁，即系统有15个资源是不会发生死锁的。

但是题目求的是至少需要多少个资源系统不会发生死锁。即无论怎么分配都不会产生死锁。

我们先给每个资源分配它需要的资源数减一个资源，本例中，给每个进程分配5 - 1 = 4 个资源，这时候每个进程还需要1个资源就可以得到满足，然后释放自己占用的进程，因此我们假设系统还有1个资源。给任何一个进程，假设给A进程，这时候A进程所需要的5个资源全部得到满足，就会执行A进程的任务，执行完成后就会释放A进程占用的5个进程，释放出的资源可以用于其他的进程，这个时候也不会发生死锁，就可以完成所有的任务。因此至少需要 3 * ( 5 - 1 ) + 1 = 13 个资源。

如果有k个进程，每个进程需要n个资源，则不发生死锁至少需要的资源数为：k * ( n -1 ) + 1 。

# P31 死锁的预防和避免以及银行家算法

进程死锁的四个必要条件：

  • 互斥：如果不是互斥使用资源，则不存在死锁的问题，所有进程都可以共享资源使用。
  • 保持和等待：各个进程会保持自己的资源，并等待别的进程释放更多的资源给自己。
  • 不剥夺：系统不会把分配给某个进程的资源剥夺来给其他进程使用。
  • 环路等待：如A等B释放资源，B等C释放资源，C又等A释放资源，这样就形成了环路，相互等待，形成了环路等待。

了解到这一点后，发现解决死锁的问题，可以有两种方案：

  • 死锁的预防：死锁的预防是通过打破死锁的4个必要条件，打破互斥，打破保持与等待，进行剥夺，强制剥夺别的进程的资源。这种用得比较少，考察得不多。
  • 死锁的避免：主要由两种解决方案：如有序资源分配法和银行家算法。
    • 有序资源分配法：先给A分配资源，再给B分配资源，再给C分配资源，再给D分配资源，依次类推，这样可以发现资源的利用率比较低，更加灵活有效的方法是使用银行家算法，
    • 银行家算法：银行家算法在考试中考察频度较高。银行家算法的基本思想是以银行放贷的思路来做资源分配。对于银行家而言，他的资源就是钱，他放贷出来，他要考虑这个资源能不能按时收回来，如果评估发现这个资源（钱）放出去后收不回来，银行家就不会去放这笔贷款。
  • 银行家算法：
    • 银行家算法分配资源的原则：
      • 当一个进程对资源的最大需求量不超过系统中的资源时可以接纳该进程。
      • 进程可以分期请求资源，但请求的总数不能超过最大需求量。
      • 当系统现有的资源不能满足进程尚需资源时，对进程的请求可以推迟分配，但总能便进程在有限的时间里得到资源。
  • 系统状态：
    • 安全状态：系统能按某种顺序来为每个进程分配其所需资源，直到最大需求，使每个进程都可顺序完成，不发生死锁，则称这个顺序为安全序列，也就是系统是处于安全状态。
    • 不安全状态：不存在安全序列，也就是系统会发生死锁现象，这个就是系统处于不安全状态。

具体由一个实例来分析。

进程\资源 最大需求量 已分配资源数 剩余资源数 还需要资源数
R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3
P1 6 5 2 1 2 1 5 3 1
P2 2 2 1 2 1 1 0 1 0
P3 8 1 1 2 1 0 6 0 1
P4 1 2 1 1 2 0 0 0 1
P5 3 4 4 1 1 3 2 3 1
初始状态总计分配资源数 7 7 5
初始状态剩余可用资源数 2 1 0

说明：

  • 初始状态总计分配资源数 = 已分配资源数的和
  • 初始状态剩余可用资源数 = 总可用资源数 - 初始状态总计分配资源数
  • 总可用资源数：R1 = 9, R2 = 8, R3 = 5。
  • 初始状态即T0时刻。

我们进行一轮计算，看先执行那个进程，初始状态可用资源是：

R1 = 9 - 7 = 2

R2 = 8 - 7 = 1

R3 = 5 - 5 = 0

可以看到R3没有可用资源了，所以第1步不能执行P1/P3/P4/P5，因为这个时候这些进程都需要R3资源，仅P2不需要R3资源，需要先执行P2操作。

因此可排除A和D选项，只能在B和C选项中选择正确答案。

那么我们第1步先执行P2进程，给P2进程分配资源。P2还需要1个R2资源，把剩余可用资源R2分配给P2后，剩余可用资源为：

R1 = 2 , R2 = 0, R3 = 0。

这时进程P2顺利执行，执行完成后，释放P2占用的资源，R1 = 2 , R2 = 2, R3 = 1。

执行完成P2后剩余的可用资源数为：

R1 = 2 + 2 = 4 , R2 = 0 + 2 = 2, R3 = 0 + 1 = 1。

我们检查P1/P3/P4/P5进程，若分配R1资源，只有4个R1资源，此时不能给P1和P3分配足够的资源，因为P1还需要5个R1资源，5 > 4，P1得不到满足，会进入到不安全状态，因此C选项排除。那么只能选择B选项，正常答案是B选项。同样P3进程需要6个R1资源，6 > 4，P3也不能得到满足，即P2执行完成后不能执行P1和P3进程，相关的选项也需要排除掉。我们同样可以检查一下R2资源，P2执行完成后R2资源只剩下2个，此时P1和P5都需要3个R2资源，因些也不能执行P1和P5，因此P2->P1,P2->P5的选项也需要排除。那么P2执行完成后只能执行P4进程。

现在我们来检查一下B选项是不是一个安全序列：

进程\资源 最大需求量 已分配资源数 可用资源数 执行完当前进程剩余资源数 还需要资源数 执行顺序
R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3
P1 6 5 2 1 2 1 5 3 1
P2 2 2 1 2 1 1 2 1 0 4 2 1 0 1 0 第1步
P3 8 1 1 2 1 0 6 0 1
P4 1 2 1 1 2 0 0 0 1
P5 3 4 4 1 1 3 2 3 1

执行完成当前进程剩余资源数 = 可用资源数 + 已经分配资源数。

执行完成P2后，再执行P4进程：

进程\资源 最大需求量 已分配资源数 可用资源数 执行完当前进程剩余资源数 还需要资源数 执行顺序
R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3
P1 6 5 2 1 2 1 5 3 1
P2 2 2 1 2 1 1 2 1 0 4 2 1 0 1 0 第1步
P3 8 1 1 2 1 0 6 0 1
P4 1 2 1 1 2 0 4 2 1 5 4 1 0 0 1 第2步
P5 3 4 4 1 1 3 2 3 1

此时，再在P1、P3、P5中选择一个进程进行下一步执行，因为P3需要6个R1资源，而剩余的R1资源数5，P3得不到满足，会发生死锁问题，因此不能执行P3进程，可以执行P1或P5进程。

若先执行P1操作：

进程\资源 最大需求量 已分配资源数 可用资源数 执行完当前进程剩余资源数 还需要资源数 执行顺序
R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3
P1 6 5 2 1 2 1 5 4 1 6 6 2 5 3 1 第3步
P2 2 2 1 2 1 1 2 1 0 4 2 1 0 1 0 第1步
P3 8 1 1 2 1 0 6 0 1
P4 1 2 1 1 2 0 4 2 1 5 4 1 0 0 1 第2步
P5 3 4 4 1 1 3 2 3 1

此时，再在P3、P5中选择一个执行，若先执行P3,因为剩余资源是：R1 = 6, R2 = 6, R3 = 2,此时能满足P3的需求，若第4步执行P3,执行完成后释放资源，剩余资源数是：R1 = 6 + 2 = 8, R2 = 6 + 1 = 7, R3 = 2 + 0 =2，最后再执行P5进程，资源数也是满足的，执行完成P5进程后，剩余资源数是：R1 = 8 + 1 = 9， R2 = 7 + 1 = 8, R3 = 2 + 3 = 5。 此时资源全部被释放出来了，与可用资源数完全一样。

所以P2 -> P4 -> P1 -> P3 -> P5 是一个安全序列。同样P2 -> P4 -> P1 -> P5 -> P3也是一个安全系统。

若执行P2->P4进程后，先执行P5进程：

进程\资源 最大需求量 已分配资源数 可用资源数 执行完当前进程剩余资源数 还需要资源数 执行顺序
R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3
P1 6 5 2 1 2 1 5 3 1
P2 2 2 1 2 1 1 2 1 0 4 2 1 0 1 0 第1步
P3 8 1 1 2 1 0 6 0 1
P4 1 2 1 1 2 0 4 2 1 5 4 1 0 0 1 第2步
P5 3 4 4 1 1 3 5 4 1 6 5 4 2 3 1 第3步

执行完成P5后剩余资源数：R1 = 5 + 1 = 6, R2 = 4 + 1 = 5, R3 = 1 + 3 = 4。此时随便执行P1或P3都可以，若先执行P1，执行完成P1后剩余资源数：R1 = 6 + 1 = 7, R2 = 5 + 2 = 7, R3 = 4 + 1 = 5。最后再执行P3，执行完成P3后剩余的资源数： R1 = 7 + 2 = 9, R2 = 7 + 1 = 8, R3 = 5 + 0 = 5，与总可用资源数相同，说明全部资源都释放出来了。

因此，又可以得到两个安全序列：

P2 -> P4 -> P5 -> P1 -> P3

P2 -> P4 -> P5 -> P3 -> P1

因此，所有的安全系列有：

P2 -> P4 -> P1 -> P3 -> P5

P2 -> P4 -> P1 -> P5 -> P3

P2 -> P4 -> P5 -> P1 -> P3

P2 -> P4 -> P5 -> P3 -> P1

题目中只有B选项满足要求，所以选择B。

我们在考试的时候，只用去验证各个流程是否满足要求，不满足要求的序列就是不安全序列，可能发生死锁。

# P32 分区存储组织

存储这一块，我们之前在组成原理这个章节已经讲到了某些内容，如Cache、内存、磁盘等基本情况，下面我们从软件层面来考虑存储管理的机制。

首先看到的是不同的存储管理的分配算法。这个分配算法在是什么样的场景下进行应用的呢？

就是我们有一个存储区域，这个存储区域除了给系统用，也有给用户用的内存空间，这个空间原来是一块连接的大的空白区域，等到用户程序用时，系统就会把用户需要的大小提交到分配的组织里面去，然后给它分配需求匹配大小容量的内存，比方如作业需要33k的内存，作业2需要22k的内存，系统就给它分配22k的内存。

作业1与作业2之间为什么会间隔25k的空白空间呢？主要原因是作业1位置有个33k的程序，有可能刚好有一个程序需要25K的空间，系统就给这个程序分配了25k的内存空间，这个程序执行完成后就释放出25k的空白空间。

在这种体制当中，存储空间是动态分配的，你需要用多少，我就给你分配多少。分配过程中又要进一步考虑很细致的问题。现在我要给作业4分区内存空间，需要9k的内存，现在整个系统中有多个空间块，如25k,28k,10k，我要给作业4分配9k的空间，到底从哪个空白区位置进行切割呢？到底放在哪个区域里呢？这要由相应的算法决定。

下面看一下这几种算法：

  • 首次适应算法：系统从内存的低地址开始选择一个能装入作业的空白区。即从内存位置0处开始向高地址找第一个合适的区域，只要能装入就分配给作业空间。
    • 在我们的示例中，现在有三块可用的空白内存空间区域，内存地址从小到大排列的可用空白内存空间区域分别是25K、28K和10K，现在我们只需要9K，按首次适应算法，只需要在25K区域（25k > 9k,大小满足要求）分配一个9K内存空间出来给作业4即可，这时第1个空白区域就剩下 25 - 9 = 16K的空白内存空间区域。
  • 最佳适应算法：把系统中所有剩余的可用空白内存空间按大小顺序连成一个链，从小到大排列，首先用最小的可用空白空间与作业需要作用的内存比较，如果刚好满足（可用空间内存 >= 作业需要的内存空间），则将这个最小的内存可用空间分配给该作业。
    • 如我们示例中，内存中可用空白内存空间区域分别是25K、28K和10K，将空白区域从小到大排列连成一个链，即10K、25K、28K，然后我们需要分配9K的空间，因为最小的空白区域10K已经满足要求(10k >= 9k)，因此会在10K的空白空间分配9K的空间给作业4，剩余1K的空白空间。如果我们需要分配15K的空间，因为最小的空白区域不满足要求(10K < 15K)，因此需要在第二个最小的空间25K区域去分配空间(25K >= 15K)，这样25K的空白区域切割15K空间出来后，就剩下10K的空白空间。
    • 使用最佳适应算法能保留较大的空白区，但是存在一个缺点是随着系统不断的释放空间，可能会产生大量无法再继续分配的无用小分区（称为外碎片），如上面在10K区域分配9K给作业4后，只剩下1K的空间，这个空间太小极有可能无法再分配给其他的程序使用，就会存在碎片。
  • 最差适应算法：与最佳适应算法相反，是在所有可用空白空间中选择最大的空间来切割分配给新的作业。这种方式不容易产生外碎片。
    • 如我们示例中，内存中可用空白内存空间区域分别是25K、28K和10K，将空白区域从小到大排列连成一个链，即10K、25K、28K，然后我们需要分配9K的空间，按最差适应算法，我们需要在最大的空白空间里面进行切割，也就是在28K的区域分配一个9K的空间出来，这样分配后，28K区域的位置还剩余28 - 9 = 19K的空白空间，这样就不易产生比较小的碎片了。
  • 循环首次适应算法：把空闲的空白空间连成一个环状，每次分配都是从刚分配的空白区域开始寻找一个能满足用户要求的空白区。
    • 如我们示例中，内存中可用空白内存空间区域分别是25K、28K和10K，将这三个空白区域组成一个环状 25K --> 28K --> 10K -->25K。。。如我们依次分配了作业1、作业2、作业3的空间，，循环均匀匹配分配，由于作业3刚好在28K空间附近进行分配，我们分配作业4时就从28K空间开始分配，这是分配9K空间出来，剩余19K的空白空间。

# P33 页式存储、段式存储、段页式存储

下面我们看到的是段页式存储，段页式存储在操作系统中的应用十分的广泛。基本上现在所有的操作系统都会支持这种机制。段页式存储需要我们掌握的有：

  • 页式存储中逻辑地址与物理地址的转换。
  • 页式存储、段式存储、段页式存储的基本特点以及运作的基本方式。

# 页式存储

为什么要提出页式存储方案：之前我们讲了分区存储组织，分区化的管理，我们在内存中划定用户区域，用户区域是供用户程序调入内存时使用的，这种管理方式往往是将用户程序整体调入内存，这也就意味着，如果内存空间是4G大，用户空间2G的话，这时候如果要运行2G以上的程序就完全不可能的，甚至还不需要运行2G程序，有可能运行1G程序也可能出问题，因为在内存当中，运行的时候，空间被打碎，不是连续的空间，这时候虽然空闲空间有1个G大，但不是连接的，虽然这时候空闲区加起来有1个G大，但不能运行1个G的程序，因为这时候不能一次性装入。为了解决这个问题，我们提出了段、页式存储的基本思路。

  • 页式存储
    • 把用户程序分成等分大小的页，比如将用户程序等分为4K一个块的区域，每个4K的块称为页。把内存中存储区也划分为4K大小的若干个物理块，称为块或页框。
    • 我们要调入程序到内存中运行的时候，不再是将程序整个调入到内存当中。采取的机制是要运行哪些块，就调入哪些块，把哪些页入调入进来。这样就需要有一个页表来记录他们之间的对应（映射）关系，用户程序的多少号页对应内存当中的多少号块。
    • 采用这种方式，就可以解决掉超越内存容量的程序运行的问题。比如内存是2G，甚至可以运行4G大小的用户程序。用户要用到哪些程序页，就调入哪些程序页，已经用完的程序页，就调出内存。
    • 优点：利用率高，碎片少，分配和管理简单。
    • 缺点：增加了系统的开销，可能产生抖动现象。
    • 这种方式有多方面的优点：内存利用率高，因为我们把内存分存4K大小的块，不能利用的只是块内的某一小块空间，比如我们程序是102K，就需要分配26个页 （26 * 4K = 104K），最后一个页只有2K的程序，但分配了4K的页，就有2K的空间被浪费掉。只要是有4K大小的容量的话，基本上都会被利用上。这样一来碎片就非常少，利用率高。这是它的优点。
    • 但这种方式也有显著的缺点，缺点就在于增加了系统的开销，可以产生抖动的现象。有一个页表，页表记录了两者之前的链接关系（映射关系），也就意味着，我们要执行某个程序的时候，要定位具体的代码，需要通过查表来准确定位，不像之前是连接的空间，不需要通过映射表来调到相应的内存块，页式需要进行这种转换，转换无疑增加了系统的开销，先读取页表，再读取页表的页号查找块号，这样就耗时一些。可能产生抖动现象（分配较多资源时，出现缺页的可能性可能更大）。
    • 在页式存储中考察得比较多的是逻辑地址与物理地址之间的转换。
    • 逻辑地址与物理地址之间很多地方是相同的，比如页内地址是一样的！页号不一样，逻辑地址的页号对应物理地址的块号，一般是不相等，但可以做到相等，如0号页对应0号块，1号页对应1号块。也可以做到不相等，如0号页对应2号块之类的。因为没有严格的限制。页号和块号需要通过查表来得知。至于页内地址是一样的，因为调入的时候是以页为单位，以页为单位的偏移量不会有变化。
    • 要如何通过逻辑地址来求物理地址呢？首先要知道逻辑地址哪一部分是页号哪一部分是页内地址。知道哪一部分是页号，哪一部分是页内地址，则直接将页内地址记录下来，是物理地址的页内地址(A，然后通过页号在页表中查找对应的块号(B)，最后将查找到的块号与页内地址拼接(BA)起来就可以了，就样就得到了物理地址。

下面看一个示例，来看一下逻辑地址与物理地址之间的转换：

我们来看一下分析过程，分析如下：

要求物理地址，首先要将逻辑地址中的页号与页内地址分开，如何分开呢？我们要通过页面大小（4K）参数来分析得知，页面大小4K，4K写成二进制，4K = 4 * 2^10 = 2^12，表示2的12次方，对应有12个2进制位，说明页内地址是12位，高于12位的就是页号，二进制每四个位对应一个十六进制位，一个十六进制位对应4个二进制位。所以12个二进制位就对应3个十六进制位，即对应5A29H中的A29，注意十六进制最后的H不参入计算，H用来表示是十六进制，因此页内地址就是A29，页号是5。可以看到备选答案中，末3位都是A29，就说明页内地址不需要我们求的。页号是5，对应的物理块是是多少呢？物理块号有多种叫法，有时候又叫它页帧号，所以通过查表可知逻辑块号5对应的物理块号是6，因此最后拼接后的物理地址是6A29H，因此选择D。

如果进程P要访问的页面4不在内存里面，那么应该淘汰哪个页面呢？淘汰只能淘汰在内存的页面，状态位表示在不在内存中，状态位为1表示在内存中，即页面0、1、2、5在内存中，只能从这几个页面中选择一个进行淘汰。选择哪一个淘汰，则需要看访问位，访问位为1的不能被淘汰，只有访问位是0的才能被淘汰，因为刚刚被访问过的有可能会被程序继续访问到（程序局部性原理）。因为只有1号页面的访问位是0，所以我们淘汰1号页面，因此选择B。

# 段式存储

段式存储包括段号和段内地址两个部分。

这样子看起来，觉得与页式存储好像是一样的，只是把名字改了一下。实际上不是这么回事。

段式和页式存储的分隔方式有较大差别。

段式存储是按逻辑结构来进行划分的。意思就是一个程序当中，会将main主函数做为一个段，function1做为一个段，function2做一个段，...，段的大小不要求一致，有的段是40K，有的段是80K,有些是150K...，这都是可以的。但这在页式存储中是不允许的，规定的页是4K大小的话，每个页就只能是4K大小，不能有区别。而段式存储中段就没有这个限制，可以有区别，有的段长，有的段短。

按段式逻辑来划分，最大的好处就是便于共享。

相对来话，内存利用率低一些，内存碎片浪费大一些，因为要按段的大小在内存中切相应的区块来完成任务。

段表存的是段号、基地址，段长。 基地址称为基地，指这个段是从内存中哪个地址开始，即起始地址。

# 段页式存储

段页式存储是将页式存储和段式存储结合起来，先分段，再分页，是典型的中庸之道的产出，它的优点是集合了段式存储和页式存储的优点。

优点：空间浪费小，存储共享容易。

缺点：增加了软件的复杂度，开销增大，速度降低。因为要先查段表，然后再查页表。

# 快表

快表是一块小容量的相联存储器（按内存存储，速度非常快，效率非常高），由高速缓存器组成（即快表放在Cache中），速度快，并且可以从硬件上保证按内容并行查找，一般用来存放当前访问最频繁的少数活动页面的页号。

查找联想存储器和查找主存页表是并行进行的，一旦在联想存储器（即相联存储器）中找到相符的逻辑页号，就停止在查找主存页号。

相对来说，将页式存储中页表、段式存储的段表放在内存中，这种称为慢表。

# P34 页面淘汰算法

页面置换算法广泛应用于分层存储体系当中。比如之前讲的cache,cache数量有限，当cache数据块都被占用了，要调入到新的块进来时，就要涉及到页面置换的问题。在内存体系这一块也一样，同样页面这样的问题。比方如页式存储当中，一个程度有100个，但是内存可以分配的页是有限的，比方只有3个页，这个时候就不可避免的在程序运行过程中，要把不用的页调出来，把现在需要用到的页调入进去。这要依据一定的算法进行识别，哪些页淘汰是比较好的，这就涉及到页面淘汰算法。

页面淘汰算法，比较有代表性的有以下几种：

  • 最优（Optimal，OPT）算法
  • 随机（Random）算法
  • 先进先出（FIFO）算法，有可能产生抖动现象。例如，432143543215序列，使用3个页面比用4个页面缺页次数少。
  • 最近最少使用（LRU）算法。不会产生抖动现象。

这几种算法，在考试中比较容易出现的是先进先出算法和最近最少使用算法。

因为前面两种算法：

  • 随机算法随机的淘汰一个，性能是不稳定的。
  • 最优算法，是一种理论层面的页面淘汰算法， 是在整个事件发生之后，即我们知道我们的访问的系列是怎么样的，而且根据系列来分析算出在什么时间点淘汰什么页面能够取得最高的效率性能，就把这个作为最优算法。它针对每个实际场景，最优算法往往是不一样的，没有普遍的规律。而且由于在实际使用过程中，往往没有办法从整体上面来了解需要访问的页面顺序到底是怎么样的，因为比如说，涉及到分支，需要根据条件来判断，不知道下一个页面到底要访问哪一个，整个完整的系列是排不出来的。所以最优算法，在实际应用中，是没有办法直接应用的。它的应用方式是怎么样的呢？就是把最优的写出来，再把它与其他算法方案对比，看看其他算法的差距有多大，往往是起到这样的作用，用来评估其他算法。

需要重点关注的算法：

  • 先进先出算法：First In First Out，先进先出的基本思路很简单，要淘汰内存页面时，看哪个页面最先进入内存，最先进入内存的页面最先被淘汰。先进先出算法有可能产生抖动现象：分配更多的资源，希望将事件做得更好，但实际上有可能效率降低了，缺页次数变多，如示例中当分配的物理块从3块增加到4块时，有缺页次数增加，缺页率提高的异常的现象。
  • 最近最少使用算法：Least Recently User，最近最少使用算法不会产生抖动现象，分配的资源越多，表现的性能越好。刚刚被访问的不会被淘汰出去，由于存在局部性原理，刚刚被访问到的页面有可能马上又会被访问到，因此不会被淘汰。

下面看示例。

首先，看一下先进先出算法：

表中第一行代表需要访问的页面资源序列，第一列代表内存中的三个物理块页面，首先这三个物理块是空的。

物理块\页面资源序列 4 3 2 1 4 3 5 4 3 2 1 5
1
2
3
是否产生缺页

刚开始是这样的，1、2、3物理块都是空的，要访问4号页面资源，由于内存物理块中没有4号页面资源，产生一次缺页，我们将4号页面资源放到物理块1中，放入后表中数据如下：

物理块\页面资源序列 4 3 2 1 4 3 5 4 3 2 1 5
1 4
2
3
是否产生缺页 Yes

然后，我们需要访问3号页面资源，由于内存物理块中没有3号页面资源，产生一次缺页，我们将3号页面资源放到物理块2中，放入后表中数据如下：

物理块\页面资源序列 4 3 2 1 4 3 5 4 3 2 1 5
1 4 4
2 3
3
是否产生缺页 Yes Yes

然后，我们需要访问2号页面资源，由于内存物理块中没有2号页面资源，产生一次缺页，我们将2号页面资源放到物理块3中，放入后表中数据如下：

物理块\页面资源序列 4 3 2 1 4 3 5 4 3 2 1 5
1 4 4 4
2 3 3
3 2
是否产生缺页 Yes Yes Yes

接着我们需要访问1号页面资源，这时候内存物理块中没有1号页面资源，产生一次缺页。这个时候三个内存物理块都被占用了，为了能够访问1号页面资源，必须要淘汰一个页面用于存放1号页面资源。根据先进先出算法，先进入内存的页面先被淘汰。我们知道4号页面资源先进入到内存中并放到物理块1中，因此我们需要将物理块1上面的4号页面资源淘汰掉，然后把1号资源装入到1号物理块中，放入后表中的数据如下：

物理块\页面资源序列 4 3 2 1 4 3 5 4 3 2 1 5
1 4 4 4 1
2 3 3 3
3 2 2
是否产生缺页 Yes Yes Yes Yes

接着我们需要访问4号资源，可以看到我们刚把4号资源淘汰后又要访问4号资源，这就是一个问题。我们接着按先进先出算法来淘汰一个页面。现在内存物理块中存在1号、3号、2号页面资源，3号页面是先进入到内存中，因此要淘汰2号物理块上面的3号页面资源，并把4号页面资源存放到2号物理块中，放入后表中的数据如下：

物理块\页面资源序列 4 3 2 1 4 3 5 4 3 2 1 5
1 4 4 4 1 1
2 3 3 3 4
3 2 2 2
是否产生缺页 Yes Yes Yes Yes Yes

接着我们需要访问3号资源，可以看到我们刚把3号资源淘汰后又要访问3号资源，这就是一个问题。我们接着按先进先出算法来淘汰一个页面。现在内存物理块中存在1号、4号、2号页面资源，2号页面是先进入到内存中，因此要淘汰3号物理块上面的2号页面资源，并把3号页面资源存放到3号物理块中，放入后表中的数据如下：

物理块\页面资源序列 4 3 2 1 4 3 5 4 3 2 1 5
1 4 4 4 1 1 1
2 3 3 3 4 4
3 2 2 2 3
是否产生缺页 Yes Yes Yes Yes Yes Yes

接着我们需要访问5号资源，我们接着按先进先出算法来淘汰一个页面。现在内存物理块中存在1号、4号、3号页面资源，1号页面是先进入到内存中，因此要淘汰1号物理块上面的1号页面资源，并把5号页面资源存放到1号物理块中，放入后表中的数据如下：

物理块\页面资源序列 4 3 2 1 4 3 5 4 3 2 1 5
1 4 4 4 1 1 1 5
2 3 3 3 4 4 4
3 2 2 2 3 3
是否产生缺页 Yes Yes Yes Yes Yes Yes Yes

接着我们需要访问4号资源，由于4号页面资源在2号物理块中，可以直接访问，不会产生缺页，访问4号页面数据如下：

物理块\页面资源序列 4 3 2 1 4 3 5 4 3 2 1 5
1 4 4 4 1 1 1 5 5
2 3 3 3 4 4 4 4
3 2 2 2 3 3 3
是否产生缺页 Yes Yes Yes Yes Yes Yes Yes No

接着我们需要访问3号资源，由于3号页面资源在3号物理块中，可以直接访问，不会产生缺页，访问3号页面数据如下：

物理块\页面资源序列 4 3 2 1 4 3 5 4 3 2 1 5
1 4 4 4 1 1 1 5 5 5
2 3 3 3 4 4 4 4 4
3 2 2 2 3 3 3 3
是否产生缺页 Yes Yes Yes Yes Yes Yes Yes No No

接着我们需要访问2号资源，现在内存物理块中存在4号、3号、5号页面资源，此时内由于2号页面资源不在内存中，产生一次缺页，4号页面是先进入到内存中，因此要淘汰2号物理块上面的4号页面资源，并把2号页面资源存放到2号物理块中，访问2号页面数据如下：

物理块\页面资源序列 4 3 2 1 4 3 5 4 3 2 1 5
1 4 4 4 1 1 1 5 5 5 5
2 3 3 3 4 4 4 4 4 2
3 2 2 2 3 3 3 3 3
是否产生缺页 Yes Yes Yes Yes Yes Yes Yes No No Yes

接着我们需要访问1号资源，现在内存物理块中存在3号、5号、2号页面资源，此时内由于1号页面资源不在内存中，产生一次缺页，3号页面是先进入到内存中，因此要淘汰3号物理块上面的3号页面资源，并把1号页面资源存放到3号物理块中，访问1号页面数据如下：

物理块\页面资源序列 4 3 2 1 4 3 5 4 3 2 1 5
1 4 4 4 1 1 1 5 5 5 5 5
2 3 3 3 4 4 4 4 4 2 2
3 2 2 2 3 3 3 3 3 1
是否产生缺页 Yes Yes Yes Yes Yes Yes Yes No No Yes Yes

接着我们需要访问5号资源，由于5号页面资源在1号物理块中，可以直接访问，不会产生缺页，访问5号页面数据如下：

物理块\页面资源序列 4 3 2 1 4 3 5 4 3 2 1 5
1 4 4 4 1 1 1 5 5 5 5 5 5
2 3 3 3 4 4 4 4 4 2 2 2
3 2 2 2 3 3 3 3 3 1 1
是否产生缺页 Yes Yes Yes Yes Yes Yes Yes No No Yes Yes No

因此可以看到，访问12次页面资源，产生了9次缺页，缺页率f = 9 / 12 = 75%。

如果我们有4个物理块的话，看看先进先出会产生多少次缺页。

按上面3个物理块资源的方式我们一次性的计算出访问各页面资源序列是否缺页：

物理块\页面资源序列 4 3 2 1 4 3 5 4 3 2 1 5
1 4 4 4 4 4 4 5 5 5 5 1 1
2 3 3 3 3 3 3 4 4 4 4 5
3 2 2 2 2 2 2 3 3 3 3
4 1 1 1 1 1 1 2 2 2
是否产生缺页 Yes Yes Yes Yes No No Yes Yes Yes Yes Yes Yes

可以看出，访问12次页面资源，产生了10次缺页，只有2次没有缺页，缺页率f = 10 / 12 = 83.3%。

注意，我这边表中的填写内容与老师给的表有些区别，老师的表中在淘汰页面时，会将内存中未被淘汰的页面重新放到1号和2号物理块上，再把新添加的页面资源放到3号物理块上。而我上面的计算过程时，并没有对未被淘汰的页面进行重排，而是直接将被淘汰的页面资源去掉，并在相应的物理块上面存入新的页面资源。

可以看出，当分配的物理块从3块增加到4块时，缺页次数增加(从9次增加到10次了)，缺页率提高了(从75%提高到83.3%)。这种异常现象就是抖动现象。

下面我们也可以按最近最少使用算法来对访问上面的页面资源序列，先看看分配3块物理块，然后增加1块物理块，看看它们的缺页次数和缺页率。

最近最少使用算法：Least Recently User，淘汰掉最近最少使用的那个页面资源。

序号 1 2 3 4 5 6 7 8 9 10 11 12
物理块\页面资源序列 4 3 2 1 4 3 5 4 3 2 1 5
1 4 4 4 1 1 1 5 5 5 2 2 2
2 3 3 3 4 4 4 4 4 4 1 1
3 2 2 2 3 3 3 3 3 3 5
是否产生缺页 Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes

对比先进先出3个物理块时候的缺页情况：

序号 1 2 3 4 5 6 7 8 9 10 11 12
物理块\页面资源序列 4 3 2 1 4 3 5 4 3 2 1 5
1 4 4 4 1 1 1 5 5 5 5 5 5
2 3 3 3 4 4 4 4 4 2 2 2
3 2 2 2 3 3 3 3 3 1 1
是否产生缺页 Yes Yes Yes Yes Yes Yes Yes Yes Yes No

可以发现访问前面的1-9号页面资源时，先进先出和最近最少使用算法的淘汰页面是一样的，但访问第10个页面资源时，对于先进先出算法，由于2号物理块上面的4号资源是最先进入内存的，所以会淘汰2号物理块上面的4号资源，并将2号页面资源存入到2号物理块中。而最近最少使用算法就不一样了，由于我们的第8个页面资源访问的是4号页面资源，第9个页面资源访问的是3号页面资源，第7个页面资源访问的是5号页面资源，现在要访问2号页面资源，可以看到5号页面资源访问后过去的时间最长，因此要淘汰1号物理块上的5号页面资源，将2号资源存放到1号物理块上，这样就看出了两种算法的不同点。

我们计算一下，3个物理块时，最近最少使用算法的缺页和缺页率情况：

访问12次页面资源，产生了9次缺页，缺页率f = 9 / 12 = 75%。此时和先进先出的缺页率相同。

我们增加一个物理块，再看一下最近最少使用算法的缺页和缺页率情况：

序号 1 2 3 4 5 6 7 8 9 10 11 12
物理块\页面资源序列 4 3 2 1 4 3 5 4 3 2 1 5
1 4 4 4 4 4 4 4 4 4 4 4 5
2 3 3 3 3 3 3 3 3 3 3 3
3 2 2 2 2 5 5 5 5 1 1
4 1 1 1 1 1 1 2 2 2
是否产生缺页 Yes Yes Yes Yes Yes Yes Yes Yes

可以看出，访问12次页面资源，产生了8次缺页，有4次没有缺页，缺页率f = 8 / 12 = 66.7%。可以看到，当物理块数增加1后，最近最少使用算法的缺页率降低了。

我们再增加一块物理看一下最近最少使用算法是不是缺页率还会下降：

序号 1 2 3 4 5 6 7 8 9 10 11 12
物理块\页面资源序列 4 3 2 1 4 3 5 4 3 2 1 5
1 4 4 4 4 4 4 4 4 4 4 4 4
2 3 3 3 3 3 3 3 3 3 3 3
3 2 2 2 2 2 2 2 2 2 2
4 1 1 1 1 1 1 1 1 1
5 5 5 5 5 5
是否产生缺页 Yes Yes Yes Yes Yes

可以看出，增加物理块妻5块时，访问12次页面资源，产生了5次缺页，有7次没有缺页，缺页率f = 5 / 12 = 41.7%。可以看到，当物理块数增加1后，最近最少使用算法的缺页率又降低了。

注意，如果只需要访问1号至5号页面资源，如果再增加物理块的个数，缺页率不会再下降，必定有5次缺页，因为刚开始1、2、3、4、5号页面资源都不在内存中，就会产生5次缺页，后面再新增物理块的话，这几个页面都在内存当中了，新增的物理块对这几个资源没有用，不会再降低缺页率了。

# FIFO先进先出算法与LRU最近最少使用算法的区别

我们来看一下上图中的两种算法的缺页数和缺页率情况。

算法 序号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
FIFO 物理块\页面资源序列 5 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 5 0 1
1 5 5 5 2 2 2 2 4 4 4 0 0 0 0 0 0 0 5 5 5
2 0 0 0 0 3 3 3 2 2 2 2 2 1 1 1 1 1 0 0
3 1 1 1 1 0 0 0 3 3 3 3 3 2 2 2 2 2 1
是否产生缺页 Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes
淘汰页面号 5 0 1 2 3 0 4 2 3 0 1 2

最近最少使用算法：

算法 序号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
LRU 物理块\页面资源序列 5 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 5 0 1
1 5 5 5 2 2 2 2 4 4 4 0 0 0 1 1 1 1 1 1 1
2 0 0 0 0 0 0 0 0 3 3 3 3 3 3 0 0 0 0 0
3 1 1 1 3 3 3 2 2 2 2 2 2 2 2 2 5 5 5
是否产生缺页 Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes
淘汰页面号 5 1 2 3 0 4 0 3 2

可以看到，两种算法淘汰的页面号不一样，FIFO算法缺页15次，LRU算法缺页12次，一共访问了20次页面，FIFO算法的缺页率f = 15/20 = 75%，LRU算法的缺页率f = 12/20 = 60%。

# P35 页面淘汰算法练习题

在考试中认同的是这种标准。我们需要按照这种标准来计算。

系统中没有使用快表，是一种暗示提示，说明每读一次程序的块需要先在内存中查询一下表，查询表后才能读取内存块，所以每一块要进行2次对内存的访问，总共有6个块，需要2*6=12次对内存的访问。第1题选B。

注意，缺页中断的计算，这里需要注意，指令无论它占用几个块（页），也是一次性读取整个指令，只产生一次缺页中断。如swap指令是跨了两个页面，swap指令存放在内存的1023单元中，1个K为一个块，1个单元就是一个字节，第一个块是从0个字节到1023字节，1023字节是0号块最后一个单元，只能存指令的一半，还有一半存放在1号块的第个单元当中。跨两个页按常规情况会产生2次缺页中断，但实际上，指令会一次性读入，只产生一次缺页中断。

而对于数据类型的操作数，会产生两次缺页中断。如操作数A在2号页中有一半，在3号页中有一半，在上半部分会产生一次缺页中断，下下半部分也会产生一次缺页中断。所以可以发现总的缺页中断次数是：1 + 2 + 2 = 5次。第2题选C。

因此，在考试中无论认不认同，都要按这种规则来计算，即：

指令存在跨页情况时，是一次性全部读入内存，只产生一次缺页中断。操作数按其跨页次数计算中断数，跨页几个产生几个缺页中断。

# P36 索引文件结构

  • 索引文件结构是一种非常巧妙的文件结构，因为这种结构本身的容量很有限，如果不做扩展的话，文件容量很有量，但是引入了扩展后，可以使容量扩大很多倍。
  • 一般的索引文件结构有13个索引节点。在考试时如涉及到不是13个标准节点，则会说明节点情况。如果没有说明，则使用标准的13个节点的标准索引节点。
  • 在索引文件结构当中，分成了直接索引，一级间接索引，二级间接索引，三级间接索引等情况。
  • 分几级间接索引，主要是考虑到文件本身的容量扩展问题。
    • 比方如，一个物理盘块假设是4K的大小，假设13个块都是直接索引，则文件最大为4K*13 = 52K， 这个容量太小。
  • 规定0-9号索引结点是直接索引，即前10个节点进行直接索引，直接存放索引文件内容。
    • 直接索引可存放容量为 4K * 10 = 40K。
  • 10号索引结点，指向的物理盘块，不再是索引文件内容，而是物理盘块的地址。
    • 假设每一个物理盘块占4个字节，则10号节点可以存放4K/4b = 1024个物理盘块的地址，所以一级间接索引可以存放4K * 1024 = 4M大小的容量。
  • 11号索引结点，进行二级间接索引，来扩展容量。
    • 二级间接索引容量就就变成了 4K * 1024 * 1024 = 4G 大小的容量。

例题。

50号物理块号对应的逻辑块号是0，67号物理块号对应的逻辑块号是1，68号物理块号对应的逻辑块号是2，78号物理块号对应的逻辑块号是3，89号物理块号对应的逻辑块号是4。

从90号物理块号开始就不是直接存储逻辑块了，而是间接索引，90空间指向的物理盘块指向的物理块从58号-136号，5号逻辑块存放在58号物理块上。

因为磁盘数据块大小是1KB，而每个地址项大小为4字节，所以90空间可以存放1kB/4b = 1024/4 = 256个地址项，所以90号物理块上逻辑块号从5号开始，后续256-1个地址项，也就是从5号开始，5+256-1 = 260号逻辑块，所以136号物理块存放的是260号逻辑块。

因此要从91号物理块号开始上261号逻辑块，90号物理块号是一级间接索引，指向187号-129号物理块，因此261号逻辑块存放在187号物理块上，因此第1题选C。

101号物理块对应的是iaddr[7]二级间接地址索引表，第2师选D。

# P37 树形目录结构

不仅在计算机中使用相对路径和绝对路径，在实际生活中也会使用相对路径和绝对路径，如拨打电话☎️，打电话时可以加区号或者不加区号，不考虑中国以外地区的话，仅在国内，加区号就是绝对路径，不加区号就是相对路径。

# P38 位示图法

空闲存储空间的管理：在磁盘上有大量的存储空间，我们需要把这些空闲的空间管理起来，以便在某一个文件需要申请存储空间的时候，能够有依据地分配给它相应的空间。空闲存储管理有以下几种方法：

  • 空闲区表法（空闲文件目录）：可以用一个表记录哪些地方是空闲的。
  • 空闲链表法：把空闲区都链接起来，分配的时候从链表中划出相应的空间。
  • 位示图法：需要重点掌握的。
  • 成组链接法：即分组又分链。

位示图法：先画一个位示图，1表达的区域表示已经被占用，0表示的区域表示没有被占用，是空闲的。我们把整个的存储空间分为多个物理块，就可以直观的看出哪些物理块被占用，哪些物理块是空间。

实际生活中，电影院卖座位也应用了位示图法，如红色座位表示已经卖出的座位，绿色或空间座位表示还没有被卖出的座位。买飞机票或火车票也会使用位示图法。

示例分析：

1个字是32位，4195号物理块对应第4196个物理块，因为物理块是从0号开始编号的。

所以可以使用 ( 4195 + 1) / 32 = 131.125， 说明要把前面131个字填满，并且当前物理块处于第132个字中。因此在132个字中，第1题选D。

第131个字： 131 * 32 = 4192，因此从第1个字（注意，第几个字是从1开始编号的，不是从0开始编号的）到131个字可以表示第0号物理块到第4191号物理块。

在第132个字中：

第0位置：对应4192号物理块，

第1位置：对应4193号物理块，

第2位置：对应4194号物理块，

第3位置：对应4195号物理块，

因此将4195号物理块分配给某文件时，需要将第132个字的第3位置为1，1表示占用。第2题选B。

需要注意的是：

  • 第多少字是从0还1开始算？从1开始算，第1个字，第2个字。
  • 第多少位是从0还是1开始算？从0开始算，第0位，第1位，第2位等。

# P39 数据传输控制方式

  • 设备管理-数据传输控制方式，主要是指内存和外设之间的数据传输控制问题，解决这一问题，有几种方案可以选择，包括：

    • 程序控制方式
    • 程序中断方式
    • DMA方式
    • 通道
    • 输入输出处理机

    其中的通道和输入输出处理机需要专用的计算机来解决程序控制方式，一般不在讨论范围之内，主要考虑前面三种控制方式。

  • 程序控制方式：又被称为程序查询方式，这种方式是最低级的，也是CPU介入最多的机制，整个数据传输控制，很多时候需要cpu的介入，在这种方式中，外设处于一种非常被动的方式，它不会主动的反馈信息，比如传输完成没有，情况怎么样，而是由CPU发出查询指令，查询有没有传输完成，没有传输完成继续传输，传输完成了就继续下一步的工作。类似于给员工分配一个任务，你要经常去问他有没有完成工作，刚开始问的时候他一直说没有完成，你就做别的事情去了，你再次来问他工作完成没有，他就告诉你他老早就完成了工作，这必然会带了一些问题。这样后来就出来了程序中断方式。

  • 程序中断方式：与程序控制方式一样，但是更主动，如果外设完成了相应的数据传输任务，就发出一个中断出来，系统就会就下一步的处理，这样效率就比程序查询方式高一些。

  • DMA方式：又称为直接存储控制方式，思路：有专门的DMA控制器，只要是外设和内存之间的数据交换，过程中间由DMA控制器管控，CPU只用在开头的时候介入，如安排好事务，初始化等，整个过程由DMA控制器来完成、处理、监管，完成之后再由CPU接手过来，做后续的操作，这样效率就提高很多。

# P40 设备管理-虚设备和SPOOLING技术

  • 虚设备和SPOOLING技术使用一个实例来说明即可，大家理解一下基本原则即可。

如A/B/C/D四个人在不同的方式连接到远程的打印机，打印机放在打印房里的。我们知道打印机在同一时刻只能服务一个用户，不能说四个人打印资料，一人打印一页，一页A的，一页B的，一页C的，一页D的，这样子不行，必须时先把一个任务打印完成了后再打印别的。这个时候共用打印机资源就会产生一个问题，我在打印资料的时候，发布打印指令，结果有可能提示‘"打印机正在使用！！"，我等10分钟再去打印，又提示"打印机正在使用！！"，我又等10分钟再去打印，又提示"打印机正在使用！！"，而实际上我们发现打印机利用率其实并没有那么高，可能刚好你要打印的时候，别人正在打印，就会提示打印机正在使用，这个时候外设利用率非常低。因此就提出了SPOOLING技术。

SPOOLING技术是怎么做的呢？

SPOOLING技术应用非常广泛，打印机上面就应用了这种技术。A,B,C,D都要打印，在打印机这边会有相应的控制程序做打印的管控，管控的时候会先把相应的需要输出的内容放到磁盘的缓冲区，进入到输出井，完成之后，打印机会顺次打印输出井里面的数据内容。即你在打印的时候不会提示你打印机正在使用，而且进度表已经过去了，等打印机把前面的任务打印完成就会开始打印你的打印任务。所以说通过加入SPOOLING技术，使用过程变得更加友好，你可以随时点击打印，打印完成后只用去打印房拿资料就可以了，不会老是出来冲突的问题。

SPOOLING技术的核心就在于开辟了缓冲区，让需要输出、输入的数据先缓存起来，这样解决了外设的低速和内部系统高效之间的瓶颈差异，一般系统都内置了SPOOLING技术。因为像打印的话不仅与其他用户有冲突，自己打印多个文档的时候也会产生冲突，比如打印文档A 100页，再打印文档B就会提示设备已经占用，有了SPOOLING技术后就不会提示打印机占用，打印会显示打印队列，打印机顺次处理。

SPOOLING技术在磁盘上开辟缓冲区，解决速度之间的差异。

# P41 微内核操作系统

  • 微内核操作系统

微内核操作系统就是把内核做得更小的操作系统。

为什么要将操作系统的内核做得更小呢？必然是有它的好处优势的。好处优势主要体现在：微内核操作系统的可靠性、稳定性、安全性更高。

操作系统作为核心的系统软件，如果操作系统出现了故障，就会影响整个系统的正常运行，如果把操作系统内核做得小一些，就会降低这种问题发生的概率，把最为核心的放在内核里，只有这一小块的东西出故障才会产生根本性的影响，而原来放在操作内核里的抽离出去，作为其他的外接系统，这些系统即使出现故障问题，我们只需要去重启这一小块的功能部件的东西，就能解决这个问题，比如把图形系统，文件系统，设备驱动等放在内核之外，假设文件系统崩溃，对于微内核系统而言，没有关系，只用将文件系统重启一下即可，不用重启整个系统；如果是单体内核系统，如果文件系统出现故障了，那就表现为整个系统出现问题了，比如以前用到的XP系统经常蓝屏，就是内核出现问题，当把内核缩小了，这种问题的概率就大大的降低了。

具体查看表中的内容，主要了解这种思想。

内核类型 实质 优点 缺点
单体内核 将图形、设备驱动及文件系统等功能全部在内核中实现，运行在内核状态和同一地址空间。 减少进程间通信和状态切换的系统开销，获得较高的运行效率。 内核庞大，占用资源多且不易剪裁。系统的稳定性和安全性不好。
微内核 只实现基本功能，将图形系统、文件系统、设备驱动及通信功能放在内核之外。 内核精练，便于剪裁和移植。系统服务程序运行在用户地址空间，系统的可靠性、稳定性和安全性较高，可用于分布式系统。 用户状态和内核状态需要频繁切换，从而导致系统效率不如单体内核。

微内核操作系统中分用户态和核心态，核心态是微内核里面内核运行的情况，用户态是核心态之外去运行的，也就是说，在用户态出现的故障都没有关系，都可以通过一定的处理方式来解决，但核心态出现故障就会比较严重。用户态和核心态之间会有交互，普通的东西在用户态处理，只有到了非常关键的部分才到核心态里面去处理，就是和系统内核紧密关联的才在核心态处理。

上面的图需要记住哪些态是在核心态，哪些是在用户态。

# P42 数据库系统前言

数据库系统主要涉及以下内容：

  • 数据库模式
  • ER模式
  • 关系代数和元组演算，每次上午题都会考。
  • 规范化理论
  • 并发控制
  • 数据完整性约束
  • 分布式数据库
  • 数据仓库与数据挖掘

# P43 数据库三级模式两级映射

一般以选择题形式出现。

三级模式两级映射这种设计是层次型架构设计，这种层次型架构设计为我们在应用数据库时提供了很多方面的便利，同时也让整个体系的可维护性、应变能力变得更好一些。

三级模式两级映射到底是什么回事？

  • 最底层是物理数据库，说白了物理数据库在计算机上面表现形式是一个文件，如数据库文件日志文件等。
  • 内模式是与物理层次的数据库直接关联的，内模式管理如何去存储一系列的数据，数据需要存储到物理文件上，按什么格式存储，如何去优化它，主要关注数据的存放。
  • 概念模式，其实就是平时用数据库中表这一级，将数据分成若干个表，这些表是根据业务、应用划分的，表之间会存在关联。
  • 外模式，对应数据库的视图，外模式的应用，使对数据的控制有更进一步的手段更加灵活的处置方式。对表进行相应的操作，得到不同的视图。表发生变化，只需要改表映射，不需要去改变应用程序。

# P44 数据库设计过程说明

需要了解数据库整个设计过程流程是怎样的？每一个阶段会有不同的产出物。

  • 需求分析：需求分析是看整个系统对数据这一块有什么样的要求，有从用户那里收集过来的，同时由转换过程中产生的一些需求，关联的一些需求，在这一个阶段，需要有数据流图、数据字典、需求说明书等产物，严格来说，需求分析是上一个阶段需求阶段的任务，而数据库设计具体应从概念结构设计开始。
  • 概念结构设计：就是做E-R模型，ER模型与数据库管理系统没有关系的模型，ER模型做出来后，你可以用Access,MYSQL等等数据库，ER模型这一层与物理数据库没有直接的关系。就是一种数据的表达，看数据的实体会有哪些属性，看实体之间会有什么样的联系，分析这些方面的问题。接着需要将E-R模型转换成关系模式。
  • 逻辑结构设计：E-R模型转换成关系模式是转换成文字表达一个一个表的形式，在转换过程中就涉及到规范化理论，规范化理论是必考的知识点，产出物是关系模式。
  • 物理设计：有了关系模式后，进一步把数据库管理系统的特性融入进入，比如说不同的数据库管理系统类型可能不同，在设计的时候值得注意和考虑，形成物理层次的设计。

这是整个数据库的设计流程。

# P45 E-R模型

  • 以方框表示实体，如学生实体，课程实体。
  • 以椭圆表示属性，如学生实体有学号、姓名、性别、年龄等属性，课程实体有课程号、任课教师、课程名等属性。
  • 以菱形表示联系，学生与课程之间会有联系，一个学生可以选不同的课程，一门课程又可以被多个学生选择，是多对多的关系。

在进行E-R图的设计过程中，往往需要分析每一个局部的E-R该如何设计和绘制，因为从整体的角度，一个庞大的系统ER图一次性绘制出来，难道比较高，风险比较大，所以一般是先画局部的ER图，然后再把局部的ER图一步一步的合成起来，形式全局的ER图。

在将多个局部ER图合成时，又可以选择不同的集成的方法：

  • 逐步集成：首先将两个局部集成在一起，再与另外一个集成，这样耗时一些，但简单一些，不容易出错。
  • 多个局部图一次集成：有可能会出现一些问题，难以发现。

在集成的过程中还会面临一个问题就是冲突问题，就是两个图不一致的情况。

在集成的过程中会产生的冲突及解决办法：

  • 属性冲突：包括属性域冲突和属性取值冲突。如教师表，有的系统设计性别为男/女，有的系统设计性别为逻辑值如T/F，这样属性值就会有差异。
  • 命名冲突：包括同名异义和异义同名。如教师在学生表里面写的是老师，而在教职工表里面写的是职工，所以同样的意思在不同系统中命名不一样就可能产生问题。
  • 结构冲突：不同抽象级别的问题。如老师即一个表，也可能是另外一个系统中的一个列。这样也可能产生问题。

# E-R模型转关系模式

  • 一个实体型转换成一个关系模式：

    • 1对1联系(1:1)：每个实体可以转换成一个关系模式，可以把联系单独转换成一个关系模式，这样就是3个关系模式； 也可以把联系记录在实体上，这样就是2个关系模式，所以1对1联系至少可以转换为2个关系模式。如实体A转换成一个关系模式，实体B转换成一个关系模式，可以将中间的菱形◇联系单独的转换成一个关系模式，也可以将菱形◇联系合并到与之关系的任意一个实体里面，即关系即可记录在实体A里面，也可以记录在实体B里面，这样1对1联系至少可以转换为2个关系模式。
    • 1对多联系(1:n)：每一个实体需要转换成一个关系模式，可以将中间的联系单独转换成一个关系模式（这种做法可以，但不是必须的），也可以将联系记录在n（多的一端）端。如果记不住，可以使用员工与部分的关系来记忆，如A是部门，B这边是员工，部门和员工是1对多关系，即一个部门有多个员工，一个员工只能属于一个部分，关系只能记录在员工这边，只用在员工表里面加上部门号就可以解决，就可以对应到相应的部门； 反过来就不行，如在部门中加上员工号，有的部门人比较少，可能只有两个，就要写两个员工号进去，部门人员多的，有几百个，把它添加到同一条记录里面，这时候就没办法添加了，所以说在员工这一边加上部门号是比较好的方案。所以一对多的关系中，至少可以转换成2个关系模式。
    • 多对多联系(m:n)：多对多有一个现成的实例，如学生与课程之间就是多对多的关系，学生实体可以选择多个课程，课程实体也可以被多个学生选择，学生实体需要转换成一个关系模式，课程实体也需要转换成一个关系模式，选课联系必须转换成一个关系模式，所以对于多对多的关系中，至少需要转换成3个关系模式。

    对于上图中的示例，A/B/C三个实体分别需要转换成一个关系模式，中间的多对多的联系也需要转换成一个关系模式，因此最少需要转换成4个关系模式。

    从这里我们可以看出，即使是和三个实体产生关系，是多对多对多的，我们也可以将这个联系转成1个关系模式，而不需要去转换成多个关系模式。

# P46 关系代数

  • 并，典型的集合运算，把两个集合的内容的并在一起，并且将两个表中都有的记录只显示一次，重复的只显示一次。
  • 交，典型的集合运算，把公共部分找出来，形成新的关系。
  • 差， 典型的集合运算，A有B没有的，将公共部分去掉。
  • 笛卡尔积，将两个表进行合并，S1中的每条记录需要与S2中的每条记录进行拼接，结果集中，属性数是参与操作的两个表的属性值之和，记录条数是两个表的记录数之积。
  • 投影，选出哪些需要的列，其他列不需要。投影时可以使用列的序号表示，如Pai1,2(S1)与图片中的等价，1代表第1列，2代表第2列。
  • 选择，选择的是记录，选择的是行。选择的时候，也可以用同样的方法，Sigama1(S1)，1代表第1列，即Sno列。
  • 联接，联接是进行等值联接，将两个表中都有的字段只保留一个，如使用S1.Sno = S2.Sno条件，这个时候连接后，Sno就只剩下一个。如果不写条件的话，就是自然联接，条件就是两个关系当中相同的字段做等值，即对于这个表默认就是S1.Sno = S2.Sno条件。

做笛卡尔积或联接后，再做投影的话，要注意最后生成的列数，笛卡尔积列数是两个表的列数之和，而联接会去掉一个公共字段，少一列！！！

# P47 规范化理论-函数依赖

函数依赖是规范化理论的基础知识点，是后面要讲的主键、范式等的基础。给定x能够确定y,则称y函数依赖于x. x->y。

如在数据库中，学号可以确定姓名，但姓名不能确定学号，如出现重名时，一个姓名可能会对应多个学号。

部分函数依赖：如以(学号，课程号)组合键可以确定姓名，而且与此同时，学号也是可以确定姓名，即主键是两个属性的组合键，其中的一部分可以确定某个属性，这就是部分函数依赖。

传递函数依赖：比较简单，A确定B，B确定C,则可以推论出A确定C，这就是传递函数依赖。这里B不能确定A，因为如果B能确定A，则说明A和B等价，如果是等价的，则不存在传递性的说法。

有了函数依赖的基础后，我们就可以看后面的问题了。

# P48 规范化理论的价值与用途

非规范化的关系模式，可能存在的问题包括：数据冗余、更新异常、插入异常、删除异常。

数据冗余：如示例表中，D01、计算机系、1号楼等这些关于计算机系的信息就存在大量的冗余，每个学生都对应一个系，导致系会重复多次记录，这就是冗余。

更新异常：另外，如果将第一条的计算机系更名为计算机科学系，但是后面的数据中并没有更新，这时候就会导致更新异常，因为都是D01，但对应的系名却不一样。

插入异常：如两个属性组合作为主键时，当一个属性不明确时，就没办法插入数据。

删除异常：删除了不应该删除的数据。

规范化理论的价值与用途是降低数据冗余，消除掉更新异常、插入异常、删除异常等异常情况。

非规范化理论：也称为反规范化理论，如加数据冗余等。

设计没有绝对的标准，没有说把规范化做得更高的级别，比如将一项指标提高，另一项指标可能会降低。

如将安全提高，有可能性能就会降低！

# P49 规范化理论-求候选关键字

  • 超键：要求最低的概念，要求唯一标识元组，超键可能存在冗余属性，在超键的基础上消除多余属性就是候选键。
  • 候选键：唯一标识元组，在超键的基础上消除多余属性，就是候选键。如（学号、姓名）可以确定性别，（学号、姓名）组合键可以称为超键，但不能称为候选键，因为可以通过学号就可以确认性别，也可以通过（学号、姓名）确认性别，所以姓名是一个冗余属性，将姓名属性去掉，通过学号确定性别，这个学号就是候选键。当有多个候选键时，只能从这些候选键中选择一个候选键设计为主键。
  • 主键：在多个候选键中选择一个设置为主键。类似于一个国家竞选总统，有多个总统候选人，最终选出来的总统只有一个。在数据库中，可以有多个候选键，如几个字段都可以设置为主键（也就是候选键），但是只能挑选其中的一个做为主键，比如即有学号又有身份证号，学号和身份证号都能唯一标识一个人，所以可选择学号做为主键，也可以选择身份证号做为主键，二选一，但不能同时设置两个为主键，这就是候选键与主键的差别。
  • 外键：别的关系的主键。很多时候需要对表做关联处理。如在员工表里面设置一个部门号，部门号用来和部门表进行关联，部门号对于员工表就是一个外键，外键主要是用来进行关联查询的。

# 求候选键

  • 使用图示法求解候选键。
  • 入度为0的属性，就是没有箭头指入进来的。出度就是有箭头指出。
  • 候选键需要能够遍历全图。
  • 注意绘制组合键时，需要将多条线先汇成一个节点，然后再从这个节点连出一个箭头到其他的位置。
  • 如果没有入度为0的，那么要找一个即有入度又有出度的，再看这个关键字是否能遍历所有关键字。

所以，按以上方法，可以知道例题中：

第1题选A,R的候选关键字是A1。

第2题候选码是ABCD组合键。

第3题选B,关系R的候选关键字为A和B，即A和B都可以做为候选键。

# P50 规范化理论-范式

范式几乎是必考的内容。函数依赖、候选键的求解是范式的基础。

范式可以分第一范式、第二范式、第三范式、BC范式、以及级别更高的第四范式。

但是范式级别不断提高时，规范化程度越来越高，与此同时带来一个问题，规范化程序越高数据的粒度越来越小。提高范式级别，基本上就是通过对数据表进行拆分，越高级别的范式时，数据拆分得越细，把数据一步步拆分的非常细的时候，往往又带来性能方面的问题，所以一般采取比较平衡折中的方式，就是把范式做到第三范式左右就差不多了，不要求进一步往更高级别去深入。

范式级别最低的是第一范式(1NF)，更高的是第二范式(2NF)，要达到第二范式必须达到第一范式；再高的是第三范式(3NF)，要达到第三范式必须达到第二范式。.... 级别越高规范程度越高。

  • 第一范式(1NF)： 属性值都是不可分的原子值。所谓原子值是指这个属性不能再拆分为几个属性。
  • 第二范式(2NF)：在第一范式的基础上，如果消除了非主属性对候选键的部分依赖就达到第二范式。
  • 第三范式(3NF)：在第二范式的基础上，如果消除了非主属性对候选键的传递依赖就达到第三范式。
  • BC范式(BCNF)：在第三范式的基础上，如果消除了主属性对候选键的传递依赖就达到BC范式。
  • 级别越高，规范化程度越高，更有可能去解决插入异常、更新异常、删除异常、数据冗余等问题。如将数据表从第一范式规范到第二范式，解决了一些问题，但仍然有可能有插入异常、删除异常、数据冗余等问题，达到第二范式，进入到第三范式，这种情况还是有可能上述问题，所以需要一步一步的深入处理。不同的范式，规范了不同的情况。

# 第一范式1NF

  • 第一范式(1NF)： 所有域只能包含原子值，每个属性值都是不可再拆分。示例表中的高级职称人数就不满足第一范式，因为高级职称人数可以拆分为教授和副教授，不满足第一范式的要求，要消除这种情况，将高级职称人数说法去掉，直接保留教授和副教授，就样就达到第一范式。要达到第一范式是非常简单的。

# 第二范式2NF

  • 第二范式2NF：必须先是第一范式，并且每一个非主属性完全依赖主键（即不存在部分函数依赖）时，则是第二范式2NF。

示例中，主键是SNo和CNo的组合键，SNo是学生号，CNo是课程号，Grade是成绩信息，Credit是课程学分信息。需要通过SNo和CNo才能确定Grade成绩信息，因为只有同时使用学生号SNo和课程号CNo才能确定该学生该门课程的成绩，仅用学生号或课程号都不能确定成绩，这个关系模式的候选键是SNo和CNo的组合键。学分Credit是能够通过课程号CNo来确定的，存在部分函数依赖，因为通过CNo课程号就可以确定Credit学分，而CNo课程号只是主键（SNo和CNo的组合键）的一部分，这就存在了部分函数依赖。要解决这种问题，就需要对表进行拆分。

主属性: 所谓主属性是指这个属性是候选键的一部分。示例中SNo学生号和CNo课程号是主属性。

非主属性：所谓非属性是指这个属性不是候选键的一部分。CNo课程号和Grade成绩是非主属性。

判断主属性和非主属性的核心是判断哪些是候选关键字，是候选关键字的属性是主属性，不是候选关键字的属性是非主属性。

部分函数依赖带来的问题：

  • 数据冗余，比如学分保存了很多次，这是不必要的，因为每一门课程都在固定的学分，其实只需要保存一个课程号CNo与学分Credit的对应关系就行。
  • 更新异常：现在课程C01对应的学分是4，如果更新第1条记录，不更新2-4条记录，那么这时候就存在问题，一个课程不能对应多个学分，更新一部分不更新一部分就会有问题，这样就是更新异常。
  • 插入异常：如果我们有一个新的课程C08，对应的学分是6分，如果要把这个信息插入到表中，这时候就没办法插入了，因为还没有学生选择这门课程，而表中的记录没有学号，学号是主键，必须是有值的，不能为空，但这时候没有学生选这门课，这时候就插入不进去。
  • 删除异常：如这一届学生毕业了，将成绩信息全部清除，这个时候学分信息也会被清除，这就是删除异常。

解决以上问题的办法是：将CNo课程号与Credit学分这两个字段提取出来，做一个新的关系模式即可，然后把原来表的Credit学分列给去掉，注意，不能将原来表的CNo课程号去掉了，去掉CNo课程号会导致原来的信息不完整。

  • 单属性作为主键时，就不存在部分函数依赖，就满足第二范式。

# 第三范式3NF

  • 第三范式3NF： 当仅且当R是第一范式1NF，并且没有非主属性传递依赖于码时，则称R是第三范式3NF。
  • 第三范式其实已经达到第二范式的要求。

示例中，表已经达到第二范式2NF要求，因为SNo已经被标识出来是主键，知道这一点不去细致分析，就知道它满足第二范式2NF。

  • 它的主键只有单属性SNo，单属性是不可能有部分函数依赖存在，这样就属于第二范式2NF。

虽然这个表已经达到第二范式2NF，但通过表中可以看到仍然存在问题，如：

  • 数据冗余：从DName系名，Location位置可以看到冗余数据比较多。
  • 更新异常：如更新系名，如果只更新一部分另一部分不更新，就会存在更新异常，会出现系名不一致的情况。
  • 插入异常：如果新建一个系，这时候没有学生属于这个系，就没有办法录入这个新的系的信息。
  • 删除异常：相应的也会出现删除异常。

解决以上问题的办法是：将DNo系号、DName系名和Location位置三个字段提取出来，做一个新的关系模式即可，打破传递依赖。原来表中删除DName系名和Location位置列，原来关系模式只剩下前面的三个字段SNo学生号、SName学生姓名和DNo系号。

# BC范式BCNF

  • BC范式：第三范式3NF消除主属性对候选键的传递依赖就达到了BCNF。

示例中，先找出所有候选键，入度为0的只有S，如果只选S做为候选键是否可行？不行，因为T是由S和J共同决定的，单独是S到不了T。可以看到SJ是一个候选键，同时ST也是一个候选键，因为T可以确定J, 可以遍历完所有的节点。

这时候可以知道，S、J、T都是主属性，没有非主属性，所有关系必须满足第二范式2NF（消除非主属性对候选键的部分函数依赖）和第三范式3NF（消除非主属性对候选键的传递函数依赖），现在连非主属性都没有，那么必定满足第三范式3NF。

示例中存在的函数依赖有：SJ --> T 以及 T --> J， 即SJ确定T，T确定J,很明显第一个函数依赖左边部分是候选键，而第二个函数依赖左边部分T不是候选健，所以可以判断这一个关系模式还没有达到BC范式的要求。

# P51 规范化理论-范式练习题

  • 第二范式2NF是消除了非主属性的部分函数依赖，在第二范式的基础如果消除了非主属性的传递函数依赖，则达到第三范式3NF。
  • 如果未达到第三范式，那么必定没有消除非主属性的传递函数依赖。
  • 部门表部门号是主属性，候选键是部门号，只有一个候选键作为主键，没有组合候选键，因此就没有非主属性的部分函数依赖，只剩下传递函数依赖，如果消除了传递函数依赖，那么就满足第三范式了，因此第1题应该选择C。
  • 第2题需要建立部门号与职工号之间的联系，部门与职工是一对多的关系，应该在多的一端添加联系，即在职工表（表3）中增加部门号，因此第2题选择D。
  • 看表4中有什么内容，看一下哪些内容前面三个表是无法表达的，销售这个新增的表，职工号是肯定有的，有了职工号就没有必要增加部门号了，因为在第2题中，已经在职工表中增加了部门号，已经建立了职工与部门之间的联系，因此销售表里面没有必要部门号，不需要部门号，因此第3题可以排除C和D。再看A和B选项，可以发现B选项中多了一个商品名称，而我们可以通过商品号来查询到对应的商品名称，所以B选项中增加商品名称就成了冗余信息，是可以去掉的，也就是A选项是满足要求的。

# P52 规范化理论-模式分解

  • 保持函数依赖分解：当范式级别不够时，主要采取将模式进行拆分，来达到相应的范式。拆分下来级别就上去了。拆分有不同的拆分机制。一个是保持函数依赖的分解，即分解之前有哪些函数依赖，分解之后仍然有哪些函数依赖。如R(A, B, C)，有函数依赖A --> B, B --> C， 可以拆分为R1(A, B), R2(B, C) 这样拆分就保留了原来的两个函数依赖，这种拆分是保持函数依赖。如果拆分成R1(A, B), R3(A, C) 这样拆分没有保留了原来的两个函数依赖，现在的函数依赖是A--> B ,A-->C, 但这个时候原来的B --> C函数依赖不存在了。
  • 无损分解：有损：不能还原。无损：可以还原。类似于压缩文件，无损压缩后可以还原成原文件，有损压缩是压缩后无法还原成原来的文件。拆分后可以连接起来还原成原来的表的话，就是无损分解。

可以看到可以将成绩表分解为成绩表、学生表、课程表，规范化更高，数据冗余更低，最后形成的表与原来的表是一样的。是无损分解。

# P53 数据库系统并发控制

并发控制会讲到几个方面的问题，首先了解一下事务的基础情况，再来讲到并发是怎么一回事，同时并发过程中可能产生一些什么样的问题，既然可能产生问题，那么就需要相应的解决方案，解决方案就是提出了封锁协议，封锁机制。当然封锁协议提出后又会产生新的问题，下面展开这个问题。

  • 事务：事务是把多个操作封装起来，把多个操作看做一个整体来进行操作，是不可分割的逻辑工作单位。为什么需要事务这种机制呢？是因为很多操作有关联性，这些操作本身是一个整体，需要一次性执行完，如果不一次性执行完会产生一系列的问题。比如银行转账业务，转账业务涉及到两大操作步骤，一个是从转出方将钱扣除，另外一个操作是在转入方将钱加进去，如果说这两个操作是过于独立的，没有联系，没有形成事务，就有可能出现问题，如转出方钱转出了，但转入方并没有收到钱，这时候就产生了错误。事务要求事务当做的操作，要么都做，要么都不做，以保持相应的正确的状态。
  • 事务的4个特性：
    • 原子性： Atomicity, 事务是原子的，要么都做，要么都不做。将事务看做一个原子，不能再拆分。
    • 一致性：Consistency, 事务在执行之前数据是保持一致的状态，在事务执行之后数据仍然保持一致的状态。仍以转账业务为例，在转账前是一致的，两个账号加起来的总和一定，转账完成之和，两个账号加起来的总和没有发生变化，只是钱从转出方到了转入方。类似于能量守恒定律。如果将转出方扣除了钱，转入方没有打入钱，这个时候就是一致了。
    • 隔离性：Lsolation, 事务之间相互隔离，互不影响。
    • 持续性：Durability, 事务执行之后，它的结果和影响是持续的。

事务的提出使得我们在操作过程中对很多的操作能更好的控制，但更多的时候是将事务做为并发的前提条件。便于并发的处理一些事情。之所以要进行并发操作，是为了操作相关的效率。并发操作并行执行往往会带来一些问题，包括以下问题：

  • 并发操作存在的问题：

    • 丢失更新：如图中右上角有T1和T2两个事务，T1事务对A进行自减5操作，操作后写入A应该但为5。T2事务对A进行自减8操作，然后写回，因为T2读取到的A是10，这时候进行自减后，将结果2写入到数据库中，这时候就出现了问题。T2写回时将T1写回的结果(5)覆盖掉了，这就是丢失更新。
    • 不可重复读：左下角的T1和T2事务表明了不可重复读的问题，T1事务在计算求和之后，本来想通过再次读取数据进行结果的验算，本身是提高可靠性的做法，因为事务T2将A的值更新了，导致T1事务在进行验证的过程中发现验证失败，因为重复读第二次读数据已经不一样了导致验证失败，这就是不可重复读问题。
    • 读脏数据：所谓脏数据，不是真正的数据，不是执行过程中应该产生的数据，而是一个临时数据，这个值没有起到真实作用。如右下角的T1和T2事务，T1事务对A进行自增操作，得到A为70，这时候事务T2读取到的A的值是70，这个时候T1操作执行了一段时间后，失败了，执行了ROLLBACK回滚操作，将之前的所有操作还原，之前所有的操作不算数，都会回到执行T1事务之前的状态，即A恢复到了20。而事务T2却读取到的是70，是一个脏数据。

为了解决以上问题，就提出了多级封锁协议。

  • 封锁协议
    • 一级封锁协议：事务T在修改数据R之前必须先对其进行加X锁（写锁），直到事务结束才释放。可防止丢失更新。如右上角T1读取数据前加行加锁，加锁后，事务T2就不能再读，必须等T1释放数据后T2事务才能读取数据。
    • 二级封锁协议：在一级封锁协议基础之上，对事务T读取数据R之前对其加S锁，读完就可以释放S锁(读锁)，可防止丢失修改，也可以防止脏数据。读锁加上去之后，其他事务可以再加上S读锁，但不能加上X写锁。写锁加上后其他事务不能再加上读锁和写锁。
    • 三级封锁协议：在一级封锁协议基础之上，对事务T读取数据R之前对其加S锁，直到事务结束才释放S锁(读锁)，可防止丢失修改，也可以防止脏数据，也可以防止数据重复读问题。
    • 两段锁协议：可串行化的，可能产生死锁。两段锁协议的引入有可能产生死锁。
  • 死锁问题
    • 预防法，提前预防死锁的产生。
    • 死锁的解除法，在死锁形成时进行甄别，然后进行解除。

# P54 数据库完整性约束

  • 数据库完整性约束：主要包括实体完整性约束、参照完整性约束和用户自定义完整性约束，这些约束是提高数据可靠性的一种机制，这些约束只能应对简单的情况，复杂的要求无法满足。
    • 实体完整性约束：约束的是主键，主键的值不能为空，不能重复。如果某一个字段为主键，输入值时，如果输入的值为空或者重复就会有异常提示。
    • 参照完整性约束：外键的完整性约束。如员工表里面有个部门号，参照的是部门，这个位置部门号不能随便填写，参照完整性要求填写的数据必须是对应表的主键必须有的内容，这个位置可以为空，或者是已经有的部门号，但不能是不存在的部门号。
    • 用户自定义完整性约束：用户可以设置属性的值的情况要求等，如年龄不能输入负数不能输入200以上的数字。
    • 触发器：上面讲解的实体完整性约束、参照完整性约束、用户自定义完整性约束应对的情况相对简单，如果有复杂的情况，就需要使用触发器来编写比较复杂的约束条件。

# P55 数据库安全

  • 数据库安全主要介绍数据库安全的措施。在数据库领域来应用安全措施提高数据库的安全性。
  • 用户标识和鉴定：身份认证，要操作数据库时需要认证身份，用户需要输入自己的用户名和密码，只用输入了正确的用户名和密码才能进行数据库操作。
  • 存取控制：对用户进行授权，不用级别的用户给予不同的操作权限，在数据库里面可以进行相应的设置。
  • 密码存储和传输：对远程终端的信息进行加密方式传输。
  • 视图的保护：对视图的限定，对不同权限的用户设置不同的视图。
  • 审计：对用户操作数据库的过程记录下来，保存在日志中，对这些记录进行分析，审计是一种标准的安全操作手段。

# P56 数据库备份与恢复

  • 数据库备份：

    • 冷备份：也称为静态备份，是将数据库正常关闭，在停止状态下，将数据库的文件全部备份(复制)下来。备份时业务会暂停，是文件级别的复制，没有办法精确到表级别。
    • 热备份：也称为动态备份，是利用备份软件，在数据库正常运行的状态下，将数据库中的数据文件备份下来。热备份不能出错，否则后果很严重。

  • 数据库备份方式：

    • 完全备份：备份所有数据。
    • 差量备份：仅备份上一次完全备份之后变化的数据，注意是针对上一次完全备份，变化量大一些，这种便于数据恢复，只需要先恢复完全备份版本+差量备份版本。
    • 增量备份：备份上一次备份之后变化的数据，这是针对上次备份，恢复起来不方便，要将完整备份之后的每个增量备份要依次恢复才能恢复数据，恢复相当麻烦。

  • 海量转储：

    • 静态海量转储：在系统中无运行事务时进行，每次转储全部数据库（即备份全部数据库）。

    • 静态增量转储：在系统中无运行事务时进行，每次只转储上一次转储后更新过的数据（类似数据库增量备份）。

    • 动态海量转储：转储期间允许对数据库进行存取或修改（就是数据库服务运行，没有停止），每次转储全部数据库。

    • 动态增量转储：转储期间允许对数据库进行存取或修改（就是数据库服务运行，没有停止），每次只转储上一次转储后更新过的数据。

  • 日志文件：

    • 事务日志是针对数据库改变所做的记录，它可以记录针对数据库的任何操作，并将记录结果保存到独立的文件中。
    • 在我们做了全量备份、增量备份、差量备份等，系统出故障仍然不能保证数据能够完全找得回来，因为增量备份是一天一次，不可能24小时一直做增量备份，这样一来，还没有做增量备份时，从上一次备份到这一次增量备份期间的数据，就没办法记录下来，这就导致恢复时数据可能恢复不完整。面对这种情况，我们应该如何应对？就是借助于日志体系。
    • 日志体系是这样的机制：在进行任何的操作（插入、更新、删除等，不包含查询操作）之前，先将SQL语句记录到日志文件中，然后写数据文件，这样子做，一旦写数据文件出故障了，需要恢复数据时，我们可以通过查询日志文件，然后按日志文件上面的SQL语句进行依次操作，达到恢复数据的效果。日志文件比数据文件先进行处理。

  • 数据库故障与恢复
    • 事务本身的可预期故障，本身逻辑有可能出的问题，事先设置回滚语句。
    • 事务本身的不可预期故障，事务不知道的故障，通过日志来撤销事务的修改，回退到事务初始状态。
    • 系统故障，可以是数据库管理系统的故障或操作系统故障，通常使用检查点方法来进行排查。
    • 介质故障，外存被破坏，使用日志进行重做。

# P57 数据仓库与数据挖掘

数据仓库和数据挖掘现在广泛应用于BI商业智能里面，BI的核心技术就是数据仓库和数据挖掘。数据仓库与数据库到底有什么差异。

讲一下数据库与数据仓库的发展历程来说明它们之间的差异。

  • 数据库：数据库是根据业务的需求，看要处理哪项业务，需要哪些数据，就把它记录下来，就形成了数据库。形成了数据库系统后，可以发现很多系统都离不开数据库系统。像超市收银员系统，收银员系统是典型的业务系统，收银员通过扫描商品的条码，计算出商品的价格，收银员系统刚刚建立的时候，系统数据不是很多，系统运行速度比较快，运行一段时间后，运行速度越来越慢了，是因为系统里面的数据越来越多，导致系统整体的性能越来越低了，降低到一定程度后，用户就难以忍受这么低的效率这么慢的速度了。在这种情况下，人们就想到，需要如何去优化这个系统，优化最简单的方法，就是删除掉一些历史数据，因为对于收银员系统而言，除了当月的收银数据有价值，有时候上个月的数据，已经结算的数据，往往没有太多的价值，因为这些数据用不到了，这个时候优化的主流做法就是删除历史数据，这样删除历史数据就引起了一些人的反思，数据删除了非常可惜，因为这些数据是好不容易收集起来的，虽然在收银员系统里面用不上，但对于企业决策来说，这些数据是有价值的，如果把这些数据删除掉，相当于数据没有用上。不删除这些数据，又觉得这些数据碍事情，会降低系统的效率，那么怎么办呢？我们弄个位置单独把这些历史数据存储起来，最初考虑就存储在普通的数据库里面，后面发现，存在这些数据库里面时，应用层面和普通业务系统有很大差别，像普通业务系统，如收银员系统，平常最主要的工作是频繁的录入数据，要求的是性能和速度，而对于这种存储下来的历史数据，不需要频繁的添加修改数据，一般添加进去之后就不变了，不修改了，而更重要的是大规模的查询分析统计这一块，人们发现需要对这种数据库进行优化，走的思路是完成不一样的，所以将这种特殊的数据库提取出来，给它一个名字叫做数据仓库。
  • 数据仓库的特点：
    • 数据仓库是面向主题的，不是按面向业务应用的。如需要分析商品这个主题，就会将商品这个主题的数据从各个系统里面抽取出来，如收银员系统，将流水的销售数据提取出来，如将库存系统里面提取库存，采购系统提取采购数据，一般的数据库系统是按系统来组织数据。
    • 集成的，一般数据仓库会记录一些集成式的数据，比如记录超市的日报表、周报表、月报表都存储起来，而普通的数据库不会这么弄。
    • 相对稳定的（非易失的），进去的数据不再做修改删除操作，相对稳定一些。
    • 反映历史变化（随着时间变化），间隔一段时间会导入新的数据数据仓库中。
  • 数据仓库的建立需要经历以下几个阶段：
    • 从数据源里面抽取、清理、装载、刷新数据。抽取是从不同的数据源（可以是普通的业务系统，也可以是商业数据等）里面的抽取数据，数据可能存在格式不统一等问题，这时候就需要清理，做数据格式的统一，冗余数据的清理，然后进行装载放到数据仓库里面，并进行定期的刷新数据。
    • 数据集市，数据集市是部门级的数据仓库，数据仓库的建立是一个风险很高的事情，就需要考虑来一步一步的创建数据仓库，这样风险可能会低一些，所以就提出了数据集市，先建部门级的数据仓库，建立好了后然后进行整合形成企业级的数据仓库。
    • OLAP服务器：OLAP是联机分析处理服务器，是专门做分析处理工作的，最表层的是数据的前端工作，如查询工具、报表工具、分析工具、数据挖掘工具等，数据挖掘工具比较独特，数据挖掘的基本形态与查询工具不一样，如查询工具有比较明确的目标，而数据挖掘工具往往没有明确的目标，因为数据挖掘工具可以挖掘到人类未知的数据、人类未知的特性，这些挖掘出来的数据，可以应用在商业领域，如做饮料销量数据的挖掘，如看什么季度什么地段什么样的超市卖什么的饮料会比较畅销，可以做老用户的数据分析挖掘，看哪一类用户偏好什么样的产品，然后以什么样的营销方式更能打动这些老用户，如之前做过很多的电话营销，针对不同的用户群体做了不同商品的营销采取了不同有策略，可以做一些挖掘工作，找出我们不知道的数据来。
    • 数据挖掘应用时间比较久，产生了不同方法和分支。

  • 数据挖掘方法：
    • 决策树
    • 神经网络
    • 遗传算法
    • 关联规则挖掘算法
  • 数据挖掘分类：
    • 关联分析：挖掘出隐藏的数据间的相互关系。
    • 序列模式分析：侧重点是分析数据间的前后关系（因果关系）。
    • 分类分析：为每一个记录赋予一个标记再按标记分类。分成不同的类别。
    • 聚类分析：分类分析法的逆过程。由个体的共性聚合成大的类别。

# P58 反规范化技术

  • 反规范化技术，也叫逆规范化技术，为什么要这么做了？应了一句老话叫做“物极必反”。当时提出规范化技术，主要是考虑，如果数据库规范化程度不高，会存在过多的冗余，会有插入异常、更新异常、删除异常等问题，所以要把规范化提上议事日程，把一般的表的规范化程度做高一些。但规范化程度一步一步提高的时候，又引入了新的问题，规范过程中对表不断的拆分，导致数据表过多，每个表颗粒度过小，这就引起了一些问题，查询的时候需要关联多个表进行查询，关联的表越多查询的效率就越低，而且低的效率是以几何级数递增的处理时间和查询时间，所以可以发现规范化程度过高了不是一件好的事情。所以提出了反规范化技术。

  • 反规范化技术的手段：

    • 增加派生性冗余列
    • 增加冗余列
    • 重新组表
    • 分割表

    这些手段其实就是规范化技术手段的逆过程。原来规范过程中为了消除冗余，现在为了查询方便，增加了一些冗余。比如说，在一个订单记录当中，会有单价，数量，这明细可以计算出总额，但这个时候我们可以增加一个派生性的冗余列，把总额总价写上，这样就避免了要计算总数的时候还需要去计算，这其实就是以空间换时间这种思想来进行。又比如成绩表原来只有学号、课程号、成绩这些信息，现在为了直接能够快速的查询到哪个人哪一科课程成绩是多少分，这时候就会把学生的姓名以及课程的名称加入到表中，这样查询到数据记录就可以直接显示了，否则的话就需要做两次关联查询才能把这个信息显示完整。重新组表，就是依据查询效率的原则来重新组表。分割表包括垂直分割和水平分割，也是从效率的角度来看是不是把一个表拆分成多个表，这样查询的数据会快一点。

    反规范化的核心就在于提高查询的效率，以牺牲一些空间以及规范程度为代价来提高查询的速度。

# P59 大数据

  • 数据量Volume 极大
  • 速度Velocity 要快
  • 多样性Variety 具备多样性
  • 值Value 有价值

对海量数据进行处理。

量变引起质变。当数据量上来后，再使用传统的方法处理已经不适用了。

大数据数据量极大关系极其复杂，量变引起质变，当量积累到一定的程度后，再去处理这些数据，使用传统的方式就已经不适用了。而且大数据分析，要求分析的细度比传统的高很多，所以一般大数据需要借助集群去完成一系列工作。

大数据系统一般应具备以下一些特性：

  • 高度可扩展性，集群就能满足这个要求
  • 高性能，集群也能满足这个要求
  • 高度容错，集群也能满足这个要求
  • 支持异构环境
  • 较短的分析延迟，强调整体的性能，分析时间短
  • 易用且开放的接口
  • 较低成本
  • 向下兼容性

现在的大数据往往与云计算虚拟化等等技术结合起来一起探讨分析，云计算就能把闲置资源利用起来，这样成本会比较低。所以现在的一系列技术，它们之间都会有千丝万缕的联系，联系非常紧密。

# P60 计算机网络-七层模型

七层模型是计算机网络的奠基石，计算机网络整个的基础其实是构建于七层模型的。七层模型是在什么样的环境下诞生的呢？

上世纪计算机的生产不像现在这样通用生产的局面，大家都生产的部件组合起来，不是这样的，往往是整台机器的生产，IBM/APPLE都是这么干的，每个生产厂商都有自己的生产标准规范体系，当时已经有互联网的概念，但是做互联网的推进工作，是各个公司自己去推进，在推进的过程中，就发现了一个问题，当多个企业之间标准不统一的时候，互联网是很难发展起来的，因为互联网的基本思想是把全世界所有的计算机都联接起来，目前已经基本上达到了这种效果，一张网把这么多台计算机都联接起来，除了计算机外，还有手机终端等。而在当时来讲，这个大环境其实是不允许的，为什么呢？像苹果、IBM都有自己的计算机都有网络功能，你把这些计算机买回来，会发现一个严重的问题，苹果和IBM的网络接口是不一样的，接口大小都不一样，插都没办法插，这样将两台计算机联网都很困难，何谈全世界的计算机联网。所以当时就有人提出必须要有通用的标准，没有通用的标准，这一切都是白搭。提出这种思想观点得到广泛的认可，但接下来面临着一个严峻挑战就是到底用哪个标准？每相厂商都不愿意放弃自己的标准去认可别人的标准，这个理由很简单，我们讲一流的企业做标准，如果你用得是别人的标准，显然你自己是没有办法在这一个行业处于领先地位，因为你要跟着别人走，别人制定新标准后，产品做好后，然后发布新标准，你才能够开始研究这个标准，你就比别人晚了很多了，所以当时陷入僵局，有人提出了一个可行的方案，大家都放弃自己的标准，然后由国际标准化组织构建一个新的标准，大家都成为标准的成员，这样大家都会满意，所以就形成了现在的七层模型。

七层模型是由国际标准化组织制定出来的。分成七层，其实是分得有点多，因为大家公认这个标准，所以也没有什么改变。

这七层标准当中：

  • 物理层：最底下的是物理层，物理层负责传输二进制数据，也就是高电频低电频这样的数据，主要涉及到的设备有中继器和集线器。中继器是这样的一个设备：我们在传输数据过程中，传输距离过远的时候，涉及到信号的衰减，衰减到一定的程度后，就会不过去了。比方说，网线就有100m的限制，我要传200m，就在中间加一个中继器，中继器接收一边的信息，然后把信息原封不动的从另外一段传输出去，这样就延长了传输距离，中继器并不会考虑这些数据是怎么情况，就是原封不动的照搬过去。中继器的原理很类似于古代的烽火台，古代传输信息比较麻烦，将一个信息传输到别外一个地方需要很长时间，一旦某个地方发生战争，就会点起狼烟！与现在中继集是一回事。集线器是多端口的中继器，也是简单的收到数据就传输出去。
  • 数据链路层：传送以帧为单位的信息。数据链路层定义了帧这个信息单位，有了信息单位，传输的时候就好处理。像我们讲的网卡就Mac地址，这个地址就是帧地址。主要的设备会涉及网桥、交换机、网卡等，网桥是连接两个同类型网络的设备。交换机（又称为多端口的网桥）用来连接多个设备，信息的传输已经有地址了，交换机比集线器性能要高很多。
  • 网络层：分组传输和路由选择。网络层会有三层交换机，路由器等典型的设备。路由选择在网络当中非常重要，网络在全局来看是一种网状的结构，从一个点到另外一个点，其实是有多条路径的，如果没有去做路径的选择，整体的性能可能比较低。三层交换机就是加了路由功能的交换机。
  • 传输层：管得是端到端的连接。涉及到端口号的问题，在传输层有两大协议，TCP和UDP。
  • 会话层：建立、管理和终止会话。
  • 表示层：数据的格式与表达、加密、压缩等。
  • 应用层：实现具体的应用功能。

示例中，主要考虑局域网和广域网的差异的问题。在七层模型中，局域网是工作在下面两层（物理层和数据链路层），即只到数据链路层，局域网的典型设备是交换机，局域网内部有广播，整个局域网成员都可以收到，但是出了局域网它们就收不到这个广播消息，所以这个示例考虑是就是让大家分析哪些地方的网络属于一个局域网内，哪些是属于不同的局域网。

不能通过的往往是跨越了网络层，因为跨越了网络层就不属于同一局域网。

A选项，计算机P和计算机Q之间，通过网桥连接，网桥属于数据链路层设备，网桥是二层设备，就是数据链路层设备，说明P和Q属于同一个局域网的，所以广播信息是可以传输的。

B选项，计算机P和计算机S之间，通过路由器连接，路由器是三层设备，就是网络层设备，局域网是不能透过三层去传播广播信息的。说明P和S不属于同一个局域网的，广播信息是不能传输的。因此本题选B。

C选项，计算机Q和计算机R之间，通过集线器连接，集线器属于物理层设备，集线器是一层设备，说明R和Q属于同一个局域网的，所以广播信息是可以传输的。

D选项，计算机S和计算机T之间，通过交换机连接，交换机属于数据链路层设备，交换机是二层设备，就是数据链路层设备，通过交换机连接并不影响它们之间的通信，说明S和T属于同一个局域网的，所以广播信息是可以传输的。

所以正确答案是B。

# P61 网络技术标准与协议

首先要了解到的是几大协议族。

  • TCP/IP协议：这是一个庞大的体系，下图中性展示的一系列的协议都属于TCP/IP协议族的一个组成范围。因为从TCP/IP协议族的划分来看，会将网络划分成四到五层，这个四或五层，没有一个非常明确的定论。不同资料上面有不同的描述。但是了解几个主要的层次就OK。TCP/IP协议之所以能够得到广泛的应用，最主要的原因是它与Internet绑定在一起了，它是Internet标准的协议族，所以随着Internet的发展变得应用范围极广，但这种协议并不见得效率和速度会有多高多快，它的效率和速度是比较低的。研究网络的应用知道，一般称TCP/IP协议族称为重量级的协议。
  • IPX/SPX协议：对于玩联网游戏的用户应该不会陌生。这个协议很早就有，在NOVELL网的时候就有这个协议，局域网的即时战略游戏基本都支持这个协议，因为局域网进行联网游戏的时候，需要有相应的协议来支撑它们之间的通信。路由、大型企业网。
  • NETBEUI协议：这个协议最大的特点就是不支持路由，正是因为不支持路由，所以速度比较快。

下面比较重要的是TCP/IP划分层次下的网络体系下的协议。常见的协议我们要了解它们基本的功能是什么。

像三层网络层的常见的协议有：IP、ICMP、IGMP、ARP、RARP协议。

其中ICMP称为英特网的控制协议,像我们常用的ping命令来检测网络是否通畅就是属于ICMP里面的协议。

$ ping baidu.com -c 3
PING baidu.com (39.156.69.79): 56 data bytes
64 bytes from 39.156.69.79: icmp_seq=0 ttl=48 time=45.149 ms
64 bytes from 39.156.69.79: icmp_seq=1 ttl=48 time=33.295 ms
64 bytes from 39.156.69.79: icmp_seq=2 ttl=48 time=46.963 ms

--- baidu.com ping statistics ---
3 packets transmitted, 3 packets received, 0.0% packet loss
round-trip min/avg/max/stddev = 33.295/41.802/46.963/6.061 ms
1
2
3
4
5
6
7
8
9

ARP是地址解析协议，地址解析协议，即ARP（Address Resolution Protocol）。

RARP是反向地址解析协议，反向地址转换协议（RARP：Reverse Address Resolution Protocol）。

它是分别将IP地址转Mac地址（即硬件物理地址），和将Mac地址转IP地址。

传输层有TCP和UDP两大协议，这两大协议是传输层主导的协议。这两种协议有不同的地方，TCP是可靠的协议，UDP是不可靠的协议。TCP在通信的时候会建立连接，UDP在通信的时候是不建立连接的。TCP的可靠是建立在什么的样基础之上的呢？凭什么就能提供可靠的传输呢？原因就在于TCP的验证机制，就是TCP协议在传输信息的过程中，会有反馈信息，有反馈信息我们就可以及时知道哪些数据包正常的顺利的传到了目的地，哪些数据包没有正常传输到目的地。TCP协议在进行通信之前还要进行三次握手的活动。

通过三次握手才能建立起连接，连接后每次传输都会有回复，通过回复可以知道哪些数据收到了，哪些数据包没有收到，进而得到哪些数据丢失了，从而通过重发的机制来确保所有的数据包对方已经都接收到了。这就保证了传输的可靠性。

UDP是直接传输数据包到目标地址，并没有验证。UDP在这方面相对弱一些。

TCP之上的协议都是可靠的协议：

  • HTTP: 超文本传输协议
  • FTP: 文件传输协议
  • Telnet:远程登陆的
  • POP3和SMTP：是邮件传输的协议

UDP之上的协议都是不可靠的协议：

  • DHCP:用来做动态IP地址的分配工作
  • TFTP: 小文件的传输工作
  • SNMP:简单网络管理协议
  • DNS:域名解析的协议

# DHCP协议

  • DHCP协议是用于做IP地址的动态分配的。我们知道在一个局域网里面给每一台机器设置IP地址是一件非常麻烦的事情。如因为张三离职了李四来了，又需要重新分配IP地址。而且对于我们个人用户来说，也是不方便的。因为你在这一个网络里面设定了固定IP，在另外一个网络里面又要设置固定IP，这是相当麻烦的事情。所以就有了DHCP协议，DHCP协议就是用来动态分配IP的协议。
  • 在局域网里面一般都有DHCP的服务器，然后客户机接入到网络后，向DHCP服务器提出IP地址的分配请求，服务器就会根据客户机的情况、网络IP地址分配的情况，给客户机分配IP地址，分配了IP地址，客户机就可以接入网络了。
  • IP地址的分配的过程中，本身是一种客户机、服务器模型。
  • 租约默认为8天。给客户机分配IP地址设置有效期，过了这个有效期，服务器就有可能将这个IP地址给别人用。租约没有满之前，你多次登陆往往分配的是同样的IP地址。租约满了之后，是不是就分配其他的IP地址或者直接收回IP地址呢？不是这样的，比如一家公司，50个员工，虽然是动态分配的IP，但每天来办公室的就这么些人，所以把你的IP地址变来变去似乎也没有什么必要。所以提示了一种机制，续约的机制，只要你在用这个IP，就一直给你去续约，以保证你在长期时间都是使用的稳定的IP地址。
  • 当租约过半的时候，客户机就要向服务器申请续约了。即4天后就需要申请续约。
  • 当租约超过87.5%的时候，如果仍然没有跟原来的DHCP连接上，就需要考虑与网络中其他的DHCP服务器取得联系了。
  • 分配IP有不同的策略，如固定分配、动态分配、自动分配等机制。如固定分配，那个Mac地址分配哪个IP地址。
  • 两个特殊的IP地址，如169.254.X.X 和0.0.0.0，如果给你分配的IP是这样的，说明给你分配的IP没有成功，这两个地址是假地址，不能与外界通信。有可能服务器出故障了，也有可能是你的计算机的故障没有与服务器联系上。

# DNS协议

  • DNS协议即域名协议。
  • 基本上，只要你要用到网络就需要与DNS打交道，平常我们都是用域名来访问站点，而在网络系统当中真正用来识别计算机的，往往是IP地址，只是因为IP地址是一长串数字，不好记忆，所以人们发明了域名，这样比较人性化，比较好记。所以就需要有机器把我们容易记忆的域名转换成对应的IP地址。所以就有了DNS协议。
  • DNS协议就是负责域名和IP地址之间的转换。
  • 在这里考得比较深的是DNS体系中，递归查询和迭代查询。
  • 递归查询：一层一层的深挖，直到找到最后的结果才返回给请求方。服务器必须回答目标IP与域名的映射关系。
  • 迭代查询：客户端请求服务器IP地址，即问服务器这个域名对应的IP地址是多少，服务器端说它自己也不知道，但是你可以问别人。

如示例中，本地需要查询y.abc.com的IP地址，这个时候本地客户机就向本地域名服务器发送查询请求，或者说本地域名服务器设置了查询方式是递归查询，如果本地服务器知道这个域名对应的IP，就会直接将这个IP地址返回给客户； 如果本地服务器不知道这个域名对应的IP，它就会负起责来，去查询这个域名对应的IP。本地域名服务器就会去问根域名服务器，所谓根域名服务器就是最高级别的域名服务器，全世界只有十几台根域名服务器。根域名就没有那么的负责，这个时候，根域名服务器不会告诉你y.abc.com这个域名对应的IP地址是多少，而会告诉你，我不知道这个域名对应的IP地址，但是我知道顶级域名服务器dns.com它可能知道，就告诉你顶级域名服务器的地址。然后本地服务器就与顶级域名服务器dns.com进行交涉，顶级域名服务器又告诉本地域名服务器，我也不知道这个域名对应的IP地址，但我知道谁知道，权限域名服务器知道，就把权限域名服务器（dns.abc.com）的地址告诉本地域名服务器。这时候本地域名服务器就与权限域名服务器交涉，权限域名服务器查询它自己的数据，发现自己有y.abc.com域名和IP之间的映射关系，就将最后y.abc.com域名对应的映射关系返回给了本地域名服务器。本地域名服务器再将最终的对应映射关系返回给客户端。

通过这种方式就可以看出递归查询和迭代查询的区别。

  • 递归查询会一直查询到最终的结果，需要刨根究底找到答案再反馈结果。客户端问到了本地域名服务器，本地域名服务器通过多方查证，最后把最终的结果答案直接告诉了客户端。
  • 迭代查询：像根域名的这种做法就是迭代查询，别人问我域名的IP是多少，我不知道，但我有线索，提供线索给别人，让他自己去追溯。一般的DNS设置都是走的这种模式。因为对于本地域名服务器，它的压力不是很大，所以它可以对一个查询负责到底，找到最终答案再反馈。而对于根域名服务器，压力过大，如果用递归查询，往往会导致整个体系效率极其低下，所以这种形式比较常见，即本域名服务器常用递归查询，根域名、顶级域名、权限域名服务器之类的采用迭代查询方式。

第二种方式：

本地域名服务器递归查询根域名服务器，然后根域名服务器也进行递归查询，这样所有的本地服务器都要查询根域名服务器，这时候根域名服务器压力会非常的大，会导致一系列的问题，这种方式效率比较低。

此题中，可以看到根域名服务器采用的是迭代查询，因为本地服务器问询根域名服务器时，根域名服务器没有直接去查找这个域名对应的IP，没有去寻找最终答案，而是直接给的一个反馈信息，因此使用的迭代查询方式。根域名服务器告诉本地服务器，中介域名服务器知道这个域名的映射关系。

因此，本地域名服务器又与中介域名服务器进行交涉，中介域名服务器并没有直接反馈一个信息给本地域名服务器，而是先去查找到对应的授权域名服务器host2，也就是中介域名服务器是采用的递归查询方式，查询到最终的结果后，直接将最终的结果返回给本地服务器。因此，中介服务器使用的是递归查询。因此本题选A。其他几种讲法都是错误的。

SNMP了解它是简单网络管理协议就行！

TFTP主要与FTP进行区别开来，一个（FTP）是可靠，一个是不可靠的。

至于中间部分的协议（Samba、CIFS、NFS）既可使用TCP协议来实现也可以使用UDP协议来实现。中间这几个协议都是文件共享协议。Samba比较有特色，可以跨平台。

# P62 网络类型与拓扑结构

  • 按分布范围分：
    • 局域网LAN: 办公室级别
    • 城域网MAN: 城市级别
    • 广域网WAN: 更大一些的是广域网
    • 因特网：全球性的网络
  • 按拓扑结构分：
    • 总线型：用一条总线把各个终端连接起来，传输信息都靠总线，都往总线上面发送和获取信息。
    • 星型结构：星型结构有一个显著特点就是中间有一个中心节点，中心节点连接各个其他节点，一旦中心节点被破坏，整个网络就瘫痪了，所以星型结构存在单点故障问题。
    • 环型结构：信息是通过环来传递的，不存在单点故障，任意一个节点都可以从两个方向传输信息。

我们在办公室里面往往是用的星型结构布局的，不是总线型的，星型的中心节点是交换机。一旦交换机出故障了，整个网络也就出故障了。

# P63 网络规划与设计

网络规划与设计主要了解网络规划的基本原则，以及逻辑设计、物理设计需要干什么事情，层次化的网络设计这么几个小的知识点。

  • 网络规划的原则：
    • 实用性原则：要解决实际的问题。
    • 开放性原则：利用与大家统一一致的标准，这就开放了，主要是用通用的国际化的标准。
    • 先进性原则：设备不是越先进越好，在保证实用性和开放性的前提下，根据实际情况，采用相对先进的设备，后期便于升级，不要使用过时的设备。采用最先进的设备可能成本比较高，同时有可能没有在所有场景都验证OK。比如，你需要给自己的老电脑换一条内存，发现原来的内存不好买，并且还贵，而新出的内存不仅便宜内存空间还大，这是因为技术更新速度太快，更新换代速度太快，一旦采用濒临淘汰的设备，过几年之后，根本没办法升级，这是一件非常麻烦的事情。所以需要考虑一定的先进性。
  • 网络设计任务：在网络设计过程中涉及到一系列的任务，整体包括以下几个方面：
    • 确定网络的总体目标
    • 确定总体设计原则
    • 通信子网设计
    • 资源子网设计
    • 设备选型
    • 网络操作系统与服务器资源设备
    • 网络安全设计
  • 网络设计原则：网络设计也有一定的原则：
    • 可用性：能够运行的时间与总时间的对比。
    • 可靠性：网络设备或计算机持续执行预定功能的可能性。
    • 可恢复性：网络要容易恢复。
    • 适应性：网络要有一定的应变能力。
    • 可伸缩性：要考虑后期扩容。
  • 实施原则：
    • 可靠性原则
    • 安全性原则
    • 高效性原则
    • 可扩展性原则
  • 网络实施步骤：大体了解按什么流程走：
    • 工程实施计划
    • 网络设备到货验收
    • 设备安装
    • 系统测试
    • 系统试运行
    • 用户培训
    • 系统转换

# 逻辑设计

主要涉及IP地址方案等。

# 物理设计

# 分层设计

  • 核心层：主要做高速数据的转换，要求设备性能好，不容易出错，可靠性高，一般做冗余设计，一台坏了，另外一台还可以使用。
  • 汇聚层：做的事情比较多，比如访问控制策略，过滤寻址等，层级比较多，可以按需求进行分配设计。
  • 接入层：向本地网段提供用户接入。

# P64 IP地址与子网划分

通过设置不同的子网掩码，注意IP中前面是网络号，后面是主机号。

# 子网划分-通过子网数确定子网掩码

首先将十进字IP地址转换成二进制的IP地址。

由于是B类网络，前面16位是网络地址，后面16位是主机地址。

转换后的IP地址是：xxxx xxxx xxxx xxxx 0000 0000 0000 0000。

此处并不用直接将前面的两个数字转换成真实的二进制数。

划子网的过程是怎么做呢？其实是拿若干个主机位（后面16位全0的是主机位）来充当子网号，需要多少个位才能构成满足要求的子网数量。

看后面的16个0位置，从最前面的第一个0开始：

假设取一位（bit位），则有两种可能性0或1，则可以构成两个子网。

假设取二位，则有两种可能性，则可以构成4个子网。

假设取三位，则有8种可能性，则可以构成8个子网。

假设取四位，则有16种可能性，则可以构成16个子网。

假设取五位，则有32种可能性，则可以构成32个子网。

假设取六位，则有64种可能性，则可以构成64个子网。

即取k个bit位，可以得到N个子网，N = 2 ^ k。

题目中需要划分成27个子网，因此需要需要取5位（5个bit位）才能构成27个子网。

所以，子网掩码是：

1111 1111 1111 1111 1111 1000 0000 0000

再将上面的二进制位转成十进制形式：

255.255.（255 - 7）.0

即：255.255.248.0

# 子网划分-通过子网主机数确定子网掩码

这种情况不知道子网数，但是知道子网内主机数。

而主机数可以由2 ^ k - 2 确认，如果要获取700个主机数，则k至少为10，因2 ^ 9 - 2 =512 -2 = 500, 2 ^ 10 - 2 = 1024 -2 = 1022。

因此主机位数需要为10个bit位。

即：XXXX XXXX XXXX XXXX XXXX XX00 0000 0000

后面的10个0代码主机地址占10个bit位。

因此把将面的X全部替换成1，后面的0保持不变就可以得到子网掩码：

1111 1111 1111 1111 1111 1100 0000 0000

即：子网掩码为：255.255.( 255 - 3).0 = 255.255.252.0 。

如果要判断两个网络IP是否在同一个子网内，这时候需要把两个IP地址化成二进制，然后看他们的网络号、子网号是否相同，如果相同，则在同一个子网类，

# 无分类编址

全0和全1的地址一般不用。

计算128.14.32.0/20地址块的最小地址和最大地址。

"/20"表示IP中前面有多少位是网络号，IP由32个bit位组成，前面20位是网络地址，那么后面12个bit位是主机地址，因此主机数可以达到2 ^ 12 = 4096个。

我们来看一下IP和子网掩码情况：

XXXX XXXX XXXX XXXX XXXX 0000 0000 0000

前面的XXXX代表网络地址，后面12个0代表可能的主机地址。

地址最小的情况就是后面主机地址全是0，这个时候IP地址是：128.14.32.0。

地址最大的情况就是后面所有的主机地址全是1，这个时候IP地址是：128.14.（32 + 15）.255 = 128.14.47.255。

C类子网前面24个bit位是网络号，后面的8个bit位是主机地址。

现在给出的地址块是210.115.192.0/20，即前面的20个bit是网络号，后面的12个bit位是主机地址。

因此可以拿4个bit位作为C类网络的子网网络号，因此可以划分的子网数量是2 ^ 4 = 16个子网！

因此选C。

# P65 特殊含义IP地址

  • 127.0.0.1 回播地址。

  • 169.254.0.0 windows系统无法连接到DHCP服务器时的IP地址。

  • 0.0.0.0 linux系统无法连接到DHCP服务器时的IP地址。

# P66 HTML

# P67 无线网

主要分为无线局域网、无线城域网、无线广域网、无线个人网。

无线网主要特点移动性、灵活性、成本低、容易扩展等相对于固定网络的。

# P68 网络接入技术

# P69 IPv6

很多应用不支持IPv6。技术更新换代不容易。

IPv4是使用32位二进制bit位，不够用。地址空间过小，分配不均匀。70%的IP地址分配给美国了，全世界其他国家要共用剩余的30%的IP地址。

绝大部分应用不支持IPv6。

一个局域网内几十可能到几百台计算机都使用同一个出口IP来访问因特网。IPv4地址分配不公。

所以中国出现了局域网都要使用内网IP，很多单位可能只能分配到一两个IP地址。

  • IPv6地址长度达128位，地址空间比IPv4扩大了2^96倍，这个地址空间是巨大的，可以理解为是取之不尽的。
  • IPv6简化了报文头部格式，提高了安全性、身份认证和隐私权，绝大数网络协议提出来时就没有考虑过安全性，就导致在应用过程中发现有很多问题，同时又必须跑一些应用，所以又补充了很多安全协议，所以可以发现有很多的安全协议在配套原来的协议在使用就是这个原因。
  • 单播地址、任播地址、组播地址。

# P70 信息系统安全属性

安全属性：

  • 保密性：最小授权原则、防暴露、信息加密、物理保密。
    • 所谓最小授权原则是指我们在给某人授权或给某个角色授权的时候，应该依据的是最小授权原则，就是他要包含哪些职能，为了保证他的工作能够正常进行，至少需要开哪些权限，就给其开相应的权限。不要给他过多的授权。举例，新招的职工A，给其安排论坛管理员和博客管理员角色，需要对论坛和博客内容进行审核，看有没有黄色信息、反动内容等，按理说开通这两块的权限就可以，但在日常生活中觉得这样开权限很麻烦，比如现在A只用管理这两个模块，等A熟悉后又需要增加一些新的模块给他管理，有些人为了省事，给A直接赋予最高的权限，这样不管A的工作怎么变化他都拥有权限，虽然这样处理比较简单最省事，但不满足最小授权原则，就会带来安全隐患，就是A不该看到的东西他也能看到。
    • 防暴露，将事物隐藏起来以提高安全性。比方说，为了防止别人破解我们的数据库，我们将数据库命名为非标准的数据库。如数据库有一个安全隐患，如果知道数据库的位置以及文件名，就可以直接把数据库给下载下来，所以可以将数据库文件命名成其他扩展结尾的，名字也是一堆的乱码名字，这样就相当于把数据库数据给隐藏起来了，不让大家很容易的访问到数据库，以至于对数据库进行破坏。
    • 信息加密，同时可以对信息进行加密，加密后再来传输，即使途中被截获了，截获者也无法了解到信息的原始信息是什么样的，除非截获者进行破解解密。
    • 物理加密，采用相应的物理设备，在发送之前进行加密，接收的时候自动解密。
  • 完整性：安全协议、校验码、密码校验、数字签名、公证。
    • 所谓完整性是指信息从一个节点发送到另外一个节点的时候，中间这个信息是不能变化的。如不能这样，发送出的是A，接收到的却是B，这样是不行的。这样会有安全隐患，要防止别人截获信息后，把信息给篡改掉，造成损失，所有有了完整性的要求。
    • 完整性可以用安全协议来保障。
    • 也可以用校验码来保障，如有了校验码后，接收到信息后，使用校验码校验一下，看看是不是和原来的一样的。如我们下载资料时，下载资料的站点给出资料的md5码，下载资料下来后，再查看一下资料的md5码，看是否与站点上面给出的md5码一至，如果不一致则说明下载的资料被别人篡改过了，如果一致则说明下载过程没有问题，完整性没有遭到破坏。
    • 还可以使用密码校验、数字签名、公证等手段来确保完整性。
  • 可用性：综合保障（IP过滤、业务流控制、路由选择控制、审计跟踪）。
    • 所谓可用性往往是指的合法用户以合法的方式来用到相应的资源。如果一台服务器不能给合法用户提供相应的功能，这个时候就是指的可用性遭到了破坏。比方说，非常常见的一类网络攻击方式DDOS破坏的就是服务器的可用性。
  • 不可抵赖性：数字签名。
    • 不可抵赖性用到的主要手段是数字签名，因为签名可以识别发送者的身份，一旦能够通过资料识别发送者，那这个时候发送者是不能够抵赖说我没有发送这个信息给你，这是不行的，所以说不可以抵赖性主要是通过数字签名的形式来做一些防范。

# P71 对称加密和非对称加密

对称加密：在加密和解密的时候所使用的密钥完全一样的，使用什么样的密钥加密，就用什么样的密钥解密。

非对称加密：在加密和解密时所使用的密钥是不同的密钥。用公钥加密，则用私钥解密，用私钥加密，则使用公钥解密。非对称加密中不能用同样的公钥加密又用同样的公钥解密！只有用自己的公钥加密后的文件，利用自己的私钥才能解密开。也就是如果要传输信息给别人，你需要先获取别人的公钥，然后再以对方的公钥加密这个文件，然后发送给对方即可。

平时所使用的RAR压缩包、Excel/word/pdf等的加密是属于对称加密还是非对称加密呢？这个应该是对称加密技术，因为你加密和解密时所输入的密码是一样的，这是典型的对称加密技术。

见课本P40页 1.3.2 加密技术和认证技术。

# 常见的对称加密算法

  • DES算法：Digital Encryption Standard数据加密标准算法，DES采用替换和移位的方法加密，所谓替换是指我们会有一个密码表，明文和密文有一个对应关系，如果要将明文翻译成密文，就直接查找这个表，看A字母翻译成密文是多少，看B字母翻译成密文是什么，这样子加密下来是用的替换的方式，替换方式非常之普遍，如抗战剧里面经常提到破解对方的电报，破解电报的时候如果有密码本在手上，所有问题迎刃而解，你只需要根据密码本，做相应的操作就能够得到原文，这实际上就是替换的方式进行加密的，因为我们把密文逐个的字母查询对应把明文翻译出来即可。移位也非常常见，一旦移位就会导致字母与原来的情况完成不一样。在DES中密钥的长度56位，比较短，它还会分数据块，可以进一步分数据块的加密方式和数据流的加密方式，数据块的加密方式就是分成数据块再对数据块加密，数据流加密方式就是顺次的对数据流用密钥进行加密。DES加密速度快，密钥生产容易。
  • 3DES算法：三重DES算法，三重DES算法是对DES算法的复杂化，正是因为这种复杂化，使得整个的加密强度要高很多，因为我们知道DES密钥长度只有56位，很容易被破解，升级到三重DES，需要用到两个56位的密钥K1、K2。加密和解密的做法：
    • 加密：K1加密 --> K2解密 --> K1加密
    • 解密：K1解密 --> K2加密 --> K1解密
    • 3DES与DES有良好的兼容性，因为所有的操作其实DES算法里面都已经有了，只是3DES多做了几次加密操作，麻烦一些而已。
  • AES算法：Advanced Encryption Standard高级加密标准算法，用来替换原先的DES的，对其要求是至少与3DES一样安全。
  • RC-5算法：Rivest Cipher 5算法，RSA数据安全公司的很多产品都使用了RC-5算法。
  • IDEA算法：国际数据加密算法，采用128位密钥，类似于三重DES，比DES加密性好，对计算机功能要求相对低，IDEA加密标准由PGP(Pretty Good Privacy)系统使用。

对称加密的优缺点：

  • 优点：主要是加密速度比较快，效率比较高。
  • 缺点：缺点也非常明显，一个方面是加密的强度不高，因为采用的密钥本身长度就比较短，密钥的长度短就影响了整个加密的强度，导致整个加密的强度是不高的。另一个方面是密钥的分发比较困难。比如说，我给你发一个秘密㊙️的信息，直接用QQ传送安不安全呢？不太安全，直接传过去的时候，有可能被人截获相应的信息，一旦截获相应的信息，你的信息可能就泄露了，由于是保密的资料，所以我们采取了措施，对资料进行加密，加密之后传给对方，对方首先会问到这个加密包密码是多少？或者说准确一点解密的密码是多少，这个时候你如果仍然用QQ的明文给他发过去，很可能信息又被截获，泄露出去，所以安全性是不怎么高的。这个时候就面临很严重的问题，如果说你直接加密传过去，又用明文将密码传过去，这跟没有加密没有什么区别，直接就被破解掉了，如果不加密呢，安全性也比较差，那面对这种情况应该怎么办呢？有人提出是不是有其他的方法来解决这个问题，就是提出了非对称加密的技术的解决方案。

# 常见的非对称加密算法

非对称加密中，每个人都有自己的公钥和私钥。

如A有自己的公钥和私钥，B也有自己的公钥和私钥，公钥可以公开给别人，公钥可以明文分发，A可以把自己的公钥直接发给B，B也可以直接把自己的公钥直接发给A。A有自己的私钥，B也有自己的私钥，私钥要保密，不能给别人，私钥非常保密，A不能把自己的私钥给任何人，B也不能把自己的私钥给任何人，A的私钥只用A才有，B的私钥也只有B才有，这是前提条件！

另外一个前提条件是，用公钥加密只能用对应的私钥解密。

如，用A的公钥加密，不能用A的公钥解密，也不能用B的公钥解密，也不能用B的私钥解密，必须是用A的私钥才能解密！同样，A的私钥做的加密，也只能用A的公钥才能解密。

有了以上前提条件，如果A需要将一段明文加密发给B，则需要用什么加密？这个明文只能用B的公钥加密并发送给B，为什么呢？用B的公钥将明文加密，B能打开这个加密的信息吗？可以打开，因为B的公钥加密只有B的私钥才能解密，而B是有自己的私钥的，因此就可以打开密文获得到明文数据了。

如果用其他的公钥或私钥加密会存在什么问题呢？假设用A的公钥加密明文，发送给了B后，B不能打开加密包，因为用A的公钥加密的文件必须用A的私钥解密，A的私钥只有A有，B是没有A的私钥的，因此B没办法打开这个加密包。

另外，也不能用B的私钥加密，因为A是没办法获取到B的私钥的，只有B有B的私钥。

那能不能用A的私钥加密呢？如果A用自己的私钥加密，B用A的公钥就可以打开这个加密包，但是因为A的公钥是对外开发的，所有人都可以获取，这个时候别的人也可以通过A的公钥来解密这个加密包，因此起不到加密的信息。因此也不能用A的私钥来加密。

也就是说，如果A要将明文信息加密后传输给B，只能用B的公钥加密明文信息，才比较安全！

有了这样的基础之后，刚才提到的密钥分发的问题就迎刃而解了！直接用对方的公钥加密然后发送即可。

这个时候问题又来了，非对称加密机制中，密钥的长度非常长（如1024位），数字证书一般都使用的是1024位的密钥，是比56位密钥（如DES加密算法）长很多倍的（1024/56 = 18.29，接近20倍），56位加密所需要的时候会远远低于使用1024位加密所需要的时间，这里面差距可以达到数千倍，所以如果对于内容比较庞大的数据，用非对称加密就完全行不通，因为效率太低，没法去走向用户。

而对称方式就非常高效快捷。

所以在实际应用中，对称加密和非对称加密是互为补充的。我们往往用对称加密方式加密大内容传输，用非对称方式来加密密钥来传输密钥。所以密钥分发问题得以解决。

用对称加密大内容传输，用非对称加密方式来传输密钥，这样密钥分发的问题就得以解决。

非对称加密技术的缺点：由于加密速度慢，不适合加密大数据量的数据。

  • RSA算法：512位（或1024位，用得更多）密钥，计算量极大，难破解。

  • Elgamal算法：其基础是Diffie-Hellman密钥交换算法。

  • ECC: 椭圆曲线算法。

  • 其他非对称算法包括：背包算法、Rabin、D-H。

# P72 信息摘要

软考高级考试需要写论文，论文需要写摘要，可能正文1500字左右，而摘要可能区区300字左右，摘要会是正文的一个总态。

信息摘要，参考课本P45 认证技术小节。

在IT领域，信息摘要是是一段信息的特征值。这个特征值的特点是，原始信息发生变化，特征值会跟着一起变化。比如将原文中的一个标点符号发生变化，生成的摘要就会变化，这就是信息摘要。这种特征可以给我们带来哪些启发在哪里可以用到这种特性呢？

举例说明，甲是领导，乙是员工，甲发送一个消息告诉乙，需要给丙支付10万元的合同款，这个消息是明文传输的，因为没有什么保密信息，不需要保密，如果这个时候这个信息被丙截获了，并在信息里面加了一个0，10万变成了100万，并传给了乙，这样会有问题吗？显然是有问题的，公司有可能为此损失90万元！而丙只做了一个小小的改动！这种情况就称之为信息的完整性遭到了破坏，所以我们要想办法保证信息的完整性，让用户发出的时候与接收到的时候是一样的！至少有机制来验证接收到的信息与发送出的信息是否一致！所以提出了完整性要求。

完整性要求是怎么做呢？是甲先将原文明文传输给乙，再产生一个摘要也传给乙，乙接收到明文后，用接收到的明文产生一个摘要，再将这个摘要与甲传输过来的摘要进行对比，如果一致代表信息不被篡改，如果不一致则代表信息被篡改了！

但存在这样的问题，如果在传输的过程中，原文明文和原文的信息摘要的传输过程中都被截获并被篡改成一致的，那乙就不知道信息被篡改了！所以后面就有了数字签名技术。将数字签名和信息摘要结合起来，这个问题就解决了。

在这里还需要了解两个知识点：

  • 信息摘要的算法是采用的单向的散列函数（单向Hash函数，即可以用正文通过摘要算出摘要的结果，但不能把摘要还原成明文，即单向操作，因为摘要是一种破坏性操作手法，它是取的特征值，长度非常之短，MD5长度是128位，SHA长度是160位，无论你多少G的数据，产生摘要都只有100多个bit位，自然绝大部分信息已经丢失了，所以不能再还原了！）
  • 信息摘要算法不能拿来做加密的，因为加密就必须要还原，需要解密。而用信息摘要的单向散列函数是不能够回过来解密的。
  • 了解MD5和SHA是信息摘要算法即可。

# P73 数字签名

数字签名技术主要是一种防抵赖的技术。之前我们在讲安全属性曾经提到过这种技术。

数字签名，顾名思义就是用数字化的方式来给发送者在信息上面签上自己的名字，这样接收者接收到信息之后就知道信息是谁发出来的，并且发送者是没办法抵赖的，因为有证据可以指示这个东西是发送者发出来的。那么要达到这样的效果，我们应该用什么样的手段去实现呢？

还是以发送者、接收者涉及到的几个公钥和密钥来说明，我们要用到哪个密钥来进行加密动作，哪个密钥来进行解密动作呢？

比如，发送者A来传给接收者B，用哪个密钥来加密，哪个密钥来解密呢？

应该是用A的私钥加密，并用A的公钥解密，这样就能达到我们的目的了！大家想想，我收到一个加密的信息，我要把加密信息解密出来，结果我用A的公钥把它解密出来了，哪这说明什么问题呢？说明这个信息包是由A的私钥来加密的，既然是A的私钥加密的，而A的私钥只有A有，所以这样逆推可以知道这个信息是A发出来的！所以相当于A的信息上面做了一个签名！

介绍完以上流程后，需要纠正一个讲法，刚才所说的加密和解密是为了大家能够理解这一个过程是怎么样的，但是一般我们用A的私钥来加密，这个过程不会把它叫加密过程，而是叫数字签名过程，而把用A的公钥解密信息的过程不叫解密的过程，而是叫数字签名的验证过程！

为什么会这样做呢？是因为，你讲是用A的私钥来加密，这种讲法其实是不准确的，为什么不准确，因为加密和解密往往是在安全传输过程中为了达到相应的保密性采取的措施，会有这种认知在里面，但事实上数字签名没有保密可言，因为你是用私钥做的加密动作，然后公钥用来解密，而公钥是满世界都有的，大家都可以获取得到，所以它没有保密的职能，任何人都可以打开这个信息包，只有识别身份的作用，我用谁的公钥能够打开这个信息包则说明这是谁用自己的私钥加的密。所以这一点大家要清晰的想清楚这个问题！

在真正用的过程中，往往是用以下步骤：

  • 首先是对正文产生信息摘要
  • 再对信息摘要进行签名发送出去，为什么是对摘要进行签名而不是对整个信息进行签名呢？这是因为非对称加密技术体制里面不适合于对大信息量数据进行加密解密操作，所以需要这么做！信息摘要就很简短，对摘要进行签名就非常高效。但如果说对原文进行签名那么效率就非常低，所以在很多时候，我们都把信息摘要和数字签名技术结合起来使用。

数字签名其实不是真正的加密。

对正文摘要进行签名（私钥加密），这样效率高一些，然后用户使用网站的公钥进行验证（解密）。

# P74 数字证书和PGP

  • 数字信封：发送方将原文用对称密钥加密传输，而将对称密钥使用接收方的公钥加密后发送给接收方。

这个过程非常的熟悉，对称的加密算法非常适合加密大信息量的内容，而非对称加密算法适合于加密小信息量的内容，所以我们会把正文信息用对称加密方式进行加密并且传输，然后把密钥用非对称方式加密传输给对方，由于你用的非对对称方式是用的对方的公钥来加密对称密钥发给对方，所以这个对称密钥只有你指定的对方才能打得开，一般人截获这个信息是没有办法打开的，所以类似于一个数字信封，它没有验证好你的身份的时候，是不会让你打开这个信封的。

正是因为使用的是接收方的公钥加密的，所以接收方收到这个电子信封后，会用自己的私钥来解开信封，从而得到对称密钥，解密得到原文。

数字信封了解以上基本原理就行。

PGP是一种协议，这种协议既可以用于电子邮件加密，也可以用于文件存储加密。目前有一定的应用，推出了一系列的应用软件。可以应用使用了PGP协议的软件对需要保密的数据进行加密。

像现在很多人习惯用的云盘，网盘，因为这种方式利用到的是云计算的技术，信息一旦存储到云盘上面去，往往是不容易丢失的，因为云盘是有专业的团队去做信息的冗余信息的备份这些工作，反而比你存在本地可靠性更高一些。但放在云盘上面又带来了另外一个问题，放在云盘上面，其他是不是能获取到我的保密信息呢？这是一个值得关注的问题。所以我们可以结合几种技术来用。

用PGP的软件先将保密信息加密，再传输到云盘上面去，这样就可以保密信息的可靠性和安全性。

在PGP体系当中，已经应用了数字证书的机制。

PGP认可的证书有：PGP证书和X.509证书。

这两类证书存储的内容有一定的差异，但是基本的内容是保持一致的，像持有者的公钥、持有者的信息这些信息必然是有的。

因为数字证书是一个什么的概念呢？在什么环境下提出来的呢？这一点需要与大家讲一下。

像我们之前提到了一系列的技术，这一系列的技术已经能够解决大部分的问题，那为什么还要有数字证书这种体系呢？是因为在应用的过程中我们发现一个非常大的问题，像我们非对称体系里面，每个人都会有自己的公钥和私钥，如果想给对方传输秘密的信息，需要用对方的公钥来加密信息传输过去，讲得轻松，但不好实现，为什么呢？比方说在QQ上面，与张三聊天，说你把你的公钥给我，我给你传一个保密的东西，等张三把他的公钥传过来，你再用张三的公钥加密信息后，把加密的信息传输给张三，发现有问题，张三传过来的密钥就是一堆数字，一堆乱码，这时候你没办法判断这个到底是不是张三的公钥而不是李四的公钥，如果这个时候李四截获了张三的公钥然后将自己的公钥传输给你，这个过程就不安全了，正是因为有这种因素，有人就想出了一个办法，就是将个人的密钥和个人信息绑定起来，这样就可靠安全了，数字证书就是这样一个东西，它描述了这是张三的数字证书，张三的公钥也在里面。

所以我们会发现，在日常生活中，安全加密的体制都已经与数字证书结合起来了，就是因为我们在传输沟通的过程中需要证明人的身份的问题，所以数字证书类似于我们生活中的身份证，它有专门的颁发机构，称为CA机构，类似于公安局。CA机构会对数字证书的申请人做相关的一些信息的核实工作然后给颁发相应的数字证书。一旦我们看到这个数字证书是我们信息的CA机构颁发的，那我们就可以认为数字证书的内容是真实有效的。如何去判定这是合法的CA机构颁发的呢？就需要用到签名的机制，因为数字证书上面都有颁发机构的签名，我们可以通过验证颁发机构的签名来了解到这个数字证书是不是伪造出来的。正是因为有这样的一个特点，所以数字证书除上有版本号、序列号、签名算法标识、证书有效期等信息之外，必须要有持有者的公钥信息，否则就违背了我们的初衷。

# P75 设计邮件加密系统实例

通过以下练习，将前面所学的安全基础相关的一系列知识整合在一起，希望大家根据PPT内容自己动手分析这个问题，如果能够分析这个问题，说明对于对称加密、非对称加密、数字签名、信息摘要这一系列技术有了一个基本的认识。所以请大家看到本页的练习题，暂停视频进行练习。花10-15分钟来把整个的内容做一个设计。如果卡壳了建议回到前面的章节回顾相应的知识，争取尽可能利用自己学到的知识来解决这个问题，因为这个问题综合性比较强的。

我们看到题目要求是这样的：

  • 要求邮件以加密方式传输，当然主题是设置邮件加密系统，这是一个前提。
  • 邮件最大的附件内容可达500MB，这说白了就是要对大数据量进行加密操作。
  • 发送者不可抵赖。
  • 若被第三方截获，第三方无法篡改。

通过这个题目内容，我们要开始解析分析啦。

  • 要求以加密方式传输，则需要用加密技术，是用对称加密技术还是非对称加密技术呢。
  • 邮件最大的附件可达500MB，说明需要对大数据信息进行加密，则需要使用对称加密技术，因为非对称的加密技术不适合于大数据的加密操作。
  • 发送者不可抵赖，说明用到了数字签名技术。
  • 第三方无法篡改，说明用到了数字摘要技术。

先把这些东西梳理清楚，梳理清楚之后我们再进一步分析。

对于邮件正文适合用什么方式加密呢？应该使用对称的方式，在发送者A这一端产生随机密钥K，随机密钥K是一个对称密钥（加密解密都用这个密钥），用对称密钥K对邮件正文进行加密，形式邮件的密文。这是第一个部分。

形成了邮件密文后，邮件官方可以发送给接收方B。

接下来，对方收到这个加密的密文，要涉及到如何打开这个密文。所以要想办法把随机密钥K传输给接收方B。如何发送呢？

直接明文发送吗？显然是不行的！不安全。需要加密发！用哪个密钥加密呢？

应该用接收方B的公钥Eb来加密随机密钥K，这样达到保密作用，形成加密后的密钥K，这里其实就是用的数字信封技术。

接收者B接收到使用公钥Eb加密的密钥K后，可以使用自己的私钥Db对加密的密钥K进行解密，得到原始的随机密钥K。

有了原始的随机密钥K后，接收方B就可以使用随机密钥K对加密后的邮件正文进行解密，就可以得到邮件正文！

保密传输这一块到这里就结束了。

接下来就要涉及到的是不可抵赖，数字签名技术。如何达到不可抵赖呢？就是会有数字签名，验证一下签名就行呢。

同时要求第三方无法篡改，就要用到完整性技术信息摘要技术，所以要把正文形式摘要。

对邮件正文提取出邮件摘要信息，形成摘要还不行，还需要对摘要进行数字签名，数字签名以发送方的私钥Da，然后得到了摘要的密文，其实就是签名后的摘要信息。

然后把签名后的摘要信息发送给接收方B，然后接收方B会解密摘要，也就是验证摘要，使用发送方的公钥Ea进行摘要解密，得到原始摘要，然后再把解密后的正文形式摘要，然后将两个摘要进行对比，能够匹配就说明整个过程中没有被篡改。

所以通过这一系列的流程，整个的技术就串联起来了， 所以这个题大家一定要搞清楚。

# P76 各个网络层次的安全保障

各个网络层次的安全保障问题。

我们知道互联网的展状大有着一定的偶然因素，同时在互联网发展的初期，虽然大家都有美好的愿景，要把全世界的计算机都给联网起来，但事实上谁也想不到真能做得这么极致，所以的设计协议的时候，基本上互联网TCP/IP协议都是走的明文方式，它没有考虑到在安全方式有很多非常严苛的应用也会在互联网上跑，所以当时没预料到这一点，导致整个协议体系在安全方面都欠缺考虑，所以在互联网高速发展的时候，人们同时也关注到这个问题，提出了很多解决方案。这也就是我们今天要讲到的安全保障各个层次的一些手段。因为原来没有，现在得补，所以基本都有一定的针对性。

以HTTPS为例，之所以提出它来，是因为原有HTTP走的是明文传输，则网页的明文传输一旦被截获，安全隐患就非常大，所以就把HTTP和SSL安全协议结合起来形式了HTTPS。在我们平常登陆网上银行的时候，基本上都是用的HTTPS协议，在后面就有SSL的保障了。

下面我们来逐个层次的分析。

  • 物理层：最底下这一层是物理层，物理层的基本手段包括隔离、屏蔽，提高安全性通过隔离和屏蔽。比如无线电信息，防止它泄露出去，可以使用屏蔽的方法。比如某科研院所，内容有WIFI信号，供大家上网方便，在这个过程中内部网有大量的数据交换和传输，这个时候最好在科研院所的墙面加上屏蔽材料，这样子防止无线电信号散发出去，被间谍组织给截获到。从最近的新闻我们也可以看到，间谍事件离我们生活是越来越近了。很多人是为了一些蝇头小利被国外的间谍组织收买，他本来原来不是做间谍的，只是顺便拍一些照片，把一些资料卖出去，这实际上是已经严重危害到国家安全，所以有些被判刑，也是非常严重的罪行，甚至有得判死刑的。所以对于高保密的科研院所可以考虑去屏蔽这些信号的。隔离更为多见，因为现在互联网已经离不开我们的生活了，国内在互联网这一块投入了很多的资金来建设基本设施通信网络，但这个网络与军方的网络还不是共用的。军方会单独铺设他们自己的通信网络，这也是考虑到安全性的问题，这是在物理层进行完全隔离，如军方使用不同的网络通道，安全性是最高的。如公安也有自己的公安专网，专网可以加强相应的保密措施，而且一般人接入不了这种网络，要截获破解更加困难一些。

从二层开始，基本上都是走的协议来保证安全。所谓协议，就是通信的时候封包的一种规则。

  • 数据链路层：PPTP和L2TP是两种隧道协议，这种隧道协议是在开放的互联网之上开出两条安全的隧道，从这个隧道里面传输的东西是很安全的，不会遭到破坏不会遭到截获，这是通过什么方式保障的呢？其实就是PPTP和L2TP会有加密机制在里面，传输的时候都进行了加密再传输，类似于是一个安全的通道，走这个通道里面过的。当然也可以直接对链路进行加密。链路加密，PPTP、L2TP协议也会进行加密。
  • 网络层：防火墙，IPSec。IPSec对包进行加密。再上一个层次是网络层，网络层典型的安全措施是防火墙技术，大家对防火墙应该不陌生的，因为平常我们在使用网络过程中或多或少要涉及到防火墙技术，防火墙有软件性质的，即你自己安装在你的本机；也有硬件和软件结合在一起的，有设备专门为防火墙策略提交支撑平台的东西，就是将软件和硬件结合在一起。防火墙又分多种类型，有网络层级的，应用层级的，后面会对防火墙做为一个主题来展开，来说明防火墙的基本特性，以及常见的防火墙的形式。除了防火墙之外，还有IPSec，IPSec与IP协议有一定的关系。IP协议刚好是在网络层，IPSec确实是针对IP包进行加密的一种协议。因为IP包本身不涉及到加密的问题的，它是直接明文传输的，当传输的数据非常的保密的时候，可以使用IPSec介入，IPSec可以把原有的IP包加上密之后再进行传输。具体来讲，IPSec又有两种动作方式，一种就是我有普通未加密的包，我把这个IP包里面的数据拆分出来进行加密，再进行封装包头之类的再进行发送出去；另外一种就是连着这些包头信息一起将整个IP包进行加密，再附加一个头发送出去。两种形式都是可以的。要记得IPSec是工作于网络层的！如果说怕搞混了，记得IP是网络层的，IPSec是与它对应的，也是网络层的!
  • 传输层：TLS是标准的传输层的协议。SET协议是面向电子商务的协议。在这一个协议里面集成了很多的机制，比如说通信过中的安全保密，比如在购物过程的防抵赖的措施，因为它是为电子商务而生的，所以它在这些方面都有所考虑。 对于TLS和SET协议，要记住他们是传输层的协议。SSL协议比较特殊，它跨越了传输层一直延伸到应用层。传输层->会话层->表示层->应用层。不建议一开始就是SSL做定论！
  • 应用层：PGP和HTTPS。PGP既可以对邮件进行加密也可以对文件进行加密。HTTPS是HTTP+SSL的协议。

# P77 网络安全与攻击

网络威胁与攻击，在这一部分主要是对威胁进行基本的介绍，尤其是有些威胁并不是很长见，考试的时候抠的就是字眼，所以下面这两张表中基本的描述要了解清楚。

  • 重放攻击(ARP)：利用ARP协议本身的协议漏洞来进行的，在这个过程中，由于它有欺骗计算机的嫌疑，所以有时候又叫ARP欺骗攻击。
  • 拒绝服务(DOS)：对信息或其它资源的合法访问被无条件地阻止。主要是破坏了系统的可用性，合法用户无法使用相应的资源。

注意一点，威胁中窃听与业务流分析的区别。

窃听主要和业务流分析区别对待，注意里面的细节。因为这两者极易搞混。两者描述太相近。业务流分析需要长期的监听或窃听。

  • 窃听：窃听是使用各种可能的合法或非法的手段窃取系统中的信息资源和敏感信息。如给新的职员分配了不该属于他的权限，他能够合法的获取到他不该看的资源内容。非法手段如要窃听别人的电话，就直接在上面搭线下来然后接电话机来窃听。还有一些时候可能是合法手段，所谓合法手段，在一个系统当中，如你本身拥有的权限应该只有论坛管理员权限，但是是给你赋予权限的时候，管理人员为了省事，给你赋予了整个网站大的管理员的权限，这个时候你就可以看一些和你本身工作业务无关的信息，像这种方式获取的信息就算是合法的，因为你是按你的权限去做的，但实际上这些信息你不该知道的。
  • 业务流分析：通过对系统进行长期监听（注意此处是长期监听），利用统计分析方法对诸如通信频度、通信的信息流向、通信总量的变化等参数进行研究，从而发现有价值的信息和规律。有分析的成分在里面，所以是业务流分析。但很多人看到系统长期监听，就容易认为这是窃听，其实是监听！
  • 信息泄露：信息被泄露或透露给某个非授权的实体。
  • 破坏信息的完整性：数据补非授权地进行增删修改或破坏而受到损失。其实之前也提到过，你把信息做了增删改之类的操作，因为我们要求在传输的过程中，原来是怎么样的，到目的地就应该是什么样子的，不能改变。
  • 非授权访问：某一资源被某个非授权的人，或以非授权的方式使用。就是没有获得授权，绕开了授权来访问调用。
  • 假冒：假冒用户冒充合法用户来进行。
  • 旁路控制：攻击者利用到系统本身的安全缺陷或者安全方面的问题来获取相应的一些权益。
  • 授权侵犯：又称内部攻击。被授权以某一目的使用某一系统或资源的某个人，却将些权限用于其他非授权的目的。
  • 特洛伊木马：相当于是一个间谍程序，用于窃取一些信息。它到系统当中来，目的是很明确的，就是为了窃取一些东西。
  • 陷阱门：在某个系统或某个部件中设置了"机关"，使得当提供特定的输入数据时允许违反安全策略。
  • 抵赖：这是一种来自用户的攻击。比如，否认自己曾经发布过的某条信息，伪造一份对方来信等。

# P78 防火墙技术

防火墙大体可以分为网络级的防火墙和应用级的防火墙。

防火墙：

  • 网络级防火墙，工作层次比较低，但是效率比较高。
  • 应用级防火墙，工作的层次比较高，工作效率比较低。

其实防火墙技术在现实生活中也很长见，只是你不知道它是防火墙而已。比方说我们经常会发现在不同的省份经常会爆发一些禽流感猪流感之类的疫情，我们知道这种动作群体疫情的发生是很头痛的事情，因为它传染性比较强，一旦传染了就要进行捕杀，造成非常大的经济损失，所以在控制疫情的过程中，我们经常会采取隔离的措施，就是一个省份爆发了猪流感，比方如上海爆发了，其他各个省份就会切段上海到本省的生猪的运输，以杜绝这种病毒通过运输的方式传到其他省份去。比如说湖南，湖南发现了临近的省份比方说江西发生了禽流感，这个时候可以做的措施是什么呢？在江西通往湖南的各个关卡上面设置卫生检疫站，检疫的时候如何检疫，看它是不是运输的禽类的车辆，然后再看它的出发地是不是江西，看这些指标。

这些就类似于我们的网络级防火墙，在设置规则的时候，设置指定来源的IP包丢弃掉，只要是哪个IP段的可以接收，哪个IP段的不可以接收，这就与卫生检疫站是一回事，这个时候的卫生检疫站只看车辆运货物的出货单，从哪里出到哪里去，一看是从江西来的，我们的规则是不允许江西的禽类进入到湖南的市场，这个时候就拒之门外。至于车箱里面装的是什么东西，在网络层是不会去检查的，检查的是头部信息，IP头信息，换句话说，只要我运输的带病毒的禽类的车辆伪造一下出货单，如将出发地伪造为广东，目的地是长沙的农贸市场，只是途经了江西，这个时候就会通关放行，因为我们的源地址没有杜绝广东的车辆进入。

什么叫应用级防火墙呢？应用级防火墙就是开箱检查，你说是广东运过来的，那不行，你必须把车箱打开，随机抽出几只鸡出来，然后检查一下这些鸡是否患有鸡瘟，如果患有鸡瘟，有安全隐患，就杜绝你的车辆进入。这就是网络级和应用级的区别。

应用级防火墙因为要把信息拆出来看里面是什么东西，这时候效率必然就会低一些。

网络级具体又可以分为包过滤和状态检测：

  • 包过滤，所谓包过滤就是最简单的防火墙，没什么好讲的。
  • 状态检测，比如TCP/IP的连接的时候，会有连接状态信息，网络级防火墙就会对状态信息进行分析统计，仍然还是比较简单的。

应用级防火墙结构就复杂得多，其中双穴主机和屏蔽主机考试中几乎不涉及，这里不讲。而且在屏蔽子网中已经含盖了前面的形式，主要掌握屏蔽子网防火墙就行。

屏蔽子网防火墙非常独特，从微观看屏蔽子网是由多道防火墙构成，堡垒主机是第三道防火墙，所以说整个的安全性是非常高的。它是思路是什么呢？它就是要弥补整个防火墙固有的一些缺陷。

防火墙有一个特点，叫做"防外不防内"，就是说网络攻击如果说是从外部发起的，如果要穿透防火墙进入到内部，这种攻击防火墙会过滤掉。但是从内部发起的攻击，防火墙顾不到。

如同一个内网的主机A攻击主机B，主机A都不用经过防火墙就可以直接攻击主机B，防火墙顾不到。

中国有句老话，日防夜防，家贼难防，经过统计会发现造成损失的攻击有80%是由内部发起的，内部发起的并不意味着他完全是真正意义上的家贼，是因为它可能感染的木马感染了病毒，导致这类形象的发生，所以说，人们在设置防火墙的时候，希望整个结构尽可能的安全，降低安全隐患，所以组成了比较复杂的防火墙。

屏蔽子网就是这种情况，在外网和内网之间做了一个屏蔽子网区，也称为隔离区，也称为DMZ非军事化区(DMZ是英文“demilitarized zone”的缩写，中文名称为“隔离区”，也称“非军事化区”),这一个隔离区，一般放对外服务的一些服务器，如Web服务器，邮件服务器之类的，这样子做有什么好处呢？如果说外部的入侵者攻破了一道防火墙，再要进入到内部网络，还要经过一道防火墙；内部访问这些服务器也需要经过防火墙，也提高了相应的安全性。

当然，纯粹的内部发动的对内部其他服务器发生的攻击仍然难以杜绝。

屏蔽子网的安全性是最高的，DMZ是什么样的区域，里面一般放什么样的服务器，这几点要记得。

# P79 数据结构与算法基础

数据结构与算法基础这一章节对于软件设计师非常重要，上午和下午考试都会考到！算法基础是整个下午设计考题中最难的！

大家一定要花时间把这部分内容学好！

课程内容：

  • 数据与矩阵，会提到数组下标的转换问题，稀疏矩阵，上三角，下三角等类型的矩阵。
  • 线性表，在线性表里面有两种非常著名的数据结构，栈和队列！栈和队列的基本特性能及相关的应用是每次都会考到的，非常重要！
  • 广义表，了解基本的概念和操作，偶尔考到。
  • 树和二叉树，必考！树和二叉树的基本特性，用这种数据结构一般用来解决什么样的问题，有特色的二叉树的基本情况。
  • 图，了解一些概念即可。
  • 排序和查找，比较重要！涉及到的排序和查找的算法也比较多，会涉及到选择题等，排序和算法的时间复杂度和空间复杂度。下午题会涉及到这一块的程序。
  • 算法基础及常见的算法。

# P80 数组

数组这一块主要了解的是：

  • 存储地址的计算
  • 在二维数组中按行存储和按列存储的区别。

因为这一个知识点与其他章节的知识点有相关性。比方说在操作系统章节页面置换算法中缺页的问题。有的时候就要结合按行存储和按列存储这些基本理论来综合考虑。回到我们的数组主题。

如果告诉我们一个一维数组a[n]，要求某一个数组变量的地址，怎么求呢？这样来求，某个数组变量的存储地址，必须是以这个数组首元素或者说首地址为偏移来算的，第一个元素存在什么位置，然后根据每个元素会占多少空间，来推算出当前这个元素的位置在哪里。

a[i]是数组的第i个元素，整个数组的首地址是a，偏移量是i*len，len是每个元素所占的字节数，一般数组是从0开始计算下标的，所以a[0]的存储地址是a，a[1]的存储地址是a + len， a[2]的存储地址是 a + 2*len, ......

二维数组是一个表，类似于矩阵！可以按行存储或按列存储，即是先存储行还是先存储列数据。因为在我们系统当中，并不是直接开辟一个二维数组的空间，而是顺次的存储二给数组各个元素的值。按行存储是先存储第一行再存储第二行数据，按列存储是先存储第一列数据再存储第二列数据。二维数组在存储的时候，第一个元素是a[0][0],这在按行和按列存储都是一样的，但第二个元素存储就会有差异，按行存储第二个元素是a[0][1]，按列存储第二个元素是a[1][0]，所以不一样！所以公式也不一样！

示例中，a[2][3]代表a[0]这一行存储完了，a[1]这一行也存储完了，a[2][3]这一行也存储了a[2][0]、a[2][1]、a[2][2], 可以看到已经存储了2行加三个元素，a[2][3]是第14个元素，所有偏移量是 2*5+3 = 13，所有a[2][3]的存储地址是 a + 13*2。

# P81 稀疏矩阵

有了数组的基础之后，稀疏矩阵就比较好理解，对于稀疏矩阵而言经常考到的是计算某个稀疏矩阵中某一元素对应的一维数字的元素的下标，这其实跟计算偏移量是一回事。因为数组，像二维数据等存储计算机里面都是以一维的形式顺次的存储下来的，这种对应关系对于我来讲很重要！值得我们注意的地方。

什么是稀疏矩阵，如果一个矩阵当中，有大量的元素都是0，则称为稀疏矩阵。大量的元素都是0的时候，我们就会考虑存储矩阵的时候，只存储矩阵中的一部分内容就可以存储所有的有效数据，这样可以节省很多空间，所以提出了这个概念。

所以存储稀疏矩阵，一般存储的是上三角矩阵或下三角矩阵，考试的时候一般会告诉我是哪一种情况。只用存储一半的数据，另一半的数据不用存储。

如果在矩阵中大量元素是0的话，就是稀疏矩阵。

考试的时候，使用代入法来处理。不用记公式！！！随便代入几个数据，可以将错误的答案全部排除掉！

A[0,0]存在M[1]中，A[1,0]存在M[2]中，A[1,1]存在M[3]中。

通过代入i=0,j=0时，结果要是M[1]，注意数组M是下标是从1开始的，不是从0开始的。

将i=0,j=0代入四个选项中，得到：

A: M[1], B: M[0], C: M[0],D:M[1]， 这个时候就可以发现B和C选项是错误的，直接排除B和C，正确答案在A和D中。

由于A[1,0]存在M[2]中，我们再来代入i=1,j=0看结果是否是M[2]。得到：

A: M[2], B: M[1], C: M[0],D:M[1]， 这个时候其实可以不用看B和C选项，但可以再次验证B和C选项是错误的，同时发现D选项也是错误的，可以排除D，正确答案为A。

我们再来验证A[1,1]存在M[3]中，看一下代入i=1,j=1看结果是否是M[3]， 此时各项的结果是：

A: M[3], B: M[2], C: M[1],D:M[2]，可以发现A验证正确，BCD都是错误的。所以再次验证正确答案是A，因此选择A。

所以用代入法比记公式来得快一些！

# P82 数据结构的定义

数据结构的定义主要讲数据结构的概念以及数据的逻辑结构。

  • 数据结构的概念：计算机存储以及组织数据的方式。之所以研究它，是因为选择不同的数据组构，可能带来的运行效率差异会非常之大，还不说什么样的数据选择什么样的存储结构的问题，就是我们在同样的一个结构里面，稍微做调整，也可以让效率有很大的改变。比方说，在数组的存储里面，行存储和列存储在既定的处理机制之下，会有非常大的性能方面的差异，这也是我们去研究数据结构的基本的价值与意义。
  • 数据结构从逻辑层面分，可以分为：
    • 线性结构，一个个的元素连成一条线。
    • 非线性结构，又可以分为树和图，树与图的区别：树不会存在环路，图中可以存在环路（连成一个圈）。

分成以上几种类型是便于我们研究。图可以包含树，树可以包含线性结构。

# P83 顺序表和链表

线性表是线性结构的基本表现，它有两种存储方式：顺序表存储和链表存储。下面看两种方式有什么差别？

  • 顺序表存储：顺序表存储就是开辟了连接的存储空间，顺次地把表存进来，其实就是采用的一维数组的方式来存储信息。
  • 链表存储：链表的每一个数据单元是包含了存储数据的地方以及存储指针的地方，为什么要有存储指针的地方呢，是因为这一系列的空间不见得是连续的，把每一个离散的空间，用指针把它们连接起来，连接起来之后就形成了链表。

顺序表是开辟的连接的空间，你要10个空间，这个连接空间必须要能够存储下这10个元素，所以从形态上来讲是不一样的。

链表又进一步可以分成单链表、循环链表、双向链表。

  • 单链表：只有一套指针，而且指针是单向的指过去的，头结点指向第一个元素，第一个元素指向第二个元素，第二个元素指向第三个元素，.... 依次类推。要定位某一元素时，需要从头开始，逐个查找下去。
  • 循环链表：把尾元素的指针指向头结点。定位任何元素时只需要续续next就行。
  • 双向链表：可以双向移动的，有一套指针是从头往后连接起来，还在一套指针是逆向的连接起来，所以指针即可指向后一个元素又可以指向前一个元素。可以往两个方向走。

链表中包含指针。

链表的操作。

链表的操作比较复杂！

单链表删除操作：删除a2的话，需要使 p->next = q->next

单链表插入操作：在a1与a2之间插入x，s->next = p->next ; p->next = s

双向链表的删除和插入原理与单链接类似，涉及到两套指针的变化。

就是对链表中的指针进行新的赋值。

单链表区分有头结节和没有头结节的链表。有头结节的好处是，我们单独有一个头结节，这个头结节不存储任何信息，头结点的下一个结点才存储信息，引入头结点的好处是，可以令所有结点的操作方式变成一致的，如果头结点存储了数据，头结点往往要采取不同的处理方式，仅此而已，其他的东西不需要了解。

# P84 顺序存储和链式存储

比较顺序存储和链式存储的差异，主要是从两个大的维度以及很多小的方面进行比较。

  • 存储密度：顺序存储=1，更优，链式存储<1, 1其实就是100%,如开辟一段连续的空间用来存储顺序表，这一段空间所有的位置都是用来存储我们需要的数据信息，没有空间上的浪费，所以利用率达到了100%，也就是1。而链式存储则不是这样的，如果链式存储有10个节点，每个节点存储了相应的数据,比如2个字节的数据，但这个节点至少需要3到4个字节的空间，因为需要存储指针，指针的存储也需要占空间，比如说每个指针占一个字节，这样一个节点就需要3个字节空间，两个字节存储数据，一个字节存储地址信息（指针），这个时候存储密度就2/3 = 66.6%。存储密度来讲，顺序存储密度比链式存储密度高。
  • 容量分配：容量分配方面，顺序存储要弱一些，顺序存储需要事先知道需要多少空间，而链式存储不需要事先知道要多少空间，存储空间可以动态分配，如果只存储一个信息，只用分配一个节点就行，当需要将第二个信息存储时，只用再分配第个节点来存储这个信息即可。所以链式存储更优，可以动态的改变分配。
  • 时间性能：
    • 查找运算：用顺序存储比较方便，链式存储要差一些。在内容没有排序的情况下，它们都是从第一个开始匹配，再开始匹配第二个，....，如果内容已经排序了的话，涉及到二分查找法的话，顺序存储则更优一些。普遍情况下再者时间复杂度是一样的，都是O(n/2)。
    • 读运算：顺序存储更优，比如要读取A[5]这个元素，顺序表直接读取A[5]即可，而链式表要先读取第一个元素，然后再next,再next，再next,再next,才读取到A[5]这个元素。这就是链表的局限性，只能一格一格的移动，不像顺序存储可以直接定位。
    • 插入运算：插入运算反而是链式存储更优一些。链式存储插入时，只需要在局部进行一个小的调整。但顺序表不一样，如果要在中间插入一个元素，需要把后面的每一个元素都朝后面移动一位，然后再将需要插入的元素插入进来。影响比较大。
    • 删除运算：删除运算操作类似于插入运算，链式存储更优一些。

# P85 栈和队列

  • 队列：先进先出。队列入队顺序是1，2，3，4，5的话，入队是12345的顺序，出队的话，也是12345的顺序。顺次的出去。队列是两端都在操作。
  • 栈：先进后出。只有一端可以操作。比如，入栈时，先入的是1，2，3，4，5，这个时候出栈的话，先出5，再出4，再出3，再出2，再出1，类似于将东西放在箱子里面，先放进去的东西放在箱子底下，后放进去的东西放在箱子上面，然后从箱子里面拿东西出来的时候，只能先拿上面的，再拿下面的。

  • 循环队列：队列走着走着双回到队头了。队空条件：head = tail，队满条件：(tail + 1)%size = head。 如队可以存5个数，队头是0，队中依次存了1，2，3，(空)，这个时候就满了，最后一个不存储数据，（4+1)%5 = 0。

以某种情况入栈，出栈的顺序可以是很多种情况的。入栈后可以马上出栈的！！！！！

看最终输出的序列，在队列中的排列情况，再看这个队列情况在入队是否是有可能的形成这种局面，不可能的就说明这种方式是异常的。

看示例中，所有选项都是e4最先出来，可以不用考察e4，只用考察e1,e2和e3三个元素的入队和出队了。

A选项中，出队顺序是e3、e2、e1，入队的话，可以先从左端或右端将e1入队，然后从左端将e2入队，再从左端将e3入队，这样在队列中的序列就是e3、e2、e1，最后出队都从左端出队，依次出队是e3、e2、e1，满足要求。所以可以排除选项A。

B选项中，出队顺序是e2、e1、e3，入队的话，可以先从左端或右端将e1入队，然后从左端将e2入队，再从右端将e3入队，这样在队列中的序列就是e2、e1、e3，最后出队都从左端出队，依次出队是e2、e1、e3，满足要求。所以可以排除选项B。

C选项中，出队顺序是e3、e1、e2，入队的话，可以先从左端或右端将e1入队，然后从右端将e2入队，再从左端将e3入队，这样在队列中的序列就是e3、e1、e2，最后出队都从左端出队，依次出队是e3、e1、e2，满足要求。所以可以排除选项C。

D选项中，出队顺序是e2、e3、e1，入队的话，可以先从左端或右端将e1入队，然后从左端将e2入队，这个时候再将e3入队的话，无论从左端入队还是从右端入队，得到的序列都不是e2、e3、e1，从左端入队的话，得到的序列是e3、e2、e1，从右端入队的话，得到的序列是e2、e1、e2，即无法得到序列e2、e3、e1，因此不满足要求。所以得不到的输出序列应该选择选项D。

# P86 广义表

  • 广义表是由n个表元素组成的有限序列。广义表是线性表的推广。
  • 广义表中有多个元素，每个元素又可以是一个广义表。类似于Python中的列表！
  • 广义表的长度：长度就是最外层的元素个数
  • 广义表的深度：深度就是括号的深度，就是嵌套的次数，类似于文件夹的深度。

表头是广义表中第一个元素，表尾是除表头外所有的元素。

  • head操作：取表头，最外层的第一个元素！
  • tail操作：取表尾，除了表头之外其他所有元素组成的广义表。

# P87 树与二叉树

  • 结点：图中1、2、3、...，都是节点。

  • 结点的度：结点有几个孩子节点，孩子节点数就是结点的度。

    • 节点1，有两个孩子节点（2和3）,所以1号节点的度为2。
    • 节点2，有两个孩子节点（4和5）,所以2号节点的度为2。
    • 节点3，有一个孩子节点（6）,所以3号节点的度为1。
    • 节点6，有两个孩子节点（7和8）,所以6号节点的度为2。
    • 节点7，有0个孩子节点, 所以7号节点的度为0。

  • 树的度：在一个树当中，所有节点度最高的节点的度称树的度。

    • 可以看到所有节点度数最高的是2，因此整个树的度是2。
    • 如果在节点2下面增加节点9，与节点4和节点5并列，这时节点2的度就是3，此时所有节点的度最高

的就是节点2，度为3，因此此时树的度就是3。

  • 叶子节点：没有孩子节点的都是叶子节点。

    • 如4、5、7、8都是叶子节点。

  • 分支节点：有相应的分支的节点。

    • 如2、3、6都是分支节点。

  • 内部节点：度不为0的结点。

    • 如2、3、6都是内部节点。

  • 树的层次：也就是树的高度。

    • 根节点1在第一层。
    • 2、3中间节点在第二层。
    • 4、5叶子节点，6中间节点在第三层。
    • 7、8叶子节点在第四层。
    • 即树的层次或者树的高度为4。

# P88 满二叉树和完全二叉树

  • 满二叉树：整颗树没有缺失的节点，所有的节点要么有两个子节点，要么本身就叶子节点（没有孩子），没有缺失节点二叉树叫满二叉树。
  • 完全二叉树：除了最底下一层是叶子节点，上面各层都是满二叉树，底下一层从左到右排列，左边都是满的（中间不能有缺失），缺失的只是右边的。

# 二叉树的重要特性

  • 在二叉树的第i层上最多有2^(i - 1)个节点（i >= 1)。最上层根节点最多为1个节点，第二层最多有2个节点，第三层最多有2^(3 - 1) = 4个节点。

完全二叉树提出来可以方便我们计算。

# P89 二叉树遍历

# 树与二叉树遍历

  • 层次遍历：从根节点开始，从最上层依次向下遍历，从上到下从左到右遍历。
  • 根据根节点在什么时候访问，又可以分为前序遍历、中序遍历和后序遍历。
  • 前序遍历：根、左、右，先访问根节点再访问左子树再访问右子树。
  • 中序遍历：左、根、右，先访问左子树，再访问根节点，最后访问右子树。
  • 后序遍历，左，右，根，先访问左子树，再访问右子树，最后访问根节点。
  • 遍历时，各子树也需要按相同的方式遍历。

我们来看这几种遍历方式看一下遍历结果。

  • 图中层次遍历结果是：1（第一层）、2、3（第二层）、4、5、6（第三层）、7（第四层）、8（第五层）。
  • 前序遍历：根左右。1、2、4、5、7、8、3、6。
  • 中序遍历：左根右。4、2、7、8、5、1、3、6。
  • 后序遍历：左右根。4、8、7、5、2、6、3、1。
  • 注意一点，遍历各子树时，也需要按相同的遍历方式进行遍历。

# P90 反序构造二叉树

有前序和中序，或者中序或后序，都能还原二叉树。

如果只有前序和后序是不能还原二叉树。

由前序序列ABHFDECG，前序遍历是先访问根节点再访问左子树最后访问右子树，可知道根节点是A。

再看中序序列，中序是先访问左子树再访问根节点最后访问右子树，所以可以知道根节点左侧的序列HBEDF是左子树上面的节点，GC是右子树上面的节点。

然后再看前序序列ABHFDE，可知道B是左子树的根节点，所以可以在中序序列HBEDF中确定H是B的左子树，EDF是B的右子树。

再回到前序序列BHFDE中，访问B节点后，再访问B的左节点H，再访问B的右子树FDE，由于是按前序遍历的，那么F是B的右子要的根节点。

再在中序序列HBEDF中，F是根节点，那么ED肯定是左子树节点。

再看前序序列FDE，可以知道D是F左子树的根节点。

再看中序序列EDF，由于D是F左子树的根节点，那么E是D左子树。

这样左侧的各个节点就推理出来了。

同样可以看右侧的子树：

在前序序列中右侧子树是CG，在中序序列中右侧子树是GC，即可以知道右侧子树中C是子树的根节点，G是C子树的左节点。

最终推理出来的二叉树如图：

# P91 树转二叉树

转换原则：

  • 树的结点的孩子结点，都会转成左子树结点。
  • 树的结点的兄弟结点，都会转成右孩子结点。

如示例中，1转换成二叉树的根节点，2、3、4都是根节点1的孩子节点，因此2、3、4都会转换成1的左子树结点。

同时，2、3、4是兄弟结点，1的左子树只能有一个根节点，因些将2作为1的左子树的根结点，3、4是2的兄弟结点，因此3和4都会转换成2的右孩子结点。因此3会做会2的右孩子的节点的根结点，4做为3结点的右结点。

简单理解，兄弟结点转换成类似\的转换，第一个兄弟结点放在左上角、最后一个兄弟结点放在右下角即可，最后把各结点连接起来。

# P92 排序二叉树或查找二叉树

排序二叉树有以下特点：

  • 左子树的数据的值都小于根结点的值。
  • 右子树的数据的值都大于根结点的值。

查找二叉树是比较特殊的二叉树。查找二叉树又称为排序二叉树。

注意，查找二叉树中，没有两个值是一样的！！！

查找二叉树的价值意义：可以极大的提高查询效率。

查找的时候，每次先与根节点比较，如果要查找的数据比根节点小，则这个数在左子树中，如果要查找的数据比根节点大，则这个数在右子树中。

# P93 最优二叉树（哈夫曼树）

最优二叉树又称哈夫曼树，哈夫曼树用于哈夫曼编码，哈夫曼编码是一种压缩编码方式，能够让原始信息的编码长度变得更短一些，从而节省存储空间和传输带宽，是一种无损压缩的压缩方式。(无损是指压缩后可以还原！)

基本概念：

  • 树的路径长度：树中这些路径一段一段的累加起来的长度。

  • 权：某个叶子节点上面有个值，代表某种数据出现的频度，就是权值，权。

  • 带权路径长度：先计算节点的路径长度，再乘以权值。

    • 如示例中，最左侧的2的带权路径长度为：路径长度2 * 权值2 = 4。
    • 最下面的4的带权路径长度为：路径长度3 * 权值4 = 12。
    • 最下面的8的带权路径长度为：路径长度3 * 权值8 = 24。

  • 树的带权路径长度：将所有叶子节点的带权路径长度加起来得到的就是树的带权路径长度。中间结点都是我们构建出来的，不是原始数据。

注意，只用计算叶子节点的带权路径长度。因为只有叶子节点是原始数据，中间节点都是我们构建出来的，不需要计算！

可以发现左边的树的带权路径长度 = 2*2 + 3*4 + 3*8 + 1*1 = 41。而右边的树的带权路径长度 = 2*4 + 3*1 +3*2 + 1*8 = 25。

构造哈夫曼树：

假设有一组数值，5，29，7，8，14，23，3，11,请尝试构造哈夫曼树。

将权值最两的小个值选出构成一个小树，如将5和3选出，构成一个小树，然后将选出的数据从原来的数据中划掉，再将他们的和8加入到原来的数据中。

再在新序列中查找两个最小的值构造一个小树！

左侧的树： 3 ---> 8 <--- 5， 将3和5从原来序列中移除，并将8加入到序列中，序列变成了7, 8, 8, 11, 14, 23, 29。

然后再在新的序列中选择两个最小的数字形成一个新的子树，选7和8,对于等值的两个8，选哪一个都无所谓，将7和之前形成的子树再构成一颗树。

就形成了左侧的树： image-20210131201953244

然后将7和8从刚形成的序列中移除，并将和15加入到序列中，形成新的序列8, 11, 14, 15, 23, 29。

然后再从新的序列中选择两个最小的值形成一颗子树。

这时8和11是最小的结点，将8和11做为一个子树。这样得到另一颗子树， 8 ---> 19 <--- 11。

这时将8和11从序列中移除，并将19加入到序列中，形成新的序列14, 15, 19, 23, 29。

然后再从新的序列中取出最小的两个值14和15，15是左侧子树形成的和，因些将14并入到左侧子树中。

形成新的子树是：

​ image-20210131203359391

将14和15从序列中移除，并将和29加入到序列中，形成新的序列19, 23, 29, 29。

这时从新的序列中取出最小的两个值19和23，19是之前左侧子树形成的和，因此将23并入到右侧子树中，此时，右侧子树为：

image-20210131203658054

然后将19和23从序列中移除，并将和42加入到序列中，形成新的序列29, 29, 42。

此时从新的序列中取出最小的两个值29和29，一个29是左侧树形成的和，因此将29并入到左则的树中，此时，左侧子树为：

image-20210131204127556

然后将29和29从序列中移除，并将和58加入到序列中，形成新的序列42, 58。

这时候只剩下最后两个数据，需要将这两个数据构成一颗树，58是左侧子树形成的和，42是右侧子树形成的和，因此此时要将这两个和合在一起构建一颗树。最终形成的树为：

image-20210131204422792

这样就构建了啥夫曼树了。

这样整个哈夫曼树的带树路径长度 = 5*5 + 3*5 + 7*4 + 14*3 + 8*3 + 11*3 + 29*2 + 23*2 = 271。

# P94 线索二叉树

image-20210202073136566

  • 线索二叉树是在二叉树的基础上会有虚线的箭线，把很多节点串起来，这就是线索二叉树。
  • 为什么要提出线索二叉树呢？是因为我们可以发现在二叉树中，有很多节点都是空闲的状态，有很多指针都是空的，没有利用起来。如此处展示的二叉树，叶子结点D左子树和右子树都是空的，E的右子树是空的，H的左子树和右子树都是空的，F的左子树和右子树都是空的，G的左子树是空的，I的左子树和右子树都是空的。
  • 人们就想能不能把这些空闲的资源利用起来，利用来做什么事情呢？主要方便遍历。
  • 正是因为方便遍历，所以提出了前序、中序和后序线索二叉树，分别对应二叉树的前序、中序和后序遍历。
  • 前序线索二叉树中的箭线是按前序遍历方式生成的。其中左子树的指针指向当前结点的遍历的前序结点，右子树的指针指向当前结点的遍历的后序结点。
  • 对于左侧的前序线索二叉树，D空出两个指针了。前序遍历访问顺序是根左右，所以二叉树的访问顺序依次是A、B、D、E、H、C、F、G、I。所以D的前驱节点是B，D的后续结点是E，所以从D出来绿色虚线指向B，红色虚线指向E。同样H的前驱是E，H的后续是C,因此有绿色虚线指向E，红色虚线指向C。加了这些线索后，能够让我们的遍历变得更加快捷。
  • 这就是线索二叉树的线索的价值与意义。

# P95 平衡二叉树

image-20210202075205083