Xv6 kernel Spinlock

Xv6操作系统内核为我们提供了两类锁：自旋锁（spinlock）和睡眠锁（sleeplock）。它们虽然都有锁的特性，但是它们具有不同的特点，应用场景也不相同。

今天我们先来讨论xv6内部spinlock的实现，首先来看 spinlock.h 内对spinlock的声明：

1
2
3
4
5
6
7
8

// Mutual exclusion lock.
struct spinlock {
  uint locked;       // Is the lock held?

  // For debugging:
  char *name;        // Name of lock.
  struct cpu *cpu;   // The cpu holding the lock.
};

十分简单，不是吗？除去debugging部分，就一个变量 locked 记录这个lock是否被某个CPU给占用。

在xv6中，lock的locked字段为0表示该lock没有被占用，字段为1表示该lock被占用了。

这可以通过 spinlock.c 中的 initlock 方法看出：

1
2
3
4
5
6
7

void
initlock(struct spinlock *lk, char *name)
{
  lk->name = name;
  lk->locked = 0;
  lk->cpu = 0;
}

对于一个给定的 spinlock ，我们需要一组函数 acquire 和 release 来分别获取与释放锁。

对于 acquire 方法，我们需要检测当前锁的 locked 变量值，若为1则继续循环（这就是自旋这个词的由来），为0则获取锁，将 locked 更改为1。

因为 spinlock 本身就是共享资源（即多个CPU的多个进程共享内存中的同一个资源），任何进程对同一个自旋锁需要互斥地访问。因此以下 for 循环体内部的代码需要转换为原子操作：

1
2
3
4
5
6
7
8
9

void acquire(struct spinlock *lk)  
{
	for(;;) {
		if(lk->locked == 0) {
			lk->locked = 1;
			break;
		}
	}
}

这里的 for 就是自旋。

xv6使用了RISCV的 amoswap 指令。从字面意义上看，就是原子交换操作。

具体来讲，xv6在acquire内部使用了指令 amoswap.w.aq a5, a5, (s1) 。这段指令的含义是从内存地址 (s1) 中读取一个32位的值（根据amoswap.w.aq 中第一个点后的 w 看出，实际上内存地址 (s1)对应的是 spinlock 中 uint 类型（刚好32位）的 locked 值），与寄存器 a5 内部存储的值进行交换。寄存器 a5 存的值在执行该指令之前就被设置为1了。也就是说，交换过后的 locked 值必然为1，而代码会根据交换过后的寄存器 a5 的值是否为0来获取锁。

来看看xv6内部 acquire 的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// Acquire the lock.
// Loops (spins) until the lock is acquired.
void
acquire(struct spinlock *lk)
{
  push_off(); // disable interrupts to avoid deadlock.
  if(holding(lk))
    panic("acquire");

  // On RISC-V, sync_lock_test_and_set turns into an atomic swap:
  //   a5 = 1
  //   s1 = &lk->locked
  //   amoswap.w.aq a5, a5, (s1)
  while(__sync_lock_test_and_set(&lk->locked, 1) != 0)
    ;

  // Tell the C compiler and the processor to not move loads or stores
  // past this point, to ensure that the critical section's memory
  // references happen strictly after the lock is acquired.
  // On RISC-V, this emits a fence instruction.
  __sync_synchronize();

  // Record info about lock acquisition for holding() and debugging.
  lk->cpu = mycpu();
}

重点在于 __sync_lock_test_and_set(&lk->locked, 1) 这个函数。通过 gdb 可以看出其对应的汇编代码：

在这里我们看到了我们熟悉的 amoswap 指令。

另外，后面一行的 __sync_synchronize(); 是一个栅栏指令，它用于告诉编译器不要对指令进行重新排序以进行优化。

例如以下场景：

1
2
3

acquire(&lock);
x = 1;
release(&lock);

通过编译器优化，可能会重排指令，把 x=1 放到加锁前或者释放锁之后。这显然是不被允许的。

__sync_synchronize(); 的作用是强制将其前后的 load/store 指令进行分隔。因此acquire 函数与 release 函数内部使用了该指令来保证 x=1 不会跑出去。

另外，acquire 函数开头调用了 push_off() 方法。根据注释说明，它是关闭了中断。

我操？为啥要关闭中断？这个锁跟中断有什么勾八关系？

这个其实是xv6内部实现的问题。因为在xv6内部，有一些设备中断会和内核内部的代码使用同一个 spinlock ，例如 xv6 book 提到的 tickslock ，用于保护各CPU时钟内部的 ticks 时间帧的不变量。

对于计时器中断，会调用下面函数：

1
2
3
4
5
6
7
8

void
clockintr()
{
  acquire(&tickslock);
  ticks++;
  wakeup(&ticks);
  release(&tickslock);
}

但是xv6的sleep系统调用也使用了该锁：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

uint64
sys_sleep(void)
{
  int n;
  uint ticks0;

  argint(0, &n);
  acquire(&tickslock);
  ticks0 = ticks;
  while(ticks - ticks0 < n){
    if(killed(myproc())){
      release(&tickslock);
      return -1;
    }
    sleep(&ticks, &tickslock);
  }
  release(&tickslock);
  return 0;
}

这会出现什么问题？

假设 sys_sleep 首先获取了 tickslock ，然后进入了 sleep(&ticks, &tickslock) 进入阻塞状态。

然后对应的CPU的计时器产生中断，想获取锁，但是被阻止，因此进入自旋。

