Category Archives: 1kos

第25章 实现进程间通信(IPC)

目标:实现系统调用

int send_msg(int pid, struct msg *msg);

int receive_msg(struct msg *msg);

消息结构如下所示:

#define TASK_MSG_NR    10
struct msg{
    int pid;        //消息的发送者
    int type;
    int size;
    union{
    char c;
    int i;
    long l;
    void *p;
    }x;
};

struct msgbox{
    unsigned long msg_nr;  //信箱中有多少条信息
    int msg_start;
    int msg_end;
    struct msg box[TASK_MSG_NR];  //循环数组
};

#define DEFAULT_STACK_SIZE  4096
struct task_struct{
    struct tss_struct    tss;
    unsigned long long tss_descriptor;
    unsigned long long ldt_descriptor;
    unsigned long long ldt[2];
    unsigned int task_function;
    void * stack0;
    void * stack3;
    unsigned int stack0_size;
    unsigned int stack3_size;
    int state;
    int priority;
    int time_slice;
    int pid;
    int ppid;
    struct task_struct *next, *prev;
    struct task_struct *hnext, *hprev;
    struct prio_array *py;
    struct timer timer;
    struct msgbox msgbox;
};

发送消息函数和接收消息函数如下所示

int sys_send_msg(int pid, struct msg *msg)
{
    
    int ret = 0;
    struct task_struct *task = NULL;

    cli();
    if(pid < 0 || !msg)
    {
      ret = 1;
      goto end;
    }
    
    //查询是否存在这个pid的任务
    task = query_task_from_hash(pid);
    if(!task)
    {
      ret = 2;
      goto end;
    }

    //查看任务的信箱是否有空位
    if(task->msgbox.msg_nr < TASK_MSG_NR) //有空位
    {
      //复制消息到任务的信箱的空位中
      task->msgbox.msg_end = ++(task->msgbox.msg_end)%TASK_MSG_NR;
      task->msgbox.box[task->msgbox.msg_end] = *msg;

      //消息数目增1
      ++(task->msgbox.msg_nr); 
    }
    else //无空位
    {
      ret = 3;
      goto end;
    }
end:
    sti();
    return ret;
}


int sys_receive_msg(struct msg *msg)
{
    int ret = 0;

    cli();
    if(!msg)
    {
      ret = 1;
      goto end;
    }

    //查看任务的信箱是否有消息
    if(current->msgbox.msg_nr > 0) //有消息
    {
      //复制任务信箱中的消息到msg中
      current->msgbox.msg_start = ++(current->msgbox.msg_start)%TASK_MSG_NR;
      *msg =     current->msgbox.box[current->msgbox.msg_start];

      //消息数目减1
      --(current->msgbox.msg_nr); 
    }
    else //无消息
    {
      ret = 2;
      goto end;
    }
end:
    sti();
    return ret;
}

第24章 任务中定时器的设计与实现

目标:实现定时器功能,实现系统调用sleep。

定时器的定义如下所示,系统使用定时器链表管理定时器。

struct timer{
    struct task_struct *task;
    struct timer *next, *prev;
    int time_slice;
};

struct timer_list{
    unsigned long timer_nr;
    struct timer *head, *tail;
};


任务调用sleep(int ms)函数时,会在定时器链表上插入一个定时器,然后任务挂起。每次时钟中断,内核都会检查定时器链表上的定时器,假如定时器到点,则删除定时器,并唤醒与该定时器关联的任务。定时器插入算法就是遍历链表,算法复杂度为O(n)。定时器检查算法的复杂度为O(1)。

假设

  • 任务A睡20秒
  • 任务B睡5秒
  • 任务C睡9秒
  • 任务D睡2秒
  • 任务E睡14秒
  • 任务F睡40秒
任务 D B C E A F
时刻 2 5 9 14 20 40
定时器的时间长度值 2 3 4 5 6 20

也就是在定时器链表上,第1个定时器的时间值是2秒,对应的任务是D;第2个定时器的时间值是3秒,对应的任务是B;

定时器插入函数如下所示

//把定时器插入到定时器链表中
//每个定时器代表一段距离,表示离左边定时器的时间片距离
struct timer * add_timer(struct timer *t)
{
   if(!t)
      return NULL;

   //当定时器链表为空时
   if(task_timer_list.head == NULL)
   {
    task_timer_list.head = task_timer_list.tail = t;
    ++task_timer_list.timer_nr;
    return t;
   }

   //当定时器不为空时
   struct timer *p = NULL;
   p = task_timer_list.head;
   while(p && p->time_slice <= t->time_slice)
   {
    t->time_slice -= p->time_slice;
    p = p->next;
   }

   if(p == task_timer_list.head) //插在最前面
   {
        p->time_slice -= t->time_slice;

    p->prev = t;
    t->next = p;
    t->prev = NULL;
    task_timer_list.head = t;
   }
   else if(p == NULL) //插在最后面
   {
    task_timer_list.tail->next = t;
    t->prev = task_timer_list.tail;
    t->next = NULL;
    task_timer_list.tail = t;
   }
   else  //插在中间
   {
        p->time_slice -= t->time_slice;
    
    p->prev->next = t;
    t->next = p;
    t->prev = p->prev;
    p->prev = t;    
   }

   ++task_timer_list.timer_nr;

   return t;
}

定时器检查函数如下所示

void check_timer()
{

    struct timer *p = NULL , *tmp = NULL;
    p = task_timer_list.head;
    //检查定时器链表
    if(p)    //链表上有定时器
    {
    //定时器到点
    if(--(p->time_slice) == 0)
    {
        //可能有多个定时器到点
        while(p && p->time_slice == 0)
        {
    
        if(p->next == NULL)    //只剩下一个定时器
        {
            task_timer_list.head = task_timer_list.tail = NULL;
        }
        else     //剩下多个定时器
        {
           task_timer_list.head = p->next;
           task_timer_list.head->prev = NULL; 
        }

            
        //定时器的任务为空可能是因为该任务已被删除(sys_remove_task)
        //定时器指定的任务有可能已经被其他任务唤醒了(使用resume_task系统调用)
        if(p->task && p->task->state == TASK_STATE_SUSPEND)
        {
            //从挂起队列中移除任务
            remove_task_from_suspend(p->task);

            //把任务插入到运行队列
            insert_task_to_running(p->task, cpu0.expired);
        }
            
        tmp = p;
        p = p->next;
        
        //初始化定时器
        init_task_timer(tmp);
        }
    }


    }
}

timer.c源代码如下所示

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


