分析精简内核mykernel中进程调度的工作过程

赵建清+原创作品转载请注明出处+《Linux内核分析》MOOC课程

mykernel是中国科学技术大学孟宁老师基于linux系统开发的一个精简操作系统内核，mykernel使用均匀时间片轮转的调度策略。本文以mykernel为例，分析该调度策略的工作机制以及如何进行上下文切换。具体实验步骤及全部源代码请参考孟宁老师的github：

进程是多道程序设计操作系统中的基本概念，通常认为进程是程序执行的一个实例。首先说明mykernel中描述进程的数据结构，然后具体分析在mykernel中如何进行上下文切换。

mykernel中进程控制块

1.  /*
2. * linux/mykernel/mypcb.h
3. *
4. * Kernel internal PCB types
5. *
6. * Copyright (C) 2013 Mengning
7. *
8. */
10. #define MAX_TASK_NUM 4
11. #define KERNEL_STACK_SIZE 1024*8
13. /* CPU-specific state of this task */
14. struct Thread {
15. unsigned long ip;
16. unsigned long sp;
17. };
19. typedef struct PCB{
20. int pid;
21. volatile long state; /* -1 unrunnable, 0 runnable, >0 stopped */
22. char stack[KERNEL_STACK_SIZE];
23. /* CPU-specific state of this task */
24. struct Thread thread;
25. unsigned long task_entry;
26. struct PCB *next;
27. }tPCB;
28. void my_schedule(void);

struct PCB是描述进程控制信息的结构。其中预先分配的stack数组用做进程的堆栈，大小为1Kb； thread.ip和thread.sp分别用于保存指令指针寄存器EIP和进程运行过程中栈指针寄存器ESP，next指针用于进程链表中的后继进程的PCB.

mykernel的调度子系统

struct PCB定义了进程控制块，用于保存进程的上下文信息以及分配堆栈。mykernel把所有进程的PCB组织成一个循环链表，使用时间片轮转调度策略依次选中进程运行。调度子系统中各组件的关系如下：

下面分析时间片轮转调度策略的具体实现，先上源代码：

