04月04, 2019

清华大学uCore OS实验

项目地址:https://github.com/Bocity/uCore-OS

本项目源于脑子一抽在操作系统课上自告奋勇的要求选修清华的uCoreOS课,也直接导致了我大三上学期最后几周睡眠严重不足。不过学习到了比较多的知识,感觉付出还是很有收获!:)

实验ZERO

实验目的

  • 了解操作系统开发实验环境
  • 熟悉命令行方式的编译、调试工程
  • 掌握基于硬件模拟器的调试技术
  • 熟悉C语言编程和指针的概念
  • 了解X86汇编语言

实验过程

使用gcc

参考资料: https://gcc.gnu.org/onlinedocs/gcc.pdf

内联汇编的使用

Ucore中用到的是AT&T格式的汇编,与Intel格式在寄存器名命名原则、源/目的操作数顺序、常数立即数的格式、操作数长度标识、寻址方式等方面存在不同。

例如,在寄存器前需要加%,立即数需要加_,源/目的操作数倒置,直接寻址则直接使用变量名,寄存器间接寻址加小括号等

寻址写做:immed32(basepointer,indexpointer,indexscale)

gcc提供了两种内联汇编语句: 1、基本内联汇编语句 2、扩展内联汇编语句

基本内联汇编语句

格式为:

        asm(“statements”);

多行语句每一行需要加上“\n\t”,这是为了让gcc将汇编代码翻译成一般的汇编代码时保证换行和留有一定的空格 例如:

    asm( "pushl %eax\n\t"
          "movl $0,%eax\n\t"
          "popl %eax"
    );
扩展内联汇编语句

格式如下

asm [volatile] ( Assembler Template
   : Output Operands
   [ : Input Operands
   [ : Clobbers ] ])

例子:

#define read_cr0() ({ \
    unsigned int __dummy; \
    __asm__( \
        "movl %%cr0,%0\n\t" \
        :"=r" (__dummy)); \
    __dummy; \
})

其中,asm 表示汇编代码的开始,"movl %%cr0,%0\n\t"。数字前加前缀 “%“,如%1,%2等表示使用寄存器的样板操作数。可以使用的操作数总数取决于具体CPU中通用寄存器的数 量,如Intel可以有8个。由于这些样板操作数的前缀使用了”%“,因此,在用到具体的寄存器时就在前面加两个“%”,如%%cr0。输出部分(output operand list),用以规定对输出变量(目标操作数)如何与寄存器结合的约束(constraint),输出部分可以有多个约束,互相以逗号分开。每个约束以“=”开头,接着用一个字母来表示操作数的类型,然后是关于变量结合的约束。

输出部分: “=r”表示相应的目标操作数(指令部分的%0)可以使用任何一个通用寄存器,并且变量__dummy 存放在这个寄存器中。

输入部分: 输入部分与输出部分相似,但没有“=”。如果输入部分一个操作数所要求使用的寄存器,与前面输出部分某个约束所要求的是同一个寄存器,那就把对应操作数的编号(如“1”,“2”等)放在约束条件中。

修改部分: 这部分常常以“memory”为约束条件,以表示操作完成后内存中的内容已有改变,如果原来某个寄存器的内容来自内存,那么现在内存中这个单元的内容已经改变。

gcc -Wall

-Wall 选项用于开启编译器常用警告

gcc -S

gcc编译上述程序后,生成.s文件,使用cat命令查看,发现,-S选项的作用是将高级语言转化为汇编语言

使用gdb

gdb 是功能强大的调试程序,可完成如下的调试任务:

  • 设置断点
  • 监视程序变量的值
  • 程序的单步(step in/step over)执行
  • 显示/修改变量的值
  • 显示/修改寄存器
  • 查看程序的堆栈情况
  • 远程调试
  • 调试线程 在可以使用 gdb 调试程序之前,必须使用 -g 或 –ggdb编译选项编译源文件。运行 gdb 调试程序时通常使用如下的命令:
gdb progname

在 gdb 提示符处键入help,将列出命令的分类,主要的分类有:

  • aliases:命令别名
  • breakpoints:断点定义;
  • data:数据查看;
  • files:指定并查看文件;
  • internals:维护命令;
  • running:程序执行;
  • stack:调用栈查看;
  • status:状态查看;
  • tracepoints:跟踪程序执行。

用gdb调试lab1

直接运行出现segment fault gdb进入run后,用where定位并list出源码 在11行设置breakpoint,重新运行,发现程序无错误 然后查看第十一行,分析后得知,程序是在循环赋值,所以D应该放buf 修改后运行正常

使用makefile

GNU make(简称make)是一种代码维护工具,在大中型项目中,它将根据程序各个模块的更新情况,自动的维护和生成目标代码。

make命令执行时,需要一个 makefile (或Makefile)文件,以告诉make命令需要怎么样的去编译和链接程序

  • 如果这个工程没有编译过,那么我们的所有c文件都要编译并被链接。
  • 如果这个工程的某几个c文件被修改,那么我们只编译被修改的c文件,并链接目标程序。
  • 如果这个工程的头文件被改变了,那么我们需要编译引用了这几个头文件的c文件,并链接目标程序。

只要我们的makefile写得够好,所有的这一切,我们只用一个make命令就可以完成,make命令会自动智能地根据当前的文件修改的情况来确定哪些文件需要重编译,从而自己编译所需要的文件和链接目标程序。

makefile的规则:

target ... : prerequisites ...
    command
    ...
    ...

target也就是一个目标文件,可以是object file,也可以是执行文件。还可以是一个标签(label)。prerequisites就是,要生成那个target所需要的文件或是目标。command也就是make需要执行的命令(任意的shell命令)。 这是一个文件的依赖关系,也就是说,target这一个或多个的目标文件依赖于prerequisites中的文件,其生成规则定义在 command中。如果prerequisites中有一个以上的文件比target文件要新,那么command所定义的命令就会被执行。这就是makefile的规则。也就是makefile中最核心的内容。

使用qemu

QEMU用于模拟一台x86计算机,让ucore能够运行在QEMU上。

格式如:

qemu [options] [disk_image]

其中 disk_image 即硬盘镜像文件。

`-hda file'        `-hdb file' `-hdc file' `-hdd file'
使用 file  作为硬盘0、1、2、3镜像。
`-fda file'  `-fdb file'
使用 file  作为软盘镜像,可以使用 /dev/fd0 作为 file 来使用主机软盘。
`-cdrom file'
使用 file  作为光盘镜像,可以使用 /dev/cdrom 作为 file 来使用主机 cd-rom。
`-boot [a|c|d]'
从软盘(a)、光盘(c)、硬盘启动(d),默认硬盘启动。
`-snapshot'
写入临时文件而不写回磁盘镜像,可以使用 C-a s 来强制写回。
`-m megs'
设置虚拟内存为 msg M字节,默认为 128M 字节。
`-smp n'
设置为有 n 个 CPU 的 SMP 系统。以 PC 为目标机,最多支持 255 个 CPU。
`-nographic'
禁止使用图形输出。
其他:
可用的主机设备 dev 例如:
vc
    虚拟终端。
null
    空设备
/dev/XXX
    使用主机的 tty。
file: filename
    将输出写入到文件 filename 中。
stdio
    标准输入/输出。
pipe:pipename
    命令管道 pipename。
等。
使用 dev 设备的命令如:
`-serial dev'
    重定向虚拟串口到主机设备 dev 中。
`-parallel dev'
    重定向虚拟并口到主机设备 dev 中。
`-monitor dev'
    重定向 monitor 到主机设备 dev 中。
其他参数:
`-s'
    等待 gdb 连接到端口 1234。
`-p port'
    改变 gdb 连接端口到 port。
`-S'
    在启动时不启动 CPU, 需要在 monitor 中输入 'c',才能让qemu继续模拟工作。
`-d'
    输出日志到 qemu.log 文件。

qemu和gdb模拟运行lab1,并分析memset设置断点

掌握指针和类型转化相关的C编程

修改lab0_ex3.c。使其可正常运行 运行命令

gcc -g -m32 lab0_ex3.c 2>&1|tee make.log

得到以下错误:

lab0_ex3.c: In function 'main':
lab0_ex3.c:48:5: warning: format '%llx' expects argument of type 'long long unsigned int', but argument 2 has type 'struct gatedesc' [-Wformat=]
     printf("gintr is 0x%llx\n",gintr);
     ^

发现gintr是个struct,题目的意思应该是输出对应地址,删掉本句即可

掌握通用链表结构相关的C编程

数据结构课已练习,故略过

实验一

实验目的

操作系统是一个软件,也需要通过某种机制加载并运行它。在这里我们将通过另外一个更加简单的软件-bootloader来完成这些工作。为此,我们需要完成一个能够切换到x86的保护模式并显示字符的bootloader,为启动操作系统ucore做准备。lab1提供了一个非常小的bootloader和ucore OS,整个bootloader执行代码小于512个字节,这样才能放到硬盘的主引导扇区中。通过分析和实现这个bootloader和ucore OS,我们的目的在于了解到:

计算机原理

  • CPU的编址与寻址: 基于分段机制的内存管理
  • CPU的中断机制
  • 外设:串口/并口/CGA,时钟,硬盘

Bootloader软件

  • 编译运行bootloader的过程
  • 调试bootloader的方法
  • PC启动bootloader的过程
  • ELF执行文件的格式和加载
  • 外设访问:读硬盘,在CGA上显示字符串

ucore OS软件

  • 编译运行ucore OS的过程
  • ucore OS的启动过程
  • 调试ucore OS的方法
  • 函数调用关系:在汇编级了解函数调用栈的结构和处理过程
  • 中断管理:与软件相关的中断处理
  • 外设管理:时钟

实验步骤

练习1 理解通过make生成执行文件的过程。

要解决的问题:

  • 操作系统镜像文件ucore.img是如何一步一步生成的?(需要比较详细地解释Makefile中每一条相关命令和命令参数的含义,以及说明命令导致的结果)
  • 一个被系统认为是符合规范的硬盘主引导扇区的特征是什么?

在lab1下执行make

生成 bin文件夹和 obj文件夹

ucore.img

打开Makefile,首先找到生成ucore.img的位置:

# create ucore.img
UCOREIMG    := $(call totarget,ucore.img)

$(UCOREIMG): $(kernel) $(bootblock)
    $(V)dd if=/dev/zero of=$@ count=10000
    $(V)dd if=$(bootblock) of=$@ conv=notrunc
    $(V)dd if=$(kernel) of=$@ seek=1 conv=notrunc

$(call create_target,ucore.img)

# 为注释,第一句定义了变量UCOREIMG 调用了call函数,将ucore.img传入totarget表达式得到。 然后开始定义UCOREIMG的生成依赖,UCOREIMG依赖于两个文件一个是kernel,一个是bootblock。

接着下面给出了链接两个文件的方式,使用了dd命令,从标准输入到标准输出拷贝一个文件并有规律的转化

  • $@表示规则中的目标文件集。
  • ‘if=file’ 代表用文件输入代替标准输入
  • ‘of=file’ 代表用文件输出代替标准输出,除非设置‘conv=notrunc’ 否则dd会进行0字节截断,或者按照‘seek=’的大小
  • ‘count=n’ 代表从输入文件中拷贝n个大小为ibs byte的块
  • ‘ibs=bytes’ 设置输入块大小,默认为512字节,这会确定dd从每块读多少字节
  • ‘conv=conversion[,conversion]…’ 将文件按照指定参数转化,其中notrunc为:不截断输出文件,
  • ‘seek=n’ 在拷贝前输出文件时跳过n 个‘obs’-byte的块。
  • ‘obs=bytes’ 设置输出块大小,默认为512字节,这会确定dd从每块写多少字节
  • 更多内容:https://www.gnu.org/software/coreutils/manual/html_node/dd-invocation.html

解释一下为,首先从/dev/zero中读了10000*512块的空字节,然后生成空文件,接着将bootblock中的内容拷贝到目标文件,然后从输出文件的512字节后继续写入kernel的内容

最后调用call函数使用了create_target表达式

kernel

# create kernel target
kernel = $(call totarget,kernel)

$(kernel): tools/kernel.ld

$(kernel): $(KOBJS)
    @echo + ld $@
    $(V)$(LD) $(LDFLAGS) -T tools/kernel.ld -o $@ $(KOBJS)
    @$(OBJDUMP) -S $@ > $(call asmfile,kernel)
    @$(OBJDUMP) -t $@ | $(SED) '1,/SYMBOL TABLE/d; s/ .* / /; /^$$/d' > $(call symfile,kernel)

$(call create_target,kernel)

kernel的生成依赖于KOBJS和tools/kernel.ld,生成命令依赖于 i386-elf-objdump 、ld和objdump等。

使用

make "V=" > 1.txt 

查看链接详情 可以看到其依赖的所有文件 单个文件编译gcc命令如下:

gcc -Iboot/ -fno-builtin -Wall -ggdb -m32 -gstabs -nostdinc  -fno-stack-protector -Ilibs/ -Os -nostdinc -c boot/bootasm.S -o obj/boot/bootasm.o

参数解释为:

  • -Iboot/-Ilibs/:找名为boot/的头文件目录
  • fno-builtin :不使用C语言的内建函数
  • -Wall:开启编译警告
  • -ggdb:产生 GDB 所需的调试信息。这意味着将会使用可用的、最具表达力的格式(DWARF 2 、stabs ,或者在前两者不支持情况下的其他本地格式),如果可能的话还会包含 GDB 扩展信息。
  • -m32:生成32位机器的汇编代码;
  • -gstabs:此选项以stabs格式声称调试信息,但是不包括gdb调试信息.
  • -nostdinc:不要在标准系统目录中寻找头文件.只搜索-I'选项指定的目录(以及当前目录,如果合适).结合使用-nostdinc'和`-I-'选项,你可以把包含文件搜索限制在显式指定的目录.
  • -fno-stack-protector禁用栈保护措施
  • -Os:相当于-O2.5。是使用了所有-O2的优化选项,但又不缩减代码尺寸的方法。
  • -c:表示只编译源文件但不链接

