# Patent

## Title
Uniprocessor schedulability testing for non-preemptive task sets

## Abstract

A method of determining schedulability of tasks for uniprocessor execution includes defining a well-formed, non-preemptive task set having a plurality of tasks, each task having at least one subtask. A determination of whether the task set is schedulable is made, such that a near-optimal amount of temporal resources required to execute the task set is estimated. Further, a method of determining schedulability of a subtask for uniprocessor execution includes defining a well-formed, non-preemptive task set having a plurality of tasks, each task having at least one subtask. A determination of whether a subtask in the task set is schedulable at a specific time is made in polynomial time. Systems for implementing such methods are also provided.

## Background
CROSS-REFERENCE TO RELATED APPLICATION
This application claims priority to and the benefit of U.S. Provisional Patent Application No. 61/640,132, filed Apr. 30, 2012, and entitled “Uniprocessor Schedulability Test and Scheduler for Task Sets with Well-Formed Precedence Relations, Temporal Deadlines, and Wait Constraints,” the entirety of which is hereby incorporated herein by reference.


STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
This invention was made with government support under Grant No. DGE1122374 awarded by the National Science Foundation. The government has certain rights in the invention.


TECHNICAL FIELD
This description relates generally to real-time processor scheduling and, in particular, to methods and systems for testing schedulability of non-premptive task sets with hard scheduling deadlines.
BACKGROUND INFORMATION
Increasingly in real-time systems, computer processors must handle the self-suspension of tasks and determine the feasibility of these task sets. Self-suspensions can result both due to hardware and software architecture. At the hardware level, the addition of multi-core processors, dedicated cards and various input/output (I/O) devices, such as external memory drives, can necessitate task self-suspensions. Furthermore, the software that utilizes these hardware systems can employ synchronization points and other algorithmic techniques that also result in self-suspensions. Thus, a schedulability test that does not significantly overestimate the temporal resources needed to execute self-suspending task sets would be of benefit to these modern computing systems.
Unfortunately the problem is NP-Hard, as can be shown through an analysis of the interaction of self-suspensions and task deadlines. In practice, the relaxation of a deadline in a self-suspending task set may result in temporal infeasibility. Many uniprocessor, priority-based scheduling algorithms introduce scheduling anomalies since they do not account for this interaction. The most straightforward, correct approach for testing the schedulability of these task sets is to treat self-suspensions as task costs; however, this can result in significant under-utilization of the processor if the duration of self-suspensions is large relative to task costs.
A number of different approaches have been proposed to test the schedulability of self-suspending task sets. The dominant strategy is to upperbound the duration of self-suspensions that needs to be treated as task cost. One approach, testing preemptive task sets with multiple self-suspensions per task under Global Earliest Deadline First (GEDF) on multiple processor systems, has shown significant improvement over the prior art. An earlier test computes the maximum utilization factor for tasks with single self-suspensions scheduled under Earliest Deadline First (EDF) for uniprocessor systems. The test works by analyzing priorities to determine the number of tasks that may be executed during a self-suspension. Other approaches test schedulability by analyzing the worst case response time of tasks due to external blocking events.
The design of scheduling policies for self-suspending task sets also remains a challenge. While EDF has desirable properties for many real-time uniprocessor scheduling problems, certain anomalies arise when scheduling task sets with both self-suspensions and hard deadlines. In some instances, it is possible to schedule a task set under EDF with tight deadlines, while the same task set with looser deadlines fails. Finding an anomaly-free scheduling priority for self-suspending task sets remains an open problem. Accordingly, a schedulability test that determines the feasibility of hard, non-preemptive, self-suspending task sets with multiple self-suspensions for each task is needed.
SUMMARY
The typical assembly task has a number of features that are not addressed together in the prior art for real-time processor scheduling. Assembly tasks are related through precedence constraints (e.g., one task must be completed before another can be started), temporal deadlines (e.g., certain tasks must be completed within a given time window), and wait constraints (e.g., one task must be started a minimum time after a previous task ends). In this document we present a sufficient schedulability criteria computed in polynomial time for task sets that are “well-formed,” meaning tasks are related through precedence, deadline and wait constraints according to well-defined composability rules. Empirically, we show that this schedulability test may be computed in seconds for factory-relevant problems, and that the criteria is tight and informative for real-world structured problems. We also provide a scheduling strategy for task sets that meet this schedulability criteria.
In one aspect, in a computer system with a memory storing computer-executable instructions, a method of determining the schedulability of tasks for uniprocessor execution includes executing the instructions by a processing unit such that the computer defines a well-formed, non-preemptive task set and determines whether the task set is schedulable. The task set includes a plurality of tasks, with each task having at least one subtask. The schedulability determination includes estimating a near-optimal amount of temporal resources required to execute the task set.
In one embodiment, at least two subtasks in the task set are related by precedence, a wait constraint, and/or a deadline constraint. At least one of the tasks may have an intra-task deadline constraint. The intra-task deadline constraint may include a hard constraint.
In another embodiment, one of the tasks has a different number of subtasks than another one of the tasks. The number of subtasks in each task may be independent of the number of subtasks in each of the other tasks in the task set. In a further embodiment, the determination of whether the task set is schedulable is made in polynomial time.
In some implementations, the computer performs the step of determining in polynomial time whether a subtask in the task set is schedulable at a specific time. Upon determining that the task set is schedulable, a uniprocessor may be configured to perform the tasks in the task set according to a schedule.
In another aspect, a system for determining the schedulability of tasks for uniprocessor execution includes a memory and a processing unit for executing instructions stored on the memory. Upon executing the instructions, the processing unit defines a well-formed, non-preemptive task set having a plurality of tasks, each task having at least one subtask. The processing unit further determines whether the task set is schedulable by, for example, estimating a near-optimal amount of temporal resources required to execute the task set.
In one embodiment, at least two subtasks in the task set are related by precedence, a wait constraint, and/or a deadline constraint. At least one of the tasks may have an intra-task deadline constraint. The intra-task deadline constraint may include a hard constraint.
In another embodiment, one of the tasks has a different number of subtasks than another one of the tasks. The number of subtasks in each task may be independent of the number of subtasks in each of the other tasks in the task set. In a further embodiment, the processing unit is configured to determine whether the task set is schedulable in polynomial time.
In some implementations, the execution of the instructions further causes the processing unit to determine in polynomial time whether a subtask in the task set is schedulable at a specific time. The processing unit may further configure, upon a determination that the task set is schedulable, a uniprocessor to perform the tasks in the task set according to a schedule.
In a further aspect, in a computer system with a memory storing computer-executable instructions, a method of determining schedulability of a subtask for uniprocessor execution includes executing the instructions by a processing unit such that the computer defines a well-formed, non-preemptive task set and determines in polynomial time whether a subtask in the task set is schedulable at a specific time. The task set includes a plurality of tasks, with each task having at least one subtask.
In one embodiment, at least two subtasks in the task set are related by precedence, a wait constraint, and/or a deadline constraint. At least one of the tasks may have an intra-task deadline constraint.
In another embodiment, the determination of whether the subtask in the task set is schedulable depends on an intra-task deadline constraint of at least one other task in the task set.
In a further implementation, the determination of whether the subtask in the task set is schedulable involves determining whether a first subtask group in the task set can be nested within a slack interval of a second subtask group in the task set. Each subtask within a subtask group may share a common deadline constraint.
In yet another embodiment, the computer determines whether the task set is schedulable based at least in part on the determination of whether the subtask in the task set is schedulable. Upon determining that the task set is schedulable, a uniprocessor may be configured to perform the tasks in the task set according to a schedule.
In yet another aspect, a system for determining the schedulability of a subtask for uniprocessor execution includes a memory and a processing unit for executing instructions stored on the memory. Execution of the instructions causes the processing unit to define a well-formed, non-preemptive task set and determine in polynomial time whether a subtask in the task set is schedulable at a specific time. The task set includes a plurality of tasks, with each task having at least one subtask.
In one embodiment, at least two subtasks in the task set are related by precedence, a wait constraint, and/or a deadline constraint. At least one of the tasks may have an intra-task deadline constraint.
In another embodiment, the processing unit is configured to determine whether the subtask in the task set is schedulable based on an intra-task deadline constraint of at least one other task in the task set.
In a further implementation, in determining whether the subtask in the task set is schedulable, the processing is configured to determine whether a first subtask group in the task set can be nested within a slack interval of a second subtask group in the task set. Each subtask within a subtask group may share a common deadline constraint.
In yet another embodiment, execution of the instructions further causes the processing unit to determine whether the task set is schedulable based at least in part on the determination of whether the subtask in the task set is schedulable. Upon a determination that the task set is schedulable, a uniprocessor may be configured to perform the tasks in the task set according to a schedule.
Other aspects and advantages of the invention will become apparent from the following drawings, detailed description, and claims, all of which illustrate the principles of the invention, by way of example only.



BRIEF DESCRIPTION OF THE DRAWINGS
A more complete appreciation of the invention and many attendant advantages thereof will be readily obtained as the same becomes better understood by reference to the following detailed description when considered in connection with the accompanying drawings. In the drawings, like reference characters generally refer to the same parts throughout the different views. Further, the drawings are not necessarily to scale, emphasis instead generally being placed upon illustrating the principles of the invention.
FIG. 1 is a diagram illustrating a task scheduler system interacting with a task performer according to an embodiment of the invention.
FIG. 2 is a diagram illustrating a serial task combinator according to an embodiment of the invention.
FIG. 3 is a diagram illustrating a parallel task combinator according to an embodiment of the invention.
FIG. 4 is a diagram illustrating a task-task deadline combinator according to an embodiment of the invention.
FIG. 5 is a diagram illustrating an epoch-task deadline combinator according to an embodiment of the invention.
FIG. 6 is a diagram illustrating nested task-task deadline constraints according to an embodiment of the invention.
FIG. 7 is a diagram illustrating an exemplary well-formed task network according to an embodiment of the invention.
FIG. 8 is exemplary pseudocode for a schedulability test according to an embodiment of the invention.
FIG. 9 is exemplary pseudocode for constructing a task superset according to an embodiment of the invention.
FIG. 10 is a graph illustrating empirical results for the tightness of a schedulability test according to an embodiment of the invention.
FIG. 11 is exemplary pseudocode for a scheduler algorithm according to an embodiment of the invention.
FIG. 12 is exemplary pseudocode for a subtask schedulability test according to an embodiment of the invention.
FIG. 13 is a graph illustrating the performance of a task scheduler according to an embodiment of the invention.



