嵌入式操作系统内核原理和开发

嵌入式操作系统内核原理和开发（开篇）

操作系统是很多人每天必须打交道的东西，因为在你打开电脑的一刹那，随着bios自检结束，你的windows系统已经开始运行了。如果问大家操作系统是什么？可能有的人会说操作系统就是windows，就是那些可以放大、缩小、移动的窗口。对曾经是计算机专业的朋友来说，这个答案还要稍微复杂一些，操作系统可能还有linux、unix、ios、sun solaris、aix等。如果再细化一点，对嵌入式工具比较解的朋友还会有新的补充，因为在他们看来，vxworks、eCos、ucos也都是操作系统，虽然它们好多系统连界面都没有。

    既然操作系统称之为一个系统，那么它必然是由好多的部件组成的。有过linux嵌入式开发经验的朋友都知道，要想使一个linux在arm芯片上真正跑起来，它必须有三个部分组成，即boot + 内核 + 文件系统。而真正内核的东西其实很少，也就是cpu初始化、线程调度、内存分配、文件系统、网络协议栈、驱动这些部分组成。那么是不是所有的芯片都需要跑操作系统呢？我们可以举个例子。

    现在有一个简单的温度测量电路，它由三部分组成：1、单片机；2、温度传感器模块；3、无线发射模块。我们设计这么一个温度测量电路其实就是一个目的，那就是为了实时获取当前的温度信息。那么，这么一个简单的电路应该怎么设计程序呢？其实很简单。

[cpp] view plaincopy

1. void sleep(int value)  
2. {  
3.     int outer;  
4.     int inner;  
5.       
6.     for(; outer < value; outer++)  
7.     {  
8.         for(inner = 0; inner < 1000; inner++)  
9.             ;  
10.     }  
11. }  
12.   
13.   
14. void main()  
15. {  
16.     while(1)  
17.     {  
18.         /* read temperature from port*/  
19.         sleep(1000);  
20.         /* send temperature to wireless module */  
21.         sleep(1000);  
22.     }  
23. }  

    如果我们需要cpu干的事情很少，甚至极端一点说只有一件事情，那么根本没有设计操作系统的必要。我们设计出操作系统，主要是想在单位时间内完成几件事情。打个比方来说，你完全可以在工作的时候一遍写文档、一遍收发电子邮件，偶尔还能开个小差休息一会。 所以操作系统就是为了共享资源而存在的。

    认识操作系统的用途不难，关键是如何把操作系统用代码写出来。也许有人会跟你说，免费的代码一大堆，Linux就不错，你下载下来直接读就好了。但是我告诉你，最新的Linux内核版本已经轻松的越过了3.0，整个代码的长度远在千万行之上，你可能从哪看起都不知道。可能此时又有人不同意了，看不懂高版本的linux，可以看看linux低版本的代码，0.11版本的代码就不错，因为赵炯就是怎么推荐的。我要说的是，0.11的代码固然好，但是怎么编译版本、怎么修改代码、怎么构造文件系统、怎么跑起来是我们绕不过的一道难题。对于很多朋友来说，阅读linux代码尚且困难，更不要说后面还需要完成的一大摊子烂事了。

    说了这么多，我们需要的的内核代码是什么样的？其实在我看来，很简单。它只要满足下面两个条件就可以了，
（1）像用户软件一样可以运行；
（2）像用户软件一样可以单步调试。    

    要解决这些问题，对linux系统来说上不难解决。要解决os的运行和调试问题，关键就在于如何仿真中断和实现os的任务切换。至于任务的开启、运行和挂起，内存分配，互斥量，信号量，文件系统，tcp/ip协议栈，GUI操作，这些其实都是可以在linux上进行仿真和操作的，朋友们可以尽请放心。这部分的内容，我们会在以后的博客中陆续展开。

    为了能够更好地阅读后面发表的博文，我建议你巩固一下下面这些知识，这样会对你的理解有很大的裨益。
（1）cpu 结构，了解中断流程就行；
（2）linux 汇编语言；
（3）函数堆栈格式和内容；
（4）互斥量、信号量的使用方法；
（5）调度的基本策略；
（6）内存分配的基本方法；
（7）tcp/ip socket编程；
（8）gui编程方法，可以参考windows的方法；
（9）系统中的内存布局、编译原理等等。

嵌入式操作系统内核原理和开发（cpu的那些事）

cpu是数字处理系统中的一个重要环节。在我看来，单片机、微处理器、dsp都可以称作是cpu，只是它们的侧重点有所不同罢了。具体来说，传统意义上的单片机更偏重于嵌入式的计算，比如说我们经常使用的51、avr、arm芯片中不仅仅含有了运算和控制功能，它还涵盖了定时器、串口、并口、usb、i2c总线等外部资源。dsp呢，cpu一般只是作为dsp的一个核存在，它通常还会包含另外一个核，专门用于数字信号的处理工作。而微处理器，也就是我们经常说的pc上的处理器，它的工作比较单一，专注于计算和控制功能的处理，因此一般来说在这方面的性能上面，单片机和dsp都是不能和它相比的，有了南桥芯片和北桥芯片的帮助，pc的微处理器就可以专注于自己的本职工作了，效率上面也会有一个很大的提高。

    对于朋友们来说，生活中遇到的最多的cpu其实是x86的cpu。当然，如果有哪位朋友喜欢apple之类的玩具，也会知道一些arm的相关事情。剩下的就是一些专用领域的cpu了，比如说在通信行业用到的比较多的powerpc芯片，在高性能服务器用的到的sun sparc芯片，在科学计算领域使用到的mips芯片。所以，无论遇到什么芯片，对于应用层开发的朋友都是一样的，只是在一些小地方需要还有一些注意的地方。比如说，

（1）数据的对齐方式

（2）数据的字节序问题

（3）函数参数的压栈问题

（4）cpu的乱序执行问题

（5）cpu中cache和内存一致性的问题

    当然，如果我们所要思考只是简单的应用层设计，考虑到这些内容本身已经实属不易了。然而，我们考虑的是如何设计嵌入式操作系统的问题，所以接下来还要看看一般cpu下面都包含了那些内容。这样，只要熟练掌握了一款cpu的设计和实现，对其他cpu的知识也会触类旁通了。

    任何一款cpu，不管是完成的功能是什么样的，通常都会有这样一些基本设计：

（1）寄存器

    堆栈寄存器    

    pc寄存器

    状态寄存器

    运算寄存器

    寄存器是cpu内部的基本资源。不管cpu的代码执行到什么时候，这些资源都是共享的，所以在cpu发生中断、函数调用、线程切换的时候，都需要对这些寄存器进行保护，常用的基本措施就是把把它们保存到临时堆栈当中去。堆栈寄存器记录了当前堆栈使用到了什么地方，pc寄存器则记录当前代码跑到了什么地方，下一条指令在什么地方等。状态寄存器则保存了当前cpu的执行情况，包括计算有没有溢出、中断是关还是开、有没有o除数异常等等。至于运算寄存器就因cpu而异了，有的cpu寄存器比较少，比如说x86的寄存器；有的cpu寄存器就比较多，比如说powerpc。运算寄存器的用途很多，比如说数据访问、计算、移位、返回计算结果等等。

（2）指令集

    寻址指令

    数学运算指令

    逻辑运算指令

    软中断指令

    跳转指令

    远程调用指令

    io访问指令

    栈操作指令

    指令集在某种程度上直接决定了某一种cpu的类型。就像intel和amd生产的cpu虽然有差别，但是它们的cpu使用的都是x86的指令集，而marwell、samsung和高通生产的cpu当然也不同，但是它们的指令集都是arm指令集。所以，如果软件在marwell上跑，一般来说也可以在Samsung上跑起来。指令集很复杂，内容很多。但是通常来说，上面这些内容都是cpu所必须要完成的几种指令。当然重中之重的还是中断和栈处理指令。

（3）中断、异常处理机制

    不管是什么cpu，中断部分的内容都是少不了的。试想一想，如果一颗cpu只知道不停地运行，那么它的执行效率实际上是很低的。拥有了中断的cpu不仅使得cpu可以和更多的外设io打交道，还能极大地提高自身运行的效率。不同的cpu处理中断的方法其实都差不多，在整个cpu的地址空间里面，通常在低地址区域会有一张中断向量表，表中每一项记录了每一个中断对应的处理函数。所以，只要中断发生时，cpu就会首先将下一条pc地址压入堆栈，然后跳转到中断向量表中对应的中断地址处执行的相应的处理函数。这个过程是cpu自动完成的，不需要我们关心。这样对我们来说，它和cpu中的函数调用其实没有什么区别。等待中断处理结束后，我们使用ret指令返回到之前压入的那个ip地址处，继续下面的代码。整个过程就好像中断根本没有发生过一样。

    所以，对于cpu的了解其实主要就是对寄存器、指令集和中断的了解。有了对中断和堆栈的深入理解，其实也就没有什么困难的了。在这里我们大家可以考虑一个问题，如何在Windows或者linux下仿真中断完成我们的操作系统开发呢？大家可以自己先思考一下，我们会在随后的博客中继续介绍。整篇文章，我们没有介绍编码的相关内容，其实只要把这里的基本概念弄清楚了，剩下来其实就是一些流程性的工作了。在软件开发中，设计其实是最难的，剩下的才是开发和调试。

嵌入式操作系统内核原理和开发（中断）

  在我个人看来，中断是cpu最重要的特色。从某种意义上来说，没有中断就没有嵌入式操作系统。一旦你明白了中断的真正含义，你对操作系统的了解就算真正入门了。什么是中断呢？我们可以看看单片机下面是怎么做的。 [cpp] view plaincopy

1. #include <REG51.h>  
2.   
3. sbit LED = P1 ^ 6;  
4. unsigned int led_enable = 0;  
5.   
6. void Delay(unsigned int a)  
7. {  
8.     unsigned int i;  
9.   
10.     while(a)  
11.     {  
12.         a --;  
13.         for(i = 0; i < 1200; i++);  
14.     }  
15. }  
16.   
17. void led_switch(void) interrupt 0 using 1  
18. {  
19.     if(0 == led_enable)  
20.     {  
21.         led_enable = 1;  
22.     }  
23.     else  
24.     {  
25.         led_enable = 0;  
26.     }  
27.   
28.     EX0 = 1;  
29. }  
30.   
31. void main(void)  
32. {  
33.     EA = 1;  
34.     EX0 = 1;  
35.   
36.     while(1){  
37.         if(led_enable)  
38.         {  
39.             LED = 0;  
40.             Delay(100);  
41.             LED = 1;  
42.             Delay(100);  
43.         }  
44.     }  
45. }  

    上面的代码是一段真实的51单片机代码。它完成的功能很简单，就是对led灯进行点亮处理。怎么解释呢?在单片机上电后，我们发现一开始led二极管没有发生闪烁。在我们单击按键之后，led开始出现间隙性闪烁的现象，之后再一次单击按键，又可以发现led的闪烁现象消失了。为什么会出现这种现象？主要是因为我们单击按键的时候，在单片机的引脚处产生了中断。查看到中断的单片机此时就会跳转到中断向量表里面查找中断处理函数。这里的按键中断处理函数就是led_switch。处理完led_switch之后，单片机又会回到原来的main函数继续执行，所以整个中断的过程就像没有发生过一样。因为在led_switch中我们对led_enable进行了处理，所以就出现了我们在前面说过的各种现象。

                                                                   
 
    说到这，也许有的朋友会说，cpu的这种中断属性怎么才能在pc上面仿真出来呢？其实很简单。linux系统本身就有一个优秀的特性，那就是信号。只要我们设定相应的信号和处理函数，那么linux系统就会在系统调度返回之前调用相应的信号函数来处理。整个信号处理的过程和中断是一模一样的。因为在处理中断的时候，我们需要对cpu的现场进行保存和恢复处理，而信号的处理也是一样。在信号处理前，系统肯定是处于内核态，那么linux系统肯定已经为我们做好了现场的保护工作，处理完信号之后，系统本身又会恢复到原来的用户态，继续执行下面的代码。所以linux自身也会默认对原来的场景进行恢复处理，就好象中断返回一样。

[cpp] view plaincopy

1. #include <stdio.h>  
2. #include <time.h>  
3. #include <sys/time.h>  
4. #include <stdlib.h>  
5. #include <signal.h>  
6.   
7. static int count = 0;  
8. static struct itimerval oldtv;  
9.   
10. void set_timer()  
11. {  
12.     struct itimerval itv;  
13.     itv.it_interval.tv_sec = 1;  
14.     itv.it_interval.tv_usec = 0;  
15.     itv.it_value.tv_sec = 1;  
16.     itv.it_value.tv_usec = 0;  
17.     setitimer(ITIMER_REAL, &itv, &oldtv);  
18. }  
19.   
20. void signal_handler(int m)  
21. {  
22.     count ++;  
23.     printf("%d\n", count);  
24. }  
25.   
26. int main()  
27. {  
28.     signal(SIGALRM, signal_handler);  
29.     set_timer();  
30.     while(count < 10000);  
31.     exit(0);  
32.     return 1;  
33. }  

    大家可以把这样一段代码在Linux编译一下，然后使用gdb调试即可。查看整个signal_handler在被断点断住的时候，本身线程是不是只有一个？函数堆栈是不是在一个线程里面。如果不出意外，整个信号的处理过程应该是这样的， [cpp] view plaincopy

1. (gdb) bt  
2. #0 signal_handler(m=14) at code.c: 23  
3. #1 <signal handler caller>  
4. #2 main() at code.c:32  

    到了这里，相应大家应该还有一个疑问，既然可以利用linux的signal对cpu的中断进行仿真，那么能不能利用windows的signal对中断进行仿真呢。因为Windows下面的没有SIGALRM这个信号，所以我们可以重新编写一段代码，然后利用visual studio 6.0进行编译，看看对应的情况。 [cpp] view plaincopy

1. #include <stdio.h>  
2. #include <stdlib.h>  
3. #include <signal.h>  
4. #include <tchar.h>  
5. #include <Windows.h>  
6.   
7. void SignalHandler(int signal)  
8. {  
9.     printf("Application over..\n");  
10. }  
11.   
12. int main()  
13. {  
14.     typedef void (*SignalHandlerPointer)(int);  
15.   
16.     SignalHandlerPointer previousHandler;  
17.     previousHandler = signal(SIGINT, SignalHandler);  
18.     while(1)  
19.     {  
20.     Sleep(0);  
21.     }  
22.       
23.     exit(1);  
24. }  

   下面，我们首先编译这一段代码。接着在程序run之后，我们可以在SignalHandler之处设置一个断点。一切就绪完毕，再按下ctrl+c之后，系统就会在SignalHandler之处断住。此时单击【Debug】-> 【Threads】，就可以看到这个情况。

                              

   相信看到这里，大家应该看明白了。其实在Windows下面，信号是专门有一个线程来完成的，和原来的main函数不是同一个线程。既然线程都不是一样的，而中断本身是必须在一个thread中完成的。我们怎么能利用windows来仿真cpu的中断处理流程呢。

嵌入式操作系统内核原理和开发（地址空间）

不管是什么样的嵌入式cpu，它必然有自己的访问地址空间。至于这个具体的访问空间是什么，那cpu就不知道了。它可以是ram，当然也可以是flash、uart、ide、i2c等。当然cpu不仅需要地址总线，它还需要数据总线和控制总线。这三个总线的目的都非常明确，控制总线主要是为了实现cpu对外设接口的控制，地址总线是为了实现地址的输出，数据总线则是为了实现数据内容的获取或者设置。所以，对于一般的嵌入式cpu来说，它的基本架构应该是这样的，

                                   

    在x86的cpu上，很多对外设的操作是需要通过北桥或者通过南桥芯片完成的。而在嵌入式硬件中，我们就把经常使用到的接口芯片集成到了cpu里面。所以在嵌入式cpu功能上面，你除了看到cpu的字长、时钟、指令集、运算速率这些通常的数据之外，你还会看到很多的接口控制寄存器，比如说定时器寄存器，lcd寄存器，uart寄存器，i2c寄存器。这些都表明了此时的cpu完成的不仅仅是简单的计算功能，它还需要完成对外设接口的设置。通过对应的寄存器设置，我们就可以对外设的接口状态进行控制。

                                               

    说了这么多，我们接下来要看看嵌入式系统在地址空间里面是怎么设计的啊？其实一个完整的嵌入式软件系统并不复杂。一般来说，一个完整的系统需要有boot、kernel、文件系统三部分。其中boot主要放在norflash里面，而kernel和文件系统是存放在nandflash里面。在系统上电之后，cpu会有一个初始地址，这个地址要么是0x00000001，或者是0xFFFF0000。通常这个地址会指向Norflash，下面开始执行的代码当然就是boot代码。因为Norflash的访问速度要比Ram速度慢很多，所以boot代码很快会把自己拷贝到Ram中，然后跳到Ram中继续运行。boot的功能比较简单，主要就是为了获取芯片参数，设置芯片属性，设置堆栈空间，加载操作系统内核等。在boot完成自己的功能之后，它会把系统内核加载到Ram中，然后jump到系统的运行首地址处运行。系统内核主要完成整个系统的初始化工作，比如说内存分配，信号量初始化，net初始化，驱动结构初始化等工作。在内核即将完成初始化的时候，它会进行最后一步操作，mount一个文件系统，加载文件系统的脚本数据，开启相关的系统进程，最后一步就是开启shell进程，接受用户的命令输入。至此，一个系统算是真正跑起来了。

                                                                   

    前面，我们说过cpu需要数据总线、地址总线和控制总线才能与外设接口打交道。既然cpu是通过状态寄存器设置外设接口的状态的，那么cpu是如何通过地址总线与外界联系的呢？这里面就涉及到片选信号的问题。我们知道，一个32位的cpu有32条地址线和外界相连，那么也就是说如果没有其他的方法，它只能外设32个接口。那么有没有什么办法可以扩大外设接口呢？说到这里，你应该知道了，它就是解码器和片选信号了。比如说，现在有4个外设接口，我们可以怎么从地址总线中挑出两条线，00表示外设1，01表示外设2，10表示外设3，11表示外设4。这样有了解码器的帮助，我们就可以用两个地址线实现对4个外设接口的控制了。

    有了cpu状态寄存器，我们可以设置当前外设接口的执行状态。如果是读命令，首先设置外设接口的状态模式为读状态，然后发送地址，此时片选信号选中的芯片就会处于使能状态，一会cpu就可以从数据总线上获得数据，存储在寄存器或者是内存当中；如果是写命令，那么cpu首先设置外设接口为写模式，然后在地址总线上输出地址，在收到芯片ready信号后，cpu再将数据从寄存器上传输到数据总线上，在等到外设芯片的ack信号后，整个数据的传输过程才算完成。我们看到，一个汇编指令的操作竟然涉及到这么多信号的操作，可见cpu的处理过程还是很复杂的。有的时候，中间还会涉及到信号完整性或者是时序的问题，那么这时候逻辑分析仪就可以派上用场了。

嵌入式操作系统内核原理和开发（基础）

  在编写我们的操作系统之前，我们需要明确一些事情。比如说，这个系统的运行环境是什么？怎么编译？基本中断环境是什么？上下文怎么切换？准备实现那些内容？基本数据类型是什么？等等。

（1）你的嵌入式操作系统准备叫什么名称？运行环境是什么？可以在实际环境上面运行吗？

    我们准备把这个嵌入式操作系统称之为MiniOS。虽然这个操作系统实现的功能不多，但是麻雀虽小，五脏俱全。一般操作系统该有的功能，MiniOS都会有这个功能。起初，我们会在linux上运行MiniOS，之后我们会把MiniOS移植到51单片机上去。 

（2）操作系统怎么编译？

    MiniOS系统采用基本的C语言进行编写，没有汇编语言，但是移植到51上面需要一些汇编语言。编写完C语言文件后，我们需要一个简单的makefile文件，这样就可以实现自动化编译，进一步提高我们开发的效率。

（3）基本中断环境是什么？

    因为MiniOS起初是在linux实现运行的，所以它是依靠SIGALRM实现中断调度的。当然在OS中还会有I/O操作，这里我们用信号进行仿真。SIGINT就是一种方法，每当我们使用键盘输入ctrl+C的时候，就会调用相应的函数。这和外设的中断是一模一样的。

（4）上下文怎么切换？

    上下文的切换就是堆栈的切换。要弄清楚堆栈的切换，首先你要明白函数，函数里面的数据是怎么安排的，压栈是怎么回事，退栈是怎么回事。这些知识点，我们在后面都会一一介绍。

（5）MiniOS要实现哪些内容？

    MiniOS虽然比较小巧，但是操作系统该有的功能它都会有。因此，我们准备实现的下面这些内容，比如说中断开关、互斥量、定时器、线程调度、内存分配都会拥有。

（6）基本数据类型是什么？

    为了移植的方便，我们需要对基本数据进行重新定义一下基本数据类型。

[cpp] view plaincopy

1. #define UINT32 unsigned int  
2. #define INT32  signed int  
3. #define UINT16 unsigned short  
4. #define INT16  signed short  
5. #define UINT8  unsigned char  
6. #define INT8   signed char  
7.   
8. #define TRUE 1L  
9. #define FALSE 0L  
10. #define OK   0L  
11. #define ERROR ~0L  
12.   
13. #define BOOLEAN UINT32  
14. #define STATUS  UINT32  

（7）把MiniOS移植到51单片机需要做些什么？

    其实把MiniOS移植到51上面，其实不困难，只要做到这几个方面就可以了。a）基本数据类型重新定义；b）中断开关重新进行设置；c）任务切换的压栈、出栈处理。要是做到这里，我们就可以在51单片机上面把自己的OS跑起来了，那是多么开心的一件事情啊。

嵌入式操作系统内核原理和开发（系统中断仿真）

在嵌入式操作系统中，最难模仿的是系统中断的问题。在windows下面，这是没有办法的事情。但是在linux下面，却有一个非常便利的条件，那就是linux的信号处理。因为用户程序处理的时候，signal的处理和用户线程的处理堆栈是一致的，这和中断是完全吻合的。所以，如果你需要关闭中断，可以这么写， [cpp] view plaincopy

1. sigprocmask(SIG_BLOCK, &new_set, &old_set);  

    当然，如果需要再次打开中断了，还可以这么写， [cpp] view plaincopy

1. sigprocmask(SIG_UNBLOCK, &new_set, NULL);  

    所以，这里我们可以编写一个完整的程序说明问题。 [cpp] view plaincopy

1. #include <stdio.h>  
2. #include <time.h>  
3. #include <sys/time.h>  
4. #include <stdlib.h>  
5. #include <signal.h>  
6.   
7. static int count = 0;  
8. static struct itimerval oldtv;  
9.   
10. void set_timer()  
11. {  
12.     struct itimerval itv;  
13.     itv.it_interval.tv_sec = 1;  
14.     itv.it_interval.tv_usec = 0;  
15.     itv.it_value.tv_sec = 1;  
16.     itv.it_value.tv_usec = 0;  
17.     setitimer(ITIMER_REAL, &itv, &oldtv);  
18. }  
19.   
20. void signal_handler(int m)  
21. {  
22.     count ++;  
23.     printf("%d\n", count);  
24. }  
25.   
26. void signal_int()  
27. {  
28.     printf("hello!\n");  
29. }  
30.   
31. int main()  
32. {  
33.     sigset_t new_set;  
34.     sigset_t old_set;  
35.   
36.     signal(SIGALRM, signal_handler);  
37.     signal(SIGINT,  signal_int);  
38.     set_timer();  
39.   
40.     sigemptyset(&new_set);  
41.     sigaddset(&new_set, SIGALRM);  
42.     sigaddset(&new_set, SIGINT);  
43.     sigprocmask(SIG_BLOCK, &new_set, &old_set);  
44.     sleep(10);  
45.       
46.     sigprocmask(SIG_UNBLOCK, &new_set, NULL);  
47.     while(count < 10 ) sleep(1);  
48.     return 0;  
49. }  

    基本说明如下：

    （1）我们的系统暂时只负责SIGINT和SIGALRM，前者负责I/O的仿真，后则负责线程的调度；

    （2） sigprocmask函数用来实现中断的打开和关闭；

    （3）程序首先关闭中断，然后打开中断，打印数据完即结束，仅作为示范使用。

嵌入式操作系统内核原理和开发（线程切换）

在操作系统中，线程切换是很重要的一个环节。如果没有线程的切换，我们如何才能实现多线程的并发运行呢？既然要实现切换，那么一方面，我们需要对原来的寄存器进行保存，另外一方面我们还要压入新堆栈的寄存器，这样才能实现线程切换的效果。在x86下面，因为切换线程的ip地址是固定的，所以切换所需要的寄存器也是固定的，一般来说保存eax、ebx、ecx、edx、esi、edi、ebp和esp即可。比如说，像这样， [cpp] view plaincopy

1. void swap(UINT32* prev, UINT32* next)  
2. {  
3.     __asm("push %%eax\n\t"  
4.           "push %%ebx\n\t"  
5.           "push %%ecx\n\t"  
6.           "push %%edx\n\t"  
7.           "push %%esi\n\t"  
8.           "push %%edi\n\t"  
9.           "push %%ebp\n\t"  
10.           "push %%esp\n\t"  
11.   
12.           "lea 0x8(%%ebp), %%eax\n\t"  
13.           "mov (%%eax), %%eax\n\t"  
14.           "mov %%esp, (%%eax)\n\t"  
15.   
16.           "lea 0xc(%%ebp), %%eax\n\t"  
17.           "mov (%%eax), %%eax\n\t"  
18.           "mov (%%eax), %%esp\n\t"  
19.   
20.           "pop %%esp\n\t"  
21.           "pop %%ebp\n\t"  
22.           "pop %%edi\n\t"  
23.           "pop %%esi\n\t"  
24.           "pop %%edx\n\t"  
25.           "pop %%ecx\n\t"  
26.           "pop %%ebx\n\t"  
27.           "pop %%eax\n\t"  
28.           ::);  
29. }  

    上面说的都是对已经运行的线程进行切换。那么刚刚创建的线程怎么进行切换呢？一个不错的方法就是仿真出栈的处理流程。把初始状态的寄存器放在堆栈里面，模仿线程的出栈过程，设置好线程的初始寄存器数值即可。比如说，像这样， [cpp] view plaincopy

1. void signal_handler(int m)  
2. {  
3.     UINT32* data;  
4.     UINT32 unit;  
5.   
6.     if(count != 0)  
7.     {  
8.         printf("count = %d\n", count++);  
9.         return;  
10.     }  
11.   
12.     printf("count = %d\n", count++);  
13.     data = (UINT32*)malloc(STACK_LENGTH);  
14.     unit = STACK_LENGTH >> 2;  
15.   
16.     if(NULL == data)  
17.         return;  
18.   
19.     memset(data, 0, STACK_LENGTH);  
20.     data[unit -1] = (UINT32) hello;  
21.     data[unit -2] = 0;  
22.     data[unit -3] = 0;  
23.     data[unit -4] = 0;  
24.     data[unit -5] = 0;  
25.     data[unit -6] = 0;  
26.     data[unit -7] = 0;  
27.     data[unit -8] = 0;  
28.     data[unit -9] = 0;  
29.     data[unit -10] = (UINT32) &data[unit - 9];  
30.   
31.     new = (UINT32) &data[unit -10];  
32.     swap(&old, &new);  
33.     free(data);  
34. }  

    最后，我们给出一份完整的代码。在程序收到第一个signal的时候，我们发现代码不仅申请了内存，还初始化成了堆栈的格式，完美地解决了堆栈切换的问题。当然在hello处理结束后，代码又恢复成了原来的格式，而且内存正常释放，一切就像没有发生过一样。试想，如果每一次处理的都是一个function和stack，那基本上就可以模仿线程的运行过程了。
[cpp] view plaincopy

1. #include <stdio.h>  
2. #include <time.h>  
3. #include <sys/time.h>  
4. #include <stdlib.h>  
5. #include <signal.h>  
6.   
7. #define UINT32 unsigned int  
8. #define STACK_LENGTH 1024  
9.   
10. static struct itimerval oldtv;  
11. UINT32 old = 0;  
12. UINT32 new = 0;  
13. UINT32 count = 0;  
14.   
15. void set_timer()  
16. {  
17.     struct itimerval itv;  
18.     itv.it_interval.tv_sec = 1;  
19.     itv.it_interval.tv_usec = 0;  
20.     itv.it_value.tv_sec = 1;  
21.     itv.it_value.tv_usec = 0;  
22.     setitimer(ITIMER_REAL, &itv, &oldtv);  
23. }  
24.   
25. void swap(UINT32* prev, UINT32* next)  
26. {  
27.     __asm("push %%eax\n\t"  
28.           "push %%ebx\n\t"  
29.           "push %%ecx\n\t"  
30.           "push %%edx\n\t"  
31.           "push %%esi\n\t"  
32.           "push %%edi\n\t"  
33.           "push %%ebp\n\t"  
34.           "push %%esp\n\t"  
35.   
36.           "lea 0x8(%%ebp), %%eax\n\t"  
37.           "mov (%%eax), %%eax\n\t"  
38.           "mov %%esp, (%%eax)\n\t"  
39.   
40.           "lea 0xc(%%ebp), %%eax\n\t"  
41.           "mov (%%eax), %%eax\n\t"  
42.           "mov (%%eax), %%esp\n\t"  
43.   
44.           "pop %%esp\n\t"  
45.           "pop %%ebp\n\t"  
46.           "pop %%edi\n\t"  
47.           "pop %%esi\n\t"  
48.           "pop %%edx\n\t"  
49.           "pop %%ecx\n\t"  
50.           "pop %%ebx\n\t"  
51.           "pop %%eax\n\t"  
52.           ::);  
53. }  
54.   
55. void hello()  
56. {  
57.     printf("hello!\n");  
58.     swap(&new, &old);  
59. }  
60.   
61. void signal_handler(int m)  
62. {  
63.     UINT32* data;  
64.     UINT32 unit;  
65.   
66.     if(count != 0)  
67.     {  
68.         printf("count = %d\n", count++);  
69.         return;  
70.     }  
71.   
72.     printf("count = %d\n", count++);  
73.     data = (UINT32*)malloc(STACK_LENGTH);  
74.     unit = STACK_LENGTH >> 2;  
75.   
76.     if(NULL == data)  
77.         return;  
78.   
79.     memset(data, 0, STACK_LENGTH);  
80.     data[unit -1] = (UINT32) hello;  
81.     data[unit -2] = 0;  
82.     data[unit -3] = 0;  
83.     data[unit -4] = 0;  
84.     data[unit -5] = 0;  
85.     data[unit -6] = 0;  
86.     data[unit -7] = 0;  
87.     data[unit -8] = 0;  
88.     data[unit -9] = 0;  
89.     data[unit -10] = (UINT32) &data[unit - 9];  
90.   
91.     new = (UINT32) &data[unit -10];  
92.     swap(&old, &new);  
93.     free(data);  
94. }  
95.   
96. int main()  
97. {  
98.     set_timer();  
99.     signal(SIGALRM, signal_handler);  
100.     while(count < 10);  
101.     exit(0);  
102.     return 1;  
103. } 
     

