2022 操作系统期中测验
⚠️ 学术诚信
请自觉遵守学术诚信
禁止与他人讨论、询问或透露任何与测验相关的信息。 请确保你交卷 (不再提交) 后再观看课程视频直播。 - 简答题:
禁止查阅任何资料。 - 编程题:
允许使用手册 (manpages, API references 等);请主动避开自己先前编写的代码和教科书/课程网站上的示例代码等。 期中测验分数由 Online Judge 给出。为了鼓励大家的诚信行为:
- 简答题提交成功获得 45% 分数,提交正确获得额外 5%
- 编程题提交成功获得 45% 分数,提交正确获得额外 5%
- 请不要为 1 分的总评 (折合小于 < 0.002 GPA) 出卖自己的灵魂
⚠️ 提交时间
测验时间:10:10 - 12:00 (服务器已经完成时间同步;以此时间段内收到的提交为准)
注意 Online Judge 30 分钟内只能提交 3 次;以得分高的为准。请大家在本地完成好测试和检查;请不要面向 Online Judge 编程。
1. 简答题
现有如下代码:
int volatile sum = 0;
void do_sum() {
int t;
/* 1 */ t = sum;
/* 2 */ t += 1;
/* 3 */ sum = t;
/* 4 */ t = sum;
/* 5 */ t += 1;
/* 6 */ sum = t;
/* 7 */ t = sum;
/* 8 */ t += 1;
/* 9 */ sum = t;
}
有两个线程 T1
和 T2
均执行 do_sum
代码 (共享 sum
变量)。假设线程每次按 1, 2, 3, ... 9 顺序执行一条语句,且读/写会立即在共享内存中生效。例如,若两个线程以如下顺序执行语句,即相当于 T1
执行完后再执行 T2
:
T1.1 T1.2 T1.3 T1.4 T1.5 T1.6 T1.7 T1.8 T1.9
T2.1 T2.2 T2.3 T2.4 T2.5 T2.6 T2.7 T2.8 T2.9
将得到 sum = 6
(但这显然不是最小值)。你需要给出使 sum
最小化的一个线程执行顺序 (T1
和 T2
可以交错执行)。
2. 编程题
假设我们需要对很多 $x$ ($x > 0$) 计算 $f(x)$ 的和。每个 $f(x)$ 都可能会计算较长的时间。你需要在 thread.h 和 thread-sync.h (Online Judge 会使用此实现) 的基础上实现不少于 4 个 worker 线程的并行处理:
- 所有待处理的 $x$ 都是
int
类型,从标准输入 (stdin) 读入直到输入结束 - 对每一个整数 $x$,都调用来自外部的
long f(int x);
计算,这个函数是线程安全的 - 你的程序需要输出所有
f(x)
的和 (保证和不超过long
的范围),并正常终止 - 你需要尽快处理来自 stdin 的输入 (读入以后统一处理将导致 Time Limit Exceeded)
- 个别的
f(x)
可能会消耗较长的时间,请确保此时在有待计算的 $x$ 时其他线程不会被闲置
注意:编程时请自觉仅使用手册,不要参考已有的代码或教科书等材料。
3. 提交方法
首先,将编程题和简答题的答案保存在/* */
中,TX.X
之间可以任意空格/换行分割,midterm-example.c 是一个 Online Judge 可以接收但无法得到满分的示例代码。注意Online Judge 将以文本中首次出现的 /* */
为准。评测环境为 x86-64。
通过命令行提交 (
$ curl http://jyywiki.cn/upload -F course=OS2022 -F module=Midterm \
-F token=你的TOKEN -F file=@你要提交的.c文件路径