风电场数据中心Hadoop云平台作业调度算法研究

风电场数据中心包含状态监测、数据采集等实时类作业和非实时类作业,采用C/S结构存在资源利用率不平衡、管理与维护成本高等缺点。设计了一种基于Hadoop云平台的数据中心架构;针对开源Hadoop平台现有FIFO调度器不能满足实时监测系统要求,在原有FIFO调度器的基础上,设计了一种双队列的作业调度器,综合考虑作业的截止时间和优先级来进行作业调度决策,实验结果表明,与FIFO调度器相比,双队列的作业调度器在集群负载较大时能够表现出较好的性能,保证实时类作业能够优先执行,为风电机组的安全运行提供保障。     

A simple distributed scheduling policy for parallel interactive continuous media servers

In this paper we discuss the design of parallel interactive continuous media servers suitable for the implementation of scalable server-based media delivery services like Video-on-Demand or Teleshopping. The main design problems for the development of such servers is to ensure the just-in-time delivery of media elements in order to maximize the Quality of Service and to minimize the buffer size at the user site. Just-in-time delivery means that the media elements should be sent as late as possible to the users but early enough to ensure a continuous replay of the media. This is important because clients have to provide buffer space for data arriving to early. The Quality of Service measures the number of data elements arrived in time at the user side. Thus, the real-time properties of the internal communication network as well as the congestion arising at the disks are of highest importance. We present models for parallel media servers and a very simple scheduler that is fully distributed and can therefore easily be implemented on a scalable parallel continuous media server. For each requested data element the scheduler sends a request to the storage subsystems at a point of time only depending on the deadline of that request, i.e. the time the data has to be delivered to the user, and the length of the path the data has to be routed through the internal network of the parallel server. In order to minimize the buffer space at the user site, and to maximize the Quality of Service, we develop timing strategies for the scheduler using simulation results as well as analytical observations.     

Modified rate-monotonic algorithm for scheduling periodic jobs withdeferred deadlines

The deadline of a request is the time instant at which its execution must complete. The deadline of the request in any period of a job with deferred deadline is some time instant after the end of the period. The authors describe a semi-static priority-driven algorithm for scheduling periodic jobs with deferred deadlines: each job is assigned two priorities, the higher one for old requests and the lower one for the current request. This algorithm is called the modified rate-monotonic algorithm and is based on the well-known rate-monotonic algorithm. It is shown that the modified rate-monotonic algorithm is optimal when the deadline of every job is deferred by max (1, γ-1) periods or more, where γ is the ratio between the longest period and the shortest period. When the deadline of each job is deferred by one period of the job, any set of n independent jobs whose total utilization is equal to or less than [1+n(2¹n/-1)]/2 can be feasibly scheduled by this algorithm. This bound approaches 0.845 when n approaches infinity     

Quantum-Based Earliest Deadline First Scheduling for Multiservices

Latency-rate (LR) schedulers have shown their ability in providing fair and weighted sharing of bandwidth with an upper bound on delivery latency of packets while earliest departure first (EDF) schedulers have shown their ability in providing LR-decoupled service whereby the delivery latency of packets is not bounded by the reserved rate. However, EDF schedulers require traffic shapers to ensure flow protection. We propose quantum-based earliest deadline first scheduling (QEDF), a quantum-based scheduler that provides flow protection, throughput guarantee and delay bound guarantee for flows that require LR-coupled and LR-decoupled types of reservations. It classifies flows into time-critical (TC), jitter-sensitive (JS), and rate-based (RB) classes and uses a quality-of-service forwarding rule to determine the next packet to be serviced by the scheduler. It provides nonpreemptive priority service to TC queues. This allows LR-decoupled reservation for flows that have a low rate and intolerable delay. Packets from JS queues can be delayed by other packets if forwarding the latter will not result in the former missing its deadline. As a quantum-based scheduler, the QEDF scheduler provides throughput guarantees for RB queues. We present both analytical and simulation results of QEDF, whereby we evaluated QEDF in its deployment as a single-class as well as a multiservice scheduler     

A design of RFTOG model for distributed real-time applications

In this paper, we design the Real-Time Fault-Tolerant Object Group (RFTOG) model that supports the grouping of distributed objects that are required for distributed application. The proposed model basically provides two services. One is the group management service, which supports both consistency maintenance and transparency of the replicated objects with a variety of replication mechanisms. It also provides the load balancing of distributed applications. The other is real-time service in an object group. When the clients request the service to the service object selected through the load balance, this service guarantees the service execution within deadline for the clients’ requests. We develop the Naval Air Defense System (NADS) simulator for verifying the effectiveness of the services proposed by the RFTOG model.     

A note on on-line broadcast scheduling with deadlines

