天衣有缝

冠盖满京华,斯人独憔悴~
posts - 35, comments - 115, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

6课:多任务    下载源代码


声明:转载请保留:

译者:http://www.cppblog.com/jinglexy

原作者:xiaoming.mo at skelix dot org

MSN & Email: jinglexy at yahoo dot com dot cn


目标

 

在本课中,我们将在skelix内核中同时运行多个任务(本文中可以暂时理解成进程)。每个任务都有自己的LDT表,并且是基于优先级的任务调度。


现在我们开始skelix内核的多任务支持工作了。首先要澄清的是:在单处理器上面,进程只能并发,而不是并行。就是说同一时刻只能有一个任务在运行,cpu会划分很多很小的时间片来运行各个任务,这样看起来就像多个任务在同时运行一样。i386从硬件上就支持多任务了,但是也可以通过编程来实现,本文就是一个例子,每个任务轮流运行一个小的时间片。我们知道,单个cpu只有1组寄存器,这些可以用于所有任务。当由一个任务切换到另一个任务时,必须先保存原来任务的运行环境(就是一堆寄存器和其他信息),通常称这个运行环境叫上下文i386使用一个叫TSS的段来存储这些信息,这个TSS段至少104字节(不包括IOPL位图的话),对应它的是一个TSS描述符。TSS描述符只能在GDT表中,这意味着任务不能自己通过LDT来切换到其他任务。当时钟中断到来切换任务时,CPU会自动保存相关信息到TSS中。

TSS
定义了任务的上下文环境,结构如下:

 

                  (图-1

 

         31       16,15          0
        +------------------------+                |
        |   NO use  |  Back Link |                |
高地址
        +------------------------+                |
        |         ESP0           |                |
        +------------------------+                |
        |   NO use  |    SS0     |                |
        +------------------------+                |
        |         ESP1           |                |
        +------------------------+                |
        |   NO use  |    SS1     |                |
低地址
        +------------------------+               \|/
        |         ESP2           |
        +------------------------+
        |   NO use  |    SS2     |
        +------------------------+
        |         CR3            |
        +------------------------+
        |         EIP            |
        +------------------------+
        |        EFLAGS          |
        +------------------------+
        |         EAX            |
        +------------------------+
        |         ECX            |
        +------------------------+
        |         EDX            |
        +------------------------+
        |         EBX            |
        +------------------------+
        |         ESP            |
        +------------------------+
        |         EBP            |
        +------------------------+
        |         ESI            |
        +------------------------+
        |         EDI            |
        +------------------------+
        |   NO use  |    ES      |
        +------------------------+
        |   NO use  |    CS      |
        +------------------------+
        |   NO use  |    SS      |
        +------------------------+
        |   NO use  |    DS      |
        +------------------------+
        |   NO use  |    FS      |
        +------------------------+
        |   NO use  |    GS      |
        +------------------------+

        |   NO use  |    LDT     |
        +------------------------+
        |  I/O
位图 NO use | T |
        +------------------------+

i386
处理器可以使用嵌套任务,就是说当任务1切换到任务2时,任务2 Back Link 域被设置成任务1的选择子,且任务2EFLAGS中的NT(嵌套任务标识)置位,这样任务2返回时,cpu就知道切换回任务1。我们知道,i3864中特权级,所以可以在TSS中设置这四种特权级下的堆栈。比如一个任务运行在ring3特权级下,它使用用户态堆栈,使用系统调用可以让这个任务切换到ring0的内核态,这是堆栈也必须切换到内核态堆栈。这些堆栈指针就是存放在TSS中的。现在我们来看看TSS描述符(它只能放在GDT中):

 

                   图-2TSS描述符定义

 

 63_______________56__55__54__53__52__51_____________48_

基地址(3124位) | G | 0 | 0 |AVL| 长度(1916位) |

|_______________________________________________________|

 

 _47__46__45__44________41__40____39_________________32_

| P |  DPL | 0 | 1 | 0 | B |  1  |  基地址(2316位)  |

|_______________________________________________________|

 

 31____________________________________________________16

|                    基地址(150位)                  |

|_______________________________________________________|

 

 16_____________________________________________________

|                    长度(150位)                    |

|_______________________________________________________|

 

*********************************************************

                   图-3通用描述符定义

 

 63_______________56__55__54__53__52__51_____________48_

基地址(3124位) | G |D/B| X | U | 长度(1916位) |

|_______________________________________________________|

 

 _47__46__45__44____41______40____39_________________32_

| P |  DPL |     类型    |  A   |  基地址(2316位)   |

|_______________________________________________________|

 

 31____________________________________________________16

|                    基地址(150位)                  |

|_______________________________________________________|

 

 16_____________________________________________________

|                    长度(150位)                    |

|_______________________________________________________|

 

我们现在来比较一下通用描述符和TSS描述符,在TSS描述符中,我们看到D位(数据还是代码段)和X位(未使用)都被置为0,而且AVL位有效。类型type010B,第41位,及B位是TSS描述符的忙标识,因为一个进程只能有一个TSS,所以当进程执行时,B位将被设置,表示这个TSS正在被使用,除了进程调度外,不能再使用它了。A位被置为1,即便A位被置为可写,TSS也不能被进程读或写。TSS的其他域和通用描述符一样,只是要注意一点:就是TSS的长度界限至少要有104字节。另外需要注意的是,skelix暂时不支持fpummxsse,如果读者想扩展的话需要注意每个进程都有自己的fpusse环境。

 

在本课中,TSS描述符的DPL将被置为0,所以只有内核可以进程任务切换。和GDTRLDTR一样,TSS描述符也有自己的用于切换任务的寄存器,就是TR。可以用LTR指令来加载这个寄存器。GDT中的TSS描述符不能被加载到任何其他寄存器,否则会发生一个异常。

切换任务有多种方法,我们的做法是使用jmp指令跳转到TSS描述符。(还有其他方法,如从中断返回,使用任务门(起始也相当于jmpTSS上))。赵博的linux内核完全剖析上讲到了切换任务的几种方法,并详细讨论了,不清楚的同学可以购买该书。

在切换任务时,CPU首先保存当前进程的上下文环境到当前TSS中,然后加载新任务的TSSTR寄存器中,然后从新任务的TSS中加载上下文到寄存器中,最后跳转到新任务的第一条指令并开始执行。不知道这样有没有说清楚,这个是比较关键的地方,欢迎和我讨论:jinglexy at yahoo dot com dot cnMSN)。

