一、计算机组成与系统结构

1.1、数据的表示

R进制转十进制使用按权展开法，其具体操作方式为：将R进制数的每一位数值用 R k R^k Rk形式表示，即幂的底数是R，指数为k，k与该位和小数点之间的距离有关。当该位位于小数点的左边，k值是该位和小数点之间数码的个数，而当该位位于小数点右边，k值是负值，其绝对值是该位和小数点之间数码的个数加1。

• 十进制转R进制使用短除法。

• 二进制转八进制。

  10 \textcolor{red}{10} 10 001 \textcolor{blue}{001} 001 110 \textcolor{green}{110} 110=> 2 \textcolor{red}{2} 2 1 \textcolor{blue}{1} 1 6 \textcolor{green}{6} 6

• 二进制转十六进制。

  1000 \textcolor{red}{1000} 1000 1110 \textcolor{green}{1110} 1110=> 8 \textcolor{red}{8} 8 E \textcolor{green}{E} E

1.1.1、原码

**原码就是符号位加上真值的绝对值，**即用第一位表示符号，其余位表示值。比如：如果是8位二进制：

[+1]原= 0000 0001

[-1]原= 1000 0001

第一位是符号位，因为第一位是符号位，所以8位二进制数的取值范围就是：（即第一位不表示值，只表示正负。）

[1111 1111 , 0111 1111]即[-127 , 127]

数值表示范围： − 2 n − 1 − 1 ∼ 2 n − 1 − 1 -2^{n-1}-1\sim2^{n-1}-1 −2n−1−1∼2n−1−1

1.1.2、反码

反码的表示方法：

• 正数的反码是其本身；

• 负数的反码是在其原码的基础上，符号位不变，其余各个位取反。

[+1] = [0000 0001]原= [0000 0001]反

[-1] = [1000 0001]原= [1111 1110]反

数值表示范围： − 2 n − 1 − 1 ∼ 2 n − 1 − 1 -2^{n-1}-1\sim2^{n-1}-1 −2n−1−1∼2n−1−1

1.1.3、补码

补码的表示方法：

• 正数的补码就是其本身；

• 负数的补码是在其原码的基础上，符号位不变，其余各位取反，最后+1。(即在反码的基础上+1)

[+1] = [0000 0001]原= [0000 0001]反= [0000 0001]补

[-1] = [1000 0001]原= [1111 1110]反= [1111 1111]补

数值表示范围： − 2 n − 1 ∼ 2 n − 1 − 1 -2^{n-1}\sim2^{n-1}-1 −2n−1∼2n−1−1

1.1.4、移码

不管正负数，只要将其补码的符号位取反即可。

[+1] = [00000001]原 = [00000001]反 = [00000001]补
[-1] = [10000001]原 = [11111110]反 = [11111111]补

1.1.5、浮点数运算

浮点数表示： N = M ∗ R e N = M * R^e N=M∗Re，其中M称为尾数，e是指数，R为基数。

1.2、计算机结构

计算机的基本硬件系统由运算器、控制器、存储器、输入设备和输出设备5大部件组成。

运算器、控制器等部件被集成在一起统称为重要处理单元（CPU）。

• 运算器
  1. 算数逻辑单元ALU
  2. 累加寄存器AC
  3. 数据缓冲寄存器DR
  4. 状态条件寄存器PSW
• 控制器
  1. 程序计数器PC
  2. 指令寄存器IR
  3. 指令译码器ID
  4. 时序部件

1.2.1、计算机体系结构分类-Flynn

1.2.2、CISC与RISC

1.3、流水线

流水线是指在程序执行时多条指令重叠进行操作的一种准并行处理实现技术。各种部件同时处理是针对不同指令而言的，它们可同时为多条指令的不同部分进行工作，以提高各部件的利用率和指令的平均执行速度。

• 指令流水线：计算机中一条指令的执行需要若干步，通常采用流水线技术实现指令的执行，以提高CPU性能。
• 运算操作流水线：计算机在执行各种运算操作时也可以以应用流水线技术来提高运算速度。

1.3.1、流水线计算

• 流水线周期为执行时间最长的一段

• 流水线指令运行时间的计算：

  一条指令执行时间 + (指令条数 - 1) * 流水想周期

  1. 理论公式：

     ( t 1 + t 2 + . . . + t k ) + ( n − 1 ) ∗ Δ t (t1+t2+...+tk)+(n-1)*\Delta t (t1+t2+...+tk)+(n−1)∗Δt

  2. 实践公式：

     ( k + n − 1 ) ∗ Δ t (k+n-1)*\Delta t (k+n−1)∗Δt

     其中 Δ t \Delta t Δt为最慢一段所需的时间

1.3.2、流水线吞吐率计算

流水线的吞吐率（Though Put rate，TP）是指在单位时间内流水线所完成的任务数量或输出的结果数量。计算流水线吞吐率的最基本的公式如下：
T P = 指令条数 流水线执行时间 {TP} = {指令条数 \over 流水线执行时间} TP=流水线执行时间指令条数​
流水线最大吞吐率：
T P max ⁡ = lim ⁡ n → ∞ n ( k + n − 1 ) Δ t = 1 Δ t {TP_{_{\max }}} = \mathop {\lim }\limits_{n \to \infty } {n \over {(k + n - 1)\Delta t}} = {1 \over {\Delta t}} TPmax​​=n→∞lim​(k+n−1)Δtn​=Δt1​

1.3.3、流水线的加速比

完成同样一批任务，不使用流水线所用的时间与使用流水线所用的时间之比称为流水线的加速比。计算流水线加速比的基本公式如下：
S = 不使用流水线执行时间 使用流水线执行时间 {{S}}={不使用流水线执行时间 \over 使用流水线执行时间} S=使用流水线执行时间不使用流水线执行时间​

1.3.4、流水线的效率

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

计算流水线效率的公式为：
E = n 个任务占用的时空区 k 个流水段的总的时空区 = T 0 k T k {{E}}={{n个任务占用的时空区} \over k个流水段的总的时空区}={T_0 \over kT_k} E=k个流水段的总的时空区n个任务占用的时空区​=kTk​T0​​

• 效率与吞吐率的关系：
  E = T P ∗ Δ t E=TP*\Delta t E=TP∗Δt

• 效率与加速比的关系：
  E = S k {E}={S\over k} E=kS​

1.4、计算机层次化存储结构

1.4.1、Cache

• Cache的功能：提高CPU数据输入输出的速率，突破冯•诺伊曼瓶颈，即CPU与存储系统间数据传送带宽限制。

• 在计算机的存储系统体系中，Cache是访问速度最快的层次。

• 使用Cache改善系统性能的依据是程序的局部性原理。

如果以h代表对Cache的访问命中率， t 1 t_1 t1​表示Cache的周期时间， t 2 t_2 t2​表示主存储器周期时间，以读操作为例，使用“Cache+主存储器”的系统的平均周期为 t 3 t_3 t3​，则：
t 3 = h ∗ t 1 + ( 1 − h ) ∗ t 2 {{t_3}}=h*t_1+(1-h)*t2 t3​=h∗t1​+(1−h)∗t2
其中，(1-h)又称为失效率（未命中率）。

Cache的读写过程

• 写直达：当要写Cache时，数据同时写回主存储器，有时也称为写通。
• 写回：CPU修改Cache的某一行后，相应的数据并不会立即写入主存储器单元。而是当该行被从Cache中淘汰时，才把数据写回到主存储器中。
• 标记法：对Cache中的每一个数据设置一个有效位。

地址映像

常见的映像方法有直接映像、相联映像和组相联映像。

地址映像是将主存与Cache的存储空间划分为若干大小相同的页（或称为块）。

例如某机的主存容量为1GB，划分为2048页，每页512KB；Cache容量为8MB，划分为16页，每页512KB。

1.4.2、局部性原理

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

1.4.3、主存分类

• 随机存取存储器
  • DRAM（Dynamic RAM，动态RAM）-SDRAM
  • SRAM（Static RAM，静态）
• 只读存储器
  • MROM（Mask ROM，掩模式ROM）
  • PROM（Programmable ROM，一次可编程ROM）
  • EPROM（Erasable PROM，可擦除的PROM）
  • 闪速存储器（flash memory，闪存）

1.4.4、主存编址

编址

芯片的拼接

如果主存容量为16M字节，且按字节编址，表示该主存地址至少需要多少位？

16M*8位的芯片，存储容量=存储单元个数×存储字长， 2 20 = 1 M 2^{20}=1M 220=1M， 2 4 = 16 2^4=16 24=16，故表示该主存地址至少需要24位。

内存按字节编址，地址从A4000H到CBFFFH，共有多少字节？若用存储容量为32K*8 bit的存储芯片构成该内存，至少需要多少片？

CBFFFH-A4000H+1H=27FFFH+1H=28000H
28000 H = 2 ∗ 16 ∗ 16 ∗ 16 ∗ 16 + 8 ∗ 16 ∗ 16 ∗ 16 + 0 ∗ 16 ∗ 16 + 0 ∗ 16 + 0 ∗ 1 = 163840 28000H=2*16*16*16*16+8*16*16*16+0*16*16+0*16+0*1=163840 28000H=2∗16∗16∗16∗16+8∗16∗16∗16+0∗16∗16+0∗16+0∗1=163840

163840 1024 = 160 {163840\over1024}=160 1024163840​=160

160 32 = 5 {160\over32}=5 32160​=5

综上，共有160K字节，至少需要5片。

1.4.5、磁盘结构与参数

存储相关计算问题

计磁道数 = ( 外半径 − 内半径 ) ∗ 道密度 ∗ 记录面数 计磁道数=(外半径-内半径)*道密度*记录面数 计磁道数=(外半径−内半径)∗道密度∗记录面数

注意：硬盘的第一面与最后一面是保护用的，要减掉。

例如：4个双面的盘片的记录面数是4*2-2=6。
非格式化容量 = 位密度 ∗ π ∗ 最内圈直径 ∗ 总磁道数 非格式化容量=位密度*\pi*最内圈直径*总磁道数 非格式化容量=位密度∗π∗最内圈直径∗总磁道数
注意：位密度是每道不同的，但每道的容量是相同的，0到最外面的磁道，其密度最小。
格式化容量 = 每道扇区数 ∗ 扇区容量 ∗ 总磁道数 格式化容量=每道扇区数*扇区容量*总磁道数 格式化容量=每道扇区数∗扇区容量∗总磁道数

平均数据传输速率 = 每道扇区数 ∗ 扇区容量 ∗ 盘片转数 平均数据传输速率=每道扇区数*扇区容量*盘片转数 平均数据传输速率=每道扇区数∗扇区容量∗盘片转数

平均数据传输速率 = 最内圈直径 ∗ π ∗ 位密度 ∗ 盘片转数 平均数据传输速率=最内圈直径*\pi*位密度*盘片转数 平均数据传输速率=最内圈直径∗π∗位密度∗盘片转数

存取时间 = 寻道时间 + 等待时间 ( 平均定位时间 + 转动延迟 ) {{存取时间}}={{寻道时间}}+{{等待时间(平均定位时间+转动延迟)}} 存取时间=寻道时间+等待时间(平均定位时间+转动延迟)

注意：

• 寻道时间是指磁头移动到磁道所需的时间；
• 等待时间为等待读写的扇区转到磁头下方所用的时间。

磁带存储是一种顺序存取设备，存取时间长，容量大，现在常用于备份。根据其读写方式的不同，它通常包括两种：

• 启停式：以文件块的形式存放信息，数据块间有空白块，其磁道数就是磁头数。
• 数据流式：结构简单、价格低、速度快。它是串行逐道记录信息，每次读写1位。

其相关的性能公式如下：
数据传输速率 ( B / s ) = 磁带记录密度 ( B / m m ) ∗ 带速 ( m m / s ) 数据传输速率(B/s)=磁带记录密度(B/mm)*带速(mm/s) 数据传输速率(B/s)=磁带记录密度(B/mm)∗带速(mm/s)

B 1 = ( 字节数 / 记录 ) ∗ 块因子 / 记录密度 B1=(字节数/记录)*块因子/记录密度 B1=(字节数/记录)∗块因子/记录密度

