This page is part of the web mail archives of SRFI 18 from before July 7th, 2015. The new archives for SRFI 18 contain all messages, not just those from before July 7th, 2015.
David Rush <kumo@xxxxxxxxxxxxx> writes: > that you are meaning that you have some subset of the tasks in > the system that need completion by a certain time, Yes. Deadline driven scheduling of RT tasks gives the highest priority to the task which has the earliest completion time. > and that their priority should be dynamically raised each quanta > that they are runnable but not actually running. Also that the > priority of a deadlined task is never allowed to rise higher than > that of a task with an earlier deadline. Conceptually, hard RT systems do not have quanta. However, as long as the partial ordering of tasks does not deviate from what it would be if priorities were assigned according to earliest completion time, you can do whatever you want to the actual priorities. > Now in a hypothetical system with deadlines, I've got to assume that > you have tasks with and without deadlines (Non-deadline tasks being > dedicated to various housekeeping functions: logging, monitoring, > etc). Non-deadlined tasks would be scheduled by normal priority, but > deadlined tasks get the per-quantum magic. Looking at it from the RT perspective (to which I have been thoroughly indoctrinated ;-), non-RT tasks are tasks with deadlines at infinity. Thus, a RT task will always preempt a non-RT task when scheduled according to a deadline driven policy. > Now if you try and map the scheduling of deadlined tasks into the > priority scheme of non-deadlined tasks, you lose information in the > scheduler, specifically the actual deadline (which serves as both a > maximum priority limit and as strong heuristic of the needed > priority). Yes. The loss of information is what prevents the implementation of deadline driven scheduling on a fixed priority scheduler in a straight forward and efficient way. Note though, that it is possible to implement deadline driven scheduling in a fixed priority system by employing a scheduler task which has the second highest priority in the system. The scheduler task selects the (user) task with the earliest deadline and elevates its priority to be the highest priority in the system, where upon it preempts the scheduler thread and runs. If the average unit of work is sufficiently large in relation to the (admittedly high) overhead of the scheduler-as-task scheme, the system works pretty well for soft RT. This scheme was implemented on top of Solaris by Hao-hua Chu at the University of Illinois at Urbana-Champaign. For more details, see <http://cairo.cs.uiuc.edu/papers/thesis.hao.ps>. > Another case where this kind of thing arises is in the > implementation of priority inheritance mutexes. In this case each > mutex has an associated priority, to which any acquiring thread gets > promoted (if a thread already has higher priority than the mutex it > retains its priority). So a thread's effective priority is the > maximum of its 'native' priority and the priorities of any mutexes > it owns. Again, with a simple integer mapping you can make the right > thing happen, but it becomes very difficult to get the right > priority restored to a thread upon mutex release, especially without > stopping the the scheduler entirely. I'm not sure I followed you. First of all, if the mutex isn't assigned the highest priority of any task that acquires it, the potential for priority inversion (a low priority task executes while a higher priority task is blocked) is still there. Second of all, a correct implementation of priority inheritence raises the temporary priority of the task holding the mutex each time a higher priority task attempts to acquire the mutex. As soon as it releases the mutex, the task's priority returns to the priority it had before it acquired the mutex. Since a task can hold several mutexes, this requires a stack of (increasing) priorities, with the priority at the bottom of the stack being the task's original priority. I see nothing in the integer implementation that would prevent the use of integer priorities. In fact, priority inheritence is routinely done in fixed priority RT systems. > Which was Marc's main complaint about the THREAD-PRIORITY>? > primitive. But the fundamental problem is that whenever you have a > change in the priority levels of the tasks in a system the scheduler > has to stop and get its head screwed back on straight. When all you > have is a single integer affecting the task priority this doesn't > seem to be much of a problem, but it is still the same problem. But the creation of a task also causes a change in the priority ordering of the tasks in the system. Changing the priority of an existing task is conceptually no different than removing the task at its current priority and creating it at its new priority (with out loosing its state, of course). Thus the "stop" mechanism is already in place. I believe Marc's objection to parameterizing the scheduler with THREAD-PRIORITY>? (or allowing modular schedulers) is that it is very difficult to design the rest of the thread/mutex/condition variable system abstractly enough to allow things to work without heavy penalties in performance. (Depending on your definitions of "difficult" and "performance", the design may be impossible.) Furthermore, the properties of the system depend critically upon the parameterizing comparison function hence it makes the use of independently developed libraries which use threads problematic. Their semantics will change depending on the comparision function you install. > As you can tell, I am actually in favor of THREAD-PRIORITY>? > (although I'm not implementing a scheduler around it at the moment). > It nicely captures the essence of the variations in scheduling > schemes. But regardless of that my experience in implementing > priority-inheritance mutexes suggests that having the > (without-scheduling <thunk>) form is going to be necessary for > mapping complex priority schemes onto the integers anyway. As you can tell from my original posting "Thoughts on Priorities and Quanta" in the archive and from my comments here, I too would like to see RT threads in Scheme. However, I feel that Marc has generally done a good job of wording SRFI-18 such that it does not preclude the development of a RT-thread SRFI in the future. The only limitation that I still see is that the concept of integral priorities prevents an efficient implementation of a deadline-driven scheduler. Marc: What about weakening the definition of priority to allow other comparable values such as real numbers or (more specifically) time objects? With this, I am sure a RT-SRFI could be written without having to undo parts of SRFI-18. Mark -- Mark K. Gardner RADIANT Team Network Engineering, CIC-5 Los Alamos National Laboratory P.O. Box 1663, M.S. D451 Los Alamos, NM 87545 Email: mkg@xxxxxxxx Phone: 1-505-665-4953 --