OK
,让程序来说明一起吧。先看看TSS数据结构的定义:
06/include/task.h

 

struct TSS_STRUCT {
    int    back_link;
    int    esp0, ss0;
    int    esp1, ss1;
    int    esp2, ss2;
    int    cr3;
    int    eip;
    int    eflags;
    int    eax,ecx,edx,ebx;
    int    esp, ebp;
    int    esi, edi;
    int    es, cs, ss, ds, fs, gs;
    int    ldt;
    int    trace_bitmap;
};

没有pad的数据结构是104字节,如果你使用或模拟 IA64 平台的话,就需要查找相关的资料了。

对于一个正在运行的OS,上面的信息显然是不够的,所有我定义了另外一个包装TSS的数据结构,

即进程信息(process control block),以后简称为pcb

#define TS_RUNNING    0                // 任务的三种状态
#define TS_RUNABLE    1
#define TS_STOPPED    2

struct TASK_STRUCT {                   // pcb
定义
    struct TSS_STRUCT tss;
    unsigned long long tss_entry;      // tss
描述符在gdt中的8字节入口项
    unsigned long long ldt[2];
    unsigned long long ldt_entry;
    int state;
    int priority;
    struct TASK_STRUCT *next;
};
#define DEFAULT_LDT_CODE    0x00cffa000000ffffULL
#define DEFAULT_LDT_DATA    0x00cff2000000ffffULL
#define INITIAL_PRIO        200

 

priority 表示任务优先级,新建任务默认的优先级是下面的 INITIAL_PRIOskelix内核中所有的任务都用一个单向链表来表示,这样做起来比较简单。我们现在来看一个任务的例子,就是任务0:内核初始化完成后,就执行任务0


06/task.c

static unsigned long TASK0_STACK[256] = {0xf};

上面数据是任务0在特权级0下使用的堆栈,0xf值如果不设置的话,这块内存就会发生一些错误,我也不清楚是为什么,所以第一个元素随便给了一个非0值。

struct TASK_STRUCT TASK0 = {

    /* tss */
    {
        0,
        /* esp0                                    ss0 */
        (unsigned)&TASK0_STACK+sizeof TASK0_STACK, DATA_SEL,

        上面定义会使任务的esp0执行栈底,使用内核数据段选择子就可以了
        /* esp1 ss1 esp2 ss2 */
        0, 0, 0, 0,
        /* cr3 */
        0,
        /* eip eflags */
        0, 0,
        /* eax ecx edx ebx */
        0, 0, 0, 0,
        /* esp ebp */
        0, 0,
        /* esi edi */
        0, 0,
        /* es          cs             ds */
        USER_DATA_SEL, USER_CODE_SEL, USER_DATA_SEL,
        /* ss          fs             gs */
        USER_DATA_SEL, USER_DATA_SEL, USER_DATA_SEL, 
        /* ldt
:见后面说明 */
        0x20,
        /* trace_bitmap */
        0x00000000},
    /* tss_entry */
    0,
    /* ldt[2] */
    {DEFAULT_LDT_CODE, DEFAULT_LDT_DATA},
    /* ldt_entry */
    0,
    /* state */
    TS_RUNNING,
    /* priority */
    INITIAL_PRIO,
    /* next */
    0,
};