bootblock

# create bootblock
bootfiles = $(call listf_cc,boot)
$(foreach f,$(bootfiles),$(call cc_compile,$(f),$(CC),$(CFLAGS) -Os -nostdinc))

bootblock = $(call totarget,bootblock)

$(bootblock): $(call toobj,$(bootfiles)) | $(call totarget,sign)
    @echo + ld $@
    $(V)$(LD) $(LDFLAGS) -N -e start -Ttext 0x7C00 $^ -o $(call toobj,bootblock)
    @$(OBJDUMP) -S $(call objfile,bootblock) > $(call asmfile,bootblock)
    @$(OBJCOPY) -S -O binary $(call objfile,bootblock) $(call outfile,bootblock)
    @$(call totarget,sign) $(call outfile,bootblock) $(bootblock)

$(call create_target,bootblock)

bootblock 依赖于bootasm.o、bootmain.o、sign 生成bootblock的编译指令为:

ld -m    elf_i386 -nostdlib -N -e start -Ttext 0x7C00 obj/boot/bootasm.o obj/boot/bootmain.o -o obj/bootblock.o

其中关键的参数为

  • -m 模拟为i386上的连接器
  • -nostdlib 不使用标准库
  • -N 设置代码段和数据段均可读写
  • -e 指定入口
  • -Ttext 制定代码段开始位置
  • -fno-builtin:除非用__builtin_前缀,否则不进行builtin函数的优化

最后拷贝二进制代码bootblock.o到bootblock.out,用使用sign工具处理bootblock.out,生成bootblock

objcopy -S -O binary obj/bootblock.o obj/bootblock.out

其中关键的参数为:

  • -S 移除所有符号和重定位信息
  • -O 指定输出格式

一个被系统认为是符合规范的硬盘主引导扇区的特征是什么?

从sign.c的代码来看,一个磁盘主引导扇区只有512字节。且第510个(倒数第二个)字节是0x55,第511个(倒数第一个)字节是0xAA。

练习2

进行如下练习

  • 从CPU加电后执行的第一条指令开始,单步跟踪BIOS的执行。
  • 在初始化位置0x7c00设置实地址断点,测试断点正常。
  • 从0x7c00开始跟踪代码运行,将单步跟踪反汇编得到的代码与bootasm.S和 bootblock.asm进行比较。
  • 自己找一个bootloader或内核中的代码位置,设置断点并进行测试。

1 修改 lab1/tools/gdbinit,内容为:

set architecture i8086
target remote :1234
define hook-stop
x/i $pc
end

命令行运行make debug,可以进行调试

可以发现启动后第一条指令地址:

要用到的gdb指令

(gdb) i r
(gdb) i r a                     # 查看所有寄存器(包括浮点、多媒体)
(gdb) i r esp
(gdb) i r pc
(gdb) x /wx 0x80040000    # 以16进制显示指定地址处的数据
(gdb) x /8x $esp
(gdb) x /16x $esp+12
(gdb) x /16s 0x86468700   # 以字符串形式显示指定地址处的数据
(gdb) x /24i 0x8048a51      # 以指令形式显示指定地址处的数据(24条)
(gdb) b *0x80400000 #断点
(gdb) watch *(unsigned int *)0xbffff400==0x90909090 #监测点

EIP 的内容为: 0xF000 CS 的内容为: 0xFFF0H

所以第一条指令地址: F000*16 + FFF0H = FFFF0H

可以看到,第一条指令为无条件跳转,跳转到F000*16+E05B = FE05B处继续执行BIOS

在tools/下的gdbinit 中添加下列语句

b *0x7c00 #在0x7c00打断点
continue    #继续执行代码
x /10i $pc    #查看当前要执行的十个代码

重新运行make debug 后,在0x7c00处中断,并显示附近指令 vim打开bootasm.S 用/查找 可以发现,bootloader此处反汇编出的代码与bootasm.S处的代码相同

通过gdb下si指令,可以单步执行该代码

练习3

定义一个全局名字start
.globl start
start:
CPU刚启动为16位模式
  .code16                     # Assemble for 16-bit mode
关中断
  cli                         # Disable interrupts
清方向标志
  cld                         # String operations increment

  # Set up the important data segment registers (DS, ES, SS).
设置重要的数据段寄存器
ax清零
  xorw    %ax,%ax             # Segment number zero
ds清零
  movw    %ax,%ds             # -> Data Segment
es清零
  movw    %ax,%es             # -> Extra Segment
ss清零
  movw    %ax,%ss             # -> Stack Segment


  • 首先进行初始化操作,关中断并且将段寄存器置零
  • cli中断标志置0,cld方向标志位置0
  # Enable A20:
  #   For backwards compatibility with the earliest PCs, physical
  #   address line 20 is tied low, so that addresses higher than
  #   1MB wrap around to zero by default.  This code undoes this.
  开启A20地址线之后,用来表示内存地址的位数变多了。开启前20位,开启后是32位。如果不开启A20地址线内存寻址最大只能找到1M,对于1M以上的地址访问会变成对address mod 1M地址的访问。通过将键盘控制器上的A20线置于高电位,全部32条地址线可用,可以访问4G的内存空间。
打开A20地址线
为了兼容早期的PC机,第20根地址线在实模式下不能使用
所以超过1MB的地址,默认就会返回到地址0,重新从0循环计数,
下面的代码打开A20地址线

seta20.1:
从0x64端口读入一个字节的数据到al中
  inb     $0x64,%al               # Wait for not busy
test指令可以当作and指令,只不过它不会影响操作数
  testb   $0x2,%al
如果上面的测试中发现al的第2位为0,就不执行该指令
否则就循环检查
  jnz     seta20.10xd1写入到al中
  movb    $0xd1,%al               # 0xd1 -> port 0x64
将al中的数据写入到端口0x64中
  outb    %al,$0x64

seta20.2:
从0x64端口读取一个字节的数据到al中
  inb     $0x64,%al               # Wait for not busy
测试al的第2位是否为0
  testb   $0x2,%al
如果上面的测试中发现al的第2位为0,就不执行该指令
否则就循环检查
  jnz     seta20.20xdf写入到al中
  movb    $0xdf,%al               # 0xdf -> port 0x60
将al中的数据写入到0x60端口中
  outb    %al,$0x60

  • inb 从I/O端口读取一个字节(BYTE, HALF-WORD) ;
  • outb 向I/O端口写入一个字节(BYTE, HALF-WORD) ;
将全局描述符表描述符加载到全局描述符表寄存器
  lgdt    gdtdesc

加载全局描述符寄存器gdtr,通过lgdt指令将全局描述符入口地址装入gdtr寄存器中

cr0中的第0位为1表示处于保护模式
cr0中的第0位为0,表示处于实模式
把控制寄存器cr0加载到eax中
  movl    %cr0, %eax
将eax中的第0位设置为1
  orl     $CR0_PE_ON, %eax
将eax中的值装入cr0中
  movl    %eax, %cr0

进入保护模式,将CR0寄存器最低位PE置1 可以看到进入保护模式一共进行了四个步骤

  1. 初始化操作
  2. 开启A20
  3. 加载gdt
  4. CR0寄存器最低位PE置1
跳转到32位模式中的下一条指令
将处理器切换为32位工作模式
下面这条指令执行的结果会将$PROT_MODE_CSEG加载到cs中,cs对应的高速缓冲存储器会加载代码段描述符
同样将$protcseg加载到ip中
  ljmp    $PROT_MODE_CSEG, $protcseg

长跳转指令ljmp \$PROT_MODE_CSEG, \$protcseg跳转到下一条代码,目的是跳过剩余的16位指令。此处新的GDT已经发挥作用,seg= PROT_MODE_CSEG, offset=protcseg,因为CSEG的基地址为0,则程序跳转到了代码段的protcseg偏移处

  .code32                     # Assemble for 32-bit mode
protcseg:
  # Set up the protected-mode data segment registers
设置保护模式下的数据寄存器
将数据段选择子装入到ax中
  movw    $PROT_MODE_DSEG, %ax    # Our data segment selector
将ax装入到其他数据段寄存器中,在装入的同时,
数据段描述符会自动的加入到这些段寄存器对应的高速缓冲寄存器中
  movw    %ax, %ds                # -> DS: Data Segment
  movw    %ax, %es                # -> ES: Extra Segment
  movw    %ax, %fs                # -> FS
  movw    %ax, %gs                # -> GS
  movw    %ax, %ss                # -> SS: Stack Segment

  # Set up the stack pointer and call into C.
设置栈指针,并且调用c函数
  movl    $start, %esp
调用main.c中的bootmain函数
  call bootmain

  # If bootmain returns (it shouldn't), loop.
如果bootmain返回的话,就一直循环
spin:
  jmp spin

设置段寄存器,并建立堆栈,进入boot主方法

练习4

通过阅读bootmain.c,了解bootloader如何加载ELF文件。通过分析源代码和通过qemu来运行并调试bootloader&OS bootloader如何读取硬盘扇区的? bootloader是如何加载ELF格式的OS

使用gdb+qemu追踪bootmain

在练习3的最后可以看到,进入保护模式后,就调用了bootmain,我们使用gdb+qemu追踪这个过程 首先 bootmain.c源码如下:

#include <defs.h>
#include <x86.h>
#include <elf.h>

/* *********************************************************************
 * This a dirt simple boot loader, whose sole job is to boot
 * an ELF kernel image from the first IDE hard disk.
 *
 * DISK LAYOUT
 *  * This program(bootasm.S and bootmain.c) is the bootloader.
 *    It should be stored in the first sector of the disk.
 *
 *  * The 2nd sector onward holds the kernel image.
 *
 *  * The kernel image must be in ELF format.
 *
 * BOOT UP STEPS
 *  * when the CPU boots it loads the BIOS into memory and executes it
 *
 *  * the BIOS intializes devices, sets of the interrupt routines, and
 *    reads the first sector of the boot device(e.g., hard-drive)
 *    into memory and jumps to it.
 *
 *  * Assuming this boot loader is stored in the first sector of the
 *    hard-drive, this code takes over...
 *
 *  * control starts in bootasm.S -- which sets up protected mode,
 *    and a stack so C code then run, then calls bootmain()
 *
 *  * bootmain() in this file takes over, reads in the kernel and jumps to it.
 * */

#define SECTSIZE        512
#define ELFHDR          ((struct elfhdr *)0x10000)      // scratch space

/* waitdisk - wait for disk ready */
static void
waitdisk(void) {
    while ((inb(0x1F7) & 0xC0) != 0x40)
        /* do nothing */;
}

/* readsect - read a single sector at @secno into @dst */
static void
readsect(void *dst, uint32_t secno) {
    // wait for disk to be ready
    waitdisk();

    outb(0x1F2, 1);                         // count = 1
    outb(0x1F3, secno & 0xFF);
    outb(0x1F4, (secno >> 8) & 0xFF);
    outb(0x1F5, (secno >> 16) & 0xFF);
    outb(0x1F6, ((secno >> 24) & 0xF) | 0xE0);
    outb(0x1F7, 0x20);                      // cmd 0x20 - read sectors

    // wait for disk to be ready
    waitdisk();

    // read a sector
    insl(0x1F0, dst, SECTSIZE / 4);
}

/* *
 * readseg - read @count bytes at @offset from kernel into virtual address @va,
 * might copy more than asked.
 * */
static void
readseg(uintptr_t va, uint32_t count, uint32_t offset) {
    uintptr_t end_va = va + count;

    // round down to sector boundary
    va -= offset % SECTSIZE;

    // translate from bytes to sectors; kernel starts at sector 1
    uint32_t secno = (offset / SECTSIZE) + 1;

    // If this is too slow, we could read lots of sectors at a time.
    // We'd write more to memory than asked, but it doesn't matter --
    // we load in increasing order.
    for (; va < end_va; va += SECTSIZE, secno ++) {
        readsect((void *)va, secno);
    }
}

