Soft Real-Time Scheduling on Multiprocessors by UmaMaheswari C. Devi A dissertation submitted to the faculty of the University of North Carolina at Chapel Hill in partial fulfillment of the requirements for the degree of Doctor of Philosophy in the Department of Computer Science. Chapel Hill 2006 Approved by: Prof. Kevin Jeffay Prof.
Daniel Mossé Prof. Ketan Mayer-Patel Prof. Jasleen Kaur UMI Number: 3239248 UMI Microform 3239248 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved.
This microform edition is protected against unauthorized copying under Title 17, United States Code. ProQuest Information and Learning Company 300 North Zeeb Road P. Box 1346 Ann Arbor, MI 48106-1346 c 2006 UmaMaheswari C. Devi ALL RIGHTS RESERVED ii Abstract UMAMAHESWARI C.
DEVI: Soft Real-Time Scheduling on Multiprocessors. (Under the direction of Prof.) The design of real-time systems is being impacted by two trends. First, tightly-coupled multiprocessor platforms are becoming quite common. This is evidenced by the availability of affordable symmetric shared-memory multiprocessors and the emergence of multicore ar- chitectures.
Second, there is an increase in the number of real-time systems that require only soft real-time guarantees and have workloads that necessitate a multiprocessor. Examples of such systems include some tracking, signal-processing, and multimedia systems. Due to the above trends, cost-effective multiprocessor-based soft real-time system designs are of growing importance. Most prior research on real-time scheduling on multiprocessors has focused only on hard real-time systems.
In a hard real-time system, no deadline may ever be missed. To meet such stringent timing requirements, all known theoretically optimal scheduling algorithms tend to preempt process threads and migrate them across processors frequently, and also impose certain other restrictions. Hence, the overheads of such algorithms can significantly reduce the amount of useful work that is accomplished and limit their practical implementation. On the other hand, non-optimal algorithms that are more practical suffer from the drawback that their validation tests require workload restrictions that can approach roughly 50% of the available processing capacity.
Thus, for soft real-time systems, which can tolerate occasional or bounded deadline misses, and hence, allow for a tradeoff between timeliness and improved processor utilization, the existing scheduling algorithms or their validation tests can be overkill. The thesis of this dissertation is: Processor utilization can be improved on multiprocessors while providing non-trivial soft real-time guarantees for different soft real-time applications, whose preemption and migration overheads can span different ranges and whose tolerances to tardiness are different, by designing new algorithms, simplifying optimal algorithms, and iii developing new validation tests. The above thesis is established by developing validation tests that are sufficient to provide soft real-time guarantees under non-optimal (but more practical) algorithms, designing and analyzing a new restricted-migration scheduling algorithm, determining the guarantees on timeliness that can be provided when some limiting restrictions of known optimal algorithms are relaxed, and quantifying the benefits of the proposed mechanisms through simulations. First, we show that both preemptive and non-preemptive global earliest-deadline-first(EDF) scheduling can guarantee bounded tardiness (that is, lateness) to every recurrent real-time task system while requiring no restriction on the workload (except that it not exceed the available processing capacity).
The tardiness bounds that we derive can be used to devise validation tests for soft real-time systems that are EDF-scheduled. Though overheads due to migrations and other factors are lower under EDF (than under known optimal algorithms), task migrations are still unrestricted. This may be unappealing for some applications, but if migrations are forbidden entirely, then bounded tardiness can- not always be guaranteed. Hence, we consider providing an acceptable middle path between unrestricted-migration and no-migration algorithms, and as a second result, present a new algorithm that restricts, but does not eliminate, migrations.
We also determine bounds on tardiness that can be guaranteed under this algorithm. Finally, we consider a more efficient but non-optimal variant of an optimal class of algo- rithms called Pfair scheduling algorithms. We show that under this variant, called earliest- pseudo-deadline-first (EPDF) scheduling, significantly more liberal restrictions on workloads than previously known are sufficient for ensuring a specified tardiness bound. We also show that bounded tardiness can be guaranteed if some limiting restrictions of optimal Pfair algo- rithms are relaxed.
The algorithms considered in this dissertation differ in the tardiness bounds guaranteed and overheads imposed. Simulation studies show that these algorithms can guarantee bounded tardiness for a significant percentage of task sets that are not schedulable in a hard real-time sense. Furthermore, for each algorithm, conditions exist in which it may be the preferred choice. iv Acknowledgments My entry to graduate school and successful completion of this dissertation and the Ph.
program are due to the confluence of some fortuitous happenings, and the support and goodwill of several people. The following is my attempt at acknowledging everyone I am indebted to. I am profoundly grateful to my advisor, Jim Anderson, for educating and guiding me over the past few years with great care, enthusiasm, and patience. Though I can fill pages thanking Jim, I will limit to only a couple of paragraphs.
Foremost, I am thankful to Jim for making me consider doing a Ph. and taking me under his care when I decided to go for it. Ever since, it has been an extreme pleasure and a privilege working for Jim and learning from him. Jim reposed a lot of confidence in me, which, I should confess, was at times overwhelming, and gave me enormous freedom in my work, all the while ensuring that I was making adequate progress.
He helped relieve much of the tedium, assuage my apprehensions, boost my self-esteem, and make the whole endeavor a joy by being readily accessible, letting me have his undivided attention most of the time I walked in to his office, offering sound and timely advice, and when needed, suggesting corrective measures. His willingness for short, impromptu discussions — over a half-baked idea, or a new result, a fresh insight, or a concern, or just a recently-read paper — and provide his perspective, was much appreciated. I cannot help remarking that I have been amazed many a time at Jim’s sharpness of mind and intellect, ability to effectively balance conflicting demands under various circumstances, thoroughness, sense of humor, and above all, genuine care and concern for his students. I would like to thank Jim in particular for being patient with some of my sloppy writing, getting those fixed, and in the process, teaching me to write.
His prompt and careful feedback on drafts served as a catalyst that accelerated writing and is perhaps a reason why his students tend to write the long dissertations that they are known for! Thanks are also due to Jim for his phenomenal support, which far exceeded what anyone can ever ask for, when I was in the academic job market. Finally, I cannot omit mentioning the numerous conference trips, five of which were to Europe, which Jim sponsored, and which have helped in widening my v perspective on several aspects. I feel honored to have had some other respected researchers also take the time to serve on my committee. In this regard, thanks are due to Sanjoy Baruah, Kevin Jeffay, Daniel Mossé, Ketan-Mayer Patel, and Jasleen Kaur.
I am thankful to my entire committee for their feedback on my work and their flexibility in accommodating my requests while scheduling proposals and exams. Profound thanks are due to Sanjoy for his support and encouragement during my stay here. Sanjoy’s work has inspired me a lot and he has influenced me to a good extent. Coincidentally, it turns out that but for Sanjoy, I would not have received admission to UNC! Special thanks are also due to Kevin for his encouragement and his concern and efforts that we receive a well-rounded education, and to Daniel for his detailed comments on my dissertation and taking the time to fly in and attend my defense in person.
I am additionally indebted to Sanjoy, Kevin, and Daniel for writing me reference letters. Ketan and Jasleen have also been very supportive overall, and special thanks to Jasleen for her friendship and for sharing some of her interviewing experiences. Thanks also go to IBM, and, in particular, to Andy Rindos, for their Ph. fellowship, which funded my final two years of study.
Giuseppe Lipari and Al Mok wrote me reference letters, which is gratefully acknowledged. I am thankful to the entire faculty of UNC’s computer science department for the congenial and stimulating atmosphere that they help create. Special thanks to everyone from whom I have taken some excellent courses, and to Profs. Gary Bishop, Dinesh Manocha, Russ Taylor, and Henry Fuchs for willingly taking the time to help me acquire some academic-job interviewing skills.
I owe it to Prof. David Stotts for funding my first year of study. My work has benefitted to a good extent from the weekly real-time lunch meetings and the interactions I have had with past and present real-time systems students. I am grateful to Anand Srinivasan and Phil Holman for patiently clarifying some of my misconceptions during my formative days and helping me with my ramp up.
The foundation for much of my work was laid by Anand in his dissertation (as will be evidenced by the numerous references), and I am thankful to both Anand and Phil for setting high standards in research and writing. Special thanks are due to Shelby Funk for her friendship and moral support. I am also very thankful for the support, friendship, and constructive criticism that I have received from Aaron Block, Nathan Fisher, John Calandrino, Hennadiy Leontyev, Abhishek Singh, Vasile Bud, Sankar Vijayaraghavan, Mithun Arora, and Billy Saelim. Special thanks go to Aaron, John, Hennadiy, and Vasile for their cooperation when we co-authored papers.
Thanks are vi also due to the following DiRT friends: Jay Aikat, Sushanth Rewaskar, and Alok Shriram. I am especially thankful to Jay for her overall support and for taking the trouble to attend several of my practice talks and offer constructive feedback. I would like to take this opportunity to extend my thanks to the administrative and tech- nical staff of the computer science department, as well, for providing us with an effective work environment, and for their readiness and cheer in attending to our needs. Special thanks in this regard go to Janet Jones, Karen Thighpen, Tammy Pike, Sandra Neely, Murray Anderegg, Charlie Bauserman, Linda Houseman, and Mike Stone.
I am fortunate to have been blessed with a loving and supportive family, who repose great trust in me despite not entirely approving my ways. I owe it to my mother and late grandfathers for instilling in me a passion for learning, and to my father for his pragmatism and for enlivening even mundane things through his wit and sense of humor. I am thankful to my sister and brother-in-law for their affection, and to my brother for his friendship and being someone I can turn to for almost anything. I am also thankful to my mother-in-law for her concern for me and her complete faith in me despite not knowing what I really do.
Above all, I am indebted in no small measure to my husband for having endured a lot during the past five years with only a few complaints. He put up with separation for several months, leftover food, and at times, an unkept home. But for his cooperation, patience, love, and faith, I would not have been able to continue with the Ph. program, let alone complete it successfully.
I owe almost everything to him and hope to be able to repay him in full in the coming years. Finally, I am thankful to God Almighty for the turn of events that led to this least expected but valuable and rewarding phase of my life: most of what happened, starting with how I applied to grad school, was by chance and not due to any careful planning on my part. vii Table of Contents List of Tables xiii List of Figures xiv List of Abbreviations xx Chapters 1 Introduction 1 1.