lab 1

Hello OS

环境配置

install nasm sdl12-compat
yay -S bochs-sdl

开机，从 ROM 运行 BIOS 程序，BIOS 程序检查软盘 0 面 0 磁道 1 扇区，如果扇区以 0xaa55 结束，则认定为引导扇区，将其 512 字节的数据加载到内存的 07c00 处，然后设置 PC，跳到内存 07c00 处开始执行代码

汇编代码

    org 07c00h
    mov ax, cs
    mov ds, ax
    mov es, ax
    call    DispStr
    jmp $
DispStr:
    mov ax, BootMessage
    mov bp, ax
    mov cx, 16
    mov ax, 01301h
    mov bx, 000ch
    mov dl, 0
    int 10h
    ret
BootMessage:       db  "Hello OS"
times    510-($-$$)  db  0
dw 0xaa55

一些解释

org 07c00h 让编译器从相对地址 07c00h 处开始编译第一条指令，考虑 BootMessage 代表的字符串地址，是相对寻址

编译

nasm boot.asm -o boot.bin

反编译

ndisasm -o 0x7c00 boot.bin | less

创建软盘

bximage -func=create -fd=1.44M -q a.img

将 boot.bin 写入软盘

dd if=boot.bin of=a.img bs=512 count=1 conv=notrunc

启动虚拟机

bochs -f bochsrc -q

配置文件如下

megs: 32
display_library: sdl
floppya: 1_44=a.img, status=inserted
boot: floppy

截图

calculator

环境配置

yay -S lib32-gcc-libs

汇编和编译

nasm -f elf32 main.asm
gcc -m32 -no-pie -o main.bin main.o

截图

下面简单讲讲具体的实现

加法

逆向存储各数位，不考虑数的位数，直接加固定位数，高位仍然为 0

乘法

化归为加法，以 123 * 123 为例

逆向存储为 321

3 2 1
3 2 1

考虑第一位，321 + 321 + 321 = 963，存储在 mul_cp_dst_buf 中，加到 mul_res_buf 中

考虑第二位，将 321 移位为 0321，0321 + 0321 = 0642，存储在 mul_cp_dst_buf 中，加到 mul_res_buf 中

考虑第三位，将 321 移位为 00321，00321 = 00321，存储在 mul_cp_dst_buf 中，加到 mul_res_buf 中

此时 mul_res_buf 为 963 + 0642 + 00321 = 92151，逆向输出即为 15129

lab 2

RTFM

http://jyywiki.cn/pages/OS/manuals/MSFAT-spec.pdf

下面给出各 region 的大小

Reserved Region - BPB_RsvdSecCnt
FAT Region - BPB_NumFATs * BPB_FATSz16
Root Directory Region - 利用 BPB_RootEntCnt 字段
Data Region - 下标从 2 开始计数

下述方法给出了如下将 data region 的 cluster 转换为 sector

void *cluster_to_sec(int n) {
    static u32 RootDirSector = hdr->BPB_RsvdSecCnt + hdr->BPB_NumFATs * hdr->BPB_FATSz16;
    static u32 RootDirSectorNum = ((hdr->BPB_RootEntCnt * 32) + (hdr->BPB_BytsPerSec - 1)) / hdr->BPB_BytsPerSec;
    u32 FirstDataSector = RootDirSector + RootDirSectorNum;
    FirstDataSector += (n - 2) * hdr->BPB_SecPerClus;
    return ((char *) hdr) + FirstDataSector * hdr->BPB_BytsPerSec;
}

data region 中可能包含文件的数据信息，也可能包含一系列的 entries，包括 short entry 和 long entry

这里只需关注 short entry，且只需关注 short entry 中的 ATTR_DIRECTORY (目录元信息) 和 ATTR_ARCHIVE (文件元信息)

DIR_Name[0] = 0xE5 indicates the directory entry is free (available)

short entry 的 DIR_FstClusLO 给出了文件或者目录所在数据的 cluster id，该 cluster id 也用于在 fat region 中寻找下一个 cluster id

例如，某 short entry 描述了某个普通文件的元数据信息，其 cluster id 为 5，而 fat[5] = 6, fat[6] = 0xfff

这说明该普通文件的数据分布在 data region 的 cluster #5 和 cluster #6 中

另外，对应 FAT 12 而言，fat 的一个 entry 占据 12 个比特，所以需要通过一些特殊的方法来进行读取

technology selection

输出

g++ 和 nasm 联合编译

nasm -f elf64 print.asm
g++ -std=c++17 main.cpp print.o -o main.bin -lreadline

