# jyy_os

**Repository Path**: HduersIT/jyy_os

## Basic Information

- **Project Name**: jyy_os
- **Description**: 南京大学蒋炎岩 2024年春学期《操作系统》课程代码
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 1
- **Created**: 2025-07-29
- **Last Updated**: 2025-07-29

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# <center> 操作系统课堂笔记

南京大学2024春季学期 蒋炎岩的操作系统课程。  
[课程讲义](http://jyywiki.cn/OS/2024/)  
[课堂代码](https://jyywiki.cn/os-demos/)  
[参考手册](https://nju-projectn.github.io/ics-pa-gitbook/ics2024/)

## 0. 开发环境搭建 <a id="0.开发环境搭建"></a>

阅读 [参考手册](https://nju-projectn.github.io/ics-pa-gitbook/ics2024/) PA0 - 世界诞生的前夜: 开发环境配置。  
主要完成 [nemu](https://github.com/NJU-ProjectN/nemu) 和 [abstract-machine](https://github.com/NJU-ProjectN/abstract-machine) 和 [fceux-am](https://github.com/NJU-ProjectN/fceux-am)的下载 以及 nemu的安装。

- 下载代码

``` sh 
git clone -b 2024 git@github.com:NJU-ProjectN/ics-pa.git ics2024
cd  ics2024
bash init.sh nemu
bash init.sh abstract-machine

source ~/.bashrc
```

- 安装 nemu

``` sh
sudo apt install bison
sudo apt install flex
sudo apt install libncurses5-dev
sudo apt install libreadline-dev
sudo apt install libsdl2-dev

cd nemu
make menuconfig          # 进入界面选定<Exit>回车<Yes>回车
make 
```



## <center> 绪论 </center>

## 1. 操作系统概述  

### 1.1 为什么要学“任何东西”  

因为我们要重走<font color=red> 从无到有</font> 的发现历程!  
理解学科中的基本动机、基本方法、里程碑、走过的弯路。
最终目的：应用、创新、革命。

### 1.2 什么是操作系统？  

> Operating System: A body of software, in fact, that is responsible for making it easy to run programs (even allowing you to seemingly run many at the same time), allowing programs to share memory, enabling programs to interact with devices, and other fun stuff like that. (OSTEP)  

我们不需要“精准”的教科书定义。
操作系统是管理软/硬件、为程序提供服务的程序。

### 1.3 操作系统的发展史  

三个重要线索：
硬件、软件、操作系统

### 1.4 理解计算机硬件（电路）

一个极简的公理系统（导线、时钟、逻辑门、触发器）能支撑非常复杂的数字系统设计。

### 1.5 数码管模拟程序

[程序说明](./course01/logisim/README.md)

### 1.6 理解计算机软件

高级语言代码 --> 指令序列 --> 二进制文件 -->  处理器执行  

[mini-rv32ima](./course01/mini-rv32ima/README.md)

## 2.应用视角的操作系统

### 2.1 第一个程序 hello world

[hello.c](./course02/hello.c)并不是最小的程序。

```C++
int main() {
    printf("Hello World\n");
}
```

编译 链接 hello.c 文件（编译环境 Ubuntu22, gcc-11）

```sh
gcc hello.c         # gcc (gcc version 11.4.0) 会报警告，但可以生成 elf文件 a.out
file a.out          # 查看 a.out 文件属性
./a.out             # 执行 a.out 打印 Hello World

readelf -a a.out    # 用 readelf 分析 a.out
objdump -d a.out    # 用 objdump 反汇编 a.out , 找不到 printf

gcc hello.c -static # 生成静态链接的 elf文件。 此时 a.out 比之前大几十倍。
objdump -d a.out    # 再用 objdump 反汇编 a.out , 找到 printf

gcc --verbose hello.c   # --verbose 选项能输出更详细的编译信息。
gcc -Wl,--verbose hello.c   # -Wl, 将后面的参数传给链接器。输出更详细的链接信息。

gcc -c hello.c      # 只编译不链接 生成 hello.o 
ld hello.o          # 链接 hello.o 失败。undefined reference to `puts'
```

<font color=red>删除 hello.c 中的 printf 语句</font>

```C++
int main() {
}

#if 0
int main() {
    return 0;   // 在本例中，有无 return 0;编译出的hello.o文件都一样。
}
#endif
```

编译、链接都成功，但执行报错。gdb调试发现程序执行了，在 <code>return</code> 的时候发生了段错误。  
<font color=red> ret 之后 pc 变成了 1 从而触发段错误。</font> 说明栈顶存的1，本来应该存子函数结束后的下一条语句的地址。  
说明:直接用 <code>gcc hello.c</code> 编译出的 a.out 不会触发段错误，因为默认链接了许多库。<code>gcc hello.c -Wl,-v</code> 查看链接的详细信息。

```bash
kwq@kwq-machine:~$ gcc -c hello.c      # 只编译不链接 生成 hello.o 
kwq@kwq-machine:~$ ld hello.o          # 链接 hello.o 有警告，但成功生成 a.out
ld: warning: cannot find entry symbol _start; defaulting to 0000000000401000
kwq@kwq-machine:~$
kwq@kwq-machine:~$ ld hello.o  --entry main  # 链接警告消除
kwq@kwq-machine:~$ ./a.out             # 执行报段错误。Segmentation fault (core dumped)
kwq@kwq-machine:~$
kwq@kwq-machine:~$ gdb a.out           # 调试。starti 程序执行到 main()。layout asm 显示汇编代码。si 单步执行
```

程序不返回

```C++
int main() {
    while(1);
}
```

编译、链接、执行都成功。但是程序不会结束了。  
引出问题，程序怎么结束? 电脑怎么关机? 有关机指令吗?(没有)。  
引出 系统调用。

```sh
gcc -c hello.c && ld hello.o    # 编译 && 链接 得到 hello.o && a.out

./a.out                         # 执行成功
```

### 2.2 系统调用实现 hello world

系统调用实现最小 hello world 程序。具体代码见 [minimal.S](./course02/minimal.S)  
strace 是一个Linux系统下的强大调试工具，用于跟踪用户空间进程对系统调用的执行情况。

```sh
make                    # 编译 minimal.S 生成 minimal.out
strace ./minimal.out    # 跟踪执行 minimal.out
```

### 2.3 汉诺塔

[hanoi](./course02/hanoi/README.md)

#### 2.3.1 递归实现汉诺塔

[hanoi-r.c](./course02/hanoi/hanoi-r.c)

#### 2.3.2 非递归实现汉诺塔

[hanoi-nr.c](./course02/hanoi/hanoi-nr.c)

### 2.4 总结

C语言是状态机、gdb是状态机、程序是状态机、操作系统也是状态机

## 3.硬件视角的操作系统

### 3.1 固件

固件（Firmware）是位于BIOS芯片中的代码。其功能是运行操作系统前扫描计算机硬件，加载操作系统。  
如今的固件(UEFI, Unified Extensible Firmware Interface)有图形化界面，算得上一个小的“操作系统”。

- CPU reset 后初始化硬件， 对接操作系统 Boot Loader

对于40年前的 IBM PC/PC-DOS 2.0(1983)，BIOS启动后会访问硬盘的**主引导记录(MBR, Master Boot Record)**，如果MBR最后2个字节是0x55, 0xaa，则认为该MBR可以启动。

- 主引导记录（MBR）是硬盘的第一个扇区。
- Firmware（BIOS）会加载 MBR 到 0x7c00

MBR（Master Boot Record） 有三个部分。

- 主引导例程：446 字节的主引导例程包括一个可变负载编码器，这是 MBR 的必要数据。硬盘驱动器启动后，MBR 会立即将控制权转移到分区表中列出的操作系统。
- 磁盘分区表 （DPT）：DPT 位于硬盘的第一个扇区中，包含有关分区位置的信息。它有 64 个字节。可以根据需要创建扩展分区，最多四个分区（每个分区 16 字节）。
- 识别码：MBR 可以通过其识别码来识别。它的值为 55AAH 或 AA55H，大小为 2 字节。

### 3.2 观察和调试 legacy BIOS

使用 __qemu-system-x86_64__ 虚拟机加载镜像文件。通过调试发现 BIOS使用 <code>rep insl</code> 指令每次从磁盘加载两个字节到内存。

[Makefile](./course03/debug-firmware/Makefile)

```sh
cd debug-firmware       # 进入工作目录
make                    # 生成镜像文件 minimal.img
make run                # 启动 qemu-system-x86_64 加载镜像文件
make debug              # 开启gdb调试、启动 qemu-system-x86_64 加载镜像文件
```

### 3.3 实验框架的正确打开方式

请完成[0.开发环境搭建](#0.开发环境搭建)中的内容[Makefile](./course03/debug-bootloader/Makefile)才能跑起来

> <code>make debug</code> 报错 gdb.error: \$(AM_HOME)/am/src/x86/qemu/boot/boot.o: No such file or directory.   
报错原因： 下载的[abstract-machine](https://github.com/NJU-ProjectN/abstract-machine)工具有问题。  
解决方法： 修改\$(AM_HOME)/am/src/x86/qemu/boot/Makefile 第4行（编译行之后）添加 <code>cp bootblock.o boot.o</code>

## 4.数学视角的操作系统

- 程序是一种“数学严格”的对象。
  - 程序 = 初始状态 + 迁移函数

### 4.1 为操作系统建模

操作系统模型 [os-model.py](./course04/os-model/os-model.py)

- 应用视角（自顶向下）
  - 操作系统 = 对象 + API
    - 应用通过 syscall 访问操作系统
- 机器视角（自底向上）
  - 操作系统 = C程序
    - 运行在计算机硬件上的一个普通程序

> 操作系统 = 状态机的管理者
  当然，操作系统自己也是状态机，有自己的状态。

- 初始状态
  - 仅有一个“main”状态机
- 迁移
  - 选择一个状态执行一步

- 调度：状态机的选择不确定
  - <code>current = random.choice(self.procs)</code>
  - 操作系统每次次可以随即选择一个状态机执行一步
- I/O：系统外的输入不确定
  - read返回的结果也有两种可能性
  - 执行<code>t = sys_read()</code>后，t=0 或 t=1

### 4.2 枚举法理解操作系统

构建状态图检查程序正确性。  [mosaic.py](./course04/mosaic/mosaic.py)

## <center> 并发 </center>

## 5.多处理器编程

### 5.1 线程模型和线程库

- 课堂中的线程库头文件 [thread.h](./course05/thread-lib/thread.h)简化了<code>pthread_create()</code>这个API的使用。
- [memory.c](./course05/thread-qa/memory.c)证明了多线程共享全局变量。[Makefile](./course05/thread-qa/Makefile)中的<code>TLIB_PATH</code>是[thread.h](./course05/thread-lib/thread.h)的路径。
- [stack.c](./course05/thread-qa/stack.c)测试了堆栈的大小。<font color=red>8MB</font>

### 5.2 原子性

编译命令： <code>make TLIB_PATH=../thread-lib/</code>

- [山寨支付宝](./course05/alipay/README.md): 余额100，但[alipay.c](./course05/alipay/alipay.c)两次扣款100后，余额变成了<code>2<sup>64</sup> - 100</code>展示了并发编程的隐患。
- [加法测试](./course05/sum/README.md): [sum.c](./course05/sum/sum.c)展示了并发编程比想象中更困难。
- [加法模型](./course05/sum-model/README.md): 可以使用[mosaic.py](./course05/mosaic/mosaic.py)和[collect.py](./course05/mosaic/collect.py)这两个工具得到[sum.py](./course05/sum-model/sum.py)多线程执行的所有情况。<code>./mosaic.py -c ../sum-model/sum.py | ./collect.py</code>

### 5.3 顺序执行

还是[加法测试](./course05/sum/README.md): 用不同的优化等级编译[sum.c](./course05/sum/sum.c)

```sh
# 不做优化，每次执行的结果都不同。 很容易触发并发bug
make TLIB_PATH="../thread-lib/ -O0"
gcc -I../thread-lib/ -O0 -o sum sum.c
./sum
sum = 102893221
2*n = 200000000
./sum
sum = 99391903
2*n = 200000000

# O1，几乎每次都是正确结果的一半。查看汇编发现 T_sum()等价 
# rax=1;  rdx+=0x5f5e101; 
# flag:  rcx=rax;  rax++;  cmp(rax, rdx); jne flag;
# sum = rcx
make TLIB_PATH="../thread-lib/ -O1"
gcc -I../thread-lib/ -O1 -o sum sum.c
./sum
sum = 100000000
2*n = 200000000

# O2，几乎每次都得到正确答案。查看汇编发现 T_sum() 只有一条等价语句 sum = 0x5f5e100;
# 其中 0x5f5e100 == 100000000 。一条语句很难触发并发bug！隐患很难查
make TLIB_PATH="../thread-lib/ -O2"
gcc -I../thread-lib/ -O2 -o sum sum.c
./sum
sum = 200000000
2*n = 200000000
```

### 5.4 全局指令顺序

单处理器多线程符合如下假设：
- 处理器会保证指令“看起来”顺序完成
- 处理器也是编译器。(编译器可以调换指令的顺序，处理器也可以)
  - 预取状态机执行的若干步，然后像编译器一样优化。

每个处理器都有自己的高速缓存。（内存在高速缓存之下。硬盘在内存之下。）导致多处理器多线程的实际执行的情况更加杂乱。

[mem-model.c](./course05/mem-model/mem-model.c) 实现了 [mem-model.py](./course05/mem-model/mem-model.py) 中的功能。  
在C代码中，主线程T_flag是一个死循环，睡眠1us同时举起2个旗子，然后等待2面旗子被T1和T2放下。  
T1和T2都在等自己的旗子举起来，然后写自己的变量为1，再读别人的变量并打印。最后放下自己的旗子。 

> F1和F2是<code>atomic_int flag;</code>这个变量的第0位和第一位。所以<code>flag=3;</code>就是同时举起两面旗子。

```mermaid
flowchart LR

B1((T_1)) --->B2(while !F1)
B2 --一.1--> B3(x=1)
B3 --一.2--> B4(read y;   print y)
B4 --一.3--> B5(F1=0)
B5 --> B2

A1((T_flag)) --> A2(x=y=0; usleep 1)
A2 --> A3("F1=F2=1
同时举旗")
A3 ----> A4("while F1 || F2
等待2个旗子都放下")
A4 ----> A2

C1((T_2)) --->C2(while !F2)
C2 -- 二.1 --> C3(y=1)
C3 -- 二.2 --> C4(read x;  print x)
C4 -- 二.3 --> C5(F2=0)
C5 --> C2
```

可以肯定不会出现0 0，但实验出现了很多次0 0; 可以肯定1 1一定会出现， 但实验结果1 1几乎不出现。出现 1 1 必须 满足如下条件：  
<code>一.1</code> 和 <code>二.1</code> 必须在 <code>一.2</code>和<code>二.2</code> 之前执行。 

``` sh
../mosaic/mosaic.py -c mem-model.py | ../mosaic/collect.py
01
10
11
|V| = 60, |E| = 69.
There are 3 distinct outputs.


make TLIB_PATH=../thread-lib/
gcc -O2 -I../thread-lib/ -o mem-model mem-model.c

# 一千万次很耗时, 跑了一个多小时
./mem-model | head -n 10000000 | sort | uniq -c
8982738 0 0 
 920526 0 1 
  96735 1 0 
      1 1 1
```

## 6.并发控制：互斥（1）

### 6.1 实现互斥：关中断

[Stop-the-world 实现互斥](./course06/stop-the-world/README.md), 在[cli.c](./course06/stop-the-world/cli.c)代码中只有关中断和开中断两条语句。程序在应用层不能正常执行，OS会拒绝APP直接使用cli汇编。如果编译到系内核，然后运行在qemu-system-x86_64，发现模拟器一直重启。因为开中断了，然而并没有写中断处理函数，所以导致电脑一直重启。

``` sh
make
make debug

(gdb) layout asm
(gdb) d 1
(gdb) c
```

### 6.2 实现互斥：peterson算法

[Peterson 算法](./course06/peterson/README.md)的python实现见[peterson.py](./course06/peterson/peterson.py)，本质是访问公共变量时，将自己的旗子举起,再谦让让别人访问（将turn设置为别人）。然后观察别人的旗子是否举起，以及 turn是不是自己。

``` sh
../../course05/mosaic/mosaic.py -c peterson.py |  grep \"cs\" | sort | uniq 
          "cs": ""
          "cs": "❶" 
          "cs": "❷" 

make TLIB_PATH=../../course05/thread-lib/
./peterson | wc -c
peterson: peterson.c:35: critical_section: Assertion `atomic_fetch_add(&inside, -1) == 1' failed.
peterson: peterson.c:25: critical_section: Assertion `atomic_fetch_add(&inside, +1) == 0' failed.
1699840
```
对于C语言实现的[peterson.c](./course06/peterson/peterson.c)， 开启 __禁止CPU乱序执行__ 能正常互斥。  
- 如果取消了 __禁止CPU乱序执行__ ，很容易触发 __互斥失效__。  
- 但是调用了 putchar() ；即使允许乱序执行，在有的CPU上很难触发 __互斥失效__。
- peterson算法只能满足两个线程的互斥。

### 6.3 实现互斥：原子指令与自旋

[使用原子指令实现求和](./course06/sum-atomic/README.md)，具体代码见[sum.c](./course06/sum-atomic/sum.c)。原子指令的执行速度比不加原子关键字慢。  
有了原子指令关键字。就可以实现自选锁了。  
[cmpxchg 实现自旋锁](./course06/sum-locked/README.md)，具体代码见[sum.c](./course06/sum-locked/sum.c)。  
<code>make TLIB_PATH=../../course05/thread-lib</code>

## 7.并发控制：互斥（2）

## <center> 虚拟化 </center>

## <center> 持久化 </center>

## <center> 总结 </center>

## <center> 积累 </center>

### hyper-V 之 ubuntu22 硬盘扩容

[参考网站](https://sl51.cn/archives/2024/01/24/linux-disk)

1. hyper-V 硬盘编辑容量大小。
    + 如果 __Edit__ 选项是浅色的，提示“hyperv硬盘 无法进行编辑，因为此虚拟机存在检查点”。需要删除 __检查点__  。 
2. ubuntu22 用 fdisk 命令分区扩容。 
    - lsblk 查看块设备。可以看到 硬盘sda 有 sda1 （目前根目录所在分区）， sda2（扩容的分区） 等分区。
    + 使用 fdisk 命令重新分区。（sudo fdisk  /dev/sda）
      - 命令 d 删除当前挂在到根目录(/) 的分区（sda1）。
      - 命令 d 删除 sda2 分区。
      - 命令 n 新建分区。（都用默认参数即可. 分区名是sda1, remove the signature 选择 No）
      - 命令 w 保存并退出。
    - 重启系统。（sudo reboot）。
    - 刷新文件系统。（ext文件系统使用该命令： resize2fs /dev/sda1）

### 常用命令

|命令|说明|注意|
|:---|:---:|---|
|sudo nautilus /|在Ubuntu终端打开文件资源管理器的根目录||
|uname  -i| 查看Linux系统版本||
|cat /proc/cpuinfo|查看CPU信息||

### gcc

|命令|说明|注意|
|:---|:---:|---|
|gcc -E|-E 预处理|生成.i文件|
|gcc -S|-S 编译|生成.s文件|
|gcc -c|-c 汇编|生成.o文件|
|gcc |默认情况下，如果你不提供 -E、-S 或 -c 选项，GCC 会执行整个编译过程，包括预处理、编译、汇编和链接|生成一个可执行文件|
|gcc -g| -g 选项生成调试信息，使得调试器（如GDB）能够更好地理解和调试生成的可执行文件。|虽然-g选项不会显著影响程序的运行性能，但会显著增加可执行文件的大小|
|gcc -I/path/to/headers|-I选项告诉编译器在预处理阶段搜索头文件的额外目录|大写的 i|
|gcc -L/path/to/libs|-L选项告诉链接器在链接阶段搜索库的额外目录||
|gcc -l|-l选项告诉链接器链接到指定的库。库名应该省略前缀 lib 和文件扩展名。比如-lm表示要链接数学库libm.so|小写的 L|
|gcc -Wl,| -Wl 选项是用来向 GCC 传递选项给链接器（linker）的|“,”两边都不能有空格|
|gcc -o myprogram myfile.c -Wl,-L/path/to/library -Wl,-lmylibrary|这里的 -L 和 -l 都是链接器的选项，通过 -Wl, 传递给链接器||