第11章 任务调度

任务调度

如何在Intel 386 CPU进行任务切换 在Intel 386 CPU中支持硬件切换任务(有多种硬件切换方法,但是我们只用一种方法)。

386 CPU 支持:

  • 任务嵌套(我们不用)
  • 支持4种特权级(我们只用两种,0和3)

TSS descriptor只在GDT中,可以参考《IBM-PC汇编语言程序设计 第2版》p545。任务切换只能由kernel来进行,因此需设置TSS descriptor中的DPL为0。

TSS结构如下所示

TSS结构

普通GDT描述符

GDT

TSS描述符

TSS描述

保存TSS descriptor的寄存器是TR(任务寄存器),保存指令是LTRW。任务切换示意图如下所示。

任务切换

初始化步骤

set_tss((unsigned long long)&(task0.tss));  //对应着箭头1
set_ldt((unsigned long long)&(task0.ldt));  //对应着箭头2
__asm__("ltrw  %%ax\n\t"::"a"(TSS_SEL));    //对应着箭头3
__asm__("lldt  %%ax\n\t"::"a"(LDT_SEL));    //对应着箭头4

箭头5表示现在TR的tss descriptor指向的是任务0的TSS结构。

箭头6表示现在LDTR的ldt descriptor指向的是任务0的LDT结构。

任务切换步骤

