关于程序员:关于时间片调度算法issue的分析与解决

32次阅读

共计 17252 个字符，预计需要花费 44 分钟才能阅读完成。

本文由 RT-Thread 论坛用户 @blta 原创公布：https://club.rt-thread.org/as…

在之前 rt_schedule 中 need_insert_from_thread 的问题 发问中，笔者提出了以后工夫片调度算法过于简单，且高优先级一旦打断未执行完工夫片的工作会导致该工作从新插入到其优先级 readylist 开端，存在重大的不公平性（毁坏了工夫片的间断）。

当然笔者也 PR 了一个解决方案 https://github.com/RT-Thread/… 暂未合并

最近又有一个小伙伴发现了工夫片调度的 issue https://github.com/RT-Thread/…

大抵的状况是：

  1. 低优先级的存在工作 A（ticks = a），B(ticks =b)，; 高优先级工作 C
  2. 如果高优先级 C 内存在延时 c 正好等于 A 的工夫片 a
  3. 后果就是低优先级的工作只有 A 在始终运行，B 始终运行不了

这种状况的根本原因其实还是笔者之前提到的高优先级导致以后低优先级工作插入 readylist 地位不对的 issue,

上面笔者再次配重新整理一下这个问题，配合图例逐渐剖析源码并联合测试例程展现不同状况下该 issue 导致的问题，并尝试解决。

源码剖析

rt_tick_increase

/**
 * @brief    This function will notify kernel there is one tick passed.
 *           Normally, this function is invoked by clock ISR.
 */
void rt_tick_increase(void)
{
    struct rt_thread *thread;
    rt_base_t level;
    RT_OBJECT_HOOK_CALL(rt_tick_hook, ());

    level = rt_hw_interrupt_disable();

    /* increase the global tick */
#ifdef RT_USING_SMP
    rt_cpu_self()->tick ++;
#else
    ++ rt_tick;
#endif /* RT_USING_SMP */

    /* check time slice */
    thread = rt_thread_self();

    -- thread->remaining_tick;
    if (thread->remaining_tick == 0)
    {
        /* change to initialized tick */
        thread->remaining_tick = thread->init_tick;
        thread->stat |= RT_THREAD_STAT_YIELD;

        rt_hw_interrupt_enable(level);
        rt_schedule();}
    else
    {rt_hw_interrupt_enable(level);
    }

    /* check timer */
    rt_timer_check();}

外面只做了两件事：

  1. 当前任务的工夫片递加，如果用完了，置位 RT_THREAD_STAT_YIELD 状态，调用 rt_schedule，
  2. 检测是否有工作的超时了（期待资源或延时超时），如果超时，最终也会调用 rt_schedule

rt_schedule

Who calling

排除 componets 中应用的状况，rt_schedule 次要在上面状况中被应用

  1. clock.c : 就是刚刚提及的在 Systick 中断中两种比拟重要的调度：工夫片调度 和超时调度
  2. ipc.c，mempool.c: 另外一种比拟重要的调度：资源阻塞和就绪调度（资源调度）
  3. scheduler.c, thread.c：自身调度器和线程 API 的应用导致的间接API 调度
  4. timer.c : 软定时器超时调度，应用的也是_thread_timeout 超时函数，也是 超时调度

鉴于 API 调度 个别应用在初始化阶段，Application 运行中次要应用的是 工夫片调度，超时调度，资源调度。前面的探讨中次要绕后三种开展：

源码

/**
 * @brief This function will perform scheduling once. It will select one thread
 *        with the highest priority, and switch to it immediately.
 */
