软件设计师考试 - 计算机组成与体系结构

Mar 18, 2025 · 4 分钟阅读 · 软考软件设计师 ·

分享到:

文章目录

一、计算机组成（Computer Organization）

计算机系统是由硬件和软件两大部分组成的复杂系统，它们协同工作以完成各种任务。硬件是计算机的物理部分，软件是计算机的程序和数据（包括操作系统和应用软件）。

1.1 基本硬件组件

中央处理器CPU（Central Processing Unit）
- 运算器（ALU）：执行算术和逻辑运算，是CPU的核心计算部件。
- 控制器（CU）：控制指令的执行和数据的流动，是CPU的指挥中心。
- 寄存器组：临时存储数据和指令（如通用寄存器、程序计数器（PC）、堆栈指针（SP）等）。
存储器（Memory）
- 主存储器（RAM）：临时存储运行中的程序和数据，速度快，但断电后数据丢失。
- 只读存储器（ROM）：存储固件和启动程序（如BIOS），断电后数据不丢失。
- 高速缓存（Cache）：提高CPU访问数据的速度，位于CPU和主存之间，用于加速数据访问。
输入/输出设备（I/O）（Input Devices / Output Devices）
- 键盘、鼠标、显示器、打印机等。
- I/O接口：连接外部设备与计算机。
存储设备：用于长期存储数据，如：硬盘（HDD）、固态硬盘（SSD）、光盘、U盘等。
总线（Bus）：用于在计算机各组件之间传输数据，包括数据总线(传输数据)、地址总线(传输内存地址)、控制总线(传输控制信号)。
主板（Motherboard）：连接和协调所有硬件组件，提供电源和数据传输通道。

1.2 CPU的组成

CPU由控制器和运算器两大部分组成，在控制器的控制之下，运算器存储器和输入输出设备等部件构成了一个整体。

