you will implement an external pager, which is a process that handles virtual memory requests for application processes.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

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:

1. 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

2. 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

3. 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.

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of