# 调度算法框架

## 结构体

调度算法框架实现为一个结构体，其中保存了各个函数指针。通过实现这些函数指针即可实现各个调度算法。结构体的定义如下：

```c
struct sched_class {
    // 调度类的名字
    const char *name;
    // 初始化run queue
    void (*init)(struct run_queue *rq);
    // 把进程放进run queue，这个是run queue的维护函数
    void (*enqueue)(struct run_queue *rq, struct proc_struct *proc);
    // 把进程取出run queue
    void (*dequeue)(struct run_queue *rq, struct proc_struct *proc);
    // 选择下一个要执行的进程
    struct proc_struct *(*pick_next)(struct run_queue *rq);
    // 每次时钟中断调用
    void (*proc_tick)(struct run_queue *rq, struct proc_struct *proc);
};
```

所有的进程被组织成一个`run_queue`数据结构。这个数据结构虽然没有保存在调度类中，但是是由调度类来管理的。目前ucore仅支持单个CPU核心，所以只有一个全局的`run_queue`。

我们在进程控制块中也记录了一些和调度有关的信息：

```c
struct proc_struct {
    // ...
    // 表示这个进程是否需要调度
    volatile bool need_resched;
    // run queue的指针
    struct run_queue *rq;
    // 与这个进程相关的run queue表项
    list_entry_t run_link;
    // 这个进程剩下的时间片
    int time_slice;
    // 以下几个都和Stride调度算法实现有关
    // 这个进程在优先队列中对应的项
    skew_heap_entry_t lab6_run_pool;
    // 该进程的Stride值
    uint32_t lab6_stride;
    // 该进程的优先级
    uint32_t lab6_priority;
};
```

前面的几个成员变量的含义都比较直接，最后面的几个的含义可以参见Stride调度算法。这也是本次lab的实验内容。

结构体`run_queue`实现了运行队列，其内部结构如下：

```c
struct run_queue {
    // 保存着链表头指针
    list_entry_t run_list;
    // 运行队列中的线程数
    unsigned int proc_num;
    // 最大的时间片大小
    int max_time_slice;
    // Stride调度算法中的优先队列
    skew_heap_entry_t *lab6_run_pool;
};
```

## RR算法

有了这些基础，我们就来实现一个最简单的调度算法：Round-Robin调度算法，也叫时间片轮转调度算法。

时间片轮转调度算法非常简单。它为每一个进程维护了一个最大运行时间片。当一个进程运行够了其最大运行时间片那么长的时间后，调度器会把它标记为需要调度，并且把它的进程控制块放在队尾，重置其时间片。这种调度算法保证了公平性，每个进程都有均等的机会使用CPU，但是没有区分不同进程的优先级（这个也就是在Stride算法中需要考虑的问题）。下面我们来实现以下时间片轮转算法相对应的调度器借口吧！

首先是`enqueue`操作。RR算法直接把需要入队的进程放在调度队列的尾端，并且如果这个进程的剩余时间片为0（刚刚用完时间片被收回CPU），则需要把它的剩余时间片设为最大时间片。具体的实现如下：

```c
static void
RR_enqueue(struct run_queue *rq, struct proc_struct *proc) {
    assert(list_empty(&(proc->run_link)));
    list_add_before(&(rq->run_list), &(proc->run_link));
    if (proc->time_slice == 0 || proc->time_slice > rq->max_time_slice) {
        proc->time_slice = rq->max_time_slice;
    }
    proc->rq = rq;
    rq->proc_num ++;
}
```

`dequeue`操作非常普通，将相应的项从队列中删除即可：

```c
static void
RR_dequeue(struct run_queue *rq, struct proc_struct *proc) {
    assert(!list_empty(&(proc->run_link)) && proc->rq == rq);
    list_del_init(&(proc->run_link));
    rq->proc_num --;
}
```

`pick_next`选取队列头的表项，用`le2proc`函数获得对应的进程控制块，返回：

```c
static struct proc_struct *
RR_pick_next(struct run_queue *rq) {
    list_entry_t *le = list_next(&(rq->run_list));
    if (le != &(rq->run_list)) {
        return le2proc(le, run_link);
    }
    return NULL;
}
```

`proc_tick`函数在每一次时钟中断调用。在这里，我们需要对当前正在运行的进程的剩余时间片减一。如果在减一后，其剩余时间片为0，那么我们就把这个进程标记为“需要调度”，这样在中断处理完之后内核判断进程是否需要调度的时候就会把它进行调度：

```c
static void
RR_proc_tick(struct run_queue *rq, struct proc_struct *proc) {
    if (proc->time_slice > 0) {
        proc->time_slice --;
    }
    if (proc->time_slice == 0) {
        proc->need_resched = 1;
    }
}
```

至此我们就实现完了和时间片轮转算法相关的所有重要接口。类似于RR算法，我们也可以参照这个方法实现自己的调度算法。本次实验中需要同学们自己实现Stride调度算法。

## Stride算法