数据块长度 = B 1 ( 记录数据所需长度 ) + B 2 ( 块间间隔 ) 数据块长度=B1(记录数据所需长度)+B2(块间间隔) 数据块长度=B1(记录数据所需长度)+B2(块间间隔)

R ( 有效时间 ) = ( N ∗ 字节数 / 记录 ) / 传输速度 R(有效时间)=(N*字节数/记录)/传输速度 R(有效时间)=(N∗字节数/记录)/传输速度

D ( 间隔时间 ) = 块间隔总长 / 带速 = [ ( N / 块化因子 ) ∗ ( 块间间隔 ) ] / 带速 D(间隔时间)=块间隔总长/带速=[(N/块化因子)*(块间间隔)]/带速 D(间隔时间)=块间隔总长/带速=[(N/块化因子)∗(块间间隔)]/带速

读 N 条记录所需的时间： T = S ( 启停时间 ) + R + D 读N条记录所需的时间：T=S(启停时间)+R+D 读N条记录所需的时间：T=S(启停时间)+R+D

1.5、总线

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

• 内部总线

• 系统总线

  • 数据总线
  • 地址总线
  • 控制总线

• 外部总线

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

1.6.1、什么是检错和纠错

检错：发现错误。

纠错：发现错误并给以纠正。

1.6.2、什么是码距

一个编码系统的码距是整个编码系统中任意（所有） 两个码字的最小距离。

• 若用1位长度的二进制编码。若A=1，B=0.这样A，B之间的最小码距为1.
• 若用2位长度的二进制编码，若以A= 11，B=00为例，A，B之间的最小码距为2.
• 若用3位长度的二进制编码，可选用111，000作为合法编码，A，B之间的最小码距为3.

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

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

1.6.3、循环校验码CRC

编码译码的方法为：

• 令r为 生成多项式G(x)的阶，将r个“0”附加在信息（数据）元的低端，使其长度变为k+r位，相当于多项式 x y ∗ m ( x ) x^y*m(x) xy∗m(x)；
• x y ∗ m ( x ) + G ( x ) [ m o d 2 ] x^y*m(x)+G(x)[mod2] xy∗m(x)+G(x)[mod2]，得余数；
• x y ∗ m ( x ) x^y*m(x) xy∗m(x)与余数对应位异或，得编码信息T(x)。
• 接收器收到发来的编码信息后，用这个编码信息除以同一个生成多项式G(x)，（注意是同一个生成多项式），而且用模2除法。若余数为0，则表示接收到正确的编码信息，否则该编码有错。
• 把接收到的正确的编码信息T(x)去掉尾部r位，即得到数据信息M(x)。

什么是模2除法，它和普通的出发有何区别？

模2除法是指在做除法运算的过程中不计其进位的除法。

1.6.4、海明校验码

海明码：本质也是利用奇偶性来检错和纠错的校验方法，构成方法是在数据位之间的确定位置上插入k个校验位，通过扩大码距实现检错和纠错。

设数据位是n位，校验位是k位，则n和k必须满足以下关系： 2 k − 1 > = n + k 2^k-1>=n+k 2k−1>=n+k

设数据位是n位，校验位是k位，则n和k必须满足关系： 2ᵏ-1>=n+k

设有数据为8位，那么 2⁴-1=15>8+4=12,则校验位为4位，即这个海明码长12位

令信息位为D7,D6,D5,D4,D3,D2,D1,D0,信息位从高往低占据编码位；
令校验位为P3,P2,P1,P0,校验位P0=2⁰=1，P1=2¹=2，P2=2²=4，P3=2³=8；
形成的海明码编码过程如下：

信息位D7的位数为12，12=8+4，所以D7的校验位组为P3（位数：8）和P2（位数：4），即信息位的位数=校验位组的位数之和。

由上表可得，P0参与了D0,D1,D3,D4,D6的检验，其他由此类推
P0=D0⊕D1⊕D3⊕D4⊕D6
P1=D0⊕D2⊕D3⊕D5⊕D6
P2=D1⊕D2⊕D3⊕D7
P3=D4⊕D5⊕D6⊕D7

这样子就可以算出整个海明码的值了。

例

设数据为01101001，求海明码。

数据位为8，则2⁴-1=15>8+4=12,则校验位为4位，即这个海明码长12位；
D7D6D5D4D3D2D1D0=01101001；
P0=2⁰=1，P1=2¹=2，P2=2²=4，P3=2³=8；
P0=D0⊕D1⊕D3⊕D4⊕D6=1⊕0⊕1⊕0⊕1=1
P1=D0⊕D2⊕D3⊕D5⊕D6=1⊕0⊕1⊕1⊕1=0
P2=D1⊕D2⊕D3⊕D7=0⊕0⊕1⊕0=1
P3=D4⊕D5⊕D6⊕D7=0⊕1⊕1⊕0=0

则海明码为011001001101

1.7、输入输出技术

二、系统可靠性分析与设计

2.1、串联系统与并联系统

串联

• 可靠度

R = R 1 ∗ R 2 ∗ . . . ∗ R n {{R}}={{R_1*R_2*...*R_n}} R=R1​∗R2​∗...∗Rn​

λ = λ 1 + λ 2 + . . . + λ n \lambda = \lambda _1+\lambda _2 +...+\lambda_n λ=λ1​+λ2​+...+λn​

并联

• 可靠度

R = 1 − ( 1 − R 1 ) ∗ ( 1 − R 2 ) ∗ . . . ∗ ( 1 − R n ) R=1-(1-R_1)*(1-R_2)*...*(1-R_n) R=1−(1−R1​)∗(1−R2​)∗...∗(1−Rn​)

μ = 1 1 λ ∑ j = 1 n 1 j \mu = {1 \over {{1 \over \lambda }\sum\limits_{j = 1}^n {{1 \over j}} }} μ=λ1​j=1∑n​j1​1​

2.2、模冗余系统与混合系统

R = ∑ i = n + 1 m C m j ∗ R 0 i ( 1 − R 0 ) m − i R = \sum\limits_{i = n + 1}^m {C_m^j} * R_0^i{(1 - {R_0})^{m - i}} R=i=n+1∑m​Cmj​∗R0i​(1−R0​)m−i

R ∗ ( 1 − ( 1 − R ) 3 ) ∗ ( 1 − ( 1 − R ) 2 ) R*(1-(1-R)^{{3}})*(1-(1-R)^{{2}}) R∗(1−(1−R)3)∗(1−(1−R)2)

三、操作系统

3.1、进程管理

3.1.1、PV操作

• 临界资源：诸进程间需要互斥方式对其进行共享的资源，如打印机、磁带机等
• 临界区：每个进程中访问临界资源的那段代码称为临界区
• 信号量：是一种特殊的变量

3.1.2、死锁问题

进程管理是操作系统的核心，但如果设计不当，就会出现死锁的问题。如果一个进程在等待一件不可能发生的事，则进程就死锁了。而如果一个或多个进程产生死锁，就会造成系统死锁。

3.1.3、银行家算法

银行家算法：分配资源的原则

• 当一个进程对资源的最大需求量不超过系统中的资源数时可以接纳该进程
• 进程可以分期请求资源，但请求的总数不能超过最大需求量
• 当系统现有的资源不能满足进程尚需资源数时，对进程的请求可以推迟分配，但总能使进程在有限的时间里得到资源。

3.2、存储管理

页式存储组织

页号|页内地址

• 优点：利用率高，碎片小，分配及管理简单
• 缺点：增加了系统开销；可能产生抖动现象

高级程序语言使用逻辑地址；

运行状态，内存中使用物理地址。

段式存储组织

段式存储：按用户作业中的自然段来划分逻辑空间，然后调入内存，段的长度可以不一样。

段号|段内地址

• 优点：多道程序共享内存，各段程序修改互不影响
• 缺点：内存利用率低，内存碎片浪费大

段页式存储组织

段页式存储：段式与页式的综合体，再分页，1个程序有若干个段，每个段中可以有若干页，每个页的大小相同，但每个段的大小不同。

• 优点：空间浪费小、存储共享容易、存储保护容易、能动态连接
• 缺点：由于管理软件的增加，复杂性和开销也随之增加，需要的硬件以及占用的内容也有所增加，使得执行速度大大下降

页面置换算法

• 最优（Optimal，OPT）算法
• 随机（RAND）算法
• 先进先出（FIFO）算法：有可能产生“抖动”
• 最近最少使用（LRU）算法：不会“抖动”，LRU的理论依据是“局部性原理”
• 时间局部性：刚被访问的内容，立即又被访问。
• 空间局部性：刚被访问的内容，临近的空间很快被访问。

磁盘管理

存取时间=寻道时间+等待时间

• 寻道时间是指磁头移动到磁道所需的时间
• 等待时间为等待读写的扇区转到磁头下方所用的时间。

磁盘调度算法

• 先来先服务（FCFS）
• 最短寻道时间优先（SSTF）
• 扫描算法（SCAN）
• 循环扫描（CSCAN）算法

读取磁盘数据时间计算

读取磁盘数据的时间应包括以下三个部分：

1. 找磁道的时间。
2. 找块（扇区）的时间，即旋转延迟时间。
3. 传输时间。

3.3、作业管理

作业状态与作业管理

作业调度算法

• 先来先服务法
• 时间片轮转法
• 短作业优先法
• 最高优先权优先法
• 高响应比优先法

3.4、文件管理

索引文件结构

树型目录结构

空间存储空间的管理

位示图法

3.5、设备管理

I/O软件

数据传输控制方式

• 程序控制（查询）方式：分为无条件传送和程序查询方式两种。方式简单，硬件开销小，但I/O能力不高，严重影响CPU的利用率。
• 程序中断方式：与程序控制方式相比，中断方式因为CPU无需等待而提高了传输请求的响应速度。
• DMA方式：DMA方式是为了在主存与外设之间实现高速、批量数据交换而设置的。DMA方式比程序控制方式与中断方式都高效。
• 通道方式
• I/O处理机

上述方式按效率从低到高排序。

虚设备与SPOOLING技术

SPOOLing是关于慢速字符设备如何与计算机主机交换信息的一种技术，通常称为“假脱机技术”。SPOOLing技术通过磁盘实现。

四、数据库系统

数据库模型

E-R模型

关系模型

关系代数

• 并
• 交
• 差
• 笛卡尔积
• 投影
• 选择（ π \pi π）
• 联接（ σ \sigma σ）

函数依赖

规范化理论

键

候选键：唯一标识元组，且无冗余

主键：候选键中任选一个

外键：其它关系的主键

求候选键

​ 图示法求候选键

1. 将关系的函数依赖关系，用“有向图”的方式表示
2. 找出入度为0的属性，并以该属性集合为起点，尝试遍历有向图，若能正常遍历图中所有结点，则该属性集即为关系模式的候选键
3. 若入度为0的属性集不能遍历图中所有结点，则需要尝试性的将一些中间结点（既有入度，也有出度的结点）并入入度为0的属性集中，直至该集合能遍历所有结点，集合为候选键

主属性与非主属性

定义：组成候选码的属性就是主属性，其它的就是非主属性。

范式

第一范式：在关系模式R中，当且仅当所有域只包含原子值，即每个属性都是不可再分的数据项，则称关系模式R是第一范式。

第二范式：当且仅当关系模式R是第一范式，且每一个非主属性完全依赖候选键（没有不完全依赖）时，则称关系模式R是第二范式。

第三范式：当且仅当关系模式R是第二范式，且R中没有非主属性传递依赖于候选键时，则称关系模式R是第三范式。

BC范式：设R是一个关系模式，F是它的依赖集，R属于BCNF当且仅当其中F中每个依赖的决定因素必定包含R的某个候选键。

模式分解

保持函数依赖分解

设数据库模式 ρ = { R 1 , R 2 , . . . , R k } \rho=\{R1,R2,...,Rk\} ρ={R1,R2,...,Rk}是关系模式R的一个分解，F是R上的函数依赖集， ρ \rho ρ中每个模式Ri上的FD集是Fi。如果 { F 1 , F 2 , . . . , F k } \{F1,F2,...,Fk\} {F1,F2,...,Fk}与F是等价的（即相互逻辑蕴涵），那么称分解 ρ \rho ρ保持FD。

