0 第一代计算机：电子管时代 ② 第二代计算机：晶体管时代 电子管作为开关器件；使用机器语言； 磁鼓存储；输入/输出很慢 晶体管替代电子管；使用高级语言； 主存使用磁芯存储器 硬件的发展 使用半导体存储器 ③ 第三代计算机：小/中规模集成电路(SSI,MSI) 计算机 开始有分时操作系统 计算机的发展历程 ④第四代计算机：大/超大规模集成电路(LSI,VLSI) 计算机 单指令流和单数据流系统SISD 传统冯诺依曼体系结构 产生了微处理器、流水线技 术、高速缓存、虚拟存储器 分类 单指令流和多数据流SIMD 多指令流和多数据流MIMD 多处理机和多计算机系统 早期的冯诺依曼 以运算器为中心 现代计算机 以存储器为中心 存储器由许多存储单元构成、存储单 元中有许多存储器件，每个存储元件 存放一个二进制的0或1 存储单元可存储一串二进制代码、称 为存储字、这一串二进制代码的长度 称为存储字长，一般是1B的整数 计算机的组成 计算机系统概述三 功能部件 应用软件 计算机系统层次结构 系统软件 软件的分类 ① 按地址存取方式 工作方式 ② 按内存访问方式 相联存储器 暂存从主存读出或写入主存的数据 MAR 位数与存储字长相等 MAR的长度与PC的长度相等(地址码长度) 奇存器 暂存从主存读出或写入主存的数据 位数与存储字长相等 对数据进行加工处理、完成算术运算和逻辑运算 功能 算术运算：加、减、乘、除 逻辑运算：与或非、异或、比较、移位 累加器ACC 功能 计算机的指挥中心 ⑤输出设备 应用软件是用户为解决某种应用问题而编制的一些程序，一般是用户或第三方软 件公司为完成具体业务工作而开发和使用的各种软件。 操作系统 语言处理程序 系统软件是用于实现计算机系统管理、调度、监视和服务等功能。 服务性程序 数据库管理系统 计算机网络软件 语言 机器语言 计算机唯一可以识别和执行的语言 汇编语言 经过汇编程序软件的翻译转换为机器语言才可执行 解释程序 逐句翻译、生成中间代码、不生成目标代码 高级语言 编译程序 生成中间代码、生成目标代码 主要区别在于是否生成【目标代码】,两者都课 程生成中间代码 计算机系统的多级层次结构 ② 汇编语言机器 ③ 操作系统机器 ④机器语言机器 ⑤微指令系统 第二级 德 2g 用汇编程序翻译成机器语言程序 用做程序解释机器酯令 由砸件直接执行微指令 机器字长是指参与运算的基本位数，即CPU在同一时间内能进行一次处 机器字长 理的二进制数的位数 机器字长 概念辨析 指令字长 标志着计算精度，也反应寄存器、运算部件和 数据总线的位数。机器字长越多，操作位数也 就越多，计算精度也就越高。 一个指令所包含的二进制位数 数据通路是指数据总线一次能并行传送信息的位数，它影响计算机的有效处理速度 CPU内部数据同类宽带 一般等于机器字长，即内部数据线的位数 等于系统数据总线一次所能并行传送的信息位数，即 CPU与主存、输入输出设备之间进行一次数据传送的 CPU外部数据同类宽带 信息位数，也称为存储字长 计算机的性能指标 三 主存容量 指一个主存储器所能存储信息的最大容量 对于字节编址的计算机，用字节数表示主存容量 对于字编址的计算机，用字数乘以字长表示主存容量 0 吞吐量 指系统在单位时间内处理的请求数。 主要取决于主存的存取周期 指令系统对请求做出的响应时间 响应时间=CPU时间(运行一个程序所花费的时间)+等待时间(用于 磁盘访问、主存储器访问、I/O 操作、操作系统开销等时间)的总和 ③ 主频 又称为时钟频率，表示在CPU内数字脉冲信号振荡的速度。 主频越高、完成指令的一个执行步骤所用的时间就越短，指令执行速度越快 ④ CPU时钟周期 运算速度 是主频的倒数，简称时钟周期，是CPU中最小的时间单位。主 频通常以MHz为单位，1Hz表示1次/秒 ⑥ CPU执行时间 运行一个程序所花费的时间 CPU执行时间=时钟周期数/主频=(指令条数*CPI)/ 主频 ⑦MIPS、MFLOPS、GFLOPS、TFLOPS 每秒执行多少百万条指令 MIPS MIPS = 指令条数/执行时间×10⁶=主频 /CPI 每秒执行百万次浮点运算 MFLOPS MFLOPS = 浮点操作次数/执行时间×106 GFLOPS 每秒执行十亿次浮点运算 TFLOPS 每秒执行万亿次浮点运算 进位计数制及其相互转化：十进制、二进制、八进制和十六进制的相互转化 真值与机器数 真值 机器数 通常用带+、-加上绝对值来表示数值的大小 通常约定二进制数的最高位为符号位，0表示正 好，1表示符号(分为原码、补码和反码) BCD码 用4位二进制来表示十进制，有冗余状态 六种冗余状态，超过9,需要加6(二进制0110)修正 ASCII码 标准ASCII码采用7位二进制数表示控制支付、 大小写字母、数字、和专用符号 字符与字符串 包括输入编码、汉字内码、汉字字形码 汉字编码 汉字国际码=汉字区位码(16进制区位码) +2020 H 数制与编码 汉字机器内码=汉字国标码(16进制区位码)+8080H 概念：校验码是指那些能够发现错误或能够自动纠正错误的数据编码 在原编码上加上一个校验位、检验整个校验码中“1“的个数是奇 数还是偶数 ● 奇偶校验码 奇偶校验 偶校验 整个校验码(有效位+信息位)“1”为奇数个 整个校验码(有效位+信息位)“1”为偶数个 只能发现奇数个错误，不能纠正错误 校验码 数据的表示与运算 三 ● 循环冗余校验码 在K位信息码后面再加上R位检验码、利用模2除法检验编码正确性 按照某种规律分成若干组、每组安排一个检验位进行奇偶性测试，产 生多位检验信息 n位信息位，K位校验位，满足n+k+1<=2^k 纠错能力恒小于校验能力，即校验错的位数大于纠正的错位数 0 算出k ② 写出n+k为H 编号 ③ 分校验组 ④校验位=校验组异或 ④ 写出完整的海明码H Si=Pi 异或检验组，全为0不出错，不全为0,转换为十进制 i, 找Hi取反即可 0 写出多项式，最高次数=信息位补0个数 ② 补0后的信息位与多项式进行模2除法 ③ 将余数替换掉信息位后面的0 接收方收到数据与多项式进行模2除法、 余数为0,没有出错，余数不为0,将所 得余数对应的信息位取反 编码 表示 原码 反码 补码 用机器数的最高位表示数的符号、其余各位表示数的绝对值 正数与原码一样，负数除符号位外，各位是原码的按位取反 正数与原码一样，负数为反码的末位加1 定点数的表示与运算 浮点数的表示与运算 算数逻辑单元 (ALU) 运算 移位运算、原码和补码下的加减乘除运算、溢出概念和判别方法 组成：阶符、阶码、数符、尾数 表示 规格化：规定尾数的最高位必须是一个有效值 IEEE754标准：尾数用源码表示。阶码用移码表示 0 对阶、小阶向大阶看齐 运算(加减运算的步骤) ② 尾数求和 ② 规格化 最基本的加法单元，输入两位加数及低位的进位(三个 输入)、输出和与高位的进位(两个输出) 一位全加器的加法器简单相连、串行进位 由若干个全加器组成，使用先行进位提高加法器的运算速度 功能较强的组合逻辑电路，它能进行多种算术运算和逻辑运算 按在计算机中的作用 主存储器(简称主存或内存)、辅助存储器(简称辅存或外存)、 高速缓冲存储器(Cache) 存储器的分类 按存储介质 按存取方式 半导体存储器、磁表面存储器、磁心存储器、光存器件 随机存取存储器( RAM) 、只读存储器( ROM)、顺序存取存储器 (SAM)、 直接存取存储器 (DAM) CPU Cache 主存 辅存 存储器的层次化结构 半导体存储器 主存与CPU的连接 组成 数据线、地址线、存储矩阵、译码驱动、片选线、读/写电路、读/写控制线 SRAM 原理：利用双稳态触发器来记忆信息，一般用来做高速缓冲存储器 原理：利用存储元电路中栅极电容上的电荷来存储信息，需要定 期刷新，一般用来做大容量主存系统 Flash (闪速存储器) 在不加电时仍可长期保存信息且能进行快速的擦除重写 0 位扩展：将芯片地址、片选和读写控制端相应并联，数据端分别引出。增加存储字长 ② 字扩展：将芯片的地址、数据、读写控制线相应并联、片选译码选择相应的片/片组。增加存储单元个数 3 字扩展位：既增加了存储单元个数，又增加存储字长 磁头：用于读取/写入盘片上的记录面信息，一个记录面对应一个磁头 存储区域 柱面数：表示硬盘每面盘片上有多少个磁道 扇区数：表示每条磁道上有多少个扇区 硬盘存储器 原理：磁头和磁性记录介质相对运动时，通过电磁转 磁记录原理 磁盘存储器 换完成读/写操作 编码方法：按某种方案(规律),把一连串的二进制信息变换成存储介质磁层中的一个磁化翻 转状态的序列，并使读/写控制电路容易、可靠地实现转换 磁记录方式：通常采用调频制(FM) 和改进型调频制(MFM) 的记录方式 指磁盘单位面积上记录的二进制信息量，通常以道密度、 位密度和面密度表示 非格式化容量 存储系统三 外部存储器 磁盘阵列 磁盘的性能指标 格式化容量 指按照某种特定的记录格式所能存储信息的总量 ③ 平均存取时间 寻道时间+旋转延迟时间+传输时间 磁盘存储器在单位时间内向主机传送 ④ 数据传输率 数据的字节数，称为传输率。 磁盘地址 驱动器号 柱面(磁道)号 盘面号 硬盘的主要操作是寻址、读写、写盘。每个操作都对应一个控制字，硬盘工作时，第一 步是取控制字，第二步是执行控制字 RAID(独立冗余磁盘阵列是指将多个独立的物理磁盘组成一个独立的逻辑盘，数据在多个物理盘上分割 交叉存储、并行访问，具有更好的存储性能、可靠性和安全性。 无冗余和无校验的磁盘阵列 ② RAID1 镜像磁盘阵列 RAID1-RAID5的分级 ④ RAID3 位交叉奇偶校验的磁盘阵列 ⑤RAID4 块交叉奇偶校验的磁盘阵列 6 RAID5 无独立校验的奇偶校验磁盘阵列 概念：固态硬盘是一种基于闪存技术的存储器。它与U盘没有本质的差别，只是容量更大，存储性能更好 优点：由半导体存储器构成，没有移动部件，因而随机访问时间比机械磁盘快，没有机械噪声和震动，能耗 低，抗震性好，安全性高 ● 缺点：反复写之后，闪存块会磨损，所以SDD也容易磨损 引入目的：解决CPU与主存速度不匹配的矛盾 ① 直接映射：主存数据块只能装入到Cache中唯一的位置 0 全相联映射：可以把主存数据块装入Cache中的任何位置 ③ 组相联映射：将Cache分为若干组、组间直接映射、组内全相联映射 ① 先进先出 ( FIFO) 算法：选择最早调入的块进行替换 ② 近期最少使用 (LRU) 算法：选择近期内长久未访问的块进行替换 ③ 最不经常使用：将一段时间内被访问次数最少的存储行换出 ③ 随机算法：随机确定被替换Cache块 0 直写法(写直达法):写操作时只把数据同时写入主存和Cache 写回法：写操作时只把数据写入Cache, 而不写回主存，只有当 Cache数据被换出时才写回主存 引入目的：解决主存不足的问题 页式存储器 段式存储器 基本分类 ② 段页式存储器 ③ 快表 (TLB) 以页为基本单位。主存空间和虚拟空间都划为为若干大小相等的页。 以段为基本单位。讲主存按段分配，各段的长度因程序而异。 讲程序按照其逻辑结构划分段，每段再划分为若干页；主存空间也 划分为若干同样大小的页。段式和页式存储的结合。但是要经过两 级查表才能完成地址转换，比较费时 讲当前最常用的信息放在一个小容器的高速存储器中，构成快表。 快表扮演的角色是作为页表的Cache, 对快表的查找和管理全部用 硬件来实现。 ① 页表机制：通过查表获取相关信息 ① 中断机制：要访问页不在内存时产生缺页中断 组成部分 ③ 地址变换机构：把逻辑地址变换成物理地址 ④ 内存和外存：需要一定容量的内存和外存的支持 ① OPT: 选择以后不再用的页 ② FIFO: 选择最先装入的页面 置换算法 ③ LRU: 选择最近最少使用的页 ④ CLOCK: 选择最近未使用的页 ⑤ 改进型CLOCK: 考虑页面修改问题 地址翻译：TBL→页表(TBL不命中)→Cache→主存→CPU 也称为逻辑地址，虚地址对应的空间为虚拟空间或程序空间 虚地址 虚地址=虚页存储+页内字地址 也称物理地址，实地址对应的空间是主存的地址空间 实地址 实地址=主存页号+页内字地址 辅存地址 辅存地址=磁盘号+盘面号+磁道号+扇区号 概念：以页面长度固定、页表简单、调入方便 优缺点 优点 缺点 页面长度固定、页表简单、调入方便 页不是逻辑上独立的实体，处理保护共享不方便 概念 段式虚拟存储器中的段是按程序的逻辑结构划分的，长度各异 虚拟地址划分 虚拟地址=段号+段内地址 段表是程序的逻辑段和在主存存放位 置的对照表 段式存储器 虚拟存储器 虚实地址的变换 段表 记录：某个段的段号，装入位、段起点、段长 变换后的实地址：段起始地址+段内地址 段分界与程序分界对应、具有逻辑独立性 优点 易于编译、管理、修改、保护、共享 容易在段时间留下碎片、造成浪费 概念 把程序按照逻辑结构划分段、每段再划分固定大小的页 虚拟地址划分 虚拟地址=段号+段内页号+页内地址 段页式存储器 段表：根据段号→段表地址、从段表中找到页表 起始地址+段内页号→页表地址 虚实地址变换 页表：在页表中取出实页号+页内地址→实地址 快表存在的原因：因为CPU找通过虚拟地址都要访存一次，因为表就在主存中， 找到表再通过地址变换得到实地址，再根据实地址访存才能得到想要的数据 快表TLB: 将经常访问的页放在高速缓存存储器中，找到表中再通过地址变换得 到实地址，再根据实地址访存才能得到想要的数据 快表TLB 慢表Page: 在主存中的表 注：查找时，快表和慢表是一起查的，若快表找到了、慢表查找停止、快表没 找到就继续在慢表查，没查到则将执行页面替换策略 ① 都有映射地址、替换算法、更新策略 相同点 ② 都根据程序访问的局部特性原理 ③ 都为了提高系统性能 虚拟存储器与Cache的比较 不同点 ① Cache解决系统速度、虚拟存储器解决主存容量问题 Cache由硬件实现，对所有程序员透明，虚拟存储器 ② 是OS和硬件共同实现，系统程序元不透明、应用程 序员透明 ③ 虚拟存储器不命中对系统性能影响更大 ④ Cache能与CPU直接通信、辅存不能 寻址方式 有效地址 根据指令中给出的地址码字段寻找有效地址的方式。指令中地址码给出的地址称 为形式地址(用字母A表示)。这个地址有可能不能直接用来访问主存 指能够直接访问主存的地址(用字母EA表示)。形 式地址经过某种寻址方式的转换才能变为有效地址。 指令寻址方式 寻址方式 指令系统 顺序寻址 跳跃寻址 立即寻址 直接寻址 隐含寻址 间接寻址 通过程序计数器PC加1,自动形成下一条指令的地址 通过转移指令直接或间接给出下一条指令的地址 操作数本身设在指令内。给出的不是操作数地址，而是操作数本身 指令中地址字段给出的地址A的操作数就是有效地址，即形式地址 等于操作数的真实地址： EA=A 操作数地址不明显给出，而是隐含在操作码中或某个寄存器中 直接给出操作数有效地址所在的存储单元的地址 大 数据寻址方式 寄存器寻址 寄存器间接寻址 直接给出操作数所在的寄存器的编号 给出的操作数放在主存单元地址的某个寄存器编号，该寄存器编号中的地 址才是有效地址。 基址寻址 将基址寄存器中的内容加上指令格式中的形式地址才是有效地址 偏移寻址 变址寻址 将变址寄存器中的内容加上指令格式中的形式地址才是有效地址 相对寻址 把程序计数器PC的内容加上指令格式中的形式地址才是有效地址 堆栈寻址 从规定的栈中取出操作数 中断处理 对计算机运行过程中出现的异常情况和特殊请求进行处理 CPU的基本结构和功能 基本结构 运算器 控制器 是对信息进行处理和运算的部件。它的功能是完成算数运算和 逻辑运算，并将运算的中间结果暂存在运算器中 是整个计算机的指挥中心。它的功能是控制、指挥程序和数据 的输入、运行以及处理运算结果 指令周期 指令执行过程 执行方案 取指周期 间址周期 执行周期 中断周期 单指令周期 多指令周期 根据PC中的内容从指定地址读出指令代码并放在IR中 取操作数的有效地址(并不是所有指令的执行过程中都会有间址周期) 根据指令字的操作码和操作数执行相应的操作 处理中断请求 对所有的指令都选用相同的执行时间来完成 指令串行执行 对不同类的指令选用不同的执行步骤来完成 指令流水线 指令之间可以并执行的方案 指令并行执行 将所有寄存器的输入端和输出端都连接到一条或多条公 CPU内部总线 共的通路上，将多个部件共享，可以存在一条或多条 数据通路的功能和基本结构 专用数据通路总线 根据指令执行过程的数据和地址的流动安排连接的线路 硬布线控制器 由复杂的组合逻辑门电路和一些触发器构成，由硬件给出控制信号 概念 把每条机器指令设计成一个微程序，由微指令给出控制信号 0 控制存储器(核心部件) 控制器的功能和工作原理 组成 ② 微指令寄存器 ③ 微地址寄存器 ④微指令形成部件 微程序控制器 编码方式 3 字段间接编码 微指令的操作控制字段中每一位代表一个微命令 将微指令的操作控制字段分成若干段，把互 斥的微指令放在一个字段中编码，把相容性 微命令放在不同字段中编码 一个字段的某些微命令需要另外一个字段的 某些微命令来解释 ④混合编码 把直接编码和字段编码(直接或间接)混合使用 格式 操作控制字段 顺序控制字段 各位操作控制信号的集合 包括判断测试字段和后继微地址字段 中央处理器 异常和中断机制 故障中断是由硬连线出现异常引起的，如存储器校验错误、总线错误等 异常是由CPU内部产生的意外事件，分为硬故障中断和程序性异常 程序性异常中断也称软件中断，指在CPU内部执行指令而引起的异常事件 故障异常和自陷异常属于程序性异常(软件中断) 在执行指令的过程中发生了使计算机无法继续执行的硬件故障，如控制器出错等，程序将无法执行，只能终 止，此时调出中断服务程序来重启系统。 ③终止 终止异常和外中断属于硬件中断 可屏蔽中断 中断的分类 指通过可屏蔽中断请求线INTR向CPU发出的中断请求。CPU可以通过在中断控制器中设置相应的屏蔽 字来屏蔽它或不屏蔽它，被屏蔽的中断请求将不被送到CPU。 指通过专门的不可屏蔽中断请求线NMI向CPU发出的中断请求，通常是非常紧急的硬件故障，如电源 掉电等。这类中断请求信号不可被屏蔽，以让CPU快速处理这类紧急事件。 中断和异常的两个重要不同点 缺页或溢出等异常事件是由特定指令在执行过程中产生的，而中断不和任何指令关联，也不阻止任何指令的完成 异常的检测由CPU自身完成，不必通过外部的信号通知CPU。对于中断，CPU必须通过中断请求获取中断源的信息， 才能知道哪种设备发生了何种中断 SISD是传统的串行计算机结构，这种计算机通常仅包含一个处理器和一个存储器，处理器在一段时间内仅执 单指令流单数据流(SISD)结构 行一条指令，按指令流规定的顺序串行执行指令流中的若干条指令。 概念：把一个重复的过程分解为若干子过程，每个子过程与其他子过程并行执行 分类 部件功能级流水 按使用级别分 处理机级流水 处理机间级流水 单功能流水 按完成功能分 多功能流水 动态流水 按连接方式分 静态流水 线性级流水 按有无反馈信号分 非线性级流水 关注公众号【考研小舟】 免费考研资料&无水印PDF 黑白&彩印都是5分/页，满4.9全国包邮 下单备注：考研小舟，送草稿纸 影响因索 性能指标 指令流水线 结构相关 数据相关 控制相关 吞吐率 加速比 效率 又称资源冲突，由多条指令同一时刻争用同一资源而形成的冲突 又称资源冒险，必须等到前一条指令执行完成后才能执行后一条指令的情况 又称控制冒险，遇到转移指令和改变PC情况而形成的断流 指定的单位时间指令流水的完成任务量 完成同样一批任务，顺序执行时间与流水线执行时间之比 流水线中各功能的利用率 概念：在指令流水线中，会遇到使得 流水线无法正确执行后续指令而引起 的流水线阻塞或停顿，这种现象称为 流水线冒险 由于多条指令在同一时刻竞争同一资 源而形成的冲突，称为资源冲突，也 是由于硬件资源竞争造成的冲突 提高转移方向的猜准率 超标量技术：在每个时钟周期内可以同时并发多条独立指令 超流水线技术：在一个时钟周期内再分段，在一个时钟周期内一个功能部件使用多次 由编译程序挖掘出指令间潜在的并行性，将多条能并行操作的指 令组合成一条具有多个操作码字段的超长指令 概念：总线是连接多个部件的信息传输线，具有各部共享的传输介质 并行传输总线 按照数据传送方式 串行传输总线 ● 片内总线 用来连接芯片内部的各个部件 ● 系统总线 用于连接计算机系统内部各功能部件 用于连接计算机系统之间或计算机系统与其他系统 一次总线操作所需要时间 总线上各种操作的频率，是总线周期的倒数 通常指总线数据的根数，也就是总线上能同时传输数据的位数 总线的数据传输速率，及单位时间内总线上传输数据的位数。 总线带宽=总线宽度×总线频率 链式查询 根据线的链接顺序依次查询每个部件有无请求 计数器定时查询 对每个设备进行编号，由计数器依次查询 独立请求方式 在总线控制器中排队，按照一定规则响应某个请求 仲裁 不要中央仲裁器，每个潜在的主模块都有自己的仲裁器，多个总线仲裁器竞争使用总线 总线的主模块向总线提出使用请求 通过总线发出本次要访问的从模块的地址及有关的命令 主模块和从模块进行数据交换，可单向或双向进行数据传送 主模块的有关信息从系统总线上擦除，让出总线使用权 ① 同步定时方式 系统采用一个统一的时钟信号来协调发送和接收双方的传递的定时关系 没有统一的时钟，也没有固定的时间间隔，完全依靠相互制约的“握 概念 手”信号来实现定时通信 ② 异步定时方式 分类 不互锁 半互锁 全互锁 主模块的请求信号和从模块的问答信号没有相互制约 主模块的请求信号和从模块的回答信号有简单的制约关系 主模块的请求信号和从模块的问答信号有完全的制约关系 I/O系统基本概念 概念：输入/输出是以主机为中心而言的，输入/输出系统解决的 主要问题是对各种形式的信息进行输入和输出的控制 控制方式：程序查询方式、程序中断方式、DMA方式、通道方式 输入设备 输出设备 外部设备 外部存储器 鼠标、键盘等 打印机、显示器等 硬盘存储器、磁盘阵列、光盘存储器等 实现主机和外设的通信控制 进行地址译码和设备选择 主要功能 实现数据缓冲 信号格式的转换 传送控制命令和状态信息 按数据传送方式 串行接口 并行接口 I/O接口 输入/输出(I/O)系统 类型 可编程接口 按功能选择的灵活性 不可编程接口 通用接口 专用接口 程序结构 DMA接口 编址 统一编址 独立编址 把I/O端口当作存储器的单元进行地址分配，不需要CPU设 置专门的VO指令，用统一的访存指令就可以访问I/O 端口 IVO端口地址与存储器地址无关，需要CPU设置专门的I/O 指令访问VO端口 程序查询 程序中断 I/O方式 由程序不断的查询外设的状态，直到外设设备就绪(在CPU的控制下进行) 概念：计算机在执行现行程序的过程中，出现某些急需处理的异常情况和特殊情 况，CPU暂时中止现行程序，转而去对这些异常处理情况和特殊情况进行处理， 处理完毕后，CPU将自动返回原来的程序继续执行 中断请求：中断源向CPU发出中断信号 中断判优：判断多个中断源的优先级 0 有中断源提出中断请求 ◎ 响应条件 ② CPU允许中断并且开中断 ③ 一条指令执行完毕且没有更紧迫的任务 中断隐指令：保存断点；引出终端服务程序；完成关中断 中断向量 查询中断服务程序的入口地址 中断处理 执行中断服务程序、最好恢复现场、中断返回 概念 当CPU处理中断时，又有更高优先级的中断请求 中断服务程序中提前设置开中断指令 条件 优先级别高的中断源有权中断优先级别低的中断源 特点：一种完全由硬件进行成组信息传送的控 制方式 概念 负责协调软硬件等计算机资源的工作，为上层用户、应用程序提供简单易用的服务的软件系统 处理机管理 一 进程控制/进程同步/进程通信/进程调度 存储器管理 一 内存分配/内存保护/地址映射/内存扩充 资源的管理者 文件管理 一 文件存储空间管理/目录管理/文件读写管理/文件保护 设备管理 一 缓冲管理/设备分配/设备处理 允许用户直接使用 联机命令接口 用户说一句，系统说一句(如终端输入命令) 用户接口 脱机命令接口 用户说一句，系统说一堆(如.bat 文件批处理) 向用户提供服务 图形用户接口 用户通过程序间接使用 程序接口 由一组系统调用组成 对硬件机器的扩展 扩充机器 并发 一 宏观上多个程序同时运行，微观上单处理机中程序分时交替进行 对摄像头设备的共享使用 共享 对硬盘资源的共享使用 通过某种技术将一个物理实体变成若干个逻辑上的对应物 操作系统 特征 空分复用技术 虚拟 利用处理机的空闲时间运行其他程序 虚拟处理机技术、虚拟设备技术 异步 进程以不可预知的速度向前推进 手工操作阶段 缺点：人机速度矛盾 引入脱机输入输出技术，监督程序控制流程 单道批处理系统 优点：缓解人机速度矛盾 缺点：资源利用率低，cpu与I/O 串行操作 操作系统开始出现 多道批处理系统 多道程序并发执行，资源利用率高 发展与分类 平均周转时间长，不提供人机交互功能 优点：提供人机交互功能 分时操作系统 缺点：不能优先处理紧急任务 网络操作系统、分布式操作系统、个人计算机操作系统 非特权指令一 如运算指令 两种指令 特权指令一 如I/O指令，内存清零指令 用户态 两种处理器状态 核心态 内核程序 两种程序 应用程序 进程管理 对系统进行管理的功能 存储器管理 设备管理 时钟管理一 实现计时功能 系统内核 负责实现中断机制 特殊的程序，初一操作系统的最底层，最接近硬件 原语 具有原子性，运行只能一气呵成不能终端 运行时间较短，调用频繁 将操作系统的主要功能模块都作为系统内核 大内核 优点：高性能； 缺点：内核代码庞大，结构混乱，难以维护 与硬件处理紧密相关的部分 足够小的内核 一些较基本的功能 客户与服务器之间的通信 将操作系统的绝大部分功能放在微内核外面的一组服务器(进程)中实现 基于客户/服务器模式 如进程/线程管理服务器、虚拟存储服务器、I/O设备管理服务器 基本概念 运行在用户态、客户与服务器之间借助微内核提供的消息传递机制实现消息交互 机制是指实现某一功能的具体执行机构，处于系统底层 应用“机制与策略分离”原理 策略是在机制的基础上借助某些参数和算法实现功能优化，处于系统高层 “抽象”和“屏蔽”原则控制系统的复杂性 采用面向对象技术 “对象”“封装”“继承”确保操作系统的正确性、可靠性、易扩展性、易修改性 将指定优先级进程/线程从所在队列中取出投入运行，属于调度功能的机制部分，放入微内核中 进程/线程管理 对用户进程/线程分类及优先级确认的方式或原则属于策略问题，放入微内核的进程/线程管理服务器中 配置最基本的低级存储器管理机制 低级存储器管理 如用于实现将用户空间的逻辑地址变换为内存空间的物理地址的页表机制和地址变换机制 捕获所发生的中断和陷入事件，进行现场保护，识别中断和陷入的类型 中断和陷入处理 将有关事件转换成消息后发送给相关的服务器，调用相应的处理程序来进行后期处理 优点一 提高了系统的可扩展性，增强了系统的可靠性，可移植性强，提供了对分布式系统的支持，融入了面向对象技术 问题一 客户和服务器、服务器和服务器之间的通信都需经过微内核，上下文切换频繁 定义 进程实体的运行过程，是系统进行资源分配和调度的一个独立单位 动态性 一 进程是程序的一次执行过程，是动态地产生、变化和消亡的 并发性 一 内存中有多个进程实体，各进程可并发执行 特征 独立性 — 独立运行/获得资源/接受调度的基本单位 ④ 异步性 — 各进程按各自独立的不可预知的速度向前推进，可能导致运行结果的不确定性 结构性 一 每个进程都配置一个PCB对其进行描述，结构上看由程序段、数据段和PCB组成 进程描述信息 一 进程标识符PID/ 用户标识符UID 程序段 存放要执行的代码 数据段 存放程序运行过程中处理的各种资源 按照进程状态将PCB分为多个队列 链接方式 操作系统持有指向各个队列的指针 进程的组织方式 按照进程状态建立几张索引表 索引方式 操作系统持有指向各索引表的指针 运行态 一 cpu√ 其他所需资源 √ 就绪态 一 cpu X 其他所需资源 √ 状态 阻塞态/等待态 一 cpu X其他所需资源√ 创建态 一 操作系统为新进程分配资源、创建PCB 结束态 一 操作系统回收进程资源、撤销PCB 进程控制 进程的创建/终止/阻塞/唤醒/切换 互斥地访问共享空间 共享存储 ①基于数据结构的共享(低级通信) — 如共享空间中放置长度为10的数组，速度慢 ②基于存储区的共享(高级通信) 一 进程控制数据形式/存放位置，速度快 传递结构化消息(消息头/消息体),系统提供"发送/接受原语" 消息传递 ①直接通信方式 一 消息直接挂到接收方的消息队列里 进程的通信 ②间接通信方式 一 消息先发送到中间体(信箱) 各进程互斥地访问管道 设置一个特殊的共享文件(管道),也就是缓冲区只 管道通信 能实现半双工通信，实现双向通信要建立两个管道写满 时不能再写，读空时不能再读 没写满不能读，没读空不能写 "轻量级进程" 传统机制中，进程是资源分配/调度的基本单位 资源分配/调度 引入线程后，进程是资源分配的基本单位，线程是处理机调度的基本单位 传统机制中，只有进程间并发 并发性 引入线程后，各线程间也并发，提高了并发度 传统的进程并发，需要切换进程的运行环境，系统开销很大 系统开销 线程间并发，同一进程的线程切换不会引起进程切换，系统开销小 线程几乎不拥有系统资源 多cpu计算机中，各个线程可以占用不同的cpu 每个线程都有一个线程ID、线程控制块(TCB) 线程也有就绪/阻塞/运行三种基本状态 同一进程中的不同线程间共享进程的资源 用户级线程 一 线程的实现方式 从操作系统角度看的线程(内核级线程才是处理机分配的单位) 缺点 一个线程阻塞会导致整个进程都被阻塞(并发度低) 各个线程可分配到多核处理机 线程管理开销大 集二者之长 cpu利用率=忙碌的时间/总时间 CPU利用率 系统吞吐量=总作业数/总时间 系统吞吐量 周转时间=完成时间-提交时间 平均周转时间=各作业周转时间之后/作业数 带权周转时间=周转时间/运行时间 平均带权周转时间=个作业带权周转时间之和/作业数 进程/作业等待被服务的时间之和 等待时间 从用户提交首次产生响应所用的时间 响应时间 优先级调度 优先级高优先 抢 占 式/ 非适用于实时操作 抢占式都有 系统 非剥夺式(非抢占式) 一 只能由当前运行的进程主动放弃cpu 剥夺式(抢占式) 一 可由操作系统剥夺当前的CPU使用权 多级反馈队 列调度算法 各级队列优先 机从高到低 抢占式 灵活调整对各类 进程的偏好程度 / 对临界资源的访问，需要互斥的进行。同一时间段内只能允许一个进程访问该资源 检查是否可进入临界区，若可进入，则需*上锁” 制约关系 互斥 四个部分 退出区 其余代码部分 临界区互斥 信号量机制 临界区空闲时，应允许一个进程访问 进不了临界区的进程，要释放处理机，防止忙等 算法思想 进入区只”检查“不”上锁”,退出区把临界区的 单标志法 使用权转交给另一个进程，即每个进程进入临 界区的权限只能被另一个进程赋予 双标志先检查 进入区先“检查“后”上锁”,退出区”解锁” 双标志后检查 先"上锁”后”检查',退出区“解锁” 可能导致饥饿 皮特森算法 进入区“主动争取一主动谦让一检查对方 是否想进一己方是否谦让 使用“开/关中断”指令实现 中断屏蔽方法 优点：简单高效 缺点：只适用于单处理机。只适用于操作系统内核进程 硬件 优点：实现简单；适用于多处理机环境 ⑥ TestAndset (TS指令/TSL指令) 缺点：不满足“让权等待” (XCHG指令)逻辑上同TSL 利用PV操作实现互斥 以上7种方法都无法实现"让权等待" 用一个整数型变量作为信号量，数值表示某种资源数 整型信号量与普通整型变量的区别：对信号量只能执行初始化、P、V三种操作 整型信号量存在的问题：不满足“让权等待“原则 S.value表示某种资源数，S.L指向该等待队列 r P操作中，一定是先S.value-, 之后可能需要执行block原语 记录型信号量- V操作中，一定是先S.value++, 之后可能需要执行wakeup原语 实现系统资源的"申请“和”释放 分析问题，确定临界区 ②设置互斥信号量，初始值为1 实现进程互斥- 临界区之前对信号量执行P操 作 ④临界区之后对信号量执行V操作 分析问题，找出“一前一后”的同步关系 ②设置同步信号量，初始值为0 实现进程同步 在"前操作“之后执行V操作 ④在”后操作“之前执行P操作 分析问题，画出前驱图，每一对前驱关系都看成一个同步问题 为每一对前驱关系设置同步信号量，初值为0 实现进程的前驱关系- 在每个"前操作“之后执行V操作 ④ 在每个"后操作"之前执行P操作 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系 PV 操作题目的解题思路 整理思路。根据各进程的操作流程确定P、V操作的大致顺序 设置信号量。根据题目条件确定信号量初值(互斥信号量一般为1,同步信号量的初值对应资源的初值) 生产者消费者问题 多生产者-多消费者问题 经典问题 吸烟者向题 哲学家进餐问题 引入管程原因 解决信号量机制编程麻烦、易出错的问题 共享数据结构 对数据结构初始化的语句 一组用来访问数据结构的过程(函数) 管 理 各外部进程/线程只能通过管程提供的特定"入口'才能访问共享数据 基本特征 每次仅允许一个进程在管程内执行某个内部进程 各进程必须互斥访问管程的特性是由编译器实现的 可在管程中设置条件变量及等待/唤醒操作以解决同步问题 产生原因 概念区别 必要条件 进程管理(死锁) 处理策略 非剥夺资源的竞争和进程的不恰当推进顺序 发生死锁的进程一定处于阻塞态 死锁 至少有两个或两个以上的进程同时发生死锁 进程可能是阻塞态(长期得不到I/O设备)/就绪态(长期得不到处理机) 饥饿 可能只有一个进程发生饥饿 由代码的逻辑错误导致 死循环 可能只有一个进程发生死循环 将互斥使用的资源改造为允许共享使用(如SPOOLing技术) 缺点：可行性低，很多时候无法破坏互斥条件 ① 申请的资源得不到满足时立即释放拥有的所有资源 申请的资源被占用时，由操作系统协助剥夺(优先级) 缺点：实现复杂：系统开销大：可能导致饥饿 采用静态分配法，运行前分配好所有资源，之后一直保持 缺点：资源利用率低：可能导致饥饿 采用顺序资源分配法，必须按编号从小到大的顺序申请资源 缺点：不方便增加新设备：导致资源浪费：用户编程麻烦 最大需求矩阵：Max[] 分配矩阵：Allocation[] 数据结构 需求矩阵：Need[]=Max-Allocation 可用资源：Available[] 申请资源：Request[] ① 检 查Request 是否超过Need 检查Avalable是否满足Request 试探分配，更改数据结构 算法步骤 检查当前Available是否满足某个进程的Need 可以则加入安全序列并把该进程所有资源回收 ⑤重复上述步骤，看最终能否让所有进程加入安全序列 进程结点/资源结点 数据结构 进程结点→资源结点：请求边 资源结点→进程结点：分配边 检测死锁 资源分配图 找出既不阻塞又不是孤点的进程Pi, 消去所有请求边和分配边，使之成为孤立的结点 算法步骤 重复上述步骤，若能消去所有边，则称该图是可完全简化的； 否则还连着边的进程就是死锁进程 指令工作的原理 一 操作码+若干参数(可能包含地址参数) 逻辑地址(相对地址)vs物理地址(绝对地址) 编辑 编译 静态链接 一 装入前链接成一个完整模块 链接 装入时动态链接 一 运行前边装入边链接 从写程序到程序运行 运行时动态链接 一 运行时需要目标模块时才装入并链接 将装入模块装入内存，装入后形成物理地址 绝对装入一 装入 ② 静态重定位 — 动态重定位 一 只支持单道程序，内存分为系统区和用户区，用户程序放在用户区 单一连接分配 无外部碎片，有内部碎片 可采用覆盖技术扩充内存，不一定需要采取内存保护 支持多道程序，内存用户空间分为若干个固定大小的分区，每个分区只能装一道作业无 无外部碎片，有内部碎片 固定分区分配 分区说明表：分区号、大小、起始地址、状态 分区大小相等 两种分区方式 分区大小不等 支持多道程序，在进程装入内存时，根据进程的大小动态地建立分区 无内部碎片，有外部碎片(由"紧凑"技术解决) 空闲分区表：分区号、分区大小、起始地址、状态 两种数据结构 空闲分区链 回收区之后有相邻的空闲分区 回收区之前有相邻的空闲分区 回收内存分区 内存空间的分配与回收 连续分配管理方式 算法 首次适应 动态分区分配 回收区前后有相邻的空闲分区 回收区前后无相邻的空闲分区 算法思想 从头到尾 找合适的分区 分区排列顺序 优点 地址递增 综合性能最好，算法开销 小，回收分区后一般无需对 空闲分区队列重新排序 缺点 优先使用更小的分区 容量递增 会有更多的大分区被保留下来， 满足大进程的需求 最佳适应 产生小的难以利用的碎片；法 开销大回收分区后可能需要 对空闲分区队列重新排序 最坏适应 优先使用更大的分区 容量递减 减少难以利用的小碎片 销 闲分 新排序 大分区容易被 用完，不利于大 进程；算法开 大，需对空 区队列重 邻近适应 从上次查找结束位置开始 地址递增 (可排列成循环链表) 无需每次从低地址的小分 区始检索；算法开销小 会使高地址的大分区 被用完 思想 — 将进程分页，各个页面离散的放到各个内存块中 "页框、页帧、内存块、物理块"vs" 页、页面" "页框号、页帧号、内存块号、物理块号"vs” 页号、页面号” 概念 一个进程对应一张页表，进程的每一页对应一个页表项 页表 每个页表项由"页号"和"块号“组成 每个页表项的长度是相同的，页号是"隐含"的 存放页表起始地址 页表寄存器 存放页表长度 根据逻辑地址算出逻辑页号、页内偏移量 页号的合法性检查(与页表长度对比) 地址变换过程 ③ 若页号合法，再根据页表起始地址、页号找到对应页表项(第一次访存：查页表) 基本地址变换结构 ④ 根据页表项中记录的内存块号、页内偏移量得到最终的物理地址 访问物理内对应的内存单元(第二次访存：访问目标内存单元) 页式管理中地址是一维的 几个细节 实际应用中，通常使一个页框恰好能放入整数个页表项 为了方便找到页表项，页表一般是放在连续的内存块中 时间局部性：执行的某条指令可能再次被执行，访问过的数据可能再次被访问 局部性原理 空间局部性：访问的某个存储单元附近的存储单元可能被访问 快表(TLB) 一 联想寄存器，访问速度比内存快很多的高速缓冲存储器，存放当前访问的若干页表项 ① 根据逻辑地址算出逻辑页号、页内偏移量 页号的合法性检查(与页表长度对比) 具有快表的地址变换结构 查快表，若命中即可知道页面存放的内存块号，可直接进行⑤,未命中则进行④ 地址变换过程 ④ 查页表，找到页面存放的内存块号，并且将页表项复制到快表中 根据内存块号与页内偏移量得到物理地址 ⑥访问目标内存单元 快表命中只需一次访存，未命中需两次访存 所有页表必须连续存放，页表过大时需要很大的连续空间 单级页表的问题 在一段时间内并非所有页面都用得到，因此没必要让整个页表常驻内存将 长的页表再分页 两级页表 逻辑地址结构(一级页号，二级页号，页内偏移量) 页目录表/外层页表/顶级页表 两级页表 按照地址结构将逻辑地址拆分成三部分 从PCB中读出页目录表始址，根据一级页号查页目录表，找到下一级页表在内存中的存放位置 地址变换 根据二级页号查表，找到最终想访问的内存块号 结合页内偏移量得到物理地址 多级页表中，各级页表大小不能超过一个页面。若两级页表不够，可以分更多级 几个细节 多级页表的访存次数(假设没有快表机构)- N级页表访问一个逻辑地址需要N+1 次访存 将地址空间按照程序自身的逻辑关系划分成若干个段，每段从0开始编址 分段 每个段在内存中占据连续空间，但各段之间可以不相邻 逻辑地址结构：(段号，段内地址) 记录逻辑段到实际存储地址的映射关系 段表 每个段表对应一个段表项，各段表项长度相同，由段号(隐含)、段长、基址组成 由逻辑地址得到段号、段内地址 段号与段表寄存器中的段长度比较，检查是否越界 基本分段存储管理 由段表始址、段号找到对应段表项(第一次访存) 地址变换 根据段表中记录的段长，检查段内地址是否越界 根据基址与段内偏移量得到物理地址 访问目标单元(第二次访存) 分页对用户不可见，分段对用户可见 分页的地址空间是一维的，分段的地址空间是二维的 分段VS分页 分段更容易实现信息的共享和保护(纯代码/可重入代码可以共享) 分页(单级页表)分段访问一个逻辑地址都需要两次访存，分段存储中也可以引入快表机构将地址 覆盖技术 内存空间的扩充(上) 交换技术 内存管理 存放最活跃的程序段 一个固定区 固定区中的程序段在运行过程中不会调入调出 若干覆盖区 —— 不可能被同时访问的程序段可共享一个覆盖区 必须由程序员声明覆盖结构，操作系统完成自动覆盖 缺点：对用户不透明，增加了用户编程负担 在同一个程序或进程中 内存紧张时，换出某些进程以腾出内存空间，再换入某些进程 磁盘分为文件去和对换去，换出的进程放在对换区 磁盘分为文件去和对换去，换出的进程放在对换区 操作系统负责逻辑地址到物理地址的转换 绝对装入 地址转换 三种方式 静态重新定位 动态重定位 保证进程在自己的内存空间运行，不会越界访问 在CPU中设置一堆上、下限寄存器，存放进程的上、下限地址 两种方式 采用重定位寄存器(基址寄存器)和界地址寄存器(限长寄存器)进行越界检查 传统存储管理方式特征 一次性：作业数据必须一次全部调入内存 驻留性：作业数据在整个运行期间都会常驻内存 时间局部性：现在访问的指令数据在不久后很可能被再次访问 局部性原理 空间局部性：现在访问的内存单元周围的内存空间很可能在不久后被再次访问高 速缓存技术：使用频繁的数据放到更高速的存储器中 定 义 一 程序不需全部装入即可运行，运行时根据需要动态调入数据，若内存不够，则换出一些数据 基本概念 多次性：无需在作业运行时一次性全部装入内存，允许被分成多次调入内存 虚拟存储器 特征 对换性：无需在作业运行时一直常驻内存，而是允许在作业运行过程中，将作业换入换出虚 拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量远大于实际容量 请求分页存储管理 虚拟内存技术实现 请求分段存储管理 请求段页式存储管理 虚拟存储技术 请求分页存储管理 在基本分页的基础上增加了几个表项 状态位：表示页面是否已在内存 页表机制 访问字段：记录最近被访问过几次，或记录上次访问的实践，供置换算法选择换出页面时参考 修改位：表示页面调入内存后是否被修改过，只有修改过的页面才需要在置换时写回外存 外存地址：页面在外存中存放的位置 找到页表项后检查页面是否已在内存，若没在内存，产生缺页中断缺 页中断处理中，需要将目标页面调入内存，有必要时还要换出页面 缺页中断机构 缺页中断属于内中断中的“故障”,可能被系统修复 一条指令在执行过程中可能产生多次缺页中断 找到页表项时需检查页面是否在内存中 若页面不在内存中，需要请求调页 地址变换机构 若内存空间不够，需要换出页面 页面调入内存后，需要修改相应页表项 算 法 算法规则 优缺点 最佳置换算法(OPT) — 优先淘汰最长时间内不会再被访问的页面 — 缺页率最小，性能最好；但无法实现 先进先出置换算法(FIFO) — 优先淘汰最先进入内存的页面 一 实现简单；但性能很差。可能出现Belady 异常 最近最久未使用置换算法(LRU — 优先淘汰最近最久没访问的页面 一 性能很好；但需要硬件支持，算法开销大 页面置换算法 时钟置换算法(CLOCK) [最近未用算法(NRU)] 第一轮淘汰(访问位=0)的页面，并将 扫描过的访问位改为0。若第一轮未选 — 中则进行第二轮扫描。最多进行两轮扫描。 实现简单，算法开销小；但未考虑页面是否被修改过 改进型时钟置换算法 用(访问位，修改位)形式描述。 第一轮：淘汰(0,0);第二轮：淘汰(0,1), 并将扫描过的页面访问位都置为0; 第三轮：淘汰(0,0);第四轮：淘汰(0,1)。 最多进行四轮扫描。 — 算法开销较小，性能也不错 驻留集 一 指请求分页存储管理中给进程分配的内存块的集合 工作集 一 在某段时间间隔里，进程实际访问页面的集合。驻留集大小一般不能小于工作集大小固 定分配vs可变分配：区别在于进程运行期间驻留集大小是否可变 局部置换vs全局置换：区别在于发生缺页时是否只能从进程自己的页面中选择一个换出 页面分配、置换策略 固定分配局部置换 进程运行前分配一定数量物理块，缺页时只能换出进程自己的某一页 可变分配全局置换 只要缺页就分配新物理块，可能来自空闲物理块，也可能需换出别的进程页面 可变分配局部置换 频繁缺页的进程，多分配一些物理块；缺页率很低的进程，回收一些物理块 页面分配策略 预调页策略 一般用于进程运行前 何时调页 请求调页策略 进程运行时发现缺页再调页 对换区-采用连续存储方式，速度快；文件区-采用离散存储方式，速度慢 对换区足够大：运行时将数据从文件区复制到对换区，之后所有页面的调入调出都是在内存与对换区之间进行 何处调页 对换区不够大：不会修改的数据每次都从文件区调入；会修改的数据调出到对换区，需要时再从对换区调入 UNIX方式：第一次使用的页面都从文件区调入；调出的页面都写回对换区，再次使用时从对换区调入 抖动(颠簸)现象 一 页面频繁换入换出，主要原因是分配给进程的物理块不够 文件定义 一组有意义的信息的集合 文件名(同一目录下不允许有重名文件)、标识符(唯一，对用户无可读性) 文件属性 类型、位置、大小、保护、时间、日期和用户标识 文件的基本操作 文件管理 文件的逻辑结构 创建文件 删除文件 打开文件 关闭文件 读文件 写文件 无结构 一 有结构 "create" 系统调用 分配外存空间，创建目录项 "delete" 系统调用 回收外存空间，删除目录项 "open" 系统调用 将目录项中的信息复制到内存中的打开文件表中，并将打开文件表的索引号(文件描述符)返回给用户 打开文件之后，对文件的操作不再需要每次都查询目录，可以根据内存中的打开文件表进行操作 每个进程有自己的打开文件表，系统中只有一张总的打开文件表 并不会把文件数据直接读入内存，只有在读文件时才数据从外存读入内存进 程打开文件表属性：读写指针、访问权限、系统表索引号 系统打开文件表属性：外存地址、打开计数器(有多少个进程打开了该文件) "close" 系统调用 将进程打开文件表中的相应表项删除 系统打开文件表的打开计数器减1,若打开计数器为0,则删除系统表的表项 "read" 系统调用 根据读指针、读入数据量、内存位置将文件数据从外存读入内存 "write" 系统调用 根据写指针、写出数据量、内存位置将文件数据从内存写出外存 "读/写文件"用”文件描述符"即可指明文件，不再需要用到文件名 由二进制流或字符流组成，无明显的逻辑结构，又称“流式文件”。如windows中的".txt” 文件 由一组相似的记录组成，又称“记录式文件”,分为定长记录、可变长记录。每条 记录由若干个数据项组成。如数据库表文件。 串结构 记录之间的顺序与关键字无关 顺序结构 记录之间的顺序按关键字顺序排列 链式存储定长/可变长记录，都无法实现随机存取，每次只能从第一个记录开始依次往后查找 可变长记录 一 无法实现随机存取。每次只能从第一个记录开始依次往后查找 可实现随机存取。记录长度为L则第 i 个记录存放的相对位置是i*L 若采用串结构，无法快速找到某关键字对应的记录 若采用顺序结构，可以快速找到某关键字对应的记录(如折半查找) 可变长记录的顺序文件无法实现随机存取，定长记录可以 定长记录、顺序结构的顺序文件可以快速检索(根据关键字快速找到记录) 最大缺点：不方便增加/删除记录 建立一张索引表，每个记录对应一个表项。各记录不用保持顺序，方便增加/删除记录 索引表本身就是定长记录的顺序文件，一个索引表项就是一条定长记录，因此索引文件可支持随机存取若 索引文件 索引表按关键字顺序排列，则可支持快速检索 解决了顺序文件不方便增/删记录的问题，同时让不定长记录的文件实现了随机存取。但索引表可能占用很多空间 将记录分组，每组对应一个索引表项 索引顺序文件 十 检索记录时先顺序查索引表，找到分组，再顺序查找分组 当记录过多时，可建立多级索引表 文件控制块(实现文件目录的关键数据结构) 文件目录的实现 对目录的操作：搜索、创建文件、删除文件、显示文件、修改文件 一个文件对应一个FCB,一个FCB就是一个目录项，多个 FCB组成文件目录 文件目录 文件管理 文件共享 文件保护 不同用户的文件可以重名，但不能对文件进行分类 一个系统只有一张目录表，不允许文件重名 系统根据“文件路径”找到目标文件 不同目录下的文件可以重名，可以对文件进行分类，不方便文件共享 从根目录出发的路径是“绝对路径”("1照片12015-081自拍jpg") 从“当前目录”出发的路径是"相对路径”(".12015-081自拍jpg") 为共享结点设置一个共享计数器，计数器为0时才真正删除该结点 无环图目录结构 在树形目录结构的基础上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图 各个用户的目录项指向同一个索引结点 索引结点中需要有链接计数 count 基于索引节点的共享方式(硬链接) 只有count==0 时才能真正删除文件数据和索引结点，否则会导致指针悬空 某用户想删除文件时，只是删除该用户的目录项，且count -- 除了文件名之外的所有信息都放到索引结点中，每个文件对应一个索引结点 索引节点(对文件控制块的优化) 目录项中只包含文件名、索引结点指针，因此每个目录项的长度大幅减小 目录项长度减小→每个磁盘块可以存放更多个目录项→检索文件时磁盘I10 的次数减少 即使软链接指向的共享文件已被删除，Link 型文件依然存在， 只是通过Link 型文件中的路径去查找共享文件会失败(找不到对应目录项) 在一个Link 型的文件中记录共享文件的存放路径(Windows 快捷方式) 基于符号链的共享方式(软链接) 由于用软链接的方式访问共享文件时要查询多级目录，会有多次磁盘I/O, 因此用软链接访问共享文件的速度要比硬链接更慢 操作系统根据路径一层层查找目录，最终找到共享文件 实现开销小，但"口令“一般存放在 Fcs或索引结点中(也就是存放在系统中),安全性低 口令保护 为文件设置一个"口令",用户想要访问文件时需要提供口令，由系统验证口令是否正确 用一个访问控制表(ACL)记录各个用户(或各组用户)对文件的访问权限 对文件的访问类型可以分为：读1写1执行1删除等 访问控制 如果对某个目录进行了访问权限的控制，那也要对目录下的所有文件进行相同的访问权限控制 实现灵活，可以实现复杂的文件保护功能 安全性高，但加密/解密需要耗费一定的时间(如：异或加密) 加密保护 用一个"密码"对文件加密，用户想要访问文件时，需要提供相同的"密码"才能正确的解密 文件管理 连续分配 链接分配 文件的物理结构 (文件分配方式) 索引分配 要求每个文件在磁盘上占有一组连续的块。 优点：支持顺序访问和直接访问(即随机访问);连续分配的文件在顺序访问时速度最快 缺点：不方便文件拓展，会产生磁盘碎片，存储空间利用率低 除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。 文件目录包括文件第一块的指针和最后一块的指针。 优点：方便文件拓展，无碎片问题，外存利用率高 隐式链接 缺点：只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的 指针也需耗费少量存储空间 考试题目中遇到未指明隐式/显式的“链接分配”,默认指的是隐式链接的链接分配 把用于链接文件各物理块的指针显式地存放在一张表中，即文件分配表(FAT) 一个磁盘只会建立一张文件分配表，开机时文件分配表放入内存，并常驻内存 显式链接 优点：文件拓展方便，无碎片问题，外存利用率高，支持随机访问。相比于隐式 链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高 缺点：文件分配表需要占用一定的存储空间 允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的 各个逻辑块对应的物理块(索引表的功能类似于内存管理中的页表——建立逻辑页面到物理页之间的映射关系) 如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放 缺点：若文件很大，索引表很长，需将很多个索引块链接起来。想要找到i 号索引块，必须先依次读入 0~ i-1 号索引块，导致磁盘I/O 次数过多，查找效率低下 建立多层索引(原理类似于多级页表)。使第一层索引块指向第二层的索引块。 还可根据文件大小的要求再建立第三层、第四层索引块 多层索引 采用K 层索引结构，且顶级索引表未调入内存，则访问一个数据块需要K+1 次 读磁盘操作缺点：即使是小文件，访问一个数据块依然需要K+1 次读磁盘。 多种索引分配方式的结合，文件的顶级索引表中，既包含直接地址索引(直接指向数据块), 又包含一级间接索引(指向单层索引表),还包含两级间接索引(指向两层索引表) 优点：对于小文件来说，访问一个数据块所需的读磁盘次数更少 根据多层索引、混合索引计算出文件的最大长度(Key: 各级索引表最大不能超过一个块) 分析访问某个数据块所需要的读磁盘次数(Key:FCB 中会存有指向顶级索引块的指针， 因此可以根据 FCB读入顶级索引块。每次读入下一级的索引块都需要一次读磁盘操作 注意题目条件顶级索引块是否已调入内存 磁盘、磁道、扇区 磁盘由表面涂有磁性物质的圆形盘片组成 每个盘片被划分为一个个磁道，每个磁道又划分为一个个扇区 磁盘中读/写数据 一 磁头移动到目标位置，盘片旋转，对应扇区划过磁道完成读/写 磁盘的结构 盘面、柱面 磁盘的物理地址 磁盘的分类 磁盘由多个盘片”摞”起来，每个盘片有两个盘面 所有盘面中相对位置相同的磁道组成柱面 (柱面号，盘面号，扇区号) 固定头磁盘(每个磁道有一个磁头) 根据磁头是否可移动 移动头磁盘(每个盘面只有一个磁头) 固定盘磁盘 根据盘片是否可更换 可换盘磁盘 思想 评价 先来先服务( FCFS) — 按访问请求到达的先后顺序进行处理 优点：公平；缺点：请求访问的 磁道分散时寻道时间长，性能差 磁盘组织与管理 磁盘速度算法 一次磁盘读/写操作 减少磁盘延迟时间 每次都优先响应距离磁头最近的磁道访问请求， 最短寻找时间 (SSTF) 一 贪心算法的思想，能保证眼前最优，但无法保证 优点：平均寻道时间短；缺点：可能导致饥饿 总的寻道时间最短 优点：平均寻道时间较短 扫描算法( SCAN) 一 只有磁头移动到最边缘的磁道时才可以改变磁头移动方向 一 无饥饿现象；缺点：对各个 位置磁道的响应频率不平均 只有磁头朝某个方向移动时才会响应请求， 循环扫描算法(C—SCAN) 一 移动到边缘后立即让磁头返回起点，返回途 中不响应任何请求 LOOK算法 一 SCAN算法的改进，只要在磁头移动方向上不再有请求，就立即改变磁头方向 一 \ C-LOOK算法 一 C-SCAN 算法改进，只要在磁头移动方向上不再有请求，就立即让磁头返回 一 \ 寻道时间 一 启动磁臂、移动磁头所花的时间 延迟时间 一 将目标扇区转到磁头下面所花的时间 传输时间 — 读 /写数据花费的时间 具体做法：让编号相邻的扇区在物理上不相邻 交替编号 原理：读取完一个扇区后需要一段时间处理才可以继续读入下一个扇区 具体做法：让相邻盘面的扇区编号”错位” 错位命名 原理：与"交替编号"的原理相同，“错位命名法”可降低延迟时间 采用(柱面号，盘面号，扇区号)结构，相邻盘面的相同磁道不用 磁盘地址 — (盘面号，柱面号，扇区号)结构，本盘面的相邻磁道原因：在读 取地址连续的磁盘块时，前者更不需要移动磁头 低级格式化/物理格式化：划分扇区 磁盘的初始化 磁盘分区：每个分区由若干柱面组成(即为C盘/D 盘/E盘) 逻辑格式化：建立文件系统(建立根目录文件、建立用于存储空间管理的数据结构) 磁盘的管理 引导快 计算机启动时需要运行初始化程序(自举程序)来完成初始化 ROM 中存放很小的“自举装入程序 完整的自举程序存放在初始块(引导块)中 简单的磁盘：逻辑格式化时在FAT表上将坏块标记出来，坏块对操作系统 环块的管理 一 不透明复杂的磁盘：磁盘控制器维护一个坏块链，低级格式化时对坏块链 进行初始化并管理备用扇区，坏块对操作系统透明 I/O 管理 I/O 管理概述 按使用特性 一 ，人机交互类外部设备、存储设备、网络通信设备 低速设备 如键盘、鼠标 按传输速率 中速设备 如行式打印机、激光打印机 分类 高速设备 如磁带机、磁盘机、光盘机 块设备：传输快，可寻址，随机读写任一块 按信息交换的单位 字符设备：传输慢，不可寻址，常采用中断驱动方式 控制寄存器：接受和识别CPU 发出的命令 状态寄存器：向CPU 报告设备的状态 主要功能 数据寄存器：数据交换，暂存输入/输出的数据 I/O 逻辑：地址识别 CPU 与控制器之间的接口：实现控制器与CPU 之间的通信 I/O 逻辑：负责识别CPU发出的命令，并向设备发出命令 控制器与设备之间的接口：实现控制器与设备之间的通信 控制器中的寄存器与内存统一编址 内存映射I/O 可以采用对内存操作的指令来对控制器进行操作 控制器中的寄存器独立编址 寄存器独立编制 需要设置专门的指令来操作控制器 完成一次读/写的过程 CPU干预频率 每次I/O 的数据传输单位 程序直接控制方式 CPU发出I/O 命令后需要不断轮询 极 高 字 CPU 发出I/O 命令后可以做其他事， 中断驱动方式 本次/O完成后设备控制器发出中断信号 I/O 控制方式 CPU发出I/O 命令后可以做其他事， 块 本次/O完成后DMA 控制器发出中断信号 CPU发出 I/O 命令后可以做其他事。 通道会执行通道程序以完成/O,完成 后通道向CPU 发出中断信号 用户层I/O 软件 — 实现与用户交互的接口，向上提供方便易用的库函数；假脱机技术 向上层提供统一的调用接口(如read/wr ite系统调用);设备的保护；差错处理； 设备独立性软件 — 设备的分配与回收；数据缓冲区管理；建立逻辑设备名到物理设备名的的映射关系， 根据设备类型选择调用相应的驱动程序 I/O 软件层次 设备驱动程序 一 设置设备寄存器、检查设备状态 中断处理程序 — 进行中断处理 硬件设备 执行I/O 操作，由机械部分、电子部分(I/O 控制器)组成 数据流向 设备→CPU→内存内存 →CPU→设备 设备→CPU→内存内存 →CPU→设备 设备 → 内存内存 → 设备 设备 → 内存内存 → 设备 假脱机技术 缓存区管理 I/O 管理 I/O 核心子系统 设备的分配与回收 外围控制机+更高速的设备磁带 脱机技术 作用：缓解设备与CPU的速度矛盾，实现预输入、缓输出又 又叫SPOOLing 技术，用软件的方式模拟脱机技术 输入井和输出井一模拟脱机输入/输出时的磁带 假脱机技术 输入进程和输出进程一模拟脱机输入/输出时的外围控制机 输入缓冲区和输出缓冲区一内存中的缓冲区，输入输出时的“中转站” 共享打印机 一 用 SPOOLing技术将独占式的打印机”虚拟”成共享打印机 利用硬件作为缓冲区的成本较高，容量较小，如TLB。一般利用内存作为缓冲区 缓解CPU与设备的速度矛盾、减少对CPU的中断频率及放款对CPU中断响应时间的限制、 解决数据粒度不匹配的问题、提高CPU与 I/O 设备之间的并行性 设备输入(T)、缓冲区传送(M)、 工作区处理(C) 分析问题的初始状态：工作区满，缓冲区空 处理一块数据平均耗时Max(C,T)+M 分析问题的初始状态：工作区空，一个缓冲区满，另一个缓冲区空处理一块数据平均耗时Max (T,C+M) 多个缓冲区链接成循环队列，in指针指向下一个可以冲入数据的空缓冲区，out 指针指向下一个可以取出数据满缓冲区 空缓冲队列 缓冲队列 输入队列 输出队列 用于收容输入数据的工作缓冲区(hin) 用于提取输入数据的工作缓冲区(sin) 用于收容输出数据的工作缓冲区(hout) 用于提取输出数据的工作缓冲区(sout) 独占设备、共享设备、虚拟设备(SPOOLing) 先来先服务、优先级高者优先、短任务优先等 应考虑的因素 安全分配方式 为进程分配一个设备后就将进程阻塞，本次I/O 完成后才将进程唤醒 不安全分配方式 系统为进程分配I/O 设备，进程可继续执行 静态分配：进程运行前为其分配全部所需资源，运行结束后归还资源 动态分配：进程运行过程中动态申请设备资源 根据进程请求的物理设备名(设备标识符)查找SDT 根据SDT找到 DCT并分配设备 根据DCT找到COCT并分配控制器 根据COCT找到CHCT并分配通道 设备分配的步骤 只有设备、控制器、通道三者都分配成功时，这次设备分配才算成功，之后便可启动/O 设备进行数据传送 缺点： 用户编程时必须使用”物理设备名",若换了一个物理设备，则程序无法运行；若进程请求的物理设备正在忙碌， 则即使系统中还有同类型的设备，进程也必须阻塞等待用户编程时使用逻辑设备名申请设备，操作系统负责实 现从逻辑设备名到物理设备名的映射(通过 LUT) 整个系统只有一张LUT:各用户所用的逻辑设备名不允许重复，适用于 单用户操作系统每个用户一张LUT:各个用户的逻辑设备名可重复， 适用于多用户操作系统 概念 以实现远程通信为目的，一些互联的、独立自治的计算机的集合 组成 组成部分 工作方式 功能组成 硬件 软件 协议 边缘部分 核心部分 通信子网 核心子网 主机、通信链路(双绞线/光纤)、交换设备( 路由器/交换机)、通信处理机(网卡) 实现资源共享的软件、方便用户使用 的工具软件 计算机网络的核心 C/S方式 P2P方 式 为边缘部分提供连通性和交换服务 实现数据通信 实现资源共享/数据处理 数据通信 资源共享 连通性 软件、硬件、数据 功能 分布式处理 提供可靠性 多台计算机各种承担同一工作任务的不同部分 互为替代机 负载均衡 工作任务均衡地分配给计算机网络的各台计算机 计算机网络体系结构 分布范围 广域网 (WAN) 城域网 (MAN) 局域网 (LAN) 通常跨越很大的物理范围，作用范围通常是几十千米 到几千千米 作用范围一般是一个城市，可以跨越几个街区甚至政 整个城市，其作用距离是5~50km 作用范围很小(一般是1km左右),一般用微型计算机 或工作站通过高速通信线路连接 个人局域网 (PAN) 在个人工作的地方把属于个人使用的电子设备用无 线技术链接起来的网络，其作用范围一般是10m 传输技术 广播式网络 点对点网络 总线型 共享公共信道 使用分组存储转发和路由选择机制 单根传输线 分类 拓扑结构 星型 环型 网状型 有一个中心结点 信号单项传输 多用于广域网 电路交换技术 交换技术 报文交换 分组交换 使用者 公用网 专用网 缴纳费用的人都可以使用的网络 某个部门为了满足本单位的特殊业务而建造的网络 标准化及相关组织 速率(数据率/数据传输速率/比特率) 连接在计算机网络上的主机在数字信道上传输数据位数的 速率，单位为bps ( 或bit/s、b/s) 通信线路允许通过的信号频带范围，单位为Hz 带宽 网络的通信线路传输数据的能力，单位时间内某信道所能通过的最高数据率 吞吐量 单位时间内通过某个网络(或信道、接口的数据量) 定义：数据(一个报文/分组/比特流)从网络的一段传输到另一端所需的时间 发送时延 数据帧长度/发送速率 传播时延 信道长度/电磁波在信道上的传播速率 时延 计算机网络的性能指标 排队时延 处理时延 分组进入路由器后在输入队列中排队等待处理所 花费的时间 主机或路由器在收到分组时分析分组的首部、进 行差错检验等所花费的时间 总时延 发送时延+传播时延+处理时延+排队时延 以比特为单位的链路长度，即“某段链路现在有多少比特” 时延带宽积 传播时延×信道带宽 往返时延RTT 双向交互一次所需要的时间 利用率 信道利用率 网络利用率 有数据通过时间/(有+无)数据通过时间 信道利用率加权平均值 计算机网络体系结构 体系结构 为完成用户所要求的功能而应传送的数据 控制协议操作的信息 协议数据单元PDU (PDU =SDU+PCI) 对等层次之间的传送的数据单位 链路层PDU: 帧 控制对等实体进行通信的规则的集合 物理层PDU: 比特 定义传输数据的格式 协议(水平) 规定所要完成的功能 同步 规定执行各种操作的条件/时序关系 同一节点内相邻两层间交换信息的连接点 接口 同一节点相邻两层的实体通 过服务访问点SAP进行交互 传输层SAP: 端口 网络层SAP:I P地址 数据链路层SAP:MAC 地址 下层为紧邻的上层提供的功能调用 服务(垂直) 服务是通过SAP提供给上层使用的 应用层 表示层 会话层 7 层OSI参考模型 传输层 面向连接 网络层 无连接+面向连接 数据链路层 物理层 应用层 传输层 无连接+面向连接 4层TCP/IP参考模型 网际层 无连接 网络接口层 OSI参考模型 应用层 表示层 会话层 传输层 网络层 数据链路层 物理层 用户与网络的界面 主要协议：文件传输协议FTP, 电子邮件SMTP, 万维网HTTP 处理两个通信系统中交换信息的表示方式(语法和语义) ① 数据格式变换 功能 ② 数据加密解密 ③ 数据压缩和恢复 主要协议：JPEG、ASCII 向表示层实体/用户进程提供建立连接上有序的传 输数据，建立同步SYN ① 建立/管理/终止会话 功能 使用校验点可使会话在通信失效时从校验点/同步点继续恢复通 信，实现数据同步 主要协议：ADSP、ASP 复杂主机中两个进程的通信，即端到端的通信 ① 可靠传输/不可靠传输 ② 差错控制 功能 ③ 流量控制 ④ 复用/分用 分用：传输层将收到的信息分别交付给上面应用层的相应进程 主要协议：TCP、UDP 将分组从源端传送到目的端，为分组交换网上的不用主机提供通信服务 路由选择 ② 流量控制 ③ 差错控制 ④ 拥塞控制 主要协议：IP、IPX、ICMP、IGMP、ARP、RARP OSPF 将网络层传下来的数据组装成帧 0 成帧(定义帧的开始和结束) ② 差错控制(帧错+位错) ③ 流量控制 ④ 访问控制(控制对信道的访问) 主要协议：SDLC、HDLC、PPP、STP 在物理媒体上实现比特流的透明传输 定义接口特性 ② 定义传输模式(半工/半双工/全双工) 功能 3 定义传输速率 ④ 比特同步 ⑤ 比特编码 主要协议：RJ45、8023 规格、接口形状、引脚数目等 信号的电压范围、阻抗匹配、传输速率、距离限制 某一电平表示何种意义、接口部件的信号线的用途 工作规程、时序 屏蔽双绞线STP 双绞线 非屏蔽双绞线UTP 基带同轴电缆 同轴电缆 宽带同轴电缆 定义 光纤 在横向模式直接传输光信号 传输介质 有多种传输光信号模式的光纤 信号向所有方向传播 信号固定方向传输 地面微波接力通信 卫星通信 1 信号固定方向传播 红外线、激光 把要输入的信号分别转换为各自信号格式、即红外光信号和激光信号 再生还原信号 中继器 连接两类完全相同的网络，网段协议与速率相同 5-4-3规则 5个网段4个中继器3个主机 设备 再生放大信号 集线器 连接在集线器上工作主机平分宽带 基本概念 基带信号 信号 带宽信号 传输信号 信道 传输介质 将数字0和1直接用两种不同的电压表示，再送到数字信道 上去传输(基带传输) 将基带信号进行调制后形成的频分复用模拟信号，在传送 到模拟信道上去传输(宽带传输) 模拟信道 数字信道 无线信道 有线信道 码元 速率 用一个固定时长的信号波形(数字脉冲)代表不同的离散数值的基本波形， 是数字通信中数字信号的计量单位。1码元可以携带多个比特信息 单位时间内数字通信系统所传输的码元个数(也可称为 脉冲个数或信号变化的次数),单位：波特 单位时间内数字通信系统传输的二进制码元个数(即比特数) 奈奎斯特定律 (带宽受限无噪音) 极限码元传输速率2WBaud( 码元传输速率有上限) 极限数据传输速率C=2Wlog₂V(bps) W: 带 宽 V: 码元离散电平数目 两个定理 香农定理 (带宽受限有噪音) 物理层 模拟数据→数字信号 (编码脉冲调制 PCM) 提高数据传输率：提高带宽/使每个码元携带更多个比特的信息量 信噪比dB=10lg(S/N) 极限数据传输速率C=W logz(1+S/N)(b/s) W: 带宽 S/N: 信噪比 提高数据传输速率：提高带宽/信噪比 二进制数据 非归零编码 基带信号 编码与调制 2PSK 数字数据→模拟信号 ( 调制解调器) 模拟数据→模拟信号 (调制放大器调制器) ①幅移键控 ②频移键控 ③相移键控 ④调幅+调相QAM 串行传输 速度慢，费用低，适合远距离 数据传输方式 并行传输 速度快，费用高，适合近距离(用于计算机内部数据传输) 单工通信 只能有一个方向的通信而没有反方向的通信 通信方式 半双工 全双工 通信的双方都可以发送消息，但不能同时发送(或接收) 通信双方可以同时发送和接收信息 为网络层提供服务 无确认无连接服务 有确认无连接服务 有确认有连接服务 适用于实时通信或误码率比较低的通信通道，如以太网 适用于误码率比较高的通信信道，如无线通信 建立数据链路，传输帧，释放数据链路 适用于通信要求(实时性，可靠性)较高的场合 连接的建立、维持、释放(用于面向连接) 帧头部用一个字段标明帧的内字符数 ② 字符填充法 组帧 ④违规编码法 发送窗口大小=1,接收窗口大小=1 特殊字符前用转义字符填充 信道利用率 Tb/(TD+RTT+TA) 用违规的编码表示帧的起始和终止 发送窗口大小>1,接收窗口大小=1 累计确认(偶尔稍待确认) 0 后退N帧协议GBN 按序接收帧、无序丢弃 功能 比特错 差错控制 帧错 1≤WT≤2n-1 奇校验码 偶校验码 检错编码 生成多项式 ② 循环冗余CRC 帧检验序列FCS 2≥ k+r+1(r 为冗余信息位，k 为信息位) 校验码P1,P2、P3、P4放在2的几次方位置 ② 确定校验码和数据的位置 数据D1、D2.……D6 按序把空填满 3 求出校验码的值 ④检错并纠错 O 频分多路复用FDM 同 样 的 时 间 占 用 不 同 的 带 宽 ( 并 行 ) 每 一 个TDM 帧 中 占 用 固 定 序 号 的 时 隙 ( 并 发 ) 静态划分信道 信道划分介质访问控制 ③ 统计时分复用STDMP 按需动态分配时隙 时隙ALOHA协议 想发就发 时间片开始时刻发送 ⑨ 波分多路复用WDM ⑤ 码分多路复用CDM 光的频分多路复用 码分多址CDMA ② CSMA协议 介质访问控制 非坚持CSMA p- 坚持CSMA 总线式以太网 0 确定基本退避时间为2t ( 争用期) 数据链路层 随机访问介质访问控制 截断二进制指数重传法 ② k=min [重传次数，10] ③ r=random(0-2^k-1)2tr ④重传16次未成功，抛弃并向高层报告出错 帧的传输时延至少两倍于信号在总线中的传播时延 最小帧长 最小帧长=总线传播时延×数据传输率*2 以太网规定的最短帧长为64B 用于无线局域网 轮询访问介质访问控制 一般工作在全双工方式 ③ RTS/CTS帧(可选) 轮询协议 主节点轮流“邀请”从属结点发送数据 令牌：一个特殊格式的MAC控制帧，不含任何信息 令牌传递协议 无碰撞，应用于令牌环网(物理星型拓扑，逻辑环型) 交换机 直通式交换机 查完目的地址(6B) 立刻转发 延迟小，可靠性低，不支持具有不同速率的端口的交换 存储转发式交换机 方式高速缓存，检查正确则转发，错误则丢弃 延迟大，可靠性高，支持不同速率的端口的交换 透明网桥 链路层设备 网桥 源路由网桥 自学习 最佳路由 能否隔离冲突域名 能否隔离广播域 物理层设备(中继器/集线器) 冲突域与广播域 链路层设备(网桥/交换机) 网络层设备(路由器) 星型结构 ② 总线型拓扑 拓扑结构 传输介质 介质访问控制 ④树型拓扑 有线局域网 无线局域网 CSMA/CD 令牌总线 令牌环 常用介质：双绞线、同轴电缆、光纤 常用介质：电磁波 常用于总线型局域网，也可用于树型网络 常用于总线型局域网，也用于树型网络 用于环型局域网，如令牌环网 源地址 目的地址 icsk MAC层 物理层 前同步码 发通在前 楚 数据链路层(局域网) IEEE 802.3 IEEE 802委员会802.3工作组制定的第一个EEE的以太网标准 无连接：发送方接收方无^握手过程” 以太网 服务 协议 传输介质 物理拓扑 CSMA/CD 粗同轴电缆 → 细同轴电缆一双绞线+集线器 总线型 → 星型 分 类 传输速率：10Mb/s 基带信号 传输媒体：非屏蔽双绞线 结构：逻辑总线型，物理星型 编码：曼彻斯特编码 协议：CSMA/CD 最多结点数目：2 最大段长：100m 100 Mb/s 基带信号，双绞线，星型拓扑 分类 无线局域网 令牌环网 FDD 网 有无固定基础设施无线局域网 分类 无固定基础设施无线局域网的自组织网络 标准：IEEE 802.5 物理上星型拓扑，逻辑上环型拓扑 标准；IEEE 802.8 物理上双环拓扑，逻辑上环型拓扑 高速以太网 吉比特以太网 10吉比特以太网 1Gb/s,光纤/双绞线 支持全双工/半双工，在全双工方式下无冲突 (半双工使用CSMA/CD,全双工不使用) 10Gb/s,光纤 只支持全双工(不使用CSMA/CD)无争用问题 逻辑链路控制子层LLC 识别网络协议并封装 链路层的两个控制子层 应用层 表示层 会话层 传输层 网络层 数据链路层 物理层 服务访问点 逻辑链路控制子层 介质访问控制子层 物理层 介质访问控制子层MAC 数据帧的封装/卸载/寻址/识别/接收/发送/差错控制 屏蔽不同物理链路种类的差异性 LCP链 路 终止 链路终止 链路故障或 关闭请求 PPP协议· 状态图 LCP配置 协商失败 鉴别失败 链路静止 设备之间无链路 物理层连接建立 物理链路 LCP 配置协商 鉴别 LCP链路 鉴别成功或无需鉴别 已鉴别的LCP链路 网络层协议 NCP配置协商 已鉴别的LCP 链路 链路打开 和NCP 链路 网络控制协议NCP:为网络层协议建立和配置逻辑连接 IP 数据报 先发送 字节 首部 C 03 协议 信息部分 不超过1500B PPP 帧一 尾部 FCS 地址字段A 控制字段C 帧格式 ⑤ 信息字段 数据链路层(广域网) 7E(01111110), 前后各占1B 占2B,说明信息段中运载的是什么种类的分组 占1B, 规定为0xFF 比特0开始：IP/IPX/AppleTalk 等网络层协议 占1B, 规定为0x03 ④ 协议字段 0×0021表示信息字段是IP数据报 比特1开始：协商其他协议，包括LCP以及每个所支持的网络层的一个不同的NCP 长度可变，范围0-1500B(PPP协议是点对点而不是总线型，无需采用CSMA/ CD协议，没有最短帧) 占2B,循环冗余检验码中的冗余码，检验区包括地址字段、控制字段、协 议字段、信息字段 8 比特 标 志F 可变 地址A 控制C 信息Info 16 帧检验序列FCS 标志F 透明传输区间一 0 标志段F 01111110,采用比特填充的首尾标志法实现透明传输 平衡方式：写入从站地址 帧格式 地址字段A 非平衡方式：写入应答站地址 信息帧(I) 第一位为0 传输数据信息/使用捎带技术对数据进行确认 3 控制字段C 监督帧(S) 一二位为10 流量控制和差错控制，执行对信息帧的确认/请求重发/请求暂停发送 无编号帧(U) 一二位为11 链路建立/拆除的控制 异构网络互联 使用IP协议使性能各异的网络在网络层看起来好像是一个统一的网络 路由与转发 路由选择 分组转发 静态路由算法(非自适应路由算法) 动态路由算法(自适应路由算法) 使用分组交换的方式转发IP数据报 虚电路服务 数据报服务 采用集中式的控制层面和分布式的数据层面，两个层面相互分离，控制层面利 用控制-数据接口对数据层面的路由选器进行集中式控制，方便软件控制网络 网络层功能 SDN ( 软件定义网络) 的基本概念 开环控制 拥塞控制 闭环控制 SDN网络体系架构 静态不可更改 动态实时调整 0 协同应用层：这一层主要是体现用户意图的各种上层应用程序。 控制层：控制层是系统的控制中心，负责网络的内部交换路径和边界业务路 由的生成，并负责处理网络状态变化事件。 转发层：转发层主要由转发器和连接器的线路构成基础转发网络，这一层负 责执行用户数据的转发，转发过程中所需要的转发表项是由控制层生成的。 北向接口：控制层与协同应用层的接口。(向上为北向) 南向接口：控制层与转发层的接口。(向下为南向) OpenFlow 协议：描述控制层和转发层之间交互所用信息的标 准，以及控制器和交换机的接口标准 电路交换 报文交换 建立连接→通信→释放连接 存储转发 网络层(1) 连接建立 电路交换 报文交换 分组交换 Pa 数据传送 连接释放 报文 数据传送 数据交换方式 比特流直达终点 报文报文报文 存储存储 转发转发 分组分组分组 存储存储 转发转发 连接建立 目的地址 路由选择 分组顺序 可靠性 对 网络故障的适应性 差错处理和流量控制 分组交换 数据报 虚电路 不要 必须有 仅在建立连接阶段使用，之后 每个分组都有完整的地址 每个分组使用长度较短的虚电 路号 每个分组独立地进行路由选择属于同一条虚电路的分组按照 出故障的结点丢失分组，其他 所有经过故障结点的虚电路均 分组路径选择发生变化可正常 传输 由用户主机进行流量控制，不可由分组交换网负责，也可由 保证数据报的可靠性 用户主机负责 版本 IP协议的版本，IPv4为4 首部长度 单位：4B,范围：20~60B, 最常用的首部长度为20B,此时不使用任何可选字段 区分服务 期望获得哪种类型的服务 单位：1B,数据报最大长度为216-1=65535字节。以太网帧的最大传送单元MTU 为1500字节，一个IP数据报封装成帧时，数据包的总长度3定不能超过下面数据链 总长度 路层的MTU值 位 0 16 31 版本 区分服务 总长度 标识 标志 片偏移 生存时间 协议 首部检验和 源地址 目的地址 可 变 可选字段(长度可变) 填 充 数 据 部 分 首部 数据部分 — IP 数据报一 IP数据报 发送在前 是一个计数器，每产生一个数据报就加1。不是序号，IP是无连接服务 标识 当一个数据报超过网络的MTU时，必须分片，此时每个数据报片都复制3次标识 号以便能正确重装成原来的数据报 中间位DF 1:禁止分片0:允许分片 标志 最低位MF 1:还有分片0:最后一片 片偏移 单位：8B,较长分组分片后，某片在原分组中的相对位置 数据报在网络中可通过的路由器数的最大值，路由器在转发之前先把TTI减 生存时间TTL 1,若TTL减为0则该分组必须丢弃 分组的数据部分交给哪个传输层协议 协议 6:TCP 17:UDP 首部校验和 只校验首部，不校验数据部分 网络层 (IPv4) 源地址、目的地址、可选字段 最大可用网络数 第一 的网最后一 用的网每个网络中最大的主 2⁷-1 126 224-2 214-1 128.1 191.255 216-2 221-1 192.0.1 223.255.255 2⁸-2 24 32 A类(1~126) 0 网络号 主机号 B类(128~191)10 C类(192~223)100 D类(224~239)Du0 E类(240~255)1 IP地址 特殊的IP地址 网络号 网络号 全0 全0 全1 特定值 特定值 127 主机号 网络号 多播地址 保留为今后使用 作为IP 分组的源作为IP分组的目的 主机号 全0 地址类别 地址范围 网段个数 网络地址转换协议 (传输层协议) 私有IP地址 A类 B类 10.0.0.0-10.255.255.255 172.16.0.0-172.31.255.255 16 C类 192.168.0.0-192.168.255.255 256 IP地址={<网络号>,<子网号>,<主机号>} IP地址={<网络前缀>,<主机号>} 斜记法：IP地址/网络前缀所占比特数 无分类编址CIDR 路由聚合：将网络前缀都相同的连续的IP地址组成"CIDR地址块" 最长前缀匹配：网络前缀越长，地址块越小，路由越具体 功能：完成主机或路由器IP地址到MAC地址的映射 网络层 (IPv4) 0 地址解析协议ARP (网络层协议) 检查ARP高速缓存，有对应项则写入MAC帧，没有则用目的 MAC地址为FF-FF-FF-FF-FF-FF的帧封并广播ARP请求分组 目的主机收到请求后向源主机单播一个ARP响应分组，源主 机收到后将此映射写入ARP缓存 主机A发给本网络上的主机B: 用ARP找到主机B 的硬件地址 主机A发给另一网络的主机B:用 ARP找到本网络上的3个路 由器(网关)的硬件地址 典型情况 ③ 路由器发给本网络的主机A:用ARP找到主机A的硬件地址 路由器发给另一网络的主机B:用ARP找到本网络上的一个 路由器的硬件地址 注：IP数据报在被路由器转发时其数据链路层封装所使用的MAC地址是在不断改 变的，决定了无法使用MAC地址跨网络通信 动态主机配置协议DHCP (应用层协议) 重要协议 网际控制报文协议ICMP (网络层协议) 功能：给动态主机分配地址 客户/服务器模式，客户端和服务器端通过广播方式进行交互，基于UDP 0 客户机广播DHCP发现报文 ② 服务器广播DHCP提供报文 工作过程 ③ 客户机广播DHCP请求报文 ④服务器广播DHCP确认报文 0 终点不可达 无法交付 拥塞丢数据 ICMP差错报告报文 3 时间超过 TTL=0/规定时间内不能收到一个数据报的全部数据报片 ④ 参数问题 首部字段有问题 ⑤改变路由(重定向) 值得更好的路由 ① 对ICMP差错报告报文不发送 ② 对第一个分片的数据报片的所有后续数据报片不发送 ③ 对具有组播地址的数据报不发送 ④ 对具有特殊地址(如127.0.0.0/0.0.0.0)的数据报不发送 回送请求和回答报文 PING: 测试两个主机之间的连通性 ICMP询问报文 Traceroute: 跟踪一个分组从源点到终点的路径 IP数据报 固定40B基本首部 IPv6首部长度必须是8B的整数倍，IPv4 首部是4B的整数倍 IPv6和IPv4 IPv6只能在主机处分片，IPv4可以在路由器和主机处分片 IPv6 网络层 (IPv6) IP组播 一个组的设备被分配一个组播组的IP地址(一群 共同需求主机的相同标识) D类地址：224.0.0.0-239.255.255.255,只能用作 分组的目标地址，并非所有D类地址都可作为组播 地址 尽最大努力交付，不提供可靠交付，应用于UDP 组播MAC地址：01-00-5E-IP组播组地址的后23位 转换十六进制 基于距离向量(距离16表示不可达),适用于小型 网络 0 距离适量协议 每30s和本节点相邻的路由器交换路由表 好消息传的快，坏消息传的慢 基于链路状态，收敛速度快，适用于大型网络 内部网关协议1 链路状态发生变化时，洪泛法向本AS内所有路由 器发送与本路由器相邻的所有路由器的链路状态 信息 ② 链路状态协议 每30分钟刷新一次数据库中的链路状态 负载均衡：将通信量分配给多条代价相同的路径 支持可变长度的子网划分和无分类编址CIDR 外部网关协 边界网关协议BGP 路由选择协议 RIP 内部 距离一向量 对比 UDP(端口520) 跳数最少 和本节点相邻的路由器 支持CIDR 打开( open)报文：与相邻的BGP发言人建立关系 并认证发送方 ③ 更新(update)报文：通知新路径或撤销原路径 保活(keepaive) 报文：确认open,周期性证实邻站 的连通性 通知(notifcation) 报文：发送检测到的差错及关闭 BGP 外部 路径一向量 TCP 较好，非最佳 和本结点相邻的路由器 交换内容 当前本路由器知道的全部 信息，即自己的路由表 与本路由器相邻的 所有路由器的链路状态 首次整个路由表非首次 有变化的部分 移动节点 具有永久IP 地址的移动设备 网络层 移动IP 通信过程 A刚进入外部网络 B给A发送数据报 A给 B发送数据报 A移动到下一个网络 0 在外部代理登记获得一个转交地址，离开时注销 ② 外地代理向本地代理登记转交地址 0 本地代理截获数据报 本地代理再封装数据报，新的数据报地址是转交 地址，通过隧道发给外部代理 3 外部代理拆封数据报并发给A A用自己的主地址作为数据报源地址 B的IP地址 作为数据报的目的地址 在新外部代理登记注册一个转交地址 新外部代理给本地代理发送新的转交地址(覆盖旧 的) A回到了归属网络 A向本地代理注销转交地址 ② 按原始方式通信 路由选择 根据路由选择协议构造路由表 与相邻路由器交换信息更新维护路由表 RIP/OSPF分组送往路由选择处理机 路由器 分组转发 根据转发表对数据分组进行转发 有多个IP 地址和MAC地址 复用：是指发送端不同的应用进程都使用同一个运输层协议传送具有一定格式的报文 ① 复用和分用 分用：指接收端的运输层在去掉报文首部后将数据正确交付给目的的应用进程 ② 运输层为应用进程之间提供端到端的逻辑通信 ③ 运输层对收到的报文进行差错检测 ④ 提供两种不同的传输协议 面向连接的TCP和无连接的UDP SOCKET=(主机IP地址，端口号) 套接字 唯一标识网络中一台主机和其上的一个应用(进程) 寻址与端口 服务端使用 熟知端口号(0-1023):一些重要的应用程序 登记端口号(1024-49151):没有熟知端口号的应用程序 客户端使用 49152~65535 仅在客户进程运行时才动态选择 无连接，在传输数据之前不需要先建立连接，减 少开销和发送数据之前的延时 ② 使用最大努力交付，不保证可靠支付 传输层 特点 3 面向报文，不合并不拆分，直接向下交付给IP层 ④ 无拥塞控制，适合很多实时应用 ⑤ 首部开销小，只占8字节 0 源端口号(16位) 在需要对方回信时选用，不需要时可全用0 UDP协议 ② 目的端口号(16位) 在不正确时由ICMP发送“端口不可达”差错报文给发送方 1516 31 16位源端口号 16位目的端口号 16位UDP长度 16位UDP检验和 首部格式 数据(如果有) ③ UDP长度(16位) 包括首部和数据 ④ UDP校验和(16位) 将伪首部、首部和数据进行二进制反码运算求和再取反 TCP协议 只在计算校验和时才出现 伪首部 源IP地址(4B) 目的IP地址(4B) 协议：17(1B) UDP长度(2B) 字节 源IP 地 址 字节 伪首部 目 的IP地 址 源端口 目的端口 0 17 2 长度 UDP长度 检验和 UDP 用户数据报 发送在前 首部 首部 数 IP 数据报一 UDP校验 12B 伪首部 8B UDP首部 7B 数据 153.19.8.104 171.3.14.11 全0 17 15 1087 15 全0 数据 数据 数据 数据 数据 数 据 数据 全0 填 充 使用16bit 段 反 码 运 算 填充部分仅参加计算 按二进制反码运算求和 将得出的结果求反码 1001100100010011→ 0000100001101000- 1010101100000011 0000111000001011 0000000000010001 0000010000111111 0000000000001101 0000000000001111 0000000000000000 0101010001000101 0101001101010100 0100100101001110 0100011100000000 0110100100010010 153.19 8.104 171.3 14.11 0和17 1087 0(检验和) 数据 数据 数据 数据和0(填充) 求 和 得 出 的 结 果 检验和 传输层 ( UDP协议) 发送端 接收端 ① 填上伪首部(不发送) ② 全0填充校验和字段 ③ 全0填充数据末端(不发送)不足4B部分 ④ 伪首部+首部+数据采用二进制反码求和 ⑤把和求反码填入校验和字段 6去掉伪首部及数据末端填充字段发送 ① 填上伪首部 ② 伪首部+首部+数据采用二进制反码求和 ③ 结果全为1则无差错，否则丢弃数据报或交给应用层附上差错的警告 小文件传输协议(TFTP)、DNS、SNMP、实时协议(RTP) 应用 0 面向连接：在传送数据之前，先建立连接 ② 点对点：每一条连接只能有两个端点 ③ 可靠交付：通过TCP连接传送的数据，无差错、不丢失、不重复且按序到达 发送缓存：准备发送的数据&已发送但未确认收到的数据 ④ 全双工通信 接收缓存：按序列到达但尚未被应用层序直接读取的数据&不按序到达的数据 ⑤ 面向字节流：将应用程序交付下来的数据看成仅仅是一连串的无结构的字节流 ① 源端口(2B) 和目的端口(2B) ② 序号(4B) 本报文段发送的数据的第一个字节的序号 期望收到对方的下一个报文段的第一个字节的序号 ③ 确认号(4B) 若确认号为N, 则证明到序号N-1为止的所有数据都已正确收到 传输层 (TCP协议) 首部长度，TCP报字段的数据起始处与TCP报文段的起始处距离 ④ 数据偏移(4位) 单位：4B, 字段值为15表示TCP首部最大长度60B ⑤ 保留字段(6位) 保留今后使用 —32位一 目的端口 20B的 固定首部 窗 口 紧急指针 填充 TCP报文段 TCP首部 TCP数据部分 发送在前 IP首部 IP数据部分 URG=1 , 紧急指针(4)有效，标明此报文段中有紧急数据，应尽快传送 ⑦ 紧急位URG 与紧急指针配套使用，数据从第一个字节到紧急指针所指字节就是紧急数据 ACK=1, 确认号(③有效；ACK=0, 确认后(③无效 确认位ACK TCP规定在连接建立后所有传送的报文段都必须把ACK置1 推送位PSH PSH=1, 接收方尽快交付接收应用进程，不再等待到缓存填满再向上交付 复位RST RST=1, 明 白TCP连接中出现严重差错，必须释放连接再重新建立传输连接 同步位SYN SYN=1, 表明一个请求连接/连接接收报文 终止位FIN FIN=1, 表面此报文段的发送方的数据已经发完并要求释放连接 窗口字段(2B) 允许对方发送的数据量 检验首部+数据 检验时加上12B伪首部 ● 校验和(2B) 源IP地址(4B)目的IP地址(4B)0(1B) 协议：6(1B)TCP长度(2B) ● 紧急指针(2B) 指出本报文段中紧急数据共有多少字节，紧急数据放在报文段数据的最前面 选项(可变长度) MSS:TCP报文段的数据字段的最大长度 ● 填充 为了使整个首部字段长度是4B的整数倍 客户端服务器模式 客户端发送连接请求报文段，不含应用层数据，SYN标志位被置为1,客户机随 机选择一个起始序号seq=x ( 连接请求报文不携带数据，但要消耗一个序号) 客户 服务器 TCP 连 接 建 立 (三次握手) 数据传送 SYN- RCVD ESTAB- LISHED 等待2MSL FIN- WAIT-1 FIN- WAIT-2 TIME- WAIT CLOSED ACK=1,seq-v,acku 数据传送 EN=1.ACK=1,seqw. 1L,sequ+1,ack=w+1 CLOSE- WAIT 被动关闭 LAST- ACK CLOSED 客户端发送连接释放报文段，停止发送数据，主动关闭TCP连接，FIN 标志位被置 ① 为1, seq=u (已传送数据的最后一个字节序号加1) (FIN 报文段不携带数据，但 要消耗一个序号) 服务器端回送一个确认报文，ack=u+1,seq=v ( 已传送数据的最后一个字节 序号加1),客户端到服务器的连接释放， TCP处于半关闭状态 ③ 服务端发完数据，发出连接释放报文段，主动关闭TCP连接 ④ 客户端回送一个确认报文字段，再等2MSL (最长报文寿命)后连接彻底关闭 概念：防止过多的数据注入网络中，这样可以使用网络中的路由器或链路不致过载 当cwndssthresh 时，每收到一个报文端的确认，cwnd加1 0 慢开始 拥塞窗口cwnd 24 20 ssthresh的初始值16 新的ssthresh值12 慢开始. 0. 2 慢开始 拥塞避免 网络拥塞 “加法增大” “乘法减小” 指数规律增长 12 14 慢开始 发送方检测到超时时采用 TCP拥塞控制 传输层(TCP协议) ② 拥塞避免 3 快重传 ④ 快恢复 当发送方连续收到3个重复ACK时，立即重传接收方期待的报文 发送方接收到冗余ACK时采用 当发送方连续收到3个重复ACK时，令ssthresh=cwnd/2,cwnd=ssthresh 0 校验 与UDP校验相同，增加伪首部 建立在传送的字节流之上，而不是建立在报文段之上 ② 序号 序号字段的值是指本报文段所发送的数据的第一个字节的序号 TCP首部的确认号是期望对方的下一个报文段的数据的第一个字节的序号 ③ 确认 累计确认：只确认数据流中至第一个丢失字节为止的字节 TCP可靠传输 TCP发送方在规定时间(重传时间)内没有收到确认就要重传已发送的报文段 自适应算法，动态改变重传时间RTTs (加权平均往返时间) 新的RTTs=(1-a)*( 旧的RTTS)+a*(新的RTT样本) a推荐值为0.125 0 超时 超时重传时间RTO=RTTs+4xRTTd(RTT的偏差加权值)注：d为下标 新的RTTd=(1-β)*(旧的RTTd)+β*(RTTs-新的RTT样本)β推荐值为0.25 注：d为下标 TCP规定每当比期望值序号大的失序报文段到达时，发送一个冗余ACK,指明下一个期 待字节的序号 冗余确认 快速重传：TCP规定当发送方收到同一个报文段的3个冗余ACK时就可以认为跟在这个 被确认报文段之后的报文段已经消失，发送方立即执行重传 接收窗口rwnd 拥塞窗口cwnd 发送窗口 接收方根据自己接收缓存的大小调整窗口字段值，反应接收方容量 发送方根据其对当前网络拥塞程度的估计而确定，反应网络当前容量 min{接收窗口，拥塞窗口} 主机A TCP流量控制 seq=1,DATA seq=101,DATA seq=201,DATA ACK=1,ack=201,rwnd=300 seq=301,DATA seq=401,DATA seq=201,DATA ACK=1,ack=501,rwnd=100 seq=501,DATA ACK=1,ack=601,rwnd=0 主机B A发送了序号1至100,还能发送300字节 A发送了序号101至200,还能发送200字节 允许A发送序号201至500共300字节 A发送了序号301至400,还能再发送100字节新数据 A发送了序号401至500,不能再发送新数据了 A超时重发旧的数据，但不能发送新的数据 允许A发送序号501至600共100字节 A发送了序号501至600,不能再发送了 不允许A再发送(到序号600为止的数据都收到了) TCP为每一个连接设置一个持续计时器，只要TCP连接的一方收到对方 的零窗口通知，就启动持续计时器。若持续计时器设置的时间到期， 就发送一个零窗口探测报文段，接收方收到探测报文段时给出现在的 窗口值。若窗口值仍然是0,发送方重新设置持续计时器 服务器 ② 永久性访问地址/域名 请求计算服务的主机 与服务器通信，使用服务器提供的服务 客户/服务器(C/S)模型 ② 间歇性接入网络 ③ 可能使用动态IP地址 ④不与其他客户机直接通信 Web, 文件传输FTP, 远程登录，电子邮件 网络应用模型 P2P模型 概念：两台主机在通信时进行的是平等的对等连接通信 ② 每个主机既可以提供服务也可以请求服务 ③ 任意端系统/节点之间可以直接通讯 ④ 节点间歇性接入网络 协议与端口：采用客户端/服务器模式，使用TCP可靠的传输服务，登录：ftp 地址 用户名&密码。控制连接采用21号端口，数据连接使用20号端口 FTP服务器 一个主进程 多个从属进程 负责接收新的请求 负责处理单个请求 ⑥ 可 扩 展 性 好 ， 网 络 健 壮 性 强 功能 应用层 文件传输协议FTP 0 提供不同种类种类主机系统(软硬件体系等都可以不同)之间的文件传输能力 用于传输控制命令和响应，在整个会话期间保持打开状态 ② 以用户权限管理的方式提供用户对远程FTP服务器的文件管理能力 控制连接 监听21号端口，整个会话期间一直保持打开状态 两 个TCP链 接 用于传输文件，在每次数据传输完毕后就关闭 数据连接 主动方式使用TCP 20端口；被动方式由服务器和客户端自行协商 打开熟知端口号21,使客户进程能够连接上 等待客户进程发出连接请求 工 作 过 程 启动从属进程，处理客户进程发来的请求 工作原理及过程 回到等待状态，继续接受其客户进程发来的请求 用户界面 TCP 控制连接端口21 控 制 进 程 因特网 数据传送 进程 FTP传输模式 文本模式 二进制模式 ASCII模式，以文本序列传输数据 Binary模式，以二进制序列传输数据 客 户 端 TCP 数据连接端口20 服 务 器 端 协议与接口：运行在UDP之上，使用53号端口 根 国家顶级域名 通用顶级域名 层次域名空间 基础结构域名 顶 级 域 名 顶 级 域 名 “ .cn” 、“ .us” 、".uk” 、“ .hk” “ .com” 、“ .net” 、". org” 、“ .gov” 只 有ARPA ( 反 向 解 析 域 名 ) 根 Com org edu goy uk 二 级 域 名 google edu hust hit 四级域名 . 域名解析系统DNS 应用层 根域名服务器 顶级域名服务器 域名服务器 ③ 授权域名服务器 ④ 本地域名服务器 最高层次的域名服务器，本地域名服务器对因特 网上域名无法解析时首先求助于根域名服务器 管理在该顶级域名服务器注册的所有二级域名 负责一个区的域名服务器，每一个主机都必须在 授权域名服务器处登记，它总是能够将其管辖的 主机名转换为该主机的IP地址 当一个主机发出DNS查询请求时，查询请求报文 就发给本地域名服务器 递归查询 m.xyz.com (a)递归查询(比较少用) m.xyZ.com (b)递归与迭代相结合的方式 信封 邮件系统将自动将信封所需信息提取出来写在信封上，用于无需亲自填写 "From:" 必须填写关键字，邮件系统自动填入 信息格式 首部 "To:" 必须填写关键字，用户填入一个或多个收件人的电子邮件地址 内容 "Subject:" 可选关键字，邮件主题 主体 发送 邮件 SMTP TCP 连接 发送方 邮件服务器 SMTP 服 务 器 SMTP 客户 发送邮件SMTP TCP连 接 接收方 邮件服务器 服务器 收件人 用户代理 POP3 客 户 SMTP 用户邮箱 (读取邮件) 发送方(发送邮件) POP3 接收方 组成结构 SMTP 因特网 用户代理 用户代理 邮件缓存 发送端邮件服务器 接收端邮件服务器 协议与端口：TCP连接，端口号25,C/S 通信阶段 建立连接→邮件传送→连接释放 SMTP协议 ① 不能传送可执行文件或者其他二进制对象 应用层(电子邮件) 缺点 ② 仅限于传送7位ASCII码 ，不能传送其他非英语国家的文字 ③ 拒绝超过一定长度的邮件 使用电子邮件系统可以支持声音、图像、视频、多种国家语言等 用户 用户 非ASCII码 非ASCII码 MIME协议 MIME MIME 协议 7位ASCII码 7位ASCII码 7位ASCII码 3 POP3协议 ④ IMAP协议 基于万维网的电子邮件 端口与协议：TCP连接，端口号110,C/S 下载并保留 工作方式 下载并删除 作用 POP3是邮件读取协议，用于用户代理从邮件服务器读取邮件 用户PC的IMAP客户程序打开IMAP服务器的邮箱时，用户可以看到邮 箱的首部，用户打开某个邮件，该邮件才上传到用户的计算机上 用户浏览器与Hotmail或Gmail的邮件服务器之间发送或接收邮件使用 HTTP协议，不同的邮件服务器之间传送邮件才使用SMTP协议 标识万维网上的各种文档，使用每个文档在整个万维 万维网客户 发起 TCP(SYN) ACK+HTTP 请求 请求图片元素 万维网服务器 非流水线 HTTP/1.1默认模式是使用流水线的持久连接 流水线 可连续发出对各个引用对象的请求，所有引用到的 对象共经历一个RTT延迟 回 应 SYN+ACK 时 间 应用层(万维网) 传输图片元素 HTTP连接方式 时 间 非持节连接 (close) 超文本传输协议HTTP 方法(操作) GET 报文结构 HEAD POST CONNECT 请求图片元素 传 输 图 片 元 素 时 间 时 间 每一个网页元素单元(如一个JPEG图，FLASH等)的传输都需要单独 建立一个TCP连接 请求一个万维网文档时间=文档传输时间(与文档的大小成正比)+ 2往返时间RTT (一个RTT用于TCP连接，另一个用于请求和接收文 档) 万维网客户 发 起TCP 连接一 RTT 第三次握手的报文段中捎带了客户对万维网文档的请求 RTT HTTP 响 应 报 文 意义 请求读取由URL所标志信息 请求读取由URL所标志的信息的头部 给服务器添加的信息 用于代理服务器 文档结构标记语言，使用约定的标记对页面上的各种信息进行描述 超文本标记语言 基本概念和术语 数据结构的三要素 绪论 算法与算法分析 数据 — 能够输入到计算机中并且被计算机程序识别和处理的符号的集合 数据元素 — 数据的基本单位 数据对象 — 相同性质的数据元素的集合 原子类型 — 不可再分 数据类型 一 结构类型 — 可再分 抽象数据类型 — 数据对象+数据关系+操作 数据结构一 是相互之间存在一种或多种特定关系的数据元素的集合 线性表 线性 栈(受限线性表) 一对一 队列(受限线性表) 逻辑结构 集合 非线性 树形结构 — 一对多的关系 图状结构一 多对多的关系 优点：实现随机存取 顺序存储 — 逻辑上相邻，物理位置上也相邻 缺点：占用一整块存储单元 优点：充分利用存储单元 链式存储 —— 逻辑上相邻，物理位置上不一定相邻 缺点：元素存储指针需要占用额外的存储空间，且只能实现顺序存取 存储结构(物理结构) 优点：检索速度快 索引存储 — 存储信息的同时，还建立附加的索引表 缺点：增加索引表，占用存储空间 优点：检索、增加、删除节点比较快 散列存储 — Hash存储，通过哈希函数计算元素存储地址 缺点：散列函数选取不好，造成元素冲突 定义 一 逻辑结构 一 运算功能 数据的运算 实现 —— 存储结构 一 — 运算操作步骤 算法 — 是对特定问题求解步骤的一种描述 输入一 0个或多个输入 输出 —— 一个或多个输出 算法特性 有穷性 — 一个算法在执行有穷步后的结束 确定性 — 每条指令必须有确切的含义 可行性 —— 算法的操作可以实现 最好时间复杂度 — 指在最好的情况下，算法的时间复杂度 最坏时间复杂度 — 指在最坏的情况下，算法的时间复杂度 时间复杂度 平均时间复杂度一 指所有可能输入实例在等概率出现的情况下，算法的期望运行时间 算法效率的度量 常见的渐进时间复杂度比较 一 0(1) L.length +1) return false if(L.length for(int 将第i 个元素及之后的元素后移 Ldata[j]=Ldata[j -1] 元素后移 ④ 插入新元素 —— Ldata[i -1]=e 表 长 + 1 —— Llength ++ 平均时间复杂度为0(n) 删除顺序表L中的第i 个位置的元素 判断i 的位置是否有效 —— if(i<1||i>Llength +1)return false 将被删除的元素赋值给e —— e=Ldata[i-1] for(intj=i;j<=Llength;j++) 将第i 个位置后的元素前移 L.data[j -1]=Ldata[j ] 元素前移 删除元素，线性表长-1 —— L length-- 平均时间复杂度为0(n) 在顺序表L中查找第一个等于e 的元素 for(i =0;inext =L->next //新结点的后继指向第一个结点 ④ L->next=s // 头节点指向新节点 ·思想：逆序插入到链表中，有一个头指针，每次新结点在表头 时间复杂度：平均时间复杂度为0(n) 方法：将新结点插入到当前链表的表尾 初试状态头指针L=NULL,尾指针r= NULL 将新结点插入到尾指针r所指节点后面，尾指针r指向新结点 0 s=( LNode*)malloc(sizeof(LNode))/ / 创建新结点 s->data =x r->nex t =s //r的后继指针指向新结点 r=s //r指向新的表尾结点 时间复杂度：平均时间复杂度为O(n) 有头结点 L->next=null 考点 无头结点 L= null 思想；1.检查位置的合法性 2.查找表中第i-1给结点，即前驱结点，然后删除 p= Getelem(L,i-1) 查找插入位置的前驱结点 5->next = p->next 新结点的指针s指向p的后继结点 p->next = s p指针指向新插入的结点 ·性能分析 插入新结点仅为0(1),查找平均时间复杂度O(n) 思想：1.先检查位置的合法性 2.查找删除位置的前驱结点 删除结点操作 q=p->next 令q指向被删除结点 p->next =q->next 将*q结点从链表中断开 Free(q) 释放结点的存储空间 定义 —— 双链表有两个指针 ( prior 指向前驱结点，next指向后继结点) s->next =p->next //将要插入结点的后继指针指向后继结点 p- >next->prior= s // 将后继结点的前驱指针指向新结点 不能更变顺序，步骤①②必须在③④之前 s->prior =p // 将新结点的前驱指针指向前驱结点 p->next =5 // 将前驱结点的指针指向新结点 双链表的操作 插入操作 表中最后一个结点的指针不是null, 而是指向头结点，从而整个链表形成环 循环判空条件 r->next =L //尾指针是否指向头结点 循环单链表 设头指针对表尾的操作 O(n) 性能分析 设尾指针对表头，表尾的操作 O(1) 在循环单链表中加入头结点prior 指针指向表尾结点 循环双链表 循环判空条件 ①L ->nex t=L &&L->prior= L / 头结点的priorl或和nextl域都等于L 栈的定义及操作 栈 栈的顺序存储结构 栈的链式存储结构 定义 栈 ( Stack) 只允许在一端进行插入或删除操作的线性表 先进后出，后进先出 栈顶：允许插入删除的一端 特点 栈底：不允许插入删除的一段 空栈：不含任何元素的空表 栈的数学性质 n个不同元素进栈，出栈元素不同的排列个数为一 C2n 重点记住，做选择题使用 InitStack(&s): 初始化一个空栈 ② StackEmpty(S): 判断栈是否为空，返回布尔值 基本操作 Push(&S,x): 进栈，把元素x压入栈顶 ④ Pop(&s,&x): 出栈，元素x弹出栈顶 GetTop(S,&x): 读取栈顶元素，用x返回栈顶元素 利用一组地址连续的存储单元存放自栈底到栈顶的数据元素 附设一个指针(top)指向当前栈顶的位置 Typedef strcuk{ 顺序栈的实现 ElemType data[Maxsize];//存放栈顶元素 int top; //栈顶指针top } SqStack; 初始化：S.top=-1; 栈顶元素：S.data[S.top] 有部分教辅会将栈指针S.top 定义为0,相当于规定top指向栈顶元素的下一个存储单元 栈空条件：S.top==-1 栈满条件：S.top =MaxSize-1 栈长：S.top+1 顺序栈的基本操作 栈不满时，栈顶指针S.top先加1,再送元素x到栈顶元素 进栈操作 S.data [++S.top]=x;/ /指针加1,再进栈 栈非空时，先取栈顶元素值x, 再将栈顶指针S.top先减1 出栈操作 x= S.data[S.top--1;// 先把元素出栈，指针再-1 读取栈顶元素 一 x=S.top[S. top] 两个顺序栈共享存储空间，两个栈顶向中间延伸 top0=-1 时0号栈为空，top1=Maxsize 0 号 栈 栈 底 0 号 栈 栈 顶 0 号 栈 栈 顶 栈满条件：top1- top 0=1 两个顺序栈共享存储空间 共享栈是为了更有效地利用存储空间，两个栈空间相互调节，只有在整个存储空间被占满时才发生上溢。 存取数据的时间复杂度为0(1) 头节点 栈顶节点 栈底节点 链栈基本结构 优点：便于多个栈共享存储空间和提高效率，不会出现栈满上溢的情况 采用链式存储结构的栈称为链栈 通常采用单链表实现。采用链式存储，便于结点的插入与删除基本操作和链表类似，入栈和出栈的操作都在表头进行 队列 (Queue) 只允许在表的一端进行插入，而在表的另一端进行册除 一种操作受限的线性表 操作特性：先进先出(FIFO) InitQueue(&Q):初始化队列，构造一个空队列 队列的定义及基本操作 QueueEmpty(Q):判队列空，若队列为空返回 true, 否则返回false EnQueue(&Q,&x): 入队，若队列未满，将x加入，使之成为新队尾 DeQueue(&Q,&x): 出 队，若队列非空，删除对头元素，返回x GetHead(Q &x): 读队头元素若队列非空，则将队头元素赋值给X 入队操作： 队不满时，先送至队尾元素，再将队尾指针+1 队不空时，先取对头元素值，再将队头指针+1 初试状态(队空条件):Q.fron t ==Q.rear==0 队 长 ：rear -front 假上溢：不能用rear=MaxSize 判断队满 front 0 队列的顺序存储结构 队首指针进Q. front= (Q. rear+1)%MaxSize 队尾指针进：Q.rear=(Q. rear+1)%MaxSize 队满条件：Q. rear=(Q. rear+1)%MaxSize= front 队空条件仍：Q.front==Qrear 队列元素个数：( Q.rear+ MaxSize- Q.front)%Maxsize if(Q.rear+1%MaxSize==Q.fron t) return false //判断是否队满 Q. rear=(Q .rear+1)%MaxSize ;// 队尾指针+1取模 if(Q.rear==Q.front) return false;//判断是否队空 出队 x= Q.data[Q. front]; / /元素出队 //对头指针加1取模 缺点：不带头结点的操作比较麻烦 不带头结点的链式存储 rear 链式存储 front ·头指针指向头结点 ·尾指针指向尾结点 带头结点，插入和删除的操作得到统一 front a₁ 带头结点的链式存储 队列的链式存储 s->data = x;s->next =null;//创建新结点，插入到队尾 Q.rear->next = s;// 将rear指针所指的结点的后继指针指向新结点 首先判断是否为空，若不空则队头元素出队，将其从链表中删除；并让front 指向下一个结点 若队列中只有一个结点，则令Q.rear==null &&Q.front==null; if(Q.front==Q.rear) return false; //空队 链式队列的基本操作- p是指向被删除结点的指针 LinkNode*p = Q.front->next; 被删除结点是头结点之后的结点 x=p->next;// 被删除的元素赋值给x Q. front->next= p->next; // 头结点的后继指针指向被删除结点的后面的结点 if( Q.rear ==p) Q.rear=Q.front; // 若原队列只有一个元素，删除后队列为空 输出受限 基础概念 一 允许两端都可以进行入队和出队操作的队列 输入受限 允许一端插入删除，另一端只允许删除 数组的基本概念 特 殊 炬 阵 的 压 缩 存 储 一 数组 稀疏矩阵及其存储方式 · 数组是由n(n≥1)个相同类型的数组元素构成的有限序列，每个数组元素称为一个数组元素，每个元素在n个线性关系中的序号称 为该元素的下标。 基本思想：先行后列，先存储行号较小的元素，行号相等先存储列号较小的元素 按行优先 - LOC(aij)= LOC(a0,0)+[i×(h₂+1)+j]×L LOC(a;ij)=LOC(a0,0)+[j×(h₂+1)+i×L 压缩存储 一 指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间，目的是节省存储空间 特殊矩阵 — 具有许多相同短阵元素或零元素，并且这些相同炬阵元素或零元素的分布具有一定的规律性。例如对称矩阵、上(下)三角炬阵， 对角矩阵 特 殊 矩 阵 的 压 缩 存 储 方 法 — 找 出 特 殊 矩 阵 中 值 相 同 的 矩 阵 元 素 的 分 布 规 律 ， 把 那 些 呈 现 规 律 特 性 分 布 的 、 值 相 司 的 多 个 矩 阵 元 素 存 储 到 一 个 存 储 空 间 中 矩阵中非零元素的个数t, 相对矩阵元素个数5来说非常少，即s>> t的矩阵为稀疏矩阵。例如一个100×100的矩阵，该矩阵中只有少于100个非零元素 0 2 → 5 稀疏矩阵A对应的三元组表示 数组存储 稀疏矩阵的三元组的存储方式 十字链表法存储 概念：串是由零个或多个字符组成的有限序列 ai可以是字母，数字或其他字符 串的定义- 子串的位置是指其在主串中以子串的第一个字符位置表示 例如：有串A='China Beijing’,B='Beijing',C='China, 则它们的长度分别为13,7和5。 B和C是A的子串，B在A中的位置是7,C在A中的位置是1 有一个或多个空格(空格是特殊字符)组成的串成为空串，它不是空串，长度为空格字符的个数 串、数组和特殊矩阵 定长顺序存储表示 十 串的存储结构 类似于线性表顺序存储 用一组连续地址的存储单元存储串值的字符序列，为每个串变量分配一个固定长度存储区，即定长数组 串实际长度<=MAXLEN,超出部分被截断 #define MAXLEN 255 //预定义最大串长为255 typedef strcut{ char cha[MAXLEN]; // 每个分量存储一个字符 int length; //串的实际长度 }sstring; 定长顺序存储表示 树是n(n>=0) 个结点的有限集合。当n=0 时，称为空树。 树的定义是递归的，是一种递归的数据结构 树适合表示具有层次结构的数据。树是一种逻辑结构同时也是一种分层结构。 树的根结点没有前驱除根节点外，所有结点有且只有一个前驱结点 树中所有结点有零个或多个后继结点 根结点 —— 树只有一个根结点 度为0 叶子结点(终端结点) 结点的度 - 一个结点的子节点的个数 度不为0 分支结点(非终端节点) 祖先结点 子孙结点 结点 结点关系 双亲结点 树与二叉树(1) 孩子结点 兄弟结点 基本术语 层次 从树根开始，根结点为第一层 结点的度，高度层次 深度 从根结点开始自顶向下逐层累加 高度 从叶子结点开始自底向上逐层累加 树的度 树中结点最大的度数 树的高度/深度 树中结点的最大层次 树中的结点数等于所有结点的度数加1 树 ② 度为m的树中第i 层上至多有m²-1个结点(i≥1) 树的性质 ③ 高度为h 的 m 叉树至多有(mh-1)/(m-1 )个结点 ④ 具有n 个结点的m 叉树的最小高度为[logm(n(m- 1))+1] 每个结点至多有两棵子树(即二叉树中不存在度大于2的结点),并且二叉树的结点有左右之分 空二叉树 只有一个根结点 二叉树的定义 二叉树的五种形态 只有左子树 二叉树的定义及特点 只有右子树 特殊二叉树 树与二叉树(2) 二叉树的概念 注意：二叉树与度为2的有序树的区别 左右子树都有 满二叉树 — 除叶子结点外，每个结点度数均为2 与其对应满二叉树中编号1~n— 一对应 完全二叉树 特点 一 度为1的结点只能有一个，且该结点只有左孩子没右孩子 二叉排序树 — 左子树的关键字<根<右子树关键字 平衡二叉树一 树上任意结点的左子树和右子树的深度之差不超过1 二叉树可以为空，而度为2的树至少有3个结点 二叉树的结点次序是有序的，而度为2的树左右次序是相对而言的，若某结点只有一个孩子结点，则无需区分左右 非空二叉树上的叶子结点数=度为2的结点数+1 重要公式：n o=nz +1 非空二叉树上第k层上至多有2k-1个结点 ( k≥1)。 高度为h的二叉树至多有2h- 1 个结点 (h≥1)。 对于完全二叉树按从上到下、从左到右的顺序一次编号1,2,...,n, 则有以下关系： 串 二叉树的性质 · 具 有n 个 ( n>0) 结点的完全二叉树的高度为[log₂(n+1)] 或 [logzn]+1。 当 i>1 时，结点 i 的双亲的编号为[i/2], 即当i 为偶数时，其双亲的编号为i/2, 它是双亲的左孩子；当i 为奇数时，其双亲的编号为(i-1)/2, 它是双亲的右孩子 当 2i≤n 时，结点i 的左孩子编号为2i, 否则无左孩子 当 2i+1≤n 时，结点i 的右孩子编号为2i+1, 否则无右孩子 结点i 所在层次(深度)为[logi]+1 若i≤In/2], 则结点i 为分支结点，否则为叶子结点 叶子结点只可能在层次最大的两层出现。对于最大层次中的叶子结点，都一次排列在该层最左边的位置上 若有度为1的结点，则只能有一个，且该结点只有左孩子而无右孩子(重要特征) 按层序编号后，一旦出现某结点(编号为i) 为叶子结点或只有左孩子，则编号大于i 的结点均为叶子结点 若n 为奇数，则每个分支结点都有左孩子和右孩子； 若n 为偶数，则编号最大的分支结点(编号为n/2) 只有左孩子， 没有右孩子，其余分支结点左、右孩子都有 先序遍历 中序遍历 二叉树的遍历(递归方式) 递归 后续遍历 void PreOrder(BiTree T) if (T!= NULL) visit (T ) ; PreOrder (T-> lchild ); PreOrder (T-> rchlid ); 若二叉树为空，则什么也不做，否则 void InOrder( BiTree T) if (T!=NULL) InOrder (T-> lchild ); visit (T ) ; InOrder (T-> rchlid ); } 若二叉树为空，则什么也不做，否则 void PostOrder(BiTree T) if (T !=NULL) PostOrder (T-> lchild ); PostOrder (T-> rchlid ); visit ( T); 若二叉树为空，则什么也不做，否则 访问根结点 先序遍历左子树 先序遍历又子树 中序遍历左子树 访问根结点 中序遍历右子树 后序遍历左子树 后续遍历右子树 访问根结点 根左右 左根右 左右根 void Post0rder(BiTree T) Inistack (S); P = T; while(P ||I StackEmpty(S)) if(P ) printf (p-> data ); push( S,P ); P = P-> Ichild ; pop(S,P); 非 递归 void InOrder(BiTree T) Inistack (S); P = T; while (P||! StackEmpty(S)) if(P) push(S,P); P = P->1child ; e lse pop(S,P ); printf (p-> data ); P = P->rchlid ; 二叉树的遍历(非递归方式及层次遍历) void PostOrder(BiTree T) Inistack( S ); P = T ; while (P||! StackEmpty(S )) if( P ) push(S,P); P = P->lchild ; pop(S ,P ); if (P-> rchild &&(P->rchild).tag ==8) push(S,P); P = P->rchlid ; printf( p->data ); P .tag =1 ; P =NULL; 层次遍历 void Levelorder(BiTree T) InitQueue(Q); //初始化辅助队列 BiTree p; ie (ISsrpby(c)) DeQueue(Q,p); // 队头元素出队 // 访问当前 p 所指向结点 借助一个辅助队列，先将二叉树根节点入队，然后出队，访问该结点 若它有左子树，则左子树根结点入队 若它有右子树，则将右子树根结点入队 ④然后出队，对出队结点访问，如此反复，直到队列为空 线 索 二 叉 树 线 索 二 叉 树 二叉树的线索化是指将二叉链的空指针改为指向前驱或后继的线索 若无左子树，令Ichilid 指向其前驱结点；若无又子树，令rchlid 指向其后继结点 增加两个标志域表面当前指针域所指对象是左右结点还是直接前驱或后继 0, Ichild 指向结点的左孩子 1, Ichild 指向结点的前驱 0,r child 指向结点的右孩子 1, rchild 指向结点的后继 附设指针 pre 指向刚刚访问过的结点，指针指向正在访问的结点，即 pre 指向前驱 在中序遍历的过程中，检指针是否为空，若为空就将它指向pre: 检查 pre 的右指针是否为空，若为就将它指， ① 如果p非空，左子树递归线索化。 如果p 的左孩子为空，则给p加上左线索，将其LTag置为1,让p的左孩子指针指向pre (前驱);否则将p的LTag置为0。 中序遍历对二叉树线索化的递及步骤 如果pre的右孩子为空，则给pre 加上右线索，将其RTag置为1,让pre 的右孩子指针指 向 p( 后继);否则将pre的RTag置为0。 将pre 指向刚访问过的结点p, 即pre =p。 右子树递归线索化。 void InThread(ThreadTree &p,ThreadTree &pre) //中序遍历对二叉树线索化的递归算法 if(p!=NULL) InThread(p->lchild,pre); / / 递 归 ，线索化左子树 if (p-> Ichild == NULL) p->lchild =pre; if(prel=NULL&8pre->rchild==NULL) pre -> rchild = p ; //建立前驱线索的后继线索 //标记当前结点成为刚刚访问过的结点 //递归，线 索 化 右 子 树 主要为访问运算服务 中序线索二叉树 这种遍历不需要借助栈，它结点中包含线索二叉树的前驱和后继信息 ThreadNode *Firstnode(ThreadNode *p) while(p->ltag==θ) p = p -> Ichild ; //最左下结点(不 一 定是叶结点) return ps rchild *线索二叉树的遍历 中序线索二叉树中结点p 在中序序列下的后继结点 ThreadNode *Nextnode(ThreadNode*p) if(p->rtag==0) return FirstNode(p->rchild); else return p-> rchild ; // rta g == 1 直接返回后继线索 不含头结点的中序线索二叉树的中序遍历算法 void InOrder (ThreadNode *T) for(ThreadNode *p=Firstnode(T);p!=NULL;P=Nextnode(p)) visit(p); 树的存储结构 顺序存储 一 链式存储 双亲表示法 - 孩子表示法 — 增设尾指针，指示其双亲结点在数组中的位置。根结点下标为0,伪指针为-1 优 点 ：快速查找双亲结点 O(1) 缺 点 ：求孩子时需要遍历整个结构 每个结点的孩子结点都用单链表链接起来形成一个线性结构 n 个结点就有n个孩子链表(叶子结点的孩子链表为空表) 孩子链表的结点 设置两种结点类型 · 每个孩子链表的表头结点 优点：易于查找孩子结点 缺点：查找双亲麻烦，需要遍历n 个结点中孩子链表指针所指向的n个孩子链表 孩子兄弟表示法(二叉树表示法) 设置两个指针 指向结点的第一个孩子结点 指向该结点的下一个兄弟结点 优点：易于查找孩子结点和兄弟，可以方便地实现树转换为二叉树地操作 缺点：查找双亲麻烦 △ 由于根节点没有兄弟，所以树转换而得的二叉树没有右子树 将森林中的每棵树转换成相应的二叉树 每棵树的根也可视为兄弟关系，在每棵树的根之间加一根连线 以第一棵树的根为轴心顺时针旋转45° 树和森林 二叉树与森林的转换 若二叉树非空，则二叉树的根及其左子树为第一棵树的二叉树形式， 故将根的右链断开。 二叉树根的右子树又可视为—一个由除第一棵树外的森林转换后的二叉树， 森林 应用同样的方法，直到最后只剩一棵没有右子树的二叉树为止 最后再将每棵二叉树依次转换成树，就得到了原森林。 二叉树转换为树或森林是唯一的 二叉树 先根遍历 一 若树非空，先访问根结点，再从左到右的顺序遍历根结点的每棵子树 后根遍历 一 若树非空，按从左到右的顺序遍历根节点的每棵子树，再访问根节点 树的遍历 树的先根追历==二叉树先序遍历 树的后根追历==二叉树中序遍历 访问森林中第一棵树的根结点 先序遍历 一 若森林非空 先序列遍历第一棵树中根结点的子树森林 先序遍历除去第一棵树之后剩余的树构成的森林 参 森林的遍历 中序列遍历第一棵树中根结点的子树森林 森林 二叉树 中序遍历 一 若森林非空 访问森林中第一棵树的根结点 先根遍历 先序遍历 先序遍历 树和森林的遍历&并查集 先序遍历除去第一棵树之后剩余的树构成的森林 森 林 先 序 = =二叉树先序 森林中序=二叉树中序 通常用树(森林)的双亲表示作为并查集的存储结构， 树中的每个结点包含集合的一个元素，每棵树表示一个集合，多个集合形 成一个森林，以每棵树的树根作为集合的代表，树中每个结点有一个指向双亲结点的指针，根结点的双亲结点指针指向其自身。 当给出两个元素的一个无序对(a,b) 时，需要快速“合并”a和b分别所在的集合，这期间需要反复“查找”某元素所在的集 并查集- 在这种数据类型中，n 个不同的元素被分为若干组，每姐是一个集合，这种集合叫做分离集合，称之为并查集 Initials(S): 将集合S中的每个元素都初始化为只有一个单元素的子集合 基本操作 Union(S,Root1,Root2): 把集合S中的子集合Root2 并入子集合Root1 。要 求Root1和Root2 互不相交，否则不执行合并 Find(S,x): 查找集合5中单元素x所在的子集合，并返回该子集合的根结点。 空树(也是二叉排序树) 若非空，左子树结点值<根结点值<右子树结点值 从根节点开始，若二叉树非空，则将给定值key 与根节点的关键字T→data 查找，若相等，查找成功 查找 若不相等，则当根结点的关键字值key 大于给的关键字T→data值时，在根节点的左子树中查找 否则在根结点的右子树中查找 BSTNode *BST_search(BITree T₂ElenType key,BSTNode *Bp) // 查找函数返回指向关罐字薛为 ey 的结点指针， P=NULL; //p 指向被查找结点的双亲，用于颓入和删除燥作中 ihile (TI= NULL 8 key l=T-> data) 若原二叉树为空，则直接插入结点 ②否则，若关键字key小于根结点T→key, 则插入左子树 若关键字k 大于根结点T→key, 则插入右子树 return T; 二叉排序树的非递归查找算法 int BST_Insert(BiTree 8T,KeyType k) if (T= NUL ) //原树为空，断插入的记录为根结点 T =( BiTree)malloc (sizeof(BSTNode )); return 1; else if (k key ) return BST_Insert (T-> 1child,k); return BST_Insert(T-> rchild,k) 二叉排序树插入算法 构造 将二叉排序树T初始化为空树 读入关键字为key的结点 将此结点插入二叉排序树T中 如果读入的关键字key 不是输入结束的标志，循环执行操作 读入关键字为key 的结点 T = NULL; int i = B ; while (ic n) // 依次将每个元素插入 BST_Insert(T₃ str [i]); 二叉排序树的构造算法 二叉排序树的操作- 若结点z只有一棵左子树或右子树，则让z的子树成为z父结点的子树，替代z的位置。 — 三种情况下的删除过程 若结点z有左、右两棵子树，则令z的直接后继(或直接前驱)替代z, 然后从二叉排序树中删去这个直接后继(或直接前驱),这样就 转换成了第一或第二种情况。 二叉排序树查找算法的平均长度主要取决于树的高度 查找效率分析 二叉排序树与二分查找 一 只有左(右)孩子的单支树为O(n) 左右子树高度差绝对值不超过1为O(logzn) 平均性能分析一 维护表的有序性 无需移动结点， 只需修改指针 即可插入和删除 插入删除O(n) 动态查找 定义 树与二叉树的应用(2) 平衡二叉树 操作 规定任意结点的左右子树高度差的绝对值不超过1 空树 左子树、右子树都是平衡二叉树，且左子树和右子树的高度差的绝对值不超过1 平衡因子只能是-1,0,1 LL平衡旋转(右单旋转) —— (b) 图5 . 28 LL 平衡旋转 RR平衡旋转(左单旋转) —— (a) 插入结点前 (b) 插入结点导致不平衡 (e)RR 旋转(左单旋转) 插入 LR平衡旋转(先左后右双旋转) (a) 插入结点前 (b) 插入结点导致不平街 (c)LR 旋转(双旋转) RL平衡旋转(先右后左双旋) (a) 插入结点前 (b) 插入结点导致不平衡 (e)RL 旋转(双旋转) 在平衡二叉树的查找过程与二叉排序树的相同 假设以Nh表示深度为h的平衡二叉树中含有的最少结点数，显然有 查找 有 no=0,ni=1,n₂=2, 并且有 nh =n(h-1)+n(h-2)+1 — ▲ 注意：h为下标 平均查找长度为O(log₂n) 是 一 种含有红属结点的自平衡二叉查找树 — 左子树节应值4根节道≤右子树节尚恤 每个结点或是红色，或是黑色的 叶 结 点 ( 外 部 贴 点 NUL 结 ) 均 是 黑 色 的 每个红色结点的两个子结点一定都是原色的 任意 一 结点到每个叶子结点的路径都包含数量相同的黑结点 — 如果 一 个结点存在黑子结点，那么该结点肯定有两个子结点 从 某 结 点 出 发 ( 不 包 含 该 结 点 ) 的 任 一 简 单 站 径 上 的 黑 色 结点 总 数 称 为 该 结 点 的“ 黑 高 ” ( 通 常 记 为bh), 根 结 点 的bh 就 为 这 棵 红 屏 树 的bh 有 n 个内部结点的红黑树的离度hszlog(n+1) — 红黑树的查找操作时间复杂度-O (logn) 插 入 结 点 的 相 父 结 点 插 入 结 点 红 黑 树 为 空 树 — 把插入结点作为根结点，并把结点设置为照色 探报结点不存在或为薰结点，井且播入 e 的 左 子 结 点 ，5R 表示兄弟结点的右子结点，灰色结点表示它可以是红色也可以是黑色 若的除结点只有 一 个子结点，用子结点替族的除结点 替换结点是红色结点 哈夫曼树的定义 燮 哈夫曼树的构造 树与二叉树的应用(3) 哈夫曼树和哈夫曼编码 哈夫曼树的特点 哈夫曼编码 权 —— 树结点被赋予某种意义的数值 结点的带权路径长度 —— 从根结点到该结点的路径长度*该结点的权值 树的带权路径长度 —— 所有叶子结点的带权路径长度之和WPL 哈夫曼树/最优二叉树 —— WPL最小的二叉树 将这n个结点分别作为n棵仅含有一个结点的二叉树，构成森林F 构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左、右子树， 并且将新结点的权值置为左、右子树根结点的权值之和 将F中删除刚刚选出的两棵树，同时将新得到的树加入F中 重复上述的2,3步骤，直至F中只剩下一棵树为止 每个初试结点最终都成为叶结点，且权值越小的结点到根节点的路径长度越大 ☆ 构造过程中共新建了n-1 个结点，因此哈夫曼树的结点总数为2n-1 固定长度编码 —— 每个字符都用同样位数的二进制表示 可变长度编码 —— 不同位数二进制表示 没有一个编码是另外一个编码的前缀 前缀编码 哈夫曼编码就是前缀码 将每个字符作为一个独立的结点，权值为它出现的频度/次数， 然后构建哈夫曼树 构建过程 ② 所有结点都出现在叶子结点上，用0标记左孩子，1标记右孩子 ③ 按照从根结点走向叶子结点的路径上的1,0来组成编码 图的定义 图由顶点集V和边集E组成，记为G(V,E) G(V,E) 其 中V为顶点集，E为边集 无向图 若E是无向边的有限集合时，则图G为无向图 有向图 若E是有向边(也称为弧)的有限集合时，则图G为有向图 连通 —— 若从顶点V到顶点W有路径存在，则称V和W是连通的 连通图 — 任意两个顶点都是联通的 非连通图 —— 如果一个图中有n个顶点，并且有小于n-1 条边，则此图必是非连通图 连通图 图的定义 极大连通图(连通分量) 是一个子图 是连通的 顶点足够多 极大连通子图包含依附这些顶点的所有边 强连通 —— 从顶点V到W, 和从顶点W到V之间都有路径 ① 连通图的生成树是包含图中的全部顶点的一个极小连通子图 ② 若图中顶点数为n, 则它的生成树含有n-1 条边 ③ 生成树去掉一条边则变成非连通图，加上一条边就会有回路 无向图 —— 度之和=2倍的边数 入度 度 有向图 出度 入读和=出度和=边数 度之和=出度+入度 权和网 —— 每一条边都可以标上具有某种含义的数值，该数值称为该边的权值 稠密图、稀疏图 —— 边数很少的称为稀疏图，反之称为稠密图 路径：顶点到另外一个顶点的序列 路径，路径长度和回路 — 路径长度：路径上边的数目 其他概念 回路(或环):第一个顶点和最后一个顶点相同的路径 简单路径 — 顶点不重复 简单路径，简单回路 简单回路 —— 除第一个顶点和最好一个顶点外，其余顶点不重复出现的回路 距 离 — 从顶点u到顶点v的最短路径存在，则此路径长度为距离；没有则为○ 有向树 — 一个顶点的入度为0,其余顶点的入度均为1的有向图 一维数组存储顶点信息 定义 二维数组存储边或弧信息(即各顶点之间的邻接关系) 1,顶点到另一个的边或弧 A[i][j]= 0,顶点与这个顶点没有边或弧 ① 判断两个顶点是否有边 ② 找到某个顶点的邻接点 ③ 求某个顶点的度=该顶点行/列为1的个数 顺存储结构——邻接矩阵法 ④无向图的邻接矩阵是对称矩阵 可以压缩存储 ① 判断某个顶点是否有弧 邻矩阵的作用 找到某个顶点的临界点 有向图 ③ 该顶点的入度=该列的1的个数 ④该顶点的出度=该行的1的个数 邻接矩阵表示法的空间复杂度为0(n²), 其中有n个顶点 注意 稠密图适用于用邻接矩阵存储 缺点：要确定有多少条边需要按行按列对每个元素进行检测 顶点表 data ( 顶点域)|firstarc(边表头指针) 边表 adjvex (邻接点域)| nextarc (指针域) 度之和=边数=边表中所有顶点和的1/2 无向图 某个顶点的度=该顶点边表里的顶点数 某个顶点的出度=该链出边表的顶点个数 有向图 出度之和=出边表中所有顶点之和 十字链表有向图的一种链式存储结构 十字链表 在十字链表中容易求得顶点的出度和入度 图的十字链表的表示不唯一，但一个十字链表表示确定一个图 邻接多重表是无向图的另外一种链式存储结构 在邻接表中，容易求得顶点和边的各种信息 ▲ 注意：无向图的邻接多重表表示法，每条边只有一个顶点 边表顶点个数=边数 图的遍历 广度优先遍历 深度优先遍历 广度优先遍历类似于树的按层次遍历的过程 从图中某个顶点v 出发，访问v, 并 置visited[v] 的值为 true, 然后将v 进队 队头顶点v出队 依次检查v 的所有邻接点 w, 如果visited[w ]的值为 false, 则访问w, 并置 visited[w] 的值为 true, 然后将w 进队 邻接表：O(IV|+IE|) ① 时间复杂度 · 邻接矩阵：O(IV²|) BFS算法性能分析 · 邻接表 邻接矩阵 BFS算法可以求解单元最短路径问题 邻接表存储 — 表示不唯一 ★ 广度优先生成树 · 邻接矩阵存储 —— 表示唯一 深度优先遍历类似于树的先序遍历，是树的先序遍历的推广 从图中某个顶点v 出发，访问v, 并置visited[v] 的值为true 依次检查v 的所有邻接点 w, 如果visited[w] 的值为 false, 再从w 出发进行递归遍历，直到图中所有顶点都被访问过 算法步骤 注意：若是非连通图，上述遍历过程执行之后，图中一定还有顶点未被访间， 需要从图中另选一个未被访问的顶点作为起始点，重复上述深度优先搜索过程， 直到图中所有顶点均被访问过为止 邻接表：O(IVl+IE|) 邻接矩阵：O(IV|²) DFS算法性能分析 · 空间复杂度 O(IV|) 邻接矩阵 连通图 — 生成深度优先树 非连通图 — 生成深度优先森林 ★ 深度优先生成树和生成森林 邻接表存储 — 表示不唯一 邻接矩阵存储 — 表示唯一 / / 从 顶 点 v 出发，广度优先遍 历 6 ,算 法 借 助 一 个 辅 助 从 列 visit (v); // 访问初始顶点 EnQueue(Q,v ); // 顶 点入 队 while (I QueueEmpty (Q)) DeQueue(Q,v); for (w = FirstNeighbo r(G,v );w>=8;w= NextNeighbo r(G,v,v)) //检测 的所有邻接点 if (1 visited [w]) // 访问顶点w visited [w]= TRUE;/ / 对做已访问顶点标记 广度优先遍历非递归算法 bool visited[MAX_VERTEX_NUM];// 标记访问数组 void DFSTraverse(Graph G) // 对 图 进 行 深 度 优 先 遍 历 ， 访 问 函 数 为v isite() for (v =0; v=0;w= NextNeighbor(G,V₂v)) DFS(G,w) 深度优先遍历递归算法 有向无环图 (DAG) 一个有向图中不存在环或回路，称为有向无环图 活动在顶点上 在AOV网中，不应该出现有向环 ờ 一个活动完成后才能进行下一个活动，具有传递性；任何活动不能以它自己作为自己的前驱或后继 每个顶点只出现一次 拓扑排序的定义 — 若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点A到B的路径 A 注：每个DAG图有一个或多个拓扑排序序列 输出A ① 从AOV图中选择一个入度为0(即没有前驱)的顶点并输出 ② 然后删除此顶点，并删去以此为起点的有向边(删除出度) ③ 重复以上①②步骤，直到所有的顶点都输出或者找不到入度为0(无前驱)的点 ① 从AOV 网中选择一个没有后继(出度为0)的顶点并输出 逆拓扑排序的过程及思想 时间复杂度 O(IV|+|E|) AOE(活动在边上) 以顶点表示事件，以有向边表示活动 边上的权值表示完成活动所需的时间 开始顶点(源点) — 仅有一个入度为0的顶点 — 工程开始 结束顶点(汇点) —— 仅有一个出度为0的顶点 —— 工程结束 概念 关键路径 ，从源点到汇点的所有路径中，具有最大路径长度的路径 关键活动 —— 关键路径上的活动 关键路径的长度 —— 完成整个工程的最短时间 参量的定义 关键路径 ① 时间V(k)的最早发生时间Ve(k) 事件V(k)的最迟发生时间VI(k) 活动ai的最早发生时间e(i) ④ 活动ai的最迟发生时间l(i 一个活动ai的最迟开始事件I(i)和其最早开始时间e(i)的差额 ① 对图中顶点进行拓扑排序，在排序过程中按拓扑排序求出每个事件的最早发生时间Ve(i) 按逆拓扑排序列求AOE网络中每个事件的最迟发生时间vl(i) 求AOE网中每个活动的最早开始时间e(i) 求AOE网中每个活动的最迟开始时间l(i) 找出e(i)=I(i) 的活动ai, 即为关键活动。由关键活动形成的由源点到汇点的每一条路径 就是关键路径，关键路径有可能不止一条。 关键路径上所有的活动都是关键活动，它是决定整个工程的关键因素，因此可通过加快关键 活动来缩短整个工程的工期。但也不能任意缩短关键活动，因为一旦缩短到一定的程度，该 关键活动就可能变成非关键活动。 注意点 关键路径并不唯一，且对于有几条关键路径的网，只提高一条关键路径上的关键活动并不能 缩短整个工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的 查询某个数据元素是否在查找表中 检索数据元素的各种属性 查找基本概念 沪 动态查找元素 — 除了上述两种操作外还需要进行修改和删除数据元素的操作 关键字 — 数据元素中唯一标识该元素的某个数据项的值 ★平均查找长度(ASL) — 所有查找过程中进行关键字比较次数的平均值 无序线性表 — 从 线 性 表 的 一 端 ，逐个检查关键字是否满足给定条件 ①平均时间只与元素存储位置有关 顺序查找 ★ 平均查找长度ASL — (n+1)/2 ▲ 缺点 — 当n比较大时，平均查找长度较大，效率低 typedef struct{ ElemType *elem; // 元素存储空间基址 int TableLen; //当前长度 }SSTable; int seach_seq( SSTable ST,KeyType key) ST.R[0].key - key; // 哨兵 for (i- ST.1ength; ST.R[i]. key!-key;i--) // 从后往前找 return i; // 若表中不存在关键字为key 的元素，将查找到i 为0时退出循环 顺序查找算法 首先将给定值key与表中位置元素的关键之比较 若相等，则查找成功 查找基本思想及过程 key>中间位置 — key< 中间位置 — ① 置查找区间初值，low =1,high =length(表长) ② 当 low ≤high 时，循环执行以下操作： mid 取值为low 和high 的中间值 将给定值key与中间位置记录的关键字进行比较， 若相等则查找成功，返回中间位置皿d 若不相等则利用中间位置记录将表对分成前、后两个子表。如果key比 中间位置记录的关键字小，则high取为mid-1 否则low 取为mid+1 ③ 循环结束，说明查找区间为空，则查找失败，返回0 ① 表顺序表中的中间位置作为根结点 ②左子树根结点==左半边的中间元素 ③ 右子树根结点==右半边的中间元素 比较次数 —— 结点在判定树的层次 查找成功 结点 平均查找长度 比较位置 —— 叶子结点 查找失败 比较次数 —— 结点所在判定树的层次 基本思想 —— 将查找表分为若干子块，块内元素可以无序，但块间是有序的 ① 在索引表中确定待查记录所在的块，可以顺序查找或折半查找 查找过程 · 块内顺序查找 性能介于顺序查找和折半查找之间的一种查找方法 分块查找(索引顺序查找) 平均查找长度 采取顺序查找 — ASL=(s²+2s+n)/2 索引表折半查找 — ASL=[log z(b+1)」+(s+1)/2 在表中插入和删除数据元素时，只要找到该元素对应的块，就可以在该块内进行插入和删除运算 优点 分块查找的优缺点 由于块内是无序的，故插入和删除比较容易，无需进行大量移动 × 缺点—要增加一个索引表的存储空间并对初始索引表进行排序运算 一棵m 阶B树，或为空树，或满足下列条件 树的每个结点至多m 棵子树(即至多含有m-1个关键字) 若根结点不是终端结点(叶子结点),则至少有两棵子树； (至少一个关键字) 除根结点外的所有非终端结点至少有「m/2」 ( 即至少含有「m/2」-1 个关键字) B树的查找和二叉树排序很类似 B树的查找 查找过程 先让等待查找关键字Key和结点的关键字比较，如果等于，则查找成功 若不等于任何一个关键字，则看key处在哪个范围内，然后去对应的指针所指向的子树中查找 如果key比第一个关键字还小，则去它的左边指针所指的子树查找，如果比最后一个关键字还大， 则去它右边指针所指向的子树中查找 取这个关键字数组中的中间关键字[n/2」作为一个新的 结点，然后其他关键字形成两个结点作为新结点的左右孩子 B树的插入 一 分裂的方法 · 插 入 6 后 ，溢 出 结 点 分 裂 20 50 52 插入前 结点分裂示意图 基本操作 被删除关键字k 不在终端结点上时 B树和B+树 505260 插入后，结点溢出 6078 删除 80 B树中删除非终端结点关键字的取代 直接删除关键字 B树的删除 兄弟够借 删除65 被删除的关键字k 在终端结点上时 删除5 兄弟不够借 7486 B+树中，具有n 个关键字的结点只含有n棵子树，即每个关键字对应一棵子树 关键字 B树中，具有n个关键字的结点含n+1棵子树 B+ 树中，每个结点(非根结点)关键字个数 n 的范围 [m/2]<=n<=m 结点范围 B树中，非根结点关键字的个数n的范围[m/2]- 1<=n<=m-1 B+ 树 B树与B+树的区别(重点) B+ 树中，叶结点包含信息，所有非叶结点仅起索引作用，对应存储子树中最大关键字 叶子结点 B树中，叶子结点不包含信息 B+树，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中 关键字 B树中，叶结点包含的关键字和其他结点包含的关键字是不可以重复的 在B+树中有一个指针指向关键字最小的结点，所有叶子结点连接成一个单链表 (Hash) 开放地址法 Hi= (H(key)+di)%m 处理冲突碰撞的方法 特点：冲突发生时，顺序查看表中下一单元，直到找出一个空闲单元或查遍全表 线性探测法 ▲ 缺点：大量元素在相邻地址处堆积“聚集”,降低查找效率 ▲ 缺点：不饿能探测到所有单元造成空闲，但至少能探测到一般单元 设置两个散列函数 再散列法 — Hi=(H(key)+i*Hash2(key)%m 是冲突的次数，初始为0; m 为表长 伪随机序列方法 拉链法(链地址法) 把具有相同散列地址的记录放在同一个单链表中，称为同义词链表 拉链法适用于经常进行插入和删除的情况 与构造散列表过程基本一致 先根据散列函数计算出散列地址，然后看看这个位置有没有关键字 散列表查找 散列查找及性能分析 如果没有，查找失败 如果有，则检查该记录是否等于关键字 装填因子α—— 定义为一个表的装满程度 等于关键字，查找成功 不等于，按照给定的冲突办法计算下一个散列地址，再用该地址重复上 述过程 α=n/m n:表中记录数 m:散列表长度 章 性能分析 越大，说明表越满 查找效率— 取决于散列函数，处理冲突的方法，填装因子α 平均查找长度 —— 取决与装填因子α,而不直接依赖与n (表中记录数)或m ( 散列表长度) 排序思想 — 首先以第一个元素为有序序列，将后面的元素一次插入到有序的序列中合适的为止，直到都插入有序序列 void Insertsort (ElemType A[],int n) 直接插入排序 稳定性 稳定 顺序存储，链式存储的线性表 适合性 注：大部分排序算法仅适用于顺序存储的线性表 排序思想一 将比较和移动操作分离，先找出插入位置，然后统一移动待插入位置的所有元素 void Insertsort (ElemType A[], int n) 代码实现 折半插入排序 mid - (low+high)/2; // 取中间点 if (A[mid] > A[0]) high = mid-1; // 查找左半边子表 else low = mid+1; // 查找右半子表 for (j = i-1; j>= high+1; --j) A[j +1] = A[j]; // 统一后移动元素， 空出插入位置 A[high+1] = A[0]; // 插入操作 性能分析 时间复杂度 稳定性 O(n²) 排序思想 将待排序表分成若干子表，对若干子表分别进行直接插入排序， 当整张表呈“基本有序”时，再对全体记录进行一次直接插入排序 代码实现(不需要掌握) 希尔排序 性能分析 时间复杂度 — 最坏情况下 一 0 (n²) 空间复杂度 — 0(1) — 仅使用了常数个辅助单元 稳定性 一 不稳定 适用性 一 仅适用于线性表为顺序存储的情况 冒泡排序 排序思想 - 代码实现 — 性能分析 两两比较相邻元素的值，若为逆序则交换它们，直到序列比较完，此为第一躺冒泡； 结果是将最小元素交换到待排序序列的第一个位置 多种方法(掌握并且手动实现) 最好情况下 — O(n) 时间复杂度 — 最坏情况下 — O(n²) 平均情况 — O(n²) ② 空间复杂度 — 0(1) — 仅使用常数个辅助单元 稳定性 — 稳定 排序思想 交换排序 快速排序 性能分析 ① 在无序表中选取一个元素作为基准pivot, 通常是第一个元素 ② 设置两个指针low,high分别指向无序表两端 ③ high从右向左找比基准小的元素然后替换low所指向元素 ④l ow从左向右找比基准大的元素然后替换high所指元素 重复步骤②和③,直到low 和high 相等为止。此时low 或 high 的位置即为枢轴在此趟排 序中的最终位置，原表被分成两个子表 void QuickSort(ElemType A[], int low,int high) if (low chigh ) int pivotpos = Partition( A,low,high); QuickSort(A,low,pivotpos- 1); QuickSort (A, pivotpos +1, high ); int Partition(ElemType A[],int low,int high) // 非递归算法 //严版教材的划分算法( 一趟划分过程) ElemType pivot = A[low]; // 将当前表中第一个元素设置为枢纽值，对表进行划分 while(low < high ) while(lowchigh &8A[ high ]>= pivot) high --; A[low]=A[high] ; // 将比枢轴值小的元素移动到左端 while (lowchigh8 8A[low ]<= pivot) low ++; A[high ]=A [low ];// 将比枢轴值大的元素移动到右端 A[low ]= pivot ;/ / 枢轴元素存放到最终位置 return low; // 返回存放枢轴的最终位置 重点掌握 最坏情况下 — O(n²) 时间复杂度 平均情况下 — O(nlogzn) 最好情况下 — O(logzn) 最坏情况下 — O(n) mantey 初始关键字 进 行 3 次 交 换 之 后 进 行 4 次 交 换 之 后 完成一题排序 ( a) 第 一 趋快速排序过程 初始状态 一 趟 排 序 结 二 趟 排 序 结 三 趟 排 序 结 四 越 排 序 结 ( b) 快 速 排 序 的 全 过 程 示例：已知待排序记录的关键字序列为(49,38,65,97,76,13,27,49), 请给出用快速排序法进行排序的过程 平均情况 — O(logzn) 稳定性 — 不稳定 排序思想 — 假设第一个元素为有序表，从后面若干待排序元素中选取关键字最小的元素，与第一个元素比较，交换位置 时间复杂度 — O(n²) 简单选择排序 ② 空间复杂度 —— O(1) 稳定性 —— 稳定(严版教材) 概念 —— 大(小)根堆 双亲>(或<)左右孩子结点 根结点是整个堆中结点最大值或最小值 每次将无序序列调节为一个堆，然后从堆中选择堆顶元素的值 ①把初始序列的完全二叉树调整为一个大顶堆 排序思想 建堆 方法：二叉树由下至上从右到左(数组下标由大到小)检查每个结点是否满足大顶堆的要求，不满足进行调整 将堆顶结点与最后一个结点交换，也就是最大值移动到数组的最末尾，此时第一趟完成 调堆 — 调整二叉树的结点使得满足大根堆的要求，方法和建堆一样 ① 时间复杂度 —— O(nlog₂n) ② 空间复杂度 —— 0(1) —— 仅使用常数个辅助单元 性能分析 ③ 稳定性 —— 不稳定 适用性 —— 初始建堆所需的比较次数较多，因此记录数较少时不宜采用，当记录较多时较为高效 排序思想 代码实现 — 冒泡排序 性能分析 两两比较相邻元素的值，若为逆序则交换它们，直到序列比较完，此为第一躺冒泡； 结果是将最小元素交换到待排序序列的第一个位置 多种方法(掌握并且手动实现) 最好情况下 一 O(n) 时间复杂度 最坏情况下一 O(n²) 平均情况 — O(n²) 空间复杂度 一 0(1) — 仅使用常数个辅助单元 稳定性 一 稳定 prvotkey 排序思想 交换排序 在无序表中选取一个元素作为基准pivot, 通常是第一个元素 设置两个指针low,high分别指向无序表两端 high从右向左找比基准小的元素然后替换low所指向元素 low从左向右找比基准大的元素然后替换high所指元素 重复步骤②和③,直到low和high相等为止。此时 low 或high 的位置即为枢轴在此趟排 序中的最终位置，原表被分成两个子表 初 始 关 健字 进 行 1 次 交 换 之 后 进行2次交换之后 进行3次交换之后 进行4次交换之后 完成一趟排序 初始状态 一 趟 排 序 结 果 二 趟 排 序 结 果 三趟排序结果 四趟排序结果 97 76 o m 38 6 5 38 ( a) 第一趟快速排序过程 (27 38 13)49 (76 9765 491 13 27 38 49 ( b) 快速排序的全过程 示例：已知待排序记录的关键字序列为(49,38,65,97,76,13,27,49), 请给出用快速排序法进行排序的过程 快速排序 代码实现 void QuickSor t(ElemType A[], int low,int high) if(low chigh) int pivotpos = Partition(A,low,high); QuickSort (A, low,pivotpos -1); QuickSort (A, pivotpos +1,high ); int Partition(ElemType A[],int low,int high) //严版教材的划分算法( 一 趟划分过程) ElemType pivot = A[lom];// 将当前表中第一个元素设置为枢纽值，对表进行划分 while(low < high) while(lowchigh 88A[high ]>=pivot) A[low]=A [hig h];// 将比枢轴值小的元素移动到左端 while(lowchigh& BA[low ]<=pivot) low +; A[high ]=A[ low ]; //将比枢轴值大的元素移动到右端 A[ low ]= pivot ;/ / 枢 轴 元 素 存 放 到 最 终 位 置 return low; // 返 回 存 放 枢 轴 的 最 终 位 置 性能分析 重点掌握 时间复杂度 空间复杂度 最坏情况下 — O(n²) 平均情况下 — O(nlogzn) 最好情况下 — O(logzn) 最坏情况下 — O(n) 平均情况 — 0 (logzn) 云上印： 关注公众号【考研小舟】 免费考研资料&无水印PDF 黑白&彩印都是5分/页，满4.9全国包邮 下单备注：考研小舟，送草稿纸 算法 直接插入 冒泡 选择 希尔 快速 堆 归并 基数 时间复杂度 最好 O(n) O(n) O(n²) O(nlogn) O(nlogn) O(nlogn) O(d(n+rd)) 平均 O(n²) O(n²) O(n²) O(nlogn) ~0(n²) O(nlogn) O(nlogn) O(nlogn) O(d(n+rd) 最坏 O(n²) O(n²) O(n²) O(nlogn) ~O(n²) O(n²) O(nlogn) O(nlogn) O(d(n+rd) 空间复杂度 O(1) O(1) O(1) O(1) O(logn) O(1) O(n) O(rd) 稳定性 是 简单 简单 复杂 复杂 否 复杂 复杂 复杂 n较小 (n<= 50) n² 和nlog₂n的差别不大 直接插入排序 简单选择排序 排序算法总结 内部排序算法的比较及应用 内部排序算法的应用 看待排序元素数目n 的大小 ② n 较大 — 采用时间复杂度为O(log₂n)的排序算法 n很大 一 — 记录的关键字位数较少 —— 基数排序 ① 直接插入 — 比较次数更少，最常用，性能最佳 待排序序列基本有序 冒泡排序 最好的排序方法 待排序的关键字随机分布 —— 快速排序 一次循环就能确定一个元素的最终位置 ④ 就辅助空间而言 —— 堆排序<快速排序<归并排序 快速排序 堆排序 归并排序 与初始状态有关 与初始状态无关 交换类的排序 —— 冒泡排序 ① 直接插入排序 简单选择排序 基数排序 如果参与排序的数据量特别大，存放在外村文件中，一次不能全部读入内存，用内排方法就不能完成对数据的整体排序 外部排序基本概念 为此采用分段处理，每次将文件中一部分数据调到内存中进行排序，这样在排序过程中需要进行多次的内、外存之间的数据交换，这种排序称为外排序。 如何得到初始的归并段一 — 置换选择排序：解决排序段放入内存的问题 内存容量无法容纳大量的数据 多路归并排序 — 如何减少多个归并段的归并次数 — 最佳归并数：最少的归并次数 如何每次m路快速的最小关键字一 败者树：减少比较次数 置换选择排序 是在树形选择排序的基础上得来的，它的特点是：在整个排序(得到所有初始归并段)的过程中，选择最小(或 最大)关键字和输入、输出交叉或平行进行 不同的归并方案所对应的归并树的带权路径长度各不相同，为了使总的读写次数达到最少，需要改变归并方案，重新组织归并 树，使其路径长度WPL尽可能短。所有归并树中最小带权路径长度WPL的归并树称为最佳归并树。 最佳归并树是带权路径长度最短的k次(阶)哈夫曼树，构造过程如下： 若(m-1)mod(k-1)≠0, 则需附加(k-1)-(m-1)mod(k-1) 个长度为0的虚段，以使每次归并都可以对应k个段。 按照哈夫曼树的构造原则(权值越小的结点离根结点越远)构造最佳归并树。 外部排序算法 最佳归并树 38 此归并树的带权路径长度WPL=38×1+(13+16+20+24+30)×2+(7+9)×3+(1+3+5)×4=328, 在归并过程中总的读写记录次数为2×WPL=656。 166 一棵3路最佳归并树 注 ：同样一组初始归并段，采用的归并路数也相同，但选择不同的归并方案，读写记录次数可能是不相同的，但是最佳归并树对 应的归并方案是读写记录次数最少的。 败者树是一棵有k个叶子结点的完成二叉树(可将大根堆看成胜者树) 叶子结点存储的各个归并段当前参与归并的记录，分支结点存放关键字对应的段号，内部结点存储的则是左右子树当中的失败者 多路平衡归并和败者树 对k 个有序段进行k路平衡归并的方法如下： 取每个输入有序段的第一个记录作为败者树的叶子结点，建立初始败者树：两两叶子结点进行比较，在双亲结点中存放比较的败 者(关键字较大者),而让胜者去参加更高一层的比赛，如此在根结点之上胜出的“冠军”是关键字最小者。 将胜出的记录写至输出归并段，在对应的叶子结点处补充其输人有序段的下一个记录，若该有序段变空，则补充一个大关键字 (比所有记录关键字都大，设为kmax)的虚记录。 调整败者树，选择新的关键字最小的记录：从补充记录的叶子结点向上和双亲结点的关键字比较，败者留在该双亲结点，胜者继续 向上，直到树的根结点，最后将胜者放在根结点的双亲结点中。 --- 表格 1 --- ③ 控制器 组成 ④输入设备 | 0 程序计数器PC ② 指令寄存器IR ③ 控制单元CU | 与MAR有直接通路 OP(IR)→cU AD ( IR) 一MAR --- 表格 2 --- 0 取指 ② 译码 | (PC)→MAR,M(MAR)→MDR,(MDR)→IR (PC)+1→PC OP(IR) →CU、Ad(IR)→MAR 计算机的工作过程 | ③ 间址 ④ 执行 ⑤ 中断 0 | M(MAR)→MDR, (MDR)→X (ACC)+(X)→ALU→ACC 检查是否中断、有则保存断点、执行中断隐指令、跳转到 中断服务程序 高级语言机器 --- 表格 3 --- DRAM 分类 MROM PROM EEPROM | 集中：用一段固定的时间依次对存储器的所有行逐一刷新 刷新 分散：把对每一行刷新的时间分散到各个工作周期中去 异步：把每行刷新分散到一整个刷新周期中去 在芯片制造商生产过程中直接写入，以后任何人都无法改变其内容 允许用户用专门的设备写入程序，写入后的内容无法改变 允许用户写入程序，用户可以对其内容进行多次改写；需要修改 时，要将其全部擦除(不可局部擦除) 和EPROM运行原理一样，但是既可以局部擦除，又可以全部擦除 --- 表格 4 --- 虚拟空间 | 虚拟地址=虚页号+页内地址 空间划分 主存地址 | 实地址=实页号+页内地址 页式存储器 | 虚实地址的变换 页表 | 虚实地址的变换 页表 | 虚实地址的变换由页表来实现，页表在主存中 记录：虚页号与实页号的对照信息、装入信息 变换后的实地址：实页号+页内地址 --- 表格 5 --- 概念：一条指令就是机器语言的一个语句，它是一组有意义的二进制代码。 | 概念：一条指令就是机器语言的一个语句，它是一组有意义的二进制代码。 基本格式 操作码 | 指出指令中该指令应该执行什么性质的操作和具体有何种功 能。如加法、减法、移位等 | 操作码 地址码 地址码 | 也称为操作数字。用来指明改指令的源操作数的地址、结果 的地址以及下一条指令的地址。 指令格式 | 定长操作码 在指令的最高位部分分配固定的若干位(定长)表示操作码 ★ 扩展操作码 全部指令的操作码字段的位数是不固定的 | 定长操作码 在指令的最高位部分分配固定的若干位(定长)表示操作码 ★ 扩展操作码 全部指令的操作码字段的位数是不固定的 --- 表格 6 --- CISC ( 复杂指令系统计算机) | 指令数目多、字长不固定；寻址方式多、寄存器数量少、一般为 微程序控制 CISC和RISC的基本概念 | RISC ( 精简指令系统计算机) | 指令书目少，字长固定；寻址方式少，寄存器数量多，一般为组 合逻辑控制 --- 表格 7 --- 指令控制 操作控制 | 完成指令，分析指令，和执行指令的操作，即程序的顺序控制 取到指令后，应该产生完成每条指令所需要的控制命令 功能 | 时间控制 数据加工 | 控制命令产生后，需要对各种控制命令加以时间上的控制 在执行过程中，对数据进行算术运算和逻辑运算 --- 表格 8 --- 0 故障 | 在引起故障的指令启动后、执行结束前被检测到的异常事件。例如，指令译码时，出现“非法操作码“ 自陷也称陷阱或者陷入，它是预先安排的一种“异常”事件。通常是事先在程序中用一条特殊指令或设定特殊控 制标志来人为设定陷阱，当执行道被设置的陷阱的指令时，CPU在执行完自陷指令后，自动根据不同的陷阱 类型进行相应的处理，然后返回道自陷指令的下一条指令执行。 异常的分类 | ② 自陷 | 注意：当自陷指令是转移指令时，并不是返回到下一条执行指令，而是返回到转移目标指令执行 --- 表格 9 --- SIMD是指一个指令流同时对多个数据流进行处理，一般称为数据级并行技术。这种结构的计算机通常 单指令流多数据流((SIMD)结构 由一个指令控制部件、多个处理单元组成。 多处理器基本概念 | 多指令流单数据流(MISD)结构 MISD是指同时执行多条指令，处理同一个数据，实际上不存在这样的计算机。 多指令流多数据流(MIMD)结构 MMD是指同时执行多条指令分别处理多个不同的数据，MIMD分为多计算机系统和多处理器系统 --- 表格 10 --- 结构冒险(资源冒险) | 前一指令访存时，使后一条相关指 令(以及其后续指令)暂停一个时钟 周期。 结构冒险、数据冒险和控制冒险的处 理 | 解决方法 | 单独设置数据存储器和指令存储器， 使取数和取指令操作各自在不同的存 储器中进行。事实上，现代计算机都 引入了Cache 机制，而UI Cache通常 采用数据Cache和指令Cache分离的 方式，因而也就避免了资源冲突的发 生。 数据冒险(数据冲突) 控制冒险(控制冲突) | 指令通常是顺序执行的，但是在遇到 改变指令执行顺序的情况，例如执行 转移、调用或返回等指令时，会改变 PC值，会造成断流，从而引起控制冒 险。 对转移指令进行分支预测 预取转移成功和不成功的两个控制流 方向上的目标指令 加快提前形成条件码 | 指令通常是顺序执行的，但是在遇到 改变指令执行顺序的情况，例如执行 转移、调用或返回等指令时，会改变 PC值，会造成断流，从而引起控制冒 险。 对转移指令进行分支预测 预取转移成功和不成功的两个控制流 方向上的目标指令 加快提前形成条件码 --- 表格 11 --- 主存地址计数器 传送长度计数器 数据缓存寄存器 组成 DMA请求触发器 | 存放要交换的主存地址 用来记录传送数据的主存地址 用于暂存每次传送的数据 I/O设备准备好数据后使DMA请求触发器置位 --- 表格 12 --- 控制/状态逻辑 由控制和时序电路及状态标志完成 | 控制/状态逻辑 由控制和时序电路及状态标志完成 DMA方式 | 中断机构 数据块传送完毕后触发中断机构，提出CPU对主存的访问 停止CPU访存 当需要传送数据时，停止CPU对主存的访问 | 中断机构 数据块传送完毕后触发中断机构，提出CPU对主存的访问 停止CPU访存 当需要传送数据时，停止CPU对主存的访问 传送方式 | 周期挪用 I/O设备需要访存时，挪用一个或几个存取周期 | 周期挪用 I/O设备需要访存时，挪用一个或几个存取周期 DMA与CPU交替访存 | 将CPU周期分为DMA访存和CPU访存两个部分， 适用于CPU的工作周期比主存周期长的情况 --- 表格 13 --- 预处理 | DMA传送之前要进行初始化，完成寄存器置初始值、设置传 送方式之类的工作 传送过程 | 数据传送 | 占有总线传输数据，数据传输完全由DMA控制 DMA后处理 | CPU执行中断服务程序做结束DMA处理 --- 表格 14 --- 硬实时操作系统 | 必须在严格的规定时间内完成处理 实时操作系统 | 软实时操作系统 | 能接收偶尔违反时间规定 --- 表格 15 --- 进程控制和管理信息 一 进程当前状态/优先级 PCB进程控制块 资源分配清单 — 代码段/数据段/堆栈段指针文件描述符键盘/鼠标 进程的组成 处理机相关信息 通用/地址/控制/标志寄存器值状态字 --- 表格 16 --- 进程的状态与转换 | 就绪态→运行态 一 | 进程被调度 运行态→就绪态 一 | 时间片到/cpu 被高优先级进程抢占 运行态→阻塞态 | 等待系统资源分配/等待某事件发生(主动行为) 状态转换 阻塞态→就绪态 一 | 资源分配到位/等待的事件发生(被动行为) 创建态 → 就绪态 一 | 系统完成创建进程相关工作 运行态→终止态 一 | 进程运行结束/运行过程中遇到不可修复的错误 --- 表格 17 --- 先来先服务 (FCFS) 短作业优先 (SJF) 高响应比优 先 (HRRN) 时间片轮转 | 规则 按到达的前后 顺序进行服务 运行时间短的 优先得到服务 响应比高优先 | 是否可抢占 非抢占式 非抢占式， 最短剩余时 间 优 先SRTN 为抢占式 非抢占式 | 评价 对长作业有利 对短作业不利 有最短的平均等 待时间和平均周 转时间；对短时 间作业有利，对 长作业时间不利 等 待 时 间 相 同 时，短作业优先； 服 务 时 间 相 同 时，等待时间长 的优先 适用于分时操作 系统；不区分任 务紧急程度 | 考虑等待 /运行时间 等待时间√ 运行时间x 等待时间X 运行时间√ 等待时间× 运行时间 先来先服务 (FCFS) 短作业优先 (SJF) 高响应比优 先 (HRRN) 时间片轮转 | 各进程执行 一 抢占式 个时间片 | 各进程执行 一 抢占式 个时间片 | 评价 对长作业有利 对短作业不利 有最短的平均等 待时间和平均周 转时间；对短时 间作业有利，对 长作业时间不利 等 待 时 间 相 同 时，短作业优先； 服 务 时 间 相 同 时，等待时间长 的优先 适用于分时操作 系统；不区分任 务紧急程度 | 考虑等待 /运行时间 等待时间√ 运行时间x 等待时间X 运行时间√ 等待时间× 运行时间 --- 表格 18 --- 基本概念 调度层次 调度算法的评级指标 导致饥馈 进程调度时机 调度算法 | 按照某种算法选择一个进程将处理机分配给它 内容 按盟某种规 业调度) 则，从后备队 的作业将其调 入内存，并为 其创建进程 外存→内存 存调度) 则 ，从挂起队 列中选择合适 的进程将其数 指调回内存 低级调度 按 照 某 种 规 则 ，从就绪态 队列中选择一 个 进程为其分 配处理机 进程正常/异常终止 主动放弃 主动阻塞(如等待/O中断) 时间片用完 被动放弃 有更紧急的事情需要处理(如I/O中断) 更高优先级进入就绪队列 处理中断的过程中 进程在操作系统内核临界区中，内核程序临界区一般用来访问某种数据结构，如进程的就绪队 不能进行进程调度 列(由各就绪进程的PCB组成)(进程处于临界区时不能进行处理机调度，进程在普通临界区中是可以进行调度切换的) 原子操作过程中(原语) --- 表格 19 --- 互斥条件 不剥夺条件 请求和保持条件 循环等待条件 | 争抢互斥使用的资源 进程保持的资源只能主动释放不能强行剥夺 保持某些资源不放的同时请求别的资源 存在进程资源循环等待链 --- 表格 20 --- 资源剥夺法 | 挂起某些死锁进程并抢占资源分配给其他死锁进程 解除死锁允许死锁发生 | 撤销进程法 | 强制撤销部分甚至全部并剥夺资源 进程回退法 | 让一个或多个进程回退到足以避免死锁的地步 --- 表格 21 --- 空间按照程序自身的逻辑关系划分为若干个段，再将各段分为大小相等的页面 分段+分页 | 将内存空间分为与页面大小相等的一个个内存块，系统以块为单位为进程分配内存 逻辑地址结构：(段号，页号，页内偏移量) 段表、页表 | 每个段对应一个段表项。各段表项长度相同，由段号(隐含)、页表长度、页表存放地址组成 每个页对应一个页表项。各页表项长度相同，由页号(隐含)、页面存放的内存块号组成 段页式存储管理 地址变换 | 由逻辑地址得到段号、页号、页内偏移量 段号与段表寄存器中的段长度比较，检查段号是否越界 由段表始址、段号找到对应段表项(第一次访存：查段表) ④根据段表中记录的页表长度，检查页号是否越界 由段表中的页表地址、页号得到查询页表，找到相应页表项(第二次：查页表) ⑥由页面存放的内存块号、页内偏移量得到最终的物理地址 访问目标单元(第三次访存) --- 表格 22 --- 设备控制表 (DCT) 控制器控制表 (COCT) 设备分配管理中的数据结构 通道控制表 (CHCT) 系统设备表 (SDT) | 每个设备对应一张 DCT 关键字段：类型/标识符/状态/指向COCT的指针/等待队列指针 每个控制器对应一张COCT 关键字段：状态/指向CHCT的指针/等待队列指针 每个控制器对应一张CHCT 关键字段：控制器表首址/状态等待队列指针 每个设备对应一个表目，记录整个系统中所有设备的情况 关键字段：设备类型/标识符/DCT/驱动程序入口 --- 表格 23 --- 数字数据→数字信号 (编码数字发送器) f 采用频率≥2f 信号最高频率 | 曼彻斯特编码 差分曼彻斯特编码 1: 先1后0 ④ 曼彻斯特编码 0: 先0后1 1: 前半个码元的电平与上个码元的 后半个部分相同 ⑤差分曼彻斯特编码 0: 相反 ⑥ 4B/5B编码 --- 表格 24 --- 信 遒 空 闲 马上发 马上发 p概率马上发，1-p概 | 信遒忙 继续持续监听 放弃监听，等一个随机时间再监听 放弃监听，等一个随机时间再监听 --- 表格 25 --- 接收端与发送端时钟同步 前同步码7B: 迅速实现MAC帧的比特同步 帧开始定界符1B: 后面的信息就是MAC帧 MAC帧不需要帧结束符，以太网在传送帧时，各帧之间必须有一定的间隙 DIX EthernetV2 | ② 地址 | 填入6B MAC地址 ③ 类型 | 占 2B, 指出数据域中携带的数据应该交给哪个协议实体处理 46~1500 B,CSMA/CD 要求以太网帧必须满足最 小长度64B,MAC 首尾部长度18B, 最大的1500 标准 | ④数据 ⑤填充 | 0-46 B, 达到64B最小长度 ⑥校验码 | 校验包括：目的地址、源地址、类型、数据、不校验前导码 --- 表格 26 --- 100BASE-T以太网 | 指出全双工/半双工，在全双工方式下无冲 标 准 ：IEEE 802.5 --- 表格 27 --- 0 提供差错检测但不提供纠错功能，只保证无差错接收(通过硬件进行CRC校验) ② 不可靠的传输协议，不使用序号和确认机制 特点 | 3 只支持全双工链路，只支持点对点的链路通信，不支持多点线路 ④ 两端可以运行不同的网络协议，但仍可使用同一个PPP进行通信 面向字节，当信息字段出现于标志字段一致的比特组合时，PPP有两种处理方法： 异步线路(默认)采用字节填充法；SONET/SDH同步线路用硬件来完成比特填充 | 一个将IP数据报封装到串行链路(同步串行/异步串行)的方法 组成部分 | 链路控制协议LCP:建立并维护数据链路连接 --- 表格 28 --- 0 全双工通信，有较高的数据链路传输效率 特点 ② 所有帧采用CRC检验，对信息帧进行顺序编号，可防止漏发或重发，传输可靠性高 非平衡配置 一个主站控制整个链路工作 链路配置 | 链路两端两个站都是复合站，每个复合站可以平等的发起数据传输而不需要得 平衡配置 到对方复合站的许可 --- 表格 29 --- 正常响应方式 | 非平衡结构操作方式，主站向从站传输数据，从站进行响应传输，但 从站只有收到主站的许可后才可进行响应 数据操作方式 | 异步平衡方式 | 平衡结构操作方式，每一个复合站都可以进行对另一站的数据传输 HDLC协议 | 异步响应方式 | 平衡结构操作方式，从站在没有接到主站的允许下就可以进行传输 --- 表格 30 --- 和转发 不保证分组有序达到 不保证通信可靠，可靠性由用 户主机保证 | 同一路由转发 保证分组有序达到 可靠性由网络保证 --- 表格 31 --- 特 定值 全 1 全0 全1 非全0/1 | 不可以 不可以 不可以 不可以 可以 | 可以 可以 不可以 可以 可以 | 表示本网内某特定主 本网广播地址(路 由器不转发) 网络地址，表示一 个网络 直接广播地址，对 特定网络上的所有 主机进行广 播 用于本地软件环回 测试 --- 表格 32 --- 子网划分 子网掩码 | 由一串1(对应网络号和子网号)和跟随的一串0(对应主机号)组成 子网的网络地址=IP地址&&子网掩码 --- 表格 33 --- 一般形式 地址表示形式 压缩形式 单播地址 基本地址类型 多播地址 任播地址 双栈协议 IPv6和IPv4过渡策略 隧道技术 单播 ① IP数据报三种传输方式 广播 组播 | 冒号十六进制记法 :000A:→ :A: 一对一通信 多对多通信 一对多中的一个通信 | 可做目的地址+源地址 可做目的地址 可做目的地址 一般形式 地址表示形式 压缩形式 单播地址 基本地址类型 多播地址 任播地址 双栈协议 IPv6和IPv4过渡策略 隧道技术 单播 ① IP数据报三种传输方式 广播 组播 | 同时启用IPv4 协议栈和IPv6协议栈 路由器：不同接口上配置了IPv4和IPv6地址 计算机：同时拥有IPv4和IPv6地址 将整个IPv6数据报封装到IPv4数据报的数据部分 点对点 点对多点 点对多点 | 同时启用IPv4 协议栈和IPv6协议栈 路由器：不同接口上配置了IPv4和IPv6地址 计算机：同时拥有IPv4和IPv6地址 将整个IPv6数据报封装到IPv4数据报的数据部分 点对点 点对多点 点对多点 --- 表格 34 --- 局域网上的硬件组播 ③ 两种情况 因特网范围内组播 功能 ④ 网际组管理协议IGMP 工作阶段 | TCP/IP协议使用的以太网多播地址范围：01-00- 5E-00-00-00 到01-00-5E-7F-FF-FF 组播IP地址与以太网硬件地址映射关系不唯一，主 机在IP层利用软件过滤非自身接收数据报 数据在传送路径分岔时(利用组播路由器)才将分 组复制后继续转发 最后阶段将组播数据报在局域网上用硬件组播交 付给组播组的所有成员 让连接在本地局域网上的组播路由器知道本局域网 上是否有主机参加或退出了某个组播组 主机加入向组播组的组播地址发送一个IGMP报 0 文，组播路由器收到利用组播路由选择协议将这 组成员关系发给因特网上的其他组播路由器 本地组播路由器周期性探寻本地局域网上的主 ② 机，只要有一个主机对某个组响应则认为活跃，否 则不再将这组成员关系发给其他组播路由器 --- 表格 35 --- 功能 找出以源主机为根节点的组播转发树 ⑤ 组播路由选择协议 | 不同的多播组对应于不同的转发树；同一个多播组，对不同的原点也有不 同的多播转发树 --- 表格 36 --- 归属代理(本地代理) | 在归属网络中代表移动节点执行移动管理功能的实体 相关术语 | 外部代理(外地代理) | 在外部网络中帮助移动节点完成移动管理功能的实体 永久地址(归属地址/主地址) | 移动站点在归属网络中的原始地址 转交地址(辅地址) | 移动站点在外部网络使用的临时地址 --- 表格 37 --- 端口号 | 应用程序 | FTP | TELNET | SMTP | DNS | TFTP | HTTP | SNMP 熟知端口号 | 21 | 23 | 25 | 53 | 69 | 80 | 161 --- 表格 38 --- 主动打开 | CLOSED | CLOSED | 被动打开 SYN-1,seg=x LISTEN SYN- SENT --- 表格 39 --- 传 输 层 ( TCP 协 议 ) TCP 连 接 管 理 | 服务端为该TCP连接分配缓存和变量，并向服务器端返回确认报字段，SYN和 ACK标志位被置为1,确认号字段为x+1, 并随机产生起始序号seq=y ( 确 认报文不携带数据，但要消耗一个序号) 客户端为该TCP连接分配缓存和变量，并向服务器端返回确认的操作，ACK标 ③ 志位置为1,序号字段为x+1, 确认号字段为y+1 ( 可携带数据，不携带数据 则不消耗序号) | 服务端为该TCP连接分配缓存和变量，并向服务器端返回确认报字段，SYN和 ACK标志位被置为1,确认号字段为x+1, 并随机产生起始序号seq=y ( 确 认报文不携带数据，但要消耗一个序号) 客户端为该TCP连接分配缓存和变量，并向服务器端返回确认的操作，ACK标 ③ 志位置为1,序号字段为x+1, 确认号字段为y+1 ( 可携带数据，不携带数据 则不消耗序号) | 服务端为该TCP连接分配缓存和变量，并向服务器端返回确认报字段，SYN和 ACK标志位被置为1,确认号字段为x+1, 并随机产生起始序号seq=y ( 确 认报文不携带数据，但要消耗一个序号) 客户端为该TCP连接分配缓存和变量，并向服务器端返回确认的操作，ACK标 ③ 志位置为1,序号字段为x+1, 确认号字段为y+1 ( 可携带数据，不携带数据 则不消耗序号) | 服务端为该TCP连接分配缓存和变量，并向服务器端返回确认报字段，SYN和 ACK标志位被置为1,确认号字段为x+1, 并随机产生起始序号seq=y ( 确 认报文不携带数据，但要消耗一个序号) 客户端为该TCP连接分配缓存和变量，并向服务器端返回确认的操作，ACK标 ③ 志位置为1,序号字段为x+1, 确认号字段为y+1 ( 可携带数据，不携带数据 则不消耗序号) 客户 A | 服务器 主动关闭 | ESTAB- LISHED | 数据传送 ESTAB- LISHED | 通知 应用 进程 --- 表格 40 --- 24 20 sshresh的初始值16 新的ssthresh 值12 慢开始 | 拥塞避免 “加法增大” “乘法减小” 快恢复 慢开始 12 | 收到3个重复的确认 执行快重传算法 拥塞避免 TCP Reno版本 “加法增大” TCP Tahoe版本 (已废弃不用) 传输轮次 14 16 18 20 --- 表格 41 --- 应用程序 | FTP数据连接 | FTP控制连接 | TELNET | SMTP | DNS | TFTP | HTTP | POP3 | SNMP 常见应用层协议 | 使用协议 | TCP | TCP | TCP | TCP | UDP | UDP | TCP | TCP | UDP 熟知端口号 | 20 | 21 | 23 | 25 | 53 | 69 | 80 | 110 | 161 --- 表格 42 --- 根域名服务器 ② 本地域名服务器 dns.xyz.com 递归 查询 ① | 顶级域名服务器 dns.com ④ 权限域名服务 dns.abc.com ⑧ vabe. com的P 地址 需要查找y.abc.com的IP地址 --- 表格 43 --- 根域名服务器 ② 本地域名服务器 dns.xyz.com 递归 查询 ① | 迭代查询 ③ ④ ⑥ | 顶级域名服务器 dns.com ⑤ 权限域名服务 dns.abc.com 根域名服务器 ② 本地域名服务器 dns.xyz.com 递归 查询 ① | ⑦ ⑧ | ⑦ ⑧ 根域名服务器 ② 本地域名服务器 dns.xyz.com 递归 查询 ① | y.abc.com的IP地址 需要查找y.abc.com的IP地址 | y.abc.com的IP地址 需要查找y.abc.com的IP地址 --- 表格 44 --- 域名解析过程 递归查询 | 本地域名服务器向根域名服务器查询时，根域名 服务器要么给出所查询的IP地址，要么告诉本地 域名服务器下一步去哪个域名服务器进行查询 迭代查询 | 本地域名服务器只需要向根域名服务器查询一 次，后面几次查询都在其他域名服务器之间进行 --- 表格 45 --- 网的范围内具有唯一的标识符URL 应用层(万维网) | 同一资源定位符 (URL) 超文本传输协议HTTP | 一般形式：<协议>://<主机>:<端口>/<路径> 运行在TCP之上，使用80端口 客 户 链接到URL的超链 浏览器程序 服务器程序 CHTTP使用此TCP连 接 因特网 ……建立TCP连接… ①请求文档 HTTP 请求报文 ②响应文档 ① 浏览器分析URL ② 浏览器向DNS请求解析IP地址 ③ DNS解析出IP地址 操作过程 ④ 浏览器与该服务器建立TCP连接 浏览器发出取文件命令 6服务器响应并发送文件 释放TCP连接 浏览器解释文件并显示Web页面 HTTP无状态协议 特点 Cookie是存储在用户主机的文本文件 HTTP协议本身无连接 | 服务器 --- 表格 46 --- 持节连接 (Keep-alive) 传 输Web 页面 | 发起 ACK+HTTP 请求 | 回应 SYN+ACK 传 输Web 页面 --- 表格 47 --- p->next =q->next q->next->prior =p free(q) | //将要删除的结点的前驱结点的后继指针指向要删除结点的后继指针 //将要删除结点的后继结点的前驱指针指向删除结点的前驱结点 // 释放结点内存 --- 表格 48 --- 堆分配存储表示 一 仍然以一组地址连续的存储单元存放串值的字符序列，但其存储空间在程序执行过程中动态分配得到的 块链存储表示 一 类似于线性表的链式存储结构，每个结点可以存放一个字符也可以存放多个字符 StrAssign(&T,chars) — 赋值操作，把串T赋值为chars StrCopy(&T,S) — 复制操作，由串5复制得到串T StrCompare(S,T) — 比较操作，S>T,返回值大于0; S=T, 返回值=0; S lchild !=NULL) EnQueue(Qp,-> lchild ); if( p->rchild !=NULL) EnQueue(Q,p->rchlid ); | // 若左子树不空，则左子树入队 // 若右子树不空，则右子 树入队 --- 表格 50 --- 树和二叉树的转换 | 每个结点左指针指向它的第一个孩子结点 右指针指向它在树中的相邻兄弟结点 --- 表格 51 --- 简单图 相对 | 不存在重复的边 不存在顶点到自身的边 多重图 | 若图G中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联 完全图 | 有向完全图 — 任意两个顶点之间存在方向相反的两条弧 — n*(n-1 )条弧边 无向完全图 — 任意两个顶点之间都存在边 — n*(n-1)/2 条边 子图 | 设有两个图G(V,E) 和G'=(V',E'),若V' 是V的子集，且E'是E的子集则称G'是G的子图 --- 表格 52 --- 散列表的基本概念 | 散列表建立了关键字和存储地址之间的一种直接映射关系 散列函数 — 一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash(key)=Addr ★ 冲突 — 对不同关键字可能得到同一散列地址，即keyi≠key₂ , 而 H(keyi)=H(keyz), 这种现象称为冲突 同义词 — 具有相同函数值的关键字对该散列函数来说称作同义词，keyi≠key₂ 互称为同义词 ① 定义域：全部需要存储的关键字；值域：依赖于散列表的大小或地址范围 构造函数的注意事项 ② 散列函数计算出来的地址应尽可能等概率，均匀分布，尽可能减少冲突 常考好的散列函数的构造原则 ③ 函数计算简单，能够计算出任一关键字对应的散列函数 直接去关键字的某个线性函数值为散列地址，直线公式 H(key)=a×key+b(a 和b是常数) | 散列表建立了关键字和存储地址之间的一种直接映射关系 散列函数 — 一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash(key)=Addr ★ 冲突 — 对不同关键字可能得到同一散列地址，即keyi≠key₂ , 而 H(keyi)=H(keyz), 这种现象称为冲突 同义词 — 具有相同函数值的关键字对该散列函数来说称作同义词，keyi≠key₂ 互称为同义词 ① 定义域：全部需要存储的关键字；值域：依赖于散列表的大小或地址范围 构造函数的注意事项 ② 散列函数计算出来的地址应尽可能等概率，均匀分布，尽可能减少冲突 常考好的散列函数的构造原则 ③ 函数计算简单，能够计算出任一关键字对应的散列函数 直接去关键字的某个线性函数值为散列地址，直线公式 H(key)=a×key+b(a 和b是常数) 直接地址法 | 这种方法计算最简单，且不会产生冲突它适合关键字的分布基本连续的情况， 若关键字分布不连续，空位较多，则会造成存储空间的浪费。 散列函数的构造 | 除留余数法 | 散列表长为m, 取一个不大于m, 但是最接近于或等于m的质数p 散列函数为：H(key)=key%p 除留余数法的关键是选好p, 使得每个关键字通过该函数转换后等概率地映射到散列空间上地任一地址，从而减小冲突 数字分析法 | 如果事先知道关键字集合，且每个关键字的位数比散列表的地址码位数多，每个关键字由 n位数组成，如k1...kn, 则可以从关键字中提取数字分布比较均匀的若干位作为散列地址 数字分析法的适用情况：事先必须明确知道所有的关键字每一位上各种数字的分布情况 取关键字的平方值的中间位作为散列地址 平方取中法 平方取中法的适用情况：不能事先了解关键字的所有情况，或难干直接从关键字中找到取值较分散的几位 折叠法 | 将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为 散列地址，这种方法称为折叠法 --- 表格 53 --- int i,j; for (i = 2;i <= n;i ++) if( A[i] < A[i-1]) | // 依次将A[2]~A[n] 插入到前面已排序序列 //若A[i] 关键码小于其前驱，将 A[i] 插入有序表 代码实现 | A[0] = A[i]; | // 复制为哨兵，A[0] 不存放元素 for (j=i-1 ;A[0]p2=cu->p1->p1;cu=cu->p1;} D. while(cu!=null){if(cu->p1!=null){cu->p2=cu->p1->p1;}else cu->p2=null;cu=cu->p1;} **参考答案**: D ##### 二叉树遍历 ---2026年真题--- 【2026-3】二叉树层次遍历序列为{ab,g,cde,f}，则后序遍历序列为？ A. cedfbga B. cefdbga C. efdcbga D. egfdbca **参考答案**: C 【2026-41】二叉树遍历综合题（回忆版） （注：本题为2026年数据结构大题，回忆版具体内容待补充） ##### 森林与二叉树转换 ---2026年真题--- 【2026-4】森林中有5棵树，结点个数分别为2、3、4、5、7，二叉树的最小高度为？ A. 5 B. 6 C. 8 D. 10 **参考答案**: B ##### 哈夫曼树 ---2026年真题--- 【2026-5】已知字符abcdefg权值为1,2,4,5,8,10,12，使带权路径长度最小，与e同层的结点是？ A. d B. g C. d或f D. f或g **参考答案**: D ##### 图的存储 ---2026年真题--- 【2026-6】采用邻接表存储有向图G，求一个顶点入度的时间复杂度为？ A. O(|V|) B. O(min(|V|,|E|)) C. O(|E|) D. O(max(|V|,|E|)) **参考答案**: D ##### 有向图的路径 ---2026年真题--- 【2026-7】有向图顶点数为m和n，初始顶点S，标记顶点T，图中每条边有一个字符，S到T的所有字符串构成集合S，下列说法错误的是？ A. 若G无环，S为有穷集合 B. 若G无环，S有长度等于mn的串 C. 若G有环，S有长度大于五的串 D. 若G有环，S有小于2n的串 **参考答案**: B ##### 平衡三叉树 ---2026年真题--- 【2026-8】在高度为4的平衡三叉树中，根的左、右子树结点数相差最多的是？ A. 1 B. 2 C. 3 D. 5 **参考答案**: D ##### 直接插入排序 ---2026年真题--- 【2026-9】使用直接插入排序对序列进行升序排序，以下比较次数最少的是？ A. 30,27,56,41,80,95,69 B. 31,43,26,55,63,99,77 C. 61,84,51,23,34,91,40 D. 93,32,48,81,50,21,72 **参考答案**: B ##### 基数排序 ---2026年真题--- 【2026-10】按C1和总乘积排序，这种排序算法是？ A. 基数排序 B. 快速排序 C. 希尔排序 D. 选择排序 **参考答案**: A ##### 外排序 ---2026年真题--- 【2026-11】使用k路归并对外存数据排序，归并趟数为4，以下正确的是？ I. k可以减少d的值 II. 归并趟数不受初始归并段影响 III. 可用内存大小限制初始归并段长度 A. I B. II C. III D. I,II **参考答案**: C #### 📙 计算机组成原理 ##### 整数的表示与运算 ---2025年真题--- 【2025-12】代码: Short si=-32767; Unsigned int ui=si; 则其对应的值为？ A. 2^15+1 B. 2^15 C. 2^32-2^15-1 D. 2^32-2^15+1 **参考答案**: D **解析**: short si=-32767 补码为 8001H，符号扩展为 FFFF8001H = 4294934529 = 2^32-2^15+1。 ##### IEEE754浮点数 ---2025年真题--- 【2025-13】在 IEEE754 标准下，47300000H 对应的真值是？ A. 0.375×2^14 B. 1.6375×2^14 C. 0.375×2^15 D. 1.375×2^15 **参考答案**: D **解析**: 符号位0，指数142-127=15，尾数1.011=1.375，真值 = 1.375×2^15。 ---2026年真题--- 【2026-14】float型变量x为12.1，采用IEEE754单精度就近舍入，x的机器数是？ A. 41419999H B. 4141999AH C. 41E0CCCCCH D. 41E0CCCCDH **参考答案**: B ##### 补码加减运算与溢出 ---2025年真题--- 【2025-14】x=A3H, y=75H，计算 x-y，求真值和 OF。 A. 220,0 B. 221,0 C. 46,0 D. 46,1 **参考答案**: D **解析**: x=163, y=117, x-y=46。OF = 最高位进位异或次高位进位 = 1。 ##### 数据存储 ---2025年真题--- 【2025-15】结构体小端存储: struct{int d; char c[10]; int s;} M[200]; 起始地址 0000A0B0H，M[1].d 的机器数是？ A. 0000A0C3H B. 0000A0C4H C. 0000A0C5H D. 0000A0C6H **参考答案**: C ##### 指令系统基本概念 ---2025年真题--- 【2025-16】ISA 可以规定（）。 A. 定长指令字 B. 阵列乘法器 C. 微程序控制器 D. 单总线数据通路 **参考答案**: A ##### RISC与CISC ---2025年真题--- 【2025-17】RISC 中说法错误的是？ A. load/store B. 硬连接方式 C. 难以采用流水线数据通路实现微架构 D. 传递过程调用函数 **参考答案**: C ##### CPU与CPI ---2025年真题--- 【2025-18】关于 CPU 和 CPI 的叙述说法正确的是？ **参考答案**: B ##### 数据通路 ---2025年真题--- 【2025-19】数据通路错误的是？ A. 通用寄存器包含在 PC B. 单周期数据通路 CPI=1 C. 多周期 CPI>1 D. 流水线 CPI=1 **参考答案**: A ##### DMA ---2025年真题--- 【2025-21】适合采用 DMA 的设备有？ I. 键盘 II. 网卡 III. SSD IV. 打印机 A. I,II,III B. II,III C. III,IV D. I,II,IV **参考答案**: B ##### 中断 ---2025年真题--- 【2025-22】下列不会触发中断的事件是？ A. DMA传送结束 B. 页故障处理结束 C. 总线事务结束 D. 执行断点指令 **参考答案**: C ##### Cache与虚拟存储 ---2025年真题--- 【2025-43】计算机M字长32位，按字节编址，数据Cache数据区大小32KB，8路组相联，主存块64B。Cache命中2周期，缺失损失200周期，页大小4KB。数组d起始地址0180 0020H。 int x, d[2048], i; for(i=0; i<2048; i++) d[i] = d[i] / x; (1) Cache组号、块内地址分别占几位？VA中哪些位可作为Cache索引？ (2) d[100]的VA是多少？Cache组号是多少？ (3) 代码已在Cache中，i,x已装入内存但不在Cache，d[0]在其主存块内的偏移量是多少？Cache缺失率和平均访问时间？ (4) d分布在几个页中？d不在主存时，缺页次数？ **参考答案**: (1) Cache组号6位，块内地址6位，VA中V11~V6可作为Cache索引。 (2) d[100] VA=0180 01B0H，Cache组号=06H。 (3) 偏移量=0；Cache缺失率=129/4096=3.15%，平均访问时间=8.37。 (4) 3个页；缺页次数=3。 ##### 补码除法器 ---2025年真题--- 【2025-44】补码除法器分析： mov R1, (R3+R4*4) // R1 <- d[i] scov R1 // {R0,R1} <- -SEXT(R1) idiv R1 // R1 <- ({R0,R1})/R2 (1) 执行idiv时，d[i]=0x87654321，x=0xff，则R、Q、Y初始值各是多少？图中哪个部分包含计数器？ALUop控制的运算有哪几种？ (2) 执行idiv时，哪些情况下会发生除法异常？CPU需要完成哪些操作？ **参考答案**: (1) R=FFFF FFFFH，Q=87654321H，Y=FFFFFFFDH。控制逻辑包含计数器。ALUop控制的运算有加法和减法。 (2) 除数为0异常(d[i]任意，x=00000000H)和溢出异常(d[i]=80000000H，x=FFFFFFFFH)。CPU响应：关中断修改为内核态，保存断点，跳转到异常处理程序。 ---2026年真题--- 【2026-43】补码除法器综合题（回忆版） （注：本题为2026年计算机组成原理综合题，回忆版具体内容待补充） ##### 计算机系统层次 ---2026年真题--- 【2026-12】关于计算机系统层次，错误的是？ A. 最上层是应用软件层 B. ISA是软件和硬件的接口 C. 计算机组成属于ISA的物理实现层 D. 操作系统可通过ISA抽象向上层提供服务 **参考答案**: C ##### 移位运算 ---2026年真题--- 【2026-13】对机器数10100110B先算术右移3位再算术左移2位，最终结果是？ A. 11010000B B. 11010011B C. 01010000B D. 01010011B **参考答案**: A ##### 存储器组织 ---2026年真题--- 【2026-15】用8个64MX8位DRAM芯片按交叉编址构成主存，与64位总线相连，下列地址中与0018001DH位于同一芯片的是？ A. 00001D5H B. 000FA020H C. 0018001EH D. 0F020014H **参考答案**: A ##### 指令系统 ---2026年真题--- 【2026-16】下列不是由ISA规定的是？ A. 输入输出指令 B. 采用向量中断 C. 虚拟存储管理方式 D. 指令流水线是否使用超级流水线技术 **参考答案**: D ##### 指令执行 ---2026年真题--- 【2026-17】下列指令中执行后有可能按存放顺序执行其下一条指令的是？ I. 无条件跳转 II. 过程调用 III. 陷阱 IV. 过程返回 A. I,II B. 仅II,III C. 仅II,IV D. I,II,IV **参考答案**: B ##### Cache映射 ---2026年真题--- 【2026-18】数据cache 1024行，4路组相联，主存块32B，访问地址1028的4字节数据，所在主存块对应的组号是？ A. 8 B. 16 C. 32 D. 64 **参考答案**: C ##### TLB与页表 ---2026年真题--- 【2026-19】虚拟地址16位，页大小2^6B，TLB 4路组相联16个页表项。主存页表中页号22对应P=0，PPN=2AH。下列不可能出现在组号2的TLB表项中的是？ A. Tag=05H, V=1, PPN=1CH B. Tag=06H, V=1, PPN=2AH **参考答案**: A ##### 数据通路与CPI ---2026年真题--- 【2026-20】关于数据通路结构与CPI的关系，正确的是？ I. 单周期CPI=1 II. 多周期CPI>1 III. 流水线CPI=1 A. I B. 仅II C. 仅II,III D. I,II,III **参考答案**: D ##### 特权指令 ---2026年真题--- 【2026-21】下列不是特权指令的是？ A. I/O指令 B. 关中断指令 C. 中断返回指令 D. 系统调用指令 **参考答案**: D ##### 中断响应 ---2026年真题--- 【2026-22】中断控制I/O方式下，必须由硬件完成的是？ A. 开中断 B. 保存断点 C. 保存通用寄存器 D. 中断返回 **参考答案**: B ##### Cache与TLB ---2026年真题--- 【2026-42】计算机组成原理综合题（回忆版） 某计算机按字节编址，数据cache 1024行，4路组相联，主存块32B。分析Cache组号、TLB、页表等工作过程。 （注：本题为2026年计算机组成原理综合题，回忆版具体内容待补充） #### 📘 操作系统 ##### 进程上下文切换 ---2025年真题--- 【2025-23】在虚拟页式管理系统中，进行进程上下文切换时，不用发生变化的是？ A. 页表基址寄存器 B. 通用寄存器 C. 程序计数器 D. 中断向量表的基址寄存器 **参考答案**: D ##### 虚拟化技术 ---2025年真题--- 【2025-24】关于虚拟化技术，错误的说法是？ A. 操作系统可以在虚拟机上运行 B. 可用一台主机上模拟多种ISA C. VMM与操作系统特权级相同 D. 一台主机可以支持多个虚拟机 **参考答案**: C ##### 进程调度算法 ---2025年真题--- 【2025-25】优先级调度算法，高优先级进程在队头，队列长度为n，插入、出队的时间复杂度分别为？ A. O(1),O(1) B. O(1),O(n) C. O(n),O(1) D. O(n),O(n) **参考答案**: C ##### 页面置换算法 ---2025年真题--- 【2025-26】采用LRU调度算法，局部置换策略，给进程分配3个页框，页面访问序列为{0,1,2,0,5,1,4,3,0,2,3,2,0}，SR0,1,2已调入内存，问缺页次数为？ A. 5 B. 6 C. 7 D. 8 **参考答案**: B ##### 页面分配策略 ---2025年真题--- 【2025-27】确定进程运行所需的最少页框数时，要考虑？ A. 代码段长 B. 虚拟地址空间大小 C. 物理地址空间大小 D. 指令系统支持的寻址方式 **参考答案**: D ##### 虚拟文件系统 ---2025年真题--- 【2025-28】关于虚拟文件系统的内容，正确的是？ A. VFS是运行在虚拟内存中的文件系统 B. C. VFS提供统一接口访问不同文件系统 D. VFS只能访问本地文件系统 **参考答案**: C ##### 文件系统的操作 ---2025年真题--- 【2025-29】使用索引节点，用户在新建文件F时，文件系统不会做的是？ A. 初始化索引节点 B. 在目录文件中写入索引节点号 C. 在目录文件中写入访问权限信息 D. 在目录中增加目录项 **参考答案**: C ##### 内存映射文件 ---2025年真题--- 【2025-30】关于内存映射文件，正确的是？ I. 可实现进程间通信 II. 实现了页面到磁盘块的映射 III. 将文件映射到进程逻辑地址空间 IV. 将文件映射到系统物理地址空间 A. I,II,III B. I,II,IV C. I,III D. II,III,IV **参考答案**: D ##### 文件分配方式 ---2025年真题--- 【2025-31】可记录外存空间使用情况的是？ A. BR B. 进程控制块 C. 文件分配表(FAT) D. 系统打开文件表 **参考答案**: C ##### 磁盘存储管理 ---2025年真题--- 【2025-32】文件系统为温彻斯特硬盘、固态硬盘都有的功能是？ A. 划分扇区 B. 确定盘块大小 C. 降低寻道时间 D. 实现均衡磨损 **参考答案**: B ##### 信号量与进程同步 ---2025年真题--- 【2025-45】甲、乙、丙三人合作种树：甲挖坑→乙放树苗填土→丙浇水。只有一把铁锹和一个水桶，甲挖坑当且仅当树坑<3时才挖坑，挖坑和填土需要铁锹，浇水需要水桶。请用尽可能少的信号量实现。 **参考答案**: semaphore mutexT = 1; // 铁锹互斥 semaphore sk = 3; // 树坑数量 semaphore empty = 0; // 可用树坑 semaphore water = 0; // 需要浇水 semaphore mutexW = 1; // 水桶互斥 甲() { while(1) { wait(sk); wait(mutexT); 挖坑; signal(mutexT); signal(empty); } } 乙() { while(1) { wait(empty); wait(mutexT); 入坑并填土; signal(mutexT); signal(sk); signal(water); } } 丙() { while(1) { wait(water); wait(mutexW); 浇水; signal(mutexW); } } ---2026年真题--- 【2026-44】进程同步综合题（回忆版） （注：本题为2026年操作系统综合题，回忆版具体内容待补充） ##### 进程映像与存储管理 ---2025年真题--- 【2025-46】代码: char *ptr; void main() { int length; ptr = (char*)malloc(10); scanf("%c", &ptr); length = ptr; printf("%d", length); free(ptr); } (1) PCB位于哪个位置？执行scanf()时，进程处于什么状态？ (2) main()、ptr指针、length变量和malloc函数各位于哪个位置？ (3) 代码中哪些函数会调用I/O驱动程序？ **参考答案**: (1) PCB位于内核区；执行scanf()时进程处于阻塞态。 (2) main()代码位于只读代码段；ptr在可读写数据段；length在栈；malloc在动态链接库。 (3) scanf()和printf()需要调用I/O驱动程序。 ##### 处理器状态 ---2026年真题--- 【2026-23】下列操作中，在内核态执行的是？ A. 编译程序 B. 链接程序 C. 中断处理程序 D. 命令解释程序 **参考答案**: C ##### 虚拟存储器与异常 ---2026年真题--- 【2026-24】在支持虚拟存储器系统下的指令执行过程中，正确的是？ A. 地址转换由操作系统完成 B. 异常由操作系统处理 **参考答案**: D ##### 线程 ---2026年真题--- 【2026-25】下列线程描述中，正确的是？ A. 内核级线程和用户级线程都由操作系统创建 B. 同一个进程下的多个内核级线程共享进程栈 C. 同一个进程下的多个线程共享进程堆 D. 同一个进程下的多个线程共享进程代码段 **参考答案**: D ##### 信号量 ---2026年真题--- 【2026-26】系统中有8个进程，资源S初始值为5，若此时S的值为-2，m为执行到访问资源的进程个数，mn为阻塞的进程个数，则m和mn是？ A. 5,2 B. 6,1 C. 6,2 D. 7,1 **参考答案**: B ##### 并发控制 ---2026年真题--- 【2026-27】进程P(Q)和W(Q)，则不会发生错误的并发执行冲要充要条件是？ I. R(Q)与W(P)不相交 II. R(P)与W(Q)不相交 III. W(Q)与W(P)不相交 IV. R(P)与R(Q)不相交 A. I,II B. I,III C. I,II,IV D. I,II,III **参考答案**: C ##### 虚拟存储管理 ---2026年真题--- 【2026-28】64位系统采用三级虚拟分页存储管理方式，第三级页表所占用的页框数是？ A. B. C. 256K D. **参考答案**: C ##### 存储系统性能 ---2026年真题--- 【2026-29】能够有效降低系统平均访存时间的是？ I. TLB II. 多级页表 III. 工作集概念 IV. 页表缓冲队列 A. I,II B. I,III C. I,II,IV D. I,III,IV **参考答案**: C ##### 进程共享 ---2026年真题--- 【2026-30】进程P1和P2共享文件R，页表项R1和R2，虚拟地址W1和W2，正确的是？ A. B. W1=W2时物理地址一定相同 C. D. **参考答案**: B ##### 设备驱动程序 ---2026年真题--- 【2026-31】下列关于驱动程序的描述中，错误的是？ A. B. C. 驱动程序需要设置统一的接口 D. 字符设备、块设备都是同一种I/O方式 **参考答案**: D ##### 中断处理 ---2026年真题--- 【2026-32】鼠标中断处理程序完成的是？ A. B. C. 将数据从输入设备传输到数据寄存器 D. 将数据从数据寄存器传输到内核缓冲区 **参考答案**: D ##### 存储管理 ---2026年真题--- 【2026-45】存储管理综合题（回忆版） 涉及malloc/free、I/O驱动程序调用等。 （注：本题为2026年操作系统综合题，回忆版具体内容待补充） #### 📕 计算机网络 ##### 以太网与总线带宽 ---2025年真题--- 【2025-20】10M以太网总线采用同步方式，并行传输，每个时钟周期传4次32位，时钟频率1333MHz，总线带宽是？ A. 10.665GB/s B. 32.636GB/s C. 24.666GB/s D. 19.663GB/s **参考答案**: A ##### 交换方式比较 ---2025年真题--- 【2025-33】H1、H2之间按电路交换、报文交换、分组交换方式传送2MB文件，耗时分别为Tcs、Tms、Tps，大小关系是？ A. Tcs>Tms>Tps B. Tms>Tps>Tcs C. Tms>Tcs>Tps D. Tps>Tms>Tcs **参考答案**: B ##### 海明码 ---2025年真题--- 【2025-34】某差错编码的编码集为{10011010,01011100,11110000,00001111}，其检错、纠错能力是？ A. 检测不超过2位错，可纠正不超过1位错 B. 检测不超过2位错，可纠正不超过2位错 C. 检测不超过3位错，可纠正不超过1位错 D. 检测不超过3位错，可纠正不超过2位错 **参考答案**: C **解析**: 最小海明距离=4，检错能力=距离-1=3，纠错能力=1。 ##### CSMA/CD与二进制指数退避 ---2025年真题--- 【2025-35】10BaseT以太网，连续发生11次冲突，甲再次发送的最大时间间隔是？ A. 0.512ms B. 0.5632ms C. 52.3776ms D. 104.8064ms **参考答案**: C **解析**: 第11次冲突后，随机选择范围0~2^10-1=1023个时隙，最大间隔=1023×51.2us=52.3776ms。 ##### DHCP协议 ---2025年真题--- 【2025-36】DHCP协议的REQUEST报文，目的IP、源IP为？ A. B. C. 255.255.255.255, 0.0.0.0 D. **参考答案**: C ##### NAT ---2025年真题--- 【2025-37】NAT路由器从内网转发分组到外网，IP分组内携带UDP数据报，UDP首部被修改的是？ I. 源端口号 II. 目的端口号 III. 总长度 IV. 校验和 A. I,II B. I,IV C. II,III D. II,IV **参考答案**: B ##### TCP发送窗口 ---2025年真题--- 【2025-38】t0时刻，甲的ssthresh=38，拥塞窗口=2，发送窗口=2，MSS=1000B。t1时刻，甲可再给乙发送多少个TCP段？ A. 2 B. 3 C. 4 D. 5 **参考答案**: A ##### UDP与TCP对比 ---2025年真题--- 【2025-39】Time服务器采用C/S模型，RTT=8ms。采用UDP、TCP请求时间服务器，最短耗时分别是？ A. 8ms,8ms B. 8ms,16ms C. 16ms,8ms D. 16ms,16ms **参考答案**: B ##### POP3协议 ---2025年真题--- 【2025-40】关于POP3，正确的是？ I. 支持用户代理从邮件服务器读取邮件 II. 支持用户代理向邮件服务器发送邮件 III. 支持邮件服务器之间发送与接收邮件 IV. 支持一条TCP连接接收多封邮件 A. I,IV B. II,III C. I,II,III D. I,II,IV **参考答案**: A ---2026年真题--- 【2026-40】关于POP3协议，正确的是？ I. 支持用户代理从邮件服务器读取邮件 II. 支持用户代理向邮件服务器发送邮件 III. 支持邮件服务器之间发送与接收邮件 IV. 支持一条TCP连接接收多封邮件 A. I,II B. I,IV C. I,II,III D. I,II,IV **参考答案**: B ##### 网络综合题 ---2025年真题--- 【2025-47】 (1) R1到R2之间卫星链路单向传播时延是多少？最大吞吐量？上传4000B文件至少需要多长时间？ (2) SLP协议：数据帧长1500B，忽略ACK帧长，要求信道利用率≥80%，发送窗口至少为多少？帧序号至少为多少？ (3) IP空间10.10.10.0/24，划分为3个子网：生活区≥120主机，作业区≥60主机，管理区≥60主机。问各子网地址？ **参考答案**: (1) 单向传播时延≈0.12s(36000km÷300000km/s)。 (2) 发送窗口应满足利用率≥80%的值；帧序号至少为发送窗口的2倍。 (3) 生活区: 10.10.10.0/26；作业区: 10.10.10.64/27；管理区: 10.10.10.96/27。 ##### 网络体系结构 ---2026年真题--- 【2026-33】关于分层网络体系结构，错误的是？ A. B. 层次越多效率越高 C. 有利于各层技术独立演化 D. **参考答案**: B ##### 传输时延 ---2026年真题--- 【2026-34】带宽200kHz，信噪比S/N=1023，发送15300B分组，传输时延至少是？ A. B. C. 3ms D. 6ms **参考答案**: D ##### CSMA/CA ---2026年真题--- 【2026-35】CSMA/CA的IEEE802.11无线局域网，数据传输速率300Mbps，DIFS=128us，SIFS=28us，发送1500B数据帧，从开始发送到确认收到所需时间至少？ A. 40us B. 68us C. 168us D. **参考答案**: B ##### VLAN ---2026年真题--- 【2026-36】支持VLAN划分的以太网交换机按端口划分了两个VLAN，下列帧中H3会接收到的是？ F1: DA=00-1A-2B-3C-4D-03, SA=00-1A-2B-3C-4D-01 F3: DA=FF-FF-FF-FF-FF-FF, SA=00-1A-2B-3C-4D-02 A. F1,F3 B. F1,F2 C. F2,F3 D. F2,F4 **参考答案**: B ##### 路由算法 ---2026年真题--- 【2026-37】基于链路状态路由算法，R1检测到到R2的链路断开，重新计算并进行充分路由聚合后，路由项的数量为？ A. 3 B. 4 C. 5 D. 6 **参考答案**: C ##### 路由协议 ---2026年真题--- 【2026-38】能将一个自治系统划分为多个区域的内部网关协议是？ I. OSPF II. RIP III. BGP A. I B. II C. I,II D. I,III **参考答案**: A ##### TCP超时重传 ---2026年真题--- 【2026-39】TCP超时重传时间(RTO)的计算与（）密切相关？ A. 往返时延RTT B. 窗口大小 C. MSS D. **参考答案**: A ##### 网络综合 ---2026年真题--- 【2026-46】计算机网络综合题（回忆版） （注：本题为2026年计算机网络综合题，回忆版具体内容待补充）