rcore-os Blog
0%

2024秋冬季开源操作系统训练营第二阶段总结报告_firecrack

Posted on Edited on In

专业阶段总结

四个抽象

  • 执行环境
  • 进程
  • 地址空间
  • 文件

    五个特征

  • 虚拟化
    • 内存地址虚拟化
    • 内存大小虚拟化：通过引入硬盘空间、
    • CPU虚拟化：通过分时以及快速切换
  • 并发
  • 异步
  • 共享
  • 持久

程序编译流程

  • 预处理：宏展开
  • 编译器： ——> 汇编语言
  • 汇编器：——> 目标代码
  • 链接器：——> 可执行文件

不使用标准库

#![no_std]添加在文件开头

禁用默认的main

#![no_main]

qemu启动流程

1
2
3
4
5
qemu-system-riscv64 \
    -machine virt \
    -nographic \
    -bios ../bootloader/rustsbi-qemu.bin \
    -device loader,file=target/riscv64gc-unknown-none-elf/release/os.bin,addr=0x80200000
  • virt 硬件平台上，物理内存的起始物理地址为 0x80000000 ，物理内存的默认大小为 128MiB，所以物理地址空间为[0x80000000,0x88000000)
  • 启动时先将sbi文件加载到0x8000 0000, 将os.bin 加载到0x8020 0000

计算机启动的三个阶段：

  1. CPU固有的一些程序，对应于QEMU就是其自带的一段程序，该程序第一条指令在0x1000处，最后一条指令就是跳转到0x8000 0000 执行bootloader
  2. bootloader 负责一些计算初始化工作后，再跳转到第三程序，对于RUSTSBI第三阶段程序的入口地址固定为0x8020 0000，实际的应用中bootloader会负责将操作系统程序从硬盘加载到该地址
  3. 执行os的代码

GDB调试

查看内存

x/nfu addr

  • n：表示要显示的内存单元的数量。
  • f：格式，可以是 b（byte）、h（halfword，2字节）、w（word，4字节）、g（giant，8字节）等。
  • u：显示的格式，可以是 x（十六进制）、d（十进制）、o（八进制）、t（二进制）等。
  • addr：内存地址。

    打印寄存器

    p/x $xx

特权级切换

S模式下的控制状态寄存器（CSR）

  • sstatus:SPP 等字段给出 Trap 发生之前 CPU 处在哪个特权级（S/U）等信息
  • sepc：当 Trap 是一个异常的时候，记录 Trap 发生之前执行的最后一条指令的地址
  • scause: Trap的原因
  • stval: Trap的附加信息 (例如缺页异常时的虚拟地址)
  • stvec: Trap处理程序的入口地址

硬件

当执行ecall时，硬件的工作：

  • sstatus 的 SPP 字段会被修改为 CPU 当前的特权级（U/S）。
  • sepc ecall的地址记录在sepc寄存器中
  • scause/stval 分别会被修改成这次 Trap 的原因以及相关的附加信息。
  • CPU 会跳转到 stvec 所设置的 Trap 处理入口地址，并将当前特权级设置为 S ，然后从Trap 处理入口地址处开始执行。

sret

  • CPU 会将当前的特权级按照 sstatus 的 SPP 字段设置为 U 或者 S ；
  • CPU 会跳转到 sepc 寄存器指向的那条指令，然后继续执行。

    软件（操作系统）

    在内存中存在两个全局变量，分别表示用户栈和内核栈，位于操作系统程序的.bss段
    从用户栈切换到内核栈，只需要将寄存器sp值进行更改即可

虚拟内存