无损分解

• 有损：不能还原
• 无损：可以还原

无损联接分解：指将一个关系模式分解成若干个关系模式后，通过自然联接和投影等运算仍能还原到原来的关系模式 。

并发控制

事务

• 原子性
• 一致性
• 隔离性
• 持续性

并发产生的问题：

• 丢失更新
• 不可重复读
• 读“脏”数据

解决方案：封锁协议

• S封锁（共享锁）
• X封锁（排它锁）
• 两段锁协议

死锁：预防、死锁的解除

数据库完整性约束

• 实体完整性约束（主键：不能为空，唯一标识）
• 参照完整性约束（外键）
• 用户自定义完整性约束
• 触发器

数据库新技术

五、计算机网络与信息安全

开放系统互连参考模型

OSI/RM七层模型

TCP/IP协议族

• POP3：110端口，邮件收取
• SMTP：25端口，邮件发送
• FTP：20数据端口/21控制端口，文件传输协议
• HTTP：80端口，超文本传输协议，网页传输
• DHCP：67端口，IP地址自动分配
• SNMP：161端口，简单网络管理协议
• DNS：53端口，域名解析协议，记录域名与IP的映射关系
• TCP：可靠的传输层协议
• UDP：不可靠的传输层协议
• ICMP：因特网控制协议，PING命令来自该协议
• IGMP：组播协议
• ARP：地址解析协议，IP地址转换为MAC地址
• RARP：反向地址解析协议，MAC地址转IP地址

IP地址

网络号+主机号

子网划分

• 子网掩码
• 将一个网络划分成多个子网（取部分主机号当子网号）
• 将多个网络合并成一个大的网络（取部分网络号当主机号）

网络存储技术

三层次网络模型

建筑物综合布线系统

网络规划与设计

需求分析

• 网络功能要求
• 网络的性能要求
• 网络运行环境的要求
• 网络的可扩充和可维护性要求

网络规划原则

• 实用性原则
• 开放性原则
• 先进性原则

网络设计与实施原则

• 可靠性原则
• 安全性原则
• 高效性原则
• 可扩展性原则

层次化网络设计

• 核心层
• 汇聚层
• 接入层

计算机网络分类

按分布范围分

• 局域网（LAN）
• 城域网（MAN）
• 广域网（WAN）
• 因特网

按拓扑结构分

• 总线型
• 星型
• 环型

网络介入技术

有线接入

• 公用交换电话网络（PSTN）
• 数字数据网（DDN）
• 综合业务数字网（ISDN）
• 非对称数字用户线路（ADSL）
• 同轴光纤技术（HFC）

无线接入

• IEEE 802.11（WiFi
• IEEE 802.15（蓝牙 Bluetooth）
• 红外（IrD A）
• WAPI

六、信息安全

对称加密技术

对称加密：Ke = Kd

特点：

• 加密强度不够，但效率高
• 密钥分发困难

常见的对称密钥加密算法：DES、3DES（三重DES）、RC-5、IDEA算法

非对称加密技术

非对称加密：密钥必须成对使用（公钥加密，相应的私钥解密）

特点：加密速度慢，但效率高

常见非对称密钥加密算法：RSA、ECC

数字签名

信息摘要

数字摘要：由单项散列函数加密成固定长度的散列值。

常用的消息摘要算法有MD5，SHA等，市场上广泛使用的MD5、SHA算法的散列值分别为128和160位，由于SHA通常采用的密钥长度较长，因此安全性高于MD5。

PGP协议

公共基础设施

网络安全

各个网络层次的安全保障

主动攻击与被动攻击

被动攻击 : 截获 ;

• 目的 : 窃听他人通信内容 ;
• 操作 : 攻击者只观察 , 分析某一协议对应的协议数据单元 PDU , 窃取其中的数据信息 , 但不干扰信息传输 ;
• 别名 : 又称为流量分析 ;

主动攻击 : 中断 , 篡改 , 伪造

• 篡改 : 修改网络上的报文信息 , 又称为更改报文流 ;
• 恶意程序 : 病毒 , 蠕虫 , 木马 , 逻辑炸弹 等 ;
• 拒绝服务攻击 : 攻击者向某服务器不停地发送大量分组 , 使服务器无法正常运行 ;

网络安全协议

DoS（拒绝服务）与DDoS

DoS：是Denial of Service的简称，即拒绝服务，不是DOS操作系统，造成DoS的攻击行为被称为DoS攻击，其目的是使计算机或网络无法提供正常的服务。最常见的DoS攻击有计算机网络带宽攻击和连通性攻击。

DDOS：分布式拒绝服务(DDoS:Distributed Denial of Service)攻击指借助于客户/服务器技术，将多个计算机联合起来作为攻击平台，对一个或多个目标发动DDoS攻击，从而成倍地提高拒绝服务攻击的威力。

防火墙

安全防范体系

安全防范体系的层次划分：

• 物理环境的安全性。包括通信线路、物理设备和机房的安全等。物理层的安全主要体现在通信线路的可靠性（线路备份、网管软件和传输介质）、软硬件设备的安全性（替换设备、拆卸设备、增加设备）、设备的备份、防灾害能力、防干扰能力、设备的运行环境（温度、湿度、烟尘）和不间断电源保障等。
• 操作系统的安全性。主要表现在三个方面，一是操作系统本身的缺陷带来的不安全因素，主要包括身份认证、访问控制和系统漏洞等；二是对操作系统的安全配置问题；三是病毒对操作系统的威胁。
• 网络的安全性。网络层的安全问题主要体现在计算机网络方面的安全性，包括网络层身份认证、网络资源的访问控制、数据传输的保密与完整性、远程接入的安全、域名系统的安全、路由系统的安全、入侵检测的手段和网络设施防病毒等。
• 应用的安全性。由提供服务所采用的应用软件和数据的安全性产生，包括Web服务、电子邮件系统和DNS等。此外，还包括病毒对系统的威胁。
• 管理的安全性。包括安全技术和设备的管理、安全管理制度、部门与人员的组织规则等。管理的制度化极大程度地影响着整个计算机网络的安全，严格的安全管理制度、明确的部门安全职责划分与合理的人员角色配置，都可以在很大程度上降低其他层次的安全漏洞。

计算机病毒与木马

病毒：编制或者在计算机程序中插入的破坏计算机功能或者破坏数据，影响计算机使用并且能够自我复制的一组指令或者程序代码。

木马：计算机木马是一种后门程序，常被黑客用作控制远程计算机的工具。

• 系统病毒（前缀：Win32、PE、W32，如：KCOM-Win32.KCOM）
• 蠕虫病毒（如：恶鹰-Worm。BBeagle）
• 木马病毒、黑客病毒（如：QQ消息尾巴木马-Trojan.QQ3344）
• 脚本病毒（如：红色代码-Script.Redlof）
• 宏病毒（如：梅丽莎-Macro.Melissa）
• 后门病毒（如：灰鸽子-Backdoor.Win32.Huigezi）
• 病毒种植程序病毒（冰河播种者-Dropper.BingHe2.2C）
• 破坏性程序病毒（杀手命令-Harm.Command.Killer）
• 玩笑病毒（如：女鬼-Jioke.Grl ghost）
• 捆绑机病毒（如：捆绑QQ-Binder.QQPass.QQBin）

七、系统开发基础

信息系统开发生命周期

开发模型

• 瀑布模型
• V模型
• 喷泉模型
• 原型化模型
• 演化模型
• 螺旋模型
• 统一过程
• 敏捷方法

软件过程模型

瀑布模型

软件计划->需求分析->软件设计->程序编码->软件测试->运行维护

V模型

喷泉模型（面向对象）

原型化模型

原型化模型第一步就是创建一个快速原型，能够满足项目干系人与未来的用户可以与原型进行交互，再通过与相关干系人进行充分的讨论和分析，最终弄清楚当前系统的需求，进行了充分的了解之后，在原型的基础上开发出用户满意的产品。在实际的项目过程中，借助于组织过程资产以及快速模型软件，一般在需求分析的时候，就可以建立一些简单的原型。原型化模型是极具意义的项目实践。

原型法认为在报难一下子全面准确地提出用户需求的情况下，首先不要求一定要对系统做全面、详细的调查、分析，而是本着开发人员对用户需求的初步理解，先快速开发一个原型系统，然后通过反复修改来实现用户的最终系统需求。

原型应当具备的特点如下。

(1)实际可行。

(2)具有最终系统的基本特征。

(3)构造方便、快速，造价低。

原型法的特点在于原型法对用户的需求是动态响应、逐步纳入的，系统分析、设计与实现都是随着对一个工作模型的不断修改而同时完成的，相互之间并无明显界限，也没有明确分工。系统开发计划就是一个反复修改的过程。适于用户需求开始时定义不清、管理决策方法结构化程度不高的系统开发，开发方法更易被用户接受；但如果用户配合不好，盲目修改，就会拖延开发过程。

可以将原型分类如下。

(1)抛弃型原型（Throw-It-Away Prototype），此类原型在系统真正实现以后就放弃不用了。

(2)进化型原型(Evolutionary Prototype)，此类原型的构造从目标系统的一个或几个基本需求出发，通过修改和追加功能的过程逐渐丰富，演化成最终系统。

演化模型

演化模型主要针对事先不能完整定义需求的软件开发。用户可以给出待开发系统的核心需求，并且当看到核心需求实现后，能够有效地提出反馈，以支持系统的最终设计和实现。软件开发人员根据用户的需求，首先开发核心系统。当该核心系统投入运行后，用户试用之，完成他们的工作，并提出精化系统、增强系统能力的需求。软件开发人员根据用户的反馈，实施开发的迭代过程。第一迭代过程均由需求、设计、编码、测试、集成等阶段组成，为整个系统增加一个可定义的、可管理的子集。

在开发模式上采取分批循环开发的办法，每循环开发一部分的功能，它们成为这个产品的原型的新增功能。于是，设计就不断地演化出新的系统。 实际上，这个模型可看作是重复执行的多个“瀑布模型”。

“演化模型”要求开发人员有能力把项目的产品需求分解为不同组，以便分批循环开发。这种分组并不是绝对随意性的，而是要根据功能的重要性及对总体设计的基础结构的影响而作出判断。有经验指出，每个开发循环以六周到八周为适当的长度。

螺旋原型

软件开发方法

结构化方法

面向数据流的方法

Jackson，面向数据结构的开发方法

• 用户至上
• 严格区分工作阶段，每阶段由任务和结果
• 强调系统开发过程的整体性和全局性
• 系统开发过程工程化，文档资料标准化
• 自顶向下，逐步分解（求精）

原型法

面向对象方法

（喷泉模型）

• 更好的复用性
• 关键在于建立一个全面、合理、统一的模型
• 分析、设计、实现三个阶段，界限不明确

面向服务的方法

（SOA）

统一过程

统一过程就是在软件生命周期过程中以用例为驱动、构架为中心来进行一次一次的增量式的迭代，每次迭代都是以上一次迭代为基础并生成包括构件的源代码体、需求说明、测试用例等的制品。每次的迭代又具体分为四个阶段：初始、细化、构建、交付，而在每个阶段又分为多个工作流：需求、分析、设计、实现和测试等。

初始：

• 确定项目范围和边界
• 识别系统的关键用例
• 展示系统的候选架构
• 估计项目费用和时间
• 评估项目风险

细化：

• 分析系统问题领域
• 建立软件架构基础
• 淘汰最高风险元素

构建：

• 开发剩余的构件
• 构件组装与测试

交付：

• 进行 β \beta β测试
• 制作发布版本
• 用户文档定稿
• 确认新系统
• 培训、调整产品

统一过程模型是基于面向对象方法和UML统一建模语言的，用这种方法论来指导软件开发主要可以解决两个问题：

• 软件复用问题
• 需求变化问题。

敏捷方法

