参考

循序渐进，学习开发一个RISC-V上的操作系统 - 汪辰 - 2021春

riscv-operating-system-mooc | Gitub
riscv-operating-system-mooc | Gitee

环境配置

建议使用 docker 容器来配置环境

1
2
# 拉取 github 仓库
git clone git@github.com:plctlab/riscv-operating-system-mooc.git
1
2
3
4
5
6
7
# 从 dockerhub 拉取 ubuntu:20.04 镜像
# https://hub.docker.com/layers/library/ubuntu/24.04/images/sha256-3963c438d67a34318a3672faa6debd1dfff48e5d52de54305988b932c61514ca
docker pull ubuntu:20.04
# 通过镜像创建 docker 容器, 并将 github 仓库对应的目录挂载到容器中
docker run -dit --privileged=true --name riscv \
--volume path/to/riscv-operating-system-mooc:/root/riscv-operating-system-mooc \
ubuntu:20.04 /bin/bash

建议使用 VSCode Dev-Containers 连接容器. 当然也可以使用 docker attach 命令

1
docker attach riscv

进入容器, 在终端中执行下面的命令安装 GNU 套件, 包括 gcc, make, git, qemu-system-misc 等工具

1
2
apt update
apt install build-essential gcc make perl dkms git gcc-riscv64-unknown-elf gdb-multiarch qemu-system-misc

测试各个工具的版本

1
2
3
4
5
6
7
8
gcc --version
make --version
git --version
gdb --version
gdb-multiarch --version
riscv64-unknown-elf-gcc --version
qemu-system-riscv32 --version
qemu-system-riscv64 --version

建议额外安装 gcc-riscv64-linux-gnu 和 qemu-user

1
2
apt install gcc-riscv64-linux-gnu
riscv64-linux-gnu-gcc --version

gcc-riscv64-unknown-elf 工具所对应的 riscv64-unknown-elf-gcc 命令不能编译带 c 库的源码, gcc-riscv64-linux-gnu 所带的 riscv64-linux-gnu-gcc 命令可以用于编译带 c 库的 c 语言源码.

1
2
3
apt install qemu-user
qemu-riscv32 --version
qemu-riscv64 --version

qemu-system-misc 工具所带的 qemu-system-riscv32 和 qemu-system-riscv64 两个命令用于运行完整的 riscv 仿真操作系统, 而 qemu-user 的 qemu-riscv32 和 qemu-riscv64 命令可以用于模拟 riscv 机器执行单个 riscv 应用程序.

qemu-system-riscv64 和 qemu-riscv64

Qemu 有两种运作模式:

  • User mode: 直接运行 riscv 应用程序
  • System mode: 模拟整个计算机系统, 包括中央处理器以及其它周边设备

System mode 对应着 qemu-system-riscv64 命令, User mode 对应着 qemu-riscv64 命令:

  • qemu-system-riscv64: 这是一个用于运行完整虚拟机的命令，通常用于仿真整个 RISC-V 计算机系统. 它提供了对 RISC-V 硬件和系统模拟的支持, 允许您运行 RISC-V 操作系统和应用程序, 就像在真实硬件上一样. 您可以使用此命令启动 RISC-V 虚拟机, 安装操作系统, 并在虚拟机内部运行应用程序. 它通常用于开发和测试操作系统和系统软件.

    1
    qemu-system-riscv64 -machine virt -cpu rv64 -m 512M -kernel your_kernel_image

  • qemu-riscv64: 这是一个用于运行 RISC-V 用户空间程序的命令, 通常用于在主机操作系统上运行单个 RISC-V 应用程序. 与 qemu-system-riscv64 不同, 它不涉及虚拟机或完整的系统仿真, 而是仅运行一个 RISC-V 用户空间程序. 这对于在主机操作系统上运行 RISC-V 二进制文件或进行应用程序开发和调试非常有用.

    1
    qemu-riscv64 your_riscv_executable

简单来说, qemu-system-riscv64 用于完整的 RISC-V 系统仿真, 而 qemu-riscv64 用于在主机操作系统上运行单个 RISC-V 应用程序.

第2章(上)-RISC-V ISA 介绍

参考文档

技术规范 Specifications

参考手册

The RISC-V Reader: An Open Architecture Atlas Authored by David Patterson, Andrew Waterman Edition: 1st

ISA是什么

ISA (Instruction Set Architecture) 指令集架构是底层硬件电路面向上层软件程序提供的一层接口规范

1
2
3
4
Application
Operating System
ISA <--
Microarchitecture

ISA 定义了

  • 基本数据类型: BYTE | HALFWORD | WORD
  • 寄存器 (Register)
  • 指令 (Instruction)
  • 寻址模式
  • 异常或者中断的处理方式

CISA vs RISC

  • CISA (Complex ISA) 复杂指令集: 针对特定的功能实现特定的指令, 导致指令的数目比较多, 但生成的程序长度相对较短. 例如 x86 指令集
  • RISA (Reduced ISA) 精简指令集: 只定义基本的指令, 对复杂的功能采用基本指令组合实现, 这样指令的数目比较精简, 但生成的程序长度相对较长. 例如 RISC-V 指令集.

ISA的宽度

ISA (处理器) 的宽度指的是 CPU 中 “通用寄存器” 的宽度 (二进制的位数). 宽度决定了寻址的范围大小, 以及数据运算的能力.

通用寄存器的宽度 寻址范围 应用场景
8位 2^8 = 256 早期单片机 8051
16位 2^16 = 65536 x86系列的鼻祖 8086, MSP430系列单片机
32位 2^32 = 4294967296 早期的终端, 个人计算机和服务器
64位 2^64 = 18446744073709551616 目前主流的移动智能设备, 个人计算机和服务器

知名 ISA 介绍

X86 SPARC Power ARM MIPS RISC-V
Intel Sun IBM ARM MIPS RISC-V

第2章(下)-RISC-V ISA 介绍

RISC-V 简介

RISC-V 读作 “risk-five”, 代表着 Berkeley 所研发的第五代精简指令集

RISC-V ISC 技术规范

Specifications

RISC-V ISC 命名规范

ISA 命名格式为 RV + 32|64 + I|E + [M][A][F[D]][C][G]..., 其中

  • RV 用于表示 RISC-V 体系架构的前缀, 即 RISC-V 的缩写;
  • 32|64|128 用于表示处理器的字宽, 也就是处理器的寄存器的宽度 (bit);
  • I|E: 表示必选的基本整数指令集, 其中 I 表示 Integer 整数, E 表示 Embedded 嵌入式;
  • [M][A][F][D][C][G]...: 为可选的扩展指令集.

RISC-V ISA = 1 个基本整数指令集 + 多个可选的扩展指令集

基本指令集:

  • RV32I (32位整数指令集)
  • RV32E (RV32I的子集, 用于小型嵌入式Embedded场景)
  • RV64I (64位整数指令集)
  • RV128I (128位整数指令集)

扩展指令集:

  • M (Multiplication, 整数乘法与除法指令集)
  • A (Atomic, 存储器原子指令集)
  • F (Float, 单精度浮点指令集)
  • D (Double, 双精度浮点指令集)
  • C (Compressed, 压缩指令集)
  • G (General, IMAFD 的通用组合)

例子:

  • RV32I (最基本的 RISC-V 的实现)
  • RV32IMAC (32位实现, 并支持 Interger 基本整数指令集, 和 Multiply + Atomic + Compressed 扩展指令集)
  • RV64GC (64位实现, 支持 IMAFDC)

通用寄存器

RISC-V 的 Unprivileged Specification 定义了 32 个通用寄存器 (General Purpose Registers) 和一个 PC (Program Counter) 寄存器.

RV32I | RV64I | RV128I 指令集都只包括 32 个通用寄存器, 如果要实现支持 F/D 扩展则需要额外支持 32 个浮点寄存器, RV32E 将 32 个通用寄存器缩减到 16 个.

HART

