On scheduling soft real-time tasks with lock-free synchronization for embedded devices

ABSTRACT

In this paper, we consider minimizing the system-level energy consumption through dynamic voltage scaling for embedded devices, while a) allowing concurrent access to shared objects through lock-free synchronization b) meeting (m, k))-constraint, and c) completing as many high importance tasks as possible. We present a scheduling algorithm called Lock-Free Utility accrual Algorithm (or MK-LfUA) to meet these goals. At offline stage, we set the optimal CPU speed to minimize system-level energy consumption. At run-time, the algorithm dynamically adjusts the CPU speed to compensate for slack time. Our simulation studies on the Intel PXA271 processor model illustrate MK-LfUA's superiority over past work by 15-25%.

REFERENCES

• 1: Hakan Aydi , Pedro Mejía-Alvarez , Daniel Mossé , Rami Melhem, Dynamic and Aggressive Scheduling Techniques for Power-Aware Real-Time Systems, Proceedings of the 22nd IEEE Real-Time Systems Symposium, p.95, December 03-06, 2001
• 2: Hyeonjoong Cho , Binoy Ravindran , E. Douglas Jensen, Lock-free synchronization for dynamic embedded real-time systems, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 3: Parameswaran Ramanathan , Moncef Hamdaoui, A Dynamic Priority Assignment Technique for Streams with (m, k)-Firm Deadlines, IEEE Transactions on Computers, v.44 n.12, p.1443-1451, December 1995 [doi>10.1109/12.477249]
• 4: E. D. Jensen, C. D. Locke, and H. Tokuda. A time-driven scheduling model for real-time operating systems. In RTSS, December 1985.
• 5: Thomas L. Martin , Daniel P. Siewiorek, Nonideal battery and main memory effects on CPU speed-setting for low power, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.1, p.29-34, Feb. 2001 [doi>10.1109/92.920816]
• 6: L. Niu and G. Quan. Energy minimization for real-time systems with (m,k)-guarantee. IEEE Trans. on VLSI Systems, 14:717--729, 1997.
• 7: L. Sha , R. Rajkumar , J. P. Lehoczky, Priority Inheritance Protocols: An Approach to Real-Time Synchronization, IEEE Transactions on Computers, v.39 n.9, p.1175-1185, September 1990 [doi>10.1109/12.57058]
• 8: Haisang Wu , Binoy Ravindran , E. Douglas Jensen , Peng Li, Energy-efficient, utility accrual scheduling under resource constraints for mobile embedded systems, Proceedings of the 4th ACM international conference on Embedded software, September 27-29, 2004, Pisa, Italy [doi>10.1145/1017753.1017768]