但是只有计时器获取了锁，才能进入临界区，执行 ticks++; 来增加时间戳，从而才有 sys_sleep 从阻塞状态恢复的可能。

也就是说，产生了死锁。

为了防止这种情况，我们应当防止一个 spinlock 在能被中断处理函数获取时，在获取期间允许中断。xv6为了实现方便，直接对所有的 spinlock 在被占用时，直接关闭了中断。并在对应的 release 函数尾部重新开放中断：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

// Release the lock.
void
release(struct spinlock *lk)
{
  if(!holding(lk))
    panic("release");

  lk->cpu = 0;

  // Tell the C compiler and the CPU to not move loads or stores
  // past this point, to ensure that all the stores in the critical
  // section are visible to other CPUs before the lock is released,
  // and that loads in the critical section occur strictly before
  // the lock is released.
  // On RISC-V, this emits a fence instruction.
  __sync_synchronize();

  // Release the lock, equivalent to lk->locked = 0.
  // This code doesn't use a C assignment, since the C standard
  // implies that an assignment might be implemented with
  // multiple store instructions.
  // On RISC-V, sync_lock_release turns into an atomic swap:
  //   s1 = &lk->locked
  //   amoswap.w zero, zero, (s1)
  __sync_lock_release(&lk->locked); 

  pop_off();
}

这里的 pop_off 方法就是开放中断。

在 spinlock 被占用期间关闭中断有以下好处：一个 spinlock 不应当被占用太久。因此在处理一个关键的任务时，对其加锁，会阻止时间片轮转，使该进程能享受所有CPU资源来集中处理当前任务，这样的化 spinlock 就不会自旋太久。

但是如果我们在某些代码中可能会同时获取多个锁，对应的会释放多个锁。那么我们在释放第一个锁的时候，是不能直接开放中断的，要等所有锁被释放后才能中断。

因此我们对于每个CPU都要有一个计数器，来统计当前CPU获取了多少个锁。关于每个CPU的结构体声明在 proc.h 下：

1
2
3
4
5
6
7

// Per-CPU state.
struct cpu {
  struct proc *proc;          // The process running on this cpu, or null.
  struct context context;     // swtch() here to enter scheduler().
  int noff;                   // Depth of push_off() nesting.
  int intena;                 // Were interrupts enabled before push_off()?
};

这里的 noff 字段就是我们需要的计数器。而 intena 则代表着获取第一个锁之前，CPU的中断状态。

接下来我们来看 push_off 和 pop_off 方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

// push_off/pop_off are like intr_off()/intr_on() except that they are matched:
// it takes two pop_off()s to undo two push_off()s.  Also, if interrupts
// are initially off, then push_off, pop_off leaves them off.

void
push_off(void)
{
  int old = intr_get();

  intr_off();
  if(mycpu()->noff == 0)
    mycpu()->intena = old;
  mycpu()->noff += 1;
}

void
pop_off(void)
{
  struct cpu *c = mycpu();
  if(intr_get())
    panic("pop_off - interruptible");
  if(c->noff < 1)
    panic("pop_off");
  c->noff -= 1;
  if(c->noff == 0 && c->intena)
    intr_on();
}

可以发现，一切都清晰了很多。在 push_off 中，如果第一次获取锁，我们会先记录一下当前的中断状态。方法是调用 intr_get ，它在 riscv.h 中声明：

1
2
3
4
5
6
7

// are device interrupts enabled?
static inline int
intr_get()
{
  uint64 x = r_sstatus();
  return (x & SSTATUS_SIE) != 0;
}

这里的 SSTATUS 是一个特殊的寄存器，里面有 SIE bit 来记录是否开启中断，有 SPP bit 来记录当前mode是user mode还是 supervisor mode。在这里我们只需要 SIE bit 就行啦。

关于 spinlock 在xv6的实现细节，就讲这么多。

五月份了，得开始准备专业课的笔面试了~

主要问题来自于各类经验贴。持续更新

数学

复习资料整理：

https://zhuanlan.zhihu.com/p/567252248?utm_id=0

线性代数

问：特征值为0，和矩阵的秩有什么关系。

答： 矩阵的秩等于其非零特征值的数目。

拓展：对于对称矩阵A，其特征值都是实数。可进行特征分解：。若A满秩，则U的列向量构成线性空间 的一组正交基。

问：半正定矩阵的特征和性质。

答：其对应的二次型 对于任意的向量 皆非负，其特征值也非负。

拓展：如果是正定矩阵的话，其对应的二次型为0等价于 为零向量，其特征值都是正的，即满秩。正定矩阵对应于线性空间 上的一个椭球面。

概率论

问：说一下先验概率和后验概率。

答：

问：贝叶斯、全概率、条件概率

答：

问：大数定律是什么

答：

离散数学

问：给你一个真值表，如何推出真值表达式。

答：找出输出端为1的各行，每行的输入变量作乘，1为变量本身，0为变量取非，最后把各式进行求和即可。

问：一个有向图是有向树的条件

答：1.只有一个结点入度为0；2.边数为点数减一。

问：说出偏序、全序、良序的定义

答：

问：集合的划分、集合的基数、无穷集合的比较、单射、满射、等价关系、偏序关系、全序关系、布尔格、欧拉图、哈密顿图、树的定义、有向边树的定义。

答：逆天

高数

问：函数的极限定义。导数的定义。

答：设函数 在点 的某一去心邻域有定义，若存在常数a，对于任意给定的正数 ，都存在 使不等式 在 时恒成立，则a为函数 当 时的极限。

