Pwn进你的心
0%

Ucore-Lab6

Posted on Edited on In 19k 17 mins.

CPU资源的时分复用

进程切换：CPU资源的当前占用者切换

  • 保存当前进程在PCB中的执行上下文（CPU状态）
  • 恢复下一个进程的执行上下文

处理机调度：

  • 从就绪队列中挑选下一个占用CPU运行的进程
  • 从多个可用CPU中挑选就绪进程可使用的CPU资源

调度程序：挑选就绪进程的内核函数

  • 调度策略：依据什么原理挑选进程/线程
  • 调度时机：什么时候进行调度

内核运行调度程序的条件：

  • 进程从运行状态切换到等待状态
  • 进程被终结了

非抢占系统：

  • 当前进程主动放弃CPU时

可抢占系统：

  • 中断请求被服务例程响应完成时
  • 当前进程被抢占
    • 进程的时间片耗尽
    • 进程从等待状态切换到就绪状态

调度准则

  • 比较调度算法的准则

    • CPU使用率：CPU处于忙状态的时间百分比
    • 吞吐量：单位时间内完成的进程数量
    • 周转时间：进程从初始化到结束（包括等待）的总时间
    • 等待时间：进程在就绪队列中的总时间
    • 响应时间：从提交请求到产生响应所花费的总时间

  • 调度策略的目标

    • 减少响应时间：及时处理用户的输入，尽快将输出反馈给用户
    • 减少平均响应时间的波动：在交互系统中，可预测性比高差异低平均更重要

  • 调度策略的吞吐量目标

    • 增加吞吐量
      • 减小开销（例如上下文切换的开销）
      • 系统资源的高效利用（例如CPU和IO设备的并行使用）
    • 减少每个进程的等待时间
    • 保证吞吐量不受用户交互的影响

时钟中断

  • 时钟中断是一种硬中断，由时间硬件（系统定时器，一种可编程硬件）产生，CPU处理后交由时间中断处理程序来完成更新系统时间、执行周期性任务等
  • 系结构相关部分被注册到内核中，确保中断产生时能执行，这部分不能有耗时操作，主要是更新时间与调用结构无关部分列程（异步）
  • 已到期的定时器由体系结构无关部分来处理，其它的一些耗时操作，如显示时间的更新也在这一部分

内核定时器

  • 内核定时器产生的是软中断，软中断是进程相关的，它不会中断CPU的处理
  • 使用定时器时，将软中断注册入内核
  • 在每个时钟中断周期中，系统会检测到期到期定时器，触发软中断，判断时间到期，则执行定时器处理函数，最后清除掉定时器软中断

用户定时器

  • 用户定时器是线程相关的，定时器产生的消息只会发送给注册线程
  • 定时器消息属于最低优先级的消息，当线程的队列中没有其他消息时，才检索该消息

队列

  • 在 SMP（对称多处理器）环境下，每个 CPU 对应一个 run_queue（可执行队列）
  • 如果一个进程处于 TASK_RUNNING 状态（可执行状态），则它会被加入到其中一个 run_queue（且同一时刻仅会被加入到一个 run_queue），以便让调度程序安排它在这个 run_queue 对应的 CPU 上面运行
  • 一个CPU对应一个 run_queue 这样的设计，其好处是：
    • 一个持续处于 TASK_RUNNING 状态的进程总是趋于在同一个 CPU 上面运行（其间，这个进程可能被抢占、然后又被调度），这有利于进程的数据被 CPU 所缓存，提高运行效率
    • 各个 CPU 上的调度程序只访问自己的 run_queue，避免了竞争

结构体 run_queue 用于描述队列：

1
2
3
4
5
6
struct run_queue {
    list_entry_t run_list; /* 其运行队列的链表结构,可以看作是队列结点(运行队列链表) */
    unsigned int proc_num; /* 表示其内部的进程总数 */
    int max_time_slice; /* 每个进程一轮占用的最多时间片 */
    skew_heap_entry_t *lab6_run_pool; /* 优先队列形式的进程容器(只在LAB6中使用) */
};