嵌入式操作系统内核原理和开发（任务创建和堆栈溢出检查）

虽然写操作系统的博客要比写普通的技术点要麻烦一些，但是心中还是挺开心的。一方面，通过几行代码就可以说明一些问题，把理论实践化，这本身就很具有挑战性；另外一方面还锻炼自己的沟通能力，让更多的人明白你的想法，认可你的想法。

    其实，通过上面一篇博客，我们就已经清楚任务的创建是怎么一回事，但是我们还是愿意就这个问题讲得更细一点，说得更多一点。系统本身是多线程的，那说明所有线程的地址空间都是共享的。由于资源都是操作系统本身提供的，所以线程本身的要求就很低，函数名、堆栈、入口点、堆栈大小、优先级，大体上也就是这么多。至于这个堆栈是哪里的内存，其实已经不太重要了。为了简单起见，我们对原来的初始化函数 稍微修改了一下，

[cpp] view plaincopy

1. void task_init()  
2. {  
3.     UINT32 unit = STACK_LENGTH;  
4.   
5.     memset((void*)data, 0, STACK_LENGTH * sizeof(UINT32));  
6.     data[unit -1] = (UINT32) hello;  
7.     data[unit -2] = 0;  
8.     data[unit -3] = 0;  
9.     data[unit -4] = 0;  
10.     data[unit -5] = 0;  
11.     data[unit -6] = 0;  
12.     data[unit -7] = 0;  
13.     data[unit -8] = 0;  
14.     data[unit -9] = 0;  
15.     data[unit -10] = (UINT32) &data[unit - 9];  
16.     new = (UINT32) &data[unit -10];  
17. }  

    上面的操作比较简陋，只是对堆栈进行了设置。这是线程初始化的时候必须要做的一步。当然，这里的hello就是我们的函数入口点。因为这里用SIGALRM代替的时钟中断是没有办法做到抢占的，所以我们可以人为多设置一些调度点，比如象这样， [cpp] view plaincopy

1. void hello()  
2. {  
3.     printf("count = %d in sub!\n", count ++);  
4.     swap(&new, &old);  
5.     printf("count = %d in sub!\n", count ++);  
6.     swap(&new, &old);  
7.     printf("count = %d in sub!\n", count ++);  
8.     swap(&new, &old);  
9.     printf("count = %d in sub!\n", count ++);  
10.     swap(&new, &old);  
11.     printf("count = %d in sub!\n", count ++);  
12.     quit = 1;  
13.     swap(&new, &old);  
14. }  

    在编写程序的时候，最恐怖的事情就是堆栈溢出了。但是在操作系统中，我们完全可以自己判断当前的堆栈是否已经溢出。因为我们知道，在线程调度的时候，保存的堆栈esp永远指向最低的那个地址。 [cpp] view plaincopy

1. int check_stack_overflow(unsigned int base, unsigned int current)  
2. {  
3.     assert(0 != base && 0 != current);  
4.   
5.     return (current < base) ? 1 :0;  
6. }  

    当然，这些说的都是线程调度的事，你也可以编写输入输出命令，实现对嵌入式操作系统的某种控制。要打印什么，设置什么，保存什么，都可以通过你的输入命令来解析执行，这些都是和signal处理是分开来的。后面这部分还要详细讨论，这里可以稍微添加一下， [cpp] view plaincopy

1. int main()  
2. {  
3.     char val;  
4.   
5.     task_init();  
6.     set_timer();  
7.     signal(SIGALRM, signal_handler);  
8.   
9.     while(1)  
10.     {  
11.         scanf("%c", &val);  
12.     }  
13.   
14.     exit(0);  
15.     return 1;  
16. }  

    最后，还是老规矩，附上详细的代码。虽然这一过程有点繁琐和冗余，但是至少看上去更完整一些。 [cpp] view plaincopy

1. #include <stdio.h>  
2. #include <time.h>  
3. #include <stdlib.h>  
4. #include <signal.h>  
5. #include <assert.h>  
6. #include <sys/time.h>  
7.   
8. #define UINT32 unsigned int  
9. #define STACK_LENGTH  512  
10.   
11. static struct itimerval oldtv;  
12. UINT32 old = 0;  
13. UINT32 new = 0;  
14. UINT32 count = 0;  
15. UINT32 data[STACK_LENGTH] = {0};  
16. UINT32 quit = 0;  
17.   
18. void set_timer()  
19. {  
20.     struct itimerval itv;  
21.     itv.it_interval.tv_sec = 1;  
22.     itv.it_interval.tv_usec = 0;  
23.     itv.it_value.tv_sec = 1;  
24.     itv.it_value.tv_usec = 0;  
25.     setitimer(ITIMER_REAL, &itv, &oldtv);  
26. }  
27.   
28. void swap(UINT32* prev, UINT32* next)  
29. {  
30.     __asm("push %%eax\n\t"  
31.           "push %%ebx\n\t"  
32.           "push %%ecx\n\t"  
33.           "push %%edx\n\t"  
34.           "push %%esi\n\t"  
35.           "push %%edi\n\t"  
36.           "push %%ebp\n\t"  
37.           "push %%esp\n\t"  
38.           "lea 0x8(%%ebp), %%eax\n\t"  
39.           "mov (%%eax), %%eax\n\t"  
40.           "mov %%esp, (%%eax)\n\t"  
41.   
42.           "lea 0xc(%%ebp), %%eax\n\t"  
43.           "mov (%%eax), %%eax\n\t"  
44.           "mov (%%eax), %%esp\n\t"  
45.           "pop %%esp\n\t"  
46.           "pop %%ebp\n\t"  
47.           "pop %%edi\n\t"  
48.           "pop %%esi\n\t"  
49.           "pop %%edx\n\t"  
50.           "pop %%ecx\n\t"  
51.           "pop %%ebx\n\t"  
52.           "pop %%eax\n\t"  
53.           ::);  
54. }  
55.   
56. void hello()  
57. {  
58.     printf("count = %d in sub!\n", count ++);  
59.     swap(&new, &old);  
60.     printf("count = %d in sub!\n", count ++);  
61.     swap(&new, &old);  
62.     printf("count = %d in sub!\n", count ++);  
63.     swap(&new, &old);  
64.     printf("count = %d in sub!\n", count ++);  
65.     swap(&new, &old);  
66.     printf("count = %d in sub!\n", count ++);  
67.     quit = 1;  
68.     swap(&new, &old);  
69. }  
70.   
71. void task_init()  
72. {  
73.     UINT32 unit = STACK_LENGTH;  
74.   
75.     memset((void*)data, 0, STACK_LENGTH * sizeof(UINT32));  
76.     data[unit -1] = (UINT32) hello;  
77.     data[unit -2] = 0;  
78.     data[unit -3] = 0;  
79.     data[unit -4] = 0;  
80.     data[unit -5] = 0;  
81.     data[unit -6] = 0;  
82.     data[unit -7] = 0;  
83.     data[unit -8] = 0;  
84.     data[unit -9] = 0;  
85.     data[unit -10] = (UINT32) &data[unit - 9];  
86.     new = (UINT32) &data[unit -10];  
87. }  
88.   
89. int check_stack_overflow(unsigned int base, unsigned int current)  
90. {  
91.     assert(0 != base && 0 != current);  
92.   
93.     return (current < base) ? 1 :0;  
94. }  
95.   
96. void signal_handler(int m)  
97. {  
98.     if(0 == quit)     
99.     {  
100.         swap(&old, &new);  
101.         assert(0 == check_stack_overflow(data,new));  
102.         return;  
103.     }  
104.   
105.     printf("count = %d in main!\n", count ++);  
106. }  
107.   
108. int main()  
109. {  
110.     char val;  
111.   
112.     task_init();  
113.     set_timer();  
114.     signal(SIGALRM, signal_handler);  
115.   
116.     while(1)  
117.     {  
118.         scanf("%c", &val);  
119.     }  
120.   
121.     exit(0);  
122.     return 1;  
123. } 
     

嵌入式操作系统内核原理和开发（多线程轮转）

之前我们也谈到了线程创建，基本上简单的系统就可以跑起来了，但是还没有到多线程运行的地步。所以，我们下面试图所要做的工作就是创建更多的线程，让更多的线程运行起来。为了做好这一点，首先我们需要对task_init重新修整一下， [cpp] view plaincopy

1. void task_init(int index, UINT32 data[], int size, void (*func)())  
2. {  
3.         UINT32 unit = size;  
4.   
5.         memset((void*)data, 0, size * sizeof(UINT32));  
6.         data[unit -1] = (UINT32) func;  
7.         data[unit -2] = 0;  
8.         data[unit -3] = 0;  
9.         data[unit -4] = 0;  
10.         data[unit -5] = 0;  
11.         data[unit -6] = 0;  
12.         data[unit -7] = 0;  
13.         data[unit -8] = 0;  
14.         data[unit -9] = 0;  
15.         data[unit -10] = (UINT32) &data[unit - 9];  
16.         new[index] = (UINT32) &data[unit -10];  
17. }  

    这是一个创建线程的函数，有堆栈、大小、函数入口。那么，我们的函数什么时候创建呢，其实就是在系统的开始位置就可以，

[cpp] view plaincopy

1. void set_all_task()  
2. {  
3.         int index;  
4.   
5.         for(index = 0; index < THREAD_MAX_NUMBER; index ++)  
6.             task_init(index, task_stack[index], STACK_LENGTH, hello);  
7. }  

    既然任务创建没有问题，那么下面就会涉及到简单轮转的问题。其实我们的方法特别简单，就是根据current_thread_id叠加，每一个thread都有自己的运转机会。代码如下所示，

[cpp] view plaincopy

1. void signal_handler(int m)  
2. {  
3.         current_thread_id = current_thread_id % THREAD_MAX_NUMBER;  
4.   
5.         if(0 == quit[current_thread_id])  
6.         {  
7.             swap(&old, &new[current_thread_id]);  
8.         }  
9.   
10.         printf("count = %d in main!\n\n",  count ++);  
11.         current_thread_id ++;  
12. }  

    当然，为了要实现真正的多线程运行，我们还要保证线程始终在运行。要达到这一点也不是很复杂，只需要把子函数设计为while（1）即可，

[cpp] view plaincopy

1. void hello()  
2. {  
3.         while(1) {  
4.             printf("id = %i, count = %d in thread!\n",current_thread_id,  count ++);  
5.             swap(&new[current_thread_id], &old);  
6.   
7.             printf("id = %i, count = %d in thread!\n",current_thread_id,  count ++);  
8.             swap(&new[current_thread_id], &old);  
9.         }  
10. }  

    基本上要做到以上几点就可以实现了，最后给出完整的代码，大家可以在linux系统好好试试这个代码。

[cpp] view plaincopy

1. #include <stdio.h>  
2. #include <time.h>  
3. #include <stdlib.h>  
4. #include <signal.h>  
5. #include <assert.h>  
6. #include <sys/time.h>  
7.   
8. #define UINT32 unsigned   int  
9. #define STACK_LENGTH      512  
10. #define THREAD_MAX_NUMBER 10  
11.   
12. struct itimerval oldtv;  
13. UINT32 old   = 0;  
14. UINT32 count = 0;  
15. UINT32 task_stack[THREAD_MAX_NUMBER][STACK_LENGTH] = {0};  
16. UINT32 new[THREAD_MAX_NUMBER]  = {0};  
17. UINT32 quit[THREAD_MAX_NUMBER] = {0};  
18. UINT32 current_thread_id = 0;  
19.   
20. void set_timer()  
21. {  
22.         struct itimerval itv;  
23.         itv.it_interval.tv_sec = 1;  
24.         itv.it_interval.tv_usec = 0;  
25.         itv.it_value.tv_sec = 1;  
26.         itv.it_value.tv_usec = 0;  
27.         setitimer(ITIMER_REAL, &itv, &oldtv);  
28. }  
29.   
30. void swap(UINT32* prev, UINT32* next)  
31. {  
32.     __asm("push %%eax\n\t"  
33.           "push %%ebx\n\t"  
34.           "push %%ecx\n\t"  
35.           "push %%edx\n\t"  
36.           "push %%esi\n\t"  
37.           "push %%edi\n\t"  
38.           "push %%ebp\n\t"  
39.           "push %%esp\n\t"  
40.           "lea 0x8(%%ebp), %%eax\n\t"  
41.           "mov (%%eax), %%eax\n\t"  
42.           "mov %%esp, (%%eax)\n\t"  
43.   
44.           "lea 0xc(%%ebp), %%eax\n\t"  
45.           "mov (%%eax), %%eax\n\t"  
46.           "mov (%%eax), %%esp\n\t"  
47.           "pop %%esp\n\t"  
48.           "pop %%ebp\n\t"  
49.           "pop %%edi\n\t"  
50.           "pop %%esi\n\t"  
51.           "pop %%edx\n\t"  
52.           "pop %%ecx\n\t"  
53.           "pop %%ebx\n\t"  
54.           "pop %%eax\n\t"  
55.           ::);  
56. }  
57.   
58. void hello()  
59. {  
60.         while(1) {  
61.             printf("id = %i, count = %d in thread!\n",current_thread_id,  count ++);  
62.             swap(&new[current_thread_id], &old);  
63.   
64.             printf("id = %i, count = %d in thread!\n",current_thread_id,  count ++);  
65.             swap(&new[current_thread_id], &old);  
66.         }  
67. }  
68.   
69. void task_init(int index, UINT32 data[], int size, void (*func)())  
70. {  
71.         UINT32 unit = size;  
72.   
73.         memset((void*)data, 0, size * sizeof(UINT32));  
74.         data[unit -1] = (UINT32) func;  
75.         data[unit -2] = 0;  
76.         data[unit -3] = 0;  
77.         data[unit -4] = 0;  
78.         data[unit -5] = 0;  
79.         data[unit -6] = 0;  
80.         data[unit -7] = 0;  
81.         data[unit -8] = 0;  
82.         data[unit -9] = 0;  
83.         data[unit -10] = (UINT32) &data[unit - 9];  
84.         new[index] = (UINT32) &data[unit -10];  
85. }  
86.   
87. void signal_handler(int m)  
88. {  
89.         current_thread_id = current_thread_id % THREAD_MAX_NUMBER;  
90.   
91.         if(0 == quit[current_thread_id])  
92.         {  
93.             swap(&old, &new[current_thread_id]);  
94.         }  
95.   
96.         printf("count = %d in main!\n\n",  count ++);  
97.         current_thread_id ++;  
98. }  
99.   
100. void set_all_task()  
101. {  
102.         int index;  
103.   
104.         for(index = 0; index < THREAD_MAX_NUMBER; index ++)  
105.             task_init(index, task_stack[index], STACK_LENGTH, hello);  
106. }  
107.   
108. int main()  
109. {  
110.         char val;  
111.   
112.         set_all_task();  
113.         set_timer();  
114.         signal(SIGALRM, signal_handler);  
115.   
116.         while(1)  
117.         {  
118.             scanf("%c", &val);  
119.         }  
120.   
121.         exit(0);  
122.         return 1;  
123. } 
     

嵌入式操作系统内核原理和开发（通用优先级调度）

相比较其他调度算法而言，时间片的轮转更多的注重公平性。但是，任务与任务之间也是有先后之分的，有的任务我们希望多安排一些时间片，而有的任务我们则希望少安排一些时间片。比较说，如果我们在上网的话，我们就希望上网的操作响应的更快一些；如果我们在进行GUI操作，我们当然就希望图形响应更快一些。这些都是可以理解的，下面我们就绪要对数据结构进行一些修改。
[cpp] view plaincopy

1. typedef struct _TASK_INFO  
2. {  
3.     UINT32 id;  
4.     UINT32* stack;  
5.     UINT32 size;  
6.     UINT32 context;  
7.     UINT32 priority;  
8.     UINT32 time_slice;  
9.     void (*func)();  
10.   
11. }TASK_INFO;  

    这里的priority就是当前线程的优先级，所以最简单的方法就是根据priority直接分配对应的time_slice。也就是这个函数，
[cpp] view plaincopy

1. void reset_time_slice ()  
2. {  
3.     int index;  
4.   
5.     for(index = 0; index < THREAD_MAX_NUMBER; index++)  
6.         gAllTask[index].time_slice = gAllTask[index].priority + 1;  
7. }  

    所以，以后每次调度的时候，我们就首先寻找当前最高优先级的任务，看看当前任务安排的时间片是否用完了，没有用完就继续运行。如果当前优先级的任务已经没有时间片了，那么此时就可以安排低优先级的任务进行调度了。
[cpp] view plaincopy

1. void signal_handler(int m)  
2. {  
3.         int index;  
4.   
5. start:  
6.         index = find_next_thread();  
7.         if(-1 == index)  
8.         {  
9.             reset_time_slice();  
10.             goto start;  
11.         }  
12.   
13.         gAllTask[index].time_slice --;  
14.         current_thread_id = index;  
15.         swap(&old, &gAllTask[current_thread_id].context);  
16. }  

    下面，我们就根据任务优先级挑选下一个需要运行的thread了，
[cpp] view plaincopy

1. int find_next_thread()  
2. {  
3.     int index;  
4.   
5.     for(index = THREAD_MAX_NUMBER -1; index >=0; index --)  
6.     {  
7.         if(0 != gAllTask[index].time_slice)  
8.             break;  
9.     }  
10.   
11.     return index;        
12. }  

    整个代码的流程也不复杂，大家可以运行、单步调试一把，试试看。
[cpp] view plaincopy

1. #include <stdio.h>  
2. #include <time.h>  
3. #include <stdlib.h>  
4. #include <signal.h>  
5. #include <assert.h>  
6. #include <string.h>  
7. #include <sys/time.h>  
8.   
9. #define UINT32 unsigned   int  
10. #define STACK_LENGTH      512  
11. #define THREAD_MAX_NUMBER 10  
12.   
13. typedef struct _TASK_INFO  
14. {  
15.     UINT32 id;  
16.     UINT32* stack;  
17.     UINT32 size;  
18.     UINT32 context;  
19.     UINT32 priority;  
20.     UINT32 time_slice;  
21.     void (*func)();  
22.   
23. }TASK_INFO;  
24.   
25. static struct itimerval oldtv;  
26. UINT32 old   = 0;  
27. UINT32 count = 0;  
28. UINT32 task_stack[THREAD_MAX_NUMBER][STACK_LENGTH] = {0};  
29. TASK_INFO gAllTask[THREAD_MAX_NUMBER] = {0};  
30. UINT32 current_thread_id = 0;  
31.   
32. void set_timer()  
33. {  
34.         struct itimerval itv;  
35.         itv.it_interval.tv_sec = 1;  
36.         itv.it_interval.tv_usec = 0;  
37.         itv.it_value.tv_sec = 1;  
38.         itv.it_value.tv_usec = 0;  
39.         setitimer(ITIMER_REAL, &itv, &oldtv);  
40. }  
41.   
42. void swap(UINT32* prev, UINT32* next)  
43. {  
44.     __asm("push %%eax\n\t"  
45.           "push %%ebx\n\t"  
46.           "push %%ecx\n\t"  
47.           "push %%edx\n\t"  
48.           "push %%esi\n\t"  
49.           "push %%edi\n\t"  
50.           "push %%ebp\n\t"  
51.           "push %%esp\n\t"  
52.           "lea 0x8(%%ebp), %%eax\n\t"  
53.           "mov (%%eax), %%eax\n\t"  
54.           "mov %%esp, (%%eax)\n\t"  
55.   
56.           "lea 0xc(%%ebp), %%eax\n\t"  
57.           "mov (%%eax), %%eax\n\t"  
58.           "mov (%%eax), %%esp\n\t"  
59.           "pop %%esp\n\t"  
60.           "pop %%ebp\n\t"  
61.           "pop %%edi\n\t"  
62.           "pop %%esi\n\t"  
63.           "pop %%edx\n\t"  
64.           "pop %%ecx\n\t"  
65.           "pop %%ebx\n\t"  
66.           "pop %%eax\n\t"  
67.           ::);  
68. }  
69.   
70. void hello()  
71. {  
72.         int temp = 0;  
73.   
74.         while(1) {  
75.             printf("id = %d, temp = %d, count = %d in thread!\n",current_thread_id,  temp ++, count ++);  
76.             swap(&gAllTask[current_thread_id].context, &old);  
77.   
78.             printf("id = %d, temp = %d, count = %d in thread!\n",current_thread_id,  temp ++, count ++);  
79.             swap(&gAllTask[current_thread_id].context, &old);  
80.         }  
81. }  
82.   
83. int find_next_thread()  
84. {  
85.     int index;  
86.   
87.     for(index = THREAD_MAX_NUMBER -1; index >=0; index --)  
88.     {  
89.         if(0 != gAllTask[index].time_slice)  
90.             break;  
91.     }  
92.   
93.     return index;        
94. }  
95.   
96. void reset_time_slice ()  
97. {  
98.     int index;  
99.   
100.     for(index = 0; index < THREAD_MAX_NUMBER; index++)  
101.         gAllTask[index].time_slice = gAllTask[index].priority + 1;  
102. }  
103.   
104. void task_init(int index)  
105. {  
106.         UINT32 unit = gAllTask[index].size;  
107.         UINT32* pData = gAllTask[index].stack;  
108.   
109.         memset((void*)pData,(int) 0, unit * sizeof(UINT32));  
110.         pData[unit -1] = (UINT32) gAllTask[index].func;  
111.         pData[unit -2] = 0;  
112.         pData[unit -3] = 0;  
113.         pData[unit -4] = 0;  
114.         pData[unit -5] = 0;  
115.         pData[unit -6] = 0;  
116.         pData[unit -7] = 0;  
117.         pData[unit -8] = 0;  
118.         pData[unit -9] = 0;  
119.         pData[unit -10] = (UINT32) &pData[unit - 9];  
120.         gAllTask[index].context = (UINT32) &pData[unit -10];  
121. }  
122.   
123. void signal_handler(int m)  
124. {  
125.         int index;  
126.   
127. start:  
128.         index = find_next_thread();  
129.         if(-1 == index)  
130.         {  
131.             reset_time_slice();  
132.             goto start;  
133.         }  
134.   
135.         gAllTask[index].time_slice --;  
136.         current_thread_id = index;  
137.         swap(&old, &gAllTask[current_thread_id].context);  
138. }  
139.   
140. void set_all_task()   
141. {  
142.         int index;  
143.         memset(gAllTask, 0, sizeof(gAllTask));  
144.   
145.         for(index = 0; index < THREAD_MAX_NUMBER; index ++)  
146.         {  
147.             gAllTask[index].id = index;  
148.             gAllTask[index].stack = task_stack[index];  
149.             gAllTask[index].size = STACK_LENGTH;  
150.             gAllTask[index].context = 0;  
151.             gAllTask[index].func = hello;  
152.             gAllTask[index].priority = index;  
153.             gAllTask[index].time_slice = index + 1;  
154.   
155.             task_init(index);  
156.         }  
157. }  
158.   
159. int main()  
160. {  
161.         char val;  
162.   
163.         set_all_task();  
164.         set_timer();  
165.         signal(SIGALRM, signal_handler);  
166.   
167.         while(1)  
168.         {  
169.             scanf("%c", &val);  
170.         }  
171.   
172.         exit(0);  
173.         return 1;  
174. } 
     

嵌入式操作系统内核原理和开发（改进型优先级调度）

上面的一篇博客说到了优先级调度，但是那个优先级调度算法比较极端。打个比方说，现在王先生有三个小孩，分别是老大、老二、老三。假设现在到了饭点，王先生需要给三个小孩喂饭。此时如果是时间片轮转的话，那么就是绝对公平，王先生每人一口不停地进行喂饭。如果是优先级调度，那么王先生首先自己有一个优先级考量，比如说三个小孩按照年龄顺序优先级是逐渐提高的，毕竟小孩需要更多的照顾嘛。这个时候如果需要进行喂饭的话，那么王先生需要首先伺候好最小的那个小孩老三，才会有时间照顾老二，至于老大什么时候才能得到照顾那就看造化了。

    现在，我们打算重新换一种方法。假设三个小孩的优先级分别是1、2、3，其中年龄越小优先级越高，3代表高优先级。接着，我们按照优先级给三个小孩安排时间片，分别是1、2、3。同时，这个时间片不光代表了当前可用的剩余时间，还代表了小孩此时的临时优先级。

    （1）首先王先生给老三喂饭，时间片降低1，即临时优先级为2；

    （2）接着王先生判断当前优先级最高的仍为老三，毕竟老二的优先级也没有超过老三，所以老三的时间片降1，临时优先级为1；

    （3）王先生获知当前优先级最高的为老二，老二获得时间片；

    （4）此时王先生发现三个孩子的临时优先级都一样，那么就会按照固定优先级的大小依次对老三、老二、老大进行喂饭。

    我们发现，这中间受益最大的就是老二。当然，我们可以做进一步推论，如果老王的孩子越多，那么优先级处于中间的孩子在时间片的分配上将更加均匀，响应也会更加及时，交互性也会变得很好。

    根据以上的想法，我们重新改写了优先级调度算法，修改为改进型优先级调度算法，

[cpp] view plaincopy

1. int find_next_thread()  
2. {  
3.     int index;  
4.     int choice = THREAD_MAX_NUMBER -1;  
5.     int value = gAllTask[choice].time_slice;  
6.   
7.     for(index = choice -1; index >= 0; index --)  
8.     {  
9.         if(value < gAllTask[index].time_slice)  
10.         {  
11.             choice = index;  
12.             value = gAllTask[index].time_slice;  
13.         }  
14.     }  
15.   
16.     if(0 == value)  
17.         choice = -1;  
18.   
19.     return choice;        
20. }  

    当然，加上原来的时间片轮转调度、通用优先级调度方法，此时就存在三种调度方法了。我们可以自己设置宏，通过宏的设置灵活选用调度算法， [cpp] view plaincopy

1. #define TIME_ROUND_SCHEDULE     0  
2. #define HARD_PRIORITY_SCHEDULE  0  
3. #define SOFT_PRIORITY_SCHEDULE  1     

    这些代码都是可以在系统*存的。选用什么算法，取决于实际情况是什么样的情形。
[cpp] view plaincopy

1. #include <stdio.h>  
2. #include <time.h>  
3. #include <stdlib.h>  
4. #include <signal.h>  
5. #include <assert.h>  
6. #include <string.h>  
7. #include <sys/time.h>  
8.   
9. #define UINT32 unsigned         int  
10. #define STACK_LENGTH            512  
11. #define THREAD_MAX_NUMBER       10  
12. #define TIME_ROUND_SCHEDULE     0  
13. #define HARD_PRIORITY_SCHEDULE  0  
14. #define SOFT_PRIORITY_SCHEDULE  1     
15.   
16. typedef struct _TASK_INFO  
17. {  
18.     UINT32 id;  
19.     UINT32* stack;  
20.     UINT32 size;  
21.     UINT32 context;  
22.     UINT32 priority;  
23.     UINT32 time_slice;  
24.     void (*func)();  
25.   
26. }TASK_INFO;  
27.   
28. static struct itimerval oldtv;  
29. UINT32 old   = 0;  
30. UINT32 count = 0;  
31. UINT32 task_stack[THREAD_MAX_NUMBER][STACK_LENGTH] = {0};  
32. TASK_INFO gAllTask[THREAD_MAX_NUMBER] = {0};  
33. UINT32 current_thread_id = 0;  
34.   
35. void set_timer()  
36. {  
37.         struct itimerval itv;  
38.         itv.it_interval.tv_sec = 1;  
39.         itv.it_interval.tv_usec = 0;  
40.         itv.it_value.tv_sec = 1;  
41.         itv.it_value.tv_usec = 0;  
42.         setitimer(ITIMER_REAL, &itv, &oldtv);  
43. }  
44.   
45. void swap(UINT32* prev, UINT32* next)  
46. {  
47.     __asm("push %%eax\n\t"  
48.           "push %%ebx\n\t"  
49.           "push %%ecx\n\t"  
50.           "push %%edx\n\t"  
51.           "push %%esi\n\t"  
52.           "push %%edi\n\t"  
53.           "push %%ebp\n\t"  
54.           "push %%esp\n\t"  
55.           "lea 0x8(%%ebp), %%eax\n\t"  
56.           "mov (%%eax), %%eax\n\t"  
57.           "mov %%esp, (%%eax)\n\t"  
58.   
59.           "lea 0xc(%%ebp), %%eax\n\t"  
60.           "mov (%%eax), %%eax\n\t"  
61.           "mov (%%eax), %%esp\n\t"  
62.           "pop %%esp\n\t"  
63.           "pop %%ebp\n\t"  
64.           "pop %%edi\n\t"  
65.           "pop %%esi\n\t"  
66.           "pop %%edx\n\t"  
67.           "pop %%ecx\n\t"  
68.           "pop %%ebx\n\t"  
69.           "pop %%eax\n\t"  
70.           ::);  
71. }  
72.   
73. void hello()  
74. {  
75.         int temp = 0;  
76.   
77.         while(1) {  
78.             printf("id = %d, temp = %d, count = %d in thread!\n",current_thread_id,  temp ++, count ++);  
79.             swap(&gAllTask[current_thread_id].context, &old);  
80.   
81.             printf("id = %d, temp = %d, count = %d in thread!\n",current_thread_id,  temp ++, count ++);  
82.             swap(&gAllTask[current_thread_id].context, &old);  
83.         }  
84. }  
85.   
86. #if HARD_PRIORITY_SCHEDULE  
87. int find_next_thread()  
88. {  
89.     int index;  
90.   
91.     for(index = THREAD_MAX_NUMBER -1; index >=0; index --)  
92.     {  
93.         if(0 != gAllTask[index].time_slice)  
94.             break;  
95.     }  
96.   
97.     return index;        
98. }  
99.   
100. #endif  
101.   
102.   
103. #if SOFT_PRIORITY_SCHEDULE  
104. int find_next_thread()  
105. {  
106.     int index;  
107.     int choice = THREAD_MAX_NUMBER -1;  
108.     int value = gAllTask[choice].time_slice;  
109.   
110.     for(index = choice -1; index >= 0; index --)  
111.     {  
112.         if(value < gAllTask[index].time_slice)  
113.         {  
114.             choice = index;  
115.             value = gAllTask[index].time_slice;  
116.         }  
117.     }  
118.   
119.     if(0 == value)  
120.         choice = -1;  
121.   
122.     return choice;        
123. }  
124.   
125. #endif  
126.   
127. void reset_time_slice ()  
128. {  
129.     int index;  
130.   
131.     for(index = 0; index < THREAD_MAX_NUMBER; index++)  
132.         gAllTask[index].time_slice = gAllTask[index].priority + 1;  
133. }  
134.   
135. void task_init(int index)  
136. {  
137.         UINT32 unit = gAllTask[index].size;  
138.         UINT32* pData = gAllTask[index].stack;  
139.   
140.         memset((void*)pData,(int) 0, unit * sizeof(UINT32));  
141.         pData[unit -1] = (UINT32) gAllTask[index].func;  
142.         pData[unit -2] = 0;  
143.         pData[unit -3] = 0;  
144.         pData[unit -4] = 0;  
145.         pData[unit -5] = 0;  
146.         pData[unit -6] = 0;  
147.         pData[unit -7] = 0;  
148.         pData[unit -8] = 0;  
149.         pData[unit -9] = 0;  
150.         pData[unit -10] = (UINT32) &pData[unit - 9];  
151.         gAllTask[index].context = (UINT32) &pData[unit -10];  
152. }  
153.   
154. #if TIME_ROUND_SCHEDULE  
155. void signal_handler(int m)  
156. {  
157.         current_thread_id = current_thread_id % THREAD_MAX_NUMBER;  
158.         swap(&old, &gAllTask[current_thread_id].context);  
159.         current_thread_id ++;  
160. }  
161.   
162. #else  
163. void signal_handler(int m)  
164. {  
165.         int index;  
166.   
167. start:  
168.         index = find_next_thread();  
169.         if(-1 == index)  
170.         {  
171.             reset_time_slice();  
172.             goto start;  
173.         }  
174.   
175.         gAllTask[index].time_slice --;  
176.         current_thread_id = index;  
177.         swap(&old, &gAllTask[current_thread_id].context);  
178. }  
179. #endif  
180.   
181.   
182. void set_all_task()   
183. {  
184.         int index;  
185.         memset(gAllTask, 0, sizeof(gAllTask));  
186.   
187.         for(index = 0; index < THREAD_MAX_NUMBER; index ++)  
188.         {  
189.             gAllTask[index].id = index;  
190.             gAllTask[index].stack = task_stack[index];  
191.             gAllTask[index].size = STACK_LENGTH;  
192.             gAllTask[index].context = 0;  
193.             gAllTask[index].func = hello;  
194.             gAllTask[index].priority = index;  
195.             gAllTask[index].time_slice = index + 1;  
196.   
197.             task_init(index);  
198.         }  
199. }  
200.   
201. int main()  
202. {  
203.         char val;  
204.   
205.         set_all_task();  
206.         set_timer();  
207.         signal(SIGALRM, signal_handler);  
208.   
209.         while(1)  
210.         {  
211.             scanf("%c", &val);  
212.         }  
213.   
214.         exit(0);  
215.         return 1;  
216. } 
     

