实时操作系统-任务管理与调度-共92页PPT课件

1、嵌入式实时操作系统及应用开发第五章 任务管理与调度主要内容进程与线程任务任务管理任务调度优先级反转第一节进程与线程 程序运行的方式进程的定义线程的定义程序的运行方式顺序运行 作业的运行总是一个一个地顺着来，完成一个作业后再运行下一个。在一个作业运行中途，决不会突然插入另一个作业运行。 顺序运行最容易实现，常见于早期的单道批处理系统中 程序的运行方式并发运行 允许多个程序共享CPU，在这种方式下，系统的资源不再被某一个程序独占，而是由多个程序共享。 简单地说，就是能用一个处理器并发（注意，不是同时！ ）地运行多个程序的计算机管理系统。并发：由同一个处理器轮换地运行多个程序。或者说是由多个程序轮班

2、地占用处理器这个资源。且在占用这个资源期间，并不一定能够把程序运行完毕。并发过程示意图处理器如何进行程序的切换？程序的切换（两句话）处理器是个傻瓜，PC让它干啥，它就干啥。PC是个指路器，它指向哪儿，处理器就去哪儿。从此可以知道，哪个程序占有了PC，哪个程序就占有了处理器。 = PC进程与程序进程与程序程序是存放在磁盘上的一系列代码和数据的可执行映像，是一个静止的实体。进程：可并发执行的程序在一个数据集合上的运行过程。程序是静止的，进程是动态的，有状态转换。进程与程序进程的四要素 ：1、作为一个进程，要有一段程序供其执行。2、有进程专用的内核空间堆栈。 3、在内核中有一个task_struct

3、数据结构，即“进程控制块”。 4、有独立的用户空间 线程的引入早期的进程，包含了以下两个方面的内容： 资源。进程是资源分配的基本单位，一个进程包括一个保存进程映像的虚拟地址空间、主存、I/O设备和文件等资源。调度执行。进程作为操作系统的调度实体，是调度的基本单位。 进程是一个庞大的结构型实体，其PCB结构包含的内容相当多，每创建一个进程，系统无论在时间或空间上都要花费较大的开支。线程定义线程是进程的一个实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈),一个线程可以创建和撤销另

4、一个线程； 使用线程的优势：创建：在一个已有进程中创建一个新线程比创建一个全新的进程所需的时间开销少；终止：终止一个线程比终止一个进程所花费的时间少；切换：线程切换比进程切换所花费的时间少；通信：使同一进程内部不同线程之间的通信效率得到显著提高。在大多数操作系统中，不同进程之间的通信需要内核的干预，而同一进程内部不同线程之间则可直接通信。 单进程/单线程模型单进程/多线程模型多进程/多线程模型多进程/单线程模型第二节任 务 任务的定义及其主要特性任务的内容任务的分类任务参数任务在嵌入式实时系统中任务（task）：任务是一个具有独立功能的无限循环的程序段的一次运行活动通常为进程（process）

5、和线程（thread）的统称任务是调度的基本单位High Priority TaskLow Priority TaskTaskTaskTaskTaskTaskTaskEventEventEach TaskInfinite LoopImportanceSplitting an application into Tasks任务任务通常包含一个具有无限循环的程序/*ioTask implements data obtaining and handling continuously*/void ioTask(void)int data;initial();/*The following sentenc

6、es get data and handle data continuously*/while(TRUE)data = getData();handleData(data);任务 任务的特性： 动态性 并发性 异步独立性任务 任务的内容 ： 代码：一段可执行的程序。 数据：程序所需要的相关数据(变量、工作空间、缓冲区) 堆栈 程序执行的上下文环境TCB 任务代码任务堆栈内存处理器PCSP任务运行时与 处理器之间的关系处理器通过两个指针寄存器（PC和SP）来与任务代码和任务堆栈建立联系并运行它寄存器组程序运行环境任务代码任务堆栈内存处理器PCSP多任务时的问题任务代码任务堆栈内存任务代码任务堆栈