当程序所需空间大于物理内存时怎么办。在没有虚拟内存前一种方法是，程序员对程序手工分段，依次将每段程序装入内存中运行。
虚拟存储器与此类似，只是由操作系统每次将正在使用的一部分放入内存，其余存在硬盘上。

  • 虚拟存储器大小由处理器位数决定，对32位处理器来说地址范围为$0 \sim FFFF\quad FFFF$，其中某一地址就叫做虚拟地址（VA）
  • 没有使用虚拟地址的系统，其处理器输出的地址直接就是物理地址（PA），而如果使用了虚拟地址，则处理器输出的就是虚拟地址了，其需要通过内存管理单元（MMU）转换成物理地址
  • 优点：使用虚拟地址的一大优点，对于需要同时运行多个程序的系统来说，每个系统都可以随意使用地址空间，不需要考虑地址的限制。以及保护（同一虚拟地址可以转换为不同物理地址）和共享（不同虚拟地址可以转换为统一物理地址）

    地址转换

    目前虚拟存储器通常使用请求分页（demand page）的方式实现，将虚拟内存按页划分，典型的是4KB，物理地址空间按同样大小划分，称为frame。
    对4KB大小的页，页内索引需要12位，即VA[11:0]，称为page offset，剩余部分可以看做是页编号VPN（virtual page number）。相应的PA[11:0]是frame offset，剩余部分PA[:11]是PFN(physical frame number)。从虚拟地址到物理地址的转换时间上就是VPN到PFN的转换。

    单级页表

    当要访问的page，没有与物理内存中的某个frame形成映射关系时，即需要的内容不在物理内存中，此时发生缺页异常（page fault），需要将内容从硬盘加载到内存中。
    操作系统如何知道page和frame的对应关系？目前普遍使用表格存储VPN到PFN的映射，称为页表（page table，PT），一般存放在物理内存中。
  • 每个程序都有一个张页表，页表在物理内存中的首地址存放在页表寄存器中
  • 页表与cache不同，其包含了所有VPN的映射关系
  • 操作系统会在不同进程之间进行切换，在当前进程被替换掉之前，需要保存其状态，对于页表来说只需要保存页表寄存器就好
  • 页表存在于物理内存中，因此一次取数据需要访问两次内存，第一次是访问页表完成VPN到PFN的转换，第二次是用物理地址来访问内存

一张页表存储了所有VPN的映射因此，对32位处理器，其虚拟空间为4GB，假设页大小为4KB，则VPN编号为VA[31:12]共20位，则一个页表有$2^{20}$项，假设每项占32位，则页表大小为4MB。而对64位处理器，一张页表达到了PB大小，这已经超出了物理内存的大小。而且大多数程序也不会用光虚拟空间，只会使用一小部分，页表项大多都是空的。解决方法就是多级页表

多级页表

通过引入多级页表，页表也无需占用一块连续空间。页表中的一项称为PTE（page table entry）
多级页表的引入，使得访问数据需要的访存次数增加

缺页异常

缺页异常通过是由软件来处理

  • 这是因为发生缺页是需要将数据从磁盘搬运到内存，读磁盘所需时间对异常处理程序来说绰绰有余。
  • 处理过程中可能需要进行页替换，使用软件来处理更加灵活，可以按需选择合适的替换策略

发生缺页异常时，如何知道虚拟地址中的一个页在硬盘哪个位置？

  • 操作系统会为每个进程的所有页在硬盘中开辟一块空间（swap空间），同时建立一张表保存每个页在硬盘中的位置
    缺页处理可能会发生页替换，为了保证一致性，对页表项添加一个脏位，此外为了实现LRU替换策略，添加一个使用位，当使用位为1说明该页最近访问过，操作系统会周期性将使用位置0.
    缺页异常的硬件支持：
  • 缺页发生时，硬件会产生相应的异常，并跳转值异常处理程序
  • 脏位
  • 使用位

除此之外还可以通过在PTE中添加AP来实现访问控制，添加cacheable来表示是否允许被缓存

引入TLB和cache

TLB

多级页表节省了页表的存储空间，但是也增加了防存次数。因此引入缓存思想，对最近访问过的PTE（页表项）进行缓存，这个缓存被称为TLB，其本质就是页表的cache。不过其只有时间相关性。
现代处理器通常采用二级TLB，第一级是哈佛结构即分为指令TLB和数据TLB，一般全相连，容量不大，第二级则是组相连模式。

TLB缺失

TLB是页表的一个子集

  1. 虚拟地址对应的页不在物理内存中，此时页表中对应的PTE是空的，所以TLB中也一定不会有相关信息
  2. 虚拟地址对应的页已经在物理内存中，则页表中对应PTE是有效的，但可能该PTE不在TLB中。

