Path: utzoo!attcan!uunet!fernwood!apple!usc!julius.cs.uiuc.edu!zaphod.mps.ohio-state.edu!wuarchive!cs.utexas.edu!mailrus!iuvax!rutgers!rochester!pt.cs.cmu.edu!o.gp.cs.cmu.edu!andrew.cmu.edu!+ From: David.Maynard@CS.CMU.EDU Newsgroups: comp.realtime Subject: Re: Software primitives for real-time programming languages Message-ID: Date: 27 Sep 90 18:18:02 GMT References: <12682@cs.utexas.edu> <1844@tuvie> <224@srchtec.UUCP>, , <1890@tuvie> Organization: Carnegie Mellon, Pittsburgh, PA Lines: 62 > This is a great idea for requirements description. But how are the > requirements then transformed into a working system? > Basically you have a set of time-value functions. I assume that > the execution of the system should maximize the `overall value', Exactly. The basic goal of the algorithms is to maximize the value to the application. When sufficient resources are available, all of the time constraints should be met. When overload situations occur, threads that will yield the least value to the application (either because they are likely to miss their time constraint or because they just aren't very valuable) should be shed so that other threads can satisfy their time constraints (and contribute value). > Are the value functions used for run-time scheduling? > How do the scheduling algorithms work? We are currently developing the third generation of scheduling algorithms that use time-value functions (at run-time). The first generation assumed a uniprocessor with independent threads (but used a consistent framework which was adapted to work in a distributed environment). The second generation of algorithms accounts for dependencies among tasks. The third generation (the topic of my thesis research) attempts to deal more intelligently with multiple processor environments. It is difficult to give a concise (and accurate) summary of how the algorithms work. In non-overload situations, the different versions are "roughly" equivalent to deadline schedulers in that you can prove similar things about their optimality. During overloads, they use a notion of "value density" to determine what threads to schedule. It is definitely a hard scheduling problem, but we have been pleased with our results to date. > Not everything is a nail. Some things are. Those things are called > `nails'. I would really like to see a set of programming primitives that deal consistently with hard deadline tasks and with other types of time constraints. Ideally I would envision a method that would work equally well on a low-level control system that was best-designed using hard-deadline periodics and on a higher-level system that was predominately aperiodic and stochastic (or on a system that handled both types of activities). Maybe an appropriate way to get started with this (as opposed to discussing what we are going to discuss) is for people to posts some relevant references. I promise to try coming up with a list of available Alpha references (although it will likely take a few days). I've seen other relevant work in some of the RTSS proceedings. It would also be good if we could get some feedback from people in industry that have developed in-house techniques. -David --- David P. Maynard (dpm@cs.cmu.edu) Alpha OS Research Group Carnegie Mellon University & Concurrent Computer Corp. --- Any opinions expressed are mine. I haven't asked CMU or Concurrent what they think. ---