7、内存？当有多个任务时，处理器中的运行环境应该怎么办？寄存器组程序运行环境程序 虚拟处理器PCSP 虚拟处理器PCSP 虚拟处理器PCSP 虚拟处理器PCSP调度器多任务时任务与处理器 之间关系的处理程序处理器PCSP在内存中为每个任务创建一个虚拟的处理器（处理器部分的运行环境由操作系统的调度器按某种规则来进行这两个复制工作复制当需要运行某个任务时就把该任务的虚拟处理器复制到实际处理器中复制当需要中止当前任务时，则把任务对应的虚拟处理器复制到内存复制再把另一个需要运行的任务的虚拟处理器复制到实际处理器中寄存器组寄存器组也就是说，任务的切换是任务运行环境的切换虚拟处理器应该存储的主要信息：1。程序

8、的断点地址（PC）2。任务堆栈指针（SP）3。程序状态字寄存器（PSW）4。通用寄存器内容5。函数调用信息（已存在于堆栈）另外再用一个数据结构保存任务堆栈指针（SP），这个数据结构叫做任务控制块，它除了保存任务堆栈指针之外还要负责保存任务其他信息。这些内容通常保存在任务堆栈中，这些内容也常叫做任务的上下文。任务控制块是由操作系统另行构造的一个数据结构，每个任务都有一个。任务代码任务堆栈内存任务控制块其实，程序切换的关键是把程序的私有堆栈指针赋予处理器的堆栈指针SP实质上系统是通过SP的切换来实现程序的切换的。要建立一个概念：具有控制块的程序才是一个可以被系统所运行的任务。程序代码、私有堆栈、任

9、务控制块是任务的三要件。任务控制块提供了运行环境的存储位置。任务任务与程序的区别：任务能真实地描述工作内容的并发性，而程序不能；程序是任务的组成部分；除程序外，任务还包括数据、堆栈及其上下文环境等内容；程序是静态的，任务是动态的；任务有生命周期，有诞生、有消亡，是短暂的；而程序是相对长久的；一个程序可对应多个任务，反之亦然；任务具有创建其他任务的功能，而程序没有。任务任务的分类 ：按照到达情况的可预测性，任务可以划分为：周期任务（periodic task），非周期任务（ non-periodic task）按照重要程度，可分为：关键任务（critical task），非关键任务（noncri

10、tical task） 任务1任务2任务3内核内核代码内核数据栈数据任务控制块代码栈数据任务控制块代码栈数据任务控制块代码任务1任务2任务3多任务系统示意图任务任务任务的参数优先级（priority）：任务的优先级分为静态优先级和动态优先级。周期（period）：表示任务周期性执行的间隔时间。计算时间（computation time）：也被称为是任务的执行时间（execution time）。就绪时间（ready time）：具备了被执行所需要条件时的时间 截止时间（deadline）：任务需要在该时间到来之前被执行完成。截止时间可以分为强截止时间（hard deadline）和弱截止时间（

11、soft deadline）两种情况：拥有关键任务的实时系统又被称为强实时统，否则称为弱实时系统。 第三节任务管理任务状态与变迁任务控制块任务切换任务队列优先级位图算法任务管理机制任务的管理-任务状态与变迁任务会在不同的状态之间进行转换，即任务状态的变迁就绪态运行态等待态获得CPU被高优先级任务抢占或超时获得资源需要资源任务状态变迁任务1任务2任务3调度程序05101520253035404550运行等待就绪三个任务进行状态转换的过程 包含三个任务和一个调度程序。调度程序用来确定下一个需要投入运行的任务，因此调度程序本身也需要占用一定的处理时间。 任务的管理-任务状态与变迁任务的状态及其转换正

12、在运行的任务，需要等待一段时间或需要等待一个事件发生再运行时，该任务就会把CPU的使用权让给别的任务而使任务进入等待状态。 任务在没有被配备任务控制块或被剥夺了任务控制块时的状态叫做任务的睡眠状态 系统为任务配备了任务控制块且在任务就绪表中进行了就绪登记，这时任务的状态叫做就绪状态。 处于就绪状态的任务如果经调度器判断获得了CPU的使用权，则任务就进入运行状态 一个正在运行的任务一旦响应中断申请就会中止运行而去执行中断服务程序，这时任务的状态叫做中断服务状态 由于系统存在着多个任务，于是系统如何来识别并管理一个任务就是一个需要解决的问题。识别一个任务的最直接的办法是为每一个任务起一个名称。 系

