Binary Search Tree Iterator(中序遍历)

要了解什么是实时操作系统，它与非实时操作系统有什么区别，必须要知道如下这些概念。

Foreground/Background System

中断是操作系统中的重要概念，也是芯片设计中核心的东西。中断处理是由中断控制器产生中断信号，到达处理器后由处理器对其进行处理的过程，中断的特点是能够打断处理器的正常执行转而去执行更重要的中断处理程序。而这里的Forground则指代中断处理的过程，而Background则指处理器正常运行的过程。如下图所示：

临界区（Critical Region）

临界区代码不可被中断，因此在进入临界区之前必须关中断，执行结束后才能开中断

资源

资源是指一切能被任务使用的东西，可以是I/O设备，打印机，键盘，显示器，或这是数组，变量等。

共享资源

共享资源是指能被多个任务所使用的资源，通常任务对资源具有独占性，一经获取，就不能被另一个任务获取，直到资源被释放。

任务

这里的任务就是指进程，UCOS中进程由五种状态：DORMANT，READY，RUNNING，WAITING，ISR

DORMANt:这个状态指任务已经被放入内存，但还不可运行
READY:进程可运行，但还未被调度
RUNNING:进程正在运行
WAITING:进程因等待某个资源可用而进入此状态并让出处理器使用权
ISR:进程在执行时被中断则进入这个状态

如下显示了进程状态变迁图

不可抢占/可抢占内核

不可抢占内核是指进程执行过程中，除了能被中断程序中断外不可被任何更高优先级的进程剥夺处理器控制权。如下图演示

可抢占内核正好相反，低优先级的进程可以被高优先级的进程抢占处理器使用权。如下图

可重入性

在程序设计中，大部分函数都会被不同对象在不同地方调用，特别是在多进程系统中，公共函数被不同进程所调用，要使得函数调用不会出现问题或其它意想不到的副作用，我们就必须要考虑函数的可重入性问题。如下例子可简单的说明这个问题。

代码1:

void strcpy(char *dst, char *src) {
	while (*dst++ = *src++) {
		;
	}
	*dst = NULL;	
}

代码2:

int tmp = 0;
void swap(int *x, int *y) {
	tmp = *x;
	*x = *y;
	*y = tmp;
}

从以上两个代码片段可以看出，代码1是可重入的，代码2是不可重入的，它们唯一的区别就是一个指使用了栈中的资源，另一个使用了全局资源。因此，在代码设计中，要保证函数的可重入性，必须确保函数调用过程中不依赖全局资源，而只依赖栈中的资源。

优先级反转

优先级反转是指高优先级的进程等待被低优先级进程占有的资源而阻塞时，系统中出现优先级比低优先级进程高但比高优先级进程低的进程时，导致低优先级进程无法执行不能释放资源，令高优先级进程一直阻塞的现象。这种现象在实时系统中是比较常见的，通常通过如下两种方法解决。

1. 优先级继承：低优先级的进程占用资源，导致高优先级进程阻塞时，低优先级进程的优先级调整为高优先级进程的优先级
2. 优先级天花板算法：进程在获得某种资源时，将自身优先级调整为可能会等待该资源的进程中优先级最高的进程的优先级

基于优先级的调度

如果有大量实时任务或规定了严格的完成时间点的任务，怎样才能完美的安排任务优先级满足任务的完成要求？RMA(Rate Monotonic Algorithm)就是其中的能做到这点的一项技术。

许多的实时系统使用了可抢占的多任务环境。而其中的每个任务则被赋予了各自的相对优先级，系统每次都选择优先级最高的就绪任务进行调度。

而调度算法在这里面扮演的就是选择赋予任务优先级的角色。依据优先级被设置的方式可将其分为三种：静态优先级，动态优先级，混合优先级。静态优先级的调度算法在任务创建时就赋予一个固定的优先级，并一直保持到任务完成。动态优先级算法会根据任务执行时的状态变化动态地调整其优先级。混合优先级算法包含了静态和动态的特征。毫无疑问，静态优先级算法比起动态优先级算法是要更简单的，因为其不用在执行过程中去根据条件计算优先级。

为展示调度算法的重要性，这儿举一个例子。在一个系统中有两个任务，分别为Task1和Task2。假设两个任务都是周期性执行的任务，执行周期分别为T1和T2,同时要求在任务必须在下一个周期开始前执行结束。T1=50ms,最坏情形下Task1需要25ms完成，设为C1=25ms;T2=100ms,C2=40ms。$U_i=\frac{C_i}{T_i}$,$U_i$为$Task_i$的CPU利用率。因此易得$U_1=50%, U_2=40%$,这意味着总的CPU利用率$U=U_1+U_2=90%$,这样在逻辑上似乎是合理的，因为其总的利用率不超过100%,这样就说明有足够的CPU时间用于执行这些任务。

但我们来考虑在静态优先级调度算法下的情形，两个任务的优先级有如下两种设置方法。

• Case1: Priority(t1)>Priority(t2)
• Case2: Priority(t1)<Priority(t2)

如下图所示，在Case1下两个任务都满足了各自的deadline,但在Case2下，任务1却无法满足它的deadline,尽管cpu仍然有10%的空闲时间，但却已经无法满足实时任务的要求，从这个例子可以看出，调度算法在保障系统实时性和任务的正常执行方面具有重要作用。

RMS/RMA(Rate Monotonic Scheduling/Rate Monotonic Algorithm)

RMA是为进程分配固定优先级以最大化任务的可调度性的算法，其思想方法很简单：

根据任务的周期分配优先级，周期越短，优先级越高

根据RMA的算法思想，我们考虑上面的例子，Task1的周期T1=50ms,Task2的周期T2=100ms,则Priority(t1) > Priority(t2),正好对应上面的Case1，也是正好满足两个任务能够正确执行的情形。

RMA是最优的静态优先级算法，如果一组任务使用RMA算法无法满足调度要求，那么使用其它静态优先级调度算法也无法满足。

静态优先级调度有其局限性，即不能最大化地利用CPU资源，尽管RMA是最优的静态优先级调度算法，但它有个最坏情形下的可调度边界：

$$
W_n = n*(2^\frac{1}{n} - 1)
$$

其中$n$为系统中的任务总数，当n=1时，最坏情形下的可调度边界为$W_1=100%$,随着系统中任务数量的增加，$W_n$不断减小，当$n\rightarrow\infty$时，$W=\ln 2$(近似等于69.3%)。

理论上系统中任务的任务对CPU的总利用率只要不超过70%，则其中的任务利用RMA总是可以调度的。反之，如下例子，T1=50,C1=25,T2=75,C2=30时,CPU总的利用率达到90%,当使用RMA调度算法时，Priority(t1)>Priority(t2),Task2将无法满足deadline,如下图：

即使反转它们的优先级，仍然无法改变这种状况。面临这种问题，唯一的选择就是改用动态优先级调度算法，但动态优先级调度算法显然会增加系统的复杂度，因此在很多的商业实时系统中不会去采用。

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 yxhlfx@163.com