International Journal of Scientific & Engineering Research, Volume 5, Issue 7, July-2014 311

ISSN 2229-5518

Fuzzy Scheduling Algorithm for Real –Time multiprocessor system

Nirmala H, Dr.Girijamma H A

Abstract:In a multiprocessor environment scheduling is very essentially done with greater challenges. Researchers are in the edge of finding so- lutions to these challenges. Scheduling is the art of allocating limited resources to competing tasks over time. A feasible schedule satisfies the constraints that are associated with any particular set of tasks and resources. So as to improve the performance of the . The problem is generally NP-Complete and is not easily solvable. Many techniques are applied like Fuzzy and Genetic algorithms. In this paper we are proposed a sched- uling algorithm to real time tasks using fuzzy technique.

Index Terms—: Real-time systems, Fuzzy Inference system, Fuzzifying, Defuzzifying, CPU time, Deadline, Communication Overhead.

1 INTRODUCTION

——————————  ——————————

Real-time systems are the “information processing sys

tems where the system responds to input stimuli within a finite and specified period”. In these systems the correctness of a computational units and the time at which results are produced is very important.
Real-time systems are essential to industrialized infrastructure such as command and control, process control, flight control, space shuttle avionics, air traffic control systems etc. [1, 4]. Such a system must react to the requests within a fixed amount of time which is called deadline. In general, real-time systems can be categorized into two important groups: hard real-time systems and soft real-time systems. In hard real-time systems, tasks need to follow strict adherence to deadline con- straints. On the other hand in soft real-time systems missing some deadlines is tolerable. Tasks can be classified as periodic or sporadic. A periodic task is a kind of task that occurs at regular intervals, and an aperiodic task occurs unpredictably. The time interval between the arrivals of two consecutive re- quests in a periodic task is called period [1].
In a multiprocessor system, the limited resources consist of one or more processors which can be identical or distinct with respect to function and speed. Real –time tasks are character- ized by their computation time, ready time, and deadline, etc [21]Real-time scheduling of periodic tasks on multiprocessors can be either on homogeneous or heterogeneous processors. Example algorithms on homogeneous are Rate monotonic (RM) and Earliest deadline first (EDF). The two main ap- proaches for all the ready tasks are placed in a queue and sorted based on priority. The task with the highest priority, which is first

————————————————

• Nirmala H is currently pursuing Ph.Degree program inComputer Science

& engineering ,Dept of CSE, RNSIT,Bangalore,Karnataka, India,. E- mail:hnirmala@sjbit.edu.in

• Co-Author Dr.Girijamma H A, Professor , Dept of CSE , RNSIT, Banga- lore, girijakasal@gmail.com

in the queue, will be selected by the scheduler and will be exe- cuted on one of the processors. During the execution task may be preempted or migrated if necessary. In partitioning, each task is assigned to a single processor, on which each of its jobs will be execute and are scheduled independently
The rest of the paper depicts the journey as follows: Section 2
describes literature survey, in section 3 proposed models is
described and conclusion section 4 gives discussion about fu-
ture work.

2. LITERATURE SURVEY

The degree of satisfaction can be used as a parameter for mak- ing a decision, which is achieved by using Fuzzy technology. Fuzzy logic is an alternate to Boolean logic, the degree of truth is applied to observe the imprecise modes of reasoning that plays an important role in decision making ability in the at- mosphere of uncertainty and imprecision.
Fuzzy Inference System (FIS) [2] consists of three steps: input
step, a processing stage, and an output step. The input stage
receives inputs like deadline, execution time, response time and so on, and maps these to appropriate membership func- tions and truth values. In the processing step each appropriate rule is invoked and the corresponding result is generated. Then results are combined so that it will be given as an input to the output stage. In output stage converts the combined result is converted back into a specific value.
The membership function of a fuzzy inference system depicts
a curve which defines how each point in the input space is
mapped to a membership value or a degree of truth value be-
tween 0 and 1.
The most common shapes of a membership function are trian-
gle, trapezoidal and bell curves.
The processing stage of an inference engine is based on a col- lection of logical rules in the form of IF-THEN statements where the IF part is called the "antecedent" and the THEN part is called the "consequent". The knowledge base of the system has dozens of rules. An example of fuzzy IF-THEN rule is: IF deadline is catastrophic then priority is high, in which dead- line and priority are linguistics variables and critical and high

International Journal of Scientific & Engineering Research, Volume 5, Issue 7, July-2014 312

ISSN 2229-5518

