-
关于时间片调度算法issue的分析与解决
本文由RT-Thread论坛用户@blta原创发布：https://club.rt-thread.org/ask/article/b3b36a52556382b2.html
在之前 rt_schedule中need_insert_from_thread的问题 提问中，笔者提出了当前时间片调度算法过于复杂，且高优先级一旦打断未执行完时间片的任务会导致该任务重新插入到其优先级readylist末尾，存在严重的不公平性（破坏了时间片的连续）。
当然笔者也PR了一个解决方案 https://github.com/RT-Thread/rt-thread/pull/5954 暂未合并
最近又有一个小伙伴发现了时间片调度的issue https://github.com/RT-Thread/rt-thread/issues/6092
大致的情况是：
- 低优先级的存在任务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(); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
里面只做了两件事：
- 当前任务的时间片递减， 如果用完了，置位RT_THREAD_STAT_YIELD状态，调用rt_schedule，
- 检测是否有任务的超时了（等待资源或延时超时），如果超时，最终也会调用rt_schedule
rt_schedule
Who calling
![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ywyhfOJu-1656404212734)(https://oss-club.rt-thread.org/uploads/20220627/13ff8ea0da8862bade41c25da763f670.png.webp "image-20220627091459627.png")]](https://1000bd.com/contentImg/2022/06/29/131837025.png)
排除componets中使用的情况，rt_schedule主要在下面情况中被使用
- clock.c : 就是刚刚提及的在Systick中断中两种比较重要的调度： 时间片调度和超时调度
- ipc.c ，mempool.c: 另外一种比较重要的调度： 资源阻塞和就绪调度（资源调度）
- scheduler.c, thread.c： 本身调度器和线程API的使用导致的直接API调度
- timer.c : 软定时器超时调度，使用的也是_thread_timeout超时函数，也是超时调度
鉴于 API调度一般使用在初始化阶段，Application运行中主要使用的是时间片调度，超时调度，资源调度 。后面的讨论中主要绕后三种展开：
![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-whmcx39c-1656404212735)(https://oss-club.rt-thread.org/uploads/20220627/ed3f79a1f6841b27ebc37cb431181a1c.png.webp "image-20220627095239360.png")]](https://1000bd.com/contentImg/2022/06/29/131837382.png)
源码
/** * @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
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
调度的过程大致如下：
- 关中断
- 判断调度是否上锁，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.org/uploads/20220627/8e468dc6ce6a747bed51e19a17a40b13.png.webp “image-20220626122316431.png”)]
之所以搞的这么复杂，是因为当前的调度策略是把运行的任务，移出了readylist，那么获取的highest_ready_priority，to_thread只是红色圈中的，还需要结合正在运行的 thread 再次判断，下面将结合下图说明上图中的1，2，3 中情况
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xhURNuMS-1656404212736)(https://oss-club.rt-thread.org/uploads/20220627/408b514a80ddf01e6577e9fa5fc55296.png.webp “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)- 1
这个很好理解：没有和当前任务优先级相同的任务，其优先级readylist为空,存在如下两种情况：
**1.1 低优先级就绪 **
存在 B,D,E3个任务， 当前 E 因资源阻塞或者延时中，B正在运行；某一时刻任务E就绪(资源就绪或者超时)，插入对应readylist后发起一次调度：highest_ready_priority = l > m
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VQLU1WKy-1656404212738)(https://oss-club.rt-thread.org/uploads/20220627/607c75814e7bd14301770d22e780b432.png.webp “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.org/uploads/20220627/607c75814e7bd14301770d22e780b432.png.webp “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)- 1
存在 B,C 两个同优先级的任务，当前C因资源阻塞或者延时中，B正在运行； 某一时刻C就绪，插入对应readylist后发起一次调度： highest_ready_priority = m
但此时B的时间片还未用完，依旧无需礼让切换，让C等着吧。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-X3FJcOVw-1656404212739)(https://oss-club.rt-thread.org/uploads/20220627/20d21df97d2686267e12a74dc7bab33a.png.webp “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)- 1
存在 B,C 两个同优先级的任务，当前C已经resume就绪， B正在运行；某一时刻B的时间片用完，thread->stat |= RT_THREAD_STAT_YIELD，发起一次调度： highest_ready_priority = m
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-89oiyinH-1656404212740)(https://oss-club.rt-thread.org/uploads/20220627/20d21df97d2686267e12a74dc7bab33a.png.webp “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)- 1
这个情况实际是不存在的:
(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)- 1
存在任务 ABCDE, 当前A，E因资源阻塞或者延时中，B正在运行；某一时刻A就绪,其任务优先级高于当前任务，虽然当前任务时间片有剩余，也必须切出
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tkRtvLTk-1656404212741)(https://oss-club.rt-thread.org/uploads/20220627/1f7ac97e450f611085a08f489750be2e.png.webp “image-20220627105736347.png”)]
高优先级就绪后会把当前任务插入的readylist最后，也就是这个插入导致了众多的问题出现。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-i1MVlmcM-1656404212741)(https://oss-club.rt-thread.org/uploads/20220627/273af8da13e953920652f03ce9761fbb.png.webp “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); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
可以明显看出，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.org/uploads/20220627/136d2c18a7212980e1894032f662abde.png.webp “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; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
线程入口函数
/* 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
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
不同时间片对调度的影响
1）t1 = 5, t2 = 4, t3=2
新就绪的任务优先级高于当前任务，当前任务时间片有剩余
通过逻辑分析仪抓取三个LED pin 电平
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-P6SkB3qQ-1656404212744)(https://oss-club.rt-thread.org/uploads/20220627/b6af85346d5e5c9237b221f2b651c5ef.png.webp “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.org/uploads/20220627/65dd10f9f351f67925e38fa7fae55d12.png.webp “image-20220627153223614.png”)]
还记得我们上面提到了3.2 不能同时满足的条件吗？
if (rt_current_thread->current_priority > highest_ready_priority && (rt_current_thread->stat & RT_THREAD_STAT_YIELD_MASK) != 0)- 1
只是因为软件的写法（第一次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.org/uploads/20220627/a2472bf1459bac299fef1be3c75dbd79.png.webp “image-20220627161546060.png”)]
这种情况造成的结果比较明显，导致thread3一直没有运行的机会了，也就是小伙伴发现的issue https://github.com/RT-Thread/rt-thread/issues/6092
从现象上看情况3是最极端，最严重的，但是你可以立即发现。 不像情况1，2虽然表面上每个thread还在执行，内部的时间片已经完全乱掉，往往这种隐形的issue会导致更加严重的后果。
解决办法
既然看到了时间片调度的众多issue,也知道了问题的原因：高优先级打断未执行完时间片的任务导致该任务被重新插入到其优先级readylist末尾
那么就开始着手解决。
方案一
先看下小伙伴同时提出的解决办法：https://github.com/RT-Thread/rt-thread/pull/6095/files
他增加了一个RT_THREAD_STAT_SCHEDULING 状态来判断和避免issue
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-891K9ZEV-1656404212747)(https://oss-club.rt-thread.org/uploads/20220627/db0821261606d7034e5769b518f70957.png.webp “image-20220627163838256.png”)]
这种做法应该没啥问题，暂未测试
方案二
直击问题本质，既然是插入的问题导致的，调整一下插入顺序即可
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dViIpV9g-1656404212748)(https://oss-club.rt-thread.org/uploads/20220627/41c355fb448e12f2f5a11a8ff6f76601.png.webp “image-20220627170547682.png”)]
除了时间片使用完，需要yield，插入其readylist的末尾，其他情况均插入readylist的头部
再次测试t1 = 5, t2 = 5, t3=2，结果如下：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FgkQYDXw-1656404212748)(https://oss-club.rt-thread.org/uploads/20220627/ca638c753cc4a2971af6d4565b67eff5.png.webp “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() */- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
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; \ }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
可以看出它再获取最高优先级后，会直接把readylist的index往后移动一次，获取下一个任务。虽然这个它的时间片ticks为常量1，但可以给我们提供一个很好的参考，没有remove, insert。
笔者之前PR的一个解决方案 https://github.com/RT-Thread/rt-thread/pull/5954 就是基于该方案
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; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
大致操作如下：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4BAt4UE9-1656404212749)(https://oss-club.rt-thread.org/uploads/20220627/305ae2f95eb79672b4ef013bf2199fde.png.webp “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,- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XWbd9Jhp-1656404212750)(https://oss-club.rt-thread.org/uploads/20220627/04d946e87daa7483def3b46fe7f1ee7d.png.webp “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)- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
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 */- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
同样测试t1 = 5, t2 = 5, t3=2，结果正常如下：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FP2FCDvh-1656404212751)(https://oss-club.rt-thread.org/uploads/20220627/a05b09d5595739809f8defa457ebdb38.png.webp “image-20220627180659240.png”)]
-
相关阅读:
解析eclipse和idea运行java程序的过程
leetcode/
Ubuntu搭建AI画图工具stable diffusion-webui
Android Studio入门——页面跳转
隧道HTTP API使用教程
《012.SpringBoot+vue之在线考试系统》【前后端分离&有开发文档】
vue面试经常会问的那些题
java: 错误: 无效的源发行版：17 【解决】
CentOS7 内核升级
vulnhub靶场之DRIPPING BLUES: 1
- 原文地址：https://blog.csdn.net/rtthreadiotos/article/details/125504677