1. /*
2. * linux/mykernel/mymain.c
3. *
4. * Kernel internal my_start_kernel
5. *
6. * Copyright (C) 2013 Mengning
7. *
8. */
9. #include
10. #include
11. #include
12. #include
13. #include
16. #include “mypcb.h”
18. tPCB task[MAX_TASK_NUM];
19. tPCB * my_current_task = NULL;
20. volatile int my_need_sched = 0;
22. void my_process(void);
25. void __init my_start_kernel(void)
26. {
27. int pid = 0;
28. int i;
29. /* Initialize process 0*/
30. task[pid].pid = pid;
31. task[pid].state = 0;/* -1 unrunnable, 0 runnable, >0 stopped */
32. task[pid].task_entry = task[pid].thread.ip = (unsigned long)my_process;
33. task[pid].thread.sp = (unsigned long)&task[pid].stack[KERNEL_STACK_SIZE-1];
34. task[pid].next = &task[pid];
35. /*fork more process */
36. for(i=1;i
37. {
38. memcpy(&task[i],&task[0],sizeof(tPCB));
39. task[i].pid = i;
40. task[i].state = -1;
41. task[i].thread.sp = (unsigned long)&task[i].stack[KERNEL_STACK_SIZE-1];
42. task[i].next = task[i-1].next;
43. task[i-1].next = &task[i];
44. }
45. /* start process 0 by task[0] */
46. pid = 0;
47. my_current_task = &task[pid];
48. asm volatile(
49. “movl %1,%%esp\n\t” /* set task[pid].thread.sp to esp */
50. “pushl %1\n\t” /* push ebp */
51. “pushl %0\n\t” /* push task[pid].thread.ip */
52. “ret\n\t” /* pop task[pid].thread.ip to eip */
53. “popl %%ebp\n\t”
54. :
55. : “c” (task[pid].thread.ip),”d” (task[pid].thread.sp) /* input c or d mean %ecx/%edx*/
56. );
57. }
58. void my_process(void)
59. {
60. int i = 0;
61. while(1)
62. {
63. i++;
64. if(i%10000000 == 0)
65. {
66. printk(KERN_NOTICE “this is process %d -\n”,my_current_task->pid);
67. if(my_need_sched == 1)
68. {
69. my_need_sched = 0;
70. my_schedule();
71. }
72. printk(KERN_NOTICE “this is process %d +\n”,my_current_task->pid);
73. }
74. }
75. }

系统使用函数my_start_kernel初始化PCB list，依次设置每个进程pid、状态、堆栈空间、下一条指令运行的地址以及后继PCB的指针，最后通过内嵌汇编代码设置系统堆栈，开始运行pid为0的进程。第30行到第34行设置pid为0的进程PCB结构。

1. 第31行将进程设置为可运行状态；
2. 第32行设置下一条指令运行的地址指向函数my_process；
3. 第33行设置进程堆栈地址空间，指向预先分配好的stack数组最后一个字节，然后设置后继PCB为其自身。此时PCB list已经是个循环链表，不过只有1个结点；
4. 第36行到第44行依次设置剩下的MAX_TASK_NUM-1个进程的PCB结构，完成设置一个PCB后将该PCB插入PCB list中，增加1个结点，保持循环链表的结构不变。
5. 第38行复制pid为0进程的PCB到当前进程PCB，效率并不高，因为每个进程PCB中只有task_entry和thread.ip是相同的，即下一条指令执行地址都函数从my_process开始，其他字段均需重新设置。
6. 第46行到第56行开始设置系统堆栈空间。

先简要介绍C语言中的嵌入式汇编，详细说明请参考gcc手册。嵌入汇编的基本格式为：

1. asm(“汇编语句”
2. ：输出寄存器
3. ：输入寄存器
4. ：会被修改的寄存器);

嵌入式汇编程序规定把输出和输入寄存器统一按顺序编号，分别记为%0、%1、… %9。输出和输入寄存器列表中多个寄存器用逗号分隔，每个寄存器项有引号和括号组成，引号内的字母表示所使用的寄存器代码，括号内表示C语言中的变量。

1. 第55行表示输入寄存器，分别表示把task[0].thread.ip的值复制到寄存器ECX以及将task[0].thread.sp的值复制到寄存器EDX中，这样ECX中保存了pid为0的进程下一条指令执行的地址，EDX中保存了该进程堆栈空间的高地址。
2. 第49行将寄存器EDX的值复制到堆栈指针寄存器ESP，此时系统堆栈指针指向了task[0].stack[KERNEL_STACK_SIZE-1]，指向stack数组最后一个字节的原因是堆栈的增长方向是从高地址到低地址;
3. 第50行将堆栈基址EBP的值压入堆栈，EBP压入堆栈前的值等于堆栈指针ESP的值;
4. 第51行将下一条指令执行的地址压入堆栈;  第52行从堆栈中弹出下一条指令执行地址到指令指针寄存器EIP；
5. 第52行执行后因为设置EIP的值为函数my_process的地址，因此开始调用函数my_process；
6. 第53行指令不会被调用。

下图分别表示第50行到第52行执行后的堆栈内容：

接下来分析函数my_process的执行过程。函数my_process有个无限循环，每执行1千万次判断my_need_sched是否等于1，如果my_need_sched等于1说明当前运行进程已经耗尽分配的时间片，需要挂起当前进程，开始运行其后继进程。函数my_schedule负责上下文切换，定义在myinterrupt.c中。

执行进程切换

1. /*
2. * linux/mykernel/myinterrupt.c
3. *
4. * Kernel internal my_timer_handler
5. *
6. * Copyright (C) 2013 Mengning
7. *
8. */
9. #include
10. #include
11. #include
12. #include
13. #include
15. #include “mypcb.h”
17. extern tPCB task[MAX_TASK_NUM];
18. extern tPCB * my_current_task;
19. extern volatile int my_need_sched;
20. volatile int time_count = 0;
22. /*
23. * Called by timer interrupt.
24. * it runs in the name of current running process,
25. * so it use kernel stack of current running process
26. */
27. void my_timer_handler(void)
28. {
29. #if 1
30. if(time_count%1000 == 0 && my_need_sched != 1)
31. {
32. printk(KERN_NOTICE “>>>my_timer_handler here<<<\n”);
33. my_need_sched = 1;
34. }
35. time_count ++ ;
36. #endif
37. return;
38. }
40. void my_schedule(void)
41. {
42. tPCB * next;
43. tPCB * prev;
45. if(my_current_task == NULL
46. || my_current_task->next == NULL)
47. {
48. return;
49. }
50. printk(KERN_NOTICE “>>>my_schedule<<<\n”);
51. /* schedule */
52. next = my_current_task->next;
53. prev = my_current_task;
54. if(next->state == 0)/* -1 unrunnable, 0 runnable, >0 stopped */
55. {
56. /* switch to next process */
57. asm volatile(
58. “pushl %%ebp\n\t” /* save ebp */
59. “movl %%esp,%0\n\t” /* save esp */
60. “movl %2,%%esp\n\t” /* restore esp */
61. “movl $1f,%1\n\t” /* save eip */
62. “pushl %3\n\t”
63. “ret\n\t” /* restore eip */
64. “1:\t” /* next process start here */
65. “popl %%ebp\n\t”
66. : “=m” (prev->thread.sp),”=m” (prev->thread.ip)
67. : “m” (next->thread.sp),”m” (next->thread.ip)
68. );
69. my_current_task = next;
70. printk(KERN_NOTICE “>>>switch %d to %d<<<\n”,prev->pid,next->pid);
71. }
72. else
73. {
74. next->state = 0;
75. my_current_task = next;
76. printk(KERN_NOTICE “>>>switch %d to %d<<<\n”,prev->pid,next->pid);
77. /* switch to new process */
78. asm volatile(
79. “pushl %%ebp\n\t” /* save ebp */
80. “movl %%esp,%0\n\t” /* save esp */
81. “movl %2,%%esp\n\t” /* restore esp */
82. “movl %2,%%ebp\n\t” /* restore ebp */
83. “movl $1f,%1\n\t” /* save eip */
84. “pushl %3\n\t”
85. “ret\n\t” /* restore eip */
86. : “=m” (prev->thread.sp),”=m” (prev->thread.ip)
87. : “m” (next->thread.sp),”m” (next->thread.ip)
88. );
89. }
90. return;
91. }

进程切换发生在函数my_schedule中。在初始化PCB链表的时，除了pid为0的其他进程PCB中state变量都设置为-1，表示未就绪状态，因此pid大于0的进程第一次被选中运行时，程序逻辑走的是else分支即第74行到第88行；第一次运行之后进程的PCB中state变量被设置为0，表示可运行状态，再次进入函数my_schedule中，程序逻辑走的是if分支即第56行到第70行。

初次切换

进程被第一次选中运行时，首先将PCB中state变量设置为0。

1. 第79行将前驱进程prev的ebp压入其堆栈；
2. 第80行将prev的esp保存到prev->thread.sp；
3. 第81行将next->thread.sp的值复制到堆栈指针寄存器ESP；
4. 第82行将next->thread.sp的值复制到基址EBP，此时建立了当前进程next的栈帧，EBP和ESP指向相同的地址即next->stack[KERNEL_STACK_SIZE-1]；
5. 第83行将标号“1:”的代码在内存中存储的地址复制到prev->thread.ip，当进程被再次选中运行时将该值加载到指令指针寄存器EIP，然后从标号为1的地方即第64行开始运行；
6. 第84行将next->thread.ip的值即函数my_process的地址压入next的堆栈；
7. 第85行设置指令指针寄存器EIP的值，因为用户无法直接设置EIP，先将需要执行的指令地址压入堆栈，然后使用ret指令从堆栈中弹出该地址并间接设置EIP，接着系统开始调用my_process；
8. 第90行从函数my_schedule返回到函数my_process继续执行。

第74行到第88行执行以后prev进程和next进程的stack数组内容以及EIP寄存器内容如下图：

mykernel中pid为0的进程时间片用尽后切换到pid为1的进程的相关日志：

非初次切换

如果进程被已经运行过，再次被调度系统选中运行时PCB中state变量已经为0，因此调用函数my_schedule时走的是if分支即第57行到第70行。

1. 第58行将前驱进程prev的ebp压入其堆栈；
2. 第59行将prev的esp保存到prev->thread.sp；
3. 第60行将next->thread.sp的值复制到堆栈指针寄存器ESP；
4. 第61行将标号“1:”的代码在内存中存储的地址复制到prev->thread.ip，当进程被再次选中运行时将该值加载到指令指针寄存器EIP，然后从标号为1的地方即第64行开始运行；
5. 第62行将原先保存在prev->thread.ip中的下一条指令地址复制到指令指针寄存器EIP，由初次切换中分析可知，prev->thread.ip中保存的是标号为“1:”的指令地址；
6. 第63行使用ret指令从堆栈中恢复EIP的值，由于上次该进程挂起时保存的指令执行地址是标号为”1:”的语句，因此执行ret指令后看似要调转到别的地方，实际上执行的是第64行的指令；
7. 第64行为标号无实际操作；
8. 第65行从堆栈从弹出上次保存的堆栈基址到EBP中；
9. 第69行将my_current_task设置为next，将next设置为当前运行进程；
10. 第70行是个输出语句，供用户观察；
11. 第90行从函数my_schedule返回到函数my_process继续执行。

第58行到第63行指令执行以后prev进程和next进程的stack数组内容以及EIP寄存器内容如下图：

时钟中断

函数my_timer_handler是发生时钟中断时的中断处理程序，每发生1000次时钟中断就会将my_need_sched的值设为1，表示当前运行的进程已经耗尽时间片将被系统挂起，然后开始运行在PCB循环链表中的后继进程。

时钟中断引起进程切换的相关日志：

总结

本文详细分析了精简内核mykernel的进程调度过程以及进程切换过程中上下文的保存和恢复，从而对linux系统的进程调度建立了比较直观的认识。mykernel的核心代码虽然只有200多行，但是清晰地示范了中断处理和上下文切换在现代多道程序设计计算机系统中的重要作用。