进程运行队列（就绪队列）：

  • linux 提供了很多队列，但本实验只涉及到了运行队列（运行队列和就绪队列是同一个东西）
  • 在 ucore 框架中，运行队列存储的是当前可以调度的进程，所以，只有状态为 runnable 的进程才能够进入运行队列，当前正在运行的进程并不会在运行队列中
  • 运行队列通过链表的形式进行组织，链表的每一个节点是一个 list_entry_t，每个 list_entry_t 又对应到了 struct proc_struct *（和前面实验对于链表的操作如出一辙）

多级反馈队列

RR时间片轮转原理

  • 在采用时间片轮转算法中，所有的就绪进程按 FCFS 策略排成一个就绪队列
  • 系统可设置每隔一定时间便产生一次中断，去激活进程调度程序进行调度，把CPU分配给队首进程，并令其执行一个时间片
  • 当它运行完毕后，又把处理机分配给就绪队列中新的队首进程，也让它执行一个时间片
  • 这样，就可以保证就绪队列中的所有进程在确定的时间段内，都能获得一个时间片的处理机时间

多级反馈队列调度机制

  • 设置多个就绪队列，在系统中设置多个就绪队列，并为每个队列赋予不同的优先
  • 第一个队列的优先级最高，第二个次之，其余队列的优先级逐个降低
  • 该算法为不同列中的进程所赋予的执行时间片的大小也各不相同，在优先级愈高的队列中，其时间片愈小
  • 每个队列都采用 FCFS 算法，当新进程进入内存后，首先将它放入第一队列的末尾，按 FCFS 原则等待调度
    • 当轮到该进程执行时，如它能在该时间片内完成，便可撤离系统
    • 否则，即它在一个时间片结束时尚未完成，调度程序将其转入第二队列的末尾等待调度
    • 如果它在第二队列中运行个时间片后仍未完成， 再依次将它放入第三队列 … 依此类推
  • 当进程最后被降到第n队列后，在第n队列中便采取按RR方式运行
  • PS：这里只讨论了最简单的情况，中途没有进程进行“抢占”

斜堆(Skew Heap)

斜堆(Skew heap)也叫自适应堆(self-adjusting heap)，它是左倾堆的一个变种，和左倾堆一样，它通常也用于实现优先队列，它的合并操作的时间复杂度也是 O(lg n)

相比于左倾堆，斜堆的节点没有”零距离”这个属性，除此之外，它们斜堆的合并操作也不同

斜堆的合并操作算法如下：

  • 第1步：如果一个空斜堆与一个非空斜堆合并，返回非空斜堆
  • 第2步：如果两个斜堆都非空，那么比较两个根节点，取较小堆的根节点为新的根节点，将 “较小堆的根节点的右孩子” 和 “较大堆” 进行合并
  • 第3步：合并后，交换新堆根节点的左孩子和右孩子

第3步是斜堆和左倾堆的合并操作差别的关键所在：

  • 如果是左倾堆，则合并后要比较左右孩子的零距离大小
  • 若右孩子的零距离 > 左孩子的零距离，则交换左右孩子
  • 最后设置根的零距离

ucore 中和斜堆有关的结构

  • skew_heap_entry：用于记录斜堆各个节点的信息
1
2
3
struct skew_heap_entry {
     struct skew_heap_entry *parent, *left, *right;
};
  • compare_f：一个函数指针，指向 proc_stride_comp_f
1
typedef int(*compare_f)(void *a, void *b);

ucore 中和斜堆有关的函数

  • proc_stride_comp_f：优先队列的比较函数， 用于测优先级 ，主要思路就是通过步数相减，然后根据其正负比较大小关系（具体的数学原理我真的搞不明白，反正这个函数可以用来测优先级就对了）
