Browsing by Author "Choi, Seonho"
Now showing 1 - 5 of 5
Results Per Page
Sort Options
Item Designing Dynamic Temporal Controls for Critical Systems(1998-10-15) Choi, Seonho; Agrawala, Ashok K.; Shi, LeyuanTraditional control systems have been designed to exercise control at regularly spaced time instants. When a discrete version of the system dynamics is used, a constant sampling interval is assumed and a new control value is calculated and exercised at each time instant. In this paper, we propose a new control scheme, {\it dynamic temporal control}, in which we not only calculate the control value but also dynamically decide the time instants when the new control computations have to be calculated. Taking a discrete, linear, time-invariant system, and a cost function which reflects a cost for computation of the control values, as an example, we show the feasibility of using this scheme. We implement the dynamic temporal control scheme in a rigid body satellite control example and demonstrate the significant reduction in cost. The scheme proposed here can be implemented using real-time operating system, such as {\em Maruti}, which schedules activities along the time axis. The reduced computations for control permit the use of the same processor for higher level functions resulting in a significant improvement in the performance of the overall system. (Also cross-referenced as UMIACS-TR-97-51)Item Designing Temporal Controls(1998-10-15) Agrawala, Ashok K.; Choi, Seonho; Shi, LeyuanTraditional control systems have been designed to exercise control at regularly spaced time instants. When a discrete version of the system dynamics is used, a constant sampling interval is assumed and a new control value is calculated and exercised at each time instant. In this paper we formulate a new control scheme, {\it temporal control}, in which we not only calculate the control value but also decide the time instants when the new values are to be used. Taking a discrete, linear, time-invariant system, and a cost function which reflects a cost for computation of the control values, as an example, we show the feasibility of using this scheme. We formulate the temporal control scheme as a feedback scheme and, through a numerical example, demonstrate the significant reduction in cost through the use of temporal control. (Also cross-referenced as UMIACS-TR-95-81)Item Dynamic Dispatching of Cyclic Real-Time Tasks with Relative Constraints(1998-10-15) Choi, Seonho; Agrawala, Ashok K.In some hard real-time systems, relative timing constraints may be imposed on task executions, in addition to the release time and deadline constraints. A periodic task may have jitter constraints between the start or finish times of any two consecutive executions. Relative constraints such as separation or relative deadline constraints may be given between start or finish times of tasks (4). One approach is to find a total order on a set of n jobs in a scheduling window, and cyclically use this order at run time to execute the jobs. However, in the presence of the relative constraints, if the job execution times are nondeterminiistic with defined lower and upper bound, it is not always possible to statically assign start times at pre-runtime without sacrificing the schedulability(4). We develop a technique called dynamic cyclic dispatching to enforce relative constraints along with release time and deadline constraints. An ordered set of N jobs is assumed to be given within a scheduling window and this schedule (ordering) is cyclically repeated at runtime. An off-line algorithm is presented to check the schedulability of the job set and to obtain parametric lower and upper bounds on the start times of jobs, if the job set is schedulable. Then, these parametric bounds are evaluated at runtime to obtain a valid time intervals during which jobs can be started. The complexity of this off-line component is shown to be O(n2N3) where n is the number of jobs in a scheduling window that have relative constraints with jobs in the next scheduling window. An online algorithm can evaluate these bounds in O(N3+n5) computation time. Unlike static approached which assign fixed start times to jobs in the scheduling window, our approach not only allows us to flexibly manage the slack times with the schedulability of a task set not affected, but also yields a guaranteed schedulability in the sense that, if other dispatching mechanism can schedule the job sequences satisfying all given constraints, then our mechanism can also schedule them. (Also cross-referenced as UMIACS-TR-97-300Item Dynamic Time-Based Scheduling for Hard Real-Time Systems(1998-10-15) Choi, SeonhoIn traditional time-based scheduling schemes for real-time systems time line is explicitly managed to obtain a feasible schedule that satisfies all timing constraints. In the schedule the task attributes, such as task start time, are statically decided off-line and used without modification throughout system operation time. However, for dynamic real-time systems, in which new tasks may arrive during the operation, or tasks may have relative constraints based on information only known at run-time, such static schemes may lack the ability to accommodate dynamic changes. Clearly a solution of dynamic real-time scheduling has to reflect the knowledge about tasks and their execution characteristics. In this dissertation we present a {\em dynamic time-based scheduling scheme} and show its applicability for three problem domains. In dynamic time-based scheduling scheme attributes of task instances in the schedule may be represented as functions parameterized with information available at task dispatching time. These functions are called {\em attribute functions} and may denote any attribute of a task instance, such as lower and upper bound of its start time, its execution mode, etc. Flexible resource management becomes possible in this scheme by utilizing the freedom provided by the scheme. First, we study the problem of dynamic dispatching of tasks, reflecting relative timing constraints among tasks. The relative constraints may be defined across the boundary of two consecutive scheduling windows as well as within one scheduling window. We present the solution approach with which we are not only able to test the schedulability of a task set, but also able to obtain maximum slack time by postponing static task executions at run-time. Second, new framework is formulated for designing real-time control systems in which the assumption of fixed sampling period is relaxed. That is, sampling time instants are found adaptively based on physical system state such that a new cost function value is minimized which incorporates computational costs. We show, for linear time-invariant control systems, that the computation requirement can be reduced while maintaining the quality of control. Third, acceptance tests are found for dynamically arriving aperiodic tasks, and for dynamically arriving sporadic tasks, respectively, under the assumption that an Earliest Deadline First scheduling policy is used for resolving resource contention between dynamic and static(dynamic) tasks. Dynamic time-based scheduling scheme can be applied as solution approaches for these problems as will be shown in this dissertation, and its effectiveness will be demonstrated. Also cross-referenced as UMIACS-TR-97-81Item Scheduling Aperiodic and Sporadic Tasks in Hard Real-Time Systems(1998-10-15) Choi, Seonho; Agrawala, Ashok K.The stringent timing constraints as well as the functional correctness are essential requirements of hard real-time systems. In such systems, scheduling plays a very important role in satisfying these constraints. The priority based scheduling schemes have been used commonly due to the simplicity of the scheduling algorithm. However, in the presence of task interdependencies and complex timing constraints, such scheduling schemes may not be appropriate due to the lack of an efficient mechanism to schedule them and to carry out the schedulability analysis. In contrast, the time based scheduling scheme may be used to schedule a set of tasks with greater degree of schedulability achieved at a cost of higher complexity of off-line scheduling. One of the drawbacks of currently available scheduling schemes, however, is known to be their inflexibility in dynamic environments where dynamic processes exist, such as aperiodic and sporadic processes. We develop and analyze scheduling schemes which efficiently provide the flexibility required in real-time systems for scheduling processes arriving dynamically. This enables static hard periodic processes and dynamic processes(aperiodic or sporadic) to be jointly scheduled. (Also cross-referenced as UMIACS-TR-97-44)