首页 计算机 操作系统

# 概述

这是关于操作系统课设的一个简单总结。课设内容为完成 MIT: 6.s081-2021 的相关实验。

# Lab: Xv6 and Unix utilities

Lab: Xv6 and Unix utilities 是 6.s081 系列的第一组实验，其目标是调用部分系统调用，实现部分程序要求。

# sleep (easy)

关于 sleep 的任务要求原文如下：

Implement the UNIX program sleep for xv6; your sleep should pause for a user-specified number of ticks. A tick is a notion of time defined by the xv6 kernel, namely the time between two interrupts from the timer chip. Your solution should be in the file user/sleep.c .

Some hints:

  • Before you start coding, read Chapter 1 of the xv6 book.
  • Look at some of the other programs in user/ (e.g., user/echo.c , user/grep.c , and user/rm.c ) to see how you can obtain the command-line arguments passed to a program.
  • If the user forgets to pass an argument, sleep should print an error message.
  • The command-line argument is passed as a string; you can convert it to an integer using atoi (see user/ulib.c ).
  • Use the system call sleep .
  • See kernel/sysproc.c for the xv6 kernel code that implements the sleep system call (look for sys_sleep ), user/user.h for the C definition of sleep callable from a user program, and user/usys.S for the assembler code that jumps from user code into the kernel for sleep .
  • Make sure main calls exit() in order to exit your program.
  • Add your sleep program to UPROGS in Makefile; once you've done that, make qemu will compile your program and you'll be able to run it from the xv6 shell.
  • Look at Kernighan and Ritchie's book The C programming language (second edition) (K&R) to learn about C.

# xargs (moderate)

xargs 是 Linux 中的一个重要指令，用来实现标准输入和文件输入的格式转换，以及输入参数的整合。其命令格式如下：

somecommand |xargs -item command

# Lab: system calls

Lab: system calls 是 6.s081 系列的第二组实验，其目标是设计一些系统调用，以深入了解 xv6 内核中的系统调用规则及实现。

# System call tracing

In this assignment you will add a system call tracing feature that may help you when debugging later labs. You'll create a new trace system call that will control tracing. It should take one argument, an integer "mask", whose bits specify which system calls to trace. For example, to trace the fork system call, a program calls trace(1 << SYS_fork) , where SYS_fork is a syscall number from kernel/syscall.h . You have to modify the xv6 kernel to print out a line when each system call is about to return, if the system call's number is set in the mask. The line should contain the process id, the name of the system call and the return value; you don't need to print the system call arguments. The trace system call should enable tracing for the process that calls it and any children that it subsequently forks, but should not affect other processes.

Some hints:

  • Add $U/_trace to UPROGS in Makefile.
  • Run make qemu and you will see that the compiler cannot compile user/trace.c , because the user-space stubs for the system call don't exist yet: add a prototype for the system call to user/user.h , a stub to user/usys.pl , and a syscall number to kernel/syscall.h . The Makefile invokes the perl script user/usys.pl , which produces user/usys.S , the actual system call stubs, which use the RISC-V ecall instruction to transition to the kernel. Once you fix the compilation issues, run trace 32 grep hello README ; it will fail because you haven't implemented the system call in the kernel yet.
  • Add a sys_trace() function in kernel/sysproc.c that implements the new system call by remembering its argument in a new variable in the proc structure (see kernel/proc.h ). The functions to retrieve system call arguments from user space are in kernel/syscall.c , and you can see examples of their use in kernel/sysproc.c .
  • Modify fork() (see kernel/proc.c ) to copy the trace mask from the parent to the child process.
  • Modify the syscall() function in kernel/syscall.c to print the trace output. You will need to add an array of syscall names to index into.

完成步骤：(主要参考 lhw---9999: xv6 实验课程 -- 系统调用)

  1. 在 Makefile 的 UPROGS 项中加入 $U/_trace\ .
  2. 包括以下步骤：
    1. 在系统调用头文件 user/user.h 中加入 int trace(uint);
    2. 在 Perl 脚本 user/usys.pl 中加入 entry("trace"); 作为动态链接的调用入口 (存根，stub).
    3. 在 kernel/syscall.h 中加入系统调用号 #define SYS_trace 22 .
  3. 在 kernel/sysproc.c 中加入函数 sys_trace() . 注意需要自定义数组 char* syscall_name[24] , 在定义时需要将数组范围开大一点。

# Sysinfo

In this assignment you will add a system call, sysinfo , that collects information about the running system. The system call takes one argument: a pointer to a struct sysinfo (see kernel/sysinfo.h ). The kernel should fill out the fields of this struct: the freemem field should be set to the number of bytes of free memory, and the nproc field should be set to the number of processes whose state is not UNUSED . We provide a test program sysinfotest ; you pass this assignment if it prints "sysinfotest: OK".

Some hints:

  • Add $U/_sysinfotest\ to UPROGS in Makefile
  • Run make qemu ; user/sysinfotest.c will fail to compile. Add the system call sysinfo , following the same steps as in the previous assignment. To declare the prototype for sysinfo() in user/user.h you need predeclare the existence of struct sysinfo:
