【Create my OS】9 实现终端

January 07, 2025

目前我们的操作系统运行的应用程序都是硬编码在代码中的。本章实现一个终端，我们可以输入应用程序的路径来选择执行的程序。

9.1 键盘中断

1、目前我们实现的操作系统，是在代码中硬编码用户程序的路径，在启动时就自动加载到内存中了。现在我们想通过键盘输入路径的方式来选择用户程序，就首先需要操作系统响应键盘中断。

在 QEMU 模拟的 Virt 机器上，键盘被挂载为一个串口设备，按下键盘按键会触发一个外部中断。
开启外部中断的步骤很简单，外部中断发生时 scause 寄存器被设置为 9L | (1L << 63) ，我们在 handleInterrupt() 里识别这种中断就好了。
同时，还可以直接使用 OpenSBI 的服务 CONSOLE_GETCHAR，就能读取到输入的字符了。最后不要忘了开启 SIE 寄存器的 SEIE 位使能外部中断。

// kernel/interrupt.c

void
handleInterrupt(InterruptContext *context, usize scause, usize stval)
{
    switch (scause)
    {
    ...
    case SUPERVISOR_EXTERNAL:
        external();
        break;
    ...
    }
}

// 外部中断处理
void external()
{
    printf("externel interrupt happened!\n Input char is ");
    // 目前只处理串口中断
    usize ret = consoleGetchar();   // 从控制台读取一个字符
    consolePutchar(ret);            // 向终端输出一个字符
}

void
initInterrupt()
{
    // 设置 stvec 寄存器，设置中断处理函数和处理模式
    extern void __interrupt();
    w_stvec((usize)__interrupt | MODE_DIRECT);

    // 开启外部中断
    w_sie(r_sie() | SIE_SEIE);
    printf("***** Init Interrupt *****\n");
}

可真的这么简单吗？我们运行一下，注意这次先不要初始化线程了，在初始化线程之前就进入一个忙循环，我们在这里验证是否能接收字符。
运行之后，和之前一样输出了时钟中断的信息，但是无论我们按下什么键，都无法触发外部中断。哪里出了问题？

2、OpenSBI 在初始化时，为了防止键盘输入打断过程，默认关闭了外部和串口中断，所以我们才接收不到键盘输入。

还记得在 3.3 节我们曾经展示过 QEMU 模拟的 RISC-V Virt 的内存结构吗，其中QEMU VIRT_PLIC 设备被映射到物理地址 0xc000000 ~ 0x10000000 处，QEMU VIRT_UART0 设备映射至物理地址 0x10000000 ~ 0x10000100 处。其中，PLIC 为 Platform Level Interrupt Controller，控制着平台的中断，UART0 是串口设备。OpenSBI 通过设置这两片内存的一些标志位来控制这两个设备，关闭了外部中断和串口中断的。
所以，我们可以通过设置这些标志位，来开启这些中断。至于相关的地址，暂且可以理解为 magic number。

// kernel/interrupt.c

// 打开 OpenSBI 的 VIRT_PLIC 外部中断响应
void
initExternalInterrupt()
{
    *(uint32 *)(0x0C002080 + KERNEL_MAP_OFFSET) = 1 << 0xa;
    *(uint32 *)(0x0C000028 + KERNEL_MAP_OFFSET) = 0x7U;
    *(uint32 *)(0x0C201000 + KERNEL_MAP_OFFSET) = 0x0U;
}
// 打开 OpenSBI 的 VIRT_UART0 串口设备响应
void
initSerialInterrupt()
{
    *(uint8 *)(0x10000004 + KERNEL_MAP_OFFSET) = 0x0bU;
    *(uint8 *)(0x10000001 + KERNEL_MAP_OFFSET) = 0x01U;
}

void
initInterrupt()
{
    ....
    // 打开 OpenSBI 的外部中断响应
    initExternalInterrupt();
    initSerialInterrupt();

    printf("***** Init Interrupt *****\n");
}

