Open this publication in new window or tab >>2010 (English)In: Lecture Notes in Computer Science, vol. 6490, Springer, 2010, p. 253-269Chapter in book (Refereed)
Abstract [en]
There are two main approaches to task scheduling on multiprocessor/multi-core platforms; 1) global scheduling, under which migration of tasks among processors is allowed, and 2) partitioned scheduling under which tasks are allocated onto processors and task migration is not allowed. Under global scheduling a higher utilization bound can be achieved, but in practice the overheads of migrating tasks is high. On the other hand under partitioned scheduling, besides simplicity and efficiency, existing scheduling and synchronization methods developed for uniprocessor platforms can more easily be extended to partitioned scheduling. However the partitioned scheduling protocols suffer from the problem of partitioning tasks among processors/cores which is a bin-packing problem. Therefore, several heuristic algorithms have been developed for partitioning a task set on multiprocessor platforms. However, these algorithms typically assume independent tasks while in practice real-time systems often contain tasks that share resources and hence may block each other.
In this paper we propose a blocking-aware partitioning algorithm which allocates a task~set onto processors in a way that the overall amount of blocking times of tasks are decreased. The algorithm reduces the total utilization which, in turn, has the potential to decrease the total number of required processors (cores). In this paper we evaluate our algorithm and compare it with an existing similar algorithm. The comparison criteria includes both number of schedulable systems as well as processor reduction performance.
Place, publisher, year, edition, pages
Springer, 2010
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 6490
National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-9592 (URN)10.1007/978-3-642-17653-1_20 (DOI)000290495600020 ()2-s2.0-78650872347 (Scopus ID)9783642176524 (ISBN)
Note
14th International Conference on Principles of Distributed Systems, OPODIS 2010; Tozeur;14 December 2010 through 17 December 2010
2010-05-172010-05-172025-10-10Bibliographically approved