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.
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 meet the specified deadlines.[3] A task can be classified as either a periodic or aperiodic process.[4]
Classifications
editThe 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 (indicating priority). The selected scheduling algorithm determines how priorities are assigned to a particular task. A real-time scheduling algorithm can be classified as static or dynamic. For a static scheduler, task priorities are determined before the system runs. A dynamic scheduler determines task priorities as it runs.[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.[5] A task deadline indicates the time set to complete for each task.
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
editThe 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 require 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.
See also
editReferences
edit- ^ a b Leung, Joseph; Zhao, Hairong (November 2005). Real-Time Scheduling Analysis (PDF) (Technical report). DOT/FAA/AR-05/27.
- ^ Liu, Zhiming; Joseph, Mathai (17 February 2001). "Verification, Refinement and Scheduling of Real-time Programs". Theoretical Computer Science. 253 (1): 119–152. CiteSeerX 10.1.1.50.2896. doi:10.1016/s0304-3975(00)00091-8.
- ^ 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. doi:10.1145/1027794.1027797. S2CID 17526360. Retrieved 4 December 2015.
- ^ a b c d e f Audsley, N.; Burns, A. (1990). Real-Time System Scheduling (PDF) (Technical report). University of York, UK.
- ^ Castanet, R.; Laurençot, P. "Testing real-Time Systems". 15th World Conference on Nondestructive Testing. AIPnD. Retrieved 4 December 2015.