Skip to content
GitLab
user avatar
update report
unknown authored
440dd320
Select Git revision
  • main default
  • master
History Find file
Clone
Name Last commit Last update
K210-Linux0.11-master
OS_design
doc
read_source
rubbish
test
testsuits-for-oskernel-main
README.md
oscomp-syscall.md
README.md

操作系统大赛 2022 内核实现赛道

团队：LED

目录

情况概述

我们是来自中国科学技术大学的大二本科生团队 LED，共有三名成员：马子睿，赵博言，万方。

在操作系统大赛 2022 中，我们选择使用 Sipeed Maix Dock K210开发板，用 c/c++ 实现一个基于 RISC-V 架构的简易操作系统。

由于时间问题，我们并未能如期完成完整内核，但我们仍决定将已经完成的部分上传。

正式报告放在/doc/report.md

系统框架和模块设计

系统启动部分

首先，令 start64.S 作为 bootloader 进行操作系统启动前的引导：

  • 设置栈空间的大小和基地址位置
  • 创建单一的硬件线程 hart
  • 设置 bss 段空间并完成初始化
  • 调转到内核初始化程序 OS_Start.c

在 OS_Start.c 程序中，完成硬件和系统的初始化，并阻塞等待（轮询方式）。

考虑到硬件模块的使用和内核已实现功能的调用，具体执行以下方面的初始化：

  • uart 模块：硬件结构实现对部分状态寄存器、指令和变址寄存器、段寄存器的设置
  • memory 中进行对内存的初始声明和分配（同时输出 Debug 信息）
  • trap 和 plic 模块开始接受中断的请求，shedule 实现进程队列结构并可以选择合适的就绪进程后，系统就可以正常处理任务的分配
  • 由于要把操作系统的执行转换到硬件的信号上，还需要令 fpioa 关于串口的部分进行初始化
  • 为了支持抢占式多任务，我们实现了定时器中断，timer 开始按时间片赋予进程执行周期

进程调度部分

进程调度分为抢占式和非抢占式，我们需要及时地响应中断（线程正常退出的中断、执行异常的中断、定时器中断），并做出正确的回应：进程调度（包含上下文切换）、系统调用等。

trap_handler 在处理相关问题时，把相关控制权交给 syscall、schedule、error_fix 等函数。

因此在实现内核进程调度时我们选择了时间片轮转算法（RR）。

内存管理部分

如上文系统启动部分所述，内存空间初始时就设置了堆空间(heap)、text 段、data 段、rodata 段、bss 段的起始位置和大小。

我们分出了用户空间和内核空间，用于后续开发时对用户态提供更好的支持。

我们用分段管理实现了首先适配算法的内存分配。

在释放内存空间时，我们做了一点小小的改进：如果 free 了一个内存块，在其与前后两块合并时可以延迟操作。

其他功能部分

同步和互斥

初步实现了同步和互斥的模块，并进行了简易测试，功能正确。

具体实现上，我们构建了 lock 结构体，使用 __sync_lock_test_and_set 完成互斥内容。

shell

我们在 shell 功能上也做出了部分工作：

  • 通过字符串处理读入一行用户指令
  • 对用户指令进行分割和格式化处理
  • 通过指令类别（argv[0]）在已实现的 command list 中进行检索，返回匹配到的功能的指针
  • 对功能函数进行调用，正确地执行指令

这样，一个简易的 shell 就实现了，在我们的内核开发中主要用于 Debug。

系统调用

为了便于协作和统筹管理，我们设置系统了调用表，团队成员分工完成不同模块的 syscall。

在执行系统调用时，直接找到 syscall_num 对应的系统调用函数，跳转执行即可。

但很遗憾的一点是，我们在完成任务时没有与评测样例对应，这也是我们后期任务崩盘的主要因素之一。

作品特征描述

一个简单的运行在 K210 上的内核，能够实现部分基本功能，包括输入输出，中断，抢占式任务调度等。

  • 基于 K210 本身内存只有 6M 的客观因素，我们决定放弃使用分页式存储（这会造成部分内存被页表等非必要支出被占据），改为使用块式链表存储，虽然是较为老旧的算法，但在这特定硬件上仍有较为优秀的表现。
  • 抢占式进程调度，保证高优先级任务能被有限执行，同时设置优先级提高策略，防止饿死情况。

提交仓库目录和文件描述

我们项目的关键部分文件树如下：

（省略了交流记录文档、硬件参考资料、芯片手册、linux-0.11 参考项目等）

