Due Date: 11:59pm (23:59), Friday, 5th of June (Week 12)
The late-penalty will begin to be applied from Tuesday 8am
(08:00), 9th of June.
The hard deadline for acceptance of late assignments is Friday
11:59pm, Friday, 12th of June
Worth 30 marks (of the 100 available for the class mark
component of the course)
The 10% bonus for one week early applies
The extra 5% bonus for a submitted, working assignment within 48 hours of
release, also applies
See course intro for exact details. The notional release time is
midnight, Monday, 18th of May
Up to a 20% bonus is available for the advanced part of the
To attempt the advanced part, you must finish the standard assignment
at least one week early, and get permission from Kevin.
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 9 tutorial. Please answer the questions and bring them to
In this assignment you will implement the virtual memory sub-system of
OS/161. The existing VM implementation in OS/161, dumbvm,
is a minimal implementation with a number of shortcomings. In this
assignment you will adapt OS/161 to take full advantage of the
simulated hardware by implementing management of the MIPS
software-managed Translation Lookaside Buffer (TLB). You will write
the code to manage this TLB. You will also write code to manage
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
In the System/161 machine, each TLB entry includes a 20-bit virtual
page number and a 20-bit physical page number as well as the following
All these bits/values are maintained by the operating system. When the
valid bit is set, the TLB entry contains a valid translation. This
implies that the virtual page is present in physical memory. A TLB
miss occurs when no TLB entry can be found with a matching virtual
page and address space ID (unless the global bit is set in which case
the address space ID is ignored) and a valid bit that is set.
- 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.
- ASID: 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 ASID field. Note,
however, that you must then flush the TLB on a context switch in your
implementation of as_activate() (why?).
The System/161 Virtual Address Space Map
The MIPS divides its address space into several regions that have
hardwired properties. These are:
Both direct-mapped segments map to the first 512 megabytes of the
physical address space.
- 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:
||Exception address if BEV set.
||UTLB exception address if BEV set.
||Execution begins here after processor reset.
||Exception address if BEV not set.
||UTLB exception address if BEV not set.
Setting Up Assignment 3
Remember to use a 3231 subshell (or continue using your
modified PATH) for this assignment, as outlined in ASST0.
In this section, you will (again) be setting up the SVN repository
that will contain your code. 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.
If not, you have done something wrong with your umask setup and need
to fix it.
- 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
Checking out a working copy
You have now completed setting up a shared repository for both
partners. The following instructions are now for both partners.
You will need to increase the amount of physical memory to run some of
the provided tests. Update ~/cs3231/root/sys161.conf so that the
ramsize is as follows
31 busctl ramsize=16777216
Or, download a fresh, appropriately configured, version from here, and install it.
Configure OS/161 for Assignment 3
Remember to set your PATH environment variable as in
previous assignments (e.g. run the 3231 command).
Before proceeding further, configure your new sources, and build
and install the user-level libraries and binaries.
% cd ~/cs3231/asst3-src
You have to reconfigure your kernel before you can use the
framework provided to do this assignment. The procedure for
configuring a kernel is the same as before, except you will use the
ASST3 configuration file:
% cd ~/cs3231/asst3-src/kern/conf
% ./config ASST3
You should now see an ASST3 directory in the compile directory.
Building for ASST3
When you built OS/161 for ASST1, you ran make from compile/ASST1 . When you built for ASST2, you ran make from compile/ASST2 ... you can probably see where this is heading:
% cd ../compile/ASST3
% make depend
% make install
If you now run the kernel as you did for previous assignments, you
should get to the menu prompt. If you try and run a program, the
kernel should panic with a message about "unimplemented feature"
(this message is coming from a function in kern/vm/addrspace.c).
For example, run p /bin/true at the OS/161
prompt to run the program /bin/true in
You are now ready to start the assignment.
Please answer the following questions and bring them to your tutorial
in week 12. You should be familiar enough with navigating the kernel
source that you can find the answers to the below questions by yourself
(Hint: use the grep utility). You may also find the
MIPS r3000 reference useful.
1. What is the difference between the different MIPS address space
segments? What is the use of each segment?
2. What functions exist to help you manage the TLB? Describe their
use. (Hint: look in kern/arch/mips/include/tlb.h)
3. What macros are used to convert from a physical address to a kernel
4. What address should the initial user stack pointer be?
5. What are the entryhi and entrylo co-processor
registers? Describe their contents.
6. What do the as_* functions do? Why do we need as_prepare_load() and as_complete_load()?
7. What does vm_fault do? When is it called?
8. Assuming an inverted page table (IPT) with 4k pages, show for the
following virtual addresses:
The page table is initially empty, with no L2 pages. You may assume
that the allocator returns frames in order, so that the first frame
allocated is frame 0, then frames 1, 2, 3, etc.
- The page number and offset;
- the translated address (after any page allocation); and
- the contents of the page table after the TLB miss.
This assignment involves designing and implementing a number of
data-structures. Before you start, you should work out what data you
need to keep track of, and what operations are required.
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.
Create your design document to the top of the source tree to
OS/161 (~/cs3231/asst3-src), and include it in SVN as follows.
% cd ~/cs3231/asst3-src
% svn add design.txt
When you later commit your changes into your repository, your
design doc will be included in the commit, and later in your
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.
This assignment requires you to keep track of physical memory. The
current memory management implementation in dumbvm never frees memory;
your implementation should handle both allocation and freeing of
You will need book keeping 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. For an IPT, you do not need an
additional data structure to store this book keeping. You can use the
collision chain link field in the inverted page table to link together
free frames. In the advanced part, you will need to keep track of
reference statistics and other information about the frames, and also
will need to modify the IPT to support sharing.
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 IPT is
initialised. You should just call ram_stealmem() if the
IPT hasn't been initialised.
Address Space Management
OS/161 has an address space abstraction, the struct
addrspace. To enable OS/161 to interact with your VM
implementation, you will need to fill in the functions in
kern/vm/addrspace.c, The semantics of these functions is
documented in kern/include/addrspace.h.
You may use a fixed-size stack region (say 16 pages) for each
The main goal for this assignment is to provide virtual memory
translation for user programs. To do this, you will need to implement
a TLB refill handler. You will also need to implement a page table.
For this assignment, you will implement a inverted page
Note that a page table is a lazy
data-structure. This means that the contents of the page table
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
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
To test this assignment, you should run a process that requires more
virtual memory than the TLB can map at any one time. You should also
ensure that touching memory not in a valid region will raise an
exception. The huge and faulter tests in
testbin may be useful.
Apart from GDB, you may also find the trace161 command
useful. trace161 will run the simulator with tracing, for
% trace161 -t t -f outfile kernel
will record all TLB accesses in outfile.
Have a close look at the dumbvm implementation, especially
vm_fault(). Although it is simple, you should get an idea on
how to approach the rest of the assignment.
For the IPT, you will need some kind of process ID to distinguish
between page table entries in the IPT for the current process, and
those belonging to other processes. We suggest you use the address of the
address space structure (struct addrspace) as the PID. The
current process's address space is available via
pid = (unsigned int) curthread->t_vmspace.
We suggest you implement the assignment in the following order:
- Understand how a page table works, and its relationship with the TLB.
- Understand the specification and the supplied code.
- Work out a basic design for you implementation.
Start simple: assume a small address space. This means you can use a
simple, static array as the page table, and can keep you code and data
Implement the TLB exception handlers in vm.c using this simplified
page table. Note, your final solution should use an IPT!
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.
- 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.
- Understand how the page table works.
- Decide exactly what data structures you need.
- Work out the design for the proper solution, using the IPT.
- Modify your implementation to include the IPT.
- Write routines in kern/vm/ipt.c to manage free
frames and copy pages. Modify
kern/arch/mips/mips/vm.c to create and delete page table
entries, and keep the TLB consistent with the page table.
- Use these routines to finish the functions in
- Test and debug.
Basic Assignment Submission
As with the previous assignments, you again will be submitting a .diff file containing your solution.
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
% cd ~
% svn diff file:///home/osprjXXX/repo/asst3/initial
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
If you add files after running svn commit, you will need to run svn commit again.
Testing Your Submission
for information on testing and resubmitting your assignment.
Submitting Your Assignment
Now submit the diff as your assignment.
% cd ~
% give cs3231 asst3 asst3.diff
You're now done.
Even though the generated .diff file should represent all the
changes you have made to the supplied code, occasionally students do
something "ingenious" and generate non representative output.
We strongly suggest keeping your checkout intact to allow
for recovery of your work if need be.
Students who wish to attempt the advanced part of this assignment may
gain up to an extra 6 marks (20%) for one (or multiple) of the
- (easy) Shared pages and copy-on-write.
- (hard) Implement mmap() and related system calls.
- (hard) Implement demand-loading. You should load pages only when
they are referenced by the user process, as opposed to at
- (harder) 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
As for the basic assignment, you need to generate a .diff file. Make sure you and your partner have recorded all changes and committed them to the repository in your group (/home/osprjXXX) directory. Then create a .diff file -- note the different name:
% cd ~
% svn diff file:///home/osprjXXX/repo/asst3/initial
Submit your solution:
% cd ~
% give cs3231 asst3_adv asst3_adv.diff
You're now done.