## 2 Problem Formulation and Complexity Review  
### Task Model and Problem Description  
Consider a set \(\tau\) of \(n\) real-time tasks, where each task \(t\in\tau\) is represented by a four-tuple:  
\[t_{i}=\left(p_{i},c_{i},d_{i},o_{i}\right) \tag{1}\]  
In which \(p_{i}\) is the task period, \(c_{i}\) is the worst case computation time of the task, \(d_{i}\) is the task deadline and \(o_{i}\) is the task offset (release time), represented as integers in suitable processor time units, for example microseconds. For the purposes of this paper it is assumed that the worst case computation time \(c\) of each task has been determined using suitable analysis techniques (see, for example [15]) and that an appropriate 'factor of safety' has been added to this estimate. Even when rigorous techniques such as static analysis are used in conjunction with standard testing, it is normal to overestimate these values by a factor of around 5% [10, 15]. In this paper it also assumed that tasks are not subject to precedence constraints, and task I/O processing is small enough to be neglected. The paper restricts attention to instances having \(n\leq 30\) tasks. Since no restriction is placed on the choice of task periods, this is representative of most real-world task sets. The objective of any feasibility analysis or test is to determine if the task set will always meet its deadlines for a given scheduling algorithm. In the case of the non-preemptive thrift scheduler, this surmounts to verifying that a 'task overrun' - an overload of the processor in any given time quantum - does not occur. The time quantum is normally referred to as the tick interval \(t_{Tick}\) and is chosen to be as large as possible given the task periods, using (2):  
\[t_{Tick}=\gcd(p_{1},\ldots,p_{n}) \tag{2}\]  
where \(gcd\) represents greatest common divisor. Without loss of generality, it can be assumed that the offsets for each task are specified as an integer multiple of the tick interval, according to the following condition [10-12]:  
\[\forall i;\,0<i<n;\,o_{i}=k\cdot t_{Tick};\,0\leq k<\frac{p_{i}}{t_{Tick}} \tag{3}\]  
Since it is desired to prevent task overruns, a constraint is placed in thrift schedulers that the effective deadline of _all_ tasks released at the start of any tick interval is the start of the following tick interval [2,3,9]. As such, a specific deadline is often omitted when describing task sets for thrift schedulers. Under these conditions, a sufficient and necessary schedulability test for synchronous task sets can be formulated to be as follows [21]:  
\[\sum\limits_{i=1}^{i=n}c_{i}\leq t_{Tick} \tag{4}\]  
Although this also provides a sufficient test for offset-free schedules, it is clearly not necessary, as illustrated in Figure 2. Similarly, two necessary (but not sufficient) related tests for offset-free thrift schedules are as follows:  
\[\forall i,\,0<i<n;\,c_{i}<t_{Tick} \tag{5}\]  
\[\sum\limits_{i=1}^{i=n}\frac{c_{i}}{p_{i}}\leq 1 \tag{6}\]  
That is, the execution time of each task must be less than \(t_{Tick}\), and the total CPU utilization \(u\) must be less than unity. A necessary and sufficient test for schedulability can only be determined algorithmically; existing approaches generally perform this through a simulation of the task schedule over a fixed time horizon, known as the schedule hyperperiod--this algorithmic process is generally referred to as \"hyperperiod simulation\" [1,9-12]. In the case of the thrift scheduler, given the deadline restrictions the hyperperiod has a length \(h\) given by [20,22,23]:  
\[h=lcm(p_{1},\ldots,p_{n}) \tag{7}\]  
where \(lcm\) is the least common multiple, in this case of the task periods. At each search point, the computational load \(\eta\) placed on the processor by the schedule in the given time bound of the current search point is computed. From (3), it can be seen that tasks may only be released at the start of any given tick interval.