void init_timer(unsigned int hz)
{
    unsigned int divisor = CLOCK_RATE/hz;
    outportb(0x43, 0x36);        //选择计数器0,输出模式3
    outportb(0x40, divisor&0xff);   //把初始值的低字节写入LSB中
    outportb(0x40, (divisor>>8)&0xff);    //把初始值的高字节写入MSB中
}

volatile unsigned long  timer_ticks = 0;
void do_timer(void)
{
    timer_ticks++;
    //检查定时器链表
    check_timer();

    //管理当前任务的时间片
    manage_time_slice();

    outportb(M_PIC, EOI);   //告诉PIC1,中断处理函数已经结束,可以处理新来的中断。
                //因为定时器是连接到PIC1的IRQ0上,所以不许要通知PIC2
    //调度
    scheduler();
}

最终的task.c源代码如下所示

#include "define.h"
#include "task.h"
#include "kernel.h"
#include "asm.h"
#include "video.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},
    //task_function
    0,
    //stack0
    NULL,
    //stack3
    NULL,
    //stack0_size
    0,
    //stack3_size
    0,
    //state
    TASK_STATE_RUNNING,    
    //priority
    0,
    //time_slice
    INITIAL_TIME_SLICE,
    //pid
    0,
    //ppid
    0,
    //next
    NULL,
    //prev
    NULL,
    //hnext
    NULL,
    //hprev
    NULL,
    //prio_array *
    NULL,
    //timer
    {
    //strcut task_struct *task
    NULL,
    //struct timer *next, *prev
    NULL,NULL,
    //int slice
    0
    },
    //msgbox
    {
    //msg_nr
    0,
    //msg_start
    0,
    //msg_end
    0,
    //box
    {}
    }
};

struct task_struct *current = &task0;
struct run cpu0;

static int newpid = 0;

static int get_newpid()
{
    return ++newpid;
}

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 init_task_timer(struct timer *timer)
{
    if(!timer)
    return NULL;
    timer->task = NULL;  //表示当前定时器非使用状态
    timer->next = timer->prev = NULL;
    timer->time_slice = 0;
}

struct timer_list task_timer_list = {0, NULL, NULL};

//初始化定时器链表
void init_task_timer_list()
{
    task_timer_list.timer_nr = 0;
    task_timer_list.head = task_timer_list.tail = NULL;
}

//把定时器插入到定时器链表中
//每个定时器代表一段距离,表示离左边定时器的时间片距离
struct timer * add_timer(struct timer *t)
{
   if(!t)
      return NULL;

   //当定时器链表为空时
   if(task_timer_list.head == NULL)
   {
    task_timer_list.head = task_timer_list.tail = t;
    ++task_timer_list.timer_nr;
    return t;
   }

   //当定时器不为空时
   struct timer *p = NULL;
   p = task_timer_list.head;
   while(p && p->time_slice <= t->time_slice)
   {
    t->time_slice -= p->time_slice;
    p = p->next;
   }

   if(p == task_timer_list.head) //插在最前面
   {
        p->time_slice -= t->time_slice;

    p->prev = t;
    t->next = p;
    t->prev = NULL;
    task_timer_list.head = t;
   }
   else if(p == NULL) //插在最后面
   {
    task_timer_list.tail->next = t;
    t->prev = task_timer_list.tail;
    t->next = NULL;
    task_timer_list.tail = t;
   }
   else  //插在中间
   {
        p->time_slice -= t->time_slice;
    
    p->prev->next = t;
    t->next = p;
    t->prev = p->prev;
    p->prev = t;    
   }

   ++task_timer_list.timer_nr;

   return t;
}


//从定时器链表上移除指定任务的定时器
//被sys_delete_task sys_resume_task sys_suspend_task 函数调用
void remove_task_timer(struct task_struct *task)
{
    if(!task)
    return ;
    if(!(task->timer.task))
    return ;
    //定时器在链表中的位置有三种:表头;表尾;表中间
    if(task_timer_list.head == &(task->timer)) //表头
    {
    if(task_timer_list.tail == &(task->timer))
    {
        task_timer_list.head = task_timer_list.tail = NULL;
    }
    else
    {
        task_timer_list.head = task->timer.next;
        task_timer_list.head->prev = NULL;
        task_timer_list.head->time_slice += task->timer.time_slice;  //这条语句是必须的
    }

    }
    else if(task_timer_list.tail == &(task->timer))  //表尾
    {
    task_timer_list.tail = task->timer.prev;
    task_timer_list.tail->next = NULL;
    }
    else  //表中间
    {
    task->timer.prev->next = task->timer.next;
    task->timer.next->prev = task->timer.prev;
    task->timer.next->time_slice += task->timer.time_slice;  //这条语句是必须的
    }

    init_task_timer(&(task->timer));
}

//添加任务到任务链表尾部
void add_task(struct list_pcd * list, struct task_struct *task)
{
    
    if(list->head == NULL) //队列为空
    {
    list->head = list->tail = task;
    task->next = task->prev = NULL;
    }
    else    //队列不为空
    {
    list->tail->next = task;
    task->prev = list->tail;
    task->next = NULL;
    list->tail = task;
    }
}


//从任务链表中删除任务
void remove_task(struct list_pcd * list, struct task_struct *task)
{

    //该任务在队列中有三种情况:队头;队尾;队中
    if(list->head == task)  //队头
    {
    if(task->next)//队列有多个任务
    {
        list->head = task->next;
        list->head->prev = NULL;
    }
    else //队列只有一个任务
    {
        list->head = list->tail = NULL;
    }

    }
    else if(list->tail == task) //队尾
    {
    if(task->prev) //队列有多个任务
    {
        list->tail = task->prev;
        list->tail->next = NULL;
    }
    else //队列只有一个任务
    {
        list->head = list->tail = NULL;
    }
    }
    else //队中
    {
    task->prev->next = task->next;
    task->next->prev = task->prev;
    }    

}


//把任务插入优先级数组中
//被sys_create_task()和manage_time_slice()函数调用
//本函数访问共享资源cpu0,因此要保证调用本函数时不能被打断
void insert_task_to_running(struct task_struct *task, struct prio_array *py)
{

    //都是把任务插在链表尾部
    add_task(py->queue + task->priority, task);

    //更新任务结构
    task->py = py;
    task->state = TASK_STATE_RUNNING;

    //更新优先级数组
    ++(py->task_nr);
    py->bitmap |= (1 << task->priority);
}

//把任务从优先级数组上移除
void remove_task_from_running(struct task_struct* task)
{
    if(task->state != TASK_STATE_RUNNING)
    return;
    struct list_pcd *list = NULL;
    list = (struct list_pcd*)(task->py->queue + task->priority);
    //把任务从运行队列中移除
    remove_task(list, task);
    
    
    //更新优先级数组
    --(task->py->task_nr);

    //假如任务所在的优先级链表已空,则更新优先级位图
    if(list->head == NULL)
    task->py->bitmap &= ~(1 << task->priority);    
}