/* bootmain - the entry of bootloader */
void
bootmain(void) {
    // read the 1st page off disk
    readseg((uintptr_t)ELFHDR, SECTSIZE * 8, 0);

    // is this a valid ELF?
    if (ELFHDR->e_magic != ELF_MAGIC) {
        goto bad;
    }

    struct proghdr *ph, *eph;

    // load each program segment (ignores ph flags)
    ph = (struct proghdr *)((uintptr_t)ELFHDR + ELFHDR->e_phoff);
    eph = ph + ELFHDR->e_phnum;
    for (; ph < eph; ph ++) {
        readseg(ph->p_va & 0xFFFFFF, ph->p_memsz, ph->p_offset);
    }

    // call the entry point from the ELF header
    // note: does not return
    ((void (*)(void))(ELFHDR->e_entry & 0xFFFFFF))();

bad:
    outw(0x8A00, 0x8A00);
    outw(0x8A00, 0x8E00);

    /* do nothing */
    while (1);
}

操作学习: gdb layout

  • layout regs
  • layout asm
  • ctrl+l 刷新窗口
  • winheight name +/-line 调整窗口大小
  • ctrl+x+(1/2/a)切换窗口模式
  • layout src:显示源代码窗口
  • layout split:显示源代码和汇编窗口

通过si单步追踪,进入bootmain,地址0x7c70 最后程序在

0x7ccc 处进入死循环,即bootmain中的

    while (1);

readsect函数

用于加载一个扇区的内容到指定的内存中,读取的过程大致为:(1)等待磁盘准备好;(2)发出读取扇区的命令,通过访问IO地址寄存器0x1f0~0x1f7实现;(3)等待磁盘准备好;(4)把磁盘扇区读取到指定内存中。

static void
    readsect(void *dst, uint32_t secno) {
        waitdisk();

        outb(0x1F2, 1);                         // 设置读取扇区的数目为1
        outb(0x1F3, secno & 0xFF);
        outb(0x1F4, (secno >> 8) & 0xFF);
        outb(0x1F5, (secno >> 16) & 0xFF);
        outb(0x1F6, ((secno >> 24) & 0xF) | 0xE0);
            // 上面四条指令联合制定了扇区号
            // 在这4个字节线联合构成的32位参数中
            //   29-31位强制设为1
            //   28位(=0)表示访问"Disk 0"
            //   0-27位是28位的偏移量
        outb(0x1F7, 0x20);                      // 0x20命令,读取扇区

        waitdisk();

        insl(0x1F0, dst, SECTSIZE / 4);         // 读取到dst位置,
                                                // 幻数4因为这里以DW为单位
    }

readseg函数

这个函数的作用是从ELF文件偏移为offset处,读取count个字节到内存地址为va处

static void
    readseg(uintptr_t va, uint32_t count, uint32_t offset) {
        uintptr_t end_va = va + count;

        va -= offset % SECTSIZE;

        uint32_t secno = (offset / SECTSIZE) + 1; 
        // 加1因为0扇区被引导占用
        // ELF文件从1扇区开始

        for (; va < end_va; va += SECTSIZE, secno ++) {
            readsect((void *)va, secno);
        }
    }

bootmain函数

首先将硬盘上从第一个扇区开始的4096个字节读到内存中地址为0x10000处,然后检查ELF文件是否合法,并找到程序段的起始地址,读取内核程序到内存中,最后执行内核程序

void bootmain(void) {
        // 首先读取ELF的头部
        readseg((uintptr_t)ELFHDR, SECTSIZE * 8, 0);

        // 通过储存在头部的幻数判断是否是合法的ELF文件
        if (ELFHDR->e_magic != ELF_MAGIC) {
            goto bad;
        }

        struct proghdr *ph, *eph;

        // ELF头部有描述ELF文件应加载到内存什么位置的描述表,
        // 先将描述表的头地址存在ph
        ph = (struct proghdr *)((uintptr_t)ELFHDR + ELFHDR->e_phoff);
        eph = ph + ELFHDR->e_phnum;

        // 按照描述表将ELF文件中数据载入内存
        for (; ph < eph; ph ++) {
            readseg(ph->p_va & 0xFFFFFF, ph->p_memsz, ph->p_offset);
        }
        // ELF文件0x1000位置后面的0xd1ec比特被载入内存0x00100000
        // ELF文件0xf000位置后面的0x1d20比特被载入内存0x0010e000

        // 根据ELF头部储存的入口信息,找到内核的入口
        ((void (*)(void))(ELFHDR->e_entry & 0xFFFFFF))();

    bad:
        outw(0x8A00, 0x8A00);
        outw(0x8A00, 0x8E00);
        while (1);
    }

练习5 实现函数调用堆栈跟踪函数

第五题为实现函数调用堆栈函数,需补全kern/debug/kdebug.c中的print_stackframe()函数。 有提示,所以编码比较简单

  • step1 获取ebp的值 以十六进制形式输出
  • step2 获取eip的值 以十六进制形式输出
  • step3 遍历栈depth 输出参数
  • step4 输出debug 信息
  • 获得上一个 ebp
/*
栈底方向      高位地址
...          
...          
参数3        
参数2        
参数1        
返回地址     
上一层[ebp]   <-------- [esp/当前ebp]
局部变量      低位地址
ss:[ebp-8]   ;变量2
ss:[ebp-4]   ;变量1
ss:[ebp]       ;栈针
ss:[ebp+4]  ;返回地址
ss:[ebp+8]   ;第一个参数
*/

    uint32_t ebp = read_ebp();
    uint32_t eip = read_eip();
    int i;
    for(i = 0; i < STACKFRAME_DEPTH ; ++i) {
        cprintf("The value of ebp:0x%08x eip:0x%08x", ebp, eip);
        uint32_t *arg = (uint32_t *)ebp + 2;
        cprintf(" arg:");
        int j;
        for(j = 0; j < 4; ++j) {
            cprintf("0x%08x  ", arg + j);
        }
        cputs("");
        print_debuginfo(eip - 1);
        eip = ((uint32_t *)ebp)[1];
        ebp = ((uint32_t*)ebp)[0];
    } 

这里好奇为什么不能使用printf

查看stdio.c后得知只有如下实现: cputch cprintf cputchar cputs getchar

在得到实验结果时,实验楼遇上了问题,此步make debug 会卡死虚拟环境

于是考虑再三,选择迁移实验环境到本地的Ubuntu 通过以下三条命令配置实验环境:

sudo apt-get install build-essential
sudo apt-get install livsdl1.2-dev
sudo apt-get install qemu-system

结果


Special kernel symbols:
  entry  0x00100000 (phys)
  etext  0x0010328a (phys)
  edata  0x0010ea16 (phys)
  end    0x0010fd20 (phys)
Kernel executable memory footprint: 64KB
The value of ebp:0x00007b38 eip:0x00100a3c arg:0x00007b40  0x00007b44  0x00007b48  0x00007b4c  
    kern/debug/kdebug.c:306: print_stackframe+21
The value of ebp:0x00007b48 eip:0x00100d4a arg:0x00007b50  0x00007b54  0x00007b58  0x00007b5c  
    kern/debug/kmonitor.c:125: mon_backtrace+10
The value of ebp:0x00007b68 eip:0x0010007f arg:0x00007b70  0x00007b74  0x00007b78  0x00007b7c  
    kern/init/init.c:48: grade_backtrace2+19
The value of ebp:0x00007b88 eip:0x001000a1 arg:0x00007b90  0x00007b94  0x00007b98  0x00007b9c  
    kern/init/init.c:53: grade_backtrace1+27
The value of ebp:0x00007ba8 eip:0x001000be arg:0x00007bb0  0x00007bb4  0x00007bb8  0x00007bbc  
    kern/init/init.c:58: grade_backtrace0+19
The value of ebp:0x00007bc8 eip:0x001000df arg:0x00007bd0  0x00007bd4  0x00007bd8  0x00007bdc  
    kern/init/init.c:63: grade_backtrace+26
The value of ebp:0x00007be8 eip:0x00100050 arg:0x00007bf0  0x00007bf4  0x00007bf8  0x00007bfc  
    kern/init/init.c:28: kern_init+79
The value of ebp:0x00007bf8 eip:0x00007d6e arg:0x00007c00  0x00007c04  0x00007c08  0x00007c0c  
    <unknow>: -- 0x00007d6d --
++ setup timer interrupts
(THU.CST) os is loading ...

Special kernel symbols:
  entry  0x00100000 (phys)
  etext  0x0010328a (phys)
  edata  0x0010ea16 (phys)
  end    0x0010fd20 (phys)
Kernel executable memory footprint: 64KB
The value of ebp:0x00007b38 eip:0x00100a3c arg:0x00007b40  0x00007b44  0x00007b48  0x00007b4c  
    kern/debug/kdebug.c:306: print_stackframe+21
The value of ebp:0x00007b48 eip:0x00100d4a arg:0x00007b50  0x00007b54  0x00007b58  0x00007b5c  
    kern/debug/kmonitor.c:125: mon_backtrace+10
The value of ebp:0x00007b68 eip:0x0010007f arg:0x00007b70  0x00007b74  0x00007b78  0x00007b7c  
    kern/init/init.c:48: grade_backtrace2+19
The value of ebp:0x00007b88 eip:0x001000a1 arg:0x00007b90  0x00007b94  0x00007b98  0x00007b9c  
    kern/init/init.c:53: grade_backtrace1+27
The value of ebp:0x00007ba8 eip:0x001000be arg:0x00007bb0  0x00007bb4  0x00007bb8  0x00007bbc  
    kern/init/init.c:58: grade_backtrace0+19
The value of ebp:0x00007bc8 eip:0x001000df arg:0x00007bd0  0x00007bd4  0x00007bd8  0x00007bdc  
    kern/init/init.c:63: grade_backtrace+26
The value of ebp:0x00007be8 eip:0x00100050 arg:0x00007bf0  0x00007bf4  0x00007bf8  0x00007bfc  
    kern/init/init.c:28: kern_init+79
The value of ebp:0x00007bf8 eip:0x00007d6e arg:0x00007c00  0x00007c04  0x00007c08  0x00007c0c  
    <unknow>: -- 0x00007d6d --
++ setup timer interrupts

最后一行输出的ebp为0x00007bf8,eip为0x00007d68,这时因为bootloader被加载到了0x00007c00地址处,在执行到bootasm最后"call bootmain"指令时,首先将返回地址压栈,再讲当前ebp压栈,所以此时esp为0x00007bf8。在bootmain函数入口处,有mov %esp %ebp指令,故bootmain中ebp为0x00007bf8。

练习6

  • 中断描述符表(也可简称为保护模式下的中断向量表)中一个表项占多少字节?其中哪几位代表中断处理代码的入口?

    IDT是一个8字节的描述符数组,但IDT的第一项可以包含一个描述符

    前16位为段偏移值 接着16位为段选择子 然后5位3位4位1位2位1位表示各种状态 最后又16位段偏移值

    所以从中可以看出,中断处理代码的入口为第一字节和最后一个字节组成的地址。

  • 请编程完善kern/trap/trap.c中对中断向量表进行初始化的函数idt_init。在idt_init函数中,依次对所有中断入口进行初始化。使用mmu.h中的SETGATE宏,填充idt数组内容。每个中断的入口由tools/vectors.c生成,使用trap.c中声明的vectors数组即可。

     /* LAB1 YOUR CODE : STEP 2 */
     /* (1) Where are the entry addrs of each Interrupt Service Routine (ISR)?
      *     All ISR's entry addrs are stored in __vectors. where is uintptr_t __vectors[] ?
      *     __vectors[] is in kern/trap/vector.S which is produced by tools/vector.c
      *     (try "make" command in lab1, then you will find vector.S in kern/trap DIR)
      *     You can use  "extern uintptr_t __vectors[];" to define this extern variable which will be used later.
      * (2) Now you should setup the entries of ISR in Interrupt Description Table (IDT).
      *     Can you see idt[256] in this file? Yes, it's IDT! you can use SETGATE macro to setup each item of IDT
      * (3) After setup the contents of IDT, you will let CPU know where is the IDT by using 'lidt' instruction.
      *     You don't know the meaning of this instruction? just google it! and check the libs/x86.h to know more.
      *     Notice: the argument of lidt is idt_pd. try to find it!
      */

SETGATE(gate, istrap, sel, off, dpl)

 extern uintptr_t __vectors[];
    int i;
    for(i = 0;  i < 256; ++i){
        SETGATE(idt[i],0,GD_KTEXT,__vectors[i],DPL_KERNEL);
    }   
    SETGATE(idt[T_SWITCH_TOK],0,GD_KTEXT,__vectors[T_SWITCH_TOK],DPL_USER);

    lidt(&idt_pd); 
/*

    传入的第一个参数gate是中断的描述符表
    传入的第二个参数istrap用来判断是中断还是trap
    传入的第三个参数sel的作用是进行段的选择
    传入的第四个参数off表示偏移
    传入的第五个参数dpl表示这个中断的优先级

*/
  • 请编程完善trap.c中的中断处理函数trap,在对时钟中断进行处理的部分填写trap函数中处理时钟中断的部分,使操作系统每遇到100次时钟中断后,调用print_ticks子程序,向屏幕上打印一行文字”100 ticks”。

