实时虚拟化环境中的负载均衡与准入控制算法

虚拟化技术在实时嵌入式系统中的应用日趋广泛,但是目前虚拟化环境中常见的调度与负载均衡算法并不适用于硬实时系统中。为满足多核平台上虚拟化环境中对实时任务的支持,通过对Xen虚拟化环境中的SEDF调度算法进行改进,提供了一种在多核硬件平台下虚拟化环境中的准入控制与负载均衡算法。该算法能够保证每个处理器核上的工作量不会超载,并保证每个虚拟机中任务的实时性及其服务质量。算法实现较为简单、运行时开销较小。     

Xen虚拟机Credit调度算法的实时性能分析

为了降低开销以及增加灵活性,通过虚拟化技术将多个系统运行在一个通用计算平台上已成为复杂实时嵌入式系统的趋势。Xen是近年来应用最广泛的虚拟化技术,对其默认使用的Credit调度算法进行实时性能分析,使得能够直接对运行在Xen上的实时系统进行可调度性测试,并且可以通过形式化的资源界限函数对Credit的实时性进行直观的评估。首先分析了Credit调度算法的基本实现,提出并且证明了一种配置VCPU参数的方法使得Credit的实时性得到提升,在此基础上,通过证明得到了Credit算法的基本性质,并得出其在最坏情况下为VCPU分配的资源函数曲线。     

可变负载动态反馈弹性调度模型及其算法研究

由于工作负载的动态变化,以多媒体应用为代表的软实时系统的运行具有很大的不确定性.在这种情况下,依靠任务的静态属性进行调度分析和决策不足以为系统提供高效、实用的资源分配支持.提出一种弹性资源调度算法,该算法周期地采集系统的作业总数和作业丢失数,并以此为根据改变部分软实时任务的作业周期,以调整系统在下一个采样周期内的作业总数,达到满足任务的QoS(quality of service)、接纳尽可能多的服务请求、提高系统的并发服务能力的目的.详细分析了模型结构和核心算法的实现机制,并利用模拟平台对该算法进行了验证.实验结果表明,该算法在提高资源利用效率的同时,还具有良好的稳定性和收敛性.     

嵌入式Forth操作系统实时调度算法研究

针对目前嵌入式Forth操作系统中缺乏实时调度机制的问题,对基于Forth虚拟机架构的嵌入式操作系统中多任务调度的关键技术进行了研究。采用Forth虚拟机技术,新定义了一种中断任务类型来处理实时突发事件,并给出了一种新的任务调度算法来调度 Forth系统中终端任务、后台任务以及中断任务顺利运行。实验结果表明,改进后的 Forth 系统能够通过实时调度处理突发事件,并且实时响应度高,尤其适用于对实时性有要求的嵌入式环境中,以满足日趋复杂的嵌入式环境对高效操作系统和 Forth 技术的应用需求。     

基于(m,k)-firm约束规范的混合任务调度算法研究

讨论了在准实时环境下,包括准实时周期任务和准实时非周期任务在内的混合任务调度算法HTSF.HTSF算法是在满足周期任务(m,k)-firm 约束规范的前提下提高非周期任务可调度性,同时合理利用可用空闲时间,提高整个系统的服务质量.HTSF算法给出了非周期任务的可调度性分析方法,同时采用静态调度与动态调度相结合的方法调度周期任务和非周期任务.模拟测试结果显示,系统对非周期任务的接收率比同类相关算法的接收率高.     

基于动态优先级策略的最优软非周期任务调度算法

周期任务与非周期任务的混合调度是实时调度研究的一个重要方向 通过定义“调度”和“逆调度” ,对实时周期任务集在使用EDF算法调度时的可挪用时间进行分析 ,求出了周期任务集在使用EDF调度时的最大可挪用时间 在此基础上 ,提出用于缩短非周期任务响应时间和周转时间的调度算法———ISA(idlestealingalgorithm) ISA算法充分使用最大可挪用时间 ,在保证周期任务满足最后期限的同时能取得非周期任务的最优响应时间和周转时间 证明了ISA算法的最优性 ,并使用仿真实验进行了性能验证     

