02 - Operating Systems from an Applied Perspective
02 - 应用视角的操作系统
1. Hello, OS World!
操作系统 - > 程序
1.1. 计算机程序
计算机：无情地执行指令的机器
机器永远是对的
如果编译器没有优化，"我们些什么，机器就就执行什么"
编译器会对这个代码做什么优化呢？
a.out assembly 汇编器的输出
在 release 版本中
编译器会优化代码
函数内联：当一个函数被频繁调用时，编译器会将该函数的代码直接插入到调用它的地方，而不是像正常情况下那样通过函数调用指令来执行。
循环展开：循环是程序中常见的结构，但循环的执行需要消耗一定的时间来判断循环条件、更新循环变量等。
常量传播：如果代码中有一些变量被赋了常量值，编译器会将这些常量值传播到程序的其他部分。
死代码删除：在代码中可能存在一些永远不会被执行的代码，这些代码被称为死代码。
程序就是状态机
在某个状态 GDB 可以帮你打印当前状态所有变量的值
每执行一条语句都会改变程序的状态...
C 语言的状态机模型
PicoC
解释型和编译型语言没有明确边界...
1.2. 理解程序：递归 vs 非递归
汉诺塔：C++课的噩梦
计算机里的函数不是数学里的函数
后悔没有选修 SICP ？？函数式编程？
f 和 g...
1.3. 把任意程序改写成非递归
C 代码总是可以改写成等价的 "Simple C"
每条语句只做一次运算（包括函数调用）
条件语句中不包含运算
Every thing = 状态机
1.4. 状态
[StackFrame, StackFrame, ...] + 全局变量
1.5. 初始状态
仅有一个 StackFrame(main, argc, argv, PC=0)
全局变量全部为初始值
操作系统最大的职责就是让我们在编程时感受不到操作系统的存在——我们在编程时想象程序 “独占整个计算机，逐条指令执行”，大部分时候都不用 “考虑” 操作系统的存在。当系统调用发生时，程序执行被完全暂停，但操作系统依然在工作——就像麻醉后醒来，周围的环境发生了变化，但我们完全没有感到时间的流逝。
2. 操作系统上的最小程序
汉诺塔的程序 和 程序的状态图
程序逻辑
从状态图中可以看出，程序的主要逻辑是一个 循环，用于计算某个数 n 经过一系列操作后变为 1 的步数。具体逻辑如下：
初始化 n = 5 ， steps = 0 。
进入循环，检查 n 是否等于 1 ：
如果 n 是偶数，则 n /= 2 。
如果 n 是奇数，则 n = 3 * n + 1 。
每次循环后， steps 增加 1 。
当 n 等于 1 时，退出循环，返回 steps 的值。
hanoi 塔
汉诺塔问题是一个经典的递归问题。问题描述如下：
有三根柱子，分别是 A（源柱）、B（辅助柱）和 C（目标柱）。
有若干个大小不同的盘子，初始时所有盘子按从大到小的顺序堆叠在源柱 A 上。
目标是将所有盘子移动到目标柱 C 上，移动过程中必须满足以下规则：
每次只能移动一个盘子。
每次移动时，只能将一个盘子从顶部移动到另一根柱子的顶部。
任何时候，在三根柱子的任何一根上，较大的盘子不能放在较小的盘子上面。
root@LAPTOP-GT06V0GS:/mnt/d/CSLab/osCourse/lec2/hanoi# ./hanoi-r
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C
A -> B
C -> B
C -> A
B -> A
C -> B
A -> C
A -> B
C -> B
Hanoi(4, A, B, C) = 152.1. 什么是程序？编译后
NEMU
struct CPUState {
uint32_t regs[32], csrs[CSR_COUNT];
uint8_t *mem;
uint32_t mem_offset, mem_size;
};2.2. 空的 main()？
实际上程序的进入不是 main() 入口，而是_start 。
Prompt: 我即便写一个空的 main()，链接后依然生成了很大的代码。怎么才能实现最小的 C 程序呢？
要实现最小的 C 程序，可以采取以下步骤：
使用最小的运行时库：避免链接标准库，使用
-nostdlib编译选项。手动定义入口点：使用
_start而不是main，直接调用系统调用退出程序。优化编译选项：使用
-Os或-O3进行优化，并去除调试信息。
2.3. _start()
示例代码：
void _start() {
__asm__("mov $60, %eax\n" // syscall: exit
"xor %edi, %edi\n" // status: 0
"syscall");
}编译命令：
gcc -nostdlib -Os -o minimal minimal.c学习知识点
在 Linux 系统中，程序的入口点通常是 _start 函数，而不是 main 函数。通过编写 _start 函数，你可以直接控制程序的启动过程，而不需要依赖标准库（如 glibc ）提供的初始化代码。
使用 -nostdlib 选项编译程序时，不会链接标准库（如 glibc ）。这意味着你需要自行处理程序的初始化和退出
在没有标准库的情况下，你需要直接使用系统调用（如 sys_exit ）来与操作系统交互。
2.4. ABI
最小可执行文件：我们可以把 gcc 编译的过程拆解开，手动完成编译和链接。我从哪里可以看到系统调用 ABI 的文档呢？DeepSeek-V3 指向了 syscalls (2)——其中的 See Also 部分 (See Also 总是有各种宝藏) 带我们来到了 syscall (2) 中的 ABI 描述。
平时说的编译其实只是其中一个步骤 - 从 .c 到 .exe
编译：将源代码（如 C 或汇编代码）转换为汇编代码
汇编：将汇编代码转换为目标文件（机器代码）
链接：将目标文件链接成最终的可执行文件
手册
手册页通常分为几个部分：
man 2 syscalls 可以查看 syscalls(2)
NAME：系统调用的名称。
SYNOPSIS：调用的语法。
DESCRIPTION：调用的描述。
RETURN VALUE：返回值的说明。
ERRORS：可能的错误和错误码。
EXAMPLES：使用示例。
SEE ALSO：相关手册页的链接。
3. 操作系统上的应用程序
作为用户，我们是感受不到操作系统的
我们只能感受到操作系统上运行的程序 (进程)
太搞了...逃课哈哈哈哈哈哈哈哈哈
3.1. Core Utilities (coreutils)
Standard programs for text and file manipulation
系统中默认安装的是 GNU Coreutils
3.2. 系统/工具程序：无所不能
Shell, binutils, ...
包管理 apt, dpkg, ...
网络 ip, ssh, curl, ...
多媒体 ffmpeg (真神 1), gstreamer (真神 2), ...
3.3. 不能看到的：各种后台程序
守护进程：daemon
万物归宗 systemd
systemd-network, systemd-logind, systemd-udevd, ...
系统管理 cron, udiskd, unattended-upgrade (讨厌), ...
各类服务 httpd, sshd, ...
安全组件 auditd, firewalld, ...
用户服务 pulseaudio, dbus-daemon, ...
3.4. 和 minimal.S 有任何区别吗？
也就是刚刚写的最小的应用程序
简短的答案：没有
任何程序 = minimal.S = 状态机
3.5. 可执行文件是操作系统中的对象
与 minimal 的二进制文件没有本质区别
让我们在命令行里看看上面那些 “程序” 都是什么
如果你是第一次接触命令行……也不用怕
问问大语言模型吧：我有一个 a.out 文件，我如何探索它里面有什么？
我有一个 a.out 文件，如何探索它里面有什么？
可以使用以下工具分析a.out文件内容：
file命令
file a.out快速识别文件类型（ELF可执行文件/目标文件等）objdump反汇编
objdump -d a.out查看汇编代码objdump -x a.out显示文件头信息nm查看符号表
nm a.out显示函数和全局变量符号strings提取字符串
strings a.out列出所有可打印字符串readelf工具（针对ELF格式）
readelf -a a.out显示完整的ELF文件结构
file
root@LAPTOP-GT06V0GS:/mnt/d/CSLab/osCourse/lec2/test_out# file a.out
a.out: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=2cd6cd98a1bb27d63fdde4ae355c361810ee8137, for GNU/Linux 3.2.0, not strippedELF ：表示这是一个可执行和可链接格式（Executable and Linkable Format）的文件。
64-bit LSB ：表示这是一个 64 位的小端字节序文件。
x86-64 ：表示它是为 x86-64 架构编译的。
dynamically linked ：表示这是一个动态链接的可执行文件。
not stripped ：表示符号信息没有被剥离，可以使用调试工具查看。
readelf
root@LAPTOP-GT06V0GS:/mnt/d/CSLab/osCourse/lec2/test_out# readelf -h a.out
ELF Header:
Magic: 7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
Class: ELF64
Data: 2's complement, little endian
Version: 1 (current)
OS/ABI: UNIX - System V
ABI Version: 0
Type: DYN (Position-Independent Executable file)
Machine: Advanced Micro Devices X86-64
Version: 0x1
Entry point address: 0x1080
Start of program headers: 64 (bytes into file)
Start of section headers: 14520 (bytes into file)
Flags: 0x0
Size of this header: 64 (bytes)
Size of program headers: 56 (bytes)
Number of program headers: 13
Size of section headers: 64 (bytes)
Number of section headers: 31
Section header string table index: 30Entry point address ：程序的入口点地址。
Type ：文件类型，这里是可执行文件（ EXEC ）。
Machine ：目标架构，这里是 x86-64。
objdump反汇编(部分)
root@LAPTOP-GT06V0GS:/mnt/d/CSLab/osCourse/lec2/test_out# objdump -d a.out
a.out: file format elf64-x86-64
Disassembly of section .init:
0000000000001000 <_init>:
1000: f3 0f 1e fa endbr64
1004: 48 83 ec 08 sub $0x8,%rsp
1008: 48 8b 05 e1 2f 00 00 mov 0x2fe1(%rip),%rax # 3ff0 <__gmon_start__@Base>
100f: 48 85 c0 test %rax,%rax
1012: 74 02 je 1016 <_init+0x16>
1014: ff d0 call *%rax
1016: 48 83 c4 08 add $0x8,%rsp
101a: c3 retDisassembly of section .init ：显示 .init 段的反汇编代码。
每行包含地址、机器码和汇编指令。
nm查看符号表(部分)
root@LAPTOP-GT06V0GS:/mnt/d/CSLab/osCourse/lec2/test_out# nm a.out
0000000000003da8 d _DYNAMIC
0000000000003fa8 d _GLOBAL_OFFSET_TABLE_
0000000000002000 R _IO_stdin_used
w _ITM_deregisterTMCloneTable
w _ITM_registerTMCloneTable
U _ZNSolsEPFRSoS_E@GLIBCXX_3.4
0000000000002012 r _ZNSt8__detail30__integer_to_chars_is_unsignedIjEE
0000000000002013 r _ZNSt8__detail30__integer_to_chars_is_unsignedImEE
0000000000002014 r _ZNSt8__detail30__integer_to_chars_is_unsignedIyEE
U _ZSt21ios_base_library_initv@GLIBCXX_3.4.32
0000000000004040 B _ZSt4cout@GLIBCXX_3.4
U _ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_@GLIBCXX_3.4
U _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc@GLIBCXX_3.4
00000000000020f8 r __FRAME_END__
0000000000002018 r __GNU_EH_FRAME_HDR
0000000000004010 D __TMC_END__
000000000000038c r __abi_tagd ：表示该符号是一个局部（data）符号，通常是变量。
U ：表示该符号是一个未定义的符号，通常是在其他目标文件中定义的符号。
strings提取字符串(部分)
root@LAPTOP-GT06V0GS:/mnt/d/CSLab/osCourse/lec2/test_out# strings a.out
/lib64/ld-linux-x86-64.so.2
__gmon_start__
_ITM_deregisterTMCloneTable
_ITM_registerTMCloneTable
_ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_
_ZNSolsEPFRSoS_E
_ZSt21ios_base_library_initv
_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
_ZSt4cout
__libc_start_main
__cxa_finalize
libstdc++.so.6
libc.so.6
GLIBCXX_3.4.32
GLIBCXX_3.4
GLIBC_2.34
GLIBC_2.2.5
PTE1
u+UH
Hello, World!toybox-0.1.0：这是早前版本的 toybox，包含一些 “最小” 系统所需的工具。现在，Android 内置了 toybox。当你打开手机的 “开发者模式” 后，通过 adb shell 连接到手机，其中的命令行工具就是 toybox。
实验省略了...看不懂
strace：
输出hello world了...不知道这是不是本意，课上看老师的输出好像不长这样啊！
root@LAPTOP-GT06V0GS:/mnt/d/CSLab/osCourse/lec2/strace# ./minimal
Hello, World!root@LAPTOP-GT06V0GS:/mnt/d/CSLab/osCourse/lec2/strace# strace ./minimal
execve("./minimal", ["./minimal"], 0x7ffe636aaf40 /* 33 vars */) = 0
write(1, "Hello, World!", 13Hello, World!) = 13
exit(0) = ?
+++ exited with 0 +++execve ：加载并运行程序。
write ：写入数据到文件描述符。
exit_group ：退出程序。
调试和分析通过 strace 的输出，你可以看到程序执行的所有系统调用及其参数和返回值。这有助于调试程序行为和理解程序与操作系统之间的交互。
于是乎可以借助 AI 又理解了！
对于冗长的 strace...仍然可以借助 AI 添加一些 optional 选项来进行优化！
...
3.6. Computer Science 是无门槛复制工具的人造科学
在 AI 的辅助下，你与 “顶尖人类” 的差距可以很小
instead of 基础科学...
3.7. 正确的工具
打开程序的执行：Trace (追踪)
In general, trace refers to the process of following anything from the beginning to the end. For example, the traceroute command follows each of the network hops as your computer connects to another computer.
System call trace (strace)
“理解程序是如何与操作系统交互的”
(观测状态机执行里的 syscalls)
Demo: 试一试最小的 Hello World
任何时候都不要犯懒...
蒋老师一直强调，AI时代，更应该多动手，在你不想动脑子的时候，不妨多问，随时随地大小问！
AI是最好的老师。
4. 课后作业
大部分的课后作业都在 WSL一一实现了，途中询问了 Kimi 许多问题...有的没的
有一个比较有意思的这里贴出来
int f(int n) { return (n <= 1) ? 1 : f(n - 1) + g(n - 2); }
int g(int n) { return (n <= 1) ? 1 : f(n + 1) + g(n - 1)将递归函数 f 和 g 转换为非递归形式的代码
4.1. 手动维护一个栈
#include <iostream>
#include <stack>
using namespace std;
int f(int n) {
stack<pair<int, char>> s; // 用于模拟递归调用的栈
s.push({n, 'f'}); // 初始调用 f(n)
int result = 0;
while (!s.empty()) {
auto [current_n, func] = s.top();
s.pop();
if (current_n <= 1) {
result += 1; // 基本情况，直接返回 1
} else {
if (func == 'f') {
s.push({current_n - 1, 'f'}); // 模拟 f(n-1)
s.push({current_n - 2, 'g'}); // 模拟 g(n-2)
} else if (func == 'g') {
s.push({current_n + 1, 'f'}); // 模拟 f(n+1)
s.push({current_n - 1, 'g'}); // 模拟 g(n-1)
}
}
}
return result;
}
int main(void) {
int n = 5; // 示例输入
cout << "f(" << n << ") = " << f(n) << endl;
return 0;
}4.2. 代码解释
栈的使用：
使用 stack<pair<int, char>> 来模拟递归调用。 pair<int, char> 中的 int 表示当前函数的参数， char 表示当前调用的是 f 还是 g 。
初始时将 f(n) 推入栈中。
循环处理栈：
每次从栈顶取出一个元素，根据其函数类型（ f 或 g ）和参数值进行处理。
如果当前参数值满足基本情况（ n <= 1 ），直接将结果累加到 result 中。
否则，根据函数类型将后续调用的参数和函数类型推入栈中，模拟递归调用。
结果累加：
每次从栈中处理一个元素时，如果满足基本情况，将结果累加到 result 中。
最终， result 就是 f(n) 的结果。
4.3. 这不还是递归吗？？
kimi 还是无法胜任，追问后给出了偷懒解法...
4.4. 迭代
#include <iostream>
#include <vector>
using namespace std;
int f(int n) {
if (n <= 1) return 1;
vector<int> f_values(n + 1, 0); // 存储 f(i) 的值
vector<int> g_values(n + 1, 0); // 存储 g(i) 的值
// 初始化基本情况
f_values[0] = 1;
f_values[1] = 1;
g_values[0] = 1;
g_values[1] = 1;
// 通过迭代计算 f(i) 和 g(i)
for (int i = 2; i <= n; ++i) {
f_values[i] = f_values[i - 1] + g_values[i - 2];
g_values[i] = f_values[i + 1] + g_values[i - 1];
}
return f_values[n];
}
int main(void) {
int n = 5; // 示例输入
cout << "f(" << n << ") = " << f(n) << endl;
return 0;
}从 g(0) g(1) 开始迭代....逐步推进....
Last updated