在 RISC-V 体系结构中, HART（Hardware Thread）指的是硬件线程或硬件处理器核. 每个 HART 是一个独立的执行单元, 能够独立地执行指令流. 通常一个 CPU Core 可以一次执行多个指令流, 为了避免与 CPU 核心的概念混淆, RISC-V 抽象出 HART 的概念. 假设一个四核 RISC-V 处理器, 每个核有两个 HART (并不是硬线上的实现, 而是根据处理器的并行处理能力抽象出的一个该奶奶), 这个处理器总共有 8 个 HART. 每个 HART 都可以执行独立的指令流, 具有自己的程序计数器和寄存器集, 操作系统可以将不同的任务分配给不同的 HART 以实现并行处理.

特权级别

RISC-V 的 Privileged Specification 定义了三个特权级别 (Privilege Level)

Level Encoding Name Abbreviation
0 00 User/Application U
1 01 Supervisor S
2 10 Reserved
3 11 Machine M
Number of levels Supported Modes Intended Usage
1 M Simple embedded systems
2 M, U Secure embedded systems
3 M, S, U Systems running Unix-like operating systems

不同的特权级别分别对应各自的一套 “控制和状态寄存器” (CSR, Control and Status Register), 用于控制相应 Level 下的处理器和获取工作状态. 高级别的特权级别下可以访问低级别的 CSR, 譬如 Machine Level 下可以访问 Supervisor/User Level 的 CSR, 以此类推. 但反之不可以.

RISC-V 定义了专门用于操作 CSR 的指令, 以及特定的指令可以用于在不同特权级别之间进行切换.

内存管理与保护

物理内存保护 (PMP, Physical Memory Protection)

虚拟内存 (Virtual Memory)

异常和中断

异常 (Exception): “an unusual condition occurringat run time associated with an instruction in the current RISC-V hart”
中断 (lnterrupt): “an external asynchronous eventthat may cause a RISC-V hart to experience an unexpected transfer of control”

"异常"是操作系统自身导致的问题, 而"中断"是由外设触发的问题. 在处理完异常后操作系统还会继续执行当前指令, 而在处理完中断后操作系统会跳到当前指令的下一个指令继续往下执行.

第3章-编译与链接

riscv-helloworld-c/Makefile

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
default: hello.elf

hello.o: hello.c
	riscv64-unknown-elf-gcc -c -g -O0 -ffreestanding -march=rv32i -mabi=ilp32 -o hello.o hello.c

start.o: start.s
	riscv64-unknown-elf-as -g -march=rv32i -mabi=ilp32 -o start.o start.s

hello.elf: hello.o start.o baremetal.ld
	riscv64-unknown-elf-ld -T baremetal.ld -m elf32lriscv -o hello.elf hello.o start.o

run: hello.elf
	@echo "Ctrl-A C for QEMU console, then quit to exit"
	qemu-system-riscv32 -nographic -serial mon:stdio -machine virt -bios hello.elf

debug: hello.elf
	@echo "Ctrl-A C for QEMU console, then quit to exit"
	qemu-system-riscv32 -nographic -serial mon:stdio -machine virt -s -S -bios hello.elf

clean:
	rm -f hello.o start.o hello.elf

C/C++ 编译流程

预处理 Preprocess - 编译 Compile - 汇编 Assemble - 链接 linking

预处理: 在这个阶段主要做了三件事: 展开头文件 、宏替换 、去掉注释. 这个阶段需要GCC调用预处理器来完成, 最终得到的还是源文件.

1
g++ -E ./helloworld.cpp -o ./helloworld.i # 预处理, 调用 cc1plus 命令

编译: 这个阶段需要GCC调用编译器对文件进行编译, 最终得到一个 .s 的汇编文件

1
g++ -S ./helloworld.i -o ./helloworld.s   # 编译, 调用 cc1plus 命令

汇编: 这个阶段需要GCC调用汇编器对文件进行汇编, 最终得到一个二进制文件

1
g++ -c ./helloworld.s -o ./helloworld.o   # 汇编, 调用 as 命令

链接: 这个阶段需要GCC调用链接器对程序需要调用的库进行链接, 最终得到一个可执行的二进制文件

1
g++ ./helloworld.o -o ./helloworld.out    # 链接, 调用 ld 命令

最后执行可执行程序

1
2
./helloworld.out
hello, world!

上面的所有步骤可以使用一次命令完成

1
g++ ./helloworld.cpp -o ./helloworld # (预处理+编译+汇编)链接->可执行文件

上述是单个文件编译生成可执行文件的过程, 对于多个文件也是类似的过程. 先编译生成二进制的动态链接库或者静态链接库, 再将多个 .o, .so 文件进行链接生成可执行文件

%%{
  init: {
    'theme': 'base',
    'themeVariables': {
      'primaryColor': '#ffffffff',
      'primaryTextColor': '#000000ff',
      'primaryBorderColor': '#000000ff',
      'lineColor': '#000000ff',
      'secondaryColor': '#00000000',
      'tertiaryColor': '#00000000'
    }
  }
}%%
graph LR
a.cpp --"preprocess"--> a.i --"compile"--> a.s --"assemble"--> a.o --> ld(("link"))
b.cpp --"preprocess"--> b.i --"compile"--> b.s --"assemble"--> b.o --> ld(("link"))
c.cpp --"preprocess"--> c.i --"compile"--> c.s --"assemble"--> c.o --> ld(("link"))
ld --> abc.out

另外并不是只能使用 g++ 编译 c++ 文件, 只能使用 gcc 编译 c 文件. 事实上 gcc 也可以编译 c++ 文件. 使用 gcc 编译 cpp 文件需要加参数 -l stdc++, 表示在链接时指定使用 C++ 的动态链接库

1
gcc ./helloworld.cpp -o ./helloworld -l stdc++

ELF 二进制文件格式

ELF (Executable Linkable Format) 是一种 Unix-like 系统上的二进制文件格式标准

section

segment

ELF 文件处理相关工具: Binutils

使用 readelf 命令可以查看二进制可执行文件

1
2
gcc -c hello.c -o hello.o
readelf -SW hello.o

详细请参考<<程序员的自我修养>>

第4章-嵌入式开发介绍

x86_64 + riscv 编译器

ubuntu 上的 gcc 编译工具默认指向 /usr/bin/x86_64-linux-gnu-gcc-9, 这是一个 x86_64 位机器上的编译器, 即由它所编译生成的二进制可执行文件只能在 x86_64 位机器上运行, 而不能在 risc-v 机器上运行, 应为两者的使用的指令集不同.

1
2
3
4
5
6
7
8
$ whereis gcc
gcc: /usr/bin/gcc /usr/lib/gcc /usr/share/gcc
$ ls -l /usr/bin/gcc
lrwxrwxrwx 1 root root 5 Mar 20  2020 /usr/bin/gcc -> gcc-9
$ ls -l /usr/bin/gcc-9
lrwxrwxrwx 1 root root 22 Oct 24  2022 /usr/bin/gcc-9 -> x86_64-linux-gnu-gcc-9
$ ls -l /usr/bin/x86_64-linux-gnu-gcc-9
-rwxr-xr-x 1 root root 1158288 Oct 24  2022 /usr/bin/x86_64-linux-gnu-gcc-9

要编译生成能在 risc-v 机器上运行的可执行文件, 需要使用 risc-v 的编译器

1
riscv64-unknown-elf-gcc

运行 riscv helloworld

