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

本文由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/…

大抵的状况是：

低优先级的存在工作A（ticks = a），B(ticks =b)，; 高优先级工作C
如果高优先级 C内存在延时c 正好等于A的工夫片a
后果就是低优先级的工作只有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();
}

外面只做了两件事：

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

rt_schedule

Who calling

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

clock.c : 就是刚刚提及的在Systick中断中两种比拟重要的调度： 工夫片调度和超时调度
ipc.c ，mempool.c: 另外一种比拟重要的调度：资源阻塞和就绪调度（资源调度）
scheduler.c, thread.c：自身调度器和线程API的应用导致的间接API调度
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;
}

调度的过程大抵如下：

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

失去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闪动

rt_led1_thread：优先级9，工夫片1，延时 t1 = 5ms闪动LED4
rt_led2_thread：优先级11，工夫片t2 =4(ms)，自定义200延时闪动LED5
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”)]

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

源码剖析

rt_tick_increase

rt_schedule

Who calling

源码

失去to_thread的再判断

1. 以后优先级小于highest_ready_priority

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

3 须要切换新的工作

rt_schedule_insert_thread

问题

测试

创立线程

线程入口函数

不同工夫片对调度的影响

解决办法

计划一

计划二

计划三

rt_list_jump_next

重定义_scheduler_get_highest_priority_thread

简化rt_schedule

rt_system_scheduler_start

评论

发表回复取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

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

源码剖析

rt_tick_increase

rt_schedule

Who calling

源码

失去to_thread的再判断

1. 以后优先级小于highest_ready_priority

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

3 须要切换新的工作

rt_schedule_insert_thread

问题

测试

创立线程

线程入口函数

不同工夫片对调度的影响

解决办法

计划一

计划二

计划三

rt_list_jump_next

重定义_scheduler_get_highest_priority_thread

简化rt_schedule

rt_system_scheduler_start

评论

发表回复 取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

发表回复取消回复