1. Due Dates and Mark Distribution

Due Date: 23:59, Friday 6th June

Extension Date: 23:59, Monday 9th June

Marks: The base assignment is worth 30 marks (of the 100 available for the class mark component of the course)

The 10% bonus for one week early applies.

The advanced assignment is assessable for COMP3891/COMP9283 students. Only a subset of the advanced assignment is required. Marks are capped at 5 marks of the 100 class marks available. The paging component is for extra bonus marks only.

COMP3231/COMP9201 students can do the advanced part with the permission of the lecturer, and only if basic assignment is completed a week prior to the deadline. Marks obtained are added to any shortfall in the participation mark component. The bonus marks are also available.

Any bonus awarded for the advanced part can be used to make up for lost marks in any class mark component of the course.

The familiarisation questions contained herein are the subject of your week 11 tutorial. Please answer the questions and bring them to your tutorial.

Note: As noted in previous email and announcements, there is a video outline of how to approach the assignment in the week 11 extended lecture.

2. Introduction

If you attempt the advanced portion of this assignment, you will implement paging, the mechanism by which memory pages of an active process can be sent to disk when memory is needed, and restored to memory when required by the program.

The System/161 TLB

• global: 1 bit; if set, ignore the PID bits in the TLB.
• valid: 1 bit; set if the TLB entry contains a valid translation.
• dirty: 1 bit; enables writing to the page referenced by the entry; if this bit is 0, the page is only accessible for reading.
• nocache: 1 bit; unused in System/161. In a real processor, indicates that the hardware cache will be disabled when accessing this page.
• pid: 6 bits; a context or address space ID that can be used to allow entries to remain in the TLB after a context switch.

For this assignment, you may ignore the pid field. Note, however, that you must then flush the TLB on a context switch (why?).

The System/161 Virtual Address Space Map

• kseg2, TLB-mapped cacheable kernel space
• kseg1, direct-mapped uncached kernel space
• kseg0, direct-mapped cached kernel space
• kuseg, TLB-mapped cacheable user space

The top of kuseg is 0x80000000. The top of kseg0 is 0xa0000000, and the top of kseg1 is 0xc0000000.

The memory map thus looks like this:

Address	Segment	Special properties
0xffffffff	kseg2
0xc0000000
0xbfffffff	kseg1
0xbfc00180		Exception address if BEV set.
0xbfc00100		UTLB exception address if BEV set.
0xbfc00000		Execution begins here after processor reset.
0xa0000000
0x9fffffff	kseg0
0x80000080		Exception address if BEV not set.
0x80000000		UTLB exception address if BEV not set.
0x7fffffff	kuseg
0x00000000

3. Setting Up Assignment 3

You will (again) be setting up the SVN repository that will contain your code. Remember to use a 3231 subshell (or continue using your modified PATH) for this assignment, as outlined in ASST0.

Only one of you needs to do the following. We suggest your partner sit in on this part of the assignment.

Check your umask is still set appropriately.

% umask
0007

Now import the assignment sources.

% cd /home/cs3231/assigns
% svn import asst3/src file:///home/osprjXXX/repo/asst3/trunk -m "Initial import"

Make an immediate branch of this import for easy reference when you generate your diff:

% svn copy -m "Tag initial import" file:///home/osprjXXX/repo/asst3/trunk file:///home/osprjXXX/repo/asst3/initial

You have now completed setting up a shared repository for both partners.

Checking out a working copy

We'll assume from your cs3231 directory is intact from the previous assignment. Change to your directory.

% cd ~/cs3231

Now checkout a copy of the os161 sources to work on from your shared repository.

% svn checkout file:///home/osprjXXX/repo/asst3/trunk asst3-src

You should now have a asst3-src directory to work on.

4. Tutorial Exercises

5. Coding Assignment

Like previous assignments, you are required to submit a small design doc that identifies the major issues you tackled in this assignment, and also describes your solutions to these issues.

The document will be used to guide our markers in their evaluation of your solution to the assignment. In the case of a poor results in the functional testing combined with a poor design document, we will base our assessment on these components alone. If you can't describe your own solution clearly, you can't expect us to reverse engineer the code to a poor and complex solution to the assignment.

Place your design document in design.txt (which we have created for you) at the top of the source tree to OS/161 (i.e. in ~/cs3231/asst3-src/design.txt).

When you later commit your changes into your repository, your design doc will be included in the commit, and later in your submission.

Also, please word wrap you design doc if your have not already done so. You can use the unix fmt command to achieve this if your editor cannot.

Memory Management

You will need a frametable containing information about the memory available in the system. In the basic assignment you will need to keep track of whether a frame is used or not. In the advanced part, you will need to keep track of reference statistics and other information about the frames.

The functions that deal with memory are described in kern/include/vm.h. You may assume that only one page will be allocated at a time—designing a page allocator that can allocate multiple pages at a time is surprisingly tricky. However, make sure that you never allocate memory (though kmalloc) that is larger than a page!

