Yanyan's Wiki 软件工程研究入门 (2022)

2022 操作系统期中测验

⚠️ 学术诚信

请自觉遵守学术诚信

  • 禁止与他人讨论、询问或透露任何与测验相关的信息。
  • 请确保你交卷 (不再提交) 后再观看课程视频直播。
  • 简答题:禁止查阅任何资料。
  • 编程题:允许使用手册 (manpages, API references 等);请主动避开自己先前编写的代码和教科书/课程网站上的示例代码等。

期中测验分数由 Online Judge 给出。为了鼓励大家的诚信行为:

  • 简答题提交成功获得 45% 分数,提交正确获得额外 5%
  • 编程题提交成功获得 45% 分数,提交正确获得额外 5%
  • 请不要为 1 分的总评 (折合小于 < 0.002 GPA) 出卖自己的灵魂

⚠️ 提交时间

测验时间:10:10 - 12:00 (服务器已经完成时间同步;以此时间段内收到的提交为准)

注意 Online Judge 30 分钟内只能提交 3 次;以得分高的为准。请大家在本地完成好测试和检查;请不要面向 Online Judge 编程。

OS2022-Midterm 提交结果

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;
}

有两个线程 T1T2 均执行 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 最小化的一个线程执行顺序 (T1T2 可以交错执行)。

2. 编程题

假设我们需要对很多 $x$ ($x > 0$) 计算 $f(x)$ 的和。每个 $f(x)$ 都可能会计算较长的时间。你需要在 thread.hthread-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. 提交方法

首先,将编程题和简答题的答案保存在一个 .c 文件中,其中简答题的答案 (线程执行顺序) 写在 /* */ 中,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文件路径
Creative Commons License    苏 ICP 备 2020049101 号