linux中list.h用户态使用，模拟多级反馈队列调度算法

      前段时间看操作系统处理机调度一节时发现轮转调度算法中有一个调度算法（多级反馈队列调度算法）比较有
意思，而且其性能也比较好，看操作系统有时光看的话，看着看着就会逐渐感觉枯燥，我确实不想陷入无趣的学习中去，于是想提高自己的动手能力，于是自己写一个小程序模拟一下这个算法，一开始感觉没什么思路，后来想想也没什么难的，就下定决心自己弄一个出来。
     现在贴出来供大家参考一下，有什么不合里的希望读者帮忙指正，谢谢！

     多级反馈队列调度算法原理描述如下：

  1、设置多个就绪队列，并给队列赋予不同的优先级数，第一个最高，依次递减。
  2、赋予各个队列中进程执行时间片的大小，优先级越高的队列，时间片越小。
  3、当一个新进程进入内存后，首先将其放入一个对列末尾，如果在一个时间片
      结束时尚未完成，将其转入第二队列末尾。
  4、当一个进程从一个对列移至第n个队列后，便在第n个队列中采用时间片轮转执行完。
  5、仅当时间片空闲时，才调度第二个队列中的进程。在低优先级的队列中的进程在运行时，又有新到达的作业，
      那么在运行完这个时间片后，CPU马上分配给新到达的作业（）。但本程序还没实现抢占式。
 
   
    
      list.zip    (从linux 内核2.6 中移出来的附件,如果需要可以下载下来与下面的程序放在同一目录下)

   好了，不多说看看代码再说^—^ ,我花了一点时间在代码中加入些许注释，希望对你阅读有帮助！
  

/* reaction_list.c */
// list.h用户态使用，模拟多级反馈队列调度算法（只是还没实现优先级抢占式分配）
// 由于使用了list.h 所以很多操作不必重新编码，大大减少工作量
// 多级反馈队列调度算法更具体描述请翻阅有关操作系统书籍

#include <stdio.h>
#include <math.h>    // 编译时请使用 -lm 参数
#include <pthread.h>  // 编译时用  -lpthread 参数
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include "list.h"  // 该文件从内核中移出来，并放到程序所在目录下

struct reaction_queue
{
    int time_slice; //队列i的时间片
    struct list_head list_r; //队列的双向头指针
};

//相当于task_struct的简单结构
struct process_task
{
    char pro_name[30];// 作业名称
    int pt_ID;        // 作业ID
    int need_times;      // 作业需要执行的时间
    struct list_head list_node; // 链接队列的指针节点
};

//#define PRINT_INFO 1

#define LEVELS 10 // 设置队列数量

FILE *Out = NULL;

struct reaction_queue rl[LEVELS]; // 指向队列首的数组
int G_pro_ID = 0; // 为载入的作业分配ID

void reaction_init(struct reaction_queue p[], int n)
{
    int i;

    for (i = 0; i < n; i++) {
        p[i].time_slice = pow(2, i+1); // 各队列时间片2^i
        INIT_LIST_HEAD(&p[i].list_r);
        //printf("Init %d Node\n",i);
    }
//    puts("Init OK");
}

// p节点初始化
void process_struct_init(struct process_task *p)
{
    memset(p->pro_name, 0, sizeof(p->pro_name)/sizeof(char));
    p->need_times = 0;
    INIT_LIST_HEAD(&p->list_node);
    //以下2个宏只能用于定义并初始化，所以这里不能用
//    struct list_head ls = LIST_HEAD_INIT(ls);LIST_HEAD(lp);
}

// 根据p所在的队列级别，运行相应的时间片（这里以睡眠模拟运行）
struct process_task *dequeue_running(struct list_head *p, int time_slice)
{
    int sleep_time = 0;
    struct process_task *q = NULL;

    // 首先通过p指向的成员list_node获得p所在的结构体指针（即struct process_task*）
    q = list_entry(p, struct process_task, list_node);
    if(q->need_times < time_slice) {
        sleep_time = q->need_times;
        q->need_times = 0;
    }
    else {
        sleep_time = time_slice;
        q->need_times -= time_slice;
    }
    // 将其运行信息写入文件中
    fprintf(Out,"%s \t  %d\t\t %d\n", q->pro_name, time_slice, \
            q->need_times);
    sleep(sleep_time);

