CS162 学习记录

#1 · 2024-04-16

摆了半个学期不能再这么下去了
帖子主要当个分布式学习闹钟，什么时候不更新了请门友狠狠 t 我 😡

也欢迎学过/正在学的门友交流

mod

#2 · 2024-04-16

好好好我刚存下 cs162 2024spring 的视频你就出来了是吧

#3 · 2024-04-16

rotartsinimdA

我看的是 2020 的

mod

#4 · 2024-04-16

Lrefrain

你要 2024 Spring 版本的吗我可以私发给你

#5 · 2024-04-16

rotartsinimdA

好啊好啊 wow

mod

#6 · 2024-04-16

Lrefrain

QQ 查收

#7 · 2024-04-16

首先是 Lecture1。
老师叫 Jonh Kubi*****后面不会念也记不住，然后老师说大家都叫他 Professor Kubi。

然后他先给了一张很帅的图 [正在处理：
image|690x378
这个图是 internet 的节点图，受 IP 所限目前大约有 38 亿节点，而每个节点背后都有大量的设备，每个这种设备上都运行着一个 OS

Kubi 大概的讲了许多跟 OS 有关的历史，讲了什么是 OS，最后给出了一个结论：
OS 提供了一种对于机器的抽象，这种抽象建立在硬件之上，是为了简化应用编写而作，隐藏了各类硬件细节。OS 还为每个用户/进程协调了各类资源的分配和共享。

#8 · 2024-04-16

明天应该会继续读书，没更新请门友狠狠 t 我

mod

#9 · 2024-04-16

Lrefrain

为什么不是超

#10 · 2024-04-16

Lecture1 同时提纲挈领地给出了教学大纲：
image|690x355

一些 OS 概念
并发编程，包括线程，调度，锁，死锁，可扩展性（是指什么？），公平性（是指核心调度的公平性吗？）
地址空间，包括虚拟内存，地址转换，保护（可能说的是例如保护一个进程中的内存不被别的进程破坏？），共享（也许是指两个进程间的共享？例如共享内存）
文件系统，包括 IO 设备，文件对象（文件描述符吗？），存储，命名，缓存（比如页表和 Cache？），性能（想起来了 ICS 课上讲的那个内存大山），事务（好像是数据库的概念），数据库
分布式系统，协议（像 TCP，UDP 那种？），剩下的不认识，不知道是啥
可靠性和安全性

求指点

#11 · 2024-04-16

Lrefrain

这里 Kubi 非常明确的说了，File Systems 是他的最爱，数据是最重要的最需要保护的东西，合理。

#12 · 2024-04-16

Lecture1 给出了在本堂课中的 Projects 会着重用到的自研精简操作系统 Pintos，将会有三次针对于 Pintos 的 Project
分别针对

用户程序（exec && syscall）什么意思，程序执行和系统调用吗？
线程和调度
文件系统

从 cswiki.diy 上面得到的信息是，即使把 Projects 平均分给 4 个人也需要将近 40 小时每人，每人分配到的代码量大概有 2000 多行。

mod

#13 · 2024-04-16 (edited)

帅！我上的 23sp，也是 kubi
你自己一个人写四人 project 吗，我们当时三个大神 + 我每周都花了好多时间才写完
另外我们当时有 ta 把关 design doc，避免 project 从上手就是错的这种情况，可能你只能自己多注意一下 design 了

#14 · 2024-04-16

m0rsun

草， 😭那怎么感觉很容易搞错啊，，

mod

#15 · 2024-04-16

Lrefrain

草，我感觉 162 其实不太适合刷课，我当时课没怎么上但配套设施用了个全 (ta，discussion，autograder，组员)，要不换个能单刷的 OS 课 (？

#16 · 2024-04-16 (edited)

m0rsun

我有个朋友大三时候单刷了，我在追随他的步伐

#17 · 2024-04-16

好巧。我上的 23sp，也是 kubi。这门课质量比较高，非常推荐。

#18 · 2024-04-16

m0rsun

但是从另一方面说，所有的 project 都有大量公开的测试样例（因此可以自己本地测试而不需要 autograder），所以也比较好避免这方面的问题。

#19 · 2024-04-16

m0rsun

感觉这门课的 autograder 约等于没用，所有 project 的测试点都在本地，可以调试。

#20 · 2024-04-17

uebian

wow，那还蛮方便的
说实话我没有运行过一个操作系统程序过，所以 Pintos 的调试大概是怎样进行的呢？会是在一个操作系统上运行，还是有某种其他方式，比如像一个 U 盘那样插到电脑上运行？

#21 · 2024-04-17

Lrefrain

Pintos 的调试是在 qemu 虚拟机和 bochs 虚拟机中进行。在开启调试模式之后，你可以在某些内存地址设置断点，这些虚拟机内的虚拟 CPU 执行到位于这些内存地址的指令时就会停下来，然后你就可以打印内存中的值或者寄存器中的值来进行调试。Pintos 提供了一系列 gdb 的宏，在载入这些宏之后的调试体验和普通的 C/C++ 调试差不多。

#22 · 2024-04-17

uebian

好完备的 proj 啊，感觉要花好久做

mod

#23 · 2024-04-17

Lrefrain

我感觉四个人平均还要 2k 行代码已经很能说明问题了 🤣 毕竟这是实验代码，不是业务搬砖。图形学这边 Dandelion 框架本体有 6k+ 行代码，但我只能设计出不到 1k 行的实验空间来。光是留给同学的空间就多达 8k+ 行，我听着都很震撼。

#24 · 2024-04-17

greyishsong

没有那么多，四人一共 2k 行差不多。主要工作集中在 design 上面，实现并不难

#25 · 2024-04-17

Lrefrain

Project 1 userprog
图片|667x499
Project 2 threads
图片|690x443
Project 3 File systems
图片|666x500
从 cs162 的文档拿了几张图，上图直观地展示了 staff 的解决方案的代码变动，从中可以看出所有的 projects 一共需要写两千多行代码

mod

#26 · 2024-04-17 (edited)

你已经 12h 没学习了，快开始吧，我就指望看着你的笔记学呢

#27 · 2024-04-17 (edited)

rotartsinimdA

糟糕，我被门友包围了

#28 · 2024-04-18

rotartsinimdA

😭闹钟响了，昨天在准备面试来着

mod

#29 · 2024-04-18

Lrefrain

👀你不是好多 offer 了吗

好厉害😭今天我体验了一下天王星的面试🤗
我的评价是：我必挂

#30 · 2024-04-18

rotartsinimdA

上海还是深圳啊，他们不太一样的，分的挺开

mod

#31 · 2024-04-18

Lrefrain

深圳，

挂了肯定😋

#32 · 2024-04-18

rotartsinimdA

深圳你找我内推呀😆万一就过了呢

mod

#33 · 2024-04-18 (edited)

Lrefrain

我啥也不会👀👀👀 推我不会对你有坏影响吧🤡
现在是成都那边的人面我，但是给我说成都和深圳是一个组

#34 · 2024-04-18

rotartsinimdA

是一个组，成都和深圳一起的，上海单独的。
不会有坏影响啊，我都离职了

mod

#35 · 2024-04-18

Lrefrain

原来如此😭

#36 · 2024-04-19

Lecture2. 四个 OS 的基本概念

Thread
很有趣的说法，线程就是虚拟核心（也就是处理器）
一个处理器（核心）上如何运行多个 Thread，给出一种好像有很多个线程的假象呢？可以像右侧图中这样随时间不断地切换当前正在运行的 Thread（vCPU）。

同时这里还给出了 Thread Control Block—TCB 的定义，我们在某个处理器中切换 Thread 的时候，为了下一次能够继续正常运行切换前的 Thread，我们需要把它内部的状态（例如寄存器信息，PC，Flags（可能是指控制器的状态？）等等）存储到内存中，这里这些状态信息就是 TCB。
同时这里涉及到一个问题：
每个 Core 往往都拥有自己独立的缓存，根据 NUMA 架构，每个 CPU Node 中所有的 Cores 会 Share L3 Cache，在此之上，每个 Core 都各自含有一层 L2 Cache 和 L1 Cache（L1 分为指令缓存和数据缓存两部分）。
因此如果我们频繁的在同一个 Core 上切换其运行的 Thread，如果有某个 Thread 极其吃缓存，就会导致每次切换带来巨大的 Cache Miss 开销，比起单核单线程运行时的性能将会大大降低。
除此之外，单次线程切换的开销大概是数微妙，如果切换的过于频繁，会导致严重的性能下降。
触发切换的可能情景：计时器（类似于 Round Robin 每次分配运行时间片？），一些可以异步的操作（例如 IO 操作，这时候会安排别的 Thread 运行），或者自愿放弃持有 Core 的资源。
我们该如何确定 Thread 们的运行是正确的呢？

这张图里有三个 Thread 的内存结构，我们发现除此之外，Thread 需要保存的信息仍然很多，因此 TCB 中的信息往往是压缩过的（例如流水线中的信息将会被全部清空）。
Kubi 说这里暂且认为 TCB 中的信息保存在内存中，尤其指明保存在内核占用的内存中。

#37 · 2024-04-19

Address Space
2.1 基本的地址空间细节
Address Space 是可访问的地址的集合。

它由这些部分构成：
栈区：用来给 Thread 存储临时变量，函数递归栈帧等
堆区：用来动态分配内存
数据区：存储静态变量，全局变量等
代码区：存储可执行代码
考虑在同一个 Core 中，除了堆栈指针，Program Counter，寄存器等，剩下的资源均是他们所共享的。
因此会带来一定的不安全性，每个 Thread 都可以访问在同一个 Core 上运行的其他 Thread 的内存。

上图带来了一个简单的处理方法：
使用 Base & Bound 寄存器表示一个 Thread 可以访问的内存的范围，限制某个 Thread 只可以访问 [Base, Bound) 范围内的地址空间，这样可以很有效的阻止 Thread 访问其他不由他管辖的内存。

另一个非常简单的 Base & Bound 实现方式如下图：

使用一个加法器，程序需要访问的内存位置 x 实际上需要访问 Base + x 的内存位置，我们只需要判断 Base + x 是否 < Bound 即可。这实际上使得每个程序中都可以认为自己所在的内存地址是从 0000...开始的，方便了程序的编辑。

我们刚刚完成了对 x 到其对应物理内存的一个极其简单的翻译，这实际上揭示了一种更加通用的内存地址转换模型。如上图所示，处理器给出虚拟的内存地址，经由翻译器获得其实际的物理地址。
2.2 页
为什么要使用页呢？
考虑一种情况：某个 Thread 占用的内存不够用（例如一直在 Allocate 新的内存，导致原本预定占用的堆区爆满），这时唯一的做法就是将其目前占用的内存全部剪切到另一片更大的内存区域中。如果这种操作频繁发生，不断的在原本被占用的长段内存中“打洞”，在原本未被占用的内存中间“填充”，这将会导致严重的内存碎片化，这个问题的解决方法将在后面的课程中学到。
除此之外，剪切本身也是一件相对困难的事情，但是如果整个内存被分为一页一页的，我们就可以按页地安置每一页内存。
2.3 页表
我们该如何按页维护内存并完成虚拟地址到物理地址的翻译呢？
使用页表作为翻译器。

如上图所示，处理器给出的虚拟地址将包括两个关键内容，一个是页号，另一个是业内偏移量，由于所有的页大小均相同，因此我们通过页号在页表内查询到对应物理地址所在的页，再使用页内偏移量即可找到在这一页中要查询的地址所在的位置。

#38 · 2024-04-19

Process
进程是一个拥有受限制权限的执行环境。（哈哈，终于有一个不是“系统资源调度的基本单位“的说法了）
注意到上文中并未区分 Thread 和 Process，因此这一节会有一小部分颠覆前两节的说法。
进程拥有一定的受限制的地址空间（比如使用 base bound 限制），文件描述符，文件系统上下文，拥有一些共享某些资源的 Threads。
出于对于安全性考虑的刻意的设计，在同一进程中的不同线程的交流很简单，在不同进程中的线程交流很困难。

这张图很好的揭示了为什么同一进程中的不同线程交流很简单，因为他们的 Code Data Fils 都是共享的。
因此，出于对安全性和可靠性的考虑，我们要求进程只能修改自己的内存，避免了对其他进程的影响。

#39 · 2024-04-19

Dual Mode
考虑为什么进程 A 的页表指针不能指向进程 B？
因为这会破坏进程间的数据隔离。
那我们该如何在必要时使用这种操作呢？这就要求硬件至少提供两种模式：内核模式和用户模式。
下一个问题是该如何控制两种模式间的过渡和切换？

image|690x212
image|690x370

简单来说，如上图：调用系统调用 syscall，系统调用会支配硬件完成某些工作，然后结束 syscall 返回用户模式。注意到至少提供两种模式，后续在 Docker 中我们将了解到更多的权限介于二者之间的模式。

#40 · 2024-04-19

一个例子

最开始处于内核模式，可以注意到其 Base 和 Bound 均失效（意味着可以访问 [0000..., FFFF....] 的所有地址空间），uPC 指向黄色进程的可执行代码，意味着目前想要加载进入黄色进程。

我们将 PC 换为之前的 uPC，sysmode 改为 0 之后，Base 和 Bound 就激活了且等于黄色的地址区域边界，这意味着我们进入了黄色进程，同时进入了用户模式。

假设一段时间后发生了计时器中断，下一条执行的指令将会是计时器中断处理程序（存在于内核代码区），中断发生后我们又一次进入了内核态。

由于要发生进程切换，因此计时器中断处理程序将会保存黄色进程 PCB 并放入内核区（灰色）的 Static Data 中的黄色小方块。
同时我们加载切换到绿色所需的寄存器信息。

更改 sysmode 后成功以用户模式运行绿色进程。

#41 · 2024-04-20 (edited)

有没有门友做过 PKU 的 Pintos 啊，在犹豫做原版的还是 PKU 的，我看了下好像把最后一个实验拆成了两半

#42 · 2024-04-20 (edited)

Windows 装 docker 蓝屏了
拿电脑店修去了 tmd
学 os，然后被 os gank

mod

#43 · 2024-04-20

Lrefrain

好像在哪里看到过某个（比较新）版本的 docker 与 Windows 的 hyper-v 之间有点协作不好……感觉自己电脑是 Windows 的话，不如直接装 VM 玩算了

#44 · 2024-04-20

greyishsong

就是 Hyper-V，我开安全模式然后把一系列 Hyper-V 组件全删了就好了，

#45 · 2024-04-20

去薅台 aliyun 来做实验吧，正好最近 aliyun 在撒钱
https://xjtu.app/t/topic/11535

#46 · 2024-04-20

platypus

我有一台闲置的 Linux 电脑，于是决定使用这个旧电脑来操作，话说我已经买了阿里云的云服务器，这种情况下还能优惠吗？

#47 · 2024-04-20 (edited)

Lrefrain

新活动好像是学生原价三折优惠 +300 元优惠券并且可叠加，已经买过这次应该也可以搞台免费机器玩，这个和新客优惠无关

#48 · 2024-04-21

决定使用 pku 版本的 pintos
刚刚做完了 lab0，gdb 搞得我有点头昏眼花的

#49 · 2024-04-21 (edited)

Lrefrain

我都没用过 gdb，都是 clion 打断点，然后 alt+shift+v eval expression，debug 面板看内存变量，断点好像也能设置条件

#50 · 2024-04-21

Anonymous Coward Old

wow，那跟 gdb 好像也每什么区别吧。
clion 调汇编方便吗？

#51 · 2024-04-21 (edited)

Lrefrain

这就涉及我的盲区了，我都不知道什么是汇编😅

#52 · 2024-04-21

Anonymous Coward Old

就是汇编语言，比起 C 要低级一些

#53 · 2024-04-21

Lrefrain

来个链接看看 pku 版本的 lab

#54 · 2024-04-21

platypus

https://pkuflyingpig.gitbook.io/pintos

#55 · 2024-04-22

Lab0

别的没什么好提的，大概熟悉了一下 Pintos 的编译运行和调试。

最后一个 Ex 是要求写一个非常简单的 terminal，只需要执行非常很少量的工作，然而这确实有助于我理解我们平时使用的 terminal 是如何编写的。

在 input.c 文件中我找到了以下代码：


/** Retrieves a key from the input buffer.
   If the buffer is empty, waits for a key to be pressed. */
uint8_t
input_getc (void) 
{
  enum intr_level old_level;
  uint8_t key;

  old_level = intr_disable ();
  key = intq_getc (&buffer);
  serial_notify ();
  intr_set_level (old_level);
  
  return key;
}

这段代码会即时地 return 一个输入的 key，因此只需要调用这个函数并加上一定的逻辑处理，就可以用来实现我们的 terminal 了。

不过这显然并不令人满意，继续递归检索 intq_getc() 函数，会得到如下代码：

//intq.h & intq.c
/** An "interrupt queue", a circular buffer shared between
   kernel threads and external interrupt handlers.

   Interrupt queue functions can be called from kernel threads or
   from external interrupt handlers.  Except for intq_init(),
   interrupts must be off in either case.

   The interrupt queue has the structure of a "monitor".  Locks
   and condition variables from threads/synch.h cannot be used in
   this case, as they normally would, because they can only
   protect kernel threads from one another, not from interrupt
   handlers. */


/** Queue buffer size, in bytes. */
#define INTQ_BUFSIZE 64

/** A circular queue of bytes. */
struct intq
  {
    /* Waiting threads. */
    struct lock lock;           /**< Only one thread may wait at once. */
    struct thread *not_full;    /**< Thread waiting for not-full condition. */
    struct thread *not_empty;   /**< Thread waiting for not-empty condition. */

    /* Queue. */
    uint8_t buf[INTQ_BUFSIZE];  /**< Buffer. */
    int head;                   /**< New data is written here. */
    int tail;                   /**< Old data is read here. */
  };

/** Removes a byte from Q and returns it.
   If Q is empty, sleeps until a byte is added.
   When called from an interrupt handler, Q must not be empty. */
uint8_t
intq_getc (struct intq *q) 
{
  uint8_t byte;
  
  ASSERT (intr_get_level () == INTR_OFF);
  while (intq_empty (q)) 
    {
      ASSERT (!intr_context ());
      lock_acquire (&q->lock);
      wait (q, &q->not_empty);
      lock_release (&q->lock);
    }
  
  byte = q->buf[q->tail];
  q->tail = next (q->tail);
  signal (q, &q->not_full);
  return byte;
}

大略的看了一下，这个interrupt queue看起来就是一个阻塞式循环队列，略有不同的是，该队列从 tail字段处取走字符，从head 字段处增加字符。
不过令人惊奇的是该队列的条件变量和锁都是自己实现的，看起来很有意思，不知道会不会在后续的实验中让学生也参与进这部分代码的编写。

除此之外还有一个有趣的技巧，我们发现在实现一个 terminal 的时候，仅仅拥有 input_getc或许是不够的，一个比较麻烦的情况是：我们键入了Backspace 退格键，该如何将已经显示的字符取消呢？
为此我了解了一个 '\b' 字符，该字符可以将光标向前移动一格，但并不会更改已经存在的字符，他对显示出的字符的更改存在于未来——当下一个字符被输出的时候，会覆盖掉光标后的一个元素，如果光标向前移动一格，同时被空格覆盖，那么我们就可以实现类似退格的效果。
不过有一些不太好的 bug：
例如运行printf("1234\b 567")将会输出字符串"123 567"，平白无故多出的空格将无法处理。
因此我们将目光从一字符后的未来放到更远的二字符后的未来，我们就会明白，空格也需要被覆盖。
对上面的例子作出更改可以得到：printf("1234\b \b567")->"123567"。
对应可得：Backspace = \b \b

#56 · 2024-04-22

https://github.com/Lrefrain/PintOS
如果想要更加仔细的看代码，可以访问这个链接

#57 · 2024-04-22

一般 lab 的实现代码不是不让公开吗

#58 · 2024-04-22 (edited)

Anonymous Coward Old

各种 cs 开头的课 GitHub 上一搜一下吧，谁管，能管得到吗？

#59 · 2024-04-22

Lecture 3. Thread & Process

Why threads?

Kubi 提出了 MTAO 的概念（他自己造出来的词儿，Multiple things at once），同时做多件事。
因为需要线程去实现 MTAO。
parallelism & concurrently

Multiprocessing 是 parallelism，Multiprogramming 不是 parallelism，他们都是 concurrently。
syscalls

上图系统调用示意图。
疑问：为什么我们没有见过 syscall，这是因为往往 syscall 被隐藏在我们运行的语言的函数接口之下。这是因为在不同的操作系统上，syscall 是不同的，因此为了同一语言在不同操作系统上的运行，采用了这种隐藏的方式。
然而 syscalls 是有一个子集被标准化了的，这个子集称为 POSIX syscall interface，这一组 syscalls 在大部分系统上以同名实现。
Threads State

信息共享情况如图
Execution Stack

这个图很直观的展示了在函数递归的过程中，运行时堆栈会保存的信息，首先是参数，然后是临时变量（如果有），还有 ret，ret 表示的是结束调用后需要执行的下一条指令的位置。

上图是同一进程中不同线程的运行时堆栈的内存布局。
这涉及到一些有趣的问题：当一个栈增长得过长，将会搞乱另一个栈。
因此为此设立了 Guard Page，当栈触及这个页面的时候会陷入内核，并且决定是应该让栈获得更大的内存，抑或是终止线程，Kubi 说后面的课程会提到。
Threads Race
多线程竞争资源，指令交错执行，老生常谈
一些和阻止多线程错误执行相关的概念

同步：协调多线程并让其正确执行的手段，通常于线程间共享的数据有关
互斥：同时只有线程作某件特定的事情，属于一种同步手段
Critical Section：同时只有一个 Thread 执行 Critical Section 的代码，Java 中可以使用 Synchronization 关键字来制作一段拥有这种功能的代码
锁：用来使某个对象同时只有一个 Thread 可以访问，属于一种互斥手段
pthread(POSIX Thread)
pthread_create，创建线程
pthread_exit，退出线程
pthread_join，等待某个线程结束
pthread_mutex_init，创建锁
pthread_mutex_lock，阻塞式地获取锁
pthread_mutex_unlock，释放锁
Process Create
每个进程都由其他进程创建。
宇宙大爆炸：在内核启动前，会有一个进程作为参数放入内核，这通常被称为 init 进程，然后 init 进程作为整个进程树的树根存在。
PV operation for mutex

使用 PV(down/up) 操作来实现锁和 pthread_join（区别在于不同的阻塞位置和信号量的初始值）。
P 操作会等待信号量变为正数时给信号量 -1，V 操作会给信号量 +1，并告诉一个 P 操作停止等待
Proccess APIs
exit，终止进程，进程正常 return 0 未调用 exit 时，OS 会自动为该进程调用 exit(0)
fork，开启子进程，对于父进程，返回子进程的 pid，对于子进程，返回 0。子进程会复制父进程的地址空间，并在新的地址空间中从同样的位置开始运行，子进程只会运行调用 fork 的 thread，其他所有的 threads 在子进程中会被终止
exec，没听懂，说是用来复制父进程的地址空间，然后把原来的副本全部删除，并在新的地址空间中运行的意思
wait，等待子进程运行完毕，并在参数中返回其 exit 的结果
sigaction，信号，有固定的信号表（例如 SIGINT 表示 Ctrl-C），也可以实现定制化的信号调用函数

#60 · 2024-04-22

Anonymous Coward Old

是指我个人的实现代码吗？
我见 github 上一堆人发，没太在意这个事
主要是感觉对于本校的，想抄作业的话还是很简单的，如果对于外校的抄不抄本来就是全凭自觉吧 ovo。
如果是指 lab 自身的代码的话似乎 PKUOS/pintos 是开源的。