在计算机科学中，调度的艺术几乎就是计算本身的全部艺术

--Edsger W. Dijkstra

闲来无事，我在STM32上实现了一个超级简陋RTOS，只有调度的功能，以至于我不敢让他称之为RTOS，所以我的题目称之为一个调度程序，实现这个的过程学习到了很多知识，不记下来总感觉对不起自己，因此才有了这样一篇无头无尾的文章

参考资料

一本书《ARM Cortex-M3与Cortex M4权威指南》 (Joseph Yiu)

一个视频《现代嵌入式系统编程》

以及丰富的网络资源

前置知识

寄存器描述

我使用的是STM32F407ZGT6开发板，其内核为Cortex-M4，下面列出了其寄存器的详细描述，为什么要知道这个呢，圣人有云，计算机的本质是一个状态机，其每一个状态就是寄存器的值，我们调度程序的时候必须保存程序运行的状态，不然如何从上一个状态继续运行呢？这个状态的具体含义很大程度上就是寄存器的值。

在这里，值得注意的是：

• R13（MSP/PSP）是栈指针寄存器，实际上有两个物理寄存器主栈指针(MSP)为默认的栈指针，而线程栈指针(PSP)只能用于线程模式，对于一般的程序而言，只能可见一个，栈指针的选择由特殊状态寄存CONTROL 控制，对于没有OS的简单应用程序，多半是用的MSP，值得注意的是栈指针必须是8字节对齐

• R14（LR）是链接寄存器，用于函数或者子程序保存返回地址使用，子程序结束时会将LR的数值加载到PC返回调用程序，在嵌套调用时LR会压入栈，在异常处理期间，LR会变成EXC_RETURN

• R15（PC）是程序计数器，可读可写，读操作会返回当前指令地址+4，写PC则会发生跳转

两个状态和两种操作模式

• 调试状态：处理器被暂停后会进调试模式，并停止指令执行

• Thumb状态：执行代码（Thumb指令）时的状态，Cortex-M4没有ARM状态，因为他不能运行ARM指令集

• 处理模式：执行中断服务程序（ISR）时所处的模式，该模式下，总是拥有特权等级

• 线程模式：线程模式可能处于特权模式和非特权模式，取决于CONTROL的控制

软件可以将处理器由特权模式切换为非特权模式，但是却没有办法反向切换，如果要换，则必须进入异常机制，因为异常机制处于特权模式，可以设置CONTROL寄存器。因此对于嵌入式OS，可以将客户软件设置为非特权模式，内核运行在特权模式，这样可以通过MPU限制客户软件的内存访问权限，防止影响其他外设和OS内核

中断处理流程

中断的处理流程的不做过多的阐释，主要是细节我也不甚了解，我们需要关心的是进入中断函数以后，寄存器入栈的顺序，我们在终端中切换线程以后需要保护现场。很容易可以查到，Cortex-M4的硬件入栈顺序如下：

中断前栈顶 (SP_old)
                |     ...     | 高地址
                +-------------+
                |    R0       | <-- SP_new (自动保存后)
                |    R1       |
                |    R2       |
                |    R3       |
                |    R12      |
                |    LR       |  (EXC_RETURN)
                |    PC       |  (返回地址)
                |    xPSR     | 低地址
                +-------------+

在keil中，进debug模式在中断函数中打一个断点；然后打memory功能模块,找SP寄存器的值，输memory 模块中查看对应的值

注意一下左边的值LR的值，如前文说的，在中断处理函数中LR的值不是返回地址了，而是保存的返回模式，在这里，具体的值为：0xFFFFFFF9，返回线程模式，且使用主栈指针。当然左边的internal可以看到更多的信息...

在这里甚至可以直接修改右边堆栈里保存的PC指针，让程序跳转到其他位置，事实上，这也是这个调度程序的基本原理。

两个异常

我们的调度程序，或者你可以称之为一个ToyRTOS，也是一个程序，在别的指令执行的过程中，如何切换CPU的执行权限是一个很重要的问题，你总不能期望别人把调度权给你吧。在这里，中断/异常提供了一个很好的机制，它允许在任何事件获取到CPU的执行权限，并且中断中一定处于特权模式，也正是因此，我们可以定时的触发中断，在中断中执行我们的切换线程的代码，当然了，任何一个现代CPU恐怕都提供了定时器中断，我们可以借助它获得CPU的执行权限，在定时器中断中直接执行我们的调度代码固然可行，但是，我们有更好的，更优雅的解决方案，也就是下面介绍的两个重要中断。