1
2
3
4
5
6
7
8
9
10
static int
proc_stride_comp_f(void *a, void *b)
{
     struct proc_struct *p = le2proc(a, lab6_run_pool); // 获取进程a
     struct proc_struct *q = le2proc(b, lab6_run_pool); // 获取进程b
     int32_t c = p->lab6_stride - q->lab6_stride; // 步数相减,通过正负比较大小关系
     if (c > 0) return 1; /* b的优先级高(stride更小) */
     else if (c == 0) return 0; 
     else return -1; /* a的优先级高(stride更小) */
}
  • skew_heap_init：初始化斜堆
1
2
3
4
5
static inline void
skew_heap_init(skew_heap_entry_t *a)
{
     a->left = a->right = a->parent = NULL; /* 置空斜堆的3个索引点 */
}
  • skew_heap_insert：将新的进程插入到表示就绪队列的斜堆中，该函数的返回结果是斜堆的新的根
1
2
3
4
5
6
7
static inline skew_heap_entry_t *
skew_heap_insert(skew_heap_entry_t *a, skew_heap_entry_t *b,
                 compare_f comp)
{
     skew_heap_init(b); /* 置空斜堆b */
     return skew_heap_merge(a, b, comp); /* 合并这两个斜堆,并返回得到的新堆 */
}
  • skew_heap_remove：删除斜堆中的指定进程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static inline skew_heap_entry_t *
skew_heap_remove(skew_heap_entry_t *a, skew_heap_entry_t *b,
                 compare_f comp)
{
     skew_heap_entry_t *p   = b->parent;
     skew_heap_entry_t *rep = skew_heap_merge(b->left, b->right, comp); /* 合并这两个斜堆,并返回得到的新堆 */
     if (rep) rep->parent = p;
     
     if (p)
     {
          if (p->left == b)
               p->left = rep;
          else p->right = rep;
          return a;
     }
     else return rep;
}
  • skew_heap_merge：合并这两个斜堆，并返回得到的新堆（没学对应的数据结构，看不懂）
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
28
29
30
31
static inline skew_heap_entry_t *
skew_heap_merge(skew_heap_entry_t *a, skew_heap_entry_t *b,
                compare_f comp)
{
     if (a == NULL) return b;
     else if (b == NULL) return a;
     
     skew_heap_entry_t *l, *r;
     if (comp(a, b) == -1) /* 执行proc_stride_comp_f: a的优先级更高 */
     {
          r = a->left;
          l = skew_heap_merge(a->right, b, comp);
          
          a->left = l;
          a->right = r;
          if (l) l->parent = a;

          return a;
     }
     else /* 执行proc_stride_comp_f: b的优先级更高 */
     {
          r = b->left;
          l = skew_heap_merge(a, b->right, comp);
          
          b->left = l;
          b->right = r;
          if (l) l->parent = b;

          return b;
     }
}

规律总结：

  • stride 值最小的进程在斜堆的最顶端（优先度更高）

练习0-把 lab5 的内容复制粘贴到 lab6

lab6 的代码有一些不同的地方

在 proc_struct 添加有关 时钟中断 的部分：

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
28
struct proc_struct {
    enum proc_state state;      // 当前进程的状态
    int pid;                    // 进程ID
    int runs;                   // 当前进程被调度的次数
    uintptr_t kstack;           // 内核栈
    volatile bool need_resched; // 是否需要被调度
    struct proc_struct *parent; // 父进程ID
    struct mm_struct *mm;       // 当前进程所管理的虚拟内存页，包括其所属的页目录项PDT
    struct context context;     // 保存的进程上下文,用于进程切换
    struct trapframe *tf;       // 中断帧指针,指向内核栈的某个位置(保存有中断上下文)
    uintptr_t cr3;                  // 页目录表的地址
    uint32_t flags;                 // 当前进程的相关标志
    char name[PROC_NAME_LEN + 1];   // 进程名称(可执行文件名)
    list_entry_t list_link;         // 进程链表 
    list_entry_t hash_link;         // 进程哈希表 
    int exit_code;    				 /* lab5新增:描述线程退出时的原因 */ 
    uint32_t wait_state;			 /* lab5新增:描述线程进入wait阻塞态的原因 */ 
    struct proc_struct *cptr, *yptr, *optr;    /* lab5新增:用于组织子进程链表 */ 
    
