Project Materials

New Fuzzy Scheduling Algorithm (NFSA) for Real-Time Tasks on Multiprocessor Systems

ABSTRACT

This thesis is an extension of existing fuzzy scheduling algorithms, to schedule real-time tasks on multiprocessor systems. The existing fuzzy scheduling algorithm was extended in order to have a better performance at higher system load.

The task scheduling parameters 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 …………………………………………………………………………………………….. 1
GENERAL INTRODUCTION ………………………………………………………………………….. 1
1.0 INTRODUCTION……………………………………………………………………………….1
1.1 PROBLEM STATEMENT AND RESEARCH MOTIVATION ………………….2
1.2 RESEARCH OBJECTIVES ………………………………………………………………….3
1.3 RESEARCH METHODOLOGY ……………………………………………………………3
1.4 CONTRIBUTION OF THE STUDY TO KNOWLEDGE ………………………….3
1.5 ORGANIZATION OF THE THESIS ……………………………………………………..4
CHAPTER TWO ……………………………………………………………………………………………. 5
LITERATURE REVIEW …………………………………………………………………………………. 5
2.0 INTRODUCTION……………………………………………………………………………….5
2.1 REAL-TIME SYSTEMS ………………………………………………………………………5
2.2 REAL-TIME SYSTEMS FEATURES ……………………………………………………7
2.3 REAL-TIME SYSTEM SCHEDULING …………………………………………………7
2.4 REAL TIME SYSTEM SCHEDULING ALGORITHMS ………………………….8
2.5 MULTIPROCESSOR SCHEDULING …………………………………………………. 10
2.6 TASK UTILIZATION (LOAD) FACTOR ……………………………………………. 11
2.7 INTRODUCTION TO FUZZY LOGIC ……………………………………………….. 12
2.7.1 Crisp Set Theory ………………………………………………………………………… 13
2.7.2 Fuzzy Set Theory ……………………………………………………………………….. 13
2.7.3 Membership Functions ………………………………………………………………… 14
2.7.4 Linguistic Variables ……………………………………………………………………. 15
2.7.5 Fuzzy Logic Systems (FLS) …………………………………………………………. 16
2.8 RELATED WORKS …………………………………………………………………………. 18
CHAPTER THREE ……………………………………………………………………………………….. 23
NEW FUZZY SCHEDULING ALGORITHM (NFSA) DESIGN………………………….. 23
3.0 INTRODUCTION…………………………………………………………………………….. 23
3.1 NEW FUZZY SCHEDULING ALGORITHM (NFSA) MODEL ……………… 23
3.1.1 Defining the Inputs/Output Membership Function for NFSA ……………… 25
3.1.2 Set-up Fuzzy Rule Base for NFSA ………………………………………………… 28
3.1.3 Defuzzified the Output for NFSA ………………………………………………….. 28
3.2 CASE ASSUMPTION ………………………………………………………………………. 32
3.3 NFSA ARCHITECTURE…………………………………………………………………… 33
3.4 NFSA ALGORITHM ………………………………………………………………………… 35
3.5 FLOW CHART FOR NFSA ………………………………………………………………. 37
CHAPTER FOUR …………………………………………………………………………………………. 38
IMPLEMENTATION AND TEST OF THE NFSA …………………………………………….. 38
4.0 INTRODUCTION…………………………………………………………………………….. 38
4.1 ILLUSTRATIVE EXAMPLE …………………………………………………………….. 38
4.1.1 Performance Evaluation Metric of EFA ………………………………………….. 40
4.1.2 Performance Evaluation Metric of NFSA ……………………………………….. 43
4.1.3 Comparing NFSA with EFA ………………………………………………………… 46
4.2 SYSTEM REQUIREMENT ……………………………………………………………….. 46
4.3 USER INTERFACE ………………………………………………………………………….. 47
4.4 RESULTS DISCUSSION AND CONCLUSION …………………………………… 50
4.4.1 Graphical Representation of Average Turnaround Time. …………………… 50
4.4.2 Graphical Representation of Average Response Time. ……………………… 52
4.4.3 Graphical Representation of Number of Tasks Miss Deadline …………… 54
4.5 PERFORMANCE CRITERIA ANALYSIS TABLE ………………………………. 56
CHAPTER FIVE …………………………………………………………………………………………… 58
SUMMARY, CONCLUSION AND FUTURE WORKS ……………………………………… 58
5.1 SUMMARY …………………………………………………………………………………….. 58
5.2 CONCLUSION ………………………………………………………………………………… 58
5.3 FUTURE WORKS ……………………………………………………………………………. 59
REFERENCES ………………………………………………………………………………………….. 60
APPENDICES …………………………………………………………………………………………… 64