//初始化CPU0,把任务0插入active优先级数组中
void init_cpu0(void)
{
    struct list_pcd * list_pcd_ptr = NULL;
    int i = 0, j = 0;
    for(i = 0; i < 2; i++)
    {
    cpu0.pa[i].task_nr = 0;
    cpu0.pa[i].bitmap = 0x0;
    for(j = 0; j < PRIO_NR; j++)
    {
        cpu0.pa[i].queue[j].head = NULL;
        cpu0.pa[i].queue[j].tail = NULL;
    }
    }
    
    cpu0.active = cpu0.pa;
    cpu0.expired = cpu0.pa+1;
    
    //把任务0插入active优先级数组中去,一定要插入active优先级数组,这很重要
    insert_task_to_running(&task0, cpu0.active);
    
    //把任务0插到任务HASH表中去
    add_task_to_hash(&task0);
}

void init_tasks(void)
{
    //设置GDT中的TSS和LDT
    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));

    //初始化CPU0,把任务0插入expired优先级数组中
    init_cpu0();

    //初始化定时器链表
    init_task_timer_list();

}

//系统调用,创建新的任务
//返回新任务的PID
int  sys_create_task(unsigned int task_function, unsigned int stack0_size, unsigned int stack3_size)
{
    int pid = 0;
    struct task_struct *task = NULL;
    void *stack0 = NULL, *stack3 = NULL;

    stack0_size = (stack0_size ? stack0_size : DEFAULT_STACK_SIZE);
    stack3_size = (stack3_size ? stack3_size : DEFAULT_STACK_SIZE);

    task = (struct task_struct *)malloc(sizeof(struct task_struct));
    stack0 = malloc(stack0_size);
    stack3 = malloc(stack3_size);
    if(!task || !stack0 || !stack3)
    {
    free(task);
    free(stack0);
    free(stack3);
    return -1;
    }

    *task = task0;

    task->tss.esp0 = stack0 + stack0_size;
    task->tss.eip = task_function;
    //task->tss.eflags = 0x3202;    // I(中断位)=1,使能INTR引脚,开中断
                        // IOPL(i/o优先级)=3,当任务的优先级高于或等于IOPL时,I/O指令才能顺利执行。
    task->tss.eflags = 0x202;        //不需要设置IOPL了,通过系统调用执行I/O指令
    task->tss.esp = stack3 + stack3_size;

    task->task_function = task_function;
    task->stack0 = stack0 + stack0_size;
    task->stack3 = stack3 + stack3_size;
    task->stack0_size = stack0_size;
    task->stack3_size = stack3_size;

    task->state = TASK_STATE_RUNNING;
    //设置时间片
    task->time_slice = INITIAL_TIME_SLICE;

    //设置PID和PPID
    pid = task->pid = get_newpid();
    task->ppid = current->pid;

    //设置优先级
    task->priority = ( task->pid % PRIO_NR);
    //task->priority = INITIAL_PRIO;

    //初始化定时器
    init_task_timer(&(task->timer));

    //初始化任务的信箱
    task->msgbox.msg_nr = 0;
    task->msgbox.msg_start = task->msgbox.msg_end = 0;

    //插入到cpu0中的expired优先级数组中
    cli();
    insert_task_to_running(task, cpu0.expired);
    
    //插到任务HASH表中
    add_task_to_hash(task);
    sti();


    return pid;
}

//计算当前任务的时间片,假如当前任务的时间片用完,则从新分配时间片,并把任务插入到expired优先级数组中
//这里存在一个假设,即当前任务是所在优先级队列的第一个任务;
//本函数需要访问共享资源cpu0,因此需要保证该调用该函数时不能被打断
void manage_time_slice(void)
{
    struct list_pcd * list_pcd_ptr = NULL;
    list_pcd_ptr = cpu0.active->queue + current->priority;  //指向当前任务所在的优先级队列

    //计算当前任务的时间片
    if(--current->time_slice > 0) //当前任务还有时间片
    {
    if(list_pcd_ptr->head != list_pcd_ptr->tail) //该优先级上还有>1个任务
    {
        //轮转算法,把当前任务插到队尾
        list_pcd_ptr->head = current->next;
        list_pcd_ptr->tail->next = current;
        current->prev = list_pcd_ptr->tail;
        list_pcd_ptr->tail = current;
        current->next = NULL;
        list_pcd_ptr->head->prev = NULL;
    }
    }
    else  //当前任务没有时间片,从队列中摘掉该任务
    {
    //摘取当前任务
    if(list_pcd_ptr->head != list_pcd_ptr->tail) //该优先级上还有>1个任务
    {
        list_pcd_ptr->head = current->next;
        list_pcd_ptr->head->prev = NULL;
    }
    else    //该优先级上只有当前任务
    {
        list_pcd_ptr->head = list_pcd_ptr->tail = NULL;
        //更新优先级数组位图
        cpu0.active->bitmap &= ~(1 << current->priority);
    }

    //更替新优先级数组
    --(cpu0.active->task_nr);
    //重新给任务分配时间片
    current->time_slice = INITIAL_TIME_SLICE;
    //把任务插入expired优先级数组中
    insert_task_to_running(current,cpu0.expired);
    }


}

static inline unsigned long  sched_find_first_bit(const unsigned long word)
{
    unsigned long index = word;
    __asm__ ("bsfl %1, %0 \n\t" \
    :"=r"(index):"rm"(index));
    return index;
}

//时间片轮转调度算法
//本函数需要访问共享资源cpu0,因此需要保证该调用该函数时不能被打断,该函数必须在临界区内,不能开中断。
//而且scheduler调用的函数也不能开中断
void scheduler(void)
{
    struct task_struct *v = NULL;
    struct list_pcd * list_pcd_ptr = NULL;
    struct prio_array *py = NULL;
    unsigned long index = 0;

    //加入active优先级数组中没有可运行的任务,则调换active和expired的指针。

    py = cpu0.active;
    if(py->task_nr == 0)
    {
    cpu0.active = cpu0.expired;
    cpu0.expired = py;
    py = cpu0.active;
    }

    if(py->task_nr == 0)
    {
        sys_kprint(char_attr(BLACK,RED),"\tScheduler Error: no running task in priority array.\n");
        while(1);
    }

    //在active优先级数组中找到具有任务的优先级最高的任务队列,取得任务队列的头个任务
    index = sched_find_first_bit(py->bitmap);
    list_pcd_ptr = py->queue + index;
    v = list_pcd_ptr->head;


    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 = v;
    __asm__ volatile("ljmp  {1}quot; TSS_SEL_STR ", $0\n\t");
    }
}