要解决TLB缺失，本质是从页表中找到相应PTE，将其写入TLB中，这个过程叫Page Table Walk。该过程可以用硬件实现，也可以用软件实现。

  1. 软件实现：发生缺失时，硬件将产生缺失的虚拟地址保存到一个特定寄存器中，同时产生一个TLB miss 异常，然后执行异常处理程序，这个过程中可能还会出现缺页异常。软件的优点就是灵活，可以调整TLB写入换出的算法。软件实现中，当发生TLB miss时，流水线中的指令需要清空用于执行异常处理程序，有一个流水线清空和恢复的操作，流水线越深，清空的指令越多。
  2. 硬件实现：一般由内存管理单元MMU实现。好处就是不需要清空恢复流水线

一种LRU近似算法：假设TLB使用全相连，使用一个计数器每周期加一，计数器宽度为TLB表项数目，当TLB表中的项目需要被替换时，就以此时计数器中的数作为要被换出的表项编号。

TLB的写入

TLB与页表的一致性。
在对物理内存进行页替换时，需要检查被替换页PTE的脏位，如果是1，需要将被替换页内存写回硬盘，如果是0可以直接替换。
而引入了TLB后，就产生了TLB中表项与PTE的一致性问题。load和store命令都会先去查看TLB，如果存在对应的项，则会将use bit置1，此外store指令会将脏位变为1，这时TLB与页表就产生了不一致。如果使用写回策略，那么知道该TLB表项被替换才会更新页表，在此之间如果系统发生了页替换，系统可能以为该内存页没有更新而直接覆盖。

解决方法：页替换发生在page fault时，在进行页替换前，先将TLB写回页表，然后再执行替换

进程调度

批处理系统的调度

特点：计算为主，少量I/O

约束条件

  1. 每个进程同时到达。
  2. 进程的执行时间是已知的。
  3. 进程在整个执行过程期间很少执行I/O操作。
  4. 进程在执行过程中不会被抢占。

性能指标

周转时间（turn around），即进程完成时间（completion）与进程到达时间（arrival）的差值：
$T_{turn} = T_{complete} - T_{arrive}$
平均周转：
$T_{avg} = \frac{1}{n}\sum T_{turn}$

先来先服务FIFO

通常使用队列来实现：

  • 就绪队列
  • 阻塞队列

优点：

  • 实现简单
  • 公平

缺点：

  • 如果长任务先到，那么短任务会被迫等待很长时间，使得平均周转时间变长

最短作业优先SJF

在约束条件下，如果把平均周转时间作为唯一的性能指标，那么SJF是一个最优调度算法。

交互式系统的调度

约束条件

  1. 每个进程可不同时间到达。
  2. 每个进程的执行时间不同。
  3. 进程的执行时间是已知的。
  4. 进程在整个执行过程期间会执行I/O操作。
  5. 进程在执行过程中会被抢占。

性能指标

目标是提高用户的交互性体验和减少I/O响应时间
响应时间（response time），即从程序到达到第一次被执行的时间

最短完成时间优先（STCF）

  • 在支持抢占式的系统上，可以改善周转时间
  • 但对于响应时间，FIFO/SJF/STCF都没用特别好的效果

    基于时间片的轮转

  • 每个任务轮流占用CPU一段时间
  • 时间片越短，任务得到响应越快，但存在进行切换开销
  • 任务越多，轮到下一次执行的时间越长，系统平均周转时间也会变长

通用计算机系统的调度

约束条件

  1. 每个进程可不同时间到达。
  2. 每个进程的执行时间不同。
  3. 进程的启动时间和执行时间是未知的。
  4. 进程在整个执行过程期间会执行I/O操作。
  5. 进程在执行过程中会被抢占。

    固定优先级的多级无反馈队列Multi-level Feedback Queue

    一般CPU密集型优先级低，I/O密集型优先级高
  6. 如果进程PA的优先级 > PB的优先级，抢占并运行PA。
  7. 如果进程PA的优先级 = PB的优先级，轮转运行PA和PB。

难点：

  • 无法预估程序的类型
  • I/O密集程度多样

    可降低优先级的多级反馈队列

  • 动态调整进程的优先级
  • 操作系统首先需要以优先级的数量来建立多个队列。当然这个数量是一个经验值，比如Linux操作系统设置了140个优先级。
  • 优先级的变化是单向的，一个进程的优先级只会持平/降低
  • 低优先级可能会一直无法拿到CPU，产生饥饿现象

如何提升优先级

  • 定期统计进程在就绪态/阻塞态的等待时间，等待时间越长，其优先级的提升度就越高