# Lab6实验报告

## 练习1

### `sched_class`各个函数指针的用法

经过阅读代码，发现调度器类中的主要功能函数如下五个，他们的功能分别如下：

- `init`：初始化调度器的相关参数；
- `enqueue`：将刚刚被调度出的进程放入等待队列，等待调度器进行调度；
- `dequeue`：从当前调度器的调度队列中移除一个进程；
- `pick_next`：根据调度策略选择下一个应该被换出的进程；
- `proc_tick`：每次时钟中断之后应该执行的函数，更新进程的相关信息。

首先，分析uCore的进程调度点，大致分为如下调度点：

- `do_exit`, `do_wait`, `init_main`, `cpu_idle`, `lock`中调用`schedule`函数时由于要执行等待操作或退出操作，如果不放弃CPU使用权是对资源的浪费，属于主动放弃CPU使用权，不涉及调度器规则中的打断；

- `trap`函数中，首先要判断是否中断处于用户态，如果处于用户态且已经被标记为需要调度，则该进程会被主动打断，至于何时被标记需要调度，一部分取决于调度器的设计。

当操作系统调用`schedule`函数进行调度的时候（以RR调度器为例），首先会使用`enqueue`函数将当前进程加入等待队列`run_queue`（一个普通的优先队列），接着使用`pick_next`和`dequeue`函数选出等待队列最前方的进程进行执行。考虑到RR算法主要通过时钟中断来确定调度点，所以每次时钟中断的时候都会执行`proc_tick`函数，对于当前执行的进程的`time_slice`进行减一操作，当进程的时间片用完之后就需要运行调度器。

### 如何实现多级反馈队列调度算法

为了实现多级反馈队列调度算法，并最大限度保证当前的调度器设计架构，应该新增一个调度器类，在`enqueue`的时候判断进程的类型放入到不同的进程队列中，每次在进行进程切换的时候按照优先级选择一个合适的进程进行调度。

需要注意的是需要在每个PCB中加入`priority`变量代表优先级，在入队和出队的时候动态进行优先级修改。

## 练习2

### 实现过程

我的stride算法基于`skew heap`类进行实现，因此只需要进行维护和更新`rq->lab6_run_pool`变量即可，而无需维护`rq->run_list`。

具体来说，就是填写上一个练习的几个有关调度器的函数，大致的思路如下：

- `init`：初始化`rq`和`run_pool`；
- `enqueue`：调用斜堆的插入功能将新的进程按照`stride`的大小插入斜堆，并且将`rq`的进程总数加1；
- `dequeue`：调用斜堆的删除功能删除斜堆的根结点（即`stride`值最小的进程）；
- `pick_next`：选择最小`stride`的进程，并且更新`stride`，使之前进`BIG_STRIDE / 优先级`大小；
- `proc_tick`：每次时钟中断之后应该执行的函数，减小`time_slice`，如果进程剩余的时间为0则将在下一步调用调度器重新选择下一个应该被执行的进程。

此外需要注意的是，原有的实验框架`proc_tick`函数是不会被每次时钟中断都调用的，需要手动加入到`trap.c`的相关实现中，否则在执行`priority.c`程序的时候会出现问题。

## 实现中与参考答案的区别

- 练习2：答案中并没有判断如果优先级过大会出现什么后果（有可能造成`stride`不变化。在极端情况下，若所有进程的优先级都大于`BIG_STRIDE`，调度器只会执行当前`stride`最小的进程且不会改变，会造成其他进程饥饿现象），因此还需要进一步判断。

## 实验中的重要知识点

本次实验中重要的知识点有：

- 处理机调度的概念
- RR算法和Stride算法
- 调度准则

而OS原理中很重要，但在实验中没有对应上的知识点有：

- FCFS算法、短进程优先算法等
- 实时调度和多处理器调度
- 优先级反置