//挂起任务队列
struct task_list suspend_tasks;
//死亡任务队列
struct task_list  dead_tasks;


void init_suspend_tasks()
{
    suspend_tasks.task_nr = 0;
    suspend_tasks.list.head = NULL;
    suspend_tasks.list.tail = NULL;
}

void init_dead_tasks()
{
    dead_tasks.task_nr = 0;
    dead_tasks.list.head = NULL;
    dead_tasks.list.tail = NULL;
}

//插入任务到挂起任务队列队尾
void insert_task_to_suspend(struct task_struct *task)
{
    task->state = TASK_STATE_SUSPEND;
    add_task(&(suspend_tasks.list), task);
    ++suspend_tasks.task_nr;
}






//插入任务到死亡任务队列队尾
void insert_task_to_dead(struct task_struct *task)
{

    task->state = TASK_STATE_DEAD;
    add_task(&(dead_tasks.list), task);
    ++dead_tasks.task_nr;

}

//从挂起任务队列中删除指定的任务
void remove_task_from_suspend(struct task_struct *task)
{
    if(task->state != TASK_STATE_SUSPEND)
    return ;
    remove_task(&(suspend_tasks.list), task);
    --suspend_tasks.task_nr;
}

void remove_task_from_dead(struct task_struct *task)
{
    if(task->state != TASK_STATE_DEAD)
    return ;
    remove_task(&(dead_tasks.list), task);
    --dead_tasks.task_nr;
}


struct task_hash tasks_hash;
void init_tasks_hash()
{
    tasks_hash.task_nr = 0;
    int i = 0;
    for(i = 0; i < TASK_HASH_NR;i++)
    {
    tasks_hash.table[i].head = tasks_hash.table[i].tail = NULL;
    }
}

void add_task_to_hash(struct task_struct *task)
{
    
    struct list_pcd *list = NULL;
    list = &(tasks_hash.table[task->pid%TASK_HASH_NR]);
    if(list->head == NULL) //队列为空
    {
    list->head = list->tail = task;
    task->hnext = task->hprev = NULL;
    }
    else    //队列不为空
    {
    list->tail->hnext = task;
    task->hprev = list->tail;
    task->hnext = NULL;
    list->tail = task;
    }

    ++tasks_hash.task_nr;
}

void remove_task_from_hash(struct task_struct *task)
{
    struct list_pcd *list = NULL;
    list = &(tasks_hash.table[task->pid%TASK_HASH_NR]);
    //该任务在队列中有三种情况:队头;队尾;队中
    if(list->head == task)  //队头
    {
    if(task->hnext)//队列有多个任务
    {
        list->head = task->hnext;
        list->head->hprev = NULL;
    }
    else //队列只有一个任务
    {
        list->head = list->tail = NULL;
    }

    }
    else if(list->tail == task) //队尾
    {
    if(task->hprev) //队列有多个任务
    {
        list->tail = task->hprev;
        list->tail->hnext = NULL;
    }
    else //队列只有一个任务
    {
        list->head = list->tail = NULL;
    }
    }
    else //队中
    {
    task->hprev->hnext = task->hnext;
    task->hnext->hprev = task->hprev;
    }    
    --tasks_hash.task_nr;    
}

struct task_struct * query_task_from_hash(int pid)
{
    struct task_struct *t;
    t = tasks_hash.table[pid%TASK_HASH_NR].head;
    for(; t; t = t->hnext )
    {
    if(t->pid == pid)
        return t;    
    }

    return NULL;
}

//挂起任务
//该函数访问共享资源,因此需要关中断
int sys_suspend_task(int pid)
{
    int ret = 0;
    struct task_struct *task = NULL;

    cli();
    if(pid < 0)
    {
    ret = 1;
    goto end;
    }
    
    //查询是否存在这个pid的任务
    task = query_task_from_hash(pid);
    if(!task)
    {
    ret = 2;
    goto end;
    }
    
    //判断该任务的状态,是否是RUNNING态
    if(task->state != TASK_STATE_RUNNING)
    {
    ret = 3;
    goto end;
    }

    //把该任务从运行队列移除
    remove_task_from_running(task);    
    
    //把该任务添加到挂起队列
    insert_task_to_suspend(task);
    
    //判断当前运行队列是否为空,假如为空则唤醒任务0
    if(cpu0.active->task_nr == 0 && cpu0.expired->task_nr == 0)
    {
    //把该任务从挂起队列删除
    remove_task_from_suspend(&task0);    

    //删除任务0上的定时器
    remove_task_timer(&task0);
    
        //把该任务添加到运行队列
    insert_task_to_running(&task0, cpu0.expired);

    }
    //判断该PID是否是当前任务的PID
    if(task == current)
    {
    scheduler();
    }
    
end:
    sti();
    return ret;
}

//把任务从挂起态唤醒
//该函数访问共享资源,因此需要关中断
int sys_resume_task(int pid)
{
    int ret = 0;
    struct task_struct *task = NULL;

    cli();
    if(pid < 0)
    {
    ret = 1;
    goto end;
    }
    
    //查询是否存在这个pid的任务
    task = query_task_from_hash(pid);
    if(!task)
    {
    ret = 2;
    goto end;
    }
    
    //判断该任务的状态,是否是SUSPEND态
    if(task->state != TASK_STATE_SUSPEND)
    {
    ret = 3;
    goto end;
    }

    //把该任务从挂起队列删除
    remove_task_from_suspend(task);    

    //删除任务上的定时器
    remove_task_timer(task);
    
    //把该任务添加到运行队列
    insert_task_to_running(task, cpu0.expired);
    
    
end:
    sti();
    return ret;
}


//删除任务
//该函数访问共享资源,因此需要关中断
int sys_delete_task(int pid)
{
    int ret = 0;
    struct task_struct *task = NULL;

    cli();
    if(pid <= 0)  //不能删除任务0,因为任务0有回收死亡任务的作用  
    {
    ret = 1;
    goto end;
    }
    
    //查询是否存在这个pid的任务
    task = query_task_from_hash(pid);
    if(!task)
    {
    ret = 2;
    goto end;
    }
    
    //判断该任务的状态
    switch(task->state)
    {
    case TASK_STATE_RUNNING:
        //把该任务从运行队列移除
        remove_task_from_running(task);    
        break;

    case TASK_STATE_SUSPEND:
        //把该任务从挂起队列删除
        remove_task_from_suspend(task);
        break;

    case TASK_STATE_DEAD:
        ret = 3;
        goto end;
        break;

    default:
        break;
    }
    

    //删除该任务上的定时器
    remove_task_timer(task);

    //把该任务添加到死亡队列
    insert_task_to_dead(task);


    //判断当前运行队列是否为空,假如为空则唤醒任务0
    if(cpu0.active->task_nr == 0 && cpu0.expired->task_nr == 0)
    {
    //把该任务从挂起队列删除
    remove_task_from_suspend(&task0);    
    
    //删除任务0上的定时器
    remove_task_timer(&task0);

        //把该任务添加到运行队列
    insert_task_to_running(&task0, cpu0.expired);

    }
    
    //判断该PID是否是当前任务的PID
    if(task == current)
    {
    scheduler();
    }
    
end:
    sti();
    return ret;
}