DETAILED DESCRIPTION
In this description, we present several contributions. First, we provide a solution to the open problem of determining the feasibility of hard, periodic, non-preemptive, self-suspending task sets with any number of self-suspensions in each task. We test the schedulability of these task sets by providing an upperbound for the amount of self-suspension time that needs to be treated as task cost. Our test is polynomial in time and, in contrast to prior art, generalizes to non-preemptive task sets with more than one self-suspension per task.
Second, we extend our schedulability test to also handle task sets with deadlines constraining the upperbound temporal difference between the start and finish of two subtasks within the same task. Third, we introduce a new scheduling policy to accompany the schedulability test. We specifically designed this scheduling policy to restrict the behavior of a self-suspending task set so as to provide an analytical basis for an informative schedulability test.
Further, we present a near-optimal method for scheduling under a jth Subtask First scheduling priority. A polynomial-time, online consistency test, call the “Russian Dolls test,” is used to determine whether we can “nest” a set of tasks within the slack of another set of tasks. Our scheduling algorithm is not optimal in all cases; in general the problem of sequencing according to both upperbound and lowerbound temporal constraints requires an idling scheduling policy and is known to be NP-complete. However, we show through empirical evaluation that schedules resulting from our algorithm are within a few percent of the best possible schedule.
Recent advances in the accuracy of industrial robots have opened the way for the use of these systems in aerospace manufacturing. Near-term applications include robotic drilling for aircraft assembly and automated composite fiber placement. Robotic solutions provide significant flexibility in operations compared to the current state-of-the-art large gantry, “monument” style automated solutions. The key challenge in harnessing the full capability of these robotic systems is to coordinate the work sharing and scheduling among multiple robots. This requires a carefully choreographed dance to achieve high productivity despite inevitable disturbances due to robot servicing, people working in the same space, and other unanticipated delays in the build process.
We have developed a capability for flexible work sequencing and scheduling (WSS) that is capable of automatically rescheduling a robot's action sequence to adapt to changes in the nominal workplan, while guaranteeing hard scheduling deadlines are met. Previous state-of-the-art scheduling solutions (e.g. disjunctive temporal problem solvers such as TSAT++) take tens of minutes to hours to compute a feasible schedule for a factory-relevant problem. We have developed an alternative, computationally efficient approach for performing this scheduling. In one embodiment, we model robotic and human workers in the system as processors within a computer. The build piece (e.g., an airplane fuselage) is modeled as a shared memory resource that the processors (human and robotic workers) must coordinate to access. The invention disclosed in this document relates, in various embodiments, to the efficient scheduling of a uniprocessor (single robot).
Referring to FIG. 1, embodiments of the invention may be implemented on a computing device in the form of a computer 100 including a processing unit 102 and a memory 104, and a system bus that couples various system components including the memory 104 to the processing unit 102. The computer 100 may be configured to perform the processes described herein to determine the schedulability of a task set and produce a scheduled task set 110. The task set 110 may be used to program a robot 120 or other uniprocessor to perform the tasks according to the scheduled task set 110 on one or more resources 130.
The techniques described herein can further be implemented in digital electronic circuitry, or in computer hardware, firmware, software, or in combinations of them. The techniques can be implemented as a computer program product, i.e., a computer program tangibly embodied in non-transitory medium such as a machine-readable storage device, or to control the operation of a data processing apparatus, e.g., a programmable processor, a computer, or multiple computers. A computer program can be written in any form of programming language, including compiled or interpreted languages, and it can be deployed in any form, including as a stand-alone program or as a module, component, subroutine, or other unit suitable for use in a computing environment. A computer program can be deployed to be executed on one computer or on multiple computers at one site or distributed across multiple sites and interconnected by a communication network.
Method steps of the techniques described herein can be performed by one or more programmable processors executing a computer program to perform functions of the invention by operating on input data and generating output. Method steps can also be performed by, and apparatus of the invention can be implemented as, special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application-specific integrated circuit). Modules can refer to portions of the computer program and/or the processor/special circuitry that implements that functionality.
Processors suitable for the execution of a computer program include, by way of example, both general and special purpose microprocessors, and any one or more processors of any kind of digital computer. Generally, a processor will receive instructions and data from a read-only memory or a random access memory or both. The essential elements of a computer are a processor for executing instructions and one or more memory devices for storing instructions and data. Generally, a computer will also include, or be operatively coupled to receive data from or transfer data to, or both, one or more mass storage devices for storing data, e.g., magnetic, magneto-optical disks, or optical disks. Information carriers suitable for embodying computer program instructions and data include all forms of non-volatile memory, including by way of example semiconductor memory devices, e.g., EPROM, EEPROM, and flash memory devices; magnetic disks, e.g., internal hard disks or removable disks; magneto-optical disks; and CD-ROM and DVD-ROM disks. The processor and the memory can be supplemented by, or incorporated in special purpose logic circuitry.
To provide for interaction with a user, the techniques described herein can be implemented on a computer, mobile device, smartphone, tablet, and the like, having a display device, e.g., a CRT (cathode ray tube) or LCD (liquid crystal display) monitor, for displaying information to the user and an input device, e.g., a keyboard, touchscreen, touchpad, mouse or trackball, by which the user can provide input to the computer or other device (e.g., interact with a user interface element, for example, by clicking a button on such a pointing device). Other kinds of devices can be used to provide for interaction with a user as well; for example, feedback provided to the user can be any form of sensory feedback, e.g., visual feedback, auditory feedback, or tactile feedback; and input from the user can be received in any form, including acoustic, speech, or tactile input.
The techniques described herein can be implemented in a distributed computing system that includes a back-end component, e.g., as a data server, and/or a middleware component, e.g., an application server, and/or a front-end component, e.g., a client computer having a graphical user interface and/or a Web browser through which a user can interact with an implementation of the invention, or any combination of such back-end, middleware, or front-end components. The components of the system can be interconnected by any form or medium of digital data communication, e.g., a communication network. Examples of communication networks include a local area network (“LAN”) and a wide area network (“WAN”), e.g., the Internet, and include both wired and wireless networks.
The computing system can include clients and servers. A client and server are generally remote from each other and typically interact over a communication network. The relationship of client and server arises by virtue of computer programs running on the respective computers and having a client-server relationship to each other.
It should also be noted that embodiments of the present invention may be provided as one or more computer-readable programs embodied on or in one or more articles of manufacture. The article of manufacture may be any suitable hardware apparatus, such as, for example, a floppy disk, a hard disk, a CD-ROM, a CD-RW, a CD-R, a DVD-ROM, a DVD-RW, a DVD-R, a flash memory card, a PROM, a RAM, a ROM, or a magnetic tape. In general, the computer-readable programs may be implemented in any programming language. The software programs may be further translated into machine language or virtual machine instructions and stored in a program file in that form. The program file may then be stored on or in one or more of the articles of manufacture.
1. Augmented Task Model
The basic model for self-suspending task sets is shown in Equation 1.

τi:(φi,(Ci1,Ei1,Ci2,Ei2, . . . , Eimi−1,Cimi),Ti,Di)  (1)

In this model, there is a task set, τ, where all tasks, τiετ must be executed by a uniprocessor. For each task, there are mi subtasks with mi−1 self-suspension intervals. Cij is the worst-case duration of the jth subtask of τi, and Eij is the worst-case duration of the jth self-suspension interval of τi.

Subtasks within a task are dependent, meaning that a subtask τij+1 must start after the finish times of the subtask τij and the self-suspension Eij. Ti and Di are the period and deadline of τi, respectively, where Di≦Ti. Lastly, a phase offset delays the release of a task, τi, by the duration, φi, after the start of a new period.
The self-suspending task model shown in Equation 1 provides a solid basis for describing many real-world processor scheduling problems of interest. In this work, we augment the traditional model to provide additional expressiveness, by incorporating deadline constraints that upperbound the temporal difference between the start and finish of two subtasks within a task. We call these deadline constraints intra-task deadlines. We define an intra-task deadline as shown in Equation 2.

D(i,a),(i,b):(fia−sib≦d(i,a),(i,b))  (2)

where fib is the finish time of subtask τib, sij is the start time of subtask τij, and d(i,a),(i,b) is the upperbound temporal constraint between the start and finish times of these two subtasks, such that b>a. These types of constraints are commonly included in artificial intelligence and operations research scheduling models.