考察`round-robin`调度器，在假设所有进程都充分使用了其拥有的 CPU 时间资源的情况下，所有进程得到的 CPU 时间应该是相等的。但是有时候我们希望调度器能够更智能地为每个进程分配合理的 CPU 资源。假设我们为不同的进程分配不同的优先级，则我们有可能希望每个进程得到的时间资源与他们的优先级成正比关系。Stride调度是基于这种想法的一个较为典型和简单的算法。除了简单易于实现以外，它还有如下的特点：

* 可控性：如我们之前所希望的，可以证明 Stride Scheduling对进程的调度次数正比于其优先级。
* 确定性：在不考虑计时器事件的情况下，整个调度机制都是可预知和重现的。该算法的基本思想可以考虑如下： 1. 为每个runnable的进程设置一个当前状态stride，表示该进程当前的调度权。另外定义其对应的pass值，表示对应进程在调度后，stride 需要进行的累加值。 2. 每次需要调度时，从当前 runnable 态的进程中选择 stride最小的进程调度。 3. 对于获得调度的进程P，将对应的stride加上其对应的步长pass（只与进程的优先权有关系）。 4. 在一段固定的时间之后，回到 2.步骤，重新调度当前stride最小的进程。

  可以证明，如果令 `P.pass =BigStride / P.priority` 其中`P.priority`表示进程的优先权（大于 1），而 `BigStride`表示一个预先定义的大常数，则该调度方案为每个进程分配的时间将与其优先级成正比。证明过程我们在这里略去，有兴趣的同学可以在网上查找相关资料。将该调度器应用到 ucore 的调度器框架中来，则需要将调度器接口实现如下：
* `init`:
  * 初始化调度器类的信息（如果有的话）。
  * 初始化当前的运行队列为一个空的容器结构。（比如和RR调度算法一样，初始化为一个有序列表）
* `enqueue`
  * 初始化刚进入运行队列的进程 proc的stride属性。
  * 将 proc插入放入运行队列中去（注意：这里并不要求放置在队列头部）。
* `dequeue`
  * 从运行队列中删除相应的元素。
* `pick_next`
  * 扫描整个运行队列，返回其中stride值最小的对应进程。
  * 更新对应进程的stride值，即`pass = BIG_STRIDE / P->priority; P->stride += pass`。
* `proc_tick`:
  * 检测当前进程是否已用完分配的时间片。如果时间片用完，应该正确设置进程结构的相关标记来引起进程切换。
  * 一个 process 最多可以连续运行 `rq.max_time_slice`个时间片。

{% hint style="info" %}
在具体实现时，有一个需要注意的地方：stride属性的溢出问题，在之前的实现里面我们并没有考虑 stride 的数值范围，而这个值在理论上是不断增加的，在 stride溢出以后，基于stride的比较可能会出现错误。比如假设当前存在两个进程A和B，stride属性采用16位无符号整数进行存储。当前队列中元素如下（假设当前运行的进程已经被重新放置进运行队列中）：

{% endhint %}

| A.stride(实际值) | A.stride(理论值) | A.pass(=BigStride/A.priority) |
| ------------- | ------------- | ----------------------------- |
| 65534         | 65534         | 100                           |
| B.stride(实际值) | B.stride(理论值) | B.pass(=BigStride/B.priority) |
| 65535         | 65535         | 50                            |

{% hint style="info" %}
此时应该选择A作为调度的进程，而在一轮调度后，队列将如下：
{% endhint %}

| A.stride(实际值) | A.stride(理论值) | A.pass(=BigStride/A.priority) |
| ------------- | ------------- | ----------------------------- |
| 98            | 65634         | 100                           |
| B.stride(实际值) | B.stride(理论值) | B.pass(=BigStride/B.priority) |
| 65535         | 65535         | 50                            |

{% hint style="info" %}
可以看到由于溢出的出现，进程间stride的理论比较和实际比较结果出现了偏差。我们首先在理论上分析这个问题：令`PASS_MAX`为当前所有进程里最大的步进值。则我们可以证明如下结论：对每次Stride调度器的调度步骤中，有其最大的步进值`STRIDE_MAX`和最小的步进值`STRIDE_MIN`之差：

`STRIDE_MAX – STRIDE_MIN <= PASS_MAX`

有了该结论，在加上之前对优先级有`Priority > 1`限制，我们有`STRIDE_MAX – STRIDE_MIN <= BIG_STRIDE`,于是我们只要将BigStride取在某个范围之内，即可保证对于任意两个 Stride 之差都会在机器整数表示的范围之内。而我们可以通过其与0的比较结构，来得到两个Stride的大小关系。在上例中，虽然在直接的数值表示上 98 < 65535，但是 98 - 65535 的结果用带符号的 16位整数表示的结果为99,与理论值之差相等。所以在这个意义下 98 > 65535。基于这种特殊考虑的比较方法，即便Stride有可能溢出，我们仍能够得到理论上的当前最小Stride，并做出正确的调度决定。
{% endhint %}