裸机程序--时间片调度

1.为什么自己写一个时间片调度呢

        a. 网上其实有很多成熟的时间片调度例程, 包括我最开始参加工作也是抄的网上的例程(还记得当时领导问我看明白了它的调度原理吗, 作为一个自学刚参加工作的我来说, 看懂别人的意思真的很难, 当时只能含糊其词的说看得差不多)

        b. 在我看来网上的例程是有一些问题的, 计算时间的那个函数放到定时器中递减, 随着任务的增加, 定时器定时越不准确, 违背了中断的快进快出, 不过话说回来时间片本来就是一个不准确的定时.

        c. 违背了软件的开闭原则, 每次添加任务都需要进去修改那个定义任务调度的数组.

        d. 时间为0的任务不能添加到调度中.

        e. 不能删除任务: 比如某个任务我运行了一段时间, 我根本就不会运行了, 这个时候它还是在调度, 只是我们会在内部放置一个标志位, 让它快速切出去.同时也不能在运行过程中添加任务.

2.程序设计思路

        1. 先说下如何定时, 通过一个int类型(32bit)来记录1ms时间过去了, 当定时中断产生中断依次将bit0-31置1, 然后在while(1)中检测有没有置1的bit, 如果有就将任务时间递减. 由于只用一个int类型计时, 这也是为什么程序最大只能支持你程序中, 不能死等超过32ms. 

        2. 任务的删除, 添加, 转移其实都是链表的知识, 掌握好链表就能明白了.

3.程序移植

2.1 移植超级简单, 只需要添加三个文件: os.c, os.h, list.h; 将time_cb放到1ms定时器中断

#include "os.h"
#include "string.h"
 
#define MAX_SLICE_SUPPORT    0x1F   /* 程序运行过程最大允许被阻塞时间, 如果大于32ms, 将会导致计时不准 */
volatile static unsigned int millisecond; 
 
typedef struct
{
    unsigned int time_que;
    unsigned char bit_head;
    unsigned char bit_tail;
}bit_time_t;
 
bit_time_t task_time = {0};
 
/* 任务等待队列和任务就绪队列 */
struct list_head list_wait = LIST_HEAD_INIT(list_wait);
struct list_head list_ready = LIST_HEAD_INIT(list_ready);
 
void add_task(task_t *task)
{
    if(task->time_slice == 0)   /* 如果时间片设置为0, 则直接挂到就绪队列 */
    {
        list_add(&task->next, &list_ready);
    } 
    else    /* 否则将任务挂到等待队列 */
    {
        list_add(&task->next, &list_wait);
    }
}
 
void delet_task_onself(task_t *task)
{
    list_del(&task->next);
}
 
static void move_task(task_t *task, struct list_head* soure_list, struct list_head* dest_list)
{
    if(soure_list == &list_wait)    /* if the task in list_wait, then move to list_ready */
    {
        list_del(&task->next);
        list_add(&task->next, dest_list);
    }
    else
    {
        /* task->time_slice is not zero can move to list_wait */
        if(task->time_slice)
        {
            list_del(&task->next);
            list_add(&task->next, dest_list);
        }
    }
}
 
/* 放到1ms的定时器中断里面 */
inline void time_cb()
{ 
    task_time.bit_tail = millisecond & MAX_SLICE_SUPPORT;
    task_time.time_que |=  1 << task_time.bit_tail;
    millisecond++;
}
 
void run_task()
{
    task_t  *node, temp_node;
 
    /* 时间队列里面是否有时间 */
    if(task_time.time_que & (1 << task_time.bit_head))
    {
        /* 将延时等待队列的时间减一 */
        list_for_each_entry(node, &list_wait, next, task_t)
        {
            node->slice_count--;
            if(node->slice_count == 0)  /* 如果时间减完了, 则将当前任务挂到就绪队列 */
            {
                memcpy(&temp_node, node, sizeof(task_t));
                node->slice_count = node->time_slice;
                move_task(node, &list_wait, &list_ready);
                node = &temp_node;
            }    
        }
 
        /* 将当前bit的时间清零, 并让bit_head指向下一个位置 */
        task_time.time_que &= ~(1 << task_time.bit_head);
        task_time.bit_head++;
        if(task_time.bit_head == MAX_SLICE_SUPPORT)
        {
            task_time.bit_head = 0;
        }
    }
 
    /* 执行就绪队列中的任务, 并将任务重新挂到等待队列 */
    list_for_each_entry(node, &list_ready, next, task_t)
    {
        memcpy(&temp_node, node, sizeof(task_t));
        move_task(node, &list_ready, &list_wait);
        node->task();
        node = &temp_node;
    }
}
 
