Scheduling task with state-dependent deadlines

The real-time scheduling problems described in this thesis are motivated by a new real-time workload model, called the state-dependent deadline model. According to this model, deadlines of real-time tasks and jobs derived from high-level timing requirements are functions of time. In contrast, deadlines of real-time tasks in traditional real-time workload models are constants, independent of time. Traditional models fail to capture time-varying response time requirements of tasks in many real-time systems.; This thesis first considers the case when every job has only one feasible interval: The job is constrained to executed in the interval. In the case when the deadline of every job is given by a known function of time for all times after the job is released, an optimal deadline determination algorithm is developed: The algorithm chooses a deadline from the given deadline function of each job such that processor utilization is minimized and the job will never miss its deadline if the job meets the chosen deadline. When the future values of job deadlines are unknown, it is not possible to make optimal choices of job deadlines. We developed several heuristics to choose deadlines for this case. Simulation results show that these heuristics allow the system to achieve good processor utilization and high probability of meeting its time-varying requirements.; This thesis then considers the general case when a job may have more than one feasible interval. Such a job is constrained to execute from start to completion in one of its feasible intervals. The problem of meeting the timing constraint of such jobs is divided into three problems: feasible interval determination, feasible interval selection, and job scheduling. When the deadline of every job is given as a known time function, there is an optimal feasible interval determination algorithm: The algorithm determines the start times and end times of feasible intervals of every job so that the job will never miss its deadline if the job executes from start to completion in one of its feasible intervals. When the future values of job deadlines are unknown, it is not possible to make optimal determination of feasible intervals. We developed several algorithms to determine probabilistically feasible interval start times and end times for each job so that the probability of a job meeting its timing constraint is no less than a given threshold if it executes from start to completion in one of its feasible intervals. Given the start times and end times of feasible intervals, the problem of selecting a feasible interval for each job in a set of multiple feasible interval jobs so that all jobs complete in time is NP-hard. The optimal branch-and-bound algorithm described here can be used when there is time to compute the schedule. (Abstract shortened by UMI.)...