//移除死亡任务,从任务HASH表上删除,并释放任务所占的资源(比如内存)
//该函数访问共享资源,因此需要关中断
int sys_clear_dead_task()
{
    //关中断
    cli();

    int ret = 0;    
    //查看死亡队列是否为空
    if(dead_tasks.list.head == NULL)
    {
    ret = 1;
    goto end;
    }

    //遍历死亡队列
    struct task_struct *p = dead_tasks.list.head;
    struct task_struct *tmp = NULL;
    while(p)
    {
    printf("clear dead task pid=%d\n", p->pid);
    //从hash表中移除该任务
    remove_task_from_hash(p);

    //从死亡队列中移除该任务
    remove_task_from_dead(p);
    
    //回收死亡任务所占的资源
    //回收内存
    free((void*)(p->stack0 - p->stack0_size));
    free((void*)(p->stack3 - p->stack3_size));
    tmp = p;
    p = p->next;
    free((void*)tmp);
    }

end:

    //开中断
    sti();
    return ret;
}



//睡眠函数,已ms为单位 1s = 1000ms
//参数ms == 0时表示该任务需要挂起,然后等待其他任务唤醒
int sys_sleep(int ms)
{
    int ret = 0;
    if(ms < 0)
        return 1;

    //先把睡眠时间转换为时间片
    int time_slice = 0;
    time_slice = ms*HZ/1000;
    if(time_slice == 0)
    time_slice = 1;

    //初始化定时器
    current->timer.task = current;
    current->timer.next = current->timer.prev = NULL;
    current->timer.time_slice = time_slice;

    //关中断
    cli();

    //把定时器插入定时器链表
    add_timer(&(current->timer));

    //调用sys_suspend_task函数,把自己挂起
    ret = sys_suspend_task(current->pid);

    //开中断
    sti();

    return ret;
}

void check_timer()
{

    struct timer *p = NULL , *tmp = NULL;
    p = task_timer_list.head;
    //检查定时器链表
    if(p)    //链表上有定时器
    {
    //定时器到点
    if(--(p->time_slice) == 0)
    {
        //可能有多个定时器到点
        while(p && p->time_slice == 0)
        {
    
        if(p->next == NULL)    //只剩下一个定时器
        {
            task_timer_list.head = task_timer_list.tail = NULL;
        }
        else     //剩下多个定时器
        {
           task_timer_list.head = p->next;
           task_timer_list.head->prev = NULL; 
        }

            
        //定时器的任务为空可能是因为该任务已被删除(sys_remove_task)
        //定时器指定的任务有可能已经被其他任务唤醒了(使用resume_task系统调用)
        if(p->task && p->task->state == TASK_STATE_SUSPEND)
        {
            //从挂起队列中移除任务
            remove_task_from_suspend(p->task);

            //把任务插入到运行队列
            insert_task_to_running(p->task, cpu0.expired);
        }
            
        tmp = p;
        p = p->next;
        
        //初始化定时器
        init_task_timer(tmp);
        }
    }


    }
}


int sys_send_msg(int pid, struct msg *msg)
{
    
    int ret = 0;
    struct task_struct *task = NULL;

    cli();
    if(pid < 0 || !msg)
    {
    ret = 1;
    goto end;
    }
    
    //查询是否存在这个pid的任务
    task = query_task_from_hash(pid);
    if(!task)
    {
    ret = 2;
    goto end;
    }

    //查看任务的信箱是否有空位
    if(task->msgbox.msg_nr < TASK_MSG_NR) //有空位
    {
    //复制消息到任务的信箱的空位中
    task->msgbox.msg_end = ++(task->msgbox.msg_end)%TASK_MSG_NR;
    task->msgbox.box[task->msgbox.msg_end] = *msg;

    //消息数目增1
    ++(task->msgbox.msg_nr); 
    }
    else //无空位
    {
    ret = 3;
    goto end;
    }
end:
    sti();
    return ret;
}


int sys_receive_msg(struct msg *msg)
{
    int ret = 0;

    cli();
    if(!msg)
    {
    ret = 1;
    goto end;
    }

    //查看任务的信箱是否有消息
    if(current->msgbox.msg_nr > 0) //有消息
    {
    //复制任务信箱中的消息到msg中
    current->msgbox.msg_start = ++(current->msgbox.msg_start)%TASK_MSG_NR;
        *msg =     current->msgbox.box[current->msgbox.msg_start];

    //消息数目减1
    --(current->msgbox.msg_nr); 
    }
    else //无消息
    {
    ret = 2;
    goto end;
    }
end:
    sti();
    return ret;
}

第23章 扩展任务管理模块

  1. 增加任务的HASH表,HASH值是任务的PID,这样通过任务的PID就能查找到任务的task_struct。
  2. 增加任务挂起队列、死亡队列。

    • 运行态的任务在运行队列。
    • 被挂起的任务在挂起队列。
    • 被杀死的任务在死亡队列。
  3. 增加任务挂起函数、任务唤醒函数、任务杀死函数、任务清理函数。并增加相应的系统调用。

    • sys_suspend_task把在运行队列上的任务移动到挂起队列。
    • sys_resume_task把在挂起队列上的任务移动到运行队列。
    • sys_delete_task把在运行队列或挂起队列上的任务移动到死亡队列。
    • sys_clear_task清理死亡队列上的任务,并回收资源。

在操作系统中,双向链表用处很多,因此需要设计好双向链表,重用代码。

对任务管理模块的扩展都在task.c文件中,源代码请看 http://blog.csdn.net/metaxen/article/details/6747631。

第22章 系统时间(RTC编程)

取得当前系统时间的方法是直接访问RTC芯片。

RTC芯片可以通过0x70和0x71端口直接访问。0x70是选址寄存器,0x71是数据寄存器。

Addr Function

==== =========================================

** clock/calendar

00 current second for real-time clock

01 alarm second

02 current minute

04 current hour

05 alarm hour

06 current day of week (1=Sunday)

07 current date of month

08 current month

09 current year (final two digits; eg, 93)

