中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 中科院软件所  > 中科院软件所
题名:
Feasibility Analysis and Design of Real-Time Systems
作者: NASRO MIN ALLAH
答辩日期: 2008-05-26
授予单位: 中国科学院软件研究所
授予地点: 软件研究所
学位: 博士
关键词: 实时系统 ; 静态优先级调度 ; 可调度分析 ; 在线可调度判定 ; 实时系统设计
其他题名: Feasibility Analysis and Design of Real-Time Systems
摘要: 针对周期性任务系统,主要是静态优先级调度策略的在线分析,本文提出了一组可调度判定算法。一个是增强的时间需求分析(ETDA),相比经典的时间需求分析(TDA),它精简了判定任务可调度性需要考察的调度点数目。另一个是混合可调度判定(HT),这是一种严格的可调度判定条件,它将已有的充分条件和充要条件结合起来,大大减少了分析时间。为进一步减少分析时间,本文还展示了一个有希望的方法:在进行可调度判定时,将现有的最高优先级优先策略替换为最低优先级优先(LPF)策略。 我们也考察了任务截止期和谐(即复合截止期)的效果,已有多个严格判定条件与此相关。我们提出的第一个判定条件主要关注如何在单个调度点上判定任务的可行性,而提出的第二个判定条件给出了一个基于CPU 利用率的严格判定算法,该算法针对和谐任务系统,其时间复杂度为O(n)。 现有的调度技术大多假设系统提供的优先级个数是不受限制的。然而,基于多种因素如经济等的考虑,大量的系统仅支持有限的优先级,相比优先级个数不受限制的情况,这方面的研究还很有限。为了适应上述应用的需求,转换技术用于将在优先级个数不受限制下可调度的任务集转换为在有限优先级下可调度的任务集,然而这种转换需要付出代价,新得到的任务集会变得不可调度,因此需要研究相应的转换技术,使得原来可调度的任务集在有限优先级下仍旧可以确保其可调度性。 节约能源是当今实时嵌入式系统设计的一个关键技术,处理器消耗了整个系统的很大一部分能源。一方面,最新器件及其复杂需求导致了对能源的大量需求,另一方面,电池技术的改进进展缓慢。由于近期相关技术很难有突破,所以目前研究重点是如何有效地利用电池能源。大量研究集中于利用动态电压调整技术,而其代价是降低了系统的响应性。但是在最新的设备中,尤其是交互式手持设备中,响应性要比节约能源更重要。因此,有效的调度策略应当同时考虑系统的响应性和节约能源。除了对动态电压调整技术在实时调度理论中的应用进行了综述,本文也提出了一个解决方法,用于处理混合负载的情形,使得系统的性能可以得到保证。 周期性任务系统的可调度性对任务参数是敏感的,系统设计师通过调整多个参数,使得系统的某个目标函数最优,如处理器利用率最大,或者能源消耗最少等。这些参数主要包括任务周期,截止期和执行时间。任务周期通常取决于系统需求,而截止期和执行时间可以被修改以便改善系统性能。在基于优先级调度的系统中,这种敏感性分析集中于改变任务执行时间和截止期上,然而迄今为止还没有最优的解决方法。我们将给定的一串由“逻辑或”连接的不等式,转换为一个独立的不等式,然后用这个不等式作为任务可调度的约束条件。这个不等式可以通过非线性规划的方法解决,以便可以设计出最大化系统目标函数如系统利用率、优化能源的方案。这同时也提供了一个通过改变任务执行时间或者处理器执行速度,将不可调度的任务集转换为可调度任务集的方法。
英文摘要: This work presents a collection of feasibility conditions for the online analysis of periodic task systems, mainly, under fixed priority scheduling policy. The first proposed test called enhanced time demand analysis (ETDA) is an efficient algorithm that confines testing schedulability of task to a reduced set of actual points as compared to the classic time demand analysis (TDA). The hybrid test (HT) is another exact condition constituted by combining sufficient condition and necessary and sufficient condition, taken from existing literature, which greatly reduces the analysis time of periodic task sets. To further reduce the analysis time of these systems a promising alternative is shown to be the replacement of the current highest priority first approach with lowest priority first(LPF) order. The effect of making the task deadlines harmonic is also observed and a couple of exact conditions are evolved with this formulation. The first condition is focusing on testing task feasibility at a single scheduling point, while the second test provides a utilization based exact test with $O(n)$ complexity. Both are intended for systems having harmonic deadlines. Most of the current scheduling techniques are based on theassumption that the number of priority levels supported by the underlying hardware is infinite. However, due to many considerations such as economic, enormous systems do exist, where the number of priority levels is limited and this area of limited priority remains relatively unexplored, in contrast to unlimited counter part. In order to accommodate such systems, transformation mechanism are used to convert an unlimited priority feasible task system into the one that can be executed with limited priority levels, however this transformation comes at the price; the newly created set might become infeasible. Care is required for such transformation so that the feasibility of the original set should be guaranteed even with limited priority levels by acquiring the lower number of priority levels required. The mechanism is explained in detail in this work and the feasibility of the unlimited priority feasible task set is kept intact with limited . Power consumption is an important issue in the design of latest real-time embedded systems, where the core processor consumes a large amount of the total system energy. On one front, the complex requirements of latest devices make them power hungry while on the other front the improvement in battery technologies is prohibited due to its fundamental limitations. Since no breakthrough is expected in near future, the focus is shifted to utilizing the battery power more efficiently. Much research is focused on the power reduction of the current dynamic voltage scaling enabled processor at the expense of system responsiveness. In latest devices, especially in interactive hand held devices, responsiveness is of higher importance than energy saving. Hence, a useful scheduling policy should account for system responsiveness as well as power reduction. A solution is also proposed for handling mixed workload such that system performance is bounded by its deadline, in addition to a survey of DVS techniques into real-time scheduling theory. In the last part of the thesis, we endeavor to present the concept of generalized bound of task schedulability to chalk out the specification requirements of a system under investigation in a formal way. Since schedulability of a periodic system is sensitive to task parameter, multiple parameters are exploited by the system designer at design time for maximizing some objective function such as increasing processor utilization or reducing the power consumptions of the systems. These parameters include task period, deadline and execution times. The task periods are usually set by the system requirements, but deadline and computation times can be modified in order to improve system performance. Under priority based scheduling, such sensitivity analysis has focused on changing the task execution times and deadlines, however no optimal solution is known as yet, prior to this work. We transform the given list of inequalities linked through logical OR conditions into a single inequality. This inequality becomes a constraint of task schedulability, which can be solved with nonlinear programming techniques for obtaining optimal task execution times that can be applied at design time for minimizing some objective function such as energy consumption or system utilization. The generalized bound provides the facility of finding the optimal values for execution times or processor speed for converting a non-feasible task set into a feasible one.
语种: 中文
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/7216
Appears in Collections:中科院软件所

Files in This Item:
File Name/ File Size Content Type Version Access License
10001_2005A8015029003NASRO MIN ALLAH_paper.pdf(9379KB)----限制开放-- 联系获取全文

Recommended Citation:
NASRO MIN ALLAH. Feasibility Analysis and Design of Real-Time Systems[D]. 软件研究所. 中国科学院软件研究所. 2008-05-26.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[NASRO MIN ALLAH]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[NASRO MIN ALLAH]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace