itsy bitsy Unix

Huw> On 18/03/2005, at 12:36 PM, Paul Koning wrote: Huw> Are the risks in preemptive scheduling just ones of complexity? Huw> I guess that it is much harder to "prove" that this type of Huw> scheduler is going to to the right thing at the right time. I Huw> know that, for example, the scheduler for VMS has gone from a Huw> couple of pages of assembler to something like 75 pages of Huw> BLISS! It's not so much the correctness of the scheduler itself that's the issue. The real issue is the correctness of the decisions it makes. That depends primarily on the settings you assign to the processes. For complex schedulers (like VMS) it also depends on all the various dynamic adjustments it makes, which are typically very hard to understand. The result is that you often end up with a system whose dynamic properties are not known and perhaps not even knowable. For a timesharing system, that's not so bad; if it doesn't act right, people just grumble a bit. For a real time system, it's a bigger issue. If somet things don't get done on time -- or not at all -- the result can be that the system doesn't do the job it was designed to do. A real world example (names omitted): a decade or so ago, there were routers whose designers thought that the job of a router is to forward packets. So they made packet forwarding the top priority. Unfortunately, that's a misunderstanding. The job of a router is to have an up to date view of the network topology, and to communicate that to the other routers. Its *secondary* job is to forward packets. What happened is that a routing loop formed -- which is normal. But there were enough packets circulating in the routing loop that the forwarding process was taking 100% of the CPU time. So the route update process didn't run, so the routing loop was persistent rather than transient as it is supposed to be. Result: the network was down until the operators could shut down enough routers to break the loop. To avoid this, you have to realize that routers are real time systems and that every process in it must be guaranteed a non-zero fraction of the system resources. (That's the absolute minimum -- a better answer is to set specific non-zero lower bounds on the per process resources.) This is why, in a previous life when I built routers, I used single priority non-preemptive schedulers (sometimes as simple as the "for loop" one I showed) to schedule the router functions. The result was that they were stable and reliable and operated correctly under all loads, including overloads. paul