嵌入式操作系统内核原理和开发（头文件调整）

很长一段时间，我个人对头文件的功能了解得不是很明白。虽然在平时的开发中，对于头文件也没有犯过什么大的错误，但是总觉得对头文件这块理解得不是很透彻。所以趁着这次嵌入式开发的机会，好好对头文件这部分的内容进行了分析和总结。下面我们主要从两个方面对头文件进行分析，即头文件是做什么的，头文件编写的过程中要注意些什么？

 

    （1）头文件的作用

    其实很多的编程语言是没有头文件的，比如说C#、java语言。为什么呢，因为这些语言数据结构和函数操作是捆绑在一起的。而C语言则不一样，它是把头文件和实现文件分开来的。头文件的内容主要有哪些呢，也就是嵌套头文件、宏定义、数据类型、函数原型定义、static函数等等。

 

    （2）头文件的编写

 

    a）头文件要简洁

    很多源文件在编写的时候常常喜欢添加很多的头文件，不管是需要的还是不需要的。可是，我们要知道，头文件的作用主要是定义数据类型和函数类型的。本质上来说，头文件很少会创建实质性的代码，不管是数据段的内容，还是代码段的内容。简洁的头文件不仅有利于快速排除编译故障，还能提高编译的速度。有经验的朋友都知道，源文件的编译错误比较容易解决，而头文件的编译错误常常十分复杂。所以，我们必须在一切可能的条件下保证头文件的简洁。

 

    b）头文件注意互斥性

   注意头文件的互斥性，需要我们在开发中养成良好的编程习惯。不管是创建头文件，首先要做的事情就是添加编译宏。看上去这是一个十分不起眼的举动，但是常常可以帮助你减少许多不必要的麻烦。

[cpp] view plaincopy

1. #ifndef _DATA_H  
2. #define _DATA_H  
3.   
4. #endif  

    c）全局变量不要在头文件里面定义，如果是外部引用，必须添加上extern

[cpp] view plaincopy

1. extern int g_Data;    

   

    d）不要在头文件里面实现函数，如果要实现，也必须要添加static

[cpp] view plaincopy

1. static int add(int a, int b)  
2. {  
3.     return a + b;  
4. }  

    e）头文件当中如果需要嵌入别的头文件，那么只是为了引用另外一个头文件的数据结构

 

    f）头文件中引用的数据类型如果没有说明，那么在被源文件引用的时候，只要保证其他的头文件存在这个数据类型定义即可

 

    g）源文件引用头文件的时候需要注意头文件的顺序，有的时候顺序变了，可能编译就失败了。原因就是之前后面头文件中定义的数据类型找不到出处了

 

    h）某些工程没有把头文件和源文件绑定在一起，修改头文件必须删除工程重新编译

 

    i）头文件的存在只是为了源文件才存在的，如果没有必要不要写头文件。要写，影响范围也要控制在最小的范围内

 

    j）如果头文件定义了数据结构，那么需要嵌入引用头文件，反之如果只是指针，声明一下即可，比如说

[cpp] view plaincopy

1. struct _Data;  
2. typedef struct _Data Data;  

 

   k）如果有可能经常整理自己的头文件，全部删除再一个一个添加，这样就知道哪些是我们需要的，哪些不是

 

    l）对于某些宏，如果不确定文件本身是在哪里定义的，可以在源文件中再定义一次，这样编译器就会精确提示我们原来这个宏是在那里定义的

    好了，差不多就这么多了。

 

嵌入式操作系统内核原理和开发（内存分配算法）

内存分配是操作系统必须面对的一个环节，除非这个系统本身不需要内存安排，所有业务可以通过全局数据和堆栈搞定。内存分配其实不困难，但是由内存引申出来的东西就比较复杂了。早前没有MMU，系统本身的空间和用户空间没有优先级之分，所以不同的程序之间的内存都是共享的，相互影响也是不可避免的。所以，一般来说，除了内存分配之外，还需要一些日志信息、检测信息帮助我们进行调试和分析。当然，这些都不是我们关心的内容，我们关注的就是内存有哪些通用的分配算法。

 

    （1）固定内存分配

    固定内存分配算法是最简单的算法，也是最好理解的算法。比如说有16M内存，现在我们假设分配的基本内存是4K，那么总共有16M/4K = 4K个单元。所以，如果用户想申请内存，最多就是4K次。如果用户想要多一点内存，那么系统把相邻的内存分给用户使用即可。

 

    （2）链表内存分配

    固定内存分配虽然好，但是还有一个缺点，那就是如果存在很多的浪费机会。试想一下，如果用户只要几十个byte，那么也要分配给它4K个字节，浪费的空间超过了99%。所以在此基础之上，我们提出了链表内存算法。链表算法中保存有空闲结点，内存释放的时候，那么内存查到空闲结点，该合并合并，该释放的释放；当然如果要申请内存的话，那方法就多了去了，可以最差申请、最优申请、最好申请，这些都是可以的。

 

    （3）伙伴算法

    链表算法相比较固定内存算法，可以节省不少内存。但是链表算法本身有一个特点，那就是容易形成内存碎片。所以，我们可以结合固定分配和链表算法的特点，把内存分配成8、16、32、64、128、256、512大小的几种链表。链表内部的大小都是相同的，链表之间是倍数的关系。分配内存的时候，我们首先寻找最合适的链表，然后分配内存，如果内存空间不够，可以向高一级的内存链表申请，这样拆解下来的内存可以分配到低一级别的链表；释放内存的时候，我们也要注意内存的合并和组合。

 

    （4）基于内存池的伙伴算法

    伙伴算法固然好，但是如果某一种内存申请特别频繁，那么在伙伴算法中就需要进行反复的拆分和合并处理。一方面，这会影响了内存的分配效率，另外一方面也比较容易造成内存的分配碎片。所以，我们可以在伙伴算法的基础之上构建一个内存池，在内存释放的时候，只是标注当前内存不再使用，但是并没有真正释放，等到内存池中所有的内存都不再使用的时候再进行释放，这在一定的程度上会提高内存的分配效率。特别是系统运行一段时间后，这种效果是特别明显的。

 

    （5）工作集算法

    工作集的算法本质上说不是一种算法，它只是一种基本思想。我们知道，在系统稳定之后，内存中分配的大小、配置的比例关系都是相对固定的，变化不是特别大。如果我们可以把这些数据给记录下来，在系统启动的时候预先分配好这些内存，那么不就可以提升系统的启动速度了吗？当然工作集中的参数设定更多的是一种经验值，它需要我们综合各种因素进行分析，反复比较才会得出比较好的结果。

 

    这五种算法只是给出了基本思想，只有付出于实践，多加操练才能从中有所收获。

嵌入式操作系统内核原理和开发（基于链表节点的内存分配算法）

链接节点的内存分配方法，其实就是一种按需分配的内存分配方法。简单一点说，就是你需要多少内存，我就给你多少内存。当然，为了把分配的内存都连起来，我们还需要对分配节点进行管理记录。就比如下面这个数据结构， [cpp] view plaincopy

1. typedef struct _MNG_NODE  
2. {  
3.     struct _MNG_NODE* next;  
4.     unsigned int size;  
5. }MNG_NODE;  

    其中，next节点记录了下面一个节点的位置，size表示了当前节点下方的内存大小。在内存初始化的时候，我们默认起始内存块就是一个大节点，其中前面8个字节就是上面的内容。此时，如果需要进行内存拆分，我们就可以把一个节点拆分成两个节点，就比如这样， [cpp] view plaincopy

1. pNew = (MNG_NODE*)((char*)pOld + sizeof(MNG_NODE) + pOld->size - (sizeof(MNG_NODE) + size));  

    pNew代表了新生成的结点，pOld代表了原来的节点。为了不影响原来的节点，每次分配新节点的时候必须在内存的高端位置进行分配。这样也保证了原来节点结构和数据的连贯性。当然分配结束之后，只需要对节点的的size重新进行一下赋值就可以了。
[cpp] view plaincopy

1. pNew->size = size;  
2. pOld->size -= sizeof(MNG_NODE) + size;  

    此时pOld节点会归还到pFreeList当中，而生成的pNew节点则插入到pAllocList当中。其中，pFreeList表示当前的空闲节点，pAllocList表示已分配节点。相比较而言，内存的释放就比较简单，只需要把节点找出来插入到pAllocList中即可。当然，此时如果能做一下前后节点的合并工作就更好了。

    不过，上面描述的步骤只是就比较重要知识点讲解了一下。在真正设计代码的过程中还需要考虑到节点的查找、内存大小的判断、数据初始化、链表插入、测试用例编写等工作，步骤会稍微繁琐一下。下面我们就给出完整的代码示例。

[cpp] view plaincopy

1. /************************************************* 
2. *      malloc & free in link node algorithm 
3. **************************************************/  
4.   
5. #include <string.h>  
6. #include <malloc.h>  
7.   
8. /************************************************* 
9. *           struct definition 
10. **************************************************/  
11.   
12. typedef struct _MNG_NODE  
13. {  
14.     struct _MNG_NODE* next;  
15.     unsigned int size;  
16. }MNG_NODE;  
17.   
18.   
19. /************************************************* 
20. *           global variable declaration 
21. **************************************************/  
22.   
23. #define MEM_BUFFER_LENGTH   (0x1 << 24)  
24.   
25. static void* pGlbData;  
26. static MNG_NODE* pFreeList;  
27. static MNG_NODE* pAllocList;  
28.   
29. /************************************************* 
30. * function: add node into headlist 
31. **************************************************/  
32.   
33. static void add_node_into_list_head(MNG_NODE* pNode, MNG_NODE** ppList)  
34. {  
35.     pNode->next = *ppList;  
36.     *ppList = pNode;     
37. }  
38.   
39.   
40. /************************************************* 
41. * function: find best fit node 
42. **************************************************/  
43.   
44. static MNG_NODE* find_best_fit_node(unsigned int size)  
45. {  
46.     MNG_NODE* pCur = pFreeList;  
47.     MNG_NODE* pPre = pCur;  
48.   
49.     while(pCur && pCur->size < (size + sizeof(MNG_NODE)))  
50.     {   
51.         pPre = pCur;  
52.         pCur = pCur->next;  
53.     }     
54.   
55.     if(NULL == pCur)  
56.         return NULL;  
57.   
58.     if(pFreeList == pCur)  
59.         pFreeList = pFreeList->next;  
60.     else  
61.         pPre->next = pCur->next;  
62.   
63.     return pCur;  
64. }  
65.   
66.   
67. /************************************************* 
68. * function: implement memory allocation 
69. **************************************************/  
70.   
71. static void* _mem_malloc(unsigned int size)  
72. {  
73.     MNG_NODE* pOld;  
74.     MNG_NODE* pNew;  
75.   
76.     pOld = find_best_fit_node(size);  
77.     if(NULL == pOld)  
78.         return NULL;  
79.   
80.     pNew = (MNG_NODE*)((char*)pOld + sizeof(MNG_NODE) + pOld->size - (sizeof(MNG_NODE) + size));  
81.     pNew->size = size;  
82.     pOld->size -= sizeof(MNG_NODE) + size;  
83.   
84.     add_node_into_list_head(pOld, &pFreeList);  
85.     add_node_into_list_head(pNew, &pAllocList);  
86.   
87.     return (void*)((char*)pNew + sizeof(MNG_NODE));  
88. }  
89.   
90.   
91. /************************************************* 
92. * function: memory allocation 
93. **************************************************/  
94.   
95. void* mem_malloc(unsigned int size)  
96. {  
97.     if(0 == size)  
98.         return NULL;  
99.   
100.     if(size > (MEM_BUFFER_LENGTH - sizeof(MNG_NODE)))  
101.         return NULL;  
102.   
103.     return _mem_malloc(size);  
104. }  
105.   
106.   
107. /************************************************* 
108. * function: find previous node  
109. **************************************************/  
110.   
111. static MNG_NODE* find_previous_node(MNG_NODE* pNode)  
112. {  
113.     MNG_NODE* pFind = pAllocList;  
114.     MNG_NODE* pPre = NULL;  
115.       
116.     while(pFind && pFind != pNode)  
117.     {  
118.         pPre = pFind;  
119.         pFind = pFind->next;  
120.     }  
121.   
122.     if(NULL == pFind)  
123.         return NULL;  
124.   
125.     return pPre;  
126. }  
127.   
128.   
129. /************************************************* 
130. * function: implement memory free 
131. **************************************************/  
132.   
133. static void _mem_free(MNG_NODE* pNode)  
134. {  
135.     MNG_NODE* pPreNode;  
136.   
137.     if(pNode == pAllocList)  
138.     {  
139.         pAllocList = pAllocList->next;  
140.         add_node_into_list_head(pNode, &pFreeList);  
141.         return;  
142.     }      
143.   
144.     pPreNode = find_previous_node(pNode);  
145.     if(NULL == pPreNode)  
146.         return;  
147.   
148.     pPreNode->next = pNode->next;  
149.     add_node_into_list_head(pNode, &pFreeList);  
150.     return;  
151. }  
152.   
153.   
154. /************************************************* 
155. * function: free memory function 
156. **************************************************/  
157.   
158. void mem_free(void* pData)  
159. {  
160.     if(NULL == pData)  
161.         return;  
162.   
163.     if(pData < pGlbData || pData >= (void*)((char*)pGlbData + MEM_BUFFER_LENGTH))  
164.         return;  
165.   
166.     _mem_free(pData - sizeof(MNG_NODE));  
167. }  
168.   
169.   
170. /************************************************* 
171. * function: get memory buffer 
172. **************************************************/  
173.   
174. void mem_init()  
175. {  
176.     pGlbData = (void*)malloc(MEM_BUFFER_LENGTH);  
177.     if(NULL == pGlbData)  
178.         return;  
179.   
180.     memset(pGlbData, 0, MEM_BUFFER_LENGTH);  
181.     pFreeList = (MNG_NODE*)pGlbData;  
182.     pFreeList->size = MEM_BUFFER_LENGTH - sizeof(MNG_NODE);  
183.     pAllocList = NULL;  
184. }  
185.   
186.   
187. /************************************************* 
188. * function: free memory buffer 
189. **************************************************/  
190.   
191. void mem_exit()  
192. {  
193.     if(NULL != pGlbData)  
194.         free(pGlbData);     
195.   
196.     pFreeList = NULL;  
197.     pAllocList = NULL;  
198. }  
199.   
200.   
201. /************************************************* 
202. * function: file starts here 
203. **************************************************/  
204.   
205. int main(int argc, char* argv[])  
206. {  
207.     mem_init();  
208.     mem_exit();  
209.     return 1;  
210. } 
     

嵌入式操作系统内核原理和开发（最快、最优、最差内存分配算法）

前面我们说到了基于 链表的内存分配算法。但是之前我们也说过，其实内存分配一般有三个原则，最快、最优和最差。最快比较好理解，就是寻找到合适的节点就立即分配内存，我们在前面一篇博客采用的就是这个方法。最优呢，就是寻找可以满足当前内存分配的最小节点，这样不会有很大的浪费，但是有可能会产生碎片节点。最后一种就是最差分配算法，说是最差效果未必最差。因为在大的内存分配的时候至少不会很快产生内存碎片，对整个系统的稳定来说有可能是好事。所以这三种方法很难说哪一种好，哪一种不好，需要结合具体的应用场景客观进行分析。不过话说回来，内存碎片是无论如何都避免不了的。

 

    首先，为了灵活对这三种分配算法进行配置，我们定义了宏开关，需要哪个就把那个开关放开。暂时默认打开的算法的是最快分配算法。

[cpp] view plaincopy

1. #define MAX_SPEED_MALLOC   1  
2. #define MIN_SIZE_MALLOC    0  
3. #define MAX_SIZE_MALLOC    0  

    因为之前已经讨论过最快分配算法，所以这里着重讨论的最优分配算法和最差分配算法。又由于两者的差别极小，所以单独分析其中一种算法也行。就拿最优分配算法来说，为了寻找到最小的节点，我们需要对整个链表进行遍历，这个还是比较消耗时间的。

[cpp] view plaincopy

1. while(pCur)  
2. {   
3.     if(pCur->size > (size + sizeof(MNG_NODE)))  
4.     {  
5.         if(NULL == pFind || pFind->size > pCur->size)  
6.         {  
7.             pFind = pCur;  
8.         }  
9.     }  
10.   
11.     pPre = pCur;  
12.     pCur = pCur->next;  
13. }     

    寻找到pFind这个我们需要的节点之后，还需要从pFreeList中删除该节点。所以，我们需要进一步的判断和分析，

[cpp] view plaincopy

1. if(NULL == pFind)  
2.     return NULL;  
3.   
4. pPre = find_previous_node_in_list(pFind, pFreeList);  
5. if(NULL == pPre)  
6.     pFreeList = pFreeList->next;  
7. else  
8.     pPre->next = pFind->next;  
9.   
10. return pFind;  

      首先判断pFind前面有没有节点，如果没有表示pFreeList就是pFind，那么pFreeList需要自行向后退缩；当然如果当前的pFind节点是有前节点的，那么只需要把前节点的next指针重新更改一下即可。当然，这里还对原来的查找节点函数作了一下修改，使之更合理更通用。

[cpp] view plaincopy

1. /************************************************* 
2. * function: find previous node  
3. **************************************************/  
4.   
5. MNG_NODE* find_previous_node_in_list(MNG_NODE* pNode, MNG_NODE* pList)  
6. {  
7.     MNG_NODE* pFind = pList;  
8.     MNG_NODE* pPre = NULL;  
9.       
10.     while(pFind && pFind != pNode)  
11.     {  
12.         pPre = pFind;  
13.         pFind = pFind->next;  
14.     }  
15.   
16.     if(NULL == pFind)  
17.         return NULL;  
18.   
19.     return pPre;  
20. }  

    上面也只是说了个大概，具体的内容可以参见下面的源代码。既可以在VC上编译，也可以在GCC上面编译，都没有问题。当然，如果本地os没有编译器，可以选择网上在线编译，也是个不错的选择。

[cpp] view plaincopy

1. /************************************************* 
2. *      malloc & free in link node algorithm 
3. **************************************************/  
4.   
5. #include <string.h>  
6. #include <malloc.h>  
7.   
8. /************************************************* 
9. *           struct definition 
10. **************************************************/  
11.   
12. typedef struct _MNG_NODE  
13. {  
14.     struct _MNG_NODE* next;  
15.     unsigned int size;  
16. }MNG_NODE;  
17.   
18.   
19. /************************************************* 
20. *          macro declaration 
21. **************************************************/  
22.   
23. #define MAX_SPEED_MALLOC   1  
24. #define MIN_SIZE_MALLOC    0  
25. #define MAX_SIZE_MALLOC    0  
26.   
27. #define MEM_BUFFER_LENGTH   (0x1 << 24)  
28.   
29.   
30. /************************************************* 
31. *           global variable declaration 
32. **************************************************/  
33.   
34. static void* pGlbData;  
35. static MNG_NODE* pFreeList;  
36. static MNG_NODE* pAllocList;  
37.   
38.   
39. /************************************************* 
40. *           function declaration 
41. **************************************************/  
42.   
43. MNG_NODE* find_previous_node_in_list(MNG_NODE* pNode, MNG_NODE* pList);  
44.   
45.   
46. /************************************************* 
47. * function: add node into headlist 
48. **************************************************/  
49.   
50. static void add_node_into_list_head(MNG_NODE* pNode, MNG_NODE** ppList)  
51. {  
52.     pNode->next = *ppList;  
53.     *ppList = pNode;     
54. }  
55.   
56.   
57. #if MAX_SPEED_MALLOC  
58. /************************************************* 
59. * function: find best fit node in max_speed 
60. **************************************************/  
61.   
62. static MNG_NODE* find_best_fit_node(unsigned int size)  
63. {  
64.     MNG_NODE* pFind = pFreeList;  
65.     MNG_NODE* pPre = pFind;  
66.   
67.     while(pFind && pFind->size < (size + sizeof(MNG_NODE)))  
68.     {   
69.         pPre = pFind;  
70.         pFind = pFind->next;  
71.     }     
72.   
73.     if(NULL == pFind)  
74.         return NULL;  
75.   
76.     if(pFreeList == pFind)  
77.         pFreeList = pFreeList->next;  
78.     else  
79.         pPre->next = pFind->next;  
80.   
81.     return pFind;  
82. }  
83. #endif  
84.   
85.   
86. #if MIN_SIZE_MALLOC  
87. /************************************************* 
88. * function: find best fit node in min size 
89. **************************************************/  
90.   
91. MNG_NODE* find_best_fit_node(unsigned int size)  
92. {  
93.     MNG_NODE* pCur = pFreeList;  
94.     MNG_NODE* pPre = pCur;  
95.     MNG_NODE* pFind = NULL;  
96.   
97.     while(pCur)  
98.     {   
99.         if(pCur->size > (size + sizeof(MNG_NODE)))  
100.         {  
101.             if(NULL == pFind || pFind->size > pCur->size)  
102.             {  
103.                 pFind = pCur;  
104.             }  
105.         }  
106.   
107.         pPre = pCur;  
108.         pCur = pCur->next;  
109.     }     
110.   
111.     if(NULL == pFind)  
112.         return NULL;  
113.   
114.     pPre = find_previous_node_in_list(pFind, pFreeList);  
115.     if(NULL == pPre)  
116.         pFreeList = pFreeList->next;  
117.     else  
118.         pPre->next = pFind->next;  
119.   
120.     return pFind;  
121. }  
122. #endif  
123.   
124.   
125. #if MAX_SIZE_MALLOC  
126. /************************************************* 
127. * function: find best fit node in max size 
128. **************************************************/  
129.   
130. MNG_NODE* find_best_fit_node(unsigned int size)  
131. {  
132.     MNG_NODE* pCur = pFreeList;  
133.     MNG_NODE* pPre = pCur;  
134.     MNG_NODE* pFind = NULL;  
135.   
136.     while(pCur)  
137.     {   
138.         if(pCur->size > (size + sizeof(MNG_NODE)))  
139.         {  
140.             if(NULL == pFind || pFind->size < pCur->size)  
141.             {  
142.                 pFind = pCur;  
143.             }  
144.         }  
145.   
146.         pPre = pCur;  
147.         pCur = pCur->next;  
148.     }     
149.   
150.     if(NULL == pFind)  
151.         return NULL;  
152.   
153.     pPre = find_previous_node_in_list(pFind, pFreeList);  
154.     if(NULL == pPre)  
155.         pFreeList = pFreeList->next;  
156.     else  
157.         pPre->next = pFind->next;  
158.   
159.     return pFind;  
160. }  
161. #endif  
162.   
163.   
164. /************************************************* 
165. * function: implement memory allocation 
166. **************************************************/  
167.   
168. static void* _mem_malloc(unsigned int size)  
169. {  
170.     MNG_NODE* pOld;  
171.     MNG_NODE* pNew;  
172.   
173.     pOld = find_best_fit_node(size);  
174.     if(NULL == pOld)  
175.         return NULL;  
176.   
177.     pNew = (MNG_NODE*)((char*)pOld + sizeof(MNG_NODE) + pOld->size - (sizeof(MNG_NODE) + size));  
178.     pNew->size = size;  
179.     pOld->size -= sizeof(MNG_NODE) + size;  
180.   
181.     add_node_into_list_head(pOld, &pFreeList);  
182.     add_node_into_list_head(pNew, &pAllocList);  
183.   
184.     return (void*)((char*)pNew + sizeof(MNG_NODE));  
185. }  
186.   
187.   
188. /************************************************* 
189. * function: memory allocation 
190. **************************************************/  
191.   
192. void* mem_malloc(unsigned int size)  
193. {  
194.     if(0 == size)  
195.         return NULL;  
196.   
197.     if(size > (MEM_BUFFER_LENGTH - sizeof(MNG_NODE)))  
198.         return NULL;  
199.   
200.     return _mem_malloc(size);  
201. }  
202.   
203.   
204. /************************************************* 
205. * function: find previous node  
206. **************************************************/  
207.   
208. MNG_NODE* find_previous_node_in_list(MNG_NODE* pNode, MNG_NODE* pList)  
209. {  
210.     MNG_NODE* pFind = pList;  
211.     MNG_NODE* pPre = NULL;  
212.       
213.     while(pFind && pFind != pNode)  
214.     {  
215.         pPre = pFind;  
216.         pFind = pFind->next;  
217.     }  
218.   
219.     if(NULL == pFind)  
220.         return NULL;  
221.   
222.     return pPre;  
223. }  
224.   
225.   
226. /************************************************* 
227. * function: implement memory free 
228. **************************************************/  
229.   
230. static void _mem_free(MNG_NODE* pNode)  
231. {  
232.     MNG_NODE* pPreNode;  
233.   
234.     if(pNode == pAllocList)  
235.     {  
236.         pAllocList = pAllocList->next;  
237.         add_node_into_list_head(pNode, &pFreeList);  
238.         return;  
239.     }      
240.   
241.     pPreNode = find_previous_node_in_list(pNode, pAllocList);  
242.     if(NULL == pPreNode)  
243.         return;  
244.   
245.     pPreNode->next = pNode->next;  
246.     add_node_into_list_head(pNode, &pFreeList);  
247.     return;  
248. }  
249.   
250.   
251. /************************************************* 
252. * function: free memory function 
253. **************************************************/  
254.   
255. void mem_free(void* pData)  
256. {  
257.     if(NULL == pData)  
258.         return;  
259.   
260.     if(pData < pGlbData || pData >= (void*)((char*)pGlbData + MEM_BUFFER_LENGTH))  
261.         return;  
262.   
263.     _mem_free((MNG_NODE*)((char*)pData - sizeof(MNG_NODE)));  
264. }  
265.   
266.   
267. /************************************************* 
268. * function: get memory buffer 
269. **************************************************/  
270.   
271. void mem_init()  
272. {  
273.     pGlbData = (void*)malloc(MEM_BUFFER_LENGTH);  
274.     if(NULL == pGlbData)  
275.         return;  
276.   
277.     memset(pGlbData, 0, MEM_BUFFER_LENGTH);  
278.     pFreeList = (MNG_NODE*)pGlbData;  
279.     pFreeList->size = MEM_BUFFER_LENGTH - sizeof(MNG_NODE);  
280.     pAllocList = NULL;  
281. }  
282.   
283.   
284. /************************************************* 
285. * function: free memory buffer 
286. **************************************************/  
287.   
288. void mem_exit()  
289. {  
290.     if(NULL != pGlbData)  
291.         free(pGlbData);     
292.   
293.     pFreeList = NULL;  
294.     pAllocList = NULL;  
295. }  
296.   
297.   
298. /************************************************* 
299. * function: file starts here 
300. **************************************************/  
301.   
302. int main(int argc, char* argv[])  
303. {  
304.     mem_init();  
305.     mem_exit();  
306.     return 1;  
307. } 
     

嵌入式操作系统内核原理和开发（信号量）

之前因为工作的原因，操作系统这块一直没有继续写下去。一方面是自己没有这方面的经历，另外一方面就是操作系统比较复杂和琐碎，调试起来比较麻烦。目前在实际项目中，使用的实时操作系统很多，很多国内的朋友也写过操作系统，有些项目现在还在维护和修改中，这是十分难得的。就我知道和熟悉的就有三个系统，比如

 

     （1）RT-THREAD

     （2）RAW-OS

     （3）ClearRTOS

 

    这里有比较介绍一下，这三个系统是国内的三位朋友开发的。其中rt-thread时间比较久一点，模块也比较全，bsp、cpu、fs、lwip、gui等辅助的代码也比较多，有兴趣的朋友可以到网站上面下载代码看一看。raw-os是我今年才发现的一个实时系统，从网站的注册时间和软件版本号上来看，系统开发的时间不是很长，不过整个系统代码的结构非常清晰，是我重点推荐阅读的代码。如果朋友们自己download下来，好好看一下其中的代码，肯定会有不少的收获。最后一个代码是作者李云在编写《专业嵌入式软件开发》这本书的时候，为了说明os的基本原理而开发的软件，前后设计了线程、互斥、内存、定时器、驱动框架等内容，值得一读。

 

    当然有了这么多优秀的代码，我觉得现在自己的工作就不是重新造一个车轮了，而是和大家分享这些优秀的代码是如何设计的。理解代码本身不是目的，关键是理解代码背后的基本思路。就我个人看过来，rt-thread和raw-os都可以用来学习，不过raw-os更好一些，主要是因为作者将raw-os移植到的vc上面，学起来也十分方便，要是个人在使用过程中有什么疑问，可以通过邮件和作者及时交流。不过由于raw-os的版本在一直在update之中，所以部分代码在前后稍微有点差别，不过这些都不是重点，暂时不了解的内容可以通过后面的了解和学习逐步掌握，不会成为太大的障碍。

 

    就像今天的题目一样，我们重点介绍一下信号量的设计原理。首先看一下信号量的数据结构是怎么样的，