void rt_schedule(void)
{
    rt_base_t level;
    struct rt_thread *to_thread;
    struct rt_thread *from_thread;

    /* disable interrupt */
    level = rt_hw_interrupt_disable();

    /* check the scheduler is enabled or not */
    if (rt_scheduler_lock_nest == 0)
    {
        rt_ubase_t highest_ready_priority;

        if (rt_thread_ready_priority_group != 0)
        {
            /* need_insert_from_thread: need to insert from_thread to ready queue */
            int need_insert_from_thread = 0;

            to_thread = _scheduler_get_highest_priority_thread(&highest_ready_priority);

            if ((rt_current_thread->stat & RT_THREAD_STAT_MASK) == RT_THREAD_RUNNING)
            {if (rt_current_thread->current_priority < highest_ready_priority)
                {to_thread = rt_current_thread;}
                else if (rt_current_thread->current_priority == highest_ready_priority && (rt_current_thread->stat & RT_THREAD_STAT_YIELD_MASK) == 0)
                {to_thread = rt_current_thread;}
                else
                {need_insert_from_thread = 1;}
                rt_current_thread->stat &= ~RT_THREAD_STAT_YIELD_MASK;
            }

            if (to_thread != rt_current_thread)
            {
                /* if the destination thread is not the same as current thread */
                rt_current_priority = (rt_uint8_t)highest_ready_priority;
                from_thread         = rt_current_thread;
                rt_current_thread   = to_thread;

                RT_OBJECT_HOOK_CALL(rt_scheduler_hook, (from_thread, to_thread));

                if (need_insert_from_thread)
                {rt_schedule_insert_thread(from_thread);
                }

                rt_schedule_remove_thread(to_thread);
                to_thread->stat = RT_THREAD_RUNNING | (to_thread->stat & ~RT_THREAD_STAT_MASK);

                /* switch to new thread */
                RT_DEBUG_LOG(RT_DEBUG_SCHEDULER,
                        ("[%d]switch to priority#%d"
                         "thread:%.*s(sp:0x%08x),"
                         "from thread:%.*s(sp: 0x%08x)\n",
                         rt_interrupt_nest, highest_ready_priority,
                         RT_NAME_MAX, to_thread->name, to_thread->sp,
                         RT_NAME_MAX, from_thread->name, from_thread->sp));

#ifdef RT_USING_OVERFLOW_CHECK
                _rt_scheduler_stack_check(to_thread);
#endif /* RT_USING_OVERFLOW_CHECK */

                if (rt_interrupt_nest == 0)
                {extern void rt_thread_handle_sig(rt_bool_t clean_state);

                    RT_OBJECT_HOOK_CALL(rt_scheduler_switch_hook, (from_thread));

                    rt_hw_context_switch((rt_ubase_t)&from_thread->sp,
                            (rt_ubase_t)&to_thread->sp);

                    /* enable interrupt */
                    rt_hw_interrupt_enable(level);

#ifdef RT_USING_SIGNALS
                    /* check stat of thread for signal */
                    level = rt_hw_interrupt_disable();
                    if (rt_current_thread->stat & RT_THREAD_STAT_SIGNAL_PENDING)
                    {extern void rt_thread_handle_sig(rt_bool_t clean_state);

                        rt_current_thread->stat &= ~RT_THREAD_STAT_SIGNAL_PENDING;

                        rt_hw_interrupt_enable(level);

                        /* check signal status */
                        rt_thread_handle_sig(RT_TRUE);
                    }
                    else
                    {rt_hw_interrupt_enable(level);
                    }
#endif /* RT_USING_SIGNALS */
                    goto __exit;
                }
                else
                {RT_DEBUG_LOG(RT_DEBUG_SCHEDULER, ("switch in interrupt\n"));

                    rt_hw_context_switch_interrupt((rt_ubase_t)&from_thread->sp,
                            (rt_ubase_t)&to_thread->sp);
                }
            }
            else
            {rt_schedule_remove_thread(rt_current_thread);
                rt_current_thread->stat = RT_THREAD_RUNNING | (rt_current_thread->stat & ~RT_THREAD_STAT_MASK);
            }
        }
    }

    /* enable interrupt */
    rt_hw_interrupt_enable(level);

__exit:
    return;
}