（白话：某个点的极限就是一个常数，该点的某个去心邻域内部的点的函数值都满足和该常数的差的绝对值小于任意小的正数）

问：一致性的定义。

答：

问：拉格朗日中值定理是什么

答：这个定理主要解释的是”平均变化率等于瞬时变化率“。具体来讲，如果函数满足在某个闭区间[a,b]上可导，在开区间(a,b)上连续，那么在开区间(a,b)上必存在一个点使得该点的导数等于平均变化率，即 。

问：介绍一下间断点。

答：间断点就是非连续点，即不满足函数极限等于函数值的点。根据左右极限将间断点分为第一类和第二类间断点，第一类间断点左右极限相等，但不等于函数值；第二类间断点指左极限或右极限不存在的点。

408

数据结构

问：讲一下两种最小生成树算法，以及如何优化。

答：Prim基于扩展点集的方法求解，每次迭代都取出与当前已加入树的点集距离最近的点加入点集。优化方法：用一个斐波那契堆来维护权重最小的边

Kruskal基于扩展边集的方法来求解。它依次取出边权小到大的边加入树，并在此之前判断是否会出现环。优化方法：并查集判联通分量。

问：给出几种求最长回文子串的解法。

答：暴力的话，可以用类似于区间dp的东西，令 表示 是否为回文串，第一维枚举长度。

然后可以枚举中心点，向外拓展，这些都是 的。

也可以把向外拓展的那个for用二分+哈希优化一下，

一般正常做都是用manacher，。

简单介绍原理的话，就是用类似于动态规划的思想，在转移的时候维护当前右边界最靠右的回文子串。根据当前位置 与右边界的大小分类讨论，如果 更大的话直接暴力， 小的话可以用维护的回文子串来转移，然后暴力拓展。均摊 。

问：树的直径怎么求。

答：随机找一个点，dfs求出离它最远的点u。然后同理找到离u最远的点v，直径即为uv。

证明可以用反证法，画画图就知道了。

问：介绍一下Huffman编码。

答：Huffman是一种前缀编码，它基于每个字符的出现频率来贪心地构建Huffman树，然后根据不同的根到叶节点的路径来得到对应的编码。

问：哪些排序算法是稳定的，哪些不稳定

答：稳定排序算法定义：关键字相同的排列顺序在排序前后不变。

问：各种排序算法及其时间复杂度。

答：

插入排序：

• 直接插入排序（当前元素插入前面已经有序的序列，）
• 折半插入排序（优化为二分查找，但是涉及到元素移动，复杂度依然是 )
• 希尔排序（增量分组插入排序，玄学算法）

交换排序：

• 冒泡排序（相邻元素交换，使最小的值一个个"冒泡"出来，）
• 快速排序（效率基于split算法（可以刷刷力扣熟悉一下？），分治，最坏情况 ，理想情况 ）

选择排序：

• 简单选择排序（选择当前最小元素，）
• 堆排序（建堆（自底向上），然后一个一个删除根，）。

归并排序：。

基数排序：， 为关键字个数， 为队列个数。

桶排序：， 为辅助空间大小。

操作系统

问：计算机启动过程。

答：

问：中断的定义。和异常有什么不同。

答：

问：经典的wait signal写代码。这个东西很无聊，只能记得自己多练，记住一些常用模型（生产者消费者、读者写者等）

问：线程进程的区别，线程同步的方式

答：

问：操作系统的四大作用

答：抽象硬件为用户接口，使计算机易于使用；提高资源的利用率，例如多道程序设计技术；

计算机网络

问：拥塞避免和流量控制

答：拥塞避免是TCP拥塞控制中采用的一个算法，其原理是在TCP发送方拥塞窗口达到一定阈值后，线性地缓慢增加拥塞窗口，这样能够有效避免拥塞。流量控制是TCP的一种限制发送方速率的算法，TCP采用滑动窗口机制实现，TCP接收端可在返回的TCP确认报文段中根据自身情况设置发送方的接收窗口大小，来达到对发送方的流量控制。

问：路由算法

答：路由协议分为两种：内部网关协议和外部网关协议。

内部网关协议之一RIP是基于距离向量的，要求自治系统内的每一个路由器都要维护到其它AS内每一个网络的距离记录，这里的距离用跳数来度量。RIP认为距离短的路由就是好的路由，在和相邻路由器（只和相邻路由器）交换信息时会根据这个原则贪心地更新自己的距离向量。RIP存在路由环路问题。

开放路径优先OSPF是基于链路状态的，它在原本RIP距离的基础上提出了“代价”这一度量指标。OSPF路由器会产生链路状态通告LSA，采用洪泛的方式对其余同AS上的路由器进行更新，最后趋于一致。在此基础上OSPF路由器会基于LSA构建的链路状态数据库，采用类似于dijkstra的算法求出到其它网络的最短路径，并以此指定路由策略。

外部网关协议有BGP，BGP要求每个AS都至少有一个路由器作为“BGP发言人”，一个BGP发言人和其它发言人交换信息需要建立一个TCP连接，然后在此基础上交换BGP报文，交换后基于自己的策略采用相应的路由算法。

计算机组成原理

问：说一下cache。cache的替换算法有哪些？

答：

数据库

问：数据库中数据的四个特性

答：

软件工程

问：给代码，求问满足不同路径下的变量集合（黑盒）

问：给代码，求问哪行出问题，如何改进（白盒）

