实时调度EDZL算法的可调度性判定

针对多处理器实时调度中的EDZL调度算法,利用多任务之间的相互干涉关系,找出与多处理器之间的时间约束条件,提出了一种可调度性判定的方法,并对给出的判定方法进行了证明。给出了一种判定多处理器实时EDZL可调度性的算法,这种方法可在设计多处理器实时系统时使用。     

一个多处理器实时线程调度算法及其在MACH操作系统下的实现方法研究

在实时操作系统中，任务调度在处理器资源的管理中起着十分关键的作用。本文提出了一种基于线程的、动态的、非抢占的多处理器实时任务调度算法，该算法可以高效地在多处理器系统上同时进行周期性和非周期性实时线程的调度。本文还讨论了该算法在ＭＡＣＨ操作系统环境下的实现方法。     

多处理器系统实时调度的可预测性

在多处理器实时系统中,由于调度的不规则性,系统的可预测性判定问题尤为重要。针对多处理器系统中实时任务调度的可预测性问题,给出了不可预测的实时任务集反例,证明了一种可预测的实时任务集合。对于多处理器实时系统中常用的最早截止期零松弛调度算法(earliest deadline zero laxity,EDZL)的可预测性,利用EDZL算法的基本性质,用一种简捷的方法证明了EDZL算法是可预测的。通过仿真系统验证了证明的正确性,该方法可用于多处理器及分布式实时系统的设计和验证。     

一种基于EDF算法的多处理器实时调度算法

多处理器系统实时调度理论是目前实时系统研究的热点问题。EDF调度算法是目前流行的实时调度算法,有很多优点,但在多处理器系统应用中存在问题。论文研究了EDF调度算法在多处理器系统中的调度理论,在此基础上,提出了一种基于EDF算法的优先级驱动实时调度算法,算法充分利用了EDF调度算法的优点,较大程度地克服了EDF算法在多处理器系统中的调度缺点,并提供了较好的实时调度性能。     

基于双曲线边界的多处理器实时任务可调度性判定

Lopez等学者求解出基于单调速率算法和首次适应分派策略的多处理器实时任务可调度性判定边界.该边界在所有O(m)复杂度的判定边界中是最优的.基于Bini等学者针对单处理器提出的双曲线可调度性判定方法,给出了一种多处理器实时任务可调度性判定边界.新边界在相当数量的利用率分布下明显优于已有边界.新边界与已有边界具有相容性,所以虽然新边界无法在所有情况下超越已有边界,但在实际应用中可联合两种边界进行判定,在不增加计算复杂度的同时全面提高可调度任务集的数量.     

多处理器系统的实时调度算法研究

调度算法是实时系统的关键技术，选取何种算法调度实时任务，这将直接影响着系统的实时响应能力。多处理器系统有局部调度和全局调度两类实时调度方法，以PFair公平调度为代表的全局调度是当前研究的热点。研究了典型局部调度EDF-FF算法和典型PFair公平调度PD^2算法，比较了多处理器系统采用PD^2算法相对于采用EDF-FF算法实现任务调度的优点，分析了由于任务频繁抢占和迁移，PD^2算法引起的时间消耗，估计并比较了PD2算法和EDF-FF算法的时间消耗，最后得出结论：在共享内存的多处理器系统中，公平调度算法是实时任务调度的比较理想的选择。     

多处理器单调速率任务分配算法性能评价

多处理器任务分配调度算法是一类经典实时调度算法，然而目前研究在如何根据任务集特征选择任务分配算法方面少见指导性原则，不利于提高多处理器任务分配算法的可调度率及使用尽可能少的处理器达到最优调度结果。基于两种多处理器任务调度策略的比较，本文给出划分策略下的多处理器RM调度的可调度条件和任务分配算法夏分析。仿真结果表明，各任务分配算法所需处理器数与任务集总利用率成正比。同时，分析总结出各算法适用范围及如何根据任务集利用率选择合适算法的指导原则。最后结果还表明，实际算法性能与理论性能界存在差异。     

一个多处理器实时线程调度算法的计算机模拟及分析

本文介绍了对作者提出的一种基于线程的、动态的、非抢占的多处理器实时任务调度算法的计算机模拟和结果分析，表明该算法在单处理器情况下比许多单处理器实时任务调度算法的调度频率高，在多处理器情况下的调度效率也较高。     

多处理器上的实时系统任务管理策略与实现

