嵌入式操作系统内核原理和开发（改进型优先级调度）

    上面的一篇博客说到了优先级调度，但是那个优先级调度算法比较极端。打个比方说，现在王先生有三个小孩，分别是老大、老二、老三。假设现在到了饭点，王先生需要给三个小孩喂饭。此时如果是时间片轮转的话，那么就是绝对公平，王先生每人一口不停地进行喂饭。如果是优先级调度，那么王先生首先自己有一个优先级考量，比如说三个小孩按照年龄顺序优先级是逐渐提高的，毕竟小孩需要更多的照顾嘛。这个时候如果需要进行喂饭的话，那么王先生需要首先伺候好最小的那个小孩老三，才会有时间照顾老二，至于老大什么时候才能得到照顾那就看造化了。

    现在，我们打算重新换一种方法。假设三个小孩的优先级分别是1、2、3，其中年龄越小优先级越高，3代表高优先级。接着，我们按照优先级给三个小孩安排时间片，分别是1、2、3。同时，这个时间片不光代表了当前可用的剩余时间，还代表了小孩此时的临时优先级。

    （1）首先王先生给老三喂饭，时间片降低1，即临时优先级为2；

    （2）接着王先生判断当前优先级最高的仍为老三，毕竟老二的优先级也没有超过老三，所以老三的时间片降1，临时优先级为1；

    （3）王先生获知当前优先级最高的为老二，老二获得时间片；

    （4）此时王先生发现三个孩子的临时优先级都一样，那么就会按照固定优先级的大小依次对老三、老二、老大进行喂饭。

    我们发现，这中间受益最大的就是老二。当然，我们可以做进一步推论，如果老王的孩子越多，那么优先级处于中间的孩子在时间片的分配上将更加均匀，响应也会更加及时，交互性也会变得很好。

    根据以上的想法，我们重新改写了优先级调度算法，修改为改进型优先级调度算法，

int find_next_thread()
{
    int index;
    int choice = THREAD_MAX_NUMBER -1;
    int value = gAllTask[choice].time_slice;

    for(index = choice -1; index >= 0; index --)
    {
        if(value < gAllTask[index].time_slice)
        {
            choice = index;
            value = gAllTask[index].time_slice;
        }
    }

    if(0 == value)
        choice = -1;

    return choice;      
}

    当然，加上原来的时间片轮转调度、通用优先级调度方法，此时就存在三种调度方法了。我们可以自己设置宏，通过宏的设置灵活选用调度算法，

#define TIME_ROUND_SCHEDULE     0
#define HARD_PRIORITY_SCHEDULE  0
#define SOFT_PRIORITY_SCHEDULE  1

    这些代码都是可以在系统中共存的。选用什么算法，取决于实际情况是什么样的情形。

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <signal.h>
#include <assert.h>
#include <string.h>
#include <sys/time.h>

#define UINT32 unsigned         int
#define STACK_LENGTH            512
#define THREAD_MAX_NUMBER       10
#define TIME_ROUND_SCHEDULE     0
#define HARD_PRIORITY_SCHEDULE  0
#define SOFT_PRIORITY_SCHEDULE  1   

typedef struct _TASK_INFO
{
    UINT32 id;
    UINT32* stack;
    UINT32 size;
    UINT32 context;
    UINT32 priority;
    UINT32 time_slice;
    void (*func)();

}TASK_INFO;

static struct itimerval oldtv;
UINT32 old   = 0;
UINT32 count = 0;
UINT32 task_stack[THREAD_MAX_NUMBER][STACK_LENGTH] = {0};
TASK_INFO gAllTask[THREAD_MAX_NUMBER] = {0};
UINT32 current_thread_id = 0;

void set_timer()
{
        struct itimerval itv;
        itv.it_interval.tv_sec = 1;
        itv.it_interval.tv_usec = 0;
        itv.it_value.tv_sec = 1;
        itv.it_value.tv_usec = 0;
        setitimer(ITIMER_REAL, &itv, &oldtv);
}

