Skip to content

operating system

process & thread

组成部分 虚拟地址 物理地址 不同进程间是否虚拟相同 不同进程间是否物理相同 备注
内核代码 内核高地址（如 0xffffffff80000000） 相同 ✅ 相同 ✅ 相同 全系统唯一一份内核
内核栈 内核高地址（每进程一段） 不同 ❌ 不同 ❌ 不同 每个进程/线程私有
用户代码 0x01000000 通常不同 ✅ 相同 ❌ 不同（除非共享） ELF 装载后的 text 段
用户栈 0x01001000 不同 ✅ 相同 ❌ 不同 每进程私有
sp（用户态） 指向用户栈虚拟地址 N/A ✅ 相同(起始都是 0x1001000 + PAGE_SIZE) ❌ 实际指向不同物理页 寄存器保存的是虚拟值
sscratch 保存内核栈指针或进程相关值 N/A ❌ 不同 ❌ 不同 每个 hart/线程独立
通用寄存器 寄存器，不是地址空间 N/A ❌ 不同 ❌ 不同 上下文切换时保存

加入多线程:

组成部分 虚拟地址（同一进程内线程） 物理地址（同一进程内线程） 不同进程间 说明
内核代码 相同 相同 相同 全系统唯一
用户代码 相同 相同 通常不同 线程共享同一地址空间
内核栈 不同 不同 不同 每线程一份
主线程用户栈 0x01001000 独立 不同 只是“约定起点”
其他线程用户栈 不同 不同 不同 由内核分配虚拟区间
sp（用户态） 不同 指向不同物理页 不同 每线程独立
sscratch / TLS 指针 不同 不同 不同 线程本地
寄存器集合 不同 不同 不同 执行上下文

fork 后父子进程修改 global/local 变量互不影响, 因为尽管用户代码段/数据段直接复制, 但是由于写时复制 (COW), 修改时会各自分配一个物理页, 所以不影响; local 在不同的用户栈中, 不影响

fd 父子进程复制, 相互独立; 同时文件表项共享, 父/子进程 close(fd) 时减少引用计数

所以文件的读写是共享的, global 变量的读写是独立的

schedule algorithm

round robin

轮询, 任务到达就放到队列中, 对于在队列中的进程按顺序执行, 执行完立即执行下一个任务, 循环直到结束

FCFS

先到先执行

SJF

优先执行剩余时间短的任务, 中途到达的任务不可抢占

SRTF

任务到达后如果剩余时间比当前任务的剩余时间短则可以抢占当前任务, 优先执行短的任务

process synchronzation

semaphores

bounding-buffer

如果不用 mutex 结果错误

如果只使用一个 mutex 信息量和 count 整数, 会使得结果正确但效率降低

使用 empty 和 full 可以允许 consumer, producer 并发, 只在更新缓存区时互斥

而且只用一个 count 也很难设计状态

对于 N = 1 的 bounding-buffer, 不需要 mutex, 因为不会出现 producer 和 consumer 同时需要修改 buffer 的情况

reader-writer

如果有计数变量 counter, 对其的读写都需要 mutex 保护

例如:

a，b两点之间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下： 1. 当ab之间有车辆在行驶时同方向的车可以同时驶入ab段，但另一方向的车必须在ab段外等待； 2. 当ab之间无车辆在行驶时，到达a点（或b点）的车辆可以进入ab段，但不能从a点和b点同时驶入； 3. 当某方向在ab段行驶的车辆驶出了ab段且暂无车辆进入ab段时，应让另一方向等待的车辆进入ab段行驶。 请用信号量为工具，对ab段实现正确管理以保证行驶安全。

这个相当于两种互斥的 readers

如果先判断 if(ab == 0) wait(Sab);, 那么两辆车可能有一个会长时间等待 Sab, 导致原本可以同时进入 ab 段行驶, 现在只能等待前一辆车出来才能进入, 变成串行的

monitor / condition variables

dining-philosopher

等待公共资源 (筷子) 会导致死锁

尽管特定的访问顺序 (如优先访问/等待编号小的筷子) 能防止死锁, 但是这样不好

所以使用条件变量, 每个哲学家等待自己

条件变量 signal 一定唤醒一个进程, 信号量不一定

other examples

