Scheduling Open Dynamic Systems: The Clearing Fund Algorithm

SANTOS VALENTINUZZI, RODRIGO; GIUSEPPE LIPARI,; JORGE SANTOS,

Gotenburgo

Congreso; 10th International Conference on Real-Time Computing Systems and Applications; 2004

This paper presents the Clearing Fund Algorithm (CFA),designed to schedule soft real-time threads in an open dynamic environment. CFA is built as a third layer upon the Constant Bandwidth Server (CBS) and the Bandwidth Inheritance (BWI) algorithms. The BWI algorithm applies the Priority Inheritance protocol to the CBS algorithm: when a task is blocked on a critical section by another task, the latter inherits the server of the former task, stealing its bandwidth. In this way, soft real-time tasks can share mutually exclusive resources in an open dynamic system. However, one of the main drawbacks of the BWI algorithm is its unfairness. In fact, a task can potentially steal thebandwidth of another server without paying any penalty.The main idea of the CFA is to keep track of debts contracted by lowpriority tasks that block higher priority tasks and are executed in their servers. The effects of those priority inversions are reduced because the blocked thread can finish its execution in its own server or in the server of the blocking task, whichever has the nearest deadline. If required, debts are paid back in that way. Also, at certain instants in time, all existing debts may be waived and the servers are reset making a clear restart of the system.