6.S081 - Lecture 2 Operating System Organization

本文最后更新于：2024年4月28日 下午

Lecture 2: Operating System Organization

预备知识：C pointer

指针是一个特殊的变量，它里面存储的数值被解释成为内存里的一个地址。

要搞清一个指针，需要搞清四方面的内容：

  1. 指针的类型
  2. 指针所指向的类型
  3. 指针的值、或者叫指针所指向的内存区
  4. 指针本身所占据的内存区

具体分析可以看看这篇文章。

C程序的内存分配：

  1. 堆(heap)：由程序员通过malloc()和free()使用和释放，如果忘记释放可能造成内存泄漏。地址从低到高增长
  2. 栈(stack)：编译器自动分配释放，存放函数的参数值、局部变量的值等。在退出函数后自动释放销毁。地址从高到低增长
  3. 全局区(static)：通过static声明，全局都可以访问，不会在函数退出后释放

用户模式与管理员模式

为了实现进程隔离，RISC-V CPU在硬件上提供3种执行命令的模式：machine mode（机器模式）, supervisor mode（管理员模式）, user mode（用户模式）。

  1. machine mode的权限最高，CPU以machine mode启动，machine mode的主要目的是为了配置电脑，之后立即切换到supervisor mode。
  2. supervisor mode运行CPU执行privileged instructions，比如中断管理、对存储页表地址的寄存器进行读写操作、执行system call。运行在supervisor mode也称为在kernel space中运行。运行在内核空间（或管理模式）的软件称为kernel。
  3. 应用程序只能执行user mode指令，比如改变变量、执行util function（工具函数）。运行在user mode也称为在user space中运行。要想让CPU从user mode切换到supervisor mode，RISC-V提供了一个特殊的ecall指令，要想从supervisor mode切换到user mode，调用sret指令。

想要调用内核函数的应用程序（例如xv6中的read系统调用）必须转换到内核；应用程 序不能直接调用内核函数。CPU提供了一种特殊的指令，可以将CPU从U态切换到S态，并在内核指定的入口点进入内核。

一旦CPU切换到管理S态，内核就可以验证系统调用的参数（例如，检查传递给系统调用的 地址是否是应用程序内存的一部分），决定应用程序是否允许执行请求的操作（例如，检查应用程序是否允许写入指定的文件），然后拒绝或执行它。

内核控制转换到管理模式的入口点非常重要；例如，如果应用程序可以决定内核入口点，则恶意应用程序可以在跳过参数验证的点进入内核。

内核组织

monolithic kernel（宏内核）：整个操作系统在kernel中，所有system call都在supervisor mode下运行。xv6是一个monolithic kernel。

  • 操作系统设计者不必决定操作系统的哪一部分不需要完整的硬件权限。
  • 操作系统的不同部分更容易协作。例如，操作系统可能具有可由文件系统和虚拟内存系统共享的缓冲区高速缓存。
  • 操作系统不同部分之间的接口通常很复杂，因此操作系统开发人员很容易犯错误。在单片内核中，错误是致命的， 因为管理模式下的错误通常会导致内核失败。如果内核出现故障，计算机就会停止工作， 因此所有应用程序也会失败。计算机必须重新启动才能重新启动。

micro kernel（微内核）：将需要运行在supervisor mode下的操作系统代码压到最小，保证kernel内系统的安全性，将大部分的操作系统代码执行在user mode下。

如2.1所示，文件系统是一个user-level的进程，为其他进程提供服务，因此也叫做server。

xv6 kernel source file如下所示。

进程

隔离的单元叫做进程，一个进程不能够破坏或者监听另外一个进程的内存、CPU、文件描述符，也不能破坏kernel本身。

为了实现进程隔离，xv6提供了一种机制让程序认为自己拥有一个独立的机器。一个进程为一个程序提供了一个私有的内存系统，或address space，其他的进程不能够读/写这个内存。xv6使用page table(页表)来给每个进程分配自己的address space，页表再将这些address space，也就是进程自己认为的虚拟地址(virtual address)映射到RISC-V实际操作的物理地址(physical address)。

虚拟地址从0开始，往上依次是指令、全局变量、栈、堆。RISC-V上的指针是64位的，xv6使用低38位，因此最大的地址是238−1238−1=0x3fffffffff=MAXVA。

