Project Materials

RESEARCH WORKS AND MATERIALS

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

Do You Have New or Fresh Topic? Send Us Your Topic

New Fuzzy Scheduling Algorithm () for Real-Time Tasks on 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
INTRODUCTION ………………………………………………………………………….. 1
1.0 INTRODUCTION……………………………………………………………………………….1
1.1 PROBLEM STATEMENT AND RESEARCH ………………….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) ………………………….. 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.

 

Do You Have New or Fresh Topic? Send Us Your Topic 

 

 

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 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.

 

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

 

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

Not What You Were Looking For? Send Us Your Topic

INSTRUCTIONS AFTER PAYMENT

After making payment, kindly send the following:
  • 1.Your Full name
  • 2. Your Active Email Address
  • 3. Your Phone Number
  • 4. Amount Paid
  • 5. Project Topic
  • 6. Location you made payment from

» Send the above details to our email; [email protected] or to our support phone number; (+234) 0813 2546 417 . As soon as details are sent and payment is confirmed, your project will be delivered to you within minutes.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Advertisements