前置知识

在 Tacos 中关于 lab2 的文档实在是少得可怜，对于实现细节以及需要的背景知识的介绍都不甚清楚，再加上运行过程中各种各样奇奇怪怪的报错，使得这个 lab 要比 lab1 难上很多。因此，在这篇文章内我想先总结一下可能需要的背景知识以及在实现过程中我遇到的报错。

线性规划基础

线性规划指的是目标函数以及约束条件都是线性函数时的最优化问题。对于最一般的情况，我们可以用如下的形式刻画要解决的问题：

• 目标函数： $c(x_1, \cdots, x_n)=\sum_{j=1}^n c_j x_j$，我们想要最大化（或者最小化也可以）它，这里 $c_i$ 可正可负。
• 约束条件： $\sum_{j=1}^n a_{ij}x_j\le b_i$ （当然，$\ge$ 或者 $=$ 也是可以的，它们都可以用 $\le$ 表示）。有 $m$ 条约束条件（$a$ 的下标就是这么来的）。
• 对于变量的非负性约束：有些 $x_i$ 可以随便取，但是有些 $x_i$ 不能小于 $0$。（其实规定所有变量必须不低于 $0$ 是等价的）

这个模型有些复杂，它可以被规约到一个难度完全相同，但是表达形式更简单的问题。我们称这种最简形式为标准型：

• 目标函数：$c(x_1, \cdots, x_n)=\sum_{j=1}^n c_jx_j$​，我们想要最大化它。
• 约束条件：$\sum_{j=1}^n a_{ij}x_j=b_i$。（全部改成 $\le$ 则被称作松弛型线性规划）
• 对于变量的非负性约束：$\forall i, x_i\ge 0$​​​。

之后将系数 $a_{ij}$ 合并为矩阵 $\mathbf A\in M_{m\times n}$，将目标函数的系数合并为列向量 $\mathbf c=(c_1, \cdots, c_n)^\top$

有感而发的小东西，点子不错，文笔有限。

一点碎碎念

操作系统的 lab 相比于 ics 的 lab 难度明显上了一个档次，里面可能踩的坑实在是太多了！！而且对于新编写出的 rust 版本的操作系统，没有前人的足迹可以追寻，在写的时候也可能出现各种各样莫名其妙的问题。这篇文章权当一个小小的指北吧。我只会列出每个任务的设计思路。

首先我想列出在写这个 lab 之前，我们应该达成的几点“共识”（要不然这 lab 没法写了）

• 多线程中常用 Mutex<> 来确保对关键数据访问的独一性。它有一个优点是不需要 Mutex 本身可变就可以修改里面的数据，同时可以很安全地被多个线程访问。

• std 是没法用的，但是 rust 很贴心地帮我们在 alloc 里面实现了很多有用的工具，比如 Vec, BinaryHeap, BTreeMap 等等。需要注意的是 rust 中没有与 multiset 类似的数据结构。

• 在这个 lab 中，我们只需要考虑单核 cpu 的情况。虽然整个系统看上去很多很多部分都是并行的，但实际上这些代码在某个时刻只会有一行正在被执行。

• 这个 lab 的核心是维护不同线程的切换，线程的切换涉及以下几种情况：

  1. 主动调用了 schedule 函数：将当前线程放回 ready 线程列表中，切换上下文，将执行权交给下一个线程。
  2. 一个线程被唤醒了，且它比当前正在运行的线程具有更高的优先级。
  3. 程序主动更改了一个线程的优先级（注意：这个线程一定是当前正在运行的线程！这个 lab 里面不需要实现更改其它线程的优先级），并且使得处于 ready 列表的线程中，存在一个线程的优先级更高。
  4. 一个线程请求了一个未被释放的锁。
  5. time interrupt。在内核中有一个计时器与一个切换阈值，如果距离上次切换的时间长于这个阈值，那么操作系统会触发一次 time interrupt 陷阱。如果不关闭 time interrupt，这个陷阱内会执行一次 schedule。因此如果要从系统层面上确保当前操作是原子的，需要关闭 time interrupt（关上这个之后甚至连 tick 都不会调用）。每个线程都有自己独立的 time interrupt 状态。在多核 cpu 上频繁地关 interrupt 不是一个好习惯，因为所有 cpu 都会停下，效率很低。不过我们只需要考虑单核的情况，因此该关还是关吧。

• 关于 CondVar：在使用互斥锁的场景下，如果我们手持一个锁，但同时又想要等待另外一个锁被释放，此时有两种想法：

  • 不释放当前手持的锁，等待被释放的锁。好处是不会产生数据竞争，但是此时任何其他需要第一个锁的线程都会被阻塞，这样效率不高。
  • 释放当前手持的锁，等待被释放的锁。这样做有一定风险：等待此线程持有的锁的那些线程有可能会在中间插入，从而导致数据竞争。

  CondVar 就是专门针对这样的场景设计的工具，核心部分由三个函数组成：

  1. wait(cond, guard) 这里 cond 是条件变量，guard 是锁，且必须处于持有状态。这个函数可以理解为“释放锁 guard，等待条件变量 cond 被触发，再重新获取锁 guard” 的原子过程，尽管其内部实现并不是原子的。
  2. notify_one(cond) 通知一个等待这个条件变量触发的线程。如果没有线程在等待，那么这次触发将会被丢失。
  3. notify_all(cond) 通知所有正在等待这个变量触发的线程。

Pushdown Automata

下推自动机可以看作是 NFA 加入栈后的拓展版本。与 NFA 相比，PDA 的定义中多了一个“栈”的概念，一个 PDA 由六元组 $(Q, \Sigma, \Gamma, \delta, q_0, F)$ 组成。其中：

• $Q, \Sigma, q_0, F$​ 与 NFA 的定义完全一致，它们分别表示状态，字符集，起始节点，接受节点集。
• $\Gamma$ 是栈字符集，它规定了栈中的每个元素可能是什么。我们常常通过往栈中压入或者弹出一个 $ 来确保当前栈是空的。
• $\delta$ 同样是转移函数，但它与 NFA 的区别是引入了栈的状态。$\delta$ 函数接受当前状态、当前栈顶以及一个字符（当然，可以是空串 $\epsilon$），它的输出是一个目标节点以及对当前栈的操作（不从栈顶读字符并压入一个字符、弹出一个字符、更改栈顶字符或者保持栈不动）。更为形式化地说，$\delta$ 的定义是 $Q\times \Sigma_{\epsilon}\times \Gamma_{\epsilon}\to Q\times \Gamma_{\epsilon}$​（输入栈顶即将被替换的那个字符，输出新的栈顶）。

其实主要是一些页面元素的备忘录，我太容易搞忘了 0. 0

这个主题好像是支持 Bulma 的，也就是说可以直接向 .md 文件里面插入它支持的 html 元素。

分栏显示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

<div class="columns">
  <div class="column">
    <article class="message is-primary">
      <div class="message-header">
        <p>这里是第一列</p>
      </div>
      <div class="message-body">
        这里有一些内容
      </div>
    </article>
  </div>
  <div class="column">
    哇，这里能递归吗
  </div>
</div>