[cpp] view plaincopy

1. typedef struct RAW_SEMAPHORE  
2. {   
3.     RAW_COMMON_BLOCK_OBJECT       common_block_obj;  
4.     RAW_U32                       count;  
5.       
6. } RAW_SEMAPHORE;  

    这些代码都是从raw-os上面摘抄下来的，这个版本是0.94版本，和最新的0.96c版本有点差别。首先分析一下信号量的基本结构，其实非常简单，就两个变量，其中comm_block_obj是一个通用类型，记录了当前结构的名称、类型和阻塞队列，而count就是计数，判断是否还有释放的资源。

 

    说到了信号量的操作，无非就是信号量的创建、获取、释放、删除操作，当然这里作者考虑的比较详细，在信号量释放的时候还分成了 WAKE_ONE_SEM和WAKE_ALL_SEM两种类型。意思很简单，就是当信号量来临的时候是唤醒一个等待线程呢，还是唤醒所有的等待线程呢，就是这么回事。下面，我们就按照顺序介绍这几个函数，首先是创建函数，

[cpp] view plaincopy

1. RAW_U16 raw_semaphore_create(RAW_SEMAPHORE *semaphore_ptr, RAW_U8 *name_ptr, RAW_U32 initial_count)  
2. {  
3.     #if (RAW_SEMA_FUNCTION_CHECK > 0)  
4.       
5.     if (semaphore_ptr == 0) {  
6.           
7.         return RAW_NULL_OBJECT;  
8.     }  
9.   
10.     if (initial_count == 0xffffffff) {  
11.   
12.         return RAW_SEMOPHORE_OVERFLOW;  
13.   
14.     }  
15.       
16.     #endif  
17.   
18.     /*Init the list*/  
19.     list_init(&semaphore_ptr->common_block_obj.block_list);  
20.       
21.     /*Init resource*/  
22.     semaphore_ptr->count     = initial_count;                                   
23.       
24.     semaphore_ptr->common_block_obj.name = name_ptr;    
25.       
26.     semaphore_ptr->common_block_obj.block_way = 0;  
27.       
28.     return RAW_SUCCESS;  
29.   
30. }  

    看着初始化函数，我们发现信号量的初始化其实也非常简单，基本工作主要有：

    （1）判断参数合法性；

    （2）初始化阻塞队列、名称等；

    （3）初始化信号量的计数。

 

    说完了这些，我们看看信号量的获取是怎么完成的，代码可能长度稍微长一些，不过也不用太紧张，

[cpp] view plaincopy

1. RAW_U16 raw_semaphore_get(RAW_SEMAPHORE *semaphore_ptr,  RAW_U32 wait_option)  
2. {  
3.   
4.     RAW_U16 error_status;  
5.   
6.     RAW_SR_ALLOC();  
7.   
8.     #if (RAW_SEMA_FUNCTION_CHECK > 0)  
9.   
10.     if (semaphore_ptr == 0) {  
11.           
12.         return RAW_NULL_OBJECT;  
13.     }  
14.       
15.     if (raw_int_nesting) {  
16.   
17.         return RAW_NOT_CALLED_BY_ISR;  
18.     }  
19.   
20.     #endif  
21.       
22.       
23.     RAW_CRITICAL_ENTER();  
24.     if (semaphore_ptr->count) {                        
25.         semaphore_ptr->count--;                                         
26.   
27.         RAW_CRITICAL_EXIT();  
28.           
29.         return RAW_SUCCESS;  
30.     }  
31.       
32.     /*Cann't get semphore, and return immediately if wait_option is  RAW_NO_WAIT*/  
33.     if (wait_option == RAW_NO_WAIT) {   
34.   
35.         RAW_CRITICAL_EXIT();  
36.         return RAW_NO_PEND_WAIT;  
37.     }        
38.       
39.     if (raw_sched_lock) {     
40.         RAW_CRITICAL_EXIT();      
41.         return RAW_SCHED_DISABLE;  
42.     }  
43.   
44.     raw_pend_object(&semaphore_ptr->common_block_obj, raw_task_active, wait_option);  
45.     RAW_CRITICAL_EXIT();  
46.   
47.     raw_sched();   
48.       
49.     error_status = block_state_post_process(raw_task_active, 0);  
50.     return error_status;  
51.   
52. }  

    信号量的获取情况比较复杂一些，这在长度上也体现出来了。不过没关系，我们一步一步看函数做了什么，

    （1）判断参数合法性；

    （2）判断当前函数是否处于中断处理的流程中，如果是选择返回；

    （3）判断当前count是否为0，如果不为 0，则减1返回；

    （4）如果当前count是0，且线程不愿意等待，那么选择返回；

    （5）如果当前禁止调度，那么依然选择返回；

     （6）当前线程将自己挂起，从ready队列中删除，把自己pend到信号量的阻塞队列中；

     （7）阻塞的线程再次获得了运行的机会，我们从task数据结构获得返回结果，此时也不一定是因为获得了资源的缘故哦。

 

    上面的get函数看上去比较复杂，但是所有的同步函数基本上都是这样设计的，看多了反而有一种八股文的感觉。刚开始看的同学可能觉得不是很习惯。不要紧，每天多看两眼，时间长了就ok了。好了，接着我们继续去看看信号量的释放函数是怎么处理的，大家做好心理准备哦，

[cpp] view plaincopy

1. static RAW_U16 internal_semaphore_put(RAW_SEMAPHORE *semaphore_ptr, RAW_U8 opt_wake_all)  
2. {  
3.     LIST *block_list_head;  
4.       
5.     RAW_SR_ALLOC();  
6.   
7.     #if (RAW_SEMA_FUNCTION_CHECK > 0)  
8.       
9.     if (semaphore_ptr == 0) {  
10.           
11.         return RAW_NULL_OBJECT;  
12.     }  
13.       
14.     #endif  
15.   
16.     block_list_head = &semaphore_ptr->common_block_obj.block_list;  
17.       
18.     RAW_CRITICAL_ENTER();  
19.     /*if no block task on this list just return*/  
20.     if (is_list_empty(block_list_head)) {          
21.           
22.         if (semaphore_ptr->count == 0xffffffff) {  
23.   
24.             RAW_CRITICAL_EXIT();  
25.             return RAW_SEMOPHORE_OVERFLOW;  
26.   
27.         }  
28.         /*increase resource*/  
29.         semaphore_ptr->count++;                                        
30.           
31.         RAW_CRITICAL_EXIT();  
32.         return RAW_SUCCESS;  
33.     }  
34.   
35.     /*wake all the task blocked on this semphore*/  
36.     if (opt_wake_all) {  
37.   
38.         while (!is_list_empty(block_list_head)) {  
39.             raw_wake_object(list_entry(block_list_head->next, RAW_TASK_OBJ, task_list));  
40.         }  
41.   
42.     }  
43.   
44.     else {  
45.           
46.         /*Wake up the highest priority task block on the semaphore*/  
47.         raw_wake_object(list_entry(block_list_head->next, RAW_TASK_OBJ, task_list));  
48.     }  
49.       
50.     RAW_CRITICAL_EXIT();  
51.   
52.     raw_sched();      
53.   
54.     return RAW_SUCCESS;  
55. }  

    看上去，信号量的释放函数也比较长，不过只要有耐心，都是可以看明白的，我们就来具体分析一下，

    （1）判断参数的合法性；

    （2）判断当前是否有等待队列，如果没有，则count自增，函数返回，当然如果count达到了0xffffffff也要返回，不过概率极低；

    （3） 当前存在等待队列，根据opt_wake_all的要求是唤醒一个线程还是唤醒所有的线程；

    （4）调用系统调度函数，让高优先级任务及时得到运行的机会；

    （5）当前线程再次得到运行的机会，函数返回。

 

    有了上面的讲解，我们发现os的代码其实也没有那么恐怖。所以，请大家一鼓作气，看看信号量是怎么删除的吧，

[cpp] view plaincopy

1. RAW_U16 raw_semaphore_delete(RAW_SEMAPHORE *semaphore_ptr)  
2. {  
3.     LIST *block_list_head;  
4.       
5.     RAW_SR_ALLOC();  
6.   
7.     #if (RAW_SEMA_FUNCTION_CHECK > 0)  
8.       
9.     if (semaphore_ptr == 0) {  
10.           
11.         return RAW_NULL_OBJECT;  
12.     }  
13.       
14.     #endif  
15.   
16.     block_list_head = &semaphore_ptr->common_block_obj.block_list;  
17.       
18.     RAW_CRITICAL_ENTER();  
19.   
20.     /*All task blocked on this queue is waken up*/  
21.     while (!is_list_empty(block_list_head)) {  
22.         delete_pend_obj(list_entry(block_list_head->next, RAW_TASK_OBJ, task_list));   
23.     }                               
24.   
25.     RAW_CRITICAL_EXIT();  
26.     raw_sched();   
27.     return RAW_SUCCESS;  
28. }  

    信号量删除的工作其实很少，也很简单，同样我们也来梳理一下，

    （1）判断参数合法性；

    （2）唤醒阻塞队列中的每一个线程；

    （3）调用系统调度函数，因为高优先级的任务很有可能刚刚从阻塞队列中释放出来；

    （4）当前线程再次运行，函数返回。

 

    通过上面几个函数的讲解，我们发现关于os互斥部分的代码其实也不复杂。只要对系统本身和中断有一些了解，其实代码都是可以看懂的。当然，上面的代码我们还是讲的比较粗糙，所以有些细节还是要补充一下，

 

    （1）全局变量操作的函数必须在关中断的情况下进行操作；

    （2）实时系统的抢占是每时每刻都在进行的，比如中断返回时、信号量释放时、调用延时函数、调用调度函数的时候，所以大家心中要有抢占的概念；

    （3）互斥函数中大量使用了链表的结构，建议大家好好掌握链表的相关算法；

    （4）关于os的代码一定要多看、多思考、多练习才会有进步和提高，纸上得来终觉浅、绝知此事要躬行。

嵌入式操作系统内核原理和开发（互斥量）

今天下午打开邮箱，打开rawos作者给我发的邮件，甚是惊喜。感谢他对我的支持，因为自己阅读过很多os的代码，包括ucos、rtthread、vxWorks、linux等等，所以阅读rawos对于我来说不算特别辛苦的事情。除了某些细节之外，我对整个系统的设计还算得上是比较了解的，所以也打算把这个代码介绍给大家。能在现实的硬件中使用当然最好，如果没有这样的机会，也可以提高个人的认识水平，或者介绍给内部的团队成员，大家一起分析和学习也不失为一个很好的方法。
 
     闲话不多说，话题还是转到我们今天的主题上面，即互斥量。学过操作系统课程的朋友对这个词汇肯定不会很陌生。和信号量相比，互斥保护的资源一般是唯一的。也就是说，资源就一份，你占有了，我就没有办法占有；当然如果你释放了，此时我就有机会占有了。
 
     一切的一切看上去没有什么问题。但是，我们都知道在实时嵌入式系统当中，线程之间的调度是严格按照优先级来进行调度。比方说，优先级为10的任务必须比优先级为11的任务优先得到调度。那么，有同学会问了，那优先级为11的任务什么时候才能得到调度呢，其实这个要求还是蛮苛刻的。要想优先级为11的任务得到调度，此时必须没有优先级10的任务、或者任务pend到资源上了、或者自身delay、或者被人suspend了。否则，优先级为10的任务会这么一直运行下去。那，这和我们的互斥量有什么关系呢？请听我一一讲来。
 
     我们假设现在有两个任务都准备运行，分别人任务A、B，优先级依次是10、11。某一段时间后，优先级为10和优先级为11的任务都在尝试获取某个资源。本来按照优先级的先后顺序，优先级为10的任务应该率先获取资源，这都没问题。但是，假设在尝试获取资源前，优先级为10的任务开了个小差，sleep一会，那么这个时候优先级为11的任务就可以开始运行了。等到优先级为10的任务苏醒过来，想重新获取资源的时候，惊讶地发现资源早就被别人给占了。因为资源目前只有一份，所以它只好把自己pend到等待队列里面，慢慢等待好心人能快点把资源释放出来。一切的一切看上去没有什么问题，但是这却和实时系统设计的初衷是相违背的。前面我们规定高优先级的任务必须优先得到运行的机会，而目前这种情况和我们的设计原则是背道而驰的。
 
     当然这个问题很早就被大家发现了，大家也在尝试不同的方法来解决。目前使用的比较多的就是两种方法，一种是给互斥量设定一个优先级，另外一种就是对优先级进行继承处理。看上去是两种方法，其实目的只有一个，就是让那些占有互斥量的thread提高优先级，赶快运行结束，把资源还给后面真正需要的人。看上去一切解决得都很完美，但是大家有没有考虑过这样一个问题，如果线程连续占有多个互斥量，优先级又该怎么处理？如果pend的任务被修改了优先级该怎么处理？如果这两种方法一起被使用，那又该怎么处理？我想，这就是作者在后期对互斥量代码进行重构的原因吧。当然了，上面讨论的内容已经是比较深的了，大家可以看看早期互斥量是怎么设计的，慢慢来，这样才会对作者的设计意图更加了解一些。
 
     老规矩，我们首先看看互斥量是怎么设计的，
[cpp] view plaincopy

1. typedef struct RAW_MUTEX  
2.   {   
3.     RAW_COMMON_BLOCK_OBJECT       common_block_obj;  
4.     RAW_U8                     count;  
5.       
6.     /*ponit to occupy task*/  
7.     RAW_TASK_OBJ   *occupy;  
8.     /*occupy task original priority*/  
9.     RAW_U8 occupy_original_priority;  
10.   } RAW_MUTEX;  

     看上去互斥量的东西多一点，其实也还可以，只要大家明白了互斥量处理逻辑再回头来看看这些东西的时候，认识就会更加深刻。我们看看，数据结构里面都有什么，
     （1）通用互斥结构，这在前面信号量的时候已经介绍过一遍；
     （2）计数，判断资源是否还在；
     （3）当前所属的任务；
     （4）该任务原来的优先级。
 
     说好了基本结构，我们看看互斥量的构造、申请、释放、删除函数是怎么设计的，首先当然还是初始化函数，
[cpp] view plaincopy

1. RAW_U16 raw_mutex_create(RAW_MUTEX *mutex_ptr, RAW_U8 *name_ptr)  
2.   {  
3.     #if (RAW_MUTEX_FUNCTION_CHECK > 0)  
4.     
5.     if (mutex_ptr == 0)  
6.         return RAW_NULL_OBJECT;  
7.       
8.     #endif  
9.     
10.     /*Init the list*/  
11.     list_init(&mutex_ptr->common_block_obj.block_list);  
12.     mutex_ptr->common_block_obj.block_way = 0;  
13.     mutex_ptr->common_block_obj.name  =  name_ptr;  
14.     
15.     /*No one occupy mutex yet*/  
16.     mutex_ptr->occupy     = 0;  
17.     
18.     /*resource is available at init state*/   
19.     mutex_ptr->count   = 1;          
20.     mutex_ptr->occupy_original_priority =  0;  
21.       
22.     
23.     return RAW_SUCCESS;  
24.   }  
25.    

    初始化的函数还是比较简单的，主要做了下面的流程，
     （1）初始化互斥结构的公共属性，比如名字、阻塞方式等等；
     （2）初始化当前资源数量；
     （3）初始化占有资源的线程指针，还有就是线程的优先级。
 
     创建了互斥量之后，我们就要看看互斥量是怎么申请的？代码有点长，同学们可以心理调整一下了，
[cpp] view plaincopy

1. RAW_U16 raw_mutex_get(RAW_MUTEX *mutex_ptr, RAW_U32 wait_option)  
2.   {  
3.     RAW_U16 error_status;  
4.     RAW_SR_ALLOC();  
5.     
6.     #if (RAW_MUTEX_FUNCTION_CHECK > 0)  
7.     
8.     
9.     if (mutex_ptr == 0) {  
10.         return RAW_NULL_OBJECT;  
11.     }  
12.     
13.     if (raw_int_nesting) {  
14.           
15.         return RAW_NOT_CALLED_BY_ISR;  
16.           
17.     }  
18.       
19.     #endif  
20.       
21.     RAW_CRITICAL_ENTER();  
22.       
23.      /* mutex is available */  
24.     if (mutex_ptr->count) {     
25.         mutex_ptr->occupy       =  raw_task_active;                                   
26.         mutex_ptr->occupy_original_priority =  raw_task_active->priority;  
27.         mutex_ptr->count   = 0;  
28.     
29.         RAW_CRITICAL_EXIT();  
30.     
31.         return RAW_SUCCESS;  
32.     }  
33.     
34.     
35.     /*if the same task get the same mutex again, it causes deadlock*/   
36.     if (raw_task_active == mutex_ptr->occupy) {       
37.     
38.         #if (CONFIG_RAW_ASSERT > 0)  
39.         RAW_ASSERT(0);  
40.         #endif  
41.           
42.             RAW_CRITICAL_EXIT();     
43.         return RAW_MUTEX_DEADLOCK;  
44.      }  
45.     
46.     /*Cann't get mutex, and return immediately if wait_option is  RAW_NO_WAIT*/  
47.     if (wait_option == RAW_NO_WAIT) {   
48.     
49.         RAW_CRITICAL_EXIT();  
50.     
51.         return RAW_NO_PEND_WAIT;  
52.     
53.     }  
54.     
55.     /*system is locked so task can not be blocked just return immediately*/  
56.     if (raw_sched_lock) {     
57.         RAW_CRITICAL_EXIT();      
58.         return RAW_SCHED_DISABLE;  
59.     }  
60.     
61.       /*if current task is a higher priority task and block on  the mutex 
62.       *priority inverse condition happened, priority inherit method is used here*/  
63.       
64.     if (raw_task_active->priority < mutex_ptr->occupy->priority) {    
65.         switch (mutex_ptr->occupy->task_state) {  
66.               
67.             case RAW_RDY:  
68.                 /*remove from the ready list*/  
69.                 remove_ready_list(&raw_ready_queue, mutex_ptr->occupy);  
70.                 /*raise the occupy task priority*/  
71.                 mutex_ptr->occupy->priority = raw_task_active->priority;     
72.                 /*readd to the ready list head*/  
73.                 add_ready_list_head(&raw_ready_queue, mutex_ptr->occupy);  
74.                 break;  
75.               
76.     
77.             case RAW_DLY:  
78.             case RAW_DLY_SUSPENDED:  
79.             case RAW_SUSPENDED:  
80.                 /*occupy task is not on any list, so just change the priority*/   
81.                 mutex_ptr->occupy->priority = raw_task_active->priority;     
82.                 break;  
83.     
84.             case RAW_PEND:                        /* Change the position of the task in the wait list       */  
85.             case RAW_PEND_TIMEOUT:  
86.             case RAW_PEND_SUSPENDED:  
87.             case RAW_PEND_TIMEOUT_SUSPENDED:      
88.                 /*occupy task is on the block list so change the priority on the block list*/  
89.                 mutex_ptr->occupy->priority = raw_task_active->priority;     
90.                 change_pend_list_priority(mutex_ptr->occupy);   
91.                 break;  
92.     
93.             default:  
94.                 RAW_CRITICAL_EXIT();      
95.                 return RAW_INVALID_STATE;  
96.         }  
97.           
98.     }  
99.     
100.     /*Any way block the current task*/  
101.     raw_pend_object(&mutex_ptr->common_block_obj, raw_task_active, wait_option);  
102.     
103.     RAW_CRITICAL_EXIT();      
104.     
105.     /*find the next highest priority task ready to run*/  
106.     raw_sched();                                               
107.     
108.     /*So the task is waked up, need know which reason cause wake up.*/  
109.     error_status = block_state_post_process(raw_task_active, 0);  
110.       
111.     return error_status;  
112.   }  
113.    

    这段代码其实开头都还好，关键是末尾要结束的时候有一段代码比较费解。我想，这就是我前面说过的优先级反转问题。为了解决这一问题，在rawos版本中采取了优先级继承的方法。我们还是详细看一下逻辑本身是怎么样的，
     （1）判断参数合法性；
     （2）判断资源是否可取，如果可取，则在记录当前线程和优先级后返回；
     （3）如果资源被自己重复申请，返回；
     （4）如果线程不愿等待，返回；
     （5）如果此时禁止调度，返回；
     （6）如果此时优先级大于互斥量占有者的优先级，分情况处理
             a）占有者处于ready的状态，那么修改它的优先级，重新加入调度队列；
             b）占有者处于sleep的状态，直接修改优先级即可；
             c）占有者也被pend到别的资源上面了，那么修改那个资源的pend列表，可能设计到调度顺序问题。
     （7）线程把自己pend到互斥量等待队列上面；
     （8）线程调用系统调度函数，切换到其他线程运行；
     （9）线程再次得到运行的机会，从task获取结果后返回。
 
     基本上上面的介绍算得上是很详细了，那么互斥量的释放基本上是一个逆操作的过程，朋友也可以思考一下应该怎么解决才好，
[cpp] view plaincopy

1. RAW_U16 raw_mutex_put(RAW_MUTEX *mutex_ptr)  
2.   {  
3.     
4.     LIST *block_list_head;  
5.       
6.     RAW_SR_ALLOC();  
7.     
8.     #if (RAW_MUTEX_FUNCTION_CHECK > 0)  
9.     
10.     if (mutex_ptr == 0) {  
11.         return RAW_NULL_OBJECT;  
12.     }  
13.       
14.     #endif  
15.     
16.     block_list_head = &mutex_ptr->common_block_obj.block_list;  
17.       
18.     RAW_CRITICAL_ENTER();  
19.     
20.     /*Must release the mutex by self*/  
21.     if (raw_task_active != mutex_ptr->occupy) {             
22.         RAW_CRITICAL_EXIT();  
23.         return RAW_MUTEX_NOT_RELEASE_BY_OCCYPY;  
24.     }  
25.     
26.     /*if no block task on this list just return*/  
27.     if (is_list_empty(block_list_head)) {          
28.         mutex_ptr->count   = 1;                                      
29.         RAW_CRITICAL_EXIT();  
30.         return RAW_SUCCESS;  
31.     }  
32.     
33.      /*if priority was changed, just change it back to original priority*/  
34.        
35.     if (raw_task_active->priority != mutex_ptr->occupy_original_priority) {  
36.           
37.         remove_ready_list(&raw_ready_queue, raw_task_active);  
38.         raw_task_active->priority = mutex_ptr->occupy_original_priority;     
39.         add_ready_list_end(&raw_ready_queue, raw_task_active);  
40.     
41.     }  
42.     
43.     /* there must have task blocked on this mutex object*/                                                                                                                
44.     mutex_ptr->occupy       =   list_entry(block_list_head->next, RAW_TASK_OBJ, task_list);   
45.     /*the first blocked task became the occupy task*/  
46.     mutex_ptr->occupy_original_priority = mutex_ptr->occupy->priority;  
47.     /*mutex resource is occupied*/  
48.     mutex_ptr->count   = 0;    
49.     
50.     /*Wake up the occupy task, which is the highst priority task on the list*/                                                                                                         
51.     raw_wake_object(mutex_ptr->occupy);  
52.       
53.     RAW_CRITICAL_EXIT();  
54.     
55.     
56.     raw_sched();                                        
57.     
58.     return RAW_SUCCESS;  
59.       
60.   }  
61.    

    和之前的信号量释放相比，互斥量的释放要复杂一切，关键就在于修改优先级的问题。我们来梳理一下，
     （1）判断参数合法性；
     （2）判断线程是否为互斥量的占有线程，不是则返回；
     （3）判断等待队列是否为空，为空的话则返回；
     （4）判断占有任务的优先级有没有发生变化，如果有则需要重新修改优先级，重新加入调度队列中；
     （5）选择下一个可以调度的线程；
     （6）函数返回。
 
     说了这么些，就剩下最后一个删除互斥量了，大家再接再厉，一起去学习。
[cpp] view plaincopy

1. RAW_U16  raw_mutex_delete(RAW_MUTEX *mutex_ptr)  
2.   {  
3.     LIST *block_list_head;  
4.       
5.     RAW_TASK_OBJ  *mutex_occupy;  
6.       
7.     RAW_SR_ALLOC();  
8.     
9.     #if (RAW_MUTEX_FUNCTION_CHECK > 0)  
10.     
11.     if (mutex_ptr == 0) {  
12.         return RAW_NULL_OBJECT;  
13.     }  
14.       
15.     #endif  
16.     
17.     block_list_head = &mutex_ptr->common_block_obj.block_list;  
18.       
19.     RAW_CRITICAL_ENTER();  
20.     
21.     mutex_occupy = mutex_ptr->occupy;       
22.     /*if mutex is occupied and occupy priority is not the original priority*/  
23.     if ((mutex_occupy) &&  (mutex_occupy->priority !=  mutex_ptr->occupy_original_priority)) {  
24.         switch (mutex_occupy->task_state) {                        
25.             case RAW_RDY:     
26.                 /*remove from the ready list*/  
27.                 remove_ready_list(&raw_ready_queue, mutex_ptr->occupy);  
28.                 /*raise the occupy task priority*/  
29.                 mutex_occupy->priority =  mutex_ptr->occupy_original_priority;  
30.                 /*readd to the ready list head*/  
31.                 add_ready_list_end(&raw_ready_queue, mutex_ptr->occupy);  
32.                 break;  
33.     
34.             case RAW_DLY:  
35.             case RAW_SUSPENDED:  
36.             case RAW_DLY_SUSPENDED:  
37.                 /*occupy task is not on any list, so just change the priority*/   
38.                 mutex_occupy->priority = mutex_ptr->occupy_original_priority;    
39.                 break;  
40.     
41.             case RAW_PEND:  
42.             case RAW_PEND_TIMEOUT:  
43.             case RAW_PEND_SUSPENDED:  
44.             case RAW_PEND_TIMEOUT_SUSPENDED:  
45.                 /*occupy task is on the block list so change the priority on the block list*/  
46.                 mutex_occupy->priority = mutex_ptr->occupy_original_priority;    
47.                 change_pend_list_priority(mutex_occupy);   
48.     
49.                 break;  
50.     
51.             default:  
52.                 RAW_CRITICAL_EXIT();  
53.                 return RAW_STATE_UNKNOWN;  
54.         }  
55.     }  
56.     
57.       
58.     /*All task blocked on this queue is waken up*/  
59.     while (!is_list_empty(block_list_head)) {  
60.         delete_pend_obj(list_entry(block_list_head->next, RAW_TASK_OBJ, task_list));   
61.     }                
62.     
63.     RAW_CRITICAL_EXIT();  
64.     
65.     raw_sched();   
66.       
67.     return RAW_SUCCESS;  
68.   }  
69.    

    互斥量的操作在实际情形下未必是存在的，所以作者在设计的时候添加了一个编译宏。不过删除所做的工作也不难理解，一个是处理好当前占有者的关系，一个是处理好等待队列的关系。我们来细看一下流程，
    （1）判断当前参数合法性；
    （2）判断占有者的情况，修改任务优先级，这里的情形和上面申请互斥量的处理方式是一样的，不再赘述；
    （3）唤醒所有的等待线程，如果线程已经suspend掉了，那么继续suspend；
    （4）调度到其他线程，防止有优先级高的任务已经被释放出来了；
    （5）函数返回，结束。
 

嵌入式操作系统内核原理和开发（事件）

在很多操作系统的书上，其实互斥和同步是放在一起进行介绍的。互斥，比较简单，就是对某一份资源或者几份资源进行抢占获取。而同步是什么意思呢，就是某一个线程等待另外一个线程的通知，只有收到了通知，它才会去干某些事情。

     通常情况下，如果是抢占的话，那么两个人使用的必须是同一个锁，而同步的话，则需要好几个锁，因为一般情况下大家等待的东西都是不一样的，所以好几个锁是不可避免的。那么，有没有什么办法，可以用一个锁实现几个事情的并发和同步呢？这就是我们今天所要说的事件。可以从一个例子说明一下。

     比方说，我们现在打算进行八宝饭的烹饪。那么，在此之前需要进行各个辅料的准备工作，等到这些辅料都准备好了，就可以开始煮八宝饭了。因为辅料之间是相互独立的，所以完全可以分开独立完成，而在所有辅料都没有完成之前，我们只能等待。等到材料全部准备好，我们就可以开始烹饪的工作了。当然，在烹饪的时候，我们又可以准备进行下一轮工作了，也就是说进行下一次八宝饭的辅料准备。在这个地方，辅料的准备是由各个子线程完成的，而煮饭这个工作是主线程完成的，主线程和子线程之间就是通过事件进行沟通的。主线程需要知道当前各个材料准备好了没，而子线程需要知道八宝饭烧好了没，是不是该进行下一轮辅料的准备了。这个中间就存在一个同步的问题了。

     如果大家对之前的信号量还有印象的话，当初我们是用count来表示资源的个数。而今天，我们用flags来表示事件状态，而其中的bit则表示了一个一个具体的事件。只不过有的线程在等待多个事件，而有的线程在等待一个事件，有的线程在获取事件后bit位立即清除，有的线程在获取事件后继续留存。

    所以下面，我们就看看raw-os上面的事件是怎么设计的。当然，我们首先看到的还是关于事件的基本数据结构，

[cpp] view plaincopy

1. typedef struct RAW_EVENT  
2.  {   
3.     RAW_COMMON_BLOCK_OBJECT       common_block_obj;  
4.     RAW_U32  flags;  
5.       
6.  } RAW_EVENT;  
7.    
8.    

    这和我们之前介绍的没什么不一样，就是通用结构加上flag标志。关于事件的基本处理函数也不复杂，主要就是创建、申请、设置和删除四个基本操作。我们来看看每一步分别是怎么实现的，首先介绍的还是事件的创建过程， [cpp] view plaincopy

