scheduler.c

一个用于学习的操作系统

/*文件名: scheduler.c
  说明:   进程调度程序
  作者:   marsinfan
  日期:   2005/12/20
*/

#include <fairysky/defs.h>
#include <fairysky/types.h>
#include <fairysky/kernel.h>
#include <asm/system.h>
#include <fairysky/string.h>
#include <fairysky/scheduler.h>

extern int printk(const char *fmt, ...);
extern int get_free_page();
int free_page(u32 addr);


#define MAX_TIME_REQUESTS   64
#define MAX_PROCESS_COUNT   64

timer_struct timer_list[MAX_TIME_REQUESTS];    //可使用的定时器
timer_struct timer_head;
timer_struct free_timer_head;

task_struct_t sleep_task_head = {{(struct list_head *)&sleep_task_head, (struct list_head *)&sleep_task_head}};

task_struct_t *pinit_task = NULL;              //可调度的进程队列，第一个就是进程0
task_struct_t *sleep_task = &sleep_task_head;//NULL;              //睡眠的调度队列
task_struct_t *current = NULL;
DESCR_SEG *gdt = (DESCR_SEG *) 0xC0000800;     //全局描述符的线性地址
u32 jiffies = 0;        //开机后的心跳数
s32 last_pid = 0;       //用于产生pid
int need_resched = 0;   //当等于1时，说明当前的进程在退到ring3时需要被调度走


//GDTR gdtr;
//全局的tss，加载tr寄存器后，不再加载，所有的进程用一个global_tss
tss_struct global_tss = {
    .link = 0,
    .esp0 = 0,
    .ss0 = 0x10,
    .esp1 = 0,
    .ss1 = 0,
    .esp2 = 0,
    .ss2 = 0,
    .cr3 = 0x00010000,
    .eip = 0,
    .eflags = 0x200L,
    .eax = 0,
    .ecx = 0,
    .edx = 0,
    .ebx = 0,
    .esp = 0,
    .ebp = 0,
    .esi = 0,
    .edi = 0,
    .es = 0x23,
    .cs = 0x1B,
    .ss = 0x23,
    .ds = 0x23,
    .fs = 0x23,
    .gs = 0x23,
    .ldtr = 0,
    .trace = 0,
    .io_map_addr = sizeof(tss_struct)
};


//设置全局描述附
static void setup_GDT_entry(DESCR_SEG *item, u32 base, u32 limit, u8 access, u8 attribs)
{
    item->base_l = base & 0xFFFF;
    item->base_m = (base >> 16) & 0xFF;
    item->base_h = base >> 24;
    item->limit = limit & 0xFFFF;
    item->attribs = attribs | ((limit >> 16) & 0x0F);
    item->access = access;
}


static void show_task(int process_nr, task_struct_t * p)
{
    int i;
    int j = PAGE_SIZE - sizeof(task_struct_t);

    printk("%d: pid=%d, state=%d, father=%d, child=%d ",
        process_nr,
        p->pid,
        p->state, p->p_parent->pid, p->p_child ? p->p_child->pid : -1);

    //printk("%d/%d chars free in kstack\n\r",i,j);
    //printk("   PC=%08X.", *(1019 + (unsigned long *) p));

    if (p->p_younger_sibling || p->p_older_sibling)  {
        printk("   Younger sib=%d, older sib=%d\n\r",
        p->p_younger_sibling ? p->p_younger_sibling->pid : -1,
        p->p_older_sibling ? p->p_older_sibling->pid : -1);
    }
        printk("\n\r");

}

void sys_show_state(void)
{
    int process_nr = 0;
    task_struct_t *tmp = NULL;

    printk("\rTask-info:\n\r");

    TASK_EACH(pinit_task, tmp) {
        show_task(++process_nr, tmp);
    }

    tmp = NULL;
    TASK_EACH(sleep_task, tmp) {
        show_task(++process_nr, tmp);
    }
}


//在进程调度前，对tss进行设置，以便再回到内核时有正确的内核堆栈地址
//此函数的参数是通过寄存器eax,ebx传递的，此函数是在宏switch_to中被jmp
#ifdef WINDOWS_CYGWIN
void _switch_to()
#else
void __switch_to()
#endif
{
    task_struct_t *prev;
    task_struct_t *next;

    //获取参数的值
    __asm__ __volatile__ (
        "movl %%eax, %0\n\t"
        "movl %%edx, %1\n\t"
        :"=m" (prev), "=m" (next)
        :
        );


    global_tss.esp0 = next->original_esp0;      //恢复内核堆栈栈顶指针
/*
    __asm__ __volatile__ ("movw %%fs, %0\n\t"
        : "=m"(prev->tss.fs)
        :);
    __asm__ __volatile__ ("movw %%gs, %0\n\t"
        : "=m"(prev->tss.gs)
        :);

    load_fs(next->tss.fs);
    load_gs(next->tss.gs);
*/
}