我们通过虚拟内存的方式访问到了这些内存区域，但是我们实际上只将物理地址 0x80200000 之后的内存区域映射到了虚拟内存，所以我们还需要手动映射被修改部分的内存。

// kernel/mapping.c

// 映射外部中断相关区域到虚拟内存
void
mapExtInterruptArea(Mapping m)
{
    // VIRT_PLIC
    Segment s1 = {
        (usize)0x0C000000 + KERNEL_MAP_OFFSET,
        (usize)0x0C001000 + KERNEL_MAP_OFFSET,
        1L | READABLE | WRITABLE
    };
    mapLinearSegment(m, s1);    // 将段映射到三级页表上

    Segment s2 = {
        (usize)0x0C002000 + KERNEL_MAP_OFFSET,
        (usize)0x0C003000 + KERNEL_MAP_OFFSET,
        1L | READABLE | WRITABLE
    };
    mapLinearSegment(m, s2);

    Segment s3 = {
        (usize)0x0C201000 + KERNEL_MAP_OFFSET,
        (usize)0x0C202000 + KERNEL_MAP_OFFSET,
        1L | READABLE | WRITABLE
    };
    mapLinearSegment(m, s3);

    // VIRT_UART
    Segment s4 = {
        (usize)0x10000000 + KERNEL_MAP_OFFSET,
        (usize)0x10001000 + KERNEL_MAP_OFFSET,
        1L | READABLE | WRITABLE
    };
    mapLinearSegment(m, s4);
}

/* 重映射内核,写入satp */
void
mapKernel()
{
    Mapping m = newKernelMapping();     // 创建一个映射了内核(0x80200000后地址）的虚拟地址空间
    mapExtInterruptArea(m);             // 创建一个映射了PLIC和UART地址
    activateMapping(m);                 // 将根页表地址写入 satp
    printf("***** Remap Kernel *****\n");
}

将 mapKernel() 添加到 initMemory() 中，并且在 initInterrupt() 之前运行

// kernel/memory.c

/*
 * 初始化 页分配 和 动态内存分配
 */
void
initMemory()
{
    /* 
     * 开启 sstatus 的 SUM 位
     * 允许内核访问用户内存
     */
    w_sstatus(r_sstatus() | SSTATUS_SUM);
    // 初始化全局页帧分配器
    initFrameAllocator(
        // 起始PPN 是内核结束虚拟地址-内核起始虚拟地址 再加上 内核起始物理地址 = 内核结束物理地址
        (((usize)(kernel_end) - KERNEL_BEGIN_VADDR + KERNEL_BEGIN_PADDR) >> 12) + 1,
        // 终止页是物理内存的最后一个页
        MEMORY_END_PADDR >> 12
    );
    extern void initHeap();     initHeap();     // 初始化动态内存分配器
    extern void mapKernel();    mapKernel();    // 内核重映射，三级页表机制
    printf("***** Init Memory *****\n");
}

由于中断初始化过程需要修改这部分内存，所以内存初始化需要在中断初始化之前进行

// kenrel/main.c

void
main()
{
    printf("Initializing Jokerix...\n");
    extern void initMemory();       initMemory();
    extern void initInterrupt();    initInterrupt();
    extern void initFs();           initFs();
    ...
}

运行可以看到，操作系统已经可以正常地响应外部中断，从键盘读取字符了。

9.2 条件变量与输入缓冲

1、我们设想这样一个场景：一个用户进程通过 getc() 函数发起了一个系统调用，用于获取一个键盘输入的字符，内核处理调用的时候发现，当前并没有字符输入。这时，一个很简单的想法就是进入一个忙循环，不断地检查是否有字符输入，直到有字符输入后再将其读出，系统调用返回。

这种方式肯定能保证读到字符，但是线程会占用资源，什么都不做，浪费 CPU 资源，即使会被 CPU 调度，但是所以属于该线程的时间片都被浪费掉了。
我们还可以用另一种方式来实现，当线程检查到当前没有键盘输入时，就自动进入睡眠状态，同时不再参与调度，直到有字符输入时，才会将这个线程唤醒参与调度，这个时候被唤醒的线程就一定可以获取到字符并返回了。
线程自动放弃 CPU，等待条件满足再被唤醒的机制，叫做条件变量（Condition Variable）。