1
2
3
4
5
6
// hello.c
#include <stdio.h>
int main() {
  printf("hello, world!);
  return 0;
}

关于 stdio 的报错

1
2
3
4
5
$ riscv64-unknown-elf-gcc -march=rv32ima -mabi=ilp32 hello.c -o hello_riscv.out
hello.c:1:10: fatal error: stdio.h: No such file or directory
    1 | #include <stdio.h>
      |          ^~~~~~~~~
compilation terminated.

这个报错在汪辰老师 gitee 仓库中有人提出过, 老师也给了详细的回答 stdio.h 头文件找不到 | gitee issues.

其原因是 riscv64-unknown-elf-gcc 不能编译如 #include <stdio.h> 这样包含 c 库的源码. 如果需要编译带 c 库的代码, 建议安装 gcc-riscv64-linux-gnu 编译器, 这个版本的 riscv64-linux-gnu-gcc 命令可以编译带 c 库的源码, 并生成能够在 riscv 机器上运行的可执行文件. 使用下面的命令来安装 gcc-riscv64-linux-gnu

1
2
apt install gcc-riscv64-linux-gnu
riscv64-linux-gnu-gcc --version

使用 riscv64-linux-gnu-gcc 命令来编译包含 c 库的源码

1
riscv64-linux-gnu-gcc hello.c -o hello_riscv.out

编译报错

使用如下命令编译 hello.c 生成 rv32ima 指令集的可执行文件

1
riscv64-linux-gnu-gcc -march=rv32ima -mabi=ilp32 hello.c -o hello_riscv.out

报错如下

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
$ riscv64-linux-gnu-gcc -march=rv32ima -mabi=ilp32 hello.c -o hello_riscv.out
In file included from /usr/riscv64-linux-gnu/include/sys/cdefs.h:452,
                 from /usr/riscv64-linux-gnu/include/features.h:461,
                 from /usr/riscv64-linux-gnu/include/bits/libc-header-start.h:33,
                 from /usr/riscv64-linux-gnu/include/stdio.h:27,
                 from hello.c:1:
/usr/riscv64-linux-gnu/include/bits/wordsize.h:28:3: error: #error "rv32i-based targets are not supported"
   28 | # error "rv32i-based targets are not supported"
      |   ^~~~~
In file included from /usr/riscv64-linux-gnu/include/gnu/stubs.h:5,
                 from /usr/riscv64-linux-gnu/include/features.h:485,
                 from /usr/riscv64-linux-gnu/include/bits/libc-header-start.h:33,
                 from /usr/riscv64-linux-gnu/include/stdio.h:27,
                 from hello.c:1:
/usr/riscv64-linux-gnu/include/bits/wordsize.h:28:3: error: #error "rv32i-based targets are not supported"
   28 | # error "rv32i-based targets are not supported"
      |   ^~~~~
In file included from /usr/riscv64-linux-gnu/include/bits/types.h:27,
                 from /usr/riscv64-linux-gnu/include/stdio.h:38,
                 from hello.c:1:
/usr/riscv64-linux-gnu/include/bits/wordsize.h:28:3: error: #error "rv32i-based targets are not supported"
   28 | # error "rv32i-based targets are not supported"
      |   ^~~~~
In file included from /usr/riscv64-linux-gnu/include/bits/timesize.h:19,
                 from /usr/riscv64-linux-gnu/include/bits/types.h:28,
                 from /usr/riscv64-linux-gnu/include/stdio.h:38,
                 from hello.c:1:
/usr/riscv64-linux-gnu/include/bits/wordsize.h:28:3: error: #error "rv32i-based targets are not supported"
   28 | # error "rv32i-based targets are not supported"
      |   ^~~~~

执行报错

使用 riscv64-linux-gnu-gcc 的默认参数编译 hello.c 得到 hello_riscv.out

1
riscv64-linux-gnu-gcc [-march=rv64gc] [-mabi=lp64d] hello.c -o hello_riscv.out

riscv64-linux-gnu-gcc 命令的 march 和 mabi 两个参数的默认值为 -march=rv64gc -mabi=lp64d
index-march-14 | gnu onlinedocs
index-mabi-5 | gnu onlinedocs

使用 qemu-riscv64 执行 hello_riscv.out 报错如下

1
2
$ qemu-riscv64 ./hello_riscv.out 
/lib/ld-linux-riscv64-lp64d.so.1: No such file or directory

指定 riscv64-linux-gnu 的路径

1
qemu-riscv64 -L /usr/riscv64-linux-gnu ./hello_riscv.out

/lib/ld-linux-riscv64-lp64d.so.1: No such file or directory

RISC-V GCC工具链介绍

RISC-V GCC工具链介绍

第6章-RTOS 介绍

RTOS, Real Time Operating System

FreeRTOS是一个很流行的应用在嵌入式设备上的实时操作系统内核, 诞生于2003年, 采用MIT许可证发布.

  • 设计小巧, 整个核心代码只有3到4个C文件;
  • 可读性强, 易维护, 大部分的代码都是C语言编写, 很少的部分采用汇编语言;
  • 支持优先级多线程(threads)、互斥锁(mutex)、信号量(semaphore)和软件计时器(software timer), 支持低功耗处理以及一定程度的内存保护;
  • 支持多种平台架构, 包括ARM, x86, RISC-V等, 已经被移植到多款微处理器上.

第7章 (上) - Hello RVOS

ROM & DRAM

ROM (Read Only Memory): 只读存储器, 内容写入后就不能更改了, 制造成本比较低, 常用于电脑中的开机启动, 如启动光盘BIOS. 在系统装好的电脑上时, 计算机将C盘目录下的操作系统文件读取至内存, 然后通过CPU调用各种配件进行工作这时系统存放存储器为RAM。

RAM (Random Access Memory)：随机存取存储器, 也叫主存, 是与CPU直接交换数据的内部存储器, 以随时读写, 而且速度快, 通常作为操作系统或其他正在运行程序的临时数据存储介质. RAM工作时可以随时从任何一个指定地址写入或读出信息. 他与ROM的最大区别是数据的易失性, 断电丢失. RAM在计算机和数字系统中用来暂时存储程序、数据和中间结果. 手机和电脑的运行内存都是使用RAM为存储空间, 内存条的作用是增加运行RAM空间.

  • SRAM (Static RAM): 静态随机存储器, SRAM存放的信息在不停电的情况下能长时间保留, 状态稳定, 不需外加刷新电路, 从而简化了外部电路设计, 常作为Cache;
  • DRAM (Dynamic RAM): 动态随机存储器, DRAM与SRAM相比具有集成度高、功耗低、价格便宜等优点, 所以在大容量存储器中普遍采用. DRAM的缺点是需要刷新逻辑电路, 且刷新操作时不能进行正常读写操作, 常作为主存储器;
  • SDRAM (Synchronous Dynamic RAM): 同步动态随机存取内存, 就是 DDR (Double Data Rate SDRAM), 常见的产品如DDR1、DDR2、DDR3.

CSR 指令

CSRRW指令

CSRRW (Atomic Read/Write CSR) 指令能够将 CSR 寄存器中的值放入 RD 寄存器中, 同时将 RS1 寄存器中的值放入 CSR 寄存器, 并且这个过程是原子性的.

1
2
3
4
; 语法
CSRRW RD, CSR, RS1
; 示例
CSRRW t6, mscratch, t6

上面的示例将 mscratch 寄存器 (一种CSR寄存器) 中的值放入 t6 寄存器中, 同时将 t6 寄存器的值放入 mscratch 寄存器中. 实现了交换 mscratch 和 t6 寄存器值的效果.

CSRRW RD, CSR, RD 指令能够在不需要额外临时寄存器的情况下实现 RD 和 CSR 值的交换, 这是因为该指令内部实现上已经包含了保存和更新操作. CSRRW 指令的功能是原子性地读取 CSR 寄存器的值并同时更新 CSR 寄存器的值, 而这些操作都是在单条指令周期内完成的. 具体步骤如下：

  • 读取 CSR 值: 指令开始时, 从 SCR 寄存器中读取当前值, 并暂时存储在内部 (在硬件层面上);
  • 更新 CSR 值: 将 RD 寄存器的值写入 CSR 寄存器;
  • 更新目标寄存器: 将最初读取的 CSR 值 (暂时存储的值) 写入 RD 寄存器.

因为这些步骤在硬件层面是原子的, 确保了在单个指令周期内完成所有操作, 因此不需要使用额外的临时寄存器. 通过上述原子操作, CSRRW t6, mscratch, t6 指令能够在单条指令内完成值的交换, 不需要额外的临时寄存器来暂存数据. 这也是为什么该指令能够高效地进行寄存器与 CSR 寄存器值的交换.

CSRRS指令

CSRRS (Atomic Read and Set Bits in CSR)

1
2
3
4
# 语法
SCRRS RD, CSR, RS1
# 示例
scrrs x5, mie, x6 # 效果: x5 = mie, mie |= x6

CSRRS 先读出 CSR 寄存器中的值, 将其按 XLEN 位的宽度进行 “零扩展(zero-extend)” 后写入RD; 然后逐个检查 RS1 中的值, 如果某一位为 1 则对 CSR 的对应位置 1, 否则保持不变. 以上两步操作以 “原子性(atomically)” 方式完成。

通常会用一下方式来使用 CSRRS 指令

1
2
3
4
; pseudo instruction
csrr rd, csr
; base instruction
scrrs rd, csr, x0

csrr 是一个伪指令, 底层实现是 csrrs 来实现, 将 csr 中的值零扩展后写入 rd 中.

mhartid 寄存器

mhartid 是一个用于存储 Hart ID 的 CSR 寄存器, 它的名字可以拆开来看 m-hart-id, 其中的 m 表示 machine 模式, hart id 即 hart id.

这个寄存器是只读的 read-only, 其包含了运行当前指令的 hart 的 id. 多个 hart 的 id 必须是唯一的, 并且必须有一个 hart 的 id 值为 0 (第一个 hart 的 id).

引导程序要做哪些事

1
2
3
4
5
6
7
8
9
10
_start:
  # park harts with id != 0
  csrr  t0, mhartid
  mv    tp, t0
  bnez  t0, park
; ... ...
; endless loop
park:
  wfi   ; wait for interrupt instruction
  j park

第7章 (下) - Hello RVOS

UART

UART (Universal Asynchronous Receiver and Transmitter) 通信协议

  • 串行: 相对于并行，串行是按位来进行传递，即一位一位的发送和接收。波特率(baud rate)，每秒传输的二进制位数，单位为bps(bit per second)。
  • 异步: 相对于同步，异步数据传输的过程中，不需要时钟线，直接发送数据，但需要约定通讯协议格式。
  • 全双工: 相对于单工和半双工，全双工指可以同时进行收发两方向的数据传递。

串口收发器 NS16550A 介绍

总结文档: TECHNICAL DATA ON 16550 | byterunner

标准文档: The NS16550A: UART Design and Application Considerations

内存映射

RISCV调试

VSCode调试RISCV程序

How to Remote Debugging with Visual Studio Code

RiscV Debugging With QEMU, GDB, and VSCode | youtube

riscv-helloworld-c | github

VSCode 调试 RISC-V 程序 | 夜云泊

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
// tasks.json
{
  "version": "2.0.0",
  "tasks": [
    {
      "type": "shell",
      "label": "01-helloRVOS-make",
      "options": {
        "cwd": "${workspaceFolder}/01-helloRVOS"
      },
      "command": "make",
      "args": [
        "all",
      ],
    },
    {
      // "> Run Task" -> "01-helloRVOS-qemu"
      // lsof -i tcp:1234 -> kill [pid]
      "type": "shell",
      "label": "01-helloRVOS-qemu",
      "dependsOn": "01-helloRVOS",
      "options": {
        "cwd": "${workspaceFolder}/01-helloRVOS"
      },
      "command": "qemu-system-riscv32",
      "args": [
          "-nographic",
          "-smp", "1",
          "-machine", "virt",
          "-bios", "none",
          "-kernel", "./out/os.elf",
          "-gdb", "tcp::1234",
          "-S"
      ],
    },
    {
      "type": "shell",
      "label": "Kill Qemu Server",
      "command": "ps -ef | grep qemu-riscv64 | grep -v grep | awk '{print $2}' | xargs -i kill -9 {}"
    },

  ]
}

因为启动 qemu 会导致阻塞, 所以 launch.json 中没有加preLaunchTask, 在启动调试之前, 先把 qemu-system-riscv32 server 运行起来.

  • 快捷键 Ctrl/Command+Shift+P, 打开 VSCode Panel;
  • 输入 Run Task 并回车, 再选择对应 label 的 task.

如果提示 Failed to find an available port: Address already in use, 使用 lsof -i tcp:1234 命令 (需要 apt install lsof) 列出占用这个端口的进程, 再使用命令 kill [pid] kill 对应的进程.

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
// launch.json
{
  "version": "0.2.0",
  "configurations": [
    {
      "name": "01-helloRVOS",
      "type": "cppdbg",
      "request": "launch",
      "program": "${workspaceFolder}/01-helloRVOS/out/os.elf",
      // "args": [],
      // "stopAtEntry": false,
      "cwd": "${workspaceFolder}/01-helloRVOS",
      // "environment": [],
      // "externalConsole": false,
      "MIMode": "gdb",
      "miDebuggerPath": "/usr/bin/gdb-multiarch",
      // "setupCommands": [
      //   {
      //     "description": "Enable pretty-printing for gdb",
      //     "text": "-enable-pretty-printing",
      //     "ignoreFailures": true
      //   },
      //   {
      //     "description": "Set Disassembly Flavor to Intel",
      //     "text": "-gdb-set disassembly-flavor intel",
      //     "ignoreFailures": true
      //   }
      // ],
      // "preLaunchTask": "01-helloRVOS-qemu", // <--
      "miDebuggerServerAddress": "localhost:1234",
    },
  ]
}

此时再启动 launch.json 中对应配置的 debug 程序. 注意需要在 launch.json 中指定 miDebuggerPath 以及对应端口号的 miDebuggerServerAddress.

关于如何在 .s/.S 文件中打断点

需要在 VSCode > Preference > Settings 中勾选 Debug: Allow Breakpoints Everywhere

GDB调试RISCV程序

首先编译生成可调式的文件, gcc 加 -g 参数

1
2
3
4
riscv64-unknown-elf-gcc -nostdlib -fno-builtin -g -Wall -march=rv32g -mabi=ilp32 -c -o out/start.o start.S
riscv64-unknown-elf-gcc -nostdlib -fno-builtin -g -Wall -march=rv32g -mabi=ilp32 -c -o out/kernel.o kernel.c
riscv64-unknown-elf-gcc -nostdlib -fno-builtin -g -Wall -march=rv32g -mabi=ilp32 -c -o out/uart.o uart.c
riscv64-unknown-elf-gcc -nostdlib -fno-builtin -g -Wall -march=rv32g -mabi=ilp32 -Ttext=0x80000000 -o out/os.elf out/start.o out/kernel.o out/uart.o

通过 qemu 启动一个 server, 并指定端口 1234

1
2
# Press Ctrl-A and then X to exit QEMU
qemu-system-riscv32 -nographic -smp 1 -machine virt -bios none -kernel out/os.elf -gdb tcp::1234 -S

在另一个终端中通过 gdb-multiarch 命令来启动一个调试程序, 并通过 target remote:1234 来连接 qemu server, 最后通过 gdb 命令进行调试

1
2
3
4
5
6
7
8
9
10
11
gdb-multiarch out/os.elf
...
--Type <RET> for more, q to quit, c to continue without paging--
q # <-- there is a q to quit GNU gdb manual
(gdb) target remote:1234
(gdb) list
(gdb) break 9
(gdb) continue
(gdb) print $t0
(gdb) layout regs # ctrl + x + a to quit windows
(gdb) quit

关于宏的讨论

宏定义函数仅仅在预处理过程中做简单的文本替换, 并不是函数调用, 所以没有压栈和出栈的过程, 在这个过程中寄存器不会发生变化. 所以如果需要对寄存器本身进行一些操作, 使用宏可以做到函数调用无法完成的一些工作.

中断与异常

exception&interrupt

调度

调度级别 描述 操作 发生频率 对进程状态的影响
高级调度(作业调度) 从外存后备队列中选择合适的作业将其调入内存, 并为其创建进程 外存->内存(面向作业) 最低 无->创建态->就绪态
中级调度(内存调度) 从挂起队列中选择合适的进程将其数据调回内存 外存->内存(面向进程) 中等 就绪挂起->就绪态; 阻塞挂起->阻塞态
低级调度(进程调度) 从就绪队列中选择一个进程为其分配处理机 内存->CPU 最高 就绪态->运行态 
graph LR
A("创建态")
B("就绪态")
C("运行态")
D("阻塞态")
E("终止态")

A --> B
B --> C
C --> B
C --> D
D --> B
C --> E

调度算法

  • 先来先服务 (FCFS, First Come First Serve), 非抢占式
  • 短作业优先 (SJF, Shortest Job First), 非抢占式
    短进程优先 (SPF, Shortest Process First), 非抢占式
  • 最短剩余时间优先 (SRTN, Shortest Remaining Time Next), 抢占式
  • 高相应比优先 (HRRN, Highest Response Ratio Next), 抢占式
  • 时间片轮转 (RR, Round-Robin), 抢占式, 分时操作系统, 非饥饿
  • 优先级调度算法, 抢占式/非抢占式, 饥饿
    • 静态优先级
    • 动态优先级
  • 多级反馈队列调度算法, 抢占式, 饥饿
  • 多级队列调度算法

周转时间 = 完成时间 - 到达时间
带权周转时间 = 周转时间 / 服务时间
等待时间 = 周转时间 - 服务时间
响应时间 = 首次响应时间 - 到达时间
响应比 = (已经等待时间 + 要求服务时间) / 要求服务时间

进程互斥与同步

软件实现

  • 单标志法, 违反 “空闲让进” 原则. 并发执行时两个进程时, 如果当前进程让出资源, 例如 Process 0 将 turn 置 1, 但是对方进程已经停止执行, 那么 turn 不能被置回 0, 此时 Process 0 会一直 while 等待

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    int turn = 0;

    // Process 0
    while(turn != 0);  // 进入区
    critical section;  // 临界区
    turn = 1;          // 退出区
    remainder section; // 剩余区

    // Process 1
    while(turn != 1);  // 进入区
    critical section;  // 临界区
    turn = 0;          // 退出区
    remainder section; // 剩余区

  • 双标志先检查法, 先检查后上锁, 违反 “忙则等待” 原则, 并发执行时两个进程可能同时访问临界区

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    bool flag[2];
    flag[0] = false;
    flag[1] = false;

    // Process 0
    while(flag[1]);    // 进入区
    flag[0] = true;
    critical section;  // 临界区
    flag[0] = false;   // 退出区
    remainder section; // 剩余区

    // Process 1
    while(flag[0]);    // 进入区
    flag[1] = true;
    critical section;  // 临界区
    flag[1] = false;   // 退出区
    remainder section; // 剩余区

  • 双标志后检查法, 先上锁后检查, 违反 “空闲让进” 和 “有限等待” 原则. 并发执行时, 可能出现两个进程同时 while 等待的情况.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    bool flag[2];
    flag[0] = false;
    flag[1] = false;

    // Process 0
    flag[0] = true;
    while(flag[1]);    // 进入区
    critical section;  // 临界区
    flag[0] = false;   // 退出区
    remainder section; // 剩余区

    // Process 1
    flag[1] = true;
    while(flag[0]);    // 进入区
    critical section;  // 临界区
    flag[1] = false;   // 退出区
    remainder section; // 剩余区

  • Peterson 算法, 结合了单标识法和双标志检查法, 解决了互斥问题, 遵循了 “空闲让进”, “忙则等待”, “有限等待” 三个原则, 但是未遵循 “让权等待” 原则. Peterson 算法在 while 等待时依然占有着处理器资源.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    bool flag[2];
    int turn = 0;

    // Process 0
    flag[0] = true;
    turn = 1;
    while(flag[1] && turn==1); // <--
    critical section;
    flag[0] = false;
    remainder section;

    // Process 1
    flag[1] = true;
    turn = 0;
    while(flag[0] && turn==0); // <--
    critical section;
    flag[1] = false;
    remainder section;

硬件实现

  • 利用 “开/关中断指令” 的实现
    只适用于单处理机, 不适用于多处理机, 因为关中断指令只对执行该指令的处理机有效. 在单处理机的情况下, 关闭中断会导致 CPU 只执行当前任务, 而不能切换到其它任务, 所以临界区资源由当前进程独享, 在执行完后再打开中断; 而在多处理机的情况下, 即使执行指令关闭当前处理机的中断, 其它处理机的进程依然可以访问临界区资源. 此外开关中断指令是特权指令, 只能在内核态下执行, 不适用于用户下的进程.

  • 利用 TestAndSet/TestAndSetLock 指令
    简称 TS/TSL 指令. TSL 指令底层由硬件实现, 具有原子性. 以下为 TSL 指令执行逻辑的 C 语言描述 (仅为逻辑描述, 非底层实现)

    1
    2
    3
    4
    5
    6
    bool TestAndSet (bool *lock) {
      bool old = true;
      old = *lock;
      *lock = true;
      return old;
    }

    TSL 指令底层先将 lock 中的值读到 old 变量中, 并同时将 lock 置为 true. 如果 lock 本来就为 true (已上锁), 这个赋值没有改变 lock 的状态; 如果 lock 本来为 false (未上锁), 这个赋值会将 lock 加锁. 通过 old 的值可以判断 lock 本来的状态, 如果 old 为 true, 说明 lock 本来已经上锁, 当前进程应该 while 等待; 如果 old 为 false, 锁门 lock 本来没有上锁, 当前进程将跳出 while 循环进入临界区.

    实际上 TSL 底层执行了一个 swap 操作, 它和下面的 Swap 有异曲同工之处.

    TSL 指令的使用

    1
    2
    3
    4
    5
    // lock 为多个进程共享的变量
    while(TestAndSet (&lock)); // 上锁并检查
    ...                        // 临界区
    lock = false;              // 解锁
    ...                        // 剩余区

  • 利用 Swap 指令
    Swap 指令底层是由硬件实现的, 具有原子性.

    1
    2
    3
    4
    5
    6
    7
    8
    // lock 为多个进程共享的变量
    bool old = true;
    while(old == true) {
      Swap(&lock, &old); // 原子交换 lock 和 old
    }
    ...                  // 临界区
    lock = false;        // 解锁
    ...                  // 剩余区

    其中 Swap(old, lock) 是借助硬件实现原子性完成的, 它使用一个 true 去交换 lock 中的值. 如果 lock 本来就等于 true, 表示已经上锁, 那么 lock 的值没有被改变; 如果 lock 本来等于 false, 那么 Swap 操作会立刻将 lock 上锁 (置换为 true). 通过 old 变量可以检查 lock 本来的值是多少, 如果为 true 说明已经上锁, 当前程序应该 while 等待; 如果 old 为 false, 说明没有上锁, 当前程序会跳出 while 循环进入临界区.

互斥锁/自旋锁

互斥锁 (mutex lock) 是解决临界区的最简单方式. 每个互斥锁有一个 bool 型变量 available, 表示锁是否可用, 一个原子方法 acquire() 方法用于获得锁(加锁), 另一个原子方法 release() 方法用于释放锁(解锁).
如果 available=true, 表示当前锁可用, 调用 acquire() 方法会成功, 并且 available 会被置 false; 如果 available=false, 表示当前锁不可用, 调用 acquire() 的进程会阻塞, 陷入 while 等待, 直到占用锁的进程调用 release() 方法将锁释放.

1
2
3
4
5
6
7
8
acquire() {
  while(!available); // 忙等待
  available = false; // 获得锁
}

release() {
  available = true; // 释放锁
}

注意 acquire() 和 release() 方法都是原子操作, 其底层由硬件实现.

需要循环忙等待, 而不是主动让出 CPU 的互斥锁, 都可以称为 自旋锁 (spin lock), 包括 TSL 指令, Swap指令, 单标识法等.

对于多核处理器, 自旋锁的效率可能会更高. 因为进程切换需要切换上下文 (Context), 这个过程会消耗额外的 CPU 资源. 如果一个进程在多核处理器的一个核上自旋等待锁的释放, 它当前只是占用了一个核, 此时处理器的其它核会快速执行占用锁的进程并将锁释放, 那么当前进程有可能在时间片结束之前自旋等到锁的释放并快速执行临界区代码. 这相比于让出处理器资源切换进程再切换回来执行临界区代码的效率会更高.

但是对于单核处理器, 自旋锁的效率会比较低. 因为无论如何当前进程都不可能在当前时间片内自旋等待到锁的释放, 占用锁的进程处于就绪队列中等待 CPU 分配时间片给它.

信号量 (让权等待)

用户进程可以通过使用操作系统提供的一对原语 (wait/signal) 来对信号量进行操作, 从而很方便的实现了进程互斥/进程同步.

信号量其实就是一个变量 (可以是一个整数, 也可以是更复杂的记录型变量). 可以用一个信号量来表示系统中某种资源的数量, 例如系统中只有一台打印机, 就可以设置一个初值为 1 的信号量.

原语 (primitive) 是一种特殊的程序段, 其执行只能一气呵成, 不可被中断. 原语是由 “关中断/开中断” 指令实现的. 进程互斥软件解决方案的主要问题是由 “进入区的各种操作无法一气呵成”, 因此如果能把进入区/退出区的操作都用 “原语” 实现, 使这些操作能 “一气呵成” 就能避免问题.

一对原语: wait(S) 原语和 signal(S) 原语, 可以把原语理解为我们自己写的函数, 函数名分别为 wait 和 signal, 括号里的信号量 S 其实就是函数调用时传入的一个参数.

wait 和 signal 原语常简称为 P、V 操作, 来自荷兰语 Proberen (测试) 和 Verhogen (增加), 因此常把 wait(S)、signal(s) 两个操作分别写为 P(S)、V(S)

整型信号量

整型信号量的 wait 和 signal 原语执行逻辑的 C 语言描述

1
2
3
4
5
6
7
8
9
10
11
12
int S = 1;

// wait 原语执行逻辑的 C 语言描述
void wait (int S) {
  while (S <= 0);
  S = S - 1;
}

// signal 原语执行逻辑的 C 语言描述
void signal (int S) {
  S = S + 1;
}

使用 wait 和 signal

1
2
3
wait(S);   // 进入区
...        // 临界区
signal(S); // 退出区

记录型信号量

记录型信号量的 wait 和 signal 原语的 C 语言逻辑描述

1
2
3
4
5
// 记录型信号量的定义
typedef struct {
  int value;         // 剩余资源数
  struct process *L; // 等待队列, 用于存放进程
} semaphore;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// wait 原语执行逻辑的 C 语言描述
void wait (semaphore S) {
  S.value--;
  if (S.value < 0) { // 注意这里是 < 0 而不是 <= 0
    block(S.L); // block 原语
  }
}

// signal 原语执行逻辑的 C 语言描述
void signal (semaphore S) {
  S.value++;
  if (S.value <= 0) { // 用于是否有进程处于等待队列
    wakeup(S.L); // wakeup 原语
  }
}

其中 block 原语会使进程从运行态进入阻塞态 (自我阻塞), 并将进程放入到信号量 S 的等待队列中; wakeup 原语用于从信号量 S 的等待队列中获得一个进程 (如果有进程处于等待队列), 并将进程从阻塞态变为就绪态.

注意在 wait 原语逻辑描述中使用 S.value < 0 而不是 S.value <= 0 来判断当前是否有资源. 这是因为在 if 判断之前还执行了一次 S.value-- 的操作, 如果 if 判断时 S.value == 0 说明执行 wait 之前的 S.value 值为 1, 即此时还有资源, 所以可以完成执行.
而在 signal 原语的逻辑描述中使用 S.value <= 0 而不是 S.value < 0 来判断是否有进程处于等待队列, 这是因为在执行 if 判断之前还执行了一次 S.value++, 如果执行 if 判断时 S.value == 0, 说明执行 signal 之前 S.value 的值为 -1, 意味着有一个进程处于等待队列.

通常若无特别说明, P(S)/V(S) 操作的 S 默认为记录型信号量

生产者消费者问题

假设内存中有一段固定大小的缓冲区 buffer (例如一个 stack 或者 queue), 多个进程并行/并发向 buffer 中写入数据 (生产者), 多个进程并行/并发从 buffer 中读取数据 (消费者), 数据被读取后就会被删除.
需要注意的是多个进程不能同时向 buffer 中写入数据, 这会导致数据被覆盖, 多个进程也不能同时从 buffer 中读取数据, 这会导致同一块数据被多次读取. 所以对 buffer 的访问需要互斥.

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
semaphore mutex = 1; // 互斥信号量, 实现进程对缓冲区的互斥访问(读/写)
semaphore empty = n; // 同步信号量, 表示缓冲区空闲空间的数量
semaphore full = 0;  // 同步信号量, 表示缓冲区已用空间的数量
                     // empty + full = n = buffer.size()

// 生产者进程
producer () {
  while(1) {
     生产一个产品;
     P(empty); // 消耗一个空闲空间 <--- empty
     P(mutex); // 加锁
     把产品放入缓冲区;
     V(mutex); // 解锁
     V(full);  // 增加一个产品  <--- full++
  }
}

// 消费者进程
consumer () {
  while(1) {
     P(full);  // 消耗一个产品  <--- full
     P(mutex); // 加锁
     从缓冲区取出一个产品;
     V(mutex); // 解锁
     V(empty); // 增加一个空间空间 <--- empty++
     使用产品;
  }
}

注意上面的 empty 与 full 的两对箭头.

  • 在初始时 full = 0, consumer 会在 P(full) 阻塞, 直到 producer 中的 V(full) 将 full++, 此时 consumer 才能继续执行.
  • 当 empty = 0 时, producer 会在 P(empty) 阻塞, 直到 consumer 中的 V(empty) 将 empty++, 此时 producer 才能继续执行.

通过 full 与 empty 这两个同步信号量可以判断 buffer 空 (full=0) 与满 (empty=0), 从而实现 producer 与 consumer 之间的同步.

多类生产者和多类消费者问题

吸烟者问题

读者写者问题

  • 允许多个读者进程同时对文件执行读操作
  • 不允许多个写者进程同时往文件中写数据
  • 任何一个写者进程完成写操作之前不允许其它读者进程和写者进程访问文件
  • 写者进程执行写操作之前, 所有的读者进程和写者进程需要全部退出

写者进程与写者进程为互斥关系, 写者进程与读者进程为互斥关系, 读者进程与读者进程没有互斥关系

哲学家进餐问题

管程 Monitors

管程相当于对互斥操作和同步操作进行了一层封装, 并将使用接口暴露给上层用户, 底层还是通过互斥锁/信号量进行实现的.

死锁-预防死锁

  • 互斥条件
    共享资源同一时刻只能由一个进程访问
  • 不剥夺条件 (不可被抢占)
    进程所获得的资源在未使用完之前, 不能由其它进程强行夺走, 只能主动释放
  • 请求和保持条件
    进程已经保持了至少一个资源, 但又提出了新的资源请求, 而该资源又被其他进程占有, 此时请求进程被阻塞, 但又对自己已有的资源保持不放.
  • 循环等待条件
    存在一种进程资源的循环等待链, 链中的每一个进程已获得的资源同时被下一个进程所请求.

避免死锁-银行家算法-安全序列

内存管理

连续分配管理方式

  • 单一连续分配, 无外部碎片, 有内部碎片

  • 固定分区分配, 分区说明表, 无外部碎片, 有内部碎片
    将整个用户空间划分为若干个固定大小的分区, 在每个分区中只装入一道作业

  • 动态分区分配, 空闲分区表/空闲分区链, 动态分区分配算法
    动态分区分配又称为可变分区分配. 这种分配方式不会预先划分内存分区, 而是在进程装入内存时根据进程的大小动态地建立分区, 并使分区的大小正好适合进程的需要.

内部碎片: 分配给某进程的内存区域中, 如果有些部分没有用上.
外部碎片: 是指内存中的某些空闲分区由于太小而难以利用.

动态分区分配算法

  • 首次适应算法
    每次都从低地址开始查找, 找到第一个能满足大小的空闲分区

  • 最佳适应算法
    由于动态分区分配是一种连续分配方式, 为各进程分配的空间必须是连续的一整片区域. 因此为了保证当 “大进程” 到来时能有连续的大片空间, 可以尽可能多地留下大片的空闲区即, 优先使用更小的空闲区.

  • 最坏适应算法
    算法思想:为了解决最佳适应算法的问题–即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。如何实现:空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。

  • 邻近适应算法

基本分页存储管理

将内存空间分为一个个大小相等的分区 (比如每个分区 4 KB), 每个分区就是一个 “页框” (页框=页帧=内存块=物理块=物理页面). 每个页框有一个编号, 即 “页框号” (页框号=页帧号=内存块号=物理块号=物理页号), 页框号从 0 开始.

页表 --> 页框 (Page Frame)

页表在内存中连续存储

1
2
3
4
5
6
# 页表 (存放的是内存块号)
  0   1   2   ...   n
| 3 | 6 | 4 | ... | 8 |

# 内存分页, 内存块号/页框号
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ...

页号 = 逻辑地址/页面大小;
页内偏移量 = 逻辑地址 % 页面大小

地址转换
计算逻辑地址对应的【页号】和【页内偏移量】
从页表中查取【页号】对应的内存块号（页框号）

物理地址 = 页面起始地址 + 页内偏移量

如果使用 2^n 大小来对内存进行分页, 会有额外的优化. 例如一个拥有 32 位宽寄存器的 CPU, 它的内存查找范围为 0 ~ 2^32 Byte (2^32 B = 2^2 × 2^30 B = 4 GB). 分页大小设为 4KB = 2^12B = 4096B. 那么

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 0 号页的逻辑地址范围是 0~4095, 用二进制表示为
[00000000 00000000 0000][0000 00000000] ~
[00000000 00000000 0000][1111 11111111]
\_________页号_________/\__页内偏移量__/

# 1 号页的逻辑地址范围是 4096~8191, 用二进制表示为
[00000000 00000000 0001][0000 00000000] ~
[00000000 00000000 0001][1111 11111111]
\_________页号_________/\__页内偏移量__/

# 2 号页的逻辑地址范围是 8192~12287, 用二进制表示为
[00000000 00000000 0010][0000 00000000] ~
[00000000 00000000 0010][1111 11111111]
\_________页号_________/\__页内偏移量__/

内存块的物理地址也同样如此

1
2
3
4
5
6
7
8
9
10
11
# 0 号内存块的起始地址为
[00000000 00000000 0000][0000 00000000]
\_________块号_________/

# 1 号内存块的起始地址为
[00000000 00000000 0001][0000 00000000]
\_________块号_________/

# 2 号内存块的起始地址为
[00000000 00000000 0010][0000 00000000]
\_________块号_________/

所以如果一个逻辑地址需要查找对应的物理地址, 例如逻辑地址 4097

1
2
3
# 逻辑地址 4097 的二进制表示
[00000000 00000000 0001][0000 00000001]
\_______ 逻辑页号 1 ____/\__页内偏移量__/

可以直接获取其对应的页号 (前20位) 和页内偏移量 (后12位), 通过查页表可以获得 1 号页对应的内存块号, 假设为 9, 通过二进制位操作可以获得 9 号内存块的起始地址

1
2
3
# 9 号内存块的起始地址为
[00000000 00000000 1001][0000 00000000]
\__________ 9 _________/

将逻辑地址的后 12 位 (页内偏移量) 与内存块起始地址的前 20 位进行 “拼接”, 即可获得 32 位的物理地址

1
2
3
# 逻辑地址 4097 的对应的物理地址
[00000000 00000000 1001][0000 00000001]
\_____ 内存块号 9 ______/\__页内偏移量__/

这其中所需要做的工作就是将逻辑地址的前 20 位 (逻辑页号) 替换为页表对应的内存块号即可

1
2
3
4
5
[00000000 00000000 0001][0000 00000001] # 逻辑地址
\______ 逻辑页号 1 _____/\__页内偏移量__/
           | # <-- 查表
/—————— 内存块号 9 —————\/——页内偏移量——\
[00000000 00000000 1001][0000 00000001] # 物理地址

通常会在系统中设置一个页表寄存器(PTR), 存放页表在内存中的起始地址F和页表长度M. 进程未执行时, 页表的始址和页表长度放在进程控制块(PCB)中, 当进程被调度时, 操作系统内核会把它们放到页表寄行器中.

注意区分 “页表项长度”, “页表长度”, “页面大小” 的区别

具有快表的地址变换机构

快表, 又称 联想寄存器 (TLB, Translation Lookaside Buffer), 是一种访问速度比内存快很多的高速缓存 (!!!TLB不是内存!!!), 用来存放最近访问的页表项的副本, 可以加速地址变换的速度. 与此对应, 内存中的页表常称为慢表.

TLB 与普通 Cache 的区别: TLB 中只有页表项的副本, 而普通 Cache 中可能会有其他各种数据的副本.

1
2
Register -> Cache|TLB -> RAM -> Disk
\____CPU内部____/

引入快表后, 地址的变换过程

  • CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。
  • 如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此若快表命中，则访问某个逻辑地址仅需一次访存即可。
  • 如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此若快表未命中，则访问某个逻辑地址需要两次访存 (注意:在找到页表项后，应同时将其存入快表，以便后面可能的再次访问。但若快表已满，则必须按照一定的算法对旧的页表项进行替换)

由于查询快表的速度比查询页表的速度快很多，因此只要快表命中，就可以节省很多时间。因为局部性原理，一般来说快表的命中率可以达到 90%以上.

局部性原理

两级页表, 缺页异常

某计算机系统按字节寻址, 支持32位的逻辑地址, 采用分页存储管理, 页面大小为4KB, 页表项长度为 4B=2^32bits.
页面(内存块)大小 4KB=2^12B, 因此页内地址要用 12 位表示. 剩余 32-12=20 位表示页号. 因此, 该系统中用户进程最多有 2^20 页 (数据块). 相应的, 一个进程的页表中, 最多会有 2^20=1M=1048,576 个页表项. 所以一个页表最大需要占用 2^20*4B=2^22B (4MB) 大小的连续内存空间, 共需要 2^22 / 2^12 = 2^10 个页框存储该页表.
根据页号查询页表的方法: K 号页对应的页表项存放位置 = 页表始址 + K*4, 要在所有的页表项都连续存放的基础上才能用这种方法找到页表项

可将长的页表进行分组, 使每个内存块刚好可以放入一个分组. 比如页面大小 4KB, 每个页表项 4B (32 位), 每个页面可存放 1K=1024 个页表项. 因此每 1K 个连续的页表项为一组, 每组刚好占一个内存块 (页面), 再将各页表组离散地放到各个内存块中.

32 位逻辑地址, 页表项大小为 4B, 页面大小位 4KB, 页面大小位 4KB = 2^12B, 则页内地址需要 12 位寻址.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 物理内存块(页面)编号, 一个内存块(页面)大小为 4K
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ...

# 单级页表
# 32 位宽的寻址寄存器, 其后 12 位用于页内寻址, 范围为 0~4K (页面大小为 4KB=2^12B)
# 前 20 位用于记录页号, 范围为 0~1M, 这样一个单级页表最多只能记录 1M 个页表项
  0   1   ...   1023  1k   ...   1M-1
| 2 | 4 | ... | 543 | ?? | ... | ???? |

# 页表分组
# 一个页面大小 4KB, 一个页表项大小 4B, 一个页面刚好放下 4KB/4B=1K=1024 个页表项
# 一组 1k 个页表项, 1M 个页表项可以分为 1k 组
   0   1   ...   1023      0   1   ...   1023           0   1   ...   1023
[| 2 | 4 | ... | 543 |] [| ? | ? | ... | ???? |] ... [| ? | ? | ... | ???? |]
 \_______ (0) _______/   \_______ (1) ________/  ...  \______ (1023) ______/

# 页目录表/顶级页表/外层页表, 存放 二级页号:内存块号
# 注意页目录表中存放的是储存对应二级页表的内存块号
  0   1   2   ...   1023
| 3 | 7 | 4 | ... | ???? |

逻辑地址到物理地址的寻址过程

1
2
3
4
5
6
7
[00000000 00][000000 0001][0000 00000001] # 逻辑地址
\__一级页号__/\__二级页号__/\__页内偏移量_/
\_________________________/
           | # 一级页号 --(页目录表)--> 二级页表内存块号(基地址) --> 二级页表
           | # 二级页号 --(二级页表)--> 内存块号(基地址)
/——————— 内存块号 9 ——————\/——页内偏移量——\
[00000000 00  000000 1001][0000 00000001] # 物理地址

基本分段存储管理方式

段页式管理方式

虚拟内存

虚拟内存的实现

  • 请求分页存储管理 / 请求分段存储管理 / 请求段页式存储管理
  • 请求掉页(或请求掉段)功能
    程序执行过程中, 当所访问的信息不在内存中时, 由操作系统负责将所需信息从外存调入内存, 然后继续执行
  • 请求页面置换(或段置换)功能
    若内存空间不够, 由操作系统负责将内存中暂时用不到的信息换出到外存

请求分页存储管理方法

  • 页表机制
    与基本分页管理相比，请求分页管理中，为了实现“请求调页”，操作系统需要知道每个页面是否已经调入内存;如果还没调入，那么也需要知道该页面在外存中存放的位置。

  • 页面置换

  • 缺页中断机构 (准确说是缺页异常)

在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。
此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。

  • 如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项。
  • 如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存。

页面置换算法

  • 最佳置换算法 (OPT, Optimal)
    理论中性能最好, 但是现实中无法实现
  • 先进先出置换算法 (FIFO, First In First Out)
    实现简单但性能很差
  • 最近最久未使用置换算法 (LRU, Least Recently Used)
    性能很好, 但需要硬件支持, 算法开销很大
  • 时钟置换算法 (CLOCK) 又称 最近未用算法 (NRU, Not Recently Used)
  • 改进型的时钟置换算法

页面分配/置换策略

驻留集: 指请求分页存储管理中给进程分配的物理块的集合。在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。
若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际用于进程推进的时间很少;
驻留集太大，又会导致多道程序并发度下降，资源利用率降低。所以应该选择一个合适的驻留集大小。

  • 驻留集大小是否可变: 固定分配/可变分配
  • 页面置换的范围: 局部置换/全局置换

对换区(连续分配)/文件区(离散分配)

工作集 vs 驻留集

内存映射文件

文件管理

文件的逻辑结构

无结构文件 / 有结构文件

有结构文件的逻辑结构

  • 顺序文件

    • 链式存储
      无论是定长还是可变长记录, 都无法实现随机存取, 每次只能从第一个记录开始依次往后查找
    • 顺序存储
      • 可变长记录: 无法实现随机存取, 每次只能从第一个记录开始依次往后查找
      • 定长记录: 可实现随机存取. 如果记录的长度为 L, 则第 i 个记录的 offset 为 i*L
        • 采用串结构(不按照关键字排序): 无法快速查找
        • 采用顺序结构(按照关键词排序): 可以快速查找某关键词对应的记录, 例如折半查找

  • 索引文件

  • 索引顺序文件

  • 多级索引顺序文件

文件目录

文件控制块 (FCB, File Control Block). FCB 是操作系统中用于管理文件的数据结构。每个打开的文件在内存中都有对应的 FCB，用于跟踪和管理该文件的信息。FCB 包含了文件的元数据，如文件名、文件大小、创建时间、修改时间等，以及指向该文件在 FAT 表格中对应项的指针。

目录本身就是一种有结构文件，由一条条记录组成, 每条记录对应一个在该目录下的文件。目录文件中的一条记录就是一个文件控制块 (FCB)。FCB 实现了文件名和文件之间的映射。使用户程序可以实现 “按名存取”。

目录结构

  • 单级目录结构
  • 两级目录结构: 分为主文件目录(MFD, Master File Directory) 和用户文件目录(UFD, User File Directory)
  • 多级目录结构: 根目录->绝对路径, 当前目录->相对路径. 树形目录结构不便于实现文件的共享
  • 无环图目录结构: 共享计数器

索引结点

文件的物理结构

逻辑块号 -> 物理块号

文件分配方式 (操作系统层面)

  • 连续分配
  • 隐式链接
  • 显示链接 (静态链表), 文件分配表 (FAT, File Allocation Table)
  • 索引分配
    • 链接方案
    • 多层索引
      假设磁盘块大小为 1KB, 一个索引表项占 4B, 则一个磁盘块只能存放 1KB/4B = 256 个索引项. 若某文件采用两层索引, 则该文件的最大长度为 256×256×1KB=64MB, 访问一个数据块需要 3 次都磁盘操作; 若采用三层缩影, 则该文件的最大长度为 256×256×256×1KB=16GB, 访问一个数据块需要 4 次读磁盘操作.
    • 混合索引

文件的逻辑结构 vs 物理结构

逻辑结构:

  • 无结构文件 (流式文件)
  • 有结构

    • 顺序文件

      • 顺序存储
      • 链式存储

    • 索引文件

      1
      2
      3
      4
      5
      6
      7
      8
      9
      typedef struct {
        int number; // 学号
        int addr;   // 学生记录的逻辑地址
      } IndexTable;

      typedef struct {
        char name[30];  // 姓名
        char major[30]; // 专业
      } Student_info;

      indexed-file

    • 索引顺序文件

物理结构:

  • 连续分配
consecutive-allocation
  • 链接分配 (隐式/显示)
lincked-allocation
  • 索引分配
indexed-allocation

文件存储空间管理

目录区: FCB / 文件区: 文件数据

空闲表法 / 空闲链表法 / 位视图法 / 成组链接法 (Unix)

文件的基本操作

系统的打开文件表的索引号 – 文件描述符

文件共享

基于索引结点的共享方式 (硬链接), 注意指针悬空
基于符号链的共享方式 (软链接), 快捷方式是软连接

文件保护

访问控制列表 (ACL, Access Control List)

文件系统的全局结构

虚拟文件系统

POSIX标准接口

虚拟文件系统

UFS 文件系统 / NTFS 文件系统 / FAT 文件系统

内存页|磁盘块

CPU-Cache-Memory-Disk

浅谈Cache Memory
从文件read/write一个字节的过程和所发生的磁盘IO
我把 CPU 三级缓存的秘密，藏在这 8 张图里

字节 (Byte): 字节是计算机数据存储的基本单位, 即使存储 1 个位也需要按 1 个字节存储;

计算机位数(机器字长)=字长=寄存器或运算器位数=CPU位数

  • 计算机位数/机器字长: 计算机一次能处理的二进制数长度, 即 “机器字长”.
  • 字长: 通常指 CPU 内部用于整数运算的数据通路的宽度, 因此字长等于 CPU 内部用于整数运算的运算器位数和通用寄存器宽度, 它反映了计算机处理信息的能力.
  • 寄存器或运算器位数: 寄存器所能存二进制数位数.
  • CPU位数: 一个时钟周期内处理器同时寄存和处理的二进制位数, 这和 CPU 中寄存器的位数对应.

缓存块(Block) / 缓存行(Cache Line): 块是 CPU Cache 管理数据的基本单位, 也叫 CPU 缓存行;
段 (Segmentation)/ 页(Page): 段 / 页是操作系统管理虚拟内存的基本单位.

机械磁盘和固态磁盘分别有一个最小的读写单位:

  • 机械磁盘的最小读写单位是扇区 (sector)，一般大小为 512 字节,
  • 固态磁盘的最小读写单位是页 (page)，通常大小是 4KB、8KB 等.

如果每次都读写 512 字节这么小的单位的话，效率很低。所以，Linux文件系统会把连续的扇区或页组成逻辑块 (block)，然后以逻辑块作为最小单元来管理数据。常见的逻辑块的大小是 4KB，也就是说连续 8 个扇区，或者单独的一个页，都可以组成一个逻辑块。

1
2
【CPU】<-- word -->【L1/L2/L3 Cache】<-- cache line (64B) -->【Main Memory】
【Main Memory】<-- page/block -->【Buffer】<-- page/block (4KB) -->【Disk】

页框/页帧/内存块大小=外存块大小 (通常设为4KB)

对于基于 Cache 的系统，CPU 在访问内存数据的时候，对数据的读取和写入总会先访问 Cache，检查要访问的数据是否在 Cache 中。如果命中则直接使用 Cache 上的数据，否则先将底层的数据源加载到 Cache 中，再从 Cache 读取数据。

IO

IO控制方式

  • 程序直接控制方式
  • 中断驱动方式
  • DMA方法
  • 通道控制方式