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.
You can submit multiple times before the due.
After the due, you cannot resubmit newer version.
Do a make clean in codebuild.linux, then compress your Nachos folder on the VM, download the compressed file into your local machine and name the compressed file Ass2yourNetId.zip Note: Zip only!!. Submit the zipped file to the Assignment Code Submission link of Blackboard.
You need to submit the entire nachos directory
We will build and run your nachos, not individual files
Use naming convention
When we uncompress your zip file, we want to see your nachos like
Ass1netid
code
threads
machine
Do not change compiler option in Makefile
You have to make sure your submission is correctly made
If you dont have a confirm email, you should check again.
You should raise an appeal within a week after grade is posted.
Due: November11 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 userlevel 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 thats 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 ..testprog 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 diskfile 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: userprogsyscall.h defines the system call prototypes of Nachos. These are kernel procedures that user programs can invoke. You need to implement the system calls: haltalready done, Fork, Exit, Exec, Read, and Write.
Read and Write for console read and write, not for file read and write.
Were 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 were faking and not utilizing the Nachos console system, we can ignore the OpenFileId parameter. You need to obtain the rst two arguments from the user program. Refer to the comments in exception.cc for hints on how to obtain the parameter values.
Can 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 le name of a user program. The way Exec creates threads is similar to what you did for the x ag in Task 2. When a user program calls Exec, Nachos kernel creates a new thread for the executable le 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 dened in syscall.h of the new thread, which can be used as the argument of Join.
SpaceId idExec..testprog;
Must copy the filename argument from user memory to kernel memory safely
Refer to the comments in exception.cc for hints on how to return a value from system call.
This should be tested with Memory Manager.
Exit can be implemented with a simple call to Thread::Finish.
But you have to be careful. All resources including AddrSpace must be returnedfreed.
The kernel handles anExitsystem call by destroying the process Nachos Thread data structures and threads, reclaiming any memory assigned to the process
No return value
You need to protect the Nachos kernel from user program errors.
User 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 userprogexception.cc implements the handlers for system calls and other userlevel exceptions. In the original file, only the Halt system call is supported.
Hint: 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 machines memory, and provide a way of copying data fromto the users 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 theres only one thread, the main thread.
.nachos x ..testprog1 x ..testprog2 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 roundrobin scheduling.
Use quantum option for setting different time slice quantum for roundrobin
In order to test this task, you need to implement a memory manager of Task 3 or at least linear contiguous memory allocation for multiprogramming
Keep track of which frames are free and which are in use
Allow multiple processes Nachos Threads to be resident in the physical memory at the same time
New AddrSpace object per user program creation
When 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, youll get an assertion failure in userprogaddrspace.cc because theres 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 parts when they are accessed.
Address space related functions
Allocate with number of pages
ReAllocate 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
Free DeAllocate
Think about Exit system call
Implement the Page Table per user process Nachos Thread
PTE contains the virtual address, owners pid, other control bits dirty, referenced,
Page fault handler
Your choice of page replacement algorithm
How to find a page on backing store
Implement demandpaging
Move 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
Find free physical pages Frame Table
Linear search is not recommended
Page replacement algorithm
You can design your own or
You 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
Handle TLB miss properly
Make 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
Task 1, run a single user program
you need to test readwriteexit syscalls
you need to test execexit syscalls by calling Exec x times
you need to test fork syscall
Task 2, stress things more and run multiple programs
Run at least 4 your own test programs you write using new syscalls
Task 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 crosscompiler.
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
Testdebug the program
Findfix errors
Create test cases, and try them out
List of your files with directory name that you modified or created for this assignment
Designyour 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 codemodification
Should be text no imagephoto 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 hitmiss rate
Page Fault handler Page hitfault 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:
SyntaxRuntimeLogic Errors with proper Makefile 50, 15
Data structure designclass definitiondeclaration respectively 40, 10
Quality of your reportcomments 20, 5
Quality of user programs 30, 5
Satisfy all implementation requirements 50, 5
Garbage collection handle all objects at the end 10, 5
Inputoutput design meaningful messages to prove your implementation 30, 10
Outputby StudentsTestby TAs 50
If you only did Task 1 and 2 with linear memory allocation without Task 3, you can get up to 50.
Reviews
There are no reviews yet.