    return q;
}

// 该函数没有使用，若要使用可以将PRINT_INFO宏的注释去掉
void pro_print()
{
    int i;
    struct list_head *lp, *lshead;
    struct process_task *p = NULL;

    #ifdef PRINT_INFO
    for (i = 0; i < LEVELS; i++) {
        lshead = &rl[i].list_r;
        if (!list_empty(lshead)) {
            printf("rl[%d]    ID   pro_name   left_time----\n", i);
            list_for_each(lp, lshead) {
                p = list_entry(lp, struct process_task, list_node);
            //    printf("rl[%d]    ID   pro_name   left_time----\n", i);
                printf("\t %-4d %-9s     %d\n", p->pt_ID, p->pro_name, \
                            p->need_times);
            }
            puts("--------------------------------");
        }
        else {
            printf("rl[%d] is NULL\n",i);
        }
    }
    #endif
}
// 反馈队列调度（先来先服务，当然这里没实现抢占式调度），主要利用list.h中的函数
void levels_schedule()
{
    int i;
    struct list_head *lp, *lshead;
    struct process_task *p = NULL;
//start:
//    system("gnome-terminal\n");
    for (;;) {

        for (i = 0; i < LEVELS; i++) {
            lshead = &rl[i].list_r;
            if (!list_empty(lshead)) {
                lshead = lshead->next;
            //    printf("run\n");
                p = dequeue_running(lshead,rl[i].time_slice);
                if (p->need_times > 0) { // 时间片用完，但还没完成
                    int next = (i+1)%LEVELS;
                    lp = &rl[next].list_r;
                    list_move_tail(lshead, lp);    // 将其移至队尾
                }
                else {
                    fprintf(Out, "\nID=%d %s quit\n",p->pt_ID, p->pro_name);
                    list_del(lshead); // 执行完了，撤销该作业
                    free(p);
                }
                break;
            }
        }

        if (LEVELS == i) { // 本不应该退出的，但在这里只是模拟
            fprintf(Out,"No process is running, quit!\n");
            break;
        }
    }
}

// 加载作业插入到就绪队列0
void load_pro_thread()
{
    char str[50];
    int time;
    struct list_head *first_head = &rl[0].list_r;

    for (; ;) {
        printf("Input process: pro_name need_times:");
        scanf("%s %d", str, &time);
        if (0 == time)
            break;
        struct process_task *new = (struct process_task *)malloc( \
                sizeof(struct process_task));
        if (NULL == new) {
            printf("Memory malloc failed\n");
            exit(1);
        }
        //printf("pro_name: %s  need_time: %d\n", str, time);
        process_struct_init(new);
        strcpy(new->pro_name, str);
        new->need_times = time;
        new->pt_ID = ++G_pro_ID;
        list_add_tail(&new->list_node, first_head);

        getchar();
        pro_print();
    }
    printf("\n");
}

int main()
{
    int i;
    pthread_t th_id;

    //把调度信息写入文件方便观看
    Out = fopen("list_reaction.txt","w");
    if (!Out) {
        return -1;
    }
    fprintf(Out, "pro_name  time_slice  need_timei\n");

    reaction_init(rl, LEVELS); //初始化全部队列为空
    // 启动一线程加载将要运行的作业，将其插入到队列下标为0的队列中
    if(pthread_create(&th_id, NULL, (void *)load_pro_thread, NULL)) {
        printf("Thread create failed\n");
        exit(1);
    }
    sleep(5);//等一下以便装入第一个作业
//    pro_print();
    levels_schedule();//主线程用于调度
    fclose(Out);

    return 0;
}

 
   编译链接代码: gcc reaction_list.c -o reaction_list -lm -lpthread 执行 ./reaction_list 然后根据提示装载
“作业”，待所有“作业”完成“退出后，可以在 list_reaction.txt 这个文件中看到“作业”执行的相关信息。
        注：本博客的文章除注明有“转载”字样的外，均为原创，欢迎转载，请注明文字出处，谢谢！