## 1 Introduction  
In many real-time embedded systems, some form of scheduler is generally used instead of a full \"real-time operating system\" to keep the software environment as simple as possible. A scheduler typically consists of a small amount of code, and a minimal hardware footprint (e.g., a timer and interrupt controller). In this context, a scheduler is a basic component of an embedded system architecture that is primarily employed to assign (or 'dispatch') software tasks to CPU's at run-time. In a typical situation, at any given time there will be more tasks than CPU's available; the role of the scheduler is to assign tasks to CPU's such that some design goal is met. This paper is concerned with single-processor scheduling, in which there are several periodic tasks to be dispatched on a single CPU, and the goal is to schedule the tasks such that deadlines are not missed. An example of such a situation would be a processor employed in a critical application such as automotive/avionic control and robotics. In such a situation, 'late' calculations--_i.e._, deadline misses--may lead to system instability, resulting in damage to property or the environment, and even loss of life [1]. In general, a scheduler for such a system may be designed around several basic paradigms: time-triggered or event-triggered, and preemptive or co-operative (non-preemptive) [1, 2, 4, 5]. This paper is primarily concerned with time-triggered, co-operative (TTC) schedulers. TTC architectures have been found to be a good match for a wide range of low-cost, resource-constrained applications. These architectures also demonstrate comparatively low levels of task jitter, CPU overheads, memory resource requirements and power consumption [2-5]. Additionally, exploratory studies seem to indicate better transient error recovery properties in TTC systems over their preemptive counterparts; however this issue requires much further investigation [6, 7]. However, non-preemptive schedulers also have certain well discussed drawbacks over their preemptive counterparts; a presumed lack of flexibility, an inability to cope with long task execution times and long/non-harmonic periods, and fragility/complexity problems when generating a schedule being the main perceived obstacles [3, 5, 8, 10]. In practice several techniques now exist to help overcome some of these problems. For example, co-operative designs based on well-understood patterns and state machines [9] coupled with pre-runtime scheduling techniques [4] provide good working solutions to the 'long task' problem. The simplest form of practical TT scheduler is a \"cyclic executive\" [2, 3, 8]. Cyclic executives achieve their behavior by storing a (repeating) look-up table which controls the execution of jobs at any instant of time. The lookup table is divided into a number of minor cycles, which make up a major cycle; the current minor cycle advances with each timer 'tick'. Such a model is generally effective when all task periods are harmonically related, resulting in a short major cycle length. It is known that the off-line problem of assigning task instances to minor cycles (_i.e._, creating the lookup table), such that periodicity constraints of the task are respected, is NP-Hard [8]. However, several effective techniques--such as those adapted from bin packing and simulated annealing--have been developed for most small instances of the problem [8]. A clear limitation that can arise in such architectures is as follows; the major cycle length is proportional to the least common multiple of the task set periods. Thus, when arbitrary - as opposed to harmonic - task periods are considered, no sub-exponential bound can be placed on the length of the required major cycle. In these cases the amount of memory required for storing the lookup table, andthe resulting computational resources that are needed to design the schedule, become hugely impractical. Therefore heavy restrictions have to be placed on the choice of task set periods.