Flammarion engraving of the virtual universe

Virtual Memory Project

by: burt rosenberg
at: university of miami
date: sep 2024

Goals

• To understand virtual memory
• To practice C bit operations.

Files Provided

The provided files are,

• Makefile: Build and test according to the make-targets in this file.
• virtmem.h: Definition of all data structures, globals and function signatures.
• chatter.c and demand.c: Driver programs containing main.
• virtmem-sub.c: This is a template, and your work is to modify the template.
• *.txt and *.ref: For testing.

The Virtual Memory that Never Was

You are to implement a simulation of a virtual memory system. The particular details were never used in any actual computer but conceptually it is accurate.

Virtual memory systems have a memory model that specifies the size of the virtual memory space, the size of the physical memory space, the size of the pages, the number of pages and the number of page frames. Sizes are always pure powers of two, so the size is measure in bits. Also because of using powers of two, all arithmetic can be replaced by bit operations: bit-and, bit-or and bit-shift.

For the project we will simulate a 16 bit memory space, as had the 8085 processor. The pages size is set to 512 bytes, or 9 bits, and the remaining 7 bits will indicate the page or page frame.

The table shows values for actual Intel processors.

Data structure walkthrough

struct PhysicalMemory {
	char * memory ;
	char * next_free_page ;
} ;

struct VirtualMemory {
	struct PhysicalMemory * pm ;
	char * ptes[PAGE_TABLE_SIZE] ;
} ;

example computation virtual to physical

{
    // high order bit must be zero
    int page = (v_addr & PAGE_MASK) >> 9 ;
    char * phys_page = vm->ptes[page] ;
    // check for a page fault
    assert (phys_page) ; 
    offset = v_addr & OFFSET_MASK ;
    // using + to avoid type cast to int
    p_add = vm->ptes[page] + offset ; 
}

         integer where we only use the low order 16 bits
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
              | 7 bits                        |  9 bits
              V                               V
+---------------------------|-----------------------------------+
|     virtual page number   |               offset              |
+---------------------------|-----------------------------------+
              |                               | 
              V  int                          |
       +------------+                         |
       |            |                         |
       | page table |                         |
       |            |                         |
       +------------+                         |
              |  char *                       |
              V                               V  
+---------------------------|-----------------------------------+
|      page frame number    |               offset              |
+---------------------------|-----------------------------------+
             a char * as a native memory pointer

struct PhysicalMemory

Here are the details of the implementation you are to work with and complete the coding of.

We will simulate the memory with a malloc of 64k, aligned to the page size; that is, the pointer to the base of our simulated memory will have the lower 9 bits zero. See the struct PhysicalMemory.

The struct also has a next_free_page field that keeps track of unallocated space. Virtual memory systems can keep track of each page frame whether it is available for use or assigned. We just have this one mechanism: all page frames below next_free_page are in used, and the rest are not.

struct VirtualMemory

Each virtual memory space has a struct VirtualMemory structure, which contains the page table as an array of page table entries (PTE). A pte is a char * and is a native memory pointer, pointing directly to a byte in memory, that will be within the region of memory pointed to by pm->memory.

If the contents of the PTE is NULL, no physical page has been assigned, as the NULL address will cause an illegal dereference.

Multiple virtual memory structs can be allocated, just as an operating system will keep track of per process virtual address spaces. Our test codes will exercise the possibility.

A word about right bit shift. The result
of a right bit shift depends on if the integer
is signed or unsigned. See if you can explain
the output of this code:

#include<stdio.h>
int main(){
    short ss ; 
    unsigned short us ;
    ss = -1 ;
    us = ss ;
    for (int i=0;i<4;i++) {
        printf("%6d %6du\n", ss, us) ;
        ss = ss>>1 ;
        us = us>>1 ;
    }
    return 0 ;
}

% ./a.out                 
    -1  65535u
    -1  32767u
    -1  16383u
    -1   8191u

Project discription

In the previous section I talked about the data structures. I do suggest looking at virtmem.h because it is through the data structures that a program can be understood. This section talks about the behavior of a correct project based on the main routines chatter.c and demand.c.

The program chatter.c constructs a physical memory object, then constructs four virtual memory objects. In each of the four virtual memory objects, four PTE's are allocated. That is, in each of the four virtual memories to bytes 0 through 2023 are mapped to physical memory.

Then vm_write_char is repeated called to fill the virtual memory. The physical memory is dumped to standard out and compared to a reference file.

In this first step, complete virtmem-sub.c to make this output match the reference file.

Demand paging

When a page is referenced, and the PTE is invalid (in our case, equal to NULL), a page fault occurs. In the previous code, you are allowed to halt the program on a page fault condition. This is the same as seg faulting in the real world.

The program demand.c, however, implements demand paged virtual memory. When the page fault occurs, the code in virtmem-sub.c should allocate a page of physical memory to the virtual memory, allowing the memory reference to succeed.

In order to test the modifications to the function mmu_map, implement the string writing function vm_write_str. That will allow a long string of characters to be written to virtual memory, thereby causing a page fault.

The program demand.c works in two modes. You can test and debug in its interactive mode. The Makefile tests run it its streaming mode, where input is cat'ed into the program and the output is captured to a file.

The format of the input to demand.c is line by line, with the first character of the line being notable. The manpage, following, explain this in detail.

Manpage discriptions

NAME
    demand -- implement demand paged virtual memory
    
SYNOPSIS
    demand [-vt]

DESCRIPTION
    The command is either interactive, accepting input form the keyboard, or
    a file can be piped into the program, and it will run until the end of file.
    
    Command lines have a first character that direct the handling of that line of input.
    The commands are,

        . if the line begins with a dot the command exits
        + if the line begins with a plus the page tables are printed to standard out
        0 if the line begins with the digit 0, the rest of the line is a string to be
          copied into physical memory using virtual memory space 0
        1,2,3 same as 0, except use virtual memory space 1, 2 or 3, respectively
        
    Other cases the entire line is ignored.
    
OPTIONS
    The following options are available:
    
    -v verbose output
    -vv very verbose
    -t print the page tables after setup

OUTPUT
    In non-interactive mode, as the program exist on end of file the contents of
    the physical memory is written to standard out.
    
HISTORY
    New for csc421 edition 251.
    
BUGS
  

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

author: burton rosenberg
created: 4 sep 20204
update: 4 sep 20204