List of Archived Posts

2006 Newsgroup Postings (05/13 - 05/18)

virtual memory

virtual memory

virtual memory

virtual memory

virtual memory

virtual memory

The Pankian Metaphor

virtual memory

ALternatives to EMail

Value of an old IBM PS/2 CL57 SX Laptop

The Chant of the Trolloc Hordes

The Pankian Metaphor

History of first use of all-computerized typesetting?

virtual memory

virtual memory

30 hop limit

Resolver Issue (was Revolver Issue)

virtual memory

virtual memory

virtual memory

virtual memory

virtual memory

virtual memory

virtual memory

virtual memory

virtual memory

virtual memory

virtual memory

Password Complexity

How to implement Lpars within Linux

virtual memory

virtual memory

Code density and performance?

How to implement Lpars within Linux

Arpa address

Code density and performance?

The Pankian Metaphor

virtual memory

The Pankian Metaphor

virtual memory

virtual memory

virtual memory

Passwords for bank sites - change or not?

virtual memory

virtual memory

Arpa address

Arpa address

where do I buy a SSL certificate?

where do I buy a SSL certificate?

Arpa address

Arpa address

Hey! Keep Your Hands Out Of My Abstraction Layer!

Passwords for bank sites - change or not?

Arpa address

virtual memory

From: Anne & Lynn Wheeler <lynn@garlic.com>
Subject: Re: virtual memory
Newsgroups: comp.arch,alt.folklore.computers
Date: Sat, 13 May 2006 12:29:08 -0600

CBFalconer writes:

Something I built in the late 70s/early 80s was a variant on LRU.
It basically took the used bit at intervals, and shifted it right
into a history byte (actually 5 bits), while resetting the used
bit.  The result was something that gave decreasing weight to older
history, and thus could resolve decisions made over the past 5 or
six intervals.

The intervals were derived from inter-segment procedure call
counting, which in turn were the only events that could use the LRU
scheme.  Nothing further was done unless the required segment was
not present, when the scheme only selected segments to displace.
This was only used for code segments, not data.

this was somewhat similar to the Multics 4-bit experiments in the
early 70s ... shifting the reference bit. there was a multics paper in
acm in the early 70s, i believe by saltzer. they actually tried
experiments with keeping different number of history bits

I did something similar in about the same time frame ... but using up
to eight history bits:
http://www.garlic.com/~lynn/subtopic.html#wsclock

one of the things that clock and a lot of the simulation work at the
science center turned up was that there was different use/past
characteristics and able to predict future behavior; aka there were
various past behavior thresholds that wouldn't correlate with future
behavior over various periods (invalidating assumption behind least
recently used replacement strategy)

random past posts mentioning saltzer (mostly nothing to do with this
subject).
http://www.garlic.com/~lynn/2000e.html#0 What good and old text formatter are there ?
http://www.garlic.com/~lynn/2002p.html#13 Multics on emulated systems?
http://www.garlic.com/~lynn/2003.html#18 cost of crossing kernel/user boundary
http://www.garlic.com/~lynn/2003o.html#32 who invented the "popup" ?
http://www.garlic.com/~lynn/2004g.html#46 PL/? History
http://www.garlic.com/~lynn/2004l.html#56 project athena & compare and swap
http://www.garlic.com/~lynn/2004l.html#73 Specifying all biz rules in relational data
http://www.garlic.com/~lynn/2005b.html#29 M.I.T. SNA study team
http://www.garlic.com/~lynn/2005u.html#42 Mainframe Applications and Records Keeping?
http://www.garlic.com/~lynn/2006e.html#31 MCTS
http://www.garlic.com/~lynn/2006h.html#46 blast from the past, tcp/ip, project athena and kerberos
http://www.garlic.com/~lynn/2006h.html#55 History of first use of all-computerized typesetting?

--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn/

virtual memory

From: Anne & Lynn Wheeler <lynn@garlic.com>
Subject: Re: virtual memory
Newsgroups: comp.arch,alt.folklore.computers
Date: Sat, 13 May 2006 17:46:33 -0600

Bill Todd writes:

Lynn's exposition is not always easy (at least for me) to follow
completely, but his expansion on this topic in other posts (see, for
example, http://www.garlic.com/~lynn/2001c.html#10 and also the first
reference therein)seems to suggest 1) that the grenoble implementation
implemented only static (fixed-size) working sets and 2) that his
implementation, while global in nature, *also* involved something
resembling working sets (and something he called 'dynamic adaptive
thrashing control').

If either of those was the case (or if the systems differed in other
significant respects - since his tweaks seem to have tended to be
fairly pervasive), then his observations about the relative
performance of those two implementations really aren't applicable to a
discussion of contemporary (more mature) working-set implementations.

previous incarnation of this thread 7aug2004
http://www.garlic.com/~lynn/2004i.html#0 Hard disk architecture: are outer cylinders still faster than inner cylinders?
http://www.garlic.com/~lynn/2004i.html#1 Hard disk architecture: are outer cylinders still faster than inner cylinders?
http://www.garlic.com/~lynn/2004i.html#8 Hard disk architecture: are outer cylinders still faster than inner cylinders?

the referenced acm article describes the grenoble implementation

J. Rodriquez-Rosell, The design, implementation, and evaluation of a
working set dispatcher, cacm16, apr73

--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn/

virtual memory

From: Anne & Lynn Wheeler <lynn@garlic.com>
Subject: Re: virtual memory
Newsgroups: comp.arch,alt.folklore.computers
Date: Sat, 13 May 2006 20:07:38 -0600

CBFalconer writes:

Something I built in the late 70s/early 80s was a variant on LRU.
It basically took the used bit at intervals, and shifted it right
into a history byte (actually 5 bits), while resetting the used
bit.  The result was something that gave decreasing weight to older
history, and thus could resolve decisions made over the past 5 or
six intervals.

The intervals were derived from inter-segment procedure call
counting, which in turn were the only events that could use the LRU
scheme.  Nothing further was done unless the required segment was
not present, when the scheme only selected segments to displace.
This was only used for code segments, not data.

the other thing that was starting to happen by the second half of the
70s was things were starting to shift from being real memory
constrained to being much more disk arm constrained.

the working set and page replacement strategies of the 60s and early
were focused on real storage being frequently a highly constrained
resource. however, by the second half of the 70s, disk arms were much
more frequently the constrained resources .... although you could have
second order effects involving paging operations putting heaving
contention on disk resource, possibly creating long queues and long
service times. the page thrashing with huge system page wait of the
60s could be replaced with disk arm contention with huge system page
waits ... but not particularly because of excessive over commitment of
real storage.

this was the late 70s shift from attempting heavy optimization of real
storage use ... to attempting to trade-off real storage resources in
attempt to compensate and mitigate the disk arm bottlenecks. some
exploration of this subject in previous post in this thread
http://www.garlic.com/~lynn/2006i.html#28 virtual memory

some of the references in the above references a comparision between a
typical 360/67 cp67 configuration supporting 80 some users comfortably
(on the cambridge system) to a decade plus later with a 3081 vm370
configuration supporting 300 some users with similar workload
operation. the processor mips and the available "pageable pages" had
increased on the order of fifty times while the numbers of supported
concurrent users increased around four times. as shown in the repeated
comparision the increase in number of users was relatively consistent
in the increase in disk arm performance (which had contributed to my
comment that relative system disk thruput had declined by a factor of
10 times during the period). one of the old references mentioned in
the post referenced above:
http://www.garlic.com/~lynn/93.html#31 Big I/O or Kicking the Mainframe out the Door

the issue became is it possible to develop strategies that better
optimized the use of disk arms ... possibly at the sacrifice of either
processor and/or real storage optimization.

one such strategy was "big pages" for paging in the early 80s for both
vm370 and mvs. part of this was 3380 disk arm thruput was maybe 3-4
times that of the earlier 2314 disk arm ... however the data transfer
was ten times as much. "big pages" went to creating "on-the-fly"
full-track clusters of 4k pages. paging area on disk was layed out
possibly ten to twenty times larger than actually needed and managed
by a "moving cursor" algorithm ... somewhat similar to some of the log
structured filesystem work that would appear a decade later (which
were done for similar objectives to try and drastically improve the
disk arm use efficiency).

for page-out ... a full-tracks worth of pages from an address space
would be collected together (whether the pages had been changed or not
during their current residency in storage) and written as one
operation. later when there was a page fault for any 4k page in a "big
page" ... the whole track would be read into real storage. This
profligate movement of pages might increase the total real storage
required by an application by 20-30percent (and similar increase in
number of bytes moved) ... but was traded off by redcuing the disk arm
resource for moving each page by 90 percent. this also could play fast
and loose with the accuracy of tracking what virtual pages were
actually the least recently used ... but the trade-off of drastically
improving the efficiency of disk arm resource for moving pages showed
a net win (as something that represented the primary bottleneck in the
infrastructure).

with such a big increase in the amount of real storage ... and the
shifting of major system bottleneck to disk arm ... there could be
significant system thruput trade-offs that might result in much less
efficient use of real storage if it might drastically improve the
overall system thruput situation dealing with disk arm bottleneck.

i had also done analogous efficiency with the page mapped filesystem
i had developed
http://www.garlic.com/~lynn/subtopic.html#mmap

improving the probability of contiguous allocation for many filesystem
objects and being able to dynamically adjusting how large a block
transfer could be done when accessing the object (based on
configuration, load) ... again trading off the efficiency of
real-storage utilization for improved diak arm efficiency.

misc. past posts discussing the "big page" strategy from a couple
decades ago.
http://www.garlic.com/~lynn/2001k.html#60 Defrag in linux? - Newbie question
http://www.garlic.com/~lynn/2002b.html#20 index searching
http://www.garlic.com/~lynn/2002c.html#29 Page size (was: VAX, M68K complex instructions)
http://www.garlic.com/~lynn/2002c.html#48 Swapper was Re: History of Login Names
http://www.garlic.com/~lynn/2002e.html#8 What are some impressive page rates?
http://www.garlic.com/~lynn/2002e.html#11 What are some impressive page rates?
http://www.garlic.com/~lynn/2002f.html#20 Blade architectures
http://www.garlic.com/~lynn/2002l.html#36 Do any architectures use instruction count instead of timer
http://www.garlic.com/~lynn/2002m.html#4 Handling variable page sizes?
http://www.garlic.com/~lynn/2003b.html#69 Disk drives as commodities. Was Re: Yamhill
http://www.garlic.com/~lynn/2003d.html#21 PDP10 and RISC
http://www.garlic.com/~lynn/2003f.html#5 Alpha performance, why?
http://www.garlic.com/~lynn/2003f.html#9 Alpha performance, why?
http://www.garlic.com/~lynn/2003f.html#48 Alpha performance, why?
http://www.garlic.com/~lynn/2003g.html#12 Page Table - per OS/Process
http://www.garlic.com/~lynn/2003o.html#61 1teraflops cell processor possible?
http://www.garlic.com/~lynn/2003o.html#62 1teraflops cell processor possible?
http://www.garlic.com/~lynn/2004.html#13 Holee shit!  30 years ago!
http://www.garlic.com/~lynn/2004e.html#16 Paging query - progress
http://www.garlic.com/~lynn/2004n.html#22 Shipwrecks
http://www.garlic.com/~lynn/2004p.html#39 100% CPU is not always bad
http://www.garlic.com/~lynn/2005h.html#15 Exceptions at basic block boundaries
http://www.garlic.com/~lynn/2005j.html#51  Q ALLOC PAGE vs. CP Q ALLOC vs ESAMAP
http://www.garlic.com/~lynn/2005l.html#41 25% Pageds utilization on 3390-09?
http://www.garlic.com/~lynn/2005n.html#18 Code density and performance?
http://www.garlic.com/~lynn/2005n.html#19 Code density and performance?
http://www.garlic.com/~lynn/2005n.html#21 Code density and performance?
http://www.garlic.com/~lynn/2005n.html#22 Code density and performance?

--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn/

virtual memory

From: Anne & Lynn Wheeler <lynn@garlic.com>
Subject: Re: virtual memory
Newsgroups: comp.arch,alt.folklore.computers
Date: Sat, 13 May 2006 20:22:33 -0600

Anne & Lynn Wheeler writes:

one such strategy was "big pages" for paging in the early 80s for
both vm370 and mvs. part of this was 3380 disk arm thruput was maybe
3-4 times that of the earlier 2314 disk arm ... however the data
transfer was ten times as much. "big pages" went to creating
"on-the-fly" full-track clusters of 4k pages. paging area on disk
was layed out possibly ten to twenty times larger than actually
needed and managed by a "moving cursor" algorithm ... somewhat
similar to some of the log structured filesystem work that would
appear a decade later (which were done for similar objectives to try
and drastically improve the disk arm use efficiency).

re:
http://www.garlic.com/~lynn/2006j.html#2 virtual memory

note that one of the advantages that "big pages" moving cursor had
over log structure filesystem ... was that the filesystem data on disk
was typically treated as persistant and periodically it had to execute
a garbage collection and coalescing process.  paging areas were
treated as much more ephemeral ... whenever a "big page" had a fault
and was brought back into real storage, the disk location was
discarded and became available (a nature of paging operation tended to
provide the garbage collection and coalescing operation as a
side-effect which was an explicit periodic overhead operation in the
log-structure paradimg).

for total topic drift ... during our ha/cmp product effort
http://www.garlic.com/~lynn/subtopic.html#hacmp

there was work started on filesystem for geographic survivability
(replicated at multiple physical sites), one of the consultants
brought in, had done a lot of the work on a unix log structured
filesystem ... cited in one of the following posts mentioning
log structure filesystems:
http://www.garlic.com/~lynn/93.html#28 Log Structured filesystems -- think twice
http://www.garlic.com/~lynn/93.html#29 Log Structured filesystems -- think twice
http://www.garlic.com/~lynn/2000.html#93 Predictions and reality: the I/O Bottleneck
http://www.garlic.com/~lynn/2000c.html#24 Hard disks, one year ago today
http://www.garlic.com/~lynn/2000g.html#38 4M pages are a bad idea (was Re: AMD 64bit Hammer CPU and VM)
http://www.garlic.com/~lynn/2001c.html#28 The Foolish Dozen or so in This News Group
http://www.garlic.com/~lynn/2001f.html#59 JFSes: are they really needed?
http://www.garlic.com/~lynn/2001f.html#60 JFSes: are they really needed?
http://www.garlic.com/~lynn/2001m.html#56 Contiguous file system
http://www.garlic.com/~lynn/2002b.html#20 index searching
http://www.garlic.com/~lynn/2002l.html#36 Do any architectures use instruction count instead of timer
http://www.garlic.com/~lynn/2002m.html#4 Handling variable page sizes?
http://www.garlic.com/~lynn/2002n.html#9 Asynch I/O
http://www.garlic.com/~lynn/2003b.html#69 Disk drives as commodities. Was Re: Yamhill
http://www.garlic.com/~lynn/2003f.html#5 Alpha performance, why?
http://www.garlic.com/~lynn/2003f.html#9 Alpha performance, why?
http://www.garlic.com/~lynn/2003k.html#0 VSPC
http://www.garlic.com/~lynn/2004g.html#22 Infiniband - practicalities for small clusters
http://www.garlic.com/~lynn/2005l.html#41 25% Pageds utilization on 3390-09?
http://www.garlic.com/~lynn/2005n.html#22 Code density and performance?
http://www.garlic.com/~lynn/2005n.html#36 Code density and performance?

--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn/

virtual memory

From: Anne & Lynn Wheeler <lynn@garlic.com>
Subject: Re: virtual memory
Newsgroups: comp.arch,alt.folklore.computers
Date: Sat, 13 May 2006 21:01:50 -0600

Anne & Lynn Wheeler writes:

for page-out ... a full-tracks worth of pages from an address space
would be collected together (whether the pages had been changed or not
during their current residency in storage) and written as one
operation. later when there was a page fault for any 4k page in a "big
page" ... the whole track would be read into real storage. This
profligate movement of pages might increase the total real storage
required by an application by 20-30percent (and similar increase in
number of bytes moved) ... but was traded off by redcuing the disk arm
resource for moving each page by 90 percent. this also could play fast
and loose with the accuracy of tracking what virtual pages were
actually the least recently used ... but the trade-off of drastically
improving the efficiency of disk arm resource for moving pages showed
a net win (as something that represented the primary bottleneck in the
infrastructure).

re:
http://www.garlic.com/~lynn/2006j.html#2 virtual memory

the replacement strategies and page thrashing from the 60s and early
70s was much more oriented towards having only just the right pages
in real memory.

by the late 70s, with the increase in many real storage size
configurations ... real storage contention because there was too many
concurrent tasks (and resulting page thrashing) was much less of an
issue ... the small size of the disk arm spigot resource was becoming
so (relatively) limited that any major movement of pages to/from
disk could represent paging bottlenecks.

the "big page" strategy could get away fetching as much as 70-80
percent wrong pages ... resulting in equal amount of 70-80 percent of
real storage being occupied by the "wrong" pages ... it could still
come out a winner, if it could cut in half the number of disk arm uses
getting the right pages into real storage.

the correllary is that there were drastistically fewer situations
where any judgement about the aggregate, concurrent working set sizes
(of active tasks) would force a scheduling reduction in the
number of concurrent tasks that were allowed to simultaneously
compete for real storage.

past incarnation of this thread:
http://www.garlic.com/~lynn/2004i.html#0 Hard disk architecture: are outer cylinders still faster than inner cylinders?
http://www.garlic.com/~lynn/2004i.html#1 Hard disk architecture: are outer cylinders still faster than inner cylinders?
http://www.garlic.com/~lynn/2004i.html#8 Hard disk architecture: are outer cylinders still faster than inner cylinders?

--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn/

virtual memory

From: Anne & Lynn Wheeler <lynn@garlic.com>
Subject: Re: virtual memory
Newsgroups: comp.arch,alt.folklore.computers,bit.listserv.vmesa-l
Date: Sun, 14 May 2006 08:35:29 -0600

jmfbahciv writes:

Then a subset of those categories would have to be code
and data, with the rare exception where code is data
(writable code segment which god never meant happen).

I suppose there would also have to be special handling
of data pages that were suddenly changed to code.

Comments on the discussion:

1.  An OS did not need VM to do relocation.  Example: KA10.
2.  Do not confuse paging hardware with virtual memory.
They are different.  The reason this confusion happens
is because both were usually done during the same
major version OS release.    If your new CPU has paging
hardware, you might as well schedule your VM project
at the same time.  You might as well subject the customer
to both pains all at the same time.  It was like
pulling a tooth:  yank it and get it over with or tweak
it and have years of long drawn annoying pain in the
nethers.

i've described two instances where there was special case processing
... and both instances resulted in non-optimal implementations ...

• one was the initial morph from cp67 to vm370 where they had actual
lists of pages for the scanning/reset/replacement selection and
"shared" pages were treated specially ... not based on reference
bits

• the other was the initial morph from mvt to os/vs2 where they would
bias the replacement selection for non-changed pages before changed
pages

post including description of the above two scenarios
http://www.garlic.com/~lynn/2006i.html#43 virtual memory

i had arguments with both groups over the details and they went ahead
and did it anyway (which, in both cases, got corrected much later
... the os/vs2 they had to do the correction themselves, the vm370
shared pages, i was able to correct in the release of the resource
manager).

i had also done a paging, non-virtual memory thing originally as an
undergraduate in the 60s for cp67 ... but it was never picked up in
the product until the morph of cp67 to vm370 where it was used.  the
issue was the kernel code ran real mode, w/o hardware translate turned
on. all its addressing was based on real addresses. when dealing with
addresses from virtual address space ... it used the LRA (load real
address) instruction that translated from virtual to real.

the issue was that the real kernel size was continuing to grow as more
and more features were being added. this was starting to impact the
number of pages left over for virtual address paging. recent post
in this thread making mention of measure of "pageable pages"
(after fixed kernel requirements):
http://www.garlic.com/~lynn/2006i.html#36 virtual memory
http://www.garlic.com/~lynn/2006j.html#2 virtual memory

so i created a dummy set of tables for the "kernel" address space
... and partitioned some low-useage kernel routines (various kinds of
commands, etc) into real, 4k "chunks". I positioned all these real
chunks at the high end of the kernel. When there were calls to
addresses above the "pageable" line ... the call processing
... instead of directly transfering would run the address thru the
dummy table to see if the chunk was actually resident. if it was
resident, then the call would be made to the translated address
location ... running w/o virtual memory turned on.  if the 4k chunk
was indicated as not resident, the paging routine was called to bring
it into storage before transferring to the "real" address. during the
call, the page fixing and lock ... that CCWTRANS for performing
virtual i/o ... was used for preventing the page for be selected from
removal from real storage. the count was decremented at the
return. otherwise these "pageable" kernel pages could be selected for
replacement just like any other page. some recent mentions of CCWTRANS
http://www.garlic.com/~lynn/2006.html#31 Is VIO mandatory?
http://www.garlic.com/~lynn/2006.html#38 Is VIO mandatory?
http://www.garlic.com/~lynn/2006b.html#25 Multiple address spaces
http://www.garlic.com/~lynn/2006f.html#5 3380-3390 Conversion - DISAPPOINTMENT
http://www.garlic.com/~lynn/2006i.html#33 virtual memory

this feature never shipped as part of the cp67 kernel, but was picked
up as part of the initial morph of cp67 to vm370.

Later for the resource manager, i also created a (2nd) small dummy set
of tables for every virtual address space that was used for
administrative writing of tables to disk. tables were collected into
page-aligned 4k real chunks and the page I/O infrastructure was used
for moving the tables to/from disk (in a manner similar to how i had
done the original pageable kernel implementation) previous description
of "paging" SWAPTABLEs.
http://www.garlic.com/~lynn/2006i.html#24 Virtual memory implementation in S/370

in the initial morph of cp67->vm370, some of cms was re-orged to take
advantage of the 370 shared segment protection. however, before 370
virtual memory was announced and shipped, the feature was dropped from
the product line (because the engineers doing the hardwareretrofit of
virtual memory to 370/165 said that shared segment protect and a
couple other features would cause an extra six month delay). a few
past posts mentioning virtual memory retrofit to 370/165:
http://www.garlic.com/~lynn/2006i.html#4 Mainframe vs. xSeries
http://www.garlic.com/~lynn/2006i.html#9 Hadware Support for Protection Bits: what does it really mean?
http://www.garlic.com/~lynn/2006i.html#23 Virtual memory implementation in S/370

as a result, the shared page protection had to redone as a hack to
utilize the storage protect keys that had been carried over from 360.
this required behind the scenes fiddling of the virtual machine
architecture ... which prevented running cms with the virtual machine
assist microcode activated (hardware directly implemented virtual
machine execution of privilege instructions). later, in order to run
cms virtual machines with the VMA microcode assist, protection was
turned off. instead a scan of all shared pages was substituted that
occured on every task switch. an application running in virtual
address space could modify shared pages ... but the effect would be
caught and discarded before task switch occured (so any modification
wouldn't be apparent in other address spaces). this sort of worked
running single processor configurations ... but got much worse in
multi-processor configurations. now you had to have a unique set of
shared pages specific to each real processor. past post mentioning
the changed protection hack for cms
http://www.garlic.com/~lynn/2006i.html#9 Hadware Support for Protection Bits: what does it really mean?
http://www.garlic.com/~lynn/2006i.html#23 Virtual memory implementation in S/370

past posts mention pageable kernel work:
http://www.garlic.com/~lynn/2001b.html#23 Linux IA-64 interrupts [was Re: Itanium benchmarks ...]
http://www.garlic.com/~lynn/2001l.html#32 mainframe question
http://www.garlic.com/~lynn/2002b.html#44 PDP-10 Archive migration plan
http://www.garlic.com/~lynn/2002n.html#71 bps loader, was PLX
http://www.garlic.com/~lynn/2002p.html#56 cost of crossing kernel/user boundary
http://www.garlic.com/~lynn/2002p.html#64 cost of crossing kernel/user boundary
http://www.garlic.com/~lynn/2003f.html#12 Alpha performance, why?
http://www.garlic.com/~lynn/2003f.html#14 Alpha performance, why?
http://www.garlic.com/~lynn/2003f.html#20 Alpha performance, why?
http://www.garlic.com/~lynn/2003f.html#23 Alpha performance, why?
http://www.garlic.com/~lynn/2003f.html#26 Alpha performance, why?
http://www.garlic.com/~lynn/2003f.html#30 Alpha performance, why?
http://www.garlic.com/~lynn/2003n.html#45 hung/zombie users ... long boring, wandering story
http://www.garlic.com/~lynn/2004b.html#26 determining memory size
http://www.garlic.com/~lynn/2004g.html#45 command line switches [Re: [REALLY OT!] Overuse of symbolic constants]
http://www.garlic.com/~lynn/2004o.html#9 Integer types for 128-bit addressing
http://www.garlic.com/~lynn/2005f.html#10 Where should the type information be: in tags and descriptors
http://www.garlic.com/~lynn/2005f.html#16 Where should the type information be: in tags and descriptors
http://www.garlic.com/~lynn/2006.html#35 Charging Time
http://www.garlic.com/~lynn/2006.html#40 All Good Things

--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn/

The Pankian Metaphor

From: Anne & Lynn Wheeler <lynn@garlic.com>
Subject: Re: The Pankian Metaphor
Newsgroups: alt.folklore.computers
Date: Sun, 14 May 2006 12:17:16 -0600

jmfbahciv writes:

And then airlines got busy.  Was there anything academic that
had a similar effect?

for a little drift, sometime after we took the early out in 92, one of
the major airline res systems were talking to us about the ten
impossible things that they couldn't do.

i went away and a couple months later came back with an implementation
that solved all ten impossible things. that was when they started
wringing their hands ... and eventually let slip that they actually
didn't want us to solve the problems ... they just wanted to be able
to tell the board that we were consulting on the problems for the next
decade.

the issue was that many of the impossible things were a result of
there being a large staff manually performing many of the steps. if
all the manual steps were automated, then much of the difficulty went
away and things got much simpler. some of this had all been layed down
based on the technology of the 60s and never really revisited
(technology may have been looked at over the years for some
straight-forward, linear scaling but never from the standpoint of
enabling fundamental paradigm change).

to some extent, the status of the executive in-charge was related to
the size of the organization. if the size of the organization was cut
by three orders of magnitude, then the executive's status was also
impacted.

various past posts mentioning airline res systems (only some
referring to this particular incident):
http://www.garlic.com/~lynn/99.html#17 Old Computers
http://www.garlic.com/~lynn/99.html#100 Why won't the AS/400 die? Or, It's 1999 why do I have to learn how to use
http://www.garlic.com/~lynn/99.html#103 IBM 9020 computers used by FAA (was Re: EPO stories (was: HELP IT'S HOT!!!!!))
http://www.garlic.com/~lynn/99.html#136a checks (was S/390 on PowerPC?)
http://www.garlic.com/~lynn/2000f.html#20 Competitors to SABRE?
http://www.garlic.com/~lynn/2001.html#26 Disk caching and file systems.  Disk history...people forget
http://www.garlic.com/~lynn/2001d.html#69 Block oriented I/O over IP
http://www.garlic.com/~lynn/2001g.html#45 Did AT&T offer Unix to Digital Equipment in the 70s?
http://www.garlic.com/~lynn/2001g.html#49 Did AT&T offer Unix to Digital Equipment in the 70s?
http://www.garlic.com/~lynn/2001j.html#17 I hate Compaq
http://www.garlic.com/~lynn/2001n.html#0 TSS/360
http://www.garlic.com/~lynn/2001n.html#3 News IBM loses supercomputer crown
http://www.garlic.com/~lynn/2002g.html#2 Computers in Science Fiction
http://www.garlic.com/~lynn/2002g.html#3 Why are Mainframe Computers really still in use at all?
http://www.garlic.com/~lynn/2002h.html#12 Why did OSI fail compared with TCP-IP?
http://www.garlic.com/~lynn/2002h.html#43 IBM doing anything for 50th Anniv?
http://www.garlic.com/~lynn/2002i.html#83 HONE
http://www.garlic.com/~lynn/2002j.html#83 Summary: Robots of Doom
http://www.garlic.com/~lynn/2002m.html#67 Tweaking old computers?
http://www.garlic.com/~lynn/2003.html#48 InfiniBand Group Sharply, Evenly Divided
http://www.garlic.com/~lynn/2003c.html#30 diffence between itanium and alpha
http://www.garlic.com/~lynn/2003d.html#67 unix
http://www.garlic.com/~lynn/2003k.html#3 Ping:  Anne & Lynn Wheeler
http://www.garlic.com/~lynn/2003n.html#47 What makes a mainframe a mainframe?
http://www.garlic.com/~lynn/2004b.html#6 Mainframe not a good architecture for interactive workloads
http://www.garlic.com/~lynn/2004e.html#44 Infiniband - practicalities for small clusters
http://www.garlic.com/~lynn/2004f.html#58 Infiniband - practicalities for small clusters
http://www.garlic.com/~lynn/2004g.html#14 Infiniband - practicalities for small clusters
http://www.garlic.com/~lynn/2004l.html#6 Xah Lee's Unixism
http://www.garlic.com/~lynn/2004o.html#23 Demo: Things in Hierarchies (w/o RM/SQL)
http://www.garlic.com/~lynn/2004o.html#29 Integer types for 128-bit addressing
http://www.garlic.com/~lynn/2004p.html#26 IBM 3614 and 3624 ATM's
http://www.garlic.com/~lynn/2004q.html#85 The TransRelational Model: Performance Concerns
http://www.garlic.com/~lynn/2005.html#22 The Soul of Barb's New Machine (was Re: creat)
http://www.garlic.com/~lynn/2005.html#41 something like a CTC on a PC
http://www.garlic.com/~lynn/2005c.html#67 intel's Vanderpool and virtualization in general
http://www.garlic.com/~lynn/2005e.html#47 Using the Cache to Change the Width of Memory
http://www.garlic.com/~lynn/2005f.html#22 System/360; Hardwired vs. Microcoded
http://www.garlic.com/~lynn/2005n.html#44 What was new&important in computer architecture 10 years ago ?
http://www.garlic.com/~lynn/2005o.html#44 Intel engineer discusses their dual-core design
http://www.garlic.com/~lynn/2005q.html#7 HASP/ASP JES/JES2/JES3
http://www.garlic.com/~lynn/2006d.html#5 IBM 610 workstation computer

--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn/

virtual memory

From: Anne & Lynn Wheeler <lynn@garlic.com>
Subject: Re: virtual memory
Newsgroups: comp.arch,alt.folklore.computers
Date: Sun, 14 May 2006 13:04:45 -0600

Anne & Lynn Wheeler writes:

the other thing that was starting to happend by the second half of
the 70s was things were starting to shift from being real memory
constrained to being much more disk arm constrained.

another characteristic of the real memory resource vis-a-vis disk
resource trade-off was the original os/360 design using CKD DASD.

the disk technology was referred to count-key-data ... it was possible
to format disk space with specified record sizes and tag each record
with various flags and attributes (not the fixed record size and
sequential numbered records that you find in much of today's much more
familiar disk technology). os/360 made a decision about conserving
real storage requirements by leaving the disk layout information
resident on disk. the "VTOC" (volume table of contents, somewhat akin
to a MFD/master file directory) had the individual records labled.
When there was a request to open some file, an I/O request was built
by the system to "search" the VTOC for the required information.

a similar design trade-off was created for file libraries that had a
special file format called PDS (partitioned data set) that included a
on-disk directory of all the members in the file. when there was a
request to retrieve a specific library member, there was an I/O
request built by the system to do ("multi-track") search of the PDS
directory for the required information.

these two design trade-offs required exorbitant amounts of disk I/O
resources ... however, the savings in scarce real memory resource was
deemed to be a reasonable trade-off.

roll-forward to mid-70s ... when the amounts of available real memory
was starting to dramatically increase ... and the improvement in disk
throughput was dramatically falling behind the thruput improvement of
other system components. as a result, major system bottleneck was
shifting from real storage to disk activity.

a widely deployed disk drive was the 3330 (a lots of other vendors
produced clones of the 3330 that made their way into a variety of
systems). it had 20 surfaces and 20 heads per (cylinder) arm position
... only 19 of the heads were addressable (the 20th head was used for
something called rotational position sensing). the device spun at 3600
rpm ... or 60 revolutions per second. a multi-track search of a
multi-cylinder PDS directory took approx. 1/3 of a second elapsed time
... per cylinder (arm position). The avg. elapsed time to find a
member in a large program library could take 1/2 second or more
elapsed time.

in the late 70s, a very large national retailer was starting to
experience severe performance degradation of its in-store, online
applications.  the retailer had its stores organizied into regions
... and the datacenter had dedicated processor complex per
region. however, all the processor complexes had shared access to a
large common pool of disks. there was a single large application
library for the online, in-store operations that was shared across all
the dedicated regional processor complexes.

over period of several months, numerous people had been brought in
attempting to diagnose the problem. finally i was brought into a class
room that was had a dozen or so long class tables. all the tables were
nearly covered with high stacks of paper performance reports from all
the operating systems.

people were expected to scan the performance reports looking for
resource activity that corresponded with periods of extremely poor
performance. the problem was that most people were accustomed to
looking at extremely high activity counts as an indication of
bottlenecked resources. all the periodic disk i/o counts failed to
indicated any specific disk in the large pool (disk drives in the
large score of drives) with high i/o count activity.

one problem was that the performance reports gave interval i/o
activity counts by disk for specific processor complex. to get the
total i/o activity for a disk ... you had to manually sum the i/o
count activity per processor complex across all the processor
complexes. the other problem was that there was no actual service time
numbers or queuing delay numbers ... just raw activity counts.

I started quickly scanning the piles of paper and after maybe 20-30
minutes started to realize that a specific disk drive had an aggregate
activity count consistently of approx. 6-7 operations per second
during the periods of bad performance and thruput. it wasn't normally
considered a high i/o rate ... but it started to appear to be the only
value that consistently correlated with periods of poor performance.
all the other values reported in the reams of paper performance data
appeared to pretty much randomly varying all over the place.

zero'ing in on that particular disk ... closer examination showed that
it was typically doing a full-cylinder multi-track search of the PDS
directory (to find a library member to load) taking nearly 1/3rd
second elapsed time ... followed by reading the library memory (taking
a couple tens of millisecond). basically the whole national datacenter
complex was reduced to loading an aggregate of three application
library programs per second.

all the system configuration easily had sufficient real memory for
caching the PDS directory of library members ... and the in-store
application load would be reduced to possibly 10-15milliseconds rather
than 340milliseconds. however, the system implementation structure had
been cast in concret from the mid-60s ... so they had to find other
compensating procedures to speed up in-store application load.

furthermore, within a few years, typical system configurations would
not only be able to cache the directory of members but also all the
members themselves.

misc. past posts about the 60s ckd-disk/storage performance trade-off
and its lingering effects long after it was no longer valid
http://www.garlic.com/~lynn/subtopic.html#dasd

--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn/

ALternatives to EMail

From: Anne & Lynn Wheeler <lynn@garlic.com>
Subject: Re: ALternatives to EMail
Newsgroups: alt.folklore.computers
Date: Sun, 14 May 2006 13:24:44 -0600

"Sam Alexander" writes:

Just curious ...

Though the protocols used in EMail are still very reliable, with so
much spyware and so many filters for me anyway email has started
becoming more and more less reliable.  I was wondering what other
email applications of the past you'd choose to used if modern day
Internet Emai was to be gone tomorrow.  Would you go back to Fidonet
netmail?  What about telex or other such messages?  Just curious.

there were a large variety of value added networks (VANs) that sprung
up ... some as early as the 70s ... but lots in the 90s ... that had
all sorts of proprietary formats for conveying information. the
existance of some of this VANs contributed to the EDI standardization
efforts.

the proliferation of the internet pretty much turned the VANs of the
70s and 80s into dinosaurs.

however, there are issues with social engineering and hostile intent
when there is relatively free any-to-any connectivity across the whole
world.

note that the internal network
http://www.garlic.com/~lynn/subnetwork.html#internalnet

was larger than the internet
http://www.garlic.com/~lynn/internet.htm
http://www.garlic.com/~lynn/subnetwork.html#internet

from just about the beginning until sometime mid-85.

there was also bitnet and earn which was larger than "internet" (more
nodes) during a period in the early 80s. note that while bitnet/earn
used similar technology to that used in the internal network ... they
were considered totally separate networks (the count of nodes in the
two networks were total different).
http://www.garlic.com/~lynn/subnetwork.html#bitnet

the internal network also evolved its own information distribution ala
usenet ... a portion of that appeared in bitnet/earn as "listserv" and
somewhat exists today in the usenet bit.listserv.* group hierarchy.

--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn/

Value of an old IBM PS/2 CL57 SX Laptop

From: Anne & Lynn Wheeler <lynn@garlic.com>
Subject: Re: Value of an old IBM PS/2 CL57 SX Laptop
Newsgroups: alt.folklore.computers
Date: Sun, 14 May 2006 13:53:23 -0600

greymaus writes:

Besides that, PayPal seens useful, but I got in a humour over my first
purchase from eBay, didn't send back the confirming number, and PayPal
wants me to try again under a different CC number, which, as CC's are
subject to a yearly tax here (Ireland), is a bit much. For a while
there, a lot of Internet commerce sites were moving to PayPal, but
that process seems to have stopped.

some more drift along this topic

3 of the big 4 - all doing payment systems
https://www.financialcryptography.com/mt/archives/000715.html

and various comments along the way:
http://www.garlic.com/~lynn/aadsm23.htm#35 3 of the big 4 - all doing payment systems
http://www.garlic.com/~lynn/aadsm23.htm#36 3 of the big 4 - all doing payment systems
http://www.garlic.com/~lynn/aadsm23.htm#37 3 of the big 4 - all doing payment systems

--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn/

The Chant of the Trolloc Hordes

From: Anne & Lynn Wheeler <lynn@garlic.com>
Subject: Re: The Chant of the Trolloc Hordes
Newsgroups: alt.folklore.computers
Date: Sun, 14 May 2006 14:04:19 -0600

scott@slp53.sl.home (Scott Lurndal) writes:

A few megabyte database fits comfortably in memory.   Sleepycat?

trivia question ... what connection between sleepycat and
following mention of log structured file system and geographic
survivability:
http://www.garlic.com/~lynn/2006j.html#3 virtual memory

work in ha/cmp
http://www.garlic.com/~lynn/subtopic.html#hacmp

--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn/

The Pankian Metaphor

From: Anne & Lynn Wheeler <lynn@garlic.com>
Subject: Re: The Pankian Metaphor
Newsgroups: alt.folklore.computers
Date: Mon, 15 May 2006 06:44:49 -0600

Charles Shannon Hendrix writes:

That's true, but you can help this a bunch by doing things like
reducing or removing the cost of swapping pages out.

For example, don't mark swap pages free when bringing pages into
RAM. That way if they need to be swapped back out, you can do it
nearly for free and without paging I/O.

A set of patches to the Linux 2.6.x kernels does this, among other
things, and it helps a lot for both interactive and server loads.

this is the subject of recent "dup"/"no-dup" (duplicate/no-duplicate)
post. retaining previous position can save a page-write when
replacing pages that haven't been changed.
http://www.garlic.com/~lynn/2006i.html#41 virtual memory

however, "no-duplicate" gives up that saved position ... which can
optimize use of available space ... especially in hierarchy of
cache/swap ... references to mix of fixed-head & non-fixed-head paging
devices (2305/3330) or caching controllers (3880-11/ironwood)
mentioned in above.

however, the aspect of saving a page write can be taken to the extreme
... as in this post that includes description of original os/vs2
implementation to specifically bias replacement strategy for
non-changed pages (and saving page write)
http://www.garlic.com/~lynn/2006i.html#43 virtual memory

note, "big pages" went to writing everything ... not for conserving
space allocation ... but to have pages likely to be used together to
be contiguously located on disk ... so later retrieval could be made
in single i/o operation. this happened with realization that primary
system bottleneck shifting away from being real storage constrained to
disk arm access constrained ... and it was possible to trade-off
optimization of real storage utilization against disk arm access
optimization.
http://www.garlic.com/~lynn/2006j.html#2 virtual memory

--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn/

History of first use of all-computerized typesetting?

From: Anne & Lynn Wheeler <lynn@garlic.com>
Subject: Re: History of first use of all-computerized typesetting?
Newsgroups: alt.folklore.computers
Date: Mon, 15 May 2006 07:37:29 -0600

Charles Shannon Hendrix writes:

Not just that, but the phenomenom where people believe anything that
is in print, and it often doesn't even matter who it came from.

It used to be that way for news over the radio, but I don't know if
it is still that way now or not. I.E. "War of the Worlds!"
broadcast.

At various workplaces I have noticed that talking in person or even
sending email is often ignored.

But print it up as a memo, especially on company letterhead, and the
story is different. They'll believe almost anything if you "make it
official".

I told a manager this in one shop where I worked and he didn't
believe me. "No one is that stupid", he told me.

story about password guidelines being printed on corporate
letterhead and placed in corporate bulletin board
http://www.garlic.com/~lynn/99.html#52 Enter fonts
http://www.garlic.com/~lynn/2001d.html#51 OT Re: A beautiful morning in AFM.
http://www.garlic.com/~lynn/2001d.html#52 OT Re: A beautiful morning in AFM.
http://www.garlic.com/~lynn/2001d.html#53 April Fools Day

--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn/

virtual memory

From: Anne & Lynn Wheeler <lynn@garlic.com>
Subject: Re: virtual memory
Newsgroups: comp.arch,alt.folklore.computers
Date: Mon, 15 May 2006 07:44:19 -0600

robert.thorpe writes:

Yes.  My point was not that others weren't mentioned so much as they
were mentioned only as bylines.

Posting a deluge of information about IBM work, may give the impression
to casual the reader that IBM were initially innovative in that area.
When in fact, despite being the largest, they were only the third
computer company to implement virtual memory.  They became innovative
in it AFAIK once they started doing it, fairly much straight away, but
that was years after the first examples had been made.

no mostly, i was posting stuff primarily about my work and products I
shipped ... as an undergraduate
http://www.garlic.com/~lynn/subtopic.html#wsclock
and then as an employee at the science center
http://www.garlic.com/~lynn/subtopic.html#545tech

i wasn't prepared to particularly write a lot about stuff about work
that other people had done. it wasn't that i was particularly trying
to bias against work that other people had done ... but i wasn't as
qualified to write about other peoples' work as i was able to write
about the work that i had done.

i was mostly including bylines about other people's work as an
indication that i wasn't the only person that had done work in the
area.

--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn/

virtual memory

From: Anne & Lynn Wheeler <lynn@garlic.com>
Subject: Re: virtual memory
Newsgroups: comp.arch,alt.folklore.computers
Date: Mon, 15 May 2006 08:36:03 -0600

Jan Vorbrüggen writes:

Yes, that was the philosophy behind the VMS working set design: They
called it "paging against the process" vs "paging against the
system" for the global approach.

The first implementation only had quotas that were also limits. This
fit the initial hardware - our first VAX-11/780 had 256 _k_Byte of
system memory - but did not fit systems even a few years
later. There, one had the situation that one wanted to have low
quota - to make sure that at 11 a.m. with the maximum number of
users logged in, the system didn't bog down with paging - but allow
a user at other times to use much more real memory when contention
was low. This was solved by introducing limits that could be much
higher.  In essence, the limit was the max amount of real memory
your process could get, and the quota was the min amount.

The restriction that all working set lists had to be the same,
boot-time size that used up non-virtual memory was a VAX hardware
feature. The Alpha with its later VM incarnation does not have this
feature.

I never had that ... dating back to my original implementations
in the 60s.

working set size was mechanism for limiting over commit of real
storage and resulting page thrashing ... pathelogical case was that
you needed a page that wasn't in real storage, had a page fault,
waiting for the page was brought in and by the time that page was
ready ... other pages that you required had been stolen; worst case
was no progress got made (since all tasks were constantly stealing
pages from each other).

working set size was mechanism for managing/limiting concurrent
competition for available real storage.

global LRU replacement was mechanism for making sure that the
optimal set of all pages were resident and ready for use in
real storage.

as real storage got more plentiful ... starting by at least the later
part of the 70s ... there were other techniques used to manage amount
of paging. one strategy that had been developed in the late 70s
... was tracking per task pagewait time (i.e. bottleneck had shifted
from constrained real storage to constrained disk i/o ... from the 60s
there was inter-relationship between constrained real storage and the
amount of paging involving disk i/o, however, moving into the late 70s
... requests could start queueing against disk, even with relatively
little real storage contention).

part of the issue was the characteristic somewhat written up as
"strong" and "weak" working sets ... i.e. the set of actual pages
required were strongly consistent over a period ... versus somewhat
changing. the set "size" over time could be the same in both ...  but
once "strong" working set had been established, the task would run
with no additional paging operation. in weak working set, once the
initial set had been established ... there would continue to be paging
over time (the size of the set didn't change, but the members of the
set changed over time).

to try and handle this situation ... there were implementations that
modified global LRU replacement strategy based on task progress (or
its inverse, amount of pagewait); a task making little progress
(higher pagewait) ... would have some percentage of its pages selected
by global LRU ... skipped i.e. global LRU would select pages from the
task, but because the task was making less progress than its target,
some percentage of its selected pages would be retained ... global LRU
would then skip past the selected page and search for another. the
percentage of pages initially selected by global LRU replacement
strategy ... but then skipped ... would be related to how much
progress the task was making vis-a-vis the objective. this tended to
lower the pagewait time for tasks that had somewhat weak working sets
that were getting behind schedule.

the issue here was that available real storage tended to be much
larger than the aggregate of the concurrent working set sizes ... so
use of aggregate working set size to limit the number of contending
tasks as mechanism for limiting paging was ineffective. global LRU
still provided that the optimal set of global pages were
resident. however, tasks with strong working sets might have advantage
over tasks with weaker working sets. as a result, a mechanism was
provided to reduce the rate of pages stolen for those tasks (typically
from tasks with weaker working sets) that were getting behind schedule
in their targeted resource consumption (because of time spent in
pagewait).

for the other scenario ... for tasks with extremely weak working set
... and even all avaiable real storage provided them little or no
additional benefit ... there was a strategy for "self-stealing"
... aka a form of local LRU ... but that was only for limiting the
effects of extremely pathelogical behavior ... it wasn't used for task
operating with normal operational characteristics.

something similar was found in the detailed analysis of disk record
caching designs.
http://www.garlic.com/~lynn/2006i.html#41 virtual memory

given detailed tracing of all disk record access across a wide
range of different live operational environments ... for a given
fixed amount of total electronic memory ... and all other things
being equal ... using the memory for a single global system
cache provided better thruput than dividing/partitioning
the memory into sub-components.

this was the case of instead of using all the fixed amount of
electronic memory for a single global system cache, the available
fixed amount of electronic memory would be divided up and used in
either controller-level caches (as in the reference to 3880-11 and
3880-13 controller caches) and/or disk-level caches.

there were two caveats; some amount of electronic store was useful at
the disk head level for staging full track of data as rotational delay
mitigation and you needed strategy to minimize caching of purely
sequential i/o ... where caching provided no benefit; i.e. for
sequential i/o ... it basically violated basic assumption behind least
recently used replacement strategies ... that records/pages used
recently would be used in the near future. for that behavior, a "most
recently used" replacement strategy would be more ideal ... which can
also be expressed as "self-stealing" ... new request replaces previous
request by same task (trying to avoid a purely sequential i/o transfer
from wiping out all other existing cache entries).

and in its analogy back to paging as a form of cache and its
relationship to least recently used replacement strategy ... past a
certain point, extremely weak working sets ... can appear to be very
little different from sequential transfer.

posts in this thread:
http://www.garlic.com/~lynn/2006i.html#22 virtual memory
http://www.garlic.com/~lynn/2006i.html#23 Virtual memory implementation in S/370
http://www.garlic.com/~lynn/2006i.html#24 Virtual memory implementation in S/370
http://www.garlic.com/~lynn/2006i.html#28 virtual memory
http://www.garlic.com/~lynn/2006i.html#30 virtual memory
http://www.garlic.com/~lynn/2006i.html#31 virtual memory
http://www.garlic.com/~lynn/2006i.html#32 virtual memory
http://www.garlic.com/~lynn/2006i.html#33 virtual memory
http://www.garlic.com/~lynn/2006i.html#36 virtual memory
http://www.garlic.com/~lynn/2006i.html#37 virtual memory
http://www.garlic.com/~lynn/2006i.html#38 virtual memory
http://www.garlic.com/~lynn/2006i.html#39 virtual memory
http://www.garlic.com/~lynn/2006i.html#40 virtual memory
http://www.garlic.com/~lynn/2006i.html#41 virtual memory
http://www.garlic.com/~lynn/2006i.html#42 virtual memory
http://www.garlic.com/~lynn/2006i.html#43 virtual memory
http://www.garlic.com/~lynn/2006j.html#0 virtual memory
http://www.garlic.com/~lynn/2006j.html#1 virtual memory
http://www.garlic.com/~lynn/2006j.html#2 virtual memory
http://www.garlic.com/~lynn/2006j.html#3 virtual memory
http://www.garlic.com/~lynn/2006j.html#4 virtual memory
http://www.garlic.com/~lynn/2006j.html#5 virtual memory
http://www.garlic.com/~lynn/2006j.html#12 virtual memory

--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn/

30 hop limit

From: Anne & Lynn Wheeler <lynn@garlic.com>
Subject: Re: 30 hop limit
Newsgroups: comp.protocols.tcp-ip
Date: Mon, 15 May 2006 09:46:13 -0600

"Albert Manfredi" writes:

So we are saying the same thing. Routing in IP can change at the drop
of a hat, but that's a far cry from any implication that the routes
are random. They are calculated and they are stable, unless something
in the network causes them to change.

Also strayed off topic, but at least it's an interesting topic.

when we were working on the original payment gateway
http://www.garlic.com/~lynn/aadsm5.htm#asrn2
http://www.garlic.com/~lynn/aadsm5.htm#asrn3

we were looking at doing high availability configuration,
in part because we had earlier done the ha/cmp product
http://www.garlic.com/~lynn/subtopic.html#hacmp

for some trivia drift ... some of the people in this ha/cmp meeting
http://www.garlic.com/~lynn/95.html#13

later showed up at a small client/server startup responsible for
turning out a payment gateway. this small client/server startup also
had this technology called SSL.

in any case during the process of initial deployment ... we were
looking at advertising routes for ip-addresses as countermeasure to
various kinds of route outages. however, in that period, the internet
backbone decided to move to hierachical routing.  we had assumed that
we could get diverse physical routing to some number of different,
carefully selected ISPs. If any of the ISPs were having connectivity
problems (like taking down critical components on sunday afternoon
prime-time for maintenance) we could advertise routes via other paths.

the transition to hierarchical routing eliminated attention being paid
to alternate advertise routes. that primarily left multiple a-records
as an alternate path mechanism (i.e. same domain/host name mapping to
a list of different ip-addresses).

--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn/

Resolver Issue (was Revolver Issue)

From: Anne & Lynn Wheeler <lynn@garlic.com>
Subject: Re: Resolver Issue (was Revolver Issue)
Newsgroups: bit.listserv.ibm-main,alt.folklore.computers
Date: Mon, 15 May 2006 11:29:52 -0600

eric-phmining@ibm-main.lst (Eric N. Bielefeld) writes:

I used to look at the list online.  The biggest problem I had is
remembering where you were.  If I forgot to write down the post
number, it was hard to find just where I left off.  Also, the only
quick way to navigate from post to post was to click on the next
button.  If I had to do something else and I was half way through the
posts overnight, it was hard to figure out where I left off.  Our
internet connection at work made you log back on if you didn't use it
for 20 minutes or so.

i've been using various flavors of gnus/emacs usenet newsreaders for
going on close to 20 years. it has always kept track of all that stuff.

virtual memory

From: Anne & Lynn Wheeler <lynn@garlic.com>
Subject: Re: virtual memory
Newsgroups: comp.arch,alt.folklore.computers
Date: Mon, 15 May 2006 14:50:28 -0600

"Eric P." writes:

As I understand it, one key issue is what happens after the
page falls out of the working set.

From what I have read, the basic Denning working set model circa 1968
had each page make one trip through a fifo list. This was later
enhanced to use a reference bit and a make two or more trips if the
page was referenced (due to performance analysis by Belady and others).

In the Denning model, when a page was pushed out of the working
set, if it was modified it was written back to file.
In any case after that the frame went onto the free list and
*** note *** all connection between it and its process was lost even
though its contents were still valid and even if there were lots of
free pages. If the page was touched again it was brought in from disk.

This meant there was a high cost to evicting a working set page so
it would be avoided by having larger working sets, yada, yada, yada.

Unlike Denning, VMS retains a link to the evicted page so that
if it is touched again before the frame is assigned to someone else,
that it can be pulled back into the working set quickly.
(They just reset the PTE valid bit but leave the frame number valid.
If the owner touches it again, it just flips the PTE to valid.
If the page is grabbed for someone else, then the PFN gets zapped.)

This allows VMS to toss pages out of its working sets at low cost,
which allows them to roll over working sets more often.
In theory this mitigates the bad effects of the Denning fifo model.

So the question I was curious about is to what extent Grenoble
was like Denning .vs. like VMS.

note that was what i did in the late '60s in global LRU ...  and it
was retained in the grenoble local LRU implementation ...  the
reclaiming of pages back into the working set was like what i had done
as an undergraduate in the 60s and shipped in cp67 (prior to grenoble
doing their local LRU stuff ... which leveraged the already existing
graceful reclaim).

i ran into something like that in the very late 70s. neither tss/360
(which had been implemented before i had done any work on cp67) nor
mvs gracefully reclaimed pages that had been selected as having
moved out of working set.

the flavor of global LRU and trashing controls that i had done for
cp67 as an undergraduate in the 60s ... had very graceful reclaim of
any virtual page still in real storage.

i had argument with the initial os/vs2 implementation over 1)
selecting non-changed pages before changed pages as abnormally
peverting the fundamental principles of least recently used
replacement strategy ... previous discussion of the subject
http://www.garlic.com/~lynn/2006i.html#43 virtual memory
http://www.garlic.com/~lynn/2006j.html#5 virtual memory
http://www.garlic.com/~lynn/2006j.html#11 The Pankian Metaphor

and 2) "graceful reclaim" (i.e. recover virtual page if it
was still resident in real storage).