进程最重要的内核状态：1. 页表 p->pagetable 2. 内核堆栈p->kstack 3. 运行状态p->state，显示进程是否已经被分配、准备运行/正在运行/等待IO或退出。

每个进程中都有线程(thread)，是执行进程命令的最小单元，可以被暂停和继续。

每个进程有两个堆栈：用户堆栈(user stack)和内核堆栈(kernel stack)。当进程在user space中进行时只使用用户堆栈，当进程进入了内核(比如进行了system call)使用内核堆栈。

启动第一个进程

RISC-V启动时，先运行一个存储于ROM中的bootloader程序kernel.ld来加载xv6 kernel到内存中，然后在machine模式下从_entry开始运行xv6。bootloader将xv6 kernel加载到0x80000000的物理地址中，因为前面的地址中有I/O设备。

在_entry中设置了一个初始stack，stack0来让xv6执行kernel/start.c。在start函数先在machine模式下做一些配置，然后通过RISC-V提供的mret指令切换到supervisor mode，使program counter切换到kernel/main.c。

main先对一些设备和子系统进行初始化，然后调用kernel/proc.c中定义的userinit来创建第一个用户进程。这个进程执行了一个initcode.S的汇编程序，这个汇编程序调用了exec这个system call来执行/init，重新进入kernel。exec将当前进程的内存和寄存器替换为一个新的程序(/init)，当kernel执行完毕exec指定的程序后，回到/init进程。/init(user/init.c)创建了一个新的console device以文件描述符0,1,2打开，然后在console device中开启了一个shell进程，至此整个系统启动了。

Lab 2: System Calls

阅读 xv6 文档的第 2 章和第 4 章的 4.3 节和 4.4 节以及相关源文件：

  • 系统调用的用户空间代码在 user/user.h 和 user/usys.pl 中。
  • 内核空间代码在 kernel/syscall.h 和 kernel/syscall.c 中。
  • 与进程相关的代码在 kernel/proc.h 和 kernel/proc.c 中。

建议同时阅读kernel/kalloc.c。

System Call tracing（moderate）

在这个实验里，我们需要让内核输出每个mask变量指定的系统函数的调用情况，格式为：<pid>: syscall <syscall_name> -> <return_value>。pid是进程序号， syscall_name是函数名称，return_value是该系统调用返回值，并且要求各个进程的输出是独立的，不相互干扰。

作为一个系统调用，我们先要定义一个系统调用的序号。系统调用序号的宏定义在 kernel/syscall.h 文件中。我们在 kernel/syscall.h 添加宏定义，模仿已经存在的系统调用序号的宏定义。

1
2
3
// kernel/syscall.h

#define SYS_trace  22

已给出用户态的 trace 函数( user/trace.c )，所以我们直接在 user/user.h 文件中声明用户态可以调用 trace 系统调用就好了。

但有一个问题，该系统调用的参数和返回值分别是什么类型呢？

接下来我们还是得看一看 trace.c 文件，可以看到 trace(atoi(argv[1])) < 0 ，即 trace 函数传入的是一个数字，并和 0 进行比较。

结合实验提示，我们知道传入的参数类型是 int ，并且由此可以猜测到返回值类型应该是 int 。

这样就可以把 trace 这个系统调用加入到kernel中声明了：

1
2
3
4
// user/user.h

// system calls
int trace(int);

接下来我们查看 user/usys.pl 文件，这里 perl 语言会自动生成汇编语言 usys.S ，是用户态系统调用接口。所以在 user/usys.pl 文件加入下面的语句来注册trace：

1
entry("trace");

可以看到首先把系统调用号压入a7寄存器，然后就直接ecall进入系统内核。而我们刚才syscall那个函数就把a7寄存器的数字读出来调用对应的函数，所以这里就是系统调用用户态和内核态的切换接口。

1
2
3
4
5
6
# usys.S
.global trace
trace:
 li a7, SYS_trace
 ecall
 ret

执行 ecall 指令会跳转到哪里呢？答案是跳转到 kernel/syscall.c 中 syscall 那个函数处，执行此函数。下面是 syscall 函数的源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void
syscall(void)
{
  int num;
  struct proc *p = myproc();

  num = p->trapframe->a7;
  if(num > 0 && num < NELEM(syscalls) && syscalls[num]) {
    p->trapframe->a0 = syscalls[num]();
  } else {
    printf("%d %s: unknown sys call %d\n",
            p->pid, p->name, num);
    p->trapframe->a0 = -1;
  }
}

