Page Directories (PDs)  

The paging hardware needs a way to find the page tables.  This is done with something called a Page Directory (PD).  Every Job gets a PD (glad they weren't called Virtual Directories...).  Each entry in a PD is called a Page Directory Entry (PDE).  Each PDE holds the PHYSICAL address of a Page Table.  Each PDE is also 4 bytes long.  This means we can have 1024 PDEs in the PD.  Each of the PDEs points to a PT which can have 1024 entries each representing 4Kb of physical memory.  If we get our calculator out we'll see that this allows us to map the entire 4 gigabyte linear address space.
 
	1024 * 1024 * 4K (4096) = 4,294,967,296 (4 Gb)

We won't need this capability any time soon, Right?  Wrong.  What you don't see (because I haven't explained it yet) is that we really DO need most of this capability but we need it in pieces.  Read on... 

The Memory MAP

MMURTL's OS code and data are mapped into the bottom of every job's address space.  A job's memory space actually begins at the 1 gigabyte linear memory mark.  Why so high??  Because we could... NO, just kidding.  There was actually some serious thought given to this (over a few brews of course).  It's a nice round number (40000000h).  This gives the OS one gigabyte of linear memory space, and each application the same thing.  Besides, when we add demand paging to MMURTL's virtual memory, an application of a hundred megabytes or more is even conceivable.

The Map of a single Job and the OS is shown below. It is identical for every Job and Service that is installed.

Linear Top -----------  4Gb -1 byte 

  Dead address space

Linear Max ------------ 2Gb (Artificial maximum limit)

Job Allocated Memory -- 1Gb + Job Memory
  Data                  1Gb + Stack Page(s) + Code Pages
  Code                  1Gb + Stack Page(s)
  Intitial Stack        1Gb
Job Memory------------- 1Gb (Initial stack, Code, Data)

DLLs (loadable shared code)
Device Drivers

OS Allocated memory --- 0Gb + OS Memory
OS Memory ------------- 0Gb
Linear Base ----------- 0Gb

Now the pundits are screaming: What about the UPPER 2 GIGABYTES - IT'S WASTED!!!  Well, in a word, YES.  But it was for a good cause (No, we didn't give it to the Red Cross).  

In the scheme of things, the OS has to know where to find all these tables that are allocated for memory management.  It needs a FAST way to get to them for memory management functions.  Sure, we could have gone and built a separate table and managed it, but it wasn't needed.  Besides, we wanted to keep the overhead down. Read on and see what we did. 

The processor translates these linear (fake) addresses into real (physical) addresses by first finding the current Page Directory.  It does this by looking at the value we (the OS) put into Control Register CR3.  CR3 is the PHYSICAL ADDRESS of the current PD.  Now that it knows where the PD is, it uses the upper 10 bits of the Linear address it's translating as an index into the PD.  The entry it finds is the PHYSICAL address of the Page Table (PT).  When it has this, it uses the next lower 10 bits in the linear address it's translating as an index into the PT.  Now it's got the PTE (should it see a doctor?).  The PTE IS the physical address of the page it's after.  Sounds like a lot of work, but it does this with very little overhead (certainly less overhead than this explanation).

The OS has no special privileges as far as addressing physical memory goes. The OS uses linear addresses (fake ones) just like the applications do.  This is fine until you have to update or change a PDE or PTE.  We can't just get the value out of CR3 and use it to find the PT because it's the physical address (CRASH - PAGE FAULT).  Likewise, we can't just take a physical address out of a PDE and find the PT it points to. 

Finding the PD for an application is no problem.  When we started the application, we built the PD and we stuck the PHYSICAL address in the Task State Segment field for CR3, then we put the linear address of the PD in the Job Control Block.  This is fine for ONE address per job.  HOWEVER, now we're talking dozens or even hundreds of linear addresses for all the Page Tables that we can have (possibly several for each application).

This is what we use the upper 2 Kb of the Page Directories for.  We keep the linear address of all the PTs there.  2K doesn't sound like a lot to save, but when you start talking 10, 20, or even 30 jobs running it starts to add up.

We make this upper 2K a SHADOW of the lower 2K.  If you remember, each PDE has the physical address of each PT.  MMURTL needs to know the physical address of a PT for aliasing addresses (and it needs it fast). 

Exactly 2048 bytes above each real entry in the PD is MMURTL's secret entry with the linear address of the PT.  Well, the secret is out.  Of course these entries are marked NOT USED so the OS doesn't take a "pointer in the weeds" and try to do something with it.  

Page Directory Entries (PDEs)

I know you're trying to picture this in your mind. What does this make the PD look like?  Below is a list of the entries in the PD for that simple program we mapped (above).  This assumes the OS consumes only a few PTEs (1 page table max):

Entry #	Description

0		Physical address of OS PT
1		Empty PTE
.
.
256		Physical address of Job PT
257		Empty PTE
.
.
512		Linear Address of OS PT (Shadow - NOT PRESENT)
513		Empty Shadow PTE
.
.
768		Linear Address of Job PT (Shadow - NOT PRESENT)
769		Empty Shadow PTE
.
.
1023		Last Empty Shadow PTE

This doesn't show that each entry only has 20 bits for each address and the rest of the bits are for management purposes, but you get the idea. It is 20 bits because the last 12 bits of the 32 bit address are below the granularity of a page (4096 bytes). The 12 bits for a linear address are the same as the last 12 bits for a physical address.  As shown, all the shadow entries are marked NOT present, in fact, all of the entries with nothing in them are marked not present.  They simply don't exist as far as the processor is concerned.  If we desired, we could move the shadow information into separate tables and expand the OS to address and handle 4Gb of memory, but we were more interested in conservation at this point in time.  If we decided to do it, it would be transparent to applications anyway.

Something else the example doesn't show is that the entry for the Physical Address of the OS PT (0) is actually an alias (a copy) of the page tables set up in the initial monitor program.  We don't keep duplicate OS page tables. That would REALLY be a waste.

Allocation of Linear Memory 

You now know the mechanics of paging and how MMURTL uses the processor's paging hardware.  Now you need to know how MMURTL actually allocates the linear space in each job, or for the OS.  This is accomplished with three different calls depending what type of memory you want. AllocPage, AllocOSPage, and AllocDMAPage are the only calls to allocate memory in MMURTL. 

AllocPage allocates contiguous linear pages in the Jobs address range.  This is 1Gb to 2Gb.  The pages are all initially marked Read/Write with the user protection level. 

AllocOSPage allocates contiguous linear pages in the OS address range.  This is 0 to 1Gb.  The pages are all initially marked Read/Write with the System protection level and the entries automatically show up in all job's memory space because all the OS PTs are listed in every job's PD. 

AllocDMAPage allocates contiguous linear pages in the OS address range, but it ensures that these pages are below the 16 megabyte physical address boundary.  Direct Memory Access hardware on ISA machines can't access physical memory above 16 megabytes.  AllocDMAPage also returns the physical address needed by the user's of DMA. The pages are all initially marked Read/Write with the System protection level. 

All AllocPage calls first check to see if there are enough physical pages to satisfy the request.  If the physical memory exists, then they must find that number of pages as contiguous free entries in one of the PTs. If enough free PTEs in a row don't exist, it will create a new PT.  All AllocPage calls return an address to contiguous linear memory, or will return an error if it's not available.  With a one gigabyte address space, it's unlikely that it won't find a contiguous section of PTEs.  It's more likely you will run out of physical memory (the story of my life...).  

DeAllocation of Linear Memory

When pages are deallocated, the caller passes in a linear address (from a previous AllocPages call) along with the number of pages to deallocate. The caller is responsible for ensuring that the number of pages in the DeAlloc call does not exceed what was allocated.  If it does, the OS will attempt to deallocate as many pages as requested which may run into memory that was allocated in another request (but only from the caller's memory space).  If so, there will be no error, but the memory will not be available for later use.  If fewer number of pages are passed in, only that number will be deallocated.  The caller will never know (nor should it try to find out) where the physical memory is located with the sole exception of DMA users (device drivers).

Managing Physical Memory

We have discussed how MMURTL handles linear addresses. Now comes that easy part. Managing physical memory.

Allocation of Physical Memory

The fact that the processor handles translation of linear to physical memory takes a great deal of work away from the OS.  It is not important (nor do we even care) if pages of memory in a particular job are physically next to each other (with the single exception of DMA).  The main goal of physical memory management is simply to ensure we keep track of how much physical memory there is, and whether or not it's currently in use.  

Physical memory allocation is tracked by pages with a single array.  The array is called the Page Allocation Map (PAM, which is also my sister's name, and to keep up family relations I told her I named this array after her).

The PAM is similar to a bit allocation map for a disk.  Each byte of the array represents eight 4Kb pages (one bit per page).  This means the PAM would be 512 bytes long for 16 Mb of physical memory.  The current version of MMURTL is designed to handle 64 Megabytes of physical memory which makes the PAM 2048 bytes long. Now if I could only afford 64 Megs of RAM...  The PAM is an array of bytes from 0 to 2047, with the least significant bit of byte 0 representing the first physical 4K page in memory (Physical Addresses 0 to 4095). 

For AllocPage and AllocOSPage, we allocate physical memory from the top down.  For AllocDMAPage we allocate physical memory from the bottom up. This ensures that even if you install a device driver that uses DMA after your applications are up and running, there will be physical memory below 16 megabytes available (if any is left at all).

The PAM only shows us which pages of memory are in use. It does not tell us who they belong to.  To get this information we must go to the PDs and PTs.

Key points to remember on memory management:

* One Page Directory (PD) for each job.
* Linear address of the PD is kept in the Job Control Block.
* One or more Page Tables (PT) for each Job.
* One or more PTs for the OS.
* OS PTs are MAPPED into every Job's Page Directory.
  by making entries in the Job's PD.
* OS uses upper 2Kb of each PD for linear addresses of PTs.
* Physical memory is tracked with a bit map.


What does all this mean to the applications programmer??? Not much I'm afraid.  They don't need to know this stuff at all to write a program for MMURTL.  It's you system weenies, and those that will brave the waters and make MMURTL better than it is that really need this information.

The application programmer needs to know that:

 - The minimum amount of allocated memory is 4Kb (one page).
 - Memory is allocated in 4Kb increments (pages).
 - Jobs can allocate one or more pages at a time.
 - Jobs can deallocate one or more pages at a time.


Initialization of Memory

Now for the old Chicken and the Egg.

If the OS really isn't a task, how does it get up and running.  Well, it's an egg before it's a chicken, but if things don't work right, it's an omelet and never makes it to the feathered stage.  Many omelets (and scrambled eggs) were produced writing MMURTL.  I've sent my processor "where no address has gone before..." many, many, many times.

There is an initial OS task that sets everything up, takes the processor into protected mode, then finally into paged memory mode (two different steps).