carlton@ji.Berkeley.EDU (Mike Carlton) (02/22/89)
The subject line says it all: can anyone give me some good references for inverted page tables? I'm looking for a good explanation of their design and use (including design of a good hash function) and also some specific details on their use in the IBM 801. I have the ACM TOC paper on the 801 from February 1988, but it doesn't go into much detail. Many thanks, Mike (carlton@ji.berkeley.edu or ...!ucbvax!ji!carlton)
ken@gatech.edu (Ken Seefried iii) (02/23/89)
IBM has a booklet called "IBM RT Personal Computer Technology" (Form No. SA23-1057, whatever that means) that is a compilation of articles discussing various aspects of the IBM PC/RT (an IBM 801 derivative). There are several articles about the MMU. One of them discusses the inverted page table scheme, though not in extreme detail. Perhaps this would be a start... ...ken seefried iii ken@gatech.edu
ohbuchi@unc.cs.unc.edu (Ryutarou Ohbuchi) (02/25/89)
Inverted page table is used in IBM System/38. I remember a couple of papers (in ISCA?, around 1980?) on System/38 mentioning inverted page table (unfortunately, they are in my reading room back in Japan), in addition to the one on RT-PC someone mentioned. Inverted page table is convenient to support virtual address space much larger than physical address space, since size of page table is linear function of physical address space size, rather than the virtual address space size. It is called "inverted" since it is looked up by physical address, rather than virtual address (e.g., through hashing.) (This resembles to the 'inverted list' (or whatever) in the field of database, right ?) ============================================================================== Any opinion expressed here is my own. ------------------------------------------------------------------------------ Ryutarou Ohbuchi "Life's rock." "Climb now, work later." ohbuchi@cs.unc.edu <on csnet> Department of Computer Science, University of North Carolina at Chapel Hill ==============================================================================
baum@Apple.COM (Allen J. Baum) (02/25/89)
>In article <6446@saturn.ucsc.edu> ken@gatech.edu (Ken Seefried iii) writes: > >IBM has a booklet called "IBM RT Personal Computer Technology" (Form >No. SA23-1057, whatever that means) that is a compilation of articles >discussing various aspects of the IBM PC/RT (an IBM 801 derivative). > >There are several articles about the MMU. One of them discusses the >inverted page table scheme, though not in extreme detail. See also: [ I assume this is a patent number. --DL ] 4,638,426 FILED: Sep. 19, 1983 Granted : Jan. 20, 1987 Virtual memory address translation mechanism with controlled data persistence Lots of gory details. -- baum@apple.com (408)974-3385 {decwrl,hplabs}!amdahl!apple!baum
sauer@cs.utexas.edu (Charlie Sauer) (02/25/89)
In article <6446@saturn.ucsc.edu>, ken@gatech.edu (Ken Seefried iii) writes: > > IBM has a booklet called "IBM RT Personal Computer Technology" (Form > No. SA23-1057, whatever that means) that is a compilation of articles > discussing various aspects of the IBM PC/RT (an IBM 801 derivative). > > There are several articles about the MMU. One of them discusses the > inverted page table scheme, though not in extreme detail. There was also an analogous book on the System/38, which also has inverted page tables. I don't own a copy of that book, and the only reference I can lay my hands on doesn't have a order number, but the title is "IBM System/38 Technical Developments." It was published in '78. I know that there was a virtual memory article in that book, by R.E. French and others, so there may be discussion of inverted page tables in that or some other article. Charlie -- C.H. Sauer IBM Advanced Workstations Div. !'s: cs.utexas.edu!ibmaus!sauer 11400 Burnet Road, D75/802 @'s: @CS.UTEXAS.EDU:sauer@ibmaus.uucp Austin, Texas 78758-2502 !&@: ibmaus!sauer@CS.UTEXAS.EDU (512) 823-3692 vnet: SAUER at AUSVM6
hine@comp.vuw.ac.nz (John Hine) (02/28/89)
In article <6464@saturn.ucsc.edu> ohbuchi@unc.cs.unc.edu (Ryutarou Ohbuchi) writes: > >Inverted page table is used in IBM System/38. I remember a couple of >papers (in ISCA?, around 1980?) on System/38 mentioning inverted page >table (unfortunately, they are in my reading room back in Japan)... Try Houdek, Soltis and Hoffman, IBM S/38 Support for Capability Based Addressing, 8th Symposium on Computer Arch., 1981 (CAN Vol 9 No 3). Berstis, Security and Protection of Data in the IBM S/38, 7th Symposium on Computer Arch., 1980 (CAN Vol 8 No 3). jh -- ----------------------------------------------------------------------- Domain: hine@comp.vuw.ac.nz Dept. of Computer Science UUCP: ...!uunet!vuwcomp!hine Victoria University P.O. Box 600, Wellington, NZ
ed@uunet.UU.NET (Ed Basart) (02/28/89)
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