nasm 仅负责填充 syscall id 并进行 write 这个系统调用，对于 x86-64 而言，系统调用指令为 syscall 而非 int 80

extern "C" {
ssize_t write_syscall(int fildes, const char *input_buf, size_t nbyte);
};

ssize_t write_str(const char *input_buf) {
    return write_syscall(0, input_buf, strlen(input_buf));
//    return write(0, input_buf, strlen(input_buf));
}

调试时可以添加一个桩函数

命令行输入

readline 库，历史记录功能

命令行解析

手写 parser，command 抽象类 execute 执行

镜像读取

mmap 内存映射

镜像解析

将镜像解析为如下数据结构

struct file_system {
    std::string name{};
    char *data{};
    u64 size{};
    std::vector<std::shared_ptr<file_system>> entries{};
};
using file_system_ref = std::shared_ptr<file_system>;

之后仅读取该数据结构即可

web assembly

https://vgalaxies-blog.vercel.app/posts/wasm/

lab 3

src

https://gitee.com/goodshred/oranges

setup

https://github.com/qemu/vgabios

install dev86 bin86
make vgabios.bin

修改后的配置文件如下

###############################################################
# Configuration file for Bochs
###############################################################

# how much memory the emulated machine will have
megs: 32

# filename of ROM images
romimage: file=/usr/share/bochs/BIOS-bochs-latest
vgaromimage: file=/home/vgalaxy/Desktop/vgabios/VGABIOS-lgpl-latest.bin

# what disk images will be used
floppya: 1_44=a.img, status=inserted

# choose the boot disk.
boot: floppy

# where do we send log messages?
log: bochsout.txt

# disable the mouse
mouse: enabled=0

# enable key mapping, using US layout as default.
keyboard: keymap=/usr/share/bochs/keymaps/x11-pc-us.map

freedos

http://bochs.sourceforge.net/guestos/freedos-img.tar.gz

dir b:
b:\pmtest.com

makefile

#########################
# Makefile for Orange'S #
#########################

# Entry point of Orange'S
# It must have the same value with 'KernelEntryPointPhyAddr' in load.inc!
ENTRYPOINT  = 0x30400

# Offset of entry point in kernel file
# It depends on ENTRYPOINT
ENTRYOFFSET  =   0x400

# Programs, flags, etc.
ASM    = nasm
DASM    = ndisasm
CC    = gcc -m32 -fno-stack-protector
LD    = ld -melf_i386
ASMBFLAGS  = -I boot/include/
ASMKFLAGS  = -I include/ -f elf32
CFLAGS    = -I include/ -c -fno-builtin
LDFLAGS    = -s -Ttext $(ENTRYPOINT)
DASMFLAGS  = -u -o $(ENTRYPOINT) -e $(ENTRYOFFSET)

# This Program
ORANGESBOOT  = boot/boot.bin boot/loader.bin
ORANGESKERNEL  = kernel.bin
OBJS    = kernel/kernel.o kernel/syscall.o kernel/start.o kernel/main.o\
      kernel/clock.o kernel/keyboard.o kernel/tty.o kernel/console.o\
      kernel/i8259.o kernel/global.o kernel/protect.o kernel/proc.o\
      kernel/printf.o kernel/vsprintf.o\
      lib/kliba.o lib/klib.o lib/string.o
DASMOUTPUT  = kernel.bin.asm
IMG = a.img

# All Phony Targets
.PHONY : everything final image clean realclean disasm all buildimg run

# Default starting position
nop :
  @echo "why not \`make run' huh? :)"

everything : $(ORANGESBOOT) $(ORANGESKERNEL)

run : image
  bochs -f bochsrc -q

all : realclean everything

image : realclean everything clean buildimg

clean :
  rm -f $(OBJS)

realclean :
  rm -f $(OBJS) $(ORANGESBOOT) $(ORANGESKERNEL) $(IMG)

disasm :
  $(DASM) $(DASMFLAGS) $(ORANGESKERNEL) > $(DASMOUTPUT)

buildimg :
  bximage -func=create -fd=1.44M -q $(IMG)
  dd if=boot/boot.bin of=$(IMG) bs=512 count=1 conv=notrunc
  sudo mount -o loop $(IMG) /mnt
  sudo cp -fv boot/loader.bin /mnt
  sudo cp -fv kernel.bin /mnt
  sudo umount /mnt

book

段式存储

突破 16 位寻址的界限

逻辑地址 -> 线性地址

段选择符高 13 位的索引值用来确定当前使用的段描述符在段描述符表中的位置，表示是其中的第几个段表项
段选择符存放在段寄存器中
段描述符是一种数据结构，实际上就是分段方式下的段表项
段描述符表 GDT 实际上就是分段方式下的段表，由若干个段描述符组成
lgdt 指令加载段描述符表
LDT，其选择子的 TI 位置 1

实模式 <-> 保护模式

16 位代码段中
修改寄存器 cr0 的 PE 位
jmp 跳转

特权级概述

CPL / DPL / RPL

考虑使用门描述符 (调用门) 以及对应的选择子，在不同特权级代码段之间转移

段间跳转 - 长跳转，call 压栈 eip 和 cs
段内跳转 - 短跳转，call 压栈 eip

对于长跳转，跳转前后 stack 发生变化

TSS 中存放了各个特权级下的 ss 和 esp

低特权级 -> 高特权级，使用调用门和 call 指令
高特权级 -> 低特权级，使用 ret 指令

页式存储

虚拟存储

线性地址 -> 物理地址

修改寄存器 cr0 的 PG 位
cr3 指定页目录表，包含 PDE，PDE 指向页表，包含 PTE，PTE 指向物理页
常用的 PDE 和 PTE 会缓存在 TLB 中

中断和异常

实模式下，int 15h 获取内存信息
保护模式下，中断向量表被 IDT 替代，存放中断门或陷阱门

异常的分类
- Trap
- Fault
- Abort
中断的分类
- 外部中断
  - 可屏蔽，中断控制器 8259A
    - IF 位为 1，且 8259A 的中断屏蔽寄存器 IMR 相应位为 0，才会发生
  - 不可屏蔽
- 内部中断，int 中断门，类似 call 调用门
中断和异常发生时，stack 也会发生变化，要看是否存在特权级变化

loader & kernel

boot.asm 寻找 LOADER.BIN，LOADER.BIN 为 COM 格式，所以可以直接加载到内存中，并跳转到其开始处
loader.asm 寻找 KERNEL.BIN，注意 KERNEL.BIN 为 FAT12 的格式，需要在其根目录中寻找 kernel 的二进制文件，并加载到内存中
- 跳入保护模式
- 获取内存信息，启动分页机制
- 根据 program header table 的信息加载 kernel
- 跳转到内核 _start 处
kernel.asm
- 切换 stack 和 GDT
- 启动中断和异常机制
  - 异常处理例程为 exception_handler
  - 中断处理例程为 spurious_irq

keyboard

扫描码

Make Code
Break Code

读取扫描码

in_byte(0x60);

0x60 为 8042 寄存器端口

console

VGA 寄存器

设置光标位置
滚动屏幕
设置开始显示的显存地址

通过写入显存显示字符，不同的 console 占据不同的显存

tty

tty task 运行在 ring 1，用户进程运行在 ring 3

每个用户进程绑定一个 tty console，通过 write 系统调用进行输出

doc

tty_do_read
- keyboard_read
  - 解析扫描码
  - in_process
    - 其中处理 ESC 的逻辑
    - 对于可输出的字符，存放在 tty 的键盘缓冲区
tty_do_write
- 读取 tty 键盘缓冲区的内容
- out_char
  - 根据是否为搜索模式，显式操控显存

lab 4

book

用户栈与内核栈

中断处理程序中应使用内核栈

中断处理机制

以时钟中断为例

hwint00 -> hwint_master -> irq_table -> clock_handler

doc

syscall

以 print_str 为例，分析流程如下

用户态应调用 atomic_print_str

void atomic_print_str(char *s) {
  disable_int();
  print_str(s);
  enable_int();
}

即在 print_str 调用前关中断，调用后开中断

在 syscall.asm 中导出符号 print_str

print_str:
  mov  ebx, [esp + 4]          ; ebx 保存了指向字符串的指针
  mov  eax, _NT_print_str
  int INT_VECTOR_SYS_CALL
  ret

此处 INT_VECTOR_SYS_CALL 中断向量在 protect.c 中对应的中断处理程序为 sys_call

其中会根据 sys_call_table 调用内核态的 sys_print_str

PUBLIC system_call sys_call_table[NR_SYS_CALL] = {
    sys_get_ticks,
    sys_delay_milli_seconds,
    sys_print_str,
    sys_sem_wait,
    sys_sem_post
};

sys_print_str 最终调用辅助函数 disp_str 即可

PUBLIC void sys_print_str(char *s) {
    disp_str(s);
}

scheduler

为了使普通进程 monitor 能够在每个时间片输出 readers 和 writers 的状态，需要在固定的时间片后调度给 monitor 进程

