טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentAvidar Jacob
SubjectRun-Time Process Scheduling in Hard Real-Time Systems with
Process Dependency Constraints
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Avigdor Gal


Abstract

A key aspect in the design and maintenance of hard real-time systems is the run-time process scheduling. Four semi-dynamic scheduling algorithms that address the problem of process sequencing are presented in this thesis. The algorithms are designed for uniprocessor applications with process dependency constraints, having release times, execution times, and deadlines. The algorithms generate a feasible schedule for the processor using a simple data structure. The feasible schedule ensures that the timing specifications of the processes are observed and that all the precedence constraints among processes are satisfied. The algorithms differ in the level of dynamicity in the operation of the scheduler. All algorithms, together with an existing, static algorithm were tested using an avionics simulated environment of the F-15 aircraft central computer (CC) operational flight program (OFP).  Our empirical results show that of the five algorithms, the best uses two tables as the main data structure for scheduling, such that events rather than processes serve as a primary key.  The main novelty that this research produced is a precept for choosing the most appropriate algorithm for a hard real time system with process dependency constraints. Not only that this research showed a greatly improve for a specific HRT system performance such as F-15 CC OFP, it also presents a set of conditions to decide offline which is the most appropriate scheduling algorithm for the HRT system.

Key words: Hard real-time systems, Scheduling algorithms, Minimizing maximum lateness, Predictability, Rate Monotonic, Dynamic scheduling algorithm, F15 avionics, Operational flight program.