In this paper, we study an on-line broadcast scheduling problem with deadlines, in which the requests asking for the same page can be satisfied simultaneously by broadcasting this page, and every request is associated with a release time, deadline and a required page with a unit size. The objective is to maximize the number of requests satisfied by the schedule. In this paper, we focus on an important special case where all the requests have their spans (the difference between release time and deadline) less than 2. We give an optimal online algorithm, i.e., its competitive ratio matches the lower bound of the problem.     

Evaluation of a CPU Scheduling Mechanism for Multimedia Systems

Multimedia applications handling audio and video data have to obey time characteristics of these media types. Besides a basic functionality to express time relations, correctness with respect to time constraints requires mechanisms which lead to favoured processing of multimedia operations. CPU scheduling techniques based on the experience from real-time operating systems offer a solution and provide multimedia applications with the ability to meet time-related quality of service requirements. This paper discusses mechanisms to express time in multimedia systems and describes an implementation of a CPU scheduler designed to run under IBM's UNIX derivate AIX. The evaluation of the implementation based on measurements shows that the scheduler is able to support the time requirements of multimedia applications and that such mechanisms are indeed necessary since otherwise deadline violations occur.     

<Emphasis FontCategory="NonProportional">rt-muse</Emphasis>: measuring real-time characteristics of execution platforms

Operating systems code is often developed according to principles like simplicity, low overhead, and low memory footprint. Schedulers are no exceptions. A scheduler is usually developed with flexibility in mind, and this restricts the ability to provide real-time guarantees. Moreover, even when schedulers can provide real-time guarantees, it is unlikely that these guarantees are properly quantified using theoretical analysis that carries on to the implementation. To be able to analyze the guarantees offered by operating systems’ schedulers, we developed a publicly available tool that analyzes timing properties extracted from the execution of a set of threads and computes the lower and upper bounds to the supply function offered by the execution platform, together with information about migrations and statistics on execution times. rt-muse evaluates the impact of many application and platform characteristics including the scheduling algorithm, the amount of available resources, the usage of shared resources, and the memory access overhead. Using rt-muse, we show the impact of Linux scheduling classes, shared data and application parallelism, on the delivered computing capacity. The tool provides useful insights on the runtime behavior of the applications and scheduler. In the reported experiments, rt-muse detected some issues arising with the real-time Linux scheduler: despite having available cores, Linux does not migrate SCHED_RR threads which are enqueued behind SCHED_FIFO threads with the same priority.     

Scheduling in the situation calculus: A case study

We illustrate the utility of the situation calculus for representing complex scheduling tasks by axiomatizing a deadline driven scheduler in the language. The actions arising in such a scheduler are examples of natural actions, as investigated in the concurrent situation calculus by Pinto (PhD thesis, 1994), and later by Reiter (Proc. Common Sense 96, 1996). Because the deadline driven scheduler is sequential, we must first suitably modify Reiter's approach to natural actions so it applies to the sequential case. Having done this, we then show how the situation calculus axiomatization of this scheduler yields a very simple simulator in GOLOG, a situation calculus-based logic programming language for dynamic domains. This revised version was published online in June 2006 with corrections to the Cover Date.     

Heterogeneous CPU Services Using Differentiated Admission Control

We present an adaptive rate-controlled scheduler for heterogeneous applications running on general purpose computers. Our scheduler can effectively support diverse application requirements. It employs uniform rate-based sharing. Application heterogeneity is satisfied by partitioning CPU capacity into service classes, each with a different criterion for admission control. As a result, we are able to provide at once guaranteed performance, flexible allocation of rates with excellent scalability and intermediate service classes offering tradeoffs between reserved rate utilization and the strength of guarantees. Our scheduler has been implemented in Solaris 2.5.1. It runs existing applications without modifications. We present experimental results showing the scalability, efficiency, guaranteed performance, and overload performance aspects of our scheduler. We demonstrate the importance of priority inheritance implemented in our scheduler for stable system performance.     

Courier: Multi-dimensional QoS guarantees for the consolidated storage system

The increasing cost and complexity of data management is driving data centers to consolidate resource and provide storage service for multiplex applications. Therefore, storage systems must be able to guarantee multi-dimensional Quality of Service (QoS) for various applications. However, satisfying performance targets for each workload is challenging, because that the I/O characteristics of workloads usually varies widely and capability of storage system changes significantly. In this paper, we design and implement a novel QoS scheduler, Courier, to maintain satisfactory performance for applications even in this highly-volatile scenario. Courier dynamically alternates between a feedback-based latency controller and reward budget-based scheduling to achieve per-application performance requirement. The feedback-based controller is employed to estimate request service times and adjust scheduling strategy dynamically. Based on the estimation, it can identify time-critical requests from throughput-sensitive requests and schedule applications with time-critical requests preferentially to avoid latency violations. In addition, Courier rewards well-behavior application with more budget to maintain high storage utilization while providing performance guarantees. We evaluate the effectiveness of our approach using synthetic and real workloads, and the results show that Courier has good ability to achieve per-application performance targets.     

