UCB CS162 学习记录

#1 · 2026-09-26

Fa25 website

CS 162 — Fall 2025
（我爬下来了但是太大上传不了，需要可以 pm 我）

Textbooks

Operating Systems Principles and Practice, Volume 1: Kernels and Processes
Operating Systems Principles and Practice, Volume 2: Concurrency
Operating Systems Principles and Practice, Volume 3: Memory Management
Operating Systems Principles and Practice, Volume 4: Persistent Storage

Sp22 course video

https://www.bilibili.com/video/BV1L541117gr

#2 · 2026-09-26

一起学的门友可以来交流哦（

#3 · 2026-09-27

话说大家觉得自学课程，看书和听课之间应该怎么选择？

看书好处是可以上课摸鱼看，而且似乎能更全面，坏处是比较消耗时间精力，而且有时候书废话太多了

看课好处是比读书效率高，而且似乎省力一些（我一般开 2x），坏处是没法上课大大方方看

#4 · 2026-09-27

无状态垃圾桶

哦对了看书还能听歌 😇

#5 · 2026-09-28

https://en.cppreference.com/c/language/translation_phases

把这个记住了可以明白各种语法的优先级 😇

EOF without newline

If a non-empty source file does not end with a newline character after this step (whether it had no newline originally, or it ended with a backslash), the behavior is undefined.

源文件在二阶段结束后必须以 newline 结束（一阶段由操作系统 EOL 符号产生），否则 UB

UB:

int main(void){return 0;}

UB: （因为结尾 newline 在二阶段被 "\" 干掉了）

int main(void){return 0;}\

execution character set

execution character set 由编译器实现决定
在五阶段，字符和字符串字面量被翻译到 execution character set

为了可移植性，不能假设编译器使用某种 execution character set：

static int is_alpha(char c) {
    return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z');
}

这里假设 'A'..'Z' 和 'a'..'z' 的编码是连续的，然而在 EBCDIC 下就不连续
正确的做法是使用 ctype.h 提供的 int isalpha(int c);：

if (isalpha((unsigned char)c)) {}

注意

CAVEATS
       The  standards  require  that the argument c for these functions is either EOF or a value that is representable in the type unsigned char; otherwise, the behavior is
       undefined.  If the argument c is of type char, it must be cast to unsigned char, as in the following example:

           char c;
           ...
           res = toupper((unsigned char) c);

       This is necessary because char may be the equivalent of signed char, in which case a byte where the top bit is set would be sign extended  when  converting  to  int,
       yielding a value that is outside the range of unsigned char.

       The  details  of what characters belong to which class depend on the locale.  For example, isupper() will not recognize an A-umlaut (Ä) as an uppercase letter in the
       default C locale.

#6 · 2026-09-28

关于这个，似乎有个老帖子 CS162 学习记录 - #81 - XJTUMen

#7 · 2026-09-28

Lrefrain

我去还有远古大佬

#8 · 2026-09-28

#9 · 2026-09-28

这个好有意思

#10 · 2026-09-28

Docker workspace

我稍微加了点常用的东西

另外因为 Docker 乱动桌子，所以设置了 "iptables": false，手动配置了 IP 和 NAT（NAT 配置不在仓库里）

#11 · 2026-09-29

hw-intro

hw0 基本上就是环境设置，C 语法以及 ICS 复习

Counting words

这里值得一提的大概有三点：

1. spec 规定了单词最大长度但是没有定义单词超出长度时的行为，让人很难受（

#define MAX_WORD_LEN 64

我觉得这可能更多是一种保证，提供的测试数据不会有超出 64 个字符的单词，以便在栈上定义 buffer，而不是说超出了要怎样特殊处理
不过如果硬要处理的话无非有这两种办法：

丢弃：当前单词超出 64 个字符则直接丢弃整个连续单词
截断：将已有的 64 个字符截取为一个单词

不过考虑这两种情况会让状态机变得更复杂，我的实现是超出 64 直接报错退出，事实证明并没有超出 64 的（

2. skeleton 给出的 `word_count.h` 没有提供释放资源的接口，而且 spec 明确规定不允许修改

这是个作业程序，而且总共只有一轮 O(n) 的堆分配，不需要长期运行，所以干脆摆烂了也是可以的吗？（

3. 自学没有 autograder

这里我直接找了圣遗物做差分测试，输出一致就没管了（