13、统必须为每个任务创建一个保存与该任务有关的相关信息的数据结构，这个数据结构就叫做该任务的任务控制块（TCB）。任务的管理-任务控制块用来记录任务的堆栈指针、任务的当前状态、任务的优先级别等一些与任务管理有关的属性的表就叫做任务控制块 任务控制块是不是像我们人在一个国家中的身份证？（其实，系统中的所有资源都应该有身份证。）任务控制块就相当于是一个任务的身份证，没有任务控制块的任务是不能被系统承认和管理的 task nametask IDtask statustask prioritytask context（registers and flags of CPU）任务控制块示意图任务的管理-任务控

14、制块任务在内存中的结构任务切换任务切换（context switching）保存当前任务的上下文，并恢复需要执行的任务的上下文的过程。当发生任务切换时：当前正在运行的任务的上下文就需要通过该任务的任务控制块保存起来；把需要投入运行的任务的上下文从对应的任务控制块中恢复出来。任务1任务2任务3调度程序05101520253035404550运行等待就绪在时刻8即发生了任务切换，任务1的上下文需要保存到任务1的任务控制块中去。经过调度程序的处理，在时刻10任务2投入运行，需要把任务2的任务控制块中关于上下文的内容恢复到CPU的寄存器中。 任务的管理-任务切换任务1任务2实时内核调度程序保存任务1的

15、上下文到TCB1从TCB2恢复任务2的上下文保存任务2的上下文到TCB2从TCB1恢复任务1的上下文时间任务的管理-任务切换任务切换任务切换具有如下基本步骤： 保存任务上下文环境；更新当前处于运行状态的任务的任务控制块的内容，如把任务的状态由运行状态改变为就绪或是等待状态；把任务的任务控制块移到相应的队列（就绪队列或是等待队列）；选择另一个任务进行执行：调度；改变需要投入运行的任务的任务控制块的内容，把任务的状态变为运行状态；根据任务控制块，恢复需要投入运行的任务的上下文环境。任务的管理-任务上下文切换时间 保 存 调 度 恢 复 保存当前运行任务上下文的时间选择下一个任务的调度时间将要运行任

16、务的上下文的恢复时间取决于任务上下文的定义和处理器的速度。不同种类的处理器，任务上下文的定义不同，其内容有多有少。任务的管理-任务切换任务切换时机中断、自陷运行任务因缺乏资源而被阻塞时间片轮转调度时高优先级任务处于就绪时任务的管理-任务队列任务队列通过任务控制块实现对系统中所有任务的管理新任务CPU就绪队列等待队列超时调度等待资源获得资源释放CPU单就绪队列和单等待队列任务的管理-任务队列队列由任务控制块构成 task nametask IDtask statustask prioritytask contexttask nametask IDtask statustask priorityt

17、ask contexttask nametask IDtask statustask prioritytask contextHead队列TCB1TCB2TCBnNULL任务队列新任务CPU就绪队列资源1等待队列超时调度等待资源1获得资源1释放CPU资源2等待队列等待资源2获得资源2资源n等待队列等待资源n获得资源n单就绪队列和多等待队列任务的管理-任务队列任务的管理-优先级位图就绪任务处理算法 为了能够使系统清楚地知道，系统中哪些任务已经就绪，哪些还没有就绪，OS在RAM中设立了一个记录表，系统中的每个任务都在这个表中占据一个位置，并用这个位置的状态（1或者0）来表示任务是否处于就绪状态，这

18、个表就叫做任务就绪状态表，简称叫任务就绪表 任务就绪表就是一个二维数组OSRdyTbl 为加快访问任务就绪表的速度，系统定义了一个变量OSRdyGrp来表明就绪表每行中是否存在就绪任务。任务的管理-优先级位图就绪任务处理算法 35: 00100011下标二进制值000000001100000010200000100300001000400010000500100000601000000710000000优先级映射表priorityMapTablechar priorityMapTable8 = 0 x01, 0 x02, 0 x04, 0 x08, 0 x10, 0 x20, 0 x40, 0