• XP（Extreme Programming，极限编程）在所有的敏捷型方法中，XP是最引人瞩目的，它源于Smalltalk圈子，特别是Kent Beck和Ward Cunningham在20世纪80年代末的密切合作。XP在一些对费用控制严格的公司中使用，已经被证明是非常有效的。

• Cockburn的水晶系列方法，水晶系列方法是由Alistair Cockburn提出的。它与XP方法一样，都有以人为中心的理念，但在实践上有所不同。Alistair考虑到人们一般很难严格遵循一个纪律约束很强的过程，因此，与XP的高度纪律性不同，Alistair探索了用最少纪律约束而仍能成功的方法，从而在产出效率与易于运作上达到一种平衡。也就是说，虽然水晶系列不如XP那样的产出效率，但会有更多的人能够接受并遵循它。

• 开放式源码，这里提到的开放式源码指的是开放源码界所用的一种运作方式。开放式源码项目有一个特别之处，就是程序开发人员在地域上分布很广，这使得它和其他敏捷方法不同。因为一般的敏捷方法都强调项目组成员在同一地点工作。开放源码的一个突出特点就是查错排障（debug）的高度并行性，任何人发现了错误都可将改正源码的“补丁”文件发给维护者。由维护者将这些“补丁”或是新增的代码并入源码库。

• SCRUM（并列争球法）。SCRUM已经出现很久了，像前面所论及的方法一样，该方法强调这样一个事实，即明确定义了的可重复的方法过程只限于定义了的可重复的环境中，为明确定义了的可重复的人员所用，去解决明确定义了的可重复的问题。

• Coad的功用驱动开发方法（FDD- Feature Driven Development）

  FDD是由Jeff De Luca和大师Peter Coad提出来的，像其他方法一样，它致力于短时的迭代阶段和可见可用的功能。在FDD中，一个迭代周期一般是两周。

  在FDD中，编程开发人员分成两类：首席程序员和“类”程序员（class owner）。首席程序员是最富有经验的开发人员，他们是项目的协调者、设计者和指导者，而“类”程序员则主要做源码编写。

• ASD方法，ASD（Adaptive Software Development）方法由Jim Highsmith提出，其核心是三个非线性的、重叠的开发阶段：猜测、合作与学习。

需求分析

应用的工具：

• 数据流图（DFD）
• 数据字典（DD）
• 判定表（由基本条件项、条件项，基本动作项、动作项形成）
• 判定树（决策树）

软件设计

处理流程设计工具

软件设计的任务与活动

模块设计的原则

高内聚低耦合

应用的工具

• IPO图（输入处理输出图）
• PDL（程序描述语言）
• PAD（问题分析图）
• 程序流程图
• N/S盒图

软件测试

动态测试

黑盒测试法

• 等价类划分

  确定无效与有效等价类

  设计用例尽可能多的覆盖有效类

  设计用例只覆盖一个无效类

• 边界值分析

  处理边界情况时最容易出错

  选取的测试数据应该恰好等于、稍小于或稍大于边界值

• 错误推测

• 因果图

白盒测试法

• 语句覆盖
• 判定覆盖
• 条件覆盖
• 条件判定覆盖
• 路径覆盖

灰盒测试法

静态测试

• 桌前检查
• 代码审查
• 代码走查

单元测试

模块接口、局部数据结构、边界条件、独立的路径、错误处理

集成测试

模块间的接口和通信

系统测试

恢复测试、安全性测试、强度测试、性能测试、可靠性测试和安装测试

验收测试

有效性测试、软件配置审查、验收测试

回归测试

负载测试

压力测试

McCabe复杂度

计算有向图G的环路复杂度公式为： V ( G ) = m − n + 2 V(G)=m-n+2 V(G)=m−n+2

或 封闭区域+1

说明：其中V(G)是有向图中的环路个数，m是G中的有向弧数，n是G中的节点数。

软件维护

系统转换

可维护性因素决定

• 可理解性
• 可测试性
• 可修改性

软件维护类型

• 改正性维护
• 适应性维护
• 预防性维护
• 完善性维护

适应性维护：指使应用软件适应信息技术变化和管理需求变化而进行的修改。企业的外部市场环境和管理需求的不断变化也使得各级管理人员不断提出新的信息需求。

完善性维护，扩充功能和改善性能而进行的修改。对已有的软件系统增加一些在系统分析和设计阶段中没有规定的功能与性能特征。

软件文档

开发文档

• 可行性研究和项目任务书
• 需求规格说明
• 功能规格说明
• 设计规格说明（包括程序和数据规格说明）
• 开发计划
• 软件集成和测试计划
• 质量保证计划、标准、进度
• 安全和测试信息

产品文档

• 培训手册
• 参考手册和用户指南
• 软件支持手册
• 产品手册和信息广告

管理文档

• 开发过程的每个阶段的进度和进度变更的记录
• 软件变更情况的记录
• 相对于开发的判定记录
• 职责定义

软件质量保证

软件过程改进

CMMI（软件成熟度模型）

项目管理

• 范围管理
• 时间管理
• 成本管理
• 质量管理
• 人力资源管理
• 沟通管理
• 风险管理
• 采购管理
• 整体管理

八、程序设计语言与语言处理程序基础

编译过程

• 词法错误：非法字符，关键字或标识符拼写错误
• 语法错误：语法结构出错，if endif不匹配，缺分号
• 语义错误：死循环，零除数，其它逻辑错误

文法定义

一个形式文法是一个有序四元组G=（V，T，S，P），其中：

• V：非终结符，不是语言组成部分，不是最终结果，可理解为占位符。
• T：终结符，是语言的组成部分，是最终结果。 V ∩ T = ⊘ V\cap T=\oslash V∩T=⊘
• S：起始符，是语言的开始符号。
• P：产生式，用终结符替代非终结符的规则，形如 α → β \alpha \rightarrow \beta α→β

正则必包：

十一、数据流图

DFD

数据流图的基本概念

数据字典

DD

数据流图平衡原则

父图与子图之间的平衡

指任何一张DFD子图边界上的输入/输出数据流必须与其父图对应加工的输入/输出保持一致。

子图内平衡

• 加工只有输入没有输出，称之为“黑洞”
• 加工只有输出没有输入，称之为“奇迹”
• 加工中输入不足以产生输出，称之为“灰洞”

十二、UML

用例图

用例图描述一组用例，参与者及它们之间的关系。

关系包括：

• 包含关系：其中这个提取出来的公共用例称为抽象用例，而把原始用例称为基本用例或基础用例系：当可以从两个或两个以上的用例中提取公共行为时，应该使用包含关系来表示它们。
• 扩展关系：如果一个用例明显地混合来两种或两种以上的不同场景，即根据情况可能发生多种分支，则可以将这个用例分为一个基本用例和一个或多个扩展用例，这样时描述可能更加清晰。
• 泛化关系：当多个用例共同拥有一种类似的结构和行为的时候，可以将它们的共性抽象称为父用例，其它的用例作为泛化关系中的子用例。在用例的泛化关系中，子用例时父用例的一种特殊形式，子用例继承了父用例所有的结构、行为和关系。

用例建模的流程：

• 识别参与者（必须）
• 合并需求获得用例（必须）
• 细化用例描述（必须）
• 调整用例模型（可选）

类图与对象图

类图（class diagram）：类图描述一组类、接口、协作和它们之间的关系。在面向对象系统的建模中，最常见的图就是类图。类图给出了系统的静态设计视图，活动类的类图给出了系统的静态进程视图。

对象图（object diagram）：对象图描述一组对象及它们之间的关系。对象图描述了在类图中所建立的事物实例的静态快照。和类图一样，这些图给出系统的静态设计视图或静态进程视图，但它们是从真实案例或原型案例的角度建立的。

1：表示一个集合中的一个对象对应另一个集合中1个对象

0…*：表示一个集合中的一个对象对应另一个集合中的0个或多个对象（可以不对应）

1…*：表示一个集合中的一个对象对应另一个集合中的一个或多个对象（至少对应一个）

*：表示一个集合中的一个对象对应另一个集合中的多个的对象

关系：

• 依赖关系
• 泛化关系
• 关联关系，组合关系
• 聚合关系
• 实现关系

序列图

顺序图（sequence diagram，序列图）。顺序图是一种交互图（interaction diagram），交互图展现了一种交互，它由一组对象或参与者以及它们之间可能发送的消息构成。交互图专注于系统的动态视图。顺序图是强调消息的时间次序的交互图。

活动图

活动图（activity diagram）。活动图将进程或其他计算结构展示为计算内部一步步的控制流和数据流。活动图专注于系统的动态视图。它对系统的功能建模和业务流程建模特别重要，并强调对象间的控制流程。

状态图

状态图（state diagram）。状态图描述一个状态机，它由状态、转移、事件和活动组成。状态图给出了对象的动态视图。它对于接口、类或协作的行为建模尤为重要，而且它强调事件导致的对象行为，这非常有助于对反应式系统建模。

通信图

通信图（communication diagram）。通信图也是一种交互图，它强调发消息的对象或参与者的结构组织。顺序图和通信图表达了类似的基本概念，但它们所强调的概念不同，顺序图强调的是时序，通信图强调的是对象之间的组织结构（关系）。

构件图

构件图（component diagram）。构件图描述一个封装的类和它的接口、端口，以及由内嵌的构件和连接件构成的内部结构。构件图用于表示系统的静态设计实现视图。对于由小的部件构建大的系统来说，构件图是很重要的。构件图是类图的变体。

部署图

部署图（deployment diagram）。部署图描述对运行时的处理节点及在其中生存的构件的配置。部署图给出了架构的静态部署视图，通常一个节点包含一个或多个部署图。

十三、数据结构与算法

分治法

对于一个规模为n的问题，若该问题可以容易解决（比如说规模n较小）则直接解决；否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

• 该问题的规模缩小到一定的程度就可以容易地解决
• 该问题可以分解为若干个规模较小的相同问题
• 利用该问题分解出的子问题的解可以合并为该问题的解
• 该问题所分解出的各个子问题是相互对立的

特征：把一个问题拆分成多个小规模的相同子问题，一般可用递归解决。

经典问题：斐波那契数列、归并排序、快速排序、矩阵乘法、二分搜索、大整数乘法、汉诺塔

回溯法

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。这种走不通就退回再走的技术就是回溯法。

• 试探部分（扩大规模）：满足除规模之外的所有条件，则扩大规模

• 回溯部分（缩小规模）：

  1、当前规模不是合法解时回溯（不满足约束条件D）

  2、求完一个解，要求下一个解时，也要回溯。

特征：系统的搜索一个问题的所有解或任一解。

经典问题：N皇后问题、迷宫、背包问题

贪心法

总是做出在当前来说是最好的选择，而并不从整体上加以考虑，它所做的每步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。由于它不必为了寻找最优解而穷尽所有可能解，因此其耗费时间少，一般可以快速得到满意的解，但得不到最优解。

用于求满意解。

特征：局部最优，但整体不见得最优。每步优明确的，既定的策略。

经典问题：背包问题（如装箱）、多机调度、找零钱问题

动态规划法

在求解问题中，对于每一步决策，列出各种可能的局部解，再依据某种判定条件，舍弃那些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解。

用于求最优解。

特征：划分子问题，并把子问题结构使用数组存储，利用查询子问题结构构造最终问题结果

经典问题：斐波那契数列、矩阵乘法、背包问题、LCS最长公共子序列

时间复杂度

1、常数级时间复杂度： O ( 1 ) O(1) O(1)

• 单个语句
• 整个程序没有循环语句，或复杂函数的调用

2、时间复杂度： O ( n ) O(n) O(n)，单层循环

3、时间复杂度： O ( n 2 ) O(n^2) O(n2)，双层循环（多少层循环则为多少次方）

4、时间复杂度： O ( l o g 2 n ) O(log_2n) O(log2​n)，（树）

5、时间复杂度： O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n)，典型代表：堆排序，每次重建堆的时间复杂度是 l o g 2 n log_2n log2​n，n个元素基本上就是 n l o g 2 n nlog_2n nlog2​n

十四、面向对象

十五、设计模式