2、但是实现这个机制前，我们先来实现一个辅助结构，队列。我们使用一个链表来实现队列，两个指针分别指向队首和队尾

// kernel/queue.h

// 队列节点
typedef struct n {
    usize item;     // 节点值
    struct n *next; // 下一个节点
} Node;

// 队列结构
typedef struct {
    Node *head;     // 队首
    Node *tail;     // 队尾
} Queue;

并实现相关的方法

// kernel/queue.c

// 向队尾插入新节点
void
pushBack(Queue *q, usize data)
{
    // 分配一个节点内存
    Node *n = kalloc(sizeof(Node));
    n->item = data;
    if(q->head == q->tail && q->head == 0) {
        // 队列为空
        q->head = n;    // 头尾节点均为当前节点
        q->tail = n;
    } else {
        // 队列不为空
        q->tail->next = n;  // 插入尾部
        q->tail = n;        // 重新设置队尾
    }
}

// 移除队列头节点（默认队列不为空）
usize
popFront(Queue *q)
{
    Node *n = q->head;      // 获取头节点
    usize ret = n->item;    // 返回值为头节点值
    if(q->head == q->tail) {
        // 队列只有一个元素
        q->head = 0;
        q->tail = 0;
    } else {
        // 队列元素大于1
        q->head = q->head->next;    // 设置新的头节点
    }
    kfree(n);       // 回收内存
    return ret;
}

// 判断队列是否为空
// 返回：1-空，0-不为空
int
isEmpty(Queue *q)
{
    if(q->head == q->tail && q->head == 0) {
        return 1;
    } else {
        return 0;
    }
}

3、实现条件变量前，我们先来添加几个简单的 CPU 运行机制，分别是 yield，即当前线程让出 CPU 并进入睡眠；和 wakeup，唤醒睡眠中的线程，使其参与调度。

// kernel/processor.c

// 当前线程主动放弃 CPU，并进入休眠状态
void
yieldCPU()
{
    if(CPU.occupied) {
        usize flags = disable_and_store();          // 关闭异步中断

        int tid = CPU.current.tid;                      // 当前线程PID
        ThreadInfo *ti = &CPU.pool.threads[tid];        // 从线程池获取该线程
        ti->status = Sleeping;                          // 睡眠
        switchThread(&CPU.current.thread, &CPU.idle);   // 切换到idle调度线程

        restore_sstatus(flags);                     // 恢复中断
    }
}

// 将某个线程唤醒，将其参与调度
void
wakeupCPU(int tid)
{
    ThreadInfo *ti = &CPU.pool.threads[tid];    // 获取线程
    ti->status = Ready;                         // 唤醒
    schedulerPush(tid);                         // 加入线程调度
}

下面就可以来实现条件变量了。条件变量的基本结构就是一个队列，里面是等待当前条件满足的线程 tid。

// kernel/condition.h

// 条件变量，内部为等待该条件满足的等待线程队列
typedef struct {
    Queue waitQueue;
} Condvar;

它的函数也很简单，waitCondition() 表示条件暂时没有满足，将当前线程加入等待队列；notifyCondition() 表示条件已经满足，唤醒等待队列队首的线程

// kernel/condition.c

// 将当前线程加入到等待队列中
void
waitCondition(Condvar *self)
{
    pushBack(&self->waitQueue, getCurrentTid());    // 插入等待队列
    yieldCPU();     // 主动放弃 CPU，并进入休眠状态
}

// 从等待队列中唤醒一个线程
void
notifyCondition(Condvar *self)
{
    // 判断等待队列是否为空
    if(!isEmpty(&self->waitQueue)) {
        int tid = (int)popFront(&self->waitQueue);  // 从等待队列获取一个线程
        wakeupCPU(tid);     // 唤醒线程，参与调度
    }
}

