转：任务调度与上下文切换

只看该作者 · 2011-3-16 10:48

1．任务调度概述：
任务调度（schedulers）是内核的主要职责，实际上它就是一个法官，决定当前由哪个任务占用CPU，多数实时内核都是基于优先级调度算法的，每个任务根据其重要程度的不同被赋予一定的优先级。基于此算法，CPU总是让处于就绪而且优先级最高的任务优先运行，然而何时高优先级任务能够得到CPU使用权，由内核的类型而定。基于优先级的内核有两种：
不可抢占型和抢占型。
1) 不可抢占型内核：
不可抢占型内核要求每个任务主动放弃CPU的使用权，其间不能被高优先级任务抢占。它的有点是：
A. 由于不需要在中断返回是进行任务切换，所以中断响应快。
B. 在任务级中可以调用不可重入函数而不必担心造成数据破坏。
C. 几乎不需要信号量来保护共享数据，也就是说，在任务运行过程中，数据是独享的。
但它的最大缺点是：响应时间不确定，当有更高优先级任务就绪后，不知道什么时候才能得到执行，这在实时系统中是致命的缺陷。所以不可抢占型内核最要用于前后台系统中。
2) 抢占型内核：
在嵌入式系统中，进程（任务）都是抢占型的，通过给每个进程（任务）设置一个优先级，当系统中有优先级比当前运行的进程（任务）的优先级更高的进程（任务）时，当前的进程（任务）执行被中断，并调用调度程序选择优先级高的进程（任务）运行。利用抢占式内核，可以保证高优先级的进程（任务）被优先执行，从而保证系统的实时响应。
在多任务系统中，进程（任务）的调度主要包括以下一些方面：
2．任务调度：
在多任务系统中，都会提供一个系统函数来进行进程（任务）间切换，综合来说，他们有两种进程（任务）切换方式：
1) 由进程（任务）本身直接调用任务切换函数进行进程（任务）切换：
在当前进程（任务）因为不能获得必须的资源而立即被堵塞时，就由进程（任务）本生直接调用进程（任务）切换函数进行进程（任务）间调度。
在Linux中可以直接调用schedule()函数来实现。
在UCos中，通过调用OSSched（）来完成。
2) 延迟调用任务切换函数进行进程（任务）切换：
此方式是把当前进程（任务）设置一调度标志而以延迟方式调用任务切换函数进行进程（任务）切换。
在Linux系统中，总是在恢复用户态进程执行之前，检查这一调度标志，在这里标志是：TIF_NEED_RESCHED，如果有这一标志，就调用调度函数进行进程切换。此种情况主要包括以下几种：
A. 当前进程用完了它的CPU时间片，有scheduler_tick()函数完成 schedule()的延迟调用。
B.当一个被唤醒进程的优先级比当前进程优先级高时，由try_to_wake_up()函数完成schedule()的延迟调用。
C.当发出系统调用sched_setscheduler()时。
在这些情况中，主要由于系统调用或中断而进入内核态，或者当前进程本来在内核态时，返回用户态时发生的。
在UCOS中，所有的任务有不同的优先级，不会出现同一优先级上有多个任务的情况，而且也没有系统调用的概念，所以任务调度的延迟调用只能出现在中断处理完成返回时，在OSIntExt()函数中，检查是否有高优先级的任务就绪，如果有高优先级的任务就绪，进行任务切换。
3．调度算法：
在Linux系统中，选用了比较复杂的调度算法，按照调度类型可以分为以下几种：
SCHED_FIFO:此算法主要应用于实时进程，当调度程序把CPU分配给当前进程后，如果没有更高优先级的进程可以运行时，此进程会一直占用CPU直到此进程退出或者自愿放弃CPU，即使此时有其他相同优先级的进程存在。
SCHED_RR:时间片轮询的实时进程，对于不同优先级的进程会调度优先级高的进程运行，对具有相同优先级的进程，会根据时间片来调度，当当前进程的时间片用完后，会调度相同优先级的其他进程运行，从而保证相同优先级进程的CPU调度公平性。
SCHED_NORMAL:此算法主要用于普通进程，利用分时进行调度。
在UCOS系统中，所有的任务都是实时任务，所以没有普通任务调度机制，而且为了简化调度算法，不同的任务有不同的优先级，不可能出现同一优先级有多个任务的情况，实际上它的调度算法就只有Linux中SCHED_FIFO这一种，即优先级高的任务抢占优先级低任务。
4．上下文切换：
上下文切换是多任务调度的核心内容，也是我们感觉在一个CPU上并行运行多个程序的基础。
任务上下文(Task Context)：任务上下文是指任务运行的环境。例如，针对x86的CPU，任务上下文可包括程序计数器、堆栈指针、通用寄存器的内容。
上下文切换（Context Switching）：在多任务系统中，上下文切换是指CPU的控制权由运行任务转移到另外一个就绪任务时所发生的事件，当前运行任务转为就绪（或者挂起、删除）状态，另一个被选定的就绪任务成为当前任务。上下文切换包括保存当前任务的运行环境，恢复将要运行任务的运行环境。上下文的内容依赖于具体的CPU。
对于不同的硬件体系结构，上下文切换的内容不一样，本质上有下面两步：
A. 如果有虚拟内存，则切换页全局目录以安装一个新的地址空间。
B. 切换内核堆栈和硬件上下文，因为硬件上下文提供了内核执行新进程所需要的所有信息，包括CPU信息。
在抢占式内核中，利用中断来实现上下文切换是一个非常理想的机制。中断发生时，中断会强制CPU把控制权交给操作系统，也就相当于一次上下文切换。这样不仅可以减少程序出错的后果，而且提高切换的效率。UCOS就是利用中断机制进行上下文切换的典型例子。在UCOS中，如果调度程序决定任务需要切换，就会调用上下文切换OS_TASK_SW()进行实际的上下文切换。OS_TASK_SW()是宏调用，含有微处理器的软中断指令，利用此中断来实现任务之间的上下文切换。所以OS_TASK_SW()是一个体系结构相关的宏，对于不同的硬件体系机构，有不同的实现方式，这也是UCOS在不同硬件体系结构中移植的一个要点。
由于UCOS不支持虚拟内存，所以不需要进行页目录切换，其他许多实时多任务嵌入式系统的一个特征，也是区别Linux系统的一个重要方面。
在2.6 Linux kernel中，引入了一个全新的调度机制O(1)调度器，它能在固定的时间内完成进程切换。如果调度程序决定任务需要切换，就会调用上下文切换函数context_switch()函数进行上下文切换，此函数会调用switch_mm()切换页全局目录以安装一个新的地址空间，然后调用switch_to()切换具体硬件上下文。
总结:
这里主要介绍了多任务系统中的任务调度及其算法，比较了Linux系统和UCOS系统中的上下文切换，具体实现可以参考Linux内核源代码和UCOS源代码。
参考：
1． Linux kernel Primer
2． Understanding the Linux kernel
3．嵌入式实时操作系统uC/OS-II
4．嵌入式计算机系统设计原理