# Compare reference and real implementation on every text file.
# $(1) is the mode flag, $(2) is a display name for the mode.
define run_tests
	@fail=0; \
	for f in $(TEXT_FILES); do \
		./$(BINARIES) $(1) $$f > .test_impl.out 2>&1; \
		./$(REF_BINARIES) $(1) $$f > .test_ref.out 2>&1; \
		if diff -u .test_ref.out .test_impl.out > .test.diff; then \
			echo "PASS ($(2)) $$f"; \
		else \
			echo "FAIL ($(2)) $$f"; cat .test.diff; fail=1; \
		fi; \
	done; \
	rm -f .test_impl.out .test_ref.out .test.diff; \
	exit $$fail
endef

#12 · 2026-09-29

pthreads 参考

#13 · 2026-09-29

pthread_cond_t

通用模式：

static int predicate;
static pthread_mutex_t mu = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

waiter:

pthread_mutex_lock(&mu);
while (!predicate)
    pthread_cond_wait(&cond, &mu);
/* do work... */
pthread_mutex_unlock(&mu);

signaler:

pthread_mutex_lock(&mu);
predicate = 1;
pthread_cond_signal(&cond);
pthread_mutex_unlock(&mu);

本质上是 条件读写和信号处理必须原子化：

waiter 检查条件并决定是否进入等待
signaler 设置条件并发送信号

实例

#include <pthread.h>
#include <stdbool.h>

#define CAP 64

static int   buf[CAP];
static int   head = 0, tail = 0, count = 0;
static pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t  not_full  = PTHREAD_COND_INITIALIZER;
static pthread_cond_t  not_empty = PTHREAD_COND_INITIALIZER;

void put(int v) {
    pthread_mutex_lock(&m);
    while (count == CAP)                       /* predicate: buffer full */
        pthread_cond_wait(&not_full, &m);      /* atomic unlock + sleep */
    buf[head] = v;
    head = (head + 1) % CAP;
    count++;
    pthread_cond_signal(&not_empty);           /* wake one consumer */
    pthread_mutex_unlock(&m);
}

int get(void) {
    pthread_mutex_lock(&m);
    while (count == 0)                         /* predicate: buffer empty */
        pthread_cond_wait(&not_empty, &m);
    int v = buf[tail];
    tail = (tail + 1) % CAP;
    count--;
    pthread_cond_signal(&not_full);            /* wake one producer */
    pthread_mutex_unlock(&m);
    return v;
}

#14 · 2026-09-29

C 的 type notation 真是十分令人迷惑，这一点还是 Go 比较爽 🫠

可能是我不习惯吧

#15 · 2026-09-30

hw-list

hw1 主要让学生上手 pintos list.h 和 pthreads 接口（以便以后自己实现吗，吓哭了）

list.h

就是一个双向链表，但是比较有意思的是，它的接口设计是完全让用户进行内存管理，只提供链表操作方法（有点像 Go 里的 container/heap）

用户在需要用链表管理的结构体内嵌入链表 header：

/* List element. */
struct list_elem {
  struct list_elem* prev; /* Previous list element. */
  struct list_elem* next; /* Next list element. */
};

比如：

struct user_struct {
  int foo;
  int bar;
  struct list_elem* elem;
}

然后把 elem，也就是链表 header 的地址作为节点插入链表，读取的时候用一个宏来恢复为用户结构体的地址：

#define list_entry(LIST_ELEM, STRUCT, MEMBER)                                                      \
  ((STRUCT*)((uint8_t*)&(LIST_ELEM)->next - offsetof(STRUCT, MEMBER.next)))

struct list_elem* e = ...;
struct user_struct* us = list_entry(e, struct user_struct, elem);

lwords

lwords 就是使用 list.h 实现 hw0 的 word list，不过这次 main 只给了 object file 没给源码，堆内存依旧用完不释放（

pwords

pwords 是 lwords 但是使用 pthreads 多线程，不同文件并行处理，需要用 mutex 锁一锁之类的

这里的 main 是让自己写了，因为需要创建和等待线程，但是中间还是夹了一层写死（只有 object file）的接口，和 lwords 是一样的，但是对于多线程来说很糟糕：

/* Find a word in a word_count list. */
word_count_t* find_word(word_count_list_t* wclist, char* word);

/*
 * Insert word with count=1, if not already present; increment count if
 * present. Takes ownership of word.
 */
word_count_t* add_word(word_count_list_t* wclist, char* word);

