Programming Assignment 3 - Memory Management

Table of Contents

• Due Date
• Introduction
• System Calls
• Interrupt Handlers
• Notes
• Test Device Files
• Comments

Due Date

Introduction

Although you probably haven’t noticed it, the simulated hardware provides processes 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 process 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 processes larger than 32 blocks, and you’ll be doing it by implementing paged virtual memory.

System Calls

Interrupt Handlers

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 Section 3.6 of Finkel and Section 6.3 of Hailperin, 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.

Make sure you understand the virtual-storage features added to Hardware.java and PrimaryStore.java for this assignment.

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.

Processes 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 has a paging area immediately following the programs on the batch disk. The paging area is as big as it needs to be, up to the maximum size of the disk (Hardware.Disk.blockCount).

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 Hardware.Address.systemBase to Hardware.Address.deviceTop - 1 (inclusive at both ends), while a valid virtual address occupies the range Hardware.Address.virtualMemoryBase to Hardware.Address.virtualMemoryTop - 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.

Understand the additions to the interface described in PrimaryStore.java.

Test Device Files

1. pa3-2blkpgm.dsk - Contains a single, simple two-block program that does nothing.

   $ java -ea -cp /export/home/class/cs-os/pa3/pa3-YYMMDD.jar:. \
       main os-class /export/home/class/cs-os/pa3/pa3-2blkpgm.dsk
   
   The system is halted.
   Total execution time:  97 ticks, idle time:  29 ticks (29%).
   
   $ 
   

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

   $ java -ea -cp /export/home/class/cs-os/pa3/pa3-YYMMDD.jar:. \
       main os-class /export/home/class/cs-os/pa3/pa3-lheapsort.dsk
   
   The system is halted.
   Total execution time:  585694 ticks, idle time:  8713 ticks (1%).
   
   $ 
   

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

   $ java -ea -cp /export/home/class/cs-os/pa3/pa3-YYMMDD.jar:. \
       main os-class /export/home/class/cs-os/pa3/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%). 
   
   $ 
   

   If there are no error messages, everything’s fine.

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

   $ java -ea -cp /export/home/class/cs-os/pa3/pa3-YYMMDD.jar:. \
       main os-class /export/home/class/cs-os/pa3/pa3-llheapsort.dsk
   
   The system is halted.
   Total execution time:  835592 ticks, idle time:  10475 ticks (1%).
   
   $
   

   Each program checks its answer and prints an error message if it finds anything wrong; no error messages, no problems.

4. 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:

   $ java -ea -cp /export/home/class/cs-os/pa3/pa3-YYMMDD.jar:. \
       main os-class /export/home/class/cs-os/pa3/pa3-smlheapsort.dsk
   
   The system is halted.
   Total execution time:  1666302 ticks, idle time:  57283 ticks (3%).
   
   $
   

   Each program checks its answer and prints an error message if it finds anything wrong; no error messages, no problems.

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

   $ java -ea -cp /export/home/class/cs-os/pa3/pa3-YYMMDD.jar:. \
       main os-class /export/home/class/cs-os/pa3/pa3-matmul.dsk
   
   The system is halted.
   Total execution time:  179860 ticks, idle time:  3489 ticks (1%).
   
   $ 
   

   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:

   $ java -ea -cp /export/home/class/cs-os/pa3/pa3-YYMMDD.jar:. \
       main os-class /export/home/class/cs-os/pa3/pa3-matmul.dsk
   * * * 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%). 
   
   $ 
   

6. pa3-2matmul.dsk - Contains two copies of the matrix multiplication program:

   $ java -ea -cp /export/home/class/cs-os/pa3/pa3-YYMMDD.jar:. \
       main os-class /export/home/class/cs-os/pa3/pa3-2matmul.dsk
   
   The system is halted. 
   Total execution time:  369665 ticks, idle time:  16677 ticks (4%).
   
   $
   

Comments

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.

   The changes involved are setting-up and managing the page table correctly, and setting the top, bottom, program-counter and status registers properly. 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.

   Some of the code added during this step (such as for page-table management) will be kept, but other code (such as allocating process segments) will have to be abandoned in step 4.

2. Get the step-1 os to run all the pa1 batch disks successfully.
3. Modify the your device drivers do the physical-virtual address mapping on I-O, and get the pa2 batch disks to run.
4. 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.

   You might be tempted to coast on the work done in step 1, but you won't be able to. Many of the programs in the pa3 disks contain programs larger than user space, and full paging will be necessary to execute the processes based on those programs.

   To get a good grade on this assignment, your os should be able to do at least this much.

5. Once the step-4 os can run all the pa1 and pa2 batch disks successfully, change the os so it can page out from user space to the disk. Get pa3-matmul.dsk working correctly.

   Once your os runs pa3-matmul.dsk, it should be able to handle all the pa3 disks.