It is known that the schedulability of a non-preemptive task set with fixed priority can be determined in pseudo-polynomial time. However, since Rate Monotonic scheduling is not optimal for non-preemptive scheduling, the applicability of existing polynomial time tests that provide sufficient schedulability conditions, such as Liu and Layland's bound, is limited. This letter proposes a new sufficient condition for non-preemptive fixed priority scheduling that can be used for any fixed priority assignment scheme. It is also shown that the proposed schedulability test has a tighter utilization bound than existing test methods.

In this paper, we propose a preemptive test scheduling technique (a test can be interrupted and later resumed) for core-based systems with the objective to minimize the test application time. We make use of reconfigurable core test wrappers in order to increase the flexibility in the scheduling process. The advantage with such a wrapper is that it is not limited to a single TAM (test access mechanism) bandwidth (wrapper chain configuration) at each core. We model the scheduling problem as a Bin-packing problem, and we discuss the transformation: number of TAM wires (wrapper-chains) versus test time in combination with preemption, as well as the possibilities and the limitations to achieve an optimal solution in respect to test application time. We have implemented the proposed preemptive test scheduling algorithm, and we have through experiments demonstrated its efficiency.

Scheduling directed a-cyclic task graphs (DAGs) onto multiprocessors is known to be an intractable problem. Although there have been several heuristic algorithms for scheduling DAGs onto multiprocessors, few address the mapping onto a given number of completely connected processors with an objective of minimizing the finish time. We present an efficient algorithm called ClusterMerge to statically schedule directed a-cyclic task graphs onto a homogeneous completely connected MIMD system with a given number of processors. The algorithm clusters tasks in a DAG using a longest path heuristic and then iteratively merges these clusters to give a number of clusters identical to the number of available processors. Each of these clusters is then scheduled on a separate processor. Using simulations, we demonstrate that ClusterMerge schedules task graphs yielding the same or lower execution times than those of other researchers, but using fewer processors. We also discuss pitfalls in the various approaches to defining the longest path in a directed a-cyclic task graph.

The problem of non-preemptive scheduling of real-time periodic tasks with specified release times on a uniprocessor system is known as NP-hard problem. In this paper we propose a new non-preemptive scheduling algorithm and a new static scheduling strategy which use the repetitiveness and the predictability of periodic tasks in order to improve schedulabilities of real-time periodic tasks with specified release times. The proposed scheduling algorithm schedules periodic tasks by using the heuristic that precalculates if the scheduling of the selected task leads to the case that a task misses a deadline when tasks are scheduled by the non-preemptive EDF algorithm. If so, it defers the scheduling of the selected task to avoid the precalculated deadline-missing. Otherwise, it schedules the selected task in the same way as the non-preemptive EDF algorithm. Our scheduling algorithm can always find a feasible schedule for the set of periodic tasks with specified release times which is schedulable by the non-preemptive EDF algorithm. Our static sheduling strategy transforms the problem of non-preemptive scheduling for periodic tasks with specified release times into one with same release times for all tasks. It suggests dividing the given problem into two subproblems, making a non-preemptive scheduling algorithm to find two feasible subschedules for the two subproblems in the forward or backward scheduling within specific time intervals, and then combining the two feasible subschedules into a complete feasible schedule for the given problem. We present the release times as a function of periods for the efficient problem division. Finally, we show improvements of schedulabilities of our scheduling algorithm and scheduling strategy by simulation results.