这里显然 find_word 是无法做到并发安全的，必须要求 caller 先锁住 mutex，因为 find_word 返回的是 reference 而不是 value
然而文档里没仔细说写死的实现到底用没用 find_word，最后我自己拆了 word_helpers.o 才证明没用（那就别定义在头文件里啊🫠）

然后 add_word 虽然可以并发安全，但是解锁 mutex 之后还要返回一个 word_count_t*，也是有点难受

#16 · 2026-10-11

hw-list 性能

第一个通过测试的版本性能非常垃圾，lwords 和 pwords 大约只有 0.5x words，分析之后大概有这几点值得注意的

Free on duplicate

word count api 中对 add_word 的描述是 "Takes ownership of word."

/*
 * Insert word with count=1, if not already present; increment count if
 * present. Takes ownership of word.
 */
word_count_t* add_word(word_count_list_t* wclist, char* word);

因此在 wclist 中已存在相同的 word 时可以直接释放传入的 word：

  ASSERT(wclist != NULL && word != NULL);
  word_count_t* wc = find_word(wclist, word);
  if (wc != NULL) {
    free(word);
    wc->count++;
    return wc;
  }

ASSERT overhead

list.c 使用了不少 ASSERT 宏（其实我实现 word count 也用了），向 gcc 传入 -DNDEBUG 后可排除 ASSERT 的消耗

最终结果

Build: -g3 -pthread -Wall -std=gnu99 -O2 -DNDEBUG
Benchmark: 5 files per invocation, 1 run(s) per implementation

words    best  3328 ms   avg  3328 ms
lwords   best  2943 ms   avg  2943 ms   (1.13x vs words)
using 22 threads
pwords   best  4051 ms   avg  4051 ms   (0.82x vs words)

这里 pwords 性能甚至不如 words，经过测试推测为 word_count_list 的 O(n) 操作在全局锁下竞争太严重

才意识到根本就没有 22 个文件，测后面的都没意义（

更优的写法是每个线程创建独立的 word_list 然后最后合并，但是 word count api 并没有提供合并的方法，所以只能作罢

#17 · 2026-10-11

https://cppcheatsheet.com/notes/c/asm.html

#18 · 2026-10-11

void _start(int argc, char* argv[]) { exit(main(argc, argv)); }

0804890f <_start>:
 804890f:       55                      push   %ebp
 8048910:       89 e5                   mov    %esp,%ebp
 8048912:       83 ec 18                sub    $0x18,%esp
 8048915:       8b 45 0c                mov    0xc(%ebp),%eax
 8048918:       89 44 24 04             mov    %eax,0x4(%esp)
 804891c:       8b 45 08                mov    0x8(%ebp),%eax
 804891f:       89 04 24                mov    %eax,(%esp)
 8048922:       e8 6d f7 ff ff          call   8048094 <main>
 8048927:       89 04 24                mov    %eax,(%esp)
 804892a:       e8 d4 22 00 00          call   804ac03 <exit>

之前学 15-213 的时候看的是 SysV AMD64 ABI，参数是用寄存器传递的，结果到这里愣了半天 🫪

 8048915:       8b 45 0c                mov    0xc(%ebp),%eax
 8048918:       89 44 24 04             mov    %eax,0x4(%esp)
 804891c:       8b 45 08                mov    0x8(%ebp),%eax
 804891f:       89 04 24                mov    %eax,(%esp)

这四步应该是 cdecl 传参，_start 的 caller 把 argc, argv 分别放在 0xc(%ebp), 0x8(%ebp) （0x4(%ebp), (%ebp) 分别是返回地址和 callee-saved %ebp）

接着 _start 把 argc, argv 分别复制到 (%esp), 0x4(%esp)，作为 main 的参数

所以函数的参数储存在其 caller 的栈帧上

#19 · 2026-10-11

proj-pregame

主要任务是修复三个测试

do-nothing

/* Does absolutely nothing. */

#include "tests/lib.h"

int main(int argc UNUSED, char* argv[] UNUSED) { return 162; }