代码

 case IRQ_OFFSET + IRQ_TIMER:
        /* LAB1 YOUR CODE : STEP 3 */
        /* handle the timer interrupt */
        /* (1) After a timer interrupt, you should record this event using a global variable (increase it), such as ticks in kern/driver/clock.c
         * (2) Every TICK_NUM cycle, you can print some info using a funciton, such as print_ticks().
         * (3) Too Simple? Yes, I think so!
         */
    ticks++;
    if(ticks%TICK_NUM == 0)//每次时钟中断之后ticks就会加一 当加到TICK_NUM次数时 打印并重新开始
    print_ticks();//前面有定义 打印字符串

实验截图如下

challenge 1

kern/init/init.c
static void lab1_switch_to_user(void) {
--------------------------------------------------------
    "sub $0x8, %%esp \n" 
    让 SS 和 ESP 这两个寄存器 有机会 POP 出时 更新 SS 和 ESP
    因为 从内核态进入中断 它的特权级没有改变 是不会 push 进 SS 和 ESP的 但是我们又需要通过 POP SS 和 ESP 去修改它们
    进入 T_SWITCH_TOU(120) 中断
    将原来的栈顶指针还给esp栈底指针
--------------------------------------------------------
    asm volatile (
        "sub $0x8, %%esp \n"
        "int %0 \n"
        "movl %%ebp, %%esp"
        : 
        : "i"(T_SWITCH_TOU)
    );
}

static void lab1_switch_to_kernel(void) {
--------------------------------------------------------
    进入 T_SWITCH_TOK(121) 中断
    将原来的栈顶指针还给esp栈底指针
--------------------------------------------------------
    asm volatile (
        "int %0 \n"
        "movl %%ebp, %%esp \n"
        : 
        : "i"(T_SWITCH_TOK)
    );
}
kern/trap/trap.c :
static void trap_dispatch(struct trapframe *tf)
通过"改造"一个中断 来进入我们想进入的用户态或者内核态
    case T_SWITCH_TOU:
        if (tf->tf_cs != USER_CS) {
            switchk2u = *tf;
            switchk2u.tf_cs = USER_CS;
            switchk2u.tf_ds = switchk2u.tf_es = switchk2u.tf_ss = USER_DS;
            switchk2u.tf_eflags |= FL_IOPL_MASK; // IOPL 改为 0
            switchk2u.tf_esp = (uint32_t)tf + sizeof(struct trapframe) - 8; // tf->esp的位置
            // iret 回到用户栈
            *((uint32_t *)tf - 1) = (uint32_t)&switchk2u;
        }
        break;
    case T_SWITCH_TOK:
        if (tf->tf_cs != KERNEL_

        CS) {
            tf->tf_cs = KERNEL_CS;
            tf->tf_ds = tf->tf_es = KERNEL_DS;
            tf->tf_eflags &= ~FL_IOPL_MASK;
            switchu2k = (struct trapframe *)(tf->tf_esp - (sizeof(struct trapframe) - 8));
            memmove(switchu2k, tf, sizeof(struct trapframe) - 8);
            *((uint32_t *)tf - 1) = (uint32_t)switchu2k;
        }
        break;

challenge 2

用键盘实现用户模式内核模式切换。具体目标是:“键盘输入3时切换到用户模式,键盘输入0时切换到内核模式”。 基本思路是借鉴软中断(syscall功能)的代码,并且把trap.c中软中断处理的设置语句拿过来。

kern/trap/trap.c
case IRQ_OFFSET + IRQ_KBD:
        c = cons_getc();
        cprintf("kbd [%03d] %c\n", c, c);
        if (c == '0') {
            if (tf->tf_cs != KERNEL_CS) {
                tf->tf_cs = KERNEL_CS;
                tf->tf_ds = tf->tf_ss = tf->tf_es = KERNEL_DS;
                tf->tf_eflags &= ~FL_IOPL_MASK;
            }
            print_trapframe(tf);
        }
        if (c == '3') {
            if (tf->tf_cs != USER_CS) {
                tf->tf_cs = USER_CS;
                tf->tf_ds = tf->tf_ss = tf->tf_es = USER_DS;
                tf->tf_eflags |= FL_IOPL_MASK;
            }
            print_trapframe(tf);
        }

实验二

实验目的

  • 理解基于段页式内存地址的转换机制
  • 理解页表的建立和使用方法
  • 理解物理内存的管理方法

练习0

本实验依赖实验1。请把你做的实验1的代码填入本实验中代码中有“LAB1”的注释相应部分。提示:可采用diff和patch工具进行半自动的合并(merge),也可用一些图形化的比较/merge工具来手动合并,比如meld,eclipse中的diff/merge工具,understand中的diff/merge工具等。

使用meld工具 很轻松的可以完成代码合并任务

练习1 实现 first-fit 连续物理内存分配算法

list.h 中已实现方法:

static inline void list_init(list_entry_t *elm) __attribute__((always_inline));
static inline void list_add(list_entry_t *listelm, list_entry_t *elm) __attribute__((always_inline));
static inline void list_add_before(list_entry_t *listelm, list_entry_t *elm) __attribute__((always_inline));
static inline void list_add_after(list_entry_t *listelm, list_entry_t *elm) __attribute__((always_inline));
static inline void list_del(list_entry_t *listelm) __attribute__((always_inline));
static inline void list_del_init(list_entry_t *listelm) __attribute__((always_inline));
static inline bool list_empty(list_entry_t *list) __attribute__((always_inline));
static inline list_entry_t *list_next(list_entry_t *listelm) __attribute__((always_inline));
static inline list_entry_t *list_prev(list_entry_t *listelm) __attribute__((always_inline));

static inline void __list_add(list_entry_t *elm, list_entry_t *prev, list_entry_t *next) __attribute__((always_inline));
static inline void __list_del(list_entry_t *prev, list_entry_t *next) __attribute__((always_inline));

Page定义在memlayout.h中,如下:

struct Page {
    int ref;                        // page frame's reference counter
    uint32_t flags;                 // array of flags that describe the status of the page frame
    unsigned int property;          // the num of free block, used in first fit pm manager
    list_entry_t page_link;         // free list link
};

实现最先适应算法:


static void
default_init(void) {
    list_init(&free_list);
    nr_free = 0;
}


static void
default_init_memmap(struct Page *base, size_t n) {
    assert(n > 0);
    struct Page *p = base;
    for (; p != base + n; p ++) {
        assert(PageReserved(p)); 
    SetPageReserved(p);
        p->property = 0;  
        set_page_ref(p, 0);
    }
    base->property = n;         
    SetPageProperty(base);
    nr_free += n;
    list_add(&free_list, &(base->page_link));
}
//判断空闲地址空间是否大于所需空间
//从free_list开始,遍历链表,直到找到第一块不小于所需空间大小的内存块
//分配连续的n页,修改标志位
//从链表中删除此内存块,如果有剩余的小的内存块,重新插入链表
static struct Page *
default_alloc_pages(size_t n) {
    assert(n > 0);
    if (n > nr_free) {
        return NULL;
    }
    struct Page *page = NULL;
    list_entry_t *le = &free_list;
    while ((le = list_next(le)) != &free_list) {
        struct Page *p = le2page(le, page_link);
        if (p->property >= n) {
            page = p;
            break;
        }
    }
    if (page != NULL) {
        list_del(&(page->page_link));
        if (page->property > n) {
            struct Page *p = page + n;
            p->property = page->property - n;
            list_add(&free_list, &(p->page_link));
    }
    list_del(&(page->page_link),&(p->page_link));
        nr_free -= n;
        ClearPageProperty(page);
    }
    return page;
}
//修改释放页的标志位
//找到链表中应该插入的位置并插入
//判断此块空余空间能否与前后空余空间合并,如果可以将其合并
static void
default_free_pages(struct Page *base, size_t n) {
    assert(n > 0);
    struct Page *p = base;
    for (; p != base + n; p ++) {
        assert(!PageReserved(p) && !PageProperty(p));
        p->flags = 0;
        set_page_ref(p, 0);
    }
    base->property = n;
    SetPageProperty(base);
    list_entry_t *le = list_next(&free_list);
    while (le != &free_list) {
        p = le2page(le, page_link);
        le = list_next(le);
        if (base + base->property == p) {
            base->property += p->property;
            ClearPageProperty(p);
            list_del(&(p->page_link));
        }
        else if (p + p->property == base) {
            p->property += base->property;
            ClearPageProperty(base);
            base = p;
            list_del(&(p->page_link));
        }
    }
    nr_free += n;
    le = list_next(&free_list);
    while (le != &free_list) {
        p = le2page(le, page_link);
        if (base + base->property <= p) {
            break;
        }
        le = list_next(le);
    }
    list_add(&free_list, &(base->page_link));
}

练习2 实现寻找虚拟地址对应的页表项

通过设置页表和对应的页表项,可建立虚拟内存地址和物理内存地址的对应关系。其中的get_pte函数是设置页表项环节中的一个重要步骤。此函数找到一个虚地址对应的二级页表项的内核虚地址,如果此二级页表项不存在,则分配一个包含此项的二级页表。

  • 请描述页目录项(Pag Director Entry)和页表(Page Table Entry)中每个组成部分的含 义和以及对ucore而言的潜在用处

    页的分配是以物理页为单位的,其地址要求按照页大小,即4096字节对齐。PDE和PTE的高20位用于保存对应页表和页的基地址,低12位可以用作表项的标志位,对表项的属性进行说明,如是否存在,是否可写以及访问权限等。

  • 如果ucore执行过程中访问内存,出现了页访问异常,请问硬件要做哪些事情?

    进行换页操作 首先 CPU 将产生页访问异常的线性地址 放到 cr2 寄存器中 然后就是和普通的中断一样 保护现场 将寄存器的值压入栈中 然后压入 error_code 中断服务例程将外存的数据换到内存中来 最后 退出中断 回到进入中断前的状态

    pde_t *pdep = &pgdir[PDX(la)]; 
    if (!(*pdep & PTE_P)) {         
        struct Page* page = alloc_page();
        if (!create || page == NULL) {
            return NULL;
        }
        set_page_ref(page, 1);
        uintptr_t pa = page2pa(page);
        memset(KADDR(pa), 0, PGSIZE); 
        *pdep = pa | PTE_U | PTE_W | PTE_P; 
    }
    return &((pte_t *)KADDR(PDE_ADDR(*pdep)))[PTX(la)];
  • 根据虚地址的高十位查询页目录,找到页表项的pdep
  • 检查该页是否在内存中,如果不在,创建该页,并更新相关信息
  • 根据虚拟地址的中间十位,找到虚拟地址对应的页表项

练习3

当释放一个包含某虚地址的物理内存页时,需要让对应此物理内存页的管理数据结构Page做相关的清除处理,使得此物理内存页成为空闲;另外还需把表示虚地址与物理地址对应关系的二级页表项清除。

static inline void
page_remove_pte(pde_t *pgdir, uintptr_t la, pte_t *ptep) {
if (*ptep & PTE_P) {                    //判断页表中该表项是否存在
    struct Page *page = pte2page(*ptep);
    if (page_ref_dec(page) == 0) {      //判断是否只被引用了一次
        free_page(page);                //如果只被引用了一次,那么可以释放掉此页
    }
    *ptep = 0;                          //如果被多次引用,则不能释放此页,只用释放二级页表的表项
    tlb_invalidate(pgdir, la);          //更新页表
    }
}

实验结果

实验二

实验目的

  • 理解基于段页式内存地址的转换机制
  • 理解页表的建立和使用方法
  • 理解物理内存的管理方法

练习0

本实验依赖实验1。请把你做的实验1的代码填入本实验中代码中有“LAB1”的注释相应部分。提示:可采用diff和patch工具进行半自动的合并(merge),也可用一些图形化的比较/merge工具来手动合并,比如meld,eclipse中的diff/merge工具,understand中的diff/merge工具等。

使用meld工具 很轻松的可以完成代码合并任务

练习1 实现 first-fit 连续物理内存分配算法

list.h 中已实现方法:

static inline void list_init(list_entry_t *elm) __attribute__((always_inline));
static inline void list_add(list_entry_t *listelm, list_entry_t *elm) __attribute__((always_inline));
static inline void list_add_before(list_entry_t *listelm, list_entry_t *elm) __attribute__((always_inline));
static inline void list_add_after(list_entry_t *listelm, list_entry_t *elm) __attribute__((always_inline));
static inline void list_del(list_entry_t *listelm) __attribute__((always_inline));
static inline void list_del_init(list_entry_t *listelm) __attribute__((always_inline));
static inline bool list_empty(list_entry_t *list) __attribute__((always_inline));
static inline list_entry_t *list_next(list_entry_t *listelm) __attribute__((always_inline));
static inline list_entry_t *list_prev(list_entry_t *listelm) __attribute__((always_inline));

static inline void __list_add(list_entry_t *elm, list_entry_t *prev, list_entry_t *next) __attribute__((always_inline));
static inline void __list_del(list_entry_t *prev, list_entry_t *next) __attribute__((always_inline));

Page定义在memlayout.h中,如下:

struct Page {
    int ref;                        // page frame's reference counter
    uint32_t flags;                 // array of flags that describe the status of the page frame
    unsigned int property;          // the num of free block, used in first fit pm manager
    list_entry_t page_link;         // free list link
};