先进飞机软件实时性能优化与测试算法

阐述了先进飞机电气系统处理机的功能;为了满足先进飞机电气系统处理机的强实时性能,着重探讨了在实时操作系统VxWorks下将电气系统处理机执行软件功能优化为若干任务,并针对普通RMS算法只能对系统中周期任务进行有效调度而不能对系统中的非周期任务进行有效调度的局限,利用分布假设检验改进RMS算法对非周期任务的调度能力,最后定量讨论了系统整个任务集的实时性和可调度性;由实际测试结果可知,该优化算法任务划分合理,可以保证强实时周期、非周期任务满足其时限要求.     

基于 Linux的实时控制系统的调度算法研究

在实时系统中,实时调度算法是影响实时性能的关键因素。本文首先分析了当前基于Linux的内核实时支持的相关主流技术,说明了Linux在实时性支持上的现状和弱点,综合比较了各种解决方案的优缺点。以往对实时调度算法的研究着重于硬实时性的满足,本文基于具体应用的特殊性以及当前对实时调度研究的发展趋势,对共存于同一系统中的
的周期性实时任务和非周期性任务的混合调度问题做进一步的探讨,提出一种实时任务的层次调度算法,保证了带宽的利用,克服了传统混合调度算法处理器利用率受限制、系统开销较大和非周期部分响应时间长的问题。基于这些研究成果,提出了改造方案,并在Linux操作系统中予以了实现。     

VMSF—一种内核级虚拟机监控器调度框架

虚拟化技术由于具有提高资源利用率、降低系统总体拥有成本等优点得到越来越多的关注。虚拟机成为计算机系统的一种新型应用模式,但虚拟机应用在服务质量保证和协同运行等方面与传统商用操作系统面向的应用不同,虚拟机监控器应针对此类应用的特点设计相应的调度算法。但是,在传统基于宿主操作系统的虚拟化技术中,虚拟机的调度由宿主操作系统的标准调度器完成。本文提出一种不修改宿主操作系统现有调度机制的虚拟机调度扩展框架VMSF,该框架允许第三方自行开发适于虚拟机系统的调度算法。最后通过在Linux上开源的内核级虚拟机监控器KVM上移植Xen的Credit调度器验证了本文研究的有效性。     

单机实时系统中的一种混合型实时容错调度算法

目前研究单机实时系统的调度算法文章大多只能调度单一类型的任务。本文在PKSA算法的基础上,建立了一种混合型实时容错模型,提出一种调度算法不仅可以调度有容错需求的周期任务,同时也能够调度无容错需求的周期任务和非周期非实时任务,实现了调度混合型任务的目的。     

Task mapper and application-aware virtual machine scheduler oriented for parallel computing

We design a task mapper TPCM for assigning tasks to virtual machines, and an application-aware virtual machine scheduler TPCS oriented for parallel computing to achieve a high performance in virtual computing systems. To solve the problem of mapping tasks to virtual machines, a virtual machine mapping algorithm (VMMA) in TPCM is presented to achieve load balance in a cluster. Based on such mapping results, TPCS is constructed including three components: a middleware supporting an application-driven scheduling, a device driver in the guest OS kernel, and a virtual machine scheduling algorithm. These components are implemented in the user space, guest OS, and the CPU virtualization subsystem of the Xen hypervisor, respectively. In TPCS, the progress statuses of tasks are transmitted to the underlying kernel from the user space, thus enabling virtual machine scheduling policy to schedule based on the progress of tasks. This policy aims to exchange completion time of tasks for resource utilization. Experimental results show that TPCM can mine the parallelism among tasks to implement the mapping from tasks to virtual machines based on the relations among subtasks. The TPCS scheduler can complete the tasks in a shorter time than can Credit and other schedulers, because it uses task progress to ensure that the tasks in virtual machines complete simultaneously, thereby reducing the time spent in pending, synchronization, communication, and switching. Therefore, parallel tasks can collaborate with each other to achieve higher resource utilization and lower overheads. We conclude that the TPCS scheduler can overcome the shortcomings of present algorithms in perceiving the progress of tasks, making it better than schedulers currently used in parallel computing.     

基于云科学工作流调度的代价与能效优化算法

为了降低云环境中科学工作流调度的执行代价与数据中心能耗,提出了一种基于能效感知的工作流调度代价最优化算法CWCO-EA。算法在满足截止时间约束下,以最小化工作流执行代价与降低能耗为目标,将工作流的任务调度划分为四步执行。首先,通过代价效用的概念设计虚拟机选择策略,实现了子makespan约束下的任务与最优虚拟机间的映射;其次,通过串行与并行任务合并策略,同步降低了工作流的执行代价与能耗;然后,通过空闲虚拟机重用机制,改善了租用虚拟机的利用率,进一步提高了能效;最后,通过任务松驰策略实现了租用虚拟机的能力回收,节省了能耗。通过四种科学工作流的仿真实验,结果表明,CWCO-EA算法比较同类型算法,在满足截止时间的同时,可以同步降低工作流的执行代价与执行能耗。     

Batch scheduling of consolidated virtual machines based on their workload interference model

The use of virtualization technology (VT) has become widespread in modern datacenters and Clouds in recent years. In spite of their many advantages, such as provisioning of isolated execution environments and migration, current implementations of VT do not provide effective performance isolation between virtual machines (VMs) running on a physical machine (PM) due to workload interference of VMs. Generally, this interference is due to contention on physical resources that impacts performance in different workload configurations. To investigate the impacts of this interference, we formalize the concept of interference for a consolidated multi-tenant virtual environment. This formulation, represented as a mathematical model, can be used by schedulers to estimate the interference of a consolidated virtual environment in terms of the processing and networking workloads of running VMs, and the number of consolidated VMs. Based on the proposed model, we present a novel batch scheduler that reduces the interference of running tenant VMs by pausing VMs that have a higher impact on proliferation of the interference. The scheduler achieves this by selecting a set of VMs that produce the least interference using a 0–1 knapsack problem solver. The selected VMs are allowed to run and other VMs are paused. Users are not troubled by the pausing and resumption of VMs for a short time because the scheduler has been designed for the execution of batch type applications such as scientific applications. Evaluation results on the makespan of VMs executed under the control of our scheduler have shown nearly 33% improvement in the best case and 7% improvement in the worst case compared to the case in which all VMs are running concurrently. In addition, the results show that our scheduling algorithm outperforms serial and random scheduling of VMs as well.     

资源调度等待开销感知的虚拟机整合

近年来,数据中心庞大的能源开销问题引起广泛关注.虚拟化管理平台可以通过虚拟机迁移技术将虚拟机整合到更少的服务器上,从而提高数据中心能源有效性.对面向数据中心节能的虚拟机整合研究工作进行调研,并总结虚拟机整合研究存在的3个挑战.针对已有工作未考虑虚拟机等待资源调度带来的服务器资源额外开销这种现象,开展了资源调度等待开销感知的虚拟机整合研究.从理论和实验上证明了在具有实际意义的约束条件下,存在着虚拟机等待资源调度带来的服务器资源额外开销,且随着整合虚拟机数量的增长保持稳定.基于典型工作负载的实验结果表明,这个额外开销平均占据了11.7%的服务器资源开销.此外,提出了资源预留整合（MRC）算法,用于改进已有的虚拟机整合算法.算法模拟实验结果表明,MRC算法相比于常用的虚拟机整合算法FFD（first fit decreasing）,明显降低了服务器资源溢出概率.     

Energy-efficiency enhanced virtual machine scheduling policy for mixed workloads in cloud environments

