加密技术 对称加密 发送者与接收者受用同一套密钥 特点： 密钥分发困难 加密强度不高，但效率高 常见对称加密算法：DES、3DES、RC-5、IDEA 非对称加密 加密是一套密钥，解密是另一套密钥 公钥体系中： 用公钥加密，私钥解密，可实现保密通信 用私钥加密，公钥解密，可实现数字签名 公钥私钥成对出现，成对使用 特点：速度慢，但强度高 常见非对称加密算法：RSA、ECC 数字签名 证明文件签发人，验证真实性 发送方的私钥加密，发送方公钥解密 消息摘要 数字摘要：有单向散列函数加密成固定长度散列值，不可逆 常用消息摘要算法: MD5,SHA. MD5是128位，SHA160位，因此SHA安全性更高 PKI公钥体系 即公开密钥管理体系 由于公钥私钥需要成对出现，当密钥过多时难以管理，因此需要一个管理系统(CA)来管理密钥的注册、更新、注销，并且颁发证书给服务器并签名
计算机体系结构 Flynn分类 体系结构类型 结构 关键特性 代表 单指令流单数据流 SISD 1控制部分 1处理器 1主存模块 单处理器系统 单指令流多数据流 SIMD 1控制部分 多处理器 多主存模块 各处理器以异步形式执行同一条指令 并行处理机 阵列处理机 超级向量处理机 多指令流单数据流 MISD 多控制部分 1处理器 多主存模块 被证明不可能，至少是不实际 目前没有，有文献称流水线计算机为此类 多指令流多数据流 MIMD 多控制部分 多处理器 多主存模块 能够实现作业、任务、指令等各级全面升级 多处理机系统 多计算机 指令的基本概念 一条指令就是机器语言的一个语句，是一组有意义的二进制代码 指令基本格式如下： 操作码字段 地址码字段 操作码指出计算机要执行什么性质的操作，如加减法、存取数等 地址码需要包含各操作数的地址及操作结果的存放地址，从其地址结构的角度可分为三地址指令、二地址指令、一地址指令、零地址指令 寻址方式 寻址方式 特点 立即寻址 操作数直接放指令 速度快 灵活性差 直接寻址 指令中放操作数地址 间接寻址 指令放地址，地址对应内容是操作数地址 寄存器寻址 寄存器放操作数 寄存器间接寻址 寄存器内存放操作数地址 CISC和RISC 指令系统类型 指令 寻址方式 实现方式 其他 CISC（复杂指令集计算机） 数量多 使用频率差别大 变长格式 多种 微程序控制技术（微码） 研制周期长 RISC（精简指令集计算机） 数量少 使用频率接近 定长格式 大部分单周期指令 操作寄存器只有Load/store操作内存 少 增加通用寄存器 硬布线逻辑控制为主 适合采用流水线 优化编译 有效支持高级语言 比较维度 指令数量、指令使用频率、寻址方式、寄存器、流水线支持、高级语言支持 ...
校验码 基础知识 码距：任何一种编码都由许多码字构成，任意两个码字之间最少变化的二进制尾数就被称为数据校验码的码距（即取最小的），用于检测有效编码发生错误 码距的计算 10 与 01 是两个合法编码，他们之间的码距为2 用4位二进制表示16种状态，则有16种不同的码字，此时码距为1 如 0000 与 0001 检验错误 假如有一组有效的二进制数字0000，0011，1100，0110，1001，1010，0101,这一组的码距是2，在传输过程中如果0000被传为0001，只有一位发生错误，那么计算机就可以检测出来这个错误，而且不管是哪一个编码，只要误传的位数为1那么都可以检测出来。 但是假如有一组有效的三位二进制数数据000,001,010,011,101,110,111这一组的码距就是1，在传输过程中如果000被误传为001,由于001也是有效数据，所以就会将000当作001了，无法检测发生了错误。 校验方式 奇偶校验 奇偶校验的编码方式是：由若干位有效信息（如一个字节），再加上一个二进制位（校验位）组成校验码 奇校验：整个校验码（有信心和校验位种）1的个数为奇数 **偶校验：**整个校验码（有信心和校验位种）1的个数为偶数 只可以校验1位错误，不可纠错 循环冗余校验码CRC 原理 可检错，不可纠错 CRC的编码方式是：在k位信息码之后拼接r位校验码 CRC编码规律如下： 把接收到的CRC码用约定多项式G(x)去除，如果正确，余数为0，出错，不为0. 不同位出错其余数不同 模2除法 CRC主要利用了模2除法 加法不进位，减法不借位 例子： $$ \begin{align} &原始报文为 1100 1010 101,\ &其生成多项式为 x^4+x^3+x+1 \ &对其CRC编码后结果为? \end{align} $$ [答案]:11001010101 0011 [解析]: 按多项式系数得到除数与K+1=5，然后把模2除法得到的K位结果附加在最后 海明码校验 可检错，也可纠错 海明校验码的原理是： 在有效信息位中加入几个校验位形成海明码, 使码距比较均匀地拉大，并把海明码的每个二进制位分配到几个奇偶校 验组中。 当某一位出错后，就会引起有关的几个校验位的值发生变化， 这不但可以发现错误，还能指出错误的位置，为自动纠错提供了依据 ✨确定校验位个数的公式 $$ \begin{align} & \begin{cases} r:校验位个数\ m:数据位个数 \end{cases} \ \ &2^r-1>=m+r \end{align} $$ 纠错原理 ...
总线 一条总线同一时刻仅允许一个设备发送、但允许多个设备接收 总线分为三大类数据总线、地址总线、控制总线 数据总线 在CPU和RAM之间来回传送需要处理或是需要储存的数据 地址总线 用来指定在RAM(Random Access Memory)之中存储的数据的地址 控制总线 将微处理器控制单元的信号，传送到周边设备，一般常见的为USB Bus和1394 Bus 总线结构的好处 简化系统结构，便于系统设计 大大减少连线数目，便于布线，减小体积，提高系统可靠性 便于接口设计，所有与总线相连的设备均采用类似接口 便于系统扩充，更新与灵活配置，易于实现系统的模块化 便于设备软件设计 便于故障诊断与维修，也降低了成本 了解即可，后续补充
串并联系统的可靠度 这种系统分为三种，一种是串联系统，一种是并联系统、一种是混合系统 失效率：单位时间内失效的元件数占总元件数的比例 串联系统 其中只要有一个子部件不正常，那么就可以不联通（即不正常，失效） 求串联系统可靠性R与失效率λ： $$ \begin{align} &可靠性R=R_1R_2R_3*…*R_n \ &失效率 λ=λ_1+λ_2+λ_3+..λ_n \end{align} $$ 并联系统 其中只要有一个子部件正常，那么就可以联通（即正常，可靠） 求并联系统可靠性R与失效率μ: $$ \begin{align} &R=1-(1-R_1)(1-R_2)…*(1-R_n) \ \end{align} $$ 前提：所有子系统失效率均为λ N模混合系统 与物理中电阻求法相同，分块处理即可 冗余技术 冗余技术是指利用时间冗余，屏蔽干扰信号。 如多次采样输入、判断，以提高输入的可靠性。利用指令冗余，对重要的指令重复写上多个，即使某一个被干扰，程序仍可执行。 利用空间冗余，判别干扰和转换硬件等。下面小编给大家介绍一下“冗余技术是什么意思 冗余技术有哪三种 分为结构冗余、信息冗余、时间冗余 结构冗余 结构冗余是常用的冗余技术，按其工作方式，可分为静态冗余、动态冗余和混合冗余三种。(考过) 静态冗余，静态冗余又称为屏蔽冗余或被动冗余，常用的有三模冗余和多模冗余。静态冗余通过表决和比较来屏蔽系统中出现的错误。例如，三模冗余是对三个功能相同，但由不同的人采用不同的方法开发出的模块的运行结果进行表决，以多数结果作为系统的最终结果。即如果模块中有一个出错，这个错误能够被其他模块的正确结果“屏蔽”。由于无需对错误进行特别的测试，也不必进行模块的切换就能实现容错，故称为静态容错。 动态冗余，动态冗余又称为主动冗余，它是通过故障检测、故障定位及故障恢复等手段达到容错的目的。其主要方式是多重模块待机储备，当系统检测到某工作模块出现错误时，就用一个备用的模块来顶替它并重新运行。各备用模块在其待机时，可与主模块一样工作，也可不工作。前者叫做热备份系统（双重系统），后者叫做冷备份系统（双工系统、双份系统）。在热备份系统中，两套系统同时、同步运行，当联机子系统检测到错误时，退出服务进行检修，而由热备份子系统接替工作，备用模块在待机过程中其失效率为0；处于冷备份的子系统平时停机或者运行与联机系统无关的运算，当联机子系统产生故障时，人工或自动进行切换，使冷备份系统成为联机系统。在运行冷备份时，不能保证从系统断点处精确地连续工作，因为备份机不能取得原来的机器上当前运行的全部数据。 混合冗余，混合冗余技术是将静态冗余和动态冗余结合起来，且取二者之长处。它先使用静态冗余中的故障屏蔽技术，使系统免受某些可以被屏蔽的故障的影响。而对那些无法屏蔽的故障则采用主动冗余中的故障检测、故障定位和故障恢复等技术，并且对系统可以作重新配置。因此，混合冗余的效果要大大优于静态冗余和动态冗余。然而，由于混合冗余既要有静态冗余的屏蔽功能，又要有动态冗余的各种检测和定位等功能，它的附加硬件的开销是相当大的，所以混合冗余的成本很高，仅在对可靠性要求极高的场合中采用。 信息冗余 信息冗余是在实现正常功能所需要的信息外，再添加一些信息，以保证运行结果正确性的方法 检错码和纠错码就是信息冗余的例子 冗余信息的添加方法是按照一组预定的规则进行的。符合添加规则而形成的带有冗余信息的字称为码字，而那些虽带有冗余信息但不符合添加规则的字则称为非码字。当系统出现故障时，可能会将码字变成非码字，于是在译码过程中会将引起非码字的故障检测出来，这就是检错码的基本思想。纠错码则不仅可以将错误检测出来，还能将由故障引起的非码字纠正成正确的码字。 由此可见，信息冗余的主要任务在于研究出一套理想的编码和译码技术来提高信息冗余的效率。编码技术中应用最广泛的是奇偶校验码、海明校验码和循环冗余校验码。 时间冗余 时间冗余是以时间（即降低系统运行速度）为代价以减少硬件冗余和信息冗余的开销来达到提高可靠性的目的 在某些实际应用中，硬件冗余和信息冗余的成本、体积、功耗、重量等开销可能过高，而时间并不是太重要的因素时，可以使用时间冗余。时间冗余的基本概念是重复多次进行相同的计算，或称为重复执行（复执），以达到故障检测的目的。 实现时间冗余的方法很多，但是其基本思想不外乎是对相同的计算任务重复执行多次，然后将每次的运行结果存放起来再进行比较。若每次的结果相同，则认为无故障；若存在不同的结果，则说明检测到了故障。不过，这种方法往往只能检测到瞬时性故障而不宜检测永久性的故障。
层次化存储结构 是在计算机体系结构下存储系统层次结构的排列顺序。 每一层于下一层相比都拥有较高的速度和较低延迟性，以及较小的容量。 由于高速缓存的效率和存储器传输位于层次结构中的不同档次，所以实际上会限制处理的速度，导致中央处理器花费大量的时间等待存储器I/O完成工作。 存储结构分类 补充：主存分为随机存储器(RAM)和只读存储器(ROM) 存储器分类 按存储介质可以分类为半导体存储器、磁表面存储器、光存储器。 按存储器的读写功能可以分类为只读存储器(ROM)、 随机读写存储器(RAM)。 按信息的可保存性可以分类为非永久记忆的存储器、永久记忆性存储器。 按在计算机系统中的作用可以分类为主存储器(内存)、辅助存储器(外存储器)、缓冲存储器。 按功能/容量/速度/所在位置可以分类为寄存器、高速缓存、内存储器、外存储器。 工作性质/存取方式可以分类为随机存取存储器、顺序存取存储器、直接存取存储器、相联存储器。 重点：相联存储器是按内容访问的 Cache 在计算机存储系统体系中，Cache是访问速度最快的层次(若有寄存器，则寄存器最快) 使用Cache改善系统性能的依据是程序的局部性原理(见后文) 命中率的计算 $$ \begin{aligned} & \begin{cases} h:访问命中率\ t_1:Cache周期时间\ t_2:主存周期时间 \ t_3:以读操作为例,使用Cache+主存的系统平均周期 \ h:命中率 \end{cases} \ \ &t_3=h*t_1+(1-h)*t_2 \ &其中(1-h)又被称为失效率(未命中率) \end{aligned} $$ **命中：**要访问的数据恰好在Cache中 **原理：**如果Cache未命中，使用主存 局部性原理 即Cache 的使用场景 局部化原理是层次化存储结构的支撑 可以有效防止抖动 抖动 进程执行过程中发生**缺页(missing page)**有两种可能： 并发进程要求的工作集总和大于内存可提供的可用区。因为缺乏足够空间装入需要的程序和数据，系统无法正常工作。 分配了足够的工作集，但系统无法在开始执行前选择适当的程序段和数据进入内存。这种情况只能依靠执行过程中CPU发现要访问的指令或数据不在内存时，由硬件中断转入中断处理程序，将需要的程序段和数据调入。 当分配的内存小于要求的工作集时，由于内存外存交换频繁，访问外存时间和I/O处理时间大大增加，造成CPU因等待数据空转，使得整个系统性能大大下降，这就造成了系统抖动。 时间局部性 如果一个信息项正在被访问，那么在近期它很可能还会被再次访问 产生时间局部性的典型原因，是程序中存在着大量的循环操作 空间局部性 旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问 即程序在一段时间内所访问的地址，可能集中在一定的范围之内，这是因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式簇聚存储的 顺序局部性 在典型程序中，除转移类指令外，大部分指令是顺序进行的 指令的顺序执行、数组的连续存放等是产生顺序局部性的原因 例题： CPU访问存储器时，被访问数据一般聚集在一个较小的连续存储区域中。若一个存储单元已被访问，则其邻近的存储单元有可能还要被访问，该特性被称为（ ） A.数据局部性 B.指令局部性 C.空间局部性 D.时间局部性 程序的局限性表现在时间局部性和空间局部性 ...
网络规划与设计 四个过程 需求分析 网络规划原则 网络设计和实施原则 层次化网络 需求分析 功能要求 性能要求 运行环境要求 可扩充性和可维护性要求 网络规划原则 实用性 开放性（可扩充） 先进性 网络设计与实施原则 可靠性 安全性 高效性 可扩展性 层次化网络设计 接入层、汇聚层、核心层 最广泛的设计方式： 核心交换机：快速高效的数据分发 汇聚交换机：以过滤为主 接入层：直接接入PC 计算机网络分类 $$ \begin{align} &分类 \begin{cases} 按分布范围 \begin{cases} 局域网(LAN) \ 城域网(MAN) \ 广域网(WAN) \ 因特网 \end{cases} \ 按拓扑结构 \begin{cases} 总线型\ 星型 \ 环形 \ \end{cases} \end{cases} \ \ &\begin{cases} 无线局域网(WLAN) \ \ \ 802.11 \ \ \ Wi-Fi \ 无线城域网(WMAN) \ \ \ 802.16 \ \ \ WiMax \ 无线广域网(WWAN) \ \ \ 3G/4G/5G \ 无线个人网(WPAN) \ \ \ 802.15 \ \ \ Bluetooth \ \end{cases} \end{align} $$ ...
数值表示范围 码制与范围 n为机器字长，减1是减去符号位 定点：小数点在固定位置，不占位数 对于8位定点整数 小数位在最后 补码移码少一个**-0** 规定1000 0000（即-0）是-128 对于8位定点小数 小数点在符号位后面 1(.)111 1111 补码为 1(.)000 0000 下图有误 规定 1000 0000 （即-0）是-1 记住即可
分布式理论 CAP 理论 CAP理论是一个很好的思考框架，它对分布式系统的特性做了高度抽象，比如抽象成了一致性、可用性和分区容错性，并对特性间的冲突（也就是CAP不可能三角）做了总结。 CAP理论对分布式系统的特性做了高度抽象，形成了三个指标： 一致性（Consistency） 可用性（Availability） 分区容错性（Partition Tolerance） 一致性说的是 BASE 理论 分布式共识算法 Paxos 在过去几十年里，它基本上是分布式共识的代名词，因为当前最常用的一批共识算法都是基于它改进的。比如Raft算法、ZAB协议等等。 Raft 不同于Paxos算法直接从分布式一致性问题出发推导出来，Raft算法则是从多副本状态机的角度提出，用于管理多副本状态机的日志复制。Raft实现了和Paxos相同的功能，它将一致性分解为多个子问题：Leader选举（Leader election）、日志同步（Log replication）、安全性（Safety）、日志压缩（Log compaction）、成员变更（Membership change）等。同时，Raft算法使用了更强的假设来减少了需要考虑的状态，使之变的易于理解和实现。 如果要用一句话概括Raft算法，我觉得是这样的：从本质上说，Raft算法是通过一切以领导者为准的方式，实现一系列值的共识和个节点日志的一致。 选举 Raft将系统中的角色分为领导者（Leader）、跟随者（Follower）和候选人（Candidate） 跟随者：相当于普通群众，默默地接收和处理来自领导者的消息，当领导者心跳信息超时的时候，就主动站出来，推荐自己当候选人。 候选人：候选人将向其他节点发送请求投票（RequestVote）RPC消息，通知其他节点来投票，如果赢得了大多数选票，就晋升当领导者。 领导者：蛮不讲理的霸道总裁，一切以我为准，平常的主要工作内容就是3部分，处理写请求、管理日志复制和不断地发送心跳信息。通知其他节点“我是领导者，我还活着，你们现在不要发起新的选举，找个新领导者来替代我。” 首先在初始状态下，集群中所有的节点都是跟随者的状态 Raft算法实现了随机超时时间的特性。也就是说，二秘阁节点等待领导者节点心跳信息的超时时间间隔是随机的。若集群中没有领导者，而节点A的等待超时时间最小（150ms），它会最先因为没有等到领导者的心跳信息，发生超时。 这个时候，节点A就增加自己的任期编号，并推举自己为候选人，先给自己投上一张选票，然后向其他节点发送请求投票RPC消息，请它们推举自己为领导者。 如果其他节点接收到候选人A的请求投票RPC消息，在编号为1的这届任期内，也还没有进行过投票，那么它将把选票投给节点A，并增加自己的任期编号。 如果候选人在选举超时时间内赢得了大多数的选票，那么它就会成为本届任期内新的领导者。 节点A当选领导者后，它将周期性地发送心跳消息，通知其他服务器我是领导者，阻止跟随者发起新的选举。 日志 在Raft算法中，副本数据是以日志的形式存在的，领导者接收到来自客户端写请求后，处理写请求的过程就是一个复制和提交日志项的过程。 如何理解日志 如何复制日志 如何实现日志的一致 安全性 Raft增加了如下两条限制以保证安全性： 拥有最新的已提交的log entry的Follower才有资格成为Leader。 这个保证是在RequestVote RPC中做的，Candidate在发送RequestVote RPC时，要带上自己的最后一条日志的term和log index，其他节点收到消息时，如果发现自己的日志比请求中携带的更新，则拒绝投票。日志比较的原则是，如果本地的最后一条log entry的term更大，则term大的更新，如果term一样大，则log index更大的更新。 Leader只能推进commit index来提交当前term的已经复制到大多数服务器上的日志，旧term日志的提交要等到提交当前term的日志来间接提交（log index 小于 commit index的日志被间接提交）。 之所以要这样，是因为可能会出现已提交的日志又被覆盖的情况： 成员变更 在集群中进行成员变更的最大风险是，可能会同时出现2个领导者。破坏了Raft的领导者的唯一性原则，影响了集群的稳定运行。 在这里，最常用的方法就是单节点变更。 单节点变更，就是通过一次变更一个节点实现成员变更。如果需要变更多个节点，安妮需要执行多次单节点变更。比如将3节点集群扩容为5节点集群，这时你需要执行2次单节点变更，先将3节点集群变更为4节点集群，然后再将4节点集群变更为5节点集群。 问题 节点间如何通讯 在Raft算法中，服务器节点间的沟通联络采用的是远程过程调用（RPC），在领导者选举中，需要用到这样两类的RPC： 请求投票（RequestVote）RPC，是由候选人在选举期间发起，通知各节点进行投票； 日志复制（AppendEntries）RPC，是由领导者发起，用来复制日志和提供心跳消息。 这里，我想强调的是，日志复制RPC只能由领导者发起，这时实现强领导者模型的关键之一。 分布式事务 DTM 官方文档 分布式事务涉及多个节点，是一个典型的分布式系统，与单机系统有非常大的差别。一个分布式系统最多只能同时满足一致性（Consistency）、可用性（Availability）和分区容错性（Partition tolerance）这三项中的两项，这被称为[CAP 理论](#CAP 理论)。 ...
进程管理 进程是程序中一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位，由程序块、进程控制块（PCB）和数据块三部分组成 程序和进程区别：进程是程序一次执行过程。程序是一个静态的概念，而进程是动态的概念。 进程的状态 进程的三态模型 等待又被称为阻塞 进程在就绪时，所有需要的资源都就绪，只需要等待CPU调度 运行状态可以回到就绪，也可以进入等待（阻塞）。当CPU时间片用完，不能再占用资源了，或者有更高优先级的进程调度时，低优先进程会回到就绪；运行完很有可能会等待某些事件（比如I/O），会**进入等待（阻塞）**状态 进入等待时，只有等待的事件发生才会进入就绪状态 五态模型 了解即可，主要考查三态 进程的互斥与同步 进程的互斥：合作进程的间接制约关系，因为需要争夺临界资源（比如图中独木桥) 进程的同步：合作进程之间的直接制约关系 PV操作 一些概念： **临界资源：**诸进程间需要互斥方式对其进行共享的资源，如打印机 临界区：每个进程中访问临界资源的那段代码 **信号量：**一种特殊变量 除了起始与终止进程，PV操作在进程中只能有一次，并且需要成对出现 详情： **P操作：**申请资源的操作 **V操作：**释放资源的操作 **S：**信号量 分析： 对于P操作，申请资源，使信号量-1，如果信号量（代表资源数）不够，那么就阻塞，直到资源足够，被V操作唤起，就继续P操作 对于V操作，释放资源，使信号量+1，如果信号量（资源数）<=0,说明有任务在阻塞，那么就唤起一个阻塞的任务 举个例子： 有两个某类资源，四个进程A、B、C、D要用该类资源，最开始S=2，当A进入，S=1，当B进入S=0，表明该类资源刚好用完， 当C进入时Sem=-1，表明有一个进程被阻塞了，D进入，S=-2。当A用完该类资源时，进行V操作，S=-1，释放该类资源，而这时S<0，表明有进程阻塞在该类资源上，于是唤醒一个。 互斥模型 多个进程共享一台打印机的问题 互斥模型初始信号量为1 P(S); 使用打印机; V(S); 后续代码; 同步模型 单缓冲区生产者、消费者问题 [解析]: s1表示市场容量，初值1；s2表示商品量，初值0 生产者生产一个产品后，P(S1)申请市场位，如果有，送入缓冲，否则阻塞；然后V(S2)释放一个商品量 消费者先P(S2)申请一个产品，如果没有，阻塞，否则取产品；然后V(S1)释放一个市场位，消费产品 来一道例题 答案 : A C [解析]: 碰到这种题，先从简单部分入手。 先看收银员进程，收银员收费，肯定是先等待，再收费，然后唤醒下一个（接待人数+1），所以b1 b2应该是P(S1) V(S2) 再看顾客，当顾客进店，要进行购书，肯定需要先唤醒收银员，收费完毕后，离开（接待人数保持为1）所以是V(S1) P(S2) 前驱图 如图所示的前驱图，每一个圆圈表示一个进程，被箭头指向的必须等待指向者完成 箭头尖是入度 根部是出度 死锁问题 如果一个进程在等待一件不可能的事情，那么会发生进程死锁 如果一个或多个进程死锁，就会导致系统死锁 例： 系统有五个进程: A、 B、 C、 D、 E，这五个进程都需要四个系统资源，系统至少有多少个资源，不可能发生死锁? [解析]：3 3 3 3 4时不可能发生死锁 ...