毕设(10)：基于时间片的协作式多任务系统

前言

之前的 xOS 运行很简单，就是简单的 shell，用户通过输入命令，回车后，离开 shell，去执行具备某个功能的函数，执行完再返回。

这样的设计有问题，因为一旦离开 shell，就意味着不能再接受输入了。而且一旦遇到意外，比如执行了某些代码，可能就再也回不到 shell 了。

因此我打算对 xOS 进行升级，基于时钟中断和原来的异常入口。

从中断到调度

任务的单位是线程 Thread，要对某一个线程定义，就得用一个数据结构来描述，线程控制块。

由于处理器是一个状态机，我们只要保存某一个线程 A 的状态，再把它赋值给处理器的状态，那么就可以认为此时处理器正在运行线程 A。

当然这里所说的状态不是指所有的状态。对于用户线程而言，它的状态可以由 32 个通用寄存器、处理器的 PC、当前的 CRMD、线程的运行状态、线程的 id、线程的名字、线程的输出buffer、 线程的栈空间。

其中 CRMD 比较特殊，因为发生中断后，处理器已经把 CRMD 保存到 PRMD 中了：

//prmd
always @(posedge clk) begin
    if (rst) begin
        csr_prmd[31:3] <= 29'b0;
    end
    else if (excp_flush) begin
        csr_prmd[`PPLV] <= csr_crmd[`PLV];
        csr_prmd[ `PIE] <= csr_crmd[`IE ];
    end
    else if (prmd_wen) begin
        csr_prmd[`PPLV] <= csr_wdata[`PPLV];
        csr_prmd[ `PIE] <= csr_wdata[ `PIE];
    end
end

之后才会通过 csr_eerntry 进入到 trap_entry，trap_entry 会保存被中断的线程的状态到 sp，然后将sp 复制到 a0 传递给 trap_dispatch：

move    $a0, $sp
bl      trap_dispatch

依靠强大的 C 语言类型转换，可以将 trap_entry 保存的上下文转成 trap_frame_t：

void trap_dispatch(trap_frame_t *tf) {
    uint32_t ecode = (tf->estat >> ESTAT_ECODE_SHIFT) & ESTAT_ECODE_MASK;
    if (ecode == ECODE_INT) {
        /* Hardware/software interrupt */
        interrupt_handler(tf);
    } else {
        /* Exception */
        exception_handler(tf);
    }
}

需要注意的是，为了转成后的结构体一致，需要保证 trap_frame_t 的结构和 trap_entry 中保存的内存排布完全一致：

typedef struct {
    uint32_t ra;        /* $r1  - Return Address */
    uint32_t tp;        /* $r2  - Thread Pointer */
    uint32_t sp;        /* $r3  - Stack Pointer */
    uint32_t a0;        /* $r4  - Argument 0 */
    uint32_t a1;        /* $r5  - Argument 1 */
    uint32_t a2;        /* $r6  - Argument 2 */
    uint32_t a3;        /* $r7  - Argument 3 */
    uint32_t a4;        /* $r8  - Argument 4 */
    uint32_t a5;        /* $r9  - Argument 5 */
    uint32_t a6;        /* $r10 - Argument 6 */
    uint32_t a7;        /* $r11 - Argument 7 */
    uint32_t t0;        /* $r12 - Temporary 0 */
    uint32_t t1;        /* $r13 - Temporary 1 */
    uint32_t t2;        /* $r14 - Temporary 2 */
    uint32_t t3;        /* $r15 - Temporary 3 */
    uint32_t t4;        /* $r16 - Temporary 4 */
    uint32_t t5;        /* $r17 - Temporary 5 */
    uint32_t t6;        /* $r18 - Temporary 6 */
    uint32_t t7;        /* $r19 - Temporary 7 */
    uint32_t t8;        /* $r20 - Temporary 8 */
    uint32_t r21;       /* $r21 - Reserved */
    uint32_t fp;        /* $r22 - Frame Pointer */
    uint32_t s0;        /* $r23 - Saved 0 */
    uint32_t s1;        /* $r24 - Saved 1 */
    uint32_t s2;        /* $r25 - Saved 2 */
    uint32_t s3;        /* $r26 - Saved 3 */
    uint32_t s4;        /* $r27 - Saved 4 */
    uint32_t s5;        /* $r28 - Saved 5 */
    uint32_t s6;        /* $r29 - Saved 6 */
    uint32_t s7;        /* $r30 - Saved 7 */
    uint32_t s8;        /* $r31 - Saved 8 */
    /* CSR values */
    uint32_t era;       /* Exception Return Address */
    uint32_t prmd;      /* Pre-exception Mode */
    uint32_t estat;     /* Exception Status */
} trap_frame_t;