struct sysinfo;
 int sysinfo(struct sysinfo *);
  • Once you fix the compilation issues, run sysinfotest ; it will fail because you haven't implemented the system call in the kernel yet.
  • sysinfo needs to copy a struct sysinfo back to user space; see sys_fstat() ( kernel/sysfile.c ) and filestat() ( kernel/file.c ) for examples of how to do that using copyout() .
  • To collect the amount of free memory, add a function to kernel/kalloc.c
  • To collect the number of processes, add a function to kernel/proc.c

# Lab: page tables

Lab: page tables 是 6.s081 系列第三组实验，其目的是掌握页表的相关内容。

# Speed up system calls (easy)

一些操作系统通过在内核和用户空间之间的部分只读区域进行数据共享，以加快系统调用速度。这样做可以避免调用不同系统调用产生跨内核现象。

第一个实验需要实现系统调用 getpid() 的优化，从而帮助更好理解如何在页表中插入映射。

pid 位于 kernel/memlayout.h 中。

When each process is created, map one read-only page at USYSCALL (a VA defined in memlayout.h ). At the start of this page, store a struct usyscall (also defined in memlayout.h ), and initialize it to store the PID of the current process. For this lab, ugetpid() has been provided on the userspace side and will automatically use the USYSCALL mapping. You will receive full credit for this part of the lab if the ugetpid test case passes when running pgtbltest .

Some hints:

  • You can perform the mapping in proc_pagetable() in kernel/proc.c .
  • Choose permission bits that allow userspace to only read the page.
  • You may find that mappages() is a useful utility.
  • Don't forget to allocate and initialize the page in allocproc() .
  • Make sure to free the page in freeproc() .

<img src="../../images/OS/lab01.png" alt="" style="zoom:80%;" />

在 kernel/vm.c 中的函数声明如下 (见 kernel/defs.h )：

void            kvminit(void);
void            kvminithart(void);
void            kvmmap(pagetable_t, uint64, uint64, uint64, int);
int             mappages(pagetable_t, uint64, uint64, uint64, int);
pagetable_t     uvmcreate(void);
void            uvminit(pagetable_t, uchar *, uint);
uint64          uvmalloc(pagetable_t, uint64, uint64);
uint64          uvmdealloc(pagetable_t, uint64, uint64);
int             uvmcopy(pagetable_t, pagetable_t, uint64);
void            uvmfree(pagetable_t, uint64);
void            uvmunmap(pagetable_t, uint64, uint64, int);
void            uvmclear(pagetable_t, uint64);
uint64          walkaddr(pagetable_t, uint64);
int             copyout(pagetable_t, uint64, char *, uint64);
int             copyin(pagetable_t, char *, uint64, uint64);
int             copyinstr(pagetable_t, char *, uint64, uint64);
pte_t *         walk(pagetable_t pagetable, uint64 va, int alloc);

其中比较关键的包括：

  1. void kvmmap : 在装入程序时添加一个内核页表。
  2. void uvminit : 对页表首地址进行初始化。
  3. pte_t walk() : 返回页表中 PTE 的地址。

步骤：

# Print a page table (easy)

要求和提示如下：

Define a function called vmprint(). It should take a pagetable_t argument, and print that pagetable in the format described below. Insert if(p->pid==1) vmprint(p->pagetable) in exec.c just before the return argc, to print the first process's page table. You receive full credit for this part of the lab if you pass the pte printout test of make grade.

Some hints:

  • You can put vmprint() in kernel/vm.c .
  • Use the macros at the end of the file kernel/riscv.h.
  • The function freewalk may be inspirational.
  • Define the prototype for vmprint in kernel/defs.h so that you can call it from exec.c.
  • Use %p in your printf calls to print out full 64-bit hex PTEs and addresses as shown in the example.

# Detecting which pages have been accessed (hard)

In this part of the lab, you will add a new feature to xv6 that detects and reports this information to userspace by inspecting the access bits in the RISC-V page table. The RISC-V hardware page walker marks these bits in the PTE whenever it resolves a TLB miss.

即要求在页表中新加入一个标志位，用来检测该页表的获取情况。

要求和提示如下：

Your job is to implement pgaccess(), a system call that reports which pages have been accessed. The system call takes three arguments. First, it takes the starting virtual address of the first user page to check. Second, it takes the number of pages to check. Finally, it takes a user address to a buffer to store the results into a bitmask (a datastructure that uses one bit per page and where the first page corresponds to the least significant bit). You will receive full credit for this part of the lab if the pgaccess test case passes when running pgtbltest.

对应的提示如下：

  • Start by implementing sys_pgaccess() in kernel/sysproc.c .
  • You'll need to parse arguments using argaddr() and argint() .

int argaddr(int n, uint64 *ip) 将一个参数检索为一个指针，而不检验指针合法性。