A nonpreemptive real-time scheduler with recovery from transient faults and its implementation

Real-time systems (RTS) are those whose correctness depends on satisfying the required functional as well as the required temporal properties. Due to the criticality of such systems, recovery from faults is an essential part of a RTS. In many systems, such as those supporting space applications, single event upsets (SEUs) are the prevalent type of faults; SEUs are transient faults and affect a single task at a time. We present a scheme to guarantee that the execution of real-time tasks can tolerate SEUs and intermittent faults assuming any queue-based scheduling technique. Three algorithms are presented to solve the problem of adding fault tolerance to a queue of real-time tasks by reserving sufficient slack in a schedule so that recovery can be carried out before the task deadline without compromising guarantees given to other tasks. The first algorithm is a dynamic programming optimal solution, the second is a linear-time heuristic for scheduling dynamic tasks, and the third algorithm comprises extensions to address queues with gaps between tasks (gaps are caused by precedence, resource, or timing constraints). We show through simulations that the heuristics closely approximate the optimal algorithm. Finally, we describe the implementation of the modified admission control algorithm, non-preemptive scheduler, and recovery mechanism in the FT-RT-Mach operating system.     

On-Line Algorithms for the Dynamic Traveling Repair Problem

We consider the dynamic traveling repair problem in which requests with deadlines arrive through time on points in a metric space. Servers move from point to point at constant speed. The goal is to plan the motion of servers so that the maximum number of requests are met by their deadline. We consider a restricted version of the problem in which there is a single server and the length of time between the arrival of a request and its deadline is constant. We give upper bounds for the competitive ratio of two very natural algorithms as well as several lower bounds for any deterministic algorithm. Most of the results in this paper are expressed as a function of β, the diameter of the metric space. In particular, we prove that the upper bound given for one of the two algorithms is within a constant factor of the best possible competitive ratio.     

An object replication algorithm for real-time distributed databases

A real-time distributed database system (RTDDBS) must maintain the consistency constraints of objects and must also guarantee the time constraints imposed by each request arriving at the system. Such a time constraint of a request is usually defined as a deadline period, which means that the request must be serviced on or before its time constraint. Servicing these requests may incur I/O costs, control-message transferring costs or data-message transferring costs. As a result, in our work, we first present a mathematical model that considers all these costs. Using this cost model, our objective is to service all the requests on or before their respective deadline periods and minimize the total servicing cost. To this end, from theoretical standpoint, we design a dynamic object replication algorithm, referred to as Real-time distributed dynamic Window Mechanism (RDDWM), that adapts to the random patterns of read-write requests. Using competitive analysis, from practical perspective, we study the performance of RDDWM algorithm under two different extreme conditions, i.e., when the deadline period of each request is sufficiently long and when the deadline period of each request is very short. Several illustrative examples are provided for the ease of understanding. Recommended by: Ashfaq Khokhar     

An optimal algorithm for scheduling soft aperiodic tasks indynamic-priority preemptive systems

The paper addresses the problem of jointly scheduling tasks with both hard and soft real time constraints. We present a new analysis applicable to systems scheduled using a priority preemptive dispatcher, with priorities assigned dynamically according to the EDF policy. Further, we present a new efficient online algorithm (the acceptor algorithm) for servicing aperiodic work load. The acceptor transforms a soft aperiodic task into a hard one by assigning a deadline. Once transformed, aperiodic tasks are handled in exactly the same way as periodic tasks with hard deadlines. The proposed algorithm is shown to be optimal in terms of providing the shortest aperiodic response time among fixed and dynamic priority schedulers. It always guarantees the proper execution of periodic hard tasks. The approach is composed of two parts: an offline analysis and a run time scheduler. The offline algorithm runs in pseudopolynomial time O(mn), where n is the number of hard periodic tasks and m is the hyperperiod/min deadline     

On automated lesson construction from electronic textbooks

An electronic book may be viewed as an application with a multimedia database. We define an electronic textbook as an electronic book that is used in conjunction with instructional resources such as lectures. We propose an electronic textbook data model with topics, topic sources, metalinks (relationships among topics), and instructional modules, which are multimedia presentations possibly capturing real-life lectures of instructors. Using the data model, the system provides users a topic-guided multimedia lesson construction. We concentrate, in detail, on the use of one metalink type in lesson construction, namely, prerequisite dependencies, and provide a sound and complete axiomatization of prerequisite dependencies. We present a simple automated way of constructing lessons for users where the user lists a set of topic names (s)he is interested in, and the system automatically constructs and delivers the "best" user-tailored lesson as a multimedia presentation, where "best" is characterized in terms of both topic closures with respect to prerequisite dependencies and what the user knows about topics. We model and present sample lesson construction requests for users, discuss their complexity, and give algorithms that evaluate such requests. For expensive lesson construction requests, we list heuristics and empirically evaluate their performance. We also discuss the worst-case performance guarantees of lesson request algorithms.     

