In multi-media applications, one of the most important issues to consider is synchronization of different media streams. Although many research works address this synchronization issue in the network layer, few discuss how OS scheduling can support multi-media synchronization. Most often real-time tasks responsible for playing media streams are scheduled as soon as they are ready. Nevertheless, such simple approach does not guarantee the synchronization and timeliness of multi-media tasks, especially in a computer environment where many of multimedia applications are running....[ Read more ]

In multi-media applications, one of the most important issues to consider is synchronization of different media streams. Although many research works address this synchronization issue in the network layer, few discuss how OS scheduling can support multi-media synchronization. Most often real-time tasks responsible for playing media streams are scheduled as soon as they are ready. Nevertheless, such simple approach does not guarantee the synchronization and timeliness of multi-media tasks, especially in a computer environment where many of multimedia applications are running.

To solve this problem, we formulated a new class of scheduling problems, called the real-time group scheduling problem. We introduced a group concept to conventional real-time scheduling problems. A group consists of two or more real-time tasks to be synchronized. Each group is associated with a time value called group extent. A group is said to satisfy its group constraint if all the tasks in this group finish their computations within its group extent, i.e. the difference in completion times for any task pairs in the group is less than or equal to the group extent. A feasible schedule for the real-time group scheduling problem is one that has all tasks meeting their deadlines and all groups satisfying their group constraints. Under this formulation, the real-time group scheduling problem is general enough to solve most synchronization problems of real-time multimedia tasks.

In this research, we studied uniprocessor non-preemptive real-time group scheduling. Each real-time task under study has its computation time and deadline. All tasks are subject to some predefined precedence constraints. Properties of this scheduling problem were studied. We showed that this scheduling problem is NP-complete. An algorithm framework which guarantees to produce a schedule with all tasks meeting their deadlines (if such a schedule exists) was described. Based on this framework, we devised two polynomial time and static scheduling heuristic algorithms. The algorithms were implemented and simulation experiment was conducted to evaluate their performance. For small-size problems, our experiment showed that the best heuristic algorithm produced no less than 96% feasible schedules and above 90% schedules were optimal schedules. For large-size problems, the best heuristic algorithm produced at least 86% feasible schedules. We concluded that these heuristics are promising and practical for solving most real-time group scheduling problems.