virtual memory

[khan]

I want to clear my virtual memory concept.
Is virtual memory, a part of hard disk or some indirect addressable
memory(NAND Flash).

[Patrick Schaaf]

"khan" <***@yahoo.co.in> writes:

>Is virtual memory, a part of hard disk or some indirect addressable
>memory(NAND Flash).

Depends on the swap setup. Could be both at the same time.

best regards
Patrick

[Doug MacKay]

khan wrote:
> I want to clear my virtual memory concept.
> Is virtual memory, a part of hard disk or some indirect addressable
> memory(NAND Flash).

The swap storage you're thinking of is only a small piece of a virtual
memory system. If it was removed from a virtual memory system you'd
still have a virtual memory system ;)

If you're interested in virtual memory as a whole your best bet would
be a google search on "virtual memory." The wikipedia VM page also
gives an easy to follow overview:
http://en.wikipedia.org/wiki/Virtual_memory

For this question in particular it sounds like you're referring to a
swap file. This is usually stored on the same bulk storage as the rest
of your software. Hard drives for PC's, Flash drives for Palms, etc.

[Anne & Lynn Wheeler]

"Doug MacKay" <***@gmail.com> writes:
> The swap storage you're thinking of is only a small piece of a virtual
> memory system. If it was removed from a virtual memory system you'd
> still have a virtual memory system ;)

see melinda's paper on the development of virtual memory and
virtual machines in the 60s
http://www.princeton.edu/~melinda/25paper.pdf

part of it was mit had chosen ge for ctss follow-on multics.

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

had added custom virtual memory to 360/40 and built cp/40 supporting
virtual machines and paging/swapping.

the 360/67 was official product with virtual memory support, built for
tss/360. however, the science center ported cp/40 from the 360/40 to
360/67 renaming it cp/67.

univ. of michigan also developed MTS (michigen terminal system) that
supported virtual memory on 360/67 (also paging/swapping).

however, there was at least one effort that modified os/360 to utilize
the 360/67 virtual memory hardware w/o providing paging/swapping
support. os/360 was nominally a "real address" operating system where
applications were allocated contiguous areas of real memory. long
running applications frequently resulted in storage fragmentation,
there would be enough real memory to run an application but not
located contiguously. the use of virtual memory hardware allowed
discontiguous real storage to be appear to be contiguous.

for some drift ... misc posts about doing page replacement algorithms
in the 60s (i.e. deciding which pages should be moved between real
memory and disk).
http://www.garlic.com/~lynn/subtopic.html#wsclock

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

[kim kubik]

"Anne & Lynn Wheeler" wrote :
> "Doug MacKay" writes:
> > The swap storage you're thinking of is only a small piece of a
virtual
> > memory system. If it was removed from a virtual memory system
you'd
> > still have a virtual memory system ;)

> see melinda's paper on the development of virtual memory and
> virtual machines in the 60s

There are (at least) two overlapping meanings of the phrase "virtual
memory"
here: a virtual (i.e., non-real) memory address and a virtual eXtention
("X" as
in VAX) of memory out to disk. Most people seem to use the latter
meaning.

The first, virtual memory addressing (dividing up of RAM into fixed
sized pages)
is in most cases a big win: drastic decrease in memory fragmentation.

Extending RAM out to disk pages adds all the cute PhD thesis project
benchmarkable optimizations: page size, replacement algorithms, thrash
minimization, etc. In an early attempt a compiling TeX in SUN the person
finally shut down the machine after 36 hours, noting the paging daemon
was
taking up more and more of cpu time and eventually might take all of it.

Extending the address space out to disk for a single user desktop
machine
has one real advantage: it gives you a chance to go get coffee when
there's a
page fault.

It's now year 2006 -- RAM is cheap.

[AZ Nomad]

On Fri, 12 May 2006 02:30:58 GMT, kim kubik <***@jps.net> wrote:



>"Anne & Lynn Wheeler" wrote :
>> "Doug MacKay" writes:
>> > The swap storage you're thinking of is only a small piece of a
>virtual
>> > memory system. If it was removed from a virtual memory system
>you'd
>> > still have a virtual memory system ;)

>> see melinda's paper on the development of virtual memory and
>> virtual machines in the 60s

>There are (at least) two overlapping meanings of the phrase "virtual
>memory"
>here: a virtual (i.e., non-real) memory address and a virtual eXtention
>("X" as
>in VAX) of memory out to disk. Most people seem to use the latter
>meaning.

>The first, virtual memory addressing (dividing up of RAM into fixed
>sized pages)
>is in most cases a big win: drastic decrease in memory fragmentation.

>Extending RAM out to disk pages adds all the cute PhD thesis project
>benchmarkable optimizations: page size, replacement algorithms, thrash
>minimization, etc. In an early attempt a compiling TeX in SUN the person
>finally shut down the machine after 36 hours, noting the paging daemon
>was
>taking up more and more of cpu time and eventually might take all of it.

>Extending the address space out to disk for a single user desktop
>machine
>has one real advantage: it gives you a chance to go get coffee when
>there's a
>page fault.

>It's now year 2006 -- RAM is cheap.

Wrong.

Virtual memory is the same in either case -- the application sees an
address space that is then mapped either to physical memory or swap
or page files.

You haven't the slightest understanding on how the VAX managed virtual
memory. It was not an extension to disk. It was an extension of the
PDP architecture.

[Anne & Lynn Wheeler]

"kim kubik" <***@jps.net> writes:
> There are (at least) two overlapping meanings of the phrase "virtual
> memory" here: a virtual (i.e., non-real) memory address and a
> virtual eXtention ("X" as in VAX) of memory out to disk. Most
> people seem to use the latter meaning.
>
> The first, virtual memory addressing (dividing up of RAM into fixed
> sized pages) is in most cases a big win: drastic decrease in memory
> fragmentation.
>
> Extending RAM out to disk pages adds all the cute PhD thesis project
> benchmarkable optimizations: page size, replacement algorithms,
> thrash minimization, etc. In an early attempt a compiling TeX in SUN
> the person finally shut down the machine after 36 hours, noting the
> paging daemon was taking up more and more of cpu time and eventually
> might take all of it.

the post did describe a case where virtual memory was used
to address fragmentation problem
http://www.garlic.com/~lynn/2006i.html#22 virtual memory

some subsequent drift on this thread in a.f.c.
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

i had done a bunch of the paging stuff as an undergraduate in the 60s
... which was picked up and shipped in cp67 product.
http://www.garlic.com/~lynn/subtopic.html#wsclock

decade plus later there was some conflict around somebody's stanford
phd on global lru replacement (work that i had done as an undergraduate in
the 60s) vis-a-vis local lru replacements. some past posts mentioning
the conflict.
http://www.garlic.com/~lynn/93.html#4 360/67, was Re: IBM's Project F/S ?
http://www.garlic.com/~lynn/94.html#49 Rethinking Virtual Memory
http://www.garlic.com/~lynn/2001c.html#10 Memory management - Page replacement
http://www.garlic.com/~lynn/2002c.html#49 Swapper was Re: History of Login Names
http://www.garlic.com/~lynn/2003k.html#8 z VM 4.3
http://www.garlic.com/~lynn/2003k.html#9 What is timesharing, anyway?
http://www.garlic.com/~lynn/2004g.html#13 Infiniband - practicalities for small clusters
http://www.garlic.com/~lynn/2004q.html#73 Athlon cache question
http://www.garlic.com/~lynn/2005d.html#37 Thou shalt have no other gods before the ANSI C standard
http://www.garlic.com/~lynn/2005d.html#48 Secure design
http://www.garlic.com/~lynn/2005f.html#47 Moving assembler programs above the line
http://www.garlic.com/~lynn/2005n.html#23 Code density and performance?
http://www.garlic.com/~lynn/2006f.html#0 using 3390 mod-9s

i had also done this stuff with dynamica adaptive scheduling
(scheduling policies included fair share) ... and scheduling to the
bottleneck
http://www.garlic.com/~lynn/subtopic.html#fairshare

much of it was dropped in the morph from cp67 to vm370 ... but
i was allowed to reintroduce it as the "resource manager"
which became availble 11may76
http://www.garlic.com/~lynn/2006i.html#26 11may76, 30 years, (re-)release of resource manager

around this time, i was starting to notice the decline of relative
disk system performance ... and significant increase in amount of
available real storage ... and being able to start to use real storage
caching to compensate for the decline in relative disk system
performance

i started making some comments about it and the disk division
eventually assigned their performance group to refute the comments.
the performance group came back and observed that i had slightly
understated the problem.

misc. past posts on the subject:
http://www.garlic.com/~lynn/93.html#31 Big I/O or Kicking the Mainframe out the Door
http://www.garlic.com/~lynn/94.html#43 Bloat, elegance, simplicity and other irrelevant concepts
http://www.garlic.com/~lynn/94.html#55 How Do the Old Mainframes Compare to Today's Micros?
http://www.garlic.com/~lynn/95.html#10 Virtual Memory (A return to the past?)
http://www.garlic.com/~lynn/98.html#46 The god old days(???)
http://www.garlic.com/~lynn/99.html#4 IBM S/360
http://www.garlic.com/~lynn/99.html#112 OS/360 names and error codes (was: Humorous and/or Interesting Opcodes)
http://www.garlic.com/~lynn/2001d.html#66 Pentium 4 Prefetch engine?
http://www.garlic.com/~lynn/2001f.html#62 any 70's era supercomputers that ran as slow as today's supercomputers?
http://www.garlic.com/~lynn/2001f.html#68 Q: Merced a flop or not?
http://www.garlic.com/~lynn/2001l.html#40 MVS History (all parts)
http://www.garlic.com/~lynn/2001l.html#61 MVS History (all parts)
http://www.garlic.com/~lynn/2001m.html#23 Smallest Storage Capacity Hard Disk?
http://www.garlic.com/~lynn/2002.html#5 index searching
http://www.garlic.com/~lynn/2002b.html#11 Microcode? (& index searching)
http://www.garlic.com/~lynn/2002b.html#20 index searching
http://www.garlic.com/~lynn/2002e.html#8 What are some impressive page rates?
http://www.garlic.com/~lynn/2002e.html#9 What are some impressive page rates?
http://www.garlic.com/~lynn/2002i.html#16 AS/400 and MVS - clarification please
http://www.garlic.com/~lynn/2003i.html#33 Fix the shuttle or fly it unmanned
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#13 Today's mainframe--anything to new?
http://www.garlic.com/~lynn/2005k.html#53 Performance and Capacity Planning
http://www.garlic.com/~lynn/2005n.html#29 Data communications over telegraph circuits

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

[toby]

kim kubik wrote:
> "Anne & Lynn Wheeler" wrote :
> > "Doug MacKay" writes:
> > > The swap storage you're thinking of is only a small piece of a
> virtual
> > > memory system. If it was removed from a virtual memory system
> you'd
> > > still have a virtual memory system ;)
>
> > see melinda's paper on the development of virtual memory and
> > virtual machines in the 60s
>
> There are (at least) two overlapping meanings of the phrase "virtual
> memory"
> here: a virtual (i.e., non-real) memory address and a virtual eXtention
> ("X" as
> in VAX) of memory out to disk. Most people seem to use the latter
> meaning.
>
> The first, virtual memory addressing (dividing up of RAM into fixed
> sized pages)
> is in most cases a big win: drastic decrease in memory fragmentation.

I have to agree with Nomad here, your explanation seems to add
confusion. You dwell on thrashing but don't mention the basic
mechanism, which is virtualisation of process address spaces in a
multiprogrammed system. Paging was the VAX approach and has been most
popular since. Given the complexity of today's runtime systems it is
hard to conceive of a practical modern computer that does not offer
virtual memory in this sense. "Fragmentation" is not "decreased" but
conceptually eliminated; each process sees one contiguous address
space. And there are various other new efficiencies such as page
sharing, access control etc.

>
> Extending RAM out to disk pages adds all the cute PhD thesis project
> benchmarkable optimizations: page size, replacement algorithms, thrash
> minimization, etc. In an early attempt a compiling TeX in SUN the person

In the era you are alluding to it would have been SunOS (a BSD)'s paged
VM on a 68K family CPU (Sun2 or more likely Sun3).

> finally shut down the machine after 36 hours, noting the paging daemon
> was
> taking up more and more of cpu time and eventually might take all of it.

You can overload, or find a pathological/buggy workload for any
machine. It's a mundane anecdote and not a statement on memory
management.

>
> Extending the address space out to disk for a single user desktop
> machine
> has one real advantage: it gives you a chance to go get coffee when
> there's a
> page fault.

I don't see how the phrase "Extending the address space out to disk"
really describes a modern system. It may describe some primitive
systems labelled "virtual memory" such as Apple's System 7
implementation. I think even Windows has something like virtual paged
memory management, but don't quote me.

>
> It's now year 2006 -- RAM is cheap.

[Jan Vorbrüggen]

> "Fragmentation" is not "decreased" but conceptually eliminated; each
> process sees one contiguous address space.

In this context, I understood fragementation to address the problem of
fragementation of real memory when you have a pre-VM system, e.g., a PDP-10
base&bounds approach. VM eliminates that entirely as well.

Jan

[j***@aol.com]

In article <***@individual.net>,
=?ISO-8859-1?Q?Jan_Vorbr=FCggen?= <***@not-mediasec.de> wrote:

To whom are you talking?

> > "Fragmentation" is not "decreased" but conceptually eliminated; each
> > process sees one contiguous address space.
>
>In this context, I understood fragementation to address the problem of
>fragementation of real memory when you have a pre-VM system, e.g., a PDP-10
>base&bounds approach. VM eliminates that entirely as well.

I'm leaping in the middle of this discussion...No, the -10 got
fragmentation because of shuffling and not swapping in a swell
foop.

/BAH

>
> Jan

[r***@yahoo.com]

toby wrote:
> I have to agree with Nomad here, your explanation seems to add
> confusion. You dwell on thrashing but don't mention the basic
> mechanism, which is virtualisation of process address spaces in a
> multiprogrammed system. Paging was the VAX approach and has been most
> popular since. Given the complexity of today's runtime systems it is
> hard to conceive of a practical modern computer that does not offer
> virtual memory in this sense.


Don't forget the single-address-space systems, of which the iSeries
(nee AS/400) is perhaps the most commercially successful example. Just
because process-per-address space is fashionable, doesn't mean it's
the only viable approach.

[John Dallman]

In article <***@j73g2000cwa.googlegroups.com>,
***@yahoo.com () wrote:

> Don't forget the single-address-space systems, of which the iSeries
> (nee AS/400) is perhaps the most commercially successful example.

What are the advantages of single address space?

An obvious one is the lack of need to flush processor cache on context
switches. The less obvious one that I've realised after writing most of
this post is that data shared between processes is easier to work with,
because it's axiomatically mapped at the same address in both processes.

The way memory is arranged on 32-bit AIX processes could make single
address space seem attractive anyway, actually, although 64-bit AIX is
fine.

Position-independent code works either way. Position-independent data
requires a data segment pointer register either way, but if you don't
have that, it's easier for a linker to get data ready for a per-process
address space, because you can know where things are based.

You don't get to avoid page tables and virtual/physical address mapping,
as far as I can see. You get to have fixed entry points for OS calls
either way if you want them.

---
John Dallman ***@cix.co.uk
"Any sufficiently advanced technology is indistinguishable from a
well-rigged demo"

[r***@yahoo.com]

John Dallman wrote:
> In article <***@j73g2000cwa.googlegroups.com>,
> ***@yahoo.com () wrote:
>
> > Don't forget the single-address-space systems, of which the iSeries
> > (nee AS/400) is perhaps the most commercially successful example.
>
> What are the advantages of single address space?
>
> An obvious one is the lack of need to flush processor cache on context
> switches. The less obvious one that I've realised after writing most of
> this post is that data shared between processes is easier to work with,
> because it's axiomatically mapped at the same address in both processes.
>
> The way memory is arranged on 32-bit AIX processes could make single
> address space seem attractive anyway, actually, although 64-bit AIX is
> fine.
>
> Position-independent code works either way. Position-independent data
> requires a data segment pointer register either way, but if you don't
> have that, it's easier for a linker to get data ready for a per-process
> address space, because you can know where things are based.
>
> You don't get to avoid page tables and virtual/physical address mapping,
> as far as I can see. You get to have fixed entry points for OS calls
> either way if you want them.


The big one is that different processes, including parts of the OS, can
communicate more easily, since everyone is sharing a single address
space. You get to establish shared memory by just adjusting the
permission maps of the two "processes" in question. This helps not
only applications, but things like device drivers, which now have to be
address-space aware if they want to do anything asynchronous directly
into an address space. Similarly DMA get easier when there's only one
mapping.

Most implementations have not done so due to hardware limitations, but
an SAS system can separate the permissions from the virtual memory
translation tables, and the permission tables are often quite a bit
smaller, since many of the permission can be set on a super-page basis.
So a context switch really just ends up being a change of permission
tables.

As you mentioned, one downside is that its hard to share code (.text)
between multiple processes running the same program, since you can't
remap just the data areas because they have to move and the second
instance needs all the pointers in code adjusted. So you either just
load two independent copies of the program, or require that the
compilers emit code than can deal with the relocations (or do both).

One reason SAS system have not been popular is that 32 bit CPUs just
don't have a big enough address space to support them. Even the S/38
(predecessor to the AS/400 and iSeries) had a 48 bit address space back
in the mid seventies when it was introduced. Although that's not
entirely fair, since the S/38 needed more address space since it's
single-level-storage in addition to being SAS.

SAS system have a quite long history too. Before virtual memory was
added, IBM mainframes (S/360) were all SAS (with access permissions
stored in a per-real-page tag). The various S/370 OS's still take
advantage of that hardware to subdivide the protections in a single
address space.

[John Dallman]

In article <***@j73g2000cwa.googlegroups.com>,
***@yahoo.com () wrote:

<huge snip>

> One reason SAS system have not been popular is that 32 bit CPUs just
> don't have a big enough address space to support them.

That all makes sense; thanks.

---
John Dallman ***@cix.co.uk
"Any sufficiently advanced technology is indistinguishable from a
well-rigged demo"

[Anne & Lynn Wheeler]

"***@yahoo.com" <***@yahoo.com> writes:
> Don't forget the single-address-space systems, of which the iSeries
> (nee AS/400) is perhaps the most commercially successful example. Just
> because process-per-address space is fashionable, doesn't mean it's
> the only viable approach.

precursor to as/400 was the s/38 ... which folklore has having
been a bunch of future system people taking refuge in rochester
after FS was killed. reference to future system effort earlier
in this thread.
http://www.garlic.com/~lynn/2006i.html#32 virtual memory

misc. collected postings referencing FS. I didn't make
myself particularly popular with the FS crowd at the time,
drawing some parallel between their effort and a cult film
that had been playing non-stop for several years down in
central sq.
http://www.garlic.com/~lynn/subtopic.html#futuresys

the transition of as/400 from cisc architecture to power/pc ...
involved a lot of hangling during the 620 chip architecture days
... with rochester demanding a 65th bit to be added to the 64bit
virtual addressing architecture (they eventually went their own way).

a few past posts mentioning 620, 630 and some of the other power/pc
activities:
http://www.garlic.com/~lynn/2000d.html#60 "all-out" vs less aggressive designs (was: Re: 36 to 32 bit transition)
http://www.garlic.com/~lynn/2001i.html#24 Proper ISA lifespan?
http://www.garlic.com/~lynn/2001i.html#28 Proper ISA lifespan?
http://www.garlic.com/~lynn/2001j.html#36 Proper ISA lifespan?
http://www.garlic.com/~lynn/2004q.html#40 Tru64 and the DECSYSTEM 20
http://www.garlic.com/~lynn/2005q.html#40 Intel strikes back with a parallel x86 design
http://www.garlic.com/~lynn/2005r.html#11 Intel strikes back with a parallel x86 design

i've perodically mused that the migrations of as/400 to power/pc was
somewhat fort knox reborn. circa 1980 there was an effort to migrate a
large number of the internal microprocessors to 801 chips. one of
these was to have been 370 4341 follow-on. I managed to contribute to
getting that effort killed ... as least so far as the 4381 was
concerned. misc. collected posts mentioning 801, fort knox, romp,
rios, somerset, power/pc, etc
http://www.garlic.com/~lynn/subtopic.html#801

for misc. other lore, the executive we had been reporting to when we
started the ha/cmp product effort ... moved over to head up somerset
... when somerset was started (i.e. the apple, motorola, ibm, et all
effort for power/pc).
http://www.garlic.com/~lynn/subpubtopic.html#hacmp

the initial port of os/360 (real memory) mvt to 370 virtual memory was
referred to as os/vs2 SVS (single virtual storage).