Minimizing bandwidth requirements for on-demand data delivery

Two recent techniques for multicast or broadcast delivery of streaming media can provide immediate service to each client request, yet achieve considerable client stream sharing which leads to significant server and network bandwidth savings. The paper considers: 1) how well these recently proposed techniques perform relative to each other and 2) whether there are new practical delivery techniques that can achieve better bandwidth savings than the previous techniques over a wide range of client request rates. The principal results are as follows: First, the recent partitioned dynamic skyscraper technique is adapted to provide immediate service to each client request more simply and directly than the original dynamic skyscraper method. Second, at moderate to high client request rates, the dynamic skyscraper method has required server bandwidth that is significantly lower than the recent optimized stream tapping/patching/controlled multicast technique. Third, the minimum required server bandwidth for any delivery technique that provides immediate real-time delivery to clients increases logarithmically (with constant factor equal to one) as a function of the client request arrival rate. Furthermore, it is (theoretically) possible to achieve very close to the minimum required server bandwidth if client receive bandwidth is equal to two times the data streaming rate and client storage capacity is sufficient for buffering data from shared streams. Finally, we propose a new practical delivery technique, called hierarchical multicast stream merging (HMSM), which has a required server bandwidth that is lower than the partitioned dynamic skyscraper and is reasonably close to the minimum achievable required server bandwidth over a wide range of client request rates     

A genetic algorithm-based scheduler for multiproduct parallel machine sheet metal job shop

This paper presents a genetic algorithm-based job-shop scheduler for a flexible multi-product, parallel machine sheet metal job shop. Most of the existing research has focused only on permutation job shops in which the manufacturing sequence and routings are strictly in a predefined order. This effectively meant that only the jobs shops with little or no flexibility could be modeled using these models. The real life job shops may have flexibility of routing and sequencing. Our paper proposes one such model where variable sequences and multiple routings are possible. Another limitation of the existing literature was found to be negligence of the setup times. In many job shops like sheet metal shops, setup time may be a very sizable portion of the total make-span of the jobs, hence setup times will be considered in this work. One more flexibility type arises as a direct consequence of the routing flexibility. When there are multiple machines (parallel machines) to perform the same operation, the job could be routed to one or more of these machines to reduce the make-span. This is possible in situations where each job consists of a pre-defined quantity of a specified product. In other words, same job is quantity-wise split into two or more parts whenever it reduces the makespan. This effectively assumes that the setup cost is negligible. This model has been implemented on a real-life industry problem using VB.Net programming language. The results from the scheduler are found to be better than those obtained by simple sequencing rules.     

基于LSTM的集群用户作业执行时间预测模型

为提升服务质量,数据中心需要确保在规定的截止时间前完成用户作业,因此必须根据实时的系统资源对作业进行有效的调度。提出了一种作业调度算法,根据预测的作业执行时间进行批作业调度,以最小化批作业的完成时间。作业执行时间预测模型基于长短期记忆LSTM网络,根据用户作业类型、作业量、作业需要的CPU核数和内存数量,以及作业需要的资源在系统总资源中的占比,对用户作业的执行时间进行预测。预测结果用于判断集群是否有能力按时完成用户作业,同时为合理安排各作业的执行顺序提供依据。通过实验确定了影响LSTM时间预测模型性能的各超参数取值,如迭代次数、学习率和网络层数等。实验表明,与SVR模型、ARIMA模型和BP模型相比,基于LSTM的作业执行时间预测模型的决定系数R²分别有2.97%,2.34%和5.66%的提升效果,且预测的平均误差仅为0.78%。     

A multi-level scheduler for batch jobs on grids

This paper proposes a two-level scheduler for dynamically scheduling a continuous stream of sequential and multi-threaded batch jobs on grids, made up of interconnected clusters of heterogeneous single-processor and/or symmetric multiprocessor machines. The scheduler aims to schedule arriving jobs respecting their computational and deadline requirements, and optimizing the hardware and software resource usage. At the top of the hierarchy a lightweight meta-scheduler (MS) classifies incoming jobs according to their requirements, and schedules them among the underlying resources balancing the workload. At cluster level a Flexible Backfilling algorithm carries out the job machine associations by exploiting dynamic information about the environment. Scheduling decisions at both levels are based on job priorities computed by using different sets of heuristics. The different proposals have been compared through simulations. Performance figures show the feasibility of our approach.