Path: utzoo!attcan!uunet!lll-winken!ames!mailrus!tut.cis.ohio-state.edu!ucbvax!agate!saturn!lupine!ed@uunet.UU.NET
From: lupine!ed@uunet.UU.NET (Ed Basart)
Newsgroups: comp.os.research
Subject: Re: Inv. Page Table references wanted
Message-ID: <6526@saturn.ucsc.edu>
Date: 28 Feb 89 07:31:10 GMT
Sender: usenet@saturn.ucsc.edu
Organization: Network Computing Devices, Palo Alto, CA
Lines: 16
Approved: comp-os-research@jupiter.ucsc.edu



It's not clear whether you want an explanation of inverted page tables, or
just a pointer to a good reference.

Anyway, the Ridge machine built in 1982 used inverted page tables.  It used
a segmented address with 16-bit segment address and 32-bit linear address
space.  The OS used about 10 bits worth of segments, so the hash scheme built
a primary hash of the upper 10 bits, then chained for the rest of the entries.
Average search was 1.4 - 2.2 probes.

-- 

Ed Basart
Network Computing Devices
uunet!lupine!ed