CIS 657 Programming Assignment 2

 

Submit two files:

Create your Assignment 2 document (doc or pdf), follow the instruction and then submit it to the Turnitin link on the blackboard (under Assignments).

oYou can submit multiple times before the due.

oAfter the due, you cannot resubmit newer version.

Do a “make clean” in code/build.linux, then compress your Nachos folder on the VM, download the compressed file into your local machine and name the compressed file Ass2_yourNetId.zip (Note: Zip only!!). Submit the zipped file to the Assignment Code Submission link of Blackboard.

oYou need to submit the entire nachos directory

We will build and run your nachos, not individual files

oUse naming convention

oWhen we uncompress your zip file, we want to see your nachos like

\Ass1_netid

\code

\threads

\machine

…

Do not change compiler option in Makefile

You have to make sure your submission is correctly made

oIf you don’t have a confirm email, you should check again.

You should raise an appeal within a week after grade is posted.

Due: November  11 (Monday, end of the day)

Late submission: you will have 2d penalty of your late days. If you submit your files on different days, later day will be considered.

 

 

Follow the Lab1 instruction and create a new fresh Nachos folder

 

Overview

Up to now, all the code you have written has been part of the kernel. In a real operating system, the kernel not only uses its procedures internally, but allows user-level programs to access some of its routines via “system calls”. Since Nachos executes MIPS instructions, these user programs must be compiled into MIPS format using the cross compiler (that’s why we build and run Nachos on the VM) The user programs need to be written in C using the system calls you implement, and located under ~/test directory. There are several example programs provided, including halt, shell, etc. The command “./nachos -x ../test/prog” will load the program “prog” to Nachos memory (physical frames) and run it on Nachos.

In this project, you will investigate the TLB, the Virtual Memory System, and Swapping space (or disk/file system). You need to design your own Virtual Memory System and get it working. You will have the freedom to choose how to create address space, how to do address translation, how to handle TLB miss, how to handle Page fault, how to represent the swap space, how to implement paging, etc. You need to prove why your choices are reasonable in terms of handling TLB miss, minimizing the number of page faults, simplicity, etc. There is no “correct” or “perfect” solution.

TLB is used to speed address translation. Given a memory address, the processor first looks in the TLB. If it finds a match (TLB hit), translation is done. If not (TLB miss), page tables (the inverted page table in our case) will be used. A TLB miss causes a trap to OS kernel, which does the address translation, loads the mapping entry to the TLB, and starts the program again.

Physical memory is used as a cache for disk to provide the abstraction of an (almost) unlimited virtual memory size. For this assignment, page translation allows us the flexibility to get pages from your choice of backing store as they are needed. Each entry in the TLB has a valid bit: if the valid bit is set, the virtual page is in memory. If the valid bit is clear or if the virtual page is not found in the TLB, software translation is needed to tell whether the page is in memory (with the TLB to be loaded with the translation), or the page must be brought in from backing store. The reference (use) bit and dirty bit are set whenever the page is reference and modified.

Caching performance depends on the policy used to decide which things are kept in memory. On a page fault, the kernel must decide which page to replace. 

 

 

 

Task 1 (25%) Implement system calls and exception handling for user programs: userprog/syscall.h defines the system call prototypes of Nachos. These are kernel procedures that user programs can invoke. You need to implement the system calls: halt(already done), Fork, Exit, Exec, Read, and Write.

Read and Write for console read and write, not for file read and write. 

oWe’re faking these, therefore Write syscall always writes to the screen. This system calls take three arguments: a char* buffer, an int size, and an OpenFileId. Since we’re faking and not utilizing the Nachos console system, we can ignore the OpenFileId parameter. You need to obtain the first two arguments from the user program. Refer to the comments in exception.cc for hints on how to obtain the parameter values.

oCan be tested with a single user program

Implement Fork system call. Fork() create a child process (Nachos Thread) and return SpaceId

Implement Exec system call. Exec() takes one string argument that is the file name of a user program. The way Exec() creates threads is similar to what you did for the -x flag in Task 2. When a user program calls Exec(), Nachos kernel creates a new thread for the executable file name given as the argument for Exec(). Nachos creates address space, initializes states and registers, and jumps to user level, as is done in RunUserProg(). Exec() also needs to return a SpaceId (defined in syscall.h) of the new thread, which can be used as the argument of Join(). 

oSpaceId id = Exec("../test/prog");

Must copy the filename argument from user memory to kernel memory safely

oRefer to the comments in exception.cc for hints on how to return a value from system call.

oThis should be tested with Memory Manager.

Exit() can be implemented with a simple call to Thread::Finish().

oBut you have to be careful. All resources including AddrSpace must be returned/freed.

oThe kernel handles an Exit system call by destroying the process (Nachos Thread) data structures and thread(s), reclaiming any memory assigned to the process

oNo return value

You need to protect the Nachos kernel from user program errors.

oUser programs can do nothing to crash the operating system except “halt” system call.

For this task, syscall.h, exception.cc, start.s (assembly routine for system calls and under test/ directory), and scheduler.cc must be modified. The userprog/exception.cc implements the handlers for system calls and other user-level exceptions. In the original file, only the Halt() system call is supported.