Note that alloc_kpages() should return the virtual address of the page, i.e., an address in kseg0.

Warning: alloc_kpages() can be called before vm_bootstrap(). The means that your implementation of alloc_kpages() must work before your frametable is initialised. You should just call ram_stealmem() if the frametable hasn't been initialised.

Address Space Management

You may use a fixed-size stack region (say 16 pages) for each process.

Address Translation

Note that a hierarchical page table is a lazy data-structure. This means that the contents of the page table, including the second level pages, are only allocated when they are needed. You may find allocating the required pages at load time helps you start your assignment, however, your final solution should allocate pages only when a page-fault occurs.

The following questions may assist you in designing the contents of your page table

• What information do you need to store for each page?
• How does the page table get populated?

Testing and Debugging Your Assignment

Apart from GDB, you may also find the trace161 command useful. trace161 will run the simulator with tracing, for example

% trace161 -t t -f outfile kernel

Hints

One approach to implementing the assignment is in the following order:

1. Understand how a page table works, and its relationship with the TLB.
2. Understand the specification and the supplied code.
3. Work out a basic design for you implementation.
   You might start simply by using a different data structure initially to keep your code and data structures simple.
4. Implement the TLB exception handlers in vm.c using this simplified page table. Note, your final solution should use a 2-level page table!
5. Implement the functions in kern/vm/addrspace.c that are required for basic functionality (e.g. as_create(), as_prepare_load(), etc.). Allocating user pages in as_define_region() may also simplify your assignment.
6. Test and debug this. Use the debugger!
   If you really get stuck, submit at least this much of the solution, and you should get some marks for it.
7. Understand how the page table works.
8. Decide exactly what data structures you need.
9. Work out the design for the proper solution, using the 2-level page table.
10. Modify your implementation to include the 2-level page table.
11. Write routines in kern/vm/frametable.c to manage free frames and copy pages. Modify kern/vm/vm.c to create and delete page table entries, and keep the TLB consistent with the page table.
12. Use these routines to finish the functions in kern/vm/addrspace.c.
13. Test and debug.

Alternatively, one could start on the frame table, and alloc_kpage() and free_kpage(). Note that alloc_kpage() and free_kpage() are the underlying routines used kmalloc() and kfree(), so ensure your implementation is correct. A broken alloc_kpage() will result in a broken kmalloc() and an unpredicably broken OS/161!

6. Basic Assignment Submission

You should first commit your changes back to the repository using the following command. Note: You will have to supply a comment on your changes. You also need to coordinate with your partner that the changes you have (or potentially both have) made are committed consistently by you and your partner, such that the repository contains the work you want from both partners.

% cd ~/cs3231/asst3-src
% svn commit

The above command will commit any changes you have made to your shared repository.

Now generate a .diff

% svn diff file:///home/osprjXXX/repo/asst3/initial file:///home/osprjXXX/repo/asst3/trunk >~/asst3.diff

Beware! If you have created new files for this assignment, they will not be included in your submission unless you add them, using svn add:

% svn add filename.c

Testing Your Submission

7. Advanced Assignment

COMP3231/COMP9201 students can do the advanced part with the permission of the lecturer, and only if basic assignment is completed a week prior to the deadline. Marks obtained are added to any shortfall in the participation mark component. The limited bonus marks are also available.

• (easy) 3 marks Shared pages and copy-on-write.
• (easy) 2 marks Implement sbrk() to enable user-level malloc() to function.
• (hard) 5 marks.
  • Implement a simplified mmap() and munmap(). Note: you only need to support the simplified case of mapping a file, and munmap() the entire region that was mapped. The prototypes are expected to be

    void *mmap(size_t length, int prot, int fd, off_t offset);
    int munmap(void *addr);
    	

    Where prot can be PROT_READ and/or PROT_WRITE. Compared to traditional mmap, there are no flags, and the OS chooses the virtual address to locate the region. You must ensure that applications can open a file, updated it, and have the updated file propagate to the filesystem.
  • And, implement demand-loading. You should load pages only when they are referenced by the user process, as opposed to at process creation.
• Bonus section. (harder) 3 marks Implement paging. You should implement some page replacement algorithm and demonstrate your solution running under memory pressure.

Advanced Assignment Submission

Submission for the advanced assignment is similar to the basic assignment, except the advance component is given to a distinguished assignment name: asst3_adv Again, you need to generate a diff based on the original source tree.

% cd ~/cs3231/asst3-src
% svn commit

Now generate a file containing the diff. (NOTE: How this works depends on how you have set up branches in svn.)

% cd ~
% svn diff file:///home/osprjXXX/repo/asst3/initial file:///home/osprjXXX/repo/asst3/adv >~/asst3_adv.diff

% cd ~
% give cs3231 asst3_adv asst3_adv.diff

You're now done.

FAQ and Gotchas