1. RAW_U16 raw_event_create(RAW_EVENT *event_ptr, RAW_U8 *name_ptr, RAW_U32 flags_init)  
2.  {  
3.     #if (RAW_EVENT_FUNCTION_CHECK > 0)  
4.       
5.     if (event_ptr == 0) {  
6.           
7.         return RAW_NULL_OBJECT;  
8.     }  
9.       
10.     #endif  
11.    
12.     /*Init the list*/  
13.     list_init(&event_ptr->common_block_obj.block_list);  
14.     event_ptr->common_block_obj.block_way = 0;  
15.     event_ptr->common_block_obj.name = name_ptr;    
16.     event_ptr->flags = flags_init ;  
17.       
18.     return RAW_SUCCESS;  
19.  }  
20.    

    看了代码，相信要说的部分不是很多，关键就是flags的赋值部分，其他的都和信号量差不太多。这里的flags代表了某一个起始状态，也就是说当前可以干什么事情、满足哪些条件等等。下面，我们继续看事件的获取函数，稍微复杂一些，

[cpp] view plaincopy

1. RAW_U16 raw_event_get(RAW_EVENT *event_ptr, RAW_U32  requested_flags, RAW_U8 get_option, RAW_U32 wait_option)  
2.  {  
3.         RAW_U16 error_status;  
4.       
5.      RAW_U8 status;  
6.     RAW_SR_ALLOC();  
7.    
8.     #if (RAW_EVENT_FUNCTION_CHECK > 0)  
9.    
10.     if (raw_int_nesting) {  
11.    
12.         return RAW_NOT_CALLED_BY_ISR;  
13.           
14.     }  
15.    
16.     if ((get_option  != RAW_AND) && (get_option  != RAW_OR) && (get_option  != RAW_AND_CLEAR) && (get_option  != RAW_OR_CLEAR)) {  
17.    
18.         return RAW_NO_THIS_OPTION;  
19.     }  
20.       
21.     #endif  
22.       
23.      RAW_CRITICAL_ENTER();  
24.    
25.     /*if option is and flag*/  
26.      if (get_option & RAW_FLAGS_AND_MASK) {  
27.       
28.          if ((event_ptr->flags & requested_flags) == requested_flags) {  
29.        
30.              status = RAW_TRUE;  
31.          }  
32.                   
33.          else {  
34.              status =  RAW_FALSE;  
35.          }  
36.                   
37.      }  
38.     /*if option is or flag*/  
39.      else {  
40.        
41.          if (event_ptr->flags & requested_flags) {  
42.    
43.               
44.              status =  RAW_TRUE;  
45.          }  
46.                   
47.          else {  
48.     
49.              status =  RAW_FALSE;  
50.          }  
51.                   
52.      }  
53.    
54.    
55.           
56.      if (status) {  
57.    
58.         /*does it need to clear the flags*/  
59.         if (get_option & RAW_FLAGS_CLEAR_MASK) {  
60.             event_ptr->flags  &=  ~requested_flags;  
61.         }  
62.           
63.         RAW_CRITICAL_EXIT();      
64.         return RAW_SUCCESS;  
65.                   
66.      }  
67.           
68.     /*Cann't get event, and return immediately if wait_option is  RAW_NO_WAIT*/  
69.     if (wait_option == RAW_NO_WAIT) {   
70.         RAW_CRITICAL_EXIT();  
71.         return RAW_NO_PEND_WAIT;  
72.     }     
73.    
74.     /*system is locked so task can not be blocked just return immediately*/  
75.     if (raw_sched_lock) {     
76.         RAW_CRITICAL_EXIT();      
77.         return RAW_SCHED_DISABLE;  
78.     }  
79.     
80.     /*Remember the passed information*/  
81.     raw_task_active->raw_suspend_option =  get_option;  
82.     raw_task_active->raw_suspend_flags = requested_flags;  
83.       
84.     raw_pend_object(&event_ptr->common_block_obj, raw_task_active, wait_option);  
85.     RAW_CRITICAL_EXIT();  
86.    
87.     raw_sched();   
88.       
89.     RAW_CRITICAL_ENTER();  
90.       
91.     /*does it need to clear the flags*/  
92.     if (get_option & RAW_FLAGS_CLEAR_MASK) {  
93.         event_ptr->flags  &=  ~requested_flags;  
94.     }  
95.       
96.     RAW_CRITICAL_EXIT();  
97.       
98.     /*So the task is waked up, need know which reason cause wake up.*/  
99.     error_status = block_state_post_process(raw_task_active, 0);  
100.     return error_status;  
101.    
102.       
103.  }  
104.    

    注意，这里事件和其他get函数的最大差别就是，函数多了一个get_option，它表示当前是同时申请多个事件还是多个事件中的一个事件，申请后是否需要进行clear置位等等，我们不妨看看具体细节，

    （1）判断函数是否在中断中；

    （2）判断get_option是否合法；

    （3）判断是否存在可以获取的事件，and或者是or；

    （4）如果事件可以获取，那么再判断是否需要置位操作，函数返回；

    （5）判断是否愿意等待，否则返回；

    （6）判断是否禁止调度，是则返回；

    （7）将自己pend到等待队列中；

    （8）调用公共调度函数转到其他线程继续运行；

    （9）当前线程重新得到运行的机会，根据选项清除标志位，函数返回。

    看完了事件的申请，下面就可以看看事件的设置函数了，

[cpp] view plaincopy

1. RAW_U16 raw_event_set(RAW_EVENT *event_ptr, RAW_U32  flags_to_set, RAW_U8 set_option)  
2.  {  
3.     LIST                                         *iter;  
4.     LIST                                         *event_head_ptr;  
5.     LIST                                         *iter_temp;  
6.     struct RAW_TASK_OBJ          *task_ptr;  
7.       
8.     RAW_U8 status;  
9.     RAW_U8 need_sche = 0;  
10.       
11.     RAW_SR_ALLOC();  
12.    
13.     #if (RAW_EVENT_FUNCTION_CHECK > 0)  
14.    
15.     if (event_ptr == 0) {  
16.         return RAW_NULL_OBJECT;  
17.     }  
18.       
19.     if ((set_option  != RAW_AND) && (set_option  != RAW_OR)) {  
20.         return RAW_NO_THIS_OPTION;  
21.     }  
22.       
23.     #endif  
24.    
25.     event_head_ptr =  &event_ptr->common_block_obj.block_list;  
26.       
27.     status = RAW_FALSE;  
28.       
29.     RAW_CRITICAL_ENTER();  
30.    
31.      /*if the set_option is AND_MASK, it just clear the flags and will return immediately!*/  
32.      if (set_option & RAW_FLAGS_AND_MASK)  {  
33.       
34.         event_ptr->flags  &=  flags_to_set;  
35.    
36.         RAW_CRITICAL_EXIT();  
37.         return  RAW_SUCCESS;  
38.      }  
39.     /*if it is or mask then set the flag and continue.........*/  
40.      else  {  
41.               
42.         event_ptr->flags |= flags_to_set;      
43.      }  
44.    
45.     iter = event_head_ptr->next;  
46.    
47.     /*if list is not empty*/  
48.     while (iter !=event_head_ptr) {  
49.    
50.         task_ptr =  list_entry(iter, RAW_TASK_OBJ, task_list);  
51.         iter_temp =  iter->next;  
52.           
53.         if (task_ptr->raw_suspend_option & RAW_FLAGS_AND_MASK)  {  
54.    
55.             if ((event_ptr->flags  & task_ptr ->raw_suspend_flags) == task_ptr ->raw_suspend_flags)  
56.                 status =  RAW_TRUE;  
57.             else  
58.    
59.                 status =   RAW_FALSE;  
60.         }  
61.    
62.           
63.         else {  
64.    
65.             if (event_ptr->flags  &  task_ptr ->raw_suspend_flags)  
66.                   
67.                 status =  RAW_TRUE;  
68.             else  
69.                   
70.                 status =  RAW_FALSE;  
71.         }  
72.    
73.           
74.         if  (status)  {  
75.               
76.             /*Ok the task condition is met, just wake this task*/  
77.             raw_wake_object(task_ptr);  
78.       
79.             /*if  task is waken up*/  
80.             need_sche = 1;  
81.         }  
82.    
83.         iter = iter_temp;  
84.    
85.     }  
86.    
87.     RAW_CRITICAL_EXIT();  
88.    
89.     if (need_sche) {  
90.           
91.         raw_sched();  
92.     }  
93.       
94.     return RAW_SUCCESS;  
95.           
96.        
97.  }  
98.    

    从函数上也看得出来，这里有一个set_option的选项，主要是为了供调用者选择是进行and设置还是or设置，细节如下所示，

    （1）判断参数合法性；

    （2）判断set_option合法性；

    （3）如果选项为and，在设置完flags之后函数返回；

    （4）设置flags标志位，开始遍历每一个等待线程；

    （5）如果存在合适的线程，不管是等待多个事件还是一个事件，都将它们唤醒，设置重新调度标志；

    （6）如果重新调度标志为1，调用系统调度函数切换到其他线程运行；

    （7）当前线程再次获取到运行的机会，函数返回。

    转眼之间，我们就到了事件的删除过程了。其实事件的删除非常简单，它就是把所有的等待线程唤醒，就这么简单，不知道我说清楚了没？当然了，这中间可能会有高优先级的线程被加入到ready队列里面，所以重新schedule一下也是很有必要的。

[cpp] view plaincopy

1. RAW_U16 raw_event_delete(RAW_EVENT *event_ptr)  
2.  {  
3.     LIST *block_list_head;  
4.       
5.     RAW_SR_ALLOC();  
6.        
7.     #if (RAW_EVENT_FUNCTION_CHECK > 0)  
8.    
9.     if (event_ptr == 0) {  
10.         return RAW_NULL_OBJECT;  
11.     }     
12.       
13.     #endif  
14.       
15.     block_list_head = &event_ptr->common_block_obj.block_list;  
16.       
17.     RAW_CRITICAL_ENTER();  
18.    
19.     /*All task blocked on this queue is waken up until list is empty*/  
20.     while (!is_list_empty(block_list_head)) {  
21.         delete_pend_obj(list_entry(block_list_head->next, RAW_TASK_OBJ, task_list));   
22.     }      
23.    
24.     event_ptr->flags = 0;  
25.       
26.     RAW_CRITICAL_EXIT();  
27.       
28.      raw_sched();    
29.    
30.     return RAW_SUCCESS;  
31.  }  
32.   
    

嵌入式操作系统内核原理和开发（消息队列）

 消息队列是线程交互的一种方法，任务可以通过消息队列来实现数据的沟通和交换。在嵌入式系统上，这可以说这是用的最多的一种方法。通过消息队列，无论是发送者，还是接受者都可以循环地处理各种消息。而我们知道，存储消息最好的方式就是循环队列，如果消息已满，那么发送者可以把自己pend到等待队列上；而如果此时没有消息，那么接受者也可以把自己pend到等待队列上。当然实现消息队列的方法很多，甚至用户可以自己利用互斥量和信号量来实现，而嵌入式系统常常会默认提供这样的功能函数，我想主要的目的还是为了方便用户，让他们可以更多地从业务的角度来看问题，而不是把重点关注在这些底层的细节上面。
  
      首先，我们还是看看rawos上面关于消息队列的数据结构是怎么定义的，
[cpp] view plaincopy

1. typedef struct RAW_MSG_Q {      
2.       
3.     RAW_VOID         **queue_start;            /* Pointer to start of queue data                              */  
4.     RAW_VOID         **queue_end;              /* Pointer to end   of queue data                              */  
5.     RAW_VOID         **write;               /* Pointer to where next message will be inserted  in   the Q  */  
6.     RAW_VOID         **read;              /* Pointer to where next message will be extracted from the Q  */  
7.     RAW_U32       size;             /* Size of queue (maximum number of entries)                   */  
8.     RAW_U32       current_numbers;          /* Current number of entries in the queue                      */  
9.     RAW_U16        blocked_send_task_numbers; /*number of blocked send task numbers                    */  
10.     RAW_U16        blocked_receive_task_numbers; /*number of blocked send task numbers                    */  
11.           
12.   } RAW_MSG_Q;  
13.     
14.   typedef struct RAW_QUEUE  
15.   {   
16.     RAW_COMMON_BLOCK_OBJECT       common_block_obj;  
17.     RAW_MSG_Q             msg_q;  
18.       
19.   } RAW_QUEUE;  

    上面的代码中有两段数据结构，第一段主要表示循环队列的内容，其中包括了队列首地址、队列末尾地址、当前队列读取地址、当前队列插入地址、队列大小、消息个数、阻塞的发送线程数据、阻塞的接受线程数目。而第二段数据结构就比较简单，它把通用等待结构和循环队列合在了一起，共同构成了消息队列的数据结构。
 
     根据我们以前的经验，互斥同步数据结构的操作都会分成几个部分，当然消息队列也不例外，也会分成初始化、发送消息、接受消息、清除消息、删除消息队列等几种操作函数。当然，消息队列还是增加了一个新的选项，那就是插入消息的时候可以插入在队列的前方，还是插入在队列的尾部，这在某种程度上决定了消息的优先级。说到这，我们还是看看消息队列是怎么初始化的，
[cpp] view plaincopy

1. RAW_U16 raw_queue_create(RAW_QUEUE  *p_q, RAW_U8    *p_name, RAW_VOID **msg_start, RAW_U32  number)  
2.   {  
3.     
4.     #if (RAW_QUEUE_FUNCTION_CHECK > 0)  
5.     
6.     if (p_q == 0) {  
7.           
8.         return RAW_NULL_OBJECT;  
9.     }  
10.       
11.     if ( msg_start == 0) {  
12.           
13.         return RAW_NULL_POINTER;  
14.     }  
15.       
16.     if (number == 0) {  
17.           
18.         return RAW_ZERO_NUMBER;  
19.     }  
20.       
21.     #endif  
22.     
23.     list_init(&p_q->common_block_obj.block_list);  
24.                                    
25.     p_q->common_block_obj.name = p_name;     
26.     p_q->common_block_obj.block_way = 0;  
27.     p_q->msg_q.queue_start  =       msg_start;               /*      Initialize the queue                 */  
28.     p_q->msg_q.queue_end             = &msg_start[number];  
29.     p_q->msg_q.write              = msg_start;  
30.     p_q->msg_q.read             = msg_start;  
31.     p_q->msg_q.size            =  number;  
32.     p_q->msg_q.current_numbers         = 0;  
33.     p_q->msg_q.blocked_send_task_numbers = 0;  
34.     p_q->msg_q.blocked_receive_task_numbers = 0;  
35.     return RAW_SUCCESS;  
36.   }  
37.    

     虽然相比较之前的互斥函数，消息队列的初始化内容好像多一些。但是大家如果对循环队列的知识比较了解的话，其实也不是很复杂的。我们看到，函数除了对通用阻塞结构进行初始化之外，就是对这些循环队列进行初始化。接着，我们就可以看看消息发送函数是怎么样的，
[cpp] view plaincopy

1. static RAW_U16 internal_msg_post(RAW_QUEUE *p_q, RAW_VOID *p_void,  RAW_U8 opt_send_method, RAW_U8 opt_wake_all, RAW_U32 wait_option)               
2.   {  
3.     RAW_U16 error_status;  
4.     LIST *block_list_head;  
5.     RAW_U8 block_way;  
6.       
7.     RAW_SR_ALLOC();  
8.     
9.     #if (RAW_QUEUE_FUNCTION_CHECK > 0)  
10.     
11.     if (raw_int_nesting) {  
12.     
13.         if (wait_option != RAW_NO_WAIT) {  
14.               
15.             return RAW_NOT_CALLED_BY_ISR;  
16.         }  
17.     }  
18.     
19.     if (p_q == 0) {  
20.           
21.         return RAW_NULL_OBJECT;  
22.     }  
23.       
24.     if (p_void == 0) {  
25.           
26.         return RAW_NULL_POINTER;  
27.     }  
28.       
29.     #endif  
30.     
31.     block_list_head = &p_q->common_block_obj.block_list;  
32.       
33.     RAW_CRITICAL_ENTER();  
34.     
35.     /*queue is full condition, there should be no received task blocked on queue object!*/  
36.     if (p_q->msg_q.current_numbers >= p_q->msg_q.size) {    
37.     
38.         if (wait_option  == RAW_NO_WAIT) {  
39.             RAW_CRITICAL_EXIT();  
40.             return RAW_MSG_MAX;  
41.         }  
42.     
43.         else {  
44.               
45.             /*system is locked so task can not be blocked just return immediately*/  
46.             if (raw_sched_lock) {     
47.                 RAW_CRITICAL_EXIT();      
48.                 return RAW_SCHED_DISABLE;      
49.             }  
50.             /*queue is full and  SEND_TO_FRONT  method is not allowd*/  
51.             if (opt_send_method == SEND_TO_FRONT) {  
52.     
53.                 RAW_CRITICAL_EXIT();      
54.                 return RAW_QUEUE_FULL_OPT_ERROR;    
55.             }  
56.     
57.             p_q->msg_q.blocked_send_task_numbers++;  
58.             raw_task_active->msg = p_void;  
59.             block_way = p_q->common_block_obj.block_way;  
60.             p_q->common_block_obj.block_way = RAW_BLOCKED_WAY_FIFO;  
61.             /*there should be no blocked received task beacuse msg exits*/  
62.             raw_pend_object(&p_q->common_block_obj, raw_task_active, wait_option);  
63.             p_q->common_block_obj.block_way = block_way;  
64.               
65.             RAW_CRITICAL_EXIT();  
66.     
67.             raw_sched();   
68.               
69.             error_status = block_state_post_process(raw_task_active, 0);  
70.     
71.             return error_status;          
72.               
73.         }  
74.     
75.     }  
76.     
77.     /*Queue is not full here, there should be no blocked send task*/      
78.     /*If there is no blocked receive task*/  
79.     if (is_list_empty(block_list_head)) {          
80.     
81.         p_q->msg_q.current_numbers++;                                 /* Update the nbr of entries in the queue        */  
82.           
83.         if (opt_send_method == SEND_TO_END)  {  
84.     
85.             *p_q->msg_q.write++ = p_void;                                
86.     
87.             if (p_q->msg_q.write == p_q->msg_q.queue_end) {     
88.                   
89.                 p_q->msg_q.write = p_q->msg_q.queue_start;  
90.                   
91.             }     
92.     
93.         }  
94.     
95.         else {  
96.     
97.             if (p_q->msg_q.read == p_q->msg_q.queue_start) {                
98.                 p_q->msg_q.read = p_q->msg_q.queue_end;  
99.             }  
100.               
101.             p_q->msg_q.read--;  
102.             *p_q->msg_q.read = p_void;                               /* Insert message into queue                     */  
103.               
104.         }  
105.           
106.         RAW_CRITICAL_EXIT();  
107.           
108.         return RAW_SUCCESS;  
109.     }  
110.     
111.     /*wake all the task blocked on this queue*/  
112.     if (opt_wake_all) {  
113.     
114.         while (!is_list_empty(block_list_head)) {  
115.             wake_send_msg(list_entry(block_list_head->next, RAW_TASK_OBJ, task_list),  p_void);    
116.         }  
117.           
118.         p_q->msg_q.blocked_receive_task_numbers = 0;  
119.     }  
120.       
121.     /*wake hignhest priority task blocked on this queue and send msg to it*/  
122.     else {  
123.           
124.         wake_send_msg(list_entry(block_list_head->next, RAW_TASK_OBJ, task_list),  p_void);    
125.         p_q->msg_q.blocked_receive_task_numbers--;  
126.     }  
127.       
128.     RAW_CRITICAL_EXIT();  
129.     
130.     raw_sched();      
131.     return RAW_SUCCESS;  
132.   }  
133.    

    这里消息发送函数稍显冗长，这主要是因为消息发送的情况比较复杂，方方面面考虑的情况比较多。但是整个函数处理的逻辑还是比较清晰的，只要有耐心，慢慢读下去还是没有什么问题。这里不妨和大家一起看一下消息发送函数是怎么实现的，
     （1）检验参数合法性，注意在中断下调用这个函数时，必须是RAW_NO_WAIT的选项，中断毕竟是不好调度的；
     （2） 处理消息已满的情况，
             a）如果线程不想等待，函数返回；
             b）如果禁止调度，函数返回；
             c）消息存储到线程的msg里面，线程把自己pend到等待队列中；
             d）调用系统调度函数，等待再次被调度的机会，函数返回。
     （3）当前消息未满，但是当前没有等待队列，那么根据要求把消息压入循环队列，函数返回；
     （4）当前消息未满，且存在等待队列，说明此时已经没有消息可读，
             a）如果需要唤醒所有的等待线程，那么唤醒所有的线程，等待线程总数置为0；
             b）如果只是唤起某一个线程，那么唤醒第一个等待线程，等待线程总数自减；
     （5）调用系统调度函数，防止有高优先级的线程加入调度队列；
     （6）线程再次得到运行的机会，函数返回。
 
     看到上面的代码，我们发现只要梳理好了代码的逻辑，其实消息发送函数也是比较好理解的。当然，有消息的发送，就必然会存在消息的接受了。此时肯定也会出现没有消息、有消息两种情况了。
[cpp] view plaincopy

1. RAW_U16 raw_queue_receive (RAW_QUEUE *p_q, RAW_U32 wait_option, RAW_VOID  **msg)  
2.   {  
3.     
4.     RAW_VOID *pmsg;  
5.     RAW_U16 result;  
6.     LIST *block_list_head;  
7.     RAW_TASK_OBJ *blocked_send_task;  
8.       
9.     RAW_SR_ALLOC();  
10.     
11.     #if (RAW_QUEUE_FUNCTION_CHECK > 0)  
12.     
13.     if (raw_int_nesting) {  
14.           
15.         return RAW_NOT_CALLED_BY_ISR;  
16.           
17.     }  
18.     
19.     if (p_q == 0) {  
20.           
21.         return RAW_NULL_OBJECT;  
22.     }  
23.       
24.     if (msg == 0) {  
25.           
26.         return RAW_NULL_POINTER;  
27.     }  
28.       
29.     #endif  
30.     
31.     block_list_head = &p_q->common_block_obj.block_list;  
32.       
33.     RAW_CRITICAL_ENTER();  
34.     
35.       
36.         /*if queue has msgs, just receive it*/  
37.     if (p_q->msg_q.current_numbers) {   
38.           
39.         pmsg = *p_q->msg_q.read++;                      
40.           
41.         if (p_q->msg_q.read == p_q->msg_q.queue_end) {           
42.             p_q->msg_q.read = p_q->msg_q.queue_start;  
43.         }  
44.     
45.         *msg = pmsg;  
46.     
47.         /*if there are  blocked_send_tasks, just reload the task msg to end*/  
48.         if (p_q->msg_q.blocked_send_task_numbers) {  
49.     
50.             blocked_send_task = list_entry(block_list_head->next, RAW_TASK_OBJ, task_list);  
51.               
52.             p_q->msg_q.blocked_send_task_numbers--;  
53.               
54.             *p_q->msg_q.write++ = blocked_send_task->msg;                                
55.     
56.             if (p_q->msg_q.write == p_q->msg_q.queue_end) {     
57.                   
58.                 p_q->msg_q.write = p_q->msg_q.queue_start;  
59.                   
60.             }     
61.               
62.             raw_wake_object(blocked_send_task);  
63.             RAW_CRITICAL_EXIT();  
64.               
65.             raw_sched();    
66.             return RAW_SUCCESS;  
67.           
68.         }  
69.     
70.         p_q->msg_q.current_numbers--;    
71.           
72.         RAW_CRITICAL_EXIT();  
73.           
74.         return RAW_SUCCESS;                           
75.     }  
76.     
77.     
78.     
79.     if (wait_option == RAW_NO_WAIT) {    /* Caller wants to block if not available?                */  
80.         *msg = (RAW_VOID *)0;  
81.         RAW_CRITICAL_EXIT();  
82.         return RAW_NO_PEND_WAIT;  
83.     }   
84.     
85.     if (raw_sched_lock) {     
86.         RAW_CRITICAL_EXIT();      
87.         return RAW_SCHED_DISABLE;      
88.     }  
89.     
90.     raw_pend_object(&p_q->common_block_obj, raw_task_active, wait_option);  
91.     p_q->msg_q.blocked_receive_task_numbers++;  
92.       
93.     RAW_CRITICAL_EXIT();  
94.       
95.     raw_sched();                                               
96.     
97.     RAW_CRITICAL_ENTER();  
98.       
99.     *msg      = (RAW_VOID      *)0;  
100.     result = block_state_post_process(raw_task_active, msg);  
101.       
102.     RAW_CRITICAL_EXIT();    
103.     
104.     return result;  
105.       
106.   }  
107.    

    和发送消息函数相比，接受消息的操作还是要少一些，不要紧，大家一起来看一下实现逻辑，
     （1）判断参数合法性；
     （2）如果当前存在消息，
             a）读取循环队列中的消息；
             b）判断当前是否存在等待线程，因为之前有可能存在没有压入队列的消息，那么此时压入消息，唤醒该线程即可，调用系统调度函数返回；
             c）没有等待线程，消息总数自减，函数返回。
     （3）当前没有消息，
             a）线程不愿等待，函数返回；
             b）系统禁止调度，函数返回；
             c）线程将自己pend到等待队列中；
             d）调用系统调度函数，切换到其他线程继续运行；
             e）线程再次获得运行的机会，从thread结构中获取返回结果，函数返回。
 
     和发送消息、接受消息比较起来，清除消息和删除消息的处理就比较简单了。为了说明问题，我们不妨放在一起讨论一下，
[cpp] view plaincopy

1. RAW_U16 raw_queue_flush(RAW_QUEUE  *p_q)  
2.   {  
3.     LIST *block_list_head;  
4.     
5.     RAW_SR_ALLOC();  
6.       
7.     RAW_TASK_OBJ *block_task;  
8.       
9.     #if (RAW_QUEUE_FUNCTION_CHECK > 0)  
10.     
11.     if (p_q == 0) {  
12.           
13.         return RAW_NULL_OBJECT;  
14.     }  
15.       
16.     #endif  
17.       
18.     block_list_head = &p_q->common_block_obj.block_list;  
19.       
20.     RAW_CRITICAL_ENTER();  
21.     
22.     /*if queue is full and task is blocked on this queue, then wake all the task*/  
23.     if (p_q->msg_q.current_numbers >= p_q->msg_q.size) {  
24.         while (!is_list_empty(block_list_head)) {  
25.             block_task = list_entry(block_list_head->next, RAW_TASK_OBJ, task_list);  
26.             raw_wake_object(block_task);  
27.             block_task->block_status = RAW_B_ABORT;  
28.     
29.         }  
30.     
31.         p_q->msg_q.blocked_send_task_numbers = 0;  
32.     }  
33.       
34.     RAW_CRITICAL_EXIT();   
35.       
36.     raw_sched();  
37.       
38.     return RAW_SUCCESS;  
39.   }  
40.   #endif  
41.     
42.     
43.   #if (CONFIG_RAW_QUEUE_DELETE > 0)  
44.   RAW_U16 raw_queue_delete(RAW_QUEUE *p_q)  
45.   {  
46.     LIST  *block_list_head;  
47.       
48.     RAW_SR_ALLOC();  
49.     
50.     #if (RAW_QUEUE_FUNCTION_CHECK > 0)  
51.     
52.     if (p_q == 0) {  
53.           
54.         return RAW_NULL_OBJECT;  
55.     }  
56.       
57.     #endif  
58.     
59.     block_list_head = &p_q->common_block_obj.block_list;  
60.       
61.     RAW_CRITICAL_ENTER();  
62.     
63.     /*All task blocked on this queue is waken up*/  
64.     while (!is_list_empty(block_list_head))  {  
65.         delete_pend_obj(list_entry(block_list_head->next, RAW_TASK_OBJ, task_list));   
66.     }                               
67.       
68.     RAW_CRITICAL_EXIT();  
69.     
70.     raw_sched();   
71.       
72.     return RAW_SUCCESS;  
73.       
74.   }  
75.   #endif  
76.    

     从代码据结构上也看得出来，两个函数的处理逻辑十分相像，所以可以放在一起研究一下，
     （1）判断参数合法性；
     （2）唤醒等待线程，这里消息清除函数唤醒的是发送线程，而消息删除函数唤醒的所有线程；
     （3）调用系统调度函数，切换到其他线程继续运行；
     （4）当前线程再次获得运行的机会，函数返回，一切ok搞定。
 

嵌入式操作系统内核原理和开发（实时调度）

和很多通用的操作系统相比， 实时操作系统有自己的一个特点，那就是实时调度。通用操作系统的线程优先级一般是可以变化的，而实时系统的线程优先级却是不变的。之所以这么设计，是为了保证高优先级的任务在第一时间获得调度，这样才能保证调度的实时性。因为实时系统是严格按照优先级搞定调度的，所以不管什么时候，我们只要寻找到最高优先级的任务即可。

    rawos系统可以支持256个优先级，对任务的创建个数也没有限制，所以就会出现多个任务共享一个优先级的情况。因此系统本身对同优先级的任务分配了定额的时间片，一旦该任务时间片用完，就会被放到优先级的末尾，直到获得下一次的调度机会，下面的代码就说明了这一情况，它是在时钟中断的时候被调度的，

[cpp] view plaincopy

1. void caculate_time_slice()  
2.  {  
3.     RAW_TASK_OBJ   *task_ptr;  
4.     LIST *head;  
5.       
6.     RAW_SR_ALLOC();  
7.    
8.     task_ptr = raw_task_active;  
9.     head = &raw_ready_queue.task_ready_list[task_ptr->priority];  
10.        
11.     RAW_CRITICAL_ENTER();  
12.                              
13.     if (is_list_empty(head)) {  
14.    
15.         RAW_CRITICAL_EXIT();  
16.         return;  
17.     }  
18.    
19.     /*there is only one task on this ready list, so do not need to caculate time slice*/  
20.     if (head->next->next == head)  {  
21.           
22.         RAW_CRITICAL_EXIT();  
23.         return;  
24.           
25.     }  
26.    
27.     if (task_ptr->time_slice) {  
28.         task_ptr->time_slice--;  
29.     }  
30.    
31.     /*if current active task has time_slice, just return*/  
32.     if (task_ptr->time_slice) {                 
33.         RAW_CRITICAL_EXIT();  
34.         return;  
35.     }  
36.    
37.     /*Move current active task to the end of ready list for the same priority*/  
38.     move_to_ready_list_end(&raw_ready_queue, task_ptr);  
39.    
40.     /*restore the task time slice*/   
41.     task_ptr->time_slice = task_ptr->time_total;    
42.       
43.     RAW_CRITICAL_EXIT();  
44.  }  
45.    

    上面说的是一个优先级下面有多个任务的情况，如果优先级本身只有一个任务，那么就很抱歉了，下面还得继续运行这个任务。另外，我们在windows上面编程的时候喜欢暂时释放线程的运行权利，调用sleep（0）即可，那么这在rawos上是怎么实现的呢， [cpp] view plaincopy