rtc.h源代码如下所示

#ifndef _RTC_H_
#define _RTC_H_

#define RTC_REG_ADDR    0x70    //寻址寄存器
#define RTC_REG_VALUE    0x71    //内容寄存器

#define SECOND_REG    0x0
#define MINUTE_REG    0x2
#define HOUR_REG    0x4
#define DAY_WEEK_REG    0x6
#define DAY_MONTH_REG    0x7
#define MONTH_REG    0x8
#define YEAR_REG    0x9

void localtime();
#endif

rtc.c源代码如下所示

#include "io.h"
#include "rtc.h"
#include "video.h"

unsigned char get_second()
{
    outportb(RTC_REG_ADDR, SECOND_REG);
    return inportb(RTC_REG_VALUE);    
}

unsigned char get_minute()
{
    outportb(RTC_REG_ADDR, MINUTE_REG);
    return inportb(RTC_REG_VALUE);    
}

unsigned char get_hour()
{
    outportb(RTC_REG_ADDR, HOUR_REG);
    return inportb(RTC_REG_VALUE);    
}
unsigned char get_week_day()
{
    outportb(RTC_REG_ADDR, DAY_WEEK_REG);
    return inportb(RTC_REG_VALUE);    
}
unsigned char get_month_day()
{
    outportb(RTC_REG_ADDR, DAY_MONTH_REG);
    return inportb(RTC_REG_VALUE);    
}
unsigned char get_month()
{
    outportb(RTC_REG_ADDR, MONTH_REG);
    return inportb(RTC_REG_VALUE);    
}
unsigned char get_year()
{
    outportb(RTC_REG_ADDR, YEAR_REG);
    return inportb(RTC_REG_VALUE);    
}

void localtime()
{
    unsigned char s,m,h,dw,dm,mm,y;
    s = m = h = dw = dm = m = y = 0;

    s = get_second();
    m = get_minute();
    h = get_hour();
    dw = get_week_day();
    dm = get_month_day();
    mm = get_month();
    y = get_year();

    printf("20%x-%x-%x  %x  %x:%x:%x\n", y,mm,dm, dw, h,m,s);
}

第21章 内存管理的设计与实现

内存管理的目标是提供:

内核函数:void *sys_malloc(unsigned long size); void *sys_free(void *);

系统调用函数 void * malloc(unsigned long size); void * free(void *);

内存管理:

  1. 发现资源
  2. 监控资源–元数据记录资源的属性和标识
  3. 分配资源–修改元数据,返回资源的标识
  4. 回收资源–修改元数据

内存的元数据

  1. 怎么设计元数据

    • 多种格式

      • 数组 — 方便查找和分配(数组元素是链表,该链表中的内存大小都是一样的)
      • 链表 — 方便分配和回收
      • hash表
    • 多角度

      • 内存起始地址
      • 内存大小
    • 多维度

2、如何存取元数据

* 不同格式的元数据造成元数据的大小、元数据的访问方式、元数据的操作都不一样
* 元数据存放的位置
* 访问(共享、竞争)

设计思路:

内存结构如下所示(mem.h源代码)

#ifndef        _MEM_H_
#define     _MEM_H_

typedef struct mem{
    struct mem *next, *prev, *hnext, *hprev;    //在未分配内存链表上是双向链表,在HASH表上是双向链表
    unsigned long size;
    unsigned long flag; //flag=0表示未分配,flag=1表示已分配
}mem_t;

#define     MEM_FREE    0x0
#define     MEM_USED    0x1




void init_mem(void);

void *sys_malloc(unsigned long size);

void *sys_free(void *addr);

#endif

内存元数据和它所描述的内存放在一起。假设OS刚启动时有63M(1M~64M)的空闲内存,要初始化内存管理。

free_mem_head = (mem_t *)1024*1024;
free_mem_head->hnext = free_mem_head->next = free_mem_head->hprev = free_mem_head->prev = NULL;
free_mem_head->size = 63*1024*1024 - sizeof(mem_t);
free_mem_head->flag = MEM_FREE;

内存分配算法是:

  1. 查找合适大小的内存,并分配

内存回收算法是:

  1. 回收内存,合并相邻内存

具体算法可以查看

http://www.nondot.org/sabre/os/files/MemManagement/LEA.html

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

#include "define.h"
#include "mem.h"
#include "kernel.h"
#include "video.h"
#include "mutex.h"

//地址方位描述符结构 Address Range Descriptor Structure
struct ARDS{
    unsigned long base_addr_low;
    unsigned long base_addr_high;
    unsigned long length_low;
    unsigned long length_high;
    unsigned long type;
}__attribute__((packed));

#define ADDRESS_RANGE_MEMORY    1
#define ADDRESS_RANGE_RESERVED    2

//可用内存起始地址和大小
static unsigned long mem_start = 0;
static unsigned long mem_size = 0;

//未分配内存链表,已分配内存链表
static mem_t * free_mem_head = NULL;
static mem_t * used_mem_head = NULL;

//未分配内存HASH表
#define MEM_HASH_NR    32
static mem_t * mem_hash[MEM_HASH_NR];



//初始化未分配内存链表
mem_t * init_free_mem_head(unsigned long mem_start, unsigned long mem_size)
{
    free_mem_head = (mem_t *)mem_start;
    free_mem_head->hnext = free_mem_head->next = free_mem_head->prev = NULL;
    free_mem_head->size = mem_size - sizeof(mem_t);
    free_mem_head->flag = MEM_FREE;
    return free_mem_head;
}

//给未分配内存链表添加内存节点
mem_t *add_free_mem_head(mem_t * p)
{
    if(!p)
    return NULL;


    //插入链表中
    if(!free_mem_head) //链表为空
    {
    free_mem_head = p;
    p->next = NULL;
    p->prev = NULL;
    }
    else if(p < free_mem_head) //插在链表头
    {
    p->next = free_mem_head;
    p->prev = NULL;
    free_mem_head->prev = p;
    free_mem_head = p;
    }
    else //插在链表中
    {
    mem_t * pt = free_mem_head;
    while(pt->next && p > pt->next)
    {
        pt = pt->next;
    }

    p->next = pt->next;
    if(p->next)
        p->next->prev = p;
    pt->next = p;
    p->prev = pt;
    }

    p->flag = MEM_FREE;    
    return p;
}

//从未分配内存链表中摘下内存节点
mem_t * get_free_mem_head(mem_t * p)
{
    if(!p)
    return NULL;

    if(free_mem_head == p)    //摘取链表头
    {
    if(p->next == NULL)        //链表只有一个节点
    { 
        free_mem_head = NULL;
    }
    else                //链表有多个节点
    {
        free_mem_head = p->next;
        free_mem_head->prev = NULL;
    }
    }
    else if(p->next == NULL)    //摘取链表尾
    {
    p->prev->next = NULL;
    }
    else            //摘取链表中的节点
    {
    p->prev->next = p->next;
    p->next->prev = p->prev;
    }

    return p;
}