其中在 processor.c 实现一些辅助函数，getCurrentTid

// kernel/processor.c

// 获取当前正在运行的线程TID
int
getCurrentTid()
{
    return CPU.current.tid;
}

4、标准输入缓冲区：如果输入字符的速度过快，可能会由于上一个字符还没被读取下一个字符就被输入了，导致上一个字符丢失。我们设置一个缓冲区，所有被输入的字符首先暂存在缓冲区中，线程获取输入时也是从缓冲区中获取字符。

缓冲区的结构很简单，字符的输入也要符合 FIFO，所以使用队列来存储字符，同时设置一个条件变量，来保存等待输入的线程 Id。
这里直接将 STDIN 声明成一个全局变量，因为标准输入缓冲区是全局唯一的。

// kernel/stdin.c

// 标准输入缓冲区，buf 为输入字符缓冲，pushed 为条件变量（等待输入的线程）
struct
{
    Queue buf;          // 队列存储字符
    Condvar pushed;     // 条件变量保存等待输入的线程id
} STDIN;

/*
 * 将一个字符放入标准输入缓冲区
 * 并唤醒一个等待字符的线程
 */
void
pushChar(char ch)
{
    pushBack(&STDIN.buf, (usize)ch);    // 将字符放入标准输入缓冲区
    notifyCondition(&STDIN.pushed);     // 从等待队列中唤醒一个线程
}

/*
 * 线程请求从 stdin 中获取一个输入的字符
 * 如果当前缓冲区为空，线程会进入等待队列，并挂起自己
 * 在之后的某个时刻被唤醒时，缓冲区必然有字符，就可以顺利返回
 */
char
popChar()
{
    while(1) {
        // 判断标准输入缓冲区是否有数据
        if(!isEmpty(&STDIN.buf)) {
            char ret = (char)popFront(&STDIN.buf);  // 获取数据
            return ret;
        } else {
            // 没有数据则将当前线程加入到等待队列中
            waitCondition(&STDIN.pushed);
        }
    }
}

popChar() 中是一个忙循环，当线程第一次试图获取字符时，如果输入缓冲为空，会调用 waitCondition() 函数使自身休眠，当有字符输入时，线程被唤醒后会回到此函数进行下一个循环，就可以顺利获取到字符并返回了。
修改外部中断处理函数，使得输入的字符会被放到输入缓冲区中。

// kernel/interrupt.c

// 外部中断处理
void external()
{
    // 将输入的字符放到输入缓冲区
    usize ret = consoleGetchar();   // 从控制台获取一个字符
    // 若获取不到字符 ret = -1
    if(ret != -1) {
        char ch = (char)ret;
        // 将字符放到缓冲区
        if(ch == '\r') {
            pushChar('\n');
        } else {
            pushChar(ch);
        }
    }
}

9.3 echo程序

1、本节我们来运用上一节中实现的标准输入缓冲区，实现一个简单的用户程序 echo，将所有输入的字符都输入在屏幕上。我们定义一个系统调用，READ，用于从标准输入读取字符。

// user/syscall.h

typedef enum {
        ...
        Read = 63,
}

....

#define sys_read(__a0, __a1, __a2) sys_call(Read, __a0, __a1, __a2, 0)

sys_read() 函数被设计为一个通用的函数，第一个参数是要读取的文件描述符，第二个参数是要读取到的字符数组，第三个参数是读取长度。
但是本节仅仅将其当做读取输入缓冲区来实现。编写一个函数包装一下 sys_read()。

// user/io.c

// 从标准输入缓存区获取一个字符
uint8 getc()
{
    uint8 c;
    // 读取的文件描述符，读取的字节数组，读取的长度
    sys_read(0, &c, 1);
    return c;
}

完成后就可以通过 getc() 函数来编写 echo 程序了

// user/echo.c

#include "types.h"
#include "ulib.h"

// 定义一些控制字符常量
#define LF 0x0au        // 换行
#define CR 0x0du        // 回车
#define BS 0x08u        // 退格
#define DL 0x7fu        // 删除

// 将读到的字符输出，其中退格键 DL 的写法来自 xv6
uint64
main()
{
    printf("Welcome to echo!\n");
    int lineCount = 0;      // 当前输入行的字符数
    while(1) {
        // 从标准输入缓存区获取一个字符
        uint8 c = getc();
        // 字符处理
        switch(c) {
            // 换行/回车
            case LF: case CR: 
                lineCount = 0;  // 重置计数
                putchar(LF);
                putchar(CR);
                break;
            // 删除
            case DL:
                // 若有字符输出
                if(lineCount > 0) {
                    putchar(BS);    // 退格
                    putchar(' ');   // 输出空格覆盖
                    putchar(BS);    // 退格
                    lineCount -= 1;
                }
                break;
            // 其他字符正常输出
            default:
                lineCount += 1;
                putchar(c);
                break;
        }
    }
}

逻辑很简单，无非是将读到的字符输出而已，其中退格键 DL 的写法来自 xv6。

2、我们在用户程序中定义了 READ 系统调用，也就需要在内核中提供支持

// kernel/syscall.c

const usize SYS_READ = 63;
const usize SYS_WRITE = 64;
const usize SYS_EXIT = 93;

// 只将 READ 系统调用实现读取输入缓冲区的功能，所以 fd 和 len 都不会被使用
usize
sysRead(usize fd, uint8 *base, usize len) {
    *base = (uint8)popChar();
    return 1;
}

// 内核处理系统调用
usize
syscall(usize id, usize args[3], InterruptContext *context)
{
    switch (id)
    {
    case SYS_WRITE:     // 系统写
        consolePutchar(args[0]);
        return 0;
    case SYS_EXIT:      // 系统线程退出
        exitFromCPU(args[0]);
        return 0;
    case SYS_READ:
        return sysRead(args[0], (uint8 *)args[1], args[2]);
    default:
        printf("Unknown syscall id %d\n", id);
        panic("");
        return -1;
    }
}

这里只将 READ 系统调用实现成读取输入缓冲区的功能，所以 fd 和 len 都不会被使用。
注意传入的目标地址 base 是用户态地址，默认内核是无法访问的，需要设置 sstatus 寄存器的 sum 标志位允许内核访问。在初始化内存时打开即可。

// kernel/memory.c

/*
 * 初始化 页分配 和 动态内存分配
 */
void
initMemory()
{
    /* 
     * 开启 sstatus 的 SUM 位
     * 允许内核访问用户内存
     */
    w_sstatus(r_sstatus() | SSTATUS_SUM);
    // 初始化全局页帧分配器
    initFrameAllocator(
        // 起始PPN 是内核结束虚拟地址-内核起始虚拟地址 再加上 内核起始物理地址 = 内核结束物理地址
        (((usize)(kernel_end) - KERNEL_BEGIN_VADDR + KERNEL_BEGIN_PADDR) >> 12) + 1,
        // 终止页是物理内存的最后一个页
        MEMORY_END_PADDR >> 12
    );
    extern void initHeap();     initHeap();     // 初始化动态内存分配器
    extern void mapKernel();    mapKernel();    // 内核重映射，三级页表机制
    printf("***** Init Memory *****\n");
}

最后将运行的线程路径改为 /bin/echo，运行，我们输入的内容就可以显示在屏幕上了

9.4 实现终端

1、现在我们可以基于 echo 程序实现一个终端了！

终端需要获取到可执行文件的路径，并执行程序。我们直接定义一个新的系统调用，用来执行程序，传入的参数是可执行文件的路径。这个系统调用会让当前线程休眠，并启动新的线程。休眠当前线程是为了防止终端的输出和用户程序的输出混杂在一起。
由于等待一个线程运行结束的线程只可能有一个，就是它的父线程，这里就不用第二节定义的条件变量了，直接修改线程的结构。