set_tss((unsigned long long)&(v->tss));   //对应着箭头7
set_ldt((unsigned long long)&(v->ldt));   //对应着箭头8
__asm__ volatile("ljmp  {1}quot; TSS_SEL_STR ", $0\n\t"); //对应着箭头9、10、11、12、13、14, TSS_SEL_STR = "0x18"

当CPU执行到指令”ljmp $0x18, $0″时,会根据0x18查找GDT表(第4项是tss descriptor),就会知道是要进行任务切换,然后执行下面的工作:

  1. 先把CPU上的寄存器的值(当前任务的上下文)保存到TR中tss descriptor指向的TSS结构中(现在TR的tss descriptor指向的任务0的TSS结构)。该步骤对应着箭头9;
  2. 把GDT表第4项的tss descriptor(在箭头7中已经换成了任务1的tss descriptor)加载到TR中。该步骤对应着箭头10;
  3. 把TR中tss descriptor指向的TSS结构的寄存器(上下文)恢复到CPU中(现在TR的tss descriptor指向的任务1的TSS结构)。该步骤对应着箭头12;
  4. CPU自动加载TSS结构中的LDT区域(是0x20),CPU查找GDT表,把第5项ldt descriptor加载到LDTR中。该步骤对应着箭头13;
  5. 执行CS:EIP所指向的指令(切换到任务1,并执行任务1)。

对任务进行管理,需要设计任务的元数据

  • 先定义TSS结构体 struct tss_struct;
  • 再定义任务结构体 struct task_struct;要管理多个任务,有两种方法,一种是使用数组,另一种是使用链表。我们使用链表来管理多个任务。
  • 定义任务不同状态(关系着任务调度)。现在定义多个任务状态:RUNNING、RUNABLE、STOPPED。
  • 定义任务的优先级。

操作任务的元数据

  • 任务结构体的初始化,初始值。
  • 定义set_tss()和set_ldt()函数。
  • 定义创建任务函数crete_task(struct task_struct *task, unsigned int function, unsigned int stack0, unsigned int stack3);
  • 创建任务函数crete_task的三个主要工作是:
    1. 初始化TSS结构。
    2. 初始化任务结构体中其他成员,比如优先级、状态、进程号等。
    3. 把新任务结构体插入到任务链表中,使得新任务可以被查询与调度。

任务0从特权级0(内核态)跳到特权级3(用户态)

特权级切换的方法是模拟中断返回(需要用到TSS和LDT):

  1. 构造中断栈
  2. 使用iret,进行中断返回。
//让任务0从特权级0退到特权级3
    //模拟中断返回
    //中断时的特权级0的堆栈是
     //
    // SS
    // ESP
    // EFLAGS  //需要设定IOPL为0x3,这样任务0才能调用kprint函数,因为kprint函数中进行了IO操作(使用out和in指令)。
               //这只是权宜之策,等以后把kprint变成系统调用了,就不需要这样设置了     
    // CS
    // EIP
    //
    // 中断返回时则把堆栈中的值赋予对应的寄存器
    __asm__("movl  %%esp,%%eax\n\t"    
        "pushl %%ecx\n\t"     -->   SS         
        "pushl %%eax\n\t"     -->   ESP 
        "pushfl\n\t"          
        "popl  %%eax\n\t"         "orl   $0x3000, %%eax\n\t" 
        "pushl %%eax\n\t"     -->  EFLAGS
        "pushl %%ebx\n\t"     -->  CS
        "pushl $1f\n\t"       -->  EIP
        "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));

使用时钟中断进行任务调度

  1. 每次时钟中断时,当前任务的时间片会变化(假如使用动态优先级算法,则优先级也会变化)。
  2. 每次时钟中断时,都会从就绪的任务中选一个任务来执行。
  3. 设置新任务的tss descriptor
  4. 设置current->state = RUNABLE; new_task->state = RUNNING; current = new_task;
  5. 任务切换”ljmp $TSS_SEL, 0x0″

kernel.h文件的源代码如下所示

#ifndef        _KERNEL_H_
#define     _KERNEL_H_

#define     GDT_ADDR    0x7d00

#define     CODE_SEL    0x08
#define     DATA_SEL    0x10

#define     KERNEL_SECT_NUMBER    1400
#define     KERNEL_STACK_BOT    0x7c00

#define     USER_CODE_SEL   0x07
#define     USER_DATA_SEL   0x0f

#define     CURRUENT_TASK_TSS    3    //在GDT表中,TSS描述符在第3项
#define     CURRUENT_TASK_LDT    4    //在GDT表中,LDT描述符在第4项

#define     TSS_SEL        0x18
#define     LDT_SEL        0x20


#define     TSS_SEL_STR        "0x18"
#define     LDT_SEL_STR        "0x20"


#endif

task.h文件的源代码如下所示

#ifndef     _TASK_H_
#define     _TASK_H_

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

#define TASK_STATE_RUNNING  0
#define TASK_STATE_RUNABLE  1
#define TASK_STATE_STOPPED  2

struct task_struct{
    struct tss_struct    tss;
    unsigned long long tss_descriptor;
    unsigned long long ldt_descriptor;
    unsigned long long ldt[2];
    int state;
    int priority;
    struct task_struct *next;
};


#define DEFAULT_LDT_CODE    0x00cffa000000ffffULL
#define DEFAULT_LDT_DATA    0x00cff2000000ffffULL

#define INITIAL_PRIO    200


extern struct task_struct task0;
extern struct task_struct *current;

unsigned long long set_tss(unsigned long long tss);
unsigned long long set_ldt(unsigned long long ldt);
unsigned long long get_tss(void);
unsigned long long get_ldt(void);

extern void create_task(struct task_struct *task, unsigned int task_function, unsigned int stack0, unsigned int stack3);
extern void scheduler(void);
#endif

task.c文件的源代码如下所示

#include "define.h"
#include "task.h"
#include "kernel.h"

static unsigned long task0_stack[1024] = {0};

struct task_struct task0 = {
    //tss
    {
    //back_link
    0,
    //esp0, ss0
    (unsigned int)&(task0_stack[1023]), DATA_SEL,
    //esp1, ss1
    0, 0,
    //esp2, ss2
    0, 0,
    //cr3
    0,
    //eip
    0,
    //eflags
    0,
    //eax,ecx,edx,ebx
    0, 0, 0, 0,
    //esp,ebp
    0, 0,
    //esi,edi
    0, 0,
    //es,cs,ss,ds,fs,gs
    USER_DATA_SEL, USER_CODE_SEL, USER_DATA_SEL, USER_DATA_SEL, USER_DATA_SEL, USER_DATA_SEL,
    //ldt
    0x20,
    //trace_iobitmap
    0x0
    },
    //tss_descriptor
    0,
    //ldt_descriptor
    0,
    //ldt[2];
    {DEFAULT_LDT_CODE, DEFAULT_LDT_DATA},
    //state
    TASK_STATE_RUNNING,    
    //priority
    INITIAL_PRIO,
    //next
    &task0   

};

struct task_struct *current = &task0;

unsigned long long set_tss(unsigned long long tss_offset)
{
    unsigned long long tss_descriptor = 0x0000890000000067ULL;
    tss_descriptor |= (tss_offset<<16)&0xffffff0000ULL;
    tss_descriptor |= (tss_offset<<32)&0xff00000000000000ULL;
    return ((unsigned long long *)GDT_ADDR)[CURRUENT_TASK_TSS] = tss_descriptor;
}


unsigned long long set_ldt(unsigned long long ldt_offset)
{
    unsigned long long ldt_descriptor = 0x000082000000000fULL;
    ldt_descriptor |= (ldt_offset<<16)&0xffffff0000ULL;
    ldt_descriptor |= (ldt_offset<<32)&0xff00000000000000ULL;
    return ((unsigned long long *)GDT_ADDR)[CURRUENT_TASK_LDT] = ldt_descriptor;
}


unsigned long long get_tss(void)
{
    return ((unsigned long long *)GDT_ADDR)[CURRUENT_TASK_TSS];
}

unsigned long long get_ldt(void)
{
    return ((unsigned long long *)GDT_ADDR)[CURRUENT_TASK_LDT];
}

void create_task(struct task_struct *task, unsigned int task_function, unsigned int stack0, unsigned int stack3)
{
    *task = task0;

    task->tss.esp0 = stack0;
    task->tss.eip = task_function;
    task->tss.eflags = 0x3202;    // I(中断位)=1,使能INTR引脚,开中断
                // IOPL(i/o优先级)=3,当任务的优先级高于或等于IOPL时,I/O指令才能顺利执行。
    task->tss.esp = stack3;

    task->priority = INITIAL_PRIO;
    task->state = TASK_STATE_STOPPED;

    //插入PCD链表中,这样新任务就能被调度了
    task->next = current->next;
    current->next = task;
    task->state = TASK_STATE_RUNABLE;

}



//时间片轮转调度算法
void scheduler(void)
{
    struct task_struct *v = current->next;

    for(; current; v = v->next)
    {
    if(v->state == TASK_STATE_RUNABLE)
        break;
    }


    if(v != current)
    {
    current->tss_descriptor = get_tss();
    current->ldt_descriptor = get_ldt();
    v->tss_descriptor = set_tss((unsigned long long)&(v->tss));
    v->ldt_descriptor = set_ldt((unsigned long long)&(v->ldt));
    current->state = TASK_STATE_RUNABLE;
    v->state = TASK_STATE_RUNNING;
    current = v;
    __asm__ volatile("ljmp  {1}quot; TSS_SEL_STR ", $0\n\t");
    }


}

main.c文件的源代码如下所示

#include "io.h"
#include "video.h"
#include "kernel.h"
#include "asm.h"
#include "idt.h"
#include "8259.h"
#include "timer.h"
#include "task.h"


static unsigned long task1_stack0[1024] = {0};
static unsigned long task1_stack3[1024] = {0};
static unsigned long task2_stack0[1024] = {0};
static unsigned long task2_stack3[1024] = {0};
static unsigned long task3_stack0[1024] = {0};
static unsigned long task3_stack3[1024] = {0};

struct task_struct task1, task2, task3;

void do_task1(void)
{
    while(1)
    {
    __asm__("incb 0xb8000+160*24+6");
    }
}

void do_task2(void)
{
    while(1)
    {
    __asm__("incb 0xb8000+160*24+8");
    }
}

void do_task3(void)
{
    while(1)
    {
    __asm__("incb 0xb8000+160*24+10");
    }
}

void test(int a, int b, int c, int d, char *ss)
{
    int i = 0;
    char str[10];
    a += b;
    b += c;
    d += c;
    for(i = 0; i < 10; i++)
    str[i] = ss[i];
    
}
int main(int argc, char **argv)
{
    char wheel[4] = {'\\', '|', '/', '-'};
    cls();
    kprint(char_attr(BLACK,GREEN),"Starting 1kOS\n");
    
    kprint(char_attr(BLACK,GREEN),"Install IDT\n");
    idt_install();


    kprint(char_attr(BLACK,GREEN),"Init 8259A\n");
    init8259();

    kprint(char_attr(BLACK,GREEN),"Init Timer\n");
    init_timer(10);
    enable_irq(0);

    kprint(char_attr(BLACK,GREEN),"Set TSS and LDT\n");
    set_tss((unsigned long long)&(task0.tss));
    set_ldt((unsigned long long)&(task0.ldt));
    __asm__("ltrw  %%ax\n\t"::"a"(TSS_SEL));
    __asm__("lldt  %%ax\n\t"::"a"(LDT_SEL));
    sti();  //关中断操作只能在特权级0上操作,在特权级3上操作会触发protectione exception错误
    
    //让任务0从特权级0退到特权级3
    //模拟中断返回
    //中断时的特权级0的堆栈是
    //
    // SS
    // ESP
    // EFLAGS  //需要设定IOPL为0x3,这样任务0才能调用kprint函数
    // CS
    // EIP
    //
    // 中断返回时则把堆栈中的值赋予对应的寄存器
    __asm__("movl  %%esp,%%eax\n\t" \   
        "pushl %%ecx\n\t" \            
        "pushl %%eax\n\t" \           
        "pushfl\n\t" \          
        "popl  %%eax\n\t" \
        "orl   $0x3000, %%eax\n\t" \
        "pushl %%eax\n\t" \
        "pushl %%ebx\n\t" \         
        "pushl $1f\n\t"  \        
        "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));

    kprint(char_attr(BLACK,GREEN),"Multiple Tasks\n");
    create_task(&task1,
        (unsigned int)do_task1,
        (unsigned int)&(task1_stack0[1023]),
        (unsigned int)&(task1_stack3[1023]));

    create_task(&task2,
        (unsigned int)do_task2,
        (unsigned int)&(task2_stack0[1023]),
        (unsigned int)&(task2_stack3[1023]));

    create_task(&task3,
        (unsigned int)do_task3,
        (unsigned int)&(task3_stack0[1023]),
        (unsigned int)&(task3_stack3[1023]));

    while(1)
    {
    __asm__ ("incb 0xb8000+160*24+0");
    }
    
    return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *