An on-line scheduling and allocation scheme for real-time tasks in 2D meshes

In hard real-time environment scheduling and allocation of sporadic tasks for multiprocessor systems is a challenging problem. In this paper, we propose an on-line scheduling and allocation scheme for real-time tasks which require the exclusive use of submeshes in 2D mesh system. By effectively manipulating the information on allocated or reserved submeshes, the proposed scheme can quickly identify the earliest available time of a free submesh for a newly-arrived task. We employ a preemption approach to reduce the complexity of the search for a feasible schedule. Computer simulation reveals that the proposed scheme significantly improves the system performance by decreasing the number of tasks rejected