异构多核处理器的任务调度算法 蒋建春;汪同庆 【期刊名称】《计算机工程与应用》 【年(卷),期】2009(045)033 【摘要】在研究Min-min、Max-min算法和Sufferage算法基础上,针对异构多核处理器的特点,提出一种任务静态调度算法--自适应分段Sufferage算法(Adaptive Segmented Sufferage,ASS).该算法以最早完成时间和负载均衡为目标进行任务分配,先将任务分配分成两个阶段:在第一个阶段以最少完成时间作为分配原则进行分配,选择单位时间内节省时间最多的任务先分配;在第二个阶段以负载均衡为分配原则进行分配,选择执行时间大的任务先分配.然后选取不同调节参数,对任务进行多次重新分配,以最小的最大完成时间为最后分配结果,实现自适应调节.通过实验验证,该算法在实现最少完成时间的前提下能很好地达到负载均衡.%After studying the Min-min,Max-min and Sufferage algorithms,this paper presents an Adaptive Segmented Sufferage (ASS) algorithm that can be applied to heterogeneous multi-core processors system,and the goal is to assign optimally tasks to different cores to get the minimal Earliest Finish Time(EFT) and optimal load balancing.At first,the algorithm divides the allo-cating process into two phases:The first phase,the tasks whose saving time is maximum have priority to be selected to a core in the minimal execution time tasks set on the principle of the minimal EFT;the second phase,as the principle of load balancing, the tasks,which have the maximum execution time in the
数据结构课程设计报告 贪心算法：任务调度问题的设计 专业 学生姓名 班级 学 号 指导教师 完成日期
贪心算法：任务调度问题的设计 目录 1设计内容 (1) 2）输入要求 (1) 3）输出要求 (1) 2设计分析 (1) 2.1排序（将数组按照从小到大排序）的设计 (1) 2.2多个测试案例的处理方法的设计 (2) 2.3 for循环设计 (2) 2.4系统流程图 (2) 3设计实践 (2) 3.1希尔排序模块设计 (2) 3.2 多个测试案例的处理方法的模块设计 (3) 4测试方法 (4) 5程序运行效果 (4) 6设计心得 (6) 7附录 (6)
数据结构课程设计报告（2017） 贪心算法：任务调度问题的设计 1设计内容 有n项任务，要求按顺序执行，并设定第I项任务需要t[i]单位时间。如果任务完成的顺序为1，2，…，n，那么第I项任务完成的时间为c[i]=t[1]+…+t[i]，平均完成时间（ACT）即为（c[1]+..+c[n]）/n。本题要求找到最小的任务平均完成时间。 2）输入要求 输入数据中包含n个测试案例。每一个案例的第一行给出一个不大于2000000的整数n，接着下面一行开始列出n各非负整数t（t≤1000000000），每个数之间用空格相互隔开，以一个负数来结束输入。 3）输出要求 对每一个测试案例，打印它的最小平均完成时间，并精确到0.01。每个案例对应的输出结果都占一行。若输入某一个案例中任务数目n=0，则对应输出一个空行。 2 设计分析 这个题目属于贪心算法应用中的任务调度问题。要得到所有任务的平均完成时间，只需要将各个任务完成时间从小到大排序，任务实际完成需要的时间等于它等待的时间与自身执行需要的时间之和。这样给出的调度是按照最短作业优先进行来安排的。贪心算法通过一系列的选择来得到一个问题的解。它所做的每一个选择都是当前状态下某种意义的最好选择，即贪心选择。在许多可以用贪心算法求解的问题中一般具有两个重要的性质：贪心选择性质和最有子结构性质。所谓贪心选择性只是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到，这是贪心算法可行的第一基本要素。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所做的贪心选择最终将会得到问题的一个整体最优解。首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。而且做了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步做贪心选择，最终可得到问题的一个整体最优解。其中，证明贪心选择后问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。当一个问题的最优解包含着它的子问题最优解时，称此问题具有最优子结构性质，这个性质是该问题可用贪心算法求解的一个关键特征。 2.1排序（将数组按照从小到大排序）的设计 排序的方法有很多，如：冒泡排序、希尔排序、堆排序等，这些排序的方法都可以使用。这里采用希尔排序来实现。 它的基本思想是：先取一个小于n的整数d1作为第一个增量；这里选取n的一半作为第一个增量（increment=n》1），把数组的全部元素分成d1个组。所有距
收稿日期:2007-05-09;修回日期:2007-07-18。 基金项目:国家863计划项目(2005AA1Z2120)。 作者简介:刘奎安(1982-),男,四川自贡人,硕士研究生,主要研究方向:无线传感器网络; 郭文生(1976-),男,辽宁铁岭人,讲师,博士研究生,主要研究方向:无线传感器网络、实时网络技术; 桑楠(1964-),男,四川营山人,教授,主要研究方向:嵌入式实时系统。 文章编号:1001-9081(2007)11-2740-03 Tiny OS 任务调度机制与实时调度构件设计 刘奎安,郭文生,桑 楠 (电子科技大学计算机科学与工程学院,成都610054) (lka10271982@sina .com ) 摘 要:Tiny OS 是一个开源的构件化操作系统,它采用构件化描述语言nes C 进行开发,主要针对资源非常有限的无线传感器网络节点而设计。分析了Tiny OS 22.x 的任务调度机制,针对其在实时应用领域的调度缺陷,设计并实现了一种软实时任务调度构件。根据构件在T OSSI M 仿真器中的验证分析,能有效增强Tiny OS 的实时性能。 关键词:无线传感器;Tiny OS;实时;构件设计;T OSSI M 中图分类号:TP316;TP311 文献标识码:A Schedule m echan is m of T i n yO S and its rea l 2ti m e schedule co m ponen t desi gn L I U Kui 2an,G UO W en 2sheng,S ANG Nan (School of Co m puter Science and Engineering,U niversity of Electronic Science and Technology of China, Chengdu S ichuan 610054,China ) Abstract:Tiny OS is an open 2s ource component operating syste m for sens or net w orks nodes that has very li m ited res ources .Tiny OS was i m p le mented in component 2devel op ing language nes C .Thr ough analyzing the schedule mechanis m of Tiny OS 22.x,a s oft real 2ti m e scheduler componentwas designed and i m p le mented for real 2ti m e app licati ons .Si m ulati on results in T OSSI M demonstrate that the s oft real 2ti m e component i m p r oves the real 2ti m e perfor mance of Tiny OS . Key words:wireless sens or net w orks;Tiny OS;real 2ti m e;component design;T OSSI M 0 引言 无线传感器网络(W ireless Sens or Net w orks,W S N )是由大量体积较小、能源受限,具有一定计算、存储和无线通信能力的传感器节点组成的无结构网络[1,2]。它综合了传感器、嵌入式、无线网络、分布式信息处理等技术。由于W S N 自身具备的特征,已广泛应用于国防军事、环境监测、交通管理、医疗卫生等领域。无线传感器网络作为一个新兴的研究领域,其中存在大量挑战性的研究课题,节点上的操作系统(W ireless Sens or Net w orks Operati on Syste m,W S NOS )设计与实现就是其 中之一。 目前,国外许多大学、研究机构着手于W S NOS 的研究,开发出了Tiny OS [3]、Magnet 、MANTI S 、Sen OS 等具有典型特征的W S NOS 。其中,由UC Berkeley 依靠S martdust (智能尘埃)项目开发出的Tiny OS 得到了广泛关注和应用。 Tiny OS 是全新面向W S N 的源码级构件化操作系统,由 构件开发语言nes C [4]开发,其内核只需要400字节的内存空间即可运行起来,是一个轻量级操作系统。但在实时应用中, Tiny OS 简单的F I F O 调度算法就显得不再适用,在任务数较 多时重要任务的响应时间无法得到保证。因此,针对实时应用的实时性需求,本文深入分析了Tiny OS 22.x 调度机制和调度相关的构件,提出了具有软实时性能的任务调度机制,开发 了相应的系统调度构件,通过在T OSSI M [5]仿真器中进行仿 真分析,此实时系统调度构件能提高Tiny OS 的实时性能。 1 Tiny OS 22.x 的调度机制 1.1 Tiny OS 的任务事件驱动的并发模型 Tiny OS 采用任务和事件驱动[6] 相结合的两级并发模型 (如图1) 。 图1 Tiny OS 任务事件驱动并发模型示意图 任务机制 任务由用户应用程序定义,可以由应用程序或事件处理程序创建。任务由task 关键字定义,具体定义语 法为:task void myTask (){…}。任务由post 关键字创建,具体语法为:post myTask ()。创建任务时,Tiny OS 的调度器将任务加入任务队列的队尾。核心调度策略中的任务调度器把此任务加入任务队列后就立即返回,任务则延迟执行。在等待执行的任务队列中,各个任务之间采用F I F O 原则进行调 第27卷第11期 2007年11月 计算机应用 Computer App licati ons Vol .27No .11 Nov .2007
一种改进的实时混合任务调度算法 谢建平1，阮幼林1,2 1武汉理工大学信息工程学院，武汉（430070） 2南京大学计算机软件新技术国家重点实验室，南京（210093） E-mail：xjp_1997@https://www.doczj.com/doc/439014092.html, 摘要：文章提出了结合TBS（总带宽服务器法）算法和DMS（时限单调算法）算法的实时混合任务的调度算法，该方法能保证周期任务满足时限的要求，还能缩短非周期任务的响应时间。基于TBS服务器思想将非周期任务转换成有时限要求的硬实时任务，然后基于DMS 调度周期任务和非周期任务。由于是使用静态的DMS算法，不仅可以减小任务的切换开销，而且对系统的瞬时过载有一定的适应性。 关键词：实时系统；任务调度；时限单调算法；总带宽服务器算法 1. 概述 随着计算机技术的飞速发展与普及，实时系统已经成为人们生产和生活中不可或缺的组成部分。实时系统具有及时响应、高可靠性、专用性、少人工干预等特征[1]，被广泛应用于工业控制、信息通讯、网络传输、媒体处理、军事等领域。实时系统的正确性不仅依赖于计算的逻辑结果，还取决于获得计算结果的时间的正确性。在航空航天、电信、制造、国防等领域，对实时系统有着强烈的应用需求。 由于实时系统的应用面非常广，所以实时系统的分类方法很多。通常按照系统中任务的周期性或者任务对截止期限的要求进行划分。实时任务按照周期性划分可以分为周期实时任务（periodic task）和非周期实时任务（aperiodic task）；按照对截止期限的要求可以分为硬实时任务和软实时任务[1]。 本文提出了结合TBS（总带宽服务器法）算法[5]和DMS（时限单调算法）[6]算法的实时混合任务的调度算法，该方法能保证周期任务满足时限的要求，还能缩短非周期任务的响应时间。算法将非周期任务赋予一个假想的时限，然后整个实时系统采用DMS算法调度。由于是使用静态的DMS算法，不仅可以减小任务的切换开销，而且对系统的瞬时过载有一定的适应性。 2. 实时系统的任务调度 由于实时调度是保障实时系统满足时间约束的重要手段，所以一直是实时计算研究领域中倍受关注的热点问题。调度的实质是资源的分配，包括处理器和其他运算、交互、存储资源，调度就是来用来将这些资源合理地分配给各个实时任务的一种方法。 根据调度顺序产生的时机和方式可以分为静态调度和动态调度[1]。若调度算法是在编译的时候就做出决定从就绪任务队列中选择哪个任务来运行的，则这样的调度是静态的。这类调度算法假设系统中实时任务的特性(如：截止期，WCET等)是事先知道的。它脱机地进行可调度性分析，并产生一个调度表。静态调度算法的优点是运行开销小，可预测性强。但是，由于静态调度算法一旦做出调度决定后在运行期间就不能再改变了，所以它的灵活性较差。 如果调度器是在运行期间才决定选择哪个就绪任务来运行的，则这类调度被称为动态调度。动态调度算法能够对变化的环境做出反应，因此，这类调度算法比较灵活，适合于任务不断生成，且在任务生成前其特性并不清楚的动态实时系统。但是，动态调度算法的可预测性差且运行开销较前者大。
关于任务调度相关研究文献综述随着多核处理器的出现，多核处理器任务调度已成为当前高性能处理器研究的热点之一。任务调度是指系统为确定一系列任务的执行顺序所采取的调度策略。随着计算机技术的不断发展，学术界对任务调度问题的讨论也逐渐深入，旨在通过减少通信开销、改变任务执行顺序，以缩短整个任务的调度长度。 近年来，由于多处理器的广泛应用，如何充分利用多处理器的计算性能成为了大家关注的焦点，针对多处理器的任务调度问题突显出来。在多处理器任务调度算法研究的早期，P Dutot[24]等人在研究中指出，对于异构计算环境下的任务调度问题是NP 难问题，难以在多项式时间内寻求最优解。正是该问题的重要性和复杂性，吸引了一大批专家学者对其进行研究，并提出了大量经典的算法。一、国外研究现状 计算机任务调度的研究早在上世纪60年代就已开始。1967年，芝加哥大学的Manacher G.K在ACM期刊上第一次提出了“任务”的概念，并利用列表法和甘特图进行了基本的多核多任务调度算法研究，提出了能够保证调度稳定性的算法。同时文章对软实时系统和硬实时系统也给出了定义和说明。但是由于文章发表年代较为久远，文中提出的是同构多核处理器的模型，并不适用于当今迅速发展的异构多核处理器之间的任务调度。随后，刘炯朗和Layland在已有工作基础上提出了周期任务模型的概念，该模型对任务进行了较好的抽象，对周期性任务做出了一些假设，忽略计算机体系结构的复杂性以及应用程序的具体实现，可以借助各种数学方法对任务的可调度性进行分析。文中提出了可在单处理器上运行的三种调度算法：单调速率算法RM(rate monotonic algorithm)、最早结束优先 EDF(earliest deadline first)算法[1]以及两者的混合算法。在 RM 算法中， 1 根据任务的需求速度赋予其一定的优先级，即所谓的固定优先级。在 EDF 算法中，任务最终期限值较小的赋予更高的优先级，即动态调整任务的优先级。而综合算法将任务分开对待，分别使用上述的算法。文章分析了在上述几种任务调度算法下，CPU能够达到的最大利用率，并用数学方法给予了证明。为后来的研究奠定了基础。后续又提出了许多经典算法，包括时间片轮转(Round Robin，RR)算法、先到先服务(First Come First Served，FCFS)算法、截止期单调调度(Deadline Monotonic Scheduling, DMS) 算法等。在这些算法中，任务的优先
TOSH_sched_init();for(;;){TOSH_run_task();} 这两个函数的实现在tinyos-1.x\tos\system目录下的sched.c源文件中。这个文件就实现了tinyos 1.x的调度策略，很简单吧？闲话少说，下面分析它的数据结构。 typedef struct { void (*tp) (); } TOSH_sched_entry_T; 这个结构体就是tinyos任务队列里的东东，里面是个函数指针。 enum { #ifdef TOSH_MAX_TASKS_LOG2 #if TOSH_MAX_TASKS_LOG2 > 8 #error "Maximum of 256 tasks, TOSH_MAX_TASKS_LOG2 must be <= 8" #endif TOSH_MAX_TASKS = 1 << TOSH_MAX_TASKS_LOG2, #else TOSH_MAX_TASKS = 8, #endif TOSH_TASK_BITMASK = (TOSH_MAX_TASKS - 1) }; 上面定义了tinyos任务队列里的最大任务数TOSH_MAX_TASKS，和一个掩码。 //定义tinyos任务队列，这个队列是个循环队列！ volatile TOSH_sched_entry_T TOSH_queue[TOSH_MAX_TASKS]; //“头指针”tinyos任务队列里的第一个不为空的任务的下标 uint8_t TOSH_sched_full; //“尾指针”如果tinyos任务队列没有满，则是最后一个不为空的任务 //的下一个元素的下标；如果任务队列满则是最后一个任务的下标。 volatile uint8_t TOSH_sched_free; 好了，数据结构分析完了，咱们看看tinyos是怎样实现这个队列的吧，实现一个队列,无非就是初始化，增加队列元素，删除队列元素，判断队列是否为空……，数据结构里最基本的东东，想必大家比我清楚了！（如果这个不清楚，赶紧回去看看数据结构 ^_^ ）。 一初始化 s 初始化函数很简单，大家肯定都会写了。 void TOSH_sched_init(void) { int i; TOSH_sched_free = 0; TOSH_sched_full = 0; for (i = 0; i < TOSH_MAX_TASKS; i++) TOSH_queue[i].tp = NULL;
目录 第一章绪论 (1) 1.1研究背景和意义 (1) 1.1.1 研究背景 (1) 1.1.2 研究意义 (3) 1.2国内外研究现状 (5) 1.2.1 MEC研究现状 (5) 1.2.2 任务协同调度机制研究现状 (6) 1.3主要研究内容及贡献 (8) 1.4结构和章节安排 (10) 第二章MEC系统中任务聚类策略 (11) 2.1引言 (11) 2.2问题描述 (11) 2.2.1 聚类算法简介 (12) 2.2.2 MEC系统中任务相似度度量 (13) 2.3MEC系统中的任务聚类策略 (14) 2.3.1 基于k-means算法的聚类策略 (14) 2.3.2 基于层次方法的聚类策略 (16) 2.3.3 基于SOM算法的聚类策略 (18) 2.3.4 基于FCM算法的聚类策略 (22) 2.4仿真验证与性能评估 (27) 2.4.1 时延的敏感度分类 (28) 2.4.2 评价指标 (28) 2.4.3 仿真结果与分析 (29) 2.5本章小结 (32) 第三章移动终端与MEC服务器任务协同调度 (33) 3.1引言 (33) 3.2问题描述 (33) 3.2.1 任务卸载流程 (35) 3.2.2 任务卸载开销 (35) 3.3单任务模式 (36)
3.3.1 模型描述 (37) 3.3.2 STM模型 (39) 3.3.3 算法设计 (40) 3.4多任务模式 (41) 3.4.1模型描述 (42) 3.4.2 MTM模型 (45) 3.4.3 问题NP性 (45) 3.4.4 算法设计 (46) 3.5仿真验证与性能评估 (50) 3.5.1 参数设置 (50) 3.5.2 仿真结果与分析 (51) 3.6本章小结 (55) 第四章MEC服务器与核心云任务协同调度 (56) 4.1引言 (56) 4.2问题描述 (57) 4.2.1 任务优先级 (58) 4.2.2 MEC服务器与核心云通信 (58) 4.2.3 MEC服务器计算模型 (59) 4.2.4 核心云计算模型 (60) 4.3MEC服务器与核心云任务协同调度模型 (61) 4.4基于动态规划的方案设计 (62) 4.5基于遗传算法的方案设计 (66) 4.5.1 染色体编码 (66) 4.5.2 适应函数 (67) 4.5.3 染色体结合 (67) 4.5.4 算法设计 (70) 4.6仿真验证与性能评估 (72) 4.6.1 仿真参数设置 (72) 4.6.2 仿真结果分析 (73) 4.7本章小结 (76) 第五章总结与展望 (78) 5.1全文总结 (78) 5.2未来展望 (79)
1.ch0502：任务调度问题，在VC++6.0环境下测试通过 文件main.c：案例源程序； 说明：读者可按照教材中提供的数据进行测试； 2 源代码 #include
Quartz任务调度快速入门1 概述 各种企业应用几乎都会碰到任务调度的需求，就拿论坛来说：每隔半个小时生成精华文章的RSS文件，每天凌晨统计论坛用户的积分排名，每隔30分钟执行锁定用户解锁任务。 对于一个典型的MIS系统来说，在每月1号凌晨统计上个月各部门的业务数据生成月报表，每半个小时查询用户是否已经有快到期的待处理业务……，这样的例子俯拾皆是，不胜枚举。 任务调度本身涉及到多线程并发、运行时间规则制定和解析、场景保持与恢复、线程池维护等诸多方面的工作。如果直接使用自定义线程这种刀耕火种的原始办法，开发任务调度程序是一项颇具挑战性的工作。Java开源的好处就是：领域问题都能找到现成的解决方案。 OpenSymphony所提供的Quartz自2001年发布版本以来已经被众多项目作为任务调度的解决方案，Quartz在提供巨大灵活性的同时并未牺牲其简单性，它所提供的强大功能使你可以应付绝大多数的调度需求。 Quartz 在开源任务调度框架中的翘首，它提供了强大任务调度机制，难能可贵的是它同时保持了使用的简单性。Quartz 允许开发人员灵活地定义触发器的调度时间表，并可以对触发器和任务进行关联映射。 此外，Quartz提供了调度运行环境的持久化机制，可以保存并恢复调度现场，即使系统因故障关闭，任务调度现场数据并不会丢失。此外，Quartz还提供了组件式的侦听器、各种插件、线程池等功能。 了解Quartz体系结构 Quartz对任务调度的领域问题进行了高度的抽象，提出了调度器、任务和触发器这3个核心的概念，并在org.quartz通过接口和类对重要的这些核心概念进行描述： ●Job：是一个接口，只有一个方法void execute(JobExecutionContext context)，开发者实现该接口定义运行任务，JobExecutionContext类提供了调度上下文的各种信息。Job运行时的信息保存在 JobDataMap实例中； ●JobDetail：Quartz在每次执行Job时，都重新创建一个Job实例，所以它不直接接受一个Job的实例，相反它接收一个Job实现类，以便运行时通过newInstance()的反射机制实例化Job。因此需要通过一个类来描述Job的实现类及其它相关的静态信息，如Job名字、描述、关联监听器等信息，JobDetail 承担了这一角色。
Windows CNC多任务调度策略 一般对于单CPU 的CNC系统，系统软件结构采用前后台式。前台程序承担几乎全部实时功能，后台程序用来完成准备工作和管理工作，任务的调度机制采用优先抢占调度与时间片轮转相结合的机制。 （1）优先抢占调度机制 为了满足CNC 实时任务的要求，系统的调度机制必须具有能根据外界的实时信息以足够快的速度（在系统规定的时间内）进行任务调度的能力。优先抢占调度机制就是能满足上述要求的调度技术，它是一种基于实时中断技术的任务调度机制。 优先抢占调度机制，其功能有两个： 1优先调度。在CPU 空闲时，当同时有多个任务请求执行时，优先级高的任务将优先得以满足。 2抢占方式。在CPU 正在执行某任务时，若另一优先级更高的任务请求执行，CPU 将立即终止正在执行的任务，转而响应优先级高的任务的请求。 优先抢占调度机制是由硬件和软件共同实现的，硬件主要提供支持中断功能的芯片和电路，如中断管理芯片（8259或功能相同的芯片），定时器计数器（8263、8294 等）。软件主要完成对硬件的初始化，任务优先级的定义方式、任务切换处理（断点的保护与恢复、中断向量的保存与恢复等）。 （2）时间片轮转调度机制 任务就绪队列往往按任务到达的时间来排序。任务调度程序总是选择就绪队列中的第一个任务，也就是说按照先来先服务的原则调度，即根据任务进入就绪队列的先后次序来占有CPU，一旦一任务占有CPU，它就一直运行下去，直到该任务完成其工作或因等待某事件而不能继续运行时才释放CPU，但一旦任务占有CPU 仅使用一个时间片。在使用完一个时间片后，任务还没有完成其运行，它也必须释放出（被抢占）CPU 给下一个就绪的任务。而被抢占的任务返回到就绪队列的末尾重新排队等候再次运行。 时间片的大小对系统运行的影响很大。如果时间片很大，大到一个任务足以完成其全部运行工作所需的时间，那么时间片轮转策略将退化为先来先服务策略了。如果时间片很小，那么CPU 在任务间的转接工作过于频繁，CPU 真正用于运行任务的时间将会减小。 （3）调度策略 1、确定任务优先级，突发性实时任务具有最高优先级。 2、为其它各任务分配执行周期。如位控为4ms，插补为8ms，预处理为16ms，背景程序为55ms。即在55ms时间片内，最先执行位控任务，位控任务完成后，接着执行插补任务，如果4ms 时间到，则插补将被终止，又开始执行位控，当位控执行完后，从刚才中断处接着执行插补，插补执行完后接着执行预处理，以此类推。 3、在背景程序中，各任务分配相同的优先权，当一个任务执行完后，就绪队列中最前头的任务占据CPU运行，而先前运行任务失去对CPU的控制退至队列尾，直到循环使其达到队头时才重新获得控制权，即按先来先服务的原则调度。 4、当突发性实时任务发生，如故障中断、机床PLC中断及其它异常发生时，当前正在运行的任务将立刻终止执行，系统保存现场环境后，立刻去响应突发性实时中断信号，在执行完突发
余蓝涛1 (天津大学精密仪器与光电子工程学院天津 300072 ) 摘要： 嵌入式系统对强大实时处理能力的需求和相对紧张的内存及内核资源的现实，对嵌入式操作系统任务调度提出了较高的要求。因此任务调度的算法的分析，实现和优化，对实现嵌入式系统的实时性有着重大的意义。从算法提出的理论基础出发，深入分析了经典的单调速率调度算法的思想，特点，具体实现并重点评价了该算法的优点和局限性。 关键词：单调速率调度算法实时嵌入式系统 Abstract： The zest for powerful real-time processing of embedded system and the reality of relatively scare memory and kernel resource pave way for the high request for task scheduling. Therefore, the analysis, implementation and optimization of task scheduling algorithm have a vast meaning for the real-time system. Based on theoretical basis of classic rate-monotonic scheduling algorithm, this paper not only analyzes fundamental thought, characteristics, practical implementation of this classic algorithm in depth, but also rate its advantages and disadvantages. Key words: Rate-monotonic Scheduling, Algorithm, Real-time, Embedded System 一，引言 现在嵌入式系统得到高速的发展。它的发展为几乎所有的电子产品注入了新的活力。它在国民经济各领域和我们日常生活中发挥了越来越重要的作用。 嵌入式系统在航天、军事、工控以及家电等方面得到了广泛应用。囿于体积，能耗，价格等方面的约束，嵌入式系统处理器速度比较慢，存储器容量也有限。而传统的操作系统为了取得较高的性能，要求硬件设备具有强大的处理能力，大容量的存储能力以及对网络的支持功能，这使得传统的操作系统难以简单地移植到嵌入式系统中。 这就导致了嵌入式操作系统由于受到系统的限制，往往内存资源都非常的有限，要求操作系统的内核都非常的精炼，对于系统中的资源操作系统内核需要进行统一的分配和调度。 嵌入式操作系统调度策略一直以来都是嵌入式操作系统的研究 中的一个热点。任务调度是嵌入式操作系统内核的关键部分，如何进行任务调度，使得各个任务能在其截止期限内得以完成是嵌入式操作系统的一个重要的研究领域。 二，嵌入式实时操作系统 绝大部分嵌入式系统都是实时系统，而且多是实时多任务系统。所谓“实时”,是指系统的正确性不仅仅依赖于计算的逻辑结果而且依赖于结果产生的时间[1][6]。结果产生的时间就是通常所说的截止期限(deadline),描述系统实时性的指标主要有： a,对紧急事件可预见性的快速响应； 1作者简介：余蓝涛（1991-）江西省人天津大学精密仪器与光电子工程学院测控技术与仪器本科生学号：79
2007年5月系统工程理论与实践第5期 文章编号:100026788(2007)0520119207 分布式环境下多任务调度问题的分析与求解 何 琨,赵 勇,陈 阳 (华中科技大学控制科学与工程系系统工程研究所,武汉430074) 摘要: 将约束条件归纳为任务约束、链路约束和资源约束,在允许任务复制的情况下,建立了问题的约 束与目标的完整数学模型;提出了一种基于任务复制的模拟人类社会中关系演化过程的簇调度算法 IRE A,包括前沿调度、动态分簇和分离图三个子算法.IRE A采用全新的优先级规则,定义了关系数、依赖 度、归并度等表示簇的优先级.通过对两个经典算例的计算,发现IRE A能求出比算例所在文献算法所得 解更优的解;对M JD算例,还得到了一个不同于原文献所给理论最优格局的一个新的最优格局. 关键词: 调度算法;任务复制;有向无回路图;动态分簇;分离图 中图分类号: TP301 文献标志码: A Analysis and S olutions for Multitasks Scheduling in Distributed Environments HE K un,ZHAO Y ong,CHE N Y ang (Institute of Systems Engineering,Department of C ontrol Science and Engineering,Huazhong University of Science and T echnology,Wuhan 430074,China) Abstract: This paper addresses the problem of static scheduling multitasks with precedence constraints represented as directed acyclic graphs for execution on distributed hom ogeneous environments.The problem is strong NP2com plete, and efficient alg orithms for it will have both highly theoretical value and highly practical value.The constraints are summed up to task constraints,link constraints and res ource constraints.An integrated mathematical m odel with constraints and objective is set up.And a new heuristic approach named the Interpers onal Relationships Ev olution Alg orithm(IRE A)that is based on task duplication is proposed.IRE A resembles the ev olution of the interpers onal relationships within the human s ociety,and includes three com ponents:cutting edge alg orithm,dynamic group alg orithm and detach graph alg orithm.The priority rules used are new.Relationship number,dependent degree and merge degree are defined for cluster’s priority.I t is found that IRE A could get better s olutions for tw o classic benchmarks than the alg orithms which gave the benchmarks.Besides,IRE A gets a different optimal s olution com pared with the theory optimal one for the M JD benchmark. K ey w ords: scheduling alg orithm;task duplication;directed acyclic graph;dymanic clustering;detach graph 1 引言 分布式环境下的任务调度问题是调度理论中的经典问题,包括资源匹配(matchmaking)和任务调度(scheduling)两部分,资源匹配解决在哪里执行任务,即匹配应用需求和可用资源;任务调度解决何时执行任务,即给出应用占用资源的起止时间[1].分布式环境下的任务调度,研究内容分为调度相互独立的任务和调度相互依赖的任务两类,对相互独立的任务一般采用动态调度,对相互依赖的任务一般采用静态调度.为充分利用分布式环境的并行处理与协作能力,往往根据数据依赖关系和计算要求,将应用分解为相互依赖的多个任务,采用有向无回路图(Directed Acyclic G raph,DAG)进行描述. 分布式环境下相互依赖多任务的调度问题是强NP完全的,其近似算法的求解非常困难[2].目前的求 收稿日期:2005205209 资助项目:国家自然科学基金(70471077,60673057);高等学校博士学科点专项基金(20020487046) 作者简介:何琨,女,博士,研究方向为分布式计算、决策分析、复杂系统建模与优化;赵勇,男,博士,教授,博士生导师,研究方向为决策分析、复杂系统建模与优化;陈阳,男,博士,讲师,研究方向为决策分析、复杂系统建模与优化.
ucos:uc/os 任务调度机制 疯狂代码 https://www.doczj.com/doc/439014092.html,/ ?: http:/https://www.doczj.com/doc/439014092.html,/NetworkProgramming/Article33556.html uc/os 任务调度机制 by zhang9733 from https://www.doczj.com/doc/439014092.html,/gd/dzbbs/ 内核核心任务是任务调度机制为了对uc/os进行分析我们从任务调度开始在uc/os中个任务通常是个无限循环具有如下结构后面我将解释为什么会有这种结构从下面结构可以看出个任务就像其他c样；而且既然任务是个无限循环我们可以想象到它定不会返回任何数据所以返回类型应该定义为void ： ------------------------------------------------------------ void mytask(void *pdata) { for (;;) { do something; waiting; do something; } } uc/os可以管理64个任务但目前版本系统占用了两个任务还保留了其他六个任务故用户可以使用56个任务每个任务必须赋予定优先级优先级数越高优先级越低所以0级优先级任务有最高优先级通过在os_cfg.h文件中定义宏os_lowest_prio可以决定系统任务个数系统目前占用两个任务为空闲任务idle task和统计任务stat task当没有其他任务进入就绪状态时空闲任务投入运行空闲任务什么也不做只是简单将计数器加1这个计数器可以用来统计cpu利用率 uc/os下每个任务可以有如下五种状态 休眠态(dormant)：指任务驻留在空间中还没有交给内核管理把任务交给内核是通过ostaskcreate( )或ostaskcreatext( )实现 就绪(ready)：当任务旦建立这个任务就处于就绪态准备运行任务可以动态被另个建立也可以在系统运行开始之前建立通过ostaskdel( )使任务返回到休眠态就绪态任务都放在就绪列表中在任务调度时指针ostcbhighrdy指向优先级最高就绪任务也就是立刻就要运行任务 运行(running)：准备就绪最高优先级任务获得cpu控制权从而处于运行态指针ostcbcur指向正在运行任务
第4章初始化和清除 “随着计算机的进步，‘不安全’的程序设计已成为造成编程代价高昂的罪魁祸首之一。” “初始化”和“清除”是这些安全问题的其中两个。许多C程序的错误都是由于程序员忘记初始化一个变量造成的。对于现成的库，若用户不知道如何初始化库的一个组件，就往往会出现这一类的错误。清除是另一个特殊的问题，因为用完一个元素后，由于不再关心，所以很容易把它忘记。这样一来，那个元素占用的资源会一直保留下去，极易产生资源（主要是内存）用尽的后果。 C++为我们引入了“构建器”的概念。这是一种特殊的方法，在一个对象创建之后自动调用。Java也沿用了这个概念，但新增了自己的“垃圾收集器”，能在资源不再需要的时候自动释放它们。本章将讨论初始化和清除的问题，以及Java如何提供它们的支持。 4.1 用构建器自动初始化 对于方法的创建，可将其想象成为自己写的每个类都调用一次initialize()。这个名字提醒我们在使用对象之前，应首先进行这样的调用。但不幸的是，这也意味着用户必须记住调用方法。在Java中，由于提供了名为“构建器”的一种特殊方法，所以类的设计者可担保每个对象都会得到正确的初始化。若某个类有一个构建器，那么在创建对象时，Java会自动调用那个构建器——甚至在用户毫不知觉的情况下。所以说这是可以担保的！ 接着的一个问题是如何命名这个方法。存在两方面的问题。第一个是我们使用的任何名字都可能与打算为某个类成员使用的名字冲突。第二是由于编译器的责任是调用构建器，所以它必须知道要调用是哪个方法。C++采取的方案看来是最简单的，且更有逻辑性，所以也在Java里得到了应用：构建器的名字与类名相同。这样一来，可保证象这样的一个方法会在初始化期间自动调用。 下面是带有构建器的一个简单的类（若执行这个程序有问题，请参考第3章的“赋值”小节）。 148-149页程序 //: c04:SimpleConstructor.java // Demonstration of a simple constructor. class Rock { Rock() { // This is the constructor System.out.println("Creating Rock"); } } public class SimpleConstructor { public static void main(String[] args) { for(int i = 0; i < 10; i++)