Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Schedulability analysis of tasks with corunner-dependent execution times
Andersson B., Kim H., de Niz D., Klein M., Rajkumar R., Lehoczky J. ACM Transactions on Embedded Computing Systems17 (3):1-29,2018.Type:Article
Date Reviewed: Nov 22 2019

Scarce computer memory and processor core resources create crucial challenges to the real-time execution of concurrent software. How should a multicore processor be efficiently programmed to process concurrent software with different execution speeds and resource requirements?

Andersson et al. present a quasi-polynomial complexity algorithm for scheduling concurrent tasks with dependent uninterruptible execution periods. They propose a model for setting up a test for tasks with competing dependent runtimes, on an exact number of processors. The model consists of the parameters and runtime actions of tasksets and a function for testing a system’s schedule. The parameters include the default progress and the specific corunner requirements of concurrent tasks. A fixed-priority preemptive partitioned scheduler is used to monitor the runtime activities of corunner tasks. The scheduler computes the appropriate segments for each processor. Segments with the highest priorities are randomly selected and executed on target processors at specific time intervals. A function takes the corunner-reliant tasks and processors as input to test whether a system can be scheduled. The model inspects certain irregularities to decide on a schedulable system. The response time of a job cannot be maximized once there are other simultaneously arriving jobs. The priority assignments of jobs to processors are used to modify the execution requirements and progress of concurrent tasks.

The authors define COMP-CORUNNER as “the problem of performing exact schedulability testing,” and then use an NP-complete 3-PARTITION problem to show that the complexity of COMP-CORUNNER is NP-hard. Consequently, they present a new quasi-polynomial time complexity algorithm for testing whether concurrent tasks on systems with finite processors are schedulable. The algorithm is effectively used to process indiscriminately created tasksets using different sizes of processors, tasks, segments per task, degrees of corunner intrusion, and workloads on a system. The execution times utilized to test the schedulability of alternative systems with varying processor and task sizes are within 1000 seconds.

The authors present reliable algorithms and illustrations for computing the lower and upper bounds on the execution times of corunner tasks, and for the theoretical analysis of a safe, schedulable concurrent taskset execution test. The presented test is inexact but sufficient for testing a schedulable system.

Reviewer:  Amos Olagunju Review #: CR146796 (2004-0081)
Bookmark and Share
  Reviewer Selected
Editor Recommended
Featured Reviewer
 
 
Real-Time Systems And Embedded Systems (D.4.7 ... )
 
 
Mathematical Software (G.4 )
 
Would you recommend this review?
yes
no
Other reviews under "Real-Time Systems And Embedded Systems": Date
Real-time software techniques
Heath W., Van Nostrand Reinhold Co., New York, NY, 1991. Type: Book (9780442003050)
Aug 1 1991
Developing safety systems
Pyle I., Prentice-Hall, Inc., Upper Saddle River, NJ, 1991. Type: Book (9780132042987)
Jul 1 1992
Real-time systems with transputers
Zedan H.  Real-time systems with transputers,York, UK,Sep 18-20, 1990,1990. Type: Whole Proceedings
Apr 1 1992
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy