Assignment 3 - Virtual Memory Manager
This assignment will help you understand address spaces and virtual memory management.
In this assignment, you will implement an external pager, which is a process that handles virtual memory requests for application processes. The external pager ("pager" for short) is analogous to the virtual-memory portion of a normal operating system. The pager will handle address space creation, read and write faults, address space destruction, and simple argument passing between spaces. Your pager will manage a fixed range of the address space (called the arena) of each application that uses it. Your pager will be single threaded, handling each request to completion before processing the next request. Valid pages in the arena will be stored in (simulated) physical memory or in (simulated) disk. Your pager will manage these two resources on behalf of all the applications using the pager.
In addition to handling page faults, your pager will handle two system calls: vm_extend and vm_syslog. An application uses vm_extend to ask the pager to make another virtual page of its arena valid. An application uses vm_syslog to ask the pager to print a message to its console.
This handout is organized as follows. Section 1 describes how the infrastructure for this assignment performs the same tasks as the MMU and exception mechanism on normal computer systems. Section 2 describes the MMU used in this assignment. Section 3 describes the system calls that applications can use to communicate explicitly with the pager. Section 4 is the main section; it describes the functionality that you will implement in the external pager. Section 5 describes how your pager will maintain the emulated page tables and access physical memory and disk. Section 6 gives some hints for doing the assignment, and Sections 8-11 describe the test suite and assignment logistics/grading.
Download the starter files from here:assignment3.tar.gz
1. Infrastructure and System Setup
In a normal computer system, the CPU's MMU (memory management unit) and exception mechanism perform several important tasks. The MMU is invoked on every virtual memory access. These important tasks include:
For accesses to non-resident or protected memory, the MMU triggers a page fault or protection exception, transfers control to the kernel's fault handler, then retries the faulting instruction after the fault handler
For resident memory accesses that are allowed by the page's protection, the MMU translates the virtual address to a physical address and accesses that physical
Some MMUs automatically maintain dirty and reference bits; other MMUs leave this task to be handled in software. The MMU in this assignment does NOT automatically maintain dirty or reference bits.
On normal computer systems, system call instructions also invoke the exception mechanism. When a system call instruction is executed, the exception mechanism transfers control to the registered kernel handler for this exception.
We provide software infrastructure to emulate the MMU and exception functionality of normal hardware. To use this infrastructure, each application that uses the external pager must include "vm_app.h" and link with "libvm_app.a", and your external pager must include "vm_pager.h" and link with "libvm_pager.a". You do not need to understand the mechanisms used to emulate
this functionality (in case you're curious, the infrastructure uses mmap, mprotect, SEGV handlers, named pipes, and remote procedure calls).
Linking with these libraries enables application processes to communicate with the pager process in the same manner as applications on real hardware communicate with real operating systems.
Applications issue load and store instructions (compiled from normal C++ variable accesses), and these are translated or faulted by the infrastructure exactly as in the above description of the MMU. The infrastructure transfers control on faults and system calls to the pager, which receives control via function calls.
The following diagram shows how your pager will interact with applications that use the pager. An application makes a request to the system via the function calls vm_extend, vm_syslog and vm_yield, or by trying to load or store an address that is non-resident or protected.
Note that there are two versions of vm_extend and vm_syslog: one for applications and one for the pager. The application-side vm_extend/vm_syslog is implemented in libvm_app.a and is called by the application process. The pager-side vm_extend/vm_syslog is implemented by you in your pager. Think of the vm_extend/vm_syslog in libvm_app.a as a system call wrapper, and think of the vm_extend/vm_syslog in your pager as the code that is invoked by the system call. When the application calls its vm_extend/vm_syslog (the one in libvm_app.a), the infrastructure takes care of invoking the system call vm_extend/vm_syslog in your pager. See the header files vm_app.h and vm_pager.h for the actual function declarations.
2. Simulated MMU
The MMU being simulated in this assignment is a single-level, fixed-size page table. A virtual address is composed of a virtual page number and a page offset:
The page table used by this MMU is an array of page table entries (PTEs), one PTE per virtual
page in the arena. The MMU locates the page table through the page table base register (PTBR). The PTBR is a variable that is declared and defined by the infrastructure (but will be controlled by your pager). The following portion of vm_pager.h describes the arena, PTE, page table, and PTBR.
/* size (in bytes) of arena */ #define VM_ARENA_SIZE 0x20000000
/*
* **************************************
* * Definition of page table structure *
* **************************************
*/
/*
Format of page table
read_enable=0 ==> loads to this virtual page will fault
write_enable=0 ==> stores to this virtual page will fault
ppage refers to the physical page for this virtual page (unused if
both read_enable and write_enable are 0)
*/
typedef struct {
unsigned long ppage : 20;
/* bit 0-19 */ unsigned int read_enable : 1;
/* bit 20 */ unsigned int write_enable : 1; /* bit 21 */
} page_table_entry_t;
/*
Format of page Entries start at virtual page VM_ARENA_BASEPAGE,
e. ptes[0] is the page table entry for virtual page VM_ARENA_BASEPAGE.
*/
typedef struct {
page_table_entry_t ptes[VM_ARENA_SIZE/VM_PAGESIZE];
} page_table_t;
/*
MMU's page table base This variable is defined by the
infrastructure, but it is controlled completely by the student's pager
*/
extern page_table_t *page_table_base_register;
3. Interface used by applications of the external pager
Applications use three system calls to communicate explicitly with the simulated operating system: vm_extend, vm_syslog, and vm_yield. The prototypes for these system calls are given in the file "vm_app.h":
#define _VM_APP_H_
/*
vm_extend() -- ask for the lowest invalid virtual page in the process's
arena to be declared Returns the lowest-numbered byte of the new
valid virtual E.g., if the valid part of the arena before calling
vm_extend is 0x60000000-0x60003fff, the return value will be 0x60004000,
and the resulting valid part of the arena will be 0x60000000- 0x60005fff.
vm_extend will return NULL if the disk is out of swap
*/
extern void *vm_extend(void);
/*
vm_syslog() -- ask external pager to log a message (message data must
be in address space controlled by external pager). Logs message of length
Returns 0 on success, -1 on failure,
*/
extern int vm_syslog(void *message, unsigned int len);
/*
vm_yield() -- ask operating system to yield the CPU to another process.
The infrastructure's scheduler is non-preemptive, so a process runs until
it calls vm_yield() or
*/
extern void vm_yield(void);
#define VM_PAGESIZE 8192
#endif /* _VM_APP_H_ */
The arena of a process is the range of addresses from (VM_ARENA_BASEADDR) to (VM_ARENA_BASEADDR + VM_ARENA_SIZE). The arena is initialized to have no valid virtual pages. An application calls vm_extend to ask for the lowest invalid page in its arena to be declared valid. vm_extend returns the lowest-numbered byte of the newly allocated memory.
E.g., if the arena before calling vm_extend is 0x60000000-0x60003fff, the return value of the next vm_extend call will be 0x60004000, and the resulting valid part of the arena will be 0x60000000-0x60005fff. Each byte of a newly extended virtual page is defined to be initialized with the value 0. Applications can load or store to any address on a valid arena page. Depending on the protections and residencies set by the pager, some of these loads and stores will result in calls to the pager's vm_fault routine; however these faults are serviced without the application's knowledge. An application calls vm_syslog to ask the pager to print a message (all message data should be in the valid part of the arena). vm_syslog returns 0 on success and -1 on failure.
FYI, the vm_extend interface is similar to the sbrk call provided by Linux (and FreeBSD). The interface you are used to using to manage dynamic memory (new/malloc and delete/free) are
user-level libraries built on top of sbrk.
The following is a sample application program that uses the external pager.
CS 340 Milestone One Guidelines and Rubric Overview: For this assignment, you will implement the fundamental operations of create, read, update,
Retail Transaction Programming Project Project Requirements: Develop a program to emulate a purchase transaction at a retail store. This
7COM1028 Secure Systems Programming Referral Coursework: Secure
Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip
CS 340 Final Project Guidelines and Rubric Overview The final project will encompass developing a web service using a software stack and impleme