the original implementation was an mvt kernel laid out in a 16mbyte
virtual memory (somewhat akin to mvt running in 16mbyte virtual
machine) with virtual memory and page handler crafted onto the side
... and CCWTRANS borrowed from cp67.

the os/360 genre was real memory orientation with heavy dependancy on
pointer passing in majority of the APIs ... being able to process any
kind of service request required directly addressing parameter list
pointed to by the passed pointer. this was, in part, big part of
having address space for os/360 operation. The application paradigm
involving I/O was largely dependent on direct transfer from/to
application allocated storage. Application and library code would
build I/O programs with the "real" address locations that were
assigned to the application. Transition to virtual memory environment,
had the majority of application I/O involved passing address pointers
to these application build I/O programs with "application" allocated
storage addresses. In the real address world, the kernel would
schedule some I/O permission restrictions and then transfer control
directly to the application I/O program. In the transition to the
virtual address space world ... all of these application I/O programs
were now specifying virtual addresses ... not real addresses. CP67's
kernel "CCWTRAN" handled the building of "shadow" I/O program copies
... fixing the required virtual pages in real storage and translating
all of the supplied virtual address into real address for execution of
the "shadow" I/O programs.

recent post about CCWTRAN and shadow I/O programs
http://www.garlic.com/~lynn/2006b.html#25 Multiple address spaces
http://www.garlic.com/~lynn/2006f.html#5 3380-3390 Conversion - DISAPPOINTMENT

SVS evolved into MVS ... there was a separate address space for every
application. However, because of the heavy pointer passing paradigm,
the "MVS" kernel actually occupied 8mbytes of every application
16mbyte virtual address space. There was some additional hacks
required. There were some number of things called subsystems that were
part of most operational environments. They existed outside of the
kernel (in their own virtual address space) ... but in the MVT & SVS
worlds, other applications were in the habit of directly calling these
subsystem functions using pointer passing paradigm ... which required
the subsystems (which now were in separate address space) to directly
access the calling application's parameters in the application's
virtual address space.

The initial solution was something called a "COMMON" segment, a (again
initially) 1mbyte area of every virtual address space where
applications could stuff parameter values that they needed to be
accessed by called subsystems, resident in other address spaces. Over
time, as customer installations added a large variety of subsystems,
it was unusual to find the COMMON segment taking up five megabytes.
While these were MVS systems, with a unique 16mbyte virtual address
space for every application, the kernel image was taking 8mbytes out
of every virtual address space, and with a five megabyte COMMON area,
that would leave a maximum of 3mbytes for application use (out of a
16mbyte virtual address space).

Dual-address space mode was introduced in the late 70s with 3033
processor (to start to alleviate this problem caused by the extensive
use of pointer passing paradigm). This provided virtual address space
modes ... a subsystem (in its own virtual address space) could be
called with a pointer to parameters in the application address
space. The subsystem had facilities that allowed it to "reach" into
other virtual address spaces. A call to one of these subsystems still
required passing through the kernel to swap virtual address space
pointers ... and some other gorp.

recent mention of some connection between dual-address space and
itanium
http://www.garlic.com/~lynn/2006.html#39 What happens if CR's are directly changed?
http://www.garlic.com/~lynn/2006b.html#28 Multiple address spaces

Along the way there was a desire to move more of the operating system
library stuff that resided as part of the application code. So
dual-address space was generalized to multiple address space and a new
hardware facility was created called "program call". It was attempting
to achieve the efficiency of branch-and-link instruction calling some
library code with the structured protection mechanisms required to
switch virtual address spaces by passing through priviledge kernel
code. the privilege "program call" hardware table had a bunch of
permission specification controls ... including which collection of
virtual address space pointers could be moved into the various access
registers. 31-bit virtual addressing was also introduced.

today there are all sorts of combinations of 24-bit virtual
addressing, 31-bit virtual addressing, 64-bit virtual addressing
... as well as possibly several such virtual address spaces be able to
be accessed concurrently.

3.8 Address spaces ... some overview including discussion about
multiple virtual address spaces:
http://publibz.boulder.ibm.com/cgi-bin/bookmgr_OS390/BOOKS/DZ9AR004/3.8?SHELF=EZ2HW125&DT=19970613131822

2.3.5 Access Registers ... discussion of access registers 1-15
can dissignate any address space
http://publibz.boulder.ibm.com/cgi-bin/bookmgr_OS390/BOOKS/DZ9AR004/2.3.5?SHELF=EZ2HW125&DT=19970613131822

10.26 Program Call
http://publibz.boulder.ibm.com/cgi-bin/bookmgr_OS390/BOOKS/DZ9AR004/10.26?SHELF=EZ2HW125&DT=19970613131822

10.27 Program Return
http://publibz.boulder.ibm.com/cgi-bin/bookmgr_OS390/BOOKS/DZ9AR004/10.27?SHELF=EZ2HW125&DT=19970613131822

10.28 Program Transfer
http://publibz.boulder.ibm.com/cgi-bin/bookmgr_OS390/BOOKS/DZ9AR004/10.28?SHELF=EZ2HW125&DT=19970613131822

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

[Brian Inglis]

On Fri, 12 May 2006 02:30:58 GMT in alt.folklore.computers, "kim
kubik" <***@jps.net> wrote:
>"Anne & Lynn Wheeler" wrote :
>>"Doug MacKay" writes:
>>>The swap storage you're thinking of is only a small piece of a
>>>virtual memory system. If it was removed from a virtual memory
>>>system you'd still have a virtual memory system ;)
>
>> see melinda's paper on the development of virtual memory and
>> virtual machines in the 60s
>
>There are (at least) two overlapping meanings of the phrase "virtual
>memory" here: a virtual (i.e., non-real) memory address and a virtual
>eXtention ("X" as in VAX) of memory out to disk. Most people seem to
>use the latter meaning.

That's because most of the benefits are derived from having a large
total address space to fit all your work.
Of course, there are a number of different approaches to doing that.
Read the ancient SUN paper on the benefits they got by changing their
approach from managing real memory and paging space to managing a
unified address space.

The VAX extension was from PDP-11 16 bit to VAX 32 bit.
The page size dropped from 8KB to .5KB but the total real memory was
initially the same 22 bits as the PDP-11, and the I/O was the same.
They added a page modified bit but forgot about the page accessed bit.
So OSes were constantly marking pages for page out and reclaiming them
from the page out queue.

VMS implemented suboptimal local LRU, trying to guess a good working
set size for the process, and then forcing the process to page if it
needed to reference other pages, with various tweakable quotas per
system and user.
VMS also had an annoying tendency to have to drop the whole address
space for various policy reasons, with much tweaking of quotas
required to try to avoid this.

Unix ran on about 25% of VAXen to avoid those problems.

>The first, virtual memory addressing (dividing up of RAM into fixed
>sized pages) is in most cases a big win: drastic decrease in memory
>fragmentation.

PDP-11 had virtual memory and swapping: 8 x 8KB pages in each 64KB
address space (x 2 with split I/D space). Not such a big win.

>Extending RAM out to disk pages adds all the cute PhD thesis project
>benchmarkable optimizations: page size, replacement algorithms, thrash
>minimization, etc. In an early attempt a compiling TeX in SUN the person
>In an early attempt a compiling TeX in SUN the person finally shut down
>the machine after 36 hours, noting the paging daemon was taking up more
>and more of cpu time and eventually might take all of it.

Bumping the user's page limit, the system page space, an OS with a
better algorithm, a machine with more memory would proabbly have been
faster. And it's unlikely the machine was shut down: a ctrl-C (or two)
should have toasted the process, and a ctrl-\ would have done the job.

>Extending the address space out to disk for a single user desktop
>machine has one real advantage: it gives you a chance to go get
>coffee when there's a page fault.

NT and newer derivatives still seem to use the old VMS drop the whole
address space approach which leads to activity more similar to
swapping than paging, and consequent delays, particularly with the
bloated OS and apps, and vast quantities of uncollected garbage.

>It's now year 2006 -- RAM is cheap.

Cheap enough for single user desktop use, but never cheap enough for
any decent server load, particularly when desktop OSes are kludged for
use as servers.
Decent server OSes can be easily tweaked to provide good desktop
performance: the inverse is much harder, as the design goals and
consequences are so different.

Unix runs on a lot of servers to avoid those problems.

--
Thanks. Take care, Brian Inglis Calgary, Alberta, Canada

***@CSi.com (Brian[dot]Inglis{at}SystematicSW[dot]ab[dot]ca)
fake address use address above to reply

[j***@aol.com]

In article <***@4ax.com>,
Brian Inglis <***@SystematicSW.Invalid> wrote:
>On Fri, 12 May 2006 02:30:58 GMT in alt.folklore.computers, "kim
>kubik" <***@jps.net> wrote:
>>"Anne & Lynn Wheeler" wrote :
>>>"Doug MacKay" writes:
>>>>The swap storage you're thinking of is only a small piece of a
>>>>virtual memory system. If it was removed from a virtual memory
>>>>system you'd still have a virtual memory system ;)
>>
>>> see melinda's paper on the development of virtual memory and
>>> virtual machines in the 60s
>>
>>There are (at least) two overlapping meanings of the phrase "virtual
>>memory" here: a virtual (i.e., non-real) memory address and a virtual
>>eXtention ("X" as in VAX) of memory out to disk. Most people seem to
>>use the latter meaning.
>
>That's because most of the benefits are derived from having a large
>total address space to fit all your work.
>Of course, there are a number of different approaches to doing that.
>Read the ancient SUN paper on the benefits they got by changing their
>approach from managing real memory and paging space to managing a
>unified address space.
>
>The VAX extension was from PDP-11 16 bit to VAX 32 bit.
>The page size dropped from 8KB to .5KB but the total real memory was
>initially the same 22 bits as the PDP-11, and the I/O was the same.
>They added a page modified bit but forgot about the page accessed bit.
>So OSes were constantly marking pages for page out and reclaiming them
>from the page out queue.
>
>VMS implemented suboptimal local LRU, trying to guess a good working
>set size for the process, and then forcing the process to page if it
>needed to reference other pages, with various tweakable quotas per
>system and user.
>VMS also had an annoying tendency to have to drop the whole address
>space for various policy reasons, with much tweaking of quotas
>required to try to avoid this.

This is a direct side effect of a task-based OS philosophy
that evolved on small computers. Before anything new can
get done, all other stuff has to go away.

<snip>

>NT and newer derivatives still seem to use the old VMS drop the whole
>address space approach which leads to activity more similar to
>swapping than paging, and consequent delays, particularly with the
>bloated OS and apps, and vast quantities of uncollected garbage.

I would have 100% surprised if they had not. Note the source.
You cannot completely change the basis philosophy of any OS.
That's why having more than one that works well is an
absolute necessity in the computing biz.

<snip>

/BAH

[toby]

***@aol.com wrote:
> ...
> >NT and newer derivatives still seem to use the old VMS drop the whole
> >address space approach which leads to activity more similar to
> >swapping than paging, and consequent delays, particularly with the
> >bloated OS and apps, and vast quantities of uncollected garbage.
>
> I would have 100% surprised if they had not. Note the source.
> You cannot completely change the basis philosophy of any OS.
> That's why having more than one that works well is an
> absolute necessity in the computing biz.

Absolutely - diversity is a great and necessary thing. Which is why
anything that attacks diversity or promotes a monoculture should be
viewed with deep suspicion :-)

>
> <snip>
>
> /BAH

[Roland Hutchinson]

toby wrote:

> ***@aol.com wrote:
>> ...
>> >NT and newer derivatives still seem to use the old VMS drop the whole
>> >address space approach which leads to activity more similar to
>> >swapping than paging, and consequent delays, particularly with the
>> >bloated OS and apps, and vast quantities of uncollected garbage.
>>
>> I would have 100% surprised if they had not. Note the source.
>> You cannot completely change the basis philosophy of any OS.
>> That's why having more than one that works well is an
>> absolute necessity in the computing biz.
>
> Absolutely - diversity is a great and necessary thing. Which is why
> anything that attacks diversity or promotes a monoculture should be
> viewed with deep suspicion :-)