CHAPTER ONE

GENERAL INTRODUCTION

1.0 INTRODUCTION

Scheduling algorithm is more significant in a real-time system to ensure desired and predictable behavior 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. The multiprocessor based scheduling have more computational complexity in practical algorithm which are unknown to most researchers, this open floor for new area of research in operating systems (Shahzad and Afzal, 2006).

It has been provened that finding a minimal schedule for a set of real-time tasks in multiprocessor system is a hard problem (Tanenbaum and Woodfhull, 2005). In this research fuzzy technique was introduced to schedule tasks on multiprocessors in real-time system.

Many scheduling algorithms have been studied to guarantee the time constraints of real-time. Scheduling decision of real-time algorithms is usually based on parameters which are assumed to be crisp. However, in uncertain and imprecise environment the values of these parameters are vague.

The vagueness of these parameters suggests that we make use of fuzzy logic to capture uncertainty and imprecision mode. Fuzzy scheduling approach therefore help to decide in what order the tasks should be scheduled for execution to better utilize the system and as a result reduce the chance of task’ deadline being missed.

1.1 PROBLEM STATEMENT AND RESEARCH MOTIVATION

There are many conventional approaches to scheduling algorithms to guarantee the time constraints of real-time processes but no one is absolutely ideal. Scheduling decision of these algorithms is usually based on parameters which are assumed to be crisp.

All practical real-time scheduling algorithms in multiprocessor systems present a trade-off between their computational complexity and performance. In real-time systems, tasks have to be performed correctly and timely. Finding minimal schedule in multiprocessor systems with real-time constraints is shown to a hard problem (Sheo et al., 2012).

Although some optimal algorithms have been employed in uni-processor systems, they fail when they are applied in multiprocessor systems. However, the existing algorithm has a better performance at normal system load but at overloaded condition the performance decreases.

Therefore, this research work will focus on the development and implementation of a new fuzzy algorithm for fair scheduling of real-time tasks on multiprocessor in order to improve performance of an existing system at higher system load.

1.2 RESEARCH OBJECTIVES

The specific objectives of this research are to:

i. Develop a new scheduling algorithm for real-time tasks on multiprocessor systems.

ii. Extend the existing fuzzy scheduler model using fuzzy logic techniques.

iii. Implement the new scheduling algorithm on the extended fuzzy scheduler.

iv. Evaluate performance metrics of both existing and new fuzzy scheduling algorithm on multiprocessor systems in term of turnaround time, response time and number of real-time tasks misses deadline at higher system load.

1.3 RESEARCH METHODOLOGY

This research applies fuzzy logic techniques to control the scheduling activities of multiprocessor in real-time
environment by putting into consideration all major scheduling parameters of each task. Review of related literatures on real-time systems and fuzzy logic scheduling algorithm were carried out.

The fuzzy logic techniques bring an expert skill to solve problems with imprecise data or incomplete knowledge. In each test case, the number of tasks and some of the metric parameters will be randomly generated using Poisson, uniform distribution and normal distribution (Sheo et al., 2012). Prototype software will be developed and implemented using java programming language and Netbeans editor.

1.4 CONTRIBUTION OF THE STUDY TO KNOWLEDGE

This research work uses fuzzy inference engine as a tool to model a knowledgeable decision making on how to schedule the processors to a given task in real-time environment. A fuzzy logic technique is adopted because of its capability in bringing an expert’s skill to solve problems of incomplete knowledge or imprecise data. This bring about;

i. An idea of using Fuzzy logic approach scheduling algorithm to optimized performance metrics of multiprocessor systems in real-time environment.

ii. A new concept of scheduling on multiprocessor systems.

iii. Carefully selecting scheduling parameters improves system performance with the appropriate algorithms.

1.5 ORGANIZATION OF THE THESIS

The rest of the thesis is organized as follows: the second chapter involves basic concept of real-time systems, multiprocessor scheduling, brief introduction of fuzzy logic and the review of related literature. Third chapter involves design of the new fuzzy scheduling algorithm.

System implementation and simulation results obtained from the new fuzzy scheduling algorithm are discussed in the fourth chapter. Finally the fifth chapter involves summary, conclusion and future work.