Well into the os/vs2 mvs release cycles in the late 70s ... they
discovered that #1 was selecting high-used, shared (across multiple
address spaces) executables before low-used, private (changed) data
pages.

In the very late 70s, I had gotten a call from somebody in POK, they
had just gotten a big corporate award for adding graceful reclaim to
mvs and was wondering if he could do something similar for vm370.

I commented that I had never not done it that way since as
undergraduate more than a decade earlier in the 60s .... and never
could figure out why anybody would have ever not done graceful
reclaim; aka no, he was not able to get another big corporate award
for doing something similar to vm370 ... and furthermore, from my
standpoint there should have never been a large corporate award for
adding graceful ... instead the people that had done the original
implementation, that didn't include graceful reclaim, should have been
severely penalized.

--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn/

virtual memory

From: Anne & Lynn Wheeler <lynn@garlic.com>
Subject: Re: virtual memory
Newsgroups: comp.arch,alt.folklore.computers
Date: Mon, 15 May 2006 15:05:41 -0600

David Scheidt writes:

LRU has the disadvantage of having to update the list of when a page
is used at every access.  FIFO avoids that.  With a second-chance
mechanism, it's not obvious that it wouldn't work well.

clock and global LRU uses an LRU approximation ... that kind of sorts
pages into two categories ... those that have their reference bit used
since the last examination/reset, and those that haven't had their
reference bit used since their last examination/reset.