oHint: you can find a good example from system call Add.

 

Task 2 (20%) Implement multiprogramming: the original Nachos code is restricted to running one user program at a time. You need to come up with a way of allocating physical memory frames so multiple programs can be loaded into the machine’s memory, and provide a way of copying data from/to the user’s virtual address space (this task is highly related to the Task 3).

when the ‘-x’ flag is used, the ‘main’ function of Nachos calls the RunUserProg() function with the string following ‘-x’ as parameter. Remember that every user program should have its own thread structure, but for now there’s only one thread, the ‘main’ thread.

./nachos -x ../test/prog1 -x ../test/prog2 -x …

 

What this means is that when you type this command, Nachos will load multiple user programs into its main memory and start executing them as threads with round-robin scheduling.

oUse -quantum option for setting different time slice quantum for round-robin 

In order to test this task, you need to implement a memory manager of Task 3 or at least linear (contiguous) memory allocation for multi-programming

oKeep track of which frames are free and which are in use

oAllow multiple processes (Nachos Threads) to be resident in the physical memory at the same time

oNew AddrSpace object per user program creation

oWhen the user process (Nachos Thread) is destroyed, release the allocated page frames and AddrSpace object

 

Task 3 (50%) Implement Memory Manager (Virtual Memory) with software TLB: how to create address space for user programs and put them all in the physical memory without overlapping is the main issue in this Virtual Memory task. If you run matmul or sort program now, you’ll get an assertion failure in userprog/addrspace.cc because there’s not enough memory to load it. So what you need to accomplish is to create a virtual address space (size can be unlimited), let Nachos run the program with part of the address space loaded, and load the other part(s) when they are accessed. 

Address space related functions

oAllocate with number of pages

oReAllocate with number of new pages

Allocate a new address space of new pages long, and move old pages from old address space to the new address space

Think about Fork() system call you implement

oFree (DeAllocate) 

Think about Exit() system call

Implement the Page Table per user process (Nachos Thread)

oPTE contains the virtual address, owner’s pid, other control bits (dirty, referenced, …)

oPage fault handler

Your choice of page replacement algorithm

How to find a page on backing store

Implement demand-paging

oMove a page from backing store (swapping space: disk or file) to memory and from memory to backing store 

Your choice of backing store

May need a data structure to keep track of virtual pages in a particular backing store (Swap Table)

oFind free physical pages (Frame Table)

Linear search is not recommended

Page replacement algorithm

oYou can design your own or

oYou can choose one of replacement algorithms discussed in the class, not FIFO

You must need to compare the performance with random

(BONUS 10 pts) Implement software TLB with software translation via the page table

oHandle TLB miss properly

oMake sure TLB is set up properly on a context switch

It is up to you

You can invalidate all TLB entries on a context switch, reload the entries as pages are referenced

Or you can associate a process id (Nachos thread id) with the entries in the TLB

 

 

Task 4 (5%) Implement your user programs in test directory: Write your own user programs to verify that the system call handling and multiprogramming are working properly with your own memory management.

Write test programs to test each Task

oTask 1, run a single user program

you need to test read/write/exit syscalls

you need to test exec/exit syscalls by calling Exec x times

you need to test fork syscall

oTask 2, stress things more and run multiple programs

Run at least 4 your own test programs you write using new syscalls

oTask 3, run larger memory need programs (no need to write)

You need to run two matmul and one sort programs under test directory

You need to update Makefile under test directory to compile user programs using the MIPS cross-compiler.

 

Your document must include the followings:

Cover Page

Disclosure Form

How much time did you spend to do:

Analyze the problem, determine specifications, and create your design

Implement the design 

write the program

Test/debug the program 

Find/fix errors

Create test cases, and try them out

List of your files with directory name that you modified or created for this assignment

Design/your solution for each requirement

We are looking for your own answers

Implementation of your solution (Code snippet with good comments)

Do not include Nachos original code

We want to see your own code/modification

Should be text (no image/photo of code)

Testing

How to run your tests

What each test case is testing (you need to prove your implementation of each requirement in the following output snapshots)

You must test multiple user programs including matmul and sort for larger memory allocation needed Nachos physical memory size.

You need to verify that all system calls are correctly working.

Show meaningful result of performance measurement for your virtual memory management system per process (Nachos Thread) or entire system

Demand paging

Page replacement and handling dirty pages

Swapping (backing storage)

Page fault handling

Performance measurement

Number of memory references

TLB handler (TLB hit/miss rate)

Page Fault handler (Page hit/fault rate)

…

Output Snapshots

 

 

Testing:

We will build and run your Nachos on the VM. You must test your program on the VM and also should provide proper test scenario in your document.

 

Grading:

Syntax/Runtime/Logic Errors with proper Makefile [-50, -15]

Data structure design/class definition/declaration respectively [-40, -10]

Quality of your report/comments [-20, -5]

Quality of user programs [-30, -5]

Satisfy all implementation requirements [-50, -5]

Garbage collection (handle all objects at the end) [-10, -5]

Input/output design (meaningful messages to prove your implementation) [-30, -10]

Output(by Students)/Test(by TAs) [-50]

If you only did Task 1 and 2 with linear memory allocation without Task 3, you can get up to 50%.