数据结构

操作系统

四、文件管理

（一）文件

1. 文件的基本概念
2. 文件元数据和索引节点（inode）
3. 文件的操作
   • 建立
   • 删除
   • 打开
   • 关闭
   • 读
   • 写
4. 文件的保护
5. 文件的逻辑结构
6. 文件的物理结构

（二）目录

1. 目录的基本概念
2. 树形目录
3. 目录的操作
4. 硬链接和软链接

（三）文件系统

1. 文件系统的全局结构（layout）
   • 文件系统在外存中的结构
   • 文件系统在内存中的结构
2. 外存空间管理办法
3. 虚拟文件系统
4. 文件系统挂载（mounting）

计算机组成原理

三、存储器层次结构

（一）存储器的分类

（二）层次化存储器的基本结构

（三）半导体随机存取存储器

1. SRAM 存储器
2. DRAM 存储器
3. Flash 存储器

（四）主存储器

1. DRAM 芯片和内存条
2. 多模块存储器
3. 主存和 CPU 之间的连接

（五）外部存储器

1. 磁盘存储器
2. 固态硬盘 (SSD)

（六）高速缓冲存储器 (Cache)

1. Cache 的基本原理
2. Cache 和主存之间的映射方式
3. Cache 中主存块的替换算法
4. Cache 写策略

（七）虚拟存储器

1. 虚拟存储器的基本概念
2. 页式虚拟存储器
   • 基本原理
   • 页表
   • 地址转换
   • TLB（块表）
3. 段式虚拟存储器
4. 段页式虚拟存储器

计算机网络

网络层

（一）网络层的功能

1. 异构网络互联

• 定义：连接不同通信协议、硬件或拓扑结构的网络。
• 关键技术：路由器、协议转换（如 IPv4/IPv6 双栈）。

2. 路由与转发

• 路由：选择数据包从源到目的地的路径（路由表生成）。
• 转发：根据路由表将数据包从输入端口转移到输出端口。

3. SDN 基本概念

• 软件定义网络：控制平面与数据平面分离，通过中央控制器动态管理网络。
• 核心组件：OpenFlow 协议、SDN 控制器（如 OpenDaylight）。

4. 拥塞控制

• 目标：避免网络过载导致性能下降。
• 方法：流量整形（如漏桶算法）、拥塞避免（如 TCP 慢启动）。

（二）路由算法

1. 静态路由与动态路由

• 静态路由：手动配置路由表，适用于小型稳定网络。
• 动态路由：通过协议自动更新路由表（如 RIP、OSPF）。

2. 距离-向量路由算法

• 原理：基于跳数（距离）选择路径，周期性与邻居交换路由信息。
• 示例：RIP（最大跳数 15）。

3. 链路状态路由算法

• 原理：全网拓扑同步，通过 Dijkstra 算法计算最短路径。
• 示例：OSPF。

4. 层次路由

• 划分自治系统（AS）：域内路由（IGP）与域间路由（BGP）。
• 优势：减少路由表规模，提高扩展性。

（三）IPv4

1. IPv4 分组

• 结构：首部（20 字节） + 数据，包含 TTL、协议类型等字段。

2. IPv4 地址与 NAT

• IPv4 地址：32 位，点分十进制表示（如 192.168.1.1）。
• NAT：将私有 IP 映射为公有 IP，解决地址短缺问题。

3. 子网划分、路由聚集、子网掩码与 CIDR

• 子网划分：通过子网掩码分割网络（如 255.255.255.0）。
• CIDR：无类别域间路由，支持超网聚合（如 192.168.0.0/16）。

4. ARP 协议、DHCP 协议与 ICMP 协议

• ARP：IP 地址到 MAC 地址的映射。
• DHCP：动态分配 IP 地址。
• ICMP：网络诊断工具（如 ping、traceroute）。

（四）IPv6

1. IPv6 的主要特点

• 地址扩展：128 位地址，解决 IPv4 枯竭问题。
• 简化首部：固定 40 字节，取消校验和字段。
• 安全性：原生支持 IPsec。

2. IPv6 地址

• 表示法：十六进制冒号分隔（如 2001:0db8::1）。
• 类型：单播、组播、任播。

（五）路由协议

1. 自治系统（AS）

• 定义：由单一组织管理的一组网络（如 ISP）。

2. 域内路由与域间路由

• 域内路由协议（IGP）：如 RIP、OSPF。
• 域间路由协议（EGP）：如 BGP。

3. RIP 路由协议

• 类型：距离-向量，最大跳数 15。
• 更新周期：30 秒广播路由表。

4. OSPF 路由协议

• 类型：链路状态，支持分层区域（Area 0 为骨干）。
• 算法：Dijkstra 计算最短路径树。

5. BGP 路由协议

• 用途：跨 AS 的路由交换，基于路径属性选择最优路径。
• 特点：TCP 端口 179，增量更新。

（六）IP 组播

1. 组播的概念

• 定义：单点发送，多点接收（如视频会议）。
• 优势：减少冗余流量。

2. IP 组播地址

• 范围：IPv4 为 224.0.0.0 ~ 239.255.255.255。
• 协议：IGMP 管理组成员关系。

（七）移动 IP

1. 移动 IP 的概念

• 目标：设备跨网络移动时保持 IP 不变。
• 核心实体：家乡代理、外地代理。

2. 移动 IP 通信过程

1. 移动节点注册家乡代理。
2. 家乡代理转发数据包至外地代理。
3. 外地代理将数据包送达移动节点。

（八）网络层设备

1. 路由器的组成和功能

• 组成：CPU、内存、接口卡、路由表。
• 功能：路由选择、分组转发、NAT、ACL。

2. 路由表与分组转发

• 路由表结构：目的网络、下一跳、接口、度量值。
• 转发流程：最长前缀匹配 → 选择最优路径 → TTL 减 1 → 转发至下一跳。