we did significant simulation with full instruction traces
some of it was part of the vs/repack technology previously
referenced
http://www.garlic.com/~lynn/2006i.html#37 virtual memory

where in detailed simulation with full instruction traces of
i-refs, d-refs, and d-stores ... compared lots of global and
local lru approximations as well as "true" lru ... where
exact ordering of page references were maintained.

the clock approach to lru approximation (that i had come up with as an
undergraduate in the 60s) ... which is also described in Carr's phd
thesis previously mentioned (and can be found online) misc. recent
past posts mentioning Carr's thesis
http://www.garlic.com/~lynn/2006i.html#37 virtual memory
http://www.garlic.com/~lynn/2006i.html#38 virtual memory
http://www.garlic.com/~lynn/2006i.html#42 virtual memory

R. Carr, Virtual Memory Management, Stanford University,
STAN-CS-81-873 (1981)

R. Carr and J. Hennessy, WSClock, A Simple and Effective Algorithm
for Virtual Memory Management, ACM SIGOPS, v15n5, 1981

.... typically operated within 10-15percent of "true" lru with
extremely nominal overhead (based on the detailed simulation). their
was no list manipulation at all, just the cyclic examination ... which
was approx. six instructions per page examined and not taken ... and
the avg. depth of search typically avg. six pages before finding a
page to select (i.e. on the order of 36 instructions to find and
select a page for replacement).

