1 第五章 任务管理与调度 主要内容 ?任务 ?任务管理 ?任务调度 ?优先级反转 2 High Priority Task Low Priority Task Task Task Task Task Task Task Event Event Each Task Infinite Loop Importance Splitting an application into Tasks int main(void) { // Initialize uCOS-II. OSInit(); // Create the first task OSTaskCreate(TestTask1, (void *) 11, &TestTaskStk1[TASK_STK_SIZE], 11); // Start multitasking. OSStart(); return 0; } void TestTask1(void *pdata) { printf("%4u: ***** Test Task 1 First call *****\n", OSTime); //Create 3 other tasks OSTaskCreate(TestTask2, (void *) 22, &TestTaskStk2[TASK_STK_SIZE], 22); OSTaskCreate(TestTask3, (void *) 33, &TestTaskStk3[TASK_STK_SIZE], 33); OSTaskCreate(TestTask4, (void *) 10, &TestTaskStk3[TASK_STK_SIZE], 10); while (1) { printf("%4u: ***** Test Task 11 *****\n", OSTime); OSTimeDly(1); } } Task demo based on ucOS 3 void TestTask2(void *pdata) { while (1) { printf("%4u: ***** Test Task 22 *****\n", OSTime); OSTimeDly(1); } } void TestTask3(void *pdata) { while (1) { printf("%4u: ***** Test Task 33 *****\n", OSTime); OSTimeDly(1); } } void TestTask4(void *pdata) { while (1) { printf("%4u: +++++ Test Task 10 +++++\n", OSTime); OSTaskSuspend(10); //Suspend yourself } } 程序运行结果程序运行结果 采用多任务的好处： ?任务的 规模较小 ? 每个任务更容易编码和调试，其质量也更容易得到 保证 ?不少 应用本身 就是由多个任务构成的 ? 如一个应用可能需要进行以下任务的处理：计算、 从网络获取数据和刷新显示屏幕 ? 采用多任务的处理方式是应用问题的一个 非常自然 的解决方式 ?任务之间具有较高的独立性，耦合性小 ? 通过增加新的任务就能方便的 扩充系统功能 ?实时性 强 ? 保证紧急事件得到优先处理成为可能 4 ?在嵌入式实时系统中 ?任务 （ task）通常为 进程 （ process）和 线程 （ thread）的统称 ?任务是 调度的基本单位 ?进程最初由 Multics的设计者在 60年代提出来 的，主要包括以下内容： ?一个正在执行的程序； ?计算机中正在运行的程序的一个实例； ?可以分配给处理器，并由处理器执行的一个实体； ?由一个顺序的执行线程、一个当前状态和一组相关 的系统资源所刻画的活动单元。 ?进程由 代码 、 数据 、 堆栈 和 进程控制块 构成。 ?进程控制块包含了操作系统用来控制进程所需要的 信息： ? 进程状态、 CPU寄存器、调度信息、内存管理信息、 I/O 状态信息等 ? 早期的进程，包含了以下两个方面的内容： ? 资源 。进程是资源分配的基本单位，一个进程包 括一个保存进程映像的虚拟地址空间、主存、 I/O 设备和文件等资源。 ? 调度执行 。进程作为操作系统的调度实体，是调 度的基本单位。 ? 随着操作系统的发展，进程所包含的两个方 面的内容逐渐被分开： ? 轻量级进程或线程 ：调度执行的单位 ? 进程 ：资源分配的单位 ? 线程是进程内部一个相对独立的控制流，由线程 上下文和需要执行的一段程序指令构成 ? 在进程中，所 有线程共享该进程的状态和资源 ， 可以访问相同的数据 5 ?使用线程的优势： ?创建 ：在一个已有进程中创建一个新线程比 创建一个全新的进程所需的时间开销少； ?终止 ：终止一个线程比终止一个进程所花费 的时间少； ?切换 ：线程切换比进程切换所花费的时间 少； ?通信 ：使同一进程内部不同线程之间的 通信 效率 得到显著提高。 ? 在大多数操作系统中，不同进程之间的通信需要 内核的干预，而同一进程内部不同线程之间则可 直接通信。 ?引入线程的概念后，可把进程和线程的 使用分为以下几种模型： ?单进程 /单线程模型 （如 MS-DOS）：整个 系统只有一个进程、一个线程 ?单进程 /多线程模型 （如 Java虚拟机）：在 单进程 /多线程模型中，整个系统有一个进 程、多个线程 ?多进程 /单线程模型 （如传统的 UNIX）：在 多进程 /单线程模型中，整个系统有多个进 程，每个进程只有一个线程 ?多进程 /多线程模型 （如 Windows NT、 Solaris、 Mach等）：在多进程 /多线程模型 中，系统有多个进程，每个进程又可包含多 个线程 6 单进程/单线程模型 单进程/多线程模型 多进程/多线程模型 多进程/单线程模型 ?大多数实时内核：单进程 /多线程模型， 或简单地称为 任务模型 ?把整个应用当作一个没有定义的进程来对 待； ?应用则被划分为多个任务的形式来进行处 理。 ?也有一些嵌入式实时操作系统采用了多 进程 /多线程模型： ?系统中包含多个进程，每个进程对应又包含 多个线程 ?多进程 /多线程模型 适合于处理复杂的应用 ?任务模型 则适用于实时性要求较高的、相对 简单的应用 7 第一节 任务 任务的定义及其主要特性 任务的内容 任务的分类 任务参数 任务的定义及其主要特性 ?任务是一个具有 独立功能 的 无限循环 的程序段 的一次运行活动，是实时内核调度的单位，具 有以下特性： ?动态性 ：任务状态是不断变化的。 ? 一般分为就绪态、运行态和等待态。 ? 在多任务系统中，任务的状态将随着系统的需要不断进行 变化。 ?并行性 ： ? 系统中同时存在多个任务，这些任务在宏观上是同时运行 的。 ?异步独立性 ： ? 每个任务各自按相互独立的不可预知的速度运行，走走停 停。 多任务运行情况多任务运行情况 8 任务的内容 ?任务主要包含以下内容： ?代码 ：一段可执行的程序 ?数据 ：程序所需要的相关数据（变量、工作 空间、缓冲区等） ?堆栈 ?程序执行的上下文环境 任务的内容 ?任务所包含的程序通常为一个具有无限 循环的程序 /*ioTask implements data obtaining and handling continuously*/ void ioTask(void) { int data; initial(); /*The following sentences get data and handle data continuously*/ while(TRUE) { data = getData(); handleData(data); } } i l ts data obtai int ta; initial(); get data ; ; 9 void YourTask (void *pdata) { for (;;){ /* USER CODE */ Call one of uC/OS-II’s services: OSFlagPend(); OSMboxPend(); OSMutexPend(); OSQPend(); OSSemPend(); OSTaskDel(OS_PRIO_SELF); OSTaskSuspend(OS_PRIO_SELF); OSTimeDly(); OSTimeDlyHMSM(); /* USER CODE */ } } void YourTask (void *pdata) { /* USER CODE */ OSTaskDel(OS_PRIO_SELF); } void TestTask2(void *pdata) { while (1) { printf("%4u: ***** Test Task 22 *****\n", OSTime); OSTimeDly(1); } } void TestTask3(void *pdata) { while (1) { printf("%4u: ***** Test Task 33 *****\n", OSTime); OSTimeDly(1); } } void TestTask4(void *pdata) { while (1) { printf("%4u: +++++ Test Task 10 +++++\n", OSTime); OSTaskSuspend(10); //Suspend yourself } } 10 任务的内容 ?任务与程序的区别： ?任务能真实地描述工作内容的 并发性 ，而程 序不能； ?程序是任务的组成部分 ? 除程序外，任务还包括数据、堆栈及其上下文环 境等内容； ?程序是静态的，任务是动态的； ?任务有 生命周期 ，有诞生、有消亡，是短暂 的；而程序是相对长久的； ?一个程序可对应多个任务，反之亦然； ?任务具有创建其他任务的功能，而程序没 有。 任务的内容 ?任务上下文环境（ context） ?包括了实时内核 管理任务 、以及处理器 执行 任务 所需要的所有信息。 ? 任务优先级 、 任务的状态 等实时内核所需要的信 息，以及处理器的 各种寄存器的内容 （ hardware context） ：程序计数器、堆栈指 针、通用寄存器等的内容 ?任务的上下文环境通过 任务控制块 （ task control block， TCB）来体现。 11 任务1 任务2 任务3 内核 内核代码 内核代码 内核数据 内核数据 栈 栈 数据 数据 任务 控制块 任务 控制块 代码 代码 栈 栈 数据 数据 任务 控制块 任务 控制块 代码 代码 栈 栈 数据 数据 任务 控制块 任务 控制块 代码 代码 任务1 任务2 任务3 多任务系统多任务系统 示意图示意图 任务的分类 ?按照到达情况的可预测性，任务可以划 分为： ?周期任务 （ periodic task） ?非周期任务 ?按照重要程度，可分为： ?关键任务 （ critical task） ?非关键任务 （ noncritical task） 12 任务的分类 ?周期任务与非周期任务 ?周期任务每隔一个固定的时间间隔就会执行 一次。 ? 飞行器可能需要每隔 100ms获得一次关于飞行器 的速度、高度和姿态数据，控制传感器获取这些 数据就需要通过周期任务来进行。 ?非周期任务执行的间隔时间则为不确定的。 ? 移动通信设备中的通信任务，该任务只有在需要 进行通信的情况下才会得到执行。 ? 非周期任务分为： o sporadic task： 有最小到达间隔时间限制 o aperiodic task： 没有到达时间限制 任务的分类 ?关键任务与非关键任务 ?关键任务： ? 为需要得到及时执行的任务，否则将出现灾难性 的后果 o 飞行器中用于处理生命支持系统和稳定性控制系统的 任务 ?非关键任务： ? 如果没有得到及时执行，则不会产生严重后果 13 任务参数 ?任务参数： ?优先级（ priority） ?周期（ period） ?计算时间（ computation time） ?就绪时间（ ready time） ?截止时间（ deadline） ?任务的优先级 ?表示任务对应工作内容在处理上的优先程度 ?优先级越高，表明任务越需要得到优先处理 ? 飞行器中处理稳定性控制的任务，就需要具有较高的优先 级，一旦执行条件得到满足，应及时得到执行 ?任务的优先级分为 静态优先级 和 动态优先级 。 ? 静态优先级： 任务的优先级被确定后，在系统运行过程中将 不再发生变化； ? 动态优先级： 系统运行过程中，任务的优先级是可以动态变 化的。 任务参数 ?周期 ?周期任务所具有的参数，表示任务周期性执行的间 隔时间 ?任务的计算时间 ?任务在 特定硬件环境下 被完整执行所需要的时间， 也被称为是任务的执行时间（ execution time）。 ?由于任务每次执行的软件环境的差异性，导致任务 在各次具体执行过程中的计算时间各有不同。 ?通常用 最坏情况下的执行时间 （ worst case time） 或是需要的最长执行时间来表示，也可用 统计时间 （ statistical time）来表示。 14 任务参数 ?任务的就绪时间 ? 任务具备了在处理器上被执行所需要的条件时的时间 ?任务的截止时间 ? 意味着任务需要在该时间到来之前被执行完成。 ? 截止时间可以通过 绝对截止时间 （ absolute deadline）和 相对 截止时间 （ relative time）两种方式来表示 o 相对截止时间为任务的绝对截止时间减去任务的就绪时间。 ? 截止时间可以分为 强截止时间 （ hard deadline）和 弱截止时间 （ soft deadline）两种情况： o 具有强截止时间的任务即为 关键任务 ，如果截止时间不能得到 满足，就会出现严重的后果。 o 拥有关键任务的实时系统又被称为 强实时 （ hard real-time）系 统，否则称为 弱实时 （ soft real-time）系统。 第二节 任务管理 任务状态与变迁 空闲任务 任务控制块 任务切换 任务队列 优先级位图算法 任务管理机制 15 任务状态与变迁 ?任务拥有的资源情况是不断变化的，导致 任务状态 也表现出不断变化的特性。 ?不同的实时内核实现方式对任务状态的定 义不尽相同，但是都可以概括为三种基本 的状态： ?等待 （ waiting）：任务在等待某个事件的发 生； ?就绪 （ ready）： 任务等待获得处理器资源； ?执行 （ running）：任务获得处理器资源，所 包含的代码内容正在被执行。 任务状态与变迁 ?在单处理器系统中： ?任何时候都只有一个任务在 CPU中执行 ? 如果没有任何事情可做，就运行 空闲任务 执行空操作 ?任何一个可以执行的任务都必须处于 就绪状态 ? 调度程序从任务的 就绪队列 中选择下一个需要执行的任务。 ? 处于就绪状态的任务拥有除 CPU以外的其他所有需要的资 源。 ?任务还可能处于 等待状态 ? 如任务在需要等待 I/O设备或其他任务提供的数据，而数据 又还没有到达该任务的情况下，就处于等待状态 16 任务状态与变迁 ?任务会在不同的状态之间进行转换，即 任务状态的变迁 ?对于处于 就绪状态 的任务，获得 CPU后，就 处于执行状态。 ?处于 执行状态 的任务如果被高优先级任务所 抢占，任务又会回到就绪状态。 ?处于执行状态的任务如果需要 等待资源 ，任 务会被切换到等待状态。 ?对处于 等待状态 的任务，如果需要的资源得 到满足，就会转换为就绪状态，等待被调度 执行。 就绪态 运行态 等待态 获得CPU 被高优先级任 务抢占或超时 获得资源 需要资源 任务状态变迁任务状态变迁 17 任务1 任务2 任务3 调度 程序 0 5 10 15 20 25 30 35 40 45 50 运行 等待 就绪 三个任务进行状态转换的过程 包含三个任务和一个调度程序。调度程序用来确定下一个需要投入运 行的任务，因此调度程序本身也需要占用一定的处理时间。 Task states and transition of ucOS 18 空闲任务 ?which is executed when none of the other tasks is ready to run. ?The idle task is always set to the lowest priority. ?The idle task can never be deleted by application software. void OS_TaskIdle (void *pdata) { /* Prevent compiler warning for not using 'pdata‘ */ pdata = pdata; for (;;) { OS_ENTER_CRITICAL(); OSIdleCtr++; OS_EXIT_CRITICAL(); /* Call user definable HOOK */ OSTaskIdleHook(); } } Idel Task of ucOS OSIdleCtr is used by the statistics task to determine how much CPU time (in percentage) is actually being consumed by the application software. 19 任务控制块 ?任务管理是通过对 任务控制块 （ task control block， TCB）的操作来实现的。 ?任务控制块 是包含任务相关信息的数据结构 ?包含了任务执行过程中所需要的所有信息。 ?任务控制块大都包括以下信息： ?任务的名字 ?任务执行的起始地址 ?任务的优先级 ?任务的状态 ?任务的硬件上下文（堆栈指针、 PC和寄存器等）、 任务的队列指针等内容 task name task ID task status task priority task context（registers and flags of CPU） … （ ） 任务控制块示意图任务控制块示意图 20 任务控制块 ?为节约内存， 任务数量 通常需要进行预先 配置 ?按照配置的任务数量初始化任务控制块，一 个任务对应一个初始的任务控制块，形成一个 空闲任务控制块链 。 ?在任务创建时，实时内核从空闲任务控制 块链中为任务分配一个任务控制块。 ?随后对任务的操作，都是基于对应的 任务控 制块 来进行的。 ?当任务被删除后，对应的任务控制块又会被 实时内核回收到 空闲任务控制块链 。 typedef struct os_tcb { OS_STK *OSTCBStkPtr; /* Pointer to current top of stack */ #if OS_TASK_CREATE_EXT_EN > 0 void *OSTCBExtPtr; /* Pointer to user definable data for TCB extension */ OS_STK *OSTCBStkBottom; /* Pointer to bottom of stack */ INT32U OSTCBStkSize; /* Size of task stack (in number of stack elements) */ INT16U OSTCBOpt; /* Task options as passed by OSTaskCreateExt() */ INT16U OSTCBId; /* Task ID (0..65535) */ #endif struct os_tcb *OSTCBNext;/* Pointer to next TCB in the TCB list */ struct os_tcb *OSTCBPrev;/* Pointer to previous TCB in the TCB list */ #if ((OS_Q_EN>0)&&(OS_MAX_QS>0))||(OS_MBOX_EN>0)||(OS_SEM_EN>0)||(OS_MUTEX_EN>0) OS_EVENT *OSTCBEventPtr; /* Pointer to event control block */ #endif #if ((OS_Q_EN > 0) && (OS_MAX_QS > 0)) || (OS_MBOX_EN > 0) void *OSTCBMsg; /* Message received from OSMboxPost() or OSQPost()*/ #endif TCB of ucOS 21 #if (OS_VERSION >= 251) && (OS_FLAG_EN > 0) && (OS_MAX_FLAGS > 0) #if OS_TASK_DEL_EN > 0 OS_FLAG_NODE *OSTCBFlagNode; /* Pointer to event flag node */ #endif OS_FLAGS OSTCBFlagsRdy; /* Event flags that made task ready to run*/ #endif INT16U OSTCBDly; /* Nbr ticks to delay task or, timeout waiting for event*/ INT8U OSTCBStat;/* Task status */ INT8U OSTCBPrio;/* Task priority (0 == highest, 63 == lowest) */ INT8U OSTCBX;/* Bit position in group corresponding to task priority (0..7)*/ INT8U OSTCBY;/* Index into ready table corresponding to task priority */ INT8U OSTCBBitX; /* Bit mask to access bit position in ready table */ INT8U OSTCBBitY; /* Bit mask to access bit position in ready group */ #if OS_TASK_DEL_EN > 0 BOOLEAN OSTCBDelReq; /* Indicates whether a task needs to delete itself */ #endif } OS_TCB; 任务切换 ?任务切换 （ context switching） ?保存当前任务的上下文，并恢复需要执行的 任务的上下文的过程。 ?当发生任务切换时： ?当前正在运行的任务的上下文就需要通过该 任务的 任务控制块 保存起来； ?把需要 投入运行的任务 的上下文从对应的任 务控制块中恢复出来。 22 任务1 任务2 任务3 调度 程序 0 5 10 15 20 25 30 35 40 45 50 运行 等待 就绪 在时刻8即发生了任务切换，任务1的上下文需要保存到任务1的任务 控制块中去。 经过调度程序的处理，在时刻10任务2投入运行，需要把任务2的任务 控制块中关于上下文的内容恢复到CPU的寄存器。 任务1 任务2 实时内核调度程序 保存任务1的上下文到TCB1 从TCB2恢复任务2的上下文 …… 保存任务2的上下文到TCB2 从TCB1恢复任务1的上下文 …… 时间 任务1执行一段时间后，由于某种原因，需要进行任务切换，进入实时内 核的调度程序。调度程序首先把当前的上下文内容保存到任务1的任务控 制块TCB1中，然后又把任务2的上下文从TCB2中恢复到CPU寄存器，随后 任务2得到执行。任务2执行一段时间后，由于某种原因，需要进行任务 切换，进入实时内核的调度程序。调度程序首先把当前的上下文内容保 存到任务2的任务控制块TCB2中，然 后又把任务1的上下文从TCB1中恢复 到CPU寄存器，随后任务1得到执行。 23 任务切换 ? 任务切换将导致 任务状态 发生变化： ? 当前正在运行的任务将由运行状态变为 就绪或是等 待 状态； ? 需要投入运行的任务则由就绪状态变为运行状态。 ? 任务切换具有如下基本步骤： 1. 保存任务上下文环境； 2. 更新当前处于运行状态的任务的任务控制块的内 容，如把任务的状态由运行状态改变为就绪或是等 待状态； 3. 把任务的任务控制块移到相应的队列（就绪队列或 是等待队列）； 4. 选择另一个任务进行执行：调度； 5. 改变需要投入运行的任务的任务控制块的内容，把 任务的状态变为运行状态； 6. 根据任务控制块，恢复需要投入运行的任务的上下 文环境 。 任务切换 ?任务切换的时机： ?可以在实时内核从当前正在运行的任务中获得控制权 的任何时刻发生。 ?导致控制权交给实时内核的事件通常包括如下 内容： ?中断、自陷 ? 如当 I/O中断发生的时候 o 如果 I/O活动是一个或多个任务正在等待的事件，内核将把相 应的处于等待状态的任务转换为就绪状态 o 同时，内核还将确定是否继续执行当前处于运行状态的任务， 或是用高优先级的就绪任务抢占该任务 ? 自陷 o 由于执行任务中当前指令所引起，将导致实时内核处理相应的 错误或异常事件，并根据事件类型，确定是否进行任务的切换 24 任务切换 ?运行任务因缺乏资源而被阻塞 ? 如，任务执行过程中进行 I/O操作时（如打开文 件），如果此前该文件已被其他任务打开，将导 致当前任务处于等待状态，而不能继续执行 ?时间片轮转调度 时 ? 内核将在时钟中断处理程序中确定当前正在运行 的任务的执行时间是否已经超过了设定的时间 片； ? 如果超过了时间片，实时内核将停止当前任务的 运行，把当前任务的状态变为就绪状态，并把另 一个任务投入运行 任务切换 ?高优先级任务处于就绪 时 ? 如果采用基于优先级的抢占式调度算法，将导致 当前任务停止运行，使更高优先级的任务处于运 行状态 25 void OS_Sched (void) { INT8U y; OS_ENTER_CRITICAL(); if ((OSIntNesting == 0) && (OSLockNesting == 0)) {/* Sched. only if all ISRs done & not locked */ y = OSUnMapTbl[OSRdyGrp]; /* Get pointer to HPT ready to run */ OSPrioHighRdy = (INT8U)((y << 3) + OSUnMapTbl[OSRdyTbl[y]]); if (OSPrioHighRdy != OSPrioCur) { /* No Ctx Sw if current task is highest rdy */ OSTCBHighRdy = OSTCBPrioTbl[OSPrioHighRdy]; OSCtxSwCtr++; /* Increment context switch counter */ OS_TASK_SW(); /* Perform a context switch */ } } OS_EXIT_CRITICAL(); } Task scheduling of ucOS void OSCtxSw (void) { PUSH R1, R2, R3 and R4 onto the current stack; OSTCBCur->OSTCBStkPtr = SP; OSTCBCur = OSTCBHighRdy; SP = OSTCBHighRdy->OSTCBStkPtr; POP R4, R3, R2 and R1 from the new stack; Execute a return from interrupt instruction; } OS_TASK_SW() 26 Context-switch in ucOS Data structures before context-switch Context-switch in ucOS Data structures after saving the context- switch of current task 27 Context-switch in ucOS Data structures after restoring the context- switch of high priority task Context-switch in ucOS Based on 80X86CPU real mode 28 _OSCtxSw PROC FAR PUSHA ; Save current task's context PUSH ES ; PUSH DS ; ; MOV AX, SEG _OSTCBCur ; Reload DS in case it was altered MOV DS, AX ; ; LES BX, DWORD PTR DS:_OSTCBCur ; OSTCBCur->OSTCBStkPtr = SS:SP MOV ES:[BX+2], SS ; MOV ES:[BX+0], SP ; ; CALL FAR PTR _OSTaskSwHook ; MOV AX, WORD PTR DS:_OSTCBHighRdy+2 ; OSTCBCur = OSTCBHighRdy MOV DX, WORD PTR DS:_OSTCBHighRdy ; MOV WORD PTR DS:_OSTCBCur+2, AX ; MOV WORD PTR DS:_OSTCBCur, DX ; ; MOV AL, BYTE PTR DS:_OSPrioHighRdy ; OSPrioCur = OSPrioHighRdy MOV BYTE PTR DS:_OSPrioCur, AL ; LES BX, DWORD PTR DS:_OSTCBHighRdy; SS:SP = OSTCBHighRdy->OSTCBStkPtr MOV SS, ES:[BX+2] ; MOV SP, ES:[BX] ; ; POP DS ; Load new task's context POP ES ; POPA ; ; IRET ; Return to new task ; _OSCtxSw ENDP Context-switch under 80x86 任务上下文切换时间 ?任务上下文切换时间： ?保存 ：保存当前运行任务上下文的时间； ?调度 ：选择下一个任务的调度时间； ?恢复 ：将要运行任务的上下文的恢复时间。 ?保存和恢复上下文的时间： ?取决于任务上下文的定义和处理器的速度。 ?不同种类的处理器，任务上下文的定义不同，其内 容有多有少。 ?任务上下文切换的时间与 调度 （即选择下一个 运行任务）的过程有关。 ?强实时内核 要求调度过程所花费的时间是确定的， 即不能随系统中 就绪任务 的数目而变化。 ?与具体实现调度算法时所采用的数据结构有关。 29 任务队列 ?任务队列通过任务控制块实现对系统中所 有任务的管理。 新任务 CPU 就绪队列 等待队列 超时 调度 等待资源 获得资源 释放CPU 单就绪队列和单等待队列单就绪队列和单等待队列 任务队列 ?队列由任务控制块构成 task name task ID task status task priority task context … it t task name task ID task status task priority task context … it t task name task ID task status task priority task context … it t Head 队列TCB1 TCB2 TCBn NULL 任务队列任务队列 30 任务队列 ?单等待队列 ?资源对应的事件发生时，实时内核需要扫描 整个等待队列，搜索等待该资源的任务，并 按照一定的策略 选取任务，把任务的任务控 制块放置到就绪队列。 ?如果系统的资源和任务比较多，搜索等待该 资源的任务所需要的时间就比较长，会影响 整个系统的实时性。 ?可采用一种 多等待队列 的处理方式 ?资源对应的事件发生时，能够在较短的时间 内确立等待该资源的任务等待队列。 新任务 CPU 就绪队列 资源1等待队列 超时 调度 等待资源1 获得资源1 释放CPU 资源2等待队列 等待资源2 获得资源2 资源n等待队列 等待资源n 获得资源n …… 单就绪队列和多等待队列单就绪队列和多等待队列 31 任务队列 ?对于就绪任务，如果采用上述队列方式进行管 理，在基于优先级的调度处理中，要获得当前 具有最高优先级的就绪任务： ?任务就绪时，把就绪任务的任务控制块放在就绪队列 的末尾。 ? 调度程序需要从就绪队列的头部到尾部进行一次遍历，才能 获得就绪队列中具有最高优先级的任务； ?就绪队列按照优先级从高到低的顺序排列 。 ? 新的就绪任务到达时，需要插入到就绪队列的合适位置，确 保就绪队列保持优先级从高到低排列的顺序性。 ?在这两种处理方式中，所花费的时间与任务数 量有密切的关系，具有不确定性。 ?为提高实时内核的确定性，可采用一种被称为 优先级 位图的就绪任务处理算法 。 Free TCBs after OS_TCBInit() in ucOS 32 Task ready list after OSInit() in ucOS Task ready list after OSStart() in ucOS 33 优先级位图算法 OSRdyGrp: 优先级就绪组优先级就绪组 OSRdyTbl: 优先级就绪表优先级就绪表 35: 00100011 char OSRdyGrp; char OSRdyTbl[8]; 100000007 010000006 001000005 000100004 000010003 000001002 000000101 000000010 二进制值下标 优先级映射表优先级映射表 char OSMapTbl[8] = = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80}; OSMapTbl的数组元素的下标与任务优先级的高三位或低三的数组元素的下标与任务优先级的高三位或低三 位相对应。位相对应。OSMapTbl的数组元素对应的二进制值中，位的数组元素对应的二进制值中，位 为为1的位表示的位表示OSRdyGrp或是或是OSRdyTbl[]的对应位也为的对应位也为1。。 35: 00100011 34 优先级判定表优先级判定表 char OSUnMapTbl[256]; 以以 OSRdyGrp或是或是 OSRdyTbl[]数组元素的值为索引，获取该值对应二进制数组元素的值为索引，获取该值对应二进制 表示中表示中 1出现的最低二进制位的序号（出现的最低二进制位的序号（ 0-7）。）。 任务进入就绪态 OSRdyGrp |= OSMapTbl[priority >> 3]; OSRdyTbl[priority >> 3] |= OSMapTbl[priority & 0x07]; 35: 00100011 OSRdyGrp 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 23 22 21 20 19 18 17 16 31 30 29 28 27 26 25 24 39 38 37 36 35 34 33 32 47 46 45 54 43 42 41 40 55 54 53 52 51 50 49 48 63 62 61 60 59 58 57 56 7 6 5 4 3 2 1 0 OSRdyTbl OSRdyTbl[0] OSRdyTbl[1] OSRdyTbl[2] OSRdyTbl[3] OSRdyTbl[4] OSRdyTbl[5] OSRdyTbl[6] OSRdyTbl[7] n00010000 o00001000 35 任务退出就绪态 if((OSRdyTbl[priority >> 3] &= ~OSMapTbl[priority & 0x07]) = = 0) OSRdyGrp &= ~OSMapTbl[priority >> 3]; 35: 00100011 OSRdyGrp 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 23 22 21 20 19 18 17 16 31 30 29 28 27 26 25 24 39 38 37 36 35 34 33 32 47 46 45 54 43 42 41 40 55 54 53 52 51 50 49 48 63 62 61 60 59 58 57 56 7 6 5 4 3 2 1 0 OSRdyTbl n 00001000->11110111 o 00010000->11101111 OSRdyTbl[0] OSRdyTbl[1] OSRdyTbl[2] OSRdyTbl[3] OSRdyTbl[4] OSRdyTbl[5] OSRdyTbl[6] OSRdyTbl[7] 获取进入就绪态的最高优先级 high3Bit = OSUnMapTbl[OSRdyGrp]; low3Bit = OSUnMapTbl[OSRdyTbl[high3Bit]]; priority = (high3Bit << 3) + low3Bit; 35: 00100011 OSRdyGrp 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 23 22 21 20 19 18 17 16 31 30 29 28 27 26 25 24 1 0 0 0 1 0 0 0 47 46 45 54 43 42 41 40 55 54 53 52 51 50 49 48 63 62 61 60 59 58 57 56 0 1 0 1 0 0 0 0 OSRdyTbl n 0x60->4/high3Bit o 0x88->3/low3Bit p ucOS中，任务按优先级进行组织，以优先级为数组元素下标，通过 OSTCBPrioTbl[]即可找到相应的TCB。 OSRdyTbl[0] OSRdyTbl[1] OSRdyTbl[2] OSRdyTbl[3] OSRdyTbl[4] OSRdyTbl[5] OSRdyTbl[6] OSRdyTbl[7] 36 任务管理机制 ?任务管理用来实现对任务状态的直接控制和访 问。 ?内核的任务管理是通过系统调用来体现，主要包 括任务创建、任务删除、任务挂起、任务唤醒、 设置任务属性等内容 。 创建任务 删除任务 挂起任务 唤醒任务 设置任务属性 改变任务优先级 获取任务信息 … 任务管理功能任务管理功能 任务管理机制 ?创建任务 的过程即为分配任务控制块的过程。 ?在创建任务时，通常需要确定任务的名字和任务的优先级等内容， 确立任务所能使用的堆栈区域。 ?任务创建成功后，通常会为用户返回一个标识该任务的 ID，以实 现对任务的引用管理。 ?删除任务 把任务从系统中去掉，释放对应的任务控制块。 ?挂起任务 把任务变为等待状态，可通过唤醒任务操作把任 务转换为就绪状态。 ?设置任务属性 可以用来设置任务的抢占、时间片等特性， 以确定是否允许任务在执行过程中被抢占或是对同优先级 任务采用时间片轮转方式运行等。 ?改变任务优先级 用来根据需要改变任务的当前优先级。 ?获取任务信息 获得任务的当前优先级、任务的属性、任务 的名字、任务的上下文、任务的状态等内容，便于用户进 行决策。 37 创建任务 ?任务创建为任务分配和初始化相关的数 据结构。 ?任务创建时通常需要使用如下信息： ?任务的名字 ?任务的初始优先级 ?任务栈 ?任务属性 ?任务对应的函数入口地址 ?任务对应函数的参数 ?任务删除时的回调函数 创建任务 ?栈空间 ： ?由于不同任务运行时需要的的大小不同，由内核进行 任务栈的分配就不能适应应用任务的多样性需求。 ?通常由用户指定任务运行过程中需要使用的栈空间。 ?确定任务到底需要多少栈空间是一个比较困难的事 情。大都需要进行一个反复修正的过程： 1.在最开始的时候，根据应用的类型，为任务分配一个比预期 估计更大的栈空间； 2.使用栈检测函数，定期监控任务对栈的使用情况，并据此对 任务栈的大小进行调整。 38 创建任务 ?任务可以包含多种属性 ?任务是否可被抢占 ?是否采用时间片轮转调度方式调度 ?是否响应异步信号 ?任务中开放的中断级别 ?是否使用数字协处理器等内容 ? 如果任务需要进行浮点运算，在创建任务时实时 内核应为任务分配浮点堆栈空间，以在任务切换 时保存或是恢复数字协处理器的上下文内容。 ?任务对应函数的入口地址 ?表示所创建任务起始执行的入口 创建任务 ? 任务创建通常需要完成以下工作： ? 获得任务控制块 TCB ? 根据实时内核用户提供的信息初始化 TCB ? 为任务分配一个可以唯一标识任务的 ID ? 使任务处于就绪状态，把任务放置到就绪 队列 ? 进行任务调度处理 39 INT8U OSTaskCreate (void (*task)(void *pd), void *pdata, OS_STK *ptos, INT8U prio) { OS_STK *psp; INT8U err; OS_ENTER_CRITICAL(); if (OSTCBPrioTbl[prio] == (OS_TCB *)0) { /* Make sure task doesn't already exist at this priority */ OSTCBPrioTbl[prio] = (OS_TCB *)1; /* Reserve the priority to prevent others from doing the same thing until task is created. */ OS_EXIT_CRITICAL(); psp = (OS_STK *)OSTaskStkInit(task, pdata, ptos, 0); /* Initialize the task's stack */ err = OS_TCBInit(prio, psp, (OS_STK *)0, 0, 0, (void *)0, 0); if (err == OS_NO_ERR) { OS_ENTER_CRITICAL(); OSTaskCtr++; /* Increment the #tasks counter */ OS_EXIT_CRITICAL(); if (OSRunning == TRUE) { /* Find highest priority task if multitasking has started */ OS_Sched(); } } else { OS_ENTER_CRITICAL(); OSTCBPrioTbl[prio] = (OS_TCB *)0;/* Make this priority available to others */ OS_EXIT_CRITICAL(); } return (err); } OS_EXIT_CRITICAL(); return (OS_PRIO_EXIST); } OSTaskCreate in ucOS int main(void) { // Initialize uCOS-II. OSInit(); // Create the first task OSTaskCreate(TestTask1, (void *) 11, &TestTaskStk1[TASK_STK_SIZE], 11); // Start multitasking. OSStart(); return 0; } void TestTask1(void *pdata) { printf("%4u: ***** Test Task 1 First call *****\n", OSTime); //Create 3 other tasks OSTaskCreate(TestTask2, (void *) 22, &TestTaskStk2[TASK_STK_SIZE], 22); OSTaskCreate(TestTask3, (void *) 33, &TestTaskStk3[TASK_STK_SIZE], 33); OSTaskCreate(TestTask4, (void *) 10, &TestTaskStk3[TASK_STK_SIZE], 10); while (1) { printf("%4u: ***** Test Task 11 *****\n", OSTime); OSTimeDly(1); } } Task demo based on ucOS 40 void TestTask2(void *pdata) { while (1) { printf("%4u: ***** Test Task 22 *****\n", OSTime); OSTimeDly(1); } } void TestTask3(void *pdata) { while (1) { printf("%4u: ***** Test Task 33 *****\n", OSTime); OSTimeDly(1); } } void TestTask4(void *pdata) { while (1) { printf("%4u: +++++ Test Task 10 +++++\n", OSTime); OSTaskSuspend(10); //Suspend yourself } } 程序运行结果程序运行结果 删除任务 ?内核根据任务创建时获得的 ID删除指定的 任务。 ?在删除一个任务时，需要 释放该任务所拥 有的资源 。 ?释放任务所拥有的资源通常由 内核 和 任务 共同 完成。 ? 内核通常只释放那些由内核为任务分配的资源 o 如任务名字和 TCB等内容所占用的空间。 ? 由任务自己分配的资源则通常由任务自身进行释放 o 如任务的堆栈空间，以及其他一些任务申请的资源，信号 量、 timer、文件系统资源、 I/O设备和使用 malloc等函数 动态获得的内存空间等。 41 删除任务 ?任务删除通常需要进行以下工作： ?根据指定的 ID，获得对应任务的 TCB ?把任务的 TCB从队列中取出来，挂入空闲 TCB队列 ?释放任务所占用的资源 INT8U OSTaskDel (INT8U prio) { OS_EVENT *pevent; OS_TCB *ptcb; BOOLEAN self; if (OSIntNesting > 0) { /* See if trying to delete from ISR */ return (OS_TASK_DEL_ISR); } OS_ENTER_CRITICAL(); if (prio == OS_PRIO_SELF) { /* See if requesting to delete self */ prio = OSTCBCur->OSTCBPrio; /* Set priority to delete to current */ } ptcb = OSTCBPrioTbl[prio]; if (ptcb != (OS_TCB *)0) { /* Task to delete must exist */ if ((OSRdyTbl[ptcb->OSTCBY] &= ~ptcb->OSTCBBitX) == 0x00) { /* Make task not ready */ OSRdyGrp &= ~ptcb->OSTCBBitY; } pevent = ptcb->OSTCBEventPtr; if (pevent != (OS_EVENT *)0) { /* If task is waiting on event */ if ((pevent->OSEventTbl[ptcb->OSTCBY] &= ~ptcb->OSTCBBitX) == 0) { /* ... remove task from event ctrl block */ pevent->OSEventGrp &= ~ptcb->OSTCBBitY; } } ptcb->OSTCBDly = 0; /* Prevent OSTimeTick() from updating */ ptcb->OSTCBStat = OS_STAT_RDY; /* Prevent task from being resumed */ if (OSLockNesting < 255) { OSLockNesting++; } OS_EXIT_CRITICAL(); OSTaskDel in ucOS 42 OS_Dummy(); /* ... Dummy ensures that INTs will be */ OS_ENTER_CRITICAL(); /* ... disabled HERE! */ if (OSLockNesting > 0) { OSLockNesting--; } OSTaskDelHook(ptcb); /* Call user defined hook */ OSTaskCtr--; /* One less task being managed */ OSTCBPrioTbl[prio] = (OS_TCB *)0; /* Clear old priority entry */ if (ptcb->OSTCBPrev == (OS_TCB *)0) { /* Remove from TCB chain */ ptcb->OSTCBNext->OSTCBPrev = (OS_TCB *)0; OSTCBList = ptcb->OSTCBNext; } else { ptcb->OSTCBPrev->OSTCBNext = ptcb->OSTCBNext; ptcb->OSTCBNext->OSTCBPrev = ptcb->OSTCBPrev; } ptcb->OSTCBNext = OSTCBFreeList; /* Return TCB to free TCB list */ OSTCBFreeList = ptcb; OS_EXIT_CRITICAL(); OS_Sched(); /* Find new highest priority task */ return (OS_NO_ERR); } OS_EXIT_CRITICAL(); return (OS_TASK_DEL_ERR); } 挂起任务 ?挂起指定任务，直到通过唤醒任务对任务 进行解挂。 ?一个任务可以把自己挂起 ? 当任务把自己挂起后，会引起任务的调度，实时 内核将选取另外一个合适的任务进行执行。 ?任务被挂起后，该任务将处于等待状态 ?挂起任务通常需要进行以下工作： ?根据指定的 ID，获得对应任务的 TCB ?把任务的状态变为等待状态，并把 TCB放置 到等待队列 ?如果任务自己挂起自己，进行任务调度 43 INT8U OSTaskSuspend (INT8U prio) { BOOLEAN self; OS_TCB *ptcb; OS_ENTER_CRITICAL(); if (prio == OS_PRIO_SELF) { /* See if suspend SELF */ prio = OSTCBCur->OSTCBPrio; self = TRUE; } else if (prio == OSTCBCur->OSTCBPrio) { /* See if suspending self */ self = TRUE; } else { self = FALSE; /* No suspending another task */ } ptcb = OSTCBPrioTbl[prio]; if (ptcb == (OS_TCB *)0) { /* Task to suspend must exist */ OS_EXIT_CRITICAL(); return (OS_TASK_SUSPEND_PRIO); } if ((OSRdyTbl[ptcb->OSTCBY] &= ~ptcb->OSTCBBitX) == 0x00) { /* Make task not ready */ OSRdyGrp &= ~ptcb->OSTCBBitY; } ptcb->OSTCBStat |= OS_STAT_SUSPEND; /* Status of task is 'SUSPENDED' */ OS_EXIT_CRITICAL(); if (self == TRUE) { /* Context switch only if SELF */ OS_Sched(); } return (OS_NO_ERR); } OSTaskSuspend in ucOS 唤醒任务 ?根据任务 ID解挂指定的任务。 ?如果任务还在等待其他资源，任务解挂后仍 然处于等待状态 ; ?否则，解挂后的任务将处于就绪状态。 ?解挂任务通常需要进行以下工作： ?根据指定的 ID，获得对应任务的 TCB ?如果任务在等待其他资源，任务将仍然处于 等待状态；否则，把任务的状态变为就绪状 态，并把 TCB放置到就绪队列 ?进行任务调度 44 INT8U OSTaskResume (INT8U prio) { OS_TCB *ptcb; OS_ENTER_CRITICAL(); ptcb = OSTCBPrioTbl[prio]; if (ptcb == (OS_TCB *)0) { /* Task to suspend must exist */ OS_EXIT_CRITICAL(); return (OS_TASK_RESUME_PRIO); } if ((ptcb->OSTCBStat & OS_STAT_SUSPEND) != OS_STAT_RDY) { /* Task must be suspended */ if (((ptcb->OSTCBStat &= ~OS_STAT_SUSPEND) == OS_STAT_RDY) && /* Remove suspension*/ (ptcb->OSTCBDly == 0)) { /* Must not be delayed */ OSRdyGrp |= ptcb->OSTCBBitY; /* Make task ready to run */ OSRdyTbl[ptcb->OSTCBY] |= ptcb->OSTCBBitX; OS_EXIT_CRITICAL(); OS_Sched(); } else { OS_EXIT_CRITICAL(); } return (OS_NO_ERR); } OS_EXIT_CRITICAL(); return (OS_TASK_NOT_SUSPENDED); } OSTaskResume in ucOS 任务睡眠 ?使当前任务睡眠一段指定的时间，时间 到后，任务又重新回到就绪状态。 ?任务睡眠通常需要进行以下工作： ?修改任务状态，把任务状态变为等待状态 ?把任务 TCB放置到时间等待链 ?进行任务调度 45 关于任务扩展 ?任务扩展 ?便于应用能够向系统中添加一些关于任务的 附加操作 ?为应用提供在系统运行的关键点上进行干预 的手段 ?可把应用提供的函数挂接到系统中去 ?在创建任务、任务上下文发生切换或是任务 被删除的时候这些被挂接的函数能够得到执 行 关于任务扩展 ?任务扩展的时机通常包含以下情况： ?任务创建时 ?任务删除时 ?任务上下文切换时 ?任务扩展功能实现方式： ?任务扩展表 ?应用编程接口 46 typedef void (*extensionRoutine)(void); typedef struct { extensionRoutine extensionOfTaskCreate; extensionRoutine extensionOfTaskDelete; extensionRoutine extensionOfTaskSwitch; }taskExtensionTable; statusCode extensionCreate(taskExtensionTable *extensionTable，int *ID); statusCode extensionDelete(int extensionTableID); 任务扩展表处理任务扩展表处理 在任务扩展表处理方式中，任务扩展表用来存放实现任务扩展处理的例 程，实时内核通过查找任务扩展表来获取扩展处理的入口函数。 通过创建任务扩展表，把任务扩展例程添加到系统中去，通过删除任务 扩展表则可把任务扩展例程删除掉。 extensionRoutineOfTaskCreateAdd(); /*为任务创建时提供扩展处理例程*/ extensionRoutineOfTaskCreateDelete(); /*删除为任务创建提供的扩展处理例程*/ extensionRoutineOfTaskDeleteAdd(); /*为任务删除时提供扩展处理例程*/ extensionRoutineOfTaskDeleteDelete(); /*删除为任务删除提供的扩展处理例程*/ extensionRoutineOfTaskSwitchAdd(); /*为任务上下文切换时提供扩展处理例程*/ extensionRoutineOfTaskSwitchDelete(); /*删除为任务上下文切换提供的扩展处理例程*/ API 描述 通过单独的通过单独的 API实现任务扩展实现任务扩展 为任务创建、任务删除和任务上下文切换分别提供了添加和删除任务扩 展处理例程。 47 void OSIntCtxSw(void); void OSStartHighRdy(void); void OSTaskCreateHook(OS_TCB *ptcb); void OSTaskDelHook(OS_TCB *ptcb); void OSTaskStatHook(void); OS_STK *OSTaskStkInit(void (*task)(void *pd), void *pdata, OS_STK *ptos, INT16U opt); void OSTaskSwHook(void); void OSTimeTickHook(void); HOOK in ucOS void OSInit (void) { OSInitHookBegin(); /* Call port specific initialization code */ OS_InitMisc(); /* Initialize miscellaneous variables */ OS_InitRdyList(); /* Initialize the Ready List */ OS_InitTCBList(); /* Initialize the free list of OS_TCBs */ OS_InitEventList(); /* Initialize the free list of OS_EVENTs */ OS_InitTaskIdle(); /* Create the Idle Task */ OSInitHookEnd(); /* Call port specific init. code */ } HOOK used in OSInit in ucOS 48 任务变量 ?某些例程可能同时被多个任务调用，每个 调用任务又期望例程中的 全局 或是 静态变 量 提供不同的值。 ?多个任务都希望使用一个私有的内存区域， 而该内存区域又是通过全局变量的方式来提供 的情况。 ?内核可采用任务变量的处理方式。 任务变量 ?任务变量位于任务的上下文，属于任务 TCB的内容。 ?任务切换 ? 任务变量对应的全局或是静态变量的内容也需要 进行切换。 ? 如果当前任务拥有任务变量，需要把任务变量对 应全局或是静态变量的内容保存到该任务的任务 变量之中。 ? 如果即将投入运行的任务使用了任务变量，需要 把任务变量的内容恢复到对应的全局或是静态变 量中去。 49 任务变量 ?通过任务变量，多个任务可以把同一个 全局或是静态变量作为任务私有的变量 来使用。 ?其他任务对该变量的修改，不会影响这个变 量在调用任务中的值。 ?即该变量虽然是一个全局或是静态变量，但 是在单个任务中可以像私有变量一样使用。 pTaskVar TCB1 pTaskVar TCB2 globalData globalData globalData 全局变量或是静态变量的当前值 ①保存当前值到 TCB1 ②从 TCB2中恢复为 当前值 任务变量的切换任务变量的切换 TCB1为当前正在运行的任务的任务控制块，TCB2为需要执行的任务的任 务控制块。pTaskVar用来表示任务的任务变量。 50 任务变量 ?实时内核通常提供以下关于任务变量的 操作： ?向指定的任务中添加任务变量 ?删除指定任务的任务变量 ?获得指定任务的任务变量 ?获得指定任务当前拥有的任务变量的数量 ?获得指定任务的所有任务变量 第三节 任务调度 基于优先级的可抢占调度 时间片轮转调度 静态调度 动态调度 静态调度与动态调度之间的比较 51 ?任务调度要解决的问题 ?WHAT：按什么原则分配 CPU ? 任务调度算法 ?WHEN：何时分配 CPU ? 任务调度的时机 ?HOW： 如何分配 CPU ? 任务调度过程（任务的上下文切换） ?计算机发展初期 ?通常都要集中在计算机所在的地方，人为地以 作业（ job）的方式把工作内容一件一件地提交 给计算机进行处理，也就不存在调度的概念 ?随后，出现了计算机的批处理方式 ?计算机把作业按照 先来先服务 的方式进行处 理，体现了一种非常简单的调度概念 ?后来出现多道程序处理方式，调度才变得复 杂和重要起来 52 ?调度用来确定 多任务环境下任务执行的 顺序 和 在获得 CPU资源后能够执行的时 间长度 。 ?操作系统通过一个 调度程序 来实现调度 功能。 ?调度程序以函数的形式存在，用来实现操作 系统的调度算法。 ? 调度程序本身并不是一个任务，是一个函数调 用，可在内核的各个部分进行调用。 ?调用调度程序的具体位置又被称为是一个 调 度点 （ scheduling point），调度点通常处于 以下位置： ? 中断服务程序的结束位置； ? 任务因等待资源而处于等待状态； ? 任务处于就绪状态时等。 ?调度本身需要一定的系统开销，需要花费 时间来计算下一个可被执行的任务。 ?竭力使用 最优调度方案 往往并不是一个明智的 办法 ? 高级的调度程序通常具有不可预见性，需要花费更 多的时间和资源，并且，其复杂性也增加了应用编 程人员的使用难度。 ?简单是实时内核所强调的主要特点 ? 实用的实时内核在实现时大都采用了简单的调度算 法，以确保任务的 实时约束特性 和 可预见性 是可以 管理的。 ?复杂的、高级的调度算法则通常用于研究领域 53 ?内核的主要职责就是要确保所有的任务 都能够 满足任务的时间约束特性要求 ?时间约束特性来源于任务的不同需求（如截 止时间、 QoS等），且同一个任务在不同时 候也可能具有不同的时间约束特性。 ? 比如，机器人中用来控制行动的任务在障碍环境 下行走所需要考虑的约束特性就比行走在开放环 境下要多得多。 ?能够同时适应所有情况的调度算法是不存在 的。 ?调度算法研究 ?从 理论上 来说，最优调度只有在能够完全获知所有 任务在处理、同步和通信方面的需求，以及硬件的 处理和时间特性的基础上才能实现。 ? 实际的应用 很难实现，特别是需要获知的信息处于动态变 化的情况下。 ? 即使在这些需要的信息都是可以预见的情况下，常用的调 度问题仍然是一个 NP难题 。 ? 调度的复杂性将随调度需要考虑的任务和约束特性的数量 呈现出指数增长。 ?调度算法不能很好地适应系统负载和硬件资源不断 增长的系统。 ?当然，这并不意味着调度算法不能解决只有少量、 定义好的任务的应用的需求。 54 ?设计调度程序时，通常需要综合考虑如 下因素： ?CPU的使用率（ CPU utilization） ?输入 /输出设备的吞吐率 ?响应时间（ responsive time） ?公平性 ?截止时间 ?这些因素之间具有一定的冲突性。 ?比如可通过让更多的任务处于就绪状态来提 高 CPU的使用率，但这显然会降低系统的响 应时间。 ?调度程序的设计需要 优先考虑最重要的需 求 ，然后 在各种因素之间进行折中处理 。 ?调度算法 ?是在一个特定时刻用来确定将要运行的任务 的一组规则。 ?从 1973年 Liu和 Layland开始关于实时调度 算法的研究工作以来（ 1973年， Liu和 Layland发表了一篇名为 “Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment”的论文）， 相继出现了很多调度算法和方法。对于调 度方法，可以划分为以下三个主要的行 为： ?脱机配置 ?运行时调度 ?先验性分析 55 ?脱机配置 产生运行时调度所需要的静态 信息； ?运行时调度 在系统运行的时候根据不同 的事件在各个计算之间进行切换处理； ?先验性分析 根据静态配置信息和调度算 法在运行时的行为分析确定所有的时间 需求是否得到满足。 ?各种调度算法之间的差异在于它们在上 述三种行为之间的侧重点。 ?先验性分析通过测试来确定调度方法的可行 性，比如所有任务在运行时的时间约束特性 是否都能得到满足。 ?对于大量的实时调度方法而言，存在着 以下几类主要的划分方法： ?离线（ off-line）和在线（ on-line）调度 ?抢占（ preemptive）和非抢占（ non- preemptive）调度 ?静态（ static）和动态（ dynamic）调度 ?最佳（ optimal）和试探性（ heuristic）调度 56 ?离线调度和在线调度：根据获得调度信 息的时机。 ?离线调度 ： ? 运行过程中使用的调度信息在系统运行之前就确 定了，如时间驱动的调度。 ? 离线调度算法具有 确定性 ，但缺乏灵活性，适用 于那些特性能够预先确定，且不容易发生变化的 应用。 ?在线调度： ? 调度信息在系统运行过程中动态获得，如优先级 驱动的调度（如 EDF， RMS等）。 ? 在线调度算法在形成最佳调度决策上具有较大的 灵活性。 ?抢占式调度和非抢占式调度：任务在运行过程中 能否被打断的处理情况。 ?抢占式调度 ： ? 正在运行的任务可能被其他任务所打断。 ?非抢占式调度 ： ? 一旦任务开始运行，该任务只有在运行完成而主动放弃 CPU 资源，或是因为等待其他资源被阻塞的情况下才会停止运 行。 ?实时内核大都采用了抢占式调度算法，使关键任 务能够打断非关键任务的执行，确保关键任务的 截止时间能够得到满足。 ?抢占式调度 算法要更复杂些，且需要更多的资 源，并可能在使用不当的情况下会造成低优先级 任务出现长时间得不到执行的情况。 ?非抢占式调度 算法常用于那些任务需要按照预先 确定的顺序进行执行，且只有当任务主动放弃 CPU资源后，其他任务才能得到执行的情况。 57 ISR Low Priority Task High Priority Task ISR ISR make High Priority Task Ready ISR Completes (Return to Task) Low Priority Task Completes (Switch to HP Task) Interrupt Occurs Vector to ISR Non-Preemptive ISR Low Priority Task (LPT) High Priority Task (HPT) ISR ISR make High Priority Task Ready Interrupt Occurs Vector to ISR ISR Completes (Switch to HP Task) HP Task Completes (Switch back to LP Task) Preemptive 58 内核的可抢占性 ?内核可抢占与不可抢占：执行内核提供 的 系统调用 的过程中，是否可以被中断 打断。 ?可抢占内核：即使正在执行的是内核服 务函数，也能响应中断，并且中断服务 程序退出时能进行任务重新调度： ?如果有优先级更高的任务就绪，就立即让高 优先级任务运行，不要求回到被中断的任 务，将未完成的系统调用执行完。 内核的可抢占性 ?不可抢占内核：不可抢占内核有两种情况 ?内核服务函数不能被中断 。系统在执行内核服务函 数时处于关中断状态，不能响应外部可屏蔽中断， 这样就会在一定程度上延迟中断响应时间。 ?能被中断但是不能进行任务重新调度 。 ? 系统在执行内核服务函数时可以响应中断，不会延迟中断 响应时间； ? 但是在中断退出时不进行 任务重新调度 ，即使在中断服务 程序执行过程中有更高优先级的任务就绪，也必须回到被 中断的任务将未完成的内核函数执行完后，才能让高优先 级任务执行。 59 低优先级任务 内核服务 ISR 高优先级任务 时 间 (1) (2) (3) (4) (5) 不可抢占内核（允许中断） 低优先级任务 内核服务 ISR 高优先级任务 时 间 (1) (2) (3) (4) (5) 可抢占内核 60 ?静态调度和动态调度：根据任务优先级的确定 时机 ?静态调度 ： ? 所有任务的优先级在设计时就确定下来了，且在运行过程中 不会发生变化（如 RMS）。 ?动态调度 ： ? 任务的优先级则在运行过程中确定，并可能不断地发生变化 （如 EDF）。 ?静态调度 算法适用于能够完全把握系统中所有 任务及其时间约束（如截止时间、运行时间、 优先顺序和运行过程中的到达时间）特性的情 况。 ?静态调度比较简单，但缺乏灵活性，不利于系统扩 展； ?动态调度 有足够的灵活性来处理变化的系统情 况，但需要消耗更多的系统资源。 ?CPU的使用率 （ utilization） ?对于给定的一组任务，这些任务所使用的整个 CPU 资源的比率。 ?对于一个给定的调度算法，其 CPU使用率存在着一 个理论上的上限，如 EDF算法的最大 CPU使用率为 1。 ?可调度性 （ schedulability） ?对于给定的一组任务，如果所有任务都能满足截止 时间的要求，这些任务就是可调度的。 ?对于 在线调度 算法，当一个新的任务需要加入到系 统中时，应进行可调度性分析 ? 如果加入任务后会导致某些任务不能满足调度性，则该任 务就不能添加到系统中去 ?可调度性的程度 可以通过所有任务截止时间都能得 到满足的情况下的最大 CPU使用率来进行衡量。 61 基于优先级的可抢占调度 ?基于优先级的可抢占调度方式 ?如果出现具有 更高优先级 的任务处于就绪状 态时，当前任务将停止运行，把 CPU的控制 权交给具有更高优先级的任务，使更高优先 级的任务得到执行。 ?实时内核需要确保 CPU总是被具有最高 优先级的就绪任务所控制。 ?当一个具有比当前正在运行任务的优先级更 高的任务处于就绪状态的时候，实时内核应 及时进行 任务切换 ，保存当前正在运行任务 的上下文，切换到具有更高优先级的任务的 上下文。 任务1 任务2 任务3 优先级 高 低 时间 任务2就绪 任务3就绪 任务2 任务1 抢占 抢占 任务3运行结束 任务2运行结束 在可抢占调度方式下的任务运行情况在可抢占调度方式下的任务运行情况 任务1被具有更高优先级的任务2所抢占，然后任务2又被任务3抢占。当 任务3完成运行后，任务2继续执行。当任务2完成运行后，任务1才又得 以继续执行。 62 时间片轮转调度 ?时间片轮转调度（ round-robin scheduling）算法 ?当有 两个或多个就绪任务具有相同的优先 级 ，且它们是就绪任务中优先级最高的任务 时，任务调度程序按照这组任务就绪的先后 次序调度第一个任务，让第一个任务运行一 段时间，然后又调度第二个任务，让第二个 任务又运行一段时间，依次类推，到该组最 后一个任务也得以运行一段时间后，接下来 又让第一个任务运行。 ?任务运行的这段时间称为 时间片 （ time slicing）。 时间片轮转调度 ?在时间片轮转调度方式中 ?当任务运行完一个时间片后，该任务即使还 没有停止运行，也必须释放处理器让下一个 与它相同优先级的任务运行，使实时系统中 优先级相同的任务 具有平等的运行权利。 ?释放处理器的任务被排到同优先级就绪任务 链的链尾，等待再次运行。 63 时间片轮转调度 ?采用时间片轮转调度算法时，任务的 时间 片大小 要适当选择。 ?时间片大小的选择会影响系统的性能和效率： ? 时间片太大 ，时间片轮转调度就没有意义； ? 时间片太小 ，任务切换过于频繁，处理器开销大， 真正用于运行应用程序的时间将会减小。 ?不同的实时内核在实现时间片轮转调度算 法上可能有一些差异： ?有的内核允许同优先级的各个任务有不一致的 时间片； ?有的内核要求相同优先级的任务具有一致的时 间片。 任务1 任务2 任务3 优先级 高 低 时间 任务3就绪 任务3运行结束 任务1 任务2 任务1 任务2 在时间片轮转调度方式下的任务运行情况在时间片轮转调度方式下的任务运行情况 任务1和任务2具有相同的优先级，按照时间片轮转的方式轮流执行。当 高优先级任务3就绪后，正在执行的任务2被抢占，高优先级任务3得到 执行。当任务3完成运行后，任务2才重新在未完成的时间片内继续执 行。随后任务1和任务2又按照时间片轮转的方式执行。 64 静态调度 ?静态调度算法 ?任务的优先级需要在系统运行前进行确定。 ?确立任务优先级的主要依据为： ? 执行时间 。以执行时间为依据的调度算法为： o 最短执行时间优先（ smallest execution time first）； o 最长执行时间优先（ largest execution time first）。 ? 周期 。以周期为依据的调度算法为： o 短周期任务优先（ smallest period first）； o 长周期任务优先（ largest period first）。 静态调度 ? 任务的 CPU使用率。 任务的 CPU使用率为任务计 算时间与任务周期的比值 。以任务的 CPU使用率 为依据的调度算法为： o 最小 CPU使用率优先（ smallest task utilization first）； o 最大 CPU使用率优先（ largest task utilization first）。 ? 紧急程度。根据任务的紧急程度，以人为的方式 进行优先级的静态安排。 ?人为安排优先级 ?比率单调调度算法 65 人为安排优先级 ?人为安排优先级是嵌入式实时软件开发中使用 得非常多的一种方法。 ?以系统分析、设计人员对系统需求的理解为基 础，确定出系统中各个任务之间的相对优先情 况，并据此确定出各个任务的优先级。 webDisplay dataHandling dataRecv 1 请求 Web页面 2 请求 Web页面 3 请求 Web页面 4 Web数据 5 Web数据 6 解析后的 Web数据 在一个用来实现网页浏览的应用中，可把整个应用划分为网络数据接收 dataRecv、网页数据处 理dataHandling和网页显示 webDisplay等三个任 务。 由于dataRecv需要及时接收从网络传过来的数据，其优先级应最高； webDisplay需要及时处理用户的输入（如停止获取当前页面或是请求新 的页面等），其优先级应比dataHandling高。据此，可人为地把 dataRecv、dataHa ndling和webDisplay的优先级分别安排为5、7、6 （设定数字越大，任务的优先级越低）。 66 比率单调调度算法 1973年， Liu和 Layland在 ACM上发表了题为 “Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment”的论文，该 论文奠定了实时系统所有现代调度算法的理论 基础。 比率单调调度算法（ rate-monotonic scheduling algorithm， RMS）即在该论文中被提出来。 比率单调调度算法 RMS是基于以下假设的基础上进行分析的： A1. 所有任务都是 周期任务 ； A2. 任务的 相对截止时间 等于 任务的周期 ； A3. 任务在每个周期内的 计算时间 都相等，保 持为一个常量； A4. 任务之间不进行通信，也不需要同步； A5. 任务可以在计算的任何位置被抢占，不存 在临界区。 67 比率单调调度算法 ?尽管 Liu和 Layland把该调度算法定位于 单处理器的实时任务调度，但实验证明， 同样适用于分布式系统。 ?RMS是一个 静态的固定优先级调度算 法： ?任务的优先级与任务的周期表现为单调函数 关系 ? 任务周期越短，任务的优先级越高； ? 任务周期越长，任务的优先级越低。 ?RMS是静态调度中的 最优调度算法 ? 如果一组任务能够被任何静态调度算法所调度， 则这些任务在 RMS下也是可调度的。 比率单调调度算法 ?任务的可调度性 可以通过计算任务的 CPU使用 率，然后把得到的 CPU使用率同一个可调度的 CPU使用率上限进行比较来获得。 ?可调度的 CPU使用率上限被称为 可调度上限 （ schedulable bound）。 ? 表示给定任务在特定调度算法下能够满足截止时间要求的最 坏情况下的最大 CPU使用率。 ?可调度上限的最大值为 100%，与 调度算法 密切相 关。 ? 对于一组任务，如果任务的 CPU使用率小于或等于可调度上 限，则这组任务是可被调度的； ? 如果任务的 CPU使用率大于可调度上限，就不能保证这组任 务是可被调度的，任务的调度性需要进一步的分析。 68 比率单调调度算法 ?在 RMS中， CPU使用率的可调度范围为： )1( 2 1 1 ?≤ ∑ = n n i i i n T C 上述条件是一个 充分条件 ，但不是一个必要条件： ?如果任务的CPU使用率满足该条件， 则任务是可调度的； ?但如果不满足该条件，也有可能被RMS所调度。 比率单调调度算法 ?RMS的可调度的 CPU使用率上限 任务数量 可调度的 CPU使用率上限 1 1 2 0.828 3 0.780 4 0.757 5 0.743 6 0.735 … … ∞ ln2 69 任务 计算时间 周期 CPU使用 率 CPU使用 率之和 可调度上 限 1 1 5 0.20 0.20 1.00 2 5 20 0.25 0.45 0.83 3 8 50 0.16 0.61 0.78 4 12 100 0.12 0.73 0.76 满足满足 RMS调度条件的任务的执行情况调度条件的任务的执行情况 任务的计算时间、周期时间 、CPU使用率及其RMS要求的可调度上限 任务的执行情况 任务 计算时间 周期 CPU使用 率 CPU使用 率之和 可调度上 限 1 1 5 0.20 0.20 1.00 2 5 20 0.25 0.45 0.83 3 10 50 0.20 0.65 0.78 4 20 100 0.20 0.85 0.76 任务的计算时间、周期时间 、CPU使用率及其RMS要求的可调度上限 任务的执行情况 不满足不满足 RMS调度条件，但能够被调度执行的情况调度条件，但能够被调度执行的情况 70 比率单调调度算法 ?在任务比较多的情况下 ?RMS的可调度的 CPU使用率上限为 ln2，如此低的 CPU使用率对大多数的系统来说都是不可接受的。 ?对于 RMS来说，即使 CPU的使用率小于 100%，但如果大于了算法给定的可调度范 围，仍有可能不能满足截止时间的要求。 比率单调调度算法 ?RMS的不足之处还在于它假定任务是相互独立 的、周期性的，且任务能够在任何计算点被抢 占。 ?在实时系统中，任务之间通常都需要进行通信和同 步。 ?Rajkumar在博士论文（ Synchronization in Real-Time Systems: A Priority Inheritance Approach）中基于 RMS提出了可以处理任务同步的调度算法。 ? 解决了单处理器上任务之间的同步问题。 ? Rajkumar还解决了任务之间存在互斥执行的问题，允许任务 存在临界区，在执行临界区时，任务不能被其他任务所抢占。 71 比率单调调度算法 ?非周期任务的处理方式 : ? 以后台方式执行非周期任务 o 效率比较低，非周期任务只有在所有周期任务都没有 执行的情况下才会得到调度。 ? 把就绪的非周期任务组织成一个队列，然后 周期 性地查询该队列 是否有非周期任务的方式来执 行。 o 有可能出现刚查询完成，就有非周期任务就绪的情 况，导致该任务等待一个轮询周期才能得到调度执行 的情况。 动态调度 ?对于静态调度，任务的优先级不会发生变 化。 ?在动态调度中，任务的优先级可根据需要 进行改变，也可能随着时间按照一定的策 略自动发生变化。 ?截止时间优先调度算法 ?最短空闲时间优先调度算法 72 截止时间优先调度算法 ?RMS调度算法的 CPU使用率比较低，在任务比较 多的情况下，可调度上限为 68%。 ?Liu和 Layland又提出了一种采用动态调度的、具 有更高 CPU使用率的调度算法 —截止时间优先调 度算法 （ earliest deadline first， EDF）。 ?在 EDF中，任务的优先级根据任务的截止时间来 确定： ?任务的绝对截止时间越近，任务的优先级越高； ?任务的绝对截止时间越远，任务的优先级越低。 ?当有新的任务处于就绪状态时，任务的优先级就有可 能需要进行调整。 截止时间优先调度算法 ?同 RMS一样， Liu和 Layland对 EDF 算法的分析也是在一系列假设的基 础上进行的。 ?在 Liu和 Layland的分析中， EDF不 要求任务为周期任务，其他假设条 件与 RMS相同。 73 截止时间优先调度算法 ?EDF算法是 最优的单处理器动态调度算 法 ，其可调度上限为 100%。在 EDF调度算 法下，对于给定的一组任务，任务可调度 的充要条件为： 1 1 ≤ ∑ = n i i i T C 对于给定的一组任务，如果EDF不能满足其调度性要求，则没有其他调 度算法能够满足这组任务的调度性要求。 截止时间优先调度算法 ?同基于固定优先级的静态调度相比，采用基于 动态优先级调度的 EDF算法的显著优点在于： ?EDF的 可调度上限 为 100%，使 CPU的计算能力能 够被充分利用起来。 ?EDF也存在不足之处： ?在实时系统中不容易实现； ?同 RMS相比， EDF具有 更大的调度开销 ，需要在系 统运行的过程中动态地计算确定任务的优先级； ?在系统出现临时过载的情况下， EDF算法不能确定 哪个任务的截止时间会得不到满足。 74 截止时间优先调度算法 ?Liu和 Layland提出了一种 混合的调度算 法 ： ?大多数任务都采用 RMS进行调度，只有少 量任务采用 EDF调度算法。 ?尽管混合的调度算法不能达到 100%的 CPU 使用率，但确实综合了 EDF和 RMS调度算法 的优点，使整个调度比较容易实现。 任务 到达时间 计算时间 绝对截止时间 T 1 0 10 30 T 2 4 3 10 T 3 5 10 25 任务及其到达时间、计算时间与绝对截止时间 当任务T1到达的时候，由于T1是系统中等待运行的唯一一个任务，因此 T1得到立即执行。任务T2在时间4到达，由于任务T2的截止时间（10） 小于任务T1的截止时间（30），因此任务T2的优先级比T1高，并抢占任 务T1得到执行。任务T3在时间5到达，由于T3的截止时间比T2的截止时 间大，因此T3的优先级T2比低，需要等到T2执行完成后，才能得到执 行。当T2执行完成后（时间7），T3开始执行（T3的优先级比T1高）。 T3运行到时间17，T1才能继续执行直到运行结束。 75 最短空闲时间优先调度算法 在最短空闲时间优先调度算法（ least- laxity-first scheduling）中，任务的优 先级根据任务的 空闲时间 进行动态分 配： ? 任务的空闲时间越短，任务的优先级越高； ? 任务的空闲时间越长，任务的优先级越低。任 务的空闲时间可通过来表示： 任务的空闲时间 = 任务的绝对截止时间 - 当前时间 - 任务的剩余执行时间 静态调度与动态调度之间的比较 ?动态调度的出现是为了确保低优先级任务 也能被调度。 ?对于所有任务都具有 同等重要程度 的系统比 较合适； ?对于需要 绝对可预测性 的系统一般不使用动 态调度： ? 在出现临时过载的情况下，要求调度算法能够选 择最紧急的任务执行，而放弃那些不太紧急的任 务。 ? 而动态调度的优先级只反映了任务的时间特性， 没有把任务的 紧急程度 体现到优先级中去。 76 静态调度与动态调度之间的比较 ?动态调度的调度代价通常都比静态调度高： ?动态调度在每一个调度点都需要对任务的优先级进 行重新计算， ?静态调度中任务的优先级则始终保持不变，不需要 进行计算。 第四节 优先级反转 优先级继承协议 优先级天花板协议 77 ?理想情况下 ?高优先级任务就绪后，能够立即抢占低优先级任务而 得到执行。 ?但在有多个任务需要使用 共享资源 的情况下，可 能会出现高优先级任务被低优先级任务阻塞，并 等待低优先级任务执行的现象。 ?优先级反转 （ priority inversion）：高优先级任 务需要等待低优先级任务释放资源，而低优先级 任务又正在等待中等优先级任务的现象。 ?两个任务都试图访问共享数据的情况即为出现 优先级反转最通常的情况。 ?为了保证一致性，这种访问应该是顺序进行的。 ? 如果高优先级任务首先访问共享资源，则会保持共享资源 访问的合适的任务优先级顺序； ? 如果是低优先级任务首先获得共享资源的访问，然后高优 先级任务请求获取对共享资源的访问，高优先级任务将被 阻塞，直到低优先级任务完成对共享资源的访问。 ?阻塞 是优先级反转的一种形式，它使得高优先 级任务必须等待低优先级任务的处理。 ?如果阻塞的时间过长，即使在 CPU使用率比较低的 情况下，也可能出现截止时间得不到满足的情况。 78 ?通常的同步互斥机制为信号量 （ semaphore）、锁（ lock）和 Ada中的 Rendezvous（汇合）等。 ?为保护共享资源的一致性，或是确保非 抢占资源在使用上的合适顺序，使用这 些方法是非常必须的。 ?直接应用这些同步互斥机制将导致系统 中出现 不定时间长度的优先级反转 和 比 较低的任务可调度性 情况。 t 0 t 01 t 2 t 3 t 4 t 5 t 6 t 7 t 8 Critical section guarded by S time τ 1 τ 2 τ 3 t 9 t 0 t 10 t 11 t 12 t 13 t 14 t 15 t 16 t 18 t 17 假设T1，T2，T3为优先级顺序降低的三个任务，T1具有最高优先级。假 定T1和T3通过信号量S共享一个数据结构，并且，在时刻t1，任务T3获 得信号量S，开始执行临界区代码。在T3执行临界区代码的过程中，高 优先级任务T1就绪，抢占任务T3 而获得CPU资源，并在随后试图使用共 享数据，但该共享数据已被T1通过信号量S加锁。在这种情况下，会期 望具有最高优先级的任务T1被阻塞的时间不超过任务T3执行完整个临界 区的时间。但事实上，这种 阻塞时间的长度是无法预知 的。这主要是由 于任务T3还可能被具有中等优先级的任务T2所阻塞，使得T1也需要等待 T2和其他中等优先级的 任务释放CPU资源。 79 ?任务 T1的阻塞时间长度不定，可能会很长。 ?如果任务在临界区内不允许被抢占，这种情况可得 到部分解决。但由于形成了不必要的阻塞，使得这 种方案只适合于非常短的临界区。 ?比如，一旦一个低优先级任务进入了一个比较长的 临界区，不会访问该临界区的高优先级任务将会被 完全不必要的阻塞。 ?Lampson在 1980年发表的题为 “Experiences with processes and monitors in Mesa”的论文中 首先讨论关于优先级反转的问题： ?建议 临界区执行在比可能使用该临界区的所有任务 的优先级更高的优先级上 。 ?解决优先级反转现象的常用协议为： ?优先级继承协议（ priority inheritance protocol）； ?优先级天花板协议（ priority ceiling protocol）。 80 优先级继承协议 优先级继承协议的基本思想是： 当一个任务阻塞了一个或多个高优先级任 务时，该任务将不使用其原来的优先级，而使 用 被该任务所阻塞的所有任务的最高优先级 作 为其 执行临界区的优先级 。 当该任务退出临界区时，又恢复到其最初 的优先级。 t 0 t 01 t 2 t 3 t 4 t 5 t 6 t 7 t 8 Critical section guarded by S time τ 1 τ 2 τ 3 t 9 t 0 t 10 t 11 t 12 t 13 t 14 t 15 t 16 t 18 t 17 如果任务T1被T3阻塞，优先级继承协议要求任务T3以任务T1的优先级执 行临界区。这样，任务T3在执行临界区的时候，原来比T3具有更高优先 级的任务T2就不能抢占T3了。当T3退出临界区时，T3又恢复到其原来的 低优先级，使任务T1又成为最高优先级的任务。这样任务T1会抢占任务 T3而继续获得CPU资源，而不会出现T1会无限期被任务T2所阻塞。 81 优先级继承协议 ?优先级继承协议的定义 ?如果任务 T为具有最高优先级的就绪任务，任务 T将 获得 CPU资源。 ?在任务 T进入临界区前，任务 T需要首先请求获得该 临界区的信号量 S： ? 如果信号量 S已经被加锁，则任务 T的请求会被拒绝。 o 在这种情况下，任务 T被称为是 被拥有信号量 S的任务所阻 塞 ； ? 如果信号量 S未被加锁，任务 T将获得信号量 S而进入临界 区。 o 当任务 T退出临界区时，使用临界区过程中所加锁的信号量 将被解锁。 o 如果有其他任务因为请求信号量 S而被阻塞，其中具有最高 优先级的任务将被激活，处于就绪状态。 优先级继承协议 ?任务 T将保持其被分配的原有优先级不变， 除非任务 T进入了临界区并 阻塞了更高优先 级的任务 。 ? 如果由于任务 T进入临界区而阻塞了更高优先级 的任务，任务 T将继承 被任务 T阻塞的所有任务 的最高优先级 ，直到任务 T退出临界区。 ? 当任务 T退出临界区时，任务 T将恢复到进入临 界区前的原有优先级； ?优先级继承具有传递性 。 ? 比如，假设 T1， T2， T3为优先级顺序降低的三 个任务，如果任务 T3阻塞了任务 T2，此前任务 T2又阻塞了任务 T1，则任务 T3将通过任务 T2继 承任务 T1的优先级。 82 优先级继承协议 ?在优先级继承协议中，高优先级任务在两种情 况下可能被低优先级任务所阻塞： ?直接阻塞 ? 如果高优先级任务试图获得一个已经被加锁的信号量，该 任务将被阻塞，这种阻塞即为直接阻塞； ? 直接阻塞用来确保临界资源使用的一致性能够得到满足 。 ?间接阻塞 ? 由于低优先级任务继承了高优先级任务的优先级，使得 中 等优先级的任务 被原来分配的低优先级任务阻塞，这种阻 塞即为间接阻塞。 ? 间接阻塞也是必须的，用来 避免高优先级任务被中等优先 级任务间接抢占 。 优先级继承协议 ?优先级继承协议具有如下特性： ?只有在高优先级任务与低优先级任务共享临 界资源，且低优先级任务已经进入临界区 后，高优先级任务才可能被低优先级任务所 阻塞； ?高优先级任务被低优先级任务阻塞的最长时 间为： ? 高优先级任务中可能被所有低优先级任务阻塞的 具有最长执行时间的临界区的执行时间； ?如果有 m个信号量可能阻塞任务 T，则任务 T最多被阻塞 m次。 83 优先级继承协议 ?采用优先级继承协议， 系统运行前就能 够确定任务的最大阻塞时间 。 ?但优先级继承协议存在以下两个方面的 问题： ?优先级继承协议本身不能避免 死锁 的发生； ?在优先级继承协议中，任务的阻塞时间虽然 是有界的，但由于可能出现 阻塞链 ，使得任 务的阻塞时间可能会很长。 t 0 t 01 t 2 t 3 t 4 t 5 t 6 t 7 t 8 Critical section guarded by S time τ 1 τ 2 t 9 t 0 t 10 t 11 t 12 t 13 t 14 t 15 t 16 t 18 t 17 假定在时间t1，任务T2获得信号量S2，进入临界区。 在时间t3，任务T2又试图获得信号量S1，但一个高优先级任务T1在这个 时候就绪，抢占任务T2并获得信号量S1，接下来任务T1又试图获得信号 量S2。 这样就出现了 死锁现象 。 84 t 0 t 01 t 2 t 3 t 4 t 5 t 6 t 7 t 8 Critical section guarded by S time τ 1 τ 2 τ 3 t 9 t 0 t 10 t 11 t 12 t 13 t 14 t 15 t 16 t 18 t 17 假定任务T1需要顺序获得信号量S1和S2； 任务T3在S1控制的临界区中被T2抢占，然后T2进入S2控制的临界区。 这个时候，任务T1被激活而获得CPU 资源，发现信号量S1和S2都分别被 低优先级任务T2和T3加锁，使得T1将被阻塞两个临界区，需要先等待任 务T3释放信号量S1，然后等待任务T2释放信号量S2，这样就形成了关于 任务T1的阻塞链 。 优先级天花板协议 ?使用优先级天花板协议的目的在于解决 优先级继承协议中存在的 死锁 和 阻塞链 问题。 ?优先级天花板指控制访问临界资源的 信 号量的优先级天花板 。 ?信号量的优先级天花板为所有使用该信号量 的任务的最高优先级。 ?在优先级天花板协议中，如果任务获得 信号量，则在任务执行临界区的过程 中，任务的优先级将被抬升到所获得信 号量的优先级天花板。 85 优先级天花板协议 ?在优先级天花板协议中，主要包含如下 处理内容： 1）对于控制临界区的信号量，设置信号量 的 优先级天花板 为可能申请该信号量的所有 任务中具有最高优先级任务的优先级； 2）如果任务成功获得信号量，任务的优先 级将被抬升为信号量的优先级天花板；任务 执行完临界区，释放信号量后，其优先级恢 复到其最初的优先级； 3）如果任务不能获得所申请的信号量，任 务将被阻塞。 优先级天花板协议 ?假设系统中存在 T1， T2， T3三个优先级顺序降低 的任务（优先级分别为 p1、 p2、 p3）。假定 T1和 T3通过信号量 S共享一个临界资源。根据优先级 天花板协议，信号量 S的优先级天花板为 p1。假定 在时刻 t1， T3获得信号量 S，按照优先级天花板协 议， T3的优先级将被抬升为信号量 S的优先级天 花板 p1，直到 T3退出临界区。这样， T3在执行临 界区的过程中， T1和 T2都不能抢占 T3，确保 T3能 尽快完成临界区的执行，并释放信号量 S，退出临 界区。当 T3退出临界区后， T3的优先级又回落为 p3。此时，如果 T3在执行临界区的过程中，任务 T1或 T2已经就绪，则 T1或 T2将抢占 T3的执行。 86 t 0 t 0 t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 Critical section guarded by S time τ 1 τ 2 τ 3 t 9 t 0 t 10 t 11 t 12 t 13 t 14 t 15 t 16 t 18 t 17 假设系统中存在T1，T2，T3三个优先级顺序降低的任务（优先级分别为 p1、p2、p3）。假定T1和T3通过信号量S共享一个临界资源。根据优先 级天花板协议，信号量S的优先级天花板为p1。假定在时刻t1，T3获得 信号量S，按照优先级天花板协议，T3的优先级将被抬升为信号量S的优 先级天花板p1，直到T3退出临界区。这样，T3在执行临界区的过程中， T1和T2都不能抢占T3，确保T3能尽快完成临界区的执行，并释放信号量 S，退出临界区。当T3退出临界区后，T3的优先级又回落为p3。此时， 如果T3在执行临界区的过程中，任务T1或T2已经就绪，则T1或T2将抢占 T3的执行。 优先级天花板协议 优先级继承协议和优先级天花板协议都 能解决优先级反转问题，但在处理效率 和对程序运行流程的影响程度上有所不 同。 87 优先级天花板协议 ?关于执行效率的比较 ?优先级继承协议 可能多次改变占有某临界资 源的任务的优先级，而 优先级天花板协议 只 需改变一次。 ?从这个角度看， 优先级天花板协议 的效率 高，因为若干次改变占有资源的任务的优先 级会引入更多的额外开销，导致任务执行临 界区的时间增加。 t 0 t 01 t 2 t 3 t 4 t 5 t 6 t 7 t 8 τ 1 τ 2 τ 3 Critical section guarded by S time τ 4 τ 5 τ 6 τ 7 t 9 t 0 t 10 t 11 t 12 t 13 t 14 t 15 t 16 t 18 t 17 Critical section in τ 7 guarded by S after 1 st ，2 nd ，3 rd ，4 th ，5 th priority inheritance respectively 假设系统中有七个任务，按优先级从高到底分别为：T1，T2，T3，T4， T5，T6，T7，使用由信号量S控制的临界资源。 图中，对于一个任务来说，单横线处于低端位置时，表示对应任务被阻 塞，或是被高优先级任务所抢占。单横线处于高端位置时，表示任务正 在执行。如果没有单横线，表示任务还未被初始化，或是任务已经执行 完成 。 阴影部分表示任务正在执行临界区 。 采用优先级继承协议的任务执行情况采用优先级继承协议的任务执行情况 88 假设系统中有七个任务，按优先级从高到底分别为：T1，T2，T3，T4， T5，T6，T7，使用由信号量S控制的临界资源。 图中，对于一个任务来说，单横线处于低端位置时，表示对应任务被阻 塞，或是被高优先级任务所抢占。单横线处于高端位置时，表示任务正 在执行。如果没有单横线，表示任务还未被初始化，或是任务已经执行 完成 。 阴影部分表示任务正在执行临界区 。 采用优先级天花板协议的任务执行情况采用优先级天花板协议的任务执行情况 t 0 t 0 t 1 t 2 t 3 t 4 t 5 t 6 t 7 t 8 τ 1 τ 2 τ 3 Critical section guarded by S time τ 4 τ 5 τ 6 τ 7 t 9 t 0 t 10 t 11 t 12 t 13 t 14 t 15 t 16 t 18 t 17 优先级天花板协议 ?对程序运行过程影响程度的比较 ?优先级天花板协议的特点是一旦任务获得某 临界资源，其 优先级就被抬升到可能的最高 程度 ，不管此后在它使用该资源的时间内是 否真的有高优先级任务申请该资源，这样就 有可能影响某些 中间优先级任务 的完成时 间。 ?但在优先级继承协议中，只有当高优先级任 务申请已被低优先级任务占有的临界资源这 一事实发生时，才抬升低优先级任务的优先 级，因此优先级继承协议对任务执行流程的 影响相对要较小。