1. RAW_U16  raw_sleep(RAW_U32  dly)   
2.  {  
3.     RAW_U16 error_status;  
4.       
5.     RAW_SR_ALLOC();  
6.    
7.     #if (RAW_TASK_FUNCTION_CHECK > 0)  
8.       
9.     if (raw_int_nesting) {  
10.           
11.         return RAW_NOT_CALLED_BY_ISR;  
12.     }  
13.     #endif        
14.           
15.     RAW_CRITICAL_ENTER();  
16.    
17.     if  (dly) {  
18.    
19.         /*system is locked so task can not sleep just return immediately*/  
20.         if (raw_sched_lock) {     
21.             RAW_CRITICAL_EXIT();      
22.             return RAW_SCHED_DISABLE;  
23.         }  
24.    
25.         raw_task_active->task_state = RAW_DLY;  
26.    
27.         tick_list_insert(raw_task_active, dly);  
28.                      
29.         remove_ready_list(&raw_ready_queue, raw_task_active);  
30.     }  
31.       
32.     else {    
33.         /*make current task to the end of ready list*/  
34.          move_to_ready_list_end(&raw_ready_queue, raw_task_active);  
35.     }  
36.    
37.     RAW_CRITICAL_EXIT();  
38.    
39.     raw_sched();     
40.    
41.     if (dly) {  
42.         /*task is timeout after sleep*/  
43.         error_status = block_state_post_process(raw_task_active, 0);  
44.     }  
45.    
46.     else {  
47.           
48.         error_status = RAW_SUCCESS;  
49.    
50.     }  
51.       
52.     return error_status;  
53.  }  
54.    

    通过的上面的代码，我们可以看到其实系统啥也没干，只是把任务方法放到优先级的链表末尾了。因为我们的系统需要实时调度，所以即使把使用权出让出来，也不可能让低优先的任务运行，只能让同优先级的其他任务运行了。当然，同优先级没有其他任务的时候，只好它自己继续玩了。说了这么多，我们看看系统是怎么调度的， [cpp] view plaincopy

1. void raw_sched()  
2.  {  
3.     RAW_SR_ALLOC();  
4.    
5.     /*if it is in interrupt or system is locked, just return*/   
6.     if (raw_int_nesting || raw_sched_lock) {                
7.         return;                                               
8.     }  
9.       
10.     RAW_CRITICAL_ENTER();  
11.                    
12.       
13.     get_ready_task(&raw_ready_queue);  
14.    
15.     /*if highest task is currently task, then no need to do switch and just return*/  
16.     if (high_ready_obj == raw_task_active) {                   
17.         RAW_CRITICAL_EXIT();                                       
18.         return;  
19.     }  
20.      
21.     CONTEXT_SWITCH();                                             
22.     RAW_CRITICAL_EXIT();  
23.    
24.  }  
25.    

    这个函数看上去很长，其实最重要的部分就是get_ready_task这个函数，它的目的就是寻找到当前最高优先级下面的任务，大家看看代码就明白了， [cpp] view plaincopy

1. void get_ready_task(RAW_RUN_QUEUE *rq)  
2. {  
3.     LIST *node ;  
4.     RAW_S32 highest_pri =  rq->highest_priority;  
5.     /*Highest task must be the first element on the list*/  
6.     node = rq->task_ready_list[highest_pri].next;  
7.   
8.     high_ready_obj = list_entry(node, RAW_TASK_OBJ, task_list);  
9.       
10. }  

    所以，实时系统的核心就是寻找到那个最高优先级就可以了。在实时系统上面，我们一般用bitmap表示优先级，如果对应的优先级存在，那么该位置1，反之置0。那么什么情况下，会发生优先级的改变呢？其实就两种情况，一种是需要把任务加入调度队列的时候，还有一种就是把任务清除出调度队列的时候。 [cpp] view plaincopy

1. void add_ready_list(RAW_RUN_QUEUE *rq, RAW_TASK_OBJ *task_ptr)  
2.  {  
3.     /*if task priority is equal current task priority then add to the end*/  
4.     if (task_ptr->priority == raw_task_active->priority) {  
5.         add_ready_list_end(rq, task_ptr);  
6.     }  
7.     /*if not add to the list front*/  
8.     else {  
9.         add_ready_list_head(rq, task_ptr);  
10.     }  
11.       
12.  }  
13.    
14.    
15.  void remove_ready_list(RAW_RUN_QUEUE *rq, RAW_TASK_OBJ *task_ptr)  
16.  {  
17.    
18.     RAW_S32     i;  
19.     RAW_S32  priority = task_ptr->priority;  
20.    
21.     list_delete(&task_ptr->task_list);  
22.    
23.     /*if the ready list is not empty, we do not need to update the highest priority*/  
24.     if (!is_list_empty(&rq->task_ready_list[priority]) ) {  
25.         return;  
26.     }  
27.    
28.     bit_clear(rq->task_bit_map, priority);  
29.    
30.     /*If task priority not equal to the highest priority, then we do not need to update the highest priority*/  
31.     if (priority != rq->highest_priority) {  
32.         return;  
33.     }  
34.       
35.     i =  bit_search_first_one(rq->task_bit_map, priority,  CONFIG_RAW_PRIO_MAX - priority);  
36.     /*Update the next highest priority task*/  
37.     if (i >= 0) {  
38.         rq->highest_priority = priority + i;  
39.     }   
40.    
41.     else {  
42.           
43.         #if (CONFIG_RAW_ASSERT > 0)  
44.         RAW_ASSERT(0);  
45.         #endif  
46.    
47.     }  
48.       
49.  }  
50.    

    加入调度队列的情况考虑的比较少，我们只需要判断当前的最高优先级和加入任务优先级之间的关系即可。如果新加入的任务优先级高，那么优先级发生了改变；反之什么也不需要做。反之删除任务则比较复杂一些，我们需要判断移除的任务是不是最高优先级，不是还好处理，如果清除出去的任务正好是最高优先级，我们就需要从bitmap中寻找下一个最高优先级了，这个函数就是bit_search_first_one。函数第一个参数是bitmap数组，第二个参数是当前最高优先级，第三个参数是剩下的优先级总数，返回值为次优先级距离当前最高优先级的偏移值。 [cpp] view plaincopy

1. /*For 32 bit cpu*/  
2.  RAW_S32 bit_search_first_one(RAW_U32 *base, RAW_S32 offset,  RAW_S32 width)  
3.  {  
4.      register RAW_U32 *cp, v;  
5.      register RAW_S32 position;  
6.    
7.      cp = base;  
8.      cp += offset >> 5;  
9.           
10.      if (offset & 31) {  
11.  #if (CONFIG_RAW_LITTLE_ENDIAN > 0)  
12.          v = *cp & ~(((RAW_U32)1 << (offset & 31)) - 1);  
13.  #else  
14.           v = *cp & (((RAW_U32)1 << (32 - (offset & 31))) - 1);  
15.  #endif  
16.      }   
17.           
18.     else {  
19.          v = *cp;  
20.      }  
21.    
22.      position = 0;  
23.      while (position < width) {  
24.          if (v) {            /* includes 1 --> search bit of 1 */  
25.              if (!position) position -= (offset & 31);  
26.                           
27.  #if  (CONFIG_RAW_LITTLE_ENDIAN > 0)  
28.    
29.              if (!(v & 0xffff)) {  
30.                  v >>= 16;  
31.                  position += 16;  
32.              }  
33.              if (!(v & 0xff)) {  
34.                  v >>= 8;  
35.                  position += 8;  
36.              }  
37.              if (!(v & 0xf)) {  
38.                  v >>= 4;  
39.                  position += 4;  
40.              }  
41.              if (!(v & 0x3)) {  
42.                  v >>= 2;  
43.                  position += 2;  
44.              }  
45.              if (!(v & 0x1)) {  
46.                  ++position;  
47.              }  
48.                
49.  #else  
50.               
51.             if (!(v & 0xffff0000)) {  
52.                 v <<= 16;  
53.                 position += 16;  
54.             }  
55.               
56.             if (!(v & 0xff000000)) {  
57.                 v <<= 8;  
58.                 position += 8;  
59.             }  
60.               
61.             if (!(v & 0xf0000000)) {  
62.                 v <<= 4;  
63.                 position += 4;  
64.             }  
65.               
66.             if (!(v & 0xc0000000)) {  
67.                 v <<= 2;  
68.                 position += 2;  
69.             }  
70.               
71.             if (!(v & 0x80000000)) {  
72.                 ++position;  
73.             }  
74.                           
75.  #endif  
76.              if (position < width) {  
77.                               
78.                  return position;  
79.                                   
80.              } else {  
81.                       
82.                  return -1;  
83.                                   
84.              }  
85.          } else {              /* all bits are 0 --> 1 Word skip */  
86.              if (position) {  
87.                  position += 32;  
88.              } else {  
89.                  position = 32 - (offset & 31);  
90.              }  
91.              v = *++cp;  
92.          }  
93.      }  
94.    
95.      return -1;  
96.  }  
97.    

    这个函数其实有两个，其中一个是32位cpu，另一个是为8位cpu准备的。当然，我们这里看到的是前一种情形，这里作者还考虑了大小端的情况，小端就是x86之类的cpu，大端就是powerpc之类的cpu，主要是指字节序不同而已。按照作者的说法，这是目前最快的查找方法，能比ucos查找表的方法快多少，我不太清楚，估计只能按照系统设备性能的平均值来估算了，别的还真不好说。要是本身用户侧的代码写的比较差，那么争取的这点调度性能其实意义也不大。

嵌入式操作系统内核原理和开发（延时操作）

 延时操作是操作系统中经常遇到的一种情形。延时的原因很多，有的时候是为了等待外设芯片处理结束，有的时候是为了暂时释放cpu的使用权，有的就是为了希望在一段时间获取资源，如果没法在单位时间内获取，放弃等待。但是不管怎么说，延时都是操作系统必不可少的一个工作。下面我们就看看延时是怎么实现的，
[cpp] view plaincopy

1. static void tick_list_priority_insert(LIST *head, RAW_TASK_OBJ *task_ptr)  
2.   {  
3.     RAW_U32 val;  
4.       
5.     LIST *q,*start, *end;  
6.     RAW_TASK_OBJ  *task_iter_temp;  
7.     
8.     start = end = head;  
9.     val = task_ptr->tick_remain;  
10.       
11.     
12.     for (q = start->next; q != end; q = q->next) {  
13.           
14.         task_iter_temp = list_entry(q, RAW_TASK_OBJ, tick_list);  
15.           
16.         /*sorted by remain time*/  
17.           
18.         if ((task_iter_temp->tick_match - raw_tick_count) > val) {  
19.             break;  
20.         }  
21.     }  
22.     
23.     list_insert(q, &task_ptr->tick_list);  
24.     
25.     
26.   }  
27.     
28.     
29.   void  tick_list_insert(RAW_TASK_OBJ   *task_ptr, RAW_U32  time)  
30.                             
31.   {  
32.     LIST     *tick_head_ptr;  
33.     
34.     RAW_U16   spoke;  
35.     
36.     if (time) {  
37.                                      
38.         task_ptr->tick_match = raw_tick_count + time;  
39.         task_ptr->tick_remain   = time;  
40.     
41.         spoke   = (RAW_U16)(task_ptr->tick_match  &  (TICK_HEAD_ARRAY - 1) );  
42.         tick_head_ptr = &tick_head[spoke];  
43.     
44.         tick_list_priority_insert(tick_head_ptr, task_ptr);  
45.     
46.         task_ptr->tick_head = tick_head_ptr;     
47.     
48.     }                  
49.       
50.   }  
51.    

    延时的代码其实不是很多，所以我在这里把最重要的两个函数给粘贴到这里了。因为每个线程都有可能延时，那么怎么处理这些线程之间的关系就是我们需要做的事情了。我们看到了，我们直接用tick_match表示线程需要等待的那个时间点就可以了。当然，tick是不断增加的，我们可以把尾数相同的线程按照高低顺序排列在一起，这样在对应的tick到来的时候，就直接按照尾数查找就可以了，tick_list_priority_insert就是干了这么一件事情。
 
     那么，tick什么时候到期呢？到期又该怎么处理呢，我们接着往下看，

[cpp] view plaincopy

1. void  tick_list_update(void)  
2.   {  
3.       
4.     LIST     *tick_head_ptr;  
5.     RAW_TASK_OBJ            *p_tcb;  
6.     LIST                            *iter;  
7.     LIST                            *iter_temp;  
8.     
9.     RAW_U16   spoke;  
10.     
11.     RAW_SR_ALLOC();  
12.     
13.     RAW_CRITICAL_ENTER();  
14.       
15.     raw_tick_count++;                                                       
16.     spoke    = (RAW_U16)(raw_tick_count &  (TICK_HEAD_ARRAY - 1) );  
17.     tick_head_ptr  = &tick_head[spoke];  
18.     iter    = tick_head_ptr->next;  
19.       
20.     while (RAW_TRUE) {  
21.     
22.         /*search all the time list if possible*/  
23.         if (iter != tick_head_ptr) {  
24.     
25.             iter_temp =  iter->next;  
26.             p_tcb =  list_entry(iter, RAW_TASK_OBJ, tick_list);  
27.     
28.             /*Since time list is sorted by remain time, so just campare  the absolute time*/  
29.             if (raw_tick_count == p_tcb->tick_match) {  
30.               
31.                 switch (p_tcb->task_state) {  
32.                     case RAW_DLY:  
33.                           
34.                         p_tcb->block_status = RAW_B_OK;   
35.                         p_tcb->task_state = RAW_RDY;    
36.                         tick_list_remove(p_tcb);  
37.                         add_ready_list(&raw_ready_queue, p_tcb);  
38.                         break;   
39.     
40.                     case RAW_PEND_TIMEOUT:  
41.                           
42.                         p_tcb->block_status = RAW_B_TIMEOUT;   
43.                         p_tcb->task_state = RAW_RDY;   
44.                         p_tcb->block_obj = 0;  
45.                         tick_list_remove(p_tcb);  
46.                         /*remove task on the block list because task is timeout*/  
47.                         list_delete(&p_tcb->task_list);   
48.                         add_ready_list(&raw_ready_queue, p_tcb);  
49.                         break;  
50.                           
51.     
52.                     case RAW_PEND_TIMEOUT_SUSPENDED:  
53.                                
54.                         p_tcb->block_status = RAW_B_TIMEOUT;   
55.                         p_tcb->task_state = RAW_SUSPENDED;    
56.                         p_tcb->block_obj = 0;  
57.                         tick_list_remove(p_tcb);  
58.                         /*remove task on the block list because task is timeout*/  
59.                         list_delete(&p_tcb->task_list);   
60.                         break;  
61.                        
62.     
63.     
64.                     case RAW_DLY_SUSPENDED:  
65.                                                 
66.                         p_tcb->task_state  =  RAW_SUSPENDED;  
67.                         p_tcb->block_status = RAW_B_OK;   
68.                         tick_list_remove(p_tcb);                     
69.                         break;  
70.     
71.                     default:  
72.                           
73.                         #if (CONFIG_RAW_ASSERT > 0)  
74.                         RAW_ASSERT(0);  
75.                         #endif  
76.                           
77.                         break;  
78.                 }  
79.     
80.                 iter  = iter_temp;  
81.             }  
82.     
83.         /*if current task time out absolute time is not equal current system time, just break because timer list is sorted*/  
84.             else {  
85.               
86.                 break;  
87.     
88.             }  
89.     
90.         }  
91.    
92.           
93.         /*finish all the time list search */   
94.           
95.         else {  
96.               
97.             break;  
98.         }  
99.           
100.     }  
101.     
102.     RAW_CRITICAL_EXIT();  
103.   }  
104.    

     这个函数是在时钟中断的时候被调用的，根据函数的先后顺序，看看函数实现了哪些功能，
     （1）自增raw_tick_count；
     （2）根据尾数获取tick队列的头指针；
     （3）开始循环迭代处理延时线程；
             a）如果没有没有延时线程，循环跳出；
             b）如果线程的终点tick和当前tick不匹配，跳出循环，因为tick都是排序好的，所以后面的tick肯定不满足要求；
             c）如果当前tick满足要求，根据线程状态进行处理，主要分为延时、阻塞超时、延时挂起、阻塞超时挂起四种状态；
             d）获取下一个延时线程，观察是否满足要求，如果是继续回到c，否则退出循环。
     （4）函数返回，继续时钟中断的剩余操作。
 
     最后，我们补充一下关于有限时间等待的知识。就像以前关于互斥操作的内容一样，其实某些情况下，我们是有时间限制的。一段时间没有获取资源，我们就不希望等待了，所以这里的延时操作还包括这部分的内容，我们看看阻塞函数的相关代码就明白了。

[cpp] view plaincopy

1. RAW_U16 raw_pend_object(RAW_COMMON_BLOCK_OBJECT  *block_common_obj, RAW_TASK_OBJ *task_ptr, RAW_U32 timeout)  
2.   {  
3.     
4.     #if (CONFIG_RAW_ASSERT > 0)  
5.       
6.     if (timeout == 0) {  
7.         RAW_ASSERT(0);  
8.     }  
9.       
10.     #endif  
11.       
12.     task_ptr->block_obj = block_common_obj;  
13.     
14.       
15.     if (timeout == RAW_WAIT_FOREVER) {  
16.           
17.     
18.         task_ptr->task_state = RAW_PEND;  
19.     
20.     }  
21.     /*task is blocked with timeout*/  
22.     else {  
23.         
24.         tick_list_insert(task_ptr,timeout);  
25.     
26.         task_ptr->task_state = RAW_PEND_TIMEOUT;  
27.     
28.     }  
29.       
30.     /*Remove from the ready list*/  
31.     remove_ready_list(&raw_ready_queue, task_ptr);  
32.       
33.     if (block_common_obj->block_way == RAW_BLOCKED_WAY_FIFO) {  
34.           
35.         list_insert(&block_common_obj->block_list, &task_ptr->task_list);  
36.     
37.     }  
38.     
39.     else {  
40.           
41.         /*add to the priority sorted block list*/  
42.         add_to_priority_list(&block_common_obj->block_list, task_ptr);  
43.           
44.     }  
45.       
46.     return RAW_SUCCESS;  
47.   }  
48.    

    大家留意一下这里timeout参数的处理过程，关注一下对应的tick_list_insert函数，这样就可以明白我的意思了。

嵌入式操作系统内核原理和开发（实时系统中的定时器）

关于定时器的内容，其实我们之前也讨论过，也书写过相应的代码，但是表达得比较晦涩，效率也比较低。所以我们这里重新再讲一下定时器的相关代码，看看嵌入式系统中的定时器是怎么实现的。在我们之前讨论线程延时的时候就使用hash的方法，将不同的线程归类到不同的延时队列当中，并且按照时间长短先后排列，这样在最短的时间内就可以寻找到最合适的线程了。本质上，线程延时和定时器的基本原理是一样的。唯一的区别就是，线程延时响应的优先级要高一些，而定时器一般由独立线程完成，rawos也是这么做的。 [cpp] view plaincopy

1. void timer_task(void *pa)   
2.  {  
3.     RAW_U16                             position;  
4.     LIST                                *timer_head_ptr;  
5.     LIST                                *iter;  
6.     LIST                                *iter_temp;  
7.     RAW_TIMER                   *timer_ptr;  
8.    
9.     timer_sem.count = 0;  
10.       
11.     while (1) {  
12.           
13.         /*timer task will be blocked after call this function*/  
14.         raw_semaphore_get(&timer_sem,  RAW_WAIT_FOREVER);  
15.           
16.        /*Disable the system schedule we do not need disable interrupt since nothing to do with interrupt*/  
17.         raw_disable_sche();  
18.    
19.         /*calculate which  timer_head*/  
20.         raw_timer_count++;                                            
21.         position = (RAW_U16)(raw_timer_count & (TIMER_HEAD_NUMBERS - 1) );  
22.         timer_head_ptr  = &timer_head[position];  
23.    
24.         iter    =timer_head_ptr->next;  
25.           
26.         while (RAW_TRUE) {  
27.             /*if timer exits*/    
28.                 if (iter !=timer_head_ptr) {  
29.                     /*Must use iter_temp because iter may be remove later.*/  
30.                     iter_temp = iter->next;  
31.                     timer_ptr =  list_entry(iter, RAW_TIMER, timer_list);  
32.                         
33.                     /*if timeout*/  
34.                  if (raw_timer_count == timer_ptr->match) {    
35.    
36.                         /*remove form timer list*/  
37.                         timer_list_remove(timer_ptr);  
38.                         /*if timer is reschedulable*/             
39.                     if (timer_ptr->reschedule_ticks) {  
40.                             /*Sort by remain time*/  
41.                             timer_ptr->remain = timer_ptr->reschedule_ticks;  
42.                               
43.                             timer_ptr->match  = raw_timer_count + timer_ptr->remain;  
44.                             position   = (RAW_U16)(timer_ptr->match & (TIMER_HEAD_NUMBERS - 1));  
45.                             timer_ptr->to_head = &timer_head[position];  
46.                             timer_list_priority_insert(&timer_head[position], timer_ptr);  
47.                                     
48.                      }   
49.    
50.                         /*Any way both condition need to call registered timer function*/  
51.                    
52.                     if (timer_ptr->raw_timeout_function) {  
53.                         timer_ptr->raw_timeout_function(timer_ptr->raw_timeout_param);  
54.                                    
55.                     }  
56.                   
57.                         iter  = iter_temp;   
58.                  }   
59.    
60.                 else {   
61.                       
62.                         break;  
63.                       
64.              }  
65.    
66.            }  
67.             /*exit because timer is not exit*/        
68.             else {  
69.                
70.                break;  
71.             }  
72.               
73.          }  
74.           
75.          raw_enable_sche();  
76.     }  
77.  }  
78.    

    由于基本原理和之前的线程延时是一样的，所以这里就不重复了。定时器的基本操作其实也不多，主要包括定时器创建、启动定时器、修改定时器、关闭定时器、删除定时器共五个基本函数，大家可以和我一起慢慢看过来。
[cpp] view plaincopy

1. RAW_U16 raw_timer_create(RAW_TIMER *timer_ptr, RAW_U8  *name_ptr,   
2.              RAW_VOID  (*expiration_function)(RAW_U32), RAW_U32 expiration_input,  
3.            RAW_U32 initial_ticks, RAW_U32 reschedule_ticks, RAW_U8 auto_activate)  
4.    
5.  {  
6.    
7.     #if (RAW_TIMER_FUNCTION_CHECK > 0)  
8.       
9.     if (timer_ptr == 0) {  
10.         return RAW_NULL_OBJECT;  
11.     }  
12.       
13.     if (expiration_function == 0) {  
14.         return RAW_NULL_POINTER;  
15.     }  
16.       
17.     #endif  
18.       
19.     timer_ptr->name = name_ptr;  
20.     timer_ptr->raw_timeout_function = expiration_function;  
21.     timer_ptr->raw_timeout_param = expiration_input;  
22.     timer_ptr->init_count = initial_ticks;  
23.     timer_ptr->reschedule_ticks = reschedule_ticks;  
24.     timer_ptr->remain = 0;  
25.     timer_ptr->match = 0;  
26.     timer_ptr->timer_state = TIMER_DEACTIVE;  
27.     timer_ptr->to_head = 0;  
28.       
29.     list_init(&timer_ptr->timer_list);  
30.       
31.     if (auto_activate) {  
32.           
33.          raw_timer_activate(timer_ptr);  
34.     }  
35.       
36.     return RAW_SUCCESS;  
37.  }  
38.    

    创建定时器的操作很简单，主要是把输入的参数存入到RAW_TIMER结构里面。相关的参数包括名称、函数指针、函数参数、初始tick、循环tick、标志参数。当然，由于定时器分为单次定时和循环定时两种，所以这里会有两个参数，如果不是循环定时器，循环tick参数可以不用配置。
[cpp] view plaincopy

1. RAW_U16  raw_timer_activate(RAW_TIMER *timer_ptr)  
2.  {  
3.     RAW_U16 position;  
4.     RAW_SR_ALLOC();  
5.    
6.     #if (RAW_TIMER_FUNCTION_CHECK > 0)  
7.       
8.     if (timer_ptr == 0) {  
9.         return RAW_NULL_OBJECT;  
10.     }  
11.       
12.     #endif  
13.    
14.     /*Timer state TIMER_ACTIVE TIMER_DELETED is not allowed to delete*/  
15.     if (timer_ptr->timer_state == TIMER_ACTIVE)  
16.         return RAW_TIMER_STATE_INVALID;   
17.    
18.     if (timer_ptr->timer_state == TIMER_DELETED)  
19.         return RAW_TIMER_STATE_INVALID;  
20.       
21.     RAW_CRITICAL_ENTER();  
22.     timer_ptr->match  = raw_timer_count + timer_ptr->init_count;  
23.     position   = (RAW_U16)(timer_ptr->match & (TIMER_HEAD_NUMBERS - 1) );  
24.     /*Sort by remain time*/  
25.     timer_ptr->remain = timer_ptr->init_count;  
26.     /*Used by timer delete*/  
27.     timer_ptr->to_head = &timer_head[position];  
28.       
29.     timer_list_priority_insert(&timer_head[position], timer_ptr);  
30.     timer_ptr->timer_state = TIMER_ACTIVE;  
31.    
32.     RAW_CRITICAL_EXIT();  
33.    
34.    
35.     return RAW_SUCCESS;  
36.  }  
37.    

    启动定时器，就是把tick加入到定时器队列当中，看看timer_list_priority_insert这个函数你就明白了。因为整个函数的处理过程涉及到  全局变量timer_head，所以需要在前后面添加中断的处理动作。
[cpp] view plaincopy

1. RAW_U16 raw_timer_change(RAW_TIMER *timer_ptr, RAW_U32 initial_ticks, RAW_U32  reschedule_ticks)  
2.  {  
3.     RAW_SR_ALLOC();  
4.       
5.     #if (RAW_TIMER_FUNCTION_CHECK > 0)  
6.       
7.     if (timer_ptr == 0) {  
8.         return RAW_NULL_OBJECT;  
9.     }  
10.       
11.     #endif  
12.       
13.     /*Only timer state TIMER_DEACTIVE is not allowed here*/   
14.     if (timer_ptr->timer_state != TIMER_DEACTIVE) {  
15.         return RAW_TIMER_STATE_INVALID;  
16.     }  
17.       
18.     if (timer_ptr->timer_state == TIMER_DELETED) {  
19.         return RAW_TIMER_STATE_INVALID;  
20.     }  
21.       
22.     RAW_CRITICAL_ENTER();  
23.     timer_ptr->init_count = initial_ticks;  
24.     timer_ptr->reschedule_ticks = reschedule_ticks;  
25.     RAW_CRITICAL_EXIT();  
26.     return RAW_SUCCESS;  
27.  }  

    定时器修改函数就是把初始tick和循环tick修改一下，当然如果此时定时器还没有运行，初始tick还有用。但是一旦定时器起作用了，起作用的就只能是循环tick了，这一点大家要好好注意。
[cpp] view plaincopy

1. RAW_U16 raw_timer_deactivate(RAW_TIMER *timer_ptr)  
2.  {  
3.     RAW_SR_ALLOC();  
4.    
5.     #if (RAW_TIMER_FUNCTION_CHECK > 0)  
6.       
7.     if (timer_ptr == 0) {  
8.         return RAW_NULL_OBJECT;  
9.     }  
10.       
11.     #endif  
12.       
13.     /*Timer state TIMER_DEACTIVE  TIMER_DELETED is not allowed to delete*/  
14.     if (timer_ptr->timer_state == TIMER_DEACTIVE) {  
15.         return RAW_TIMER_STATE_INVALID;  
16.     }  
17.       
18.     if (timer_ptr->timer_state == TIMER_DELETED) {  
19.         return RAW_TIMER_STATE_INVALID;  
20.    
21.     }  
22.       
23.     RAW_CRITICAL_ENTER();  
24.     timer_list_remove(timer_ptr);  
25.     timer_ptr->timer_state = TIMER_DEACTIVE;  
26.     RAW_CRITICAL_EXIT();  
27.       
28.     return RAW_SUCCESS;  
29.    
30.  }  
31.    

    停止定时器，顾名思义就是将定时器从队列中删除，同时设置状态为TIMER_DEACTIVE。当然在进行操作之前需要判断一下当前定时器的属性，如果定时器本身已经删除或者停止，那什么也不用做了。

[cpp] view plaincopy

1. RAW_U16 raw_timer_delete(RAW_TIMER *timer_ptr)  
2.  {  
3.     RAW_SR_ALLOC();  
4.       
5.     #if (RAW_TIMER_FUNCTION_CHECK > 0)  
6.       
7.     if (timer_ptr == 0) {  
8.         return RAW_NULL_OBJECT;  
9.     }  
10.       
11.     #endif  
12.       
13.     if (timer_ptr->timer_state == TIMER_DELETED) {  
14.           
15.         return RAW_TIMER_STATE_INVALID;  
16.           
17.     }  
18.       
19.     RAW_CRITICAL_ENTER();  
20.       
21.     timer_list_remove(timer_ptr);  
22.     timer_ptr->timer_state = TIMER_DELETED;  
23.       
24.     RAW_CRITICAL_EXIT();  
25.       
26.     return RAW_SUCCESS;  
27.    
28.  }  
29.    

    定时器的删除函数和定时器的停止函数是一样的，主要是判断逻辑不一样的。删除定时器，只要定时器的状态不是已经删除就可以了，其他的操作都是一样的。

嵌入式操作系统内核原理和开发（线程状态）

从第一篇的os博客以来，谈了很多内容，有中断、切换、调度、内存、互斥和延时等等，但是线程的状态却没有涉及到，今天我们要好好说一说。说到线程的状态，按照一般的说法，主要包括就绪、延时、阻塞、阻塞超时四个状态。如果线程没有死亡的话，那么这几个状态也够用了，但是我们后来发现可能需要对某些线程进行挂起处理，这可能是出现了故障或者是为了调试使用。因此，除了上面的四个状态，我们还要补充对应的四个挂起状态，分别是挂起、延时挂起、阻塞挂起、阻塞延时挂起。

     说到了线程状态，下面我们就看看常见的线程处理函数有哪些，无外乎线程创建、线程延时、线程挂起、线程恢复和线程删除等等。 

[cpp] view plaincopy