接着拿着这个线程的上下文去 interrupt_handler，这里以时间中断为例：

void __attribute__((noinline)) timer_irq_handler(trap_frame_t *tf) {
    timer_tick_count++;

    /* Clear timer interrupt */
    csr_write(CSR_TICLR, 0x1);
    schedule(tf);
}

清理时钟中断是必要的，因为清理掉意味着已经处理或者马上处理完了这个中断。之后就进入调度环节：

void schedule(trap_frame_t *tf) {
    /* Save current task context (if not first schedule) */
    if (current_task >= 0 && tf != NULL) {
        task_t *curr = &tasks[current_task];

        /* Copy trap frame to TCB */
        curr->regs[1] = tf->ra;
        curr->regs[2] = tf->tp;
        curr->regs[3] = tf->sp;
        curr->regs[4] = tf->a0;
        curr->regs[5] = tf->a1;
        curr->regs[6] = tf->a2;
        curr->regs[7] = tf->a3;
        curr->regs[8] = tf->a4;
        curr->regs[9] = tf->a5;
        curr->regs[10] = tf->a6;
        curr->regs[11] = tf->a7;
        curr->regs[12] = tf->t0;
        curr->regs[13] = tf->t1;
        curr->regs[14] = tf->t2;
        curr->regs[15] = tf->t3;
        curr->regs[16] = tf->t4;
        curr->regs[17] = tf->t5;
        curr->regs[18] = tf->t6;
        curr->regs[19] = tf->t7;
        curr->regs[20] = tf->t8;
        curr->regs[21] = tf->r21;
        curr->regs[22] = tf->fp;
        curr->regs[23] = tf->s0;
        curr->regs[24] = tf->s1;
        curr->regs[25] = tf->s2;
        curr->regs[26] = tf->s3;
        curr->regs[27] = tf->s4;
        curr->regs[28] = tf->s5;
        curr->regs[29] = tf->s6;
        curr->regs[30] = tf->s7;
        curr->regs[31] = tf->s8;
        curr->era = tf->era;
        curr->prmd = tf->prmd;

        curr->state = TASK_READY;
    }
    int next = current_task;
    int attempts = 0;

    do {
        /* Move to next task */
        if (next < 0) {
            next = 0;  /* First schedule */
        } else {
            next = (next + 1) % MAX_TASKS;
        }
        /* Check if this task is ready */
        if (tasks[next].state == TASK_READY) {
            break;
        }
        attempts++;
    } while (attempts < MAX_TASKS);

    /* No ready task found */
    if (attempts >= MAX_TASKS) {
        printf("[SCHED] ERROR: No ready task found!\n");
        while (1);
    }

    /* Switch to next task */
    current_task = next;
    tasks[next].state = TASK_RUNNING;
    switch_to(&tasks[next]);
}

current_task 是一个全局变量，表示当前的 task 的 id。如果 id 合法，就把 trap_frame 中保存的上下文保存到 TCB 中。包括 通用寄存器、era、prmd、线程的状态。

接着就是调度了，这里直接循环遍历，找到一个出在就绪态的任务，并且修改 current_task 为将要运转的线程，再修改它的运行状态，然后 switch_to 到它。

switch_to() 是一段汇编指令，用于将这个 TCB 的状态 load 到响应的 CPU 寄存器中：