during this period with the work on extensive full instruction traces
and analysis of wide variety of replacement strategies ... both real
implementation in live deployment and the extensive simulation and
modeling work ... I discovered a coding hack that allowed a kind of
clock operation to actual beat "true" LRU ... the instructions and
pathlength was identical to regular clock ... but there was a coding
slight of hand the resulted in being able to beat "true" LRU (based on
the detailed simulation work). post in this thread mentioning the
detailed simulation work, comparing the LRU approximations with "true"
LRU ... and coming up with the slight-of-hand clock that would beat
"true" LRU
http://www.garlic.com/~lynn/2006i.html#42 virtual memory

posts in this thread:
http://www.garlic.com/~lynn/2006i.html#22 virtual memory
http://www.garlic.com/~lynn/2006i.html#23 Virtual memory implementation in S/370
http://www.garlic.com/~lynn/2006i.html#24 Virtual memory implementation in S/370
http://www.garlic.com/~lynn/2006i.html#28 virtual memory
http://www.garlic.com/~lynn/2006i.html#30 virtual memory
http://www.garlic.com/~lynn/2006i.html#31 virtual memory
http://www.garlic.com/~lynn/2006i.html#32 virtual memory
http://www.garlic.com/~lynn/2006i.html#33 virtual memory
http://www.garlic.com/~lynn/2006i.html#36 virtual memory
http://www.garlic.com/~lynn/2006i.html#37 virtual memory
http://www.garlic.com/~lynn/2006i.html#38 virtual memory
http://www.garlic.com/~lynn/2006i.html#39 virtual memory
http://www.garlic.com/~lynn/2006i.html#40 virtual memory
http://www.garlic.com/~lynn/2006i.html#41 virtual memory
http://www.garlic.com/~lynn/2006i.html#42 virtual memory
http://www.garlic.com/~lynn/2006i.html#43 virtual memory
http://www.garlic.com/~lynn/2006j.html#0 virtual memory
http://www.garlic.com/~lynn/2006j.html#1 virtual memory
http://www.garlic.com/~lynn/2006j.html#2 virtual memory
http://www.garlic.com/~lynn/2006j.html#3 virtual memory
http://www.garlic.com/~lynn/2006j.html#4 virtual memory
http://www.garlic.com/~lynn/2006j.html#5 virtual memory
http://www.garlic.com/~lynn/2006j.html#12 virtual memory
http://www.garlic.com/~lynn/2006j.html#13 virtual memory
http://www.garlic.com/~lynn/2006j.html#14 virtual memory
http://www.garlic.com/~lynn/2006j.html#17 virtual memory