    /* <-- 以下都是lab6新增的部分 --> */
    
    struct run_queue *rq;                       // 指向运行队列(就绪队列)
    list_entry_t run_link;                      // 在运行队列中链接的条目
    int time_slice;                             // 占用CPU的时间片
    skew_heap_entry_t lab6_run_pool;            // 仅适用于LAB6:运行池中的条目
    uint32_t lab6_stride;                       // 仅适用于LAB6:流程的当前步幅
    uint32_t lab6_priority;                     // 仅适用于LAB6:进程的优先级(由LAB6_set_priority设置)
};

对应的 alloc_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
27
28
29
30
static struct proc_struct *
alloc_proc(void) {
    struct proc_struct *proc = kmalloc(sizeof(struct proc_struct));
    if (proc != NULL) {
        proc->state = PROC_UNINIT;
        proc->pid = -1;
        proc->runs = 0;
        proc->kstack = 0;
        proc->need_resched = 0;
        proc->parent = NULL;
        proc->mm = NULL;
        memset(&(proc->context), 0, sizeof(struct context));
        proc->tf = NULL;
        proc->cr3 = boot_cr3;
        proc->flags = 0;
        memset(proc->name, 0, PROC_NAME_LEN);
        proc->wait_state = 0;
        proc->cptr = proc->optr = proc->yptr = NULL;
        
        /* <-- 以下都是lab6新增的部分 --> */
        
        proc->rq = NULL; /* 把运行队列置空 */
        list_init(&(proc->run_link)); /* 初始化运行队列中链接的条目 */
        proc->time_slice = 0; /* 初始化占用CPU的时间片 */
        proc->lab6_run_pool.left = proc->lab6_run_pool.right = proc->lab6_run_pool.parent = NULL;
        proc->lab6_stride = 0;
        proc->lab6_priority = 0;
    }
    return proc;
}

另外在 trap_dispatch 函数中填入 “中断请求-计时器中断” 对应的部分：

  • 在 lab6 中，时钟中断的处理逻辑中主动调用了调度器的 proc_tick 函数，使得调度器能感知到时钟中断的产生，并调整调度相关的数据结构
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
static void
trap_dispatch(struct trapframe *tf) {
    /* 根据trapframe中断帧中的标志位,来执行具体的中断服务历程 */
    char c;
    int ret=0;
    switch (tf->tf_trapno) {
    case T_PGFLT: /* 页错误异常(page fault) */
        if ((ret = pgfault_handler(tf)) != 0) {
            print_trapframe(tf);
            /* lab5新增:与进程相关的if判断语句 */
            if (current == NULL) {
                panic("handle pgfault failed. ret=%d\n", ret);
            }
            else {
                if (trap_in_kernel(tf)) {
                    panic("handle pgfault failed in kernel mode. ret=%d\n", ret);
                }
                cprintf("killed by kernel.\n");
                panic("handle user mode pgfault failed. ret=%d\n", ret); 
                do_exit(-E_KILLED);
            }
        }
        break;
    case T_SYSCALL: /* 系统调用(syscall) */
        syscall();
        break;
            
            /*  <---- start ---->  */
    case IRQ_OFFSET + IRQ_TIMER:
#if 0
    LAB3 : If some page replacement algorithm(such as CLOCK PRA) need tick to change the priority of pages, 
    then you can add code here. 
#endif
        ticks ++;
        assert(current != NULL);
        sched_class_proc_tick(current); /* lab6新添:使得调度器能感知到时钟中断的产生,并调整调度相关的数据结构 */
        break;   
            /*  <---- end ---->  */
            
    case IRQ_OFFSET + IRQ_COM1: /* 中断请求-串口中断 */
        c = cons_getc();
        cprintf("serial [%03d] %c\n", c, c);
        break;
    case IRQ_OFFSET + IRQ_KBD: /* 中断请求-键盘中断 */
        c = cons_getc();
        cprintf("kbd [%03d] %c\n", c, c);
        break;
    case T_SWITCH_TOU: /* 中断请求-内核到用户空间触发的中断 */
    case T_SWITCH_TOK: /* 中断请求-用户空间到内核触发的中断 */
        panic("T_SWITCH_** ??\n");
        break;
    case IRQ_OFFSET + IRQ_IDE1: /* 中断请求-IDE通道1中断 */
    case IRQ_OFFSET + IRQ_IDE2: /* 中断请求-IDE通道2中断 */
            /* 本实验不涉及这一部分 */
        break;
    default:
            /* lab5改动:完善了报错处理 */
        print_trapframe(tf); /* 打印trapframe结构体(中断帧,用于存储执行中断的信息) */
        if (current != NULL) {
            cprintf("unhandled trap.\n");
            do_exit(-E_KILLED);
        }
        panic("unexpected trap in kernel.\n");
    }
}

