Linux系统分析实验(一):时间片轮转多道程序内核
Linux系统分析实验(一):时间片轮转多道程序内核
注:后三位416
原创作品转载请注明出处<https://github.com/mengning/linuxkernel/
实验环境
Ubuntu16.04虚拟机
VMware workstation 12 Player
实验步骤
-
下载
linux3.9.4
版本内核源码并打上mykernel
的补丁wget <https://www.kernel.org/pub/linux/kernel/v3.x/linux-3.9.4.tar.xz>
wget <https://raw.github.com/mengning/mykernel/master/mykernel_for_linux3.9.4sc.patch>
tar -xvf linux-3.9.4.tar
cd linux-3.9.4
patch -p1 < ../mykernel_for_linux3.9.4sc.patch
-
编译
make allnoconfig make
编译报错:缺少compiler-gcc5.h
的头文件。cd
到include/linux
下发现只有compiler-gcc4.h
,我们将该文件重命名为compiler-gcc5.h:mv compiler-gcc4.h compiler-gcc5.h
。
-
安装qemu启动内核
sudo apt-get install qemu # install QEMU sudo ln -s /usr/bin/qemu-system-i386 /usr/bin/qemu qemu -kernel arch/x86/boot/bzImage # 使用qemu启动内核
mykernel
代码分析
从孟宁老师的主页上获取源码 https://github.com/mengning/mykernel 下载mymain.c ,myinterrupt.c 和 mypcb.h
三个文件。
mypcb.h
:
该头文件包含一个thread
结构体线程的上下文(指令指针和栈顶指针)。PCB结构定义了进程控制块:
(1)pid
进程标识符;
(2)state
状态,-1表示不可运行,0表示可运行,>0
表示停止;
(3)定义了一个栈空间;
(4)一个Thread
变量;
(5)任务入口点;
(6)下一个PCB
的指针;
struct Thread {
unsigned long ip;//point to cpu run address
unsigned long sp;//point to the thread stack's top address
//todo add other attrubte of system thread
};
//PCB Struct
typedef struct PCB{
int pid; // pcb id
volatile long state; /* -1 unrunnable, 0 runnable, >0 stopped */
char stack[KERNEL_STACK_SIZE];// each pcb stack size is 1024*8
/* CPU-specific state of this task */
struct Thread thread;
unsigned long task_entry;//the task execute entry memory address
struct PCB *next;//pcb is a circular linked list
unsigned long priority;// task priority ////////
//todo add other attrubte of process control block
}tPCB;
myinterrupt.c
:
主要实现定时器中断,每隔1000ms进行my_need_sched
的检查,如果不为1,则置为1使其进入就绪队列。my_schedule函数具体实现了进程的切换。声明了两个指针,prev
和next
,分别指向当前进程和下一个进程。
void my_timer_handler(void)
{
#if 1
if(time_count%1000 == 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 there no task running or only a task ,it shouldn't need schedule
if(my_current_task == NULL
|| my_current_task->next == NULL)
{
printk(KERN_NOTICE " time out!!!,but no more than 2 task,need not schedule\n");
return;
}
/* schedule */
next = get_next();
prev = my_current_task;
printk(KERN_NOTICE " the next task is %d priority is %u\n",next->pid,next->priority);
/*进程上下文的切换,与函数调用堆栈类似*/
if(next->state == 0)/* -1 unrunnable, 0 runnable, >0 stopped */
{//save current scene
/* switch to next process */
asm volatile(
/*保存当前进程的ebp esp*/
"pushl %%ebp\n\t" /* save ebp */
"movl %%esp,%0\n\t" /* save esp */
/*构建下一个进程的esp*/
"movl %2,%%esp\n\t" /* restore esp */
/*$1f是指下面标号为1的位置,就是下一个进程启动的位置*/
"movl $1f,%1\n\t" /* save eip */
/*下一个进程eip压栈*/
"pushl %3\n\t"
/*恢复现场:eip指向下下个进程的地址ebp恢复为第一条指令压栈保存的ebp*/
"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;//switch to the next task
printk(KERN_NOTICE " switch from %d process to %d process\n >>>process %d running!!!<<<\n\n",prev->pid,next->pid,next->pid);
}
else
{
next->state = 0; //新的进程设置为正在运行状态
my_current_task = next;
printk(KERN_NOTICE " switch from %d process to %d process\n >>>process %d running!!!<<<\n\n\n",prev->pid,next->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 *//*新的进程从来没有执行过,所以栈为空esp与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;
}//end of my_schedule
mymain.c
:
在mymain.c
中,主要负责进程的初始化并启动进程:
(1) 初始化一个进程 为其分配进程编号、进程状态state、进程堆栈、线程、任务实体等,并将其next指针指向自己。
(2) 初始化更多的进程 根据第一个进程的部分资源,包括内存拷贝函数的运用,将0号进程的信息进行了复制,修改pid
等信息。
(3) 设置当前进程为0号进程,通过嵌入汇编代码来执行mykernel
内核。
void __init my_start_kernel(void)
{
int pid = 0;
/* Initialize process 0*/
task[pid].pid = pid;
task[pid].state = 0;/* -1 unrunnable, 0 runnable, >0 stopped */
// set task 0 execute entry address to my_process
/*进程入口地址与进程的eip设为my_process*/
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(pid=1;pid<MAX_TASK_NUM;pid++)
{
memcpy(&task[pid],&task[0],sizeof(tPCB));
task[pid].pid = pid;
task[pid].state = -1;
task[pid].thread.sp = (unsigned long)&task[pid].stack[KERNEL_STACK_SIZE-1];
task[pid].priority=get_rand(PRIORITY_MAX);//each time all tasks get a random priority
}
task[MAX_TASK_NUM-1].next=&task[0];
printk(KERN_NOTICE "\n\n\n\n\n\n system begin :>>>process 0 running!!!<<<\n\n");
/* start process 0 by task[0] */
pid = 0;
my_current_task = &task[pid];
/*构建0号进程的堆栈环境 ,启动0号进程
c语言中嵌入汇编代码,格式如下:
asm (
内容
: 输出
:输入
);
加入volatitle表示不让编译器优化
"c"就是ecx,内容为task[pid].thread.ip,"d"就是edx,内容为task[pid].thread.sp。从冒号 开始,以逗号分隔开,从0开始,每一个寄存器有一个标号,即ecx的标号为%0,edx的标号为%1。
第二步将esp指向当前进程的栈顶;第三行将标号%1压栈,因为上一句就是当前进程的esp被压栈,此时 栈为空,当前ebp被压栈,esp下移一位;第四行将当前进程的指令指针eip压栈,第五行将eip指向当前 进程指针,开始执行当前进程。
*/
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*/
);
}
/*最后实现了my_process函数,这是一个死循环,每个进程都是执行此函数。每10000000次,打印当前进 程的pid,全局变量my_need_sched,通过对my_need_sched进行判断,若为1,则通知正在执行的进程 执行调度程序,然后打印调度后的进程pid。*/
void my_process(void)
{
int i = 0;
while(1) {
i++;
if(i%10000000 == 0) {
if(my_need_sched == 1) {
/*调度标志位,在myinterrupt.c的my_timer_handler()函数中设置*/
my_need_sched = 0;
sand_priority();
/*主动调用进程列表的下一个进程*/
my_schedule();
}
}
}
}//end of my_process
实验总结
进程优先级
调度算法中最主要的一类就是基于优先级的调度。这是一种依据进程的价值和其对处理器时间的需求来对进程分级的想法。优先级高的进程先执行,低的后执行,同样优先级的进程按轮转方式进行调度。
Linux依据以上思想实现了一种基于动态优先级的调度方法。一開始,该方法先设置主要的优先级,然而它同意调度程度依据须要来加、减优先级。比如,假设一个进程在I/O等待上耗费的时间多于其执行时间,那么该进程明显属于I/O消耗型,它的优先级会被动态提高。相反,处理器消耗型进程的优先级会被动态减少。
Linux内核提供两组独立的优先级范围。第一种是nice值,范围从-20到+19,默认值是0。nice值越大优先级越低。另外一种是实时优先级,其值可配置,范围从0到99,不论什么实时进程的优先级都高于普通的进程。
时间片
时间片是一个数值,它表明进程在被抢占前所能持续执行的时间,I/O消耗型不须要长的时间片,而处理器消耗型的进程则希望越长越好。时间片的大小设置并不简单,设大了,系统响应变慢(调度周期长);设小了,进程频繁切换带来的处理器消耗。
Linux调度程序提高交互程序的优先级,让它们运行得更频繁。于是,调度程序提供了比較长的默认时间片给交互程序。此外,Linux调度程序还能依据进程的优先级动态调整分配给它的时间片。从而保证优先级高的进程,假定也是重要性高的进程,运行的频率高,运行时间长。通过实现这样一种动态调整优先级和时间片长度的机制,Linux调度性性能不但非常稳定并且也非常强健。
注意,进程并非一定非要一次就用完它全部的时间片,比如一个拥有100毫秒时间片的进程,能够通过反复调度,分5次每次20毫秒用完这些时间片。
当一个进程的时间耗尽时,就觉得到期了。没有时间片的进程不会再投入执行,除非等到其它全部的进程都耗尽了他们的时间片。那个时候,全部进程的时间片会被又一次计算。