1. RAW_U16 raw_task_create(RAW_TASK_OBJ  *task_obj, RAW_U8  *task_name,  RAW_VOID   *task_arg,   
2.                                RAW_U8  task_prio,  RAW_U16  time_slice,  PORT_STACK  *task_stack_base,   
3.                                RAW_U32 stack_size, RAW_TASK_ENTRY task_entry, RAW_U8 auto_start)  
4.                                           
5.   {  
6.     #if (RAW_TASK_STACK_CHECK > 0)  
7.     PORT_STACK  *p_stack;  
8.     RAW_U32 i;  
9.     #endif  
10.       
11.     RAW_SR_ALLOC();  
12.       
13.     #if (RAW_TASK_FUNCTION_CHECK > 0)  
14.     
15.     if (task_obj == 0) {  
16.         return RAW_NULL_OBJECT;  
17.     }  
18.       
19.     if (task_prio >= CONFIG_RAW_PRIO_MAX) {  
20.         return RAW_BYOND_MAX_PRIORITY;  
21.     }  
22.       
23.     if (task_stack_base == 0) {  
24.         return RAW_NULL_POINTER;  
25.     }  
26.     
27.     if (task_entry == 0) {  
28.         return RAW_NULL_POINTER;  
29.     }  
30.       
31.     #endif  
32.     
33.     RAW_CRITICAL_ENTER();  
34.       
35.      if (task_prio == IDLE_PRIORITY) {  
36.           
37.         if (idle_task_exit) {  
38.               
39.             RAW_CRITICAL_EXIT();  
40.             return RAW_IDLE_EXIT;  
41.                   
42.         }  
43.           
44.         idle_task_exit = 1;  
45.     }  
46.     
47.     
48.     RAW_CRITICAL_EXIT();  
49.       
50.     raw_memset(task_obj, 0, sizeof(RAW_TASK_OBJ));  
51.     
52.     #if (CONFIG_ROUND_ROBIN > 0)  
53.       
54.     if (time_slice) {  
55.         task_obj->time_total        = time_slice;  
56.           
57.     }  
58.       
59.     else  {  
60.           
61.         task_obj->time_total        = TIME_SLICE_DEFAULT;  
62.     }  
63.     
64.     task_obj->time_slice = task_obj->time_total;  
65.     
66.     #endif  
67.       
68.     if (auto_start)  
69.         task_obj->task_state = RAW_RDY;  
70.     else  
71.         task_obj->task_state = RAW_SUSPENDED;  
72.     
73.     
74.     #if (RAW_TASK_STACK_CHECK > 0)  
75.       
76.     task_obj->task_stack_base = task_stack_base;  
77.     p_stack = task_stack_base;  
78.       
79.       for (i = 0; i < stack_size; i++) {                             
80.         *p_stack++ =0;                                              
81.                   
82.     }  
83.           
84.     #endif  
85.     
86.     task_obj->task_stack  = port_stack_init(task_stack_base, stack_size, task_arg, task_entry);  
87.     task_obj->task_name   = task_name;   
88.     task_obj->priority    = task_prio;  
89.     
90.     task_create_hook(task_obj);  
91.     
92.     
93.     RAW_CRITICAL_ENTER();  
94.       
95.     #if (RAW_TASK_STACK_CHECK > 0)  
96.     task_obj->stack_size = stack_size;  
97.     list_insert(&task_head, &task_obj->stack_check_list);  
98.     #endif  
99.     
100.     if (auto_start) {  
101.         add_ready_list_end(&raw_ready_queue, task_obj);  
102.     }  
103.       
104.     if (raw_os_active !=  RAW_OS_RUNNING) {                 /* Return if multitasking has not started                 */  
105.         RAW_CRITICAL_EXIT();  
106.         return RAW_OS_STOPPED;  
107.     }  
108.     
109.     RAW_CRITICAL_EXIT();  
110.       
111.     if (auto_start) {  
112.         raw_sched();  
113.     }  
114.       
115.     return RAW_SUCCESS;  
116.               
117.   }  
118.    

    创建线程的函数是比较复杂的，内容长一些，参数也多一些。首先看看有哪些参数，虽然很多，但是慢慢梳理一下也不难理解，有名称、参数、优先级、时间片、堆栈起始指针、堆栈大小、入口函数和标志。整个函数基本上都是赋值的过程，最重要的其实就两个部分，一个是port_stack_init，另一个就是add_ready_list_end。前者可以对堆栈进行默认处理，比如压入一些寄存器、压入函数参数、函数指针等等，后者就是把线程加入到就绪队列。
[cpp] view plaincopy

1. RAW_U16  raw_sleep(RAW_U32  dly)   
2.   {  
3.     RAW_U16 error_status;  
4.       
5.     RAW_SR_ALLOC();  
6.     
7.     #if (RAW_TASK_FUNCTION_CHECK > 0)  
8.       
9.     if (raw_int_nesting) {  
10.           
11.         return RAW_NOT_CALLED_BY_ISR;  
12.     }  
13.     #endif        
14.           
15.     RAW_CRITICAL_ENTER();  
16.     
17.     if  (dly) {  
18.     
19.         /*system is locked so task can not sleep just return immediately*/  
20.         if (raw_sched_lock) {     
21.             RAW_CRITICAL_EXIT();      
22.             return RAW_SCHED_DISABLE;  
23.         }  
24.     
25.         raw_task_active->task_state = RAW_DLY;  
26.     
27.         tick_list_insert(raw_task_active, dly);  
28.                      
29.         remove_ready_list(&raw_ready_queue, raw_task_active);  
30.     }  
31.       
32.     else {    
33.         /*make current task to the end of ready list*/  
34.          move_to_ready_list_end(&raw_ready_queue, raw_task_active);  
35.     }  
36.     
37.     RAW_CRITICAL_EXIT();  
38.     
39.     raw_sched();     
40.     
41.     if (dly) {  
42.         /*task is timeout after sleep*/  
43.         error_status = block_state_post_process(raw_task_active, 0);  
44.     }  
45.     
46.     else {  
47.           
48.         error_status = RAW_SUCCESS;  
49.     
50.     }  
51.       
52.     return error_status;  
53.   }  
54.    

    我们之前也介绍过系统的延时功能。延时，就是把线程暂时从就绪队列清除出来，添加到延时队列中。当然如果参数为0，那表示作者只是希望暂时释放cpu的使用权，如果此时没有同等优先级的任务，那么下一个运行的线程还是它自己。  [cpp] view plaincopy

1. RAW_U16  raw_task_suspend(RAW_TASK_OBJ *task_ptr)  
2.   {  
3.     RAW_SR_ALLOC();  
4.     
5.     #if (RAW_TASK_FUNCTION_CHECK > 0)  
6.       
7.     if (task_ptr == 0) {  
8.         return RAW_NULL_OBJECT;  
9.     }  
10.       
11.     #endif        
12.     
13.     if (task_ptr->priority == IDLE_PRIORITY) {  
14.         return RAW_SUSPEND_TASK_NOT_ALLOWED;  
15.     }  
16.       
17.     RAW_CRITICAL_ENTER();  
18.     
19.     if (task_ptr == raw_task_active) {  
20.           
21.         if (raw_sched_lock) {    
22.             RAW_CRITICAL_EXIT();  
23.             return RAW_SCHED_LOCKED;  
24.         }  
25.     }  
26.     
27.     switch (task_ptr->task_state) {  
28.         case RAW_RDY:  
29.             task_ptr->task_state  =  RAW_SUSPENDED;  
30.             remove_ready_list(&raw_ready_queue, task_ptr);  
31.             break;  
32.     
33.         case RAW_DLY:  
34.             task_ptr->task_state  = RAW_DLY_SUSPENDED;  
35.             break;  
36.     
37.         case RAW_PEND:  
38.               
39.             task_ptr->task_state  = RAW_PEND_SUSPENDED;  
40.             break;  
41.               
42.     
43.         case RAW_PEND_TIMEOUT:  
44.             task_ptr->task_state  = RAW_PEND_TIMEOUT_SUSPENDED;  
45.             break;  
46.               
47.     
48.         case RAW_DLY_SUSPENDED:  
49.         case RAW_PEND_SUSPENDED:  
50.         case RAW_PEND_TIMEOUT_SUSPENDED:  
51.             RAW_CRITICAL_EXIT();  
52.             return RAW_SUSPENDED_AGAIN;  
53.           
54.     
55.         default:  
56.               
57.             #if (CONFIG_RAW_ASSERT > 0)  
58.             RAW_ASSERT(0);  
59.             #endif  
60.               
61.             RAW_CRITICAL_EXIT();  
62.             return  RAW_STATE_UNKNOWN;  
63.     }  
64.     
65.     RAW_CRITICAL_EXIT();  
66.       
67.     raw_sched();       
68.     
69.     return RAW_SUCCESS;  
70.   }  
71.    

    挂起任务的动作其实是比较残暴的，因为此时你不知道线程处于什么状态。当然任务如果已经被挂起了，那什么也不用做了，否则就需要把任务修改为对应的挂起状态就可以了。当然如果任务是就绪态的，还得把任务清除处理来。在函数结束的时候，我们需要重新进行调度，因为很有可能当前最高优先级的线程已经发生了改变。
[cpp] view plaincopy

1. RAW_U16  raw_task_resume(RAW_TASK_OBJ *task_ptr)  
2.   {  
3.     RAW_SR_ALLOC();  
4.     
5.     #if (RAW_TASK_FUNCTION_CHECK > 0)  
6.       
7.     if (task_ptr == 0) {  
8.         return RAW_NULL_OBJECT;  
9.     }  
10.       
11.     #endif        
12.       
13.     RAW_CRITICAL_ENTER();  
14.       
15.     switch (task_ptr->task_state) {  
16.         case RAW_RDY:  
17.         case RAW_DLY:  
18.         case RAW_PEND:  
19.         case RAW_PEND_TIMEOUT:  
20.               
21.             RAW_CRITICAL_EXIT();  
22.             return HAS_NOT_SUSPENDED;  
23.               
24.     
25.         case RAW_SUSPENDED:  
26.             task_ptr->task_state = RAW_RDY;  
27.             add_ready_list(&raw_ready_queue, task_ptr);  
28.             break;  
29.     
30.         case RAW_DLY_SUSPENDED:  
31.       
32.             task_ptr->task_state = RAW_DLY;  
33.             break;  
34.     
35.         case RAW_PEND_SUSPENDED:  
36.           
37.             task_ptr->task_state = RAW_PEND;  
38.             break;  
39.     
40.         case RAW_PEND_TIMEOUT_SUSPENDED:  
41.           
42.             task_ptr->task_state = RAW_PEND_TIMEOUT;  
43.             break;  
44.               
45.         default:  
46.    
47.             #if (CONFIG_RAW_ASSERT > 0)  
48.             RAW_ASSERT(0);  
49.             #endif  
50.               
51.             RAW_CRITICAL_EXIT();  
52.               
53.             return RAW_STATE_UNKNOWN;  
54.     
55.     }  
56.     
57.     RAW_CRITICAL_EXIT();  
58.       
59.     raw_sched();     
60.     
61.     return RAW_SUCCESS;  
62.   }  
63.    

    恢复函数其实就是挂起函数的逆向操作。如果任务没有被挂起，那么什么也不用做。否则就需要把任务的状态修改为对应的非挂起状态，当然该就绪的线程还得加入到就绪队列当中去。同时在函数结束之前不忘调度一下，说不定刚刚释放的这个线程就是优先级最高的那个线程。
[cpp] view plaincopy

1. RAW_U16 raw_task_delete(RAW_TASK_OBJ *task_ptr)  
2.  {  
3.     RAW_SR_ALLOC();  
4.    
5.     #if (RAW_TASK_FUNCTION_CHECK > 0)  
6.    
7.     if (task_ptr == 0) {  
8.           
9.         return RAW_NULL_OBJECT;  
10.     }  
11.    
12.     if (raw_int_nesting) {  
13.           
14.         return RAW_NOT_CALLED_BY_ISR;  
15.           
16.     }  
17.       
18.     #endif  
19.    
20.     if (task_ptr->priority == IDLE_PRIORITY) {  
21.           
22.         return RAW_DELETE_TASK_NOT_ALLOWED;  
23.     }  
24.    
25.     RAW_CRITICAL_ENTER();  
26.    
27.     if (task_ptr == raw_task_active) {  
28.           
29.         if (raw_sched_lock) {    
30.             RAW_CRITICAL_EXIT();  
31.             return RAW_SCHED_LOCKED;  
32.         }  
33.     }  
34.       
35.     switch (task_ptr->task_state) {  
36.         case RAW_RDY:  
37.             remove_ready_list(&raw_ready_queue, task_ptr);  
38.             break;  
39.    
40.         case RAW_SUSPENDED:  
41.             break;  
42.    
43.         case RAW_DLY:                             /* Task is only delayed, not on any wait list             */  
44.         case RAW_DLY_SUSPENDED:  
45.             tick_list_remove(task_ptr);  
46.             break;  
47.    
48.         case RAW_PEND:  
49.         case RAW_PEND_SUSPENDED:  
50.         case RAW_PEND_TIMEOUT:  
51.         case RAW_PEND_TIMEOUT_SUSPENDED:  
52.             tick_list_remove(task_ptr);  
53.             list_delete(&task_ptr->task_list);  
54.             break;  
55.    
56.         default:  
57.               
58.             #if (CONFIG_RAW_ASSERT > 0)  
59.             RAW_ASSERT(0);  
60.             #endif  
61.               
62.             RAW_CRITICAL_EXIT();  
63.             return  RAW_STATE_UNKNOWN;  
64.     }    
65.    
66.     task_ptr->task_state = RAW_DELETED;     
67.       
68.     #if (RAW_TASK_STACK_CHECK > 0)  
69.     /*make after_delete_list to right position*/  
70.     after_delete_list = task_ptr->stack_check_list.next;  
71.       
72.     if (after_delete_list == &task_head) {  
73.                 after_delete_list = task_head.next;  
74.     }  
75.       
76.     list_delete(&task_ptr->stack_check_list);  
77.        
78.     #endif  
79.       
80.     RAW_CRITICAL_EXIT();  
81.    
82.     raw_sched();   
83.       
84.     return RAW_SUCCESS;  
85.  }  
86.    

    删除函数的动作其实是比较残忍的，因为此时你不清楚线程已经执行到哪一步了，拥有了那些资源，正在处理哪些资源，所以没事不要用这个函数。这里做的只是把任务从就绪队列、等待队列和阻塞队列清除出来，但是真正善后的工作要比这多得多，如果有兴趣，你看看linux的exit函数就明白了。

嵌入式操作系统内核原理和开发（等值block内存池设计）

 内存池设计是嵌入式系统的一个重要环节，之前我们也讨论过相关的内容。但是，看了rawos的代码之后，我觉得rawos的内存池设计更有特点。整个内存池的设计非常健壮，不但考虑了字节对齐的问题，而且还引入了等待调度机制，这是我所没有想到的。所以，在此我很愿意和大家分享这份优秀的代码。闲话不多说，我们看看rawos的mempool数据结构是什么样的，
[cpp] view plaincopy

1. typedef struct MEM_POOL  
2.   {  
3.     RAW_COMMON_BLOCK_OBJECT       common_block_obj;  
4.       
5.     /* Define the number of available memory blocks in the pool.  */  
6.     RAW_U32      raw_block_pool_available;  
7.     
8.     /* Define the head pointer of the available block pool.  */  
9.     RAW_U8      *raw_block_pool_available_list;  
10.     
11.   } MEM_POOL;  
12.     

    内存池的结构非常简单，主要包括了通用阻塞结构、block数值，block起始指针。内存池下面可以包括若干个block，每个block的大小都是相等的，同时block之间是通过链表串联在一起的，这个我们看了后面的代码就明白了。mempool的处理函数不多，就三个，初始化、申请、释放函数。
[cpp] view plaincopy

1. RAW_U16  raw_block_pool_create(MEM_POOL *pool_ptr, RAW_U8  *name_ptr, RAW_U32  block_size, RAW_VOID  *pool_start, RAW_U32  pool_size)  
2.   {  
3.     
4.     //MEM_POOL   *tail_ptr;                  /* Working block pool pointer  */  
5.     RAW_U32       blocks;                     /* Number of blocks in pool    */  
6.     RAW_U8        *block_ptr;                  /* Working block pointer       */  
7.     RAW_U8        *next_block_ptr;             /* Next block pointer          */  
8.     RAW_U8        *end_of_pool;                /* End of pool area            */  
9.     RAW_U8          block_align_mask;  
10.       
11.     #if (RAW_BLOCK_FUNCTION_CHECK > 0)  
12.        /* Check for invalid pool size.  */  
13.       
14.      if (pool_size < (block_size +  block_size) ) {  
15.           
16.         return RAW_BLOCK_SIZE_ERROR;  
17.     }  
18.     
19.     if (pool_ptr == 0) {  
20.           
21.         return RAW_NULL_OBJECT;  
22.     }  
23.       
24.     if (pool_start == 0) {  
25.           
26.         return RAW_NULL_POINTER;  
27.     }  
28.       
29.     #endif  
30.     
31.      block_align_mask = sizeof(void *) - 1u;  
32.     
33.     if (((RAW_U32)pool_start & block_align_mask)){                               
34.     
35.         return RAW_INVALID_ALIGN;  
36.     
37.     }  
38.        
39.     if ((pool_size & block_align_mask)) {     
40.           
41.         return RAW_INVALID_ALIGN;  
42.     }  
43.     
44.     if ((block_size & block_align_mask)) {     
45.           
46.         return RAW_INVALID_ALIGN;  
47.     }  
48.       
49.     /*Init the list*/  
50.     list_init(&pool_ptr->common_block_obj.block_list);  
51.     
52.     /* Setup the basic block pool fields.  */  
53.     pool_ptr ->common_block_obj.name =  name_ptr;  
54.     pool_ptr ->common_block_obj.block_way = 0;  
55.       
56.     /* Calculate the end of the pool's memory area.  */  
57.     end_of_pool =  (RAW_U8  *) pool_start + pool_size;  
58.     
59.     /* Walk through the pool area, setting up the available block list.  */  
60.     blocks =            0;  
61.     block_ptr =         (RAW_U8  *) pool_start;  
62.     next_block_ptr =    block_ptr + block_size;  
63.       
64.     while (next_block_ptr <= end_of_pool) {  
65.     
66.             blocks++;  
67.               
68.             if (next_block_ptr == end_of_pool) {  
69.                   
70.                 break;  
71.     
72.             }  
73.     
74.             /* Setup the link to the next block.  */  
75.             *((RAW_U8  * *) block_ptr) =  next_block_ptr;  
76.     
77.             /* Advance to the next block.  */  
78.             block_ptr =   next_block_ptr;  
79.     
80.             /* Update the next block pointer.  */  
81.             next_block_ptr =  block_ptr + block_size;  
82.     }  
83.     
84.     /* Set the last block's forward pointer to NULL.  */  
85.     *((RAW_U8  * *) block_ptr) =  0;  
86.     
87.     /* Save the remaining information in the pool control block.  */  
88.     pool_ptr ->raw_block_pool_available =  blocks;  
89.     
90.     
91.     pool_ptr ->raw_block_pool_available_list =  (RAW_U8  *) pool_start;  
92.     
93.     
94.     return RAW_SUCCESS;  
95.   }  
96.    

    上面就是内存池的创建函数，入参共有五个参数，分别是mempool结构、名称、block大小、pool起始地址、pool大小。函数基本内容如下所示，
     （1）判断内存池、指针参数合法性；
     （2）检验指针是否n字节对齐，n取决于地址的大小；
     （3）构建block链表，前后相连，最后一个block指向NULL指针；
     （4）将pool首地址赋值给raw_block_pool_available_list，函数返回。
[cpp] view plaincopy

1. RAW_U16 raw_block_allocate(MEM_POOL *pool_ptr, RAW_VOID **block_ptr, RAW_U32 wait_option)  
2.   {  
3.       
4.     RAW_U16             status;                               
5.     
6.     RAW_U8      *work_ptr;                        
7.     
8.     RAW_SR_ALLOC();  
9.     
10.     #if (RAW_BLOCK_FUNCTION_CHECK > 0)  
11.        
12.     if (pool_ptr == 0) {  
13.         return RAW_NULL_OBJECT;  
14.     }  
15.       
16.     if (block_ptr == 0) {  
17.           
18.         return RAW_NULL_POINTER;  
19.     }  
20.     
21.     if (raw_int_nesting) {  
22.     
23.         if (wait_option != RAW_NO_WAIT) {  
24.               
25.             return RAW_NOT_CALLED_BY_ISR;  
26.         }  
27.           
28.     }  
29.       
30.     #endif  
31.     
32.     RAW_CRITICAL_ENTER();  
33.     
34.     /* Determine if there is an available block.  */  
35.     if (pool_ptr ->raw_block_pool_available) {  
36.     
37.         /* Yes, a block is available.  Decrement the available count.  */  
38.         pool_ptr ->raw_block_pool_available--;  
39.     
40.         /* Pickup the current block pointer.  */  
41.         work_ptr =  pool_ptr ->raw_block_pool_available_list;  
42.     
43.         /* Return the first available block to the caller.  */  
44.         *((RAW_U8 **)block_ptr) =  work_ptr;  
45.     
46.         /* Modify the available list to point at the next block in the pool. */  
47.         pool_ptr ->raw_block_pool_available_list = *((RAW_U8 **)work_ptr);  
48.     
49.         /* Set status to success.  */  
50.         status =  RAW_SUCCESS;  
51.     }  
52.     
53.     /*if no block memory is available then do it depend wait_option*/  
54.     else {    
55.           
56.         if (wait_option == RAW_NO_WAIT) {   
57.             *((RAW_U8 **)block_ptr)     = 0;  
58.             RAW_CRITICAL_EXIT();  
59.             return RAW_NO_PEND_WAIT;  
60.         }    
61.     
62.         /*system is locked so task can not be blocked just return immediately*/  
63.         if (raw_sched_lock) {    
64.             *((RAW_U8 **)block_ptr)     = 0;  
65.             RAW_CRITICAL_EXIT();      
66.             return RAW_SCHED_DISABLE;      
67.         }  
68.       
69.         raw_pend_object(&pool_ptr->common_block_obj, raw_task_active, wait_option);  
70.     
71.         RAW_CRITICAL_EXIT();  
72.     
73.         raw_sched();                                               
74.     
75.         RAW_CRITICAL_ENTER();  
76.     
77.         *((RAW_U8 **)block_ptr)     = 0;  
78.         status = block_state_post_process(raw_task_active, block_ptr);  
79.           
80.         RAW_CRITICAL_EXIT();    
81.     
82.     }  
83.     
84.     
85.     return status;  
86.     
87.   }  
88.    

    和其他的内存池申请函数不一样，这里有一个wait_option选项。也就是说，如果当前没有合适的block，那么你可以选择等待处理。一旦别的线程释放内存，你就可以得到调度继续运行了。当然你也可以不等待，一旦寻找不到合适的block，立即返回为NULL。
[cpp] view plaincopy

1. RAW_U16 raw_block_release(MEM_POOL *pool_ptr, RAW_VOID *block_ptr)  
2.   {  
3.     LIST *block_list_head;  
4.       
5.     RAW_U8        *work_ptr;           /* Working block pointer   */  
6.     RAW_U8          need_schedule = 0;  
7.       
8.     RAW_SR_ALLOC();  
9.     
10.     #if (RAW_BLOCK_FUNCTION_CHECK > 0)  
11.        
12.     if (block_ptr == 0) {  
13.         return RAW_NULL_OBJECT;  
14.     }  
15.       
16.     if (pool_ptr == 0) {  
17.           
18.         return RAW_NULL_OBJECT;  
19.     }  
20.       
21.     #endif  
22.     
23.     block_list_head = &pool_ptr->common_block_obj.block_list;  
24.       
25.     RAW_CRITICAL_ENTER();  
26.       
27.     work_ptr =  ((RAW_U8 *) block_ptr);  
28.       
29.     if (is_list_empty(block_list_head)) {          
30.     
31.         /* Put the block back in the available list.  */  
32.         *((RAW_U8  **) work_ptr) =  pool_ptr ->raw_block_pool_available_list;  
33.     
34.         /* Adjust the head pointer.  */  
35.         pool_ptr ->raw_block_pool_available_list =  work_ptr;          
36.     
37.         /* Increment the count of available blocks.  */  
38.         pool_ptr ->raw_block_pool_available++;  
39.     }  
40.     
41.     else {  
42.           
43.         need_schedule = 1;  
44.         wake_send_msg(list_entry(block_list_head->next, RAW_TASK_OBJ, task_list),  block_ptr);     
45.     
46.     }  
47.      
48.     RAW_CRITICAL_EXIT();  
49.     
50.     if (need_schedule) {  
51.         raw_sched();  
52.     }  
53.       
54.     /* Return completion status.  */  
55.     return RAW_SUCCESS;  
56.   }  
57.    

    和其他的内存free函数不一样，这里的free函数多了一个wake_send_msg的功能。这也就是说，当然如果存在阻塞等待资源的线程，那么把资源送给该线程，同时把该线程唤醒，还要把need_schedule设置为1才可以。当然如果没有等待的线程，那么直接把内存插入到链表前面中即可，就是这么简单。

嵌入式操作系统内核原理和开发（改进的链表内存分配算法）

之前我自己也写过基于链表的内存分配算法，但是看了rawos的内存分配算法，还是感觉rawos写的要更好些。大家都知道，链表内存分配就是从链表中快速找到最合适的内存块分配给用户线程。因为这种分配是随机的，所以一般来说内存碎片是不可避免的。但是，我们在编写代码的时候还是应该注意内存合并的问题。这里我们为什么要介绍rawos的内存分配呢，还包括有这么几个原因，

    （1）整个内存链表采用循环链表的方法，使用起来简单可靠；

    （2）内存分配的时候所有节点都是连在一起的，通过标志数据判断当前数据是否已经分配；

    （3）如果当前没有合适的内存，可以选择等待；

    （4）代码充分考虑了合并和切分的问题；

    （5）在遍历内存的时候灵活处理了中断问题，可以及时响应中断，这个比我考虑得要周到很多；

    （6）代码注释丰富，只要多读几遍，是可以慢慢理解代码内容的。

    整个代码的结构清晰，共四个函数，分别是创建函数、内存查找函数、内存分配函数、内存释放函数。其中在内存分配和释放的时候，都会调用到内存查找函数。

[cpp] view plaincopy

1. RAW_U16  raw_byte_pool_create(RAW_BYTE_POOL_STRUCT *pool_ptr, RAW_U8 *name_ptr, RAW_VOID *pool_start, RAW_U32 pool_size)  
2.  {  
3.    
4.     RAW_U8  *block_ptr;                  /* Working block pointer       */  
5.     RAW_U8   byte_align_mask;  
6.       
7.     #if (RAW_BYTE_FUNCTION_CHECK > 0)  
8.    
9.      if (pool_ptr == 0) {  
10.               
11.          return RAW_NULL_POINTER;  
12.      }  
13.    
14.      if (pool_start == 0) {  
15.               
16.          return RAW_NULL_POINTER;  
17.      }  
18.    
19.      /* Check for invalid pool size.  */  
20.      if (pool_size < RAW_BYTE_POOL_MIN) {  
21.               
22.          return RAW_BYTE_SIZE_ERROR;  
23.                   
24.      }  
25.    
26.     #endif  
27.    
28.      byte_align_mask = sizeof(void *) - 1u;  
29.    
30.     /*pool_start needs 4 bytes aligned*/  
31.     if (((RAW_U32)pool_start & byte_align_mask)){                               
32.    
33.         return RAW_INVALID_ALIGN;  
34.    
35.     }  
36.    
37.     /*pool_size needs 4 bytes aligned*/  
38.     if ((pool_size & byte_align_mask)) {     
39.           
40.         return RAW_INVALID_ALIGN;  
41.     }  
42.    
43.  /*Init the list*/  
44.     list_init(&pool_ptr->common_block_obj.block_list);  
45.           
46.     /* Setup the basic byte pool fields.  */  
47.     pool_ptr ->common_block_obj.name =  name_ptr;  
48.     pool_ptr ->common_block_obj.block_way = 0;  
49.     pool_ptr ->raw_byte_pool_search =  (RAW_U8  *) pool_start;  
50.     pool_ptr ->raw_byte_pool_owner = 0;  
51.    
52.     /* Initially, the pool will have two blocks.  One large block at the  
53.        beginning that is available and a small allocated block at the end 
54.        of the pool that is there just for the algorithm.  Be sure to count 
55.        the available block's header in the available bytes count.  */  
56.     pool_ptr ->raw_byte_pool_available =   pool_size - sizeof(void *) - sizeof(RAW_U32);  
57.     pool_ptr ->raw_byte_pool_fragments =    2;  
58.    
59.     /* Calculate the end of the pool's memory area.  */  
60.     block_ptr =  ((RAW_U8  *) pool_start) + (RAW_U32) pool_size;  
61.    
62.     /* Backup the end of the pool pointer and build the pre-allocated block.  */  
63.     block_ptr =  block_ptr - sizeof(RAW_U32);  
64.     *((RAW_U32 *) block_ptr) =  RAW_BYTE_BLOCK_ALLOC;  
65.     block_ptr =  block_ptr - sizeof(RAW_U8  *);  
66.     *((RAW_U8  * *) block_ptr) =  pool_start;  
67.    
68.     /* Now setup the large available block in the pool.  */  
69.     *((RAW_U8  * *) pool_start) =  block_ptr;  
70.     block_ptr =  (RAW_U8  *) pool_start;  
71.     block_ptr =  block_ptr + sizeof(RAW_U8  *);  
72.     *((RAW_U32 *) block_ptr) =  RAW_BYTE_BLOCK_FREE;  
73.    
74.     
75.      return RAW_SUCCESS;  
76.  }  
77.    

    内存池的创建还是比较简单的，基本的步骤如下所示，

    （1）验证参数的合法性，比如是否是NULL指针、是否对齐；

    （2）初始化内存池的基本参数，比如说名称、默认阻塞结构、入口地址、剩余大小等等；

    （3）构建两个block节点，前面是free节点，后面是alloc节点，两个节点构成循环节点。每个节点有三个部分组成，分别是下一跳地址、标志、buffer。

[cpp] view plaincopy

