IBM 610 workstation computer 3422

that was something akin to the original cp67 10 level scheduler (some of which may have even been inherited from ctss). the cpu overhead was more overhead than any benefit it provided (in part because it only looked at cpu and didn't have any page thrashing controls). it also had some stuff that rescanned the whole list ... that resulted in the overhead being proportional to the size of the queue (number of users) ... not the amount work performed.

the change done by lincoln labs to two level scheduler ... got lot less sophisticated about differentiating cpu utilization ... significantly reduced the scheduling cpu overhead and thru in a very rudimentary page thrashing control ... however it left in some frequent list scanning ... so while the overhead scanning the lists was reduced (compared to the earlier implementation) ... it still grew as the size of the queues grew ... not proportional to the thruput.

so the dynamic adaptive feedback stuff ... fundamental approach was attempt to achieve near zero scheduling pathlength overhead at the same time making it much more proportional to the work perform ... not proportional to the size of the queues (which can grow non-linear independent of the amount of resources handed out).

so that was part of the various slight of hand stuff ... to come up with coding solutions that didn't involve rescanning complete queues and attempting to do things like n*(n-1)-2 set of comparisons regarding various states.

rule of thumb, scheduling overhead was proportional to the thruput, not the size of the queues. for some topic drift ... we encountered a drastic example of this in the early web scale-up days. tcp implementations originally buttumed relatively long-lived sessions. http came along and used tcp for reliable transaction operations ... with all the setup-teardown ... minimum of 7 packet exchange (we had earlier worked on xtp that had minimum of 3 package exchange for reliable transaction). tcp kept a finwait list of all terminated sessions on the off chance that there might be some dangling packets arrive after the termination handshake (because of out-of-order delivery feature of underlying ip). as webservers scaled up ... there was a period where several major platforms were spending 95percent of total cpu doing linear scan of the finwait list on packet arrival. misc. past finwait posts:

misc. past posts mentioning xtp (and hsp, high-speed protocol, as well as our problems with OSI in ISO standards meetings)

another scheduling point i learned from cp67 in my undergraduate days is that frequently there is a whole bunch of scenarios where spending a lot of time making a decision has little or no overall effect. make the most frequent decisions a lot simpler and save more sophisticated stuff for less frequent. misc. past posts on scheduling

one of the other places that i threw in slight of hand coding was in the page replacement. i had highly optimized the selection to be near zero overhead ... while still near optimally approx. true LRU replacement. a problem is that true LRU (and the various approx) degenerate to FIFO under various conditions. I came up with a slight of hand that degnerated to random (instead of fifo) under those conditions. part of the trick was the transition to random didn't involve any real coding ... it involved a slightly different way that the data structures were built-handled ... such that degenerating to random (instead of FIFO) was much more a side-effect of the data structure ... as opposed to lots of fancy coding (that would have tended to have significantly more overhead).

misc. past postings on page replacement, etc

for even more drift ... effectively part of dynamic adaptive resource management was keeping track of the rate at which resources were consumed. xtp also wandered into doing rate-based pacing ... as opposed to windows and things like slow-start for congestion control. in the same period that slow-start was originally published ... there was paper in acm sigcomm conference showing that window-based congestion control was unstable in high-latency, heterogeneous networking environments (and the original point of windows is as latency compensation in high-latency environments). misc. past posts mentioning rate-based pacing

--