SVC异常

SVC异常被称之为请求管理调用，在许多系统中，该异常用于统一处理内核请求，对于高系统稳定性的要求，应用程序在非特权等级运行，要操作某些硬件资源需要运行在特权等级之下，只能通过异常机制实现，此处的异常就是SVC，例如Linuxopen()函数，当然了，在本文实现的程序中，没有做到这个，我的程序运行在特权模式之下。仅作了解，具体了解可以参考《权威指南》第十章 OS支持特性

PendSV异常

PendSV被称为可挂起的系统调用，中断编号为14，具有可编程的优先级，可以软件触发，且会在高优先级中断/异常执行完以后再执行，再PendSV中执行线程切换可以保证其他中断不被打断，换句话讲，这个异常就是为OS设计的。

该异常是软件触发的，可以在系统控制块的中断控制和状态寄存器（ICSR）中被触发，28位为PENDSVSET，设置为1表示挂起系统调用，27位为PENDSVCLR，清除挂起状态，在执行异常处理程序或者清除挂起状态以后，PENDSVSET会自动清零

在CMSIScore_cm4.h提供了直接访问该寄存器的映射

#include<core_cm4.h>
SCB->ICSR |= SCB_ICSR_PENDSVSET_Msk;

实现

线程控制块

线程控制块是一个线程的抽象数据结构，因为这个实在是非常简单，所以我们的数据结构内容也很简单

typedef struct {
	void *sp;
	uint32_t timeout;
	uint8_t prio;
}OSThread;

• 第一个成员是一个指针，指向该线程的栈区，一个栈用于现场的保存以及局部变量之类的保存

• 第二个成员是一个延时事件的记录，用于后面的非阻塞延时

• 第三个是程序的优先级，这个里面实现的是抢占优先级，并且为了简单，优先级不可重复

线程切换

线程切换的原理就是在中断异常中，将PC指针修改为另一个线程（在这里实际上只有一个处理函数）的启示位置，不过实际上还有一些现场需要保存。

线程的存储

这个代码线程存储的策略非常简陋。使用长度位33的数组保存，也就是说最长允许32个线程，然后用两个32位的整数保存处于准备状态的线程和处于阻塞状态的线程，第多少位为1，表示对应下标的线程的状态，例如，Thread_Ready_Set的整数 0b00000000_00000000_00000000_00000001 代表数组第0下标的线程处于准备状态...这样有个好处是我们很容易拿到前导0的个数，数学上可以用log₂(x)获取前导数，在ARM里面提供了对应的指令，在CMSIS中，可以通__clz(x) 函数获取前导数，数组的长度比32多1是因为我后面会添加一个默认的idle线程。

OSThread *volatile OS_curr;
OSThread *volatile OS_next;

uint32_t Thread_Ready_Set = 0U;
uint32_t Thread_Delay_Set = 0U;

OSThread *ThreadList[MAX_THREAD_SUM+1];//MAX_THREAD_SUM == 32

线程的初始化

一个线程包含自己的上下文，上下文包括了局部变量和寄存器的值，因为在切换回来的时候需要把这些值继续处理，然后将线程继续进行，我们如何保存呢，因为线程会被切换，所以每个线程我们需要构建自己的栈，用来保存自己的上下文，在被切换的时候我们将没有被自动入栈（还记得中断会自动入栈部分寄存器吗？）的寄存器手动入栈，在线程被切换回来的时候将栈指针也切换回来，就算恢复了上下文，在这里，栈仅仅是一段内存空间，（实际上也是，是对它的操作规定了他叫栈），因为只需要处理好栈指针，他自己会处理栈的操作。

同时我们应该将我们自己设置的栈中的数据模拟成进入中断时候的内存分布，这样，这个线程就可以直接在中断中被切换过去。

在这里，代码如下