void
sched_class_proc_tick(struct proc_struct *proc) {
    if (proc != idleproc) {
        sched_class->proc_tick(rq, proc); /* 处理时钟中断,更新对应的调度参数 */
    }
    else {
        proc->need_resched = 1; /* idleproc处理时钟中断:需要进行调度 */
    }
}

练习1-使用 Round Robin 调度算法

  • 理解并分析 sched_class（调度类，调度器框架）中各个函数指针的用法，并结合 Round Robin 调度算法描 ucore 的调度执行过程
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
static struct sched_class *sched_class;

struct sched_class {
    const char *name; /* 零,该调度类的名称 */
    
    void (*init)(struct run_queue *rq); /* 一,初始化运行队列 */
    
    void (*enqueue)(struct run_queue *rq, struct proc_struct *proc); /* 二,将proc(进程)放入runqueue(运行队列),必须使用"rq_lock"调用此函数 */
    
    void (*dequeue)(struct run_queue *rq, struct proc_struct *proc); /* 三,将proc(进程)移出runqueue(运行队列),必须使用"rq_lock"调用此函数 */
    
    struct proc_struct *(*pick_next)(struct run_queue *rq); /* 四,选择下一个可运行任务 */
    
    void (*proc_tick)(struct run_queue *rq, struct proc_struct *proc); /* 五,以减小当前运行进程的time-tick(剩余时间片) */
    
};

struct sched_class default_sched_class = {
    /* 六,定义一个c语言类的实现,提供调度算法的切换接口(不属于调度类但后续会遇到) */
    .name = "RR_scheduler",
    .init = RR_init,
    .enqueue = RR_enqueue,
    .dequeue = RR_dequeue,
    .pick_next = RR_pick_next,
    .proc_tick = RR_proc_tick,
};
  • RR调度算法的调度思想是让所有 runnable 态的进程分时轮流使用 CPU 时间
  • RR调度器维护当前 runnable 进程的有序运行队列
  • 当前进程的时间片用完之后，调度器将当前进程放置到运行队列的尾部，再从其头部取出进程进行调度

零，const char *name：指向了当前调度算法的名称字符串

一，void (*init)(struct run_queue *rq)：

1
2
3
4
5
static void
RR_init(struct run_queue *rq) {
    list_init(&(rq->run_list)); /* 置空链表 */
    rq->proc_num = 0; /* 进程总数变为'0' */
}
  • 用于初始化传入的就绪队列，RR算法中只初始化了对应 run_queue 的 run_list 成员

二，void (*enqueue)(struct run_queue *rq, struct proc_struct *proc)：

1
2
3
4
5
6
7
8
9
10
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 ++; /* 运行队列中的进程数增加 */
}
  • 用于将某个进程添加进传入的队列中
  • RR算法除了将进程添加进队列中，还重置了相关的时间片

三，void (*dequeue)(struct run_queue *rq, struct proc_struct *proc)：

1
2
3
4
5
6
7
8
9
10
11
12
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 --; /* 运行队列中的进程数减少 */
}

static inline void
list_del_init(list_entry_t *listelm) {
    list_del(listelm);
    list_init(listelm);
}
  • 用于将某个进程从传入的队列中移除