--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn/

virtual memory

From: Anne & Lynn Wheeler <lynn@garlic.com>
Subject: Re: virtual memory
Newsgroups: comp.arch,alt.folklore.computers
Date: Mon, 15 May 2006 15:22:40 -0600

Anne & Lynn Wheeler writes:

.... typically operated within 10-15percent of "true" lru with
extremely nominal overhead (based on the detailed simulation). their
was no list manipulation at all, just the cyclic examination ... which
was approx. six instructions per page examined and not taken ... and
the avg. depth of search typically avg. six pages before finding a
page to select (i.e. on the order of 36 instructions to find and
select a page for replacement).

re:
http://www.garlic.com/~lynn/2006j.html#18 virtual memory

oops, that was six instructions on the 360/67. the changed & reference
bits were maintained in the storage keys ... which were for 2k blocks
of storage ... and paging was done on 4k blocks. the result was that
cp67 had to check two sets of changes&reference bits to get the result
for a single 4k page. the bits had to be retrieved and then stored
back with value reset. also since cp67 was not only providing virtual
memory paging management but also providing virtual machine simulation
... whatever the real hardware changed&reference bits were before the
reset, had to be copied/shadowed to the virtual machine values.

this was slightly reduced in the move from 360/67 to 370 ... since the
370 provided a single instruction that would retrieve, interrogate and
reset the reference bit in a single instruction (although for correct
virtual machine emulation, there still requirement to shadow the
reference bit value, prior to reset, for the virtual machine).

some recent posts mentioning various shadowing requirements for correct
virtual machine:
http://www.garlic.com/~lynn/2006c.html#36 Secure web page?
http://www.garlic.com/~lynn/2006e.html#0 About TLB in lower-level caches
http://www.garlic.com/~lynn/2006e.html#6 About TLB in lower-level caches
http://www.garlic.com/~lynn/2006e.html#7 About TLB in lower-level caches
http://www.garlic.com/~lynn/2006e.html#12 About TLB in lower-level caches
http://www.garlic.com/~lynn/2006e.html#19 About TLB in lower-level caches
http://www.garlic.com/~lynn/2006e.html#20 About TLB in lower-level caches
http://www.garlic.com/~lynn/2006e.html#37 The Pankian Metaphor
http://www.garlic.com/~lynn/2006f.html#5 3380-3390 Conversion - DISAPPOINTMENT
http://www.garlic.com/~lynn/2006i.html#10 Hadware Support for Protection Bits: what does it really mean?
http://www.garlic.com/~lynn/2006i.html#24 Virtual memory implementation in S/370

--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn/

virtual memory

From: Anne & Lynn Wheeler <lynn@garlic.com>
Subject: Re: virtual memory
Newsgroups: comp.arch,alt.folklore.computers
Date: Mon, 15 May 2006 15:47:43 -0600

David Scheidt writes:

LRU has the disadvantage of having to update the list of when a page
is used at every access.  FIFO avoids that.  With a second-chance
mechanism, it's not obvious that it wouldn't work well.

possibly you are thinking of simulation of LRU for things like
database caches ... rather than processor paging that has hardware
support for reference and change bits ... and paging least recently
used replacement stragies that approximate LRU with approaches
like clock. ref:
http://www.garlic.com/~lynn/2006j.html#18 virtual memory
http://www.garlic.com/~lynn/2006j.html#19 virtual memory

in that situation, where the database cache entries have little or no
correspondance to any familiar hardware support for change/reference
bits ... then you might find a link-list of database cache
entries. the database manager can emulate least recently used of
database cache entries by updating a cache line link list whenever a
transaction requests a location of a database record (and it is found
in the cache) and the cache location is returned (i.e. remove the
found cache line from its current location in the linked list and move
it to the front of the list).

for some topic drift ... misc. posts mentioning working on
original relational/sql implementation
http://www.garlic.com/~lynn/subtopic.html#systemr

and in the previous incarnation of this subject
http://www.garlic.com/~lynn/2004i.html#0 Hard disk architecture: are outer cylinders still faster than inner cylinders?
http://www.garlic.com/~lynn/2004i.html#1 Hard disk architecture: are outer cylinders still faster than inner cylinders?
http://www.garlic.com/~lynn/2004i.html#8 Hard disk architecture: are outer cylinders still faster than inner cylinders?

it strayed into doing cross-cache transfers in conjunction with
the work on distributed lock manager for ha/cmp
http://www.garlic.com/~lynn/subtopic.html#hacmp

and a little more drift here
http://www.garlic.com/~lynn/95.html#13

misc. other past posts mentioning distribute lock manager work
http://www.garlic.com/~lynn/2000.html#64 distributed locking patents
http://www.garlic.com/~lynn/2001.html#40 Disk drive behavior
http://www.garlic.com/~lynn/2001c.html#66 KI-10 vs. IBM at Rutgers
http://www.garlic.com/~lynn/2001e.html#2 Block oriented I/O over IP
http://www.garlic.com/~lynn/2001e.html#4 Block oriented I/O over IP
http://www.garlic.com/~lynn/2001j.html#47 OT - Internet Explorer V6.0
http://www.garlic.com/~lynn/2001k.html#5 OT - Internet Explorer V6.0
http://www.garlic.com/~lynn/2002e.html#67 Blade architectures
http://www.garlic.com/~lynn/2002e.html#71 Blade architectures
http://www.garlic.com/~lynn/2002f.html#1 Blade architectures
http://www.garlic.com/~lynn/2002f.html#4 Blade architectures
http://www.garlic.com/~lynn/2002f.html#6 Blade architectures
http://www.garlic.com/~lynn/2002k.html#8 Avoiding JCL Space Abends
http://www.garlic.com/~lynn/2003i.html#70 A few Z990 Gee-Wiz stats
http://www.garlic.com/~lynn/2004i.html#1 Hard disk architecture: are outer cylinders still faster than inner cylinders?
http://www.garlic.com/~lynn/2004i.html#2 New Method for Authenticated Public Key Exchange without Digital Certificates
http://www.garlic.com/~lynn/2004i.html#8 Hard disk architecture: are outer cylinders still faster than inner cylinders?
http://www.garlic.com/~lynn/2004m.html#0 Specifying all biz rules in relational data
http://www.garlic.com/~lynn/2004m.html#5 Tera
http://www.garlic.com/~lynn/2004q.html#10 [Lit.] Buffer overruns
http://www.garlic.com/~lynn/2004q.html#70 CAS and LL/SC
http://www.garlic.com/~lynn/2004q.html#71 will there every be another commerically signficant new ISA?
http://www.garlic.com/~lynn/2005.html#40 clusters vs shared-memory (was: Re: CAS and LL/SC (was Re: High Level Assembler for MVS & VM & VSE))
http://www.garlic.com/~lynn/2005.html#55 Foreign key in Oracle Sql
http://www.garlic.com/~lynn/2005b.html#1 Foreign key in Oracle Sql
http://www.garlic.com/~lynn/2005f.html#18 Is Supercomputing Possible?
http://www.garlic.com/~lynn/2005f.html#32 the relational model of data objects *and* program objects
http://www.garlic.com/~lynn/2005h.html#26 Crash detection by OS
http://www.garlic.com/~lynn/2005i.html#42 Development as Configuration
http://www.garlic.com/~lynn/2006c.html#8 IBM 610 workstation computer
http://www.garlic.com/~lynn/2006c.html#41 IBM 610 workstation computer

--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn/

virtual memory

From: Anne & Lynn Wheeler <lynn@garlic.com>
Subject: Re: virtual memory
Newsgroups: comp.arch,alt.folklore.computers
Date: Mon, 15 May 2006 17:26:09 -0600

Brian Inglis writes:

Pool/subpool allocation seems advantageous in situations where, as
with OS control blocks, you sometimes have high rates of
de-/allocation and sometimes have high numbers, but only rarely in
different subpools at the same time.

I've used a generic subpool allocator, which doubles the total
number of allocated objects each time it has to ask malloc for more
memory, in such situations on projects, and as a result never had
noticeable time or space problems.

So I never actually had to measure the difference between that
approach and regular malloc (yeah, premature optimization is the
root of all evil, but I'm Scottish and cheap with other people's
CPUs and bits, and dislike debugging problems when I can design to
avoid them).

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
http://www.garlic.com/~lynn/subtopic.html#wsclock
and dynamic adaptive scheduling
http://www.garlic.com/~lynn/subtopic.html#fairshare

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 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 assist 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
http://www.garlic.com/~lynn/94.html#21 370 ECPS VM microcode assist

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
execution ...  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
http://www.garlic.com/~lynn/93.html#26 MTS & LLMPS?
http://www.garlic.com/~lynn/98.html#19 S/360 operating systems geneaology
http://www.garlic.com/~lynn/2000d.html#47 Charging for time-share CPU time
http://www.garlic.com/~lynn/2002.html#14 index searching
http://www.garlic.com/~lynn/2002h.html#87 Atomic operations redux
http://www.garlic.com/~lynn/2004g.html#57 Adventure game (was:PL/? History (was Hercules))
http://www.garlic.com/~lynn/2004h.html#0 Adventure game (was:PL/? History (was Hercules))
http://www.garlic.com/~lynn/2004m.html#22 Lock-free algorithms
http://www.garlic.com/~lynn/2006e.html#40 transputers again was: The demise of Commodore

--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn/

virtual memory

From: Anne & Lynn Wheeler <lynn@garlic.com>
Subject: Re: virtual memory
Newsgroups: comp.arch,alt.folklore.computers
Date: Mon, 15 May 2006 19:09:05 -0600

Anne & Lynn Wheeler writes:

clock and global LRU uses an LRU approximation ... that kind of sorts
pages into two categories ... those that have their reference bit used
since the last examination/reset, and those that haven't had their
reference bit used since their last examination/reset.

we did significant simulation with full instruction traces
some of it was part of the vs/repack technology previously
referenced
http://www.garlic.com/~lynn/2006i.html#37 virtual memory

where in detailed simulation with full instruction traces of
i-refs, d-refs, and d-stores ... compared lots of global and
local lru approximations as well as "true" lru ... where
exact ordering of page references were maintained.

ref:
http://www.garlic.com/~lynn/2006j.html#18 virtual memory

besides the numerous different variations on LRU approximations,
"true" LRU implemented in simulators ... there was also belady's "OPT"
... basically with a full trace of all storage accesses ... OPT chose
the page to replace that resulted in the fewest future page faults (of
course ... you were no longer working on past history ... like LRU or
LRU approximation ... you needed a full prediction of the future ...
which you could simulate given a complete trace of all storage access
to replay).