In another embodiment, a well-formed task model is defined as a task set, τ, that is composed of tasks τi, iε{1, . . . n}, where each τi has an associated execution time, or cost, ci. The model is well-formed in that tasks are related through upperbound deadlines and lowerbound wait constraints according to a set of primitive combinators defined below. The resulting task model has a well-defined network structure that we leverage to create an empirically tight scheduling policy.
A well-formed network consists of an epoch and terminus task each with zero cost, and a set of intermediate tasks each with non-zero cost. The epoch serves as a trigger for the release of the network. An upperbound temporal constraint on the makespan, m, may be placed on the execution time from the epoch to terminus. Tasks may also be related through upper and lowerbound temporal constraints using the following set of four primitive combinators.
Serial Task Combinator: We define the serial task combinator as the ordering in series of two tasks, τi and τj, into a super task, τk, where the start of task τj must follow the end of τi after minimum wait time, θi,j. Similarly, two super tasks, or a task and a super task may be combined with the serial task combinator. FIG. 2 shows an illustration of the serial task combinator.
Parallel Task Combinator: We define the parallel task combinator as the parallelization of a set of tasks, {τi, . . . , τj}, into a super task, τk, where each task in {τi, . . . , τj} begins a minimum wait time, {θ{k,i}, . . . , θ{k,j}}, respectively, after the start of τk. Similarly, each task ends a minimum wait time {θ{i,k}, . . . , θ{j,k}} before the end of τk. Tasks and super tasks may be combined with the parallel task combinator. FIG. 3 shows an illustration of a parallel task combinator.
Task-Task Deadline Combinator: We define the task-task deadline combinator, as a constraint, di, on the upperbound of the allowable duration between the start and finish time of task or super task, τi. FIG. 4 shows the graphical illustration of task-task deadline combination. When a task, τi, is scheduled with an associated task-task deadline, di, that deadline constraint is considered active while si≦t≦fi where si is the start time of τi, t is the current time, and fi is the finish time of τi. In the case that τi is not a supertask, the deadline constraint is trivial because non-preemptable tasks execute with a fixed duration, c.
Epoch-Task Deadline Combinator: We define the epoch-task deadline combinator as a constraint, d{k,i}, on the upperbound of the duration between the start time of a supertask, τk, formed by the Parallel Task Combinator, and finish time of a task, τi. FIG. 5 shows a graphical description of epoch-task deadline combination. When a super task, τk, is scheduled and has an associated epoch-task deadline constraint, d{k,i}, from the start of τk to the end of τi, as shown in FIG. 5, that epoch-task deadline is considered active while sk≦t≦fi where sk is the start time of τk, t is the current time, and fi is the finish time of τi. The task-task and epoch-task deadlines are similar to latency constraints, where latency is defined as a limit on the upperbound duration relating the start of two tasks. The key difference is that the task-task and epoch-task deadline combinators, instead, limit the upperbound duration between the start of one task and the end of another task.
As a consequence of combination, one task-task deadline constraint may be nested within another task-task deadline constraint as shown in FIG. 6. If a task is involved in one of a set of nested task-task deadlines, then the task is said to be involved in a complex deadline constraint. We define {τC DC} as the set of tasks with complex deadline constraints. FIG. 6 shows two nested task-task deadlines that form complex deadline constraints, where {τC DC}={τi, τj}. Epoch-task deadlines may also be nested to form complex deadline constraints, where each task involved is likewise in the set {τC DC}. To support efficient inferences on the task network structure, we add a restriction on the use of complex deadline constraints as follows: an epoch-task and a task-task deadline cannot be combined to create a complex deadline constraint.
FIG. 7 shows an example of a well-formed task network constructed using the four primitive combinators. This network is composed of eleven tasks: nine tasks related through serial and parallel combination and one epoch and terminus task; the network has one epoch-task deadline and two task-task deadlines. The two task-task deadlines are complex deadline constraints, because one is nested within the other.
We can represent many real-world constraints using the well-formed task model. For example, serial combination may be applied to encode precedence constraints or denote minimum wait times between tasks. Wait constraints arise, for example, in robotic painting where time is necessary for the paint to cure, or in air traffic scheduling, where landing aircraft must be spaced by a minimum separation time.
The parallel combination encodes choice in the valid sequencing. Parallel and serial combinators together form a partially ordered plan. Task-task and epoch-task deadlines also arise naturally in factory operations and airplane scheduling. For example, a factory supervisor may specify that a sequence of tasks should be accomplished in the first shift, or should be grouped together to be executed within a specified window. Deadlines may also encode the amount of time an aircraft can remain in a holding pattern based on fuel considerations.
2. Terminology
In this section we introduce new terminology to help describe our schedulability test and the execution behavior of self-suspending tasks, which in turn will help us intuitively describe the various components of our schedulability test.
Definition 1: A free subtask, τijετfree, is a subtask that does not share a deadline constraint with τij−1. In other words, a subtask τij is free iff for any deadline D(i,a)(i,b) associated with that task, (j≦a)(b<j). We define τi1 as free since there does not exist a preceding subtask.
Definition 2: An embedded subtask, τij+1ετembedded, is a subtask shares a deadline constraint with τij (i.e., τij+1∉τfree). τfree∩τembedded=Ø.
The intuitive difference between a free and an embedded subtask is as follows: a scheduler has the flexibility to sequence a free subtask relative to the other free subtasks without consideration of intra-task deadlines. On the other hand, the scheduler must take extra consideration to satisfy intra-task deadlines when sequencing an embedded subtask relative to other subtasks.
Definition 3: A free self-suspension, EijεEfree, is a self-suspension that suspends two subtasks, τij and τij+1, where τij+1ετfree.
Definition 4: An embedded self-suspension, EijεEembedded, is a self-suspension that suspends the execution of two subtasks, τij and τij+1, where τij+1ετembedded·Efree∩Eembedded=Ø.
In Section 4, we describe how we can use τfree to reduce processor idle time due to Efree, and, in turn, analytically upperbound the duration of the self-suspensions that needs to be treated as task cost. We will also derive an upperbound on processor idle time due to Eembedded.
In Section 6, we describe how we attempt to interleave subtasks within self-suspensions according to specific rules on whether the subtasks and self-suspensions are free or embedded. The next terms we will use to describe how we determine the feasibility of the interleaving of these subtasks and self-suspensions.
Definition 5: A subtask group, Gij, is a set of subtasks that share a common intra-task deadline constraint. If we have a deadline constraint D(i,a)(i,b), then the subtask group for that deadline constraint would be the Gia={τia,τia+1, . . . , τib}, where Gia(k) returns the kth element of Gia(k). Finally, we say that Gia|f Giais the set of all subtasks in Gia that have not finished executing.
Definition 6: An active intra-task deadline is an intra-task deadline constraint, D(i,a)(i,b), where the processor has started τia (or completed) and the processor has not finished τib.
Definition 7: The set of active subtasks, τactive, are the set of all subtasks associated with active deadlines.
Definition 8: The set of next subtasks, τnext, are the set of all subtasks, τij, such that the processor has finished τij−1 but not started τij.
3. Motivating Our jth Subtask First (JSF) Priority Scheduling Policy
Scheduling of self-suspending task sets is challenging because polynomial-time, priority-based approaches such as EDF can result in scheduling anomalies. To construct a tight schedulability test, we desire a priority method of restricting the execution behavior of the task set in a way that allows us to analytically bound the contributions of self-suspensions to processor idle time, without unnecessarily sacrificing processor efficiency.
We restrict behavior using a novel scheduling priority, which we call jth Subtask First (JSF). We formally define the jth Subtask First priority scheduling policy in Definition 5.
Definition 9: jth Subtask First (JSF). We use j to correspond to the subtask index in τij. A processor executing a set of self-suspending tasks under JSF must execute the jth subtask (free or embedded) of every task before any jth+1 free subtask. Furthermore, a processor does not idle if there is an available free subtask unless executing that free task results in temporal infeasibility due to an intra-task deadline constraint.
Enforcing that all jth subtasks are completed before any jth+1 free subtasks allows the processor to execute any embedded kth subtasks where k>j as necessary to ensure that intra-task deadlines are satisfied. The JSF priority scheduling policy offers choice among consistency checking algorithms. A simple algorithm to ensure deadlines are satisfied would require that, if a free subtask that triggers a deadline constraint is executed (i.e. τijετfree, τij+1ετembedded), the subsequent embedded tasks for the associated deadline constraint would then be scheduled as early as possible without the processor executing any other subtasks during this duration.
4. Schedulability Test
To describe how our test works and prove its correctness, we will start with a simplified version of the task set and build to the full task model. We follow the following six steps:
Step 1. We restrict τ such that each task only has two subtasks (i.e., mi=2,∀i), there are no intra-task deadlines, and all tasks are released at t=0 (i.e., φ=0,∀i). Here we will introduce our formula for upperbounding the amount of self-suspension time that we treat as task cost, Wfree. Additionally, we say that all tasks have the same period and deadline (i.e., Ti=Di=Tj=Dj,∀i,jε{1, 2, . . . , n}). Thus, the hyperperiod of the task set is equal to the period of each task.
Step 2. Next, we allow for general task release times (i.e., φi≧0,∀i). In this step, we upperbound processor idle time due to phase offsets, Wφ.
Step 3. Third, we relax the restriction that each task has two subtasks and say that each task can have any number of subtasks.
Step 4. Fourth, we incorporate intra-task deadlines. In this step, we will describe how we calculate an upperbound on processor idle time due to embedded self-suspensions Wembedded.
Step 5. Fifth, we relax the uniform task deadline restriction and allow for general task deadlines where Di≦Ti,∀iε{1, 2, . . . , n}.
Step 6. Lastly, we relax the uniform periodicity restriction and allow for general task periods where Ti≠Tj,∀i,jε{1, 2, . . . , n}.
4.1 Two Subtasks Per Task, No Deadlines, and Zero Phase Offsets
In step one, we consider a task set, τ with two subtasks per each of the n tasks, no intra-task deadlines, and zero phase offsets (i.e., φi=0,∀iεn). Furthermore, we say that task deadlines are equal to task periods, and that all tasks have equal periods (i.e., Ti=Di=Tj=Dj,∀i,jε{1, 2, . . . , n}). We assert that one can upperbound the idle time due to the set of all of the Ei1 self-suspensions by analyzing the difference between the duration of the self-suspensions and the duration of the subtasks costs that will be interleaved during the self-suspensions.
We say that the set of all subtasks that might be interleaved during a self-suspension, Ei1, is Bi1. As described by Equation 3, Bij is the set of all of the jth and jth+1 subtask costs less the subtasks costs for τij and τij+1. Note, by definition, τij and τij+1 cannot execute during Eij. We further define an operator Bij(k) that provides the kth smallest subtask cost from Bij. We also restrict Bij such that the jth and jth+1 subtasks must both be free subtasks if either is to be added. Because we are currently considering task sets with no deadlines, this restriction does not affect the subtasks in Bi1 during this step. In Step 4, we will explain why we make this restriction on the subtasks in Bij.
For convenience in notation, we say that N is the set of all task indices (i.e., N={i|iε{1, 2, . . . , n}}, where n is the number of tasks in the task set, τ). Without loss of generality, we assume that the first subtasks τi1 execute in the order i={1, 2, . . . , n}.

Bij={Cxy|xεN\i,yε{j,j+1},τxjετfree,τxj+1ετfree}  (3)

To upperbound the idle time due to the set of Ei1 self-suspensions, we consider a worst-case interleaving of subtask costs and self-suspension durations, as shown in Equation 6 and Equation 5 where Wj is an upperbound on processor idle time due to the set of Eij self-suspensions, and Wij is an upperbound on processor idle time due to Eij. To determine Wj, we first consider the difference between each of the Eij self-suspensions and the minimum subtask cost that we can guarantee will execute during Eij iff Eij results in processor idle time. To compute this quantity we provide a minimum bound on the number of free subtasks (Equation 4) that will execute during a self-suspension Eij. By taking the maximum over all i of Wij, we upperbound the idle time due to the set of jth self-suspensions.




  
    
      
        
          η
          i
          j
        
        =
        
          
            
              
              
                B
                i
                j
              
              
            
            2
          
          -
          1
        
      
    
    
      
        (
        4
        )
      
    
  
  
    
      
        
          W
          i
          j
        
        =
        
          max
          (
          
            
              (
              
                
                  E
                  i
                  j
                
                -
                
                  
                    ∑
                    
                      k
                      =
                      1
                    
                    
                      η
                      i
                      j
                    
                  
                  ⁢
                  
                    
                      B
                      i
                      j
                    
                    ⁡
                    
                      (
                      k
                      )
                    
                  
                
              
              )
            
            ,
            0
          
          )
        
      
    
    
      
        (
        5
        )
      
    
  
  
    
      
        
          W
          j
        
        =
        
          
            max
            
              i
              |
              
                
                  E
                  i
                  j
                
                ∈
                
                  E
                  free
                
              
            
          
          ⁢
          
            (
            
              W
              i
              j
            
            )
          
        
      
    
    
      
        (
        6
        )
      
    
  