随着计算机应用的发展,实时任务在控制中的范围和规模也越来越大,对于强实时任务,必须保证它的急迫的时间要求。使用多处理器系统来的构造实时系统具有较高的性能价格比和良好的扩充性,并能够简化应用的实现。对于周期性任务和随机任务共存的多处理器系统,选择一个最佳的任务管理策略是ＮＰ问题。在本文中,讲述了一般的任务管理策略,并给出了一种基于资源保留策略的集中分配的多处理器实时任务管理策略。     

基于分批优化的实时多处理器系统的集成动态调度算法

提出了一种基于分批优化的实时多处理器系统的集成动态调度算法，该算法采用在每次扩充当前局部调度时，通过对所选取的一批任务进行优化分配的策略以及软实时任务的服务质量QoS（quality of service）降级策略，以统一方式实现了对实时多处理器糸统中硬、软实时任务的集成动态调度．进行了大量的模拟研究，结果表明．在多种任务参数取值下，新算法的调度成功率均高于近视算法（Myopic Algorithm）．     

New Algorithms for Resource Reclaiming from Precedence Constrained Tasks in Multiprocessor Real-Time Systems

The scheduling of tasks in multiprocessor real-time systems has attracted many researchers in the recent past. Tasks in these systems have deadlines to be met, and most of the real-time scheduling algorithms use worst case computation times to schedule these tasks. Many resources will be left unused if the tasks are dispatched purely based on the schedule produced by these scheduling algorithms, since most of the tasks will take less time to execute than their respective worst case computation times. Resource reclaiming refers to the problem of reclaiming the resources left unused by a real-time task when it takes less time to execute than its worst case computation time. In this paper, we propose two algorithms to reclaim these resources from real-time tasks that are constrained by precedence relations and resource requirements, in shared memory multiprocessor systems. We introduce a notion called a restriction vector for each task which captures its resource and precedence constraints with other tasks. This will help not only in the efficient implementation of the algorithms, but also in obtaining an improvement in performance over the reclaiming algorithms proposed in earlier work [[2]]. We compare our resource reclaiming algorithms with the earlier algorithms and, by experimental studies, show that they reclaim more resources, thereby increasing the guarantee ratio (the ratio of the number of tasks guaranteed to meet their deadlines to the number of tasks that have arrived), which is the basic requirement of any resource reclaiming algorithm. From our simulation studies, we demonstrate that complex reclaiming algorithms with high reclaiming overheads do not lead to an improvement in the guarantee ratio.     

Resource reclaiming in multiprocessor real-time systems

Most real-time scheduling algorithms schedule tasks with regard to their worst case computation times. Resources reclaiming refers to the problem of utilizing the resources left unused by a task when it executes in less than its worst case computation time, or when a task is deleted from the current schedule. Dynamic resource reclaiming algorithms that are effective, avoid any run time anomalies, and have bounded overhead costs that are independent of the number of tasks in the schedule are presented. Each task is assumed to have a worst case computation time, a deadline, and a set of resource requirements. The algorithms utilize the information given in a multiprocessor task schedule and perform online local optimization. The effectiveness of the algorithms is demonstrated through simulation studies     

A New Strategy for Improving the Effectiveness of Resource Reclaiming Algorithms in Multiprocessor Real-Time Systems

The scheduling of tasks in multiprocessor real-time systems has attracted the attention of many researchers in the recent past. Tasks in such systems have deadlines to be met, and most real-time scheduling algorithms use worst case computation times to schedule these tasks. Many resources will be left unused if the tasks are dispatched purely based on the schedule produced by these scheduling algorithms, since most of the tasks will take less time to execute than their respective worst case computation times. Resource reclaiming refers to the problem of reclaiming the resources left unused by a real-time task when it takes less time to execute than its worst case computation time. Several resource reclaiming algorithms such as Basic, Early Start, and RV algorithms have been proposed in the recent past. But these pay very little attention to the strategy by which the scheduler can better utilize the benefits of reclaimed resources. In this paper, we propose an esti- mation strategy which can be used along with a particular class of resource reclaiming algorithms (such as Early Start and RV algorithms) by which the scheduler can estimate the minimum time by which any scheduled but unexecuted task will start or finish early, based solely on the start and finish times of tasks that have started or finished execution. We then propose an approach by which dynamic scheduling strategies, which append or reschedule new tasks into the schedules, can use this estimation strategy to achieve better schedulability. Extensive simulation studies are carried out to investigate the effectiveness of this estimation strategy versus its cost.     