现在,我们定义了一个TSS,再在GDT中加入描述符索引:


06/bootsect.s

gdt:
        .quad    0x0000000000000000 # null descriptor
        .quad    0x00cf9a000000ffff # cs
        .quad    0x00cf92000000ffff # ds
        .quad    0x0000000000000000 # reserved for further use
        .quad    0x0000000000000000 # reserved for further use

第四项(0x3)用于存放该任务的TSS,所以定义了一个宏:  CURR_TASK_TSS = 3来索引GDT中的这个TSS。当任务释放控制权后,会加载自己的TSS描述符索引到pcbtss_entry域。不管多少任务,都可以只使用两个描述符,切换任务前更新GDT中的描述符即可。由于GDT有长度限制,只能存放8096个描述符,linux操作系统限制了任务的数量,我不知道为什么要这样做,因为突破进程数限制看起来如此的简单。


06/task.c

unsigned long long set_tss(unsigned long long tss) {             // 参数为tss在内存中的地址
    unsigned long long __tss_entry = 0x0080890000000067ULL;
    __tss_entry |= ((tss)<<16) & 0xffffff0000ULL;                //
基地址低24
    __tss_entry |= ((tss)<<32) & 0xff00  0000  0000   0000ULL;   //
基地址高8
    return gdt[CURR_TASK_TSS] = __tss_entry;
}

这个函数产生TSS描述符,并存放它到GDT中,可以看到,描述符的DPL设置为0,所以只有内核可以用这个描述符。

属性0080890000000067分析:0x67是长度103(从0开始计算,即长104),89p位为1dpl位为0b位为180是粒度G位为1


unsigned long long get_tss(void) {
    return gdt[CURR_TASK_TSS];
}

LDT

我们看了这么多关于GDTLDT的代码后,LDT非常容易理解了。它和GDT差不多,区别是具有局部特性,每个任务都可以有自己的LDT,我们在skelix内核中为每个任务在LDT中设置两个描述符项,第一项是代码段,第二项是数据段和堆栈段,描述符选择子格式如下:

            图-4

 15______________________________3___2____1___0__

|              Index              | TI |   RPL  |

|_______________________________________________|

 

我们设置所有任务的特权级为3,即RPL 11b,且TI 1(表示使用LDT而不是GDT),和GDT不同的是,LDT的第一项可以使用而不是保留,所以代码段的选择子为0x7,而数据段和堆栈段选择子为0xf

TSS
数据结构中,有一个LDT域,保存的是GDT表中的描述符。听起来可能昏菜,我们现在来搞明白她。首先,每个进程都有自己的LDT表,而且这个表可以在内存的任何地方(暂时不考虑虚拟内存),所以需要一个描述符来索引这个内存地址(即LDT表),这个描述符就放在GDT中,并且在TSS中存放一份该描述符的选择子。

画个图来说明好了:

            图-5

 

 ________________                            ________________

|      TASK      |                          |      GDT       |

|________________|                          |                |

TSS  __________|/    选择子存于此         |________________|

|     | LDT field|--------------------------|     描述符     |

|      ----------|\                        /|________________|

|________________|                        / |                |

|                |                       /  |                |

|                |     描述符索引该 LDT /   |                |

|                |         -------------    |                |

|                |        /                 |________________|

|                |       /

|                |      /

|                |     /

|                |    /

|                |   /

|                |  /

|________________| /

|      LDT       |/

|________________|

|________________|

GDT
中的第三项用于任务TSS,第四项用于任务LDT。通过选择子0x180x20分包可以索引到它们。和设置TSS一样,对应也写有两个LDT操作的函数。

06/task.c

 

unsigned long long
set_ldt(unsigned long long ldt) {
    unsigned long long ldt_entry = 0x008082000000000fULL;        // DPL
3而不是0

    ldt_entry |= ((ldt)<<16) & 0xffffff0000ULL;
    ldt_entry |= ((ldt)<<32) & 0xff00000000000000ULL;
    return gdt[CURR_TASK_LDT] = ldt_entry;
}

