home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / realtime / 1474 < prev    next >
Encoding:
Text File  |  1992-12-22  |  4.1 KB  |  73 lines
  1. Newsgroups: comp.realtime
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!cis.ohio-state.edu!news.sei.cmu.edu!lph
  3. From: lph@sei.cmu.edu (Larry Howard)
  4. Subject: Re: Real_time systems
  5. Message-ID: <1992Dec22.103105.9044@sei.cmu.edu>
  6. Keywords: non-preemptive scheduling
  7. Sender: netnews@sei.cmu.edu (Netnews)
  8. Organization: Software Engineering Institute
  9. References: <1992Dec17.234430.18247@cbnewsm.cb.att.com> <1992Dec22.041024.25911@megadata.mega.oz.au>
  10. Date: Tue, 22 Dec 1992 10:31:05 EST
  11. Lines: 60
  12.  
  13. Andrew McRae writes:
  14.  
  15. > Preemption and priorities are a slippery slope; once you
  16. > are on them, you quickly slide down into a sticky swamp. Why?
  17. > Prioritisation implies preemption - there would be no point in
  18. > having a higher priority task if it did not preempt a lower
  19. > priority task. If you have preemption, then you have a problem
  20. > with synchronisation and locking, especially with shared data structures
  21. > such as lists and queues. Fine, you then add semaphores, messaging
  22. > and mailboxes so that you can overcome the locking problems, but
  23. > you have to ensure that preemption works properly and that
  24. > tasks do not get switched in the middle of critical sections. So you
  25. > add monitors, or have the concept of priviledge (priviledged sections
  26. > do not get switched), and then after each monitor/semaphore you have
  27. > checking for preemption... And then you find that your real time
  28. > operating system has grown too big and slow for your real time
  29. > processing needs, since it spends all its time locking and
  30. > messaging and semaphoring and preempting, so you have to
  31. > buy a bigger processor with more memory, and buy a more
  32. > expensive licence for your whiz-bang real time OS.
  33.  
  34. While preemptive scheduling admittedly comes with an assortment of challenges,
  35. let's not pretend that non-preemptive scheduling in hard real-time systems
  36. doesn't provide a "slippery slope" of its own.
  37.  
  38. Simulating multiple periodic rates with a single control tread typically leads
  39. to rate coercion into uniformly harmonic rate series.  This reflects minor
  40. cycle frames as the basic scheduling quantum.  All periodic processing must be
  41. allocated to such frames.  Schedulability analysis is an instance of the
  42. bin-packing problem (which is NP complete.)  Under-packed bins (frames) lead
  43. to dead time which decreases resource utilization.  Improving utilization
  44. usually results in segmentation, which is an optimization on a given schedule.
  45. Such segmentation leads to modifiability problems when the schedule must be
  46. changed to reflect increased utilization within a given periodic activity.
  47. The more finely tuned the schedule becomes, the more difficult it becomes to
  48. change the "time line mosaic" as the system evolves.
  49.  
  50. Large hard real-time systems, such as flight simulators, often distribute
  51. their processing across a number of computational resources.  In shared memory
  52. multi-processing systems, concurrent execution leads to the same data
  53. synchronization problems found with preemptive scheduling.  Solving these
  54. problems leads to an additional optimization, where groups of periodic
  55. activities with strong data dependencies are allocated to the same processing
  56. resource.  This optimization results in the same schedule rigidity as before.
  57. As the load on a given processor approaches its maximum potential,
  58. re-balancing the load leads to additional data synchronization problems when
  59. cooperating periodic activities are allocated to different processors.
  60.  
  61. My purpose here is not to argue for one scheduling discipline or another.
  62. Such arguments must be made in context of a given application's functional and
  63. non-functional attributes, together with some sense of the system's evolution.
  64. Rather, my point is that the wealth of experience with non-preemptive
  65. scheduling has motivated interest in alternatives, especially in the area of
  66. distributed hard real-time systems.  As long as the use of non-preemptive
  67. scheduling results in modifiability and extensibility problems, leading to
  68. premature product mortality, this interest will likely remain strong.
  69.  
  70.  Larry Howard  (lph@sei.cmu.edu)                       |
  71.  Software Engineering Institute, Carnegie Mellon Univ. | Vera pro gratiis.
  72.  Pittsburgh, PA 15213-3890   (412) 268-6397/5857 (fax) | 
  73.