说明
欧长坤
原创作品转载请注明出处
《Linux内核分析》MOOC课程http://mooc.study.163.com/course/USTC-1000029000
这学期学校恰好有操作系统的课程，上个学习就开始寻思研究研究Linux内核代码，恰好MOOC有这个课程，遂选了此课。
一、准备工作
首先，我们需要先在自己的系统上搭建实验环境，老师给出了Linux内核版本为3.9.4的加载mykernel的方法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
sudo apt-get install qemu # 安装 QEMU
# 这里对QEMU进行一个简单介绍，QEMU是一个Open Source Processor Emulator
# 它能有效的模拟 x86 架构等个人电脑，有两种运行模式：
# User mode模拟模式，QEMU 能启动那些为不同中央处理器编译的Linux程序。而Wine及 Dosemu是其主要目标。
# System mode模拟模式，QEMU能模拟整个电脑系统，包括中央处理器及其他周边设备。
# 一句话来说就是QEMU可以模拟运行我们编译的linux内核镜像
sudo ln -s /usr/bin/qemu-system-i386 /usr/bin/qemu # 为QEMU创建一个链接能够在系统级上直接执行而不需要通过目录来执行
wget https://www.kernel.org/pub/linux/kernel/v3.x/linux-3.9.4.tar.xz # 下载 Linux3.9.4 内核
wget https://raw.github.com/mengning/mykernel/master/mykernel_for_linux3.9.4sc.patch # 下载 mykernel_for_linux3.9.4sc.patch 补丁
xz -d linux-3.9.4.tar.xz # 解开Linux内核源码包
tar -xvf linux-3.9.4.tar # 同上
cd linux-3.9.4 # 进入
patch -p1 < ../mykernel_for_linux3.9.4sc.patch # 给Linux内核添加mykernel补丁，但是这个补丁做了什么事情，我们等一下来说。
make allnoconfig # 接下来这两步就是对Linux内核的源码进行编译了
make
qemu -kernel arch/x86/boot/bzImage #从qemu窗口中可以看到my_start_kernel在执行，同时my_timer_handler时钟中断处理程序周期性执行。
|
从上面的准备过程我们可以看出，准备过程为了能够运行我们自己的内核做了三件事情：
1、安装QEMU，为我们运行内核提供模拟环境；
2、下载Linux内核源码，为我们编译自己的内核提供源码基础；
3、打补丁。
老师讲课讲到这里，让我非常疑惑，这个补丁究竟干了什么事情，之后的编译指令不再编译其他架构的内核代码，而是直接编译mykernel的内核代码。
我们可以使用vim来查看一下.patch文件到底做了什么事情，进去之后我们可以看到：
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
|
diff -Naur linux-3.9.4/arch/x86/kernel/time.c linux-3.9.4.new/arch/x86/kernel/time.c
---
linux-3.9.4/arch/x86/kernel/time.c 2013-05-24 11:45:59.000000000 -0700
+++ linux-3.9.4.new/arch/x86/kernel/time.c 2013-06-25 21:39:34.641299852 -0700
@@ -13,6 +13,7 @@
#include <linux/interrupt.h>
#include <linux/i8253.h>
#include <linux/time.h>
+#include <linux/timer.h>
#include <linux/export.h>
#include <asm/vsyscall.h>
@@ -57,6 +58,7 @@
static irqreturn_t timer_interrupt(int irq, void *dev_id)
{
global_clock_event->event_handler(global_clock_event);
+ my_timer_handler();
return IRQ_HANDLED;
}
@@ -68,6 +70,7 @@
void __init setup_default_timer_irq(void)
{
+ printk(KERN_NOTICE "timer interrupt setup\n");
setup_irq(0, &irq0);
}
diff -Naur linux-3.9.4/include/linux/start_kernel.h linux-3.9.4.new/include/linux/start_kernel.h
---
linux-3.9.4/include/linux/start_kernel.h 2013-05-24 11:45:59.000000000 -0700
+++ linux-3.9.4.new/include/linux/start_kernel.h 2013-06-25 19:18:58.396722448 -0700
@@ -8,5 +8,6 @@
up something else. */
extern asmlinkage void __init start_kernel(void);
+extern void __init my_start_kernel(void);
…………
…………
…………
|
可以知道，其实.patch其实是一个用于描述内核文件变化的文件，也就是我们常说的补丁文件，它修改了需要编译的内核文件的部分代码，达到DIY的效果，那么老师的这份补丁做了哪些事情？
通过文件我们可以看到：
- 首先，修改了
arch/x86/kernel/time.c 文件，新包含 timer.h，在timer_interrupt()函数返回之前，添加了一个 my_timer_handler() 函数，在setup_default_timer_irg()执行了一段printk(KERN_NOTICE "timer interrupt setup\n");
- 其次，修改了
include/linux/start_kernel.h，在里面添加了一个外部引用的函数 my_start_kernel();
- 还修改了
include/linux/timer.c，在里面添加了一个外部引用的函数my_timer_handler();
- 然后，修改了
init/main.c下面的start_kernel()的最后ftrace_init()下一行添加了一个函数my_start_kernel();
- 然后的一些修改就是让
makefile文件多编译mykernel文件了，这里就不继续赘述了。
现在我们似乎明白了老师让我们自行编写内核的方式，那就是Linux内核的入口函数是start_kernel()，位于init/main.c下，在这个文件中包含了start_kernel.h，而我们在start_kernel.h说明了一个外部存在的函数my_start_kernel()，这就为我们能够在内核启动阶段，执行我们需要的代码（自己编写的内核代码）提供了支持。
说到这我们似乎有点跑偏了，上面只是对为什么补丁会起作用做出的一个简单分析，下面我们回到对我们自己编写的精简内核代码的分析上来。
二、实验过程
我们打好老师的补丁后，我们可以看到，在mykernel下方并不是我们最终的代码，老师原本的目的是要我们自行写出能够进行时间片轮转调度的内核代码，降低了难度，老师在视频里演示了全部的代码过程。
我们需要修改在linux3.9.4/mykernel下的三个文件，分别是 mypcb.h, mymain.c myinterrupt.c。
在这三个文件里面mypcb.h定义了一个名为PCB的结构体，名为Thread的结构体，在mymain.c中包含了对my_start_kernel()的实现，在myinterrupt.c中包含了对my_timer_handler()的实现。
所以实际上我们要实现的支持时间片轮转的内核代码逻辑非常简单，因为这三个函数几乎帮我们屏蔽了其他复杂的内核代码，模拟了基于时间片轮转算法的进程切换调度，而且不涉及其他复杂的调度情况：
- my_start_kernel()帮助我们创建进程。
- my_timer_handler()用于记录时间，完成时间片时长的统计。
- my_start_kernel()中创建的0号进程的入口地址是my_process()，这个函数在mymain.c中内部使用。
- 通过到达时间片的轮转时刻，my_process()会调用my_schedule()来保护进程堆栈现场，完成进程间的切换。
整个实验涉及的代码包括：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
//
// mypcb.h
//
#define MAX_TASK_NUM 4
#define KERNEL_STACK_SIZE 1024*8
/* CPU-specific state of this task */
struct Thread {
unsigned long ip;
unsigned long sp;
};
typedef struct PCB{
int pid;
volatile long state; /* -1 unrunnable, 0 runnable, >0 stopped */
char stack[KERNEL_STACK_SIZE];
/* CPU-specific state of this task */
struct Thread thread;
unsigned long task_entry;
struct PCB *next;
}tPCB;
void my_schedule(void);
|
上面是mypcb.h的代码，里面定义个一个Thread的结构体，用于保存进程的状态。
同时还定义了一接PCB进程控制块的结构体，变量pid来保存进程id，state保存进程的基本状态：执行、阻塞和就绪。
stack用来表示PCB管理堆栈的大小。
在每个thread表示PCB当前执行进程。
注意，这里尽管使用的是thread，但是老师解释说这里实际上是进程，而不是线程。
还有一点则是mypcb.h中定义了my_schedule()函数，却没有真正的实现它，反而是放在了myinterrupt.c中来实现。
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
|
//
// mymain.c
//
#include <linux/types.h>
#include <linux/string.h>
#include <linux/ctype.h>
#include <linux/tty.h>
#include <linux/vmalloc.h>
#include "mypcb.h"
tPCB task[MAX_TASK_NUM];
tPCB * my_current_task = NULL;
volatile int my_need_sched = 0;
void my_process(void);
void __init my_start_kernel(void)
{
int pid = 0;
int i;
/* Initialize process 0*/
task[pid].pid = pid;
task[pid].state = 0;/* -1 unrunnable, 0 runnable, >0 stopped */
task[pid].task_entry = task[pid].thread.ip = (unsigned long)my_process;
task[pid].thread.sp = (unsigned long)&task[pid].stack[KERNEL_STACK_SIZE-1];
task[pid].next = &task[pid];
/*fork more process */
for(i=1;i<MAX_TASK_NUM;i++)
{
memcpy(&task[i],&task[0],sizeof(tPCB));
task[i].pid = i;
task[i].state = -1;
task[i].thread.sp = (unsigned long)&task[i].stack[KERNEL_STACK_SIZE-1];
task[i].next = task[i-1].next;
task[i-1].next = &task[i];
}
/* start process 0 by task[0] */
pid = 0;
my_current_task = &task[pid];
asm volatile(
"movl %1,%%esp\n\t" /* set task[pid].thread.sp to esp */
"pushl %1\n\t" /* push ebp */
"pushl %0\n\t" /* push task[pid].thread.ip */
"ret\n\t" /* pop task[pid].thread.ip to eip */
"popl %%ebp\n\t"
:
: "c" (task[pid].thread.ip),"d" (task[pid].thread.sp) /* input c or d mean %ecx/%edx*/
);
}
void my_process(void)
{
int i = 0;
while(1)
{
i++;
if(i%10000000 == 0)
{
printk(KERN_NOTICE "this is process %d -\n",my_current_task->pid);
if(my_need_sched == 1)
{
my_need_sched = 0;
my_schedule();
}
printk(KERN_NOTICE "this is process %d +\n",my_current_task->pid);
}
}
}
|
这里实现内核的启动，通过my_start_kernel()来初始化进程，my_process作为每个进程的入口地址，开始逐个执行。
但是值得注意的是，事实上老师并没有解释清楚，这个my_process的地址传给了PCB中task_entry后为何会自动得以调用，我们在进一步分析中将会说明。
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
76
77
78
79
80
81
82
83
84
85
86
|
//
// myinterrupt.c
//
#include <linux/types.h>
#include <linux/string.h>
#include <linux/ctype.h>
#include <linux/tty.h>
#include <linux/vmalloc.h>
#include "mypcb.h"
extern tPCB task[MAX_TASK_NUM];
extern tPCB * my_current_task;
extern volatile int my_need_sched;
volatile int time_count = 0;
/*
* Called by timer interrupt.
* it runs in the name of current running process,
* so it use kernel stack of current running process
*/
void my_timer_handler(void)
{
#if 1
if(time_count%100 == 0 && my_need_sched != 1)
{
printk(KERN_NOTICE ">>>my_timer_handler here<<<\n");
my_need_sched = 1;
}
time_count ++ ;
#endif
return;
}
void my_schedule(void)
{
tPCB * next;
tPCB * prev;
if(my_current_task == NULL
|| my_current_task->next == NULL)
{
return;
}
printk(KERN_NOTICE ">>>my_schedule<<<\n");
/* schedule */
next = my_current_task->next;
prev = my_current_task;
if(next->state == 0)/* -1 unrunnable, 0 runnable, >0 stopped */
{
/* switch to next process */
asm volatile(
"pushl %%ebp\n\t" /* save ebp */
"movl %%esp,%0\n\t" /* save esp */
"movl %2,%%esp\n\t" /* restore esp */
"movl $1f,%1\n\t" /* save eip */
"pushl %3\n\t"
"ret\n\t" /* restore eip */
"1:\t" /* next process start here */
"popl %%ebp\n\t"
: "=m" (prev->thread.sp),"=m" (prev->thread.ip)
: "m" (next->thread.sp),"m" (next->thread.ip)
);
my_current_task = next;
printk(KERN_NOTICE ">>>switch %d to %d<<<\n",prev->pid,next->pid);
}
else
{
next->state = 0;
my_current_task = next;
printk(KERN_NOTICE ">>>switch %d to %d<<<\n",prev->pid,next->pid);
/* switch to new process */
asm volatile(
"pushl %%ebp\n\t" /* save ebp */
"movl %%esp,%0\n\t" /* save esp */
"movl %2,%%esp\n\t" /* restore esp */
"movl %2,%%ebp\n\t" /* restore ebp */
"movl $1f,%1\n\t" /* save eip */
"pushl %3\n\t"
"ret\n\t" /* restore eip */
: "=m" (prev->thread.sp),"=m" (prev->thread.ip)
: "m" (next->thread.sp),"m" (next->thread.ip)
);
}
return;
}
|
上面的代码就是对时间片轮转的一个调度实现了，通过my_timer_handler()来记录时间，触发调度。通过my_schedule()来完成调度，保护现场。
在完成对上面三个文件代码的修改之后，我们在linux-3.9.4目录下需要重新执行
来编译镜像文件，并使用
1
|
qemu -kernel arch/x86/boot/bzImage
|
重新加载内核文件的镜像，所以我们就可以看到下面的结果啦。
我们来看几张执行的结果图，然后再来进一步分析代码。
三、进一步分析
我们从入口函数my_start_kernel(void)在运行之初的这段代码里：
1
2
3
4
5
6
7
8
|
int pid = 0;
int i;
/* Initialize process 0*/
task[pid].pid = pid;
task[pid].state = 0;/* -1 unrunnable, 0 runnable, >0 stopped */
task[pid].task_entry = task[pid].thread.ip = (unsigned long)my_process;
task[pid].thread.sp = (unsigned long)&task[pid].stack[KERNEL_STACK_SIZE-1];
task[pid].next = &task[pid];
|
完成了对0号进程的一些初始化工作，包括讲task[0]的pid初始化为0，运行状态设置为运行态，零号进程的入口地址被设置为my_process()，从而使得零号进程可以完成对时间片轮转的调度。同时，task[0]的进程属性中，ip和sp分别被设置为了my_process()函数的入口地址和零号进程的对战首地址，这是正确地。因为零号进程的入口是my_process，ip作为地址偏移，能够完成对入口地址的寻址。而把thread.sp指向对应PCB内的char stack[KERNEL_STACK_SIZE-1]，用数组作为运行堆栈，为什么会为何指向stack[KERNEL_STACK_SIZE - 1]，需要注意的是：栈是由高地址向低地址增长。
接下来，
1
2
3
4
5
6
7
8
9
|
for(i=1;i<MAX_TASK_NUM;i++)
{
memcpy(&task[i],&task[0],sizeof(tPCB));
task[i].pid = i;
task[i].state = -1;
task[i].thread.sp = (unsigned long)&task[i].stack[KERNEL_STACK_SIZE-1];
task[i].next = task[i-1].next;
task[i-1].next = &task[i];
}
|
这段循环复制出了不同的进程，以零号进程为模板，复制了整个task的结构，重新设置了pid，状态为-1表示就绪态，修改了运行堆栈的指针，同时利用next指针来指向下一个进程，通过训完，完成了进程之间的一个循环链表，如图所示。这时候只有0号进程是运行态，而其他进程都是就绪态。
那么，
1
2
3
4
5
6
7
8
9
10
11
12
|
/* start process 0 by task[0] */
pid = 0;
my_current_task = &task[pid];
asm volatile(
"movl %1,%%esp\n\t" /* set task[pid].thread.sp to esp */
"pushl %1\n\t" /* push ebp */
"pushl %0\n\t" /* push task[pid].thread.ip */
"ret\n\t" /* pop task[pid].thread.ip to eip */
"popl %%ebp\n\t"
:
: "c" (task[pid].thread.ip),"d" (task[pid].thread.sp) /* input c or d mean %ecx/%edx*/
);
|
这段代码开始执行零号进程。为了对寄存器的严格把控，不受到编译器的影响，我们使用volatile关键字消除编译器的优化，使用内联汇编。
最初，将task[0].thread.sp拿去修改esp的值，这时候内核堆栈的栈顶被修改到了task[0]的sp位置。
然后，在这个位置出压入ebp的值，来保护原来的内核堆栈（注意！我们之前已经分析过了，事实上老师给出的这段精简内核代码是在原有Linux内核上跑起来的，所以实际上原有Linux内核会有内核堆栈，压入ebp的值的目的显然是为了保护堆栈内容方便返回）。然后我们设置task[0].thread.ip的值给eip，这样的话我们就能够保证cpu下一步能够执行我们的零号进程，这时候我们就完成了进入my_process()的过程。注意，这时候eip的值已经被修改了，所以最后一句的popl ebp并不会被立即执行。这时候CPU已经进入my_process()了。下图反应了堆栈的变化过程：
这时候，程序执行转到了my_process()，注意，这时候所有的进程只有task[0]才是执行态，my_need_sched == 0，无论如何，都不会触发时间片的轮转从而调度其他的进程。但是，我们有my_timer_handler()函数，根据上面的分析，老师代码对Linux内核的改动包括让include/linux/timer.c，在里面添加了一个外部引用的函数my_timer_handler()，并且在原来的Linux内核代码timer_interrupt()上添加了my_timer_handler()，事实上这个步骤保证了函数会被原来的linux内核自动调用，因此，my_timer_handler()能够得以自动执行，每次执行时，会检查时间计数time_count是否完成了100次计数，以及当前进程是否应该被调度，注意，这时候我们的零号进程是执行状态，my_need_sched == 0，不等于1，所以当time_count完成了100次计数后，会自动修改零号进程的my_need_sched值为1，这时候，零号进程就被暂停执行了。
1
2
3
4
5
6
|
if(time_count%100 == 0 && my_need_sched != 1)
{
printk(KERN_NOTICE ">>>my_timer_handler here<<<\n");
my_need_sched = 1;
}
time_count ++ ;
|
当完成暂停执行后，不要慌张，下面的这段代码还在被循环执行着，这时候一旦发现my_need_sched==1后，这时候便会触发时间片轮转调度的核心：my_schedule()函数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
int i = 0;
while(1)
{
i++;
if(i%10000000 == 0)
{
printk(KERN_NOTICE "this is process %d -\n",my_current_task->pid);
if(my_need_sched == 1)
{
my_need_sched = 0;
my_schedule();
}
printk(KERN_NOTICE "this is process %d +\n",my_current_task->pid);
}
}
|
好，那么接下来最麻烦的来了，我们来看看进程之间的切换到底做了哪些事情？
首先，下面的代码对当前进行的任务做了一次判断，判断当前的任务和接下来要被执行的任务是否为空，如果空，那么根本不需要调度，我们直接返回就完了。
1
2
3
4
5
6
|
if(my_current_task == NULL
|| my_current_task->next == NULL)
{
return;
}
printk(KERN_NOTICE ">>>my_schedule<<<\n");
|
那么接下来这段调度就是核心了：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
next = my_current_task->next;
prev = my_current_task;
if(next->state == 0)/* -1 unrunnable, 0 runnable, >0 stopped */
{
/* switch to next process */
asm volatile(
"pushl %%ebp\n\t" /* save ebp */
"movl %%esp,%0\n\t" /* save esp */
"movl %2,%%esp\n\t" /* restore esp */
"movl $1f,%1\n\t" /* save eip */
"pushl %3\n\t"
"ret\n\t" /* restore eip */
"1:\t" /* next process start here */
"popl %%ebp\n\t"
: "=m" (prev->thread.sp),"=m" (prev->thread.ip)
: "m" (next->thread.sp),"m" (next->thread.ip)
);
my_current_task = next;
printk(KERN_NOTICE ">>>switch %d to %d<<<\n",prev->pid,next->pid);
}
|
在上面的代码中，出现了一个next指针指向了当前任务的下一个任务。prev指针指向了我们的当前任务零号进程。看看上面我们画出来的进程之间的调度循环链表，可以知道，下一个被调度的进程应该是task[3]。这时候，零号进程的下一个进程task[3]的状态应该是-1，表示就绪态，所以不会执行上面的调度，相反会执行下面的这段调度：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
else
{
next->state = 0;
my_current_task = next;
printk(KERN_NOTICE ">>>switch %d to %d<<<\n",prev->pid,next->pid);
/* switch to new process */
asm volatile(
"pushl %%ebp\n\t" /* save ebp */
"movl %%esp,%0\n\t" /* save esp */
"movl %2,%%esp\n\t" /* restore esp */
"movl %2,%%ebp\n\t" /* restore ebp */
"movl $1f,%1\n\t" /* save eip */
"pushl %3\n\t"
"ret\n\t" /* restore eip */
: "=m" (prev->thread.sp),"=m" (prev->thread.ip)
: "m" (next->thread.sp),"m" (next->thread.ip)
);
}
|
这时候，task[3]的状态被更改为执行态，当前任务被修改为task[3]。这时候便开始需要进行零号进程的现场保护工作，以便我们日后的调度。
这时候，堆栈会保存ebp的值，同时将esp保存到零号进程的sp中。这是因为，当我们切换回零号进程的时候，可以通过零号进程内sp的值来寻找我们要执行的task[3]的进程堆栈。然后将task[3]的sp值设置到esp和ebp中，创建好了task[3]的执行堆栈。将task[3]执行任务的入口地址ip设置给eip，完成对任务的执行入口设置。这时候实际上后面的返回仍然不会被执行，因为在修改eip后，cpu又去执行下一步的my_process()了，因此这时候就会出现各种循环调用，利用时间片的统计，完成对进程之间的切换。
至此，我们便完成了一个基于时间片轮转调度的微内核代码的分析。
四、总结
支持多任务的操作系统，不可避免的需要设计进程之间的调度，上下文的转换就是进程间调度的核心。
显然，对于mykernel来说，next和prev之间的角色可以相互转换，上一个next在下一次进程调度的时候可能会变成prev，上一个prev在下一个进程调度的时候就是next。即是一种“参数化上下文转换”的形式。
my_schedule方法是调度的关键，其执行总是分为两部分，调度时执行前一部分，下一次调度回来后才会执行剩下的部分。
在现代操作系统当中，多任务运行的方式应该就是上述简化过程的复杂化实现。
