Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

Fine tuning the scheduling of tasks through a genetic algorithm: application to Posix1003.1b compliant systems

Fine tuning the scheduling of tasks through a genetic algorithm: application to Posix1003.1b compliant systems

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IEE Proceedings - Software — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

Most of today's commercial real-time operating systems (RTOSs) offer multiple scheduling policies which are applied on a per-process basis. The best illustrations of this are the Posix1003.1b compliant OSs that provide two real-time scheduling policies, namely sched_fifo and sched_rr, which under some limited hypotheses are respectively the equivalent of fixed priority pre-emptive (FPP) and round-robin (RR). In the field of processor scheduling, schedulability analysis has been studied extensively and the problem of assessing the schedulability of multi-policy systems has recently been addressed by Migge et al. When FPP and RR are used in conjunction, no optimal priority/policy assignment, such as Audsley's algorithm for FPP, is known, a fortiori when other criteria besides feasibility are considered. Because of the size of the solution space, an exhaustive search is not possible; an optimisation technique is required. A schedulability analysis provides valuable help for the application designer but it simply asserts whether a given configuration is feasible or not; in general it does not propose any feasible configurations (i) and, as stated by Gerber and Hong (1997) ‘it can rarely help to tune the system (ii), which is the inevitable next step’. To address problems (i) and (ii), an approach is proposed using a genetic algorithm to best set task priorities and scheduling policies, according to a chosen criterion, on Posix1003.1b uniprocessor systems. Moreover, it is shown that the use of RR, in conjunction with FPP, may improve the schedulability as well as the satisfaction of additional application-dependent criteria.