To prove that our method is correct, we first show that Equation 4 lowerbounds the number of free subtasks that execute during a self-suspension Ei1, if Ei1 is the dominant contributor to processor idle time. We will prove this by contradiction, assuming that Ei1 is the dominant contributor to idle time and fewer than




  
    
      
      
        B
        i
        1
      
      
    
    2
  
  -
  1




subtasks execute (i.e., are completely interleaved) during Ei1. We perform this analysis for three cases: for i=1, 1<i=x<n, and i=n. Second, we will show that, if at least





  
    
      
      
        B
        i
        1
      
      
    
    2
  
  -
  1




subtasks execute during Ei1, then Equation 5 correctly upperbounds idle time due to Ei1. Lastly, we will show that if an Ei1 is the dominant contributor to idle time then Equation 6 holds, meaning Wj is an upperbound on processor idle time due to the set of Ei1 self-suspensions. (In Step 3 we will show that these three equations also hold for all Eij.)

4.1.1 Proof of Correctness for Equation 4, where j=1.

Proof by Contradiction for i=1. We currently assume that all subtasks are free (i.e., there are no intra-task deadline constraints), thus




  
    
      
      
        B
        i
        1
      
      
    
    2
  
  =
  
    n
    .
  




We recall that a processor executing under JSF will execute all jth subtasks before any free jth+1 subtask. Thus, after executing the first subtask, τ11, there are n−1 other subtasks that must execute before the processor can execute τ12. Thus, Equation 4 holds for E11 irrespective of whether or not E11 results in processor idle time.

Corollary 1: From our Proof for i=1, any first subtask, τx1, will have at least n−x subtasks that execute during Ex1 if Ex1 causes processor idle time, (i.e., the remaining n−x first subtasks in τ).
Proof by Contradiction for 1<i=x<n. We assume for contradiction that fewer than n−1 subtasks execute during Ex1 and Ex1 is the dominant contributor to processor idle time from the set of first self-suspensions Ei1. We apply Corollary 1 to further constrain our assumption that fewer than x−1 second subtasks execute during Ex1. We consider two cases: 1) fewer than x−1 subtasks are released before τx2 and 2) at least x−1 subtasks are released before τx2.
First, if fewer than x−1 subtasks are released before rx2 (with release time of τxj is denoted rxj), then at least one of the x−1 second subtasks, τa2, is released at or after rx2. We recall that there is no idle time during t=[0,fn1]. Thus, Ea1 subsumes any and all processor idle time due to Ex1. In turn, Ex1 cannot be the dominant contributor to processor idle time.
Second, we consider the case where at least x−1 second subtasks are released before rx2. If we complete x−1 of these subtasks before rx2 then at least n−1 subtasks execute during Ex1, which is a contradiction. If fewer than x−1 of these subtasks execute before rx2, then there must exist a continuous non-idle duration between the release of one of the x−1 subtasks, τa2 and the release of rx2, such that the processor does not have time to finish all of the x−1 released subtasks before rx2. Therefore, the self-suspension that defines the release of that second subtask, Ea2, subsumes any and all idle time due to Ex1. Ex1 then is not the dominant contributor to processor idle time, which is a contradiction.
Proof by Contradiction for i=n. We show that if fewer than n−1 subtasks execute during En1, then En1 cannot be the dominant contributor to processor idle time. As in Case 2: i =x, if rn2 is less than or equal to the release of some other task, τz1, then any idle time due to En1 is subsumed by Ez1, thus En1 cannot be the dominant contributor to processor idle time. If τn2 is released after any other second subtask and fewer than n−1 subtasks then at least one subtask finishes executing after rn2. Then, for the same reasoning as in Case 2: i=x, any idle time due to En1 must be subsumed by another self-suspension. Thus, Ex1 cannot be the dominant contributor to processor idle time if fewer than n−1 subtasks execute during Ei1, where i=n.
4.1.2. Proof of Correctness for Equation 5, where j=1.
Proof by Deduction. If n−1 subtasks execute during Eij, then the amount of idle time that results from Eij is greater than or equal to the duration of Eij less the cost of the n−1 subtasks that execute during that self-suspension. We also note that the sum of the costs of the n−1 subtasks that execute during Eij must be greater than or equal to the sum of the costs of the n−1 smallest-cost subtasks that could possibly execute during Eij. We can therefore upperbound the idle time due to Eij by subtracting the n−1 smallest-cost subtasks. Next we compute Wi1 as the maximum of zero and Ei1 less the sum of the smallest n−1 smallest-cost subtasks. If Wi1 is equal to zero, then Ei1 is not the dominant contributor to processor idle time, since this would mean that fewer than n−1 subtasks execute during Ei1 (see proof for Equation 4). If Wij is greater than zero, then Ei1 may be the dominant contributor to processor idle time, and this idle time due to Eij is upperbounded by Wij.
4.1.3 Proof of Correctness for Equation 6, where j=1.
Proof by Deduction. Here we show that by taking the maximum over all i of Wi1, we upperbound the idle time due to the set of Ei1 self-suspensions. We know from the proof of correctness for Equation 4 that if fewer than n−1 subtasks execute during a self-suspension, Ei1, then that self-suspension cannot be the dominant contributor to idle time. Furthermore, the dominant self-suspension subsumes the idle time due to any other self-suspension. We recall that Equation 5 bounds processor idle time caused by the dominant self-suspension, say Eqj. Thus, we note in Equation 6 that the maximum of the upperbound processor idle time due any other self-suspension and the upperbound for Eqj is still an upperbound on processor idle time due to the dominant self-suspension.
4.2 Step 2) General Phase Offsets
Next we allow for general task release times (i.e., φi≧0,∀i). Phase offsets may result in additional processor idle time. For example, if every task has a phase offset greater than zero, the processor is forced to idle at least until the first task is released. We also observe that, at the initial release of a task set, the largest phase offset of a task set will subsume the other phase offsets. We recall that the index i of the task τi corresponds to the ordering with which its first subtask is executed (i.e. i={1, 2, . . . , n}). We can therefore conservatively upperbound the idle time during t=[0,fn1] due to the first instance of phase offsets by taking the maximum over all phase offsets, as shown in Equation 7.
The quantity Wφ computed in Step 2 is summed with W1 computed in Step 1 to conservatively bound the contributions of first self-suspensions and first phase offsets to processor idle time. This summation allows us to relax the assumption in Step 1 that there is no processor idle time during the interval t=[0,fn1].




  
    
      
        
          W
          φ
        
        =
        
          
            max
            i
          
          ⁢
          
            φ
            i
          
        
      
    
    
      
        (
        7
        )
      
    
  




4.3 Step 3) General Number of Subtasks Per Task

The next step in formulating our schedulability test is incorporating general numbers of subtasks in each task. As in Step 1, our goal is to determine an upperbound on processor idle time that results from the worst-case interleaving of the jth and jth+1 subtask costs during the jth self-suspensions. Again, we recall that our formulation for upperbounding idle time due to the 1st self-suspensions in actuality was an upperbound for idle time during the interval t=[fn1,maxi(fi2)].
In Step 2, we used this understanding of Equation 6 to upperbound idle time resulting from phase offsets. We said that we needed to determine an upperbound on the idle time between the release of the first instance of each task at t=0 and the finish of τn1. Equivalently, this duration is t=[0,maxi,(fi1)].
It follows then that, for each of the jth self-suspensions, we can apply Equation 6 to determine an upperbound on processor idle time during the interval t=[maxi(fij),maxi(fij+1)]. The upperbound on total processor idle time for all free self-suspensions in the task set is computed by summing over the contribution of each of the jth self-suspensions as shown in Equation 8.




  
    
      
        
          W
          free
        
        =
        
          
            
              ∑
              j
            
            ⁢
            
              W
              j
            
          
          =
          
            
              
                ∑
                j
              
              ⁢
              
                
                  max
                  
                    i
                    ❘
                    
                      
                        E
                        i
                        j
                      
                      ∈
                      
                        E
                        free
                      
                    
                  
                
                ⁢
                
                  (
                  
                    W
                    i
                    j
                  
                  )
                
              
            
            =
            
              
                ∑
                j
              
              ⁢
              
                
                  max
                  
                    i
                    ❘
                    
                      
                        E
                        i
                        j
                      
                      ∈
                      
                        E
                        free
                      
                    
                  
                
                ⁢
                
                  (
                  
                    max
                    ⁡
                    
                      (
                      
                        
                          (
                          
                            
                              E
                              i
                              j
                            
                            -
                            
                              
                                ∑
                                
                                  k
                                  =
                                  1
                                
                                
                                  n
                                  -
                                  1
                                
                              
                              ⁢
                              
                                
                                  B
                                  i
                                  j
                                
                                ⁡
                                
                                  (
                                  k
                                  )
                                
                              
                            
                          
                          )
                        
                        ,
                        0
                      
                      )
                    
                  
                  )
                
              
            
          
        
      
    
    
      
        (
        8
        )
      
    
  




