An implementation of the Bandwidth Inheritance Protocol in the Linux Kernel

The Resource Reservation (RR) framework has been proven very effective in the joint scheduling of hard real time and soft real time application in Open Systems. A fundamental problem in this context concerns the extension of the Resource Reservation approach to systems where tasks interact through shared resources. The Bandwidth Inheritance (BWI) protocol was first proposed in [Lamastra G., Lipari G., Abeni L. (2001) A bandwidth inheritance algorithm for real-time task synchronization in open systems. In: Proc. 22nd IEEE Real-Time Systems Symposium] to preserve Bandwidth Isolation between independent groups of tasks, and to enable a schedulability analysis for hard real time tasks. In this paper, we present the first implementation of the BWI protocol within the Linux kernel. We describe the protocol, the way it has been implemented in Linux, and we report some early experiments to measure its overhead. Our work is based on the SCHED_DEADLINE patch, a scheduling class for the Linux kernel that provides Resource Reservation using the Constant Bandwidth Server algorithm. The BWI implementation extends Linux's current implementation of the Priority Inheritance protocol, without affecting past design decisions. Our implementation is neutral to the underlying scheduling scheme and can be adopted in global, clustered and partitioned scheduling. Results show agreement with theoretical analysis, and performance/overheads comparable with the current implementation of Priority Inheritance in Linux. The work presented here has practical implications for applications running on Linux with SCHED_DEADLINE scheduling policy and share resources through mutex semaphores. In fact, the protocol guarantees temporal isolation between non-interacting threads, hence real-time guarantees are possible even where no a-priori information about tasks' scheduling parameters are available.