// kernel/thread.h

typedef struct {
    // 线程上下文存储的地址
    usize contextAddr;
    // 线程栈底地址
    usize kstack;
    // 所属进程
    Process process;
    // 等待其退出的 Tid
    int wait;
} Thread;

当没有线程等待时，wait 被赋值为 -1。这样在线程调用 exitFromCPU() 退出时就需要检查是否有线程在等待，如果有就需要唤醒。

// kernel/processor.c

// 由当前线程执行，退出线程并切换到 idle
void
exitFromCPU(usize code)
{
    disable_and_store();
    int tid = CPU.current.tid;
    exitFromPool(&CPU.pool, tid);
    
    if(CPU.current.thread.wait != -1) {
        wakeupCPU(CPU.current.thread.wait);
    }

    switchThread(&CPU.current.thread, &CPU.idle);
}

我们在用户程序中定义 EXEC 系统调用

// kernel/syscall.h

typedef enum {
    ....
    Exec = 221,
} SyscallId;

....

#define sys_exec(__a0) sys_call(Exec, __a0, 0, 0, 0)

并在内核中添加对应的支持

// kernel/syscall.c

const usize SYS_EXEC     = 221;

usize
syscall(usize id, usize args[3], InterruptContext *context)
{
    switch (id)
    {
    ....
    case SYS_EXEC:
        sysExec((char *)args[0]);
        return 0;
    ....
    }
}

usize
sysExec(char *path)
{
    if(executeCPU(path, getCurrentTid())) {
        yieldCPU();
    }
    return 0;
}

executeCPU() 函数返回值表示是否执行成功，如果成功就会让当前线程（终端线程）进入休眠

// kernel/processor.c

/*
 * 执行一个用户进程
 * path 为可执行文件在文件系统的路径, hostTid 为需要暂停的线程的 tid
 */
int
executeCPU(char *path, int hostTid)
{
    Inode *res = lookup(0, path);   // 查找文件inode
    if(res == 0) {
        printf("Command not found!\n");
        return 0;
    }
    char *buf = kalloc(res->size);  // 分配内存
    readall(res, buf);              // 读取文件所有数据到buf
    Thread t = newUserThread(buf);  // 创建新的用户线程
    t.wait = hostTid;               // 记录等待其退出的进程tid
    kfree(buf);                     // 释放内存
    addToCPU(t);                    // 添加到线程池中
    return 1;
}

2、实现 shell，其实就是根据 echo 修改而来

// user/sh.c

#include "types.h"
#include "ulib.h"
#include "syscall.h"

#define LF      0x0au
#define CR      0x0du
#define BS      0x08u
#define DL      0x7fu

int
isEmpty(char *line, int length) {
    int i;
    for(i = 0; i < length; i ++) {
        if(line[i] == 0) break;
        if(line[i] != ' ' && line[i] != '\t') {
            return 0;
        }
    }
    return 1;
}

void
empty(char *line, int length)
{
    int i;
    for(i = 0; i < length; i ++) {
        line[i] = 0;
    }
}

uint64
main()
{
    char line[256];
    int lineCount = 0;
    printf("Welcome to Jokerix!\n");
    printf("$ ");
    while(1) {
        uint8 c = getc();
        switch(c) {
            case LF: case CR: 
                printf("\n");
                if(!isEmpty(line, 256)) {
                    sys_exec(line);
                    lineCount = 0;
                    empty(line, 256);
                }
                printf("$ ");
                break;
            case DL:
                if(lineCount > 0) {
                    putchar(BS);
                    putchar(' ');
                    putchar(BS);
                    line[lineCount-1] = 0;
                    lineCount -= 1;
                }
                break;
            default:
                if(lineCount < 255) {
                    line[lineCount] = c;
                    lineCount += 1;
                    putchar(c);
                }
                break;
        }
    }
}

逻辑很简单。最后别忘了在线程初始化时启动 /bin/sh 程序。我们可以多写几个应用程序测试一下。