网格资源查找方法的分析与比较

在网格环境下,如何快速进行资源查找定位是影响网格性能和QoS的重要因素.本文分析了目前已有的两种用于网格资源发现的资源查找算法(集中式查找算法、分布式查找算法)的优劣,并参照网络路由器的路由转发策略,提出了改进的基于路由转发的资源查找算法.     

Soft sets based symbiotic organisms search algorithm for resource discovery in cloud computing environment

The dynamicity, coupled with the uncertainty that occurs between advertised resources and users’ resource requirement queries, remains significant problems that hamper the discovery of candidate resources in a cloud computing environment. Network size and complexity continue to increase dynamically which makes resource discovery a complex, NP-hard problem that requires efficient algorithms for optimum resource discovery. Several algorithms have been proposed in literature but there is still room for more efficient algorithms especially as the size of the resources increases. This paper proposes a soft-set symbiotic organisms search (SSSOS) algorithm, a new hybrid resource discovery solution. Soft-set theory has been proved efficient for tackling uncertainty problems that arises in static systems while symbiotic organisms search (SOS) has shown strength for tackling dynamic relationships that occur in dynamic environments in search of optimal solutions among objects. The SSSOS algorithm innovatively combines the strengths of the underlying techniques to provide efficient management of tasks that need to be accomplished during resource discovery in the cloud. The effectiveness and efficiency of the proposed hybrid algorithm is demonstrated through empirical simulation study and benchmarking against recent techniques in literature. Results obtained reveal the promising potential of the proposed SSSOS algorithm for resource discovery in a cloud environment.     

Exploiting multi-core nodes in peer-to-peer grids

While the majority of CPUs now sold contain multiple computing cores, current grid computing systems either ignore the multiplicity of cores, or treat them as distinct, independent machines. The latter approach ignores the resource contention present between cores in a single CPU, while the former approach fails to take advantage of significant computing power. We provide a decentralized resource management framework for exploiting multi-core nodes to run multi-threaded applications in peer-to-peer grids. We present two new load-balancing schemes that explicitly account for the resource sharing and contention of multiple cores, and propose a parameterized performance prediction model that can represent a continuum of resource sharing among cores of a CPU. We use extensive simulation to confirm that our two algorithms match jobs with computing nodes efficiently, and balance load during the lifetime of the computing jobs.     

A family of incentive-compatible and non-subsidizing optimal resource allocation problems

This paper provides a structure unifying several recent results on an incentive optimal resource allocation problem. They include an incentive-compatible modification of the Heal Algorithm, a generalization of it allowing the formation of secret coalitions and a class of center-free resource allocation algorithms as special cases. Our framework encompasses these earlier results and allows us to characterize a large class of incentive-compatible and non-subsidizing optimal resource allocation algorithms.     

网格环境中带度约束的多播资源查找算法

网格计算的前提是资源查找。本文分析研究了几种适应某些网格资源模型的现有资源查找算法及其时间和空间复杂度。针对有多播特征的网格环境中的资源查找，基于多播功能，同时赋予资源节点不同权值，构造带度的多播网格资源模型，提出带度约束的多播资源查找算法。与现有算法相比，此算法能更有效实现多播网格环境中资源的快速查找。     

网格计算资源调度算法研究

如何将网格这个复杂环境中的资源进行有效调度，是一个NP问题。并行遗传算法被证明是解决这类问题的有效算法，同时并行遗传算法有“早熟”和慢速收敛等缺点。为了克服其缺点，该文引进蚁群算法思想，将两个算法结合起来，充分发挥各自的优势，该算法能更有效地解决网格计算资源分配的问题。     

Resource placement in Cartesian product of networks

The utilization of the limited resources of a multiprocessor or multicomputer system is a primary performance issue which is crucial for the design of many scheduling algorithms. While many of the existing parallel machines benefit from a regular product network topology, almost none of the previous resource placement techniques have come to recognize and exploit this inherent regularity. This paper introduces several novel algorithms for deriving resource placement schemes in product networks based on the assumption of perfect resource placement in their underling basic graphs. Our techniques use known schemes for the basic networks as their building blocks for deploying the resource placement scheme in the product network. This seriously cuts down the expenses required for deploying and rescaling the network. In particular, we propose some efficient algorithms for adjacency placement in a product of k$k$ heterogeneous graphs. Furthermore, we extend our approach and present algorithms for distant resource placement in product networks.