一、计算机组成与系统结构

1.1、数据的表示

R进制转十进制使用按权展开法，其具体操作方式为：将R进制数的每一位数值用 R k R^k Rk形式表示，即幂的底数是R，指数为k，k与该位和小数点之间的距离有关。当该位位于小数点的左边，k值是该位和小数点之间数码的个数，而当该位位于小数点右边，k值是负值，其绝对值是该位和小数点之间数码的个数加1。

• 十进制转R进制使用短除法。

• 二进制转八进制。

  10 \textcolor{red}{10} 10 001 \textcolor{blue}{001} 001 110 \textcolor{green}{110} 110=> 2 \textcolor{red}{2} 2 1 \textcolor{blue}{1} 1 6 \textcolor{green}{6} 6

• 二进制转十六进制。

  1000 \textcolor{red}{1000} 1000 1110 \textcolor{green}{1110} 1110=> 8 \textcolor{red}{8} 8 E \textcolor{green}{E} E

1.1.1、原码

**原码就是符号位加上真值的绝对值，**即用第一位表示符号，其余位表示值。比如：如果是8位二进制：

[+1]原= 0000 0001

[-1]原= 1000 0001

第一位是符号位，因为第一位是符号位，所以8位二进制数的取值范围就是：（即第一位不表示值，只表示正负。）

[1111 1111 , 0111 1111]即[-127 , 127]

数值表示范围： − 2 n − 1 − 1 ∼ 2 n − 1 − 1 -2^{n-1}-1\sim2^{n-1}-1 −2n−1−1∼2n−1−1

1.1.2、反码

反码的表示方法：

• 正数的反码是其本身；

• 负数的反码是在其原码的基础上，符号位不变，其余各个位取反。

[+1] = [0000 0001]原= [0000 0001]反

[-1] = [1000 0001]原= [1111 1110]反

数值表示范围： − 2 n − 1 − 1 ∼ 2 n − 1 − 1 -2^{n-1}-1\sim2^{n-1}-1 −2n−1−1∼2n−1−1

1.1.3、补码

补码的表示方法：

• 正数的补码就是其本身；

• 负数的补码是在其原码的基础上，符号位不变，其余各位取反，最后+1。(即在反码的基础上+1)

[+1] = [0000 0001]原= [0000 0001]反= [0000 0001]补

[-1] = [1000 0001]原= [1111 1110]反= [1111 1111]补

数值表示范围： − 2 n − 1 ∼ 2 n − 1 − 1 -2^{n-1}\sim2^{n-1}-1 −2n−1∼2n−1−1

1.1.4、移码

不管正负数，只要将其补码的符号位取反即可。

[+1] = [00000001]原 = [00000001]反 = [00000001]补
[-1] = [10000001]原 = [11111110]反 = [11111111]补

1.1.5、浮点数运算

浮点数表示： N = M ∗ R e N = M * R^e N=M∗Re，其中M称为尾数，e是指数，R为基数。

1.2、计算机结构

计算机的基本硬件系统由运算器、控制器、存储器、输入设备和输出设备5大部件组成。

运算器、控制器等部件被集成在一起统称为重要处理单元（CPU）。

• 运算器
  1. 算数逻辑单元ALU
  2. 累加寄存器AC
  3. 数据缓冲寄存器DR
  4. 状态条件寄存器PSW
• 控制器
  1. 程序计数器PC
  2. 指令寄存器IR
  3. 指令译码器ID
  4. 时序部件

1.2.1、计算机体系结构分类-Flynn

1.2.2、CISC与RISC

1.3、流水线

流水线是指在程序执行时多条指令重叠进行操作的一种准并行处理实现技术。各种部件同时处理是针对不同指令而言的，它们可同时为多条指令的不同部分进行工作，以提高各部件的利用率和指令的平均执行速度。

• 指令流水线：计算机中一条指令的执行需要若干步，通常采用流水线技术实现指令的执行，以提高CPU性能。
• 运算操作流水线：计算机在执行各种运算操作时也可以以应用流水线技术来提高运算速度。

1.3.1、流水线计算

• 流水线周期为执行时间最长的一段

• 流水线指令运行时间的计算：

  一条指令执行时间 + (指令条数 - 1) * 流水想周期

  1. 理论公式：

     ( t 1 + t 2 + . . . + t k ) + ( n − 1 ) ∗ Δ t (t1+t2+...+tk)+(n-1)*\Delta t (t1+t2+...+tk)+(n−1)∗Δt

  2. 实践公式：

     ( k + n − 1 ) ∗ Δ t (k+n-1)*\Delta t (k+n−1)∗Δt

     其中 Δ t \Delta t Δt为最慢一段所需的时间

1.3.2、流水线吞吐率计算

流水线的吞吐率（Though Put rate，TP）是指在单位时间内流水线所完成的任务数量或输出的结果数量。计算流水线吞吐率的最基本的公式如下：
T P = 指令条数 流水线执行时间 {TP} = {指令条数 \over 流水线执行时间} TP=流水线执行时间指令条数​
流水线最大吞吐率：
T P max ⁡ = lim ⁡ n → ∞ n ( k + n − 1 ) Δ t = 1 Δ t {TP_{_{\max }}} = \mathop {\lim }\limits_{n \to \infty } {n \over {(k + n - 1)\Delta t}} = {1 \over {\Delta t}} TPmax​​=n→∞lim​(k+n−1)Δtn​=Δt1​

1.3.3、流水线的加速比

完成同样一批任务，不使用流水线所用的时间与使用流水线所用的时间之比称为流水线的加速比。计算流水线加速比的基本公式如下：
S = 不使用流水线执行时间 使用流水线执行时间 {{S}}={不使用流水线执行时间 \over 使用流水线执行时间} S=使用流水线执行时间不使用流水线执行时间​

1.3.4、流水线的效率

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

计算流水线效率的公式为：
E = n 个任务占用的时空区 k 个流水段的总的时空区 = T 0 k T k {{E}}={{n个任务占用的时空区} \over k个流水段的总的时空区}={T_0 \over kT_k} E=k个流水段的总的时空区n个任务占用的时空区​=kTk​T0​​

• 效率与吞吐率的关系：
  E = T P ∗ Δ t E=TP*\Delta t E=TP∗Δt

• 效率与加速比的关系：
  E = S k {E}={S\over k} E=kS​

1.4、计算机层次化存储结构

1.4.1、Cache

• Cache的功能：提高CPU数据输入输出的速率，突破冯•诺伊曼瓶颈，即CPU与存储系统间数据传送带宽限制。

• 在计算机的存储系统体系中，Cache是访问速度最快的层次。

• 使用Cache改善系统性能的依据是程序的局部性原理。

如果以h代表对Cache的访问命中率， t 1 t_1 t1​表示Cache的周期时间， t 2 t_2 t2​表示主存储器周期时间，以读操作为例，使用“Cache+主存储器”的系统的平均周期为 t 3 t_3 t3​，则：
t 3 = h ∗ t 1 + ( 1 − h ) ∗ t 2 {{t_3}}=h*t_1+(1-h)*t2 t3​=h∗t1​+(1−h)∗t2
其中，(1-h)又称为失效率（未命中率）。

Cache的读写过程

• 写直达：当要写Cache时，数据同时写回主存储器，有时也称为写通。
• 写回：CPU修改Cache的某一行后，相应的数据并不会立即写入主存储器单元。而是当该行被从Cache中淘汰时，才把数据写回到主存储器中。
• 标记法：对Cache中的每一个数据设置一个有效位。

地址映像

常见的映像方法有直接映像、相联映像和组相联映像。

地址映像是将主存与Cache的存储空间划分为若干大小相同的页（或称为块）。

例如某机的主存容量为1GB，划分为2048页，每页512KB；Cache容量为8MB，划分为16页，每页512KB。

1.4.2、局部性原理

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

1.4.3、主存分类

• 随机存取存储器
  • DRAM（Dynamic RAM，动态RAM）-SDRAM
  • SRAM（Static RAM，静态）
• 只读存储器
  • MROM（Mask ROM，掩模式ROM）
  • PROM（Programmable ROM，一次可编程ROM）
  • EPROM（Erasable PROM，可擦除的PROM）
  • 闪速存储器（flash memory，闪存）

1.4.4、主存编址

编址

芯片的拼接

如果主存容量为16M字节，且按字节编址，表示该主存地址至少需要多少位？

16M*8位的芯片，存储容量=存储单元个数×存储字长， 2 20 = 1 M 2^{20}=1M 220=1M， 2 4 = 16 2^4=16 24=16，故表示该主存地址至少需要24位。

内存按字节编址，地址从A4000H到CBFFFH，共有多少字节？若用存储容量为32K*8 bit的存储芯片构成该内存，至少需要多少片？

CBFFFH-A4000H+1H=27FFFH+1H=28000H
28000 H = 2 ∗ 16 ∗ 16 ∗ 16 ∗ 16 + 8 ∗ 16 ∗ 16 ∗ 16 + 0 ∗ 16 ∗ 16 + 0 ∗ 16 + 0 ∗ 1 = 163840 28000H=2*16*16*16*16+8*16*16*16+0*16*16+0*16+0*1=163840 28000H=2∗16∗16∗16∗16+8∗16∗16∗16+0∗16∗16+0∗16+0∗1=163840

163840 1024 = 160 {163840\over1024}=160 1024163840​=160

160 32 = 5 {160\over32}=5 32160​=5

综上，共有160K字节，至少需要5片。

1.4.5、磁盘结构与参数

存储相关计算问题

计磁道数 = ( 外半径 − 内半径 ) ∗ 道密度 ∗ 记录面数 计磁道数=(外半径-内半径)*道密度*记录面数 计磁道数=(外半径−内半径)∗道密度∗记录面数

注意：硬盘的第一面与最后一面是保护用的，要减掉。

例如：4个双面的盘片的记录面数是4*2-2=6。
非格式化容量 = 位密度 ∗ π ∗ 最内圈直径 ∗ 总磁道数 非格式化容量=位密度*\pi*最内圈直径*总磁道数 非格式化容量=位密度∗π∗最内圈直径∗总磁道数
注意：位密度是每道不同的，但每道的容量是相同的，0到最外面的磁道，其密度最小。
格式化容量 = 每道扇区数 ∗ 扇区容量 ∗ 总磁道数 格式化容量=每道扇区数*扇区容量*总磁道数 格式化容量=每道扇区数∗扇区容量∗总磁道数

平均数据传输速率 = 每道扇区数 ∗ 扇区容量 ∗ 盘片转数 平均数据传输速率=每道扇区数*扇区容量*盘片转数 平均数据传输速率=每道扇区数∗扇区容量∗盘片转数

平均数据传输速率 = 最内圈直径 ∗ π ∗ 位密度 ∗ 盘片转数 平均数据传输速率=最内圈直径*\pi*位密度*盘片转数 平均数据传输速率=最内圈直径∗π∗位密度∗盘片转数

存取时间 = 寻道时间 + 等待时间 ( 平均定位时间 + 转动延迟 ) {{存取时间}}={{寻道时间}}+{{等待时间(平均定位时间+转动延迟)}} 存取时间=寻道时间+等待时间(平均定位时间+转动延迟)

注意：

• 寻道时间是指磁头移动到磁道所需的时间；
• 等待时间为等待读写的扇区转到磁头下方所用的时间。

磁带存储是一种顺序存取设备，存取时间长，容量大，现在常用于备份。根据其读写方式的不同，它通常包括两种：

• 启停式：以文件块的形式存放信息，数据块间有空白块，其磁道数就是磁头数。
• 数据流式：结构简单、价格低、速度快。它是串行逐道记录信息，每次读写1位。

其相关的性能公式如下：
数据传输速率 ( B / s ) = 磁带记录密度 ( B / m m ) ∗ 带速 ( m m / s ) 数据传输速率(B/s)=磁带记录密度(B/mm)*带速(mm/s) 数据传输速率(B/s)=磁带记录密度(B/mm)∗带速(mm/s)

B 1 = ( 字节数 / 记录 ) ∗ 块因子 / 记录密度 B1=(字节数/记录)*块因子/记录密度 B1=(字节数/记录)∗块因子/记录密度

