一个简单进程调度器的实现和分析

浏览数：16 / 时间：2015年06月20日

主体代码文件有三个，mypcb.h，myinterupt.h, mymain.h，mypcb定义了进程控制块结构，myinterupt实现了中断处理程序，mymain是实际入口点，以下代码省去了头文件部分，并有详细注释，下面的分析中只挑选关键部分进行分析

 1 /* A simply process control block */
 2 
 3 #define MAX_TASK_NUM 10 //max number of tasks
 4 #define KERNEL_STACK_SIZE 1024*8 //max kernel stack size of a single process, here is 8KiB
 5 
 6 //This struct describes basic CPU info
 7 struct Thread
 8 {
 9     unsigned long ip; //EIP Register, Points to next instruction
10     unsigned long sp; //ESP Register, Points to Stack head
11 };
12 
13 //This struct describes the structure of PCB
14 typedef struct PCB
15 {
16     int pid;    //pid
17     volatile long state;    //process state
18     /* -1 unrunnable,
19      * 0 runnable,
20      * >0 stopped */
21     char stack[KERNEL_STACK_SIZE];
22     //each PCB stack size is KERNEL_STACK_SIZE, here is 8KiB
23     struct Thread thread; //CPU info
24     unsigned long task_entry; //task execute entry
25     struct PCB *next; //all processes are in a circled linked list
26 }tPCB;
27 
28 void my_schedule(void);

 1 #include "mypcb.h"
 2 
 3 extern tPCB task[MAX_TASK_NUM];
 4 extern tPCB *my_current_task;
 5 extern volatile int my_need_sched;
 6 volatile int time_count;
 7 
 8 /*
 9  * Called by timer interrupt.
10  */
11 void my_timer_handler(void)
12 {
13 #if 1
14     //here defines the system circle count, after that count the processes should be resheduled
15     if(time_count % 10 == 0 && my_need_sched != 1)
16     {
17         printk(KERN_NOTICE ">>>my_timer_handler here<<<\n");
18         my_need_sched = 1;
19     }
20     time_count ++;
21 #endif
22     return;
23 }
24 
25 void my_schedule(void)
26 {
27     tPCB *next;
28     tPCB *prev;
29 
30     printk(KERN_NOTICE "This is process %d, next is process %d", my_current_task->pid, my_current_task->next->pid);
31 
32     if(my_current_task == NULL || my_current_task->next == NULL)
33     {
34         return;
35     }
36 
37     printk(KERN_NOTICE ">>>my_schedule<<<\n");
38 
39     //Scheduler code below
40     next = my_current_task->next;
41     prev = my_current_task;
42 
43     //state 0 means next process is runnable
44     if(next->state == 0) // -1 unrunnable, 0 runnable, >0 stopped
45     {
46         asm volatile(
47                 //saving current task scene
48                 "pushl %%ebp\n\t"   //save ebp, aka current scene
49                 "movl %%esp, %0\n\t"//save esp, also part of current scene
50                 //changing to next task
51                 "movl %2, %%esp\n\t"//set esp to the very value of next task
52                 "movl $1f, %1\n\t"  //save current EIP to memory
53                 "pushl %3\n\t"      //next task‘s EIP is now in stack
54                 "ret\n\t"           //reset EIP to next task‘s EIP, same as ‘popl %eip‘
55                 "1:\t"              //flag, next process start here
56                 "popl %%ebp\n\t"    //
57                 :"=m"(prev->thread.sp), "=m"(prev->thread.ip)
58                 :"m"(next->thread.sp), "m"(next->thread.ip)
59         );
60         //The inline assembly did everything to cut the scene, now we are running ‘next‘ task
61         my_current_task = next;
62         printk(KERN_NOTICE ">>>switch %d to %d<<<\n", prev->pid, next->pid);
63     }
64     else
65     {
66         next->state = 0;
67         my_current_task = next;
68         printk(KERN_NOTICE ">>>switch %d to %d<<<\n", prev->pid, next->pid);
69         //Switch to new process
70         asm volatile(
71                 //Saving current task scene
72                 "pushl %%ebp\n\t"   //save ebp, same as above
73                 "movl %%esp, %0\n\t"//save esp, same as above
74                 //Changing to next task
75                 "movl %2, %%esp\n\t"//reset esp, same as above
76                 "movl %2, %%ebp\n\t"//set ebp to next->thread.sp, since next task is totally new, so its stack should be empty. aka esp == ebp
77                 "movl $1f, %1\n\t"  //save EIP
78                 "pushl %3\n\t"      //enstack next task‘s EIP, same as above
79                 "ret\n\t"           //reset EIP, same as above
80                 :"=m"(prev->thread.sp), "=m"(prev->thread.ip)
81                 :"m"(next->thread.sp), "m"(next->thread.ip)
82         );
83     }
84     return;
85 }

#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;
    //Initializing process 0, root of everything
    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 processes
    for(++pid; pid < MAX_TASK_NUM; ++pid)
    {
        memcpy(&task[pid], &task[0], sizeof(tPCB)); //Just a simple memcpy, copies every thing of process 0
        //Reset PCB info, everything is similar as above, except this new process‘s state is ‘unrunnable‘
        task[pid].pid = pid;
        task[pid].state = -1; // -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];
        //Link the new process to process list
        task[pid].next = task[pid-1].next;
        task[pid-1].next = &task[pid];
    }

    //Starting process 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 process 0‘s sp to stack
            //Redirect EIP to entry point of process 0
            "pushl %0\n\t"          //push task[pid].thread.ip
            "ret\n\t"               //Set actuall EIP via ret
            "popl %%ebp\n\t"        //ebp is now process0‘s esp, aka the process is new
            :
            :"c"(task[pid].thread.ip),"d"(task[pid].thread.sp)
    );
}

