Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!pt.cs.cmu.edu!MATHOM.GANDALF.CS.CMU.EDU!lindsay
From: lindsay@MATHOM.GANDALF.CS.CMU.EDU (Donald Lindsay)
Newsgroups: comp.arch
Subject: Re: Paging page tables
Message-ID: <9818@pt.cs.cmu.edu>
Date: 5 Jul 90 20:55:17 GMT
References: <3300142@m.cs.uiuc.edu> <1990Jun29.154940.22762@tera.com> <2936@skye.ed.ac.uk>
Organization: Carnegie-Mellon University, CS/RI
Lines: 28

In article <2936@skye.ed.ac.uk> richard@aiai.UUCP (Richard Tobin) writes:
>Do operating systems that allow sparse address spaces (eg SunOS 4) use
>paged page tables to achieve this?  Is the fact that BSD doesn't use
>the Vax's paged page tables the reason why it doesn't support sparse
>address spaces?

The answer is no. The VAX hardware supports multilevel page tables,
so the "usual" sparse address spaces can be described by a fairly
small page table.

For example: the 88000 uses a two level table.  The first level is a
single 4 KB page, containing 1024 one-word entries.  The second level
is N pages, where N is less-than-or-equal-to 1024. Each second level
page can access 1024 data pages. Conveniently, 1024 * 1024 * 4 KB is
4 GB, which is what you need when virtual addresses are 32 bits.

In the example you gave, there was a code region, and a stack.  If
each of these is smaller than 4 MB, then the 88000's page table for
that fits into three pages. In the first level table, there are 1022
null entries, and two valid entries.

If (say) a particular compile had a 10 MB heap, then the 88000's page
table would occupy 3 pages, +1 for the stack, +1 for the first level.
That's 5 pages (20 KB), or an overhead of one fifth of one percent.
For smaller programs, the overhead is relatively higher, but that's
not a major problem.
-- 
Don		D.C.Lindsay