This is an extension of existing fuzzy scheduling algorithms, to schedule real-time on multiprocessor .
The existing fuzzy scheduling algorithm was extended in order to have a better at higher system load. The task scheduling used in this research work are; arrival time, computation time, and deadline which are inputs to the fuzzy inference system.
The outputs are the runtime priorities which are used to schedule tasks in a priority (ready) queue for execution on multiprocessor. The performance of the new fuzzy scheduling algorithm was compared with the existing fuzzy scheduling algorithm.
Results show that the new fuzzy algorithm has a better performance than the existing algorithm at higher system load; this is as a result of minimum response time, turnaround time and lower number of tasks that missed their deadline.
Table Of Contents
Declaration……………………………i
Certification……………………………ii
Dedication……………………………….iii
Acknowledgement…………………….. iv
Abstract………………………………………. v
Table of Contents……………………….. vi
List of Tables………………………………..ix
List of Figures………………………………. x
List of Appendices…………………………xi
List of Abbreviations……………………..xii
CHAPTER ONE
GENERAL INTRODUCTION………………………. 1
- INTRODUCTION………………………. 1
- PROBLEM STATEMENT AND RESEARCH MOTIVATION…….. 2
- RESEARCH OBJECTIVES……………………………..3
- RESEARCH METHODOLOGY…………………………….3
- CONTRIBUTION OF THE STUDY TO KNOWLEDGE……….3
- ORGANIZATION OF THE THESIS…………………….4
CHAPTER TWO
LITERATURE REVIEW…………………………. 5
- INTRODUCTION………………………………………………………..5
- REAL-TIME SYSTEMS……………………………………………..5
- REAL-TIME SYSTEMS FEATURES……………………………7
- REAL-TIME SYSTEM SCHEDULING……………………………7
- REAL TIME SYSTEM SCHEDULING ALGORITHMS…….. 8
- MULTIPROCESSOR SCHEDULING………………10
- TASK UTILIZATION (LOAD) FACTOR…………11
- INTRODUCTION TO FUZZY LOGIC…….12
- RELATED WORKS…………………………..18
CHAPTER THREE
NEW FUZZY SCHEDULING ALGORITHM (NFSA) DESIGN…………... 23
- INTRODUCTION…………………. 23
- NEW FUZZY SCHEDULING ALGORITHM (NFSA) MODEL……………. 23
- Defining the Inputs/Output Membership Function for NFSA…… 25
- Set-up Fuzzy Rule Base for NFSA………………28
- Defuzzified the Output for NFSA…………………….. 28
- CASE ASSUMPTION……………………..32
- NFSA ARCHITECTURE………………..33
- NFSA ALGORITHM…………………….35
- FLOW CHART FOR NFSA…………….37
CHAPTER FOUR
IMPLEMENTATION AND TEST OF THE NFSA………..38
- INTRODUCTION……………………………………38
- ILLUSTRATIVE EXAMPLE………………38
- SYSTEM REQUIREMENT……………………….46
- USER INTERFACE…………………………………... 47
- RESULTS DISCUSSION AND CONCLUSION……………. 50
- Graphical Representation of Average Turnaround Time……………………… 50
- Graphical Representation of Average Response Time………………………… 52
- Graphical Representation of Number of Tasks Miss Deadline……………. 54
- PERFORMANCE CRITERIA ANALYSIS TABLE…… 56
CHAPTER FIVE
SUMMARY, CONCLUSION AND FUTURE WORKS…. 58
- SUMMARY………………………………58
- CONCLUSION………………………..58
- FUTURE WORKS…………………….59
REFERENCES…………………..60
APPENDICES…………………….64
Introduction
Background Of Study
Scheduling algorithm is more significant in a real-time system to ensure desired and predictable behaviour of a system (Sagar et al., 2012).
Scheduling is concern with the optimal allocation of resources to tasks in a specified time. Real-time systems are often embedded in most of domestic devices which are used for daily activities without our knowledge when we use the devices in which they reside.
Cars, planes and entertainment systems are just some devices in which real-time systems reside, governing the workings of that device while we do not consider that such a system exists within the chosen device.
A real-time-system is a computer system in which the key aspect of the system is to perform tasks on time, not finishing too early nor too late.
A classic example is that of the air-bag in a car; it is of great importance that the bag inflates neither too soon nor too late in orders to be of help and not be potentially harmful.
In real-time systems, all tasks have specific parameters such as execution time, deadline, arrival time, priority, etc. Modern embedded computing systems are becoming increasingly complex (Sagar et al., 2012).
Many real-time systems are soft in which missing the deadline is tolerable while some others are hard and missing deadline is catastrophic (Sabeghi et al., 2006).
Nowadays, the use of real-time multiprocessor systems is dramatically increasing. Unfortunately, little is known about how to schedule multiprocessor-based real-time systems than that for uni-processors.
References
Ascia G., Catania V., Ficili G. and Panno D. (2001). A Fuzzy Buffer Management Scheme for ATM and IP Networks, Institute of Electrical and Electronics Engineers Transactions on Computer Engineering (IEEE) INFOCOM, Anchorage, 1539-1547, Alaska.
Bashir A. (2013). Fuzzy Round Robin CPU Scheduling Algorithm. Journal of Computer Science, doi:10.3844/jcssp.2013.1079.1085, 1079-1085.
Behera H., Ratikanta P., Priyabrata M. (2012). An Improved Fuzzy-Based CPU Scheduling (IFCS) Algorithm for Real Time Systems. International Journal of Soft Computing and Engineering (IJ
SCE), 2(1), ISSN: 2231-2307.Bindi C. (2013). Fuzzy Logic Membership Function. Retrieved March 13, 2014, from http://www.bindichen.co.uk/post/AI/fuzzy-inference-membership-function.html
Bogdan C., Wong C., Jason N. and Clifford S. (2005). Group ratio round-robin: Proportional share scheduling for uniprocessor and multiprocessor systems. In Proceedings of the USENIX Annual Technical Conference, 337–352, Anaheim, California.
Bovet D. and Marco C. (2005).Understanding the Linux Kernel. O’Reilly Media, Inc., 3rd edition. 266-274, ISBN:0-596-00565-2.
Be the first to comment