That said, if we have to pick (and it's beginning to look like we do), I'd
rather live in a Unixy monoculture than a Windozy one.

--
Roland Hutchinson              Will play viola da gamba for food.

NB mail to my.spamtrap [at] verizon.net is heavily filtered to
remove spam.  If your message looks like spam I may not see it.

[toby]

Roland Hutchinson wrote:
> toby wrote:
>
> > ***@aol.com wrote:
> >> ...
> >> That's why having more than one that works well is an
> >> absolute necessity in the computing biz.
> >
> > Absolutely - diversity is a great and necessary thing. Which is why
> > anything that attacks diversity or promotes a monoculture should be
> > viewed with deep suspicion :-)
>
> That said, if we have to pick (and it's beginning to look like we do),

I wish we did. But "10%" does not a monoculture make, and it's highly
diverse within that (always was).

> I'd rather live in a Unixy monoculture than a Windozy one.

Heartily concur.

--T

>
> --
> Roland Hutchinson Will play viola da gamba for food.
>
> NB mail to my.spamtrap [at] verizon.net is heavily filtered to
> remove spam. If your message looks like spam I may not see it.

[Brian Inglis]

On Fri, 12 May 2006 15:37:36 GMT in alt.folklore.computers, Roland
Hutchinson <***@verizon.net> wrote:

>toby wrote:
>
>> ***@aol.com wrote:
>>> ...
>>> >NT and newer derivatives still seem to use the old VMS drop the whole
>>> >address space approach which leads to activity more similar to
>>> >swapping than paging, and consequent delays, particularly with the
>>> >bloated OS and apps, and vast quantities of uncollected garbage.
>>>
>>> I would have 100% surprised if they had not. Note the source.
>>> You cannot completely change the basis philosophy of any OS.
>>> That's why having more than one that works well is an
>>> absolute necessity in the computing biz.
>>
>> Absolutely - diversity is a great and necessary thing. Which is why
>> anything that attacks diversity or promotes a monoculture should be
>> viewed with deep suspicion :-)
>
>That said, if we have to pick (and it's beginning to look like we do), I'd
>rather live in a Unixy monoculture than a Windozy one.

Unix is preferable because it's standard, and like standards, there
are so many to choose from. ;^>

--
Thanks. Take care, Brian Inglis Calgary, Alberta, Canada

***@CSi.com (Brian[dot]Inglis{at}SystematicSW[dot]ab[dot]ca)
fake address use address above to reply

[Bill Todd]

Brian Inglis wrote:

...

> NT and newer derivatives still seem to use the old VMS drop the whole
> address space approach which leads to activity more similar to
> swapping than paging, and consequent delays, particularly with the
> bloated OS and apps, and vast quantities of uncollected garbage.

It's (as usual) actually more complicated than that.

While I can't remember exactly how VMS managed inter-process memory
conflicts, NT and derivatives certainly attempt to do so with some
intelligence. The whole 'working set' approach assumes that the OS can
ascertain (preferably dynamically based on the process' paging history)
some minimum occupancy below which a given process won't be able to
function efficiently, and use that information to let some minimum set
of processes take the hit when physical memory gets tight rather than
cripple *all* processes by taking some smaller amount of memory from
each. When the mechanism works as intended, the result is that as many
processes as possible continue to run (and run reasonably well), with
bulk (and at least to some degree on-disk-contiguous) evictions and
restorations making more efficient use of the system resources than a
situation in which processes are allowed to engage in uncontrolled
fine-grained global page-thrashing.

In situations where physical memory is less constrained, the per-process
working sets expand beyond their minimum values (again, preferably
according to individual process needs rather than in a more static
manner - in which case the result does start to approximate a global
page-replacement policy, just one implemented in two tiers rather than
directly).

The underlying rationale is sound, and used to good effect in some
environments to handle portions of database queries (where it's
sometimes somewhat easier to ascertain what a given operation may need
to function well - such as an operation involving repeated bulk access
to a smallish relation which would very much like to remain
memory-resident until the operation completes): rather than let the
query dive right into the operation and execute inefficiently, when
sufficient RAM is likely to become available soon the system allows
other activity (that it thinks *can* execute efficiently) to continue
until sufficient RAM becomes available to allow the new operation to do so.

- bill

[Brian Inglis]

On Fri, 12 May 2006 17:28:37 -0400 in alt.folklore.computers, Bill
Todd <***@metrocast.net> wrote:

>Brian Inglis wrote:
>
>...
>
>> NT and newer derivatives still seem to use the old VMS drop the whole
>> address space approach which leads to activity more similar to
>> swapping than paging, and consequent delays, particularly with the
>> bloated OS and apps, and vast quantities of uncollected garbage.
>
>It's (as usual) actually more complicated than that.
>
>While I can't remember exactly how VMS managed inter-process memory
>conflicts, NT and derivatives certainly attempt to do so with some
>intelligence. The whole 'working set' approach assumes that the OS can
>ascertain (preferably dynamically based on the process' paging history)
>some minimum occupancy below which a given process won't be able to
>function efficiently, and use that information to let some minimum set
>of processes take the hit when physical memory gets tight rather than
>cripple *all* processes by taking some smaller amount of memory from
>each. When the mechanism works as intended, the result is that as many
>processes as possible continue to run (and run reasonably well), with
>bulk (and at least to some degree on-disk-contiguous) evictions and
>restorations making more efficient use of the system resources than a
>situation in which processes are allowed to engage in uncontrolled
>fine-grained global page-thrashing.

That's Cutler's VMS approach he imported into NT.

>In situations where physical memory is less constrained, the per-process
>working sets expand beyond their minimum values (again, preferably
>according to individual process needs rather than in a more static
>manner - in which case the result does start to approximate a global
>page-replacement policy, just one implemented in two tiers rather than
>directly).

See Lynn Wheeler's references downthread to CP/67 global vs local LRU
policies and results, and Stanford Ph.D. thesis on same: local sucks,
global rocks!

>The underlying rationale is sound, and used to good effect in some
>environments to handle portions of database queries (where it's
>sometimes somewhat easier to ascertain what a given operation may need
>to function well - such as an operation involving repeated bulk access
>to a smallish relation which would very much like to remain
>memory-resident until the operation completes): rather than let the
>query dive right into the operation and execute inefficiently, when
>sufficient RAM is likely to become available soon the system allows
>other activity (that it thinks *can* execute efficiently) to continue
>until sufficient RAM becomes available to allow the new operation to do so.

Local LRU (like microkernels) was considered superior by academics,
but global LRU (like monolithic kernels) is better on real workloads.

--
Thanks. Take care, Brian Inglis Calgary, Alberta, Canada

***@CSi.com (Brian[dot]Inglis{at}SystematicSW[dot]ab[dot]ca)
fake address use address above to reply

[Bill Todd]

Brian Inglis wrote:

...

>> In situations where physical memory is less constrained, the per-process
>> working sets expand beyond their minimum values (again, preferably
>> according to individual process needs rather than in a more static
>> manner - in which case the result does start to approximate a global
>> page-replacement policy, just one implemented in two tiers rather than
>> directly).
>
> See Lynn Wheeler's references downthread to CP/67 global vs local LRU
> policies and results, and Stanford Ph.D. thesis on same:

I took a quick look and saw nothing specific, so you'll need to provide
a pointer or two.

local sucks,
> global rocks!

Fanboy bluster, in the absence of credible references.

>
>> The underlying rationale is sound, and used to good effect in some
>> environments to handle portions of database queries (where it's
>> sometimes somewhat easier to ascertain what a given operation may need
>> to function well - such as an operation involving repeated bulk access
>> to a smallish relation which would very much like to remain
>> memory-resident until the operation completes): rather than let the
>> query dive right into the operation and execute inefficiently, when
>> sufficient RAM is likely to become available soon the system allows
>> other activity (that it thinks *can* execute efficiently) to continue
>> until sufficient RAM becomes available to allow the new operation to do so.
>
> Local LRU (like microkernels) was considered superior by academics,
> but global LRU (like monolithic kernels) is better on real workloads.

While I happen to agree about the relative merits of microkernels, their
applicability to the current discussion escapes me (save as a marginal
comment on the fallibility of academics - a tribe which Cutler did not
hold in especially high esteem and of which he was not a member).

Once again, you'll have to provide substantial references for your
personal assertion of what constitutes 'reality' to become credible.

- bill

[toby]

Bill Todd wrote:
> Brian Inglis wrote:
> ...
> > Local LRU (like microkernels) was considered superior by academics,
> > but global LRU (like monolithic kernels) is better on real workloads.
>
> While I happen to agree about the relative merits of microkernels, their
> applicability to the current discussion escapes me (save as a marginal
> comment on the fallibility of academics - a tribe which Cutler did not
> hold in especially high esteem and of which he was not a member).
>
> Once again, you'll have to provide substantial references for your
> personal assertion of what constitutes 'reality' to become credible.

This is going to be a long thread... I can just feel it!

>
> - bill

[Anne & Lynn Wheeler]

Bill Todd <***@metrocast.net> writes:
> I took a quick look and saw nothing specific, so you'll need to
> provide a pointer or two.

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

I posted it numerous times before ... so there were URLs to
where it had been repeatedly posted before

basically i had done local LRU. cambridge had 768kbyte 360/67,
104 "pageable pages" after fixed kernel requirements running
cp67.

grenoble modified they same cp67 for "working set" dispatcher and
local LRU running on 1mbyte 360/67, 154 "pageable pages" after fixed
kernel requirements (basically 50 percent more real storage for
application paging). they published a paper on the work in the early
70s in cacm

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

basically running same kind of workload, cambridge ran approx. 80
users with the same interactive response and thruput as grenoble did
with 35 users i.e. cambridge system with 1/3rd less real storage for
application paging was able to support more than twice as many users
with comperable thruput and no worse interactive response
... typically much better. the interactive response was somewhat more
sensitive to latency associated with the "working dispatcher"
attempting to avoid page thrashing and how effective local LRU was in
selecting pages for replacement ... so the cambridge system response
... even with more than twice as many users typically had better
interactive response and lower latency delays.

specific reference from the earlier listed "grenoble" references
http://www.garlic.com/~lynn/2001c.html#10 Memory management - Page replacement

after all the festuche had settled, the stanford phd on clock and
global lru was finally awarded ... despite the best efforts by some of
the backers of local LRU.

consistent with the stuff I had invented as an undergraduate in the
60s ... also, about the time the whole uproar was going on over
whether somebody would get a stanford phd thesis on global LRU ... we
had a project that was recording all disk record references from a
variety of operational production systems.

there were also a fairly sophisticated cache simulator built which was
looking at various disk i/o caching strategies. simulation was done
for a broad range of different configurations, disk arm caching,
controller caching, channel caching, system caching, etc. across the
broad range of different environments and workloads, it was found for
a given amount of electronic storage ... system level caching always
provided better throughput (modulo some issues with use of some disk
arm store for rotational delay compensation ... i.e. being able to
start i/o transfer as soon the head had settled as opposed to waiting
for the records to arrive under the head in a specified sequence). if
there was a fixed amount of electronic cache ... say 20mbytes
... using that 20mbytes for a system level cache always provided
better thruput than breaking the electronic store up and partitioining
it out to any level of sub-components.

partitioning the electronic store and parceling it out to
subcomponents is analogous to doing local LRU replacement strategy
(i.e. partitioning real memory and only doing replacement within the
individual partitions).

aggregating the electronic store into a single larger cache is
analogous to doing global LRU replacement strategy.

some past posts mentioning the global versus partitioned cache
work:
http://www.garlic.com/~lynn/95.html#3 What is an IBM 137/148 ???
http://www.garlic.com/~lynn/99.html#104 Fixed Head Drive (Was: Re:Power distribution (Was: Re: A primeval C compiler)
http://www.garlic.com/~lynn/99.html#105 Fixed Head Drive (Was: Re:Power distribution (Was: Re: A primeval C compiler)
http://www.garlic.com/~lynn/2000d.html#11 4341 was "Is a VAX a mainframe?"
http://www.garlic.com/~lynn/2001l.html#55 mainframe question
http://www.garlic.com/~lynn/2004g.html#13 Infiniband - practicalities for small clusters
http://www.garlic.com/~lynn/2004i.html#0 Hard disk architecture: are outer cylinders still faster than
http://www.garlic.com/~lynn/2004q.html#76 Athlon cache question
http://www.garlic.com/~lynn/2005.html#2 Athlon cache question
http://www.garlic.com/~lynn/2005m.html#28 IBM's mini computers--lack thereof
http://www.garlic.com/~lynn/2005n.html#23 Code density and performance?
http://www.garlic.com/~lynn/2006b.html#14 Expanded Storage
http://www.garlic.com/~lynn/2006f.html#0 using 3390 mod-9s

and for some drift and urban legend
http://susandennis.livejournal.com/2003/02/04/

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

[Anne & Lynn Wheeler]

Anne & Lynn Wheeler <***@garlic.com> writes:
> specific reference from the earlier listed "grenoble" references
> http://www.garlic.com/~lynn/2001c.html#10 Memory management - Page replacement

more of the references listed in the above:

L. Belady, A Study of Replacement Algorithms for a Virtual Storage
Computer, IBM Systems Journal, v5n2, 1966

L. Belady, The IBM History of Memory Management Technology, IBM
Journal of R&amp;D, v25n5

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

P. Denning, Working sets past and present, IEEE Trans Softw Eng, SE6,
jan80

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

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

....

for a little more drift, the Hatfield & Gerald reference in the
above eventually resulted in a product called VS/REPACK ...
another product of the science center
http://www.garlic.com/~lynn/subtopic.html#545tech

i wasn't involved directly in any of the analysis part of the product
... but i wrote a lot of the data collection facilities that was used
to collect the data that vs/repack analysed.

for additional random drift, various past posts mentioning
vs/repack
http://www.garlic.com/~lynn/94.html#7 IBM 7090 (360s, 370s, apl, etc)
http://www.garlic.com/~lynn/99.html#68 The Melissa Virus or War on Microsoft?
http://www.garlic.com/~lynn/2000g.html#30 Could CDR-coding be on the way back?
http://www.garlic.com/~lynn/2001b.html#83 Z/90, S/390, 370/ESA (slightly off topic)
http://www.garlic.com/~lynn/2001c.html#31 database (or b-tree) page sizes
http://www.garlic.com/~lynn/2001c.html#33 database (or b-tree) page sizes
http://www.garlic.com/~lynn/2001i.html#20 Very CISC Instuctions (Was: why the machine word size ...)
http://www.garlic.com/~lynn/2002c.html#28 OS Workloads : Interactive etc
http://www.garlic.com/~lynn/2002c.html#45 cp/67 addenda (cross-post warning)
http://www.garlic.com/~lynn/2002c.html#46 cp/67 addenda (cross-post warning)
http://www.garlic.com/~lynn/2002c.html#49 Swapper was Re: History of Login Names
http://www.garlic.com/~lynn/2002e.html#50 IBM going after Strobe?
http://www.garlic.com/~lynn/2002f.html#50 Blade architectures
http://www.garlic.com/~lynn/2003f.html#15 Alpha performance, why?
http://www.garlic.com/~lynn/2003f.html#21 "Super-Cheap" Supercomputing
http://www.garlic.com/~lynn/2003f.html#53 Alpha performance, why?
http://www.garlic.com/~lynn/2003g.html#15 Disk capacity and backup solutions
http://www.garlic.com/~lynn/2003h.html#8 IBM says AMD dead in 5yrs ... -- Microsoft Monopoly vs. IBM
http://www.garlic.com/~lynn/2003j.html#32 Language semantics wrt exploits
http://www.garlic.com/~lynn/2004.html#14 Holee shit! 30 years ago!
http://www.garlic.com/~lynn/2004c.html#21 PSW Sampling
http://www.garlic.com/~lynn/2004m.html#22 Lock-free algorithms
http://www.garlic.com/~lynn/2004n.html#55 Integer types for 128-bit addressing
http://www.garlic.com/~lynn/2004o.html#7 Integer types for 128-bit addressing
http://www.garlic.com/~lynn/2004q.html#73 Athlon cache question
http://www.garlic.com/~lynn/2004q.html#76 Athlon cache question
http://www.garlic.com/~lynn/2005.html#4 Athlon cache question
http://www.garlic.com/~lynn/2005d.html#41 Thou shalt have no other gods before the ANSI C standard
http://www.garlic.com/~lynn/2005d.html#48 Secure design
http://www.garlic.com/~lynn/2005h.html#15 Exceptions at basic block boundaries
http://www.garlic.com/~lynn/2005j.html#62 More on garbage collection
http://www.garlic.com/~lynn/2005k.html#17 More on garbage collection
http://www.garlic.com/~lynn/2005m.html#28 IBM's mini computers--lack thereof
http://www.garlic.com/~lynn/2005n.html#18 Code density and performance?
http://www.garlic.com/~lynn/2005o.html#5 Code density and performance?
http://www.garlic.com/~lynn/2006b.html#15 {SPAM?} Re: Expanded Storage
http://www.garlic.com/~lynn/2006b.html#23 Seeking Info on XDS Sigma 7 APL
http://www.garlic.com/~lynn/2006e.html#20 About TLB in lower-level caches
http://www.garlic.com/~lynn/2006e.html#46 using 3390 mod-9s

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

[Anne & Lynn Wheeler]

Anne & Lynn Wheeler <***@garlic.com> writes:
> L. Belady, A Study of Replacement Algorithms for a Virtual Storage
> Computer, IBM Systems Journal, v5n2, 1966
>
> L. Belady, The IBM History of Memory Management Technology, IBM
> Journal of R&amp;D, v25n5
>
> 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
>
> P. Denning, Working sets past and present, IEEE Trans Softw Eng, SE6,
> jan80
>
> J. Rodriquez-Rosell, The design, implementation, and evaluation of a
> working set dispatcher, cacm16, apr73
>
> D. Hatfield &amp; J. Gerald, Program Restructuring for Virtual Memory,
> IBM Systems Journal, v10n3, 1971

a couple other specific postings about the above:
http://www.garlic.com/~lynn/2002c.html#49 Swapper was Re: History of Login Names
http://www.garlic.com/~lynn/93.html#4 360/67, was Re: IBM's Project F/S ?
http://www.garlic.com/~lynn/94.html#49 Rethinking Virtual Memory

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

[Anne & Lynn Wheeler]

another posting going over this
http://www.garlic.com/~lynn/2004i.html#0 Hard disk architecture: are outer cylinders still faster than

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

[Anne & Lynn Wheeler]

Anne & Lynn Wheeler <***@garlic.com> writes:
> consistent with the stuff I had invented as an undergraduate in the
> 60s ... also, about the time the whole uproar was going on over
> whether somebody would get a stanford phd thesis on global LRU ... we
> had a project that was recording all disk record references from a
> variety of operational production systems.
>
> there were also a fairly sophisticated cache simulator built which was
> looking at various disk i/o caching strategies. simulation was done
> for a broad range of different configurations, disk arm caching,
> controller caching, channel caching, system caching, etc. across the
> broad range of different environments and workloads, it was found for
> a given amount of electronic storage ... system level caching always
> provided better throughput (modulo some issues with use of some disk
> arm store for rotational delay compensation ... i.e. being able to
> start i/o transfer as soon the head had settled as opposed to waiting
> for the records to arrive under the head in a specified sequence). if
> there was a fixed amount of electronic cache ... say 20mbytes
> ... using that 20mbytes for a system level cache always provided
> better thruput than breaking the electronic store up and partitioining
> it out to any level of sub-components.
>
> partitioning the electronic store and parceling it out to
> subcomponents is analogous to doing local LRU replacement strategy
> (i.e. partitioning real memory and only doing replacement within the
> individual partitions).
>
> aggregating the electronic store into a single larger cache is
> analogous to doing global LRU replacement strategy.

in this previous incarnation of the thread/subject from 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?

there was the issue of paging virtual memory being a flavor of cache
managed by LRU-type replacement algorithms. besides the similarity
between global/local LRU replacement and configuration decision about
having fixed amount of electronic store as a single "system" global
cache or partitioned and divided up into smaller caches dedicated to
specific sub devices ... you can also get into the subject of cache
hierarchies as well as technology limitations where you have lots of
electronic store and for various issues that it can't all be applied
to the highest level in the hierarchy (in which case still being able
to use the available electronic storage at other levels in the
infrastructure might still provide some benefit).

an example of the limitation issues was the 4.5mip 3033 processor
versus a cluster of six 1mip 4341 processors. initially, all the real
memory you could with either the 3033 or the 4341 was 16mbytes. six
1mip 4341 processors with 16mbytes of electronic store each (96mbytes
total) cost about the same as a 4.5mip 3033 processor with 16mbytes
(16mbytes total) .... assuming the workload was partitionable in a
cluster, the six 4341 cluster got much higher thruput than the single
3033 at about the same price.

the cache hiearchy could have other issues that I've referred to as
the dup/no-up problem. circa 1981, you could get a 3880 disk
controller with cache ... limited to 8mbytes. if came as a
3880-11/ironwood and cache line was 4k records or 3880-13/sheriff
where cache line was full-track.

a 3033 or 3081 with 16mbytes real storage might have two such disk
controllers in configuration for a total of 16mbytes of disk
controller cache. the issue in the "duplicate" strategy was if every
page fault by the processor pulled in a page from disk, thru the disk
controller cache, a copy of the page would be resident in both the
disk controller cache and the processor memory (i.e. there was a
duplicate in both places). then what happens is when could there be a
page that wasn't in the processor 16mbyte memory that happened to be
in the disk cache? i.e. if the processor faulted on a virtual page
(because it wasn't resident and needed to be brought in from disk),
was there a reasonable probability that a page not in processor memory
being found in the disk cache. if the total disk cache held about the
same number of 4k records as the main processor memory and every
record in processor memory was duplicated in disk cache ... what was
the probability that there was a 4k record in disk cache that wasn't
in processor memory.

I had actually started working on a resource management
duplicate/no-duplicate strategy with page migration in configuration
with a hierarchy of different performance paging devices (fixed-head
2305s and lots of moveable arm 3330 disks) in the 70s ... which
was released as part of the resource manager on 11may1976 .. a couple
recent references:
http://www.garlic.com/~lynn/2006h.html#25 The Pankian Metaphor
http://www.garlic.com/~lynn/2006i.html#24 Virtual memory implementation in S/370
http://www.garlic.com/~lynn/2006i.html#26 11may76, 30 years, (re-)release of resource manager
http://www.garlic.com/~lynn/2006i.html#28 virtual memory

in the 3380-ii/ironwood scenario the processor page i/o could do reads
that were "normal" (if it wasn't in the disk cache, it would be read
into both disk cache and processor memory, if it was in disk cache, it
would be read directly from cache) or "destructive" (if it was in the
disk cache, it would be read from disk cache and deallocated from the
cache ... aka destructive read; if it wasn't in disk cache, it would
be read directly into processor memory w/o involving the cache).

misc. past posts mentioning duplicate/no-duplicate scenarios
for hierarchical caches
http://www.garlic.com/~lynn/93.html#12 managing large amounts of vm
http://www.garlic.com/~lynn/93.html#13 managing large amounts of vm
http://www.garlic.com/~lynn/94.html#9 talk to your I/O cache
http://www.garlic.com/~lynn/2000d.html#13 4341 was "Is a VAX a mainframe?"
http://www.garlic.com/~lynn/2001i.html#42 Question re: Size of Swap File
http://www.garlic.com/~lynn/2001l.html#55 mainframe question
http://www.garlic.com/~lynn/2001n.html#78 Swap partition no bigger than 128MB?????
http://www.garlic.com/~lynn/2002b.html#10 hollow files in unix filesystems?
http://www.garlic.com/~lynn/2002b.html#16 hollow files in unix filesystems?
http://www.garlic.com/~lynn/2002b.html#19 hollow files in unix filesystems?
http://www.garlic.com/~lynn/2002b.html#20 index searching
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/2002f.html#26 Blade architectures
http://www.garlic.com/~lynn/2003f.html#5 Alpha performance, why?
http://www.garlic.com/~lynn/2003o.html#62 1teraflops cell processor possible?
http://www.garlic.com/~lynn/2004g.html#17 Infiniband - practicalities for small clusters
http://www.garlic.com/~lynn/2004g.html#18 Infiniband - practicalities for small clusters
http://www.garlic.com/~lynn/2004g.html#20 Infiniband - practicalities for small clusters
http://www.garlic.com/~lynn/2004h.html#19 fast check for binary zeroes in memory
http://www.garlic.com/~lynn/2004i.html#1 Hard disk architecture: are outer cylinders still faster than inner cylinders?
http://www.garlic.com/~lynn/2005c.html#27 [Lit.] Buffer overruns
http://www.garlic.com/~lynn/2005m.html#28 IBM's mini computers--lack thereof
http://www.garlic.com/~lynn/2006c.html#8 IBM 610 workstation computer
http://www.garlic.com/~lynn/2006e.html#45 using 3390 mod-9s
http://www.garlic.com/~lynn/2006f.html#18 how much swap size did you take?

misc. past posts mentioning the 3033/4341 partitioned comparison
(implementation issues)
http://www.garlic.com/~lynn/95.html#3 What is an IBM 137/148 ???
http://www.garlic.com/~lynn/99.html#7 IBM S/360
http://www.garlic.com/~lynn/99.html#110 OS/360 names and error codes (was: Humorous and/or Interesting Opcodes)
http://www.garlic.com/~lynn/99.html#112 OS/360 names and error codes (was: Humorous and/or Interesting Opcodes)
http://www.garlic.com/~lynn/2000d.html#7 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#82 "all-out" vs less aggressive designs (was: Re: 36 to 32 bit transition)
http://www.garlic.com/~lynn/2000e.html#57 Why not an IBM zSeries workstation?
http://www.garlic.com/~lynn/2001b.html#69 Z/90, S/390, 370/ESA (slightly off topic)
http://www.garlic.com/~lynn/2001i.html#13 GETMAIN R/RU (was: An IEABRC Adventure)
http://www.garlic.com/~lynn/2001j.html#3 YKYGOW...
http://www.garlic.com/~lynn/2001l.html#32 mainframe question
http://www.garlic.com/~lynn/2001m.html#15 departmental servers
http://www.garlic.com/~lynn/2001n.html#39 195 was: Computer Typesetting Was: Movies with source code
http://www.garlic.com/~lynn/2002b.html#2 Microcode? (& index searching)
http://www.garlic.com/~lynn/2002d.html#7 IBM Mainframe at home
http://www.garlic.com/~lynn/2002f.html#8 Is AMD doing an Intel?
http://www.garlic.com/~lynn/2002i.html#22 CDC6600 - just how powerful a machine was it?
http://www.garlic.com/~lynn/2002i.html#23 CDC6600 - just how powerful a machine was it?
http://www.garlic.com/~lynn/2002n.html#58 IBM S/370-168, 195, and 3033
http://www.garlic.com/~lynn/2002n.html#59 IBM S/370-168, 195, and 3033
http://www.garlic.com/~lynn/2002n.html#63 Help me find pics of a UNIVAC please
http://www.garlic.com/~lynn/2002p.html#59 AMP vs SMP
http://www.garlic.com/~lynn/2002q.html#27 Beyond 8+3
http://www.garlic.com/~lynn/2002q.html#29 Collating on the S/360-2540 card reader?
http://www.garlic.com/~lynn/2003.html#14 vax6k.openecs.org rebirth
http://www.garlic.com/~lynn/2003.html#67 3745 & NCP Withdrawl?
http://www.garlic.com/~lynn/2003c.html#77 COMTEN- IBM networking boxes
http://www.garlic.com/~lynn/2003d.html#33 Why only 24 bits on S/360?
http://www.garlic.com/~lynn/2003f.html#50 Alpha performance, why?
http://www.garlic.com/~lynn/2003f.html#56 ECPS:VM DISPx instructions
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/2003j.html#2 Fix the shuttle or fly it unmanned
http://www.garlic.com/~lynn/2003l.html#31 IBM Manuals from the 1940's and 1950's
http://www.garlic.com/~lynn/2004.html#7 Dyadic
http://www.garlic.com/~lynn/2004.html#8 virtual-machine theory
http://www.garlic.com/~lynn/2004d.html#12 real multi-tasking, multi-programming
http://www.garlic.com/~lynn/2004g.html#20 Infiniband - practicalities for small clusters
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#17 mainframe and microprocessor
http://www.garlic.com/~lynn/2004n.html#14 360 longevity, was RISCs too close to hardware?
http://www.garlic.com/~lynn/2004n.html#50 Integer types for 128-bit addressing
http://www.garlic.com/~lynn/2004o.html#57 Integer types for 128-bit addressing
http://www.garlic.com/~lynn/2005.html#34 increasing addressable memory via paged memory?
http://www.garlic.com/~lynn/2005d.html#62 Misuse of word "microcode"
http://www.garlic.com/~lynn/2005f.html#4 System/360; Hardwired vs. Microcoded
http://www.garlic.com/~lynn/2005m.html#25 IBM's mini computers--lack thereof
http://www.garlic.com/~lynn/2005n.html#11 Code density and performance?
http://www.garlic.com/~lynn/2005n.html#29 Data communications over telegraph circuits
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#30 HASP/ASP JES/JES2/JES3
http://www.garlic.com/~lynn/2005q.html#38 Intel strikes back with a parallel x86 design
http://www.garlic.com/~lynn/2005s.html#22 MVCIN instruction
http://www.garlic.com/~lynn/2005u.html#40 POWER6 on zSeries?
http://www.garlic.com/~lynn/2005u.html#44 POWER6 on zSeries?
http://www.garlic.com/~lynn/2005u.html#48 POWER6 on zSeries?
http://www.garlic.com/~lynn/2006b.html#28 Multiple address spaces
http://www.garlic.com/~lynn/2006b.html#34 Multiple address spaces
http://www.garlic.com/~lynn/2006b.html#39 another blast from the past
http://www.garlic.com/~lynn/2006i.html#33 virtual memory


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

[Eric P.]

Anne & Lynn Wheeler wrote:
>
> Bill Todd <***@metrocast.net> writes:
> > I took a quick look and saw nothing specific, so you'll need to
> > provide a pointer or two.
>
> ref:
> http://www.garlic.com/~lynn/2006i.html#31 virtual memory
>
> I posted it numerous times before ... so there were URLs to
> where it had been repeatedly posted before
>
> basically i had done local LRU. cambridge had 768kbyte 360/67,
> 104 "pageable pages" after fixed kernel requirements running
> cp67.
>
> grenoble modified they same cp67 for "working set" dispatcher and
> local LRU running on 1mbyte 360/67, 154 "pageable pages" after fixed
> kernel requirements (basically 50 percent more real storage for
> application paging). they published a paper on the work in the early
> 70s in cacm

After our previous discussions, I looked high and low for any details
on the grenoble system, and fifo or local working sets on cp67.
Unfortunately I found nothing.

My suspicion is that Grenoble used strict fifo local working sets.
These are now known (possibly as a result of that very project)
to not perform well.

VMS and WNT use Second Chance Fifo, which has very different behavior
to strict Fifo, and is reputed to have the same behavior as WSClock.
VMS also has an option for a third chance - I don't know if WNT
also has that. This gives them all the control advantages that
local working sets allow with the same paging statistics as global.

In second chance fifo, pages removed from a local working set are
tossed into a global Valid list to become a candidate for recycling.
If referenced again quickly the page is pulled page into the local
working set for almost no cost. This is essentially the same as
the WSClock and its referenced bits.

In 3rd chance, VMS allows a page to make 2 trips through the working
set list. After the first trip a flag is set on the working set entry
it goes to the tail of the list and the PTE's valid flag is cleared.
If it gets touched again then the handler just enables the PTE.
When it gets to the head of the list again the PTE is checked to
see if it was referenced. If is was, it cycles again, otherwise
it goes into the global Valid list. [1]

The working set size is not fixed but can vary if memory is available.
If a process pages too much the size is increased until it stops. [2}

The combination of all these features makes the VMS/WNT local
working sets completely different from the early strict fifo models.

[1] My informal experiments on VMS found that enabling the 3rd
chance mechanism had no effect on performance. The 2nd chance
mechanism appears to be quite sufficient.

[2] A valid criticism of VMS, and possibly WNT, is they use boot time
sized arrays to track the working set entries rather than linked lists.
Because of this there is an absolute maximum working set size and
processes which reach that maximum will page fault even when there is
gobs of free memory on a system. However that is a deficiency in a
particular implementation and not due to the local working sets.

There is no technical reason for these to not allow process working
sets to be arbitrarily large, up to all of virtual space is memory
is available, and use dynamic software controls to limit their size.

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

Thanks, I didn't see this reference before. Unfortunately it is
imprisoned inside the ACM.

Eric

[Anne & Lynn Wheeler]

"Eric P." <***@sympaticoREMOVE.ca> writes:
> After our previous discussions, I looked high and low for any details
> on the grenoble system, and fifo or local working sets on cp67.
> Unfortunately I found nothing.
>
> My suspicion is that Grenoble used strict fifo local working sets.
> These are now known (possibly as a result of that very project)
> to not perform well.
>
> VMS and WNT use Second Chance Fifo, which has very different behavior
> to strict Fifo, and is reputed to have the same behavior as WSClock.
> VMS also has an option for a third chance - I don't know if WNT
> also has that. This gives them all the control advantages that
> local working sets allow with the same paging statistics as global.
>
> In second chance fifo, pages removed from a local working set are
> tossed into a global Valid list to become a candidate for recycling.
> If referenced again quickly the page is pulled page into the local
> working set for almost no cost. This is essentially the same as
> the WSClock and its referenced bits.
>
> In 3rd chance, VMS allows a page to make 2 trips through the working
> set list. After the first trip a flag is set on the working set entry
> it goes to the tail of the list and the PTE's valid flag is cleared.
> If it gets touched again then the handler just enables the PTE.
> When it gets to the head of the list again the PTE is checked to
> see if it was referenced. If is was, it cycles again, otherwise
> it goes into the global Valid list. [1]
>
> The working set size is not fixed but can vary if memory is available.
> If a process pages too much the size is increased until it stops. [2}
>
> The combination of all these features makes the VMS/WNT local
> working sets completely different from the early strict fifo models.
>
> [1] My informal experiments on VMS found that enabling the 3rd
> chance mechanism had no effect on performance. The 2nd chance
> mechanism appears to be quite sufficient.
>
> [2] A valid criticism of VMS, and possibly WNT, is they use boot time
> sized arrays to track the working set entries rather than linked lists.
> Because of this there is an absolute maximum working set size and
> processes which reach that maximum will page fault even when there is
> gobs of free memory on a system. However that is a deficiency in a
> particular implementation and not due to the local working sets.
>
> There is no technical reason for these to not allow process working
> sets to be arbitrarily large, up to all of virtual space is memory
> is available, and use dynamic software controls to limit their size.
>
>> J. Rodriquez-Rosell, The design, implementation, and evaluation of a
>> working set dispatcher, cacm16, apr73
>
> Thanks, I didn't see this reference before. Unfortunately it is
> imprisoned inside the ACM.

some posts in previous incarnation of this thread from
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 original cp67 that was installed in the univ. last week jan68
used effectively a variation on fifo; it scanned storage looking
for pages in state somewhat like your second chance ... and if it
couldn't find one ... it took a standard page.

within several months, i had changed that and added testing and
resetting of the reference bits in cycle. ... basically clock like
operation.

grenoble used resetting of reference bits in local LRU.

so multics did a multi-bit reference cycle operation ... 5th floor,
545 tech. sq; science center was on 4th floor 545 tech sq.
http://www.garlic.com/~lynn/subtopic.html#545tech

the original cp67 didn't have any thrashing controls. early in '68,
lincoln labs made a modification that limited the total number of
processes in the active/dispatch set ... as a means of limiting
page contention ... however, it didn't take into account amount
of pages needed by different virtual address spaces.

i added some calculations that measured real storage requirements of a
virtual address space. the real storage requierment calculations were
dynamically adjusted that included some measure of proportion of time
spent waiting for page fault servicing ... aka if total page fault
service time was low, estimate of virtual address space requirement
for real storage was lowered, if total page fault service time was
high, estimate of virtual address space requirement for real storage
was increased ... basically dynamically adapting amount of real
storage requirements to configuration, workload, and contention
(i.e. high paging rates that also introduced long queues and high
service times would increase estimates of real storage requirements,
the same high paging rates with higher speed devices and no queues,
and much lower service times would have lower estimates of real
storage requirements).

in the early 70s, we ran huge number of experiments with lots of
different code implementation in live operation as well as having
various kinds of detailed simulators that also tried wide variety of
different implementation details.

one of the scenarios that i had come up with (in the early 70s) was
something that would beat true LRU. in part, LRU is based on
assumption that pages used in the recent past are likely to be used in
the near future. this is only a rough guess across a wide range of
different operational characteristics. sometimes the LRU related
assumption about page use is very accurate and sometimes it has no
relationship to what is actually happening. in some cases, LRU
replacement degenerates to FIFO and is not the optimal strategy.

the simulators could mimick the actual implementations which all
tended to be approximations of true LRU. the simulators could also
implement actual LRU (ordering page reference on every instruction
executed). In general, the simulators found that "true" LRU did 10-15
precent better than the real-world LRU approximation implementations.
so there had been lots and lots of work attempting to come closer and
closer to "true" LRU.

however, the gimick that I had come up looked, tasted and operated as
standard clock ... a flavor of LRU approximation. The referenced
multics experiment with multiple reference bits basically kept longer
and longer history ... attempting to come closer and closer to a
"true" LRU implementation.

I did a slight-of-hand coding trick in an implementation ... where all
the standard LRU varieties degenerated to FIFO under various
conditions ... this slight-of-hand coding gimick degneerated to RANDOM
under the same conditions. as a result, when LRU was applicable, both
"true" LRU and my LRU approximation gimick operated nearly the same.
however, it operational regions when LRU would degenerate to FIFO, my
coding slight-of-hand degenerated to RANDOM automagically (aka there
was no explicit code to switch from LRU to RANDOM ... it just turned
out that the coding slight-of-hand resulted in the implementation
degenerating to RANDOM rather than FIFO).

previously mentioned references:
L. Belady, A Study of Replacement Algorithms for a Virtual Storage
Computer, IBM Systems Journal, v5n2, 1966

L. Belady, The IBM History of Memory Management Technology, IBM
Journal of R&amp;D, v25n5

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

P. Denning, Working sets past and present, IEEE Trans Softw Eng, SE6,
jan80

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

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

past posts mentioning lru, fifo, random:
http://www.garlic.com/~lynn/94.html#1 Multitasking question
http://www.garlic.com/~lynn/94.html#4 Schedulers
http://www.garlic.com/~lynn/94.html#10 lru, clock, random & dynamic adaptive
http://www.garlic.com/~lynn/94.html#14 lru, clock, random & dynamic adaptive ... addenda
http://www.garlic.com/~lynn/94.html#54 How Do the Old Mainframes
http://www.garlic.com/~lynn/98.html#17 S/360 operating systems geneaology
http://www.garlic.com/~lynn/2000f.html#9 Optimal replacement Algorithm
http://www.garlic.com/~lynn/2000f.html#32 Optimal replacement Algorithm
http://www.garlic.com/~lynn/2000f.html#34 Optimal replacement Algorithm
http://www.garlic.com/~lynn/2001f.html#55 any 70's era supercomputers that ran as slow as today's supercomputers?
http://www.garlic.com/~lynn/2002j.html#31 Unisys A11 worth keeping?
http://www.garlic.com/~lynn/2002j.html#32 Latency benchmark (was HP Itanium2 benchmarks)
http://www.garlic.com/~lynn/2002j.html#35 Latency benchmark (was HP Itanium2 benchmarks)
http://www.garlic.com/~lynn/2003f.html#53 Alpha performance, why?
http://www.garlic.com/~lynn/2003g.html#0 Alpha performance, why?
http://www.garlic.com/~lynn/2003i.html#72 A few Z990 Gee-Wiz stats
http://www.garlic.com/~lynn/2004l.html#66 Lock-free algorithms
http://www.garlic.com/~lynn/2004o.html#9 Integer types for 128-bit addressing
http://www.garlic.com/~lynn/2004q.html#73 Athlon cache question
http://www.garlic.com/~lynn/2004q.html#77 Athlon cache question
http://www.garlic.com/~lynn/2005j.html#51 Q ALLOC PAGE vs. CP Q ALLOC vs ESAMAP
http://www.garlic.com/~lynn/2005n.html#23 Code density and performance?
http://www.garlic.com/~lynn/2006b.html#15 {SPAM?} Re: Expanded Storage
http://www.garlic.com/~lynn/2006d.html#21 IBM 610 workstation computer


past 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

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

[CBFalconer]

Anne & Lynn Wheeler wrote:
>
... snip ...
>
> one of the scenarios that i had come up with (in the early 70s) was
> something that would beat true LRU. in part, LRU is based on
> assumption that pages used in the recent past are likely to be used in
> the near future. this is only a rough guess across a wide range of
> different operational characteristics. sometimes the LRU related
> assumption about page use is very accurate and sometimes it has no
> relationship to what is actually happening. in some cases, LRU
> replacement degenerates to FIFO and is not the optimal strategy.

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.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>

[Anne & Lynn Wheeler]

CBFalconer <***@yahoo.com> 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/

[Anne & Lynn Wheeler]

CBFalconer <***@yahoo.com> 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 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.

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/

[Anne & Lynn Wheeler]

Anne & Lynn Wheeler <***@garlic.com> 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).

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/

[Anne & Lynn Wheeler]

Anne & Lynn Wheeler <***@garlic.com> 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).

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/

[Anne & Lynn Wheeler]

Anne & Lynn Wheeler <***@garlic.com> 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 vary all over the
place.

zero'ing 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/

[Eric P.]

Anne & Lynn Wheeler wrote:
>
> grenoble used resetting of reference bits in local LRU.

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.

Eric

[Anne & Lynn Wheeler]

"Eric P." <***@sympaticoREMOVE.ca> 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/

[Eric P.]

Anne & Lynn Wheeler wrote:
>
> "Eric P." <***@sympaticoREMOVE.ca> writes:
> >
> > 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).

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?

> <snip>
> 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.

Penalized? For selling the same patch for major bucks to two
different customers to correct a deficiency in their own software?

They are probably all executives now.

Eric

[Anne & Lynn Wheeler]

"Eric P." <***@sympaticoREMOVE.ca> 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/

[Anne & Lynn Wheeler]

"Eric P." <***@sympaticoREMOVE.ca> writes:
> VMS and WNT use Second Chance Fifo, which has very different behavior
> to strict Fifo, and is reputed to have the same behavior as WSClock.
> VMS also has an option for a third chance - I don't know if WNT
> also has that. This gives them all the control advantages that
> local working sets allow with the same paging statistics as global.
>
> In second chance fifo, pages removed from a local working set are
> tossed into a global Valid list to become a candidate for recycling.
> If referenced again quickly the page is pulled page into the local
> working set for almost no cost. This is essentially the same as
> the WSClock and its referenced bits.
>
> In 3rd chance, VMS allows a page to make 2 trips through the working
> set list. After the first trip a flag is set on the working set entry
> it goes to the tail of the list and the PTE's valid flag is cleared.
> If it gets touched again then the handler just enables the PTE.
> When it gets to the head of the list again the PTE is checked to
> see if it was referenced. If is was, it cycles again, otherwise
> it goes into the global Valid list. [1]

as mentioned in the previous post
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

some of the work that i had done in the 60s as an undergraduate for
cp67 ... had been dropped in the morph from cp67 to vm370. i was able
to rectify that with the resource manager released 11may1976.

the cp67 "clock" scanned pages by their real storage address.
basically the idea behind a "clock" reset and testing the reference
bit is that the time it takes to cycle completely around all virtual
pages represents approximately the same interval between the resetting
and testing for all pages.

one of the advantages of clock type implementation that i had done in
the 60s was that it had some interesting dynamic adaptive stuff. if
there weren't enuf pages, the replacement algorithm would be called
more frequently ... causing it to cycle through more pages faster. as
it did the cycle quicker ... there was shortened time between the time
a page had its reference reset and then tested again. with the
shortened cycle time, there tended to be more pages that hadn't a
chance to be used and therefor have their reference bit turned on
again. as a result, each time the selection was called on a page
fault, fewer pages had to be examined before finding one w/o its
reference set. if the avg. number of pages examined per page fault
was reduced ... then it increased the total time to cycle through
all pages (allowing more pages to have a chance to be used and
have their reference bit set).

part of the vm370 morph was that it change the page scanning from real
storage address (which basically distributed virtual pages fairly
randomly) to a link list. one of the side-effects of the link list
management was that it drastically disturbed the basic premise under
which clock operated. with the virtual pages position in the list
constantly being perturbed ... it was no longer possible to assert
that the time between a page had its reference reset and not taken and
the time it was examined again ... was in anyway related to the
avg. time it took clock to cycle through all pages.

basically a single reference bit represented some amount of activity
history related to the use of that specific page. in clock the
avg. amount of activity history that a reference bit represents is the
interval between the time the bit was reset and the time it was
examined again. on the avg. that is the interval that it takes clock
to cycle through all pages ... and is approximately the same for all
pages. if pages were being constantly re-ordered on the list (that is
being used by clock to examine pages) ... there is much less assurance
that the inverval between times that a specific page was examined in
any way relates to the avg. elapsed time it takes clock to make one
complete cycle through all pages. this perturbs and biases how pages
are selected in ways totally unrelated to the overall system avg. of
the interval between one reset/examination and the next ... basically
violating any claim as to approximating a least recently used
replacement strategy.

because of the constant list re-order in the initial vm370
implementation ... it was no longer possible to claim that it actually
approached a real approximation of a least recently used replacement
strategy. on the "micro" level ... they claimed that the code made
complete cycles through the list ... just like the implementation that
cycled through real storage. however, at the "macro" level, they
didn't see that the constant list re-ordering invalidated basic
assumptions about approximating least recently used replacement
strategy.

the other thing that the initial morph to vm370 was that "shared"
virtual memory pages were not included in the standard list for
selection ... so they were subject to the same examine/reset/examine
replacement cycle as non-shared pages. this was downplayed by saying
that it only amounted to, at most, 16 shared pages.

well a couple releases came and went ... and they then decided
to release a small subset of my memory mapping stuff as
something called discontiguous shared segments. recent post
on the subject in this thread
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

basically the support in vm370 for having more than single shared
segment ... and some number of my changes to cms code to make it r/o
(i.e. be able to operate in a r/o protected shared segment)
... various collected posts
http://www.garlic.com/~lynn/subtopic.html#mmap
http://www.garlic.com/~lynn/subtopic.html#adcon

in any case, this drastically increased the possible amount of shared
virtual pages ... that were being treated specially by the list-based
replacement algorithm ... and not subject to the same least recently
used replacement strategies and normal virtual pages ... some shared
virtual page at any specific moment might only be relatively lightly
used by a single virtual address space ... even tho it appeared in
multiple different virtual address spaces; aka its "sharing"
characteristic might have little to do with its "used" characteristic
(but the "sharing" characteristic was somewhat being used in place of
its actual "use" characteristic for determing replacement selection).

however, i was able to rectify that when they allowed me to ship
resource manager several months later on 11may76 ... and put the
replacement strategy back to the way I had implemented it for
cp67 as an undergraduate in the 60s.
http://www.garlic.com/~lynn/subtopic.html#fairshare
http://www.garlic.com/~lynn/subtopic.html#wsclock

so i had a similar but different argument with the group doing os/vs2
... the morph of real-memory os/360 mvt with support for virtual
memory. recent post in this thread about other aspects of that
effort
http://www.garlic.com/~lynn/2006i.html#33 virtual memory

they were also claiming that they were doing a least recently used
replacement stragegy. however, their performance group did some simple
modeling and found that if they choose non-changed least recently used
pages ... before choosing changed least recently used pages ... that
the service time to handle the replacement was drastically reduced. a
non-changed page already had an exact duplicate out on disk ... and
therefor replacement processing could simply discard the copy in
virtual memory and make the real memory location available. a
"changed" page selected for replacement, first had to be written to
disk before the real memory location was available. first attempting
to select non-changed pages for replacement significantly reduced the
service time and processing. I argued that such approach basically
perturbed and violated any claim as to approximating least recently
used replacement strategy. they did it any way.

so os/vs2 svs eventually morphed into os/vs2 mvs ... and then they
shortened the name to just calling it mvs. customers had been using it
for some number of years ... it was coming up in 1980 ... and somebody
discovered that high-useage, shared executable images (i.e. same
executable image appearing in lots of different virtual address spaces
and being executed by lots of different applications) were being
selected for replacement before low-useage application data pages. The
high-useage, shared executable images were "read-only" ... aka they
were never modified and/or changed. The low-useage application data
areas were constantly being changed. As a result, the high-useage
(execution, shared) pages were being selected for replacement before
low-useage application data pages.

in much the same way that the vm370 page list management was
constantly and significantly changing the order that pages were
examined for replacement ... invalidating basic premise of least
recently used replacement stragegies ... the os/vs2 (svs and mvs) was
also creating an ordering different than based on purely use ... also
invalidating basic premise of least recently used replacement
strategies.

some past posts mentiong the os/vs2 early forey into least
recently used replacement strategy:
http://www.garlic.com/~lynn/94.html#4 Schedulers
http://www.garlic.com/~lynn/94.html#49 Rethinking Virtual Memory
http://www.garlic.com/~lynn/2000c.html#35 What level of computer is needed for a computer to Love?
http://www.garlic.com/~lynn/2001b.html#61 Disks size growing while disk count shrinking = bad performance
http://www.garlic.com/~lynn/2002.html#6 index searching
http://www.garlic.com/~lynn/2002c.html#52 Swapper was Re: History of Login Names
http://www.garlic.com/~lynn/2003b.html#44 filesystem structure, was tape format (long post)
http://www.garlic.com/~lynn/2004.html#13 Holee shit! 30 years ago!
http://www.garlic.com/~lynn/2004o.html#57 Integer types for 128-bit addressing
http://www.garlic.com/~lynn/2005f.html#47 Moving assembler programs above the line
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/2006b.html#15 {SPAM?} Re: Expanded Storage

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

[j***@aol.com]

In article <***@lhwlinux.garlic.com>,
Anne & Lynn Wheeler <***@garlic.com> wrote:
<snip>

>they were also claiming that they were doing a least recently used
>replacement stragegy. however, their performance group did some simple
>modeling and found that if they choose non-changed least recently used
>pages ... before choosing changed least recently used pages ... that
>the service time to handle the replacement was drastically reduced. a
>non-changed page already had an exact duplicate out on disk ... and
>therefor replacement processing could simply discard the copy in
>virtual memory and make the real memory location available.

Right. All you had to was zero the word, or half word, or bit,
that pointed at the index of the page table.

But, now you have the decision of when does the data within
that page get zeroed when it is placed into the next
address space usage list. I don't think it matters as
long as they're all done on the same side of usage.



>a
>"changed" page selected for replacement, first had to be written to
>disk before the real memory location was available. first attempting
>to select non-changed pages for replacement significantly reduced the
>service time and processing. I argued that such approach basically
>perturbed and violated any claim as to approximating least recently
>used replacement strategy. they did it any way.
>
>so os/vs2 svs eventually morphed into os/vs2 mvs ... and then they
>shortened the name to just calling it mvs. customers had been using it
>for some number of years ... it was coming up in 1980 ... and somebody
>discovered that high-useage, shared executable images (i.e. same
>executable image appearing in lots of different virtual address spaces
>and being executed by lots of different applications) were being
>selected for replacement before low-useage application data pages. The
>high-useage, shared executable images were "read-only" ... aka they
>were never modified and/or changed. The low-useage application data
>areas were constantly being changed. As a result, the high-useage
>(execution, shared) pages were being selected for replacement before
>low-useage application data pages.

They didn't keep a count of how many were sharing the code? This
means that user data pages had the same priority as code? One
would assume that all user data pages would have be written out.
>
>in much the same way that the vm370 page list management was
>constantly and significantly changing the order that pages were
>examined for replacement ... invalidating basic premise of least
>recently used replacement stragegies ... the os/vs2 (svs and mvs) was
>also creating an ordering different than based on purely use ... also
>invalidating basic premise of least recently used replacement
>strategies.

Was there a difference between exec pages and user pages?
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.

/BAH

[Anne & Lynn Wheeler]

***@aol.com 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/

[j***@aol.com]

In article <***@lhwlinux.garlic.com>,
Anne & Lynn Wheeler <***@garlic.com> wrote:
>***@aol.com writes:

<snip implementation descriptions reluctantly>

Just for clarification: I don't think I ever knew
how TOPS-10 did the stuff at this level. I do
remember discussions about it all but I understood 0%
of what the guys talked about. I no longer can
recall what was said, let alone the order.

ISTM that DECUS had some sessions about all this stuff.
Is any of those session writeups available?


/BAH

[Brian Inglis]

On Sat, 13 May 2006 10:01:52 -0400 in alt.folklore.computers, "Eric
P." <***@sympaticoREMOVE.ca> wrote:

>Anne & Lynn Wheeler wrote:
>>
>> Bill Todd <***@metrocast.net> writes:
>> > I took a quick look and saw nothing specific, so you'll need to
>> > provide a pointer or two.
>>
>> ref:
>> http://www.garlic.com/~lynn/2006i.html#31 virtual memory
>>
>> I posted it numerous times before ... so there were URLs to
>> where it had been repeatedly posted before
>>
>> basically i had done local LRU. cambridge had 768kbyte 360/67,
>> 104 "pageable pages" after fixed kernel requirements running
>> cp67.
>>
>> grenoble modified they same cp67 for "working set" dispatcher and
>> local LRU running on 1mbyte 360/67, 154 "pageable pages" after fixed
>> kernel requirements (basically 50 percent more real storage for
>> application paging). they published a paper on the work in the early
>> 70s in cacm
>
>After our previous discussions, I looked high and low for any details
>on the grenoble system, and fifo or local working sets on cp67.
>Unfortunately I found nothing.
>
>My suspicion is that Grenoble used strict fifo local working sets.
>These are now known (possibly as a result of that very project)
>to not perform well.

Strict FIFO only tracks page add, nothing to do with reference/use, so
why would anyone in their right mind think that would be a sane basis
for LRU approximation, or was an LRU approach unknown at that time?

>VMS and WNT use Second Chance Fifo, which has very different behavior
>to strict Fifo, and is reputed to have the same behavior as WSClock.
>VMS also has an option for a third chance - I don't know if WNT
>also has that. This gives them all the control advantages that
>local working sets allow with the same paging statistics as global.
>
>In second chance fifo, pages removed from a local working set are
>tossed into a global Valid list to become a candidate for recycling.
>If referenced again quickly the page is pulled page into the local
>working set for almost no cost. This is essentially the same as
>the WSClock and its referenced bits.

The drop/reclaim approach was used with clock in VM/CP.

>In 3rd chance, VMS allows a page to make 2 trips through the working
>set list. After the first trip a flag is set on the working set entry
>it goes to the tail of the list and the PTE's valid flag is cleared.
>If it gets touched again then the handler just enables the PTE.
>When it gets to the head of the list again the PTE is checked to
>see if it was referenced. If is was, it cycles again, otherwise
>it goes into the global Valid list. [1]
>
>The working set size is not fixed but can vary if memory is available.
>If a process pages too much the size is increased until it stops. [2}
>
>The combination of all these features makes the VMS/WNT local
>working sets completely different from the early strict fifo models.
>
>[1] My informal experiments on VMS found that enabling the 3rd
>chance mechanism had no effect on performance. The 2nd chance
>mechanism appears to be quite sufficient.
>
>[2] A valid criticism of VMS, and possibly WNT, is they use boot time
>sized arrays to track the working set entries rather than linked lists.
>Because of this there is an absolute maximum working set size and
>processes which reach that maximum will page fault even when there is
>gobs of free memory on a system. However that is a deficiency in a
>particular implementation and not due to the local working sets.

Linked list overhead became too high as memory sizes jumped.
VM/CP used core table to track page frames instead of per process
pages, so had the advantage of a fixed size array, without the
disadvantage of a fixed maximum process size.
Used the process page table to map from page to frame.

>There is no technical reason for these to not allow process working
>sets to be arbitrarily large, up to all of virtual space is memory
>is available, and use dynamic software controls to limit their size.

--
Thanks. Take care, Brian Inglis Calgary, Alberta, Canada

***@CSi.com (Brian[dot]Inglis{at}SystematicSW[dot]ab[dot]ca)
fake address use address above to reply

[David Scheidt]

In alt.folklore.computers Brian Inglis <***@systematicsw.invalid> wrote:
:On Sat, 13 May 2006 10:01:52 -0400 in alt.folklore.computers, "Eric
:P." <***@sympaticoREMOVE.ca> wrote:

:>Anne & Lynn Wheeler wrote:
:>>
:>> Bill Todd <***@metrocast.net> writes:
:>> > I took a quick look and saw nothing specific, so you'll need to
:>> > provide a pointer or two.
:>>
:>> ref:
:>> http://www.garlic.com/~lynn/2006i.html#31 virtual memory
:>>
:>> I posted it numerous times before ... so there were URLs to
:>> where it had been repeatedly posted before
:>>
:>> basically i had done local LRU. cambridge had 768kbyte 360/67,
:>> 104 "pageable pages" after fixed kernel requirements running
:>> cp67.
:>>
:>> grenoble modified they same cp67 for "working set" dispatcher and
:>> local LRU running on 1mbyte 360/67, 154 "pageable pages" after fixed
:>> kernel requirements (basically 50 percent more real storage for
:>> application paging). they published a paper on the work in the early
:>> 70s in cacm
:>
:>After our previous discussions, I looked high and low for any details
:>on the grenoble system, and fifo or local working sets on cp67.
:>Unfortunately I found nothing.
:>
:>My suspicion is that Grenoble used strict fifo local working sets.
:>These are now known (possibly as a result of that very project)
:>to not perform well.

:Strict FIFO only tracks page add, nothing to do with reference/use, so
:why would anyone in their right mind think that would be a sane basis
:for LRU approximation, or was an LRU approach unknown at that time?

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.

David

[Anne & Lynn Wheeler]

David Scheidt <***@panix.com> 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

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

[Anne & Lynn Wheeler]

Anne & Lynn Wheeler <***@garlic.com> 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/

[Anne & Lynn Wheeler]

Anne & Lynn Wheeler <***@garlic.com> 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 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/

[Anne & Lynn Wheeler]

David Scheidt <***@panix.com> 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/

[Brian Inglis]

On Mon, 15 May 2006 19:25:53 +0000 (UTC) in alt.folklore.computers,
David Scheidt <***@panix.com> wrote:

>In alt.folklore.computers Brian Inglis <***@systematicsw.invalid> wrote:

>:>Anne & Lynn Wheeler wrote:
>:>>
>:>> Bill Todd <***@metrocast.net> writes:

>:Strict FIFO only tracks page add, nothing to do with reference/use, so
>:why would anyone in their right mind think that would be a sane basis
>:for LRU approximation, or was an LRU approach unknown at that time?
>
>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.

The accessed bit should be in the hardware just like the mod bit. FIFO
avoids tracking anything to do with *use*, it just tracks pages in the
current working set, and you already know which those are; it tells
you nothing about which pages are currently actively used. It's
obvious that it won't work as well as any other (i.e. better) real
LR*U* approximation with reclaim.

Compare with other (disk based) hierarchical storage management
systems which migrate unused data to offline storage. They would be
useless if they didn't track access, which requires an additional disk
write, but seems to be considered acceptable overhead on most file
systems, even where migration is not done.

On one system where we used migration to alleviate a disk space
crunch, we found files unaccessed for three weeks could be migrated
with nearly zero impact; we got about one retrieval request a year for
migrated data. Using FIFO would be equivalent to using the created or
modified date as our migration criteria: there are a lot of files
which are only read after creation and migrating those would have lead
to masses of retrieval requests, requiring other files to be migrated
first, and the situation would have looked very much like thrashing;
so I'd expect systems using FIFO paging to have difficulty being able
to distinguish thrashing from SOP.

--
Thanks. Take care, Brian Inglis Calgary, Alberta, Canada

***@CSi.com (Brian[dot]Inglis{at}SystematicSW[dot]ab[dot]ca)
fake address use address above to reply

[Eric P.]

Brian Inglis wrote:
>
> On Sat, 13 May 2006 10:01:52 -0400 in alt.folklore.computers, "Eric
> P." <***@sympaticoREMOVE.ca> wrote:
>
> >My suspicion is that Grenoble used strict fifo local working sets.
> >These are now known (possibly as a result of that very project)
> >to not perform well.
>
> Strict FIFO only tracks page add, nothing to do with reference/use, so
> why would anyone in their right mind think that would be a sane basis
> for LRU approximation, or was an LRU approach unknown at that time?

Hard to tell exactly what was going on then. In Belady's "A study of
replacement algorithms for a virtual-storage computer" from 1966
(I just quickly scanned it - it is a bit of a heavy read)
he compares RAND, FIFO, OPT and something called MIN which sounds
very similar to working sets. He mentions ATLAS, and talks about how
reference and modify bits can be helpful, but no mention of LRU.
Denning's working set paper was in 1968.

So fifo was obviously on peoples minds, but Lynn says he was
doing LRU around this time so it was probably gathering steam.

> >[2] A valid criticism of VMS, and possibly WNT, is they use boot time
> >sized arrays to track the working set entries rather than linked lists.
> >Because of this there is an absolute maximum working set size and
> >processes which reach that maximum will page fault even when there is
> >gobs of free memory on a system. However that is a deficiency in a
> >particular implementation and not due to the local working sets.
>
> Linked list overhead became too high as memory sizes jumped.
> VM/CP used core table to track page frames instead of per process
> pages, so had the advantage of a fixed size array, without the
> disadvantage of a fixed maximum process size.
> Used the process page table to map from page to frame.

I don't see why linked list overhead would be significantly different.

VMS uses a circular buffer with tail (add) and head (remove) indexes.
Dirt cheap but if the tail meets the head, the list is full.

A slightly more sophisticated mechanism would have a linked list of
page-sized working set "buckets", with each bucket containing fields
for the list link, some house keeping fields, and a vector of working
set entries. Basically a linked list of small arrays. It is no more
expensive than the circular buffer, but has no intrinsic size limit.
The vast majority of processes would only use one or two buckets.

As for global, it needs to maintain a linked list of reverse pointers
to all the PTE's that reference each frame so that it can remove
the frame from all address spaces and recycle with a minimum of work.
Without reverse pointers, it requires scanning all process page
tables (yeech - try that in a 48 bit address space).

So these list overheads appear equivalent.

Eric

[Brian Inglis]

On Tue, 16 May 2006 14:14:46 -0400 in alt.folklore.computers, "Eric
P." <***@sympaticoREMOVE.ca> wrote:

>Brian Inglis wrote:
>>
>> On Sat, 13 May 2006 10:01:52 -0400 in alt.folklore.computers, "Eric
>> P." <***@sympaticoREMOVE.ca> wrote:
>>
>> >My suspicion is that Grenoble used strict fifo local working sets.
>> >These are now known (possibly as a result of that very project)
>> >to not perform well.
>>
>> Strict FIFO only tracks page add, nothing to do with reference/use, so
>> why would anyone in their right mind think that would be a sane basis
>> for LRU approximation, or was an LRU approach unknown at that time?
>
>Hard to tell exactly what was going on then. In Belady's "A study of
>replacement algorithms for a virtual-storage computer" from 1966
>(I just quickly scanned it - it is a bit of a heavy read)
>he compares RAND, FIFO, OPT and something called MIN which sounds
>very similar to working sets. He mentions ATLAS, and talks about how
>reference and modify bits can be helpful, but no mention of LRU.
>Denning's working set paper was in 1968.
>
>So fifo was obviously on peoples minds, but Lynn says he was
>doing LRU around this time so it was probably gathering steam.
>
>> >[2] A valid criticism of VMS, and possibly WNT, is they use boot time
>> >sized arrays to track the working set entries rather than linked lists.
>> >Because of this there is an absolute maximum working set size and
>> >processes which reach that maximum will page fault even when there is
>> >gobs of free memory on a system. However that is a deficiency in a
>> >particular implementation and not due to the local working sets.
>>
>> Linked list overhead became too high as memory sizes jumped.
>> VM/CP used core table to track page frames instead of per process
>> pages, so had the advantage of a fixed size array, without the
>> disadvantage of a fixed maximum process size.
>> Used the process page table to map from page to frame.
>
>I don't see why linked list overhead would be significantly different.
>
>VMS uses a circular buffer with tail (add) and head (remove) indexes.
>Dirt cheap but if the tail meets the head, the list is full.
>
>A slightly more sophisticated mechanism would have a linked list of
>page-sized working set "buckets", with each bucket containing fields
>for the list link, some house keeping fields, and a vector of working
>set entries. Basically a linked list of small arrays. It is no more
>expensive than the circular buffer, but has no intrinsic size limit.
>The vast majority of processes would only use one or two buckets.
>
>As for global, it needs to maintain a linked list of reverse pointers
>to all the PTE's that reference each frame so that it can remove
>the frame from all address spaces and recycle with a minimum of work.
>Without reverse pointers, it requires scanning all process page
>tables (yeech - try that in a 48 bit address space).
>
>So these list overheads appear equivalent.

Shared segments (portions of address spaces) were handled separately
(as the shared segments needed a common storage protection key/virtual
PID to allow multiple virtual machines access) in lists of pages, with
a list of pointers to the virtual machines using them, so the virtual
machine shared pages could be quickly accessed via the page tables
(similar to a TLB lookup) and flipped when a frame was dropped.

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").

--
Thanks. Take care, Brian Inglis Calgary, Alberta, Canada

***@CSi.com (Brian[dot]Inglis{at}SystematicSW[dot]ab[dot]ca)
fake address use address above to reply

[Anne & Lynn Wheeler]

Brian Inglis <***@SystematicSW.Invalid> 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):

