Path: utzoo!attcan!uunet!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: <9758@pt.cs.cmu.edu>
Date: 28 Jun 90 20:23:51 GMT
References: <3300142@m.cs.uiuc.edu>
Organization: Carnegie-Mellon University, CS/RI
Lines: 40

In article <3300142@m.cs.uiuc.edu> march@m.cs.uiuc.edu writes:
>While reading Hennessey and Patterson (p. 437), they mention the fact
>that page tables entries are often paged themselves (with the operative
>word being often).  Now to me, paging you're means of address translation 
>makes no sense.  As they continue to point out, the cost of this is 
>appreciable because one has to swap the PTEs back in and then do the 
>translation.  Given this, just how "often" is this used?  I suppose
>given a translation-lookaside buffer, the hugh cost of swapping page
>table entries back in could be offset by some translations being very
>fast (via the TLB).

This cost is incurred only if the OS software decides to make the
page tables swappable.  The cost of a swap may not be known at the
chip-designer level, because a general purpose design could be
suitable for quite varying amounts of memory, and varying speeds of
swap devices, and of course varying demands upon that memory. 

The OS designer balances memory demands and  swap speed against swap
frequency.  Note that a 16 byte table entry per 512 byte page is only
a 3% overhead. Most designs run leaner.

The chip designer does control the cost of a simple TLB refill.  For
example, the 88000 and 68020 (well, 68851) have table-walk hardware,
whereas the R3000 designers punted TLB refill to an interrupt handler
and some special instructions.

The chip designer also controls the replacement algorithm of the TLB.
(That is, when an item is loaded into a TLB, some slot has to be
selected and overwritten.)  The 68020 uses a pseudo-LRU algorithm for
this.  The 88000 uses FIFO - entries, valid or not, are just shifted
off the end into the bit bucket. The R3000 hardware selects victims
with a pseudo-random.  (Very pseudo.) Are these equivalent?  Not
hardly!  It's always been assumed that it just doesn't matter.

Discussions on this topic usually move on the the issue of Process ID
tags, which are variously a few bits (MIPS) or one bit (88000).
(Does the i860 have PIDs?)  From there one gets into task switch
issues, which is to say, flushing.
-- 
Don		D.C.Lindsay