控制器（CU）：控制整个CPU的工作，控制器是整个系统的指挥中心。（记忆口诀：寄存遗址时）
- 程序计数器(PC)：存放下一条指令在内存的地址
- 指令寄存器(IR)：存放即将要执行的指令
- 指令译码器(ID)：翻译指令(操作码+操作地址)
- 地址寄存器(AR)：保存当前CPU所访问的内存地址
- 时序部件：提供时序控制信号(计算机时钟）
运算器（ALU）：执行算术运算(加减乘除等)和逻辑运算(与或非等）。（记忆口诀：蒜同树撞）
- 算术逻辑单元(ALU)：实现对数据的算数和逻辑运算
- 累加寄存器(AC)：通用寄存器，为ALU提供一个工作区，暂存
- 数据缓冲寄存器(DR)：读写内存，暂存的指令或数据
- 状态条件寄存器(PSW)：存状态标志及控制标志

1.3 指令系统

指令系统是计算机硬件与软件之间的接口。一条指令是计算机执行的基本操作，例如加法、减法、数据移动等。指令集是指所有指令的集合，是计算机硬件设计的基础。

一条指令的执行流程可以概括为取指、分析和执行三个阶段。
- 执行过程：
  1. 取指(Fetch): PC(程序计数器) → AR(地址寄存器) → DR(数据缓冲寄存器) → IR(指令寄存器)
  2. 分析(Decode): OP(IR) → CU(控制单元)
  3. 执行(Execute): Ad(IR) → AR(地址寄存器) → DR(数据缓冲寄存器) → AC(累加器)
- 细节解释：
  - PC（程序计数器）：PC中存储的是下一条要执行的指令的地址。（在取指完成后，PC会递增，指向下一条指令的地址(除非遇到跳转指令,PC将被更新为新的地址,从而改变程序的执行流程)。）
  - AR（地址寄存器）：PC中的地址被送到AR，AR将地址发送到内存地址总线。
  - DR（数据缓冲寄存器）：内存根据AR中的地址将指令数据送到DR。
  - IR（指令寄存器）：DR中的指令数据被送到IR，IR将保存这条指令直到它被执行。
  - OP（IR）：IR中的指令被解析，操作码（OP）部分被提取出来。（如果指令包含操作数（如立即数或地址），这些操作数也会从IR中提取出来。）
  - CU（控制单元）：操作码被送到CU，CU根据操作码生成控制信号，控制后续的执行步骤。
  - Ad（IR）：如果指令涉及内存访问，IR中的地址部分被送到AR。
  - AR（地址寄存器）：AR将地址发送到内存地址总线。
  - DR（数据缓冲寄存器）：内存根据AR中的地址将数据送到DR。
  - AC（累加器）：如果指令涉及算术或逻辑操作，AC中的数据将与DR中的数据或立即数进行运算，结果可能存回AC或内存。（如果指令涉及写回内存，运算结果可能会从AC或DR写回到内存中。）
- 补充：
  - 流水线技术：现代CPU通常采用流水线技术，使得取指、分析和执行可以并行进行，从而提高指令执行效率。
  - 中断处理：在执行过程中，CPU可能会响应中断，暂停当前指令的执行，转而处理中断服务程序。
  - 缓存机制：为了提高内存访问速度，CPU通常使用缓存（Cache）来存储最近访问的指令和数据，减少访问主内存的次数。
指令格式
- 操作码（Opcode）：指定要执行的操作，例如加法、减法、跳转等。
- 操作数（Operand）：参与操作的数据或地址（可以是寄存器、内存地址或立即数）。
- 寻址方式（寻找操作数的有效地址）：
  - 立即寻址：操作数直接包含在指令中。
  - 直接寻址：操作数的地址直接包含在指令中。
  - 寄存器寻址：操作数在寄存器中。
  - 间接寻址：操作数的地址在寄存器或内存中。
  - 相对寻址：基于当前程序计数器（PC）的偏移量。
常见的指令类型：
- 数据传送指令：在寄存器和内存之间传输数据，如MOV（移动数据）、PUSH（压栈）、POP（出栈）。
- 算术运算指令：执行加减乘除等运算，如ADD（加法）、SUB（减法）、MUL（乘法）。
- 逻辑运算指令：执行与、或、非等逻辑操作，如AND（与）、OR（或）、NOT（非）。
- 控制转移指令：改变程序执行顺序，如JMP（无条件跳转）、CALL（调用子程序）、RET（返回）。
- 输入输出指令：与外部设备进行数据交换，如IN（从端口读取数据）、OUT（向端口写入数据）。

1.4 输入输出技术

I/O设备与主机数据传输。早期计算机的I/O种类比较少，与主存交换信息都是通过CPU，而现代计算机的I/O种类较多，如果使用这种方式会使CPU的效率大大降低，如果想要提高资源利用率，那么我们就必须引入一些机制，来让整个机器工作效率变高。 I/O设备与主机交换信息的几种控制方式：

程序查询方式（Programmed I/O, PIO）：CPU通过不断轮询I/0设备的状态来判断是否可以进行数据传输。CPU工作效率低。
中断方式（Interrupt-Driven I/O）：当1/0设备准备就绪，向CPU发送中断请求，CPU响应中断（并保存状态）并处理数据传输，完成后恢复原来的状态并继续执行被中断的程序。提高了CPU利用率。
直接内存访问（Direct Memory Access, DMA）：DMA控制器直接控制数据在外设和内存之间的传输，传输过程无需CPU参与。减少了CPU的负担（CPU仅初始化DMA,传输完成后DMA通知CPU）。
通道方式（Channel I/O）：通道是一种专用的I/O处理器，负责管理和控制多个I/0设备的数据传输。进一步减轻了CPU的负担（传输完成后，通道处理器通知CPU）。
I/O处理机（IOP, I/O Processor）：I/O处理机是一种专门用于处理I/O操作的小型处理器，通常集成在系统中。（独立处理I/O操作，完成后I/O处理机通知CPU）。

1.5 磁盘的工作原理

工作步骤：
1. 旋转：磁盘的盘片以恒定速度旋转（通常为5400 RPM或7200 RPM）。
2. 寻道：磁头移动到目标磁道，这个过程称为寻道时间（Seek Time）。
3. 旋转等待：磁头等待目标扇区旋转到磁头下方，这个过程称为旋转延迟（Rotational Latency）。
4. 数据传输：磁头读取或写入数据，这个过程称为传输时间（Transfer Time）。
性能指标：
- 寻道时间（Seek Time）：磁头移动到目标磁道所需的时间。
- 旋转延迟（Rotational Latency）：盘片旋转到目标扇区所需的时间，通常为旋转周期的一半。
- 传输时间（Transfer Time）：读取或写入数据所需的时间。
- 存取时间（Access Time）：寻道时间 + 旋转延迟 + 传输时间。
- 数据传输率（Data Transfer Rate）：单位时间内磁盘传输的数据量。
存取时间计算:
- 旋转周期：\(\text{旋转周期} = \frac{60}{\text{转速（RPM）}}\)
- 旋转延迟：\(\text{旋转延迟} = \frac{\text{旋转周期}}{2}\)
- 传输时间：\(\text{传输时间} = \frac{\text{数据量}}{\text{数据传输率}}\)
- 存取时间：\(\text{存取时间} = \text{寻道时间} + \text{旋转延迟} + \text{传输时间}\)
计算示例：
- 示例1：磁盘转速为 7200RPM（每分钟7200转），则:
  - \(\text{旋转周期} = \frac{60}{\text{转速（RPM）}} = \frac{60}{7200} = 0.00833 \text{s} = 8.33 \text{ms} \)
  - \(\text{旋转延迟} = \frac{\text{旋转周期}}{2} = \frac{8.33}{2} = 4.17 \text{ms} \)
- 示例2：假设某磁盘的每个磁道划分成11个物理块，每块存放1个逻辑记录。逻辑记录 \( R_0,R_1,...,R_{10} \) 存放在同一个磁道上，如果磁盘的旋转周期为33ms，磁头当前处在 \( R_0 \)的开始处。若系统使用单缓冲区顺序处理这些记录，每个记录处理时间为5ms，则处理这11个记录的最长时间为(?); 若对信息存储进行优化分布后，处理11个记录的最少时间为(?)。
  - 分析：
    - 磁盘旋转周期为33ms，因此每个物理块的读取时间为：\( \frac{33\text{ms}}{11} = 3\text{ms} \)
    - 每个记录的处理时间为：\( 5\text{ms} \)
    - 系统使用单缓冲区，因此读取和处理是串行的。
  - 计算最长时间：（需要考虑最坏情况；即除\( R_0 \)(开始处)外，每次读取记录时都需要等待完整的旋转延迟。）
    1. \( R_0 \)：磁头已经在R0的开始处，因此无需等待。
    - 耗时：3ms（读取） + 5ms（处理） = 8ms。
    1. \( R_0 \cdots R_{10} \) ：最坏情况需要等待完整的旋转延迟，磁盘旋转周期为33ms，且顺序读取间隔为1块（3ms），因此需要等待：\( 33\text{ms} - 3\text{ms} = 30\text{ms} \)
    - 耗时：30ms（等待） + 3ms（读取） + 5ms（处理） = 38ms。
    1. 最长总时间为：\( 8\text{ms} + 10 \times 38\text{ms} = 8\text{ms} + 380\text{ms} = 388\text{ms} \)
  - 计算最短时间：（通过优化记录的分布，使得读取和处理可以重叠进行，从而减少总时间。）
    1. \( R_0 \)：磁头已经在R0的开始处，因此无需等待。
    - 耗时：3ms（读取） + 5ms（处理） = 8ms。
    1. \( R_0 \cdots R_{10}\)：顺序读取间隔为1块（3ms），因此旋转等待最快为：3ms（则在R0处理的同时，磁盘旋转到R1的位置，其他一样，所以无需计算等待时间）
    - 耗时：3ms（读取） + 5ms（处理） = 8ms。
    1. 最短总时间为：\( 11 \times 8\text{ms} = 88\text{ms} \)

1.6 磁盘阵列技术 RAID

磁盘阵列技术（RAID，Redundant Array of Independent Disks）是一种将多个独立的物理磁盘组合成一个逻辑磁盘的技术。通过数据分布、冗余和并行访问，RAID 可以提高存储系统的性能、可靠性和容量。

RAID 的常见级别：
- RAID 0（条带化）：数据被分割成块（条带），并分布存储在多个磁盘上（至少2块）。无冗余，所有磁盘并行工作。
- RAID 1（镜像）：数据完全复制到两个或多个磁盘上。每个磁盘存储相同的数据。
- RAID 5（带奇偶校验的条带化）：数据被分割成条带，并分布存储在多个磁盘上。每个条带包含一个奇偶校验块，用于数据恢复。
- RAID 6（双奇偶校验的条带化）：类似于 RAID 5，但使用两个独立的奇偶校验块（至少4块）。支持同时两个磁盘故障的数据恢复。
- RAID 10（镜像+条带化）：结合 RAID 1 和 RAID 0 的特点。数据先镜像，再条带化分布存储。
RAID 的性能与可靠性对比:

RAID 级别	冗余能力	读写性能	存储空间利用率	最少磁盘数量	特点	适用场景
RAID 0	无	高	100%	2 块	高性能、低可靠性	视频编辑、临时数据存储
RAID 1	高	读高，写中	50%	2 块	高可靠性	数据库服务器、关键数据存储
RAID 5	单磁盘故障恢复	读高，写中	(N-1)/N	3 块（1个奇偶校验块）	均衡性能与可靠性	文件服务器、中小型数据库
RAID 6	双磁盘故障恢复	读高，写低	(N-2)/N	4 块（2个奇偶校验块）	极高可靠性	大型数据库、数据备份
RAID 10	高	高	50%	4 块（R0 + R1）	高性能、高可靠性	高性能数据库、虚拟化平台

二、计算机体系结构（Computer Architecture）

计算机体系结构中的两种经典模型：

冯·诺依曼体系结构：别名普林斯顿结构，程序和数据共享同一存储空间，指令和数据都通过同一总线传输。
- 特点：单一存储器、指令流和数据流同一总线、指令按顺序执行、通用寄存器（使用一组通用寄存器来暂存数据和地址）。
- 五大部件：运算器、控制器、存储器、输入设备、输出设备。
- 优点：灵活性高、易于编程。缺点：性能瓶颈，安全性较低。
- 应用场景：通用计算机、个人电脑、服务器等。
哈佛体系结构：程序指令存储和数据存储分开的存储器结构，提高指令和数据的访问效率。
- 特点：分离的存储器、独立的总线、专用硬件（通常用于嵌入式系统和微控制器）、固定指令集。
- 优点：高性能、低功耗、安全性较高。缺点：灵活性较低、复杂性增加。
- 应用场景：嵌入式系统、微控制器、数字信号处理器（DSP）等。

2.1 指令集架构

指令集架构（ISA, Instruction Set Architecture）：指令集架构定义了处理器支持的基本操作集合。

CISC（复杂指令集计算机）（Complex Instruction Set Computer）：指令集包含大量复杂指令，每条指令可以完成多个操作。目标是通过复杂的指令减少程序中的指令数量，提高编程效率。
RISC（精简指令集计算机）(Reduced Instruction Set Computer)：指令集包含少量简单指令，每条指令只完成一个基本操作。目标是通过简化指令提高指令的执行效率，优化硬件设计。

对比项	CISC	RISC
指令集	指令集复杂，包含大量指令，指令长度可变。	指令集精简，包含少量指令，指令长度固定。
指令执行	一条指令可以完成多个操作，执行时间较长。	一条指令只完成一个基本操作，执行时间较短。
硬件复杂度	硬件设计复杂，需要支持多种指令和寻址方式。	硬件设计简单，优化指令流水线和并行处理。
编译器复杂度	编译器设计相对简单，指令功能强大。	编译器设计复杂，需要优化指令序列。
寄存器数量	寄存器数量较少，依赖内存访问。	寄存器数量较多，减少内存访问。
性能优化	通过复杂指令减少程序中的指令数量。	通过简化指令提高指令执行效率。
应用场景	适用于通用计算机，如x86架构。	适用于嵌入式系统和高性能计算，如ARM架构。

2.2 计算机体系结构的分类

Flynn分类法（Flynn’s Taxonomy）是计算机体系结构的一种分类方法，它根据指令流（Instruction Stream）和数据流（Data Stream）的多重性对计算机系统进行分类，是理解并行计算和多处理器系统的重要框架。

根据Flynn分类法，计算机体系结构可以分为以下四类：
- SISD（Single Instruction Single Data）：单指令流单数据流，典型的串行计算机。
- SIMD（Single Instruction Multiple Data）：单指令流多数据流，适合数据并行计算（一条指令同时处理多个数据）。
- MISD（Multiple Instruction Single Data）：多指令流单数据流，实际应用中较少见（理论可行现实不实际）。
- MIMD（Multiple Instruction Multiple Data）：多指令流多数据流，适合任务并行计算（多个处理器独立执行不同指令）。

类别	指令流	数据流	特点	示例
SISD	单指令流	单数据流	串行计算	单核CPU
SIMD	单指令流	多数据流	数据并行	GPU、向量处理器
MISD	多指令流	单数据流	冗余计算	容错计算机
MIMD	多指令流	多数据流	任务并行	多核CPU、分布式系统

Flynn分类法的应用
- 并行计算：理解SIMD和MIMD模型，设计高效的并行算法。
- 多处理器系统：分析多核CPU和分布式系统的性能。
- 高性能计算：优化超级计算机和集群系统的架构。
Flynn分类法的扩展
- SPMD（Single Program Multiple Data）：一种特殊的MIMD模型，多个处理器执行相同的程序，但操作不同的数据。
- 数据流计算机：基于数据驱动的计算模型，不属于传统的Flynn分类。

2.3 并行处理技术

通过多核处理器、多线程、多进程等方式提高计算机的处理能力。
- 指令级并行（ILP）：在单个处理器中同时执行多条指令。如流水线、超标量。
- 数据级并行（DLP）：对多个数据元素同时执行相同的操作。如SIMD（单指令多数据）。
- 任务级并行（TLP）：如多线程、多进程。

指令级并行（Instruction-Level Parallelism, ILP），实现方式：
- 流水线技术：将指令的执行过程分为多个阶段，使多个指令可以并行执行。
- 超标量技术：在一个时钟周期内发射多条指令到多个执行单元。
- 超长指令字（VLIW）：将多条指令打包成一条长指令，由硬件并行执行。
数据级并行（Data-Level Parallelism, DLP），实现方式：
- SIMD（单指令多数据）：一条指令同时处理多个数据元素，如Intel的SSE、AVX指令集。
- 向量处理器：专门设计用于处理向量数据的处理器。
任务级并行（Task-Level Parallelism, TLP），实现方式：
- 多线程：在单个处理器中通过时间片轮转执行多个线程。
- 多进程：在多个处理器或核心中同时执行多个进程。
- 分布式计算：在多台计算机中同时执行多个任务。
线程级并行（Thread-Level Parallelism, TLP）：在多个处理器或核心中同时执行多个线程。实现方式：
- 多核处理器：在一个芯片上集成多个核心，每个核心可以独立执行线程。
- 超线程技术：通过硬件模拟多个逻辑核心，提高单个物理核心的利用率。

硬件支持（多核处理器、GPU、FPGA）、软件支持（OpenMP、MPI、CUDA）。
并行处理的挑战
- 负载均衡：确保任务均匀分配到各个处理器或核心。
- 数据依赖性：解决任务间的数据依赖关系，避免冲突。
- 同步与通信：确保任务间的同步和通信效率。
- 可扩展性：随着处理器数量的增加，保持系统性能的线性提升。

2.4 流水线技术（Pipelining）

流水线：将一条指令的执行过程分解为多个独立的阶段，每个阶段由一个专门的硬件单元处理，多条指令在不同阶段同时执行。提高指令执行的并行性，从而提高处理速度。
流水线阶段：
1. 取指（Fetch, F）：从内存中取出指令。
2. 译码（Decode, D）：解析指令的操作码和操作数。
3. 执行（Execute, E）：执行指令的操作。
4. 访存（Memory, M）：如果需要，访问内存。
5. 写回（Write Back, W）：将结果写回寄存器或内存。
流水线的工作原理：
- 并行执行：多条指令在不同阶段同时执行。
- 阶段同步：每个阶段在一个时钟周期内完成，时钟信号驱动流水线的推进。
- 数据流动：指令在流水线中依次流动，每个阶段处理不同的指令。
- 示例：假设有三条指令（I1、I2、I3）在五级流水线中执行：
  
  时钟周期取指译码执行访存写回
  
  1 I1
  
  2 I2 I1
  
  3 I3 I2 I1
  
  4 I3 I2 I1
  
  5 I3 I2 I1
流水线性能指标
- 吞吐率（Throughput）：单位时间内完成的指令数。
- 加速比（Speedup）：使用流水线技术后的性能提升比例。
- 效率（Efficiency）：流水线的实际利用率。
流水线的优点：
1. 提高吞吐量：多条指令同时执行，单位时间内完成更多指令。
2. 资源利用率高：每个硬件单元在每个时钟周期都被充分利用。
3. 降低延迟：虽然单条指令的执行时间不变，但整体效率提高。
流水线冒险
- 结构冒险：硬件资源冲突，如同一时间多个指令需要访问同一个功能部件。
  - 解决方法：增加硬件资源，如多端口寄存器文件。
- 数据冒险：数据依赖问题，如先读后写（RAW）、先写后读（WAR）、先写后写（WAW）。
  - 解决方法：前推（Forwarding）、延迟（Stalling）。
- 控制冒险：分支指令导致的流水线停顿。
  - 解决方法：分支预测、延迟分支。
流水线的优化技术：
1. 数据前递（Forwarding）：将计算结果直接传递给后续指令，减少数据冲突。
2. 分支预测（Branch Prediction）：预测分支指令的执行路径，减少控制冲突。
3. 乱序执行（Out-of-Order Execution）：根据指令的依赖关系重新排序执行，提高效率。
4. 超标量技术（Superscalar）：在单个时钟周期内执行多条指令。

时钟周期	取指	译码	执行	访存	写回
1	I1
2	I2	I1
3	I3	I2	I1
4		I3	I2	I1
5			I3	I2	I1

2.5存储器的层次结构

采用层次化存储体系，可以通过平衡存储介质的速度和成本得到最佳的存储效用。解决了主存容量不足与高成本的矛盾、CPU与主存速度不匹配的矛盾。

存储器的层次结构从高速到低速依次为：
1. 寄存器：位于CPU内部，速度最快，容量最小。用于存储CPU正在处理的数据和指令，支持高速运算。
2. 高速缓存（Cache）：位于CPU和主存之间，分为L1、L2、L3缓存（L1最快但容量最小，L3较慢但容量较大），用于缓存主存中的常用数据，减少CPU访问主存的次数，提高系统性能。
3. 主存（内存）：包括RAM（随机存取存储器）和ROM（只读存储器）。用于存储正在运行的程序和数据。
4. 辅存（外存）：如硬盘、固态硬盘（SSD）、光盘等，容量大但速度较慢。用于长期存储程序和数据。断电不丢失。
RAM（随机存取存储器）VS ROM（只读存储器）
- RAM：随机存取，速度快，断电丢失。如：SRAM（静态）、DRAM（动态）。
- ROM：只读，不能随意写入，断电不丢失。如：EEPROM（电可擦除可编程）、EPROM（可擦除可编程）、PROM（可编程）、Flash Memory（闪存）。
SRAM（静态随机存取存储器）VS DRAM（动态随机存取存储器）
- SRAM（Static Random Access Memory）：使用触发器存储数据，不需要刷新。速度快，容量小，功耗高，用于高速缓存（Cache），如CPU的L1、L2、L3缓存。
- DRAM（Dynamic Random Access Memory）：使用电容存储数据，需要定期刷新。速度慢，容量大，功耗低，用于主存（内存），如计算机的DDR4、DDR5内存。
局部性原理：
- 时间局部性: 如果某个数据被访问，那么在不久的将来它可能再次被访问。
- 空间局部性: 如果某个数据项被访问，与它相邻的数据项可能也将被访问。

三、操作系统（Operating System，OS）

计算机系统的层次结构：硬件层 – 操作系统层 – 语言处理程序层 – 应用程序层。 操作系统是管理系统的硬件、软件、数据资源，控制程序运行，提供接口的系统软件。包括：进程管理、存储管理、文件系统、设备管理等。

3.1 进程管理

进程与线程：
- 进程是资源分配的基本单位，线程是CPU调度的基本单位。
- 线程是进程的一个实体（一个进程包含N个线程），同一类线程共享代码和数据空间，每个线程有独立的运行栈和程序计数器(PC)，线程切换开销小；(线程是 CPU 调度和分派的最小单位)。
进程状态：
- 就绪(Ready)、运行(Running)、阻塞(Block)。
- 状态转换：运行→阻塞（等待资源），阻塞→就绪（资源就绪），就绪→运行（被调度）。
进程同步与互斥：
- 临界区：一段代码，同一时间只能被一个进程执行。
- 互斥：确保同一时间只有一个进程访问临界资源。
- 同步：协调多个进程的执行顺序，确保它们按照一定的规则访问共享资源。
信号量（Semaphore）：一个整型变量，用于表示资源的可用数量。通过两个原子操作（P操作和V操作）实现进程同步与互斥。
- P操作（wait）：申请资源，信号量减1。（如果信号量小于0，进程阻塞。）
- V操作（signal）：释放资源，信号量加1。（如果信号量小于等于0，唤醒一个阻塞进程。）
经典同步问题：
- 生产者-消费者问题：生产者进程生产数据并放入缓冲区（大小有限），消费者进程从缓冲区取出数据。
  - 解决：使用两个信号量（①empty表示空闲缓冲区数量。 ②full表示已占用缓冲区数量。）使用互斥信号量mutex保护缓冲区。
- 读者-写者问题：多个读者进程和写者进程共享一个文件。（允许多个读者同时读取，但写者必须独占访问。）
  - 解决：使用信号量rw_mutex保护写者。使用计数器read_count记录读者数量，并用信号量mutex保护计数器。
- 哲学家进餐问题：五个哲学家围坐在圆桌旁，每个哲学家左右各有一根筷子。（需要两根筷子才能进餐。）
  - 解决：使用信号量数组chopstick[5]表示筷子。通过限制同时进餐的哲学家数量（如最多4个）避免死锁。
死锁与饥饿：
- 死锁（Deadlock）：多个进程因竞争资源而相互等待，无法继续执行。
  - 死锁条件：互斥、占有并等待、非抢占、循环等待。
  - 死锁处理：预防（破坏死锁条件）、避免（银行家算法）、检测与恢复。
- 饥饿（Starvation）：某些进程因资源分配策略而长期得不到资源。
  - 解决方法：公平调度算法（如时间片轮转）。

3.2 存储管理

存储管理是操作系统的重要功能之一，主要负责管理主存和辅存，确保程序和数据的高效存储与访问。

存储管理的功能：
- 内存分配与回收：为程序分配内存空间，并在程序结束后回收内存。
- 地址映射：将逻辑地址（程序使用的地址）转换为物理地址（内存中实际的地址），包括分段管理和分页管理。
- 内存保护：防止程序越界访问内存。
- 虚拟内存：通过虚拟内存技术扩展主存容量。

3.2.1 内存管理

连续分配管理：
- 单一连续分配：整个内存分配给一个程序。
- 固定分区分配：内存划分为固定大小的分区。
- 动态分区分配：根据程序需求动态划分内存。（分配算法：首次适应、最佳适应、最坏适应）
非连续分配管理：

分页管理：
- 将内存划分为固定大小的页。
- 页表：记录页与内存块的映射关系。
- 地址映射：逻辑地址 = 页号 + 页内偏移。
分段管理：
- 将内存划分为不同大小的段，每段长度可变。
- 段表：记录段与内存块的映射关系。
- 地址映射：逻辑地址 = 段号 + 段内偏移。
段页式管理：
- 结合分段和分页的优点，先分段再分页。
- 地址映射：逻辑地址 = 段号 + 页号 + 页内偏移。

3.2.2 虚拟内存

虚拟内存：通过将部分内存数据存储到磁盘（辅存）上，扩展内存容量，解决主存容量不足的问题。

实现方式：
- 分页式虚拟内存：将虚拟内存分为页，通过页表管理。
- 分段式虚拟内存：将虚拟内存分为段，通过段表管理。
页面置换算法：
- 先进先出（FIFO）：淘汰最早进入内存的页（可能产生Belady异常）。
- 最近最少使用（LRU）：淘汰最近最少使用的页（实际应用最广）。
- 最优置换（OPT）：淘汰未来最长时间不会被使用的页（理论最优，实际不可实现）。
页面抖动：频繁的页面置换导致系统性能下降。
缺页中断：访问的页面不在内存中时触发。

3.2.2 内存碎片

内部碎片：分配给程序的内存块中未被使用的部分。
外部碎片：内存中分散的小块空闲内存，无法满足程序的需求。
解决方法：
- 紧凑技术：将内存中的程序移动，合并空闲内存。
- 分页管理：通过固定大小的页减少外部碎片。

3.3 文件系统

文件（File）：存储在磁盘上的数据集合，具有唯一的名称和属性（文件名、大小、创建时间、访问权限等）。
目录（Directory）：用于组织文件的逻辑结构，可以包含文件和子目录。
文件系统（File System）：操作系统用于管理文件和目录的机制，提供文件的存储、访问和保护功能。

3.3.1 文件的逻辑结构和物理结构

逻辑结构：
1. 无结构文件（流式文件）：文件内容为字节流（文本文件、二进制文件等）。
2. 有结构文件（记录式文件）：文件内容由记录组成，每条记录有固定的格式（数据库文件、表格文件等）。
物理结构：
1. 连续分配：文件存储在磁盘的连续物理块中。
  - 优点：访问速度快，支持顺序访问和直接访问。
  - 缺点：外部碎片问题，文件扩展困难。
2. 链接分配：
  - 文件存储在离散的物理块中，每个块包含指向下一个块的指针。
  - 优点：无外部碎片，文件扩展方便。
  - 缺点：访问速度慢，不支持直接访问。
3. 索引分配：
  - 文件存储在离散的物理块中，通过索引表管理文件块。
  - 优点：支持直接访问，文件扩展方便。
  - 缺点：索引表占用额外空间。

3.3.2 目录结构

单级目录：所有文件存储在一个目录中。（简单，但查找效率低）
两级目录：目录分为主目录和用户目录。（不支持多层次组织）
树形目录：目录以树形结构组织，支持子目录。（层次清晰，但路径较长）
图形目录：目录以图形结构组织，支持文件共享。（灵活性高，但管理复杂）

3.3.3 文件系统的性能优化

磁盘调度算法：
- FCFS（First Come, First Serve）：先来先服务，简单但效率低。
- SSTF（Shortest Seek Time First）：最短寻道时间优先，可能导致饥饿。
- SCAN（电梯算法）：双向扫描，公平且高效。
- C-SCAN（Circular SCAN）：循环扫描，减少等待时间。
缓存机制：使用内存缓存磁盘数据，提高访问速度。
预读机制：提前读取磁盘数据，减少访问延迟。
旋转延迟：磁盘旋转到目标扇区的时间。

3.3.4 文件系统的保护

访问控制：通过权限位（如读、写、执行）控制用户对文件的访问。
加密：对文件内容进行加密，防止未授权访问。
备份与恢复：定期备份文件，防止数据丢失。

3.4 设备管理

设备的分类：
- 按数据传输单位（数据块/字符）分为：块设备（如磁盘）、字符设备（如键盘、鼠标）。
- 按共享属性分为：独占设备（如打印机）、共享设备（如磁盘）、虚拟设备（通过SPOOLING技术将独占设备虚拟为共享设备，如打印机假脱机系统）。
I/O控制方式：
- 程序查询：CPU轮询设备状态，效率低。
- 中断：设备完成操作后通知CPU。
- DMA（直接内存访问）：设备直接与内存交换数据，无需CPU干预。
- 通道：使用专门的I/O处理器（通道）管理设备，硬件成本高。
设备分配与调度
- 设备分配：
  - 静态分配：进程运行前分配设备，运行结束后释放。
  - 动态分配：进程运行时根据需要分配设备。
- 设备调度：通过调度算法提高设备利用率，如磁盘调度算法（FCFS、SSTF、SCAN 等）。
SPOOLING技术：
- 定义：SPOOLING（Simultaneous Peripheral Operations On-Line）是一种通过缓冲区实现设备虚拟化的技术。
- 原理：将设备的输入输出数据先存储在磁盘缓冲区中，再由SPOOLING系统管理设备的实际操作。
- 典型应用：打印机假脱机系统，多个进程可以同时提交打印任务，SPOOLING 系统按顺序处理。

END .