EE469 Spring 2004 Lab 4: Memory Management

Due: Thursday, April 8 Midnight

Introduction

The goal of this project is to extend DLXOS memory management subsystem to support dynamic one-level page paging, dynamic two-level paging and heap management. The project is divided into three parts.

PART ONE: Dynamic one-level paging (30 points)

In this part you will implement dynamic one-level paging.

DLXOS currently supports a static one-level page table, which allocates a single 64KB page (for all of the code, data and the stack segment) per process. This page is allocated when the process is first created. The total amount of physical memory present in DLXSIM is 2 MB. Extend the current implementation to support dynamic one-level page tables. The system should totally support 512 pages of 4 KB each. The virtual address space of each process is limited to 512 KB. During the process creation only the necessary physical pages (3 pages for text & data, one page for user stack) are allocated. The rest of the physical pages are dynamically allocated when a page fault occurs. Once a physical page is allocated, it is not freed. A process can use at most 32 physical pages (including the 4 pages allocated for text, data and user stack) during its execution. The kernel kills a process, if it exceeds the 32 page physical memory limit and displays an informative error message.

Modify the constants MEMORY_L1_PAGE_SIZE_BITS and MEMORY_L2_PAGE_SIZE_BITS appropriately.

See notes below for more details.

Do your implementation in "lab4_q1" directory

PART TWO: Dynamic two-level paging (40 points)

In this part you will implement dynamic two level paging.

Extend the one-level dynamic page table implementation to support two-level dynamic page table. The virtual address space of each process is limited to 16MB. Any virtual address referenced by a process is translated to a physical address using the two-level page table. Each L1 (Level-1) page table entry refers to an L2(Level-2) page table and each L2 page table entry points to a 8KB page.  Each process can use at most 1 MB of physical memory during its execution (this includes the pages being used for code & data, user stack, and L2 page tables). The kernel kills a process, if it exceeds the 1MB physical memory limit, and displays an informative error message.

Each L1 page table entry corresponds to 512 KB. If a particular entry in L1 table does not exist, that entry should be zero. L2 page table entries point to real physical pages in memory. In addition to the physical page address, there are three special bits in each PTE: valid, dirty, and reference bits. The valid bit must be set by the operating system to indicate that the page in memory is valid. The dirty and reference bits are set by the "hardware" when an address in the page is modified and accessed (read or written), respectively. The bits are never reset by the "hardware", but they may be reset by the OS if desired.

In order to activate two-level page tables, modify the constants MEMORY_L1_PAGE_SIZE_BITS and MEMORY_L2_PAGE_SIZE_BITS appropriately.

To simulate 16MB of physical memory, you need to add the flag '-m 16777216' as shown below:
dlxsim -m 16777216 -x os.dlx.obj -a -u userprog.dlx.obj.

See notes below for more details.

Do your implementation in "lab4_q2" directory.

Notes for PART ONE and PART TWO

• When a process is created, it will need 3 pages for its code and data segment, one page for the user stack and one page for the system stack. The user stack should always be initialized to the last page in the virtual address space of a process.  
• The highest virtual address space for a process is defined as TOP_VIRTUAL_ADDRESS_SPACE in memory.h. You will need to change that because the user stack pointer initialization is dependent upon that. You can find the dependency by looking at ProcessFork().
• The page table for each process in current version of DLXOS has only 16 entries. You should adjust this value depending on the number of L1 page table entries in PART ONE and PART TWO.
• A TRAP_PAGEFAULT trap is generated when a process tries to access an invalid address. Create a "page fault handler" and call it in the case of TRAP_PAGEFAULT. The page-fault handler first needs to find the faulting address (look at PROCESS_STACK_FAULT in process.h). After loading the missing page and fixing the page tables, return from the page fault handler.
• A TRAP_ACCESS trap is generated when a process tries to access beyond its virtual address space limit. The current implementation causes the simulator to exit when this trap is generated. Modify the trap functionality so that only the process is killed and the simulator does not exit.
• When a process exits, all physical pages allocated to a process need to be freed (in case of two-level paging free the pages used for L2 page tables also).  
• You may look at the function CPU: VaddrToPaddr in dlxsim.cc to see how virtual address to physical address translation is done.
• If the pagefault handler successfully allocates a physical page, make sure to print the page faulting address inside the handler. This should be of the following form: "Process id .., page fault address: 0x........, physical page number allocated: ....".
• When a process is killed or when a process exits, you should print all the physical page numbers being freed. This should be of the following form: "process id ..,, virtual page base address: 0x......., Freeing physical page number: .., "
• All virtual page addresses should be displayed in %x (hexadecimal) format. All physical page numbers should be displayed in %d (decimal) format.
• MemoryTranslateUserToSystem( ): This procedure is used to translate user addresses into system addresses. The current implementation supports only static one-level page tables. Modify it to handle both one-level and two-level page tables.
• ProcessKill(PCB * pcb): This system call should release all the resources (i.e. all physical pages) held by the process and then remove its context. You should implement ProcessKill() both in PART ONE and PART TWO. You will need to use the function ProcessFreeResources()  already defined in process.c. You will need to change the implementation of ProcessFreeResources() for all three parts of this project appropriately

Test Cases:

