An Improved Static-Priority Scheduling Algorithm for Multi-Processor Real-Time Systems

Examensarbete för masterexamen

Please use this identifier to cite or link to this item:
Download file(s):
File Description SizeFormat 
129034.pdfFulltext3.39 MBAdobe PDFView/Open
Type: Examensarbete för masterexamen
Master Thesis
Title: An Improved Static-Priority Scheduling Algorithm for Multi-Processor Real-Time Systems
Authors: Xu, Chao
Ding, Ying
Abstract: This thesis deals with the problem of designing a new real-time scheduling algorithm for independent periodic tasks with static priority on multi-processor platforms called IBSP-TS (Interval Based Semi-Partitioned Task Splitting). The widely implemented priority policy Rate-Monotonic is applied in the algorithm. IBSP-TS combines interval-based semi-partition technique and another multi-processor scheduling algorithm SPA2 to achieve the highest possible worst-case utilization bound to ln2 while meeting the deadlines. The assignment of IBSP is divided into two parts. In the first part, tasks are categorized into several interval groups. Each group has its own assignment policy except for the last interval. In most cases, there are some tasks residual after applying all the policies. All the residual tasks are handled along with the tasks from last interval in the second part of the algorithm. The schedulability can be ensured by feasibility tests. The simulation experiment shows IBSP-TS has some good properties compared to the best static-priority multi-processor scheduling algorithm at this moment. It generally has higher success ratio, less sorted tasks and also less task migrations. In the best case, it can achieve the break-down utilization point to 76% in simulation. Additionally, this algorithm can let system designer to choose the number of intervals in the algorithm. The more intervals, the less number of sorted tasks there are.
Keywords: Information Technology;Informationsteknik
Issue Date: 2010
Publisher: Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers)
Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)
Collection:Examensarbeten för masterexamen // Master Theses

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.