switch_to:
    /* a0 points to task_t, which starts with regs[32] */

    /* Restore general purpose registers from TCB */
    /* Note: We restore most registers, but skip $r0 (always 0) */

    ld.w    $r1,  $a0, 4       # $ra
    ld.w    $r2,  $a0, 8       # $tp
    ld.w    $r3,  $a0, 12      # $sp (critical!)

    /* Save a0 temporarily, we need it to access TCB */
    move    $t0, $a0

    ld.w    $r4,  $t0, 16      # $a0
    ld.w    $r5,  $t0, 20      # $a1
    ld.w    $r6,  $t0, 24      # $a2
    ld.w    $r7,  $t0, 28      # $a3
    ld.w    $r8,  $t0, 32      # $a4
    ld.w    $r9,  $t0, 36      # $a5
    ld.w    $r10, $t0, 40      # $a6
    ld.w    $r11, $t0, 44      # $a7

    /* Restore temporary registers (t2-t8, skip t0 and t1 for now) */
    ld.w    $r14, $t0, 56      # $t2
    ld.w    $r15, $t0, 60      # $t3
    ld.w    $r16, $t0, 64      # $t4
    ld.w    $r17, $t0, 68      # $t5
    ld.w    $r18, $t0, 72      # $t6
    ld.w    $r19, $t0, 76      # $t7
    ld.w    $r20, $t0, 80      # $t8

    /* Restore r21 and saved registers */
    ld.w    $r21, $t0, 84      # $r21
    ld.w    $r22, $t0, 88      # $fp
    ld.w    $r23, $t0, 92      # $s0
    ld.w    $r24, $t0, 96      # $s1
    ld.w    $r25, $t0, 100     # $s2
    ld.w    $r26, $t0, 104     # $s3
    ld.w    $r27, $t0, 108     # $s4
    ld.w    $r28, $t0, 112     # $s5
    ld.w    $r29, $t0, 116     # $s6
    ld.w    $r30, $t0, 120     # $s7
    ld.w    $r31, $t0, 124     # $s8

    /* Restore CSR registers (use $t1 as temp before restoring it) */
    /* ERA is at offset 128 (32 regs × 4 bytes) */
    ld.w    $t1, $t0, 128      # Load ERA
    csrwr   $t1, 0x6           # Write to CSR_ERA

    /* PRMD is at offset 132 */
    ld.w    $t1, $t0, 132      # Load PRMD
    csrwr   $t1, 0x1           # Write to CSR_PRMD

    /* Now restore $t1 and $t0 */
    ld.w    $r13, $t0, 52      # Restore $t1
    ld.w    $r12, $t0, 48      # Restore $t0

    /* Return to task using ertn */
    /* This will:
     *   - Jump to address in ERA
     *   - Restore privilege level from PRMD
     *   - Enable interrupts if PRMD.IE was set
     */
    ertn
.end

这里需要注意的是，我们用 t0、t1 作为恢复其它寄存器的桥梁，因此最后恢复它们就好。当 ertn 的时候：

else if (ertn_flush) begin
    csr_crmd[ `PLV] <= csr_prmd[`PPLV]; // 恢复特权等级
    csr_crmd[  `IE] <= csr_prmd[`PIE ]; // 恢复中断
    if (eret_tlbrefill_excp) begin
        csr_crmd[`DA] <= 1'b0;
        csr_crmd[`PG] <= 1'b1;
    end
end

这样返回后，就回到被调度的任务了。

TCB

从上面的讨论中可以看到，TCB 除了包含基本状态以外，我还加了 task_output_t output，这是因为每一个 task 都有信息输出，因此可以在任务执行的时候，将它的信息输出到 output 内存区。

typedef struct {
    uint32_t regs[32];
    uint32_t era;
    uint32_t prmd;

    /* Task metadata */
    task_state_t state;     /* Task state */
    int task_id;            /* Task ID */
    char name[32];          /* Task name (for debugging) */
    /* Output buffer */
    task_output_t output;   /* Task output buffer */
    /* Stack */
    uint32_t stack[TASK_STACK_SIZE];  /* Task's stack */
} task_t;

