The Experts below are selected from a list of 285 Experts worldwide ranked by ideXlab platform
Azer Bestavros - One of the best experts on this subject based on the ideXlab platform.
-
design and implementation of statistical rate monotonic scheduling in kurt linux
Real-Time Systems Symposium, 1999Co-Authors: Alia Atlas, Azer BestavrosAbstract:We present the design and implementation of statistical rate monotonic scheduling (SRMS) on the KURT Linux operating system. We overview the technical issues we had to address to integrate SRMS into KURT Linux and present the API we have developed for scheduling periodic real-time tasks using SRMS.
-
multiplexing vbr traffic flows with guaranteed application level qos using statistical rate monotonic scheduling
International Conference on Computer Communications and Networks, 1999Co-Authors: Alia Atlas, Azer BestavrosAbstract:The data units transmitted by an application may vary in size while being constant in rate, which results in a variable bit rate (VBR) data flow. That data flow requires QoS guarantees. Statistical multiplexing is inadequate, because no guarantees can be made and no firewall property exists between different data flows. In this paper, we present a novel resource management paradigm for the maintenance of application-level QoS for VBR flows. Our paradigm is based on statistical rate monotonic scheduling (SRMS), in which: (1) each application generates its variable-size data units at a fixed rate; (2) the partial delivery of data units is of no value to the application; and (3) the QoS guarantee extended to the application is the probability that an arbitrary data unit will be successfully transmitted through the network to/from the application.
-
statistical rate monotonic scheduling
Real-Time Systems Symposium, 1998Co-Authors: Alia Atlas, Azer BestavrosAbstract:Statistical rate monotonic scheduling (SRMS) is a generalization of the classical RMS results of C. Liu and J. Layland (1973) for periodic tasks with highly variable execution times and statistical QoS requirements. The main tenet of SRMS is that the variability in task resource requirements could be smoothed through aggregation to yield guaranteed QoS. This aggregation is done over time for a given task and across multiple tasks for a given period of time. Similar to RMS, SRMS has two components: a feasibility test and a scheduling algorithm. SRMS feasibility test ensures that it is possible for a given periodic task set to share a given resource without violating any of the statistical QoS constraints imposed on each task in the set. The SRMS scheduling algorithm consists of two parts: a job admission controller and a scheduler. The SRMS scheduler is a simple, preemptive, fixed priority scheduler. The SRMS job admission controller manages the QoS delivered to the various tasks through admit/reject and priority assignment decisions. In particular it ensures the important property of task isolation, whereby tasks do not infringe on each other.
-
the statistical rate monotonic scheduling workbench
1998Co-Authors: Alia Atlas, Azer BestavrosAbstract:Abstract The SRMS Workbench is a software system developed to demonstrate the notion of Statistical QoS employed in SRMS [AtlasBestavros:1998]. The SRMS Workbench includes: (1) the SRMS schedulability analyzer (QoS negotiator), and (2) a SRMS simulator (Basic SRMS + all extensions). These two components are packaged into a Java Applet that can be executed remotely on any Java-capable Internet browser. For comparison, other scheduling algorithms, including RMS [LiuLayland:1973] and SSJAC [AtlasBestavros:1998] are included. Through a simple GUI, the SRMS Workbench allows users to specify a set of periodic tasks, each with (a) its own period, (b) the distributional characteristics of its periodic resource requirements (e.g. Poisson, Pareto, Normal, Exponential, Gamma, etc.), (c) its desired QoS as a lower bound on the percentage of deadlines to be met, and (d) a criticality/importance index indicating the value of the task (relative to other tasks in the task set). Once the task set is specified, the SRMS Workbench allows the user to check for schedulability under SRMS. If the task set is schedulable, the SRMS Workbench generates the appropriate allowance for each task and allows the user to create an animated simulation of the task system, which can be executed and profiled. If the task set is not schedulable, the SRMS Workbench informs the user of that fact and suggests (as part of the QoS negotiation) an alternative set of feasible QoS requirements that reflects the specified criticality/importance index of the tasks in the task set. The SRMS Workbench is available on the Web at http://www.cs.bu.edu/groups/realtime/SRMSworkbench
Javier Orozco - One of the best experts on this subject based on the ideXlab platform.
-
rate monotonic scheduling of real time control systems with the minimum number of priority levels
Euromicro Conference on Real-Time Systems, 1999Co-Authors: Ricardo Cayssials, Javier Orozco, J. Santos, Rodrigo SantosAbstract:When applying the rate monotonic discipline to schedule a set of periodic preemptible real-time tasks, the scheduler may be able to distinguish only a limited number of priority levels. This is common in control applications using low cost embedded controllers. If the number of tasks to be scheduled is larger than the number of distinguishable levels, the set of tasks must be partitioned in a set of priority classes. RM can be used only to arbitrate conflicts between tasks of different classes. In this paper a method to determine the minimum number of priority levels necessary to schedule the set of tasks is formally proved and its complexity analysed. Finally, a systematic method to obtain all the possible partitions with the minimum number of classes, resembling the Quine's method to minimize Boolean functions, is also given.
-
a heuristic approach to the multitask multiprocessor assignmentproblem using the empty slots method and rate monotonic scheduling
Real-time Systems, 1997Co-Authors: J. Santos, Javier Orozco, Edgardo Ferro, Ricardo CayssialsAbstract:A heuristic approach to the problem of assigning a set of preemptible resource-sharing and blockable real-time tasks to be executed in a set of heterogeneous processors communicated through an interprocessor network, is presented. The problem is NP-hard. The empty-slots method is used to test the RM schedulability in each processor. There are placement, time, memory, communication and precedence constraints. A general expression for the modification of hard-precedence deadlines of related tasks executing in the same or in different processors is given. The effects of the Average Processor Utilization Factor and the Network Bandwidth on the number of solutions found are shown and discussed through systematic sets of examples. Also, Success Ratios are obtained and plotted vs. Average Processor Utilization Factors for different Network Bandwidths. Results obtained are compared to those obtained by other methods.
-
802.4 rate monotonic scheduling in hard real-time environments: setting the medium access control parameters
Information Processing Letters, 1997Co-Authors: Javier Orozco, Ricardo Cayssials, J. Santos, Edgardo FerroAbstract:This paper presents an analysis of the rate monotonic scheduling of an 802.4 network operating in a hard real-time environment. The worst-case number of priority inversions is determined. With that, an iterative algorithm is derived to partition the set of nodes in priority classes and to assign the two fundamental medium access control parameters, Target Token Rotation Time and High Priority Token Holding Time, in order to meet the hard real-time constraints.
-
rate monotonic scheduling in hard real time systems
Information Processing Letters, 1993Co-Authors: J. Santos, Javier OrozcoAbstract:Abstract We present a systematic method that improves previous results to determine if a Real-Time Multiple Tasks-Single Processor or any other isomorphic system can be rate monotonic (RM) scheduled, even with a coarse granularity of priority levels.
Shangping Ren - One of the best experts on this subject based on the ideXlab platform.
-
enhanced fixed priority real time scheduling on multi core platforms by exploiting task period relationship
Journal of Systems and Software, 2015Co-Authors: Ming Fan, Qiushi Han, Shuo Liu, Shaolei Ren, Gang Quan, Shangping RenAbstract:HighlightsThe utilization bound of task sets increases as task periods are closer to harmonic.We present two scheduling algorithms for real-time tasks on multi-core platforms.We take the period relationship among tasks into consideration.We formally prove the schedulability of our proposed scheduling algorithms.The proposed algorithms significantly outperform the existing related work. One common approach for multi-core partitioned scheduling problem is to transform this problem into a traditional bin-packing problem, with the utilization of a task being the "size" of the object and the utilization bound of a processing core being the "capacity" of the bin. However, this approach ignores the fact that some implicit relations among tasks may significantly affect the feasibility of the tasks allocated to each local core. In this paper, we study the problem of partitioned scheduling of periodic real-time tasks on multi-core platforms under the rate monotonic scheduling (RMS) policy. We present two effective and efficient partitioned scheduling algorithms, i.e. PSER and HAPS, by exploiting the fact that the utilization bound of a task set increases as task periods are closer to harmonic on a single-core platform. We formally prove the schedulability of our partitioned scheduling algorithms. Our extensive experimental results demonstrate that the proposed algorithms can significantly improve the scheduling performance compared with the existing work.
Gang Quan - One of the best experts on this subject based on the ideXlab platform.
-
enhanced fault tolerant fixed priority scheduling of hard real time tasks on multi core platforms
Embedded and Real-Time Computing Systems and Applications, 2015Co-Authors: Qiushi Han, Tianyi Wang, Gang QuanAbstract:In this paper, we study the problem of partitioned scheduling of periodic real-time tasks with the capability of tolerating transient faults on multi-core platforms under rate monotonic scheduling (RMS) policy. In our approach, we exploit the implicit relations among periods and recovery costs among tasks and develop a novel metric, called "compatibility index", to quantify how "compatible" a task set is when they are allocated on the same core. We theoretically analyze its properties for improving the system schedulability. Based on this metric, we propose two task partitioning schemes to partition hard real-time tasks with fault-tolerance requirements on multi-core platforms. Simulation results demonstrate that our proposed approaches can significantly enhance the performance of existing techniques.
-
enhanced fixed priority real time scheduling on multi core platforms by exploiting task period relationship
Journal of Systems and Software, 2015Co-Authors: Ming Fan, Qiushi Han, Shuo Liu, Shaolei Ren, Gang Quan, Shangping RenAbstract:HighlightsThe utilization bound of task sets increases as task periods are closer to harmonic.We present two scheduling algorithms for real-time tasks on multi-core platforms.We take the period relationship among tasks into consideration.We formally prove the schedulability of our proposed scheduling algorithms.The proposed algorithms significantly outperform the existing related work. One common approach for multi-core partitioned scheduling problem is to transform this problem into a traditional bin-packing problem, with the utilization of a task being the "size" of the object and the utilization bound of a processing core being the "capacity" of the bin. However, this approach ignores the fact that some implicit relations among tasks may significantly affect the feasibility of the tasks allocated to each local core. In this paper, we study the problem of partitioned scheduling of periodic real-time tasks on multi-core platforms under the rate monotonic scheduling (RMS) policy. We present two effective and efficient partitioned scheduling algorithms, i.e. PSER and HAPS, by exploiting the fact that the utilization bound of a task set increases as task periods are closer to harmonic on a single-core platform. We formally prove the schedulability of our partitioned scheduling algorithms. Our extensive experimental results demonstrate that the proposed algorithms can significantly improve the scheduling performance compared with the existing work.
J. Santos - One of the best experts on this subject based on the ideXlab platform.
-
rate monotonic scheduling of real time control systems with the minimum number of priority levels
Euromicro Conference on Real-Time Systems, 1999Co-Authors: Ricardo Cayssials, Javier Orozco, J. Santos, Rodrigo SantosAbstract:When applying the rate monotonic discipline to schedule a set of periodic preemptible real-time tasks, the scheduler may be able to distinguish only a limited number of priority levels. This is common in control applications using low cost embedded controllers. If the number of tasks to be scheduled is larger than the number of distinguishable levels, the set of tasks must be partitioned in a set of priority classes. RM can be used only to arbitrate conflicts between tasks of different classes. In this paper a method to determine the minimum number of priority levels necessary to schedule the set of tasks is formally proved and its complexity analysed. Finally, a systematic method to obtain all the possible partitions with the minimum number of classes, resembling the Quine's method to minimize Boolean functions, is also given.
-
a heuristic approach to the multitask multiprocessor assignmentproblem using the empty slots method and rate monotonic scheduling
Real-time Systems, 1997Co-Authors: J. Santos, Javier Orozco, Edgardo Ferro, Ricardo CayssialsAbstract:A heuristic approach to the problem of assigning a set of preemptible resource-sharing and blockable real-time tasks to be executed in a set of heterogeneous processors communicated through an interprocessor network, is presented. The problem is NP-hard. The empty-slots method is used to test the RM schedulability in each processor. There are placement, time, memory, communication and precedence constraints. A general expression for the modification of hard-precedence deadlines of related tasks executing in the same or in different processors is given. The effects of the Average Processor Utilization Factor and the Network Bandwidth on the number of solutions found are shown and discussed through systematic sets of examples. Also, Success Ratios are obtained and plotted vs. Average Processor Utilization Factors for different Network Bandwidths. Results obtained are compared to those obtained by other methods.
-
802.4 rate monotonic scheduling in hard real-time environments: setting the medium access control parameters
Information Processing Letters, 1997Co-Authors: Javier Orozco, Ricardo Cayssials, J. Santos, Edgardo FerroAbstract:This paper presents an analysis of the rate monotonic scheduling of an 802.4 network operating in a hard real-time environment. The worst-case number of priority inversions is determined. With that, an iterative algorithm is derived to partition the set of nodes in priority classes and to assign the two fundamental medium access control parameters, Target Token Rotation Time and High Priority Token Holding Time, in order to meet the hard real-time constraints.
-
rate monotonic scheduling in hard real time systems
Information Processing Letters, 1993Co-Authors: J. Santos, Javier OrozcoAbstract:Abstract We present a systematic method that improves previous results to determine if a Real-Time Multiple Tasks-Single Processor or any other isomorphic system can be rate monotonic (RM) scheduled, even with a coarse granularity of priority levels.