void swap(UINT32* prev, UINT32* next)
{
    __asm("push %%eax\n\t"
          "push %%ebx\n\t"
          "push %%ecx\n\t"
          "push %%edx\n\t"
          "push %%esi\n\t"
          "push %%edi\n\t"
          "push %%ebp\n\t"
          "push %%esp\n\t"
          "lea 0x8(%%ebp), %%eax\n\t"
          "mov (%%eax), %%eax\n\t"
          "mov %%esp, (%%eax)\n\t"

          "lea 0xc(%%ebp), %%eax\n\t"
          "mov (%%eax), %%eax\n\t"
          "mov (%%eax), %%esp\n\t"
          "pop %%esp\n\t"
          "pop %%ebp\n\t"
          "pop %%edi\n\t"
          "pop %%esi\n\t"
          "pop %%edx\n\t"
          "pop %%ecx\n\t"
          "pop %%ebx\n\t"
          "pop %%eax\n\t"
          ::);
}

void hello()
{
        int temp = 0;

        while(1) {
            printf("id = %d, temp = %d, count = %d in thread!\n",current_thread_id,  temp ++, count ++);
            swap(&gAllTask[current_thread_id].context, &old);

            printf("id = %d, temp = %d, count = %d in thread!\n",current_thread_id,  temp ++, count ++);
            swap(&gAllTask[current_thread_id].context, &old);
        }
}

#if HARD_PRIORITY_SCHEDULE
int find_next_thread()
{
    int index;

    for(index = THREAD_MAX_NUMBER -1; index >=0; index --)
    {
        if(0 != gAllTask[index].time_slice)
            break;
    }

    return index;      
}

#endif


#if SOFT_PRIORITY_SCHEDULE
int find_next_thread()
{
    int index;
    int choice = THREAD_MAX_NUMBER -1;
    int value = gAllTask[choice].time_slice;

    for(index = choice -1; index >= 0; index --)
    {
        if(value < gAllTask[index].time_slice)
        {
            choice = index;
            value = gAllTask[index].time_slice;
        }
    }

    if(0 == value)
        choice = -1;

    return choice;      
}

#endif

void reset_time_slice ()
{
    int index;

    for(index = 0; index < THREAD_MAX_NUMBER; index++)
        gAllTask[index].time_slice = gAllTask[index].priority + 1;
}

void task_init(int index)
{
        UINT32 unit = gAllTask[index].size;
        UINT32* pData = gAllTask[index].stack;

        memset((void*)pData,(int) 0, unit * sizeof(UINT32));
        pData[unit -1] = (UINT32) gAllTask[index].func;
        pData[unit -2] = 0;
        pData[unit -3] = 0;
        pData[unit -4] = 0;
        pData[unit -5] = 0;
        pData[unit -6] = 0;
        pData[unit -7] = 0;
        pData[unit -8] = 0;
        pData[unit -9] = 0;
        pData[unit -10] = (UINT32) &pData[unit - 9];
        gAllTask[index].context = (UINT32) &pData[unit -10];
}

#if TIME_ROUND_SCHEDULE
void signal_handler(int m)
{
        current_thread_id = current_thread_id % THREAD_MAX_NUMBER;
        swap(&old, &gAllTask[current_thread_id].context);
        current_thread_id ++;
}

#else
void signal_handler(int m)
{
        int index;

start:
        index = find_next_thread();
        if(-1 == index)
        {
            reset_time_slice();
            goto start;
        }

        gAllTask[index].time_slice --;
        current_thread_id = index;
        swap(&old, &gAllTask[current_thread_id].context);
}
#endif


void set_all_task() 
{
        int index;
        memset(gAllTask, 0, sizeof(gAllTask));

        for(index = 0; index < THREAD_MAX_NUMBER; index ++)
        {
            gAllTask[index].id = index;
            gAllTask[index].stack = task_stack[index];
            gAllTask[index].size = STACK_LENGTH;
            gAllTask[index].context = 0;
            gAllTask[index].func = hello;
            gAllTask[index].priority = index;
            gAllTask[index].time_slice = index + 1;

            task_init(index);
        }
}

int main()
{
        char val;

        set_all_task();
        set_timer();
        signal(SIGALRM, signal_handler);

        while(1)
        {
            scanf("%c", &val);
        }

        exit(0);
        return 1;
}