制式多處理器下即時排程的增進

Abstract

Scheduling periodic tasks on multiprocessor platform in a hard-real-time environment is one of the fundamental problems in computer science. In this thesis, we consider the problem of on-line scheduling a set of n independent periodic tasks on m uniform processors. We present an optimal scheduling algorithm in the sense that the algorithm is able to schedule any feasible set to meet all deadlines. From previous works, the optimal algorithm gave an O(n) bound for number of task migration and an O(n lg n) bound for time complexity on each rescheduling. But for our algorithm, we reduce both number of task migration and time complexity to O(1) and O(lg n) respectively. Our algorithm also guarantees minimal schedule length for scheduling non-periodic tasks on uniform multiprocessors.