task_output_t 作为 TCB，因为它必须也有状态的：

typedef struct {
    char *buffer;           /* Pointer to 1MB buffer */
    uint32_t write_pos;     /* Write position (circular) */
    uint32_t total_bytes;   /* Total bytes written (for overflow detection) */
    int is_foreground;      /* 1 = foreground (print to UART), 0 = background */
} task_output_t;

创建一个 task

有了 TCB 创建一个 线程也就不难了。首先获取一个线程 tid：在 tasks 中遍历，只要找到死掉的任务或者 unused 就行了：

static int find_free_slot(void) {
    for (int i = 0; i < MAX_TASKS; i++) {
        if (tasks[i].state == TASK_UNUSED || tasks[i].state == TASK_DEAD) {
            return i;
        }
    }
    return -1;
}

然后对这个 tasks[tid] 就可以操作了。将上下文 32 个通用寄存器清零，然后非常关键的将 regs[3] 也就是 sp 赋值为待用的 stack 的指针。接着设置 era 为 函数入口，然后就是设置 prmd、状态、线程名、以及是否在后台运行等。

这里需要关注的是后台执行的线程。如果是在后台执行的，那么就要给它 malloc 一个内存区域（calloc 更合适，会自动清零），然后初始化输出区。

代码大致如下：

int task_create(void (*entry)(void), const char *name) {
    int tid = find_free_slot();
    if (tid < 0) {
        printf("[SCHED] ERROR: No free task slot\n");
        return -1;
    }
    task_t *task = &tasks[tid];
    /* Initialize registers to 0 */
    for (int i = 0; i < 32; i++) {
        task->regs[i] = 0;
    }
    task->regs[3] = (uint32_t)&task->stack[TASK_STACK_SIZE - 1];
    task->era = (uint32_t)entry;
    task->prmd = 0x4;  /* 0b0100: PLV=0, IE=1 */

    /* Set task metadata */
    task->state = TASK_READY;
    safe_strcpy(task->name, name, sizeof(task->name));

    if (task->output.buffer == NULL) {
        task->output.buffer = (char*)malloc(TASK_OUTPUT_BUF_SIZE);
        if (task->output.buffer == NULL) {
            printf("[SCHED] ERROR: Failed to allocate output buffer for task %d\n", tid);
            task->state = TASK_UNUSED;
            return -1;
        }
        task->output.write_pos = 0;
        task->output.total_bytes = 0;
    }
    if (tid == 0) {
        task->output.is_foreground = 1;
        foreground_task = 0;
    } else {
        task->output.is_foreground = 0;
    }

    num_tasks++;

    return tid;
}

我把所有的任务都设置在后台执行，shell 永远在台前执行（shell 不能在后台，它应该时钟保持交互性！）。

运行 task0

xOS 在启动的时候，它会直接进入到 shell 呢还是先创建一个 shell 进程等着调度或者手动调度？我认为这是一个哲学问题。

因为如果直接进入 shell 那么 shell 就不是一个 task 了，就成了 OS 的一部分且不参与调度，这显然不符合设计思想。如果把 shell 设计成一个 task，那么时钟中断调度他的时候，肯定要保存它运行之前的程序的上下文，这个程序都不是一个 task，连 TCB 都没有，因此 schedule 就会犯难。

我的做法是，进入 shell 之前，创建 shell 的 task，然后手动调度。

int main(void) {
    bsp_uart_init(0, BAUDRATE);
    system_init();

    task_create(shell_task, "shell");
    schedule(NULL);

    /* Should never reach here */
    while (1);

    return 0;
}

shell_task 是一个特殊的 task，它会开启时钟调度：

void shell_task(void) {
    timer_start();
    /* Initialize shell */
    shell_init();
    /* Run shell (infinite loop) */
    shell_run();

    /* Should never reach here */
    task_exit();
}

这里的关键之处就是这是第一个 task，因此它的 tid 一定是 0，所以它会被标记被 foreground_task。