From: zzzzz
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 ...

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://www.garlic.com/~lynn/2000.html#68 Mainframe operating systems
http://www.garlic.com/~lynn/2000c.html#34 What level of computer is needed for a computer to Love?
http://www.garlic.com/~lynn/2001b.html#18 Linux IA-64 interrupts [was Re: Itanium benchmarks ...]
http://www.garlic.com/~lynn/2001i.html#37 IBM OS Timeline?
http://www.garlic.com/~lynn/2001i.html#38 IBM OS Timeline?
http://www.garlic.com/~lynn/2001l.html#36 History
http://www.garlic.com/~lynn/2002c.html#39 VAX, M68K complex instructions (was Re: Did Intel Bite Off More Than It Can Chew?)
http://www.garlic.com/~lynn/2002g.html#61 GE 625/635 Reference + Smart Hardware
http://www.garlic.com/~lynn/2002j.html#70 hone acronym (cross post)
http://www.garlic.com/~lynn/2002l.html#65 The problem with installable operating systems
http://www.garlic.com/~lynn/2002l.html#67 The problem with installable operating systems
http://www.garlic.com/~lynn/2002n.html#62 PLX
http://www.garlic.com/~lynn/2003b.html#0 Disk drives as commodities. Was Re: Yamhill
http://www.garlic.com/~lynn/2003g.html#13 Page Table - per OS/Process
http://www.garlic.com/~lynn/2003k.html#27 Microkernels are not "all or nothing". Re: Multics Concepts For
http://www.garlic.com/~lynn/2004.html#18 virtual-machine theory
http://www.garlic.com/~lynn/2004c.html#59 real multi-tasking, multi-programming
http://www.garlic.com/~lynn/2004d.html#0 IBM 360 memory
http://www.garlic.com/~lynn/2004g.html#50 Chained I/O's
http://www.garlic.com/~lynn/2004m.html#16 computer industry scenairo before the invention of the PC?
http://www.garlic.com/~lynn/2004n.html#26 PCIe as a chip-to-chip interconnect
http://www.garlic.com/~lynn/2004n.html#54 CKD Disks?
http://www.garlic.com/~lynn/2004o.html#57 Integer types for 128-bit addressing
http://www.garlic.com/~lynn/2005b.html#23 360 DIAGNOSE
http://www.garlic.com/~lynn/2005b.html#49 The mid-seventies SHARE survey
http://www.garlic.com/~lynn/2005b.html#50 [Lit.] Buffer overruns
http://www.garlic.com/~lynn/2005f.html#45 Moving assembler programs above the line
http://www.garlic.com/~lynn/2005f.html#47 Moving assembler programs above the line
http://www.garlic.com/~lynn/2005p.html#18 address space
http://www.garlic.com/~lynn/2005q.html#41 Instruction Set Enhancement Idea
http://www.garlic.com/~lynn/2005s.html#25 MVCIN instruction
http://www.garlic.com/~lynn/2005t.html#7 2nd level install - duplicate volsers
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
http://www.garlic.com/~lynn/2006j.html#5 virtual memory

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

