[数据结构与算法] OS-基于位图的RR调度算法

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> OS-基于位图的RR调度算法 -> 正文阅读

[数据结构与算法]OS-基于位图的RR调度算法

OS-基于位图的RR调度算法

位图原理

有这么个业务场景，在10亿个不重复的随机整数中查找某个数 x 是否存在其中，32为操作系统，4G内存。

普通算法
我们可以使用10亿个int类型的空间来存储这10亿个数据，然后再进行x查找。这1亿个int数据就需要占用：1000000000*4 = 3.72G字节空间。光存储这10亿数据就要花到这么多内存实在是太恐怖了。其次在查找的时候，最快的hash查找，光数据结构的空间都要需要很庞大的内存空间。
位图算法
我们先把数据量缩小，假设只有10个随机数（0-9）
BitMap算法的核心思想是用bit数组来记录0-1两种状态，然后再将具体数据映射到这个比特数组的具体位置，这个比特位设置成0表示数据不存在，设置成1表示数据存在。
BitMap算在在大量数据查询、去重等应用场景中使用的比较多，这个算法具有比较高的空间利用率。

在这里插入图片描述

存储这个位图所需要的空间只需要2个字节，扩展到10亿个数的话，也只需要1000000000/8 = 119M字节空间，相比3.72G缩小了32倍

BitMap的一些缺点：
（1）数据碰撞。比如将字符串映射到 BitMap 的时候会有碰撞的问题，那就可以考虑用 Bloom Filter 来解决，Bloom Filter 使用多个 Hash 函数来减少冲突的概率。
（2）数据稀疏。又比如要存入(10,8887983,93452134)这三个数据，我们需要建立一个 99999999 长度的 BitMap ，但是实际上只存了3个数据，这时候就有很大的空间浪费，碰到这种问题的话，可以通过引入 Roaring BitMap 来解决。

bitmap在调度算法中的运用

基于现在我们的业务场景，我们需要在一堆随机优先级里查找出一个最高优先级，也就是查找出priority最小的那个优先级是多少。