四，struct proc_struct *(*pick_next)(struct run_queue *rq)：

1
2
3
4
5
6
7
8
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;
}
  • 用于在传入的运行队列中选择出一个最适合运行的进程（选择进程但不将从队列中移除）
  • 在RR算法采用 [首次适配] ，每次都只选择队列最前面那个进程

五，void (*proc_tick)(struct run_queue *rq, struct proc_struct *proc)：

1
2
3
4
5
6
7
8
9
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; /* 如果用完时间片,那么就使该进程变成可调度状态,等待再次调度 */
    }
}
  • 该函数会在时间中断处理例程中被调用（ sched_class_proc_tick(current) 中的 sched_class->proc_tick(rq, proc) ），以减小当前运行进程的剩余时间片，若时间片耗尽，则设置当前进程的 need_resched 为 1

结合 Round Robin 调度算法描 uCore 的调度执行过程：

  • 首先，uCore调用 sched_init 函数用于初始化相关的就绪队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void
sched_init(void) {
    list_init(&timer_list); /* 这个timer_list在之后的实验中会出现 */

    sched_class = &default_sched_class; /* 提供调度算法的切换接口 */

    /* 这里让我联想到了面向对象中的类与实例:
    sched_class其实就是一组接口,有点类似于一组函数指针
    它起到了和“实例化”差不多的效果,可以任意调用该类中的函数
    没准这就是面向对象的雏形,只不过面向对象更强大,采用了更加高级的数据抽象的形式
    */
    
    rq = &__rq;
    rq->max_time_slice = MAX_TIME_SLICE;
    sched_class->init(rq); /* 调用RR_init初始化rq运行列表 */

    cprintf("sched class: %s\n", sched_class->name);
}
  • 之后在 proc_init 函数中，建立第一个内核进程，并将其添加至就绪队列中
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
28
29
30
31
32
33
34
void
proc_init(void) {
    int i;

    list_init(&proc_list);
    for (i = 0; i < HASH_LIST_SIZE; i ++) {
        list_init(hash_list + i);
    }

    if ((idleproc = alloc_proc()) == NULL) {
        /* 分配一个物理页,作为proc_struct结构体 */
        panic("cannot alloc idleproc.\n");
    }

    idleproc->pid = 0; /* 将空闲进程作为第一个进程,pid为0 */
    idleproc->state = PROC_RUNNABLE; /* 设置该空闲进程始终可运行 */
    idleproc->kstack = (uintptr_t)bootstack; /* 设置空闲进程的内核栈 */
    idleproc->need_resched = 1; /* 设置该空闲进程为可调度 */
    set_proc_name(idleproc, "idle"); /* 设置该进程的name为"idle" */
    nr_process ++; /* 将全局线程的数目加1 */

    current = idleproc; /* 设置当前进程为idleproc */

    int pid = kernel_thread(init_main, NULL, 0); /* 先设置trapframe,最后调用do_fork(详情请参考起前面的实验) */
    if (pid <= 0) { /* 内核进程创建失败 */
        panic("create init_main failed.\n");
    }

    initproc = find_proc(pid); /* 通过pid查找proc_struct,并赋值给initproc */
    set_proc_name(initproc, "init"); /* 设置该进程的name为"init" */

    assert(idleproc != NULL && idleproc->pid == 0);
    assert(initproc != NULL && initproc->pid == 1);
}
  • 当所有的初始化完成后，uCore执行 cpu_idle 函数，并在其内部循环执行 schedule 函数
1
2
3
4
5
6
7
8
9
10
struct proc_struct *current = NULL; /* 指向当前的进程 */ 