Page fault at 0xc0000008: rights violation error reading page in user context.
do-nothing: dying due to interrupt 0x0e (#PF Page-Fault Exception).
Interrupt 0x0e (#PF Page-Fault Exception) at eip=0x8048915

可以看到在用户模式发生了非法读取导致的页面错误，0x8048915 处的指令访问了 0xc0000008

搜索 0xc0000000 可找到：

/* Kernel virtual address at which all physical memory is mapped.
   Must be aligned on a 4 MB boundary. */
#define LOADER_PHYS_BASE 0xc0000000 /* 3 GB. */

/* Base address of the 1:1 physical-to-virtual mapping.  Physical
   memory is mapped starting at this virtual address.  Thus,
   physical address 0 is accessible at PHYS_BASE, physical
   address address 0x1234 at (uint8_t *) PHYS_BASE + 0x1234, and
   so on.

   This address also marks the end of user programs' address
   space.  Up to this point in memory, user programs are allowed
   to map whatever they like.  At this point and above, the
   virtual address space belongs to the kernel. */
#define PHYS_BASE ((void*)LOADER_PHYS_BASE)

/* Returns true if VADDR is a user virtual address. */
static inline bool is_user_vaddr(const void* vaddr) { return vaddr < PHYS_BASE; }

/* Returns true if VADDR is a kernel virtual address. */
static inline bool is_kernel_vaddr(const void* vaddr) { return vaddr >= PHYS_BASE; }

可知内核虚拟内存空间以及物理内存映射从 0xc0000000 开始（用户虚拟内存空间结束），因此在用户空间对 0xc0000008 的访问是非法的，触发了页面错误

用 objdump 把反汇编 do-nothing 后查找 0x8048915 可得到：

0804890f <_start>:
 804890f:       55                      push   %ebp
 8048910:       89 e5                   mov    %esp,%ebp
 8048912:       83 ec 18                sub    $0x18,%esp
 8048915:       8b 45 0c                mov    0xc(%ebp),%eax
 8048918:       89 44 24 04             mov    %eax,0x4(%esp)
 804891c:       8b 45 08                mov    0x8(%ebp),%eax
 804891f:       89 04 24                mov    %eax,(%esp)
 8048922:       e8 6d f7 ff ff          call   8048094 <main>
 8048927:       89 04 24                mov    %eax,(%esp)
 804892a:       e8 d4 22 00 00          call   804ac03 <exit>

（对就是楼上那个片段）

这是 lib/user/entry.c，负责在用户程序返回后调用 exit syscall

触发页面错误的指令是 mov 0xc(%ebp),%eax，作用是读取栈上的 argv，不过实际读取了 0xc0000008

用 gdb 追踪内核创建进程和进入用户模式的过程：

创建新线程
分配 PCB，并和主线程关联
糊一个假的中断帧，从磁盘加载用户程序，分配栈内存，初始化中断帧内的寄存器值
调用正常中断恢复的流程，通过 iret 进入用户空间，并开始执行用户程序

这里炸掉是因为内核没有正确根据 cdecl 实现 _start 的 argc, argv 的传递，而是直接把中断帧的 %esp 设置为实际栈内存的顶部，导致 argc, argv 的理论位置超过了栈顶进入了内核虚拟内存空间，详见下图：

CamScanner 10-12-2026 06.24.jpg
~~我草我字好丑~~

任务要求我们只要修好错误就行，不必正确实现传参，所以很简单：

  // Hack for do-nothing.
  // Offset esp so argc, argv copy in _start does not trigger page fault.
  if_.esp -= 0xc;

给初始 %esp 加个偏移量，保证 argc, argv 都在栈内就可以了

do-not-much

/* Does pretty much nothing. */

#include "tests/lib.h"

int main(int argc, char* argv[] UNUSED) {
  return argc;
}

测试要求 exit(1)，也就是 argc 需要是 1，我们在内核模式下分配栈后设置一下即可

  // Hack for do-nothing.
  // Offset esp so argc, argv copy in _start does not trigger page fault.
  if_.esp -= 0xc;
  // Hack for do-not-much.
  // Set argc to 1.
  *(int*) (if_.esp+0x4) = 1;

stack-align-v

/* Does absolutely nothing. */

#include "tests/lib.h"

int main(int argc, char* argv[] UNUSED) {
  register unsigned int esp asm("esp");
  if (argc != 1)  // argc must be 1.
    return -1;
  else
    return esp % 16;
}

测试要求 exit(0)，即 esp 必须 16B 对齐，%esp 偏移量 +8 即可

  // Hack for do-nothing.
  // Offset esp so argc, argv copy in _start does not trigger page fault.
  if_.esp -= 0xc + 0x8; // Align to 16 bytes.
  // Hack for do-not-much.
  // Set argc to 1.
  *(int*) (if_.esp+0x4) = 1;

#20 · 2026-10-11

这个 docker workspace 真是让人头疼，因为共享 host 内核所以 perf 装上用不了 🫠

不过 proj* 里大概也用不上（