However, we need to be careful in the application of this equation for general task sets with unequal numbers of subtasks per task. Let us consider a scenario were one task, τi, has mi subtasks, and τx has only mx=mi−1 subtasks. When we upperbound idle time due to the mith−1 self-suspensions, there is no corresponding subtask τxmi that could execute during Eimi−1. We note that τxmi−1 does exist and might execute during Eimi−1, but we cannot guarantee that it does. Thus, when computing the set of subtasks, Bij, that may execute during a given self-suspension Eij, we only add a pair of subtasks τxj,τxj+1 if both τxj,τxj+1 exist, as described by Equation 3. We note that, by inspection, if τxj were to execute during Eij, it would only reduce processor idle time.
4.4 Step 4) Intra-Task Deadline Constraints
In Steps 1 and 3, we provided a lowerbound for the number of free subtasks that will execute during a free self-suspension, if that self-suspension produces processor idle time. We then upperbounded the processor idle time due to the set of free self-suspensions by computing the least amount of free task cost that will execute during a given self-suspension. However, our proof assumed no intra-task deadline constraints. Now, we relax this constraint and calculate an upperbound on processor idle time due to embedded self-suspensions Wembedded.
Recall under the JSF priority scheduling policy, an embedded subtask τij+1 may execute before all jth subtasks are executed, contingent on a temporal consistency check for intra-task deadlines. The implication is that we cannot guarantee that embedded tasks (e.g. τij or τij+1) will be interleaved during their associated self-suspensions (e.g., Exj, xεN\i).
To account for this lack of certainty, we conservatively treat embedded self-suspensions as task cost, as shown in Equations 9 and 10. Equation 9 requires that if a self-suspension, Eij is free, then Eij(1−xij+1)=0. The formula (1−xij+1) is used to restrict our sum to only include embedded self-suspensions. Recall that a self-suspension, Eij is embedded iff τij+1 is an embedded subtask.
Second, we restrict Bij such that the jth and jth+1 subtasks must be free subtasks if either is to be added. (We specified this constraint in Step 1, but this restriction did not have an effect because we were considering task sets without intra-task deadlines)
Third, we now must consider cases where ηij<n−1, as described in (Equation 4). We recall that ηij=n−1 if there are no intra-task deadlines; however, with the introduction of these deadline constraints, we can only guarantee that at least




  
    
      
      
        B
        i
        j
      
      
    
    2
  
  -
  1




subtasks will execute during a given Eij, if Eij results in processor idle time.





  
    
      
        
          W
          embedded
        
        =
        
          
            ∑
            
              i
              =
              1
            
            n
          
          ⁢
          
            (
            
              
                ∑
                
                  j
                  =
                  1
                
                
                  
                    m
                    i
                  
                  -
                  1
                
              
              ⁢
              
                
                  E
                  i
                  j
                
                ⁡
                
                  (
                  
                    q
                    -
                    
                      x
                      i
                      
                        j
                        +
                        1
                      
                    
                  
                  )
                
              
            
            )
          
        
      
    
    
      
        (
        9
        )
      
    
  
  
    
      
        
          x
          i
          j
        
        =
        
          {
          
            
              
                
                  1
                  ,
                
              
              
                
                  
                    if
                    ⁢
                    
                      
                    
                    ⁢
                    
                      τ
                      i
                      j
                    
                  
                  ∈
                  
                    τ
                    free
                  
                
              
            
            
              
                
                  0
                  ,
                
              
              
                
                  
                    if
                    ⁢
                    
                      
                    
                    ⁢
                    
                      τ
                      i
                      j
                    
                  
                  ∈
                  
                    τ
                    embedded
                  
                
              
            
          
        
      
    
    
      
        (
        10
        )
      
    
  




Having bounded the amount of processor idle time due to free and embedded self-suspensions and phase offsets, we now provide an upperbound on the time HUBτ the processor will take to complete all instances of each task in the hyperperiod (Equation 11). H denotes the hyperperiod of the task set, and HLBτ is defined as the sum over all task costs released during the hyperperiod. Recall that we are still assuming that Ti=Di=Tj=Dj,∀i,jεN; thus, there is only one instance of each task in the hyperperiod.




  
    
      
        
          H
          UB
          τ
        
        =
        
          
            H
            LB
            τ
          
          +
          
            W
            phase
          
          +
          
            W
            
              free
              ⁢
              
                
              
            
          
          +
          
            W
            embedded
          
        
      
    
    
      
        (
        11
        )
      
    
  
  
    
      
        
          H
          LB
          τ
        
        =
        
          
            ∑
            
              i
              =
              1
            
            n
          
          ⁢
          
            
              H
              
                T
                i
              
            
            ⁢
            
              
                ∑
                
                  j
                  =
                  1
                
                
                  m
                  i
                
              
              ⁢
              
                C
                i
                j
              
            
          
        
      
    
    
      
        (
        12
        )
      
    
  




4.5 Step 5) Deadlines Less Than or Equal to Periods

Next we allow for tasks to have deadlines less than or equal to the period. We recall that we still restrict the periods such that Ti=Tj,∀i,jεN for this step. When we formulated our schedulability test of a self-suspending task set in Equation 11, we calculated an upperbound on the time the processor needs to execute the task set, HUBτ. Now we seek to upperbound the amount of time required to execute the final subtask τij for task τi, and we can utilize the methods already developed to upperbound this time.
To compute this bound we consider the largest subset of subtasks in τ, which we define as τ|j⊂τ, that might execute before the task deadline for τi. If we find that HUBτ|j≦Dabs, where Dabs is the absolute task deadline for τi, then we know that a processor scheduling under JSF will satisfy the task deadline for τi. We recall that, for Step 5, we have restricted the periods such that there is only one instance of each task in the hyperperiod. Thus, we have Di,1abs=Di+φi. In Step 6, we consider the more general case where each task may have multiple instances within the hyperperiod. For this scenario, the absolute deadline of the kth instance of τi is Di,kabs=Di+Ti(k−1)+φi.
We present an algorithm named testDeadline(τ,Dabs,j) to perform this test. Pseudocode for testDeadline(τ,Dabs,j) is shown in FIG. 8. This algorithm requires as input a task set τ, an absolute deadline Dabs for task deadline Di, and the j subtask index of the last subtask τij associated with Di (e.g., j=mi associated with Di for τiετ). The algorithm returns true if a guarantee can be provided that the processor will satisfy Di under the JSF, and returns false otherwise.
Referring now to FIG. 8, in Lines 1-14, the algorithm computes τ|j, the set of subtasks that may execute before Di. In the absence of intra-deadline constraints, τ|j includes all subtasks τij′ where i=N (recall N={i|iε{1, 2, . . . , n}}) and j′ε{1, 2, . . . , j}. In the case an intra-task deadline spans subtask τxj (in other words, a deadline D(x,a)(x,b) exists where a≦j and b>j), then the processor may be required to execute all embedded subtasks associated with the deadline before executing the final subtask for task τi. Therefore the embedded subtasks of D(x,a)(x,b) are also added to the set τ|j. In Line 15, the algorithm tests the schedulability of τ|j using Equation 11.
Next we walk through the pseudocode for testDeadline(τ,Dabs,j) in detail. Line 1 initializes τ|j. Line 2 iterates over each task, τx, in τ. Line 3 initializes the index of the last subtask from τx that may need to execute before τij as z=j, assuming no intra-task constraints.
Lines 5-11 search for additional subtasks that may need to execute before τij due to intra-task deadlines. If the next subtask, τxz+1 does not exist, then τxz is the last subtask that may need to execute before τij (Lines 5-6). The same is true if τxz+1ετfree, because τxz+1 will not execute before τij under JSF if z+1>j (Lines 7-8). If τxz+1 is an embedded subtask, then it may be executed before τij, so we increment z, the index of the last subtask, by one (Line 9-10). Finally, Line 13 adds the subtasks collected for τx, denoted τxIj, to the task subset, τ|j.
After constructing our subset τ|j, we compute an upperbound on the time the processor needs to complete τ|j (Line 15). If this duration is less than or equal to the deadline Dabs associated with Di for τi, then we can guarantee that the deadline will be satisfied by a processor scheduling under JSF (Line 16). Otherwise, we cannot guarantee the deadline will be satisfied and return false (Line 18). To determine if all task deadlines are satisfied, we call testDeadline(τ,Dabs,j) once for each task deadline.
4.6 Step 6) General Periods
Thus far, we have established a mechanism for testing the schedulability of a self-suspending task set with general task deadlines less than or equal to the period, general numbers of subtasks in each task, non-zero phase offsets, and intra-task deadlines. We now relax the restriction that Ti=Tj,∀i,j. The principle challenge of relaxing this restriction is there will be any number of task instances in a hyperperiod, whereas before, each task only had one instance.
To determine the schedulability of the task set, we first start by defining a task superset, τ*, where τ*⊃τ. This superset has the same number of tasks as τ (i.e., n), but each task τ*iετ* is composed of




  H
  
    T
    i
  




instances of τiετ. A formal definition is shown in Equation 13, where Ci,kj and Ei,kj are the kth instance of the jth subtask cost and self-suspension of τ*i.

τ*i:(φi,(Ci,11,Ei,11, . . . ,Ci,1mi,Ci,21,Ei,21, . . . ,Ci,2mi, . . . ,Ci,k1,Ei,k1, . . . ,Ci,kmi),D*i=H,T*i=H)  (13)