void
cpu_idle(void) {
    while (1) {
        if (current->need_resched) { /* 是否需要被调度 */
            schedule(); /* 准备开始调度进程 */
        }
    }
}
  • 调用 sched_class_enqueue 将当前进程添加进就绪队列中（因为当前进程要被切换出CPU了）
  • 然后，调用 sched_class_pick_next 获取就绪队列中可被轮换至CPU的进程
  • 如果存在可用的进程，则调用 sched_class_dequeue 函数，将该进程移出就绪队列，并在之后执行 proc_run 函数进行进程上下文切换
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
void
schedule(void) {
    bool intr_flag;
    struct proc_struct *next;
    local_intr_save(intr_flag);
    {
        current->need_resched = 0;
        /* 相比与上一个实验要朴实得多,可能做了优化吧 */
        if (current->state == PROC_RUNNABLE) {
            sched_class_enqueue(current); /* 将current添加进就绪队列中 */
        }
        if ((next = sched_class_pick_next()) != NULL) { /* 获取就绪队列中可被轮换至CPU的进程 */
            sched_class_dequeue(next); /* 如果存在可用的进程,将该进程移出就绪队列 */
        }
        if (next == NULL) {
            next = idleproc; /* 判断将要被调度的进程为空闲进程 */
        }
        next->runs ++; /* 目标进程被调度的次数增加 */
        if (next != current) {
            /* 如果调度进程不是当前进程,则运行proc_run,否则会重新进入空闲进程(循环) */
            proc_run(next); /* 执行进程调度操作(上下文切换) */
        }
    }
    local_intr_restore(intr_flag); /* 解除中断的阻塞 */
}
  • sched_class_enqueue 的具体实现：
1
2
3
4
5
6
static inline void
sched_class_enqueue(struct proc_struct *proc) {
    if (proc != idleproc) {
        sched_class->enqueue(rq, proc); /* RR_enqueue的外包装 */
    }
}
  • sched_class_pick_next
1
2
3
4
static inline struct proc_struct *
sched_class_pick_next(void) {
    return sched_class->pick_next(rq); /* RR_pick_next的外包装 */
}
  • sched_class_dequeue
1
2
3
4
static inline void
sched_class_dequeue(struct proc_struct *proc) {
    sched_class->dequeue(rq, proc); /* RR_dequeue的外包装 */
}

设计多级反馈队列调度算法

我自己的理解：

  • 其实多级反馈队列就是把进程进行了优先级分级，在每一级中的时间片长度不一样（第一级的优先度最高，时间片最短，被 CPU 调度的机会更多）
  • 在同一个优先级的队列内使用时间片轮转算法
  • CPU 如果一次没有执行完毕目标进程，那么该进程就会降级（降到下一级）
  • 在最后一级中，如果一次还是没有执行完毕目标进程，那么下次就会在这一级中实现 RR 时间片轮转算法
  • PS：至于为什么要这样搞，这就是数学家用公式算出来的，有关数学公式的理论本人一概不会

具体的过程我就随便抄了一个：（其实我也写了一个，就不献丑了）

  • 在 proc_struct 中添加总共N个多级反馈队列的入口，每个队列都有着各自的优先级，编号越大的队列优先级约低，并且优先级越低的队列上时间片的长度越大，为其上一个优先级队列的两倍；并且在PCB中记录当前进程所处的队列的优先级
  • 处理调度算法初始化的时候需要同时对N个队列进行初始化
  • 在处理将进程加入到就绪进程集合的时候，观察这个进程的时间片有没有使用完，如果使用完了，就将所在队列的优先级调低，加入到优先级低1级的队列中去，如果没有使用完时间片，则加入到当前优先级的队列中去
  • 在同一个优先级的队列内使用时间片轮转算法
  • 在选择下一个执行的进程的时候，有限考虑高优先级的队列中是否存在任务，如果不存在才转而寻找较低优先级的队列（有可能导致饥饿）
  • 从就绪进程集合中删除某一个进程就只需要在对应队列中删除即可
  • 处理时间中断的函数不需要改变

练习2-实现 Stride Scheduling 调度算法

uCore 的 Round-Robin 算法可以保证每个进程得到的 CPU 资源是相等的，但我们希望调度器能够更加智能的为每个进程分配合理的 CPU 资源，让 每个进程得到的时间资源与它们的优先级成正比关系 ，而 Stride Scheduling 调度算法就是这样的一种典型而简单的算法

