这是备考软考时的学习笔记, 记录一下学习的要点, 方便复习.
软考<系统架构设计师>
软考<系统架构设计师>备考过程中的学习笔记
- 1: 《第一章》 计算机组成与解构
- 2: 《第二章》 系统配置和性能评价
- 3: 《第三章》 操作系统知识
- 4: 《第四章》 数据库系统
- 5:
- 6: 《第五章》 计算机网络
1 - 《第一章》 计算机组成与解构
考察计算机的硬件组成以及系统解构, 包括计算机的基本硬件组成、中央处理器单元组成、计算机指令系统、存储系统、总线系统等。
考察计算机的硬件组成以及系统解构, 包括计算机的基本硬件组成、中央处理器单元组成、计算机指令系统、存储系统、总线系统等。
计算机系统基础知识
计算机基本硬件系统由
* 运算器
* 控制器
以上集成在一起，统称为CPU (Central Processing Unit), 完成算数、逻辑运算和控制功能。
* 存储器
分为内部存储器和外部存储器。 内部存储器速度高，容量小。 外部存储器速度慢，容量大。
* 输入系统
* 输出系统
统称外部设备。 输入原始数据和指令，输出运行结果。
CPU的功能
* 程序控制
* 操作控制
* 时间控制
* 数据处理
* 中断处理
运算器由 算术逻辑单元ALU，累加寄存器AC，数据缓冲寄存器DR，状态寄存器PSW 组成
运算器：由算术逻辑单元ALU（实现对数据的算术和逻辑运算）、 累加寄存器AC(运算结果或源操作数的存放区）、
数据缓冲寄存器DR(暂时存放内存的指令或数据）、和状态条件寄存器PSW（保存指令运行结果的条件码内容，如溢出标志等）组成。
执行所有的算术运算，如加减乘除等；执行所有的逻辑运算并进行逻辑测试，如与、或、非、比较等。
控制器由 指令寄存器IR，程序计数器PC，地址寄存器， 指令译码器ID 组合
控制器：由指令寄存器IR（暂存CPU执行指令）、程序计数器PC（存放指令执行地址）、
地址寄存器AR(保存当前CPU所访问的内存地址）、指令译码器ID（分析指令操作码）等组成。
控制整个CPU的工作，最为重要。
CPU根据 指令周期的不同阶段 分别去取指令或者数据来区分指令和数据。
一条指令的执行步骤:
取指: PC (程序计数器) -> AR (地址寄存器) -> M存储器 -> DR数据寄存器 -> IR指令寄存器
分析: OP -> ID -> CU控制器
执行: Ad -> AR (地址寄存器) -M存储器 -> DR数据寄存器 -> AC累加器
数据的表示
进制转换
* R进制转十进制 从低位到高位依次乘以R的n次方(从0递增)，求和
> 1011011 转 10进制 => 1*10^0^+1*10^1^+0*10^2^+1*10^3^+1*10^4^+0*10^5^+1*10^6^
* 十进制转R进制 数据除R的余数倒排，直到商为0.
> 456 转 7进制 =》
> 456/7 = 65 ... 1
> 65/7 = 9 ... 2
> 9/7 = 1 ... 2
> 1/7 = 0 ... 1
> 转换结果 = 1221 从下往上排序余数
数的表示
* 数值在机器中的表示形式为机器数，二进制。
* 分为 有符号数和无符号数
- 无符号数表示正数， 没有符号位。
- 有符号数最高位为符号位， 0为正数， 1为负数。
算数运算、逻辑运算
* 算术运算包括 加减乘除
* 逻辑运算包括
- 逻辑与 一个为0结果就为0
- 逻辑或 一个为1结果就为1
- 异或 相同为0 不同为1
- 逻辑非 取反
- 逻辑左移右移
检验码
* 奇偶校验码
- 奇校验码 检查数据1的个数 如果奇数就前面加0， 偶数就前面加1， 使得1的个数保持奇数
- 偶校验码 同上相反
* 循环冗余校验码 **重要**
> 预先约定一个多项式，最高位和最低位必须为1 如 原始信息： 10110 多项式 fn=x^4+x^1+1
> 多项式最高阶为4， 则原始数据后面补上 4个 0 为： 10110 0000
> 有多项式的指数存在为1，不存在为0， 得到 10011
> 10110 0000 / 10011 -> 余数 1111， 如果余数不足4(阶数) 则前面补0 如 0011
> 将原始信息+余数 发送： 10110 1111
* 海明校验码 **重要**
> 原始数据 1011， 校验位处于 1,2,4,8,16,32位置上
> 1 0 1 x 1 x x 原始数据位置 3,5,6,7位置上
> x x x m x m m 校验位在 1,2,4位置上
> 7位置上的拆解为 7=2^2+2^1+2^0, 6=2^2+2^1, 5=2^2+2^0, 3=2^1+2^0
> 即 7位置需要 2,1,0, 6位置需要 2,1 5位置需要2,0 3位置需要1,0 校验位
> 同理 2校验位可校验 7,6,5三个原始数据位， 1校验位可校验 7,6,3三个原始数据位 0校验位可校验 7,5,3 三个原始数据位
> 校验位的值等于可校验的原始数据异或结果
计算机的体系结构
按处理机
* 单处理系统 一个处理单元
* 并行处理系统 两个以上的处理机互联
* 分布式处理系统 远距离的多计算机系统
按指令流和数据流
* 单指令流单数据流SISD 1个控制器 1个处理器 1个存储器
* 单指令流多数据流SIMD 1个控制器 多个处理器 多个存储器
* 多指令流单数据流MISD 多个控制器 1个处理器 多个存储器 不现实
* 多指令流多数据流MIMD 多个控制器 多个处理器 多个存储器
指令系统
计算机指令
* 计算机指令有操作码和操作数组成
* 指令执行分为 取指令，分析指令，执行指令
* 寻址方式
- 顺序寻址 一条指令接着一条指令地顺序执行
- 跳跃寻址 下一条指令的地址码不是由程序计数器给出，而是由本条指令直接给出
- 指令操作数寻址
* 立即寻址 指令的地址码字段指出的不是地址，而是操作数本身
* 直接寻址 指令的地址字段中直接指出操作数在主存中的地址
* 间接寻址 指令地址码字段所指向的存储单元中存储的是操作数的地址
- 寄存器寻址
- 基址寻址
- 变址寻址
- 寻对寻址
指令系统 重要
* 复杂指令系统 CISC
- 指令数量多，使用频率大，可变长指令
- 支持多种寻址方式
- 微程序控制
- 研制周期长
* 精简指令系统 RISC
- 指令数量少， 使用频率接近， 定长指令， 单周期指令
- 支持寻址方式少
- 增加通用寄存器，硬布线逻辑控制， 使用流水线
- 优化编译，支持高级语言
RISC中的流水线技术：
（1)超流水线（Super Pipe Line)技术。它通过细化流水、增加级数和提高主频，使得在每个机器周期内能完成一个甚至两个浮点操作。其实质是以时间换取空间。
（2)超标量（Super Scalar)技术。它通过内装多条流水线来同时执行多个处理，其时钟频率虽然与一般流水接近，却有更小的CPI.其实质是以空间换取时间。
（3) 超长指令字（Very Long Instruction Word,VLIW)技术。VLIW和超标量都是20世纪80年代出现的概念，其共同点是要同时执行多条指令，
其不同在于超标量依靠硬件来实现并行处理的调度，VLIW 则充分发挥软件的作用而使硬件简化，性能提高。
流水线时间计算 重要
* 流水线周期： 指令分成不同的执行阶段， 执行时间最长的段为 流水线周期
* 流水线执行时间： 1条指令的执行时间 + (总指令条数-1)*流水线周期
* 流水线的吞吐率： 单位时间内执行的指令条数， = 指令条数/流水线执行时间
* 流水线的加速比： 使用流水线后比不适用流水线快了多少倍。 = 不使用流水线时间/使用流水线时间
某计算机系统采用5级流水线结构， 每条指令分 取指令2t， 分析指令1t， 去操作数3t， 运算1t， 写回结果2t，分别用5个部件完成。
流水线周期： 5个阶段的执行时间最长的 3t
流水线执行时间： (2t+1t+3t+1t+2t)+(n-1)*3t
流水线吞吐率： n/(2t+1t+3t+1t+2t)+(n-1)*3t ~~~ n无限大时候 1/3t
10条指令的时候， 流水线加速比 = (2t+1t+3t+1t+2t)*10/(2t+1t+3t+1t+2t)+(10-1)*3t = 5/2
单缓冲区、双缓冲区
* 有三个阶段 读入缓冲区， 送入用户去， 处理数据
> 单缓冲区中： 缓冲区和用户区都只有一个，一块数据必须读入+送出才算完成。 因此单缓冲区中这两个阶段合并， 处理数据独立
> 结果是 单缓冲区最终为 读取送出 + 处理数据 两个阶段
> 双缓冲区中： 由于两个缓冲区读入可以交替进行，但是用户区只有一个， 不能合并， 再加上数据处理， 最终为 读入缓冲区 + 送入用户区 + 处理数据 三个阶段
假设计算机输入、输出采用双缓冲区工作，磁盘块与缓冲区大小相等。 每个磁盘块读入10ms， 缓冲区送入用户区6ms， 数据处理用时2ms。
如果想要将10块磁盘块大小的文档从磁盘读入给用户处理
采用单缓冲区时， 读入数据送出到用户可以看做一个阶段16ms， 数据处理一个阶段2ms
即流水线执行时间 (16ms+2ms)*(10-1)*16ms = 162ms
采用双缓冲区时，读入数据10ms 送出到用户6ms 不能合并 数据处理单独2ms
即流水线执行时间 (10ms+6ms+2ms)+(10-1)*10ms = 108ms
存储系统
计算机存储解构
计算机采用分级存储体系的主要目的是为了解决存储容量、成本和速度之间的矛盾问题。
局部性原理：总的来说，在CPU运行时，所访问的数据会趋向于一个较小的局部空间地址内，包括下面两个方面：
> 时间局部性原理：如果一个数据项正在被访问，那么在近期它很可能会被再次访问，即在相邻的时间里会访问同一个数据项。
> 空间局部性原理：在最近的将来会用到的数据的地址和现在正在访问的数据地址很可能是相近的，即相邻的空间地址会被连续访问。
* cpu内部寄存器 -》 高速缓存cache -》 主存储器DRAM -》 联机磁盘 -》 脱机存盘、光盘
Cache
地址映射：在CPU工作时，送出的是主存单元的地址，而应从Cache存储器中读／写信息。这就需要将主存地址转换为Cache存储器地址，
这种地址的转换称为地址映像，由硬件自动完成映射
> 直接映像：将Cache存储器等分成块，主存也等分成块并编号。主存中的块与Cache中的块的对应关系是固定的，
也即二者块号相同才能命中。地址变换简单，但不灵活，容易造成资源浪费。
> 全相联映像：同样都等分成块并编号。主存中任意一块主存块号都与Cache中任意一块对应。因此可以随意调入Cache任意位置，
但地址变换复杂，速度较慢。因为主存可以随意调主存块号入Cache任意块，只有当Cache满了才会发生块冲突，是最不容易发生块冲突的映像方式（考点）。
> 组组相连映像：前面两种方式的结合，将Cache存储器先分块再分组，主存也同样先分块再分组，组间采用直接映像，即主存中组号与Cache中组号相同的组才能命中，
但是组内全相联映像，也即组号相同的两个组内的所有块可以任意调换
Cache替换算法（cache满了就要替换）
替换算法的目标就是使Cache 获得尽可能高的命中率。常用算法有如下几种：
（a)随机替换算法：就是用随机数发生器产生一个要替换的块号，将该块替换出去。
（b)先进先出算法：就是将最先进入Cache的信息块替换出去。
（c)近期最少使用算法：这种方法是将近期最少使用的Cache中的信息块替换出去。
（d)优化替换算法：这种方法必须先执行一次程序，统计Cache的替换情况。有了这样的先验信息，在第二次执行该程序时便可以用最有效的方式来替换。
地址编号从80000H到BFFFFH且按字节编址的内存容量为（）KB,若用16K*4bit的存储器芯片构成该内存，共需（）片
A.128 B.256 C.512 D.1024
A.8 B.16 C.32 D.64
内存容量=BFFFFH-80000H+1=C0000H-80000H=4*16^4=4*2^16bit = 4*2^6KB = 2^8KB = 256KB
单片存储器 16K*4bit=8K*8bit=8KB 256/8=32片
若用256K×8bit的存储器芯片，构成地址40000000H到400FFFFFH且按字节编址的内存区域，则需（）片芯片。
A.4 B.8 C.16 D.32
内存容量= 400FFFFFH-40000000H+1=40100000H-40000000H=1*16^5H=2^20B
单片=256K*8bit=2^8*2^10*2^3bit=2^18B
需要使用： 2^20B/2^18B = 4片
内存按字节编址从B3000H到DABFFH的区域，其存储容量为（）。
A.123KB B.159KB C.163KB D.194KB
内存容量=DABFFH-B3000H+1=DAC00H-B3000H=27C00H=2*16^4+7*16^3+C*16^2=162816=159KB
内存按字节编址，从A1000H到B13FFH的区域的存储容量为（1）KB。
A.32 B.34 C.65 D.67
内存容量=B13FFH+1-A1000H=B1400H-A1000H=10400H=16^4+4*16^2=2^16+2^2*2^8=2^16+2^10bit/2^10=2^6+1=65KB
若某计算机字长为32位，内存容量为2GB，按字编址，则可寻址范围为（4）。
A.1024M B.1GB C.512M D.2GB
字长32bit/字8bit=4
可寻址范围=2GB/4=512Mb
内存容量2GB=2*1024*1024*1024*8位，按字编址时，存储单元的个数为2*1024*1024*1024*8/32=512*1024*1024,即可寻址范围为512MB。
存储系统-磁盘
* 磁盘
- 磁盘有两个盘面， 每个盘面有多个同心圆（磁道）， 每个磁道划分多个扇区
- 磁盘存取时间 = 寻道时间 + 等待时间(转动延迟)
* 磁盘调度
- 先来先服务 FIFS 按照进程要求顺序读取
- 最短寻道时间优先 SSTF 每次访问与当前磁道最近的磁道
- 扫描算法 SCAN 先寻找最近的磁道， 然后同方向读取完毕， 再回头反方向读取
- 单向扫描算法 CSCAN 永远只单向移动
磁盘调度先进行移臂调度， 再进行旋转调度。 假设磁盘移动臂目前在21号柱面。
有一下调度请求
柱面 磁头 扇区
17 8 9
23 6 3
23 9 6
32 10 5
17 8 4
32 3 10
17 7 9
23 10 4
38 10 8
采用最短移臂调度算法请求顺序
当前在21号柱面， 移动最近柱面 17号， 然后移动到 23号柱面， 然后 32号柱面， 然后 38号柱面
磁盘上存储数据的排列方式影响I/O效率， 假设一个磁道分为10个扇区， 每个扇区1个逻辑记录，
假设磁盘转速 30ms/周， 磁头当前在 1号数据处， 当使用单缓冲区时， 处理数据时间为 6ms。
处理所有数据最长时间为： 需要转10圈 30ms*10 = 300ms 加最后一个数据处理时间 6ms 总计 306ms
优化数据存储后最少时间为： 读取第1块数据后，处理6ms，间隔两个数据块正好读 第2块， 依次类推 即每个数据块需要9ms * 10块 = 90ms
- RAID0 没有提供冗余， 数据分成多个块， 同时写入每个磁盘， 同时读或者同时写 效率为单块磁盘的N倍
- RAID1 数据同时写入成对的磁盘互为备份， 提高读取性能 读快写慢
- RAID2 数据条块化存储到不同的磁盘， 使用海明码校验
- RAID3 使用奇偶校验， 单块磁盘存储校验码
- RAID5 至少3块磁盘 数据和校验交叉存储到所有磁盘， 总校验数据量为1块磁盘
输入输出设备
输入输出设备的编址方式
常见的编址方式有两种：
- I/O端口和存储器分开编址，又被称为I/O映像的方式
内存地址和接口地址是完全独立的两个地址空间。访问数据时所使用的指令也完全不同，用于接口的指令只用于接口的读／写，
其余的指令全都是用于内存的。因此，在编程序或读程序时很易使用和辨认。这种编址方法的缺点是用于接口的指令太少、功能太弱。
- I/O端口和存储器统一编址，又称为存储器映像的I/O方式（常见）
内存地址和接口地址统一在一个公共的地址空间里，即内存单元和接口共用地址空间。优点是原则上用于内存的指令全都可以用于接口，
这就大大地增强了对接口的操作功能，而且在指令上也不再区分内存或接口指令。该编址方法的缺点就在于整个地址空间被分成两部分，
其中一部分分配给接口使用，剩余的为内存所用，这经常会导致内存地址不连续。
计算机与外设的数据交换方式
- 查询方式
CPU主动查询外设是否完成数据传输，效率极低。
- 中断方式
外设完成数据传输后，向CPU发送中断，等待CPU处理数据，效率对较高
中断响应时间: 从发出中断请求到开始进入中断处理程序；
中断处理时间: 从中断处理开始到中断处理结束。
中断向量提供中断服务程序的入口地址。
多级中断嵌套，使用堆栈来保护断点和现场
- DMA方式（direct memory access）
CPU只需完成必要的初始化等操作，数据传输的整个过程由DMA控制器来完成（CPU让出对总线的控制权），在主存和外设之间建立直接的数据通路，效率很高
在一个总线周期结束后，CPU会响应DMA请求开始读取数据；CPU响应程序中断方式请求是在一条指令执行结束时
总线
总线（Bus),是指计算机设备和设备之间传输信息的公共数据通道
- 内部总线：内部芯片级别的总线，芯片与处理器之间通信的总线。
- 系统总线：是板级总线，用于计算机内各部分之间的连接，具体分为数据总线（并行数据传输位数）、地址总线（系统可管理的内存空间的大小）、控制总线（传送控制命令）。
代表的有ISA总线、EISA总线、PCI总线。（考试主要考计算机内部的三个总线）
- 外部总线：设备一级的总线，微机和外部设备的总线。代表的有RS232(串行总线）、SCSI(并行总线）、USB(通用串行总线，即插即用，支持热插拔）
- 单工数据传输：一般用在只向一个方向传输数据的场合
- 半双工数据传输：允许数据在两个方向上传输,但是,在某一时刻,只允许数据在一个方向上传输,它实际上是一种切换方向的单工通信
- 全双工数据通信：允许数据在同一时刻同时在两个方向上传输,因此,全双工通信是两个单工通信方式的结合,它要求发送设备和接收设备都有独立的接收和发送能力
系统可靠性
系统可靠性指标
* 平均无故障时间 MTTF = 1/失效率
* 平均故障修复时间 MTTR = 1/修复率
* 平均故障间隔时间 MTBF = MTTF+MTTR
* 系统可用性 = MTTF/(MTTF+MTTR)*100%
- 串联系统，一个设备不可靠，整个系统崩溃，整个系统可靠性R=R1*R2*...*Rn！
- 并联系统，所有设备都不可靠，整个系统才崩溃，整个系统可靠性R=1-(1-R1)＊（1-R2)*...*(1-Rn).
2 - 《第二章》 系统配置和性能评价
考察计算机、路由器、交换机等性能指标和性能评价方法及阿姆达尔定律等知识
考察计算机、路由器、交换机等性能指标和性能评价方法及阿姆达尔定律等知识
性能指标
性能指标是软、硬件的性能指标的集成。硬件包括计算机、各种通信交换设备、各类网络设备等；软件包括操作系统、协议以及应用程序等。
计算机
评价计算机的主要性能指标有：时钟频率（主频）、运算速度、运算精度、内存的存储容量、存储器的存取周期、
数据处理速率（Processing Data Rate，PDR）、吞吐率、各种响应时间、各种利用率、
RASIS特性（即可靠性、可用性、可维护性、完整性和安全性）、平均故障响应时间、兼容性、可扩充性、性能价格比。
路由器
评价路由器的主要性能指标有：设备吞吐量、端口吞吐量、全双工线速转发能力、背靠背帧数、路由表能力、
背板能力、丢包率、时延、时延抖动、VPN支持能力、内部时钟精度、队列管理机制、端口硬件队列数、
分类业务带宽保证、RSVP、IP Diff Serv、CAR支持、冗余、热插拔组件、路由器冗余协议、网管、
基于Web的管理、网管类型、带外网管支持、网管粒度、计费能力／协议、
分组语音支持方式、协议支持、语音压缩能力、端口密度、信令支持。
交换机
评价交换机的主要性能指标有：大 SONET端口数、最大FDDI端口数、背板吞吐量、缓冲区大小、最大MAC地址表大小、
最大电源数、支持协议和标准、路由信息协议（RIP）、RIP2（开放式最短路径优先算法第2版）、边界网关协议（BGP）、
无类域间路由（CIDR）、互联网成组管理协议（IGMP）、距离矢量多播路由协议（DVMRP）、开放式最短路径优先多播路由协议（MOSPF）、
协议无关的多播协议(PIM）、资源预留协议（RSVP）、802.1p优先级标记、多队列、路由、支持第3层交换、支持多层（4到7层）交换、
支持多协议路由、支持路由缓存、可支持最大路由表数、VLAN、最大VLAN数量、网管、支持网管类型、支持端口镜像、QoS、
支持基于策略的第2层交换、每端口最大优先级队列数、支持基于策略的第3层交换、支持基于策略的应用级QoS、支持最小／最大带宽分配、
冗余、热交换组件（管理卡，交换结构，接口模块，电源，冷却系统）、支持端口链路聚集协议、负载均衡。
网络
评价网络的性能指标有：设备级性能指标、网络级性能指标、应用级性能指标、用户级性能指标、吞吐量。
操作系统
评价操作系统的性能指标有：可靠性、吞吐率（量）、响应时间、资源利用率、可移植性。
数据库管理系统
衡量数据库管理系统的主要性能指标包括数据库本身和管理系统两部分。具体有：数据库的大小、数据库中表的数量、单个表的大小、
表中允许的记录（行）数量、单个记录（行）的大小、表上所允许的索引数量、数据库所允许的索引数量、
最大并发事务处理能力、负载均衡能力、最大连接数等。
Web服务器
评价Web服务器的主要性能指标有：最大并发连接数、响应延迟、吞吐量。
性能评价方法
性能评价的常用方法
* 时钟频率法。一般来讲，主频越高，速度越快。
* 指令执行速度法。计量单位KIPS、MIPS。
* 等效指令速度法。统计各类指令在程序中所占的比例，并进行折算，是一种固定比例法。
* 数据处理速率法。。采用计算PDR值的方法来衡量机器性能，PDR值越大，机器性能越好。
PDR与每条指令和每个操作数的平均位数以及每条指令的平均运算速度有关。
基准程序法（Benchmark）
测试程序。基准程序法是目前被用户一致承认的测试性能的较好方法，基准程序多种多样，包括：
* 整数测试程序。同一厂家的机器，采用相同的体系结构，用相同的基准程序测试，得到的MIPS值越大，
一般说明机器速度越快。
* 浮点测试程序。指标MFLOPS（Million Floating-point Operations Per Second）（理论峰值浮点速度）。
* SPEC基准程序（SPEC Benchmark）。重点面向处理器性能的基准程序集，将被测计算机的执行时间标准化，
即将被测计算机的执行时间除以一个参考处理器的执行时间。
* TPC基准程序。用于评测计算机在事务处理、数据库处理、企业管理与决策支持系统等方面的性能。
其中，TPC-C是在线事务处理（On-line Transaction Processing，OLTP）的基准程序，
TPC-D是决策支持的基准程序。TPC-E是为大型企业信息服务的基准程序。
大多数情况下，为测试新系统的性能，用户必须依靠评价程序来评价机器的性能。
以下4种评价程序：真实的程序、核心程序、小型基准程序、合成基准程序，评测的准确程度依次递减。
阿姆达尔定律
阿姆达尔（Amdahl）定律主要用于系统性能改进的计算中。
阿姆达尔定律是指计算机系统中对某一部件采用某种更快的执行方式所获得的系统性能改变程度，取决于这种方式被使用的频率，或所占总执行时间的比例。
阿姆达尔定律定义了采用特定部件所取得的加速比。假定我们使用某种增强部件，计算机的性能就会得到提高，
- 加速比 = 不使用增强部件时完成整个任务的时间 / 使用增强部件时完成整个任务的时间
- 加速比 = 原来的执行时间 / 新的执行时间 = 1/[(1-增强比例)+增强比例/增强加速比]
假设某一功能的处理时间为整个系统运行时间的60%,若使该功能的处理速度提高至原来的5倍，则根据阿姆达尔定律，整个系统的处理速度可提高至原来的（）倍。 加速比 = 原来的执行时间 / 新的执行时间 = 1/[(1-增强比例)+增强比例/增强加速比] 增强比例 = 60% = 0.6， 增强加速比 = 5 加速比 = 1/[(1-0.6)+0.6/5] = 1/0.52 ~~ 1.92
3 - 《第三章》 操作系统知识
考察操作系统概述、进程管理、存储管理、设备管理和文件管理等知识
考察操作系统概述、进程管理、存储管理、设备管理和文件管理等知识
操作系统概述
定义
操作系统能有效的组织和管理系统中的各种软硬件资源，合理的组织计算机系统工作流程，控制程序的执行，
并向用户提供良好的工作环境和用户接口。
操作系统的作用：
* 通过资源管理提高计算机系统的效率
* 改善人机界面向用户提供友好的工作环境
4个特性： 并发性、共享性、虚拟性和不确定性。
功能
* 进程管理
对处理机的“时间”进行管理，采用多道程序等技术将CPU时间合理分配
包括 进程控制、进程同步、进程通信和进程调度。
* 文件管理
包括 文件存储空间管理、目录管理、文件读写管理和存取控制。
* 存储管理
对主存储空间进行管理，包括 存储的分配与回收、存储保护、地址映像(变换)和主存扩充。
* 设备管理
对硬件设备管理，包括 输入/输出设备的分配、启动、完成和回收。
* 作业管理
包括 任务、界面管理、人机交互、图形界面、语音控制和虚拟现实。
操作系统的分类
* 批处理操作系统 分 单道批处理系统 和 多道批处理系统
* 分时操作系统 将CPU的工作时间划分多个时间片，轮流用各个用户终端工作。
* 实时操作系统 对外来信息能够以足够快的速度处理，并在被控对象允许时间范围内做出反应
对交互能力要求不高，但要求可靠
* 网络操作系统 使联网计算机能够方便高效的共享网络资源，为网络用户提供各种软件服务和协议。
三种模式： 集中模式、服务器/客户机模式和对等模式
* 分布式操作系统 多个无主次的分散计算机连接而成
* 微型计算机系统 WIN，MacOS, Linux
* 嵌入式操作系统 运行在嵌入芯片中，对智能芯片和操作控制的部件进行统一协调、处理、指挥和控制。
特点：
- 微型化 占用资源和系统代码量小
- 可定制 可运行在不同处理器平台，能针对硬件变化进行调整
- 实时性 用于过程控制、数据采集、传输通信等实时性较高的领域
- 可靠性 高可靠性，要害应用有冗余防错和防故障要求
- 易移植性 采用底层抽象HAL 和 板级支撑包BSP 的底层技术 提高可移植性
嵌入式初始化采用自底向上的初始化方式
芯片级初始化(微处理器初始化)-》板卡级初始化(其他硬件设备初始化)-》系统初始化(软件及操作系统初始化)。
* 微内核操作系统 尽可能内核做的小，只将核心东西放入内核，其他放到用户进程中。
系统分为 用户态和内核态
单体内核 图形、设备驱动、文件系统都在内核实现 减少了进程间通信和状态切换，提高了运行效率， 占用资源多，稳定性和安全性不好。
微内核 只有基本功能，图形、驱动、文件系统在内核之外 便于移植，系统服务在用户空间，稳定性和可靠性，安全性高，可用于分布式，
用户态和内核态切换频繁效率低
分布式操作系统与网络操作系统有什么不同之处?
(1)分布性:分布式操作系统是驻留在系统的各个结点上,
而网络操作系统的控制功能大部分是集中在服务器上。
(2)并行性:分布式操作系统可将一个用户的多个任务分配到多个计算机上并行执行;而网络环境下,
每个用户的一个或多个任务只能在自己的计算机上处理。
(3)透明性:分布式系统能隐藏自己内部的物理位置、并发控制、系统故障等实现细节来使用系统;
而网络操作系统计算机之间的通信需要IP地址。
(4)共享性:分布式系统中,所有分布在各个站点的软、硬件资源均可供系统中所有用户共享,并能以透明的方式使用它们;
而网络操作系统共享的资源大多数是设置在服务器中,它机的资源一般由本机用户使用。
(5)健壮性:分布式系统任何结点的故障都不会对系统造成太大的影响,某些部件的故障可以通过容错技术实现系统的重构;
而网络操作系统的控制功能大部分集中在服务器中,这使得服务器会成为单点故障,它一出故障,就会影响整个系统的可靠性。
进程管理
进程的组成
进程有 程序控制块PCB，程序，数据组成
进程三态 就绪态、运行态、阻塞态
PCB进程块的存储方式： 线性表，链式表，索引表
前趋图和进程资源图
前趋图 用来表示那些任务可以并行执行， 那些任务之间有顺序关系，有向无环图。
前驱图中增加信号量的时候， 从左向右，从前向后，从小到大， s1,s2,s3....
进程资源图 用来表示进程和资源之间的分配和请求关系。
进程的同步和互斥
互斥 表示同一个资源在同一个时间只能有一个进程使用
同步 表示两个任务和同时执行，不存在资源的单独占用和共享问题
P操作：申请资源，S=S-1,若S>=0,则执行P操作的进程继续执行；
若S<0,则置该进程为阻塞状态（因为无可用资源），并将其插入阻塞队列。
V操作：释放资源，S=S+1,若S>0,则执行V操作的进程继续执行；
若S<=0,则从阻塞状态唤醒一个进程，并将其插入就绪队列（此时因为缺少资源被P操作阻塞的进程可以继续执行），
然后执行v操作的进程继续。
信号量
- 临界资源 各个进程间需要互斥方式使用的资源
- 临界区 每个进程中访问临界资源的代码
- 信号量
* 互斥信号量： 对临界资源采用互斥访问， 使用互斥信号量后其他进程无法使用 初始化=1
* 同步信号量： 对共享资源的访问控制， 初始化=资源数量
进程调度
进程调度是指当有更高优先级的进程到来时，如何分配CPU。
- 可剥夺 指当有更高优先级的进程到来时，强制将CPU分配给高优先级的进程
- 不可剥夺 指高优先级的进程必须等待当前进程释放CPU
一个作业要经历高中低三级调度
* 高级调度 又叫长调度、作业调度。 决定输入池中那个作业可以进入主系统成为就绪进程， 仅一次
* 中级调度 又叫中程调度、对换调度。 决定交换区中的哪个就绪进程可以进入内存参与争夺CPU。
* 低级调度 又叫短程调度、进程调度。 决定内存中的哪个进程可以占用CPU
在单处理机系统中，采用先来先服务调度算法。系统中有4个进程P1、P2、P3、P4(假设进程按此顺序到达），
其中P1为运行状态，P2为就绪状态，P3和P4为等待状态，且P3等待打印机，P4等待扫描仪。
若P1（）,则P1、P2、P3和P4的状态应分别为（）
--------------------------------------
A.时间片到 B.释放了扫描仪 C.释放了打印机 D.已完成
A.等待、就绪、等待和等待
B.运行、就绪、运行和等待
C.就绪、运行、等待和等待
D.就绪、就绪、等待和运行
第一个空不能选D，已完成则第二空就不能等待/运行/就绪。
第二个空P3,P4不管那个资源有了，都是从等待到就绪， 所以只能选C， 还是等待中，
则第一个空只能选A，时间片到了P1转为就绪，P2运行，P3、P4继续等待。
调度算法
* 先来先服务 FCFS， 先到达的进程先占用CPU
* 时间片轮转 分配给每个进程大小相等的时间片，轮流使用CPU，
* 优先级调度 每个进度有独自的优先级，优先级高的优先使用CPU
* 多级反馈调度 设置从高到低不同优先级队列，进程分配不同优先级和时间片。
首先进入最高级队列， 执行完成后进入次一次的队列。 直到执行完成退出
死锁问题
当一个进程等待永远不会发生的事情时， 就会死锁。
死锁的必要条件： 资源互斥、进程占用并等待其他资源、系统不能剥夺进程资源、进程资源图是一个环路。
打破死锁：
- 死锁预防： 采用某种策略限制并发进程对资源的请求
- 死锁避免： 采用银行家算法，提前分配资源，如果死锁则不分配资源
- 死锁检测： 定时检测死锁并加以清除
- 死锁解除： 强制剥夺资源，清除死锁进程
死锁资源计算：
系统有n个进程， 每个进程请求r个资源
发生死锁的最大资源数为： n*(r-1)
不发生死锁的最小资源数为： n*(r-1)+1
线程
进程有两个属性： 可拥有资源的独立单位、可独立调度和分配的基本单位
进程在创建、撤销和切换中，要付出较大的时空开销。
引入线程作为调度和分配的基本单位， 进程作为独立分配资源的单位
存储管理
分区存储管理
就是整存， 将进程运行所需的内存整体全部分配给它再执行
- 固定分区 静态分区法，主存分为若干固定区
- 可变分区 动态分区法， 主存空间在作业转入时正好划分所需的空间
* 首次适应法 按地址顺序从头查找大于等于需要的空间分配
* 最佳适应法 所有空闲分区排序，找到最接近需要大小的空间
* 最差适应法 找到空闲分区中最大的分配
* 循环首次适应法 按顺序继续查找，不再从头开始找，区别首次适应法
- 可重定位分区 移动所有已分配好的分区，使其连续
分页存储管理
根据可变分区演化
逻辑页包括 页号+页内地址。 页内地址就是物理偏移地址， 页号与物理块号通过页表查询对照，找到物理块号+偏移地址
优点： 利用率高，碎片小，分配和管理建单
缺点： 增加了系统开销，可能产生抖动
1) 根据页面大小可计算出页内地址的位数
2) 页内地址位数结合逻辑地址计算出页内地址（即，块内地址）和页号
3) 页号结合页表，即可得出块号
4) 块号&块内地址即可得出物理地址
有多少个页，决定了我的页号是多少位，
4GB=（4*1024*1024）KB进程，分的每页是4KB，
这个时候就是有（4*1024*1024）KB/4KB= 2^20个页数，对应的两进制是20位，也就是页号有20位，
所以说有多少个页，就决定了我的页号是多少位！
页号有多少位跟页数多少有关
页内地址跟什么相关？页内地址是根据页的大小来的，比如页大小是4KB=（4*1024）B=2^12，所以页地址就是12位！
某计算机系统页面大小为4K,若进程的页面变换表如下所示，逻辑地址为十六进制1D16H.该地址经过变换后，其物理地址应为十六进制（）。
系统页面大小4K，决定页内地址位数 4K=4*1024b=2^12b 即页内地址 12位
逻辑地址1D16H,低三位正好是12位二进制页内地址，则最高位的1 是页号
地址表示和转换
地址组成： 页地址+页内偏移地址， 页地址在高位
物理地址： 物理块号+页内偏移地址
逻辑地址： 页号+页内偏移地址
首先求出页号的位数， 得到页号， 去页表对照得到物理块号， 加上页内偏移地址得到实际地址
页面置换算法
例如： 进程需要100个页面， 系统只有10个物理块，则需要加载马上要执行的页面
* 最优算法 理论算法
* 先进先出算法 先调入内存的页面先调出
* 最近最少使用算法 进程执行过程中，过去最少使用的页面先调出
* 淘汰原则 优先淘汰最近未访问的页面，而后淘汰最近未修改的页面
快表
快表是一个小容量相连存储器，由快速存储器组成，按内容访问，速度快
快表是将页表放入Cache，慢表是页表放入内存上，慢表访问两次内存，快表访问Cache+内存，速度更快
段式存储管理
将内存为每个段分配一个连续的分区，段的长度由相应的逻辑信息组的长度决定，因而各段长度不等， 每段由段号和段内地址。每段物理大小不同
优点： 多道程序共享内存，各段程序修改不互影响
缺点： 内存利用率低，内存碎片大
分页是根据物理空间划分，每页大小相同
分段是根据逻辑空间划分，每段大小不同
地址表示
地址组成： 段号+段内偏移
段页式存储管理
对进程空间先分段，再分页。
优点： 空间浪费小，存储共享容易，存储保护容易、能动态链接。
缺点： 复杂性和开销增加，执行速度下降
设备管理
设备分类
设备是计算机系统与外界交互的工具，具体负责计算机与外部的输入／输出工作，所以常称为外部设备（简称外设）
设备的分类：
按数据组织分类：块设备、字符设备。
按照设备功能分类：输入设备、输出设备、存储设备、网络联网设备、供电设备。
资源分配角度分类：独占设备、共享设备和虚拟设备。
数据传输速率分类：低速设备、中速设备、高速设备。
将负责管理设备和输入／输出的机构称为I/O系统 I/O系统由设备、控器、通道（具有通道的计算机系统）、总线和／0软件组成。
设备管理的任务是保证在多道程序环境下，当多个进程竞争使用设备时，按一定的策略分配和管理各种设备，控制设备的各种操作，完成I/0设备与主存之间的数据交换。
设备管理的主要功能是动态地掌握并记录设备的状态、设备分配和释放、缓冲区管理、实现物理I/O设备的操作、提供设备使用的用户接口及设备的访问和控制。
缓冲管理、设备分配与回收、设备处理和虚拟设备
I/O软件
当用户程序试图读一个硬盘文件时，需要通过操作系统实现这一操作。
与设备无关软件检查高速缓存中有无要读的数据块，若没有，则调用设备驱动程序，向I/O硬件发出一个请求。
然后，用户进程阻塞并等待磁盘操作的完成。
当磁盘操作完成时，硬件产生一个中断，转入中断处理程序。
中断处理程序检查中断的原因，认识到这时磁盘读取操作已经完成，于是唤醒用户进程取回从磁盘读取的信息，从而结束此次I/O请求。
用户进程在得到了所需的硬盘文件内容之，后继续运行。
文件管理
概述
文件是具有符号名的、在逻辑上具有完整意义的一组相关信息项的集合。
信息项是构成文件内容的基本单位，可以是一个字符，也可以是一个记录，记录可以等长，也可以不等长。
一个文件包括文件体和文件说明。
文件体是文件真实的内容。
文件说明是操作系统为了管理文件所用到的信息，包括文件名、文件内部标识、文件的类型、文件存储地址、文件的长度、访问权限、建立时间和访问时间等。
文件管理系统，就是操作系统中实现文件统一管理的一组软件和相关数据的集合，专门负责管理和存取文件信息的软件机构，简称文件系统
文件的类型
按文件性质和用途可将文件： 系统文件、库文件和用户文件。
按信息保存期限分类可将文件： 临时文件、档案文件和永久文件。
按文件的保护方式分类可将文件： 只读文件、读／写文件、可执行文件和不保护文件。
UNIX系统将文件： 普通文件、目录文件和设备文件（特殊文件）。
文件结构
文件结构分为逻辑结构和物理结构
文件的逻辑结构可分为两大类：有结构的记录式文件；无结构的流式文件。
文件的物理结构是指文件在物理存储设备上的存放方法
连续结构：连续结构也称顺序结构，它将逻辑上连续的文件信息（如记录）依次存放在连续编号的物理块上。
链接结构：链接结构也称串联结构，它是将逻辑上连续的文件信息（如记录）存放在不连续的物理块上，
每个物理块设有一个指针指向下一个物理块。
索引结构：将逻辑上连续的文件信息（如记录）存放在不连续的物理块中，系统为每个文件建立一张索引表。
索引表记录了文件信息所在的逻辑块号对应的物理块号，并将索引表的起始地址放在与文件对应的文件目录项中。
多个物理块的索引表：索引表是在文件创建时由系统自动建立的，并与文件一起存放在同一文件卷上。
根据一个文件大小的不同，其索引表占用物理块的个数不等，一般占一个或几个物理块。
索引文件结构
索引结构分了直接索引跟间接索引。
直接索引，每个索引节点直接指向一个物理盘块。
间接索引，每一个索引节点，存放的是又一个索引节点，终结点还是指向物理盘块！（分为一级间接索引，二级间接索引，三级间接索引.......
设文件索引节点中有8个地址项，每个地址项大小为4字节，其中5个地址项为直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，
磁盘索引块和磁盘数据块大小均为1KB,
若要访问文件的逻辑块号分别为5和518,则系统应分别采用（）,而且可表示的单个文件最大长度是（）KB.
5个地址项为直接地址索引 可以访问0~4号逻辑块
2个地址项是一级间接地址索引 每个索引块1KB=2^10B 每地址项4字节=2^2B， 每个一级地址索引可拥有：2^10/2^2=2^8=256个逻辑块
即：2个地址项是一级间接地址索引共有512个逻辑块编号可访问5~511号逻辑块
1个地址项是二级间接地址索引 每个索引块包含256个一级间接地址索引 总计 256*256=65536个物理块
总计可索引： 65536+512+4 = 66052个物理块
> 依题意，5个直接地址索引可以表示5×1KB=5KB，其逻辑块号是0-4；
> 一级间接地址索引可以产生的索引项为1024/4=256，
> 一级间接索引可以表示256×1KB=256KB， 其逻辑块号是5～511；
> 2个一级间接地是索引表示256×2=512KB，
> 二级间接索引产生的二级间接索引项也为256，因此二级索引表示256×256KB=65536KB，其逻辑块号是512-65535。
> 由于5＞4，因此要访问逻辑块号为5的文件，系统应采用一级间接地址索引。
> 而518＞511，要访问逻辑块号为518的文件，则系统应采用二级间接地址索引。
文件目录
文件控制块中包含以下三类信息：基本信息类、存取控制信息类和使用信息类。
基本信息类。例如文件名、文件的物理地址、文件长度和文件块数等。
存取控制信息类。文件的存取权限，像UNIX用户分成文件主、同组用户和一般用户三类，这三类用户的读／写执行。
使用信息类。文件建立日期、最后一次修改日期、最后一次访问的日期、当前使用的信息（如打开文件的进程数、在文件上的等待队列）等。
文件控制块的有序集合称为文件目录。
相对路径：是从当前路径开始的路径。
绝对路径：是从根目录开始的路径。
全文件名＝绝对路径＋文件名。
要注意，绝对路径和相对路径是不加最后的文件名的，只是单纯的路径序列。
文件存储空间管理
文件的存取方法是指读／写文件存储器上的一个物理块的方法
通常有顺序存取和随机存取两种方法。
顺序存取方法是指对文件中的信息按顺序依次进行读／写；
随机存取方法是指对文件中的信息可以按任意的次序随机地读／写。
文件存储空间的管理：
- 空闲区表。将外存空间上的一个连续的未分配区域称为“空闲区”。
操作系统为磁盘外存上的所有空闲区建立一张空闲表，每个表项对应一个空闲区，适用于连续文件结构。
- 位示图这种方法是在外存上建立一张位示图（Bitmap),记录文件存储器的使用情况。
每一位对应文件存储器上的一个物理块，取值0和1分别表示空闲和占用。（注意位示图是考点）
- 空闲块链。每个空闲物理块中有指向下一个空闲物理块的指针，所有空闲物理块构成一个链表，
链表的头指针放在文件存储器的特定位置上（如管理块中），不需要磁盘分配表，节省空间。
- 成组链接法。例如，在实现时系统将空闲块分成若干组，每100个空闲块为一组，
每组的第一个空闲块登记了下一组空闲块的物理盘块号和空闲块总数。假如某个组的第一个空闲块号等于0,意味着该组是最后一组，无下一组空闲块。
某文件管理系统采用位示图（bitmap)记录磁盘的使用情况。
如果系统的字长为32位，磁盘物理块的大小为4MB,物理块依次编号为：0、1、2、．．．，位示图字依次编号为：0、1、2、．．
那么16385号物理块的使用情况在位示图中的第（ )个字中描述：如果磁盘的容量为1000GB,那么位示图需要（ )个字来表示。
16385 转为十六进制=4001H, 4001H/32bit = 4*16^3+1/2^5 =2^2*2^12+1/2^5=2^9+1 = 512 + 1即在512字上
总计物理块 = 1000GB/4MB = 1000*1024MB / 4MB=1000*256块， 即需要2^8*1000个bit的位示图，
系统字长32bit， 2^8*1000/2^5=2^3*1000=8000 字
4 - 《第四章》 数据库系统
考察数据库系统
考察数据库系统
数据库系统
数据：是数据库中存储的基本对象，是描述事物的符号记录。
数据的种类：文本、图形、图像、音频、视频、学生的档案记录、货物的运输情况等。
数据库DB:是长期存储在计算机内、有组织的、可共享的大量数据的集合。
数据库的基本特征：
数据按一定的数据模型组织、描述和存储；
可为各种用户共享；
冗余度较小；
数据独立性较高；
易扩展。
数据库系统DBS:是一个采用了数据库技术，有组织地、动态地存储大量相关数据，
方便多用户访问的计算机系统。其由下面四个部分组成：
数据库（统一管理、长期存储在计算机内的，有组织的相关数据的集合）
硬件（构成计算机系统包括存储数据所需的外部设备）
软件（操作系统、数据库管理系统及应用程序）
人员（系统分析和数据库设计人员、应用程序员、最终用户、数据库管理员DBA)
数据库管理系统DBMS的功能
实现对共享数据有效的组织、管理和存取。
包括数据定义、数据库操作、数据库运行管理、数据的存储管理、数据库的建立和维护等。
三级模式-两级映像
内模式：管理如何存储物理的数据，对应具体物理存储文件。
模式一内模式映像：是表和数据的物理存储之间的映射，存在概念级和内部级之间，
若修改了数据存储方式，只需要修改此映射，而不需要去修改应用程序。
模式：又称为概念模式，就是我们通常使用的基本表，根据应用、需求将物理数据划分成一张张表。
外模式一模式映像：是表和视图之间的映射，存在于概念级和外部级之间，
若表中数据发生了修改，只需要修改此映射，而无需修改应用程序。
外模式：对应数据库中的视图这个级别，将表进行一定的处理后再提供给用户使用。
扩展下，三级模式-两级映像存在的意义是什么？
主要保证了数据的独立性，数据的独立性是指数据与程序独立，
将数据的定义从程序中分离出来，由DBMS（数据库管理系统）负责数据的存储，
从而简化应用程序，大大减少应用程序编制的工作量。
数据的独立性是由DBMS的二级映像功能来保证的。数据的独立性包括数据的物理独立性和数据的逻辑独立性。
什么是数据的物理独立性？
答：数据的物理独立性是指当数据库的内模式发生改变时，数据的的逻辑结构不变。
由于应用程序处理的只是数据的逻辑结构，这样物理独立性可以保证，
当数据的物理结构改变了，应用程序不用改变。
但是，为了保证应用程序能够正确执行，需要修改概念模式/内模式之间的映像。
什么是数据的逻辑独立性？
答：数据的逻辑独立性是指用户的应用程序与数据库结构是相互独立的。
数据的逻辑结构发生变化后，用户程序也可以不修改。
但是，为了保证应用程序能够正确执行，需要修改外模式/概念模式之间的映像。
数据库设计
需求分析：即分析数据存储的要求，产出物有数据流图、数据字典、需求说明书。
概念结构设计：就是设计E-R图，也即实体－联系图，与物理实现无关，说明有哪些实体，实体有哪些属性。
逻辑结构设计：将E-R图，转换成关系模式，也即转换成实际的表和表中的列属性，这里要考虑很多规范化的东西。
物理设计：根据生成的表等概念，生成物理数据库。
数据模型
关系模型是二维表的形式表示的实体－联系模型（做开发的人可以理解为数据库表），是将实体－联系模型转换而来的，经过开发人员设计的；
概念模型是从用户的角度进行建模的，是现实世界到信息世界的第一抽象，是真正的实体－联系模型。
网状模型表示实体类型及其实体之间的联系，一个事物和另外几个都有联系，形成一张网。
面向对象模型是采用面向对象的方法设计数据库，以对象为单位，每个对象包括属性和方法，具有类和继承等特点。
数据模型三要素：数据结构（所研究的对象类型的集合）、数据操作（对数据库中各种对象的实例允许执行的操作的集合）、数据的约束条件（一组完整性规则的集合）。
关系代数
关系代数就是说白了就是表跟表之间的逻辑运算！
- 并：结果是两张表中所有记录数合并，相同记录只显示一次。
- 交：结果是两张表中相同的记录。
- 差：S1-S2,结果是S1表中有而S2表中没有的那些记录。
- 笛卡尔积：S1*S2,产生的结果包括S1和S2的所有属性列，并且S1中每条记录依次和S2中所有记录组合成一条记录，最终属性列为S1+S2属性列，记录数为S1*S2记录数。
- 投影：实际是按条件选择某关系模式中的某列，列也可以用数字表示。符号（π）
- 选择：实际是按条件选择某关系模式中的某条记录。符号（σ）
- 自然连接：自然连接的结果显示全部的属性列，但是相同属性列只显示一次，显示两个关系模式中属性相同且值相同的记录。
笛卡尔积与自然连接相互转换的原则：先投影（π），选出不重复的列，然后选择（σ）找出相同的行。
函数依赖
给定一个X，能唯一确定一个Y，就称X确定Y，或者说Y依赖于X，例如Y=X*X函数。
部分函数依赖：A可确定C，(A,B)也可确定C，(A,B)中的一部分（即A)可以确定C,称为部分函数依赖。
传递函数依赖：当A和B不等价时，A可确定B，B可确定C，则A可确定C,是传递函数依赖；若A和B等价，则不存在传递，直接就可确定C。
设关系模式R<U,F>，U是关系模式R的属性全集，F是关系模式R的一个函数依赖集。
- 对于R<U,F>来说有以下的：
- 自反律：若Y⊆X⊆U，则X→Y为F所逻辑蕴含。
- 增广律：若X→Y为F所逻辑蕴含，且Z⊆U,则XZ→YZ为F所逻辑蕴含。
- 传递律：若X→Y和Y→Z为F所逻辑蕴含，则X→Z为F所逻辑蕴含。
- 合并规则：若X→Y，X→Z，则X→YZ为F所蕴涵。
- 伪传递率：若X→Y,WY→Z,则XW→Z为F所蕴涵。
- 分解规则：若X→Y，Z⊆Y，则X→Z为F所蕴涵
键与约束
超键：能唯一标识此表的属性的组合。
候选键：超键中去掉冗余的属性，剩余的属性是候选键。
主键：任选一个候选键，即可作为主键。
外键：其他表中的主键。
主属性：候选键内的属性为主属性，其他属性为非主属性。
以学生表为例（包含学号，身份证号，姓名，年龄），
假设学号，身份证号是唯一标识，超键只要包含学号，身份证号即可，
比如（学号，身份证号），（学号，身份证号，姓名），（学号，身份证号，姓名，年龄），以上都属于超键，有没有冗余没有关系！
候选键就是（学号，身份证号），去掉冗余的属性。
主键就是，学号或者身份证号，任选一个候选键即可。
实体完整性约束：即主键约束，主键值不能为空，也不能重复。
参照完整性约束：即外键约束，外键必须是其他表中已经存在的主键的值，或者为空。
用户自定义完整性约束：自定义表达式约束，如设定年龄属性的值必须在0到150之间。
范式
第一范式 关系中的每一个分量必须是一个不可分的数据项。通俗地说，第一范式就是表中不允许有小表的存在。
用一个单一的关系模式学生来描述学校的教务系统：学生（学号，学生姓名，系号，系主任姓名，课程号，成绩）
依赖关系：（学号->学生姓名，学号->系号，系号->系主任姓名，学号->课程号，（学号，课程号）->成绩）
第二范式 如果关系R属于1NF,且每一个非主属性完全函数依赖于任何一个候选码，则R属于2NF.
通俗地说，2NF就是在1NF的基础上，表中的每一个非主属性不会依赖复合主键中的某一个列。
第二范式，消除了非主属性对于主属性的部分函数依赖！
部分函数依赖只存在于联合主键里，
主键是多个的才存在部分函数依赖！对于只有一个主键，它必然满足第二范式！
上面的学生表就不满足2NF,因为学号不能完全确定课程号和成绩（每个学生可以选多门课）。
将学生表分解为：
学生（学号，学生姓名，系编号，系名，系主任）
选课（学号，课程号，成绩）。
第三范式 在满足2NF的基础上，表中不存在非主属性对码的传递依赖。
学生关系模式就不属于3NF，
因为学生无法直接决定系主任和系名，是由学号－＞系编号，再由系编号－＞系主任，系编号－＞系名，因此存在非主属性对主属性的传递依赖。
将学生表进一步分解为：
学生（学号，学生姓名，系编号）
系（系编号，系名，系主任）
选课（学号，课程号，成绩）
BC范式 BC范式BCNF，是指在第三范式的基础上进一步消除主属性对于码的部分函数依赖和传递依赖。
通俗的来说，就是在每一种情况下，每一个依赖的左边决定因素都必然包含候选键
并发控制
事务：由一系列操作组成，这些操作，要么全做，要么全不做，拥有四种特性，详解如下：
- 原子性：要么全做，要么全不做。
- 一致性：事务发生后数据是一致的，例如银行转账，不会存在A账户转出，但是B账户没收到的情况。
- 隔离性：任一事务的更新操作直到其成功提交的整个过程对其他事务都是不可见的，不同事务之间是隔离的，互不干涉。
- 持续性：事务操作的结果是持续性的。
事务是并发控制的前提条件，并发控制就是控制不同的事务并发执行，提高系统效率，但是并发控制中存在下面三个问题：
- 丢失更新：事务1对数据A进行了修改并写回，事务2也对A进行了修改并写回，此时事务2写回的数据会覆盖事务1写回的数据，就丢失了事务1对A的更新。即对数据A的更新会被覆盖。
- 不可重复读：事务2读A,而后事务1对数据A进行了修改并写回，此时若事务2再读A，发现数据不对。即一个事务重复读A两次，会发现数据A有误。
- 读脏数据：事务1对数据A进行了修改后，事务2读数据A，而后事务1回滚，数据A恢复了原来的值，那么事务2对数据A做的事是无效的，读到了脏数据。
封锁协议
X锁是排它锁（写锁）。若事务T对数据对象A加上X锁，则只允许T读取和修改A，其他事务都不能再对A加任何类型的锁，直到T释放A上的锁。
S锁是共享锁（读锁）。若事务T对数据对象A加上S锁，则只允许T读取A，但不能修改A，其他事务只能再对A加S锁（也即能读不能修改），直到T释放A上的S锁。
共分为三级封锁协议，如下：
* 一级封锁协议：事务在修改数据R之前必须先对其加X锁，直到事务结束才释放。 可解决丢失更新问题。
* 二级封锁协议：一级封锁协议的基础上加上事务T在读数据R之前必须先对其加S锁，读完后即可释放S锁。 可解决丢失更新、读脏数据问题。
* 三级封锁协议：一级封锁协议加上事务T在读取数据R之前先对其加S锁，直到事务结束才释放。 可解决丢失更新、读脏数据、数据重复读问题。
数据库安全
* 静态转储：即冷备份，指在转储期间不允许对数据库进行任何存取、修改操作；
优点是非常快速的备份方法、容易归档（直接物理复制操作）；
缺点是只能提供到某一时间点上的恢复，不能做其他工作，不能按表或按用户恢复。
* 动态转储：即热备份，在转储期间允许对数据库进行存取、修改操作，因此，转储和用户事务可并发执行；
优点是可在表空间或数据库文件级备份，数据库扔可使用，可达到秒级恢复；
缺点是不能出错，否则后果严重，若热备份不成功，所得结果几乎全部无效。
* 完全备份：备份所有数据。
* 差量备份：仅备份上一次完全备份之后变化的数据。
* 增量备份：备份上一次备份之后变化的数据。
* 日志文件：在事务处理过程中，DBMS把事务开始、事务结束以及对数据库的插入、删除和修改的每一次操作写入日志文件。
一旦发生故障，DBMS的恢复子系统利用日志文件撤销事务对数据库的改变，回退到事务的初始状态。
**差量备份跟增量备份的区别是，差量备份是备份上一次完全备份之后变化的数据，（主要是这个上一次完全备份！**
分布式数据库
分布式也有自己的三级模式两级映像
局部数据库位于不同的物理位置，使用一个全局DBMS将所有局部数据库联网管理，这就是分布式数据库。
分片模式
水平分片：将表中水平的记录分别存放在不同的地方。
垂直分片：将表中的垂直的列值分别存放在不同的地方。
分布透明性
分片透明性：用户或应用程序不需要知道逻辑上访问的表具体是如何分块存储的。
位置透明性：应用程序不关心数据存储物理位置的改变。
逻辑透明性：用户或应用程序无需知道局部使用的是哪种数据模型。
复制透明性：用户或应用程序不关心复制的数据从何而来。
数据仓库技术
数据仓库是一个面向主题的、集成的、非易失的、且随时间变化的数据集合，用于支持管理决策。
- 面向主题：按照一定的主题域进行组织的。
- 集成的：数据仓库中的数据是在对原有分散的数据库数据抽取、清理的基础上经过系统加工、汇总和整理得到的，
必须消除源数据中的不一致性，以保证数据仓库内的信息是关于整个企业的一致的全局信息。
- 相对稳定的：数据仓库的数据主要供企业决策分析之用，所涉及的数据操作主要是数据查询，
一旦某个数据进入数据仓库以后，一般情况下将被长期保留，也就是数据仓库中一般有大量的查询操作，
但修改和删除操作很少，通常只需要定期的加载、刷新。
- 反映历史变化：数据仓库中的数据通常包含历史信息，系统记录了企业从过去某一时点（如开始应用数据仓库的时点）到目前的各个阶段的信息，
通过这些信息，可以对企业的发展历程和未来趋势做出定量分析和预测。
数据仓库的结构通常包含四个层次，如下图所示：
1.数据源：是数据仓库系统的基础，是整个系统的数据源泉。
2.数据的存储与管理：是整个数据仓库系统的核心。
3.OLAP(联机分析处理）服务器：对分析需要的数据进行有效集成，按多维模型组织，以便进行多角度、多层次的分析，并发现趋势。
4.前端工具：主要包括各种报表工具、查询工具、数据分析工具、数据挖掘工具以及各种基于数据仓库或数据集市的应用开发工具。
BI系统主要包括数据预处理、建立数据仓库、数据分析和数据展现四个主要阶段。
数据预处理是整合企业原始数据的第一步，它包括数据的抽取（Extraction)、转换（Transformation)和加载（Load)三个过程（ETL过程）；
建立数据仓库则是处理海量数据的基础；
数据分析是体现系统智能的关键，一段采用联机分析处理（OLAP)和数据挖掘两大技术。联机分析处理不仅进行数据汇总／聚集，
同时还提供切片、切块、下钻、上卷和旋转等数据分析功能，用户可以方便地对海量数据进行多维分析。
数据挖掘的目标则是挖掘数据背后隐藏的知识，通过关联分析、聚类和分类等方法建立分析模型，预测企业未来发展趋势和将要面临的问题；
在海量数据和分析手段增多的情况下，数据展现则主要保障系统分析结果的可视化。
5 -
设计模式的三大类 创建型模式（Creational Pattern）：对类的实例化过程进行了抽象，能够将软件模块中对象的创建和对象的使用分离。
（5种）工厂模式、抽象工厂模式、单例模式、建造者模式、原型模式
记忆口诀：创工原单建抽（创公园，但见愁） 结构型模式（Structural Pattern）：关注于对象的组成以及对象之间的依赖关系，描述如何将类或者对象结合在一起形成更大的结构，就像搭积木，可以通过简单积木的组合形成复杂的、功能更为强大的结构。
（7种）适配器模式、装饰者模式、代理模式、外观模式、桥接模式、组合模式、享元模式
记忆口诀：结享外组适代装桥（姐想外租，世代装桥） 行为型模式（Behavioral Pattern）：关注于对象的行为问题，是对在不同的对象之间划分责任和算法的抽象化；不仅仅关注类和对象的结构，而且重点关注它们之间的相互作用。
（11种）策略模式、模板方法模式、观察者模式、迭代器模式、责任链模式、命令模式、备忘录模式、状态模式、访问者模式、中介者模式、解释器模式
记忆口诀：行状责中模访解备观策命迭（形状折中模仿，戒备观测鸣笛）
创建型模式
简单工厂模式
简单工厂模式通常就是这样，一个工厂类 XxxFactory，里面有一个静态方法，根据我们不同的参数，返回不同的派生自同一个父类（或实现同一接口）的实例对象。
工厂模式
核心在于，我们需要在第一步选好我们需要的工厂。比如，我们有 LogFactory 接口，实现类有 FileLogFactory 和 KafkaLogFactory，分别对应将日志写入文件和写入 Kafka 中，显然，我们客户端第一步就需要决定到底要实例化 FileLogFactory 还是 KafkaLogFactory，这将决定之后的所有的操作。
抽象工厂模式
单例模式
建造者模式
核心是：先把所有的属性都设置给 Builder，然后 build() 方法的时候，将这些属性复制给实际产生的对象。
原型模式
原型模式很简单：有一个原型实例，基于这个原型实例产生新的实例，也就是“克隆”了。
Object 类中有一个 clone() 方法，它用于生成一个新的对象，当然，如果我们要调用这个方法，java 要求我们的类必须先实现 Cloneable 接口，
此接口没有定义任何方法，但是不这么做的话，在 clone() 的时候，会抛出 CloneNotSupportedException 异常。
创建型模式总结
创建型模式总体上比较简单，它们的作用就是为了产生实例对象，算是各种工作的第一步了，因为我们写的是面向对象的代码，所以我们第一步当然是需要创建一个对象了。
简单工厂模式最简单；工厂模式在简单工厂模式的基础上增加了选择工厂的维度，需要第一步选择合适的工厂；抽象工厂模式有产品族的概念，如果各个产品是存在兼容性问题的，就要用抽象工厂模式。
单例模式就不说了，为了保证全局使用的是同一对象，一方面是安全性考虑，一方面是为了节省资源；建造者模式专门对付属性很多的那种类，为了让代码更优美；原型模式用得最少，了解和 Object 类中的 clone() 方法相关的知识即可。
结构型模式
代理模式
代理模式是最常使用的模式之一了，用一个代理来隐藏具体实现类的实现细节，通常还用于在真实的实现的前后添加一部分逻辑。
既然说是代理，那就要对客户端隐藏真实实现，由代理来负责客户端的所有请求。当然，代理只是个代理，它不会完成实际的业务逻辑，而是一层皮而已，但是对于客户端来说，它必须表现得就是客户端需要的真实实现。
适配器模式
适配器模式做的就是，有一个接口需要实现，但是我们现成的对象都不满足，需要加一层适配器来进行适配。
适配器模式总体来说分三种：默认适配器模式、对象适配器模式、类适配器模式
适配器模式总结
类适配和对象适配的异同
一个采用继承，一个采用组合；
类适配属于静态实现，对象适配属于组合的动态实现，对象适配需要多实例化一个对象。
总体来说，对象适配用得比较多。
适配器模式和代理模式的异同
比较这两种模式，其实是比较对象适配器模式和代理模式，在代码结构上，它们很相似，都需要一个具体的实现类的实例。但是它们的目的不一样，
代理模式做的是增强原方法的活；适配器做的是适配的活，为的是提供“把鸡包装成鸭，然后当做鸭来使用”，而鸡和鸭它们之间原本没有继承关系。
桥梁模式
装饰模式
门面模式
组合模式
享元模式
结构型模式总结 前面，我们说了代理模式、适配器模式、桥梁模式、装饰模式、门面模式、组合模式和享元模式。读者是否可以分别把这几个模式说清楚了呢？在说到这些模式的时候，心中是否有一个清晰的图或处理流程在脑海里呢？
代理模式是做方法增强的，适配器模式是把鸡包装成鸭这种用来适配接口的，桥梁模式做到了很好的解耦，装饰模式从名字上就看得出来，适合于装饰类或者说是增强类的场景，门面模式的优点是客户端不需要关心实例化过程，只要调用需要的方法即可，组合模式用于描述具有层次结构的数据，享元模式是为了在特定的场景中缓存已经创建的对象，用于提高性能。
行为型模式
策略模式
观察者模式
责任链模式
模板方法模式
状态模式
行为型模式总结 行为型模式部分介绍了策略模式、观察者模式、责任链模式、模板方法模式和状态模式，其实，经典的行为型模式还包括备忘录模式、命令模式等
各分类中模式的关键点
创建型模式：对象实例化的模式，创建型模式用于解耦对象的实例化过程。
5种）工厂模式、抽象工厂模式、单例模式、建造者模式、原型模式
记忆口诀：创工原单建抽（创公园，但见愁）
单例模式：某个类只能有一个实例，提供一个全局的访问点。 单例模式（Singleton Pattern）
简单工厂：一个工厂类根据传入的参量决定创建出那一种产品类的实例。 工厂模式（Factory Pattern）
工厂方法：定义一个创建对象的接口，让子类决定实例化那个类。
抽象工厂：创建相关或依赖对象的家族，而无需明确指定具体类。 抽象工厂模式（Abstract Factory Pattern）
建造者模式：封装一个复杂对象的构建过程，并可以按步骤构造。 建造者模式（Builder Pattern）
原型模式：通过复制现有的实例来创建新的实例。 原型模式（Prototype Pattern）
结构型模式：把类或对象结合在一起形成一个更大的结构。
（7种）适配器模式、装饰者模式、代理模式、外观模式、桥接模式、组合模式、享元模式
记忆口诀：结享外组适代装桥（姐想外租，世代装桥）
适配器模式：将一个类的方法接口转换成客户希望的另外一个接口。 适配器模式（Adapter Pattern）
组合模式：将对象组合成树形结构以表示“”部分-整体“”的层次结构。 组合模式（Composite Pattern）
装饰模式：动态的给对象添加新的功能。 装饰器模式（Decorator Pattern）
代理模式：为其他对象提供一个代理以便控制这个对象的访问。 代理模式（Proxy Pattern）
亨元（蝇量）模式：通过共享技术来有效的支持大量细粒度的对象。 享元模式（Flyweight Pattern）
外观模式：对外提供一个统一的方法，来访问子系统中的一群接口。 外观模式（Facade Pattern）
桥接模式：将抽象部分和它的实现部分分离，使它们都可以独立的变化。 桥接（Bridge）
行为型模式：类和对象如何交互，及划分责任和算法。
（11种）策略模式、模板方法模式、观察者模式、迭代器模式、责任链模式、命令模式、备忘录模式、状态模式、访问者模式、中介者模式、解释器模式
记忆口诀：行状责中模访解备观策命迭（形状折中模仿，戒备观测鸣笛）
模板模式：定义一个算法结构，而将一些步骤延迟到子类实现。 模板模式（Template Pattern）
解释器模式：给定一个语言，定义它的文法的一种表示，并定义一个解释器。 解释器模式（Interpreter Pattern）
策略模式：定义一系列算法，把他们封装起来，并且使它们可以相互替换。 策略模式（Strategy Pattern）
状态模式：允许一个对象在其对象内部状态改变时改变它的行为。 状态模式（State Pattern）
观察者模式：对象间的一对多的依赖关系。 观察者模式（Observer Pattern）
备忘录模式：在不破坏封装的前提下，保持对象的内部状态。 备忘录模式（Memento Pattern）
中介者模式：用一个中介对象来封装一系列的对象交互。 中介者模式（Mediator Pattern）
命令模式：将命令请求封装为一个对象，使得可以用不同的请求来进行参数化。 命令模式（Command Pattern）
访问者模式：在不改变数据结构的前提下，增加作用于一组对象元素的新功能。 访问者模式（Visitor Pattern）
责任链模式：将请求的发送者和接收者解耦，使的多个对象都有处理这个请求的机会。 责任链模式（Chain of Responsibility Pattern）
迭代器模式：一种遍历访问聚合对象中各个元素的方法，不暴露该对象的内部结构。 迭代器模式（Iterator Pattern）
应用层： http协议：超文本传输协议， TCP 端口号80， 常用的还有8080、8081、9080
https：443/tcp 443/udp
SOCKS： 代理协议， 常用端口号8080
FTP：文件传输协议 20 数据传输 21 控制指令传输，选用TCP连接
telnet：远程登录，常用端口号23/tcp
SSH 安全登录 SCP 文件传输，默认端口22/tcp
DHCP：动态主机配置协议，服务器是67，客户机是68
POP3：接收协议 端口TCP 110）
DNS：域名系统 UDP 53）
1-1024是众所周知的端口。1025-65535是动态端口
TCP 1863端口：MSN Messenger的文件传输功能所使用的端口 TCP 5000端口：DB2 UDP 8000端口：腾讯QQ 0保留端口
mysql默认端口是3306 sqlserver默认端口是1433 TCP 1521端口：Oracle数据库服务 上面三层是定义应用程序的功能
6 - 《第五章》 计算机网络
考察计算机网络
考察计算机网络