19、 x80;priorityMapTable的数组元素的下标与任务优先级的高三位或低三位相对应。 priorityMapTable的数组元素对应的二进制值中，位为1的位表示priorityReadyGroup或是priorityReadyTable的对应位也为1。35: 00100011Char priorityDecisionTable = 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0

20、, 2, 0, 1, 0,4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,4, 0,

21、 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,4, 0, 1, 0, 2, 0, 1, 0,

22、 3, 0, 1, 0, 2, 0, 1, 0,/* 0 x00 to 0 x0F */* 0 x10 to 0 x1F */* 0 x60 to 0 x6F */* 0 x70 to 0 x7F */* 0 x80 to 0 x8F */* 0 x90 to 0 x9F */* 0 xA0 to 0 xAF */* 0 xB0 to 0 xBF */* 0 xC0 to 0 xCF */* 0 xD0 to 0 xDF */* 0 xE0 to 0 xEF */* 0 x20 to 0 x2F */* 0 x30 to 0 x3F */* 0 x40 to 0 x4F */ /* 0 x50

23、 to 0 x5F */* 0 xF0 to 0 xFF */priorityReadyTable3 contains 0 xE4priorityReadyGroup contains 0 x68;3 = priorityDecisionTable 0 x68 ;2 = priorityDecisionTable 0 xE4 ;26 = (3 3;priorityReadyTablepriority 3 |= priorityMapTablepriority & 0 x07;35: 00100 011OSRdyGrp765432107654321015141312111098232221201

24、918171631302928272625243938373635343332474645544342414055545352515049486362616059585756OSRdyTblOSRdyTbl0OSRdyTbl1OSRdyTbl2OSRdyTbl3OSRdyTbl4OSRdyTbl5OSRdyTbl6OSRdyTbl70001000000001000任务退出就绪态 if(priorityReadyTablepriority 3 &= priorityMapTable priority & 0 x07) = = 0)priorityReadyGroup &= priorityMap

25、Table priority 3; 35: 00100 011OSRdyGrp765432101514131211109823222120191817163130292827262524393837363534333247464554434241405554535251504948636261605958575676543210OSRdyTbl 00001000-11110111 00010000-11101111OSRdyTbl0OSRdyTbl1OSRdyTbl2OSRdyTbl3OSRdyTbl4OSRdyTbl5OSRdyTbl6OSRdyTbl7获取进入就绪态的最高优先级 high3