问：课：软件生命周期、软件开发模型（瀑布、螺旋、敏捷）并比较（各自的优点适用的场景）、软件测试方法、什么是黑白盒测试、白盒测试有哪些（语句覆盖、判断覆盖、条件覆盖、路径覆盖、判断条件覆盖）、路径覆盖是否一定是条件覆盖

答：逆天

AI

勾八东西

问：介绍一下SVM原理？

答：

问：什么是凸函数？如何判断凸函数？

答：

问：有监督学习和无监督学习区别

答：

英语

问：用英文介绍自己最满意的项目。

答：I'm sorry to say I didn't do any valuable projects during my undergraduate years. If I must say so, I will introduce a online operating-system related project proposed by MIT.

问：你觉得最骄傲的一件事情

问：介绍一下你的学校？为什么来我们学校？

问：介绍一下你的家乡？

机试

作为ACMer，也要在意机试。不要自视甚高，眼高手低。

这是我少数的能拿的出手的东西，但也不要压力太大

去年南软的四道：

1. 面向对象，考察桥接模式和抽象工厂模式
2. 前缀和
3. 环形染色问题
4. 凸包算法

太变态了，考凸包？

问：一个N个正数的集合，找出和为M的子集

答：dfs???

只输出一个方案的话可以搞个背包。

杂项

问：你如果遇到无法解决的事情会怎么办

答：如果是学习或科研方面的工作，我会借助chatgpt这类工具以及一些网络上的资源来获得解答。如果是生活中的事情，我会求助于身边人，并且通过这件事情进行反思。

问：你认为你的缺点？并如何改善

答：我是个比较敏感的人，这可能并不能算做一个严格意义上的缺点。对于一件事情，我可能会提前想象出它的结果，从而导致犹豫，造成没办法在有效的时间内做出比较有效的结果。换句话说，我不是那种敢于做出突破自我的工作的人。我认为这是因为我没有专心于行动本身，从而导致自己喜欢浪费时间胡思乱想，或许这就是 终日而思，不如须臾之所学也。

问：你认为的自己的优点有哪些？

答：我认为我的自我学习能力比较强。在大学期间，我在没有任何人带我教我的情况下从零开始入坑算法竞赛，并在自我努力下能力逐渐变强，最后获得一系列ICPC等奖项。其次我是一个兴趣驱动的人，对于我感兴趣的东西，我会花时间一步一步的去弄懂它的原理，我认为因为兴趣本身，学习才会变成一个快乐的过程。

问：介绍一下你最近了解的时政（逆天

答：阿赛jumping？好的985也不比中专差。

模拟面试

1、正交矩阵有什么性质？

答：正交矩阵和它自身的转置相乘为单位矩阵。几何意义上，它所对应的线性变换为空间中的旋转和反射，即向量在正交矩阵变换下的长度和夹角保持不变。

2、矩阵的迹有什么性质？

答：矩阵的迹为矩阵对角元的和。也是所有特征值的和。对于若干的向量或矩阵相乘所得矩阵，它们相互之间轮换得到的矩阵的迹是相等的。

3、说一下你对特征值和特征向量的理解。

答：定义上，一个方阵的特征值是满足以下方程的解 ，其中 为特征值， 为其对应的特征向量。几何意义上，特征向量在方阵A上进行线性变换等价于进行 倍的长度收缩。

在机器学习中，特征向量一般代表着矩阵的“特征信息”。例如PCA降维中，我们都是先求样本的协方差矩阵，然后进行特征分解（或者奇异值分解），将样本尽量投影到其部分特征向量（一般按特征值从大到小排序）所张成的空间上，一般认为这么降维能够最大化无监督样本的特征信息。（凭记忆瞎说的，毕竟我不是搞AI的）

4、介绍一下最短路算法及其优化。

答：单源最短路径可采用经典的dijkstra算法。dijkstra只能用在正权图上，它是基于贪心的思想：它维护一个已求出最短路值的点集和未求出最短路值的点集。构建一个数组dis来表示通过已求出点集能得到的最短路径，每次从未求出点集中找出dis最小的放到已求出点集，然后再根据该点更新dis，这样迭代下去可求出所有点的最短路。朴素算法是 的，在图稀疏的时候可以采用堆优化将复杂度变为 。

多源最短路采用floyd算法，它是基于动态规划的思想，通过枚举中转结点来转移状态：。时间复杂度为 。

5、介绍一下你的项目。

答：

ABC351E - Jump Distance Sum

题意

二维平面上有 个点，对于横纵坐标之和具有相同奇偶性的点，距离为切比雪夫距离。否则距离为0.

求所有点对之间的距离之和。

切比雪夫距离与曼哈顿距离的转换

这题我在比赛中没想出来，虽然退役了，但还是有点丢人。

其实这是个很常见的套路了：将难求的切比雪夫距离转换为好求的曼哈顿距离。

先考虑曼哈顿距离的式子，它比较简单： 然后考虑到切比雪夫有 之类的东西，我们可以将上式进行转化： 乐，其实就是四种情况取最大值。 中两项取正，两项取负。

然后考虑切比雪夫距离： 展开： 我操，也是四项。

那么，令 ，代入一下，你会发现，卧槽，和曼哈顿的形式一样！

总结

所以，求曼哈顿距离时，可以将点 变成 ，然后求切比雪夫距离。

反之，求切比雪夫距离时，可以将点 变成 ，然后求曼哈顿距离。

解法

先将所有的点按奇偶性分两块，对每一块内部进行上面切比雪夫->曼哈顿的转化，然后求总距离是很简单的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

public class Main {
    static Scanner sc = new Scanner(System.in);
    static final int N = 1010;