数据块长度 = B 1 ( 记录数据所需长度 ) + B 2 ( 块间间隔 ) 数据块长度=B1(记录数据所需长度)+B2(块间间隔) 数据块长度=B1(记录数据所需长度)+B2(块间间隔)

R ( 有效时间 ) = ( N ∗ 字节数 / 记录 ) / 传输速度 R(有效时间)=(N*字节数/记录)/传输速度 R(有效时间)=(N∗字节数/记录)/传输速度

D ( 间隔时间 ) = 块间隔总长 / 带速 = [ ( N / 块化因子 ) ∗ ( 块间间隔 ) ] / 带速 D(间隔时间)=块间隔总长/带速=[(N/块化因子)*(块间间隔)]/带速 D(间隔时间)=块间隔总长/带速=[(N/块化因子)∗(块间间隔)]/带速

读 N 条记录所需的时间： T = S ( 启停时间 ) + R + D 读N条记录所需的时间：T=S(启停时间)+R+D 读N条记录所需的时间：T=S(启停时间)+R+D

1.5、总线

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

• 内部总线

• 系统总线

  • 数据总线
  • 地址总线
  • 控制总线

• 外部总线

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

1.6.1、什么是检错和纠错

检错：发现错误。

纠错：发现错误并给以纠正。

1.6.2、什么是码距

一个编码系统的码距是整个编码系统中任意（所有） 两个码字的最小距离。

• 若用1位长度的二进制编码。若A=1，B=0.这样A，B之间的最小码距为1.
• 若用2位长度的二进制编码，若以A= 11，B=00为例，A，B之间的最小码距为2.
• 若用3位长度的二进制编码，可选用111，000作为合法编码，A，B之间的最小码距为3.

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

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

1.6.3、循环校验码CRC

编码译码的方法为：

• 令r为 生成多项式G(x)的阶，将r个“0”附加在信息（数据）元的低端，使其长度变为k+r位，相当于多项式 x y ∗ m ( x ) x^y*m(x) xy∗m(x)；
• x y ∗ m ( x ) + G ( x ) [ m o d 2 ] x^y*m(x)+G(x)[mod2] xy∗m(x)+G(x)[mod2]，得余数；
• x y ∗ m ( x ) x^y*m(x) xy∗m(x)与余数对应位异或，得编码信息T(x)。
• 接收器收到发来的编码信息后，用这个编码信息除以同一个生成多项式G(x)，（注意是同一个生成多项式），而且用模2除法。若余数为0，则表示接收到正确的编码信息，否则该编码有错。
• 把接收到的正确的编码信息T(x)去掉尾部r位，即得到数据信息M(x)。

什么是模2除法，它和普通的出发有何区别？

模2除法是指在做除法运算的过程中不计其进位的除法。

1.6.4、海明校验码

海明码：本质也是利用奇偶性来检错和纠错的校验方法，构成方法是在数据位之间的确定位置上插入k个校验位，通过扩大码距实现检错和纠错。

设数据位是n位，校验位是k位，则n和k必须满足以下关系： 2 k − 1 > = n + k 2^k-1>=n+k 2k−1>=n+k

设数据位是n位，校验位是k位，则n和k必须满足关系： 2ᵏ-1>=n+k

设有数据为8位，那么 2⁴-1=15>8+4=12,则校验位为4位，即这个海明码长12位

令信息位为D7,D6,D5,D4,D3,D2,D1,D0,信息位从高往低占据编码位；
令校验位为P3,P2,P1,P0,校验位P0=2⁰=1，P1=2¹=2，P2=2²=4，P3=2³=8；
形成的海明码编码过程如下：

信息位D7的位数为12，12=8+4，所以D7的校验位组为P3（位数：8）和P2（位数：4），即信息位的位数=校验位组的位数之和。

由上表可得，P0参与了D0,D1,D3,D4,D6的检验，其他由此类推
P0=D0⊕D1⊕D3⊕D4⊕D6
P1=D0⊕D2⊕D3⊕D5⊕D6
P2=D1⊕D2⊕D3⊕D7
P3=D4⊕D5⊕D6⊕D7

这样子就可以算出整个海明码的值了。

例

设数据为01101001，求海明码。

数据位为8，则2⁴-1=15>8+4=12,则校验位为4位，即这个海明码长12位；
D7D6D5D4D3D2D1D0=01101001；
P0=2⁰=1，P1=2¹=2，P2=2²=4，P3=2³=8；
P0=D0⊕D1⊕D3⊕D4⊕D6=1⊕0⊕1⊕0⊕1=1
P1=D0⊕D2⊕D3⊕D5⊕D6=1⊕0⊕1⊕1⊕1=0
P2=D1⊕D2⊕D3⊕D7=0⊕0⊕1⊕0=1
P3=D4⊕D5⊕D6⊕D7=0⊕1⊕1⊕0=0

则海明码为011001001101

1.7、输入输出技术

二、系统可靠性分析与设计

2.1、串联系统与并联系统

串联

• 可靠度

R = R 1 ∗ R 2 ∗ . . . ∗ R n {{R}}={{R_1*R_2*...*R_n}} R=R1​∗R2​∗...∗Rn​

λ = λ 1 + λ 2 + . . . + λ n \lambda = \lambda _1+\lambda _2 +...+\lambda_n λ=λ1​+λ2​+...+λn​

并联

• 可靠度

R = 1 − ( 1 − R 1 ) ∗ ( 1 − R 2 ) ∗ . . . ∗ ( 1 − R n ) R=1-(1-R_1)*(1-R_2)*...*(1-R_n) R=1−(1−R1​)∗(1−R2​)∗...∗(1−Rn​)

μ = 1 1 λ ∑ j = 1 n 1 j \mu = {1 \over {{1 \over \lambda }\sum\limits_{j = 1}^n {{1 \over j}} }} μ=λ1​j=1∑n​j1​1​

2.2、模冗余系统与混合系统

R = ∑ i = n + 1 m C m j ∗ R 0 i ( 1 − R 0 ) m − i R = \sum\limits_{i = n + 1}^m {C_m^j} * R_0^i{(1 - {R_0})^{m - i}} R=i=n+1∑m​Cmj​∗R0i​(1−R0​)m−i

R ∗ ( 1 − ( 1 − R ) 3 ) ∗ ( 1 − ( 1 − R ) 2 ) R*(1-(1-R)^{{3}})*(1-(1-R)^{{2}}) R∗(1−(1−R)3)∗(1−(1−R)2)

三、操作系统

3.1、进程管理

3.1.1、PV操作

• 临界资源：诸进程间需要互斥方式对其进行共享的资源，如打印机、磁带机等
• 临界区：每个进程中访问临界资源的那段代码称为临界区
• 信号量：是一种特殊的变量

3.1.2、死锁问题

进程管理是操作系统的核心，但如果设计不当，就会出现死锁的问题。如果一个进程在等待一件不可能发生的事，则进程就死锁了。而如果一个或多个进程产生死锁，就会造成系统死锁。

3.1.3、银行家算法

银行家算法：分配资源的原则

• 当一个进程对资源的最大需求量不超过系统中的资源数时可以接纳该进程
• 进程可以分期请求资源，但请求的总数不能超过最大需求量
• 当系统现有的资源不能满足进程尚需资源数时，对进程的请求可以推迟分配，但总能使进程在有限的时间里得到资源。

3.2、存储管理

页式存储组织

页号|页内地址

• 优点：利用率高，碎片小，分配及管理简单
• 缺点：增加了系统开销；可能产生抖动现象

高级程序语言使用逻辑地址；

运行状态，内存中使用物理地址。

段式存储组织

段式存储：按用户作业中的自然段来划分逻辑空间，然后调入内存，段的长度可以不一样。

段号|段内地址

• 优点：多道程序共享内存，各段程序修改互不影响
• 缺点：内存利用率低，内存碎片浪费大

段页式存储组织

段页式存储：段式与页式的综合体，再分页，1个程序有若干个段，每个段中可以有若干页，每个页的大小相同，但每个段的大小不同。

• 优点：空间浪费小、存储共享容易、存储保护容易、能动态连接
• 缺点：由于管理软件的增加，复杂性和开销也随之增加，需要的硬件以及占用的内容也有所增加，使得执行速度大大下降

页面置换算法

• 最优（Optimal，OPT）算法
• 随机（RAND）算法
• 先进先出（FIFO）算法：有可能产生“抖动”
• 最近最少使用（LRU）算法：不会“抖动”，LRU的理论依据是“局部性原理”
• 时间局部性：刚被访问的内容，立即又被访问。
• 空间局部性：刚被访问的内容，临近的空间很快被访问。

磁盘管理

存取时间=寻道时间+等待时间

• 寻道时间是指磁头移动到磁道所需的时间
• 等待时间为等待读写的扇区转到磁头下方所用的时间。

磁盘调度算法

• 先来先服务（FCFS）
• 最短寻道时间优先（SSTF）
• 扫描算法（SCAN）
• 循环扫描（CSCAN）算法

读取磁盘数据时间计算

读取磁盘数据的时间应包括以下三个部分：

1. 找磁道的时间。
2. 找块（扇区）的时间，即旋转延迟时间。
3. 传输时间。

3.3、作业管理

作业状态与作业管理

作业调度算法

• 先来先服务法
• 时间片轮转法
• 短作业优先法
• 最高优先权优先法
• 高响应比优先法

3.4、文件管理

索引文件结构

树型目录结构

空间存储空间的管理

位示图法

3.5、设备管理

I/O软件

数据传输控制方式

• 程序控制（查询）方式：分为无条件传送和程序查询方式两种。方式简单，硬件开销小，但I/O能力不高，严重影响CPU的利用率。
• 程序中断方式：与程序控制方式相比，中断方式因为CPU无需等待而提高了传输请求的响应速度。
• DMA方式：DMA方式是为了在主存与外设之间实现高速、批量数据交换而设置的。DMA方式比程序控制方式与中断方式都高效。
• 通道方式
• I/O处理机

上述方式按效率从低到高排序。

虚设备与SPOOLING技术

SPOOLing是关于慢速字符设备如何与计算机主机交换信息的一种技术，通常称为“假脱机技术”。SPOOLing技术通过磁盘实现。

四、数据库系统

数据库模型

E-R模型

关系模型

关系代数

• 并
• 交
• 差
• 笛卡尔积
• 投影
• 选择（ π \pi π）
• 联接（ σ \sigma σ）

函数依赖

规范化理论

键

候选键：唯一标识元组，且无冗余

主键：候选键中任选一个

外键：其它关系的主键

求候选键

​ 图示法求候选键

1. 将关系的函数依赖关系，用“有向图”的方式表示
2. 找出入度为0的属性，并以该属性集合为起点，尝试遍历有向图，若能正常遍历图中所有结点，则该属性集即为关系模式的候选键
3. 若入度为0的属性集不能遍历图中所有结点，则需要尝试性的将一些中间结点（既有入度，也有出度的结点）并入入度为0的属性集中，直至该集合能遍历所有结点，集合为候选键

主属性与非主属性

定义：组成候选码的属性就是主属性，其它的就是非主属性。

范式

第一范式：在关系模式R中，当且仅当所有域只包含原子值，即每个属性都是不可再分的数据项，则称关系模式R是第一范式。

第二范式：当且仅当关系模式R是第一范式，且每一个非主属性完全依赖候选键（没有不完全依赖）时，则称关系模式R是第二范式。

第三范式：当且仅当关系模式R是第二范式，且R中没有非主属性传递依赖于候选键时，则称关系模式R是第三范式。

BC范式：设R是一个关系模式，F是它的依赖集，R属于BCNF当且仅当其中F中每个依赖的决定因素必定包含R的某个候选键。

模式分解

保持函数依赖分解

设数据库模式 ρ = { R 1 , R 2 , . . . , R k } \rho=\{R1,R2,...,Rk\} ρ={R1,R2,...,Rk}是关系模式R的一个分解，F是R上的函数依赖集， ρ \rho ρ中每个模式Ri上的FD集是Fi。如果 { F 1 , F 2 , . . . , F k } \{F1,F2,...,Fk\} {F1,F2,...,Fk}与F是等价的（即相互逻辑蕴涵），那么称分解 ρ \rho ρ保持FD。