are linguistics terms. Each linguistic term corresponds to membership functions. The basic five steps applied in a fuzzy inference engine [10] are as follows:
• Fuzzifying inputs
• Applying fuzzy operators
• Applying implication methods
• Aggregating outputs
• Defuzzifying outputs
Fuzzifying the input is the process of determining the degree to which they belong to each of the appropriate fuzzy sets via membership functions. Once the inputs have been fuzzified the degree to which each part of the antecedent has been satis- fied for each rule is known. If the antecedent of a given rule has one or more part, the fuzzy operator is applied to obtain one value that represents the result of the antecedent for that rule. The implication function modifies the output fuzzy set to the degree specified by the antecedent. Here decisions are based on the testing of all the rules in an inference system, the results from each rule must be combined in order to make a decision. In aggregation the output of each fuzzy set that rep- resents the output of each rule is combined into a single fuzzy set. The input for the defuzzification process is aggregated output fuzzy set and the output is a single value. There are two common inference processes. The first one is called Mamdani's fuzzy inference method proposed by Ebrahim Mamdani [16] and the second one is Takagi-Sugeno-Kang, or simply Sugeno [17], method of fuzzy inference. These two methods are the same in many aspects, such as the procedure of fuzzifying the inputs and fuzzy operators. The main differ- ence between Mamdani and Sugeno is that the Sugeno’s out- put membership functions are either linear or constant but Mamdani’s inference expects the output membership func- tions to be fuzzy sets. Sugeno’s method has three advantages. First, it is computationally efficient, which is very important for real-time systems. Second, it works well with optimization and adaptive techniques. These adaptive techniques provide a method for the fuzzy modeling procedure to extract proper knowledge about a data set, in order to compute the member- ship function parameters that allow the fuzzy inference sys- tem to track the given input/output data. The third, ad- vantage of Sugeno type inference is that it is well-suited to mathematical analysis.

3. THE PROPOSED MODEL

In the proposed model, the input stage consists of three lin- guistic variables i.e. CPU time, deadline and communication overhead, as shown in Fig1. CPU time is the amount of time a task requires to execute a task. Deadline represents the final time limit within which task has to complete its work. Com- munication overhead is the time, how much a task spending in communicating with other task so has to complete its work. If the communication overhead is close to 1 then priority is low and if it is close to 0 then priority is high.
Fig.1.The proposed Fuzzy Inference Engine
Membership functions describe the degree to which each in- put parameter represents its association. Linguistic variables are assigned to each input parameter, to represent this associa- tion. CPU time can be classified as low, medium and high. Similarly communication overhead is defined in the same way. However deadline is defined as tolerable, sensitive and catastrophic as depicted in Fig.2. Fig.3 and Fig.4.

Fig.2. Fuzzy Set Corresponding to CPU time

Fig.3.Fuzzy Set Corresponding to Communication over- head

Fig.4. Fuzzy Set Corresponding to Deadline

International Journal of Scientific & Engineering Research, Volume 5, Issue 7, July-2014 313

ISSN 2229-5518

Fuzzy rules combine these parameters as they are connected in real worlds. Some of these rules are as follows:
IF (CPU time is low), (Communication overhead is low) and
(Deadline is Tolerable), THEN priority is medium
IF (CPU time is medium), (Communication overhead is high)
and (Deadline is Tolerable), THEN priority is low
IF (CPU time is high),(Communication overhead is medium)
and (Deadline is catastrophic), THEN priority is high
In our proposed algorithm as given below, a newly arrived task will be added to input queue, which consists of tasks that has not yet been assigned to processor.
Loop
For each processor in the multiprocessor environment do the following:
1. For each ready task, feed its CPU time, communica- tion overhead and Deadline into the inference engine. Consider the output of inference system as priority of task T.
2. Execute the task with highest priority until a schedul- ing event occurs (a running task completes , a new task arrives )
3. Update the system states.

4. EXPERIMENTAL RESULTS

If we choose more rules and member functions it will directly affects the overall system accuracy, even though performance of the system can be made better when number of rules are reduce. Technique like genetic algorithm for choosing rules from a set of rules may be considered, however this approach can discussed in future. The above considered rules decision surface and member functions is illustrated in the Fig.6

Fig.6. The decision surface Corresponding to Inference rules.

5. CONCLUSION

The scheduling algorithm proposed in the paper considered with deeper simulation by having more rules. The Overall system performance can be further made it better using hybrid technique which may be combine approaches of fuzzy and genetic techniques.

REFERENCES

