计算机组成与程序执行

本文整理计算机的基本构成、可计算性理论，以及程序从编译到执行的完整过程，作为理解操作系统的前置基础。

一、计算机的基本构成

计算机的核心部件包括：

• 输入/输出（I/O）设备：负责人与计算机之间的数据交换。
• CPU（中央处理器）：负责运算与逻辑控制，包含算术逻辑单元（ALU）与控制单元。
• 内存（Memory）：临时存放指令与数据，断电后丢失。
• 总线（Bus）：连接各部件，负责数据传输。

程序执行的本质是：CPU 从内存中不断取指令（Fetch）、译码（Decode）、执行（Execute），即经典的冯·诺依曼架构取指-执行循环。

二、可计算性理论

在讨论"如何把程序写好"之前，需要先回答一个更根本的问题：哪些问题是计算机可以求解的。

图灵机与可计算性

图灵机（Turing Machine）是一个抽象计算模型，由一条无限长的纸带、一个读写头和一组状态转移规则组成。如果一个问题存在一台图灵机能在有限步内给出答案，则称该问题是可计算的（Computable）。

• 可以构造图灵机求解的问题集合，称为图灵完备（Turing Complete）。
• 现代编程语言（如 C、Python、Java）都是图灵完备的，因为它们能模拟图灵机的全部能力。
• 存在不可计算问题，例如"停机问题"：不存在一个通用程序能判断任意程序是否会在有限步内停止。

丘奇-图灵论题

丘奇-图灵论题指出：所有可有效计算（算法可解）的函数，都能被图灵机计算。它为"什么是计算"给出了统一的边界定义。

对工程实践的启示

• 写程序前先判断问题是否可计算，避免尝试用算法解决本质上不可计算的问题。
• 当问题规模超出单台机器能力时，应转向分布式、近似计算或降维策略，而非单纯追求更快的 CPU。

三、程序的编译与执行

源代码到可执行程序通常经历以下阶段：

1. 预处理（Preprocess）：展开宏、包含头文件。
2. 编译（Compile）：将高级语言翻译为汇编语言。
3. 汇编（Assemble）：将汇编语言翻译为机器码（目标文件 .o）。
4. 链接（Link）：将多个目标文件与库合并，解析符号引用，生成可执行文件。

32 位与 64 位的差异

64 位相比 32 位的核心优势在于可寻址内存容量与单次运算吞吐。当程序需要处理超过 4 GB 的数据集（如大型数据库、科学计算）时，64 位是必要条件。

程序载入内存

操作系统通过加载器（Loader）将可执行文件从磁盘读入内存，建立进程地址空间，并将指令指针（PC/IP）指向入口地址（如 main），随后开始取指-执行循环。

四、构造复杂程序：递归转非递归

递归函数依赖调用栈保存中间状态。将递归转为非递归，本质是用显式数据结构替代系统调用栈。通用方法如下：

方法一：显式栈模拟

用一个显式的栈结构保存每次递归调用的参数与返回现场，用循环替代递归调用。

以斐波那契为例，递归版本：

int fib(int n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

非递归版本（自底向上迭代，空间复杂度从 (O(n)) 降为 (O(1))）：

int fib(int n) {
  if (n <= 1) return n;
  int a = 0, b = 1;
  for (int i = 2; i <= n; i++) {
    int t = a + b;
    a = b;
    b = t;
  }
  return b;
}

方法二：尾递归转循环

当递归调用位于函数末尾（尾递归），编译器可将其优化为跳转而非新建栈帧：

int sum_tail(int n, int acc) {
  if (n == 0) return acc;
  return sum_tail(n - 1, acc + n);  // 尾递归
}

等价循环：

int sum_loop(int n) {
  int acc = 0;
  while (n > 0) {
    acc += n;
    n--;
  }
  return acc;
}

方法三：状态机法

对分治型递归（如树遍历），将"待访问节点 + 状态"封装为栈帧对象，用循环驱动状态转移。该方式适用于无法简单用迭代替换、且栈深度可能过大的场景。

选择建议

• 能用迭代直接改写（如斐波那契、阶乘）时优先迭代，可读性与性能最佳。
• 无法线性展开时（如回溯、树形分治），使用显式栈模拟。
• 若函数本身是尾递归，优先依赖编译器尾调用优化，否则手动转循环。

小结

• 计算机是可计算问题的物理实现，图灵机界定了计算的边界。
• 程序经编译、链接、加载后由 CPU 取指执行；64 位在寻址与吞吐上显著优于 32 位。
• 递归可通过显式栈、尾递归优化、状态机三种通用方法转为非递归，以消除栈溢出风险并控制空间开销。