An Efficient Multi-Task Scheduling Methodology for Real-Time System Based on Normalized Slack Time

Tomoyoshi Funazaki; Hirofumi Yamamoto; Shinichirou Taguchi; Takesi Kondo

doi:10.4271/2014-01-0232

This paper presents a multi-task scheduling algorithm with small circuit size implementation to achieve high-speed performance for real-time system.

Rate Monotonic Scheduling (RMS) is generally used because of its low cost and easy implementation although it is not highly efficient. On the other hand, Least Slack Time Scheduling (LSTS) has high scheduling efficiency, especially in a multi-core system, which is becoming widely used in recent years. However, it is difficult to process in real time by software implementation with LSTS, because the straightforward LSTS implementation has to calculate individual slack time from release time of each task, and compare them to determine the execution priority. Even though LSTS algorithm has already been implemented in hardware, its long circuit delay and the large circuit area still remain to be solved.

Our proposal focuses on the time management that is the dominant part in LSTS process. The proposed method normalizes slack time by using a common timer and determines the execution priority based on ascending order of the time point when slack time runs out. In such cases, time measurement for individual task is no longer needed and operations for task dispatching can be reduced. The proposed algorithm uses less amount of calculation to maintain the same execution priority of tasks as the conventional algorithm.

Consequently, proposed algorithm can reduce the circuit area by 77% and its delay by 88% compared to the conventional approach. Furthermore, the simulation result shows that scheduling efficiency with the proposed algorithm performs very close to the theoretical value.

Standards

SAE Mobilus®

Publications

News

Events

Professional Development

A World in Motion (PreK-12)

Participate with SAE

SAE Membership

Donate

An Efficient Multi-Task Scheduling Methodology for Real-Time System Based on Normalized Slack Time 2014-01-0232

SAE MOBILUS