Virtualization technology is an effective approach to improving the energy-efficiency in cloud platforms; however, it also introduces many energy-efficiency losses especially when I/O virtualization is involved. In this paper, we present an energy-efficiency enhanced virtual machine (VM) scheduling policy, namely Share-Reclaiming with Collective I/O (SRC-I/O), with aiming at reducing the energy-efficiency losses caused by I/O virtualization. The proposed SRC-I/O scheduler allows VMs to reclaim extra CPU shares in certain conditions so as to increase CPU utilization. Meanwhile, it separates I/O-intensive VMs from CPU-intensive ones and schedules them in a collective manner, so as to reduce the context-switching cost when scheduling mixed workloads. Extensive experiments are conducted on various platforms to investigate the performance of the proposed scheduler. The results indicate that when the system is in presence of mixed workloads, SRC-I/O scheduler outperforms many existing VM schedulers in terms of energy-efficiency and I/O responsiveness.     

Energy-efficient Tasks Scheduling Heuristics with Multi-constraints in Virtualized Clouds

Reducing energy consumption has become an important task in cloud datacenters. Many existing scheduling approaches in cloud datacenters try to consolidate virtual machines (VMs) to the minimum number of physical hosts and hence minimize the energy consumption. VM live migration technique is used to dynamically consolidate VMs to as few PMs as possible; however, it introduces high migration overhead. Furthermore, the cost factor is usually not taken into account by existing approaches, which will lead to high payment cost for cloud users. In this paper, we aim to achieve energy reduction for cloud providers and payment saving for cloud users, and at the same time, without introducing VM migration overhead and without compromising deadline guarantees for user tasks. Motivated by the fact that some of the tasks have relatively loose deadlines, we can further reduce energy consumption by proactively postponing the tasks without waking up new physical machines (PMs). A heuristic task scheduling algorithm called Energy and Deadline Aware with Non-Migration Scheduling (EDA-NMS) algorithm is proposed, which exploits the looseness of task deadlines and tries to postpone the execution of the tasks that have loose deadlines in order to avoid waking up new PMs. When determining the VM instant types, EDA-NMS selects the instant types that are just sufficient to guarantee task deadline to reduce user payment cost. The results of extensive experiments show that our algorithm performs better than other existing algorithms on achieving energy efficiency without introducing VM migration overhead and without compromising deadline guarantees.     

Integrating QoS awareness with virtualization in cloud computing systems for delay-sensitive applications

Cloud computing provides scalable computing and storage resources over the Internet. These scalable resources can be dynamically organized as many virtual machines (VMs) to run user applications based on a pay-per-use basis. The required resources of a VM are sliced from a physical machine (PM) in the cloud computing system. A PM may hold one or more VMs. When a cloud provider would like to create a number of VMs, the main concerned issue is the VM placement problem, such that how to place these VMs at appropriate PMs to provision their required resources of VMs. However, if two or more VMs are placed at the same PM, there exists certain degree of interference between these VMs due to sharing non-sliceable resources, e.g. I/O resources. This phenomenon is called as the VM interference. The VM interference will affect the performance of applications running in VMs, especially the delay-sensitive applications. The delay-sensitive applications have quality of service (QoS) requirements in their data access delays. This paper investigates how to integrate QoS awareness with virtualization in cloud computing systems, such as the QoS-aware VM placement (QAVMP) problem. In addition to fully exploiting the resources of PMs, the QAVMP problem considers the QoS requirements of user applications and the VM interference reduction. Therefore, in the QAVMP problem, there are following three factors: resource utilization, application QoS, and VM interference. We first formulate the QAVMP problem as an Integer Linear Programming (ILP) model by integrating the three factors as the profit of cloud provider. Due to the computation complexity of the ILP model, we propose a polynomial-time heuristic algorithm to efficiently solve the QAVMP problem. In the heuristic algorithm, a bipartite graph is modeled to represent all the possible placement relationships between VMs and PMs. Then, the VMs are gradually placed at their preferable PMs to maximize the profit of cloud provider as much as possible. Finally, simulation experiments are performed to demonstrate the effectiveness of the proposed heuristic algorithm by comparing with other VM placement algorithms.     

