26/1/16
约 1617 字大约 5 分钟
2026-01-16
昨日OS补完
昨天OS写的太草率，光吹牛忘讲正事了。
昨天学的主要是进程，进程的定义早就被讲烂了：“操作系统为正在运行的程序提供的抽象”。主要梳理一下细一点的概念。
进程有三种状态：
- 运行
- 就绪
- 阻塞
众所周知，计算机可以同时运行多个程序，但一个处理器只能同时存在一个运行中的进程。我们使用时分共享技术，提供了存在多个虚拟CPU的假象（我当然知道现代CPU是多核的），这跟计网的时分复用非常相像。上下文切换就是最经典的分时机制，它使得当一个进程被阻塞时（比如等待IO），CPU可以切换到另一个就绪的进程上运行。
根据OSTEP提供的模拟程序 cpu-intro/process-run.py ，我们可以探究到一些进程切换的策略。
第一种： -I IO_RUN_LATER
sherlock@ShenzhenCoast:~/ostep/ostep-homework/cpu-intro$ python3 process-run.py -l 3:0,5:100,5:100,5:100 -S SWITCH_ON_IO -I IO_RUN_LATER -c -p
Time PID: 0 PID: 1 PID: 2 PID: 3 CPU IOs
1 RUN:io READY READY READY 1
2 BLOCKED RUN:cpu READY READY 1 1
3 BLOCKED RUN:cpu READY READY 1 1
4 BLOCKED RUN:cpu READY READY 1 1
5 BLOCKED RUN:cpu READY READY 1 1
6 BLOCKED RUN:cpu READY READY 1 1
7* READY DONE RUN:cpu READY 1
8 READY DONE RUN:cpu READY 1
9 READY DONE RUN:cpu READY 1
10 READY DONE RUN:cpu READY 1
11 READY DONE RUN:cpu READY 1
12 READY DONE DONE RUN:cpu 1
13 READY DONE DONE RUN:cpu 1
14 READY DONE DONE RUN:cpu 1
15 READY DONE DONE RUN:cpu 1
16 READY DONE DONE RUN:cpu 1
17 RUN:io_done DONE DONE DONE 1
18 RUN:io DONE DONE DONE 1
19 BLOCKED DONE DONE DONE 1
20 BLOCKED DONE DONE DONE 1
21 BLOCKED DONE DONE DONE 1
22 BLOCKED DONE DONE DONE 1
23 BLOCKED DONE DONE DONE 1
24* RUN:io_done DONE DONE DONE 1
25 RUN:io DONE DONE DONE 1
26 BLOCKED DONE DONE DONE 1
27 BLOCKED DONE DONE DONE 1
28 BLOCKED DONE DONE DONE 1
29 BLOCKED DONE DONE DONE 1
30 BLOCKED DONE DONE DONE 1
31* RUN:io_done DONE DONE DONE 1
Stats: Total Time 31
Stats: CPU Busy 21 (67.74%)
Stats: IO Busy 15 (48.39%)第二种： -I IO_RUN_IMMEDIATE
sherlock@ShenzhenCoast:~/ostep/ostep-homework/cpu-intro$ python3 process-run.py -l 3:0,5:100,5:100,5:100 -S SWITCH_ON_IO -I IO_RUN_IMMEDIATE -c
-p
Time PID: 0 PID: 1 PID: 2 PID: 3 CPU IOs
1 RUN:io READY READY READY 1
2 BLOCKED RUN:cpu READY READY 1 1
3 BLOCKED RUN:cpu READY READY 1 1
4 BLOCKED RUN:cpu READY READY 1 1
5 BLOCKED RUN:cpu READY READY 1 1
6 BLOCKED RUN:cpu READY READY 1 1
7* RUN:io_done DONE READY READY 1
8 RUN:io DONE READY READY 1
9 BLOCKED DONE RUN:cpu READY 1 1
10 BLOCKED DONE RUN:cpu READY 1 1
11 BLOCKED DONE RUN:cpu READY 1 1
12 BLOCKED DONE RUN:cpu READY 1 1
13 BLOCKED DONE RUN:cpu READY 1 1
14* RUN:io_done DONE DONE READY 1
15 RUN:io DONE DONE READY 1
16 BLOCKED DONE DONE RUN:cpu 1 1
17 BLOCKED DONE DONE RUN:cpu 1 1
18 BLOCKED DONE DONE RUN:cpu 1 1
19 BLOCKED DONE DONE RUN:cpu 1 1
20 BLOCKED DONE DONE RUN:cpu 1 1
21* RUN:io_done DONE DONE DONE 1
Stats: Total Time 21
Stats: CPU Busy 21 (100.00%)
Stats: IO Busy 15 (71.43%)可以看到两种策略中，CPU Busy的比例完全不一样，运行程序耗时也更少。所以有结论：IO密集型任务更适合使用“IO_RUN_IMMEDIATE”策略，因为它能更有效地利用CPU资源，减少等待时间；我们也猜测CPU密集型任务则可能更适合“IO_RUN_LATER”策略，以避免频繁的上下文切换带来的开销。
算法竞赛
打了一场 牛客小白月赛 ，前三道送分，第四道用的方法不够妙，第五道没做出来树形DP不会推。
D. Flower_Rainbow_and_Balloon
我的思路是记录前缀和，然后暴力枚举区间二分寻找答案。
bool check(int mid) {
if (mid == 0) return false;
for (int i = 0; i + mid - 1 < n; ++i) {
int end = i + mid - 1;
int R = prer[end] - (i > 0 ? prer[i - 1] : 0);
int Y = prey[end] - (i > 0 ? prey[i - 1] : 0);
int W = mid - R - Y;
int base = max(2 * R + Y, R + 2 * Y);
int add = 2 * min(m, W);
int total = base + add;
if (total >= k) return true;
}
return false;
}
int solve() {
cin >> n >> m >> k;
scanf("%s", str);
for (int i = 0; i < n; ++i) {
if (i == 0) {
prer[i] = (str[i] == 'r');
prey[i] = (str[i] == 'y');
} else {
prer[i] = prer[i - 1] + (str[i] == 'r');
prey[i] = prey[i - 1] + (str[i] == 'y');
}
}
int l = 0, r = n;
int ans = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}当然也可以使用官解滑动窗口的思路，同样是二分，但是每次 check() 时使用滑动窗口的方法。
八数码
这是在罗勇军的书上看到的，本身其实就是对于不同状态的BFS，但是每次判重时间复杂度是 O(n!) ，这太高了，所以会需要其它技术来优化，比如康托展开、双向BFS等。
康托展开还没细看。
双向BFS
参照他的书上的比喻，讲两颗石头丢入水中，波纹汇聚的地方就是最优路径交汇的地方。如果要用这个思路解决八数码问题，我们选择从初始状态与完成状态同时开始BFS，再结合康托展开技巧进行判重，就能大幅提升效率。
计算机网络
Networking的知识点确实繁杂，各种概念层出不穷。既然协议分层本身就为我们提供了个非常好的做思维导图的思路，我再次开坑，绝对会做个计网思维导图出来的。
网络应用原理
简单阐述一下概念。
首先是应用体系结构，这个名字着实抽象，但我要是告诉你应用体系结构分为 client-server architecture 和 P2P architecture ，你大概就知道这是什么了。网络通信的主体其实是进程，不同端操作系统的进程，通过跨越计算机网络交换报文，实现通信。进程与计算机网络之间的接口就是socket，它只负责应用层与运输层之间的通信，至于运输层如何，它只能管到协议选择和一点点运输层参数。这样的设计就是十分优雅，因为它将复杂性隔离开来，让应用层开发者不需要关心运输层的实现细节。对于某一层，只要该层对其上面的层提供相同的发服务，并且使用下面的层的相同服务，当某层的实现变化时，系统的其余部分可以保持不变。
协议分层
- 应用层
- 运输层
- 网络层
- 链路层
- 物理层