//把p内存空间分割成 size 和 (p->size - size - sizeof(mem_t))大小的两个内存空间,然后摘除内存节点p
//返回(p->size - size - sizeof(mem_t))大小内存空间节点的指针
mem_t * split_get_free_mem_head(mem_t *p, unsigned long size)
{
    if(!p || !size)
    return NULL;
    if(p->size <= (size + sizeof(mem_t)))
    return NULL;
    
    //分割
    mem_t * newp = (mem_t *)((void *)p + sizeof(mem_t) + size);
    newp->size = p->size - size -sizeof(mem_t);
    newp->flag = MEM_FREE;
    p->size = size;
    newp->next = p->next;
    if(p->next)
    p->next->prev = newp;
    newp->prev = p;
    p->next = newp;

    //从未分配内存链表上摘除p节点
    get_free_mem_head(p);

    //返回新分割出来的内存节点
    return newp;
}

//初始化已分配内存链表
void init_used_mem_head()
{
    used_mem_head = NULL;
}

//添加已分配内存节点到已分配内存链表中 TODO:以后再实现
mem_t *add_used_mem_head(mem_t * p)
{
    if(!p)
    return NULL;

    p->flag = MEM_USED;
    return p;
}



//从已分配内存链表中摘除已分配内存节点 TODO:以后再实现
mem_t *get_used_mem_head(mem_t * p)
{
    if(!p)
    return NULL;

    return p;
}

//初始化未分配内存HASH表
void init_mem_hash()
{
    int i = 0;
    for(i = 0; i < MEM_HASH_NR; i++)
    {
    mem_hash[i] = NULL;
    }    
}

//把未分配的内存插入HASH表中
mem_t * add_mem_to_hash(mem_t * mem)
{
    if(!mem)
    return NULL;
    //根据内存大小,选择HASH表的下标
    //BSF 自右向左扫描  31~0
    //BSR 自左向右扫描  31~0
    unsigned long index = mem->size;
    __asm__ __volatile__ ("bsrl %1,%0\n\t"
        :"=r"(index)
        :"rm"(index)
        );
    if(mem_hash[index])
    {    //插到链表头
    mem->hnext = mem_hash[index];
    mem->hprev = NULL;
    mem_hash[index]->hprev = mem;
    mem_hash[index] = mem;
    }
    else
    {
    mem_hash[index] = mem;
    mem->hnext = NULL;
    mem->hprev = NULL;
    }

    return mem;
}

//从HASH表中获得未分配内存,只要未分配的内存大小大于size
//成功则从HASH表上摘除该内存!!!!!!!
//成功返回mem_t 指针,失败返回NULL
mem_t * get_mem_from_hash(unsigned long size)
{
    if(!size)
    return NULL;

    //根据内存大小,选择HASH表的下标
    //BSF 自右向左扫描  31~0
    //BSR 自左向右扫描  31~0
    unsigned long index = size;
    __asm__ __volatile__ ("bsrl %1,%0\n\t"
        :"=r"(index)
        :"rm"(index)
        );
    int i = 0;
    mem_t * p = NULL;
    for(i = index; i < MEM_HASH_NR; i++)
    {
    if(mem_hash[i])
    {
        //从链表头取
        p = mem_hash[i];
        mem_hash[i] = mem_hash[i]->hnext;
        if(mem_hash[i])
        mem_hash[i]->hprev = NULL;
        break; 
    }
    }

    return p;
}


mem_t * remove_mem_from_hash(mem_t *p)
{
    if(!p || p->flag != MEM_FREE)
    return NULL;

    //p在HASH表中的链表的位置有三种情况:链表头;链表尾;链表中间
    if(p->hprev == NULL)
    {
    //根据内存大小,选择HASH表的下标
    //BSF 自右向左扫描  31~0
    //BSR 自左向右扫描  31~0
    unsigned long index = p->size;
    __asm__ __volatile__ ("bsrl %1,%0\n\t"
            :"=r"(index)
        :"rm"(index)
        );
    if(mem_hash[index] != p)
        return NULL;

    mem_hash[index] = mem_hash[index]->hnext;
    if(mem_hash[index])
        mem_hash[index]->hprev = NULL;
    }
    else if(p->hnext == NULL)
    {
    p->hprev->hnext = NULL;
    }
    else
    {
    p->hprev->hnext = p->hnext;
    p->hnext->hprev = p->hprev;
    }


    return p;
}

//合并未分配内存
//成功则返回 合并后的mem_t内存节点指针
//该函数操作未分配内存链表和内存HASH表
mem_t *join_free_mem(mem_t *p)
{
    if(!p)
    return NULL;

    //尝试合并相邻节点,合并条件是
    // p->prev + sizeof(mem_t) + p->prev->size == p
    // p + sizeof(mem_t) + p->size == p->next
    mem_t * tmp = NULL;
    if(p->prev && (p->prev + sizeof(mem_t) + p->prev->size) == p) //合并左边节点
    {
    tmp = p->prev;
    remove_mem_from_hash(p); //从hash表上摘除
    remove_mem_from_hash(tmp); //从hash表上摘除

    tmp->next = p->next;
    if(p->next)
        p->next->prev = tmp;
    tmp->size = tmp->size + sizeof(mem_t) + p->size;
    p = tmp;
    add_mem_to_hash(p);      //把新合并的内存节点添加到HASH表上
    }

    if(p->next && (p + sizeof(mem_t) + p->size) == p->next)    //合并右边节点
    {
    tmp = p->next;
    remove_mem_from_hash(p); //从hash表上摘除
    remove_mem_from_hash(tmp); //从hash表上摘除

    p->next = tmp->next;
    if(tmp->next)
        tmp->next->prev = p;
    p->size = p->size + sizeof(mem_t) + tmp->size;
    add_mem_to_hash(p);      //把新合并的内存节点添加到HASH表上
    }

   return p;

}
void init_mem()
{
    int i = 0;
    //查找内存大小
    unsigned long *nr = (unsigned long *)E820NR;
    struct ARDS *ptr = (struct ARDS *)E820MAP;
    //打印物理内存信息,并初始化内存起始地址和内存大小
    sys_kprint(char_attr(BLACK,WHITE),"BaseAddr\tLength\tType\n");    
    for(i = 0; i < *nr; i++)
    {
    
    print16base(char_attr(BLACK,WHITE),ptr[i].base_addr_low);
    sys_kprint(char_attr(BLACK,WHITE),"\t");
    print16base(char_attr(BLACK,WHITE),ptr[i].length_low);
    sys_kprint(char_attr(BLACK,WHITE),"\t");
    print16base(char_attr(BLACK,WHITE),ptr[i].type);
    sys_kprint(char_attr(BLACK,WHITE),"\n");
    
    if(ptr[i].type == ADDRESS_RANGE_MEMORY && ptr[i].length_low > mem_size)
    {
        mem_start = ptr[i].base_addr_low;    //得到可用内存的起始地址
        mem_size = ptr[i].length_low;    //得到可用内存的大小
    }
    }

    sys_kprint(char_attr(BLACK,WHITE),"\nMemory Start = ");
    print16base(char_attr(BLACK,WHITE),mem_start);
    sys_kprint(char_attr(BLACK,WHITE),"\nMemory Size = ");
    print16base(char_attr(BLACK,WHITE),mem_size);
    sys_kprint(char_attr(BLACK,WHITE),"\n\n");


    //初始化未分配内存链表和已分配内存链表
    mem_t *first_mem = NULL;
    first_mem = init_free_mem_head(mem_start, mem_size);
    init_used_mem_head();

    //初始化未分配内存HASH表
    init_mem_hash();
    
    //把第一块未分配的内存添加进HASH表中
    add_mem_to_hash(first_mem); 
}