调度的过程大抵如下：

  1. 关中断
  2. 判断调度是否上锁，rt_thread_ready_priority_group 是否为 0
  3. _scheduler_get_highest_priority_thread 获取以后最高优先级
  4. 和以后优先级再次比拟，确定实在的最高优先级
  5. 获取最高优先级 readylist 的第一个工作 to_thread
  6. to_thread 和 rt_current_thread 比拟
  7. 如果相等，简略设置状态，持续运行
  8. 如果不相等，把当前任务插入其优先级 readylist , 切换到 to_thread
  9. 开中断

失去 to_thread 的再判断

[外链图片转存失败, 源站可能有防盗链机制, 倡议将图片保留下来间接上传(img-lL4gjIqM-1656404212736)(https://oss-club.rt-thread.or… “image-20220626122316431.png”)]

之所以搞的这么简单，是因为以后的调度策略是把运行的工作，移出了 readylist，那么获取的 highest_ready_priority，to_thread 只是红色圈中的，还须要联合正在运行的 thread 再次判断，上面将联合下图阐明上图中的 1，2，3 中状况

[外链图片转存失败, 源站可能有防盗链机制, 倡议将图片保留下来间接上传(img-xhURNuMS-1656404212736)(https://oss-club.rt-thread.or… “image-20220627104008931.png”)]

假如 以后 rt_thread_priority_table 中存在三个优先级列表，下标别离为 h, m, l (h<m<l), 别离代表了高，中，低三个优先级

1. 以后优先级小于 highest_ready_priority
 if (rt_current_thread->current_priority < highest_ready_priority)

这个很好了解：没有和当前任务优先级雷同的工作，其优先级 readylist 为空, 存在如下两种状况：

1.1 低优先级就绪

存在 B,D,E3 个工作，以后 E 因资源阻塞或者延时中，B 正在运行；某一时刻工作 E 就绪(资源就绪或者超时)，插入对应 readylist 后发动一次调度：highest_ready_priority = l > m

[外链图片转存失败, 源站可能有防盗链机制, 倡议将图片保留下来间接上传(img-VQLU1WKy-1656404212738)(https://oss-club.rt-thread.or… “image-20220627100541109.png”)]

对于某一工作的阻塞，图例仅展现资源阻塞（调度），或者延时阻塞（调度）中的一种，下同，不再阐明

1.2 以后运行工作的工夫片用完

同样存在 B,D,E 3 个工作，以后 B 在运行; 某一时刻 B 的工夫片用完，thread->stat |= RT_THREAD_STAT_YIELD，发动一次调度：highest_ready_priority = l > m

因为最高优先级 m 下，只有 B 一个工作，所以只管其工夫片曾经应用完，还会复位 ticks，再次运行。

[外链图片转存失败, 源站可能有防盗链机制, 倡议将图片保留下来间接上传(img-WaWLFd2E-1656404212739)(https://oss-club.rt-thread.or… “image-20220627100541109.png”)]

这两种状况，最初运行的还是当前任务

2. 以后优先级等于 highest_ready_priority，且当前任务工夫片未用完
if (rt_current_thread->current_priority == highest_ready_priority && (rt_current_thread->stat & RT_THREAD_STAT_YIELD_MASK) == 0)

存在 B,C 两个同优先级的工作，以后 C 因资源阻塞或者延时中，B 正在运行；某一时刻 C 就绪，插入对应 readylist 后发动一次调度：highest_ready_priority = m

但此时 B 的工夫片还未用完，仍旧无需礼让切换，让 C 等着吧。

[外链图片转存失败, 源站可能有防盗链机制, 倡议将图片保留下来间接上传(img-X3FJcOVw-1656404212739)(https://oss-club.rt-thread.or… “image-20220627104748330.png”)]

最初运行的也当前任务

3 须要切换新的工作

能够间接列出残余的三种状况，

3.1 以后优先级等于 highest_ready_priority，且当前任务工夫片用完

if (rt_current_thread->current_priority == highest_ready_priority && (rt_current_thread->stat & RT_THREAD_STAT_YIELD_MASK) != 0)

存在 B,C 两个同优先级的工作，以后 C 曾经 resume 就绪，B 正在运行；某一时刻 B 的工夫片用完，thread->stat |= RT_THREAD_STAT_YIELD，发动一次调度：highest_ready_priority = m

[外链图片转存失败, 源站可能有防盗链机制, 倡议将图片保留下来间接上传(img-89oiyinH-1656404212740)(https://oss-club.rt-thread.or… “image-20220627104801028.png”)]

须要礼让，把当前任务 B 插入对应优先级 readylist 后, 而后切换到 C

3.2 以后优先级大于 highest_ready_priority，且当前任务工夫片用完

if (rt_current_thread->current_priority > highest_ready_priority && (rt_current_thread->stat & RT_THREAD_STAT_YIELD_MASK) != 0)

这个状况理论是不存在的:

(rt_current_thread->stat & RT_THREAD_STAT_YIELD_MASK) != 0 示意工夫片用完了，是通过 rt_tick_increase->rt_schedule，即工夫片用完，置位 RT_THREAD_STAT_YIELD 后发动的一次 rt_schedule 调度，调度完结会革除 RT_THREAD_STAT_YIELD 状态

rt_current_thread->current_priority > highest_ready_priority 示意高优先级就绪，是通过 rt_tick_increase->rt_timer_check->_thread_timeout->rt_schedule

即高优先级的超时函数触发调度一次 rt_schedule 调度

很显著，这两种调度不会同时产生，就算 rt_tick_increase->rt_schedule 先产生，也会革除 RT_THREAD_STAT_YIELD 状态，导致条件不满足。

3.3 以后优先级大于 highest_ready_priority，且当前任务工夫片未用完

if (rt_current_thread->current_priority > highest_ready_priority && (rt_current_thread->stat & RT_THREAD_STAT_YIELD_MASK) == 0)

存在工作 ABCDE, 以后 A，E 因资源阻塞或者延时中，B 正在运行；某一时刻 A 就绪, 其工作优先级高于当前任务，尽管当前任务工夫片有残余，也必须切出

[外链图片转存失败, 源站可能有防盗链机制, 倡议将图片保留下来间接上传(img-tkRtvLTk-1656404212741)(https://oss-club.rt-thread.or… “image-20220627105736347.png”)]

高优先级就绪后会把当前任务插入的 readylist 最初，也就是这个插入导致了泛滥的问题呈现。

[外链图片转存失败, 源站可能有防盗链机制, 倡议将图片保留下来间接上传(img-i1MVlmcM-1656404212741)(https://oss-club.rt-thread.or… “image-20220626121200429.png”)]

rt_schedule_insert_thread

void rt_schedule_insert_thread(struct rt_thread *thread)
{
    register rt_base_t temp;

    RT_ASSERT(thread != RT_NULL);

    /* disable interrupt */
    temp = rt_hw_interrupt_disable();

    /* it's current thread, it should be RUNNING thread */
    if (thread == rt_current_thread)
    {thread->stat = RT_THREAD_RUNNING | (thread->stat & ~RT_THREAD_STAT_MASK);
        goto __exit;
    }

    /* READY thread, insert to ready queue */
    thread->stat = RT_THREAD_READY | (thread->stat & ~RT_THREAD_STAT_MASK);
    /* insert thread to ready list */
    rt_list_insert_before(&(rt_thread_priority_table[thread->current_priority]),
                          &(thread->tlist));

    RT_DEBUG_LOG(RT_DEBUG_SCHEDULER, ("insert thread[%.*s], the priority: %d\n",
                                      RT_NAME_MAX, thread->name, thread->current_priority));

    /* set priority mask */
#if RT_THREAD_PRIORITY_MAX > 32
    rt_thread_ready_table[thread->number] |= thread->high_mask;
#endif /* RT_THREAD_PRIORITY_MAX > 32 */
    rt_thread_ready_priority_group |= thread->number_mask;

__exit:
    /* enable interrupt */
    rt_hw_interrupt_enable(temp);
}

能够显著看出，rt_schedule_insert_thread 调用的是 rt_list_insert_before，即把当然运行工作插入到其优先级 readylist 的最初

问题

因为以后运行线程是 remove 出 readylist 的，再插入 readylist 是必须的，然而应用 rt_list_insert_before 把未执行完工夫片的工作插入到 readylist 的最初面，下次轮到该优先级时，会间接执行 C，B 的工夫片被分成了两次或以上来执行，同理 C 也可能面临同样的状况。这就导致了很多问题。

[外链图片转存失败, 源站可能有防盗链机制, 倡议将图片保留下来间接上传(img-v4OWJzBz-1656404212743)(https://oss-club.rt-thread.or… “image-20220627144433820.png”)]

测试

测试环境：基于 stm32f4disc1 开发板，创立 3 个线程别离管制 LED3,LED4,LED5 闪动

  1. rt_led1_thread：优先级 9，工夫片 1，延时 t1 = 5ms 闪动 LED4
  2. rt_led2_thread：优先级 11，工夫片 t2 =4(ms)，自定义 200 延时闪动 LED5
  3. rt_led3_thread：优先级 11，工夫片 t3 = 2(ms)，自定义 300 延时闪动 LED3

创立线程

int main(void)
{
    rt_thread_init( &rt_led1_thread,                 
                    "LED1",                          
                    led1_thread_entry,            
                    RT_NULL,                       
                    &rt_led1_thread_stack[0],       
                    sizeof(rt_led1_thread_stack),  
                    6,
                    1);                               
    rt_thread_startup(&rt_led1_thread);
    
    rt_thread_init( &rt_led2_thread,                 
                    "LED2",                          
                    led2_thread_entry,              
                    RT_NULL,                       
                    &rt_led2_thread_stack[0],     
                    sizeof(rt_led2_thread_stack),
                    11,
                    4);                         
    rt_thread_startup(&rt_led2_thread);
    
    
    rt_thread_init( &rt_led3_thread,       
                    "LED3",               
                    led3_thread_entry,        
                    RT_NULL,                   
                    &rt_led3_thread_stack[0],     
                    sizeof(rt_led3_thread_stack),  
                    11,
                    2);                         
    
    rt_thread_startup(&rt_led3_thread);
    while (1)
    {rt_thread_mdelay(1000);
    }

    return RT_EOK;
}

线程入口函数

/* customer short delay  */
void delay (uint32_t count)
{for(; count!=0; count--);
}

void led1_thread_entry(void *p_arg)
{for( ;;)
    {HAL_GPIO_WritePin(GPIOD, LD4_Pin, GPIO_PIN_SET);
        rt_thread_delay(5);
        HAL_GPIO_WritePin(GPIOD, LD4_Pin, GPIO_PIN_RESET);
        rt_thread_delay(5);
    }
}

void led2_thread_entry(void *p_arg)
{for( ;;)
    {HAL_GPIO_WritePin(GPIOD, LD5_Pin, GPIO_PIN_SET);
        delay(300);
        HAL_GPIO_WritePin(GPIOD, LD5_Pin, GPIO_PIN_RESET);
        delay(300);
    }
}

void led3_thread_entry(void *p_arg)
{for( ;;)
    {HAL_GPIO_WritePin(GPIOD, LD3_Pin, GPIO_PIN_SET);
        delay(300);
        HAL_GPIO_WritePin(GPIOD, LD3_Pin, GPIO_PIN_RESET);
        delay(300);
    }
}

不同工夫片对调度的影响

1）t1 = 5, t2 = 4, t3=2

新就绪的工作优先级高于当前任务，当前任务工夫片有残余

通过逻辑分析仪抓取三个 LED pin 电平
[外链图片转存失败, 源站可能有防盗链机制, 倡议将图片保留下来间接上传(img-P6SkB3qQ-1656404212744)(https://oss-club.rt-thread.or… “image-20220627152027184.png”)]

波形中能够显著看出 thread2 工夫片 4ms（4 ticks)，执行 3ms 后因为高优先级 thread1 打断，残余的 1ms 会在 thread3 执行完后才执行。thread3 甚至呈现了间断执行的状况，稍后剖析。总之工夫片调度齐全乱掉了。

2）t1 = 5, t2 = 3, t3=2

新就绪的工作优先级高于当前任务，当前任务工夫片无残余

[外链图片转存失败, 源站可能有防盗链机制, 倡议将图片保留下来间接上传(img-vobwJCEA-1656404212745)(https://oss-club.rt-thread.or… “image-20220627153223614.png”)]

还记得咱们下面提到了 3.2 不能同时满足的条件吗？

if (rt_current_thread->current_priority > highest_ready_priority && (rt_current_thread->stat & RT_THREAD_STAT_YIELD_MASK) != 0)

只是因为软件的写法（第一次 rt_scheduler 后革除了 RT_THREAD_STAT_YIELD 状态），这个条件不能同时满足。从波形图看这两条件是能够同时满足的：

某一个 tick 中断了，线程 thread2 的工夫片用完了，工夫片调度度后，rt_timer_check 发现正好有一个高优先级线程超时了，于是先后触发了两次调度：

第一次：工夫片调度，rt_current = thread3, rt_thread_priority_table[11] -> thread2

第二次：超时调度，把 rt_current 插入其 readylist , rt_thread_priority_table[11] -> thread2–>thread3, rt_current = thread2

而后，当高优先级 thread1 再次阻塞时，首先运行的还是 thread2。

这就是为什么 thread2 间断运行了两个 t2(3*2)，同理 thread3 也是，和咱们冀望的轮流执行不统一。

3）t1 = 5, t2 = 5, t3=x (t2/t3 =5)

高优先级的延时正好等于某一低优先级线程的工夫片

[外链图片转存失败, 源站可能有防盗链机制, 倡议将图片保留下来间接上传(img-48nRTlqD-1656404212746)(https://oss-club.rt-thread.or… “image-20220627161546060.png”)]

这种状况造成的后果比拟显著，导致 thread3 始终没有运行的机会了，也就是小伙伴发现的 issue https://github.com/RT-Thread/…

从景象上看状况 3 是最极其，最重大的，然而你能够立刻发现。不像状况 1，2 尽管外表上每个 thread 还在执行，外部的工夫片曾经齐全乱掉，往往这种隐形的 issue 会导致更加重大的结果。

解决办法

既然看到了工夫片调度的泛滥 issue, 也晓得了问题的起因：高优先级打断未执行完工夫片的工作导致该工作被从新插入到其优先级 readylist 开端

那么就开始着手解决。

计划一

先看下小伙伴同时提出的解决办法：https://github.com/RT-Thread/…

他减少了一个 RT_THREAD_STAT_SCHEDULING 状态来判断和防止 issue

[外链图片转存失败, 源站可能有防盗链机制, 倡议将图片保留下来间接上传(img-891K9ZEV-1656404212747)(https://oss-club.rt-thread.or… “image-20220627163838256.png”)]

这种做法应该没啥问题，暂未测试

计划二

直击问题实质，既然是插入的问题导致的，调整一下插入程序即可

[外链图片转存失败, 源站可能有防盗链机制, 倡议将图片保留下来间接上传(img-dViIpV9g-1656404212748)(https://oss-club.rt-thread.or… “image-20220627170547682.png”)]

除了工夫片应用完，须要 yield，插入其 readylist 的开端，其余状况均插入 readylist 的头部

再次测试 t1 = 5, t2 = 5, t3=2，后果如下：

[外链图片转存失败, 源站可能有防盗链机制, 倡议将图片保留下来间接上传(img-FgkQYDXw-1656404212748)(https://oss-club.rt-thread.or… “image-20220627165958080.png”)]

能够看到，ticks 间断执行了，线程没有反复执行，没有跳过，也没有不被执行的，完满解决。

计划三

更近一步，可不可以不把运行的 thread 移除 readylist 呢？如果能够，没有 remove, 也就没有了 insert, 没有了 issue

其实 FreeRTOS 应用的就是这种计划：

taskSELECT_HIGHEST_PRIORITY_TASK()

    #define taskSELECT_HIGHEST_PRIORITY_TASK()                                                        \
    {                                                                                                \
    UBaseType_t uxTopPriority;                                                                        \
                                                                                                    \
        /* Find the highest priority list that contains ready tasks. */                                \
        portGET_HIGHEST_PRIORITY(uxTopPriority, uxTopReadyPriority);                                \
        configASSERT(listCURRENT_LIST_LENGTH( &( pxReadyTasksLists[ uxTopPriority] ) ) > 0 );        \
        listGET_OWNER_OF_NEXT_ENTRY(pxCurrentTCB, &( pxReadyTasksLists[ uxTopPriority] ) );        \
    } /* taskSELECT_HIGHEST_PRIORITY_TASK() */

listGET_OWNER_OF_NEXT_ENTRY(pxTCB, pxList)

#define listGET_OWNER_OF_NEXT_ENTRY(pxTCB, pxList)                                        \
{                                                                                            \
List_t * const pxConstList = (pxList);                                                    \
    /* Increment the index to the next item and return the item, ensuring */                \
    /* we don't return the marker used at the end of the list.  */                            \
    (pxConstList)->pxIndex = (pxConstList)->pxIndex->pxNext;                            \
    if(( void *) (pxConstList)->pxIndex == (void *) &(( pxConstList)->xListEnd ) )    \
    {                                                                                        \
        (pxConstList)->pxIndex = (pxConstList)->pxIndex->pxNext;                        \
    }                                                                                        \
    (pxTCB) = (pxConstList)->pxIndex->pvOwner;                                            \
}

能够看出它再获取最高优先级后，会间接把 readylist 的 index 往后挪动一次，获取下一个工作。尽管这个它的工夫片 ticks 为常量 1，但能够给咱们提供一个很好的参考，没有 remove, insert。

笔者之前 PR 的一个解决方案 https://github.com/RT-Thread/… 就是基于该计划

rt_list_jump_next

尽管 rt_list_t 也是一个双向链表，然而少了一个成员变量 index, 不能像 FreeRTOS 那样间接挪动实现工夫片的调度

首先咱们须要新增一个 rt_list_t 操作函数 rt_list_jump_next，实现 rt_list_t 头部往后挪动一次，同时要保障 list 成员绝对程序不变

/**

 * @brief move the list to its next's next position
   *
 * @param l list to insert it
   */
   rt_inline void rt_list_jump_next(rt_list_t *l)
   {
   l->next->prev = l->prev;
   l->prev->next = l->next;


    l->prev = l->next;
    
    l->next->next->prev = l;
    l->next = l->next->next;
    
    l->prev->next = l;

}

大抵操作如下：

[外链图片转存失败, 源站可能有防盗链机制, 倡议将图片保留下来间接上传(img-4BAt4UE9-1656404212749)(https://oss-club.rt-thread.or… “image-20220627182045409.png”)]

这种间接挪动 list head 的做法，一次调度会有 6 次指针赋值操作，

而原来的一次调度 remove（4 次）, insert（4 次）加起来是 8 次指针赋值操作

重定义_scheduler_get_highest_priority_thread

--- a/src/scheduler.c
+++ b/src/scheduler.c
@@ -180,6 +180,19 @@ static struct rt_thread* _scheduler_get_highest_priority_thread(rt_ubase_t *high
     highest_ready_priority = __rt_ffs(rt_thread_ready_priority_group) - 1;
 #endif /* RT_THREAD_PRIORITY_MAX > 32 */

+    /* if current thread is yield , move the head of priority list to next and change its status to READY */
+    if((rt_current_thread->stat & RT_THREAD_STAT_YIELD_MASK) != 0)
+    {+        if(rt_current_thread->tlist.next != rt_current_thread->tlist.prev)
+        {
+            /* multiple threads, move the list head to next */
+            rt_list_jump_next(&rt_thread_priority_table[rt_current_thread->current_priority]);
+        }
+
+        /* clear YIELD and ready thread*/
+        rt_current_thread->stat = RT_THREAD_READY | (rt_current_thread->stat & ~(RT_THREAD_STAT_YIELD_MASK|RT_THREAD_STAT_MASK));
+    }
+
     /* get highest ready priority thread */
     highest_priority_thread = rt_list_entry(rt_thread_priority_table[highest_ready_priority].next,
                               struct rt_thread,

[外链图片转存失败, 源站可能有防盗链机制, 倡议将图片保留下来间接上传(img-XWbd9Jhp-1656404212750)(https://oss-club.rt-thread.or… “image-20220627175149148.png”)]

简化 rt_schedule

下面的剖析可知，rt_schedule 之所以搞的简单，是因为获取的 highest_ready_priority，to_thread 不蕴含对以后正在运行 thread 的计算。当初咱们不把 rt_current_thread 移除其 readylist, 取得的 highest_ready_priority，to_thread 就是最终的

@@ -258,7 +271,6 @@ void rt_system_scheduler_start(void)
     rt_current_thread = to_thread;
 #endif /* RT_USING_SMP */

-    rt_schedule_remove_thread(to_thread);
     to_thread->stat = RT_THREAD_RUNNING;

     /* switch to new thread */
@@ -436,28 +448,8 @@ void rt_schedule(void)

         if (rt_thread_ready_priority_group != 0)
         {
-            /* need_insert_from_thread: need to insert from_thread to ready queue */
-            int need_insert_from_thread = 0;
-
             to_thread = _scheduler_get_highest_priority_thread(&highest_ready_priority);

-            if ((rt_current_thread->stat & RT_THREAD_STAT_MASK) == RT_THREAD_RUNNING)
-            {-                if (rt_current_thread->current_priority < highest_ready_priority)
-                {
-                    to_thread = rt_current_thread;
-                }
-                else if (rt_current_thread->current_priority == highest_ready_priority && (rt_current_thread->stat & RT_THREAD_STAT_YIELD_MASK) == 0)
-                {
-                    to_thread = rt_current_thread;
-                }
-                else
-                {
-                    need_insert_from_thread = 1;
-                }
-                rt_current_thread->stat &= ~RT_THREAD_STAT_YIELD_MASK;
-            }
-
             if (to_thread != rt_current_thread)
             {
                 /* if the destination thread is not the same as current thread */
@@ -467,12 +459,6 @@ void rt_schedule(void)

                 RT_OBJECT_HOOK_CALL(rt_scheduler_hook, (from_thread, to_thread));

-                if (need_insert_from_thread)
-                {-                    rt_schedule_insert_thread(from_thread);
-                }
-
-                rt_schedule_remove_thread(to_thread);
                 to_thread->stat = RT_THREAD_RUNNING | (to_thread->stat & ~RT_THREAD_STAT_MASK);

                 /* switch to new thread */
@@ -531,7 +517,6 @@ void rt_schedule(void)
             }
             else
             {-                rt_schedule_remove_thread(rt_current_thread);
                 rt_current_thread->stat = RT_THREAD_RUNNING | (rt_current_thread->stat & ~RT_THREAD_STAT_MASK);
             }
         }
(END)

rt_system_scheduler_start

@@ -258,7 +271,6 @@ void rt_system_scheduler_start(void)
     rt_current_thread = to_thread;
 #endif /* RT_USING_SMP */

-    rt_schedule_remove_thread(to_thread);
     to_thread->stat = RT_THREAD_RUNNING;

     /* switch to new thread */

同样测试 t1 = 5, t2 = 5, t3=2，后果失常如下：

[外链图片转存失败, 源站可能有防盗链机制, 倡议将图片保留下来间接上传(img-FP2FCDvh-1656404212751)(https://oss-club.rt-thread.or… “image-20220627180659240.png”)]

正文完
程序员
发表至： 程序员
2022-06-28
 0
关于程序员:大数据MapReduce是什么
关于程序员:变量与指针变量
关于程序员:今年的情人节给心爱的她一个不一样的礼物吧
关于程序员:Restful-API-接口设计标准及规范