Scheduling analysis real-time systems

The term scheduling analysis in real-time computing includes the analysis and testing of the scheduler system and the algorithms used in real-time applications. In computer science, real-time scheduling Analysis is the evaluation, testing and verification of the scheduling system and the algorithms used in real-time operations. For critical operations, a real-time system must be tested and verified for performance. In computer science, testing and verification is also known as model checking.

A real-time scheduling System is composed of the scheduler, clock and the processing hardware elements. In a real-time system, a process or task has schedulability; tasks are accepted by a real-time system and completed as specified by the task deadline depending on the characteristic of the scheduling algorithm.[1] Modeling and evaluation of a real-time scheduling system concern is on the analysis of the algorithm capability to meet a process deadline. A deadline is defined as the time required for a task to be processed.

For example, in a real-time scheduling algorithm a deadline could be set to five nano-seconds. In a critical operation the task must be processed in the time specified by the deadline (i.e. five nano-seconds). A task in a real-time system must be completed “neither too early nor too late;..”.[2] A system is said to be unschedulable when tasks can not met the specified deadlines.[3] A task can be classified as either a periodic or aperiodic process.[4]

Other Uses

Marketing Analytics is another application for real-time technology.[5] For example the use of real-time analytics can be implemented by an online retailer interested in displaying ads to consumers at specific intervals. In real-time, large volumes of consumer data can be analyzed to improve the marketing strategy.

Classifications

The criteria of a real-time can be classified as hard, firm or soft. The scheduler set the algorithms for executing tasks according to a specified order.[4] There are multiple mathematical models to represent a scheduling System, most implementations of real-time scheduling algorithm are modeled for the implementation of uniprocessors or multiprocessors configurations. The more challenging scheduling algorithm is found in multiprocessors, it is not always feasible to implement a uniprocessor scheduling algorithm in a multiprocessor.[4] The algorithms used in scheduling analysis “can be classified as pre-emptive or non-pre-emptive".[1]

A scheduling algorithm defines how tasks are processed by the scheduling system. In general terms, in the algorithm for a real-time scheduling system, each task is assigned a description, deadline and an identifier. The scheduler traces an accepted task according to a scheduling algorithm.

A real-time scheduling algorithm can also be classified as static or dynamic.[4] Tasks are accepted by the hardware elements in a real-time scheduling system from the computing environment and processed in real-time. An output signal indicates the processing status.[6] A task deadline indicates the time set to complete for each task. A task deadline for a static scheduler is predetermined offline. A different alternative is to schedule a task when the system is running; this process is known as Dynamic scheduling.[4]

It is not always possible to meet the required deadline; hence further verification of the scheduling algorithm must be conducted. Two different models can be implemented using a dynamic scheduling algorithm; a task deadline can be assigned according to the task priority (earliest deadline) or a completion time for each task is assigned by subtracting the processing time from the deadline (least laxity).[4] Deadlines and the required task execution time must be understood in advance to ensure the effective use of the processing elements execution times.

Testing and verification

The performance verification and execution of a real-time scheduling algorithm is performed by the analysis of the algorithm execution times. Verification for the performance of a real-time Scheduler will require testing the scheduling algorithm under different test scenarios including the worst-case execution time. These testing scenarios include worst case and unfavorable cases to assess the algorithm performance. The time calculations required for the analysis of scheduling systems requires evaluating the algorithm at the code level.[4]

Different methods can be applied to testing a scheduling System in a real-time system. Some methods include: input/output verifications and code analysis. One method is by testing each input condition and performing observations of the outputs. Depending on the number of inputs this approach could result in a lot of effort. Another faster and more economical method is a risk based approach where representative critical inputs are selected for testing. This method is more economical but could result in less than optimal conclusions over the validity of the system if the incorrect approach is used. Retesting requirements after changes to the scheduling System are considered in a case by case basis.

Testing and verification of real-time systems should not be limited to input/output and codes verifications but are performed also in running applications using intrusive or non-intrusive methods.

References

  1. 1 2 Leung, Joseph; Zhao, Hairong (November 2005). Real-Time Scheduling Analysis (PDF) (Technical report). DOT/FAA/AR-05/27.
  2. ↑ Liu, Zhiming; Joseph, Mathai (17 February 2001). "Verification, Refinement and Scheduling of Real-time Programs" (PDF). Theoretical Computer Science 253 (1): 119–152. Retrieved 4 December 2015.
  3. ↑ Sorin, Manolache,; Petru, Eles; Zebo, Peng (November 2004). "Schedulability Analysis of Applications with Stochastic Task Execution Times" (PDF). ACM Transactions on Embedded Computing Systems 3 (4): 706–735. Retrieved 4 December 2015.
  4. 1 2 3 4 5 6 7 Audsley, N.; Burns, A. (1990). Real-Time System Scheduling (PDF) (Technical report). University of York, UK.
  5. ↑ Derrick, Harris. "Big Data in real time is not fantasy". Gigaom. Retrieved 4 December 2015.
  6. ↑ Castanet, R.; Laurençot, P. "Testing real-Time Systems". 15th World Conference on Nondestructive Testing. AIPnD. Retrieved 4 December 2015.

External links

This article is issued from Wikipedia - version of the Sunday, April 17, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.