    public static void main(String[] args) {
        int n = sc.nextInt();
        ArrayList<Integer>[] A = new ArrayList[4];
        for(int i = 0; i < 4; i++) A[i] = new ArrayList<>();
        for(int i = 0; i < n; i++){
            int x = sc.nextInt();
            int y = sc.nextInt();
            if((x+y)%2==0){ // 转化，这里不除二，在最后答案再除二
                A[0].add(x+y);
                A[1].add(x-y);
            }else{
                A[2].add(x+y);
                A[3].add(x-y);
            }
        }
        long ans = 0;
        for(int i = 0; i < 4; i++){
            Collections.sort(A[i]);
            long s = 0; int cnt = 0;
            for(int x: A[i]){
                ++cnt; s += x;
                ans += (long)cnt * x - s;
            }
        }
        System.out.println(ans/2);
    }
}

C++移动语义&智能指针

摘自https://www.learncpp.com/cpp-tutorial/

在一个局部函数内部new一个对象，我们容易忘记对它delete，从而造成内存泄漏：

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

#include <iostream>

void someFunction()
{
    Resource* ptr = new Resource();

    int x;
    std::cout << "Enter an integer: ";
    std::cin >> x;

    if (x == 0)
        throw 0; // the function returns early, and ptr won’t be deleted!

    // do stuff with ptr here

    delete ptr;
}

对此，我们可以采用RAII编程范例：通过局部变量的自动析构性，定义一个Auto_ptr1类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include <iostream>

template <typename T>
class Auto_ptr1
{
	T* m_ptr {};
public:
	// Pass in a pointer to "own" via the constructor
	Auto_ptr1(T* ptr=nullptr)
		:m_ptr(ptr)
	{
	}

	// The destructor will make sure it gets deallocated
	~Auto_ptr1()
	{
		delete m_ptr;
	}

	// Overload dereference and operator-> so we can use Auto_ptr1 like m_ptr.
	T& operator*() const { return *m_ptr; }
	T* operator->() const { return m_ptr; }
};

// A sample class to prove the above works
class Resource
{
public:
    Resource() { std::cout << "Resource acquired\n"; }
    ~Resource() { std::cout << "Resource destroyed\n"; }
};

int main()
{
	Auto_ptr1<Resource> res(new Resource()); // Note the allocation of memory here

        // ... but no explicit delete needed

	// Also note that we use <Resource>, not <Resource*>
        // This is because we've defined m_ptr to have type T* (not T)

	return 0;
} // res goes out of scope here, and destroys the allocated Resource for us

将指针包含在类里，通过类的析构函数，可以做到自动释放内存。

但是这么做会有问题，例如两个Auto_ptr1可能管理同一个指针：

1
2
3
4
5
6
7

int main()
{
	Auto_ptr1<Resource> res1(new Resource());
	Auto_ptr1<Resource> res2(res1); // Alternatively, don't initialize res2 and then assign res2 = res1;

	return 0;
}

这样会对同一个地址delete两次，造成ub。

同样地，如果将Auto_ptr1作为函数参数或者函数返回值，都会出现奇怪的问题。

因此一种解决方式，是采用移动语义：通过转移ownership来替代浅拷贝：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

#include <iostream>

template <typename T>
class Auto_ptr2
{
	T* m_ptr {};
public:
	Auto_ptr2(T* ptr=nullptr)
		:m_ptr(ptr)
	{
	}

	~Auto_ptr2()
	{
		delete m_ptr;
	}

	// A copy constructor that implements move semantics
	Auto_ptr2(Auto_ptr2& a) // note: not const
	{
		// We don't need to delete m_ptr here.  This constructor is only called when we're creating a new object, and m_ptr can't be set prior to this.
		m_ptr = a.m_ptr; // transfer our dumb pointer from the source to our local object
		a.m_ptr = nullptr; // make sure the source no longer owns the pointer
	}

	// An assignment operator that implements move semantics
	Auto_ptr2& operator=(Auto_ptr2& a) // note: not const
	{
		if (&a == this)
			return *this;

		delete m_ptr; // make sure we deallocate any pointer the destination is already holding first
		m_ptr = a.m_ptr; // then transfer our dumb pointer from the source to the local object
		a.m_ptr = nullptr; // make sure the source no longer owns the pointer
		return *this;
	}

	T& operator*() const { return *m_ptr; }
	T* operator->() const { return m_ptr; }
	bool isNull() const { return m_ptr == nullptr; }
};

class Resource
{
public:
	Resource() { std::cout << "Resource acquired\n"; }
	~Resource() { std::cout << "Resource destroyed\n"; }
};

int main()
{
	Auto_ptr2<Resource> res1(new Resource());
	Auto_ptr2<Resource> res2; // Start as nullptr

	std::cout << "res1 is " << (res1.isNull() ? "null\n" : "not null\n");
	std::cout << "res2 is " << (res2.isNull() ? "null\n" : "not null\n");

	res2 = res1; // res2 assumes ownership, res1 is set to null

	std::cout << "Ownership transferred\n";

	std::cout << "res1 is " << (res1.isNull() ? "null\n" : "not null\n");
	std::cout << "res2 is " << (res2.isNull() ? "null\n" : "not null\n");

	return 0;
}
/*
Resource acquired
res1 is not null
res2 is null
Ownership transferred
res1 is null
res2 is not null
Resource destroyed
*/