We aim to devise a test where τ*i is schedulable if HUBτ*≦D*i and if the task deadline Di for each release of τi is satisfied for all tasks and releases. This requires three steps.
First we must perform a mapping of subtasks from τ to τ* that guarantees that τ*ij+1 will be released by the completion time of all other jth subtasks in τ*. Consider a scenario where we have just completed the last subtask τi,kj of the kth instance of τi. We do not know if the first subtask of the next k+1th instance of τi will be released by the time the processor finishes executing the other jth subtasks from τ*. We would like to shift the index of each subtask in the new instance to some j′≧j such that we can guarantee the subtask will be released by the completion time of all other j′−1th subtasks.
Second, we need to check that each task deadline Di,k for each instance k of each task τi released during the hyperperiod will be satisfied. To do this check, we compose a paired list of the subtask indices j in τ* that correspond to the last subtasks for each task instance, and their associated deadlines. We then apply testDeadline(τ,Di,j) for each pair of deadlines and subtask indices in our list.
Finally, we must determine an upperbound, HUBτ*, on the temporal resources required to execute τ* using Equation 11. If HUBτ*≦H, where H is the hyperperiod of τ, then the task set is schedulable under JSF.
We use an algorithm called constructTaskSuperSet(τ), presented in FIG. 9, to construct our task superset τ*. The function constructTaskSuperSet(τ) takes as input a self-suspending task set τ and returns either the superset τ* if we can construct the superset, or null if we cannot guarantee that the deadlines for all task instances released during the hyperperiod will be satisfied.
Referring to FIG. 9, in Line 1, we initialize our task superset, τ*, to include the subtask costs, self-suspensions, phase offsets, and intra-task deadlines of the first instance of each task τi in τ. In Line 2, we initialize a vector I, where I[i] corresponds to the instance number of the last instance of τi that we have added to τ*. Note that after initialization, I[i]=1 for all i. In Line 3, we initialize a vector J, where J[i] corresponds to the j subtask index of τ*ij for instance I[i], the last task instance added to τ*i. The mapping to new subtask indices is constructed in J to ensure that the jth+1 subtasks in τ* will be released by the time the processor finishes executing the set of jth subtasks.
We use D[i][k] to keep track of the subtasks in τ* that correspond to the last subtasks of each instance k of a task τi. D[i][k] returns the j subtask index in τ* of instance k of τi. In Line 4, D[i][k] is initialized to the subtask indices associated with the first instance of each task.
In Line 5, we initialize counter, which we use to iterate through each j subtask index in τ*. In Line 6 we initialize HLB to zero. HLB will be used to determine whether we can guarantee that a task instance in τ has been released by the time the processor finishes executing the set of j=counter−1 subtasks in τ*.
Next we compute the mapping of subtask indices for each of the remaining task instances released during the hyperperiod (Line 7-31). In Line 11, we increment HLB by the sum of the costs of the set of the j=counter−1 subtasks.
In Line 12, we iterate over each task τ*i. First we check if there is a remaining instance of τi to add to τ*i (Line 13). If so, we then check whether counter >J[i] (i.e., the current j=counter subtask index is greater than the index of the last subtask we added to τ*i) (Line 14).
If the two conditions in Line 13 and 14 are satisfied, we test whether we can guarantee the first subtask of the next instance of τi will be released by the completion of the set of the j=counter−1 subtasks in τ* (Line 15). We recall that under JSF, the processor executes all j−1 subtasks before executing a jth free subtask, and, by definition, the first subtask in any task instance is always free. The release time of the next instance of τi is given by Ti*I[i]+φi. Therefore, if the sum of the cost of all subtasks with index jε{1, 2, . . . , counter−1} is greater than the release time of the next task instance, then we can guarantee the next task instance will be released by the time the processor finishes executing the set of j=counter−1 subtasks in τ*.
We can therefore map the indices of the subtasks of the next instance of τi to subtask indices in τ*i with j=counter+y−1, where y is the subtask index of τiy in τi. Thus, we increment I[i] to indicate that we are considering the next instance of τi (Line 16) and add the next instance of τi, including subtask costs, self-suspensions, and intra-task deadlines, to τ*i (Line 17). Next, we set J[i] and D[i][k] to the j subtask index of the subtask we last added to τ*i (Lines 18-19). We will use D[i][k] later to test the task deadlines of the task instances we add to τ*i.
In the case where all subtasks of all task instances up to instance I[i], ∀i are guaranteed to complete before the next scheduled release of any task in τ (i.e, there are no subtasks to execute at j=counter), then counter is not incremented and HLB is set to the earliest next release time of any task instance (Lines 24 and 25). Otherwise, counter is incremented (Line 27). The mapping of subtasks from τ to τ* continues until all remaining task instances released during the hyperperiod are processed. Finally, Lines 31-39 ensure that the superset exists iff each task deadline Di,k for each instance k of each task τi released during the hyperperiod is guaranteed to be satisfied.
In summary, to determine the schedulability of a task set, τ, we call constructTaskSuperSet(τ) on τ. If the function call returns null then we cannot guarantee the feasibility of the task set. If the function call successfully returns a task superset, τ*, then we determine an upperbound, HUBτ*, on the temporal resources required to execute τ* using Equation 11. If HUBτ*≦H, where H is the hyperperiod of τ, then the task set is schedulable under JSF. Furthermore the processor executes τ under JSF according to the j subtask indices of τ*.
5. Schedulability Test Results and Discussion
In this section, we empirically evaluate the tightness of our schedulability test and analyze its computational complexity. We perform our empirical analysis using randomly generated task sets. The number of subtasks mi for a task τi is generated according to mi:U(1,2n), where n is the number of tasks. If mi=1, then that task does not have a self-suspension. The subtask cost and self-suspension durations are drawn from uniform distributions Cij:U(1,10) and Eij:U(1,10), respectively. Task periods are drawn from a uniform distribution such that Ti:U(Σi,jCij,2Σi,jCij). Lastly, task deadlines are drawn from a uniform distribution such that Di:U(Σi,jCij,Ti).
We benchmark our method against the naive approach that treats all self-suspensions as task cost. To our knowledge our method is the first polynomial-time test for hard, periodic, non-preemptive, self-suspending task systems with any number of self-suspensions per task. Other approaches for scheduling self-suspending task sets using model checking with Computational Tree Logic (CTL) are exponential in the number of tasks and do not currently scale to moderately-sized task sets of interest for real-world applications.
5.1 Tightness of the Schedulability Test
The metric we use to evaluate the tightness of our schedulability test is the percentage of self-suspension time our method treats as task cost, as calculated in Equation 14. This provides a comparison between our method and the naive worst-case analysis that treats all self-suspensions as idle time. We evaluate this metric as a function of task cost and the percentage of subtasks that are constrained by intra-task deadline constraints. We note that these parameters are calculated for τ* using constructTaskSuperSet(τ) and randomly generated task sets τ.




  
    
      
        
          E
          ^
        
        =
        
          
            
              
                W
                free
              
              +
              
                W
                embedded
              
            
            
              
                ∑
                
                  i
                  ,
                  j
                
              
              ⁢
              
                E
                i
                j
              
            
          
          *
          100
        
      
    
    
      
        (
        14
        )
      
    
  




FIG. 10 presents the empirical results evaluating the tightness of our schedulability test for randomly generated task sets with 2 to 50 tasks. Each data point and errors bar represents the mean and standard deviation evaluated for fifty randomly generated task sets. {circumflex over (D)} denotes the ratio of subtasks that are released during the hyperperiod and constrained by intra-task deadline constraints to the total number of subtasks released during the hyperperiod. Fifty task sets were randomly generated for each data point. We see that for small or highly constrained task sets, the amount of self-suspension time treated as task cost is relatively high ( >50%). However, for problems with relatively fewer intra-task deadline constraints, our schedulability test for the JSF priority scheduling policy produces a near-zero upperbound on processor idle time due to self-suspensions.
5.2 Computational Scalability of the Schedulability Test
Our schedulability test is computed in polynomial time. We bound the time-complexity as follows, noting that mmax is the largest number of subtasks in any task in τ and Tmin is the shortest period of any task in τ. The complexity of evaluating Equation 11 for τ* is upperbounded by




  O
  ⁡
  
    (
    
      
        n
        2
      
      ⁢
      
        m
        max
      
      ⁢
      
        H
        
          T
          min
        
      
    
    )
  




where





  O
  ⁡
  
    (
    
      n
      ⁢
      
        
      
      ⁢
      
        m
        max
      
      ⁢
      
        H
        
          T
          min
        
      
    
    )
  




bounds the number of self-suspensions in τ*. The complexity of testDeadline( ) is dominated by evaluating Equation 11. In turn, constructTaskSuperset( ) is dominated by





  O
  ⁡
  
    (
    
      n
      ⁢
      
        H
        
          T
          min
        
      
    
    )
  




calls to testDeadline( ). Thus, for the algorithm we have presented in FIGS. 7 and 8, the computational complexity is





  
    O
    ⁡
    
      (
      
        
          n
          3
        
        ⁢
        
          
            
              m
              max
            
            ⁡
            
              (
              
                H
                
                  T
                  min
                
              
              )
            
          
          2
        
      
      )
    
  
  .




However, we note our implementation of the algorithm is more efficient. We reduce the complexity to





  O
  ⁡
  
    (
    
      
        n
        2
      
      ⁢
      
        m
        max
      
      ⁢
      
        H
        
          T
          min
        
      
    
    )
  




by caching the result of intermediate steps in evaluating Equation 11.

6. JSF Scheduling Algorithm

To fully describe our JSF scheduling algorithm, we will first give an overview of the full algorithm. Second, we describe how the algorithm simplifies deadline constraints to better structure the problem. Third, we describe how we use this enhanced problem structure to formulate an online consistency test, which we call the Russian Dolls Test.
6.1 JSF Scheduling Algorithm: Overview
Our JSF scheduling algorithm (FIG. 11) receives as input a self-suspending task set, τ and terminates after all completing all instance of each task τiετ have been completed. Because these tasks are periodic, scheduling can continue until a user-specified terminating condition; however, for simplicity, the algorithm we present terminates after scheduling through one hyperperiod. The algorithm works by stepping through time scheduling released and unscheduled subtasks in τ*. If the processor is available and there is released, unscheduled subtask, τcandidate, the algorithm determines whether or not scheduling τcandidate at the current time t would result in another subtask violating its intra-task deadline constraint. Now, we step through in detail the operation of the algorithm.
Referring to FIG. 11, in Line 1, we construct our task superset from τ using our schedulability test previously described herein. We recall that τ is a hard, periodic, self-suspending task set with phase offsets, task deadlines less than or equal to periods, intra-task deadlines, and multiple self-suspensions per task. τ* is a task set, composed of each task instance of τ released during the hyperperiod for τ. The tasks in τ* are restricted such that T*i=T*j=H where H is the hyperperiod for τ, and T*i and T*j are periods of tasks τ*i,τ*j in τ*. Most importantly, we know that if τ is found schedulable according to our schedulability test (Lines 2-4), then our JSF scheduling algorithm will be able to satisfy all task deadlines. Thus, our scheduling algorithm merely needs to satisfy intra-task deadlines by allowing or disallowing the interleaving of certain subtasks and self-suspensions.
In Line 5, we simplify the intra-task deadlines so that we can increase the problem structure. The operation works by mapping multiple, overlapping intra-task deadlines constraints into one intra-task deadline constraint such that, if a scheduling algorithm satisfies the one intra-task deadline constraint, then the multiple, overlapping constraints will also be satisfied. For example, consider two intra-task deadline constraints, D*(i,a)(i,b) and D*(i,y)(i,z), such that a≦y≦b. First, we calculate the tightness of each deadline constraint, as shown in Equation 15. Second, we construct our new intra-task deadline, D*(i,a),(i,max(b,z)), such that the slack provided by D*(i,a),(i,max(b,z)) is equal to the lesser of the slack provided by D*(i,a)(i,b) and D*(i,y),(i,z), as shown in Equation 16. Lastly, we remove D*(i,a)(i,b) and D*(i,y)(i,z) from the set of intra-task deadline constraints. We continue constructing new intra-task deadline constraints until there are no two deadlines that overlapping (i.e., ∃D*(i,a)(i,b) and D*(i,y)(i,z), such that a≦y≦b).




  
    
      
        
          
        
        ⁢
        
          
            δ
            
              
                (
                
                  i
                  ,
                  a
                
                )
              
              ,
              
                (
                
                  i
                  ,
                  b
                
                )
              
            
            *
          
          =
          
            
              d
              
                
                  (
                  
                    i
                    ,
                    a
                  
                  )
                
                ,
                
                  (
                  
                    i
                    ,
                    b
                  
                  )
                
              
              *
            
            -
            
              C
              i
              
                *
                b
              
            
            +
            
              
                ∑
                
                  j
                  =
                  a
                
                
                  b
                  -
                  1
                
              
              ⁢
              
                C
                i
                
                  *
                  j
                
              
            
            +
            
              E
              i
              
                *
                j
              
            
          
        
      
    
    
      
        (
        15
        )
      
    
  
  
    
      
        
          d
          
            
              (
              
                i
                ,
                a
              
              )
            
            ,
            
              (
              
                i
                ,
                
                  max
                  ⁢
                  
                    
                  
                  ⁢
                  b
                
                ,
                z
              
              )
            
          
          *
        
        =
        
          
            min
            ⁡
            
              (
              
                
                  δ
                  
                    
                      (
                      
                        i
                        ,
                        a
                      
                      )
                    
                    ,
                    
                      (
                      
                        i
                        ,
                        b
                      
                      )
                    
                  
                  *
                
                ,
                
                  δ
                  
                    
                      (
                      
                        i
                        ,
                        y
                      
                      )
                    
                    ,
                    
                      (
                      
                        i
                        ,
                        z
                      
                      )
                    
                  
                  *
                
              
              )
            
          
          -
          
            C
            i
            
              *
              
                max
                ⁡
                
                  (
                  
                    b
                    ,
                    z
                  
                  )
                
              
            
          
          +
          
            
              ∑
              
                j
                =
                a
              
              
                
                  max
                  ⁡
                  
                    (
                    
                      b
                      ,
                      z
                    
                    )
                  
                
                -
                1
              
            
            ⁢
            
              C
              i
              
                *
                j
              
            
          
          +
          
            E
            i
            
              *
              j
            
          
        
      
    
    
      
        (
        16
        )
      
    
  




