Scheduling Processes with Release Times, Deadlines, Precedence and Exclusion Relations
Umamaheswaran Arumugam and Amit Sahoo
CSE 870 Advanced Software Engineering MiniProject
Computer Science and Engineering
Instructor: Dr. B. Cheng
Michigan State University
Abstract:
In this paper, Xu and Parnas present an algorithm to compute an optimal pre-run-timeschedule for a set of real time process segments with hard deadlines as well as exclusion and precedence relations between them. Since many real time systems are known to contain periodic processes, pre-run-time scheduling can help in reducing run-time resource usage and also help in designing efficient and fail-safe real time systems. This paper is pioneering in the sense that it was the first to deal with the general problem, where not only a real time process as a whole but also the individual segments of the process could be associated with precedence and exclusion relations. As this problem is known to be NP-Hard the authors use a branch-and-bound approach which evaluates a large number of possible schedules to find the optimal solution. This paper was the first to come up with a systematic approach to solve the general pre-run-time scheduling problem and hence it has had a major impact on research in real time scheduling.
Scheduling processes with release times, deadlines, precedence and exclusion relations
(Jia Xu and David Lorge Parnas)
Many hard real time systems e.g. control systems have a large number of processes that are executed repeatedly with a fixed time period. The relationships that exist among the processes and other constraints that might be present are also usually known in advance. Hence the best possible schedule for these processes can be scheduled beforehand. This saves precious resources during run time and also allows the user to know in advance if the deadlines for all the processes can be successfully met. However the problem of finding a feasible schedule for a group of processes with a set of constraint relations among them is NP-hard. In this paper the authors present a branch-and-bound algorithm for this problem that can be successfully used for practical real time applications.
Before describing the algorithm the authors define the various terms and the exact scope of the problem:
The authors divide each process into a set of continuous segments. Each segment has a release time, a fixed computation time and a deadline. All times are measured in units, which is defined as the smallest amount of time for which a segment can be in execution without being preempted. Exclusion, precedence and preemption relations can exist between the segments. The lateness of a segment is calculated as the time at which the segment completes execution subtracted by the deadline for that segment. The lateness of a schedule for a set of processes is the maximum lateness of any segment of any process in the set. A feasible schedule satisfies the deadlines of all processes and an optimal schedule is a feasible schedule with the minimum lateness.
The method proposed by the authors starts with the computation of an initial schedule for the set of processes using the earliest-deadline-first strategy. The initial schedule is the root of the search tree for the optimal solution. Once the schedule has been computed the segment with the maximum lateness, say j, is identified. The only way the lateness of j can be reduced is by making it complete before one of the segments that currently finish execution before it. Hence two sets of segments G1 and G2 are identified such that the lateness of j can be improved by either scheduling it before a segment in G1 or by preempting a segment in G2. Finally the lowerbound for the delay is calculated. This value is the minimum lateness that any schedule generated from the current schedule can have. For each segment k in either G1 or G2 a child node is created. New relations are added to ensure that j precedes k if k is in G1 and j preempts k if k is in G2. At each successor node the earliest-deadline-first schedule, the maximum lateness and the lowerbound for the lateness are calculated. If the lateness of the schedule at the child is less than or equal to the minimum lowerbound at any of the nodes then the optimal solution has been found. If the lateness is equal to the lowerbound at the child then the child is not expanded further because a better schedule cannot be obtained in any successor node. If the minimum lateness among all other schedules is less than the lowerbound at the child then successor nodes are not generated, as the schedule computed at any of those nodes will definitely be non-optimal. If at this stage the optimal solution has not been found, the node with the least lowerbound among all nodes is selected, successor nodes are generated and the process continues.
The running time of the algorithm can be reduced by terminating it if a feasible schedule is found or if the lateness is within some fixed of the optimal solution. The estimated cost of context switches can also be included in the calculations in order to get a more realistic figure for the lateness. The authors implemented their algorithm and found that it performed better than one of the best other algorithms available at that time.
This paper was the first attempt at formalizing the process of computing a pre-run-time schedule for a set of real-time processes with “arbitrary exclusion and precedence relations” [4]. This was a major step forward from contemporary solutions, which only addressed simplified process models and relations that were often unrealistic. The automation of this process greatly reduced the time required and the possibility of errors as compared to computing the schedule manually using ad-hoc methods. Furthermore the authors were able to devise a solution for an NP-Hard problem that is sufficient for use with the type of real time systems in use today. This has been verified by other researches who implemented this algorithm on actual real-time systems. This paper has made a major impact on the field of real time systems in general and on the topic of pre-run-time scheduling in particular. This is borne out by the large number of citations that it has received and by the significant amount of follow-up work in which the authors’ algorithm has been extended to multiprocessors, fault tolerant systems etc.
SCHEDULING FAULT-TOLERANT DISTRIBUTED HARD REAL-TIME TASKS INDEPENDENTLY OF THE REPLICATION STRATEGIES
(Pascal Chevochot and Isabelle Puaut)
Existing scheduling techniques in fault-tolerant distributed real-time systems depend on the type of replication strategy being used. The authors propose to extend the Xu and Parnas’ algorithm [4] for scheduling tasks in a fault-tolerant distributed real-time system with arbitrary replication and error-treatment strategy. The different replication techniques that are discussed in the paper are active, passive and semi-active. Active replication allows the same task to be executed in parallel at different sites or locations and uses a distributed consensus protocol to detect faults. Passive replication allows the state of the executed task to be stored in different sites or locations. Semi-active replication allows decisions to be taken in a single location unlike the active replication.
Tasks are distributed and they can be synchronized using shared resources (for example, semaphores) or precedence relations. A set of ordering relations are defined on the basic units (elementary unit or segments) of each task to get a deterministic replicated execution. The above two requirements must be satisfied by any scheduling algorithm for scheduling fault-tolerant tasks. The authors extend Xu and Parnas’ algorithm [4] to build the scheduler for scheduling fault-tolerant tasks and also to satisfy the requirements mentioned earlier.
The required extensions in Xu and Parnas’ algorithm [4] are: Exclusions between groups of elementary units, distributed execution, and ordering constraints[2]. In a fault-tolerant distributed real-time system, resources may be requested by a group of elementary units belonging to the same task. The original algorithm [4] cannot provide such resource allocation constraints since exclusion relation (EX) is defined for an ordered pair of elementary units (segments) and not on groups of elementary units. So the authors introduce a new relation called EXe. Let I be the set of elementary units in the group belonging to the same group that request a resource. Let euj be an elementary unit not in the group I. The relation I EXe euj means if an elementary unit started executing before euj, then euj can start executing only after all the elementary units in the set I finished executing. The relation EXe affects the way eligible [4] function works. The eligible function finds whether an elementary unit is eligible to execute at a given instant of time. So the eligible function is modified to reflect the introduction of the relation EXe.
Since this fault-tolerant distributed real-time system allows distributed execution, the precedence relation (PC) defined in the original paper [4] has to be extended. The authors define a new relation PCe to allow distributed execution. Let eui and euj be two elementary units. The relation eui PCe euj is similar to PC relation if both the elementary units are assigned to the same site or location. If they are executing in different sites or locations, the start time [4]of euj is greater than or equal to the sum of termination time (completion time [4]) of eui and the delay incurred in validating the precedence constraint. To take the relation PCe into consideration for determining the schedule, the extended algorithm creates n schedules at every node in the search tree instead of just a single schedule, where n is the number of sites or locations present in the fault-tolerant distributed system. Also the eligible[4]function is modified to take the delay incurred in validation of the precedence constraint into account.
As mentioned in the requirements earlier, the scheduling algorithm must take the ordering relations into consideration. An ordering constraint[2] is defined on two sets of elementary units, each set consists of two elementary units that execute on the same site or location. The authors define a set E(REP, gr) where REP is the replication strategy used and gr is the granularity of the fault-tolerant system (called pattern). The set E(REP, gr) represents the set of all groups of elementary units that may form a non-deterministic execution. In order to deal with such constraints, a new relation called IO (identical order [2]) is defined. Let eui, euj, euk and eul be elementary units. The relation (eui, euj) IO (euk, eul) means eui can execute only after euj and euk and execute only after eul or euj can execute only after eui and eul and execute only after euk. The eligible [4] function is modified to take this relation into consideration. Further, when adding eui PCeuj to create a new child node in the search tree being constructed, if (eui, euj) IO (euk, eul) exists, then the relation euk PCeul is also added.
The authors then show an example for constructing the schedule. They show that their approach to scheduling tasks depends very little on the replication technique used in the system.
HYBRID ONLINE/OFFLINE SCHEDULING FOR HARD REAL-TIME SYSTEMS
(Michal Young and Lih-Chyun Shu)
The authors propose the use of a hybrid scheduling technique (combination of online and offline scheduling approach) that improves the utilization of systems in which schedulability guarantees are necessary. This approach makes use of the offline scheduling algorithm for scheduling periodic tasks and the online scheduling algorithm for scheduling sporadic tasks. The authors extend the offline Xu and Parnas’ algorithm [4] for generating cyclic schedules for the periodic tasks. They use the priority based scheduling technique for the online scheduling of the sporadic tasks. The authors claim that the offline algorithm improves the rate-monotonic scheduling by optimally allocating the idle times across different units of the tasks. The rate-monotonic schedule requires that a task should finish its execution within its period.
The authors extend Xu and Parnas’ algorithm [4] to build the cyclic schedules of the periodic tasks. The length of this cyclic schedule is called the major frame size [5]. The major frame size is divided into sub frames of same length, called minor frames[5]. The deadline [4] of every group of tasks scheduled offline (static scheduling) must be less than or equal to the minor frame boundaries. This approach may some time lead to uneven distribution of computation time. The authors propose an automated offline-scheduling algorithm (extension of [4]) to provide an even allocation of computation time by scheduling idle times in each minor frame boundaries.
The authors use [4] to get a schedule for a set of tasks that has predefined release times, deadlines, precedence, and exclusion relations. The minor frame boundaries are marked using tasks whose release time is equal to deadline or computation time is equal to zero. The important constraint on the boundary is that it cannot have a mutual exclusion relation with other critical sections that may cross the frame boundary. The authors guarantee even distribution of computation time by adding dummy tasks at the frame boundaries. The authors use a binary search algorithm to determine the maximum size IMAX of dummy tasks that are to be added such that the original and the dummy tasks can be scheduled for the size of the dummy tasks IMAX but not for IMAX + 1.
The algorithm proposed by the authors first finds the optimal schedule for the given task set using the algorithm in [4]. If the lateness of this schedule is greater than zero, then there exists no valid schedule for the given task set. The algorithm now finds the idle time in the schedule and distributes the idle time (adding dummy tasks) evenly across all minor frames. Now the algorithm in [4] is applied to the original set of tasks and the set of dummy tasks added in the previous step. If the lateness of the resultant schedule is less than or equal to zero or the idle time distributed to the minor frames is one, then the algorithm terminates and returns the resultant schedule. Otherwise, the algorithm adds some more idle time (dummy tasks) to the set of the tasks present in the system in a binary search fashion. The binary search is continued until the algorithm finds an optimal schedule in which the idle times are evenly distributed.
The authors propose some modifications to the search strategy used in [4]. The authors implemented a depth-first search strategy and found that the late latest segment [4] is not a good choice. The schedule that uses the first late segment helps to find a partial valid initial schedule instead of the complete initial schedule. There is no need to construct the complete schedule since rescheduling involves the segments that are scheduled before the segment that is going to be rescheduled. Also this approach finds the impossible scheduling problems faster and the feasible scheduling problems at about the same time as the original algorithm.
The advantages of hybrid scheduling over the pure offline scheduling are: not all tasks are necessary to be scheduled together and troublesome sporadic tasks can be left for online scheduling. The advantages of hybrid scheduling over the pure online scheduling are: it avoids task phasings, eliminates blocking time, reduces semaphore and context switch overhead.
The authors thus make use of the cyclic schedules in periodic tasks to provide a better scheduling of tasks that improves the schedulability guarantees.
Optimal combined task and message scheduling in distributed real-time systems
(Tarek F. Abdelzaher and Kang G. Shin)
In this paper [1], the authors propose a pre-run-time scheduling algorithm for distributed real-time systems. This algorithm is significant because not only does it consider arrival times, deadlines and relations among different real time tasks but it also takes into account the delays and the precedence relations imposed by interprocess messages. As in the Xu and Parnas paper [4] an initial solution is computed using earliest deadline first (EDF) scheduling and then a branch and bound approach is employed to find an optimal solution. As the tasks are now scheduled on multiple processors and message passing is also involved, there are more number of ways to improve the lateness of a schedule and hence the algorithm is more complicated than the original one.
The distributed systems consists of a number of processing nodes (PNs) on which real time processes are executed. Each process is executed on one processor only. Processes are composed of a fixed number of modules[1] that are linked together by precedence and exclusion relations. All processes and hence modules are assumed to be periodic so that pre-run-time scheduling can be used. Interprocess communication is an integral part of distributed systems and hence the authors consider the problems of scheduling messages and that of scheduling processes together. Lateness is defined as the difference of the actual completion time and the deadline of a module and schedule lateness is defined as the maximum lateness of a schedule.