//这里得切换进程的地址空间
void switch_mm(task_struct_t *prev, task_struct_t *current)
{
    __asm__ __volatile__ ("movl %0, %%cr3": :"r"(current->tss.cr3));
}

//根据进程优先级进行进程切换
void scheduler()
{
    task_struct_t *prev = current;
    task_struct_t *tmp;
    s32 tmp_counter = -1;

    //如果进程处于可中断睡眠状态，先看看有没有得到信号，如果得到则把其唤醒
    TASK_EACH(sleep_task, tmp) {
        if (tmp->alarm && tmp->alarm < jiffies) {
            tmp->signal |= (1 << (SIGALRM - 1));
            tmp->alarm = 0;
        }

        if ((tmp->signal & ~tmp->signal_blocked) && (tmp->state == TASK_INTERRUPTIBLE)) {
            tmp->state = TASK_RUNNING;
            if (tmp->counter > current->counter) {   //如果被唤醒的进程更需要调度，则设置标志
                need_resched = 1;
            }
            move_wait_to_run(tmp);
        }
    }

    TASK_EACH(pinit_task, tmp) {
        if (tmp->alarm && tmp->alarm < jiffies) {
            tmp->signal |= (1 << (SIGALRM - 1));
            tmp->alarm = 0;
        }
    }

    //获取最需要调度的进程
    if ((task_struct_t *)pinit_task->list.next == pinit_task) {//如果可调度队列中只有进程0
        if (pinit_task == current) {        //如果可调度队列中只有进程0，且当前进程是进程0，则不调度
            return;
        } else {                //如果可调度队列中只有进程0，且当前进程不是进程0，则调度执行进程0
            current = pinit_task;
        }
    } else {
        for (;;) {
            //遍历可调度队列，取得最需执行的进程
            TASK_EACH(pinit_task, tmp) {
                if (tmp->counter > tmp_counter) {
                    tmp_counter = tmp->counter;
                    current = tmp;//(task_struct_t *)(tmp & 0xFFFFF000);
                }
            }

            if (tmp_counter) {  //取到了最需执行的进程，则开始调度
                break;
            }

            //所有可调度的进程的运行时间片都用完，则重新分配时间片
            TASK_EACH(pinit_task, tmp) {
                ////tmp->counter = (tmp->counter >> 1) + tmp->priority;
                tmp->counter = 15 + tmp->priority;
            }
        }
    }

    //current = (task_struct_t *) ((u32) current->list.next & 0xFFFFF000);

    //printk(" %xH", current);
    //开始切换进程
    switch_mm(prev, current);
    switch_to(prev, current, prev);
}

//初始化init进程，即进程0(这个进程是手工捏造的)
task_struct_t * init_task()
{
    task_struct_t *tmp_task = NULL;
    int index = get_free_page();
    //分配pcb空间，4k
    if (index) {
        tmp_task = (task_struct_t *) index_to_vaddr(index);
        index = get_free_page();
        //分配进程的页目录
        if (!index) {
            free_page((u32) tmp_task);     //如果失败，则释放pcb空间
            panic("init_task: get page_dir_page failed!");
        }
        INIT_LIST_HEAD(&(tmp_task->list));


        tmp_task->state = TASK_RUNNING;         //进程状态
        tmp_task->counter = 15;                 //运行时间片，对进程0来说是没有用的，只有没有其他进程可调度的情况下才会调度进程0
        tmp_task->priority = 15;                //优先级，对进程0来说也没有用的
        tmp_task->uid = tmp_task->euid = tmp_task->suid = 0;
        tmp_task->gid = tmp_task->egid = tmp_task->sgid = 0;
        tmp_task->signal = 0;                   //信号，按位
        tmp_task->signal_blocked = 0;           //被掩码的信号,位图
        tmp_task->pid = 0;                      //进程的pid
        tmp_task->pgrp = 0;                     //组id
        tmp_task->session = 0;
        tmp_task->leader = 0;
        tmp_task->p_original_parent = NULL;     //原始的父进程
        tmp_task->p_parent = NULL;              //父进程
        tmp_task->p_child = NULL;               //子进程
        tmp_task->p_younger_sibling = NULL;     //弟进程
        tmp_task->p_older_sibling = NULL;       //兄进程
        tmp_task->uid = 0;                      //用户id
        tmp_task->euid = 0;                     //有效用户id
        tmp_task->suid = 0;                     //保存的用户id，好像没有用啊
        tmp_task->gid = 0;                      //组id
        tmp_task->egid = 0;                     //有效组id
        tmp_task->sgid = 0;                     //保存的组id
        tmp_task->alarm = 0;
        tmp_task->user_time = 0;                //用户态运行时间(滴答数)
        tmp_task->system_time = 0;              //内核态运行时间(滴答数)
        //cutime,                               //子进程用户态运行时间(滴答数)，好像没有用啊
        //cstime,                               //子进程内核态运行时间(滴答数)，好像没有用啊