前言
本文是对本学期操作系统实验必做的前四次实验的总结，以供参考。
lab1
主要是记录操作系统实验过程，为实验报告提供副本：
前导实验过程
这里是按照实验课发布的markdown文件中的指示实现实模式下Hello world的输出。
这里省略前面计基讲过的知识（P.S. 群里计科的学生似乎没接触过Linux、git这些东西，甚至被墙了也不知道为啥，很疑惑）。
实验利用的是qemu模拟80386平台，运行自制的操作系统映像，这里就要提到QEMU，它就是一款可执行硬件虚拟化的开源托管虚拟机，用软件模拟硬件。
代码运行和调试
输入
qemu-system-i386 -s -S os.img
其中-s选项是在TCP的1234端口运行一个gdbserver，选项-S使得QEMU启动时不运行80386的CPU
这时在另一个终端中运行gdb，输入
(gdb)target remote localhost:1234
就可以连接到上述的gdbserver，接着记性一系列调试操作（gdb目前不是很熟悉，打算找个时间学一学？）.
实际上在后续的实验中，可能很难通过程序计数器添加断点，而我们生成的可执行文件也可能没有符号表信息，这时候就需要使用：
(gdb)file example # 可执行文件
这样就支持使用行号、函数名等方式添加断点。
简单上手
我们将自制一个主引导扇区，然后用QEMU启动它，并输出Hello,world!.
mkdir OS2020
cd OS2020
touch mbr.s
在mbr.s这个汇编文本中写入：
接下来使用gcc编译得到的mbr.s文件：
gcc -c -m32 mbr.s -o mbr.o
文件夹下会多一个mbr.o的文件，接下来使用ld进行链接：
ld -m elf_i386 -e start -Ttext 0x7c00 mbr.o -o mbr.elf
然后查看mbr.elf属性会发现文件过大，超过一个扇区（扇区是硬盘的最小存储单元，传统扇区大小是512字节，下图的玫红色部分就是一个扇区：）
不管是i386还是i386之前的芯片，在加电后的第一条指令都是跳转到BIOS固件进行开机自检，然后将磁盘的主引导扇区（Master Boot Record, MBR ；0号柱面，0号磁头，0号扇区对应的扇区，512字节，末尾两字节为魔数
0x55和0xaa）加载到0x7c00。
所以我们尝试减少程序大小：
objcopy -S -j .text -O binary mbr.elf mbr.bin
我们接着需要将这个mbr.bin文件做成一个真正的MBR:
touch genboot.pl
在这个脚本语言中，我们写入以下内容：
#!/usr/bin/perl
open(SIG, $ARGV[0]) || die "open $ARGV[0]: $!";
$n = sysread(SIG, $buf, 1000);
if($n > 510){
print STDERR "ERROR: boot block too large: $n bytes (max 510)\n";
exit 1;
}
print STDERR "OK: boot block is $n bytes (max 510)\n";
$buf .= "\0" x (510-$n);
$buf .= "\x55\xAA";
open(SIG, ">$ARGV[0]") || die "open >$ARGV[0]: $!";
print SIG $buf;
close SIG;
修改权限以便于以./filename形式运行；
然后利用genboot.pl生成一个MBR，再次查看mbr.bin，发现其大小已经为512字节了：
/genboot.pl mbr.bin
OK: boot block is 65 bytes (max 510)
ls -al mbr.bin
-rwxr-xr-x 1 kingxu kingxu 512 2月 15 20:11 mbr.bin
一个MBR已经制作完成了，接下来就是查看我们的成果：
qemu-system-i386 mbr.bin
实现效果如下：
我们在做什么？
做完实验，但只是照葫芦画瓢，并不知道我们到底在做啥，接下来会详细介绍。
MBR
可以参考《计算机是如何启动的》，我们的工作是从第二阶段，也就是主引导记录开始：“这时，计算机读取该设备的第一个扇区，也就是读取最前面的512个字节。如果这512个字节的最后两个字节是0x55和0xAA，表明这个设备可以用于启动；如果不是，表明设备不能用于启动，控制权于是被转交给”启动顺序”中的下一个设备。”，我们在简单上手中制作的主引导扇区，就是这512个字节，也就是“主引导记录”（$Master\;boot\;record$，缩写就是MBR）。
关于mbr.s
-
.code16是指定生成16位汇编代码，对应实地址模式，我们可以在代码中发现mov、push等指令都是16位模式的； -
在
start中，我们可以发现程序将栈指针移到了0x7d00处，也就是让程序从这里开始运行，将13（字符串的长度）和字符串内容推入栈，再调用displayStr函数，符合调用约定； -
在
displayStr中的16号中断int $0x10是BIOS中断调用的第16号功能，BIOS通常在此创建了一个中断处理程序提供了实模式下的视频服务。此类服务包括设置显示模式，字符和字符串输出，和基本图形（在图形模式下的读取和写入像素）功能。更详细内容见维基百科关于它的介绍
文件处理
我们对写好的.s文件先后采取了编译、链接、缩小文件大小、制作成MBR，我们会一一解释。
编译
gcc -c -m32 mbr.s -o mbr.o
我们需要注意编译时的参数：
-
-c：编译成可重定位目标文件； -
-m32：生成32位机器的汇编代码；
链接
ld -m elf_i386 -e start -Ttext 0x7c00 mbr.o -o mbr.elf
在ld --help中，我们可以了解到这个复杂命令的行为：
-
-m：设置仿真，后面的elf_i386就是以elf_i386的模式仿真: -
-e：设置起始地址，后面的start对应mbr.s中的start； -
-Ttext：设置 .text 节的地址，此处是0x7c00，对应要将引导程序复制到的位置.
减小程序大小
objcopy -S -j .text -O binary mbr.elf mbr.bin
objcopy命令的作用是“复制二进制文件，可能在此过程中进行变换”.
参数含义：
-
-S：移除所有的符号和重定位信息； -
-j：只将某一节的内容复制到输出文件，这里就是.text节； -
-O：输出文件以指定形式输出，这里就是以二进制形式输出.
制作MBR
这里是使用一个Perl脚本将二进制文件制作成MBR，个人觉得不难读懂：
-
打开从命令行参数读取的文件；
-
设文件大小为$n$个字节，如果$n$超过510字节，则转换失败，否则就会将$n$个字节后的$510-n$个字节全部填充为0，最后两个字节分别是魔数
0x55和0xaa，此时文件大小恰是512字节； -
关闭文件.
接着我们就按教程那样去用QEMU执行引导程序，并显示上面的结果
实验一记录
下面是实验文件的文件夹结构
.
├── lab1
│ ├── app
│ │ ├── app.s # 为实验1.3提供的磁盘程序
│ │ └── Makefile
│ ├── bootloader
│ │ ├── boot.c # 保护模式下，由于中断关闭而无法通过陷入磁盘中断调用BIOS进行磁盘读取的解决方案
│ │ ├── boot.h
│ │ ├── Makefile
│ │ └── start.s # 实验的核心，MBR的汇编代码
│ ├── Makefile
│ └── utils
│ └── genboot.pl # MBR生成脚本，上文已提及
└── report # 实验报告
└── 191300064.pdf
实验1.1就是上面说的实模式输出Hello world，我们接着要实现的是：保护模式下输出Hello world和加载磁盘中的Hello world程序并运行。
保护模式
首先是实模式到保护模式的切换：
.global start
start:
movw %cs, %ax
movw %ax, %ds
movw %ax, %es
movw %ax, %ss
cli
inb $0x92, %al
orb $0x02, %al
outb %al, $0x92
data32 addr32 lgdt gdtDesc
movl %cr0, %eax
orb $0x01, %al
movl %eax, %cr0
data32 ljmp $0x08, $start32
-
cli指令禁止终端发生； -
inb ..., orb ..., outb ...是在打开A20数据总线； -
data32 addr32 lgdt gdtDesc语句加载GDTR，启动保护模式； -
后面三句是设置
CR0的PE位（第0位）为1（PE就是protection enable的意思）； -
data32 ljmp $0x08, $start32将长跳转切换至保护模式.
cli指令禁止中段发生后，原来的displayStr就无法使用了，我们需要像另外一种方式：
displayStr:
movl 4(%esp), %ebx
movl 8(%esp), %ecx
movl $0, %edi # 这里是将输出字符坐标的起始点设置为最上角；
# 你也可以设置为(80*i+j)，也就是第i行第j列开始输出.
movb $0x0c, %ah # 黑底红字
label: # 我们通过循环来实现输出.
movb (%ebx), %al
movw %ax, %gs:(%edi)
addl $2, %edi # 每一个屏幕上字符单元,在内存中通过两字节表示,第一个字节被展示字符的 ASCII 编码,第二个字节包含
# 字符的一些属性,比如字符的前景色和背景色,字符是否应该闪烁等。
incl %ebx
loop label
ret
下面就是实现的结果：
保护模式运行磁盘程序
这里我们就不再需要displatStr函数了，它已经在app.s中，在原来start32的最后是调用自定义的displayStr函数，这里就需要跳转到给定的bootMain入口：
movl $0x8000, %eax
movl %eax, %esp
jmp bootMain
相应的，我们补全boot.c中的bootMain函数：
typedef void (*PF)(void);
void bootMain(void) {
PF pf = (PF)0x8c00;
readSect((void *)pf, 1);
pf();
}
定义函数指针，令指针指向0x8c00，读取扇区，然后调用函数，效果如下：
总结
也许是实验本身的原因，它的内容比课堂内容超前，使得我一直在参考讲义和书本（和Github）。但这次实验让我收获颇多，而且和之前装系统的经历对应起来，强化了我对操作系统的了解。
lab2
这是操作系统的第二次实验，代码量大幅度增加，任务也比较多。
这是操作系统的第二次实验，首先，实验框架很大，需要一定时间去阅读以窥全貌；第二，该实验对设备有一定需求：Ubuntu20.04内核过新而不适用于该实验（体现在qemu在打印字符失败）；此外，实验涉及到的不只是操作系统中提及的中断等知识点，还涉及到一些编程任务，比如手写一个printf等；最后，$\text{TODO Tree}$和$\text{git}$是好东西。我们会按照手册的指导顺序来书写实验报告。
模式跳转和程序加载
这部分其实是$\text{lab 1}$的任务，我们只在这里作简要概述。
我们有三个任务：
- 补全
bootMain，即内核程序加载； - 补全
loadUMain，即用户程序加载； - 在
start.S中设置esp，以实现跳转.
在任务一中，我们需要获取kMainEntry（程序入口）、phoff（程序头偏移）和offset（文件内便宜量）.
掌握可执行文件面向执行的segment视角以及<elf.h>库的使用就可以完成：
typedef void (*VPVF)(void);
kMainEntry = (VPVF)((ElfHeader* elf))->entry;
phoff = ((ELFHeader *)elf)->phoff;
offset = ((ProgramHeader *)(elf + phoff))->off;
任务二是任务一的复用，我们仿照bootMain函数来补全loadUMain：
void loadUMain(void) {
int i = 0;
int phoff = 0x34;
int offset = 0x1000;
uint32_t elf = 0x200000;
uint32_t uMainEntry = 0x200000;
for (i = 0; i < 200; i++) {
readSect((void *)(elf + i * 512), 201 + i);
}
uMainEntry =
((struct ELFHeader *)elf)->entry; // entry address of the program
phoff = ((struct ELFHeader *)elf)->phoff;
offset = ((struct ProgramHeader *)(elf + phoff))->off;
for (i = 0; i < 200 * 512; i++) {
*(uint8_t *)(elf + i) = *(uint8_t *)(elf + i + offset);
}
enterUserSpace(uMainEntry);
}
任务三需要我们将esp设置为合适的值，事实上，就是TSS.esp0的初始值：
movl $0x1fffff, %eax
movl %eax, %esp
中断机制的实现
这部分我们还是有三个任务：
- 将irqKeyboard的中断向量号压入栈（
doIrq.S）； - 完善中断处理机制（
idt.c）； - 补全中断处理程序（
irqHandle.c）.
任务一不难，只需要知道键盘中断的中断向量号是0x21即可：
.global irqKeyboard
irqKeyboard:
pushl $0
pushl $0x21
jmp asmDoIrq
对于任务二，我们需要初始化门和IDT表。初始化门需要就是根据讲义中的中断门和陷阱门结构就可以完成：
/* 初始化一个中断门(interrupt gate) */
static void setIntr(struct GateDescriptor *ptr, uint32_t selector,
uint32_t offset, uint32_t dpl) {
ptr->offset_15_0 = (uint16_t)(offset & 0xffff);
ptr->segment = selector << 3;
ptr->pad0 = 0;
ptr->type = INTERRUPT_GATE_32;
ptr->system = FALSE;
ptr->privilege_level = dpl;
ptr->present = TRUE;
ptr->offset_31_16 = (offset >> 16) & 0xFFFF;
}
/* 初始化一个陷阱门(trap gate) */
static void setTrap(struct GateDescriptor *ptr, uint32_t selector,
uint32_t offset, uint32_t dpl) {
ptr->offset_15_0 = (uint16_t)(offset & 0xffff);
ptr->segment = selector << 3;
ptr->pad0 = 0;
ptr->type = TRAP_GATE_32;
ptr->system = FALSE;
ptr->privilege_level = dpl;
ptr->present = TRUE;
ptr->offset_31_16 = (offset >> 16) & 0xFFFF;
}
IDT表的初始化就是利用setTrap函数将中断处理函数设置到IDT表中，并注明特权优先级：
/*
* init your idt here
* 初始化 IDT 表, 为中断设置中断处理函数
*/
/* Exceptions with error code */
setTrap(idt + 0x08, SEG_KCODE, (uint32_t)irqDoubleFault, DPL_KERN);
setTrap(idt + 0x0a, SEG_KCODE, (uint32_t)irqInvalidTSS, DPL_KERN);
setTrap(idt + 0x0b, SEG_KCODE, (uint32_t)irqSegNotPresent, DPL_KERN);
setTrap(idt + 0x0c, SEG_KCODE, (uint32_t)irqStackSegFault, DPL_KERN);
setTrap(idt + 0x0d, SEG_KCODE, (uint32_t)irqGProtectFault, DPL_KERN);
setTrap(idt + 0x0e, SEG_KCODE, (uint32_t)irqPageFault, DPL_KERN);
setTrap(idt + 0x11, SEG_KCODE, (uint32_t)irqAlignCheck, DPL_KERN);
setTrap(idt + 0x1e, SEG_KCODE, (uint32_t)irqSecException, DPL_KERN);
setTrap(idt + 0x21, SEG_KCODE, (uint32_t)irqKeyboard, DPL_KERN);
/* Exceptions with DPL = 3 */
setIntr(idt + 0x80, SEG_KCODE, (uint32_t)irqSyscall, DPL_USER);
/* 写入IDT */
saveIdt(idt, sizeof(idt));
任务三是让程序能够通过不同的irq（中断请求），来进行不同的处理：
switch (tf->irq) {
case -1:
break;
case 0x0d: // 一般保护错误
GProtectFaultHandle(tf);
break;
case 0x21: // 键盘中断
KeyboardHandle(tf);
break;
case 0x80: // 系统调用中断
syscallHandle(tf);
break;
default:
assert(0);
}
printf和对应的处理例程的实现
在之前的学习中（ICS-2020），我们已经接触过printf函数的实现，但当时负责输出的函数put(char)是直接与串口连接的，与真实情况存在差别。我们知道实际上printf函数的输出是通过系统调用实现的，这次的实验正是基于这一事实去实现它。
框架已经为我们提供了格式化函数（十进制转字符串，十六进制转字符串，字符串转字符串），为我们的工作带来便利。
实现好的printf：
void printf(const char *format, ...) {
va_list ap;
va_start(ap, format);
int i = 0; // format index
char buffer[MAX_BUFFER_SIZE];
int count = 0; // buffer index
int decimal = 0;
uint32_t hexadecimal = 0;
char *string = 0;
char character = 0;
while (format[i] != 0) {
buffer[count++] = format[i];
if (format[i] == '%') {
count--;
i++;
switch (format[i]) {
case 'c':
character = va_arg(ap, int);
buffer[count++] = character;
break;
case 's':
string = va_arg(ap, char *);
count = str2Str(string, buffer, (uint32_t)MAX_BUFFER_SIZE,
count);
break;
case 'x':
hexadecimal = va_arg(ap, uint32_t);
count = hex2Str(hexadecimal, buffer,
(uint32_t)MAX_BUFFER_SIZE, count);
break;
case 'd':
decimal = va_arg(ap, int);
count = dec2Str(decimal, buffer, (uint32_t)MAX_BUFFER_SIZE,
count);
break;
case '%':
count++;
break;
}
}
if (count == MAX_BUFFER_SIZE) {
syscall(SYS_WRITE, STD_OUT, (uint32_t)buffer,
(uint32_t)MAX_BUFFER_SIZE, 0, 0);
count = 0;
}
i++;
}
if (count != 0)
syscall(SYS_WRITE, STD_OUT, (uint32_t)buffer, (uint32_t)count, 0, 0);
va_end(ap);
return;
}
我们需要熟悉$\text{C}$的可变长参数的使用。这里的系统调用
syscall(SYS_WRITE, STD_OUT, (uint32_t)buffer, (uint32_t)count, 0, 0);
实现了字符串写入到标准输出。
当然，这些系统调用也需要我们补全，框架的系统调用逻辑：
\[\text{syscallHandle} \begin{cases} \text{syscallWrite}\to\text{syscallPrint}\\ \text{syscallRead}\begin{cases} \text{syscallGetChar}\\ \text{syscallGetStr}\\ \end{cases} \end{cases}\]这里我们先完成$\text{syscallPrint}$，我们需要维护光标和打印字符：
void syscallPrint(struct TrapFrame *tf) {
int sel = USEL(SEG_UDATA); // TODO: segment selector for user data, need
// further modification
char *str = (char *)tf->edx;
int size = tf->ebx;
int i = 0;
int pos = 0;
char character = 0;
uint16_t data = 0;
asm volatile("movw %0, %%es" ::"m"(sel));
for (i = 0; i < size; i++) {
asm volatile("movb %%es:(%1), %0" : "=r"(character) : "r"(str + i));
// TODO: 完成光标的维护和打印到显存
if (character == '\n') {
displayRow++;
displayCol = 0;
if (displayRow == 25) {
displayRow = 24;
displayCol = 0;
scrollScreen();
}
} else {
pos = (80 * displayRow + displayCol) * 2;
asm volatile("movw %0, (%1)" ::"r"(character), "r"(pos + 0xb8000));
displayCol++;
if (displayCol == 80) {
displayRow++;
displayCol = 0;
if (displayRow == 25) {
displayRow = 24;
displayCol = 0;
scrollScreen();
}
}
}
}
updateCursor(displayRow, displayCol);
}
至此，我们已经可以在qemu中看到红色的字符，也就是app/main.c中的测试内容：
由于我们后面要经常维护光标和打印显存，所以我们定义下面的宏：
getChar/Str的实现
准备工作
在实现这两个库函数之前，我们先定义这几个宏：
-
输入回车时光标和显存的维护：
#define enterHandle \ displayRow++; \ displayCol = 0; \ if (displayRow == 25) { \ displayRow = 24; \ displayCol = 0; \ scrollScreen(); \ } -
输入退格键时对光标和显存的维护，其中参数
row和col表示开始输入时的光标起始点，防止光标出界：#define backspaceHandle(row, col) \ if (displayCol > col && displayRow == row) { \ displayCol--; \ } else if (displayCol > 0 && row > displayRow) { \ displayCol--; \ } \ uint16_t data = 0 | (0x0c << 8); \ int pos = (80 * displayRow + displayCol) * 2; \ asm volatile("movw %0,(%1)" ::"r"(data), "r"(pos + 0xb8000)); -
输入字符时对光标和显存的维护（只对可见字符生效）：
#define charHandle(character) \ if (character >= 0x20 && character <= 0x07e) { \ int pos = (80 * displayRow + displayCol) * 2; \ asm volatile("movb %0, (%1)" ::"r"(character), "r"(pos + 0xb8000)); \ displayCol++; \ if (displayCol == 80) { \ displayRow++; \ displayCol = 0; \ if (displayRow == 25) { \ displayRow = 24; \ displayCol = 0; \ scrollScreen(); \ } \ } \ }
getChar书写
根据框架中的提示，尤其是printf，我们不难知道getChar和getStr函数也是借助系统调用实现：
char getChar() {
char ch = syscall(SYS_READ, STD_IN, 0, 0, 0, 0);
// 将eax作为返回值.
return ch;
}
void getStr(char* str, int size) {
// 和printf的系统调用几乎完全一致
syscall(SYS_READ, STD_STR, (uint32_t)str, (uint32_t)size, 0, 0);
}
根据上面系统调用的层次图，我们需要补全syscallGetChar和syscallGetStr.
正如讲义说的那样，syscallGetChar的逻辑其实比较简单，但实现起来需要考虑周全：
void syscallGetChar(struct TrapFrame *tf) {
uint32_t code = 0;
int get_result = 0;
char character = 0;
int stdDisplayRow = displayRow; // 光标初始行
int stdDisplayCol = displayCol; // 光标初始列
while (code != 0x1c) { // 输入回车就退出
code = getKeyCode();
if (code < 0x81 && code != 0) { // 合法字符
character = getChar(code);
// 模仿C中的getChar：
// 接受多个输入字符，但只返回第一个字符.
// 仍是仅限可见字符
if (get_result == 0 && character >= 0x20 && character <= 0x7e) {
get_result = 1;
tf->eax = character;
}
if (character == '\n') {
enterHandle; // 回车处理
} else if (code == 0x0e) {
backspaceHandle(stdDisplayRow, stdDisplayCol);
// 在只剩一个字符时再输入退格，则会抹除存储的char
if (get_result == 1 && stdDisplayCol == displayCol &&
stdDisplayRow == displayRow) {
get_result = 0;
}
} else {
charHandle(character); // 处理普通字符
}
// 更新光标
updateCursor(displayRow, displayCol);
}
}
return;
}
getChar测试
我们先连续输入123：
再退格删掉全部字符：
最后输入4作为最后答案（虽然是错的）：
说明我们已经实现了较为完备的getChar.
getStr书写
而对于syscallGetStr，就更加复杂，不能简单理解为多个getChar，因为还要考虑缓冲区的操作：
先是信息的获取：
char *str = (char *)tf->edx;
int size = tf->ebx;
然后读取键盘输入直到缓冲区即将溢出：
while ((bufferTail + 1) % MAX_KEYBUFFER_SIZE != bufferHead) {
while (code != 0x1c) {
code = getKeyCode();
character = getChar(code);
if (code < 0x81 && code != 0) {
if (character == '\n') {
enterHandle;
} else if (code == 0x0e) {
backspaceHandle(stdDisplayRow, stdDisplayCol);
// 按下退格键后，我们需要所减缓冲区直到为空
if (bufferTail > 0) {
bufferTail--;
}
} else if (character >= 0x20 && character <= 0x7e) {
// 读取合法字符
bufferTail = (bufferTail + 1) % MAX_KEYBUFFER_SIZE;
keyBuffer[bufferTail] = character;
charHandle(character);
}
updateCursor(displayRow, displayCol);
}
}
if (code == 0x1c || code == 0x9c) break;
code = 0;
}
这里的缓冲区使用2个int来充当缓冲区的指针，分别指向头和尾。
在获取到字符之后，就是只要将缓冲区中的字符写入str即可：
while (i < size - 1) {
if (bufferHead != bufferTail) {
character = getChar(keyBuffer[bufferHead]);
bufferHead = (bufferHead + 1) % MAX_KEYBUFFER_SIZE;
if (character != 0) {
asm volatile("movb %0, %%es:(%1)" ::"r"(character),
"r"(str + i));
i++;
}
} else
break;
}
别忘记在字符串最后加上'\0'字符：
asm volatile("movb $0x00, %%es:(%0)" ::"r"(str + i));
getStr测试
这里我们类似地进行带退格键的getStr测试.
先输入错误答案：
然后退格，输入正确答案：
成功！
总结
至此，我们已经完成了实验二。虽然完成了实验，但显然对代码框架的了解不如实验一，很大一部分归结于对知识点的不了解，操作系统的书本知识对实验有很大帮助，这是这次实验我所学到的东西.
勘误：测试
getStr函数时的例句和上面的printf内容不符，但不影响实验.
lab3
实验三主要内容是系统调用的实现，难度不大。
实验手册，但内容比较像是往年的实验，因为存在与今年框架不相容的地方，但不是很影响阅读.
这次实验还是需要在$\text{Ubuntu 18.04}$及以下的内核版本上进行，否则会产生问题。
实验的必做内容比较简单，参考实验手册可完成不少.
这次实验涉及到C的进程编程，可以参考C的进程编程.
通过$\text{TODO Tree}$，我们可以更快的确定任务位置，此次任务主要是对irqHandle.c的增改. 我们将按照任务的难易程度来书写实验过程.
实验效果预览：
系统调用框架和库函数的补全
如讲义所言，这部分任务其实算是lab2的延申，根据lib.h提供的系统调用号：
#define SYS_FORK 1
#define SYS_EXEC 2
#define SYS_SLEEP 3
#define SYS_EXIT 4
我们按此可以定义函数和将其嵌入框架（syscallHandle）：
void syscallFork(struct StackFrame *sf);
void syscallExec(struct StackFrame *sf);
void syscallSleep(struct StackFrame *sf);
void syscallExit(struct StackFrame *sf);
我们在syscallHandle函数中加入上述系统调用函数：
void syscallHandle(struct StackFrame *sf) {
switch (sf->eax) { // syscall number
case 0:
syscallWrite(sf);
break; // for SYS_WRITE
case 1:
syscallFork(sf);
break; // for SYS_FORK
case 2:
syscallExec(sf);
break; // for SYS_EXEC
case 3:
syscallSleep(sf);
break; // for SYS_SLEEP
case 4:
syscallExit(sf);
break; // for SYS_EXIT
default:
break;
}
}
时钟中断的实现
首先我们要在irqHandle函数中注册时钟中断（b不要忘记栈指针的保存和恢复）：
void irqHandle(struct StackFrame *sf) {
...
uint32_t tmpStackTop = pcb[current].stackTop;
pcb[current].prevStackTop = pcb[current].stackTop;
pcb[current].stackTop = (uint32_t)sf;
switch (sf->irq) {
case -1:
break;
case 0xd:
GProtectFaultHandle(sf);
break;
case 0x20:
timerHandle(sf);
break;
case 0x80:
syscallHandle(sf);
break;
default:
assert(0);
pcb[current].stackTop = tmpStackTop;
...
我们按照讲义的指导在时钟中断时的中断处理函数中实现进程的切换：
void timeHandle(struct StackFrame *sf) {
/*
遍历pcb，将状态为STATE_BLOCKED的进程的sleepTime减一，
如果进程的sleepTime变为0，
重新设为STATE_RUNNABLE
*/
for (int i = 0; i < MAX_PCB_NUM; i++) {
if (pcb[i].state == STATE_BLOCKED) {
pcb[i].sleepTime--;
if (pcb[i].sleepTime == 0) {
pcb[i].state = STATE_RUNNABLE;
}
}
}
// 将当前进程的timeCount加一
pcb[current].timeCount++;
int i;
/*
如果时间片用完（timeCount==MAX_TIME_COUNT）
且有其它状态为STATE_RUNNABLE的进程，切换
*/
if (pcb[current].timeCount > MAX_TIME_COUNT) {
pcb[current].state = STATE_RUNNABLE;
pcb[current].timeCount = 0;
for (i = (current + 1) % MAX_PCB_NUM; i != current;
i = (i + 1) % MAX_PCB_NUM)
if (pcb[i].state == STATE_RUNNABLE) break;
current = i;
pcb[current].state = STATE_RUNNING;
}
// 进程切换
uint32_t tmpStackTop = pcb[current].stackTop;
pcb[current].stackTop = pcb[current].prevStackTop;
tss.esp0 = pcb[current].stackTop;
tss.ss0 = KSEL(SEG_KDATA);
asm volatile("movl %0, %%esp" : : "m"(tmpStackTop));
asm volatile("popl %gs");
asm volatile("popl %fs");
asm volatile("popl %es");
asm volatile("popl %ds");
asm volatile("popal");
asm volatile("addl $8, %esp");
asm volatile("iret");
}
系统调用例程
syscallFork
void syscallFork(struct StackFrame *sf) {
int i, j;
// 寻找一个空闲的pcb做为子进程的进程控制块
for (i = 0; i < MAX_PCB_NUM; i++) {
if (pcb[i].state == STATE_DEAD) {
break;
}
}
if (i != MAX_PCB_NUM) {
// 将父进程的资源复制给子进程
// 开中断
enableInterrupt();
for (j = 0; j < 0x100000; j++) {
*(uint8_t *)(j + (i + 1) * 0x100000) =
*(uint8_t *)(j + (current + 1) * 0x100000);
}
// 关中断
disableInterrupt();
// 复制内核栈
for (j = 0; j < sizeof(ProcessTable); ++j)
*((uint8_t *)(&pcb[i]) + j) = *((uint8_t *)(&pcb[current]) + j);
pcb[i].stackTop = (uint32_t) & (pcb[i].regs);
pcb[i].prevStackTop = (uint32_t) & (pcb[i].stackTop);
pcb[i].state = STATE_RUNNABLE;
pcb[i].timeCount = 0;
pcb[i].sleepTime = 0;
pcb[i].pid = i;
// 设置寄存器
pcb[i].regs.ss = USEL(2 + 2 * i);
pcb[i].regs.cs = USEL(1 + 2 * i);
pcb[i].regs.ds = USEL(2 + 2 * i);
pcb[i].regs.es = USEL(2 + 2 * i);
pcb[i].regs.fs = USEL(2 + 2 * i);
pcb[i].regs.gs = USEL(2 + 2 * i);
// 设置返回值
// 成功,子进程返回0
pcb[i].regs.eax = 0;
// 父进程返回子进程pid
pcb[current].regs.eax = i;
} else {
// fork失败，父进程返回-1
pcb[current].regs.eax = -1;
}
return;
}
syscallSleep
这里我们有两个任务：
- 将当前的进程的
sleepTime设置为传入的参数，将当前进程的状态设置为STATE_BLOCKED; - 模拟时钟中断，利用
timerHandle进行进程切换.
void syscallSleep(struct StackFrame *sf) {
// 将当前的进程的sleepTime设置为传入的参数
pcb[current].sleepTime = sf->ecx;
// 模拟时钟中断，利用timerHandle进行进程切换.
pcb[current].state = STATE_BLOCKED;
// 仿照timerHandle进行进程切换
int i;
for (i = (current + 1) % MAX_PCB_NUM; i != current;
i = (i + 1) % MAX_PCB_NUM)
if (pcb[i].state == STATE_RUNNABLE) break;
current = i;
pcb[current].state = STATE_RUNNING;
uint32_t tmpStackTop = pcb[current].stackTop;
pcb[current].stackTop = pcb[current].prevStackTop;
tss.esp0 = pcb[current].stackTop;
tss.ss0 = KSEL(SEG_KDATA);
asm volatile("movl %0, %%esp" : : "m"(tmpStackTop));
asm volatile("popl %gs");
asm volatile("popl %fs");
asm volatile("popl %es");
asm volatile("popl %ds");
asm volatile("popal");
asm volatile("addl $8, %esp");
asm volatile("iret");
return;
}
syscallExit
这里还是有2个任务：
- 将当前进程的状态设置为STATE_DEAD;
- 模拟时钟中断进行进程切换.
void syscallExit(struct StackFrame *sf) {
// 将当前进程的状态设置为STATE_DEAD
int i;
for (i = (current + 1) % MAX_PCB_NUM; i != current;
i = (i + 1) % MAX_PCB_NUM)
if (pcb[i].state == STATE_RUNNABLE) break;
current = i;
pcb[current].state = STATE_RUNNING;
// 仿照timerHandle进行进程切换
...
}
至此我们已经实现了进程切换：
lab4
实验四是关于信号量与PV操作，与理论联系较密切。
本次实验的主题是信号量与PV操作，并基于此解决5个哲学界就餐问题。基于实验手册，我们可以在一些步骤上节省不少时间。我们这次采用的是$\text{Ubuntu16.04}$平台，使用$\text{TODO Tree}$进行任务搜寻和$\text{git}$进行版本控制。实验难度不大，但在调试上花去了不少时间。
格式化输入函数(scanf)的实现
在lab2中，我们已经实现了格式化输出函数，但没有实现真正功能完备的格式化输入函数，这是因为基于中断的scanf需要进行进程同步，而这个在前面的实验中没有涉及。我们首先需要实现一个scanf函数并通过下面的程序测试：
#include "lib.h"
#include "types.h"
int uEntry(void) {
int dec = 0;
int hex = 0;
char str[6];
char cha = 0;
int ret = 0;
while(1){
printf("Input:\" Test %%c Test %%6s %%d %%x\"\n");
ret = scanf(" Test %c Test %6s %d %x", &cha, str, &dec, &hex);
printf("Ret: %d; %c, %s, %d, %x.\n", ret, cha, str, dec, hex);
if (ret == 4)
break;
}
return 0;
}
我们输入Test a Test oslab 2021 0xadc，屏幕上会输出Ret: 4; a, oslab, 2021, adc。
任务目标
好在为了降低实验难度，scanf的框架已经完成，我们只需要完成中断处理例程。借助$\text{TODO Tree}$，我们找到了实现位置：
-
处理好键盘中断，也就是在无法立刻获得键盘资源时，进程阻塞时的处理：
void keyboardHandle(struct StackFrame *sf) { ProcessTable *pt = NULL; uint32_t keyCode = getKeyCode(); if (keyCode == 0) // illegal keyCode return; // putChar(getChar(keyCode)); keyBuffer[bufferTail] = keyCode; bufferTail = (bufferTail + 1) % MAX_KEYBUFFER_SIZE; if (dev[STD_IN].value < 0) { // with process blocked // TODO: deal with blocked situation } return; } -
标准流输入的系统调用，这里也需要对进程阻塞进行额外的处理：
void syscallReadStdIn(struct StackFrame *sf) { // TODO: complete `stdin` }
解决方案
这次实验框架设计的巧妙之处在于，它将设备抽象成一种资源，从而在设计上与“信号量”极为相似：
struct Semaphore {
int state;
int value;
struct ListHead pcb; // link to all pcb ListHead blocked on this semaphore
};
typedef struct Semaphore Semaphore;
struct Device {
int state;
int value;
struct ListHead pcb; // link to all pcb ListHead blocked on this device
};
typedef struct Device Device;
Semaphore sem[MAX_SEM_NUM];
Device dev[MAX_DEV_NUM];
在操作系统中，我们不可能通过一直监听键盘中断来进行输入，这样太浪费系统资源了，所以我们需要一个键盘输入缓冲区和类似信号量的东西来实现条件同步，在键盘中断将输入存入缓冲区后再让用户程序读取，所以代码中定义了Device，他其实就是信号量，只不过不能由用户通过系统调用控制，而是直接和硬件绑定。一个信号量由其状态，值（value）和等待队列构成，设备亦然。
所以，对于keyboardHandle，当进程阻塞（也就是设备信号量的值为负），我们进行的是类似PV操作中的V操作：
if (dev[STD_IN].value < 0) {
// v.value++
dev[STD_IN].value++;
// 从信号量i上阻塞的进程列表取出一个进程
// 这里不是信号量(sem)，而是设备(dev)，注意区分
pt = (ProcessTable*)((uint32_t)(dev[i].pcb.prev) -
(uint32_t)&(((ProcessTable*)0)->blocked));
dev[i].pcb.prev = (dev[i].pcb.prev)->prev;
(dev[i].pcb.prev)->next = &(dev[i].pcb);
// 进程被激活唤醒
pt->state = STATE_RUNNABLE;
pt->sleepTime = 0;
}
类似的，在syscallReadStdIn中，我们需要占用输入设备资源，所以对应的是PV操作中的P：
void syscallReadStdIn(struct StackFrame *sf) {
if (dev[STD_IN].value == 0) {
// 信号量减一
dev[STD_IN].value--;
// 将current线程加到信号量i的阻塞列表
pcb[current].blocked.next = dev[STD_IN].pcb.next;
pcb[current].blocked.prev = &(dev[STD_IN].pcb);
dev[STD_IN].pcb.next = &(pcb[current].blocked);
(pcb[current].blocked.next)->prev = &(pcb[current].blocked);
// 阻塞线程
pcb[current].state = STATE_BLOCKED;
pcb[current].sleepTime = -1; // blocked on STD_IN
asm volatile("int $0x20");
// 获取相关信息
int sel = sf->ds;
char *str = (char *)sf->edx;
int size = sf->ebx; // MAX_BUFFER_SIZE, reverse last byte
int i = 0;
char character = 0;
asm volatile("movw %0, %%es" ::"m"(sel));
// 处理键盘输入
while (i < size - 1) {
if (bufferHead != bufferTail) {
character = getChar(keyBuffer[bufferHead]);
bufferHead = (bufferHead + 1) % MAX_KEYBUFFER_SIZE;
// putChar(character);
if (character != 0) {
asm volatile("movb %0, %%es:(%1)" ::"r"(character),
"r"(str + i));
i++;
}
} else
break;
}
asm volatile("movb $0x00, %%es:(%0)" ::"r"(str + i));
pcb[current].regs.eax = i;
return;
} else if (dev[STD_IN].value < 0) { // 进程仍然堵塞
pcb[current].regs.eax = -1;
return;
}
}
至此我们已经完整实现了scanf，接下来是测试环节：
信号量相关系统调用的实现
我们将实现SEM_INIT、SEM_POST、SEM_WAIT、SEM_DETROY系统调用，分别用于信号量初始化、V操作、P操作和释放信号量。并进行下面的用户测试：
#include "lib.h"
#include "types.h"
int uEntry(void) {
int i = 4;
int ret = 0;
int value = 2;
sem_t sem;
printf("Father Process: Semaphore Initializing.\n");
ret = sem_init(&sem, value);
if (ret == -1) {
printf("Father Process: Semaphore Initializing Failed.\n");
exit();
}
ret = fork();
if (ret == 0) {
while( i != 0) {
i --;
printf("Child Process: Semaphore Waiting.\n");
sem_wait(&sem);
printf("Child Process: In Critical Area.\n");
}
printf("Child Process: Semaphore Destroying.\n");
sem_destroy(&sem);
exit();
}
else if (ret != -1) {
while( i != 0) {
i --;
printf("Father Process: Sleeping.\n");
sleep(128);
printf("Father Process: Semaphore Posting.\n");
sem_post(&sem);
}
printf("Father Process: Semaphore Destroying.\n");
sem_destroy(&sem);
exit();
}
return 0;
}
其中，系统调用函数systemSemWait和systemSemPost对应P操作和V操作，参考实验手册和教材上的伪码即可实现，而syscallSemInit将所有的信号量进行状态，值以及进程队列的初始化：
void syscallSemInit(struct StackFrame *sf) {
int i;
for (i = 0; i < MAX_SEM_NUM; i++) {
if (sem[i].state == 0) break;
}
if (i != MAX_SEM_NUM) {
sem[i].state = 1;
sem[i].value = (int32_t)sf->edx;
sem[i].pcb.next = &(sem[i].pcb);
sem[i].pcb.prev = &(sem[i].pcb);
pcb[current].regs.eax = i;
} else
pcb[current].regs.eax = -1;
return;
}
而在syscallSenDestroy中，我们需要将仍在使用的信号量销毁：
void syscallSemDestroy(struct StackFrame *sf) {
int i = sf->edx;
if (sem[i].state == 1) {
pcb[current].regs.eax = 0;
sem[i].state = 0;
asm volatile("int $0x20");
} else
pcb[current].regs.eax = -1;
return;
}
我们可以运行测试：
通过源码和输出，我们可以解释这段测试程序：
- 父进程（生产者）初始定义了一个值为
2的信号量value，然后睡眠，子进程（消费者）因此可以进入临界区两次，之后子进程睡眠； - 子进程睡眠会唤醒父进程，父进程会将信号量加一，继续睡眠，子进程又可以进入临界区一次；
- 上面的循环一直持续到子进程访问了4次临界区.
基于信号量解决哲学家就餐问题
哲学家就餐问题可以这样表述，假设有五位哲学家围坐在一张圆形餐桌旁，做以下两件事情之一：吃饭，或者思考。吃东西的时候，他们就停止思考，思考的时候也停止吃东西。餐桌中间有一大碗义大利面，每位哲学家之间各有一支餐叉。因为用一支餐叉很难吃到义大利面，所以假设哲学家必须用两支餐叉吃东西。他们只能使用自己左右手边的那两支餐叉。
哲学家就餐问题有时也用米饭和五根筷子而不是意大利面和餐叉来描述，因为吃米饭必须用两根筷子。
我们采用实验手册上最全面的PV操作算法来解决这个问题，它既没有死锁，也允许多人就餐：
#define N 5 // 哲学家个数
semaphore fork[5]; // 信号量初值为1
void philosopher(int i){ // 哲学家编号：0-4
while(TRUE){
think(); // 哲学家在思考
if(i%2==0){
P(fork[i]); // 去拿左边的叉子
P(fork[(i+1)%N]); // 去拿右边的叉子
} else {
P(fork[(i+1)%N]); // 去拿右边的叉子
P(fork[i]); // 去拿左边的叉子
}
eat(); // 吃面条
V(fork[i]); // 放下左边的叉子
V(fork[(i+1)%N]); // 放下右边的叉子
}
}
为了更好观察实验结果，我们规定，每个原语（P，V操作，吃和思考）之间都会有一个sleep(128)语句。
那么我们不难用程序模拟这个问题：
#define N 5
void philosopher(int id, sem_t* forks) {
pid_t pid = getpid();
while (1) { // 不断循环：思考->拿餐具->吃
printf("Pid : %d, Philosopher %d: think\n", pid, id);
sleep(128);
if (id % 2 == 0) {
sem_wait(forks + id);
sleep(128);
sem_wait(forks + (id + 1) % N);
} else {
sem_wait(forks + (id + 1) % N);
sleep(128);
sem_wait(forks + id);
}
sleep(128);
printf("Pid : %d, Philosopher %d: eat\n", pid, id);
sleep(128);
sem_post(forks + id);
sleep(128);
sem_post(forks + (id + 1) % N);
}
}
int uEntry(void) {
sem_t forks[N];
for (int i = 0; i < N; i++) {
sem_init(forks + i, 1); // 信号量初始化
}
for (int i = 0; i < N; i++) {
if (fork() == 0) {
philosopher(i, forks);// 五个子进程用于模拟五个哲学家
}
}
while (1)
;
for (int i = 0; i < N; i++) {
sem_destroy(forks + i); // 回收信号量
}
return 0;
}
框架的问题
我们如果用目前的框架运行上面的模拟程序，其实是行不通的：只能看到只有2个哲学家在吃饭和思考，那么原因大概是框架无法fork出多个进程。在使用自己写的程序对fork进行测试后，发现确实无法产生3个以上进程。
我们追溯到syscallFork，发现进程生成数量收到MAX_PCB_NUM的限制，此时它的值是4，算上父进程，这正解释上述现象发生的原因，我们将其扩大到10，这样就不会对我们的程序造成影响。
受此启发，我检查了MAX_SEM_NUM，发现它的值设置为4，也就是说框架只允许4个信号量发挥作用，而我们的哲学家问题需要5个信号量，于是我们将其扩展至5。
这大概就是手册中所说的”不要盲目相信框架代码，框架代码只在有限范围内正确“。
这时我们运行模拟程序，就可以看到哲学家们正在思考和进食：
至此我们完成了全部实验内容。
总结
这次实验是对课堂上信号量与PV操作的一次复习和实践，让我加深了对知识点的理解；此外，发现框架的问题、寻找原因、到最后解决问题的流程让我收获良多。
以上是南京大学2021操作系统实验的内容。