26、Bit = priorityDecisionTable priorityReadyGroup;low3Bit = priorityDecisionTable priorityReadyTablehigh3Bit; priority = (high3Bit 4=high3Bit 0 x88-3=low3BitOSRdyTbl0OSRdyTbl1OSRdyTbl2OSRdyTbl3OSRdyTbl4OSRdyTbl5OSRdyTbl6OSRdyTbl7任务管理机制任务管理用来实现对任务状态的直接控制和访问。创建任务删除任务挂起任务唤醒任务设置任务属性改变任务优先级获取任务信息任务的管理机制-创建任

27、务任务创建通常需要完成以下工作：获得任务控制块TCB根据实时内核用户提供的信息初始化TCB为任务分配一个可以唯一标识任务的ID使任务处于就绪状态，把任务放置到就绪队列进行任务调度处理任务的管理机制-删除任务任务删除通常需要进行以下工作：根据指定的ID，获得对应任务的TCB把任务的TCB从队列中取出来，挂入空闲TCB队列释放任务所占用的资源任务的管理机制-挂起任务 挂起任务通常需要进行以下工作：根据指定的ID，获得对应任务的TCB把任务的状态变为等待状态，并把TCB放置到等待队列如果任务自己挂起自己，进行任务调度任务的管理机制-任务唤醒 解挂任务通常需要进行以下工作：根据指定的ID，获得对应任务

28、的TCB如果任务在等待其他资源，任务将仍然处于等待状态；否则，把任务的状态变为就绪状态，并把TCB放置到就绪队列进行任务调度任务的管理机制-任务睡眠 任务睡眠通常需要进行以下工作：修改任务状态，把任务状态变为等待状态把任务TCB放置到时间等待链进行任务调度第四节任务调度任务调度时间片轮转调度基于优先级的可抢占调度任务调度要解决的问题WHEN：何时分配CPU任务调度的时机WHAT：按什么原则分配CPU 任务调度算法HOW： 如何分配CPU任务调度过程任务调度调用调度程序的具体位置又被称为是一个调度点（scheduling point），调度点通常处于以下位置：中断服务程序的结束位置；任务因等待资

29、源而处于等待状态；任务处于就绪状态时等。任务调度设计调度程序时，通常需要综合考虑如下因素：CPU的使用率（CPU utilization）输入/输出设备的吞吐率响应时间（responsive time）公平性截止时间调度算法对于大量的实时调度方法而言，存在着以下几类主要的划分方法：离线（off-line）和在线（on-line）调度抢占（preemptive）和非抢占（non-preemptive）调度静态（static）和动态（dynamic）调度最佳（optimal）和试探性（heuristic）调度调度算法时间片轮转调度(round-robin scheduling)是指： 当有两个或多

30、个就绪任务具有相同的优先级， 且它们是就绪任务中优先级最高的任务时， 调度器按照任务就绪的先后次序调度每个任务， 每个任务运行一段时间后调度下一个任务， 直到最后一个任务也得以运行一段时间后，接下来又让第一个任务运行。时间片轮转调度 时间片轮转调度 基于优先级的调度的基本思路： 给每一个任务都设置一个优先级 然后在任务调度的时候，在所有处于就绪状态的任务中选择优先级最高的那个任务去运行。基于优先级的调度 优先级算法可以分为两种：当一个任务正在运行的时候，如果这时来了一个新的任务，其优先级更高，那么在这种情况下，是立即抢占CPU去运行新任务，还是等当前任务运行完后再决定。 可抢占方式 不可抢占方

31、式区别在于：基于优先级的调度 ISRLow Priority TaskHigh Priority TaskISRISR make High Priority Task ReadyISR Completes(Return to Task)Low Priority Task Completes(Switch to HP Task)Interrupt OccursVector to ISRNon-Preemptive 不可抢占式调度 ISRLow Priority Task (LPT)High Priority Task (HPT)ISRISR make High Priority Task Rea

32、dyInterrupt occursVector to ISRISR Completes(Switch to HP Task)HP Task Completes(Switch back to LP Task)Preemptive 可抢占式调度 低优先级任务内核服务ISR高优先级任务时间(1)(2)(3)(4)(5)不可抢占内核（允许中断）不可抢占内核 低优先级任务内核服务ISR高优先级任务时间(1)(2)(3)(4)(5)可抢占内核可抢占式内核 任务2就绪任务3就绪任务1任务2任务3优先级高低时间任务2任务1抢占抢占任务3运行结束任务2运行结束在可抢占调度方式下的任务运行情况 基于优先级的可抢

33、占调度 在优先级算法中，如果两个任务的优先级相同，又该如何处理呢?把任务按照不同的优先级进行分组，然后在不同组的任务之间使用优先级算法，而在同一组的各个任务之间使用时间片轮转法。通常的做法：时间片轮转调度基于优先级的调度 任务1任务2任务3优先级高低时间任务3就绪任务3运行结束任务1任务2任务1任务2时间片轮转调度 优先级可抢占与时间片轮转调度相结合方式下的任务运行情况第五节优先级反转优先级继承协议 优先级天花板协议优先级反转(Priority Inversion)：指一个任务等待比它优先级低的任务释放资源而被阻塞，如果这时有中等优先级的就绪任务，阻塞会进一步恶化。优先级反转解决优先级反转现象

34、的常用协议为： 优先级继承协议（priority inheritance protocol）；优先级天花板协议（priority ceiling protocol）。 解决优先级反转优先级继承协议的思想当一个任务阻塞 一个或多个高优先级任务时，该任务将不使用其原来的优先级，而使用被该任务所阻塞的所有任务的最高优先级作为其临界区的优先级。当该任务退出临界区时，又恢复到其最初的优先级。优先级继承协议t0t0t1t2t3t4t5t6t7t8Critical section guarded by StimeT1T2T3t9t0t10t11t12t13t14t15t16t18t17优先级高低优先级继承协议优先级继承协议但优先级继承协议存在以下两个方面的问题： 优先级继承协议本身不能