General questions about virtual memory

[Erik Trulsson]

On Wed, Jul 30, 2008 at 07:59:53AM -0400, FreeBSD Hackers wrote:
> Hi, all.  I apologize for not posting a question specific to FreeBSD (I'll
> study about that later), but I'm looking for some help understanding a few
> things and I don't know where else to turn.  Using FreeBSD to give me
> concrete examples of how certain things work is okay, since I do use FreeBSD
> and I intend to read and study books covering the design and implementation
> of FreeBSD.
> 
> I recently picked up one of my old college textbooks, "Modern Operating
> Systems" (Tanenbaum, an older edition, but I'm not sure which one since the
> book is at home and I am not) with a strong desire to read it cover-to-cover
> and get a solid foundation of the concepts described therein.  The chapter
> on virtual memory has left me with some questions, and if anyone would be
> willing to help me understand (either on or off list) a few things that
> aren't clear, I would very much appreciate it.

You could try picking up one of Tanenbaum's other books: "Structured
Computer Organization", which among other things cover virtual memory from
a hardware perspective. (At least my copy does. It is the third edition,
which is not the latest.)


> 
> Examples of some specific questions that I have include:
> 
> WRT translation of virtual addresses to physical addresses, where does the
> hardware stop and the software begin?  Explanation: who determines the
> format of the page tables (CPU or OS)?  Who populates and maintains the page
> tables?  Where does the translation lookaside buffer reside?  Who maintains
> the TLB?

It can vary a bit between different architectures, but in general the format
of the page tables is determined by the CPU.  The TLB is located inside the
CPU (so it can be accessed quickly, it is after all just a specialized
cache.)  The page tables are normally populated and maintained by the OS,
the CPU just reads them.  The TLB is typically maintained in hardware, but
there are systems where it has to be updated by the OS.


> 
> Also WRT page tables, how does the OS and the MMU adjust for different sizes
> of physical RAM?  Wouldn't the page tables for a system with 512 MB of RAM
> will be fewer than the page tables for a system with 2 GB of RAM?  How does
> the CPU know how many page table entries there are?

The page tables are typically used for mapping between virtual and physical
addresses (and also for access rights to the mapped memory).  This means
that the size of the page table depends primarily on the size of the virtual
memory which is not dependent on the actual RAM installed.

The page tables are typically a tree-like structure, where the top level is
a fairly small (typically one page) fixed-size array which contains pointers
to the next level of the page table.  In that level there are either yet
another array of entries each of which is either a pointer to another level,
or a page descriptor.  You walk down the tree until you either find a
descriptor for the page you are looking for or an entry saying that pages
further down that branch has not been allocated.

How many levels there are is system dependent.  IIRC the i386 only uses a
two-level format (three levels when using PAE), while the Motorola 68030
could have as many as seven levels.


> 
> I have a few more questions, but for starters this is the kind of
> information I'm seeking.  I'm just not getting a clear enough picture from
> the textbook I'm reading now.  (It makes me wish I was still in college so I
> could dump my questions on my college professor. :)
> 
> If anyone is willing to help me understand this, I would greatly appreciate
> it.  I would also value your input if there are other resources (people,
> mailing lists, books, web pages, etc.) that you want to recommend instead of
> taking some time to help teach me.


You could try picking up one of Tanenbaum's other books: "Structured
Computer Organization", which among other things cover virtual memory from
a hardware perspective, including examples for how the page tables are
organized for a couple of example architectures.


-- 
<Insert your favourite quote here.>
Erik Trulsson
ertr1013 at student.uu.se