Many time-critical applications require predictable performance and tasks in these applications have deadlines to be met. In this paper, we propose an efficient algorithm for nonpreemptive scheduling of dynamically arriving real-time tasks (aperiodic tasks) in multiprocessor systems. A real-time task is characterized by its deadline, resource requirements, and worst case computation time on p processors, where p is the degree of parallelization of the task. We use this parallelism in tasks to meet their deadlines and, thus, obtain better schedulability compared to nonparallelizable task scheduling algorithms. To study the effectiveness of the proposed scheduling algorithm, we have conducted extensive simulation studies and compared its performance with the myopic [8] scheduling algorithm. The simulation studies show that the schedulability of the proposed algorithm is always higher than that of the myopic algorithm for a wide variety of task parameters. © 1998 IEEE.

Chebiyyam Siva Ram Murthy

Department of Computer Science and Engineering

Computer simulation

parallel algorithms

Real time systems

resource allocation

DYNAMIC TASK SCHEDULING

Parallel processing systems

IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

An efficient dynamic scheduling algorithm for multiprocessor real-time systems

IEEE Transactions on Parallel and Distributed Systems

The problem of real-time communication over a multiple access network has been well studied in the recent past. However, there are very few protocols that can bound the worst case channel access time to ensure predictability of message transmission for the LAN environment. In addition, there has been no prior work addressing real-time communication over a switched (extended) local area network (SLAN), where several LAN segments are connected through a switch. In this paper, we propose real-time protocols for the LAN and the SLAN. The proposed protocols are based on CSMA/CD with deterministic collision resolution and belong to the dynamic planning based category, where an admission test is performed for guaranteeing message transmission. The admission test used in the proposed protocols is based on the worst case channel access time that can elapse before a particular node can start transmitting its message. We also compute the worst case buffer requirement at the switch for the proposed SLAN protocols. We study the effectiveness of the proposed protocols through extensive simulation studies. © 2001 Elsevier Science B.V. All rights reserved.

Computer Communications

Dynamic planning based protocols for real-time communication in LAN and switched LAN environments

A majority of today's real-time systems assume a priori knowledge of task characteristics and hence are based on static designs which contribute to their high cost and inflexibility. The next generation of hard real-time systems must be designed to be dynamic and flexible. This provides the motivation to study various dynamic scheduling proposals. In this paper, we evaluate new algorithms for scheduling and resource reclaiming in a dynamic multiprocessor system with fault-tolerant requirements. Resource reclaiming refers to the problem of utilizing resources left unused by a task when its actual computation time is less than its worst case computation time, or when a task is deleted in a fault-tolerant schedule. We also describe the design and implementation of a tool, called Dynamic (Heuristic) scheduling Algorithms for Real-time Multiprocessor systems (DHARMA), to study various dynamic scheduling algorithms, with or without fault-tolerance requirements, and associated resource reclaiming algorithms in a multiprocessor real-time system.

Journal of Systems and Software

DHARMA: A tool for evaluating dynamic scheduling algorithms for real-time multiprocessor 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. © 2000 Academic Press.

Fulltext

Journal of Parallel and Distributed Computing

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

Many time-critical applications require dynamic scheduling with predictable performance. Tasks corresponding to these applications have deadlines to be met despite the presence of faults. In this paper, we propose an algorithm to dynamically schedule arriving real-time tasks with resource and fault-tolerant requirements on to multiprocessor systems. The tasks are assumed to be nonpreemptable and each task has two copies (versions) which are mutually excluded in space, as well as in time in the schedule, to handle permanent processor failures and to obtain better performance, respectively. Our algorithm can tolerate more than one fault at a time, and employs performance improving techniques such as 1) distance concept which decides the relative position of the two copies of a task in the task queue, 2) flexible backup overloading, which introduces a trade-off between degree of fault tolerance and performance, and 3) resource reclaiming, which reclaims resources both from deallocated backups and early completing tasks. We quantify, through simulation studies, the effectiveness of each of these techniques in improving the guarantee ratio, which is defined as the percentage of total tasks, arrived in the system, whose deadlines are met. Also, we compare through simulation studies the performance our algorithm with a best known algorithm for the problem, and show analytically the importance of distance parameter in fault-tolerant dynamic scheduling in multiprocessor real-time systems. © 1998 IEEE.

A fault-tolerant dynamic scheduling algorithm for multiprocessor real-time systems and its analysis

In cloud computing, clients comply a policy of pay-as-you go, i.e., they only pay for the resources they use. So, the processing power of the clouds has to be optimised to reduce the cost at client's side. Using the resources optimally ensures enterprise sustainability of cloud service providers. Workflow is a set of tasks that are interdependent on each other. Scheduling these workflows is one of the most important challenges to optimally utilise the cloud resources and ensure better quality of service (QoS) to clients. Existing works on scheduling in cloud computing mainly focus on scheduling independent tasks rather than (inter)dependent tasks. In this paper, we propose a strategy to schedule dependent tasks called pre-emptive fair scheduling algorithm (PFSA). This is fair scheduling strategy also aims to ensure higher utilisation of virtual machines (VMs) by reducing the idle time and to minimize the number of times a pre-empted task is submitted to the virtual machine. In both cases, this algorithm tries to effectively reduce the overall processing time of dependent tasks at virtual machine, thus minimising the cost involved in processing of tasks. This economically viable decision-based strategy will be helpful for cloud service providers in ensuring sustainability. Copyright © 2014 Inderscience Enterprises Ltd.

International Journal of Business Information Systems

A decision-based pre-emptive fair scheduling strategy to process cloud computing work-flows for sustainable enterprise management

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. © 1997 Academic Press.

Journal	IEEE Transactions on Parallel and Distributed Systems
ISSN	10459219
Open Access	No