实现最先适应算法:


static void
default_init(void) {
    list_init(&free_list);
    nr_free = 0;
}


static void
default_init_memmap(struct Page *base, size_t n) {
    assert(n > 0);
    struct Page *p = base;
    for (; p != base + n; p ++) {
        assert(PageReserved(p)); 
    SetPageReserved(p);
        p->property = 0;  
        set_page_ref(p, 0);
    }
    base->property = n;         
    SetPageProperty(base);
    nr_free += n;
    list_add(&free_list, &(base->page_link));
}
//判断空闲地址空间是否大于所需空间
//从free_list开始,遍历链表,直到找到第一块不小于所需空间大小的内存块
//分配连续的n页,修改标志位
//从链表中删除此内存块,如果有剩余的小的内存块,重新插入链表
static struct Page *
default_alloc_pages(size_t n) {
    assert(n > 0);
    if (n > nr_free) {
        return NULL;
    }
    struct Page *page = NULL;
    list_entry_t *le = &free_list;
    while ((le = list_next(le)) != &free_list) {
        struct Page *p = le2page(le, page_link);
        if (p->property >= n) {
            page = p;
            break;
        }
    }
    if (page != NULL) {
        list_del(&(page->page_link));
        if (page->property > n) {
            struct Page *p = page + n;
            p->property = page->property - n;
            list_add(&free_list, &(p->page_link));
    }
    list_del(&(page->page_link),&(p->page_link));
        nr_free -= n;
        ClearPageProperty(page);
    }
    return page;
}
//修改释放页的标志位
//找到链表中应该插入的位置并插入
//判断此块空余空间能否与前后空余空间合并,如果可以将其合并
static void
default_free_pages(struct Page *base, size_t n) {
    assert(n > 0);
    struct Page *p = base;
    for (; p != base + n; p ++) {
        assert(!PageReserved(p) && !PageProperty(p));
        p->flags = 0;
        set_page_ref(p, 0);
    }
    base->property = n;
    SetPageProperty(base);
    list_entry_t *le = list_next(&free_list);
    while (le != &free_list) {
        p = le2page(le, page_link);
        le = list_next(le);
        if (base + base->property == p) {
            base->property += p->property;
            ClearPageProperty(p);
            list_del(&(p->page_link));
        }
        else if (p + p->property == base) {
            p->property += base->property;
            ClearPageProperty(base);
            base = p;
            list_del(&(p->page_link));
        }
    }
    nr_free += n;
    le = list_next(&free_list);
    while (le != &free_list) {
        p = le2page(le, page_link);
        if (base + base->property <= p) {
            break;
        }
        le = list_next(le);
    }
    list_add(&free_list, &(base->page_link));
}

练习2 实现寻找虚拟地址对应的页表项

通过设置页表和对应的页表项,可建立虚拟内存地址和物理内存地址的对应关系。其中的get_pte函数是设置页表项环节中的一个重要步骤。此函数找到一个虚地址对应的二级页表项的内核虚地址,如果此二级页表项不存在,则分配一个包含此项的二级页表。

  • 请描述页目录项(Pag Director Entry)和页表(Page Table Entry)中每个组成部分的含 义和以及对ucore而言的潜在用处

    页的分配是以物理页为单位的,其地址要求按照页大小,即4096字节对齐。PDE和PTE的高20位用于保存对应页表和页的基地址,低12位可以用作表项的标志位,对表项的属性进行说明,如是否存在,是否可写以及访问权限等。

  • 如果ucore执行过程中访问内存,出现了页访问异常,请问硬件要做哪些事情?

    进行换页操作 首先 CPU 将产生页访问异常的线性地址 放到 cr2 寄存器中 然后就是和普通的中断一样 保护现场 将寄存器的值压入栈中 然后压入 error_code 中断服务例程将外存的数据换到内存中来 最后 退出中断 回到进入中断前的状态

    pde_t *pdep = &pgdir[PDX(la)]; 
    if (!(*pdep & PTE_P)) {         
        struct Page* page = alloc_page();
        if (!create || page == NULL) {
            return NULL;
        }
        set_page_ref(page, 1);
        uintptr_t pa = page2pa(page);
        memset(KADDR(pa), 0, PGSIZE); 
        *pdep = pa | PTE_U | PTE_W | PTE_P; 
    }
    return &((pte_t *)KADDR(PDE_ADDR(*pdep)))[PTX(la)];
  • 根据虚地址的高十位查询页目录,找到页表项的pdep
  • 检查该页是否在内存中,如果不在,创建该页,并更新相关信息
  • 根据虚拟地址的中间十位,找到虚拟地址对应的页表项

练习3

当释放一个包含某虚地址的物理内存页时,需要让对应此物理内存页的管理数据结构Page做相关的清除处理,使得此物理内存页成为空闲;另外还需把表示虚地址与物理地址对应关系的二级页表项清除。

static inline void
page_remove_pte(pde_t *pgdir, uintptr_t la, pte_t *ptep) {
if (*ptep & PTE_P) {                    //判断页表中该表项是否存在
    struct Page *page = pte2page(*ptep);
    if (page_ref_dec(page) == 0) {      //判断是否只被引用了一次
        free_page(page);                //如果只被引用了一次,那么可以释放掉此页
    }
    *ptep = 0;                          //如果被多次引用,则不能释放此页,只用释放二级页表的表项
    tlb_invalidate(pgdir, la);          //更新页表
    }
}

实验结果

实验三

实验目的

  • 了解虚拟内存的Page Fault异常处理实现
  • 了解页替换算法在操作系统中的实现

实验内容

本次实验是在实验二的基础上,借助于页表机制和实验一中涉及的中断异常处理机制,完成Page Fault异常处理和FIFO页替换算法的实现,结合磁盘提供的缓存空间,从而能够支持虚存管理,提供一个比实际物理内存空间“更大”的虚拟内存空间给系统使用。这个实验与实际操作系统中的实现比较起来要简单,不过需要了解实验一和实验二的具体实现。实际操作系统系统中的虚拟内存管理设计与实现是相当复杂的,涉及到与进程管理系统、文件系统等的交叉访问。如果大家有余力,可以尝试完成扩展练习,实现extended clock页替换算法。

练习0:填写已有实验

与lab2相同,使用meld快速合并

练习1:给未被映射的地址映射上物理页(需要编程)

完成do_pgfault(mm/vmm.c)函数,给未被映射的地址映射上物理页。设置访问权限 的时候需要参考页面所在 VMA 的权限,同时需要注意映射物理页时需要操作内存控制 结构所指定的页表,而不是内核的页表。注意:在LAB3 EXERCISE 1处填写代码。执行