.
├── common.mk
├── LED_OS
│   ├── dev
│   │   ├── dev.mk
│   │   ├── fpioa.c
│   │   └── uart.c
│   ├── include
│   │   ├── command.h
│   │   ├── dpart.h
│   │   ├── fpioa.h
│   │   ├── interrupt.h
│   │   ├── io.h
│   │   ├── k210.h
│   │   ├── kernel_io.h
│   │   ├── kmalloc.h
│   │   ├── lock.h
│   │   ├── main.h
│   │   ├── malloc.h
│   │   ├── mem.h
│   │   ├── riscv.h
│   │   ├── schedule.h
│   │   ├── shell.h
│   │   ├── string.h
│   │   ├── syscall_cope.h
│   │   ├── syscall_user.h
│   │   ├── timer.h
│   │   ├── type.h
│   │   ├── uart.h
│   │   └── vsprintf.h
│   ├── kernel
│   │   ├── interrupt
│   │   │   ├── interrupt.mk
│   │   │   ├── plic.c
│   │   │   ├── trap.c
│   │   │   └── trap_vector.S
│   │   ├── kernel.mk
│   │   ├── lock
│   │   │   ├── lock.c
│   │   │   └── lock.mk
│   │   ├── memory
│   │   │   ├── dpart.c
│   │   │   ├── malloc.c
│   │   │   ├── mem_init.c
│   │   │   ├── memory.mk
│   │   │   └── memory.S
│   │   ├── schedule
│   │   │   ├── schedule.c
│   │   │   ├── schedule.mk
│   │   │   └── switch.S
│   │   ├── syscall
│   │   │   ├── syscall.c
│   │   │   ├── syscall_entry.S
│   │   │   └── syscall.mk
│   │   └── timer
│   │       ├── timer.c
│   │       └── timer.mk
│   ├── LED_OS.mk
│   ├── lib
│   │   ├── lib.mk
│   │   └── string.c
│   ├── os.ld
│   ├── OS_Start.c
│   ├── printf
│   │   ├── printf.c
│   │   ├── printf.mk
│   │   └── vsprintf.c
│   └── start64.S
├── LED_OS USAGE.md
├── Makefile
├── output
│   ├── LED_OS
│   │   ├── dev
│   │   │   ├── fpioa.o
│   │   │   └── uart.o
│   │   ├── kernel
│   │   │   ├── interrupt
│   │   │   │   ├── plic.o
│   │   │   │   ├── trap.o
│   │   │   │   └── trap_vector.o
│   │   │   ├── lock
│   │   │   │   └── lock.o
│   │   │   ├── memory
│   │   │   │   ├── dpart.o
│   │   │   │   ├── malloc.o
│   │   │   │   ├── mem_init.o
│   │   │   │   └── memory.o
│   │   │   ├── schedule
│   │   │   │   ├── schedule.o
│   │   │   │   └── switch.o
│   │   │   ├── syscall
│   │   │   │   ├── syscall_entry.o
│   │   │   │   └── syscall.o
│   │   │   └── timer
│   │   │       └── timer.o
│   │   ├── lib
│   │   │   └── string.o
│   │   ├── OS_Start.o
│   │   ├── printf
│   │   │   ├── printf.o
│   │   │   └── vsprintf.o
│   │   └── start64.o
│   ├── LED_OS.bin
│   └── userapp
│       ├── cmd_func.o
│       ├── lock_test.o
│       ├── main.o
│       ├── memory_test.o
│       ├── shell.o
│       └── trap_test.o
├── rubbish
│   ├── block.c
│   ├── block.h
│   ├── lock_test.h
│   ├── memory_test.h
│   ├── page.c
│   ├── page.h
│   └── trap_test.h
└── userapp
    ├── cmd_func.c
    ├── lock_test.c
    ├── main.c
    ├── memory_test.c
    ├── shell.c
    ├── test.h
    ├── trap_test.c
    └── user.mk

27 directories, 99 files

文件的组织方式参考 PLCT 提供内核学习课程的组织规范。

  • rubbish：被团队丢弃的实现方法，如上文提到的效率并不优秀的页分配等
  • userapp：与用户进行交互的部分，包括 shell 以及多个模块（互斥、内存分配、陷阱..）的 Debug 功能
  • output：存储编译生成的对象文件
  • LED_OS：实现的内核项目源码
    • dev：包含内核使用的外部设备，但不包含外部设备驱动信息
    • include：头文件文件夹
    • printf ：实现的内核输出函数
    • OS_Start.c 和 start64.S 上文解释过，分别为内核执行函数和内核进入初始化文件
    • kernel 包含了操作系统内核各个功能的实现代码（功能与命名一致）
      • interrupt：实现中断
      • lock：实现互斥锁，进程可以同步
      • memory：实现内存管理
      • schedule：实现进程调度
      • syscall：实现部分系统调用
      • timer：实现定时器功能，可以进行时间片轮状调度（RR）