//user process
void my_process(void)
{
    int i = 0;
    while(true)
    {
        ++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);
        }
    }
}

mypcb.h中定义了pcb的数据结构，每个字段都已经用注释注明含义，此处不再赘述，需要注意的是tPCB.next如何指向下一个PCB从某种程度上影响了进程调度的方式，这儿采用时间片轮转调度法，因此在后面的mymain中将所有进程连接成了一个环形链表进行调度。

mymain是入口点，从整体结构上可以看出，系统启动时首先创建了0号进程，然后由0号进程fork出了所有其他进程，这个过程很简单，不赘述，需要详细说一下的是0号进程的启动过程，代码如下

 1 //Starting process 0
 2 pid = 0;
 3 my_current_task = &task[pid];
 4 asm volatile(
 5        "movl %1, %%esp\n\t"    //set task[pid].thread.sp to esp
 6        "pushl %1\n\t"          //push process 0‘s sp to stack
 7        //Redirect EIP to entry point of process 0
 8        "pushl %0\n\t"          //push task[pid].thread.ip
 9        "ret\n\t"               //Set actuall EIP via ret
10        "popl %%ebp\n\t"        //ebp is now process0‘s esp, aka the process is new
11        :
12        :"c"(task[pid].thread.ip),"d"(task[pid].thread.sp)
13 );

这段代码首先将0号进程设置为当前进程，接下来的汇编才真正让0号进程跑了起来

L5，将0号进程的sp保存到esp中，即将栈顶挪到了0号进程栈的栈顶，但由于0号进程此时还未运行，实际上这儿也是其栈底

L6，继续将0号进程的sp入栈作为栈底

下面几行将程序执行流真正定向到了process 0

L8，L9，我们知道ret相当于popl %eip,所以现将进程0的eip入栈然后ret，不难理解，这是将0号进程的eip值实际注入到了cpu的eip寄存器中

L10，如上面所说，当前栈顶位置储存的是0号进程的栈底，所以这句重设ebp为0号进程的栈底

这段汇编执行完成后，CPU就会根据eip指向的0号进程的入口点继续执行了

以上就是系统启动的过程，下面的my_process则是一个进程的主体，这个进程干的事情很简单，计时，达到预设时间后调用中断处理函数做好准备切换到下一个进程，代码很简单不再赘述

下面要说的myinterupt是调度器的核心，内含了中断处理函数，也就是调度器真正实现保护现场和恢复现场的部分

time_handler不难理解，计时，到达预设时间时候通知用户进程准备进行调度，不详细解释

 1     //Scheduler code below
 2     next = my_current_task->next;
 3     prev = my_current_task;
 4 
 5     //state 0 means next process is runnable
 6     if(next->state == 0) // -1 unrunnable, 0 runnable, >0 stopped
 7     {
 8         asm volatile(
 9                 //saving current task scene
10                 "pushl %%ebp\n\t"   //save ebp, aka current scene
11                 "movl %%esp, %0\n\t"//save esp, also part of current scene
12                 //changing to next task
13                 "movl %2, %%esp\n\t"//set esp to the very value of next task
14                 "movl $1f, %1\n\t"  //save current EIP to memory
15                 "pushl %3\n\t"      //next task‘s EIP is now in stack
16                 "ret\n\t"           //reset EIP to next task‘s EIP, same as ‘popl %eip‘
17                 "1:\t"              //flag, next process start here
18                 "popl %%ebp\n\t"    //
19                 :"=m"(prev->thread.sp), "=m"(prev->thread.ip)
20                 :"m"(next->thread.sp), "m"(next->thread.ip)
21         );
22         //The inline assembly did everything to cut the scene, now we are running ‘next‘ task
23         my_current_task = next;
24         printk(KERN_NOTICE ">>>switch %d to %d<<<\n", prev->pid, next->pid);
25     }
26     else
27     {
28         next->state = 0;
29         my_current_task = next;
30         printk(KERN_NOTICE ">>>switch %d to %d<<<\n", prev->pid, next->pid);
31         //Switch to new process
32         asm volatile(
33                 //Saving current task scene
34                 "pushl %%ebp\n\t"   //save ebp, same as above
35                 "movl %%esp, %0\n\t"//save esp, same as above
36                 //Changing to next task
37                 "movl %2, %%esp\n\t"//reset esp, same as above
38                 "movl %2, %%ebp\n\t"//set ebp to next->thread.sp, since next task is totally new, so its stack should be empty. aka esp == ebp
39                 "movl $1f, %1\n\t"  //save EIP
40                 "pushl %3\n\t"      //enstack next task‘s EIP, same as above
41                 "ret\n\t"           //reset EIP, same as above
42                 :"=m"(prev->thread.sp), "=m"(prev->thread.ip)
43                 :"m"(next->thread.sp), "m"(next->thread.ip)
44         );
45     }