其中，该算法的有如下几个特点：

  • 可控性：可以证明 Stride Scheduling 对进程的调度次数正比于其优先级
  • 确定性：在不考虑计时器事件的情况下，整个调度机制都是可预知和重现的

算法简析：

在实验中使用的 Stride Scheduling 算法是结合时间片的一种优先级调度策略，每一个时间片结束时，选择就绪状态的进程中 Pass 值最小的进程分配一个时间片，在一个时间段中进程所获得的时间片数量和进程的优先级大致成正比

该算法的基本思想如下：

  • 为每个 runnable 的进程设置一个当前状态 stride，表示该进程当前的调度权，另外定义其对应的 pass 值，表示对应进程在调度后 stride 需要进行的累加值
  • 每次需要调度时，从当前 runnable 态的进程中选择 stride 最小的进程调度
  • 对于获得调度的进程P，将对应的 stride 加上其对应的步长 pass（只与进程的优先权有关系）
  • 在一段固定的时间之后，重新调度当前 stride 最小的进程（返回步骤二）

总之：

其实就是模仿 Round Robin 调度算法来重新写一个 Stride Scheduling，具体的优化策略需要结合一些数学理论，所以我直接抄答案了，并在答案中理解该算法

下面便是具体的实现过程：（有和 Round Robin 的对比）

一，stride_init：进行初始化操作

1
2
3
4
5
6
static void
stride_init(struct run_queue *rq) {
     list_init(&(rq->run_list)); /* 置空链表 */
     rq->lab6_run_pool = NULL; /* 运行池中的条目初始化为空 */
     rq->proc_num = 0; /* 进程总数变为'0' */
}
1
2
3
4
5
static void /* 对比Round Robin */
RR_init(struct run_queue *rq) {
    list_init(&(rq->run_list)); /* 置空链表 */
    rq->proc_num = 0; /* 进程总数变为'0' */
}

二，stride_enqueue：用于将某个进程添加进传入的队列中

1
2
3
4
5
6
7
8
9
10
static void
stride_enqueue(struct run_queue *rq, struct proc_struct *proc) {
     rq->lab6_run_pool =
          skew_heap_insert(rq->lab6_run_pool, &(proc->lab6_run_pool), proc_stride_comp_f); 
     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 ++; /* 运行队列中的进程数增加 */
}
1
2
3
4
5
6
7
8
9
10
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 ++; /* 运行队列中的进程数增加 */
}

三，stride_dequeue：用于将某个进程从传入的队列中移除

1
2
3
4
5
6
static void
stride_dequeue(struct run_queue *rq, struct proc_struct *proc) {
     rq->lab6_run_pool =
          skew_heap_remove(rq->lab6_run_pool, &(proc->lab6_run_pool), proc_stride_comp_f);
     rq->proc_num --; /* 运行队列中的进程数减少 */
}
1
2
3
4
5
6
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 --; /* 运行队列中的进程数减少 */
}

四，stride_pick_next：涉及到了选取最小 Stride 值的进程，以及 stride 值的更新

1
2
3
4
5
6
7
8
9
10
static struct proc_struct *
stride_pick_next(struct run_queue *rq) {
     if (rq->lab6_run_pool == NULL) 
         return NULL;
     struct proc_struct *p = le2proc(rq->lab6_run_pool, lab6_run_pool);
     if (p->lab6_priority == 0)
          p->lab6_stride += BIG_STRIDE;
     else p->lab6_stride += BIG_STRIDE / p->lab6_priority;
     return p;
}
1
2
3
4
5
6
7
8
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;
}

五，stride_proc_tick：和 RR_proc_tick 一致

1
2
3
4
5
6
7
8
9
static void
stride_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; /* 如果用完时间片,那么就使该进程变成可调度状态,等待再次调度 */
    }
}
1
2
3
4
5
6
7
8
9
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; /* 如果用完时间片,那么就使该进程变成可调度状态,等待再次调度 */
    }
}