Honey bee behavior inspired load balancing of tasks in cloud computing environments

Scheduling of tasks in cloud computing is an NP-hard optimization problem. Load balancing of non-preemptive independent tasks on virtual machines (VMs) is an important aspect of task scheduling in clouds. Whenever certain VMs are overloaded and remaining VMs are under loaded with tasks for processing, the load has to be balanced to achieve optimal machine utilization. In this paper, we propose an algorithm named honey bee behavior inspired load balancing (HBB-LB), which aims to achieve well balanced load across virtual machines for maximizing the throughput. The proposed algorithm also balances the priorities of tasks on the machines in such a way that the amount of waiting time of the tasks in the queue is minimal. We have compared the proposed algorithm with existing load balancing and scheduling algorithms. The experimental results show that the algorithm is effective when compared with existing algorithms. Our approach illustrates that there is a significant improvement in average execution time and reduction in waiting time of tasks on queue.     

Effects of dynamic isolation for full virtualized RTOS and GPOS guests

Industrial systems currently include not only control processing with real-time operating system (RTOS) but also information processing with general-purpose operating system (GPOS). Multicore-based virtualization is an attractive option to provide consolidated environment when GPOS and RTOS are put in service on a single hardware platform. Researches on this technology have predominantly focused on the schedulability of RTOS virtual machines (VMs) by completely dedicated physical-CPUs (pCPUs) but have rarely considered parallelism or the throughput of the GPOS. However, it is also important that the multicore-based hypervisor adaptively selects pCPU assignment policy to efficiently manage resources in modern industrial systems. In this paper, we report our study on the effects of dynamic isolation when two mixed criticality systems are working on one platform. Based on our investigation of mutual interferences between RTOS VMs and GPOS VMs, we found explicit effects of dynamic isolation by special events. While maintaining low RTOS VMs scheduling latency, a hypervisor should manage pCPUs assignment by event-driven and threshold-based strategies to improve the throughput of GPOS VMs. Furthermore, we deal with implicit negative effects of dynamic isolation caused by the synchronization inside a GPOS VM, then propose a process of urgent boosting with dynamic isolation. All our methods are implemented in a real hypervisor, KVM. In experimental evaluation with benchmarks and an automotive digital cluster application, we analyzed that proposed dynamic isolation guarantees soft real-time operations for RTOS tasks while improving the throughput of GPOS tasks on a virtualized multicore system.     

Task-Based System Load Balancing in Cloud Computing Using Particle Swarm Optimization

Live virtual machine (VM) migration is a technique for achieving system load balancing in a cloud environment by transferring an active VM from one physical host to another. This technique has been proposed to reduce the downtime for migrating overloaded VMs, but it is still time- and cost-consuming, and a large amount of memory is involved in the migration process. To overcome these drawbacks, we propose a Task-based System Load Balancing method using Particle Swarm Optimization (TBSLB-PSO) that achieves system load balancing by only transferring extra tasks from an overloaded VM instead of migrating the entire overloaded VM. We also design an optimization model to migrate these extra tasks to the new host VMs by applying Particle Swarm Optimization (PSO). To evaluate the proposed method, we extend the cloud simulator (Cloudsim) package and use PSO as its task scheduling model. The simulation results show that the proposed TBSLB-PSO method significantly reduces the time taken for the load balancing process compared to traditional load balancing approaches. Furthermore, in our proposed approach the overloaded VMs will not be paused during the migration process, and there is no need to use the VM pre-copy process. Therefore, the TBSLB-PSO method will eliminate VM downtime and the risk of losing the last activity performed by a customer, and will increase the Quality of Service experienced by cloud customers.