这其实就是早期 std::auto_ptr 的写法。但是这个东西是很危险的，以至于在C++17标准中被删除。例如你将auto_ptr传入函数（并在函数结束时析构），但是调用者函数的对应的auto_ptr并不知道自己维护的指针已经释放了。二是auto_ptr没办法采用数组delete（挖坑，数组delete和普通delete的区别），三是auto_ptr没办法与STL容器很好地交互。

介绍移动语义之前，需要了解一下右值引用的性质。

要知道，函数的返回值是右值（然后用赋值=赋给左值），而右值引用可以延长返回值的生命周期：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <iostream>

class Fraction
{
private:
	int m_numerator { 0 };
	int m_denominator { 1 };

public:
	Fraction(int numerator = 0, int denominator = 1) :
		m_numerator{ numerator }, m_denominator{ denominator }
	{
	}

	friend std::ostream& operator<<(std::ostream& out, const Fraction& f1)
	{
		out << f1.m_numerator << '/' << f1.m_denominator;
		return out;
	}
};

int main()
{
	auto&& rref{ Fraction{ 3, 5 } }; // r-value reference to temporary Fraction

	// f1 of operator<< binds to the temporary, no copies are created.
	std::cout << rref << '\n';

	return 0;
} // rref (and the temporary Fraction) goes out of scope here

那，考虑将右值和右值引用作为函数参数，会是什么情况呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>

void fun(const int& lref) // l-value arguments will select this function
{
	std::cout << "l-value reference to const: " << lref << '\n';
}

void fun(int&& rref) // r-value arguments will select this function
{
	std::cout << "r-value reference: " << rref << '\n';
}

int main()
{
	int x{ 5 };
	fun(x); // l-value argument calls l-value version of function
	fun(5); // r-value argument calls r-value version of function

	return 0;
}
/*
l-value reference to const: 5
r-value reference: 5
*/

可以发现，当我们传入一个右值5，会采用形参为右值引用的重载函数。相比于const的左值引用（可以用右值初始化const左值引用），编译器认为右值引用是更好的选择。

那传入右值引用呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <iostream>

void fun(const int& lref) // l-value arguments will select this function
{
	std::cout << "l-value reference to const: " << lref << '\n';
}

void fun(int&& rref) // r-value arguments will select this function
{
	std::cout << "r-value reference: " << rref << '\n';
}

int main()
{
	int&& ref{ 5 };
    fun(ref);

	return 0;
}
/*
l-value reference to const: 5
*/

我操，居然右值引用是左值。这说明 int&& ref 是 int&& 类型的左值。

另外，根据learncpp，和不能返回左值引用一样，你也不能返回右值引用（虽然本身返回的是int&&类型的左值，但是它引用的是一个生命周期已经结束的右值，这很危险）

我们知道，const左值引用可以接受右值为参数。这里看看learncpp的copy类型auto_ptr：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

#include <iostream>

template<typename T>
class Auto_ptr3
{
	T* m_ptr {};
public:
	Auto_ptr3(T* ptr = nullptr)
		: m_ptr { ptr }
	{
	}

	~Auto_ptr3()
	{
		delete m_ptr;
	}

	// Copy constructor
	// Do deep copy of a.m_ptr to m_ptr
	Auto_ptr3(const Auto_ptr3& a)
	{
		m_ptr = new T;
		*m_ptr = *a.m_ptr;
	}

	// Copy assignment
	// Do deep copy of a.m_ptr to m_ptr
	Auto_ptr3& operator=(const Auto_ptr3& a)
	{
		// Self-assignment detection
		if (&a == this)
			return *this;

		// Release any resource we're holding
		delete m_ptr;

		// Copy the resource
		m_ptr = new T;
		*m_ptr = *a.m_ptr;

		return *this;
	}

	T& operator*() const { return *m_ptr; }
	T* operator->() const { return m_ptr; }
	bool isNull() const { return m_ptr == nullptr; }
};

class Resource
{
public:
	Resource() { std::cout << "Resource acquired\n"; }
	~Resource() { std::cout << "Resource destroyed\n"; }
};

Auto_ptr3<Resource> generateResource()
{
	Auto_ptr3<Resource> res{new Resource};
	return res; // this return value will invoke the copy constructor
}

int main()
{
	Auto_ptr3<Resource> mainres;
	mainres = generateResource(); // this assignment will invoke the copy assignment

	return 0;
}
/*
mine:
Resource acquired
Resource acquired
Resource destroyed
Resource destroyed

learncpp:
Resource acquired
Resource acquired
Resource destroyed
Resource acquired
Resource destroyed
Resource destroyed
*/

按理来说应该有六行，但是我的编译器忽略了返回值。

挖坑，Auto_ptr3& operator=(const Auto_ptr3& a) 前面引用的含义 & ，它防止又调用一次copy constructor

这样我们就实现了一个基于copy的智能指针。但是，通过移动语义，可以做的更好。

C++11为类提供了移动构造函数和移动赋值重载，它们的参数都是右值引用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

#include <iostream>

template<typename T>
class Auto_ptr4
{
	T* m_ptr {};
public:
	Auto_ptr4(T* ptr = nullptr)
		: m_ptr { ptr }
	{
	}

	~Auto_ptr4()
	{
		delete m_ptr;
	}

	// Copy constructor
	// Do deep copy of a.m_ptr to m_ptr
	Auto_ptr4(const Auto_ptr4& a)
	{
		m_ptr = new T;
		*m_ptr = *a.m_ptr;
	}

	// Move constructor
	// Transfer ownership of a.m_ptr to m_ptr
	Auto_ptr4(Auto_ptr4&& a) noexcept
		: m_ptr(a.m_ptr)
	{
		a.m_ptr = nullptr; // we'll talk more about this line below
	}