[Eugene Miya]

"Memory is like an orgasm - it's better when you don't have to fake it."
"You can't fake what you don't have".
"In this business, you can't fake what you don't have"

"If you were plowing a field, which would you rather use? Two strong
oxen or 1024 chickens?"
-- Seymour Cray

Scene: 1979 Cray Research, Inc. Annual Meeting
Lutherin Brotherhood Building, Minneapolis, Mn.
Q & A period, after the address by the Officers of the Company,

Q: "Mr. Cray, ... Since you seem to have implemented almost
all of the current schemes published in the scientific press
on improving performance in your systems, I was wondering
why you didn't also provide for virtual memeory?"

A: From Mr. Cray: "Well as you know, over the years I have
provided the largest physical memories available for use.
The addition of a "virtual memory" scheme would have
added another level of hardware and hardware addressing
delays in accessing code and data.
I believe that it's better to spend the resource providing for
a larger overall memory system for the programmer. ...
Historically, this is what the programmers have preferred."

--

[Anne & Lynn Wheeler]

Anne & Lynn Wheeler <***@garlic.com> writes:
> 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.

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

"811" (named after 11/78 publication date on the architecture
documents) or 3081 was considered somewhat of a 155/158 follow-on
machine ... being much more of a m'coded machine.

"TROUT" or 3090 was considered somewhat of a 165/168 follow-on machine
... being much more of a hardwired machine.

these were the days of processors getting bigger and bigger with much
more effort being put into more processors in SMP configuration.