// thread 1
while(1){
    P(mutex_Y1);
    w = add(x, y);
    V(mutex_Y1);
}
// thread 2
while(1){
    P(mutex_Y2);
    P(mutex_Z);
    w = add(y, z);
    V(mutex_Z);
    V(mutex_Y2);
}
//thread 3
while(1){
    P(mutex_Z);
    z = add(z, w);
    V(mutex_Z);
    P(mutex_Y1);
    P(mutex_Y2);
    y = add(y, w);
    V(mutex_Y2);
    V(mutex_Y1);
}

注意 thread 3 一定要先释放 mutex_Z 再等待 mutex_Y2, 不然与 thread 2 死锁

启动 OS

basic concept

  1. BIOS: 写在 ROM 中, 先进行开机硬件自查, 之后根据 boot sequence 选择存储设备
  2. MBR: 读取存储设备的第一个扇区, 512 字节内容为 MBR (主引导记录), 里面有引导机器码, 分区表和签名 (得到 boot 分区)
  3. VBR/Grub: 控制权转交给分区 / Grub, 如果是分区则读取 VBR (卷引导记录), 确定操作系统的位置; 如果是 Grub, 直接从文件系统选择操作系统
  4. 启动内核...

grub stage

  • 阶段 1: 存储在 MBR (BIOS 模式) 或 ESP 分区 (UEFI 模式), 仅包含指向后续阶段的代码 (因空间限制, 无法存储完整逻辑)

  • 阶段 1.5(仅 BIOS 模式): 位于 MBR 与第一个分区之间的间隙 (通常 32KB-1MB), 提供文件系统驱动 (如 ext4、xfs), 用于访问 /boot 分区中的 GRUB 核心文件

  • 阶段 2: 存储在 /boot/grub, 加载 GRUB 配置文件 (/boot/grub/grub.cfg), 显示引导菜单, 供用户选择启动项 (如不同内核版本、其他操作系统)

Legacy BIOS Boot Flow (Sector-based)

1. Hardware Stage * Power On: CPU in 16-bit Real Mode. * POST: Hardware self-test. * MBR: BIOS loads the first sector (MBR) of the drive to memory.

2. OS Loading Stage * Windows (Relies on VBR) * MBR checks Partition Table -> Finds Active Partition. * Loads VBR (Volume Boot Record) of that partition. * VBR loads BOOTMGR -> Reads BCD -> Loads winload.exe. * winload.exe switches to Protected Mode -> Loads Kernel (ntoskrnl.exe).

  • Linux (Skips VBR)
    • MBR (GRUB Stage 1) executes.
    • Jumps directly to MBR Gap (Stage 1.5 core.img).
    • Loads filesystem drivers (now can read /boot) -> Reads /boot/grub/grub.cfg.
    • Loads Kernel (vmlinuz) & initrd -> Kernel switches mode manually.

Modern UEFI Boot Flow (File-based)

1. Hardware Stage * Power On: CPU in Protected Mode (32/64-bit). * Init: Load DXE drivers. * ESP: Firmware mounts the EFI System Partition (FAT32).

2. OS Loading Stage * Windows * Firmware directly loads file: \EFI\Microsoft\Boot\bootmgfw.efi. * bootmgfw.efi reads BCD -> Loads winload.efi. * Calls ExitBootServices() -> Hands over to Kernel (ntoskrnl.exe).

  • Linux
    • Firmware loads file: \EFI\...\shimx64.efi (Secure Boot) -> grubx64.efi.
    • grubx64.efi reads grub.cfg -> Displays menu.
    • Loads Kernel (vmlinuz) via EFI Protocols (EFI Stub).
    • Calls ExitBootServices() -> Hands over to Kernel.

对比

特征 BIOS (Windows) BIOS (Linux) UEFI (Windows) UEFI (Linux)
磁盘分区表 MBR (主分区限制) MBR GPT GPT
第一步 读取 MBR (512字节) 读取 MBR (512字节) 挂载 ESP 分区 挂载 ESP 分区
关键中介 VBR (分区首扇区) MBR Gap (扇区缝隙) 无 (直接读文件) 无 (直接读文件)
引导文件 BOOTMGR (无扩展名) GRUB Stage 2 bootmgfw.efi grubx64.efi
加载器 winload.exe GRUB 自身 winload.efi GRUB / EFI Stub
内核交接前 16位实模式，需手动切模式 16位实模式，需手动切模式 64位模式，ExitBootServices 64位模式，ExitBootServices

double systems

先装 windows 再装 linux

grub 会覆盖 MBR, 但是 grub 本身可以支持双系统选择, 此时可以选择启动 windows 或 linux

先装 linux 再装 windows (或第一种情况重装 windows)