void OS_Thread_Start(OSThread *me,uint8_t priority, OSTaskFunc taskFunc,void *stack, uint32_t stackSize){
		
	uint32_t *sp = (uint32_t *)((((uint32_t)stack + stackSize) / 8)*8);//8字节对齐
	uint32_t *limit;
	*(--sp) = (1U<<24);
	*(--sp) = (uint32_t)taskFunc;
	*(--sp) = 0x0000000EU; //LR
	*(--sp) = 0x0000000CU; //R12
	*(--sp) = 0x00000003U; //R3
	*(--sp) = 0x00000002U; //R2
	*(--sp) = 0x00000001U; //R1
	*(--sp) = 0x00000000U; //R0
	
	*(--sp) = 0x0000000BU; //R11
	*(--sp) = 0x0000000AU; //R10
	*(--sp) = 0x00000009U; //R9
	*(--sp) = 0x00000008U; //R8
	*(--sp) = 0x00000007U; //R7
	*(--sp) = 0x00000006U; //R6
	*(--sp) = 0x00000005U; //R5
	*(--sp) = 0x00000004U; //R4
	me->sp = sp;
	me->prio = priority;
	limit = (uint32_t*)(((((uint32_t)stack -1U)/8)+1U)*8);
	for(sp = sp-1;sp>=limit;--sp){
		*sp = 0xDEADBEEFU;
	}
	ThreadList[priority] = me;
	if(priority > 0){
		Thread_Ready_Set |= (1<<(priority - 1));
	}
}

该函数的参数是线程控制块的指针，线程的优先级，处理函数，堆栈指针，堆栈大小

堆栈由外部传入的一个连续内存的指针定义，可能外部是一个全局变量数组，注意数组的地址增长是随着下标增加而增加，但是栈的增长方向是往低地址增长，因此我们要将初始的栈指针指向数组的最后一个元素 --sp 地址是增长，但是，ARM 要sp指针是8字节对齐，算法也很简单，简单的利用地板除的特性即可解决。

根据前文的中断入栈顺序，堆栈中的值应该 xPSR -> R0 然后手动入栈的顺序是R11 -> R4

因此初始化的值应该按照如此，其中xPSR 寄存器是程序状态寄存器，具体定义应该看前面，这里主要是设置为第24位为1，这里是固定的，ARM要求这一位必须为1，其他位没有设置。

PC寄存器应该设置为这个线程处理函数的函数地址，这样才能正确的返回处理函数

其他的寄存器我是随便填的，因为其他的寄存器在运行一次以后会被替换成正确的值，堆栈的其他内存空间我给了一个初始值。

然后应该将线程控制块做一些初始化

PendSV异常切换线程

利用Arm核的SystemTick中断触发PendSV异常，在PendSV异常中进行线程切换，首先我们定义两全局变量OSThread的变量

OSThread *volatile OS_curr;
OSThread *volatile OS_next;

这两个变量用于表示下一个线程和当前的线程

在PendSV中我们大致要做几件事，第一我们要保存线程的上下文，保存的位置是线程自身的栈，也就是将中断异常处理函数不会自动入栈的寄存器（r4-r11）压入栈，第二是切换线程，在中断处理函数中，切换线程实际上只是切换上下文，恢复现场，恢复成一个仿佛刚next 线程进来的中断一样，具体来说，将栈寄存器的值切换成下一个线程的栈地址，将手动保存的寄存器值填充到寄存器（r4-r11）中，这样中断返回的时候会自动从栈的位置中读取PC指针返回，因为栈已经被替换了，里面保存的是下一个线程处理函数的函数地址，因此返回的也是下一个线程，这就完成了线程切换。并且上下文也是正常的。Talk is cheap. Show me the code.

这里因为要操作寄存器，所以要用汇编，不过我们大致可以用C语言描述一下

	__disable_irq();
	if(OS_curr!=(OSThread*)0){
		//将r4-r11入栈，C语言无法实现
		OS_curr->sp = sp;
	}
	sp = OS_next->sp;
	//r4-r11出栈,C语言无法实现
	OS_curr = OS_next;
	
	__enable_irq();

写成汇编对应的是

IMPORT OS_curr
	IMPORT OS_next
	//禁用中断
	CPSID I
	LDR r1,=OS_curr
	LDR r1,[r1,#0x00]
	CBZ r1,PendSV_restore
	//现场入栈
	PUSH {r4-r11}
	LDR r1,=OS_curr
	LDR r1,[r1,#0x00]

	STR sp,[r1,#0x00]
		
PendSV_restore
	LDR r1,=OS_next
	LDR r1,[r1,#0x00]
	LDR sp,[r1,#0x00]

	LDR r1,=OS_next
	LDR r1,[r1,#0x00]
	LDR r2,=OS_curr
	STR r1,[r2,#0x00]

	POP {r4-r11}

	CPSIE I
	BX lr

注意：我在这里使用了没有使用PSP指针寄存器，还记得这个寄存器吗，《权威手册》里面使用了这个寄存器，我没有用，如果要使用，需要在系统初始化的时候，设置CONTROL寄存器，并且初始化PSP的值。

优先级策略

【未完待续...】