实时操作系统任务管理与调度.ppt

嵌入式实时操作系统及应用开发,第五章 任务管理与调度,主要内容,进程与线程任务任务管理任务调度优先级反转,第一节进程与线程,程序运行的方式进程的定义线程的定义,程序的运行方式,顺序运行 作业的运行总是一个一个地顺着来，完成一个作业后再运行下一个。在一个作业运行中途，决不会突然插入另一个作业运行。顺序运行最容易实现，常见于早期的单道批处理系统中,程序的运行方式,并发运行 允许多个程序共享CPU，在这种方式下，系统的资源不再被某一个程序独占，而是由多个程序共享。,简单地说，就是能用一个处理器并发（注意，不是同时！）地运行多个程序的计算机管理系统。,并发：由同一个处理器轮换地运行多个程序。或者说是由多个程序轮班地占用处理器这个资源。且在占用这个资源期间，并不一定能够把程序运行完毕。,并发过程示意图,处理器如何进行程序的切换？,程序的切换（两句话）,处理器是个傻瓜，PC让它干啥，它就干啥。,PC是个指路器，它指向哪儿，处理器就去哪儿。,从此可以知道，哪个程序占有了PC，哪个程序就占有了处理器。,进程与程序,进程与程序,程序是存放在磁盘上的一系列代码和数据的可执行映像，是一个静止的实体。进程：可并发执行的程序在一个数据集合上的运行过程。程序是静止的，进程是动态的，有状态转换。,进程与程序,进程的四要素：1、作为一个进程，要有一段程序供其执行。2、有进程专用的内核空间堆栈。3、在内核中有一个task_struct数据结构，即“进程控制块”。4、有独立的用户空间,线程的引入,早期的进程，包含了以下两个方面的内容：资源。进程是资源分配的基本单位，一个进程包括一个保存进程映像的虚拟地址空间、主存、I/O设备和文件等资源。调度执行。进程作为操作系统的调度实体，是调度的基本单位。进程是一个庞大的结构型实体，其PCB结构包含的内容相当多，每创建一个进程，系统无论在时间或空间上都要花费较大的开支。,线程定义,线程是进程的一个实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈),一个线程可以创建和撤销另一个线程；,使用线程的优势：创建：在一个已有进程中创建一个新线程比创建一个全新的进程所需的时间开销少；终止：终止一个线程比终止一个进程所花费的时间少；切换：线程切换比进程切换所花费的时间少；通信：使同一进程内部不同线程之间的通信效率得到显著提高。在大多数操作系统中，不同进程之间的通信需要内核的干预，而同一进程内部不同线程之间则可直接通信。,第二节任 务,任务的定义及其主要特性任务的内容任务的分类任务参数,任务,在嵌入式实时系统中任务（task）：任务是一个具有独立功能的无限循环的程序段的一次运行活动通常为进程（process）和线程（thread）的统称任务是调度的基本单位,High Priority Task,Low Priority Task,Task,Task,Task,Task,Task,Task,Event,Event,Each Task,Infinite Loop,Importance,Splitting an application into Tasks,任务,任务通常包含一个具有无限循环的程序,/*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);,任务,任务的特性：动态性 并发性 异步独立性,任务,任务的内容：代码：一段可执行的程序。数据：程序所需要的相关数据(变量、工作空间、缓冲区)堆栈 程序执行的上下文环境TCB,任务代码,任务堆栈,内存,处理器,任务运行时与 处理器之间的关系,处理器通过两个指针寄存器（PC和SP）来与任务代码和任务堆栈建立联系并运行它,寄存器组,处理器,多任务时的问题,？,当有多个任务时，处理器中的运行环境应该怎么办？,寄存器组,程序运行环境,多任务时任务与处理器 之间关系的处理,程序,在内存中为每个任务创建一个虚拟的处理器（处理器部分的运行环境,由操作系统的调度器按某种规则来进行这两个复制工作,寄存器组,寄存器组,也就是说，任务的切换是任务运行环境的切换,虚拟处理器应该存储的主要信息：1。程序的断点地址（PC）2。任务堆栈指针（SP）3。程序状态字寄存器（PSW）4。通用寄存器内容5。函数调用信息（已存在于堆栈）,另外再用一个数据结构保存任务堆栈指针（SP），这个数据结构叫做任务控制块，它除了保存任务堆栈指针之外还要负责保存任务其他信息。,这些内容通常保存在任务堆栈中，这些内容也常叫做任务的上下文。,任务控制块是由操作系统另行构造的一个数据结构，每个任务都有一个。,其实，程序切换的关键是把程序的私有堆栈指针赋予处理器的堆栈指针SP,实质上系统是通过SP的切换来实现程序的切换的。,要建立一个概念：具有控制块的程序才是一个可以被系统所运行的任务。程序代码、私有堆栈、任务控制块是任务的三要件。任务控制块提供了运行环境的存储位置。,任务,任务与程序的区别：任务能真实地描述工作内容的并发性，而程序不能；程序是任务的组成部分；除程序外，任务还包括数据、堆栈及其上下文环境等内容；程序是静态的，任务是动态的；任务有生命周期，有诞生、有消亡，是短暂的；而程序是相对长久的；一个程序可对应多个任务，反之亦然；任务具有创建其他任务的功能，而程序没有。,任务,任务的分类：按照到达情况的可预测性，任务可以划分为：周期任务（periodic task），非周期任务（non-periodic task）按照重要程度，可分为：关键任务（critical task），非关键任务（noncritical task）,多任务系统示意图,任务,任务,任务的参数优先级（priority）：任务的优先级分为静态优先级和动态优先级。周期（period）：表示任务周期性执行的间隔时间。计算时间（computation time）：也被称为是任务的执行时间（execution time）。就绪时间（ready time）：具备了被执行所需要条件时的时间 截止时间（deadline）：任务需要在该时间到来之前被执行完成。截止时间可以分为强截止时间（hard deadline）和弱截止时间（soft deadline）两种情况：拥有关键任务的实时系统又被称为强实时统，否则称为弱实时系统。,第三节任务管理,任务状态与变迁任务控制块任务切换任务队列优先级位图算法任务管理机制,任务的管理-任务状态与变迁,任务会在不同的状态之间进行转换，即任务状态的变迁,就绪态,运行态,等待态,获得CPU,被高优先级任务抢占或超时,获得资源,需要资源,任务状态变迁,三个任务进行状态转换的过程 包含三个任务和一个调度程序。调度程序用来确定下一个需要投入运行的任务，因此调度程序本身也需要占用一定的处理时间。,任务的管理-任务状态与变迁,任务的状态及其转换,正在运行的任务，需要等待一段时间或需要等待一个事件发生再运行时，该任务就会把CPU的使用权让给别的任务而使任务进入等待状态。,任务在没有被配备任务控制块或被剥夺了任务控制块时的状态叫做任务的睡眠状态,系统为任务配备了任务控制块且在任务就绪表中进行了就绪登记，这时任务的状态叫做就绪状态。,处于就绪状态的任务如果经调度器判断获得了CPU的使用权，则任务就进入运行状态,一个正在运行的任务一旦响应中断申请就会中止运行而去执行中断服务程序，这时任务的状态叫做中断服务状态,由于系统存在着多个任务，于是系统如何来识别并管理一个任务就是一个需要解决的问题。识别一个任务的最直接的办法是为每一个任务起一个名称。,系统必须为每个任务创建一个保存与该任务有关的相关信息的数据结构，这个数据结构就叫做该任务的任务控制块（TCB）。,任务的管理-任务控制块,用来记录任务的堆栈指针、任务的当前状态、任务的优先级别等一些与任务管理有关的属性的表就叫做任务控制块,任务控制块是不是像我们人在一个国家中的身份证？（其实，系统中的所有资源都应该有身份证。）,任务控制块就相当于是一个任务的身份证，没有任务控制块的任务是不能被系统承认和管理的,任务控制块示意图,任务的管理-任务控制块,任务在内存中的结构,任务切换,任务切换（context switching）保存当前任务的上下文，并恢复需要执行的任务的上下文的过程。当发生任务切换时：当前正在运行的任务的上下文就需要通过该任务的任务控制块保存起来；把需要投入运行的任务的上下文从对应的任务控制块中恢复出来。,在时刻8即发生了任务切换，任务1的上下文需要保存到任务1的任务控制块中去。经过调度程序的处理，在时刻10任务2投入运行，需要把任务2的任务控制块中关于上下文的内容恢复到CPU的寄存器中。,任务的管理-任务切换,任务1,任务2,实时内核调度程序,保存任务1的上下文到TCB1,从TCB2恢复任务2的上下文,保存任务2的上下文到TCB2,从TCB1恢复任务1的上下文,时间,任务的管理-任务切换,任务切换,任务切换具有如下基本步骤：保存任务上下文环境；更新当前处于运行状态的任务的任务控制块的内容，如把任务的状态由运行状态改变为就绪或是等待状态；把任务的任务控制块移到相应的队列（就绪队列或是等待队列）；选择另一个任务进行执行：调度；改变需要投入运行的任务的任务控制块的内容，把任务的状态变为运行状态；根据任务控制块，恢复需要投入运行的任务的上下文环境。,任务的管理-任务上下文切换时间,保 存,调 度,恢 复,保存当前运行任务上下文的时间,选择下一个任务的调度时间,将要运行任务的上下文的恢复时间,取决于任务上下文的定义和处理器的速度。不同种类的处理器，任务上下文的定义不同，其内容有多有少。,任务的管理-任务切换,任务切换时机,中断、自陷,运行任务因缺乏资源而被阻塞,时间片轮转调度时,高优先级任务处于就绪时,任务的管理-任务队列,任务队列通过任务控制块实现对系统中所有任务的管理,单就绪队列和单等待队列,任务的管理-任务队列,队列由任务控制块构成,任务队列,单就绪队列和多等待队列,任务的管理-任务队列,任务的管理-优先级位图就绪任务处理算法,为了能够使系统清楚地知道，系统中哪些任务已经就绪，哪些还没有就绪，OS在RAM中设立了一个记录表，系统中的每个任务都在这个表中占据一个位置，并用这个位置的状态（1或者0）来表示任务是否处于就绪状态，这个表就叫做任务就绪状态表，简称叫任务就绪表,任务就绪表就是一个二维数组OSRdyTbl,为加快访问任务就绪表的速度，系统定义了一个变量OSRdyGrp来表明就绪表每行中是否存在就绪任务。,任务的管理-优先级位图就绪任务处理算法,35:00100011,优先级映射表priorityMapTable,char priorityMapTable8=0 x01,0 x02,0 x04,0 x08,0 x10,0 x20,0 x40,0 x80;priorityMapTable的数组元素的下标与任务优先级的高三位或低三位相对应。priorityMapTable的数组元素对应的二进制值中，位为1的位表示priorityReadyGroup或是priorityReadyTable的对应位也为1。,35:00100011,Char 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,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,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,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 to 0 x5F*/,/*0 xF0 to 0 xFF*/,priorityReadyTable3 contains 0 xE4,priorityReadyGroup contains 0 x68,;,3=priorityDecisionTable 0 x68;2=priorityDecisionTable 0 xE4;26=(3 3)+2;,以priorityReadyGroup或是priorityReadyTable 数组元素的值为索引，获取该值对应二进制表示中1出现的最低二进制位的序号（0-7）。,优先级判定表char priorityDecisionTable 256,任务进入就绪态 priorityReadyGroup|=priorityMapTablepriority 3;priorityReadyTablepriority 3|=priorityMapTablepriority,35:00100 011,00010000,00001000,任务退出就绪态 if(priorityReadyTablepriority 3,35:00100 011,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,00001000-11110111,00010000-11101111,OSRdyTbl0,OSRdyTbl1,OSRdyTbl2,OSRdyTbl3,OSRdyTbl4,OSRdyTbl5,OSRdyTbl6,OSRdyTbl7,获取进入就绪态的最高优先级 high3Bit=priorityDecisionTable priorityReadyGroup;low3Bit=priorityDecisionTable priorityReadyTablehigh3Bit;priority=(high3Bit 3)+low3Bit;,35:00100 011,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,0 x50-4=high3Bit,0 x88-3=low3Bit,OSRdyTbl0,OSRdyTbl1,OSRdyTbl2,OSRdyTbl3,OSRdyTbl4,OSRdyTbl5,OSRdyTbl6,OSRdyTbl7,任务管理机制,任务管理用来实现对任务状态的直接控制和访问。,创建任务删除任务挂起任务唤醒任务设置任务属性改变任务优先级获取任务信息,任务的管理机制-创建任务,任务创建通常需要完成以下工作：获得任务控制块TCB根据实时内核用户提供的信息初始化TCB为任务分配一个可以唯一标识任务的ID使任务处于就绪状态，把任务放置到就绪队列进行任务调度处理,任务的管理机制-删除任务,任务删除通常需要进行以下工作：根据指定的ID，获得对应任务的TCB把任务的TCB从队列中取出来，挂入空闲TCB队列释放任务所占用的资源,任务的管理机制-挂起任务,挂起任务通常需要进行以下工作：根据指定的ID，获得对应任务的TCB把任务的状态变为等待状态，并把TCB放置到等待队列如果任务自己挂起自己，进行任务调度,任务的管理机制-任务唤醒,解挂任务通常需要进行以下工作：根据指定的ID，获得对应任务的TCB如果任务在等待其他资源，任务将仍然处于等待状态；否则，把任务的状态变为就绪状态，并把TCB放置到就绪队列进行任务调度,任务的管理机制-任务睡眠,任务睡眠通常需要进行以下工作：修改任务状态，把任务状态变为等待状态把任务TCB放置到时间等待链进行任务调度,第四节任务调度,任务调度时间片轮转调度基于优先级的可抢占调度,任务调度要解决的问题WHEN：何时分配CPU任务调度的时机WHAT：按什么原则分配CPU 任务调度算法HOW：如何分配CPU任务调度过程,任务调度,调用调度程序的具体位置又被称为是一个调度点（scheduling point），调度点通常处于以下位置：中断服务程序的结束位置；任务因等待资源而处于等待状态；任务处于就绪状态时等。,任务调度,设计调度程序时，通常需要综合考虑如下因素：CPU的使用率（CPU utilization）输入/输出设备的吞吐率响应时间（responsive time）公平性截止时间,调度算法,对于大量的实时调度方法而言，存在着以下几类主要的划分方法：离线（off-line）和在线（on-line）调度抢占（preemptive）和非抢占（non-preemptive）调度静态（static）和动态（dynamic）调度最佳（optimal）和试探性（heuristic）调度,调度算法,时间片轮转调度(round-robin scheduling)是指：当有两个或多个就绪任务具有相同的优先级，且它们是就绪任务中优先级最高的任务时，调度器按照任务就绪的先后次序调度每个任务，每个任务运行一段时间后调度下一个任务，,直到最后一个任务也得以运行一段时间后，接下来又让,第一个任务运行。,时间片轮转调度,时间片轮转调度,基于优先级的调度的基本思路：,给每一个任务都设置一个优先级,然后在任务调度的时候，在所有处于就绪,状态的任务中选择优先级最高的那个任务去运行。,基于优先级的调度,优先级算法可以分为两种：,当一个任务正在运行的时候，如果这时来了一个新的任务，其优先级更高，那么在这种情况下，是立即抢占CPU去运行新任务，还是等当前任务运行完后再决定。,可抢占方式 不可抢占方式区别在于：,基于优先级的调度,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 OccursVector to ISR,Non-Preemptive,不可抢占式调度,ISR,Low Priority Task(LPT),High Priority Task(HPT),ISR,ISR make High Priority Task Ready,Interrupt occursVector to ISR,ISR Completes(Switch to HP Task),HP Task Completes(Switch back to LP Task),Preemptive,可抢占式调度,不可抢占内核,可抢占式内核,任务2就绪,任务3就绪,在可抢占调度方式下的任务运行情况,基于优先级的可抢占调度,在优先级算法中，如果两个任务的优先级相同，又该如何处理呢?,把任务按照不同的优先级进行分组，然后在不同组的任务之间使用优先级算法，而在同一组的各个任务之间使用时间片轮转法。,通常的做法：,时间片轮转调度,基于优先级的调度,时间片轮转调度,优先级可抢占与时间片轮转调度相结合方式下的任务运行情况,第五节优先级反转,优先级继承协议 优先级天花板协议,优先级反转(Priority Inversion)：指一个任务等待比它优先级低的任务释放资源而被阻塞，如果这时有中等优先级的就绪任务，阻塞会进一步恶化。,优先级反转,解决优先级反转现象的常用协议为：优先级继承协议（priority inheritance protocol）；优先级天花板协议（priority ceiling protocol）。,解决优先级反转,优先级继承协议的思想当一个任务阻塞 一个或多个高优先级任务时，该任务将不使用其原来的优先级，而使用被该任务所阻塞的所有任务的最高优先级作为其临界区的优先级。当该任务退出临界区时，又恢复到其最初的优先级。,优先级继承协议,优先级继承协议,优先级继承协议,但优先级继承协议存在以下两个方面的问题：优先级继承协议本身不能避免死锁的发生；在优先级继承协议中，任务的阻塞时间虽然是有界的，但由于可能出现阻塞链，使得任务的阻塞时间可能会很长。,死锁现象,优先级继承协议,任务的阻塞链,优先级继承协议,Critical section guarded by S2,在优先级天花板协议中，主要包含如下处理内容：对于控制临界区的信号量，设置信号量的优先级天花板为可能申请该信号量的所有任务中具有最高优先级任务的优先级；如果任务成功获得信号量，任务的优先级将被抬升为信号量的优先级天花板；任务执行完临界区，释放信号量后，其优先级恢复到其最初的优先级；如果任务不能获得所申请的信号量，任务将被阻塞。,优先级天花板协议,优先级天花板协议,优先级天花板协议,优先级继承协议与优先级天花板协议的比较,关于执行效率的比较 优先级天花板协议的效率高。对程序运行过程影响程度的比较优先级继承协议对任务执行流程的影响相对要较小。,采用优先级继承协议的任务执行情况,解决优先级反转,采用优先级天花板协议的任务执行情况,优先级高低,解决优先级反转,解决优先级反转,基于优先级继承的天花板协议的任务执行情况,谢谢！,