假设，优先级范围为（0-255），现在假设有3个活动的优先级（20, 3, 32），按照之前的线性查找法，我们必须从0到255去轮询ready数组，轮询到g_readytorun[3]的时候，发现里面有任务可以调度，那么我们就找到了最高优先级。但是如果活动的优先级为（255，255，255），那我们就要查找255次才能确定最高优先级为255。所以线性查找法的时间复杂度为O(N），N为优先级最大取值

假设，现在有2个活动优先级（7，5），那么在位图中的表达为：

在这里插入图片描述

如果我们把他看成是一个字节的数据，二进制为bit（10100000）= 120 = 0xA0，从优先级来看，是不是从第0位开始第一个为1所代表的优先级，就是最低优先级，也就是第5位，我们查表g_priority_map[0xA0]就可以得到5这个优先级

我们只需要从0xA0这个值就可以一次找出最低优先级，不再需要去轮询了

在插入优先级的时

g_priority_bitmap |= 1 <<priority;

查找时

priority = g_priority_map(g_priority_bitmap)

当优先级在0_{7时使用1维就可以很简单的实现，如果优先级扩展到0}255我们就需要使用二维来实现

0~255的数据可以可以拆解成2个维度：

priority = row * 8 + col;

row为priority所在的分组，col为priority所在分组所在的位

bitmap数据结构

在二维数据结构中，我们把g_priority_bitmap扩展到一个数组，另外使用g_priority_group来保存所在分组

#define bitmask(x) (1ul << (x))

#define CONFIG_MAX_TASK_PRIORITY 256
struct sched_queue g_readytorun[CONFIG_MAX_TASK_PRIORITY];

#define MAX_PRIORITY_BITMAP_INDEX (CONFIG_MAX_TASK_PRIORITY / 8)
uint8_t g_priority_bitmap[MAX_PRIORITY_BITMAP_INDEX];

uint8_t g_priority_group;

关键数据结构

要实现O(1)查找的关键，就在下面这个map表，这个表存储了（0~255）所对应的二进制位下最低位为1所在的位数。
比如说priority（2，3） = bit（1100）,那么最低位为1所在的位数为第二位，当然现在很多汇编指令可以直接提取，比如说ARM下的CLZ指令，这样就不用去查找这个表了。

/* 任务优先级查找表-优先级值最低位为1所在的位数 */
uint8_t const g_priority_map[256] = { 
    0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x00 to 0x0F                             */ 
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x10 to 0x1F                             */ 
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x20 to 0x2F                             */ 
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x30 to 0x3F                             */ 
    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x40 to 0x4F                             */ 
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x50 to 0x5F                             */ 
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x60 to 0x6F                             */ 
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x70 to 0x7F                             */ 
    7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x80 to 0x8F                             */ 
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0x90 to 0x9F                             */ 
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0xA0 to 0xAF                             */ 
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0xB0 to 0xBF                             */ 
    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0xC0 to 0xCF                             */ 
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0xD0 to 0xDF                             */ 
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,       /* 0xE0 to 0xEF                             */ 
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0        /* 0xF0 to 0xFF                             */ 
};

添加一个优先级

g_priority_group代表该优先级所在分组
g_priority_bitmap[index]存储着该优先级对应分组下所在的位

int index = task->sched_priority / 8;
int remain = task->sched_priority % 8;

g_priority_group |= bitmask(index);
g_priority_bitmap[index] |= bitmask(remain);

查找优先级

uint8_t row = g_priority_map[g_priority_group];
uint8_t re = g_priority_bitmap[row];
uint8_t col = g_priority_map[re];
uint8_t sched_priority = row * 8 + col;

删除一个优先级

在删除优先级时，需要确保此优先级分组所有优先级都被删除时才能清空优先级分组标识

if ((g_priority_bitmap[index] &= (~ bitmask(remain))) == 0) {
    // 当此优先级所在组全部清空后，才清空优先级分组标识
    g_priority_group &= (~ bitmask(index));
}

实际模拟一下

有2个优先级（3, 32）

添加优先级3

int index = task->sched_priority / 8;
// index = 3 / 8 = 0
int remain = task->sched_priority % 8;
// remain = 3 % 8 = 3

g_priority_group |= bitmask(index);
// g_priority_group |= 1 << 0 = 1
g_priority_bitmap[index] |= bitmask(remain);
// g_priority_bitmap[0] |= 1 << 3 = 8

添加优先级32

int index = task->sched_priority / 8;
// index = 32 / 8 = 4
int remain = task->sched_priority % 8;
// remain = 32 % 8 = 0

g_priority_group |= bitmask(index);
// g_priority_group = 1 | 1 << 4 = 17
g_priority_bitmap[index] |= bitmask(remain);
// g_priority_bitmap[4] |= 1 << 0 = 1

查找优先级

uint8_t row = g_priority_map[g_priority_group];
// row = g_priority_map[17] = 0
uint8_t re = g_priority_bitmap[row];
// re = g_priority_bitmap[0] = 8
uint8_t col = g_priority_map[re];
// col = g_priority_map[8] = 3
uint8_t sched_priority = row * 8 + col;
// sched_priority = 0 * 8 + 3 = 3

再添加一个队列

采用bitmap进行查找后，我们需要在原来的ready队列之上，再增加一个pending队列，pending队列上保存着所有待调度的任务（不包括mutex/semaphore），我们需要在每一次schedule时去检查pending队列上是否有可被调度的任务，然后把可调度的任务再加入到ready队列中去。

struct sched_queue g_pendingtasks;

void schedule_wake(tcb_t *task)
{
    list_del_init(&task->link_head);

    int index = task->sched_priority / 8;
    int remain = task->sched_priority % 8;

    g_priority_group |= bitmask(index);
    g_priority_bitmap[index] |= bitmask(remain);
}

void schedule_attach(tcb_t *task)
{
    assert(task != NULL);

    task->task_state = TSTATE_TASK_READYTORUN;
    sched_enqueue(&g_readytorun[task->sched_priority], task);

    int index = task->sched_priority / 8;
    int remain = task->sched_priority % 8;

    g_priority_group |= bitmask(index);
    g_priority_bitmap[index] |= bitmask(remain);
}

void schedule_pending_check(void)
{
    tcb_t *pend_task = NULL;
    tcb_t *pend_task_tmp = NULL;
    list_for_each_entry_safe(pend_task, pend_task_tmp, &g_pendingtasks.tasks_head, link_head)
    {
        int64_t remain_ticks = clock_systime_ticks() - pend_task->readytime;
        if (remain_ticks >= 0) {
            schedule_wake(pend_task);
            schedule_attach(pend_task);
        }
    }
}

schedule

void schedule(void)
{
    tcb_t *cur_task = this_task();

    schedule_pending_check();

    uint8_t row = g_priority_map[g_priority_group];
    uint8_t re = g_priority_bitmap[row];
    uint8_t col = g_priority_map[re];
    uint8_t sched_priority = row * 8 + col;

    tcb_t *task = NULL;
    tcb_t *task_tmp = NULL;
    sched_queue_t *ready_queue = &g_readytorun[sched_priority];

    /* 找到需要调度的任务 */
    list_for_each_entry_safe(task, task_tmp, &ready_queue->tasks_head, link_head)
    {
        if (cur_task != task) 
        {
            /*
             * 如果要执行的任务不是当前任务则进行切换
             * 如果要执行的任务是当前任务，则不进行切换
             * 根据优先级抢占式调度，当前优先级高的任务不主动放弃，低优先级任务永远不能得到执行
             */
            task->task_state = TSTATE_TASK_RUNNING;
            g_current_task = task;

            /* 把当前任务从ready队列删除，并添加到pending队尾 */
            list_del(&task->link_head);
            list_add_tail(&task->link_head, &g_pendingtasks.tasks_head);

            task_switch(cur_task, task);
            break;
        }
    }
}