1. static void *raw_byte_pool_search(RAW_BYTE_POOL_STRUCT *pool_ptr, RAW_U32 memory_size)  
2.  {  
3.    
4.     RAW_U8  *  current_ptr;                /* Current block pointer      */  
5.     RAW_U8  *  next_ptr;                   /* Next block pointer         */  
6.     RAW_U32     available_bytes;            /* Calculate bytes available  */  
7.     RAW_U32     examine_blocks;             /* Blocks to be examined      */  
8.    
9.     RAW_SR_ALLOC();  
10.       
11.     /* Disable interrupts.  */  
12.     RAW_CRITICAL_ENTER();  
13.    
14.      /* First, determine if there are enough bytes in the pool.  */  
15.      if (memory_size >= pool_ptr ->raw_byte_pool_available) {  
16.      
17.         /* Restore interrupts.  */  
18.         RAW_CRITICAL_EXIT();  
19.          /* Not enough memory, return a NULL pointer.  */  
20.          return   0;  
21.      }  
22.    
23.      /* Walk through the memory pool in search for a large enough block.  */  
24.      current_ptr =      pool_ptr ->raw_byte_pool_search;  
25.      examine_blocks =   pool_ptr ->raw_byte_pool_fragments + 1;  
26.      available_bytes =  0;  
27.           
28.      do {  
29.       
30.          /* Check to see if this block is free.  */  
31.          if (*((RAW_U32 *) (current_ptr + sizeof(RAW_U8  *))) == RAW_BYTE_BLOCK_FREE) {  
32.            
33.    
34.              /* Block is free, see if it is large enough.  */  
35.    
36.              /* Pickup the next block's pointer.  */  
37.              next_ptr =  *((RAW_U8  * *) current_ptr);  
38.    
39.              /* Calculate the number of byte available in this block.  */  
40.              available_bytes =  next_ptr - current_ptr - sizeof(RAW_U8  *) - sizeof(RAW_U32);  
41.    
42.              /* If this is large enough, we are done because our first-fit algorithm 
43.                 has been satisfied!  */  
44.              if (available_bytes >= memory_size) {  
45.                
46.                  /* Find the suitable position */  
47.                  break;  
48.              }  
49.                           
50.              else {  
51.                
52.                  /* Clear the available bytes variable.  */  
53.                  available_bytes =  0;  
54.    
55.                  /* Not enough memory, check to see if the neighbor is  
56.                     free and can be merged.  */  
57.                  if (*((RAW_U32 *) (next_ptr + sizeof(RAW_U8  *))) == RAW_BYTE_BLOCK_FREE) {  
58.                    
59.                      /* Yes, neighbor block can be merged!  This is quickly accomplished 
60.                         by updating the current block with the next blocks pointer.  */  
61.                      *((RAW_U8  * *) current_ptr) =  *((RAW_U8  * *) next_ptr);  
62.    
63.                      /* Reduce the fragment number, and does not need to increase  available bytes since  
64.                          they are already there*/  
65.                            
66.                      pool_ptr ->raw_byte_pool_fragments--;  
67.    
68.                      /* Update the search pointer, if it is involved */  
69.                      if (pool_ptr ->raw_byte_pool_search ==  next_ptr) {  
70.                          pool_ptr ->raw_byte_pool_search =  current_ptr;  
71.                      }  
72.                                           
73.                  }  
74.                  else {  
75.                    
76.                      /* Neighbor is not free so get to the next search point*/  
77.                      current_ptr =  *((RAW_U8  * *) next_ptr);  
78.    
79.                      /* Reduse the examined block since we have skiped one search */  
80.                      if (examine_blocks) {  
81.                          examine_blocks--;  
82.                      }  
83.                  }  
84.              }  
85.          }  
86.          else  
87.          {  
88.    
89.              /* Block is not free, move to next block.  */  
90.              current_ptr = *((RAW_U8  * *) current_ptr);  
91.          }   
92.    
93.          /* finish one block search*/  
94.          if (examine_blocks) {  
95.              examine_blocks--;  
96.          }  
97.            
98.         /* Restore interrupts temporarily.  */  
99.         RAW_CRITICAL_EXIT();  
100.    
101.         /* Disable interrupts.  */  
102.        RAW_CRITICAL_ENTER();  
103.    
104.          /* Determine if anything has changed in terms of pool ownership.  */  
105.          if (pool_ptr ->raw_byte_pool_owner != raw_task_active)  
106.          {  
107.    
108.              /* Pool changed ownership during interrupts.so we reset the search*/  
109.                    
110.              current_ptr =      pool_ptr ->raw_byte_pool_search;  
111.              examine_blocks =   pool_ptr ->raw_byte_pool_fragments + 1;  
112.    
113.              /* Setup our ownership again.  */  
114.              pool_ptr ->raw_byte_pool_owner =   raw_task_active;  
115.          }  
116.                   
117.      } while (examine_blocks);  
118.    
119.      /* Determine if a block was found.  If so, determine if it needs to be 
120.         split.  */  
121.      if (available_bytes) {  
122.        
123.          /* Do we need to split this block if this is big enough.*/  
124.          if ((available_bytes - memory_size) >= ((RAW_U32) RAW_BYTE_BLOCK_MIN)) {  
125.            
126.              /* Split the block.  */  
127.              next_ptr =  current_ptr + memory_size + sizeof(RAW_U8  *) + sizeof(RAW_U32);  
128.    
129.              /* Setup the new free block.  */  
130.              *((RAW_U8  * *) next_ptr) =  *((RAW_U8  * *) current_ptr);  
131.              *((RAW_U32 *) (next_ptr + sizeof(RAW_U8  *))) =  RAW_BYTE_BLOCK_FREE;  
132.    
133.              /* Increase the total fragment counter.  */  
134.              pool_ptr ->raw_byte_pool_fragments++;  
135.    
136.              /* Update the current pointer to point at the newly created block.  */  
137.              *((RAW_U8  * *) current_ptr) = next_ptr;  
138.    
139.              /* Set available equal to memory size for subsequent calculation.  */  
140.              available_bytes =  memory_size;  
141.          }  
142.    
143.         /* In any case, mark the current block as allocated.  */  
144.         *((RAW_U32 *) (current_ptr + sizeof(RAW_U8  *))) =  RAW_BYTE_BLOCK_ALLOC;  
145.    
146.         /* Reduce the number of available bytes in the pool.  */  
147.         pool_ptr ->raw_byte_pool_available =  pool_ptr ->raw_byte_pool_available - available_bytes  
148.                                        - sizeof(RAW_U8  *) - sizeof(RAW_U32);  
149.    
150.         /* Adjust the pointer for the application.  */  
151.         current_ptr =  current_ptr + sizeof(RAW_U8  *) + sizeof(RAW_U32);  
152.           
153.      }  
154.           
155.      else {  
156.               
157.          /* Set current pointer to NULL to indicate nothing was found.  */  
158.          current_ptr =  0;  
159.      }  
160.    
161.    
162.     /* Restore interrupts temporarily.  */  
163.     RAW_CRITICAL_EXIT();  
164.    
165.     /* Return the searched result*/  
166.     return current_ptr;  
167.  }  
168.    

    这个内存查找函数是这四个函数中最难的那个函数。看上去内容很多，其实我们可以分成两个部分分析，其中do～while的这个部分就是负责查找合适的内存块，后面的if～else部分是对分配的节点进行后续处理，下面我们可以详细来看看，

    （1）验证剩余空间是否满足条件，不满足立即返回；

    （2）遍历所有的block节点，查找合适的节点，

            a、如果寻找到合适的节点，那么立即跳出循环；

            b、如果没有寻找到合适的节点，可以做一些额外的工作，比如说对相连的free节点进行合并；

            c、循环的结束条件是examine_blocks全部遍历结束，当然如果发现raw_byte_pool_owner不为当前线程，那么一切重来；

    （3）对于获得的block节点，同样有两种方法处理，

            a、如果除去分配的空间，剩下的节点空间仍然很多，那么可以把当前节点拆分成两个节点进行处理；

            b、如果剩下的空间本身就很有限，那么全部分配给当前线程算了。

    （4）函数返回，current_ptr包含了那个分配好的地址。

[cpp] view plaincopy

1. RAW_U16  raw_byte_allocate(RAW_BYTE_POOL_STRUCT *pool_ptr, RAW_VOID **memory_ptr,   
2.                                      RAW_U32 memory_size,  RAW_U32 wait_option)  
3.  {  
4.    
5.     RAW_U16        status;                 /* Return status              */  
6.     RAW_U8         *work_ptr;               /* Working byte pointer       */  
7.     RAW_TASK_OBJ  *current_work_task;  
8.       
9.     RAW_SR_ALLOC();  
10.    
11.     #if (RAW_BYTE_FUNCTION_CHECK > 0)  
12.    
13.      if (pool_ptr == 0) {  
14.               
15.          return RAW_NULL_POINTER;  
16.      }  
17.    
18.    
19.      if (memory_ptr == 0) {  
20.               
21.          return RAW_NULL_POINTER;  
22.      }  
23.    
24.      if (raw_int_nesting) {  
25.    
26.         if (wait_option != RAW_NO_WAIT)  
27.             return RAW_NOT_CALLED_BY_ISR;  
28.    
29.     }  
30.        
31.     #endif  
32.       
33.      /* align the memory size to 4 byte*/  
34.           
35.      memory_size = ((memory_size & (~3u)) +4u);  
36.    
37.     current_work_task = raw_task_active;  
38.    
39.      /* Disable interrupts.  */  
40.     RAW_CRITICAL_ENTER();  
41.    
42.       /* Loop to handle cases where the owner of the pool changed.  */  
43.      do {  
44.        
45.         /* Indicate that this thread is the current owner.  */  
46.         pool_ptr ->raw_byte_pool_owner =  current_work_task;  
47.    
48.         /* Restore interrupts.  */  
49.         RAW_CRITICAL_EXIT();  
50.       
51.         /*Search for free memory*/  
52.         work_ptr =  raw_byte_pool_search(pool_ptr, memory_size);  
53.    
54.         /* Disable interrupts.  */  
55.         RAW_CRITICAL_ENTER();  
56.           
57.         /*if raw_byte_pool_owner changed and we have not got memory yet, continue tom do search*/  
58.      } while ((!work_ptr) && (pool_ptr ->raw_byte_pool_owner != current_work_task));  
59.    
60.           
61.    
62.      /* Determine if memory was found.  */  
63.      if (work_ptr) {  
64.               
65.         /* Copy the pointer into the return destination.  */  
66.         *memory_ptr =  (RAW_U8  *) work_ptr;  
67.           
68.          RAW_CRITICAL_EXIT();  
69.         /* Set the status to success.  */  
70.         return  RAW_SUCCESS;  
71.            
72.      }  
73.           
74.      else {  
75.    
76.          if (wait_option) {  
77.    
78.             /*system is locked so task can not be blocked just return immediately*/  
79.             if (raw_sched_lock) {   
80.                   
81.                 *memory_ptr   = 0;  
82.                 RAW_CRITICAL_EXIT();      
83.                 return RAW_SCHED_DISABLE;      
84.             }  
85.    
86.             raw_task_active->msg = (RAW_VOID *)memory_size;  
87.             raw_pend_object(&pool_ptr->common_block_obj, raw_task_active, wait_option);  
88.               
89.          }  
90.                   
91.         else {  
92.                   
93.             *memory_ptr   = 0;  
94.             RAW_CRITICAL_EXIT();  
95.             /* Immediate return, return error completion.  */  
96.             return RAW_NO_MEMORY;  
97.          }  
98.      }  
99.    
100.      /* Restore interrupts.  */  
101.     RAW_CRITICAL_EXIT();  
102.    
103.     raw_sched();  
104.    
105.     RAW_CRITICAL_ENTER();  
106.       
107.     *memory_ptr   = 0;  
108.     status = block_state_post_process(raw_task_active, memory_ptr);  
109.       
110.     RAW_CRITICAL_EXIT();    
111.       
112.      return  status;  
113.  }  
114.    

    和内存查找函数相比，内存分配函数就简单多了，

    （1）判断参数的合法性；

    （2）循环查找链表节点，寻找合适的内存块，注意循环的跳出条件，即work_ptr==NULL且没有其他线程的干扰；

    （3）如果寻找到了合适的节点，那么没有问题，反之需要根据wait_option判断是否需要把自己挂起在等待队列上；

    （4）线程再次得到运行的机会，memory_ptr中包含了内存地址，函数返回。

[cpp] view plaincopy

1. RAW_U16  raw_byte_release(RAW_BYTE_POOL_STRUCT *pool_ptr, void  *memory_ptr)  
2.  {  
3.     RAW_U8  *work_ptr;           /* Working block pointer      */  
4.       
5.     LIST                                         *iter;  
6.     LIST                                         *iter_temp;  
7.     LIST                                         *byte_head_ptr;  
8.     RAW_TASK_OBJ                         *task_ptr;  
9.    
10.     RAW_U8 need_sche = 0;  
11.       
12.     RAW_SR_ALLOC();  
13.    
14.    
15.     #if (RAW_BYTE_FUNCTION_CHECK > 0)  
16.    
17.     if (pool_ptr == 0) {  
18.               
19.          return RAW_NULL_POINTER;  
20.      }  
21.    
22.      if (memory_ptr == 0) {  
23.               
24.          return RAW_NULL_POINTER;  
25.      }  
26.           
27.     #endif  
28.       
29.     byte_head_ptr = &pool_ptr->common_block_obj.block_list;  
30.       
31.     /* Back off the memory pointer to pickup its header.  */  
32.     work_ptr = (RAW_U8  *) memory_ptr - sizeof(RAW_U8  *) - sizeof(RAW_U32);  
33.                   
34.     /* Disable interrupts.  */  
35.     RAW_CRITICAL_ENTER();  
36.    
37.     /* Indicate that this thread is the current owner.  */  
38.     pool_ptr ->raw_byte_pool_owner =  raw_task_active;  
39.    
40.      /* Release the memory.*/  
41.      *((RAW_U32 *) (work_ptr + sizeof(RAW_U8  *))) =  RAW_BYTE_BLOCK_FREE;  
42.    
43.      /* Update the number of available bytes in the pool.  */  
44.      pool_ptr ->raw_byte_pool_available =    
45.        pool_ptr ->raw_byte_pool_available + (*((RAW_U8  * *) (work_ptr)) - work_ptr);  
46.    
47.      /* Set the pool search value appropriately.  */  
48.      pool_ptr ->raw_byte_pool_search =  work_ptr;  
49.    
50.     iter = byte_head_ptr->next;  
51.       
52.      while (iter != byte_head_ptr) {  
53.    
54.         iter_temp = iter->next;  
55.         task_ptr =  list_entry(iter, RAW_TASK_OBJ, task_list);  
56.           
57.         RAW_CRITICAL_EXIT();  
58.          /* See if the request can be satisfied.  */  
59.          work_ptr =  raw_byte_pool_search(pool_ptr, (RAW_U32)task_ptr->msg);     
60.             RAW_CRITICAL_ENTER();  
61.     
62.           /* If there is not enough memory, break this loop!  */  
63.           if (!work_ptr) {  
64.              break;  
65.           }  
66.    
67.             wake_send_msg(task_ptr, (RAW_VOID *)work_ptr);    
68.         need_sche = 1;  
69.         iter = iter_temp;  
70.           
71.      }  
72.    
73.     RAW_CRITICAL_EXIT();  
74.    
75.     if (need_sche) {  
76.           
77.         raw_sched();  
78.           
79.     }  
80.       
81.     return RAW_SUCCESS;  
82.           
83.  }  
84.    

    内存释放后，本来我们只需要把内存节点的标志设置为RAW_BYTE_BLOCK_FREE即可。可是，我们还需要判断当前是否存在等待唤醒的线程，是否可以为等待线程寻找到合适的内存节点，整个函数基本流程如下所示，

    （1）判断参数合法性；

    （2）将当前block节点设置为可用，调整pool中的参数数据；

    （3）遍历等待线程，并为之查找到合适的节点，寻找到节点跳出，遍历完所有等待节点也跳出；   

    （4）如果有线程被唤醒，那么需要重新调度，否则函数返回。

嵌入式操作系统内核原理和开发（优先级的修改）

之前在和rawos作者的闲聊中，rawos作者认为实时操作系统中最大的特色就是互斥量的问题。一开始，我对这个看法其实是有保留意见的，直到我看到了修改优先级的相关代码，才开始对作者的看法有了很大的认同感。实话说，在嵌入式实时系统中修改优先级是一个很复杂的事情，为什么呢，因为这其中涉及到了互斥量的问题。我们大家都知道，在嵌入式系统中优先级反转是一个绕不去的砍。低优先级的任务因为获得了互斥量因而比高优先级的任务获得了更多的运行机会，这从根本上违背了实时系统设计的初衷。所以，人们为了解决除了这一问题，提出了优先级互斥量和优先级继承两种方法。

 

    优先级互斥量的办法比较简单，ucos也是这么做的。我们在分配一个互斥量的时候，也给这个互斥量分配一定的优先级。任何获得该互斥量的任务都会把自己的优先级修改为互斥量的优先级，这样保证了获得该优先级的任务可以在最短的时间内完成，尽快释放资源。但是，这也会导致一个问题，那就是该互斥量需要占用一个优先级，而且比此优先级高的任务也没办法获得该互斥量。另外一种方法就是优先级继承的方法，简单一点说就是任何对阻塞线程优先级的修改，都会导致拥有此互斥量的任务进行优先级的修改。闲话不多说，我们看看rawos上面的代码是怎么描述的，

[cpp] view plaincopy

1. RAW_U16 raw_task_priority_change (RAW_TASK_OBJ *task_ptr, RAW_U8 new_priority, RAW_U8 *old_priority)  
2. {  
3.     RAW_U8 ret_pri;  
4.     RAW_U16 error;  
5.       
6.     RAW_SR_ALLOC();  
7.   
8.     #if (RAW_TASK_FUNCTION_CHECK > 0)  
9.       
10.     if (task_ptr == 0) {  
11.           
12.         return RAW_NULL_OBJECT;  
13.     }  
14.   
15.     if (old_priority == 0) {  
16.           
17.         return RAW_NULL_OBJECT;  
18.     }  
19.       
20.     #endif        
21.   
22.     /*Idle task is not allowed to change priority*/  
23.     if (task_ptr->priority >= IDLE_PRIORITY) {  
24.           
25.         return RAW_CHANGE_PRIORITY_NOT_ALLOWED;  
26.     }  
27.       
28.    /*Not allowed change to idle priority*/  
29.     if (new_priority == IDLE_PRIORITY) {               
30.   
31.         return RAW_CHANGE_PRIORITY_NOT_ALLOWED;  
32.     }  
33.   
34.       
35.     RAW_CRITICAL_ENTER();  
36.   
37.     #if (CONFIG_RAW_MUTEX > 0)  
38.     ret_pri = chg_pri_mutex(task_ptr, new_priority, &error);  
39.   
40.     if (error != RAW_SUCCESS) {  
41.         goto error_exit;  
42.     }  
43.   
44.     task_ptr->bpriority = new_priority;  
45.     new_priority = ret_pri;  
46.       
47.     #else  
48.       
49.     task_ptr->bpriority = new_priority;  
50.     #endif  
51.   
52.     *old_priority = task_ptr->priority;  
53.   
54.     error = change_interal_task_priority(task_ptr, new_priority);  
55.       
56.     if (error != RAW_SUCCESS) {  
57.         goto error_exit;  
58.     }  
59.   
60.     RAW_CRITICAL_EXIT();  
61.       
62.     do_possible_sche();    
63.           
64.     return RAW_SUCCESS;  
65.       
66.     error_exit:  
67.     RAW_CRITICAL_EXIT();  
68.     return error;  
69.       
70. }  

    这个函数是系统本身提供的一个函数，内容不算少，但是重点可以放在两个子函数上面。一个部分是函数chg_pri_mutex，另外一个函数是change_interal_task_priority。前者判断当前优先级是否可以修改，后者判断如何对当前的任务进行修改，后面我们会看到会对这个问题有一个详细的说明。

[cpp] view plaincopy

1. RAW_U8 chg_pri_mutex(RAW_TASK_OBJ *tcb, RAW_U8 priority, RAW_U16 *error)  
2. {  
3.     RAW_MUTEX   *mtxcb;  
4.     RAW_U8  hi_pri, low_pri, pri;  
5.     RAW_TASK_OBJ *first_block_task;  
6.     LIST *block_list_head;  
7.       
8.     hi_pri  = priority;  
9.     low_pri = 0;  
10.       
11.     mtxcb = (RAW_MUTEX  *)(tcb->block_obj);  
12.       
13.     if (mtxcb) {  
14.   
15.         /*if it is blocked on mutex*/  
16.         if (mtxcb->common_block_obj.object_type == RAW_MUTEX_OBJ_TYPE) {  
17.               
18.             if (mtxcb->policy == RAW_MUTEX_CEILING_POLICY) {  
19.                 pri = mtxcb->ceiling_prio;  
20.                   
21.                 if (pri > low_pri) {  
22.                     low_pri = pri;  
23.                 }  
24.             }  
25.         }  
26.     }  
27.   
28.     /* Locked Mutex */  
29.     pri = hi_pri;  
30.     for (mtxcb = tcb->mtxlist; mtxcb != 0; mtxcb = mtxcb->mtxlist) {  
31.         switch (mtxcb->policy) {  
32.               
33.           case RAW_MUTEX_CEILING_POLICY:  
34.             pri = mtxcb->ceiling_prio;  
35.             if ( pri > low_pri ) {  
36.                 low_pri = pri;  
37.             }  
38.             break;  
39.               
40.           case RAW_MUTEX_INHERIT_POLICY:  
41.               
42.             block_list_head = &mtxcb->common_block_obj.block_list;  
43.               
44.             if (!is_list_empty(block_list_head)) {  
45.                 first_block_task = list_entry(block_list_head->next, RAW_TASK_OBJ, task_list);   
46.                 pri = first_block_task->priority;  
47.             }  
48.               
49.             break;  
50.               
51.           default:  
52.             /* nothing to do */  
53.             break;  
54.         }  
55.         if ( pri < hi_pri ) {  
56.             hi_pri = pri;  
57.         }  
58.     }  
59.   
60.     if (priority < low_pri) {  
61.           
62.         *error = RAW_EXCEED_CEILING_PRIORITY;  
63.         return RAW_EXCEED_CEILING_PRIORITY;  
64.     }  
65.   
66.     *error = RAW_SUCCESS;  
67.     return hi_pri;  
68. }  

    上面的代码还是比较复杂的，我们看到其实任务的优先级不是可以随便修改的，因为当前任务可能已经占有了许多互斥量资源，而这些互斥量资源其实是有约束条件的。如果占有的互斥量类型是那种带优先级的互斥量，那么必须找出的那个最低优先级的互斥量，至少修改的任务优先级不能比它高。剩下的工作就是在继承优先级的*下寻找到最高的优先级，仅此而已。

[cpp] view plaincopy

1. RAW_U16 change_interal_task_priority(RAW_TASK_OBJ *task_ptr, RAW_U8 new_priority)  
2. {  
3.     RAW_U8 old_pri;  
4.   
5.     switch (task_ptr->task_state) {  
6.         case RAW_RDY:  
7.               
8.             remove_ready_list(&raw_ready_queue, task_ptr);  
9.             task_ptr->priority = new_priority;  
10.               
11.             if (task_ptr == raw_task_active) {  
12.                 add_ready_list_head(&raw_ready_queue, task_ptr);  
13.                   
14.             }  
15.               
16.             else {  
17.               
18.                 add_ready_list_end(&raw_ready_queue, task_ptr);  
19.             }  
20.       
21.             break;  
22.   
23.         case RAW_DLY:                             /* Nothing to do except change the priority in the OS_TCB */  
24.         case RAW_SUSPENDED:  
25.         case RAW_DLY_SUSPENDED:  
26.               
27.             task_ptr->priority = new_priority;                        /* Set new task priority*/  
28.               
29.             break;  
30.   
31.         case RAW_PEND:  
32.         case RAW_PEND_TIMEOUT:  
33.         case RAW_PEND_SUSPENDED:  
34.         case RAW_PEND_TIMEOUT_SUSPENDED:  
35.             old_pri = task_ptr->priority;  
36.             task_ptr->priority = new_priority;    
37.             change_pend_list_priority(task_ptr);  
38.               
39.             #if (CONFIG_RAW_MUTEX > 0)  
40.             mtx_chg_pri(task_ptr, old_pri);  
41.             #endif  
42.               
43.             break;  
44.   
45.         default:  
46.               
47.             #if (CONFIG_RAW_ASSERT > 0)  
48.             RAW_ASSERT(0);  
49.             #endif  
50.               
51.             return RAW_STATE_UNKNOWN;  
52.     }  
53.   
54.     return RAW_SUCCESS;  
55.   
56. }  

    前面，我们说到了优先级的修改函数，而change_interal_task_priority就是完成这一功能的函数。当然，我们需要针对目前任务的状态对任务的优先级进行修改，如果任务此时正在运行或者延迟运行，那么还好办，关键是如果此时任务已经阻塞了，那么考虑的情况就多了。

[cpp] view plaincopy

1. RAW_VOID mtx_chg_pri(RAW_TASK_OBJ *tcb, RAW_U8 oldpri)  
2. {  
3.     RAW_MUTEX       *mtxcb;  
4.     RAW_TASK_OBJ    *mtxtsk;  
5.   
6.     mtxcb = (RAW_MUTEX  *)(tcb->block_obj);  
7.       
8.     if (mtxcb->common_block_obj.object_type == RAW_MUTEX_OBJ_TYPE) {  
9.           
10.         if (mtxcb->policy == RAW_MUTEX_INHERIT_POLICY) {  
11.             mtxtsk = mtxcb->mtxtsk;  
12.               
13.             if (mtxtsk->priority > tcb->priority) {  
14.                 /* Since the highest priority of the lock wait task 
15.                  became higher, raise the lock get task priority 
16.                 higher */  
17.                 change_interal_task_priority(mtxtsk, tcb->priority);  
18.             }  
19.   
20.             /*the highest priority task blocked on this mutex may decrease priority so reset the mutex task priority*/  
21.             else if(mtxtsk->priority == oldpri) {  
22.   
23.                 release_mutex(mtxtsk, 0);  
24.             }  
25.               
26.         }  
27.     }  
28.   
29. }  

    mtx_chg_pri函数此时考虑的不光是它自己优先级的问题，它还需要考虑此时占有互斥量的这个任务优先级该怎么修改。我们进一步看看release_mutex下面做了哪些工作。

[cpp] view plaincopy

1. static RAW_VOID release_mutex(RAW_TASK_OBJ *tcb, RAW_MUTEX *relmtxcb)  
2. {  
3.     RAW_MUTEX   *mtxcb, **prev;  
4.     RAW_U8  newpri, pri;  
5.     RAW_TASK_OBJ *first_block_task;  
6.     LIST *block_list_head;  
7.       
8.     /* (B) The base priority of task */  
9.     newpri = tcb->bpriority;  
10.   
11.     /* (A) The highest priority in mutex which is locked */  
12.     pri = newpri;  
13.     prev = &tcb->mtxlist;  
14.     while ((mtxcb = *prev) != 0) {  
15.         if (mtxcb == relmtxcb) {  
16.             /* Delete from list */  
17.             *prev = mtxcb->mtxlist;  
18.             continue;  
19.         }  
20.   
21.         switch (mtxcb->policy) {  
22.           case RAW_MUTEX_CEILING_POLICY:  
23.             pri = mtxcb->ceiling_prio;  
24.             break;  
25.               
26.           case RAW_MUTEX_INHERIT_POLICY:  
27.               
28.             block_list_head = &mtxcb->common_block_obj.block_list;  
29.               
30.             if (!is_list_empty(block_list_head)) {  
31.                 first_block_task = list_entry(block_list_head->next, RAW_TASK_OBJ, task_list);   
32.                 pri = first_block_task->priority;  
33.             }  
34.               
35.             break;  
36.               
37.           default:  
38.             break;  
39.         }  
40.         if (newpri > pri) {  
41.             newpri = pri;  
42.         }  
43.   
44.         prev = &mtxcb->mtxlist;  
45.     }  
46.   
47.     if ( newpri != tcb->priority ) {  
48.         /* Change priority of lock get task */  
49.         change_interal_task_priority(tcb, newpri);  
50.     }  
51.       
52. }  

    这个函数的工作就是修改那个获得互斥量的任务的优先级的，在寻找到最高优先级之后，那么又需要调用change_internall_task_priority函数了。有过递归函数编写经验的朋友就知道了，这其实就是一个典型的递归函数。change_internall_task_priority函数调用到release_mutex，然而release_mutex又调用到change_internall_task_priority，感觉上没完没了了，其实不是这样。递归函数都是需要出口的，这个函数的出口就是change_internall_task_priority，一切等到获得的那个任务不再是阻塞任务为止，整个修改的过程就结束了。当然，任务优先级恢复的工作也是非常麻烦的，不管是带优先级的互斥量还是优先级继承机制的互斥量，额外的优先级修改和计算都是必须的，不知道我讲清楚了没有。rawos在互斥量的最大进步就是进一步说明了拥有多互斥量的任务该如何修改优先级，当然了，函数迭代的过程多了堆栈使用的空间也多了，有没有溢出的危险，这是我们需要考虑的另外一个重要因素。

嵌入式操作系统内核原理和开发（总结篇）

  很多朋友都喜欢嵌入式操作系统的内容，但是如何实现和仿真这样一个系统一直是困扰我们的难题。现在郑重推荐一下raw-os系统，在我们的博客当中也多次提到了这个代码，希望大家可以多多阅读，不断加深对os的认识。如果有可能，大家可以到 http://ishare.iask.sina.com.cn/f/33440944.html这里下载raw-os的vc6.0版本，单步调试每一行代码，肯定会有所收获。

（01） 嵌入式操作系统内核原理和开发（优先级的修改）  

（02）嵌入式操作系统内核原理和开发（改进的链表内存分配算法）

（03）嵌入式操作系统内核原理和开发（等值block内存池设计）

（04）嵌入式操作系统内核原理和开发（线程状态）

（05）嵌入式操作系统内核原理和开发（实时系统中的定时器）

（06）嵌入式操作系统内核原理和开发（延时操作）

（07）嵌入式操作系统内核原理和开发（实时调度）

（08）嵌入式操作系统内核原理和开发（消息队列）

（09）嵌入式操作系统内核原理和开发（事件）

（10）嵌入式操作系统内核原理和开发（互斥量）

（11）嵌入式操作系统内核原理和开发（信号量）

（12）嵌入式操作系统内核原理和开发（最快、最优、最差内存分配算法）

（13）嵌入式操作系统内核原理和开发（基于链表节点的内存分配算法）

（14）嵌入式操作系统内核原理和开发（固定内存分配算法）

（15）嵌入式操作系统内核原理和开发（内存分配算法）

（16）嵌入式操作系统内核原理和开发（头文件调整）

（17）嵌入式操作系统内核原理和开发（改进型优先级调度）

（18）嵌入式操作系统内核原理和开发（通用优先级调度）

（19）嵌入式操作系统内核原理和开发（多线程轮转）

（20）嵌入式操作系统内核原理和开发（任务创建和堆栈溢出检查）

（21）嵌入式操作系统内核原理和开发（线程切换）

（22）嵌入式操作系统内核原理和开发（系统中断仿真）

（23）嵌入式操作系统内核原理和开发（基础）

（24）嵌入式操作系统内核原理和开发（地址空间）

（25）嵌入式操作系统内核原理和开发（中断）

（26）嵌入式操作系统内核原理和开发（cpu的那些事）

（27）嵌入式操作系统内核原理和开发（开篇）