virtual memory 4514

cp67 kernel initially implemented bestfit ... an issue was storage fragmentation and long chains of "free" blocks ... production operation frequently would get to several hundred (or more) available blocks ... releasing a block required scanning the list to find storage address to sort it into and see if newly released storage block was adjacent to something already on the chain and could be merged into single larger block ... obtaining a block required scanning list for best fit.

Lincoln Labs had defined the search list instruction (SLT) which was available on many 360-67 models. Lincoln did a modification of the CP67 kernel to use the SLT instruction for running the free storage blocks. it still required a couple storage references per block ... even if the instruction looping overhead had been minimized (even with the SLT instruction, scanning several hundred blocks still took 3-4 storage references per block or a couple thousand storage references per call).

when i was an undergraduate ... in addition to the virtual memory stuff and dynamic adaptive scheduling

I had also done a lot of other work on the kernel ... including some significant pathlength reductions. as other kernel pathlengths were significantly improved, the storage allocation routine was becoming a significant fraction of total kernel pathlength ... approaching half of kernel overhead

in the early 70s, there was a lot of work on cp67 subpool strategy. this eventually resulted in an implementation that defined a set of subpools that handled something like 95percent of typical storage requests and satisfied a typical request in something like 14 instructions (half of which were creating trace table entry for each call). this implementation got cp67 internal kernel storage Debt Management overhead back down under ten percent.

reference to paper on the work: B. Margolin, et al, Analysis of Free-Storage Algorithms, IBM System Journal 10, pgs 283-304, 1971

this subpool design was carried over into vm370. in the mid-70s, when I was working on the ECPS microcode performance buttist for the 138-148 there was extensive kernel pathlength investigation. the following shows a summary of major internal kernel pathlength sorted by percent of total ... that was used for selecting portions of the vm370 kernel to drop into microcode

there was 6k bytes of microcode space available ... and 370 instructions translated into microcode at approximately 1:1 bytes ... so 6k bytes of 370 instructions translated into approx. 6k bytes of microcode ... but ran ten times faster. The top 6k bytes of kernel pathlength instructions represented nearly 80percent of kernel end ... dropping it into microcode got a 10:1 performance improvement.

in any case, from the above, the typical call to return a block of storage ("FRET") represented 3.77percent of total kernel overhead and typical call to obtain a block of storage ("FREE") represented 3.47percent of total kernel overhead.

misc. past posts mentioning the cp67 subpool work

--