Degree Type

Dissertation

Date of Award

2001

Degree Name

Doctor of Philosophy

Department

Electrical and Computer Engineering

First Advisor

Arun K. Somani

Abstract

The main focus of this thesis is to introduce new techniques that offer trade-offs between schedulability (ability of the system to accept more tasks) and reliability (ability of the system to tolerate more faults) in real-time systems. Different techniques have been introduced for different system models. The mechanisms that are used to offer trade-offs in these techniques differ based on the deadline strictness for each model. In this thesis, three different real-time models (hard, soft, and firm real-time systems) have been studied.;For hard real-time systems, the amount of time redundancy can be varied based on the number and type of faults which can be tolerated. Therefore, we propose two new techniques to accommodate more tasks and/or tolerate more faults effectively in hard real-time systems. In the first technique, called dynamic grouping, the processors are dynamically grouped into logical groups in order to achieve efficient overloading of resources, thereby improving the schedulability and the reliability of the system. In the second technique, called Primary-Backup (PB) overloading , the primary of a task can share/overlap in time with the backup of another task on a processor. Two variations of the adaptive scheme are proposed by varying the adaptation mechanism. The adaptation can be done in a continuous manner which leads to an approach called primary-backup overlap continuous (PB-OVER-CONT), or it can be in a discrete manner which leads to an approach called primary-backup overlap switch (PB-OVER-SWITCH). We propose three closed-loop scheduling algorithms that use feedback from: (i) the deadline miss ratio in the first approach which is called CL-OVER-MISS ; (ii) the task rejection ratio in the second approach which is called CL-OVER-REJ; (iii) both the miss ratio and rejection ratio in the final approach which is called CL-OVER-MISSREJ . These feedbacks are used to efficiently estimate the execution time for the arriving tasks. The efficiency of these techniques have been measured in terms of the percentage of incoming tasks they can schedule and the percentage of scheduling tasks that meet their deadlines. (Abstract shortened by UMI.)

DOI

https://doi.org/10.31274/rtd-180813-11503

Publisher

Digital Repository @ Iowa State University, http://lib.dr.iastate.edu

Copyright Owner

Raed̓ Mohammad S. Al-Omari

Language

en

Proquest ID

AAI3016687

File Format

application/pdf

File Size

164 pages

Share

COinS