[1] Mojtaba Sabeghi, Mahmoud Naghibzadeh , A Fuzzy Algo- rithm for Real-Time Scheduling of Soft Periodic Tasks, IJCSNS International Journal of Computer Science and Net- work Security, VOL.6 No.2A, February 2006
[2] Ramamritham K., Stankovic J. A., Scheduling algorithms and operating systems support for real-time systems, Proceed- ings of the IEEE, Vol. 82, No. 1, pp. 55--67, January 1994.
[3] Probir Roy, Md. Mejbah U Alam and Nishita Das, Heuristic based task scheduling in multiprocessor system with Genetic algorithm by choosing the eligible processor, International Journal of Distributed and Parallel Systems (IJDPS) Vol.3, No.4, July 2012
[4] Robert T. Casey, A Survey of Fuzzy Scheduling Algo- rithms, EEL 270-RTOS, Spring 2007
[5] Sabeghi M., Naghibzadeh M., Taghavi T., A Fuzzy Algo-
rithm for Real-Time Scheduling of Soft Periodic Tasks on Mul-
tiprocessor Systems, IADIS International Conference on Ap-
plied Computing, February 2006
[6] Vahid Majid Nezhad, Habib Motee Gader and Evgueni Efimov, A Novel Hybrid Algorithm for Task Graph Schedul- ing, IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 2, March 2011
[7] Sagar Gulati , Neha Arora , KamalDeep, A Fuzzy Ap- proach for Task scheduling in Real Time Distributed System, International Journal of Research in Engineering & Applied Sciences, Vol 2, Issue 2 ISSN: 2249-3905,February 2012
[8] Liu C. L., Layland J. W., Scheduling Algorithms for Multi- programming in a Hard Real-Time Environment. Journal of the ACM, 20(1):46-61, 1973.
[9] Sabeghi M., Naghibzadeh M., Taghavi T., "Scheduling Non-Preemptive Periodic Tasks in Soft Real-Time Systems using Fuzzy Inference", 9th IEEE International Symposium on Object and component-oriented Real-time distributed Compu- ting (ISORC), April 2006
[10] Sabeghi M., Deldari H., A Fuzzy Algorithm for Schedul- ing Periodic Tasks on Multiprocessor Soft Real- Time Systems,

International Journal of Scientific & Engineering Research, Volume 5, Issue 7, July-2014 314

ISSN 2229-5518

IASTED International Conference on Modeling and Simula- tion, May 2006
[11] Goossens J., Richard P., Overview of real-time scheduling problems, Euro Workshop on Project Management and Scheduling, 2004
[12] Hong J., Tan X., Towsley D., A Performance Analysis of Minimum Laxity and Earliest Deadline Scheduling in a Real- Time System, IEEE Trans. on Comp., Vol. 38, No. 12, Dec. 1989
[13] Sha, L. and Goodenough, J. B., Real-Time Scheduling
Theory and Ada, IEEE Computer, Vol. 23, No. 4, pp. 53-62
April 1990.
[14] Wang Lie-Xin, A course in fuzzy systems and control, Prentice Hall, Paperback, Published August 1996.
[15] Andersson B., Jonsson J. Fixed-priority preemptive multi- processor scheduling: to partition or not to partition, Seventh International Conference on Real-Time Computing Systems and Applications (RTCSA'00), 2000
[16] Mamdani E.H., Assilian S., An experiment in linguistic synthesis with a fuzzy logic controller, International Journal of Man-Machine Studies, Vol. 7, No. 1, pp. 1-13, 1975.
[17] Sugeno, M., Industrial applications of fuzzy control, Else- vier Science Inc., New York, NY, 1985.
[18] Sabeghi M., Naghibzadeh M., Taghavi T., A Fuzzy Algo- rithm for Scheduling Soft Periodic Tasks in Preemptive Real- Time Systems, International Joint Conferences on Computer, Information, and Systems Sciences, and Engineering (CISSE),
2005
[19] Jaewon Oh, Chisu Wu Genetic-algorithm-based real-time task scheduling with multiple goals, October 2002, The Journal of Systems and Software 71 (2004) 245–258
[20] Laura E Jackson George N Rouskas, Deterministic Preemptive Scheduling of Real-Time tasks. May 2002,A tech- nical report.
[21] Fredrik Lindh, Thomas Otnes, Jessica Wennerström, Scheduling Algorithms for Real-Time Systems.
[22] Handbook of Scheduling Algorithms, models and per- formance analysis By Joseph Y-T.Leung.