手动 schedule(NULL) 的关键之处传入了一个空指针，这就会避免保存上下文，只会创建上下文。然后自然而然就跳转到了 shell 中，这样就解决了上面第一个 task 保存上下文的问题。

运行 task1

task0 是所有 task 的祖宗，因为所有的 task 都将是它创建的。

在 shell 中输入回车后，就会跳转到

void shell_input_char(char c) {
    switch (c) {
        case '\n':  /* Enter */
            printf("\n");  // UART 驱动会自动转换为 \r\n
            execute_command();
            cmd_pos = 0;
            shell_print_prompt();
            break;

execute_command() 执行结束后，就会重置 cmd_pos，然后返回 shell。我们关注 execute_command() 的设计。

首先要区分内置命令和外置命令。xOS 对于内置的命令的定义是，shell 在执行它的之后，执行完后才会回到 shell；外置命令是创建一个 task 然后返回到 shell。

由于内置命令都比较短且可靠性极高，不会出现不会返回情形。对于外置命令，是一些执行时间很长的命令，它们会和 shell 一起在宏观上并发，就算出问题了，可以在 shell 中 kill 掉。

当我们输入不同的外部命令的时候，需要统一的接口：命令名字 + 命令参数，而且 命令参数 的数量还不一样多。那么应该怎么解决这个办法呢？

需要明白的是，shell 负责传递 一组字符串，然后进入到 execute_command() 中 parse cmd_buffer 从而得到命令的数据结构。因此我们得创建一个 task 的中间体：task_wrapper。这个中间体会在真正运行 task 之前做一些准备工作。将相应的 task_contexts 完善：主要就是将 arg_buffer 中的信息复制拷贝的 argv_storage。

然后通过 handler 直接运行：ctx->handler(ctx->argc, ctx->argv_storage)就行了：

typedef int (*shell_cmd_handler_t)(int argc, char *argv[]);

typedef struct {
    shell_cmd_handler_t handler;
    int argc;
    char *argv_storage[SHELL_MAX_ARGS];
    char arg_buffer[SHELL_CMD_MAX_LEN];
} task_cmd_context_t;

...
...

/* Task wrapper function - executes command and exits */
static void task_wrapper(void) {
    int tid = get_current_task();
    if (tid < 0 || tid >= MAX_TASKS) {
        task_exit();
    }
    task_cmd_context_t *ctx = &task_contexts[tid];
    /* Reconstruct argv pointers from stored buffer */
    char *p = ctx->arg_buffer;
    for (int i = 0; i < ctx->argc; i++) {
        ctx->argv_storage[i] = p;
        while (*p++);  /* Skip to next null terminator */
    }
    /* Execute command handler */
    ctx->handler(ctx->argc, ctx->argv_storage);

    /* Task complete, exit */
    task_exit();
}

为什么这样可以运行呢？先看之前的 parse_command，它可以把来自 shell 的命令字符串转成了标准的形式：

/* Parse command line into argc/argv */
static int parse_command(char *cmd, char *argv[], int max_args) {
    int argc = 0;
    char *p = cmd;

    while (*p && argc < max_args) {
        /* Skip leading spaces */
        while (*p == ' ') p++;
        if (*p == '\0') break;

        /* Start of argument */
        argv[argc++] = p;

        /* Find end of argument */
        while (*p && *p != ' ') p++;

        /* Null terminate */
        if (*p) {
            *p++ = '\0';
        }
    }

    return argc;
}

比如输入 countdown xxx，这里就会解析成 countdown\0xxx\0，argc 也是 2。

回过头关注 execute_command(void)：

/* Countdown command runs in background */
            if (strcmp(cmd->name, "countdown") == 0 || 0) {
                run_background = 1;
            }

            if (run_background) {
                irq_global_disable();
                /* Create background task */
                int tid = task_create(task_wrapper, cmd->name);
                if (tid < 0) {
                    irq_global_enable();
                    return;
                }
                /* Store command context for the task */
                task_cmd_context_t *ctx = &task_contexts[tid];
                ctx->handler = cmd->handler;
                ctx->argc = argc;

                /* Copy arguments into task's buffer */
                char *dst = ctx->arg_buffer;
                for (int i = 0; i < argc; i++) {
                    int len = strlen(argv[i]);
                    strcpy(dst, argv[i]);
                    dst += len + 1;  /* Include null terminator */
                }
                /* Re-enable interrupts - now it's safe to schedule the task */
                irq_global_enable();

可以看到，它在创建 task_cmd_context_t 的时候，拷贝了 handler、argc、以及使用 strlen()、strcpy() 逐个拷贝了 argv 中的每一个字符串。

需要注意的是，mylibc 中的 strlen() 不包括字符串的结束符：

/*
 * strlen - 计算字符串长度
 *
 * 返回字符串 s 的长度（不包括结尾的 '\0'）
 */
size_t strlen(const char *s) {
    const char *p = s;
    while (*p) {
        p++;
    }
    return p - s;
}

另外 strcpy(dst, argv[i]) 拷贝了 '\0'：

/*
 * strcpy - 复制字符串
 *
 * 将 src 复制到 dst（包括 '\0'）
 * 返回 dst
 * 警告：不检查缓冲区大小，可能溢出，建议使用 strncpy
 */
char *strcpy(char *dst, const char *src) {
    char *ret = dst;
    while ((*dst++ = *src++)) {
        /* 遇到 '\0' 成功复制，但是赋值表达式的指是 0，然后退出*/
    }
    return ret;
}

此时，arg_buffer 就装好了良好的格式化的参数列表。

当 task 执行的时候，就会把各个参数的字符串指针赋值给 argv_storage：

char *p = ctx->arg_buffer;
for (int i = 0; i < ctx->argc; i++) {
    ctx->argv_storage[i] = p;
    while (*p++);  /* Skip to next null terminator */
}

这符合函数调用约定，然后调用 handler，就可以执行了。另外，创建 task 之前应该关闭中断，想想为什么。

退出 task1

task 执行结束之后，应该回收资源。包括 tid 置为 dead 标识，清空输出 buffer。其它标志位会在创建 task 的时候重置，因此退出 task 的时候就不用重置了。

接着就是手动触发调度，因为当前的线程不用保存上下文了，简直妙不可言：

void task_exit(void) {
    if (current_task < 0) {
        while (1);
    }
    /* Free output buffer */
    if (tasks[current_task].output.buffer != NULL) {
        free(tasks[current_task].output.buffer);
        tasks[current_task].output.buffer = NULL;
    }

    /* Mark task as dead */
    tasks[current_task].state = TASK_DEAD;
    num_tasks--;

    /* Trigger immediate reschedule */
    schedule(NULL);

    /* Never returns */
    while (1);
}

至此，一个完整的基于时间调度的 xOS 就设计的有了基础功能了。

运行效果

========================================
  xOS - Simple Operating System
  for LoongArch32R SoC
========================================

Type 'help' for available commands.

xos> help
Available commands:
help - Show available commands
echo - Echo arguments (e.g. echo hello world)
clear - Clear screen
info - Show system information
ps - Show task status
fg - Move task to foreground (e.g. fg 1)
bg - Move task to background (e.g. bg 1)
logs - Show task output history (e.g. logs 1)
heap - Show heap memory statistics
countdown - Countdown from N (e.g. countdown 10)
xos> countdown 50
xos> ps
TID STATE  FG NAME        OUTPUT
--- ------ -- ----------- ------
*0  RUN    FG shell 0KB
 1  READY  BG countdown 0KB

Active tasks: 2/8
Current task: 0
Foreground task: 0
xos> fg 1
Task 1 moved to foreground
xos> 24...
23...
22...
21...
20...

输入 countdown 50 运行在后台，可以通过 ps 查看运行信息，可以通过 fg 移动到前台（谨慎，因为会占用 shell，影响输入），也可以使用 bg 移动到后台。