Operating System代写：CIS657 Virtual Memory System

研究TLB，虚拟内存(Virtual Memory)以及文件交换(Swapping Space)，在Nachos上设计并实现。

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

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.
  • We’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 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 id = Exec(“../test/prog”);
    • 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 returned/freed.
  • The kernel handles an Exit system call by destroying the process (Nachos Thread) data structures and thread(s), 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 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.
  • Hint: you can find a good example from system call Add.

Task 2

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. o Use -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 o Keep track of which frames are free and which are in use o Allow multiple processes (Nachos Threads) to be resident in the physical memory at the same time o New AddrSpace object per user program creation o When the user process (Nachos Thread) is destroyed, release the allocated page frames and AddrSpace object

Task 3

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
  • 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, owner’s pid, other control bits (dirty, referenced, )
  • Page fault handler
    • Your choice of page replacement algorithm
    • How to find a page on backing store
• Implement demand-paging
  • 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

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 read/write/exit syscalls
    • you need to test exec/exit 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 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%.