//获取指定大小内存空间的地址,成功返回内存地址,失败返回NULL
void *kmalloc(unsigned long size)
{
    if(!size)
    return NULL;

    //把size变成4的倍数,防止碎片化
    size = ((size - 1)/4  + 1)*4;

    //从hash表中查找大于等于size的未分配空间
    mem_t *p = get_mem_from_hash(size);
    if(!p)
    return NULL;

    //在未分配内存链表中摘除该空间,有三种情况:
    //第一种情况:(p->size) == size                大小刚合适
    //第二种情况:size < (p->size)  < size + sizeof(mem_t) + 4    全分配,不至于分割出小于4的内存空间
    //第三种情况:size + sizeof(mem_t) + 4 <= (p->size)        分割内存

    if(p->size < size + sizeof(mem_t) + 4)   
    {
    p = get_free_mem_head(p);  //全分配
    }
    else
    {
    mem_t *newp = split_get_free_mem_head(p, size);  //分割内存
    add_mem_to_hash(newp);                 //把新分割出的内存添加到HASH表中
    }

    //添加到已分配内存链表中
    add_used_mem_head(p);

    //从内存节点转换成可用的内存指针
    return ((void *)p + sizeof(mem_t));    
}

//释放内存,成功则返回内存地址,失败则返回NULL
void *kfree(void *addr)
{
    if(!addr)
    return NULL;

    //从内存指针转换成可用的内存节点
    mem_t *p = (mem_t *)(addr - sizeof(mem_t));
    
    //从已分配内存链表中摘除
    p = get_used_mem_head(p);

    //添加到未分配内存链表中
    p = add_free_mem_head(p);

    //添加到内存HASH表中
    add_mem_to_hash(p);

    //尝试合并内存,减少内存碎片
    join_free_mem(p);

    return addr;
}

mutex_t mem_mutex = 0;

void * sys_malloc(unsigned long size)
{
    void *p = NULL;
    lock(&mem_mutex);
    p = kmalloc(size);
    unlock(&mem_mutex);

    return p;
}

void * sys_free(void *addr)
{
    void *p = NULL;
    lock(&mem_mutex);
    p = kfree(addr);
    unlock(&mem_mutex);

    return p;
}

第20章 内联汇编

C/C+代码与汇编代码间有交接,双方要指定交接人。交接人之间传值,完成C/C++代码与汇编代码的沟通。

内联汇编执行步骤:

  1. C/C++代码把值传给汇编代码(输入)
  2. 内联汇编中的汇编语句
  3. 汇编代码把值传回给C/C++代码(输出)

可以参考《Developing Your Own Unix-Like OS on IBM PC》中的AT&T ASM章节中。 http://www.huihoo.org/gnu_linux/own_os/preparing-asm_3.htm

第17章 互斥量的设计与实现

当所有的任务在同个单一地址空间下,使用共享资源时,必然涉及到共享资源的竞争。只有多个任务互斥地访问共享资源时才不会发生错误。只有提供互斥或信号量才能保证内核并发机制。

任何互斥尝试必须基于一些基础硬件互斥机制。最常见的这种约束是某一时刻对内存的一次访问。(intel处理器可以查看《IA-32架构软件开发人员指南 卷3 系统编程指南》中7.1节 加锁的原子操作)

x86上实现互斥,需要硬件的支持:

  1. 中断禁用。代价高,在单CPU上能使用。在多CPU上不能使用(多处理器中,是对等关系,没有支持互斥的中断机制)。
  2. 专用机器指令:在一个指令的执行周期内对一个存储单元的读和写(xchg) 或 测试和设置(testset)。在该指令的执行过程中,任何其他指令访问内存将被阻止。

IA-32处理器提供了LOCK#信号。这个信号会在某些内存操作过程中被自动发出。当做这个输出信号发出的时候,来自其他处理器或总线代理的总线控制请求将被阻塞。软件能够利用在指令前添加LOCK前缀来指定,在其他情况下也需要LOCK语义(LOCK semantices)。

在Intel 386 ,Intel 486,Pentium处理器中,直接调用加锁的指令会导致LOCK#信号的产生。硬件的设计者需要保证系统硬件中LOCK#信号的有效性,以控制多个处理器对内存的访问。对与Pentium 4,Intel Xeon,以及P6系列处理器,如果被访问的内存区域存在于处理器内部的高速缓存中,那么LOCK#信号通常不被发出;但是处理器的缓存却要被锁定。

xchg指令会自动的带有LOCK 语义。

mutex.h源代码如下所示

#ifndef _MUTEX_H_  
#define _MUTEX_H_  
  
typedef unsigned long mutex_t;  
  
static inline unsigned long xchgl(unsigned long x, unsigned long *ptr)  
{  
    __asm__ __volatile__("xchgl %0,%1\n\t"  
        :"=r"(x)  
        :"m"(*ptr),"0"(x)  
        :"memory"  
        );  
    return x;  
}  
  
/*mptr是mutex_t的指针*/  
#define lock(mptr) ({\  
    while(xchgl(1,(mptr)));\  
})  
  
/*mptr是mutex_t的指针*/  
#define unlock(mptr) xchgl(0,(mptr))  
  
  
/*mptr是mutex_t的指针*/  
#define init_mutex(mptr) ({*mptr = 0;})  
  
  
#endif