P.: Translating off-line schedules into task attributes for fixed priority scheduling

Off-line scheduling and fixed priority scheduling (FPS) are often considered as complementing and incompatible paradigms. A number of industrial applications demand temporal properties (predictability, jitter constraints, end-to-end deadlines, etc.) that are typically achieved by using off-line scheduling. The rigid off-line scheduling schemes used, however, do not provide for flexibility. FPS has been widely studied and used in a number of applications, mostly due to its simple run-time scheduling, and small overhead. It can provide more flexibility, but is limited with respect to predictability, as actual start and completion times of exe-cution depend on run-time events. In this paper we show how off-line scheduling and FPS run-time scheduling can be combined to get the advantages of both – the capability to cope with complex timing con-straints and flexibility. The paper assumes that a schedule for a set of tasks with complex constraints has been con-structed off-line. It presents a method to analyze the off-line schedule and derive an FPS task set with FPS attributes priority, offset, and period, such that the runtime FPS exe-cution matches the off-line schedule. It does so by analyzing the schedule and setting up inequality relations for the pri-orities of the tasks under FPS. Integer linear programming (ILP) is then used to find a FPS priority assignment that ful-fils the relations. In case the priority relations for the tasks of the off-line schedule are not solvable we split tasks into the number of instances, to obtain a new task set with con-sistent task attributes. Our schedule translation algorithm keeps the number of newly generated artifact tasks minimal