num = p->trapframe->a7; 从寄存器 a7 中读取系统调用号，所以上面的 usys.S 文件就是系统调用用户态和内核态的切换接口。接下来是 p->trapframe->a0 = syscalls[num](); 语句，通过调用 syscalls[num](); 函数，把返回值保存在了 a0 寄存器中。

我们看看 syscalls[num](); 函数，这个函数在当前文件中，调用了系统调用命令。所以我们把新增的 trace 系统调用添加到函数指针数组 *syscalls[] 上：

1
2
3
4
5
static uint64 (*syscalls[])(void) = {
  ...
  [SYS_trace]   sys_trace,
};

接下来在文件开头给内核态的系统调用 trace 加上声明，在 kernel/syscall.c 加上extern uint64 sys_trace(void);。

我们的 trace 系统调用应该有一个参数，一个整数“mask(掩码)”，其指定要跟踪的系统调用。

所以，我们在 kernel/proc.h 文件的 proc 结构体中，新添加一个变量 mask ，使得每一个进程都有自己的 mask ，即要跟踪的系统调用。

然后我们就可以在 kernel/sysproc.c 给出 sys_trace 函数的具体实现了，只要把传进来的参数给到现有进程的 mask 就好了。

接下来我们就要把输出功能实现，因为 RISCV 的 C 规范是把返回值放在 a0 中，所以我们只要在调用系统调用时判断是不是 mask 规定的输出函数，如果是就输出。

因为 proc 结构体(见 kernel/proc.h )里的 name 是整个线程的名字，不是函数调用的函数名称，所以我们不能用 p->name ，而要自己定义一个数组，我这里直接在 kernel/syscall.c 中定义了。

这里注意系统调用名字一定要按顺序，第一个为空，当然你也可以去掉第一个空字符串，但要记得取值的时候索引要减一，因为这里的系统调用号是从 1 开始的。

然后我们就可以在 kernel/syscall.c 中的 syscall 函数中添加打印调用情况语句。 mask 是按位判断的，所以判断使用的是按位运算。进程序号直接通过 p->pid 就可以取到，函数名称需要从我们刚刚定义的数组中获取，即 syscall_names[num] ，其中 num 是从寄存器 a7 中读取的系统调用号，系统调用的返回值就是寄存器 a0 的值了，直接通过 p->trapframe->a0 语句获取即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
static char *syscall_names[] = {
  "", "fork", "exit", "wait", "pipe", 
  "read", "kill", "exec", "fstat", "chdir", 
  "dup", "getpid", "sbrk", "sleep", "uptime", 
  "open", "write", "mknod", "unlink", "link", 
  "mkdir", "close", "trace"};


void
syscall(void)
{
  int num;
  struct proc *p = myproc();

  num = p->trapframe->a7;
  if(num > 0 && num < NELEM(syscalls) && syscalls[num]) {
    p->trapframe->a0 = syscalls[num]();
    if((1 << num) & p->mask) {
      printf("%d: syscall %s -> %d\n", p->pid, syscall_names[num], p->trapframe->a0);
    }
  } else {
    printf("%d %s: unknown sys call %d\n",
            p->pid, p->name, num);
    p->trapframe->a0 = -1;
  }
}

然后在 kernel/proc.c 中 fork 函数调用时，添加子进程复制父进程的 mask 的代码，这样就可以了。

System Call sysinfo（moderate）

跟上个实验一样，首先定义一个系统调用的序号，同时修改 user/usys.pl 来注册sysinfo。

然后在 user/user.h 中添加 sysinfo 结构体以及 sysinfo 函数的声明。在 kernel/syscall.c 中新增 sys_sysinfo 函数的定义，函数指针数组新增 sys_sysinfo，在system_names新增”sysinfo”。接下来我们就要开始写相应的函数实现了。

首先我们写获取可用进程数目的函数实现。通过阅读 kernel/proc.c 文件可以看到struct proc proc[NPROC];。我们可以再看看struct proc的定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
enum procstate { UNUSED, SLEEPING, RUNNABLE, RUNNING, ZOMBIE };

// Per-process state
struct proc {
  struct spinlock lock;

  // p->lock must be held when using these:
  enum procstate state;        // Process state
  struct proc *parent;         // Parent process
  void *chan;                  // If non-zero, sleeping on chan
  int killed;                  // If non-zero, have been killed
  int xstate;                  // Exit status to be returned to parent's wait
  int pid;                     // Process ID