无损分解

• 有损：不能还原
• 无损：可以还原

无损联接分解：指将一个关系模式分解成若干个关系模式后，通过自然联接和投影等运算仍能还原到原来的关系模式 。

并发控制

事务

• 原子性
• 一致性
• 隔离性
• 持续性

并发产生的问题：

• 丢失更新
• 不可重复读
• 读“脏”数据

解决方案：封锁协议

• S封锁（共享锁）
• X封锁（排它锁）
• 两段锁协议

死锁：预防、死锁的解除

数据库完整性约束

• 实体完整性约束（主键：不能为空，唯一标识）
• 参照完整性约束（外键）
• 用户自定义完整性约束
• 触发器

数据库新技术

五、计算机网络与信息安全

开放系统互连参考模型

OSI/RM七层模型

TCP/IP协议族

• POP3：110端口，邮件收取
• SMTP：25端口，邮件发送
• FTP：20数据端口/21控制端口，文件传输协议
• HTTP：80端口，超文本传输协议，网页传输
• DHCP：67端口，IP地址自动分配
• SNMP：161端口，简单网络管理协议
• DNS：53端口，域名解析协议，记录域名与IP的映射关系
• TCP：可靠的传输层协议
• UDP：不可靠的传输层协议
• ICMP：因特网控制协议，PING命令来自该协议
• IGMP：组播协议
• ARP：地址解析协议，IP地址转换为MAC地址
• RARP：反向地址解析协议，MAC地址转IP地址

IP地址

网络号+主机号

子网划分

• 子网掩码
• 将一个网络划分成多个子网（取部分主机号当子网号）
• 将多个网络合并成一个大的网络（取部分网络号当主机号）

网络存储技术

三层次网络模型

建筑物综合布线系统

网络规划与设计

需求分析

• 网络功能要求
• 网络的性能要求
• 网络运行环境的要求
• 网络的可扩充和可维护性要求

网络规划原则

• 实用性原则
• 开放性原则
• 先进性原则

网络设计与实施原则

• 可靠性原则
• 安全性原则
• 高效性原则
• 可扩展性原则

层次化网络设计

• 核心层
• 汇聚层
• 接入层

计算机网络分类

按分布范围分

• 局域网（LAN）
• 城域网（MAN）
• 广域网（WAN）
• 因特网

按拓扑结构分

• 总线型
• 星型
• 环型

网络介入技术

有线接入

• 公用交换电话网络（PSTN）
• 数字数据网（DDN）
• 综合业务数字网（ISDN）
• 非对称数字用户线路（ADSL）
• 同轴光纤技术（HFC）

无线接入

• IEEE 802.11（WiFi
• IEEE 802.15（蓝牙 Bluetooth）
• 红外（IrD A）
• WAPI

六、信息安全

对称加密技术

对称加密：Ke = Kd

特点：

• 加密强度不够，但效率高
• 密钥分发困难

常见的对称密钥加密算法：DES、3DES（三重DES）、RC-5、IDEA算法

非对称加密技术

非对称加密：密钥必须成对使用（公钥加密，相应的私钥解密）

特点：加密速度慢，但效率高

常见非对称密钥加密算法：RSA、ECC

数字签名

信息摘要

数字摘要：由单项散列函数加密成固定长度的散列值。

常用的消息摘要算法有MD5，SHA等，市场上广泛使用的MD5、SHA算法的散列值分别为128和160位，由于SHA通常采用的密钥长度较长，因此安全性高于MD5。

PGP协议

公共基础设施

网络安全

各个网络层次的安全保障

主动攻击与被动攻击

被动攻击 : 截获 ;

• 目的 : 窃听他人通信内容 ;
• 操作 : 攻击者只观察 , 分析某一协议对应的协议数据单元 PDU , 窃取其中的数据信息 , 但不干扰信息传输 ;
• 别名 : 又称为流量分析 ;

主动攻击 : 中断 , 篡改 , 伪造

• 篡改 : 修改网络上的报文信息 , 又称为更改报文流 ;
• 恶意程序 : 病毒 , 蠕虫 , 木马 , 逻辑炸弹 等 ;
• 拒绝服务攻击 : 攻击者向某服务器不停地发送大量分组 , 使服务器无法正常运行 ;

网络安全协议

DoS（拒绝服务）与DDoS

DoS：是Denial of Service的简称，即拒绝服务，不是DOS操作系统，造成DoS的攻击行为被称为DoS攻击，其目的是使计算机或网络无法提供正常的服务。最常见的DoS攻击有计算机网络带宽攻击和连通性攻击。

DDOS：分布式拒绝服务(DDoS:Distributed Denial of Service)攻击指借助于客户/服务器技术，将多个计算机联合起来作为攻击平台，对一个或多个目标发动DDoS攻击，从而成倍地提高拒绝服务攻击的威力。

防火墙

安全防范体系

安全防范体系的层次划分：

• 物理环境的安全性。包括通信线路、物理设备和机房的安全等。物理层的安全主要体现在通信线路的可靠性（线路备份、网管软件和传输介质）、软硬件设备的安全性（替换设备、拆卸设备、增加设备）、设备的备份、防灾害能力、防干扰能力、设备的运行环境（温度、湿度、烟尘）和不间断电源保障等。
• 操作系统的安全性。主要表现在三个方面，一是操作系统本身的缺陷带来的不安全因素，主要包括身份认证、访问控制和系统漏洞等；二是对操作系统的安全配置问题；三是病毒对操作系统的威胁。
• 网络的安全性。网络层的安全问题主要体现在计算机网络方面的安全性，包括网络层身份认证、网络资源的访问控制、数据传输的保密与完整性、远程接入的安全、域名系统的安全、路由系统的安全、入侵检测的手段和网络设施防病毒等。
• 应用的安全性。由提供服务所采用的应用软件和数据的安全性产生，包括Web服务、电子邮件系统和DNS等。此外，还包括病毒对系统的威胁。
• 管理的安全性。包括安全技术和设备的管理、安全管理制度、部门与人员的组织规则等。管理的制度化极大程度地影响着整个计算机网络的安全，严格的安全管理制度、明确的部门安全职责划分与合理的人员角色配置，都可以在很大程度上降低其他层次的安全漏洞。

计算机病毒与木马

病毒：编制或者在计算机程序中插入的破坏计算机功能或者破坏数据，影响计算机使用并且能够自我复制的一组指令或者程序代码。

木马：计算机木马是一种后门程序，常被黑客用作控制远程计算机的工具。

• 系统病毒（前缀：Win32、PE、W32，如：KCOM-Win32.KCOM）
• 蠕虫病毒（如：恶鹰-Worm。BBeagle）
• 木马病毒、黑客病毒（如：QQ消息尾巴木马-Trojan.QQ3344）
• 脚本病毒（如：红色代码-Script.Redlof）
• 宏病毒（如：梅丽莎-Macro.Melissa）
• 后门病毒（如：灰鸽子-Backdoor.Win32.Huigezi）
• 病毒种植程序病毒（冰河播种者-Dropper.BingHe2.2C）
• 破坏性程序病毒（杀手命令-Harm.Command.Killer）
• 玩笑病毒（如：女鬼-Jioke.Grl ghost）
• 捆绑机病毒（如：捆绑QQ-Binder.QQPass.QQBin）

七、系统开发基础

信息系统开发生命周期

开发模型

• 瀑布模型
• V模型
• 喷泉模型
• 原型化模型
• 演化模型
• 螺旋模型
• 统一过程
• 敏捷方法

软件过程模型

瀑布模型

软件计划->需求分析->软件设计->程序编码->软件测试->运行维护

V模型

喷泉模型（面向对象）

原型化模型

原型化模型第一步就是创建一个快速原型，能够满足项目干系人与未来的用户可以与原型进行交互，再通过与相关干系人进行充分的讨论和分析，最终弄清楚当前系统的需求，进行了充分的了解之后，在原型的基础上开发出用户满意的产品。在实际的项目过程中，借助于组织过程资产以及快速模型软件，一般在需求分析的时候，就可以建立一些简单的原型。原型化模型是极具意义的项目实践。

原型法认为在报难一下子全面准确地提出用户需求的情况下，首先不要求一定要对系统做全面、详细的调查、分析，而是本着开发人员对用户需求的初步理解，先快速开发一个原型系统，然后通过反复修改来实现用户的最终系统需求。

原型应当具备的特点如下。

(1)实际可行。

(2)具有最终系统的基本特征。

(3)构造方便、快速，造价低。

原型法的特点在于原型法对用户的需求是动态响应、逐步纳入的，系统分析、设计与实现都是随着对一个工作模型的不断修改而同时完成的，相互之间并无明显界限，也没有明确分工。系统开发计划就是一个反复修改的过程。适于用户需求开始时定义不清、管理决策方法结构化程度不高的系统开发，开发方法更易被用户接受；但如果用户配合不好，盲目修改，就会拖延开发过程。

可以将原型分类如下。

(1)抛弃型原型（Throw-It-Away Prototype），此类原型在系统真正实现以后就放弃不用了。

(2)进化型原型(Evolutionary Prototype)，此类原型的构造从目标系统的一个或几个基本需求出发，通过修改和追加功能的过程逐渐丰富，演化成最终系统。

演化模型

演化模型主要针对事先不能完整定义需求的软件开发。用户可以给出待开发系统的核心需求，并且当看到核心需求实现后，能够有效地提出反馈，以支持系统的最终设计和实现。软件开发人员根据用户的需求，首先开发核心系统。当该核心系统投入运行后，用户试用之，完成他们的工作，并提出精化系统、增强系统能力的需求。软件开发人员根据用户的反馈，实施开发的迭代过程。第一迭代过程均由需求、设计、编码、测试、集成等阶段组成，为整个系统增加一个可定义的、可管理的子集。

在开发模式上采取分批循环开发的办法，每循环开发一部分的功能，它们成为这个产品的原型的新增功能。于是，设计就不断地演化出新的系统。 实际上，这个模型可看作是重复执行的多个“瀑布模型”。

“演化模型”要求开发人员有能力把项目的产品需求分解为不同组，以便分批循环开发。这种分组并不是绝对随意性的，而是要根据功能的重要性及对总体设计的基础结构的影响而作出判断。有经验指出，每个开发循环以六周到八周为适当的长度。

螺旋原型

软件开发方法

结构化方法

面向数据流的方法

Jackson，面向数据结构的开发方法

• 用户至上
• 严格区分工作阶段，每阶段由任务和结果
• 强调系统开发过程的整体性和全局性
• 系统开发过程工程化，文档资料标准化
• 自顶向下，逐步分解（求精）

原型法

面向对象方法

（喷泉模型）

• 更好的复用性
• 关键在于建立一个全面、合理、统一的模型
• 分析、设计、实现三个阶段，界限不明确

面向服务的方法

（SOA）

统一过程

统一过程就是在软件生命周期过程中以用例为驱动、构架为中心来进行一次一次的增量式的迭代，每次迭代都是以上一次迭代为基础并生成包括构件的源代码体、需求说明、测试用例等的制品。每次的迭代又具体分为四个阶段：初始、细化、构建、交付，而在每个阶段又分为多个工作流：需求、分析、设计、实现和测试等。

初始：

• 确定项目范围和边界
• 识别系统的关键用例
• 展示系统的候选架构
• 估计项目费用和时间
• 评估项目风险

细化：

• 分析系统问题领域
• 建立软件架构基础
• 淘汰最高风险元素

构建：

• 开发剩余的构件
• 构件组装与测试

交付：

• 进行 β \beta β测试
• 制作发布版本
• 用户文档定稿
• 确认新系统
• 培训、调整产品

统一过程模型是基于面向对象方法和UML统一建模语言的，用这种方法论来指导软件开发主要可以解决两个问题：

• 软件复用问题
• 需求变化问题。

敏捷方法