unsigned int current_time()
{
    return millisecond;
}
unsigned int time_interval(unsigned int *start_time)
{
    if(*start_time == 0)
    {
        *start_time = millisecond;
    }
    return (millisecond > *start_time) ? (millisecond - *start_time) : (0xFFFFFFFF - *start_time + millisecond);
}

#ifndef LIST_H
#define LIST_H
 
struct list_head {
    struct list_head *next, *prev;
};
 
//双链表的头初始化,next, prev指向自己
#define LIST_HEAD_INIT(name) { &(name), &(name) }
 
//通过函数初始化头
static inline void INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list;
    list->prev = list;
}
 
//添加一个新的结点
static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next)
{
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}
 
//头插法
static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}
 
//尾插法
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
    __list_add(new, head->prev, head);
}
 
//删除某个结点
static inline void __list_del(struct list_head *prev, struct list_head *next)//将要删除的结点从链表中释放出来
{
    next->prev = prev;
    prev->next = next;
}
static inline void list_del(struct list_head *entry) //这个函数才是最后的删除函数
{
    __list_del(entry->prev, entry->next);
    entry->next = (void *)0;
    entry->prev = (void *)0;
}
 
//判断结点是否为空
static inline int list_empty(const struct list_head *head)
{
    return head->next == head;
}
 
//已知结构体中的某个成员的地址ptr,得到结构体的地址
#define list_entry(ptr, type, member) \
    ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
 
//遍历链表, pos为链表结点, head为链表头, member为链表中的成员, type为结点类型
#define list_for_each_entry(pos, head, member, type)        \
    for (pos = list_entry((head)->next, type, member);      \
            &pos->member != (head);                         \
            pos = list_entry(pos->member.next, type, member))
#endif
 

#ifndef OS_H
#define OS_H
#include "list.h"
typedef struct
{
    void (*task)();
    unsigned short time_slice;
    unsigned short slice_count;
    struct list_head next;
}task_t;  
 
void add_task(task_t *task);
void delet_task_onself(task_t *task);
void run_task(void);
 
void time_cb(void);
unsigned int current_time(void);
unsigned int time_interval(unsigned int *start_time);
 
#endif

2.2 添加任务和调用

我使用了编译器特性, 自动运行程序, 这样就不需要在main函数开头手动调用函数add_task()了

#include "./UART/uart.h"
#include "./BaseTime/basetime.h"
#include "os.h"
 
static void task1(void);
 
static task_t task_1 = {
    .task = task1,
    .time_slice = 500,
    .slice_count = 500,
};
 
static void task1()
{
    printf("task1\n");
}
 
/* 使用编译器特性, 自动运行该程序 */
__attribute__((constructor)) static void task1_add()
{
    add_task(&task_1);
}
 
 
void task2();
task_t task_2 = {
    .task = task2,
    .time_slice = 387,
    .slice_count = 387,
};
void task2()
{
    static int count = 0;
    printf("task2ddasdfasfsafafasdsfsfsfsfsfsew\r\n");
    if(++count > 5)
    {
        delet_task_onself(&task_2);
    }
}
 
__attribute__((constructor)) void task2_add()
{
    add_task(&task_2);
}
 
void task3()
{
    printf("task3\r\n");
}
 
task_t task_3 = {
    .task = task3,
    .time_slice = 632,
    .slice_count = 632,
};
 
__attribute__((constructor)) void task3_add()
{
    add_task(&task_3);
}
 
 
 
int main(void)
{ 
    NVIC_PriorityGroupConfig(NVIC_PriorityGroup_2);
    uart_init(115200);
    bsTime_Init(1004, 80);//1ms中断
 
    while(1)
    {
        run_task();
    }
}

3.注意点

1.为了尽可能的节约内存, 以及程序调用的及时性, 程序运行过程最大可以等待32ms去轮询时间递减. 如果内部有死等大于32ms, 就有会导致任务执行时间不准确.

2.如果想在window验证, 由于list.h在visual studio会报错, 如果想验证需要安装gcc(在windows环境下用vscode配置gcc编译代码_windows vscode gcc-CSDN博客), 

贴出keil和gcc源码, 有积分的兄弟可以支持下.也可以不下, 我已经将所有代码贴出来了.

https://download.csdn.net/download/qq_38591801/88900090

4.代码仓库

        代码已放到gitee, 功能也会进一步完善, 如果有在使用中遇到bug, 可以在博客这边留言.

时间片框架: 基于时间片的裸机程序框架