Next, we initialize our time to zero (Line 6) and schedule all tasks in τ released during the hyperperiod (i.e., all τ*i in τ*) (Lines 7-23). At each step in time, if the processor is not busy executing a task (Line 8), we collect all available subtasks (Line 9). There are three conditions necessary for a subtask, τ*ij, to be available. First, an available subtask, τ*ij must have been released (i.e., t≧r*ij). We note that we determine the release time of a subtask according to Equation 17. Second, the processor must have neither started nor finished τ*ij. If τ*ij is a free subtask, then all τ*ij−1 subtasks must have been completed. This third condition is derived directly from the JSF scheduling policy.




  
    
      
        
          r
          i
          
            *
            j
          
        
        =
        
          {
          
            
              
                
                  
                    φ
                    i
                    *
                  
                  ,
                
              
              
                
                  
                    if
                    ⁢
                    
                      
                    
                    ⁢
                    j
                  
                  =
                  1
                
              
            
            
              
                
                  
                    
                      f
                      i
                      
                        *
                        j
                      
                    
                    +
                    
                      E
                      i
                      
                        *
                        j
                      
                    
                  
                  ,
                
              
              
                otherwise
              
            
          
        
      
    
    
      
        (
        17
        )
      
    
  




In Lines 10-16, we iterate over all available subtasks. If the next available subtask (Line 11) is temporally consistent according to our online consistency test (Line 12), then we schedule the subtask at time t. We note that we do not enforce a priority between available subtasks. However, one could prioritize the available subtasks according to EDF, RM, or another scheduling priority. For generality in our presentation of the JSF Scheduling Algorithm, we merely prioritize based upon the i index of τ*iετ*. If we are able to schedule a new subtask, we terminate the iteration (Line 14). After either scheduling a new subtask or if there are no temporally consistent, available subtasks, we increment the clock (Line 21). If all tasks (i.e. all subtask) in τ* have been scheduled, then the scheduling operation has completed (Line 19).
6.2 Russian Dolls Test
The Russian Dolls Test is a method for determining whether or not scheduling a candidate subtask, τcandidate, at time t, will result in a temporally consistent schedule. Consider two deadlines, D(i,a)(i,b) and D(x,y),(x,z) such that D(i,a)(i,b)≦D(x,y),(x,z, with associated subtask groups Gij and Gxy. Furthermore, the processor has just finished executing τxw, where y≦w<z, and we want to determine whether or not we can next schedule τcandidate, where τcandidate=τia, or if we must continue on to some other available task. To answer this question, the Russian Dolls Test evaluates whether or not we can nest the amount of time that the processor will be busy executing Gia within the slack of D(x,y),(x,y+z). If this nesting is possible, then we are able to execute τia and still guarantee that the remaining subtasks in Gia and Gxy can satisfy their deadlines. Otherwise, we assume that scheduling Gia at the current time will result in temporal infeasibility for the remaining subtasks in Gxy.
To understand how the Russian Dolls Test works, we must know three pieces of information about τcandidate, and τactive. We recall an in intra-task deadline, D(i,a),(i,b), is active if the processor has started τia and has not finished τib. In turn, a subtask is in τactive if it is associated with an active deadline.
Definition 10: If τij is the first, unexecuted subtask in Gij associated with D(i,a),(i,b), where a≦j≦b, then with tmaxIij is the remaining time available to execute the unexecuted subtasks in Gij. We compute tmaxIij using Equation 18. If there is no intra-task deadline associate with τij, then tmaxIij=Cij.




  
    
      
        
          
            
              t
              max
            
            ⁢
            
              ❘
              i
              j
            
          
          =
          
            
              min
              ⁡
              
                [
                
                  
                    
                      
                        
                          D
                          
                            
                              (
                              
                                i
                                ,
                                a
                              
                              )
                            
                            ,
                            
                              (
                              
                                i
                                ,
                                b
                              
                              )
                            
                          
                        
                        +
                        
                          s
                          i
                          a
                        
                      
                    
                  
                  
                    
                      
                        T
                        -
                        
                          (
                          
                            
                              
                                ∑
                                
                                  q
                                  =
                                  
                                    b
                                    +
                                    1
                                  
                                
                                
                                  m
                                  i
                                
                              
                              ⁢
                              
                                C
                                i
                                q
                              
                            
                            +
                            
                              E
                              i
                              
                                q
                                -
                                1
                              
                            
                          
                          )
                        
                      
                    
                  
                
                ]
              
            
            -
            t
          
        
        ,
        
          

        
        ⁢
        
          ∀
          
            j
            ∈
            
              {
              
                a
                ,
                
                  a
                  +
                  1
                
                ,
                ...
                ⁢
                
                  
                
                ,
                b
              
              }
            
          
        
      
    
    
      
        (
        18
        )
      
    
  




Definition 11: If τij is the first, unexecuted subtask in Gij, associated with D(i,a),(i,b), where a≦j≦b, then tmin|ij is the a lowerbound on the time the processor will be occupied executing the remaining subtasks in Gij. We compute tmin|ij using Equation 19. This method treats self-suspensions as task cost. If there is no intra-task deadline associate with τij, then tmin|ij=Cij.




  
    
      
        
          
            t
            min
          
          ⁡
          
            (
            
              τ
              i
              j
            
            )
          
        
        =
        
          
            C
            i
            b
          
          +
          
            
              ∑
              
                q
                =
                j
              
              
                b
                -
                1
              
            
            ⁢
            
              C
              i
              q
            
          
          +
          
            E
            i
            q
          
        
      
    
    
      
        (
        19
        )
      
    
  




Definition 12: tδ|ij is the slack time available for the processor to execute subtasks not in the Gij. This duration is equal to the difference between tmax and tmin.

tδ(D(i,j))=tmax|ij−tmine|ij  (20)

Having defined these, we can now formally describe the Russian Dolls Test.
Definition 13: The Russian Dolls Test determines whether or not we can schedule τcandidate=τij at time t by first considering the direct execution τcandidate at t, and second, if there is a deadline D(i,j),(i,b), considering the activation of this deadline.
To check the first consideration, we can merely evaluate whether the cost of τcandidate (i.e., Cij) is less than or equal to the slack of every active deadline. For the second consideration, if there is a deadline D(x,w),(x,z) such that x=i and w=j, then we must consider the indirect effects of activating D(i,j),(i,z) on the processor after executing τij. If {τij+1, . . . , τib} is the set of all unexecuted tasks in Gij after executing τij, then we must ensure that the can nest amongst the other active subtasks. If, for all active deadlines D(x,w),(x,z), where τxyετnext, we can nest {τij+1, . . . , τib} within the slack of {τxy, . . . , τxz} or vice versa, then we can guarantee that the processor will find a feasible schedule.
We note that if a candidate subtask, τcandidate=τij with associated deadline D(i,j),(i,z), passes the Russian Dolls Test, we do not need to re-test D(i,j),(i,z) when attempting to execute any subtask in the set {τij+1, . . . , τiz}. For the processor to execute a subtask in {τij+1, . . . , τiz}, we merely need to test whether the cost of the subtask is less than or equal to the slack of every other active deadlines not including D(i,j),(i,z).
We provide pseudocode to describe the Russian Dolls Test in FIG. 12. In Line 1, we test whether or not τcandidate will active a deadline D(x,w),(x,z), where x=i and w=j. If so, we determine the parameters tmax, tmin, and tδ for {τij+1, . . . , τiz} in Lines 3-5. In Lines 7-25, we determine whether we can perform the nesting of deadlines and associated active subtasks. We iterate over all subtasks that are active and next. For a subtask, τxy to be in active and next, then τxy−1 must have been completed and there must be an intra-task deadline D(x,w),(x,z) such that w≦y≦z. If the rth subtask in the set of active and next subtasks is not the equal to the candidate subtask, then we proceed with testing the rth subtask in this set. In Lines 11-13, we compute tmax, tmin, and tδ for the unexecuted subtasks in τxy (i.e., {τxy, . . . , τxz}).
In Lines 14-16, we evaluate the first consideration of the Russian Dolls Test: whether the cost of τcandidate (i.e., Cij) is less than or equal to the slack of D(x,w),(x,z). If not, then executing τcandidate at time t will directly result in τxy missing its deadline, so we return that the nesting is not possible (Line 15). Otherwise, we proceed. Next, we evaluate the second consideration of the Russian Dolls test: if there is a deadline D(x,w),(x,z) such that x=i and w=j, then we must consider the indirect effects of activating D(i,j),(i,b) on the processor after executing τij. If there is such a deadline D(i,j),(i,z) (Line 17), then we consider whether we can nest the execution of {τij+1, . . . , τib} within the slack of D(x,w),(x,z) or nest the execution of {τxy, . . . , τxz} within the slack of D(i,j),(i,b) (Line 18). If not, then we cannot guarantee that all subtasks in these sets (i.e., {τij+1, . . . , τib}∪{τxy, . . . , τxy}) will meet their deadline requirements, so we return false (Line 19). After iterating over all active, next subtasks, if we do not meet a failure condition, then we may execute τcandidate at time t.
7. Scheduler Results
In this section, we empirically validate the tightness of the scheduler and analyze its computational complexity. We perform our empirical analysis using randomly generated task sets. The number of subtasks mi for a task τi is generated according to mi:U(1,2n), where n is the number of tasks. If mi=1, then that task does not have a self-suspension. The subtask cost and self-suspension durations are drawn from uniform distributions Cij:U(1,10) and Eij:U(1,10), respectively. Task periods are drawn from a uniform distribution such that Ti:U(Σi,jCij,2Σi,jCij). Lastly, task deadlines are drawn from a uniform distribution such that Di:U(Σi,jCij,Ti).
7.1 Empirical Validation
The metric we use to evaluate the tightness of our JSF Scheduling Algorithm is similar to the metric we used above to test the tightness of our Schedulability Test. For our Schedulability Test, we consider the percentage of self-suspension time our method treats as task cost. This measure provides a comparison between our schedulability test and the naive worst-case analysis that treats all self-suspensions as idle time. For our JSF Scheduling Algorithm, we consider the percentage of self-suspension time that the processor actually is idle.
FIG. 13 presents the empirical results evaluating the tightness of our scheduler for randomly generated task sets with 2 to 12 tasks. Each data point and errors bar represents the mean and standard deviation evaluated for ten randomly generated task sets. {circumflex over (D)} denotes the ratio of subtasks that are released during the hyperperiod and constrained by intra-task deadline constraints to the total number of subtasks released during the hyperperiod. We see the amount of amount idle time due to self-suspensions normalized to the total duration of the self-suspensions is inversely proportional to problem size. For large problem sizes, our JSF scheduling algorithm produces a near-zero amount of idle time due to self-suspensions relative to the total duration of all self-suspensions released during the hyperperiod.
7.2 Computational Complexity
We upperbound the computational complexity of our JSF Scheduling Algorithm for each time step. At each time step, the processor must consider n tasks in the worst case. For each of the n tasks, the scheduler would call russianDollsTest(τij). In the worst case, the number of active deadlines is upperbounded by n; thus, the complexity of the Russian Dolls Test is O(n). In turn, the JSF Scheduling algorithm performs at most O(n2) operations for each time step.
Certain embodiments of the present invention are described above. It is, however, expressly noted that the present invention is not limited to those embodiments, but rather the intention is that additions and modifications to what is expressly described herein are also included within the scope of the invention. Moreover, it is to be understood that the features of the various embodiments described herein are not mutually exclusive and can exist in various combinations and permutations, even if such combinations or permutations are not made express herein, without departing from the spirit and scope of the invention. In fact, variations, modifications, and other implementations of what is described herein will occur to those of ordinary skill in the art without departing from the spirit and the scope of the invention. As such, the invention is not to be defined only by the preceding illustrative description, but rather by the claims.

## Claims

1. In a system comprising at least one computer having at least one memory storing computer-executable instructions, a method of determining schedulability of tasks for uniprocessor execution, the method comprising:
executing the instructions by at least one processing unit, the execution of the instructions resulting in the at least one computer performing the steps of:
receiving a well-formed, non-preemptive task set comprising a plurality of tasks, each task having a period and at least one subtask, wherein the task set is designated for execution by a uniprocessor;
performing a schedulability test on the task set by:
constructing, from the task set, a task superset defining relationships among subtasks of tasks in the task set, wherein the task superset comprises a number of tasks corresponding to a number of tasks in the task set, each task in the task superset comprising a plurality of instances of a corresponding task in the task set;
calculating an upper bound on temporal resources required to execute the task superset; and
determining whether the task set is schedulable based on whether the upper bound exceeds a hyperperiod of the task set, wherein the hyperperiod of the task set comprises a sum of the periods of the tasks in the task set; and

upon determining that the task set is schedulable, configuring the uniprocessor to perform the tasks in the task set according to a schedule.

2. The method of claim 1, wherein at least two subtasks in the task set are related by at least one of precedence, a wait constraint, and a deadline constraint.

3. The method of claim 2, wherein at least one of the tasks in the task set comprises an intra-task deadline constraint.

4. The method of claim 3, wherein the intra-task deadline constraint comprises a hard constraint.

5. The method of claim 1, wherein a first one of the tasks in the task set has a first number of subtasks and a second one of the tasks in the task set has a second number of subtasks, the second number of subtasks being different from the first number of subtasks.

6. The method of claim 5, wherein the number of subtasks in each task in the task set is independent of the number of subtasks in each of the other tasks in the task set.

7. The method of claim 1, wherein the schedulability test is performed in polynomial time.

8. The method of claim 1, wherein the execution of the instructions further results in the at least one computer performing the step of determining in polynomial time whether a subtask in the task set is schedulable at a specific time.

9. The method of claim 1, wherein the plurality of instances of a corresponding task in the task set comprises a number of instances equal to the hyperperiod of the task set divided by a period of the corresponding task in the task set.

10. A system for determining schedulability of tasks for uniprocessor execution, the system comprising:
at least one memory storing computer-executable instructions; and
at least one processing unit for executing the instructions, wherein execution of the instructions causes the at least one processing unit to:
receive a well-formed, non-preemptive task set comprising a plurality of tasks, each task having a period and at least one subtask, wherein the task set is designated for execution by a uniprocessor;
perform a schedulability test on the task set by:
constructing, from the task set, a task superset defining relationships among subtasks of tasks in the task set, wherein the task superset comprises a number of tasks corresponding to a number of tasks in the task set, each task in the task superset comprising a plurality of instances of a corresponding task in the task set;
calculating an upper bound on temporal resources required to execute the task superset; and
determining whether the task set is schedulable based on whether the upper bound exceeds a hyperperiod of the task set, wherein the hyperperiod of the task set comprises a sum of the periods of the tasks in the task set; and

upon determining that the task set is schedulable, configure the uniprocessor to perform the tasks in the task set according to a schedule.

11. The system of claim 10, wherein at least two subtasks in the task set are related by at least one of precedence, a wait constraint, and a deadline constraint.

12. The system of claim 11, wherein at least one of the tasks in the task set comprises an intra-task deadline constraint.

13. The system of claim 12, wherein the intra-task deadline constraint comprises a hard constraint.

14. The system of claim 10, wherein a first one of the tasks in the task set has a first number of subtasks and a second one of the tasks in the task set has a second number of subtasks, the second number of subtasks being different from the first number of subtasks.

15. The system of claim 14, wherein the number of subtasks in each task in the task set is independent of the number of subtasks in each of the other tasks in the task set.

16. The system of claim 10, wherein the at least one processing unit, in executing the instructions, is configured to perform the schedulability test in polynomial time.

17. The system of claim 10, wherein the execution of the instructions further causes the at least one processing unit to determine in polynomial time whether a subtask in the task set is schedulable at a specific time.

18. In a system comprising at least one computer having at least one memory storing computer-executable instructions, a method of determining schedulability of a subtask for uniprocessor execution, the method comprising:
executing the instructions by at least one processing unit, the execution of the instructions resulting in the at least one computer performing the steps of:
receiving a well-formed, non-preemptive task set comprising a plurality of tasks, each task having at least one subtask, wherein the task set is designated for execution by a uniprocessor;
determining whether the task set can be scheduled according to a particular scheduling policy given constraints relating particular tasks in the task set to each other by calculating an upper bound on temporal resources required to execute a task superset constructed from the task set, wherein the task superset comprises a number of tasks corresponding to a number of tasks in the task set, each task in the task superset comprising a plurality of instances of a corresponding task in the task set;
generating a schedule for the task set using the particular scheduling policy, the generating comprising determining in polynomial time whether a particular subtask in the task set is schedulable at a specific time; and
upon determining that the task set can be scheduled, configuring a uniprocessor to perform the tasks in the task set according to the schedule.

19. The method of claim 18, wherein at least two subtasks in the task set are related by at least one of precedence, a wait constraint, and a deadline constraint.

20. The method of claim 19, wherein at least one of the tasks in the task set comprises an intra-task deadline constraint.

21. The method of claim 19, wherein the determination of whether the particular subtask in the task set is schedulable is based at least in part on an intra-task deadline constraint of at least one other task in the task set.

22. The method of claim 18, wherein the determination of whether the particular subtask in the task set is schedulable comprises determining whether a first subtask group in the task set can be nested within a slack interval of a second subtask group in the task set.

23. The method of claim 22, wherein each subtask within a subtask group shares a common deadline constraint.

24. A system for determining schedulability of a subtask for uniprocessor execution, the system comprising:
at least one memory storing computer-executable instructions; and
at least one processing unit for executing the instructions, wherein execution of the instructions causes the at least one processing unit to:
receive a well-formed, non-preemptive task set comprising a plurality of tasks, each task having at least one subtask, wherein the task set is designated for execution by a uniprocessor;
determine whether the task set can be scheduled according to a particular scheduling policy given constraints relating particular tasks in the task set to each other by calculating an upper bound on temporal resources required to execute a task superset constructed from the task set, wherein the task superset comprises a number of tasks corresponding to a number of tasks in the task set, each task in the task superset comprising a plurality of instances of a corresponding task in the task set;
generate a schedule for the task set using the particular scheduling policy, the generation of the schedule comprising determining in polynomial time whether a particular subtask in the task set is schedulable at a specific time; and
upon a determination that the task set can be scheduled, configure a uniprocessor to perform the tasks in the task set according to the schedule.

25. The system of claim 24, wherein at least two subtasks in the task set are related by at least one of precedence, a wait constraint, and a deadline constraint.

26. The system of claim 25, wherein at least one of the tasks in the task set comprises an intra-task deadline constraint.

27. The system of claim 25, wherein the at least one processing unit, in executing the instructions, is configured to determine whether the particular subtask in the task set is schedulable based at least in part on an intra-task deadline constraint of at least one other task in the task set.

28. The system of claim 24, wherein the at least one processing unit, in determining whether the particular subtask in the task set is schedulable, determines whether a first subtask group in the task set can be nested within a slack interval of a second subtask group in the task set.

29. The system of claim 28, wherein each subtask within a subtask group shares a common deadline constraint.