You have been provided with test cases userprog1.c, userprog2.c, and userprog3.c. Use userprog1.cand userprog2.c to test PART 1, and userprog3.c to test PART 2. To run a test case, type “dlxsim -x os.dlx.obj -a -u userprog.dlx.obj [testcaseid]” in the execs directory. Testcaseid is the number of test case that you want to run. See userprog.c for details. Remember to add –m 16777216 for PART 2. Also beware that these test cases only test minimal functionality and for grading purposes, we may use several other test cases as well. You may write your own test cases to check your implementation.

PART THREE: Heap Management (30 points)

In this part, you will extend DLXOS to support heap management using the one-level paging implemented in Part One.
Heap is used for dynamic memory management in process space. Some portion of process’s address space is pre-allocated as the process heap. The heap always grows from a lower address to a higher address (different from the stack). When a process dynamically requests some memory by performing a malloc() call, the OS scans through all the free space in the heap and tries to find an area at least as large as the requested size. Freeing the heap space is the responsibility of process.  
Assume a heap size of 1 page for this part. Implement the heap management by pre-allocating 1 page for heap at the time of process creation for the one-level paging implemented in Part One. Note that this page is in addition to the 4 pages that you allocated for code, data and user stack.

The following system calls have to be implemented.

void *malloc(int memsize): malloc( ) allocates memory block of size memsize in the heap space and returns a pointer that corresponds to the starting virtual address of the allocated block. malloc() allocates blocks having sizes in multiples of 4 bytes e.g. if memsize is 7 bytes, the allocated heap block will have a size of 8 bytes.

Return Values:
 -    On success, the starting virtual address of allocated heap space is returned.  
 -    On failure NULL is returned, and no memory allocation is performed. The following conditions result in failure.

1. memsize requested is less than or equal to zero.
2. memsize is greater than the total heap size.
3. There is no free heap block large enough to accommodate memsize bytes.

Output:
If the call is successful, output the virtual address and the physical address of the allocated heap space. It should look like the following :
                "Created a heap block of size <memsize> bytes: virtual address <vaddress>, physical address <paddress>."       

int mfree(void *ptr): mfree() frees the heap block identified by ptr. The caller does not specify the size of heap block to be freed. (HINT: malloc() must keep track of the size of heap block before allocating the block). After freeing the block, mfree() should see whether there are any free block(s) adjacent to this newly-freed heap block. If such block(s) exist, the newly-freed heap block should be merged with adjacent free block(s) to create a larger free block.

Return Values:
-    On success the number of bytes freed is returned.
-    On failure -1 is returned. The following conditions result in failure:

1 ptr is NULL.

2 ptr does not belong to the heap space

Output:
If the call is successful, output the virtual and physical address of the memory, and the number of bytes being freed. It should look like the following:
" Freeing <nbytes> bytes in heap space, virtual address <vaddress> physical address <paddress>".

Do your implementation in "lab4_q3" directory. Note that PART 3 builds on top of PART 1. So you will need to copy your implementation of PART 1 in lab4_q3 directory before you start implementing PART 3. No test case has been provided for PART 3.

Notes for PART THREE

· The limit on a process to use at most 32 physical pages during its execution includes the page being used for the heap

• When a process exits or is killed, all physical pages allocated to a process need to be freed. These pages include the page allocated for the heap.
• You will need to keep track of the location and size of free blocks in the heap. The free blocks can be arranged as a linked list.
• As mentioned in the HINT in the description of mfree(), there will be some space overhead in each allocated block. Because the size of the allocated block will be stored as an integer, the actual space occupied by the allocated block will be 4 bytes larger than the size requested in the malloc() call. Therefore the maximum number of bytes requested in malloc() can be 4096-4=4092 bytes (Remember that the total heap size is 1 page, which is 4096 bytes).

Turning in

Copy /home/shay/g/ee469/labs/common/lab4.tar to your lab directory. After you untar it (tar xvf), it will becomes lab4. Make three separate directories for your code and call them lab4_q1, lab4_q2, and lab4_q3. All your modifications have to be saved in these directories and only these directories should be turned in by

turnin -c ee469 -p labX-Y lab4_q1 lab4_q2 lab4_q3

lab4_q1: your directory containing solutions for part 1

lab4_q2: your directory containing solutions for question 2

lab4_q3: your directory containing solutions for question 3

Please include all the files you have used to build your project: source code, Makefiles, and any other scripts you may have used. In addition, please include a README file in each directory to explain anything unusual to the TA - testing procedures, etc.

Your solution should only print out only what was specified in the assignment. i.e. it should not contain any debug printf statements. Not following this rule will results in points deduction by the TA.

Make sure that each of the directories that you turn in contains an appropriate Makefile. The Makefile should be written in such a way that after typing make in the problem directory, all the executables will automatically be produced. So the Makefile for q2 should be written in such a way that after typing make in the directory q2, it should make all the executables (including os.dlx.obj, userprog.dlx.obj, and any other programs that you wrote. If you do not know how to write a makefile, ask your TA.

IMPORTANT: do NOT submit object files or other files generated by the DLX compiler or assembler. Every file in the directory that could be generated automatically by the DLX compiler or assembler will result in a warning from your TA or a 5-point deduction from your project grade. To do so, you should do 'make clean' before you turn in.