they had created two positions, one in charge of "tightly-coupled"
architecuture (SMP) and one in charge of "loosely-coupled"
architecture (clusters). my wife got con'ed into taking the job in pok
in charge of loosed-coupled architecture.

she didn't last long ... while there, she did do done peer-coupled
shared data architecture
http://www.garlic.com/~lynn/subtopic.html#shareddata

which didn't see much uptake until sysplex ... except for the ims
group doing ims hot-standby.

part of the problem was she was fighting frequently with the
communication's group, who wanted SNA/VTAM to be in charge of any
signals leaving a processor complex (even those directly to another
processor).

one example was trouter/3088 ... she fought hard for hardware
enhancements for full-duplex operation. there had been a previous
"channel-to-channel" hardware which was half-duplex direct channel/bus
communication between two processor complexes. 3088 enhanced this to
provide connectivity to up to eight different processor complexes.

sna was essentially a dumb terminal controller infrastructure. their
reference to it as a "network" required other people in the
organization to migrate to using the term "peer-to-peer network" to
differentiate from the sna variety.

of course, earlier, in the time-frame that sna was just starting out
... she had also co-authored a peer-to-peer networking architecture
with Burt Moldow ... which was somewhat viewed as threatening to sna
... misc. past posts mentioning awp39:
http://www.garlic.com/~lynn/2004n.html#38 RS/6000 in Sysplex Environment
http://www.garlic.com/~lynn/2004p.html#31 IBM 3705 and UC.5
http://www.garlic.com/~lynn/2005p.html#8 EBCDIC to 6-bit and back
http://www.garlic.com/~lynn/2005p.html#15 DUMP Datasets and SMS
http://www.garlic.com/~lynn/2005p.html#17 DUMP Datasets and SMS
http://www.garlic.com/~lynn/2005q.html#27 What ever happened to Tandem and NonStop OS ?
http://www.garlic.com/~lynn/2005u.html#23 Channel Distances
http://www.garlic.com/~lynn/2006h.html#52 Need Help defining an AS400 with an IP address to the mainframe

anyway, in the trotter/3088 time-frame ... san jose had done a
prototype vm/cluster implementation using a modified trotter/3088 with
full-duplex protocols. however, before it was allowed to ship, they
had to convert it to san operation. one of the cluster example was to
fully "resynch" cluster operation of all the processors ... with took
under a second using full-duplex protocols on the 3088 ... but the
same operation took on the order of a minute using sna protocols
and a half-duplex paradigm.

we ran afoul again later with 3-tier architecture
http://www.garlic.com/~lynn/subtopic.html#3tier

this was in the time-frame that the communications group was
out pushing SAA ... a lot of which was an attempt to revert back
to terminal emulation paradigm
http://www.garlic.com/~lynn/subnetwork.html#emulation

from that of client/server. we had come up with 3-tier architecture
and was out pitching it to customer executives ... and the same time
they were trying to revert 2-tier architecture back to dumb terminal
emulation.

then we did ha/cmp product
http://www.garlic.com/~lynn/subtopic.html#hacmp

minor reference
http://www.garlic.com/~lynn/95.html#13

which didn't make a lot of them happy either.

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

[j***@aol.com]

In article <***@sympaticoREMOVE.ca>,
"Eric P." <***@sympaticoREMOVE.ca> wrote:
>Brian Inglis wrote:
>>
>> On Sat, 13 May 2006 10:01:52 -0400 in alt.folklore.computers, "Eric
>> P." <***@sympaticoREMOVE.ca> wrote:
>>
>> >My suspicion is that Grenoble used strict fifo local working sets.
>> >These are now known (possibly as a result of that very project)
>> >to not perform well.
>>
>> Strict FIFO only tracks page add, nothing to do with reference/use, so
>> why would anyone in their right mind think that would be a sane basis
>> for LRU approximation, or was an LRU approach unknown at that time?
>
>Hard to tell exactly what was going on then. In Belady's "A study of
>replacement algorithms for a virtual-storage computer" from 1966
>(I just quickly scanned it - it is a bit of a heavy read)
>he compares RAND, FIFO, OPT and something called MIN which sounds
>very similar to working sets. He mentions ATLAS, and talks about how
>reference and modify bits can be helpful, but no mention of LRU.
>Denning's working set paper was in 1968.
>
>So fifo was obviously on peoples minds, but Lynn says he was
>doing LRU around this time so it was probably gathering steam.
>
>> >[2] A valid criticism of VMS, and possibly WNT, is they use boot time
>> >sized arrays to track the working set entries rather than linked lists.
>> >Because of this there is an absolute maximum working set size and
>> >processes which reach that maximum will page fault even when there is
>> >gobs of free memory on a system. However that is a deficiency in a
>> >particular implementation and not due to the local working sets.
>>
>> Linked list overhead became too high as memory sizes jumped.
>> VM/CP used core table to track page frames instead of per process
>> pages, so had the advantage of a fixed size array, without the
>> disadvantage of a fixed maximum process size.
>> Used the process page table to map from page to frame.
>
>I don't see why linked list overhead would be significantly different.

Consider the case where you have to page in part of your linked list.

You get the "pink scheduling" of shuffling memory management all
over again.
>
>VMS uses a circular buffer with tail (add) and head (remove) indexes.
>Dirt cheap but if the tail meets the head, the list is full.

That's definitely a task-orienting thinking style. You have
x resources so you use x and if you need more, stop. Nothing
is dynamic; computer services are not provided on a demand
basis.

>
>A slightly more sophisticated mechanism would have a linked list of
>page-sized working set "buckets", with each bucket containing fields
>for the list link, some house keeping fields, and a vector of working
>set entries. Basically a linked list of small arrays. It is no more
>expensive than the circular buffer, but has no intrinsic size limit.
>The vast majority of processes would only use one or two buckets.
>
>As for global, it needs to maintain a linked list of reverse pointers
>to all the PTE's that reference each frame so that it can remove
>the frame from all address spaces and recycle with a minimum of work.
>Without reverse pointers, it requires scanning all process page
>tables (yeech - try that in a 48 bit address space).

Which process tables? The user's or the exec's?


>
>So these list overheads appear equivalent.

The devil is in the details :-).

Now, an apology is due. It appears that I'm confused. Thus,
I apologize for wasting all for you people's time.

/BAH

[Eric P.]

***@aol.com wrote:
>
> In article <***@sympaticoREMOVE.ca>,
> "Eric P." <***@sympaticoREMOVE.ca> wrote:
> >
> >I don't see why linked list overhead would be significantly different.
>
> Consider the case where you have to page in part of your linked list.
>
> You get the "pink scheduling" of shuffling memory management all
> over again.

I had to look up the term. "pink scheduling" = OS thrashing loop
that caused a mode light on the PDP-10 console to glow pink.

Yes, so you just don't make those OS data structures pagable,
in the sense that they never page fault when touched.
But resources can still dynamically grow and shrink by explicitly
managing how the virtual pages map to physical frames, rather
than using the paging mechanism.

> >As for global, it needs to maintain a linked list of reverse pointers
> >to all the PTE's that reference each frame so that it can remove
> >the frame from all address spaces and recycle with a minimum of work.
> >Without reverse pointers, it requires scanning all process page
> >tables (yeech - try that in a 48 bit address space).
>
> Which process tables? The user's or the exec's?

I'm not quite sure what you are asking.

Any page table entry that references the frame number which
is about to be reassigned has to be invalidated.
Since a page may be shared between many processes, that can
involve tracking down and zapping PTE's in multiple page tables.

On many systems only user space is pagable. However if
parts of the kernel are also pagable, then there too.
VMS and WNT allow some parts of their kernel to page.

> >
> >So these list overheads appear equivalent.
>
> The devil is in the details :-).
>
> Now, an apology is due. It appears that I'm confused. Thus,
> I apologize for wasting all for you people's time.

Not as far as I am concerend.

Eric

[Anne & Lynn Wheeler]

"Eric P." <***@sympaticoREMOVE.ca> writes:
> I had to look up the term. "pink scheduling" = OS thrashing loop
> that caused a mode light on the PDP-10 console to glow pink.
>
> Yes, so you just don't make those OS data structures pagable,
> in the sense that they never page fault when touched.
> But resources can still dynamically grow and shrink by explicitly
> managing how the virtual pages map to physical frames, rather
> than using the paging mechanism.

what i did in vm370 ... was i created a separate psuedo address space
for each virtual machine to allow the page I/O infastructure to move
such data structures to/from the paging area. there was some amount of
dynamic adaptive stuff that precluded getting into pathelogical
behavior moving the stuff in/out.

administrative code had explicit checking to see whether the objects
were present ... as opposed to the kernel taking a page fault. part
of this was based on the LRA (load-real address) instruction ... where
the instruction set a condition code based on whether the page &/or
tables were actually present.

at least one of the vm370-based time-sharing service bureaus
http://www.garlic.com/~lynn/subtopic.html#timeshare

enhanced that support to support process migration in a
loosely-coupled environment ... i.e. a collection of independent
processor complexes (non-shared memory) that all had access to the
same physical disks (a process and all its support data structures
could be paged out from one processor complex to disk ... and then
paged into a different processor complex.

this was useful for some of these operations that had gone 7x24 with
customers world-wide ... and the processor complexes had to be taken
down periodically for standard hardware maintenance purposes.

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

[Anne & Lynn Wheeler]

"Eric P." <***@sympaticoREMOVE.ca> writes:
> Any page table entry that references the frame number which is about
> to be reassigned has to be invalidated. Since a page may be shared
> between many processes, that can involve tracking down and zapping
> PTE's in multiple page tables.

cp67 use to support a limited number of shared pages in this
manner. however, in the morph from cp67->vm370 ... the 370 offerred a
"64kbyte" segment option (16 4k pages) in the two level table
structures.

a virtual address space was represented by a "segment" table. segment
table entries pointed to page tables. page tables had PTE entries that
indicated real address. segment table entries in different segment
tables (i.e. virtual address spaces) could point at the same page
table. such a page table (associated with a specific segment or range
of virtual addresses) could then be "shared" accross multiple
different address spaces. however, real, shared pages would only have
a single, unique PTE in a single page table ... even tho multiple
different segment tables could point at the same shared page.

as previous mentioned, the original 370 architecture allowed for
read-only shared segment protection. basically a spare bit was defined
in the segment table entry (which included pointer to a potentially
shared page table entry) that precluded instructions executing in that
virtual address space from storing/altering locations in that address
range. this allowed for storage protection property to be virtual
address space specific for the same shared pages i.e. a shared page
table is "store" protected for virtual address spaces with the segment
protect bit set in their segment table entry ... however the same
shared page table may not be "store" protect for virtual address
spaces w/o the segment protect bit set.

in the morph from cp67 to vm370, cms was reorganized to take advantage
of the 370 shared segment architecture and the segment protection
(allowing different address spaces to share the same information but
preventing one cms from affecting other cms'es).

as previously mentioned, when the retrofit of virtual memory hardware
to 370/165 fell behind schedule, the segment protect feature was
dropped from the architecture (as well as some number of other
features in the original 370 virtual memory architecture). this
forced vm370/cms to revert to the storage protection mechanism
that had been used in cp67.
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
http://www.garlic.com/~lynn/2006j.html#5 virtual memory


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

[j***@aol.com]

In article <***@sympaticoREMOVE.ca>,
"Eric P." <***@sympaticoREMOVE.ca> wrote:
>***@aol.com wrote:
>>
>> In article <***@sympaticoREMOVE.ca>,
>> "Eric P." <***@sympaticoREMOVE.ca> wrote:
>> >
>> >I don't see why linked list overhead would be significantly different.
>>
>> Consider the case where you have to page in part of your linked list.
>>
>> You get the "pink scheduling" of shuffling memory management all
>> over again.
>
>I had to look up the term. "pink scheduling" = OS thrashing loop
>that caused a mode light on the PDP-10 console to glow pink.

Sorry. It was better that you looked it up for the precise
description; I don't write well. :-) I saw a lot of pink
on the PDP-10 I met first.

>
>Yes, so you just don't make those OS data structures pagable,
>in the sense that they never page fault when touched.
>But resources can still dynamically grow and shrink by explicitly
>managing how the virtual pages map to physical frames, rather
>than using the paging mechanism.

Sure they're dynamic. An OS has to be able to cope without
insisting that it has unreasonable constraints at boot time.
It's like trying to fit a 2" square peg in a 1 mm round hole.

>
>> >As for global, it needs to maintain a linked list of reverse pointers
>> >to all the PTE's that reference each frame so that it can remove
>> >the frame from all address spaces and recycle with a minimum of work.
>> >Without reverse pointers, it requires scanning all process page
>> >tables (yeech - try that in a 48 bit address space).
>>
>> Which process tables? The user's or the exec's?
>
>I'm not quite sure what you are asking.

I'm speaking pure TOPS-10ese because I don't know the biz these
days. Note that an OS also has to do its memory management.
It has to have a page table for itself. Each user (or process)
also needs to have a page table assigned to it.

For more info about these you might try looking at the back
of our cheat sheet, DECsystem-10 System Reference Card
The one I have here in front of my nose includes the KI10.
Order No. DEC-10-XSRCA-B-D. It has a description of the
formats of the User Process Table (UPT) and the Exec
Process Table (EPT) as it was shipped at that time (1974).
That may give you an idea about how DEC did its first
implementation.

I don't know where I can point you for the KL equivalent
of that document. Thei system reference card has more
knowledge in it, explicit and implicit, than you'ld find
in a library dedicated to computering.

>
>Any page table entry that references the frame number which
>is about to be reassigned has to be invalidated.
>Since a page may be shared between many processes, that can
>involve tracking down and zapping PTE's in multiple page tables.

Not if this "data" is designed correctly. The goal is to do
one mark and have the results cascaded through all "users" of that
page. You cannot, as an OS, know who is _going to_ use that
reference; especially in this age of network and on-demand coding.
>
>On many systems only user space is pagable.

HUH? If your hardware architecture is page-based, everything is
pagable. It is the job of the OS how...[emoticon grasps for word]
elastic the determinations of what goes in and out are.

>However if
>parts of the kernel are also pagable, then there too.
>VMS and WNT allow some parts of their kernel to page.

I'll guarantee you those parts are the wrong parts. I may be
showing bias, but it's an experienced bias.
When an OS executes an user mode instruction, it has to do so
in behalf of the user. IOW, the OS "becomes" a user mode
program for that instance. It was not uncommon for JMF
to call TW's disk service as a "user mode" program even
though he was the exec. There are a lot of time when you
want the monitor (core-resident OS) to run as a mere user rather
than The God called Exec.

JMF was the guy who was DEC's CPU device driver wizard
and became the guy in charge of memory management. TW
was the controller and device driver and file system
guy. These were the TOPS-10 development guys.

Another term often used was the exec page table page and the
user page table page. And indirection through this page
could set any bit. So the only data maintenance one had to
for knowing about pages was making sure the page table pages'
data were pristine and always correct. Note that I'm being
extremely simplistic talking about this stuff. What I know
I learned from listening to the bit gods; I never did the
work so the knowledge isn't embedded in my bones.

One of the problems the OS has to deal with is how to manage
when the data kept in these page table pages spills over
a page boundary.
>
>> >
>> >So these list overheads appear equivalent.
>>
>> The devil is in the details :-).
>>
>> Now, an apology is due. It appears that I'm confused. Thus,
>> I apologize for wasting all for you people's time.
>
>Not as far as I am concerend.

Thank you for being kind :-). I had noticed that That Other
Newsgroup was listed. I try to keep my bits out of there. :-)

/BAH

[Brian Boutel]

Brian Inglis wrote:

>
>
> Strict FIFO only tracks page add, nothing to do with reference/use, so
> why would anyone in their right mind think that would be a sane basis
> for LRU approximation, or was an LRU approach unknown at that time?
>
>

FIFO, like all these algorithms, tries to predict future behaviour from
the past. LRU guesses that pages that have not been used for a while
have moved out of the working set, LFU prefers pages that have not been
used very often, and FIFO thinks that the working set typically moves
through the page set, so old pages are more likely to have moved out of it.

The standard objection to FIFO is that it has the undesirable property
of being able to perform worse given more real memory. LRU and friends
have the property that if you repeat a run with more real memory, then,
at any time t, the set of pages in memory will be a superset of the
pages in memory at time t in the previous run, i.e the most important
pages are in memory, and adding more memory will not cause any of them
to be not in memory at the same point of the run.

FIFO cannot guarantee such good behaviour. It is quite easy to set up an
execution trace that demonstrates this.

--brian


--
Wellington, New Zealand

"What's life? Life's easy. A quirk of matter. Nature's way of keeping
meat fresh."

[Anne & Lynn Wheeler]

Brian Boutel <***@fake> writes:
> FIFO, like all these algorithms, tries to predict future behaviour
> from the past. LRU guesses that pages that have not been used for a
> while have moved out of the working set, LFU prefers pages that have
> not been used very often, and FIFO thinks that the working set
> typically moves through the page set, so old pages are more likely to
> have moved out of it.
>
> The standard objection to FIFO is that it has the undesirable property
> of being able to perform worse given more real memory. LRU and friends
> have the property that if you repeat a run with more real memory,
> then, at any time t, the set of pages in memory will be a superset of
> the pages in memory at time t in the previous run, i.e the most
> important pages are in memory, and adding more memory will not cause
> any of them to be not in memory at the same point of the run.
>
> FIFO cannot guarantee such good behaviour. It is quite easy to set up
> an execution trace that demonstrates this.

actually LRU replacement strategy has the property that it can
degenerate to FIFO replacement strategy ... i.e. program behavior
that cycles through memory location. An example is the apl\360
memory management within a workspace ... referenced here
http://www.garlic.com/~lynn/2006j.html#24 virtual memory

it worked ok, in small real-memory workspaces ... but porting apl\360
to cms\apl large virtual memory was disasterous. the issue is that
some number of applications can have transient execution patterns that
resumble such cyclic behavior.

the problem with LRU degenerating to FIFO is that even if the virtual
memory pages, that are being cycled, are only one larger than the
available real memory ... every virtual page in the cycle will be
faulted on every pass thru the cycle (aka the first/FIFO page in such
a cycle is also the least recently used). Say there are N available
real pages (for the cycle) and there are N+1 pages in the cycle. Page
fault for page N+1 will replace page 1 (since it is both LRU and FIFO)
... but the next page to be accessed will be page 1 ... the page just
replaced. In the N+1 scenario, this replacing the very next page that
is going to be needed will continue throughout the cycle.

global clock is a very good and efficient approximation to global LRU
replacement strategy ... including degenerating to FIFO under various
conditions. as i mentioned before
http://www.garlic.com/~lynn/2006i.html#42 virtual memory

in the early 70s, i came up with a coding slight of hand that resulted
in global clock (LRU approximation) that degenerating to RANDOM rather
than FIFO. in the N+1 case where FIFO replacement was constantly
selecting the very next page that was about to be used ... a RANDOM
page would be selected for replacement instead. This significantly
reduced the overall fault rate ... since you were constantly replacing
the very page that you were about to use.

misc. past posts on page replacement algorithms, virtual memory,
etc
http://www.garlic.com/~lynn/subtopic.html#wsclock

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

[Brian Inglis]

On Fri, 12 May 2006 19:54:39 -0400 in alt.folklore.computers, Bill
Todd <***@metrocast.net> wrote:

>Brian Inglis wrote:
>
>...
>
>>> In situations where physical memory is less constrained, the per-process
>>> working sets expand beyond their minimum values (again, preferably
>>> according to individual process needs rather than in a more static
>>> manner - in which case the result does start to approximate a global
>>> page-replacement policy, just one implemented in two tiers rather than
>>> directly).
>>
>> See Lynn Wheeler's references downthread to CP/67 global vs local LRU
>> policies and results, and Stanford Ph.D. thesis on same:
>
>I took a quick look and saw nothing specific, so you'll need to provide
>a pointer or two.

Message-ID: <***@lhwlinux.garlic.com>

> local sucks,
>> global rocks!
>
>Fanboy bluster, in the absence of credible references.

Did you ever use VMS, NT, or any other OS using local LRU, and similar
configuration with OS using global LRU? Needn't be OSes, could be DBs,
file systems, any shared resource using large LRU cache where replace
policy could be local or global.

>> Local LRU (like microkernels) was considered superior by academics,
>> but global LRU (like monolithic kernels) is better on real workloads.
>
>While I happen to agree about the relative merits of microkernels, their
>applicability to the current discussion escapes me (save as a marginal
>comment on the fallibility of academics - a tribe which Cutler did not
>hold in especially high esteem and of which he was not a member).
>
>Once again, you'll have to provide substantial references for your
>personal assertion of what constitutes 'reality' to become credible.