a few recent posts mentioning other of belady's references
http://www.garlic.com/~lynn/2006i.html#37 virtual memory
http://www.garlic.com/~lynn/2006i.html#38 virtual memory
http://www.garlic.com/~lynn/2006i.html#42 virtual memory
http://www.garlic.com/~lynn/2006j.html#17 virtual memory

here is a spring 2005 class assignment
http://www.cs.georgetown.edu/~clay/classes/spring2005/os/paging.html

requiring implementation & comparison of:

• FIFO: First In, First Out
• GC: Global Clock
• LFU: Least Frequently Used
• LRU: Least Recently Used
• MFU: Most Frequently Used
• OPT: Belady's Optimal Algorithm
• RAND: Random

.....

for some drift:

R. L. Mattson, J. Gecsei, D. R. Slutz, and I. L. Traiger. Evaluation
techniques for storage hierarchies. IBM Systems Journal, 9(2):78-117,
1970.

with respect to the cache investigation using simulator that
had full trace of all record accesses for production systems ...
http://www.garlic.com/~lynn/2006i.html#41 virtual memory
http://www.garlic.com/~lynn/2006j.html#14 virtual memory

I had implemented much of the data collection stuff in 1979 and
Mattson had done most of the simulator implementation.

One of the other outcomes of Mattson 1979 simulation work was that he
developed a process that could analyse the record access activity in
real-time ... looking at being able to do run it as part of normal
production operation and do real-time optimal disk data
reorganization.

a more recent paper referencing Mattson's 1970 work.
http://csdl2.computer.org/persagen/DLAbsToc.jsp?resourcePath=/dl/trans/tc/&toc=comp/trans/tc/1998/06/t6toc.xml&DOI=10.1109/12.689650

--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn/

virtual memory

From: Anne & Lynn Wheeler <lynn@garlic.com>
Subject: Re: virtual memory
Newsgroups: comp.arch,alt.folklore.computers
Date: Tue, 16 May 2006 07:51:45 -0600

jmfbahciv writes:

I always thought that virtual memory was akin to custom-made
suits.  Each manufacturer had its own unique problem set
and would have applied to anybody else's.

You should also remember that IBM was based on batch folklore.
We weren't; DEC never learned how to do batch computing with
huge data bases and transaction processin.  To IBM this
stuff was as natural as breathing.

that was POK and the majority of the customer base. however, a lot of
virtual machines, virtual memory, paging, interactive computing,
networking, multiprocessor and other stuff was done at the science
center
http://www.garlic.com/~lynn/subtopic.html#545tech

the technology for the internal network was developed at
the science center. the internal network was larger than
the arpanet/internet from just about the beginning until
possibly mid-85.
http://www.garlic.com/~lynn/subnetwork.html#internalnet

the technology used in the internal network was also used
in bitnet & earn
http://www.garlic.com/~lynn/subnetwork.html#bitnet

gml (precusor to sgml, html, xml, etc) was invented at
the science center
http://www.garlic.com/~lynn/subtopic.html#sgml

