调度

初始化

  1. 根据支持的最大优先级,初始化不同的链表
1
2
3
4
5
6
7
8
9

for (offset = 0; offset < RT_THREAD_PRIORITY_MAX; offset ++)

{

    rt_list_init(&rt_thread_priority_table[offset]);

}

  1. 初始化就绪优先级组
  2. 优先级>32, 初始化线程就绪表

位图

  • 软件实现

RT-Thread的位图调度算法分析

一种新的高效的寻找字节最低非0位的有效算法

  • 硬件实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

__asm int __rt_ffs(int value)

{

    CMP     r0, #0x00     // 比较寄存器r0和0，设置条件标志

    BEQ     exit          // 如果r0等于0（即输入值为0），则跳转到exit标签


    RBIT    r0, r0        // 反转r0中的位，最低位变为最高位，最高位变为最低位

    CLZ     r0, r0        // 计算r0中前导零的数量

    ADDS    r0, r0, #0x01 // 将前导零的数量加1，因为位位置从1开始计数


exit

    BX      lr            // 返回到调用者

}

插入线程

image-20240512142100156

  1. 插入的线程时间片用完或者发生了让步(YIELD),证明该线程需要优先执行,将其插入到链表头部;
  2. 否则,还是时间片未走完,将其插入到链表尾部;

3.rt_thread_ready_priority_group置位,用于更快确认系统使用了什么优先级任务

删除线程

  1. 从链表中删除线程
  2. 判断该优先级任务链表是否为空,为空则清除 rt_thread_ready_priority_group中的相关置位标志.

线程启动

  1. 线程状态设置为 RT_THREAD_SUSPEND

2.number_mask = 1L << RT_SCHED_PRIV(thread).current_priority;

系统启动

  1. 调度程序获取最高优先级线程 _scheduler_get_highest_priority_thread
  • 注意到 rt_thread_ready_priority_group在初始化时置0
  • 线程创建启动后,将会把 rt_thread_ready_priority_group置位,用于更快确认系统使用了什么优先级任务