• XP（Extreme Programming，极限编程）在所有的敏捷型方法中，XP是最引人瞩目的，它源于Smalltalk圈子，特别是Kent Beck和Ward Cunningham在20世纪80年代末的密切合作。XP在一些对费用控制严格的公司中使用，已经被证明是非常有效的。

• Cockburn的水晶系列方法，水晶系列方法是由Alistair Cockburn提出的。它与XP方法一样，都有以人为中心的理念，但在实践上有所不同。Alistair考虑到人们一般很难严格遵循一个纪律约束很强的过程，因此，与XP的高度纪律性不同，Alistair探索了用最少纪律约束而仍能成功的方法，从而在产出效率与易于运作上达到一种平衡。也就是说，虽然水晶系列不如XP那样的产出效率，但会有更多的人能够接受并遵循它。

• 开放式源码，这里提到的开放式源码指的是开放源码界所用的一种运作方式。开放式源码项目有一个特别之处，就是程序开发人员在地域上分布很广，这使得它和其他敏捷方法不同。因为一般的敏捷方法都强调项目组成员在同一地点工作。开放源码的一个突出特点就是查错排障（debug）的高度并行性，任何人发现了错误都可将改正源码的“补丁”文件发给维护者。由维护者将这些“补丁”或是新增的代码并入源码库。

• SCRUM（并列争球法）。SCRUM已经出现很久了，像前面所论及的方法一样，该方法强调这样一个事实，即明确定义了的可重复的方法过程只限于定义了的可重复的环境中，为明确定义了的可重复的人员所用，去解决明确定义了的可重复的问题。

• Coad的功用驱动开发方法（FDD- Feature Driven Development）

  FDD是由Jeff De Luca和大师Peter Coad提出来的，像其他方法一样，它致力于短时的迭代阶段和可见可用的功能。在FDD中，一个迭代周期一般是两周。

  在FDD中，编程开发人员分成两类：首席程序员和“类”程序员（class owner）。首席程序员是最富有经验的开发人员，他们是项目的协调者、设计者和指导者，而“类”程序员则主要做源码编写。

• ASD方法，ASD（Adaptive Software Development）方法由Jim Highsmith提出，其核心是三个非线性的、重叠的开发阶段：猜测、合作与学习。

需求分析

应用的工具：

• 数据流图（DFD）
• 数据字典（DD）
• 判定表（由基本条件项、条件项，基本动作项、动作项形成）
• 判定树（决策树）

软件设计

处理流程设计工具

软件设计的任务与活动

模块设计的原则

高内聚低耦合

应用的工具

• IPO图（输入处理输出图）
• PDL（程序描述语言）
• PAD（问题分析图）
• 程序流程图
• N/S盒图

软件测试

动态测试

黑盒测试法

• 等价类划分

  确定无效与有效等价类

  设计用例尽可能多的覆盖有效类

  设计用例只覆盖一个无效类

• 边界值分析

  处理边界情况时最容易出错

  选取的测试数据应该恰好等于、稍小于或稍大于边界值

• 错误推测

• 因果图

白盒测试法

• 语句覆盖
• 判定覆盖
• 条件覆盖
• 条件判定覆盖
• 路径覆盖

灰盒测试法

静态测试

• 桌前检查
• 代码审查
• 代码走查

单元测试

模块接口、局部数据结构、边界条件、独立的路径、错误处理

集成测试

模块间的接口和通信

系统测试

恢复测试、安全性测试、强度测试、性能测试、可靠性测试和安装测试

验收测试

有效性测试、软件配置审查、验收测试

回归测试

负载测试

压力测试

McCabe复杂度

计算有向图G的环路复杂度公式为： V ( G ) = m − n + 2 V(G)=m-n+2 V(G)=m−n+2

或 封闭区域+1

说明：其中V(G)是有向图中的环路个数，m是G中的有向弧数，n是G中的节点数。

软件维护

系统转换

可维护性因素决定

• 可理解性
• 可测试性
• 可修改性

软件维护类型

• 改正性维护
• 适应性维护
• 预防性维护
• 完善性维护

适应性维护：指使应用软件适应信息技术变化和管理需求变化而进行的修改。企业的外部市场环境和管理需求的不断变化也使得各级管理人员不断提出新的信息需求。

完善性维护，扩充功能和改善性能而进行的修改。对已有的软件系统增加一些在系统分析和设计阶段中没有规定的功能与性能特征。

软件文档

开发文档

• 可行性研究和项目任务书
• 需求规格说明
• 功能规格说明
• 设计规格说明（包括程序和数据规格说明）
• 开发计划
• 软件集成和测试计划
• 质量保证计划、标准、进度
• 安全和测试信息

产品文档

• 培训手册
• 参考手册和用户指南
• 软件支持手册
• 产品手册和信息广告

管理文档

• 开发过程的每个阶段的进度和进度变更的记录
• 软件变更情况的记录
• 相对于开发的判定记录
• 职责定义

软件质量保证

软件过程改进

CMMI（软件成熟度模型）

项目管理

• 范围管理
• 时间管理
• 成本管理
• 质量管理
• 人力资源管理
• 沟通管理
• 风险管理
• 采购管理
• 整体管理

八、程序设计语言与语言处理程序基础

编译过程

• 词法错误：非法字符，关键字或标识符拼写错误
• 语法错误：语法结构出错，if endif不匹配，缺分号
• 语义错误：死循环，零除数，其它逻辑错误

文法定义

一个形式文法是一个有序四元组G=（V，T，S，P），其中：

• V：非终结符，不是语言组成部分，不是最终结果，可理解为占位符。
• T：终结符，是语言的组成部分，是最终结果。 V ∩ T = ⊘ V\cap T=\oslash V∩T=⊘
• S：起始符，是语言的开始符号。
• P：产生式，用终结符替代非终结符的规则，形如 α → β \alpha \rightarrow \beta α→β

正则必包：

十一、数据流图

DFD

数据流图的基本概念

数据字典

DD

数据流图平衡原则

父图与子图之间的平衡

指任何一张DFD子图边界上的输入/输出数据流必须与其父图对应加工的输入/输出保持一致。

子图内平衡

• 加工只有输入没有输出，称之为“黑洞”
• 加工只有输出没有输入，称之为“奇迹”
• 加工中输入不足以产生输出，称之为“灰洞”

十二、UML

用例图

用例图描述一组用例，参与者及它们之间的关系。

关系包括：

• 包含关系：其中这个提取出来的公共用例称为抽象用例，而把原始用例称为基本用例或基础用例系：当可以从两个或两个以上的用例中提取公共行为时，应该使用包含关系来表示它们。
• 扩展关系：如果一个用例明显地混合来两种或两种以上的不同场景，即根据情况可能发生多种分支，则可以将这个用例分为一个基本用例和一个或多个扩展用例，这样时描述可能更加清晰。
• 泛化关系：当多个用例共同拥有一种类似的结构和行为的时候，可以将它们的共性抽象称为父用例，其它的用例作为泛化关系中的子用例。在用例的泛化关系中，子用例时父用例的一种特殊形式，子用例继承了父用例所有的结构、行为和关系。

用例建模的流程：

• 识别参与者（必须）
• 合并需求获得用例（必须）
• 细化用例描述（必须）
• 调整用例模型（可选）

类图与对象图

类图（class diagram）：类图描述一组类、接口、协作和它们之间的关系。在面向对象系统的建模中，最常见的图就是类图。类图给出了系统的静态设计视图，活动类的类图给出了系统的静态进程视图。

对象图（object diagram）：对象图描述一组对象及它们之间的关系。对象图描述了在类图中所建立的事物实例的静态快照。和类图一样，这些图给出系统的静态设计视图或静态进程视图，但它们是从真实案例或原型案例的角度建立的。

1：表示一个集合中的一个对象对应另一个集合中1个对象

0…*：表示一个集合中的一个对象对应另一个集合中的0个或多个对象（可以不对应）

1…*：表示一个集合中的一个对象对应另一个集合中的一个或多个对象（至少对应一个）

*：表示一个集合中的一个对象对应另一个集合中的多个的对象

关系：

• 依赖关系
• 泛化关系
• 关联关系，组合关系
• 聚合关系
• 实现关系

序列图

顺序图（sequence diagram，序列图）。顺序图是一种交互图（interaction diagram），交互图展现了一种交互，它由一组对象或参与者以及它们之间可能发送的消息构成。交互图专注于系统的动态视图。顺序图是强调消息的时间次序的交互图。

活动图

活动图（activity diagram）。活动图将进程或其他计算结构展示为计算内部一步步的控制流和数据流。活动图专注于系统的动态视图。它对系统的功能建模和业务流程建模特别重要，并强调对象间的控制流程。

状态图

状态图（state diagram）。状态图描述一个状态机，它由状态、转移、事件和活动组成。状态图给出了对象的动态视图。它对于接口、类或协作的行为建模尤为重要，而且它强调事件导致的对象行为，这非常有助于对反应式系统建模。

通信图

通信图（communication diagram）。通信图也是一种交互图，它强调发消息的对象或参与者的结构组织。顺序图和通信图表达了类似的基本概念，但它们所强调的概念不同，顺序图强调的是时序，通信图强调的是对象之间的组织结构（关系）。

构件图

构件图（component diagram）。构件图描述一个封装的类和它的接口、端口，以及由内嵌的构件和连接件构成的内部结构。构件图用于表示系统的静态设计实现视图。对于由小的部件构建大的系统来说，构件图是很重要的。构件图是类图的变体。

部署图

部署图（deployment diagram）。部署图描述对运行时的处理节点及在其中生存的构件的配置。部署图给出了架构的静态部署视图，通常一个节点包含一个或多个部署图。

十三、数据结构与算法

分治法

对于一个规模为n的问题，若该问题可以容易解决（比如说规模n较小）则直接解决；否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

• 该问题的规模缩小到一定的程度就可以容易地解决
• 该问题可以分解为若干个规模较小的相同问题
• 利用该问题分解出的子问题的解可以合并为该问题的解
• 该问题所分解出的各个子问题是相互对立的

特征：把一个问题拆分成多个小规模的相同子问题，一般可用递归解决。

经典问题：斐波那契数列、归并排序、快速排序、矩阵乘法、二分搜索、大整数乘法、汉诺塔

回溯法

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。这种走不通就退回再走的技术就是回溯法。

• 试探部分（扩大规模）：满足除规模之外的所有条件，则扩大规模

• 回溯部分（缩小规模）：

  1、当前规模不是合法解时回溯（不满足约束条件D）

  2、求完一个解，要求下一个解时，也要回溯。

特征：系统的搜索一个问题的所有解或任一解。

经典问题：N皇后问题、迷宫、背包问题

贪心法

总是做出在当前来说是最好的选择，而并不从整体上加以考虑，它所做的每步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。由于它不必为了寻找最优解而穷尽所有可能解，因此其耗费时间少，一般可以快速得到满意的解，但得不到最优解。

用于求满意解。

特征：局部最优，但整体不见得最优。每步优明确的，既定的策略。

经典问题：背包问题（如装箱）、多机调度、找零钱问题

动态规划法

在求解问题中，对于每一步决策，列出各种可能的局部解，再依据某种判定条件，舍弃那些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解。

用于求最优解。

特征：划分子问题，并把子问题结构使用数组存储，利用查询子问题结构构造最终问题结果

经典问题：斐波那契数列、矩阵乘法、背包问题、LCS最长公共子序列

时间复杂度

1、常数级时间复杂度： O ( 1 ) O(1) O(1)

• 单个语句
• 整个程序没有循环语句，或复杂函数的调用

2、时间复杂度： O ( n ) O(n) O(n)，单层循环

3、时间复杂度： O ( n 2 ) O(n^2) O(n2)，双层循环（多少层循环则为多少次方）

4、时间复杂度： O ( l o g 2 n ) O(log_2n) O(log2​n)，（树）

5、时间复杂度： O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n)，典型代表：堆排序，每次重建堆的时间复杂度是 l o g 2 n log_2n log2​n，n个元素基本上就是 n l o g 2 n nlog_2n nlog2​n

十四、面向对象

十五、设计模式