	// Copy assignment
	// Do deep copy of a.m_ptr to m_ptr
	Auto_ptr4& operator=(const Auto_ptr4& a)
	{
		// Self-assignment detection
		if (&a == this)
			return *this;

		// Release any resource we're holding
		delete m_ptr;

		// Copy the resource
		m_ptr = new T;
		*m_ptr = *a.m_ptr;

		return *this;
	}

	// Move assignment
	// Transfer ownership of a.m_ptr to m_ptr
	Auto_ptr4& operator=(Auto_ptr4&& a) noexcept
	{
		// Self-assignment detection
		if (&a == this)
			return *this;

		// Release any resource we're holding
		delete m_ptr;

		// Transfer ownership of a.m_ptr to m_ptr
		m_ptr = a.m_ptr;
		a.m_ptr = nullptr; // we'll talk more about this line below

		return *this;
	}

	T& operator*() const { return *m_ptr; }
	T* operator->() const { return m_ptr; }
	bool isNull() const { return m_ptr == nullptr; }
};

class Resource
{
public:
	Resource() { std::cout << "Resource acquired\n"; }
	~Resource() { std::cout << "Resource destroyed\n"; }
};

Auto_ptr4<Resource> generateResource()
{
	Auto_ptr4<Resource> res{new Resource};
	return res; // this return value will invoke the move constructor
}

int main()
{
	Auto_ptr4<Resource> mainres;
	mainres = generateResource(); // this assignment will invoke the move assignment

	return 0;
}
/*
Resource acquired
Resource destroyed
*/

认真看一下移动语义的实现~（挖坑：noexcept

由于Resource自始自终都只有一个（只不过所有权转移了很多次），因此只有一次构造和一次析构。

我们将移动语义与右值挂钩。这是因为右值一般来讲都是暂时使用的东西，在以后的程序执行不需要使用。因此比起前面使用左值来实现移动语义，右值更加安全。我们不希望类似于 a=b 这种东西会影响到 b 。

我们观察到，函数 generateResource 返回的是一个左值，但是似乎根据结果来看，返回过程采用了移动语义（即没有构造新值）。这是可以的，C++内部也是这么干的。因为返回的左值在离开函数后会立即销毁，我们没必要在这里使用深拷贝。

learncpp网站上给出建议：对于move-enabled的类，有时候禁止使用拷贝构造和拷贝赋值会更好：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include <iostream>

template<typename T>
class Auto_ptr5
{
	T* m_ptr {};
public:
	Auto_ptr5(T* ptr = nullptr)
		: m_ptr { ptr }
	{
	}

	~Auto_ptr5()
	{
		delete m_ptr;
	}

	// Copy constructor -- no copying allowed!
	Auto_ptr5(const Auto_ptr5& a) = delete;

	// Move constructor
	// Transfer ownership of a.m_ptr to m_ptr
	Auto_ptr5(Auto_ptr5&& a) noexcept
		: m_ptr(a.m_ptr)
	{
		a.m_ptr = nullptr;
	}

	// Copy assignment -- no copying allowed!
	Auto_ptr5& operator=(const Auto_ptr5& a) = delete;

	// Move assignment
	// Transfer ownership of a.m_ptr to m_ptr
	Auto_ptr5& operator=(Auto_ptr5&& a) noexcept
	{
		// Self-assignment detection
		if (&a == this)
			return *this;

		// Release any resource we're holding
		delete m_ptr;

		// Transfer ownership of a.m_ptr to m_ptr
		m_ptr = a.m_ptr;
		a.m_ptr = nullptr;

		return *this;
	}

	T& operator*() const { return *m_ptr; }
	T* operator->() const { return m_ptr; }
	bool isNull() const { return m_ptr == nullptr; }
};

这个东西非常像 std::unique_ptr 。正如其名，unique 的性质让它不能被复制。

std::move 用于将左值转化为右值，这样可以使用移动语义：

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

int main()
{
	std::string a, b;
	b = "nuaa is garbage";
	a = std::move(b);
	std::cout << "a=" <<a << '\n' << "b=" << b;
	return 0;
}
/*
a=nuaa is garbage
b=
*/

但是原有的字符串b变为了空值，这也是意料之内的。

但是根据learncpp上的建议：不要对任何被std::move后的对象的值有任何假设

因此我们以后要避免依赖b的具体的值的操作。

1. xv6-摆烂-理解

大三上学期突然很想自学CS，然后在寒假学了CSAPP的大部分后开始了MIT 6.S081这个课程。用时大概两个月(2.25-4.24)从零开始自学OS到完成了除network外的所有lab，包括2020年和2021年的版本。

学这东西纯属兴趣，想体验一下科班的感觉（

学习路径

我并没有看课程视频，原因是我英语非常差。我看的是这个翻译后的版本：https://mit-public-courses-cn-translatio.gitbook.io/mit6-s081

一般就是，先根据课程要求，浏览一遍xv6 book上对应的章节及源码，然后看上面那个文档，然后再回到xv6 book当中巩固一下。

然后lab的话，前期是根据课程安排进行的。但到后面课程会开始讲一些论文，我是在那之前把所有lab给完成的。所以在写这个文章的时候，我其实还没有结束这门课程的学习。如标题所见，这只是我这两个月来对lab的回顾。我会继续后续论文的学习

lab 1 Xv6 and Unix utilities (2020/2021)

