PDP-11 Overlays

[Jerome H. Fine]

 >Paul Koning wrote:

>>>On Sep 21, 2015, at 3:14 PM, Jerome H. Fine wrote:
>>
>>Recently, there have been a number of references to using
>>overlays on the PDP-11.  There have also been strong suggestions
>>that overlays were structured differently under the 3 operating
>>systems:  RSTS/E, RSX-11 and RT-11.
>>
>>Obviously, I understand how RT-11 overlays were set up, but
>>for those readers who don't:
>>
>>ROOT
>>- contains overlay code subroutines and data tables
>>- data used by more than one overlay
>>
>>FIRST Overlay Region - size of the largest overlay in the region
>>- one or more overlays and the data used by just that overlay
>>
>>SECOND Overlay Region - size of the largest overlay in the region
>>- one or more overlays and the data used by just that overlay
>>
>>THIRD Overlay Region - size of the largest overlay in the region
>>- one or more overlays and the data used by just that overlay
>>
>>FREE  MEMORY
>>
>>Any overlay could be called from any location.  About the only
>>requirement was that the calling instruction code (specifically the
>>code which followed the calling instruction) had to be in memory
>>when the code returned from the overlay.  In practice, the usual
>>protocol was that an overlay in a higher region was only called
>>from a lower region or the root.
>>
>>I understand that RSTS/E and RSX-11 were a bit more complex.
>>Can anyone briefly summarize and also provide a link to the
>>details in the appropriate manual if it is available on the internet?
>>    
>>
>
>RSTS has no specific structure of its own.  It provided both RT-11 and RSX emulation, and as a result would offer the structures from both of those, depending on which environment you chose for a particular application.
>
>RSX uses a tree structure.  For details (lots of details) see the TKB manual.
>
>Suppose you have main which calls o1.  o1 calls o2 which calls o3, and o1 also calls o5 which calls o6.  
>
>In the RSX case, you could specify a tree with two branches: main to o1 and from there o2 to o3, and o5 to o6.  In the RT11 case, you might put o1 in region 1, o2 and o5 in region 2, and o3 and o6 in region 3.
>
>The memory requirements would be:
>
>	rt11: main + o1 + max (o2, o5) + max (o3, o6)
>	rsx:  main + o1 + max (o2 + o3, o5 + o6)
>
>If o2 and o6 are large while o3 and o5 are small, then the RSX case gives you a smaller memory footprint.
>
In RT-11, you can also put o5 in region three and o6 in region two
and still have o5 call o6.  If TKB does not allow that, then it is
more restrictive in some ways than RT-11.  So the memory
requirements would be:

            RT-11:  main + max (o2, o6) + max (o3, o5)

This is probably better than the RT-11 memory requirement which
you suggested, but likely not as good as the RSX-11 memory
requirement.

Also, my example is rarely that simple in actual practice.

Another important aspect is that RT-11 has a few extra instructions
in the overlay handler which determines if the overlay is already in
memory.  The linker assigns an overlay number to each overlay and
places that value (actually *6) in the first word of each overlay as a
data value that the user program does not see.  When the overlay
handler is invoked and the address to be used for the .ReadF request
is found, the overlay handler checks to determine if that value *6 is
still in the first word.  If so, the overlay handler can assume that the
overlay is still in memory and the call can jump to the normal entry
address for that subroutine call without the overhead of reading the
overlay  NOTE that this check depends on a region which has
the same starting address for all overlays within the region and
no overlap between regions.  This allows for that extra word
which the user code is unaware of and never accesses.

In MACRO-11 which executes under RT-11, I modified the
overlay handler to keep track of how many times the overlay
was called and how may times it needed to be read.  99% of the
time, the overlay was already in memory and the code was ready
to be executed.  The number of calls can be so large that a 32-bit
entry was required to track the number of calls.  It was very easy
to add the additional code since the instructions to test for the
overlay being present were already there along with an extra
register (having already been saved) that pointed to the 32-bit
entry that kept track of the number of calls as well as the number
of times that the overlay needed to be read.

My question is if TKB overlays also have these extra instructions?
For example, if there are three trees with only two trees having a
second overlay, does the overlay handler know if the second overlay
for a different tree is still there?  It seems doubtful since a data value
could, by chance, have the same value that was being checked.

So each overlay handler has advantages and disadvantages.
I wonder if in RSX-11 the MACRO-11 assembler takes longer
than in RT-11 when it needs to always read in the overlay?

Jerome Fine