Lynn Wheeler has posted more background in Message-ID:
<***@lhwlinux.garlic.com> and references in Message-ID:
<***@lhwlinux.garlic.com>

--
Thanks. Take care, Brian Inglis Calgary, Alberta, Canada

***@CSi.com (Brian[dot]Inglis{at}SystematicSW[dot]ab[dot]ca)
fake address use address above to reply

[Anne & Lynn Wheeler]

note this same discussion from comp.arch thread in 7aug2004
http://www.garlic.com/~lynn/2004i.html#0 Hard disk architecture: are outer cylinders still faster than inner cylinders?

a little more in that same thread
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/

[Bill Todd]

Brian Inglis wrote:
> On Fri, 12 May 2006 19:54:39 -0400 in alt.folklore.computers, Bill
> Todd <***@metrocast.net> wrote:
>
>> Brian Inglis wrote:
>>
>> ...
>>
>>>> In situations where physical memory is less constrained, the per-process
>>>> working sets expand beyond their minimum values (again, preferably
>>>> according to individual process needs rather than in a more static
>>>> manner - in which case the result does start to approximate a global
>>>> page-replacement policy, just one implemented in two tiers rather than
>>>> directly).
>>> See Lynn Wheeler's references downthread to CP/67 global vs local LRU
>>> policies and results, and Stanford Ph.D. thesis on same:
>> I took a quick look and saw nothing specific, so you'll need to provide
>> a pointer or two.
>
> Message-ID: <***@lhwlinux.garlic.com>

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.

>
>> local sucks,
>>> global rocks!
>> Fanboy bluster, in the absence of credible references.
>
> Did you ever use VMS, NT, or any other OS using local LRU, and similar
> configuration with OS using global LRU? Needn't be OSes, could be DBs,
> file systems, any shared resource using large LRU cache where replace
> policy could be local or global.

Not in a manner which stressed the systems sufficiently to give any
relative indication of their performance.

Of course, 'large' caches almost by definition are relatively
insensitive to replacement policies anyway (according to studies using
real access traces rather than academic intuition, I might add): it's
when memory starts to get tight that the policy choices start to matter.

And there are considerably more applicable analogies than to
microkernels to consider: those other situations where limiting the
degree of multiprogramming in order to avoid thrashing has proven
desirable (limits on numbers of concurrent and potentially interacting
threads in server processes, limits on promiscuous numbers of concurrent
and potentially interacting transactions in databases,
cache-segmentation to avoid pollution by large sequential access
streams, etc.). Whenever a resource is constrained, attempts to avoid
hogging and/or contending for it unnecessarily are appropriate - and
adaptive working-set approaches do exactly that by biasing process
residencies to what each process needs to execute reasonably rather than
allowing some subset of promiscuously-paging processes to bring the
entire system to a crawl.

Furthermore, batch-evicting modified pages LRU for a single process
increases the probability that batching them back in will be profitable
- which of course is an absolute win which would be at best awkward to
accomplish in a strictly global LRU approach (you'd have to evict a
large enough group of pages at once to hit processes multiple times so
that their dirty pages could be grouped, though if the mechanism were
only pseudo-LRU such that lifetimes were relatively coarse-grained that
might work).

I'd be interested in any serious studies (using real and of course
repeatable system traces) of relative page-replacement policies (rather
than random opinions and anecdotes) should you or anyone else have any
at your finger tips.

- bill

[Anne & Lynn Wheeler]

Bill Todd <***@metrocast.net> 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
<a href="2004i.html#0">http://www.garlic.com/~lynn/2004i.html#0</a> Hard disk architecture: are outer cylinders still faster than inner cylinders?
<a href="2004i.html#1">http://www.garlic.com/~lynn/2004i.html#1</a> Hard disk architecture: are outer cylinders still faster than inner cylinders?
<a href="2004i.html#8">http://www.garlic.com/~lynn/2004i.html#8</a> 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/

[Bill Todd]

Anne & Lynn Wheeler wrote:
> Bill Todd <***@metrocast.net> 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
> <a href="2004i.html#0">http://www.garlic.com/~lynn/2004i.html#0</a> Hard disk architecture: are outer cylinders still faster than inner cylinders?

The above post seems to suggest that the grenoble implementation was
indeed a "semi-static fixed partitioning of available memory [which] did
"local" LRU replacement within the partitioning", as I suggested above.

> <a href="2004i.html#1">http://www.garlic.com/~lynn/2004i.html#1</a> Hard disk architecture: are outer cylinders still faster than inner cylinders?
> <a href="2004i.html#8">http://www.garlic.com/~lynn/2004i.html#8</a> Hard disk architecture: are outer cylinders still faster than inner cylinders?

Didn't find anything helpful in those.

>
> the referenced acm article describes the grenoble implementation
> J. Rodriquez-Rosell, The design, implementation, and evaluation of a
> working set dispatcher, cacm16, apr73

As Eric noted, this paper does not appear to be generally available, and
I'm not soon going to have the time to make a trip to my local
university library to find it.

- bill

[Jan Vorbrüggen]

> Whenever a resource is constrained, attempts to avoid
> hogging and/or contending for it unnecessarily are appropriate - and
> adaptive working-set approaches do exactly that by biasing process
> residencies to what each process needs to execute reasonably rather than
> allowing some subset of promiscuously-paging processes to bring the
> entire system to a crawl.

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.

Jan

[Anne & Lynn Wheeler]

Jan Vorbrüggen <***@not-mediasec.de> 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 reading.

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

[Brian Inglis]

On Mon, 15 May 2006 15:51:40 +0200 in alt.folklore.computers, Jan
Vorbrüggen <***@not-mediasec.de> wrote:

>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.

Not sure what you mean by this.
The minimum VAX user process size was one P0 (code/data) space page
and one P1 (stack) space page, and one S0 (system) space page for each
of the two process space page tables.
Any other limitation was imposed by VMS design, which seems baroque
nowadays, with dozens of parameters to alleviate problems caused by
questionable design choices, perhaps driven by attempting to position
the system as capable of handling real-time workloads, for what would
be considered as fairly large values of real-time windows.

--
Thanks. Take care, Brian Inglis Calgary, Alberta, Canada

***@CSi.com (Brian[dot]Inglis{at}SystematicSW[dot]ab[dot]ca)
fake address use address above to reply

[Eric P.]

Jan Vorbrüggen wrote:
>
> 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.

Yeah. The problem on the VAX was that the WS list was an array
sized by WSMAX parameter that resided inside the process header,
and the system had an array of resident process headers
(the balance set). Since system space was limited, if you tried to
increase WSMAX larger, you were forced to drop the balance set count.

Also because all processes had the same sized WS array, it could
cause waste. If you set the value WSMAX high to handle one or two
very large processes (like a database server), all the zillions of
normal tiny processes would have these large pinned down ws list that
they didn't need. If you set the value smaller, then the large
process would soft-fault a lot.

The HP documentation does state that the WS list has moved
out of the process header to S2 space as of OS version 7.3-2
(I don't know what year that was).

But (and correct me if I am wrong, I haven't touched VMS since 1994)
the working set still seems to be managed as a great whacking
one-size-fits-all vector of working set entries sized by WSMAX
that must reside in non-pagable memory (or at least I saw nothing
that implied a change in their basic approach).

WRT WinNT, I have never found any documentation on it as detailed as
the VMS internals guide so its internal operations are just a guess.
However its KPROCESS header data structure contains a linked list
field called WorkingSetExpansionLinks which leads me to guess it
uses a more flexible approach.

Eric

[Andy Glew]

Brian Inglis <***@SystematicSW.Invalid> writes:

> local sucks,
> global rocks!
> ...
> Local LRU (like microkernels) was considered superior by academics,
> but global LRU (like monolithic kernels) is better on real workloads.

I remember similar conclusions
(a) from when I was at Gould 1985-1989, where we put the latest and greatest
working set scheduler into UNIX - and then backed off
(b) from reading the literature
but I'll rely on others to provide references.

Methinks this is the virtual memory / paging analogy of what I posted
about with respect to hardware caches some time ago: everybody talks
about partitioned LRU, but it almost never pays off. Global LRU, and
various approximations are where we are at.

In that earlier post about caches I ventured the guess that, if some
sort of local replacement is to be a win, it must be mixed with global
replacement. Since determining cache demand is hard, I suggested
randomization - e.g. use local 9/10s of the time, global 1/10 of the
time. Randomized to prevent resonance.

I conjecture that the same thing may apply to virtual memory / paging
systems. Although paging systems have much more time available to
applies "smarts" to determine memory demand, I don't know how well
these work for a varying workload. Randomized mixing of local and
global working set policies may help.

Or maybe local just sucks irretrievably.

[Terje Mathisen]

Andy Glew wrote:
> Brian Inglis <***@SystematicSW.Invalid> writes:
>
>> local sucks,
>> global rocks!
>> ...
>> Local LRU (like microkernels) was considered superior by academics,
>> but global LRU (like monolithic kernels) is better on real workloads.
>
> I remember similar conclusions
> (a) from when I was at Gould 1985-1989, where we put the latest and greatest
> working set scheduler into UNIX - and then backed off
> (b) from reading the literature
> but I'll rely on others to provide references.
>
> Methinks this is the virtual memory / paging analogy of what I posted
> about with respect to hardware caches some time ago: everybody talks
> about partitioned LRU, but it almost never pays off. Global LRU, and
> various approximations are where we are at.
>
> In that earlier post about caches I ventured the guess that, if some
> sort of local replacement is to be a win, it must be mixed with global
> replacement. Since determining cache demand is hard, I suggested
> randomization - e.g. use local 9/10s of the time, global 1/10 of the
> time. Randomized to prevent resonance.
>
> I conjecture that the same thing may apply to virtual memory / paging
> systems. Although paging systems have much more time available to
> applies "smarts" to determine memory demand, I don't know how well
> these work for a varying workload. Randomized mixing of local and
> global working set policies may help.
>
> Or maybe local just sucks irretrievably.

To me this problem reminds me somewhat of the malloc() problem:

When does it make sense to use local (i.e. application-specific)
allocation strategies vs simply having a single, solid, good-enough
global allocator.

We all know that in some specific instances, like a huge number of
small, equal-size allocation, a locally-optimized allocator can do a
much better job, but how often is this actually the right thing to do?

It seems to me that the slow but steady movement is in the direction of
languages that either hide alloc/free completely, or (with the help of
garbage collection) at least gets rid of free().

To bring it back to virtual memory and global/local replacement
policies, it is well-known that some applications, like Adobe PhotoShop,
use their own explicit/manual virtual memory allocator, just to be able
to avoid the OS virtual memory menagement being involved at all.

Terje
--
- <***@hda.hydro.com>
"almost all programming can be viewed as an exercise in caching"

[Brian Inglis]

fOn Mon, 15 May 2006 22:38:39 +0200 in alt.folklore.computers, Terje
Mathisen <***@hda.hydro.com> wrote:

>Andy Glew wrote:
>> Brian Inglis <***@SystematicSW.Invalid> writes:
>>
>>> local sucks,
>>> global rocks!
>>> ...
>>> Local LRU (like microkernels) was considered superior by academics,
>>> but global LRU (like monolithic kernels) is better on real workloads.
>>
>> I remember similar conclusions
>> (a) from when I was at Gould 1985-1989, where we put the latest and greatest
>> working set scheduler into UNIX - and then backed off
>> (b) from reading the literature
>> but I'll rely on others to provide references.
>>
>> Methinks this is the virtual memory / paging analogy of what I posted
>> about with respect to hardware caches some time ago: everybody talks
>> about partitioned LRU, but it almost never pays off. Global LRU, and
>> various approximations are where we are at.
>>
>> In that earlier post about caches I ventured the guess that, if some
>> sort of local replacement is to be a win, it must be mixed with global
>> replacement. Since determining cache demand is hard, I suggested
>> randomization - e.g. use local 9/10s of the time, global 1/10 of the
>> time. Randomized to prevent resonance.
>>
>> I conjecture that the same thing may apply to virtual memory / paging
>> systems. Although paging systems have much more time available to
>> applies "smarts" to determine memory demand, I don't know how well
>> these work for a varying workload. Randomized mixing of local and
>> global working set policies may help.
>>
>> Or maybe local just sucks irretrievably.
>
>To me this problem reminds me somewhat of the malloc() problem:
>
>When does it make sense to use local (i.e. application-specific)
>allocation strategies vs simply having a single, solid, good-enough
>global allocator.
>
>We all know that in some specific instances, like a huge number of
>small, equal-size allocation, a locally-optimized allocator can do a
>much better job, but how often is this actually the right thing to do?

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).

>It seems to me that the slow but steady movement is in the direction of
>languages that either hide alloc/free completely, or (with the help of
>garbage collection) at least gets rid of free().

And results in massive working sets for fairly trivial programs in
Java where garbage is rarely deallocated due to finalize rarely being
called.

>To bring it back to virtual memory and global/local replacement
>policies, it is well-known that some applications, like Adobe PhotoShop,
>use their own explicit/manual virtual memory allocator, just to be able
>to avoid the OS virtual memory menagement being involved at all.

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.

--
Thanks. Take care, Brian Inglis Calgary, Alberta, Canada

***@CSi.com (Brian[dot]Inglis{at}SystematicSW[dot]ab[dot]ca)
fake address use address above to reply

[Anne & Lynn Wheeler]

Brian Inglis <***@SystematicSW.Invalid> 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/

[Anne & Lynn Wheeler]

Brian Inglis <***@SystematicSW.Invalid> 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 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 &amp; 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/

[Mark Horsburgh]

On Mon, 15 May 2006 22:29:35 GMT, Brian Inglis <***@SystematicSW.Invalid> wrote:
> fOn Mon, 15 May 2006 22:38:39 +0200 in alt.folklore.computers, Terje
> Mathisen <***@hda.hydro.com> wrote:
>
>>It seems to me that the slow but steady movement is in the direction of
>>languages that either hide alloc/free completely, or (with the help of
>>garbage collection) at least gets rid of free().
>
> And results in massive working sets for fairly trivial programs in
> Java where garbage is rarely deallocated due to finalize rarely being
> called.

Could you explain what you're saying here? Whether garbage is collected
or not has nothing to do with finalize being called.

Cheers,
Mark

[Brian Inglis]

On Fri, 19 May 2006 15:45:13 GMT in alt.folklore.computers, Mark
Horsburgh <***@cantab.net> wrote:

>On Mon, 15 May 2006 22:29:35 GMT, Brian Inglis <***@SystematicSW.Invalid> wrote:
>> fOn Mon, 15 May 2006 22:38:39 +0200 in alt.folklore.computers, Terje
>> Mathisen <***@hda.hydro.com> wrote:
>>
>>>It seems to me that the slow but steady movement is in the direction of
>>>languages that either hide alloc/free completely, or (with the help of
>>>garbage collection) at least gets rid of free().
>>
>> And results in massive working sets for fairly trivial programs in
>> Java where garbage is rarely deallocated due to finalize rarely being
>> called.
>
>Could you explain what you're saying here? Whether garbage is collected
>or not has nothing to do with finalize being called.

IIRC Java GCs are supposed to call finalize to free memory occupied by
objects; a number of JVMs never call finalize, so memory is never
freed for reuse.

--
Thanks. Take care, Brian Inglis Calgary, Alberta, Canada

***@CSi.com (Brian[dot]Inglis{at}SystematicSW[dot]ab[dot]ca)
fake address use address above to reply

[John Dallman]

In article <jf5nj3-***@osl016lin.hda.hydro.com>,
***@hda.hydro.com (Terje Mathisen) wrote:

> When does it make sense to use local (i.e. application-specific)
> allocation strategies vs simply having a single, solid, good-enough
> global allocator.

IME, a local allocator is axiomatically worthwhile when you're starting
the job of creating a piece of software that you expect to be in use and
under maintenance as far as you can predict into the future, and can
reasonably anticipate absorbing man-decades of work.

At that point, having a serious think about memory management, and
especially about the interfaces to it that you'll need is seriously
worthwhile. Especially if you have to provide comprehensive undo or
rollback; the issues are best considered together. When you expect to
take 20-40 man-years before you have a deliverable product, putting six
man-months into getting the management of memory /right/ is well
worthwhile.

That assumes, of course, that the code is something which users will
push to the limits of the hardware it runs on.

> ... it is well-known that some applications, like Adobe
> PhotoShop, use their own explicit/manual virtual memory allocator,
> just to be able to avoid the OS virtual memory menagement being
> involved at all.

PhotoShop is a good example of something which one expects to continue
for a long time, to absorb man-decades of work, and to be pushed to the
limits of its hardware. People will always just use bigger bitmaps, if
they can.

---
John Dallman ***@cix.co.uk
"Any sufficiently advanced technology is indistinguishable from a
well-rigged demo"

[r***@antenova.com]

Anne & Lynn Wheeler wrote:
> "Doug MacKay" <***@gmail.com> writes:
> > The swap storage you're thinking of is only a small piece of a virtual
> > memory system. If it was removed from a virtual memory system you'd
> > still have a virtual memory system ;)
>
> see melinda's paper on the development of virtual memory and
> virtual machines in the 60s
> http://www.princeton.edu/~melinda/25paper.pdf
>
> part of it was mit had chosen ge for ctss follow-on multics.
>
> the science center
> http://www.garlic.com/~lynn/subtopic.html#545tech
>
> had added custom virtual memory to 360/40 and built cp/40 supporting
> virtual machines and paging/swapping.
>
> the 360/67 was official product with virtual memory support, built for
> tss/360. however, the science center ported cp/40 from the 360/40 to
> 360/67 renaming it cp/67.
>
> univ. of michigan also developed MTS (michigen terminal system) that
> supported virtual memory on 360/67 (also paging/swapping).
>
> however, there was at least one effort that modified os/360 to utilize
> the 360/67 virtual memory hardware w/o providing paging/swapping
> support. os/360 was nominally a "real address" operating system where
> applications were allocated contiguous areas of real memory. long
> running applications frequently resulted in storage fragmentation,
> there would be enough real memory to run an application but not
> located contiguously. the use of virtual memory hardware allowed
> discontiguous real storage to be appear to be contiguous.

There certainly would still be a virtual memory system without paging
to a slower store.
The VMs of some languages do something similar to virtual memory for
the purpose of stopping fragmentation.


The above gives much of the IBM (and to some extent US) view of virtual
memory.
For a little balance here are some articles on virtual memory
elsewhere, if anyone's interested.

http://en.wikipedia.org/wiki/Virtual_memory
http://en.wikipedia.org/wiki/B5000
http://en.wikipedia.org/wiki/Atlas_Computer

[Anne & Lynn Wheeler]

***@antenova.com writes:
> The above gives much of the IBM (and to some extent US) view of
> virtual memory. For a little balance here are some articles on
> virtual memory elsewhere, if anyone's interested.
>
> http://en.wikipedia.org/wiki/Virtual_memory
> http://en.wikipedia.org/wiki/B5000
> http://en.wikipedia.org/wiki/Atlas_Computer
>
a quote from Melinda's paper
http://www.princeton.edu/~melinda/

about some of the commitment to 360/67 and TSS/360:

What was most significant was that the commitment to virtual memory
was backed with no successful experience. A system of that period that
had implemented virtual memory was the Ferranti Atlas computer, and
that was known not to be working well. What was frightening is that
nobody who was setting this virtual memory direction at IBM knew why
Atlas didn't work. 23

... snip ...

taken from:

23 L.W. Comeau, ``CP­40, the Origin of VM/370'', Proceedings of SEAS
AM82, September, 1982, p. 40.

also more of the above quotes found in old post
http://www.garlic.com/~lynn/2000f.html#78 TSS ancient history

some amount of Melinda's paper explores the early CTSS work at MIT and
derivatives ... aka multics on the 5th floor 545 tech sq. and cp40,
cp67, vm370, virtual machines, etc at the science center on 4th floor
545 tech sq
http://www.garlic.com/~lynn/subtopic.html#545tech

aka ... not so much ibm, but more mit area.

the science center also did a lot of the stuff leading up to
capacity planning
http://www.garlic.com/~lynn/subtopic.html#bench

and gml (precursor to sgml, html, xml, etc) was invented in 69 at the
science center by "G", "M", and "L"
http://www.garlic.com/~lynn/subtopic.html#sgml

posts in this/related 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

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

[Anne & Lynn Wheeler]

as an aside .... there was a lot of close work with europe ... both
grenoble science center, cern, etc.

the original cp67 (and cp40) provided only "vanilla" 360 virtual
machines, but lacked virtualization support for virtual machine with
virtual memory capability. one of the people came over on assignment
from grenoble science center and did much of the implementation to
support virtualizing virtual memory aka all the shadow table stuff to
support virtual 360/67.