unsigned long long
get_ldt(void) {
    return gdt[CURR_TASK_LDT];
}

现在,我们将设置所有任务使用相同的LDT,这些任务共享相同的内存空间。如果你要设计字节的OS,这不会是个好主意。但是后面会为这些任务通过虚拟内存机制来设置不同的内存空间,后续课程会讲到。

06/include/task.h

 

#define DEFAULT_LDT_CODE    0x00cffa000000ffffULL
#define DEFAULT_LDT_DATA    0x00cff2000000ffffULL

上面就是任务的LDT描述符定义,注意DPLdescriptor priority level)值为3

 

上面已经提到,所有任务使用一个单向链表连接起来,其中有两个重要指针:一个是任务0TASK0)的next指针,它是所有任务链表的头指针;另一个是current指针,指向当前正在运行的任务。

创建任务并调度

首先,我们定义有:
06/task.c

struct TASK_STRUCT *current = &TASK0;

 

现在我们来看看新任务是如何创建的:
06/init.c

static void
new_task(struct TASK_STRUCT *task, unsigned int eip,
                unsigned int stack0, unsigned int stack3) {

// 这个函数有4个参数:第一个参数是任务数据结构的内存地址

// 第二个参数是任务入口地址

// 第三个和第四个参数是0环和3环特权级下堆栈地址

// 由于堆栈地址的描述符选择子是固定的,所以就不用传进来了

    memcpy(task, &TASK0, sizeof(struct TASK_STRUCT));        // TASK0
作为任务模板
    task->tss.esp0 = stack0;
    task->tss.eip = eip;
    task->tss.eflags = 0x3202;        //
合适的状态标识
    task->tss.esp = stack3;

    task->priority = INITIAL_PRIO;    //
新任务默认优先级

    task->state = TS_STOPPED;
    task->next = current->next;
    current->next = task;
    task->state = TS_RUNABLE;
}
extern void task1_run(void);          // 
任务入口函数
extern void task2_run(void);

static long task1_stack0[1024] = {0xf, };
static long task1_stack3[1024] = {0xf, };
static long task2_stack0[1024] = {0xf, };
static long task2_stack3[1024] = {0xf, };

// 因为没有内核中没有实现内存管理,所以固定设置一些任务和她们使用的堆栈。

// 任务0运行在内核态,任务1和任务2运行在ring3

void
init(void) {
    char wheel[] = {'\\', '|', '/', '-'};
    int i = 0;
    struct TASK_STRUCT task1;                      //
移到全局定义较合适
    struct TASK_STRUCT task2;

    idt_install();
    pic_install();
    kb_install();
    timer_install(100);

    set_tss((unsigned long long)&TASK0.tss);       // 让任务0先跑起来
    set_ldt((unsigned long long)&TASK0.ldt);

    __asm__ ("ltrw    %%ax\n\t"::"a"(TSS_SEL));    // 加载任务0使用的TRLDTR寄存器
    __asm__ ("lldt    %%ax\n\t"::"a"(LDT_SEL));    //
使用ltrwlldt指令

 

    sti();                                         // 从现在开始捕获中断或异常
    new_task(&task1,                               //
注意:创建任务时,中断是使能的
            (unsigned int)task1_run,
            (unsigned int)task1_stack0+sizeof task1_stack0,
            (unsigned int)task1_stack3+sizeof task1_stack3);
    new_task(&task2,
            (unsigned int)task2_run,
            (unsigned int)task2_stack0+sizeof task2_stack0,
            (unsigned int)task1_stack3+sizeof task2_stack3);

 

    __asm__ ("movl %%esp,%%eax\n\t" \
             "pushl %%ecx\n\t" \         //
任务0内核栈ss
             "pushl %%eax\n\t" \         //
任务0内核栈esp0
             "pushfl\n\t" \              // eflags
             "pushl %%ebx\n\t" \         //
任务0代码段选择子cs
             "pushl $1f\n\t" \           // 
任务0函数地址eip:就是下面第2行汇编
             "iret\n" \
             "1:\tmovw %%cx,%%ds\n\t" \
             "movw %%cx,%%es\n\t" \
             "movw %%cx,%%fs\n\t" \
             "movw %%cx,%%gs" \
             ::"b"(USER_CODE_SEL),"c"(USER_DATA_SEL));

    // 注意:现在开始内核运行在任务0上了,通过iret指令长跳转到任务0

    // (先加载正确的EIPCSSSESP,图如下:)
    +--------------------+
    | LDT stack selector |
    +--------------------+
    |        ESP         |
    +--------------------+
    |       EFLAGS       |
    +--------------------+
    | LDT code selector  |
    +--------------------+
    |        EIP         |
    +--------------------+

 

    for (;;) {
        __asm__ ("movb    %%al,    0xb8000+160*24"::"a"(wheel[i]));
        if (i == sizeof wheel)
            i = 0;
        else
            ++i;
    }
}