the invention of the compare&swap instruction was invented
by charlie at the science center (CAS comes from charlie's
initials and then had to come up with an instruction name
that matched charlie's initials)
http://www.garlic.com/~lynn/subtopic.html#smp

a lot of the work on performance monitoring and workload
profiling leading up to capacity planning was also done
at the science center
http://www.garlic.com/~lynn/subtopic.html#bench

while the original relational stuff wasn't done at the science center
... i did get to work on some of it after i transferred from the
science center out to research on the west coast. however, all of the
original relational/sql stuff was developed on vm370 ... which was on
outgrowth of the virtual machine cp67 stuff that had originated at the
science center
http://www.garlic.com/~lynn/subtopic.html#systemr

note that while the virtual machine and interactive install base was
considered relatively small compared to the big batch customer base
... there was some numbers that in the early 80s, the 4341 vm370
install base was approximately the same size as the vax install base
(even tho the 4341 vm370 install base was considered almost trivially
small compared to the company's batch install base).

some old vax install numbers:
http://www.garlic.com/~lynn/2002f.html#0 Computers in Science Fiction
http://www.garlic.com/~lynn/2002f.html#5 Blade architectures
http://www.garlic.com/~lynn/2005f.html#37 Where should the type information be: in tags and descriptors

some old 4341 and/or vax postings
http://www.garlic.com/~lynn/2000c.html#76 Is a VAX a mainframe?
http://www.garlic.com/~lynn/2000c.html#83 Is a VAX a mainframe?
http://www.garlic.com/~lynn/2000d.html#0 Is a VAX a mainframe?
http://www.garlic.com/~lynn/2000d.html#7 4341 was "Is a VAX a mainframe?"
http://www.garlic.com/~lynn/2000d.html#9 4341 was "Is a VAX a mainframe?"
http://www.garlic.com/~lynn/2000d.html#10 4341 was "Is a VAX a mainframe?"
http://www.garlic.com/~lynn/2000d.html#11 4341 was "Is a VAX a mainframe?"
http://www.garlic.com/~lynn/2000d.html#12 4341 was "Is a VAX a mainframe?"
http://www.garlic.com/~lynn/2000d.html#13 4341 was "Is a VAX a mainframe?"
http://www.garlic.com/~lynn/2001m.html#15 departmental servers
http://www.garlic.com/~lynn/2002h.html#52 Bettman Archive in Trouble
http://www.garlic.com/~lynn/2002i.html#30 CDC6600 - just how powerful a machine was it?
http://www.garlic.com/~lynn/2002k.html#1 misc. old benchmarks (4331 & 11/750)
http://www.garlic.com/~lynn/2002k.html#3 misc. old benchmarks (4331 & 11/750)
http://www.garlic.com/~lynn/2003.html#14 vax6k.openecs.org rebirth
http://www.garlic.com/~lynn/2003.html#15 vax6k.openecs.org rebirth
http://www.garlic.com/~lynn/2003c.html#17 diffence between itanium and alpha
http://www.garlic.com/~lynn/2003c.html#19 diffence between itanium and alpha
http://www.garlic.com/~lynn/2003d.html#0 big buys was: Tubes in IBM 1620?
http://www.garlic.com/~lynn/2003d.html#33 Why only 24 bits on S/360?
http://www.garlic.com/~lynn/2003d.html#61 Another light on the map going out
http://www.garlic.com/~lynn/2003d.html#64 IBM was: VAX again: unix
http://www.garlic.com/~lynn/2003e.html#56 Reviving Multics
http://www.garlic.com/~lynn/2003f.html#48 Alpha performance, why?
http://www.garlic.com/~lynn/2003g.html#22 303x, idals, dat, disk head settle, and other rambling folklore
http://www.garlic.com/~lynn/2003i.html#5 Name for this early transistor package?
http://www.garlic.com/~lynn/2003p.html#38 Mainframe Emulation Solutions
http://www.garlic.com/~lynn/2004.html#46 DE-skilling was Re: ServerPak Install via QuickLoad Product
http://www.garlic.com/~lynn/2004f.html#39 Who said "The Mainframe is dead"?
http://www.garlic.com/~lynn/2004g.html#24 |d|i|g|i|t|a|l| questions
http://www.garlic.com/~lynn/2004j.html#57 Monster(ous) sig (was Re: Vintage computers are better
http://www.garlic.com/~lynn/2004l.html#10 Complex Instructions
http://www.garlic.com/~lynn/2004m.html#59 RISCs too close to hardware?
http://www.garlic.com/~lynn/2004m.html#63 RISCs too close to hardware?
http://www.garlic.com/~lynn/2004q.html#71 will there every be another commerically signficant new ISA?
http://www.garlic.com/~lynn/2005f.html#30 Where should the type information be: in tags and descriptors
http://www.garlic.com/~lynn/2005f.html#58 Where should the type information be: in tags and descriptors
http://www.garlic.com/~lynn/2005f.html#59 Where should the type information be: in tags and descriptors
http://www.garlic.com/~lynn/2005m.html#8 IBM's mini computers--lack thereof
http://www.garlic.com/~lynn/2005m.html#12 IBM's mini computers--lack thereof
http://www.garlic.com/~lynn/2005m.html#25 IBM's mini computers--lack thereof
http://www.garlic.com/~lynn/2005n.html#10 Code density and performance?
http://www.garlic.com/~lynn/2005n.html#11 Code density and performance?
http://www.garlic.com/~lynn/2005n.html#12 Code density and performance?
http://www.garlic.com/~lynn/2005n.html#16 Code density and performance?
http://www.garlic.com/~lynn/2005n.html#47 Anyone know whether VM/370 EDGAR is still available anywhere?
http://www.garlic.com/~lynn/2005p.html#1 Intel engineer discusses their dual-core design
http://www.garlic.com/~lynn/2005p.html#19 address space
http://www.garlic.com/~lynn/2005q.html#27 What ever happened to Tandem and NonStop OS ?
http://www.garlic.com/~lynn/2005s.html#36 Filemode 7-9?
http://www.garlic.com/~lynn/2005s.html#39 Filemode 7-9?
http://www.garlic.com/~lynn/2006.html#47 "VAX" Tradename reused !
http://www.garlic.com/~lynn/2006b.html#34 Multiple address spaces

--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn/

virtual memory

From: Anne & Lynn Wheeler <lynn@garlic.com>
Subject: Re: virtual memory
Newsgroups: comp.arch,alt.folklore.computers
Date: Tue, 16 May 2006 08:58:02 -0600

Brian Inglis writes:

As with malloc and friends, there must be some bad VM implementations
out there for them to build their own, unless it's a holdover from old
68K Macs without MMU.

science center
http://www.garlic.com/~lynn/subtopic.html#545tech

had ported apl\360 to cms\apl. apl\360 had basicly its own subsystem
monitor, terminal handler, swapper, storage manager etc ...  running
"real memory" under os/360. typical apl\360 workspaces were 16kbytes
to 32kbytes.

in the move to cms\apl ... got rid of the subsystem monitor, terminal
handler, swapper, etc ... as part of the apl implementation (allowing
it to rely on the underlying infrastructure provided by cp67).

one of the things that the move to cms\apl environment was transition
from 16kbyte ("real") workspaces to possibly multi-megabyte virtual
memory workspaces. this created a big problem for the apl storage
manager. it basically started with all unused space as available, then
on ever assignment, it allocated the next available unused space
(discarding any old location containing a value). when it had
exhausted unused space, it did garbage collection, compacting all
"used" storage ... and creating a large contiguous area of unused
space ... and then started all over again.

in a small, swapped, real-storage implementation, the side-effects of
this strategy wasn't particularly bad. however, with very large
virtual memory workspaces ... this strategy quickly touched all
available virtual pages, then garbage collect/compact, and started all
over.

the early vs/repack technology:

D. Hatfield & J. Gerald, Program Restructuring for Virtual Memory,
IBM Systems Journal, v10n3, 1971

http://www.garlic.com/~lynn/2006i.html#37 virtual memory

was used to analyze this behavior and perfect a modified garbage
collection implementation that was significantly more virtual memory
friendly.

misc. past posts mentioning apl &/or hone
http://www.garlic.com/~lynn/subtopic.html#hone

hone started out was a joint project with the science center and the
marketing division to provide online, interactive support for all the
sales, marketing, and field people ... initially with cp67 and later
moved to vm370 base. a majority of the applications for the sales and
marketing people were implemented in apl.

in the mid-70s, the various hone us datacenters were consolidated in
northern cal. by the late 70s, the size of the defined US hone users
was approaching 40k. in addition there were numerous clones of the US
hone datacenter at various locations around the world. in the very
early 80s, the high-available, fall-over hone implementation in
northern cal. was replicated first with a new datacenter in dallas and
then a 3rd datacenter in boulder (providing load balancing and
fall-over across the datacenters in case of a natural disaster in
cal.).

--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn/

virtual memory

From: Anne & Lynn Wheeler <lynn@garlic.com>
Subject: Re: virtual memory
Newsgroups: comp.arch,alt.folklore.computers
Date: Tue, 16 May 2006 14:00:54 -0600

"Eric P." writes:

Ok, so it sounds like Grenoble did have a second chance mechanism.
Rats, I was kinda hoping it didn't so I could explain away your
results. :-)

Why would your global (approx) LRU needed to reclaim? I suppose if
you trim the global valid list to refill a low free list, then the
previous owner touches one of the trimmed pages before it is
reassigned, you want to just retrieve it from the free list.
Correct?

so, I've told the story of how MVS decided to bias the LRU replacement
algorithm in favor of non-changed pages ... because there was lower
overhead and less latency ... than compared to when a changed page had
to be first written out.
http://www.garlic.com/~lynn/2006i.html#43 virtual memory
http://www.garlic.com/~lynn/2006j.html#5 virtual memory

however, if you are just doing straight page replacement selection,
somewhat syncronized with the page fault ... then the latency for
servicing a page fault when a changed page has been selected is
possibly twice the elapsed time of servicing a page fault when a
non-changed page has been selected (since replacing a page that has
been changed first requires writing the current contents out before
the replaced contents can be read in).

to cut down on this latency, you run the selecting of pages for
replacement slightly out of sync and ahead of servicing a page fault.
you have a small (fifo) pool of pages selected for replacement. a page
fault results in selecting a replacement page from the pool
... probably dropping the pool below threshold, which then requires
invoking the replacement algorithm to replenish the pool. changed
pages that are selected for replacement are written out as they are
added to the replacement pool. by the time, a page fault requires the
page, any changed page has completed its write and the real storage
location is immediately available to bring in the replacement page
... cutting down on the latency to service a page fault.

you might also check carr's global clock thesis ... i was able to find
it online.

--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn/

virtual memory

From: Anne & Lynn Wheeler <lynn@garlic.com>
Subject: Re: virtual memory
Newsgroups: comp.arch,alt.folklore.computers
Date: Wed, 17 May 2006 07:43:20 -0600

robert.thorpe writes:

I see.  I wish I'd done something so interesting when I was an
undergraduate.

i got to do the support and maint. for the univ. datacenter production
systems. i would frequently get the machine room 8am on sat. and have
it all to myself until 8am on monday. monday classes were sometimes a
little difficult having already gone 48hrs w/o sleep.

misc. past posts pulling 48hr shift before monday classes.
http://www.garlic.com/~lynn/2001b.html#26 HELP
http://www.garlic.com/~lynn/2001f.html#63 First Workstation
http://www.garlic.com/~lynn/2002k.html#63 OT (sort-of) - Does it take math skills to do data processing ?
http://www.garlic.com/~lynn/2002o.html#1 Home mainframes
http://www.garlic.com/~lynn/2002o.html#2 Home mainframes
http://www.garlic.com/~lynn/2002p.html#38 20th anniversary of the internet (fwd)
http://www.garlic.com/~lynn/2003c.html#51 HASP assembly: What the heck is an MVT ABEND 422?
http://www.garlic.com/~lynn/2003c.html#57 Easiest possible PASV experiment
http://www.garlic.com/~lynn/2004c.html#19 IT jobs move to India
http://www.garlic.com/~lynn/2004e.html#45 going w/o sleep

--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn/

virtual memory

From: Anne & Lynn Wheeler <lynn@garlic.com>
Subject: Re: virtual memory
Newsgroups: comp.arch,alt.folklore.computers,bit.listserv.vmesa-l
Date: Wed, 17 May 2006 08:39:16 -0600

Brian Inglis writes:

In virtual machine environments, software versions of hardware
approaches tends to be used instead of "creating beautiful new
impediments to understanding" (Henry Spencer -- from #8 in "The Ten
Commandments for C Programmers").

old post discussing how hardware address translation worked
on trout 1.5 (3090), including email from fall of '83
http://www.garlic.com/~lynn/2003j.html#42 Flash 10208

there is a reference to Birnbaum starting in early '75 on 801 project
(including split caches), i.e. 801 turned into romp, rios, power,
power/pc, etc. misc. past posts mentioning 801
http://www.garlic.com/~lynn/subtopic.html#801

and old discussion about SIE (virtual machine assist) from long
ago and far away (couple weeks short of 25years ago):


To: wheeler
Date: 6/30/81  15:33:04

I would like to add a bit more to the discussion of SIE.  I seem to
have hit a sensitive area with my original comments.  I would have
preferred to contain this to an offline discussion, but I feel that
some of the things that have appeared in the memos require a reply.

First, let me say that all of the comments I have made have been
accurate to the best of my knowledge.  The performance data I quoted
came directly from a presentation I attended given by the VM/811
group.  The purpose of the presentation was to justify extensions to
the SIE architecture.  Since I my last writing, I have been told by
XXXXX that the numbers quoted were for MVS running under VMTOOL on the
3081.  XXXXXX mentioned that VMTOOL has some significant software
problems which are partially responsible for the poor performance.
Presumably, VM/811 would not have these problems.  This was not
pointed out at the meeting.

For many years the software and hardware groups have misunderstood
each other.  Engineers who knew nothing about software could not
understand why it was necessary to make their hardware do certain
things.  Likewise, programmers who knew nothing about software could
not understand why the engineers could not make the hardware do the
things they wanted.  Traditionally, microcode has been done by
engineers because a thorough understanding of the hardware is
necessary in order to write microcode.  In recent years, this has
become a problem as more complex software functions have been placed
into microcode.  In my department, we have tried to remedy this
problem by hiring people with programming experience as
microprogrammers.

The statement that millions of dollars have been spent writing
microcode in order to avoid putting a few ten cent latches into the
hardware is completely false.  The truth is that changes have often
been made to the microcode to AVOID SPENDING MILLIONS OF DOLLARS by
putting a change in hardware.  In the world of LSI and VLSI, there
is no longer such a thing as a "ten cent latch."  Once a chip has
been designed, it is very expensive to make even the smallest
change to it.

Microcode offers a high degree of flexibility in an environment that
is subject to change, especially if one has a writable control store.
When a change is necessary, it can often be had for "free" by making a
change to the microcode and sending out a new floppy disk, whereas it
might cost millions of dollars to make an equivalent change to the
hardware.  While the performance of the microcode may not be as good
as the hardware implementation, the overall cost/performance has
dictated that it is the method of choice.

As I pointed out in a previous writing, what works well or does not
work well on one machine says absolutely nothing about the performance
of that item on another machine.  XXXXX seems to have completely
missed this critical point, since he expects a 158-like performance
boost from SIE on machines which are nothing like the 158 in their
design.

SIE is a poor performer on the 3081 for several reasons.  One reason
is that the 3081 pages its microcode.  Each time it is necessary to
enter or exit SIE, a large piece of microcode must be paged in to
carry out this function.  This is rather costly in terms of
performance.  A performance gain could be realized if the number of
exit/entry trips could be reduced.  One way of doing this would be to
emulate more instructions on the assumption that it takes less to
emulate them than it does to exit and re-enter emulation mode.  This
thinking is completely valid for the 3081, but is not necessarily
relevent when it comes to other machines, such as TROUT.

TROUT does not page its microcode, and therefore the cost of exiting
and re-entering emulation mode is less.  The thinking behind the
changes to the SIE architecture should be re-examined when it comes to
TROUT because the data upon which the changes were based is not
necessarily valid.  This is why I have asked that the extensions to
SIE be made optional.  This would allow machines that do have
performance problems to implement the extensions, while machines that
do not have problems could leave them out and use their control store
for more valuable functions.

The extensions that are being proposed are not at all trivial.  It may
seem like a simple matter to emulate an I/O instruction, but such is
not the case.  To appreciate what is involved, one must have a
detailed understanding of just how the CPU, SCE and and Channels work.

Other machines do indeed have an easier time when it comes to
implementing some of these assists.  That is because they are rather
simple machines internally, not because their designers had more
foresight when they designed the machines.  The cycle time of TROUT is
only slightly faster than the 3081, yet TROUT is much faster in terms
of MIPS.  This performance comes from the highly overlapped design of
the processor.  This makes for a much more complex design.  Sometimes
you pay dearly for this, like when it comes to putting in complex
microcode functions.

TROUT has never treated SIE as "just another assist."  SIE has been a
basic part of our machine's design since the beginning. In fact, we
have chosen to put many functions into hardware instead of microcode
to pick up significant performance gains.  For example, the 3081 takes
a significant amount of time to do certain types of guest-to-host
address translation because it does them in microcode, while TROUT
does them completely in hardware.

... snip ... top of post, old email index

nomenclature in the above with "guest" refers to an operating system
running in a virtual machine.

...

with regard to the above comment about virtual machines and I/O
instruction ... part of the issue is translating the I/O channel
program and fixing the related virtual pages in real memory .. since
the real channels run using real addresses from the channel programs.
the channel programs from the virtual address space have all been
created using the addresses of the virtual address space. this
wasn't just an issue for virtual machine emulation ... but OS/VS2
also has the issue with channel programs created by applications
running in virtual address space.

...

3090 responded to Amdahl's hypervisor support with PR/SM, misc. past
posts mentioning PR/SM (and LPARs)
http://www.garlic.com/~lynn/2000c.html#76 Is a VAX a mainframe?
http://www.garlic.com/~lynn/2002o.html#15 Home mainframes
http://www.garlic.com/~lynn/2002o.html#18 Everything you wanted to know about z900 from IBM
http://www.garlic.com/~lynn/2002p.html#44 Linux paging
http://www.garlic.com/~lynn/2002p.html#46 Linux paging
http://www.garlic.com/~lynn/2002p.html#48 Linux paging
http://www.garlic.com/~lynn/2003.html#56 Wild hardware idea
http://www.garlic.com/~lynn/2003n.html#13 CPUs with microcode  ?
http://www.garlic.com/~lynn/2003o.html#52 Virtual Machine Concept
http://www.garlic.com/~lynn/2004c.html#4 OS Partitioning and security
http://www.garlic.com/~lynn/2004c.html#5 PSW Sampling
http://www.garlic.com/~lynn/2004m.html#41 EAL5
http://www.garlic.com/~lynn/2004m.html#49 EAL5
http://www.garlic.com/~lynn/2004n.html#10 RISCs too close to hardware?
http://www.garlic.com/~lynn/2004o.html#13 Integer types for 128-bit addressing
http://www.garlic.com/~lynn/2004p.html#37 IBM 3614 and 3624 ATM's
http://www.garlic.com/~lynn/2004q.html#18 PR/SM Dynamic Time Slice calculation
http://www.garlic.com/~lynn/2004q.html#76 Athlon cache question
http://www.garlic.com/~lynn/2005.html#6 [Lit.] Buffer overruns
http://www.garlic.com/~lynn/2005b.html#5 Relocating application architecture and compiler support
http://www.garlic.com/~lynn/2005c.html#56 intel's Vanderpool and virtualization in general
http://www.garlic.com/~lynn/2005d.html#59 Misuse of word "microcode"
http://www.garlic.com/~lynn/2005d.html#74 [Lit.] Buffer overruns
http://www.garlic.com/~lynn/2005h.html#13 Today's mainframe--anything to new?
http://www.garlic.com/~lynn/2005h.html#19 Blowing My Own Horn
http://www.garlic.com/~lynn/2005k.html#43 Determining processor status without IPIs
http://www.garlic.com/~lynn/2005m.html#16 CPU time and system load
http://www.garlic.com/~lynn/2005p.html#29 Documentation for the New Instructions for the z9 Processor
http://www.garlic.com/~lynn/2006e.html#15 About TLB in lower-level caches
http://www.garlic.com/~lynn/2006h.html#30 The Pankian Metaphor

...

misc. past posts mentioning CCWTRANS (cp/67 routine that created
"shadow" channel program copies of what was in the virtual address
space, replacing all virtual addresses with "real" addresses, for
example initial prototype of OS/VS2 was built by crafting hardware
translation into mvt and hacking a copy of CP67's CCWTRANS into mvt):
http