时间片调度算法issue解决后续及utest测试 10.00

发布于 2022-11-23 23:29:35 浏览：1444 订阅该版

[tocm]

之前针对时间片调度算法，写过一篇文章[关于时间片调度算法issue的分析与解决](https://club.rt-thread.org/ask/article/b3b36a52556382b2.html)

最近又仔细研究发现考虑不全，依然存在bug, 现进行修复并针对性设计一下utest测试实例。

## 存在部分任务不调度的情况

前一笔提交https://github.com/RT-Thread/rt-thread/pull/6232， 已经合并到了主线分支。

后来有社区伙伴，使用该最新分支出现了不调度的情况。看了一下原因：

![image-20221113221407406.png](https://oss-club.rt-thread.org/uploads/20221123/6aef517bfc1dbae09284eac2928c54d2.png.webp "image-20221113221407406.png")

是YIELD 状态位的清除过早了，导致后面 rt_schedule_insert_thread的根据YIELD 状态位来判断时间片是否用完就存在问题了。

当时临时给出的方案如下，社区伙伴测试后，他们的问题不复现，解决了。

![image-20221116214502846.png](https://oss-club.rt-thread.org/uploads/20221123/be6c5d926ba9aa2b16c2c2727eb752f7.png.webp "image-20221116214502846.png")

从本质上来看，这是修改不完整导致。是我的问题，当时认为方案二很简单，修改不多，大意了。但内心还是有疑问的，问什么我测试的时候没发现问题呢。加上当时内部小组讨论是重新理一下时间片的流程，看下还有什么漏洞，暂未提交该PR。最近搬完家，生活工作正常后，再次研究一下。

### 测试时为什么没发现

![image-20221113224031466.png](https://oss-club.rt-thread.org/uploads/20221123/acd1605d3a0e3208d5eec4f5b656a15e.png.webp "image-20221113224031466.png")

当时测试的情况，thread2,thread3 同优先级，低于 thread1。 结合上图和代码，仔细研究一下它们的调度过程：

1）A1时间点，rt_current_thread = thread2, 其时间片用完，置位 YIELD状态，进入一次调度。但该状态在是调用 rt_schedule_insert_thread 前被清零了。

![image-20221113230956074.png](https://oss-club.rt-thread.org/uploads/20221123/acc70acaf6d5e20118e9f77ef3a24939.png.webp "image-20221113230956074.png")

那么按照更改后的rt_schedule_insert_thread代码就会调用rt_list_insert_after把 thread2错误地插入到 其优先级ready_list的后面，即 list-> thread2-> thread3, 理论上应该是 list->thread3->thread2。

![image-20221113224530562.png](https://oss-club.rt-thread.org/uploads/20221123/e9b195f8b3e4cca346ba959adf706f97.png.webp "image-20221113224530562.png")

从rt_schedule_insert_thread 出来后，调用rt_schedule_remove_thread(to_thread);

![image-20221113225532969.png](https://oss-club.rt-thread.org/uploads/20221123/a4168090e61453f47c109d0e2109f5c1.png.webp "image-20221113225532969.png")

这个时候 to_thraed = thread3, 把它从ready_list移除，置为运行态，开始调度。结果ready_list变成了 list-> thread2

2）A2时间点，高优先级thread1打断了 thread3的运行，再次调用rt_list_insert_after把 thread3插入其优先级ready_list的后面，即list->thread3->thread2， 这次是正确的，后面确实继续调用了thread3。

3）A3时间点，thread3时间片用完，置位 YIELD状态，再次进入一次调度。同理的结果就是虽然错误的插入，list->thread3->thread2，然后是list->thread3。

**虽然从结果上是对的，但是不符合理论，然后在未覆盖的使用实例中（2个以上同等级线程）就出现了问题。**

### 复现不调度问题

新增一个同等级线程4，测试

![image-20221116212519471.png](https://oss-club.rt-thread.org/uploads/20221123/d9b854bbd128759a34328453e1e30edc.png.webp "image-20221116212519471.png")

该线程反转STM32F4Disc1的LED6

```
void led4_thread_entry( void *p_arg )
{
    for( ;; )
    {
        HAL_GPIO_WritePin(GPIOD, LD6_Pin, GPIO_PIN_SET);
        delay( 300 );
        HAL_GPIO_WritePin(GPIOD, LD6_Pin, GPIO_PIN_RESET);
        delay( 300 );
    }
}
```

当前在stm32f407disc1上测试环境如下

| thread  | priority | time slice | operation                                    |
| ------- | -------- | ---------- | -------------------------------------------- |
| thread1 | 6        | 5          | rt_thread_delay( 5 )， 5s 翻转一次LED4(PD12) |
| thread2 | 11       | 5          | delay( 300 )，自定义阻塞延时翻转LED3(PD13)   |
| thread3 | 11       | 2          | delay( 300 )，自定义阻塞延时翻转LED5(PD14)   |
| thread4 | 11       | 2          | delay( 300 )，自定义阻塞延时翻转LED6(PD15)   |

运行波形如下，很明显thread2没有调度。

![image-20221116212808864.png](https://oss-club.rt-thread.org/uploads/20221123/a726a2c8e42ee54a7c4192648b3cb33c.png.webp "image-20221116212808864.png")

按照当时的补丁，处理后

![image-20221116214852361.png](https://oss-club.rt-thread.org/uploads/20221123/5c4b5de789b7d023f5483ad8bfbca62f.png.webp "image-20221116214852361.png")

## 一波又起（顺序问题）

### 启动顺序问题

反复测试中，本能地抓了一下复位后的波形。

![image-20221116215129530.png](https://oss-club.rt-thread.org/uploads/20221123/cabed7e6fc3124fdfb31b085a05ecca1.png.webp "image-20221116215129530.png")

晕，启动顺序不对了，按照main中startup的顺序，调度顺序应该是 thread2 -> thread3 -> thread4,完全反调了。

```
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,
                    5);
    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);

rt_thread_init( &rt_led4_thread,
                    "LED3",
                    led4_thread_entry,
                    RT_NULL,
                    &rt_led4_thread_stack[0],
                    sizeof(rt_led4_thread_stack),
                    11,
                    2);

rt_thread_startup(&rt_led4_thread);
    while (1)
    {
        rt_thread_mdelay(1000);
    }

return RT_EOK;
}
```

发现了问题，其实很容易知道也是rt_schedule_insert_thread 修改后插入导致的问题，毕竟主要改了这个地方

![image-20221116221029346-1668904373390-12.png](https://oss-club.rt-thread.org/uploads/20221123/250ef9ab1f0afd64196078de6ad507b6.png.webp "image-20221116221029346-1668904373390-12.png")

rt_schedule_insert_thread 按照名字很好理解就算把 ready task 插入其优先级对应的ready_list，主要发生在线程状态发生变化（就绪，或者礼让）后。全局搜索一下

![image-20221116221448747.png](https://oss-club.rt-thread.org/uploads/20221123/38e43a47b38b461dd5dddadbdac91d81.png.webp "image-20221116221448747.png")

逐步查找，整理如下

| Call condition                                  | Callee                                       | Note                                                         |
| ----------------------------------------------- | -------------------------------------------- | ------------------------------------------------------------ |
| thread ready后 或者Yield礼让<br /> 产生的调度内 | rt_schedule->rt_schedule_insert_thread       | to_thread != rt_current_thread，才把当前线程插入ready_list   |
| 等待资源或Deley超时                             | _thread_timeout->rt_schedule_insert_thread   | 超时后，重新把thread 插入其ready_list 最后，然后调用rt_schedule |
| thread 改变优先级，导致的优先级readylist的变动  | rt_thread_control->rt_schedule_insert_thread | 控制类接口                                                   |
| 资源就绪, 主动把thread从suspend 恢复到ready状态 | rt_thread_resume->rt_schedule_insert_thread  | 这个调用后，一般紧接着会调用rt_schedule                      |

thread的启动最终调用了rt_schedule_insert_thread

```
rt_thread_startup
	->rt_thread_resume
		->rt_schedule_insert_thread
```

![image-20221117212103621.png](https://oss-club.rt-thread.org/uploads/20221123/63a3415fd250a69f824e114122be619f.png.webp "image-20221117212103621.png")

在插入前该thread的stat为2（RT_THREAD_SUSPEND），我猜是为了保持和正常resume的情况保持一致。

![image-20221117212309784.png](https://oss-club.rt-thread.org/uploads/20221123/45cdd3cac8655617fe9893b9ceda5625.png.webp "image-20221117212309784.png")

同时，YIELD状态位默认为0，即不礼让。也就是这个导致在rt_schedule_insert_thread 根据YIELD状态位判断出了问题：

> 1. 新的线程启动时，YIELD状态位为0，应该调用rt_list_insert_before，把它插入其ready_list的前面，按顺序最后调用
> 2. 但时间片调度要求，YIELD状态位为0（高优先级打断，时间片未用完），应该rt_list_insert_after把它插入到其ready_list的后面，下一次继续调用它
> 3. 当前满足了时间片的公平，使用rt_list_insert_after，却导致了正常线程的调度顺序发生反转。

### 更糟糕的情况

如果参考freertos的调度，启动顺序相反来看，倒也没什么。但是从刚刚的表格知道，rt_schedule_insert_thread更多时用在资源就绪，超时等动态的ready task插入。这个就存在很大的问题：

> 1. 同一优先级有多个任务在排队等待调度
> 2. 某一时刻thread1运行期间，因为等待资源或延时，suspended
> 3. 资源就绪或者超时后，回来的时候，YIELD状态位为0， 不能使用rt_list_insert_after把它直接插入到ready_list的后面，下一次就调用它

这就比如大家一起去服务中心排队办事，排到的某个人处理了一半，中间有事离开了。再回来的时候，不能插队到最前面，需要重新排！

稍微修改一下新建的thread4, 使用系统delay延时来测试：

```
void led4_thread_entry( void *p_arg )
{
    uint32_t i;

for( ;; )
    {
        for(i=0 ;i < 27; i++ )
        {
            HAL_GPIO_WritePin(GPIOD, LD6_Pin, GPIO_PIN_SET);
            delay( 300 );
            HAL_GPIO_WritePin(GPIOD, LD6_Pin, GPIO_PIN_RESET);
            delay( 300 );
        }
        rt_thread_delay( 1);
        for(i=0 ;i < 27; i++ )
        {
            HAL_GPIO_WritePin(GPIOD, LD6_Pin, GPIO_PIN_SET);
            delay( 300 );
            HAL_GPIO_WritePin(GPIOD, LD6_Pin, GPIO_PIN_RESET);
            delay( 300 );
        }
    }

}
```

再看下波形，会发现thread4已经不按照 thread2->thread3->thread4原始的顺序运行了。原因就是在A1时刻，1ms超时后，thread4被错误地插入到ready_list 头部，A2时刻直接运行了。

![image-20221119192000198.png](https://oss-club.rt-thread.org/uploads/20221123/a97c011e3eb168afb7c840fbd3ce19b5.png.webp "image-20221119192000198.png")

> B1,B2时刻thread3时间减少的原因，一开始认为也是 thread4乱插队导致的，最后发现是碰巧了，刚切换就碰上了tick中断发生，看上去就运行了一个tick。

### 解决办法

#### 方案一

resume线程后，也置位YIELD状态位，新ready的线程本来也就是插入到最后面的。这个理论上应该可以，但是改动点太多，风险过高；另外还要改变RT_THREAD_STAT_YIELD的定义，不太好。

```
#define RT_THREAD_STAT_YIELD            0x08                /**< indicate whether remaining_tick has been reloaded since last schedule */
#define RT_THREAD_STAT_YIELD_MASK       RT_THREAD_STAT_YIELD
```

#### 方案二

区分正常线程的和时间片的插入。这个折腾了很久，一开始一直有冲突

![image-20221117220844108.png](https://oss-club.rt-thread.org/uploads/20221123/9457c3645a45e90b61a728241246a68a.png.webp "image-20221117220844108.png")

后来单步调试时，多次观察thread->stat后， 豁然开朗：

> 1. 对于时间片用完 YIELD或者被高优先级打断的thread(有时间片剩余)，那么该线程一定是当前正在运行的，其插入前状态位是 RT_THREAD_RUNNING
>
>    这就比如：  **在车上，只有占到座了，才有让不让的问题**
>
> 2. 其他线程的插入，不管是刚启动的，还是刚刚资源就绪或者超时的，插入前状态位肯定不是RT_THREAD_RUNNING，一般应该是RT_THREAD_SUSPEND

然后我们只要在rt_schedule_insert_thread稍加调整就可以满足要求

![image-20221117222103562.png](https://oss-club.rt-thread.org/uploads/20221123/c25bf24b8220c14233f5a2c25d66b9f7.png.webp "image-20221117222103562.png")

> 1. if 内是时间片调度的插入处理
> 2. else内 是原有的插入处理
> 3. theead->stat 的 READY置位操作需要从if 前移到后面，保证RT_THREAD_RUNNING的状态用于判断。

##### 静态顺序验证

thread4使用阻塞延时，按启动顺序调度

![image-20221119194018055.png](https://oss-club.rt-thread.org/uploads/20221123/439795862275ac5783ff4853d64869f1.png.webp "image-20221119194018055.png")

##### 动态顺序验证

thread4使用delay延时

![image-20221119193721999.png](https://oss-club.rt-thread.org/uploads/20221123/43c1dbf5aa5aaeeb5795bbde9dc14286.png.webp "image-20221119193721999.png")

虽然看上去基本按照thread2->thread3->thread4在顺序执行，但是感觉还是有些不太对劲，放大时序

![image-20221119195036310.png](https://oss-club.rt-thread.org/uploads/20221123/d5deb7b124e86fa45b0ba99874ca88c1.png.webp "image-20221119195036310.png")

果然，thread4第一次运行时，中间1ms的延时，没起作用。如果参考A1时刻，5ms时基和tick中断的偏移，8ms前的A2时刻应该也有一次tick中断。就算是1ms延时碰巧很快就到了，也是往后边排队，为何又继续运行了呢？

下面根据debug 单步调试，追踪看下到底什么原因

![image-20221119201724761.png](https://oss-club.rt-thread.org/uploads/20221123/a23021b55b18b9ecd92f6315cdc05028.png.webp "image-20221119201724761.png")

一旦在rt_thread_sleep中打开中断，程序会立即跳转到熟悉的tick 中断里，说明刚延时启动定时器，还没来得及调度，就碰上了tick中断

![image-20221119201920165.png](https://oss-club.rt-thread.org/uploads/20221123/817ccaf9e5bd38e9df6b8d9323ffd190.png.webp "image-20221119201920165.png")

然后时间片减1，有剩余，跳到rt_check 继续执行

![image-20221119202137204.png](https://oss-club.rt-thread.org/uploads/20221123/e25481bea109d6bf87ebcdfda0363e65.png.webp "image-20221119202137204.png")

刚设置的1ms 延时，直接超时了，调用了timeout callback。

![image-20221119202648780.png](https://oss-club.rt-thread.org/uploads/20221123/daa9afb5be08b7a2bedbaaf2d61b9ad2.png.webp "image-20221119202648780.png")

由于太突然rt_current 还是thread4，而且带着suspend的状态进入了 rt_schedule_insert_thread，然后判定特殊情况，直接切到RT_THREAD_RUNNING，继续运行。退出systick 中断，回到 rt_thread_delay 还是继续运行。

![image-20221119203102993.png](https://oss-club.rt-thread.org/uploads/20221123/6d1614c50f4e0ac98140d7dd3a125b92.png.webp "image-20221119203102993.png")

原因找到了，和改动的插入没啥关系，逻辑上也不能说是错的。

> 如果让rt_thread_sleep完成调度,再开中断响应systick，rt_current_thread已改变，会导致time slice少减一次，后面会继续运行，对其他线程不太友好。
>
> 至于最后直接置位RT_THREAD_RUNNING，是否合适，看下blame 提交历史的描述
>
> 
![image-20221121220329606.png](https://oss-club.rt-thread.org/uploads/20221123/a4eb7f51c9a71c35047d7571171090e9.png.webp "image-20221121220329606.png")
>
> 和我们遇到的情况一样，提交认为对于立即resume的情况，应该继续持有调度，RUNNING
>
> 1. 对于资源阻塞任务，切到一半，资源就绪了（比如串口中断发生了信号量），这种快速响应很合适。有同优先级排队的话，都不知道你要让给他。
>
>  **就像前面柜台办事的人，少了一个文件资源，准备走了，突然有找到了，那就继续呗，后面排队的也没啥意见。**
>
> 2. 对于自延时1tick导致的立即resume，还没延时呢，理论上后响应合适些，不过问题也不大。
>
>  **这就提示我们谨慎使用1 tick 延时，刚好碰上tick中断，就是无效的**

## 极端情况

### 实例

上面有惊无险，但是也提示我们考虑极端情况： **同样是刚延时，未来得及调度被systick打断，碰巧时间片又用完了，会有什么情况**

再次修改thread4, 把它的时间片改为1，测试一下

![image-20221119204935510.png](https://oss-club.rt-thread.org/uploads/20221123/65f8e69cf6199a3c8d28e3c4d665b608.png.webp "image-20221119204935510.png")

好家伙，A2时刻thread4直接罢工了。

### 分析

继续dubug找原因，同样是带着suspend状态进入tick中断，这次thred4时间片使用完，置位RT_THREAD_STAT_YIELD，进入rt_schedule调度时

> + rt_current_thread = thred4
> + rt_current_thread->stat = RT_THREAD_STAT_YIELD |RT_THREAD_SUSPEND  (先suspend然后 yield)

![image-20221119210825832.png](https://oss-club.rt-thread.org/uploads/20221123/98b66d7bcbf52afa95bc183393243eb7.png.webp "image-20221119210825832.png")

然后if 语句未执行，need_insert_from_thread 未被置1，thread4带着RT_THREAD_STAT_YIELD |RT_THREAD_SUSPEND 奇怪的状态离开调度

![image-20221119211235051.png](https://oss-club.rt-thread.org/uploads/20221123/d13fb50042231e5ac248af2f2fbe6911.png.webp "image-20221119211235051.png")

然后同样的流程

```
rt_timer_check
	->_thread_timeout
		->rt_schedule_insert_thread
```

![image-20221119212739603.png](https://oss-club.rt-thread.org/uploads/20221123/e9729cba04f7f721c6ec9e0491c27ec3.png.webp "image-20221119212739603.png")

结果是插入的顺序是对的，但状态是 RT_THREAD_STAT_YIELD|RT_THREAD_READY。

目前为止也算不上啥大问题，再次运行时，正好被高优先级的thread1打断，错误的RT_THREAD_STAT_YIELD就导致系统认为thread4时间片用完了，让出调度，少了一次运行。

![image-20221119214600987.png](https://oss-club.rt-thread.org/uploads/20221123/b4d1ee493b964f763dd60e394c53207a.png.webp "image-20221119214600987.png")

> A2时刻的调度顺序如下：
>
> 1. systic中断产生，thread3先礼让切换到thread4
> 2. 紧接者timer check 发现高优先级的thread1延时超时，从thread4 切到 thread1, 同时误认为thread4要礼让 ，把它插入到ready_list前面
> 3. thread1 切换到 thread2

当前只是延时碰巧导致的极端情况，ipc等资源阻塞也有同样的问题（本质上也是起一个定时器延时，流程基本一致）

总结一下这个极端情况：

> 1. 延时或者资源阻塞时，碰到了systick中断
> 2. 当设置好定时器和suspend状态，开中断后，准备发起一次调度，却被tick中断抢占
> 3. tick中断里，如果碰巧又遇到当前thread的time slice使用完，会同时保留RT_THREAD_STAT_YIELD |RT_THREAD_SUSPEND进入礼让调度
> 4. 礼让调度里切换成功了，但thread的状态依然是RT_THREAD_STAT_YIELD |RT_THREAD_SUSPEND
> 5. 然后在timer check发现超时（**不一定在这次中断里**）或者 资源就绪唤醒thread ,均会导致插入后状态为RT_THREAD_STAT_YIELD |RT_THREAD_READY
> 6. 再次运行时，一旦被高优先级任务打断，就会误认为在礼让，在时间片未用完的情况下会提前退出调度，严重时，直接缺少一次调度。

需要同时满足 1，3，6 才会出现，算是比较极端，但还是有概率存在的, 是一直存在的一个bug，不管之前的还是现在的，只能保证最多错误礼让一次，然后被修正！

### 解决

设计上，RT_THREAD_STAT_YIELD明显是后来加的，不在一个MASK下，是或的关系，导致thread status兼容性不太好。

对极端流程分析来看，如果从开始的suspend状态解决，需要考虑很多。在5上更正状态是最合适，风险最小，改起来也比较简单：

直接在插入后，清除RT_THREAD_STAT_YIELD ，保证插入后均是RT_THREAD_READY状态，无复合态。稍微合并如下：

![image-20221119223849228.png](https://oss-club.rt-thread.org/uploads/20221123/9523b5fdab67e464c889d20239ed1f8f.png.webp "image-20221119223849228.png")

> 也就是确保插入后的thread 只处于一种RT_THREAD_READY状态，也应该是这种状态，合理简单的结果往往是正确的。

再测试一下，就正常了。

![image-20221119224017117.png](https://oss-club.rt-thread.org/uploads/20221123/d3808e5389309ad620634c47b9f81c48.png.webp "image-20221119224017117.png")

> A1时刻由于刚好碰上thread4中间的延时，切到其他thread了

# SMP处理

SMP多核的也需参考处理一下，具体参考PR, 不在赘述。

到此，我这边测出的时间片的问题，基本都解决了。

# Utest

时间片这个问题，一波几折，归根到底还是测试的不全面，未覆盖一些特殊的情况。没发现的问题才是最可怕的，尽可能全面的测试实例可以减少出错的概率。

现结合改动过程，写一下time slice 的utest 用例。

## 测试内容

时间片测试应包含如下内容

1. **达到设置的时间片，是否礼让**
2. **给定时间内，相同时间片，运行的时间是否相同（或者测试时间片比例）**
3. **同优先级的任务数>=3**
4. **无系统延时或资源阻塞的任务，相对调度顺序不变，静态顺序测试**
5. **有系统延时或资源阻塞的任务，相对调度顺序改变，动态顺序测试**

> 稍微合并一下：
>
> 1. 运行时间测试：包含测试项1，2，3；主要通过任务里的变量的累加，最后比较结果。
>
> 2. 调度顺序测试：包好3，4，5；计数一致，调度顺序不一定对（比如前半段一直运行A,后半段一直运行B），要保证轮询调度。

### 运行时间测试

参考已有的时间片测试，吃了线程不够的亏，再增加2个线程，一共4个同优先级测试（稍后会有线程用于延时，动态插入）

![image-20221120215826718.png](https://oss-club.rt-thread.org/uploads/20221123/aab9c83f88b5fc4554abe618fa59be1e.png.webp "image-20221120215826718.png")

新增线程

![image-20221123215607007.png](https://oss-club.rt-thread.org/uploads/20221123/c3395b132e01779cf08a55435243a218.png.webp "image-20221123215607007.png")

新增assert

![image-20221123215804367.png](https://oss-club.rt-thread.org/uploads/20221123/cd436e56fada75909ad6a5738a03b317.png "image-20221123215804367.png")

测试结果，pass

![image-20221123215924324.png](https://oss-club.rt-thread.org/uploads/20221123/fe8b411d96072f2d9f63460cd7f581ad.png.webp "image-20221123215924324.png")

> 允许部分误差

### 调度顺序测试

#### 静态测试

测试调用顺序，打算借助rt_scheduler_hook实现

```
void timer_slice_hook(struct rt_thread *from, struct rt_thread *to)
{
    if(__current_thread->current_priority + 2  == to->current_priority)
    {
        if(&(to->tlist) != timeslice_list.next)
        {
            if( (from->current_priority < __current_thread->current_priority + 2) && (to->tlist.next == timeslice_list.next) )
            {
                 /* high priority had interrupted thread to*/
            }
            else
            {
                timeslice_error++;
            }
        }
        else
        {

timeslice_list.next  = to->tlist.next;
        }
    }
}
```

> 1. 定义一个timeslice_list 初始化为时间片优先级ready_list，记录该优先级下一个该调用的thread
>
> ```
>     rt_scheduler_sethook(timer_slice_hook);
>     timeslice_list = rt_thread_priority_table[__current_thread->current_priority + 2];
> ```
>
> 2. 每次rt_schedule调用rt_scheduler_hook时，检查to thread是否正确
>
>    * 如果to thread == timeslice_list->next对应的thread, 更新timeslice_list.next  = to->tlist.next
>    * 如果to thread != timeslice_list->next对应的thread, 检查一下是不是有高优先级打断了当前的thread,且下一个thread未发生变动、
>
>           则认为正常，不更新timeslice_list，否则timeslice_error++。

新增assert

![image-20221123224147118.png](https://oss-club.rt-thread.org/uploads/20221123/1f9a7860a2b06a55aee839072aeb8aac.png.webp "image-20221123224147118.png")

utest run

![image-20221123224052845.png](https://oss-club.rt-thread.org/uploads/20221123/8251ed42d7c3edf0e29dfe4df727a273.png.webp "image-20221123224052845.png")

#### 动态测试

修改，thread4 新增一个1ms的延时， 不统计它计数，观察对其他thread的影响

![image-20221123224850584.png](https://oss-club.rt-thread.org/uploads/20221123/1932af155128e23719fc7e3c6d6b294d.png "image-20221123224850584.png")

utest run

![image-20221123225007304.png](https://oss-club.rt-thread.org/uploads/20221123/d66c02aaf7df9925f36b48190067b803.png.webp "image-20221123225007304.png")

## 最终测试用例

最后的动态测试，基本和下面的测试一样，包含了全部的测试内容，所以最终只使用这一个测试用例即可。

![image-20221119224017117.png](https://oss-club.rt-thread.org/uploads/20221123/d3808e5389309ad620634c47b9f81c48.png.webp "image-20221119224017117.png")

> A1时刻由于刚好碰上thread4中间的延时，切到其他thread了，属于正常，这个不影响 hook的判断。

## 反向测试

目前的utest看上去挺顺利的，是否真的有效，把最新的scheduler.c拉下来，替换工程里的，再测试一下

### master 测试

可以看出B1几乎没有调度，调度顺序错误了44次

![image-20221124080227041.png](https://oss-club.rt-thread.org/uploads/20221124/da3b7b849cb1f756585910d915ba9249.png.webp "image-20221124080227041.png")

### 打上第一个patch

虽然所有thread都调度了，但调度顺序错误了依旧严重

![image-20221124080810621.png](https://oss-club.rt-thread.org/uploads/20221124/62c2838485f16d889f98fece5c391685.png.webp "image-20221124080810621.png")

### 区分正常线程和礼让

调度顺序未发现问题

![image-20221124081530759.png](https://oss-club.rt-thread.org/uploads/20221124/74c20a45af3a6d509b3a3f3c1d259e86.png.webp "image-20221124081530759.png")

> 对于下面的极端情况，A2时刻刚调度被高优先级打断，因为YIELD提前置位错误礼让，理论上它也调度了，当前测试实例测试不出来。
>
> 
![image-20221119214600987.png](https://oss-club.rt-thread.org/uploads/20221124/b4d1ee493b964f763dd60e394c53207a.png.webp "image-20221119214600987.png")

PR:  https://github.com/RT-Thread/rt-thread/pull/6645

aozima 打赏了 10.00 元 2022-11-24 09:01:51

9 条评论

flyboy 2022-11-24

Do my self();

lebel 2023-05-05

这家伙很懒，什么也没写！

博主你好，你的时间片调度bug修复的很好！不过我仔细分析一下，感觉还遗漏了一个地方，就是时间片剩余值更新的点应该也要和切换标志RT_THREAD_STAT_YIELD的更新保持一致，具体可以看看我附的图片代码对比哈！就是还得麻烦你有空做测试哈，另外，我只改了单核处理器的部分，SMP的部分我不懂就没去动了。
图1:void rt_tick_increase(void)函数修改对比
![rt_tick_increase.png](https://oss-club.rt-thread.org/uploads/20230505/8a2b7ea6ed5048e04303667bf451c44b.png.webp)
void rt_tick_increase(void)函数修改后的代码
```c
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();

if (thread->remaining_tick != 0)        //确保非零才减1，该判断可要可不要，主要是担心:由于修改了时间片的赋值位置，意外出现了没有考虑到的情况，使得该变量变为0了而没有及时给赋值thread->init_tick
	{
    -- thread->remaining_tick;
	}
    if (thread->remaining_tick == 0)
    {
        /* change to initialized tick */
//        thread->remaining_tick = thread->init_tick;    //删除此处的赋值，改到rt_schedule_insert_thread函数中进行赋值
        thread->stat |= RT_THREAD_STAT_YIELD;

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

/* check timer */
    rt_timer_check();
}
```
图2:void rt_schedule_insert_thread(struct rt_thread *thread)函数修改对比
![rt_schedule_insert_thread.png](https://oss-club.rt-thread.org/uploads/20230505/870fa90f673d5c7b0ff127a2f6dd347f.png.webp)
void rt_schedule_insert_thread(struct rt_thread *thread)函数修改后的代码
```c
void rt_schedule_insert_thread(struct rt_thread *thread)
{
    rt_base_t level;

RT_ASSERT(thread != RT_NULL);

/* disable interrupt */
    level = 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;
    }

if((thread->stat & RT_THREAD_STAT_MASK) == RT_THREAD_RUNNING)
    {
        /* there is no time slices left(YIELD), inserting thread before ready list*/
        if((thread->stat & RT_THREAD_STAT_YIELD_MASK) == RT_THREAD_STAT_YIELD)
        {
            rt_list_insert_before(&(rt_thread_priority_table[thread->current_priority]),
                                  &(thread->tlist));
					thread->remaining_tick = thread->init_tick;    //由于时间片用完发起线程切换而更新时间片的值
        }
        /* there are some time slices left, inserting thread after ready list to schedule it firstly at next time*/
        else
        {
            rt_list_insert_after(&(rt_thread_priority_table[thread->current_priority]),
                                  &(thread->tlist));
					thread->remaining_tick = thread->remaining_tick;    //由于被高优先级抢占而发起线程切换，从而将线程插入就绪队列的首部，不更新时间片的值，此语句可要可不要，仅方便理解
        }
    }
    else
    {
        rt_list_insert_before(&(rt_thread_priority_table[thread->current_priority]),
                              &(thread->tlist));
					thread->remaining_tick = thread->init_tick;    //由于线程挂起(包括延时、获取资源被阻塞等)而发起线程切换，从而将线程插入就绪队列的尾部，需更新时间片的值
    }
    /* clear YIELD status*/
    thread->stat &= ~RT_THREAD_STAT_YIELD_MASK;
    /* READY thread, insert to ready queue */
    thread->stat = RT_THREAD_READY | (thread->stat & ~RT_THREAD_STAT_MASK);
    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(level);
}
```

blta 2023-05-05

这家伙很懒，什么也没写！

[@lebel](https://club.rt-thread.org/u/5d163a0e048baeaa)
你好，
参考rt_tick_increase函数
```
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. 关于thread->remaining_tick = 0的问题
刚刚看了最新代码，对一个刚建立的thread，对传入的时间片参数tick未作判断，
```
    /* tick init */
    thread->init_tick      = tick;
    thread->remaining_tick = tick;
```
如果手残给了一个0，加上无符号类型，一旦这个thread 获得运行，除非它主动放弃，否则其他同等优先级thread将无法运行。（算是一个小bug）
至于正常情况 tick > 0，现在的代码先减再判断，没有问题。

2.在插入readylist 后更新时间片
官方把这个操作放到了rt_tick_increase里：
先更新时间片，置位RT_THREAD_STAT_YIELD状态，再调用rt_schedule()把当前thread插入对应readylist

你这个方案把时间片的更新放到了后面，理论上没啥问题（暂未测试），可能更好理解些。 但改进的新方案要比现有的更精简，更高效，才能体现它被合入的价值。bug修复另说。

lebel 2023-05-05

这家伙很懒，什么也没写！

blta 2023-05-05

这家伙很懒，什么也没写！

CrazyH 2023-05-06

这家伙很懒，什么也没写！

lebel 2023-05-16

这家伙很懒，什么也没写！

[@blta](https://club.rt-thread.org/u/5a9ed626a8493bb2)
纯文字说明，没有贴图和代码，需要耐心点看描述并结合代码就知道我说的情况了哈！

考虑这类情况：有3个优先级相同的线程T1、T2、T3，他们的时间片均是10tick，某一段时间内，T1正在执行，T2和T3在就绪队列中。假设T1线程时间片剩余数在3tick的时候调用获取信号量Sem1资源的函数rt_sem_take()并且此时信号量值为0时，T1线程进行线程切换的关键步骤情况如下：
1.在rt_sem_take()中调用_ipc_list_suspend(),进而调用rt_thread_suspend()将当前线程状态变为RT_THREAD_SUSPEND，即线程T1的状态由RT_THREAD_RUNNING变为RT_THREAD_SUSPEND
2.回到rt_sem_take()接着调用rt_schedule()进行线程切换，且切换过程中信号量Sem1没有被release，即成功切换线程了，后续由线程T2、T3交替运行
在T2、T3交替运行期间的某一时刻(假设该时刻的状态是T2在运行、T3处在就绪列表中)由于中断触发了对信号量Sem1的release，即调用rt_sem_release()函数，其关键步骤如下:
1.在rt_sem_release()中调用_ipc_list_resume(),进而调用rt_thread_resume()，进而在rt_thread_resume()中调用rt_schedule_insert_thread()
2.在rt_schedule_insert_thread()中判断T1线程的状态，前面挂起的时候T1线程的状态已经变成RT_THREAD_SUSPEND，所以这里会进入到else的分支，即将T1线程插入该优先级就绪列表的队尾(也即插在T3线程的后面)
3.接下来就是等待T2、T3的时间片运行完后才轮到T1的运行，重点来了，由于目前源码的线程的时间片剩余数更新只在systick中断里面修改，所以此时T1时间片还是只有3tick，那么T1线程此次只能运行3个tick就又得重新交出CPU占用了，所以这次的调度对T1是不公平的
当然T1线程调用rt_sem_take()而挂起自己的时候时间片剩余数是可以在1~10之间的，我这里只是取3举例说明

再考虑另一类情况：同样有3个优先级相同的线程T1、T2、T3，他们的时间片均是10tick，某一段时间内，T1正在执行，T2和T3在就绪队列中。假设T1线程时间片剩余数在3tick的时候调用rt_thread_mdelay()延时并且大于2确保T1线程交出cpu进行线程切换，T1线程的运行情况和上面的信号量是类似的:
1.在rt_thread_mdelay()中调用rt_thread_sleep(),进而调用rt_thread_suspend()将当前线程状态变为RT_THREAD_SUSPEND，即线程T1的状态由RT_THREAD_RUNNING变为RT_THREAD_SUSPEND
2.中调用rt_thread_sleep()接着调用rt_schedule()进行线程切换，后续由线程T2、T3交替运行
在T2、T3交替运行期间的某一时刻(假设该时刻的状态是T2在运行、T3处在就绪列表中),在systick中断里面的rt_timer_check()判断延时到了后，其关键步骤如下:
1.在rt_timer_check()中调用线程自身的_thread_timeout(),进而调用rt_schedule_insert_thread()
2.在rt_schedule_insert_thread()中判断T1线程的状态，前面挂起的时候T1线程的状态已经变成RT_THREAD_SUSPEND，所以这里会进入到else的分支，即将T1线程插入该优先级就绪列表的队尾(也即插在T3线程的后面)
3.接下来就是等待T2、T3的时间片运行完后才轮到T1的运行，此时的情况就和上面的信号量情况是一样的了，同样对T1线程的调度不公平

其实上面的这两类情况如果是在时间片剩余数只剩1tick时发生的话，就很接近你自己分析到的一个极端情况了，我直接引用你的文字：“极端情况 实例 我们考虑极端情况： 同样是刚延时，未来得及调度被systick打断，碰巧时间片又用完了，会有什么情况
目前为止也算不上啥大问题，再次运行时，正好被高优先级的thread1打断，错误的RT_THREAD_STAT_YIELD就导致系统认为thread4时间片用完了，让出调度，少了一次运行。”
也就是说你这种情况下对thread4的调度少了一次，对thread4是不公平的。
而我上面说的情况相当于少T1调度了0.7次(如果是3tick挂起的时候)，对T1是不公平的。