这个其实主要目的是让你安装好环境+熟悉一下xv6的代码结构。主要任务是使用xv6自带的系统调用实现一些功能，比较难的可能是 primes 那个实验，需要你使用多进程通信来完成素数筛。

我当时的想法大致是给每个进程都维护了一个要筛的素数（通过向管道写入第一个数来完成），如果当前传进来的数没办法整除当前进程所维护的素数，就交付给它的子进程处理。

lab 2 system calls (2020/2021)

这个lab就开启了你魔改内核的征程（不是）。你需要实现两个系统调用trace和sysinfo，分别追踪系统调用以及空闲内存与进程的数量。算是最简单的lab之一了，跟着Hint做就行。

lab 3 page tables (2021)

这个lab主要考察你对RISCV和xv6内页表的理解。由于时间太过遥远，我不太记得清楚其中的细节了。但总之也是一个比较简单的lab。

lab 3 page tables (2020)

其实这个才是真正的lab3（，2021年的是阉割的版本

我是到最后才完成的这个lab，原因是它真的非常难！大概耗费了我三天时间

这个lab要求我们为每个进程都额外维护一个内核页表，来简化 copyin/copyinstr 函数所需要的内核/进程页表之间的转换。

你需要为这个进程的内核页表写很多函数，例如初始化，拷贝页表等。

你还需要兼顾效率，即你需要在同一个物理地址上同时为内核页表以及进程的内核页表建立映射，而非直接拷贝物理空间。这涉及到许多细节，可能需要允许一些非法情况发生。

lab 4 traps (2020/2021)

这个lab考察你对xv6内部如何处理trap的细节，相对来说也是比较难的。通过了解xv6如何让trap机制透明来完成该lab中的alarm功能，例如保存上下文，设置pc、ra寄存器等。

另外顺带一提，在这个lab中，你实现的backtrace函数非常实用，可以直接拷贝到其它lab中，非常方便调试。

lab 5 xv6 lazy page allocation (2020)

这个lab考察你对page fault的理解。通过对特定的page fault的处理，使内核能够“按需”分配物理内存。

同时你也需要修改其它函数，让它能够允许一些非法情况的发生。

lab 6 Copy-on-Write Fork for xv6 (2020/2021)

同样考察page fault的理解。COW fork和lazy page allocation都是可以通过处理page fault来实现的功能，但是前者可能要更难一些。因为在fork之后，新进程的页表和父进程的页表指向同一块区域，因此需要对page进行计数。这个涉及到一些多线程并发的东西，例如自旋锁来维护每个page的计数的不变性。

总之也算是比较难的一个lab。

lab 7 Multithreading (2020/2021)

这个lab有点意思，它不仅考察了你对xv6进程调度的理解，还让你了解了一下 UNIX pthread 库函数的使用，来实现多线程并发以及barrier。

多线程并发编程是个老生常谈的话题，我以后大概也会花时间深入了解一下。

但是lab本身是简单的。

lab 8 lock (2020/2021)

这个lab的主要任务是改善xv6原有的对lock的粗粒度的使用。需要你给出更加细粒度的lock方案。

对于每个lock，你需要明确它所保护的不变性。

之前无聊的时候写过解法：https://atri2333.github.io/2024/04/12/lock-lab/

lab 9 file system (2020/2021)

这个lab有两个任务：第一个任务是采用页表分层的思想，将inode的indirect数据block也进行分层，来大幅扩展一个文件所能支持的大小。第二个任务是实现 symlink 系统调用，创建一个新的文件类型symlink，并可以通过这个symlink来追踪其它文件或symlink。

讲真文件系统这章我学的有点仓促，感觉有些东西并没有特别懂，但是对于lab本身还是够用。

lab 10 mmap (2020/2021)

这个lab要求你实现一个阉割版的mmap系统调用，及其对应的阉割版的munmap系统调用，能让用户可以通过访问内存来同步访问文件。

算是对前面的lab的总结了，它涉及到了页表、page fault、文件系统等知识点。

杂谈

关于调试，一般来讲是推荐gdb。但是根据我亲身经历（或者acmer的破习惯），printf调试法更加有用。这可能是由于我gdb用的并不熟练，所以调试起来笨手笨脚的，不如直接打log来的方便与显然（

另外，有一些lab并不是只靠我一个人完成的，我是适当地参考了一些其它人的做法。特别是2020年的页表那个实验，我发现我的写法和网上很多人都不一样，导致就算看别人的也没办法把自己的bug调试好（

不过最终也是赶在学校的破实验课开课前把除了network的xv6 lab都过了一遍，收获挺大的，算是对os有了初步的理解。至少给我一些名词，例如进程、线程、页表等，我都能从xv6的例子中进行联想。

后面会通过这个系列深入xv6源码：https://www.youtube.com/playlist?list=PLbtzT1TYeoMhTPzyTZboW_j7TPAnjv9XB

摆烂

这几周，除了自学这个课程，感觉就没做什么了。

可能，打了一些比赛

校赛，虽然acm退役了，但是打了rk4，仅次于三位noi选手

csp，455，虽然发挥不太好

蓝桥杯，一般般吧，国赛懒得去了

天梯赛，国一，但是我比赛期间（不知晓具体规则的情况下）本能地去头文件查了api，感觉要被查作弊了

codeforces，摆烂了，不想打，只打atcoder，然后1600还没上

学了点java

感觉，学国外的公开课，收获确实挺大

做对应的lab，居然会有点网瘾的感觉

但是现在却没有当初网瘾的动力了

好在，认识了一个非常好的人

所以这几周过的也是非常有意义