make qemu
或者
make grade
ptep = get_pte(mm->pgdir, addr, 1); // 根据引发缺页异常的地址 去找到 地址所对应的 PTE 如果找不到 则创建一页表
    if (*ptep == 0) { // PTE 所指向的 物理页表地址 若不存在 则分配一物理页并将逻辑地址和物理地址作映射 (就是让 PTE 指向 物理页帧)
        if (pgdir_alloc_page(mm->pgdir, addr, perm) == NULL) {
            goto failed;
        }
    } else { // 如果 PTE 存在 说明此时 P 位为 0 该页被换出到外存中 需要将其换入内存
        if(swap_init_ok) { // 是否可以换入页面
            struct Page *page = NULL;
            ret = swap_in(mm, addr, &page); // 根据 PTE 找到 换出那页所在的硬盘地址 并将其从外存中换入
            if (ret != 0) {
                cprintf("swap_in in do_pgfault failed\n");
                goto failed;
            }
            page_insert(mm->pgdir, page, addr, perm); // 建立虚拟地址和物理地址之间的对应关系(更新 PTE 因为 已经被换入到内存中了)
            swap_map_swappable(mm, addr, page, 0); // 使这一页可以置换
            page->pra_vaddr = addr; // 设置 这一页的虚拟地址
        }
  • AVL CPU 不理会这个属性 可以不管 (有可能在32位系统使用大过 4G内存的时候 用到这几位)
  • G Global 全局位 表示是否将虚拟地址与物理地址的转换结果缓存到 TLB 中
  • D Dirty 脏页位 当 CPU 对这个页进行写操作时 会置 1
  • PAT Page Attribute Table 页属性表位 置 0
  • A Accessed 访问位 若为 1 则 说明 CPU 访问过了 CPU 会定时清 0 记录被置 1 的频率 当内存不足时 会将 使用频率较低的页面换出到外存 同时将 P位 置 0 下次访问 该页时 会引起 Pagefault 异常 中断处理程序再将此页换上
  • PCD Page-level Cache Disable 页级高速缓存位 置 0 即可 读的时候 高速缓存是否有效 若有效则直接从高速缓存中读出 若无效的话 则必须实实在在的从 I/O 端口去读数据
  • PWT Page-level Write-Through 页级通写位 控制是先写到高速缓存里再慢慢回写到内存里 还是 直接慢慢写到内存里
  • US User/Superviosr 普通用户/超级用户位
  • RW Read/Write 读写位
  • P Present 存在位 (虚拟页式存储的关键位 若为 0 则发起缺页异常)

页访问异常 会将产生页访问异常的线性地址存入 cr2 寄存器中 并且给出 错误码 error_code 说明是页访问异常的具体原因 uCore OS 会将其 存入 struct trapframe 中 tf_err 等到中断服务例程 调用页访问异常处理函数(do_pgfault()) 时 再判断 具体原因 若不在某个VMA的地址范围内 或 不满足正确的读写权限 则是非法访问 若在此范围 且 权限也正确 则 认为是 合法访问 只是没有建立虚实对应关系 应分配一页 并修改页表 完成 虚拟地址到 物理地址的映射 刷新 TLB 最后再 调用 iret 重新执行引发页访问异常的 那条指令 若是在外存中 则将其换入 内存 刷新 TLB 然后退出中断服务例程 重新执行引发页访问异常的 那条指令

练习2:补充完成基于FIFO的页面替换算法(需要编程)

完成vmm.c中的do_pgfault函数,并且在实现FIFO算法的swap_fifo.c中完成map_swappable和swap_out_vistim函数。通过对swap的测试。注意:在LAB2 EXERCISE 2处填写代码。执行

make qemu
或者
make grade
此时完成的是 FIFO 置换算法 因此 每次换出的都应该是 最先进来的 页
static int _fifo_map_swappable(struct mm_struct *mm, uintptr_t addr, struct Page *page, int swap_in) {
    list_entry_t *head=(list_entry_t*) mm->sm_priv;
    list_entry_t *entry=&(page->pra_page_link);

    assert(entry != NULL && head != NULL);

    list_add(head, entry); // 就是将这一页加入到链表头中(最近访问过的放前面) 使其可以被置换算法使用到
    return 0;
}
static int _fifo_swap_out_victim(struct mm_struct *mm, struct Page ** ptr_page, int in_tick) {
    list_entry_t *head=(list_entry_t*) mm->sm_priv;
    assert(head != NULL);
    assert(in_tick==0);

    list_entry_t *le = head->prev; // 换出最先进来的页 (因为每次访问一个页 都是插入到头节点的后面 因此 头节点的前面就是最先访问的页)
    struct Page* page = le2page(le, pra_page_link); // 和之前一样 通过 le 这个链表节点的地址 减去 pra_page_link 在 Page 结构体中的 Offset 得到 Page 的地址
    list_del(le); // 删掉这个节点
    *ptr_page = page; // 将这一页地址存到 ptr_page 中 给 调用本函数的函数使用
    return 0;
}


请在实验报告中回答如下问题:

如果要在ucore上实现"extended clock页替换算法"请给你的设计方案,现有的swap_manager框架是否足以支持在ucore中实现此算法?如果是,请给你的设计方案。如果不是,请给出你的新的扩展和基此扩展的设计方案。并需要回答如下问题

  • 需要被换出的页的特征是什么?
  • 在ucore中如何判断具有这样特征的页?
  • 何时进行换入和换出操作?
当然能够支持
首选 页表项的 Dirty Bit 为 0 的页 且 Access Bit 为 0 的页 其次是 访问了但没修改的页 最次是 访问了修改了的页
!(*ptep & PTE_A) && !(*ptep & PTE_D)  没被访问过 也没被修改过
(*ptep & PTE_A) && !(*ptep & PTE_D) 被访问过 但没被修改过
!(*ptep & PTE_A) && (*ptep & PTE_D) 没被访问过 但被修改过
换入是在缺页异常的时候 换出是在物理页帧满的时候

扩展练习 Challenge:实现识别dirty bit的 extended clock页替换算法(需要编程)

实验四

实验目的

  • 了解内核线程创建/执行的管理过程
  • 了解内核线程的切换和基本调度过程

实验内容

实验2/3完成了物理和虚拟内存管理,这给创建内核线程(内核线程是一种特殊的进程)打下了提供内存管理的基础。当一个程序加载到内存中运行时,首先通过ucore OS的内存管理子系统分配合适的空间,然后就需要考虑如何分时使用CPU来“并发”执行多个程序,让每个运行的程序(这里用线程或进程表示)“感到”它们各自拥有“自己”的CPU。

本次实验将首先接触的是内核线程的管理。内核线程是一种特殊的进程,内核线程与用户进程的区别有两个:

  • 内核线程只运行在内核态
  • 用户进程会在在用户态和内核态交替运行
  • 所有内核线程共用ucore内核内存空间,不需为每个内核线程维护单独的内存空间
  • 而用户进程需要维护各自的用户内存空间 相关原理介绍可看附录B:【原理】进程/线程的属性与特征解析。

练习0: 填写已有实验

本实验依赖实验1/2/3。请把你做的实验1/2/3的代码填入本实验中代码中有“LAB1”,“LAB2”,“LAB3”的注释相应部分。

同lab2 3,使用meld即可

练习1:分配并初始化一个进程控制块(需要编码)

        proc->state = PROC_UNINIT; // 进程状态
        proc->pid = -1; // 进程ID
        proc->runs = 0; // 进程时间片
        proc->kstack = 0; // 进程所使用的内存栈地址
        proc->need_resched = NULL; // 进程是否能被调度
        proc->parent = NULL; // 父进程
        proc->mm = NULL; // 进程所用的虚拟内存
        memset(&(proc->context), 0, sizeof(struct context)); // 进程的上下文
        proc->tf = NULL; // 中断帧指针
        proc->cr3 = boot_cr3; // 页目录表地址 设为 内核页目录表基址
        proc->flags = 0; // 标志位
        memset(&(proc->name), 0, PROC_NAME_LEN); // 进程名

请在实验报告中简要说明你的设计实现过程。请回答如下问题:

  • 请说明proc_struct中struct context context和struct trapframe *tf成员变量含义和在本实验中的作用是啥?(提示通过看代码和编程调试可以判断出来) context作用时在进行上下文切换的过程中,保存当前寄存器的值。其定义在kern/process/proc.h中:
    struct context {
      uint32_t eip;
      uint32_t esp;
      uint32_t ebx;
      uint32_t ecx;
      uint32_t edx;
      uint32_t esi;
      uint32_t edi;
      uint32_t ebp;
    };
    
    trapframe *tf用于记录发生中断之前的栈帧的内容,其中一部分为硬件保存。定义在kern/trap/trap.h中:
    struct trapframe {
      struct pushregs tf_regs;
      uint16_t tf_gs;
      uint16_t tf_padding0;
      uint16_t tf_fs;
      uint16_t tf_padding1;
      uint16_t tf_es;
      uint16_t tf_padding2;
      uint16_t tf_ds;
      uint16_t tf_padding3;
      uint32_t tf_trapno;
      /* below here defined by x86 hardware */
      uint32_t tf_err;
      uintptr_t tf_eip;
      uint16_t tf_cs;
      uint16_t tf_padding4;
      uint32_t tf_eflags;
      /* below here only when crossing rings, such as from user to kernel */
      uintptr_t tf_esp;
      uint16_t tf_ss;
      uint16_t tf_padding5;
    } __attribute__((packed));
    

    练习2:为新创建的内核线程分配资源(需要编码)

    创建一个内核线程需要分配和设置好很多资源。kernel_thread函数通过调用do_fork函数完成具体内核线程的创建工作。do_kernel函数会调用alloc_proc函数来分配并初始化一个进程控制块,但alloc_proc只是找到了一小块内存用以记录进程的必要信息,并没有实际分配这些资源。ucore一般通过do_fork实际创建新的内核线程。do_fork的作用是,创建当前内核线程的一个副本,它们的执行上下文、代码、数据都一样,但是存储位置不同。在这个过程中,需要给新内核线程分配资源,并且复制原进程的状态。你需要完成在kern/process/proc.c中的do_fork函数中的处理过程。它的大致执行步骤包括:
  • 调用alloc_proc,首先获得一块用户信息块。
  • 为进程分配一个内核栈。
  • 复制原进程的内存管理信息到新进程(但内核线程不必做此事)
  • 复制原进程上下文到新进程
  • 将新进程添加到进程列表
  • 唤醒新进程
  • 返回新进程号 请在实验报告中简要说明你的设计实现过程。请回答如下问题:
  • 请说明ucore是否做到给每个新fork的线程一个唯一的id?请说明你的分析和理由。

    练习3:阅读代码,理解 proc_run 函数和它调用的函数如何完成进程切换的。(无编码工作)

    请在实验报告中简要说明你对proc_run函数的分析。并回答如下问题:
    当前进程/线程 切换到 proc 这个进程/线程
    void proc_run(struct proc_struct *proc) {
      if (proc != current) {
          bool intr_flag;
          struct proc_struct *prev = current, *next = proc;
          local_intr_save(intr_flag); // 关闭中断
          {
              current = proc; // 将当前进程换为 要切换到的进程
              // 设置任务状态段tss中的特权级0下的 esp0 指针为 next 内核线程 的内核栈的栈顶
              load_esp0(next->kstack + KSTACKSIZE);
              lcr3(next->cr3); // 重新加载 cr3 寄存器(页目录表基址) 进行进程间的页表切换
              switch_to(&(prev->context), &(next->context)); // 调用 switch_to 进行上下文的保存与切换
          }
          local_intr_restore(intr_flag);
      }
    }
    
    在本实验的执行过程中,创建且运行了几个内核线程? 两个内核线程 一个为 idle_proc 为 第 0 个内核线程 完成内核中的初始化 然后调度执行其他进程或线程 另一个为 init_proc 本次实验的内核线程 只用来打印字符串 语句local_intr_save(intr_flag);....local_intr_restore(intr_flag);在这里有何作用?请说明理由 关闭中断 避免进程切换的中途 再被中断(其他进程再进行调度) 完成代码编写后,编译并运行代码:make qemu
    WARNING: Image format was not specified for 'bin/ucore.img' and probing guessed raw.         Automatically detecting the format is dangerous for raw images, write operations on block 0 will be restricted.         Specify the 'raw' format explicitly to remove the restrictions.WARNING: Image format was not specified for 'bin/swap.img' and probing guessed raw.         Automatically detecting the format is dangerous for raw images, write operations on block 0 will be restricted.         Specify the 'raw' format explicitly to remove the restrictions.(THU.CST) os is loading ...Special kernel symbols:  entry  0xc0100036 (phys)  etext  0xc0109614 (phys)  edata  0xc0127000 (phys)  end    0xc012a160 (phys)Kernel executable memory footprint: 169KBThe value of ebp:0xc0123f48 eip:0xc0100a89 arg:0xc0123f50  0xc0123f54  0xc0123f58  0xc0123f5c      kern/debug/kdebug.c:309: print_stackframe+21The value of ebp:0xc0123f58 eip:0xc0100d97 arg:0xc0123f60  0xc0123f64  0xc0123f68  0xc0123f6c      kern/debug/kmonitor.c:129: mon_backtrace+10The value of ebp:0xc0123f78 eip:0xc01000cc arg:0xc0123f80  0xc0123f84  0xc0123f88  0xc0123f8c      kern/init/init.c:58: grade_backtrace2+19The value of ebp:0xc0123f98 eip:0xc01000ee arg:0xc0123fa0  0xc0123fa4  0xc0123fa8  0xc0123fac      kern/init/init.c:63: grade_backtrace1+27The value of ebp:0xc0123fb8 eip:0xc010010b arg:0xc0123fc0  0xc0123fc4  0xc0123fc8  0xc0123fcc      kern/init/init.c:68: grade_backtrace0+19The value of ebp:0xc0123fd8 eip:0xc010012c arg:0xc0123fe0  0xc0123fe4  0xc0123fe8  0xc0123fec      kern/init/init.c:73: grade_backtrace+26The value of ebp:0xc0123ff8 eip:0xc0100086 arg:0xc0124000  0xc0124004  0xc0124008  0xc012400c      kern/init/init.c:33: kern_init+79memory management: default_pmm_managere820map:  memory: 0009fc00, [00000000, 0009fbff], type = 1.  memory: 00000400, [0009fc00, 0009ffff], type = 2.  memory: 00010000, [000f0000, 000fffff], type = 2.  memory: 07ee0000, [00100000, 07fdffff], type = 1.  memory: 00020000, [07fe0000, 07ffffff], type = 2.  memory: 00040000, [fffc0000, ffffffff], type = 2.check_alloc_page() succeeded!check_pgdir() succeeded!check_boot_pgdir() succeeded!-------------------- BEGIN --------------------PDE(0e0) c0000000-f8000000 38000000 urw  |-- PTE(38000) c0000000-f8000000 38000000 -rwPDE(001) fac00000-fb000000 00400000 -rw  |-- PTE(000e0) faf00000-fafe0000 000e0000 urw  |-- PTE(00001) fafeb000-fafec000 00001000 -rw--------------------- END ---------------------use SLOB allocatorkmalloc_init() succeeded!check_vma_struct() succeeded!page fault at 0x00000100: K/W [no page found].check_pgfault() succeeded!check_vmm() succeeded.ide 0:      10000(sectors), 'QEMU HARDDISK'.ide 1:     262144(sectors), 'QEMU HARDDISK'.SWAP: manager = fifo swap managerBEGIN check_swap: count 1, total 31954setup Page Table for vaddr 0X1000, so alloc a pagesetup Page Table vaddr 0~4MB OVER!set up init env for check_swap begin!page fault at 0x00001000: K/W [no page found].page fault at 0x00002000: K/W [no page found].page fault at 0x00003000: K/W [no page found].page fault at 0x00004000: K/W [no page found].set up init env for check_swap over!write Virt Page c in fifo_check_swapwrite Virt Page a in fifo_check_swapwrite Virt Page d in fifo_check_swapwrite Virt Page b in fifo_check_swapwrite Virt Page e in fifo_check_swappage fault at 0x00005000: K/W [no page found].main-loop: WARNING: I/O thread spun for 1000 iterationsswap_out: i 0, store page in vaddr 0x1000 to disk swap entry 2write Virt Page b in fifo_check_swapwrite Virt Page a in fifo_check_swappage fault at 0x00001000: K/W [no page found].swap_out: i 0, store page in vaddr 0x2000 to disk swap entry 3swap_in: load disk swap entry 2 with swap_page in vadr 0x1000write Virt Page b in fifo_check_swappage fault at 0x00002000: K/W [no page found].swap_out: i 0, store page in vaddr 0x3000 to disk swap entry 4swap_in: load disk swap entry 3 with swap_page in vadr 0x2000write Virt Page c in fifo_check_swappage fault at 0x00003000: K/W [no page found].swap_out: i 0, store page in vaddr 0x4000 to disk swap entry 5swap_in: load disk swap entry 4 with swap_page in vadr 0x3000write Virt Page d in fifo_check_swappage fault at 0x00004000: K/W [no page found].swap_out: i 0, store page in vaddr 0x5000 to disk swap entry 6swap_in: load disk swap entry 5 with swap_page in vadr 0x4000write Virt Page e in fifo_check_swappage fault at 0x00005000: K/W [no page found].swap_out: i 0, store page in vaddr 0x1000 to disk swap entry 2swap_in: load disk swap entry 6 with swap_page in vadr 0x5000write Virt Page a in fifo_check_swappage fault at 0x00001000: K/R [no page found].swap_out: i 0, store page in vaddr 0x2000 to disk swap entry 3swap_in: load disk swap entry 2 with swap_page in vadr 0x1000count is 0, total is 5check_swap() succeeded!++ setup timer interruptsthis initproc, pid = 1, name = "init"To U: "Hello world!!".To U: "en.., Bye, Bye. :)"kernel panic at kern/process/proc.c:348:    process exit!!.stack trackback:The value of ebp:0xc030dfa8 eip:0xc0100a89 arg:0xc030dfb0  0xc030dfb4  0xc030dfb8  0xc030dfbc      kern/debug/kdebug.c:309: print_stackframe+21The value of ebp:0xc030dfc8 eip:0xc010045c arg:0xc030dfd0  0xc030dfd4  0xc030dfd8  0xc030dfdc      kern/debug/panic.c:27: __panic+107The value of ebp:0xc030dfe8 eip:0xc01086f1 arg:0xc030dff0  0xc030dff4  0xc030dff8  0xc030dffc      kern/process/proc.c:348: do_exit+28Welcome to the kernel debug monitor!!Type 'help' for a list of commands.
    

    扩展练习Challenge:实现支持任意大小的内存分配算法

实验五

实验目的

  • 了解第一个用户进程创建过程
  • 了解系统调用框架的实现机制
  • 了解ucore如何实现系统调用sys_fork/sys_exec/sys_exit/sys_wait来进行进程管理

实验内容

实验4完成了内核线程,但到目前为止,所有的运行都在内核态执行。实验5将创建用户进程,让用户进程在用户态执行,且在需要ucore支持时,可通过系统调用来让ucore提供服务。为此需要构造出第一个用户进程,并通过系统调用sys_fork/sys_exec/sys_exit/sys_wait来支持运行不同的应用程序,完成对用户进程的执行过程的基本管理。相关原理介绍可看附录B。

实验0

本实验依赖实验1/2/3/4。请把你做的实验1/2/3/4的代码填入本实验中代码中有“LAB1”/“LAB2”/“LAB3”/“LAB4”的注释相应部分。注意:为了能够正确执行lab5的测试应用程序,可能需对已完成的实验1/2/3/4的代码进行进一步改进。

用meld完成同样的步骤

修改部分如下:

proc.c: 
static struct proc_struct * alloc_proc(void) {
    proc->state = PROC_UNINIT;
    proc->pid = -1;
    proc->runs = 0;
    proc->kstack = 0;
    proc->need_resched = NULL;
    proc->parent = NULL;
    proc->mm = NULL;
    memset(&(proc->context), 0, sizeof(struct context));
    proc->tf = NULL;
    proc->cr3 = boot_cr3;
    proc->flags = 0;
    memset(&(proc->name), 0, PROC_NAME_LEN);


    // 新添加: 初始化进程等待状态 初始化进程相关指针
    proc->wait_state = 0; 
    proc->cptr = proc->yptr = proc-> optr = NULL;
    |   cptr: proc is parent          |
    |   yptr: proc is younger sibling |
    |   optr: proc is older sibling   |
}
int do_fork(uint32_t clone_flags, uintptr_t stack, struct trapframe *tf) {
    if ((proc = alloc_proc()) == NULL) {
        goto fork_out;
    }
    proc->parent = current;

    // 添加这行 确保 当前进程正在等待    
    assert(current->wait_state == 0);

    if (setup_kstack(proc) != 0) {
        goto bad_fork_cleanup_proc;
    }
    if (copy_mm(clone_flags, proc) != 0) {
        goto bad_fork_cleanup_kstack;
    }
    copy_thread(proc, stack, tf);
    bool intr_flag;
    local_intr_save(intr_flag);
    {
        proc->pid = get_pid();
        hash_proc(proc);

        // 删除此行 nr_process++ 和 加入链表那行 添加下面那行;
        // 将原来的简单 计数 改成设置进程的相关链接
        set_links(proc);
    }
    local_intr_restore(intr_flag);

    wakeup_proc(proc);
    ret = proc->pid;
}

trap.c:
static void trap_dispatch(struct trapframe *tf) {
    // 时间片用完 设置进程 为 需要被调度
    if (++ticks % TICK_NUM == 0) {
        assert(current != NULL);
        current->need_resched = 1;
    }
}
void idt_init(void) {
    int i;
    for (i = 0; i < sizeof(idt) / sizeof(struct gatedesc); i++) {
        SETGATE(idt[i], 0, GD_KTEXT, __vectors[i], DPL_KERNEL);
    }
    // 添加下面这行
    // 设置给用户态用的中断门 让用户态能够进行系统调用
    SETGATE(idt[T_SYSCALL], 1, GD_KTEXT, __vectors[T_SYSCALL], DPL_USER);

    lidt(&idt_pd);
}

练习1: 加载应用程序并执行(需要编码)

do_execv函数调用load_icode(位于kern/process/proc.c中)来加载并解析一个处于内存中的ELF执行文件格式的应用程序,建立相应的用户内存空间来放置应用程序的代码段、数据段等,且要设置好proc_struct结构中的成员变量trapframe中的内容,确保在执行此进程后,能够从应用程序设定的起始执行地址开始执行。需设置正确的trapframe内容。

请在实验报告中简要说明你的设计实现过程。

首先清空进程原先的中断帧 然后再将 中断帧中的 代码段 和 数据段
修改为 用户态的段选择子 栈指针设置为 用户栈顶 eip 设置为 用户程序的入口地址
最后 确保在用户进程中能够响应中断
static int load_icode(unsigned char *binary, size_t size) {
    tf->tf_cs = USER_CS;
    tf->tf_ds = tf->tf_es = tf->tf_ss = USER_DS;
    tf->tf_esp = USTACKTOP;
    tf->tf_eip = elf->e_entry;
    tf->tf_eflags = FL_IF;
}

请在实验报告中描述当创建一个用户态进程并加载了应用程序后,CPU是如何让这个应用程序最终在用户态执行起来的。即这个用户态进程被ucore选择占用CPU执行(RUNNING态)到具体执行应用程序第一条指令的整个经过。

在此之前先理一下 用户态进程是怎么来的

  • 创建了一个 硬构造了 第0个 内核线程 idleproc
  • idleproc 通过 kernel_thread 创建了 第1个内核线程 initproc 在 lab 4 中只是打印字符串
  • initproc 通过 kernel_execve 将 hello应用程序执行码覆盖到了 initproc 用户虚拟内存空间 来创建 用户态进程

    创建一个用户态进程并加载了应用程序之后 调度器 schedule 调用 proc_run 设置 指针 current 为当前执行PCB 并加载 该进程的 内核栈和页目录表 调用 switch_to 因为 当前进程的 context 其中的 eip 被设置为 forkret(copy_thread 拷贝父进程的中断帧时设置的) 因此 switch_to ret 后 会跳转到 forkret 处 forkret 又会 将栈 设置为 当前进程的trapframe 然后跳到 trapret 此时 trapret 会根据当前进程的trapframe 恢复上下文 最后 退出中断 iret 从系统调用的函数调用路径 返回 切换到用户进程 hello 第一句语句 _start 处 开始执行

练习2: 父进程复制自己的内存空间给子进程(需要编码)

创建子进程的函数do_fork在执行中将拷贝当前进程(即父进程)的用户内存地址空间中的合法内容到新进程中(子进程),完成内存资源的复制。具体是通过copy_range函数(位于kern/mm/pmm.c中)实现的,请补充copy_range的实现,确保能够正确执行。

/* LAB5:EXERCISE2 YOUR CODE
         * replicate content of page to npage, build the map of phy addr of nage with the linear addr start
         *
         * Some Useful MACROs and DEFINEs, you can use them in below implementation.
         * MACROs or Functions:
         *    page2kva(struct Page *page): return the kernel vritual addr of memory which page managed (SEE pmm.h)
         *    page_insert: build the map of phy addr of an Page with the linear addr la
         *    memcpy: typical memory copy function
         *
         * (1) find src_kvaddr: the kernel virtual address of page
         * (2) find dst_kvaddr: the kernel virtual address of npage
         * (3) memory copy from src_kvaddr to dst_kvaddr, size is PGSIZE
         * (4) build the map of phy addr of  nage with the linear addr start
         */
这个函数是用来 拷贝父进程的用户内存地址空间到子进程中 share 此处没用到 不管它
int copy_range(pde_t *to, pde_t *from, uintptr_t start, uintptr_t end, bool share) {
    // 找到父进程的 页虚拟内存地址 和 子进程的 页虚拟内存地址 将 父进程的页 拷贝到 子进程的页
    void* src_kvaddr = page2kva(page);
    void* dst_kvaddr = page2kva(npage);
    memcpy(dst_kvaddr, src_kvaddr, PGSIZE);
    ret = page_insert(to, npage, start, perm);
}

Copy-on-write(简称COW)的基本概念是指如果有多个使用者对一个资源A(比如内存块)进行读操作,则每个使用者只需获得一个指向同一个资源A的指针,就可以该资源了。若某使用者需要对这个资源A进行写操作,系统会对该资源进行拷贝操作,从而使得该“写操作”使用者获得一个该资源A的“私有”拷贝—资源B,可对资源B进行写操作。该“写操作”使用者对资源B的改变对于其他的使用者而言是不可见的,因为其他使用者看到的还是资源A。

练习3: 阅读分析源代码,理解进程执行 fork/exec/wait/exit 的实现,以及系统调用的实现(不需要编码)

请在实验报告中简要说明你对 fork/exec/wait/exit函数的分析。并回答如下问题:

  • 请分析fork/exec/wait/exit在实现中是如何影响进程的执行状态的?

    fork 创建新的 PCB 进程状态为 UNINIT exec 将当前进程的内存布局清除 再调用 load_icode 读出 ELF映像中的内存布局 并填写 进程状态不改变 wait 当前进程若无子进程 则返回错误 若有子进程 则判定 是否为 ZOMBIE 子进程 有则释放子进程的资源 并返回子进程的返回状态码 若无 ZOMBIE 状态子进程 则进入 SLEEPING 状态 等子进程唤醒 exit 清除当前进程几乎所有资源(PCB和内核栈不清除) 将所有子进程(如果有的话)设置为 init 进程(内核) 将当前进程状态设置为 ZOMBIE 若有父进程在等待当前进程exit 则 唤醒父进程

  • 请给出ucore中一个用户态进程的执行状态生命周期图(包执行状态,执行状态之间的变换关系,以及产生变换的事件或函数调用)。(字符方式画即可)

                                             RUNNING----------------+
                                               A |                  |
                                               | |                  |
                                            proc_run()            exit()  
                                               | |                  |
                                               | V                  V
--alloc_page()--> UNINIT --wakeup_proc()--> RUNNABLE --exit()--> ZOMBIE
                                               A                    A
                                               |                    |
                                           子进程exit()            exit()
                                               |                    |
                                               |                    |
                                            SLEEPING----------------+

执行:make grade。如果所显示的应用程序检测都输出ok,则基本正确。(使用的是qemu-1.0.1)

扩展练习 Challenge :实现 Copy on Write 机制

给出实现源码和设计报告。

这个扩展练习涉及到本实验和上一个实验“虚拟内存管理”。在ucore操作系统中,当一个用户父进程创建自己的子进程时,父进程会把其申请的用户空间设置为只读,子进程可共享父进程占用的用户内存空间中的页面(这就是一个共享的资源)。当其中任何一个进程修改此用户内存空间中的某页面时,ucore会通过page fault异常获知该操作,并完成拷贝内存页面,使得两个进程都有各自的内存页面。这样一个进程所做的修改不会被另外一个进程可见了。请在ucore中实现这样的COW机制。

实验六

实验目的

  • 理解操作系统的调度管理机制
  • 熟悉 ucore 的系统调度器框架,以及缺省的Round-Robin 调度算法
  • 基于调度器框架实现一个(Stride Scheduling)调度算法来替换缺省的调度算法

实验内容

实验五完成了用户进程的管理,可在用户态运行多个进程。但到目前为止,采用的调度策略是很简单的FIFO调度策略。本次实验,主要是熟悉ucore的系统调度器框架,以及基于此框架的Round-Robin(RR) 调度算法。然后参考RR调度算法的实现,完成Stride Scheduling调度算法。

练习0:填写已有实验

本实验依赖实验1/2/3/4/5/6。请把你做的实验1/2/3/4/5/6的代码填入本实验中代码中有“LAB1”/“LAB2”/“LAB3”/“LAB4”/“LAB5”/“LAB6”的注释相应部分。并确保编译通过。注意:为了能够正确执行lab7的测试应用程序,可能需对已完成的实验1/2/3/4/5/6的代码进行进一步改进。

同前面lab,用meld进行代码合并 修改代码如下

// alloc_proc - alloc a proc_struct and init all fields of proc_struct
static struct proc_struct *
alloc_proc(void) {
    struct proc_struct *proc = kmalloc(sizeof(struct proc_struct));
    if (proc != NULL) {
    //LAB4:EXERCISE1 YOUR CODE
    /*
     * below fields in proc_struct need to be initialized
     *       enum proc_state state;                      // Process state
     *       int pid;                                    // Process ID
     *       int runs;                                   // the running times of Proces
     *       uintptr_t kstack;                           // Process kernel stack
     *       volatile bool need_resched;                 // bool value: need to be rescheduled to release CPU?
     *       struct proc_struct *parent;                 // the parent process
     *       struct mm_struct *mm;                       // Process's memory management field
     *       struct context context;                     // Switch here to run process
     *       struct trapframe *tf;                       // Trap frame for current interrupt
     *       uintptr_t cr3;                              // CR3 register: the base addr of Page Directroy Table(PDT)
     *       uint32_t flags;                             // Process flag
     *       char name[PROC_NAME_LEN + 1];               // Process name
     */
     //LAB5 YOUR CODE : (update LAB4 steps)
    /*
     * below fields(add in LAB5) in proc_struct need to be initialized    
     *       uint32_t wait_state;                        // waiting state
     *       struct proc_struct *cptr, *yptr, *optr;     // relations between processes
     */
     //LAB6 YOUR CODE : (update LAB5 steps)
    /*
     * below fields(add in LAB6) in proc_struct need to be initialized
     *     struct run_queue *rq;                       // running queue contains Process
     *     list_entry_t run_link;                      // the entry linked in run queue
     *     int time_slice;                             // time slice for occupying the CPU
     *     skew_heap_entry_t lab6_run_pool;            // FOR LAB6 ONLY: the entry in the run pool
     *     uint32_t lab6_stride;                       // FOR LAB6 ONLY: the current stride of the process
     *     uint32_t lab6_priority;                     // FOR LAB6 ONLY: the priority of process, set by lab6_set_priority(uint32_t)
     */
        proc->state = PROC_UNINIT;//设置进程为未初始化状态
        proc->pid = -1;          //未初始化的进程id=-1
        proc->runs = 0;          //初始化时间片
        proc->kstack = 0;      //初始化内存栈的地址
        proc->need_resched = 0;   //是否需要调度设为不需要
        proc->parent = NULL;      //置空父节点
        proc->mm = NULL;      //置空虚拟内存
        memset(&(proc->context), 0, sizeof(struct context));//初始化上下文
        proc->tf = NULL;      //中断帧指针设置为空
        proc->cr3 = boot_cr3;      //页目录设为内核页目录表的基址
        proc->flags = 0;      //初始化标志位
        memset(proc->name, 0, PROC_NAME_LEN);//置空进程名
        proc->wait_state = 0;  //初始化进程等待状态  
        //*cptr-->children | *yptr-->younger | *optr-->older 
        proc->cptr=proc->yptr=proc->optr = NULL;//进程相关指针初始化  
        proc->rq = NULL;//置运行队列为空
        //该进程的调度链表结构,该结构内部的链接组成了运行队列列表
        list_init(&(proc->run_link));//初始化运行队列的指针
        //该进程剩余的时间片,只对当前进程有效
        proc->time_slice = 0;//初始化时间片
        //该进程在优先队列中的节点,仅在lab6中使用
        proc->lab6_run_pool.left = proc->lab6_run_pool.right = proc->lab6_run_pool.parent = NULL; //初始化各类指针为空
        //该进程的调度步进值,仅在lab6中使用
        proc->lab6_stride = 0;//初始化当前运行步数
        //该进程的调度优先级,仅在lab6中使用
        proc->lab6_priority = 0;//初始化优先级
    }
    return proc;
}

练习1: 使用 Round Robin 调度算法(不需要编码)

完成练习0后,建议大家比较一下(可用kdiff3等文件比较软件)个人完成的lab5和练习0完成后的刚修改的lab6之间的区别,分析了解lab6采用RR调度算法后的执行过程。执行make grade,大部分测试用例应该通过。但执行priority.c应该过不去。

请在实验报告中完成:

  • 请理解并分析sched_calss中各个函数指针的用法,并接合Round Robin 调度算法描ucore的调度执行过程

让所有runnable态的进程分时轮流使用CPU时间。RR调度器维护当前runnable进程的有序运行队列。当前进程的时间片用完之后,调度器将当前进程放置到运行队列的尾部,再从其头部取出进程进行调度。

  RR调度算法的就绪队列在组织结构上也是一个双向链表,只是增加了一个成员变量,表明在此就绪进程队列中的最大执行时间片。而且在进程控制块proc_struct中增加了一个成员变量time_slice,用来记录进程当前的可运行时间片段。这是由于RR调度算法需要考虑执行进程的运行时间不能太长。在每个timer到时的时候,操作系统会递减当前执行进程的time_slice,当time_slice为0时,就意味着这个进程运行了一段时间(这个时间片段称为进程的时间片),需要把CPU让给其他进程执行,于是操作系统就需要让此进程重新回到rq的队列尾,且重置此进程的时间片为就绪队列的成员变量最大时间片max_time_slice值,这表示如果进程在当前的执行时间片已经用完,需要等到下一次有机会运行时,才能再执行一段时间,然后再从rq的队列头取出一个新的进程执行。

RR_init函数

首先RR_init完成了对进程队列的初始化

RR_enqueue函数

它把进程的进程控制块指针放入到rq队列末尾,且如果进程控制块的时间片为0,则需要把它重置为max_time_slice。这表示如果进程在当前的执行时间片已经用完,需要等到下一次有机会运行时,才能再执行一段时间。然后在依次调整rq和rq的进程数目加

###RR_dequeue函数 把就绪进程队列rq的进程控制块指针的队列元素删除,并把表示就绪进程个数的proc_num减一。

RR_pick_next函数

选取函数,即选取就绪进程队列rq中的队头队列元素,并把队列元素转换成进程控制块指针。

  • 请在实验报告中简要说明如何设计实现”多级反馈队列调度算法“,给出概要设计,鼓励给出详细设计

RR_proc_tick函数

即每一次时间片到时的时候,当前执行进程的时间片time_slice便减一。如果time_slice降到零,则设置此进程成员变量need_resched标识为1,设置为需要调度,这样在下一次中断来后执行trap函数时,会执行schedule函数,然后把当前执行进程放回就绪队列末尾,而从就绪队列头取出等待时间最久的那个就绪进程执行。

default_sched_class

定义一个c语言类的实现,提供调度算法的切换接口

练习2: 实现 Stride Scheduling 调度算法(需要编码)

首先需要换掉RR调度器的实现,即用default_sched_stride_c覆盖default_sched.c。然后根据此文件和后续文档对Stride度器的相关描述,完成Stride调度算法的实现。

首先,根据的要求覆盖掉Round Robin调度算法。 覆盖掉之后需要在该框架上实现Stride Scheduling调度算法。    1、为每个runnable的进程设置一个当前状态stride,表示该进程当前的调度权。另外定义其对应的pass值,表示对应进程在调度后,stride 需要进行的累加值。 2、每次需要调度时,从当前 runnable 态的进程中选择 stride最小的进程调度。对于获得调度的进程P,将对应的stride加上其对应的步长pass(只与进程的优先权有关系)。 3、在一段固定的时间之后,回到步骤2,重新调度当前stride最小的进程

proc_stride_comp_f函数

/* You should define the BigStride constant here*/  
/* LAB6: YOUR CODE */  
#define BIG_STRIDE    0x7FFFFFFF /* 定义一个大整数处以优先级 */  

/* The compare function for two skew_heap_node_t's and the 
 * corresponding procs*/  
static int  
proc_stride_comp_f(void *a, void *b)  
{  
     struct proc_struct *p = le2proc(a, lab6_run_pool);  
     struct proc_struct *q = le2proc(b, lab6_run_pool);  
     int32_t c = p->lab6_stride - q->lab6_stride;//步数相减,通过正负比较大小关系  
     if (c > 0) return 1;  
     else if (c == 0) return 0;  
     else return -1;  
}

stride_init函数

首先初始化调度器类的信息,初始化运行队列为一个空的容器结构,然后设置当前运行队列内进程数目为0。

/*
 * stride_init initializes the run-queue rq with correct assignment for
 * member variables, including:
 *
 *   - run_list: should be a empty list after initialization.
 *   - lab6_run_pool: NULL
 *   - proc_num: 0
 *   - max_time_slice: no need here, the variable would be assigned by the caller.
 *
 * hint: see libs/list.h for routines of the list structures.
 */
static void
stride_init(struct run_queue *rq) {
     /* LAB6: YOUR CODE 
      * (1) init the ready process list: rq->run_list
      * (2) init the run pool: rq->lab6_run_pool
      * (3) set number of process: rq->proc_num to 0       
      */
    list_init(&(rq->run_list));//初始化调度器类的信息  
    rq->lab6_run_pool = NULL;//初始化当前的运行队列为一个空的容器结构。  
    rq->proc_num = 0;//设置rq->proc_num为 0  
}

stride_enqueue函数

初始化刚进入运行队列的进程proc的stride属性。 比较队头元素与当前进程的步数大小,选择步数最小的运行,将proc插入放入运行队列中去(注意:这里并不要求放置在队列头部)。 最后初始化时间片,然后将运行队列进程数目加一。

/* 
 * stride_enqueue inserts the process ``proc'' into the run-queue 
 * ``rq''. The procedure should verify/initialize the relevant members 
 * of ``proc'', and then put the ``lab6_run_pool'' node into the 
 * queue(since we use priority queue here). The procedure should also 
 * update the meta date in ``rq'' structure. 
 * 
 * proc->time_slice denotes the time slices allocation for the 
 * process, which should set to rq->max_time_slice. 
 *  
 * hint: see proj13.1/libs/skew_heap.h for routines of the priority 
 * queue structures. 
 */  
static void  
stride_enqueue(struct run_queue *rq, struct proc_struct *proc) {  
    /* LAB6: YOUR CODE */  
    #if USE_SKEW_HEAP  
    //在使用优先队列的实现中表示当前优先队列的头元素
    rq->lab6_run_pool = skew_heap_insert(rq->lab6_run_pool, &(proc->lab6_run_pool), proc_stride_comp_f);//比较队头元素与当前进程的步数大小,选择步数最小的运行  
    #else  
    assert(list_empty(&(proc->run_link)));  
    list_add_before(&(rq->run_list), &(proc->run_link));//将 proc插入放入运行队列中去  
    #endif  
    if (proc->time_slice == 0 || proc->time_slice > rq->max_time_slice) 
    {//初始化时间片  
        proc->time_slice = rq->max_time_slice;  
    }  
    proc->rq = rq;  
    rq->proc_num ++;  
}

stride_dequeue函数

从运行队列中删除相应的元素,完成将一个进程从队列中移除的功能,使用优先队列。最后运行队列数目减一。

/* 
 * stride_dequeue removes the process ``proc'' from the run-queue 
 * ``rq'', the operation would be finished by the skew_heap_remove 
 * operations. Remember to update the ``rq'' structure. 
 * 
 * hint: see proj13.1/libs/skew_heap.h for routines of the priority 
 * queue structures. 
 */  
static void  
stride_dequeue(struct run_queue *rq, struct proc_struct *proc) {  
     /* LAB6: YOUR CODE */  
#if USE_SKEW_HEAP  
     rq->lab6_run_pool =   
          skew_heap_remove(rq->lab6_run_pool, &(proc->lab6_run_pool), proc_stride_comp_f);// 在斜堆中删除相应元素  
#else  
     assert(!list_empty(&(proc->run_link)) && proc->rq == rq);  
     list_del_init(&(proc->run_link));// 从运行队列中删除相应元素  
#endif  
     rq->proc_num --;  
}

stride_pick_next函数

扫描整个运行队列,返回其中stride值最小的对应进程。 更新对应进程的stride值,即pass = BIG_STRIDE / P->priority; P->stride += pass。将步长设置为优先级的倒数,如果为0则设置为最大的步长。

/* 
 * stride_pick_next pick the element from the ``run-queue'', with the 
 * minimum value of stride, and returns the corresponding process 
 * pointer. The process pointer would be calculated by macro le2proc, 
 * see proj13.1/kern/process/proc.h for definition. Return NULL if 
 * there is no process in the queue. 
 * 
 * When one proc structure is selected, remember to update the stride 
 * property of the proc. (stride += BIG_STRIDE / priority) 
 * 
 * hint: see proj13.1/libs/skew_heap.h for routines of the priority 
 * queue structures. 
 */  
static struct proc_struct *  
stride_pick_next(struct run_queue *rq) {  
    /* LAB6: YOUR CODE */  
#if USE_SKEW_HEAP  
    if (rq->lab6_run_pool == NULL) 
    {
        return NULL;  
    }
    //找到相应指针指向rq->lab6_run_pool
    struct proc_struct *p = le2proc(rq->lab6_run_pool, lab6_run_pool);   
#else  
    list_entry_t *le = list_next(&(rq->run_list));  

    if (le == &rq->run_list)  
    {
        return NULL;
    }


    struct proc_struct *p = le2proc(le, run_link);  
    le = list_next(le);  
    while (le != &rq->run_list)  
    {  
        struct proc_struct *q = le2proc(le, run_link);  
        if ((int32_t)(p->lab6_stride - q->lab6_stride) > 0)  
        {
            p = q;  
        }
        le = list_next(le);  
    }  
#endif  
    if (p->lab6_priority == 0)//优先级设置  
    {
        //步长为0则设置为最大步长保持相减的有效性 
        p->lab6_stride += BIG_STRIDE;
    }    
    else 
    {
        //步长设置为优先级的倒数  
        p->lab6_stride += BIG_STRIDE / p->lab6_priority;
    }
    return p;  
}  

stride_proc_tick函数

检测当前进程是否已用完分配的时间片。如果时间片用完,应该正确设置进程结构的相关标记来引起进程切换。 一个 process 最多可以连续运行 rq.max_time_slice个时间片。 具体思想同RR算法思想

/* 
 * stride_proc_tick works with the tick event of current process. You 
 * should check whether the time slices for current process is 
 * exhausted and update the proc struct ``proc''. proc->time_slice 
 * denotes the time slices left for current 
 * process. proc->need_resched is the flag variable for process 
 * switching. 
 */  
static void  
stride_proc_tick(struct run_queue *rq, struct proc_struct *proc) {  
     /* LAB6: YOUR CODE */  
    if (proc->time_slice > 0) 
    {  
        proc->time_slice --;  
    }  
    if (proc->time_slice == 0) 
    {  
        proc->need_resched = 1;  
    }  
}  

default_sched_class

定义一个c语言类的实现,提供调度算法的切换接口


struct sched_class default_sched_class = {  
     .name = "stride_scheduler",  
     .init = stride_init,  
     .enqueue = stride_enqueue,  
     .dequeue = stride_dequeue,  
     .pick_next = stride_pick_next,  
     .proc_tick = stride_proc_tick,  
}; 

结果

实验1结果:

实验2 结果:

实验7

还没填坑。。。。

本文链接:https://www.haolovej.com/post/uCore_OS.html

-- EOF --

Comments

评论加载中...

注:如果长时间无法加载,请针对 disq.us | disquscdn.com | disqus.com 启用代理。