BIOS (Legacy) + MBR
  • Only one MBR (512 bytes)
  • Linux install → GRUB writes to MBR
  • Windows reinstall → overwrites MBR completely
  • Result: GRUB gone, boot straight to Windows
  • Fix: Boot Linux Live USB → grub-install /dev/sdX
UEFI + GPT
  • Bootloaders are files in ESP (FAT32)
  • Linux: /EFI/ubuntu/grubx64.efi (or shimx64.efi)
  • Windows: /EFI/Microsoft/Boot/bootmgfw.efi
  • Windows reinstall:
  • Does NOT delete Linux EFI files
  • Only adds/replaces "Windows Boot Manager" as Boot####0001 in NVRAM
  • Result: GRUB still exists, but moved down the boot order
  • Fix:
  • Enter BIOS → move Ubuntu/GRUB to top
  • Or use EasyUEFI/bootice in Windows to reorder

Summary Table

Mode GRUB after Windows reinstall Symptom Fix difficulty
BIOS Physically overwritten Direct boot to Windows High (Live USB)
UEFI Files intact, order changed Direct boot to Windows Low (BIOS reorder)
  • 例外情况 (UEFI): 在重装 Windows 时，选择删除所有分区并重新建立分区, 那么 ESP 分区也会被格式化, 这种情况下 GRUB 文件就真的被删除了. 如果只是格式化 C 盘重装, ESP 分区通常不动, GRUB 就是安全的

grub 选择双系统

BIOS/Legacy 安装 Linux 后

  • Linux GRUB Stage1 会覆盖 Windows MBR
  • 但 Windows 分区 VBR 还在
  • GRUB 用 os-prober 找到 Windows 的 VBR → 生成菜单项
  • 选 Windows → GRUB 执行 chainloader +1 → 交给该分区 VBR → BOOTMGR → Windows

UEFI 安装 Linux 后

  • 两个 .efi 文件独立共存于 ESP
  • Windows: /EFI/Microsoft/Boot/bootmgfw.efi
  • Linux: /EFI/ubuntu/grubx64.efi
  • os-prober 发现 Windows Boot Manager → 添加菜单
  • 选 Windows → GRUB 调用 UEFI API 直接 LoadImage/StartImage 运行 bootmgfw.efi

memory

optimal

最优性证明

FIFO

有可能出现 Belady 现象: 缓存容量增大, 命中率反而降低

\(\underline{例}:\)

\(1,2,3,4,1,2,5,1,2,3,4,5\)

\(C=3: 9\text{ page faults}\)

\(C=4: 10\text{ page faults}\)

LRU

不会有 Belady 现象, 因为容量小的缓存中数据始终是容量大的缓存中数据的子集

当前考虑第 \(i\) 个元素, 最近访问的是 reference sequence 从 \(i-1\) 往前 \(k\) 个不重复元素, 这 \(k\) 个元素一定都在缓存中

所以缓存的数据集合始终为前 \(k\) 个不重复元素, 这使得子集关系成立

Second Chance

clock, 转一圈, 把 R = 1 变成 R = 0, 第二次遇到时, 把 R = 0 替换出去

file

软连接/硬链接

filesystem

每个 disk 由 MBR 规定了至多 4 个主分区 / 3 主分区 + 1 扩展分区

逻辑分区都存放在扩展分区中

每个分区有一个文件系统管理, 里面有 directory + files

linux 只有一个目录树, 即根目录树 /

在 MBR + BIOS 的操作系统中:

  • /boot 必须放主分区，因为 BIOS 引导链只能访问主分区

  • / 放主分区因为启动过程依赖它, 主分区更简单可靠

  • swap 放主分区因为 EBR 链表不稳定和性能考量

所以一般可以把 3 个主分区 (的文件系统) 挂载到 /, /boot, swap

其他逻辑分区挂载到挂载点即可通过目录树访问该分区的文件系统

在 linux 中应用

  1. 查看磁盘分区/文件系统

    lsblk -f
fdisk -l

  2. 创建分区

    使用 parted 工具

    parted [Enter]
(parted) select /dev/sdb
(parted) mklabel gpt
(parted) mkpart [Enter]
Partition name?  []? sdb1
File system type?  [ext2]? ext4 
Start? 1 
End? 1024
(parted) print # 查看分区
quit

  3. 创建文件系统

    mkfs.ext4 /dev/sdb1
    3. 挂载 
    mount /dev/sdb1 /mnt
blkid /dev/sdb1 # UUID
vim /etc/fstab # 设置开机自动挂载