  // these are private to the process, so p->lock need not be held.
  uint64 kstack;               // Virtual address of kernel stack
  uint64 sz;                   // Size of process memory (bytes)
  pagetable_t pagetable;       // User page table
  struct trapframe *trapframe; // data page for trampoline.S
  struct context context;      // swtch() here to run process
  struct file *ofile[NOFILE];  // Open files
  struct inode *cwd;           // Current directory
  char name[16];               // Process name (debugging)
  int mask;                    // Mask
};

进程里已保存当前进程的状态，所以我们可以直接遍历所有进程，获取其状态判断当前进程的状态是不是为 UNUSED 并统计数目就行了。

当然，通过 proc 结构体的定义，我们知道使用进程状态时必须加锁，我们在 kernel/proc.c 中新增函数 nproc 如下，通过该函数以获取可用进程数目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Return the number of processes whose state is not UNUSED
uint64
nproc(void)
{
  struct proc *p;
  // counting the number of processes
  uint64 num = 0;
  // traverse all processes
  for (p = proc; p < &proc[NPROC]; p++)
  {
    // add lock
    acquire(&p->lock);
    // if the processes's state is not UNUSED
    if (p->state != UNUSED)
    {
      // the num add one
      num++;
    }
    // release lock
    release(&p->lock);
  }
  return num;
}

接下来实现获取空闲内存数量的函数。可用空间的判断在 kernel/kalloc.c 文件中。

这里定义了一个链表，每个链表都指向上一个可用空间，这里的 kmem 就是一个保存最后链表的变量。

1
2
3
4
5
6
7
8
9
struct run {
  struct run *next;
};

struct {
  struct spinlock lock;
  struct run *freelist;
} kmem;

kmem.freelist 永远指向最后一个可用页，那我们只要顺着这个链表往前走，直到 NULL 为止。所以我们就可以在 kernel/kalloc.c 中新增函数 free_mem ，以获取空闲内存数量：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Return the number of bytes of free memory
uint64
free_mem(void)
{
  struct run *r;
  // counting the number of free page
  uint64 num = 0;
  // add lock
  acquire(&kmem.lock);
  // r points to freelist
  r = kmem.freelist;
  // while r not null
  while (r)
  {
    // the num add one
    num++;
    // r points to the next
    r = r->next;
  }
  // release lock
  release(&kmem.lock);
  // page multiplicated 4096-byte page
  return num * PGSIZE;
}

最后的难点就在这个copyout：copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)。它其实就是把在内核地址src开始的len大小的数据拷贝到用户进程pagetable的虚地址dstva处，所以sysinfo实现里先用argaddr读进来我们要保存的在用户态的数据sysinfo的指针地址，然后再把从内核里得到的sysinfo开始的内容以sizeof(sysinfo)大小的的数据复制到这个指针上，其实就是同一个数据结构，所以这样直接复制过去就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// add header
#include "sysinfo.h"

uint64
sys_sysinfo(void)
{
  // addr is a user virtual address, pointing to a struct sysinfo
  uint64 addr;
  struct sysinfo info;
  struct proc *p = myproc();
  
  if (argaddr(0, &addr) < 0)
	  return -1;
  // get the number of bytes of free memory
  info.freemem = free_mem();
  // get the number of processes whose state is not UNUSED
  info.nproc = nproc();

  if (copyout(p->pagetable, addr, (char *)&info, sizeof(info)) < 0)
    return -1;
  
  return 0;
}

最后添加一个用户程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include "kernel/param.h"
#include "kernel/types.h"
#include "kernel/sysinfo.h"
#include "user/user.h"

int
main(int argc, char *argv[])
{
    // param error
    if (argc != 1)
    {
        fprintf(2, "Usage: %s need not param\n", argv[0]);
        exit(1);
    }

    struct sysinfo info;
    sysinfo(&info);
    // print the sysinfo
    printf("free space: %d\nused process: %d\n", info.freemem, info.nproc);
    exit(0);
}
课外拓展
#操作系统 #cs自学指南
6.S081 - Lecture 2 Operating System Organization
https://galaxy-jewxw.github.io/2024/04/28/6-S081-Lecture-2-Operating-System-Organization/
作者
Traumtänzer aka 'Jew1!5!'
发布于
2024年4月28日
许可协议