some number of years later he shows up running earn, minor reference
http://www.garlic.com/~lynn/2001h.html#65

also the grenoble science center had modified cp67 to have a "working
set dispatcher" and support local lru page replacement article and
published a paper in ACM on the work.

in the later contention over awarding a stanford phd thesis for
clock and global lru page replacement ... mentioned in prior
post
http://www.garlic.com/~lynn/2006i.html#28 virtual memory

i was able to supply performance comparison numbers of cp67 running at
the cambridge science center with global LRU page replacement and cp67
at the grenoble science center with local LRU page replacement ... which
possibly contributed to helping resolve the issue.

misc. past posts mentioning the cambridge/grenoble comparison
http://www.garlic.com/~lynn/93.html#7 HELP: Algorithm for Working Sets (Virtual Memory)
http://www.garlic.com/~lynn/94.html#1 Multitasking question
http://www.garlic.com/~lynn/99.html#18 Old Computers
http://www.garlic.com/~lynn/2001h.html#26 TECO Critique
http://www.garlic.com/~lynn/2001l.html#6 mainframe question
http://www.garlic.com/~lynn/2002c.html#49 Swapper was Re: History of Login Names
http://www.garlic.com/~lynn/2002o.html#30 Computer History Exhibition, Grenoble France
http://www.garlic.com/~lynn/2002q.html#24 Vector display systems
http://www.garlic.com/~lynn/2003f.html#50 Alpha performance, why?
http://www.garlic.com/~lynn/2004.html#25 40th anniversary of IBM System/360 on 7 Apr 2004
http://www.garlic.com/~lynn/2004c.html#59 real multi-tasking, multi-programming
http://www.garlic.com/~lynn/2004g.html#13 Infiniband - practicalities for small clusters
http://www.garlic.com/~lynn/2004q.html#73 Athlon cache question
http://www.garlic.com/~lynn/2005d.html#37 Thou shalt have no other gods before the ANSI C standard
http://www.garlic.com/~lynn/2005d.html#48 Secure design
http://www.garlic.com/~lynn/2005f.html#47 Moving assembler programs above the line
http://www.garlic.com/~lynn/2005h.html#10 Exceptions at basic block boundaries
http://www.garlic.com/~lynn/2005h.html#15 Exceptions at basic block boundaries
http://www.garlic.com/~lynn/2005n.html#23 Code density and performance?
http://www.garlic.com/~lynn/2006e.html#7 About TLB in lower-level caches
http://www.garlic.com/~lynn/2006e.html#37 The Pankian Metaphor
http://www.garlic.com/~lynn/2006f.html#0 using 3390 mod-9s

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

[Anne & Lynn Wheeler]

Anne & Lynn Wheeler <***@garlic.com> writes:
> 23 L.W. Comeau, ``CP­40, the Origin of VM/370'', Proceedings of SEAS
> AM82, September, 1982, p. 40.

random drift, during FS days, Les owned part of the FS architecture
related to advanced interconnect. my wife reported to him.
http://www.garlic.com/~lynn/subtopic.html#futuresys

she then went on to work in the g'burg jes group and then was con'ed
into going to POK to be responsible for loosely-coupled (i.e. cluster)
architecture.
http://www.garlic.com/~lynn/subtopic.html#shareddata

later when we started work on the ha/cmp product
http://www.garlic.com/~lynn/subtopic.html#hacmp

minor reference for some additional drift
http://www.garlic.com/~lynn/95.htm#13

Les had retired and was director of computing for one of the medical
schools in the boston area. He was also the "C" in CLaM ... a three
person dataprocessing consulting/services company in the Boston area.
We needed a lot of work done on hacmp ... and subcontracted a lof of
it out to CLaM (which contributed to their rapid growth).

The science center had moved from 545 tech sq, down the street to 101
Main. After they closed down the science center, CLaM took over their
space in 101 Main (for a time).

past 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

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

[r***@antenova.com]

Anne & Lynn Wheeler wrote:
> ***@antenova.com writes:
> > The above gives much of the IBM (and to some extent US) view of
> > virtual memory. For a little balance here are some articles on
> > virtual memory elsewhere, if anyone's interested.
> >
> > http://en.wikipedia.org/wiki/Virtual_memory
> > http://en.wikipedia.org/wiki/B5000
> > http://en.wikipedia.org/wiki/Atlas_Computer
> >
> a quote from Melinda's paper
> http://www.princeton.edu/~melinda/
>
> about some of the commitment to 360/67 and TSS/360:
>
> What was most significant was that the commitment to virtual memory
> was backed with no successful experience. A system of that period that
> had implemented virtual memory was the Ferranti Atlas computer, and
> that was known not to be working well. What was frightening is that
> nobody who was setting this virtual memory direction at IBM knew why
> Atlas didn't work. 23
>
> ... snip ...
>
> taken from:
>
> 23 L.W. Comeau, ``CP­40, the Origin of VM/370'', Proceedings of SEAS
> AM82, September, 1982, p. 40.

Yes. I read that bit. I don't know much about the Atlas' failings. It
used least-recently-used as the basis of replacing pages. People have
said that as a result very critical parts of the OS would get swapped
out.

> also more of the above quotes found in old post
> http://www.garlic.com/~lynn/2000f.html#78 TSS ancient history
>
> some amount of Melinda's paper explores the early CTSS work at MIT and
> derivatives ... aka multics on the 5th floor 545 tech sq. and cp40,
> cp67, vm370, virtual machines, etc at the science center on 4th floor
> 545 tech sq
> http://www.garlic.com/~lynn/subtopic.html#545tech
>
> aka ... not so much ibm, but more mit area.

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.

[Anne & Lynn Wheeler]

***@antenova.com 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/

[r***@antenova.com]

Anne & Lynn Wheeler wrote:
> ***@antenova.com 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.

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

[Anne & Lynn Wheeler]

***@antenova.com 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/

[Anne & Lynn Wheeler]

Anne & Lynn Wheeler <***@garlic.com> writes:
> 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.

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

i.e. my real undergraduate job was supporting and maintaining the
univ. datacenter production (real memory) os/360 batch system.

the stuff about inventing, implementing, and shipping production code
for things like replacement dynamic adaptive scheduling
http://www.garlic.com/~lynn/subtopic.html#fairshare
and replacement/paging algorithms
http://www.garlic.com/~lynn/subtopic.html#wsclock

as well as misc. other things like the hardware clone controller
http://www.garlic.com/~lynn/subtopic.html#360pcm

was much more of a hobby for entertainment.

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

[Peter Flass]

***@antenova.com wrote:
>
> Yes. I read that bit. I don't know much about the Atlas' failings. It
> used least-recently-used as the basis of replacing pages. People have
> said that as a result very critical parts of the OS would get swapped
> out.

The Burroughs 5500 MCP had the same problem. It was segmented, not
paged, and it swapped segments. I don't know whether it was
fragmentation or some other problem, but it was very possible to lock up
the system so only a Halt-Load (=reboot) could fix it. I got this a lot
when trying to run more than one instance of the sort. I still remember
the "00 no mem" message. ("00" was the MCP's process id).

[j***@aol.com]

In article <***@j33g2000cwa.googlegroups.com>,
***@antenova.com wrote:
>Anne & Lynn Wheeler wrote:
>> ***@antenova.com writes:
>> > The above gives much of the IBM (and to some extent US) view of
>> > virtual memory. For a little balance here are some articles on
>> > virtual memory elsewhere, if anyone's interested.
>> >
>> > http://en.wikipedia.org/wiki/Virtual_memory
>> > http://en.wikipedia.org/wiki/B5000
>> > http://en.wikipedia.org/wiki/Atlas_Computer
>> >
>> a quote from Melinda's paper
>> http://www.princeton.edu/~melinda/
>>
>> about some of the commitment to 360/67 and TSS/360:
>>
>> What was most significant was that the commitment to virtual memory
>> was backed with no successful experience. A system of that period that
>> had implemented virtual memory was the Ferranti Atlas computer, and
>> that was known not to be working well. What was frightening is that
>> nobody who was setting this virtual memory direction at IBM knew why
>> Atlas didn't work. 23
>>
>> ... snip ...
>>
>> taken from:
>>
>> 23 L.W. Comeau, ``CP­40, the Origin of VM/370'', Proceedings of SEAS
>> AM82, September, 1982, p. 40.
>
>Yes. I read that bit. I don't know much about the Atlas' failings. It
>used least-recently-used as the basis of replacing pages. People have
>said that as a result very critical parts of the OS would get swapped
>out.
>
>> also more of the above quotes found in old post
>> http://www.garlic.com/~lynn/2000f.html#78 TSS ancient history
>>
>> some amount of Melinda's paper explores the early CTSS work at MIT and
>> derivatives ... aka multics on the 5th floor 545 tech sq. and cp40,
>> cp67, vm370, virtual machines, etc at the science center on 4th floor
>> 545 tech sq
>> http://www.garlic.com/~lynn/subtopic.html#545tech
>>
>> aka ... not so much ibm, but more mit area.
>
>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.

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.

/BAH

[Anne & Lynn Wheeler]

***@aol.com 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/subnetwork.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 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/

[j***@aol.com]

In article <***@lhwlinux.garlic.com>,
Anne & Lynn Wheeler <***@garlic.com> wrote:
>***@aol.com 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

I'm not sure we ever had much bidding wars in the early 70s with
your science group's output. Didn't IBM use your nook to
do the R&D to eventually seep into the main stream of their
products?
>
>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

But what gets done and used in-house can be extremely horrible
to turn into a product that can be sold, maintained and put
into the company's main software production line.

>
>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/subnetwork.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 batch install base).

Right. At that time DEC was trying to do what IBM did very, very
well. And IBM was trying to do what DEC used to do very, very well.
It was one of the ironies of the biz. It reminded me of the
horse who always wanted the grass on the other side of the fence
no matter which side he was on. But I suppose that's what
competition is all about.

Clarification: I'm talking about each company's production line
work, not its special case work.
>
<snip-reluctantly>

/BAH

[Anne & Lynn Wheeler]

***@aol.com writes:
> Right. At that time DEC was trying to do what IBM did very, very
> well. And IBM was trying to do what DEC used to do very, very well.
> It was one of the ironies of the biz. It reminded me of the
> horse who always wanted the grass on the other side of the fence
> no matter which side he was on. But I suppose that's what
> competition is all about.
>
> Clarification: I'm talking about each company's production line
> work, not its special case work.

it wasn't that the science center didn't know how to do very well the
type of thing that DEC did very well and/or have as many customers as
DEC in this market segment ... it was that the size of the batch
market segment was so much larger than this market segment ... that
when people thot of the company ... they automatically thot of the
much larger batch market segment ... which seem to totally obfuscate
in their minds, the fact that the science center had been doing as
well as DEC in this totally different market segment.

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

[j***@aol.com]

In article <***@lhwlinux.garlic.com>,
Anne & Lynn Wheeler <***@garlic.com> wrote:
>***@aol.com writes:
>> Right. At that time DEC was trying to do what IBM did very, very
>> well. And IBM was trying to do what DEC used to do very, very well.
>> It was one of the ironies of the biz. It reminded me of the
>> horse who always wanted the grass on the other side of the fence
>> no matter which side he was on. But I suppose that's what
>> competition is all about.
>>
>> Clarification: I'm talking about each company's production line
>> work, not its special case work.
>
>it wasn't that the science center didn't know how to do very well

Sorry. When I say "very well" I include the whole biz process.
Sales, marketing, distribution, development, maintenance, everything.

> the
>type of thing that DEC did very well and/or have as many customers as
>DEC in this market segment ... it was that the size of the batch
>market segment was so much larger than this market segment ... that
>when people thot of the company ... they automatically thot of the
>much larger batch market segment ...

Yup. And the rest of IBM also thought this way. It establishes
a corporate mindset; so the little decisions that nudge the
company's direction of providing for their customers will
always have the batch slant to it. I can't describe this
very well.

> which seem to totally obfuscate
>in their minds, the fact that the science center had been doing as
>well as DEC in this totally different market segment.

I know we didn't know how to do, what you call, batch very well.
As late as, IIRC, 1980 or 1981, when JMF and CDO worked on
the TPS architectural spec, there were people who pooh-poohed
the need for a 1000 transactions per second. That was one
time the temptation to kick ass literally was high.

An unspoken bias at DEC was that hardware and code was
more important than data. I had to bang heads once in
a while to try to correct this unconscious attitude.

/BAH

[Anne & Lynn Wheeler]

***@aol.com writes:
> But what gets done and used in-house can be extremely horrible
> to turn into a product that can be sold, maintained and put
> into the company's main software production line.

as i've mentioned before we were operating a high-speed backbone,
but told we were allowed to bid on the initial NSFNET RFP,
recent posting discussing some of the subject:
http://www.garlic.com/~lynn/2006j.html#34 Arpa address

an older post also mentioning the subject
http://www.garlic.com/~lynn/internet.htm#0

the technology used in the internal network
http://www.garlic.com/~lynn/subnetwork.html#internalnet

was re-released the same year the resource manager was released (1976)
(a version with subset of the function had been released earlier)

it was also deployed for bitnet ... for a period in the early
80s, the number of bitnet nodes (independent of the internal
network nodes) was also as large or larger than the number
of arpanet/internet nodes.
http://www.garlic.com/~lynn/subnetwork.html#bitnet

this was also then propogated to europe for earn ... old earn
email by the person got the job to head it up
http://www.garlic.com/~lynn/2001h.html#65
and also mentioned in this recent posting
http://www.garlic.com/~lynn/2006i.html#31 virtual memory

some amount of the success of tcp/ip was having peer-to-peer (in
addition to gateways and internetworking) that extended down to
workstations and PCs.

as i've mentioned before there was significant internal corporate
politics by the communication group ... trying to maintain the
terminal emulation paradigm for workstations and PCs (in the mid-80s
there were huge number of PCs connected to internal networking nodes
... but they were mostly forced to be treated as emulated terminals
... as opposed to networking nodes):
http://www.garlic.com/~lynn/subnetwork.html#emulation

a few recent postings also discussing the subject
http://www.garlic.com/~lynn/2006h.html#52 Need Help defining an AS400 with an IP address to the mainframe
http://www.garlic.com/~lynn/2006i.html#2 The Pankian Metaphor
http://www.garlic.com/~lynn/2006j.html#8 ALternatives to EMail
http://www.garlic.com/~lynn/2006j.html#31 virtual memory

for a little drift ... i've been periodically made somewhat
facetious statements about the installed customer base
of products that originated from the science center work
http://www.garlic.com/~lynn/subtopic.html#545tech

was as large or larger than some other vendors whole product line;
however because the corporation's mainstream batch offerings so
dominated the market ... many people's impression of what products
were in the market place was obscured.

i've joked about some rivalry between the science center on the 4th
floor and the work that went on at the 5th floor at 545tech
sq. however, it was difficult to compare the two efforts in terms of
installed customers ... since there was so much of the corporation
behind the science center's effort.

i've periodically tried to put in into perspective by pointing out
that there was a really humongous installed batch customer based
... and that the installed customer base for the science center
technology was much smaller (that the batch customer base) ... and the
number of internal installed customers for the science center
technology was much smaller than the external customers.

now, one of my hobbies at the science center was producing my own
internal production system product and distributing and supporting it
directly for a limited number of internal customers. this was a small
subset of the total number of internal customers (which was in turn
smaller than the number of external customers, which in turn was much
smaller than the number of the batch external customers) ... however
at one point, the number of internal places running the heavily
customized system that I directly distributed was about the same as
the total number of systems (internal, external, over its complete
lifetime) that ever ran the system produced on the 5th floor.

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

[Anne & Lynn Wheeler]

***@aol.com writes:
> I'm not sure we ever had much bidding wars in the early 70s with
> your science group's output. Didn't IBM use your nook to do the R&D
> to eventually seep into the main stream of their products?

around the middle of the cp67 product cycle ... they split off the
cp67 group from the science center into a standard product group
... which eventually moved to the 3rd floor and absorbed the boston
science center located there (they had done cps ... converstational
programming system that swapped and ran in real memory environment
under os/360 ... and provided interactive basic and interactive pli,
jean sammet was also in the boston programming center). the cp67
product group continued to expand and also started the work to morph
cp67 to vm370). it eventually outgrew the space on the 3rd floor and
moved out to burlington mall taking over the old service bureau
corporation bldg. there (and growing to a couple hundred people).

misc. past posts mentioning the evoluation of the cp67 (and then
vm370) product group
http://www.garlic.com/~lynn/94.html#2 Schedulers
http://www.garlic.com/~lynn/98.html#7 DOS is Stolen!
http://www.garlic.com/~lynn/99.html#179 S/360 history
http://www.garlic.com/~lynn/2000b.html#54 Multics dual-page-size scheme
http://www.garlic.com/~lynn/2000b.html#55 Multics dual-page-size scheme
http://www.garlic.com/~lynn/2001m.html#47 TSS/360
http://www.garlic.com/~lynn/2001m.html#49 TSS/360
http://www.garlic.com/~lynn/2001n.html#67 Hercules etc. IBM not just missing a great opportunity...
http://www.garlic.com/~lynn/2002e.html#27 moving on
http://www.garlic.com/~lynn/2002h.html#34 Computers in Science Fiction
http://www.garlic.com/~lynn/2002h.html#59 history of CMS
http://www.garlic.com/~lynn/2002j.html#17 CDC6600 - just how powerful a machine was it?
http://www.garlic.com/~lynn/2002m.html#9 DOS history question
http://www.garlic.com/~lynn/2002o.html#78 Newsgroup cliques?
http://www.garlic.com/~lynn/2002p.html#14 Multics on emulated systems?
http://www.garlic.com/~lynn/2003c.html#0 Wanted: Weird Programming Language
http://www.garlic.com/~lynn/2003d.html#8 IBM says AMD dead in 5yrs ... -- Microsoft Monopoly vs. IBM
http://www.garlic.com/~lynn/2003f.html#53 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/2003h.html#34 chad... the unknown story
http://www.garlic.com/~lynn/2003k.html#0 VSPC
http://www.garlic.com/~lynn/2003k.html#55 S/360 IPL from 7 track tape
http://www.garlic.com/~lynn/2004.html#20 BASIC Language History?
http://www.garlic.com/~lynn/2004.html#32 BASIC Language History?
http://www.garlic.com/~lynn/2004c.html#47 IBM 360 memory
http://www.garlic.com/~lynn/2004d.html#42 REXX still going strong after 25 years
http://www.garlic.com/~lynn/2004e.html#37 command line switches [Re: [REALLY OT!] Overuse of symbolic
http://www.garlic.com/~lynn/2004g.html#24 |d|i|g|i|t|a|l| questions
http://www.garlic.com/~lynn/2004g.html#35 network history (repeat, google may have gotten confused?)
http://www.garlic.com/~lynn/2004g.html#38 Infiniband - practicalities for small clusters
http://www.garlic.com/~lynn/2004k.html#23 US fiscal policy (Was: Bob Bemer, Computer Pioneer,Father of
http://www.garlic.com/~lynn/2004m.html#6 a history question
http://www.garlic.com/~lynn/2004m.html#54 Shipwrecks
http://www.garlic.com/~lynn/2004n.html#7 RISCs too close to hardware?
http://www.garlic.com/~lynn/2004q.html#72 IUCV in VM/CMS
http://www.garlic.com/~lynn/2005f.html#58 Where should the type information be: in tags and descriptors
http://www.garlic.com/~lynn/2005h.html#37 Software for IBM 360/30
http://www.garlic.com/~lynn/2005j.html#25 IBM Plugs Big Iron to the College Crowd
http://www.garlic.com/~lynn/2005j.html#54 Q ALLOC PAGE vs. CP Q ALLOC vs ESAMAP
http://www.garlic.com/~lynn/2005p.html#0 Article: The True Value of Mainframe Security
http://www.garlic.com/~lynn/2005q.html#12 What ever happened to Tandem and NonStop OS ?
http://www.garlic.com/~lynn/2005q.html#14 What ever happened to Tandem and NonStop OS ?
http://www.garlic.com/~lynn/2005s.html#35 Filemode 7-9?
http://www.garlic.com/~lynn/2005s.html#36 Filemode 7-9?
http://www.garlic.com/~lynn/2006b.html#18 {SPAM?} Re: Expanded Storage

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

[Peter Flass]

***@antenova.com wrote:
> There certainly would still be a virtual memory system without paging
> to a slower store.
> The VMs of some languages do something similar to virtual memory for
> the purpose of stopping fragmentation.
>

Also:
* Provides a flavor of storage protection independent of other methods.
* Allows all processes to be run starting a a fixed memory address.
This can save relocations at load time, but anyone who has ever had to
debug an OS/360 dump where the addresses could be different for each run
will see the benefit.