例如必须创建的空闲线程,其线程优先级为``RT_THREAD_PRIORITY_MAX - 1`

  1. 获得最高优先级的第一个线程作为 current_thread, 从就绪列表中删除该线程,切换线程状态为 RT_THREAD_RUNNING
  • 为什么要删除当前线程?

将线程从就绪队列中移除。这是因为，当线程被调度并开始运行时，它就不再处于就绪状态，因此需要从就绪队列中移除。当线程完成其任务或者被阻塞时，它会再次被添加到就绪队列中，等待下一次的调度。这种设计可以确保就绪队列中始终只包含那些实际上处于就绪状态的线程，从而提高调度的效率和准确性。

  1. 执行线程切换 rt_hw_context_switch_to
  • 这个函数只有目标线程，没有来源线程。
  • 只在第一次启动时在rt_system_scheduler_start()中调用。
  • 会设置rt_interrupt_to_thread为目标线程的地址。
  • 会设置rt_interrupt_from_thread为0，表示不需要保存来源线程的上下文。
  • 会设置rt_thread_switch_interrupt_flag为1，表示需要进行上下文切换。
  • 会设置PendSV异常的优先级为最低优先级，并触发PendSV异常。
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

.global rt_hw_context_switch_to

.type rt_hw_context_switch_to, %function

rt_hw_context_switch_to:

    /* 将要切换到的任务的地址存储到rt_interrupt_to_thread */

    LDR r1, =rt_interrupt_to_thread

    STR r0, [r1]


#if defined (__VFP_FP__) && !defined(__SOFTFP__)

    /* 清除CONTROL.FPCA */

    MRS     r2, CONTROL         /* 读取CONTROL寄存器的值 */

    BIC     r2, #0x04           /* 修改CONTROL寄存器的值 */

    MSR     CONTROL, r2         /* 将修改后的值写回CONTROL寄存器 */

#endif


    /* 将rt_interrupt_from_thread设置为0 */

    LDR r1, =rt_interrupt_from_thread

    MOV r0, #0x0

    STR r0, [r1]


    /* 将rt_thread_switch_interrupt_flag设置为1 */

    LDR     r1, =rt_thread_switch_interrupt_flag

    MOV     r0, #1

    STR     r0, [r1]


    /* 设置PendSV和SysTick异常的优先级 */

    LDR r0, =NVIC_SYSPRI2

    LDR r1, =NVIC_PENDSV_PRI

    LDR.W   r2, [r0,#0x00]       /* 读取NVIC_SYSPRI2寄存器的值 */

    ORR     r1,r1,r2             /* 修改NVIC_SYSPRI2寄存器的值 */

    STR     r1, [r0]             /* 将修改后的值写回NVIC_SYSPRI2寄存器 */


    /* 触发PendSV异常（导致上下文切换） */

    LDR r0, =NVIC_INT_CTRL    

    LDR r1, =NVIC_PENDSVSET

    STR r1, [r0]


    /* 恢复MSP */

    LDR     r0, =SCB_VTOR

    LDR     r0, [r0]

    LDR     r0, [r0]

    NOP

    MSR     msp, r0


    /* 在处理器级别启用中断 */

    CPSIE   F

    CPSIE   I


    /* 确保在后续操作之前已经发生了PendSV异常 */

    DSB

    ISB


    /* 这里永远不会到达！ */


临界区保护

  1. rt_enter_critical(void)：这个函数用于锁定线程调度器。它首先禁用中断，然后将调度器锁定的层数加一，并将新的层数保存在critical_level变量中。然后，它启用中断，并返回新的调度器锁定层数。这个函数通常用于进入临界区。
  2. rt_exit_critical(void)：这个函数用于解锁线程调度器。它首先禁用中断，然后将调度器锁定的层数减一。如果调度器锁定的层数减到0或以下，它将调度器锁定的层数重置为0，然后启用中断，并检查是否需要进行任务调度。如果调度器锁定的层数仍然大于0，它将直接启用中断。这个函数通常用于退出临界区。
  3. rt_critical_level(void)：这个函数返回当前的调度器锁定层数。如果返回值为0，表示调度器当前未被锁定。

这些函数通常用于实现临界区，以保护共享资源的访问。在临界区内，调度器被锁定，因此不会发生上下文切换。当离开临界区时，调度器被解锁，如果有必要，还会进行重新调度。这样可以确保在临界区内的代码不会被其他线程中断，从而保护了共享资源的一致性。注意，这些函数通常在内核或驱动程序代码中使用，应用程序代码通常不直接使用它们。在应用程序代码中，通常使用互斥量、信号量等同步原语来保护共享资源。这些同步原语的实现内部可能会使用到这些函数。

调度实现

rt_schedule 分析

  1. 中断屏蔽,rt_scheduler_lock_nest = 0,即没有进入临界区,则进行线程调度

2.rt_thread_ready_priority_group != 0,系统存在就绪线程,进行线程调度

  1. 获取最高优先级的线程和优先级
  2. 获取需要执行的线程
  3. 如果当前线程不是最高优先级线程,则进行线程切换
  4. 如果需要插入线程,把 from插入就绪链表末尾
  5. 从就绪链表中删除 to线程
  6. 执行栈异常检测
  7. 执行线程切换
  8. 不需要切换,则从就绪链表中删除 to线程

线程切换

上下文切换

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

.global rt_hw_context_switch_interrupt  // 声明一个全局函数 rt_hw_context_switch_interrupt

.type rt_hw_context_switch_interrupt, %function  // 定义 rt_hw_context_switch_interrupt 的类型为函数


.global rt_hw_context_switch  // 声明一个全局函数 rt_hw_context_switch

.type rt_hw_context_switch, %function  // 定义 rt_hw_context_switch 的类型为函数


rt_hw_context_switch_interrupt:  // rt_hw_context_switch_interrupt 函数的开始

rt_hw_context_switch:  // rt_hw_context_switch 函数的开始

    // 设置 rt_thread_switch_interrupt_flag 为 1

    LDR     r2, =rt_thread_switch_interrupt_flag  // 将 rt_thread_switch_interrupt_flag 的地址加载到寄存器 r2

    LDR     r3, [r2]  // 从 r2 指向的地址加载值到寄存器 r3

    CMP     r3, #1  // 比较 r3 和 1

    BEQ     _reswitch  // 如果 r3 等于 1，跳转到 _reswitch

    MOV     r3, #1  // 将 1 移动到寄存器 r3

    STR     r3, [r2]  // 将 r3 的值存储到 r2 指向的地址


    // 设置 rt_interrupt_from_thread

    LDR     r2, =rt_interrupt_from_thread  // 将 rt_interrupt_from_thread 的地址加载到寄存器 r2

    STR     r0, [r2]  // 将 r0 的值存储到 r2 指向的地址


_reswitch:  // _reswitch 标签的开始

    // 设置 rt_interrupt_to_thread

    LDR     r2, =rt_interrupt_to_thread  // 将 rt_interrupt_to_thread 的地址加载到寄存器 r2

    STR     r1, [r2]  // 将 r1 的值存储到 r2 指向的地址


    // 触发 PendSV 异常（导致上下文切换）

    LDR r0, =NVIC_INT_CTRL  // 将 NVIC_INT_CTRL 的地址加载到寄存器 r0

    LDR r1, =NVIC_PENDSVSET  // 将 NVIC_PENDSVSET 的地址加载到寄存器 r1

    STR r1, [r0]  // 将 r1 的值存储到 r0 指向的地址

    BX  LR  // 返回函数

PENSV异常处理

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154

.global PendSV_Handler

.type PendSV_Handler, %function

PendSV_Handler:

    /* 禁用中断以保护上下文切换 */

    MRS r2, PRIMASK

    CPSID   I


    /* 获取rt_thread_switch_interrupt_flag */

    LDR r0, =rt_thread_switch_interrupt_flag

    LDR r1, [r0]

    CBZ r1, pendsv_exit         /* 如果pendsv已经处理过，则退出 */


    /* 清除rt_thread_switch_interrupt_flag，将其设置为0 */

    MOV r1, #0x00

    STR r1, [r0]


    /* 获取rt_interrupt_from_thread的值 */

    LDR r0, =rt_interrupt_from_thread

    LDR r1, [r0]

    CBZ r1, switch_to_thread    /* 如果是第一次进行任务切换，则跳过寄存器保存 */


    /* 保存上下文 */

    MRS r1, psp                 /* 获取当前任务的堆栈指针 */


#if defined (__VFP_FP__) && !defined(__SOFTFP__)

    TST     lr, #0x10           /* 如果!EXC_RETURN[4] */

    IT      EQ

    VSTMDBEQ r1!, {d8 - d15}    /* 保存FPU寄存器s16~s31 */

#endif


    STMFD   r1!, {r4 - r11}     /* 保存r4 - r11寄存器 */


#if defined (__VFP_FP__) && !defined(__SOFTFP__)

    MOV     r4, #0x00           /* 设置flag为0 */


    TST     lr, #0x10           /* 如果!EXC_RETURN[4] */

    IT      EQ

    MOVEQ   r4, #0x01           /* 设置flag为1 */


    STMFD   r1!, {r4}           /* 保存flag */

#endif


    LDR r0, [r0]

    STR r1, [r0]                /* 更新当前任务的堆栈指针 */


switch_to_thread:

    /* 加载新任务的上下文 */

    LDR r1, =rt_interrupt_to_thread

    LDR r1, [r1]

    LDR r1, [r1]                /* 加载新任务的堆栈指针 */


#if defined (__VFP_FP__) && !defined(__SOFTFP__)

    LDMFD   r1!, {r3}           /* 弹出flag */

#endif


    LDMFD   r1!, {r4 - r11}     /* 弹出r4 - r11寄存器 */


#if defined (__VFP_FP__) && !defined(__SOFTFP__)

    CMP     r3,  #0             /* 如果flag_r3 != 0 */

    IT      NE

    VLDMIANE  r1!, {d8 - d15}   /* 弹出FPU寄存器s16~s31 */

#endif


    MSR psp, r1                 /* 更新堆栈指针 */


#if defined (__VFP_FP__) && !defined(__SOFTFP__)

    ORR     lr, lr, #0x10       /* lr |=  (1 << 4)，清除FPCA。 */

    CMP     r3,  #0             /* 如果flag_r3 != 0 */

    IT      NE

    BICNE   lr, lr, #0x10       /* lr &= ~(1 << 4)，设置FPCA。 */

#endif


#if defined (RT_USING_MEM_PROTECTION)

    PUSH    {r0-r3, r12, lr}

    LDR     r1, =rt_current_thread

    LDR     r0, [r1]

    BL      rt_hw_mpu_table_switch

    POP     {r0-r3, r12, lr}

#endif


pendsv_exit:

    /* 恢复中断 */

    MSR PRIMASK, r2


    ORR lr, lr, #0x04

    BX  lr