int argint(int n, int *ip) : 获取第 n 个 32 位系统调用参数。

  • For the output bitmask, it's easier to store a temporary buffer in the kernel and copy it to the user (via copyout() ) after filling it with the right bits.
  • It's okay to set an upper limit on the number of pages that can be scanned.
  • walk() in kernel/vm.c is very useful for finding the right PTEs.
  • You'll need to define PTE_A, the access bit, in kernel/riscv.h . Consult the RISC-V manual to determine its value.
  • Be sure to clear PTE_A after checking if it is set. Otherwise, it won't be possible to determine if the page was accessed since the last time pgaccess() was called (i.e., the bit will be set forever).
  • vmprint() may come in handy to debug page tables.

步骤：

  1. 首先需要在 PTE 中定义一个标志位 PTE_A 表示当前 PTE 是否已经被获取 (hint 6)。
  2. 在 kernel/sysproc.c 中完成程序：
    1. 采用 argaddr() 及 argint() 解析参数

<img src="../../images/OS/lab02.png" alt="" style="zoom:80%;" />

# Lab: Traps

# Alarm(hard)

目的是实现一个新的系统调用 sigalarm(interval, handler) , 其中 interval 表示 alarm 周期， handler 是一个函数指针。

# Test0 invoke handler

下面是一些提示：

  • You'll need to modify the Makefile to cause alarmtest.c to be compiled as an xv6 user program.
  • The right declarations to put in user/user.h are:
int sigalarm(int ticks, void (*handler)());
    int sigreturn(void);
  • Update user/usys.pl (which generates user/usys.S ), kernel/syscall.h , and kernel/syscall.c to allow alarmtest to invoke the sigalarm and sigreturn system calls.
  • For now, your sys_sigreturn should just return zero.
  • Your sys_sigalarm() should store the alarm interval and the pointer to the handler function in new fields in the proc structure (in kernel/proc.h ).
  • You'll need to keep track of how many ticks have passed since the last call(defined as ticks in proc.h ) to a process's alarm handler; you'll need a new field in struct proc for this too. You can initialize proc fields in allocproc() in proc.c .(OK)
  • Every tick, the hardware clock forces an interrupt, which is handled in usertrap() in kernel/trap.c .
  • You only want to manipulate a process's alarm ticks if there's a timer interrupt; you want something like
if(which_dev == 2) ...
  • Only invoke the alarm function if the process has a timer outstanding. Note that the address of the user's alarm function might be 0 (e.g., in user/alarmtest.asm , periodic is at address 0). ????
  • You'll need to modify usertrap() so that when a process's alarm interval expires, the user process executes the handler function. When a trap on the RISC-V returns to user space, what determines the instruction address at which user-space code resumes execution?
  • It will be easier to look at traps with gdb if you tell qemu to use only one CPU, which you can do by running
make CPUS=1 qemu-gdb
  • You've succeeded if alarmtest prints "alarm!".

# Test1/test2(): resume interrupted code

又是一些 hints:

  • Your solution will require you to save and restore registers---what registers do you need to save and restore to resume the interrupted code correctly? (Hint: it will be many).
  • Have usertrap save enough state in struct proc when the timer goes off that sigreturn can correctly return to the interrupted user code.
  • Prevent re-entrant calls to the handler----if a handler hasn't returned yet, the kernel shouldn't call it again. test2 tests this.

Debug:
已经完成了寄存器保存和恢复，寄存器保存位于 trap.c 的 usertrap 中，恢复位于 proc.c 的 sys_sigreturn 中。

# Lab: Copy-on-Write Fork for xv6

# Reference

  • Lab6: Copy-on-Write Fork for xv6 详解
  • 6.S081 lab 6: Copy-on-Write Fork for xv6

# Lab6： MultiThreading

# Reference

  • Lab:multithreading
  • Lab7: Multithreading

# Lab7: networking

# Reference

  • duile:MIT6.S081-Lab7 Lab Networking [2021Fall]

# Lab8: Locks

# Reference

  • xv6 6.S081 Lab7: Lock
  • Mit6.S081 - 实验 8-locks
  • [mit6.s081] 笔记 Lab8: Locks | 锁优化
  • duile: MIT6.S081-Lab8 Lock [2021Fall]

无锁队列的理解？

  • 无锁队列的实现

# Lab9: File System

# Reference

  • yale_OS (7)——xv6 中的文件系统 (File System)
  • Mit6.S081 - 实验 9-file system

# Lab10: mmap

# Reference

  • xv6 6.S081 Lab9: mmap
  • 虚拟内存 MMU mmap
  • Mit6.S081 - 实验 10-mmap
  • [MIT 6.S081] Lab 10: mmap
  • mmap 详解

# Reference

  • MIT 6.S081
  • MIT6.S081 lab util-xargs 的一种实现方法
  • xv6 实验课程 -- 系统调用
  • xv6 实验课程 -- 页表
  • YuanZiming: MIT-6.S081-2020 实验
  • Learn OS with me
  • 嘉然今天学 C++: MIT 6.S081 2021: Lab page tables
  • ohmyfish: MIT6.S081
  • XV6 学习（6）Lab: traps
  • LAB4：Traps 及 xv6 中断相关源码理解
  • Lab4: traps
  • 嘉然今天 C++: Traps
  • XV6 学习（9）Lab cow: Copy-on-write fork