此处时间片的选择应与 readers 和 writers 的时间片保持一致，相关参数如下

#define TIMER_FREQ 1193182L /* clock frequency for timer in PC and AT */
#define HZ 100              /* clock freq (software settable on IBM-PC) */

#define TIMESLICE 500
#define MONITOR_GAP 50

monitor 进程不参与下面的讨论

scheduler 依赖的核心数据结构为 ready_queue，其中存放了可以被调度的 pid

int ready_queue[NR_TASKS - 1] = {3, 0, 1, 2, 4}; // 可调整
int ready_queue_size = NR_TASKS - 1;

为了避免进程饿死问题，考虑在 PROCESS 结构体中添加字段 has_worked，当 readers 和 writers 完成了一次读写之后，会 set 该字段为 true

scheduler 会删除 ready_queue 的第一个 pid，由此获得一个 proc，并重新添加该 pid 到 ready_queue 的末尾，若该 proc 的 has_worked 为 false，则调度该 proc，否则重复上述过程

semaphore

typedef struct semaphore {
  int value;
  int size;
  char name[32];
  PROCESS *list[MAX_WAIT_PROCESS];
} SEMAPHORE;

其中的 size 代表 wait list 目前的大小

PV 操作如下

PUBLIC void sys_sem_wait(SEMAPHORE *s) {
  s->value--;
  if (s->value < 0) {
    sleep(s);
  }
}

PUBLIC void sys_sem_post(SEMAPHORE *s) {
  s->value++;
  if (s->value <= 0) {
    wakeup(s);
  }
}

其中的 sleep 和 wakeup 会修改对应 semaphore 的 wait list，以及全局的 ready_queue

readers writers

核心算法参考了 Readers–writers problem

所需的 semaphore 如下

extern SEMAPHORE r_mutex; // 互斥保护 read count
extern SEMAPHORE w_mutex; // 互斥保护 write count
extern SEMAPHORE read_try; // 用于实现写者优先
extern SEMAPHORE resource; // 互斥保护被读写资源
extern SEMAPHORE nr_readers; // 控制同时读的次数

前四个为二值信号量，最后一个的 value 可以调整

为了给 monitor 提供相应的信息，对应的 read 和 write 的框架如下

void reader(int slices) {
  while (1) {
    task_states[p_proc_ready->pid] = WAIT_READ;
    read(slices);
    task_states[p_proc_ready->pid] = SLEEP;
    slice_milli_delay(sleeping_time[p_proc_ready->pid]);
//    atomic_delay_milli_seconds(sleeping_time[p_proc_ready->pid]);
    task_states[p_proc_ready->pid] = WAIT_READ;
    p_proc_ready->has_worked = 1;
    while (p_proc_ready->has_worked == 1) {
    }
  }
}

在获取被读写资源资源后，置 proc 的 state 为 DO_READ 或 DO_WRITE

delay

根据往届学长的分析，milli_delay 函数是进程共享的，比如 A 进程和 B 进程都需要延迟 20ms，然后 A 进程和 B 进程轮流被分配时间片，事实上在 A 的时间片里面 B 进程的延迟也在被计时，因为 ticks 对于每个进程是共享变化的

所以需要实现一个非共享的 delay 函数，为此需要：

在 PROCESS 结构体中添加字段 sleep_time
调用此函数会将对应的 proc 移出 ready_queue，同时设置 sleep_time 字段
在 scheduler 调用前，遍历所有 procs，若 proc 的 sleep_time 非 0，则递减，若减为 0，则重新移入 ready_queue

monitor

依赖下面三个数据结构输出 readers 和 writers 的状态

enum task_state { DO_READ, WAIT_READ, DO_WRITE, WAIT_WRITE, SLEEP };
enum task_state task_states[NR_TASKS - 1] = {SLEEP, SLEEP, SLEEP, SLEEP, SLEEP};
int state_to_color[5] = {0x2, 0x4, 0x2, 0x4, 0x1};
char* state_to_char[5] = {"O", "X", "O", "X", "Z"};

新时代南软特色 OS Lab

TOC

lab 1

Hello OS

calculator

lab 2

RTFM

technology selection

web assembly

lab 3

src

setup

freedos

makefile

book

段式存储

实模式 <-> 保护模式

特权级概述

页式存储

中断和异常

loader & kernel

keyboard

console

tty

doc

lab 4

book

用户栈与内核栈

中断处理机制

doc

syscall

scheduler

semaphore

readers writers

delay

monitor