References

    1. 1)
    2. 2)
      • Gerber, R., Hong, S.: `Slicing real-time programs for enhanced schedulability', UMD CS-TR-3477, UMIACS TR 95-62, Technical, May 1995.
    3. 3)
      • J.H. Holland . (1975) Adaptation in natural and artificial systems.
    4. 4)
      • N. Abramowitz , I. Stegun . (1965) Handbook of mathematical functions.
    5. 5)
      • Nakano, R., Yamada, T.: `Conventional genetic algorithm for job shop problems', Proceedings of the 4th Int. Conf. on Genetic Algorithms, 1991, San Mateo, USA, p. 474–479.
    6. 6)
    7. 7)
      • Oliver, I.M., Smith, G.J., Holland, J.R.C.: `A study of permutation crossover operators on the travelling salesman problem', Proceedings of the 2nd International Conference on Genetic Algorithms, 1987, Hillsdale, USA, p. 224–230.
    8. 8)
      • Navet, N., Migge, J.: `Fine tuning the scheduling of tasks on posix1003.1b compliant systems', 3730 INRIA, Technical, July 1999, available at http://www.loria.fr/~nnavet/.
    9. 9)
      • J.Y.T. Leung , J. Whitehead . On the complexity of fixed-priority scheduling of periodic real-time tasks. Perform. Eval. , 4 , 237 - 250
    10. 10)
      • R. Gerber , S. Hong . Slicing real-time programs for enhanced schedulability. ACM Trans. Program. Lang. Syst. , 3 , 525 - 555
    11. 11)
      • Y.K. Kwok , I. Ahmad . Efficient scheduling of arbitrary task graphs to multiprocessors using a parallel genetic algorithm. J. Parallel Distrib. Comput.-Special Issue on Parallel Evolutionary Computing , 1 , 58 - 77
    12. 12)
    13. 13)
      • J.A. Michalewicz . (1992) Genetic algorithm+data structure=evolution program.
    14. 14)
      • K. Tindell , A. Burns , A.J. Wellings . Allocating hard real time tasks (an np problem made easy). Real-Time Syst. , 2 , 145 - 165
    15. 15)
      • F. Baccelli , P. Brémaud . (1994) Elements of queuing theory.
    16. 16)
      • Koopman, P., Sung, J., Dingman, C., Siewiorek, D.: `Comparing operating systems using robustness benchmarks', Presented at the Symposium on Reliable Distributed Systems, October 1997, Durham, USA, p. 72–79.
    17. 17)
      • Beaty, S.J.: `Genetic algorithm versus tabu search for instruction scheduling', International Conference on Neural Networks and Genetic Algorithms, April 1993, Innsbruck, Austria.
    18. 18)
      • Kidwell, M.D.: `Using genetic algorithms to schedule distributed tasks on a bus-based system', Proceedings of 5th International Conference on Genetic Algorithms, 1993, Urbana-Champaign, USA, p. 368–374.
    19. 19)
      • Davis, L.: `Job-shop scheduling with genetic algorithms', Proceedings of the First Int. Conf. on Genetic Algorithms, 1985, Hillsdale, USA, p. 136–140.
    20. 20)
      • Djerid, L., Portmann, M.-C., Villon, P.: `Performance analysis of previous and new proposed cross-over genetic operators designed for permutation scheduling problem', Proceedings of the International Conference on Industrial Engineering and Production Management, April 1995, Marrakech, Maroc, p. 487–497.
    21. 21)
    22. 22)
      • `Information Technology—Portable Operating System Interface (POSIX)—Part I : System Application : Program Interface', (ISO/IEC): ‘9945-1:1996 (ISO/IEC)[IEEE/ANSI Std 1003.1 1096 Edition], 1996.
    23. 23)
      • Migge, J.M.: `Scheduling of recurrent tasks on one processor: A trajectory based model', 1999, PhD, University of Nice Sophia-Antipolis, available at http://ww.migge.net/jorn/thesis/.
    24. 24)
      • M. Schwehm , T. Walter . Mapping and scheduling by genetic algorithms. Lect. Notes in Comput. Sci. , 833 - 841
    25. 25)
      • D.E. Goldberg . (1999) Genetic algorithms in search, optimization and machine learning.
    26. 26)
      • Salles, F., Arlat, J., Fabre, J.-C.: `Can we rely on COTS microkernels for building fault-tolerant systems', Proceedings of the 6th IEEE Computer Society Workshop on Future Trends of Distributed Computing Systems, October 1997, Tunis, Tunisia, p. 189–194.
    27. 27)
      • M.H. Klein , T. Ralya , B. Pollak , R. Obenza , M.G. Harbour . (1993) A practitioner's hand-book far real-time analysis.
    28. 28)
      • Macos, D., Mueller, F.: `Integrating gnat/gcc into a timing analysis environment', 10thEUROMICRO Workshop on Real Time Systems, 17–19 June 1998, Berlin, Germany, WIP Session.
    29. 29)
    30. 30)
      • Beaty, S.J., Colcord, S., Sweany, P.: `Using genetic algorithms to fine-tune instruction-scheduling heuristics', 2ndInternational Conference on Massively Parallel Computing Systems (MPCS'96), May 1996, Ischia, Italy.
    31. 31)
      • L. Davis . (1991) Handbook of genetic algorithms.
    32. 32)
      • B.O. Gallmeister . (1995) Programming for the Real World—Posix4.
    33. 33)
      • Falkenauer, E., Bouffoix, S.: `A genetic algorithm for job shop', Proceedings of the IEEE Int. Conf. on Robotics and Automation, 1991, Sacramento, USA, p. 824–829.
    34. 34)
      • M.-C. Portmann , A. Artiba , S.E. Elmahgraby . Scheduling methodology: Optimization and compu-search approaches, Production and Scheduling of Manufacturing System.
    35. 35)
      • DiNatale, M., Stankovic, J.A.: `Applicability of simulated annealing methods to real-time scheduling and jitter control', Proceedings of the 16th IEEE Real-Time Systems Symposium, December 1995, Pisa, Italy, also available at http://retis.sssup.it/papers/abstracts.html.
    36. 36)
      • Audsley, N.C.: `Optimal priority assignment and feasibility of static priority tasks with arbitrary start times', YCS164, Technical, November 1991.
    37. 37)
      • Goldberg, D.E., Lingle, R.: `Alleles, loci, and the travelling salesman problem', Proceedings of the 1st Int. Conf. on Genetic Algorithms, 1985, Hillsdale, USA, p. 154–159.
    38. 38)
      • Gerber, R.: `Languages and tools for real-time systems: Problems, solutions and opportunities', UMD CS-TR-3362, UMIACS-TR-94-117, Technical, October 1994.
    39. 39)
      • J. Migge , A. Jean-Marie , N. Navet . Timing analysis of compound scheduling policies: Application to posix1003.1b. J. Sched.
    40. 40)
      • D. Thiel . Un algorithme génétique pour la résolution de problèmes d'affectation quadratique comparé aux performances du recuit simulé. RAIRO-APII-JESA J. Eur. Syst. Autom. , 9 , 1541 - 1564
    41. 41)
      • Dussa-Zieger, K.: `Task scheduling on configurable parallel systems by genetic algorithms', Proceedings of Conference on Telecommunication, distribution, parallelism (TDP'96), July 1996, p. 485–494.
    42. 42)
      • Beaty, S.J., Whitley, J., Johnson, G.: `Motivation and framework for using genetic algorithms for microcode compaction', Presented at the 23rd Annual Workshop in Microprogramming and Microarchitecture (MICRO-23), December 1990, Orlando, USA.
    43. 43)
    44. 44)
      • T. Barret . How to write an rtos—a guide for anyone pondering the “make-or-buy” decision. Real-Time Mag. , 3 , 43 - 45
    45. 45)
      • Cantù-Paz, E.: `A summary of research on parallel genetic algorithms', 95007, Technical, 1995.
    46. 46)
      • C.L. Liu , J.W. Layland . Scheduling algorithms for multiprogramming in hard real-time environment. J. ACM , 1 , 40 - 61
    47. 47)
      • J. Moses . Is posix appropriate for embedded systems. Embedded Syst. Program. , 7
    48. 48)
      • J.A. Stankovic , A. Burns , K. Jeffay , M. Jones , G. Koob , I. Lee , J. Lehoczky , J. Liu , A. Mok , K. Ramamritham , J. Ready , L. Sha , A. Van Tilborg . Strategic directions in real-time and embedded systems. ACM Comput. Surv. , 4 , 751 - 763
http://iet.metastore.ingenta.com/content/journals/10.1049/ip-sen_20030205
Loading

Related content

content/journals/10.1049/ip-sen_20030205
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address