现在,任务已经有了,万事具备只欠东风了,下面加入时钟中断代码进行任务调度。
06/timer.c

void do_timer(void) {        // 时钟中断处理函数
    struct TASK_STRUCT *v = &TASK0;
    int x, y;
    ++timer_ticks;
    get_cursor(&x, &y);
    set_cursor(71, 24);
    kprintf(KPL_DUMP, "%x", timer_ticks);
    set_cursor(x, y);
    outb(0x20, 0x20);
    cli();
    for (; v; v=v->next) {   //
遍历链表,调整任务优先级
        if (v->state == TS_RUNNING) {
            if ((v->priority+=30) <= 0)
                v->priority = 0xffffffff;
        } else
            v->priority -= 10;    // 
值越低,优先级越高(等待的任务优先级会变高)

        // *nix内核通常这样做:较小的值优先级较高
    }

    if (! (timer_ticks%1))
        scheduler();

    sti();
}

 

调度函数实现:
06/task.c

void scheduler(void) {
    struct TASK_STRUCT *v = &TASK0, *tmp = 0;
    int cp = current->priority;

    for (; v; v = v->next) {
        if ((v->state==TS_RUNABLE) && (cp>v->priority)) {
            tmp = v;
            cp = v->priority;
        }
    }    //
遍历链表,找寻优先级最高的任务(即值最小的任务)

    if (tmp && (tmp!=current)) {           // tmp
是遍历的结果
        current->tss_entry = get_tss();    //
TSS LDT描述符
        current->ldt_entry = get_ldt();
        tmp->tss_entry = set_tss((unsigned long long)((unsigned int)&tmp->tss));
        tmp->ldt_entry = set_ldt((unsigned long long)((unsigned int)&tmp->ldt));


        current->state = TS_RUNABLE;
        tmp->state = TS_RUNNING;
        current = tmp;

        __asm__ __volatile__("ljmp    $" TSS_SEL_STR ",    $0\n\t");

        // skelix通过长跳转到TSS描述符上(偏移应为0)切换任务
    }
}


下面是任务 A & B

06/isr.s

task1_run:
        call    do_task1
        jmp     task1_run
task2_run:
        call    do_task2
        jmp     task2_run

这里使用汇编而不是c语言来写这两个任务的入口函数的原因,

是不想在跳转前后改变内核栈。

 

我们现在看看能不能在任务1和任务2中使用kprintf
06/init.c

void
do_task1(void) {
    unsigned int cs;
    __asm__ ("movl    %%cs,    %%eax":"=a"(cs));
    kprintf(KPL_DUMP, "%x", cs);
    for (;;)
        ;
}

void
do_task2(void) {
    unsigned int cs;
    __asm__ ("movl    %%cs,    %%eax":"=a"(cs));
    kprintf(KPL_PANIC, "%x", cs);
    for (;;)
        ;
}

 

修改Makefile 中的 KERNEL_OBJS
06/MakefileKERNEL_OBJS= load.o init.o isr.o timer.o libcc.o scr.o kb.o task.o kprintf.o exceptions.o

编译,运行一把。截图就不贴出来了(结果是看不到任务1和任务2的打印:ring3任务当然不能使用ring0函数)

ok,现在改一下这两个任务函数:
06/init.cvoid
do_task1(void) {
    print_c('A', BLUE, WHITE);
}

void
do_task2(void) {
    print_c('B', GRAY, BROWN);
}

 

编译,运行,正是我们想要的结果。

 

 

Feedback

# re: 自己动手写内核(第6课:多任务)(原创)  回复  更多评论   

2007-05-18 19:06 by raywill
加油哦~

快快去实现内存管理,文件系统~

那才是最有挑战的地方!Fighting!

------------
raywill.blog.sohu.com

# re: 自己动手写内核(第6课:多任务)(原创)  回复  更多评论   

2007-05-18 19:19 by raywill
不过,发现你这都是转载吧.....

skelix....

请注明 :(


# re: 自己动手写内核(第6课:多任务)(原创)[未登录]  回复  更多评论   

2007-05-19 09:32 by 天衣有缝
没错,翻译文章,原作者只在第一篇声明了,所有文章整理完的时候加上去把,免得对不起作者了,相对来说我做的事情就少很多。

欢迎批评指正

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理