Programming Assignment 3 - Memory Management

Operating Systems, Fall 2001

Due Date
Introduction
System Calls
Interrupt Handlers
Notes
Test Device Files

Due Date

This assignment is due on Wednesday, 21 November, no later than 2:00 p.m. See the submissions page (last modified on 20 December 2001) for information about submitting your assignment.

Although you probably haven't noticed it, the simulated hardware provides programs with a luxurious 11-bit address space in which to run. Taking a 32-word disk block as the basic unit of memory management, that means a program may occupy 64 blocks. Unfortunately, user space is only 32 block long.

In this assignment, you'll be modifying your operating system to let the hardware run programs larger than 32 blocks, and you'll be doing it by implementing paged virtual memory.

System Calls

This assignment implements no new system calls.

Interrupt Handlers

This assignment modifies the invalid-address interrupt so it can determine why an invalid address occurred. A process causing an invalid-address interrupt because of a page fault should not be killed, while a process issuing an invalid address should be.

Notes

Make sure you understand the difference between virtual and physical addresses and the mechanisms for translating between the two. To help minimize pain and suffering while implementing this assignment, you should not only read Sections 11.4.2, 12.1, and 12.2 of the text, you should also understand them well enough to implement them.
To help minimize pain and suffering while completing this assignment, you should know and understand how the simulator supports virtual memory. Be sure to review the specifications for the Memory Management Unit, the process address space, and the way paging works.
The simulator default is to run user processes non-virtual, so those of you still working on assignment 2 can continue to do so without change.
Process don't change their size; a program that's n blocks long on the batch disk remains n blocks long throughout its execution.
Each batch disk will have a paging area immediately following the programs on the batch disk. The paging area of the batch disk contains the same number blocks as does the program area of the batch disk.
The invalid address interrupt handler needs to be changed to determine why an invalid address occurred. The invalid address can be found in the invalid-address register.
The operating system does not run under virtual memory; paging and address translation are disabled when the operating system is running. The operating system must explicitly perform any address translation or paging it requires.
The operating-system code should always be aware of whether an address is a virtual or a physical address. Confusing the two types of address in the operating system leads to subtle and nasty execution-time errors. Distinguishing between physical and virtual addresses is simplified by the address ranges occupied by each: a valid physical address occupies the range sys_base to dev_top - 1 (inclusive at both ends), while a valid virtual address occupies the range vmem_base to vmem_top - 1 (inclusive at both ends).
The hardware does not use virtual memory. Disks and terminals don't deal with virtual addresses, only with physical addresses. Your drivers for these devices have to perform the virtual-to-physical address translation and manage the page table appropriately.
The page table is accessed in the same way that the memory fetch() and store() routines are accesses: mass.memory->page_table.

Test Device Files

There are five disks, three involving heap sort and two involving matrix multiplication.

pa3-lheapsort.dsk - Contains one program that heap sorts an array of 1600 words. The array contains the numbers 1 through 1600 randomly shuffled; the program checks to see that the array is sorted in ascending order; that is, that array[i] = i.

cl os3 -d /export/home/class/cs-438-505/devices/pa3-lheapsort.dsk

The system is halted. 
Total execution time: 585694 ticks, idle time: 8713 ticks (1%). 

cl

If the program finds something wrong, it prints a message to std-err:

cl os3 -d /export/home/class/cs-438-505/devices/pa3-lheapsort.dsk
* * * array isn't sorted in ascending order: a[5] = 100. 

The system is halted. 
Total execution time: 405983 ticks, idle time: 3121 ticks (0%). 

cl

pa3-llheapsort.dsk - Contains two copies of the heap-sort program, each one sorting a 1200-element array:

cl os3 -d /export/home/class/cs-438-505/devices/pa3-llheapsort.dsk

The system is halted. 
Total execution time: 831828 ticks, idle time: 6721 ticks (0%). 

cl

pa3-smlheapsort.dsk - Contains three copies of the heap-sort program, one sorting a 1200-element array, one sorting a 1500 element array, and the third sorting a 1800-element array:
```
cl os3 -d /export/home/class/cs-438-505/devices/pa3-smlheapsort.dsk

The system is halted. 
Total execution time: 1666260 ticks, idle time: 57245 ticks (3%). 

cl 
```

pa3-matmul.dsk - Contains a program that multiplies two 22x22 matrices together:

cl os3 -d /export/home/class/cs-438-505/devices/pa3-matmul.dsk 

The system is halted. 
Total execution time: 179860 ticks, idle time: 3489 ticks (1%). 

cl

One of the original matrices contains random numbers, the other is the identity matrix. The program checks to make sure that the product matrix C is equal to the non-identity matrix A, printing an error message if something goes wrong:

cl os3 
* * * Matrix multiplication failed: A[0, 0] = 205 != -182 = C[0, 0]. 

The system is halted. 
Total execution time: 170509 ticks, idle time: 2099 ticks (1%). 

cl

pa3-2matmul.dsk - Contains two copies of the matrix multiplication program:
```
cl os3 -d /export/home/class/cs-438-505/devices/pa3-2matmul.dsk

The system is halted. 
Total execution time: 367585 ticks, idle time: 14611 ticks (3%). 

cl
```
My implementation of the third assignment is available in /export/home/class/cs-438-505/misc.
If you're looking looking for suggestions about how to approach this assignment, you might want to consider the following steps:
1. Starting from a working implementation of assignment 2, change the os to make the process address space virtual, but otherwise leave the os unchanged. In particular, the os will continue to load the entire program before execution, and you won't have to modify your invalid-instruction interrupt handler.
  This step familiarizes you with virtual memory and the page table. Because all a process's pages are pre-loaded before execution, no page faults occur during process execution and there is no paging activity.
2. Once the step-1 os can run all the pa1 batch disks successfully, add paging. Because all the pa1 batch disks fit in user space, the paging activity will be paging in from disk to user space; it will not be necessary to page out from user space to disk for this step.
  You will need to change your invalid-address interrupt handler to let it distinguish between invalid addresses and page faults, and to let it handle the page faults. Probably the easiest way to add paging is to make a process ready to run without reading in any of its pages; when it starts to execute, the process will page fault in its first page and you're off and running.
  This technique is known as pure demand paging. An alternative is to implement prefetch - a process needs its first page, so just read it in and avoid the page fault. Prefetch is more efficient than pure demand paging is, but it is also, in my opinion, harder to implement than pure demand paging is.
3. Once the step-2 os can run all the pa1 batch disks successfully, change the os so it can page out from user space to the disk.
  To get a good grade on this assignment, your os should be able to do at least this much.
4. Once the step-3 os can run all the pa1 batch disks, the pa1-bigpgms.dsk batch disk and pa3 batch disks, modify the os to allow user-process device i-o to work with virtual addresses.
  Once this step is completed, your os should be able to run all the batch disks.

This page last modified on 9 November 2001.